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.
| 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. |
| 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. |
| 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. |
| 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 |  |
| 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. |
| 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 | |
| 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. |
| 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 | |
| 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 |
| 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. |
| 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. |
| 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 |