A9. Conception et implantation d'algorithmes numériques parallèles

L'objectif du projet "Algorithmes numériques parallèles" (Contrat IT/IF/14) était la conception, le développement et l'implantation d'algorithmes numériques parallèles d'intérêt général dans les applications industrielles.

La difficulté majeure des grosses applications industrielles, c'est-à-dire celles qui motivent le recours aux architectures parallèles, réside dans la mise au point de solveurs linéaires efficaces et plus spécifiquement de solveurs linéaires itératifs efficaces et les difficultés de parallélisation de ces solveurs sont à localiser au niveau de la parallélisation du préconditionnement.

Il s'agit là de la parallélisation d'un solveur linéaire direct mais approché. Il est souhaitable que cette approximation soit bonne (entraînant un moindre nombre d'itérations) mais d'exécution rapide (entraînant un moindre coût par itération).

C'est principalement à ce problème central que nous nous sommes attaqués, tout en ne négligeant pas les aspects auxiliaires tels que la discrétisation ou les simulations du type Monte Carlo, dont nous ne parlons que peu dans ce rapport parce que ces aspects n'ont pas soulevé de gros problèmes de parallélisation.

La parallélisation repose sur la définition d'un ordre de numérotation des inconnues par niveaux tel que les inconnues d'un même niveau n'aient pas de connexions entre elles et puissent donc être traitées en parallèle.

Mais l'ordre de numérotation choisi peut avoir une influence importante sur la précision (c'est-à-dire l'efficacité) du préconditionneur. Pas toujours cependant : dans le cas des méthodes de Jacobi ou de Schwarz, cet ordre n'a pas d'influence et ces méthodes se prêtent bien à une parallélisation efficace et peuvent dès lors servir de référence. (La méthode de Jacobi est très peu coûteuse mais très peu efficace; la méthode de Schwarz est, moyennant quelques perfectionnements, très efficace mais très coûteuse).

Il est donc important d'étudier l'influence de l'ordre sur le conditionnement (pour des ordres à degré de parallélisme élevé). Nous avons abouti à de nombreux résultats dans ce domaine par la définition d'ordres et de stratégies de conditionnement tels que les ordres consistants avec perturbations non diagonales, les ordres S/P consistants, les ordres de Kutcherov Makarov et les ordres du type rouge-noir récursif. Non seulement ces ordres sont à degré de parallélisme élevé mais ils améliorent en outre l'efficacité du préconditionnement.

Nous n'avons pas eu de succès lors de l'implantation de ces stratégies d'ordonnancement sur Connection Machine. Cependant, nous avons récemment appris que d'autres groupes avaient réussi à en tirer parti sur des architectures à mémoire partagée. La conclusion à en tirer est que, sur les architectures parallèles à mémoire distribuées actuellement disponibles, il ne suffit pas de mettre au point des ordres à degré de parallélisme élevé. Il faut en outre rencontrer le problème de la lenteur des communications sur ces architectures. Il faut donc minimiser les communications.

Ce deuxième problème représente une limitation importante imposée par les architectures actuelles et l'on ne saurait trop insister sur l'importance qu'il y a à progresser dans ce domaine, de façon à pouvoir utiliser des algorithmes plus efficaces.

Nous avons attaqué ce deuxième problème par l'emploi de partitionnements et de recouvrements définis soit géométriquement (décomposition de domaine), soit algébriquement (détermination de séparateurs dans les graphes matriciels) et par le développement d'une implantation parallèle spécifique des méthodes de factorisation approchée utilisant des recouvrements minimaux et n'exigeant que légèrement plus de communications que la méthode de Jacobi moins en général que celle de Schwarz, qui utilise des recouvrements plus importants) .

L'emploi des partitionnements a été développé par S. BOUSRI pour des applications industrielles en théorie des réacteurs nucléaires et par M.M. MAGOLU pour la parallélisation des méthodes de factorisation par blocs . Dans les deux cas, il s'agit d'implantations MIMD sur grappe IBM à l'ULB et sur GCel de Parsytec à l'IC3A. Les gains relevés par BOUSRI sont particulièrement élevés, conduisant typiquement à des "speedups" de l'ordre de 16 pour 36 processeurs. Les gains relevés par MAGOLU sont moins spectaculaires mais restent très intéressants, de l'ordre de 4 pour 32 processeurs.

L'emploi des recouvrements a été développé par Y. NOTAY et Z. OULD AMAR pour la parallélisation des méthodes de factorisation ponctuelles. Y. NOTAY a inventé une technique d'implantation originale, qui, comme nous l'avons déjà mentionné, ne requiert que légèrement plus de communications que la méthode de Jacobi et l'a appliquée aux architectures MIMD. Il a typiquement observé des speedups de l'ordre de 5 à 200 ou plus pour des grilles de 8 à 512 processeurs (sur GCel) tandis que la comparaison, plus sévère, avec le préconditionnement de Jacobi, montre des gains de temps CPU d'un facteur pouvant atteindre 10 pour les gros problèmes.

Z. OULD AMAR a adapté cette technique d'implantation aux architectures SIMD et a relevé des gains en temps CPU d'un facteur pouvant atteindre 3 par rapport au préconditionnement de Jacobi sur Connection Machine. A notre connaissance, c'est la première implantation qui réussit à faire nettement mieux que le préconditionnement de Jacobi sur Connection Machine sans recourir à la solution de problèmes hautement anisotropes ou fortement discontinus (qui handicapent la méthode de Jacobi).

Au cours de ces recherches, nous avons développé plusieurs logiciels dont une partie est déjà mise en accès public et accessible par ftp anonyme. Nous avons également développé notre collaboration industrielle et nos contacts internationaux. Sur ce dernier plan, notre équipe s'est acquis une position internationale reconnue.