1   Parallélisme

2  Plan

• Communications et routage
  • Généralités
  • Cas de l'hypercube (diffusion simple)
  • Cas du tore 2D (multiplication de matrices)
• Algorithmique sur ressources hétérogènes
  • Allocation et équilibrage de charges statique/dynamique
  • Cas de l'algorithme LU: sur anneau (1D) puis tore (2D)

3  Généralités

• Topologie statique: réseau d'interconnexion fixe:
  • anneau, tore 2D,
  • hypercube, graphe complet etc.
• Topologie dynamique: modifiée en cours d'exécution (par configuration de switch)

4  Caractéristiques

5  Intérêt

• Réseau complet: idéal pour le temps de communications (toujours unitaire)
• Mais: passage à l'échelle difficile! (prix du cablage, rajouter des nouveaux processeurs?)
• Anneau: pas cher, mais communications lentes, et tolérance aux pannes des liens faible
• Tore 2D, Hypercube: bons compromis entre les deux

6  Routage

• Chaque processeur intermédiaire reçoit et stocke le message M avant de le re-émettre en direction du processeur destinataire
• Modèle à commutation de message
• Première génération de machines
• Coût: d(x,y)(b+Lt)
• Sauf programmation particulière (voir cours 5): Lt + O((L))

7  Routage

• Co-processeur de communication
• Coût b+(d(x,y)-1)d+Lt
• d << b: chemin calculé par le matériel, partie logicielle dans b
• Deux protocoles: ``Circuit-switching'' (CC) et ``Wormhole'' (WH)

8  Circuit-switching

• Chemin créé avant l'émission des premiers octets
• Puis message acheminé directement entre source et destinataire
• Immobilisation des liens
• iPSC d'INTEL

9  Wormhole

• Adresse du destinataire placée dans l'entête du message
• Routage sur chaque processeur
• Message découpé en petits paquets appelés flits
• En cas de blocage: flits stockés dans les registres internes des routeurs intermédiaires
• Paragon d'INTEL

10  Comparaison

• CC et WH plus efficaces que SF: masquent la distance entre les processeurs communiquants
• CC contruit son chemin avant l'envoi des premiers paquets de données
• WH construit sa route tandis que le message avance dans le réseau (meilleure bande passante que CC)

11  Comparaison

12  Communications dans un hypercube

• Chemins et routage dans un hypercube
• Broadcast dans un hypercube

13  Numérotation des sommets

• sommets numérotés de 0 à 2^m-1
• il existe une arête d'un sommet à un autre si les deux diffèrent seulement d'un bit dans leur écriture binaire

14  Chemins et routage

• A, B deux sommets, H(A,B) leur distance de Hamming (le nombre de bits qui diffèrent dans l'écriture)
• Il existe un chemin de longueur H(A,B) entre A et B (récurrence facile sur H(A,B))
• Il existe H(A,B)! chemins entre A et B, dont seuls H(A,B) sont indépendants (passent par des sommets différents)

15  Chemins et routage

• A=1011, B=1101
• A xor B=0110 (ou exclusif bit à bit)
• A envoie donc son message sur le lien 1 (c'est à dire vers 1001) avec entête 0100
• Puis 1001, lisant l'entête, renvoie sur son lien 2, c'est à dire vers 1101=B.

16  Plongements d'anneaux et de grilles

• xG énumère les éléments de G en rajoutant x en tête de leur écriture binaire
• G^rev énumère les éléments de G dans l'ordre renversé
• | est la concaténation (de ``listes'' de mots binaires)

17  Codes de Gray: exemple

• G₁={0,1}
• G₂={00,01,10,11}
• G₃={000,001,010,011,111,110,101,100}
• G₄={0000,0001,0010,0011,0111,0110,0101,0100,1100,
  
            1101,1110,1111,1011,1010,1001,1000}

18  Codes de Gray: intérêt

• Permet de définir un anneau de 2^m processeurs dans le m-cube grâce à G_m
• Permet de définir un réseau torique de taille 2^r × 2^s dans un m-cube avec r+s=m (utiliser le code G_r × G_s)

19  Codes de Gray: exemple

20  Diffusion simple dans l'hypercube

• on suppose que le processeur 0 veut envoyer un message à tous les autres
• algorithme naïf 1: le processeur 0 envoie à tous ses voisins, puis tous ses voisins à tous leurs voisins etc.: Très redondant!
• algorithme naïf 2: on utilise le code de Gray et on utilise la diffusion sur l'anneau

21  Arbres couvrants de l'hypercube

• Primitives: send(cube-link,send-adr,L),
  
  receive(cube-link,recv-adr,L)
• Les processeurs vont recevoir le message sur le lien correspondant à leur premier 1 (à partir des poids faibles)
• Et vont propager sur les liens qui précèdent ce premier 1
• Le processeur 0 est supposé avoir un 1 fictif en position m
• Tout ceci en m phases, i=m-1 ® 0

22  Arbres couvrants de l'hypercube

23  Exemple

• phase 3: 0000 envoie le message sur le lien 3 à 1000
• phase 2: 0000 et 1000 envoient le message sur le lien 2, à 0100 et 1100 respectivement
• ainsi de suite jusqu'à la phase 0

24  Algorithmique sur grille 2D

• Algorithme de Cannon
• Algorithme de Fox
• Algorithme de Snyder

25  Produit de matrices sur grille 2D

• Algorithmes par blocs: augmenter le grain de calcul et améliorer l'utilisation des mémoires hiérarchiques
• Distribution cyclique: équilibrer la charge

26  Distribution cyclique par blocs

27  Réseau linéaire par blocs (4 procs)

28  Réseau linéaire cyclique

29  Réseau en grille 2D par blocs (4×4 procs)

30  Réseau en grille 2D par blocs cycliques

31  En pratique?

• Version centralisée:
  • routines appelées avec données et résultats sur machine hôte
  • minimise le nombre de fonctions à écrire, permet de choisir la distribution des données la plus adaptée
  • MAIS coût prohibitif si on enchaîne les appels (penser à FFT 2D)
• Version distribuée:
  • données déjà distribuées, résultat distribué
  • passage à l'échelle (``scalable''), fonctions de redistribution des données
  • MAIS compromis: coût de redistribution/coût de l'algorithme avec rangement adapté/coût de l'algorithme avec rangement non-adapté

32  Produit de matrices sur grille 2D

• C=C+AB, avec A, B et C de taille N × N
• p=q²: on dispose d'une grille de processeurs en tore de taille q × q
• distribution des matrices par blocs: P_ij stocke A_ij, B_ij et C_ij

33  Au départ:

34  Principe de l'algorithme de Cannon

35  Principe de l'algorithme de Cannon (2)

36  Principe de l'algorithme de Cannon

/* diag(A) sur col 0, diag(B) sur ligne 0 */
Rotations(A,B); /* preskewing */

/* calcul du produit de matrice */
forall (k=1; k<=sqrt(P)) {
  LocalProdMat(A,B,C);
  VerticalRotation(B,downwards);
  HorizontalRotation(A,leftwards); }

/* mouvements des donnees apres les calculs */
Rotations(A,B); /* postskewing */

37  Principe de l'algorithme de Fox

• Pas de mouvements de données initials
• Diffusions horizontales des diagonales de A (décalées vers la droite)
• Rotations verticales de B (de bas en haut)

38  Principe de l'algorithme de Fox

39  Principe de l'algorithme de Fox (2)

40  Principe de l'algorithme de Fox

/* pas de mouvements de donnees avant les calculs */

/* calcul du produit de matrices */
broadcast(A(x,x));
forall (k=1; k<sqrt(P)) {
  LocalProdMat(A,B,C);
  VerticalRotation(B,upwards);
  broadcast(A(k+x,k+x)); }
forall () {
  LocalProdMat(A,B,C);
  VerticalRotation(B,upwards); }

/* pas de mouvements de donnees apres les calculs */

41  Principe de l'algorithme de Snyder

• Transposition préalable de B
• Sommes globales sur les lignes de processeurs (des produits calculés à chaque étape)
• Accumulation sur les diagonales (décalées à chaque étape vers la droite) de C des résultats - représentées en gras dans les transparents ci-après
• Rotations verticales de B (de bas en haut)

42  Principe de l'algorithme de Snyder

43  Principe de l'algorithme de Snyder (2)

44  Principe de l'algorithme de Snyder

/* mouvements des donnees avant les calculs */
Transpose(B);
/* calcul du produit de matrices */
forall () {
  LocalProdMat(A,B,C);
  VerticalRotation(B,upwards); }
forall (k=1;k<sqrt(P)) {
  GlobalSum(C(i,(i+k-1) mod sqrt(P)));
  LocalProdMat(A,B,C);
  VerticalRotation(B,upwards); }
GlobalSum(C(i,(i+sqrt(P)-1) mod sqrt(P)));
/* mouvements des donnees apres les calculs */
Transpose(B);

45  Analyse des algorithmes

46  Algorithmique hétérogène

• t₁,t₂,...,t_p temps de cycle des processeurs
• B tâches identiques et indépendantes
• Principe: c_i × t_i = constante, d'où:

  ci=

  ê ê ê ê ê ê ë

  1 ti p S k=1 1 tk

  ú ú ú ú ú ú û

  × B

47  Allocation statique optimale

Distribute(B,t1,t2,...,tn)
/* initialisation: calcule ci */
for (i=1;i<=p;i++)
  c[i]=...
/* incrementer iterativement les ci minimisant le temps */
while (sum(c[])<B) {
  find k in {1,...,p} st t[k]*(c[k]+1)=min{t[i]*(c[i]+1)};
  c[k] = c[k]+1;
return(c[]);

48  Algorithme incrémental

• Allocation optimale pour tout nombre d'atomes entre 1 et B
• Programmation dynamique avec t₁=3, t₂=5 et t₃=8

49  Algorithme incrémental

Distribute(B,t1,t2,...tp)
/* Initialisation: aucune tache a distribuer m=0 */
for (i=1;i<=p;i++) c[i]=0;
/* construit iterativement l'allocation sigma */
for (m=1;m<=B;m++)
  find(k in {1,...p} st t[k]*(c[k]+1)=min{t[i]*(c[i]+1)});
  c[k]=c[k]+1;
  sigma[m]=k;
return(sigma[],c[]);

50  Exemple

51  Ressources hétérogènes et équilibrage de charges

• A chaque étape, le processeur qui possède le bloc pivot le factorise et le diffuse
• Les autres processeurs mettent à jour les colonnes restantes
• A l'étape suivante le bloc des b colonnes suivantes devient le pivot
• ainsi de suite: la taille des données passe de (n-1)× b à (n-2)× b etc.

52  Allocation statique équilibrant les charges 1D

• Solution 1: on redistribue les colonnes restant à traiter à chaque étape entre les processeurs: pb, coût des communications
• Solution 2: trouver une allocation statique donnant un équilibrage de charges à chaque étapes

53  Allocation statique équilibrant les charges 1D

• Distribution de B tâches sur p processeurs de temps de cycle t₁, t₂ etc. t_p telle que
• pour tout i Î {2,...,B}, le nombre de blocs de {i,...,B} que possède chaque processeur P_j soit approximativement inversement proportionnel à t_j

54  Allocation 1D

• Allouer périodiquement un motif de largeur B les blocs de colonnes
• B est un paramètre, par exemple si la matrice est (nb)× (nb), B=n (mais meilleur pour le recouvrement calcul communication si B << n)
• Utiliser l'algorithme précédent en sens inverse: le bloc de colonne 1£ k £ B alloué sur s(B-k+1)
• Cette distribution est quasi-optimale pour tout sous-ensemble [i,B] de colonnes

55  Exemple

56  Allocation statique 2D

• Algorithme par blocs de ScaLAPACK
• Double diffusion horizontale et verticale
• S'adapte au cas de matrices et grilles
• Aucune redistribution initiale des données

57  Multiplication de matrices - cas homogène

58  Multiplication - cas inhomogène ``régulier''

• Allouer des rectangles de tailles différentes aux processeurs, en fonction de leur vitesse relative
• p× q processeurs P_i,j de temps de cycle t_i,j

59  Equilibrage de charge parfait

• Uniquement quand la matrice des temps de cycle T=(t_i,j) est de rang 1
• Exemple, rang 2, P_2,2 est partiellement inactif:

  	1	1 2
  1	t11=1	t12=2
  1 3	t21=3	t22=5

• Exemple, rang 1, équilibrage parfait:

  	1	1 2
  1	t11=1	t12=2
  1 3	t21=3	t22=6

60  Problème

• Objectif Obj1:

  min

  S i ri=1;   S j cj=1

  maxi,j {ri × ti,j× cj}

• Objectif Onj2:

  max

  ri × ti,j × cj £ 1

  ì í î

  æ ç ç è

  S i

  ri

  ö ÷ ÷ ø

  ×

  æ ç ç è

  S j

  cj

  ö ÷ ÷ ø

  ü ý þ

61  Régularité?

• En fait, la position des processeurs dans la grille n'est pas une donnée du problème
• Toutes les permutations sont possibles, et il faut chercher la meilleure
• Problème NP-complet
• Conclusion: l'équilibrage 2D est très difficile!

62  Partitionnement libre

63  Partitionnement libre

• p processeurs de vitesses s₁,s₂,...,s_n de somme 1 (normalisées)
• Partitionner le carré unité en p rectangles de surfaces s₁,s₂,...,s_n
• Surface des rectangles Û vitesses relatives des processeurs
• Forme des rectangles Û minimiser les communications

64  Géométriquement

• Partitionner le carré unité en p rectangles d'aires fixées s₁, s₂, ..., s_p afin de minimiser
  • soit la somme des demi-périmètres des rectangels dans le cas des communications séquentielles
  • soit le plus grand des demi-périmètres des rectangles dans le cas de communications parallèles
• Problèmes NP-complets

65  Exemple

• p=5 rectangles R₁,...,R₅
• Aires s₁=0.36, s₂=0.25, s₃=s₄=s₅=0.13

66  Exemple

• Demi-périmètre maximal pour R₁, approximativement 1.2002
  • borne inférieure absolue 2s₁ = 1.2 atteinte lorsque le plus grand rectangle est un carré (pas possible ici)
• Somme des demi-périmètres =4.39
  • borne absolue inférieure S_i=1^p 2 s_i=4.36 atteinte lorsque tous les rectangles sont des carrés

This document was translated from L^AT_EX by H^EV^EA.