Algoritmi Paraleli i Distribuii
Ciprian [email protected]
Reguli, punctaje,
Despre curs (1)
http://curs.cs.pub.ro
MaterialeForumTeme .
Luni Marti Miercuri Joi Vineri
0810 331CCDragos
Comaneci
1012 331CCMihaiCarabas 333CC
DragosComaneci
1214 333CCElianaTirsa
1416 332CCElianaTirsa 332CC GabrielGutu
1618 334CCAlecsandruPatrascu
1820 334CCAlecsandruPatrascu
Despre curs (2)
Nota:10 = 5 (Laborator) + 1.5 (Curs) + 0.5 (Supl) + 4 (Examen)
Laborator+Curs >= 3 Examen >= 2
Laborator: 4 teme(4)+activitate(1)
Curs: lucrri de curs (1) + teste la laborator (0.5)
Examen: scris (4) + problem suplimentar (0.5)
ntrebri?
Interactivitate dialog Open-office: ????, EG403 Regulament afiat pe pagina cursului Punctajele obinute pe parcurs sau examen se pot
pastra pentru in an universitar (nu acumulare) Temele se pot trimite doar pe parcursul primului
semestru universitar Mrirea de not nu se poate face far re-susinerea
examenului
Despre curs (3)
Vineri, 10-12 AM
Interactivitate - teamwork
Despre mineAbsolvent al Facultatii de Automatica si Calculatoare
E-mail: [email protected]: http://www.facebook.com/ciprian.dobre
http://cipsm.hpc.pub.ro
Despre curs
Mainframe
Mini Computer
Workstation
PC
Bibliografie
G.R.AndrewsConcurrent Programming. Principles and PracticeThe Benjamin/Cummings Publishing Company, Inc., 1991
G.R.AndrewsFoundations of Multithreaded, Parallel, and Distributed ProgrammingAddison Wesley, Inc., 2000
F. Thomson LeightonIntroduction to Parallel Algorithms and Architectures: Arrays. Trees. Hypercubes.Morgan Kaufmann Publishers, San Mateo, California, 1992
A.G. AklParallel Computation. Models and MethodsPrentice Hall 1997
M.J. QuinnParallel Computing. Theory and PracticeMcGraw-Hill, 1994
Claudia LeopoldParallel and Distributed ComputingJohn Wiley & Sons, 2001
A.Y.H. ZomayaParallel and Distributed ComputingMcGraw-Hill, 1996
Gerard TelIntroduction to Distributed AlgorithmsCambridge University, 1994
Robert W. SebestaConcepts of Programming Languages (Second Edition)The Benjamin Cummings, 1993
S.A. WilliamsProgramming Models for Parallel SystemsJohn Wiley & Sons, 1990
K.M. Chandy, J.MisraParallel program design.A foundation Addison-Wesley Publishing Company, 1988
M. Ben AriPrinciples of concurrent and distributed programmingPrentice Hall, N.Y. 1990
H.BallProgramming distributed systemsPrentice Hall, NY 1990
C.A.R. HoareCommunicating Sequential ProcessesComm. of the ACM, 1978
S.G. AklThe Design and Analysis of Parallel AlgorithmsPrentice Hall, 1989
G.R. Andrews, R.A. OlssonThe SR Programming Language. Concurrency in PracticeThe Benjamin/Cummings Publishing Company, Inc., 1993
Ian FosterDesigning and Building Parallel ProgramsAddison-Wesley Publishing Company, 1995
A.S. TanenbaumStructured Computer Organization (Fourth Edition)Prentice Hall, 1999
Curs
1. Introducere - Limbaje de descriere a algoritmilor paraleli. Concurena i sincronizare. Atomicitate. Bariere. 3 ore
2. Paralelism de date - Calcule prefix. Prelucrri de liste i matrice. 3 ore
3.Complexitatea calculului paralel - Msuri de performan. Calculul complexitii. Proprieti ale modelului de evaluare. Modelul Work-depth.
3 ore
4. Dezvoltarea algoritmilor folosind variabile partajate 2 ore
5.Dezvoltarea aplicaiilor pentru modele PRAM - Cutarea paralel. Selecia paralel.
3 ore
6. Comunicarea prin mesaje - Biblioteci pentru programare distribuit. MPI. 3 ore
7. Complexitatea calculului distribuit - Modelul Foster. Modelul LogP. 2 ore
Curs (2)
8.Ceasuri logice i ordonarea evenimentelor -Vectori de timp (vector timestamps).
3 ore
9.Algoritmi und Descriere i proprieti. Algoritmii inel, arbore, ecou. Algoritmul fazelor. Algoritmul lui Finn.
3 ore
10. Stabilirea topologiei 2 ore
11. Terminarea programelor distribuite 3 ore
12. Algoritmi pentru sisteme tolerante la defecte 3 ore
13. Alegerea liderului 3 ore
14. Algoritmi pentru excludere mutual 3 ore
Obiectiv
Acumularea competentelor necesare pentru rezolvarea problemelor prin solutii paralele sau
distribuite
Calcul paralel = impartirea unei aplicatii in task-uriexecutate simultan
Calcul distribuit = impartirea unei aplicatii in task-uriexecutate in sisteme diferite (cu resurse diferite)
APD difera de algoritmii secventiali
Au la baza concepte diferite Communicating Sequential Processes (Hoare) Concurenta Atomicitate Sincronizare
Folosesc modele de programare care asigura comunicareaintre procese prin Date partajate Comunicare de mesaje Algoritmii paraleli si distributi NU sunt simple extensiisau versiuni ale celor secventiali Sunt folosite abordari diferite
APD difera de algoritmiisecventiali
Exemplu
Dou conturi replicate n New York(NY) i San Francisco(SF) Dou actualizri n acelai timp: Soldul curent: $1,000 Actualizare1: Adaug $100 la SF; Actualizare2: Adaug dobnda de 1% la NY Whoops, stri inconsistente!
SF NY
Actualizare 2Actualizare 1
Baze de date replicateOrdine actualizri
1 2 2 1
La terminare veti cunoaste
Conceptele de baza Modelele de programare Metode de proiectare a solutiilor paralele si
distribuite Modalitati de implementare a solutiilor folosind
limbaje de programare / biblioteci Java concurentMPI
Metode de imbunatatire a performantei solutiilorfolosind modele de complexitate
Ce este calculul paralel?
abordarea serial:
abordarea paralel:
(simplificat): folosirea simultan a mai multor resurse de calculpentru rezolvarea unei probleme computaionale
Ce este calculul paralel? (2)
Resurse de calcul
Un singur computer cu maimulte CPU DualCore, QuadCore, HPC
Mai multe computereconectate ntr-o reea Clustere
Combinaie ntre cele dou Grid-uri, Sisteme Cloud
Problem computaional
Caracteristici:
Poate fi divizat n pri discrete ce pot fi rezolvate simultan
Poate executa mai multe instruciuniconcomitent
Poate fi rezolvat n mai puin timp cu resursemultiple dect cu o singur resurs
De ce calcul paralel? (2)
Timp mai puin (wall clock time) Probleme de dimensiuni mai mari Concuren (procesri simultane) Folosirea resurselor nelocale Reducerea costurilor Depirea constrngerilor de memorie
Limitri ale arhitecturilor seriale:
Viteze de transmisie dependene de hardware Limitri de miniaturizare chiar i n molecular
computing!
Limitri economice costuri ridicate pentru a realiza un procesor mai rapid (ex: Intel, IBM Cell)
De ce calcul paralel? (3)
Great Challenge Problems: Fizica nuclear Clim, meteo Biologie genomul uman Geologie activitate seismic Electronic circuite Medicin imagistic
Aplicaii comerciale: Baze de date paralele data minning Motoare de cutare Collaborative work Realitate virtuala (gaming), grafica Networked video Aviaie - modelare
Cine i ce?
Cine i ce? (2)
Experimentul ALICE la CERN: Unul din cele 4 experimente
LHC, dedicat fizicii ionilorgrei
Volum de date: 1 luna de experimente Pb-Pb
~ 1 Pbyte 11 luni de experimente p-p
~ 1 Pbyte Simulare:
1 eveniment Pb-Pb ~24 ore Reconstrucie de date,
filtrare, analiz, calibrare
Paralel vs. Distribuit
Calcul paralel mprirea unei aplicaii n task-uri executate simultan
Calcul distribuit mprirea unei aplicaii n task-uri executate n sisteme diferite (cu
resurse diferite)
Convergen paralel distribuit Folosesc din ce n ce mai mult aceleai arhitecturi
Sisteme distribuite folosite n calcul paralel Calculatoare paralele folosite ca servere de mare performan
Au zone de aplicaii comune Problemele de cercetare se intreptrund i sunt abordate n comun Se folosete termenul comun de calcul de nalta performan (HPC
High Performance Computing)
Arhitecturi Paralele
Taxonomia Flynn (1986) SISD Single Instruction Stream, Single Data
Stream SIMD Single Instruction Stream, Multiple Data
Stream MISD Multiple Instruction Stream, Single Data
Stream MIMD Multiple Instruction Stream, Multiple
Data Stream Importana pentru implementarea
algoritmilor paraleli
SISD
Model clasic von Neumann
Unitatede
controlProcesor Memorie
Flux deinstruciuni
Flux de date
SIMD
Implementat ca Sisteme cu memorie partajat - Shared Memory (PRAM) Multiprocesoare interconectate - Interconnected Multiprocessors
C
M
M
M
SIMD (2)
Shared memory (Parallel Random Access Machine - PRAM) EREW - Exclusive Read Exclusive Write CREW - Concurrent Read Exclusive Write ERCW CRCW
Influeneaz performana Exemplu: citirea valorii unei variabile partajate Un pas in CREW, CRCW log N pai in EREW, ERCW
SIMD (3)
Valoarea este n variabila A n memoria comun Folosete X0, X1, din memoria comun
Procesul P0 citeste valoarea i o scrie n X0 Procesul P1 citete X0 i o scrie n X1 Procesele P2, P3 citesc X0, X1 i scriu n X2, X3
numrul de cpii se dubleaz la fiecare pas pentru N procesoare operaia se termin dupa log N pai
X0 X1 X2 X3 X4 X5
a
AMemoriacomun
P0 P1 P2 P3 P4
Pas 1
a
X0 X1 X2 X3 X4 X5
a
A Memoriacomun
P0 P1 P2 P3 P4
Pas 2
a
X0
a
X1
a
X2 X3 X4 X5
a
A Memoriacomun
P0 P1 P2 P3 P4
Pas 3
SIMD (4)
Reele de interconectare Topologii: tablou arbore cub hipercub
Configuraia depinde de: aplicaie performanele dorite numrul procesoarelor disponibile
Exemple: IBM 9000, Cray C90, Fujitsu VP
Arbore
0 1
2 3
4 5
6 7
MISD
Fr relevan practic
M
MIMD
Implementat ca Multi-calculatoare (memorie distribuit) sau Multi-procesoare (memorie partajat)
MIMD (2)
"Shared Memory" Uniform Memory Access (UMA) Non-Uniform Memory Access
(NUMA) Cache coherent Non-Uniform
Memory Access (ccNUMA)
Avantaje: Spaiu de adrese global uurina n programare Partajare rapid a datelor ntre procese datorit proximitii memorie
CPU
Dezavantaje: Lips scalabilitii ntre memorie i CPU Sincronizarea n responsabilitatea programatorului Scump
MIMD (3)
"Multi-Computer" Massively Parallel
Processors (MPP) Network Of Workstations
(NOW)
Avantaje: Scalabilitate memorie CPU Acces rapid la memorie Costuri reduse: procesoare + networking
Dezavantaje: Responsabilitatea programatorului pentru comunicaia inter-procesoare Mapare dificil a structurilor de date globale
Metode de programare
Date partajate (Shared data)
M M
M M
M
M
M
M
M
M M
M M
M
CPU CPU CPU
Metode de Programare (2)
Transmitere de mesaje (Message passing)
CPU
M
CPU
M
CPU
M
CPU
M
Un model de programare
Un program paralel / distribuit = colecie de procese paralele comunicante -Communicating Sequential ProcessesBazat pe modelul CSP al lui HoareFolosit n multe limbaje i biblioteci
paralele / distribuiteAdaptat pentru message passing i
shared data
boolean boolntreg intreal realcaracter charir caractere string
Declaraia variabilelorvar id1: tip1:= val1, ... , idn: tipn:= valn;
Definiiile de constanteconst id1 = val1, ... , idn = valn;
Tipuri de baz
Tablou
var vector: array [1:10] of int; matrice: array [1:n,1:m] of real;
Constructor
var forks: array [1:5] of bool := ([5]false);
Tipuri de baz (2)
Elemente contigue ce pot fi procesate n paralel
nregistrare
type student = rec (nume : string[20];vrsta: int;clase: array [1:5] of string[15]);
var queue: rec (front: int :=1;rear: int :=1;size: int :=0;contents: array [1:n] of int);
Tipuri de baz (3)
Atribuirea x:=eInterschimbarea x1:=:x2Comanda cu gard B SInstruciunea compus [S] este o secven de instruciuni. Selecia (if)
if B1 S1[] B2 S2
...[] Bn Snfi
Instruciuni
S se execut doar dac B esteevaluat la valoarea true
Iteraia (do)do B1 S1[] B2 S2
...[] Bn Snod
Ciclul cu contor (fa)fa cuantificatori instruciuni afvariabil := val_init to val_final st B
Exemple:fa i:=1 to n, j:=i+1 to n m[i,j]:=:m[j,i] affa i:=1 to n, j:=i+1 to n st a[i]>a[j] a[i]:=:a[j]af
Instruciuni (2)
procedure p(f1: t1; ...; fn: tn) returns r: tr;declaraiiinstruciuni
end;
Exemplu: calculul factorialului.procedure fact(i : int) returns f: int;
if i < 0 f := -1[] i = 0 or i=1 f:=1[] i > 1 f := i * fact(i-1)fi
end;
Proceduri
Execuie concurent
co S1 || S2 || ... || Sn oc
Ex.1:x:=0; y:=0;co x:=x+1 || y:=y+1 ocz:=x+y;
Ex. 2:co j:=1 to n a[j]:=0 oc
Execuie concurent
co S1 || S2 || ... || Sn oc
Ex.1:x:=0; y:=0;co x:=x+1 || y:=y+1 ocz:=x+y;
Ex. 2:co j:=1 to n a[j]:=0 oc
Ex. 3: produs de matrici
var a,b,c: array [1:n,1:n] of real;co Prod(i:1..n, j:1..n)::
var sum : real :=0;fa k := 1 to n
sum := sum + a[i, k] * b[k, j] afc[i,j]:=sum
oc
Execuie concurent (2)
Aciuni indivizibile care examineaz sau modificstarea sistemului / starea programului
Orice stare intermediar din implementarea aciuniiatomice nu trebuie s fie vizibil celorlalte procese Ex: instruciuni main de load sau store
Read/write aciuni atomice, fiecare proces are propriul set de regitri, strile intermediare evaluriiunei expresii complexe sunt stocate n regitriiproprii procesului
Execuia unui program concurent const n ntreeserea secvenelor de aciuni atomiceexecutate de fiecare proces
Istorie (trace): s0 s1 sn
Aciuni atomice
Variabilele pot fi mprite n: R: Variabile care sunt citite, dar nu i modificate W: Variabile care sunt modificate (pot fi i citite)
Dou pri ale unui program sunt independente dac mulimea R a fiecrei pri este disjunct fa de mulimile R i W ale celeilalte pri
Referin critic: o variabil dintr-o expresie care este modificat de un alt proces
Aciuni Atomice (2)
y:= 0; z:= 0;co x:=y+z || y:=1 || z:=2 oc;
La sfrit, x poate avea oricare valoare dintre: 0,1,2,3.
Corecie: n cursul evalurii unei expresii, variabilele nu trebuie modificate de alte procese
Majoritatea declaraiilor din programele concurente nu ndeplinesc aceast condiie!
Aciuni Atomice (3)
evaluarea atomic
x:=e satisface proprietatea dac fie: e conine cel mult o referina critic i x nu e
citit de alte procese e nu conine referine critice (deci x poate fi
citit de alte procese)
Dac nu e ndeplinit aceast condiie,folosim mecanisme de sincronizare pentru a asigura atomicitatea.
At Most Once
Sincronizare
Soluia: Aciuni atomice: Sincronizare folosind await:
Doar sincronizare condiionat: spin loop / busy waiting !
Exemplu: Productor - Consumator
Productor
Consumator
Buffer 1
var buf: int, p: int :=0, c:int :=0;co Producer::
var a: array[1:n] of int;do p < n ;
buf := a[p + 1];p := p + 1
odocco Consumer::
var b: array [1:n] of int;do c < n ;
b[c + 1] := buf;c := c + 1
odoc
p = c
p > c
Exemplu: Productor-Consumator
Paralelism de date, algoritmi iterativi:do true co i := 1 to n code_process_i oc
odco Process(i: 1..n):: do true
code_process_ibarrierodoc Toate procesele se sincronizeaz la sfritul fiecarui ciclu Util cnd fiecare iteraie depinde n ntregime de rezultatele
iteraiei precedente
Sincronizarea cu barier
Soluie ineficient!
co
oc
barrier
barrier
code_process_i
Sincronizarea cu barier
co
oc
co
oc
co
oc
t
i
m
p
var gril, nou: array [0:n+1, 0:n+1] ofreal;
var converge: boolean := false;co CalculGril(i:1..n, j:1..n)::
do not converge nou[i,j] := (gril[i-1,j]
+ gril[i+1,j]+ gril[i,j-1]+ gril[i,j+1])/4;
barriertest_convergent;barriergril[i,j] := nou[i,j];barrier
odoc
Exemplu: calcul gril
Sumar
Problematica calculului paralel i distribuit Arhitecturi paralele Metode de programare Limbaje de descriere a algoritmilor paraleli Concuren i sincronizare Atomicitate Bariere
ntrebri?