SDR

Battements

Olivier Lemer

Rappels

Dans chaque battement, un processus peut

Faire des calculs relatifs aux battements précédents.
Envoyer jusqu'à un message par voisin, fonction des battements précédents.
Recevoir jusqu'à un message par voisin, fonction des battements précédents.

Un signal est reçu pour déclencher un nouveau battement.

(pulse)

Un processus est prêt quand tous ses messages ont été reçus.

battement

signal

Algorithmes synchrones

Aujourd'hui

Deux exemples d'algorithme synchronisé.

Découverte de la topologie du réseau.
Calcul distribué de la multiplication de deux matrices.

Découvrir la topologie

Un algorithme synchrone

Description du problème

Initialement, chaque processus connait uniquement

ses voisins directs, et
le nombre total de processus, n.

Topologie : description du graphe ("qui est connecté à qui")

En fin d'algorithme, chaque processus doit connaitre aussi

les voisins de chaque processus du système.

Comment faire ?

Comment représenter la topologie ?

Algorithme synchrone

Une matrice nxn de booléens

(i,j)

"i a j comme voisin"

Un dictionnaire

V⟼𝒫(V)

(à chaque processus, associe un sous-ensemble de processus)

Taille :

O(V²)

Taille :

O(E+V)

Comment faire ?

Comment représenter la topologie ?

Algorithme synchrone

Un dictionnaire : V⟼𝒫(V)

Quelle valeur initiale ?

Quoi faire à chaque battement ?

Mettre à jour mon dictionnaire avec ceux reçus au précédent battement.
Envoyer mon dictionnaire à tous mes voisins.

Quand m'arrêter ?

Quand mon dictionnaire a une taille de n.

Uniquement mes voisins

(c'est tout ce que je sais, de toute façon)

Découvrir la topologie

Exemple

B

A

C

D

F

E

A:BCD

dictA

D:AEF

dictD

dictF

F:D

Battement 1

Envoi des premiers messages

B

A

C

D

F

E

A:BCD

dictA

D:AEF

dictD

dictF

F:D

D:AEF

A:BCD

E:D

F:D

B:A

C:A

D:AEF

Battement 2

Traitement des messages précédents

Envoi des messages

Exemple

B

A

C

D

F

E

dictA

D:AEF

dictD

dictF

F:D

D:AEF

A:BCD

E:D

F:D

A:BCD

B:A

C:A

D:AEF

E:D

F:D

Battement 3

Traitement des messages précédents

Exemple

B

A

C

D

F

E

A:BCD

B:A

C:A

D:AEF

E:D

F:D

dictA

D:AEF

A:BCD

B:A

C:A

E:D

F:D

dictD

dictF

F:D

D:AEF

Battement 3

Traitement des messages précédents

Exemple

B

A

C

D

F

E

A:BCD

B:A

C:A

D:AEF

E:D

F:D

dictA

D:AEF

A:BCD

B:A

C:A

E:D

F:D

dictD

dictF

F:D

D:AEF

A:BCD

E:D

Battement 3

Traitement des messages précédents

Envoi des messages

Exemple

B

A

C

D

F

E

A:BCD

B:A

C:A

D:AEF

E:D

F:D

dictA

D:AEF

A:BCD

B:A

C:A

E:D

F:D

dictD

dictF

F:D

D:AEF

A:BCD

E:D

Battement 4

Traitement des messages précédents

Exemple

B

A

C

D

F

E

A:BCD

B:A

C:A

D:AEF

E:D

F:D

dictA

D:AEF

A:BCD

B:A

C:A

E:D

F:D

dictD

dictF

F:D

D:AEF

A:BCD

B:A

C:A

E:D

"Le compte est bon !

Mais pas forcément chez mes voisins,

je l'envoie une dernière fois"

"Le compte est bon !

Mais pas forcément chez mes voisins,

je l'envoie une dernière fois"

Battement 4

Traitement des messages précédents

Envoi des messages

Exemple

B

A

C

D

F

E

A:BCD

B:A

C:A

D:AEF

E:D

F:D

dictA

D:AEF

A:BCD

B:A

C:A

E:D

F:D

dictD

dictF

F:D

D:AEF

A:BCD

B:A

C:A

E:D

"Le compte est bon !

Mais pas forcément chez mes voisins,

je l'envoie une dernière fois"

"Le compte est bon,

et mes voisins ont l'info, j'ai fini"

Battement 5

Traitement des messages précédents

Envoi des messages

Exemple

"Le compte est bon,

et mes voisins ont l'info, j'ai fini"

Découvrir la topologie

Pseudocode

Variables

sync

synchroniseur

Utilisé pour avancer par battements

dict

dictionnaire

Topologie du réseau

Pseudocode

À chaque nouveau battement i

Pseudocode

dernierBattement := true ssi dict a une taille de n

Pour chaque message du battement i-1

Mise à jour de dict avec le dictionnaire du message

Envoi de dict à tous les voisins actifs

Si dernierBattement

Quitter le synchroniseur

Remarque : tout se fait à travers un synchroniseur

Les "messages du battement i-1" sont obtenus du synchroniseur.
Les "voisins actifs" sont ceux qui n'ont pas encore quitté le synchroniseur.
"Quitter le synchroniseur" lui fera dire "j'ai fini" en fin de ce battement.

(Souvenez-vous : quand un processus n'a plus besoin de synchronisation, il dit "j'ai fini" au lieu de "je suis prêt" en fin de battement)

Découvrir la topologie

Propriétés

Messages par battement

Propriétés

Taille d'un message

2 par lien, donc O(E)

Jusqu'à O(V+E)

Donc O(E) pour tout réseau connecté

(Parce que le réseau connecté ayant le moins de liens possible est un arbre, et a E = V-1 liens, donc V devient négligeable asymptotiquement)

Mémoire par processus

Comme les messages, O(E).

Comment réduire la taille des messages ?

Amélioration ?

Chaque lien est stocké en double !

Envoyer un set de liens connus.

C'est tout ?

Envoyer aussi la liste des processus dont on connait les voisins (nécessaire pour savoir quand s'arrêter)

Sinon, connaitre le diamètre d du réseau et s'arrêter au battement d+1.

Exercice

A

B

C

D

E

Étant donné le réseau ci-contre, simuler l'algorithme

synchronisé de découverte de topologie, en décrivant

l'état des dictionnaires à la fin de chaque battement.

Solution

A

B

C

D

E

A:BC

B:AC

C:ABD

D:EC

E:D

A:BC

B:AC

C:ABD

B:AC

A:BC

C:ABD

A:BC

B:AC

D:EC

C:ABD

E:D

D:EC

A:BC

B:AC

C:ABD

D:CE

B:AC

A:BC

C:ABD

D:EC

C:ABD

A:BC

B:AC

D:EC

E:D

D:EC

C:ABD

E:D

A:BC

B:AC

E:D

D:EC

C:ABD

A:BC

B:AC

C:ABD

D:CE

E:D

B:AC

A:BC

C:ABD

D:EC

E:D

C:ABD

A:BC

B:AC

D:EC

E:D

D:EC

C:ABD

E:D

A:BC

B:AC

E:D

D:EC

C:ABD

A:BC

B:CA

A:BC

B:AC

C:ABD

D:CE

E:D

B:AC

A:BC

C:ABD

D:EC

E:D

C:ABD

A:BC

B:AC

D:EC

E:D

D:EC

C:ABD

E:D

A:BC

B:AC

E:D

D:EC

C:ABD

A:BC

B:CA

Noter le dernier broadcast après avoir reçu toutes les informations. Sans cela, C n'aurait pas propagé les voisins de E à A et B.

Multiplication de matrices

Un algorithme synchrone

Exemple parfait d'algorithme distribué dans le but d'améliorer les performances.

Description du problème

Multiplication de matrices

Remarque : parallélisation par distribution

Input : deux matrices nxn, A et B

Output : une matrice nxn, C = AB

Ressources : n^2 processus

Arrangement des processus

Arrangement en grille

en tore !

Les processus d'une extrémité sont connectés à ceux de l'extrémité opposée.

Stratégie

Quels

avoir initialement ?

Avoir (i,j) qui possède Aij et Bij ne marche pas

est donc calculé progressivement, en k battements.

À chaque battement k, (i,j)

possède
les multiplie pour calculer
les passe à ceux qui en ont besoin.

Processus en (i,j) calculera

Stratégie

Quels

avoir initialement ?

Shift

est donc calculé progressivement, en k battements.

À chaque battement k, (i,j)

possède
les multiplie pour calculer
les passe à ceux qui en ont besoin.

Processus en (i,j) calculera

de i vers la gauche.

de j vers le haut.

Shift

Ainsi, (i,j) a

tels que

Stratégie

Quels

avoir initialement ?

est donc calculé progressivement, en k battements.

À chaque battement k, (i,j)

possède
les multiplie pour calculer
les passe à ceux qui en ont besoin.

Processus en (i,j) calculera

(i,j) commence avec

tels que

Comment changer de

à chaque battement ?

On veut passer à

On peut simplement envoyer

la valeur de A vers la gauche
la valeur de B vers le haut

Multiplication de matrices

Résumé & Pseudocode

Algorithme de Cannon

Résumé

En tant que processus (i,j)

Je suis en charge de

, initialement 0.

Je commence avec

tels que

À chaque battement

J'ajoute

J'envoie

au voisin à gauche

J'envoie

au voisin au dessus

Je reçois les

pour mon prochain battement

Algorithme de Cannon

Pseudocode

Variables

Aik

nombre

Valeur de A en ma possession

Cij

nombre, initialement 0

Somme intermédiaire

Bkj

nombre

Valeur de B en ma possession

n

entier, constant

Largeur des matrices

Avec initialement,

Aik = A[i][(i+j)%n]
Bkj = A[(i+j)%n][j]
Cij = 0

Pseudocode

À chaque nouveau battement b (en commençant à 0)

Si b > 0

Aik ← message reçu de la droite au battement précédent

Bkj ← message reçu d'en dessous au battement précédent

Cij ← Cij + Aik * Bkj

Envoi de Aik à ma gauche

Envoi de Bkj au dessus

Si b vaut n-1

Quitter le synchroniseur

Algorithme de Cannon

Multiplication de matrices

Propriétés

Messages par battement

Taille d'un message

Un par lien.

Donc 2V

Donc 2n^2

Constante

Mémoire par processus

Constante

Exercice

À chaque battement, quelles valeurs intermédiaires ont chaque processus lorsqu'ils exécutent l'algorithme de Cannon pour effectuer la multiplication suivante.

Solution

2 1 0

1 2 0

1 3 0

3 2 2

0 3 0

0 1 1

Valeurs de A

Valeurs de B

6 2 0

0 6 0

0 3 0

Valeurs de C

En fin de battement...

... 1 :

1 0 2

2 0 1

3 0 1

0 3 0

0 1 1

3 2 2

6 2 0

0 6 1

9 3 2

... 2 :

0 2 1

0 1 2

0 1 3

0 1 1

3 2 2

0 3 0

6 4 1

0 8 5

9 6 2

... 3 :