Computer Architecture: A Quantitative Approach

1  Fundamentals of Computer Design......Page 1
1.1  Introduction......Page 2
1.2  The Changing Face of Computing and the Task of the Computer Designer......Page 5
1.3  Technology Trends......Page 12
1.4 Cost, Price and their Trends......Page 15
1.5 Measuring and Reporting Performance......Page 26
1.6  Quantitative Principles of Computer Design......Page 41
1.7  Putting It All Together: Performance and Price-Performance......Page 50
1.8  Another View: Power Consumption and
 Efficiency as the Metric......Page 59
1.9  Fallacies and Pitfalls......Page 60
1.10  Concluding Remarks......Page 70
1.11  Historical Perspective and References......Page 71
E X E R C I S E S......Page 78
2 Instruction Set Principles and Examples......Page 87
2.1  Introduction......Page 88
2.2  Classifying Instruction Set Architectures......Page 90
2.3  Memory Addressing......Page 94
2.4  Addressing Modes for Signal Processing......Page 100
2.5  Type and Size of Operands......Page 103
2.6  Operands for Media and Signal Processing......Page 105
2.8  Operations for Media and Signal Processing......Page 107
2.9  Instructions for Control Flow......Page 111
2.10  Encoding an Instruction Set......Page 116
2.11  Crosscutting Issues: The Role of Compilers......Page 119
2.12  Putting It All Together: The MIPS Architecture......Page 129
2.13  Another View: The Trimedia TM32 CPU......Page 140
2.14  Fallacies and Pitfalls......Page 141
2.15  Concluding Remarks......Page 147
2.16  Historical Perspective and References......Page 149
E X E R C I S E S......Page 161
3  Instruction-Level Parallelism and its Dynamic Exploitation......Page 167
3.1  Instruction-Level Parallelism: Concepts and Challenges......Page 168
3.2  Overcoming Data Hazards with Dynamic Scheduling......Page 178
3.3  Dynamic Scheduling: Examples and the Algorithm......Page 186
3.4  Reducing Branch Costs with Dynamic Hardware Prediction......Page 194
3.5  High Performance Instruction Delivery......Page 208
3.6  Taking Advantage of More ILP with Multiple Issue......Page 215
3.7  Hardware-Based Speculation......Page 225
3.8  Studies of the Limitations of ILP......Page 241
3.9  Limitations on ILP for Realizable Processors......Page 256
3.10  Putting It All Together: The P6 Microarchitecture......Page 263
3.11  Another View: Thread Level Parallelism......Page 276
3.13  Fallacies and Pitfalls......Page 277
3.14  Concluding Remarks......Page 280
3.15  Historical Perspective and References......Page 284
E X E R C I S E S......Page 292
4  Exploiting Instruction Level Parallelism with Software Approaches......Page 301
4.1  Basic Compiler Techniques for Exposing ILP......Page 302
4.2  Static Branch Prediction......Page 312
4.3  Static Multiple Issue: the VLIW Approach......Page 315
4.4  Advanced Compiler Support for Exposing and Exploiting ILP......Page 319
4.5  Hardware Support for Exposing More Parallelism at Compile-Time......Page 341
4.6  Crosscutting Issues......Page 351
4.7  Putting It All Together: The Intel IA-64 Architecture and Itanium Processor......Page 352
4.8  Another View: ILP in the Embedded and Mobile Markets......Page 364
4.9  Fallacies and Pitfalls......Page 373
4.10  Concluding Remarks......Page 374
4.11  Historical Perspective and References......Page 376
E X E R C I S E S......Page 380
5  Memory-Hierarchy Design......Page 385
5.1  Introduction......Page 386
5.2  Review of the ABCs of Caches......Page 389
5.3  Cache Performance......Page 403
5.4  Reducing Cache Miss Penalty......Page 411
5.5  Reducing Miss Rate......Page 421
5.6  Reducing Cache Miss Penalty or Miss Rate via Parallelism......Page 434
5.7  Reducing Hit Time......Page 443
5.8  Main Memory and Organizations for Improving Performance......Page 448
5.9  Memory Technology......Page 455
5.10  Virtual Memory......Page 461
5.11  Protection and Examples of Virtual Memory......Page 470
5.12  Crosscutting Issues in the Design of Memory Hierarchies......Page 480
5.13  Putting It All Together: Alpha 21264 Memory Hierarchy......Page 484
5.14  Another View: The Emotion Engine of the Sony Playstation 2......Page 492
5.15  Another View: The Sun Fire 6800 Server......Page 496
5.16  Fallacies and Pitfalls......Page 501
5.17  Concluding Remarks......Page 508
5.18  Historical Perspective and References......Page 511
E X E R C I S E S......Page 517
6  Multiprocessors and Thread-Level Parallelism......Page 527
6.1  Introduction......Page 528
6.2  Characteristics of Application Domains......Page 542
6.3  Symmetric Shared-Memory Architectures......Page 551
6.4  Performance of Symmetric Shared-Memory Multiprocessors......Page 563
6.5  Distributed Shared-Memory Architectures......Page 580
6.6  Performance of Distributed Shared-Memory Multiprocessors......Page 590
6.7  Synchronization......Page 598
6.8  Models of Memory Consistency: An Introduction......Page 612
6.9  Multithreading: Exploiting Thread-Level Parallelism within a Processor......Page 616
6.10  Crosscutting Issues......Page 621
6.11  Putting It All Together: Sun’s Wildfire Prototype......Page 628
6.12  Another View: Multithreading in a Commercial Server......Page 643
6.13  Another View: Embedded Multiprocessors......Page 644
6.14  Fallacies and Pitfalls......Page 645
6.15  Concluding Remarks......Page 651
6.16  Historical Perspective and References......Page 658
E X E R C I S E S......Page 673
7  Storage Systems......Page 681
7.1  Introduction......Page 682
7.2  Types of Storage Devices......Page 684
7.3  Buses—Connecting I/O Devices to CPU/Memory......Page 697
7.4  Reliability, Availability, and Dependability......Page 706
7.5  RAID: Redundant Arrays of Inexpensive Disks......Page 711
7.6  Errors and Failures in Real Systems......Page 717
7.7  I/O Performance Measures......Page 721
7.8  A Little Queuing Theory......Page 727
7.9  Benchmarks of Storage Performance and Availability......Page 738
7.10  Crosscutting Issues......Page 744
7.11  Designing an I/O System in Five Easy Pieces......Page 749
7.12  Putting It All Together: EMC Symmetrix and Celerra......Page 762
7.13  Another View: Sanyo DSC-110 Digital Camera......Page 769
7.14  Fallacies and Pitfalls......Page 772
7.15  Concluding Remarks......Page 778
7.16  Historical Perspective and References......Page 779
E X E R C I S E S......Page 787
8  Interconnection Networks and Clusters 8......Page 793
8.1  Introduction......Page 794
8.2  A Simple Network......Page 801
8.3  Interconnection Network Media......Page 811
8.4  Connecting More Than Two Computers......Page 814
8.5  Network Topology......Page 823
8.6  Practical Issues for Commercial Interconnection Networks......Page 831
8.7  Examples of Interconnection Networks......Page 835
8.8  Internetworking......Page 841
8.9  Crosscutting Issues for Interconnection Networks......Page 846
8.10  Clusters......Page 850
8.11  Designing a Cluster......Page 855
8.12  Putting It All Together: The Goggle Cluster of PCs......Page 869
8.13  Another View: Inside a Cell Phone......Page 876
8.14 Fallacies and Pitfalls......Page 881
8.15  Concluding Remarks......Page 884
8.16 Historical Perspective and References......Page 885
E X E R C I S E S......Page 891
Appendix C:  A Survey of RISC Architectures for Desktop, Server, and Embedded Computers......Page 898
C1  Introduction......Page 899
C2  Addressing Modes and Instruction Formats......Page 901
C3  Instructions: The MIPS Core Subset......Page 902
C4  Instructions: Multimedia Extensions of the Desktop/ Server RISCs......Page 913
C5  Instructions: Digital Signal-Processing Extensions of the Embedded RISCs......Page 915
C6  Instructions: Common Extensions to MIPS Core......Page 916
C7 Instructions Unique to MIPS64......Page 921
C8  Instructions Unique to Alpha......Page 923
C9  Instructions Unique to SPARC v.9......Page 924
C10  Instructions Unique to PowerPC......Page 928
C11  Instructions Unique to PA-RISC 2.0......Page 929
C12  Instructions Unique to ARM......Page 932
C13  Instructions Unique to Thumb......Page 933
C14  Instructions Unique to SuperH......Page 934
C16  Instructions Unique to MIPS16......Page 935
C17  Concluding Remarks......Page 937
C18  Acknowledgments......Page 938
Appendix D:  An Alternative to RISC: The Intel 80x86......Page 943
D1  Introduction......Page 944
D2  80x86 Registers and Data Addressing Modes......Page 945
D3  80x86 Integer Operations......Page 948
D4  80x86 Floating-Point Operations......Page 952
D5  80x86 Instruction Encoding......Page 954
D6  Putting It All Together: Measurements of Instruction Set Usage......Page 956
D7  Concluding Remarks......Page 962
D8  Historical Perspective and References......Page 963
Appendix E:  Another Alternative to RISC: The VAX Architecture......Page 967
E2  VAX Operands and Addressing Modes......Page 968
E3  Encoding VAX Instructions......Page 971
E4  VAX Operations......Page 972
E5  An Example to Put It All Together: swap......Page 976
E6  A Longer Example: sort......Page 979
E7  Fallacies and Pitfalls......Page 984
E8  Concluding Remarks......Page 985
E9  Historical Perspective and Further Reading......Page 986
Exercises......Page 987
Appendix F:  The IBM 360/370 Architecture for Mainframe Computers......Page 990
F1  Introduction......Page 991
F2  System/360 Instruction Set......Page 992
F3  360 Detailed Measurements......Page 995
F4  Historical Perspective and References......Page 997
Appendix G:  Vector Processors......Page 999
G1  Why Vector Processors?......Page 1000
G2  Basic Vector Architecture......Page 1002
G3  Two Real-World Issues: Vector Length and Stride......Page 1014
G4  Enhancing Vector Performance......Page 1021
G5  Effectiveness of Compiler Vectorization......Page 1030
G6  Putting It All Together: Performance of Vector Processors......Page 1032
G7  Fallacies and Pitfalls......Page 1038
G8  Concluding Remarks......Page 1040
G9  Historical Perspective and References......Page 1041
Exercises......Page 1047
Appendix H:  Computer Arithmetic......Page 1054
H2  Basic Techniques of Integer Arithmetic......Page 1055
H3  Floating Point......Page 1066
H4  Floating-Point Multiplication......Page 1070
H5  Floating-Point Addition......Page 1074
H6  Division and Remainder......Page 1080
H7  More on Floating-Point Arithmetic......Page 1086
H8  Speeding Up Integer Addition......Page 1090
H9  Speeding Up Integer Multiplication and Division......Page 1098
H10  Putting It All Together......Page 1111
H11  Fallacies and Pitfalls......Page 1115
H12  Historical Perspective and References......Page 1116
Exercises......Page 1122
Appendix I:  Implementing Coherence Protocols......Page 1129
I1  Implementation Issues for the Snooping Coherence Protocol......Page 1130
I2  Implementation Issues in the Distributed Directory Protocol......Page 1134
Exercises......Page 1140