C'est avec un plaisir non dissimulé que je vous invite à ma soutenance
de thèse intitulée :
"Etude du RCPSP cyclique".
Ainsi qu'au pot qui suivra.
La soutenance se déroulera le : Lundi 07 février 2011 à 16h30, au
LIP6 salle 105 (barre 25-26) 1er étage.
Bien cordialement,
Abir Benabid.
=======*=
Jury
=======*=
M. Christian Artigue, CNRS-LAAS de Toulouse examinateur
M. Benoit D. De Dinechin, Responsable du développement logiciel à Kalray
Mme. Claire Hanen, Université Paris Ouest Nanterre la Defense
M. Jean-Claude Konig, Université de Montpellier
Mme. Alix Munier Kordon, Université Pierre et Marie Curie
M. Sid-Ahmed-Ali Touati, Université de Versailles
M. Frédéric Vivien, INRIA Rhone-Alpes
=======*=
Résumé
=======*=
La constante évolution des architectures des processeurs à haute
performance, afin de répondre aux exigences des applications embarquées,
donnent de plus en plus d'importance à une programmation plus
performante, surtout au niveau de la compilation, dans ces systèmes.
Notre étude est particulièrement motivée par l'optimisation de
l'ordonnancement lors de la compilation des instructions dans les
processeurs de type VLIW (Very Large Instruction Word), et sa résolution à
l'aide du RCPSP (Resource Constrained Project Scheduling Problem)
cyclique. Dans un tel model, on dispose en général d'un petit nombre
d'unités fonctionnelles indépendantes et qui peuvent exécuter plusieurs
tâches simultanément si les dépendances de données s'y prêtent et si les
ressources nécessaires sont disponibles.
Aujourd'hui, les études théoriques dans le domaine d'ordonnancement
cyclique visent à caractériser les algorithmes d'ordonnancement (analyses
du pire cas, résultat d'optimalité, etc) pour des applications réelles
aussi bien dans les systèmes embarqués que dans les systèmes de
production. Dans le cadre de cette thèse, nous avons travaillé sur la
détermination de modèles appropriés, capables de prendre en compte les
nouvelles caractéristiques de ces systèmes (la nature des dépendances,
l'hétérogénéité des ressources, etc.). Plusieurs algorithmes approchés
avec garanties de performance ont été proposés, ainsi qu'une étude
expérimentale, afin d'analyser leur efficacité en pratique, a été établie.
=======*=
Abstract
=======*=
The constant evolution of high performance processors architectures, to
hold the challenging requirements of embedded applications, gives an
increasing importance to a more efficient programming, mainly in
compilation level, in these systems. Our study is particularly motivated
by the optimization of scheduling when compiling instructions in VLIW
processors (Very Large Instruction Word), and its resolution by using the
RCPSP (Resource Constrained Project Scheduling Problem) cyclic. In such
model, there is usually a small number of independent functional units
that can execute multiple task simultaneously if the data dependencies are
met and if necessary resources are available.
Today, theoretical studies in the field of cyclic scheduling aims to
characterize the scheduling algorithms (worst-case analysis, optimality
result, etc.) for real applications in embedded systems as well as in mass
production systems. In this thesis, we worked on identifying suitable
models, able to take into account the new characteristics of these systems
(the nature of dependencies, the heterogeneity of resources, etc..).
Several approximation algorithms with performance guarantees have been
proposed, and an experimental study to analyze their performance in
practice has been established.
