La ROADEF
La R.O.A.D
Evénements
Prix
Publications
Plus
Forums
Connexion
Livre blanc

Soutenance de these de Maria Alejandra Ayala Perez le 15 Juin 2011

Forum 'Annonces' - Sujet créé le 2011-06-07 par mayala

DOCTORAT DE L'UNIVERSITE DE TOULOUSE

Délivré par l'Université Paul Sabatier


École Doctorale : EDSYS

Unité de recherche : LAAS-CNRS groupe MOGISA

Spécialité : Systèmes Informatiques et Systèmes Industriels

Titre :

Programmation linéaire en nombres entiers pour l'ordonnancement cyclique sous contraintes de ressources.

de

Maria Alejandra Ayala Perez (Groupe MOGISA)
E-mail : maria.ayala@laas.fr


*Date :15 Juin 2011 à 10h30

Lieu :! LAAS-CNRS - Salle de Conférences
7 avenue du Colonel Roche
31077 TOULOUSE Cedex 4

Composition du jury :

DIRECTEUR DE THÈSE

Christian ARTIGUES, Chargé de recherche, LAAS-CNRS

RAPPORTEURS

Eric SANLAVILLE, Professeur , Université de Havre

Marc SEVAUX, Professeur , Université de Bretagne-Sud

EXAMINATEURS

Claire HANEN, Professeur , Université Paris Ouest Nanterre la Défense

Benoit DUPONT de DINECHIN, Directeur du Développement Logiciel, KALRAY Grenoble

Pascal SAINRAT, Professeur , Université Paul Sabatiér

Résumé :

Un problème d'ordonnancement cyclique consiste à ordonner dans le temps l'exécution répétitive d'un ensemble d'opérations liées par des contraintes de précédence, en utilisant un nombre limité de ressources. Ces problèmes ont des applications immédiates dans les systèmes de production ou en informatique parallèle. Particulièrement, ils permettent de modéliser l'ensemble des contraintes de précédence et de ressource à prendre en compte pour l'ordonnancement d'instructions dans les processeurs de type VLIW (Very Long Instruction Word). Dans ce cas, une opération représente une instance d'une instruction dans un programme.

L'ordonnancement d'instructions de boucles internes est connu sous le nom de pipeline logiciel. Le pipeline logiciel désigne une méthode efficace pour l'optimisation de boucles qui permet la réalisation en parallèle des opérations des différentes itérations de la boucle. Dans cette thèse, nous nous intéressons principalement au problème d'ordonnancement périodique qui est un cas particulier de l'ordonnancement cyclique et qui est également la base du pipeline logiciel. Le terme ordonnancement modulo désigne un ordonnancement périodique tel que l'allocation de ressources pour une opération donnée n'est pas modifiée d'une itération sur l'autre! .

Pour résoudre le problème, nous nous intéressons aux formulations de programmation linéaire en nombres entiers, et notamment à la résolution du problème par des techniques de séparation, évaluation, génération de colonnes, relaxation lagrangienne et des méthodes hybrides. En particulier, nous proposons des nouvelles formulations basées sur des variables binaires représentant l'exécution d'ensembles d'instructions en parallèle. Enfin, les méthodes développées ont été validées sur des jeux d'instances industrielles pour des processeurs de type VLIW.




Mot(s)-clé(s) : décomposition de Dantzig-Wolfe - méthodes hybrides - ordonnancement modulo - programmation linéaire en nombres entiers - relaxation lagrangienne