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: