APD - Note Curs - 1 Introducere

8/8/2019 APD - Note Curs - 1 Introducere

1/15

1

Capitolul 1 Introducere

Domeniul algoritmilor paraleli preocup de mai bine de mai mult timp un numr marede specialiti. Despre el, ca de altfel despre algoritmi n general, s-a scris mult i dindiferite puncte de vedere. Un efort considerabil a fost depus pentru gsirea celor mai

bune soluii paralele sau distribuite ale diverselor probleme, prin particularizarea unorsoluii secveniale cunoscute sau pornind de la premise conceptuale total distincte deacestea.

Lucrarea de fa vizeaz studierea sistematic a algoritmilor paraleli pentru cteva dincele mai reprezentative clase de aplicaii. Aceasta presupune adoptarea unui limbaj dedescriere adecvat i utilizarea lui pentru prezentarea i analiza celor mai cunoscute

soluii ale claselor de probleme selectate. Descrierea este completat prin discutareaunor aspecte relative la metodele de dezvoltare a algoritmilor paraleli i distribuii,precum i la analiza complexitii lor.

Pentru a ncadra mai bine subiectul, vom ncerca s rspundem succint la urmtoarelentrebri: care sunt principalele categorii de aplicaii paralele? care sunt principalele clase conceptuale de paralelism? care sunt principalele metode de programare? care sunt principalele clase de sisteme paralele folosite?

1.1. Categorii de aplicaii

Exist mai multe motive pentru a utiliza calculul paralel n realizarea aplicaiilor:scurtarea timpului de execuie, realizarea unei fiabiliti crescute, specializareafuncionali natura inerent paralel a aplicaiilor.

Una din cile de cretere a performanelor unei aplicaii este execuia simultan adiferitelor pari ale programului (pari pe care le numim procese) pe procesoaredistincte. De cele mai multe ori, procesele nu sunt complet independente, ci comunicntre ele. n funcie de frecvena comunicrilor, paralelismul are o granularitate maimare (comunicri rare) sau mai fin (comunicri frecvente).

O mare parte dintre algoritmii paraleli prezentai n literatur se refer la aceastcategorie de aplicaii. Problemele care trebuie rezolvate aici sunt legate att de gsirea


2/15

2

unei mpriri adecvate n procese a prelucrrilor ce trebuie realizate, ct i de gsirea

celor mai potrivite mecanisme de comunicare sau sincronizare ntre procese.

Pentru aplicaii la care sigurana n funcionare este un factor critic (de exemplu,comanda unui avion), replicarea unor pri ale lor (procese sau date) poate constitui osoluie de toleran la defecte. Daca anumite procesoare se defecteaz, replicile lor le

pot suplini. Ceea ce intereseaz aici sunt tehnicile de realizare corect a comutrii, cualte cuvinte protocoalele ce asigur comportarea corect n sisteme n carefuncionalitatea componentelor este parial.

Unele aplicaii pot fi mprite n faze cu funcionaliti distincte: de calcul nvirgul mobil, de prelucrri grafice, de prelucrare de fiiere, de imprimare etc.Aceasta permite exploatarea mai bun a caracteristicilor diferitelor componente alesistemelor de calcul, pentru realizarea unor performane deosebite (folosirea unor

procesoare n virgul mobil, a unor procesoare grafice, a unor servere de fiiere saude imprimare). Problemele importante sunt aici cele legate de partajarea eficient aresurselor sistemelor de calcul.

Unele aplicaii sunt inerent paralele. Un exemplu l constituie accesul simultan la obaz de date. Problemele importante aici sunt excluderea mutual i proteciautilizatorilor.

Sunt patru categorii despecialiti interesai de calculul paralel i distribuit: specialiti n calculatoare (computer scientists) din domeniile arhitectura, limbaje,

algoritmi (cutare i sortare, recunoaterea formelor, tolerana la defecte,algoritmi cu nalt grad de paralelism, algoritmi cu ascunderea latentelor),metodologii;

specialiti n calcul numeric (computational scientists) interesai n pachete de programe pentru calcul matriceal, sisteme de ecuaii lineare i nelineare, cuderivate pariale etc.

alte domenii tiinifice i inginereti (tehnologii i materiale noi, biomedicina,fizica nucleari altele)

comerciali (data mining, analize de risc etc.)Cerinele acestora i caracteristicile aplicaiilor lor sunt prezente succint n tabelul 1.1.


3/15

3

Tabel 1.1Domeniu tiinific i ingineresc ComercialCaracteristici virgul mobil

cod de dimensiune redusrata I/E redus

puine datepuini utilizatori

ntregicod de dimensiune marerata I/E maremulte datemuli utilizatori

Cerine performanascalabilitate

performanasigurana n funcionaredisponibilitate

1.2. Clase conceptuale

Desprinderea unor clase conceptuale n paralelism este important ca sprijin n primafaz de abordare a unei probleme. ncadrarea ntr-una din aceste clase poate dirija

proiectantul pe parcursul conceperii soluiei paralele a unei probleme. Clasificareaadoptat aici este una din mai multele prezentate n literatura de specialitate. Eaaparine lui Carriero i Gelernteri privete paralelismul n termenii: rezultatului unui program, agendei de activiti a programului, unui ansamblu de specialiti care mpreun constituie programul.Pentru a nelege mai bine fiecare concept, vom lua ca exemplu construcia unei case.Folosirea mai multor persoane la acest lucru conduce inerent spre paralelism. Dar,

exist mai multe ci de folosire a lucrtorilor.

Putem porni prin divizarea produsului final n mai multe componente: fundaie, perei,ferestre, ui, contor electric i conductori, contor de ap, evi, chiuvete etc. Putem apoitrece la construirea simultan a componentelori la asamblarea lor, pe msur ce suntterminate. Fiecrui lucrtor i se repartizeaz o parte a produsului final, de a cruiconstruire se ngrijete. Toi pornesc lucrul simultan i lucreaz pn n momentulcnd continuarea depinde de o anumit restricie (de exemplu, de o alt component).Acesta este paralelismul rezultat, numit astfel deoarece rezolvarea unei probleme

pleac de la mparirea rezultatului n mai multe fragmente, care sunt calculate nparalel, lund n consideraie (bineneles) restriciile impuse de problem.


4/15

4

Un exemplu tipic este calculul sumei a doi vectori de n elemente, S = A+B.

Elementele lui S sunt independente ntre ele i pot fi calculate n paralel, ntr-unsingur pas, folosind n procesoare, dup urmtoarea schem:

fa i := 1 to n do in parallel S[i] := A[i] + B[i] af

O alt posibilitate este de a alctui o agend de activiti necesare pentru a construicasa. Unele dintre ele se vor executa n paralel, altele sunt condiionate de o anumitordine. Oricum, lucrtorii vor fi repartizai activitilor curente din agend, n numrulnecesari fr a se face vreo difereniere ntre ei. Fiecare lucreaz ct timp restriciilenaturale ale problemei le permite acest lucru.

Cea mai cunoscut paradigm de implementare a acestei clase de paralelsim este

replicated workers sau master-worker. Un proces master iniializeaz calculele icreaz un numr de procese worker identice. n mod repetat, fiecare worker preia osarcin i o execut. Programul se execut la fel, indiferent de numrul proceselorworkeri se termin odat cu epuizarea sarcinilor.

Pentru exemplificare, s considerm o problem de minim. Dat fiind un ansamblu Ede nregistrri, E = {r} i o funcie de cost f:E->R care asociaz fiecrei nregistrri run cost f(r), se cere min f(r) cu r din E. Procesul master umple un sac cunregistrrile din E. Fiecare proces worker extrage o nregistrare r, calculeazf(r)i,dac gsete o valoare inferioar minimului parial curent, o transmite master-ului.Acesta actualizeaz minimul curent. Programul se termin la golirea sacului.

n fine, putem avea n vedere faptul c lucrtorii sunt specializai i c realizarea uneicase reclam diferite specialiti. Toi lucrtorii pot ncepe simultan. Iniial unii voratepta, pn cnd condiiile necesare efecturii operaiei pentru care sunt specializaisunt ndeplinite. Oricum, la un moment dat, vor lucra mai multe persoane. Aceastaeste abordarea paralelismului ca ansamblu de specialiti.

Aceast abordare este specific lucrului n banda de asamblare (pipeline) i sepreteaz n cazul prelucrrii mai multor obiecte identice (de exemplu un grup decase). n cazul general, ea conduce la programe organizate ca o reea logic, n carenodurile execut calcule relativ autonome, iar comunicarea ntre noduri se face dupatipare predictibile. Un exemplu tipic este cel al simulrii unor circuite, n care

funcionarea fiecrei componente este reprezentat de descrierea unui proces.


5/15

5

Autorii acestei clasificri insist asupra faptului c diversele clase nu sunt net

difereniate ntre ele. De asemenea, evideniaz cparalelismul de date, consideratde ali autori ca o clas conceptual important, nu este dect o form particular aagendei de activiti. n paralelismul de date, fiecare operaie este aplicat sincrontuturor componentelor unei structuri de date. Asupra acestui subiect vom reveni,artnd n ce mod alegerea unei clase conceptuale influeneaz rezultatul proiectrii.

1.3. Metode de programare

Odat stabilit clasa conceptual cea mai potrivit pentru aplicaie, urmeazproiectarea algoritmului folosind o metod de programare adecvat.

n programarea folosind comunicare de mesaje (figura 1.1), fiecare procesncapsuleaz structurile de date folosite (locale procesului), comunicarea ntre procesefcndu-se prin mesaje. Fiecare proces are acces doar la datele sale locale. Pentrucomunicare, procesele includ aciuni explicite de transmitere i recepie de mesaje.

Comunicarea de mesaje exprim ntr-un mod natural paralelismul specialist. Fiecareproces este un nod al reelei de specialiti, ntre care comunicarea se face prin mesaje.

Figura 1.1

O abordare complet diferit (figura 1.2) ncapsuleaz fiecare proces ntr-un obiect.Procesul este responsabil doar de calculul valorii corespunztoare obiectuluirespectiv. Mediul exterior este interesat doar n cunoaterea valorii unui obiect, nu in modul n care ea este calculat. Comunicarea nu se face prin aciuni de transmiterei recepie. Pur i simplu, cnd un proces are nevoie de valoarea produs de un alt

proces, el o citete prin acces la obiectul respectiv. Aceste obiecte sunt aa numitelestructuri active (vii) de date, sau obiecte active.

procesdate

mesaj


6/15

6

Figura 1.2

Aceast metod exprim bine paralelismul rezultat. Relund exemplul sumei a doivectori, fiecare obiect poate reprezenta un element S[i] al vectorului suma i poatencapsula procesul ce calculeaz valoarea sa.

ntre cele dou abordri extreme se afl cea la care procesele i datele sunt entitidistincte. Procesele pot comunica prin citirea i scrierea datelor partajate (figura1.3).

Figura 1.3

Aceast metod se potrivete bine cu paralelsimul agenda, datele partajatereprezentnd un mijloc eficient de comunicare ntre procesele masteri worker.

Tabelul 1.2 arat o coresponden posibil ntre clasele conceptuale i metodele deprogramare paralel. Ea nu trebuie interpretat rigid. Aa cum pentru o problem de

proces proces proces proces

proces

obiectactiv

procese


7/15

7

rezolvat, programatorul are la dispoziie modele aparinnd, eventual, unor clase

conceptuale diferite, n acelai fel, pentru un model el are la dispoziie mai multemetode de programare.

Tabel 1.2Clase conceptuale Metode de programare

rezultat obiecte activeagenda de activiti date partajateansamblu de specialiti comunicare de mesaje

1.4. Clase de sisteme paralele i distribuite

n principiu, ar trebui ca efortul de gsire a unor algoritmi paraleli eficieni s nu inseama de particularitile unora sau altora din mainile pe care se face implementareaacestora, ci s caute s exploateze ct mai bine paralelismul inerent problemeistudiate. n practic, ns, trebuie avute n vedere detalii de implementare legate demaina, care pot afecta (uneori ntr-o msur important) timpul de execuie.

Una din clasificrile clasice adoptate pentru calculatoarele paralele este cea a luiFlynn (1966). Ea consider fluxurile de instruciuni i de date, pentru a distinge ntreurmtorele categorii: SISD -Single Instruction stream Single Data stream (flux unic de instruciuni,

flux unic de date); SIMD -Single Instruction stream Multiple Data stream; MISD -Multiple Instruction stream Single Data stream; MIMD -Multiple Instruction stream Multiple Data stream.O alt clasificare, asemntoare precedenteia, consider ca elemente de baz

procesoarele i memoria, fcnd distincie ntre urmtoarele categorii de sisteme: tablouri de procesoare (processor array) procesoare n linie de asamblare (pipeline processors) sisteme cu memorie partajat (multi-processors) sisteme cu transmitere de mesaje (distributed systems).Dei exist legturi evidente ntre cele dou clasificri, nu se poate face ntre ele o

coresponden unu la unu. Astfel, dei modelul SIMD descrie tabloul de procesoare,el este folosit uneori i pentru procesoare n linie de asamblare. Pentru acestea dinurm, modelele SISD i MISD sunt, de asemenea, de multe ori aplicabile. A doua


8/15

8

clasificare prezentat este uneori preferat pentru corespondenele directe pe care le

are n programare. Reprezentrile grafice asociate modelelor lui Flynn sunt cele dinfigura 1.4.

SISD este modelul von Newmann din anii 40. El nu include, n esen, forme deparalelism, operaiile unui algoritm fiind executate secvenial, de un singur procesor.

Figura 1.4C - Control, P - Procesor, M - Memorie

n modelul MISD exist un singur flux de date i mai multe fluxuri de control. nficare pas, procesoarele au acces la o aceeai dat din memorie, creia i pot aplicatratamente diferite, corespunztoare unor fluxuri de instruciuni diferite. De exemplu,

putem stabili dac un numr natural este sau nu prim, ntr-un singur pas, dac existun numr de procesoare egal cu numrul de divizori poteniali. Mai general,

procesoarele pot face operaii diferite asupra unei aceleiai valori: primul poate afla

C

P

P

P

M

M

M

C

C

C

P

P

P

M

C P M

flux instruct flux date

C

C

C

P

P

P

M

M

M

SISD SIMD

MISD MIMD


9/15

9

rdcina ptrat, al doilea calculeaz puterea a treia a aceluiai numr, iar un alt

procesor afl dac numrul este sau nu prim.

Spre deosebire de modelele la care ne vom referi n continuare, MISD este mai rigidi are o utilitate practic foarte restrans.

Un tablou de procesoare (figura 1.5) const dintr-un numr de procesoare identice,aflate sub controlul unei singure uniti de comand. Fiecare procesor are accesseparat la datele sale locale, astfel nct, la un moment dat, o aceeai operaie esteexecutat simultan asupra mai multor uniti de date. Acest mod de lucru sincron estetipic tablourilor de procesoare. n mod natural, operaiile caracteristice sunt celematriceale. Aa cum s-a menionat, fiecare procesor are propria sa memorie local.Pentru actualizarea ei este necesar comunicarea cu celelalte procesoare sau cu uncalculator gazd. Comunicarea poate fi realizat n dou moduri, de unde rezult douclase de sisteme SIMD: prin memorie partajat (SM - shared memory - SIMD) i prinreea de interconectare.

Figura 1.5

Primele sisteme, cunoscute i sub numele de PRAM (Parallel Random - AccessMachine), au diferite variante, dup cum accesele la aceeai locaie de memorie

pentru citire sau scriere sunt concurente sau exclusive. Evident c performanelealgoritmilor sunt influenate de acest aspect, aa cum rezulti din exemplul urmtor,care se refer la o problem de cutare.

Fie un fiier cu n intrri, unde n este foarte mare. Dndu-se o valoare oarecare a, secere s se precizeze dac ea este n fiier. Considerm c fiierul este mprit n N

M M MP P P

Unitate de control


10/15

10

sub-fiiere, fiecare sub-fiier Si, de dimensiune n/N, fiind accesibil unui procesor Pi

distinct (sunt deci N procesoare P1, ..., PN). Fiecare procesor Pi citete valoarea lui a,caut aceast valoare n sub-fiierul Si i, n caz de succes, seteaz valoarea uneivariabile rezultat R.

Problema poate fi rezolvat n n/N pai. Condiia este ns ca accesul la valoarea lui apentru citire s fie concurent. n plus, dac fiierul nu are nregistrri distincte, estenecesar ca i accesul la scriere pentru R s fie concurent.Dac prima condiie nu este ndeplinit, valoarea lui a trebuie difuzat explicittuturor proceselor. Difuzarea se poate face astfel:- P1 citete valoarea lui ai o comunic lui P2;

- P1i P2 comunic simultan valoarea lui a ctre P3i P4;- simultan, P1, P2, P3i P4 comunic valoarea lui a ctre P5, P6, P7i P8.a.m.d.Deoarece numrul de procese care cunosc valoarea lui a se dubleaz la fiecare pas,rezult c difuzarea dureaz log2 N pai. ntregul algoritm reclam deci log N + n/N

pai n cazul cel mai defavorabil.

Exist i variante de terminare a algoritmului imediat ce un procesor a regsitvaloarea lui a n sub-fiierul corespunztor. n acest caz valoarea rspunsului Rtrebuie difuzat celorlalte procese. De data aceasta, valoarea rezultatului esteinspectat de fiecare proces, nainte de a continua cutarea n propriul fiier, ceea ceconduce la un total de log N + (n/N).log N pai n cazul cel mai defavorabil.

n privina sistemelor SIMD interconectate n reea, topologiile uzuale sunt maisimple dect graful complet. Prezentm cteva variante:a) tabloul uni-dimensional

b) tabloul bi-dimensionalc) arbore binar completd) amestecare perfect (perfect shuffle)

- date fiind N procesoare P0, ..., PN-1, cu N o putere a lui 2, Pi i Pj suntlegate printr-o linie uni-direcional, unde

j = 2.i pentru 0


11/15

11

Figura 1.6e) cubf) hipercub.

Alegerea unei configuraii depinde de aplicaie, de performanele dorite i de numrulprocesoarelor disponibile. Astfel, pentru suma a n numere, o topologie avantajoaseste arborele cu n/2 frunze i log n nivele. Operaia se realizeaz n log n pai (vezifigura 1.7).

Figura 1.7

n cazul a m grupuri de cte n numere, sumele pot fi aflate n log n + m - 1 pai,folosind tehnica liniei de asamblare (pipeline), la care ne referim ceva mai departe naceast seciune.

Exemplele de sisteme SIMD includ mai multe modele comerciale, dintre care celemai cunoscute sunt CM-2 produs de Thinking Machines i MP-2 produs de Maspar.Din pcate, nici unul din aceste modele (care se bazeaz pe matrice de procesoare) nu

a cunoscut succesul de pia. n schimb, mai larg acceptate au fost sistemelevectoriale, dintre care modelele Cray-1, C90i T90 au dominat domeniul calcululuitiinific.

X0

X1

X2

X3

X4

X5

X6

X7

X0+X1

X2+X3

X0+X1+X2+X3

Suma

X4+X5+X6+X7

X4+X5

X6+X7

P0 P1 P2 P3 P4 P5 P6 P7


12/15

12

Exemple de limbaje de programare: DAP-FORTRAN, Actus (bazat pe Pascal),CMLISP (Connection Machine Lisp). Caracteristicile sistemelor se reflect la nivelullimbajelor. Astfel, pentru FORTRAN, tablourile sunt tratate ca tipuri fundamentale,cu operatori specifici operaiilor matriceale.

Prelucrarea n linie de asamblare este un principiu utilizat n multe fabrici i estemprumutat n sistemele de calcul. Ideea este de a mpri o prelucrare n mai multe

procese care se deruleaz unul dup altul i se execut fiecare pe un procesor aparte.Fiecare proces depinde de rezultatul procesului precedent din secveni furnizeazrezultate procesului urmtor.

Dac este necesar efectuarea mai multor prelucrri, atunci, derularea lor poate avealoc n paralel: n timp ce procesorul i execut un proces, procesorul i-1 execut

procesul i-1 din prelucrarea ce urmeaz, iar procesorul i+1 execut procesul i+1 dinprelucrarea precedent.

S considerm calculul urmtor:for i:=1 to 64 do

begin

E[i]:=A[i]+B[i];

F[i]:=E[i]*C[i];

G[i]:=F[i]-D[i]

end

executat pe trei procesoare specializate pentru operaiile de adunare, nmulire i

respectiv scdere. Derularea n timp a operaiilor, n condiiile unei prelucrri n liniede asamblare la nivelul instruciunilor poate fi cea din figura 1.8.

E[I]:= 1 2 3 4 n

F[I]:= 1 2 3 4 n-1 n

G[I]:= 1 2 3 n-2 n-1 n

t 1 2 3 4 5 n n+1 N+2

Figura 1.8

O clasificare a sistemelor cu prelucrare n linie de asamblare ine cont de nivelul decomplexitate al proceselor, care poate fi:

al operaiilor aritmetice (faze de instruciune) al instruciunilor


13/15

13

al programelor.Clasa cea mai general este cea a sistemelor MIMD. i aici ntlnim cele douvariante de comunicare: prin memorie partajat (sisteme multiprocesoare) i printransmitere de mesaje (sisteme multicalculatoare).

Un sistem cu memorie partajat (figura 1.9) const din mai multe procesoare care auacces la module de memorie comun (sisteme multiprocesor). Procesoarele potexecuta procese diferite, dar care trebuie corelate ntre ele (sincronizate) pentru a evitainterferenele (i deci erorile de prelucrare). Numeroase modele au fost propuse pentru

programarea acestor sisteme. Dintre ele, amintim: primitivele P si V, regiunile critice,monitoarele.

Figura 1.9

Exist destul de multe sisteme experimentale care se nscriu n aceast categorie.Dintre cele comerciale mai recente, amintim Sun Enterprise 10000, care este unsistem din categoria UMA (Uniform Memory Access) pentru care procesoarele auacelai timp de acces la oricare modul de memorie. Configuraia maxim a unuisistem include 64 de procesoare UltraSPARC distribuite n 16 grupuri a cte 4

procesoare. Fiecare grup este dispus pe o plac mpreun cu 4 module de memorieRAM de cte 1 GB fiecare. Conexiunea ntre procesoare i blocurile de memorie esteasigurat de unswitch crossbar16*16, numit Gigaplane-XB. Acesta are funcia de atransfera datele ntre memorie i cache-urile procesoarelor. Transferul se face pe 16octei, astfel c sunt necesare 4 cicluri pentru a transfera o line de cache care are 64octei. n afara switch-ului, mai exist patru magistrale de adrese care sunt folosite

pentrusupraveghere (snooping). Fiecare bus este folosit pentru o ptrime din spaiulde adrese fizice, astfel c pentru selecia unei magistrale din patru sunt folosii doi bii

M M M

P P P

Interconexiune rapid


14/15

14

de adres. Cnd un procesor nu gsete datele n propria memorie cache el plaseaz

adresa pe magistrala de adrese corespunztoare pentru a vedea dac datele sunt nmemoria cache a altui procesor. Toate grupurile de procesoare inspectreaz toate cele

patru magistrale. Cea care are datele cerute le furnizeaz imediat. Dac nu existrspuns, datele nu exist n cache i trebuie aduse din memorie.

Uneori, memoria partajat este distribuit, astfel nct exist um modul de memoriemai apropiat de fiecare procesor. Accesul la acest modul este mai rapid pentru un

procesor i mai lent pentru celelalte. Din acest motiv, modelul se mai numeteNUMA (Non Uniform Memory Access). Pentru a scurta timpul de acces, unelesisteme pstreaz o parte a datelor n memoriile cache ale procesoarelor, care, evidenttrebuie pstrate coerente (ccNUMA - cache coherent NUMA). Aceste sisteme se mainumesc sisteme cu memorie distribuit, alteori sisteme cu memorie local (figura1.10). Exemple de sisteme ccNUMA includ SGI Origin 2000 i Sequent NUMA-Q2000.

Figura 1.10

Sistemele cu transmitere de mesaje (se mai numesc multicalculatoare) constau dincalculatoare interconectate. Procesoarele execut procese diferite, iar sincronizareaeste realizat prin schimburi de mesaje. Diferenele ntre sisteme se manifest prin: comunicare sincron sau asincron de mesaje schema de comunicare -direct de la proces la proces

-prin cutii potale globale-prin canale de legtur ntre procese

Exist dou categorii de multicalculatoare. Prima categorie, cunoscut sub denumirea

de MPP, Massively Parallel Processors, include sisteme n care procesoarele (nnumr ridicat) sunt interconectate prin reele de mare vitez, construite special ca

M M M

P P P

Reea de comunicaie


15/15

15

soluii de firm, pentru a realiza performane foarte ridicate. Exemple de sisteme

din aceast categorie sunt: Cray T3EiIBM SP-2.

A doua categorie include sisteme construite din PC-uri sau staii de lucruinterconectate prin reele comerciale. Astfel de sisteme se numesc NOW (NetworksOf Workstations) sau COW (Clusters Of Workstations).

Un exemplu de aplicaie pentru multi-calculatoare este jocul de ah, n care segenereaz mutrile posibile, a cror mulime poate fi organizat arborescent: rdcinaeste configuraia curent; fiii si corespund configuraiilor dup prima mutare .a.m.d.Gsirea mai rapid a celei mai bune mutri se poate face distribuind unor procesoaredistincte cutarea n sub-arbori diferii.

Comunicarea ntre procesoare este necesar pentru transmiterea celei mai bune soluiigsite pn la un anumit moment i pentru transmiterea unor sub-arbori n vedereacontinurii inspectrii. La un moment dat, dou procesoare distincte pot executasecvene diferite de instruciuni, ceea ce este n concordan cu caracteristicilesistemelor MIMD.

APD - Note Curs - 1 Introducere

Documents

Transcript of APD - Note Curs - 1 Introducere