Graph partitioning is a technique used for solving many problems in scientific computing, such as the decomposition of a mesh into domains so as to evenly balance the compute load on the processors of a parallel architecture. Because of the ever increasing size of the meshes to handle, partitioning tools themselves had to be parallelized. The parallel versions of these software provide good results for and on several thousands of processors, but the advent of architectures comprising more than a million processing elements raises new problems. Not only do the partitioning results produced by these software have to take into account the heterogeneity of these architectures, but also does the efficient execution of the partitioning software on these architectures require much more sophisticated algorithms. The purpose of this note is to present the challenges to overcome in order to reach these goals.

Le partitionnement de graphes est une technique utilisée pour la résolution de nombreux problèmes en calcul scientifique, tels que la décomposition d'un maillage en sous-domaines pour répartir la charge de calcul sur les processeurs d'une architecture parallèle. La taille des maillages à traiter augmentant sans cesse, les logiciels de partitionnement ont eux-mêmes dû être parallélisés. Les versions parallèles de ces logiciels fournissent de bons résultats sur et pour plusieurs milliers de processeurs, mais l'arrivée imminente d'architectures hétérogènes comprenant plus d'un million d'unités de traitement pose de nouveaux problèmes. Non seulement les résultats de partitionnement produits par ces logiciels doivent-ils tenir compte de l'hétérogénéité de ces architectures, mais l'exécution efficace du logiciel de partitionnement sur cette même architecture doit-elle nécessiter une algorithmique bien plus sophistiquée. L'objet de cette note est de présenter les défis à surmonter afin d'atteindre ces objectifs.