Computer Organisation and Architecture: Evolutionary Concepts, Principles, and Designs

Cover
Half Title
Title Page
Copyright Page
Table of Contents
Preface
Acknowledgements
Author
Part I: Fundamental Computer Organisation
	1. Computer and Its Environment
		1.1 History in Short
		1.2 Computer Organisation and Architecture
		1.3 Hardware and Software: An Introductory Concept
		1.4 Hardware and Software: Their Roles and Characteristics
		1.5 Evolution of Computers: Salient Milestones
			1.5.1 The Generation of Computers: Electronic Era
				1.5.1.1 Von Neumann Architecture: Stored-Program Concept
				1.5.1.2 Second-Generation Systems (1955–1965)
				1.5.1.3 Integrated Circuits (ICs) and Moore’s Law
				1.5.1.4 Third-Generation Systems (1965–1971): The MSI Era
				1.5.1.5 Fourth-Generation Systems (1972–1978): The LSI Era
				1.5.1.6 Fifth-Generation Systems (1978–1991): The VLSI Era
				1.5.1.7 Sixth-Generation Systems (1991–Present): The ULSI Era
				1.5.1.8 Grand Challenges: Tomorrow’s Microprocessors
		1.6 Evolution of Operating System and System Software: Their Roles
			1.6.1 Modern Operating Systems
		1.7 Genesis of Computer Organisation and Architecture
		1.8 Summary
		Exercises
		Suggested References and Websites
	2. Computer System Organisation
		2.1 Modular Design Levels
		2.2 Methods of Design
			2.2.1 The Processor Level
				2.2.1.1 Design Approach
				2.2.1.2 Performance and Related Factors
				2.2.1.3 Processor Clock
				2.2.1.4 Performance Assessment: A Rough Estimation
				2.2.1.5 Design Principles: CISC and RISC
				2.2.1.6 Speed-Up Approach
				2.2.1.7 Performance Measurements
			2.2.2 The Register Level
				2.2.2.1 Combinational Components
				2.2.2.2 Sequential Components
				2.2.2.3 General Representation
				2.2.2.4 Combinational Circuits
				2.2.2.5 Sequential Circuits
				2.2.2.6 Tri-State Buffers
			2.2.3 The Gate Level
				2.2.3.1 Basic Memory Components: Latches and Flip–Flops
			2.2.4 Genesis of Digital Systems
		2.3 Summary
		Exercises
		Suggested References and Websites
	3. Processor Basics – Structure and Function
		3.1 Introduction
		3.2 Processor (CPU) Organisation
			3.2.1 Fundamental Concepts
		3.3 Register Organisation
			3.3.1 User-Accessible Registers
			3.3.2 Control and Status Registers
			3.3.3 Register Organisation in Microprocessor: IA-32/64 and MC68000
				3.3.3.1 Motorola MC68000 Series
				3.3.3.2 Intel IA-32 Architecture
				3.3.3.3 Intel IA-64 Architecture
		3.4 Stack Organisation
		3.5 Generalized Structure of CPU
		3.6 CPU Operation: Instruction Execution
		3.7 Instruction Set
			3.7.1 Machine Instruction Elements
			3.7.2 Instruction Formats and Design Criteria
		3.8 Types of Operands
		3.9 Intel X-86 (IA-32 and IA-64) Data Types
		3.10 Types of Instructions and Related Operations
			3.10.1 Arithmetic
			3.10.2 Logical
			3.10.3 Shift Operation
			3.10.4 Data Transfer
			3.10.5 Input/Output (I/O)
			3.10.6 Transfer of Control
				3.10.6.1 Branch Instructions
				3.10.6.2 Skip Instruction
				3.10.6.3 Subroutine Call Instruction
			3.10.7 System Control
				3.10.7.1 System Call versus Subroutine Call
			3.10.8 Other Operations: IA-32 Instruction Set
				3.10.8.1 MMX (Multimedia Extension) Operation
				3.10.8.2 Streaming SIMD Extension (SSE)
		3.11 Instruction Addressing Scheme
		3.12 Addressing Modes
		3.13 Intel X-86 Addressing Modes: IA-32 and IA-64
		3.14 Register-Organised CPU
			3.14.1 Accumulator-Based CPU (Single Accumulator Organisation)
			3.14.2 General Register-Organised CPU (Multiple Register)
				3.14.2.1 The Intel IA-32/IA-64 Architecture
				3.14.2.2 Register Organisation
		3.15 Stack-Organised CPU (A Stack Processor)
			3.15.1 Expression Evaluation and Reverse Polish Notation
		3.16 Stack-Organised Symbolic LISP Processor
		3.17 Summary
		Exercises
		Suggested References
	4. Memory Organisation
		4.1 Memory System Overview
			4.1.1 Key Characteristics of the Memory System
		4.2 The Memory Hierarchy
		4.3 Semiconductor Main Memory
			4.3.1 Random-Access Memory (RAM)
			4.3.2 Cell Organisation
			4.3.3 Static RAM (SRAM)
			4.3.4 Dynamic RAM (DRAM)
				4.3.4.1 Schemes For Refreshing DRAM
			4.3.5 SRAM vs DRAM: A Rough Comparison
			4.3.6 RAM Organisation
				4.3.6.1 2D Organisation
				4.3.6.2 2½D (Word-Oriented) Organisation
			4.3.7 Advanced DRAM Organisation
				4.3.7.1 SDRAMs (Synchronous DRAMs)
				4.3.7.2 DDR SDRAM
				4.3.7.3 Rambus DRAM (RDRAM)
				4.3.7.4 Cache DRAM (CDRAM)
			4.3.8 Other Types of Random-Access Semiconductor Memory
				4.3.8.1 ROM (Read-Only Memory)
				4.3.8.2 PROM (Programmable ROM)
				4.3.8.3 EPROM (Erasable PROM)
				4.3.8.4 EEPROMs (Electrically Erasable PROM)
				4.3.8.5 Flash Memory (Flash EEPROM)
				4.3.8.6 USB Flash Drive: Pen Drive
			4.3.9 RAM Module Organisation
		4.4 Serial-Access Memory: External Memory
			4.4.1 Characteristics
			4.4.2 Rotating Memory (Disk) Organisation
				4.4.2.1 Read–Write Mechanism
			4.4.3 Device Controller: Rotating Memory
			4.4.4 Magnetic Disk
				4.4.4.1 Commodity Disk Considerations
				4.4.4.2 RAID: Redundant Array of Inexpensive Disks
				4.4.4.3 Disk Cache
			4.4.5 Magnetic Tape
		4.5 Optical Memory: External Memory
			4.5.1 Compact Disk (CD) Technology
			4.5.2 CD-ROM (Compact Disk Read-Only Memory)
			4.5.3 CD-Recordable: CD-R (WORM)
			4.5.4 CD-Rewritable (CD-RW): Erasable Optical Disk
			4.5.5 Digital Versatile Disk (DVD)
				4.5.5.1 High-Definition Optical Disk: HD-DVD and Blu-Ray
		4.6 Virtual Memory
			4.6.1 Background
			4.6.2 Address Space
			4.6.3 Address Mapping
			4.6.4 Types of Virtual Memory
			4.6.5 Address Translation Mechanisms
			4.6.6 Translation Lookaside Buffer (TLB)
			4.6.7 Working-Set Model
			4.6.8 Demand Paging Systems
			4.6.9 Page Replacement Principles
			4.6.10 Page Replacement Policies
				4.6.10.1 Not Recently Used Page Replacement (NRU)
				4.6.10.2 First-In–First-Out (FIFO)
				4.6.10.3 Least Recently Used Page (LRU)
				4.6.10.4 Performance Comparison
			4.6.11 Segmentation
				4.6.11.1 Pure Segmentation
				4.6.11.2 Segmentation with Paging
				4.6.11.3 Paged Segmentation in Mainframe (IBM 370/XA)
				4.6.11.4 Paged Segmentation in Microprocessor (Intel Pentium)
		4.7 Cache Memory
			4.7.1 Background
			4.7.2 Objective
			4.7.3 Hierarchical View
			4.7.4 Principles
			4.7.5 Cache–Main Memory Hierarchy: Its Performance
			4.7.6 Cache Design
			4.7.7 Cache Design Issues: Different Elements
				4.7.7.1 Cache Size
				4.7.7.2 Block Size
				4.7.7.3 Mapping Schemes
				4.7.7.4 Cache Initialization
				4.7.7.5 Writing into Cache
				4.7.7.6 Replacement Policy (Algorithm)
			4.7.8 Multiple-Level Caches
			4.7.9 Unified Cache and Split Cache
				4.7.9.1 Implementation: PENTIUM Cache Organisation
				4.7.9.2 Motorola RISC MPC7450 Cache Organisation
			4.7.10 Cache Addressing
				4.7.10.1 Physical Address Cache
				4.7.10.2 Virtual Address Cache
			4.7.11 Miss Rate and Miss Penalty
				4.7.11.1 Types of Cache Misses and Reduction Techniques
				4.7.11.2 Miss Penalty and Reduction Techniques
			4.7.12 Caches in Multiprocessor
			4.7.13 Cache Coherence
			4.7.14 Reasons of Coherence Problem
			4.7.15 Cache Coherence Problem: Solution Methodologies
				4.7.15.1 No Private Cache
				4.7.15.2 Software Solution
				4.7.15.3 Hardware-Only Solution
			4.7.16 Two-Level Memory Performance: Cost Consideration
			4.7.17 Memory Hierarchy Design: Size and Cost Consideration
		4.8 Interleaved Memory Organisation
			4.8.1 Background
			4.8.2 Memory Interleaving
			4.8.3 Types of Interleaving
			4.8.4 Interleaving in Motorola 68040
			4.8.5 Conclusion
		4.9 Associative Memory Organisation
			4.9.1 Background
			4.9.2 Implementation
				4.9.2.1 Word-Organised Associative Memory
		4.10 Summary
		Exercises
		Suggested References and Websites
	5 Input–Output Organisation
		5.1 Input–Output System
		5.2 I/O Module: I/O Interface
			5.2.1 I/O Module Design
		5.3 Types of I/O Operations: Definitions and Differences
			5.3.1 Programmed I/O (Using Buffer)
			5.3.2 Interrupt-Driven I/O
				5.3.2.1 Interrupt-Driven I/O: Design Issues
			5.3.3 Direct Memory Access (DMA) I/O
				5.3.3.1 Introduction
				5.3.3.2 Definition
				5.3.3.3 Essential Features
				5.3.3.4 Processing Details
				5.3.3.5 Different Transfer Types
				5.3.3.6 Implementation Mechanisms: Different Approaches
			5.3.4 I/O Processor (I/O Channels)
				5.3.4.1 Introduction
				5.3.4.2 I/O Channel
				5.3.4.3 I/O Processor (IOP) And Its Organisation
		5.4 Bus, Bus System and Bus Design
			5.4.1 Bus Structure
			5.4.2 Bus Arbitration
			5.4.3 Bus Protocol
			5.4.4 Bus Design Parameters
			5.4.5 Bus Interfacing: Tri-State Devices
			5.4.6 Some Representative Bus Systems of Early Days
			5.4.7 PCI (Peripheral Component Interconnect): Local Bus
			5.4.8 SCSI (Small Computer System Interface) BUS
			5.4.9 Universal Serial Bus (USB)
			5.4.10 FireWire Serial Bus
			5.4.11 InfiniBand
		5.5 PORT and Its Different Types
			5.5.1 Serial Port
			5.5.2 Parallel Port
			5.5.3 USB Port
		5.6 Summary
		Exercises
		Suggested References and Websites
	6 Control Unit: Design and Operation
		6.1 Introduction
		6.2 Micro-Operations: Fetch Cycle
		6.3 Design Issues
		6.4 Methods of Implementation
			6.4.1 Hardwired Control
				6.4.1.1 Control Unit Logic
				6.4.1.2 Control Signals in Accumulator-Based CPU
			6.4.2 Microprogrammed Control
				6.4.2.1 Basic Concepts: Microinstructions
				6.4.2.2 Microprogrammed Control Unit Organisation
				6.4.2.3 Microinstruction Design Issues
				6.4.2.4 Horizontal versus Vertical
				6.4.2.5 Encoding Schemes
				6.4.2.6 Addressing Schemes
				6.4.2.7 Emulation
				6.4.2.8 Merits and Drawbacks
				6.4.2.9 Application Areas
			6.4.3 Nanoprogramming
		6.5 Summary
		Exercises
		Suggested References
	7 Arithmetic and Logic Unit Organisation
		7.1 Numerical Representations: Number Systems
			7.1.1 Decimal System
			7.1.2 Binary System
			7.1.3 Hexadecimal and Octal System
				7.1.3.1 Merits of Hex and Octal Systems
			7.1.4 BCD (Binary-Coded Decimal) Code
			7.1.5 Gray Code
		7.2 Number Representations: Binary Systems
			7.2.1 Sign-Magnitude Representation
			7.2.2 1’s (One’s) Complement Representation
			7.2.3 2’s (Two’s) Complement Representation
				7.2.3.1 Conversion: Decimal to 2’s Complement and Vice Versa
		7.3 Addition and Subtraction: Signed Numbers
		7.4 Overflow: Integer Arithmetic
		7.5 Characters
		7.6 Arithmetic and Logic Unit (ALU)
		7.7 Fixed-Point Arithmetic
			7.7.1 Addition and Subtraction
				7.7.1.1 Basic Adders
				7.7.1.2 Subtracters
			7.7.2 High-Speed Adder
				7.7.2.1 Carry-Lookahead Adder (CLA)
				7.7.2.2 Adder Expansion
				7.7.2.3 Carry-Save Adder (CSA)
			7.7.3 Multiplication
				7.7.3.1 Unsigned Integers
				7.7.3.2 Signed-Magnitude Numbers
				7.7.3.3 Signed-Operand Multiplication
				7.7.3.4 Fast Multiplication: Carry-Save Addition
			7.7.4 Division
				7.7.4.1 Unsigned Integers
		7.8 Floating-Point Representation
			7.8.1 Normalized Form
			7.8.2 Range and Precision
			7.8.3 IEEE Standard: Binary Floating-Point Representation
			7.8.4 Exceptions and Special Values
			7.8.5 Floating-Point Representation: Merits and Drawbacks
		7.9 Floating-Point Arithmetic
			7.9.1 Addition and Subtraction
				7.9.1.1 Implementation: Floating-Point Unit
			7.9.2 Multiplication and Division
				7.9.2.1 Implementation: Floating-Point Multiplication
		7.10 Precision Considerations: Guard Bits
			7.10.1 Truncation
			7.10.2 Rounding: IEEE Standard
			7.10.3 Infinity; NaNs; and Denormalized Numbers: IEEE Standards
		7.11 Summary of Floating-Point Numbers
		7.12 Summary
		Exercises
		Suggested References and Websites
Part II: High-End Processor Organisation
	8. Pipeline Architecture
		8.1 Pipeline Concept
		8.2 Pipeline Approach: Instruction-Level Parallelism
		8.3 Implementation
		8.4 Linear and Nonlinear (Static and Dynamic) Pipelines
			8.4.1 Linear Pipeline:Asynchronous and Synchronous Models
			8.4.2 Characteristics and Behaviour: Space-Time
			8.4.3 Speed-Up, Efficiency and Throughput
			8.4.4 Nonlinear (Dynamic) Pipeline
				8.4.4.1 Reservation Table
				8.4.4.2 Latency and Collision
		8.5 Areas of a Pipeline
			8.5.1 Instruction Pipeline
				8.5.1.1 Limitations
			8.5.2 Pipeline Hazards and Solution Methodology
				8.5.2.1 Structural Hazard and Solution Approaches
				8.5.2.2 Data Hazard (Data Dependency) and Solution Approaches
				8.5.2.3 Control Hazard
			8.5.3 Arithmetic Pipeline
				8.5.3.1 Adder Pipeline Design
				8.5.3.2 Multiplication Pipeline Design
		8.6 Pipeline Control and Collision-Free Scheduling
			8.6.1 Control Scheme: Collision Vectors
			8.6.2 State Diagrams
			8.6.3 Greedy Cycles and Minimum Average Latency (MAL)
			8.6.4 Dynamic Pipeline Scheduling
				8.6.4.1 Implementation
		8.7 Superpipeline Architecture
			8.7.1 Superpipeline Performance
		8.8 Superscalar Architecture
			8.8.1 Requirements and Essential Components
			8.8.2 Multipipeline Scheduling
			8.8.3 Superscalar Performance
			8.8.4 Superscalar Processors: Key Factors
			8.8.5 Implementation: Superscalar Processors
		8.9 Superpipelined Superscalar Processors
			8.9.1 Superpipelined Superscalar Performance
			8.9.2 Implementation:Superpipelined Superscalar Processors
				8.9.2.1 DEC Alpha 21X64
				8.9.2.2 Intel Pentium 4
		8.10 VLIW and EPIC Architectures
			8.10.1 Instruction Bundles:the Intel IA-64 Family
		8.11 Thread-Level Parallelism: Multithreading
			8.11.1 Scalar Processor
			8.11.2 Superscalar Processor
			8.11.3 VLIW Processor
			8.11.4 Simultaneous Hardware Multithreaded Processor (SHMT)
			8.11.5 Chip Multiprocessors (Multicore Processors)
		8.12 Multicore Architecture
			8.12.1 Background
			8.12.2 Definition
			8.12.3 Design Issues
			8.12.4 Multicore Organisation
			8.12.5 Basic Multicore Implementation: Intel Core Duo
			8.12.6 Intel Core 2 DUO
			8.12.7 Intel Core 2 Quad
		8.13 Multicore with Hardware Multithreading
			8.13.1 IBM Power 5
			8.13.2 Intel Core i7
				8.13.2.1 Distinctive Features of Intel Core i7 900-Series Processors
			8.13.3 Sun UltraSPARC T2 Processor
		8.14 Summary
		Exercises
		Suggested References and Websites
	9. RISC Architecture
		9.1 Background: Evolution of Computer Architecture
		9.2 Characteristics of CICS and Its Drawbacks
			9.2.1 Drawbacks
		9.3 RISC: Definition and Features
		9.4 Representative RISC Processors
		9.5 RISC Characteristics
		9.6 The RISC Impacts and Drawbacks
			9.6.1 Drawbacks
		9.7 RISC versus CISC Debate
			9.7.1 Running Programs in High-Level Languages
			9.7.2 Technology of the Components
			9.7.3 Role of Large Register File
		9.8 RISC Design Issues
		9.9 RISC Instruction Set
		9.10 RISC Instruction Format
		9.11 RISC Addressing Mode
		9.12 Register Windows: The Large Register File
		9.13 Register File and Cache Memory
		9.14 Comparison between RISCs and CISCs
		9.15 RISC Pipelining
		9.16 RISC and CISC Union: Hybrid Architecture
		9.17 Types of RISC Processors
			9.17.1 PowerPC Processors
			9.17.2 SPARC Family of Processors
				9.17.2.1 UltraSPARC Processors
			9.17.3 MIPS Processors
			9.17.4 PA-RISC Processors
			9.17.5 ARM (Advanced RISC Machine) Processors
			9.17.6 Motorola Processors (MC 88000)
		9.18 Comparison of Four Representative RISC Machines
		9.19 Summary
		Exercises
		Suggested References and Websites
	10. Parallel Architectures
		10.1 Introduction
		10.2 Classicfication of Computer Architectures: Flynn’s Proposal
		10.3 Parallel Computers: Forms and Issues
		10.4 Parallel Computers: Its Classitication
		10.5 Parallel Computers: Its Environment
		10.6 Interconnection Networks
			10.6.1 Interconnection Network: Different Types
				10.6.1.1 Hierarchical Common (Shared) Bus Systems
				10.6.1.2 Crossbar Networks
				10.6.1.3 Multiport Memory
				10.6.1.4 Multistage Networks
				10.6.1.5 Omega Network (Perfect Shuffle)
				10.6.1.6 Benes Network
				10.6.1.7 The Hot-Spot Problem
				10.6.1.8 Butterfly Network
			10.6.2 Implementation of Multistage Networks
			10.6.3 Comparison of Dynamic Networks
			10.6.4 Static Connection Networks (Message-Passing Approach)
				10.6.4.1 Hypercubes
				10.6.4.2 Mesh and Torus
				10.6.4.3 Systolic Arrays
				10.6.4.4 Ring
				10.6.4.5 Tree and Star
				10.6.4.6 Fat Tree
				10.6.4.7 Transputer
			10.6.5 Comparison of Static Networks
			10.6.6 Hybrid (Mixed Topology) Networks
			10.6.7 Important Characteristics of a Network
		10.7 Multiprocessor Architectures
			10.7.1 Shared-Memory Multiprocessor
			10.7.2 Symmetric Multiprocessors (SMP): UMA Model
			10.7.3 Distributed Shared Memory Multiprocessors (DSM): NUMA Model
			10.7.4 Cache-Coherent NUMA: CC-NUMA Model
			10.7.5 No Remote Memory Access (NORMA)
			10.7.6 General-Purpose Multiprocessors
				10.7.6.1 Implementation: A Mainframe SMP (IBM z990 Series)
			10.7.7 Operating System Considerations
		10.8 Multicomputer Architectures
			10.8.1 Design Considerations
			10.8.2 Multicomputer Generations
			10.8.3 Different Models of Multicomputer Systems
				10.8.3.1 Multitiered Architecture: Three–tier Client–Server Architecture
			10.8.4 Computer Networks
			10.8.5 Distributed Systems
		10.9 Clusters: A Distributed Computer System Design
			10.9.1 Distinct Advantage
			10.9.2 Classification of Clusters
			10.9.3 Different Clustering Methods
			10.9.4 General Architectures
			10.9.5 Operating System Considerations
			10.9.6 Windows Cluster
			10.9.7 Sun Cluster
			10.9.8 Blade Servers
		10.10 SIMD Machines
			10.10.1 SIMD Computer Organisations
			10.10.2 Vector Processors and SIMD Vector Computers
			10.10.3 Vector Stride
			10.10.4 Vector Fitting
			10.10.5 Vector Instruction Format
			10.10.6 Vector Instruction: Different Types
			10.10.7 Vector Processing
			10.10.8 Vectorization Inhibitor
			10.10.9 Vectorizing Compilers
			10.10.10 Different Types of Vector Processor Organisations
			10.10.11 Salient Features of Vector Operations
			10.10.12 Basic Vector Processor Architecture
			10.10.13 Memory-Access Schemes
			10.10.14 Implementation: The CRAY 1 Architecture
		10.11 Array Processors and SIMD Parallel Computers
			10.11.1 Applications
			10.11.2 Implementation: Connection Machine CM 2 Architecture
			10.11.3 Vector Processor Versus Array Processor: A Rough Comparison
		10.12 Massively Parallel Processing (MPP) System
			10.12.1 Representative MPP System: Connection Machine CM-5
		10.13 Scalable Parallel Computer Architecture
		10.14 Supercomputers
			10.14.1 The Contemporary Fastest Supercomputer System
		10.15 Summary
		Exercises
		Suggested References and Websites
Additional Reading
Suggested Websites
Index