Computer Organization and Architecture: …

1 COMPUTERORGANIZATIONANDARCHITECTUREDESIG NING FORPERFORMANCEEIGHTHEDITIONW illiam StallingsPrentice HallUpper Saddle River, NJ 07458 Library of Congress Cataloging-in-Publication Data On FileVice President and Editorial Director:Marcia J. HortonEditor-in-Chief:Michael HirschExecutive Editor:Tracy DunkelbergerAssociate Editor:Melinda HaggertyMarketing Manager:Erin DavisSenior Managing Editor:Scott DisannoProduction Editor:Rose KernanOperations Specialist:Lisa McDowellArt Director:Kenny BeckCover Design:Kristine CarneyDirector, Image Resource Center:Melinda PatelliManager, Rights and Permissions:Zina ArabiaManager, Visual Research:Beth BrenzelManager, Cover Visual Research & Permissions:Karen SanatarComposition:Rakesh Poddar, Aptara , Image:Picturegarden / Image Bank /Getty Images, 2010, 2006 by Pearson Education, Inc.

2 , Upper Saddle River, New Jersey, Prentice Hall. All rights reserved. Printed in the United States of America. This publication is protectedby Copyright and permission should be obtained from the publisher prior to any prohibited reproduction, storagein a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying,recording, or likewise. For information regarding permission(s), write to: Rights and Permissions Prentice Hall is a trademark of Pearson Education, is a registered trademark of Pearson plcPrentice Hall is a registered trademark of Pearson Education, Education LTD. LondonPearson Education North Asia LtdPearson Education Singapore, Pte. LtdPearson Educaci n de Mexico, de Education, Canada, LtdPearson Education Malaysia, Pte.

3 LtdPearson Education JapanPearson Education, Upper Saddle River, New JerseyPearson Education Australia PTY, Limited10 9 8 7 6 5 4 3 2 1 ISBN-13: 978-0-13-607373-4 ISBN-10:0-13-607373-5To Tricia (ATS),my loving wife the kindestand gentlest personWEBSITEFORCOMPUTERORGANIZATIONANDA RCHITECTURE, EIGHTHEDITIONThe Web site at provides support for instructorsand students using the book. It includes the following Support Materials A set of PowerPointslides for use as lecture aids. Copies of figuresfrom the book in PDF format. Copies of tablesfrom the book in PDF format. Computer Science Student Resource Site:contains a number of links and docu-ments that students may find useful in their ongoing Computer science site includes a review of basic, relevant mathematics; advice on research,writing, and doing homework problems; links to Computer science researchresources, such as report repositories and bibliographies; and other useful links.

4 An errata sheetfor the book, updated at most Documents A set of supplemental homework problems with solutions. Students can en-hance their understanding of the material by working out the solutions tothese problems and then checking their answers. Three online chapters: number systems, digital logic, and IA-64 architecture Nine online appendices that expand on the treatment in the book. Topicsinclude recursion, and various topics related to memory. All of the Intel x86 and ARM architecture material from the book reproducedin two PDF documents for easy reference. Other useful documentsCOA CoursesThe Web site includes links to Web sites for courses taught using the book. Thesesites can provide useful ideas about scheduling and topic ordering, as well as a num-ber of useful handouts and other Web SitesThe Web site includes links to relevant Web sites.

5 The links cover a broad spectrumof topics and will enable students to explore timely issues in greater Mailing ListAn Internet mailing list is maintained so that instructors using this book can ex-change information, suggestions, and questions with each other and the author. Sub-scription information is provided at the book s Web Tools for COA ProjectsThe Web site includes a number of interactive simulation tools, which are keyed to thetopics of the book. The Web site also includes links to the SimpleScalar and SMPC acheweb sites. These are two software packages that serve as frameworks for project imple-mentation. Each site includes downloadable software and background Site for the Book ivAbout the Author xiPreface xiiiChapter 0 Reader s Guide of the Book Roadmap for Readers and Instructors Study Computer Organization and architecture and Web Resources 4 PART ONE OVERVIEW 7 Chapter 1 Introduction and architecture and Function Terms and Review Questions 15 Chapter 2 Computer Evolution and Performance Brief History of Computers for Performance Evolution of the Intel x86 architecture Systems and the ARM Assessment Reading and Web Sites Terms, Review Questions.

6 And Problems 59 PART TWO THE Computer SYSTEM 63 Chapter 3 A Top-Level View of Computer Function and Interconnection Components Function Structures Interconnection Reading and Web Sites Terms, Review Questions, and Problems 104 Appendix 3A Timing Diagrams 108 Chapter 4 Cache Memory Memory System Overview Memory Principles of Cache Design 4 Cache Organization Cache Organization Reading Terms, Review Questions, and Problems 146 Appendix 4A Performance Characteristics of Two-Level Memories 151 Chapter 5 Internal Memory Technology Main Memory Correction DRAM Organization Reading and Web Sites Terms, Review Questions, and Problems 180 Chapter 6 External Memory Disk Memory Tape Reading and Web Sites Terms, Review Questions, and Problems 214 Chapter 7 Input/Output Devices Modules I/O I/O Memory Access Channels and Processors External Interface: FireWire and Infiniband Reading and Web Sites Terms, Review Questions, and Problems 254 Chapter 8 Operating System Support System Overview Management Memory Management Memory Management Reading and Web Sites Terms, Review Questions, and Problems 299 PART THREE THE CENTRAL PROCESSING UNIT 303 Chapter 9 Computer Arithmetic Arithmetic and Logic Unit (ALU) Representation Arithmetic Representation Arithmetic Reading and Web Sites Terms, Review Questions, and Problems 344 CONTENTSviiChapter 10 Instruction Sets.

7 Characteristics and Functions Instruction Characteristics of Operands x86 and ARM Data Types of Operations x86 and ARM Operation Types Reading Terms, Review Questions, and Problems 385 Appendix 10 AStacks 390 Appendix 10 BLittle, Big, and Bi-Endian 396 Chapter 11 Instruction Sets: Addressing Modes and Formats and ARM Addressing Modes Formats and ARM Instruction Formats Language Reading Terms, Review Questions, and Problems 428 Chapter 12 Processor Structure and Function Organization Organization Instruction Cycle Pipelining x86 Processor Family ARM Processor Reading Terms, Review Questions, and Problems 476 Chapter 13 Reduced Instruction Set Computers (RISCs) Execution Characteristics Use of a Large Register File Register Optimization Instruction Set architecture Pipelining R4000 RISC versus CISC Controversy Reading Terms, Review Questions, and Problems 518 Chapter 14 Instruction-Level Parallelism and Superscalar Processors Issues 4 Cortex-A8 Reading Terms, Review Questions, and Problems 554viiiCONTENTSPART FOUR THE CONTROL UNIT 559 Chapter 15 Control Unit Operation of the Processor Implementation Reading Terms, Review Questions, and Problems 584 Chapter 16 Microprogrammed Control Concepts Sequencing Execution 8800 Reading Terms, Review Questions.

8 And Problems 625 PART FIVE PARALLEL Organization 627 Chapter 17 Parallel Processing Use of Multiple Processors Multiprocessors Coherence and the MESI Protocol and Chip Multiprocessors Memory Access Computers Computation Reading and Web Sites Terms, Review Questions, and Problems 677 Chapter 18 Multicore Computers Issues Performance Issues Organization x86 Multicore Organization MPCore Reading and Web Sites Terms, Review Questions, and Problems 705 Appendix AProjects for Teaching Computer Organization and architecture Simulations Projects Projects Language Projects Assignments Assignments Bank 712 CONTENTSixAppendix BAssembly Language and Related Topics Language and Linking Reading and Web Sites Terms, Review Questions, and Problems 736 ONLINE 19 Number Systems Decimal System Binary System between Binary and Decimal Notation Terms, Review Questions, and Problems 19-8 Chapter 20 Digital Logic Algebra Circuits Circuits Logic Devices Reading and Web Site Terms and Problems 20-39 Chapter 21 The IA-64 architecture Organization , Speculation, and Software Pipelining Instruction Set architecture Organization Reading and Web Sites Terms, Review Questions.

9 And Problems 21-32 ONLINE CHash TablesAppendix DVictim Cache Victim CacheAppendix EInterleaved MemoryAppendix FInternational Reference AlphabetAppendix GVirtual Memory Page Replacement AlgorithmsxCONTENTSA ppendix HRecursive Tree and IterationAppendix IAdditional Instruction Pipeline Reservation s AlgorithmAppendix JLinear Tape Open TechnologyAppendix KDDR SDRAMG lossary 740 References 750 Index 763xiABOUT THEAUTHORW illiam Stallings has made a unique contribution to understanding the broad sweep of tech-nical developments in Computer security, Computer networking and Computer has authored 17 titles, and counting revised editions, a total of 42 books on various as-pects of these subjects. His writings have appeared in numerous ACM and IEEE publica-tions, including the Proceedings of the IEEEand ACM Computing has 10 times received the award for the best Computer Science textbook of theyear from the Text and Academic Authors over 30 years in the field, he has been a technical contributor, technical manager,and an executive with several high-technology firms.

10 He has designed and implemented bothTCP/IP-based and OSI-based protocol suites on a variety of computers and operating sys-tems, ranging from microcomputers to mainframes. As a consultant, he has advised govern-ment agencies, Computer and software vendors, and major users on the design, selection, anduse of networking software and created and maintains the Computer Science Student Resource This site provides documents and links on a va-riety of subjects of general interest to Computer science students (and professionals). He is amember of the editorial board of Cryptologia, a scholarly journal devoted to all aspects Stallings holds a PhD from in Computer Science and a from NotreDame in electrical page intentionally left blank xiiiPREFACEOBJECTIVESThis book is about the structure and function of computers.