Lekcija Konveijers

1.

Ievads datoru arhitektūrā
DST203
5. Lekcija
Konveijers
Asoc.prof., Dr.sc.ing, Dmitrijs Bļizņuks
1

2.

Outline
Tipiskā komandas izpilde
Konveijers
Konflikti
Paralelizācijas ierobežojums
2

3.

Skaitļošanas spēja
1978
2020
Frekvences paaugstinājums
Skaitļošanas spējas
Vairaki kodoli?
Intel 8086
AMD Ryzen 9 3950X
0.3 MIPS
750 000 MIPS
x1 000
x2 500 000
pie 5.0 MHz
pie 4.6 GHz
MIPS - Millions of instructions per second
(vienkāršākais skaitļošanas mērs)
Sega (spēļu konsole)
16 MIPS
Cray (superdators)
160 MIPS
iPhone 5S
18 200 MIPS
…
‘Meaningless Indicator of Processor Speed’
3
3

4.

Komandas izpilde
1. Fetch instruction
FI
2. Decode instruction
DI
3. Calculate operand(s)
CO
4. Fetch operand(s)
FO
5. Execute instruction
EI
6. Write operand
WO
4
4

5.

Secīgā komandas izpilde
Secīgā izpildē jaunas komandas izpilde sākas pēc iepriekšēja
rezultata pieraksta (izpildes).
n komandu izpildes laiks t ir:
t=6*n
5
5

6.

Konveijerizācija
Konveijers ļauj pāātrināt programmas izpildi, apstradājot
vairākas darbības vienlaicīgi.
n komandu izpildes laiks t ir:
t = 6 + (n – 1)
6
6

7.

Pamati
Datori izpilda miljoniem darbību sekundē tāpēc mums ir svarīga to caurlaides spēja nevis
darbības ātrums
Katrā laika momentā dažādas komandas būs dažādos izpildes posmos (IF DI CO FO EI
WR)
Ilgākais posma izpildes laiks noteiks takts frekvenci
Komandu skaits uz takts CPI=1 (ideālā gadījumā)
Uzlabojums = posmu skaits (ideālā gadījumā)
Diemžēl vairāki faktori neļauj sasniegt ideālus rezultātus:
– Nevar komandas izpildi sadalīt vienādi ilgos laika posmos
– Ir jāpatērē laiks lai aizpildītu un iztukšotu konveijeru
– Ir nepieciešami virstēriņi darbību sinhronizācijai, datu pārraidei….
– Konflikti (structural, data, control hazards)
7
7

8.

Konveijera īpašības
Pēc zināma laika (n-1 taktīm) visi n posmi strādā un konveijers ir
“pilns”.
Tad, teorētiski, konveijers var nodrošināt maksimālu paralēlismu
(n komandas izpildās vienlaicīgi).
Problēmas:
– Lielie virstēriņi uz datu pārvietošanu un sinhronizāciju:
aiztures laiks,
takts nobīdes (skew),
takts trīces (jitter);
– Pieaug arī CPU sarežģītība;
– Nav iespējams turēt konveijeru pilnu dēļ konveijeru konfliktiem
(hazards).
8
8

9.

Konveijera konflikti
Konveijera riski (konflikti) ir situācijas kad kādas problēmas neļauj izpildīt komandu tai
atvēlētajā taktī.
Šādu komandu sauc par aizkavētu (‘stalled’)
Kad kāda komanda tiek aizkavēta tad visas pārējās komandas (kas atrodas
konveijerā aiz aizkavētās komandas) arī tiek aizkavētas.
Komandas kas atrodas pirms aizkavētās komandas var tikt izpildītas.
Aizkaves gadījumā jaunas komandas konveijerā netiek ielādētas.
Konfliktu veidi:
– Strukturālie (Structural hazards) - Aparatūra nespēj izpildīt komandu secību ja piemēram
divas komandas vēlas izmantot vienu aparatūras resursu.
– Datu (Data hazards) - Komanda ir atkarīga no iepriekš esošas komandas rezultāta.
– Vadības (Control hazards) – Vadības komandas kuras maina komandu skaitītāja (PC)
saturu.
9
9

10.

Resursu konflikti
Struktūras konflikti rodas tad kad divas vai vairāk komandas pieprasa vienu un to pašu
resursu
Lai izvairītos:
– Dublē resursus
– Konveijerizē resursus
– Pārkārto komandas
Ir gadījumi kad šos konfliktus nevar novērst (tad ir jāaizkavē konveijers)
10
10

11.

Resursu konflikti
Struktūras konflikti rodas tad kad divas vai vairāk komandas pieprasa vienu un to pašu
resursu
Lai izvairītos:
– Dublē resursus
– Konveijerizē resursus
– Pārkārto komandas
Ir gadījumi kad šos konfliktus nevar novērst (tad ir jāaizkavē konveijers)
11
11

12.

Resursu konflikti
Fetch instruction
Decode instruction
Calculate operand(s)
Fetch operand(s)
Execute instruction
Write operand
FI
DI
CO
FO
EI
WO
(jebkāda atmiņa RAM)
(Moduļu ir daudz)
(Moduļu ir daudz)
(RAM, tie paši reģistri)
(ALU)
(RAM, tie paši reģistri)
12
12

13.

Resursu konflikti
jebkāds RAM ar jebkādu RAM
jebkāds RAM ar jebkādu RAM
vai konkrētie vienādi reģistri Rx un Rx,
ja reģistri ir dažādi, tad viss kārtībā (Rx un Ry)
atmiņa ar reģistru viss kārībā
DI ar CO ar EI vienmēr būs labi
FI ar FI:
FI ar FO ar WO:
13
13

14.

Resursu konflikti
FI ar FI:
RAM un RAM
FI ar FO ar WO:
RAM un RAM, Rx un Rx, Rx un Ry, RAM ar Rx
DI ar CO ar EI vienmēr būs labi
add r1,#2,[100]
[100]=r1+2
sub r2,#2,[200]
[200]=r2+2
add [100],[200],r3
r3=[100]+[200]
add r3,[100],r4
r4=r3+[100]
add r3,[200],r5
r5=r3+[200]
sub r4,r5,r6
r6=r4+r5
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
14
14

15.

Resursu konflikti
FI ar FI:
RAM un RAM
FI ar FO ar WO:
RAM un RAM, Rx un Rx, Rx un Ry, RAM ar Rx
DI ar CO ar EI vienmēr būs labi
add r1,#2,[100]
[100]=r1+2
sub r2,#2,[200]
[200]=r2+2
add [100],[200],r3
r3=[100]+[200]
add r3,[100],r4
r4=r3+[100]
add r3,[200],r5
r5=r3+[200]
sub r4,r5,r6
r6=r4+r5
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FO – operands: R1 and #2 (register and constant)
FI – memory
15
15

16.

Resursu konflikti
FI ar FI:
RAM un RAM
FI ar FO ar WO:
RAM un RAM, Rx un Rx, Rx un Ry, RAM ar Rx
DI ar CO ar EI vienmēr būs labi
add r1,#2,[100]
[100]=r1+2
sub r2,#2,[200]
[200]=r2+2
add [100],[200],r3
r3=[100]+[200]
add r3,[100],r4
r4=r3+[100]
add r3,[200],r5
r5=r3+[200]
sub r4,r5,r6
r6=r4+r5
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FO – operands: R2 and #2 (register and constant)
FI – memory
16
16

17.

Resursu konflikti
FI ar FI:
RAM un RAM
FI ar FO ar WO:
RAM un RAM, Rx un Rx, Rx un Ry, RAM ar Rx
DI ar CO ar EI vienmēr būs labi
add r1,#2,[100]
[100]=r1+2
sub r2,#2,[200]
[200]=r2+2
add [100],[200],r3
r3=[100]+[200]
add r3,[100],r4
r4=r3+[100]
add r3,[200],r5
r5=r3+[200]
sub r4,r5,r6
r6=r4+r5
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
WO – result: M[100] (memory)
FO – operands: M[100]and M[200] (memory)
FI – memory
W
17
17

18.

Resursu konflikti
FI ar FI:
RAM un RAM
FI ar FO ar WO:
RAM un RAM, Rx un Rx, Rx un Ry, RAM ar Rx
DI ar CO ar EI vienmēr būs labi
add r1,#2,[100]
[100]=r1+2
sub r2,#2,[200]
[200]=r2+2
add [100],[200],r3
r3=[100]+[200]
add r3,[100],r4
r4=r3+[100]
add r3,[200],r5
r5=r3+[200]
sub r4,r5,r6
r6=r4+r5
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
WO – result: R3 (register)
FO – operands: R3 and M[200] (register and memory)
18
18

19.

Resursu konflikti
FI ar FI:
RAM un RAM
FI ar FO ar WO:
RAM un RAM, Rx un Rx, Rx un Ry, RAM ar Rx
DI ar CO ar EI vienmēr būs labi
add r1,#2,[100]
[100]=r1+2
sub r2,#2,[200]
[200]=r2+2
add [100],[200],r3
r3=[100]+[200]
add r3,[100],r4
r4=r3+[100]
add r3,[200],r5
r5=r3+[200]
sub r4,r5,r6
r6=r4+r5
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
WO – result: R4 (register)
FO – operands: R4 and R5 (registers)
W
19
19

20.

Resursu konflikti
FI ar FI:
RAM un RAM
FI ar FO ar WO:
RAM un RAM, Rx un Rx, Rx un Ry, RAM ar Rx
DI ar CO ar EI vienmēr būs labi
add r1,#2,[100]
[100]=r1+2
sub r2,#2,[200]
[200]=r2+2
add [100],[200],r3
r3=[100]+[200]
add r3,[100],r4
r4=r3+[100]
add r3,[200],r5
r5=r3+[200]
sub r4,r5,r6
r6=r4+r5
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
W
FI
DI
CO
FO
EI
WO – result: M[100] (memory)
FO – operands: R1 and R2 (registers)
FI – memory
W
20
20

21.

Resursu konflikti
FI ar FI:
RAM un RAM
FI ar FO ar WO:
RAM un RAM, Rx un Rx, Rx un Ry, RAM ar Rx
DI ar CO ar EI vienmēr būs labi
add r1,#2,[100]
[100]=r1+2
sub r2,#2,[200]
[200]=r2+2
add [100],[200],r3
r3=[101]+[200]
add r3,[100],r4
r4=r3+[100]
add r3,[200],r5
r5=r3+[200]
sub r4,r5,r6
r6=r4+r5
FI
DI
CO
FO
EI
WO
FI
DI
CO
FO
EI
FI
DI
CO
FO
FI
DI
X
FI
X
X
21
21

22.

Datu konflikti
Read After Write (RAW)
Komanda “J” cenšas nolasīt operandu pirms Komanda “I” to pieraksta
To izraisa atkarība (”dependance”) ko izveido programmētājs (vai kompilators) un kura
pieprasa šo datu nodošanu no vienas komandas otrai
22
22

23.

Datu konflikti
Write After Read (WAR)
Komanda “J” pieraksta operandu pirms Komanda “I” to nolasa
Sauc arī par “anti-dependence” un to izraisa reģistra “r1” atkārtota izmantošana
Vienkāršā konveijerā neiespējams gadījums jo:
– Visas komandas izpildās vienādā taktu skaitā
– Nolasa vienmēr 3. taktī bet pieraksta vienmēr 6. taktī
WAR konflikti rodas ja komandas tiek izpildītas ārpus secības vai tās piekļūst datiem vēlāk
nekā parasti
23
23

24.

Datu konflikti
Write After Write (WAW)
Komanda “J” pieraksta operandu pirms Komanda “I” pieraksta to pašu operandu
Tiek saukta arī par “output dependence” un to arī izraisa vārda “r1” atkārtota izmantošana
Vienkāršā konveijerā neiespējami jo:
– Visas komandas izpildās vienādā taktu skaitā
– Pieraksta vienmēr 6. taktī
WAR un WAW ir iespējami sarežģīti organizētos konveijeros.
24
24

25.

Datu konfliktu novēršana
Piemēram izveidojiet pēc iespējas ātrāku dotā koda izpildi:
– a=b+c
– d=e–f
Pieņemot to ka a, b, c, d ,e, un f atrodas atmiņā
25
25

26.

Read After Write (RAW) piemērs
26
26

27.

Paralelizācijas ierobežojums
Dažos pielietojumos aparatūras dublēšana rada proporcionālo skaitļošanas uzlabojumu
27
27

28.

Amdala likums (Amdahl’s Law)
28
28

29.

Amdala likuma piemērs
Video spēle izmanto CPU un GPU, lai izrēķināt katru kadru
Pie kadru frekvences 10 fps, katrs kadrs aizņem 100 ms
Pieņemsim ka 60% laika aizņem GPU un 40% CPU
Jūs gribiet uzlabot sistēmu, bet iztērēt naudu visefektīvāk.
Ir sekojošie variant:
a)
b)
Jauns GPU ir četras reizes ātrāks un maksā 1500 EUR;
Jauns CPU ir trīs reizēs ātrāks un maksā 700 EUR.
Kurš variants ir izdevīgāks?
100 ms is 100%
60 ms is 60% - GPU
40 ms is 40% - CPU
29
29

30.

Amdala likuma piemērs
100 ms is 100%
60 ms is 60% - GPU
40 ms is 40% - CPU
Opcija “a” ar GPU
60 ms samazinās līdz 15 ms
Kopējais laiks = 15 + 40 = 55 ms
Paātrinājums 100/55 = 1.8181 reizēs
Par 81,8% samaksāsiet 1500 EUR, kas rezultējas ~33 EUR/%
Opcija “b” ar CPU
40 ms samazinās līdz 13,3 ms
Kopējais laiks = 13,3 + 60 = 73,3 ms
Paātrinājums 100/73,3 = 1.364 reizēs
Par 36,4% samaksāsiet 700 EUR, kas rezultējas ~26 EUR/%
30
30

31.

Amdahl’s Law example
Option “a”
1
1