abiadura handiko konputazioa - sc.ehu.es · arkitektura paraleloak if - ehu arkitektura paraleloak...
TRANSCRIPT
Arkitektura Paraleloak IF - EHU
ARKITEKTURA
PARALELOAK Abiadura Handiko Konputazioa
Agustin Arruabarrena [email protected]
www.sc.ehu.es/arpar
Konputagailuen Arkitektura eta Teknologia saila
Informatika Fakultatea – Euskal Herriko Unibertsitatea
Arkitektura Paraleloak
IF - 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 Paraleloak
IF - EHU
Sarrera 4 0
Konputagailuen eboluzioa azaltzeko, hiru faktore kontuan hartu behar dira:
aurrerapenak teknologia elektronikoan.
aurrerapenak sistemaren arkitekturaren
diseinuan.
aurrerapenak sistemaren softwarearen
garapenean.
Arkitektura Paraleloak
IF - EHU
Sarrera 5 0
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 Paraleloak
IF - EHU
Sarrera 6 0
Aurrerapenak sistemaren arkitekturan
RISC arkitekturak memoria-hierarkia unitate funtzional bereziak
segmentazioa (ILP)
desordena (Tomasulo)
supereskalarrak - VLIW / espekulazioa - aurreikuspena multithreading
erregistroak
nukleo (core) asko txipean
kalkulurako gune bereziak: txartel grafikoak
Arkitektura Paraleloak
IF - EHU
Sarrera 7 0
Aurrerapenak sistemaren eta aplikazioen softwarean
list scheduling
loop unrolling
software pipelining
trace scheduling
EPIC
…
OpenMP
MPI
UPC
OpenCL / Cuda
...
Arkitektura Paraleloak
IF - EHU
Sarrera 8 0
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 Paraleloak
IF - EHU
Sarrera 10 0
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 Paraleloak
IF - EHU
Sarrera 11 0
Datu-jarioak
1 asko
1
asko
Agindu- jarioak
SISD
Flynn-en sailkapena
SIMD
array processors
bektore-konputagailuak
MIMD
memoria partekatua
memoria pribatua
Arkitektura Paraleloak
IF - EHU
Arkitektura Paraleloak
1. Bektore-konputagailuak
- Sarrera
- Datu-dependentziak
- Egiturazko dependentziak
- Kalkulu-abiadura
- Bektore-kodea
Arkitektura Paraleloak
IF - EHU
BK 13 1
do i = 0, N-1
C(i) = A(i) + B(i)
enddo
TE ≈ 7N ziklo
beg: FLD F1,A(R1)
FLD F2,B(R1)
FADD F3,F2,F1
FST C(R1),F3
ADDI R1,R1,#8
SUBI R2,R2,#1
BNZ R2,beg
Kode eskalar arrunta
Sarrera
Arkitektura Paraleloak
IF - EHU
BK 14 1
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV C(R1),V3
Bektore-kodea
Bektoreak:
- hasiera-helbidea
- luzera
- pausoa (stride)
2000 – 2008 – 2016 – 2024 – ... – 2116
hasiera-helb. = 2000 / luzera = 16 / pausoa = 8
Sarrera
do i = 0, N-1
C(i) = A(i) + B(i)
enddo
Arkitektura Paraleloak
IF - EHU
BK 15 1
BD Ir AM M M M Id
LV V1,A(R1)
BD Ir AM M M M Id Id ... ... Id
AM M M M Id
AM M M M Id
... ...
AM M M M Id
Sarrera
Arkitektura Paraleloak
IF - EHU
BK 16 1
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V1,V2
SV C(R1),V3
BD Ir AM M M M Id ... ... Id
BD Ir AM M M M Id ... ... Id
BD . . . . Ir A A Id ... ... Id
BD Ir AM . . . . Ir M M M Id ... ... Id
th N
TB ≈ th + N ziklo
TE ≈ 7 N ziklo
N = 128, th = 14
TE = 896 ziklo
TB = 142 ziklo
Sarrera
Arkitektura Paraleloak
IF - EHU
BK 17 1
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,V2
SV C(R1),V3
BD Ir AM M M M Id ... ... Id
BD Ir AM M M M Id ... ... Id
BD . . . . Ir A A Id ... ... Id
BD Ir AM . . . . Ir M M M Id ... ... Id
Arkitektura Paraleloak
IF - EHU
BK 18 1
Arazoak
Programak: dena bektore-eragiketak?
beti bektoriza daitezke?
do i = 0, N-1
A(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 Paraleloak
IF - EHU
BK 19 1
Erregistroak
Unitate
funtzion.
Prozesadore eskalarra (osoa)
Memoria
Bektore-arkitekturaren eskema logikoa
(tomasulo)
Bektore-prozesadoreko
kontrola
Helbide- unitatea (datuak)
(erag.)
Erregistroak
Sarrera
Arkitektura Paraleloak
IF - EHU
BK 20 1
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 Vk
OPVS Vi,Vj,Fk Vi := Vj OP Fk
OPVI Vi,Vj,#k Vi := Vj OP #k
MOVI VL,#64
MOVI VS,#8
LV V1,A(R1)
Sarrera
Arkitektura Paraleloak
IF - EHU
BK 21 1
Bektore-agindu batek aurreko agindu baten emaitza behar du.
do i = 0, N-1
A(i) = A(i) + 1
enddo
LV V1,A(R1)
ADDVI V2,V1,#1
SV 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 Paraleloak
IF - EHU
BK 22 1
Kateaketa egin gabe
LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
BD Ir AM M M M Id ... Id
BD . . . . . ... . Ir A A Id ... Id
BD Ir AM . . ... . . . . . ... . Ir M M M Id ...
TB = 13 + 3N LV
N ADDVI
N SV
N
Datu-dependentziak
Arkitektura Paraleloak
IF - EHU
BK 23 1
Kateaketa eginez
LV V1,A(R1)
ADDVI V2,V1,#1
SV A(R1),V2
BD Ir AM M M M Id ... ... ... ...Id
BD . . . .
BD Ir AM . . . .
TB = 13 + N
LV
ADDVI
SV
N
Ir A A Id ... ... ... Id
Ir M M M Id ... ...
Datu-dependentziak
Arkitektura Paraleloak
IF - EHU
BK 24 1
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV 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 Paraleloak
IF - EHU
BK 25 1
Exekuzio-taulak (A = A + 1)
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1)
ADDVI V2,V1,#1
SV 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,#1
SV A(R1),V2
3 3 6+1 6+N
[7] 2 9+1 9+N
[10] 3 13+1 13+N
Datu-dependentziak
Arkitektura Paraleloak
IF - EHU
BK 26 1
kate
aketa
ba
i
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V1,V2
SV 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,V2
SV C(R1),V3
kate
aketa
ez
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 Paraleloak
IF - EHU
BK 27 1
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 Paraleloak
IF - EHU
BK 28 1
Memoriako busak
Zenbat bus daude memoriarekin lan egiteko?
LV V1,A(R1)
ADDVI V2,V1,#1
SV 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 Paraleloak
IF - EHU
BK 29 1
Memoria-bus bakarra (A = A + 1)
kateaketa bai
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1)
ADDVI V2,V1,#1
SV 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 Paraleloak
IF - EHU
BK 30 1
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,V1
SV C(R1),V3
kate
aketa
ba
i
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 N LV
ADDV
SV
LV
Egiturazko dependentziak
Arkitektura Paraleloak
IF - EHU
BK 31 1
kate
aketa
ba
i
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1)
LV V2,B(R1)
ADDV V3,V2,V1
SV 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 N LV
ADDV
SV
LV
Egiturazko dependentziak
Bi memoria-bus (C = A + B)
Arkitektura Paraleloak
IF - EHU
BK 32 1
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 Paraleloak
IF - EHU
BK 33 1
Memoria-eragiketa bakarra
m0
m1
m2
m3
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 = 4
s = 1
mk / ZKH(mk,s)
Egiturazko dependentziak
Arkitektura Paraleloak
IF - EHU
BK 34 1
A00 A01 A02 A03
- A10 A11 A12
A13 - A20 A21
A22 A23 - A30
A31 A32 A33 -
m0 m1 m2 m3
Padding
Errenkadak: s = 1 arazorik ez
Zutabeak: s = 4 arazo asko
Diagonal n.: s = 5 arazorik ez
Diagonal tx.: s = 3 arazorik ez
s = 1 arazorik ez
s = 5 arazorik ez
s = 6 arazoak
s = 4 arazoak
m0 m1 m2 m3
A00 A01 A02 A03
A10 A11 A12 A13
A20 A21 A22 A23
A30 A31 A32 A33
Egiturazko dependentziak
Arkitektura Paraleloak
IF - EHU
BK 35 1
Memoria-eragiketa bat baino gehiago
Ex.has. UF lat. 1. dat N. dat
LV V1,A(R1)
ADDVI V2,V1,#1
SV 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 19
m0
m1
m2
m3
m4
m5
m6
m7
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 Paraleloak
IF - EHU
BK 36 1
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 Paraleloak
IF - EHU
BK 37 1
Ex.has. Mod.ok. Itx. UF lat. 1.dat N.dat
LV V1,A(R1)
ADDVI V2,V1,#1
SV 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+N 4
Egiturazko dependentziak
Arkitektura Paraleloak
IF - EHU
BK 38 1
Erregistroen tamaina (Lmax)
- zer egin bektoreak luzeagoak badira?
do i = 0, N-1
A(i) = A(i) + 1
enddo
MOVI VS,#1
MOVI R1,#N
segi: MOV VL,R1
LV V1,A(R2)
ADDVI V2,V1,#1
SV A(R2),V2
ADDI R2,R2,#Lmax
SUBI R1,R1,#Lmax
BGTZ 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 Paraleloak
IF - EHU
BK 39 1
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 Paraleloak
IF - EHU
BK 40 1
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 Paraleloak
IF - EHU
BK 41 1
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 Paraleloak
IF - EHU
BK 42 1
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 Paraleloak
IF - EHU
BK 43 1
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 Paraleloak
IF - EHU
BK 44 1
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
azele
razio
-fakto
rea (
sp
ee
d-u
p)
f (bektorizazio-faktorea)
(KB = 2, 4, 8, 16)
KBE = KB / (KB – f (KB–1))
Arkitektura Paraleloak
IF - EHU
BK 45 1
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 Paraleloak
IF - EHU
BK 46 1
Amdahl-en legearen eragina
CRAY X-MP
tb = 10 ns
te = 66,6ns
→ K∞ = 6,6 0
2
4
6
8
10
12
14
16
0 0.2 0.4 0.6 0.8 1
azele
razio
-fakto
rea
f
Kalkulu-abiadura
tb = 5 ns
te = 66,6 ns
tb = 10 ns
te = 33,3 ns
Arkitektura Paraleloak
IF - EHU
Arkitektura Paraleloak
1. Bektore-konputagailuak
- Sarrera
- Datu-dependentziak
- Egiturazko dependentziak
- Kalkulu-abiadura
- Bektore-kodea
- datu-dependentziak
- bektorizazioa
- optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 48 1
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 Paraleloak
IF - EHU
BK 49 1
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 Paraleloak
IF - EHU
BK 50 1
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 Paraleloak
IF - EHU
BK 51 1
do i = 2, N-2
1: A(i) = B(i) + 2
2: C(i) = A(i-2) + A(i+1)
enddo
1
2
A,2
A,1
A(2) = B(2) + 2
C(2) = A(0) + A(3)
A(3) = B(3) + 2
C(3) = A(1) + A(4)
A(4) = B(4) + 2
C(4) = A(2) + A(5)
A(5) = B(5) + 2
C(5) = A(3) + A(6)
Dimentsio bakarreko
begiztak
Dependentzia-grafoa
i Iterazio-espazioa
Datu-dependentziak
Arkitektura Paraleloak
IF - EHU
BK 52 1
Bi dimentsioko begiztak
do i = 2, N-1
do j = 1, N-2
1: A(i,j) = A(i,j-1) * 2
2: C(i,j) = A(i-2,j+1) + 1
enddo
enddo
1
2
A,(2,-1)
A(0,1)
i
j
Datu-dependentziak
Arkitektura Paraleloak
IF - EHU
BK 53 1
do i = 2, N-31
1: A(i) = B(i) + 2
2: C(i) = A(i-2)
3: D(i+1) = C(i) + C(i+1)
4: B(i+1) = B(i) + 1
5: 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 Paraleloak
IF - EHU
BK 54 1
do i = 0, N-1
A(i) = B(i) + C(i)
enddo
MOVI VL,#N
MOVI VS,#1
LV V1,B(R1)
LV V2,C(R1)
ADDV V3,V1,V2
SV A(R1),V3
1. adibidea
Ikus dezagun nola sortu bektore-kodea zenbait
adibideren bidez.
Bektorizazioa
Arkitektura Paraleloak
IF - EHU
BK 55 1
do i = 0, N-1
1: A(i) = B(i) + C(i)
2: D(i) = A(i)
enddo
MOVI VL,#N
MOVI VS,#1
(1) LV V1,B(R1)
LV V2,C(R1)
ADDV V3,V1,V2
SV A(R1),V3
(2) SV D(R1),V3
2. adibidea
1
2
A,0
i
Bektorizazioa
Arkitektura Paraleloak
IF - EHU
BK 56 1
do i = 1, N-1
1: A(i) = B(i) + C(i)
2: D(i) = A(i-1)
enddo
MOVI VL,#N-1
MOVI VS,#1
(1) LV V1,B+1(R1)
LV V2,C+1(R1)
ADDV V3,V1,V2
SV A+1(R1),V3
(2) LV V4,A(R1)
SV D+1(R1),V4
3. adibidea
1
2
A,1
i
Bektorizazioa
Arkitektura Paraleloak
IF - EHU
BK 57 1
do i = 0, N-2
1: A(i) = B(i) + C(i)
2: D(i) = A(i+1)
enddo
MOVI VL,#N-1
MOVI VS,#1
(2) LV V1,A+1(R1)
SV D(R1),V1
(1) LV V2,B(R1)
LV V3,C(R1)
ADDV V4,V2,V3
SV A(R1),V4
4. adibidea
1
2
i
A,1
Bektorizazioa
Arkitektura Paraleloak
IF - EHU
BK 58 1
do i = 1, N-1
1: A(i) = B(i-1) + 1
2: B(i) = A(i)
enddo
5. adibidea
1
2
A,0
B,1
do i = 3, N-1
A(i) = A(i-3) * 3
enddo
1
A,3
Bektorizazioa
Arkitektura Paraleloak
IF - EHU
BK 59 1
do i = 0, N-1
do j = 0, M-1
A(i,j) = B(i,j) + C(i,j)
enddo
enddo
6. adibidea: bi dimentsioko bektoreak (errenk.)
MOVI R2,#N
MOVI VL,#M
MOVI VS,#1
beg: LV V1,B(R1)
LV V2,C(R1)
ADDV V3,V1,V2
SV A(R1),V3
ADDI R1,R1,#M
SUBI R2,R2,#1
BNZ 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=1
A+M
Bektorizazioa
Arkitektura Paraleloak
IF - EHU
BK 60 1
do i = 0, N-1
do j = 0, M-1
A(i,j) = B(i,j) + C(i,j)
enddo
enddo
6. adibidea: bi dimentsioko bektoreak (zutab.)
MOVI R2,#M
MOVI VL,#N
MOVI VS,#M
beg: LV V1,B(R1)
LV V2,C(R1)
ADDV V3,V1,V2
SV A(R1),V3
ADDI R1,R1,#1
SUBI R2,R2,#1
BNZ 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 Paraleloak
IF - EHU
BK 61 1
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 Paraleloak
IF - EHU
BK 62 1
do i = 1, N-1
1: A(i) = B(i)
2: B(i) = B(i-1)
enddo
1
2
B,0
B,1
MOVI VL,#N-1
MOVI VS,#1
(1) LV V1,B+1(R1)
SV A+1(R1),V1
(2) MOVI R3,#N-1
beg: FLD F1,B(R2)
FST B+1(R2),F1
ADDI R2,R2,#1
SUBI R3,R3,#1
BNZ R3,beg
Bektorizazioa
Arkitektura Paraleloak
IF - EHU
BK 63 1
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 - b
ZKH(c,a) Z → ez dago depend.
Automatikoki, begiztaren indizearen funtzio
linealak soilik.
i1 i2
Dependentzia-proba
Arkitektura Paraleloak
IF - EHU
BK 65 1
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 Paraleloak
IF - EHU
BK 66 1
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 Paraleloak
IF - EHU
BK 67 1
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 Paraleloak
IF - EHU
BK 68 1
Labur
Begiztak 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 Paraleloak
IF - EHU
BK 69 1
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 Paraleloak
IF - EHU
BK 70 1
1 Aurreranzko ordezkapen globala
Dependentzien analisia errazteko, egindako definizio guztiak ordezkatu egin behar dira.
NP1 = L+1
NP2 = 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
enddo
enddo
L+1
L+1 L+2
Optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 71 1
2 Indukzio-aldagaiak
Begiztaren barruan progresio aritmetikoan aldatzen diren aldagaiak ordezkatu behar dira.
j = 2
k = 2
do i = 1, L
j = j + 5
R(k) = R(j) + 1
k = k + 3
enddo
i = 1 2 3 4 5 ...
j = 7 12 17 22 27 ...
k = 2 5 8 11 14 ...
j = 5*i + 2
k = 3*i - 1
do i = 1, L
R(3*i-1) = R(5*i+2) + 1
enddo
Optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 72 1
3 Antidependentziak
do i = 0, N-2
1: 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-2
0: [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 Paraleloak
IF - EHU
BK 73 1
3 Antidependentziak
do i = 0, N-2
1: A(i) = B(i) + C(i)
2: D(i) = A(i) + A(i+1)
enddo
1
2
A,0
A,1
MOVI VL,#N-1
MOVI VS,#1
(2/0) LV V1,A+1(R1)
(1) LV V2,B(R1)
LV V3,C(R1)
ADDV V4,V3,V2
SV A(R1),V4
(2) ADDV V5,V1,V4
SV D(R1),V5
Optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 74 1
T,0
4 Irteera-dependentziak
do i = 0, N-3
1: A(i) = B(i) + C(i)
2: A(i+2) = A(i) * D(i)
enddo
do i = 0, N-3
1: [T(i)] = B(i) + C(i)
2: A(i+2) = [T(i)] * D(i)
3: A(i) = [T(i)]
enddo
T,0 1
2
A,0
A,2
A,2
2
3
1
Optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 75 1
4 Irteera-dependentziak
do i = 0, N-3
1: A(i) = B(i) + C(i)
2: A(i+2) = A(i) * D(i)
enddo
1
2
A,0
A,2
MOVI VL,#N-2
MOVI VS,#1
(1) LV V1,B(R1)
LV V2,C(R1)
ADDV V3,V2,V1
(2) LV V4,D(R1)
MULV V5,V3,V4
SV A+2(R1),V5
(1/3) SV A(R1),V3
Optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 76 1
5 Begizta-trukea
do i = 0, N-1
do j = 1, N-1
A(i,j) = A(i,j-1) + 1
enddo
enddo
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
enddo
enddo
Optimizazioak
zutabe bat
Arkitektura Paraleloak
IF - EHU
BK 77 1
5 Begizta-trukea
do i = 1, N-1
do j = 1, N-2
1: A(i,j) = B(i-1,j+1) + 1
2: B(i,j) = A(i,j-1)
enddo
enddo
1
2
A,(0,1)
B,(1,-1)
i
j
Optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 78 1
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 Paraleloak
IF - EHU
BK 79 1
5 Begizta-trukea
Zenbait kasutan, trukea eta fisioa batera erabili behar dira:
do i = 1, N-1
do j = 1, N-1
1: A(i,j) = A(i-1,j) + 1
2: B(i,j) = B(i,j-1) * 2
enddo
enddo
i
j
2
B,(0,1)
1
A,(1,0)
Optimizazioak
1 → errenkadaka; eta gero, 2 → zutabeka
Arkitektura Paraleloak
IF - EHU
BK 80 1
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
enddo
enddo
A0,0 ... A0,9
... ...
... ...
... ...
A99,0 .. A99,9
Optimizazioak
Ahalik eta bektorerik luzeenak prozesatu (erregistroen tamaina kontuan hartuz).
Arkitektura Paraleloak
IF - EHU
BK 81 1
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 * 2
enddo
Adi, bukaeran: batura = batura(N-1)
(i)
(i) (i)
(i)
Optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 82 1
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) * 5
enddo
do i = 0, N-1
A(i) = B(i) + C(i)
D(i) = E(i) * 5
enddo
Adi, esanahiari (dependentziei!) eutsi behar zaio.
Optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 83 1
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) + 1
enddo
do i = 0, N-2
A(i) = B(i) + C(i)
D(i) = A(i+1) + 1
enddo
???
Optimizazioak
Ez da gauza bera!
Arkitektura Paraleloak
IF - EHU
BK 84 1
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
enddo
enddo
float A(100)
do i = 0, 99
A(i) = A(i) * 2.0
enddo
Optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 85 1
Begiztaren exekuzioa bukatu ondoren, aldagai
laguntzaileen azken balioak (begizta eskalarki exekutatzean hartuko lituzketenak) sortu behar dira:
begizta-indizeak
indukzio-aldagaiak
eskalarrak
...
Optimizazioak
Arkitektura Paraleloak
IF - EHU
BK 86 1
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.5
enddo
Ohiko irtenbidea: maskarak (VM, vector mask).
VM erregistroan:
1 – osagai hori prozesatu behar da
0 – osagai hori “maskaratu” behar da
Maskara-erregistroa
Arkitektura Paraleloak
IF - EHU
BK 87 1
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 kontatzeko
POP R1,VM
MOVI VL,#N
MOVI VS,#1
MOVI F1,#5.0
LV V1,B(R1)
SGTVS V1,F1
LV V2,A(R1)
ADDVI V3,V2,#1.5
SV A(R1),V3
CVM
Maskara-erregistroa
Arkitektura Paraleloak
IF - EHU
BK 88 1
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 8
Nola?
Indize-bektoreak
Arkitektura Paraleloak
IF - EHU
BK 89 1
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 Paraleloak
IF - EHU
BK 90 1
do i = 0, M
A(i*i) = B(i*i) + 1
enddo
MOVI VL,#M+1
MOVI R1,#1
CVI V4,R1
MULV V5,V4,V4
LVI V1,B(V5)
ADDVI V2,V1,#1
SVI 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 Paraleloak
IF - EHU
BK 91 1
Helbideratze indizeduna “maskara gisa”
MOVI VL,#N
MOVI VS,#1
MOVI F1,#5.0
LV V1,B(R1)
SGTVS V1,F1
MOVI R2,#1
CVI V2,R2
POP R1,VM
MOV VL,R1
CVM
LVI V3,A(V2)
ADDVI V4,V3,#1.5
SVI A(V2),V4
do i = 0, N-1
if (B(i) > 5.0) A(i) = A(i) + 1.5
enddo
VM = 1 0 0 1 1 1 0 1
V2 = 0 3 4 5 7
R1 = 5
Indize-bektoreak
Arkitektura Paraleloak
IF - EHU
BK 92 1
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 Paraleloak
IF - EHU
BK 93 1
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