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.

2 , 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. 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.

3 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.

4 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.

5 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.

6 You mayalso complete your request on-line via the Elsevier homepage ( ) by selecting CustomerSupport and then Obtaining Permissions. 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.

7 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.

8 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: 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.

9 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.

10 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: 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.