Preface
Why Should You Read This Book?
Who Should Read the Book?
How Is This Book Different from Earlier Editions?
Acknowledgments
Contents
About the Author
Frequently Used Mathematical Symbols
1 Introduction
1.1 History of Terms
1.2 Opportunities
1.3 Challenges
1.4 Common Characteristics
1.5 Curriculum Integration of Embedded Systems, CPS, and IoT
1.5.1 Prerequisites
1.5.2 Recommended Additional Courses
1.6 Design Flows
1.7 Structure of This Book
1.8 Problems
2 Specifications and Modeling
2.1 Requirements
2.2 Models of Computation
2.3 Early Design Phases
2.3.1 Use Cases
2.3.2 (Message) Sequence Charts and Time/Distance Diagrams
2.3.3 Differential Equations
2.4 Communicating Finite State Machines (CFSMs)
2.4.1 Timed Automata
2.4.2 StateCharts
Modeling of Hierarchy
Timers
Edge Labels and StateMate Semantics
Evaluation and Extensions
2.4.3 Synchronous Languages
Motivation
Examples of Synchronous Languages: Esterel, Lustre, and SCADE
2.4.4 Message Passing: SDL as an Example
Features of the Language
Evaluation of SDL
2.5 Data Flow
2.5.1 Scope
2.5.2 Kahn Process Networks
2.5.3 SDF
2.5.4 Simulink
2.6 Petri Nets
2.6.1 Introduction
2.6.2 Condition/Event Nets
2.6.3 Place/Transition Nets
2.6.4 Predicate/Transition Nets
2.6.5 Evaluation
2.7 Discrete Event-Based Languages
2.7.1 Basic Discrete Event Simulation Cycle
2.7.2 Multi-Valued Logic
One Signal Strength (Two Logic Values)
Two Signal Strengths (Three and Four Logic Values)
Three Signal Strengths (Seven Signal Values)
Four Signal Strengths (Ten Signal Values)
Five Signal Strengths
2.7.3 Transaction-Level Modeling (TLM)
2.7.4 SpecC
2.7.5 SystemC
2.7.6 VHDL
Introduction
Entities and Architectures
Assignments
VHDL Processes
The VHDL Simulation Cycle
IEEE 1164
2.7.7 Verilog and SystemVerilog
2.8 von Neumann Languages
2.8.1 CSP
2.8.2 Ada
2.8.3 Communication Libraries
MPI
OpenMP
2.8.4 Additional Languages
2.9 Levels of Hardware Modeling
2.10 Comparison of Models of Computation
2.10.1 Criteria
2.10.2 Unified Modeling Language (UML)
2.10.3 Ptolemy II
2.11 Problems
3 Embedded System Hardware
3.1 Introduction
3.2 Input: Interface Between Physical and Cyber-World
3.2.1 Sensors
3.2.2 Discretization of Time: Sample-and-Hold Circuits
3.2.3 Fourier Approximation of Signals
3.2.4 Discretization of Values: Analog-to-Digital Converters
Flash ADC
Successive Approximation
Pipelined Converters
Other Converters
Comparison of ADCs
Quantization Noise
3.3 Processing Units
3.3.1 Application-Specific Integrated Circuits (ASICs)
3.3.2 Processors
Energy Efficiency
Code Size Efficiency
Execution Time Efficiency Using Digital Signal Processing as an Example
Multimedia and Short Vector Instruction Sets
Very Long Instruction Word (VLIW) Processors
VLIW Pipelines
Multi-core Processors
Graphics Processing Units (GPUs)
Multiprocessor Systems on a Chip (MPSoCs)
3.3.3 Reconfigurable Logic
3.4 Memories
3.4.1 Conflicting Goals
3.4.2 Memory Hierarchies
3.4.3 Register Files
3.4.4 Caches
3.4.5 Scratchpad Memories
3.5 Communication
3.5.1 Requirements
3.5.2 Electrical Robustness
3.5.3 Guaranteeing Real-Time Behavior
3.5.4 Examples
3.6 Output: Interface Between Cyber and Physical World
3.6.1 Digital-to-Analog Converters
3.6.2 Sampling Theorem
3.6.3 Pulse-Width Modulation
3.6.4 Actuators
3.7 Electrical Energy
3.7.1 Energy Sources
3.7.2 Energy Storage
3.7.3 Energy Efficiency of Hardware Components
The Case of Mobile Phones
Sensor Networks
3.8 Secure Hardware
3.9 Problems
4 System Software
4.1 Embedded Operating Systems
4.1.1 General Requirements
4.1.2 Real-Time Operating Systems
4.1.3 Virtual Machines
4.2 Resource Access Protocols
4.2.1 Priority Inversion
4.2.2 Priority Inheritance
4.2.3 Priority Ceiling Protocol
4.2.4 Stack Resource Policy
4.3 ERIKA
4.4 Embedded Linux
4.4.1 Embedded Linux Structure and Size
4.4.2 Real-Time Properties
4.4.3 Flash Memory File Systems
4.4.4 Reducing RAM Usage
4.4.5 uClinux: Linux for MMU-Less Systems
4.4.6 Evaluating the Use of Linux in Embedded Systems
4.5 Hardware Abstraction Layer
4.6 Middleware
4.6.1 OSEK/VDX COM
4.6.2 CORBA
4.6.3 POSIX Threads (Pthreads)
4.6.4 UPnP and DPWS
4.7 Real-Time Databases
4.8 Problems
5 Evaluation and Validation
5.1 Introduction
5.1.1 Scope
5.1.2 Multi-Objective Optimization
5.1.3 Relevant Objectives
5.2 Performance Evaluation
5.2.1 Early Phases
5.2.2 WCET Estimation
5.2.3 Real-Time Calculus
5.3 Quality Metrics
5.3.1 Approximate Computing
5.3.2 Simple Criteria of Quality
5.3.3 Criteria for Data Analysis
5.4 Energy and Power Models
5.4.1 General Properties
5.4.2 Energy Model for Memories
5.4.3 Energy Model for Instructions
5.4.4 Energy Model for Functional Processor Units
5.4.5 Energy Model for Processor and Memory
5.4.6 Energy Model for an Application
5.4.7 Energy Model for Multiple Applications with Hardware Multithreading
5.4.8 Energy Model for an Android Mobile Phone
5.4.9 Worst Case Energy Consumption
5.5 Thermal Models
5.5.1 Steady-State Behavior
5.5.2 Transient State Behavior
5.6 Dependability and Risk Analysis
5.6.1 Aspects of Dependability
5.6.2 Security Analysis
5.6.3 Safety Analysis
5.6.4 Reliability Analysis
5.6.5 Fault Tree Analysis, Failure Mode, and Effect Analysis
5.7 Simulation
5.8 Rapid Prototyping and Emulation
5.9 Formal Verification
5.10 Problems
6 Application Mapping
6.1 Definition of Scheduling Problems
6.1.1 Elaboration on the Design Problem
6.1.2 Types of Scheduling Problems
The ฮฑ Field
The ฮฒ Field
The ฮณ Field
6.2 Scheduling for Uniprocessors
6.2.1 Scheduling for Independent Jobs
Earliest Due Date (EDD) Algorithm
Earliest Deadline First (EDF) Algorithm
Least Laxity (LL) Algorithm
Scheduling Without Preemption
6.2.2 Scheduling with Precedence Constraints
Task Graphs
Latest Deadline First (LDF) Algorithm
6.2.3 Periodic Scheduling Without Precedence Constraints
Notation
Rate Monotonic Scheduling
Earliest Deadline First Scheduling
Explicit-Deadline Tasks
Deadline Monotonic Scheduling
6.2.4 Periodic Scheduling with Precedence Constraints
6.2.5 Sporadic Events
6.3 Scheduling for Independent Jobs on Identical Multiprocessors
6.3.1 Partitioned Scheduling
6.3.2 Global Dynamic-Priority Scheduling
Proportional Fair (Pfair) Scheduling
6.3.3 Global Fixed-Job-Priority Scheduling
G-EDF Scheduling
EDZL Scheduling
6.3.4 Global Fixed-Task-Priority Scheduling
Global Rate Monotonic Scheduling
RMZL Scheduling
Partitioned Scheduling for Explicit Deadlines
6.4 Dependent Jobs on Homogeneous Multiprocessors
6.4.1 As-Soon-as-Possible Scheduling
6.4.2 As-Late-as-Possible Scheduling
6.4.3 List Scheduling
6.4.4 Optimal Scheduling with Integer Linear Programming
6.5 Dependent Jobs on Heterogeneous Multiprocessors
6.5.1 Problem Description
6.5.2 Static Scheduling with Local Heuristics
6.5.3 Static Scheduling with Integer Linear Programming
6.5.4 Static Scheduling with Evolutionary Algorithms
6.5.5 Dynamic and Hybrid Scheduling
6.6 Problems
7 Optimization
7.1 High-Level Optimizations
7.1.1 Simple Loop Transformations
7.1.2 Loop Tiling/Blocking
7.1.3 Loop Splitting
7.1.4 Array Folding
7.1.5 Floating-Point to Fixed-Point Conversion
7.2 Task-Level Concurrency Management
7.3 Compilers for Embedded Systems
7.3.1 Introduction
7.3.2 Energy-Aware Compilation
7.3.3 Memory-Architecture Aware Compilation
Compilation Techniques for Scratchpads
Non-overlaying Allocation
Overlaying Allocation
Multiple Threads/Processes
Supporting Different Architectures and Objectives
7.3.4 Reconciling Compilers and Timing Analysis
7.4 Power and Thermal Management
7.4.1 Dynamic Voltage and Frequency Scaling (DVFS)
7.4.2 Dynamic Power Management (DPM)
7.4.3 Thermal Management
7.5 Problems
8 Test
8.1 Scope
8.2 Test Procedures
8.2.1 Test Pattern Generation for Gate-Level Models
8.2.2 Self-Test Programs
8.3 Evaluation of Test Pattern Sets and System Robustness
8.3.1 Fault Coverage
8.3.2 Fault Simulation
8.3.3 Fault Injection
8.4 Design for Testability
8.4.1 Motivation
8.4.2 Scan Design
8.4.3 Signature Analysis
8.4.4 Pseudo-random Test Pattern Generation
8.5 Problems
A Integer Linear Programming
B Kirchhoff's Laws and Operational Amplifiers
B.1 Kirchhoff's Laws
B.2 Operational Amplifiers
C Paging and Memory Management Units
References
Index