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, 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.
Type de document :
Article dans une revue
Journal of Combinatorial Optimization, Springer Verlag, 2011, 22 (4), pp.819-844. 〈http://www.springerlink.com/content/r30422pm90m33602/〉. 〈10.1007/s10878-010-9332-8〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00636028
Contributeur : Sid Touati <>
Soumis le : vendredi 3 février 2012 - 10:44:37
Dernière modification le : jeudi 9 février 2017 - 15:45:07
Document(s) archivé(s) le : lundi 19 novembre 2012 - 15:45:31

Fichier

siralina.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de
la notice

214

Téléchargements du document

157