March 22, 2012, 10h30, salle de conseil du LIP 3 94 N.

Frédéric Vivien: Intérêts relatifs des protocoles de checkpoint coordonnés et hiérarchiques, bloquants et non bloquants.

Dans cet exposé nous présenterons une analyse au premier ordre de la performance des protocoles de checkpoint coordonnés et hiérarchiques, qu'ils soient bloquants ou non-bloquants. Les protocoles de checkpoints hiérarchiques ont été élaborés pour répondre aux faiblesses des protocoles coordonnés. Ces protocoles permettent-ils d'obtenir de meilleures performances ? Dans quels cas ?

March 29, 2012, 10h30, salle de conseil du LIP 3 94 N.

Guillaume Aupy: Speed scaling is not as easy as you think: Approximation algorithms for linear chains and load balancing problem

We consider the problem of speed-scaling to minimize the energy consumption of a schedule. We consider two different cases, the case where the precedence constraints have the form of a linear chain, and the case where there are no precedence constraints (also known as load balancing problem). The main contribution of this work is the fact that we not only try to enforce a deadline bound, but we take into account the fact that speed-scaling has negative effect on the reliability of a schedule. In order to take this into account, we enforce a precribed bound on the reliability of our schedule using techniques such as replication and re-execution. Our results are the first approximation algorithms for this natural class of speed-scaling problems.

March 1, 2012, 10h30, salle de conseil du LIP 3 94 N.

Bora Uçar: Partitioning problems in trees

We will investigate two partitioning problems on trees. We will discuss their computational complexity, an approximation algorithm for one of them and an exact algorithm for the other. We will also discuss hypergraph models for the two problems where the standard hypergraph partitioning problem encode exactly the objective and constraints of the partitioning problems.

February 23, 2012, 10h30, salle de conseil du LIP 3 94 N.

Fanny Dufossé: AV

AV

February 9, 2012, 10h30, salle de conseil du LIP 3 94 N.

Fabrice Rastello: AV

AV

February 2, 2012, 10h30, salle de conseil du LIP 3 94 N.

Yves Robert: Replication @ exascale

Exascale machines will have a high failure rate. Checkpoint/recovery is doomed to fail at some point. Can replication help? In this talk we survey two recent replication techniques and assess their usefulness for exascale plaftorms. In passing, we revisit the birthday problem!

January 26, 2012, 10h30, salle de conseil du LIP 3 94 N.

Amina Guermouche: Un Nouveau Protocole de Tolérance aux Faute Pour les Applications MPI du Calcul Haute Performance

Abstract: High performance computing will probably reach exascale in this decade. At such a scale, the mean time between failures is expected to be a few hours. Existing fault tolerance protocols will no longer be suitable: Coordinated checkointing protocols force all processes to restart and message logging protocols log all messages and their determinants. In order to overcome these limits, one can combine these protocols and use them on groups of processes. Many protocols based this idea already exist in the litterature. In this talk, we will present a new hierarchical protocol that logs only message payload unlike all existing hierarchical protocols. We first present a study on MPI applications execution model. The study shows that many MPI applications are "send-deterministic". Then we briefly present applications communication patterns for group creation. Finally we present the protocol principles and some performance evaluations.

January 12, 2012, 10h30, salle B2.

Loris Marchal: Fair allocations of multiple resources

Dans cet exposé, après avoir brièvement rappelé quelques résultats classiques sur l'allocation équitable d'un seul type de ressource (MaxMin Fairness, etc.), nous présenterons deux articles récents qui s'intéressent à l'allocation équitable dans le cas de plusieurs types de ressources. Nous verrons comment il est possible d'étendre la notion d'équité lorsque les utilisateurs requièrent différentes fractions de différentes ressources, et comment calculer une telle allocation équitable. In this talk, we will first briefly recall classical results on fair allocation for a single type of resource (MaxMin Fairness, etc.). Then we will present two recent articles which focus on the fair allocation of multiple types of resources. We will show how to define fairness when several users request different fractions of different resources, and how to compute such a fair allocation.

December 15, 2011, 15h30, salle 115.

Johannes Langguth: Matching Algorithms in Combinatorial Scientific Computing

We present a parallel algorithm for perfect matching based on the push relabel algorithm and discuss the underlying sequential concepts, the challenges involved in the parallelization and its applications in scientific computing.

December 5, 2011, 15h30, salle B1.

Louis-Claude Canon: Scheduling Associative Reductions with Overlapping Transfers and Computation

Increasing the performance of HPC and could environments involves to optimize the reduction phase, which is present in many applications. This optimization problem arises in at least two contexts: the MPI_Reduce collective function that allows to combine several arrays by performing a pairwise reduction operation on every arrays; and, the Reduce part of MapReduce applications, where a single result is generated from several inputs. By assuming the associativity of the reduction operation, it is possible to determine a spanning tree that schedules data transfers and reduction operations. Two algorithms are proposed for the cases where the number of reducers or the number of concurrent transfers is bounded. When there is no limitation, two specific optimal spanning trees are also characterized for specific transfer and computation costs.>

October 4, 2011, 14h00, salle 115.

Guillaume Joslin: MUMPS (MUltifrontal Massively Parallel Solver)

General presentation of the MUMPS solver and of Guillaume Joslin's work in the project.

September 13, 2011, 10h00, salle 115.

Mohamed Wissam Sid Lakhdar

The use of multicore architechtures on multifrontal methods

August 30, 2011, 10h00, salle 115.

Fanny Dufosse

Scheduling for Reliability : Complexity and Algorithms

June 15, 2011, 11h00, salle 115.

Marin Bougeret: Using oracles for the design of efficient approximation algorithms.

We are interested here in oracle techniques for the design of approximation algorithms. Following the classical denition, an oracle is a black box capable of answering correctly and instantaneously any question. Several classical PTAS design techniques can be expressed using oracle formalism (by allowing the algorithm to \guess" some values during the computation). Our objective in this work is to point out the interest of oracle techniques, beyond the design of PTAS. Indeed, questions to the oracle (i.e. guessed values) leading to non polynomial algorithms must also be considered, as the complexity may be exponential, but in a parameter that is supposed to be "small". Moreover, we aim at showing how it is possible to "degenerate" questions asked to the oracle to derive fast implementations of these interactive algorithms. These ideas will be illustrated on the classical makespan minimization on uniform machines problem (Q||Cmax).

May 10, 2011, 09h30, salle 115.

Paul Renaud-Goud: Power-aware replica placement and update strategies in tree networks

This paper deals with optimal strategies to place replicas in tree networks, with the double objective to minimize the total cost of the servers, and/or to optimize power consumption. The client requests are known beforehand, and some servers are assumed to pre-exist in the tree. Without power consumption constraints, the total cost is an arbitrary function of the number of existing servers that are reused, and of the number of new servers. Whenever creating and operating a new server has higher cost than reusing an existing one (which is a very natural assumption), cost optimal strategies have to trade-off between reusing resources and load-balancing requests on new servers. We provide an optimal dynamic programming algorithm that returns the optimal cost, thereby extending known results without pre-existing servers. With power consumption constraints, we assume that servers operate under a set of M different modes depending upon the number of requests that they have to process. In practice M is a small number, typically 2 or 3, depending upon the number of allowed voltages. Power consumption includes a static part, proportional to the total number of servers, and a dynamic part, proportional to a constant exponent of the server mode, which depends upon the model for power. The cost function becomes a more complicated function that takes into account reuse and creation as before, but also upgrading or downgrading an existing server from one mode to another. We show that with an arbitrary number of modes, the power minimization problem is NP-complete, even without cost constraint, and without static power. Still, we provide an optimal dynamic programming algorithm that returns the minimal power, given a threshold value on the total cost; it has exponential complexity in the number of modes M, and its practical usefulness is limited to small values of M. Still, experiments conducted with this algorithm show that it can process large trees in reasonable time, despite its worst-case complexity.

May 3, 2011, 09h30, salle 115.

Guillaume Aupy: Reclaiming the energy of a schedule, models and algorithms

We consider a task graph to be executed on a set of processors. We assume that the mapping is given, say by an ordered list of tasks to execute on each processor, and we aim at optimizing the energy consumption while enforcing a prescribed bound on the execution time. While it is not possible to change the allocation of a task, it is possible to change its speed. We study the complexity of the problem for different models: continuous speeds, discrete modes, distributed either arbitrarily or regularly, and VDD-hopping.

April 19, 2011, 09h30, salle 115.

Mathias Jacquelin: Comparing archival policies for BlueWaters

This paper introduces two new tape archival policies that can improve tape archive performance in certain regimes, compared to the classical RAIT (\emph{Redundant Array of Independent Tapes}) policy. The first policy, PARALLEL, still requires as many parallel tape drives as RAIT but pre-computes large data stripes that are written contiguously on tapes to increase write/read performance. The second policy, VERTICAL, writes contiguous data into a single tape, while updating error correcting information on the fly and delaying its archival until enough data has been archived. This second approach reduces the number of tape drives used for every user request to one. The performance of the three RAIT, PARALLEL and VERTICAL policies is assessed through extensive simulations, using a hardware configuration and a distribution of I/O requests similar to these expected on the BLUE WATERS system. These simulations show that VERTICAL is the most suitable policy for small files, whereas PARALLEL must be used for files larger than 1GB. We also demonstrate that RAIT never outperforms both proposed policies, and that a heterogeneous policies mixing VERTICAL and PARALLEL performs 10 times better than any other policy.

transparents [pdf] de la présentation

April 12, 2011, 09h30, salle 115.

Yves Robert

Tiled QR algorithms (on multicore platforms)

April 5, 2011, 09h30, salle 115.

Mark L. Stillwell and Bora Uçar

Bora Uçar: Randomized algorithms for the bipartite (cardinality) matching problem.
Mark L. Stillwell: Dynamic Fractional Resource Scheduling

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