Séminaires 2006-2007
Les séminaires ont lieu tous les jeudi à 15h00 au laboratoire ID. Le responsable de l'organisation des séminaires est Arnaud Legrand. Certains membres du Laboratoire ID participent également au Séminaire Grenoblois d'Évaluation de Performances. On peut également noter l'existence d'un certain nombre de groupes de travail: MESCAL, PERF, GAMES.
Les listes des anciens séminaires sont là (2003-2004, 2004-2005 2005-2006).
24/05/2007 : George Da Costa : Gestion de ressources Peer to peer pour les Grilles
|
George Da Costa
(???)
Résumé : Le passage à l'échelle est un problème fondamental pour les systèmes d'information. Dans le cas particulier de la gestion de ressources des Grilles, d'autres problèmes se posent. Ainsi autant la difficulté d'administration que le besoin de fraîcheur des informations s'ajoutent aux problème du passage à l'échelle. Je vais présenter un nouvel algorithme permettant d'améliorer les approches actuelles, basé sur des techniques Peer to Peer : Multi-set DHT. Cet algorithme a été évalué en utilisant un modèle, un simulateur ainsi que grâce à une expérimentation sur PlanetLab. Je présenterai aussi une première étude de la charge sur la grille européenne EGEE qui permettra à terme d'évaluer de manière plus réaliste ce type de systèmes. |
25/04/2007 : Laurent Daynès, Sun Microsystems : Scalable, multitasking and isolated JVM
|
Laurent Daynès, Sun Microsystems
(http://sardes.inrialpes.fr/past-events/summer-schools/past-summer-schools.html)
Résumé : The negative effects of large increments of memory required by each additional applications, long startup latencies, loss of results of expensive runtime compilation and transformation of code across programs, all hurt the Java Platform's ability to compete with more nimble and efficient language systems and cast doubt on the prospects for scalability and the scope of applicability of the Java platform. The need for freedom from inter application interference remains high as users of Java mix ever more varied applications in their cell phones, on their desktops and within their servers. Ad hoc script and native code mechanisms for controlling and load balancing multiple Java virtual machines in server settings hurt portability, maintainability and robustness. There is a need for simple yet effective control mechanisms that are tightly focused on Java applications instead of their implementation artifacts. These observations led to the design of the Multi-tasking virtual machine (MVM) and of the Application Isolation API (JSR 121). In this talk I will briefly present MVM and the Application Isolation API, before diving into details of the anatomy of Java virtual machine implementations and analyze the reason for the issues plaguing today's implementation with poor startup time, poor memory usage and expensive runtime overhead. I will then present the various solution that were investigated to address these issues (sharing across JVM processes, sharing via encoding into standard shared libraries, multi-tasking in a single address space), and discuss, based on qualitative and quantitative date, why we believe a multi-tasking approach to virtual machine remains one of the most appropriate answer today. I will then quickly go over the additional challenges that need to be addressed to make a multi-tasking virtual machine a valid alternative to today's industrial-strength implementation of the JVM (e.g., native method support, multi-user support, scalable garbage collection for multi-tasking). |
19/04/2007 : Clément Ménier : Thèse: Système de vision temps réel pour les interactions
|
Clément Ménier
(???)
Résumé : Nous nous intéressons à l'acquisition temps réel d'informations tridimensionnelles sur une scène à partir de plusieurs caméras dans le contexte des applications interactives. Nous proposons un système de vision complet allant de l'acquisition des images à la modélisation des formes et du mouvement de l'utilisateur. La distribution des tâches sur une grappe de PC, et en particulier la parallélisation de plusieurs algorithmes d'extraction de la géométrie de la scène, permet un fonctionnement temps-réel avec une faible latence. De nombreuses applications sont développées et valident la mise en oeuvre réalisée de ce système. Une approche nouvelle de la modélisation du mouvement est aussi proposée. Celle-ci permet de suivre et d'identifier les membres de l'utilisateur sans connaissance a priori sur la forme de ce dernier. |
16/04/2007 : Gilles Muller : Documenting and Automating Collateral Evolutions in Linux Device Drivers
|
Gilles Muller
(http://www.emn.fr/x-info/gmuller/)
Résumé : In recent years, the internal libraries of Linux have been evolving rapidly, to address new requirements and improve performance. These evolutions, however, have been found to entail a massive problem of collateral evolution in Linux device drivers: for every change that affects an API, all dependent drivers must be updated accordingly. Currently,collateral evolutions in Linux are done ``nearly'' manually. The large number of Linux drivers, however, implies that this approach is time-consuming and unreliable, leading to subtle errors when modifications are not done consistently. In this talk, we present an automatic program transformation tool, Coccinelle, for documenting and automating device driver collateral evolutions. This tool provides a WYSIWYG approach, based on a language inspired by the notation found in patch files. The tool also features a C parser that is tolerant of C preprocessing directives, techniques to abstract away from details of coding style, and feedback to the user about partial matches of the transformation rules against the driver code. We have evaluated our approach on over 48 collateral evolutions selected to illustrate the representative situations in term of automation and documentation. On this test suite, Coccinelle updates on average 90% of the drivers in the same way as was done by the human programmer. In the remaining cases, the user is alerted either to a parsing problem or to a partial match of the rule against the code, signaling to him that the code must be considered manually. We have additionally identified a number of drivers where the maintainer made some mistake in performing the collateral evolution, but Coccinelle transforms the code correctly. |
05/04/2007 : Nicolas Bonneau : Non-Atomic Games for CDMA systems
|
Nicolas Bonneau
(http://www-sop.inria.fr/maestro/personnel/Nicolas.Bonneau/)
Résumé : The performance of an uplink CDMA system is analyzed in the context of frequency selective fading channels. Using game theoretic tools, a useful framework is provided in order to determine the optimal power allocation when users know only their own channel (while perfect channel state information is assumed at the base station). We consider the realistic case of frequency selective channels. This scenario illustrates the case of decentralized schemes and aims at reducing the downlink signaling overhead. We derive simple expressions for the non-cooperative Nash equilibrium as the number of mobiles becomes large. To that end we combine two asymptotic methodologies. The first is asymptotic random matrix theory which allows us to obtain explicit expressions for the impact of all other mobiles on any given tagged mobile. The second is the theory of non-atomic games along with the Wardrop equilibrium concept which allows us to compute good approximations of the Nash equilibrium as the number of mobiles grow. |
29/03/2007 : Guillaume Pierre, Vrije University, Amsterdam : Scalable Hosting of Internet Services
|
Guillaume Pierre, Vrije University, Amsterdam
(http://sardes.inrialpes.fr/past-events/summer-schools/past-summer-schools.html)
Résumé : Nowadays, most Web sites a structured as Web applications, which dynamically generate content based on a client request's parameters and the results of queries issued to an underlying database. Traditional page caching/replication techniques cannot efficiently host such web sites, so new techniques are necessary. My talk will review a number of research efforts we have conducted in this direction. GlobeCBC allows to cache the results of database queries at the edge servers, while GlobeDB allows to split a database into individual fragments that can be replicated independently. I will then present in more detail GlobeTP, which addresses the throughput bottleneck that these two systems experience at their origin database. I will then show how one may dynamically select the best set of techniques to suit one's application workload. |
15/03/2007 : Urtzi Ayesta : Optimal scheduling discipline in a single-server queue with Pareto type service times
|
Urtzi Ayesta
(http://www.laas.fr/~urtzi/)
Get the slides Résumé : We consider the mean delay optimization in an M/G/1 queue for some Pareto type service time distributions. If the Pareto distribution is defined in such a way that all positive values are allowed, then the distribution has a decreasing hazard rate, which implies that the FB discipline is optimal. However, if it is defined starting from a strictly positive value, the hazard rate is no longer monotone. In this paper we prove that, not only for this but for a whole class of service time distributions, the optimal discipline is a combination of FCFS and Foreground-Background (FB) disciplines, which gives full priority to the jobs with attained service less than some fixed threshold $ heta^*$. These priority jobs are served in the FCFS manner. If there are no jobs with attained service less than $ heta^*$, the full priority is given to the job with least amount of attained service. In our proof, we utilize the index approach developed by Gittins and Klimov. In addition to the ordinary Pareto type distributions with an infinite support, we also discuss the structure of the optimal scheduling discipline when dealing with bounded Pareto distribution with a finite support. Joint work with: Samuli Aalto (Helsinki University of Technology). |
8/03/2007 : Derrick Kondo : Towards Soft Real-Time Applications on Enterprise Desktop Grids
|
Derrick Kondo
(http://www.lri.fr/~dkondo/)
Get the slides Résumé : Desktop grids use the idle cycles of desktop PC's to provide huge computational power at low cost. However, because the underlying desktop computing resources are volatile, achieving performance guarantees such as task completion rate is difficult. We will present our investigation of the use of buffering to ensure task completion rates, which is essential for soft real-time applications. In particular, we develop a model of task completion rate as a function of buffer size. We instantiate this model using parameters derived from two enterprise desktop grid data sets, evaluate the model via trace-driven simulation, and show how this model can be used to ensure application task completion rates on enterprise desktop grid systems. |
1/03/2007 : Olivier Aumage : NewMadeleine - Ordonnancement de requêtes sur réseaux hautes performances
|
Olivier Aumage
(http://dept-info.labri.fr/~aumage/)
Get the slides Résumé : RUNTIME élabore depuis environ un an une nouvelle architecture de communication pour réseaux rapides nommée NewMadeleine. Sa principale originalité réside dans son moteur d'optimisation des transferts de données qui, tout en exploitation les informations fournies par l'interface (dépendances entre segments, contraintes temporelles), permet d'appliquer dynamiquement des stratégies d'ordonnancement et d'optimisation génériques. La bibliothèque assure une progression des communications décoréllée de l'application, ce qui lui permet de déclencher les optimisations just-in-time, en fonction de l'activité des cartes réseau. Entre chaque paire de processus, les optimisations ont une portée globale aux flux de données, quel que soit le nombre de canaux de communications utilisés, ce qui permet des optimisations opportunistes et agressives. Ce séminaire sera donc l'occasion de présenter NewMadeleine et les travaux connexes en cours et à venir. |
15/02/2007 : Sara Alouf : Performance Analysis of Peer-to-Peer Storage Systems
|
Sara Alouf
(http://www-sop.inria.fr/maestro/personnel/Sara.Alouf/moi.html)
Résumé : In this talk, we will evaluate and compare the performance of two schemes for recovering lost data in a peer-to-peer (P2P) storage systems. The first scheme is centralized and relies on a server that recovers multiple losses at once, whereas the second one is distributed. By representing the state of each scheme by an absorbing Markov chain, we are able to compute their performance in terms of the delivered data lifetime and data availability. Numerical computations are provided to better illustrate the impact of each system parameter on the performance. Depending on the context considered, we provide guidelines on how to tune the system parameters in order to provide a desired data lifetime. |
08/02/2007 : Anne-Marie Kermarrec : Build One, Get One Free: Leveraging the Coexistence of Multiple P2P Overlay Networks
|
Anne-Marie Kermarrec
(http://www.irisa.fr/asap/Members/akermarrec/anne-marie-kermarrec)
Get the slides Résumé : Many different P2P overlay networks providing various functionalities, targeting specific applications, have been proposed in the past five years. It is now reasonable to consider that multiple overlays may be deployed over a large set of nodes so that the most appropriate overlay might be chosen depending on the application. A physical peer may then host several instances of logical peers belonging to different overlay networks. In this paper, we show that the co-existence of a structured P2P overlay and an unstructured one may be leveraged so that, by building one, the other is automatically constructed as well. More specifically, we show that the randomness provided by an unstructured gossip-based overlay can be used to build the routing tables of a structured P2P overlay and the randomness resulting by the numerical proximity links in the structured networks provides the random peer sampling required by gossip-based unstructured overlays. In this paper, we show that maintaining the leaf set of Pastry and the proximity links of an unstructured overlay, is enough to build the complete overlays. Simulation results comparing our approach with both a Pastry-like system and a gossip-based unstructured overlay show that we significantly reduce the overlay maintenance overhead whithout sacrificing upon performance. |
01/02/2007 : Anne Benoit : Strategies for Replica Placement in Tree Networks
|
Anne Benoit
(http://graal.ens-lyon.fr/~abenoit/)
Get the slides Résumé : We will discuss and compare several policies to place replicas in tree networks, subject to server capacity. The client requests are known beforehand, while the number and location of the servers are to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers. One major contribution is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity and QoS constraints, both from a theoretical and a practical perspective. We establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. These heuristics are compared to an optimal solution provided by the formulation of the problem in terms of the solution of an integer linear program. |
25/01/2007 : Abdou Guermouche : Mémoire et volume d'entrées sorties pour les méthodes hors mémoire de factorisation de matrices creuses : même combat?
|
Abdou Guermouche
Get the slides Résumé : Les systèmes linéaires creux de grande taille sont au c\oe{}ur de nombreux codes de simulation numérique. En raison de leur robustesse et de leur performance, les approches directes sont des méthodes appréciées pour la résolution de tels systèmes. Il apparaît que ces approches, bien que très performantes, utilisent souvent une quantité de mémoire significative, qui peut souvent dépasser la mémoire disponible sur la plate-forme cible considérée (cluster, grappe de SMP, calculateur haute-performance). De ce fait, nous nous intéresserons dans cet exposé à des algorithmes visant la minimisation de la mémoire dans un premier temps. D'autre part, si la miminisation de la mémoire nécessaire n'est pas suffisante pour pouvoir résoudre le problème, il est nécessaire d'utiliser des techniques hors-mémoire (out-of-core). Dans ce nouveau contexte, nous montrerons que la minimisation du volume d'entrées sorties n'est pas équivalente à la minimisation de la mémoire et nous proposerons des algorithmes pour réduire le volume d'entrées sorties. Toutes les techniques présentées dans cet exposé seront prouvées théoriquement (lorsqu'un algorithme optimal existe) et validée expérimentalement sur des problèmes issus du monde industriel. |
18/01/2007 : Isabelle Guérin-Lassous : Problèmes de partage de bande passante dans les réseaux radio multisauts
|
Isabelle Guérin-Lassous
(http://citi.insa-lyon.fr/~iguerinl/)
Get the slides Résumé : Dans cet exposé, nous montrerons quels sont les problèmes qui surviennent dans les réseaux radio multisauts qui utilisent une technologie sans fil basée sur un accès au médium de type CSMA/CA. Nous décrirons ensuite quelques approches possibles pour résoudre les problèmes de partage de bande passante qui ont été mis en évidence. |
09/01/2007 : Jérémie Allard : SOFA - Combining simulations, interactions, and multi-processing on GPUs and clusters for medical applications
|
Jérémie Allard
(http://sofa-framework.org/)
Résumé : SOFA is an open-source physical simulation architecture developped in collaboration between SimGroup @ CIMIT, Alcove / Asclepios / Evasion @ INRIA as well as other partners (IRCAD, ETHZ, Case Western). The long term goal is to create an open and extensible platform for medical simulation, however the current challenges reside in coupling all the required components and expertise in a modular yet efficient framework. In this talk I will present the current design, proposing a new scenegraph-like high-level simulation formalism. This architecture allows the integration of fluids, rigids and deformable bodies while supporting hard constraints and stiff interaction forces, using implicit or multi-step explicit integrators that handle dynamically-created groups of interacting objects. Preliminary results coupling FEM or FFD-based deformable bodies with rigids and SPH or eulerian fluids will be discussed. To achieve interactive refresh rates as required by medical applications, efficient scheduling schemes exploiting the available CPU and GPU units are of great interest. By modularizing computations and formalizing data dependencies, SOFA offers a clean separation between the simulation code and the parallel scheduling algorithm. Several prototypes have been implemented, reaching 10x speedups on 16-core Opteron-based SMP host thanks to KAAPI work-stealing scheduler from MOAIS, as well as similar speedups on the new 128-core NVIDIA 8800 graphics card using CUDA. As SOFA is maturing, more complex applications will be possible. I will present videos of the most recent results, from integrating real objects in the simulation using multi-camera real-time reconstruction, to an advanced endovascular training system involving deformed volume rendering, and implicit-surface contact solver for catheter navigation. |
21/12/2006 : Ken Tomlinson : OpenSolaris, le Systeme d'Exploitation Ouvert de Sun Microsystems: les Motivations de ce Choix et les Opportunités pour le Milieu Educatif.
|
Ken Tomlinson
Get the slides Get the slides Résumé : Sun est connu pour ses serveurs et pour certaines technologies telles que NFS, Java, ainsi que son systeme d'exploitation Solaris. Ce qui est moins connu est l'ouverture du systeme sous le nom de OpenSolaris en juin 2005, ce qui transforme un systeme proprietaire en systeme parmi les plus ouverts. Les facteurs ayant conduit a cette décision sont la demande des clients, le désir d'améliorer la qualité du système par des echanges enrichissants avec une communauté active. Ce changement ouvre également de nouvelles possibilités pour le milieu educatif (crédits de recherche, dons de materiel, etc.). |
14/12/2006 : Paul Amblard : Notes de lecture et d'expérimentation sur le Multi-processeur CELL (IBM-Sony-Toshiba)
|
Paul Amblard
(http://tima-cmp.imag.fr/~amblard/)
Get the slides Get the slides Résumé : Le groupement IBM-Sony-Toshiba a défini une nouvelle architecture parallèle avec 9 processeurs hétérogènes sur une puce. Avec un étudiant de magistère, nous avons lu et expérimenté... (Mais pas au point d'avoir des mesures de "performances", disponibles de toute facon par ailleurs) Je présente quelques principes du CELL qui m'ont semblé susceptibles d'intéresser des spécialistes de répartition. |
7/12/2006 : Patrice Moreaux : Analyse des réseaux de Petri stochastiques non markoviens - une nouvelle approche
|
Patrice Moreaux
(http://www.univ-savoie.fr/Portail/Groupes/listic2/membres/Patrice.Moreaux/index.html)
Résumé : Les réseaux de Petri stochastiques (SPN) ont donné lieu à de nombreuses variantes pour prendre en compte différents aspects de la modélisation des systèmes à événements discrets avec aléa. Dans ce travail, nous nous intéressons à l'analyse transitoire et à l'équilibre des SPN -non markoviens- comportant des distributions à support fini, sans autre contrainte. Plutôt que de calculer une distribution approchée du modèle, comme c'est le cas dans les approches précédentes, nous réalisons une analyse exacte d'un modèle approché. La conception de cette méthode conduit à une gestion uniforme des cas transitoire et à l'équilibre. Cette méthode est une adaptation de nos résultats précédents développés pour des processus stochastiques généraux. L'emploi du formalisme réseaux de Petri nous permet de décrire le comportement du processus approché sous forme d'expressions tensorielle. Ces représentations conduisent à des réductions significatives des complexités temporelles et mémoire. Travail commun avec Serge Haddad, Lynda Mokdad (LAMSADE, U. Paris Dauphine). |
30/11/2006 : Francois Faure : Sofa: flexible modeling and programming of physical scenes
|
Francois Faure
(???)
Résumé : Sofa is a new open-source library primarily targetted to the physical simulation of surgical models. Based on a sophisticated data structure, it allows to:
|
23/11/2006 : Francis Sourd : Résolution du problème d'ordonnancement avance-retard à l'aide de programmes linéaires avec variables indexées sur le temps.
|
Francis Sourd
(http://www-poleia.lip6.fr/~sourd/)
Get the slides Résumé : Nous commencerons par introduire la problématique de l'ordonnancement avec pénalités d'avance et de retard en insistant sur ses particularités (insertion de période d'inactivité même lorsque des tâches pourraient être exécutées). Nous formulerons ensuite le problème par deux programmes linéaires en nombres entiers différents qui utilisent tous deux des variables indexées sur le temps. Les liens théoriques entre ces deux modèles seront présentés ainsi les différentes manières de les utiliser pour résoudre efficacement le problème d'ordonnancement. L'exposé se terminera par la présentation de techniques qui ont permis d'améliorer la qualité des bornes inférieures et ainsi d'implanter l'algorithme permettant de résoudre des problèmes de plus grosse taille (60 tâches dans le cas général et 1000 tâches dans le cas de date d'échéance commune). |
17/11/2006 : Ivan Frain : Systèmes à quorums dynamiques et projet ViSaGe : gestion de la cohérence des données répliquées sur une grille informatique.
|
Ivan Frain
Get the slides Résumé : Les systèmes à quorums sont des mécanismes permettant de gérer la cohérence des réplicas en univers réparti. Un système à quorums utilise une organisation logique des réplicas en divers sous-ensembles appelés quorums. Une opération de lecture ou une opération d'écriture se fait alors uniquement sur les copies d'un seul quorum. Tout en maintenant la cohérence des réplicas lors des opérations de lecture et d'écriture, les systèmes à quorums limitent le nombre de copies accédées et permettent, ainsi, d'améliorer la disponibilité des données. Dans des systèmes distribués de nouvelle génération, comme les grilles informatiques, les distances entre les noeuds de stockage sont importantes et l'utilisation de la réplication permet de pallier les problèmes de bande passante faible et de temps de latence élevé. Afin que le maintien de la cohérence des réplicas soit le moins coûteux possible dans ce genre d'environnement, les systèmes à quorums doivent être adaptés à la dynamicité des grilles. Cette dynamicité se retrouve au niveau de l'évolution de la charge des noeuds de stockage. Malheureusement, dans la plupart des intergiciels de grille dédiés au stockage, la construction des quorums à partir de l'ensemble des N copies est complétement détachée de l'état des ressources de la grille. Dans un premier temps, nous présenterons des protocoles de reconfiguration permettant l'ajustement dynamique de systèmes à quorums afin de mieux prendre en compte l'évolution de la charge des noeuds de stockage. Puis nous présenterons l'architecture logicielle de ViSaGe (Virtualisation du Stockage appliquée aux Grilles informatiques), un système de gestion du stockage pour grille permettant l'exploitation de plusieurs systèmes à quorums simultanément. |
16/11/2006 : Emmanuel Jeannot : Bi-objective Scheduling Algorithm for Optimizing Makespan and Reliability on Heterogeneous Systems
|
Emmanuel Jeannot
(http://www.loria.fr/~ejeannot/)
Get the slides Résumé : We tackle the problem of scheduling DAGs a on an heterogeneous set of machines, where each processor has a probability of failure driven by an exponential law. The goal is given a makespan objective, find the best achievable reliability. We provide an optimal scheduling algorithm for independent unitary tasks, we study the problem of a indenpendent tasks where we provide an approximation algorithm. For general DAG, we show how to compare two schedules using one metric and we provide a general method for converting an algorithm that schedules DAG on heterogeneous cluster into an algorithm that takes reliability into account. |
9/11/2006 : : Séminaire de Rentrée: présentations des projets, des nouveaux arrivants, ...
|
Résumé : 14h00: présentation de la structure administrative : Brigitte 14h15: présentation de Mescal : Bruno G. 14h30: présentation de Moais : Jean-Louis 14h45: présentation de Grimage : Bruno R. 15h00: présentation de Ciment et grid 5000 : Olivier R. 15h15: les droits et les devoirs dans le labo : Denis T. 15h30: le point de vue du thésard: Florent Blachot 16h00: POT |
26/10/2006 : Fanny Pascual : De l'approximation polynomiale à la théorie des jeux : applications dans les domaines des réseaux et de l'internet.
|
Fanny Pascual
(http://www.lami.univ-evry.fr/~fpascual/)
Get the slides Résumé : Je propose d'exposer les travaux que j'ai réalisés dans ma thèse, et qui traitent de problèmes d'optimisation liés au domaine des réseaux. Ces problèmes sont d'une part des problèmes d'optimisation ``classiques'' dans lesquels nous cherchons à pallier la NP-difficulté d'un problème en proposant des algorithmes approchés, le plus souvent avec garantie de performance. D'autre part, nous avons considéré des problèmes dans lesquels les utisateurs du réseau sont indépendants et individualistes. Chaque utilisateur souhaite alors optimiser sa propre fonction objectif, qui peut être très différente de la fonction objectif globale que, en tant que concepteurs d'un protocole, nous souhaitons optimiser. Par exemple, si les utilisateurs possèdent des tâches à ordonnancer, la fonction objectif globale que nous souhaitons optimiser peut être la date de fin de l'ordonnancement (makespan), alors que le but de chaque utilisateur est de minimiser la date de fin de sa propre tâche. Il peut pour cela choisir lui-même la machine sur laquelle sa tâche sera ordonnancée, et/ou déclarer un faux temps d'exécution à la machine qui l'ordonnance. Nous nous plaçons alors dans le cadre de la théorie des jeux algorithmique et cherchons à optimiser la fonction objectif globale en prenant en compte des contraintes supplémentaires dues au fait que les utilisateurs se comportent de façon individualiste. Les problèmes que nous avons considérés sont des problèmes d'ordonnancement et de routage. |
19/10/2006 : Guillaume Huard : TakTuk-3: Adaptive large scale remote execution deployment
|
Guillaume Huard
(http://www-id.imag.fr/Laboratoire/Membres/Huard_Guillaume/)
Get the slides Résumé : Taktuk is a tool for deploying remote execution commands to a potentially large set of remote nodes. It spreads itself using an adaptive algorithm and set up an interconnection network to transport commands and perform I/Os multiplexing/demultiplexing. The Taktuk algorithms dynamically adapts to environment (machine performance and current load, network contention) byusing a reactive algorithm that mix local parallelization and work distribution. http://taktuk.gforge.inria.fr/ |
28/09/2006 : Frédéric Wagner : Redistribution de données à travers un réseau à haut débit
|
Frédéric Wagner
(http://www.loria.fr/~wagnerf/)
Get the slides Résumé : Pour utiliser au mieux les ressources distribuées (calculateurs parallèles, grappes d'ordinateurs, serveurs de calcul ou de données, ordinateur personnel, dispositifs de visualisation, etc.) et plus généralement l'infrastructure numérique il est nécessaire de mettre au point des environnements et des algorithmes qui gèrent celle-ci de manière optimisée. Nous présentons le problème qui survient lorsque des données doivent être rapidement transférées d'un calculateur parallèle à un autre calculateur. C'est le cas lorsque le traitement fait intervenir du couplage de code ou lorsque l'on veut visualiser des données calculées par une machine parallèle. Ce problème appelé la redistribution de données est un problème très important quand les critères de performances sont au premier plan. Pour être résolu, il nécessite surtout d'optimiser l'ordre dans lequel les données sont transférées. Nous introduisons une modélisation de ce problème d'ordonnancement basé sur la théorie des graphes ainsi que deux algorithmes d'approximation le résolvant. Nous illustrons le développement de ces algorithmes par la transformation d'un algorithme pseudo-polynomial en algorithme polynomial. |
21/09/2006 : Alain Darte : Register Allocation: What does the NP-completeness Proof of Chaitin et al. Really Prove?
|
Alain Darte
(http://perso.ens-lyon.fr/alain.darte/)
Get the slides Get the slides Résumé : Register allocation is one of the most studied problems in compilation. It is considered as an NP-complete problem since Chaitin et al., in 1981, modeled the problem of assigning temporary variables to k machine registers as the problem of coloring, with k colors, the interference graph associated to the variables. The fact that the interference graph can be arbitrary proves the NP-completeness of this formulation. However, this original proof does not really show where the complexity of register allocation comes from. Recently, the re-discovery that interference graphs of SSA programs can be colored in polynomial time raised the question: Can we exploit SSA form to perform register allocation in polynomial time, without contradicting Chaitin et al's NP-completeness result? To address such a question and, more generally, the complexity of register allocation, we revisit Chaitin et al's proof to better identify the interactions between spilling (load/store insertion), coalescing/splitting (removal/insertion of moves between registers), critical edges (a property of the control-flow graph), and coloring (assignment to registers). In particular, we show that, in general (we will make clear when), it is /easy/ to decide if temporary variables can be assigned to k registers or if some spilling is necessary. In other words, the real complexity does not come from the coloring itself (as a wrong interpretation of the proof of Chaitin et al. may suggest) but comes from the presence of critical edges and from the optimizations of spilling and coalescing. |
14/09/2006 : Aurélien Bouteiller : Tolérance automatique aux défaillances par points de reprise et retour en arrière dans les systèmes hautes performances à passage de messages
|
Aurélien Bouteiller
(http://www.lri.fr/~bouteill/)
Get the slides Résumé : Si l'augmentation du parallélisme a permis aux architectures hautes performances de dépasser la barrière symbolique du TeraFlop, il semblerait que la diminution de la fiabilité de la machine consécutive à l'augmentation du nombre de composants n'entrave la course au PetaFlop. Cette constatation a réactivé les recherches dans le domaine de la tolérance aux défaillances. Une solution pour assurer la progression d'un calcul numérique distribué en présence de fautes est d'enregistrer périodiquement des points de reprise. Lorsqu'une défaillance survient, un processus de remplacement est relancé à partir des données du point de reprise. Cependant, le comportement de chaque processus d'une application distribuée subit le non déterminisme des évènements survenant sur le réseau. Aussi, il faut introduire des mécanismes assurant que l'ensemble des points de reprise permet bien de restaurer l'application dans un état légitime. Notre travail a pour objectifs principal l'étude des mécanismes automatiques de tolérance aux défaillances par points de reprise pour les applications à passage de message utilisant le standard de communication MPI. Notre présentons un environnement logiciel permettant l'expression d'algorithmes de tolérance aux défaillances de diverses familles et leur comparaison équitable et significative dans un environnement uniforme. Nous introduisons dans cet environnement plusieurs protocoles de tolérance aux défaillances : un protocole utilisant des points de reprise coordonné, deux protocoles par enregistrement de message dont un entièrement nouveau, trois protocoles par enregistrement de message causal dont un nouveau. Nous améliorons les mécanismes d'enregistrement sur support stable des évènements et des points de reprise. Nous réalisons une comparaison expérimentale poussée de ces protocoles permettant d'identifier une fréquence de faute au delà de laquelle les protocoles par enregistrement de messages se comportent mieux que les protocoles coordonnés. Nous présentons enfin OpenMPI-V, un environnement de tolérance aux défaillance adapté aux réseaux à très haut débit. La performance de ces réseaux implique que l'utilisation de copies mémoires intermédiaires est très pénalisante. Nous présentons les performances d'une variante du protocole par enregistrement de message pessimiste lourdement modifiée pour supprimer ces copies mémoires. |