Universiteit Leiden, Computerarchitectuur
Computer Architecture, A Quantitative
Approach
John L. Hennesy & David A. Patterson, 4th edition
Samenvatting
, Contents
1 Hoofdstuk 1. Fundamentals of Quantitative Design and Analysis 3
1.1 Introductie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Computerklassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 De definitie van Computer Architecture . . . . . . . . . . . . . . . . . . . 6
1.4 Trends in de technology . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Trens in power en energie in integrated circuits . . . . . . . . . . . . . . 8
1.8 Meten, rapporteren en samenvatten van prestatie . . . . . . . . . . . . . 9
1.9 Kwantitatieve principes van computer design . . . . . . . . . . . . . . . . 10
2 Hoofdstuk 2. Memory Hierarchy Design 11
2.1 Introductie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Tien geavanceerde optimalisaties voor Cache prestatie . . . . . . . . . . . 11
2.3 Memory technology en optimizations . . . . . . . . . . . . . . . . . . . . 13
2.8 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Hoofdstuk 3. Instruction-Level Parallellism and It’s Exploitation 14
3.1 Instruction-level parallellism: concepts and challenges . . . . . . . . . . . 14
3.2 Basic compiler techniques for exposing ILP . . . . . . . . . . . . . . . . . 16
3.3 Reducing branch costs with advanced branch prediction . . . . . . . . . . 17
3.4 Overcoming data hazards with dynamic scheduling . . . . . . . . . . . . 17
3.5 Dynamic scheduling: examples and the algorithm . . . . . . . . . . . . . 19
3.6 Hardware-based speculation . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.7 Exploiting ILP using multiple issue and static scheduling . . . . . . . . . 20
3.9 Advanced techniques for instruction delivery and speculation . . . . . . . 21
3.12 Multithreading: exploiting thread-level parallellism to improve uniproces-
sor throughput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.14 Fallacies and pitfalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Hoofdstuk 4. Data-level parallellism in vector, SIMD and GPU archi-
tectures 22
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Vector architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3 SIMD instruction set extensions for multimedia . . . . . . . . . . . . . . 24
4.4 Graphics processing units . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.5 Detecting and enhancing loop-level parallellism . . . . . . . . . . . . . . 28
4.9 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1
,A A. Instruction set principles 28
A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
A.2 Classifying instruction set architectures . . . . . . . . . . . . . . . . . . . 29
A.3 Memory addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
A.4 Type and size of operands . . . . . . . . . . . . . . . . . . . . . . . . . . 31
A.5 Operations in the instruction set . . . . . . . . . . . . . . . . . . . . . . . 31
A.6 Instructions for control flow . . . . . . . . . . . . . . . . . . . . . . . . . 31
A.7 Encoding an instruction set . . . . . . . . . . . . . . . . . . . . . . . . . 32
A.8 Crosscutting issues: the role of compilers . . . . . . . . . . . . . . . . . . 32
A.9 Putting it all together: the MIPS architecture . . . . . . . . . . . . . . . 33
B B. Review of memory hierarchy 33
B.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
B.2 Cache performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
B.3 Six basic cache optimizations . . . . . . . . . . . . . . . . . . . . . . . . 36
B.4 Virtual Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
C C. Pipelining: basic and intermediate concepts 38
C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
C.2 The major hurdle of pipelining - pipeline hazards . . . . . . . . . . . . . 40
C.4 What makes pipelining hard to implement? . . . . . . . . . . . . . . . . . 42
D Extra uitleg en voorbeelden 43
D.1 Direct mapped caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
D.2 Set associative & fully associative . . . . . . . . . . . . . . . . . . . . . . 44
D.3 Merging write buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
D.4 Dynamic scheduling: Scoreboarding . . . . . . . . . . . . . . . . . . . . . 46
D.5 Dynamic scheduling: Tomasulo . . . . . . . . . . . . . . . . . . . . . . . 47
2
,1.
Hoofdstuk 1. Fundamentals of Quantitative
Design and Analysis
1.1 Introductie
Er is binnen de computer technologie de afgelopen 65 jaar ongelofelijk veel vooruitgang
geboekt. Eind jaren 70 deed de microprocessor zijn intrede. Dit zorgde voor een per-
centueel hogere prestatieverbetering per jaar, namelijk 35%. Na introduction van de
RISC architectuur en andere verbeteringen steeg deze groei zelf naar 52%. Deze groei
hield 17 jaar aan, maar daalde vanaf 2003 weer naar 22%. Dit wordt veroorzaakt door
het stagneren van de klokfrequentie. De oorzaak hiervan is de power wall die ontstaat
doordat power niet verder toe kan nemen. Een hogere klokfrequentie vereist namelijk
een hoger voltage, omdat de transistoren dan sneller schakelen. Een hoger voltage
zorgt voor een meer power. De power, uitgedrukt in watt, kan echter niet omhoog
omdat meer dan 150 watt niet meer af te koelen is met ventilatie. Zie de formule
1
P owerdynamic = × Capacativeload × V oltage2 × F requencyswitched. Dit alles zorgt
2
dat de performance van de single processor stagneert. De verwerking van instructies kon
echter nog steeds worden versneld, door het gebruik van slimme trucs. Eén hiervan is In-
struction Level Parallellism. Voor deze methode geldt echter ook dat de limieten in zicht
zijn. Naast het toepassen van deze trucs werden en worden er steeds meer multi-core pro-
cessoren gebruikt, meerdere processoren op een chip in plaats van snellere uniprocessoren.
Daarnaast is er nog de memory wall, waarbij de performance van processoren veel sneller
3
,toeneemt dan dat van het interne geheugen(RAM). Verbetering van latency blijft dus
achter. Relatief gezien moeten nieuwe processoren dus steeds langer wachten op data uit
het geheugen.
1.2 Computerklassen
Het boek maakt onderscheidt in de volgende computerklassen:
1. Personal Mobile Device PMD: dit zijn de systemen zoals smartphones en tablet.
Ontwerp problemen zijn:
- kosten
- energiegebruik
- media performance
- responsiveness
2. Desktop: dit zijn de systemen zoals bureaucomputers en laptops. Ontwerpprob-
lemen zijn:
- prijs-performance verhouding
- energiegebruik
- graphics performance
3. Server: dit kan een enkele server op een kantoor zijn(2 CPU) tot groot schalige ma-
chines voor high end transaction processing(tientallen CPUs). Ontwerpproblemen
zijn:
- throughput
- beschikbaarheid
- schaalbaarheid
- algehele performance
4. Clusters/Warehouse scale computers: dit kunnen kleine clusters zijn die uit
16 nodes bestaan of volledig gevulde datacentra. Ontwerpproblemen zijn:
- prijs-performance verhouding
- throughput
- energie proportionaliteit (de kosten van energie, het koelen)
5. Embedded: dit zijn systemen zoals wasmachines, tandenborstels, USB-sticks enz.
Ontwerpproblemen zijn:
- kosten
- energiegebruik
- applicatie-specifieke performance
4
, Klassen Prijs systeem Prijs microprocessor
Personal Mobile Device(PMD) $100 - $1000 $10 - $100
Desktop $300 - $2500 $50 - $500
Server $5000 - $10.000.000 $200 - $2000
Clusters/warehouse scale computer $100.000 - $200.000.000 $50 - $250
Embedded $10 - $100.000 $0,01 - $100
We onderscheiden twee soorten parallellisme:
Data-Level Parallelism (DLP): er zijn vele data items die tegelijkertijd kunnen
worden verwerkt. Vaak gaat het hier om dezelfde operatie op elk item. Een image
filter over een foto: zelfde operatie op elke pixel toepassen.
Task-Level Parallelism (TLP): er zijn verschillende taken de onafhankelijk van
elkaar kunnen worden uitgevoerd. Het draaien van verschillende programma’s.
Computersystemen kunnen deze vormen van parallellisme op verschillende manieren aan-
pakken:
Instruction-level parallelism (ILP): data-level parallellisme dat te vinden is in een
enkele instructiestroom, bijv. pipelining: het werken aan meerdere instructies tegelijk.
Vector architectures, GPUs: maken gebruik van data-level parallellisme door
dezelfde instructie tegelijkertijd toe te passen op vele verschillende data items.
Thread-level parallelism: zowel data-level/task-level parallellisme door gebruik te
maken van threads.
Request-level parallelism: miljoenen gebruikers maken tegelijkertijd van Google
Search.
Let op: het boek heeft een hoofdstuk over elk van deze manieren.
Michael van Flynn bedacht in 1966 een classificatie van de manier waarop instructies
en data worden, Taxonomie van Flynn:
Single instruction stream, single data stream SISD: de uniprocessor valt binnen
deze categorie. De programmeur ziet ziet het als de standaard sequentiele computer,
maar het kan wel instruction-level parallellisme toepassen.
Single instruction stream, multiple data streams SIMD: meerdere processoren
voeren dezelfde instructie uit op verschillende data reeksen. SIMD computers passen
data-level parallellisme toe door dezelfde operaties op meerdere data items toe te
passen in parallel. Elke processor heeft zijn eigen data memory, maar er is een enkele
instructie memory en control processor die de instructies ophaalt en verdeelt onder de
processoren.
Multiple instruction streams, single data stream MISD: dit type is tot op
heden nog niet gebouwd, maar staat er voor de volledigheid van de classificatie.
5
, Multiple instruction streams, multiple data streams MIMD: elke processor
haalt zijn eigen instructies op en opereert op zijn eigen data. Dit is een vorm van task-
level parallellisme. MIMD is flexibeler dan SIMD, maar ook een stuk kostbaarder.
1.3 De definitie van Computer Architecture
Enkele jaren geleden verwees de term computer architecture enkel naar instruction set
design. De andere aspecten van computer design werden implementation genoemd. Vol-
gens het boek zijn behoren beide taken tot het ontwerpen van een computer architectuur.
We gebruiken de term instruction set architecture(ISA) om te refereren aan de voor
de programmeur zichtbare instructie set. De ISA dient als de schakel tussen software en
hardware. We delen de ISA op in onderstaande 7 dimensies:
1. Class of ISA: bijna alle ISAs vandaag de dag worden geclassificeerd als general-
purpose register architecturen, waarbij de operanden ofwel registers ofwel geheugen
locaties zijn. Verder zijn de meeste ISAs tegenwoordig load-store.
2. Memory addressing: bijna alle desktop en server computers maken gebruik van
byte adresseren om toegang te krijgen tot operanden uit het geheugen. Sommige
architecturen vereisen dat objecten aligned zijn. Toegang krijgen tot een object van s
bytes op byte adres A is aligned als A mod s = 0.
3. Addressing modes: in aanvulling op het specificeren van registers en constante
operanden gebruiken we addressing modes om het adress van een geheugen object te
specificeren. We tellen hiervoor een constante, de offset, op bij een register om een
geheugen adres te vormen.
4. Types and sizes of operands: Meeste ISAs ondersteunen een operand grootte van
8-bit: ASCII karakters
16 bit: Unicode karakters of half word
32 bit: interger of word
64-bit: double word of long integer
5. Operations: de operatie categorieën zijn over het algemeen data transfer, rekenkundige
en logica operaties, control en floating point.
6. Control flow instructions: zo goed als alle ISAs ondersteunen branches, uncon-
ditional jumps, procedure calls en returns. Alledrie maken gebruik van PC-relatieve
adressering, waarbij het branch adres gespecificeerd wordt door een adres veld die
optegeld wordt bij de PC.
7. Encoding an ISA: er zijn twee fundamentele keuzes voor het coderen van een ISAs:
fixed length en variable length. ARM en MIPS instructie formats bestaan bijvoorbeeld
standaard uit 32 bits, terwijl de codering van de 80x86 instructie format van variabele
length is en uit 1 tot 18 bytes kan bestaan. Fixed length maakt het decoderen van
instructies gemakkelijker, terwijl variable length vaak zorgt voor kleinere programma’s.
De implementatie van een computer bestaat uit twee componenten.
6
, Organization: omvat alle high-level aspecten van een computer design, zoals het mem-
ory systeem, de verbinding met het geheugen en het ontwerp van de interne processor
of CPU. Een alternatieve term hiervoor is microarchitecture.
Hardware: omvat de details van een computer, waaronder het gedetailleerde logica
ontwerp en de verpakkingstechnologie.
We kunnen nu zeggen dat de term computer architectuur in de boek verwijst naar de drie
behandelde termen: instruction set architecture ISA, organization of microarchitecture
en hardware.
1.4 Trends in de technology
Voor verdere evolutie van de computer moet de ontwerpen op de hoogte zijn van snelle
veranderingen binnen de implementation technologie. De volgende vijf implementatie
technologieën, die in drastisch tempo veranderen, zijn van groot belang voor moderne
implementaties:
Integrated circuit logic technology: de transistoren dichtheid neemt toe met 35%
per jaar, terwijl de chip grootte minder snel toeneemt met 10% tot 20% per jaar. Het
effect hiervan is dat het groeitempo van transistoren op een chip 40% tot 55% per jaar
is. Deze trend noemen we ook wel Moore’s law.
Semiconductor DRAM: het groeitempo van het DRAM neemt steeds verder af.
Men vraagt zich zelfs af of de groei volledig zal stagneren halverwege deze eeuw.
Semiconductor flash: dit read-only geheugen is het standaard opslag apparaat ge-
bruikt in PMDs en diens toenemende populariteit heeft gezorgd voor de grote groei in
de capaciteit ervan. De capaciteit per flash chip is toegenemen met zo’n 50% tot 60%
per jaar. Flash memory is 15 tot 20 keer goedkoper per bit dan DRAM.
Magnetic disk technology: begin 1990 groeide de dichtheid met zo’n 30% per jaar.
In 1960 steeg dit zelfs tot 100% per jaar. Sinds 2004 is het percentage echter weer
terug gedaald naar 40% per jaar. Disks zijn 15 tot 25 keer goedkoper per bit dan
flash en zelfs 300 tot 500 keer goedkoper per bit dan DRAM. Deze technologie staat
centraal binnen servers en warehouse scale storage.
Network technology: Netwerk performance is afhankelijk van zowel de performance
van switches als de performance van het transmission systeem.
Bandwidth/throughput: dit is de totale hoeveelheid werk gedaan in een gegeven ti-
jdsbestek, zoals het aantal megabytes per seconde voor een disk onverdracht.
Latency/response time: dit is de tijd tussen het starten en voltooien van een evene-
ment, zoals het aantal milliseconden voor een disk access.
Een simpele vuistregel voor deze twee begrippen is dat bandwidth groeit met ten minste
het kwadraat van de verbetering in latency.
7
,Integrated circuits worden gekarakteriseerd door de feature size. Dit is de minimale
grootte van een transistor of wire(draad) in zowel de x of de y dimensie. Feature sizes
zijn afgenomen van 10 microns in 1970 naar 0,032 microns in 2011. Aangezien het aantal
transistoren per vierkante millimeter siliconen bepaald wordt door het oppervlakte van
een transistor, is de dichtheid van transistoren kwadratisch toegenomen met een lineare
afname in de feature size. De toename in transistor performance is ingewikkelder. Als de
feature size krimpt, dan krimpt de grootte van devices kwadratische over de horizontale
dimensie en ook de verticale dimensie krimpt. Het krimpen in de verticale dimensie vereist
een reductie in het opererende voltage om correct uitvoeren en de betrouwbaarheid van
de transistoren te onderhouden. De combinatie van schaalfactoren leidt tot een complexe
verwevenheid tussen de transistoren performance en het proces van de feature size.
1.5 Trens in power en energie in integrated
circuits
Vandaag de dag is power de grootste uitdaging voor computer designers voor bijna elke
computerklasse. Vanuit het oogpunt van de ontwerper zijn er drie voornaamste be-
zorgdheden:
1. Wat is de maximale hoeveelheid power die een processor ooit nodig heeft?
2. Wat is de aanhoudende hoeveelheid power verbruik? De maatstaaf hiervoor wordt
de thermal design power(TDP) genoemd en geeft de hoeveelheid waarmee we moeten
koelen aan.
3. Wat is de energy efficiëntie? De energie benodigd voor het uitvoeren van een workload
is gelijk aan de gemiddelde hoeveelheid power vermenigvuldigd met de executie tijd
voor die workload. Het is bij vergelijken van efficiëntie dus belangrijk om naar energie
consumptie te kijken in plaats van power. Een voorbeeld hiervan: processor A heeft
een 20% hogere gemiddelde power consumptie dan processor B, maar A voert de taak
uit in 70% van de tijd die B voor die taak nodig heeft. De energie consumptie van A
voor die taak is dan 1, 20 × 0, 70 = 0, 84. Dat is overduidelijk beter.
De traditionale voornaamste energie consumptie in een CMOS chip bevindt zich in het
omzetten van transistoren. Dit noemen we de dynamic energie en heeft de volgende
formule:
Energydynamic = Capacitiveload × V oltage2
Deze formule geeft het energieverbruik voor een trilling van de vorm 0 → 1 → 0 of
1 → 0 → 1. Als we het energieverbruik voor een enkele trilling van de vorm 0 → 1 of
1 → 0 willen weten, dan is de formule:
1
Energydynamic = × Capacitiveload × V oltage2
2
De power die nodig is per transistor is simpelweg het product van de energie van een
transistor vermenigvuldig met de frequentie van transities:
1
P owerdynamic = × Capacitiveload × V oltage2 × F requency switches
2
8
, 1.8 Meten, rapporteren en samenvatten van
prestatie
We moeten altijd specificeren wat we bedoelen als we zeggen dat computer A sneller is
dan computer B. We kunnen bijvoorbeeld bedoelen dat de:
Throughput hoger ligt, dit is de totale hoeveelheid werk voltooid in een gegeven tijds-
bestek.
Response time/Execution time hoger ligt, dit is de tijd tussen het starten en voltooien
van een evenement.
Als we de performance van twee verschillende computers X en Y willen vergelijken kijken
we naar de execution time. We gebruiken hiervoor de volgende formule:
Execution timeY
=n
Execution timeX
We zeggen dan dat X n keer sneller is dan Y. De volgende relatie geldt dan:
1
Execution timeY Execution timeY Execution timeX
n= = =
Execution timeX 1 Execution timeY
Execution timeX
Maar hoe meten we dan deze execution time? Execution time kan op verschillende
manieren gedefinieerd worden afhankelijk van wat we wel en niet meer tellen. De meest
eenvoudige definitie van tijd is wall-clock time, response time of elapsed time. Bij
deze tijd zit echter ook de wachttijd op I/O inbegrepen, eveneens als de tijd dat het
proces neit actief is op de CPU en de CPU wat anders aan het doen is. CPU time
telt alleen de daadwerkelijke tijd dat de CPU aan het specifieke programma werkt. We
gebruiken benchmarks om performance te meten. De vraag is echter waarvan we dan
de execution time gaan meten. De beste keuze is van echte, representatieve applicaties.
Dit blijkt echter vaak lastig doordat de applicatie niet in de testomgeving past of niet op
de verschillende platformen draait die we met elkaar willen vergelijken.
Vaak zie je dat er eenvoudigere programma’s worden gebruikt.
Kernels: dit zijn kleine stukjes van echte programma’s. Een probleem met deze
methode is dat eventuele negatieve effectn van de code om het kleine stukje heen niet
worden meegenomen in de bechmark.
Toy programs: dit zijn kleine, simpele programma’s om snel wat te testen. Het
probleem van deze methode is dat het niet erg representatief is.
Synthetic benchmarks: programma’s die het gedrag van echte programma’s proberen
na te doen. Het probleem van deze methode is dat de compiler writer en de systeemar-
chitect optimalisaties uitvoeren voor deze benchmark en niet de echte programma’s.
De meest succesvolle standaard benchmark is de SPEC benchmark. Deze bestaan al
sinds de jaren 80 en bestaat uit een collectie van echte programma’s. Bijvoorbeeld de gcc
compiler, een schaakspel, videocompressie en quantum computer simulatie. Hier komt
vervolgens een score uit die relatief is aan een vastgestelde referentiemachine.
9
