Structured Computer Organization

Cover......Page 1
CONTENTS......Page 8
PREFACE......Page 20
1 INTRODUCTION......Page 26
  1.1.1 Languages, Levels, and Virtual Machines......Page 27
  1.1.2 Contemporary Multilevel Machines......Page 30
  1.1.3 Evolution of Multilevel Machines......Page 33
  1.2.1 The Zeroth Generation—Mechanical Computers (1642–1945)......Page 38
  1.2.2 The First Generation—Vacuum Tubes (1945–1955)......Page 41
  1.2.3 The Second Generation—Transistors (1955–1965)......Page 44
  1.2.4 The Third Generation—Integrated Circuits (1965–1980)......Page 46
  1.2.5 The Fourth Generation—Very Large Scale Integration (1980–?)......Page 48
  1.2.6 The Fifth Generation—Low-Power and Invisible Computers......Page 51
  1.3.1 Technological and Economic Forces......Page 53
  1.3.2 The Computer Spectrum......Page 55
  1.3.3 Disposable Computers......Page 56
  1.3.4 Microcontrollers......Page 58
  1.3.5 Mobile and Game Computers......Page 60
  1.3.7 Servers......Page 61
  1.3.8 Mainframes......Page 63
  1.4.1 Introduction to the x86 Architecture......Page 64
  1.4.2 Introduction to the ARM Architecture......Page 70
  1.4.3 Introduction to the AVR Architecture......Page 72
 1.5 METRIC UNITS......Page 74
 1.6 OUTLINE OF THIS BOOK......Page 75
 2.1 PROCESSORS......Page 80
  2.1.1 CPU Organization......Page 81
  2.1.2 Instruction Execution......Page 83
  2.1.3 RISC versus CISC......Page 87
  2.1.4 Design Principles for Modern Computers......Page 88
  2.1.5 Instruction-Level Parallelism......Page 90
  2.1.6 Processor-Level Parallelism......Page 94
 2.2 PRIMARYMEMORY......Page 98
  2.2.2 Memory Addresses......Page 99
  2.2.3 Byte Ordering......Page 101
  2.2.4 Error-Correcting Codes......Page 103
  2.2.5 Cache Memory......Page 107
  2.2.6 Memory Packaging and Types......Page 110
  2.3.1 Memory Hierarchies......Page 111
  2.3.2 Magnetic Disks......Page 112
  2.3.3 IDE Disks......Page 116
  2.3.4 SCSI Disks......Page 117
  2.3.5 RAID......Page 119
  2.3.6 Solid-State Disks......Page 122
  2.3.7 CD-ROMs......Page 124
  2.3.8 CD-Recordables......Page 128
  2.3.9 CD-Rewritables......Page 130
  2.3.10 DVD......Page 131
  2.4.1 Buses......Page 133
  2.4.2 Terminals......Page 138
  2.4.3 Mice......Page 143
  2.4.4 Game Controllers......Page 145
  2.4.5 Printers......Page 147
  2.4.6 Telecommunications Equipment......Page 152
  2.4.7 Digital Cameras......Page 160
  2.4.8 Character Codes......Page 162
 2.5 SUMMARY......Page 167
 3.1 GATES AND BOOLEAN ALGEBRA......Page 172
  3.1.1 Gates......Page 173
  3.1.2 Boolean Algebra......Page 175
  3.1.3 Implementation of Boolean Functions......Page 177
  3.1.4 Circuit Equivalence......Page 178
  3.2.1 Integrated Circuits......Page 183
  3.2.2 Combinational Circuits......Page 184
  3.2.3 Arithmetic Circuits......Page 188
  3.2.4 Clocks......Page 193
  3.3.1 Latches......Page 194
  3.3.2 Flip-Flops......Page 197
  3.3.4 Memory Organization......Page 199
  3.3.5 Memory Chips......Page 203
  3.3.6 RAMs and ROMs......Page 205
  3.4.1 CPU Chips......Page 210
  3.4.2 Computer Buses......Page 212
  3.4.3 Bus Width......Page 215
  3.4.4 Bus Clocking......Page 216
  3.4.5 Bus Arbitration......Page 221
  3.4.6 Bus Operations......Page 223
  3.5.1 The Intel Core i7......Page 226
  3.5.2 The Texas Instruments OMAP4430 System-on-a-Chip......Page 233
  3.5.3 The Atmel ATmega168 Microcontroller......Page 237
  3.6 EXAMPLE BUSES......Page 239
  3.6.1 The PCI Bus......Page 240
  3.6.2 PCI Express......Page 248
  3.6.3 The Universal Serial Bus......Page 253
  3.7.1 I/O Interfaces......Page 257
  3.7.2 Address Decoding......Page 258
 3.8 SUMMARY......Page 260
 4.1 AN EXAMPLE MICROARCHITECTURE......Page 268
  4.1.1 The Data Path......Page 269
  4.1.2 Microinstructions......Page 276
  4.1.3 Microinstruction Control: The Mic-1......Page 278
  4.2.1 Stacks......Page 283
  4.2.2 The IJVM Memory Model......Page 285
  4.2.3 The IJVM Instruction Set......Page 287
  4.2.4 Compiling Java to IJVM......Page 290
  4.3.1 Microinstructions and Notation......Page 292
  4.3.2 Implementation of IJVM Using the Mic-1......Page 296
  4.4.1 Speed versus Cost......Page 308
  4.4.2 Reducing the Execution Path Length......Page 310
  4.4.3 A Design with Prefetching: The Mic-2......Page 316
  4.4.4 A Pipelined Design: The Mic-3......Page 318
  4.4.5 A Seven-Stage Pipeline: The Mic-4......Page 325
 4.5 IMPROVING PERFORMANCE......Page 328
  4.5.1 Cache Memory......Page 329
  4.5.2 Branch Prediction......Page 335
  4.5.3 Out-of-Order Execution and Register Renaming......Page 340
  4.5.4 Speculative Execution......Page 345
  4.6.1 The Microarchitecture of the Core i7 CPU......Page 348
  4.6.2 The Microarchitecture of the OMAP4430 CPU......Page 354
  4.6.3 The Microarchitecture of the ATmega168 Microcontroller......Page 359
 4.7 COMPARISON OF THE I7, OMAP4430, AND ATMEGA168......Page 361
 4.8 SUMMARY......Page 362
5 THE INSTRUCTION SET......Page 368
  5.1.1 Properties of the ISA Level......Page 370
  5.1.2 Memory Models......Page 372
  5.1.3 Registers......Page 374
  5.1.5 Overview of the Core i7 ISA Level......Page 376
  5.1.6 Overview of the OMAP4430 ARM ISA Level......Page 379
  5.1.7 Overview of the ATmega168 AVR ISA Level......Page 381
  5.2.1 Numeric Data Types......Page 383
  5.2.2 Nonnumeric Data Types......Page 384
  5.2.3 Data Types on the Core i7......Page 385
  5.2.5 Data Types on the ATmega168 AVR CPU......Page 386
  5.3.1 Design Criteria for Instruction Formats......Page 387
  5.3.2 Expanding Opcodes......Page 390
  5.3.3 The Core i7 Instruction Formats......Page 392
  5.3.4 The OMAP4430 ARM CPU Instruction Formats......Page 393
  5.3.5 The ATmega168 AVR Instruction Formats......Page 395
  5.4.1 Addressing Modes......Page 396
  5.4.4 Register Addressing......Page 397
  5.4.5 Register Indirect Addressing......Page 398
  5.4.6 Indexed Addressing......Page 399
  5.4.8 Stack Addressing......Page 401
  5.4.9 Addressing Modes for Branch Instructions......Page 404
  5.4.10 Orthogonality of Opcodes and Addressing Modes......Page 405
  5.4.11 The Core i7 Addressing Modes......Page 407
  5.4.13 The ATmega168 AVR Addressing Modes......Page 409
  5.4.14 Discussion of Addressing Modes......Page 410
  5.5.1 Data Movement Instructions......Page 411
  5.5.2 Dyadic Operations......Page 412
  5.5.3 Monadic Operations......Page 413
  5.5.4 Comparisons and Conditional Branches......Page 415
  5.5.5 Procedure Call Instructions......Page 417
  5.5.6 Loop Control......Page 418
  5.5.7 Input/Output......Page 419
  5.5.8 The Core i7 Instructions......Page 422
  5.5.9 The OMAP4430 ARM CPU Instructions......Page 425
  5.5.11 Comparison of Instruction Sets......Page 427
 5.6 FLOWOF CONTROL......Page 429
  5.6.1 Sequential Flow of Control and Branches......Page 430
  5.6.2 Procedures......Page 431
  5.6.3 Coroutines......Page 435
  5.6.4 Traps......Page 438
  5.6.5 Interrupts......Page 439
 5.7 A DETAILED EXAMPLE: THE TOWERS OF HANOI......Page 442
  5.7.2 The Towers of Hanoi in OMAP4430 ARM Assembly Language......Page 443
 5.8 THE IA-64 ARCHITECTURE AND THE ITANIUM 2......Page 445
  5.8.1 The Problem with the IA-32 ISA......Page 446
  5.8.3 Reducing Memory References......Page 448
  5.8.4 Instruction Scheduling......Page 449
  5.8.5 Reducing Conditional Branches: Predication......Page 451
  5.8.6 Speculative Loads......Page 454
 5.9 SUMMARY......Page 455
6 THE OPERATING SYSTEM......Page 462
 6.1 VIRTUAL MEMORY......Page 463
  6.1.1 Paging......Page 464
  6.1.2 Implementation of Paging......Page 466
  6.1.3 Demand Paging and the Working-Set Model......Page 468
  6.1.4 Page-Replacement Policy......Page 471
  6.1.5 Page Size and Fragmentation......Page 473
  6.1.6 Segmentation......Page 474
  6.1.7 Implementation of Segmentation......Page 477
  6.1.8 Virtual Memory on the Core i7......Page 480
  6.1.9 Virtual Memory on the OMAP4430 ARM CPU......Page 485
  6.1.10 Virtual Memory and Caching......Page 487
 6.2 HARDWARE VIRTUALIZATION......Page 488
  6.2.1 Hardware Virtualization on the Core I7......Page 489
  6.3.1 Files......Page 490
  6.3.2 Implementation of OSM-Level I/O Instructions......Page 492
 6.4 OSM-LEVEL INSTRUCTIONS FOR PARALLEL PROCESSING......Page 496
  6.4.2 Race Conditions......Page 498
  6.4.3 Process Synchronization Using Semaphores......Page 503
 6.5 EXAMPLE OPERATING SYSTEMS......Page 505
  6.5.1 Introduction......Page 507
  6.5.2 Examples of Virtual Memory......Page 513
  6.5.3 Examples of OS-Level I/O......Page 517
  6.5.4 Examples of Process Management......Page 528
 6.6 SUMMARY......Page 534
7 THE ASSEMBLY LANGUAGE LEVEL......Page 542
  7.1.1 What Is an Assembly Language?......Page 543
  7.1.2 Why Use Assembly Language?......Page 544
  7.1.3 Format of an Assembly Language Statement......Page 545
  7.1.4 Pseudoinstructions......Page 547
  7.2.1 Macro Definition, Call, and Expansion......Page 549
  7.2.2 Macros with Parameters......Page 551
  7.2.3 Advanced Features......Page 552
  7.2.4 Implementation of a Macro Facility in an Assembler......Page 553
  7.3.1 Two-Pass Assemblers......Page 554
  7.3.2 Pass One......Page 555
  7.3.3 Pass Two......Page 559
  7.3.4 The Symbol Table......Page 560
 7.4 LINKING AND LOADING......Page 561
  7.4.1 Tasks Performed by the Linker......Page 563
  7.4.2 Structure of an Object Module......Page 566
  7.4.3 Binding Time and Dynamic Relocation......Page 567
  7.4.4 Dynamic Linking......Page 570
 7.5 SUMMARY......Page 574
8 PARALLEL COMPUTER ARCHITECTURES......Page 578
 8.1 ON-CHIP PARALELLISM......Page 579
  8.1.1 Instruction-Level Parallelism......Page 580
  8.1.2 On-Chip Multithreading......Page 587
  8.1.3 Single-Chip Multiprocessors......Page 593
  8.2.1 Network Processors......Page 599
  8.2.2 Graphics Processors......Page 607
  8.2.3 Cryptoprocessors......Page 610
  8.3.1 Multiprocessors vs. Multicomputers......Page 611
  8.3.2 Memory Semantics......Page 618
  8.3.3 UMA Symmetric Multiprocessor Architectures......Page 623
  8.3.4 NUMA Multiprocessors......Page 631
  8.3.5 COMA Multiprocessors......Page 639
 8.4 MESSAGE-PASSING MULTICOMPUTERS......Page 641
  8.4.1 Interconnection Networks......Page 642
  8.4.2 MPPs—Massively Parallel Processors......Page 646
  8.4.3 Cluster Computing......Page 656
  8.4.4 Communication Software for Multicomputers......Page 661
  8.4.5 Scheduling......Page 664
  8.4.6 Application-Level Shared Memory......Page 665
  8.4.7 Performance......Page 671
 8.5 GRID COMPUTING......Page 677
 8.6 SUMMARY......Page 680
9 BIBLIOGRAPHY......Page 684
 A.1 FINITE-PRECISION NUMBERS......Page 694
 A.2 RADIX NUMBER SYSTEMS......Page 696
 A.3 CONVERSION FROM ONE RADIX TO ANOTHER......Page 698
 A.4 NEGATIVE BINARY NUMBERS......Page 700
 A.5 BINARY ARITHMETIC......Page 703
B: FLOATING-POINT NUMBERS......Page 706
 B.1 PRINCIPLES OF FLOATING POINT......Page 707
 B.2 IEEE FLOATING-POINT STANDARD 754......Page 709
C: ASSEMBLY LANGUAGE PROGRAMMING......Page 716
  C.1.1 Assembly Language......Page 717
  C.1.2 A Small Assembly Language Program......Page 718
 C.2 THE 8088 PROCESSOR......Page 719
  C.2.2 The General Registers......Page 720
  C.2.3 Pointer Registers......Page 723
  C.3.1 Memory Organization and Segments......Page 724
  C.3.2 Addressing......Page 726
  C.4.1 Move, Copy and Arithmetic......Page 730
  C.4.3 Loop and Repetitive String Operations......Page 733
  C.4.4 Jump and Call Instructions......Page 734
  C.4.5 Subroutine Calls......Page 735
  C.4.6 System Calls and System Subroutines......Page 737
  C.5.1 Introduction......Page 740
  C.5.2 The ACK-Based Tutorial Assembler as88......Page 741
  C.5.3 Some Differences with Other 8088 Assemblers......Page 745
 C.6 THE TRACER......Page 746
  C.6.1 Tracer Commands......Page 748
 C.7 GETTING STARTED......Page 750
 C.8.1 Hello World Example......Page 751
 C.8.2 General Registers Example......Page 754
 C.8.3 Call Command and Pointer Registers......Page 755
 C.8.4 Debugging an Array Print Program......Page 759
 C.8.5 String Manipulation and String Instructions......Page 761
 C.8.6 Dispatch Tables......Page 765
 C.8.7 Buffered and Random File Access......Page 767
INDEX......Page 772
 A......Page 774
 B......Page 775
 C......Page 776
 D......Page 778
 F......Page 780
 H......Page 781
 I......Page 782
 L......Page 784
 M......Page 785
 N......Page 786
 O......Page 787
 P......Page 788
 R......Page 789
 S......Page 790
 U......Page 792
 W......Page 793
 Z......Page 794