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