(Downloads - 0)
For more info about our services contact : help@bestpfe.com
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
