Groupe de travail Graal 2007-2008


Note aux orateurs
Contact et renseignements : Emmanuel Agullo ou Jean-François Pineau
Les groupes de travail Graal ont lieu les jeudi 15h30, soit en amphi B, soit en salle de travail de Gerland.
Le prochain groupe de travail sera lundi 5 mai 2008 à 9h et aura lieu à Lyon 1.

Programme


 
Date : jeudi Orateur Titre
 Jeudi 11 Octobre 2007 15h   Raphaël Bolze, Yves Caniou, Matthieu Gallet (UCBL - LIP, ENS Lyon)  Problématiques d'ordonnancement de graphes de tâches (Workflow Scheduling)
 Mercredi 17 octobre 2007 16h   Osni Marques (Berkeley Lab)  ACTS: A Collection of Robust and High-Performance Software Tools
 25 Octobre 2007   Raphaël Bolze (LIP, ENS Lyon)  Exécution à très grande échelle d'une application bioInformatique sur une grille d'internautes
 8 Novembre 2007   Cédric Tedeschi (LIP, ENS Lyon)  Snap-stabilizing Prefix Tree for Peer-to-peer Systems
  15 Novembre 2007      Journée MAO
  22 Novembre 2007    Bora Ucar(Post-doc, CERFACS, Toulouse)  Models and techniques for parallel sparse matrix computations
  6 Decembre 2007 16h   Veronika Rehn(LIP, ENS Lyon)  Multi-criteria Scheduling of Pipeline Workflows
  31 Janvier 2008      Journée Alpage
  14 Février 2008    Alfredo Buttari  Dense Factorizations on Multicore Architectures
  28 Février 2008    Loris Marchal  Bag of Tasks
 20 Mars 2008    Emmanuel Agullo - Amphi A  Méthodes directes supernodales non symétriques pour la factorisation hors-mémoire (out-of-core) de matrices creuses
 3 Avril 2008      Journée MAO
 Lundi 5 Mai 2008, 9h    Frédéric Vivien  Répétition d'HDR
 22 Mai 2008    Philippe Combes  SystemC
 5 Juin 2008    Mourad Hakem  Sûreté de fonctionnement et ordonnancement (Dependability and Scheduling)



À voir également


Résumés des groupes de travail


 

Workflow Scheduling



Date
11 Octobre 2007

Orateur
Raphaël Bolze, Yves Caniou, Matthieu Gallet

Résumé
Yvessss (remplaçant Jean-Sébastien), Raphaël et Matthieu travaillons tous les 3 sur l'ordonnancement de graphes de tâches sur plates-formes de grille hétérogène. Nous ferons ce groupe de travail à 3. Durant cet exposé, nous ne présenterons pas de résultats, mais le cadre de nos travaux. L'objectif étant de mettre en exergue les similitudes et différences de nos approches pour aboutir sur une discussion ouverte sur nos travaux de recherche. Après une présentation commune des notations et du contexte où nous nous plaçons, nous décrirons chacun nos spécificités. Raphaël exposera ses recherches sur l'ordonnancement de workflows sur des grilles de calcul et l'exemple concret des applications du programme Décrypthon. Matthieu parlera d'ordonnancement en régime permanent sur plates-formes hétérogènes et de méthodes pour maximiser le débit. Quant à Yvessss, il présentera le travail effectué avec Jean-Sébastien sur des heuristiques d'ordonnancement pour worflow conçues pour le modèle GridRPC.


 

ACTS: A Collection of Robust and High-Performance Software Tools



Date
Octobre 2007

Orateur
Osni Marques

Résumé
The development of efficient simulation codes is an expensive process that often requires specialized support and information about the available computational resources and software tools. The development effort is usually augmented by the complexity of the phenomena that can be addressed through computers simulations, along with the increase and evolution of computing resources. The US Department of Energy (DOE) Advanced Computational Software (ACTS) Collection comprises a set of DOE-developed software tools, sometimes in collaboration with other funding agencies, and that aim at simplifying the development of computational sciences applications. The talk will describe the functionalities that the tools provide, categories of problems that the tools can solve, availability, portability, and a number of applications that have benefited from the tools, and issues related to long-term support and maintenance.


 

Exécution à très grande échelle d'une application bioInformatique sur une grille d'internautes



Date
25 Octobre 2007

Orateur
Raphaël Bolze

Résumé
Le 19 Décembre 2006 le projet HCMD (Help Cure Muscular Dystrophy) a été lancé sur la grille de volontaires WorldCommunityGrid supportée par IBM. Il s'agit d'étudier la modélisation des interactions protéine- protéine de protéines dont la structuretridimensionnelle (structure 3D) est connue, en se concentrant sur les protéines qui jouent un rôle dans les maladies neuromusculaires. Pour des structures complexes comme les protéines (les plus petites sont composées de centaines d'atomes), la modélisation par des moyens informatiques des interactions protéine-protéine demande des temps de calcul considérables : estimé à 14 siècles de temps CPU sur un processeur à 2 Ghz. Lors de cette exposé, je commencerai par vous présenter le principe d'assemblage moléculaire (docking). Je vous expliquerai les différentes étapes qui ont jalonnées le lancement du projet, puis je commenterai les actions menées durant les 6 mois d'exécution sur la grille mondiale WCG. Enfin je finirai par une comparaison avec une grille dédiée (type Grid'5000) et quelques projections sur le déroulement de la deuxième phase du projet, prévue en juin 2008.


 

Snap-stabilizing Prefix Tree for Peer-to-peer System



Date
8 novembre 2007

Orateur
Cédric Tedeschi

Résumé
Resource Discovery is a crucial issue in the deployment of computational grids over peer-to-peer platforms. Because they efficiently allow range queries, tries (aka prefix trees) appear to be among promising ways in the design of distributed data structures indexing resources. Self-stabilization is an efficient approach in the design of reliable solutions for dynamic systems. A snap-stabilizing algorithm guarantees that it always behaves according to its specification. In other words, a snap-stabilizing algorithm is also a self-stabilizing algorithm which stabilizes in 0 steps. In this paper, we provide the first snap-stabilizing protocol for trie construction. We use particular tries called Proper Greatest Common Prefix (PGCP) Tree. The proposed algorithm arranges the n label values stored in the tree, in average, in O(h+h') rounds, where h and h' are the initial and final heights of the tree, respectively. In the worst case, the algorithm requires an O(n) extra space on each node, O(n) rounds and O(n^2) actions. However, simulations show that, using relevant data sets, this worst case is far from being reached and confirm the average complexities, making this algorithm efficient in practice.

Transparents
pdf


 

Models and techniques for parallel sparse matrix computations



Date
22 novembre 2007

Orateur
Bora Ucar

Résumé
The talk consists of three parts. In the first part, we will discuss efficient parallelization of sparse matrix-vector multiply operations on distributed memory systems. Then, in the second part, we will investigate a matrix scaling algorithm and its parallelization. Although the scaling algorithm is not based on matrix-vector multiply operations, we will see that it can be parallelized using the techniques discussed in the first part. In the last part, we will briefly summarize an ongoing work at CERFACS. In this work, the scaling algorithm is used to attack a seemingly unrelated problem known as the bipartite matching problem. Bipartite matchings are used in direct solvers, such as MUMPS, and mostly computed sequentially, forming a bottleneck in parallel execution. By this work, we hope to relieve MUMPS of that bottleneck.


 

Multi-criteria Scheduling of Pipeline Workflows



Date
6 décembre 2007

Oratrice
Véronika Rehn

Résumé
Mapping workflow applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline graphs. Several antagonist criteria should be optimized, such as throughput and latency (or a combination). In this talk, we study the complexity of the bi-criteria mapping problem for pipeline graphs on communication homogeneous platforms. In particular, we assess the complexity of the well-known chains-to-chains problem for different-speed processors, which turns out to be NP-hard. We provide several efficient polynomial bi-criteria heuristics, and their relative performance is evaluated through extensive simulations. Furthermore we present the behaviour of our heuristics on an image processing simulation, the JPEG encoder.

Transparents
pdf


 

Dense Factorizations on Multicore Architectures



Date
14 février 2008

Orateur
Alfredo Buttari

Résumé
As multicore systems continue to gain ground in the High Performance Computing world, linear algebra algorithms have to be reformulated or new algorithms have to be developed in order to take advantage of the architectural features on these new processors. Fine grain parallelism becomes a major requirement and introduces the necessity of loose synchronization in the parallel execution of an operation. This paper presents an algorithm for the Cholesky, LU and QR factorization where the operations can be represented as a sequence of small tasks that operate on square blocks of data. These tasks can be dynamically scheduled for execution based on the dependencies among them and on the availability of computational resources. This may result in an out of order execution of the tasks which will completely hide the presence of intrinsically sequential tasks in the factorization. Performance comparisons are presented with the LAPACK algorithms where parallelism can only be exploited at the level of the BLAS operations and vendor implementations.


 

Bag of Taks



Date
28 Février 2008

Orateur
Loris Marchal

Résumé
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.

Transparents
pdf


 

Méthodes directes supernodales non symétriques pour la factorisation hors-mémoire (out-of-core) de matrices creuses



Date
20 Mars 2008

Lieu
Salle 118

Orateur
Emmanuel Agullo

Résumé
Les problèmes de simulation numérique requièrent souvent de résoudre des systèmes linéaires creux. Les méthodes directes sont une approchent robuste mais nécessistant une quantité de mémoire importante. Quand le besoin mémoire est plus important que la mémoire (RAM) disponible de la machine utilisée, les méthodes hors-mémoire (out-of-core) - où les disques sont utilisés pour seconder la mémoire centrale - doivent etre employées. Un accès disque étant lent comparé à un accès mémoire, c'est l'ensemble de l'algorithme de factorisation qui doit souvent etre repensé afin de conserver l'efficacité d'une méthode. Nous allons présenter différentes méthodes supernodales - une classe de méthodes directes particulières - et étudier leur extension hors-mémoire. L'évaluation des méthodes se basera sur différentes métriques, notamment la quantité de traffic induit entre la mémoire et les disques, la localité spatiale des accès disques et le surcout lié aux indirections. Nous retiendrons deux approches, pour lesquelles nous présenterons respectivement un prototype (basé sur le logiciel SuperLU) et une modélisation. Ce travail a été réalisé en collaboration avec Xiaoye S. Li (Lawrence Berkeley National Laboratory, US), auteur de SuperLU, lors d'un séjour de 6 mois à Berkeley


 

On scheduling for distributed heterogeneous platforms



Date
5 Mai 2008

Orateur
Frédéric Vivien

Résumé du mémoire
Ce mémoire a pour objet l'ordonnancement d'applications sur des plates-formes hétérogènes et distribuées, c'est-à-dire le problème de la détermination de où (placement) et de quand (ordonnancement) une application doit être exécutée sur une plate-forme constituée d'un ensemble hétéroclite de ressources: une grappe (cluster) hétérogène, une grappe de grappes, une grille, etc. Nous commençons par passer en revue les différents modèles d'applications et de plates-formes existants, puis les différents objectifs que nous pouvons chercher à atteindre. Nous évoquons ensuite les problèmes que nous pouvons rencontrer lors de la modélisation des applications et des plates-formes, et les perspectives de recherche qui en découlent. Le deuxième chapitre illustre l'impact que les modèles d'applications et de plates-formes peuvent avoir sur notre capacité à résoudre efficacement un problème d'ordonnancement. Le troisième chapitre présente trois travaux prenant en compte les communications dues aux données utilisées en entrée des applications. L'idée sous-jacente à ce chapitre est que, sur ces plates-formes hétérogènes et distribuées, il n'est pas possible de dissocier l'ordonnancement des calculs de la gestion des données et de l'ordonnancement des communications. Le dernier chapitre est consacré à une étude de l'ordonnancement en ligne de tâches divisibles dans le cadre de la minimisation du ralentissement (stretch) subi par les tâches parce que le système ne leur est pas dédié. Dans ce chapitre nous avons donc affaire à des tâches qui sont soumises dynamiquement au cours du temps, et à une fonction objective peu étudiée.


 

SystemC



Date
22 Mai 2008

Orateur
Philippe Combes

Résumé
SystemC has become a very popular language for the modeling of System-On-Chip (SoC) devices. However, due to the ever increasing complexity of SoC designs, the ever longer simulation times affect SoC exploration potential and time-to-market. We investigate the use of parallel computing to exploit the inherent concurrent execution of the hardware components, and thus to speed up the simulation of complex SoC's. A parallel SystemC prototype based on the open source OSCI kernel is introduced and preliminary results are discussed.


 

Sûreté de fonctionnement et ordonnancement(Dependability and Scheduling)



Date
5 Juin 2008

Orateur
Mourad Hakem

Résumé
Les systèmes informatiques temps réel et embarqués sont aujourd?hui omniprésents et concernent un large spectre d?activités. Dans la vie de tous les jours, on en trouve dans le guidage de mobiles, la surveillance des centrales nucléaires, la robotique, le suivi opératoire en milieu médical, le suivi d?informations boursières et même dans les équipements électroménagers. Certains sont à sûreté critique et d?autres moins. Dans ce type de systèmes, la correction des résultats et le respect des échéances des tâches composant les applications déployées est une condition nécessaire mais pas suffisante pour garantir le bon fonctionnement. En effet, la présence de fautes matérielles ou logiciels est inévitable. Donc, le recours aux stratégies de fiabilité et de tolérance aux pannes est vitale pour la conception de systèmes sûrs de fonctionnement. Dans notre contexte, les actions d?un système sont des tâches avec des contraintes de précédence et l?organisation de leur exécution par les processeurs du système (séquencement, entrelacement, parallélisme) est assurée par un processus d?ordonnancement. Dans le cadre de ce groupe de travail, je parlerai des algorithmes d?ordonnancement bi-critères (fautes & latence), et multi-critères (fiabilité, fautes & latence). Dans un premier temps on considérera le modèle classique (macro-dataflow), puis on s'intéressera à un modèle plus réaliste pour les communications (modèle 1-port). Nos approches sont basées sur un mécanisme de compensation (réplication active) pour masquer des pannes de type silence sur défaillance (fail-stop/fail-silent).



Responsable : Emmanuel Agullo