Réunions
Réunion du 3 Avril 2008
La réunion aura lieu à l'ENS de Lyon dans l'amphi B. Venir a l'ENS.
Planning
- 09H30 -> 10H00 : Accueil
- : Application de type 'sac de tâches': ordonnancement hors-ligne et en-ligne par Loris Marchal (LIP)
- : Un algorithme polynomial 2-approché pour le problème de dimensionnement des mémoires avec débit maximum intrinsèque par Olivier Marchetti (LIP6)
- : Multi-threaded Caching Problem par Haifeng Xu (LIG)
- 12H00 -> 13h30 : Déjeuner
- : Ordonnancement sur chemin critique et quelques outils par Christophe Cerin (LIPN)
- : Stratégies d'Ordonnancement pour l'Optimisation Bicritère du Makespan et de la Robustesse par Louis-Claude Canon (LoRIA)
- : Ordonnancement de tache couplées par Gilles Simonin (LIRM)
- : Autour de la veracite par Evripidis Bampis (LaMI)
- 16H00 -> 17H00 : Discussion
Details
Accueil
Application de type 'sac de tâches': ordonnancement hors-ligne et en-ligne
Les problèmes liés à l'ordonnancement de tâches sont déjà difficiles sur des machines traditionnelles. Ils deviennent encore plus inextricables sur des machines hétérogènes, même lorsque les applications considérées sont facilement parallélisables (de type tâches indépendantes). Nous nous intéressons ici à l'ordonnancement d'applications multiples, sous forme de collections de tâches indépendantes et identiques, sur une plate-forme maître-esclave hétérogène. Les requêtes de calcul surviennent au cours du temps, ce qui signifie que nous ne disposons pas de connaissance sur la charge de travail au tout début de l'exécution. Notre objectif est de minimiser l'étirement (stretch) maximum des applications, c'est-à-dire le rapport entre le temps que l'application passe dans le système avant d'être terminée et le temps qu'elle y aurait passé si elle disposait de la plate-forme pour elle seule. D'un point de vue théorique, nous concevons un algorithme optimal pour le cas hors-ligne (offline), lorsque toutes les dates d'arrivée et les caractéristiques des applications sont connues à l'avance. Nous proposons également plusieurs méthodes heuristiques pour le cas en-ligne (online), sans connaissance sur l'arrivée future des applications. D'un point vue expérimental, nous avons mené des expérimentations approfondies sous la forme de simulations avec SimGrid mais aussi dans un environment parallèle réel, en utilisant MPI. Ces expérimentations montrent que nous sommes capables d'ordonnancer des problèmes de grande taille en quelques secondes. Enfin, la solution que nous proposons surpasse les méthodes heuristiques classiques, ce qui démontre l'intérêt de notre démarche.
- Slide Show (PDF)
Un algorithme polynomial 2-approché pour le problème de dimensionnement des mémoires avec débit maximum intrinsèque
Lors de la synthèse des systèmes embarqués, la phase de dimensionnement des mémoires s'avère être une étape cruciale. Une spécification majeure de ces systèmes est que chaque processus doit pouvoir s'exécuter un nombre de fois non-borné a priori. Dans ce contexte, il est impératif de garantir un certain débit de l'application tout en minimisant la surface totale occupée par les mémoires sur la puce. Pour traiter ce problème d'ordonnancement cyclique, nous utilisons le formalisme des graphes d'événements généralisés temporisés (GEGT, sous-classe des réseaux de Petri). Après avoir rappelé quelques résultats de complexité associés à ce problème, nous proposons un algorithme polynomial 2-approché qui détermine les tailles de chacune des mémoires (la surface totale obtenue étant au pire deux fois plus grande que la surface optimale) de sorte à ce que l'application puisse atteindre son débit maximum intrinsèque.
- Slide Show (PDF)
Multi-threaded Caching Problem
Caching problem is a well-studied problem in online algorithms, usually under the assumption that there is only one chain of requests to be served. However, recent applications related to this problem may need to process more than one chain.
Here we introduce an extension of caching problems, say multi-threaded caching problem, where there are more than one chain of requests. Hence, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities.
- Slide Show (PDF)
Déjeuner
Ordonnancement sur chemin critique et quelques outils
- Slide Show (PDF)
- Paper (PDF)
Stratégies d'Ordonnancement pour l'Optimisation Bicritère du Makespan et de la Robustesse
Nous considérons le problème de l'ordonnancement de graphes de tâches lorsque les durées de traitement sont soumises à des incertitudes. Les deux objectifs principaux sont alors de minimiser le temps d'exécution tout en maximisant la robustesse. Ceux-ci n'étant pas équivalents, une approche bicritère est nécessaire. Nous proposons donc différentes stratégies qui couvrent un large spectre de solutions en terme de compromis qualité/temps de calcul. Parmi celles-ci, une métaheuristique dont nous étudions la convergence vers le front de Pareto.
- Slide Show (PDF)
Ordonnancement de tache couplées
Nous étudions un problème d'ordonnancement avec des tâches-couplées en présence d'un graphe de compatibilité sur un monoprocesseur. Dans un premier temps, nous présenterons la modélisation de ce problème, puis un état de l'art de ce problème sans graphe de compatibilité. Nous verrons l'impact du graphe de compatibilité sur ces problèmes d'un point de vu de la complexité. Nous présenterons les différentes façons de chercher des bornes d'approximations et de non-approximations. Cette présentation sera donc une introduction à ce problème et un survol des différents résultats et techniques déjà utilisées.
- Slide Show (PDF)