Computer Systems: An Embedded Approach

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