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
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