1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE

• 1.1 MASINI PARALELE SI MODELE DE PROGRAMARE

• 1.2 CLASIFICAREA CALCULATOARELOR PARALELE

• 1.3 TIPURI DE CALCULATOARE PARALELE

• 1.4 PERFORMANŢE ALE CALCULATOARELOR PARALELE

• 1.5 PROGRAME PARALELE

1.1 MASINI PARALELE SI MODELE DE PROGRAMARE

Calculator paralel = colectie de elemente de prelucrare care comunica si coopereaza pentru rezolvarea rapida a unor probleme complexe.

Comunicatie si cooperare: esentiale intr-o arhitectura paralela!=> arhitectura comunicatiei

Cadrul de organizare intr-o masina paralela:

O arhitectura paralela generala:

 Exemplu de aplicatie paralela: calcularea sumei

Solutia generala: n/p taskuri p procesoare (procese).

Se disting doua seturi de date:-partajate: valorile A[i] si suma finala;-private: evalurile individuale de functii si sumele partiale

1

0])[(

n

iiAf

1) Modelul 1 de programare: spatiu partajat de adrese.

Programul = colectie de fire de executie, fiecare avand un set de variabile private, iar impreuna partajeaza un alt set de variabile.

Comunicatia dintre firele de executie: prin citirea/scrierea variabilelor partajate.

Coordonarea firelor de executie prin operatii de sincronizare: indicatori (flags), zavoare (locks), semafoare.

Masina paralela corespunzatoare modelului 1: masina cu memorie partajata (sistemele multiprocesor, in primul rand sistemele multiprocesor simetrice sau SMP-Symmetric Multiprocessors).

Exemple: sisteme de la Sun, DEC, Intel (Millennium), SGI Origin.

Variante ale acestui model:

a) masina cu memorie partajata distribuita (logic partajata, dar fizic distribuita. Exemplu: SGI Origin (scalabila la cateva sute de procesoare).

b) masina cu spatiu partajat de adrese (memoriile cache inlocuite cu memorii locale). Exemplu: Cray T3E.

O posibila solutie pentru rezolvarea problemei:

Este necesara sincronizarea threadurilor pentru accesul la variabilele partajate !

Exemplu: prin excludere mutuala, folosind operatia de zavorare (lock):

2) Modelul 2 de programare: transfer de mesaje.

Programul = colectie de procese, fiecare cu thread de control si spatiu local de adrese, variabile locale, variabile statice, blocuri comune.

Comunicatia dintre procese: prin transfer explicit de date (perechi de operatii corespunzatoare send si receive la procesele sursa si respectiv destinatie). Datele partajate din punct de vedere logic sunt partitionate intre toate procesele.

=> asemanare cu programarea distribuita! 

Exista biblioteci standard (exemplu: MPI si PVM).

Masina corespunzatoare modelului 2 este multicalculatorul (sistem cu memorie distribuita):

Exemple: Cray T3E (poate fi incadrat si in aceasta categorie), IBM SP2, NOW, Millenium.

O posibila solutie a problemei in cadrul modelului in transfer de mesaje (simplificand, se calculeaza suma s = f(A[1]) + f(A[2]) ):

sau:

Procesor 1 Procesor 2xlocal = f(A[1]) xlocal = f(A[2])send xlocal, proc2 send xlocal, proc1receive xremote, proc2 receive xremote, proc1s = xlocal + xremote s = xlocal + xremote

Procesor 1 Procesor 2xlocal = f(A[1]) xlocal = f(A[2])send xlocal, proc2 receive xremote, proc1receive xremote, proc2 send xlocal, proc1s = xlocal + xremote s = xlocal + xremote

3) Modelul 3 de programare: paralelism al datelor.

Thread singular secvential de control controleaza un set de operatii paralele aplicate intregii structuri de date, sau numai unui singur subset.

Comunicatia: implicita, in modul de deplasare a datelor.

Eficienta numai pentru anumite probleme (exemplu: prelucrari de tablouri)!

Masina corespunzatoare modelului 3: sistem SIMD - Single Instruction Multiple Data (numar mare de procesoare elementare comandate de un singur procesor de control, executand aceeasi instructiune, posibil anumite procesoare inactive la anumite momente de timp - la executia anumitor instructiuni).

Exemple: CM2, MASPAR, sistemele sistolice VLSI

Varianta: masina vectoriala (un singur procesor cu unitati functionale multiple, toate efectuand aceeasi operatie in acelasi moment de timp).

4) Modelul 4 de masina: cluster de SMP-uri sau CLUMP (mai multe SMP-uri conectate intr-o retea).

Fiecare SMP: sistem cu memorie partajata!

Comunicatia intre SMP-uri: prin transfer de mesaje.

Exemple: Millennium, IBM SPx, ASCI Red (Intel).

Model de programare: se utilizeaza transferul de mesaje, chiar in interiorul SMP-urilor!

1.2 CLASIFICAREA CALCULATOARELOR PARALELE

-SIMD (Single Instruction Multiple Data):-Procesoare matriciale;-Procesoare vectoriale;-Procesoare sistolice VLSI.

-MIMD (Multiple Instruction Multiple Data):-Multiprocesoare (MIMD cu memorie partajată):

-UMA (Uniform Memory Access):-UMA cu magistrale;-UMA cu comutatoare.

-NUMA (Non-Uniform Memory Access):-CC-NUMA (Cache Coherent NUMA);-NC-NUMA (Non Coherent NUMA).

-COMA (Cache Only Memory Access).-Multicalculatoare (MIMD cu transfer de mesaje):

-MPP (Massively Parallel Processors):-MPP cu grilă;-MPP hipercub.

-COW (Cluster Of Workstations).

1.3 TIPURI DE CALCULATOARE PARALELE

• Calculatoare în bandă de asamblare

• Calculatoare de masive

• Sisteme multiprocesor

• Calculatoare în flux de date

• Sisteme sistolice VLSI

Calculatoare în bandă de asamblare

Execuţia instrucţiunilor într-un calculator secveţial.

Procesor în bandă de asamblare

Execuţia instrucţiunilor într-un calculator în bandă de asamblare.

Structura funcţională a unui calculator în bandă de asamblare.

Calculatoare de masive

Structura funcţională a unui calculator de masive.

Sisteme multiprocesor

Structura funcţională a unui sistem multiprocesor.

Calculatoare în flux de date

Exemplu: se consideră calcularea expresiei: z = ( x + y ) * 2

. Graful şi şabloanele în flux de date.

Mecanismul de execuţie al unui program în flux de date.

Sisteme sistolice VLSI

Exemplu: se consideră un sistem simplu pentru calcularea convoluţiilor, utilizând o reţea liniară de elemente de prelucrare:

y(i) = w1*x(i)+ w2*x(i+1)+w3*x(i+2)+w4*x(i+3)

Reţea liniară pentru calcularea convoluţiilor.

1.4 PERFORMANŢE ALE CALCULATOARELOR PARALELE

• Masuratori de performanta

• Factorul câştig de viteză

• Principiul mediei armonice ponderate

• Legea lui Amdahl

• Limitări ale calculului paralel

Masuratori de performanta 

Gradul de paralelism DOP („degree of parallelism”) = numarul de procesoare dintr-un calculator paralel utilizate pe un anumit interval de timp.

Profilul paralelismului = graficul DOP in functie de timp (pentru un anumit program). Depinde de:

-structura algoritmului;-optimizarea programului;-utilizarea resurselor;-conditiile de rulare.

 

Se considera un sistem paralel cu n procesoare identice.  

Paralelism mediu Notatii:

∆ = capacitatea de calcul pentru un procesor, aproximat cu rata MIPS (million instructions per second):

666 101010

C

If

CPI

f

T

IRata CC

MIPS

undeIC : numar instructiuni pentru program („instruction count”);

T : timp de executie pentru program in secunde;f : frecventa ceasului in Hz, egala cu 1/τ (τ perioada ceasului in secunde);CPI : cicluri per instructiune (perioade de ceas necesare pentru executia unei

instructiuni);C : numar de cicluri necesare pentru executia unui program.

Au fost utilizate relatiile:

CI

CCPI f

CPIICPII

f

CCT CC

Aproximarea ∆ cu rata MIPS sau rata Mflops nu tine seama de penalizarile datorate accesului la memorie, latenta comunicatiei, overhead-ul sistemului.

Volumul de lucru W („work”) este proportional cu aria de sub graficul profilului:

2

1

)(t

t

dttDOPW

iar in cazul discret:

n

iitiW

1

unde ti = timpul total cat DOP = i, iar

n

ii ttt

112

(timpul total scurs). 

Paralelismul mediu A („average paralellism”):

2

1

)(1

12

t

t

dttDOPtt

A

n

ii

n

ii ttiA

11

/

Factorul câştig de viteză

Definitie. Factorul câştig de viteză sau accelerare notat S (“speedup”) pentru un calculator paralel este raportul dntre timpii necesari pentru rezolvarea aceleiaşi probleme pe un sistem monoprocesor şi respectiv pe sistemul paralel.

log2n < S < n/ln n

log2n supoziţia lui Minsky.

Limita superioară n/ln n :-o problemă se rezolva pe un monoprocesor în unitatea de timp, T1=1;

- fi probabilitatea de a asigna aceeaşi problemă la i procesoare, cu o încărcare medie

di=1/i per procesor;

-se presupun probabilităţi egale pentru fiecare mod de operare utilizând i procesoare, (fi=1/n pentru n moduri de operare, i=1,2,3,…,n);

-timpul mediu necesar pentru rezolvarea problemei pe un sistem cu n procesoare :

n

i

n

iiin n

idfT

1

1

1

-câştigul mediu de viteză S :

n

n

i

n

T

TS n

i

n ln1

1

1

-volumul de lucru cu DOP =i:

ii tiW

n

iiWW

1

-timpul de executie al volumului Wi pe un uniprocesor:

i

i

Wt )1(

- timpul de executie al volumului Wi pe k procesoare:

ikk

Wkt i

i

)(

-intr-un sistem cu numar infinit de procesoare:

nii

Wt i

i

1)(

-timpul de raspuns:

n

i

n

i

ii

WtT

1 1

)1()1(

n

i

n

i

ii i

WtT

1 1

)()(

=> factorul asimptotic de accelerare S∞ :

n

ii

n

ii

n

i

i

n

ii

n

i

i

n

ii

t

ti

iti

ti

iW

W

T

TS

1

1

1

1

1

1

)(

)1(

Performanta medie aritmetica 

-se noteaza cu Ri ratele de executie ale programelor i = 1, 2, 3, ... , n. Rata

medie aritmetica de executie:

n

RR

n

ii

a

1

(s-a presupus ponderea 1/n pentru fiecare din cele n programe). 

-daca programele au ponderi cu o distributie oarecare π = { fi | i = 1, 2, ..., n}:

i

n

iia RfR

1

*

Performanta medie geometrica 

-rata de executie medie geometrica:

n

i

nig RR

1

/1

-iar pentru o distributie a ponderilor π = { fi | i = 1, 2, ..., n}:

n

i

fig

iRR1

*

Rata de executie medie armonica 

-timpul mediu de executie per instructiune pentru programul i:

ii R

T1

-timpul mediu (aritmetic) de executie per instructiune:

n

i

n

i iia Rn

Tn

T1 1

111

=> rata de executie medie armonica este inversul timpului mediu:

n

i i

h

R

nR

1

1

=> rata de executie medie armonica ponderata pentru o distributie oarecare de ponderi π = { fi | i = 1, 2, ..., n}:

n

i i

ih

Rf

R

1

* 1

Principiul mediei armonice ponderate Fie Tn timpul necesar execuţiei a m taskuri de n tipuri diferite, fiecare tip constând din

mi taskuri, necesitând ti secunde:

ii f

m

m

n

ii

in

iii

nh

tmm

tm

m

T

mR

11

* 1

n

iimm

1

n

iiin tmT

1

Rata de execuţie R (numărul de evenimente sau operaţii în unitatea de timp):

Se definesc fi ca fracţia de rezultate generate la rata Ri şi ti=1/Ri ca timpul necesar

pentru generarea unui rezultat

ii

ii

ii t

Rfm

mf

1;1;

Rata globala a masinii:

n

i i

in

iii

h

Rf

tfR

11

* 11

Factorul de accelerare medie armonica 

Se presupune executia unui program (sau o incarcare cu mai multe programe) pe un sistem cu n procesoare. In diferite intervale de timp sistemul poate utiliza i=1, 2, ..., n procesoare (modul i cu i procesoare).  -timpul secvential pe un uniprocesor cu R1 = 1:

11

11

RT

-timpul de executie cu i procesoare cu Ri = i, in cazul ideal:

iRT

ii

11

Programul este executat in n moduri de functionare cu o distributie a ponderilor π = { fi

| i = 1, 2, ..., n}. 

=> factorul de accelerare medie armonica:

n

i i

ih

R

fT

TS

1

*1* 1

unde T* = 1/Rh* este timpul mediu armonic de executie pentru cele m moduri de

executie.

Legea lui Amdahl 

caz particular al principiului de mai sus

Pentru un sistem de calcul se consideră două rate de execuţie:-rata de execuţie superioară (sau paralelă) RH;

-rata de execuţie inferioară (sau serială) RL.

Dacă f reprezintă fracţia rezultatelor generate cu rata RH şi 1-f este fracţia rezultatelor

generate cu rata RL, ecuaţia mediei armonice ponderate devine:

LH Rf

Rf

fR

1

1)(

Se presupune Ri = i, π = (1-f, 0, 0, ..., 0, f). In ecuatia pentru Sh* se inlocuieste R1 = 1 si

Rn = n:

ffn

n

nff

Rf

Rf

S

n

h

)1(1

11

11

1

*

Consecinta: Sh* → 1/(1-f) pe masura ce n → ∞.

Eficienta, utilizarea si calitatea

Se noteaza:O(n) = numarul de operatii unitare executate intr-un sistem cu n procesoare.T(n) = timp de executie (unitati de timp) in general O(n) > T(n).T(1) = O(1) intr-un uniprocesor.

 Se definesc:-factorul de accelerare:

)(

)1()(

nT

TnS

-eficienta:

)(

)1()()(

nTn

T

n

nSnE

Deoarece 1≤S(n) ≤n => 1/n≤E(n) ≤1.  -redundanta:

)1(

)()(

O

nOnR

Evident 1≤R(n) ≤n.

)(

)()()()(

nTn

nOnEnRnU

-utilizarea:

Sunt interesante urmatoarele relatii: 

1/n≤E(n) ≤U(n) ≤11≤R(n) ≤1/E(n) ≤n

 -calitatea paralelismului:

)()(

)1(

)(

)()()(

2

3

nOnTn

T

nR

nEnSnQ

deoarece E(n) ≤1, 1≤R(n) ≤n => Q(n) este limitat superior de S(n).

In concluzie:

-accelerarea indica castigul de viteza de calcul intr-un sistem paralel;

-eficienta masoara partea utila a prelucrarii (lucrului) efectuate de n procesoare;

-redundanta masoara dimensiunea cresterii incarcarii de lucru;

-utilizarea indica gradul de utilizare a resurselor in timpul calculului paralel;

-calitatea combina efectele accelerarii, eficientei si redundantei intr-o singura expresie pentru a evidentia meritul calcului paralel.

Limitări ale calculului paralel variabile:

-ts = timpul de sincronizare;

-t = timpul mediu de execuţie a unui task (granularitatea taskurilor);-to = overhead-ul taskurilor cauzat de execuţia paralelă;

-N = numărul de taskuri executate între două puncte de sincronizare;-n = numărul de procesoare.

Execuţia secvenţială a celor N taskuri, fiecare necesitând un timp t are loc într-un timp total T1 = N t.

Într-un sistem paralel:-fiecare task necesită (t+to) unităţi de timp, în loc de t.

-N taskuri pe n procesoare număr paşi paraleli (raportul celular) = N/n.

Timpul de execuţie paralelă:

)(, osnN ttn

NtT

Creşterea de viteză este:

Ntt

nN

Ntt

ttnN

t

Nt

T

TS

o

sos

nNnN

)1(

1

)(,

1,

Mărirea factorului de accelerare:

-efectul sincronizării ts/(Nt):

-scăderea timpului de sincronizare ts;

-creşterea produsului Nt (însemnând intervale mai largi între sincronizări).-efectul de overhead to/t,:

-scăderea timpului de overhead to;

-creşterea granularităţii t.-numărul de paşi de calcul N/n :

-utilizând mai multe procesoare;-număr de taskuri multiplu al numărului de procesoare.

Eficienţa sistemului multiprocesor se defineşte prin relaţia:

n

SE nN

nN,

,

Limitările calculului paralel trecerea la limită în relaţiile pentru creşterea de viteză SN,n şi eficienţa EN,n. Rezultatele în tabela:

1.5 PROGRAME PARALELE

Cateva exemple de aplicatii complexe ale calculatoarelor paralele:

-simularea curentilor oceanici (structura regulata si calcule stiintifice);-simularea evolutiei galaxiei (structura neregulata si calcule stiintifice);-generarea scenelor prin metoda „Ray Tracing” (aplicatie de grafica pe

calculator cu structura neregulata);-Data Mining (structura neregulata).

 

Simularea curentilor oceanici 

Forte fizice: efectele atmosferice, vantul si frecarea cu fundul oceanului => sisteme complexe de ecuatii.

Problema continua in spatiu (intanderea oceanului) si in timp (se face studiul pe un interval mare de timp) => discretizarea problemei dupa ambele dimensiuni.

Discretizarea spatiului: grid de puncte egal distantate, fiecare punct avand valori pentru marimile de interes ( presiune, viteza, etc). Se utilizeaza un set de griduri bidimensionale (sectiuni orizontale prin volumul oceanului).

Timpul discretizat: serie finita de pasi.

Solutia depinde de rezolutia aleasa in ambele dimensiuni (spatiu si timp). Exemplu: o zona din ocean de 2000x2000 km2 un grid de 100x100 este insuficient (distanta dintre doua puncte 20 km, iar pentru simularea pe 5 ani, cu un pas de timp de 8 ore => 5500 pasi de timp).

Problema prezinta un paralelism intrinsec (calculele si actualizarea valorilor diferitelor puncte din spatiu se poate face in paralel). Astfel, de exemplu se poate asigna cate un grid unui procesor, calculele realizandu-se in paralel. 

Simularea evolutiei galaxiei 

Studiul evolutiei stelelor intr-un sistem de galaxii in timp (probleme de coliziune a galaxiilor, gruparea stelelor in galaxii).

Se simuleaza deplasarea a n corpuri, fiecare corp fiind sub influenta tuturor celorlalte corpuri (problema n-body). Timpul discretizat, mai multi pasi de timp. Pentru fiecare pas se calculeaza fortele gravitationale exercitate, actualizand pozitia, viteza si alti parametri pentru fiecare corp.

n corpuri => complexitate O(n2), dar prin algoritmi ierarhici => complexitate O(n log n).

Algoritmii ierarhici se bazeaza pe faptul ca forta de interactiune scade cu distanta (~1/r2), deci influentele corpurilor foarte indepartate pot fi calculate prin gruparea acestora si considerarea grupului ca un singur corp in centrul de masa, fara pierdere de precizie.

Algoritmii ierarhici: forta de interactiune scade cu distanta (~1/r2).

=> influentele corpurilor foarte indepartate -> prin gruparea acestora!

=> cu cat stele sunt mai indepartate de steaua curenta cu atat grupurile de aproximare pot fi mai mari.

Algoritmul utilizat: Barnes-Hut.

Caracteristici: 1) Distributia de stele neregulata (galaxiile mai dense in anumite zone si mai

imprastiate in altele).2) Distributia se modifica in timp (evolutia in timp).

=> structura neregulata si dinamica a sistemului de galaxii (implementare dificila pe un sistem paralel).

Paralelizarea programelor

Algoritm secvential pentru rezolvarea unei probleme => programul paralel.

Este necesar:-sa se identifice activitatile (incluzand calcule, accesul la date si operatii de

I/E) care pot fi efectuate in paralel;-sa se imparta activitatea si eventual si datele intre procese;-se se gestioneze accesul datelor, comunicatia si sincronizarea;

Scop: micsorarea timpului de calcul => factorul de accelerare S=T(1)/T(n).

Pasii pentru crearea unui program paralel:

1. Descompunerea: spargerea calculului (algoritmului) intr-o colectie de taskuri -> distribuite procesoarelor.

Exemplu. Program cu doua etape:1) se calculeaza in mod independent n2 valori (tablou nxn);2) se insumeaza cele n2 rezultate.

Sistem cu p procesoare: n2/p calcule fiecarui procesor(in paralel), apoi rezultatele insumate secvential intr-o variabila globala.

Timpul total in acest caz este n2/p+n2 (fata de 2n2 unitati de timp in cazul secvential). Factorul de accelerare obtinut este:

(limita 2).

Imbunatatirea algoritmului: in etapa a doua fiecare procesor face o suma locala a rezultatelor obtinute, iar apoi aceasta suma este adunata la rezultatul fina (variabila globala).

Timpul: n2/p+n2/p+p=2n2/p+p.

Factorul de accelerare in acest caz se obtine:

(pentru n mare, limita apropiata de p).

Profilul concurentei: numarul de operatii (sau taskuri) disponibile pentru executie concurenta la un moment dat.

Aria de sub grafic = volumul total de prelucrare (timp uniprocesor).Limita orizontala din grafic = timpul cel mai scurt de executie a aplicatiei (presupunand un numar infinit de procesoare). Factorul de accelerare:

2. Asignarea: mecanism de distribuire a taskurilor la procese (exemplu: algoritm Barnes-Hut -> care procese calculeaza fortele de interactiune pentru care stele).

Scop principal: echilibru de incarcare intre procese (reduce comunicatia intre procese si costul gestionarii).

Asignarea poate sa fie:

-statica (predeterminata): asignarea este complet determinata la inceputul programului, sau dupa introducerea datelor initiale si nu se modifica in timpul executiei aplicatiei;

-dinamica: asignarea lucrului la procese se determina in timpul executiei, eventual ca reactie la un dezechilibru de incarcare.

3. Orchestrarea: determinata de arhitectura si modelul de programare(chiar si de limbajul de programare).

Mecanisme:-numire si accesare a datelor;-comunicatie intre procese;-sincronizare;-planificarea taskurilor asignate unui proces (ordinea in care taskurile sunt

executate).

Scop: reducerea costului comunicatie si sincronizarii vazute de procesoare, planificarea executie mai devreme a taskurilor de care depind alte taskuri, reducerea overhead-ului corespunzator gestionarii paralelismului.

4. Maparea: repartizarea proceselor (dupa etapele 1, 2, 3 => program paralel) la procesoare.

Controlul maparii:-program;-S.O.

In cazul cel mai simplu: procesoarele masinii impartite in subseturi si doar un singur program poate rula la un moment dat pe un subset (partajarea spatiului).

Cealalta solutie extrema: S.O. controleaza dinamic momentul si spatiul (setul de procesoare) pentru executia proceselor (fara interventia utilizatorului).

=> o mai buna partajare si utilizare a resurselor.

In multe situatii reale: combinatie a celor doua.

Paralelizarea unui program

Modul al aplicatiei de simulare a curentilor oceanici: rezolvarea iterativa de ecuatii („equation solver”).

Limbaj pseudocod cu extensii pentru specificarea paralelismului (primitive de sincronizare si comunicatie, in cadrul arhitecturilor cu memorie parajata sau in transfer de mesaje).

Metoda de diferente finite (Gauss-Siedel): tablou bidimensional de (n+2)x(n+2) elemente corespunzator unui grid (sectiune orizontala prin volumul oceanului). Punctele de pe granite nu se modifica, in timp ce cele nxn puncte interioare sunt actualizate de program pornind de la valorile lor initiale, intr-un numar de pasi. La fiecare pas se opereaza asupra tuturor punctelor interioare ale gridului, fiecare punct fiind inlocuit printr-o medie ponderata a vecinilor imediati.

Actualizarile se fac imediat (un punct va vedea valorile noi la vecinii sus si stanga si valorile vechi la vecinii jos si dreapta).

Se calculeaza de asemenea si diferenta intre valoarea veche si valoarea noua pentru fiecare punct. Daca diferenta medie peste toate elementele este mai mica decat o valoare predefinita solutia a convers si se incheie algoritmul, altfel se continua cu un nou pas.

1) Descompunerea.

-studierea buclelor: daca iteratiile pot fi executate in paralel (aici nu exista concurenta: datele utilizate in iteratia curenta sunt actualizate in iteratia precedenta, deci iteratiile nu se pot executa in paralel).

-examinarea dependentelor fundamentale. Ordinea de actualizare a punctelor gridului este stanga->dreapta si sus->jos, deci punctele de pe antidiagonala (diagonala secundara, NE->SV) sunt independente din p.d.v. al calculului si deci pot fi calculate in paralel. Dezavantaje: prea multe puncte de sincronizare si incarcarea este dezechilibrata (procese cu numar de puncte intre 1-n).

-cunoasterea problemei: ordinea de evaluare a punctelor din grid nu este esentiala in metoda Gauss-Seidel => alta ordine: ordinea rosu-negru. Fiecare pas al algoritmului este impartit in doua faze complet echilibrate (actualizarea n2/2 puncte rosii si actualizare n2/2 puncte negre) ce se pot executa in paralel, cu o singura operatie de sincronizare (care nu este absolut necesara, dar convenabila).

for -> for_all (paralelizare, gradul de concurenta obtinut fiind n2).

Descompunere pe randuri: linia 18 for_all -> for (grad de concurenta n).

Sincronizare globala la sfarsitul buclei for_all (end for_all).

2) Asignarea. Solutia statica (cea mai simpla): se asigneaza cate un bloc compact de randuri la un proces (asignare de blocuri), astfel incat randul i este asignat procesului

Avantaj: reducerea comunicatiilor (randurile adiacente sunt pastrate impreuna la acelasi proces).

Solutia dinamica: un proces terminand de calculat un rand, va prelua un alt rand necalculat.

3a) Orchestrarea in modelul paralelismul datelor.

3b) Orchestrarea in modelul cu memorie partajata. Tabloul A este declarat partajat, elementele acestuia fiind accesate de procese pe masura ce sunt necesare, folosind instructiuni load/store obisnuite. Sunt utilizate mecanisme pentru crearea de procese, coordonarea acestora prin sincronizare si controlul asignarii lucrului la acestea.

Program de tip SPMD (Single Program Multiple Data). Se utilizeaza o serie de primitive cu implementari in diferite masini fizice cu memorie partajata:

3c) Orchestrarea in modelul cu transfer de mesaje. Matricea A reprezentata prin structuri de date mai mici, alocate spatiilor private ale proceselor care le prelucreaza.. In cazul acestui algoritm se aloca fiecarui proces cate un set de randuri consecutive din cadrul gridului.

Se pot utiliza operatiile REDUCE si BROADCAST pentru simplificarea codului:

Concluzii:-descompunerea si asignarea sunt asemanatoare in cele doua modele

importante, cu memorie partajata si in transfer de mesaje;-orchestrarea este diferita (structuri de date, accesul/denumirea datelor,

comunicatia, sincronizarea).

Diferente: