Computer Organization and Design, Revised Printing (eBook)

Front cover 1
Title page 4
Copyright page 5
Table of Contents 6
Preface 12
About This Book 12
About the Other Book 12
Changes for the Third Edition 13
Instructor Support 16
Concluding Remarks 16
Acknowledgments for the Third Edition 16
1 Computer Abstractions and Technology 19
1.1 Introduction 20
Classes of Computing Applications and Their Characteristics 22
What You Can Learn in This Book 25
1.2 Below Your Program 28
From a High-Level Language to the Language of Hardware 29
1.3 Under the Covers 32
Anatomy of a Mouse 33
Through the Looking Glass 35
Opening the Box 35
A Safe Place for Data 40
Communicating with Other Computers 42
Technologies for Building Processors and Memory 44
1.4 Real Stuff: Manufacturing Pentium 4 Chips 45
1.5 Fallacies and Pitfalls 50
Road Map for This Book 52
1.6 Concluding Remarks 52
1.7 Historical Perspective and Further Reading 53
1.8 Exercises 53
Computers in the Real World 61
2 Instructions: Language of the Computer 63
2.1 Introduction 65
2.2 Operations of the Computer Hardware 66
2.3 Operands of the Computer Hardware 69
Memory Operands 71
Constant or Immediate Operands 74
2.4 Representing Instructions in the Computer 77
MIPS Fields 80
2.5 Logical Operations 85
2.6 Instructions for Making Decisions 89
Loops 91
Case/Switch Statement 93
2.7 Supporting Procedures in Computer Hardware 96
Using More Registers 97
Nested Procedures 100
Allocating Space for New Data on the Stack 103
Allocating Space for New Data on the Heap 104
2.8 Communicating with People 107
Characters and Strings in Java 110
32-Bit Immediate Operands 112
2.9 MIPS Addressing for 32-Bit Immediates and Addresses 112
Addressing in Branches and Jumps 114
MIPS Addressing Mode Summary 117
Decoding Machine Language 117
2.10 Translating and Starting a Program 123
Compiler 124
Assembler 124
Linker 125
Loader 129
Dynamically Linked Libraries 129
Starting a Java Program 131
High-Level Optimizations 133
2.11 How Compilers Optimize 133
Local and Global Optimizations 134
2.12 How Compilers Work: An Introduction 138
2.13 A C Sort Example to Put It All Together 138
The Procedure 139
Array Version of Clear 147
2.14 Implementing an Object-Oriented Language 147
2.15 Arrays versus Pointers 147
Pointer Version of Clear 149
Comparing the Two Versions of Clear 150
2.16 Real Stuff: IA-32 Instructions 151
The Intel IA-32 151
IA-32 Integer Operations 155
IA-32 Instruction Encoding 157
IA-32 Conclusion 159
2.17 Fallacies and Pitfalls 160
2.18 Concluding Remarks 162
2.19 Historical Perspective and Further Reading 164
2.20 Exercises 164
Computers in the Real World 173
3 Arithmetic for Computers 175
3.1 Introduction 177
3.2 Signed and Unsigned Numbers 177
Summary 185
3.3 Addition and Subtraction 187
Summary 191
3.4 Multiplication 193
Sequential Version of the Multiplication Algorithm and Hardware 194
Signed Multiplication 197
Faster Multiplication 198
Multiply in MIPS 198
Summary 198
3.5 Division 200
A Division Algorithm and Hardware 201
Signed Division 204
Faster Division 205
Divide in MIPS 205
Summary 206
3.6 Floating Point 206
Floating-Point Representation 208
Floating-Point Addition 214
Floating-Point Multiplication 219
Floating-Point Instructions in MIPS 223
Accurate Arithmetic 230
Summary 232
3.7 Real Stuff: Floating Point in the IA-32 234
The IA-32 Floating-Point Architecture 235
The Intel Streaming SIMD Extension 2 (SSE2) Floating-Point Architecture 237
3.8 Fallacies and Pitfalls 237
3.9 Concluding Remarks 242
3.10 Historical Perspective and Further Reading 246
3.11 Exercises 246
Computers in the Real World 253
4 Assessing and Understanding Performance 255
4.1 Introduction 257
Defining Performance 258
Measuring Performance 261
4.2 CPU Performance and Its Factors 263
4.3 Evaluating Performance 271
Comparing and Summarizing Performance 273
Total Execution Time: A Consistent Summary Measure 274
Performance with SPEC CPU Benchmarks 276
4.4 Real Stuff: Two SPEC Benchmarks and the Performance of Recent Intel Processors 276
SPECweb99: A Throughput Benchmark for Web Servers 279
Performance, Power, and Energy Efficiency 280
4.5 Fallacies and Pitfalls 283
4.6 Concluding Remarks 287
4.7 Historical Perspective and Further Reading 289
4.8 Exercises 289
Computers in the Real World 297
5 The Processor: Datapath and Control 299
5.1 Introduction 301
A Basic MIPS Implementation 302
5.2 Logic Design Conventions 306
5.3 Building a Datapath 309
Creating a Single Datapath 315
5.4 A Simple Implementation Scheme 317
The ALU Control 318
Designing the Main Control Unit 320
Why a Single-Cycle Implementation Is Not Used Today 331
5.5 A Multicycle Implementation 335
Breaking the Instruction Execution into Clock Cycles 342
Defining the Control 347
5.6 Exceptions 357
How Exceptions Are Handled 358
How Control Checks for Exceptions 360
5.7 Microprogramming: Simplifying Control Design 363
5.8 An Introduction to Digital Design Using a Hardware Design Language 363
Challenges Implementing More Complex Architectures 364
5.9 Real Stuff: The Organization of Recent Pentium Implementations 364
The Structure of the Pentium 4 Implementation 365
5.10 Fallacies and Pitfalls 367
5.11 Concluding Remarks 369
5.12 Historical Perspective and Further Reading 370
5.13 Exercises 371
Computers in the Real World 383
6 Enhancing Performance with Pipelining 385
6.1 An Overview of Pipelining 387
Designing Instruction Sets for Pipelining 391
Pipeline Hazards 392
Pipeline Overview Summary 400
6.2 A Pipelined Datapath 401
Graphically Representing Pipelines 412
6.3 Pipelined Control 416
6.4 Data Hazards and Forwarding 419
6.5 Data Hazards and Stalls 430
6.6 Control Hazards 433
Assume Branch Not Taken 435
Reducing the Delay of Branches 435
Dynamic Branch Prediction 438
Pipeline Summary 441
6.7 Using a Hardware Description Language to Describe and Model a Pipeline 443
6.8 Exceptions 444
6.9 Advanced Pipelining: Extracting More Performance 449
The Concept of Speculation 451
Static Multiple Issue 452
Dynamic Multiple-Issue Processors 459
6.10 Real Stuff: The Pentium 4 Pipeline 465
6.11 Fallacies and Pitfalls 468
6.12 Concluding Remarks 469
6.13 Historical Perspective and Further Reading 471
6.14 Exercises 471
Computers in the Real World 481
7 Large and Fast: Exploiting Memory Hierarchy 483
7.1 Introduction 485
7.2 The Basics of Caches 490
Accessing a Cache 493
Handling Cache Misses 499
Handling Writes 500
An Example Cache: The Intrinsity FastMATH Processor 502
Designing the Memory System to Support Caches 504
Summary 508
7.3 Measuring and Improving Cache Performance 509
Reducing Cache Misses by More Flexible Placement of Blocks 513
Locating a Block in the Cache 519
Choosing Which Block to Replace 521
Reducing the Miss Penalty Using Multilevel Caches 521
Check Yourself 526
Summary 527
7.4 Virtual Memory 528
Placing a Page and Finding It Again 532
Page Faults 533
What about Writes? 538
Making Address Translation Fast: The TLB 538
Integrating Virtual Memory, TLBs, and Caches 541
Implementing Protection with Virtual Memory 545
Handling TLB Misses and Page Faults 548
Summary 553
Question 1: Where Can a Block Be Placed? 555
7.5 A Common Framework for Memory Hierarchies 555
Question 2: How Is a Block Found? 557
Question 3: Which Block Should Be Replaced on a Cache Miss? 558
Question 4: What Happens on a Write? 559
The Three Cs: An Intuitive Model for Understanding the Behavior of Memory Hierarchies 560
Check Yourself 562
7.6 Real Stuff: The Pentium P4 and the AMD Opteron Memory Hierarchies 563
The Memory Hierarchies of the P4 and Opteron 564
Techniques to Reduce Miss Penalties 564
7.7 Fallacies and Pitfalls 567
7.8 Concluding Remarks 569
Recent Trends 570
7.9 Historical Perspective and Further Reading 572
7.10 Exercises 572
Answers to Check Yourself 578
Computers in the Real World 579
8 Storage, Networks, and Other Peripherals 581
8.1 Introduction 583
8.2 Disk Storage and Dependability 586
Dependability, Reliability, and Availability 588
RAID 591
8.3 Networks 597
Bus Basics 598
8.4 Buses and Other Connections between Processors, Memory, and I/O Devices 598
The Buses and Networks of the Pentium 4 602
8.5 Interfacing I/O Devices to the Processor, Memory, and Operating System 605
Giving Commands to I/O Devices 606
Communicating with the Processor 607
Interrupt Priority Levels 608
Transferring the Data between a Device and Memory 610
Direct Memory Access and the Memory System 612
8.6 I/O Performance Measures: Examples from Disk and File Systems 614
Transaction Processing I/O Benchmarks 615
File System and Web I/O Benchmarks 615
I/O Performance versus Processor Performance 616
8.7 Designing an I/O System 617
8.8 Real Stuff: A Digital Camera 620
8.9 Fallacies and Pitfalls 623
8.10 Concluding Remarks 626
8.11 Historical Perspective and Further Reading 628
8.12 Exercises 628
Computers in the Real World 639
Appendix A Assemblers, Linkers, and the SPIM Simulator 641
A.1 Introduction 642
When to Use Assembly Language 647
Drawbacks of Assembly Language 648
A.2 Assemblers 649
Object File Format 652
Additional Facilities 653
A.3 Linkers 657
A.4 Loading 658
A.5 Memory Usage 659
A.6 Procedure Call Convention 661
Procedure Calls 662
Procedure Call Example 665
Another Procedure Call Example 669
A.7 Exceptions and Interrupts 672
A.8 Input and Output 676
Simulation of a Virtual Machine 679
A.9 SPIM 679
Getting Started with SPIM 680
Surprising Features 681
Byte Order 681
System Calls 682
Addressing Modes 683
A.10 MIPS R2000 Assembly Language 683
Assembler Syntax 685
Encoding MIPS Instructions 687
Instruction Format 687
Arithmetic and Logical Instructions 689
Constant-Manipulating Instructions 695
Comparison Instructions 695
Branch Instructions 697
Jump Instructions 701
Trap Instructions 701
Load Instructions 703
Store Instructions 705
Data Movement Instructions 707
Floating-Point Instructions 710
Exception and Interrupt Instructions 717
Further Reading 718
A.11 Concluding Remarks 718
A.12 Exercises 719
Index 722
MIPS Reference Data 738