Computer Architecture : A Quantitative Approach

We said the fourth edition of Computer Architecture: A Quantitative Approach may have been the most significant since the first edition due to the switch to multicore chips. The feedback we received this time was that the book had lost the sharp focus of the first edition, covering everthing equally but without emphasis and context. We’re pretty sure that won’t be said about the fifth edition. We believe most of the excitement is at the extremes in size of computing, with personal mobile devices (PMDs) such as cell phones and tablets as the clients and warehouse-scale computers offering cloud computing as the server. (Observant readers may seen the hint for cloud computing on the cover.) We are struck by the common theme of these two extremes in cost, performance, and energy efficiency despite their difference in size. As a result, the running context through each chapter is computing for PMDs and for warehouse scale computers, and Chapter 6 is a brand-new chapter on the latter topic. The other theme is parallelism in all its forms. We first idetify the two types of application-level parallelism in Chapter 1: data-level parallelism (DLP), which arises because there are many data items that can be operated on at the same time, and task-level parallelism (TLP), which arises because tasks of work are created that can operate independently and largely in parallel. We then explain the four architectural styles that exploit DLP and TLP: instruction-level parallelism (ILP) in Chapter 3; vector architectures and graphic processor units (GPUs) in Chapter 4, which is a brand-new chapter for this edition; thread-level parallelism in Chapter 5; and request-level parallelism (RLP) via warehouse-scale computers in Chapter 6, which is also a brand-new chapter for this edition. We moved memory hierarchy earlier in the book to Chapter 2, and we moved the storage systems chapter to Appendix D. We are particularly proud about Chapter 4, which con- tains the most detailed and clearest explanation of GPUs yet, and Chapter 6, which is the first publication of the most recent details of a Google Warehouse- scale computer. 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 Computer Architecture: A Quantitative Approach explores the ways that software and technology in the cloud are accessed by digital media, such as cell phones, computers, tablets, and other mobile devices. The book became a part of Intel's 2012 recommended reading list for developers, and it covers the revolution of mobile computing. The text also highlights the two most important factors in architecture today: parallelism and memory hierarchy. The six chapters that this book is composed of follow a consistent framework: explanation of the ideas in each chapter; a''crosscutting issues''section, which presents how the concepts covered in one chapter connect with those given in other chapters; a''putting it all together''section that links these concepts by discussing how they are applied in real machine; and detailed examples of misunderstandings and architectural traps commonly encountered by developers and architects. The first chapter of the book includes formulas for energy, static and dynamic power, integrated circuit costs, reliability, and availability. Chapter 2 discusses memory hierarchy and includes discussions about virtual machines, SRAM and DRAM technologies, and new material on Flash memory. The third chapter covers the exploitation of instruction-level parallelism in high-performance processors, superscalar execution, dynamic scheduling and multithreading, followed by an introduction to vector architectures in the fourth chapter. Chapters 5 and 6 describe multicore processors and warehouse-scale computers (WSCs), respectively. This book is an important reference for computer architects, programmers, application developers, compiler and system software developers, computer system designers and application developers.Part of Intel's 2012 Recommended Reading List for DevelopersUpdated to cover the mobile computing revolutionEmphasizes the two most important topics in architecture today: memory hierarchy and parallelism in all its forms.Develops common themes throughout each chapter: power, performance, cost, dependability, protection, programming models, and emerging trends ('What's Next')Includes three review appendices in the printed text. Additional reference appendices are available online.Includes updated Case Studies and completely new exercises. Computer Architecture: A Quantitative Approach explores the ways that software and technology in the cloud are accessed by digital media, such as cell phones, computers, tablets, and other mobile devices. The book became a part of Intel's 2012 recommended reading list for developers, and it covers the revolution of mobile computing. The text also highlights the two most important factors in architecture today: parallelism and memory hierarchy. The six chapters that this book is composed of follow a consistent framework: explanation of the ideas in each chapter; a "crosscutting issues" section, which presents how the concepts covered in one chapter connect with those given in other chapters; a "putting it all together" section that links these concepts by discussing how they are applied in real machine; and detailed examples of misunderstandings and architectural traps commonly encountered by developers and architects. The first chapter of the book includes formulas for energy, static and dynamic power, integrated circuit costs, reliability, and availability. Chapter 2 discusses memory hierarchy and includes discussions about virtual machines, SRAM and DRAM technologies, and new material on Flash memory. The third chapter covers the exploitation of instruction-level parallelism in high-performance processors, superscalar execution, dynamic scheduling and multithreading, followed by an introduction to vector architectures in the fourth chapter. Chapters 5 and 6 describe multicore processors and warehouse-scale computers (WSCs), respectively. This book is an important reference for computer architects, programmers, application developers, compiler and system software developers, computer system designers and application developers. Fully updated fifth edition covers the twin shifts to mobile and cloud computing, with new material, exercises, and case studies.--Publisher website

The computing world today is in the middle of a revolution: mobile clients and cloud computing have emerged as the dominant paradigms driving programming and hardware innovation today. The Fifth Edition of Computer Architecture focuses on this dramatic shift, exploring the ways in which software and technology in the cloud are accessed by cell phones, tablets, laptops, and other mobile computing devices. Each chapter includes two real-world examples, one mobile and one datacenter, to illustrate this revolutionary change.

• Part of Intel's 2012 Recommended Reading List for Developers
• Updated to cover the mobile computing revolution
• Emphasizes the two most important topics in architecture today: memory hierarchy and parallelism in all its forms.
• Develops common themes throughout each chapter: power, performance, cost, dependability, protection, programming models, and emerging trends ("What's Next")
• Includes three review appendices in the printed text. Additional reference appendices are available online.
• Includes updated Case Studies and completely new exercises.

The computing world today is in the middle of a revolution: mobile clients and cloud computing have emerged as the dominant paradigms driving programming and hardware innovation today. The Fifth Edition of "Computer Architecture" focuses on this dramatic shift, exploring the ways in which software and technology in the 'cloud' are accessed by cell phones, tablets, laptops, and other mobile computing devices. Each chapter includes two real-world examples, one mobile and one datacenter, to illustrate this revolutionary change. It is updated to cover the mobile computing revolution. It emphasizes the two most important topics in architecture today: memory hierarchy and parallelism in all its forms. It develops common themes throughout each chapter: power, performance, cost, dependability, protection, programming models, and emerging trends ('What's Next'). It includes three review appendices in the printed text. Additional reference appendices are available online. It includes updated Case Studies and completely new exercises