THÈSE

oN d’ordre : 3434 THÈSE PRÉSENTÉE À L’UNIVERSITÉ DE BORDEAUX I ÉCOLE DOCTORALE DE MATHÉMATIQUES ET D’INFORMATIQUE Par Cédric CHEVALIER POUR OBTENIR LE GRADE DE DOCTEUR SPÉCIALITÉ : INFORMATIQUE Conception et mise en œuvre d’outils efficaces pour le partitionnement et la distribution parallèles de problèmes numériques de très grande taille Soutenue le : 28 septembre 2007 Après avis des rapporteurs : Erik G. Boman ....... Scientist, SANDIA Stéphane Lanteri .... Directeur de recherche, INRIA Devant la commission d’examen composée de : Olivier Coulaud ...... Directeur de recherche, INRIA . Président & Rapporteur du Jury François Pellegrini .. Maître de conférence, ENSEIRB Directeur de Thèse Jean Roman .......... Professeur, ENSEIRB .......... de Jean-Christophe Weill Chercheur, CEA ............... Examinateur 2007iii Remerciements Tout d’abord, j’aimerais signaler que ces remerciements me tiennent vraiment à cœur, je regrette simplement qu’il me soit impossible d’être exhaustif sur le papier. Comme il s’agit quand-même de mon manuscrit de thèse, je voudrais commencer par re- mercier ceux qui ont accepté de le rapporter, Erik Boman et Stéphane Lanteri. Je les remercie aussi de m’avoir fait part de remarques judicieuses concernant la pré-version de ce document, et également d’avoir été présents à ma soutenance, en effectuant un voyage de près de 9000 kilomètres pour Erik. Je remercie également Jean-Christophe Weill et Olivier Coulaud d’avoir accepté d’être présents dans mon jury de thèse. Ensuite,etjecroisquejesuissonpremierthésardàpouvoirledire:),jeremercieJeanRoman pour avoir laissé son fameux stylo rouge au repos pour ma thèse. Ce qui ne l’a pas empêché, rassurez-vous, de m’indiquer des corrections. Je le remercie également pour plein d’autres choses, notamment ses conseils, qui sont d’ailleurs à l’origine de mon choix d’effectuer cette thèse. Vient maintenant le tour de remercier le dernier membre du jury, François Pellegrini, qui m’a encadré tout au long de cette thèse et même avant puisque cela avait commencé pour le DEA et aussi en cours à l’ENSEIRB. Il m’a réellement fait entrer dans le monde de la recherche, que ce soit avec l’aide de stylos (parfois rouge, et oui, il en faut quand même un) ou lors des voyages et des conférences. Sa disponibilité à des horaires tardifs a aussi permis de nombreuses fois que la recherche avance de manière (terriblement) efficace aux bons moments :). Pour continuer dans l’environnement de travail, je tiens à remercier les thésards qui m’ont chaleureusement accueilli au sein de l’équipe ScAlApplix lors de ma première année au Haut- Carré : Gaple, Pierre, Guillaume et mon homonyme Cédric. Le déménagement au LaBRI a permis d’intégrer d’autres personnes de qualité dans ce groupe « super sérieux », je pense notamment à Nico, Benji, Guilhem mais aussi à Martin. Je pense également aux petits jeunes qui m’ont aidé à garder le moral lors de la rédaction : Jérémie, Mathieu (×2), Adam, Robin et les divers stagiaires qui ont souffert pour la science;) (d’ailleurs on me fait signe qu’il reste des matches de catch à faire). Je n’oublie pas non plus les conseils avisés d’Orel, ni les discussions avec Abdou (sur la moto et O_DIRECT notamment!). Je tiens également à remercier très vivement le CNRS pour son financement (avec la région Aquitaine) et surtout, le plus important, son restaurant de Talence (qui hélas a tiré sa révérence enmêmetempsquemoi)pourlessucculentsrepasdontj’aipuprofitercesdeuxdernièresannées, et qui sont étonnamment à l’origine de pas mal d’idées. Merci aussi à mes amis qui m’ont tous permis de passer de bons moments, souvent malgré la distance. C’est aussi ce qui me fait penser que mon départ pour le Nouveau-Mexique va se dérouler sans accrocs (comme dirait un gouverneur californien); par contre, c’est pas une raison pour ne pas venir me voir là-bas! Je garderai de très bons souvenirs de ces dernières années de vie étudiante mais je rejoins confiant mes anciens compagnons ENSEIRBiens dans le monde « actif », en délaissant à regret mes voisin(e)s qui continuent leurs études. Je ne peux pas non plus parler des amis sans citer mes copains de lycée : Bob(o), Cédric (encore un!) et Vincent. De soirées grand Cinéma en restos en passant par des vacances à Royan, je leur dois de bons instants de détente et de bonnes rigolades, et ceci depuis maintenant plus d’une dizaine d’années. D’ailleurs, j’espère que nous ne cesserons jamais d’écouter et d’appliquer le conseil plein de sagesse du fabuleux Joe de Killer Crocodile : « On ne refuse jamais une bière. ». Maintenant vient le tour de ceux qui me supportent depuis le début (et même avant?), ma famille. Merci à mes parents de m’avoir toujours laissé libre dans mes choix tout en me soutenantiv et me conseillant constamment. Merci à ma grand-mère pour les week-ends (nourrissants!) de ressourcedanslacampagnelimousine.Unepenséeaussiàmesautresgrands-parentsquin’auront paspuassisteràlafindemesétudes.Maintenant,jepasselerelaisdesétudesàmasœurSandrine (bonne thèse!) et mes « petites » cousines Amandine et Laure. Cette page fait certes un peu liste de personnes, mais n’ayant pas les talents artistiques de Zlad ou des Fatals Picards, j’ai préféré ne pas me laisser tenter par des envolées lyriques que je ne maîtriserais pas. Pour finir, je remercie aussi toutes les personnes qui n’ont pas été citées mais qui auraient mérité de l’être. Bonne lecture, Cédric.v Conception et mise en œuvre d’outils efficaces pour le partition- nement et la distribution parallèles de problèmes numériques de très grande taille Résumé : Cette thèse porte sur le partitionnement parallèle de graphes et essentiellement sur son application à la renumérotation de matrices creuses. Nous utilisons pour résoudre ce problème un schéma multi-niveaux dont nous avons paral- lé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 en améliorant les algorithmes déjà existants en leur associant une phase de sélection des communications les plus utiles. Concernant la phase de d’expansion, nous avons introduit la notion de graphe bande qui per- met 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équen- tielles et parallèles de notre outil de partitionnement Scotch. Grâce à la présence du graphe bande, nous avons proposé une utilisation nouvelle des algo- rithmes génétiques dans le cadre de l’expansion en les utilisant comme heuristiques parallèles de raffinement de la partition. Mots clés : Parallélisme, partitionnement, renumérotation, matrice creuse, dissections emboîtées, multi- niveaux, heuristiques, contraction, expansion, optimisation locale, mémoire distribuée Discipline : Informatique 1LaBRI (UMR CNRS 5800) et Projet INRIA Futurs ScAlApplix , Université Bordeaux 1, 351, cours de la libération 33405 Talence Cedex, FRANCE 1 ScAlApplix : Schémas et Algorithmes Hautes Performances pour les Applications Scientifiques Complexes, http://www.labri.fr/scalapplix .vi Design and implementation of efficient tools for parallel partitio- ning and distribution of very large numerical problems Abstract : This thesis deals with parallel graph partitioning and, more specifically, focuses on its appli- cation to sparse matrix ordering. To solve this problem, we use a multi-level scheme, of which we have parallelized the coar- sening 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 theuseofbandgraphstothesequentialandparallelimplementationsofourScotchpartitioning tool. Basing on band graphs, we have proposed a new application of genetic algorithms to the uncoarsening phase, using them as parallel refinement algorithms. Keywords : Parallelism, partitioning, ordering, sparse matrix, nested dissection, multi-level, heuristics, coarsening, uncoarsening, local optimization, distributed memory Discipline : Computer science 2LaBRI (UMR CNRS 5800) et Projet INRIA Futurs ScAlApplix , Université Bordeaux 1, 351, cours de la libération 33405 Talence Cedex, FRANCE 2 ScAlApplix : Schémas et Algorithmes Hautes Performances pour les Applications Scientifiques Complexes, http://www.labri.fr/scalapplix .Table des matières Introduction générale 1 1 État de l’art et positionnement 3 1.1 Définitions et notations générales . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Vocabulaire et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Définitions sur les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 du partitionnement de graphes . . . . . . . . . . . . . . . . . . 8 1.2 Algorithmes utilisés pour let de graphes . . . . . . . . . . . . . . 10 1.2.1 L’approche spectrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2che combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 L’approche multi-niveaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.1 La phase de contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.2 Le partitionnement initial . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.3 La phase d’expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.4 Mise en œuvre parallèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.4.1 Vocabulaire du parallélisme . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.4.2 Formulation parallèle . . . . . . . . . . . . . . . . . . . . . . . . . .