Computer Architecture: A Quantitative Approach

Front Cover......Page 1
In Praise of Computer Architecture: A Quantitative ApproachFifth Edition......Page 2
Computer Architecture: A Quantitative Approach......Page 6
Copyright......Page 7
Dedication......Page 8
Foreword......Page 10
Table of Contents......Page 12
Why We Wrote This Book......Page 16
This Edition......Page 17
An Overview of the Content......Page 18
Navigating the Text......Page 20
Supplemental Materials......Page 21
Concluding Remarks......Page 22
Advisory Panel......Page 24
Additional Material......Page 25
Reviewers......Page 26
Case Studies with Exercises......Page 27
Special Thanks......Page 28
1 Fundamentals of Quantitative Design and Analysis......Page 30
1.1 Introduction......Page 31
1.2 Classes of Computers......Page 34
Desktop Computing......Page 35
Servers......Page 36
Embedded Computers......Page 37
Classes of Parallelism and Parallel Architectures......Page 38
Instruction Set Architecture: The Myopic View of Computer Architecture......Page 40
Genuine Computer Architecture: Designing the Organization and Hardware to Meet Goals and Functional Requirements......Page 44
1.4 Trends in Technology......Page 46
Performance Trends: Bandwidth over Latency......Page 47
Scaling of Transistor Performance and Wires......Page 48
Power and Energy: A Systems Perspective......Page 50
Energy and Power within a Microprocessor......Page 52
The Impact of Time, Volume, and Commoditization......Page 56
Cost of an Integrated Circuit......Page 57
Cost versus Price......Page 61
1.7 Dependability......Page 62
1.8 Measuring, Reporting, and Summarizing Performance......Page 65
Benchmarks......Page 66
Desktop Benchmarks......Page 67
Server Benchmarks......Page 69
Summarizing Performance Results......Page 70
Take Advantage of Parallelism......Page 73
Focus on the Common Case......Page 74
Amdahl’s Law......Page 75
The Processor Performance Equation......Page 77
1.10 Putting It All Together: Performance, Price, and Power......Page 81
1.11 Fallacies and Pitfalls......Page 84
1.12 Concluding Remarks......Page 88
Concepts illustrated by this case study......Page 90
Concepts illustrated by this case study......Page 92
Exercises......Page 94
2 Memory Hierarchy Design......Page 100
2.1 Introduction......Page 0
Basics of Memory Hierarchies: A Quick Review......Page 103
2.2 Ten Advanced Optimizations of Cache Performance......Page 107
First Optimization: Small and Simple First-Level Caches to Reduce Hit Time and Power......Page 108
Second Optimization: Way Prediction to Reduce Hit Time......Page 110
Third Optimization: Pipelined Cache Access to Increase Cache Bandwidth......Page 111
Fourth Optimization: Nonblocking Caches to Increase Cache Bandwidth......Page 112
Fifth Optimization: Multibanked Caches to Increase Cache Bandwidth......Page 114
Sixth Optimization: Critical Word First and Early Restart to Reduce Miss Penalty......Page 115
Eighth Optimization: Compiler Optimizations to Reduce Miss Rate......Page 116
Loop Interchange......Page 117
Blocking......Page 118
Ninth Optimization: Hardware Prefetching of Instructions and Data to Reduce Miss Penalty or Miss Rate......Page 120
Tenth Optimization: Compiler-Controlled Prefetching to Reduce Miss Penalty or Miss Rate......Page 121
Cache Optimization Summary......Page 124
2.3 Memory Technology and Optimizations......Page 125
SRAM Technology......Page 126
DRAM Technology......Page 127
Improving Memory Performance Inside a DRAM Chip......Page 129
Flash Memory......Page 131
Enhancing Dependability in Memory Systems......Page 133
Protection via Virtual Memory......Page 134
Protection via Virtual Machines......Page 136
Requirements of a Virtual Machine Monitor......Page 137
(Lack of) Instruction Set Architecture Support for Virtual Machines......Page 138
Impact of Virtual Machines on Virtual Memory and I/O......Page 139
An Example VMM: The Xen Virtual Machine......Page 140
Coherency of Cached Data......Page 141
2.6 Putting It All Together: Memory Hierachies in the ARM Cortex-A8 and Intel Core i7......Page 142
The ARM Cortex-A8......Page 143
Performance of the Cortex-A8 Memory Hierarchy......Page 144
The Intel Core i7......Page 146
Performance of the i7 Memory System......Page 151
2.7 Fallacies and Pitfalls......Page 154
2.8 Concluding Remarks: Looking Ahead......Page 158
Concepts illustrated by this case study......Page 160
Concept illustrated by this case study......Page 162
Exercises......Page 165
3 Instruction-Level Parallelism and Its Exploitation......Page 176
3.1 Instruction-Level Parallelism: Concepts and Challenges......Page 177
What Is Instruction-Level Parallelism?......Page 178
Data Dependences......Page 179
Name Dependences......Page 181
Data Hazards......Page 182
Control Dependences......Page 183
3.2 Basic Compiler Techniques for Exposing ILP......Page 185
Basic Pipeline Scheduling and Loop Unrolling......Page 186
Summary of the Loop Unrolling and Scheduling......Page 190
Correlating Branch Predictors......Page 191
Tournament Predictors: Adaptively Combining Local and Global Predictors......Page 193
The Intel Core i7 Branch Predictor......Page 195
3.4 Overcoming Data Hazards with Dynamic Scheduling......Page 196
Dynamic Scheduling: The Idea......Page 197
Dynamic Scheduling Using Tomasulo’s Approach......Page 199
3.5 Dynamic Scheduling: Examples and the Algorithm......Page 205
Tomasulo’s Algorithm: The Details......Page 207
Tomasulo’s Algorithm: A Loop-Based Example......Page 208
3.6 Hardware-Based Speculation......Page 212
3.7 Exploiting ILP Using Multiple Issue and Static Scheduling......Page 221
The Basic VLIW Approach......Page 222
3.8 Exploiting ILP Using Dynamic Scheduling, Multiple Issue, and Speculation......Page 226
Increasing Instruction Fetch Bandwidth......Page 231
Branch-Target Buffers......Page 232
Return Address Predictors......Page 235
Integrated Instruction Fetch Units......Page 236
Speculation Support: Register Renaming versus Reorder Buffers......Page 237
How Much to Speculate......Page 239
Speculation and the Challenge of Energy Efficiency......Page 240
Value Prediction......Page 241
3.10 Studies of the Limitations of ILP......Page 242
The Hardware Model......Page 243
Limitations on ILP for Realizable Processors......Page 245
Beyond the Limits of This Study......Page 248
Hardware versus Software Speculation......Page 250
Speculative Execution and the Memory System......Page 251
3.12 Multithreading: Exploiting Thread-Level Parallelism to Improve Uniprocessor Throughput......Page 252
Effectiveness of Fine-Grained Multithreading on the Sun T1......Page 255
T1 Multithreading Unicore Performance......Page 256
Effectiveness of Simultaneous Multithreading on Superscalar Processors......Page 259
Performance of the A8 Pipeline......Page 262
The Intel Core i7......Page 265
Performance of the i7......Page 268
3.14 Fallacies and Pitfalls......Page 270
3.15 Concluding Remarks: What’s Ahead?......Page 274
Concepts illustrated by this case study......Page 276
Exercises......Page 283
4 Data-Level Parallelism in Vector, SIMD, and GPU Architectures......Page 290
4.1 Introduction......Page 291
VMIPS......Page 293
How Vector Processors Work: An Example......Page 296
Vector Execution Time......Page 297
Multiple Lanes: Beyond One Element per Clock Cycle......Page 300
Vector-Length Registers: Handling Loops Not Equal to 64......Page 303
Vector Mask Registers: Handling IF Statements in Vector Loops......Page 304
Memory Banks: Supplying Bandwidth for Vector Load/Store Units......Page 305
Stride: Handling Multidimensional Arrays in Vector Architectures......Page 307
Gather-Scatter: Handling Sparse Matrices in Vector Architectures......Page 308
Programming Vector Architectures......Page 309
4.3 SIMD Instruction Set Extensions for Multimedia......Page 311
The Roofline Visual Performance Model......Page 314
Programming the GPU......Page 317
NVIDIA GPU Computational Structures......Page 320
NVIDA GPU Instruction Set Architecture......Page 327
Conditional Branching in GPUs......Page 329
NVIDIA GPU Memory Structures......Page 333
Innovations in the Fermi GPU Architecture......Page 334
Similarities and Differences between Vector Architectures and GPUs......Page 337
Similarities and Differences between Multimedia SIMD Computers and GPUs......Page 341
Summary......Page 342
4.5 Detecting and Enhancing Loop-Level Parallelism......Page 344
Finding Dependences......Page 347
Eliminating Dependent Computations......Page 350
Banked Memory and Graphics Memory......Page 351
4.7 Putting It All Together: Mobile versus Server GPUs and Tesla versus Core i7......Page 352
4.8 Fallacies and Pitfalls......Page 359
4.9 Concluding Remarks......Page 361
Concepts illustrated by this case study......Page 363
Exercises......Page 366
5 Thread-Level Parallelism......Page 372
5.1 Introduction......Page 373
Multiprocessor Architecture: Issues and Approach......Page 375
Challenges of Parallel Processing......Page 378
5.2 Centralized Shared-Memory Architectures......Page 380
What Is Multiprocessor Cache Coherence?......Page 381
Basic Schemes for Enforcing Coherence......Page 383
Snooping Coherence Protocols......Page 384
Basic Implementation Techniques......Page 385
An Example Protocol......Page 386
Extensions to the Basic Coherence Protocol......Page 391
Limitations in Symmetric Shared-Memory Multiprocessors and Snooping Protocols......Page 392
Implementing Snooping Cache Coherence......Page 394
5.3 Performance of Symmetric Shared-Memory Multiprocessors......Page 395
A Commercial Workload......Page 396
Performance Measurements of the Commercial Workload......Page 398
A Multiprogramming and OS Workload......Page 403
Performance of the Multiprogramming and OS Workload......Page 404
5.4 Distributed Shared-Memory and Directory-Based Coherence......Page 407
Directory-Based Cache Coherence Protocols: The Basics......Page 409
An Example Directory Protocol......Page 411
5.5 Synchronization: The Basics......Page 415
Basic Hardware Primitives......Page 416
Implementing Locks Using Coherence......Page 418
5.6 Models of Memory Consistency: An Introduction......Page 421
The Programmer’s View......Page 422
Relaxed Consistency Models: The Basics......Page 423
5.7 Crosscutting Issues......Page 424
Using Speculation to Hide Latency in Strict Consistency Models......Page 425
Inclusion and Its Implementation......Page 426
Performance Gains from Using Multiprocessing and Multithreading......Page 427
5.8 Putting It All Together: Multicore Processors and Their Performance......Page 429
Performance and Energy Efficiency of the Intel Core i7 Multicore......Page 430
Putting Multicore and SMT Together......Page 433
5.9 Fallacies and Pitfalls......Page 434
5.10 Concluding Remarks......Page 438
Concepts illustrated by this case study......Page 441
Concepts illustrated by this case study......Page 447
Concepts illustrated by this case study......Page 449
Exercises......Page 455
6 Warehouse-Scale Computers to Exploit Request-Level and Data-Level Parallelism......Page 460
6.1 Introduction......Page 461
6.2 Programming Models and Workloads for Warehouse-Scale Computers......Page 465
6.3 Computer Architecture of Warehouse-Scale Computers......Page 470
Storage......Page 471
WSC Memory Hierarchy......Page 472
6.4 Physical Infrastructure and Costs of Warehouse-Scale Computers......Page 475
Measuring Efficiency of a WSC......Page 479
Cost of a WSC......Page 481
6.5 Cloud Computing: The Return of Utility Computing......Page 484
Amazon Web Services......Page 485
WSC Network as a Bottleneck......Page 490
Using Energy Efficiently Inside the Server......Page 491
Containers......Page 493
Cooling and Power in the Google WSC......Page 494
Servers in a Google WSC......Page 497
Monitoring and Repair in a Google WSC......Page 498
Summary......Page 499
6.8 Fallacies and Pitfalls......Page 500
6.9 Concluding Remarks......Page 504
Concepts illustrated by this case study......Page 505
Concepts illustrated by this case study......Page 507
Exercises......Page 508
Appendix A. Instruction Set Principles......Page 524
A.1 Introduction......Page 525
A.2 Classifying Instruction Set Architectures......Page 526
Summary: Classifying Instruction Set Architectures......Page 529
Interpreting Memory Addresses......Page 530
Addressing Modes......Page 532
Immediate or Literal Addressing Mode......Page 533
Summary: Memory Addressing......Page 534
A.4 Type and Size of Operands......Page 536
A.5 Operations in the Instruction Set......Page 537
A.6 Instructions for Control Flow......Page 539
Addressing Modes for Control Flow Instructions......Page 540
Procedure Invocation Options......Page 542
Summary: Instructions for Control Flow......Page 543
A.7 Encoding an Instruction Set......Page 544
Reduced Code Size in RISCs......Page 546
The Structure of Recent Compilers......Page 547
Register Allocation......Page 549
The Impact of Compiler Technology on the Architect’s Decisions......Page 550
How the Architect Can Help the Compiler Writer......Page 552
Compiler Support (or Lack Thereof) for Multimedia Instructions......Page 554
A.9 Putting It All Together: The MIPS Architecture......Page 555
Addressing Modes for MIPS Data Transfers......Page 557
MIPS Operations......Page 558
MIPS Control Flow Instructions......Page 560
MIPS Floating-Point Operations......Page 561
A.10 Fallacies and Pitfalls......Page 562
A.11 Concluding Remarks......Page 568
Exercises by Gregory D. Peterson......Page 570
Appendix B. Review of Memory Hierarchy......Page 580
B.1 Introduction......Page 581
Cache Performance Review......Page 582
Four Memory Hierarchy Questions......Page 585
An Example: The Opteron Data Cache......Page 591
B.2 Cache Performance......Page 595
Average Memory Access Time and Processor Performance......Page 596
Miss Penalty and Out-of-Order Execution Processors......Page 599
B.3 Six Basic Cache Optimizations......Page 601
First Optimization: Larger Block Size to Reduce Miss Rate......Page 605
Third Optimization: Higher Associativity to Reduce Miss Rate......Page 607
Fourth Optimization: Multilevel Caches to Reduce Miss Penalty......Page 609
Fifth Optimization: Giving Priority to Read Misses over Writes to Reduce Miss Penalty......Page 614
Sixth Optimization: Avoiding Address Translation during Indexing of the Cache to Reduce Hit Time......Page 615
B.4 Virtual Memory......Page 619
Four Memory Hierarchy Questions Revisited......Page 623
Selecting a Page Size......Page 625
Summary of Virtual Memory and Caches......Page 627
B.5 Protection and Examples of Virtual Memory......Page 628
Protecting Processes......Page 629
A Segmented Virtual Memory Example: Protection in the Intel Pentium......Page 630
Adding Sharing and Protection......Page 631
A Paged Virtual Memory Example: The 64-Bit Opteron Memory Management......Page 633
B.6 Fallacies and Pitfalls......Page 636
B.8 Historical Perspective and References......Page 638
Exercises by Amr Zaky......Page 639
Appendix C. Pipelining: Basic and Intermediate Concepts......Page 648
What Is Pipelining?......Page 649
The Basics of a RISC Instruction Set......Page 651
A Simple Implementation of a RISC Instruction Set......Page 652
The Classic Five-Stage Pipeline for a RISC Processor......Page 653
Basic Performance Issues in Pipelining......Page 657
C.2 The Major Hurdle of Pipelining—Pipeline Hazards......Page 658
Performance of Pipelines with Stalls......Page 659
Structural Hazards......Page 660
Minimizing Data Hazard Stalls by Forwarding......Page 663
Data Hazards Requiring Stalls......Page 666
Branch Hazards......Page 668
Reducing Pipeline Branch Penalties......Page 669
Performance of Branch Schemes......Page 672
Static Branch Prediction......Page 673
Dynamic Branch Prediction and Branch-Prediction Buffers......Page 674
C.3 How Is Pipelining Implemented?......Page 677
A Simple Implementation of MIPS......Page 678
A Basic Pipeline for MIPS......Page 681
Implementing the Control for the MIPS Pipeline......Page 683
Dealing with Branches in the Pipeline......Page 686
Types of Exceptions and Requirements......Page 690
Stopping and Restarting Execution......Page 693
Exceptions in MIPS......Page 695
Instruction Set Complications......Page 696
C.5 Extending the MIPS Pipeline to Handle Multicycle Operations......Page 698
Hazards and Forwarding in Longer Latency Pipelines......Page 701
Maintaining Precise Exceptions......Page 705
Performance of a MIPS FP Pipeline......Page 707
C.6 Putting It All Together: The MIPS R4000 Pipeline......Page 708
The Floating-Point Pipeline......Page 712
Performance of the R4000 Pipeline......Page 714
Dynamically Scheduled Pipelines......Page 717
Dynamic Scheduling with a Scoreboard......Page 718
C.8 Fallacies and Pitfalls......Page 727
C.10 Historical Perspective and References......Page 728
Updated Exercises by Diana Franklin......Page 729
Appendix D: Storage Systems......Page 858
Appendix E: Embedded Systems by Thomas M. Conte
......Page 926
Appendix F: Interconnection Networks updated by Timothy M. Pinkston and José Duato......Page 953
Appendix G: Vector Processors by Krste Asanovic......Page 1071
Appendix H: Hardware and Software for VLIW and EPIC......Page 1106
Appendix I: Large-Scale Multiprocessors and Scientific Applications......Page 1151
Appendix J: Computer Arithmetic by David Goldberg......Page 1198
Appendix K: Survey of Instruction Set Architectures......Page 1272
References......Page 736
A......Page 768
B......Page 772
C......Page 775
D......Page 784
E......Page 789
F......Page 793
G......Page 795
H......Page 797
I......Page 798
L......Page 807
M......Page 810
N......Page 818
O......Page 819
P......Page 821
R......Page 828
S......Page 832
T......Page 842
V......Page 846
W......Page 849
Z......Page 851
Translation between GPU terms in book and official NVIDIA and OpenCL terms......Page 857