Previous Up Next

Chapter 8  Communications et routage

8.1  Généralités

On distingue généralement les topologies statiques où le réseau d'interconnexion est fixe, en anneau, tore 2D, hypercube, graphe complet etc. des topologies dynamiques, modifiées en cours d'exécution (par configuration de switch).

Chaque topologie de communication a des caractéristiques spécifiques, qui permettent de discuter de leurs qualités et de leurs défauts. Ces caractéristiques sont, en fonction du nombre de processeurs interconnectés, le degré du graphe d'interconnection, c'est-à-dire le nombre de processeurs interconnectés avec un processeur donné, le diamètre, c'est-à-dire la distance maximale entre deux noeuds, et le nombre total de liens, c'est-à-dire le nombre total de ``fils'' reliant les différents processeurs. Les topologies de communications avec un petit nombre de liens sont plus économiques mais en général leur diamètre est plus important, c'est-à-dire que le temps de communication entre deux processeurs ``éloignés'' va être plus important. Enfin, on verra un peu plus loin que le degré est également une mesure importante: cela permet d'avoir plus de choix pour ``router'' un message transitant par un noeud. On imagine bien également (thème développé au chapitre 11, mais sous un autre point de vue), que si on a une panne au niveau d'un lien, ou d'un processeur, plus le degré est important, plus on pourra trouver un autre chemin pour faire transiter un message. Les caractéristiques de quelques topologies statiques classiques sont résumées dans le tableau ci-dessous:
Topologie # proc. do diam. # liens
Complet p p-1 1 p(p-1)/2
Anneau p 2 ë p/2 û p
Grille 2D sqrt(p)sqrt(p) 2,3,4 2(sqrt(p)-1) 2p-2sqrt(p)
Tore 2D sqrt(p)sqrt(p) 4 2 ë sqrt(p)/2 û 2p
Hypercube p=2d d=log(p) d p log(p)/2

L'intérêt est relatif, pour chaque choix. Par exemple, le réseau complet est idéal pour le temps de communications (toujours unitaire) mais le passage à l'échelle est difficile! (prix du cablage, comment rajouter des nouveaux processeurs?). La topologie en anneau n'est pas chère, mais les communications sont lentes, et la tolérance aux pannes des liens est faible. On considère généralement que le tore 2D ou l'hypercube sont de bons compromis entre ces deux architectures.

8.2  Routage

On distingue deux modèles principaux, pour le routage des messages dans un système distribué. Chaque modèle a un calcul de coût de communication distinct.

Le premier modèle est le modèle ``Store and Forward'' (SF): chaque processeur intermédiaire reçoit et stocke le message M avant de le re-émettre en direction du processeur destinataire. C'est un modèle à commutation de message qui équipait les premières générations de machines. Le coût de communication est de d(x,y)(b+Lt) (où d(x,y) est la distance entre les machines x et y, t est lié au débit du réseau, b est la latence d'un envoi de message, et L est la longueur du message) sauf programmation particulièrement optimisée (voir section 8.3.5) où on peut atteindre Lt + O(sqrt(L)).

Le modèle ``cut-through'' (CT) utilise un co-processeur de communication associé à chaque noeud. Le coût de communication est de b+(d(x,y)-1)d+Lt (où d est encore une fois lié au débit du réseau, t est la latence). Si d << b, le chemin est calculé par le matériel, la partie logicielle étant dans le facteur b.

Il existe également deux principaux protocoles de routage: ``Circuit-switching'' (CC - ou ``commutation de données'') et ``Wormhole'' (WH).

Le circuit-switching crée le chemin avant l'émission des premiers octets. Le message est ensuite acheminé directement entre source et destinataire. Cela nécessite une immobilisation des liens (cas par exemple de l'iPSC d'INTEL).

Le protocole Wormhole place l'adresse du destinataire dans l'entête du message. Le routage se fait sur chaque processeur et le message est découpé en petits paquets appelés flits. En cas de blocage: les flits sont stockés dans les registres internes des routeurs intermédiaires (exemple, Paragon d'INTEL).

En général, CC et WH sont plus efficaces que SF. Ils masquent la distance entre les processeurs communiquants. CC contruit son chemin avant l'envoi des premiers paquets de données alors que WH construit sa route tandis que le message avance dans le réseau (meilleure bande passante que CC). Ces points sont résumés à la figure 8.1.


Figure 8.1: Comparaison CC, WH et SF


8.3  Algorithmique sur anneau de processeurs

8.3.1  Hypothèses

On étude une architecture dans laquelle (voir figure 8.2 pour une explication graphique) on a p processeurs en anneau, chacun ayant accès à son numéro d'ordre (entre 0 et p-1), par my_num() et au nombre total de processeur par tot_proc_num (=p).


Figure 8.2: Architecture en anneau


En mode SPMD, tous les processeurs exécutent le même code, ils calculent tous dans leur mémoire locale, et ils peuvent envoyer un message au processeur de numéro proc_num()+1[p] par send(adr,L). La variable adr contient l'adresse de la première valeur dans la mémoire locale de l'expéditeur et L est la longueur du message. De même, ils peuvent recevoir un message de proc_num()-1[p] par receive(adr,L).

Le premier problème auquel on est confronté, avant même de penser à implémenter des algorithmes efficaces, est de s'arranger pour qu'à tout send corresponde un receive.

On peut faire plusieurs hypothèses possibles pour décrire la sémantique de telles primitives. Les send et receive peuvent être bloquants comme dans OCCAM. Plus classiquement, send est non bloquant mais receive est bloquant (mode par défaut en PVM, MPI). Sur des machines plus modernes, aucune opération n'est bloquante (trois threads sont utilisés en fait: un pour le calcul, un pour le send et un pour le receive).

La modélisation du coût d'une communication est difficile en général: ici envoyer ou recevoir un message de longueur L (au voisin immédiat) coûtera b+Ltb est le coût d'initialisation (latence) et t (débit) mesure la vitesse de transmission en régime permanent. Donc, a priori, envoyer ou recevoir un message de longueur L de proc_num()+/-q coûtera q(b+Lt). On verra que dans certains cas, on peut améliorer les performances de communication en ``recouvrant'' plusieurs communications au même moment (entre des paires de processeurs distincts).

8.3.2  Problème élémentaire: la diffusion

C'est l'envoi par un Pk d'un message de longueur L (stocké à l'adresse adr) à tous les autres processeurs. C'est une primitive implémentée de façon efficace dans la plupart des librairies de communications (PVM, MPI etc.). On va supposer ici que le receive est bloquant.
broadcast(k,adr,L) { // emetteur initial=k
  q = my_num();
  p = tot_proc_num();
  if (q == k) 
    (1) send(adr,L);       
  else
    if (q == k-1 mod p)
      (2) receive(adr,L);  
    else {
      (3) receive(adr,L);  
      (4) send(adr,L);      
    } 
}
L'exécution est décrite pour k=0 au temps 0 à la figure 8.3, au temps b+Lt à la figure 8.4, au temps j(b+Lt) (j<p-1) à la figure 8.5, et au temps (p-1)(b+Lt) à la figure 8.6.


Figure 8.3: Exécution de la diffusion sur un anneau au temps 0.




Figure 8.4: Exécution de la diffusion sur un anneau au temps b+Lt.




Figure 8.5: Exécution de la diffusion sur un anneau au temps i(b+Lt) (i<p-1).




Figure 8.6: Exécution de la diffusion sur un anneau au temps (p-1)(b+Lt).


8.3.3  Diffusion personnalisée

On suppose toujours ici un send non-bloquant et un receive bloquant. On veut programmer un envoi par Pk d'un message différent à tous les processeurs (en adr[q] dans Pk pour Pq). A la fin, chaque processeur devra avoir son message à la location adr. L'algorithme suivant opère en pipeline, et on obtient une bonne performance grâce à un recouvrement entre les différentes communications!

Le programmme est le suivant:
scatter(k,adr,L) {
  q = my_num();
  p = tot_proc_num();
  if (q == k) {
    adr = adr[k];
    for (i=1;i<p;i=i+1)
      send(adr[k-i mod p],L); }
  else 
    (1) receive(adr,L);
  for (i=1;i<k-q mod p;i = i+1) {
    (2) send(adr,L); 
    (3) receive(temp,L);
    adr = temp; } }
Les exécutions pour k=0 aux temps 0 b+Lt, i(b+Lt) et enfin (p-1)(b+Lt), sont représentées respectivement aux figures 8.7, 8.8, 8.9 et 8.10.


Figure 8.7: Exécution de la diffusion personnalisée au temps 0.




Figure 8.8: Exécution de la diffusion personnalisée au temps b+Lt.




Figure 8.9: Exécution de la diffusion personnalisée au temps i(b+Lt).




Figure 8.10: Exécution de la diffusion personnalisée au temps (p-1)(b+Lt).


8.3.4  Echange total

Maintenant, chaque processeur k veut envoyer un message à tous les autres. Au départ chaque processeur dispose de son message à envoyer à tous les autres à la location my_adr. A la fin, tous ont un tableau (le même) adr[] tel que adr[q] contient le message envoyé par le processeur q. Il se trouve que par la même technique de recouvrement des communications, cela peut se faire aussi en (p-1)(b+Lt) (et de même pour l'échange total personnalisé, voir [RL03]). Le programme est:
all-to-all(my_adr,adr,L) {
  q = my_num();
  p = tot_proc_num();
  adr[q] == my_adr;
  for (i=1;i<p;i++) {
    send(adr[q-i+1 mod p],L);
    receive(adr[q-i mod p],L);
  }
}

8.3.5  Diffusion pipelinée

Les temps d'une diffusion simple et d'une diffusion personnalisée sont les mêmes; peut-on améliorer le temps de la diffusion simple en utilisant les idées de la diffusion personnalisée? La réponse est oui: il suffit de tronçonner le message à envoyer en r morceaux (r divise L bien choisi). L'émetteur envoie successivement les r morceaux, avec recouvrement partiel des communications. Au début, ces morceaux de messages sont dans adr[1],...,adr[r] du processeur k. Le programme est:
broadcast(k,adr,L) {
  q = my_num();
  p = tot_proc_num();
  if (q == k)
    for (i=1;i<=r;i++) send(adr[i],L/r);
  else
    if (q == k-1 mod p)
      for (i=1;i<=r;i++) receive(adr[i],L/r);
    else {
      receive(adr[1],L/r);
      for (i=1;i<r;i++) {
        send(adr[i],L/r);
        receive(adr[i+1],L/r); } } }
Le temps d'exécution se calcule ainsi; le premier morceau de longueur L/r du message sera arrivé au dernier processeur k-1 mod p en temps (p-1)(b+L/rt) (diffusion simple). Les r-1 autres morceaux arrivent les uns derrière les autres, d'où un temps supplémentaire de (r-1)(b+L/rt). En tout, cela fait un temps de (p-2+r)(b+L/r t).

On peut maintenant optimiser le paramètre r. On trouve ropt=sqrtL(p-2)t/b. Le temps optimal d'exécution est donc de
( sqrt(p-2)b+sqrtLt ) 2
Quand L tend vers l'infini, ceci est asymptotiquement équivalent à Lt, le facteur p devient négligeable!

8.4  Election dans un anneau bidirectionnel

Chaque processeur part avec un identificateur propre (un entier dans notre cas), et au bout d'un temps fini, on veut que chaque processeur termine avec l'identificateur d'un même processeur, qui deviendra ainsi le ``leader''.

Dans la suite, les processeurs vont être organisés en anneau bidirectionnel synchrone:

8.4.1  Algorithme de Le Lann, Chang et Roberts (LCR)

Dans cet algorithme, chaque processeur va essentiellement essayer de diffuser son identificateur aux autres processus. Le processus ayant l'identificateur le plus grand deviendra leader.

Les messages doivent tous transiter dans le même sens, soit +, soit -.

Au lieu de faire une diffusion complète, on peut s'arranger pour que quand un processus reçoit un identificateur, il le compare avec le sien: si celui qu'il a reçu est strictement plus grand que le sien, il continue à le passer sur le réseau. S'il est égal à son identificateur, il se déclare leader, sinon il ne fait rien. On enlève ainsi certaines communications inutiles.

Chaque processus fait:
LCR() {
  send(pid,1,+);
  while (recv(newpid,1,+)) {
    if (newpid==pid)
      leader = 1;
    else if (newpid>pid)
           send(newpid,1,+);
  }
}
Cet algorithme permet bien d'élire un leader. En effet, soit imax le numéro du processeur ayant l'identificateur pidimax maximal. Soit 0 £ r £ n-1. On peut voir facilement par induction sur r que après r étapes, la valeur de newpid sur le processeur Pimax+r est pidimax. Ainsi, à l'étape n, Pimax+n=Pimax aura reçu son numéro d'identificateur et en déduira qu'il est le leader.

Il faut maintenant voir que personne d'autre ne croit être le leader. On peut voir par induction sur r que pour toute étape r, pour tous i et j, si i ¹ imax et imax £ j < i, alors Pj envoie un message différent de pidi. Alors nécessairement, seul Pimax peut recevoir son propre identificateur, et est donc le seul leader possible.

Il faut n étapes et O(n2) communications.

Remarquez que l'on peut relâcher l'hypothèse synchrone et se contenter d'un send non bloquant et d'un recv bloquant, sans aucun changement dans l'algorithme.

8.4.2  Algorithme de Hirschberg et Sinclair (HS)

Cet algorithme fonctionne informellement de la façon suivante: Les tokens utilisés dans cet algorithme contiennent un identificateur, mais aussi un drapeau indiquant si le message est dans la phase envoi ou dans la phase retour, et un compteur (entier), indiquant la distance qu'il reste à parcourir dans la phase envoi avant de passer à la phase retour. On n'essaiera pas de coder ces tokens, et on se contentera d'utiliser les fonctions (que l'on supposera programmées par ailleurs) suivantes: Le pseudo-code correspondant, pour l'algorithme HS, est alors:
HS() {
  boolean leader, continuephase;
  int l;
  token plus, moins;
  l = 0;
  leader = false;
  
  continuephase = true;

  while (continuephase) {
    send(token(l,pid),L,+);
    send(token(l,pid),L,-);
    continuephase = false;

    while () {
      if (recv(plus,L,+)) {
        if (not retour(plus)) {
          if (valeur(plus) > pid) {
            plus = incr(plus);
            if (retour(plus))
              send(plus,L,-);
            else
              send(plus,L,+);
          }
          else if (valeur(plus) == pid) {
                 leader = true;
                 System.exit(0);
               }
        }
       else
         if (valeur(plus) == pid) {
           l = l+1;
           continuephase = true;
         }
         else 
           send(incr(plus),L,-);

      if (recv(moins,L,-)) {
        if (not retour(moins)) {
          if (valeur(moins) > pid) {
            plus = incr(moins);
            if (retour(moins))
              send(moins,L,+);
            else
              send(moins,L,-);
          }
          else if (valeur(moins) == pid) {
                 leader = true;
                 System.exit(0);
               }
        }
       else
         if (valeur(moins) == pid) {
           l = l+1;
           continuephase = true;
         }
         else 
           send(incr(moins),L,+);
      }
  }
}
Le nombre total de phases exécutées au maximum avant qu'un leader ne soit élu est évidemment borné par 1+é log n ù, car si on a un processeur qui arrive à l'étape é log n ù, il est nécessaire que son pid soit plus grand que tous les autres, comme 2é log n ù³ n.

Le temps mis par cet algorithme est donc de O(n). En effet, chaque phase l coûte au plus 2l+1 (c'est le nombre de recv maximum que l'on peut avoir dans cette phase, en même temps par tous les processeurs impliqués dans cette phase). En sommant sur les O(log n) phases, on trouve O(n).

A la phase 0, chaque processus envoie un token dans chaque direction à la distance 1. Donc au maximum, il y a 4n messages à cette phase (2n aller, et 2n retour).

Pour une phase l > 0, un processus envoie un token seulement si il a reçu un des deux tokens qu'il a envoyés à la phase l-1. Ce n'est le cas que si il n'a pas trouvé de processeur de pid supérieur à une distance au maximum de 2l-1, dans chaque direction sur l'anneau. Cela implique que dans tout groupe de 2l-1+1 processeurs consécutifs, un au plus va commencer une phase l. Donc on aura au plus
ê
ê
ê
ë
n
2l-1+1
ú
ú
ú
û
processeurs entrant en phase l. Donc le nombre total de messages envoyés en phase l sera borné (car chaque token envoyé parcourt au plus 2l processeurs) par:
4 æ
ç
ç
è
2l ê
ê
ê
ë
n
2l-1+1
ú
ú
ú
û
ö
÷
÷
ø
£ 8n

Comme on a un nombre de phases en O(log n), on en déduit un nombre de communications de l'ordre de O(n log(n)).

On a moins de communications, et l'algorithme sera meilleur que LCR si le débit des canaux est faible (moins de contention de messages).

8.5  Communications dans un hypercube

On va examiner successivement les chemins de communication et en déduire les façon de router les messages dans un hypercube, puis appliquer tout cela au problème du broadcast dans un hypercube.

8.5.1  Chemins dans un hypercube

Un m-cube est la donnée de sommets numérotés de 0 à 2m-1. Il existe une arête d'un sommet à un autre si les deux diffèrent seulement d'un bit dans leur écriture binaire.

Par exemple, un 2-cube est le carré suivant:
00 ®0 01
¯1 ¯1
10 ®0 11

où les numéros sur les arcs indiquent le numéro du lien (ou du canal) sortant du noeud correspondant.

Soient A, B deux sommets d'un m-cube, et H(A,B) leur distance de Hamming (le nombre de bits qui diffèrent dans l'écriture). Alors il existe un chemin de longueur H(A,B) entre A et B (récurrence facile sur H(A,B)). En fait, il existe H(A,B)! chemins entre A et B, dont seuls H(A,B) sont indépendants (c'est-à-dire qu'ils passent par des sommets différents).

Un routage possible est le suivant. On ``corrige'' les bits de poids faibles d'abord. Par exemple, pour A=1011, B=1101, on fait: A xor B=0110 (ou exclusif bit à bit). A envoie donc son message sur le lien 1 (c'est à dire vers 1001) avec en-tête 0100. Puis 1001, lisant l'entête, renvoie sur son lien 2, c'est à dire vers 1101=B.

On peut également écrire un algorithme dynamique qui corrige les bits selon les liens disponibles (voir à ce propos [RL03]).

8.5.2  Plongements d'anneaux et de grilles

Le code de Gray Gm de dimension m est défini récursivement par:
Gm = 0Gm-1 | 1 Gm-1rev
Par exemple: (imaginer la numérotation des processeurs sur l'anneau, dans cet ordre - un seul bit change à chaque fois)

L'intérêt des codes de Gray est qu'ils permettent de définir un anneau de 2m processeurs dans le m-cube grâce à Gm. Ils permettent également de définir un réseau torique de taille 2r × 2s dans un m-cube avec r+s=m (utiliser le code Gr × Gs).

On trouvera un exemple de plongement d'anneau dans l'hypercube à la figure 8.11. On reconnaît l'anneau sur l'hypercube à la droite de cette figure, matérialisé par des arcs gras.


Figure 8.11: Plongement d'un anneau dans un hypercube.


8.5.3  Diffusion simple dans l'hypercube

On suppose que le processeur 0 veut envoyer un message à tous les autres. Un premier algorithme naïf est le suivant: le processeur 0 envoie à tous ses voisins, puis tous ses voisins à tous leurs voisins etc.: ceci est très inefficace, car les messages sont distribués de façon très redondante! On peut penser à un deuxième algorithme naïf, mais un peu moins: on utilise le code de Gray et on utilise la diffusion sur l'anneau. Mais il y a mieux, on va utiliser les arbres couvrants de l'hypercube.

On se donne les primitives suivantes: send(cube-link,send-adr,L), et receive(cube-link, recv-adr,L). On fait en sorte que les processeurs reçoivent le message sur le lien correspondant à leur premier 1 (à partir des poids faibles), et propagent sur les liens qui précèdent ce premier 1. Le processeur 0 est supposé avoir un 1 fictif en position m. Tout ceci va se passer en m phases, i=m-1 ® 0. En fait, on construit à la fois un arbre couvrant de l'hypercube et l'algorithme de diffusion (voir la figure 8.12 dans le cas m=4).


Figure 8.12: Un arbre couvrant pour un 4-cube.


Sans entrer dans les détails, toujours pour m=4, on a les phases suivantes: Pour le cas général, on se reportera à [RL03].


Previous Up Next