Communications

L'arrivée de nombreuses machines parallèles ces dix dernières années a provoqué de nombreuses recherches dans le domaine des communications. Ces recherches ont été principalement articulées autour soit de projets de machines, soit de développement d'algorithmes parallèles pour des applications spécifiques.

On peut citer dans le premier cas le travail de l'équipe de C.Seitz à Caltech qui a determiné l'architecture des machines Intel et a popularisé la topologie en hypercube, ou plus récemment les travaux de Leiserson pour Thinking Machine Corp. sur l'architecture en Fat-tree de la CM-5.

L'étude des communications sur ces architectures a porté sur le routage et le problème de l'interblocage, comme dans le cas du routage wormhole introduit par Dally et Seitz dans le cadre du projet J-Machine au MIT. Elle a aussi concerné les algorithmes de communication globale; citons par exemple les travaux de Ho (IBM San Jose) et Johnson (Thinking Machine Corp.) ainsi que ceux de chercheurs du MIT, d'IBM-Yorktown, d'AT&T et de Bellcore ou de NTT au Japon.

L'étude des algorithmes sur ces machines, comme dans le cadre du calcul matriciel, consiste à résoudre des problèmes de communication globale sur des topologies données. Notons le travail de Leighton (MIT) sur l'algorithmique parallèle sur les hypercubes.

Pour programmer de manière efficace ces algorithmes parallèles, on a développé des outils et des environnements de programmation. Cependant il n'existe que des outils rudimentaires pour les protocoles de communications globales comme la diffusion, le multicast ou l'échange total, même si un effort a été entrepris sur ce point avec par exemple la librairie de communication PVM (équipe de Dongarra à UTK) qui est devenue un standard.

À travers les thèmes RUMEUR (et aussi CAPA) du GDR/PRC PRS, l'équipe de parallélisme de l'I3S a acquis une compétence et une reconnaissance internationale sur les problèmes de communication dans les réseaux. Elle a été à l'initiative ou un des éléments moteurs de plusieurs conférences internationales sur le sujet (IWIN par exemple), d'édition d'actes de conférences ou de numéros spéciaux, de plusieurs actions de coopérations (cf. 5). De nombreux articles ont été écrits en commun avec des chercheurs du monde entier. L'équipe participe à plusieurs comités d'édition (JPDC, Networks, PPL, Discrete Math., Discrete Applied Math., etc.).

Citons certains résultats :

• sur les problèmes de routage, de diffusion et de communications globales dans les réseaux d'interconnexion des machines parallèles [35][13][12][11];

• sur les nouvelles techniques de commutation de type «commutation de circuit» comme le «wormhole» qui sont employées sur les toutes dernières machines, en particulier les problèmes d'interblocage [15], de tolérance aux pannes et d'adaptativité;

• sur les protocoles de communication tels que la diffusion pour des architectures spécifiques comme les réseaux de de Bruijn [33][10], les hypercubes [18], les grilles toriques [34][16] ou les "Star-graphs" [17];

• sur l'étude des propriétés de certains réseaux classiques comme les réseaux de de Bruijn [14], les réseaux en boucles [7], ou plus récemment les réseaux à bus [8][9], et par la modélisation d'architectures hétérogènes comportant des connexions optiques dans le cadre du projet ILIAD (cf. 5.2).

Aujourd'hui, les recherches dans ce domaine sont de nature plus appliquée et l'équipe est prête à mettre en uvre tous ses acquis théoriques pour fournir des outils pratiques de communication [6] pour les deux autres composantes du projet (simulation et langages à objets). Ceci pourra être fait par exemple dans le cadre d'optimisations et d'ajouts à des librairies existantes comme PVM ou MPI. Par exemple dans le cas du Cray T3D ou de son successeur le T3E il est possible d'exploiter les résultats obtenus sur les communications globales en mode "circuit-switched" sur le tore pour améliorer les librairies de communication standard. De manière générale nous pourrons collaborer d'une part avec d'autres équipes pour toute application parallèle ou distribuée (en simulation bien entendu mais aussi en optimisation combinatoire, etc.) d'autre part avec des constructeurs de machines (coopération prévue avec le fournisseur de la future machine parallèle du centre de calcul).

De plus des réflexions sont menées actuellement au niveau international sur d'autres types de réseaux que ceux point à point, tant dans le domaine du parallélisme que des télécommunications. C'est le cas des réseaux par bus et des modèles classiques des liaisons optiques. L'expérience acquise permettra de donner de bons algorithmes quelles que soient les nouvelles architectures.