Algorithmes pour la grille et Ordonnancement.

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

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.

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.

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.

Déjeuner

Ordonnancement sur chemin critique et quelques outils

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.

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.

Autour de la veracite

Discussion