Proiectare ¸ si dezvoltare formal˘ a a programelor paralele

(1)

Virginia Niculescu

CALCUL PARALEL

Proiectare ¸ si dezvoltare formal˘ a a programelor paralele

2005

(2)

blanc

(3)

iii

Familiei mele

(4)

(5)

Cuprins

Prefat¸˘a ix

I Fundamente 1

1 Not¸iuni generale 3

1.1 Clasific˘ari ale sistemelor paralele . . . 3

1.1.1 Clasificarea lui Flynn . . . 3

1.1.2 Alte clasificari . . . 8

1.2 Criterii de performant¸˘a ale sistemelor paralele . . . 11

1.3 Ret¸ele de interconectare a procesoarelor . . . 12

1.3.1 Topologii de baz˘a . . . 13

1.3.2 Problema includerii . . . 17

1.3.3 Comunicat¸ia ˆın ret¸ele . . . 19

1.4 Niveluri la care poate apare paralelism . . . 20

1.5 Clasificarea algoritmilor paraleli . . . 22

1.6 Modelul standard PRAM . . . 24

1.7 M˘asurarea performant¸ei algoritmilor paraleli . . . 27

1.7.1 Complexitatea-timp . . . 28

1.7.2 Accelerat¸ia . . . 28

1.7.3 Eficient¸a . . . 32

1.7.4 Costul ¸si volumul de lucru . . . 32

1.7.5 Paralelism limitat ¸si nelimitat . . . 33

1.7.6 Teorema lui Brent . . . 34

1.7.7 Clasa problemelor NC . . . 37

2 Construct¸ia programelor paralele 39 2.1 Etape ˆın dezvoltarea programelor paralele . . . 40

2.1.1 Partit¸ionarea . . . 41

2.1.2 Analiza comunicat¸iei . . . 43

2.1.3 Aglomerarea . . . 44

2.1.4 Maparea . . . 47 v

(6)

II Proiectare 49

3 Paradigme 51

3.1 Master/Slave . . . 51

3.2 Work Pool . . . 53

3.3 Paralelism al datelor . . . 53

3.4 Pipeline . . . 54

3.5 Divide&impera . . . 54

3.6 Alte clasific˘ari . . . 55

4 Tehnici 57 4.1 Tehnica paraleliz˘arii directe . . . 59

4.2 Tehnica arbore binar . . . 62

4.3 Tehnica dubl˘arii recursive . . . 64

4.4 Contract¸ia arborescent˘a . . . 67

4.5 Tehnica reducerii ciclice par-impar . . . 72

4.6 Tehnica divide&impera . . . 75

4.7 Algoritmii generici Ascend¸si Descend . . . 78

4.8 Tehnica calculului sistolic (pipeline) . . . 82

4.9 Tehnica par-impar . . . 89

4.10 Prefix paralel – Scan . . . 94

4.11 Branch-and-Bound . . . 100

4.12 Adaptarea algoritmilor paraleli . . . 101

4.13 S¸abloane de programare (Skeletons) . . . 107

4.14 Cˆat¸iva algoritmi paraleli remarcabili . . . 108

4.14.1 Sortare bitonic˘a . . . 108

4.14.2 ˆInmult¸ire matriceal˘a . . . 112

4.15 Memorie partajat˘a versus memorie distribuit˘a . . . 115

4.15.1 Programare paralel˘a bazat˘a pe transmitere de mesaje . . . 115

4.15.2 Programare paralel˘a bazat˘a pe memorie partajat˘a . . . 120

4.15.3 Memorie partajat˘a distribuit˘a . . . 121

III Dezvoltare formal˘ a 123

5 Modelul UNITY 125 5.1 Prezentarea general˘a a teoriei . . . 125

5.1.1 Separarea not¸iunilor: programe ¸si implement˘ari . . . 125

5.2 Notat¸ia programelor UNITY . . . 126

5.2.1 Instruct¸iunea de atribuire . . . 126

5.2.2 Sect¸iunea assign . . . 127

5.2.3 Sect¸iunea initially . . . 128

5.2.4 Exemple . . . 128

5.2.5 Sect¸iunea always . . . 130

(7)

CUPRINS vii

5.3 Reguli de demonstrare . . . 130

5.3.1 Not¸iuni de baz˘a . . . 130

5.3.2 Un model al execut¸iei programului . . . 131

5.3.3 Concepte fundamentale . . . 132

5.3.4 Un exemplu complet – ˆımp˘art¸ire ˆıntreag˘a . . . 134

5.4 Maparea programelor pe arhitecturi . . . 138

5.5 Aplicat¸ii . . . 138

5.5.1 Eliminare Gauss-Jordan nedeterminist˘a . . . 138

5.5.2 Inversa unei matrice ¸si rezolvare de sistem liniar . . . 142

5.5.3 ˆInmult¸irea matricelor booleene . . . 144

6 Dezvoltare formal˘a din specificat¸ii 153 6.1 Descrierea metodei . . . 153

6.1.1 Construct¸ia programelor paralele . . . 155

6.1.2 Specificat¸ii funct¸ionale . . . 155

6.1.3 Invariant¸i . . . 156

6.1.4 Corectitudinea . . . 157

6.1.5 Notat¸ia programelor . . . 158

6.1.6 Reguli de demonstrare . . . 159

6.1.7 Procese de comunicat¸ie . . . 163

6.1.8 Complexitatea . . . 163

6.1.9 Regula ParSeq . . . 167

6.2 Distribut¸ia datelor . . . 168

6.2.1 Distribut¸ii simple . . . 168

6.2.2 Distribut¸ii multivoce . . . 175

6.3 Aplicat¸ii . . . 179

6.3.1 Operat¸ii prefix . . . 179

6.3.2 ˆInmult¸ire matriceal˘a . . . 182

6.3.3 Polinomul de interpolare Lagrange . . . 186

7 Formalismul Bird-Meertens – BMF 195 7.1 Omeomorfisme pe liste . . . 198

7.1.1 Extragere . . . 199

7.1.2 Aproape-omeomorfisme . . . 201

7.2 Implementare . . . 203

7.2.1 Sortare prin num˘arare . . . 204

7.3 Tipuri de date categoriale . . . 208

7.3.1 Tipul arbore binar omogen . . . 210

8 Structuri de date pentru paralelism 213 8.1 Structuri de dateP owerList . . . 214

8.1.1 Definit¸ii . . . 214

8.1.2 Principiul induct¸iei pentru P owerList . . . 216

8.1.3 Operatori, relat¸ii ¸si funct¸ii . . . 216

(8)

8.1.4 Complexitatea funct¸iilor definite pe P owerList . . . 218

8.1.5 Maparea pe hipercuburi . . . 219

8.1.6 Aplicat¸ii . . . 219

8.2 Structuri de dateP arList . . . 222

8.2.1 Definit¸ii . . . 222

8.2.2 Un principiu al induct¸iei pentru P arList . . . 224

8.2.4 Aplicat¸ii . . . 227

8.3 Structuri de dateP List . . . 230

8.3.1 Definit¸ii . . . 230

8.3.2 Un principiu al induct¸iei pentru P List . . . 232

8.3.3 Aplicat¸ii . . . 234

8.4 Transformarea Fourier rapid˘a . . . 235

8.4.1 Cazul n=2^k . . . 236

8.4.2 Cazul n prim . . . 238

8.4.3 Cazul n=r₁r₂. . . r_p . . . 238

8.5 Structuri de date n-dimensionale . . . 241

8.5.1 Definit¸ii . . . 241

8.5.2 Un principiu al induct¸iei pentru P owerArray . . . 242

8.5.4 Aplicat¸ii . . . 246

8.5.5 Evaluarea relat¸iilor de recurent¸˘a . . . 248

IV Modele 253

9 Modele de calcul paralel 255 9.1 Caracteristicile unui model de calcul paralel ideal . . . 255

9.2 Clasificarea modelelor . . . 261

9.2.1 Paralelism implicit . . . 263

9.2.2 Descompunere implicit˘a . . . 271

9.2.3 Descompunere explicit˘a . . . 274

9.2.4 Mapare explicit˘a . . . 276

9.2.5 Comunicat¸ie explicit˘a . . . 279

9.2.6 Totul explicit . . . 282

Anex˘a – Not¸iuni de teoria grafurilor 287

Bibliografie 290

Index 300

(9)

Prefat ¸˘ a

ˆIn timp ce multe probleme de mare interes practic cer tot mai mult˘a putere de calcul, viteza componentelor calculatoarelor se apropie de limitele posibile. Este ˆın general ac- ceptat ¸si chiar dovedit faptul c˘a aceste probleme ce necesit˘a calcul intensiv nu vor putea fi rezolvate prin cre¸sterea continu˘a a performant¸elor calculatoarelor individuale, ci singura solut¸ie viabil˘a este folosirea calculului paralel.

Ma¸sinile paralele, constˆand din mii de procesoare, ofer˘a o putere de calcul foarte mare pentru aplicat¸ii complexe. Comunitatea potent¸ialilor utilizatori cre¸ste foarte puternic ¸si datorit˘a ret¸elelor globale, care aduc hard, soft ¸si expertize din surse dispersate geogra- fic. Totu¸si, calculul paralel nu a devenit deocamdat˘a, o cale de rezolvare mai rapid˘a a problemelor, cu o foarte larg˘a r˘aspˆandire.

ˆIn acest moment programarea paralel˘a este proiectat˘a, ˆın general, pentru tipuri speciale de arhitecturi ¸si de aceea mutarea unui program de pe o arhitectur˘a pe alta, necesit˘a rescrierea lui aproape ˆın ˆıntregime. Singura cale de a dep˘a¸si aceast˘a problem˘a ¸si de a folosi paralelismul pe scar˘a larg˘a, este de a distruge aceast˘a conexiune strˆans˘a dintre soft

¸si hard.

Scopul principal al paralelismului este performant¸a, dar aceasta este ˆın acela¸si timp ¸si sursa principal˘a a dificult˘at¸ilor legate de paralelism. Pentru a proiecta o solut¸ie paralel˘a eficient˘a, programatorul trebuie s˘a descompun˘a problema ˆıntr-o colect¸ie de procese care se pot executa simultan, s˘a mapeze procesele pe procesoarele disponibile, s˘a sincronizeze procesele, s˘a organizeze comunicat¸iile, etc. Pentru acestea s-au dezvoltat numeroase familii particulare de algoritmi, limbaje ¸si tehnici de implementare, pentru diferite tipuri de arhitecturi.

Criza program˘arii secvent¸iale a evident¸iat necesitatea abstractiz˘arii ¸si ascunderii deta- liilor nivelului de jos de programare. ˆIn programarea paralel˘a, necesitatea abstractiz˘arii este ¸si mai acut˘a, datorit˘a complexit˘at¸ii programelor paralele. Dac˘a programatorii de aplicat¸ii, consider˘a abstractizarea foarte necesar˘a, totu¸si implementatorii programelor paralele sunt de p˘arere c˘a aceasta intr˘a ˆın conflict cu performant¸a. Reconcilierea dintre abstractizare ¸si performant¸˘a, pare a fi calea prin care programarea paralel˘a s-ar putea impune mai mult ˆın viitor.

ˆIn procesul de dezvoltare a unui program se pot identifica trei etape:

Specificarea. Construirea formal˘a a unei descrieri a problemei care trebuie s˘a fie rezol- vat˘a. Aceast˘a descriere exprim˘a esent¸a problemei. Specificat¸ia trebuie s˘a ajute la demonstrarea formal˘a a corectitudinii programului rezultat ˆın final.

ix

(10)

Figura 1: Rolul modelului ˆın calculul paralel

Proiectarea. Sarcina de a crea un “program”, care s˘a satisfac˘a specificat¸ia problemei ¸si care s˘a poate fi implementat eficient pe o arhitectur˘a t¸int˘a.

Implementarea. Maparea programului pe resursele de calcul disponibile pentru execu- t¸ia sa. Aceasta trebuie s˘a fie f˘acut˘a folosind instrumente ¸si tehnici, care au fost verificate formal.

Proiectarea este o etap˘a fundamental˘a nu doar pentru aplicat¸iile de dimensiuni mari, dar ¸si ˆın cazul algoritmilor. Paradigme precum programarea structurat˘a, proiectarea

“top-down” sau “bottom-up” sunt bine cunoscute. La nivel de algoritm, pentru programarea secvent¸ial˘a, sunt de asemenea bine cunoscute tehnici de programare precum:

greedy, backtraking, branch-and-bound, sau programarea dinamic˘a. Ele direct¸ioneaz˘a construct¸ia programelor, permit st˘apˆanirea complexit˘at¸ii oferind un cadru ¸stiint¸ific ¸si matematic ¸si, de asemenea, permit realizarea unor bune documentat¸ii.

Pentru programarea paralel˘a, faza de proiectare este poate chiar mai important˘a decˆat ˆın cazul program˘arii secvent¸iale, datorit˘a gradului ridicat al complexit˘at¸ii programelor paralele. Putem analiza, ¸si ˆın acest caz, diferite paradigme consacrate, precum ¸si tehnici de programare care ghideaz˘a construct¸ia algoritmilor paraleli.

ˆIn programarea secvent¸ial˘a, faza de implementare este realizat˘a de obicei de un compilator capabil s˘a produc˘a cod optimizat pentru o arhitectur˘a t¸int˘a. Asemenea compilatoare sunt posibile, deoarece majoritatea arhitecturilor secvent¸iale sunt similare la nivele ˆınalte de abstractizare ¸si diferent¸ele de la nivelele de jos pot fi rezolvate de c˘atre compilator.

ˆIn plus, datorit˘a arhitecturilor similare, limbajele de nivel ˆınalt pot fi proiectate, f˘ar˘a a sacrifica strategiile de compilare eficiente. Aceasta permite programatorilor de programe secvent¸iale, luxul de a se concentra asupra corectitudinii ¸si complexit˘at¸ii abstracte a programelor, l˘asˆand compilatorului sarcina de a le implementa eficient ¸si corect.

Arhitecturile paralele sunt foarte diferite unele de altele, chiar ¸si la nivele ˆınalte de abstractizare. O posibil˘a abordare este de a l˘asa limbajul s˘a reflecte particularit˘at¸ile arhitecturii – dar aceasta nu este totu¸si, o solut¸ie prea bun˘a. O alt˘a abordare ar fi de a face abstract¸ie de considerat¸iile arhitecturale ¸si de a construi un limbaj de programare

(11)

CUPRINS xi bazat pe not¸iunile abstracte ale paralelismului. Aceasta permite programatorului s˘a se concentreze asupra a ceea ce trebuie f˘acut, mai degrab˘a decˆat asupra cum se poate face pe o anumit˘a arhitectur˘a.

ˆIn concluzie, este important˘a rezolvarea conflictului dintre soft ¸si hard ˆın programarea paralel˘a prin decuplarea semanticii programelor de potent¸ialele lor implement˘ari. Aceasta se poate face printr-un model de calcul paralel. Un model furnizeaz˘a programatorului o singur˘a ma¸sin˘a paralel˘a abstract˘a, permint¸ˆand diferite implement˘ari pe arhitecturi concrete, diferite (Figura 1).

Un program paralel poate implica multe procese cu interact¸iuni complexe. Este cunoscut faptul c˘a gradul ˆınalt de complexitate al unui program paralel face extrem de dificil˘a dezvoltarea lui. Un model de proiectare a programelor paralele trebuie s˘a poat˘a pune la dispozit¸ie mecanisme prin care s˘a se poat˘a st˘apˆani complexitatea ¸si care s˘a permit˘a verificarea formal˘a a corectitudinii programelor paralele. Aceasta conduce la necesitatea folosirii metodelor formale, adic˘a folosirea de instrumente ¸si tehnici bazate pe modele matematice de calcul.

În general, pentru dezvoltarea algoritmilor paraleli s-a folosit mai degrab˘a intuit¸ia decât metode formale de derivare. Folosirea unor astfel de metode, poate u¸sura mult procesul de derivare a algoritmilor paraleli, asigurându-se ˆın acela¸si timp ¸si corectitudinea lor. Derivarea corect˘a este esent¸ial˘a, datorit˘a depan˘arii greoaie a programelor paralele.

Intuit¸ia nu poate fi ˆıntotdeauna folosit˘a cu succes, iar folosirea unei metode formale poate conduce la obt¸inerea unor variante eficiente, chiar dac˘a nu atˆat de evidente.

Exist˘a mai multe modele pentru calcului paralel (care vor fi analizate ˆın Capitolul 9), fiecare cu propria metod˘a de derivare a algoritmilor, mai riguroas˘a sau mai put¸in riguroas˘a. Modelele se diferent¸iaz˘a prin gradul lor de abstractizare, ¸si prin urmare, ¸si metodele de derivare a algoritmilor pot fi mai generale sau particularizate pentru anumite variante de programare paralel˘a.

Cartea ˆı¸si propune s˘a prezinte atât tehnici de proiectare cât ¸si metodologii de dezvoltare formal˘a a programelor paralele ¸si este dedicat˘a atât student¸ilor de la sect¸iile de informatic˘a ¸si calculatoare, cât ¸si tuturor celor interesat¸i de aprofundarea problemelor legate de calculul paralel.

Prima parte a c˘art¸ii trateaz˘a fundamentele calcului paralel ¸si ale proiect˘arii programelor paralele. Primul capitol introduce not¸iunile fundamentale ce intervin ˆın calculul paralel: tipuri de arhitecturi, tipuri de ret¸ele de interconectare, m˘asuri ale performant¸ei, caracteristici ale algoritmilor paraleli, etc. ˆIn cel de-al doilea capitol se evident¸iaz˘a etapele de baz˘a ale construct¸iei programelor paralele.

A doua parte format˘a din capitolele 3 ¸si 4 trateaz˘a paradigme ¸si tehnici de proiectare ale programelor paralele. Sunt analizate tehnici precum: dublarea recursiv˘a, divide&impera, arbore binar, pipeline, etc. Cititorul poate g˘asi numeroase exemple care ilustreaz˘a aceste tehnici, dar care reprezint˘a ¸si solut¸ii paralele pentru unele probleme foarte des ˆıntˆalnite.

Cea de-a treia parte a c˘art¸ii prezint˘a diferite modele de dezvoltare formal˘a a programelor paralele.

UNITY ”Unbounded Nondeterministic Iterative Transformations” reprezint˘a o teorie, care este ˆın acela¸si timp ¸si un model de calcul ¸si un sistem de demonstrare. Aceast˘a

(12)

teorie are ca scop introducerea unei metodologii de dezvoltare de programe, care s˘a fie independent˘a de arhitectura secvent¸ial˘a sau paralel˘a, pe care se vor implementa.

ˆIn Capitolul 6 se prezint˘a o metod˘a de dezvoltare corect˘a a programelor paralele, por- nind de la specificat¸ii. Metoda prezentat˘a folose¸ste procese parametrizate ¸si structurarea pe nivele a programelor. Distribut¸ia datelor este determinant˘a ˆın construct¸ia programelor paralele ¸si este aici analizat˘a formal.

Propriet˘at¸ile program˘arii funct¸ionale fac ca aceasta s˘a aduc˘a avantaje importante pentru programarea paralel˘a, f˘acˆand posibil˘a dezvoltarea programelor prin transform˘ari riguroase ¸si exploatˆand mecanisme de abstractizare a datelor. Capitolul 7 prezint˘a o abordare funct¸ional˘a de dezvoltare a programelor paralele, care combin˘a abstractizarea

¸si performant¸a ˆıntr-un mod sistematic. Este folosit formalismul BMF cu structura de baz˘a lista, cu operatorul de concatenare ca ¸si constructor.

Algoritmii recursivi intervin ˆın rezolvarea unei mari variet˘at¸i de probleme, constitu- indu-se astfel ˆıntr-o clas˘a important˘a de probleme. PowerList,ParList¸siPList sunt teorii bazate pe structuri de date liniare, ce pot fi folosite cu succes ˆın descrierea funct¸ional˘a simpl˘a a programelor paralele care sunt de natur˘a Divide&Impera. Folosind tehnici formale se pot deriva descrieri succinte pentru programele paralele, plecˆand de la specificat¸ii.

Capitolul 8 descrie acest formalism.

Ultimul capitol face o analiz˘a ¸si o clasificare general˘a a modelelor de calcul paralel existente, plecˆand de la caracteristicile pe care un asemenea model trebuie s˘a le satisfac˘a.

(13)

xiii

Notat ¸ii folosite

Notat¸ia pentru exprimarea cuantific˘arilor difer˘a put¸in de cea folosit˘a ˆın mod uzual ˆın matematic˘a. Formatul general este:

(k :Q:E), undeeste un cuantificator, de exempluP

,max,∀etc., keste o list˘a de variabile legate, Q este un predicat care descrie domeniul variabilelor, iar E este o expresie care cont¸ine variabilelek. Tipul de baz˘a al variabilelor este tipul ˆıntreg.

Aceast˘a notat¸ie are avantajul clarit˘at¸ii, ˆın cazul ˆın care domeniul variabilelor este exprimat prin mai multe relat¸ii.

Mult¸imile sunt notate ˆın mod similar cu cuantific˘arile. Notat¸ia V ={i, j :i²+j² =a² : (i, j)}

specific˘a mult¸imea tuturor perechilor de ˆıntregi de pe cercul cu centrul ˆın origine ¸si de raz˘a a. Cardinalul mult¸imii V este notat cu |V|.

Aplicat¸ia funct¸iilor este notat˘a prin punct (.). Are prioritate maxim˘a ¸si este asociativ˘a la stˆanga. De exemplu, f.a.b este echivalent cu (f.a).b. Vom folosi aceast˘a notat¸ie doar pentru funct¸iile care exprim˘a algoritmi sau au leg˘atur˘a cu derivarea programelor; pentru funct¸iile care exprim˘a formule matematice vom folosi notat¸ia clasic˘a.

Pentru funct¸iile anonime se folose¸ste o abstractizare lambda. De exemplu, (λn·n²) reprezint˘a funct¸ia care returneaz˘a p˘atratul argumentului s˘au.

Derivarea demonstrat¸iilor este f˘acut˘a cu urm˘atorul stil de notat¸ie, datorat lui W.F.H.

Feijen:

E₀

= {explicat¸ia egalit˘at¸ii}

E₁

≥ {explicat¸ia inegalit˘at¸ii}

E₂

unde Ei,0 ≤ i < 3 sunt expresii. ˆIn acest fel, derivarea E0 ≥ E2 este f˘acut˘a prin intermediul expresiei intermediare E₁.

Pentru operat¸iile cu numere ˆıntregi, not˘am operat¸ia modulo cu %.

Mult¸imea numerelor {0,1, . . . , n−1}, n >0 se va nota cu n.

(14)

(15)

List˘ a de figuri

1 Rolul modelului ˆın calculul paralel . . . x

1.1 Arhitectura uniprocesor SISD. . . 4

1.2 Arhitectura SIMD. . . 5

1.3 Arhitectura MISD – arhitectura sistolic˘a. . . 5

1.4 Arhitectura MIMD cu memorie partajat˘a. . . 7

1.5 Multicalculator bazat pe transmitere de mesaje. . . 8

1.6 Clasificarea lui Hocney. . . 10

1.7 (a) – Ret¸eaua liniar˘a(lant¸); (b) – ret¸eaua ciclic˘a(inel). . . 13

1.8 Ret¸eaua arbore binar pentru n= 15. . . 14

1.9 (a) Ret¸eaua gril˘a cu M = 4 ¸si N = 6. (b) Ret¸eaua tor cuM = 4 ¸si N = 6. 14 1.10 Ret¸eaua fluture pentru k = 3. . . 15

1.11 Ret¸eaua hipercub. . . 16

1.12 Ret¸eaua amestecare perfect˘a pentru n= 8. . . 17

1.13 (a)Ciclu hamiltonian ˆıntr-o gril˘a 4 ×5; (b) scufundarea unui inel ˆıntr-o gril˘a 5×5 cu dilatare 2; (c) ciclu hamiltonian ˆıntr-un tor 5×5. . . 18

1.14 Dou˘a cicluri hamiltoniene ale hipercubului de ordin 3. . . 19

1.15 Scufundarea unei grile 4×4 ˆıntr-un hipercub de ordin 4. . . 19

1.16 Niveluri ale paralelismului. . . 21

1.17 Dependent¸a performant¸ei de num˘arul de procesoare. . . 24

1.18 Exemplificarea legii lui Amdahl. . . 30

1.19 Accelerat¸ia ˆın funct¸ie de num˘arul de procesoare. . . 31

1.20 Volumul de lucru. . . 33

1.21 Ret¸ea de calcul, cu adˆancimea 7, pentru adunarea a 8 numere. . . 36

1.22 Ret¸ea de calcul, cu adˆancimea 3, pentru adunarea a 8 numere. . . 37

2.1 Etape ˆın dezvoltarea programelor paralele. . . 40

2.2 Tehnicile de partit¸ionare a datelor prin “t˘aiere” ¸si “ˆıncret¸ire”. . . 42

2.3 Efectul suprafat¸˘a-volum. . . 45

3.1 Paradigma “Master/Slave”. . . 52

3.2 Paradigma “Work Pool”. . . 53

3.3 Structura pipeline. . . 54

4.1 Ret¸ea de calcul de tip arbore binar. . . 62 xv

(16)

4.2 Tehnica “pointer-jumping” . . . 65

4.3 Construirea arborelui de acoperire minim. . . 67

4.4 Operat¸iilerakepentru calcularea expresieiE = ((2∗3) + (4 + 5∗6))∗2 = 80. 71 4.5 Ret¸ele de calcul pentru relat¸ia de recurent¸˘a de ordin n= 4. . . 73

4.6 Tipul 1 de calcul pipeline. . . 82

4.9 ˆInmult¸ire matriceal˘a pe un tablou sistolic. . . 88

4.10 Sortare prin transpozit¸ie par-impar. . . 89

4.11 Interclasare par-impar a dou˘a liste sortate. . . 90

4.12 Actualizarea aproxim˘arilor ˆın metoda Jacobi. . . 92

4.13 Actualizarea aproxim˘arilor ˆın metoda Gauss-Seidel. . . 92

4.14 Avansarea frontului de aproxim˘ari ˆın metoda Gauss-Seidel. . . 93

4.15 Colorarea grilei de noduri ˆın cazul metodei ro¸su-negru. . . 93

4.16 Ret¸eaua de calcul secvent¸ial pentru sumele prefix. . . 95

4.17 Ret¸eaua de calcul folosind algoritmul prefix sus-jos. . . 96

4.18 Ret¸eaua de calcul folosind algoritmul prefix impar-par. . . 97

4.19 Ret¸eaua de calcul folosind algoritmul prefix Ladner-Fisher. . . 98

4.20 Sortarea rapid˘a pe un hipercub cu 4 procesoare. . . 104

4.21 Sortarea bitonic˘a pentru o secvent¸˘a de n = 8 elemente. . . 109

4.22 Intrarea datelor ˆın comparatori dup˘a o amestecare. . . 111

4.23 Sortarea bitonic˘a pe interconexiunea amestecare perfect˘a. . . 112

4.24 Deplasarea datelor ˆın Algoritmul lui Canon. . . 113

4.25 Partit¸ionarea matricelor ˆın submatrice pentru algoritmul lui Strassen. . . 115

4.26 Transmiterea unei date ˆıntre dou˘a procese. . . 116

4.27 Modelul SPMD de crearea a proceselor (MPI). . . 117

4.28 Modelul MPMD de crearea a proceselor (PVM). . . 117

4.29 Barier˘a de sincronizare folosind o actualizare a unui contor. . . 119

4.30 Barier˘a de sincronizare folosind o comunicat¸ie cu structur˘a de tip arbore binar. . . 119

4.31 Barier˘a de sincronizare folosind o comunicat¸ie cu structur˘a de tip fluture. 119 6.1 Calculul operat¸iei prefix – structura comunicat¸iei. . . 182

6.2 Interpolare Lagrange cu distribut¸ii simple . . . 187

6.3 Distribut¸ia datelor pentru m= 9 ¸si M = 3. . . 189

6.4 Interpolare Lagrange cu distribut¸ii multivoce . . . 191

7.1 Sortare prin num˘arare – programul SM pentru p≤n. . . 206

7.2 Sortare prin num˘arare – programul DM pentru p≤n. . . 207

8.1 Ret¸eaua de calcul pentru [x₀, x₁, x₂, x₃;f] . . . 229

8.2 Structura arborescent˘a pentru matriceaM . . . 243

8.3 Transpunerea unei matrice . . . 246

9.1 Un superpas BSP. . . 275

(17)

Partea I Fundamente

1

(18)

(19)

Capitolul 1

Not ¸iuni generale ale calculului paralel

1.1 Clasific˘ ari ale sistemelor paralele

Spre deosebire de calculatoarele secvent¸iale unde modelul de calcul von Neumann este unic ¸si foarte simplu conceptual, ˆın domeniul calculului paralel coexist˘a mai multe modele de arhitecturi care trebuie avute ˆın vedere. Nevoia de ordonare a determinat, ulterior, propunerea a numeroase clasific˘ari, cˆateva dintre ele fiind consacrate de c˘atre comunitatea stiint¸ific˘a. Clasificarea propus˘a de M. Flynn [61] este cea mai popular˘a, probabil ¸si datorit˘a simplit˘at¸ii ei.

1.1.1 Clasificarea lui Flynn

Clasificarea lui Flynn [61] se realizeaz˘a preponderent pe baza definirii ¸si utiliz˘arii not¸iunilor de flux de instruct¸iuni ¸si flux de date. Conform acestei clasific˘ari avem urm˘atoarele categorii de calculatoare:

1. Sisteme de calcul cu flux unic de instruct¸iuni ¸si flux unic de date (SISD - “Single Instruction Single Data”)ˆın care un flux unic de instruct¸iuni opereaz˘a asupra unui singur flux de date. Acest tip de arhitectur˘a corespunde sistemelor de calcul mono- procesor, clasice. Totu¸si ele nu exclud paralelismul ˆın totalitate (organiz˘ari de tip look-ahead, pipeline, blocuri funct¸ionale ale microprocesoarelor moderne, . . . ).

Calculatoarele SISD pot avea mai multe unit˘at¸i funct¸ionale de exemplu: coproce- soare matematice, unit˘at¸i vectoriale, procesoare grafice ¸si de intrare-ie¸sire. Aceste calculatoare se ˆıncadreaz˘a ˆın categoria SISD atˆata timp cˆat au doar un procesor.

Exemple de calculatoare SISD care folosesc paralelismul sunt: CDC 6600 care are multiple unit˘at¸i funct¸ionale, CDC 7600 care are o unitate aritmetic˘a de tip pipeline, Cray-1 care suport˘a procesarea vectorial˘a.

2. Sisteme de calcul cu un flux de instruct¸iuni ¸si fluxuri de date multiple (SIMD -

“Single Instruction Multiple Data”)ˆın care un singur flux de instruct¸iuni opereaz˘a 3

(20)

Figura 1.1: Arhitectura uniprocesor SISD (IS – flux de instruct¸iuni, DS – flux de date, CU – unitate de control, PU – procesor, MU – memorie).

asupra mai multor fluxuri de date. Aceast˘a clas˘a presupune existent¸a unor elemente de procesare identice (PE) ¸si capabile s˘a execute aceea¸si instruct¸iune pe seturi diferite de date ¸si care sunt dirijate de c˘atre o unitate de control (CU). Modelele SIMD pot varia ˆın funct¸ie de modul de transmitere a datelor ˆıntre elementele de procesare.

Elementele de procesare pot comunica ˆıntre ele printr-o memorie partajat˘a sau prin intermediul unit˘at¸ii de control.

Execut¸ia instruct¸iunilor este sincron˘a, ˆın sensul c˘a fiecare PE care execut˘a o instruct¸iune ˆın paralel trebuie s˘a termine execut¸ia respectivei instruct¸iuni ˆınainte ca o nou˘a instruct¸iune s˘a fie lansat˘a ˆın execut¸ie.

Tablourile de procesoare sunt exemple tipice de ma¸sini SIMD. Un tablou de procesoare este format dintr-o unitate de control care decodific˘a instruct¸iunile ¸si transmite semnale control c˘atre mai multe elemente de procesare care lucreaz˘a cu datele locale. O unitate central˘a, ˆıns˘a, nu poate comanda un num˘ar mare de procesoare, decˆat cu adoptarea unor solut¸ii costisitoare. Fiecare PE se poate g˘asi ˆıntr-o stare fie activ˘a, fie inactiv˘a ˆın timpul unui ciclu de execut¸ie. Dac˘a un PE se g˘ase¸ste ˆıntr-o stare inactiv˘a atunci el nu execut˘a instruct¸iunea care i-a fost trimis˘a de c˘atre unitatea central˘a. Selectarea PE active se face pe baza unor scheme de mascare.

Aceste scheme pot depinde de adresele elementelor de procesare sau de datele lor locale.

Procesarea vectorial˘a poate fi executat˘a pe un tablou de procesoare. Prin procesare vectorial˘a se ˆınt¸elege prelucrarea informat¸iei reprezentat˘a sub form˘a de vectori. O operat¸ie vectorial˘a presupune operanzi sub forma de vectori, iar rezultatul obt¸inut este ˆın general tot un vector. Pe un tablou de procesoare, dac˘a o operat¸ie este de tip scalar atunci ea va fi executat˘a de unitatea central˘a, iar dac˘a operat¸ia este de tip vectorial atunci ea va fi executat˘a de c˘atre elementele de procesare.

Calculatoarele vectoriale prezint˘a caracteristice specifice pentru procesarea vectorial˘a ¸si se ˆıncadreaz˘a tot ˆın clasa ma¸sinilor SIMD.

Exemple de calculatoare care corespund acestei categorii sunt: ILLIAC-IV, PEPE, BSP, STARAN MPP, DAP ¸si Connection Machine(CM-1).

3. Sisteme de calcul cu fluxuri multiple de instruct¸iuni ¸si flux unic de date (MISD - “Multiple Instruction Single Data”) ˆın care mai multe fluxuri de instruct¸iuni

(21)

1.1. CLASIFIC ˘ARI ALE SISTEMELOR PARALELE 5

Figura 1.2: Arhitectura SIMD (IS – flux de instruct¸iuni, DS – flux de date, CU – unitate de control, PE – element de procesare, LM – memorie local˘a).

Figura 1.3: Arhitectura MISD – arhitectura sistolic˘a (IS – flux de instruct¸iuni, DS – flux de date, CU – unitate de control, PU – procesor).

opereaz˘a asupra aceluia¸si flux de date. Aceast˘a clas˘a pare a fi vid˘a, cu toate c˘a ˆın ea ar putea fi cuprinse structuri specializate de calcul. Execut¸ia simultan˘a a mai multor operat¸ii asupra aceleia¸si date este dificil de definit: poate fi stabilit˘a o ordine de execut¸ie a operat¸iilor ¸si care este rezultatul final? De aceea, ˆın timp ce unii consider˘a acest model arhitectural pur teoretic, alt¸ii consider˘a c˘a arhitecturile sistolice s-ar ˆıncadra ˆın aceast˘a categorie.

O arhitectur˘a sistolic˘a const˘a dintr-o mult¸ime de elemente de procesare, sincronizate ¸si construite pentru un scop precis, care sunt interconcetate ˆıntr-o ret¸ea cu structur˘a fix˘a. Fiecare PE “pompeaz˘a” ˆın mod regulat datele ˆın interior ¸si ˆın exte- rior, de fiecare dat˘a executˆand un anumit calcul simplu. Funct¸ia unui asemenea PE

¸si schema de interconectare depinde ˆın general de problema care se rezolv˘a. Simpli- tatea elementelor de procesare ¸si uniformitatea ¸sablonului de interconectare permite ma¸sinilor sistolice cu un num˘ar mare de elemente de procesare s˘a fie implementate pe un singur chip folosind tehnologia VLSI (“Very Large System Integration”).

Sarcinile de calcul se divid ˆın dou˘a clase mari: calcule propriu-zise ¸si operat¸ii de I/O.

ˆIn general o ma¸sin˘a sistolic˘a poate fi definit˘a ca o ret¸ea de calcul care are urm˘atoarele propriet˘at¸i:

(22)

i Simplitate ¸si regularitate: ma¸sina const˘a ˆıntr-un num˘ar mare de elemente de procesare simple cu interconexiuni simple ¸si omogene.

ii Sincronicitate: Datele sunt calculate ritmic fiind dirijate de un ceas global.

iii “Pipelining”: La fiecare pas rezultatul unui calcul executat de c˘atre un PE devine intrare pentru un PE vecin.

Ret¸eaua de interconectare poate fi liniar˘a, caz ˆın care putem considera c˘a avem un calculator pipeline, sau poate fi mai complex˘a - de exemplu bidimensional˘a.

Aceste tipuri de arhitecturi au fost ˆıncadrate ˆın diferite exemple din literatur˘a atˆat ˆın clasa SISD cˆat ¸si ˆın SIMD.

4. Sisteme cu fluxuri multiple de instruct¸iuni ¸si fluxuri multiple de date (MIMD -

“Multiple Instruction Multiple Data”) sunt sistemele la care mai multe fluxuri de instruct¸iuni opereaz˘a simultan asupra unor fluxuri de date diferite. Fluxurile de instruct¸iuni pot fi identice (SPMD - “Single Program Multiple Data”) sau nu, dar ele nu se execut˘a sincron. Aceast˘a clas˘a include toate formele de configurat¸ii multiprocesor, de la ret¸elele de calcul de uz general pˆan˘a la masivele de procesoare. Ele pot fi cu memorie comun˘a sau distribuit˘a. Aceste tipuri de sisteme reprezint˘a cele mai folosite arhitecturi paralele.

Calculatoarele MIMD, sau calculatoarele cu unit˘at¸i de control (CPU) multiple, constau ˆıntr-un num˘ar de elemente de procesare, care pot fi indexate individual.

Fiecare are propriul indice ¸si memorie local˘a unde pot fi stocate atˆat datele cˆat

¸si programul. Elementele de procesare sunt complet programabile ¸si pot executa propriul program.

Arhitecturile MIMD cu memorie partajat˘a permit fiec˘arei unit˘at¸i de procesare s˘a acceseze o memorie global˘a prin intermediul unei ret¸ele de interconectare. Pro- cesele care se execut˘a ˆın paralel pot s˘a ˆı¸si partajeze date pentru diferite scopuri, inclusiv pentru a-¸si sincroniza activitatea. Aceast˘a partajare a datelor pune programatorilor dou˘a probleme importante: sincronizarea accesului la date ¸si ment¸inerea consistent¸ei. Cˆateva caracteristici care le diferent¸iaz˘a de calculatoarele MIMD cu memorie distribuit˘a sunt:

• Comunicarea se face prin intermediul memoriei comune.

• ˆIntˆarzierea (“latency”) datorat˘a accesului la memorie poate fi mare ¸si variabil˘a.

• Coliziunile sunt posibile la accesarea memoriei.

ˆIntr-o arhitectur˘a MIMD cu memorie distribuit˘a unit˘at¸ile de procesare sunt conectate printr-o ret¸ea de interconectare. Fiecare unitate de procesare are propria memorie local˘a; dac˘a o anumit˘a dat˘a memorat˘a ˆın memoria unei unit˘at¸i de calcul este dorit˘a de o alta, atunci data trebuie s˘a fie trimis˘a explicit de la o unitate de procesare la cealalt˘a. Calculatoarele MIMD cu memorie distribuit˘a au cˆateva caracteristici de baz˘a care le diferent¸iaz˘a:

(23)

1.1. CLASIFIC ˘ARI ALE SISTEMELOR PARALELE 7

Figura 1.4: Arhitectura MIMD cu memorie partajat˘a (IS – flux de instruct¸iuni, DS – flux de date, CU – unitate de control, PU – procesor).

• Comunicarea se face prin soft, folosind instruct¸iuni de transmitere de date (“send/receive”).

• Mesajele de dimensiuni mari pot ascunde ˆıntˆarzirea(“latency”).

• Este necesar un management atent al comunicat¸iilor pentru a evita inter- bloc˘arile.

Principala proprietate a sistemelor cu memorie distribuit˘a, care le avantajeaz˘a fat¸˘a de cele cu memorie comun˘a, estescalabilitatea. Scalabilitatea refer˘a posibilitatea de a cre¸ste eficient¸a prin cre¸sterea num˘arului de procesoare. Deoarece nu exist˘a nici un element care ar putea duce la strangularea comunicat¸iilor, cum este accesul la memoria comun˘a, sistemele cu memorie distribuit˘a pot avea, cel put¸in ˆın principiu, un num˘ar nelimitat de procesoare.

Clasific˘ari mai detaliate ale acestor calculatoare sunt date de Hockeney [90] ¸si Bell [15]. Exemple de calculatoare care corespund categoriei MIMD sunt: Cray-2, Cay X-MP, HEp, IBM 370/168 MP, Univac 1100/80, Tndem/16, IBM 3081/3084, iPCS.

Sisteme Cluster. Ret¸elele de calculatoare au devenit ˆın ultimii ani o alternativ˘a foarte atractiv˘a pentru ˆınlocuirea costisitoarelor supercalculatoare. Ele s-au dovedit a fi utile chiar ¸si ˆın domenii ale calculului de ˆınalt˘a performant¸˘a (“High-Performance Computing”), unde performant¸a este crucial˘a. Sistemele de tip cluster reprezint˘a un exemplu de acest tip care a avut un deosebit succes ˆın ultimul timp. Acestea presupun interconectarea de stat¸ii de lucru de performant¸˘a ridicat˘a prin intermediul unor strategii clasice de interconectare (de exemplu: Ethernet sau Linux OS). În anumite cazuri, memoria acestor stat¸ii de lucru poate fi gestionat˘a ˆın a¸sa fel ˆıncât tehnici specifice arhitecturilor cu memorie partajat˘a s˘a poate fi folosite. Sistemele cluster sunt sisteme scalabile, pot fi adaptate ˆın funct¸ie de buget ¸si de nevoile de calcul ¸si permit execut¸ia eficient˘a atât a aplicat¸iilor secvent¸iale, cât ¸si a celor paralele. Câteva exemple de asemenea sisteme sunt: Berkeley NOW, HPVM, Beowulf, Solaris-MC.

Poate fi considerat˘a o nou˘a clas˘a, hibrid˘a, de sisteme paralele: SIMD-MIMD. Aceste sisteme numite ¸si SAMD (“Synchronous-Asynchronous Multiple Data”), sunt ˆın mod

(24)

Figura 1.5: Multicalculator bazat pe transmitere de mesaje (P – procesor, M – memorie).

esent¸ial calculatoare MIMD care au ˆın plus urm˘atoarele caracteristici:

• Permit asigurarea sincroniz˘arii proceselor.

• Sincronizarea proceselor poate fi ment¸inut˘a f˘ar˘a un consum mare de timp, prin faptul c˘a exist˘a un “ceas” uniform pentru toate procesoarele.

ˆIn timp s-a dezvoltat ¸si o a doua generat¸ie de abstractiz˘ari pentru aceste clase. Cˆateva dintre acestea sunt:

• Relaxarea sistemelor de calcul SIMD astfel ˆıncˆat sincronizarea s˘a nu mai apar˘a dup˘a fiecare pas-instruct¸iune, ci doar ocazional. Rezultatul este modul de lucru SPMD(“Single Program Multiple Data”), care se poate executa pe ma¸sini SIMD, dar poate fi folosit eficient ¸si pe alte arhitecturi.

• Modul de tratare a transmiterii mesajelor, al clasei MIMD cu memorie distribuit˘a, poate fi l˘argit pentru a se permite o dezvoltare mai simpl˘a a softului prin adau- garea de concepte cum ar fi: spat¸ii partajate asociative (“tuple spaces”) pentru comunicat¸ie, sau comunicat¸ie mapat˘a ˆın memorie astfel ˆıncˆat operat¸iile “send” ¸si

“receive” se aseam˘an˘a cu accesul la memorie(“put/get”).

1.1.2 Alte clasificari

Clasificarea lui Schwartz

Schwartz a introdus o clasificare a calculatoarelor paralele utilizate ˆın cercetare [151].

El utilizeaz˘a pentru aceasta not¸iunea de granulat¸ie prin care se ˆınt¸elege num˘arul de

(25)

1.1. CLASIFIC ˘ARI ALE SISTEMELOR PARALELE 9 procesoare din sistem. Conform acestei clasific˘ari, calculatoarele sunt cu granulat¸ie brut˘a (cele care cont¸in cˆateva zeci de procesoare), medie (sute de procesoare) ¸si cu granulat¸ie fin˘a (cu mii ¸si zeci de mii de procesoare).

Clasificarea lui Handler

Handler propune o notat¸ie elaborat˘a pentru exprimarea paralelismului calculatoarelor [83]. Clasificarea lui Handler compar˘a calculatoarele pe trei nivele distincte: unitatea de control a procesorului (PCU), unitatea aritmetic˘a (ALU) ¸si nivelul circuitului de bit (BLC). PCU corespunde procesorului sau CPU, ALU corespunde unei unit˘at¸i funct¸ionale sau unui element de procesare ˆıntr-un tablou de procesoare, iar BCL corespunde logicii necesare realiz˘arii operat¸iilor pe bit ˆın ALU.

Taxonomia lui Handler folose¸ste trei perechi de ˆıntregi pentru a descrie un calculator:

calculator = (k∗k⁰, d∗d⁰, w∗w⁰) unde:

k = num˘arul de PCU;

k⁰ = num˘arul de PCU care pot fi aranjate ˆın pipeline;

d= num˘arul de ALU controlate de fiecare PCU;

d⁰ = num˘arul de ALU care pot fi aranjate ˆın pipeline;

w= num˘arul de bit¸i ai cuvˆantului din ALU sau ai elementului de procesare (PE);

w⁰ = num˘arul de segmente pipeline din toate ALU sau dintr-un singur PE.

Urm˘atoarele reguli ¸si operatori sunt folosit¸i pentru a ar˘ata relat¸iile dintre diferitele elemente ale calculatorului:

- Operatorul ∗ este folosit pentru a indica faptul c˘a unit˘at¸ile sunt legate ˆın pipeline cu un singur flux de date ˆın toate unit˘at¸ile.

- Operatorul + poate fi folosit pentru a arata c˘a unit˘at¸ile nu sunt legate ˆın pipeline, ci lucreaz˘a independent pe fluxuri diferite de date.

- Operatorulv poate fi folosit pentru a indica faptul c˘a calculatorul poate lucra ˆın moduri diferite.

- Simbolul ∼indic˘a rangul valorilor pentru un parametru.

De exemplu, calculatorul Cray-1 este un calcultor cu un singur procesor pe 64 de bit¸i, care are 12 unit˘at¸i funct¸ionale, dintre care 8 pot fi ˆınl˘ant¸uite pentru a forma un pipeline.

Unit˘at¸ile funct¸ionale au ˆıntre 1 ¸si 14 segmente care pot fi deasemenea legate ˆın pipeline.

Descrierea lui Handler pentru acesta este:

Cray-1 = (1,12∗8,64∗(1∼14))

Descrierea lui Handler este foarte potrivit˘a descrierii procesoarelor de tip pipeline.

Este, de asemenea, bine adaptat˘a descrierii paralelismului pentru un singur procesor, dar nu tocmai potrivit˘a descrierii variet˘at¸ii de paralelism care poate apare ˆıntr-un calculator multiprocesor.

(26)

Figura 1.6: Clasificarea lui Hocney.

Clasificarea lui Hockney

Hockney propune o alt˘a clasificare foarte detaliat˘a a calculatoarelor atˆat seriale cˆat ¸si paralele [90]. Clasificarea este dat˘a ˆın form˘a ierarhic˘a, iar o variant˘a simplificat˘a este prezentat˘a ˆın Figura 1.6.

La nivelul cel mai ˆınalt se respect˘a clasificarea funct¸ional˘a a lui Flynn, ˆın sensul ˆımp˘art¸irii calculatoarelor ˆın cele cu un singur flux de instruct¸iuni (SI) ¸si cele cu mai

multe fluxuri de instruct¸iuni (MI).

Este demn de remarcat faptul c˘a aceast˘a clasificare evident¸iaz˘a procesarea pipeline atˆat ˆın cazul fluxului unic de instruct¸iuni, cˆat ¸si ˆın cazul fluxurilor multiple de instruct¸iuni.

Clasificarea lui Bell

O alt˘a clasificare, numai a sistemelor MIMD, cunoscut˘a ca ¸si taxonomia lui Bell, a fost propus˘a de Gordon Bell ˆın 1992. Acesta a considerat multiprocesoarele cu memorie partajat˘a ca avˆand un spat¸iu unic de adresare. Multiprocesoarele scalabile trebuie s˘a utilizeze o memorie distribuit˘a. Mutiprocesoarele nescalabile utilizeaz˘a memorie partajat˘a.

• Multiprocesoare(spat¸iu unic de adrese) – cu memorie distribuit˘a (scalabil) – cu memorie comun˘a (nescalabil)

(27)

1.2. CRITERII DE PERFORMANT¸ ˘A ALE SISTEMELOR PARALELE 11

• Multicalculatoare(mai multe spat¸ii de adrese, transfer de mesaje) – distribuite (scalabil)

– centralizate Clasificarea lui Lewis

Ted Lewis[108] propune ca ˆın clasificarea sistemelor de calcul s˘a se plece de la cele dou˘a modele fundamentale de paralelism, cel generat defluxul controlului, iar al doilea generat deparalelismul de date(“data-parallelism”). Primul tip de paralelism se refer˘a la construirea unui program paralel din mai multe procese ce se pot executa simultan. ˆIn acest caz, exist˘a gradul cel mai mare de generalitate, dar nu se pot obt¸ine niveluri foarte ridicate de paralelism. Sistemele de calcul sunt de tipul MIMD. Al doilea tip presupune execut¸ia acelora¸si operat¸ii simultan, dar cu date diferite. De data aceasta, se poate obt¸ine un nivel foarte ridicat de paralelism, dar numai la algoritmii care folosesc operat¸ii cu vectori sau matrice. Sistemele de calcul paralel corespunz˘atoare sunt SIMD sau SPMD.

ˆIn ceea ce prive¸ste analiza proiect˘arii algoritmilor paraleli clasificarea cea mai util˘a ar fi aceea ˆın care se iau ˆın considerare dou˘a clase mari de arhitecturi paralele:

i Multiprocesoare cu memorie partajat˘a.

ii Multicalculatoare cu memorie distribuit˘a.

Aceasta pentru c˘a un algoritm paralel poate fi v˘azut ca ¸si o mult¸ime de componente de calcul (“task”-uri) independente, care se pot executa concurent ¸si ˆın mod cooperativ pentru rezolvarea unei probleme. La proiectarea unui asemenea algoritm ne intereseaz˘a s˘a

¸stim c˘a avem unit˘at¸i de procesare independente ¸si modul ˆın care acestea pot interact¸iona:

fie prin intermediul unei memorii comune, fie prin intermediul unei ret¸ele de interconectare.

În general, componentele care constituie programul paralel trebuie s˘a coopereze ˆıntr- un anumit mod pentru a rezolva o problem˘a. De asemenea, foarte des poate apare necesitatea ca anumite sarcini s˘a se execute doar dup˘a ce s-a ajuns la o anumit˘a stare, sau anumite operat¸ii au fost executate. Prin urmare, posibilitatea sincroniz˘arii proceselor este esent¸ial˘a. În funct¸ie de clasa de arhitectur˘a paralel˘a - cu memorie partajat˘a sau distribuit˘a - sincronizarea poate fi obt¸inut˘a prin diferite metode specifice. Pe lâng˘a ˆınc˘arcarea echilibrat˘a a componentelor, posibilitatea de a implementa mecanisme eficiente

de sincronizare poate conduce la obt¸inerea de programe paralele eficiente.

1.2 Criterii de performant ¸˘ a ale sistemelor paralele

Posibilit˘at¸ile hardware ale unui sistem paralel pot fi evaluate pe baza unor criterii bine precizate; cˆateva dintre acestea sunt prezentate pe scurt ˆın continuare:

(28)

• Viteza de calcul maxim˘a, m˘asurat˘a ˆın Mflop/s (Million FLoting point OPeration per Second), sau ˆın MIPS (Million Instructions Per Second). În descrierea vitezelor de calcul, se folosesc ˆın general dou˘a valori: una de vârf, care presupune c˘a procesoarele lucreaz˘a la ˆınc˘arcare maxim˘a (ignorând conflictele de access la memorie, comunicat¸ie, sincroniz˘ari, timpi mort¸i) ¸si cealalt˘a, evaluat˘a cu programe speciale de test (“benchmark”), care rezolv˘a probleme des ˆıntâlnite ˆın calcule ¸stiint¸ifice.

• Num˘arul de procesoare. Se proiecteaz˘a variante arhitecturale cu num˘ar de procesoare de la cˆateva zeci, la cˆateva mii. Este indicat ca aceste sisteme s˘a fie scalabile, adic˘a s˘a poat˘a fi ad˘augate noi procesoare, u¸sor, f˘ar˘a necesitatea unor modific˘ari laborioase.

• Dimensiunea memoriei locale a unui procesor sau a memoriei globale, dac˘a exist˘a.

Acesta este un parametru de mare important¸˘a, deoarece dicteaz˘a dimensiunea problemelor care pot fi rezolvate.

• Frecvent¸a ceasului unui procesor, care d˘a informat¸ii despre puterea unui nod de procesare.

• Viteza de comunicat¸ie ¸si caracteristici ale bandei de trecere a unei leg˘aturi, m˘asurat˘a ˆın num˘ar de octet¸i transferat¸i pe secund˘a. Este esent¸ial˘a pentru sistemele cu memorie distribuit˘a. Ca ¸si la viteza de calcul, trebuie s˘a se fac˘a diferent¸e ˆıntre viteza de vˆarf ¸si cea atins˘a efectiv ˆın aplicat¸ii reale.

• Viteza de acces la memorie a fiec˘arui procesor, esent¸ial˘a pentru calculatoarele cu memorie comun˘a.

• Viteza de comunicat¸ie cu exteriorul, care poate produce un efect de strangulare a vitezei efective de calcul, prin introducerea unor timpi mort¸i, datorit˘a nealiment˘arii cu programe ¸si date.

• Suportul sofware oferit odat˘a cu calculatorul. ˆIn ultimii ani se constat˘a un efort in- tens de standardizare, materializat prin aparit¸ia de biblioteci implementate eficient pe diferite clase de arhitecturi. Aceasta conduce la portabilitatea programelor.

• Raportul dintre costul calculatorului ¸si viteza sa de calcul – pret¸ul unui Mflop/s.

Tendint¸a actual˘a este de ment¸ine cˆat mai sc˘azut acest raport, chiar dac˘a nu se obt¸ine o vitez˘a de calcul deosebit de ridicat˘a. Este ¸si motivul pentru care sistemele cluster s-au impus atˆat de mult ˆın ultima vreme ˆın detrimentul costisitoarelor supercalculatoare.

1.3 Ret ¸ele de interconectare a procesoarelor

Performant¸ele unei arhitecturi paralele cu memorie distribuit˘a depind mult de num˘arul de procesoare dar ¸si de modul ˆın care acestea sunt interconectate.

Ret¸elele de interconectare se pot clasifica ˆın trei categorii:

• Fiecare procesor este conectat direct cu oricare altul. Aceast˘a construct¸ie este practic inexistent˘a, exceptˆand ma¸sinile cu num˘ar mic de procesoare.

(29)

1.3. RET¸ ELE DE INTERCONECTARE A PROCESOARELOR 13

Figura 1.7: (a) – Ret¸eaua liniar˘a(lant¸); (b) – ret¸eaua ciclic˘a(inel).

• Fiecare procesor este conectat cu oricare altul prin intermediul unei punt¸i de leg˘a- tur˘a numit˘a “switchboard”. Aceast˘a conectare asigur˘a leg˘atura ˆıntre oricare dou˘a procesoare dup˘a un num˘ar mic de pa¸si. Se pot utiliza ˆın plus conexiuni directe ˆıntre procesoare ˆınvecinate.

• Fiecare procesor este conectat direct cu un num˘ar de alte procesoare.

ˆIn continuare, vom prezenta cˆateva ret¸ele de interconectare din cea de-a treia categorie, care sunt mai des folosite ˆın practic˘a.

ˆInainte de a le prezenta, s˘a vedem care sunt propriet˘at¸ile unei astfel de topologii.

În primul rând graful asociat trebuie sa fieconex(exist˘a cel put¸in un drum ˆıntre oricare dou˘a noduri ale sale) ¸si pe cât posibilregulat(gradele tututor nodurilor s˘a fie egale). Este indicat ca un procesor s˘a nu aib˘a prea multe canale de comunicat¸ie, pentru a fi u¸sor de realizat; strâns legat˘a de aceasta este cerint¸a ca num˘arul de arce s˘a fie relativ mic. Prin urmare se urm˘are¸ste cagradul grafului–g (maximul gradelor tuturor nodurilor) s˘a fie cât mai mic. Pe de alt˘a parte, este bine ca diametrul – d (maximul tuturor distant¸elor ˆıntre perechi de noduri din graf) s˘a fie cât mai mic, astfel ˆıncât distant¸ele ˆıntre procesoare s˘a fie limitate ¸si deci comunicarea cât mai facil˘a. Evident cele dou˘a deziderate sunt antagonice;

cu cˆat gradul este mai mic, cu atˆat sunt mai put¸ine muchii ¸si deci scad ¸sansele s˘a existe drumuri scurte ˆıntre oricare dou˘a procesoare.

1.3.1 Topologii de baz˘ a

Ret¸ea liniar˘a ¸si ciclic˘a

ˆIntr-o ret¸ea liniar˘a (lant¸), un procesor P_i este conectat cu vecinii s˘ai P_i−1 ¸si P_i+1 pentru tot¸i i: 1< i < n(Figura 1.7 (a)). Gradul este 2, iar diametrul este n−1.

Ret¸eaua ciclic˘a (inel) aduce un plus de flexibilitate prin stabilirea unei conexiuni ¸si ˆıntre primul ¸si ultimul procesor (Figura 1.7 (b)). Diametrul se reduce la jum˘atate –

dn/2e, iar gradul r˘amˆane egal cu 2.

(30)

Figura 1.8: Ret¸eaua arbore binar pentrun = 15.

Figura 1.9: (a) Ret¸eaua gril˘a cu M = 4 ¸si N = 6. (b) Ret¸eaua tor cu M = 4 ¸si N = 6.

Ret¸ea arbore binar

Numero¸si algoritmi pot fi implementat¸i convenabil pe calculatoare paralele ale c˘aror procesoare sunt conectate ˆın structur˘a de arbore binar. Acest tip de ret¸ea este foarte convenabil datorit˘a diametrului mic, care estedlog₂ne (n=num˘arul de procesoare); gradul este egal cu 3.

Ret¸ea gril˘a

Se pot obt¸ine noi ret¸ele de interconectare prin considerarea produsului cartezian a altor ret¸ele. De exemplu, o ret¸ea gril˘a(latice) M×N, M, N >0 este produsul cartezian a dou˘a ret¸ele lant¸de lungime M ¸si N (Figura 1.9 (a)). Diametrul acest¸ei ret¸ele esteM+N−2, iar gradul este 4.

O ret¸ea tor sau toroid este produsul cartezian a dou˘a ret¸ele inel (Figura 1.9 (b)).

Diametrul scade ˆın acest caz ¸si este dM/2e+dN/2e.

Ret¸ea fluture

O ret¸ea fluture de ordin k are (k+ 1)2^k procesoare dispuse ˆın nodurile unui graf ¸si are urm˘atoarele propriet˘at¸i:

- exist˘a 2^k coloane fiecare cu cˆate k+ 1 noduri;

(31)

Figura 1.10: Ret¸eaua fluture pentru k = 3.

- procesoarele de pe fiecare coloan˘a sunt numerotate de la 0 la k, iar acest num˘ar reprezint˘a rangul acelui nod;

- procesorul de rang r de pe coloanaj se noteaz˘a cu d_r,j;

- procesorul d_r,j este conectat cu procesoarele d_r−1,j ¸si d_r−1,j⁰, unde j⁰ este num˘arul al c˘arei reprezent˘ari binare pe k bit¸i este aceea¸si ca ¸si reprezentarea binar˘a a luij cu except¸ia bituluir−1.

ˆIn anumite cazuri, procesoarele de rang 0 ¸si k coincid, caz ˆın care toate procesoarele sunt conectate cu exact alte 4 procesoare.

Diametrul este egal cu k.

Ret¸eaua fluture de rang k are dou˘a propriet˘at¸i remarcabile:

1. Dac˘a procesoarele de rang k se ¸sterg, ˆımpreun˘a cu toate arcele incidente, rezult˘a dou˘a ret¸ele fluture de rangk−1.

2. Dac˘a procesoarele de rang 0 se ¸sterg, ˆımpreun˘a cu toate arcele incidente, rezult˘a dou˘a ret¸ele fluture interclasate de rang k−1.

Ret¸ea hipercub

Un hipercub binarH_n de dimensiune n are 2ⁿ noduri ¸si se obt¸ine din produsul cartezian an lant¸uri de lungime 2. Nodurile sunt etichetate prin numere reprezentate binar prinn cifre binare, iar dou˘a noduri sunt conectate dac˘a ¸si numai dac˘a numerele corespunz˘atoare lor difer˘a doar ˆıntr-o singur˘a pozit¸ie binar˘a. Prin urmare, fiecare nod are exactn vecini

¸si diametrul este n. Dac˘a se ˆınlocuie¸ste 2 cu un num˘ar k oarecare se obt¸in n-cuburi cu aritatek.

O alt˘a modalitate de definire a unui hipercub binar este recursiv˘a. H_n este obt¸inut din dou˘a hipercuburi Hn−1 prin unirea corespunz˘atoare a nodurilor: fiec˘arui num˘ar care reprezint˘a un nod i se adaug˘a un nou bit pe pozit¸ia cea mai semnificativ˘a (egal cu 0 pentru primul hipercub ¸si egal cu 1 pentru cel de-al doilea) ¸si apoi se unesc nodurile care difer˘a ˆın cel mult o pozit¸ie binar˘a. HipercubulH1 este format din dou˘a procesoare unite.

(32)

Figura 1.11: Ret¸eaua hipercub. (a) Ret¸eaua hipercub pentrun= 3.(b) Ret¸eaua hipercub pentru n= 4 (se formeaz˘a prin combinarea a dou˘a hipercuburi de dimensiune 3).

Definit¸ia 1.1 (Distant¸a Hamming) Fie a ¸si b dou˘a secvent¸e de bit¸i de aceea¸si lungime. Distant¸a Hamming dintre aceste secvent¸e este num˘arul de pozit¸ii din cele dou˘a secvent¸e ˆın care exist˘a valori diferite.

Evident distant¸a dintre dou˘a noduri ale unui hipercub este egal˘a cu distant¸a Hamming dintre reprezent˘arile binare ale indec¸silor celor dou˘a noduri. Diametrul pentru ret¸eaua H_n este n, egal˘a cu gradul.

Un hipercub de dimensiune n este echivalent cu o ret¸ea fluture ale c˘arei coloane sunt unite ˆıntr-un singur vˆarf ¸si care va avea jum˘atate din num˘arul de muchii ale ret¸elei fluture.

Ret¸ea amestecare perfect˘a

Acest tip de ret¸ea este unul special, inspirat de amestecarea perfect˘a a c˘art¸ilor de joc dintr-un pachet. Structura acestei ret¸ele este exploatat˘a de mult¸i algoritmi paraleli dintre care cel mai cunoscut este cel de sortare bitonic˘a (Sect¸iunea 4.14.1).

Se consider˘a n= 2^m c˘art¸i de joc ˆımp˘art¸ite ˆın mod egal ˆın dou˘a pachete. Se amestec˘a aceste c˘art¸i astfel ˆıncˆat prima carte din pachetul al doilea se afl˘a ˆıntre prima ¸si a doua carte din primul pachet, a doua carte din al doilea pachet ˆıntre a doua ¸si a treia carte din primul ¸s.a.m.d. Acest procedeu de amestecare este numit amestecare perfect˘a.

Amestecarea se bazeaz˘a pe o permutare π:

0 1 2 3 4. . . n−2 n−1

0 n/2 1 n/2 + 1 2. . . n/2−1 n−1

Permutarea invers˘aπ⁻¹ are urm˘atoarea proprietate:

π⁻¹(x) = 2x%(n−1), x= 0, . . . , n−2 π⁻¹(n−1) = n−1.

Conectarea este definit˘a ˆın urm˘atorul mod:

(33)

Figura 1.12: Ret¸eaua amestecare perfect˘a pentru n= 8.

• procesorulx este conectat cu procesorul π⁻¹(x), dac˘ax= 0,1, . . . , n−1,

• procesorul 2x este conectat cu procesorul 2x+ 1,

• procesorul 2x+ 1 este conectat cu procesorul 2x,

Acestui procedeu de amestecare i se poate asocia o topologie de interconectare a procesoarelor.

O ret¸ea amestecare perfect˘a pentru n = 8 este prezentat˘a ˆın Figura 1.12.

1.3.2 Problema includerii

Mult¸i algoritmi folosesc o topologie virtual˘a ˆın care comunicat¸ia se desf˘a¸soar˘a doar ˆıntre vecinii grafului. Performant¸a obt¸inut˘a poate fi ˆımbun˘at˘at¸it˘a considerabil dac˘a topologia virtual˘a a algoritmului corespunde cu topologia fizic˘a, real˘a, a sistemului paralel.

Totu¸si, ˆın proiectarea algoritmilor este indicat˘a o distant¸are fat¸˘a de arhitectur˘a (chiar independent¸˘a), pentru a nu fi necesar˘a rescrierea programului pentru fiecare implementare pe un alt sistem. O modalitate de obt¸inere a portabilit˘at¸ii se bazeaz˘a pe g˘asirea unor modalit˘at¸i de includere a unei topologii (cea a algoritmului) ˆın altele, astfel ˆıncˆat, un algoritm s˘a poat˘a fi implementat pe diferite arhitecturi.

Problema este interesant˘a ¸si din alte motive, cum este de exemplu, posibilitatea emul˘arii unei arhitecturi prin alta ¸si determinarea efectului cerut de aceast˘a emulare.

Aceast˘a problem˘a a includerii se bazeaz˘a pe o problem˘a matematic˘a, a¸sa numita scufundare a grafurilor [122].

Definit¸ia 1.2 (Scufundarea grafurilor) Fie G ¸si H dou˘a grafuri simple neorientate.

Oscufundarea grafuluiGˆın grafulH este definit˘a printr-o funct¸ief definit˘a pe mult¸imea nodurilor din G cu valori ˆın mult¸imea nodurilor din H, ¸si o funct¸ie Sf definit˘a pe mult¸imea muchiilor din G cu valori ˆın mult¸imea lant¸urilor din H; prin S_f se asociaz˘a unei muchii (x, y) din G o cale din H care une¸ste f(x) cu f(y).

ˆIn general, se consider˘a doar funct¸ia f, l˘asˆand funct¸ia S_f s˘a fie dedus˘a prin considerarea unui drum minim ˆıntre f(x) ¸si f(y) corespunz˘ator muchiei (x, y).

(34)

Figura 1.13: (a)Ciclu hamiltonian ˆıntr-o gril˘a 4×5; (b) scufundarea unui inel ˆıntr-o gril˘a 5×5 cu dilatare 2 (muchia diagonal˘a se mapeaz˘a printr-un lant¸ cu lungimea 2); (c) ciclu hamiltonian ˆıntr-un tor 5×5.

Dilatarea ¸si congestia sunt dou˘a caracteristici importante ale unei scufund˘ari. Dila- tarea exprim˘a lungimea maxim˘a a unei c˘ai S_f(x, y), unde (x, y) este muchie ˆın G; iar congestia este maximul dup˘a toate muchiile e ∈E(H), a num˘arului de c˘ai S_f(x, y) care sunt imagini de muchii din G care cont¸in muchia e din H.

Putem considera H ca fiind arhitectura real˘a, iarG topologia emulat˘a (fie c˘a ea pro- vine dintr-un algoritm, sau este topologia altei arhitecturi). Dilatarea exprim˘a distant¸a maxim˘a ˆıntre dou˘a noduri emulate; este de dorit s˘a fie cât mai mic˘a, valoarea ideal˘a fiind 1. Congestia d˘a informat¸ii despre num˘arul de canale emulate pe un canal de comunicat¸ie fizic˘a; cu cât este mai mic cu atât conflictele de utilizare a canalului sunt reduse. Dac˘a dilatarea este egal˘a cu 1, atunci ¸si congestia este egal˘a cu 1.

Exemplul 1.1 (Scufundarea unui inel)Dorim s˘a analiz˘am modalit˘at¸ile de scufundare cu dilatare 1, a unui inel ˆın topologiile: gril˘a, tor ¸si hipercub. Problema se reduce la g˘asirea unui drum hamiltonian (care trece prin toate nodurile grafului) ˆın grafurile topologiilor respective. Vom prezenta doar rezultatele, f˘ar˘a a intra ˆın detalii ce t¸in de demonstrare.

O gril˘a de dimeniuniM×N are ciclu hamiltonian dac˘a ori M ori N este par – Figura 1.13 (a). Dac˘a ambele dimensiuni sunt impare atunci scufundarea unui inel se poate face doar cu o dilatare egal˘a cu 2. Un exemplu este dat ˆın Figura1.13 (b), unde se observ˘a c˘a linia oblic˘a nu corepunde unei muchii a grilei ¸si deci este nevoie de un drum de lungime 2 pentru acea leg˘atur˘a.

Un tor are ˆıntotdeanuna ciclu hamiltonian; dac˘a M sau N este par, atunci se aplic˘a rezultatul precedent, iar dac˘a ambele dimensiuni sunt impare se folosesc muchiile pe care torul le are ˆın plus fat¸˘a de de gril˘a – Figura 1.13 (c).

S¸i un hipercub are ˆıntotdeauna un ciclu hamiltonian – Figura 1.14. Pentru un hipercub H_2n exist˘a n cicluri hamiltoniene distincte.

(35)

Figura 1.14: Dou˘a cicluri hamiltoniene ale hipercubului de ordin 3; liniile punctate indic˘a muchiile din hipercub neutilizate.

Figura 1.15: Scufundarea unei grile 4×4 ˆıntr-un hipercub de ordin 4; un tor este chiar hipercubul.

Exemplul 1.2 (Scufundarea unei grile ˆıntr-un hipercub) O gril˘a de dimensiuni 2^n/2×2^n/2 poate fi scufundat˘a cu dilatare 1 ˆıntr-un hipercub de ordin n (cu n par). Mai general, orice gril˘a de dimensiuni 2ⁿ¹×2ⁿ², cun₁+n₂ =npoate fi scufundat˘a cu dilatare 1 ˆıntr-un hipercub Hn [167]. Un exemplu este prezentat ˆın Figura 1.15.

1.3.3 Comunicat ¸ia ˆın ret ¸ele

Principalele criterii de performant¸˘a de care se t¸ine cont ˆın proiectarea unei ret¸ele de interconectare sunt asociate cu parametrii urm˘atori:

- ˆıntârzierea (“latency”) - timpul de transmitere pentru un singur mesaj, m˘asurat de la momentul trimiterii sale pân˘a la primirea la destinat¸ie (este indicat s˘a fie cât mai mic);

- l˘argimea de band˘a (“bandwidth”) - num˘arul de octet¸i transferat¸i de ret¸ea ˆın unitatea de timp (este indicat s˘a fie cˆat mai mare);

- diametrul (“diameter”) - distant¸a maxim˘a ˆıntre oricare dou˘a procesoare din ret¸ea (este indicat s˘a fie cˆat mai mic); distant¸a dintre dou˘a procesoare se define¸ste ca fiind lungimea drumului minim dintre ele;

(36)

- m˘arimea bisect¸iei (“bisection width”) - num˘arul minim de canale de comunicat¸ie, ce trebuie eliminate pentru a ˆımp˘art¸i ret¸eaua ˆın dou˘a jum˘at˘at¸i egale (este indicat s˘a fie cˆat mai mic˘a);

- conectivitatea (“connectivity”) - num˘arul de vecini direct¸i ai fiec˘arui procesor, parametru cunoscut ca ¸si gradul procesorului;

- costul hardware - proport¸ia din costul total care reprezint˘a costul ret¸elei;

- fiabilitatea - se asigur˘a prin introducerea unor c˘ai redundante, etc.;

- funct¸ionalitatea - posibilitatea asigur˘arii unor funct¸ii suplimentare de c˘atre ret¸ea, cum ar fi combinarea mesajelor ¸si arbitrarea.

Este imposibil de satisf˘acut toate aceste criterii de performant¸˘a, unele chiar contra- dictorii. De aceea, trebuie s˘a se decid˘a care sunt obiectivele de performant¸˘a ce trebuie atinse. De exemplu, nu este posibil ˆıntotdeauna ca fiecare procesor s˘a fie conectat direct cu toate celelalte procesoare (cazul ideal), decât ˆın cazul unei configurat¸ii reduse, cu pân˘a la câteva zeci de procesoare. Un procesor este conectat direct doar cu o submult¸ime de procesoare, care formeaz˘a vecin˘atatea sa. În consecint¸˘a, pentru ca un mesaj trimis de oricare dintre procesoare s˘a ajung˘a la destinat¸ie, trebuie s˘a existe un mecanism de propagare a mesajului la nivelul fiec˘arui procesor. Acesta trebuie s˘a decid˘a care este canalul pe care se transmite ˆın continuare mesajul primit, astfel ca acesta s˘a ajung˘a ˆın mod sigur la destinat¸ie ¸si ˆıntr-un timp rezonabil. Funct¸ia de propagare a mesajelor prin ret¸eaua de comunicat¸ie poart˘a numele de dirijare (rutare - “routing”). În leg˘atur˘a cu dirijarea mesajelor prin ret¸ea va trebui s˘a se asigure respectarea urm˘atoarelor cerint¸e:

- nici un mesaj nu trebuie s˘a fie pierdut;

- strategia de rutare trebuie s˘a evite producerea fenomenului de interblocare;

- toate mesajele trebuie s˘a-¸si ating˘a destinat¸ia ˆıntr-un interval de timp finit;

- strategia de dirijare trebuie s˘a fie independent˘a de topologia ¸si de m˘arimea ret¸elei.

Transmiterea de mesaje ˆıntre dou˘a procesoare poate fi sincron˘a sau asincron˘a.

ˆIn cazul transmiterii asincrone de mesaje, procesul care comunic˘a informat¸ie continu˘a execut¸ia dup˘a ce aceasta a fost transmis˘a spre destinat¸ie. Procesul receptor va prelua mesaje ˆıntr-o coad˘a de mesaje. Mesaje pot fi primite ˆıntr-o ordine diferit˘a de cea ˆın care au fost trimise, existˆand ¸si posibilitatea trimiterii lor cu prioritate.

Transmisia sincron˘a cere ca atât procesul care trimite cât ¸si cel care recept¸ioneaz˘a mesajul s˘a fie disponibile pân˘a ˆın momentul când transmisia s-a terminat, ambele procese putând apoi s˘a-¸si continue lucrul. În felul acesta, nu este necesar˘a stocarea mesajelor (lucru care poate fi necesar ˆın cazul transmiterii asincrone).

1.4 Niveluri la care poate apare paralelism

În calculatoarele moderne, paralelismul apare pe diferite niveluri atât ˆın hardware cât

¸si ˆın software: niveluri semnal ¸si circuit, componente ¸si sistem. La cel mai sc˘azut nivel,

(37)

1.4. NIVELURI LA CARE POATE APARE PARALELISM 21

Figura 1.16: Niveluri ale paralelismului.

semnalele sunt transmise ˆın paralel, iar la un nivel un pic mai ˆınalt poate apare a¸sa numitul paralelism la nivel de instruct¸iune. De exemplu, un procesor cum este Pentium Pro are capabilitatea de a procesa trei instruct¸iuni simultan. Majoritatea calculatoarelor su- prapun activit˘at¸ile unit˘at¸ii de control ¸si cele de intrare-ie¸sire (I/O). Anumite calculatoare folosesc tehnica de ˆıntret¸esere a memoriei – cˆateva blocuri de memorie pot fi accesate ˆın paralel pentru accesul mai rapid la memorie. La un nivel ¸si mai ˆınalt, sistemele de calcul pot avea mai multe procesoare, iar la un nivel ¸si mai ˆınalt se pot conecta ˆımpreun˘a mai multe calculatoare care pot lucra ˆımpreun˘a ca o singur˘a ma¸sin˘a.

La primele dou˘a niveluri – semnal ¸si circuit – paralelismul se realizeaz˘a prin tehnici hardware ¸si are loc a¸sa numitul paralelism hardware. Paralelismul celorlalte dou˘a niveluri – componente ¸si sistem – este ˆın general exprimat implicit sau explicit prin diferite tehnici software care formeaz˘a paralelismul software.

Nivelurile de paralelism pot fi structurate ¸si ˆın funct¸ie de dimensiunea componentelor de cod (“grain size”) care se pot executa ˆın paralel. ˆIn funct¸ie de acestea avem urm˘atoarele nivele:

• granularitate foarte fin˘a (instruct¸iuni multiple) – paralelizarea este realizat˘a de procesor;

• granularitate fin˘a (nivel de date)– paralelizarea este realizat˘a de compilator;

• granularitate medie (nivel al controlului) – paralelizarea este realizat˘a de programator;

(38)

• granularitate brut˘a (nivel-task) – paralelizarea este realizat˘a de programator.

Diferitele niveluri de paralelism sunt evident¸iate ˆın Figura 1.16. Primele dou˘a niveluri sunt suportate fie de c˘atre hardware, fie de c˘atre compilatoare de paralelizare.

Programatorul se ocup˘a ˆın general de ultimele dou˘a niveluri de paralelism.

1.5 Clasificarea algoritmilor paraleli

A¸sa cum am precizat ¸si anterior, un algoritm paralel poate fi v˘azut ca ¸si o mult¸ime de p componente de calcul/taskuri independente, care se pot executa concurent ¸si ˆın mod cooperativ la rezolvarea unei probleme. ˆIn mod evident, dac˘a p = 1 atunci avem un algoritm secvent¸ial.

În timpul execut¸iei unui algoritm paralel componentele interact¸ioneaz˘a prin sincronizare ¸si/sau schimb de date. Aceste puncte sunt numite puncte de interact¸iune. O component˘a poate fi ˆımp˘art¸it˘a ˆın funct¸ie de aceste puncte de interact¸iune ˆıntr-un anumit num˘ar de etape, astfel ˆıncât la sfâr¸situl unei etape o component˘a poate comunica cu alte componente ˆınainte de ˆınceperea etapei urm˘atoare. În execut¸ia unui program paralel, timpul asociat unei etape pentru un procesor oarecare este o variabil˘a aleatoare, datorit˘a urm˘atorilor factori:

- procesoarele pot avea viteze ¸si caracteristici diferite;

- operat¸iile efectuate de c˘atre un procesor pot fi ˆıntrerupte de c˘atre sistemul de operare;

- timpul de procesare poate depinde de datele de intrare.

Ca rezultat al necesit˘at¸ii interact¸iuniilor dintre componente, o component˘a poate fi blocat˘a pentru o anumit˘a perioad˘a de timp. Un algoritm paralel ˆın care componentele trebuie s˘a a¸stepte execut¸ia unor anumite evenimente care apar ˆın alte procese se nume¸ste algoritm sincron. Într-un algoritm sincronizat componenta ce ajunge la un punct de interact¸iune este blocat˘a pân˘a când componentele cu care trebuie s˘a interact¸ioneze ajung

¸si ele la acel punct de interact¸iune. Aceast˘a form˘a de sincronizare se nume¸ste explicit˘a.

Deoarece execut¸ia unei componente este variabil˘a, toate componentele care trebuie s˘a fie sincronizate la un anumit punct trebuie s˘a a¸stepte terminarea celui cu execut¸ia cea mai lung˘a. Aceasta reprezint˘a o limitare important˘a a algoritmilor paraleli sincroni ¸si poate duce la o utilizare ineficient˘a a procesoarelor.

Algoritmii paraleli asincroni elimin˘a problemele implicate de sincronicitate. Compo- nentele algoritmilor asincroni nu trebuie ˆın general s˘a se a¸stepte unele pe altele. Comu- nicarea se realizeaz˘a prin citirea unor variabile globale actualizate ˆın mod dinamic. Pot apare ˆıntˆarzieri ¸si ˆın acest caz, datorit˘a rezolv˘arii conflictelor ce pot apare ˆın accesarea memoriei comune. Acest tip de sincronizare se nume¸ste implicit. Pot apare ˆıns˘a probleme legate de consistent¸˘a ¸si corectitudine ¸si pentru eliminarea lor sunt programate a¸sa numitelesect¸iuni critice, iar procesele pot fi blocate ˆınainte de intrarea ˆın aceste sect¸iuni.

Algoritmii paraleli pot fi clasificat¸i ¸si ˆın funct¸ie de controlul concurent¸ei, de granularitate, scalabilitate ¸si de structura comunicat¸iei impuse de ei.