Computer Systems: An Embedded Approach

Ian McLoughlin is an Associate Professor in the School of Computer Engineering, Nanyang Technological University, Singapore. He received his BEng and PhD degrees from the University of Birmingham in 1991 and 1997 respectively. His background includes work for industry, government and academia across three continents over the past 20 years. He is an engineer, having designed or worked on systems that can be found in space, flying in the troposphere, empowering the global telecommunications network, underwater, in daily use by emergency services and embedded within consumer devices. He has conducted technical training courses for the electronic industry and consulted on development projects related to embedded systems, particularly related to audio and wireless technology. For his work on rural telecommunications solutions, he won the inaugural IEE Innovation in Engineering Award in 2005 with his team from Tait Electronics Ltd, Christchurch, NewZealand. He is a member of IET, senior member of IEEE, a Chartered Engineer in the UK and an Ingenieur Europeen (Eur. Ing.)       Associate Professor McLoughlin has published more than 100 papers and book chapters, and a book to date – "Applied Speech and Audio Processing" with Cambridge University Press.

• 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 10.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