Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization

International audience In this paper, we study an efficient approximate integer linear programming formulation of the general problem of one-dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in [8] a theoretical framework t...

Full description

Bibliographic Details
Main Authors: Deschinkel, Karine, Touati, Sid
Other Authors: Parallélisme, Réseaux, Systèmes, Modélisation (PRISM), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS)
Format: Conference Object
Language:English
Published: HAL CCSD 2008
Subjects:
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]
Newfoundland
Canada
Online Access:https://inria.hal.science/inria-00637210
https://inria.hal.science/inria-00637210/document
https://inria.hal.science/inria-00637210/file/Efficient_Method_for_Periodic_Task.pdf
https://doi.org/10.1007/978-3-540-85097-7_41
Description
Summary:International audience In this paper, we study an efficient approximate integer linear programming formulation of the general problem of one-dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in [8] a theoretical framework that allows an optimal optimization of periodic storage requirement in a periodic schedule. This problem is used to optimise processor register usage in embedded systems. Our storage optimisation problem being NP-complete [7], solving an exact integer linear programming formulation as proposed in [8] is too expensive in practice. In this article, we give an efficient approximate model that allows fast resolution times while providing nearly optimal results. Our solution has been implemented and included inside a compiler for embedded processors.

Similar Items