Les 1: van scalaire naar superscalaire

Les 1: van scalaire naar
superscalaire microarchitectuur
Geavanceerde computerarchitectuur
Lieven Eeckhout
Academiejaar 2008-2009
Universiteit Gent
Overzicht
• Pijplijn
• Hazards
– M.b.t. data-afhankelijkheden
– M.b.t. controle-afhankelijkheden
• Beperkingen van scalaire pijplijn
– Gediversifieerde pijplijn
– Uitbreiding naar superscalaire pijplijn
– Out-of-order uitvoering
2
Pijplijn
• Motivatie: verhogen van prestatie
• Prestatie = # uitgevoerde instructies per
tijdseenheid
• Bijkomende hardware is beperkt
• Principe is analoog aan de transportband
in een fabriek
• Merk op: (bijna) alle hedendaagse
microprocessors zijn gepijplijnd
3
flip- flop
Pijplijn: idee
latentie Tg
flip- flop
flip- flop
prestatie ≈ 1/Tg
latentie Tg/2
latentie Tg/2
latentie Tg/3
flip- flop
latentie Tg/3
flip- flop
flip- flop
prestatie ≈ 2/Tg
latentie Tg/3
prestatie ≈ 3/Tg
4
Prestatiewinst
• Potentiële prestatiewinst is factor k met k het
aantal pijplijntrappen
• Maar... er is een toenemende kost
– Aantal flipflops stijgt met factor k
• En... overhead tgv. inklokken data in flipflops
–
–
–
–
Latentie Tl tgv. flipflops: hold and setup time
Niet-gepijplijnde architectuur: klokcyclus T = Tg+Tl
Gepijplijnde architectuur: T = Tg/k + Tl
(prestatie = 1/T wegens 1 nieuwe instructie per
klokcyclus in de pijplijn)
– Belang van inklokken stijgt dus met een toenemend
aantal pijplijntrappen
5
Optimale pijplijndiepte
• Maw. het is zinloos het aantal
pijplijntrappen oneindig te laten toenemen
• Er bestaat dus een optimale pijplijndiepte
(zie oefeningen)
• Tot nu toe: enkel hardware beschouwd en
‘perfect’ pijplijngedrag verondersteld
• (‘perfect’ pijplijngedrag = iedere cyclus kan
een nieuwe operatie gestart worden)
6
‘Perfect’ pijplijngedrag
• Is het geval indien er geen
afhankelijkheden zijn tussen
opeenvolgende operaties in de pijplijn
• Is niet het geval in instructiepijplijnen
– Reden: er zijn afhankelijkheden tussen
opeenvolgende operaties in de pijplijn
– Het niet-respecteren van afhankelijkheden
wordt een hazard genoemd
7
Instructiepijplijn
IF
ID
OF
EX
MEM
WB
Instruction Fetch: instructie ophalen
Instruction Decode: instructie decoderen
Operand Fetch: registers lezen
Execute: instructie uitvoeren
Memory Read/Write: geheugen lezen/schrijven
Write Back: resultaten wegschrijven in registerbestand
8
Overzicht
• Pijplijnen
• Hazards
– M.b.t. data-afhankelijkheden
– M.b.t. controle-afhankelijkheden
• Beperkingen van scalaire pijplijn
– Gediversifieerde pijplijn
– Uitbreiding naar superscalaire pijplijn
– Out-of-order uitvoering
9
Hazards
• Hazard treedt op als gevolg van niet respecteren
van een programma-afhankelijkheid
• Hazard mag dus niet optreden!
• Programma-afhankelijkheden
– Data-afhankelijkheid via geheugen
– Data-afhankelijkheid via registers
– Controle-afhankelijkheid
• Hoe hazards vermijden in scalaire pijplijn?
– Volgende slides
10
Data-afhankelijkheden
• Echte afhankelijkheid = read-after-write
(RAW)
V3 ← V1 op V2
V4 ← V3 op V5
• Anti afhankelijkheid = write-after-read
V3 ← V1 op V2
(WAR)
V1 ← V4 op V5
• Output afhankelijkheid = write-after-write
(WAW)
V3 ← V1 op V2
V3 ← V4 op V5
11
Hazard op data-afhankelijkheid
• RAW hazard
V3 ← V1 op V2
V4 ← V3 op V5
V4 ← V3 op V5
V3 ← V1 op V2
• WAR hazard
V3 ← V1 op V2
V1 ← V4 op V5
V1 ← V4 op V5
V3 ← V1 op V2
• WAW hazard
V3 ← V1 op V2
V3 ← V4 op V5
V3 ← V4 op V5
V3 ← V1 op V2
12
Hazards via geheugen?
• Enkel MEM trap leest/schrijft in geheugen
• Alle toegangen tot geheugen gebeuren
sequentieel en in programmavolgorde
• Maw. hazards kunnen niet optreden tgv.
afhankelijkheden via het geheugen
13
Hazards via registers?
• WAW hazard?
– Neen, enkel WB trap schijft en doet dit sequentieel en
in programmavolgorde
• WAR hazard?
– Neen, lezen gebeurt in OF trap, schrijven gebeurt in
WB trap; schrijven komt dus altijd na lezen
• RAW hazard?
– Ja, indien instructie een ‘oude’ waarde leest uit
registerbestand
14
RAW hazard via registers
IF
cyclus x
cyclus x+1
t
ID
R4 ← R3 op R5
OF
R3 ← R1 op R2
EX
R4 ← R3 op R5
R3 ← R1 op R2
MEM
WB
15
Blokkering van de pijplijn
IF
x
x+1
x+2
x+3
x+4
t
ID
←R3
OF
R3←
EX
←R3
←R3
←R3
←R3
R3←
penalty = 3 cycli
MEM
WB
R3←
R3←
16
Oplossing: Forwarding
x
IF
pipeline
interlock
hardware
x+1
x+2
t
←R3
ID
←R3
←R3
OF
←R3
←R3
←R3
EX
R3←
←R3
←R3
a
MEM
x+3
via a
R3←
via b
forwarding pad c
kan ev. via het
registerbestand
geïmplementeerd
worden
←R3
via c
←R3
←R3
R3←
←R3
b
WB
c
data-afhankelijke instructies
worden in opeenvolgende
cycli uitgevoerd
17
Overzicht
• Pijplijn
• Hazards
– M.b.t. data-afhankelijkheden
– M.b.t. controle-afhankelijkheden
• Beperkingen van scalaire pijplijn
– Gediversifieerde pijplijn
– Uitbreiding naar superscalaire pijplijn
– Out-of-order uitvoering
18
Controle hazard?
x
IF
ID
OF
EX
MEM
WB
x+1
x+2
x+3
x+4
br
x+5
inst
t
br
penalty = 4 cycli
br
br
br
19
Controle hazards vermijden
• Delayed branches
– instructies volgend op de sprong in de
programmacode worden uitgevoerd ongeacht de
sprongrichting
– door compiler in te vullen
– was populair bij vroege RISC machines
– vrij complex in hedendaagse processors
– (achteraf gezien: slechte ontwerpkeuze)
• Beter is (zeker voor hedendaagse processors)
instructies op te halen en de uitvoering ervan
(speculatief) te starten langs het voorspelde pad
20
Veronderstel niet-genomen (1)
IF
x
x+1
x+2
x+3
x+4
x+5
br
inst
inst
inst
inst
inst
br
inst
inst
inst
inst
br
inst
inst
inst
br
inst
inst
br
inst
ID
OF
EX
t
br
MEM
not-taken
inst
WB
taken
inst
indien correct voorspeld
is penalty = 0 cycli
21
Veronderstel niet-genomen (2)
IF
x
x+1
x+2
x+3
x+4
x+5
br
inst
inst
inst
inst
inst
br
inst
inst
inst
br
inst
inst
br
inst
ID
OF
EX
t
br
MEM
not-taken
inst
WB
taken
inst
br
indien incorrect voorspeld
is penalty = 4 cycli
22
Invloed pijplijndiepte
• Vroege pijplijnen hadden 4 tot 6 trappen
• Hedendaagse pijplijnen hebben typisch
meer pijplijntrappen
– b.v. Intel Pentium 4 heeft 20 trappen
(sommige varianten hebben tot 31 trappen)
• Reden: hogere klokfrequenties f
• Impact op penalties?
• Netto prestatiewinst? (cfr. P = IPC x f)
23
Optimale pijplijndiepte
• k pijplijntrappen geeft een potentiële winst van
een factor k
• Maar...
– Er zijn technologische beperkingen
• Toenemende kost
• Inklokken in flipflops
• Vermogenverbruik (zie later)
– En niet-ideaal pijplijngedrag
• Invloed foutief voorspeld sprongen stijgt met diepere pijplijn
• Wordt vervolgd...
24
Overzicht
• Pijplijn
• Hazards
– M.b.t. data-afhankelijkheden
– M.b.t. controle-afhankelijkheden
• Beperkingen van scalaire pijplijn
– Gediversifieerde pijplijn
– Uitbreiding naar superscalaire pijplijn
– Out-of-order uitvoering
25
Beperking scalaire pijplijn
• Verschillende instructietypes unificeren is
een probleem
– b.v. floating-point vermenigvuldiging vs. een
integer optelling
• Maximale IPC = 1
– Het is onmogelijk meer dan 1 instructie uit te
voeren per klokcyclus
• In-order uitvoering
– Stalls tgv. in-order uitvoering
26
Probleem 1: unificatie
IF
ID
OF
EX
EX voert zowel integer
optelling als floating-point
vermenigvuldiging uit in 1 klokcyclus...
Oplossing: diversificatie
MEM
WB
27
Gediversifieerde pijplijn
IF
ID
OF
INT
MEM (1)
FP (1)
MEM (2)
FP (2)
MEM (3)
FP (3)
BR
FP (4)
FP (5)
FP (6)
WB
hogere klokfrequentie
dan geunificeerde pijplijn
28
Drie problemen
• Out-of-order completion
– Wegschrijven resultaten gebeurt mogelijks
niet in programmavolgorde (= WAW hazard)
• Mogelijks meerdere schrijfacties naar
registerbestand in WB trap per klokcyclus
(= structurele hazard)
• Excepties
29
Out-of-order completion
t
R4←ld[MEM]
R3←R1+R2
IF
ID
OF
MEM1 MEM2 MEM3 WB
IF
ID
OF
EX
WB
... is in principe geen probleem (behoudens excepties—zie later)
30
maar ...
t
R4←ld[MEM]
IF
R4←R1+R2
ID
OF
MEM1 MEM2 MEM3 WB
IF
ID
OF
EX
WB
... dit is een WAW hazard; de oplossing is...
t
R4←ld[MEM]
R4←R1+R2
IF
ID
OF
MEM1 MEM2 MEM3 WB
IF
ID
OF
xx
xx
EX
WB
... een blokkering (stall)
31
Meerdere WBs per cyclus
t
R4←ld[MEM]
R3←R1+R2
R5←R3+R2
IF
ID
OF
MEM1 MEM2 MEM3 WB
IF
ID
OF
EX
WB
IF
ID
OF
EX
WB
• Onmogelijk wegens slechts 1 schrijfpoort naar
registerbestand
• Oplossing:
– Schrijfpoort toevoegen of
– Schrijfpoort beschouwen als structurele hazard (maw.
een extra blokkering)
R5←R3+R2
IF
ID
OF
xx
EX
WB
32
Interrupts vs. excepties
• Interrupts
– Typisch door externe factoren
– Asynchroon tov. programma in uitvoering
– Afhandelen:
•
•
•
•
•
Stop ophalen nieuwe instructies
Voer instructies in pijplijn uit
Bewaar architecturale toestand
Handel interrupt af
Herstel architecturale toestand en voer programma
verder uit
33
Interrupts vs. excepties
• Excepties/faults
– Door instructies van programma in uitvoering
– B.v. deling door nul, paginafout, overflow, etc.
– Precise exception
• Architecturale toestand net vóór instructie opslaan
• Exceptie afhandelen
• Uitvoering hervatten vanaf instructie die exceptie
veroorzaakt heeft
– Wat in geval van out-of-order completion?
34
Excepties en OoO completion
• Door OoO completion kunnen precieze
excepties niet gegarandeerd worden
– Imprecise exceptions
– [Bedenk hier zelf een voorbeeld]
35
Overzicht
• Pijplijn
• Hazards
– M.b.t. data-afhankelijkheden
– M.b.t. controle-afhankelijkheden
• Beperkingen van scalaire pijplijn
– Gediversifieerde pijplijn
– Uitbreiding naar superscalaire pijplijn
– Out-of-order uitvoering
36
Beperking scalaire pijplijn
• Verschillende instructietypes unificeren is
een probleem
– b.v. floating-point vermenigvuldiging vs. een
integer optelling
• Maximale IPC = 1
– Het is onmogelijk meer dan 1 instructie uit te
voeren per klokcyclus
• In-order uitvoering
– Stalls tgv. in-order uitvoering
37
Superscalaire pijplijn
IF
ID
OF
INT
crossbar
MEM (1)
FP (1)
MEM (2)
FP (2)
MEM (3)
FP (3)
BR
FP (4)
FP (5)
FP (6)
WB
38
Superscalaire pijplijn
• Parallellisme in tijd
– Pijplijn
– Relatief goedkoop
• Parallellisme in ruimte
– Superscalair
– Relatief duur (meer hardware)
• Superscalaire pijplijn
– Parallellisme in tijd én in ruimte
• Potentiële prestatiewinst = k x b met k =
#pijplijntrappen en b = breedte van pijplijn
39
Extra hardwarekost
• Meer registerpoorten
– 2 x b leespoorten
– b schrijfpoorten
– kan ook minder (ten koste van blokkeringen)
• Meer bandbreedte naar I- en D-cache
• Interconnectiestructuur
– Verdelen instructies over verschillende FUs
– Complexiteit b2
• Detectie van hazards wordt complexer
40
Voorkomen hazards
• Gebeurt typisch alvorens instructie naar
FU gaat voor uitvoering
• Maw. at issue time
• Dus eenmaal in FU, wordt instructie niet
meer opgehouden (geen blokkeringen
meer voor die instructie)
41
Superscalaire uitvoering
t
R4←ld[MEM]
IF
ID
OF
MEM1 MEM2 MEM3 WB
R3←R1+R2
IF
ID
OF
EX
WB
R5←R3+R2
IF
ID
OF
xx
EX
WB
R6←R1+R2
IF
ID
OF
xx
EX
WB
R3←R1+R6
IF
ID
OF
xx
xx
EX
WB
R5←R2+R6
IF
ID
OF
xx
xx
EX
WB
Uitvoering van de eerste en tweede instructie start in dezelfde cyclus
wegens onafhankelijk van elkaar. Blokkering voor derde instructie wegens RAW
afhankelijkheid met tweede instructie; blokkering gebeurt in OF trap.
42
Overzicht
• Pijplijn
• Hazards
– M.b.t. data-afhankelijkheden
– M.b.t. controle-afhankelijkheden
• Beperkingen van scalaire pijplijn
– Gediversifieerde pijplijn
– Uitbreiding naar superscalaire pijplijn
– Out-of-order uitvoering
43
Beperking scalaire pijplijn
• Verschillende instructietypes unificeren is
een probleem
– b.v. floating-point vermenigvuldiging vs. een
integer optelling
• Maximale IPC = 1
– Het is onmogelijk meer dan 1 instructie uit te
voeren per klokcyclus
• In-order uitvoering
– Blokkeringen tgv. in-order uitvoering
44
In-order issue
t
R4←ld[MEM]
IF
ID
OF
MEM1 MEM2 MEM3 WB
R3←R1+R2
IF
ID
OF
EX
WB
R5←R3+R2
IF
ID
OF
xx
EX
WB
R6←R1+R2
IF
ID
OF
xx
EX
WB
R3←R1+R6
IF
ID
OF
xx
xx
EX
WB
R5←R2+R6
IF
ID
OF
xx
xx
EX
WB
Instructies 4 tem. 6 blokkeren in ID trap omdat 3de instructie blokkeert in ID trap
ofschoon zij in principe een cyclus vroeger uitgevoerd kunnen worden.
Dit is een fundamentele beperking van in-order issue.
45
In-order issue: blokkering
t
R4←ld[MEM]
R3←ld[R1]
IF
ID
OF
MEM1 MEM2 MEM3 WB
cache
IF
ID
miss
OF
MEM1 MEM2 MEM3 xx
xx
WB
R5←R3+R2
IF
ID
OF
xx
xx
xx
xx
xx
EX
WB
R6←R1+R2
IF
ID
OF
xx
xx
xx
xx
xx
EX
WB
R3←R1+R6
IF
ID
OF
xx
xx
xx
xx
xx
xx
EX
R5←R2+R6
IF
ID
OF
xx
xx
xx
xx
xx
xx
EX
De kost stijgt heel sterk als functie van de uitvoeringslatentie van de instructies,
zoals b.v. vermenigvuldigingen (typisch 4 cycli) of cache misses (typisch
10 tot 15 cycli voor L1 misses, tot honderden cycli voor L2 misses).
M.a.w. de kost neemt toe bij slechter cachegedrag (meer cache misses).
46
In-order issue: WAW
t
R4←ld[MEM]
IF
R3←R1+R2
ID
OF
MEM1 MEM2 MEM3 WB
IF
ID
OF
EX
WB
IF
ID
OF
xx
R4←R3+R2
EX
t
cache
R4←ld[MEM]missIF
ID
OF
MEM1 MEM2 MEM3 xx
R3←R1+R2
IF
ID
OF
EX
WB
IF
ID
OF
xx
R4←R3+R2
WB
xx
xx
xx
WB
xx
xx
EX
WB
(Stel er is maar één schrijfpoort naar het registerbestand.)
De kost stijgt heel sterk als functie van de uitvoeringslatentie van de instructies.
47
Fundamentele beperkingen
• Een instructie die blokkeert verhindert de
uitvoering van alle daarop volgende instructies
– Ook de instructies die onafhankelijk zijn van
geblokkeerde instructie blokkeren!!!
– Is vooral een probleem voor instructies met lange
uitvoeringslatenties
• WAW afhankelijkheden beperken ook het
parallellisme ofschoon dit geen echte dataafhankelijkheid is
• (Waarom zijn WAR afhankelijkheden geen
beperking?)
48
Out-of-order uitvoering
• Idee:
– Echte (RAW) afhankelijkheden bepalen uitvoering
– Valse (WAR en WAW) afhankelijkheden veroorzaken geen
blokkeringen
• Tenzij het aantal fysieke registers beperkt is, zie later
– Maw. we bereiken de data flow limiet = instructies worden
uitgevoerd als operandi beschikbaar zijn, d.i. zo vroeg mogelijk
• Out-of-order uitvoering = dynamische pijplijn
49
Data flow limiet
Enkel RAW afhankelijkheden!
R4←ld[MEM]
R3←R1+R2
R4←ld[MEM]
R3←R1+R2
R5←R3+R4
R6←R1+R5
R5←R3+R4
R3←R1+R4
R3←R1+R4
R5←R4+R5
R6←R1+R5
R5←R4+R5
Dataverloopgraaf bepaalt de
out-of-order uitvoering
50
Superscalaire OoO pijplijn
fetch
reorder buffer
in-order
decode
dispatch
INT
out-of-order
MEM (1)
FP (1)
MEM (2)
FP (2)
MEM (3)
FP (3)
FP (4)
BR
issue buffer
issue
execute
finish
store
queue
in-order
complete
retire
store buffer
51
Twee nieuwe structuren
• Issue buffer = reservatiestation
– Instructies worden ingevoegd in issue buffer (en
reorder buffer) in programmavolgorde
– Instructies uitgevoerd op FUs en verlaten issue buffer
mogelijks niet in programmavolgorde
• Reorder buffer = completion buffer
– Out-of-order finish wegens out-of-order issue en nietuniforme uitvoeringslatenties
– In-order retirement = wegschrijven resultaten in
architecturale registers
– Precieze excepties mogelijk maken
• Store queue en store buffer (zie later)
52
“Sequentiality is an illusion”
• Het beeld van de programmeur/compiler is dat
instructies uitgevoerd worden in programmavolgorde,
sequentieel dus
• In hardware gebeurt heel wat in parallel
– In de tijd via de pijplijn
– In de ruimte via uitbuiten ILP
• In out-of-order processor is dit zelfs door instructies niet in
programmavolgorde uit te voeren
• In-order retirement garandeert het sequentiële beeld van
uitvoering
• Parallellisme op instructie-niveau = instruction-level
parallelism (ILP)
53
Samenvatting
• Hoe prestatie verbeteren?
– Pijplijn: parallellisme in de tijd
– Superscalariteit: parallellisme in de ruimte
• Optimale pijplijndiepte
– Beperkingen om steeds dieper te pijplijnen
• Technologische aspecten, data- en controleafhankelijkheden in computerprogramma
• Superscalaire processor
– Meer dan één operatie per cyclus uitvoeren
– In-order versus out-of-order
54
Drie belangrijke “stromen”
• Instructiestroom
– Front-end van pijplijn
– Zoveel mogelijk instructies per klokcyclus in pijplijn
sturen
– Les 2
• Datastroom via registers
– Afhankelijkheden tussen instructies detecteren
– OoO uitvoering van instructies
– Les 3
• Datastroom via geheugen
– Uitvoering van geheugenoperaties
– Les 4
55
Oefeningen (1)
• Bereken optimale pijplijndiepte voor ‘perfect’
pijplijngedrag met
–
–
–
–
–
G kost voor combinatorisch circuit (gates)
L kost voor flipflops (latches)
Tg latentie van combinatorisch circuit
Tl latentie van flipflops
En kostfunctie = kost / prestatie
• Via forwarding paden kunnen we RAW hazards
voorkomen. Indien het schrijven gebeurt door
een niet-geheugen operatie elimineren we de
penalty volledig. Wat indien het schrijven
gebeurt door een load instructie? Kan die
penalty vermeden worden?
56
Oefeningen (2)
• Hoe veranderen de penalties wanneer het aantal
pijplijntrappen toeneemt? Bekijk RAW vanuit een
niet-geheugen instructie, RAW vanuit geheugen
instructie en sprongpenalties. Veronderstel dat
in de diepe pijplijn:
–
–
–
–
–
–
IF uit 3 trappen bestaat
ID uit 4 trappen
OF uit 2 trappen
EX uit 2 trappen
MEM uit 3 trappen
WB uit 2 trappen
57
Oefeningen (3)
• Hoeveel extra forwardingpaden zijn er in
een gediversifieerde pijplijn?
58

Download Report