3"
`'r.
`i".._.'.t~»i{.,--
`I-l EVEN-R
`
`:
`'
`
`THE HARDWAREISGFTWARE INTERFACE
`
`
`
`Oracle-1041 p. 1
`Oracle v. Teleputers
`|PR2021-00078
`
`Oracle-1041 p. 1
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`THIRD EDITION
`
`Computer Organization Design
`
`THE HARDWARE / SOFTWARE INTERFACE
`
`Oracle-1041 p. 2
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`ACKNOWLEDGEMENTS
`
`Figures 1.9, I. 15 Courtesy oflntel.
`
`Computers in the Real World:
`
`Figure 1.11 Courtesy of Storage Technology Corp.
`
`Photo of "A Laotian villager," courtesy of David Sanger.
`
`Figures 1.7.1, 1.7.2, 6.13.2 Courtesy of the Charles Babbage Institute,
`University of l'vlinnesota Libraries, Minneapolis.
`
`Figures 1.7.3, 6.13.1, 6.13.3, 7.9.3, 8.11.2 Courtesy of IBM.
`
`Figure 1. 7.4 Courtesy of Cray Inc.
`
`Figure 1.7.5 Courtesy of Apple Computer, Inc.
`
`Figure 1.7.6 Courtesy of the Computer History Museum.
`
`Figure 7.33 Courtesy of AMD.
`
`Photo of an "Indian villager," property of Encore Software, Ltd., India.
`
`Photos of "Block and students" and "a pop-up ard1ival satellite tag,"
`courtesy of Professor Barbara Block. Photos by Scott Taylor.
`
`Photos of "Professor Dawson and student" and "the Mica micromote,"
`courtesy of AP/World Wide Photos.
`
`Photos of "images of pottery fragments" and "a computer reconstruc(cid:173)
`tion," courtesy of Andrew Willis and DaYid B. Cooper, Brown University,
`Division of Engineering.
`
`Figures 7.9.l, 7.9.2 Courtesy of Museum of Science, Boston.
`
`Photo of"the Eurostar TGV train," by Jos van der Kolk.
`
`Figure 7.9.4 Courtesy of MIPS Technologies, Inc.
`
`Photo of "the interior of a Eurostar TGV cab," by Andy Veitch.
`
`Figure 8.3 ©Peg Skorpinski.
`
`Photo of "firefighter Ken Whitten," courtesy of World Economic Forum.
`
`Figure 8.11.1 Courtesy of the Computer Museum of America.
`
`Figure 8.11.3 Courtesy of the Commercial Computing Museum.
`
`Figures 9.11.2, 9.11.3 Courtesy of NASA Ames Research Center.
`
`Figllie 9.11.4 Courtesy of Lawrence Livermore National Laboratory.
`
`Graphic of an "artificial retina," © The San Francisco Chronicle.
`Reprinted by permission.
`
`Image of "A laser scan of Michelangelo's statue of David," courtesy of
`Marc Levoy and Dr. Franca Falletti, director of the Galleria dell'Acca(cid:173)
`demia, Italy.
`
`"An image from the Sistine Chapel," courtesy of Luca Pezzati. IR image
`recorded using the scanner for IR reflectography of the INOA (National
`Institute for Applied Optics, http://arte.ino.it) at the Opificio delle Pietre
`Dure in Florence.
`
`Oracle-1041 p. 3
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`T H I R D EDITION
`
`Computer Organization and Design
`
`THE HARDWARE / SOFTWARE INTERFACE
`
`David A. Patterson
`University of Californfa, Berkeley
`
`John L. Hennessy
`Stanford University
`
`With a contribution by
`Peter J. Ashenden
`Ashenden Designs Pty Ltd
`
`James R. larus
`Microsoft Research
`
`Daniel J. Sorin
`Duke University
`
`AMSTERDAM · BOSTON • HEIDELBERG · LONDON
`NEW YORK • OXFORD • PARIS · SAN DIEGO
`SAN FRANCISCO • SINGAPORE · SYDNEY · TOKYO
`
`ELSEVIER
`
`Morgan Kaufmann is an imprint of Elsevier
`
`MORGAN KAUFMANN PUBLISHERS
`
`Oracle-1041 p. 4
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Senior Editor
`Publishing Services Manager
`Editorial Assistant
`Cover Design
`Cover and Chapter Illustration
`Text Design
`Composition
`Technical illustration
`Copyeditor
`Proofreader
`Indexer
`Interior printer
`Cover printer
`
`Denise E. M. Penrose
`Simon Crwnp
`Swnmer Blodc
`Ross Caron Design
`Chris Asimoudis
`GGS Book Services
`Nancy Logan and Dartmouth Publishing, Inc.
`Dartmouth Publishing, lnc.
`Ken DellaPenta
`Jacqui Brownstein
`Linda Buskus
`Courier
`Courier
`
`Morgan Kaufmann Publishers is an imprint of Elsevier.
`500 Sansome Street, Suite 400, San Francisco, CA 94111
`
`This book is printed on acid-free paper.
`
`© 2005 by Elsevier Inc. All rights reserved.
`
`Designations used by companies to distinguish their products are often claimed as trademarks or registered
`trademarks. ln all instances in whid1 Morgan Kaufmann Publishers is aware of a claim, the product names
`appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies
`for more complete information regardi11g trademarks and registration.
`
`No part of this publication may be reproduced, stored in a retrieval system, or transmitted iJ1 any form or
`by any means--electronic, med1anical, photocopying, scanniJ1g, or otherwise- without prior written per(cid:173)
`mission of the publisher.
`
`Permissions may be sought directly from Elsevier's Science & Technology Rights Department in Oxford,
`UK: phone: ( +44) 1865 843830, fax: ( +44) 1865 853333, e-mail: permi.ssions@else,,ier.com.uk. You may
`also complete your request on-line via the Elsevier homepage (http://elsevier.com) by selecting "Customer
`Support" and then "Obtaining Permissions."
`
`Library of Congress Cataloging-m-Publication Data
`Application submitted
`
`ISBN: 1-55860-604-1
`
`For information on all Morgan Kaufmann publications,
`visit our Web site at www.mkp.com.
`
`Printed in the United States of America
`04 05 06 07 08
`5 4 3 2 1
`
`Oracle-1041 p. 5
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Contents
`
`V
`
`Contents
`
`Preface
`
`ix
`
`CHAPTERS
`
`a Computer Abstractions and Technology 2
`
`11
`
`Introduction 3
`1.1
`1.2 Below Your Program
`1.3 Under the Covers 15
`1.4 Real Stuff: Manufacturing Pentium 4 Chips 28
`1.5 Fallacies and PitfaJls 33
`1.6 Concluding Remarks 35
`1.7 Historical Perspective and Further Reading 36
`1.8 Exercises 36
`
`a
`
`IN THE REAL WORLD
`COMPUTERS
`Information Technology for the 4 Billion without IT 44
`
`EJ Instructions: Language of the Computer 46
`
`Introduction 48
`2.1
`2.2 Operations of the Computer Hardware 49
`2.3 Operands of the Computer Hardware 52
`2.4 Representing Instructions in the Computer 60
`2.5 Logical Operations 68
`2.6
`Instructions for Making Decisions 72
`2.7 Supporting Procedures in Computer Hardware 79
`2.8 Communicating with People 90
`2.9 MIPS Addressing for 32-Bit Immediates and Addresses 95
`2.10 Translating and Starting a Program 106
`2.11 How Compilers Optimize 116
`2.12 How Compilers Work: A.n Introduction 121
`
`Oracle-1041 p. 6
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`vi
`
`Contents
`
`lj
`
`2.13 AC Sort Example to Put It All Together 121
`2.14 Implementing an Object-Oriented Language 130
`2.15 Arrays versus Pointers 130
`2.16 Real Stuff: IA-32 Instructions 134
`2.17 Fallacies and Pitfalls 143
`2.18 Concluding Remarks 145
`2.19 Historical Perspective and Further Reading 147
`2.20 Exercises 147
`
`IN THE REAL WORLD
`COMPUTERS
`Helping Save Our Environment with Data 156
`
`El Arithmetic for Computers 158
`
`Introduction 160
`3.1
`3.2 Signed and Unsigned Numbers 160
`3.3 Adclition and Subtraction 170
`3.4 Multiplication 176
`3.5 Division 183
`3.6 Floating Point 189
`3.7 Rea l Stuff: Floati11g Point in the IA-32 217
`3.8 Fallacies and Pitfalls 220
`3.9 Concluding Remarks 225
`3.10 Historical Perspective and Further Reading 229
`3.11 Exercises 229
`
`IN THE REAL WORLD
`COMPUTERS
`Reconstructing the Ancient World 236
`
`a Assessing and Understanding Performance 238
`
`Introduction 240
`4.1
`4.2 CPU Performance and Its Factors 246
`4.3 Evaluating Performance 254
`4.4 Rea l Stuff: Two SPEC Benchmarks and the Performance ofRecent
`Intel Processors 259
`Fallacies and Pitfalls 266
`4.5
`4.6 Concluding Remarks 270
`4.7 Historical Perspective and Further Reading 272
`4.8 Exercises 272
`
`IN THE REAL WORLD
`COMPUTERS
`Moving People Faster and More Safely 280
`
`Oracle-1041 p. 7
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Contents
`
`vii
`
`El The Processor: Datapath and Control 282
`
`Introduction 284
`5.1
`5.2 Logic Design Conventions 289
`5.3 Building a Datapatl1 292
`5.4 A Simple Implementation Scheme 300
`5.5 A Multicycle Implementation 318
`5.6 Exceptions 340
`5.7 Mkroprogramming: Simplifying Control Design 346
`5.8 An Introduction to Digital Design Using a Hardware Design
`Language 346
`5.9 Real Stuff: The Organization of Recent Pentium
`Implementations 347
`5.10 Fallacies and Pitfalls 350
`5.11 Concluding Remarks 352
`5.12 Historical Perspective and Further Reading 353
`5.13 Exercises 354
`
`Iii
`
`1fi
`
`IN THE REAL WORLD
`COMPUTERS
`Empowering the Disabled 366
`
`a Enhancing Performance with Pipelining 368
`
`6.1 An Overview of Pipelining 370
`6.2 A Pipelined Datapath 384
`PipeJined Control 399
`6.3
`6.4 Data Hazards and Forwarding 402
`6.5 Data Hazards and Stalls 413
`6.6 Branch Hazards 416
`6.7 UsiJ1g a Hardware Description Language to Describe and Model a
`Pipeline 426
`6.8 Exceptions 427
`6.9 Advanced Pipelining: fa.tracting More Performance 432
`6.10 Rea] Stuff: The Pentiwn 4 Pipeline 448
`6.11 Fallacies and Pitfalls 451
`6.12 ConcludingRemarks 452
`6.13 Historical Perspective and Further Reading 454
`6.14 Exercises 454
`
`a
`
`Iii
`
`IN THE REAL WORLD
`COMPUTERS
`Mass Communication without Gatekeepers 464
`
`Oracle-1041 p. 8
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`viii
`
`Contents
`
`II
`
`-~
`
`Large and Fast: Exploiting Memory Hierarchy 466
`
`7.1
`7.2
`7.3
`7.4
`7.5
`7.6
`
`7.7
`7.8
`7.9
`7.10
`
`Introduction 468
`The Basics of Caches 473
`Measuring and Improving Cache Performance 492
`Virtual Memory 511
`A Common Framework for Memory Hierarchies 538
`Real Stuff: The Pentium P4 and the AMD Opteron Memory
`Hierarchies 546
`Fallacies and Pitfalls 550
`ConcJuding Remarks 552
`Historical Perspective and Further Reading 555
`Exercises 555
`
`IN THE REAL WORLD
`COMPUTERS
`Saving the World's Art Treasures 562
`
`El Storage, Networks, and Other Peripherals 564
`
`8.1
`8.2
`8.3
`8.4
`
`8.5
`
`8.6
`
`8.7
`8.8
`8.9
`8.10
`8.11
`8.12
`
`Introduction 566
`Disk Storage and Dependability 569
`Networks 580
`Buses and Other Connections between Processors, Memory, and I/0
`Devices 581
`Interfacing 1/0 Devices to the Processor, Memory, and Operating
`System 588
`I/0 Performance Measures: Examples from Disk and File
`Systems 597
`Designing an I/0 System 600
`Real Stuff: A Digital Camera 603
`Fallacies and Pitfalls 606
`Concluding Remarks 609
`Historical Perspective and Further Reading 611
`Exercises 611
`
`-~
`
`IN THE REAL WORLD
`COMPUTERS
`Saving lives through Better Diagnosis 622
`
`lfJ Multiprocessors and Clusters 9-2
`
`Introduction 9-4
`9.1
`9.2 Programming Multiprocessors 9-8
`9.3 Multiprocessors Connected by a Single Bus 9-11
`
`Oracle-1041 p. 9
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Contents
`
`Ix
`
`9.4 Multiprocessors Connected by a Network 9-20
`9.5 Clusters 9-25
`9.6 Network Topologies 9-27
`9.7 Multiprocessors Inside a Chip and Mnltitbreading 9-30
`9.8 Real Stuff: The Google Cluster ofpCs 9-34
`9.9 Fallacies and Pitfalls 9-39
`9 .10 Concluding Remarks 9-42
`9.11 Historical Perspective and Further Reading 9-47
`9.12 Exercises 9-55
`
`APPENDICES
`
`la Assemblers, Linkers, and the SPIM Simulator A-2
`
`Introduction A-3
`A.l
`A.2 Assemblers A-10
`A.3 Linkers A-18
`A.4 Loading A-19
`A.5 Memory Usage A-20
`A.6 Procedme Call Convention A-22
`A.7 Exceptions and Interrupts A-33
`A.8
`Input and Output A-38
`A.9 SPIM A-40
`A.10 MIPS R2000 Assembly Language A-45
`A.I I Concluding Remarks A-81
`A.12 Exercises A-82
`
`ID The Basics of Logic Design B-2
`
`Introduction B-3
`B.l
`B.2 Gates, Truth Tables, and Logic Equations B-4
`B.3 Combinational Logic B-8
`B.4 Using a Hardware Description Language B-20
`B.5 Constructing a Basic Arithmetic Logic Unit B-26
`B.6 Faster Addition: Carry Looka}1ead B-38
`B.7 Clocks B-47
`B.8 Memory Elements: Flip-flops, Latches, and Registers B-49
`B.9 Memory Elements: SRAMs and DRAMs B-57
`B.10 Finite State Machines B-67
`B.11 Timing Methodologies B-72
`
`Oracle-1041 p. 10
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`X
`
`Contents
`
`B.12 Field Programmable Devices B-77
`B.13 Concluding Remarks B-78
`B.14 Exercises B-79
`
`Im Mapping Control to Hardware C-2
`
`ID
`
`Introduction C-3
`C.1
`Implementing Combinational Control Units C-4
`C.2
`Implementing Finite State Machine Control C-8
`C.3
`Implementing the Next-State Function with a Sequencer C-21
`C.4
`C.5 Translating a Microprogram to Hardware C-27
`C.6 Concluding Remarks C-31
`C.7 Exercises C-32
`
`A Survey of RISC Architectures for Desktop, Server,
`and Embedded Computers D-2
`
`Introduction D-3
`D.l
`D.2 Addressing Modes and Instruction Formats D-5
`D.3
`Instructions: The MIPS Core Subset D-9
`Instructions: Multimedia Extensions of the Desktop/Server RISCs D-16
`D.4
`D.5
`Instructions: Digital Signal-Processing Extensions oft be
`Embedded RISCs D-19
`Instructions: Common Extensions to MIPS Core D-20
`D.6
`Instructions Unique to MIPS64 D-25
`D.7
`Instructions Unique to Alpha D-27
`D.8
`Instructions Unique to SPARC v.9 D-29
`D.9
`D.10 Instructions Unique to PowerPC D-32
`D.11 Instructions Unique to PA-RISC 2.0 D-34
`D.12 Instructions Unique to ARM D-36
`D.13 Instructions Unique to Thumb D-38
`D.14 Instructions Unique to SuperH D-39
`D.15 Instructions Unique to M32R D-40
`D.16 Instructions Unique to MIPS16 D-41
`D.17 ConcludingRemarks D-43
`D.18 Acknowledgments D-46
`D.19 References D-47
`
`Index 1-1
`Glossary G -1
`II Further Reading FR-1
`
`Oracle-1041 p. 11
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Preface
`
`xi
`
`Preface
`
`The most beautiful thing we can experience is the mysterious.
`It is the source of all true art and science.
`
`Albert Einstein, What I Believe, 1930
`
`About This Book
`We believe that learning in computer science and engineering should reflect the
`current state of the field, as well as introduce the principles that are shaping com(cid:173)
`puting. We also feel that readers in every specialty of computing need to appreci(cid:173)
`ate the organizational paradigms that determine the capabilities, performance,
`and, ultimately, the success of computer systems.
`Modern computer technology requires professionals of every computing spe(cid:173)
`cialty to understand both hardware and software. The interaction between hard(cid:173)
`ware and software at a variety of levels also offers a framework for understanding
`the fundamentals of computing. Whether your primary interest is hardware or
`software, computer science or electrical engineering, the central ideas in computer
`organizatfon and design are the same. Thus, our emphasis in this book is to show
`the relationship between hardware and software and to focus on the concepts that
`are the basis for current computers.
`The audience for this book includes those with little experience in assembly
`language or logic design who need to w1derstand basic computer organization as
`well as readers with backgrounds in assembly language and/or logic design who
`want to learn how to design a computer or w1derstand how a system works and
`why it performs as it does.
`
`About the Other Book
`Some readers may be familiar with Computer Architecture: A Quantitative
`Approach, popularly known as Hennessy and Patterson. (This book in turn is
`called Patterson and Hennessy.) Our motivation in writing that book was to
`describe the principles of computer architecture using solid engineering funda-
`
`Oracle-1041 p. 12
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`xii
`
`Preface
`
`mentals and quantitative cost/performance trade-offs. We used an approach that
`combined examples and measurements, based on commercial systems, to create
`realistic design e>..l)eriences. Our goal was to demonstrate that computer architec(cid:173)
`ture could be learned using quantitative methodologies instead of a descriptive
`approach. It is intended for the serious computing professional who wants a
`detailed understanding of computers.
`A majority of the readers for this book do not plan to become computer archi(cid:173)
`tects. The performance of future software systems will be dramatically affected,
`however, by how well software designers understand the basic hardware tech(cid:173)
`niques at work in a system. Thus, compiler writers, operating system designers,
`database programmers, and most other software engineers need a firm grounding
`in the principles presented in this book. Similarly, hardware designers must
`understand clearly the effects of their work on software applications.
`Thus, we knew that this book had to be much more than a subset of the mate(cid:173)
`rial in Computer Architecture, and the material was extensively revised to match
`the different audience. We were so happy with the result that the subsequent edi(cid:173)
`tions of Computer Architecture were revised to remove most of the introductory
`material; hence, there is much less overlap today than with the first editions of
`both books.
`
`Changes for the Third Edition
`We had six major goals for the third edition of Computer Organization and Design:
`make the book work equally well for readers with a software focus or with a hard(cid:173)
`ware focus; improve pedagogy in general; enhance w1derstanding of program per(cid:173)
`formance; update the technical content to reflect changes in the industry since the
`publication of the second edition in 1998; tie the ideas from the book more closely
`to tJ1e real world outside the computing industry; and reduce the size of tJ1js book.
`First, the table on the next page shows the hardware and software pailis through
`the material. Chapters 1, 4, and 7 are found on both paths, no matter what the expe(cid:173)
`rience or the focus. Chapters 2 and 3 are likely to be review material for the hard(cid:173)
`ware-oriented, but are essential reading for the software-oriented, especially for
`those readers interested in learning more about compilers and object-oriented pro(cid:173)
`gramming languages. The first sections of Chapters 5 and 6 give overviews for those
`with a software focus. Those with a hardware focus, however, will find that these
`chapters present core material; they may also, depending on background, want to
`read Appendix B on logic design first and the sections on microprogramming and
`how to use hardware description languages to specify control. Chapter 8 on
`input/output is key to readers with a software focus and should be read if time per(cid:173)
`mits by others. The last chapter on multiprocessors and clusters is again a question
`of time for the reader. Even the history sections show this balanced focus; they
`include short histories of programming languages, compilers, numerical software,
`operating systems, networking protocols, and databases.
`
`Oracle-1041 p. 13
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Preface
`
`xiii
`
`Chapter or Appendix
`
`Sections
`
`Software Focus Hardware Focus
`
`1. Computer Abstractions
`and Technology
`
`2. Instructions: Language
`of the Computer
`
`1.1 to 1.6
`SI 1.7 (History)
`2.1 to 2.11
`■ 2. 12 (Compilers)
`2.13 (C sort)
`■ 2.1 4 (Java)
`2.1510 2.18
`■ 2. 19 (History)
`3.1 to 3.11
`■ 3. 12 (History)
`D. RISC instruction set architectures ■ D.1 toD.19
`4.1 to4.6
`■ 4.7 (History)
`■ B.1 to B.13
`5.1 (Overview)
`
`3. Arithmetic for Computers
`
`4. Assessing and Understanding
`Performance
`
`B. The Basics of Logic Design
`
`5. The Processor: Datapath and
`Control
`
`C. Mapping Control to Hardware
`
`6. Enhancing Performance with
`Pipelining
`
`7. Large and Fast: Exploiting
`Memory Hierarchy
`
`8. Storage, Networks, and
`Ofher Peripherals
`
`9. Multiprocessors and Clusters
`
`A. Assemblers, Linkers, and
`the SPIM Simulator
`
`5.2 to 5.7
`■ 5.8 (Microcode)
`■ 5.9 (Verilog)
`5.1010 5.12
`■ 5.1 3 (History)
`■ C.1 toC.6
`6.1 (Overview)
`6.2106.6
`■ 6.7 (verilog)
`6.8 to6.9
`
`6.10 to 6.12
`■ 6.13 (History)
`7.1 to7.8
`■ 7.9 (History)
`8.1 to8.2
`■ 8.3 (Networks)
`8.4 to 8.10
`■ 8. 13 (History)
`■ 9. 1 to9.10
`■ 9.11 (History)
`■ A.1 to A. 12
`
`~ ~
`~ ~
`~ ~
`~
`~ ~
`
`~ -- ~
`
`~ ~
`~ ~
`~ ~
`~
`~ ~
`~ ~
`~
`:e'Q ~
`a"Q:
`~
`~
`0-. ~
`~ ~
`~
`
`-- ~ --~
`
`~
`~ ~
`~ ~
`~ ~
`~ ~
`~ ~
`O'Or ~
`~ ~
`~ ~
`~
`~
`
`~ ~
`
`Computers in the Real World
`
`Between Chapters
`
`~ ~
`
`Read carefully
`
`Review or read
`
`
`Read if have time ~ Reference ~
`Read for culture ~
`
`Oracle-1041 p. 14
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`xiv
`
`Preface
`
`The next goal was to improve the exposition of the ideas in the book, based on
`difficulties mentioned by readers of the second edition. We added five new book
`elements to help. To make the book work better as a reference, we placed defini(cid:173)
`tions of new terms in the margins at their first occurrence. We hope this will help
`readers find the sections when they want to refer back to material they have
`already read. Another change was the insertion of the "Check Yourself" sections,
`which we added to help readers to check their comprehension of the material on
`the first time through it. A third change is that added extra exercises in the "For
`More Practice" section. Fourth, we added the answers to the "Check Yourself" sec(cid:173)
`tions and to the For More Practice exercises to help readers see for themselves if
`they understand the material by comparing their answers to the book. The final
`new book element was inspired by the "Green Card" of the IBM System/360. We
`believe that you will find that the MIPS Reference Data Card will be a handy refer(cid:173)
`ence when writing MIPS assembly language programs. Our idea is that you will
`remove the card from the front of the book, fold it in half, and keep it in your
`pocket, just as IBM S/360 programmers did in the 1960s.
`Third, computers are so complex today that understanding the performance of
`a program involves w1derstanding a good deal about the underlying principles
`and the organization of a given computer. Our goal is that readers of this book
`should be able to understand the performance of their progams and how to
`improve it. To aid in that goal, we added a new book element called "Understand(cid:173)
`ing Program Performance" in several chapters. These sections often give concrete
`examples of how ideas in the chapter affect performance of real programs.
`Fourth, in the interval since the second edition of this book, Moore's law has
`marched onward so that we now have processors with 200 million transistors,
`DRAM chips with a billion transistors, and clock rates of multiple gigahertz. The
`"Real Stuff" examples have been updated to describe such chips. This edition also
`includes AMD64/IA-32e, the 64-bit address version of the long-lived 80x86 archi(cid:173)
`tecture, which appears to be the nemesis of the more recent IA-64. It also reflects
`the transition from parallel buses to serial networks and switches. Later chapters
`describe Google, which was born after the second edition, in terms of its cluster
`technology and in novel uses of search.
`Fifth, although many computer science and engineering students enjoy infor(cid:173)
`mation technology for technology's sake, some have more altruistic interests. This
`latter group tends to have more women and underrepresented minorities. Conse(cid:173)
`quently, we have added a new book element, "Computers in the Real World;' two(cid:173)
`page layouts fow1d between each chapter. Our perspective is that information
`technology is more valuable for humanity than most other topics you could
`study- whether it is preserving our art heritage, helping the Third World, saving
`our environment, or even changing political systems- and so we demonstrate our
`view with concrete examples of nontraditional applications. '-Ne think readers of
`these segments will have a greater appreciation of the computing culture beyond
`
`Oracle-1041 p. 15
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Preface
`
`xv
`
`the inherently interesting technology, much like those who read the history sec(cid:173)
`tions at the end of each chapter
`Finally, books are like people: they usually get larger as they get older. By using
`technology, we have managed to do aU the above and yet sh.rink the page count by
`hundreds of pages. As the table illustrates, the core portion of the book for hard(cid:173)
`ware and software readers is on paper, but sections that some readers would value
`more than others are found on the companfon CD. This technology also allows
`your authors to provide longer histories and more extensive exercises without
`concerns about lengthening the book. Once we added the CD to the book, we
`could then include a great deal of free software and tutorials that many instructors
`have told us they would like to use in their courses. This hybrid paper-CD publi(cid:173)
`cation weighs about 30% less than it did six years ago- an impressive goal for
`books as well as for people.
`
`Instructor Support
`We have collected a great deal of material to help instructors teach courses using
`this book. Solutions to exercises, figures from the book, lecture notes, lecture
`slides, and other materials are available to adopters from the publisher. Check the
`publisher's Web site for more information:
`
`www. mkp. com/ comp anion s /1 5586060 41
`
`Concluding Remarks
`If you read the following acknowledgments section, you will see that we went to
`great lengths to correct mistakes. Since a book goes through many printings, we
`have the opportunity to make even more corrections. If you uncover any remaining,
`resilient bugs, please contact the publisher by electronic mail at cod3bugs@mkp.com
`or by low-tech mail using the address found on the copyright page. The first person
`to report a technical error will be awarded a $1.00 bounty upon its implementation
`in future printings of the book!
`This book is truly collaborative, despite one of us running a major university.
`Together we brainstormed about the ideas and method of presentation, then indi(cid:173)
`vidually wrote about one-half of the chapters and acted as reviewer for every draft
`of the other half. The page count suggests we again wrote almost exactly the same
`number of pages. Thus, we equally share the blame for what you are about to read.
`
`Acknowledgments for the Third Edition
`We'd like to again express our appreciation to Jim Larus for his willingness in con(cid:173)
`tributing his expertise on assembly language programming, as well as for welcom(cid:173)
`ing readers of this book to use the simulator he developed and maintains. Our
`
`Oracle-1041 p. 16
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`xvi
`
`Preface
`
`exercise editor Dan Sorin took on the Herculean task of adding new exercises and
`answers. Peter Ashenden worked similarly hard to collect and organize the com(cid:173)
`panion CD.
`We are grateful to the many instructors who answered the publisher's surveys,
`reviewed our proposals, and attended focus groups to analyze and respond to our
`plans for this edition. They include the following individuals: Michael Anderson
`(University of Hartford), David Bader (University of New Mexico), Rusty Baldwin
`(Air Force Institute of Technology), John Barr (Ithaca College), Jack Briner
`(Charleston Southern University), Mats Brorsson (KTH, Sweden), Colin Brown
`(Franklin University), Lori Carter (Point Loma Nazarene University), John Casey
`(Northeastern University), Gene Chase (Messiah College), George Cheney (Univer(cid:173)
`sity of Massachusetts, Lowell), Daniel Citron (Jerusalem College of Technology,
`Israel), Albert Cohen (INRIA, France), Lloyd Dickman (PathScale), Jose Duato
`(Universidad Politecnica de Valencia, Spain), Ben Dugan (University of Washing(cid:173)
`ton), Derek Eager (University of Saskatchewan, Canada), Magnus Ekman (Chalm(cid:173)
`ers University of Technology, Sweden), Ata Elahi (Southern Connecticut State
`University), Soundararajan Ezekiel (Indiana University of Pennsylvania), Ernest
`Ferguson (Northwest Missouri State University), Michael Fry (Lebanon Valley Col(cid:173)
`lege, Pennsylvania), R. Gaede (University of Arkansas at Little Rock), Jean-Luc
`Gaudiot (University of California, Irvine), Thomas Gendreau (University of Wis(cid:173)
`consin, La Crosse), George Georgiou (California State University, San Bernardino),
`Paul Gillard (Memorial University of Newfoundland, Canada), Joe Grimes (Califor(cid:173)
`nia Polytechnic State University, SLO), Max Hailperin (Gustavus Adolphus Col(cid:173)
`lege), Jayantha Herath (St. Cloud State University, Minnesota), Mark Hill
`(University of Wisconsin, Madison), Michael Hsaio (Virginia Tech), Richard
`Hughey (University of California, Santa Cruz), Tony Jebara (Columbia University),
`Elizabeth Johnson (Xavier University), Peter Kogge (University of Notre Dame),
`Morris Lancaster (BAH), Doug Lawrence (University of Montana), David Lilja
`(University of Minnesota), Nam Ling (Santa Clara University, California), Paul Lrnn
`(Agilent Technologies), Stephen Mann (University of Waterloo, Canada), Diana
`Marculescu (Carnegie Mellon University), Margaret McMahon (U.S. Naval Aca.d(cid:173)
`emy Computer Science), Uwe Meyer-Baese (Florida State University), Chris Milner
`(University of Virginia), Tom Pittman (Southwest Baptist University), Jalel Rejeb
`(San Jose State University, California), Bill Siever (University of Missouri, Rolla),
`Kevin Skadron (University of Virginia), Pam Smallwood (Regis University, Colo(cid:173)
`rado), K. Stuart Smith (Rocky Mountain College), William J. Taffe (Plymouth State
`University), Michael E. Thomodakis (Texas A&M University), Ruppa K. Thulasiram
`(University of Manitoba, Canada), Ye Tw1g (University of South Alabama), Steve
`VanderLeest (Calvin College), Neal R. Wagner (University of Texas at San Antonio),
`and Kent Wilken (University of California, Davis).
`
`Oracle-1041 p. 17
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Preface
`
`xvii
`
`We are grateful too to those who carefully read our draft manuscripts; some
`read successive drafts to help ensure new errors didn't creep in as we revised.
`They in dude Krste Asanovic (Massachusetts Institute of Technology), Jean-Loup
`Baer (University of Washington), David Brooks (Harvard University), Doug Clark
`(Princeton University), Dan Connors (University of Colorado at Boulder), Matt
`Farrens (University of California, Davis), Manoj Franklin (University of Maryland
`College Park), John Greiner (Rice University), David Harris (Harvey Mudd Col(cid:173)
`lege), Paul Hilfinger (University of California, Berkeley), Norm Jouppi (Hewlett(cid:173)
`Packard), David Kaeli (Northeastern University), David Oppenheimer (University
`of Californfa, Berkeley), Timothy Pinkston (University of Southern California),
`Mark Smotherman (Clemson University), and David Wood (University of Wis(cid:173)
`consin, Madison).
`To he]p us meet our goal of creating 70% new exercises and solutions for this
`edition, we recruited several graduate students recommended to us by their pro(cid:173)
`fessors. We are grateful for their creativity and persistence: Michael Black (Uni(cid:173)
`versity of Maryland), Lei Chen
`(University of Rochester), Nirav Dave
`(Massachusetts Institute of Technology), Wael El Essawy (University of Roches(cid:173)
`ter), Niki! Mehta (Brown University), Nicholas Nelson (University of Rochester),
`Aaron Smith (University of Texas, Austin), and Charlie Wang (Duke University).
`We would like to especially thank Mark Smotherman for making a careful final
`pass to find technical and writing glitches that significantly improved the quality
`of this edition.
`We wish to thank the extended Morgan Kaufmann family for agreeing to pub(cid:173)
`lish this book again under the able leadership of Denise Penro se. She developed
`the vision of the hybrid paper-CD book and recruited the many people above who
`played important roles in developing the book.
`Simon Crump managed the book production process, and Summer Block
`coordinated the surveying of users and their responses. We thank also the many
`freelance vendors who contributed to this volume, especially Nancy Logan and
`Dartmouth Publishing, Inc., our compositors.
`The contributions of the nearly 100 people we mentioned here have made this
`third edition our best book yet. Enjoy!
`
`David A. Patterson
`
`John L. Hennessy
`
`Oracle-1041 p. 18
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Computer
`Abstractions
`and Technology
`
`Civilization advances by extending
`the number of important operations
`which we can perform without
`thinking about them.
`
`Alfred North Whitehead
`An fotrod11clio11 to Mathematics, 1911
`
`Oracle-1041 p. 19
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`1.1
`1.2
`1.3
`1.4
`1.5
`1.6
`~ 1.7
`1.8
`
`Introduction 3
`Below Your Program 11
`Under the Covers 15
`Real Stuff: Manufacturing Pentium 4 Chips 28
`Fallacies and Pitfalls 33
`Concluding Remarks 35
`Historical Perspective and Further Reading 36
`Exercises 36
`
`■ Introduction
`
`Welcome to this book! We're delighted to have this opportunity to convey the
`excitement of the world of computer systems. Th.is is not a dry and drea ry field,
`where progress is glacial and where new ideas atrophy from neglect. No! Comput(cid:173)
`ers are the product of the incredibly vibrant information technology industry, alJ
`aspects of wh ich are responsible for almost 10% of the gross national product of
`the United States. This unusual industry embra