Computer Organization and Design: The Hardware/Software ...

1 THIRD EDITIONC omputer Organization DesignTHE Hardware/Software INTERFACEACKNOWLEDGEMENTSF igures , Courtesy of Courtesy of Storage Technology , , Courtesy of the Charles Babbage Institute,University of Minnesota Libraries, Minneapolis. Figures , , , , Courtesy of Courtesy of Cray Courtesy of Apple Computer , Courtesy of the Computer History Courtesy of , Courtesy of Museum of Science, Courtesy of MIPS Technologies, Peg Courtesy of the Computer Museum of Courtesy of the Commercial Computing , Courtesy of NASA Ames Research Courtesy of Lawrence Livermore National in the Real World:Photo of A Laotian villager, courtesy of David of an Indian villager, property of Encore Software, Ltd., of Block and students and a pop-up archival satellite tag, courtesy of Professor Barbara Block. Photos by Scott of Professor Dawson and student and the Mica micromote, courtesy of AP/World Wide of images of pottery fragments and a Computer reconstruc-tion, courtesy of Andrew Willis and David B.

2 Cooper, Brown University,Division of of the Eurostar TGV train, by Jos van der of the interior of a Eurostar TGV cab, by Andy of firefighter Ken Whitten, courtesy of World Economic of an artificial retina, The San Francisco by of A laser scan of Michelangelo s statue of David, courtesy ofMarc Levoy and Dr. Franca Falletti, director of the Galleria dell'Acca-demia, Italy. An image from the Sistine Chapel, courtesy of Luca Pezzati. IR imagerecorded using the scanner for IR reflectography of the INOA (NationalInstitute for Applied Optics, ) at the Opificio delle PietreDure in EDITIONC omputer Organization and DesignTHE Hardware/Software INTERFACED avid A. PattersonUniversity of California, BerkeleyJohn L. HennessyStanford UniversityWith a contribution byPeter J. AshendenJames R. LarusDaniel J. SorinAshenden Designs Pty LtdMicrosoft ResearchDuke UniversityAMSTERDAM BOSTON HEIDELBERG LONDONNEW YORK OXFORD PARIS SAN DIEGOSAN FRANCISCO SINGAPORE SYDNEY TOKYOM organ Kaufmann is an imprint of ElsevierSenior EditorDenise E.

3 M. PenrosePublishing Services ManagerSimon CrumpEditorial AssistantSummer BlockCover DesignRoss Caron DesignCover and Chapter IllustrationChris AsimoudisText DesignGGS Book ServicesCompositionNancy Logan and Dartmouth Publishing, IllustrationDartmouth Publishing, DellaPentaProofreaderJacqui BrownsteinIndexerLinda BuskusInterior printerCourierCover printerCourierMorgan Kaufmann Publishers is an imprint of Sansome Street, Suite 400, San Francisco, CA 94111 This book is printed on acid-free paper. 2005 by Elsevier Inc. All rights used by companies to distinguish their products are often claimed as trademarks or registeredtrademarks. In all instances in which Morgan Kaufmann Publishers is aware of a claim, the product namesappear in initial capital or all capital letters. Readers, however, should contact the appropriate companiesfor more complete information regarding trademarks and part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form orby any means electronic, mechanical, photocopying, scanning, or otherwise without prior written per-mission of the may be sought directly from Elsevier s Science & Technology Rights Department in Oxford,UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail: You mayalso complete your request on-line via the Elsevier homepage ( ) by selecting CustomerSupport and then Obtaining Permissions.

4 Library of Congress Cataloging-in-Publication DataApplication submittedISBN: 1-55860-604-1 For information on all Morgan Kaufmann publications,visit our Web site at in the United States of America04 05 06 07 08 5 4 3 2 1 ContentsvContentsPrefaceixCHAPTERSC omputer Abstractions and Technology Your the Stuff: Manufacturing Pentium 4 and Perspective and Further IN THE REAL WORLDI nformation Technology for the 4 Billion without IT 44 Instructions: Language of the Computer of the Computer of the Computer Instructions in the for Making Procedures in Computer with Addressing for 32-Bit Immediates and Translating and Starting a How Compilers How Compilers Work: An A C Sort Example to Put It All Implementing an Object-Oriented Arrays versus Real Stuff: IA-32 fallacies and Concluding Historical Perspective and Further Exercises147 COMPUTERS IN THE REAL WORLDH elping Save Our Environment with Data 156 Arithmetic for Computers and Unsigned and Stuff: Floating Point in the and Historical Perspective and Further Exercises229 COMPUTERS IN THE REAL WORLDR econstructing the Ancient World 236 Assessing and Understanding Performance Performance and Its Stuff: Two SPEC Benchmarks and the Performance of Recent Intel and Perspective and Further IN THE REAL WORLDM oving People Faster and More Safely 28034 ContentsviiThe Processor: Datapath and Control Design a Simple Implementation Multicycle : Simplifying Control Introduction to Digital Design Using a Hardware Design Stuff.

5 The Organization of Recent Pentium fallacies and Concluding Historical Perspective and Further Exercises354 COMPUTERS IN THE REAL WORLDE mpowering the Disabled 366 Enhancing Performance with Pipelining Overview of Pipelined Hazards and Hazards and a Hardware Description Language to Describe and Model a Pipelining: Extracting More Real Stuff: The Pentium 4 fallacies and Concluding Historical Perspective and Further Exercises454 COMPUTERS IN THE REAL WORLDMass Communication without Gatekeepers 46456viiiContentsLarge and Fast: Exploiting Memory Hierarchy Basics of and Improving Cache Common Framework for Memory Stuff: The Pentium P4 and the AMD Opteron Memory and Perspective and Further Exercises555 COMPUTERS IN THE REAL WORLDS aving the World's Art Treasures 562 Storage, Networks, and Other Peripherals Storage and and Other Connections between Processors, Memory, and I/O I/O Devices to the Processor, Memory, and Operating Performance Measures: Examples from Disk and File an I/O Stuff: A Digital and Concluding Historical Perspective and Further Exercises611 COMPUTERS IN THE REAL WORLDS aving Lives through Better Diagnosis 622 Multiprocessors and Clusters Connected by a Single Connected by a Network Inside a Chip and Stuff.

6 The Google Cluster of and Concluding Historical Perspective and Further Exercises9-55 APPENDICESA ssemblers, Linkers, and the SPIM Simulator Call and and MIPS R2000 Assembly Concluding ExercisesA-82 The Basics of Logic Design , Truth Tables, and Logic a Hardware Description a Basic Arithmetic Logic Addition: Carry Elements: Flip-flops, Latches, and Elements: SRAMs and Finite State Timing Field Programmable Concluding ExercisesB-79 Mapping Control to Hardware Combinational Control Finite State Machine the Next-State Function with a a Microprogram to Survey of RISC Architectures for Desktop, Server, and Embedded Computers Modes and Instruction : The MIPS Core Subset : Multimedia Extensions of the Desktop/Server RISCs : Digital Signal-Processing Extensions of the Embedded RISCs : Common Extensions to MIPS Unique to MIPS64 Unique to Unique to SPARC Instructions Unique to Instructions Unique to PA-RISC Instructions Unique to Instructions Unique to Instructions Unique to Instructions Unique to Instructions Unique to Concluding ReferencesD-47 EIndexI-1 GlossaryG-1 Further ReadingFR-1 CDPrefacexiPrefaceThe most beautiful thing we can experience is the is the source of all true art and Einstein, What I Believe, 1930 About This BookWe believe that learning in Computer science and engineering should reflect thecurrent state of the field, as well as introduce the principles that are shaping com-puting.

7 We also feel that readers in every specialty of computing need to appreci-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-cialty to understand both hardware and software. The interaction between hard-ware and software at a variety of levels also offers a framework for understandingthe fundamentals of computing. Whether your primary interest is hardware orsoftware, Computer science or electrical engineering, the central ideas in computerorganization and design are the same. Thus, our emphasis in this book is to showthe relationship between hardware and software and to focus on the concepts thatare the basis for current audience for this book includes those with little experience in assemblylanguage or logic design who need to understand basic Computer Organization aswell as readers with backgrounds in assembly language and/or logic design whowant to learn how to design a Computer or understand how a system works andwhy it performs as it the Other BookSome readers may be familiar with Computer Architecture: A QuantitativeApproach, popularly known as Hennessy and Patterson.

8 (This book in turn iscalled Patterson and Hennessy.) Our motivation in writing that book was todescribe the principles of Computer architecture using solid engineering funda-xiiPrefacementals and quantitative cost/performance trade-offs. We used an approach thatcombined examples and measurements, based on commercial systems, to createrealistic design experiences. Our goal was to demonstrate that Computer architec-ture could be learned using quantitative methodologies instead of a descriptiveapproach. It is intended for the serious computing professional who wants adetailed understanding of majority of the readers for this book do not plan to become Computer archi-tects. The performance of future software systems will be dramatically affected,however, by how well software designers understand the basic hardware tech-niques at work in a system. Thus, compiler writers, operating system designers,database programmers, and most other software engineers need a firm groundingin the principles presented in this book.

9 Similarly, hardware designers mustunderstand 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-rial in Computer Architecture, and the material was extensively revised to matchthe different audience. We were so happy with the result that the subsequent edi-tions of Computer Architecturewere revised to remove most of the introductorymaterial; hence, there is much less overlap today than with the first editions ofboth for the Third EditionWe 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-ware focus; improve pedagogy in general; enhance understanding of program per-formance; update the technical content to reflect changes in the industry since thepublication of the second edition in 1998; tie the ideas from the book more closelyto the real world outside the computing industry; and reduce the size of this , the table on the next page shows the hardware and software paths throughthe material.

10 Chapters 1, 4, and 7 are found on both paths, no matter what the expe-rience or the focus. Chapters 2 and 3 are likely to be review material for the hard-ware-oriented, but are essential reading for the software-oriented, especially forthose readers interested in learning more about compilers and object-oriented pro-gramming languages. The first sections of Chapters 5 and 6 give overviews for thosewith a software focus. Those with a hardware focus, however, will find that thesechapters present core material; they may also, depending on background, want toread Appendix B on logic design first and the sections on microprogramming andhow to use hardware description languages to specify control. Chapter 8 oninput/output is key to readers with a software focus and should be read if time per-mits by others. The last chapter on multiprocessors and clusters is again a questionof time for the reader. Even the history sections show this balanced focus; theyinclude short histories of programming languages, compilers, numerical software,operating systems, networking protocols, and Page Intentionally Left BlankPrefacexiiiChapter or AppendixSectionsSoftware Focus Hardware Focus1.