APD - Note Curs - 5 SIMD

8/8/2019 APD - Note Curs - 5 SIMD

1/17

61

Capitolul 4. Dezvoltarea aplicaiilor pentru calculatoare SM SIMD

O clas important de sisteme paralele este cea care corespunde modelului SIMD cumemorie partajat (Shared Memory SIMD). Ele sunt cunoscute i sub denumirea dePRAM (Parallel Random Access Machines). n funcie de modul de acces lamemorie pentru operaiile de citire i scriere, sistemele SM SIMD se subdivid n:- EREW (Exclusive Read Exclusive Write);- CREW (Concurrent Read Exclusive Write);- ERCW (Exclusive Read Concurrent Write);- CRCW (Concurrent Read Concurrent Write).

Descrierea urmrete prezentarea unor metode generale de dezvoltare a algoritmilor

paraleli (partiionarea, divide et impera) i a unei abordri posibile pentru obinereaalgoritmilor cost-optimali.

Cteva caracteristici importante ale algoritmilor SM SIMD sunt urmtoarele: algoritmii indic aciunile executate de procesoare (n general, fiecare procesoreste dedicat execuiei aciunilor unui proces) algoritmii expliciteaz separat aciunile de citire i cele de scriere (pentru a puteaaprecia costul operaiilor n raport cu categoriile de sisteme PRAM menionate) lansarea i terminarea proceselor au "overhead" redus (instruciuni co...oc pot fiincluse n cicluri) algoritmii se ncadreaz, de obicei, n clasa "fine grain" (granularitate fin).

Aceste caracteristici sunt subliniate prin notaia specific PRAM, care a fostprezentat n capitolul 2 al lucrrii.

4.1. Proprietile (dorite ale) algoritmilor paraleli

Numr de procesoare

n cele ce urmeaz, n reprezint dimensiunea problemei, iar p(n) este numrul de procesoare utilizate la execuia algoritmului. Numrul de procesoare trebuie sndeplineasc urmtoarele cerine:- p(n) trebuie sa fie mai mic dact n

Este nerealist s presupunem c avem n procesoare. Uzual se ia p(n) ca funcie

sublinear de n (de exemplu, log n sau sqrt(n))- p(n) trebuie s fie adaptiv


2/17

62

Algoritmul nu trebuie s depind de un numr fix de procesoare.

Timp de execuie

n cele ce urmeaz, t(n) este timpul de execuie n funcie de dimensiunea problemei.Condiiile sunt urmtoarele:- t(n) s fie mic,

semnificativ mai mic dect timpul de execuie al variantei secveniale- t(n) sa fie adaptiv,

i s fie invers proportional cu p(n)

Cost

n cele ce urmeaz, c(n) este costul algoritmului c(n) = t(n) * p(n). Condiiile sunturmtoarele:- c(n) s fie minim

deci algoritmul s fie cost-optimal.

Exemplu

Algoritmul de selecie a unei valori din secvena S = {s1, ..., sn}, prezentat maideparte n acest capitol, se execut pe o main EREW SM SIMD cu N procesoare,unde N


3/17

63

4.2. Dou proceduri utile

Dou operaii tipice apar n execuia algoritmilor paraleli n sisteme EREW SIMD:- fiecare procesor trebuie s citeasc coninutul unei celule din memoria comun(difuzarea unei valori);- fiecare procesor trebuie s calculeze valoarea unei funcii dependente de dateledeinute de celelalte procesoare (calcule prefix).

Difuzarea unei valori

Fie D celula din memoria comun ce trebuie difuzat celor N procesoare ale unuisistem EREW SIMD. Algoritmul BROADCAST presupune folosirea unui tablouA[1:N]. Aciunile de citire i de scriere sunt explicitate distinct i explicit ndescrierea algoritmului. Acest tratament este specific sistemelor PRAM.

procedure BROADCAST (D, N, A)

Pas 1: Procesorul P11.1. citete valoarea din D1.2. o memoreaza n propria memorie1.3. o scrie n A[1]

Pas 2: fa i := 0 to (log N -1) ->fa j := 2i+1 to 2i+1do in parallelProcesor Pj

2.1. citete valoarea din A[j-2i]2.2. o memoreaz n propria memorie

2.3. o scrie n A[j]afaf

end

Aciunile de citire i de scriere sunt specificate distinct i explicit n descriereaalgoritmului, iar paii executai sincron de procesoare sunt foarte bine precizai.

Observaii

- Deoarece numrul de procesoare care dein valoarea din D se dubleaz la fiecareiteraie, timpul de execuie este O(log N).- Dimensiunea tabloului A poate fi redus la N/2, valorile memorate n ultimul pasfiind inutile.- Utilizare tipic: difuzarea lui n, n cazul algoritmilor adaptivi.


4/17

64

Calculul sumelor prefix

Fiind dat vectorul A[1:N], fiecare procesor Pi calculeaz sumaA[1] + ...+ A[i].

Algoritmul este urmtorul:

procedure ALLSUMS (A)

fa j = 0 to log N - 1 ->fa i = 2j+1 to N do in parallel

Procesor P(i)1. obine A[i-2j] de la P(i-2j), prin memoria comun2. A[i] := A[i-2j] + A[i]

afaf

end

Observaie

- Deoarece numrul procesoarelor care termin de calculat suma parial se dubleazla fiecare pas, calculul se face n O(log N) pai folosind O(N) procesoare.

4.3. Cutarea paralel

n cele ce urmeaz, prezentm soluia unei probleme de cutare a unei valori x ntr-osecven ordonat S de n valori, pentru o main SM SIMD. Pentru simplitate,

considerm c elementele secvenei sunt toate distincte ntre ele, adic:s[1] < s[2] < ... < s[n].

Metoda secvenial de cutare binar const n compararea lui x cu elementul dinmijlocul secvenei S. n funcie de rezultatul acestei comparaii, cutarea se terminsau continu cu una din cele dou jumti separate de elementul din mijloc.Algoritmul are complexitatea O(log n).

S considerm mai nti cazul unui sistem EREW format din N procesoare,1


5/17

65

deci de ordinul O(log N) + O(log(n/N)) adic O(log n), acelai cu timpul necesar

cutrii binare pe un procesor secvenial.

n cazul unui sistem CREW, difuzarea valorii lui x se poate face ntr-un singur pas.Mai mult, se poate adopta o politic de cutare diferit, obinndu-se o performanmai bun pentru timpul de execuie.

Algoritmul se bazeaz pe mprirea, n fiecare etap, a secvenei n care se facecutarea n N+1 subsecvene de aceeai lungime. Fiecare din cele N procesoareinspecteaz o valoare s aflat n poziia dintre dou secvene adiacente. Dac xs sunt ignorate elementele mai mici ca s. Urmtorul subinterval de cutare seobine fcand intersecia subintervalelor pstrate de diferitele procesoare. Deoarecefiecare etap se aplic unei secvene de dimensiune 1/(N+1) din secvena precedent,sunt necesare O(logN+1(n+1)) etape.

P1 P2 Pi Pi+1 PN+-----------------------------------------------------------------+| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | S+-----------------------------------------------------------------+

^ ^

indici elemente ..... i(N+1)g-1 (i+1)(N+1)

g-1 ....||

dimensiune subinterval (N+1)g-1-1

Figura 4.1

Fie g cel mai mic ntreg astfel c n


6/17

66

un sistem cu N procesoare poate acoperi n doi pai o secven de lungime cel mult

n2 = (N+1)2 -1 (vezi figura 4.2).

P1 P2 PN+---------+| | | | | | n1 = N+---------+

P1 P2 PN+---------+ +-++---------+ +-++---------+ +-++---------+| | | | | | | || | | | | | | || | | | | | | || | | | | |+---------+ +-++---------+ +-++---------+ +-++---------+

||||

Figura 4.2

n general, un sistem cu N procesoare poate "acoperi" n g pai o secven de lungimecel mult ng = (N+1)

g-1. n primul pas, aceast secven este mprit n subsecvenede ng-1 = (N+1)

g-1-1 elemente, procesorul Pi inspectnd elementul din poziiai*(N+1)g-1 (considerand c primul element are poziia 1). Dac primul element areindicele q, atunci poziia care corespunde lui Pi este (q-1)+i*(N+1)g-1.

Ca urmare, dat fiind lungimea n a unei secvene de numere, numrul de pai g aiprocedurii de cutare rezult din relaia n= n+1, adic 4g >= 16. Rezult g=2. Lungimea unei subsecvene n primul

pas este egal cu 3. Rezolvarea este schiat n figura 4.3.

P1 P2 P3+--------------------------------------------+| 1| 4| 6| 9|10|11|13|14|15|18|20|25|32|45|51| (a)+--------------------------------------------+1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Figura 4.3a


7/17

67

P1 P2 P3

+--------+|32|45|51| (b)+--------+13 14 15

Figura 4.3b

Exemplul 2

S considerm o a doua execuie, cu N=2, x=21. Deci, din relaia (N+1)g>=n+1rezult 3g>=16, deci g=3. Lungimea unei subsecvene n primul pas este egal cu 8.Rezolvarea este schiat n figura 4.4.

P1 P2 (n afara irului)

+--------------------------------------------+| 1| 4| 6| 9|10|11|13|14|15|18|20|25|32|45|51| (a)+--------------------------------------------+1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

P1 P2+-----------------+|18|20|25|32|45|51| (b)+-----------------+10 11 12 13 14 15

P1 P2+-----+|18|20| (c)

+-----+10 11

Figura 4.4

Pentru a determina subintervalul care rmane n fiecare etap, fiecare proces Pi,1


8/17

68

q := q+(i-1)(N+1)g-1+1, iar

r := q+i(N+1)g-1 -1.Un singur procesor calculeaz noile valori pentru q i r, celelalte avnd acces laaceste valori n timp constant.

n descrierea ce urmeaz sunt marcate cele trei etape ale algoritmului, precum i paiicare-i compun.

/1/ /* Iniializarea indicilor secvenei de cutat *//1.1/ var q:int := 1; r:int := n;/1.2/ var x: real ; s: array [1 :n] of real ;/2/ /* Iniializarea rezultatului i a numrului maxim de pai *//2.1/ var k:int := 0;/2.2/ var g:int := sup(log(n+1)/log(N+1))

/2.3/ var c: array [0:N+1] of (stg,dr);c[0] := dr; c[N+1] := stg;

/3/ do (q/3.1/ var j: array [0 :N] of int; j[0] := q-1 ;/3.2/ fa i := 1 to N do in parallel

ji := (q-1) + i*(N+1)g-1

/* Pi compar x cu s[ji] i determin partea de secv acceptat */if ji if s[ji]=x -> k := ji

[] s[ji]>x -> c[i] := stg[] s[ji] c[i] := dr

fi;[]ji > r -> ji := r+1;

c[i] := stg;fi;

/* calculeaz indicii subsecvenei urmtoare */if c[i] c[i-1] -> q := ji - (N+1)

g-1;r := ji - 1;

fi;if (i=N) and (c[i]c[i+1]) -> q := ji +1 fi;

af;g := g-1;

od;

Observaie

Operaiile paralele din algoritm se execut n acelai timp n toate procesoarele.Operaiile secveniale sunt executate de un singur procesor.

Pentru exemplificarea execuiei algoritmului, fie secvena de numere dat n figura4.5a i x=45, N=3. Iniial, q=1, r=15, k=0 i g=2. Rezult j1=4, j2=8 i j3=12. Caurmare, n prima etap:


9/17

69

P1 compar x cu s[4] i deoarece 45>9 alege c[1]=dr;

P2 compar x cu s[8] i deoarece 45>14 alege c[2]=dr;P3 compar x cu s[12] i deoarece 45>25 alege c[3]=dr.Rezult c[3]32 alege c[1]=dr;P2 compar x cu s[14] i deoarece 45=45 pune k=14 i las c[2] neschimbat;P3 compar x cu s[15] i deoarece 4515, deci n afara secvenei. Ca urmare:P1 compar x cu s[9] i deoarece 21>15 alege c[1]=dr;P2 pune j2 la 16 (deoarece valoarea calculat este n afara secvenei) i actualizeazc[2]=stg.Deoarece c[1]c[2], se stabilesc noile valori q=10 i r=15, obinndu-se subsecvenadin figura 4.6b i g=2.

P1 P2 (n afara irului)+--------------------------------------------+| 1| 4| 6| 9|10|11|13|14|15|18|20|25|32|45|51| (a)+--------------------------------------------+1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Figura 4.6a


10/17

70

P1 P2

+-----------------+|18|20|25|32|45|51| (b)+-----------------+10 11 12 13 14 15

P1 P2+-----+|18|20| (c)+-----+10 11

Figura 4.6b,c

n a doua iteraie, P1 calculeaz j1=9+3 i compar x cu s[12]. Deoarece 2120. Ca urmare q capt valoarea 12, mai maredect valoarea lui r provocnd astfel ieirea din ciclu cu k=0.

Observaii

Deoarece pasul 3 al algoritmului precedent se execut de cel mult g ori, rezult calgoritmul are complexitatea t(n) = O(logN+1(n+1)). Lucrul efectuat de algoritm

este O(N logN+1(n+1)), deci algoritmul nu este cost-optimal. Cu toate acestea, sepoate arta c el este optim din punct de vedere al timpului de calcul. Pentru a artaacest lucru, s observm c, folosind N procesoare, algoritmul poate compara x cucel mult N valori s[i], la un moment dat. Dup aceste comparaii i dupeliminarea din secven a elementelor despre care se tie c nu sunt egale cu x,lungimea subsecvenei rmase este de cel puin:

sup((n-N)/(N+1)) >= (n-N)/(N+1) = [(n+1)/(N+1)]-1.Dupg repetiii, secvena rmas este de lungime

[(n+1)/(N+1)g]-1.Deci, numrul de iteraii cerute de orice algoritm paralel trebuie s fie mai mare decel mai mic g pentru care avem:

[(n+1)/(N+1)g]-1


11/17

71

n privina cerinei ca toate elementele secvenei S s fie distincte, ea poate fi

nlturat dac actualizarea lui k la gsirea unei coincidene este realizat printr-oprocedur special care evit conflictele de acces simultan (modelele folosite pnacum sunt cu scriere exclusiv). Aceast procedur ia un timp O(log N), mrindastfel timpul de execuie al algoritmului la:

t(n) = O(log(n+1)/log(N+1)) + O(log N).Putem aprecia importana acestui timp suplimentar dac lum cazul N=n, n care nuse realizeaz nici o mbuntire fa de algoritmul secvenial.

Meninerea eficienei algoritmului n cazul n care n ir pot exista valori egale se poate realiza prin folosirea unui model CRCW. n acest caz, este posibil ca la unconflict (mai multe elemente egale cu x se afl n secvena S), doar cea mai micvaloare a indicilor elementelor respective s fie dat lui k.

4.4. Algoritm de selecie paralel

Consideraii

(1) Se dau:- o secven de numere ntregi, S = {s1,...,sn} i- un intreg k, 1


12/17

72

Se mparte S n subsecvene de cte 5 elemente (se va arta mai departe de ce 5!). Se

afl medianele grupurilor de 5 elemente:M: 14 22 9 14 25 32Se calculeaz mediana medianelor, m = 14.Se mparte secvena S n trei subsecvene, S1, S2 i S3, cu elemente mai mici, egalei mai mari decat m, respectiv.S1: 3 8 12 1 4 9 10 5 13 7 2S2: 14 14 14S3: 16 20 31 22 33 24 26 18 34 25 27 32 35 33Deoarece |S1|=11 i |S2|=3, al 21-lea element se afl n S3. Se reine S3 n care secaut al 21-14= 7-lea element.

Se reia calculul, mprindu-se irul n subsecvene de cte 5 elemente i calculndmedianele:M: 22 26 32Se afl mediana medianelor, m=26.Se mparte secvena n trei subsecvene, S1, S2 i S3, cu elemente mai mici, egale imai mari dect m, respectiv.S1: 16 20 22 24 18 25S2: 26S3: 31 33 34 36 27 32 35 33Deoarece |S1|=6 i |S1|+|S2|=7, al 7-lea element se afl n S2, fiind egal cu m=26.

Algoritmul (divide-and-conquer) este recursiv. La fiecare etapa, se restrnge

mulimea elementelor candidate pentru selecia rezultatului. Fie |S| numrul deelemente din secvena S; fie Q o constant ntreag a crei valoare va fi precizat maitrziu.

procedure SEQUENTIAL_SELECT (S, k) returns elk: int;

Pas 1: if |S| sorteaza S i afl al k-lea element[] |S|>=Q -> mparte S n |S|/Q subsecvene de Q elemente

(cu cel mult Q-1 elemente ramase)

Pas 2: Sorteaz fiecare subsecvent si determin mediana saPas 3: Apeleaza SEQUENTIAL_SELECT recursiv pentru a afla m,

medianacelor |S|/Q mediane aflate la pasul 2

Pas 4: Creeaza trei subsecvente S1, S2, S3 cu elemente din S maimici dect, egale cu, respectiv mai mari dect m

Pas 5: if |S1|>=k -> {al k-lea element din S este in S1}


13/17

73

elk := SEQUENTIAL_SELECT (S1, k)

[] |S1|=k -> elk := m[] |S1|+|S2| elk :=SEQUENTIAL_SELECT (S3, k-|S1|-|S2|)fi

fi

Rezultatul poate fi ntors n S[1] sau ntr-un parametru suplimentar al proceduriianterioare.

Analiza complexitti este fcut considernd paii algoritmului, unul dup altul.

Pas 1. Deoarece Q este constant, sortarea lui S cnd |S|


14/17

74

In final, lund c5 = 20*c4, obinem

t(n) elk := PARALLEL_SELECT (L, k)[] (|L| < k) and (|L|+|E| >= k) -> elk := m[] |L|+|E| >= k -> elk := PARALLEL_SELECT (G, k-|L|-|E|)fi

fi

end

Valoarea celui de al k-lea element este ntoars fie n S[1], fie ntr-un argumentsuplimentar al procedurii, n cazul de faelk.


15/17

75

Exemplu

Prezentm etapele algoritmului paralel pe un exemplu. Fie secvena S:3 14 16 20 8 31 22 12 33 1 4 9 10 5 13 7 24 2 14 26 18 34 36 25 14 27 32 35 33cu n=29, i fie k=21 elementul ce trebuie selectat. De asemenea, fie N=5=|S|1-x.Rezult |S|x=6, deci secvena iniial se mparte n grupuri de cate 6 elemente. Se afl,n paralel, medianele grupurilor de 6 elemente:M: 14 9 7 25 32Se calculeaz mediana medianelor, m = 14, prin selecie paralel.Se mparte secvena S n trei subsecvene, L, E i G, cu elemente mai mici, egale imai mari dect m, respectiv.L: 3 8 12 1 4 9 10 5 13 7 2E: 14 14 14G: 16 20 31 22 33 24 26 18 34 25 27 32 35 33Deoarece |L|=11 i |E|=3, al 21-lea element se afl n G. Se reine G n care se caut al21-14= 7-lea element.

Se reia calculul. Deoarece |G|=15, se folosesc 151-x = 3 procesoare pe parcursulacestui apel (deoarece se urmrete un cost optimal, nu se iau 4 procesoare, ct arrezulta din rotunjire). Se mparte irul n subsecvene de cte 15x=5 elemente i secalculeaz medianele:M: 22 26 32Se afl mediana medianelor, m=26.

Se mparte secvena n trei subsecvene, S1, S2 i S3, cu elemente mai mici, egale imai mari dect m, respectiv.L: 16 20 22 24 18 25E: 26G: 31 33 34 36 27 32 35 33Deoarece |L|=6 i |L|+|E|=7, al 7-lea element se afl n E, fiind egal cu m=26.

Analiza complexitii.Considerm, pe rnd, fiecare pas al procedurii.

Pas 1. Pentru a ncepe, fiecare procesor trebuie s cunoasc:- adresa A a primului element al secvenei S n memoria comun;

- dimensiunea |S| i- valoarea lui k.Pentru aceasta se folosete procedura BROADCAST, care cere un timp O(log n1-x).


16/17

76

Daca |S|


17/17

77

Costul este deci optimal. De notat c nx este asimptotic mai mare decat log n, pentru

orice x. Deoarece N = n1-x si n/nx < n/log n, rezult c PARALLEL_SELECTeste optimal cu condiia ca N < n/log n.

Observaie

Algoritmul precedent a fost obinut prin paralelizarea unui algoritm secvenial. Nu ntotdeauna acest procedeu conduce la rezultate optime, uneori fiind necesarca proiectantul s ignore soluia secvenial i s exploateze paralelismul inerent al

problemei. Aceasta abordare poate conduce la mbuntirea celei mai bune soluiisecveniale cunoscute.

APD - Note Curs - 5 SIMD

Documents

Transcript of APD - Note Curs - 5 SIMD