This book is intended for use in a first-level course on computer organization in electrical engineering,computer engineering,and computer science curricula.The book is self-contained,assuming only that the reader has a basic knowledge of computer programming in a gigh-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.

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 University, 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 Science. 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 Qaeen'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 Laboratory 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 Rivenide and in the LIP6 Laboratory of the University of Paris VI, France.
　　His 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 Northerm Electric Co., Ltd. in Bramalea, Ontario. In 1968, hejoined 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. ,Microcompurter Structures,　and Field-Programmable Gate Arrays. In 1990, he received the Wighton Fellowship for "innovative and distinctive contributions to undergraduate laboratory instruction."
Safwat Zaky received his B.Sc. degree in electrical engineering and B.Sc. in mathematics, both from Cairo University, Egypt, and his M.A.Sc. and Rh.D. degrees in electrical engineering from the University of Toronto. From 1969 to 1972 he was with Bell Northem Research, Bramalea, Ontario, where he worked on applications ofelectro optics and magnetics in mass storage and telephone switching. In 1973, he joioed 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, he serves as chair of the Deparanent of Elecaical and Computer Engineering. From 1980 to 198l. he was a senior visitor at the Computer Laboratory, University of Cambridge,England.
　　His research interests are in the areas of computer 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.

This book is intended for use in a first-level course on computer organization in electrical engineering,computer engineering,and computer science curricula.The book is self-contained,assuming only that the reader has a basic knowledge of computer programming in a gigh-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 distinct groups of undergraduates: electrical and computer enineering undergraduates, computer science specilalists ,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 illustrate the principles of computer organization using examples drawn from commercially available commputers.Our main examples are based on the following processors:ARM,Motorola 680X0,Intel Pentium,and Sun UltraSPARC.
　　It is important to recognize that digital system desing is not a straightforward process of applying optimal designalgorithms.Many design decisions are based largely on heuristic judgment and experience,They involve cost/performance and hardware/software tradeoffs over a range of alternatives.It is our goal to convey these notions to the reader.
　　We have endeavored to provide sufficient details to encourage the student to digbeyond the surface when dealing with ideas that seem to be intuitively obvious.We believe that this is best accomplished by giving real examples that are adequately documented .Block diagrams are a powerful means of describing organizational features of a computer.However,they can easily lead to an oversimplified view of problems involved.Hence,they must e accompanied by the details of implementation alternatives.
　　The book is aimed at a one-semester course in engineeringor computer science programs.It is suitable for both hardware-and software-oriented students.Even though the emphasis is on hardware,we have addressed a number of software issues,including basic aspects of compilers and operating systems related to instruction execution performance,coordination of parallel operations at the system level,and real-time applications.An understanding of hardware/software interaction and tradeoffs is necessary for computer specialists.

(美)Carl Hamacher 等：Carl Hamacher: Carl Hamacher 加拿大滑铁卢大学工程物理学士，加拿大金斯顿女皇大学（Queen誷 University at Kingston）电子工程硕士，纽约州Syracuse大学电子工程博士。1968～1990年任多伦多大学电子工程及计算机科学学院教授，1984～1988年担任计算机系统研究所所长，1988～1990年担任工程科学部主席。自1991年1月起任女皇大学电子及计算机工程学院教授，1991～1996年任应用科学系主任。1978～1979年曾作为访问学者到加利福尼亚州San Jose的IBM研究实验室工作。1986年作为访问研究员在法国Grenoble大学电路与系统实验室工作。1996～1997年作为访问教授在加州大学 Riverside 分校计算机科学系和法国Paris VI 大学LIP6实验室工作。 他的研究方向为多处理器与多计算机，侧重于网络互连。

Chapter I
BASIC STRUCTURE OF
1.l ComputerTypes
1.2 Functional Units
l.2.I Input Unit
l.2.2 Memory Unit
1.2.3 Arithmetic and Logic Unit
1.2.4 Output Unit
1.2.5 Control Unit
1.3 Basic Operational Concepts
1.4 Bus Structures
1.5 Software
1.6 Performance
1.6.I Processor Clock
1.6.2 Basic Performance Equation
1.6.3 Pipelining and Superscalar Operation
1.6.4 Clock Rate
l.6.5 Instruction Set CISC and RISC
1.6.6 Compiler
1.6.7 Performance Measurement
1.7 Multiprocessors and Multicomputers
l.8 Historical
1.8.I The First Generation
l.8.2 The Second Generation
l.8.3 The Third Generation
l.8.4 The Fourth Generation
1.8.5 Beyond the Fourth Generation
l.8.6 Evolution of Performance
1.9 Concluding Remarks
Problems
References
Chapter 2
MACHINE INSTRUCTIONS AND
2.1 Numbers, Arithmetic Operations, and Characters　　
2.I.1 Number Representation
2.1.2 Addition of Positive Numbers
2.1.3 Addition and Subtraction of Signed Numbers
2.l.4 Overflow in Integer Arithmetic
2.1.5 Characters
2.2 Memory Locations and Addresses
2.2.l Byte
2.2.2 Big-endian and Little-endian Assignments
2.2.3 Word Alignment
2.2.4 Accssing Numbers Character Strings
2.3 Memory Operations
2.4 Instructions and Instruction Sequencing
2.4.I Register Transfer Notation
2.4.2 Assembly Language Notation
2.4.3 Basic Instruction Types
2.4.4 lnstruction Execution and Straight-Line Sequencing
2.4.5 Branching
2.4.6 Condition Codes
2.4.7 Generating Memory Addresses
2.5 Addressing Modes
2.5.l Implementation of Variables and Constants
2.5.2 Indirection and Pointers
2.5.3 Indexing and Arrays
2.5.4 Relalive Addressing
2.5.5 Additional Modes
2.6 Assembly Language
2.6.I Assembler Directives
2.6.2 Assembly and Execution of Programs
2.6.3 Number Notation
2.7 Basic Input/Output Operations
2.8 Stacks and Queues
2.9 Subroutines
2.9.I Subroutine Nesting and the Processor Stack
2.9.2 Parameter Passing
2.9.3 The Stack Frame
2. 10 Additional Instructions
2.l0.l Logic Instructions
2.10.2 Shift and Rotate Instructions
2.10.3 Multiplication and Division
2.11 Example Programs
2.11.l Vector Dot Product Program
2.11.2 Byte-Sorting Program
2.11.3 Linked Lists
2.12 Encoding of Machine Instructions
2.13 Concluding Remarks
Problems
Chapter 3
ARM MOTOROLA, AND INTEL
INSTRUCTIONSETS
Part I TheARM Example
3.l Registers, Memory Access, and Data Transfer
3.l.l Register Structure
3.l.2 Memory Access lnstructions and Addressing Modes
3.l.3 Register Move Instructions
3.2 Arithetic and Logic Instructions
3.2.l Arithmetic Instructions
3.2.2 Logic Instructions
3.3 Branch Instructions
3.3.l Setting Condition Codes
3.3.2 A Loop Program for Adding Numbers
3.4 Assembly Language
3.4.l Pseudo-Instructions
3.5 I/O Operations
3.6 Subroutines
3.7 Program Examples
3.7.l Vector Dot Product Program
3.7.2 Byte-Sorting Program
3.7.3 Linked-List Insertion and Deletion Subroutines
PartII　The 68000 Example
3.8 Registers and Addressing
3.8.l The 68OOO Register Structure
3.8.2 Addressing
3.9 Instructions
3.IO Assembly Language
3.ll Program Flow Control
3.Il.l Condition Code Flags
3.Il.2 Branch Instructions
3.12 I/O Operations
3.13 Stacks and Subroutines
3.14 Logic Instructions
3.15 Program Examples
3.15.I Vector Dot Product Program
3.15.2 Byte-Sorting Program
3.15.3 Linked-List Insertion and Deletion Subroutines
PartIII The IA-32 Pentium Example
3.16 Registen and Addressing
3.16.l IA-32 Register Structure
3.16.2 IA-32 Addressing Modes
3.17 IA-32 Instructions
3.17.l Machine Instruction Format
3.I8 IA-32 Assembly Language
3.19 Program Flow Control
3.19.l Conditional Jumps and Condition Code Flags
3.19.2 Unconditional Jump
3.20 Logic and Shift/Rotate Instructions
3.20.l Logic Operations
3.20.2 Shift and Rotate Operalions
3.21 I/O Operations
3.21.l Memory-MappedI/O
3.21.2 Isolated I/O
3.21.3 BlockTransfers
3.22 Subroutines
3.23 Other instructions
3.23.l Multiply and Divide Instructions
3.23.2 Multimedia Extension (MMX) Instructions
3.23.3 Vector(SIMD) Instructions
3.24 Program Examples
3.24.l Vector Dot Product Rogram
3.24.2 Byte-Sorting Program
3.24.3 Linked-List Insertion and Deletion Subroutines
3.25 Concluding Remarks
Problems
References
Chapter 4
INPUT
4.l Accessing I/O Devices
4.2 Interrupts
4.2.l Interrupt Hardware
4.2.2 Enabling and Disabling Interrupts
4.2.3 Handling Multiple Devices
4.2.4 Controlling Device Reqaests
4.2.5 Exceptions
4.2.6 Use of Interrupts in Operaling Systems
4.3 Processor Examples
4.3.l ARM Interrupt Structure
4.3.2 68000 Interrupt Structure
4.3.3 Pentium Interrupt Structure
4.4 Direct Memory Access
4.4.1 Bus Arbitration
4.5 Buses
4.5.l Synchronous Bus
4.5.2 Asynchronous Bus
4.5.3 Discussion
4.6 Interface Circuits
4.6.l Parallel Port
4.6.2 Serial Port
4.7 Standard I/O Interfaces
4.7.l Peripheral Component Interconnect (PCD) Bus
4.7.2 SCSI Bus
4.7.3 Universal Serial Bus (USB)
4.8 Concluding Remarks
Problems
References
Chapler 5
THE MEMORYSYSTEM
5.l Some Basic Concepts
5.2 Semiconductor RAM Memories
5.2.l Internal Organization of Memory Chips
5.2.2 Static Memories
5.2.3 Asynchronous Drams
5.2.4 Synchronous DRAMs
5.2.5 Structure of Larger Memones
5.2.6 Memory System Considerations
5.2.7 Rambus Memory
5.3 Read-Only Memories
5.3.l ROM
5.3.2 PROM
5.3.3 EPROM
5.3.4 EEPROM
5.3.5 Flash Memory
5.4 Speed, Size. and Cost
5.5 Cache Memories
5.5.l Mapping Functions
5.5.2 Replacement Algorithms
5.5.3 Example of Mapping Techniques
5.5.4 Examples of Caches in Commercial Processors
5.6 Performance Considerations
5.6.1 Interleaving
5.6.2 Hit Rate and Miss Penalty
5.6.3 Caches on the Processor Chip
5.6.4 Other Enhancements
5.7 Virual Memories
5.7.l Address Translation
5.8 Memory Management Requilements
5.9 Secondary Storage
5.9.l Magnetic Hard Disks
5.9.2 Optical Disks
5.9.3 Magnetic Tape Systems
5.IO Concluding Remarks Problems
References
Chapter 6
6. l Addition and Subtraction of Signed Numbers
6. l .l Addition/Subtraction Logic Unit
6.2 Design of Fast Adders
6.2.l Carry-Lookahead Addition
6.3 Multiplicalion of Positive Numbers
6.4 Signed-Opeand Multiplication
6.4.l Booth Algorithm
6.5 Fast Multiplication
6.5.l Bit-Palr Recoding of Multipliers
6.5.2 Carry-Save Addition of Summands
6.6 Integer Division
6.7 Floating-Point Numbers and Opeations
6.7.l IEEE Standard for Floating-Point Numbers
6.7.2 Arithmetic Opeations on Floating-Point Numbers
6.7.3 Guard Bits and Truncation
6.7.4 Implementing Roating-Point Operations
6.8 Coocluding Remarks
Problems
References
Chapter 7
BASIC PROCESSING UNIT
7.l Some Fundamental Concepts
7.l.1 Register Transfers
7.l.2 Performing an Arithmetic or Logic Operatian
7.l.3 Fetching a Word from Memory
7.1.4 Storing a Word in Memory
7.2 Execution of a Complete Instruction
7.2.1 Branch Instructions
7.3 Multiple-Bus Organization
7.4 Hardwired Control
7.4.1 A Complete Processor
7.5 Microprogrammed Control
7.5.1 Microinstructions
7.5.2 Microprogram Sequencing
7.5.3 Wide-Branch Addressing
7.5.4 Microinstructions with Next-Address Field
7.5.5 Prefetching Microinstructions
7.5.6 Emulation
7.6 Concluding Remarks
Problems
Chaprer 8
8.1 Basic Concepts
8.1.l Role of Cache Memory
8.l.2 Pipeline Performance
8.2 Data Hazards
8.2. l Operand Forwarding
8.2.2 Handling Data Hazards in Software
8.2.3 Side Effects
8.3 1nstruction Hazards
8.3.1 Unconditional Branches
8.3.2 Condilional Branches and Branch Prediction
8.4 Influence on Instruction Sets
S.4.1 Addressing Modes
8.4.2 Condition Codes
8.5 Datapath and Control Considerations
8.6 Superscalar Operation
8.6.l Out-of-Order Execution
8.6.2 Execution Completion
8.6.3 Dispatch Operation
8.7 UItraSPARC II EXAMPLE
8.7.l SPARC Architecture
8.7.2 UltraSPAXC II
8.7.3 Pipeline Structure
8.8 Performance Considerations
8.8.l Effect of Instruction Hazards
8.8.2 Number of Pipeline Stages
8.9 Concluding Remarks
Problems
Reference
Chapter 9
EMBEDDED SYSTEMS
9.l Examples of Embedded Systems
9.1.l Microwave Oven
9.l.2 Digital Camera
9.1.3 Home Telemetry
9.2 Processor Chips for Embedded Applications
9.3 A Simple Microcontroller
9.3.l Parallel I/O Ports
9.3.2 Serial I/O Interface
9.3.3 Counter/Timer
9.3.4 Interrupt Control Mechanism
9.4 Programming Considerations
9.4.l Polling Approach
9.4.2 Interrupt　Approach
9.5 I/O Device Timing Constraints
9.5.l C Program for　Transfer via a Circular Buffer
9.5.2 Assembly Language Program for Transfer via a Circular Buffer
9.6 Reaction Timer-An Example
9.6.l C Program for the Reaction Timer
9.6.2 Assembly Language Program for the Reaction Timer
9.6.3 Final Comments
9.7 Embedded Processor Families
9.7.1 Microcontrollers Based on the Intel 8051
9.7.2 Motorola Microcontrollers
9.7.3 ARM Microcontrollers
9.8 DesignIssues
9.9 System-on-a-Chip
9.9. I FPGA Implementation
9.IO Concluding Remarks
Problems
References
Chaprer l0
l0. 1 Input Devices
l0.1.l Keyboard
l0.l.2 Mouse
l0.l.3 Trackball. Joystick_ and
l0 uchpad
l0.l.4 Scanners
l0.2 Output Devices
l0.2.l Video Displays
l0.2.2 Flat-Panel Displays
l0.2.3 Printers
l0.2.4 Graphics Accelerators
l0.3 Serial Communication Links
l0.3.l Asynchronous Transmission
l0.3.2 Synchronous Transmission
l0.3.3 Standard Communications Interfaces
l0.4 Concluding Remarks
Problems
Chapter 11
PROCESSORFAMILIES
ll.l The ARM Family
ll.I.l The Thumb lustruction Set
ll.l.2 Processor and CPU Cores
ll.2 The Motorola 680XO and CoIdFire Families
ll.2.l 68020 Processor
ll.2.2 Enhancements in 68030 and 6804O Processors
ll.2.3 68060 Processor
ll.2.4 The ColdFire Family
ll.3 The Intel IA-32 Family
ll.3.l IA-32 Memory Segmentation
ll.3.2 Sixteen-BitMode
ll.3.3 80386and 80486 Processors
ll.3.4 Pentium Processor
ll.3.5 Pentium Pro Processor
ll.3.6 Pentium II and III Processors
ll.3.7 Pentium4Processor
ll.3.8 Advanced Micro Devices IA-32 Processors
11.4 The PowerPC Family
11.4.l RegisterSet
11.4.2 Memory Addressing Modes
11.4.3 Instructions
11.4.4 PowerPC Processon
11.5 The Sun Microsystems SPARC Family
11.6 The Compaq Alpha Family
11.6.l Instruction and Addressing Mode Formats
11.6.2 Alpha 21064 Processor
11.6.3 Alpha 21164 Processor
11.6.4 Alpha 21264 Processor
11.7 The Intel IA-64 Family
11.7.I InastructionBundles
11.7.2 Conditional Execution
ll.7.3 Speculalive Loads
l1.7.4 Registers and the Register Stack
11.7.5 ItaniumProcessor
11.8 A Stack Processor
11.8.1 Stack Structure
11.8.2 Stack Instructions
11.8.3 Hardware Registers in the Stack
11.9 Concluding Remarks
Problems
References
Chapter 12
LARGE
12.l Forms of Parallel Processing
12.l.l Classification of Parallel Structures
12.2 Array
12.3 The Structure of General-Purpose Multiprocessors
12.4 Bltaeomection Newolb
12.4.l SingleBus
12.4.2 Crossbar Networks
12.4.3 Multistage Networks
12.4.4 Hypercube Networks
12.4.5 MeshNetworks
12.4.6 TreeNetworks
12.4.7 RingNetworks
12.4.8 Practical
12.4.9 Mixed Topology Networks
12.4.10 Symmetric Multiprocessors
l2.5 Memory Organization in Multiprocessors
12.6 Program Parallelism and Shared Variables
12.6.l Accessing Shared Variables
12.6.2 Cache Cnherence
12.6.3 Need for Locking and Cache Coherence
12.7 Multicomputers
12.7.l Local Area Networks
12.7.2 Ethernet (CSMA/CD) Bus
12.7.3 TokenRing
12.7.4 Network of Workstations
12.8 Programmer's View of Shared Memory and Message Passing
12.8.l SharedMemoryCase
12.8.2 Message-Passing Case
12.9 Performance Considerations
12.9.l Amdahl'sLaw
12.9.2 Performance Indicators
12.IO Concluding Remarks
Problems
References
APPENDIX A: LOGIC CIRCUITS
A.l Basic Logic Functions
A. l .l EIectronic Logic Gates
A.2 Synthesis ofLogic Functions
A.3 Minimization of Logic Expressions
A.3.l Minimization Using Karnaugh Maps
A.3.2 Don't-Cale Conditions
A.4 Synthesis with NAND and NOR Gates
A.5 Practical Implementation of Logic Gates
A.5.l CMOS Circuits
A.5.2 Propagation Delay
A.5.3 Fan-In and Fan-Out Constraints
A.5.4 Tri-state Buffers
A.5.5 Integrated Circuit Packages
A.6 Flip-Flops
A.6. l Gated Latches
A.6.2 Master-Slave Flip-Flop
A.6.3 Edge Triggering
A.6.4 T Flip-Flop
A.6.5 JK Flip-Flop
A.6.6 Flip-Flops with Reset and Clear
A.7 Registers and Shift Registers
A.8 Counters
A.9 Decoders
A.IO Multiplexers
A.Il Programmable Logic Devices pLDs)
A.Il.l Progammable Logic Array(PLA)
A.ll.2 Programmable Array Logic(PAI.)
A.II.3 Complex Programmable Logic Devices(CPLDs)
A. 12 Field-Programmable Gate Arrays
A. 13 Seqnential Circuits
A.13.I An Example of an Up/Down Counter
A.13.2 Timing Diagrams
A.13.3 The Finite State Machine Model
A.13.4 Synthesis of Finite State Machines
A.14 Concluding Remarks
Problems
References
SET
B.l Instruction Encoding
B.I.l Arithmetic and Logic Instructions
B. l .2 Memary Load and Store Instructions
B.l.3 Block Load and Store Instructions
B.l.4 Branch and Branch with Link Instructions
B. l .5 Machine Control Instructions
B.2 Other ARM Instructions
B.2.l Coprocessor Instructions
B.2.2 Versions v4 and v5 Instructions
B.3 Programming Experiments
INSTRUCTION　SET
APPENDIX D: INTELIA-32
INSTRUCTION　SET
D.l Instruction Encoding
D.l.l Addressing Modes
D.2 Basic Instructions
D.2.I Conditional Jump Instructions
D.2.2 Unconditional Jump Instructions
D.3 PrefixBytes
D.4 Other Insutructions
D.4.l String Instructions
D.4.2 Floating-Point. MMX, and SSE Instructions
D.5 Sixteen-Bit Operation
D.6 Programming Experiments NUMBER
E.l Character, Codes
E.2 Decimal-to-Binary Conversion
INDEX