Declaration ofRachel J. Waiters on Authentication ofPublication
`
`1, Rachel J. Watters, am a librarian, and the Director of Wisconsin TechSearch
`
`(“WTS”), located at 728 State Street, Madison, Wisconsin, 53706. WTS is an
`
`interlibrary loan department at the University of Wisconsin-Madison.
`
`[ have worked as
`
`a librarian at the University of Wisconsin library system since 1998.
`
`I have been
`
`employed at WTS since 2002, first as a librarian and, beginning in 2011, as the Director.
`
`Through the course of my employment, I have become well informed about the
`
`operations ofthe University of Wisconsin library system, which follows standard library
`
`practices.
`
`This Declaration relates to the dates of receipt and availability of the following:
`
`Henncssy, J.L. and Patterson, D.A. (1998) Computer
`Organization and Design: the Hardware/Software Interface. San
`Francisco, CA: Morgan Kaufmann Publishers.
`
`
`Standard 0 eratin )mcedures ornratericdsatthe Universit *0 Wisconsin-
`
`Madison Libraries. When a volume was received by the Library, it would be checked
`
`in, added to library holdings records, and made available to readers as soon after its
`
`arrival as possible. The procedure normally took a few days or at most 2 to 3 weeks.
`
`Exhibit A to this Declaration is true and accurate copy ofthe front matter of the
`
`Computer Organization and Design: the Hardware/Sqflware Interface (1998)
`
`publication, which includes a stamp on the verse page showing that this book is the
`
`property of the University of Wisconsin-Madison Libraries.
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`Declaration of Rachel J. Watters on Authentication of Publication
`
`Attached as Exhibit B is the cataloging system record of the University of
`
`Wisconsin-Madison Libraries for its copy of the Computer Organization and Design:
`
`the Hardware/Software Interface (1998) publication. As shown in the “Receiving date”
`
`field of this Exhibit, the University of Wisconsin-Madison Libraries owned this book
`
`and had it cataloged in the system as of June 6, 1999.
`
`Members of the interested public could locate the Computer Organization and
`
`Design: the Hardware/Sofhvare Interface (1998) publication after it was cataloged by
`
`searching the public library catalog or requesting a search through WTS. The search
`
`could be done by title, author, and/0r subject key words. Members of the interested
`
`public could access the publication by locating it on the library’s shelves or requesting it
`
`from WTS.
`
`I declare that all statements made herein of my own knowledge are true and that
`
`all statements made on information and belief are believed to be true; and further that
`
`these statements were made with the knowledge that willful false statements and the like
`
`so made are punishable by fine or imprisonment, or both, under Section 1001 of Title 18
`
`0f the United States Code.
`
`Date: January 30, 2020
`
`
`'
`- Z
`Rachel/J. Watters
`
`Wisconsin TechSearch
`
`Director
`
`Memorial Library
`728 State Street
`
`Madison, Wisconsin 53706
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`SECOND EDITION
`
`Computer Organization and Design
`
`THE HARDWARE/SOFTWARE INTERFACE
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`TRADEMARKS
`
`The following trademarks are the property of the following organizations:
`
`TeX is a trademark of Americal Mathematical Society.
`Apple II and Macintosh are trademarks of Apple Computers, Inc.
`CDC 6600, CDC F’bUU, CDC STAR-100, CYBER-ilill, CYBER-
`ltltl,’990, and CYBER—ZOS are trademarks of Control Data Corpora—
`tion.
`
`The Cosmic Cube is a trademark of California Institute of Technol—
`ogy.
`
`C P3100 is a trademark of Courier Peripherals.
`Cray, CRAY—I, CRAY J90, CRAY T00, CRAY X-MP/«llo, and
`CRAY Y-M IJ are trademarks of Cray Research.
`
`Alpha, AlphaS-erver. AlphaStatiou, DEC, DECsystem, DECsystem
`3100, DEC-station, PDP-ti, I’DP—II, Unilaus, VAX, VA): 37010, and
`VnXil HBO are trademarks of Digital Equipment Corporation.
`M P2361 A, Super Eagle, Vl’tUtt, VPEUU, and Vt’I’ItUU are trademarks
`of Fujitsu Corporation.
`Gnu C Compiler is a trademark of Free Software Foundation.
`Goodyear M01" is a trademark of Goodyear Tire and Rubber C0,,
`Inc.
`
`Apollo DN 300, Apollo DN 10000, Convex. Ill“, Hi’ Precision
`Architecture, HPI’A, HI’850, HP 3000, HP 300/?0, I’i‘t-RISC, and
`Precision are registered trademarks of Hewlet—l’ackard Company.
`432, 960 CA, 4004, 3008, 8080, 3050, 805?, 8038, 801313, 30286, 80330.
`30486, Delta, iAI’X 432, ism, Intet, lntelxitib, Intel Hypercube, iP—
`SC/Z, MMX, Multibus, Multibus ll, Paragon, and Pentium are
`trademarks of Intel Corporation. Intel Inside is a registered trade'
`mark of Intel Corporation.
`360. 360/30, 300/40, 360/50, 300/65, 360MB, 300/01. , 3?0, 370/158,
`370/ 165, 3?0/168, 3?l1—XA, BSA/3m, 70] , 3’04, 709, 801, 3033, 3030,
`3030 series, 3080 VF, 3081, 3090, 3000/1110, 3090;200, 3090/400,
`3090/600, 3090/6005, 3090 VP, 3330, 3380, 33801.), 3380 Disk Model
`AK4, 3380], 3390, 3350-23, 3990, 7090, F094, IBM, IBM I’C, IBM PC-
`AT, IBM 5V5. ISAM, MVS, PI..S, I’owerPC, POWERstation, RT‘I’C,
`RAMAC, IRS/6000, Sage, Stretch, System/360, Vector Faility. and
`VM are trademarks of International Business Machines Corpora—
`tion. POWERserver, RISC System/6000, and SP2 are registered
`trademarks of International Business Machines Corporation.
`[C L. DAIJ is a trademark of international Computers Limited.
`Inmos and Transputer are trademarks of bones.
`FutureBus is a trademark of the Institute of Electrical and Electron-
`ic Engineers.
`KSR-l 15 a trademark of Kendall Square Research.
`
`MASPAR MP—l and MASPAR NIP-2 are trademarks of MasPar
`Corporation.
`MIPS, R2000, R3000, and RItJDDU are registered trademarks of
`MIPS Technology, Inc.
`Windows is a trademark of MicroSoft Corporation.
`NuEus is a trademark of Massachusetts Institute of Technology.
`Delta Series sans, System V/SH R32VI, VME bus, 6809, 68000.
`{08010, 68020, h9030, b92581, 68832, 88000, 38000 1.8.4ml4, 88100.
`and 38200 are trademarks of Motorola Corporation.
`Ncube and nCube / ten are trademarks of Ncube Corporation.
`NEC is a registered trademark of NEC Corporation.
`Network Computer is a trademark of Oracle Corporation.
`’arsytec CC is a trademark of t’arsytec, Inc.
`Imprimis',
`lPl—2, Sabre, Sabre 0.720“, Seagate, and Wren IV are
`trademarks of Seagate Technology, Inc.
`NUMA—Q, Seouent, and Symmetry are trademarks of Sequent
`Computers.
`Power Challenge, Silicon Graphics, Silicon Graphics 43/240,
`Silicon Graphics «1th10, Silicon Graphics 4D!240, and Silicon
`Graphics 4B Series are trademarks of Silicon Graphics. Origin2000
`is a registered trademark of Silicon Graphics.
`SPEC is a registered trademark of the Standard Performance Eval—
`uation Corporation.
`Spice is a trademark of University of California at Berkeley.
`Enterprise, Java, Sun, Sim Ultra, Sun Microsystems, and Ultra are
`trademarks of Sun Mirrosystems, lnc. SI‘ARC and UltraSPARC
`are registered trademarks oiSlJARC International, Inc., licensed to
`Sun Microsystems, Inc.
`Connection Machine, CM-Z‘. and CM-S are trademarks of Thinking
`Machines.
`
`Burroughts 55:10, 35000. 35500, D—machine, UNIVAC, UNIVAC I,
`and UNIVAC 110-3 are trademarks of UN ISYS.
`Alto, PA RC, Palo Alto Research Center. and Xerox are trademarks
`of Xerox Corp nra tion.
`The UNIX trademark is IiCensecI exclusively through X/Open
`Company Ltd.
`All other product: names are trademarks or registered trademarks
`of their respective companies. Where trademarks appear in this
`book and Morgan Kaufmann Publishers was aware of a trademark
`claim, the trademarks haw.- been printed in initial caps or all caps.
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`SECOND EDITION
`
`Computer Organization and Design
`
`'I'HE HARDWARE/SOFTWARE INTERFACE
`
`John L. Honneasy
`
`Stanford University
`
`David A. Patterson
`
`University of California, Berkeley
`
`With a contribution by
`James R. Larus
`
`University of Wisconsin
`
`7
`M I. 4
`
`Morgan Kaufmann Publishers, Inc.
`
`San Francisco, California
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`Kurt K. Wendi Library _
`University of Wisconsin—Madison
`215 N. Randall Avenue
`5”"‘°""“"“°' ”W Madison,Wl 53706-1688
`Production Manager Ynnie Overton
`Production Editor
`Julie Pabst
`Editorial Coordinator
`Jane Elliott
`'l'oxt and Cover Design Ross Carton Design
`lllultrltlon Alexander Tesbin Associates, with second edition modifications by Dartmouth
`Publishing. Inc.
`chapter Opener Illustrations Canary Studios
`Copyeditor Ken DelIaPenta
`Composition Nancy Logan
`Proofreader
`Jennifer McClain
`Indexer Steve Rath
`Printer Courier Corporation
`
`Morgan Kaufmann Publishers, Inc.
`Editorial and Sales Office:
`340 Pine Street, Sixth Floor
`San Francisco, CA ‘i-IIIJ-l—JZE‘I‘S
`USA
`
`~11 5! 3‘9 2—3165
`Telephone
`415/932-2b65
`Facsimile
`Email mkpt‘ymltprom
`WWW Itttp://wrutrrarikpxom
`Order toll free 300/?45-7323
`
`lg 1998 by Morgan Kaufmann Publishers, Inc.
`All rights reserved
`Printed in the United States of America
`
`02
`
`01
`
`lit]
`
`“9
`
`5
`
`4
`
`3
`
`2
`
`No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form
`or by any meme—electronic, mechanical, photocopying, recording; 0!" DIHEI'WiSE—Withflut the prior
`written permission of the publisher.
`
`Advice, Pralse, and Errors: Any currespumlenCe related to this publication or intended for the authors
`should lie sent electronically to r'urfllrn‘es-ei'”drum-um. Informatinn regarding error sightings is encouraged.
`An}; error sightings that a re accepted for correction in subsequent printings will be rewarded by the
`authors with a payment at 31ml [LIL-3.} per correction at the time of their implementation in a reprint.
`“hirer;f of Congress Cataloging-irrPubltcatlon Date
`Patterson, David A.
`the hardware}software interlace
`Computer organization and design :
`X David A. I‘attersun, John |._ Hen messy—2nd ed.
`I"
`CITI.
`Includes bibliographical references and index.
`ISBN l—5SRhIJ—428vh (clnthl.—ISBN 1-5."\tihtl—-IHI-X {paper}
`1. Computer organization. 2. Computers—Design and construction.
`3. Computer interfaces.
`l. Hennessy, John L.
`[1. Title
`QAFMLCEvlitl-Hu
`1W?
`”Eliza—dell
`97-1h05ll
`
`
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`Contents
`viii
`
`
`Contents
`
`Foreword vi
`by john H. Crmiifom‘
`
`Worked Examples
`
`xiii
`
`Computer Organization and Design Online
`
`xvi
`
`Preface xix
`
`CHAPTERS
`
`a Computer Abstractions and Technology 2
`
`Introduction 3
`Below Your Program 5
`Under the Covers
`10
`
`4.1
`1.2
`“1.3
`' 1.4
`.,1-5
`1.8
`
`Integrated Circuits: Fueling Innovation 21
`Real Stuff: Manufacturing Pentium Chips
`Fallacies and Pitfalls
`29
`Concluding Remarks
`30
`f 1.7
`Historical Perspective end Further Reading 32
`_ 11.3
`1.9
`Key Terms 44
`~ 1.10 Exercises
`45
`
`24
`
`n The Role of Performance 52
`
`2.1
`2.2
`2.3
`2.4
`2.5
`2.8
`
`2.7
`2.8
`
`Introduction 54
`
`Measuring Performance 58
`Relating the Metrics
`60
`Choosing Programs to Evaluate Performance 60
`Comparing and Summarizing Performance 69
`Real Stuff: The SPEC95 Benchmarks and Performance of Recent
`Processors
`71
`Fallacies and Pitfalls
`Concluding Remarks
`
`75
`32
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`Contents
`ix
`
`2.9
`2.10
`2.11
`.———-"'
`
`Historical Perspective and Further Reading 83
`Key Terms
`80
`Exercises
`Lil]
`
`a Instructions: Language of the Machine
`
`104
`
`Introduction
`
`106
`
`3.1
`3.2
`3.3
`3.4
`3.5
`3.6
`3.7
`3.8
`3.9
`3.10
`3.11
`3.12
`3.13
`3.14
`3.15
`3.16
`3.1?
`
`116
`
`132
`
`Operations of the Computer Hardware 107
`Operands of the Computer Hardware
`Int}
`Representing Instructions in the Computer
`Instructions for Making Decisions
`122
`Supporting Procedures in Computer Hardware
`Beyond Numbers
`142
`other Styles of MIPS Addressing 145
`Starting a Program 15h
`An Example to Put It All Together
`Arrays versus Pointers
`171
`Real Stuff: PowerPC and 80x86 Instructions 175
`Fallacies and Pitfalls
`185
`Concluding Remarks
`187
`Historical Perspective and Further Reading 189
`Key Terms
`1%
`Exercises
`1%
`
`1(13
`
`n Arithmetic for Computers
`
`203
`
`4.1
`
`Introduction 210
`
`‘14.:
`14.3
`4.4
`4.5
`4.6
`4.7
`4.8
`4.9
`4.10
`.11
`4.12
`4.13
`4.14
`
`
`
`:10
`
`Signed and Unsigned Numbers
`Addition and Subtraction 220
`Logical Operations 25
`Constructing an Arithmetic Logic Unit 230
`Multiplication 250
`Division 265
`275
`Floating Point
`Real Stuff: Floating Point in the Power-PC and 80x86 301
`Fallacies and Pitfalls
`304
`Concluding Remarks
`30H
`Historical Perspective and Further Reading 312
`Key Terms
`322
`Exercises
`322
`
`a The Processor: Datapath and Control
`
`3%
`
`_5_.1
`5;?-
`5.3
`
`Introduction 338
`
`Building a Datapath 343
`A Simple Implementation Scheme 351
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`CDI'IIOI‘I‘!
`
`5.4 A Multicycle Implementation 37?
`5.5 Microprogramming: Simplifying Control Design 399
`5.6 Exceptions
`410
`5.7 Real Stuff: The Pentium Pro Implementation 416
`5.6 Fallacies and Pitfalls 419
`
`421
`5.6 Concluding Remarks
`5.10 Historical Perspective and Further Reading 423
`5.11 Key Terms
`426
`5.12 Exercises 427
`
`n Enhancing Performance with Pipelining 434
`
`3:1 An Overview of Pipelining 436
`8.2 A Pipelined Datapath 449
`6.3 Pipelined Control
`466
`6.4 Data Hazards and Forwarding 476
`6.5 Data Hazards and Stella 489
`6.6 Branch Hazards
`496
`6.7 Exceptions
`505
`6.6 Superscalar and Dynamic Pipelining 510
`6.9 Real Stuff: PowerPC 604 and Pentium Pro Pipelines
`6.10 Fallacies and Pitfalls
`520
`6.11 Concluding Remarks
`521
`6.12 Historical Perspective and Further Reading 525
`6.13 Key Terms
`529
`6.14 Exercises
`529
`
`517
`
`a Large and Fast: Exploiting Memory Hierarchy 538
`
`Introduction 540
`7.1
`545
`7.2 The Basics of Caches
`7.3 Measuring and Improving Cache Performance 564
`7.4 Virtual Memory 579
`7.5 A Common Framework for Memory Hierarchies 603
`7.6 Real Stuff: The Pentium Pro and Powe rPC 604 Memory Hierarchies 611
`7.7 Fallacies and Pitfalls 615
`
`618
`7.6 Concluding Remarks
`7.9 Historical Perspective and Further Reading 621
`7.10 Key Terms
`627
`7.11 Exercises
`628
`
`n Interfacing Processors and Peripherals
`
`636
`
`6.1
`
`Introduction 638
`
`6.2
`
`I/0 Performance Measures: Some Examples from Disk and File
`Systems
`641
`6.3 Types and Characteristics of I/O Devices 644
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`Contents
`
`J“
`
`8.4 Buses: Connecting I/O Devices to Processor and Memory 055
`8.5
`Interfacing l/O Devices to the Memory, Processor, and Operating
`System 073
`8.6 Designing an I/O System {#44
`8.7 Real Stuff: A Typical Desktop l/O System {387
`8.8 Fallacies and Pitfalls
`{2188
`
`(NU
`8.9 Concluding Remarks
`8.10 Hlsterical Perspective and Further Reading (194
`8.11 Key Terms
`700
`8.12 Exercises
`700
`
`a Multiprocessors
`
`91
`
`Introduction 712
`
`7m
`
`-
`
`Programming Multiprocessors 7H
`9.2
`9.3 Multiprocessors Connected by a Single Bus 717
`9.4 Multiprocessors Connected by a Network 727
`9.5 Clusters
`7’34
`
`73h
`9.6 Network Topologies
`9.7 Real Stuff: Future Directions for Multiprocessors
`9.8 Fallacies and Pitfalls
`743
`
`740
`
`9.9 Concluding Remarks—Evolution versus Revolution in Computer
`Architecture 7%
`
`9.10 Historical Perspective and Further Reading 748
`9.11 Key Terms
`75b
`9.12 Exercises 7%
`
`APPENDICES
`
`u Assemblers, Linkers, and the SPIM Simulator A-2
`
`by flames R. Lflms, University of Wisconsin
`11.1
`Introduction A»3
`A.2 Assemblers A-lD
`A.3 Linkers A—i?
`A.4 Loading A—19
`A.5 Memory Usage A-Zn
`11.6 Procedure Call Convention A-22
`
`11.? Exceptions and Interrupts A-32
`A.8
`Input and Output A-Bh
`A.9
`SPIM A38
`
`A.10 MIPS R2000 Assembly Language A49
`A.11 Concluding Remarks
`A—F’F
`11.12 Key Terms A—7c
`11.13 Exercises A-7h
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`xii
`
`Contents
`
`n The Basics of Logic Design B-Z
`
`3.1 Introduction 33
`
`3.2 Gates, Truth Tables, and Logic Equations 8-4
`3.3 Combinational Logic 8-8
`3.4 Clocks B-IB
`8-21
`3.5 Memory Elements
`3.6 Finite state Machines B-35
`3.1 Timing Methodologies
`3—39
`3.8 Concluding Remarks 344
`3.9 Key Terms B45
`3.10 Exercises 8-45
`
`B Mapping Control to Hardware 02
`
`0.1
`
`Introduction C—3
`
`0.2 Implementing Combinational Control Units 04
`0.3 Implementing Finite State Machine Control
`C—B
`0.4 Implementing the Next-State Function with a Sequencer C—21
`0.5 Translating a Microprogram to Hardware C-ZB
`0.6 Concluding Remarks
`C—31
`0.7 Key Terms C-32
`0.3 Exercises C-32
`
`Glossary (3-1
`
`Index 1-1
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`ganeig: “meg, oyflam
`:1f.Jigsaw;fint ‘Jciscomin-L’iedéson
`.
`.{u §_-.¢aite utiee;
`iamun. ”Hi; “Eh":S-‘fm-i
`‘
`I‘.‘
`.
`
`K.F. WENDT LIBRARY
`UW COLLEGE OF ENGR.
`215 N. RANDALL AVENUE
`MANSON “1| 53706
`
`INTEL -1013
`
`INTEL - 1013
`
`

`

`B‘IDHESDIDHH
`
`WlllfllHWI
`
`
`
`
`
`VII“W4NWI‘IWIWW
`
`389096501044A
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`LIBRARIES
`
`Alma
`
`Computer organization and design : the hardware/soft
`/ ware interface / John L. Hennessy, David A. Patterson ;
`g! with a contribution by James R. Larus. Hennessy, John
`
`0
`
`L. Morgan Kaufmann Publishers, San Francisco, Calif. :
`1998 [155860491X (paper)]
`
`Holdings
`
`Steenbock Library: Steenbock Stacks; QA76.9 C643 H46 1993 1
`
`Holdings ID
`
`22865152910002122
`
`Barcode
`
`Item ID
`
`View all holdings
`89096501 044
`
`23623132570002122
`
`View all items
`
`Process type
`
`Loan
`
`Status
`
`Item not in place
`
`Browse shelf listing
`
`General
`
`ENUMICHRON
`
`Notes
`
`History
`
`R
`
`General Information
`
`Barcode
`
`89096501044
`
`Material type
`
`Book
`
`Item policy
`
`general (book)
`
`Is magnetic
`
`No
`
`PD Line
`
`Select from a list
`
`v
`
`V
`
`V
`
`V
`
`55
`
`Receiving date
`
`061061'1999
`
`x 3
`
`Expected receiving
`date
`
`Enumeration A
`
`Enumeration B
`
`:|
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`I
`
`Chronology I
`
`Chronology J
`
`Description
`
`r—N
`
`| Generate
`
`
`
`l
`
`u—a
`import
`[
`:]
`
`Pages
`
`Pieces
`
`Replacement cost
`
`Receiving operator
`
`Physical condition
`
`Process type
`
`J J
`
`Inventory Information
`
`Inventory number
`
`Inventory date
`
`Inventory price
`
`Clear Inventory Information
`
`Location Information
`
`Permanent location
`
`Steenbock Library: Steenbock Stacks (stir)
`
`Item call number
`
`type
`
`Item call number
`
`Source {Subfleld 2)
`
`Storage location ID
`
`Temporary Location Information
`
`Item is in temporary
`location
`
`No 0 Yes
`
`Temporary location
`
`:]
`
`INTEL - 1013
`
`INTEL - 1013
`
`

`

`(cid:56)(cid:73)(cid:81)(cid:84)(cid:83)(cid:86)(cid:69)(cid:86)(cid:93) (cid:71)(cid:69)(cid:80)(cid:80)
`Temporary call
`(cid:82)(cid:89)(cid:81)(cid:70)(cid:73)(cid:86) (cid:88)(cid:93)(cid:84)(cid:73)
`number type
`(cid:56)(cid:73)(cid:81)(cid:84)(cid:83)(cid:86)(cid:69)(cid:86)(cid:93) (cid:71)(cid:69)(cid:80)(cid:80)
`Temporary call
`number
`(cid:82)(cid:89)(cid:81)(cid:70)(cid:73)(cid:86)
`
`(cid:55)(cid:83)(cid:89)(cid:86)(cid:71)(cid:73) (cid:12)(cid:55)(cid:89)(cid:70)(cid:444)(cid:73)(cid:80)(cid:72) (cid:22)(cid:13)
`Source (Subfield 2)
`
`(cid:56)(cid:73)(cid:81)(cid:84)(cid:83)(cid:86)(cid:69)(cid:86)(cid:93) (cid:77)(cid:88)(cid:73)(cid:81)
`Temporary item
`(cid:84)(cid:83)(cid:80)(cid:77)(cid:71)(cid:93)
`policy
`
`Due back date
`(cid:40)(cid:89)(cid:73) (cid:70)(cid:69)(cid:71)(cid:79) (cid:72)(cid:69)(cid:88)(cid:73)
`
`(cid:142)
`
`INTEL - 1013
`
`INTEL - 1013
`
`