Jeudi 14 octobre 2010, 10h15, salle 117.

Marin Bougeret: Systèmes interactifs pour la résolution des problèmes complexes. Application en optimisation combinatoire, planification et ordonnancement

Cette thèse concerne l'utilisation de l'interaction entre un algorithme et un expert, typiquement pour la résolution de problèmes d'optimisations NP hard. Plusieurs définitions de l'expert sont possibles. L'objectif étant d'obtenir des algorithmes dont les performances sont garanties, ce travail est centré sur les interactions avec un expert de type "oracle", plutôt que "humain". Ainsi, on s'intéresse à des compromis entre performance, coût (typiquement temps d'exécution), et quantité d'information donnée par l'oracle. Le premier objectif de cette thèse est de comprendre quel est l'état de l'art des différentes techniques interactives dans différents domaines (algorithmique distribuée et online, complexité, optimisation combinatoire). Le second objectif est centré sur l'optimisation combinatoire, et plus particulièrement les problèmes d'ordonnancement et d'empaquetage. Nous proposons un formalisme interactif pour le contexte des problèmes d'optimisations (offline). Le but est de montrer en quoi ce formalisme facilite la conception d'algorithmes d'approximation, en le situant par rapport aux techniques classiques de conceptions (tout particulièrement de schémas d'approximation), et l'utilisant pour fournir de nouveaux résultats sur des problèmes d'ordonnancement et d'empaquetage. Nous avons principalement abordé deux problèmes : le "discrete Resource Sharing Scheduling Problem (dRSSP)" et le problème du "Multiple Strip Packing" (MSP). Le dRSSP est un problème d'hybridation d'algorithmes. Etant donné un ensemble d'algorithmes (appelé un "portfolio"), un nombre fini de ressources (des processeurs par exemple), et un ensemble représentatif d'instances (appelé "benchmark"), le but est de distribué ces ressources aux algorithmes afin de minimiser le temps nécessaire à la résolution de toutes les instances du benchmark, en exécutant les algorithmes en parallèle selon le modèle dit du "space sharing" . Nous avons étudié l'impact de plusieurs questions à poser à l'oracle, ainsi que comment communiquer efficacement avec ce dernier (signifiant que la réponse de l'oracle est courte), aboutissant à plusieurs schémas d'approximation. Le MSP est une extension du problème célèbre du "Strip Packing" consistant à placer des rectangles dans un nombre fixé de boîtes, en minimisant la hauteur atteinte. Nous avons fourni plusieurs algorithmes/schémas d'approximation pour différentes variantes de ce problème, dans lesquelles les boîtes ont des largeurs égales/différentes, ou les rectangles doivent être placés de façon "continue" ou non (correspondant alors à un problème classique d'ordonnancement de tâches parallèles). D'une manière générale l'utilisation de l'interactivité permet d'isoler la difficulté des problèmes, et donc de les étudier différemment.

Lundi 31 mai 2010, 15h00, amphi B.

H.J. Siegel: Stochastic Robustness Metric and its Use for Static Resource Allocations in Parallel Computing Systems

What does it mean for a computer system to be "robust"? How can robustness be described? How does one determine if a claim of robustness is true? How can one decide which of two systems is more robust? Parallel computing systems are often heterogeneous mixtures of machines, used to execute collections of tasks with diverse computational requirements. A critical research problem is how to allocate resources to tasks to optimize some performance objective. However, systems frequently have degraded performance due to uncertainties, such as inaccurate estimates of actual workload parameters. It is important for system performance to be robust against uncertainty. To accomplish this, we present a stochastic model for deriving the robustness of a resource allocation. This model assumes that stochastic (experiential) information is available for a parameter whose actual values are uncertain. The robustness of a resource allocation is quantified as the probability that a user-specified level of system performance can be met. We show how to use this stochastic model to evaluate the robustness of resource assignments and to design resource management heuristics that produce robust allocations. To compare heuristics, we simulate operating on periodically updated data sets in a heterogeneous cluster-based radar data processing center. The stochastic robustness analysis approach can be applied to a variety of computing and communication system environments, including cluster, grid, Internet, cloud, embedded, multicore, content distribution networks, wireless networks, and sensor networks. Furthermore, the robustness model is generally applicable to design problems throughout various scientific and engineering fields.

Mercredi 26 mai 2010, 14h, amphi B.

Abdou Guermouche: Minimisation de la mémoire vs. minimisation du volume d'E/S dans les méthodes de factorisation de matrices creuses.

Les méthodes directes de résolution de systèmes linéaires creux sont au coeur d'un grand nombre d'applications de simulation numérique. Bien que très robustes numériquement, ces méthodes sont connues pour être gourmandes en mémoire. Dans cet exposé, nous nous intéresserons, dans un premier temps, à des approches de minimisation de la mémoire. Ces algorithmes sont basés sur le calcul d'un parcours particulier du graphe de dépendance des tâches (qui dans notre cas est un arbre). Ainsi, nous présenterons différentes approches permettant d'obtenir une occupation mémoire optimale. Puis, Dans une deuxième étape, nous nous placerons dans le contexte out-of-core dans lequel les disques sont utilisés pour seconder la mémoire. Dans ce nouveau cadre, la métrique critique pour l'obtention de bonnes performances est le volume d'entrées/sorties. Ainsi, nous présenterons un résultat peu intuitif montrant que la minimisation du volume d'entrées/sorties est différente de la minimisation de la mémoire dans notre contexte. Enfin, nous présenterons un algorithme optimal pour la minimisation du volume d'entrées/sorties.

transparents [pdf] de la présentation

Mercredi 17 mai 2010, 14h30, salle B1.

Mikaël Rabie: Optimisation du travail dans un système soumis à des pannes

Pour pouvoir planifier l'exécution de calcul sur des processeurs, on a besoin de modéliser le matériel. En plus de la rapidité de calcul, et de communication, il faut savoir prendre en compte la fiabilité du support. En effet, tout processeur, comme tout logiciel, a une probabilité non nulle de tomber en panne avant la fin de l'exécution d'un travail donné. L'objectif devient alors de minimiser le temps perdu à cause des pannes. C'est pourquoi on décide d'ajouter au travail à faire des sauvegardes (à des dates quelconques ou régulières), afin de permettre des reprise sur pannes qui ne nécessitent pas de redémarrer le travail du début.
Le but de ce stage est de regarder comment répartir les sauvegardes pour optimiser le temps de travail effectif par rapport à celui demandé. Pour cela, différentes méthodes de calculs ont été utilisées, en passant du théorème de Wald à la récursion. De plus, une approche sur la duplication d'un même travail a été explorée.

Mercredi 7 avril 2010, 14h, salle 116.

Matthieu Gallet: Calcul du débit d'applications linéaires probabilistes répliquées

Nous étudions le calcul du débit d'applications probabilistes dont le graphe de dépendance est une chaîne. On considère ainsi une application déployée sur une plate-forme complètement hétérogène, de telle façon que si un processeur ne traite qu'un type de tâches, une même tâche peut être traitée par plusieurs processeurs. De plus, les temps de calcul et de communication sont modélisés par un ensemble de variables aléatoires indépendantes et identiquement distribuées. Comment déterminer le débit du système, c'est-à-dire le nombre d'instances traitées par unité de temps ? Si le problème est simple quand les tâches ne sont pas répliquées, il est beaucoup plus difficile quand elles le sont. La première contribution est de donner une méthode générale pour déterminer le débit quand les variables aléatoires suivent des lois exponentielles, mais cette méthode a une complexité exponentielle. Si la plate-forme permet le recouvrement des calculs par les communications et que celles-ci sont homogènes, nous donnons une méthode en temps polynomial. La seconde contribution montre que le débit du système peut-être borné facilement lorsque toutes les variables aléatoires sont IID et NBUE: il est compris entre le cas exponentiel et le cas déterministe.

transparents [pdf] de la présentation

Mercredi 31 mars 2010, 14h, salle 116.

Paul Renaud-Goud: Performance and energy optimization of concurrent pipelined applications

In this talk, we study the problem of finding optimal mappings for several independent but concurrent workflow applications, in order to optimize performance-related criteria together with energy consumption. Each application consists in a linear chain graph with several stages, and processes successive data sets in pipeline mode, from the first to the last stage. We study the problem complexity on different target execution platforms, ranking from fully homogeneous platforms to fully heterogeneous ones. The goal is to select an execution speed for each processor, and then to assign stages to processors, with the aim of optimizing several concurrent optimization criteria. There is a clear trade-off to reach, since running faster and/or more processors leads to better performance, but the energy consumption is then very high. Energy savings can be achieved at the price of a lower performance, by reducing processor speeds or enrolling fewer resources. We consider two mapping strategies: in one-to-one mappings, a processor is assigned a single stage, while in interval mappings, a processor may process an interval of consecutive stages of the same application. For both mapping strategies and all platform types, we establish the complexity of several multi-criteria optimization problems, whose objective functions combine period, latency and energy criteria. In particular, we exhibit cases where the problem is NP-hard with concurrent applications, while it can be solved in polynomial time for a single application. Also, we demonstrate the difficulty of performance/energy trade-offs by proving that the tri-criteria problem is NP-hard, even with a single application on a fully homogeneous platform.

Mercredi 24 mars 2010, 14h30, salle 117.

Erik Saule: Load Balancing of Spatially Located Computation - the One Dimensional Case.

Particle in Cell simulation, raycasting algorithms, sparse matrices operations are spatially located computations. When distributing such computation, it is important take into account the load balance of the processors but also to keep the amount of communication reasonable. In this talk, we focus on the one dimension case (also known as chain-on-chain partitioning). We mainly review existing optimal and heuristic techniques and present the performance of those algorithms on random data sets and sparse matrices.

slides [pdf] of the presentation

Jeudi 26 Novembre 2009, 14h, salle 117.

Yves Robert: Checkpointing, or not ?

Jeudi 19 Novembre 2009, salle 117.

Jean-Marc Nicod: Practical Steady-State Scheduling for Tree-Shaped Task Graphs

In this work, we focus on the problem of scheduling a collection of similar task graphs on a heterogeneous platform, when the task graph is a tree. We rely on steady-state scheduling techniques, and try to optimize the throughput of the system. Contrarily to previous studies, we concentrate on practical aspects of steady-state scheduling, when dealing with a collection (or batch) of limited size. We focus here on two optimizations. The first one consists in reducing the processing time of each task graph, thus making steady-state scheduling applicable to smaller batches. The second one consists in degrading a little the optimal-throughput solution to get a simpler solution, more efficient on small batches. We present our optimizations in details, and show that they both help to overcome the limitation of steady-state scheduling: our simulations show that we are able to reach a better efficiency on small batches, to reduce the size of the buffers, and to significantly decrease the processing time of a single task graph (latency).

slides [pdf] of the presentation

Vendredi 13 Novembre 2009, salle 115.

Frédéric Vivien: Ordonnancement de sac de tâches

Nous nous sommes intéressés à l'ordonnancement de sacs de tâches indépendantes sur une plate-forme maître-esclave. Contrairement aux études précédentes, nous n'avons pas supposé que les tâches d'un même sac avaient exactement les mêmes caractéristiques. Nous avons seulement supposé qu'il existait une distribution décrivant le volume de calcul requis par les différentes tâches, et une distribution pour le volume de communication, mais que ces distributions nous étaient inconnues. Dans ces conditions, nous nous demandions si les approches statiques obtenaient toujours des meilleurs résultats que les approches purement dynamique. Nous avons proposé un schéma d'approximation pour le cas offline. Pour le cas online non-clairvoyant, nous avons montré qu'une solution « à la demande » était asymptotiquement optimale si les calculs (respectivement les communications) dominaient significativement les communications (resp. les calculs). Quand les temps cumulés de calcul et de communication sont comparables, nous avons montré via simulation que les approches statiques pouvaient battre les approches systèmes.

slides [pdf] of the presentation

Jeudi 22 Octobre 2009.

Bora Uçar: Partitioning regular meshes for minimizing the total communication volume.

We investigate one-dimensional partitioning of sparse matrices that arise after the discretization of square domains with the five-point stencil. The objective is to minimize the total volume of communication and to have balance among the processors, when the partition is used to parallelize sparse matrix-vector multiplies. The problem is known to be equivalent to the hypergraph partitioning problem. This later problem is NP-complete and hence heuristic algorithms are used. We propose a method that works on the mesh (the geometric coordinates) to partition the associated matrix. The method obtains perfect load balance and achieves very good total communication volume. In general, a hypergraph partitioning-based method obtains results that are about 1.16 times of the results of the proposed method. At the time being, we do not have any optimality results, but we believe that the method can be optimal as it has closed form formulas for the total volume of communication. We also try to generalize the partitioning method to 9-point stencil matrices and also to 3D domains.

slides [pdf] of the presentation

Jeudi 15 Octobre 2009.

Matthieu Gallet: Ordonnancement de graphes de tâches sur plates-formes hétérogènes.

Dans cette présentation, je parlerai d'ordonnancement de graphes de tâches sur plates-formes hétérogènes. Je présenterai en détail trois problèmes différents : Le premier concerne l'ordonnancement en régime permanent de nombreuses instances d'un graphe de tâches donné, en utilisant la même allocation pour tous. Même si le problème est NP-complet, une solution optimale (nécessitant un temps de calcul exponentiel) sera donnée, ainsi que plusieurs heuristiques. Des résultats expérimentaux seront également donnés pour comparer les efficacités relatives de ces méthodes. Ensuite, je m'attacherai à l'ordonnancement de multiples instances de graphes de tâches sur un processeur Cell, toujours en utilisant des méthodes de régime permanent. Je décrirai un modèle théorique de ce processeur multi-coeur hétérogène puis une méthode pour déterminer un ordonnancement en régime permanent optimal, ainsi que plusieurs simulations montrant son efficacité face à une simple heuristique gloutonne. Le dernier problème de cette présentation sera à propos de graphes linéaires. On suppose que le placement est connu, que certaines tâches sont répliquées sur plusieurs processeurs et que les différentes instances de ces tâches sont distribuées à leurs processeurs en respectant un tourniquet. Dans ce cas, simplement calculer le débit est difficile, et une méthode modélisant le système par un graphe d'événements temporisé sera utilisé.

slides [pdf] of the presentation

Jeudi 8 Octobre 2009.

Mark Stillwell:Dynamic Fractional Resource Scheduling

We propose a novel approach for sharing homogeneous cluster computing platforms among competing jobs. Its key feature is the use of virtual machine technology for sharing resources in a precise and controlled manner so that performance, fairness, and cluster utilization are optimized. We describe and justify our approach and propose several job scheduling algorithms. We present results obtained in simulations for synthetic and real-world High Performance Computing (HPC) workloads, in which we compare our proposed algorithms with standard batch scheduling algorithms. We find that our approach provides drastic performance improvements over batch scheduling. In particular, we identify a few promising algorithms that perform well across most experimental scenarios. Our results demonstrate that virtualization technology coupled with lightweight scheduling strategies enables dramatic improvements for scheduling HPC workloads on homogeneous clusters.

slides [pdf] of the presentation