Sujet : Conception et mise en oeuvre de méthodes et d'outils efficaces
pour le partitionnement et la distribution parallèles de problèmes
numériques de très grande taille

Responsable : François Pellegrini et Jean Roman
Téléphone : 05 40 00 37 93 et 05 40 00 69 36
e-mail : pelegrin@labri.fr, roman@labri.fr
Site Web : http://www.labri.fr/scalapplix
Equipe : Projet INRIA Futurs ScAlApplix

Présentation du sujet :


Du fait des quantités considérables de données et de calculs
mises en jeu, la résolution des simulations numériques en vraie
grandeur imaginées aujourd'hui par les chercheurs (issues par exemple
de l'utilisation de lasers hautes énergies, ou relatives à des
problèmes de dynamique moléculaire ou d'environnement) n'est
réalisable qu'en ayant recours au calcul parallèle haute performance
au sens large. Pour cela, il est nécessaire de pouvoir décomposer
efficacement et distribuer de façon équilibrée dans le temps et sur
l'ensemble des processeurs les données et les calculs associés à
traiter.
Une approche très efficace pour résoudre ce problème consiste
à utiliser des techniques de partitionnement de graphes, graphes qui
modélisent finement l'application à paralléliser. Si, à l'heure
actuelle, il existe des techniques séquentielles efficaces de
partitionnement, le partitionnement parallèle, rendu lui aussi
indispensable du fait de l'augmentation de la taille des problèmes (le
graphe modélisant le problème n'est plus stockable sur une seule
machine), est loin d'être aussi performant. Les différentes tentatives
menées à ce jour ne sont pas réellement concluantes, car trop
fortement basées sur des adaptations des algorithmes séquentiels
existants et qui se parallélisent mal.

L'objectif de cette thèse est donc de rechercher des
méthodes intrinsèquement parallèles efficaces de partitonnement de
grands graphes irréguliers basées sur des multi-critères, et de les
valider au sein d'outils facilement intégrables au sein des grands
codes numériques parallèles traitant de challenges numériques actuels
(problèmes issus de collaborations avec le CEA/CESTA et le
CEA-Ile-de-France comme par exemple l'endommagement laser; problèmes
de parasitologie de la vigne avec l'INRA, ...). On considèrera aussi
le problème du repartitionnement dynamique de graphe qui est
stratégique quand on traite d'un problème ayant une structure
évolutive, ou quand on considère l'équilibrage de charge dynamique pour
des plateformes hétérogènes de type grille de calcul.


Mot-clés : Algorithmique et calcul haute performance, applications complexes multi physiques
et multi échelles, grandes grappes et grilles de calcul, partitionnement
statique et dynamique de grands graphes irréguliers