Curs 01
description
Transcript of Curs 01
-
SyllabusIntroducere
Algoritmi paraleli
Alexandru HORVTH
Petru Maior University
Tg-Mure
Note de cursCurs 1. Syllabus Introducere
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Table of Content 1
1 SyllabusConinutul cursuluiBibliograe recomandat
2 IntroducereNoiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Coninutul cursuluiBibliograe recomandat
Table of Content 2
1 SyllabusConinutul cursuluiBibliograe recomandat
2 IntroducereNoiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Coninutul cursuluiBibliograe recomandat
Table of Content 3
1 SyllabusConinutul cursuluiBibliograe recomandat
2 IntroducereNoiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Coninutul cursuluiBibliograe recomandat
Coninutul cursului 4
Curs 1. Noiuni de baz. Principiul de alocare a lui Brent.Exemplu de algoritm paralel.
Curs 2. MPI, OpenMP, MATLAB
Curs 3. Algoritm paralel de interclasare.
Curs 4. Algoritm paralel de sortare.
Curs 5. Algoritm paralel de calcul al prexului.
Curs 6. Algoritm paralel de "bucket sort".
Curs 7. Algoritm paralel de "radix sort".
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Coninutul cursuluiBibliograe recomandat
Coninutul cursului 5
Curs 8. Algebra liniar. Matrici "dense".
Curs 9. Algoritm paralel de multiplicare a matricilor.
Curs 10. "Sparse Linear Algebra".
Curs 11. Algoritmi paraleli de factorizare a matricilor.
Curs 12. Algoritm paralel de factorizare SVD.
Curs 13 FFT paralel.
Curs 14 Algoritmi geometrici paraleli. Mesh generation.
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Coninutul cursuluiBibliograe recomandat
Table of Content 6
1 SyllabusConinutul cursuluiBibliograe recomandat
2 IntroducereNoiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Coninutul cursuluiBibliograe recomandat
Bibliograe 7
1 L.G. Valiant, General Purpose Parallel Architectures,Handbook of Theoretical Computer Science, Elsevier SciencePublishers B.V. (1990) pp. 945-972
2 C.P.Kruskal, L.Rudolph, M.Snir, A Coplexity Theory forEcient Parallel Algorithms, TCS 71 (1990) pp. 95-132.
3 R.E.Ladner, M.J.Fischer, Parallel Prex Computations,J.ACM, 27 (1980) pp. 831-838
4 Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest,and Cliord Stein. Introduction to Algorithms. 2nd ed.Cambridge, MA: MIT Press. ISBN: 0262032937
5 G.E Blelloch, Vector Models for Data-Parallel Computing,MIT-Press, 2 Cambridge, 1990
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Coninutul cursuluiBibliograe recomandat
Bibliograe 8
6 Atallah M.J. (ed.) Algorithms and theory of computationhandbook (CRC, 1999), ISBN 0849326494, 1265pp
7 Gacs P., Lovasz L. Complexity of algorithms, lecture notes,1999, 180pp
8 Greene D.H., Knuth D.E. Mathematics for the analysis ofalgorithms, 3ed., Burkhauser, 1990, 139pp
9 Wilf H. S., Algorithms and Complexity, 1ed, 1994, 139pp10 Khuller S. Advanced algorithms, lecture notes, web draft,
1994, pages ordered backwards, 112pp
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Coninutul cursuluiBibliograe recomandat
Bibliograe 9
11 Donald E. Knuth, Tratat de programarea calculatoarelor:Sortare i cutare, Editura Tehnic, Bucureti, 1976, III 6727 1
12 Ioan Marusciac, Teoria algoritmilor, Universitatea"Babe-Bolyai"- Cluj, III 287 3
13 Metode i strategii de proiectare a algoritmilor (alias tehnici deprogramare) Buletinul tiinic al Universitii "Petru Maior"din Trgu-Mure, Vol.XI-XII, 1998-1999 P II 272 2
Alte resurse1 Programul OpenCourseWare, MIT, USA
http://ocw.mit.edu/OcwWeb/Mathematics/index.htm2 Applied Parallel Algorithms, MIT, USA
http://ocw.mit.edu/OcwWeb/Mathematics/18-337JSpring-2005/CourseHome/index.htm
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Table of Content 10
1 SyllabusConinutul cursuluiBibliograe recomandat
2 IntroducereNoiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Table of Content 11
1 SyllabusConinutul cursuluiBibliograe recomandat
2 IntroducereNoiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Noiuni fundamentale 12
Algoritmii pot executai/implementati pe un:
calculator echipat cu un procesor i o memorie (maina Turing)
calculator echipat cu mai multe (teoretic orict de multe)procesoare i o memorie comun (procesoarele comunic ntreele doar prin intermediul memoriei comune)
Modele de calculatoare: servesc la analiza algoritmilor.Exist dou modele de baz:
RAM (Random Access Machine) - Procesorul execut secvenialpaii unui algoritm/instruciunile i poate accesa orice adresade memorie, nu doar adrese consecutive.
PRAM (Parallel Random Access Machine) - Procesoarele lucreazsimultan i pot accesa independent orice adres din memoriacomun.
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Noiuni fundamentale 13
Un pas al unui algoritm are urmtoarele faze de execuie:
citirea coninutului unei adrese de memorie n procesor,
efectuarea unei operaii de baz n procesor,
scrierea coninutului unui registru al procesorului n memorie,la o anumit adres.
n analiza timpului de rulare al algoritmilor prima i a treia faz(precum i alte operaii de tip comunicare) se ignor, respectiv seconsider de cost (1).
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Noiuni fundamentale 14
n funcie de modul de tratare al conictul la citirea/scriereaaceleiai adrese de memorie de ctre mai muli procesori n acelaimoment, modelul PRAM poate :
La citire:
ER (Exclusiv Read) Un singur procesor poate citi o adres dememorie la un moment dat.
CR (Concurrent Read) Mai multe procesoare pot citi o aceeaiadres de memorie simultan.
La scriere:
EW (Exclusiv Write) Un singur procesor poate scrie o adres dememorie la un moment dat
CW (Concurrent Write) Mai multe procesoare pot scrie o aceeaiadres de memorie simultan.
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Noiuni fundamentale 15
Modelul concurent la scriere CW poate de tipul:
CW prioritar Conictul se rezolv pe baza unei prioritialocate ecrui procesor: procesorul cu prioritatea cea maimare va scrie la adresa de memorie respectiv.
CW comun Scrierea simultan la aceai adres este permisdoar dac procesoarele concurente scriu aceeai valoare. n cazcontrar se raporteaz eroere de scriere.
CW arbitrar Procesorul care scrie este selectat arbitrar dintreprocesoarele concurente.
CW combinat Valoarea scris n memorie este o combinaie(de exemplu sum) a valorilor pe care procesorele concurentevor s o scrie la adresa respectiv.
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Noiuni fundamentale 16
Cele mai importante modele sunt:
CREW PRAM
EREW PRAM
CRCW PRAM (cu specicaia tipului de CW)
Arhitectura concret a sistemelor de calcul tinde s realizeze unuldin aceste modele.
Rezultatele analizei unui algoritm pe un model de calcul paralelsunt relevante pe arhitecturile concrete.
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Noiuni fundamentale 17
Algoritmii pot :
Secveniali avem o singur unitate de calcul
Paraleli paii se execut secvenial, dar dispunem de unnumr orict de mare de uniti de calcul care lucreazsincronizat
Calculul (respectiv comunicarea cu unitile de calcul) poate :
Sincron Calcul paralel
Asincron Calcul distribuit
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Table of Content 18
1 SyllabusConinutul cursuluiBibliograe recomandat
2 IntroducereNoiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Principiul de alocare a lui Brent 19
Teorem
Dac un calcul paralel are k faze 1, 2, . . . , k, care necesitt1, t2, . . . , tk uniti de timp, i care folosesc succesiv un numr dep1, p2, . . . , pk procesoare, atunci acest calcul poate efectuatfolosind p procesoare ntr-un timp
O(a/p + t),
unde
a = p1t1 + p2t2 + + pktk ,
t = t1 + t2 + + tk ,
iar numrul p al procesoarelor poate ales arbitrar!
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Principiul de alocare a lui Brent 20
Demonstraie.
n faza i cele p procesoare existente trebuie s efectueze muncacelor pi procesoare necesare algoritmului.
Fiecrui procesor i revine deci n faza i munca a dpi/pe pi/p + 1procesoare, aadar faza i necesit cel mult un timp c(pi/p + 1)ti ,unde c este o constant independent de i .
Toate fazele la un loc necesit aadark
1(pi/p + 1)ti = O(a/p + t) timp de execuie.
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Table of Content 21
1 SyllabusConinutul cursuluiBibliograe recomandat
2 IntroducereNoiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Exemplu de paralelizare 22
Problem.
S se determine cel mai mare numr dintr-un vector A de n
componente numerice!
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Exemplu de paralelizare 23
Algorithm 1: Maximul unui vector - secvenial
Input : A, n, vectorul A de numere ntregi, de lungime n
Output: m = max{A[i ] | i = 1 . . . n}
function Max(A, n)
m for i = 1...n do
m max(m,A[i ])return m
m =Max(A, n)
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Exemplu de paralelizare 24
Algorithm 2: Maximul unui vector - secvenial
Input : A, n, vectorul A de numere ntregi, de lungime n = 2k
Output: m = max{A[i ] | i = 1 . . . n = 2k}
function Max(A, a, b)
if a == b thenreturn A[a]
elsereturn
max(Max(A, a, [(a + b 1)/2]),Max(A, [(a + b + 1)/2], b))
m =Max(A, 1, n)
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Exemplu de paralelizare 25
Algorithm 3: Maximul unui vector - secvenial
Input : A, n, vectorul A de numere ntregi, de lungime n = 2k
Output: m = max{A[i ] | i = 1 . . . n = 2k}
function Max(A, n)
for i = 1...n/2 doB[i ] max(A[2i 1],A[2i ])
if n == 2 thenreturn B[1]
elsereturn Max(B, n/2)
m =Max(A, n)
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Exemplu de paralelizare 26
Algorithm 4: Maximul unui vector alg. paralel, EREW PRAM
Input : A, n, vectorul A de numere ntregi, de lungime n = 2k
Output: m = max{A[i ] | i = 1 . . . n = 2k}
function Max(A, n)[p1, p2, . . . , pn/2]
for i = 1...n/2 dopi : B[i ] max(A[2i 1],A[2i ]); #execuie paralel
if n == 2 thenreturn p1 : B[1]
elsereturn Max(B, n/2)[p1, p2, . . . , pn/4]
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Exemplu de paralelizare 27
Analiza timpului de rulare al algoritmului paralel.
Notm cu t(n) timpul de rulare al algoritmului, pentru vectorul delungime n. Avem:
t(n) = t(n/2) + O(1), i t(2) = O(1).
Din teorema Master rezult:
t(n) = O(log(n)).
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Exemplu de paralelizare 28
Deniie.
Funcia w(n) = p(n) t(n) se numete efortul/work algoritmuluiparalel (unde p(n) este numrul procesoarelor care lucreaz nparalel). Algoritmul paralel se numete optimal, dac efortul sueste n clasa asimptotic a celui mai performant algoritm secvenial
cunoscut pentru problema respectiv.
Observaie.
Algoritmul Max paralel (4) nu este optimal.
ntr-adevr, efortul algoritmului este n clasa O(n log(n)), n timpce algoritmul secvenial are efortul(timpul) liniar O(n).
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Exemplu de paralelizare 29
Challenge.
Una din cele dou deziderate echivalente:
gsirea algoritmului paralel optimal, cu timpul de rulare cel
mai mic, sau
gsirea algoritmului paralel optimal, cu numrul cel mai mic de
procesoare.
Observaie.
Se poate demonstra c cele dou deziderate sunt echivalente.
Ideea de baz: numrul procesoarelor i timpul de rulare alalgoritmului paralel sunt invers proporionale.
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Exemplu de paralelizare 30
Aplicaie a principiului de alocare a lui Brent:
n algoritmul Max paralel (4) numrul fazelor este log(n), avndecare un timp de rulare unitar O(1), iar numrul procesoareloreste pe rnd n/2, n/4, . . . , aadar
a = n/2 1 + n/4 1 + + 1 1 = n.
Folosind p procesoare, timpul de rulare va
O(n/p + log(n)).
Rezult de aici
Teorem
Cel mai mare element al unui vector de lungime n poate calculat
pe un calculator EREW PRAM echipat cu p = O(n/ log(n))procesoare, n timpul O(log(n)). Aceste valori sunt optimale.
Alexandru HORVTH Algoritmi paraleli
-
SyllabusIntroducere
Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm
Mulumesc... 31
V mulumesc pentru atenia acordat!
Alexandru HORVTH Algoritmi paraleli
SyllabusContinutul cursuluiBibliografie recomandata
IntroducereNotiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm