SIRALINA: efficient two-steps heuristic for storage optimisation in single period task scheduling - Archive ouverte HAL Access content directly
Journal Articles Journal of Combinatorial Optimization Year : 2011

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

(1) , (1, 2) , (1)
1
2

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.
Fichier principal
Vignette du fichier
siralina.pdf (266.28 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00636028 , version 1 (03-02-2012)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More