The "séminaire OCAD" receives Karine Deschinkel (Laboratoire PRiSM,Université de Versailles).

Cet article traite du problème d'optimisation du besoin en stockage dans les graphes de tâches périodiques. En pratique, notre problème tend à minimiser le besoin en registres dans les programmes embarqués, où les instructions d'une boucle sont représentées par un graphe de dépendances de données cyclique (GDD).

Le problème d'ordonnancement périodique de tâches (instructions) cycliques avec minimisation du nombre de registres, dans sa forme la plus générale, peut se formuler sous forme d'un programme linéaire en nombre entiers où les variables de décision sont les dates de début de chacune des tâches, des variables binaires indiquant une réutilisation ou non de registres entre deux tâches (non nécessairement distinctes), et les distances de réutilisation. Ce problème étant NP-complet , une résolution exacte s'avère trop coûteuse en pratique.

Ici, nous avons exploité le fait que le problème en question fait apparaître un problème sous-jacent d'affectation pour lequel nous connaissons un algorithme en temps polynomial (méthode Hongroise) pour proposer une heuristique appropriée appelée SIRALINA. Cette heuristique très satisfaisante est en train d'être incluse dans un compilateur pour l'embarqué chez STMicroelectronics.