Project topics and materials
Get Complete Project Material File(s) Now! »
Real-time Multiprocessor Systems
The problem of scheduling real-time applications on multiprocessor systems is more complicated and challenging than real-time scheduling on uniprocessor systems. It is because there are more decisions to be taken in the case of multiprocessor scheduling and more issues to be considered. The responsibility of a real-time scheduler is not limited to decide which job to execute at what time, but also to decide on what processor to execute. Moreover, the multiprocessor schedulingproblem can be seen as two parts, (i) allocating tasks/jobs to processors and (ii) assigning them priorities to be used by the scheduler. Real-time multiprocessor scheduling is divided into the following categories based on migration level of jobs between processors:
Global scheduling in which job migration is completely allowed at any time and for all jobs. Hence, a given job can start its execution on one processor and migrate to another during its execution. In such systems, overheads due to job migration can be costly (e.g. additional communication loads, context switching and cache misses).Following our previous remark regarding the complexity of multiprocessor scheduling when compared to uniprocessors, Dhall and Liu [51] described a particular problem of multipro- cessor scheduling which is called the Dhall eect. It shows that task sets can be unschedu- lable using common scheduling algorithms such as RM, DM and EDF regardless of the number of used processors, as shown in the example in Figure 1.6. Thus, the scheduling algorithms lose their scheduling properties and their optimality when used on multiprocessor systems. The Dhall eect discouraged researchers from considering multiprocessor systems until Phillips et al. [95] showed that Dhall eect was related to high utilization tasks. Furthermore, Fisher [58] proved the impossibility of an online optimal scheduling algorithm for sporadic tasks on multiprocessor systems. This result is extended also to consider more general task models that include dependencies such as the generalized mul- tiframe model and the recurring task model4. Global scheduling has many advantages such as acceptable overheads and context switches and avoiding the complexity of jobassigning on processors.
Special Parallel Model: Fork-Join Tasks
The Fork-Join (FJ) model of parallel tasks is well known as the execution model of the famous OpenMP [1] framework and Cilk programming language5. In this model, a task is dened as an alternative sequence of sequential and parallel segments. It consists mainly of a master thread that forks into multiple threads of the sameWCET to form a parallel segment. When all threads terminate their execution they merge again into the master thread. Figure 1.9 shows an example of a fork-join model. In this document, we consider that all parallel segments consist of the same number of threads. All threads of the same segment have the same WCET. The master thread of the FJ task represents its critical path and its length is the minimum sequential execution time of the task.
Special Parallel Model: Multi-Threaded Segment Tasks
Another model of parallel tasks is the Multi-Threaded Segment (MTS) model, which is a more general version of the FJ model but still a special case of the Directed Acyclic Graphs. Instead of having alternative sequence of sequential and parallel segments as in the Fork-Join model, a MTS task consists of a sequence of parallel segments, where each one consists of at least on thread. A segment is activated when all threads of the predecessor segment terminate their execution, and similarly, its successor segment becomes active after it terminates its execution. A segment that consists of a single thread is considered as a sequential segment.
Table of contents :
Abstract
Resume
Contents
List of Figures
List of Tables
List of Algorithms
Abbreviations
Symbols
1 General Introduction
1.1 Real-time Systems
1.1.1 Real-time Task Model
1.1.2 Real-time Scheduling
1.1.3 Real-time Algorithms
1.2 Development of Computer Processors
1.2.1 History of Processor Development
1.2.2 Uniprocessor Systems
1.2.3 Multiprocessor Systems
1.2.4 Real-time Multiprocessor Systems
1.3 Parallel Applications
1.3.1 Parallelism in Uniprocessor Systems
1.3.2 Parallelism in Real-time Systems
1.3.3 General Parallel Real-time Task Models
1.3.4 Directed Acyclic Graph (DAG)
1.3.4.1 Special Parallel Model: Fork-Join Tasks
1.3.4.2 Special Parallel Model: Multi-Threaded Segment Tasks
1.4 Problem Description and Contributions
2 Related Work
2.1 Real-time Scheduling of Uniprocessor Systems
2.2 Real-time Scheduling of Multiprocessor Systems
2.3 Parallel Real-time Scheduling
2.3.1 Parallel Scheduling on Uniprocessor Systems
2.3.2 Parallel Scheduling on Multiprocessor Systems
2.3.2.1 Model Transformation Scheduling Approach
2.3.2.2 Direct Scheduling Approach
3 Scheduling of Parallel Tasks using Model Transformation
3.1 Introduction and Motivation
3.2 Task Model and Notation
3.3 DAG Stretching (DAG-Str) Algorithm
3.3.1 The Multi-Threaded Segment (MTS) Representation
3.3.2 The DAG-Str Algorithm
3.3.3 Resource Augmentation Bound Analysis
3.4 Segment Stretching (Seg-Str) Algorithm
3.4.1 Concept and Algorithm
3.4.2 Resource Augmentation Bound Analysis
3.5 Simulation-Based Evaluation
3.5.1 DAG-Str Algorithm
3.5.2 Seg-Str Algorithm vs. DAG-Str Algorithm
3.6 Summary
4 Direct Scheduling Approach of Parallel DAG Tasks
4.1 Dening Extra Timing Parameters of DAG Tasks
4.1.1 Local Oset and Deadline for Subtasks
4.1.2 Local Release Jitter of Subtasks
4.2 Scheduling DAGs using Global Parameters
4.2.1 Interference Analysis on DAGs
4.2.1.1 The Worst Case Interference Scenario for DAG tasks
4.2.2 Sustainability Analysis
4.2.3 Schedulablity test
4.3 Scheduling DAGs using Local Parameters
4.3.1 Advantage of Subtask-Level Scheduling
4.3.2 Interference Analysis
4.3.3 Workload Analysis for Work Conserving Algorithms
4.3.4 Global Earliest Deadline First Scheduling Algorithm
4.3.5 Simulation-Based Evaluation
4.4 Summary
5 Experimental Analysis of DAG Task Scheduling
5.1 Incomparability of DAG Scheduling Approaches
5.1.1 DAG Stretching Algorithm vs. Direct Scheduling
5.1.2 Direct Scheduling: DAG-Level vs. Subtask-Level
5.2 Simulation-Based Evaluation
5.2.1 Simulation Tool: YARTISS
5.2.2 Simulation Features and Functionality
5.3 Simulation Results of DAG Scheduling Approaches
5.3.1 Simulation Results for GEDF Scheduling Algorithm
5.3.2 Simulation Results for GDM Scheduling Algorithm
5.4 Summary
6 Conclusion and Perspectives
6.1 List of Contributions
6.2 Future Work and Perspectives
A DAG TASK Generator in YARTISS Simulator
B Subtasks in YARTISS Simulator
Bibliography
