1. noŢiuni introductive despre calculatoarele paralele
DESCRIPTION
1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE. 1.1 MASINI PARALELE SI MODELE DE PROGRAMARE 1.2 CLASIFICAREA CALCULATOARELOR PARALELE 1.3 TIPURI DE CALCULATOARE PARALELE 1.4 PERFORMANŢE ALE CALCULATOARELOR PARALELE 1.5 PROGRAME PARALELE. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/1.jpg)
1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE
• 1.1 MASINI PARALELE SI MODELE DE PROGRAMARE
• 1.2 CLASIFICAREA CALCULATOARELOR PARALELE
• 1.3 TIPURI DE CALCULATOARE PARALELE
• 1.4 PERFORMANŢE ALE CALCULATOARELOR PARALELE
• 1.5 PROGRAME PARALELE
![Page 2: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/2.jpg)
1.1 MASINI PARALELE SI MODELE DE PROGRAMARE
Calculator paralel = colectie de elemente de prelucrare care comunica si coopereaza pentru rezolvarea rapida a unor probleme complexe.
Comunicatie si cooperare: esentiale intr-o arhitectura paralela!=> arhitectura comunicatiei
![Page 3: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/3.jpg)
Cadrul de organizare intr-o masina paralela:
![Page 4: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/4.jpg)
O arhitectura paralela generala:
![Page 5: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/5.jpg)
Exemplu de aplicatie paralela: calcularea sumei
Solutia generala: n/p taskuri p procesoare (procese).
Se disting doua seturi de date:-partajate: valorile A[i] si suma finala;-private: evalurile individuale de functii si sumele partiale
1
0])[(
n
iiAf
![Page 6: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/6.jpg)
1) Modelul 1 de programare: spatiu partajat de adrese.
Programul = colectie de fire de executie, fiecare avand un set de variabile private, iar impreuna partajeaza un alt set de variabile.
Comunicatia dintre firele de executie: prin citirea/scrierea variabilelor partajate.
Coordonarea firelor de executie prin operatii de sincronizare: indicatori (flags), zavoare (locks), semafoare.
![Page 7: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/7.jpg)
Masina paralela corespunzatoare modelului 1: masina cu memorie partajata (sistemele multiprocesor, in primul rand sistemele multiprocesor simetrice sau SMP-Symmetric Multiprocessors).
Exemple: sisteme de la Sun, DEC, Intel (Millennium), SGI Origin.
![Page 8: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/8.jpg)
Variante ale acestui model:
a) masina cu memorie partajata distribuita (logic partajata, dar fizic distribuita. Exemplu: SGI Origin (scalabila la cateva sute de procesoare).
b) masina cu spatiu partajat de adrese (memoriile cache inlocuite cu memorii locale). Exemplu: Cray T3E.
![Page 9: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/9.jpg)
O posibila solutie pentru rezolvarea problemei:
![Page 10: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/10.jpg)
Este necesara sincronizarea threadurilor pentru accesul la variabilele partajate !
Exemplu: prin excludere mutuala, folosind operatia de zavorare (lock):
![Page 11: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/11.jpg)
2) Modelul 2 de programare: transfer de mesaje.
Programul = colectie de procese, fiecare cu thread de control si spatiu local de adrese, variabile locale, variabile statice, blocuri comune.
Comunicatia dintre procese: prin transfer explicit de date (perechi de operatii corespunzatoare send si receive la procesele sursa si respectiv destinatie). Datele partajate din punct de vedere logic sunt partitionate intre toate procesele.
=> asemanare cu programarea distribuita!
Exista biblioteci standard (exemplu: MPI si PVM).
![Page 12: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/12.jpg)
Masina corespunzatoare modelului 2 este multicalculatorul (sistem cu memorie distribuita):
Exemple: Cray T3E (poate fi incadrat si in aceasta categorie), IBM SP2, NOW, Millenium.
![Page 13: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/13.jpg)
O posibila solutie a problemei in cadrul modelului in transfer de mesaje (simplificand, se calculeaza suma s = f(A[1]) + f(A[2]) ):
sau:
Procesor 1 Procesor 2xlocal = f(A[1]) xlocal = f(A[2])send xlocal, proc2 send xlocal, proc1receive xremote, proc2 receive xremote, proc1s = xlocal + xremote s = xlocal + xremote
Procesor 1 Procesor 2xlocal = f(A[1]) xlocal = f(A[2])send xlocal, proc2 receive xremote, proc1receive xremote, proc2 send xlocal, proc1s = xlocal + xremote s = xlocal + xremote
![Page 14: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/14.jpg)
3) Modelul 3 de programare: paralelism al datelor.
Thread singular secvential de control controleaza un set de operatii paralele aplicate intregii structuri de date, sau numai unui singur subset.
Comunicatia: implicita, in modul de deplasare a datelor.
Eficienta numai pentru anumite probleme (exemplu: prelucrari de tablouri)!
![Page 15: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/15.jpg)
Masina corespunzatoare modelului 3: sistem SIMD - Single Instruction Multiple Data (numar mare de procesoare elementare comandate de un singur procesor de control, executand aceeasi instructiune, posibil anumite procesoare inactive la anumite momente de timp - la executia anumitor instructiuni).
Exemple: CM2, MASPAR, sistemele sistolice VLSI
Varianta: masina vectoriala (un singur procesor cu unitati functionale multiple, toate efectuand aceeasi operatie in acelasi moment de timp).
![Page 16: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/16.jpg)
4) Modelul 4 de masina: cluster de SMP-uri sau CLUMP (mai multe SMP-uri conectate intr-o retea).
Fiecare SMP: sistem cu memorie partajata!
Comunicatia intre SMP-uri: prin transfer de mesaje.
Exemple: Millennium, IBM SPx, ASCI Red (Intel).
Model de programare: se utilizeaza transferul de mesaje, chiar in interiorul SMP-urilor!
![Page 17: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/17.jpg)
1.2 CLASIFICAREA CALCULATOARELOR PARALELE
-SIMD (Single Instruction Multiple Data):-Procesoare matriciale;-Procesoare vectoriale;-Procesoare sistolice VLSI.
-MIMD (Multiple Instruction Multiple Data):-Multiprocesoare (MIMD cu memorie partajată):
-UMA (Uniform Memory Access):-UMA cu magistrale;-UMA cu comutatoare.
-NUMA (Non-Uniform Memory Access):-CC-NUMA (Cache Coherent NUMA);-NC-NUMA (Non Coherent NUMA).
-COMA (Cache Only Memory Access).-Multicalculatoare (MIMD cu transfer de mesaje):
-MPP (Massively Parallel Processors):-MPP cu grilă;-MPP hipercub.
-COW (Cluster Of Workstations).
![Page 18: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/18.jpg)
1.3 TIPURI DE CALCULATOARE PARALELE
• Calculatoare în bandă de asamblare
• Calculatoare de masive
• Sisteme multiprocesor
• Calculatoare în flux de date
• Sisteme sistolice VLSI
![Page 19: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/19.jpg)
Calculatoare în bandă de asamblare
Execuţia instrucţiunilor într-un calculator secveţial.
![Page 20: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/20.jpg)
Procesor în bandă de asamblare
Execuţia instrucţiunilor într-un calculator în bandă de asamblare.
![Page 21: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/21.jpg)
Structura funcţională a unui calculator în bandă de asamblare.
![Page 22: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/22.jpg)
Calculatoare de masive
Structura funcţională a unui calculator de masive.
![Page 23: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/23.jpg)
Sisteme multiprocesor
Structura funcţională a unui sistem multiprocesor.
![Page 24: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/24.jpg)
Calculatoare în flux de date
Exemplu: se consideră calcularea expresiei: z = ( x + y ) * 2
. Graful şi şabloanele în flux de date.
![Page 25: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/25.jpg)
Mecanismul de execuţie al unui program în flux de date.
![Page 26: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/26.jpg)
Sisteme sistolice VLSI
Exemplu: se consideră un sistem simplu pentru calcularea convoluţiilor, utilizând o reţea liniară de elemente de prelucrare:
y(i) = w1*x(i)+ w2*x(i+1)+w3*x(i+2)+w4*x(i+3)
Reţea liniară pentru calcularea convoluţiilor.
![Page 27: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/27.jpg)
1.4 PERFORMANŢE ALE CALCULATOARELOR PARALELE
• Masuratori de performanta
• Factorul câştig de viteză
• Principiul mediei armonice ponderate
• Legea lui Amdahl
• Limitări ale calculului paralel
![Page 28: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/28.jpg)
Masuratori de performanta
Gradul de paralelism DOP („degree of parallelism”) = numarul de procesoare dintr-un calculator paralel utilizate pe un anumit interval de timp.
Profilul paralelismului = graficul DOP in functie de timp (pentru un anumit program). Depinde de:
-structura algoritmului;-optimizarea programului;-utilizarea resurselor;-conditiile de rulare.
Se considera un sistem paralel cu n procesoare identice.
![Page 29: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/29.jpg)
Paralelism mediu Notatii:
∆ = capacitatea de calcul pentru un procesor, aproximat cu rata MIPS (million instructions per second):
666 101010
C
If
CPI
f
T
IRata CC
MIPS
undeIC : numar instructiuni pentru program („instruction count”);
T : timp de executie pentru program in secunde;f : frecventa ceasului in Hz, egala cu 1/τ (τ perioada ceasului in secunde);CPI : cicluri per instructiune (perioade de ceas necesare pentru executia unei
instructiuni);C : numar de cicluri necesare pentru executia unui program.
Au fost utilizate relatiile:
CI
CCPI f
CPIICPII
f
CCT CC
Aproximarea ∆ cu rata MIPS sau rata Mflops nu tine seama de penalizarile datorate accesului la memorie, latenta comunicatiei, overhead-ul sistemului.
![Page 30: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/30.jpg)
Volumul de lucru W („work”) este proportional cu aria de sub graficul profilului:
2
1
)(t
t
dttDOPW
iar in cazul discret:
n
iitiW
1
unde ti = timpul total cat DOP = i, iar
n
ii ttt
112
(timpul total scurs).
Paralelismul mediu A („average paralellism”):
2
1
)(1
12
t
t
dttDOPtt
A
n
ii
n
ii ttiA
11
/
![Page 31: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/31.jpg)
Factorul câştig de viteză
Definitie. Factorul câştig de viteză sau accelerare notat S (“speedup”) pentru un calculator paralel este raportul dntre timpii necesari pentru rezolvarea aceleiaşi probleme pe un sistem monoprocesor şi respectiv pe sistemul paralel.
log2n < S < n/ln n
log2n supoziţia lui Minsky.
Limita superioară n/ln n :-o problemă se rezolva pe un monoprocesor în unitatea de timp, T1=1;
- fi probabilitatea de a asigna aceeaşi problemă la i procesoare, cu o încărcare medie
di=1/i per procesor;
-se presupun probabilităţi egale pentru fiecare mod de operare utilizând i procesoare, (fi=1/n pentru n moduri de operare, i=1,2,3,…,n);
![Page 32: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/32.jpg)
-timpul mediu necesar pentru rezolvarea problemei pe un sistem cu n procesoare :
n
i
n
iiin n
idfT
1
1
1
-câştigul mediu de viteză S :
n
n
i
n
T
TS n
i
n ln1
1
1
![Page 33: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/33.jpg)
-volumul de lucru cu DOP =i:
ii tiW
n
iiWW
1
-timpul de executie al volumului Wi pe un uniprocesor:
i
i
Wt )1(
- timpul de executie al volumului Wi pe k procesoare:
ikk
Wkt i
i
)(
-intr-un sistem cu numar infinit de procesoare:
nii
Wt i
i
1)(
![Page 34: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/34.jpg)
-timpul de raspuns:
n
i
n
i
ii
WtT
1 1
)1()1(
n
i
n
i
ii i
WtT
1 1
)()(
=> factorul asimptotic de accelerare S∞ :
n
ii
n
ii
n
i
i
n
ii
n
i
i
n
ii
t
ti
iti
ti
iW
W
T
TS
1
1
1
1
1
1
)(
)1(
![Page 35: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/35.jpg)
Performanta medie aritmetica
-se noteaza cu Ri ratele de executie ale programelor i = 1, 2, 3, ... , n. Rata
medie aritmetica de executie:
n
RR
n
ii
a
1
(s-a presupus ponderea 1/n pentru fiecare din cele n programe).
-daca programele au ponderi cu o distributie oarecare π = { fi | i = 1, 2, ..., n}:
i
n
iia RfR
1
*
![Page 36: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/36.jpg)
Performanta medie geometrica
-rata de executie medie geometrica:
n
i
nig RR
1
/1
-iar pentru o distributie a ponderilor π = { fi | i = 1, 2, ..., n}:
n
i
fig
iRR1
*
![Page 37: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/37.jpg)
Rata de executie medie armonica
-timpul mediu de executie per instructiune pentru programul i:
ii R
T1
-timpul mediu (aritmetic) de executie per instructiune:
n
i
n
i iia Rn
Tn
T1 1
111
=> rata de executie medie armonica este inversul timpului mediu:
n
i i
h
R
nR
1
1
=> rata de executie medie armonica ponderata pentru o distributie oarecare de ponderi π = { fi | i = 1, 2, ..., n}:
n
i i
ih
Rf
R
1
* 1
![Page 38: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/38.jpg)
Principiul mediei armonice ponderate Fie Tn timpul necesar execuţiei a m taskuri de n tipuri diferite, fiecare tip constând din
mi taskuri, necesitând ti secunde:
ii f
m
m
n
ii
in
iii
nh
tmm
tm
m
T
mR
11
* 1
n
iimm
1
n
iiin tmT
1
Rata de execuţie R (numărul de evenimente sau operaţii în unitatea de timp):
Se definesc fi ca fracţia de rezultate generate la rata Ri şi ti=1/Ri ca timpul necesar
pentru generarea unui rezultat
ii
ii
ii t
Rfm
mf
1;1;
Rata globala a masinii:
n
i i
in
iii
h
Rf
tfR
11
* 11
![Page 39: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/39.jpg)
Factorul de accelerare medie armonica
Se presupune executia unui program (sau o incarcare cu mai multe programe) pe un sistem cu n procesoare. In diferite intervale de timp sistemul poate utiliza i=1, 2, ..., n procesoare (modul i cu i procesoare). -timpul secvential pe un uniprocesor cu R1 = 1:
11
11
RT
-timpul de executie cu i procesoare cu Ri = i, in cazul ideal:
iRT
ii
11
Programul este executat in n moduri de functionare cu o distributie a ponderilor π = { fi
| i = 1, 2, ..., n}.
=> factorul de accelerare medie armonica:
n
i i
ih
R
fT
TS
1
*1* 1
unde T* = 1/Rh* este timpul mediu armonic de executie pentru cele m moduri de
executie.
![Page 40: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/40.jpg)
Legea lui Amdahl
caz particular al principiului de mai sus
Pentru un sistem de calcul se consideră două rate de execuţie:-rata de execuţie superioară (sau paralelă) RH;
-rata de execuţie inferioară (sau serială) RL.
Dacă f reprezintă fracţia rezultatelor generate cu rata RH şi 1-f este fracţia rezultatelor
generate cu rata RL, ecuaţia mediei armonice ponderate devine:
LH Rf
Rf
fR
1
1)(
![Page 41: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/41.jpg)
Se presupune Ri = i, π = (1-f, 0, 0, ..., 0, f). In ecuatia pentru Sh* se inlocuieste R1 = 1 si
Rn = n:
ffn
n
nff
Rf
Rf
S
n
h
)1(1
11
11
1
*
Consecinta: Sh* → 1/(1-f) pe masura ce n → ∞.
![Page 42: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/42.jpg)
Eficienta, utilizarea si calitatea
Se noteaza:O(n) = numarul de operatii unitare executate intr-un sistem cu n procesoare.T(n) = timp de executie (unitati de timp) in general O(n) > T(n).T(1) = O(1) intr-un uniprocesor.
Se definesc:-factorul de accelerare:
)(
)1()(
nT
TnS
-eficienta:
)(
)1()()(
nTn
T
n
nSnE
Deoarece 1≤S(n) ≤n => 1/n≤E(n) ≤1. -redundanta:
)1(
)()(
O
nOnR
Evident 1≤R(n) ≤n.
![Page 43: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/43.jpg)
)(
)()()()(
nTn
nOnEnRnU
-utilizarea:
Sunt interesante urmatoarele relatii:
1/n≤E(n) ≤U(n) ≤11≤R(n) ≤1/E(n) ≤n
-calitatea paralelismului:
)()(
)1(
)(
)()()(
2
3
nOnTn
T
nR
nEnSnQ
deoarece E(n) ≤1, 1≤R(n) ≤n => Q(n) este limitat superior de S(n).
![Page 44: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/44.jpg)
In concluzie:
-accelerarea indica castigul de viteza de calcul intr-un sistem paralel;
-eficienta masoara partea utila a prelucrarii (lucrului) efectuate de n procesoare;
-redundanta masoara dimensiunea cresterii incarcarii de lucru;
-utilizarea indica gradul de utilizare a resurselor in timpul calculului paralel;
-calitatea combina efectele accelerarii, eficientei si redundantei intr-o singura expresie pentru a evidentia meritul calcului paralel.
![Page 45: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/45.jpg)
Limitări ale calculului paralel variabile:
-ts = timpul de sincronizare;
-t = timpul mediu de execuţie a unui task (granularitatea taskurilor);-to = overhead-ul taskurilor cauzat de execuţia paralelă;
-N = numărul de taskuri executate între două puncte de sincronizare;-n = numărul de procesoare.
Execuţia secvenţială a celor N taskuri, fiecare necesitând un timp t are loc într-un timp total T1 = N t.
Într-un sistem paralel:-fiecare task necesită (t+to) unităţi de timp, în loc de t.
-N taskuri pe n procesoare număr paşi paraleli (raportul celular) = N/n.
Timpul de execuţie paralelă:
)(, osnN ttn
NtT
![Page 46: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/46.jpg)
Creşterea de viteză este:
Ntt
nN
Ntt
ttnN
t
Nt
T
TS
o
sos
nNnN
)1(
1
)(,
1,
Mărirea factorului de accelerare:
-efectul sincronizării ts/(Nt):
-scăderea timpului de sincronizare ts;
-creşterea produsului Nt (însemnând intervale mai largi între sincronizări).-efectul de overhead to/t,:
-scăderea timpului de overhead to;
-creşterea granularităţii t.-numărul de paşi de calcul N/n :
-utilizând mai multe procesoare;-număr de taskuri multiplu al numărului de procesoare.
![Page 47: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/47.jpg)
Eficienţa sistemului multiprocesor se defineşte prin relaţia:
n
SE nN
nN,
,
Limitările calculului paralel trecerea la limită în relaţiile pentru creşterea de viteză SN,n şi eficienţa EN,n. Rezultatele în tabela:
![Page 48: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/48.jpg)
![Page 49: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/49.jpg)
![Page 50: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/50.jpg)
1.5 PROGRAME PARALELE
Cateva exemple de aplicatii complexe ale calculatoarelor paralele:
-simularea curentilor oceanici (structura regulata si calcule stiintifice);-simularea evolutiei galaxiei (structura neregulata si calcule stiintifice);-generarea scenelor prin metoda „Ray Tracing” (aplicatie de grafica pe
calculator cu structura neregulata);-Data Mining (structura neregulata).
![Page 51: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/51.jpg)
Simularea curentilor oceanici
Forte fizice: efectele atmosferice, vantul si frecarea cu fundul oceanului => sisteme complexe de ecuatii.
Problema continua in spatiu (intanderea oceanului) si in timp (se face studiul pe un interval mare de timp) => discretizarea problemei dupa ambele dimensiuni.
Discretizarea spatiului: grid de puncte egal distantate, fiecare punct avand valori pentru marimile de interes ( presiune, viteza, etc). Se utilizeaza un set de griduri bidimensionale (sectiuni orizontale prin volumul oceanului).
![Page 52: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/52.jpg)
Timpul discretizat: serie finita de pasi.
Solutia depinde de rezolutia aleasa in ambele dimensiuni (spatiu si timp). Exemplu: o zona din ocean de 2000x2000 km2 un grid de 100x100 este insuficient (distanta dintre doua puncte 20 km, iar pentru simularea pe 5 ani, cu un pas de timp de 8 ore => 5500 pasi de timp).
Problema prezinta un paralelism intrinsec (calculele si actualizarea valorilor diferitelor puncte din spatiu se poate face in paralel). Astfel, de exemplu se poate asigna cate un grid unui procesor, calculele realizandu-se in paralel.
![Page 53: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/53.jpg)
Simularea evolutiei galaxiei
Studiul evolutiei stelelor intr-un sistem de galaxii in timp (probleme de coliziune a galaxiilor, gruparea stelelor in galaxii).
Se simuleaza deplasarea a n corpuri, fiecare corp fiind sub influenta tuturor celorlalte corpuri (problema n-body). Timpul discretizat, mai multi pasi de timp. Pentru fiecare pas se calculeaza fortele gravitationale exercitate, actualizand pozitia, viteza si alti parametri pentru fiecare corp.
n corpuri => complexitate O(n2), dar prin algoritmi ierarhici => complexitate O(n log n).
Algoritmii ierarhici se bazeaza pe faptul ca forta de interactiune scade cu distanta (~1/r2), deci influentele corpurilor foarte indepartate pot fi calculate prin gruparea acestora si considerarea grupului ca un singur corp in centrul de masa, fara pierdere de precizie.
![Page 54: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/54.jpg)
Algoritmii ierarhici: forta de interactiune scade cu distanta (~1/r2).
=> influentele corpurilor foarte indepartate -> prin gruparea acestora!
![Page 55: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/55.jpg)
=> cu cat stele sunt mai indepartate de steaua curenta cu atat grupurile de aproximare pot fi mai mari.
Algoritmul utilizat: Barnes-Hut.
Caracteristici: 1) Distributia de stele neregulata (galaxiile mai dense in anumite zone si mai
imprastiate in altele).2) Distributia se modifica in timp (evolutia in timp).
=> structura neregulata si dinamica a sistemului de galaxii (implementare dificila pe un sistem paralel).
![Page 56: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/56.jpg)
Paralelizarea programelor
Algoritm secvential pentru rezolvarea unei probleme => programul paralel.
Este necesar:-sa se identifice activitatile (incluzand calcule, accesul la date si operatii de
I/E) care pot fi efectuate in paralel;-sa se imparta activitatea si eventual si datele intre procese;-se se gestioneze accesul datelor, comunicatia si sincronizarea;
Scop: micsorarea timpului de calcul => factorul de accelerare S=T(1)/T(n).
![Page 57: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/57.jpg)
Pasii pentru crearea unui program paralel:
![Page 58: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/58.jpg)
1. Descompunerea: spargerea calculului (algoritmului) intr-o colectie de taskuri -> distribuite procesoarelor.
Exemplu. Program cu doua etape:1) se calculeaza in mod independent n2 valori (tablou nxn);2) se insumeaza cele n2 rezultate.
Sistem cu p procesoare: n2/p calcule fiecarui procesor(in paralel), apoi rezultatele insumate secvential intr-o variabila globala.
Timpul total in acest caz este n2/p+n2 (fata de 2n2 unitati de timp in cazul secvential). Factorul de accelerare obtinut este:
(limita 2).
![Page 59: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/59.jpg)
Imbunatatirea algoritmului: in etapa a doua fiecare procesor face o suma locala a rezultatelor obtinute, iar apoi aceasta suma este adunata la rezultatul fina (variabila globala).
Timpul: n2/p+n2/p+p=2n2/p+p.
Factorul de accelerare in acest caz se obtine:
(pentru n mare, limita apropiata de p).
![Page 60: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/60.jpg)
Profilul concurentei: numarul de operatii (sau taskuri) disponibile pentru executie concurenta la un moment dat.
Aria de sub grafic = volumul total de prelucrare (timp uniprocesor).Limita orizontala din grafic = timpul cel mai scurt de executie a aplicatiei (presupunand un numar infinit de procesoare). Factorul de accelerare:
![Page 61: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/61.jpg)
2. Asignarea: mecanism de distribuire a taskurilor la procese (exemplu: algoritm Barnes-Hut -> care procese calculeaza fortele de interactiune pentru care stele).
Scop principal: echilibru de incarcare intre procese (reduce comunicatia intre procese si costul gestionarii).
Asignarea poate sa fie:
-statica (predeterminata): asignarea este complet determinata la inceputul programului, sau dupa introducerea datelor initiale si nu se modifica in timpul executiei aplicatiei;
-dinamica: asignarea lucrului la procese se determina in timpul executiei, eventual ca reactie la un dezechilibru de incarcare.
![Page 62: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/62.jpg)
3. Orchestrarea: determinata de arhitectura si modelul de programare(chiar si de limbajul de programare).
Mecanisme:-numire si accesare a datelor;-comunicatie intre procese;-sincronizare;-planificarea taskurilor asignate unui proces (ordinea in care taskurile sunt
executate).
Scop: reducerea costului comunicatie si sincronizarii vazute de procesoare, planificarea executie mai devreme a taskurilor de care depind alte taskuri, reducerea overhead-ului corespunzator gestionarii paralelismului.
![Page 63: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/63.jpg)
4. Maparea: repartizarea proceselor (dupa etapele 1, 2, 3 => program paralel) la procesoare.
Controlul maparii:-program;-S.O.
In cazul cel mai simplu: procesoarele masinii impartite in subseturi si doar un singur program poate rula la un moment dat pe un subset (partajarea spatiului).
Cealalta solutie extrema: S.O. controleaza dinamic momentul si spatiul (setul de procesoare) pentru executia proceselor (fara interventia utilizatorului).
=> o mai buna partajare si utilizare a resurselor.
In multe situatii reale: combinatie a celor doua.
![Page 64: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/64.jpg)
Paralelizarea unui program
Modul al aplicatiei de simulare a curentilor oceanici: rezolvarea iterativa de ecuatii („equation solver”).
Limbaj pseudocod cu extensii pentru specificarea paralelismului (primitive de sincronizare si comunicatie, in cadrul arhitecturilor cu memorie parajata sau in transfer de mesaje).
Metoda de diferente finite (Gauss-Siedel): tablou bidimensional de (n+2)x(n+2) elemente corespunzator unui grid (sectiune orizontala prin volumul oceanului). Punctele de pe granite nu se modifica, in timp ce cele nxn puncte interioare sunt actualizate de program pornind de la valorile lor initiale, intr-un numar de pasi. La fiecare pas se opereaza asupra tuturor punctelor interioare ale gridului, fiecare punct fiind inlocuit printr-o medie ponderata a vecinilor imediati.
![Page 65: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/65.jpg)
Actualizarile se fac imediat (un punct va vedea valorile noi la vecinii sus si stanga si valorile vechi la vecinii jos si dreapta).
Se calculeaza de asemenea si diferenta intre valoarea veche si valoarea noua pentru fiecare punct. Daca diferenta medie peste toate elementele este mai mica decat o valoare predefinita solutia a convers si se incheie algoritmul, altfel se continua cu un nou pas.
![Page 66: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/66.jpg)
![Page 67: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/67.jpg)
1) Descompunerea.
-studierea buclelor: daca iteratiile pot fi executate in paralel (aici nu exista concurenta: datele utilizate in iteratia curenta sunt actualizate in iteratia precedenta, deci iteratiile nu se pot executa in paralel).
-examinarea dependentelor fundamentale. Ordinea de actualizare a punctelor gridului este stanga->dreapta si sus->jos, deci punctele de pe antidiagonala (diagonala secundara, NE->SV) sunt independente din p.d.v. al calculului si deci pot fi calculate in paralel. Dezavantaje: prea multe puncte de sincronizare si incarcarea este dezechilibrata (procese cu numar de puncte intre 1-n).
![Page 68: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/68.jpg)
-cunoasterea problemei: ordinea de evaluare a punctelor din grid nu este esentiala in metoda Gauss-Seidel => alta ordine: ordinea rosu-negru. Fiecare pas al algoritmului este impartit in doua faze complet echilibrate (actualizarea n2/2 puncte rosii si actualizare n2/2 puncte negre) ce se pot executa in paralel, cu o singura operatie de sincronizare (care nu este absolut necesara, dar convenabila).
![Page 69: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/69.jpg)
for -> for_all (paralelizare, gradul de concurenta obtinut fiind n2).
Descompunere pe randuri: linia 18 for_all -> for (grad de concurenta n).
Sincronizare globala la sfarsitul buclei for_all (end for_all).
![Page 70: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/70.jpg)
2) Asignarea. Solutia statica (cea mai simpla): se asigneaza cate un bloc compact de randuri la un proces (asignare de blocuri), astfel incat randul i este asignat procesului
Avantaj: reducerea comunicatiilor (randurile adiacente sunt pastrate impreuna la acelasi proces).
Solutia dinamica: un proces terminand de calculat un rand, va prelua un alt rand necalculat.
![Page 71: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/71.jpg)
3a) Orchestrarea in modelul paralelismul datelor.
![Page 72: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/72.jpg)
![Page 73: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/73.jpg)
3b) Orchestrarea in modelul cu memorie partajata. Tabloul A este declarat partajat, elementele acestuia fiind accesate de procese pe masura ce sunt necesare, folosind instructiuni load/store obisnuite. Sunt utilizate mecanisme pentru crearea de procese, coordonarea acestora prin sincronizare si controlul asignarii lucrului la acestea.
![Page 74: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/74.jpg)
![Page 75: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/75.jpg)
Program de tip SPMD (Single Program Multiple Data). Se utilizeaza o serie de primitive cu implementari in diferite masini fizice cu memorie partajata:
![Page 76: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/76.jpg)
3c) Orchestrarea in modelul cu transfer de mesaje. Matricea A reprezentata prin structuri de date mai mici, alocate spatiilor private ale proceselor care le prelucreaza.. In cazul acestui algoritm se aloca fiecarui proces cate un set de randuri consecutive din cadrul gridului.
![Page 77: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/77.jpg)
![Page 78: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/78.jpg)
Se pot utiliza operatiile REDUCE si BROADCAST pentru simplificarea codului:
![Page 79: 1. NOŢIUNI INTRODUCTIVE DESPRE CALCULATOARELE PARALELE](https://reader036.vdocumente.com/reader036/viewer/2022081501/568137c7550346895d9f64cf/html5/thumbnails/79.jpg)
Concluzii:-descompunerea si asignarea sunt asemanatoare in cele doua modele
importante, cu memorie partajata si in transfer de mesaje;-orchestrarea este diferita (structuri de date, accesul/denumirea datelor,
comunicatia, sincronizarea).
Diferente: