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


SyllabusIntroducere

Coninutul cursuluiBibliograe recomandat

Table of Content 2




SyllabusIntroducere


Table of Content 3




SyllabusIntroducere


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".


SyllabusIntroducere


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.


SyllabusIntroducere


Table of Content 6




SyllabusIntroducere


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


SyllabusIntroducere


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


SyllabusIntroducere


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


SyllabusIntroducere

Noiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm

Table of Content 10




SyllabusIntroducere


Table of Content 11




SyllabusIntroducere


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.


SyllabusIntroducere



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).


SyllabusIntroducere



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.


SyllabusIntroducere



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.


SyllabusIntroducere



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.


SyllabusIntroducere



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


SyllabusIntroducere


Table of Content 18




SyllabusIntroducere


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!


SyllabusIntroducere


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.


SyllabusIntroducere


Table of Content 21




SyllabusIntroducere


Exemplu de paralelizare 22

Problem.

S se determine cel mai mare numr dintr-un vector A de n

componente numerice!


SyllabusIntroducere



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)


SyllabusIntroducere




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)


SyllabusIntroducere






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)


SyllabusIntroducere



Algorithm 4: Maximul unui vector alg. paralel, EREW PRAM



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]


SyllabusIntroducere



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)).


SyllabusIntroducere



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).


SyllabusIntroducere



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.


SyllabusIntroducere



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.


SyllabusIntroducere


Mulumesc... 31

V mulumesc pentru atenia acordat!


SyllabusContinutul cursuluiBibliografie recomandata

IntroducereNotiuni fundamentalePrincipiul de alocare a lui BrentExemplu de paralelizare a unui algoritm

Date post:	20-Nov-2015
Category:	Documents
Upload:	reb2009
View:	216 times
Download:	0 times

Curs 01

Documents