計算機組成與體系結構：英文版

CHAPTER  Introduction  1
 1.1  Overview  1
 1.2  The Main Components of a Computer  3
 1.3  An Example System: Wading through the Jargon  4
 1.4  Standards Organizations  10
 1.5  Historical Development  12
 1.5.1  Generation Zero: Mechanical Calculating Machines (1642-1945)  12
 1.5.2  The First Generation: Vacuum Tube Computers (1945-1953)  14
 1.5.3  The Second Generation: Transistorized Computers (1954-1965)  19
 1.5.4  The Third Generation: Integrated Circuit Computers (1965-1980)  21
 1.5.5  The Fourth Generation: VLSI Computers (1980-????)  22
 1.5.6  Moore's Law  24
 1.6  The Computer Level Hierarchy  25
 1.7  The von Neumann Model  27
 1.8  Non-von Neumann Models  29
 Chapter Summary  31
 Further Reading  31
 References  32
 Review of Essential Terms and Concepts  33
 Exercises  34
 CHAPTER  Data Representation in Computer Systems  37
 2
 2.1  Introduction 37
 2.2  Positional Numbering Systems 38
 2.3  Decimal to Binary Conversions  38
 2.3.1  Converting Unsigned Whole Numbers  39
 2.3.2  Converting Fractions  41
 2.3.3  Converting between Power-of-Two Radices  44
 2.4  Signed Integer Representation 44
 2.4.1  Signed Magnitude 44
 2.4.2  Complement Systems  49
 2.5  Floating-Point Representation  55
 2.5.1  A Simple Model  56
 2.5.2  Floating-Point Arithmetic  58
 2.5.3  Floating-Point Errors  59
 2.5.4  The IEEE-754 Floating-Point Standard 61
 2.6  Character Codes  62
 2.6.1  Binary-Coded Decimal  62
 2.6.2  EBCDIC  63
 2.6.3  ASCII  63
 2.6.4  Unicode 65
 2.7  Codes for Data Recording and Transmission  67
 2.7.1  Non-Return-to-Zero Code  68
 2.7.2  Non-Return-to-Zero-Invert Encoding  69
 2.7.3  Phase Modulation (Manchester Coding)  70
 2.7.4  Frequency Modulation  70
 2.7.5  Run-Length-Limited Code  71
 2.8  Error Detection and Correction 73
 2.8.1  Cyclic Redundancy Check  73
 2.8.2  Hamming Codes  77
 2.8.3  Reed-Soloman  82
 Chapter Summary 83
 Further Reading  84
 References  85
 Review of Essential Terms and Concepts  85
 Exercises  86
 CHAPTER  Boolean Algebra and Digital Logic    93
 3
 3.1  Introduction 93
 3.2  Boolean Algebra 94
 3.2.1  Boolean Expressions  94
 3.2.2  Boolean Identities  96
 3.2.3  Simplification of Boolean Expressions  98
 3.2.4  Complements  99
 3.2.5  Representing Boolean Functions  100
 3.3  Logic Gates  102
 3.3.1  Symbols for Logic Gates  102
 3.3.2  Universal Gates  103
 3.3.3  Multiple Input Gates  104
 3.4  Digital Components  10S
 3.4.1  Digital Circuits and Their Relationship to Boolean Algebra  105
 3.4.2  Integrated Circuits  106
 3.5  Combinational Circuits  106
 3.5.1  Basic Concepts  107
 3.5.2  Examples of Typical Combinational Circuits  107
 3.6  Sequential Circuits  113
 3.6.1  Basic Concepts  114
 3.6.2  Clocks  114
 3.6.3  Flip-Flops  115
 3.6.4  Examples of Sequential Circuits  117
 3.7  Desiguing Circuits 120
 Chapter Summary  121
 Further Reading  122
 References  123
 Review of Essential Terms and Concepts  123
 Exercises  124
 Focus on Karnaugh Maps  130
 3A.1  Introduction  130
 3A.2  Description of Kmaps and Terminology  131
 3A.3  Kmap Simplification for Two Variables  133
 3A.4  Kmap Simplification for Three Variables  134
 3A.5  Kmap Simplification for Four Variables  137
 3A.6  Don't Care Conditions  140
 3A.7  Summary  141
 Exercises  141
 CHAPTER  MARIE: An Introduction toa Simple Computer    14!
 4
 4.1  Introduction  145
 4.1.1  CPU Basics and Organization  145
 4.1.2  The Bus  147
 4.1.3  Clocks  151
 4.1.4  The Input/Output Subsystem  153
 4.1.5  Memory Organization and Addressing  153
 4.1.6  Interrupts  156
 4.2  MARIE 157
 4.2.1  The Architecture  157
 4.2.2  Registers and Buses  159
 4.2.3  The Instruction Set Architecture  160
 4.2.4  Register Transfer Notation  163
 4.3  Instruction Processing 166
 4.3.1  The Fetch-Decode-Execute Cycle  166
 4.3.2  Interrupts and FO  166
 4.4  A Simple Program 169
 4.5  A Discussion on Assemblers  170
 4.5.1  What Do Assemblers Do?  170
 4.5.2  Why Use Assembly Language?  173
 4.6  Extending Our Instruction Set 174
 4.7  A Discussion on Decoding: Hardwired vs. Microprogrammed
 Control  179
 4.8  Real-World Examples of Computer Architectures  182
 4.8.1  Intel Architectures  183
 4.8.2  MIPS Architectures  187
 Chapter Summary  189
 Further Reading  190
 References  191
 Review of Essential Terms and Concepts  192
 Exercises  193
 CHAPTER  A Closer Look at Instruction Set Architectures     199
 5
 5.1  Introduction  199
 5.2  Instruction Formats  199
 5.2.1  Design Decisions for Instruction Sets  200
 5.2.2  Little versus Big Endian  201
 5.2.3  Internal Storage in the CPU: Stacks versus Registers  203
 5.2.4  Number of Operands and Instruction Length  204
 5.2.5  Expanding Opcodes  208
 5.3  Instruction Types  210
 5.4  Addressing 211
 5.4.1  Data Types  211
 5.4.2  Address Modes  212
 5.5  Instruction-Level Pipelining  214
 5.6  Real-World Examples of ISAs 219
 5.6.1  Intel 220
 5.6.2  MIPS  220
 5.6.3  Java Virtual Machine  221
 Chapter Summary  225
 Further Reading  226
 References  227
 Review of Essential Terms and Concepts  228
 Exercises  229
 CHAPTER  Memory    233
 6
 6.1  Memory  233
 6.2  Types of Memory  233
 6.3  The Memory Hierarchy  235
 6.3.1  Locality of Reference  237
 6.4  Cache Memory  237
 6.4.1  Cache Mapping Schemes  239
 6.4.2  Replacement Policies  247
 6.4.3  Effective Access Time and Hit Ratio  248
 6.4.4  When Does Caching Break Down?  249
 6.4.5  Cache Write Policies 249
 6.5  Virtual Memory  250
 6.5.1  Paging  251
 6.5.2  Effective Access Time Using Paging  258
 6.5.3  Putting It All Together: Using Cache, TLBs, and Paging  259
 6.5.4  Advantages and Disadvantages of Paging and Virtual Memory  259
 6.5.5  Segmentation  262
 6.5.6  Paging Combined with Segmentation  263
 6.6  A Real-World Example of Memory Management 263
 Chapter Summary  264
 Further Reading  265
 References  266
 Review of Essential Terms and Concepts  266
 Exercises  267
 CHAPTER  Input/Output and Storage Systems   273
 7
 7.1  Introduction 273
 7.2  Amdahl's Law  274
 7.3  I/O Architectures 275
 7.3.1  I/O Control Methods  276
 7.3.2  I/O Bus Operation  280
 7.3.3  Another Look at Interrupt-Driven I/O  283
 7.4  Magnetic Disk Tedmology 286
 7.4.1  Rigid Disk Drives  288
 7.4.2  Flexible (Floppy) Disks  292
 7.5  Optical Disks 293
 7.5.1  CD-ROM  294
 7.5.2  DVD  297
 7.5.3  Optical Disk Recording Methods  298
 7.6  Magnetic Tape  299
 7.7  RAID 301
 7.7.1  RAID Level 0  302
 7.7.2  RAID Level 1  303
 7.7.3  RAID Level 2  303
 7.7.4  RAID Level 3  304
 7.7.5  RAID Level 4  305
 7.7.6  RAID Level 5  306
 7.7.7  RAID Level 6  307
 7.7.8  Hybrid RAID Systems  308
 7.8  Data Compression 309
 7.8.1  Statistical Coding 311
 7.8.2  Ziv-Lempel (LZ) Dictionary Systems  318
 7.8.3  GIF and PNG Compression  322
 7.8.4  JPEG Compression  323
 Chapter Summary  328
 Further Reading  328
 References  329
 Review of Essential Terms and Concepts  330
 Exercises  332
 Focus on Selected Disk Storage Implementations  335
 7A. 1  Introduction  335
 7A.2  Data Transmission Modes  335
 7A.3  SCSI 338
 7A.4  Storage Area Networks  350
 7A.5  Other I/O Connections  352
 7A.6  Summary  354
 Exercises  354
 CHAPTER  System Software      357
 8
 8.1  Introduction  357
 8.2  Operating Systems  358
 8.2.1  Operating Systems History  359
 8.2.2  Operating System Design  364
 8.2.3  Operating System Services  366
 8.3  Protected Environments  370
 8.3.1  Virtual Machines  371
 8.3.2  Subsystems and Partitions  374
 8.3.3  Protected Environments and the Evolution of Systems Architectures  376
 8.4  Programming Tools 378
 8.4.1  Assemblers and Assembly  378
 8.4.2  Link Editors 381
 8.4.3  Dynamic Link Libraries  382
 8.4.4  Compilers  384
 8.4.5  Interpreters  388
 8.5  Java: All of the Above 389
 8.6  Database Software  395
 8.7  Transaction Managers  401
 Chapter Summary  403
 Further Reading  404
 References  405
 Review of Essential Terms and Concepts  406
 Exercises  407
 CHAPTER  Alternative Architectures       411
 9
 9.1  Introduction 411
 9.2  RISC Machines 412
 9.3  Flynn's Taxonomy  417
 9.4  Parallel and Multiprocessor Architectures  421
 9.4.1  Superscalar and VLIW  422
 9.4.2  Vector Processors  424
 9.4.3  Interconnection Networks  425
 9.4.4  Shared Memory Multprocessors  430
 9.4.5  Distributed Computing 434
 9.5  Alternative Parallel Processing Approaches 435
 9.5.1  Dataflow Computing  435
 9.5.2  Neural Networks  438
 9.5.3  Systolic Arrays 441
 Chapter Summary  442
 Further Reading  443
 References  443
 Review of Essential Terms and Concepts  445
 Exercises  446
 CaAPTER  Performance Measurement and Analysis  451
 10
 10.1  Introduction 451
 10.2  The Basic Computer Performance Equation  452
 10.3  Mathematical Preliminaries 453
 10.3.1  What the Means Mean 454
 10.3.2  The Statistics and Semantics  459
 10.4  Benchmarking  461
 10.4.1  Clock Rate, MIPS, and FLOPS  462
 10.4.2  Synthetic Benchmarks: Whetstone, Linpack, and Dhrystone  464
 10.4.3  Standard Performance Evaluation Cooperation Benchmarks  465
 10.4.4  Transaction Performance Council Benchmarks  469
 10.4.5  System Simulation  476
 10.5  CPU Performance Optimization 477
 10.5.1  Branch Optimization 477
 10.5.2  Use of Good Algorithms and Simple Code  480
 10.6  Disk Performance 484
 10.6.1  Understanding the Problem 484
 10.6.2  Physical Considerations  485
 10.6.3  Logical Considerations  486
 Chapter Summary  492
 Further Reading  493
 References  494
 Review of Essential Terms and Concepts  495
 Exercises  495
 CHAPTER  Network Organization and Architecture  501
 11
 11.1  Introduction 501
 11.2  Early Business Computer Networks  501
 11.3  Early Academic and Scientific Networks: The Roots and Architecture of
 the Internet 502
 11.4  Network Protocols I: ISO/OSI Protocol Unification 506
 11.4.1  A Parable  507
 11.4.2  The OSI Reference Model  508
 11.5  Network Protocols II: TCP/IP Network Architecture  512
 11.5.1  The IP Layer for Version 4  512
 11.5.2  The Trouble with IP Version 4  516
 11.5.3  Transmission Control Protocol  520
 11.5.4  The TCP Protocol at Work 521
 11.5.5  IP Version 6  525
 11.6  Network Organization  530
 11.6.1  Physical Transmission Media  530
 11.6.2  Interface Cards  535
 11.6.3  Repeaters  536
 11.6.4  Hubs 537
 11.6.5  Switches  537
 11.6.6  Bridges and Gateways  538
 11.6.7  Routers and Routing  539
 11.7  High-Capacity Digital Links 548
 11.7.1  The Digital Hierarchy 549
 11.7.2  ISDN  553
 11.7.3  Asynchronous Transfer Mode  556
 1 1.8  A Look at the Internet  557
 11.8.1  Ramping on to the Intemet  558
 11.8.2  Ramping up the Intemet  565
 Chapter Summary  566
 Further Reading  566
 References  568
 Review of Essential Terms and Concepts  568
 Exercises  570
 APPENDIX  Data Structures and the Computer    575
 A
 A.1  Introduction  575
 A.2  FUNDAMENTAL Strnctures  575
 A.2.1  Arrays  575
 A.2.2  Queues and Linked Lists  577
 A.2.3  Stacks  578
 A.3  Trees  581
 A.4  Network Graphs  587
 Summary  590
 Further Reading  590
 References  590
 Exercises  591
 Glossary  595
 Answers and Hints for Selected Exercises  633
 Index  647