Algoritmi Paraleli i Distribuii

Ciprian Dobreciprian.dobre@cs.pub.ro

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: ciprian.dobre@cs.pub.roFacebook: 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?