Robert
le 9 Novembre 2000 à 14h30
salle Firtech ()
(LIP - ENS de Lyon, et École Polytechnique)
Algorithmique parallèle hétérogène
Résumé/Abstract :
L'hétérogénéité va être une
caractéristique majeure des plateformes de calcul de demain,
des plus modestes (le réseau Ethernet des multiples PC
et stations de travail d'un laboratoire ou d'une entreprise) aux plus
onéreuses (la fameuse "metacomputing grid").
Cet exposé s'attache à montrer toute la difficulté de
l'algorithmique parallèle sur machine hétérogène.
À partir d'exemples simples issus de l'algèbre linéaire,
on montrera
- les limites des stratégies dynamiques d'allocation des
données et des calculs,
- l'impérieuse nécessité des approches statiques,
- et la difficulté de ces dernières.
En effet, équilibrage de charge et minimisation des communications
s'avèrent intrinsèquement plus difficiles que dans le cas
homogène. Des problèmes aussi simples que la multiplication
de deux matrices conduisent à des résultats de
NP-complétude, et exigent un recours à des distributions
sophistiquées qui vont bien au-delà du simple CYCLIC(r)
de ScaLAPACK.
Travail réalisé en commun avec Olivier Beaumont, Vincent Boudet,
Arnaud Legrand et Fabrice Rastello, dans le cadre du projet CNRS - INRIA ReMaP.