![Page 1: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/1.jpg)
Arkitektura Paraleloak
IF - EHU
Arkitektura Paraleloak
2. Konputagailu Paraleloak (oinarrizko kontzeptuak)
- Sarrera - SIMD konputagailuak - MIMD konputagailuak - Arazo nagusiak - Kalkulu-abiadura
![Page 2: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/2.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 2 2
Paralelismoa: “eragiketa” bat baino gehiago “batera, aldi berean” egitea.
• datuen tamaina: 4 - 8 - 16 - 32 - 64... bit • aginduen exekuzioa (ILP):
segmentazioa, supereskalarrak, VLIW...
• datuetan vs programetan
Sarrera
![Page 3: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/3.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 3 2
Paralelismoa
SIMD: Single-Instruction-Multiple-Data - bektore-prozesadoreak - prozesatze-matrizeak (array processors) - GPU
MIMD: Multiple-Instruction-Multiple-Data Prozesu/hari asko, erantzuna ahalik eta azkarren emateko (high performance).
- multiprozesua, hutsegiteekiko tolerantzia, P kopia (lan-emaria edo throughput-a)
Sarrera
![Page 4: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/4.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 4 2
komunikazio-sarea
Prozesadore sinple asko, memoria gutxi, sarrera/ irteera eragiketetarako aukera.
Komunikazio-sare berezia.
prozesatze-matrizea
P+M+S/I
SIMD prozesatze-matrizea
![Page 5: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/5.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 5 2
komunikazio-sarea
Kontrol-proz.
front-end
Kontrol-prozesadoreak sinkronoki exekutatuko duten agindua bidaltzen die prozesadore guztiei (BC). Prozesadore bakoitzak, agindua exekutatzen du edo ez du ezer egiten.
prozesatze-matrizea
P+M+S/I
SIMD prozesatze-matrizea
![Page 6: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/6.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 6 2
Arkitektura mota hau egokia da aplikazio jakin batzuetarako; esaterako, irudiak (seinaleak) prozesatzeko.
Adibidea (X, Y eta Z bektoreak prozesadoreen artean banatuta daude)
for (i=0; i<1000; i++) if (Y[i] != 0) Z[i] = X[i] / Y[i]; else Z[i] = X[i];
1. pausoa: egiaztatu denak Y[i] != 0 (true / false) 2. pausoa: baldin (true) egin Z[i] = X[i] / Y[i]
(besteok, ezer ez) 3. pausoa: baldin (false) egin Z[i] = X[i]
(besteok, ezer ez)
SIMD prozesatze-matrizea
![Page 7: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/7.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 7 2 GPU
GP-GPU
• erabiltzea kalkulurako, azeleragailu gisa, irudiak (matrizeak) prozesatzeko hardware berezia.
• prozesu-unitate (sinple) asko eta egituratuta. • kalkulu independente asko, datu-egitura oso
handien gainean. • CUDA arkitektura: memoria hierarkia berezia.
ADI memoria-transferentziak (MN-GPU) kalkulu baino denbora gehiago har dezakete.
![Page 8: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/8.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 8 2
MIMD: Multiple-Instruction-Multiple-Data P prozesu/hari batera exekutatzen dira.
Oinarrizko bi eredu: - memoria partekatua - memoria banatua
MIMD konputagailuak
![Page 9: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/9.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 9 2
M0
Mm–1 memoria nagusia
Memoria partekatua (shared memory)
P0 P1 Pp–1 prozesadoreak + CM
komunikazio-sarea
S/I
MIMD konputagailuak
![Page 10: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/10.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 10 2
Memoria partekatua (shared memory)
- Helbide-espazio bakarra.
- Prozesuen arteko komunikazioa aldagai partekatuen bidez.
- Komunikazio-sarea: busa (edo urrats anitzeko sare bat).
- Izenak: multiprozesadorea, SMP, UMA.
- Eskuarki, prozesadore “gutxi”.
P0 P1 Pp–1
M0
Mm–1
S/I
MIMD konputagailuak
![Page 11: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/11.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 11 2
Pp-1
Mp-1 S/I
Memoria banatua (distributed memory)
P0
M0 S/I
Konputagailua: Pr + CM + MN + S/I
komunikazio-sarea
K K
MIMD konputagailuak
![Page 12: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/12.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 12 2
Memoria banatua (distributed memory)
- Helbide-espazio bat prozesadore bakoitzeko.
- Prozesuen arteko komunikazioa mezu-ematearen bidez.
- Komunikazio-sare orokorrak: hiperkuboa, maila, torua...
- Izenak: multikonputagailua, MPP.
- Eskuarki, prozesadore “asko”.
Pp-1
Mp-1 S/I
P0
M0 S/I K K
MIMD konputagailuak
![Page 13: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/13.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 13 2
Beste aukera bat: memoria partekatua baina fisikoki banatua.
- Helbide-espazioa bakarra da, baina erabilera ez da homogeneoa: memoria-hierarkia bat osatu da.
- Prozesuen arteko komunikazioa aldagai partekatuen bidez egiten da (logikoki), eta mezu-ematearen bidez gauzatzen da.
- Izenak: DSM, NUMA (MPP).
Pp-1
S/I
P0
S/I K
M0
Mp-1 K
MIMD konputagailuak
![Page 14: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/14.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 14 2
Izenak:
- SMP: memoria partekatuko multiprozesadorea, eskuarki prozesadore kopuru txikia, bus batez komunikatuta.
- MPP: prozesadore kopuru handiko sistema paraleloa, memoria partekatukoa zein banatukoa.
Oro har, makinarik azkarrenak, berariazko komunikazioko zein kalkuluko hardwarea eta softwarea dituzten sistemak. Baina garestiak.
Egitura hierarkikoak antola daitezke (adib., nodoak SMP sistemak dira).
MIMD konputagailuak
![Page 15: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/15.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 15 2
Izenak:
- Cluster: helburu orokorreko hardware zein soft-warearekin egindako sistema paraleloa. Kostua/abiadura erlazioa oso ona da.
PC PC
PC PC
PC
ethernet
Sinpleena: PC / ethernet (Beowulf).
Commodity / Custom
Gero eta gehiago, sistema paralelo orokorra.
MIMD konputagailuak
![Page 16: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/16.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 16 2
Izenak:
- Konstelazioa (constellation): cluster bat, non nodo kopurua nodo bakoitzeko prozesadore kopurua baino txikiagoa baita.
MIMD konputagailuak
![Page 17: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/17.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 17 2
1
1
N
N
SIMD MIMD
SISD
agindu-jarioak
datu-jarioak
Prozesatze-matrizeak
Bektore-konputagailuak
MPP/NUMA
Clusters
memoria banatua
P
C
M
sare orokorra
MN
P
C
memoria partekatua
SMP
busa
Laburpena
![Page 18: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/18.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 18 2
Helbide-espazioa partekatua pribatua
zentralizatua (busa)
banatua (sarea)
Memoria
SMP
DSM, NUMA
MPP
-
Laburpena
![Page 19: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/19.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 19 2
- Nola kudeatzen da sistema osoa?
- Nola banatzen da algoritmo bat P prozesutan? Kode guztia paraleloan exekuta al daiteke?
- Lan-banaketa orekatua da, edo, adibidez, exekuzio-karga “% 80 - % 20” banatu da?
(load balancing)
Arazoak
Sistema paraleloetan gainditu behar diren arazo batzuk:
![Page 20: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/20.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 20 2
Sistema paraleloetan gainditu behar diren arazo batzuk:
- Non daude datuak? Nola mantentzen da datuen koherentzia?
- Prozesu guztiak independenteak dira? Sinkronizatu egin behar dira?
- Prozesadoretik prozesadorera bidali beharko dira datuak? Nola?
Arazoak
![Page 21: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/21.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 21 2
Ordaindu behar diren gainkargak
1. Komunikazioa Tp = Texe + Tkom
Texe Tkom
prozesadore kopurua
Tp
Arazoak
![Page 22: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/22.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 22 2
Ordaindu behar diren gainkargak
2. Lan-banaketaren desoreka
Adibidez: 6 prozesu independente, antzeko exekuzio-denborak → Ts = 6T
▪ 3 prozesadoreren artean (2 + 2 + 2) Tp = 2T = Ts/3
▪ 4 prozesadoreren artean (2 + 2 + 1 + 1) Tp = 2T = Ts/3 !
Arazoak
![Page 23: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/23.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 23 2
Ordaindu behar diren gainkargak
3. Cachearen erabilera
Cache-blokeetako datuak (ber)erabili behar dira (ingurutasuna).
Adibidez, baldin A1 eta A2 ondoz ondoko memoria-posiziotan badaude, prozesadore berean prozesatzea mereziko du, cacheko asmatze-tasa handitzeko.
Arazoak
![Page 24: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/24.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 24 2
Aplikazio motak
- ale xeheko paralelismoa ataza asko, txikiak komunikazioa: maiz, datu gutxi
- ale larriko paralelismoa ataza gutxi, handiak komunikazioa: noizbehinka, datu asko
Arazoak
![Page 25: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/25.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 25 2
Azelerazio-faktorea / Eraginkortasuna
af = Ts / Tp (onena: P-rekiko linealki haztea)
erag = af / P (onena: P-rekiko independentea)
Kasurik onena: Tp = Ts / P → af = P eta erag = 1
Helburua: 1 programa bera azkarrago exekutatzea. 2 programa handiagoak denbora berdinean
exekutatzea.
Eraginkortasuna
![Page 26: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/26.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 26 2
Beraz, hau da benetako azelerazio-faktorea (Amdahl-en legea):
af = Ts / Tsp = Ts / [f Ts/P + (1-f) Ts] af = P / [f + (1-f) P] → 1 / (1-f) !
1 Oro har, zati bat paraleloan eta beste bat seriean:
Tsp = f Tp + (1-f) Ts
Amdahl
![Page 27: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/27.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 27 2
1 Amdahl-en legea af = P / (f + (1-f) P) → 1 / (1-f)
Amdahl
![Page 28: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/28.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 28 2
2 Maiz, paralelismoa ez da azkarrago exekutatzeko erabiltzen, baizik eta tamaina handiagoko atazak exekutatu ahal izateko.
af = Ts’ / Tp’
af = (1-f) + f P
f Ts P (1-f) Ts
tamaina handiagoa (xP) Ts’ = ((1-f) + f P) Ts
Gustafson
(1-f) Ts f Ts Ts
seriean
f Ts (1-f) Ts
P prozesadore
Tp’ = Ts paraleloan
![Page 29: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/29.jpg)
Arkitektura Paraleloak IF - EHU
K. Par. 29 2
2 Gustafson-en legea af = (1-f) + f P
Gustafson
![Page 30: Presentación de PowerPoint › acwarfra › arpar › AP › AP.fitxategiak › AP-Gardenkia… · - prozesatze-matrizeak (array processors) - GPU . MIMD: Multiple-Instruction-Multiple-Data](https://reader033.vdocumento.com/reader033/viewer/2022060323/5f0dc61c7e708231d43c04ab/html5/thumbnails/30.jpg)
any questions?
Arkitektura Paraleloak
IF - EHU
K. Par. | Gustafson
2 Gustafson-en legea af = (1-f) + f P