Sid-Ahmed-Ali Touati (PRISM, Versailles)



"Efficient Method for Periodic Task Scheduling with Storage Requirement Minimisation"

Karine Deschinkel, Sid-Ahmed-Ali Touati

Abstract:

In this paper, we study the general problem of one-dimensional periodic task 
scheduling under storage requirement, irrespective of machine constraints. 
We have already presented in \cite{Touati:MISTA:07} a theoretical framework 
that  allows an optimal optimisation 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 
\cite{TouatiPHD}, solving an exact integer linear programming formulation as 
proposed in \cite{Touati:MISTA:07}  is too expensive in practice. 
In this article, we propose an efficient two-steps heuristic using model's 
properties that allows fast resolution times while providing nearly optimal 
results.  This method includes the resolution of a integer linear program with
a totally unimodular constraints matrix in first step, then the resolution of 
a linear assignment problem. Our solution has been implemented and included 
inside a compiler for embedded processors in collaboration with 
STmicroelectronics.