arkitektura paraleloak
Post on 14-Jan-2016
79 Views
Preview:
DESCRIPTION
TRANSCRIPT
Arkitektura Paraleloak IF - EHU
ARKITEKTURA PARALELOAK
Abiadura Handiko Konputazioa
Agustin Arruabarrenaagustin.arruabarrena@ehu.es
www.sc.ehu.es/arpar
Konputagailuen Arkitektura eta Teknologia saila
Informatika Fakultatea – Euskal Herriko Unibertsitatea
Arkitektura ParaleloakIF - EHU
Arkitektura Paraleloak
0. Sarrera.1. Bektore-konputagailuak.
2. Konputagailu paraleloak (oinarrizko kontzeptuak).3. Datuen koherentzia (SMP).4. Prozesuen sinkronizazioa (SMP).5. Memoriaren kontsistentzia.
6. Komunikazio-sarea. Mezu-ematea.
7. Datuen koherentzia (DSM).8. Begizten paralelizazioa eta atazen
banaketa.9. Abiadura handiko konputagailu paraleloak.
Programazio paraleloa: OpenMP eta MPI (sarrera).
Arkitektura ParaleloakIF - EHU
Arkitektura Paraleloak
0. Sarrera
Arkitektura ParaleloakIF - EHU
Sarrera 40
Konputagailuen eboluzioa azaltzeko, hiru faktore kontuan hartu behar dira: aurrerapenak teknologia
elektronikoan.
aurrerapenak sistemaren arkitekturaren diseinuan.
aurrerapenak sistemaren softwarearen garapenean.
Arkitektura ParaleloakIF - EHU
Sarrera 50
Aurrerapenak teknologia elektronikoan transistore kopurua > 1.000 M
erloju-maiztasuna > 1 GHz
kommutazio-abiadura
integrazio- eta paketatze-teknologia
memoria-edukiera
osagaien/txipen arteko komunikazio-denborak
Arkitektura ParaleloakIF - EHU
Sarrera 60
Aurrerapenak sistemaren arkitekturan RISC arkitekturak memoria-hierarkia unitate funtzional bereziak
segmentazioa (ILP)desordena (Tomasulo) supereskalarrak - VLIW / espekulazioa - aurreikuspenamultithreading
erregistroak
nukleo (core) asko txipean
kalkulurako gune bereziak: txartel grafikoak
Arkitektura ParaleloakIF - EHU
Sarrera 70
Aurrerapenak sistemaren eta aplikazioen softwarean
list scheduling
loop unrolling
software pipelining
trace scheduling
EPIC
…
OpenMP
MPI
UPC
OpenCL / Cuda
...
Arkitektura ParaleloakIF - EHU
Sarrera 80
Prozesadore eskalarren kalkulu-abiadura
> 1 Gflop/s 109 koma higikorreko eragiketa segundoko
Abiadura hori ez da nahikoa hainbat aplikazio tekniko/zientifikotarako
meteorologia, genetika, astrofisika, aeronautika, geofisika, ingeniaritza, materialak, datu-base handiak...
Gogoratu:Mega (M) 106 Giga (G) 109 Tera (T) 1012 Peta
(P) 1015
mikro (µ) 10-6 nano (n) 10-9 pico (p) 10-12
femto (f) 10-15
Arkitektura ParaleloakIF - EHU
Sarrera 90
Hennessy – Patterson, 4. arg.
% 52 urteko
% 20 urteko
Arkitektura ParaleloakIF - EHU
Sarrera 100
Irtenbidea: paralelismoa
- Multicore (2-8 prozesadore txip batean)- Prozesadore asko (?) batera elkarlanean
P = 10.000 proz. → 10.000 GF/s?? Nola erabili P prozesadore? sare bat / errepikapen hutsa /sistema paraleloa
Arkitektura ParaleloakIF - EHU
Sarrera 110
Datu-jarioak
1 asko
1
asko
Agindu-jarioak
SISD
Flynn-en sailkapena
SIMDarray processorsbektore-konputagailuak
MIMDmemoria partekatuamemoria pribatua
Arkitektura ParaleloakIF - EHU
Arkitektura Paraleloak
1. Bektore-konputagailuak
- Sarrera- Datu-dependentziak- Egiturazko dependentziak- Kalkulu-abiadura
- Bektore-kodea
Arkitektura ParaleloakIF - EHU
BK 131
do i = 0, N-1C(i) = A(i) + B(i)
enddo
TE ≈ 7N ziklo
beg: FLD F1,A(R1)FLD F2,B(R1)FADD F3,F2,F1FST C(R1),F3
ADDI R1,R1,#8SUBI R2,R2,#1BNZ R2,beg
Kode eskalar arrunta
Sarrera
Arkitektura ParaleloakIF - EHU
BK 141
LV V1,A(R1)LV V2,B(R1)ADDV V3,V2,V1SV C(R1),V3
Bektore-kodea
Bektoreak: - hasiera-helbidea- luzera- pausoa (stride)
2000 – 2008 – 2016 – 2024 – ... – 2116hasiera-helb. = 2000 / luzera = 16 / pausoa
= 8
Sarrera
do i = 0, N-1C(i) = A(i) + B(i)
enddo
Arkitektura ParaleloakIF - EHU
BK 151
BD Ir AM M M M Id
LV V1,A(R1)
BD Ir AM M M M Id Id ... ...Id
AM M M M IdAM M M M Id
... ...AM M M M Id
Sarrera
Arkitektura ParaleloakIF - EHU
BK 161
LV V1,A(R1)LV V2,B(R1)ADDV V3,V1,V2SV C(R1),V3
BD Ir AM M M M Id ... ... IdBD Ir AM M M M Id ... ... Id
BD . . . . Ir A A Id ... ... IdBD Ir AM . . . . Ir M M M Id ... ... Id
th N
TB ≈ th + N zikloTE ≈ 7 N ziklo
N = 128, th = 14
TE = 896 ziklo
TB = 142 ziklo
Sarrera
Arkitektura ParaleloakIF - EHU
BK 171
Arazoak
Memoria: segmentatuta / bus kop. / moduluak
Unitate funtzionalak: segmentatuta / asko
Bektore-erreg.: tamaina / kopurua / atzipena
Sarrera
LV V1,A(R1)LV V2,B(R1)ADDV V3,V1,V2SV C(R1),V3
BD Ir AM M M M Id ... ... IdBD Ir AM M M M Id ... ... Id
BD . . . . Ir A A Id ... ... IdBD Ir AM . . . . Ir M M M Id ... ... Id
Arkitektura ParaleloakIF - EHU
BK 181
Arazoak
Programak: dena bektore-eragiketak? beti bektoriza daitezke?
do i = 0, N-1A(i) = A(i) + 1
enddo
eskalarki: L0 +0 S0 / L1 +1 S1 / ... / LN-1 +N-1 SN-1
bektorialki: L0 L1 ... LN-1 / +0 +1 ... +N-1 / S0 S1 ... SN-1
Jatorrizko kodea desordenatu egin behar da!
Sarrera
Arkitektura ParaleloakIF - EHU
BK 191
ErregistroakUnita
te funtzion.
Prozesadore eskalarra
(osoa)
Memoria
Bektore-arkitekturaren eskema logikoa(tomasulo)
Bektore-prozesadorek
o kontrola
Helbide- unitatea (datuak)
(erag.)
Erregistroak
Sarrera
Arkitektura ParaleloakIF - EHU
BK 201
Makina-lengoaia
LV Vi,A(Rj) Vi := M(A+Rj)SV A(Rj),Vi M(A+Rj) := Vi
VL → bektoreen luzera
VS → bektoreen pausoa
OPV Vi,Vj,Vk Vi := Vj OP VkOPVS Vi,Vj,Fk Vi := Vj OP FkOPVI Vi,Vj,#k Vi := Vj OP #k
MOVI VL,#64MOVI VS,#8LV V1,A(R1)
Sarrera
Arkitektura ParaleloakIF - EHU
BK 211
Bektore-agindu batek aurreko agindu baten emaitza behar du.
do i = 0, N-1A(i) = A(i) + 1
enddo
LV V1,A(R1)ADDVI V2,V1,#1SV A(R1),V2
- itxaron bektore osoa erregistroan kargatu arte, eta gero irakurri.
- egin Id → Ir zirkuitulaburra, eta irakurri bektore-osagaiak ahal bezain laster:
KATEAKETA (chaining)
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 221
Kateaketa egin gabe
LV V1,A(R1)ADDVI V2,V1,#1SV A(R1),V2
BD Ir AM M M M Id ... Id
BD . . . . . ... . Ir A A Id ... IdBD Ir AM . . ... . . . . . ... . Ir M M M Id ...
TB = 13 + 3N LV
N ADDVI
N SV
N
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 231
Kateaketa eginez
LV V1,A(R1)ADDVI V2,V1,#1SV A(R1),V2
BD Ir AM M M M Id ... ... ... ...Id
BD . . . .
BD Ir AM . . . .
TB = 13 + NLV
ADDVI
SV
N
Ir A A Id ... ... ... IdIr M M M Id ... ...
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 241
LV V1,A(R1)LV V2,B(R1)ADDV V3,V2,V1SV C(R1),V3
BD Ir AM M M M Id ... ... ... ... Id
BD Ir AM M M M Id ... ... ... ... Id
Kateaketa bi agindurekin: C = A + B
BD . . . .
BD Ir AM . . . .
Oro har, eragigai bat unitate funtzional batetik eta bestea erregistro-multzotik (idazten ari da, edo idatzita dago).
Ir A A Id ... ... ... Id
Ir M M M Id ... ...
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 251
Exekuzio-taulak (A = A + 1)
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1) ADDVI V2,V1,#1SV A(R1),V2
kateaketa ez
kateaketa bai
3 3 6+1 6+N
6+N+1 2 9+N+1 9+2N
9+2N+1 3 13+2N+1 13+3N
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1) ADDVI V2,V1,#1SV A(R1),V2
3 3 6+1 6+N
[7] 2 9+1 9+N
[10] 3 13+1 13+N
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 261
kate
ake
ta b
ai
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1) LV V2,B(R1)ADDV V3,V1,V2SV C(R1),V3
Exekuzio-taulak (C = A + B)
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1) LV V2,B(R1)ADDV V3,V1,V2SV C(R1),V3ka
teake
ta e
z
3 3 6+1 6+N
7+N+1 2 10+N+1 10+2N
10+2N+1 3 14+2N+1 14+3N
3 3 6+1 6+N
[8] 2 10+1 10+N
[11] 3 14+1 14+N
4 3 7+1 7+N
4 3 7+1 7+N
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 271
Baliabideak libre al daude?
- unitate funtzionalak
adi: N ziklo okupatuko dira.
Okupatuta badaude, ziklo asko (N) galduko dira.
- bektore-erregistroak
adi: irakurketa/idazketarako bus nahikoak.- memoriako busak
- memoria-moduluak
Egiturazko dependentziak
Arkitektura ParaleloakIF - EHU
BK 281
Memoriako busakZenbat bus daude memoriarekin lan egiteko?
LV V1,A(R1)ADDVI V2,V1,#1SV A(R1),V2
BD Ir AM M M M Id ... ... ... ... Id
BD . . . . Ir A A Id ... ... ... Id
BD Ir AM . . . . ?
TB ≈ 2 N
LV
ADDVI
SV
busa okupatuta
... Ir M M M Id ...
bus bakar bat
Egiturazko dependentziak
Arkitektura ParaleloakIF - EHU
BK 291
Memoria-bus bakarra (A = A + 1)
kateaketa bai
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1) ADDVI V2,V1,#1SV A(R1),V2
3 3 6+1 6+N
[7] 2 9+1 9+N
[6+N] 3 9+N+1 9+2N
Egiturazko dependentziak
Arkitektura ParaleloakIF - EHU
BK 301
Memoria-bus bakarra (C = A + B)
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1) LV V2,B(R1)ADDV V3,V2,V1SV C(R1),V3ka
teake
ta b
ai
3 3 6+1 6+N
[10+N] 2 12+N+1 12+2N
[9+2N] 3 12+2N+1 12+3N
6+N 3 9+N+1 9+2N
TB ≈ 3 NLV
ADDV
SV
LV
Egiturazko dependentziak
Arkitektura ParaleloakIF - EHU
BK 311
kate
ake
ta b
ai Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1) LV V2,B(R1)ADDV V3,V2,V1SV C(R1),V3
3 3 6+1 6+N
[8] 2 10+1 10+N
[6+N] 3 9+N+1 9+2N
4 3 7+1 7+N
TB ≈ 2 NLV
ADDV
SV
LV
Egiturazko dependentziak
Bi memoria-bus (C = A + B)
Arkitektura ParaleloakIF - EHU
BK 321
Memoria-moduluak
Arazoak:- memoria-agindu bat bere buruarekin.- memoria-agindu bat beste batzuekin.
Libre al daude erabili behar diren memoria-moduluak?Okupatuta badaude, LV/SV aginduak zain geratuko dira.
Egiturazko dependentziak
Arkitektura ParaleloakIF - EHU
BK 331
Memoria-eragiketa bakarra
m0m1m2m3
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
M M M
Zenbat modulu erabiltzen dira? Beraz, ez dago arazorik baldin
mk / ZKH(mk,s) ≥ tm
tm = 3 ziklo
mk = 4s = 1
mk / ZKH(mk,s)
Egiturazko dependentziak
Arkitektura ParaleloakIF - EHU
BK 341
A00 A01 A02 A03
- A10 A11 A12
A13 - A20 A21
A22 A23 - A30
A31 A32 A33 -
m0 m1 m2m3
Padding
Errenkadak: s = 1 arazorik ezZutabeak:
s = 4 arazo askoDiagonal n.:
s = 5 arazorik ezDiagonal
tx.:s = 3 arazorik ez
s = 1 arazorik ezs = 5 arazorik ezs = 6 arazoak
s = 4 arazoak
m0 m1 m2m3A00 A01 A02 A03
A10 A11 A12 A13
A20 A21 A22 A23
A30 A31 A32 A33
Egiturazko dependentziak
Arkitektura ParaleloakIF - EHU
BK 351
Memoria-eragiketa bat baino gehiago
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1) ADDVI V2,V1,#1SV A(R1),V2
3 3 6+1 6+N
[7] 2 9+1 9+N
[10]
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19m0m1m2m3m4m5m6m7
M M M M M M M M M M M M M M M M M M M M M M M M
M M M M M M M M M M M M M M M M M M M M M
- - -
M M M M M M M M M M M
Egiturazko dependentziak
Arkitektura ParaleloakIF - EHU
BK 361
Zenbat ziklo itxaron behar da, erabili behar den memoria-modulua libre izan arte (s=1)? Erabili ezin diren moduluen zerrenda osatu behar da:1. Kalkulatu zein modulutan hasiko den
memoriako aurreko agindua (j): (hk – hj) + hasiera-moduluaj
2. Gehitu aurretik eta atzetik tm-1 modulu.3. k aginduak erabili behar duen modulua zerrenda horretan badago, itxaron zerrendako posizioko adinako ziklo.
Egiturazko dependentziak
Arkitektura ParaleloakIF - EHU
BK 371
Ex.has. Mod.ok. Itx. UF lat. 1.dat N.dat
LV V1,A(R1) ADDVI V2,V1,#1SV A(R1),V2
3 3 6+1 6+N
[7] 2 9+1 9+N
[10] - 7 -5, 6 0, 1 3 17+1 17+N4
Egiturazko dependentziak
Arkitektura ParaleloakIF - EHU
BK 381
Erregistroen tamaina (Lmax)
- zer egin bektoreak luzeagoak badira?
do i = 0, N-1A(i) = A(i) + 1
enddo
MOVI VS,#1MOVI R1,#N
segi: MOV VL,R1 LV V1,A(R2)ADDVI V2,V1,#1SV A(R2),V2ADDI R2,R2,#LmaxSUBI R1,R1,#LmaxBGTZ R1,segi
TB = N/Lmax (th + tbeg) + tb N
strip mining
Egiturazko dependentziak
TB = 30 + 3N; N = 500; Lmax = 64; tbeg = 10
→ 8×(30+10) + 1.500 = 1.820 (+ % 19)
Arkitektura ParaleloakIF - EHU
BK 391
Hiru parametro erabili ohi dira “abiadura” adierazteko:
- Exekuzio-denbora (ziklotan zein segundotan).
- Kalkulu-abiadura: exekutatu diren koma higikorreko eragiketen kopurua, segundoko.
- Azelerazio-faktorea (speed-up): zenbat bider azkarragoa den bektore-exekuzioa exekuzio eskalarra baino.
Kalkulu-abiadura
Arkitektura ParaleloakIF - EHU
BK 401
0
50
100
150
200
250
300
0 25 50 75 100 125 150
N
TB = 30 + 2N
TB
Exekuzio-denbora (N-ren arabera)
esk.: TE = te N
bekt.: TB = th + tb N
th
malda = tb
ADI: zikloak!segundotan emateko, erloju-periodoaz (T) biderkatu behar da.
Kalkulu-abiadura
Arkitektura ParaleloakIF - EHU
BK 411
Kalkulu-abiadura (N-ren arabera)
RB = N / TB = N / (th + tbN)
N
R∞
RB
R∞/2
N1/2
[ ] × EragKop × F MF/s
R∞ = [1 / tb] × EK × F
N1/2 = th / tb
N1/2 → R∞ / 2
Kalkulu-abiadura
Arkitektura ParaleloakIF - EHU
BK 421
Azelerazio-faktorea (speed-up)
KB = TE / TB = te N / (th + tbN)
K∞ = te / tb
TE = TB
te NB = th + tb NB → NB = N1/2 / (K∞– 1)
Bektore-luzera minimoa
Kalkulu-abiadura
Arkitektura ParaleloakIF - EHU
BK 431
Kode eskalarraren eragina: Amdahl-en legea.
Kode zati bat, f, bektorialki, eta bestea, 1–f, eskalarki.
TBE = f TB + (1-f) TE
KBE = TE / TBE
= TE / (f TB + (1–f) TE)
= KB / (KB – f (KB–1))
Kalkulu-abiadura
Arkitektura ParaleloakIF - EHU
BK 441
Amdahl-en legea
Kalkulu-abiadura
KB = ∞
0
2
4
6
8
10
12
14
16
0 0.2 0.4 0.6 0.8 1
azel
eraz
io-f
akto
rea
(speed-up)
f (bektorizazio-faktorea)
(KB = 2, 4, 8, 16)
KBE = KB / (KB – f (KB–1))
Arkitektura ParaleloakIF - EHU
BK 451
Amdahl-en legea
Kalkulu-abiadura:
RBE = N / TBE = N / (f TB + (1-f) TE) =
= N / (f (th + tb N) + (1-f) te N) =
= N / (f (th + tb N) + (1-f) K∞ tb N) [× EK × F]
Kalkulu-abiadura
Arkitektura ParaleloakIF - EHU
BK 461
Amdahl-en legearen eragina
CRAY X-MPtb = 10 ns
te = 66,6ns
→ K∞ = 6,60
2
4
6
8
10
12
14
16
0 0.2 0.4 0.6 0.8 1
azel
eraz
io-f
akto
rea
f
Kalkulu-abiadura
tb = 5 ns
te = 66,6 ns
tb = 10 ns
te = 33,3 ns
Arkitektura ParaleloakIF - EHU
Arkitektura Paraleloak
1. Bektore-konputagailuak
- Sarrera- Datu-dependentziak- Egiturazko dependentziak- Kalkulu-abiadura
- Bektore-kodea- datu-dependentziak- bektorizazioa- optimizazioak
Arkitektura ParaleloakIF - EHU
BK 481
Begizta bat bektorialki exekutatu ahal izateko, aginduen jatorrizko ordena aldatu behar da.
eskalarki: L0 +0 S0 / L1 +1 S1 / ... / LN-1 +N-1 SN-1
bektorialki: L0 L1 ... LN-1 / +0 +1 ... +N-1 / S0 S1 ... SN-1
Adi: ordena-aldaketak egin daitezke, baina aginduen arteko datu-dependentziak errespetatu egin behar dira, beti!
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 491
dependentzia
RAW
i: A =
... j:= A
antidependentzia
WAR
i: = A
... j: A =
irteera-dependentzia
WAW
i: A =...
j: A =
i j i j i j
Gogoratu: dependentzia batek eragiketen arteko ordena-erlazio jakin bat ezartzen du.
benetako dependentziak
izen-dependentziak
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 501
Begiztekin lan egin behar denez, dependentziak edozein iteraziotako aginduen artean eman daitezke.
i1 eta i2 iterazioko aginduen arteko dependentzia bat badago, i2 – i1 distantziakoa dela esaten da.
Dependentziak bi graforen bidez adierazi ohi dira: dependentzia-grafoa eta iterazio-espazioa izenekoak.
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 511
do i = 2, N-21: A(i) = B(i) + 22: C(i) = A(i-2) + A(i+1)
enddo
1
2
A,2
A,1
A(2) = B(2) + 2C(2) = A(0) + A(3)
A(3) = B(3) + 2C(3) = A(1) + A(4)
A(4) = B(4) + 2C(4) = A(2) + A(5)
A(5) = B(5) + 2C(5) = A(3) + A(6)
Dimentsio bakarreko begiztak
Dependentzia-grafoa
iIterazio-espazioa
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 521
Bi dimentsioko begiztak
do i = 2, N-1 do j = 1, N-21: A(i,j) = A(i,j-1) * 22: C(i,j) = A(i-2,j+1) + 1 enddoenddo
1
2
A,(2,-1)
A(0,1)
i
j
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 531
do i = 2, N-311: A(i) = B(i) + 22: C(i) = A(i-2)3: D(i+1) = C(i) + C(i+1)4: B(i+1) = B(i) + 15: D(i+30) = A(i)enddo
1
2
3
4
5
A,0
A,2
C,0 C,1
D,29
B,1
B,1
Beste adibide bat
Datu-dependentziak
Arkitektura ParaleloakIF - EHU
BK 541
do i = 0, N-1 A(i) = B(i) + C(i)enddo
MOVI VL,#NMOVI VS,#1
LV V1,B(R1)LV V2,C(R1)ADDV V3,V1,V2SV A(R1),V3
1. adibidea
Ikus dezagun nola sortu bektore-kodea zenbait adibideren bidez.
Bektorizazioa
Arkitektura ParaleloakIF - EHU
BK 551
do i = 0, N-11: A(i) = B(i) + C(i)2: D(i) = A(i)enddo
MOVI VL,#NMOVI VS,#1
(1) LV V1,B(R1)LV V2,C(R1)ADDV V3,V1,V2SV A(R1),V3
(2) SV D(R1),V3
2. adibidea
1
2
A,0
i
Bektorizazioa
Arkitektura ParaleloakIF - EHU
BK 561
do i = 1, N-11: A(i) = B(i) + C(i)2: D(i) = A(i-1)enddo
MOVI VL,#N-1MOVI VS,#1
(1) LVV1,B+1(R1)LVV2,C+1(R1)ADDV V3,V1,V2SVA+1(R1),V3
(2) LV V4,A(R1)SVD+1(R1),V4
3. adibidea
1
2
A,1
i
Bektorizazioa
Arkitektura ParaleloakIF - EHU
BK 571
do i = 0, N-21: A(i) = B(i) + C(i)2: D(i) = A(i+1)enddo
MOVI VL,#N-1MOVI VS,#1
(2) LVV1,A+1(R1)SV D(R1),V1
(1) LV V2,B(R1)LV V3,C(R1)ADDV V4,V2,V3SV A(R1),V4
4. adibidea
1
2
i
A,1
Bektorizazioa
Arkitektura ParaleloakIF - EHU
BK 581
do i = 1, N-11: A(i) = B(i-1) + 12: B(i) = A(i)enddo
5. adibidea
1
2
A,0
B,1
do i = 3, N-1 A(i) = A(i-3) * 3enddo
1
A,3
Bektorizazioa
Arkitektura ParaleloakIF - EHU
BK 591
do i = 0, N-1do j = 0, M-1 A(i,j) = B(i,j) + C(i,j)enddoenddo
6. adibidea: bi dimentsioko bektoreak (errenk.)
MOVI R2,#NMOVI VL,#MMOVI VS,#1
beg: LV V1,B(R1)LV V2,C(R1)ADDV V3,V1,V2SV A(R1),V3
ADDI R1,R1,#MSUBI R2,R2,#1BNZ R2,beg
0,0 0,1 ... 0,M-1
1,0 1,1 ... 1,M-1
... ... ... ...
N-1,0 N-1,1 ... N-1,M-1
As=1
A+M
Bektorizazioa
Arkitektura ParaleloakIF - EHU
BK 601
do i = 0, N-1do j = 0, M-1 A(i,j) = B(i,j) + C(i,j)enddoenddo
6. adibidea: bi dimentsioko bektoreak (zutab.)
MOVI R2,#MMOVI VL,#NMOVI VS,#M
beg: LV V1,B(R1)LV V2,C(R1)ADDV V3,V1,V2SV A(R1),V3
ADDI R1,R1,#1SUBI R2,R2,#1BNZ R2,beg
0,0 0,1 ... 0,M-1
1,0 1,1 ... 1,M-1
... ... ... ...
N-1,0 N-1,1 ... N-1,M-1
A
s=M
A+1
Bektorizazioa
Arkitektura ParaleloakIF - EHU
BK 611
Begizta bat bektorizatu ahal izateko baldintza:
Dependentziek ez dute ziklorik osatzen dependentzia-grafoan.
Oro har, begizta baten agindu batzuk bektore gisa exekuta ahal izango ditugu, baina agian beste batzuk ez (“fisioa”):
Bektorizazioa
Arkitektura ParaleloakIF - EHU
BK 621
do i = 1, N-11: A(i) = B(i)2: B(i) = B(i-1)enddo
1
2
B,0
B,1
MOVI VL,#N-1MOVI VS,#1
(1) LV V1,B+1(R1)SV A+1(R1),V1
(2) MOVI R3,#N-1beg: FLD F1,B(R2)
FST B+1(R2),F1ADDI R2,R2,#1SUBI R3,R3,#1BNZ R3,beg
Bektorizazioa
Arkitektura ParaleloakIF - EHU
BK 631
Nork analizatu behar ditu dependentziak? Programatzaileak edo konpiladoreak?
do i = L1, L2 X(a*i+b) = = X(c*i+d)enddo
L1 L2
i
a*i+b
c*i+d
d - bZKH(c,a)
Z → ez dago depend.
Automatikoki, begiztaren indizearen funtzio linealak soilik.
i1 i2
Dependentzia-proba
Arkitektura ParaleloakIF - EHU
BK 641
iL1 L2
iL1 L2
iL1 L2
Dependentzia-proba
Arkitektura ParaleloakIF - EHU
BK 651
do i = 1, 100 A(2*i) = ... ... = A(2*i+1)enddo
(1 – 0) / ZKH(2, 2) = 1/2 → ez
do i = 5, 100 A(i-5) = ... ... = A(2*i+90)enddo
(90 – (-5)) / ZKH(2, 1) = 95 → bai?
wr: A0 ... A95
rd: A100 ... A290
Dependentzia-proba
Arkitektura ParaleloakIF - EHU
BK 661
do i = 1, 100 A(3*i+100) = ... ... = A(2*i-1)enddo
(100 – (-1)) / ZKH(2, 3) = 101 → bai?
do i = 1, 100 A(6*i+3) = ... ... = A(3*i+81)enddo
(81 – 3) / ZKH(6, 3) = 26 → bai?
wr: A9 ... A603
rd: A84 ... A381
wr: A103 ... A400
rd: A1 ... A199
i=1, wr A103 i=52, rd A103
i=1, rd A84 i=14, wr A84
i=26, rd A159 i=26, wr A159
i=27, wr A165 i=28, rd A165
Dependentzia-proba
Arkitektura ParaleloakIF - EHU
BK 671
Adi: memoria-atzipenen pausoa bi tokitan adieraz daiteke: begiztaren mugen definizioan, edo aginduetan bertan.ZKH proba erabili baino lehen, begiztak “normalizatu” behar dira (begiztaren pausoa, 1).
do i = 1, 100, 2 A(i) = ... B(2*i+5) = ...enddo
do k = 1, 50 A(2*k-1) = ... B(4*k+3) = ...enddo
Dependentzia-proba
Arkitektura ParaleloakIF - EHU
BK 681
LaburBegiztak bektore moduan exekuta daitezkeen jakiteko, aginduen arteko dependentziak analizatu behar dira.Bektore-konpiladoreak analizatuko ditu dependentziak, atzipenen pausoa konstantea den kasuetan.Dependentzia dagoen jakiteko, ZKH proba erabil daiteke.Aginduak bektoriza daitezke, baldin eta dependentzia-ziklo batean sartuta ez badaude.
Bektorizazioa
Arkitektura ParaleloakIF - EHU
BK 691
Dependentzien analisi automatikoa ez da sinplea. Konpiladorea dependentzia dagoen ala ez erabakitzeko gauza ez bada, badaezpada ere, dependentzia dagoela erabakiko du.
Bestalde, oso garrantzitsua da bektorizazio-frakzio handiak eskuratzea (Amdahl!).Beraz, hainbat eraldaketa edo optimizazio erabiltzen dira bektorizatze-prozesua errazteko.Hona hemen optimizazio nagusiak:
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 701
1 Aurreranzko ordezkapen globalaDependentzien analisia errazteko, egindako definizio guztiak ordezkatu egin behar dira.
NP1 = L+1NP2 = L+2...do i = 1, L B(i) = A(NP1) + C(i) A(i) = A(i) – 1 do j = 1, L D(j,NP1) = D(j-1,NP2)*C(j) +1 enddoenddo
L+1
L+1 L+2
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 711
2 Indukzio-aldagaiakBegiztaren barruan progresio aritmetikoan aldatzen diren aldagaiak ordezkatu behar dira.
j = 2k = 2do i = 1, L j = j + 5 R(k) = R(j) + 1 k = k + 3enddo
i = 1 2 3 4 5 ...j = 7 12 17 22 27 ...k = 2 5 8 11 14 ...
j = 5*i + 2k = 3*i - 1
do i = 1, L R(3*i-1) = R(5*i+2) + 1enddo
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 721
3 Antidependentziak
do i = 0, N-21: A(i) = B(i) + C(i)2: D(i) = A(i) + A(i+1)enddo
1
2
A,0
A,1
do i = 0, N-20: [T(i)] = A(i+1)1: A(i) = B(i) + C(i)2: D(i) = A(i) + [T(i)]enddo
A,0
T,0
1
2
0
A,1
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 731
3 Antidependentziak
do i = 0, N-21: A(i) = B(i) + C(i)2: D(i) = A(i) + A(i+1)enddo
1
2
A,0
A,1
MOVI VL,#N-1MOVI VS,#1
(2/0) LV V1,A+1(R1)
(1) LV V2,B(R1)LV V3,C(R1)ADDV V4,V3,V2SV A(R1),V4
(2) ADDV V5,V1,V4SV D(R1),V5
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 741
T,0
4 Irteera-dependentziak
do i = 0, N-31: A(i) = B(i) + C(i)2: A(i+2) = A(i) * D(i)enddo
do i = 0, N-31: [T(i)] = B(i) + C(i)2: A(i+2) = [T(i)] * D(i)3: A(i) = [T(i)]enddo
T,01
2
A,0
A,2A,2
2
3
1
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 751
4 Irteera-dependentziak
do i = 0, N-31: A(i) = B(i) + C(i)2: A(i+2) = A(i) * D(i)enddo
1
2
A,0
A,2
MOVI VL,#N-2MOVI VS,#1
(1) LV V1,B(R1)LV V2,C(R1)ADDV V3,V2,V1
(2) LV V4,D(R1)MULV V5,V3,V4SV A+2(R1),V5
(1/3) SV A(R1),V3
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 761
5 Begizta-trukea
do i = 0, N-1 do j = 1, N-1 A(i,j) = A(i,j-1) + 1 enddoenddo
1
A,(0,1)
i
j
ez
bai
do j = 1, N-1 do i = 0, N-1 A(i,j) = A(i,j-1) + 1 enddoenddo
Optimizazioak
zutabe bat
Arkitektura ParaleloakIF - EHU
BK 771
5 Begizta-trukea
do i = 1, N-1 do j = 1, N-21: A(i,j) = B(i-1,j+1) + 12: B(i,j) = A(i,j-1) enddoenddo
1
2
A,(0,1)
B,(1,-1)
i
j
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 781
5 Begizta-trukea
Begiztak trukatu daitezke, baldin eta dependentzien distantzia-bektore berrietan 0 ez den pisu handieneko lehen osagaia positiboa bada.Adibidez,
(0, 1)→ (1, 0) ondo da(1, -1) → (-1, 1) ezin da
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 791
5 Begizta-trukea
Zenbait kasutan, trukea eta fisioa batera erabili behar dira:
do i = 1, N-1 do j = 1, N-11: A(i,j) = A(i-1,j) + 12: B(i,j) = B(i,j-1) * 2 enddoenddo
i
j
2
B,(0,1)
1
A,(1,0)
Optimizazioak
1 → errenkadaka; eta gero, 2 → zutabeka
Arkitektura ParaleloakIF - EHU
BK 801
5 Begizta-trukea
Beste kasu batzuetan, eraginkortasuna dela eta merezi du begiztak trukatzea.
do i = 0, 99 do j = 0, 9 A(i,j) = A(i,j) + 1 enddoenddo
A0,0 ... A0,9
... ...
... ...
... ...A99,0 .. A99,9
Optimizazioak
Ahalik eta bektorerik luzeenak prozesatu (erregistroen tamaina kontuan hartuz).
Arkitektura ParaleloakIF - EHU
BK 811
6 Hedapen eskalarra
Begiztan aldagai eskalar laguntzaileak erabiltzen direnean, bektorizazioa galaratzen duten hainbat dependentzia sortzen dira.
do i = 0, N-1 batura = A(i) + B(i) C(i) = batura * batura D(i) = batura * 2enddo
Adi, bukaeran: batura = batura(N-1)
(i)(i) (i)(i)
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 821
7 Begizten fusioa
Aukera badago, egokia da bi begizta bat bihurtzea (hasiera-denborak, gainkargak... aurrezteko).do i = 0, N-1 A(i) = B(i) + C(i)enddo
do i = 0, N-1 D(i) = E(i) * 5enddo
do i = 0, N-1 A(i) = B(i) + C(i) D(i) = E(i) * 5enddo
Adi, esanahiari (dependentziei!) eutsi behar zaio.
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 831
7 Begizten fusioa
do i = 0, N-2 A(i) = B(i) + C(i)enddo
do i = 0, N-2 D(i) = A(i+1) + 1enddo
do i = 0, N-2 A(i) = B(i) + C(i) D(i) = A(i+1) + 1enddo
???
Optimizazioak
Ez da gauza bera!
Arkitektura ParaleloakIF - EHU
BK 841
8 Begizten kolapsoa
Bi dimentsioko begizta dimentsio bakarreko begizta bihurtzea, bektore luzeagoak prozesatzeko.
float A(10,10)
do i = 0, 9 do j = 0, 9 A(i,j) = A(i,j) * 2.0 enddoenddo
float A(100)
do i = 0, 99 A(i) = A(i) * 2.0enddo
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 851
Begiztaren exekuzioa bukatu ondoren, aldagai laguntzaileen azken balioak (begizta eskalarki exekutatzean hartuko lituzketenak) sortu behar dira:
begizta-indizeakindukzio-aldagaiakeskalarrak...
Optimizazioak
Arkitektura ParaleloakIF - EHU
BK 861
Ohikoa da, kalkulua egiten denean, bektore baten osagai bakar batzuk baino ez prozesatu behar izatea:
do i = 0, N-1 if (B(i) > 5.0) A(i) = A(i) + 1.5enddo
Ohiko irtenbidea: maskarak (VM, vector mask).
VM erregistroan:1 – osagai hori prozesatu behar da 0 – osagai hori “maskaratu” behar da
Maskara-erregistroa
Arkitektura ParaleloakIF - EHU
BK 871
Lehenik, maskara sortzen da, eskuarki konparazio-eragiketa baten bidez; gero, bektore-eragiketa egiten da, maskara-erregistroa haintzat hartuz.
- VM kargatzeko (konparazioa)SxxV V1,V2 (ad. set
equal)
SxxVS V1,F1
- VM hasieratzeko (denak 1)CVM
- VM-ren 1ekoak kontatzekoPOP R1,VM
MOVI VL,#NMOVI VS,#1
MOVI F1,#5.0LV V1,B(R1)SGTVS V1,F1
LV V2,A(R1)ADDVI V3,V2,#1.5SV A(R1),V3
CVM
Maskara-erregistroa
Arkitektura ParaleloakIF - EHU
BK 881
Pauso konstanteko (VS) bektoreak bakarrik prozesatu ditugu.
LV V1,A(R1) VL osagai, VS distantziara, A+R1 helbidetik aurrera
Hainbat kasutan, ordea, pauso aldakorreko bektoreak prozesatu behar dira.
s=3
5
14
4
1 8Nola?
Indize-bektoreak
Arkitektura ParaleloakIF - EHU
BK 891
Pauso aldakorreko bektoreak prozesatzeko, indize-bektoreak erabili ohi dira (eta helbideratze-modu indizeduna):LVI V1,A(V2) V2 indize-erregistroa da, eta
prozesatu behar diren osagaien posizioak adierazten ditu.
SVI V1,A(V2)
CVI V1,R1 0, R1, 2R1... indize-bektorea sortu.
Indize-bektoreak
Arkitektura ParaleloakIF - EHU
BK 901
do i = 0, M A(i*i) = B(i*i) + 1enddo
MOVI VL,#M+1
MOVI R1,#1CVI V4,R1MULV V5,V4,V4
LVI V1,B(V5)ADDVI V2,V1,#1SVI A(V5),V2
Oro har, atzipen indizedunen exekuzio-denbora atzipen arrunten (pauso konstanteen) bidez egindakoena baino handiagoa ohi da (ez da zikloko osagai bat lortzen).
Indize-bektoreak
Arkitektura ParaleloakIF - EHU
BK 911
Helbideratze indizeduna “maskara gisa”
MOVI VL,#NMOVI VS,#1MOVI F1,#5.0
LV V1,B(R1)SGTVS V1,F1
MOVI R2,#1CVI V2,R2POP R1,VMMOV VL,R1CVM
LVI V3,A(V2)ADDVI V4,V3,#1.5SVI A(V2),V4
do i = 0, N-1 if (B(i) > 5.0) A(i) = A(i) + 1.5enddo
VM = 1 0 0 1 1 1 0 1V2 = 0 3 4 5 7R1 = 5
Indize-bektoreak
Arkitektura ParaleloakIF - EHU
BK 921
Bektore-prozesadoreak bektoreak prozesatzeko arkitektura berezi eta oso eraginkorrak dira. Ezaugarri hauek dituzte:
▪ Makina-lengoaia berezia, bektoreak agindu bakar batez prozesatu ahal izateko.
▪ Memoria irakurtzeko/idazteko banda-zabalera handia.
▪ Unitate funtzional segmentatu asko.▪ Aginduen exekuzioa kateatu egiten da.▪ Bektore-kodea sortzeko konpiladore
onak.
Laburpena
Arkitektura ParaleloakIF - EHU
BK 931
Duela gutxi arte, superkonputagailuak bektore-konputagailuak ziren. Gaur, ordea, MIMD motako konputagailu paraleloak dira azkarrenak. Salbuespenak badaude; adib., Earth Simulator konp.
Laburpena
Bektore-prozesadoreak MIMD sistema paraleloen nodo bereziak izan daitezke, bektoreak prozesatzen espezializatuta.
Bestalde, oraingo prozesadore guztiek badituzte “bektore-eragiketak” agindu-multzoan. Adibidez (PA-RISC): FMAC, multiply-accumulate.
please, don’t forget exercices!
Arkitektura Paraleloak IF - EHU
Duela gutxi arte, superkonputagailuak bektore-konputagailuak ziren. Gaur, ordea, MIMD motako konputagailu paraleloak dira azkarrenak. Salbuespenak badaude; adib., Earth Simulator konp.
Bektore-prozesadoreak MIMD sistema paraleloen nodo bereziak izan daitezke, bektoreak prozesatzen espezializatuta.
Bestalde, oraingo prozesadore guztiek badituzte “bektore-eragiketak” agindu-multzoan.Adibidez (PA-RISC): FMAC, multiply-accumulate.
BK | Laburpena
top related