Ievads datoru arhitektūrā. 5 lekcija

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
Vairāki 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) 1985
16 MIPS
Cray (superdators)
1975
160 MIPS
iPhone 5S
2013
18 200 MIPS
…
‘Meaningless Indicator of Processor Speed’
3

4.

Komandas izpilde
V13
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
Vadības
mezgls
V01
Karodziņu
reģistrs
V05
V06
V02
Steka
rādītājs
V07
V08
V03
Komandu
skaitītājs
V09
V10
Komandu
reģistrs
V11
V04
Kods
Adrese
Dešifrators
V14
(lasīt)
Atmiņa
V15
(rakstīt)
V12
Datu reģistrs
V16
V17
Kopne
V22
V18
Reģistrs 1
V20
ALM
V19
Reģistrs 2
Reģistrs N
V23
V21
4

5.

Secīgā komandas izpilde
Secīgā jaunas komandas izpilde sākas pēc iepriekšēja rezultāta
pieraksta.
n komandu izpildes laiks t ir:
t=6*n
1.Fetch instruction
2.Decode instruction
3.Calculate operand(s)
4.Fetch operand(s)
5.Execute instruction
6.Write operand
FI
DI
CO
FO
EI
WO
5

6.

Konveijerizācija
Konveijers ļauj paātrināt programmas izpildi, apstrādājot
vairākas darbības vienlaicīgi.
n komandu izpildes laiks t ir:
t = 6 + (n – 1)
1.Fetch instruction
2.Decode instruction
3.Calculate operand(s)
4.Fetch operand(s)
5.Execute instruction
6.Write operand
FI
DI
CO
FO
EI
WO
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 … WR)
• Ilgākais posma izpildes laiks noteiks komandas izpildes ātrumu
• 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

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 (ierobežo gaismas ātrums),
• 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

9.

Konveijera konflikti
• Konveijera konfliktsi kad nav iespējams izpildīt komandu tai atvēlētajā taktī.
• Šādu komandu sauc par aizkavētu (‘stalled’).
• Kad 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:
– Resursu / Strukturālie (‘Structural hazards’) – Kad divas komandas vēlas izmantot vienu
aparatūras resursu (peim. atmiņu).
– 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 saturu.
9

10.

Resursu konflikti
• Struktūras/resursu konflikti rodas kad divas vai vairāk komandas pieprasa vienu un to pašu
resursu.
• Lai izvairītos:
– Dublē resursus;
– Pārkārto komandas.
• Kad šos konfliktus nevar novērst, tad ir jāaizkavē konveijers.
*r1, r2, … – CPU reģistri
[100], … – atmiņa
10
Mēģināja nolasīt komandu no atmiņas, kāmēr lasa operandu

11.

Resursu konflikti
• Struktūras/resursu konflikti rodas kad divas vai vairāk komandas pieprasa vienu un to pašu
resursu.
• Lai izvairītos:
– Dublē resursus;
– Pārkārto komandas.
• Kad šos konfliktus nevar novērst, tad ir jāaizkavē konveijers.
*r1, r2, … – CPU reģistri
[100], … – atmiņa
11
Var nolasīt komandu no atmiņas, jo operandi ir reģistros

12.

Resursu konflikti
V13
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 vai vienādi reģistri)
(ALU)
(RAM vai vienādi reģistri)
Vadības
mezgls
V01
Karodziņu
reģistrs
V05
V06
V02
Steka
rādītājs
V07
V08
V03
Komandu
skaitītājs
V09
V10
Komandu
reģistrs
V11
V04
Kods
Adrese
Dešifrators
V14
(lasīt)
Atmiņa
V15
(rakstīt)
V12
Datu reģistrs
V16
V17
Kopne
V22
V18
Reģistrs 1
V20
ALM
V19
Reģistrs 2
V21
V23
12

13.

Resursu konflikti
FI ar FI:
vienmēr, jo komandas glabājas atmiņā
V13
FI ar FO ar WO:
jebkāds RAM ar jebkādu RAM
vai konkrētie vienādi reģistri
R1 un R1
ja reģistri ir dažādi, tad
viss kārtībā (Rx un Ry)
atmiņa ar reģistru viss
kārībā
Vadības
mezgls
V01
Karodziņu
reģistrs
V05
V06
V02
Steka
rādītājs
V07
V08
V03
Komandu
skaitītājs
V09
V10
Komandu
reģistrs
V11
V04
Kods
Adrese
Dešifrators
V14
(lasīt)
Atmiņa
V15
(rakstīt)
V12
Datu reģistrs
V16
V17
Kopne
DI ar CO ar EI:
nekad nav konfliktu
V22
V18
Reģistrs 1
V20
ALM
V19
Reģistrs 2
V21
V23
13

14.

Resursu konflikti
FI ar FI:
FI ar FO ar WO:
DI ar CO ar EI:
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
RAM un RAM
RAM un RAM, Rx un Rx, Rx un Ry, RAM ar Rx
nekad nav konfliktu
FI
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
FI
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
FI
DI
FI
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
FI
DI
CO
FI
DI
FI
FO – operands: R1 and #2 (register and constant)
FI – memory
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
FI
DI
CO
FO
FI
DI
CO
FI
DI
FI
FO – operands: R2 and #2 (register and constant)
FI – 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
FI
DI
CO
FO
FI
DI
CO
FI
DI
FI
WO – result: M[100] (memory)
FO – operands: M[100]and M[200] (memory)
FI – memory
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
FI
DI
CO
FO
FI
DI
X
FI
X
X
WO – result: M[100] (memory)
FO – operands: M[100]and M[200] (memory)
FI – memory
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=[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
FI
DI
CO
FO
FI
DI
CO
FI
DI
WO – result: R3 (register)
FO – operands: R3 and M[200] (register and memory)
*pieņemsim ka konflikts iepriekš neaizkavēja konveijeru
21
21

22.

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
FI
DI
CO
FO
FI
DI
X
FI
X
WO – result: R3 (register)
FO – operands: R3 and M[200] (register and memory)
*pieņemsim ka konflikts iepriekš neaizkavēja konveijeru
22
22

23.

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
FI
DI
CO
FO
FI
DI
CO
WO – result: R3 (register)
FO – operands: R3 and M[200] (register and memory)
*pieņemsim ka konflikts iepriekš neaizkavēja konveijeru
23
23

24.

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
FI
DI
CO
FO
FI
DI
CO
WO – result: R3 (register)
FO – operands: R3 and M[200] (register and memory)
*pieņemsim ka konflikts iepriekš neaizkavēja konveijeru
24
24

25.

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
FI
DI
CO
FO
WO – result: R4 (register)
FO – operands: R4 and R5 (registers)
*pieņemsim ka konflikts iepriekš neaizkavēja konveijeru
25
25

26.

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
FI
DI
CO
FO
WO – result: R4 (register)
FO – operands: R4 and R5 (registers)
*pieņemsim ka konflikts iepriekš neaizkavēja konveijeru
26
26

27.

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
*pieņemsim ka konflikts iepriekš neaizkavēja konveijeru
27
27

28.

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
*pieņemsim ka konflikts iepriekš neaizkavēja konveijeru
W
28
28

29.

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=r1+r2
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
29
29

30.

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

31.

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

32.

Datu konflikti
2+3
add #3,#2,R1
r1 = 3+2
sub r4,r1,r3
r3 = r1+r4
FI
=5
DI
CO
FO
EI
W
FI
DI
CO
FO
X
32
32

33.

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

34.

Datu konflikti
Write After Write (WAW)
Komanda “J” parraksta 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.
34
34

35.

Read After Write (RAW) piemērs
35

36.

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ņā
Var izpildīt citu komandu, kāmēr izpildas ADD
36
36

37.

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

38.

Amdala likums (Amdahl’s Law)
38

39.

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

40.

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/%
40
40

41.

Amdahl’s Law example
Option “a”
1
1