Algorithmes pour la grille et Ordonnancement.

Réunions

Réunion du 15 novembre 07

La réunion aura lieu à Grenoble dans la Maison Jean Kuntzman (MJK) sur le campus. Venir à la MJK.

Planning

Details

Accueil

Comment tenir compte des incertitudes

Les nouveaux supports d'exécution sont caratérisés par une plus grande hétérogénéité des ressources, et une versatilité plus grande des données et des composants (processeurs, liens de communications, etc.). Au cours de cet exposé, nous ferons une rapide introduction des approches déterministes qui permettent de tenir compte des incertitudes sur les données vis à vis de la fonction objectif.

Nous présenterons en particulier, les approches semi on-line qui partent d'une solution initale calculée sur des prédictions des données, et de mécanismes de corrections à l'exécution.

Comparaison des métriques et conception d'heuristiques pour l'ordonnancement robuste de graphes de tâches sur des systèmes hétérogènes

Un ordonnancement est dit robuste s'il est capable d'absorber des variations dans les durées des tâches tout en maintenant une solution stable. Cette notion intuitive de la robustesse a induit beaucoup d'interprétations et de métriques différentes. Cependant, il n'existe pas de comparaison entre ces dernières. Nous présentons donc une étude empirique de ces métriques et montrons comment elles sont corrélées dans le cadre de l'ordonnancement de tâches dépendantes. Dans une seconde phase, nous menons une investigation sur le plan d'heuristiques efficaces et performantes pour l'objectif de la robustesse.

Allocations équitables en ligne

Nous nous sommes intéressés au cas de l'ordonnancement multi-utilisateurs en ligne de tâches permanentes où l'on cherche à être le plus équitable possibles entre les utilisateurs. Nous avons cherché dans un cadre "multi-critères" les propriétés de l'ensemble des politiques d'allocations qui prennent en compte les demandes futures possibles et qui soient dominantes pour la relation d'ordre de l'équité. Nous proposons un algorithme de recherche des frontières de Pareto classique et Pareto équitable. Cet exposé portera principalement sur des travaux en démarrage.

Déjeuner

Ordonnancement de lot de travaux identiques sur une plate-forme d'exécution hétérogène

Nous nous intéressons à l´ordonnancement d´un lot de travaux identiques sur une plate-forme d´exécution hétérogène. Chacun des travaux de ce lot est une application exécutée indépendamment des autres, si possible en parallèle. Cette application est décrite par un graphe de tâches orienté, acyclique (DAG) et sans fourche (anti-arbre) dans lequel chaque noeud est une tâche et chaque arête est une dépendance. La plate-forme d´exécution est une grille de calcul formée de machines interconnectées par des liens réseau. L´originalité de nos travaux tient au fait que chaque noeud n´est capable d´exécuter qu´un sous-ensemble des tâches, et plusieurs machines peuvent exécuter un même type de tâche.

New Approaches to Broadcast Messages in Grid Environment

In this talk we introduce new algorithms to achieve performance for broadcasting data in a large scale platform. Many algorithms were built in the past for broadcasting messages in a cluster linked by an homogeneous network. Our target architecture is hyper-cluster, typically a computing grid, composed of geographically distributed clusters interconnected by a dedicated private network. Since network is heterogeneous in such infrastructure, we need to optimize network occupation. We investigated the case were a source node broadcasts a message to some distant nodes located in the same cluster as well as in the other clusters. Our approach is based on an extension of a work from Estefanel [CCGRID2007].

Break

Revisiting the bicriteria (length,reliability) multiprocessor static scheduling problem

Our starting point is a dependency task graph and an heterogeneous distributed memory target architecture. We revisit the well studied problem of bicriteria (length,reliability) multiprocessor static scheduling of this task graph onto this architecture. Our first criteria remains the static schedule's length: this is crucial to assess the system's real-time property. For our second criteria, we consider the global system failure rate, seen as if the whole system were a single task scheduled onto a single processor, instead of the usual reliability, because it does not depend on the schedule length like the reliability does (due to its computation in the classical reliability model of \SW). Therefore, we control better the replication factor of each individual task of the dependency task graph given as a specification, with respect to the desired failure rate.

To solve this bicriteria optimization problem, we take the failure rate as a constraint, and we minimize the schedule length. We are thus able to produce, for a given application task graph and multiprocessor architecture, a Pareto curve of non-dominated solutions, among which the user can choose the compromise that fits his requirements best.

Reliability and Scheduling on Systems Subject to Failures

We present a bi-objective greedy heuristic for scheduling parallel applications on heterogeneous computing systems. The algorithm which is called BSA (Bi-objective Scheduling Algorithm) takes into account not only the time makespan but also the failure probability of the application. Since it is not usually possible to achieve the two conflicting objectives (performance and reliability) simultaneously, a bi-objective compromise function is introduced. BSA has a low time complexity. Experimental results show the performance of the proposed algorithm.

Discussion