Computer Organization and Design, Fifth Edition: The Hardware/Software Interface

The 5th edition of __Computer Organization and Design__ moves forward into the post-PC era with new examples, exercises, and material highlighting the emergence of mobile computing and the cloud. This generational change is emphasized and explored with updated content featuring tablet computers, cloud infrastructure, and the ARM (mobile computing devices) and x86 (cloud computing) architectures. Because an understanding of modern hardware is essential to achieving good performance and energy efficiency, this edition adds a new concrete example, "Going Faster," used throughout the text to demonstrate extremely effective optimization techniques. Also new to this edition is discussion of the "Eight Great Ideas" of computer architecture. As with previous editions, a MIPS processor is the core used to present the fundamentals of hardware technologies, assembly language, computer arithmetic, pipelining, memory hierarchies and I/O. Instructors looking for 4th Edition teaching materials should e-mail textbook@elsevier.com. * Includes new examples, exercises, and material highlighting the emergence of mobile computing and the Cloud. * Covers parallelism in depth with examples and content highlighting parallel hardware and software topics * Features the Intel Core i7, ARM Cortex-A8 and NVIDIA Fermi GPU as real-world examples throughout the book * Adds a new concrete example, "Going Faster," to demonstrate how understanding hardware can inspire software optimizations that improve performance by 200 times. * Discusses and highlights the "Eight Great Ideas" of computer architecture: Performance via Parallelism; Performance via Pipelining; Performance via Prediction; Design for Moore's Law; Hierarchy of Memories; Abstraction to Simplify Design; Make the Common Case Fast; and Dependability via Redundancy. * Includes a full set of updated and improved exercises. Computer Organization and Design: The Hardware/Software Interface, Fifth Edition (2014) 793pp. 978-0-12-407726-3 Front Cover 1 Computer Organization and Design 6 Copyright Page 7 Acknowledgments 9 Contents 10 Preface 16 About This Book 16 About the Other Book 17 Changes for the Fifth Edition 17 Changes for the Fifth Edition 20 Concluding Remarks 20 Acknowledgments for the Fifth Edition 21 1 Computer Abstractions and Technology 25 1.1 Introduction 26 Classes of Computing Applications and Their Characteristics 28 Welcome to the PostPC Era 29 What You Can Learn in This Book 30 1.2 Eight Great Ideas in Computer Architecture 34 Design for Moore’s Law 34 Use Abstraction to Simplify Design 34 Make the Common Case Fast 34 Performance via Parallelism 35 Performance via Pipelining 35 Performance via Prediction 35 Hierarchy of Memories 35 Dependability via Redundancy 35 1.3 Below Your Program 36 From a High-Level Language to the Language of Hardware 37 1.4 Under the Covers 39 Through the Looking Glass 41 Touchscreen 42 Opening the Box 42 A Safe Place for Data 45 Communicating with Other Computers 46 1.5 Technologies for Building Processors and Memory 47 1.6 Performance 51 Defining Performance 52 Measuring Performance 55 CPU Performance and Its Factors 56 Instruction Performance 58 The Classic CPU Performance Equation 59 1.7 The Power Wall 63 1.8 The Sea Change: The Switch from Uniprocessors to Multiprocessors 66 1.9 Real Stuff: Benchmarking the Intel Core i7 69 SPEC CPU Benchmark 69 SPEC Power Benchmark 71 1.10 Fallacies and Pitfalls 72 1.11 Concluding Remarks 75 Road Map for This Book 76 1.12 Historical Perspective and Further Reading 77 1.13 Exercises 77 2 Instructions: Language of the Computer 83 2.1 Introduction 85 2.2 Operations of the Computer Hardware 86 2.3 Operands of the Computer Hardware 89 Memory Operands 91 Constant or Immediate Operands 95 2.4 Signed and Unsigned Numbers 96 Summary 102 2.5 Representing Instructions in the Computer 103 MIPS Fields 105 2.6 Logical Operations 110 2.7 Instructions for Making Decisions 113 Loops 115 Case/Switch Statement 118 2.8 Supporting Procedures in Computer Hardware 119 Using More Registers 121 Nested Procedures 123 Allocating Space for New Data on the Stack 126 Allocating Space for New Data on the Heap 127 2.9 Communicating with People 129 Characters and Strings in Java 132 2.10 MIPS Addressing for 32-bit Immediates and Addresses 134 32-Bit Immediate Operands 135 Addressing in Branches and Jumps 136 MIPS Addressing Mode Summary 139 Decoding Machine Language 141 2.11 Parallelism and Instructions: Synchronization 144 2.12 Translating and Starting a Program 146 Compiler 146 Assembler 147 Linker 149 Loader 152 Dynamically Linked Libraries 152 Starting a Java Program 154 2.13 A C Sort Example to Put It All Together 155 The Procedure swap 156 Register Allocation for swap 156 Code for the Body of the Procedure swap 156 The Full swap Procedure 157 The Procedure sort 158 Register Allocation for sort 158 Code for the Body of the Procedure sort 158 The Procedure Call in sort 160 Passing Parameters in sort 161 Preserving Registers in sort 161 The Full Procedure sort 161 2.14 Arrays versus Pointers 164 Array Version of Clear 164 Pointer Version of Clear 166 Comparing the Two Versions of Clear 167 2.15 Advanced Material: Compiling C and Interpreting Java 168 2.16 Real Stuff: ARMv7 (32-bit) Instructions 168 Addressing Modes 168 Compare and Conditional Branch 170 Unique Features of ARM 171 2.17 Real Stuff: x86 Instructions 172 Evolution of the Intel x86 172 x86 Registers and Data Addressing Modes 175 x86 Integer Operations 175 x86 Instruction Encoding 178 x86 Conclusion 179 2.18 Real Stuff: ARMv8 (64-bit) Instructions 181 2.19 Fallacies and Pitfalls 182 2.20 Concluding Remarks 184 2.21 Historical Perspective and Further Reading 186 2.22 Exercises 187 3 Arithmetic for Computers 199 3.1 Introduction 201 3.2 Addition and Subtraction 201 Summary 204 3.3 Multiplication 206 Sequential Version of the Multiplication Algorithm and Hardware 207 Signed Multiplication 210 Faster Multiplication 210 Multiply in MIPS 211 Summary 211 3.4 Division 212 A Division Algorithm and Hardware 212 Signed Division 215 Faster Division 217 Divide in MIPS 217 Summary 217 3.5 Floating Point 219 Floating-Point Representation 220 Floating-Point Addition 226 Floating-Point Multiplication 229 Floating-Point Instructions in MIPS 234 Accurate Arithmetic 241 Summary 243 3.6 Parallelism and Computer Arithmetic: Subword Parallelism 245 3.7 Real Stuff: Streaming SIMD Extensions and Advanced Vector Extensions in x86 247 3.8 Going Faster: Subword Parallelism and Matrix Multiply 248 3.9 Fallacies and Pitfalls 252 3.10 Concluding Remarks 255 3.11 Historical Perspective and Further Reading 259 3.12 Exercises 260 4 The Processor 265 4.1 Introduction 267 A Basic MIPS Implementation 267 An Overview of the Implementation 268 Clocking Methodology 272 4.2 Logic Design Conventions 271 4.3 Building a Datapath 274 Creating a Single Datapath 279 4.4 A Simple Implementation Scheme 282 The ALU Control 282 Designing the Main Control Unit 284 Operation of the Datapath 287 Finalizing Control 292 Why a Single-Cycle Implementation Is Not Used Today 294 4.5 An Overview of Pipelining 295 Designing Instruction Sets for Pipelining 300 Pipeline Hazards 300 Hazards 300 Data Hazards 301 Control Hazards 304 Pipeline Overview Summary 308 4.6 Pipelined Datapath and Control 309 Graphically Representing Pipelines 319 Pipelined Control 323 4.7 Data Hazards: Forwarding versus Stalling 326 Data Hazards and Stalls 336 4.8 Control Hazards 339 Assume Branch Not Taken 341 Reducing the Delay of Branches 341 Dynamic Branch Prediction 344 Pipeline Summary 347 4.9 Exceptions 348 How Exceptions Are Handled in the MIPS Architecture 349 Exceptions in a Pipelined Implementation 350 4.10 Parallelism via Instructions 355 The Concept of Speculation 356 Static Multiple Issue 357 An Example: Static Multiple Issue with the MIPS ISA 358 Dynamic Multiple-Issue Processors 362 Dynamic Pipeline Scheduling 362 Energy Efficiency and Advanced Pipelining 366 4.11 Real Stuff: The ARM Cortex-A8 and Intel Core i7 Pipelines 367 The ARM Cortex-A8 368 The Intel Core i7 920 369 Performance of the Intel Core i7 920 372 4.12 Going Faster: Instruction-Level Parallelism and Matrix Multiply 374 4.13 Advanced Topic: an Introduction to Digital Design Using a Hardware Design Language to Describe and Model a Pipeline and Mo... 377 4.14 Fallacies and Pitfalls 378 4.15 Concluding Remarks 379 4.16 Historical Perspective and Further Reading 380 4.17 Exercises 380 5 Large and Fast: Exploiting Memory Hierarchy 395 5.1 Introduction 397 5.2 Memory Technologies 401 SRAM Technology 402 DRAM Technology 402 Flash Memory 404 Disk Memory 404 5.3 The Basics of Caches 406 Accessing a Cache 409 Handling Cache Misses 415 Handling Writes 416 An Example Cache: The Intrinsity FastMATH Processor 418 Summary 420 5.4 Measuring and Improving Cache Performance 421 Reducing Cache Misses by More Flexible Placement of Blocks 425 Locating a Block in the Cache 430 Choosing Which Block to Replace 432 Reducing the Miss Penalty Using Multilevel Caches 433 Software Optimization via Blocking 436 Summary 440 5.5 Dependable Memory Hierarchy 441 Defining Failure 441 The Hamming Single Error Correcting, Double Error Detecting Code (SEC/DED) 443 5.6 Virtual Machines 447 Requirements of a Virtual Machine Monitor 449 (Lack of) Instruction Set Architecture Support for Virtual Machines 449 Protection and Instruction Set Architecture 450 5.7 Virtual Memory 450 Placing a Page and Finding it Again 454 Page Faults 457 What about Writes? 460 Making Address Translation Fast: the TLB 461 The Intrinsity FastMATH TLB 463 Integrating Virtual Memory, TLBs, and Caches 463 Implementing Protection with Virtual Memory 467 Handling TLB Misses and Page Faults 469 Summary 475 5.8 A Common Framework for Memory Hierarchy 477 Question 1: Where Can a Block Be Placed? 478 Question 2: How is a Block Found? 479 Question 3: Which Block Should Be Replaced on a Cache Miss? 480 Question 4: What Happens on a Write? 480 The Three Cs: An Intuitive Model for Understanding the Behavior of Memory Hierarchies 482 5.9 Using a Finite-State Machine to Control a Simple Cache 484 A Simple Cache 484 Finite-State Machines 486 FSM for a Simple Cache Controller 487 5.10 Parallelism and Memory Hierarchy: Cache Coherence 489 Basic Schemes for Enforcing Coherence 490 Snooping Protocols 491 5.11 Parallelism and Memory Hierarchy: Redundant Arrays of Inexpensive Disks 493 5.12 Advanced Material: Implementing Cache Controllers 493 5.13 Real Stuff: The ARM Cortex-A8 and Intel Core i7 Memory Hierarchies 494 Performance of the A8 and Core i7 Memory Hierarchies 496 5.14 Going Faster: Cache Blocking and Matrix Multiply 498 5.15 Fallacies and Pitfalls 501 5.16 Concluding Remarks 505 5.17 Historica Perspective and Further Reading 506 5.18 Exercises 506 6 Parallel Processors from Client to Cloud 523 6.1 Introduction 525 6.2 The Difficulty of Creating Parallel Processing Programs 527 6.3 SISD, MIMD, SIMD, SPMD, and Vector 532 SIMD in x86: Multimedia Extensions 533 Vector 533 Vector versus Scalar 535 Vector versus Multimedia Extensions 536 6.4 Hardware Multithreading 539 6.5 Multicore and Other Shared Memory Multiprocessors 542 6.6 Introduction to Graphics Processing Units 547 An Introduction to the NVIDIA GPU Architecture 548 NVIDIA GPU Memory Structures 550 Putting GPUs into Perspective 552 6.7 Clusters, Warehouse Scale Computers, and Other Message-Passing Multiprocessors 554 Warehouse-Scale Computers 556 6.8 Introduction to Multiprocessor Network Topologies 559 Implementing Network Topologies 561 6.9 Communicating to the Outside World: Cluster Networking 562 6.10 Multiprocessor Benchmarks and Performance Models 563 Performance Models 565 The Roofline Model 567 Comparing Two Generations of Opterons 568 6.11 Real Stuff: Benchmarking and Rooflines of the Intel Core i7 960 and the NVIDIA Tesla GPU 573 6.12 Going Faster: Multiple Processors and Matrix Multiply 578 6.13 Fallacies and Pitfalls 581 6.14 Concluding Remarks 583 6.15 Historical Perspective and Further Reading 586 6.16 Exercises 586 Appendix A: Assemblers, Linkers, and the SPIM Simulator 599 A.1 Introduction 600 A.2 Assemblers 607 A.3 Linkers 615 A.4 Loading 616 A.5 Memory Usage 617 A.6 Procedure Call Convention 619 A.7 Exceptions and Interrupts 630 A.8 Input and Output 635 A.9 SPIM 637 A.10 MIPS R2000 Assembly Language 642 A.11 Concluding Remarks 678 A.12 Exercises 679 Appendix B: The Basics of Logic Design 681 B.1 Introduction 682 B.2 Gates, Truth Tables, and Logic Equations 683 B.3 Combinational Logic 688 B.4 Using a Hardware Description Language 699 B.5 Constructing a Basic Arithmetic Logic Unit 705 B.6 Faster Addition: Carry Lookahead 717 B.7 Clocks 727 B.8 Memory Elements: Flip-Flops, Latches, and Registers 729 B.9 Memory Elements: SRAMs and DRAMs 737 B.10 Finite-State Machines 746 B.11 Timing Methodologies 751 B.12 Field Programmable Devices 757 B.13 Concluding Remarks 758 B.14 Exercises 759 Index 768 Computer Organization and Design, Fifth Edition, is the latest update to the classic introduction to computer organization. The text now contains new examples and material highlighting the emergence of mobile computing and the cloud. It explores this generational change with updated content featuring tablet computers, cloud infrastructure, and the ARM (mobile computing devices) and x86 (cloud computing) architectures. The book uses a MIPS processor core to present the fundamentals of hardware technologies, assembly language, computer arithmetic, pipelining, memory hierarchies and I/O.Because an understanding of modern hardware is essential to achieving good performance and energy efficiency, this edition adds a new concrete example, Going Faster, used throughout the text to demonstrate extremely effective optimization techniques. There is also a new discussion of the Eight Great Ideas of computer architecture. Parallelism is examined in depth with examples and content highlighting parallel hardware and software topics. The book features the Intel Core i7, ARM Cortex-A8 and NVIDIA Fermi GPU as real-world examples, along with a full set of updated and improved exercises.This new edition is an ideal resource for professional digital system designers, programmers, application developers, and system software developers. It will also be of interest to undergraduate students in Computer Science, Computer Engineering and Electrical Engineering courses in Computer Organization, Computer Design, ranging from Sophomore required courses to Senior Electives. Winner of a 2014 Texty Award from the Text and Academic Authors Association Includes new examples, exercises, and material highlighting the emergence of mobile computing and the cloud Covers parallelism in depth with examples and content highlighting parallel hardware and software topics Features the Intel Core i7, ARM Cortex-A8 and NVIDIA Fermi GPU as real-world examples throughout the book Adds a new concrete example,'Going Faster,'to demonstrate how understanding hardware can inspire software optimizations that improve performance by 200 times Discusses and highlights the'Eight Great Ideas'of computer architecture: Performance via Parallelism; Performance via Pipelining; Performance via Prediction; Design for Moore's Law; Hierarchy of Memories; Abstraction to Simplify Design; Make the Common Case Fast; and Dependability via Redundancy Includes a full set of updated and improved exercises

The fifth edition of Computer Organization and Design—winner of a 2014 Textbook Excellence Award (Texty) from The Text and Academic Authors Association—moves forward into the post-PC era with new examples, exercises, and material highlighting the emergence of mobile computing and the cloud. This generational change is emphasized and explored with updated content featuring tablet computers, cloud infrastructure, and the ARM (mobile computing devices) and x86 (cloud computing) architectures.

Because an understanding of modern hardware is essential to achieving good performance and energy efficiency, this edition adds a new concrete example, "Going Faster," used throughout the text to demonstrate extremely effective optimization techniques. Also new to this edition is discussion of the "Eight Great Ideas" of computer architecture.

As with previous editions, a MIPS processor is the core used to present the fundamentals of hardware technologies, assembly language, computer arithmetic, pipelining, memory hierarchies and I/O.

Instructors looking for fourth edition teaching materials should e-mail textbook@elsevier.com.

• Winner of a 2014 Texty Award from the Text and Academic Authors Association
• Includes new examples, exercises, and material highlighting the emergence of mobile computing and the cloud
• Covers parallelism in depth with examples and content highlighting parallel hardware and software topics
• Features the Intel Core i7, ARM Cortex-A8 and NVIDIA Fermi GPU as real-world examples throughout the book
• Adds a new concrete example, "Going Faster," to demonstrate how understanding hardware can inspire software optimizations that improve performance by 200 times
• Discusses and highlights the "Eight Great Ideas" of computer architecture: Performance via Parallelism; Performance via Pipelining; Performance via Prediction; Design for Moore's Law; Hierarchy of Memories; Abstraction to Simplify Design; Make the Common Case Fast; and Dependability via Redundancy
• Includes a full set of updated and improved exercises

Front Cover -- Computer Organization and Design -- Copyright Page -- Acknowledgments -- Contents -- Preface -- About This Book -- About the Other Book -- Changes for the Fifth Edition -- Instructor Support -- Concluding Remarks -- Acknowledgments for the Fifth Edition -- 1 Computer Abstractions and Technology -- 1.1 Introduction -- Classes of Computing Applications and Their Characteristics -- Welcome to the PostPC Era -- What You Can Learn in This Book -- 1.2 Eight Great Ideas in Computer Architecture -- Design for Moore's Law -- Use Abstraction to Simplify Design -- Make the Common Case Fast -- Performance via Parallelism -- Performance via Pipelining -- Performance via Prediction -- Hierarchy of Memories -- Dependability via Redundancy -- 1.3 Below Your Program -- From a High-Level Language to the Language of Hardware -- 1.4 Under the Covers -- Through the Looking Glass -- Touchscreen -- Opening the Box -- A Safe Place for Data -- Communicating with Other Computers -- 1.5 Technologies for Building Processors and Memory -- 1.6 Performance -- Defining Performance -- Measuring Performance -- CPU Performance and Its Factors -- Instruction Performance -- The Classic CPU Performance Equation -- 1.7 The Power Wall -- 1.8 The Sea Change: The Switch from Uniprocessors to Multiprocessors -- 1.9 Real Stuff: Benchmarking the Intel Core i7 -- SPEC CPU Benchmark -- SPEC Power Benchmark -- 1.10 Fallacies and Pitfalls -- 1.11 Concluding Remarks -- Road Map for This Book -- 1.12 Historical Perspective and Further Reading -- The First Electronic Computers -- Commercial Developments -- Measuring Performance -- The Quest for an Average Program -- SPECulating about Performance -- The Growth of Embedded Computing -- A Half-Century of Progress -- Further Reading -- 1.13 Exercises -- 2 Instructions: Language of the Computer -- 2.1 Introduction