Méthodes de partition de données pour améliorer le temps de tri sur grappes hétérogènes

Cet article, co-écrit avec Christophe Cérin et Jean-Louis Roch, introduit plusieurs techniques d’optimisation du temps d’exécution parallèle d’un tri distribué sur une grappe de calcul dont les processeurs sont hétérogènes. Le tri nécessite une répartition préalable des données — nous nous intéressons ici à une répartition préalable des données à trier (ou autre calcul similaire).

Dans le cas où les vitesses des processeurs sont linéairement dépendantes (un processeur travaille à une vitesse qui est un facteur individuel multiplié par une vitesse de base), nous proposons une méthode analytique de répartition optimale des données dans le cas où la complexité de la fonction de calcul estconnue et un cadre algorithmique de répartition dans le cas où la complexité de la fonction est inconnue, mais où plusieurs séries de calcul sont à effectuer.

Dans le cas où les processeurs ne sont pas liés linéairement, nous utilisons une technique fondée sur la programmmation dynamique.

La plupart du temps, nos solutions de partition ajoutent un temps de traitement en $\mathcal{O}(p)$ où p est le nombre de processeurs disponibles.

Quelques mots sur le contenu

Cet article est le fruit de deux réflexions un peu indépendantes sur le même thème, qui ont été fédérées par Christophe Cérin (on voit bien d’ailleurs les trois styles d’écriture dans l’article, pas très homogène). C’est moi qui ai gagné le droit de faire le voyage jusqu’à Taïwan pour présenter l’article.

J’ai mis à côté de l’article les diapositives que j’ai utilisé lors de la présentation.

Citer ce document

Cet article a été publié dans les actes de la conférence GPC 2006, qui s’est déroulée cette année-là à Taichung, Taïwan.

@InProceedings{cdr06,
author = 	 {Christophe C\'erin and Jean-Christophe Dubacq and Jean-Louis Roch},
title = 	 {Methods for Partitioning Data to Improve Parallel Execution Time for Sorting on Heterogeneous Clusters},
booktitle =      {Advances in Grid and Pervasive Computing},
pages = 	 {175--186},
year = 	         {2006},
editor = 	 {Yeh-Ching Chung and Jos\'{e} E. Moreira},
volume = 	 {3947},
series = 	 {Lecture Notes in Computer Science},
month = 	 may,
publisher =      {Springer},
isbn =           {3-540-33809-8}
}

Jean-Christophe Dubacq