SIM Project: Optimizing a Benchmarking Tool

23
1 11.01.2011 SIM DASCĂLU Cristian, 343C4 [email protected] PETRE Vlad-Ştefan, 341C1 [email protected] ŞERBĂNESCU Vlad-Nicolae, 341C3 [email protected]

description

Prezentare a proiectului de semestru, ce a constat in incercarea de a paraleliza un tool de benchmarking, sustinuta in ianuarie 2011, in cadrul laboratorului final al materiei Arhitecturi si Prelucrari Paralele (Facultatea de Automatica si Calculatoare - Universitatea Politehnica Bucuresti).

Transcript of SIM Project: Optimizing a Benchmarking Tool

Page 1: SIM Project: Optimizing a Benchmarking Tool

1 11.01.2011

SIM

DASCĂLU Cristian, 343C4

[email protected]

PETRE Vlad-Ştefan, 341C1

[email protected]

ŞERBĂNESCU Vlad-Nicolae, 341C3

[email protected]

Page 2: SIM Project: Optimizing a Benchmarking Tool

2 11.01.2011

Page 3: SIM Project: Optimizing a Benchmarking Tool

3 11.01.2011

Descrierea Proiectului

• SIM este un program serial bazat pe tehnici de programare dinamică, care caută similarităţi locale între două şiruri de caractere sau în cadrul aceleaşi secvenţe, folosind ponderi afine.

• Ca utilizare practică a acestui program, putem aminti compararea de secvenţe ADN sau rularea de benchmarkuri.

Page 4: SIM Project: Optimizing a Benchmarking Tool

4 11.01.2011

Analiza Sumară

Page 5: SIM Project: Optimizing a Benchmarking Tool

5 11.01.2011

Abordări

• OpenMP

• Pthreads

• Optimizare serială

Page 6: SIM Project: Optimizing a Benchmarking Tool

6 11.01.2011

OpenMP

• Abordare: introducerea de directive OpenMP de genul #pragma omp section sau #pragma omp for acolo unde este cazul.

Page 7: SIM Project: Optimizing a Benchmarking Tool

7 11.01.2011

Problema Principală

• Puţine zone de cod cu potenţial de paralelizare datorită algoritmului (avem multe dependinţe de date în zonele de cod care rulează mult timp).

Page 8: SIM Project: Optimizing a Benchmarking Tool

8 11.01.2011

Exemplu de Dependinţeregister long f; //f – este o variabilă globală (deci shared)

for ( i = m1 + 1; i <= mm; i++)

{ // Notă: Am scos liniile de cod irelevante din acest exemplu

f = - (q); //iniţializarea lui f

limit = i + 1;

for ( j = limit ; j <= nn ; j++ )

{

f = f - r; //dacă ar fi doar asta, aş putea să paralelizez

if ( f < c )

{

f = c; //dar eu nu pot şti când se intră aici

}

myf = f; //utilizarea variabilei în buclă

}

} // În “for”-ul principal mai avem o dependinţă pe care o va prezenta colegul meu peste câteva momente.

Page 9: SIM Project: Optimizing a Benchmarking Tool

9 11.01.2011

Problema Secundară

• Aplicarea directivelor OpenMP acolo unde este posibil (banale iniţializări ...) nu rentează datorită overhead-ului mare în lucrul cu threaduri comparativ cu câştigul computaţional.

Page 10: SIM Project: Optimizing a Benchmarking Tool

10 11.01.2011

Rezultate OpenMP

• Varianta paralelizată durează mai mult decât cea serială datorită overhead-ului mare şi a posibilităţilor reduse de a folosi directive OpenMP.

Page 11: SIM Project: Optimizing a Benchmarking Tool

11 11.01.2011

Pthreads

• Adăugarea unei rutine de execuţie a instrucţiunilor din “for-ul” cel mai din exterior din funcţia small_pass.

Page 12: SIM Project: Optimizing a Benchmarking Tool

12 11.01.2011

Problema Pthreads• Dependenţa de date din for-ul exterior al porţiunii principale a

funcţiei:for ( i = m1 + 1; i <= mm; i++) {

...

for ( j = limit ; j <= nn ; j++ ) {

/* citire RR[j] */

ci = RR[j]; //RR[j] este global, iar ci este local

ORDER(c, ci, cj, d, di, dj)

ORDER(c, ci, cj, f, fi, fj)

/* prelucrări ci */

RR[j] = ci; //scriere RR[j]!!

}

}

Page 13: SIM Project: Optimizing a Benchmarking Tool

13 11.01.2011

Rezultate Pthreads

• Partea de iniţializare.

• Overhead mare pentru 12000 de fire.

• Impărţirea celor 12000 de fire pe bucăţi, asemănător OpenMP.

Page 14: SIM Project: Optimizing a Benchmarking Tool

14 11.01.2011

Optimizare Serială

• Problema identificată: predictibilitatea scăzută a fluxului de instrucţiuni.

• Soluţia abordată: binary lookup table sau ceva similar.

Page 15: SIM Project: Optimizing a Benchmarking Tool

15 11.01.2011

Branch Miss Predictions

Page 16: SIM Project: Optimizing a Benchmarking Tool

16 11.01.2011

Varianta 1 for (j = 1; j <= N; j++)

{

if ( (c = c - qr) > (e = e – r) )

e = c;

if ((c = CC[j] - qr) > (d = DD[j] - r))

d = c;

DIAG(i+I, j+J, c, s+va[B[j]]);

if (c < d)

c = d;

if (c < e)

c = e;

s = CC[j];

CC[j] = c;

DD[j] = d;

}

for (...){

...

lookup_table[0] = c; lookup_table[1] = d; lookup_index = (c < d); c = lookup_table[lookup_index];

...

}

Page 17: SIM Project: Optimizing a Benchmarking Tool

17 11.01.2011

Rezultate Varianta 1

Dar timpul total de execuţie este mai mare: aproximativ 105s faţă de 90s pe un Intel Celeron 550 tactat la 2 GHz.

Page 18: SIM Project: Optimizing a Benchmarking Tool

18 11.01.2011

Varianta 2 ORDER(ss1, xx1, yy1, ss2, xx2, yy2)

{

if ( ss1 < ss2 )

{ ss1 = ss2; xx1 = xx2; yy1 = yy2; }

else

if ( ss1 == ss2 )

{ if ( xx1 < xx2 )

{ xx1 = xx2; yy1 = yy2; }

else

if ( xx1 == xx2 && yy1 < yy2 )

yy1 = yy2;

}

}

short _ORDER_case; ORDER(ss1, xx1, yy1, ss2, xx2, yy2) { _ORDER_case = (ss1 < ss2) | ((ss1 == ss2 && xx1 < xx2) << 1) | ((ss1 == ss2 && xx1 == xx2 && yy1 < yy2) << 2);

switch (_ORDER_case) {

case 1: ss1 = ss2; xx1 = xx2; yy1 = yy2; break;

case 2:xx1 = xx2; yy1 = yy2;

break; case 4:

yy1 = yy2; break;

} }

Page 19: SIM Project: Optimizing a Benchmarking Tool

19 11.01.2011

Rezultate Varianta 2

Dar timpul total de execuţie rămâne în continuare mai mare: aproximativ 115s faţă de 90s pe un Intel Celeron 550 tactat la 2 GHz.

Page 20: SIM Project: Optimizing a Benchmarking Tool

20 11.01.2011

Rezultate Finale

Varianta Optimizare Timp de rulare

Serial iniţial -g 1m20s

Serial iniţial -O3 29s

Serial optimizat -g 1m22s

OpenMP -g 1m22s

Pthreads -g 1m15s

Notă: • S-au folosit două fişiere de intrare, fiecare având dimensiunea de 12 KB.• Testele au fost efectuate pe Cluster, pe IBM-Opteron cu rezervare de 4 sloturi.

Page 21: SIM Project: Optimizing a Benchmarking Tool

21 11.01.2011

Concluzii• Din păcate, datorită faptului că algoritmul are un

grad ridicat de dependinţe de date, părţile cu adevărat importante din cod nu au putut fi paralelizate.

• Structura codului serial nu permite intervenţii de profunzime. Iar pentru cele de suprafaţă, raportul dintre overhead-ul introdus şi timpul câştigat este nefavorabil.

Page 22: SIM Project: Optimizing a Benchmarking Tool

22 11.01.2011

Referinţe

• http://www.google.com/codesearch/p?hl=en#yOs0oGPVNuU/MultiSource/Benchmarks/sim/ – Codul original al proiectului pe Google Code Search.

• https://ncit-cluster.grid.pub.ro/trac/APP2010/wiki/SIM:/

– Documentaţia proiectului nostru.• https://svn-batch.grid.pub.ro/svn/APP2010/proiecte/SIM/

– Codul proiectului nostru.• http://en.wikibooks.org/wiki/Optimizing_C++• http://www-graphics.stanford.edu/~seander/bithacks.html

Page 23: SIM Project: Optimizing a Benchmarking Tool

23 11.01.2011

Vă mulţumim pentru atenţie!

Întrebări?