c1-ccalculparalel

25
Calcul paralel si concurent Liviu P. Dinu [email protected]

description

-

Transcript of c1-ccalculparalel

Calcul paralel si concurent

Liviu P. Dinu

[email protected]

Introducere

• Partea 1: Aspecte formale ale calcului paralel– Indian grammars– Parsare paralela a limbajelor independente de context – Sisteme Lindenmayer– Gramatici contextuale (comportament paralel)– Gramatici de insertie (comportament paralel )

• Partea a doua: Aspecte tehnice– Modele de arhitecturi paralele;Clasificari– Metrici de performanta– Proiectarea algoritmilor paraleli– Exemple de algoritmi paraleli

Bibliografie

• Handbook of Formal Languages (eds. Roszenberg and Salomaa )

• Marcus Contextual grammars (Gh. Paun)• L-systems (Roszenberg and Salomaa)• www.*.*• A. Grama, A. Gupta, G. Karypis, V. Kumar: Introduction to

Parallel Computing, Second Edition, 2003, AddisonWesley.

• Ian Foster: Designing and Building Parallel Programs, 1995, Addison Wesley http://wotug.kent.ac.uk/parallel/books/addison-wesley/dbpp/

• Dana Petcu (@Universitatea de Vest Timisoara), Procesare paralela, Ed. Eubeea Timisoara, 2001 http://www.info.uvt.ro/~petcu

Cresterea vitezei de calcul, prin:• Cresterea performantelor procesoarelor

secventiale: – Dezavantaje: cost mare al fabricarii unui procesor de

inalta performanta, Limitari tehnologice la un moment dat

• Calcul paralel: Utilizarea in paralel a mai multor CPU – Avantaje: cost - utilizarea mai multor procesoare

ieftine fiecare in parte. – Dezavantaje: necesitatea de a dezvolta noi medii de

lucru, noi algoritmi

Avantajele calculului paralel

• “mai repede”– Exemplu problema: sortarea a 10 milioane de intregi

• PC Pentium: 50 sec• CM5 cu 1024 procesoare: 0.2 sec

• “mai mult”– Exemplu problema: inmultirea a 2 matrici de

dimensiuni mari• PC cu memorie 512MB: dimensiune maxima a matricilor

8192*8192 (pentru elem de tip double – 8 octeti)• Paragon cu 1024 procesoare cu 64MB fiecare: dimensiune

maxima a matricilor: 92000*92000

Modul de gandire paralel

• Paralelizare: trecerea de la modul de gandire secvential la modul de gandire paralel

• Exemplu problema: Distribuirea formularelor de examen intr-un amfiteatru cu N=100 studenti

• Solutie secventiala: Instructorul ia teancul cu N formulareWhile (exista studenti nevizitati) {

Viziteaza un student inca nevizitatInmaneaza formular}

Dezavantaj: durata mare de timp; studentii sunt in starea “idle” in tot acest interval

Modul de gandire paralel (cont)

• Solutie paralela: instructorul inmaneaza teancul de formulare unui student; Acesta retine un formular si da teancul mai departe unui alt student

• Instructorul:Viziteaza primul student;Inmaneaza teancul cu formulare;

Prezinta explicatii;• Studentul:

While (nu a primit inca teancul de formulare) Audiaza explicatiile instructorului;

Retine un formular;If (exista un student care nu a primit formulare)

inmaneaza teancul de formulare studentului;

Modul de gandire paralel (cont)

• Solutie paralela 2: se poate imbunatati timpul daca instructorul inmaneaza o cate o parte parte din teancul de formulare(N/r) primului student din marginea celor r randuri. Fiecare student retine o copie si inmaneaza restul teancului studentului urmator de pe randul lui.

• Dezavantajul solutiei: depinde de topologia amfiteatrului – presupune banci egale organizate pe randuri.

• Ce se intampla daca amfiteatrul este unui semicircular ?

Modul de gandire paralel (cont)

• Solutie paralela 3: pentru un amfiteatru de forma semicirculara:

Domenii de aplicatii

• Aplicatii tipice: cele care necesita procesari complexe pe volum mare de date– Prognoza meteo– Inteligenta artificiala: retele neuronale,

cautare– Procesare automata a limbajului Natural,

Computaional Linguistics– Bioinformatica– Brain Computing– Motoare de cautare

Exemplu – prognoza meteo

• Modelarea atmosferica:– Marimi caracteristice: {temperatura-1dimens,

presiune-1dimens, umiditate-1dimens, vant-3dimensional}=6 valori

– In functie de (longitudine, latitudine, altitudine, timp)– Problema: prezicerea valorilor acestor marimi la

momentul T pornind de la valorile lor la momentul 0– Evolutia acestor marimi e data de un set de ecuatii

diferentiale

Exemplu- prognoza meteo (cont)

• Comportamentul acestor ecuatii in spatiul continuu este aproximat prin comportamentul lor pe o multime finita de puncte echidistante din spatiu => metoda elementelor finite

• Spatiul: aproximat cu suprafata desfasurata a pamantului * altitudinea maxima

• Spatiul este descompus in celule 3-dimensionale de volum egal

Exemplu- prognoza meteo (cont)

•Pentru fiecare celula de volum (punct pe grid) se retine un vector de 6 valori reprezentand marimile caracteristice•Problema: prezicerea valorilor acestor marimi la momentul T pornind de la valorile lor la momentul 0

Exemplu- prognoza meteo (cont)

• Pentru fiecare punct de pe grid, valorile de la momentul t+1 sunt calculate pe baza valorilor vecinilor sai la momentul t

• Calculul necesita T pasi, pentru t, 0<t<T

Exemplu- prognoza meteo (cont)

• Numarul punctelor de pe grid: – supraf pamantului aprox 500 milioane km2 *

altitudine 10 km– Consideram o celula de volum 1 km3– => 5*10^9 celule (puncte pe grid)

• Volumul de date: starea curenta a variabilelor = 6 valori reale * 8 octeti => 24*10^10 octeti

• Calculul de actualizare a starii curente a variabilelor pentru un volum: aprox 500 instructiuni

Exemplu- prognoza meteo (cont)

• Durata si acuratetea prezicerii: 2 zile, cu o acuratete de 30 minute => aprox 100 pasi de calcul

• Numar total de instructiuni: 5*10^9*500*100=25*10^13

• Calculator secvential: aprox 10^9 instructiuni/sec => 25*10^4 sec = aprox 69 ore necesare pentru calculul secvential (… intervalul prognozei fiind de 48 de ore)

Ce este calculul paralel ?

• Algoritm paralel = algoritm care permite efectuarea simultana a mai multor operatii– Descompunerea unei probleme in

subprobleme care se executa in paralel pe mai multe procesoare

• “Calculator paralel”= un set de procesoare capabile sa coopereze pentru rezolvarea unor probleme de calcul ([Foster])– Supercalculatoare paralele, statii de lucru

multiprocesor, retele de calculatoare, …

• Algoritm secvential: specifica executia secventiala a unui set de instructiuni

• Proces: executia unui program secvential• Algoritm paralel: specifica mai multi algoritmi

secventiali care pot fi executati simultan ca procese paralele (concurente)

Programare paralela concurenta

Calcul paralel Calcul distribuit

Sistem de calcul paralel Sistem distribuit

Procesoarele sunt, de obicei, de acelasi tip

Procesoarele sunt, de obicei, eterogene

Procesoarele sunt, de obicei, distribuite pe o arie geografica mica

Procesoarele sunt, de obicei, distribuite pe o arie geografica mare

Scopul: executarea unor calcule mai rapid decat cu un singur procesor

Scopul: utilizarea in comun a resurselor disponibile, transmiterea informatiilor. Probleme specifice: fiabilitate, securitate

Proiectarea algoritmilor paraleli

• Identificarea subtaskurilor care pot fi realizate in paralel

• Maparea taskurilor pe mai multe procesoare

• Impartirea si distribuirea datelor intre taskuri

• Coordonarea activitatii si comunicarii intre procesoare

Performantele algoritmilor paraleli

• Metrici:– Accelerarea obtinutat prin paralelizare (de cate ori ruleaza mai

repede in paralel pe N procesoare fata de executia secventiala)– Eficienta – daca accelerarea este obtinuta cu un efort rezonabil

din punct de vedere al resurselor (procesoarelor) aditionale• Maximizarea concurentei (cat mai multe operatii

efectuate in paralel)• Minimizarea comunicarilor cauzate de

– Date ne-locale– Transfer de rezultate intermediare intre procesoare– Sincronizarea intre procese

• Distributia buna a datelor, pentru minimizarea comunicarilor

• Echilibrarea incarcarii procesoarelor, pentru minimizarea timpilor de inactivitate

Indian grammar

K-grammar