Analysis and optimisation of real-time systems with stochastic behaviour

I Preliminaries......Page 13
1.1 Embedded System Design Flow......Page 15
1.2 Contribution......Page 19
1.3 Thesis Organisation......Page 20
II Stochastic Schedulability Analysis and Optimisation......Page 21
2.1 Motivation......Page 23
2.2 Related Work......Page 26
3.1 Hardware Model......Page 31
3.2.1 Functionality......Page 32
3.2.2 Periodic Task Model......Page 34
3.2.4 Execution Times......Page 35
3.2.5 Real-Time Requirements......Page 36
3.2.6 Late Task Policy......Page 37
3.3 Illustrative Example......Page 39
4.1.1 Input......Page 43
4.2 Analysis Algorithm......Page 44
4.2.1 The Underlying Stochastic Process......Page 45
4.2.2 Memory Efficient Analysis Method......Page 53
4.2.3 Multiple Simultaneously Active Instantiations of the Same Task Graph......Page 54
4.2.4 Construction and Analysis Algorithm......Page 57
4.3 Experimental Results......Page 61
4.3.1 Stochastic Process Size as a Function of the Number of Tasks......Page 63
4.3.3 Stochastic Process Size as a Function of the Task Dependency Degree......Page 64
4.3.4 Stochastic Process Size as a Function of the Average Number of Concurrently Active Instantiations of the Same Task Graph......Page 66
4.3.5 Rejection versus Discarding......Page 67
4.3.6 Encoding of a GSM Dedicated Signalling Channel......Page 69
4.4 Limitations and Extensions......Page 73
5 Analysis of Multiprocessor Systems......Page 77
5.1.1 Input......Page 78
5.2 Approach Outline......Page 79
5.3.1 Modelling of Task Activation and Execution......Page 82
5.3.3 Modelling Deadline Misses......Page 85
5.3.5 Scheduling Policies......Page 86
5.4 Generation of the Marking Process......Page 87
5.5 Coxian Approximation......Page 90
5.6 Approximating Markov Chain Construction......Page 91
5.7 Extraction of Results......Page 100
5.8 Experimental Results......Page 101
5.8.2 Analysis Time as a Function of the Number of Processors......Page 103
5.8.3 Memory Reduction as a Consequence of the On-the-Fly Construction of the Markov Chain Underlying the System......Page 104
5.8.4 Stochastic Process Size as a Function of the Number of Stages of the Coxian Distributions......Page 106
5.8.5 Accuracy of the Analysis as a Function of the Number of Stages of the Coxian Distributions......Page 107
5.9.1 Individual Task Periods......Page 108
5.9.2 Task Rejection vs. Discarding......Page 114
5.10 Conclusions......Page 119
6.1.1 Input......Page 121
6.2 Approach Outline......Page 122
6.3 The Inappropriateness of Fixed Execution Time Models......Page 123
6.4.1 The Tabu Search Based Heuristic......Page 126
6.4.2 Candidate Move Selection......Page 129
6.5.1 Analysis Algorithm......Page 132
6.5.2 Approximations......Page 138
6.6 Experimental Results......Page 142
6.6.1 RNS and ENS: Quality of Results......Page 143
6.6.4 Real-Life Example: GSM Voice Decoding......Page 145
III Communication Synthesis for Networks-on-Chip......Page 149
7.1 Motivation......Page 151
7.2 Related Work......Page 153
7.3 Highlights of Our Approach......Page 155
8.1 Hardware Model......Page 157
8.3 Communication Model......Page 158
8.4 Fault Model......Page 159
8.5 Message Communication Support......Page 160
9 Energy and Fault-Aware Time Constrained Communication Synthesis for NoC......Page 165
9.1.3 Constraints......Page 166
9.2 Approach Outline......Page 167
9.3 Communication Support Candidates......Page 168
9.4 Response Time Calculation......Page 173
9.5 Selection of Communication Supports......Page 174
9.6 Experimental Results......Page 176
9.6.1 Latency as a Function of the Number of Tasks......Page 177
9.6.2 Latency as a Function of the Imposed Message Arrival Probability......Page 178
9.6.3 Latency as a Function of the Size of the NoC and Communication Load......Page 179
9.6.5 Exploiting the Time Slack for Energy Reduction......Page 180
9.6.6 Real-Life Example: An Audio/Video Encoder......Page 182
9.7 Conclusions......Page 184
10 Buffer Space Aware Communication Synthesis for NoC......Page 187
10.1.3 Output......Page 188
10.2 Motivational Example......Page 189
10.3 Approach Outline......Page 192
10.3.1 Delimitation of the Design Space......Page 193
10.3.2 Exploration Strategy......Page 194
10.3.3 System Analysis Procedure......Page 197
10.4.1 Evaluation of the Solution to the CSBSDM Problem......Page 201
10.5 Conclusions......Page 204
IV Conclusions......Page 207
11.1.1 An Exact Approach for Deadline Miss Ratio Analysis......Page 209
11.1.3 Minimisation of Deadline Miss Ratios......Page 210
11.2.1 Time-Constrained Energy-Efficient Communication Synthesis......Page 211
11.2.2 Communication Buffer Minimisation......Page 212
Bibliography......Page 213