Embedded System Design (eBook)

Dr. Peter Marwedel received his PhD in Physics from the University of Kiel in 1974. He is one of the early researchers in high level synthesis, working on the MIMOLA system for a number of years. Dr. Marwedel is a professor at the University of Dortmund since 1989. He has served as the chairman of the computer science department, has played a leading role in establishing the Design, Automation and Test in Europe (DATE) conference and is the chairman of the Informatik Centrum Dortmund (ICD), a technology transfer centre.

Contents 6
Preface 11
Importance of embedded systems 11
Audience for this book 12
Curriculum integration of embedded systems 12
Acknowledgments 15
Chapter 1 INTRODUCTION 16
1.1 Terms and scope 16
1.2 Application areas 20
1.3 Growing importance of embedded systems 23
1.4 Structure of this book 24
Chapter 2 SPECIFICATIONS 27
2.1 Requirements 27
2.2 Models of computation 30
2.3 StateCharts 32
2.3.1 Modeling of hierarchy 33
2.3.2 Timers 37
2.3.3 Edge labels and StateCharts semantics 38
2.3.4 Evaluation and extensions 40
2.4 General language characteristics 41
2.4.1 Synchronous and asynchronous languages 41
2.4.2 Process concepts 42
2.4.3 Synchronization and communication 42
2.4.4 Specifying timing 43
2.4.5 Using non-standard I/O devices 44
2.5 SDL 44
2.6 Petri nets 50
2.6.1 Introduction 50
2.6.2 Condition/event nets 54
2.6.3 Place/transition nets 54
2.6.4 Predicate/transition nets 56
2.6.5 Evaluation 58
2.7 Message Sequence Charts 58
2.8 UML 59
2.9 Process networks 64
2.9.1 Task graphs 64
2.9.2 Asynchronous message passing 67
2.9.3 Synchronous message passing 69
2.10 Java 72
2.11 VHDL 73
2.11.1 Introduction 73
2.11.2 Entities and architectures 74
2.11.3 Multi-valued logic and IEEE 1164 76
2.11.4 VHDL processes and simulation semantics 83
2.12 SystemC 87
2.13 Verilog and SystemVerilog 89
2.14 SpecC 90
2.15 Additional languages 91
2.16 Levels of hardware modeling 93
2.17 Language comparison 96
2.18 Dependability requirements 97
Chapter 3 EMBEDDED SYSTEM HARDWARE 100
3.1 Introduction 100
3.2 Input 101
3.2.1 Sensors 101
3.2.2 Sample-and-hold circuits 103
3.2.3 A/D-converters 104
3.3 Communication 106
3.3.1 Requirements 107
3.3.2 Electrical robustness 108
3.3.3 Guaranteeing real-time behavior 109
3.3.4 Examples 110
3.4 Processing Units 111
3.4.1 Overview 111
3.4.2 Application-Speci.c Circuits (ASICs) 113
3.4.3 Processors 113
3.4.4 Recon.gurable Logic 128
3.5 Memories 131
3.6 Output 133
3.6.1 D/A-converters 134
3.6.2 Actuators 135
Chapter 4 STANDARD SOFTWARE: EMBEDDED OPERATING SYSTEMS, MIDDLEWARE, AND SCHEDULING 137
4.1 Prediction of execution times 138
4.2 Scheduling in real-time systems 139
4.2.1 Classi.cation of scheduling algorithms 140
4.2.2 Aperiodic scheduling 143
4.2.3 Periodic scheduling 147
4.2.4 Resource access protocols 152
4.3 Embedded operating systems 155
4.3.1 General requirements 155
4.3.2 Real-time operating systems 156
4.4 Middleware 160
4.4.1 Real-time data bases 160
4.4.2 Access to remote objects 161
Chapter 5 IMPLEMENTING EMBEDDED SYSTEMS: HARDWARE/SOFTWARE CODESIGN 163
5.1 Task level concurrency management 165
5.2 High-level optimizations 169
5.2.1 Floating-point to .xed-point conversion 169
5.2.2 Simple loop transformations 171
5.2.3 Loop tiling/blocking 172
5.2.4 Loop splitting 175
5.2.5 Array folding 177
5.3 Hardware/software partitioning 179
5.3.1 Introduction 179
5.3.2 COOL 180
5.4 Compilers for embedded systems 189
5.4.1 Introduction 189
5.4.2 Energy-aware compilation 190
5.4.3 Compilation for digital signal processors 193
5.4.4 Compilation for multimedia processors 196
5.4.5 Compilation for VLIW processors 196
5.4.6 Compilation for network processors 197
5.4.7 Compiler generation, retargetable compilers and design space exploration 197
5.5 Voltage Scaling and Power Management 198
5.5.1 Dynamic Voltage Scaling 198
5.5.2 Dynamic power management (DPM) 201
5.6 Actual design .ows and tools 202
5.6.1 SpecC methodology 202
5.6.2 IMEC tool .ow 203
5.6.3 The COSYMA design .ow 206
5.6.4 Ptolemy II 207
5.6.5 The OCTOPUS design .ow 208
Chapter 6 VALIDATION 210
6.1 Introduction 210
6.2 Simulation 211
6.3 Rapid Prototyping and Emulation 212
6.4 Test 212
6.4.1 Scope 212
6.4.2 Design for testability 213
6.4.3 Self-test programs 216
6.5 Fault simulation 217
6.6 Fault injection 218
6.7 Risk- and dependability analysis 218
6.8 Formal Veri.cation 220
References 223
List of Figures 239
Index 246

Chapter 2
SPECIFICATIONS (p. 13-14)

2.1 Requirements
Consistent with the simplified design flow (see .g. 1.5), we will now describe requirements and approaches for specifying embedded systems. There may still be cases in which the specification of embedded systems is captured in a natural language, such as English. However, this approach is absolutely inappropriate since it lacks key requirements for specification techniques: it is necessary to check specifications for completeness, absence of contradictions and it should be possible to derive implementations from the speci.cation in a systematic way. Therefore, specifications should be captured in machine readable, formal languages. Specification languages for embedded systems should be capable of representing the following features: Hierarchy: Human beings are generally not capable of comprehending systems that contain many objects (states, components) having complex relations with each other. The description of all real-life systems needs more objects than human beings can understand. Hierarchy is the only mechanism that helps to solve this dilemma. Hierarchies can be introduced such that humans need to handle only a small number of objects at any time.

There are two kinds of hierarchies:

– Behavioral hierarchies: Behavioral hierarchies are hierarchies containing objects necessary to describe the system behavior. States, events and output signals are examples of such objects.

– Structural hierarchies: Structural hierarchies describe how systems are composed of physical components.

For example, embedded systems can be comprised of processors, memories, actors and sensors. Processors, in turn, include registers, multiplexers and adders. Multiplexers are composed of gates.

Timing-behavior: Since explicit timing requirements are one of the characteristics of embedded systems, timing requirements must be captured in the specification.

State-oriented behavior: It was already mentioned in chapter 1 that automata provide a good mechanism for modeling reactive systems. Therefore, the state-oriented behavior provided by automata should be easy to describe. However, classical automata models are insufficient, since they cannot model timing and since hierarchy is not supported.

Event-handling: Due to the reactive nature of embedded systems, mechanisms for describing events must exist. Such events may be external events (caused by the environment) or internal events (caused by components of the system).

No obstacles to the generation of efficient implementations: Since embedded systems have to be ef.cient, no obstacles prohibiting the generation of ef.cient realizations should be present in the specification.

Support for the design of dependable systems: Specification techniques should provide support for designing dependable systems. For example, specification languages should have unambiguous semantics, facilitate formal veri.cation and be capable of describing security and safety requirements.

Exception-oriented behavior: In many practical, systems exceptions do occur. In order to design dependable systems, it must be possible to describe actions to handle exceptions easily. It is not acceptable that exceptions have to be indicated for each and every state (like in the case of classical state diagrams). Example: In .g. 2.1, input k might correspond to an exception.

Specifying this exception at each state makes the diagram very complex. The situation would get worse for larger state diagrams with many transitions. We will later show, how all the transitions can be replaced by a single one.