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

https://hal.inria.fr/inria-00636028
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

File

siralina.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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. ⟨http://www.springerlink.com/content/r30422pm90m33602/⟩. ⟨10.1007/s10878-010-9332-8⟩. ⟨inria-00636028⟩

Share

Metrics

Record views

326

Files downloads

190