Groupe de travail Graal 2006-2007

Programme

À voir également

• Archives de l'année 2005-2006
• Conférences et Séminaires de l'ENS Lyon
• Le séminaire du LIP  
• Le séminaire du MIM  (dont cette page est "tres" inspiree)
• La page d'accueil de l'equipe GRAAL
  

Résumés des groupes de travail

Simulations cosmologiques sur Grid'5000

	Date		15 Septembre 2006 - 10h15
	Orateur		Benjamin Depardon
	Résumé		L'étude de la cosmologie a un besoin croissant en puissance de calcul pour pouvoir valider ses modèles théoriques. Dans le cadre de mon stage je me suis intéressé à l'application Ramses, et à sa mise en oeuvre dans l'environnement Grid'5000. Le but de cette application est de suivre l'évolution des particules de matière sombre au cours du temps (depuis la formation de l'univers, jusqu'à aujourd'hui), pour étudier la formation de structures (halos de matière) et pouvoir comparer ces résultats à la réalité. Mon travail a été de mettre en place une architecture sur Grid'5000, en utilisant DIET, permettant de réaliser des simulations de bout en bout (de la récupération des conditions initiales, jusqu'au post-traitement des données générées par Ramses). Je présenterai les différentes applications utilisées, puis les 2 architectures mises en place. Enfin je présenterai quelques résultats expérimentaux.
	Transparents

Répétition de thèse: Automatic Deployment for ASP Environments

	Date		21 Septembre 2006 - 10h15
	Oratrice		Pushpinder Kaur Chouhan
	Résumé		The main objective of the thesis is to improve the performance of a ASP environment so as to use these environments efficiently. Here efficiency means the maximum number of completed requests that can be treated in a time step by these environments. The very first problem which comes to picture is related to the applications scheduling on the selected servers. We have presented algorithms for the scheduling of the sequential tasks on a ASP environment. Experimentally we proved that the deadline scheduling with priority along with fallback mechanism can increase the overall number of tasks executed by the ASP. Another important factor that influence the efficiency of the ASP environments is the mapping style of the environment's components on the available resources. The questions such as ``which resources should be used?'', ``how many resources should be used?'' and ``should the fastest and connected resource be used for middleware or as a computational resource?'' remained unanswered. In this thesis we gave the solutions to these questions. We have shown theoretically that the optimal deployment on cluster is a Complete Spanning d-ary (CSD) tree complete spanning d-ary tree. Considering heterogeneous resources we presented a deployment heuristic, as finding the best deployment among heterogeneous resources is amounts to find the best broadcast tree on a general graph, which is known to be NP-complete. Finally, we gave a mathematical model that can analyze an existing deployment and can improve the performance of the deployment by finding and then removing the bottlenecks. This is an heuristic approach for improving deployments of ASP environments that has been defined by other means. Deployment planning algorithms and heuristic presented in thesis are validated by implementing them to deploy a hierarchical middleware diet, on different sites of gk, a set of distributed computational resources in France.
	Transparents

Répétition de thèse: Ordonnancement et réplication de données bioinformatiques dans un contexte de grille de calcul

	Date		5 Octobre 2006 - 15h30
	Orateur		Antoine Vernois
	Transparents

Répétition de thèse: Communications collectives et ordonnancement en régime permanent sur plates-formes hétérogènes

	Date		12 Octobre 2006 - 15h30
	Orateur		Loris Marchal
	Transparents

Mapping an Indexing Trie-Structured System on a Peer-to-Peer Network

	Date		26 Octobre - 15h30
	Orateur		Cédric Tedeschi
	Résumé		Some new trie-based peer-to-peer tools attempt at passing through the limitation of traditional approaches for the grid's service discovery. They support a scalable mean for range queries. Most of those approaches are two-layers architectures, a trie indexing the objects being mapped on a DHT network. They present some drawbacks. First, the complexities of the two layers are multiplied, resulting in a non negligible cost of maintenance and communications. Second, the mapping is randomly achieved, resulting in avoiding potential communication cost reduction and poor load balancing. In this paper, we propose a scheme maintaining and mapping a prefix tree without an underlying DHT. We provide the algorithms required to achieve this purpose and deal with the load balancing issue by proposing a novel heuristic and comparing it to the most recent work by simulation.
	Transparents

Strategies for Replica Placement in Tree Networks - part 1

	Date		9 Novembre - 15h30
	Oratrice		Anne Benoit
	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, 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 absolute lower bound provided by the formulation of the problem in terms of the solution of an integer linear program.
	Transparents

Théorie et pratique de l'ordonnancement d'applications sur les systèmes parallèles et distribués

	Date		16 Novembre 2006 - 15h30
	Orateur		Lionel Eyraud-Dubois
	Résumé		Nous explorons deux facettes de la gestion de ressources sur grappes de PCs, l'analyse théorique et la mise en oeuvre pratique. Les études théoriques sont basées sur le modèles des tâches parallèles, et ont mené à la conception d'un algorithme bicritère, avec de bonnes garanties simultanément sur le makespan et le temps de complétion moyen pondéré. Nous en proposons également une version simplifiée, qui obtient de bonnes performances en simulation par rapport aux algorithmes existants et à des bornes inférieures. Enfin, cet algorithme a été implémenté et adapté au logiciel de gestion de ressources OAR, et a ainsi pu être validé en rejouant des traces d'exécution de grappes locales. Les problèmes rencontrés lors de cette implémentation ont mené à l'étude théorique de modèles avec indisponibilité des ressources. Nous proposons ainsi quelques résultats de complexité et des garanties pour les algorithmes de liste, qui généralisent le cas séquentiel.
	Transparents

Strategies for Replica Placement in Tree Networks - part 2

	Date		30 Novembre 2006 - 15h30
	Oratrice		Veronika Rehn
	Résumé		This working group is the second part of "Strategies for Replica Placement in Tree Networks". The first part (Nov 9th) focused on theoretical results, while this part is assigned to the study of several efficient polynomial heuristics for NP-complete instances of the problem. We will discuss and compare several heuristics 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. Last time, we introduced 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 of this working group is to assess experimentally the impact of these new policies on the total replication cost, as well as the impact of server heterogeneity. In a second part we introduce some QoS constraints and present a set of adapted heuristics for each policy. An important goal is to assess the impact of QoS on the performance. All heuristics are compared to an absolute lower bound provided by the formulation of the problem in terms of the solution of an integer linear program.
	Transparents

Multi-workflow scheduling

	Date		7 Décembre 2006 - 15h30
	Orateur		Raphaël Bolze
	Résumé		Au cours de ce groupe de travail, je commencerai par poser le problème auquel nous nous intéressons : l'ordonnancement d'un ensemble de graphes de tâches dans un environnement grille. La motivation de ce travail sera illustrée par quatre applications. Je présenterai un bref état de l'art du sujet et vous détaillerai un ensemble d'heuristiques qui découlent de l'étude de ce problème. Dans ce cadre je vous présenterai un outil que j'ai développé permettant de simuler les heuristiques précédemment évoquées. Enfin, nous aborderons les prochaines étapes de notre étude, notamment avec l'intégration de certaines heuristiques dans l'intergiciel DIET.
	Transparents

Étude d'un solveur parallèle multifrontal out-of-core

	Date		11 Janvier 2007 - 15h30
	Orateur		Emmanuel Agullo
	Résumé		The memory usage of sparse direct solvers can be the bottleneck to solve large-scale problems involving sparse systems of linear equations of the form Ax=b. In a previous work, we proposed a first out-of-core extension of a parallel multifrontal approach based on the solver MUMPS, where only the computed factors were written to disk during the factorization. In this presentation, we will study in detail the minimum memory requirement of this parallel multifrontal approach. For a given amount of memory, we will also discuss the volume of disk accesses involved during the factorization of matrix A, providing insight on the extra cost that we can expect due to I/O. Large-scale problems from applicative fields are used to illustrate our discussions.
	Transparents

Think before coding: static strategies (and dynamic execution) for clusters and grids.

	Date		10 Mai 2007 - 15h30
	Orateur		Yves Robert
	Résumé		In this talk we provide several examples to illustrate key algorithmic concepts required to efficiently execute applications on clusters and grids. The idea is to give a lively exposition of the necessity to inject whatever static knowledge is available into the design of typical applications, such as master-slave tasking, numerical kernels, and job workflows. We claim that this is the key to an efficient deployment of these applications onto large-scale distributed computational platforms. The talk will proceed through examples to explain how to cope with resource selection, memory constraints, platform heterogeneity, etc.
	Transparents

A Model for Large Scale Self-Stabilization

	Date		31 Mai 2007 - 15h30
	Orateur		Cédric Tedeschi
	Auteurs		Thomas Herault, Pierre Lemarinier, Olivier Peres, Laurence Pilard, Joffroy Beauquier
	Résumé		We introduce a new model for distributed algorithms designed for large scale systems that need a low-overhead solution to allow the processes to communicate with each other. We assume that every process can communicate with any other process provided it knows its identifier, which is usually the case in e.g. a peer to peer system, and that nodes may arrive or leave at any time. To cope with the large number of processes, we limit the memory usage of each process to a small constant number of variables, combining this with previous results concerning failure detectors and resource discovery. We illustrate the model with a self-stabilizing algorithm that builds and maintains a spanning tree topology. We provide a formal proof of the algorithm and the results of experiments on a cluster.
	Transparents

Parallélisation de l'algorithme MkDom2

	Date		14 juin 2007 - 15h30
	Orateur		Clément Rezvoy
	Résumé		ProDom est une base de données de familles de domaines protéiques construite automatiquement par comparaison de séquences à l'aide de l'algorithme MkDom2. Avec l'augmentation exponentielle du nombre de séquences connues, le temps de construction de la base de données Prodom a explosé jusqu'à devenir impraticable (plus de deux ans de calcul à l'heure actuelle). Cette étude montre qu'il est possible de répartir efficacement le temps de calcul de façon à permettre une accélération d'un facteur de plus de 50 et définit les limites de cette parallélisation imposées par la nature de l'algorithme MkDom2.
	Transparents

Scheduling for climate forecast application

Déploiement générique d'applications sur plates-formes hétérogènes réparties

	Date		26 juin 2007 - 10h00
	Orateur		Benjamin Depardon
	Résumé		Les grilles de calcul sont des systèmes distribués hétérogènes de plus en plus utilisés pour exécuter des applications de calcul scientifique. Seulement les expériences à large échelle nécessitent des moyens simples et automatisés pour sélectionner les ressources à utiliser, puis installer et exécuter les applications afin de rendre accessible cette puissance de calcul à des utilisateurs non experts en informatique. Aucun outil ne permet pour l'instant de couvrir l'intégralité du processus de déploiement, le plus gros manque se situant au niveau des algorithmes d'attribution de ressources aux applications. Il est donc indispensable de proposer de nouveaux algorithmes efficaces. Parmi les logiciels de déploiement Adage est celui qui s'annonce le plus prometteur. Notre but est de rajouter des algorithmes de déploiement au sein d'Adage. Le problème que nous cherchons à résoudre est de trouver un déploiement qui minimise les communications, répartit la charge de façon équitable entre les processeurs, et maximise le nombre d'instances des applications déployées.
	Transparents

Scheduling multi-task applications

	Date		5 juillet 2007 - 15h30
	Orateur		Jean-François Pineau
	Résumé		Les problèmes d'ordonnancement sont déjà difficiles sur des traditionnelles machines parallèles. Ils deviennent encore plus intéressant sur des grappes de machines hétérogènes. Ici, nous envisageons la situation où des usagers, ou clients, soumettent de nombreuses applications composées de paquets de tâches sur une telle grappe de machines, utilisant un modèle client-serveur classique. Les applications sont soumises à la volée, ce qui signifie qu'il n'y a pas à priori de connaissance de la charge de travail au début de l'éxécution. Lorsque plusieurs applications sont éxécutées simultanément, elles sont en compétition pour l'accès aux ressources. Après avoir définit notre fonction objective, nous étudierons le modèle hors-ligne, et nous mettrons au point un algorithme optimal pour résoudre notre problème, en faisant appel à des outils mathématiques compliqués.
	Transparents

2 ans de travaux sur MUMPS