Algorithme d'évitement de la communication

hiérarchie mémoire afin d'améliorer le temps d'exécution et la consommation d'énergie. Ils minimisent le total de deux coûts (en termes de temps et d'énergie) : les opérations arithmétiques et les communications. Dans ce contexte, la communication désigne le déplacement de données, que ce soit entre différents niveaux de mémoire ou entre plusieurs processeurs via un réseau. Elle est beaucoup plus coûteuse que les opérations arithmétiques.

Un modèle de calcul courant pour l'analyse des algorithmes évitant la communication est le modèle de mémoire à deux niveaux :

Il y a un processeur et deux niveaux de mémoire.
La mémoire de niveau 1 est infiniment grande. La mémoire de niveau 0 (« cache ») a une taille .
Au début, les données d'entrée se trouvent au niveau 1. À la fin, les données de sortie se trouvent au niveau 1.
Le processeur ne peut traiter que les données en cache.
L'objectif est de minimiser les transferts de données entre les deux niveaux de mémoire.

Multiplication matricielle

Corollaire 6.2 :

Des résultats plus généraux concernant d'autres opérations d'algèbre linéaire numérique se trouvent dans . La démonstration suivante est tirée de

Si la taille de l'ensemble est importante, nous pouvons simplement charger toutes les entrées puis les écrire. Cela ne présente aucun intérêt. Si la taille du cache est petite, on peut diviser l'algorithme de communication minimale en segments distincts. Durant chaque segment, il effectue exactement lectures du cache et un nombre quelconque d'écritures depuis ce cache. Durant chaque segment, le processeur a accès à au plus différents points de . Soit l'ensemble des points du réseau parcourus durant ce segment. Alors, d'après l'inégalité de Loomis-Whitney, avec contrainte . Par l' inégalité des moyennes arithmétiques et géométriques, nous avons , avec un extremum atteint lorsque . Ainsi, l'intensité arithmétique est bornée supérieurement par où , et donc la communication est bornée inférieurement par . Un calcul direct vérifie que l'algorithme de multiplication de matrices de pavage atteint la limite inférieure.

Motivation

Considérons le modèle de temps d'exécution suivant :

Mesure de calcul = Temps par FLOP = γ
Mesure de la communication = Nombre de mots de données transférés = β

⇒ Temps d'exécution total = γ·(nombre d'opérations en virgule flottante ) + β·(nombre de mots)

Étant donné que β >> γ, en termes de temps et d'énergie, le coût de la communication domine le coût du calcul. Les tendances technologiques indiquent que le coût relatif de la communication augmente sur diverses plateformes, du cloud computing aux supercalculateurs en passant par les appareils mobiles. Le rapport prévoit également que l'écart entre le temps d'accès à la DRAM et les FLOPs sera multiplié par 100 au cours de la prochaine décennie afin d'équilibrer la consommation d'énergie entre les processeurs et la DRAM.

Taux FLOP (γ)	Bande passante DRAM (β)	Bande passante du réseau (β)
59 % par an	23 % par an	26 % par an

La consommation d'énergie augmente de plusieurs ordres de grandeur à mesure que l'on monte dans la hiérarchie de la mémoire.

Le président des États-Unis, Barack Obama, a cité des algorithmes d’évitement de la communication dans la demande de budget du département de l’Énergie pour l’exercice 2012 au Congrès :

Un nouvel algorithme améliore les performances et la précision des systèmes de calcul à très grande échelle. Sur les architectures informatiques modernes, la communication entre processeurs est plus lente que l'exécution d'une opération arithmétique en virgule flottante par un processeur donné. Des chercheurs de l'ASCR ont développé une nouvelle méthode, dérivée de méthodes d'algèbre linéaire courantes, afin de minimiser les communications entre les processeurs et la hiérarchie mémoire, en reformulant les schémas de communication spécifiés dans l'algorithme. Cette méthode a été implémentée dans le framework TRILINOS, une suite logicielle de référence qui permet aux chercheurs du monde entier de résoudre des problèmes multiphysiques complexes à grande échelle.

Objectifs

Les algorithmes d'évitement de la communication sont conçus avec les objectifs suivants :

Réorganiser les algorithmes afin de réduire la communication entre toutes les hiérarchies de mémoire.
Limitez au strict minimum la communication lorsque cela est possible.

L’exemple simple suivant montre comment ces résultats sont obtenus.

Exemple de multiplication matricielle

Soient A, B et C des matrices carrées d'ordre n × n . L'algorithme naïf suivant implémente C = C + A * B :

pour i = 1 à n pour j = 1 à n pour k = 1 à n C(i,j) = C(i,j) + A(i,k) * B(k,j)

Coût arithmétique (complexité temporelle) : n ² (2 n − 1) pour n suffisamment grand ou O( n ³ ).

Réécriture de cet algorithme avec le coût de communication indiqué à chaque étape

pour i = 1 à n {lire la ligne i de A dans la mémoire rapide} - n ² lectures pour j = 1 à n {lire C(i,j) dans la mémoire rapide} - n ² lectures {lire la colonne j de B dans la mémoire rapide} - n ³ lectures pour k = 1 à n C(i,j) = C(i,j) + A(i,k) * B(k,j) {réécrire C(i,j) dans la mémoire lente} - n ² écritures

La mémoire rapide peut être définie comme la mémoire locale du processeur ( cache du processeur ) de taille M et la mémoire lente comme la DRAM.

Coût de communication ^{( lectures}^/ écritures) : n³ + 3n² ou O( n³ ⁾

Étant donné que le temps d'exécution total = γ · O( n³ ) + β · O( n³ ) et β >> γ, ^le^coût de communication est prépondérant. L'algorithme de multiplication matricielle par blocs (tuilage) réduit ce terme prépondérant :

Multiplication de matrices par blocs (tuilées)

Considérons A, B et C comme des matrices n / b -by- n / b de sous-blocs b -by- b où b est appelé la taille du bloc ; supposons que trois blocs b -by- b tiennent dans la mémoire rapide.

pour i = 1 à n/b pour j = 1 à n/b {lire le bloc C(i,j) en mémoire rapide} - b ² × (n/b) ² = n ² lectures pour k = 1 à n/b {lire le bloc A(i,k) en mémoire rapide} - b ² × (n/b) ³ = n ³ /b lectures {lire le bloc B(k,j) en mémoire rapide} - b ² × (n/b) ³ = n ³ /b lectures C(i,j) = C(i,j) + A(i,k) * B(k,j) - {effectuer une multiplication matricielle par blocs} {réécriture du bloc C(i,j) dans la mémoire lente} - b ² × (n/b) ² = n ² écritures

Coût de communication : ^2n³/ b + 2n² lectures ^/ écritures << 2n³ coût ^{arithmétique}

Augmenter la valeur de b au maximum :

3 b ² ≤ M

nous atteignons la limite inférieure de communication suivante :

3 ^1/2n ³ / M ^1/2 + 2 n ² ou Ω (nombre d'opérations en virgule flottante / M ^1/2 )

Approches précédentes pour réduire la communication

La plupart des approches étudiées par le passé pour résoudre ce problème reposent sur des techniques d'ordonnancement ou d'optimisation visant à faire coïncider la communication et le calcul. Cependant, cette approche ne permet d'obtenir qu'une amélioration d'un facteur deux au maximum. Le « ghosting » est une technique différente de réduction de la communication, dans laquelle un processeur stocke et traite de manière redondante des données provenant de processeurs voisins pour des calculs ultérieurs. Les algorithmes indépendants du cache représentent une approche différente, introduite en 1999 pour les transformées de Fourier rapides , puis étendue aux algorithmes de graphes, à la programmation dynamique , etc. Ils ont également été appliqués à plusieurs opérations d'algèbre linéaire telles que les factorisations LU et QR denses. La conception d'algorithmes spécifiques à l'architecture est une autre approche permettant de réduire la communication dans les algorithmes parallèles , et la littérature regorge d'exemples d'algorithmes adaptés à une topologie de communication donnée