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 a theoretical framework that allows an optimal optimization of periodic storage requirement in a periodic schedule. This problem is used to optimize processor register usage in embedded systems. Our storage optimization problem being NP-complete, solving an exact integer linear programming formulation 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.
展开▼
