Carl Hamacher et al.: Computer Organization, SEG(SBN 0-07-112218-4). Copyright © 2002 by The McGraw-Hill Companies, Inc. All rights reserved. Jointly published by China Machine Press/McGraw-Hill. This edition may be sold in the People's Republic of China only. This book cannot be re- exported and is not for sale outside the People's Republic of China. AERC GAR eh SS McGraw-Hill 4 ALAR Wy LE BK ARABRRARRT, RAMA, KELEMAR DR. Ria SA ENTERS RETA, BALE. ABMMBAS: MF: 01-2002-2178 BRERA (CIP) 4 HRA (GE + SSM) / (32) RDS (Hamacher, C. ) 23. Sta: BURT AL, 2002.6 ( BRU BPE ) B44 IRC: Computer Organization, SE ISBN 7-111-10346-7 Lite EO TL. RUA Ra - EK WV. TP303 FAD SCIPS (2002) 50380145 PUR TNH AL tse a2 BEE 100037) SUE: i AC APES DR EDR + RAEN RAT RA 2002486 Fi 5 1 ASE 1K ET 850mm x 1168mm 1/32 + 26 BUF EN: 0 001-3 OOORE REO: 48.0056 JUBA, MARI, BE, RT, EL ATtoRS B RERXUM, WAKA ESE ROSA, HR REARELHRTURRE TSR; HIE AE, (HIER ERBRARRWATSER ERE, ROR, EAMES, R SOMATA RR, HOLE RPO eR AC at SATA, BATE E, AER TOE 1, GRATSRORE, RMR, RAAEAME, ROME AeA AEA MMT Te, ESR AM MET, RAWHHOP RA, ae MAA ATER F238. ORT LSC FA AL, th ALE BR; WELLE TRE RBELBE, ERERARKRA RA REG, DLA RRR, SERRE LAS RAUL TERRRENSRAM AAS EHEE SA. Alt, S/d FMAM EURAT PAT PNR RRO EA, thie STP SL. PRUE MHRA BURT Ne A ARS RD) “Hh TESS” 0 A19984En, RAR MELE ABET Bi. BERR BHL. & TUL ASA, FAN gPrentice Hall, Addison-Wesley, McGraw-Hill, Morgan Kaufmann tt A243 HR AB T REMARK, WEA SCH PRP Bie Mi Tanenbaum, Stroustrup, Kemighan, Jim Gray AUER MBSE, “TRL” PRU, GRE, TER RR. KAATHHHH, MERA REA Ra “HRAEAB” MU LGEIT AMER, BAAS RAT Hs ES, RHE T PERLE; TT ROA RAST EE, SOLER PRE FR. eS, “ROA BAM TU, RHR Pt ST RHO, HRASHRRAAERRRHSS EM, WHE ARATE BSCEBME ELA SCAN OEM, SOT STEAL BH OTR AL BE ARTE. Wt, RES LAS eT EE, Ee “PRAT” WO BMMS FARE TRHRL: Ft, AMIR, HECHIOMEITR “BSR” A, SYRIA, SURE “SSSR RE” ; RCRA MSS SH “i PLOLAL SAME" ROR, BEC MLE. WT RER SEA CRE, AINA Rene RME MRS, RAAT PRS Bi, RAS. WAY, BRAY. MAAS, RMA. He KE, WA, PRREAS. MRR DUKE, RAR. PRA RAF. AMM RAS. AMA. PUK, RETAKE, SAAS, MILER. PHRRATALAMTAEP DSA AREA PO BENR AMS TORNSS FEAR “CRESRAR”, WRN ‘ESSERE Ln tH RUA “GRRE” SLM OCT REE OS, A BR HOLECE BESTE. HEP EMER RA “SRESEAS” RLS, RAs T ROSH AEE UREA neta, PAAR BSEMLLT.. Stanford, U.C. Berkley, CM.U.FHURG ACER AFRO T BP, BGR. BERS. TOUR. BORE. RE. RE. AS. HS. RRP SRA ASH RL POF RORORE, HASAH—AWK ARRAS, AHS ER. AWE RAHFULA BRA, ROC PRINS HAE RHBSLZT, BRAM EHO SRP TAS BURNER. BRS, ATR. PRR RI, SARERNA EA TARO, PRNMARERBER, MR PRLELRMAAR RRAPHRR BH. SHH BRM SR FARE 5 EELS LS MATE TET LE ER PE, TARR AMF HAF HME: [email protected] RAG: (010) 68995265 RAL: ION EAS BESS: 100037ERESERSA (BoE ECS BBUF ) zw a # BR 1: i ABR #eAB AR He EK KR F ee HAF ERE i Bid EE bb BR fe 8 RB KES BP Ber iH eh AL 3 Lem AME MAR Ae | BeareABOUT THE AUTHORS Carl Hamacher received his B.A.Sc. degree in engineering physics from the University of Waterloo, Canada, an M.Sc. degree in electrical engineering.from Queen's Univer- sity, Kingston, Canada, and a Ph.D. degree in electrical engineering from Syracuse University, New York. From 1968 to 1990 he was at the University of Toronto, where ‘he was a Professor in the Departments of Electrical Engineering and Computer Sci- ence. He served as director of the Computer Systems Research Institute during 1984 to 1988, and as chairman of the Division of Engineering Science during 1988 to 1990. Since January 1991 he has been a Professor of Electrical and Computer Engineering at Queen’s University. He served as the dean of the Faculty of Applied Science from 1991 to 1996, During 1978 to 1979, he was a visiting scientist at the IBM Research Laboratory in San Jose, California. In 1986, he was a research visitor at the Labora- tory for Circuits and Systems associated with the University of Grenoble in France. In 1996 to 1997, he was a visiting professor in the Computer Science Department at the University of California at Riverside and in the LIP6 Laboratory of the University of Paris VE, France, Bis research interests are in multiprocessors and multicomputers, focusing on their interconnection networks. Zvonko Vranesic received his B.A.Sc., M.A.Sc., and Ph.D. degrees, in electrical engineering from the University of Toronto. From 1963 to 1965 he worked as a design engineer with the Northem Electric Co., Ltd, in Bramalea, Ontario. In 1968, he joined the University of Toronto, where he is now a Professor in the Department of Electrical and Computer Engineering and the Department of Computer Science, During 1978 to 1979, he was a senior visitor at the University of Cambridge, England, and during 1984 to 1985 he was at the University of Paris VI, France. In 2000 to 2001, he was a principal software engineer at Altera Corporation in Toronto. From 1995 to 2000, he served as chair of the Division of Engineering Science at the University of Toronto. His current research interests include computer architecture, field-programmable VLSI technology, and multiple-valued logic systems. He is a coauthor of three other books: Fundamentals of Digital Logic with VHDL Design, Microcomputer Structures, and Field-Programmable Gate Arrays. In 1990, he received the Wighton Fellowship for “innovative and distinctive contributions te undergraduate laboratory instruction.” Safwat Zaky received his B.Sc. degree in electrical engincering and B.Sc. in mathematics, both from Cairo University, Egypt, and his M.A.Sc. and Ph.D. degrees in electrical engineering from the University of Toronto. From 1969 to 1972 he was with Bell Northern Research, Bramalea, Ontario, where he worked on applications of electro- optics and magnetics in mass storage and telephone switching. In 1973, he joined the University of Toronto, where he is now a Professor in the Department of Electrical and Computer Engineering and the Department of Computer Science. Presently, hevit ABOUT THE AUTHORS serves as chair of the Department of Electrical and Computer Engineering. From 1980 to 1981, he was a senior visitor at the Computer Laboratory, University of Cambridge, England. His research interests are in the areas of coraputer architecture, reliability of digital circuits, and electromagnetic compatibility. He is a coauthor of the book Microcomputer ‘Structures and is a recipient of the IEEE Third Millennium Medal.CONTENTS Preface xvii Chapter ¥ BASIC STRUCTURE OF COMPUTERS 1 Lt Computer Types 2 12 Functional Units 3 L2E lope Unie 4 1.22 Memory Unit 4 1.23 Arithmetic and Logic Unit 5 1.24 Ontpat Unit 6 125 Comrol Unit 6 13 Basic Operational Concepts 7 14 Bus Structures 9 15 Software 10 1.6 Performance 13 L6.1 Processor Clock 14 1.6.2 Basic Performance Equation 14 1.6.3. Pipelining and Superscalar Operation 15 1.6.4 Clock Rate 16 1.6.5 Instruction Set: CISC and RISC 16 16.6 Compiler 17 1.6.7 Performance Measurement 17 1.7 Multiprocessors and Multicomputers 18 1.8 Historical Perspective. 19 18.1 The First Generntion 19 1.8.2 The Second Generation 20 1.8.3 TheThird Generation 20 1.84 The FourthGeneration 20 1.8.5 Beyond the Fourth Generation 21 18.6 — Evolution of Performance 21 1.9 Concluding Remarks 21 Problems 22 References 23 Chapter 2 MACHINE INSTRUCTIONS AND PROGRAMS 25 2.1 Numbers, Arithmetic Operations, and ” Characters 27 22 Memory Location ad Adenes 33 23° Memory Operations 36 2.4 Instructions and Instruction Sequencing 37 24.2 Assembly Language Notation 38 243 Basic Insirction Types 38 244 Instruction Execution and Straight-Line Sequencing 42 2.45 Branching 44 246 Condition Codes 45 24.7 Generating Memory Addresses 47 25 Addressing Modes 48 25.1 Implementation of Varisbles and Constants 49 25.2 Indirection and Pointers 50 25.3 Indexing and Amays 52 254 Relative Addressing 56 255 Additional Modes’ 56s 2.6 Assembly Language ° 58 2.6.1 Assembler Directives 59 262 Assembly and Execution of Programs 62 26.3 Number Notation 64 2.7 Basic InpuvOurput Operations 64 28 Stacks and Queues 68 29 Subroutines 72 29.1 Subn Neng anthers 29.2 Panne Posy 4 29.3 TheStack Frame 75 2.10 Additional Instructions 81x ConTENTS 2.10.1 Logic instructions 81 2.10.2 Shift and Rotate Instructions 82 2.10.3 Multiplication and Division 86 2.11 Example Programs 86 2.11.1 Vector Dot Product Program 86 2.11.2 Byte-Sorting Program 87 2113 Linked Lists 99 2.12 Encoding of Machine Instructions 94 2.13 Concluding Remarks 98 Problems 98 Chapter 3 ARM, MOroroLa, AND INTEL INSTRUCTION SETS 103 Parti The ARM Example 104 3.1. Registers, Memory Access, and Data ‘Transfer 104 3.11 Register Structure 105 3.1.2 Memory Access Instructions and ‘Addressing Modes 106 3.1.3 Register Move Instructions 113 3.2. Arithmetic and Logic Instructions 113 3.2.1 Arithmetic Instructions 113 3.2.2 Logic instructions 115 3.3. Branch Instructions 116 3.3.1 Setting Condition Codes 117 3.3.2 A Loop Program for Adding Nombers 118 3.4 Assembly Language 118 3.4.1 Pseudo-Instructions 120 3.5 WO Operations 121 3,6 Subroutines 122 3.7 Program Examples 126 3.7.1 Vector Dot Product Program 126 3.7.2 Byte-Sorting Program 127 3.7.3 Linked-List Insertion and Deletion Subroutines 127 Part I The 69000 Example 130 38 Registers and Addressing 131 3.8.1 The 68000 Register Structure 131 3.8.2 Addressing 131 3.9 instructions 136 3.10 Assembly Language 140 3.11 Program Flow Control 141 BALL Condition Code Flags 141 3.11.2 Branch instructions 141 3.12 70 Operations 145 3.13 Stacks and Subroutines 146 3.14 Logic Instructions 151 3,15 Program Examples 152 BAS.1 Vector Dot Product Program 152 3.15.2 Byte-Sorting Program 153 3.15.3 Linked-List Insertion and Deletion Subroutines 154 Part Hi The 14-32 Pentium Example 155 3.16 Registers and Addressing 156 3.16.1 1A-32 Register Structure 156 3.16.2 1A-32 Addressing Modes 159 3.17 1A-32 Instructions 164 3.17.1 Machine Instruction Format 168 3.18 IA-32 Assembly Language 170 3.19 Program Flow Control 171 3.19.1 Conditional Jumps and Condition Code Fiags 171 3.19.2 Unconditional Jump 173 3.20 Logic and Shif/Rotate Instructions 173 3.20.1 Logic Operations 173 3.20.2 Shift and Rotate Operations 173 3.21 WO Operations 174 3.21.1 Memory-Mapped/O 174 321.2 Isolaed YO 175 3.21.3 Block Transfers 176 3.22 Subroutines 177 3.23 Other Instructions 182 3.23.1 Mubiply and Divide Instructions 182 3.23.2 Multimedia Extension (MMX) Instructions 183 3.23.3. Vector (SIMD) Instructions 184 3.24 Program Examples 184 3.24.1 Vector Dot Product Program 184 3.24.2 Byte-Sorting Program 185 = * 3.24.3 Linked-List Insertion and Deletion Subroutines 185 3.25 Concluding Remarks 188 Problems 188 References 201 Chapter 4 TNPUV/OUTPUT ORGANIZATION 203 4.1 Accessing OQ Devices 204 42 Interrupts 208 _4.2.1 Interrupt Hardware 210 4.2.2 Enabling and Disabling Interrupts 211 423 Handling Multiple Devices 213 42,4 Controlling Device Requests 217 4.2.5 Exceptions 218 42.6 — Use of Interrupts in Operating Systems 220 43. Processor Examples 224 43.1 ARM Interrupt Structure 224 43.2 68000 Interrupt Structure 229 43.3 Pentium Interrupt Structure 231 44° Direct Memory Access 234 44.1 Bus Arbitration 237 4.5 Buses 240 45.1 Synchronous Bus 241 45,2 Asynchronous Bus 244 45.3 Discussion 247 4.6 Interface Circuits 248 46.1 Parallel Port 248 46.2 Seriat Port 257 4.7 Standard 1/0 Interfaces 259 4.7.1 Peripheral Component Interconnect (PCI) Bus 261 47.2 SCSIBus 266 4.7.3 Universal Serial Bus (USB) 272 4.8. Concluding Remarks 283 Problems 283 References 289 Chapter 5 ‘THE MEMORY SYSTEM 291 5.4 Some Basic Concepts 292 5.2 Semiconductor RAM Memories 295 5.2.4 Internal Organization of Memory Chips 295 5.2.2 Static Memories 297 5.2.3 Asynchronous Drams 299 5.24 SynchronousDRAMs 302 5.2.5 Structure of Larger Memories 305 °5.2.6 Memory System Considerations 307 5.2.7 Rambus Memory 308 5.3 Read-Only Memories 309 3.3.1 ROM 310 53.2 PROM 311 5.3.3 EPROM 311 5.3.4 EEPROM 311 53.5 FlashMemory 312 54 35 56 57 58 59 5.10 ConTENTs x Speed, Size, and Cost 313 Cache Memories 314. 5.5.1 Mapping Punctions 316 5.5.2 Replacement Algorithms 321 5.5.3 Example of Mapping Techniques 322 5.5.4 Examples of Caches in Commercial Processors 325 Performance Considerations 329 5.6.1 Interleaving 330 5.6.2 Hit Rate and Miss Penalty 332 5.6.3 Caches on the Processor Chip 334 5.64 Other Enhancements 335 Virtual Memories 337 5.7.1 Address Translation 339 Memory Management Requirements 343 Secondary Storage 344 5.9.1 Magnetic Hard Disks 344 5.9.2 Optical Disks 352 5.9.3 Magnetic Tape Systems 358 Concluding Remarks 359 Problems 360 References 366 Chapter 6 ARITHMETIC 367 61 62 63 65 6.6 67 Addition and Subtraction of Signed Numbers 368 6.1.1 Adgition/Subtraction Logic Unit 369 Design of Fast Adders 371 6.2.1 Camy-Lookahead Addition 372 Multiplication of Positive Numbers 376 Signed-Operand Multiplication 380 6.4.1 Booth Algorithm 380 Fast Multiplication 383 6.5.1 Bit-Pair Recoding of Multipliers 384 6.5.2 Camy-Save Addition of ‘Sommands 385 Integer Division 390 Floating-Point Numbers and ‘Operations 393 6.7.1 IEEE Standard for Floating-Point Numbers 394 6.7.2 Arithmetic Operations on Floating-Point Numbers 398 67.3 Guard Bits and Truncation 39968 Contents: 6:74 Implementing Floating-Point Operations 400 Concluding Remarks 403 Problems 403 References 410 Chapter 7 Basic PROCESSING UNIT 411 TA 12 73 14 75 16 Some Fundamental Concepts 412 TAL Register Transfers 415 71.1.2 Performing an Arithmetic or Logic Operation 415 7.1.3 Fetching a Word from Memory 418 7.14 Storinga Word in Memory 420 Execution of a Complete Instruction 421 7.2.1 Branch instructions 422 Multiple-Bus Organization 423 Hardwired Control 425 1.4.1 AComplese Processor 428 Microprogrammed Control 429 75.1 Microinstructions 432 1.5.2 Microprogram Sequencing 435 1.5.3 Wide-Branch Addressing 437 7.54 — Microinstructions with Next-Address Field 440 75.5 Prefetching Microinstructions 443 75.6 Emulation 443 Concluding Remarks 445 Problems 446 Chapter 8 PIPELINING 453 BL 82 83 84 Basic Concepts 454 B11 RoleofCache Memory 456 8.1.2 Pipeline Performance 458 Date Hazards 461 8.2.1 Operand Forwarding 462 8.2.2 Handling Data Hazards in Software 464 8.2.3 Side Effects 464 Instruction Hazards 465 8.3.1 Unconditional Branches 466 8.3.2 Conditional Branches and Branch Prediction 470 Influence on instruction Sets 476 8.4.1 Addressing Modes 476 8.4.2 Condition Codes 478 8.5 Datapath and Control Considerations 479 8.6 Superscalar Operation 481 8.6.1 Outof-Order Execution 483 8.6.2 Execution Completion 485 8.6.3 Dispatch Operation 486 8.7 UltraSPARC EXAMPLE 486 8.7.1 SPARC Architecture 487 37.2 UlnaSPARCH 493 8.7.3 Pipeline Stucture 493 88 Performance Considerations 503 8.8.1 Effect of Instruction Hazards S04 8.8.2 Number of Pipeline Stages 50S 89 Concluding Remarks 506 Problems 506 Reference 509 Chapter 9 EMBEDDED Systems 511 9.1 Examples of Embedded Systems 512 9.1.1 Microwave Oven S12 9.1.2 Digital Camera Sid 9.13 Home Telemeuy 516 9.2 Processor Chips for Embedded Applications 517 9.3 A Simple Microcontroller 518 9.3.1 Parallel YOPors S18 9.3.2 Serial VO Imecface 521 9.3.3 CoumerTimer 523 9.3.4 interrupt Control Mechanism $25 94 Programming Considerations 525 94.1 Polling Approach 526 94.2 Interrupt Approach 529 9.5 VO Device Timing Constraints 531 9.5.1 C Program for Transfer via a Circular Buffer 533 9.5.2 Assembly Language Program for ‘Transfer via a Circular Buffer 534 9.6 Reaction Timer—An Example 535 9.6.1 C Program for the Reaction Timer 937 9.6.2 Assembly Language Program for the Reaction Timer $37 9.63 Final Comments 541 9.7 Embedded Processor Families 541 9.7.1 Microcontrollers Based on the Inte! 051 542 9.7.2 Motorola Microcontrollers 542 9.73 ARM Microcontollers 54398 Design Issues 544 9.9 System-on-a-Chip 546 9.9.1 FPGA Implementation 547 9,10 Concluding Remarks 549 Problems 550 References 552 Chapter 10 COMPUTER PERIPHERALS 553 10.1 Inpat Devices 554 10.1.1 Keyboard 554 10.1.2 Mouse 555 10:13 ‘Trackball, Joystick, and Touchpad 556 10.1.4 Scanners 557 10.2 Output Devices 558 10.2.1 VideoDisptays 558 102.2 Flat-Panel Displays 559 10.2.3 Primers 560 10.2.4 Graphics Accelerators 561 10.3 Serial Communication Links 563 10.3.4 Asynchronous Transmission 566 10.3.2 Synchronous Transmission 568 10.3.3 Standard Communications Interfaces S71 10.4 Concluding Remarks 574 Problems 575 Chapter 11 PROCESSOR FAMILIES 577 ILL The ARM Family 579 ALL] The Thumb Instruction Set 579 1.1.2. Processor and CPU Cores 580 IL2_ The Motorola 680X0 and ColdFire Families 582 11.2.1 68020 Processor 582 11.2.2 Enhancements in 68030 and 68040 Processors 584 11.23 68060 Processor 585 11,24 The ColdFire Pamily 585 113 The Intel [A-32 Family 585 11.3.1 IA-32Memory Segmentation 586 11.3.2 Sixteea-Bit Mode 588 11.3.3 80386 and 81486 Processors. 588 11.3.4 Pentium Processor 589 11.3.5 Pentium Pro Processor 589 11.3.6 Pentium Il and INI Processors 590 CONTENTS eit 11.3.7 Pentium 4 Processor $90 IL38 Advanced Micto Devices 14-32 Processors S91 114 The PowerPC Family 591 ILA. Register Set 591 114.2 Memory Addressing Modes 592 1143 Instructions 592 114.4 PowerPC Processors 592 11.5 The Sun Microsystems SPARC Family 594 116 The Compaq Alpha Family 596 11.6.1 Instruction and Addressing Mode Formats 596 11.6.2 Alpha 21064 Processor 597 11.63 Alpha 21164 Processor 597 LL64 Aigha 21264 Processor $97 11.7 The lotel 14-64 Family 598 17.1 Unsiruetion Bundles 598 11.7.2 Conditional Execution 598 11.73 Speculative Loads 600 TL7.4 Registers and the Register Stack 600 11.7.5 [anium Processor 602 1LB A Stack Processor 603 1.8.1 Stack Structure 604 11.8.2. Stack Instructions 606 118.3 Hardware Registers in the Stack 610 119 Concluding Remarks 612 Problems 612 References 614 Chapter 12 Larce COMPUTER SYSTEMS 617 12.1 Forms of Parallel Processing 619 12.L1 Classification of Parallel Soucures 619 12.2, Array Processors 620 12.3 The Structure of General-Purpose. Multiprocessors 622 12.4 Interconnection Networks 624 124.1 SingleBus 624 124.2 Crossbar Networks 625 12.4.3 Multistage Networks 626 12.44 Hypercube Networks 628 12.4.5 Mesh Networks 630 124.6 Tree Networks 630 124.7 Ring Networks 631 1248 Practical Considerations 632 12.4.9 Mixed Topology Networks 636. 124.10 Symmetric Multiprocessors 636a CONTENTS 12.5 Memory Organization in ‘Multiprocessors 637 12.6 Program Parallelism and Shared Variables 638 12.6.1 Accessing Shared Variables 640 12.6.2 Cache Coherence 641 12.6.3 Need for Locking and Cache Coherence 645 12.7 Multicompaters 645 12.7.1 Local Area Networks 646 12.7.2. Ethemet (CSMA/CD) Bus 646 1273 Token Ring 647 12.7.4 Network of Workstations 647 12.8 Programmer's View of Shared Memory and Message Passing 648 128.1 Shared Memory Case 648 12.8.2 Message-Passing Case 651 12.9 Performance Considerations 653 12.9.1 Amdabl’s Law 654 12.9.2 Performance Indicators 656 12.10Concluding Remarks 656 Problems 657 References 660 APPENDIX A: LOGIC CIRCUITS 661 A. Basic Logic Functions 662 A.L.1 Electronic Logic Gates 665 A2 Synthesis of Logic Functions 666 A3 Minimization of Logic Expressions 668 A3.1— Minimization Using Karnaugh Maps. 671 A32 Don't-Care Conditions 674 A4 Synthesis with NAND and NOR Gates 674 AS. Practical implementation of Logic Gates 678 © AS.1 CMOS Circuits 681 AS2 Propagation Delay 686 AS3 — Fan-In and Fan-Ont Constraints 687 ASA Trista Buffers 687 A5.5 Integrated Circuit Packages 688 A6 Flip-Flops 690 A6.1 Gated Latches 690 6.2 Mastcr-Slave Flip-Flop 694 A63 Edge Triggering 694 A64 TFlip-Flop 697 AGS IKFlip-Flop 697 A.6.6 Flip-Flops with Preset and Clear 658 AT Registers and Shift Registers 699 A& Counters 702 AQ Decoders 703 A.10 Multiplexers 705 ‘A.Li Programmable Logic Devices (PLDs) 705 ATLL Programmable Logic Array @PLA) 707 A.LL2 Programmable Array Logic PAL) 710 A.IL3 Complex Programmable Logic Devices (CPLDs) 711 A.12 Field-Programmable Gate Arrays 712 A.13 Sequential Circuits 714 A341 An Example of an Up/Down Counter 714 AI3.2 Timing Diagrams 718 A133 The Figite State Machine Made! 719 A134 Syothisis of Finite State Machines 720 A.14 Concluding Remarks 724 Problems 724 References 731 APPENDIX B: ARM INSTRUCTION Ser 733 B.1 Instruction Encoding 734 B.L1 Arithmetic and Logic Instructions 734 B.1.2 Memory Load and Store Instructions 741 B.13 Block Load and Store Instructions 744 B.14 Branch and Branch with Link Instructions 747 B.1.5 Machine Control Instructions 747 B2 Other ARM Instructions 750 B21 Coprocessor Instructions 750 B.2.2 Versions v4 and v5 Instructions 750 B3 Programming Experiments 750 APPENDIX C: MOTOROLA 68000 INSTRUCTION SET 751CONTENTS: ” APPENDIX D: INTEL IA-32 DA42 Floating-Point, MMX, and SSE INSTRUCTION SET 769 Instructions 784 D.5 Sixteen-Bit Operation 785 D.i Instruction Encoding 70 DS Programming Experiments 785 DALI Addressing Modes 772 D2 Basic mctions ™ APPENDIX E: CHARACTER CODES AND D2. Conditional Jump Instructions 782 NUMBER CONVERSION 789 D3 D22 we emo 782 Bl. c 790 D4 OtherInstructions 783 E2 Decimal-to-Binary Conversion 793 DAL Sting lastructions 783 INDEX 795PREFACE ‘This book is intended for use in a first-level course on computer organization in elec- trical engineering, computer engineering, and computer science curricula. The book is self-contained, assuming only that the reader has a basic knowledge of computer pro- gramming in a high-level language. Many students who study computer organization will have had an introductory course on digital logic circuits. Therefore, this subject is not covered in the main body of the book. However, we have provided an extensive appendix on logic circuits for those students who need it. The book reflects our experience in teaching computer organization to three dis- tinct groups of undergraduates: electrical and computer engineering undergraduates, computer science specialists, and engineering science undergraduates. We have always approached the teaching of courses in this area from a practical point of view. Thus, a ‘Key consideration in shaping the contents of the book has been to ilfustraté. the prin- ciples of computer orgaization using examples drawn from commercially avaflable computers. Our main examples are based on the following processars: ARM, Motorola ‘680X0, intel Pentium, and Sun UluaSPARC. It is important to recognize that digital system design is not a straightforward process of applying optimal design algorithms. Many design decisions are based largely on heuristic judgment and experience. They involve costiperformance and hardware/ software tradeofis over a range of altematives. It is our goal to convey these notions to the reader, ‘We have endeavored to provide sufficient details to encourage the student to dig beyond the surface when dealing with ideas that seem to be intuitively obvious. We believe that this is best accomplished by giving real examples that ate adequately doc: umented. Block diagrams are a powerful means of describing organizational features of a computer. However, they can easily lead to an oversimplified view of the prob- Jems involved. Hence, they must be accompanied by the details of implementation alternatives. ‘The book is aimed at a one-semester course in engineering or computer science programs. It is suitable for both hardware- and software-oriented students. Eve though the emphasis is on hardware, we have addressed a number of software issues, includ- ing basic aspects of compilers and operating systems related to instruction execution performance, coordination of parallel operations at the system level, and real-time appli- cations. An understanding of hardware/software interaction and tradeoffs is necessary for computer specialists. THE SCOPE OF THE BOOK ‘We now review the topics covered in sequence, chapter by chapter. The first eight chap- ters cover the basic principles of computer Organization, operation, and performance.PRERACE, ‘The remaining four chapters deal with embedded systems, peripheral devices, processor family evolution patterns, and large computer systems. Chapter I provides an overview of computer hardware and software and informally introduces terms that are dealt with in more depth in the remainder of the book. This chapter discusses the basic functional units and the ways they are interconnected to form a complete computer system. The role of system software is introduced and basic aspects of performance evaluation are discussed. A brief treatment of the history of computer development is also provided. Chapter 2 gives a methodical treatment of machine instructions, addressing tech- niques, and instruction sequencing. Basic aspects of 2's-complement arithmetic are introduced t facilitate the discussion of the generation of effective addresses, Program: examples at the machine instruction level, expressed in a generic assembly language, are used to discuss loops, subroutines, simple input-output programming, sorting, and Tinked list operations, Chapter 3 illustrates implementation of the concepts introduced in Chapter 2 on three commercial procesgnrtie- ARM, 68000, and Pentium. The ARM processor il- Instrates the RISC depigaiteyle, the 68000 has an easy-to-teach CISC design, while the Pentium represents themdstaticcessful commercial design that combines the elements of both the CISC and RISC styles. The material is organized into three independent and complete parts. Each part includes ail of the examples from Chapter 2 implemented in the context of the specific processor. It is sufficient to cover only one of the three parts to provide the continuity needed to follow the rest of the book, If laboratory experiments using one of the three processors are associated with the course, the relevant part of Chapter 3 can be covered in parallel with Chapter 2. Input-outpat organization is developed in Chapter 4. The basics of 1/0 data transfer synchronization are presented, and a series of increasingly complex VO structures are explained, Interrupts and direct-memory access methods are described in detail, including a discussion of the role of software interrupts in operating systems. Bus Protocols and standards are also presented, with the PCI, SCSI, and USB standards being used as representative commercial examples. Semiconductor memories, including SDRAM, Rambus, and Flash memory impte- mentations, are discussed in Chapter 5, Caches and multiple-module memory systems are explained as ways for increasing main memory bandwidth. Caches are discussed. in some detail, including performance modeling, Virwal-memory systems, memory management, and rapid address translation techniques are also presented. Magnetic and optical disks are discussed as components in the memory hierarchy. Chapter 6 treats the arithmetic unit of a computer. Logic design for fixed-point add, subtract, multiply, and divide hardware, operating on 2’s-complement numbers, is described. Lookshead adders and high-speed multipliers are explained, including de- scriptions of the Booth multiplier recoding and carry-save addition techniques. Floating- point number representation and operations, in the context of the IEEE Standard, are presented. Chapter 7 begins with a register-transfer-level treatment of the implementation of instruction fetching and execution in a processor. This is followed by a discussion of processor implementation by both hardwired and microprogrammed control,PREFACE, Chapter 8 provides a detailed coverage of the use of pipelining and multiple func- tion units in the design of high-performance processors. The role of the compiler and the relationship between pipelined execution and instruction set design are explored. Su- perscalar processors are discussed, and the Sun Microsystems UltraSPARC II processor organization is used to illustrate the concepts. Today there are many more processors in use in embedded systems than in gencral- purpose computers. This increasingly important subject, where a single chip integrates the processing, I/O, and timer functionality needed in a wide range of low-cost applica- tions, is treated in Chapter 9, System integration issues, interconnections, and real-time software are discussed. Chapter 10 presents peripheral devices and computer interconnections. Typical input/output devices are described and hardware needed to support computer graphics applications is introduced. Commonly used communication links, such as DSL, are discussed. . ‘The evolution of the ARM, Motorola, and Inte! processor families is discussed in ‘Chapter 11. This chapter highlights the design changes that led to higher performance. ‘The PowerPC, SPARC, Alpha, and Intel IA-64 families are also discussed. Chapter 12 extends the discussion of computer organization to large systems that use many processors operating in parallel. Interconnection networks for multiprocessors are described, and an introduction to cache coherence controls is presented. Shared- memory and message-passing schemes are discussed. CHANGES IN THF Fret Eninion ‘Major changes in content and organization have been made in preparing the fifth edition of this book. They include the following: * Chapter 2 of the fourth edition has been split into two chapters —- Chapters 2 and 3 — in the fifth edition. An expanded treatment of basic issues, explained using generic instructions, is presented in Chapter 2. More programming examples for typical tasks, both numeric and non-numeric, are provided. Chapter 3 uses the instruction sets of ARM, 68000, and Pentium processors to show how the basic concepts of instruction set design have been implemented in both the RISC and CISC design styles. * The discussion of the role of pipelining and multiple functional units in processor design has been extended significantly. The UltraSPARC architecture is used to provide specific examples of performance-enhancing design features. + Anew chapter on embedded-processor systems has been added. A generic de- sign of a typical system is used as the basis for detailed discussion of example applications. ’ In addition to these main changes, many recent technology and design advances have been added to a number of chapters.PREFACE Wnat CAN BE COVERED IN 4 ONE-SeMESTER COURSE This book is suitable for use at the university of college level as a text for aone-semester course in computer organization. It is intended for use in the first course on computer organization that the students will take. ‘There is more than enough material in the book for a one-semester course. The care material is given in Chapters | through 8. For students who have not had a course in logic circuits, the basic material in Appendix A should be studied at the beginning of the course and certainly prior to covering Chapter 4. Chapters 9 through 12 contain a variety of useful material that the instructor may choose from if time permits. Particularly suitable are the discussion of embedded sys- tems in Chapter 9 and the description of hardware found in most personal computers given in Chapter 10. ACKNOWLEDGMENTS We wish to express our thanks to many people who have helped during the preparation of this fifth edition. Gail Burgess and Kelly Chan helped with the technical prepara- tion of the manuscript. Alex Grbic, Frank Hsu and Robert Lu provided valuable help with a number of programming examples. Our colleagues Tarek Abdelraman, Stephen Brown, Paul Chow, Glenn Gulak and Jonathan Rose offered constructive comments. We are particularly grateful to Stephen and Tarek for their help with important details. ‘The reviewers, Gojko Babic of The Ohio State University, Nathaniel Davis of Vir- ginia Polytechnic Institate and State University, Jose Fortes of Purdue University, John Greiner of Rice University, Sung Hu of San Francisco State University, Ali Hurson of Pennsylvania State University, Lizy Kurian John of University of Texas at Austin, Stefan Leue of Albert Ludwigs Universitat in Freiburg, Fabrizio Lombardi of North- eastem University, Wayne Loucks of University of Waterloo, Prasant Mohapatra of Iowa State University, Daniel Tabak of Gearge Mason University, and John Valois of Rensselaer Polytechnic Institute gave us many excellent suggestions and provided con- ‘structive criticism. We want to thank Eli Vranesic for permission to use his painting “Pall in High Park” on the front cover; he created it using the competer as a paint brush. Finally, we traly appreciate the support of our editor, Catherine Fields Shaltz, and her McGraw-Hill associates: Kelley Butcher, Michelle Flomenhoft, Kalah Graham, Betsy Jones, Rick Noel, Heather Sabo, and Christine Walker. Carl Hamacher Zvonko Vranesic ‘Safwat ZakyCHAPTER I BASIC STRUCTURE OF COMPUTERS CHAPTER ORJECTIVES In this chapter you willbe introduced to: The basic structure of a computer Machine instructions and their execution ‘System software that enables the preparation and execution of Programs Performance issues in computer systems ‘The history of computer developmentSHAPTER E+ BASIC STRUCTURE OF COMPUTERS Thisbookis: about computer organization. It describes the function and design of the var- ious units of digital computers that store and process information. It also deals with the Units of the computer that receive information from external sources and send computed estilts to external destinations. Most of the material in this book is devoted to computer hardware and computer architecture. Computer hardware consists of electronic cir- cuits, displays, magnetic and optical storage media, electromechanical equipment, and communication facilities. Comper echt cacampscs the specication ofan instruction nt the in ‘Many aspects of programming and software components in computer systems are also discussed in this book. It is important to consider both hardware and software aspects of the design of various computer components in order to achieve a good understanding of computer systems. This chapter introduces a number of hardware and software concepts, presents some common terminology, and gives a broad overview of the fundamental aspects of the subject, More detailed discussions follow in subsequent chapters. TE COMPUTER TYPES Let us frst define the term digital computer, or simply computer. Inthe simplest terms, acontemporary computer is a fast electronic calculating machine that accepts digitized inpot information, processes it according to a list of intemally stored instructions, and produces the resulting output information. The list of instructions is called a computer program, and the internal storage is called computer memory. Many types of computers exist that differ widely in size, cost, computational power, and intended use. The most common computer is the personal computer, which has found wide use in homes, schools, and business offices. It is the most common form. of desktop computers. Desktop computers have processing and storage units, visual display and audio output units, and a keyboard that can all be located easily on a home or office desk. The storage media include bard disks, CD-ROMs, and diskettes. Portable notebook computers are a compact-version of the personal computer with all of these components packaged into a single unit the size of a thin briefcase, Workstations with high-resolution graphics input/output capability, although still retaining the di- mensions of desktop computers, have significantly more computational power than personal computers. Workstations are often used in engineering applications, espe- cially for interactive design work. Beyond workstations, a range of large and very powerful computer systems exist that are called enterprise systems and servers at the low end of the range, and supercom- puters at the high end. Enterprise systems, or mainframes, are used for business data processing in medium to large corporations that require much more computing power and storage capacity than workstations can provide. Servers contain sizable database storage units and are capable of handling large volumes of requests to access the data, In many cases, servers are widely accessible to the education, business, and personal user communities. The requests and responses are usually transported over Internet communication facilities. Indeed, the Internet and its associated servers have become a dominant worldwide source of all types of information. The Intemet communication1.2 FUNCTIONAL UNTIS facilities consist of a complex structure of high-speed fiber-optic backbone links inter- connected with broadcast cable and telephone connections to schools, businesses, and homes. Supercomputers are used for the large-scale numerical calculations required in applications such as weather forecasting and aircraft design and siraulation. In enter- Prise systems, servers, and supercomputers, the functional units, including multiple processors, may consist of a number of separate and often lange units. 1.2 FUNCTIONAT, Unis Acomputer consists of five functionally independent main parts: input, memory, arith~ metic and logic, output, and control units, as shown in Figure 1.1. The input unit accepts coded information from human operators, from electromechanical devices such as key- boards, or from other computers over digital communication lines. The information re- ceived is either stored in the computer’s memory for later reference or immediately used by the arithmetic and logic circuitry to perform the desired operations. The processing steps are determined by a program stored in the memory. Finally, the results are sent back to the outside world through the output unit. All of these actions are coordinated by the control unit. Figure 1.1 does, not show the connections among the functional units. These connections, which can be made in several ways, are discussed throughout this book. We refer to the arithmetic and logic circuits, in conjunction with the main control circuits, as the processor, and input and output equipment is often collectively referred to as the input-output (1/0) unit. ‘We now take acloser look at the information handled by a computer. Itis convenient to categorize this information as cither instructions or data. Instructions, or machine instructions, are explicit commands that * — Govern the transfer of information within a computer as well as between the com- puter and its 1/0 devices + Specify the arithmetic and logic operations to be performed Figure 1.1 Basic functional units of a computer.