c1-ccalculparalel
25
description
-
Transcript of c1-ccalculparalel
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
