Optimisation Vitesse d'Exécution Calcul matriciel

Bonjour à toutes et à toutes.

Pour un algorithme de traitement d'informations, je dois appliquer sur un tableau 600x600 un filtre de corrélation 21x21

Code:

---

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

int demiTaille = 10; for(int n=0; n< 600; ++n) for(int m=0; m<600; ++m) { int uBegin = std::max(0, n - demiTaille ); int uEnd = std::min(600- 1, n + demiTaille ); int vBegin = std::max(0, m - demiTaille ); int vEnd = std::min(600- 1, m + demiTaille ); double temp = 0.0; for(int u=uBegin; u<=uEnd; ++u) for(int v=vBegin; v<=vEnd; ++v) temp += abs(tabInitial[u][v]) * filter[demiTaille + u - n][demiTaille + v - m]; tabFinal[n][m] = temp; }

---

Le problème est que l'exécution de cette partie dure 0.4 secondes, ce qui est trop long pour mon application.

Est ce que quelqu'un aurait des solutions d'optimisation.

Merci d'avance :)

Bonjour,

est ce que tes conteneurs sont des vectors ?

alors au depart oui j'ai utiliser des vector<vector<double>>, mais l'exécution était alors de 4.2s.
donc j'ai essayé avec des double**, et la je passe à 0.4s

je n'ai pas essayer de faire un vector<double> de taille 600x600 par contre...

essaye :ccool:

Avec un double**, toutes tes données ne sont pas contiguë en mémoire. Avec un vector de taille 600*600 elle le seront et les accès mémoire seront beaucoup plus rapide.

Je te renvois là, ça pourrait t'aider:
http://www.developpez.net/forums/d10...cteur-vecteur/

Citation:

---

Envoyé par pyros

essaye :ccool:

Avec un double**, toutes tes données ne sont pas contiguë en mémoire. Avec un vector de taille 600*600 elle le seront et les accès mémoire seront beaucoup plus rapide.

---

Non, c'est pas garantie en C++98 (par contre toute les implémentations que je connaissent le sont oui )

une idée à tester, bien qu'il y a de grandes chances pour que le compilateur optimise ça lui-même, mais ne sait-on jamais:
- les tests d'arrêt de boucle. Ils sont appelés à chaque itération. Les == et != sont plus rapide que les <, >, <= ou >=

Après, moi je suis sûr que dans ce cas là, ce sera plus rapide avec des vector à une dimension et un iterateur, qu'avec un vector à une dimension et accès avec indice. Certainement pas un gain énorme, mais ce sera toujours ça de pris.

Et puis après, il faut chercher du côté de l'utilisation de threads, si tu as plusieurs cores ou plusieurs processeurs en particulier. Et surtout si tu peux trouver une méthode pour pouvoir permettre cela. Par exemple en découpant ta matrice en sous-matrices et appliquant le filtre dans des processus séparés, ce genre de choses.

Sinon iol doit bien y avoir des libs qui font ce genre de choses déjà non?

Citation:

---

Envoyé par r0d

Sinon iol doit bien y avoir des libs qui font ce genre de choses déjà non?

---

+++

** Dans le genre d'idée qui te feront gagner quelques pouillèmes (peu quantifiables?) : garnir tes lignes à gauches et à droites de 10 cases à 0 pour éviter les std::max/min. Ou alors, couper la boucle for pour gérer l'intérieur (n/m de 10 à 590) et gérer les bords séparément toujours pour éviter ces min/max inutiles.

** int demiTaille = 10; => int const demiTaille = 10; Ca ne fera rien gagner en vitesse mais c'est probablement plus exact dans ton code

** Cette dbouble boucle là :

Code:

---

1 2 3

for(int u=uBegin; u<=uEnd; ++u) for(int v=vBegin; v<=vEnd; ++v) temp += abs(tabInitial[u][v]) * filter[demiTaille + u - n][demiTaille + v - m];

---

Elle peut être exprimée en fonction de l'itération précédente (faire attention à l'impact du calcul numérique ??)

** (je ne sais pas si c'est encore vrai) : passer de double en int en supposant que tes grandeurs peuvent être représentées par un entier (modulo un coef de proportion)

Citation:

---

Non, c'est pas garantie en C++98 (par contre toute les implémentations que je connaissent le sont oui )

---

Plus par oubli que par volonté. D'ailleurs, certaines interprétations de la sainte norme affirment que la contigüité est sous-entendu.

Cependant, le std::vector est tellement utilisé en tant que wrapper entre container C++ et fonction C classique (comme read/write) que si un jour quelqu'un s'amusait à sortir une implémentation différente, il n'aurait pas beaucoup de succès :mrgreen:

merci pour toutes ses réponses, quel succès 8-) !

d'habitude j'utilise souvent les conteneurs tel que vector, c'est juste la que c'était plus rapide.
j'ai commencer à implémenter un vector<double> 600x600.
en faisant juste cela je passe à 1.2s, ce qui est toujours plus long qu'avec mon double**, mais je vais utiliser les messages précédents pour essayer d'affiner mon code et donnerai ma meilleure solution selon ce que je trouve.

concernant le const demiTaille = 10;
en fait non je ne peux pas le mettre en const, je l'ai mis la pour la compréhension du code montré, mais en fait cette variable est calculée en amont en fonction de certains paramètres propres à chaque instance de ma classe (mais merci pour l'intention ;)).

je vous tiens, au courant, tout en restant ouvert à toute proposition !

j'ai essayé de réduire mon algo à 10-590 et ainsi enlever les min et max, aucun changement à l'horizon.
je ne l'avais pas fait mais j'ai aussi mis "filter" en vector 1D.

j'ai aussi mi un iterator pour les vector "filter" et "tabFinal".
je ne l'ai pas fait pour tabInitial, car lors du calcul je n'utilise pas les valeurs contiguës donc je ne suis pas certain du résultat

mon temps est maintenant à 1.5s, toujours inférieur au double**, avec le code suivant

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

std::vector<double>::iterator iteratorFinal = m_resFinal.begin(); for(int n=halfSizeFilter; n!=nbPixV-halfSizeFilter; ++n) { int index = n * nbPixH; for(int m=halfSizeFilter; m!=nbPixH-halfSizeFilter; ++m) { int uBegin = n - halfSizeFilter; int uEnd = n + halfSizeFilter; int vBegin = m - halfSizeFilter; int vEnd = m + halfSizeFilter; double temp = 0.0; std::vector<double>::const_iterator iterFilter = diskFilter.begin(); for(int u=uBegin; u!=uEnd+1; ++u) { int index2 = u * nbPixH; int indexF = (halfSizeFilter + u - n) * sizeFilter; for(int v=vBegin; v!=vEnd+1; ++v) { temp += abs(m_res[index2 + v]) * (*iterFilter); ++iterFilter; } } maxResFinal = std::max(maxResFinal, temp); *iteratorFinal = temp; ++iteratorFinal; } }

---

Par contre la j'ai une erreur dans mon résultat final à cause d'un des deux itérator:oops:

@3DArchi :

Citation:

---

Elle peut être exprimée en fonction de l'itération précédente (faire attention à l'impact du calcul numérique ??)

---

Je ne vois pas trop ce que tu veux dire...

alloue 620 au lieu de 600 pour te débarasser des cas particuliers

Citation:

---

Envoyé par screetch

alloue 620 au lieu de 600 pour te débarasser des cas particuliers

---

je sais, pour le moment je restreint mon parcours à 10-590, si je dois allouer à 620, ça va me faire un paquet de modifs dans le code, et pour le moment je me concentre déjà sur l'optimisation de cette partie ;)

dacodac.
des instructions SSE?

on ne boucle *jamais* sur les valeurs d'un filtre ...
Ensuite 21x21, ca commence a faire, et je pense que tu irais bcp plus vite a faire un coup de FFT puis de FFTI avec FFTW.

Sinon dans l'ordre :
- alignement de la memoire sur la taille des lignes de caches
- paddign en fin de ligne
- vector<vector> a remplacé par un tableau NRC contigu
- deroule la boucle du filtrage entierement
- SSE2
- OpenMP

Je pense que Joel F a tout résumé.

Et si les perf te suffisent toujours pas => CUDA/Shader. Mais là c'est une autre histoire.

What about utiliser le GPU?

je n'ai encore jamais fait de programmation GPU, mais j'avais songé que ce serait peu être une solution à moyen terme, mais je n'ai pas forcément le temps d'appréhender cette programmation si les perfs ne sont pas au rendez-vous!

Citation:

---

Envoyé par r0d

What about utiliser le GPU?

---

pas pour 600x600 pauvres valeurs ... tu va payer 100000 fois le temps de trasnfert et avoir une acceleration moisie.

J'avais pas vu ce poste :

Citation:

---

Envoyé par r0d

une idée à tester, bien qu'il y a de grandes chances pour que le compilateur optimise ça lui-même, mais ne sait-on jamais:
- les tests d'arrêt de boucle. Ils sont appelés à chaque itération. Les == et != sont plus rapide que les <, >, <= ou >=

---

Si c'est vrai, c'est qu'il est temps pour toi de changer de compilateur. Ces micro-optimisations n'ont absolument aucun effet.

Citation:

---

Envoyé par r0d

Après, moi je suis sûr que dans ce cas là, ce sera plus rapide avec des vector à une dimension et un iterateur, qu'avec un vector à une dimension et accès avec indice. Certainement pas un gain énorme, mais ce sera toujours ça de pris.

---

Non, ca sera plus rapide avec un tableau 2d contigu acceder via des [][] en notation NRC. Et en general, iterateur , pointeur == meme vitesse.

Citation:

---

Envoyé par Joel F

notation NRC

---

Et pour ceux qui ne parle pas le Joel couramment :aie: , NRC ça veut dire quoi :koi:

Vectors Iliffe de leur petit nom. (et NRC pour numerical recipe in C).

Citation:

---

Plus par oubli que par volonté.

---

J'ai pas dis le contraire, et l'origine ne change rien au fait que c'est pas garantie.

Citation:

---

D'ailleurs, certaines interprétations de la sainte norme affirment que la contigüité est sous-entendu.

---

C'est pas la mienne. (d'interprétation)

Citation:

---

Envoyé par 3DArchi

Et pour ceux qui ne parle pas le Joel couramment :aie: , NRC ça veut dire quoi :koi:

---

Je vais finir par faire une entrée dans la FAQ ^^

Tableaux NRC == tableaux alloués selon la methode preconisée dans Numerical Recipes in C.

Citation:

---

Envoyé par Joel F

Je vais finir par faire une entrée dans la FAQ ^^

---

Chiche. Il y le dico aussi pour ça :mrgreen:

Citation:

---

Envoyé par Joel F

Tableaux NRC == tableaux alloués selon la methode preconisée dans Numerical Recipes in C.

---

:merci: En même temps, je comprends pourquoi ça ne m'évoquait rien. Ca sent l'analyse numérique (qui n'est pas mon meilleur souvenir)

Citation:

---

Envoyé par Goten

Non, c'est pas garantie en C++98 (par contre toute les implémentations que je connaissent le sont oui )

---

La contigüité dans les vecteurs est garantie en C++03.
Pour les sttring, j'ai la flemme de chercher si c'est maintenant assuré dans le C++11.

Citation:

---

Envoyé par 3DArchi

Chiche. Il y le dico aussi pour ça :mrgreen:
:merci: En même temps, je comprends pourquoi ça ne m'évoquait rien. Ca sent l'analyse numérique (qui n'est pas mon meilleur souvenir)

---

Je pensais a la FAQ, histoire qu'on ai le bout de code d'example avec.

Salut,

J'en viens aux nouvelles, tu as réussi ?

Sinon, je crois qu'en c++, tu peux directement intégrer du code assembleur :D

Citation:

---

Envoyé par Joel F

pas pour 600x600 pauvres valeurs ... tu va payer 100000 fois le temps de trasnfert et avoir une acceleration moisie.

---

sauf en host alloc

Avant de passer à une version SSE ou GPU, il faudrait peut être faire des choses simples avec un impact assez immédiat, comme sortir les calculs non nécessaires des boucles les plus imbriquées, éliminer au mieux les multiplications (par exemple, u augmente de 1 en 1, donc index2 va augmenter de nbPixH en nbPixH ; il y a quelques autres exemples), simplifier le calcul des bornes, changer la représentation mémoire, etc.

Ce code peut être optimisé de manière assez violente avant même de penser à changer de techno.

sinon pour savoir exactement exactement ou ton code à des eprtes de performances tu peux te former dans l'utilisation d'outils de profiling.

http://matthieu-brucher.developpez.c...visual-studio/

suivant les opinions d'une ou deux personnes que j'ai recontré, les vectors on des gros problèmes de perfomances ( 15% du temps passé pour certains algorithmes est utilisé dans l'operateur [] )

Je suppose que je le code est utilisé pour du traitement d'image, passer dans le domaine fréquentiel (FFT/FFTi) est généralement une bonne idée pour gagner en performances

Citation:

---

Envoyé par xelif

suivant les opinions d'une ou deux personnes que j'ai recontré, les vectors on des gros problèmes de perfomances ( 15% du temps passé pour certains algorithmes est utilisé dans l'operateur [] )

---

Etrange - à moins qu'ils n'aient fait les tests de performance en release débug. L'opérator [] est du vector est inliné en mode release.

Le code de operator[] pour la libstdc++ de gcc :

Code:

---

1 2 3 4

reference operator[](size_type __n) { return *(this->_M_impl._M_start + __n); }

---

Ce qui est strictement équivalent à l'accès à une entrée d'un tableau simple (déréférencement d'une pointeur + offset)

As-tu activé le max d'optimisations niveau compilo ?
Il me semble que setter la macro _SECURE_SCL à 0 (qui permet de s'assurer que tu ne fais pas de bêtises avec les containers de la STL) te donnera un petit gain. Le multithreading avec répartition de charges te donnera de biens meilleurs performances aussi.

Si ça te dit poste un main.cpp qui compile tout seul et j'essaye de faire des améliorations.
Ca me fera plaisir de faire un peu d'optimisation, ça fait longtemps ;)

voici ce que j'ai fait (c'est-à-dire pas grand chose)
et en mettant des tableaux C (des double* quoi) ça va 3,5 fois plus vite chez moi. (sous visual studio 2008 Express avec les options d'optimisation de base)

j'imagine que GCC doit faire bien mieux.
Sans parler d'ICC.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124

#include <Windows.h> #include <cstdlib> #include <cstdio> #include <cmath>   // timer pour afficher les perfs struct timer { LARGE_INTEGER _start, _stop, _freq ; timer () { ::QueryPerformanceFrequency(&_freq); } void start () { ::QueryPerformanceCounter(&_start); } double stop () { ::QueryPerformanceCounter(&_stop); return double (_stop.QuadPart - _start.QuadPart) / double (_freq.QuadPart) ; } }; // petite fonction d'allocation pour les double** double** allocate(int n) ; void desallocate(double** a, int size) ;   void fonction1 (); // la tienne (sans rien changer) void fonction2(); // la mienne   // -------------- MAIN ------------------------   int main (int argc, char** argv) { fonction1 (); fonction2 (); } // -------------- MAIN ------------------------   double** allocate(int n) { double** res = (double**) malloc(600*sizeof(double*)); for (int i=0; i<600; ++i) res[i] = (double*) malloc(600*sizeof(double)); return res ; }   void desallocate(double** a, int size) { for (int i = 0 ; i < size ; ++i) free(a[i]); free(a); }   void fonction1 () { timer tim ;   double** tabInitial = allocate(600); double** tabFinal = allocate(600); double** filter = allocate(21);     tim.start () ;   int demiTaille = 10;   for(int n=0; n< 600; ++n) { for(int m=0; m<600; ++m) { int uBegin = max(0, n - demiTaille ); int uEnd = min(599, n + demiTaille ); int vBegin = max(0, m - demiTaille ); int vEnd = min(599, m + demiTaille ); double temp = 0.0; for(int u=uBegin; u<=uEnd; ++u) { for(int v=vBegin; v<=vEnd; ++v) { temp += abs(tabInitial[u][v]) * filter[demiTaille + u - n][demiTaille + v - m]; } } tabFinal[n][m] = temp; } }   ::printf("fonction initiale : %f\n", tim.stop ()); desallocate(tabInitial, 600); desallocate(tabFinal, 600); desallocate(filter, 600); }     void fonction2 () { timer tim ;   int demiTaille = 10;   double* tabInitial = (double*) malloc(600*600*sizeof(double)) ; double* tabFinal = (double*) malloc(600*600*sizeof(double)) ; double* filter = (double*) malloc(21*21*sizeof(double)); tim.start () ;   int ind = 0 ; for (int n = 0; n < 600; ++n) // loop on main matrix { for (int m = 0 ; m < 600 ; ++m, ++ind) { double temp = 0. ; int uBegin = max(0, n - demiTaille ); int uEnd = min(599, n + demiTaille ); int vBegin = max(0, m - demiTaille ); int vEnd = min(599, m + demiTaille ); for(int u=uBegin; u<=uEnd; ++u) { int uu=demiTaille+u -n ; for(int v=vBegin; v<=vEnd; ++v) { int vv=demiTaille+v-m; temp += abs(tabInitial[u*600+v]) * filter[uu*21 + vv]; } } tabFinal[ind] = temp; } } ::printf("fonction mieux : %f\n", tim.stop ());   free(tabInitial); free(tabFinal); free(filter);   }

---

Avec un compilo qui fait bien son boulot:
http://stackoverflow.com/questions/3.../381656#381656