Designing Embedded Systems with the SIGNAL Programming Language (eBook)
XXIII, 259 Seiten
Springer New York (Verlag)
978-1-4419-0941-1 (ISBN)
I am very pleased to play even a small part in the publication of this book on the SIGNAL language and its environment POLYCHRONY. I am sure it will be a s- ni?cant milestone in the development of the SIGNAL language, of synchronous computing in general, and of the data?ow approach to computation. In data?ow, the computation takes place in a producer-consumer network of - dependent processing stations. Data travels in streams and is transformed as these streams pass through the processing stations (often called ?lters). Data?ow is an attractive model for many reasons, not least because it corresponds to the way p- duction,transportation,andcommunicationare typicallyorganizedin the real world (outside cyberspace). I myself stumbled into data?ow almost against my will. In the mid-1970s, Ed Ashcroft and I set out to design a "e;super"e; structured programming language that, we hoped, would radically simplify proving assertions about programs. In the end, we decided that it had to be declarative. However, we also were determined that iterative algorithms could be expressed directly, without circumlocutions such as the use of a tail-recursive function. The language that resulted, which we named LUCID, was much less traditional then we would have liked. LUCID statements are equations in a kind of executable temporallogic thatspecifythe (time)sequencesof variablesinvolvedin aniteration.
Foreword 6
Preface 8
Contents 16
Part I Real-Time and Synchronous Programming 22
1 Generalities on Real-Time Programming 23
1.1 Embedded, Reactive, and Real-Time Systems 23
1.1.1 Definitions and Examples 24
1.1.1.1 Embedded Systems 24
1.1.1.2 Reactive Systems 26
1.1.1.3 Real-Time Systems 27
1.1.2 Some Important Design Issues 28
1.1.2.1 Hard Versus Soft Real Time 29
1.1.2.2 Safety Criticality 29
1.1.2.3 Determinism 30
1.1.2.4 Predictability 30
1.1.2.5 Distribution and Heterogeneity 30
1.1.2.6 Complexity and Modularity 31
1.2 Dealing with Time During System Execution 31
1.3 Real-Time Programming Models 32
1.3.1 Asynchronous Vision 33
1.3.2 Preestimated Time Vision 34
1.3.3 Synchronous Vision 35
1.3.4 Summary 36
1.4 Methodological Elements for System Design 37
References 40
2 Synchronous Programming: Overview 41
2.1 Objectives 41
2.2 Foundations 42
2.2.1 The Synchronous Hypothesis 42
2.2.1.1 What Does It Mean? 42
2.2.1.2 Illustration and Discussion 42
2.2.1.3 A Qualitative Way To Deal with Time 43
2.2.1.4 Methodological Implications 44
2.2.2 Monoclocked Versus Multiclocked System Models 44
2.2.3 Implementation Models 46
2.3 Imperative Languages 47
2.3.1 Esterel 47
2.3.1.1 Language Features 47
2.3.1.2 Compilation of Programs 49
2.3.1.3 Application Domains and Tools 50
2.3.2 Graphical Languages: Statecharts, Statecharts, and Argos 50
2.3.2.1 Statecharts 50
2.3.2.2 Basic Features 50
2.3.2.3 Semantics of Execution Models 51
2.3.2.4 Argos 52
2.3.2.5 SyncCharts 52
2.4 Declarative Languages 52
2.4.1 Functional Languages: Lustre and Lucid Synchrone 53
2.4.1.1 Lustre 53
2.4.1.2 Language Features 53
2.4.1.3 Compilation of Programs 55
2.4.1.4 Application Domains and Tools 55
2.4.1.5 Lucid Synchrone 55
2.4.2 The Relational Language SIGNAL 56
2.5 Other Languages 56
2.6 Summary 57
References 58
Part II Elementary Concepts and Notations of SIGNAL 60
3 Basics: Signals and Relations 61
3.1 Signals and Their Elementary Features 61
3.1.1 Definition of Signals 61
3.1.2 Data Types 62
3.1.2.1 Type Definition 62
3.1.2.2 Integer 62
3.1.2.3 Real 63
3.1.2.4 Complex 63
3.1.2.5 Boolean 64
3.1.2.6 Event 64
3.1.2.7 Character 64
3.1.2.8 String 64
3.1.2.9 Enumeration 64
3.1.2.10 Structure 65
3.1.2.11 Bundle 65
3.1.2.12 Arrays 65
3.1.2.13 Comparison and Conversion of Types 66
3.1.3 Identifier of a Signal 68
3.1.4 Declaration of Signals 68
3.1.5 Constant Signals 69
3.2 Abstract Clock of a Signal 69
3.2.1 The Notion of Polychrony 69
3.2.1.1 Need to Specify Absence 70
3.2.1.2 Role of Abstract Clocks in Design 71
3.2.2 Definition 72
3.2.3 The Event Type 72
3.3 Relation Between Signals 73
3.3.1 Equational Specification of Relations 73
3.3.2 Primitive Monoclock Relations 73
3.3.2.1 Instantaneous Relations/Functions 74
3.3.2.2 Delay (or Shift Register) 75
3.3.3 Primitive Multiclock Relations 77
3.3.3.1 Undersampling 77
3.3.3.2 Deterministic Merging 77
3.4 Exercises 78
References 79
4 Programming Units: Processes 80
4.1 Elementary Notions 80
4.1.1 Definition of Processes 80
4.1.2 A Specific Process: Function 81
4.1.3 Programs 81
4.2 Primitive Operations on Processes 81
4.2.1 Composition 82
4.2.2 Local Declaration 82
4.3 Notation 83
4.3.1 Process Frame 83
4.3.1.1 Comments in a Process 83
4.3.2 Example: A Resettable Counter 84
4.3.3 Hierarchy of Processes 86
4.3.4 Label of a Process 86
4.4 Exercises 87
References 88
5 Extended Constructs 89
5.1 Pure Control Specification 89
5.1.1 Extraction of Abstract Clocks 90
5.1.1.1 Boolean Signal Value 90
5.1.1.2 Signal Presence 90
5.1.2 Synchronization of Abstract Clocks 90
5.1.3 Set Operations on Abstract Clocks 91
5.1.4 Comparison of Abstract Clocks 93
5.2 Memorization 93
5.3 Sliding Window 94
5.4 Array of Processes 95
5.5 Exercises 95
Reference 97
6 Design in Polychrony: First Steps 98
6.1 The Polychrony Design Environment 98
6.1.1 What Is It Useful for? 98
6.1.2 What Tools Does It Provide? 99
6.2 Design of a Watchdog 99
6.2.1 Definition of a Signal Specification 100
6.2.2 Compilation and Code Generation 101
6.2.3 Behavioral Simulation 103
6.3 Exercises 106
Reference 107
Part III Formal Properties of SIGNAL Programs 108
7 Formal Semantics 109
7.1 An Operational Semantics 109
7.1.1 Preliminary Definitions 110
7.1.2 Primitive Constructs on Signals 112
7.1.2.1 Instantaneous Relations/Functions 112
7.1.2.2 Delay 112
7.1.2.3 Undersampling 113
7.1.2.4 Deterministic Merging 113
7.1.3 Primitive Constructs on Processes 114
7.1.3.1 Composition 114
7.1.3.2 Local Definition 114
7.2 A Denotational Semantics 116
7.2.1 A Multiclocked Semantic Model 116
7.2.2 Primitive Constructs on Signals 119
7.2.2.1 Instantaneous Relations/Functions 119
7.2.2.2 Delay 119
7.2.2.3 Undersampling 120
7.2.2.4 Deterministic Merging 120
7.2.3 Primitive Constructs on Processes 121
7.2.3.1 Composition 121
7.2.3.2 Local Definition 121
7.3 Exercises 121
References 122
8 Formal Model for Program Analysis 123
8.1 The Synchronization Space: F3 123
8.1.1 Encoding Abstract Clocks and Values 124
8.1.2 Encoding Primitive Constructs 124
8.1.2.1 Instantaneous Relations/Functions 125
8.1.2.2 Delay 125
8.1.2.3 Undersampling 125
8.1.2.4 Deterministic Merging 126
8.1.2.5 Composition 126
8.1.2.6 Local Definition 126
8.1.3 Encoding Some Extended Constructs 126
8.1.4 General Form of an Encoded Program 128
8.2 Conditional Dependency Graph 129
8.2.1 Dependencies in Primitive Constructs 130
8.2.1.1 Instantaneous Relations/Functions 130
8.2.1.2 Delay 130
8.2.1.3 Undersampling 130
8.2.1.4 Deterministic Merging 130
8.2.1.5 Composition 131
8.2.1.6 Local Definition 131
8.2.2 Example: Checking Dependency Cycles 131
8.3 Exercises 132
References 133
9 Compilation of Programs 134
9.1 Overview 135
9.2 Abstract Clock Calculus: Analysis of Programs 136
9.2.1 Typical Program Analysis Issues 136
9.2.1.1 Does a Program Exhibit Contradictions? 137
9.2.1.2 Is a Program Setting Constraints on Its Inputs? 137
9.2.1.3 Are There Clocked Cyclic Definitions in a Program? 139
9.2.1.4 Is a Program Temporally Deterministic? 141
9.2.1.5 Does a Program Satisfy Some Property? 142
9.2.2 Hierarchy Synthesis for Abstract Clocks 143
9.3 Exploiting Hierarchies of Abstract Clocks in Practice 145
9.3.1 Endochronous Programs 145
9.3.1.1 Clock Hierarchy 146
9.3.1.2 Hierarchized Conditional Dependency Graph 146
9.3.2 Exochronous Programs 148
9.3.2.1 Clock Hierarchy 148
9.3.2.2 Hierarchized Conditional Dependency Graph 149
9.3.3 Endochronization of Exochronous Programs 149
9.3.3.1 A First Example 149
9.3.3.2 Another Example: Resettable Counter 151
9.4 Code Generation 154
9.4.1 An Example of a Generated Code Sketch 155
9.5 Exercises 156
References 157
Part IV Advanced Design in SIGNAL 159
10 Advanced Design Concepts 160
10.1 Modularity 160
10.2 Abstraction 161
10.2.1 External Processes 161
10.2.2 Black Box Model 163
10.2.3 Gray Box Model 164
10.3 Oversampling 166
10.4 Assertion 167
10.4.1 Assertion on Boolean Signals 167
10.4.2 Assertion on Clock Constraints 168
10.5 Exercises 169
References 169
11 GALS System Design 170
11.1 Motivation in Some Application Domains 170
11.2 Theoretical Foundations 171
11.2.1 Endochrony 172
11.2.2 Endo-isochrony 175
11.3 A Distribution Methodology 178
11.4 Exercises 180
References 181
12 Design Patterns 182
12.1 Refinement-Based Design (Top-Down) 182
12.1.1 A Blackboard Mechanism 183
12.1.2 SIGNAL Modeling of read_blackboard 184
12.1.2.1 Initial Model Specification 184
12.1.2.2 Refined Model Specification 185
12.2 Incremental Design (Bottom-Up) 187
12.2.1 A FIFO Message Queue 188
12.2.2 SIGNAL Modeling of the FIFO Queue 188
12.2.2.1 Initial Model Design 188
12.2.2.2 Enhanced Model Design 190
12.3 Control-Related Aspects 191
12.3.1 Finite State Machines 191
12.3.1.1 Informal Description of an FSM 191
12.3.1.2 SIGNAL Model of the FSM 192
12.3.2 Preemption 193
12.4 Oversampling 194
12.4.1 Euclid's Algorithm for Greatest Common Divisor Computation 194
12.4.2 SIGNAL Modeling of the Algorithm 195
12.5 Endo-isochrony 196
12.5.1 A Flight Warning System 196
12.5.2 SIGNAL Modeling of the FWS 196
12.5.2.1 Alarm Manager and Notifier Processes 196
12.5.2.2 The Global System 198
12.6 Exercises 200
References 201
13 A Synchronization Example Design with Polychrony 202
13.1 The Dining Philosophers Problem 202
13.1.1 Informal Presentation 202
13.1.2 A Solution 203
13.2 Design of the Solution Within Polychrony 203
13.2.1 Modeling of Philosophers 204
13.2.1.1 Signal Description 204
13.2.1.2 Analysis with the Compiler 206
13.2.1.3 Code Generation 208
13.2.1.4 Simulation 212
13.2.2 Modeling of Forks 214
13.2.2.1 Signal Specification 214
13.2.2.2 Analysis, Code Generation, and Simulation 215
13.2.3 Coordination Between Philosophers and Forks 216
13.3 Exercises 220
References 220
A Main Commands of the Compiler 221
A.1 Compilation Commands 221
A.1.1 General Synopsis 221
A.1.2 Commonly Used Compiler Options 222
A.1.3 Examples of Command Usage 223
A.2 Automatic Makefile Generation 225
A.2.1 Synopsis 226
A.2.2 Examples of Command Usage 226
B The Grammar of SIGNAL 227
Glossary 241
Solutions to Exercises 244
Index 265
| Erscheint lt. Verlag | 6.10.2009 |
|---|---|
| Zusatzinfo | XXIII, 259 p. |
| Verlagsort | New York |
| Sprache | englisch |
| Themenwelt | Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge |
| Informatik ► Weitere Themen ► CAD-Programme | |
| Informatik ► Weitere Themen ► Hardware | |
| Technik ► Elektrotechnik / Energietechnik | |
| Schlagworte | Correct by Construction • Embedded System Design • GALS • Hardware/Software Co-Design • Programming language • Reliable software • Safety critical embedded software • Signal • Synchronous Programming • synchronous programming language |
| ISBN-10 | 1-4419-0941-9 / 1441909419 |
| ISBN-13 | 978-1-4419-0941-1 / 9781441909411 |
| Haben Sie eine Frage zum Produkt? |
PDF (Wasserzeichen)Größe: 3,9 MB
DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasserzeichen und ist damit für Sie personalisiert. Bei einer missbräuchlichen Weitergabe des eBooks an Dritte ist eine Rückverfolgung an die Quelle möglich.
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
