Computer Organization and Architecture 9th - USTC

1 Computer Organization AND ARCHITECTUREDESIGNING FOR PERFORMANCENINTH EDITIONW illiam StallingsBoston Columbus Indianapolis New York San Francisco Upper Saddle RiverAmsterdam Cape Town Dubai London Madrid Milan Munich Paris Montr al TorontoDelhi Mexico City S o Paulo Sydney Hong Kong Seoul Singapore Taipei TokyoCredits: Figure : reprinted with permission from The Computer Language Company, Inc. Figure : 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 : Reprinted with permission from Ethernet and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on the appropriate page within 2013, 2010, 2006 by Pearson Education, Inc., publishing as Prentice Hall. All rights reserved.

2 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 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 of Congress Cataloging-in-Publication Data available upon request10 9 8 7 6 5 4 3 2 1 ISBN 10: 0-13-293633-XISBN 13: 978-0-13-293633-0 Editorial Director: Marcia HortonExecutive Editor: Tracy DunkelbergerAssociate Editor: Carole SnyderDirector of Marketing: Patrice JonesMarketing Manager: Yez AlayanMarketing Coordinator: Kathryn FerrantiMarketing Assistant: Emma SniderDirector of Production: Vince O BrienManaging Editor: Jeff HolcombProduction Project Manager: Kayla Smith-TarboxProduction Editor: Pat BrownManufacturing Buyer: Pat BrownCreative Director: Jayne ConteDesigner: Bruce KenselaarManager, Visual Research: Karen SanatarManager, Rights and Permissions: Mike JoyceText Permission Coordinator: Jen RoachCover Art: Charles Bowman/Robert HardingLead Media Project Manager.

3 Daniel SandinFull-Service Project Management: Shiny Rajesh/ Integra Software Services Pvt. : Integra Software Services Pvt. : Edward BrothersCover Printer: Lehigh-Phoenix Color/HagerstownText Font: Times Ten-RomanTo Tricia (ATS), my loving wife, the kindest and gentlest personThis page intentionally left blank vOnline Resources xiPreface xiiiAbout the Author xxiChapter 0 Reader s and Instructor s Guide 1 Outline of the Book 2 A Roadmap for Readers and Instructors 2 Why Study Computer Organization and Architecture ? 3 Internet and Web Resources 5 PART ONE OVERVIEW 6 Chapter 1 Introduction 6 Organization and Architecture 7 Structure and Function 8 Key Terms and Review Questions 14 Chapter 2 Computer Evolution and Performance 15 A Brief History of Computers 16 Designing for Performance 37 Multicore, MICs, and GPGPUs 43 The Evolution of the Intel x86 Architecture 44 Embedded Systems and the ARM 45 Performance Assessment 49 Recommended Reading 59 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 Computer Components 66 Computer Function 68 Interconnection Structures 84 Bus Interconnection 85 Point-To-Point Interconnect 93 PCI Express 98 Recommended Reading 108 Key Terms.

4 Review Questions, and Problems 108 Chapter 4 Cache Memory 112 Computer Memory System Overview 113 Cache Memory Principles 120 Elements of Cache Design 123 CONTENTSvi CONTENTS Pentium 4 Cache Organization 141 ARM Cache Organization 144 Recommended Reading 146 Key Terms, Review Questions, and Problems 147 Appendix 4A Performance Characteristics of Two-Level Memories 152 Chapter 5 Internal Memory 159 Semiconductor Main Memory 160 Error Correction 170 Advanced DRAM Organization 174 Recommended Reading 180 Key Terms, Review Questions, and Problems 181 Chapter 6 External Memory 185 Magnetic Disk 186 RAID 195 Solid State Drives 205 Optical Memory 210 Magnetic Tape 215 Recommended Reading 217 Key Terms, Review Questions, and Problems 218 Chapter 7 Input/Output 221 External Devices 223 I/O Modules 226 Programmed I/O 228 Interrupt-Driven I/O 232 Direct Memory Access 240 I/O Channels and Processors 246 The External Interface.

5 Thunderbolt and Infiniband 248 IBM zEnterprise 196 I/O Structure 256 Recommended Reading 260 Key Terms, Review Questions, and Problems 260 Chapter 8 Operating System Support 265 Operating System Overview 266 Scheduling 277 Memory Management 283 Pentium Memory Management 294 ARM Memory Management 299 Recommended Reading 304 Key Terms, Review Questions, and Problems 304 PART THREE ARITHMETIC AND LOGIC 309 Chapter 9 Number Systems 309 The Decimal System 310 Positional Number Systems 311 The Binary System 312 Converting Between Binary and Decimal 312 CONTENTS vii Hexadecimal Notation 315 Recommended Reading 317 Key Terms and Problems 317 Chapter 10 Computer Arithmetic 319 The Arithmetic and Logic Unit 320 Integer Representation 321 Integer Arithmetic 326 Floating-Point Representation 341 Floating-Point Arithmetic 349 Recommended Reading 358 Key Terms, Review Questions.

6 And Problems 359 Chapter 11 Digital Logic 364 Boolean Algebra 365 Gates 368 Combinational Circuits 370 Sequential Circuits 388 Programmable Logic Devices 397 Recommended Reading 401 Key Terms and Problems 401 PART FOUR THE CENTRAL PROCESSING UNIT 405 Chapter 12 Instruction Sets: Characteristics and Functions 405 Machine Instruction Characteristics 406 Types of Operands 413 Intel x86 and ARM Data Types 415 Types of Operations 418 Intel x86 and ARM Operation Types 431 Recommended Reading 441 Key Terms, Review Questions, and Problems 441 Appendix 12A Little-, Big-, and Bi-Endian 447 Chapter 13 Instruction Sets: Addressing Modes and Formats 451 Addressing Modes 452 x86 and ARM Addressing Modes 459 Instruction Formats 464 x86 and ARM Instruction Formats 473 Assembly Language 477 Recommended Reading 479 Key Terms, Review Questions, and Problems 479 Chapter 14 Processor Structure and Function 483 Processor Organization 484 Register Organization 486 Instruction Cycle 491 Instruction Pipelining 495 The x86 Processor Family 512viii CONTENTS The ARM Processor 520 Recommended Reading 526 Key Terms, Review Questions.

7 And Problems 527 Chapter 15 Reduced Instruction Set Computers 531 Instruction Execution Characteristics 533 The Use of a Large Register File 538 Compiler-Based Register Optimization 543 Reduced Instruction Set Architecture 545 RISC Pipelining 551 MIPS R4000 556 SPARC 562 RISC Versus CISC Controversy 568 Recommended Reading 569 Key Terms, Review Questions, and Problems 569 Chapter 16 Instruction-Level Parallelism and Superscalar Processors 573 Overview 574 Design Issues 579 Pentium 4 589 ARM Cortex-A8 595 Recommended Reading 603 Key Terms, Review Questions, and Problems 605 PART FIVE PARALLEL Organization 611 Chapter 17 Parallel Processing 611 Multiple Processor Organizations 613 Symmetric Multiprocessors 615 Cache Coherence and the MESI Protocol 619 Multithreading and Chip Multiprocessors 626 Clusters 633 Nonuniform Memory Access 640 Vector Computation 644 Recommended Reading 656 Key Terms, Review Questions, and Problems 657 Chapter 18 Multicore Computers 664 Hardware Performance Issues 665 Software Performance Issues 669 Multicore Organization 674 Intel x86 Multicore Organization 676 ARM11 MPCore 679 IBM zEnterprise 196 Mainframe 684 Recommended Reading 687 Key Terms, Review Questions.

8 And Problems 687 CONTENTS ix Appendix A Projects for Teaching Computer Organization and Architecture 691 Interactive Simulations 692 Research Projects 694 Simulation Projects 694 Assembly Language Projects 695 Reading/Report Assignments 696 Writing Assignments 696 Test Bank 696 Appendix B Assembly Language and Related Topics 697 Assembly Language 698 Assemblers 706 Loading and Linking 710 Recommended Reading 718 Key Terms, Review Questions, and Problems 719 ONLINE CHAPTERS1 PART SIX THE CONTROL UNIT 19-1 Chapter 19 Control Unit Operation 19-1 Micro-operations 19-3 Control of the Processor 19-13 Hardwired Implementation 19-30 Recommended Reading 19-35 Key Terms, Review Questions, and Problems 19-35 Chapter 20 Microprogrammed Control 20-1 Basic Concepts 20-3 Microinstruction Sequencing 20-16 Microinstruction Execution 20-26 TI 8800 20-45 Recommended Reading 20-59 Key Terms, Review Questions, and Problems 20-60 ONLINE APPENDICES Appendix C Hash Tables Appendix D Victim Cache Strategies Victim Cache Selective Victim Cache 1 Online chapters, appendices, and other documents are Premium Content.

9 Available via the access card at the front of this CONTENTS Appendix E Interleaved Memory Appendix F The International Reference Alphabet Appendix G Virtual Memory Page Replacement Algorithms Optimal Least Recently Used First-In-First-Out Other Page Replacement Algorithms Appendix H Recursive Procedures Recursion Activation Tree Representation Stack Processing Recursion and Iteration Appendix I Additional Instruction Pipeline Topics Pipeline Reservation Tables Reorder Buffers Tomasulo s Algorithm Scoreboarding Appendix J Linear Tape Open Technology LTO Generations LTO Format LTO Operation Appendix K DDR SRAM Appendix L Protocols and Protocol Architectures Introduction The TCP/IP Protocol Architecture The Role of an Internet Protocol IPv4 IPv6 The OSI Protocol Architecture Appendix M Scrambling Appendix N Timing Diagrams Appendix O Stacks Stack Structure Stack Implementation Expression Evaluation Glossary 723 References 733 Index 745xiSiteLocationDescriptionCompanion Resources link: Useful links and documents for Resources link.

10 Useful links and documents for ContentClick on Premium Content link at Companion Website or at and enter the student access code found on the card in the front of the chapters, appendices, and other documents that supplement the Resource Center (IRC)Click on Pearson Resources for Instructors link at Companion Website or on Instructor Resource link at manual, projects manual, slides, and other useful Science Student Resource links and documents for Computer science RESOURCESThis page intentionally left blank xiiiWHAT S NEW IN THE NINTH EDITIONIn 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.