FACULTATEA DE AUTOMATIC I CALCULATOARE

CATEDRA CALCULATOARE

PROIECTla disciplina

Calcul Paralel i DistribuitProgramare paralel folosind biblioteca PJ2Delia GuitaMdlina IacobAn academic :2014 2015PROIECT de SEMESTRU

Catedra de Calculatoare

Disciplina : Calcul Paralel si Distribuit

Coordonator: s.l. ing. Cosmina IVAN

Data: 13-01-2015AbstractProiectul de fa prezint studiul programrii paralele folosind biblioteca PJ2. Lucrarea a fost ntocmit n baza unor exemple de utilizare a bibliotecii PJ2, evideniind avantajele acestei abordri prin implementarea algoritmilor exemplificai, att secvenial ct i paralel.Cuprins

iii1.Introducere

iii2.Studiu bibliografic

vi3.Elemente de implementare

vi3.1.Aproximarea lui PI

vii3.2.Generarea setului Mandelbrot

x4.Evaluare

x4.1.Evaluare algoritm pentru aproximarea lui PI

xii4.2.Evaluare algoritm pentru generarea setului Mandelbrot

xiv5.Concluzii

xv6.Bibiografie

1. IntroducereParallel Java 2 (PJ2) este o librrie de clase java care suport programare cu memorie distribuit, pentru calculatoare cu mai multe nuclee; programare paralel cu pasare de mesaje; programare paralel pentru accelerare GPU.

Pentru programarea pe mai multe nuclee, PJ2 furnizeaz buclele paralele i sectiunile paralele care sunt similare conceptual cu OpenMP. PJ2 suport reducerea claselor de variabile pentru tipurile primitive cu operaii de reducere predefinite: sum, minimum, maximum, dar putem defini i propriile clase.

Libraria PJ2 este gratuit, sub licenta GNU GLP, i este disponobil pe site-ul autorului. Versiunea de download include toate fisierele surs Java, i documentaia Javadoc. PJ2 ruleaz pe orice sistem cu versiune de Java 1.7 sau mai mare.2. Studiu bibliografic

Calculul paralel abordeaz problema proiectrii programelor astfel nct acestea s aib dou caracteristici: s ruleze pe mai multe procesoare (sau core-uri) i toate procesoarele s coopereze ntre ele pentru a rezolva o singur problem.Calculul paralel are aplicabilitate n vaste domenii cum ar fi: matematic (algebr liniar, teoria grafurilor), tiine (prognoza meteo, astrifizic, chimie), inginerie computaional (dinamica fluidelor, analiza elementelor finite), analiza datelor Big data analytics (data mining, indexarea paginilor web), securitate i criptografie, .a. [1]Arhitecturile paralele ofer o soluie de cretere a performanei sistemelor de calcul. Dac un algoritm secvenial specific execuia secvenial a aunui set de instruciuni, atunci un algoritm paralel permite executarea mai multor algoritmi secveniali, simultan ca procese paralele.[2]

Figur 1 Calculator cu un singur nod i un singur procesor

Figur 2 Calculator cu un singur nod i procesoare multiple

Conceptul calculului paralel se bazeaz n mare msur pe imbuntirea performanei. Astfel au fost definite diferite metrici de performan pentru programele paralele, care au la baz urmtoarea terminologie: Dimensiunea problemei N reprezint numrul de calcule pe care programul trebuie s le efectueze

Programul ruleaz pe un anumit numr de core-uri (nuclee) K. Pentru varianta secvenial se consider K=1.

Timpul de rulare T este timpul necesar prograului pentru a rula i depinde de dimensiune problemei i numrul de nuclee: T(N,K).Scalarea se refer la rularea programului pe un numr cresctor de nuclee. Exist dou moduri de scalare a unui program: strong scaling i weak scaling. n cazul scalrii tari (strong scaling) la creterea numrului de nuclee, dimensiune problemei rmne constant i astfel timpul scade la 1/K pentru calcularea rspunsului (speedup), iar n cazul scalrii slabe (weak scaling) dimensiunea problemei crete proporional cu numrul de nuclee, timpul rmnnd acelai pentru o dimensiune a problemei de K ori mai mare (sizeup).

Figur 3 Scalare tare

Figur 4 Scalare slab

Viteza de calcul reprezint numrul de calcule efectuate ntr-o secund:

R(N ,K) = N/T(N ,K) Speedup: Speedup(N,K)=Tseq(N,1)/Tpar(N,K)

Eficien: Eff(N,K)=Speedup(N,K)/K

Legea lui Amdahl susine faptul c de obicei o singur poriune dintr-un program poate fi paralelizat, restul programului rulnd pe un singur nucleu, indiferent de numrul de nuclee disponibile. Astfel se impune o linit speed-upului care se poate obine n ura scalrii tari.

T(N,K) = F*T(N,1)+(1-F)*T(N,1)/K,

unde F este fraciune de timp din timpul total de rulare n care programe este executat de un singur nucleu.

Figur 5 Scalare tare cu o fraciune de timp secvenial3. Elemente de implementare

Analiza eficienei i exemplificarea scalrii tari s-a efectuat pe doi algoritmi: aproximarea lui PI i generarea setului Mandelbrot.3.1. Aproximarea lui PI

Se consider o tabl ptrat de darts cu latura de diemensiunea 1 ce conine un cadran de cerc. Se genereaz N(x,y) puncte aleatorii pe aceast tabl i se vor numra punctele care sunt n interiorul cadranului de cerc. (x2+y21), notate C. Astfel se va calcula valoarea lui PI ca fiind aproximarea: 4C/N.

Figur 6 Tabl folosit pentru estimarea lui PI

Un program secvenial pentru acest algoritm va genera N, va numra C i apoi va calcula PI. Varianta paralel a algoritmului, n schimb, presupune mprirea lui N la numrul de thread-uri corespunztor numrului de core-uri, fiecare thread calculnd C-ul corespunztor, n final nsumndu-se aceste valori. Se va obine apoi valoare lui PI. Procesul de combinare a mai multor thread-uri ntr-unul (n cazul de fa la nsumarea C-urilor) se numete reducere paralel (parallel reduction).

Figur 7 Estimarea lui PI-algoritm secvenial i paralelPentru evidenierea rolului calculului distribuit, trebuie considerat N foarte mare. Condiia ca programul sa fi e secvenial, folosind PJ2, este ca metoda coresRequired() s fie suprascris asftfel nct s returneze valoare 1, reprezentnd sigurul core folosit de aplicaie. Dac nu se va suprascrie metoda, middleware-ul va consider c programul folosete toate core-urile disponibile.

n cazul implementrii paralele se folosete o bucl special numit parallelFor care va parcurge toate argumentele din linia de comand, crend astfel un obiect parallel loop. Se apeleaz metoda exec care duce la crearea unei noi bucle care conine metoda run unde s gsete codul pentru calculul propriu-zis. Prin apelul metodei threadLocal() se obine obiectul local thread-ului.[1]3.2. Generarea setului Mandelbrot

Setul Mandelbrot (Figura 8) este unul dintre cele mai faimoase obiecte fractale descoperite. Este numit n onoarea matematicianului Benoit Mandelbrot care a studiat acest set.

Punctele din setul Mandelbrot sunt negre, iar cele din afara setului sunt colorate, n functie de valoarea unui contor i . Banda roie din partea stng a imaginii corespunde valorii 1 a contorului, urmtoarea valorii 2, i aa mai departe. Tehnic, un punct este n setul Mandelbrot, doar dac a^2+b^2