Computer Organization and Design: The Hardware/Software Interface 5th Edition - With all appendices and advanced material

Front Cover......Page 1
Computer Organization and Design......Page 6
Copyright Page......Page 7
Acknowledgments......Page 9
Contents......Page 10
About This Book......Page 16
Changes for the Fifth Edition......Page 17
Concluding Remarks......Page 20
Acknowledgments for the Fifth Edition......Page 21
1 Computer Abstractions and Technology......Page 25
1.1 Introduction......Page 26
Classes of Computing Applications and Their Characteristics......Page 28
Welcome to the PostPC Era......Page 29
What You Can Learn in This Book......Page 30
Make the Common Case Fast......Page 34
Dependability via Redundancy......Page 35
1.3 Below Your Program......Page 36
From a High-Level Language to the Language of Hardware......Page 37
1.4 Under the Covers......Page 39
Through the Looking Glass......Page 41
Opening the Box......Page 42
A Safe Place for Data......Page 45
Communicating with Other Computers......Page 46
1.5 Technologies for Building Processors and Memory......Page 47
1.6 Performance......Page 51
Defining Performance......Page 52
Measuring Performance......Page 55
CPU Performance and Its Factors......Page 56
Instruction Performance......Page 58
The Classic CPU Performance Equation......Page 59
1.7 The Power Wall......Page 63
1.8 The Sea Change: The Switch from Uniprocessors to Multiprocessors......Page 66
SPEC CPU Benchmark......Page 69
SPEC Power Benchmark......Page 71
1.10 Fallacies and Pitfalls......Page 72
1.11 Concluding Remarks......Page 75
Road Map for This Book......Page 76
1.13 Exercises......Page 77
2 Instructions: Language of the Computer......Page 83
2.1 Introduction......Page 85
2.2 Operations of the Computer Hardware......Page 86
2.3 Operands of the Computer Hardware......Page 89
Memory Operands......Page 91
Constant or Immediate Operands......Page 95
2.4 Signed and Unsigned Numbers......Page 96
Summary......Page 102
2.5 Representing Instructions in the Computer......Page 103
MIPS Fields......Page 105
2.6 Logical Operations......Page 110
2.7 Instructions for Making Decisions......Page 113
Loops......Page 115
Case/Switch Statement......Page 118
2.8 Supporting Procedures in Computer Hardware......Page 119
Using More Registers......Page 121
Nested Procedures......Page 123
Allocating Space for New Data on the Stack......Page 126
Allocating Space for New Data on the Heap......Page 127
2.9 Communicating with People......Page 129
Characters and Strings in Java......Page 132
2.10 MIPS Addressing for 32-bit Immediates and Addresses......Page 134
32-Bit Immediate Operands......Page 135
Addressing in Branches and Jumps......Page 136
MIPS Addressing Mode Summary......Page 139
Decoding Machine Language......Page 141
2.11 Parallelism and Instructions: Synchronization......Page 144
Compiler......Page 146
Assembler......Page 147
Linker......Page 149
Dynamically Linked Libraries......Page 152
Starting a Java Program......Page 154
2.13 A C Sort Example to Put It All Together......Page 155
Code for the Body of the Procedure swap......Page 156
The Full swap Procedure......Page 157
Code for the Body of the Procedure sort......Page 158
The Procedure Call in sort......Page 160
The Full Procedure sort......Page 161
Array Version of Clear......Page 164
Pointer Version of Clear......Page 166
Comparing the Two Versions of Clear......Page 167
2.15 Advanced Material: Compiling C and Interpreting Java......Page 168
Addressing Modes......Page 194
Compare and Conditional Branch......Page 196
Unique Features of ARM......Page 197
Evolution of the Intel x86......Page 198
x86 Integer Operations......Page 201
x86 Instruction Encoding......Page 204
x86 Conclusion......Page 205
2.18 Real Stuff: ARMv8 (64-bit) Instructions......Page 207
2.19 Fallacies and Pitfalls......Page 208
2.20 Concluding Remarks......Page 210
2.21 Historical Perspective and Further Reading......Page 212
2.22 Exercises......Page 213
3 Arithmetic for Computers......Page 225
3.2 Addition and Subtraction......Page 227
Summary......Page 230
3.3 Multiplication......Page 232
Sequential Version of the Multiplication Algorithm and Hardware......Page 233
Faster Multiplication......Page 236
Summary......Page 237
A Division Algorithm and Hardware......Page 238
Signed Division......Page 241
Summary......Page 243
3.5 Floating Point......Page 245
Floating-Point Representation......Page 246
Floating-Point Addition......Page 252
Floating-Point Multiplication......Page 255
Floating-Point Instructions in MIPS......Page 260
Accurate Arithmetic......Page 267
Summary......Page 269
3.6 Parallelism and Computer Arithmetic: Subword Parallelism......Page 271
3.7 Real Stuff: Streaming SIMD Extensions and Advanced Vector Extensions in x86......Page 273
3.8 Going Faster: Subword Parallelism and Matrix Multiply......Page 274
3.9 Fallacies and Pitfalls......Page 278
3.10 Concluding Remarks......Page 281
3.11 Historical Perspective and Further Reading......Page 285
3.12 Exercises......Page 286
4 The Processor......Page 291
A Basic MIPS Implementation......Page 293
An Overview of the Implementation......Page 294
Clocking Methodology......Page 298
4.2 Logic Design Conventions......Page 297
4.3 Building a Datapath......Page 300
Creating a Single Datapath......Page 305
The ALU Control......Page 308
Designing the Main Control Unit......Page 310
Operation of the Datapath......Page 313
Finalizing Control......Page 318
Why a Single-Cycle Implementation Is Not Used Today......Page 320
4.5 An Overview of Pipelining......Page 321
Hazards......Page 326
Data Hazards......Page 327
Control Hazards......Page 330
Pipeline Overview Summary......Page 334
4.6 Pipelined Datapath and Control......Page 335
Graphically Representing Pipelines......Page 345
Pipelined Control......Page 349
4.7 Data Hazards: Forwarding versus Stalling......Page 352
Data Hazards and Stalls......Page 362
4.8 Control Hazards......Page 365
Reducing the Delay of Branches......Page 367
Dynamic Branch Prediction......Page 370
Pipeline Summary......Page 373
4.9 Exceptions......Page 374
How Exceptions Are Handled in the MIPS Architecture......Page 375
Exceptions in a Pipelined Implementation......Page 376
4.10 Parallelism via Instructions......Page 381
The Concept of Speculation......Page 382
Static Multiple Issue......Page 383
An Example: Static Multiple Issue with the MIPS ISA......Page 384
Dynamic Pipeline Scheduling......Page 388
Energy Efficiency and Advanced Pipelining......Page 392
4.11 Real Stuff: The ARM Cortex-A8 and Intel Core i7 Pipelines......Page 393
The ARM Cortex-A8......Page 394
The Intel Core i7 920......Page 395
Performance of the Intel Core i7 920......Page 398
4.12 Going Faster: Instruction-Level Parallelism and Matrix Multiply......Page 400
4.13 Advanced Topic: an Introduction to Digital Design Using a Hardware Design Language to Describe and Model a Pipeline and Mo…......Page 403
4.14 Fallacies and Pitfalls......Page 434
4.15 Concluding Remarks......Page 435
4.17 Exercises......Page 436
5 Large and Fast: Exploiting Memory Hierarchy......Page 451
5.1 Introduction......Page 453
5.2 Memory Technologies......Page 457
DRAM Technology......Page 458
Disk Memory......Page 460
5.3 The Basics of Caches......Page 462
Accessing a Cache......Page 465
Handling Cache Misses......Page 471
Handling Writes......Page 472
An Example Cache: The Intrinsity FastMATH Processor......Page 474
Summary......Page 476
5.4 Measuring and Improving Cache Performance......Page 477
Reducing Cache Misses by More Flexible Placement of Blocks......Page 481
Locating a Block in the Cache......Page 486
Choosing Which Block to Replace......Page 488
Reducing the Miss Penalty Using Multilevel Caches......Page 489
Software Optimization via Blocking......Page 492
Summary......Page 496
Defining Failure......Page 497
The Hamming Single Error Correcting, Double Error Detecting Code (SEC/DED)......Page 499
5.6 Virtual Machines......Page 503
(Lack of) Instruction Set Architecture Support for Virtual Machines......Page 505
5.7 Virtual Memory......Page 506
Placing a Page and Finding it Again......Page 510
Page Faults......Page 513
What about Writes?......Page 516
Making Address Translation Fast: the TLB......Page 517
Integrating Virtual Memory, TLBs, and Caches......Page 519
Implementing Protection with Virtual Memory......Page 523
Handling TLB Misses and Page Faults......Page 525
Summary......Page 531
5.8 A Common Framework for Memory Hierarchy......Page 533
Question 1: Where Can a Block Be Placed?......Page 534
Question 2: How is a Block Found?......Page 535
Question 4: What Happens on a Write?......Page 536
The Three Cs: An Intuitive Model for Understanding the Behavior of Memory Hierarchies......Page 538
A Simple Cache......Page 540
Finite-State Machines......Page 542
FSM for a Simple Cache Controller......Page 543
5.10 Parallelism and Memory Hierarchy: Cache Coherence......Page 545
Basic Schemes for Enforcing Coherence......Page 546
Snooping Protocols......Page 547
5.11 Parallelism and Memory Hierarchy: Redundant Arrays of Inexpensive Disks......Page 550
5.12 Advanced Material: Implementing Cache Controllers......Page 549
5.13 Real Stuff: The ARM Cortex-A8 and Intel Core i7 Memory Hierarchies......Page 557
Performance of the A8 and Core i7 Memory Hierarchies......Page 559
5.14 Going Faster: Cache Blocking and Matrix Multiply......Page 561
5.15 Fallacies and Pitfalls......Page 564
5.16 Concluding Remarks......Page 568
5.18 Exercises......Page 569
6 Parallel Processors from Client to Cloud......Page 586
6.1 Introduction......Page 588
6.2 The Difficulty of Creating Parallel Processing Programs......Page 590
6.3 SISD, MIMD, SIMD, SPMD, and Vector......Page 595
Vector......Page 596
Vector versus Scalar......Page 598
Vector versus Multimedia Extensions......Page 599
6.4 Hardware Multithreading......Page 602
6.5 Multicore and Other Shared Memory Multiprocessors......Page 605
6.6 Introduction to Graphics Processing Units......Page 610
An Introduction to the NVIDIA GPU Architecture......Page 611
NVIDIA GPU Memory Structures......Page 613
Putting GPUs into Perspective......Page 615
6.7 Clusters, Warehouse Scale Computers, and Other Message-Passing Multiprocessors......Page 617
Warehouse-Scale Computers......Page 619
6.8 Introduction to Multiprocessor Network Topologies......Page 622
Implementing Network Topologies......Page 624
6.9 Communicating to the Outside World: Cluster Networking......Page 625
6.10 Multiprocessor Benchmarks and Performance Models......Page 635
Performance Models......Page 637
The Roofline Model......Page 639
Comparing Two Generations of Opterons......Page 640
6.11 Real Stuff: Benchmarking and Rooflines of the Intel Core i7 960 and the NVIDIA Tesla GPU......Page 645
6.12 Going Faster: Multiple Processors and Matrix Multiply......Page 650
6.13 Fallacies and Pitfalls......Page 653
6.14 Concluding Remarks......Page 655
6.16 Exercises......Page 658
Appendix A: Assemblers, Linkers, and the SPIM Simulator......Page 671
A.1 Introduction......Page 672
A.2 Assemblers......Page 679
A.3 Linkers......Page 687
A.4 Loading......Page 688
A.5 Memory Usage......Page 689
A.6 Procedure Call Convention......Page 691
A.7 Exceptions and Interrupts......Page 702
A.8 Input and Output......Page 707
A.9 SPIM......Page 709
A.10 MIPS R2000 Assembly Language......Page 714
A.11 Concluding Remarks......Page 750
A.12 Exercises......Page 751
Appendix B: The Basics of Logic Design......Page 753
B.1 Introduction......Page 754
B.2 Gates, Truth Tables, and Logic Equations......Page 755
B.3 Combinational Logic......Page 760
B.4 Using a Hardware Description Language......Page 771
B.5 Constructing a Basic Arithmetic Logic Unit......Page 777
B.6 Faster Addition: Carry Lookahead......Page 789
B.7 Clocks......Page 799
B.8 Memory Elements: Flip-Flops, Latches, and Registers......Page 801
B.9 Memory Elements: SRAMs and DRAMs......Page 809
B.10 Finite-State Machines......Page 818
B.11 Timing Methodologies......Page 823
B.12 Field Programmable Devices......Page 829
B.13 Concluding Remarks......Page 830
B.14 Exercises......Page 831
Appendix C: 
Graphics and Computing GPUs......Page 839
 Appendix D: 
Mapping Control to Hardware......Page 921
 Appendix E:  A Survey of RISC Architectures for Desktop, Server, and Embedded Computers......Page 953
Index......Page 999