HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 metadata

Cited literature [18 references]  Display  Hide  Download

Contributor : Kumar Guha Connect in order to contact the contributor
Submitted on : Friday, September 4, 2009 - 11:54:44 AM
Last modification on : Friday, January 21, 2022 - 3:16:11 AM
Long-term archiving on: : Tuesday, June 15, 2010 - 8:31:27 PM


Files produced by the author(s)


  • HAL Id : inria-00413486, version 1



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⟩



Record views


Files downloads