Groupe de travail Graal 2005-2006

Programme

À voir également

• 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

Evaluation des performances de programmes paralleles haut niveau a base de squelette algorithmique

	Date		06 octobre 2005 - 8h45
	Orateur		Anne Benoit
	Résumé		Dans un contexte de programmation pour les grilles de calcul (ensemble hétérogène de ressources reliées par un réseau, accessible à une communauté d'utilisateurs), la programmation à base de squelettes algorithmiques exploite le fait que de nombreuses applications utilisent les mêmes schémas de programmation bien connus. Cette approche de haut niveau permet ainsi de structurer aisément les programmes parallèles en fournissant à l'utilisateur une librairie de squelettes (routines génériques) prédéfinis. Dans le projet eSkel -- Edinburgh Skeleton Library (http://homepages.inf.ed.ac.uk/abenoit1/eSkel), motivés par nos observations sur les précédentes tentatives pour implémenter ces idées, nous avons commencé à définir un ensemble générique de squelettes sous la forme d'une librairie de fonctions C, basée sur MPI. La première partie du séminaire présentera la librairie eSkel, en présentant les principaux concepts fondamentaux à la base de la librairie. L'utilisation d'un squelette donné de la librairie eSkel implique de nombreuses informations sur les dépendances imposées sur le scheduling de l'application. La deuxième partie du séminaire montre comment nous exploitons cette information dans le projet Enhance (http://groups.inf.ed.ac.uk/enhance), en modélisant les squelettes à l'aide d'algèbres de processus. Nous pensons pouvoir obtenir ainsi des résultats permettant de prendre de meilleures décisions d'ordonnancement sur la grille que les approches moins sophistiquées. De plus, les techniques développées sur les grilles permettent d'obtenir les performances des ressources utilisées de façon dynamique, ce qui permet un réordonnancement dynamique de l'application.
	Transparents

Automatic Deployment Planning For Clusters

	Date		13 octobre 2005 - 8h45
	Orateur		Pushpinder Kaur Chouhan (LIP, ENS Lyon)
	Résumé		The use of many distributed, heterogeneous resources as a large collective resource offers great potential and has become an increasingly popular idea. A key issue for these Grid platforms is middleware scalability and how middleware services can best be mapped to the resource platform structure. Optimizing deployment is a difficult problem with no existing, general solutions. In this paper we address a simpler sub-problem: how to carry out an adapted deployment on a cluster with hundreds of nodes? Efficient use of clusters alone or as part of the Grid is an important issue. We present an optimal deployment model that predicts the maximum throughput of each element of a deployment. We proved that optimal deployment is a CSD tree with degree d. We presented algorithms to calcualte best degree and to construct a CSD tree with best degree. Our deployment construction algorithm uses this model to automatically create a mapping of middleware elements onto resources with the goal of maximizing the throughput. We apply our approach to automatically deploy a distributed Problem Solving Environment (PSE) called DIET on a homogeneous cluster environment. We present experiments comparing the automatically-generated deployment against a number of other reasonable deployments. Experiments proved that our optimal deployment model can select best degree for a CDS tree and can predict throughput of the CSD tree.
	Transparents

Comparaison des stratégies centralisées et distribuées pour l'ordonnancement d'applications concurrentes sur plate-forme maître-esclave hétérogène

	Date		20 octobre 2005 - 8h45
	Orateur		Loris Marchal (LIP, ENS Lyon)
	Résumé		Lorsqu'on exécute plusieurs applications simultanément sur une plate-forme de calcul hétérogène, celles-ci doivent se partager les ressources de calcul (processeurs) et de communication (bande-passante des liens réseau). Dans ce travail nous nous intéressons à l'ordonnancement efficace et équitable de ces applications sur une plate-forme maître-esclave où les communications sont faites le long d'un arbre inclus dans le réseau. Nous montrons qu'il est possible de calculer un ordonnancement périodique asymptotiquement optimal en utilisant la programmation linéaire. Pour les topologies en étoile (arbre de profondeur 1), nous montrons comment calculer la solution optimale de façon analytique. Pour des plates-formes de grande taille, rassembler l'information globale nécessaire au programme linéaire en un ordonnanceur centralisé peut sembler irréaliste. Une solution est d'adapter l'algorithme des flux concurrents d'Awerbuch et Leighton, mais celui nécessite tout de même quelques informations globales. Nous nous intéressons donc également aux heuristiques n'utilisant que des informations locales, et testons leurs performances par simulation. La meilleure de ces heuristiques atteint les performances optimales dans environ les deux tiers de nos essais, mais peut en être très éloigné dans quelques cas.
	Transparents

Tolerance aux fautes, impossibilites et solutions

	Date		27 octobre 2005 - 8h45
	Orateur		Aurelien Bouteiller (LIP, ENS Lyon)
	Résumé		Pour satisfaire une demande de puissance de calcul toujours grandissante, le nombre de processeurs dans les calculateurs hautes performances ne cesse d'augmenter. Bien que la fiabilité individuelle des composants utilisée soit très bonne, leur très grand nombre implique que le temps moyen d'opération entre deux fautes diminue par rapport à chaque génération précédente de calculateurs. Pour assurer que les architectures parallèles obtiendront de bonnes performances dans le futur, il faut donc développer des solutions au problème des défaillances. La gestion des défaillances est un problème difficile. En fait, dans le cas général, il est démontré qu'il est impossible de réaliser un consensus distribué en présence d'une unique faute de type arrêt total - la plus simple - ce qui limite fortement la calculabilité. Pour continuer d'obtenir des résultats déterministes, il faut donc au choix restreindre le modèle d'exécution ou ce que l'on souhaite calculer. J'exposerais deux travaux de recherche, MPICH-V et RPC-V. MPICH-V est une librairie de passage de message tolérante aux fautes où l'on considère que le système dispose d'un réseau pseudo-synchrone, ce qui permet de lever les limites de calculabilité. RPC-V est un environnement d'appels de procédure à distance (éventuellement récursifs) dans lequel on s'interdit d'écrire des procédures dépendant de l'historique des appels précédents.
	Transparents

Grid5000, présentation et utilisation

	Date		27 octobre 2005 - 8h45
	Orateur		Stéphane D'Alu (LIP, ENS Lyon)
	Résumé		Je veux bien un resume et tes slides (en pdf) s'il te plait Stephane ...
	Transparents

Équilibrage de charge et redistribution de données sur plates-formes hétérogènes

Produit de matrices en maitre-esclave

Minimisation du volume d'E/S pour la méthode multifrontale

Impact de l'hétérogénéité sur l'ordonnancement en ligne sur une plate-forme maître-esclave

	Date		16 mars 2006 - 10h15
	Orateur		Jean-François Pineau
	Résumé		Nous étudions ici le problème d'ordonnancement de tâches identiques et indépendantes avec dates d'arrivées sur une plate-forme maître-esclave, communiquant à l'aide d'un modèle un-port. Alors que ce problème est résoluble en temps polynomial sur une plate-forme homogène, il n'existe pas d'algorithme optimal déterministe dès l'ajout d'une source d'hétérogénéité, que cela soit au niveau des calculs ou des communications. Nous présenterons ainsi des bornes inférieures de compétitivités pour plus de 3 fonctions objectives, et ce sur des plate-formes ayant différentes sources d'hétérogénéité. Des résultats expérimentaux illustreront ce problème.
	Transparents

VoroNet: un réseau objet-à-objet extensible basé sur un diagramme de Voronoi

	Date		23 mars 2006 - 10h15
	Orateur		Loris Marchal
	Résumé		Dans cet exposé, nous introduirons VoroNet, un réseau d'objets pair-à-pair reposant sur une décomposition de Voronoi de l'espace de nommage. Nous présenterons à la fois le protocole, sa justification théorique ainsi que son évaluation expérimentale. VoroNet se distingue des autres réseaux pair-à-pair par le fait que dans VoroNet, les pairs sont les objets de l'application eux-mêmes et ont des identificateurs liés à la sémantique de l'application, au lieu de dépendre d'une fonction de hachage. Cela permet un support extensible pour une recherche efficace dans une grande collection de données. Dans VoroNet, les objets sont organisés dans l'espace de leurs attributs selon un diagramme de Voronoi. VoroNet est inspiré du modèle petit-monde de Kleinberg dans lequel chaque pair est connecté à des voisins proches ainsi qu'à un noeud distant. VoroNet améliore le modèle initial de Kleinberg car il gère des topologies quelconques et peut ainsi faire face à des distributions de données hétérogènes. Nous monterons que VoroNet peut être construit et maintenu de façon totalement décentralisée. L'analyse théorique du système montre que le routage dans VoroNet peut être effectué avec un nombre de sauts poly-logarithmique en la taille du système. Cette analyse est confirmée par l'évaluation expérimentale, menée sous forme de simulations.
	Transparents

Autonomic QoS in ASSIST Grid-aware components

	Date		30 mars 2006 - 10h15
	Orateur		Marco Aldinucci
	Résumé		Current Grid-aware applications are developed on existing software infrastructures, such as Globus, by developers who are experts on Grid software implementation. Although many useful applications have been produced this way, this approach may hardly support the additional complexity to Quality of Service (QoS) control in real application. We describe the ASSIST programming environment, the prototype of parallel programming environment currently under development at our group, as a suitable basis to capture all the desired features for QoS control for the Grid. Grid applications, built as compositions of ASSIST components, are supported by an innovative Grid Abstract Machine, which includes essential abstractions of standard middleware services and a hierarchical Application Manager, which may be considered as an early prototype of Autonomic Manager.
	Transparents

Vers une theorie statistique des SVM multi-classes

Static Scheduling for Large-Scale Platforms: Myth or Reality?

Ordonnancement de workflows dans DIET

	Date		11 mai 2006 - 10h15 - amphi F
	Orateur		Abdelkader Amar
	Résumé		L'environnement DIET développé au sein de l'équipe GRAAL fournit un middleware et un ensemble d'outils pour l'exécution d'applications hautes performances dans un environnement de grille. Cet environnement qui utilise une approche à base d'agents hiérarchiques distribués pour assurer la gestion des ressources et des requêtes des clients, s'appuie sur le paradigme RPC. D'un autre côté, un grand nombre d'applications distribuées ou parallèles est souvent représenté par des graphes de tâches appelés workflows. Cet exposé présente les travaux autour de la gestion et l'ordonnancement de telles applications dans l'environnement DIET, et en particulier la nouvelle architecture logicielle proposée.
	Transparents

Simbatch : une API pour la simulation et la prédiction de performances de systèmes batch

	Date		18 mai 2006 - 10h15
	Orateur		Jean-Sébastien Gay
	Résumé		L'étude d'algorithmes d'ordonnancement de tâches parallèles dans le contexte des grilles de calcul ignore souvent les systèmes de réservation locaux qui gèrent les ressources parallèles, ou suppose qu'ils instancient First Come Fisrt Served. Nous présenterons dans ce groupe de travail une API intégrée au simulateur de grille Simgrid. Elle offre les structures et fonctionnalités pour simuler de façon réaliste les grappes de PCs et les systèmes de réservation batch pour les gérer.
	Transparents

A Repair Mechanism for Fault-Tolerance for Tree-Structured Peer-to-Peer Systems

	Date		Mercredi 24 mai 2006 - 10h15 - amphi F
	Orateur		Cédric Tedeschi
	Résumé		Facing the limits of traditional tools of resource management within computational grids (related to scale, dynamicity, etc. of the platforms newly considered), new approaches, based on peer-to-peer technologies are emerging. The resource discovery and in particular the service discovery is concerned by this evolution. Among the solutions, a promising one is the indexing of resources using trie structures and more particularly prefix trees. The major advantages of trie-structured approaches is the capability to support search queries on ranges of values with a latency growing logarithmically in the number of nodes in the trie. Those techniques are easy to extend to multicriteria searches. One drawback of using tries is its inherent poor robustness in a dynamic environment, where nodes join and leave the network, leading to the split of the tree into a forest, which results in the impossibility to route requests. Within most recent approaches, the fault-tolerance is a prevention mechanism, often replication-based. The replication can be costly in term of resources required. In this talk, we propose a fault-tolerance protocol that reconnects subtrees a posteriori, after crashes, to have a connected graph and then reorder the nodes to rebuild a consistent tree. Finally, we will give a few directions dealing with the reduction of costs of maintenance of such logical structures and its mapping on the physical network.
	Transparents

Scheduling Strategies for minimizing response time on Heterogeneous Master-Slave Platforms

	Date		Jeudi 1er juin 2006 - 10h15 - amphi F
	Orateur		Maria Vlad
	Résumé		We discuss the problem of analytical construction of periodic schedules on a master-slave heterogeneous platform. The tasks are identical, independent and arrive at fixed periods of time communicating on a one-port model. Starting from the algorithm that is building a schedule considering the maximum throughput of the node and the bandwidth centric principle we develop 2 improved heuristics. Both heuristics will try to minimize the response time for the schedule while enforcing a high throughput. The first heuristic is an improved version of the bandwidth centric principle. The schedule is constructed using an accumulation heap for each slave in order to determinate the sending order. The second heuristic is using fixed size periods for constructing schedules that will respect a certain objective response time. The periods will be wrapped around.
	Transparents

Case of Study Around DIET Scheduling

	Date		Jeudi 1er juin 2006 - 10h45 - amphi F
	Orateur		Andreea Chis
	Résumé		DIET a grid middleware provides plugin schedulers specially designed for expert users who wish to upgrade the scheduling for a specific application. This will allow the user to play with the internals of schedulers (called agents) and tune DIET's scheduling by changing the heuristics, adding queues, changing the performance metrics and the aggregation functions, ... In this talk we give an overview of the scheduling mechanism existing in DIET. Two main parts will be discussed : the plugin scheduler and the Collector of Resource Information (CoRI). CoRI is a manager for performance prediction tools. To conclude, the implementation and issues encountered along with some experimental results will be presented.
	Transparents

Ordonnancement et équité proportionnelle sur une plate-forme en structure d'arbre

	Date		Jeudi 8 juin 2006 - 10h15 - amphi B
	Orateur		Rémi Vannier
	Résumé		Les besoins croissants en puissance de calcul impliquent l'utilisation de grilles, sur lesquelles sont généralement exécutées des applications composées de tâches répétitives. Ces différentes applications entrent en concurrence pour l'utilisation des ressources. Il est donc nécessaire lors de l'élaboration d'algorithmes pour l'ordonnancement de ces tâches d'introduire une notion d'équité entre les différentes applications, pour ne pas trop léser les applications gourmandes en calcul, ou en bande passante, tout en maximisant l'utilisation des ressources. Je présenterai lors de cet exposé un algorithme distribué entre les ressources de calcul qui implémente une équité proportionnelle entre les débits des applications, en utilisant notamment des techniques d'optimisation Lagrangienne et de gradient distribué. Notre modèle de grille est un arbre où la racine émet les tâches, et notre algorithme permet à chaque ressource de déterminer localement et pour chaque application les proportions à envoyer à tel fils, ou à exécuter sur place.
	Transparents

Ordonnancement de requêtes commutées : complexités et heuristiques

	Date		Mardi 20 juin 2006 - 10h15 - amphi B
	Orateur		Matthieu Gallet
	Résumé		Les grilles de calcul sont de plus en plus utilisées pour répondre à la demande croissante de puissance de calcul. Cependant, la distribution géographique des centres de calcul pose de nombreux problèmes d'ordonnancement des communications et des calculs. Même si l'utilisation de liens de communication dédiés à ces centres permet d'éviter de nombreux problèmes de trafic, choisir les fichiers à transmettre et définir les bandes passantes à leur attribuer reste un problème difficile. Durant ce stage de février à juin, j'ai donc étudié un cas particulier de ce problème d'attribution de bandes passantes, en considérant uniquement un switch réseau relié à un certain nombre de liens entrants ou sortants, d'abord d'un point de vue théorique puis d'un point de vue expérimental. Après avoir présenté de façon détaillée le problème, je décrirai quelques résultats pratiques avant de donner les principaux résultats théoriques obtenus. Enfin, nous conclurons par l'étude pratique de quelques algorithmes d'approximation.
	Transparents

Scheduling and data redistribution strategies on star platforms

	Date		Jeudi 22 juin 2006 - 10h15 - amphi B
	Orateur		Veronika Rehn
	Résumé		In this work we are interested in the problem of scheduling and redistributing data on master-slave platforms. We consider the case were the workers possess initial loads, some of which having to be redistributed in order to balance their completion times. We examine two different scenarios. The first model assumes that the data consists of independent and identical tasks. We prove the NP-completeness in the strong sense for the general case, and we present two optimal algorithms for special platform types. Furthermore we propose three heuristics for the general case. Simulations consolidate the theoretical results. The second data model is based on Divisible Load Theory. This problem can be solved in polynomial time by a combination of linear programming and simple analytical manipulations.
	Transparents