Matrice, template, optimisation.

Version imprimable

16/02/2011, 19h24
NoIdea

Matrice, template, optimisation.

Bonjour à tous, j'essaie de créer une classe Matrice la plus rapide possible.

Je vous demande donc quelques conseils.

Quelques informations :

-Les éléments de ma matrice sont contigus en mémoire (j'ai un T* et non un T**).
-Le nombre de ligne et de colonnes est connus à la compilation (ce sont des templates)

Quelques questions :

En utilisant les templates, et en particulier std::is_pod, j'ai pensé qu'on pourrait optimiser les copies.

-Comment optimiser la création de la matrice ou tous les éléments sont à une valeur donnée et les éléments des pod ? (memset marche que pour des taille d'un octet).
-utiliser memcpy pour les copies si T est un POD.
-Existe-il pour les matrices de manière non intuitive d'effectuer des opérations pour les accélérer (multiplication de matrice, mise à une puissance d'une matrice, ...). Par exemple, lors d'une mise à une puissance, puisque la taille est connue à la compilation, décomposé les facteurs de chaque opération à la compilation ?
-Autres astuces ?

Merci.

SVP, ne dites pas qu'il faut faire quelque chose qui marche avant d'optimiser.
16/02/2011, 19h38
Joel F

Citation:

Envoyé par NoIdea

-Les éléments de ma matrice sont contigus en mémoire (j'ai un T* et non un T**).

Tu peux avoir un T** et un stockage continue, cf Pointeur de Iliffe.

Citation:

Envoyé par NoIdea

En utilisant les templates, et en particulier std::is_pod, j'ai pensé qu'on pourrait optimiser les copies.

std::copy fait deja ca tout seul.

Citation:

Envoyé par NoIdea

-Existe-il pour les matrices de manière non intuitive d'effectuer des opérations pour les accélérer (multiplication de matrice, mise à une puissance d'une matrice, ...). Par exemple, lors d'une mise à une puissance, puisque la taille est connue à la compilation, décomposé les facteurs de chaque opération à la compilation ?

Plein, des theses entieres sont faites dessus tout les ans. Je te donne 6 mois avant d'arreter de vouloir faire mieux que BLAS/LAPACK.

Citation:

Envoyé par NoIdea

-Autres astuces ?

Ne reinvente pas la roue :o
16/02/2011, 20h45
Goten

Citation:

Envoyé par NoIdea

Bonjour à tous, j'essaie de créer une classe Matrice la plus rapide possible.

Je vous demande donc quelques conseils.

Ne le fais pas.
16/02/2011, 21h48
Invité

Bonjour,

La façon d'optimiser (et de stocker, d'ailleurs) va beaucoup dépendre du type de données que tu auras dans tes matrices, et du type de traitements que tu entends leur infliger.

Quelques questions qu'il faut te poser, sur la nature des données :

1- quelle est la taille de tes matrices? si elles sont à peu près carrées, et de petite dimension, les méthodes compliquées d'optimisation sont généralement peu utiles.
2- tes matrices sont elles pleines ou creuses ?(les creuses ca ne se stocke pas pareil, et donc ca ne se traite pas pareil) Ont elle des caractéristiques particulières (genre beaucoup de matrices carrées, ou symétriques, ou des coefficients bornés, ou...)
3- tes matrices sont elles de "vraies" matrices, avec une forte équivalence entre lignes et colonnes, ou sont elles des tableaux de données (par exemple avec des questions en colonnes et des individus en ligne...)? Dans le second cas, ce qui compte c'est généralement davantage de stocker les données dans le "bon ordre" que d'utiliser des algorithmes génériques.
4- tes données sont elles exactes, ou de nature statistique? Dans le second cas, comme tu peux remplacer une matrice par une autre matrice "voisine", tu vas utiliser toutes sortes d'algorithmes particuliers.

Sur les traitements, si tu fais de l'algèbre "de base" (additions, produits, ...) sur un grand nombre de matrices, les principal facteur d'optimisation sont d'éviter les copies intermédiaires, et le stockage si tu as des matrices creuses. Si tu fais des stats, et que tu inverses ou que tu diagonalises, alors les considérations de stabilité du calcul prendront toujours le pas sur la vitesse (traiter vite mais faux n'est pas une bonne idée).

Pour une bonne introduction générale, et des exemples dans des domaines variés, essaye Numerical Recipes in C++, il y a beaucoup de choses (pas juste sur les matrices), ça ne demande pas un niveau de maths trop élevé, c'est très bien écrit, et il y a des exemples. Cherche la 3eme édition (le bouquin noir) plutôt que la seconde (le rouge), il y a pas mal de choses en plus.

Francois
17/02/2011, 10h40
Aleph69

Bonjour,

Citation:

Envoyé par NoIdea

Comment optimiser la création de la matrice ou tous les éléments sont à une valeur donnée et les éléments des pod ?

Ne stocker la valeur qu'une seule fois dans un scalaire.

Citation:

Envoyé par NoIdea

Existe-il pour les matrices de manière non intuitive d'effectuer des opérations pour les accélérer (multiplication de matrice, mise à une puissance d'une matrice, ...).

Regarde l'algorithme de Strassen. Attention à trouver un bon compromis entre stabilité et rapidité à chaque fois.

Plus généralement, pour aller vite il y a le parallélisme... voir le gpgpu puisque c'est à la mode... voir de la parallélisation hybride puisque c'est un sujet de recherche actuel. Un autre moyen consiste à t'acheter un supercalculateur... :lol:
17/02/2011, 10h55
Joel F

Citation:

Envoyé par Aleph69

Regarde l'algorithme de Strassen. Attention à trouver un bon compromis entre stabilité et rapidité à chaque fois.

Strassen est impracticable en geenral car tres complexes a coder. Il n'as d'interet que pour des matrices denses de tres grande tailles.

Citation:

Envoyé par Aleph69

Plus généralement, pour aller vite il y a le parallélisme... voir le gpgpu puisque c'est à la mode... voir de la parallélisation hybride puisque c'est un sujet de recherche actuel. Un autre moyen consiste à t'acheter un supercalculateur... :lol:

Cooli sur les GPUs. Deja SIMD+openMP et on en reparle.
17/02/2011, 11h27
Aleph69

Bonjour Joel,

concernant les très petites matrices, j'étais tombé là-dessus si ça t'intéresse :
http://www.csd.uwo.ca/~eschost/publi...s/DrIsSc09.pdf

Sinon, pour Strassen-Winograd , le problème c'est la stabilité numérique. C'est surtout pour cela qu'on ne l'utilise presque jamais. Dans le cas contraire, la complexité de l'implémentation n'arrêterait personne à mon avis.
17/02/2011, 11h55
Invité

Citation:

Envoyé par Aleph69

Bonjour Joel,
Sinon, pour Strassen-Winograd , le problème c'est la stabilité numérique. C'est surtout pour cela qu'on ne l'utilise presque jamais. Dans le cas contraire, la complexité de l'implémentation n'arrêterait personne à mon avis.

Pas seulement. La complexité de l'algorithme se traduit généralement par une augmentation du coefficient du terme dominant, ou des termes juste en dessous. Sur de grosses matrices, l'amélioration est réelle, sur de petites, il faut faire le calcul.

C'est d'ailleurs pour cela qu'on a un problème de stabilité. L'algorithme de Strassen est exact, il n'y a donc en théorie pas que problème de stabilité, si on utilise des mantisses suffisantes, ou des méthodes adaptées, mais celles ci se traduisent pas une augmentation des coefficients dominants, qui repoussent les conditions d'utilisation de la méthode.

Ensuite, sur de petites matrices, des optimisations "machine" entrent en ligne de compte, qui font qu'un algorithme plus efficace sur le papier ne l'est pas toujours en pratique.

Francois
17/02/2011, 14h48
Aleph69

Bonjour François,

Citation:

Envoyé par fcharton

Pas seulement. La complexité de l'algorithme se traduit généralement par une augmentation du coefficient du terme dominant, ou des termes juste en dessous. Sur de grosses matrices, l'amélioration est réelle, sur de petites, il faut faire le calcul.

Il y a un malentendu sur le terme de complexité. Je n'évoquais pas la complexité algorithmique mais la "complexité d'implémentation" c'est-à-dire la difficulté à programmer l'algorithme. Je reconnais volontiers que ma phrase était ambigue et que j'aurais dû utiliser un vocabulaire plus clair. En particulier, je ne remets pas du tout en cause ce qu'a dit Joel sur les petites/moyennes matrices.

Citation:

Envoyé par fcharton

C'est d'ailleurs pour cela qu'on a un problème de stabilité. L'algorithme de Strassen est exact, il n'y a donc en théorie pas que problème de stabilité, si on utilise des mantisses suffisantes, ou des méthodes adaptées, mais celles ci se traduisent pas une augmentation des coefficients dominants, qui repoussent les conditions d'utilisation de la méthode.

L'algorithme de Strassen n'est pas backward stable (théorie).
17/02/2011, 18h10
Joel F

surtout deja avant de strassen, je pense que faire bu blocking et du loop unrolling proprement en SIMD suffit largement pour les matrices de tailles raissonable.