Computer Systems: An Embedded Approach

Preface
Acknowledgments
List of Boxes
1 Introduction
1.1 The Evolution of Computers
1.2 Forward Progress
1.3 Computer Generations
1.3.1 First Generation
1.3.2 Second Generation
1.3.3 Third Generation
1.3.4 Fourth Generation
1.3.5 Fifth Generation
1.4 Cloud, Pervasive, Grid, and Massively Parallel Computers
1.5 Where To from Here?
1.6 Summary
2 Foundations
2.1 Computer Organization
2.1.1 Flynn's Taxonomy
2.1.2 Connection Arrangements
2.1.3 Layered View of Computer Organization
2.2 Computer Fundamentals
2.3 Number Formats
2.3.1 Unsigned Binary
2.3.2 Sign Magnitude
2.3.3 One's Complement
2.3.4 Two's Complement
2.3.5 Excess-n
2.3.6 Binary-Coded Decimal
2.3.7 Fractional Notation
2.3.8 Sign Extension
2.4 Arithmetic
2.4.1 Addition
2.4.2 The Parallel Carry-Propagate Adder
2.4.3 Carry Look-Ahead
2.4.4 Subtraction
2.5 Multiplication
2.5.1 Repeated Addition
2.5.2 Partial Products
2.5.3 Shift-Add Method
2.5.4 Booth's and Robertson's Methods
2.6 Division
2.6.1 Repeated Subtraction
2.7 Working with Fractional Number Formats
2.7.1 Arithmetic with Fractional Numbers
2.7.2 Multiplication and Division of Fractional Numbers
2.8 Floating Point
2.8.1 Generalized Floating Point
2.8.2 IEEE754 Floating Point
2.8.3 IEEE754 Modes
2.8.4 IEEE754 Number Ranges
2.9 Floating Point Processing
2.9.1 Addition and Subtraction of IEEE754 Numbers
2.9.2 Multiplication and Division of IEEE754 Numbers
2.9.3 IEEE754 Intermediate Formats
2.9.4 Rounding
2.10 Summary
2.11 Problems
3 CPU Basics
3.1 What Is a Computer?
3.2 Making the Computer Work for You
3.2.1 Program Storage
3.2.2 Memory Hierarchy
3.2.3 Program Transfer
3.2.4 Control Unit
3.2.5 Microcode
3.2.6 RISC versus CISC Approaches
3.2.7 Example Processor-the ARM
3.2.8 More about the ARM
3.3 Instruction Handling
3.3.1 The Instruction Set
3.3.2 Instruction Fetch and Decode
3.3.3 Compressed Instruction Sets
3.3.4 Addressing Modes
3.3.5 Stack Machines and Reverse Polish Notation
3.4 Data Handling
3.4.1 Data Formats and Representations
3.4.2 Data Flows
3.4.3 Data Storage
3.4.4 Internal Data
3.4.5 Data Processing
3.5 A Top-Down View
3.5.1 Computer Capabilities
3.5.2 Performance Measures, Statistics, and Lies
3.5.3 Assessing Performance
3.6 Summary
3.7 Problems
4 Processor Internals
4.1 Internal Bus Architecture
4.1.1 A Programmer's Perspective
4.1.2 Split Interconnection Arrangements
4.1.3 ADSP21xx Bus Arrangement
4.1.4 Simultaneous Data and Program Memory Access
4.1.5 Dual-Bus Architectures
4.1.6 Single-Bus Architectures
4.2 Arithmetic Logic Unit
4.2.1 ALU Functionality
4.2.2 ALU Design
4.3 Memory Management Unit
4.3.1 The Need for Virtual Memory
4.3.2 MMU Operation
4.3.3 Retirement Algorithms
4.3.4 Internal Fragmentation and Segmentation
4.3.5 External Fragmentation
4.3.6 Advanced MMUs
4.3.7 Memory Protection
4.4 Cache
4.4.1 Direct Cache
4.4.2 Set-Associative Cache
4.4.3 Full-Associative Caches
4.4.4 Locality Principles
4.4.5 Cache Replacement Algorithms
4.4.6 Cache Performance
4.4.7 Cache Coherency
4.5 Coprocessors
4.6 Floating Point Unit
4.6.1 Floating Point Emulation
4.7 Streaming SIMD Extensions and Multimedia Extensions
4.7.1 Multimedia Extensions
4.7.2 MMX Implementation
4.7.3 Use of MMX
4.7.4 Streaming SIMD Extensions
4.7.5 Using SSE and MMX
4.8 Coprocessing in Embedded Systems
4.9 Summary
4.10 Problems
5 Enhancing CPU Performance
5.1 Speedups
5.2 Pipelining
5.2.1 Multifunction Pipelines
5.2.2 Dynamic Pipelines
5.2.3 Changing Mode in a Pipeline
5.2.4 Data Dependency Hazard
5.2.5 Conditional Hazards
5.2.6 Conditional Branches
5.2.7 Compile-Time Pipeline Remedies
5.2.8 Relative Branching
5.2.9 Instruction Set Pipeline Remedies
5.2.10 Run-Time Pipeline Remedies
5.3 Complex and Reduced Instruction Set Computers
5.4 Superscalar Architectures
5.4.1 Simple Superscalar
5.4.2 Multiple-Issue Superscalar
5.4.3 Superscalar Performance
5.5 Instructions per Cycle
5.5.1 IPC of Difference Architectures
5.5.2 Measuring IPC
5.6 Hardware Acceleration
5.6.1 Zero-Overhead Loops
5.6.2 Address Handling Hardware
5.6.3 Shadow Registers
5.7 Branch Prediction
5.7.1 The Need for Branch Prediction
5.7.2 Single T-Bit Predictor
5.7.3 Two-Bit Predictor
5.7.4 The Counter and Shift Registers as Predictors
5.7.5 Local Branch Predictor
5.7.6 Global Branch Predictor
5.7.7 The Gselect Predictor
5.7.8 The Gshare Predictor
5.7.9 Hybrid Predictors
5.7.10 Branch Target Buffer
5.7.11 Basic Blocks
5.7.12 Branch Prediction Summary
5.8 Parallel and Massively Parallel Machines
5.8.1 Evolution of SISD to MIMD
5.8.2 Parallelism for Raw Performance
5.8.3 More on Parallel Processing
5.9 Tomasulo's Algorithm
5.9.1 The Rationale behind Tomasulo's Algorithm
5.9.2 An Example Tomasulo System
5.9.3 Tomasulo in Embedded Systems
5.10 Very Long Instruction Word Architectures
5.10.1 What Is VLIW?
5.10.2 The VLIW Rationale
5.10.3 Difficulties with VLIW
5.10.4 Comparison with Superscalar
5.11 Summary
5.12 Problems
6 Externals
6.1 Interfacing Using a Bus
6.1.1 Bus Control Signals
6.1.2 Direct Memory Access
6.2 Parallel Bus Specifications
6.3 Standard Interfaces
6.3.1 System Control Interfaces
6.3.2 System Data Buses
6.3.3 I/O Buses
6.3.4 Peripheral Device Buses
6.3.5 Interface to Networking Devices
6.4 Real-Time Issues
6.4.1 External Stimuli
6.4.2 Interrupts
6.4.3 Real-Time Definitions
6.4.4 Temporal Scope
6.4.5 Hardware Architecture Support for Real Time
6.5 Interrupts and Interrupt Handling
6.5.1 The Importance of Interrupts
6.5.2 The Interrupt Process
6.5.3 Advanced Interrupt Handling
6.5.4 Sharing Interrupts
6.5.5 Reentrant Code
6.5.6 Software Interrupts
6.6 Embedded Wireless Connectivity
6.6.1 Wireless Technology
6.6.2 Wireless Interfacing
6.6.3 Issues Relating to Wireless
6.7 Summary
6.8 Problems
7 Practical Embedded CPUs
7.1 Introduction
7.2 Microprocessors Are Core Plus More
7.3 Required Functionality
7.4 Clocking
7.4.1 Clock Generation
7.5 Clocks and Power
7.5.1 Propagation Delay
7.5.2 The Trouble with Current
7.5.3 Solutions for Clock Issues
7.5.4 Low-Power Design
7.6 Memory
7.6.1 Early Computer Memory
7.6.2 ROM: Read-Only Memory
7.6.3 RAM: Random-Access Memory
7.7 Pages and Overlays
7.8 Memory in Embedded Systems
7.8.1 Booting from Non-Volatile Memory
7.8.2 Other Memory
7.9 Test and Verification
7.9.1 IC Design and Manufacture Problems
7.9.2 Built-In Self-Test
7.9.3 JTAG
7.10 Error Detection and Correction
7.11 Watchdog Timers and Reset Supervision
7.11.1 Reset Supervisors and Brownout Detectors
7.12 Reverse Engineering
7.12.1 The Reverse Engineering Process
7.12.2 Detailed Physical Layout
7.13 Preventing Reverse Engineering
7.13.1 Passive Obfuscation of Stored Programs
7.13.2 Programmable Logic Families
7.13.3 Active RE Mitigation
7.13.4 Active RE Mitigation Classification
7.14 Soft Core Processors
7.14.1 Microprocessors Are More Than Cores
7.14.2 The Advantages of Soft Core Processors
7.15 Hardware Software Codesign
7.16 Off-the-Shelf Cores
7.17 Summary
7.18 Problems
8 Programming
8.1 Running a Program
8.1.1 What Does Executing Mean?
8.1.2 Other Things to Note
8.2 Writing a Program
8.2.1 Compiled Languages
8.2.2 Interpreted Languages
8.3 The UNIX Programming Model
8.3.1 The Shell
8.3.2 Redirections and Data Flow
8.3.3 Utility Software
8.4 Summary
8.5 Problems
9 Operating Systems
9.1 What Is an Operating System?
9.2 Why Do We Need an Operating System?
9.2.1 Operating System Characteristics
9.2.2 Types of Operating Systems
9.3 The Role of an Operating System
9.3.1 Resource Management
9.3.2 Virtual Machine
9.3.3 CPU Time
9.3.4 Memory Management
9.3.5 Storage and Filing
9.3.6 Protection and Error Handling
9.4 OS Structure
9.4.1 Layered Operating Systems
9.4.2 Client-Server Operating Systems
9.5 Booting
9.5.1 Booting from Parallel Flash
9.5.2 Booting from HDD/SSD
9.5.3 What Happens Next
9.6 Processes
9.6.1 Processes, Processors, and Concurrency
9.7 Scheduling
9.7.1 The Scheduler
9.8 Storage and File Systems
9.8.1 Secondary Storage
9.8.2 Need for File Systems
9.8.3 What Are File Systems?
9.8.4 Backup
9.9 Summary
9.10 Problems
10 Connectivity
10.1 Why Connect, How to Connect
10.1.1 One-to-One Communications
10.1.2 One-to-Many Communications
10.1.3 Packet Switching
10.1.4 Simple Communications Topologies
10.2 System Requirements
10.2.1 Packetization
10.2.2 Encoding and Decoding
1
0.2.3 Transmission
10.2.4 Receiving
10.2.5 Error Handling
10.2.6 Connection Management
10.3 Scalability, Efficiency, and Reuse
10.4 OSI Layers
10.5 Topology and Architecture
10.5.1 Hierarchical Network
10.5.2 Client-Server Architecture
10.5.3 Peer-to-Peer Architecture
10.5.4 Ad Hoc Connection
10.5.5 Mobility and Handoff
10.6 Summary
10.7 Problems
11 Networking
11.1 The Internet
11.1.1 Internet History
11.1.2 Internet Governance
11.2 TCP/IP and the IP Layer Model
11.2.1 Encapsulation
11.3 Ethernet Overview
11.3.1 Ethernet Data Format
11.3.2 Ethernet Encapsulation
11.3.3 Ethernet Carrier Sense
11.4 The Internet Layer
11.4.1 IP Address
11.4.2 Internet Packet Format
11.4.3 Routing
11.4.4 Unicasting and Multicasting
11.4.5 Anycasting
11.4.6 Naming
11.4.7 Domain Name Servers
11.5 The Transport Layer
11.5.1 Port Number
11.5.2 User Datagram Protocol
11.5.3 Transmission Control Protocol
11.5.4 UDP versus TCP
11.6 Other Messages
11.6.1 Address Resolution Protocol
11.6.2 Control Messages
11.7 Wireless Connectivity
11.7.1 WiFi
11.7.2 WiMax
11.7.3 Bluetooth
11.7.4 ZigBee
11.7.5 Near-Field Communications
11.8 Network Scales
11.9 Summary
11.10 Problems
12 The Future
12.1 Single-Bit Architectures
12.1.1 Bit-Serial Addition
12.1.2 Bit-Serial Subtraction
12.1.3 Bit-Serial Logic and Processing
12.2 More-Parallel Machines
12.2.1 Clusters of Small CPUs
12.2.2 Parallel and Cluster Processing Considerations
12.2.3 Interconnection Strategies
12.3 Asynchronous Processors
12.3.1 Data Flow Control
12.3.2 Avoiding Pipeline Hazards
12.4 Alternative Number Format Systems
12.4.1 Multiple-Valued Logic
12.4.2 Signed Digit Number Representation
12.5 Optical Computation
12.5.1 The Electro-Optical Full Adder
12.5.2 The Electro-Optic Backplane
12.6 Science Fiction or Future Reality?
12.6.1 Distributed Computing
12.6.2 Wetware
12.7 Summary
A Standard Memory Size Notation
B Standard Logic Gates
Index