SIM Project: Optimizing a Benchmarking Tool
-
Upload
vlad-petre -
Category
Technology
-
view
522 -
download
1
description
Transcript of SIM Project: Optimizing a Benchmarking Tool
1 11.01.2011
SIM
DASCĂLU Cristian, 343C4
PETRE Vlad-Ştefan, 341C1
ŞERBĂNESCU Vlad-Nicolae, 341C3
2 11.01.2011
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.
4 11.01.2011
Analiza Sumară
5 11.01.2011
Abordări
• OpenMP
• Pthreads
• Optimizare serială
6 11.01.2011
OpenMP
• Abordare: introducerea de directive OpenMP de genul #pragma omp section sau #pragma omp for acolo unde este cazul.
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).
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.
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.
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.
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.
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]!!
}
}
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.
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.
15 11.01.2011
Branch Miss Predictions
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];
...
}
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.
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;
} }
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.
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.
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.
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
23 11.01.2011
Vă mulţumim pentru atenţie!
Întrebări?