SIRALINA: efficient two-steps heuristic for storage optimisation in single period task scheduling

Karine Deschinkel 1 Sid Touati 1, 2 Sébastien Briais 1
2 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 : 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 (Touati and Eisenbeis, Parallel Process. Lett. 14(2):287-313, 2004) a theoretical framework that allows an optimal optimisation of periodic storage requirement in a cyclic schedule. Since our optimisation problem is NP-hard (Touati, PhD thesis, 2002), 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 computation times while providing highly satisfactory results. This method includes the solution of an integer linear program with a totally unimodular constraints matrix in first step, then the solution of a linear assignment problem. Our heuristic is implemented for an industrial compiler for embedded VLIW processors.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [25 references]  Display  Hide  Download
Contributor : Sid Touati <>
Submitted on : Friday, February 3, 2012 - 10:44:37 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Monday, November 19, 2012 - 3:45:31 PM


Files produced by the author(s)




Karine Deschinkel, Sid Touati, Sébastien Briais. SIRALINA: efficient two-steps heuristic for storage optimisation in single period task scheduling. Journal of Combinatorial Optimization, Springer Verlag, 2011, 22 (4), pp.819-844. ⟨⟩. ⟨10.1007/s10878-010-9332-8⟩. ⟨inria-00636028⟩



Record views


Files downloads