Real-Time Applications with Stochastic Task Execution Times: Analysis and Optimisation

✍ Scribed by Sorin Manolache, Petru Eles, Zebo Peng

• Publisher: Springer
• Year: 2007
• Tongue: English
• Leaves: 161
• Category: Library

✦ Synopsis

Real-Time Applications with Stochastic Task Execution Times presents three approaches to the analysis of the deadline miss ratio of applications with stochastic task execution times. Each of the three approaches fits best to a different context. The first approach is an exact one and is efficiently applicable to monoprocessor systems. The second approach is an approximate one, which allows for designer-controlled trade-off between analysis accuracy and analysis speed. It is efficiently applicable to multiprocessor systems. The third approach is less accurate but sufficiently fast in order to be placed inside optimisation loops. Based on the last approach, we propose a heuristic for task mapping and priority assignment for deadline miss ratio minimisation.

✦ Table of Contents

List of Figures
List of Tables
Preface
1 Introduction
1.1 Embedded System Design Flow
1.2 Stochastic Task Execution Times
1.3 Book Organisation
2 Related Work
3 System Modelling
3.1 Hardware Model
3.2 Application Model
3.2.1 Functionality
3.2.2 Periodic Task Model
3.2.3 Mapping
3.2.4 Execution Times
3.2.5 Real-Time Requirements
3.2.6 Late Task Policy
3.2.7 Scheduling Policy
3.3 Illustrative Example
4 Analysis of Monoprocessor Systems
4.1 Problem Formulation
4.1.1 Input
4.1.2 Output
4.1.3 Limitations
4.2 Analysis Algorithm
4.2.1 The Underlying Stochastic Process
4.2.2 Memory Efficient Analysis Method
4.2.3 Multiple Simultaneously Active Instantiations of the Same Task Graph
4.2.4 Construction and Analysis Algorithm
4.3 Experimental Results
4.3.1 Stochastic Process Size as a Function of the Number of Tasks
4.3.2 Stochastic Process Size as a Function of the Application Period
4.3.3 Stochastic Process Size as a Function of the Task Dependency Degree
4.3.4 Stochastic Process Size as a Function of the Average Number of Concurrently Active Instantiations of the Same Task Graph
4.3.5 Rejection versus Discarding
4.3.6 Encoding of a GSM Dedicated Signalling Channel
4.4 Limitations and Extensions
5 Analysis of Multiprocessor Systems
5.1 Problem Formulation
5.1.1 Input
5.1.2 Output
5.1.3 Limitations
5.2 Approach Outline
5.3 Intermediate Model Generation
5.3.1 Modelling of Task Activation and Execution
5.3.2 Modelling of Periodic Task Arrivals
5.3.3 Modelling Deadline Misses
5.3.4 Modelling of Task Graph Discarding
5.3.5 Scheduling Policies
5.4 Generation of the Marking Process
5.5 Coxian Approximation
5.6 Approximating Markov Chain Construction
5.7 Extraction of Results
5.8 Experimental Results
5.8.1 Analysis Time as a Function of the Number of Tasks
5.8.2 Analysis Time as a Function of the Number of Processors
5.8.3 Memory Reduction as a Consequence of the On-the-Fly Construction of the Markov Chain Underlying the System
5.8.4 Stochastic Process Size as a Function of the Number of Stages of the Coxian Distributions
5.8.5 Accuracy of the Analysis as a Function of the Number of Stages of the Coxian Distributions
5.8.6 Encoding of a GSM Dedicated Signalling Channel
5.9 Extensions
5.9.1 Individual Task Periods
5.9.2 Task Rejection vs. Discarding
5.9.3 Arbitrary Task Deadlines
5.10 Conclusions
6 Deadline Miss Ratio Minimisation
6.1 Problem Formulation
6.1.1 Input
6.1.2 Output
6.1.3 Limitations
6.2 Approach Outline
6.3 The Inappropriateness of Fixed Execution Time Models
6.4 Mapping and Priority Assignment Heuristic
6.4.1 The Tabu Search Based Heuristic
6.4.2 Candidate Move Selection
6.5 Analysis
6.5.1 Analysis Algorithm
6.5.2 Approximations
6.6 Experimental Results
6.6.1 RNS and ENS: Quality of Results
6.6.2 RNS and ENS: Exploration Time
6.6.3 RNS and LO-AET: Quality of Results and Exploration Time
6.6.4 Real-Life Example: GSM Voice Decoding
7 Conclusions
7.1 An Exact Approach for Deadline Miss Ratio Analysis
7.2 An Approximate Approach for Deadline Miss Ratio Analysis
7.3 A Fast Approximation Approach for Deadline Miss Ratio Analysis
7.4 Minimisation of Deadline Miss Ratios
Appendix: Elements of Probability Theory
Bibliography
Index