Le 09/01/2012 par alm :
Sujet de stage de Master M2 : Etude d'algorithmes approchés pour l'ordonnancement d'applications sur une architecture multi-core avec des dates d'échéance et de disponibilité.
Responsables : Claire Hanen Claire.Hanen@lip6.fr, Alix Munier-Kordon Alix.Munier@lip6.fr
Sujet : Les architectures multi-cores offrent aujourd'hui pour un coût relativement bas des ressources de calculs en nombre important. Cependant, lorsque l'on souhaite déployer une application de manière semi-automatique sur ce type d'architecture, l'on se retrouve rapidement confronté à un ensemble de problèmes combinatoires. A défaut de les résoudre efficacement, les ressources de ces architectures sont sous-employées ; les temps d'exécution des applications restent élevés malgré la puissance de calcul potentiel offert par ces machines.
D'un point de vue théorique, ces nouvelles architectures entrainent des contraintes à prendre en compte pour construire des ordonnancements efficaces : des dates d'échéance et de disponibilité pour les différentes tâches présentes dans les applications temps-réels, mais aussi des délais entre les tâches dépendantes, dus aux temps de communication, aux accès à la mémoire partagée ou encore au fait que les processeurs soient pipelinés.
Les problèmes d'ordonnancement avec dates d'échéance ont fait l'objet de nombreux travaux théoriques. Deux algorithmes classiques de liste ont notamment été repris de manière indépendante par plusieurs auteurs :
L'algorithme de Garey-Johnson [1] résoud de manière exacte la recherche d'un ordonnancement réalisable avec dates d'échéance pour deux machines identiques et des tâches unitaires dépendantes.
L'algorithme de Leung, Palem et Pnueli [2] résoud de manière exacte des problèmes avec tâches typées dont le graphe de précédence présente certaines caractéristiques particulières.
Récemment, C. Hanen et A. Munier-Kordon ont établi que pour les problèmes d'ordonnancement avec des tâches unitaires, des dates de disponibilité et des dates d'échéance sur machines parallèles, les deux algorithmes reposent sur une notion commune de cohérence des échéances. Une des conséquences est que pour cette famille de problèmes, les résultats prouvés pour l'un des algorithmes s'appliquent à l'autre et réciproquement, unifiant ainsi un ensemble de résultats épars de la littérature.
Le but de ce stage est de proposer et programmer un algorithme le plus efficace possible d'un point de vue complexité qui s'appuie sur la convergence constatée des deux algorithmes cités précédemment et l'utilise pour en tirer le meilleur parti algorithmique. Son efficacité et la qualité des solutions obtenues devront être étudiés d'un point de vue expérimental, ainsi que la distance avec la performance théorique dans le pire des cas.
Pré-requis : de bonnes connaissances en algorithmique et en recherche opérationnelles sont indispensables, ainsi que la maîtrise d'au moins un langage de programmation.
Conditions du stage : le stage doit avoir lieu au LIP6, 4 place Jussieu, 75252 Paris cedex 05. Sa durée est de 5 à 6 mois et sera gratifié (approx. 417/mois).
Bibliographie [imgs=][/imgs][url=][/url]:
[1] M. R. Garey and D. S. Johnson. Two-processor scheduling with start-time and deadlines. SIAM Journal on Computing, 6:416426, 1977.
[2] Allen Leung, Krishna V. Palem, and Amir Pnueli. Scheduling time-constrained instruc-tions on pipelined processors. ACM Trans. Program. Lang. Syst., 23:73103, January 2001.
