Systematic Searches for Global Multiprocessor Real-Time Scheduling

Olivier Buffet (1) , Liliana Cucu-Grosjean (2)

1 MAIA - Autonomous intelligent machine
2 TRIO - Real time and interoperability

In this paper we address the problem of global real-time periodic scheduling on homogeneous multiprocessor platforms. A number of theoretical results have been obtained in the field of real-time systems, but mainly focusing on properties of specific algorithms in uniprocessor settings. The multiprocessor case has been considered only recently, with few resolution techniques proposed and experimented with up to now. In this paper we discuss several systematic search algorithms—exploring different search spaces—that exploit various features of the problem. These approaches are then evaluated experimentally on numerous randomly generated problems. This work shows (1) how two heuristic approaches can solve most (feasible and unfeasible) problems in no time, and (2) how to improve a state of the art algorithm by looking at jobs' laxities and by focusing the search on bottlenecks. We also discuss limitations of the proposed solvers and future work.

Mots clés: global realtime periodic scheduling; multiprocessor scheduling; systematic search

Domaines: Intelligence artificielle [cs.AI]; Systèmes embarqués

Olivier Buffet, Liliana Cucu-Grosjean. Systematic Searches for Global Multiprocessor Real-Time Scheduling. [Research Report] RR-7386, INRIA. 2010, pp.17. ⟨inria-00519324⟩