Discussion :

[progfou]

Bonjour à tous et toutes !
Je cherche un algo pour faire la multiplication de deux matrices 8x8 la plus rapide possible.
L'algo "naïf" que j'ai est le suivant :

C=A*B

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
pour i=0 à 7
    pour j=0 à 7
        pour k=0 à 7
            C[i*8+j] += A[i*8+k] * B[k*8+j];

Mais je ne pense pas me tromper quand je dis que c'est lent et qu'on peut faire mieux, non ?

[ToTo13]

Bonjour,

je sais que l'on peut aller beaucoup plus vite, mais ça dépend du contenu des matrices.

Regarde du coté de matlab qui est le numéro un incontesté pour tout ce qui touche au matrices.

[progfou]

OK, mais on n'a pas le code ?
A moins que je ne soit pas au courant de son éventuelle libération ?

[nicolas66]

Si tu n'as pas tellement de données dans tes matrices tu peux toujours utiliser une bibliothèque qui gère les matrices creuses (matrices qui ne stockent que les valeurs non nulles). Il y a un article sur Wikipedia à cette adresse : http://en.wikipedia.org/wiki/Sparse_matrix.


Nico.

[ronan99999]

Il y'a eu un sujet sur l'optimisation des multiplications des matrices 4*4, c'est toujours les memes combines, comme pour l'optimisation de la multiplication des complexes.
En suite tu généralise la formule, puisqu'une multilication 8*8 peut etre decomposée comme plusieurs produit et somme de matrice 4*4.

(Pour un algo générale il faut chercher du coté de Strassen)

http://www.enseignement.polytechniqu...iez/sujet.html

[Charlemagne]

Etant donné que tu te limites à une dimension 8x8, je te conseille fortement de développer autant que possible les boucles.
Si tu veux encore plus optimiser je te conseille d'utiliser les instructions parallèles SIMD (SSE/SSE2 sur les Pentiums) , plutôt que de chercher un algorithme d'ordre inférieur à O(N^3) qui ne saura pas utiliser le calcul parallèle.

[larnicebafteur]

A moins que la matrice soit vraiment particulière, il n'y a pas vraiment d'autre solution que la solution avec les boucles proposée.
Si la matrice ne contient pas tout les termes et possède beaucoup de 0, on peut envisager d'utiliser d'autres méthodes, mais dans ce cas, on risque de complexifier le problème car l'accès aux elements de la matrice demande d'utiliser plusieurs tables.
Et pour des matrice 8*8, est-ce bien utile de vouloir optimiser un calcul qui est de toute facon très rapide ?
On utilise des méthodes de stockage et de calcul pour des tailles de matrices à partir de centaines ou de milliers de lignes.

[salseropom]

Est-ce que ta matrice est diagonale par bloc ?

[progfou]

Non, c'est une multiplication d'une matrice dont l'une est une DCT, et l'autre correspond à un macroblock (codage MPEG-2).

[Invité]

Pour ameliorer ton calcul, tu peux déjà, comme il a été evoqué, au lieu de faire 3 boucles, en faire qu'une seule, ce qui risque d'etre assez moche, mais qui marchera un poil plus vite, apres, tu peux aussi remarquer que 8 = 2**3 et donc faire des décalages de bits plutot que des multiplications, et pour finir, essayer de paralleliser

[progfou]

Ce n'est pas destiné à une machine INTEL ou AMD...
Pas de parallélisation dispo.
Et les décalages, un -O3 avec GCC le fait déjà .

[Charlemagne]

S'il n'y a pas d'instructions SIMD disponibles (bizarre quand-même car ça existe sur la plupart des processeurs depuis pas mal d'années), voici quelques idées pour améliorer la vitesse:

1)Développer les boucles, surtout les boucles intérieurs

2)Utiliser le minimum de ponteurs, 3 doivent suffire pour 3 matrices

3)Stocker les matrices sous forme de vecteurs et faire des accès comme ceci:
X[3*8+5] pour la coordonnée (3,5). Il est important d'utiliser des constantes dans les crochets plutôt que des variables i,j,k: c'est possible grâce au développement des boucles

4)Faire de la rétention de valeurs dans les registres en "factorisant" les calculs, pour limiter les accès mémoire. Le facteur de factorisation dépend du nombre de registres (8 sur un pentium)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
for (int i=0; i<8; ++i)
  for (int j=0; j<8; j+=N)

    ...