Show simple item record

dc.contributor.advisorRoman, Jean
dc.contributor.advisorEsnard, Aurélien
dc.contributor.authorVUCHENER, Clement
dc.contributor.otherDuchaine, Florent
dc.contributor.otherPellegrini, François
dc.date2014-02-07
dc.identifier.urihttp://www.theses.fr/2014BORD0012/abes
dc.identifier.urihttps://tel.archives-ouvertes.fr/tel-00952777
dc.identifier.nnt2014BORD0012
dc.description.abstractL'équilibrage de charge est une étape importante conditionnant les performances des applications parallèles. Dans le cas où la charge varie au cours de la simulation, il est important de redistribuer régulièrement la charge entre les différents processeurs. Dans ce contexte, il peut s'avérer pertinent d'adapter le nombre de processeurs au cours d'une simulation afin d'obtenir une meilleure efficacité, ou de continuer l'exécution quand toute la mémoire des ressources courantes est utilisée. Contrairement au cas où le nombre de processeurs ne varie pas, le rééquilibrage dynamique avec un nombre variable de processeurs est un problème peu étudié que nous abordons ici.Cette thèse propose différentes méthodes basées sur le repartitionnement de graphe pour rééquilibrer la charge tout en changeant le nombre de processeurs. Nous appelons ce problème « repartitionnement M x N ». Ces méthodes se décomposent en deux grandes étapes. Dans un premier temps, nous étudions la phase de migration et nous construisons une « bonne » matrice de migration minimisant plusieurs critères objectifs comme le volume total de migration et le nombre total de messages échangés. Puis, dans un second temps, nous utilisons des heuristiques de partitionnement de graphe pour calculer une nouvelle distribution optimisant la migration en s'appuyant sur les résultats de l'étape précédente. En outre, nous proposons un algorithme de partitionnement k-aire direct permettant d'améliorer le partitionnement biaisé. Finalement, nous validons cette thèse par une étude expérimentale en comparant nos méthodes aux partitionneursactuels.
dc.description.abstractEnLoad balancing is an important step conditioning the performance of parallel programs. If the workload varies drastically during the simulation, the load must be redistributed regularly among the processors. Dynamic load balancing is a well studied subject but most studies are limited to an initially fixed number of processors. Adjusting the number of processors at runtime allows to preserve the parallel code efficiency or to keep running the simulation when the memory of the current resources is exceeded.In this thesis, we propose some methods based on graph repartitioning in order to rebalance the load while changing the number of processors. We call this problem \M x N repartitioning". These methods are split in two main steps. Firstly, we study the migration phase and we build a \good" migration matrix minimizing several metrics like the migration volume or the number of exchanged messages. Secondly, we use graph partitioning heuristics to compute a new distribution optimizing the migration according to the previous step results. Besides, we propose a direct k-way partitioning algorithm that allows us to improve our biased partitioning. Finally, an experimental study validates our algorithms against state-of-the-art partitioning tools.
dc.language.isofr
dc.subjectSimulation numérique
dc.subjectRepartitionnement
dc.subjectPartitionnement de graphe
dc.subjectRedistribution
dc.subjectEquilibrage de charge dynamique
dc.subjectParallélisme
dc.subject.enNumerical simulation
dc.subject.enRepartitioning.
dc.subject.enGraph partitioning
dc.subject.enRedistribution
dc.subject.enDynamic load-balancing
dc.subject.enParallelism
dc.titleEquilibrage de charges dynamique avec un nombre variable de processeurs basé sur des méthodes de partitionnement de graphe
dc.title.enDynamic Load-Balancing with Variable Number of Processors based on Graph Partitioning
dc.typeThèses de doctorat
dc.contributor.jurypresidentManneback, Pierre
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.hal.laboratoriesInstitut national de recherche en informatique et en automatique (France). Centre de recherche Bordeaux - Sud-Ouest
bordeaux.type.institutionBordeaux
bordeaux.thesis.disciplineInformatique
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde)
star.origin.linkhttps://www.theses.fr/2014BORD0012
dc.contributor.rapporteurManneback, Pierre
dc.contributor.rapporteurUçar, Bora
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Equilibrage%20de%20charges%20dynamique%20avec%20un%20nombre%20variable%20de%20processeurs%20bas%C3%A9%20sur%20des%20m%C3%A9thodes%20de%20partitionnement%20de%20graphe&rft.atitle=Equilibrage%20de%20charges%20dynamique%20avec%20un%20nombre%20variable%20de%20processeurs%20bas%C3%A9%20sur%20des%20m%C3%A9thodes%20de%20partitionnement%20de%20graphe&rft.au=VUCHENER,%20Clement&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record