Project Topics
Get Complete Project Material File(s) Now! »
Estimation of Probabilistic Real-time Parameters
The estimation of distributions of probabilistic parameters (pWCET, pWCCT) is tackled in the literature using different techniques. These techniques are divided mainly into two categories; Static Probabilistic Timing Analysis (SPTA) and Measurement-Based Probabilistic Timing Analysis (MBPTA). Static Probabilistic Timing Analysis (SPTA): In order to build an upper bound of the pWCET distribution of a program, SPTA methods do not execute the program on the target hardware. In fact, they analyze the code and information about input values, along with an abstract model of the hardware behavior. First, they derive information about feasible paths and loop bound by analyzing the code and possible input values. Then, they upper bound the execution time distribution for every path by considering the behavior of hardware features such as pipelines and caches. Finally, they combine these execution time distributions to derive an upper bound on the pWCET distribution of the entire program. SPTA methods do not explore explicitly different valid scenarios of operation (sequence of input states and hardware states), instead they consider that any scenario could occur. Hence, they yield a valid upper bound on the pWCET distribution for a future scenario of operation. However, this upper bound is obtained after several over-approximations of dynamic behaviors of the program that cannot be precisely determined due to issues of tractability (e.g. cache states in a random replacement cache). Consequently, the estimated pWCET may introduce a significant pessimism.
Measurement-Based Probabilistic Timing Analysis (MBPTA): On the other hand, MBPTA methods execute the program multiple times, on the target hardware, according to several scenarios of operation (i.e. according to a set of feasible input states and initial hardware states) and they measure its execution times under each of these scenarios. Then, they use Extreme Value Theory (EVT) to make a statistical estimate of the pWCET distribution of the program by evaluating the extreme value distribution of measured execution times (samples). In the literature, there are two main methods to estimate the extreme value distribution [61, 62]; The Block Maxima method is based on the Fisher-Tippett- Gnedenko theorem. It splits samples into blocks and selects the maximum value inside each block. These values are used to fit a Generalized Extreme Value (GEV) distribution that estimates the pWCET of the program. Alternatively, the Peaks-over-Threshold (PoT) method, which is based on Pickands-Balkema-de Haan theorem, selects values that exceed a suitable threshold. Then, using these values, it fits a Generalized Pareto Distribution (GPD) that estimates the pWCET.
We note that MBPTA methods have lower complexity than SPTA ones when computing an estimate of pWCET since they do not consider all possible paths of the program and all possible inputs and hardware states. However, to guarantee a valid pWCET estimate by MBPTA methods, the chosen scenarios of operation, when measuring execution time, must be representative of those that will occur during the lifetime of the system. Otherwise, the derived pWCET could under-estimate the actual one and then it could be not a safe upper bound.
Hybrid Probabilistic Timing Analysis (HyPTA): According to the criticality of the application and the available means, one of these two presented methods or both (SPTA and MBPTA) are used to estimate the pWCET. Another category of techniques, called Hybrid Probabilistic Timing Analysis (HyPTA), are used to estimate pWCET. This category combines elements of both static and measurementbased analyses. It may take measurements at the level of sub-paths and then it uses pWCETs of different sub-paths to derive the pWCET of the program by using structural information obtained from static analysis of the code. Similarly to pWCET estimation, MBPTA techniques are used to estimate the pWCCT distribution of communication time between two programs (sub-tasks). In addition, a similar approach to static analysis is used to estimate communication time via the LIN protocol between ECUs on a vehicle in the work of Byhlin et al. [63].
Single core scheduling
The real-time queueing theory: In [70], Lehoczky presents an analysis based on queueing theory. This analysis operates on tasks with an arrival that follows a Poisson distribution of parameter and an execution time that follows an exponential law of means 1/μ. Actually, these hypotheses are restrictive, but at this time, the paper was one of the first that propose an analysis for a system with probabilistic arrivals and execution times. The author tries to characterize the remaining margin (lead-time) for each task. The problem has a theoretical solution in the case of dense arrivals. This estimate follows the same shape of the empirical distribution of the margin in different cases but it presents a significant difference. Probabilistic guarantee of schedulability: In the work of Tia and others [71], a performance analysis for a set of semi-periodic tasks is proposed. This model describes tasks with a periodic arrivals but with a variable execution time described by a probability distribution. This analysis provides a probabilistic guarantee by two methods.
The first method is called Probabilistic time demand analysis (PTDA) and it calculates the probability of meeting the deadline by any instance of a Ti task. This method is based on the classical demand time analysis and it finds a bound on the computation time required by the task Ti and all higher priority tasks. Then, authors estimate the probability that the bound at time t is less than t before the deadline Di. This probability is derived from the Cumulative Distribution Function (CDF) of the studied bound. Thus, an algorithm is implemented to determine this distribution. Indeed, the algorithm proceeds with a convolution if the number of execution time distributions to sum is less than 10. Otherwise, it uses the central limit theorem to estimate the sum of the probabilistic execution times.
The second method consists on transforming semi-periodic tasks into periodic tasks with constant execution times and sporadic tasks with the remaining execution time (if any). Then, two scheduling approaches are used. The first is to schedule the periodic tasks by the algorithm RM [12] while the other tasks are scheduled by a sporadic server. An analytic calculation, based on generating functions, is used to evaluate the probability that a sporadic task misses its deadline.
The second approach schedules the periodic tasks by EDF algorithm [12] while the sporadic tasks are scheduled by the Slack Stealing [72] algorithm. This approach is similar to the one used by Chetto and Chetto [42] to schedule periodic tasks with sporadic others by EDF. However, this approach has a linear complexity compared to a polynomial complexity for the solution proposed in [42].
Multi-core scheduling
Probabilistic execution time with precedence constraints: had two main periods of development. The first one is related to the early 2000’s regain of interest for probabilistic and statistical approaches, answering an increased pressure from the industrial partners to propose more complex models. During this period, one thread of results is dedicated to the scheduling analysis of DAG task models [78, 79], where a stochastic modelling for the execution times is proposed.
This thesis belongs to the second period started after 2010. Federated scheduling for DAG task model with probabilistic execution time [80] is another such recent work. The difficulties in advancing towards a more general solution does not come from a lack of interest from the real-time community. The difficulties are explainedby the fact that the DAG task model is placing the scheduling closer to the modeling stage within the design of a real-time system, while expressing an increased need of describing the functional constraints between tasks.
Deterministic Response Time Analysis
In this section, we propose a response time analysis of the DAG task model defined previously. Our RTA reduces pessimism when estimating Worst-Case Response Time (WCRT) without increasing computational complexity. Indeed, Palencia et al. [1] use fixed point equations to derive an estimation of WCRT.
These equations are based on a pessimistic assumption about worst-case arrival patterns that simplifies the analysis but causes an over-estimation of WCRT. On the other hand, Fonseca et al. [55] propose a response time analysis based on solving a MILP optimization problem. Their solution outperforms the work of Palencia et al. [1] and it reduces pessimism in the WCRT estimate. However, it increases the computational complexity and the run-time.
Our proposed response time analysis is based on iterative equations that reduce pessimism compared to Palencia et al. [1]. They reduce also the complexity of the method compared to Fonseca et al. work [55]. In order to present our response time equations, we start by explaining the equations proposed by Palencia et al. in [1]. Then, we describe how we derive our analysis by modifying these equations.
Holistic analysis for sub-task chains on distributed systems
Palencia et al. [1] compute an upper-bound on the response time of a chain of sub-tasks executed on a distributed system (several processors). They proceed sub-task by sub-task from the beginning of the chain. First, they compute the local response time, denoted wi,j , of the studied sub-task i,j when executed on its processor with all higher priority sub-tasks. They assume that these higher priority sub-tasks are activated synchronously with i,j (at the critical instant). Then, they add to the local response wi,j , the global response time of the predecessor sub-task of i,j and the communication delay between the two sub-tasks in order to obtain the global response time Rglobal i,j of sub-task i,j .
In Equation 3.1, we compute recursively the local response time. It updates monotonically wi,j until reaching a fixed point. This equation is guaranteed to converge if the total utilization of the task set is less than system resources (U m).
Extension of holistic analysis for a DAG task model
The holistic analysis for distributed systems (Section 3.2.1), implemented through Equations 3.1, 3.2 and 3.3, operates only on tasks composed of a single path without any parallel sub-tasks. Moreover, priorities are defined at task level because at sub-task level there is only one order of execution; it is the one that respects precedence constraints in the sub-task chain. However, in a DAG task model, several orders among sub-tasks could exist because there are parallel sub-tasks and multiple paths within a single task.
In this part, we present three methods to extend holistic analysis from a sub-task chains model (Section 3.2.1) to a DAG task model with parallel sub-tasks. First, we add to the equations analyzing the sub-task chains model, the effect of parallel sub-tasks from the same graph that are executed on the same core. Next, we identify and avoid counting the same sub-task several times because it is parallel to different sub-tasks. Thus, we reduce the pessimism and the over-estimation of the worst-case response time. Moreover, in the proposed extensions, we consider the two cases when priorities are defined at task level and at sub-task level. We provide a generic formulation for all equations by using the set hepi(i,j) of higher or equal priority sub-tasks inside the same graph. Depending on the definition of this set hepi(i,j), the equations are adapted to the desired definition of the level of priority .
In addition, the holistic analysis is applied only on periodic task sets. Thus, the derived extensions also operate on periodic task sets. However, we could use them to study the schedulability of sporadic task sets on a partitioned multi-core processor. Indeed, the multi-core partitioned scheduling problem could be seen as several single core processor scheduling problems once the allocation is done [14].
On the other hand, Baruah and Burns [19] show that response time analysis of fixed-priority and preemptive scheduling on a single core processor incorporating release jitter and blocking time is sustainable with respect to the period. Hence, if a periodic task set is schedulable with minimum inter-arrival time as the period for all tasks then it is schedulable with higher period and thus the sporadic system is schedulable. We conclude that the resulting sporadic systems on each core are all schedulable and so the whole partitioned task set is also schedulable.
Third method: Including parallel execution between predecessors
To avoid considering parallel sub-tasks on the critical path twice when computing sequential and global response times, we propose to consider first the effect of parallel execution from different paths that are predecessors to the studied sub-task.
Then, we add the effect of parallel sub-tasks that are not predecessors. We denote by Rpred i,j the preceding response time that considers the effect of higher priority DAG tasks and the effect of parallel sub-tasks that are predecessors of i,j while it omits the effect of parallel and not predecessor sub-tasks.
Table of contents :
List of my Publications
List of Figures
List of Tables
List of Abbreviations
List of Symbols
1 Introduction
1.1 Context and Motivation
1.2 Problem Description and Objectives
1.3 Thesis Outline
2 State Of The Art
2.1 Real-time Domain and Terms Definitions
2.1.1 Real-time Task Model
2.1.2 Real-time Scheduling
2.1.3 Real-time Schedulability Analysis
2.2 Multi-core Scheduling
2.2.1 Global Scheduling
2.2.2 Partitioned Scheduling
2.2.3 Hybrid Scheduling
2.3 Scheduling of Tasks with Precedence Constraints
2.3.1 Single Core Scheduling
2.3.2 Multi-core scheduling
2.4 Probabilistic Scheduling
2.4.1 Estimation of Probabilistic Real-time Parameters
2.4.2 Single core scheduling
2.4.3 Multi-core scheduling
3 Deterministic DAG Tasks Schedulability on a Multi-core Processor
3.1 Task Model
3.2 Deterministic Response Time Analysis
3.2.1 Holistic analysis for sub-task chains on distributed systems .
3.2.2 Extension of holistic analysis for a DAG task model
3.2.2.1 First method: Including parallel execution in local response time
3.2.2.2 Second method: Including parallel execution in global response time
3.2.2.3 Third method: Including parallel execution between predecessors
3.2.2.4 Worst-case arrival patterns assumption used in previous analyses
3.2.3 New characterization of worst-case arrival patterns
3.2.3.1 First method: Including preemption on the whole graph
3.2.3.2 Second method: Including preemption on connected sub-graphs
3.3 Conclusion
4 Probabilistic DAG Tasks Schedulability on a Multi-core Processor
4.1 Probabilistic Task Model and Definitions
4.2 Extension of Response Time Equations
4.2.1 Probabilistic Operators
4.2.1.1 Probabilistic sum (convolution) operator
4.2.1.2 Probabilistic maximum operator
Probabilistic maximum based on independent random variables comparison
Probabilistic maximum based on CDF function comparison
Probabilistic maximum based on the Fréchet-Hoeffding copula bound
4.2.2 Extension of first method equations
4.2.2.1 Replacing sum and maximum operators
4.2.2.2 Iterative equation for global response time
4.2.3 Extension of second method equations
4.3 Bayesian Network Inference For Dependent Random Variables .
4.3.1 Modeling Dependencies
4.3.2 Probabilistic Inference
4.3.2.1 Exact Inference: Variable Elimination
4.3.2.2 Approximate Inference: Sampling
4.4 Schedulability in Probabilistic C-space
4.4.1 C-space and schedulability
4.4.2 C-space and Classification
4.4.2.1 Border and regions characterization
4.4.2.2 SVM classifier
Single core processor
Multi-core processor
4.5 Conclusion
5 Scheduling techniques
5.1 Priority Assignment
5.1.1 Priority assignment at the task level
5.1.1.1 Deadline Monotonic
5.1.1.2 Audsley’s Algorithm
5.1.2 Priority at the sub-task level
5.1.2.1 Motivation Example
5.1.2.2 Optimal Sub-task Priority Assignment
5.1.2.3 Sub-task Priority Assignment Heuristic
5.1.2.4 Sub-task Priority Assignment with a Genetic Algorithm
5.2 Partitioning Heuristic
5.3 Graph Reduction
5.3.1 ILP based approach
5.3.2 Heuristic based approach
5.4 Integrated Scheduling Methodology
6 Evaluation Results
6.1 Experimental Setup
6.1.1 Random Generation of DAG Tasks
6.1.2 SimSo Simulator
6.2 Evaluation of RTA and Scheduling Techniques
6.2.1 Response Time Analysis
6.2.1.1 Deterministic approach
First experiment
Second experiment
Third experiment
6.2.1.2 Probabilistic approach
Response time equations based on probabilistic operators
Bayesian network
C-space and SVM classifier
6.2.2 Priority Assignment for Sub-tasks
6.2.3 Partitioning Heuristic
6.2.4 Graph Reduction
6.3 Use Case: PX4 Autopilot
6.3.1 Single Core Processor
6.3.2 Multi-core Processor
7 Conclusion and Perspectives
7.1 Contributions
7.2 Research Perspectives
Appendices
A DAG scheduling with MILP Formulation
A.1 MILP Formulation [59]
A.2 Specific Case
A.3 Adapting Constraints
B NP-hardness of Graph Reduction Problem
C Example of Generated DAG Tasks
References
