Post on 04-Apr-2018
7/29/2019 Arhitecturi Paralele de Calcul
1/75
1
ANALIZA I PROIECTAREA ALGORITMILOR PARALELI
1. PARAMETRI DE PERFORMAN I MODELE PENTRU SISTEMEPARALELE
1.1. Concepte de baz
Dezvoltarea tehnologiei VLSI a permis crearea de maini care dein sute sauchiar mii de procesoare care comunic ntre ele pentru rezolvarea unor problemedate. Scopul realizrii acestor maini este de a obine timpi de procesare ct mai micipentru rezolvarea de probleme complexe care, n unele cazuri, sunt aproapeimposibil de procesat pe mainile clasice (uniprocesor) existente.
Practic, creterea spectaculoas a puterii de calcul nu s-a concretizatntotdeauna n mod direct n creterea performanei sistemului. Mai multe motivestau la baza inegalitii existente ntre puterea de calcul disponibil i performanaobinut. Pentru a obine performana maxim pentru un anumit sistem de calcultrebuie s se pstreze, pe ct este posibil, ct mai multe procesoare active. ns,acest lucru depinde foarte mult de algoritmul utilizat. Se poate ca problema n sine sfie de aa natur nct ea s nu admit pentru rezolvare un algoritm paralel eficient.Dac totui algoritmul paralel ales este eficient pentru problema dat, s-ar putea caacesta s nu se potriveasc n ntregime pe arhitectura mainii pe care este executat.
n concluzie, nu orice algoritm paralel poate fi mapat eficient pe o main
paralel real sau, se poate, ca din necesitatea meninerii ct mai multor procesoareactive pe o perioad ct mai mare de timp s se ajung la execuia unei cantiti
nsemnate de calcule redundante. Mai mult, dac dou sau mai multe procesoarecoopereaz n rezolvarea unei probleme, apare necesitatea existenei unei structurieficiente de comunicare i coordonare a procesoarelor. Eficiena i complexitateaacestei structuri depinde de numrul procesoarelor existente n sistem i de modulde comunicare a acestora.
nelegerea naturii i a gradului n care toi aceti factori afecteaz negativperformanele algoritmilor i arhitecturilor paralele, va duce n mod negreit la
mbuntirea semnificativ a acestora.
1.2. Modele paralele
Exist dou mari clase de modele paralele:1. cu memorie partajat (shared memory architecture)2. cu memorie nepartajat (non-shared memory architecture)
7/29/2019 Arhitecturi Paralele de Calcul
2/75
2
Reteauade
interconectare
P1
P2
Pp
M1
M2
Mqa)Shared memory architecture (p procesoare i un sistem de memorie partajat cu
q - ci de ntreesere);
Reteauade
interconectare
P1
P2
Pp
b)Non-shared memory architecture;
Reteaua de interconectare
P1P2
P3P4
P5P6
P7
P8
M1M2
M3M4
M5M6
M7
M8
c) Sistem cu memorie partajat pentru a interconecta 8 procesoare la un sistem dememorie ntreesut cu 8 ci prin intermediul comutatoarelor crossbar;
P1
P2 P3
P4 P5
P6 P7
P0
d) Reea de tip hipercub;
Fig. 1.1 Exemple de modele paralele [Lak90].
7/29/2019 Arhitecturi Paralele de Calcul
3/75
3
n arhitecturile cu memorie partajat, procesoarele comunic prin scrierea,respectiv citirea datelor n/din memoria partajat. Dei n cazul acestor arhitecturiapare necesitatea sincronizrii globale a procesoarelor pentru transmiterea datelor,ele au dou avantaje extrem de importante:
permit proiectantului de algoritmi accesul la date n modtransparent; pot simula orice form de comunicare dintre cele permise de
modelele cu memorie nepartajat.
Comunicaiile dintre procesoare n cazul arhitecturilor cu memorienepartajat, se realizeaz prin transmiterea de mesaje (message-passing), iarsincronizarea procesoarelor este esenial pentru transmiterea datelor. Un avantajmajor al acestor arhitecturi este acela c pot exploata imediat topologia reelei deinterconectare pentru a rezolva n mod eficient o clas de probleme specifice.
Un model general utilizat pentru studiul calcului paralel este paracalculatorul.Acesta const dintr-un set de procesoare identice )pi1(,Pi , fiecare avnd omemorie local. Memoria local reine programele i fiecare procesor utilizeazaceast memorie pentru calculele sale. Se presupune c fiecare procesor i cunoatepropriul index. Procesoarele pot rula sincron sau asincron. ntr-un model sincron,toate procesoarele ruleaz un singur, dar pot opera pe diferite segmente de date, nfuncie de propriul index. ntr-o configuraie asincron, fiecare procesor poate rulaseturi diferite de programe.
n cazul n care procesoarele lucreaz sincron fiecare procesor comunic cucelelalte prin scrierea/citirea n/din memoria partajat (aceast memorie are un
numr nelimitat de celule). Se poate presupune c datele se afl n primele N celulede memorie M1, M2, . . ., MN ale memoriei partajate iar celelalte celule sunt iniializatecu valoarea zero. Numrul de procesoare (p) trebuie s fie o funcie dependent dedimensiunea problemei (N, Nlog2N, 2N, etc.). ntr-un pas oarecare, fiecare procesorpoate fie s execute calcule, fie s scrie/citeasc n/din memoria partajat.
O clasificare a modelului cu memorie partajat este dat de modalitile deaccesare a memoriei partajate de ctre procesoare [Lak90]:
a) Concurrent Read and Concurrent Write (CRCW). Sunt permisescrierile/citirile simultane n/din aceeai locaie de memorie de ctre
procesoare diferite. Acest model poate fi clasificat mai departe n funciede modul n care este rezolvat conflictul care apare la scriere:
Priority Write CRCW: atunci cnd survin mai multe cereri descriere, procesorul cu index minim va avea prioritate la scriere;
Common Write CRCW: toate procesoarele vor scrie aceeaicantitate de date atunci cnd apar cereri simultane de scriere.
7/29/2019 Arhitecturi Paralele de Calcul
4/75
4
b) Concurrent Read but Exclusive Write (CREW). Permit citiri simultanedintr-o celul de memorie de ctre mai mult procesoare, ns nu permitdect unui singur procesor s scrie la un moment dat n celularespectiv. La fel ca i modelul CRCW, acest model permite conflicte nfaza defetch (instruciune sau operand). Acest model mai este denumit i
PRAM (Parallel Random Access Memory).
c) Exclusive Read and Exclusive Write (EREW). Acest model nu permitecitiri/scrieri simultane din aceeai celul de memorie. Modelul estecunoscut sub numele de PRAC (Parallel Random Access Computer) i estemai apropiat de realitate. Modelul EREW poate fi redus la un numr fixde celule de memorie i permite implementarea restriciilor deacces/celul. Dac exist un singur procesor care are drept de citire i unsingur procesor care are drept de scriere pentru fiecare celul dememorie, atunci fiecare locaie acioneaz ca o legtur unidirecional
ntre cele dou procesoare. n acest fel, modelul EREW poate simula uorarhitectura cu memorie nepartajat cu reea de interconectare fix, cumar fi hipercubul.
1.3. Msurarea performanei sistemelor paralele
Exist mai multe ci de evaluare a performanei calculatoarelor i aalgoritmilor paraleli. Ca i standard, s-a impus ca vrful de performan al uneimaini s fie exprimat n uniti de milioane de instruciuni executate ntr-o secund
(MIPS), sau de milioane de operaii n virgul flotant executate/secund (MFLOPS).
610executiedeTimpul
programniinstructiudeNumarMIPS
= ( 1.1)
610executiedeTimpul
tatanflovirgulainoperatiideNumarMFLOPS
= ( 1.2)
Dei aceti parametri sunt simplu de neles i de utilizat, ei nu reflect corectperformanele reale ale sistemelor de calcul. De exemplu, se poate estima timpul de
execuie al unui program dac se cunoate numrul su de instruciuni i valorileparametrilor MIPS sau MFLOPS. ns, aceti parametri sunt dependeni de setul deinstruciuni main i de programul evaluat. Mai mult, nu toate instruciunile nvirgul flotant au aceeai complexitate i acelai timp de execuie [Gri00].
Pentru evaluarea corect a performanelor reale ale sistemelor de calcul s-apropus utilizarea unor programe standard, care, executate n condiii identice, sofere posibiliti de analiz a calculatoarelor (buclele Livermore, Linpack, PerfectClub, Whetstone, Dhrystone, SPEC etc.).
7/29/2019 Arhitecturi Paralele de Calcul
5/75
5
n realitate, performana realizat (atins) poate fi mult mai mic dectperformana de vrf. n mod cert, performana atins la ora actual este n funcie degradul de mapare (de potrivire) a algoritmilor pe arhitectura pe care acetia ruleaz[Lak90].
1.3.1. Accelerarea
Cea mai bun msur a eficacitii algoritmilor paraleli este raportul deaccelerare (Sp) fa de cel mai bun algoritm serial, care este definit ca raportul dintretimpul necesar de a rezolva aceeai problem utiliznd cea mai bun metod serialcunoscut i timpul necesar de a rezolva aceeai problem cu un algoritm paralelcare utilizeaz p procesoare.
Astfel, dac T(N) semnific timpul cerut de cel mai bun algoritm serial pentrua rezolva o problem de dimensiune N, i Tp(N) semnific timpul luat de algoritmulparalel care utilizeaz p procesoare n rezolvarea aceleiai probleme, atunci [Lak90]
[Cul99]:
)N(T
)N(TS
p
p = ( 1.3)
Este evident c Sp este o funcie dependent de N (N este dimensiuneaproblemei), iarp este numrul de procesoare.
Practic, exist mai multe variante alternative ale definiiei accelerrii [Gri00]:
relativ, cnd T(N) este timpul de execuie al variantei paralele pe un
singur procesor al sistemului paralel;
real, cnd se compar timpul execuiei paralele cu timpul de execuiepentru varianta serial cea mai rapid, pe un procesor al sistemuluiparalel;
absolut, cnd se compar timpul de execuie al algoritmului paralel cutimpul de execuie al celui mai rapid algoritm serial, executat deprocesorul serial cel mai rapid;
asimptotic, cnd se compar timpul de execuie al celui mai bunalgoritm serial cu funcia de complexitate asimptotic a algoritmuluiparalel, n ipoteza existenei numrului necesar de procesoare;
relativ asimptotic, cnd se folosete complexitatea asimptotic aalgoritmului paralel executat pe un procesor.
7/29/2019 Arhitecturi Paralele de Calcul
6/75
6
1.3.2. Eficiena
O alt msur a performanei este eficiena procesorului Ep (randamentul unuiprocesor) care este definit ca raportul ntre rata de accelerare i numrul deprocesoare:
=p
SE
p
p Accelerare / procesor ( 1.4)
Nu toi algoritmii seriali admit accelerare atunci cnd sunt implementaiparalel. Dar toi algoritmii paraleli pot fi serializai n mod direct. Deoarecealgoritmul paralel care utilizeazp (>1) procesoare trebuie s se execute cel puin attde repede ca algoritmul serial, este necesar ca:
1Sp ( 1.5)
n multe cazuri trebuie s comparm performana aceluiai algoritm executatpe o main serial i una paralel. n acest caz accelerarea este definit ca:
)N(T
)N(TS
p
1*
p = ( 1.6)
Ti(N) timpul necesar executrii algoritmului pe i procesoare
Eficiena devine:
p
SE
*
p*
p = cu 1S*
p ( 1.7)
Mai mult, o iteraie a algoritmului paralel care utilizeaz p procesoare va luace multp pai atunci cnd este implementat serial:
)N(Tp)N(T p1 pS1*
p i 1E0*
p ( 1.8)
Deoarece )N(T)N(T 1 , rezult c:
*
pp SS ( 1.9)
Se definete acceleraia liniar sau ideal ( )p( ) pentru o problem dat cafiind o valoare constant independent de dimensiunea problemei i a numrului deprocesoare utilizate n rezolvarea acesteia (fig. 1.2).
7/29/2019 Arhitecturi Paralele de Calcul
7/75
7
0
N
P
( )p
Fig. 1.2. Reprezentarea grafic a acceleraiei ideale ((p)).
Se spune despre un algoritm c are acceleraie optim ( )N(Sp ) dac acceleraia
sa tinde asimptotic ctre acceleraia liniar (fig. 1.3).
)N()N(Sp = ( 1.10)
Sp
0
N
P
( )p
Fig. 1.3. Reprezentarea grafic a acceleraiei optime (Sp(N)).
Este evident c un algoritm cu acceleraie optim poate avea o eficiensczut i, de asemenea, un algoritm cu un bun randament/procesor s nu aib oaccelerare mare (un algoritm serial bun poate fi un algoritm paralel prost i, invers,
algoritmul serial poate fi un algoritm paralel rezonabil [Lak90]).Un alt factor care influeneaz performana este numrul total de operaii
scalare solicitate de algoritm. n cazul algoritmilor seriali funcia de complexitate aalgoritmului este dat de numrul de operaii scalare efectuate. O metod obinuitprin care se poate obine o cretere a accelerrii sistemului, este de a introduce calculescalare suplimentare (redundante). Factorul de redundan Rp al unuialgoritm/procesor este definit ca fiind raportul dintre numrul total de operaii
7/29/2019 Arhitecturi Paralele de Calcul
8/75
8
scalare efectuate de algoritmul paralel cu numrul de operaii scalare efectuate dealgoritmul serial.
1Rp ( 1.11)
n continuare se prezint un algoritm paralel de adunare a N numere x1, x2, ...,xN, stocate n primele N celule de memorie M1, M2, ... MN (fig. 1.4). Se utilizeazpentru calculul sumei celor N numere, N/2 procesoare. Coninutul celulelor dememorie pe parcursul execuiei programului este dat n figura 1.5.a. Calculeleefectuate n algoritm sunt reprezentate n arborele binar din figura 1.5.b.
/* Fie N = 2n pentru orice n 1. Fie x1, x2, ..., xN valori stocate n M1, M2, ... MN.Suma final a celor N valori va fi stocat n celula M1. Se presupune c exist Nprocesoare, ns doar N/2 vor fi utilizate. */
inc=1;
FOR j=1 TO log2N DOFOR i { 1+2kinc | k = 0, 1, ..., N/2j - 1 } DO IN PARALLELREAD Mi and Mi+inc;ADD contents of Mi and Mi+inc;WRITE the sum in Mi;
ENDinc=2inc;
ENDFig. 1.4. Algoritmul paralel de adunare a N numere utiliznd N/2 procesoare pe un
model CREW cu memorie partajat
j M1 M2 M3 M4 M5 M6 M7 M80 1 2 3 4 5 6 7 81 3 2 7 4 11 6 15 82 10 2 7 4 26 6 15 83 36 2 7 4 26 6 15 8
a) Coninutul celulelor de memorie de-a lungul execuiei algoritmului;
x1 x2 x3 x4 x5 x6 x7 x8
x + x1 2 x + x3 4 x + x5 6 x + x7 8
x + x +1 2 x + x3 4 x + x +5 6 x + x7 8
x + x +1 2 x + x +3 4 x + x + x + x5 7 86
b) reprezentarea algoritmului sub form de arbore;Fig. 1.5. Algoritmul de adunare asociativ (algoritmul Heller).
7/29/2019 Arhitecturi Paralele de Calcul
9/75
7/29/2019 Arhitecturi Paralele de Calcul
10/75
10
Grup 1
S + S1 2
S + S + S1 2 3 4+ S
Grup 2 Grup 3 Grup 4
S + S3 4
Fig. 1.6. Arborele binar utilizat n algoritmul de adunare paralel.Si reprezint suma elementelor din grupul i.
Rezult c timpul de execuie al acestui algoritm va fi dat de:
plog1p
N)N(T 2p +
= ( 1.15)
plog1p
N1NS
2
p
+
= ( 1.16)
Fieplogp
NL
2
= factorul de ncrcare al sistemului. Atunci, fiecare procesor va
avea plogL 2 numere de procesat. Rezult c:
1L
Lp
plog)1L(
plogLpS
2
2p +
=+
( 1.17)
1L
LEp +
( 1.18)
Se observ c pentru L , accelerarea este liniar dup p, iar eficiena(randamentul) 1Ep .
O problem este denumit complet asimptotic paralelizabil dac admite unalgoritm cu accelerare optim. n mod cert, accelerarea optim se obine prin alegereadimensiunii problemei ca fiind o funcie de dimensiunea p a numrului de
procesoare utilizate.Algoritmul prezentat anterior este fundamental pentru soluionarea unuimare numr de probleme: calculul produsului intern al unui vector, gsireamaximului sau a minimului unor numere, calculul disjunciei/conjunciei variabilelor
booleene etc.Din acest exemplu se observ c avnd orice algoritm paralel care se bazeaz
pe o structur arborescent, el poate fi convertit imediat ntr-un program paralel imapat pe o arhitectur bazat pe modelul cu memorie partajat.
7/29/2019 Arhitecturi Paralele de Calcul
11/75
11
1.3.3. Costul
Costul este definit ca fiind produsul dintre timpul de execuie al algoritmuluiparalel i numrul de procesoare utilizate n execuia algoritmului respectiv (se
presupune c fiecare procesor execut acelai numr de instruciuni) [Gri00].
pTC pp = ( 1.19)
Pentru ca o aplicaie paralel s fie optim din punctul de vedere al costuluitrebuie ca valoarea acestuia s fie egal cu timpul de execuie al celei mai bunevariante secveniale:
1p TC = ( 1.20)
1.3.4. Legile accelerrii
Legea lui Amdahl
Pentru evidenierea acestei legi am luat ca exemplu o aplicaie care realizeaztestarea porilor logice din cadrul unui circuit digital. n figura 1.7 se prezintcaracteristica procesului de testare. Pe axa x se reprezint timpul de testare alcircuitului (cicli main), iar pe axay se reprezint numrul de pori logice testate lamomentul respectiv de timp [Cul99].
Fig. 1.7. Caracteristica procesului de testare a circuitelor logice digitale [Cul99].
Aria de sub grafic reprezint totalitatea calculelor efectuate de sistemulparalel. Aceast arie mprit la numrul de cicli necesari rulrii programului ne vada accelerarea obinut pe un numr nelimitat de procesoare.
7/29/2019 Arhitecturi Paralele de Calcul
12/75
12
Putem scrie:
cicli.Nr
AriaS ( 1.21)
Pentru p procesoare, dac fk este numrul de puncte de pe axa x n care se
testeaz k circuite, atunci ecuaia (1.21) devine:
=
=
1k
k
1k
k
p
p
kf
kf
S ( 1.22)
Se observ uor c
=
1k
k kf reprezint totalitatea calculelor efectuate. Prin
normalizare i presupunnd c s reprezint fraciunea inerent de cod secvenial din
program, obinem:
p
s1s
1Sp
+ ( 1.23)
Aceast ecuaie este cunoscut ca legea lui Amdahl i ne arat c indiferent denumrul de procesoare i de arhitectura mainii, accelerarea obinut va fi
ntotdeauna mrginit superior datorit fraciunii de cod secvenial care apare ncadrul oricrui program.
Ecuaia Gustafson-Barsis
Legea lui Amdahl nu reflect cazul n care aplicaiile admit paralelism la date.Gustafson i Barsis au modelat matematic un astfel de caz [Gri00].
S-a plecat de la ipoteza conform creia, timpul de execuie al unui programparalel cu paralelism de date poate fi normalizat:
1Tp = ( 1.24)
Timpul de execuie al programului paralel pe un procesor este dat de:
)1p(spT)s1(psTTTT ppparsec1 =+=+= ( 1.25)
iar
s)s1(psspp1
)1p(sp
T
TS
p
1p +=+=
== ( 1.26)
Din ecuaia (1.26) rezult c Sp = O(p) ceea ce nseamn c accelerarea va crete
7/29/2019 Arhitecturi Paralele de Calcul
13/75
13
proporional cu creterea numrului de procesoare. Eficiena n acest caz va ficonstant Ep = O(1) indiferent de variaia luip sau n.
1.3.5. Parametri calitativi
Granularitatea
Granularitatea aplicaiei se definete ca fiind dimensiunea (grain size) minima unei uniti secveniale dintr-un program, exprimat n numr de instruciuni. ncadrul unei uniti considerate secveniale nu se execut operaii de sincronizare saucomunicare cu alte procese. Un proces este compus din uniti secveniale degranulariti diferite. n figura 1.8, se prezint structura unei aplicaii compuse dinmai multe activiti paralele (procese sau fire de execuie). Apar puncte desincronizare/comunicare; fiecare proces sau fir va avea propria granularitate.Granularitatea acestei aplicaii va fi dat de valoarea minim a granularitii pentru
toate activitile paralele componente [Gri00].
Start
1
2
3 4 5
6
7
Stop
Crearea activitatilorparalele (proces, fir)
Puncte de sincronizaresau comunicatie
Fig. 1.8. Structura unei aplicaii paralele.
Se definete granularitatea unui sistem ca fiind valoarea minim agranularitii aplicaiilor, valoare sub care performana scade n mod semnificativ.Scderea de performan se explic prin faptul c n cazul aplicaiilor cugranularitate mic, timpul de sincronizri/comunicaii devine comparabil cu timpul
de execuie paralel.Spre deosebire de granularitatea programelor paralele care trebuie s fierelativ mare, n cazul sistemelor este de dorit s avem o granularitate ct mai mic,astfel nct acestea s poat executa o palet larg de programe (fig. 1.9). Ogranularitate mic pentru un sistem de calcul nseamn un timp de execuie foartemic pentru primitivele de calcul paralel (fork, join, barrier etc.).
7/29/2019 Arhitecturi Paralele de Calcul
14/75
14
Sistem
Granularitate
Timp
Fig. 1.9. Granularitatea sistemului vs. granularitatea aplicaiei.
Scalabilitatea
Scalabilitatea unui sistem paralel reprezint proprietatea acestuia de a asiguracreterea accelerrii odat cu creterea numrului de procesoare. Scalabilitateasistemului este ns dependent de gradul de paralelism al aplicaiei, degranularitatea aplicaiei i, nu n ultimul rnd, de granularitatea sistemului. Dacprin creterea numrului de procesoare se obine o cretere liniar a accelerrii, sespune c sistemul este scalabil liniar.
Pentru a beneficia de proprietatea de scalabilitate trebuie ca n programeleparalele s existe ct mai multe procese concurente, astfel nct odat cu cretereanumrului de procesoare s nu se modifice codul ci doar s se redistribuie procesele.
n plus, prezena n sistem a mai multor procese dect procesoare va permitemascarea operaiilor de comunicaie. Aceast dependen a scalabilitii att desoftware ct i de hardware este reprezentat n fig. 1.10.
localitateareferintei
acces ladate comune
concurentacomunicatiaechilibrarea incarcarii
dimensiunea memorieiraportul calcule/comunicatiidezechilibre arhitecturale
performantele I/E
ALGORITM/SOFTWARE HARDWARE
Fig. 1.10. Factori care influeneaz scalabilitatea [Gri00].
7/29/2019 Arhitecturi Paralele de Calcul
15/75
15
2. MULTICALCULATOARE I MULTIPROCESOARE
Performana unui algoritm paralel se msoar prin valorile accelerrii ieficienei obinute pe mainile actuale. Timpul de citire/scriere n/din memorie este
critic dependent de topologia reelei de interconectare a procesoarelor i respectiv, aprocesoarelor cu memoria. Pentru proiectarea eficient a algoritmilor paraleli trebuies se cunoasc n detaliu modul de organizare a datelor pentru accesul paralel,costurile de comunicaie, maparea sau portabilitatea algoritmilor pe diversearhitecturi.
Calculatoarele paralele sunt clasificate n dou mari grupuri:
1. Multicalculatoare cu memorie distribuit2. Multiprocesoare cu memorie partajat
n organizarea cu memorie partajat un set de procesoare va fi conectat la unset de memorie comun prin intermediul unui bus de vitez mare sau prin una saumai multe reele de interconectare dinamice multinivel. Procesoarele comunic prinscrierea n, i citirea din, memoria comun (partajat).
n organizarea cu memorie distribuit fiecare procesor este conectat lamemoria local (proprie) prin intermediul unei reele statice (fixe) de interconectare.
O alt trstur fundamental de importan teoretic ct i practic se referla portabilitatea algoritmilor pe diverse arhitecturi paralele. Analiza portabilitii vaconduce n mod natural la simularea (ncapsularea) unui set de grafuri n altul.
Exist doi parametri cheie care caracterizeaz calitatea ncapsulrii:
expansiunea i dilataia. Expansiunea se refer la suprancrcarea hardware exprimatn numr de procesoare utilizate, iar dilatarea la creterea comunicaiilor necesaresimulrii unui graf de ctre altul. De exemplu o strategie des utilizat pentruobinerea acestor arhitecturi cu un hipercub este de a utiliza codificri bazate pecodul Gray.
2.1. Multicalculatorul hipercub
2.1.1. Structura recursiv a unui hipercub N-noduri b-baz
Fie N i b dou valori ntregi astfel nct 2bN i fie k un ntreg astfel nctk1k bNb
7/29/2019 Arhitecturi Paralele de Calcul
16/75
16
Mulimea V reprezint mulimea etichetelor nodurilor din graful G, iarmulimea E reprezint mulimea muchiilor hipercubului aferent lui G.
Dou noduri din graful G sunt conectate dac i numai dac etichetele lordifer printr-o valoare de 1. Dac baza b = 2, acest graf este denumit hipercub (N, b,k). Dac N = bk, atunci graful G este denumit hipercub complet (N, b, k) de
dimensiune k, sau pur i simplu cub (N, b, k). Dac N bk, G este denumit cubincomplet (N, b, k) (fig. 2.1.).
000 001
011010
100 101
111110
Fig. 2.1. Structura unui hipercub (8,2,3).
Cubul (N, b, k) admite o caracterizare recursiv. Dac A este un set de iruripeste , atunci se definete
B = xA = { x | A i x },
unde x este un ir obinut prin concatenarea lui x i .
Pentru mulimea nodurilor se definete o mulime de seturi V(i)
, i = 0, 1, ..., k-1,unde
U>
7/29/2019 Arhitecturi Paralele de Calcul
17/75
17
i, pentru 1i ,
>
7/29/2019 Arhitecturi Paralele de Calcul
18/75
18
2.1.2. Proprietile topologice ale unui hipercub (N, b, k)
1) Dac b = N, atunci cubul (N, N, 1) este un graf complet cu N noduri.
2) ntr-un cub complet (N, b, k)
a. Gradul fiecrui nod este Nlog)1b( b
b. Exist NlogN)1b(2
1b muchii
3) Diametrul unui cub (N, b, k) este Nlogb . Diametrul este definit ca fiind
valoarea maxim a cilor cele mai scurte existente ntre perechile denoduri ale unui cub. Aceast valoare maxim apare ntre dou noduriatunci cnd etichetele acestora difer pe fiecare digit. Atta timp ctdiametrul specific ntrzierea maxim de comunicaie, algoritmii
implementai pe cuburi de baz b (b > 2) vor avea ntrzieri mai mici dectun hipercub (b = 2).
4) Avnd date N i d, exist k i b astfel nct diametrul unui cub (N, b, k)este mai mic sau egal cu d.
2.2. Multiprocesoare cu memorie partajat
2.2.1. Concepte de baz
Trstura caracteristic a multiprocesoarelor cu memorie partajat este aceeac un banc comun de module de memorie cu adresare ntreesut este conectat la unset de procesoare printr-o reea, unde fiecare procesor este o main independent(fig. 2.2).
Reteauade
interconectare
P1
P2
Pp
M1
M2
Mq
Fig. 2.2. Arhitectura cu memorie partajat.
Un factor important care deseori degradeaz performana global a acestui tipde arhitectur paralel este legat de conflictele de acces la memorie. Dac k
7/29/2019 Arhitecturi Paralele de Calcul
19/75
19
)Nk1( < din N procesoare genereaz adrese care sunt rezidente ntr-un singurmodul de memorie, atunci sunt necesari k cicli pentru a furniza datele, iarperformana algoritmului poate s fie degradat cu factorul k. Astfel, pentru a pstrarandamentul global, este necesar ca:
a) procesoarele s genereze adrese astfel nct dou procesoare s nusolicite date din acelai modul;
b) datele trebuie s fie distribuite n modulele de memorie pentru a sepermite accesul n paralel
c) reeaua de interconectare trebuie s fie capabil s furnizeze ct mairapid datele solicitate de ctre respectivele procesoare.
Cea mai simpl reea de interconectare este magistrala de mare vitez (highspeed bus) (fig. 2.3). n aceast reea procesoarele nu pot accesa simultan memoria.Prin stabilirea numrului de procesoare i a modulelor de memorie n avans, se poate
calcula lrgimea de band necesar magistralei pentru a servi toate accesele(fetch/store) cu o ntrziere prestabilit. Aceast schem nu se utilizeaz n cazul unuinumr mare de procesoare datorit creterii lrgimii magistralei.
High Speed Bus
P1 P2 Pp
M1 M2 Mq
Fig. 2.3. Structura high speed bus.
La cellalt capt al spectrului se afl reeaua NN crossbar, care are N intrri iN ieiri. Procesoarele sunt conectate la intrri, iar modulele de memorie la ieiri (fig.2.4). La intersecia liniei i cu coloana j exist un comutator cu dou stri ( on/off).Starea on a acestui comutator realizeaz o conexiune ntre procesorul Pi i modululMj. Astfel, ntr-o astfel de reea exist N2 comutatoare.
P1
M1
P2
P3
P4
M2 M3 M4
P1
M1
P2
P3
M2 M3 M4 M5
Fig. 2.4. Reele crossbar de dimensiune 44 i 35.
7/29/2019 Arhitecturi Paralele de Calcul
20/75
20
Fie NN: o permutare. O reea de interconectare realizeaz permutarea
dac exist o stare a comutatoarelor n reea astfel nct intrarea i este conectat laieirea (i) pentru Ni0
7/29/2019 Arhitecturi Paralele de Calcul
21/75
21
0
1
0 1
IN
OUT
S00 S01
S10 S11
0
1IN OUT
0
1
a) Structura unui comutator 22 crossbar b) Simbolul unui comutator 22 crossbar
0
1IN OUT
0
1
bit de control = 0
0
1IN OUT
0
1
bit de control = 1
c) Starea on.
=
10
10d) Starea off.
=
01
10
Fig. 2.5. Comutatorul 22 crossbar.
0
1
0
1
S1
2
3
2
3
S2
0
1
0
1
S1
2
3
2
3
S2
S3
S4
a) Reea 44 cu un singur nivel b) Reea 44 cu dou nivele
0
1
0
1
S1
2
3
2
3
S2
S3
S4
0
1
0
1
S1
2
3
2
3
S2
S3
S4
S5
S6
c) Reea 44 cu dou nivele d) Reea 44 cu trei nivele
Fig. 2.6. Exemple de reele de dimensiune 44 implementatecu comutatoare 22 crossbar.
Astfel, numrul cilor i factorul CP depind critic de numrul de nivele i deschema de interconectare dintre nivele pentru reeaua respectiv.
7/29/2019 Arhitecturi Paralele de Calcul
22/75
22
Fie N = 2n i o reea cu k nivele construit cu comutatoare 22:
1) Exist cel mult2
kNcomutatoare 22;
2) ntr-o reea cu k nivele, nk , exist cel mult o cale ntre fiecareintrare/ieire;
3) Sunt necesare n nivele pentru ca aceast reea s posede proprietatea deacces complet;4) Numrul de permutri realizate de o reea cu k nivele este de cel mult
Nk1pentru2 2kN
;5) ntr-o reea cu o singur cale numrul de permutri realizate este egal cu
numrul de stri distincte ale reelei;6) Dac este permutarea realizat de o reea cu acces complet, atunci, n
general, cel puin o stare a reelei realizeaz aceeai permutare .
Topologii de retea
Statice Dinamice
Crossbar Uninivel Multinivel
Fara blocare Rearanjabile Cu blocare
Fig. 2.7. Taxonomia reelelor de interconectare.
2.2.2. Reele de interconectare cu blocare
Reelele cu blocare fac parte din clasa reelelor cu cale unic i au ocaracteristic recursiv.
Fie N = 2n . BL2 este o reea cu un nivel constnd dintr-un comutator crossbar22. Pentru N 4 i presupunnd c putem crea reeaua BLN/2 rezult reeaua BLN din
figura 2.8.Primul nivel const din N/2 comutatoare 22 numerotate de la 0 la 1
2
N .
Acest nivel este urmat de dou reele BLN/2 identice denumite subreele (cea dedeasupra = top, respectiv, cea de dedesubt = bottom). Ieirea top/bottom aferentcomutatorului i este conectat la intrarea i a subreelei top/bottom. Ieirile subreelei
top sunt numerotate de la 0 la 12
N , iar cele ale subreelei bottom de la
2
Nla N 1.
7/29/2019 Arhitecturi Paralele de Calcul
23/75
23
0
1
0
1
a) BL2;
0
1
0
1
2
3 N/2-1
2i+1
N/2
N/2+1
N-2N-1 N-1
0
1
i
N/2-1
BLN/2
0
1
i
N/2-1
BLN/2
INPUT OUTPUT
0
1
i
N/2 -1
b) Structura BLN;
0
1
0
1
2
3
4
5
6
7
INPUT OUTPUT
S11
S12
S13
S14
S21
S22
S23
S24
S31
S32
S33
S34
2
3
4
5
6
7
c) Un exemplu de BL8;
Fig. 2.8. Exemple de reele cu blocare BLN.
Din definiia anterioar, rezult c aceast reea are log2N nivele cu 2N
comutatoare 22 pe fiecare nivel. Numrul total de comutatoare 22 utilizate pentru
construcia BLN este Nlog2
N2 .
Fie x , N = 2n, i x = xn xn-1 ... x2 x1 n binar. Amestecarea perfect (perfectshuffle) este permutarea NN: astfel nct
7/29/2019 Arhitecturi Paralele de Calcul
24/75
24
n122n1n xxx...xx)x( = ( 2.11)
unde (x) se obine prin rotirea la stnga cu o poziie a biilor din reprezentarea lui x.n exprimare zecimal, rezult
NmodN
x2x2)x(
+= ( 2.12)
Dac k reprezint produsul lui de k ori (k = ..., de k ori), atunci
-1 = n-1
unde -1 este inversa amestecrii perfecte.Permutarea cu reversie de bii este NN: , unde
n1n21 x...xxx(x) = ( 2.13)
Permutarea fluture este NN: astfel nct
n232n1n1 xxx...xxx)x( = ( 2.14)
Permutarea de conversie NN:ei este
1231ii1i1nni xxx...xxx...xx)x(e += ( 2.15)
unde y reprezint complementul lui y.
Fie E un set de 2N/2 permutri realizate de2
Ncomutatoare 22 ntr-o reea
crossbar. Pe baza acestei ipoteze se definesc alte tipuri de reele.O reea omega (N) NN are log2N nivele de comutatoare 22, iar
interconexiunile dintre nivele sunt amestecate perfect (fig. 2.9). Mai mult, intrrilesunt conectate cu primul nivel dup modelul de amestecare perfect. Astfel, N poatefi notat astfel:
( )nN E= ( 2.16)
Reeaua n-cub binar indirect (CN) prezentat n figura 2.10 este definit derelaia
1
)n()3()2(N EE.....EEC= ( 2.17)
7/29/2019 Arhitecturi Paralele de Calcul
25/75
25
Aceast reea este denumit cub binar indirect deoarece menine relaiileexistente ntr-un hipercub. n schema din figura 2.10, prin setarea n cruce (cross) acomutatoarelor de pe nivelul 1 i setarea n starea normal (through) a celorlaltecomutatoare, C8 realizeaz conexiuni ntre procesoarele aflate de-a lungul axei primeidimensiuni a cubului. Se realizeaz astfel conexiuni ntre procesoarele (000, 001) (010,
011) (100, 101) (110, 111). n cazul general, prin setarea cross a comutatoarelor de penivelul i i setarea through a celorlalte comutatoare, se observ c CN simuleazinterconectarea nodurilor unui cub de-a lungul dimensiunii i (de aici rezult numelede cub binar indirect, unde N = 2n).
000
001
010
011
100
101
110
111
S11
S12
S13
S14
S21
S22
S23
S24
S31
S32
S33
S34
000
001
010
011
100
101
110
111
Nivel 1 Nivel 2 Nivel 3
E E E
Fig. 2.9. Reeaua omega ( )3
8 E= .
000
001
010
011
100
101
110
111
S11
S12
S13
S14
S21
S22
S23
S24
S31
S32
S33
S34
000
001
010
011
100
101
110
111
Nivel 1 Nivel 2 Nivel 3
E E E(2) (3) 1
Fig. 2.10. Exemplu de cub binar indirect 1)3()2(N EEC
= .
7/29/2019 Arhitecturi Paralele de Calcul
26/75
26
Avnd dat o reea de interconectare multinivel, prin interschimbareaintrrilor cu ieirile obinem o nou reea denumit reea invers (fig. 2.11).
0
1
0
1
2
3N/2-1
2i+1
N/2
N/2+1
N-2N-1N-1
BLN/2
BLN/2
INPUT OUTPUT
0
1
i
N/2 -1
Fig. 2.11. Reeaua invers BLN
.
Dou reele sunt echivalente din punct de vedere topologic dac o reea poatefi obinut din cealalt prin reetichetarea intrrilor/ieirilor. Echivalena funcional adou reele apare atunci cnd ele realizeaz acelai set de permutri.
Fie N = 2n i fie ca intrrile i ieirile fiecrui nivel din reeaua s fienumerotate de la 0 la N 1 n binar. Conectarea procesorului aferent nodului deintrare s (surs) cu zona (modulul) de memorie aferent nodului de ieire d(destinaie), unde
121nn ss...sss =
i121nn dd...ddd =
se va face prin traseul s d, traseu denumit cale(s, d).O secven de ci unice cu proprietate de acces complet vor determina
obinerea unui arbore binar complet cu n nivele n care fiecare nod de intrarereprezint rdcina, iar toate cele N noduri de ieire reprezentnd frunzele (fig. 2.12).
Pentru fiecare nod al acestui arbore se eticheteaz ramura superioar cu 0, iarcea inferioar cu 1. Prin concatenarea acestor etichete de-a lungul fiecrei ci de lardcin la frunze obinem etichetele pentru ieirea corespunztoare frunzei
respective. Acest mod de etichetare conduce la un algoritm de rutare.Fie u1, u2 ... un comutatoarele de-a lungul cii s d (fig. 2.13). Aceast cale esteincident cu comutatorul uk pe nivelul k. Starea comutatorului uk va fi setat n aafel nct cale(s, d) trece prin ramura de sus a lui uk dac dn-k+1 = 0 i prin ramura de josdac dn-k+1 = 1. Deoarece starea comutatorului uk depinde de dn-k+1, rezult c dn-k+1poate fi utilizat ca i bit de control. Acest algoritm este denumit algoritm de rutare
bazat pe identificatorul destinaiei (destination tag control algorithm).
7/29/2019 Arhitecturi Paralele de Calcul
27/75
27
000
001
010
011
100
101
s = 110
111
000
001
010
011
100
101
110
111
Nivel 1 Nivel 2 Nivel 3
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Fig. 2.12. Arbore binar complet cu n nivele
000
001
010
011
100
101
110111
000
001
010
011
100
101
110111
Nivel 1 Nivel 2 Nivel 3
v1
u1
w1
u2
v2
v3
u3
Fig. 2.13. O reprezentare a algoritmului de rutare bazat pe identificatorul destinaiei110 010, 001 001, 011 000.
2.2.3. Reele de interconectare fr blocare
Primul proiect prin care s-a implementat fizic o reea de interconectare cu CP =1, dar care s necesite mai puin de N2 comutatoare, a fost dezvoltat de Clos i Benes[Lak90].
Fie N = n2 pentru n 2. Reeaua Clos cu trei nivele simetrice const din n copiide nm i mn comutatoare pentru nivelele 1 i 3, unde m = 2n 1. Nivelul 2 esterealizat cu m comutatoare nn (fig. 2.14).
7/29/2019 Arhitecturi Paralele de Calcul
28/75
28
1
2
n
1
2
n
1
2
n
INPUT OUTPUT
Nivel 1(n comutatoare dedimensiune nm)
Nivel 2(m comutatoare dedimensiune nn)
Nivel 3(n comutatoare dedimensiune mn)
Fig. 2.14. Reea Clos cu trei nivele cu N = n2
i m = 2n-1.
Interconexiunile dintre nivele satisfac regula de distributivitate care spune cieirea i a comutatoruluij dintr-un nivel este conectat cu intrareaj a comutatorului idin nivelul urmtor (fig. 2.15).
23
23
22
22
22
32
32
1
2
3
4
1
2
3
4
INPUT OUTPUT
Nivel 1 Nivel 2 Nivel 3
Fig. 2.15. Reea Clos cu trei nivele: N = 4, n = 2, m = 3.
Fie ca primele n 1 procesoare ataate la comutatorul 1 (nivel 1) s fieconectate la un set de n 1 module de memorie printr-un set S de n 1 comutatoaredin nivelul 2, unde S = {s1, s2, ..., sn-1}. Similar, fie ca primele n 1 module de memorieataate la ieirea comutatorului 1 de pe nivelul 3 s fie conectate la un set de n 1procesoare printr-un set t de n 1 comutatoare de pe nivelul 2, unde T = {t1, t2, ..., tn-1}.
7/29/2019 Arhitecturi Paralele de Calcul
29/75
29
Dac cel de-al n-lea procesor dorete s acceseze locaii de memorie din al n-lea modul, iar aceast conexiune este fcut prin comutatorul u de pe nivelul2, ocondiie necesar i suficient care permite tuturor comunicaiilor s se executeindependent, este ca seturile S, T i {u} s fie mutual disjuncte. Deoarece |S| + |T| +{u} = 2n 1, stratul din mijloc al reelei va conine 2n 1 comutatoare. Nivelele 1 i 3
vor conine cte n2m comutatoare. De aici rezult c pentru o reea Clos NN (cu N =n2) cu trei nivele, costul va fi
N3N6mn3)3,n(C 2/322 == ( 2.18)
Se observ intuitiv c reelele fr blocare au un cost mai mic dect reelele cublocare. n tabelul 2.3 se realizeaz o comparaie ntre costul reelelor Clos i costulreelelor cu blocare (se observ c pentru N 36, reelele Clos sunt mai economicedect reelele crossbar cu un singur nivel).
Numr de comutatoareN Reea Crossbar
(N2)Reea Clos cu 3 nivele
(6N3/2 3N)4 16 369 81 135
16 256 33625 625 67536 1296 118849 2401 191164 4096 2880
81 6561 4131100 10000 5700
Tabelul 2.3. O comparaie ntre costurile reelelor crossbar i Clos.
7/29/2019 Arhitecturi Paralele de Calcul
30/75
30
3. PARALELISMUL LA NIVELUL OPERAIILOR ARITMETICE
Paralelismul poate fi obinut n cel puin patru moduri:
la nivel aritmetic la nivel de instruciune la nivel de expresie la nivel de proces (task)
Identificarea paralelismului la aceste nivele se face att hardware prin structurispecifice, ct i software prin implementarea de algoritmi paraleli eficieni.
Pentru o accelerare global a sistemului, este esenial s se utilizeze cei maibuni algoritmi pentru execuia operaiilor aritmetice de baz. Extragereaparalelismului la nivelul instruciunilor a condus la crearea de arhitecturi moderne,
cu putere mare de calcul i execuie rapid. Analiza expresiilor conduce la programeorganizate eficient, care n conjuncie cu paralelizarea operaiilor matematice i aexecuiei instruciunilor vor conduce la execuii rapide ale aplicaiilor. Sistemele deoperare moderne au ca sarcin repartizarea i distribuirea eficient a proceselor (task-urilor) n sistemul paralel. De asemenea, programatorul trebuie s identificeparalelismul existent n aplicaiile create i s utilizeze algoritmi care s exploatezeeficient acest grad de paralelism.
3.1. Analiza algoritmilor de adunare paralel. Algoritmul lui Brent
Implementarea hardware a acestor algoritmi se bazeaz pe operaiile pe bitAND i OR necesare pentru execuia operaiilor aritmetice de baz. Acesta estenivelul cel mai jos de paralelism denumit bit level sau micro level parallelism.
Fie a = aN aN-1 ... a2 a1 i b = bNbN-1 ... b2b1 dou numere ntregi reprezentate nbinar ce vor fi adunate. Fie s = (a + b) mod 2N unde s = sN sN-1 ... s2 s1 este suma celordou numere. Se tie c
1iiii cbas = ( 3.1)
unde c0 = 0 i pentru i = 1 ... N
=
=
=
iii
iii
1iiii
bag
bap
)cg(pc
( 3.2)
unde simbolurile , , reprezint operaiile logice OR-Exclusiv, OR i AND, iar ci
7/29/2019 Arhitecturi Paralele de Calcul
31/75
31
este transportul dinspre bitul de pe poziia i. n calculul sumei s avem nevoie devalorile biilor de transport c0 la cN-1. Deoarece c0 = 0, rezult
( )( )
( )( )( )( )
=
=
=
...gp...gpgpc
gpgpc
gpc
111i1iiii
11222
111
( 3.3)
Biii de propagare pi (i = 1 ... N) i generare g i (i = 1 ... N) pot fi calculai nparalel utiliznd N pori AND i N pori OR cu dou intrri. Dac toi biii detransport ci (i = 1 ... N-1) sunt cunoscui, termenii si (i = 1 ... N) se pot calcula n doardoi pai. Dac TA(N) este timpul necesar pentru adunarea a dou numere binare, iarTC(N-1) este timpul de calcul pentru N-1 bii de transport, atunci
3)1N(T)N(T CA += ( 3.4)
Din (3.4) se observ c n adunarea a dou numere binare, valoarea timpuluide calcul este puternic influenat de operaia de obinere a biilor de transport. ncontinuare se propune un algoritm paralel pentru calculul acestor bii (fig. 3.1).
Fie r 1 i q 1 astfel nct N = rq. Pentru i = 1 ... r se definesc urmtoriitermeni
( )( )
=
=
==
=
++
+
+
iii
1q)1i(1q)1i(iqiqi
r1iri
1q)1i(iqi
EDF
...qp...qpE
1D,P...PD
p...pP
( 3.5)
Fie N = 8, r = 4 i q = 2. Atunci
4441333222111
7788455663
3344211221
4433422341
784563342121
EEDFEDFEDFEDF
))gp(g(pE))gp(g(pE
))gp(g(pE))gp(g(pE
1DPDPPDPPPD
ppPppPppPppP
=====
==
==
====
====
( 3.6)
Din (3.6), prin asociativitate, comutativitate i distributivitate, rezult
12348 FFFFc = ( 3.7)
i pentru cazul general
11rrN FFFc = L ( 3.8)
7/29/2019 Arhitecturi Paralele de Calcul
32/75
32
n cazul algoritmului clasic de adunare, calculul biilor de transport se face nN pai (TC(N)=N). Utiliznd algoritmul lui Brent (fig. 3.1) reiese c timpul necesarobinerii bitului de transport final va fi [Lak90]:
{ }qlog)1r(log),q(Tmaxrlog1)N(T 22C2C +++ ( 3.9)
unde ( )
2/1
2C Nlog2kcu,2
)1k(k)N(T
+ ( 3.10)
Din (3.4), (3.9) i (3.10) rezult c adunarea a dou numere binare de lungimeN se efectueaz n aproximativ log2N pai utiliznd algoritmul lui Brent i n N paiutiliznd algoritmul clasic.
Pentru cazul prezentat anterior (N =8, r = 4, q = 2) calculul biilor de transportse va face n 8 pai utiliznd algoritmul clasic i n maxim 6 pai utiliznd algoritmullui Brent. Performanele obinute nu sunt spectaculoase, ns odat cu creterea
numrului de bii ai valorilor a i b acestea vor crete considerabil.
aN aN-1 a1 N N-1 1. . . . . .
Calculeaza p si g , i = 1, . . . , N
intr-un singur pas, utilizand 2N portii i
p , g , i = 1, . . . , Ni i p , i = 1, . . . , Ni
Calculeaza E, i = 1, . . . , r
in T (q) pasi,
utilizand s(q) porti
i
C
Calculeaza P , i = 1, . . . , r
in log q pasi,
utilizand r(q-1) porti
i
2
P , i = 1, . . . , ri
Calculeaza D, i = 1, . . . , r
in log (r-1) pasi,
util izand (r/2) porti
i
2
log r2
Calculeaza F, i = 1, . . . , r
intr-un singur pas, utilizand r portii
D , i = 1, . . . , ri
E , i = 1, . . . , ri
Calculeaza C
in log r pasi, utilizand (r-1) portiN
2
CN
Fig. 3.1. Schem de calcul paralel al bitului de transport.
7/29/2019 Arhitecturi Paralele de Calcul
33/75
33
3.2. Analiza algoritmilor de nmulire paralel
Fie a = aN aN-1 ... a2 a1 i b = bNbN-1 ... b2b1 dou numere ntregi reprezentate nbinar ce vor fi adunate. Fie s = (a b) mod 2N unde s = sN sN-1 ... s2 s1 este produsul celor
dou numere.
3.2.1. Algoritmul clasic de nmulire varianta paralel
Fie a = 1101 i b=1101. Se calculeaz n paralel produsele pariale x1 ... x4 pebaza operaiei logice AND
x1 = 0001101x2 = 0000000x3 = 0110100
x4 = 1101000
Se adun dou ct dou valorile astfel obinute executnd calculele n paralel
x1 + x2 = 00001101x3 + x4 = 10011100
n final se obine s = x1 + x2 + x3 + x4 = 10101001 care reprezint produsulnumerelor a i b (fig. 3.2). Timpul de execuie al acestui algoritm va fi (log2N)2 (spredeosebire de algoritmul clasic care se efectueaz n N2 pai).
/* Fiind date numerele a = aN aN-1 ... a2 a1 i b = bN bN-1 ... b2 b1, s segseasc produsul s = ab = s2N s2N-1 ... s2 s1 */Pasul 1:Se calculeaz cele N produse pariale x1, x2, ..., xN de lungime 2N-1fiecare.
x1 = 0 0 0 ... 0 aN^b1 aN-1^b1 ... a2^b1 a1^b1x2 = 0 0 0 ... aN^b2 aN-1^b2 aN-2^b2 ... a1^b2 0
... ... ... ... ... ... ... ... ... ...
xN = aN^bN aN-1^bN ... ... ... ... a1^bN ... 0 0
unde ai^bj reprezint operaia AND logicPasul 2:Se adun n paralel cele N produse pariale obinute n pasul 1.
Fig. 3.2. Algoritmul clasic de nmulire varianta paralel
7/29/2019 Arhitecturi Paralele de Calcul
34/75
34
3.2.2. Algoritmul de nmulire Ofman - Wallace
Ofman i Wallace au creat un algoritm paralel rapid de nmulire a dounumere ntregi pe N bii cu timp de execuie log2N. Algoritmul se bazeaz pe
modificarea (mbuntirea) pasului 2 din algoritmul prezentat anterior (fig. 3.2).Fie x, y, z numere ntregi pe N bii. Exist dou numere ntregi pe N + 1 biiastfel nct
bazyx +=++ ( 3.11)
unde a i b pot fi obinute n paralel din x, y, z n trei pai.Fie a = aN-1 aN ... a2 a1 i b = bN-1 bN ... b2 b1. Se definesc aN+1 = 0 i b1 = 0, iar
pentru 1 i N
1iiiii b2azyx ++=++ ( 3.12)
Operaiile + i reprezint adunarea i respectiv nmulirea celor doi termeni.nmulind cu 2i-1 i apoi adunnd se obine relaia (3.11). Termenii a i i bi auurmtoarea form
iiiii1i
iiii
z)yx()yx(b
zyxa
=
=
+
( 3.13)
iar calculul acestora se poate face n paralel utiliznd schema din figura 3.3.
+
+
zi xi yi zi xi yi
ai
bi+1
Fig. 3.3. Circuit pentru calculul termenilor ai i bi+1
Exemplu:
Fie x = 1011, y = 0111, z = 1101 trei produse pariale obinute n pasul 1 alalgoritmului clasic de nmulire (se observ uor c a = 00001 i b = 11110). Forma
7/29/2019 Arhitecturi Paralele de Calcul
35/75
35
acestor produse este x0,1, x0,2, ..., x0,N0 (N0 = N), unde x0,i = xi sunt biii de pe poziia(2N-1) pentru fiecare produs parial.
n prima etap se mparte grupul de produse pariale n
3
N0 grupuri de cte
trei ntregi fiecare. Aplicnd metoda Ofman - Wallace pentru fiecare grup se obin
3
N2 0 ntregi de 2N bii lungime (practic a i b). Prin adunarea (cu alinierea fa de
bitul cel mai puin semnificativ) restului de produse pariale (
3
N3N 00 ) se obin
=
+
=
3
NN
3
N3N
3
N2N 00
00
01 ( 3.14)
ntregi pe 2N bii.
Reiternd, se formeaz
3
N1 grupuri de trei ntregi avnd lungimea de 2N
bii i se obin
=
+
=
3
NN
3
N3N
3
N2N 11
11
12 ( 3.15)
ntregi avnd 2N+1 bii. Dup i pai rezult
=
3
N
NN
1i
1ii ( 3.16)
ntregi de lungime 2N+1-i bii. Algoritmul se repet pn cnd Ni < 3.Deoarece aceste valori ntregi se obin n paralel pe baza circuitului din fig. 3.3,
rezult c n final se va efectua o singur adunare a dou valori pe 2n-1+i bii, care vanecesita log2N pai (spre deosebire de algoritmul paralel anterior care necesita(log2N)2 pai).
3.2.3. Algoritmul de nmulire Karatsuba Ofman (divide et impera)
Se bazeaz pe strategia divide et impera i permite nmulirea a dou valorintregi de N bii, unde N = 2n. Numerele ntregi a i b se pot rescrie astfel
+=
+=
0
2/N
1
0
2/N
1
B2Bb
A2Aa( 3.17)
7/29/2019 Arhitecturi Paralele de Calcul
36/75
36
unde Ai i Bi, i = 0 sunt numere ntregi de2
Nbii. A0 este restul i A1 este ctul
mpririi lui a la 2N/2 (n mod identic, B0 i B1 reprezint restul, respectiv ctul,mpririi lui b la 2N/2). Se definesc r0, r1 i r2 astfel nct
=
++==
112
01011
000
BAr
)BB()AA(rBAr
( 3.18)
Produsul numerelor a i b va fi
0
2/N
021
N
2 r2)rrr(2rba ++= ( 3.19)
i este obinut n urma a trei nmuliri (recursive) a ntregilor de2
Nbii i un total de
6 operaii adunare/scdere a unor termeni de cel mult 2N bii. nmulirile cu 2N i 2N/2implic doar operaii de deplasare efectuate pe o singur perioad de tact. Rezult c
n operaia de nmulire doar operaiile de adunare/scdere consum timp, iar acesttimp va fi (log2N)2.
Metoda Karatsuba Ofman este elegant i se poate implementa recursiv, nsnecesit ca timp de execuie (log2N)2 pai. Acest timp de execuie reprezint o valoarefoarte mare n comparaie cu metoda Ofman Wallace bazat pe modificareaalgoritmului clasic (log2N pai).
7/29/2019 Arhitecturi Paralele de Calcul
37/75
37
4. STRATEGII PENTRU CREAREA PROGRAMELOR PARALELE
4.1. Scopurile procesului de paralelizare
Scopul major al utilizrii mainilor paralele este de a mbunti performanaprin obinere de accelerare fa de cea mai bun performan obinut pe un sistemuniprocesor.
Fiecare din paii utilizai n crearea programelor paralele are un rol importantn atingerea complet a acestui scop i fiecare pas are propriul subset de scopuri carevizeaz performana.
Crearea unui program efectiv paralel necesit evaluarea costului i aperformanei. n plus, fa de costul n bani al mainii respective, trebuie luate nconsiderare cerinele de resurse ale programului pe acea arhitectur (de exemplumemoria utilizat) i efortul necesar dezvoltrii unui program satisfctor. Dei
costurile i impactul acestora sunt deseori dificil de cuantificat, ele sunt foarteimportante i de multe ori performana sistemului este sacrificat pentru reducereaacestora.
Proiectanii de algoritmi trebuie s se concentreze pe soluiile performantecare solicit resurse minimale i care nu necesit eforturi de programare excesive.
Proiectanii de arhitecturi de calcul trebuie s ncerce s proiecteze sisteme denalt performan care s faciliteze utilizarea eficient a resurselor de ctrealgoritmi, precum i reducerea efortului de programare i toate acestea la un costsczut. O arhitectur n care performana crete gradual cu creterea efortului deprogramare poate fi preferat uneia care este capabil s furnizeze performan mai
bun, dar care necesit eforturi excesive de programare pentru a obine performaneacceptabile.
4.2. Pai n procesul de paralelizare
Un task este definit ca fiind o sarcin de lucru dintr-un proces. task-ulreprezint cea mai mic unitate de concuren care poate fi exploatat de ctre unprogram. Codul unui task poate fi executat doar de ctre un singur procesor, iarconcurena este exploatat doar prin task-uri.
Un proces este o entitate abstract care execut task-uri. Programele paralele
sunt compuse din procese comunicante (cooperante), fiecare dintre ele executnd unsubset de task-uri din program.Task-urile sunt asignate (atribuite) proceselor printr-un mecanism de atribuire.
Procesele trebuie s comunice i s se sincronizeze cu alte procese, pentru a-i puteaexecuta propriile task-uri. n final, calea prin care procesele execut propriul task esteca ele s ruleze pe procesoarele fizice existente n maina de calcul.
Diferena dintre procese i procesoare (din punct de vedere al paralelismului)const n faptul c n timp ce procesoarele sunt resurse fizice, procesele furnizeaz o
7/29/2019 Arhitecturi Paralele de Calcul
38/75
38
metod convenabil de abstractizare sau virtualizare a unui multiprocesor: iniialprogramele paralele sunt scrise avnd n vedere procesele i nu procesoarele;maparea proceselor pe procesoare revine pasului urmtor.
Numrul de procese dintr-un program nu va fi identic cu numrulprocesoarelor disponibile programului. Dac exist mai multe procese, ele sunt
multiplexate pe procesoarele disponibile. De asemenea, unele procesoare vor rmneneutilizate dac numrul proceselor din program este mai mic dect al procesoarelor.Se definesc [Cul99] patru pai n procesul de creare a programelor paralele
(fig. 4.1):
1. Decompoziia calculelor n task-uri2. Atribuirea de task-uri n procese3. Coordonarea acceselor la date i asigurarea comunicrii i
sincronizrii dintre procese4. Maparea (legarea) proceselor de procesoare
DECOMPOZITIE
ATRIB
UIRE
p0 p1
p2 p3
COORD
ONARE
p0 p1
p2 p3
MAPARE
P0 P1
P2 P3
Calculsecvential
Task-uri Procese Programparalel
Procesoare
Partitionare
Fig. 4.1. Paii parcuri n procesul de paralelizare.
Etapele de decompoziie i atribuire fac parte din procesul de partiionaredeoarece n aceast etap se divid calculele efectuate de ctre un program n procesecooperante. n faza de coordonare se gestioneaz accesele la date, comunicaiile isincronizrile ntre procese. n faza de mapare se face alocarea proceselor peprocesoarele existente n sistem.
7/29/2019 Arhitecturi Paralele de Calcul
39/75
39
4.2.1. Decompoziia
Reprezint divizarea calculelor ntr-o colecie de task-uri. n general, task-uriledevin disponibile dinamic, pe msur ce programul se execut. Numrul de task-uridisponibile la un moment dat variaz pe timpul execuiei programului. Acest numr
ne furnizeaz limita superioar a numrului de procese (respectiv procesoare) carepot fi utilizate efectiv la acel moment de timp.De aceea, scopul major n decompoziia datelor este de a extrage (a etala)
suficient concuren pentru a pstra procesele ocupate ct mai mult timp. ns dactimpul ocupat de task-urile de coordonare tinde s devin comparabil cu timpulocupat de task-urile utile se va obine un randament sczut pentru sistemul de calcul.
Gradul sczut de concuren reprezint o limitare important a accelerriiobinute prin paralelism. ntr-o problem fundamental nu conteaz doar concurenadisponibil ci i cantitatea de concuren care poate fi obinut prin paralelism.
Impactul concurenei disponibile este codificat n legea lui Amdahl (ec. 1.21).
Dac anumite secvene din execuia programului nu dein concuren suficient (nfuncie de numrul procesoarelor utilizate), atunci unele procesoare vor fi neutilizateo fraciune din timpul de execuie, iar accelerarea sistemului va fi neoptimal.
4.2.2. Atribuirea
Atribuirea este un mecanism prin care task-urile vor fi distribuite proceselor.Scopul atribuirii este de a echilibra ncrcarea proceselor, de a reduce
cantitatea de comunicaii interproces i de a reduce calculele suplimentare aprute(pe parcursul execuiei programului) pentru implementarea acestui mecanism.
Comunicaia interprocese este costisitoare, mai ales atunci cnd proceseleruleaz pe procesoare diferite, iar atribuirile pentru procesarea task-urilor pot generasuprancrcri la rulare.
Programele sunt structurate n faze, iar task-urile candidate pentrudecompoziie din cadrul unei faze sunt uor de identificat. O atribuire corect a task-urilor se poate face fie prin analiza codului, fie prin nelegerea aplicaiei la nivel nalt(pseudocod). Dac acest lucru nu se poate face, se vor aplica tehnici euristice.
Dac atribuirea este determinat complet de la nceputul programului sauimediat dup citirea i analiza intrrilor i dac nu se modific dup aceea, ea estedenumit static sau predeterminat. Atribuirea dinamic se face n timpul rulrii
programului, pentru a rezolva dezechilibrul ncrcrii procesoarelor.Decompoziia i atribuirea reprezint cele mai importante etape n procesul deparalelizare; ele sunt independente de arhitectura sistemului i de modelul deprogramare, iar costurile i complexitatea aplicaiilor influeneaz deciziile luate naceste etape.
Din punctul de vedere al arhitectului, se presupune c programele care vorrula pe main sunt partiionate rezonabil i nu se poate interveni dac calculele nusunt paralelizate destul , sau dac exist dezechilibre ntre procese.
7/29/2019 Arhitecturi Paralele de Calcul
40/75
40
Din punctul de vedere al programatorului, trebuie acionat independent (nsensul decompoziiei i atribuirii) de modelul de programare sau de arhitectur.
4.2.3. Coordonarea
Este pasul n care att arhitectura ct i modelul de programare joac rolurieseniale. Pentru a executa task-urile asignate, procesele au nevoie de mecanisme deidentificare i accesare a datelor, de a schimba date (de a comunica) cu alte procese ide a se sincroniza cu acestea. Coordonarea utilizeaz mecanismele disponibile pentrua atinge corect i eficient aceste scopuri.
Alegerile efectuate n coordonare sunt mai mult dependente de modelele deprogramare (i de modul n care primitivele modelului de programare suntsuportate) dect de alegerile efectuate n paii anteriori.
n acest pas se rezolv urmtoarele probleme:
organizarea structurilor de date; planificarea temporar a task-urilor n cadrul unui proces pentru aexploata localitatea datelor;
se alege modul de comunicare interproces: implicit sau explicit, dac seva face prin mesaje mici sau mari;
organizarea comunicaiei i sincronizrii ntre procesele rezultate dinatribuire.
Limbajul de programare este important deoarece acesta este pasul n careprogramul este scris, iar realizarea echilibrrii proceselor este puternic influenat de
mecanismele disponibile n limbaj i de costurile acestora.Scopurile principale n coordonare sunt:
reducerea costurilor de comunicaie i sincronizare; pstrarea localitii n referina datelor; planificarea task-urilor astfel nct toate celelalte task-uri de care depind
acestea s se fi executat deja; reducerea suprancrcrii aprute datorit managementului
paralelismului.
Sarcina proiectanilor de arhitecturi este de a pune la dispoziie primitivelenecesare care simplific partea de coordonare.
4.2.4. Maparea
Procesele cooperante care rezult n urma pailor anteriori constituie unprogram paralel complex. Maparea proceselor pe procesoare poate fi fcut de ctreprogram sau de ctre sistemul de operare.
7/29/2019 Arhitecturi Paralele de Calcul
41/75
41
n cazul cel mai simplu, procesoarele de pe main sunt partiionate nsubseturi i doar un singur program ruleaz la un moment dat pe un subset. Aceastmetod este deseori denumit partajarea spaiului. Programul poate legaprocesele de procesoare pentru a nu permite migrarea acestora n timpul execuiei;poate controla exact perechile procesor-proces pentru a asigura localitatea
comunicaiilor.Schemele de partajare a spaiului, mpreun cu mecanismele simple departajare a timpului sunt tipice deja n sistemele multiprocesor. La cealalt extrem,sistemul de operare poate alege dinamic ce proces va rula la un moment dat (fr apermite utilizatorului s intervin n mapare), pentru a gestiona n mod corectpartajarea resurselor i utilizarea acestora.
Fiecare procesor poate folosi un criteriu de planificare multiprogram pentru agestiona procese din acelai sau din programe diferite, iar procesele pot fi mutate dela procesor la procesor aa cum dicteaz planificatorul.
Sistemul de operare poate extinde criteriul de planificare pentru a include
caracteristici specifice multiprocesoarelor. De exemplu, se pot crea proceseplanificate s ruleze pe acelai procesor ct mai mult timp posibil, astfel nctprocesul poate reutiliza starea sa din cache-ul procesorului respectiv.
Majoritatea sistemelor de operare moderne se afl undeva ntre aceste douextreme: utilizatorul poate solicita sistemului s i pstreze anumite proprieti(drepturi de control i mapare), dar sistemul de operare este n msur de a modificamaparea dinamic pentru managementul eficient al resurselor mainii.
Maparea i managementul de utilizare a resurselor n sistemelemultiprogramate sunt domenii deschise cercetrii.
4.3. Paralelizarea calculelor i paralelizarea accesului la date
Metodele de paralelizare ale proceselor descrise anterior au fcut referire doarla calculele efectuate n program i nu la datele accesate. Datorit modelului deprogramare sau din consideraii de performan, trebuie s realizm decompoziia iatribuirea datelor pentru fiecare proces. n multe clase de probleme calculele i datelesunt att de strns legate ntre ele, nct decompoziia este dificil de realizat pentrufiecare n parte.
Mediile de programare permit programatorului s specifice decompoziia iatribuirea structurilor de date. Atribuirea calculelor se va face dup atribuirea
datelor.
4.4. Exemplu de paralelizare a unui program
Pentru paralelizarea unui program secvenial, programatorul trebuie sparcurg paii de decompoziie, atribuire i coordonare. Ultimul pas (maparea) va fiefectuat de ctre sistemul de operare.
7/29/2019 Arhitecturi Paralele de Calcul
42/75
42
Fie2x1
4)x(f
+= . Graficul funciei f(x) este prezentat n figura 4.2. Aria de sub
grafic reprezint valoarea .
x
y
4
00 1
1 + x2
4f(x) =
Fig. 4.2. Reprezentarea grafic a funciei2x1
4)x(f
+= .
n continuare se propune [Sun00] o metod simpl de calcul a valorii ,utiliznd un program secvenial i apoi un program paralel. Algoritmul se bazeazpe metoda dreptunghiurilor (fig. 4.3).
x
y
4
00 1
Fig. 4.3. Descompunerea ariei de sub f(x) prin regula dreptunghiului.
7/29/2019 Arhitecturi Paralele de Calcul
43/75
43
Din figura 4.3 rezult c =1
0
)x(f . Aria de sub grafic poate fi calculat astfel:
=
=n
1i
i )x(fwidthS ( 4.1)
unden
1width = , iar )5,0i(widthx i = .
Programul secvenial pentru calculul valorii , poate fi implementat dupurmtorul algoritm:
float f(int x){
return 4 / (1 + x * x);}
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -cin >> n;width = 1.0 / n;sum = 0;pi = 0;
for(i = 1; i n; i++){
xi = width * (i 0.5);sum = sum + f(xi);
}
pi = width * sum;cout
7/29/2019 Arhitecturi Paralele de Calcul
44/75
44
x
y
4
00 1
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
Fig. 4.4. Asignarea dretunghiurilor.
Coordonarea se va face prin intermediul procesorului principal, princolectarea rezultatelor de la celelalte procesoare implicate n execuia programuluiparalel. n continuare se prezint o variant paralel de calcul a valorii .
float f(int x){
return 4 / (1 + x * x);}
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
cin>> n;width = 1.0 / n;
sum = 0;pi = 0;
for(i = 1; i n; i++){for(j = 0; j < nrproc; j++) do in parallel
{P[j]:xi = width * (i 0.5);sum(j) = sum(j) + f(xi);}
}for(k = 0; k < nrproc; k++){
P[0]: sum = sum + sum(k);}pi = width * sum;cout
7/29/2019 Arhitecturi Paralele de Calcul
45/75
45
5. ALGORITMI PARALELI NUMERICI
5.1. Adunarea a N numere
Algoritmul secvenial pentru adunarea a N numere are funcia complexitatede timp O(N), ceea ce reprezint valoarea optim.
sum = 0;for(i=0;i
7/29/2019 Arhitecturi Paralele de Calcul
46/75
46
Algoritmul de adunare prezentat anterior se refer doar la faza global. Dacse consider i faza local, procesoarele vor aduna local L = N/p valori, cu algoritmulsecvenial n O(L).
Timpul total de calcul va fi O(L) + O(log2p) = O(L + log2p). Dac N este multmai mare dect p, atunci
(L)Op)logO(L(N)T HL2p =+= ( 5.4)
iar accelerarea devine
+=
+=
plogp
N
NO
)plogL(O
)N(O)N(S
22
p ( 5.5)
iar pentru N >> p se obine
)p(O)N(S HLp = ( 5.6)
De aici rezult c Ep(N) = OHL(1) i imediat se observ c problema estecomplet paralelizabil.
Raportul N/p (L) va trebui ales de aa manier nct fazele local i global saib aceeai complexitate.
)N(T)N(T
)N(T)N(S
global
p
local
p
1
p += ( 5.7)
Cei doi termeni de la numitor sunt asimptotic egali. Prin procesare de tippipeline, se obine
)N(T
)N(T)N(S
local
p
1
p= ( 5.8)
Accelerarea ideal se obine cnd L = O(log2p), adic N = O(plog2p). Se vorlansa n execuie noi instane ale problemei pe fiecare pas, astfel nct dei fiecare
instan necesit timpul O(log2p), arborele poate rezolva probleme de nsumare la orat de una la fiecare log2p uniti de timp.
5.2. Calculul sumelor pariale (prefixul paralel)
Problema calculrii sumelor pariale reprezint o generalizare a algoritmuluide nsumare.
7/29/2019 Arhitecturi Paralele de Calcul
47/75
47
Fiind date N valori, a1, a2, ..., aN se dorete calcularea sumelor S1, S2, ..., SN,
unde =
=i
1j
ji aS .
Algoritmul secvenial al acestei probleme este:
for(i = 0; i n -1; i++){
sum[i] = 0;for(j = 0; j i; j++) sum[i] = sum[i] + a[j];
}
ntr-un sistem EREW cu p procesoare aceste sume se calculeaz n timpulO(log2n), prin exploatarea asociativitii i meninerii ocupate a ct mai multorprocesoare. Algoritmul este prezentat n continuare.
void ALLSUMS(a1, a2, ..., aN){
for(j = 0; j log2p -1; j++){
for(i = 2j + 1; j p; j++) do in parallel{
P[i]:(1) obine a[i - 2j] de la P[i 2j] prin memoria comun;(2) nlocuiete a[i] cu a[i - 2j] + a[i];
}}
}
Operaia de adunare poate fi nlocuit de orice alt operaie asociativ:nmulire, scdere, operaie boolean etc.
Pentru produs putem rezolva problema prin metoda divide et impera. Senoteaz cu PR(i,j) produsul a1 a2 ... aj. Trebuie s se calculeze PR(1,k) pentru 1 k N. Se presupune c N = 2n i c se poate rezolva problema prefixului paralelpentru N/2 elemente. Algoritmul const n mprirea la jumtate a mulimii deintrare i rezolvarea fiecrei pri prin inducie.
Astfel, se obin PR(l,k) i PR(N/2+1, N/2+k) pentru 1 k N/2. ValorilePR(1,m), cu N/2 < m N, se pot obine prin calculul PR(l,N/2) PR(N/2+1, m).Datele de intrare se mpart n dou mulimi disjuncte, la fiecare apel recursiv
al algoritmului. Dac sunt N procesoare i problema are dimensiunea N, atunci vomavea dou subprobleme de dimensiune N/2. Combinarea va consuma N/2 pai, cepot fi executai n paralel pe un model CREW, deoarece toate procesoarele folosesca[middle]. Mai multe procesoare citesc simultan a[middle] i scriu rezultatele n locaiidiferite.
7/29/2019 Arhitecturi Paralele de Calcul
48/75
48
Astfel, obinem
)N(logO)p,N(T 2= ( 5.9)i
)
Nlog
1(OE
2
= ( 5.10)
deoarece algoritmul secvenial se execut n O(N) pai. Datorit celui de-al doileaapel recursiv, numrul total de pai este O(Nlog2N). Mai jos este prezentat algoritmulde calcul al prefixului paralel.
void ParallelPrefix(left, right){
if(right - left) = 1{
a[right] = a[left] a[right];}else{
middle = (left + right - 1)/2;do in parallel
{ParallelPrefix(left, middle); //atribuie lui P[1] la P[N/2]ParallelPrefix(middle + 1, right); //atribuie lui P[N/2+1] la P[N]
}for(i = middle + 1; i right; i++) do in parallel{
a[i] = a[middle] a[i];
}}}
5.3. Operaii cu matrice
Matricele sunt des utilizate n aplicaii, indiferent de caracterul acestora.Prelucrarea matricelor poate fi paralelizat prin descompunerea domeniului. Existmai multe posibiliti (fig. 5.2):
Descompunerea are loc pe linii sau pe coloane, fiecare procesorprimind una sau mai multe linii, sau coloane. La rndul ei, aceastapoate fi pe bloc, cnd liniile sau coloanele alocate unui procesor suntvecine, sau ciclic, cnd alocarea se face cu o funcie modulo numrulde procesoare.
Descompunerea pe submatrice, ptratice sau nu, cte una alocatfiecrui procesor.
7/29/2019 Arhitecturi Paralele de Calcul
49/75
49
P0
P1
P2
P3
P4
P6
P8
P9
P0 P1 P3 P4 P5
P0 P1
P3
Fig. 5.2. Descompunerea unei matrice.
5.3.1. nmulirea matricelor
Algoritmul secvenial de nmulire a matricelor este prezentat n continuare.
for(i = 0; i < N; i++){
for(j = 0; j < N; j++){
c[i][j] = 0;for(k = 0; k < N; k++) c[i][j] = c[i][j] + a[j][k] b[k][j];
}}
Acest algoritm are complexitatea O(N3). Evident, el poate fi paralelizat n maimulte moduri. Fiecare iteraie a celor dou bucle exterioare este independent, iarfiecare iteraie a buclei interioare poate fi executat separat. n principiu, toate cele N;
nmuliri pot fi executate simultan, ca i cele N2 adunri. Cu N3 procesoare,complexitatea funciei de timp este
N)O(logN)logO(1 22 =+ ( 5.11)
ceea ce ar reprezenta limita inferioar a timpului de execuie pentru acest algoritmparalel. Din (5.11) rezult expresia funciei de cost
NlogN)N(C 233 = ( 5.12)
care ne arat c aceasta nu este optimal.n cazul unei arhitecturi de tip hipercub, pe care s-ar putea implementa
aceast soluie se va consuma un timp important pentru comunicaii. n faza deiniializare ar trebui distribuite 2N2 date la N3 procesoare. Mai mult, elementelematricelor vor avea copii multiple n sistem.
7/29/2019 Arhitecturi Paralele de Calcul
50/75
50
Atunci cnd numrul procesoarelor este relativ mic (sau mai mic dect N), seprefer descompunerea pe blocuri sau submatrice [Gri00].
A B C=
Fig. 5.3. nmulirea a dou matrice folosind mprirea pe blocuri.
Dac matricele A i B sunt ptratice i sunt mprite n M blocuri (n fapt, totmatrice, dar de dimensiuni mai mici) a cte N/M N/M elemente (sau s s, unde s =N/M), algoritmul poate fi rearanjat n urmtoarea form:
for(p = 0; p < M; p++){
for(q = 0; q < M; q++){
Cp,q = 0;for(r = 0; r < s; r++) Cp,q = Cp,q + Ap,r Br,q;
}}
De data aceasta bucla interioar const n operaii cu matrice. Dac p = M 2,fiecare procesor va evalua o iteraie a buclei interioare. Complexitatea calculelorefectuate de un procesor este O(N), iar numrul mesajelor este redus fa de situaiaunui sistem cu N3 procesoare. ns, colectarea rezultatelor va avea complexitateaO(N2).
n figura 5.4 se prezint operaia de nmulire a dou matrice ptratice cudivizarea n patru submatrice.
A B C=
A11 A12
A22A21
B11 B12
B22B21
C11 C12
C22C21
Fig. 5.4. nmulirea matricelor folosind mprirea n submatrice.
7/29/2019 Arhitecturi Paralele de Calcul
51/75
51
Fiecare submatrice a lui C se obine prin evaluarea unei ecuaii matriceale deforma
j22ij11ij,i BABAC += ( 5.13)
unde 1 i, j 2.Se pot folosi patru procesoare, cte unul pentru fiecare submatrice rezultat, fie
opt procesoare care lucreaz n doi pai. n primul pas, procesoarele executnmulirile, dup care, n pasul doi, patru procesoare calculeaz sumele.
Acest algoritm poate fi realizat i sub forma unei proceduri recursive, fiecaresubmatrice fiind mprit n patru, la fiecare apel. Apelurile vor continua pn la ungrad al matricelor care asigur o granularitate acceptabil.
Exist i alte soluii paralele pentru nmulirea matricelor, bazate pe utilizareasistemelor cu topologie de tip torus [Gri00]. Cannon a produs un sistem cu topologiede tip torus, la care fiecare procesor memoreaz un element, sau submatrice dupcaz, din fiecare matrice operand. Prin deplasri circulare, factorii produsului din
bucla cea mai interioar vor fi adui n acelai procesor. Toate procesoarele execut
produsele, dup care are loc, sincron, o nou deplasare a tuturor elementelor.Operaia se repet de un numr de ori egal cu o dimensiune a torus - ului.
5.3.2. Rezolvarea sistemelor de ecuaii liniare. Eliminarea gaussian
Fiind dat sistemul de ecuaii liniare (5.14), se cere s se determinenecunoscutele xi, cu 0 i n-1.
=++++
=++++=++++
=
=++++
00001102n2n01n1n0
10011112n2n11n1n1
20021122n2n21n1n2
1n001n111n2n2n1n1n1n1n
bx,ax,ax,ax,a
bx,ax,ax,ax,a
bx,ax,ax,ax,a
bx,ax,ax,ax,a
LLLL
LLLL
LLLL
LLLLLLLLLLLLLLLLLLLLLLL
L
( 5.14)
Forma matricial a sistemului este Ax = b, unde A este o matrice N x N, iar beste o matrice N x 1.
Ideea acestei metode este de a transforma sistemul iniial de ecuaii ntr-unulde form triunghiular (superioar, sau inferioar), la care coeficienii de pediagonala principal au valoarea 1.
Metoda se bazeaz pe proprietatea sistemelor de a fi echivalente cu celeproduse prin nlocuirea unui linii a matricei A cu suma dintre ea i o alt linie,nmulit cu o constant. Alegerea acestei constante este astfel fcut nctcoeficientul unei necunoscute s devin nul i astfel, treptat, s se elimine toi factoriide sub, sau de deasupra diagonalei principale. Se ncepe cu prima linie i se continupn la ultima (fig. 5.5).
7/29/2019 Arhitecturi Paralele de Calcul
52/75
52
10...0
10 10 0 10..........10..........00..........0
10 10 0 10............10..............010....................01
Fig. 5.5. Procesul de eliminarea gaussian.
Cnd s-a ajuns la linia i, se nlocuiete fiecare liniej de sub ea cu
+=
i,i
i,j
a
a)ilinia()jlinia()jlinia( , ( 5.15)
ceea ce are ca efect anularea tuturor elementelor de pe coloana i, aflate sub linia i. Se
observ c
0a
aaaa
i,i
i,j
i,ii,ji,j =
+= ( 5.16)
Dac aj,i este nul sau apropiat ca valoare de zero, mprirea nu mai poate avealoc. n aceast situaie, se folosete pivotarea parial, care const n schimbareapoziiilor liniei i cu linia de sub ea care are valoarea cea mai mare pe coloana i, pestetoate elementele de pe coloana i, situate sub linia i. Verificarea coeficientului ai,itrebuie s se fac pentru fiecare linie i nu poate fi executat nainte de a ncepeeliminarea gaussian.
Algoritmul secvenial (O(N3)) este prezentat n continuare.
for(i = 0; i < N -1; i++){
for(j = i +1; j < N; j++){
c = a[j][i]/a[i][i];for(k = i; k < N; k++) a[j][k] = a[j][k] a[i][k] c;b[j] = b[j] b[i] c;
}}
Dac analizm secvena anterioar de instruciuni, observm imediatposibilitile de paralelizare. Fiecare indice j al buclei interioare poate fi alocat unuiprocesor, dar, n acelai timp, modificarea coeficienilor din linia j poate fi realizatindependent una de alta, ceea ce reprezint un nivel dublu de paralelism, exploatat
ntr-adevr de unii algoritmi paraleli.
7/29/2019 Arhitecturi Paralele de Calcul
53/75
53
Dac presupunem c p = N, fiecare procesor va primi o linie: procesorul Pi vaprimi elementele a[i][j], unde 0 j N. La nceput, procesorul P0 va trimiteelementele liniei sale tuturor celorlalte procesoare (broadcasting). Apoi, fiecareprocesor calculeaz constanta c i modific coeficienii liniei sale. Procedura se repetcu P1, P2, ..., PN-2. Elementele trimise de Pi la procesoarele Pi+1, Pi+2, ... sunt a[i][i+1],
a[i][i+2], ..., a[i][n -1].
7/29/2019 Arhitecturi Paralele de Calcul
54/75
54
6. ALGORITMI PARALELI NENUMERICI
Pe lng operaiile numerice, calculatoarele efectueaz un volum
impresionant de operaii nenumerice, cum ar fi sortri, cutri, interclasri, utilizaten aplicaii multimedia, inteligen artificial, compilatoare etc.
6.1. Exploatarea static a paralelismului la nivelul instruciunilor
Reorganizarea codului (scheduling) reprezint procesul de aranjare ainstruciunilor din cadrul unui program obiect astfel nct acesta s se execute ntr-unmod cvasioptimal din punct de vedere al timpului de procesare. Procesul dereorganizare a instruciunilor determin creterea probabilitii ca procesorul saduc simultan din cache-ul de instruciuni mai multe instruciuni independente
[Vin00a].Procesul de reorganizare implic utilizarea unor algoritmi de analiz acodului extrem de compleci, bazai pe tehnici euristice.
Studiul acestor algoritmi prin prisma procesrii paralele, poate conduce lacrearea de compilatoare extrem de eficiente i performante.
6.1.1. Partiionarea unui program n basic-block"-uri
Algoritmul de partiionare const principial n urmtorii 2 pai:
1) Determinarea setului de lideri n cadrul programului. Se numete liderprima instruciune dintr-un program, instruciunea destinaie a oricrei instruciunide branch sau orice instruciune urmtoare unei instruciuni de branch.
2) Partiionarea programului n uniti secveniale i construirea grafului decontrol. Fiecare unitate secvenial conine un singur lider i toate instruciunile de laacest lider pn la urmtorul, exclusiv. Se determin predecesorii imediai fa de ounitate secvenial de program. Poate fi un predecesor imediat al unei unitisecveniale date orice unitate secvenial care se poate executa naintea unitii date.Se determin succesorii unei uniti secveniale de program. Se numete succesor alunei uniti secveniale de program orice unitate secvenial de program care poate
s se execute dup execuia celei curente.Un exemplu de partiionare a unui program n basic-block"-uri (i graful de
control aferent) este reprezentat n figura 6.1.
7/29/2019 Arhitecturi Paralele de Calcul
55/75
55
A;B;DO{
D;E;
IF (F){ G;H;
}ELSE {
I;}J;K;L;} WHILE (C);
Fig. 6.1. Partiionarea unui program n basic-block uri [Vin00a].
I1: ADD R1,R11,R12I2: ADD R1,R1,R13I3: SLL R2,R3,#4 ; R2R3 deplasat logic la stnga cu 4 poziii binareI4: AND R2,R1,R2I5: ADD R1,R14,R15I6: ADD R1,R1,R16
I7: ADD R1,R1,#6I8: LD R1,(R1)I9: LD R4,(R4)
I10: ADD R1,R4,R1I11: OR R1,R1,R2I12: ST R1,(R4)
Dup cum se va vedea, n stabilirea unei secvene reorganizate de program nvederea unei procesri cvasioptimale pe un procesor superscalar sau VLIW, grafuldependenelor de date aferent unei uniti secveniale de program se va dovedi
deosebit de util. Un arc n acest graf semnific o dependen RAW ntre cele 2 stri.Instruciunile care utilizeaz date din afara unitii secveniale de program se vorplasa n vrful grafului astfel nct n ele nu va intra nici un arc. Pentru o instruciunedat se caut n jos proxima dependen RAW. Cu aceste reguli simple, grafuldependenelor de date corespunztor secvenei de program anterioare este prezentatmai jos (fig. 6.2).
7/29/2019 Arhitecturi Paralele de Calcul
56/75
56
Fig. 6.2. Graful dependenelor de date asociat.
n stnga arcului este scris latena operaiei respective. n dreapta arcului estescris latena maxim a drumului msurat dintr-un vrf al arcului pn n starearespectiv. Graful dependenelor specific deci relaii de ordine ntre instruciuniabsolut necesare execuiei corecte a programului dat.
6.1.2. Graful precedenelor
Se obine pe baza grafului dependenelor de date n baza faptului c exist
cazuri n care acesta poate s nu cuprind toate precedenele necesare unei corectereorganizri. Altfel spus, acest graf nu pune n eviden relaiile de preceden strict
n lansarea n execuie, impuse de ctre dependenele de tip WAR respectiv WAWntre instruciuni.
6.1.3. Conceptul cii critice
Calea critic a grafului dependenelor de date o reprezint drumul cu latenmaxim. Conceptul cii critice este important deoarece el indic faptul c dupscheduling, profitnd la maxim de paralelismul ntre instruciuni, programul se va
putea executa n minimum 8 cicli, adic ntr-un timp egal cu latena cii critice. Prinstrategia sa, scheduler-ul va trebui ca n fiecare ciclu, pe ct posibil, s execute cte oinstruciune din calea critic ncercnd simultan s suprapun peste aceastinstruciune i alte instruciuni independente din program.
ntr-un procesor ipotetic avnd resurse infinite, scheduler-ul optim ar trebuipur i simplu s urmeze calea critic, suprapunnd peste operaiile de aici operaiidin alte ci. n cazul apariiei unui hazard WAW sau WAR ntre instruciuni trebuieredenumite registrele implicate.
7/29/2019 Arhitecturi Paralele de Calcul
57/75
57
O reorganizare optim ar nsemna s se simuleze execuia tuturor variantelorposibile de programe reorganizate i s se msoare ratele de procesare aferente,alegndu-se varianta de program cu rata cea mai mare. Pentru programe mari acestdeziderat ar implica uneori sptmni sau chiar ani de procesare devenind deciprohibit. n practic se prefer algoritmi euristici bazai pe graful dependenelor, care
dau rezultate apropiate de cele optimale, n schimb necesit timpi de execuieacceptabili. Aadar, problema optimalitii teoretice a scheduling-ului nu se pune dincauz de probleme de timp. n plus algoritmii euristici utilizai n practic daurezultate bune.
6.1.4. Algoritmul LIST SCHEDULING" (LS)
Este unul dintre cei mai reprezentativi algoritmi n acest sens, fapt pentru careva fi prezentat pe scurt. Timpul de execuie este rezonabil ntruct algoritmul seexecut ntr-o singur trecere prin graful dependenelor, genernd n majoritateacazurilor reorganizri optimale.
Algoritmul LS parcurge graful dependenelor asociat unitii secveniale deprogram de jos n sus. n fiecare pas se ncearc lansarea n execuie a instruciunilordisponibile. Dup ce aceste instruciuni au fost puse n execuie, instruciunileprecedente devin disponibile spre a fi lansate n pasul urmtor. Fiecrei instruciuni ise ataeaz un grad de prioritate egal cu latena cii instruciunii. Dac apare unconflict la resurse hardware comune ntre 2 sau mai multe instruciuni, are prioritateinstruciunea cu un grad de prioritate mai mare. Preciznd c iniial se seteaz uncontor de cicli la o valoare maxim, paii algoritmului sunt urmtorii:
1) Instruciunea cea mai prioritar dintre instruciunile disponibile n setul
curent este lansat n execuie dac nu necesit o resurs ocupat n acest ciclu.2) Dac o instruciune a fost pus n execuie n pasul 1, resursele utilizate de
aceasta vor fi setate ca fiind ocupate pentru un numr de cicli egali cu latenainstruciunii. Pentru exemplul nostru se va considera latena instruciunilor LOADde 2 cicli, iar latena celorlalte instruciuni de un ciclu.
3) Dac instruciunea a fost lansat n execuie n pasul 1 ea va fi tears dinlista instruciunilor disponibile n acel ciclu. Dac instruciunea nu a fost lansat nexecuie datorit unui conflict, reorganizarea va continua cu o alt instruciunedisponibil.
4) Se repet paii 1-3 pn cnd nu mai exist nici o instruciune disponibil n
acest ciclu.S) Se decrementeaz contorul de cicli.
6) Se determin urmtorul set de instruciuni disponibile. Precizm c oinstruciune este disponibil dac diferena ntre numrul ciclului n care a fostlansat n execuie instruciunea succesoare i numrul ciclului curent este egalcu latenta instruciunii.
7/29/2019 Arhitecturi Paralele de Calcul
58/75
58
7) Dac setul determinat la pasul 6 este consistent se trece la pasul 1. n cazcontrar, reorganizarea este complet.
6.1.5. Problema optimizrii globale n cadrul procesoarelor MEM. Tehnica
TRACE SCHEDULING" (TS)
Optimizarea basic-block"-urilor aferente unui program nu implic n modnecesar optimizarea ntregului program datorit problemelor legate deinstruciunile de ramificaie.
Reorganizarea programelor care conin branch-uri este mai dificil ntructaici mutrile" de instruciuni pot cauza incorectitudini ale programului reorga-nizat care ar trebui corectate. Aceast optimizare se mai numete i optimizareglobal.
Problema optimizrii globale este una deschis la ora actual, avnd o naturNP-complet. Se prezint n continuare n acest sens doar tehnica numit Trace
Scheduling", datorit faptului c este oarecum mai simpl i mai clar documentat.Se definete o cale (Trace") ntr-un program ce conine salturi condiionate, oramur particular a acelui program legat de o asumare dat a adreselor acestorsalturi. Rezult deci c un program care conine n salturi condiionate va avea 2nposibile ci (trace-uri). Aadar, o cale a unui program va traversa mai multe unitisecveniale din acel program. n figura 6.3 se prezint un program compus din 2 cidistincte, i anume TRACE1 i TRACE2.
A;B;
C;IF (D) {E;F;
}ELSE {
G;}H;I;
Fig. 6.3. Exemplu de trace-uri pe o secven de program [Vin00a].
Tehnica TS este similar cu tehnicile de reorganizare n basic-block-uri, cudeosebirea c aici se va reorganiza o ntreag cale i nu doar un basic-block. nesen, ea se bazeaz pe optimizarea celor mai probabile ci n a fi executate.
Pentru a putea aplica TS compilatorul trebuie s aib criterii rezonabile depredicie a salturilor condiionate, n vederea construirii cilor cu cea mai mare
7/29/2019 Arhitecturi Paralele de Calcul
59/75
59
probabilitate de execuie. n general, predicia software se face pe baza informaiilorrezultate din execuia anterioar a programului neoptimizat (profilings) sau a altoralgoritmi euristici nglobai n compilator.
6.1.6. Optimizarea buclelor de program
Este foarte important pentru c n buclele de program se pierde cea maimare parte a timpului de execuie aferent respectivului program, dup regula
binecunoscut care afirm c ,,n 90% din timp se execut cca. 10% din program"[Vin00b].
Exist dou tehnici importante utilizate n optimizarea buclelor: loop unrolling software pipelining
Aplicarea celor dou tehnici asupra unei bucle dintr-un program va conducela expandarea pe vertical a buclei respective. Spre deosebire de loop unrolling,tehnica software pipelining va consuma mai puin spaiu de cod.
Tehnica loop unrolling se va concentra pe eliminarea codurilor redundantedin cadrul buclelor (actualizri de contoare, loop-uri). Bucla se va procesa la vitezmaxim doar pe parcursul iteraiilor desfurate.
Tehnica software pipelining va determina obinerea unei viteze mari deexecuie pe timpul procesrii ntregii bucle.
6.2. Paralelizarea operaiei de