Institut Supérieur des

Master M1

Systèmes pèrvasifs

Résumé D’a

Adaptive Strassen’s Matrix Multiplication

Paolo D’Alberto/

Réalisé par : Mlle :Zrigui Sarah

Mlle: Sakly Amna

Mr :Shili Mohamed

Ministère de l’Enseignement Supérieur et de la Recherche

upérieur des Sciences Applique et de Technologie de Sousse

Master M1 : Master de Recherche informatique

Systèmes pèrvasifs intelligents (SPI)

Année Universitaire

Résumé D’article :

Adaptive Strassen’s Matrix Multiplication

Paolo D’Alberto/ Alexandru Nicolau

:Zrigui Sarah

Amna

:Shili Mohamed

Proposé par

Docteur: Achour

République Tunisienne

Ministère de l’Enseignement Supérieur et de la Recherche

Scientifique

Université de Sousse

echnologie de Sousse

de Recherche informatique

Année Universitaire : 2013/ 2014

Adaptive Strassen’s Matrix Multiplication

par :

r: Achour Sami

Ministère de l’Enseignement Supérieur et de la Recherche

ISSAT Sousse

2

Sommaire I. Introduction .................................................................................................................. 3

II. Travail realisé ............................................................................................................... 3

III. Multiplication matricielle équilibré ............................................................................ 3

1. AlgorithmeATLAS/GotoBLAS–Strassenhybride (HASA) ...................................... 4

2. Considérations numériques ........................................................................................ 5

3. Récursivité Point et complexité .................................................................................. 5

IV. Résultats expérimentaux ............................................................................................. 6

1. Matrice rectangulaire .................................................................................................. 6

1.1 HP zv6000, Athlon-64 2 GHz utilisant ATLAS, localité des données par

rapport à des opérations ......................................................................................................... 6

1.2 GotoBLAS, Strassen VS rapide MM Altura 939, Athlon-64 2.5GHz utilisant

GotoBLAS. ............................................................................................................................... 6

2. Matrices carrées ........................................................................................................... 7

V. Conclusion .................................................................................................................... 7

3

I. Introduction

La performance d’une application et le résultat de l’interaction entre l’architecture du

système d’un coté, et la partie logiciel de l’autre. Lorsque l’architecture évolue, le

code aussi doit évoluer pour maintenir une performance optimale. L'évolution des

systèmes est modélisée par le calcul matriciel et pour cela l’evolution dans ce

domaine est fondamentale.

Dans cet article on s’interesse a la multiplication des matrices MM quel que soit sa

taille ou sa forme. On montre que avec la bonne combinaison de l’algorithme de

Strassen avec ATLAS/GotoBLAS on peut achever une acceleration30%/22% par

rapport a l’utilisation de ATLAS/GotoBLAS seulement. On presente aussi la

compléxité, l’analyse numerique et la performance de notre algorithme.

II. Travail réalisé

Strassen a decouvrit que l’algorithme de complexité O(n3) peut etre organiser d’une

manière que chaque instruction recursive couteuse peut et remplacer par 18 additions

de matrice MA.

Comme resultat l’algorithme de Strassen a asymptotiquement moins d’operation.

Notre approche comprend trois avantages par rapport aux approches précédentes :

1. Notre algorithme divise les problèmes MM en un ensemble de sous-problèmes

équilibrées. Cette répartition équilibrée conduit à une parallélisation facile, et

peu ou pas de travail en combinant les solutions de sous-problèmes.

2. Notre algorithme applique la stratégie de Strassen récursivement le plus grand

nombre de fois en fonction de la taille du problème. Si la taille du problème

est suffisamment grande, l'algorithme a une profondeur de récurrence qui va

aussi profond que il n'y a aucun avantage de performance.

3. Nous stockons des matrices en ligne ou colonne, Ainsi, nous pouvons utiliser

notre algorithme en combinaison avec ces routines MM sans aucune

modification ou changement de mise en page.

III. Multiplication matricielle équilibré

Nous avons choisi de diviser logiquement une matrice M en au plus quatre sous-

matrices; nous les marquons ainsi : M0 est le premier et le plus grand sous-matrice,

M2 est logiquement sous M0, M1 est a la dr

M2.

Dans le tableau 1, nous présentons l’algorithme que nous identifions comme MM

équilibré. cet algorithme réduit le problème à matrices presque carrés. Nous visons à

l'utilisation efficace du niveau supérieur de

1. AlgorithmeATLAS/GotoBLAS

Quel que soit la taille de la matrice, nous appliquons le procesus de division de

Strassen équilibré, Cela réduit le nombre de calculs plus loin que d'un problème pair /

impair taille.

La répartition équilibrée de la récurrence de Strassen a besoin d'une nouvelle

définition de MA a cause de l'addition de matrices de différentes tailles.

Nous généralisons les opérations telles que:

L'algorithme est correct

Le contrôle supplémentaire pour les tailles irrégulières est tout à fait

négligeable et que pour les ajouts de la matrice

4

M2 est logiquement sous M0, M1 est a la droite de M0, M3 est sous M1 et à droite du

Dans le tableau 1, nous présentons l’algorithme que nous identifions comme MM

équilibré. cet algorithme réduit le problème à matrices presque carrés. Nous visons à

l'utilisation efficace du niveau supérieur de la hiérarchie de la mémoire.

AlgorithmeATLAS/GotoBLAS–Strassenhybride (HASA)

Quel que soit la taille de la matrice, nous appliquons le procesus de division de

Strassen équilibré, Cela réduit le nombre de calculs plus loin que d'un problème pair /

La répartition équilibrée de la récurrence de Strassen a besoin d'une nouvelle

définition de MA a cause de l'addition de matrices de différentes tailles.

Nous généralisons les opérations telles que:

L'algorithme est correct

supplémentaire pour les tailles irrégulières est tout à fait

négligeable et que pour les ajouts de la matrice

oite de M0, M3 est sous M1 et à droite du

Dans le tableau 1, nous présentons l’algorithme que nous identifions comme MM

équilibré. cet algorithme réduit le problème à matrices presque carrés. Nous visons à

la hiérarchie de la mémoire.

Quel que soit la taille de la matrice, nous appliquons le procesus de division de

Strassen équilibré, Cela réduit le nombre de calculs plus loin que d'un problème pair /

La répartition équilibrée de la récurrence de Strassen a besoin d'une nouvelle

définition de MA a cause de l'addition de matrices de différentes tailles.

supplémentaire pour les tailles irrégulières est tout à fait

5

2. Considérations numériques

Pour cet algorithme, on peut appliquer la même analyse numérique utilisée pour

l'algorithme de Strassen. Strassen a été prouvé faiblement stable.

La stabilité de l'algorithme s'aggrave lorsque la profondeur de la récurions augmente.

(1)

Entrée(Input)

On limite les valeurs de la matrice d'entrée à une gamme ou intervalles spécifique: [-

1, 1] et [0, 1].

Comparison

On compare la différence de valeur de sortie d’algorithme ATLAS, l’algorithme Hasa

et l’algorithme naïve ligne par colonne en utilisant un registre accumulateur, pour

laquelle la sommation n'est pas compensée et les valeurs sont dans l'ordre original.

Figure 1: Pentium 4 3.2GHz Maximum error estimation: Recursion point n1=900, 1

recursion 900_n_1800, 2 recursions 1800_n_3600, and 3 recursions 3600_n

3. Récursivité Point et complexité

L'algorithme de Strassen incarne deux propriétés de localités différentes parce que ses

deux calculs de base exploitent différents localité des données: matrice multiplier MM

a la localité spatiale et temporelle, et la matrice addition MA a seulement localité

spatiale.

6

La taille du problème [m, n, p] pour donner le contrôle à l'algorithme

ATLAS/GotoBLAS, c'est quand l'équation suivante est satisfaite:

(2) [m/2][n/2][p/2]<= α/2π [5⌈n/2]([m/2]+[p/2])+3mp]

IV. Résultats expérimentaux

1. Matrice rectangulaire

1.1 HP zv6000, Athlon-64 2 GHz utilisant ATLAS, localité des données par

rapport à des opérations

On présente les résultats de performance relative de deux algorithmes en respectant le

cblas_dgemm: Balanced et HASA dynamic.

Balanced : est l'algorithme où on détermine le point récursion pour HASA lorsqu’on

installe les codes dans cette architecture.

HASA dynamic: est l'algorithme où nous déterminons le point récurrent pour chaque

taille spécifique de problème lors de l'exécution. On a mis le point récurrent comme la

taille du problème satisfaisante :

[m/2][n/2][p/2]<= α5/π5 + ᵋ [5⌈n/2]([m/2]+[p/2])+3mp]

Observation de performance L'algorithme de Strassen peut être appliqué avec

succès aux matrices rectangulaires et on peut atteindre des améliorations importantes

de la performance dans le travail. Cependant ces améliorations sont souvent le

résultat d'une meilleure utilisation de localisation des données ‘data-locality ’ qu’une

réduction des opérations.

1.2 GotoBLAS, Strassen VS rapide MM Altura 939, Athlon-64 2.5GHz

utilisant GotoBLAS.

La performance de GotoBLAS pique à 4,5 GFLOPS, Balanced et HASA dynamic

piquent à 5,4 GFLOPS.. Le point de la récursivité est empiriquement constaté à n1=

900 et nous nous arrêtons la récursion si la taille de la matrice est plus petite de n1.

Les deux algorithmes ont même performances; qui est, en moyenne de 7,7%

d’accélération pour HASA et 7,5% accélération pour Balanced. pour ces

architectures, la performance est très prévisible et l'intrigue de la performance montre

les niveaux de récursivité appliqués clairement, voir Figure 5.

Figure 5: Altura 939, Athlon 64 2.5GHz, utilisant GotoBLAS’s DGEMM.

2. Matrices carrées

Présentation de la performance

temps d'exécution relative de HASA sur cblas_DGEMM et cblas_DGEMM relatifs au

MFLOPS. En effet, le temps d'exécution est ce que tout final utilisateur prend quand

on compare les deux algorithmes.

Tableau 3: Les systèmes et les performances: 1/

cblas_DGEMM ou DGEMM (GotoBLAS) dans MFLOPS pour n = 1000;1/α 10

la performance de MA en MFLOPS pour n = 1000;

théorique estimée à 22 α/π

V. Conclusion

Cet article a présenté une mise en œuvre pratique de l'algorithme Strassen, qui

applique un algorithme

qu’ATLAS. On se distingue depuis les approches précédentes qu’on utilise un

algorithme récursif facile à adapter utilisant un processus de division équilibré.

En observant on conclu que l'expérimentatio

un modèle à simple complexité qui quantifie les interactions entre les grains d'une

application et l'architecture sous jacente, peut aller un long chemin en aidant le

désigne de codes complexes, mais portable.

conception des algorithmes et peut servir une base pour une approche automatisée.

7

5: Altura 939, Athlon 64 2.5GHz, utilisant GotoBLAS’s DGEMM.

Présentation de la performance : on présente deux mesures de performance: le

temps d'exécution relative de HASA sur cblas_DGEMM et cblas_DGEMM relatifs au

temps d'exécution est ce que tout final utilisateur prend quand

on compare les deux algorithmes.

Tableau 3: Les systèmes et les performances: 1/π106 est la performance de

cblas_DGEMM ou DGEMM (GotoBLAS) dans MFLOPS pour n = 1000;1/α 10

e de MA en MFLOPS pour n = 1000; n1 est le point de récurrence

α/π à la place, n1 est l' mesurée point de récursivité.

Cet article a présenté une mise en œuvre pratique de l'algorithme Strassen, qui

applique un algorithme adaptatif pour exploiter MMs importantes, tels

On se distingue depuis les approches précédentes qu’on utilise un

algorithme récursif facile à adapter utilisant un processus de division équilibré.

En observant on conclu que l'expérimentation environnement en combinaison avec

un modèle à simple complexité qui quantifie les interactions entre les grains d'une

application et l'architecture sous jacente, peut aller un long chemin en aidant le

désigne de codes complexes, mais portable. Ces mesures peuvent améliorer la

conception des algorithmes et peut servir une base pour une approche automatisée.

5: Altura 939, Athlon 64 2.5GHz, utilisant GotoBLAS’s DGEMM.

on présente deux mesures de performance: le

temps d'exécution relative de HASA sur cblas_DGEMM et cblas_DGEMM relatifs au

temps d'exécution est ce que tout final utilisateur prend quand

est la performance de

cblas_DGEMM ou DGEMM (GotoBLAS) dans MFLOPS pour n = 1000;1/α 106 est

n1 est le point de récurrence

à la place, n1 est l' mesurée point de récursivité.

Cet article a présenté une mise en œuvre pratique de l'algorithme Strassen, qui

adaptatif pour exploiter MMs importantes, tels

On se distingue depuis les approches précédentes qu’on utilise un

algorithme récursif facile à adapter utilisant un processus de division équilibré.

n environnement en combinaison avec

un modèle à simple complexité qui quantifie les interactions entre les grains d'une

application et l'architecture sous jacente, peut aller un long chemin en aidant le

s peuvent améliorer la

conception des algorithmes et peut servir une base pour une approche automatisée.