Complexitatea algoritmilorComplexitatea algoritmilor paralelip

Ciprian Dobreciprian dobre@cs pub rociprian.dobre@cs.pub.ro

Complexitatea algoritmilor paraleli

Ct de mult paralelism exist ntr-o aplicaie? Ct de mult paralelism exist ntr-o aplicaie? Depinde

P f f i d Performana funcie de: Timp de execuie Memorie ocupat

N d Nr. de procesoare Scalabilitate Eficien Fiabilitate Fiabilitate Toleran la defecte Portabilitate CosturiCosturi

Exemplu: sortarea pe un vector de procesoare

Sortarea pe un vector de procesoare

intrare

Fi i l l i i l

intrare

ieire

Fiecare procesor are o memorie local i propriul su program

Funcionare sistolicFuncionare sistolic Un ceas global comand execuia simultan a operaiilor Fiecare procesor realizeaz la fiecare pas:

R i d t d l i i Recepia unor date de la vecini Inspecia memoriei locale Execuia calculelor specificate de program p p g Modificarea memoriei locale Transmiterea unor date ctre vecini

Sortarea pe un vector de procesoare

intrareintrare

ieire

Vector de N procesoare 2 faze

n fiecare pas al primei faze, fiecare procesor realizeaz urmtoarele operaii:1) accept o valoare de la vecinul din stnga;1) accept o valoare de la vecinul din stnga;2) compar valoarea cu cea memorat local;3) transmite valoarea mai mare vecinului din dreapta;) p ;4) memoreaz local valoarea mai mic.

Paii algoritmului de sortare

3 0 5 1 2 iniial

3 0 5 1 pasul 12

3 0 5 pasul 221

comparatie

3 0 pasul 3215 1

comparatie

3 pasul 421503 pasul 421

comparatie

0

comparatie

Paii algoritmului de sortare

Dup pasul 9:

53210

Pentru N valori, faza 1 dureaza 2N-1 pasi

Faza a doua

Valorile ordonate sunt scoase prin celula din stngap g Variante:

1. fiecare procesor ncepe s transmit spre stnga, imediat ce numerele sunt sortate;

2. cunoscnd poziia sa din vector i numrnd valorile inspectate, fiecare procesor calculeaz momentul cnd ncepe s transmit spre stnga;

3 l di d t t it t i di t3. procesorul din dreapta ncepe s transmit spre stnga imediat ce primete o valoare; toate celelalte ncep s transmit spre stnga imediat ce primesc o valoare din dreapta;

4. fiecare procesor ncepe s transmit spre stnga imediat ce nu mai4. fiecare procesor ncepe s transmit spre stnga imediat ce nu mai primete o valoare dinspre stnga.

Complexitate: metoda 3 => 4N-3 pasi Variantele 1 i 2 impun cunoaterea:

P iti i l i t !!!e oda 3 3 pas

metoda 4 => 3N-1 pasi -Pozitiei procesoarelor in vector !!!-Contorizarea valorilor !!!

Msuri de performan

Timpul total T necesar execuiei Timpul total T necesar execuiei Numrul de procesoare utilizate P

n algoritmul prezentat P = N i T = O(N) n algoritmul prezentat, P = N i T = O(N). Acceleraia S (speedup)

S = G/TS = G/T unde G este timpul de execuie al celui mai rapid algoritm G este timpul de execuie al celui mai rapid algoritm

secvenial n algoritmul precedent,

S= O(N log N)/ O(N) = O(log N).

Msuri de performan

Acceleraia liniar S = O(P) Acceleraia liniar S = O(P) Exemplu ???

Ideal ar fi ca algoritmul paralels se execute de P ori mai rapid dect

cel mai bun algoritm secvenial

Cea mai bun valoare a acceleraiei ce se poate obineob e

Justificare:Dac un program se poate executa n T pai pe P p g p p p

procesoare, putem oricnd s rulm respectivul algoritm n mod secvenial n TP pai

G

Msuri de performan (2)

Se poate obine mereu acceleraie liniar ?Se poate obine mereu acceleraie liniar ? Topologia sistemului impune uneori restricii de timp (ex: liniar O(N),

arbore O(logN)) Seciuni secveniale Legea lui AmdahlSeciuni secveniale Legea lui Amdahl

Presupunnd c procentul f din totalul calculelor trebuie s se desfoare secvenial

T = f * G + (1-f) * G / PT f G (1 f) G / P =>

S = 1 / (f + (1-f) / P) >=>

S Un program paralel nu va rula mai repede dect suma poriunilor

sale secveniale indiferent de nr de procesoare pe care se executsale secveniale, indiferent de nr. de procesoare pe care se execut

T >= f * G

Msuri de performana (3)

the effort expended on achieving high parallel processing rates is wasted unless it is accompanied by

hi i i l i fachievements in sequential processing rates of very nearly the same magnitude. Amdhal, 1967

speedup should be measured by scaling the problem to the number of processors not by fixing theproblem to the number of processors, not by fixing the problem size. Gustafson, 1988

Msuri de performan (4)

Costul C T*P Costul C = T*P n exemplu - C = O(N2) Caracterizeaz ineficiena datorat nefolosirii complete a Caracterizeaz ineficiena datorat nefolosirii complete a

procesoarelor Eficiena E = G/C

E = G/C = G/(TP) = S/P n exemplu - E = O((log N)/N)

Scalabilitatea msur a accelerrii date de adugarea mai multor msur a accelerrii date de adugarea mai multor

procesoare

Calculul detaliat al complexitii

P l li f t ti i Paralelizarea se face pentru atingerea unui timp de execuie ct mai redus

Cum putem ti dac un algoritm paralel este optim sau nu?

Rspunsul depinde de modelul de evaluare adoptatevaluare adoptat

n algoritmul anterior pasul algoritmului reprezenta o operaie asupra unor cuvintereprezenta o operaie asupra unor cuvinte

Calculul detaliat al complexitii Trecere la modelul "bit"

Fiecare procesor opereaz pe 1 bit Operaia principal compararea a dou numere "s" i "d" Operaia principal compararea a dou numere "s" i "d" Topologie arborescent

pas 3pas 2pas 1msb

=

=0 0pas 3pas 2pas 1

=s

0 0

s s1 0

s dlsb d0 1

Calculul detaliat al complexitii

msb s0 0

pas 3pas 2pas 1

msb

ss

s0 0

0 0

s

s0 0

1 0

lsb

s

s

s1 0

0 1

i t i t i 2*l k i

s dlsb s0 1

comparaia terminat in 2*log k pai 2k-1 procesoare

Calculul detaliat al complexitii

Algoritmul de sortare devine:Algoritmul de sortare devine:

Intrare

I i

Reea de (2k-1)*N procesoare

Ieire

Reea de (2k 1) N procesoare

Test: Ci pai sunt necesari n aceast abordare pentrufaza 1?

(2N-1)*2*logK pai pt. faza 1

Abordare pipeline Algoritm mai bun de comparare Tablou liniar de k procesoare pe bit n timp ce un procesor compar o pereche de bii a dou numere n timp ce un procesor compar o pereche de bii a dou numere

succesive, procesorul de sub el lucreaz cu biii mai puin semnificativi ai perechii de numere anterioare

La fiecare pas, un procesor primete la intrare un bit, iar de la f f

p , p p ,procesorul de deasupra o informaie asupra comparaiei fcute de el la pasul anterior: s dac numrul de la intrare este mai mare d dac numrul memorat este mai mare = - dac cele dou numere sunt egale

Dac primete s, procesorul transmite bitul de la intrare la ieireDac primete s, procesorul transmite bitul de la intrare la ieire i transmite s n jos

Dac primete d, procesorul transmite bitul memorat la ieire i transmite d n jos

Dac primete =, transmite bitul mai mare la ieire, memoreaz bitul mai mic i transmite n jos s, d, sau = n mod corespunztor

Abordare pipeline3 0 5 1 2 0 11 0 0 0 1 [ ] 1 0 [0] -> 0 1

/ / / / / / s /1 0 1 1 0 [ ] 0

iniial dup pasul 4--------------------------------------------------------------------------------------------------------------------------

0 0 1 0 [0] [0] -> 0 0 1 0/ / / / / // / / / = / /

1 0 0 0 1 [ ] 1 [0] -> 0 0 1/ / / / = / /1 0 1 1 0 [ ] 1 0 [1] -> 1 0

dup pasul 1 dup pasul 5-------------------------------------------------------------------------------------------------------------------------

Complexitate:(k-1)+(2N-1) pai faza 1

0 0 1 [0] -> 0 [0] -> 0 0 1 0/ / / = / / /

1 0 0 0 [1] [0] -> 1 0 0 1/ / / s / / /

1 0 1 1 0 [ ] 1 [0] -> 1 1 0 dup pasul 2 dup pasul 6dup pasul 2 dup pasul 6

-------------------------------------------------------------------------------------------------------------------------0 0 [0] -> 1 0 [0] -> 0 0 1 0

/ / s / / / / 1 0 0 [0] -> 1 [0] -> 1 0 0 1

/ / d / / / / 1 0 1 1 [0] [0] -> 1 1 1 0

dup pasul 3 dup pasul 7-------------------------------------------------------------------------------------------------------------------------rezultat -> 0 3 1 5 2

Limite inferioare

Lrgimea benzii pentru introducerea datelorLrgimea benzii pentru introducerea datelor ex: N numere se introduc n N pai

Diametrul reelei distana maxim ntre oricare dou noduri ex: pentru un grid de k*N noduri, diametrul este N+k-2ex: pentru un grid de k N noduri, diametrul este N k 2

Lrgimea biseciei reelei numrul minim de legturi care t b i d t t t i d trebuie ndeprtate pentru a mpri reeaua n dou subreele separate, avnd acelai numr de noduri interschimbarea datelor ex: k*N/2 bii "trec" prin bisecia de lrgime k n minim N/2

pai

Limite inferioare (2)

procesorul rdcin are log N celule

procesoare intermediare

11

10

01

00

procesoare frunza cu

14011

910

510

110 cte K

celule

Diametrul reelei este 2*log N + 2*K - 2 Lrgimea benzii de intrare a datelor este K*N Lrgimea biseciei este 1 dac log N = 1 i 2 n celelalte cazuri

14951

Lrgimea biseciei este 1, dac log N = 1 i 2 n celelalte cazuri Sortare in O(KN) pai dar, pentru K =1 exist algoritmi in O(log N)

Modele generale

Analiza complexitii algoritmilor presupune folosirea unui Analiza complexitii algoritmilor presupune folosirea unui model formal: particulare (ex: SIMD cu memorie locala)p ( ) abstracte: Modele orientate spre categorii de maini paralele:Maini cu memorie localaMaini cu memorie modularaMaini PRAMMaini PRAM

Modele orientate spre algoritmi:Modelul grafurilor orientate aciclice (work depth)

Modelul grafurilor orientate aciclice

M d l d f ( k d th) Model de graf (work depth) fiecare intrare este reprezentat ca un nod fr arce de intrare fiecare operaie este reprezentat ca un nod ale crui arce de p p

intrare provin de la nodurile care reprezint operanzii o ieire este reprezentat ca un nod fr arce de ieire.

a[1]+a[2]

+a[3]

a[4] +

+a[5]a[6] +

+

a[7]a[8]

+

Modelul grafurilor orientate aciclice (2)

Modelul este independent de orice arhitectur i orice Modelul este independent de orice arhitectur i orice numr concret de procesoare.

Pune n eviden: lucrul efectuat de algoritm (numrul total de operaii) adncimea (lungimea celui mai lung lan de

dependene secveniale din algoritm). paralelismul algoritmului

=> lucru / adncime=> lucru / adncime nsumarea a n numere

lucrul = n-1lucrul n 1 adncimea = log n

Calculul complexitii

var a, b: array [1:n] of real;/* pp n = 2k */ar lvar s: real;

fa i := 1 to n do in parallel b[i] := a[i] af;fa h := 1 to log n dofa h : 1 to log n do

fa i := 1 to n/2h do in parallelb[i] := b[2*i-1] + b[2*i]

afaf;s := b[1];

T( ) 1 l 1 O(l )T(n) = 1 + log n + 1 = O(log n)W(n) = n + h = 1, log n n/2h + 1 = O(n)

Principiul de planificare pentru PRAM

Teorema lui Brent Pentru un algoritm care ruleaz n T(n) uniti de timp executndPentru un algoritm care ruleaz n T(n) uniti de timp, executnd

W(n) operaii, se poate obine o adaptare a algoritmului care s ruleze pe p procesoare PRAM n cel mult inf(W(n)/p) + T(n) uniti de timp p

Justificare Fie Wi(n) numrul de operaii executate n unitatea i de timp.

P t fi i 1 i T( ) W ( ) ii t W ( )/ Pentru fiecare i, 1

Principiul de planificare pentru PRAM (2)

var A, B: array [1:n] of real; /* n = 2k si p = 2q */var S: real; l: int := n/p;fa s := 1 to p do in parallel

fa j := 1 to l -> B[l*(s-1)+j] := A[l*(s-1)+j] af;fa h := 1 to log n ->

if k-h-q >= 0 ->fa j := 2k-h-q(s-1) + 1 to 2k-h-q s ->

B[j] := B[2*j-1] + B[2*j]af

[] k-h-q < 0 ->if s B[s] := B[2*s-1] + B[2*s] fi

fiafif s = 1 -> S := B[1] fi

af;

Cerine pentru algoritmi PRAM eficieni

P < (di i bl i) P d ti P < n (dimensiunea problemei), P adaptiv (dependent de dimensiunea problemei) Ex: P(n) funcie subliniar de n rdcina Ex: P(n) funcie subliniar de n rdcina

ptrat de n

Tp(n) mic, adaptiv, invers proporional cu P

C minim

Implementare pentru reele de procesoare

Topologie hipercub: p 2d procesoare p = 2d procesoare,

indexate de la 0 la p-1 reprezentarea binar a p

lui i, 0

Implementare pentru reele de procesoare

P110 P111

P011P010P000 P001 P010 P011 P100 P101 P110 P111

P011P010

P110P100 P110P100

P000 P001

Implementare pentru reele de procesoare (2)

Algoritmul de nsumare:fiecare element A[i] al tabloului cu n elemente este memorat ntr-un

nod P[i] al hipercubului cu n noduri (n=2d) rezultatul acumulat in A[0]

Paii:A[0] := A[0] + A[4]A[1] := A[1] + A[5]A[1] := A[1] + A[5]A[2] := A[2] + A[6]A[3] := A[3] + A[7]

A[0] := A[0] + A[4] + A[2] + A[6]A[1] := A[1] + A[5] + A[3] + A[7]

A[0] := A[0] + A[4] + A[2] + A[6] + A[1] + A[5] + A[3] + A[7]

Implementare pentru reele de procesoare (2)

var A: array [0:n 1] of real; /* n = 2d */var A: array [0:n-1] of real; /* n = 2d */fa i := 0 to n-1 do in parallel

fa l := d-1 to 0 ->if i

A[i] := A[i] + A[i(l)]fi

afaf

Obs: i(l) denot indexul obinut din i prin complementarea bitului l

Complexitatea: O(log n)

Sumar

C l it t l it il l li Complexitatea algoritmilor paraleliMsuri de performan Calculul detaliat al complexitii Limite inferioare

Sortarea pe un vector de procesoareModele generice Modele genericeModelul grafurilor orientate aciclice Principiul de planificare pentru PRAM

ntrebri?