Arkitektura Paraleloak

Arkitektura Paraleloak IF - EHU

Arkitektura Paraleloak

2. Konputagailu Paraleloak(oinarrizko kontzeptuak)- Sarrera- SIMD konputagailuak- MIMD konputagailuak- Arazo nagusiak- Kalkulu-abiadura

Arkitektura ParaleloakIF - EHU

K. Par. 22

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


K. Par. 32

ParalelismoaSIMD: 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


K. Par. 42

komunikazio-sarea

Prozesadore sinple asko, memoria gutxi, sarrera/ irteera eragiketetarako aukera.Komunikazio-sare berezia.

prozesatze-matrizea

P+M+S/I

SIMD prozesatze-matrizea


K. Par. 52

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



K. Par. 62

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)



K. Par. 72GPU

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.


K. Par. 82

MIMD: Multiple-Instruction-Multiple-Data

P prozesu/hari batera exekutatzen dira.Oinarrizko bi eredu:

- memoria partekatua- memoria banatua

MIMD konputagailuak


K. Par. 92

M0 Mm–1 memoria nagusia

Memoria partekatua (shared memory)

P0 P1 Pp–1 prozesadoreak + CM

komunikazio-sarea

S/I

MIMD konputagailuak


K. Par. 102

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–1S/I

MIMD konputagailuak


K. Par. 112

Pp-1

Mp-1S/I

Memoria banatua (distributed memory)

P0

M0S/I

Konputagailua:Pr + CM + MN + S/I

komunikazio-sarea

KK

MIMD konputagailuak


K. Par. 122

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/IKK

MIMD konputagailuak


K. Par. 132

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/IKM0Mp-1K

MIMD konputagailuak


K. Par. 142

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


K. Par. 152

Izenak:- Cluster: helburu orokorreko hardware zein

soft-warearekin egindako sistema paraleloa. Kostua/abiadura erlazioa oso ona da.

PCPC

PCPC

PC

ethernet

Sinpleena: PC / ethernet (Beowulf).Commodity / Custom

Gero eta gehiago, sistema paralelo orokorra.

MIMD konputagailuak


K. Par. 162

Izenak:- Konstelazioa (constellation): cluster bat,

non nodo kopurua nodo bakoitzeko prozesadore kopurua baino txikiagoa baita.

MIMD konputagailuak


K. Par. 172

1

1

N

N

SIMD MIMD

SISD

agindu-jarioak

datu-jarioak

Prozesatze-matrizeakBektore-konputagailuak

MPP/NUMA

Clustersmemoria banatua

P

C

M

sare orokorra

MN

P

C

memoria partekatua

SMP

busa

Laburpena


K. Par. 182

Helbide-espazioa partekatua pribatua

zentralizatua(busa)

banatua(sarea)

MemoriaSMP

DSM, NUMA MPP

-

Laburpena


K. Par. 192

- 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:


K. Par. 202

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


K. Par. 212

Ordaindu behar diren gainkargak

1. Komunikazioa Tp = Texe + Tkom

Texe

Tkom

prozesadore kopurua

Tp

Arazoak


K. Par. 222


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


K. Par. 232


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


K. Par. 242

Aplikazio motak

- ale xeheko paralelismoaataza asko, txikiakkomunikazioa: maiz, datu gutxi

- ale larriko paralelismoaataza gutxi, handiakkomunikazioa: noizbehinka, datu

asko

Arazoak


K. Par. 252

Azelerazio-faktorea / Eraginkortasunaaf = 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


K. Par. 262

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


K. Par. 272

1 Amdahl-en legeaaf = P / (f + (1-f) P) → 1 / (1-f)

0

20

40

60

80

100

0 20 40 60 80 100

Azele

razio

-fakto

rea

Prozesadore kopurua

f = 0,8 f = 0,9

f = 0,95

azelerazio-faktore lineala (P)

Amdahl


K. Par. 282

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 TsTs

seriean

f Ts(1-f) Ts

P prozesadoreTp’ = Tsparaleloan


K. Par. 292

2 Gustafson-en legea

0

10

20

30

40

0 10 20 30 40

Azele

razio

-fakto

rea

Prozesadore kopurua

f konstantea

ideala

t konstantea

af = (1-f) + f P

Gustafson

any questions?

Arkitektura Paraleloak IF - EHU

K. Par. | Gustafson

2 Gustafson-en legea af = (1-f) + f P

0

10

20

30

40

0 10 20 30 40

azel

eraz

io-fa

ktor

ea

prozesadore kopurua

f konstantea

ideala

t konstantea

Documents

Arkitektura Paraleloak