Multiplication de deux matrices

Salut à tous,

En faisant le profiling de mon programme, j'ai retrouvé que le hot path est la fonction que j'ai définit pour la multiplication entre deux matrices, voici son code

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

vector<double> Multiplication(vector<double>const & a,vector<double>const & b,int m) { int i,j,w; int l(a.size()/m); int e(b.size()/m); double sum; vector<double> cl; cl.reserve(l*e); for(int i(0);i<l;++i) for(int j(0);j<e;++j) { sum=0; for(int w(0);w<m;++w) { sum=sum+a[i*m+w]*b[w*e+j]; } cl.push_back(sum); } return(cl); }

---

Alors est ce que je peux faire mieux ??

Bonjour

Oui :
- lisibilité (indentation)
- compréhension (noms des variables, commentaires)
- performance (tiling, parallélisme)
- simplicité (et performance) (pourquoi ne pas appeler une bibliothèque dédié au calcul matriciel comme BLAS via Boost.uBLAS)

Pardon c'est vrai les indices ne snt pas compréhensible, voici le code de nouveau

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

vector<double> Multiplication(vector<double>const & a,vector<double>const & b,int m) { int i,j,w; int l(a.size()/m);//ligne de la matrice a int e(b.size()/m);//colonne de la matrice b, m nombre de colonne de a et les lignes de b double sum; vector<double> cl;//la matrice produit cl.reserve(l*e); for(int i(0);i<l;++i) for(int j(0);j<e;++j) { sum=0; for(int w(0);w<m;++w) { sum=sum+a[i*m+w]*b[w*e+j]; } cl.push_back(sum); } return(cl); }

---

Si j'appelle une bibliothèque dédié au calcul matricielle est ce que elle peux faire carément la multiplication des deux matrices est ça sera en performance mieux

j'ai cherché sur le tiling, parallélisme mais j'ai pas trouvé grand chose :( sinon est ce que ça va m'aider d'une façon remarqueble ???

Si elle est orientée fonction, oui si la fonction 2mm existe.
Sinon, il faut prendre des bibliothèques comme NT².

Pour le tiling ou le parallélisme, sur des cas aussi simples que des multiplications de matrices, un compilateur polyhédrique comme PoCC ou Pluto s'en sort très bien :)

Sincèrement je suis perdu dans les bibliothèque, j'arrivepar à retrouvé la fonction :?

J'ai un autre hot path:c'est la fonction sous_matrice qui prend en paramètre une matrice a et un tableau b et retourne une sous matrice de a dont les colonne sont les colonne de a d'indice dans b, le code source est le suivant

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

vector<double> sous_matrice(vector<double>const & a,vector<int>const & b, int m, int e) { int l(a.size()/m);//m:nombre de colonne de a, l:nombre de ligne de a vector<double> cl;// la sous matrice à retourné cl.reserve(m*e);// e la taille du tableau b for(int i(0);i<m;++i) for(int j(0);j<e;++j) { cl.push_back(a[i*l+b[j]]);//l'instruction hot } return(cl); }

---

Est ce que je peut l'améliorer ?? (j'espère que le code est indenté)

Citation:

---

Envoyé par Ehonn

Bonjour
- performance (tiling, parallélisme)

---

maintenant j'ai compris ce que tu voulais dire Ehonn à travers ce site msdn.microsoft.com/en-us/library/hh873134.aspx ;)

reimplantez MM a la main (sauf exercice scolaire) est inutile. On sort un bon BLAS et hop;

Bonjour,

après une lecture rapide de ton code, voici plusieurs remarques générales :

1. ce n'est pas utile d'utiliser un conteneur tel que vector puisque les tailles de tes matrices doivent être connues a priori;
2. modéliser le comportement des matrices à l'aide d'une classe améliorerait la simplicité et la lisibilité de ton code;
3. dans la mesure du possible, indiquer à son compilateur où et comment optimiser (register, inline, const, ...);
4. respecter le principe de localité des données;
5. promouvoir la réutilisation des mémoires caches en découpant tes matrices en blocs;
6. la parallélisation est évidemment à conseiller mais l'extensibilité de ton code dépendra très fortement du point précédent;
7. utiliser les bonnes options de compilation (O2,O3,etc) pour optimiser ton code permet de gagner en performances;
8. le recours à des bibliothèques externes ne t'apprendra pas grand chose sur l'optimisation de code mais te fera gagner un temps considérable;
9. privilégier les générateurs de codes optimisés pour ta machine (Atlas, Goto, Intel MKL, ...) sinon la performance ne sera pas au rendez-vous;
10. puisque tu écris ton code en C++, les expression templates sont susceptibles de t'intéresser;
11. les instructions SIMD sont susceptibles de t'intéresser;
12. les manuels de référence sur l'optimisation proposés par Intel sont susceptibles de t'intéresser;
13. la notion de "cache-oblivious algorithm" est susceptible de t'intéresser;
14. les techniques de transformation de programme sont susceptibles de t'intéresser.