Paper Info
Title
A Stretching Algorithm for Parallel Real-time DAG Tasks on Multiprocessor Systems
Abstract
Parallelism is becoming more important nowadays due to the increasing use of multiprocessor systems. In this paper, we study the problem of scheduling periodic parallel real-time Directed Acyclic graph (DAG) tasks on m homogeneous multiprocessor systems. A DAG task is an example of inter-subtask parallelism. It consists of a collection of dependent subtasks under precedence constraints. The dependencies between subtasks make scheduling process more challenging. We propose a stretching algorithm applied on each DAG tasks to transform them into a set of independent sequential threads with intermediate offsets and deadlines. The threads obtained with the transformation are two types, (i) fully-stretched master threads with utilization equal to 1 and (ii) constrained-deadline independent threads. The fully-stretched master threads are assigned to dedicated processors and the remaining processors m′ ≤ m, are scheduled using global EDF scheduling algorithm. Then, we prove that preemptive global EDF scheduling of stretched threads has a resource augmentation bound equal to 3+√5/2 for all tasksets with n < &phiv; ·m′, where n is the number of tasks in the taskset and &phiv; is the golden ratio.
Year
DOI
Venue
2014
10.1145/2659787.2659818
RTNS
Keywords
Field
DocType
real-time systems and embedded systems,algorithms,design,graphs and networks,experimentation,real-time scheduling,speedup factor,parallel tasks,measurement,global edf scheduling,performance,real-time and embedded systems,directed acyclic graphs
Computer science,Scheduling (computing),Real-time computing,Distributed computing,Multiprocessor scheduling,Fair-share scheduling,Parallel computing,Gang scheduling,Algorithm,Thread (computing),Directed acyclic graph,Multiprocessing,Periodic graph (geometry)
Conference
Citations 
PageRank 
References 
5
0.46
9
Authors
3
Name
Order
Citations
PageRank
Manar Qamhieh1393.27
Laurent George221429.39
Serge Midonnet37713.13