Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 11
Types de communications, topologies de connexion, SIMD, MIMD
Année 2002-2003

Putting multiple computers to work together, or in parallel, is apparently a straightforward way to increase the performance of computation. However, more than thirty years of parallel computing have shown that crossing the bridge from sequential to parallel computing has been far from simple because both the architecture and programming are substantially different.

      Livin Iftode
      thèse soutenue à l'université de Princeton (1998)

Mettre plusieurs ordinateurs à travailler ensemble ou en parallèle est apparemment la voie directe pour augmenter la capacité de calcul. Toutefois, plus de trente années de calcul parallèle ont montré que passer le pont qui mène de la programmation séquentielle à la programmation parallèle est tout sauf simple car et l'architecture et la programmation sont substantiellement différentes.

11.0 PRÉSENTATION

Nous avons vu que les taxinomies ou bien sont pauvres ou bien dont basées sur quelques caractéristiques choisies assez arbitrairement.
On aborde ici les multiprocesseurs, SIMD et MIMD via les moyens de communication qu'ils utilisent comme dit plus haut. Il s'agit des moyens vus dans leur organisation matérielle et dans leur fonctionnement.
Le modèle SIMD est le mieux identifié. Il a donné lieu à des réalisations anciennes et récentes, nous en traitons d'abord.
Les MIMD, plus complexes sont traités ensuite.
On examine les questions essentielles de maintien de la cohérence des données.
On finit par quelques autres types d'architectures.

Ce chapitre contient :

11.1 les architectures de communication
11.2 les topologies de connexion
11.3 un développement sur les machines SIMD dites vectorielles,
11.4 la communication par messages, communication spatiale,
11.5 la communication par la mémoire, communauté de mémoire, communication temporelle,
11.6 la place et l'incidence des caches,
11.7 les questions de cohérence,
11.8 d'autres machines parallèles,
11.9 un état du développement des machines parallèles,
11.10 des modèles mixtes ou composites.

11.1 LES ARCHITECTURES DE COMMUNICATION

Rendre simultanée l'exécution de séquences d'un programme, quels qu'en soient les modalités et l'architecture sur laquelle l'exécution est faite, reste conforme au modèle initial de Turing étendu par les propriétés d'assemblage. Toutefois, cela perturbe gravement le modèle séquentiel de Neumann car on passe outre à ses prescriptions 5 et 6. On entre dans un domaine à la fois valide en théorie et complexe en pratique.

Nous commençons par développer les notions relatives à la seule communication. Nous présenterons ensuite les différents voies par lesquelles on peut définir et organiser les MIMD, topologies de communication et structures de fonctionnement. Elles n'épuisent pas le sujet et ne prennent pas en compte les méthodes de programmation. On finira par l'examen des questions relatives à la cohérence des mémoires et à la surveillance des systèmes de communication.

Avertissement :
Le lecteur trouvera dans la suite encore plus de redites qu'à l'ordinaire. Elles sont nécessaires pour présenter sous des aspects différents une matière encore moins stabilisée que les précédentes.

Les moyens de communication. On a vu très brièvement les moyens principaux de communication entre processeurs et donc entre les processus qu'ils exécutent. Considérant une architecture parallèle comme une collection de processeurs communicants qui exécutent des processus coopérants à la résolution d'un problème, il vient normalement à l'esprit de définir et de caractériser ces architectures par leurs voies et moyens de communication.

Cette notion de communication dans une machine informatique est analysée dans les chapitre 16 et chapitre 17. On y établit la relation très forte qu'il y a entre la communication spatiale et la communication temporelle. Ces deux modes sont assemblés sous le nom de logistique qui devient la fonction prépondérante d'un ordinateur. Cette même notion existe ici.

Un câble, un bus sont des supports de communication Les mémoires sont aussi des supports de communication

Ces deux types de support fondent les archétypes des machines MIMD.
Les réalisations mêleront ces deux modes qui sont visibles sous trois aspects au moins :

• la communication abstraite, modèle des échanges entre processus;
• les moyens matériels proprement architecturaux de cette communication;
• les moyens logiciels qui sont fournis par le système d'exploitation, le langage ou l'environnement de programmation.

• l'interpellation directe de l'interlocuteur;
• le dépôt du contenu.

Plus rare est l'utilisation d'intermédiaires multiples comme le font les enfants dans une salle de classe : «le prof est bête, fais passer à Alfred» ou comme le font les adultes dans une réunion par un petit papier glissé au voisin à destination d'un autre.

Nous trouvons ces types de communication dans les machines MIMD présentées en utilisant le vocabulaire informatique.

• La communication directe par message ou passage de messages (message passing architecture) est une communication dans l'espace, transposition de l'interpellation verbale entre interlocuteurs (en vis-à-vis, par porte-voix, par téléphone, etc.). Le canal est spatial. Dans ce mode, chaque processeur peut transmettre des messages à chacun de ses voisins, processeurs connectés à un canal auquel il est relié. Ce canal peut être point à point, un bus, un commutateur, etc.  À chaque extrémité du canal se trouve un tampon de type temporel. Exemples : IBM SP-2, Intel Paragon, Cray T3E et T3D (parfois considéré comme étant à mémoire commune), Fujitsu VPP500, Meiko CS2.
• La mémoire commune souvent dite mémoire partagée (shared memory) fournit un moyen de communication dans le temps, transposition de la communication écrite par dépôt de contenu sur un tableau accessible aux deux interlocuteurs. Dans ce mode, chaque processeur lit et écrit à volonté pour ses propres besoins, sauf à gêner l'autre ou les autres. Le canal est temporel. La mémoire peut n'être pas accessible à tous dans toutes ses parties. Des zones peuvent être réservées à l'un ou à l'autre. L'arrivée dans la mémoire commune (l'écriture) et le départ (ma lecture) sont faits par un canal spatial. Exemples : SUN Enterprise 10000 serveur, Intel Pentium Pro «quad pack» quadriprocesseur, NEC SX, SGI Power Challenge, Fujitsu CP 2600 (parfois considéré comme processeur vectoriel), Hitachi S-3800, HP/Convex Exempler.
• Les autres moyens sont des combinaisons des deux modes précédents. Par exemple, la communication indirecte par message déposé en mémoire sous le nom bien trouvé de boite à lettres. Le message est accompagné ou non d'un signal au destinataire. Il est comparable au courrier ou au répondeur enregistreur. Le message est bien envoyé mais pas directement sous les sens du destinataire. La transmission peut utiliser des intermédiaires comme dans les réseaux.

Note 3
En faisant la communication via la mémoire, on rend la programmation simple; elle devient une extension de la programmation concurrente sur un processeur unique. Des difficultés apparaissent sous la forme du nécessaire maintien de la cohérence des données.

Une présentation succincte des deux programmations est faite dans le chapitre 12.

11.2 TOPOLOGIES DE CONNEXION

Ce paragraphe est consacré aux modèles de connexion ou d'interconnexion quels que soient les objets connectés. Ils peuvent être des processeurs, de la mémoire, des disques. Il s'agit aussi bien des organisations physiques que d'organisations logiques de connexion qui ont des propriétés différentes vis-à-vis des grands modes de fonctionnement des processeurs : vectoriel, messages et mémoire partagée. On inventorie des modèles simples :

• l'anneau, le cylindre et le tore;
• les maille, grille, filet ou réseau;
• les arbres;
• l'hypercube qui a des propriétés notables;
• la pyramide.

D'autres travaux ont été consacrés à la transposition, ou application d'une architecture sur une autre, en général dans le sens de la complexité croissante comme : appliquer un anneau ou une maille sur un hypercube.

11.2.1.1 L'anneau, le cylindre, le tore

L'anneau bien connu en informatique comme réseau local (anneau à jeton) est organisé ici de la même façon. On le trouve parfois en anneau simple avec un seul lien entre deux nœuds adjacents, parfois avec une paire de liens, en général spécialisés chacun pour une direction.

Des liens peuvent être insérés à l'intérieur de l'anneau formant un anneau chordal.

Des anneaux de même taille peuvent être superposés avec des liens à la verticale entre processeurs homologues, formant un cylindre.

Le bouclage des liaisons verticales forme un tore.

11.2.1.2 La maille ou grille ou filet ou réseau

La maille (mesh en anglais) est au départ une organisation plane. Il s'agit d'un tableau de lignes et de colonnes. Chaque intersection est un nœud, les liens sont du type quatre voisins en ligne et colonne. Une maille à trois dimensions est obtenue en superposant des mailles et en reliant les nœuds de même position à la verticale. Elle nécessite des nœuds à six liens.

11.2.1.3 Les arbres

Les arbres peuvent être quelconques, ici deux représentations d'arbres binaires :

Une variété d'arbre dit épais (fat tree) est parfois utilisée :

11.2.1.4 L'hypercube

On définit un hypercube comme suit :

• un hypercube de dimension n a 2ⁿ nœuds numérotés en binaire à partir de 0;
• deux nœuds sont adjacents si et seulement si leur numéro diffère d'un seul bit;
• alors le nombre d'adjacences pour la dimension n est de n2^n-1.

Dans un hypercube de dimension 4, le nœud 0010 est relié aux nœuds 1010, 0110, 0000, 0011.

On utilise le plus souvent les liens entre processeurs (liens série) apparus pour la première fois dans les transputeurs d'Inmos et maintenant généralisés en matière de traitement du signal pour réaliser ces liaisons. Toutefois, rien ne s'oppose dans le principe à ce que le lien soit concrétisé sous la forme de zones de mémoire partagées entre les processeurs deux à deux ou encore sous la forme d'un bus unique.

Le nombre de liens de chaque processeur définit de fait la taille ou diamètre de l'hypercube, quatre dans les transputeurs, six dans les DSP de la série TMS320C40 par exemple. Remarquons que l'on peut augmenter le diamètre de l'hypercube réalisable en formant un amas de processeurs. Par exemple, prenons des processeurs à six liens, formons des amas de deux processeurs reliés par un lien, il restera dix liens disponibles pour l'amas. On pourra construire un hypercube de diamètre 10, dont les nœuds seront des biprocesseurs. On utilisera ce biprocesseur de manière symétrique ou asymétrique.

On remarque que le câblage devient rapidement important si l'on veut le réaliser point à point. Un hypercube de diamètre 6 a 6x2⁵ soit 192 liens. Rien n'empêche de simuler un hypercube au moyen d'un commutateur.

Un hypercube à 16 dimensions a 65536 nœuds.

Quelques mots sur les propriétés de l'hypercube qui sont nombreuses.

• Un hypercube de dimension n peut être construit de façon récursive à partir d'un hypercube de dimension n-1. Cette propriété est incluse dans la numérotation des nœuds. On passe par exemple de 00 01 11 10 à 000 001 011 010 et 100 101 111 1011 1010. Cette propriété rend aisée la construction d'architectures modulaires évolutives (scalability).
• Tout hypercube de diamètre n peut être décomposé de n façons différentes en deux hypercubes de diamètre n-1. Ceci facilite le placement des tâches (cf. chapitre 12) et la diffusion des données.
• Il y a n!2ⁿ façons de numéroter les 2ⁿ nœuds d'un hypercube. Cette variété est utilisable pour écrire des programmes dans lesquels des modifications se réduiront à des changements d'adresses plutôt qu'à devoir refaire des connexions.
• Un hypercube est un graphe connexe de diamètre n, tout nœud est atteignable à partir de n'importe quel autre. La distance est minimale entre les nœuds les plus éloignés par rapport à toute autre topologie.
• Si deux nœuds A et B sont adjacents, les autres nœuds adjacents à chacun sont connectés deux à deux, cette disposition est souvent utilisée pour des processus coopérant étroitement.
• Il n'y a pas de cycles de longueur impaire dans un hypercube, etc.

Une pyramide est une construction faite à partir de blocs de base comprenant chacun un père et en général quatre fils connectés entre eux en maille. On peut construire des blocs à trois fils ou plus encore mais alors reliés en anneaux. Les blocs sont connectés de telle sorte qu'un fils du premier devienne père du bloc suivant.

11.2.2 Modèles complexes

Pour l'essentiel, ils sont deux :

. la matrice d'interconnexion, un commutateur dit aussi crossbar reliant toute voie d'entrée à n'importe quel circuit sortant.

. les réseaux quelconques qui ne relèvent pas d'un modèle prédéfini.