Design and implementation of efficient tools for parallel partitioning and distribution of very large numerical problems
| Autor: | Chevalier, Cédric |
|---|---|
| Přispěvatelé: | Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithms and high performance computing for grand challenge applications (SCALAPPLIX), INRIA Futurs, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Bordeaux I, Jean Roman(roman@labri.fr), ScAlApplix, INRIA, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux I |
| Jazyk: | francouzština |
| Rok vydání: | 2007 |
| Předmět: |
sparse matrix
distributed memory optimisation locale Parallelism local optimization contraction heuristics coarsening partitionnement heuristiques [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation multi-level Parallélisme expansion renumérotation partitioning uncoarsening matrice creuse dissections emboîtées multi-niveaux nested dissection ordering mémoire distribuée |
| Zdroj: | Modélisation et simulation. Université Bordeaux I, 2007. Français Modélisation et simulation. Université Bordeaux I, 2007. Français. ⟨NNT : ⟩ Modélisation et simulation. Université Sciences et Technologies-Bordeaux I, 2007. Français |
| Popis: | This thesis deals with parallel graph partitioning and, more specifically, focuses on its application to sparse matrix ordering.To solve this problem, we use a multi-level scheme, of which we have parallelized the coarsening and uncoarsening phases.We have developed, for the coarsening phase, a new synchronization algorithm to handle conflicts in remote matchings. We have also improved over existing algorithms by adding to them a selection step which aims at keeping only the most useful communications.Regarding the uncoarsening phase, we have introduced the concept of band graph, which allows us to dramatically decrease problem size for refinement algorithms. We have generalized the use of band graphs to the sequential and parallel implementations of our Scotch partitioning tool. Basing on band graphs, we have proposed a new application of genetic algorithms to the uncoarsening phase, using them as parallel refinement algorithms.; Cette thèse porte sur le partitionnement parallèle de graphes et essentiellement sur son application à la renumérotation de matricescreuses.Nous utilisons pour résoudre ce problème un schéma multi-niveaux dont nous avons parallélisé les phases de contraction et d'expansion.Nous avons ainsi introduit pour la phase de contraction un nouvel algorithme de gestion des conflits d'appariements distants, tout enaméliorant les algorithmes déjà existants en leur associant une phasede sélection des communications les plus utiles.Concernant la phase d'expansion, nous avons introduit la notion de graphe bande qui permet de diminuer de manière très conséquente la taille du problème à traiter par les algorithmes de raffinement. Nous avons généralisé l'utilisation de ce graphe bande aux implantations séquentielles et parallèles de notre outil de partitionnement Scotch.Grâce à la présence du graphe bande, nous avons proposé une utilisation nouvelle des algorithmes génétiques dans le cadre del'expansion en les utilisant comme heuristiques parallèles de raffinement de la partition. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|