Skip to Main content Skip to Navigation
Conference papers

A Rapid Heuristic for Scheduling Non-Preemptive Dependent Periodic Tasks onto Multiprocessor

Omar Kermia 1 Yves Sorel 1
1 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We address distributed real-time applications represented by systems of non-preemptive dependent periodic tasks. This system is described by an acyclic directed graph. Because the distribution and the scheduling of these tasks onto a multiprocessor is an NP-hard problem we propose a greedy heuristic to solve it. Our heuristic sequences three algorithms: assignment, unrolling, and scheduling. The tasks of the same, or multiple, periods are assigned to the same processor according to a mixed sort. Then, the initial graph of tasks is unrolled, i.e. each task is repeated according to the ratio between its period and the least common multiple of all periods of tasks. Finally, the tasks of the unrolled graph are distributed and scheduled onto the processors where they have been assigned. Then, we give the complexity of this heuristic, and we illustrate it with an example. A performance analysis comparing our heuristic with an optimal Branch and Cut algorithm concludes that our heuristic is effective in terms of scheduling success ratio and speed.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00413486
Contributor : Kumar Guha <>
Submitted on : Friday, September 4, 2009 - 11:54:44 AM
Last modification on : Tuesday, May 26, 2020 - 6:50:21 PM
Document(s) archivé(s) le : Tuesday, June 15, 2010 - 8:31:27 PM

File

pdcs07.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00413486, version 1

Collections

Citation

Omar Kermia, Yves Sorel. A Rapid Heuristic for Scheduling Non-Preemptive Dependent Periodic Tasks onto Multiprocessor. Proceedings of ISCA 20th International Conference on Parallel and Distributed Computing Systems, PDCS'07, 2007, Las Vegas, Nevada, United States. ⟨inria-00413486⟩

Share

Metrics

Record views

789

Files downloads

355