Embedded System Design (eBook)

Contents 7
Preface 13
Acknowledgments 17
1 INTRODUCTION 18
1.1 Terms and scope 18
1.2 Application areas 22
1.3 Growing importance of embedded systems 25
1.4 Structure of this book 26
2 SPECIFICATIONS 30
2.1 Requirements 30
2.2 Models of computation 33
2.3 StateCharts 35
2.3.1 Modeling of hierarchy 36
2.3.2 Timers 40
2.3.3 Edge labels and StateCharts semantics 41
2.3.4 Evaluation and extensions 43
2.4 General language characteristics 44
2.4.1 Synchronous and asynchronous languages 44
2.4.2 Process concepts 45
2.4.3 Synchronization and communication 45
2.4.4 Specifying timing 46
2.4.5 Using non-standard I/O devices 47
2.5 SDL 47
2.6 Petri nets 53
2.6.1 Introduction 53
2.6.2 Condition/event nets 57
2.6.3 Place/transition nets 57
2.6.4 Predicate/transition nets 59
2.6.5 Evaluation 61
2.7 Message Sequence Charts 61
2.8 UML 62
2.9 Process networks 67
2.9.1 Task graphs 67
2.9.2 Asynchronous message passing 70
2.9.3 Synchronous message passing 72
2.10 Java 75
2.11 VHDL 76
2.11.1 Introduction 76
2.11.2 Entities and architectures 77
2.11.3 Multi-valued logic and IEEE 1164 79
2.11.4 VHDL processes and simulation semantics 86
2.12 SystemC 90
2.13 Verilog and SystemVerilog 92
2.14 SpecC 93
2.15 Additional languages 94
2.16 Levels of hardware modeling 96
2.17 Language comparison 99
2.18 Dependability requirements 100
3 EMBEDDED SYSTEM HARDWARE 104
3.1 Introduction 104
3.2 Input 105
3.2.1 Sensors 105
3.2.2 Sample-and-hold circuits 107
3.2.3 A/D-converters 108
3.3 Communication 110
3.3.1 Requirements 111
3.3.2 Electrical robustness 112
3.3.3 Guaranteeing real-time behavior 113
3.3.4 Examples 114
3.4 Processing Units 115
3.4.1 Overview 115
3.4.2 Application-Speci.c Circuits (ASICs) 117
3.4.3 Processors 117
3.4.4 Reconfigurable Logic 132
3.5 Memories 135
3.6 Output 137
3.6.1 D/A-converters 138
3.6.2 Actuators 139
4 STANDARD SOFTWARE: EMBEDDED OPERATING SYSTEMS, MIDDLEWARE, AND SCHEDULING 142
4.1 Prediction of execution times 143
4.2 Scheduling in real-time systems 144
4.2.1 Classification of scheduling algorithms 145
4.2.2 Aperiodic scheduling 148
4.2.3 Periodic scheduling 152
4.2.4 Resource access protocols 157
4.3 Embedded operating systems 160
4.3.1 General requirements 160
4.3.2 Real-time operating systems 161
4.4 Middleware 165
4.4.1 Real-time data bases 165
4.4.2 Access to remote objects 166
5 IMPLEMENTING EMBEDDED SYSTEMS: HARDWARE/SOFTWARE CODESIGN 168
5.1 Task level concurrency management 170
5.2 High-level optimizations 174
5.2.1 Floating-point to fixed-point conversion 174
5.2.2 Simple loop transformations 176
5.2.3 Loop tiling/blocking 177
5.2.4 Loop splitting 180
5.2.5 Array folding 182
5.3 Hardware/software partitioning 184
5.3.1 Introduction 184
5.3.2 COOL 185
5.4 Compilers for embedded systems 194
5.4.1 Introduction 194
5.4.2 Energy-aware compilation 195
5.4.3 Compilation for digital signal processors 198
5.4.4 Compilation for multimedia processors 201
5.4.5 Compilation for VLIW processors 201
5.4.6 Compilation for network processors 202
5.4.7 Compiler generation, retargetable compilers and design space exploration 202
5.5 Voltage Scaling and Power Management 203
5.5.1 Dynamic Voltage Scaling 203
5.5.2 Dynamic power management (DPM) 206
5.6 Actual design flows and tools 207
5.6.1 SpecC methodology 207
5.6.2 IMEC tool flow 208
5.6.3 The COSYMA design flow 211
5.6.4 Ptolemy II 212
5.6.5 The OCTOPUS design flow 213
6 VALIDATION 216
6.1 Introduction 216
6.2 Simulation 217
6.3 Rapid Prototyping and Emulation 218
6.4 Test 218
6.4.1 Scope 218
6.4.2 Design for testability 219
6.4.3 Self-test programs 222
6.5 Fault simulation 223
6.6 Fault injection 224
6.7 Risk- and dependability analysis 224
6.8 Formal Veri.cation 226
References 229
About the Author 244
List of Figures 246
Index 254
More eBooks at www.ciando.com 0

Chapter 2

SPECIFICATIONS (p. 13-14)

2.1 Requirements

Consistent with the simplified design flow (see fig. 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 specification 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 features1: 

* 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 efficient, no obstacles prohibiting the generation of efficient 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 verification 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 fig. 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.