com COMPUTER ORGANIZATION AND ARCHITECTURE DESIGNING FOR PERFORMANCE NINTH EDITION William Stallings Boston Columbus Indianapolis New York San Francisco Upper Saddle River Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montréal Toronto Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo www.com Editorial Director: Marcia Horton Designer: Bruce Kenselaar Executive Editor: Tracy Dunkelberger Manager, Visual Research: Karen Sanatar Associate Editor: Carole Snyder Manager, Rights and Permissions: Mike Joyce Director of Marketing: Patrice Jones Text Permission Coordinator: Jen Roach Marketing Manager: Yez Alayan Cover Art: Charles Bowman/Robert Harding Marketing Coordinator: Kathryn Ferranti Lead Media Project Manager: Daniel Sandin Marketing Assistant: Emma Snider Full-Service Project Management: Shiny Rajesh/ Director of Production: Vince O’Brien Integra Software Services Pvt. Managing Editor: Jeff Holcomb Composition: Integra Software Services Pvt. Production Project Manager: Kayla Smith-Tarbox Printer/Binder: Edward Brothers Production Editor: Pat Brown Cover Printer: Lehigh-Phoenix Color/Hagerstown Manufacturing Buyer: Pat Brown Text Font: Times Ten-Roman Creative Director: Jayne Conte Credits: Figure 2.14: reprinted with permission from The Computer Language Company, Inc.10: Buyya, Rajkumar, High-Performance Cluster Computing: Architectures and Systems, Vol I, 1st edition, ©1999. Reprinted and Electronically reproduced by permission of Pearson Education, Inc.
Upper Saddle River, New Jersey, Figure 17.11: Reprinted with permission from Ethernet Alliance. Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on the appropriate page within text. Copyright © 2013, 2010, 2006 by Pearson Education, Inc., publishing as Prentice Hall. All rights reserved.
Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your request to 201-236-3290. Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks.
Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps. Library of Congress Cataloging-in-Publication Data available upon request 10 9 8 7 6 5 4 3 2 1 ISBN 10: 0-13-293633-X ISBN 13: 978-0-13-293633-0 www.com To Tricia (ATS), my loving wife, the kindest and gentlest person www.com This page intentionally left blank www.com CONTENTS Online Resources xi Preface xiii About the Author xxi Chapter 0 Reader’s and Instructor’s Guide 1 0.1 Outline of the Book 2 0.2 A Roadmap for Readers and Instructors 2 0.3 Why Study Computer Organization and Architecture? 3 0.4 Internet and Web Resources 5 PART ONE OVERVIEW 6 Chapter 1 Introduction 6 1.1 Organization and Architecture 7 1.2 Structure and Function 8 1.3 Key Terms and Review Questions 14 Chapter 2 Computer Evolution and Performance 15 2.1 A Brief History of Computers 16 2.2 Designing for Performance 37 2.3 Multicore, MICs, and GPGPUs 43 2.4 The Evolution of the Intel x86 Architecture 44 2.5 Embedded Systems and the ARM 45 2.8 Key Terms, Review Questions, and Problems 60 PART TWO THE COMPUTER SYSTEM 65 Chapter 3 A Top-Level View of Computer Function and Interconnection 65 3.5 Point-To-Point Interconnect 93 3.8 Key Terms, Review Questions, and Problems 108 Chapter 4 Cache Memory 112 4.1 Computer Memory System Overview 113 4.2 Cache Memory Principles 120 4.3 Elements of Cache Design 123 v www.com vi CONTENTS 4.4 Pentium 4 Cache Organization 141 4.5 ARM Cache Organization 144 4.7 Key Terms, Review Questions, and Problems 147 Appendix 4A Performance Characteristics of Two-Level Memories 152 Chapter 5 Internal Memory 159 5.1 Semiconductor Main Memory 160 5.3 Advanced DRAM Organization 174 5.5 Key Terms, Review Questions, and Problems 181 Chapter 6 External Memory 185 6.3 Solid State Drives 205 6.7 Key Terms, Review Questions, and Problems 218 Chapter 7 Input/Output 221 7.5 Direct Memory Access 240 7.6 I/O Channels and Processors 246 7.7 The External Interface: Thunderbolt and Infiniband 248 7.8 IBM zEnterprise 196 I/O Structure 256 7.10 Key Terms, Review Questions, and Problems 260 Chapter 8 Operating System Support 265 8.1 Operating System Overview 266 8.4 Pentium Memory Management 294 8.5 ARM Memory Management 299 8.7 Key Terms, Review Questions, and Problems 304 PART THREE ARITHMETIC AND LOGIC 309 Chapter 9 Number Systems 309 9.1 The Decimal System 310 9.2 Positional Number Systems 311 9.3 The Binary System 312 9.4 Converting Between Binary and Decimal 312 www.com CONTENTS vii 9.7 Key Terms and Problems 317 Chapter 10 Computer Arithmetic 319 10.1 The Arithmetic and Logic Unit 320 10.4 Floating-Point Representation 341 10.5 Floating-Point Arithmetic 349 10.7 Key Terms, Review Questions, and Problems 359 Chapter 11 Digital Logic 364 11.5 Programmable Logic Devices 397 11.7 Key Terms and Problems 401 PART FOUR THE CENTRAL PROCESSING UNIT 405 Chapter 12 Instruction Sets: Characteristics and Functions 405 12.1 Machine Instruction Characteristics 406 12.2 Types of Operands 413 12.3 Intel x86 and ARM Data Types 415 12.4 Types of Operations 418 12.5 Intel x86 and ARM Operation Types 431 12.7 Key Terms, Review Questions, and Problems 441 Appendix 12A Little-, Big-, and Bi-Endian 447 Chapter 13 Instruction Sets: Addressing Modes and Formats 451 13.2 x86 and ARM Addressing Modes 459 13.4 x86 and ARM Instruction Formats 473 13.7 Key Terms, Review Questions, and Problems 479 Chapter 14 Processor Structure and Function 483 14.5 The x86 Processor Family 512 www.com viii CONTENTS 14.6 The ARM Processor 520 14.8 Key Terms, Review Questions, and Problems 527 Chapter 15 Reduced Instruction Set Computers 531 15.1 Instruction Execution Characteristics 533 15.2 The Use of a Large Register File 538 15.3 Compiler-Based Register Optimization 543 15.4 Reduced Instruction Set Architecture 545 15.8 RISC Versus CISC Controversy 568 15.10 Key Terms, Review Questions, and Problems 569 Chapter 16 Instruction-Level Parallelism and Superscalar Processors 573 16.6 Key Terms, Review Questions, and Problems 605 PART FIVE PARALLEL ORGANIZATION 611 Chapter 17 Parallel Processing 611 17.1 Multiple Processor Organizations 613 17.3 Cache Coherence and the MESI Protocol 619 17.4 Multithreading and Chip Multiprocessors 626 17.6 Nonuniform Memory Access 640 17.9 Key Terms, Review Questions, and Problems 657 Chapter 18 Multicore Computers 664 18.1 Hardware Performance Issues 665 18.2 Software Performance Issues 669 18.4 Intel x86 Multicore Organization 676 18.6 IBM zEnterprise 196 Mainframe 684 18.8 Key Terms, Review Questions, and Problems 687 www.com CONTENTS ix Appendix A Projects for Teaching Computer Organization and Architecture 691 A.4 Assembly Language Projects 695 A.5 Reading/Report Assignments 696 A.7 Test Bank 696 Appendix B Assembly Language and Related Topics 697 B.3 Loading and Linking 710 B.5 Key Terms, Review Questions, and Problems 719 ONLINE CHAPTERS1 PART SIX THE CONTROL UNIT 19-1 Chapter 19 Control Unit Operation 19-1 19.2 Control of the Processor 19-13 19.5 Key Terms, Review Questions, and Problems 19-35 Chapter 20 Microprogrammed Control 20-1 20.6 Key Terms, Review Questions, and Problems 20-60 ONLINE APPENDICES Appendix C Hash Tables Appendix D Victim Cache Strategies D.2 Selective Victim Cache 1 Online chapters, appendices, and other documents are Premium Content, available via the access card at the front of this book.com x CONTENTS Appendix E Interleaved Memory Appendix F The International Reference Alphabet Appendix G Virtual Memory Page Replacement Algorithms G.2 Least Recently Used G.3 First-In-First-Out G.4 Other Page Replacement Algorithms Appendix H Recursive Procedures H.2 Activation Tree Representation H.4 Recursion and Iteration Appendix I Additional Instruction Pipeline Topics I.1 Pipeline Reservation Tables I.4 Scoreboarding Appendix J Linear Tape Open Technology J.3 LTO Operation Appendix K DDR SRAM Appendix L Protocols and Protocol Architectures L.2 The TCP/IP Protocol Architecture L.3 The Role of an Internet Protocol L.6 The OSI Protocol Architecture Appendix M Scrambling Appendix N Timing Diagrams Appendix O Stacks O.3 Expression Evaluation Glossary 723 References 733 Index 745 ONLINE RESOURCES Site Location Description Companion Website WilliamStallings.com/ Student Resources link: Useful links ComputerOrganization and documents for students. Instructor Resources link: Useful links and documents for instructors. Premium Content Click on Premium Content link Online chapters, appendices, and other at Companion Website or at documents that supplement the book.com/stallings and enter the student access code found on the card in the front of the book.
Instructor Resource Click on Pearson Resources for Solutions manual, projects manual, Center (IRC) Instructors link at Companion slides, and other useful documents. Website or on Instructor Resource link at pearsonhighered. Computer Science ComputerScienceStudent.com Useful links and documents for Student Resource Site computer science students. xi This page intentionally left blank PREFACE WHAT’S NEW IN THE NINTH EDITION In the four years since the eighth edition of this book was published, the field has seen con- tinued innovations and improvements.
In this new edition, I try to capture these changes while maintaining a broad and comprehensive coverage of the entire field. To begin this process of revision, the eighth edition of this book was extensively reviewed by a number of professors who teach the subject and by professionals working in the field. The result is that, in many places, the narrative has been clarified and tightened, and illustrations have been improved. Beyond these refinements to improve pedagogy and user-friendliness, there have been substantive changes throughout the book.
Roughly the same chapter organization has been retained, but much of the material has been revised and new material has been added. The most noteworthy changes are as follows: • Point-to-point interconnect: The traditional bus architecture has increasingly been re- placed with high-speed point-to-point interconnect schemes. A new section explores this technology, using Intel’s QuickPath Interconnect (QPI) as an example. • PCI Express: PCI Express (PCIe) has become a standard peripheral interconnect archi- tecture, replacing PCI and other bus-based architectures.
A new section covers PCIe. • Solid state drive and flash memory: Solid state drives are increasingly displacing hard disk drives over a range of computers. A new section covers SSDs and the underlying flash memory technology. • IEEE 754 Floating-Point Standard: The coverage of IEEE 754 has been updated to reflect the 2008 standard.
• Contemporary mainframe organization: Chapters 7 and 18 include sections on the zEnterprise 196, IBM’s latest mainframe computer offering (at the time of this writing), introduced in 2010. • I/O standards: The book has been updated to reflect the latest developments, including Thunderbolt. • Multicore architecture: The material on multicore architecture has been expanded sig- nificantly. • Student study aids: Each chapter now begins with a list of learning objectives.
xiii xiv PREFACE • Sample syllabus: The text contains more material than can be conveniently covered in one semester. Accordingly, instructors are provided with several sample syllabi that guide the use of the text within limited time (e., 16 weeks or 12 weeks). These samples are based on real-world experience by professors with the eighth edition. • Test bank: A set of review questions, including yes/no, multiple choice, and fill in the blank is provided for each chapter.
With each new edition it is a struggle to maintain a reasonable page count while adding new material. In part this objective is realized by eliminating obsolete material and tighten- ing the narrative. For this edition, chapters and appendices that are of less general interest have been moved online, as individual PDF files. This has allowed an expansion of material without the corresponding increase in size and price.
OBJECTIVES This book is about the structure and function of computers. Its purpose is to present, as clearly and completely as possible, the nature and characteristics of modern-day computer systems. This task is challenging for several reasons. First, there is a tremendous variety of prod- ucts that can rightly claim the name of computer, from single-chip microprocessors costing a few dollars to supercomputers costing tens of millions of dollars.
Variety is exhibited not only in cost but also in size, performance, and application. Second, the rapid pace of change that has always characterized computer technology continues with no letup.