Hoofdstuk 4: the processor

Question 1

ALU control (including ALU control bits)

Answer 1

De ALU is een Arithmetic Logical Unit. Het wordt gebruikt voor verschillende bewerkingen zoals add, substract, less then, OR, AND en NOR. Hiervoor bestaat er een implementatie schema voor de ALU om te bepalen welke bewerking hij moet doen. Voor elke soort instructie zal er een andere bewerking moeten gebeuren.

We kunnen de 4-bit ALU control input genereren door gebruik te maken van een kleine control unit met als inputs funct7 en funct3 velden van de instructies en een 2-bit controle veld, namelijk de ALUOp (zie def ALUOp).  De output van een ALU control unit is dus een 4-bit signaal dat afhangt van de ALUop control bits en de verschillende opcodes voor de R-type instructies. 
De ALUOp (gegenereerd door de main control unit) is het 1ste niveau van decodering. In het 2de niveau wordt (optioneel - niet voor ld, st, beq) gebruik gemaakt van de func3 en func7 velden. 2 niveaus want main control unit is kritisch voor performantie -> kleiner is sneller.

0000 AND
0001 OR
0010 add
0110 substract

Question 2

Branch hazard

Answer 2

Een vorm van een control hazard, waarbij men moet wachten op het branch target adress voor men verder kan gaan.

Question 3

Figure 4.10

Answer 3

Het datapad voor S-, en R-type instructies. Zie foto en zie dat je nut van elk element kan uitleggen. (zie def. S-, en R-type instructions). Two multiplexors worden hier gebruikt.

Question 4

Branch history table

Answer 4

= Branch prediction buffer = klein geheugenelement dat geindexeerd wordt door een deel van het adres van een branch instructie en 1 bit bevat dat behoud of de vorige branch recent was genomen of niet. We weten niet zeker of deze assumptie de juiste is, want twee branches kunnen wijzen naar hetzelfde element van de tabel. Dit is niet erg want we beschouwen de assumptie gewoon als een hint.

Question 5

Branch prediction

Answer 5

Een methode om een branch hazard (control hazard) op te lossen door een bepaalde uitkomst aan te nemen en met die assumptie verder te gaan ipv. te wachten. Als de assumptie juist was, wordt de pipeline hierdoor niet vertraagd. Je hebt dus enkel een stall bij een misvoorspelling.

Indien de voorspelling fout was worden de reeds uitgevoerde instructies ongedaan gemaakt (meestal gebruikt men daarom een soort tijdelijke opslag) en geflusht door controle op 0 te zetten en dit door te laten sijpelen in de pipeline. Kan static en dynamisch. Er zijn verschillende soorten prediction. Bijvoorbeeld kijken naar wat de vorige keer werd gedaan of altijd voorspellen dat de branch niet genomen wordt. De kost van een foute prediction moet worden afgewogen tegen de kost van de voorspellingsmethode. De 2-bit predictor is een oplossing voor een tekortkoming van een 1-bit predictor. In een 2-bit predictor moet de voorspelling twee keer fout zijn voordat het wordt veranderd.

Question 6

Branch prediction buffer

Answer 6

= branch history table = Klein geïndexeerd geheugen in de lagere portie van het adres van de branch instructies en bevat 1 bit dat zegt of de vorige branch recent was genomen of niet. We weten niet zeker of deze assumptie de juiste is, want twee branches kunnen wijzen naar hetzelfde element van de tabel. Dit is niet erg want we beschouwen de assumptie gewoon als een hint.

Question 7

Branch taken

Answer 7

Indien de conditie van de branch geldig is bij een I-type instructie en de program counter het branch target adres wordt.

Als de branch untaken is, is de conditie vals en wordt de PC gewoon het adres van de instructie dat sequentieel volgt op de branch.

Question 8

Figure 4.13

Answer 8

De waarheidstabel voor de 4 ALU controle bits, met X = don’t-cares. Inputs: ALUOp (2 bits), funct7 veld (7 bits), funct3 veld (3 bits) → 4 controle bits als output.

Question 9

Branch target address

Answer 9

Dit wordt gebruikt in de beq instructie.
Het adres dat in de branch wordt gespecifieerd dat de nieuwe PC wordt als de branch taken is (dus als de condition true is). Dit adres is gelijk aan de som van het offset veld van de instructie en het adres van de branch.

Als de branch untaken is, is de conditie van de branch vals en wordt de PC gewoon het adres van de instructie dat sequentieel volgt op de branch.

Question 10

Branch target buffer

Answer 10

Een structuur dat de bestemming voor de PC of een instructie voor een branch bijhoudt via tags (duurder dan simpele prediction buffer).

Een branch predictor vertelt ons of een conditionele branch genomen is of niet, maar het moet ook nog steeds de branch target berekenen. Deze calculatie neemt 1 cyclus in beslag en dus taken branches hebben een 1 cyclus penalty. Een alternatief is dus dat we ook adressen bijhouden. De branch target buffer is dus de cache van target adressen.

Question 11

Bubble

Answer 11

= pipeline stall = pause om een (load-use) hazard op te lossen

Question 12

Bypassing

Answer 12

= forwarding = een methode om data hazards op te lossen door het missende data elements uit interne buffers te halen ipv. Te wachten tot deze in een register of het geheugen wordt gestoken . (gaat alleen indien destination stage later is de source stage) (lost niet echt load-use data hazards op = een load nog niet zichtbaar voor instructie dat hem nodig heeft)

Question 13

Figure 4.14

Answer 13

De 4 types voor de instructieklassen (elks 32 bit → 64 bit via Imm Gen).

• R-type = arithmetische operaties. Het heeft 3 register operanden, rs1, rs2 en rd. rs1 en rs2 zijn bronnen, rd is de destinatie. De ALU functie zit in the funct3 en funct7 velden.
• I-type = immediate en load. Het register rs1 is het basisregister dat opgeteld wordt aan het 12-bit immediate veld om het geheugenadres te vormen. Het veld rd is het destinatie register voor de geladen waarde.
• S-type = store. Het register rs1 is het basisregister dat opgeteld wordt aan het 12-bit immediate veld om het geheugenadres te vormen. Het immediate veld is opgesplitst in een 7-bit stuk en een 5-bit stuk. Het feld rs2 is het bronregister waarvan de waarde in het geheugen moeten worden opgeslagen.
• SB-type = conditional branch. De registers rs1 en rs2 worden met elkaar vergeleken. He 2-bit immediate adres wordt sighn-extended, wordt naar links geschift met 1 bit en wordt toegevoegd aan de PC om het branch target adres te vormen.

Question 14

Check yourself p. 250

Answer 14

1) Voor een load instructie zorgt de MemtoReg ervoor dat de data van het geheugen naar de register file wordt gestuurd.
2) In een single-cycle datapath hebben we een apart geheugen voor instructies en data, omdat de processor per cyclus werkt en geen 2 opvragingen kan doen in 1 geheugen in 1 cyclus.

Question 15

Combinational element +

Answer 15

Er zijn 2 soorten logische elementen in een datapad( combinational en sequential element). Een combinational element is een element dat opereert op data (zoals en AND gate of een ALU). De output is enkel afhankelijk van de input (geen intern geheugen) Het geeft dus altijd hetzelfde resultaat bij dezelfde input.

Question 16

Pipelining

Answer 16

Mooi voorbeeld van parallelisme: een implementatie techniek waarbij verschillende instructies overlappen tijdens uitvoering. Pipelining verbetert de performantie door de instructie throughput te vergroten ipv. de lengte van een instructie te verkorten.

De processor wordt hierbij in verschillende stages verdeeld (vb. IF, ID, EXE, MEM, WB). Een RISC-V instructie heeft meestal 5 stappen:

1. intrusction fetch IF
2. instruction decode / register lezen ID
3. execution / adres berekenen EX
4. memory access MEM
5. resultaat in register schrijven WB

The RISC-V pipeline heeft dus 5 stages. De klok cyclus is gelijk aan de duur van de traagste operatie. (bij single cycle implementantion bepaalt langste instructie klok cyclus).

In ideale omstandigheden duren alle stages even lang en voer je een heel groot aantal instructies uit waardoor de speedup = aantal stages. In realiteit is dit echter niet zo en is de speedup < aantal stages.

RISC-V is ontworpen voor pipelining:

• elke instructie is even lang, ophalen altijd gelijk (makkelijker voor fetch en decodering)
• heeft weinig instructieformaten
• geheugen operanden alleen in stores en loads

Question 17

Comment figure 4.77

Answer 17

DGEMM, met zowel AVX subword-parallelism als loop unrolling om meer kansen te creëren voor instruction-level parallelism. (performantie: unoptimized 1.7 GFLOPS, AVX 6.4, AVX + unroll 14.6)

Question 18

Comment figures 4.73, 4.75, 4.76

Answer 18

4. 73: performantie ARM cortex-A53 op benchmarks: ideale CPI = 0.5 (2 micro operaties/cyclus) + pipeline stalls + memory hierarchy stalls + mcf heel moeilijk programma snel te krijgen.
5. 75: performantie i7 op benchmarks: 4 micro operaties/cyclus (theoretisch) + stalls en misvoorspellingen
6. 76: I7 ‘verloren werk’: percentage misvoorspellingen van branches en hun verloren werk

Question 19

Commit unit

Answer 19

Dit is 1 van 3 grote delen van een processor bij dynamic pipeline scheduling. Dynamische of out-of-order pipeline dat bepaalt wanneer het veilig is een resultaat van een operatie in het register en geheugen te plaatsen, zichtbaar voor de programmeur.

Question 20

Control hazard

Answer 20

Algemeen veroorzaken hazards pipeline stalls (situatie waardoor een instructie-stroom niet gewoon verder kan uitgevoerd worden in de pipeline). Bij control hazards (= branch hazards) is de uitkomst van een conditionele branch nog niet geweten. We moeten dus een beslissing maken gebasseerd op een resultaat dat nog aan het uitvoeren is (bv. Branch): We kunnen dit oplossen via een stall of via branch prediction.

Question 21

Control signal

Answer 21

Een signaal dat gebruikt wordt voor het aansturen van multiplexors of om te bepalen welke operatie een functionele unit moet uitvoeren. Het staat in contrast met een data signaal dat de info bevat dat gebruikt wordt door het functionele element.

Voor de eenvoud tonen we geen controle signaal als er bij elke klok tik in een state element geschreven worden. Als dit niet het geval is, is een expliciet controle signaal nodig en zal een controle lijn aangeven wanneer er geschreven wordt.

De output van een control unit bestaat uit 2 1-bit signalen dat gebruikt worden om multiplexors the controleren (ALUSrc en MemtoReg), 3 signalen om het lezen en schrijven in een register file en geheugen te controlereren (RegWrite, MemRead en MemWrite), 1 signaal om te bepalen of er gebranched wordt (Branch) en een 2-bit signaal voor de ALU (ALUOp).

Question 22

Correlating predictors

Answer 22

Je gebruikt niet alleen de info van de lokale branches (per sprong bijhouden wat die sprong de vorige keer / keren deed), maar ook het globale gedrag van de meest recente branches om een prediction te maken voor het branch target adress. Door niet enkel info te gebruiken van de lokale branches (zoals gedaan wordt bij 1-bit of 2-bit dynamic predictors), zorgt men voor een grotere predictie accuraatheid voor hetzelfde aantal prediction bits.

De globale geschiedenis (= gedrag van sprong hangt af van vorige sprongen in heel programma) wordt bijgehouden in 1 lang schuifregister.

Question 23

Data hazards

Answer 23

Algemeen veroorzaken hazards pipeline stalls (situatie waardoor een instructie-stroom niet gewoon verder kan uitgevoerd worden in de pipeline). Bij data hazards heeft een instructie gegevens nodig die nog niet beschikbaar zijn. Er is dus een stall in pipeline doordat een stap moet wachten op een voorgaande stap om te voltooien.
Primaire oplossing is gebaseerd op de observatie dat we niet moeten wachten tot de instructie voltooid is om de hazard op te lossen. Forwarding: het toevoegen van extra HW om het resultaat direct naar de plaats te brengen waar het nodig is. Kan enkel als de bestemminsgstage later in tijd voorkomt.

Question 24

Datapath

Answer 24

Een verzameling van functionele elementen (bv alu, data memory, instruction memory, …) die operaties uitvoeren voor gegevensverwerking, als ook registers en buses (=datapad voor informatieuitwisseling tussen CPU, RAM en I/O). Samen met de controle eenheid vormt het datapad de CPU.

De basiselementen van een datapad zijn:

• een geheugen unit om de instructies van het programma in op te slaan en instructies te geven gegeven het adres (dit is een state element)
• PC dat het adres van de huidige instructie bijhoudt (dit is een state element)
• adder dat de PC verandert naar het adres van de volgende instructie

Question 25

Destination register in instruction format

Answer 25

Destination register is 5 bits lang en komt voor bij R en I type instructies. Het bepaald in welk register het resultaat van de ALU of uit het geheugen geschreven moet worden.

Question 26

Difference between figures 4.11 and 4.15

Answer 26

Het verschil is dat nu alle nodige multiplexors en controlelijnen zijn toegevoegd (in fig 4.15). Ook de ALUOp control signal is toegevoegd.

Question 27

Differences between figures 4.9 and 4.10

Answer 27

4.10 is een datapad voor een R, S, en I-type en 4.9 is voor een SB-type (branch)

Question 28

Don’t care terms

Answer 28

Termen in een waarheidstabel die geen invloed hebben op de uitkomst, ongeacht of ze 0 of 1 zijn. Deze maken de tabellen korter.
bv. bij de waarheidstabel voor de 4 ALU controle bits maakt het bij de ALUOp bits 00 niet uit wat de funct7 en funct3 velden zijn.

Question 29

Dynamic branch prediction

Answer 29

Prediction of een branch al dan niet genomen wordt die zich baseert op runtime informatie en zich dus aanpast tijdens de uitvoer van het programma. De predictie wordt dus bepaald tijdens de uitvoering. De hardware meet het branch gedrag door de recente geschiedenis van elke branch bij te houden. Het veronderstelt dat het toekomstig gedrag = huidig gedrag en bij misvoorspelling krijg je een stall + aanpassing van geschiedenis.

Question 30

Dynamic branch prediction: 1-bit predictor

Answer 30

Houdt 1 bit bij van de vorige status van de branch (taken of untaken), nadeel is dat de nauwkeurigheid gelijk zal zijn aan de taken branch frequentie voor veel voorkomende branches. Bij de 1-bit predictor kunnen binnenste lussen twee maal misvoorspeld worden. Een beter alternatief is de 2-bit predictor.

Question 31

Figure 4.19: explain all lines that are active during an R-type instruction

Answer 31

1) Instructie wordt opgevraagd en de PC wijst naar de volgende adres.
2) De controle eenheid berekent de setting van de controle lijnen en 2 registers worden gelezen uit het register file
3) De ALU voert de bewerking uit, afhankelijk van de opcode
4) Het resultaat van de ALU wordt geschreven in het destination register

Question 32

Figure 4.20: explain all lines that are active during a load instruction

Answer 32

1) Instructie wordt opgevraagd en de PC wijst naar de volgende adres
2) Een register waarde wordt gelezen uit register file
3) De ALU neemt de som van de read en de sign extended 12 bits van de instructie (offset)
4) Som van de ALU wordt gebruikt als adres in het geheugen
5) De data uit het geheugen wordt geschreven in het destination register

Question 33

Figure 4.21: explain active lines during branch-if-equal instruction

Answer 33

1) Instructive wordt opgevraagd en de PC wordt naar het volgende adres gezet
2) 2 registers worden gelezen uit register file
3) De ALU trekt de waarden van de reads van elkaar af en de waarde van de PC wordt opgeteld bij de sign-extended 12 bits van de instructe (left shift met 1(, het resultaat is het branch target adress
4) De nul status van de ALU wordt gebruikt om te beslissen welk adres het volgende is en dus de PC.

Question 34

AluOp

Answer 34

2-bit controle veld dat aanduid of de operatie die moet uitgevoerd worden een add(00) is voor loads en stores, substract en test if zero (01) voor beq of afhankelijk is van de operaties gecodeerd in de velden funct7 en func3 (10) voor R-type instructies.
De bits worden gegenereerd in de main controle unit en zijn output wordt gebruikt door de ALU control unit

Question 35

Dynamic branch prediction: 2-bit predictor

Answer 35

Een prediction moet 2 keer fout zijn voordat de prediction wordt veranderd. Dit is het betere alternatief van de 1-bit predictor

Question 36

Dynamic multiple issue

Answer 36

Een implementatie van een multiple issue schema waarbij de beslissingen worden gemaakt tijdens de executie door de processor. De hardware bepaalt dan welke instructies samen worden uitgevoerd.
Alternatief is static multiple issue

Question 37

Dynamic pipeline scheduling

Answer 37

Kiest welke instructie we gaan uitvoeren in een gegeven clock-cyclus om stalls en hazards te vermijden. (herorganisatie van de volgorde van de instructies). Een superscalar processor bevat dit.

In zo’n processor wordt de pipeline in 3 delen onderverdeeld:

• instruction fetch en issue unit: fetchen van instructies, ze decoderen en elke instructie naar de overeenstemmende functionele unit sturen voor execution.
• multiple functional units (inclusief reservation stations)
• commit unit

Question 38

Edge-triggered clocking

Answer 38

Een clocking methodology bepaalt wanneer signalen gelezen of geschreven worden (kan niet tegelijk want dit zou de hardware onvoorspelbaar maken door rommel).

Een clocking methodology, waarin elke verandering van een staat op een clock edge moet gebeuren wordt een edge-triggered clocking methodology genoemd. (clock edge = snelle transitie van H-voltage L-voltage) Aangezien enkel state elementen een datawaarde kunnen opslaan, moeten de inputs van een set van state elements komen en de outputs in een set van state elementen geschreven worden.
(state element 1 -> combinational logic -> state element 2). Deze methodology laat ons toe dat het lezen, bewerken en schrijven in 1 klokcyclus kan gebeuren.

Question 39

Figure 4.28

Answer 39

Een voorbeeld van een pipeline stall of bubble (bij data hazards)

Question 40

Exception

Answer 40

= interrupt = een onvoorziene omstandigheid dat een executie van het programma tegenhoudt (kan zowel een externe als interne oorzaak zijn), wordt gebruikt om niet gedefinieerde instructies op te sporen (bv. overflow, een niet bestaande instructie, oproep naar OS)

Het behandelen van exceptions is een kritisch element in het ontwerp en is een deel van de controle. Het is het moeilijkste deel om juist te krijgen en snel te maken. Het moet goed bekeken worden van bij het begin.

Question 41

Exception program counter

Answer 41

= SEPC (supervisor exception program counter)
Wordt gebruikt om het adres op te slaan van de instructie waarbij tijdens het uitvoeren een exception is ontstaan. Dit is een van de basisacties die de processor moet ondernemen wanneer een exception zich voordoet. Men doet dit zodat men hier eventueel naar kan terugkeren (bv. nadat de OS actie heeft ondernomen) .

Question 42

Figure 4.42 and 4.43

Answer 42

4. 42: Een traditionele versie van de multiple-clock-cycle pipeline diagram met de naam van elk stadium. Wordt gebruikt om te laten zien wat er in elke clock-cyclus gebeurt in de pipeline
5. 43: Een single-clock-cycle diagram: geeft de uitgevoerde taken weer in 1 clock-cyclus

Question 43

Role of funct3 and funct7 in instruction format

Answer 43

Deze velden worden gebruikt om de 4-bit ALU control input te genereren (enkel bij R-type instructie van belang).
funct7 (bits 31:25) –> 7 bits
funct3 (bits 14:12) –> 3 bits

Question 44

Forwarding

Answer 44

= bypassing = een methode om data hazards op te lossen door het missende data element uit interne buffers te halen ipv. te wachten tot deze in een register of het geheugen wordt gestoken (gaat alleen indien destination stage later is de source stage) (lost niet echt load-use data hazards op = een load nog niet zichtbaar voor instructie dat hem nodig heeft)

Question 45

How to reduce the delay of branches?

Answer 45

Een mogelijkheid om de delay van branches te verkleinen is door niet langer in de MEM-stage de branch te selecteren, maar dit vroeger te doen (de branch adder in de ID stage doen ipv in de EXEC stage). Dit zou voor een lager aantal geflushte instructies zorgen indien foute predictie. We moeten er natuurlijk wel voor zorgen dat deze optimalisatie ook werkt voor registervalues die nog in de pipeline zitten. Een add net voor een beq zal 1 stall met zich meebrengen, een ld net voor een beq 2. Door dit te doen met er natuurlijk een extra controlelijn toegevoegd worden (IF.Flush) die aangeeft of er een instructie geflushd moet worden.

Question 46

Figure 4.50

Answer 46

Pipeline afhankelijkheden in een sequentie van 5 instructies, we merken op dat de uitkomst van de eerste instructie pas in cyclus 5 wordt geschreven → elke instructie dat het resultaat nodig heeft voor instructie 5: pipeline data hazards

Question 47

ILP

Answer 47

= instruction level parallelism
Parallelism bij instructies bv. pipelining. Er zijn 2 methodes om het te verbeteren:
- De diepte van de pipeline vergroten zodat het meer instructies kan overlappen (hierdoor kan de klockcyclus korter worden)
- Multiple issue: meerdere instructies kunnen in 1 clock cyclus beginnen doordat de interne componenten van de computer gerepliceerd worden → hardware (vraagt wel extra werk om elke pipeline bezig te houden en de lading naar de volgende pipeline stage over te brengen) Dit zorgt ervoor dat de CPI kleiner wordt dan 1 (instruction execution rate exceeds clock rate)

Question 48

Imprecise exception

Answer 48

Interrupts of exceptions in een pipelined computer die niet geassocieerd zijn met de exacte instructie dat de oorzaak was voor de interrupt/exception. Dit kan gebruikt worden bij noncritical cases.

Een alternatief is precise exceptions.

Question 49

Figure 4.52

Answer 49

Een representative van de forwarding unit, die 2 axtre multiplexors nodig heeft. (is een simplistische voorstelling, er ontbreken nog delen, bv sign extension hardware)

Question 50

Immediate field in instruction format

Answer 50

Het is het veld van een instructie die de offset voor een branch, load en store bevat. Voor een branch dient deze offset als offset voor de PC indien de branch genomen wordt. Voor load en store kan dit gebruikt worden als offset voor een geheugenadres.

Question 51

In-order commit

Answer 51

Een commit waarbij de resultaten van de pipeline geschreven worden, zichtbaar voor de programmeur, in dezelfde volgorde als de instructies opgehaald zijn. Dit wordt gebruikt als men wil dat het programma zich gedraagt alsof het een simpele in-order pipeline aan het runnen is. Dus als een exception zich voordoet, zal de computer wijzen naar de laatste instructie die is uitgevoerd en zullen de enige registers die upgedated worden diegene zijn die geschreven werden door instructies voor de instructie die de exception veroorzaakte.

Question 52

Instructieformaat van RISC-V

Answer 52

We hebben 4 instructie klassen:

• arthimetic-logical instructies (add, sub, and, or, slt) heeft steeds 2 operanden registers en 1 resultaat register.
• memory-reference instructie load
• memory-reference instructie store
• conditional branch instructies (beq)

Deze 4 klassen hebben elk verschillende instructieformaten. (zie fig. 4.14). Ze bestaan mogelijks uit:
- opcode: bits 6:0 (voor alle formaten), eventueel aangevuld met funct3 en funct7
- registers rs1 (19:15) en rs2 (24:20)
Voor R-type instructies en branch instructies zijn dit de registers die gelezen worden. Voor load en store instructies is rs1 het basisregister. Voor store is rs2 het register de operand die naar het geheugen wordt gekopieerd
- resultaat register bits 11:7
12-bit offset (gesplitst over 2 velden voor S en SB-type instructies)

–> simplicity favors regularity

Question 53

Interrupt

Answer 53

Interrupt is een expection die een externe oorzaak heeft. Het is dus een exception die zich buiten de processor heeft voorgedaan. (bv. System reset, I/O device request, HW probleem)

Question 54

Issue packet

Answer 54

Verzameling van instructies die in dezelfde clock cyclus voorkomen. (kan statisch → compiler, dynamisch → processor bepaald worden)

Men praat over een issue packet bij static / dynamic multiple-issue processors.

Question 55

Figure 4.58

Answer 55

Een weergave van een pipelined control datapad om data hazards tegen te gaan; Met 2 multiplexors voor de forwarding unit en de hazard detection unit.

Question 56

Issue slot

Answer 56

De slots waarin instructies geplaatst kunnen worden waarin ze wachten op de functionele unit en op eventueel nodige inputs (vb. wachten op operand uit het geheugen).

Question 57

SB-type instructions

Answer 57

= branch instruction. The beq instructie (beq x1, x2, offset ) heeft 3 operanden, nl. 2 registers die vergeleken worden en een 12-bit offset dat gebruikt wordt om de PC te berekenen voor de branch target address.
De branch target address wordt gevonden door de offset op te tellen bij de PC.
We moeten ook bepalen of de volgende instructie diegene is dat erop volgt of het de instructie op de branch target address is (door 2 registers te vergelijken) -> branch taken of untaken.

Deze instructie omvat een immediate generation unite (om branch target address te berekenen), een registere file (om 2 registers te lezen) en een ALU (om de 2 registers te vergelijken).

= Branch instruction = ALU (branch condition), adder (branch target) , shift left 1 (in instructive: offset/2 → opnieuw x2 doen), ImmGenn (32→ 64 bit), register file

Question 58

Loop unrolling

Answer 58

Een techniek om een betere performantie te krijgen voor loops die toegang hebben tot arrays waarbij er veel iteraties zijn en de instructies van verschillende iteraties samen worden gebracht. Bij loop unrolling worden meerdere kopieën gemaakt van de loop body zo heb je meer instructies in de lus die je dan beter kan ‘schedulen’.

Question 59

Microarchitecture

Answer 59

De organisatie van een processor, inclusief de belangrijkste functional units, hun interconnectie en controle.

Question 60

Figure 4.60

Answer 60

Een predictie van een branch (taken). Voor de volgende cyclus flusht hij dus de volgende instruction fetched. ??

Question 61

Multiple issue

Answer 61

Een schema om pipelining te verbeteren via extra hardware (interne componenten van de computer worden gedupliceerd) zodat er meerdere instructies per clock cyclus gestart kunnen worden. Er zijn 2 manier om een multiple-issue processor te implementeren, het grote verschil tussen de 2 is de divisie van werk tussen de compiler en hardware (static of dynamic). Een multiple-issue pipline heeft 2 belangrijke opdrachten:

• instructies ‘verpakken’ in issue slots (= hoeveel instructies en welke instructies kunnen tegelijk gestart worden)
• omgaan met data en controle hazards (= hoe gaan we er mee om, wie test er op hazards?)

Question 62

Multiplexors

Answer 62

= data selector = een logisch element uit het datapad, gebruikt om te kiezen uit verschillende bronnen van info en 1 van deze bronnen naar zijn bestemming begeleiden

Question 63

Nops

Answer 63

Instructie die geen bewerking maakt om een status te veranderen. Door een instructie een nop te maken, creëer je een bubble (=stall)

Question 64

Opcode en zijn rol in controle

Answer 64

Duid het formaat en operatie van de instructie aan. Het bepaald ook of funct7 en funct3 een uitbereiding zijn van het veld. Bij de instruction format bevindt de opcode zich altijd in bits 6:0. De opcode bepaalt de controlelijnen (behalve de PC controlelijn).

Question 65

Out-of-order execution

Answer 65

Een situatie in gepipelinede uitvoering waarbij het blokkeren van een instructie de volgende instructies niet noodzakelijk blokkeerd. De instructies kunnen dus in een andere volgorde uitgevoerd worden dan waarin ze gefetcht werden.

Question 66

Figure 4.61

Answer 66

Een schema voor een 2-bit prediction scheme voor dynanmic branch prediction

Question 67

Pipeline hazards

Answer 67

Dit zijn situaties waardoor een instructie-stroom niet gewoon verder kan uitvoeren (in dezelfde clock cyclus) in de pipeline. Er zijn 3 verschillende soorten: data, control en structural hazards. De gevolgen van een hazard zijn dat alle instructies na de gestopte instructie blokkeren. Dus er kan geen nieuwe instructie beginnen in de pipeline. Door stalls (bubble) zal de speedup en de performantie verlagen.

Question 68

Figure 4.62

Answer 68

Een volledig datapad met alles erop en eraan om nu ook data en control hazards op te lossen, controle, detection unit, forwarding unit, pipeline registers, …

Question 69

Pipeline registers

Answer 69

Bij een pipeline verdelen we ons datapad in 5 onderdelen die elk een deel van de operatie uitvoeren: instruction fetch, instructio decode / registers file read, execution / address calculation, memory access en write-back. Omdat sommige van deze delen meer tijd in beslag kunnen nemen dan anderen en er in de ideale pipeline in elk deel iets gebeurt, zetten we pipeline registers tussen elke van de stages.

Het zijn dus registers die de verschillende stadia in de pipeline scheiden. Deze registers houden de data bij die een instructie in de volgende stap in de pipeline in de volgende cyclus nodig heeft. Deze houdt ook de informatie bij van de control unit (die tijdens stage2: decoderen van de instructie) vrijkomt en geeft deze door naar de gepaste stadia.

Question 70

Pipeline stall

Answer 70

= bubble = Een stall om een hazard op te lossen. Dit komt voor bij pipelining.

Question 71

Figure 4.49

Answer 71

Een pipelined datapad met de controle signalen geordend per pipeline register

Question 72

Precise exception

Answer 72

Een interrupt/exception die altijd geassocieerd is met de juiste instructie in een pipelined computer

Question 73

Program counter

Answer 73

Register met het adres van de instructie, die op dat moment wordt uitgevoerd.

Question 74

Figure 4.63

Answer 74

Datapad met controle bij om nu ook exceptions te fixen. SCAUSE, SEPC, 2 nieuwe multiplexors en 1 adder, om eventueel ook de ID en de EX te flushen.

Question 75

Register file

Answer 75

De processor zijn general-purpose registers worden opgeslagen in een structuur genaamd register file. Het is een state element dat bestaat uit een set registers die gelezen en geschreven kunnen worden via het registernummer. Het bevat dus de register-staat van de computer.

Question 76

Register renaming

Answer 76

Het hernoemen van registers door de compiler/hardware om afhankelijkheden weg te werken. (gebeurt tijdens loop unrolling, bij dynamic pipeline scheduling: bufferen)

Question 77

Reorder buffer

Answer 77

De buffer in de commit unit (1 van de 3 grote delen van een processor bij dynamic pipeline scheduling): houdt de resultaten bij in een dynamically scheduled processor tot het veilig is het resultaat in het geheugen/een register te plaatsen en dus tot ze gecommit worden door de commit unit.

Question 78

Figure 4.64

Answer 78

Het resultaat op het datapad voor een exception door het falen van hardware tijdens een add instructie. De exception wordt gevonden tijdens de execute fase, waarna het de add instructie in het SEPC register steekt. Om daarna de ex fase te flushen

Question 79

Reservation station

Answer 79

Een buffer in een functional unit, verantwoordelijk voor de operanden en de operaties bij te houden. De functional unit is 1 van de 3 grote delen in een processor die dynamic pipeline scheduling gebruikt. Zodra de buffer al zijn operanden bevat en de functionele unit klaar is om uit te voeren, wordt het resultaat berekend.

Question 80

R-type instructions

Answer 80

= arithmetic logical instructions = Instructies die 2 registers lezen, dan een bewerking doen in de ALU, en tot slot het resultaat in een register schrijven. (add, sub, and, or, …)

Om deze instructies te implementeren, hebben we een register file en ALU nodig. Het register file bevat alle registers. We moeten 2 data woorden van het register file lezen en 1 data woord in het register file schrijven voor elke instructie.

Question 81

Setting the control lines (figure 4.18)

Answer 81

8 controle lijnen, afhankelijk van het formaat zullen zij een andere waarde hebben, worden berekend door de main control in de 2de stap van een instructie. De setting van de controlelijnen is volledig bepaald door de opcode velden van de instructie.

Question 82

Sign-extend unit

Answer 82

= Immediate generation unit = vergroten van een data-item door de high order sign bit van het originele data-item te dupliceren naar de high order sign bit van het grotere data-item.
Dit wordt bv. gebruikt in de S-type instructies om het 12 bit offset veld in de instructie naar een 64-bit signed value om te zetten.

Question 83

Figure 4.66

Answer 83

Een 2-issue datapad (kan dus 2 instructies tegelijk aan), heeft nood aan extra: Imm Gen, ALU, 2 meer read en write poorten in register, (enkel voor adress calculations)

Question 84

Single cylce implementation

Answer 84

Bij single cycle implementation moet elke klok cyclus dezelfde lengte hebben voor elke instructie. Elke instructie voert uit in 1 klok cyclus. Dus de lengte van 1 klok cyclus = duur van langste instructie. Elke functie-eenheid wordt maar 1 keer gebruikt per cyclus. Dus het moet gedupliceerd worden als het meerdere keren wordt gebruikt. Dit is duur.

Beter alternatief: pipelining (heeft hogere throughput). Het verbetert de efficiëntie door meerdere instructies tegelijkertijd uit te voeren.

Question 85

Source registers in instruction format

Answer 85

rs1: bits 19:15, rs2: bits 24:20 (elk uit 5 bits dus)
Voor R-type en SB-type instructies zijn dit de registers die gelezen moeten worden. Voor load en store instructies is rs1 het basisregister. Voor store is rs2 het register de operand die naar het geheugen wordt gekopieerd

Question 86

Speculation

Answer 86

Speculatie is een manier van prediction, waarbij de compiler of de processor de uitkomst van een instructie probeert te raden, zodat het geen afhankelijkheid kan vormen tijdens de uitvoering van andere instructies. (methode nodig om te zien of de gok juist is en methode om terug te keren indien fout)

Zowel de compiler als hardware ondersteunen speculatie:

• compiler: zal extra instructies invoegen voor terug krabbelen
• HW: buffert resultaten, nog niet definitief wegschrijven

Speculatie kan wel voor extra problemen zorgen, nl. exceptions die daarvoor nog niet aanwezig waren.

Question 87

State element

Answer 87

Er zijn 2 soorten logische elementen in een datapad (combinational en state elementen). Een state element = sequential element is een element dat een toestand bevat. Het resultaat hangt af van de input en de toestand. Het bevat dus een geheugen. bv. een register. Een stat element heeft steeds minstens 2 inputs (de klok die zegt wanneer geschreven wordt en de nieuwe inhoud) en 1 output (oude inhoud).

Een register of het geheugen: Een element dat een status bijhoudt en dus wel een intern geheugen heeft
 combinational element (vormen samen alle elementen in een datapad)

Question 88

Static multiple issue

Answer 88

Een implementatie van een multiple issue schema waarbij de beslissingen worden gemaakt door de compiler voor de uitvoering. De compiler bepaalt dan welke instructies samen worden uitgevoerd.
Een alternatief is dynamic multiple issue

Question 89

Structural hazards

Answer 89

Algemeen veroorzaken hazards pipeline stalls (situatie waardoor een instructie-stroom niet gewoon verder kan uitgevoerd worden in de pipeline). Structural hazards zijn hazards bekomen doordat de hardware de combinatie van instructies die we in dezelfde clock-cyclus willen uitvoeren niet kan uitvoeren door conflicten over resources. Dus bv. als een bepaalde resource niet voldoende gerepliceerd is.

bv als er geen apart geheugen is voor de instructies en de data, zou dit tot conflicten kunnen leiden. => extra HW toevoegen => register klok cyclus opdelen in 2 (rising edge read, falling edge write), wordt soms toegelaten door plaatsgebrek of om kosten laag te houden.

Question 90

I-typeen S-type instructions

Answer 90

= load en store instructions
Deze instructies berekenen een geheugenadres door het basisregister x2 op te tellen met een 12-bit offset value dat in de instructie staat. Voor deze instructies hebben we een register file en ALU nodig. We hebben ook een immediate generation unit nodig om de 12-bit offset value te verlengen naar een 64-bit signed value en een data memory unit om uit te lezen of in te schrijven.

• Store: waarde dat opgeslagen moet worden, moet ook gelezen worden uit register (x1)
  sd x1, offset(x2)
• Load: waarde dat gelezen wordt uit geheugen moet ook in het register komen (x1)
  ld x1, offset(x2)

Question 91

Figure 4.74

Answer 91

De I7 core pipeline met geheugencomponenten: depth = 14 stages (branch mispredictions = 17 clock cycles), buffer 48 loads en 32 stores, 6 onafhankelijke units die elks een uitvoering kunnen beginnen elke clock cyclus. (zie p 339-339 voor stappen executie)

Question 92

Superscalar processor

Answer 92

Een dynamische multiple-issue processor: een geavanceerde pipeline techniek waarbij de processor meer dan 1 instructie per clock cyclus kan uitvoeren door ze te selecteren tijdens uitvoering (verschilt met VLIW: de hardware garandeert altijd dat de code correct wordt uitgevoerd). De hardware is verantwoordelijk voor alle hazard detecties.

Question 93

Table of figure 4.16

Answer 93

Duid de functie van de 6 controle lijnen aan. (PCSrc kan je nog splitsen in branch en zero uit ALU en zie def. voor ALUOp)

Question 94

Tournament predictor

Answer 94

Een branch predictor die meerdere predictors en een selectiemechanisme gebruikt om voor elke branch bij te houden wat de beste resultaten levert. Typisch houdt deze 2 voorspellingen bij, 1 gebaseerd op locale en 1 op globale geschiedenis en kiest het dan de beste via het selectiemechanisme.

Een andere mogelijkheid is een correlating predictor die het lokale gedrag van een bepaalde branch en de globale informatie over het gedrag van een recent aantal uitgevoerde branches combineert. Een branch predictor wordt gebruikt om branch hazards op te lossen zonder stalling te gebruiken. (of 1-bit of 2-bit dynamic predictor)

Question 95

Vectored interrupts

Answer 95

Een methode (SCAUSE is andere methode, wat RISC-V ook gebruikt) om de reden van een exception te communiceren: het adres waarnaar de controle overgebracht wordt, wordt bepaald door de oorzaak van de exception. De OS weet dan de reden door het adres

Question 96

Figures 4.34, 4.35, 4.36, 4.37 and 4.38

Answer 96

De pipeline stages voor een load en een store instructie (inclusief de pipeline registers), waarvan de actieve delen gemarkeerd zijn. (rechts = read, links = write)

Question 97

VLIW

Answer 97

= very long instruction word
Een ISA stijl die veel individuele operaties begint als 1 grote instructie, typisch met veel aparte opcode velden.
Dit is de originele naam van de multiple-issue approach.

Question 98

Why is a single cycle implementation not used?

Answer 98

Te inefficiënt: clock-cylus moet dezelfde lengte hebben voor elke instructie → langst mogelijke pad bepaald clock-cyclus (load), het wordt dus ook nutteloos om de common case snel te maken, aangezien de snelheid enkel afhangt van de worst case

Alhoewel dus de CPI gelijk is aan 1, is de performantie in het algemeen niet zo hoog aangezien de klok cyclus te lang is.

Oplossing: pipelining

Question 99

Voordeel RISC-V t.o.v. x86 voor pipelining +

Answer 99

1) Makkelijker op te zoeken/decoderen → vaste lengte
2) Weinig soorten instruction formats
3) Memory operands alleen in loads/stores

Question 100

Flush +

Answer 100

Discard instructies in een pipeline door een onverwachte gebeurtenis.

Question 101

SCAUSE

Answer 101

= supervisor exception cause register
Dit is 1 van de methoden die gebruikt wordt om ervoor te zorgen dat de OS de reden van exception kent.
De methode die gebruikt wordt in de RISC-V architectuur is om een register bij te houden met de reden. Bij elke exception of interrupt spring je dan naar hetzelfde adres. Het is dus een 64-bit register dat de oorzaak van de exception weergeeft.

Een andere methode is het gebruik van vectored interrupts

Question 102

Stappen nodig voor elke instructie +

Answer 102

1. haal de instructie uit het geheugen, de program counter heeft het adres van de instructie.
2. lees de nodige registers
3. doe wat in de instructie staat. Bijna alle instructies gebruiken hiervoor de ALU:
   - arithmetic-logical instructies: voor bewerking
   - memory reference instructies: voor adresberekening
   - sprongen: voor vgl
4. deze stap varieert voor verschillende instructies:
   - arithmetic-logical instructies: schrijf resultaat in register
   - memory reference instructies: toegang tot geheugen
   - sprongen: pas PC aan

Question 103

Clocking methodology +

Answer 103

Dit definieert wanneer een signaal gelezen kan worden en wanneer het geschreven kan worden. Dit is belangrijk want we kunnen niet lezen en schrijven tegelijkertijd, dit zou namelijk mogelijk rommel geven. Een clocking methodology is ontworpen om hardware voorspelbaar te maken.

Question 104

Static branch prediction +

Answer 104

Assumptie die bepaald wordt voor de uitvoering. Het is gebaseerd op typische branch gedrag.