Optimisation Vitesse d'Exécution Calcul matriciel

**olivier21c** · 26/05/2011, 11h51

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 :

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

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

**Nhaps** · 26/05/2011, 11h55

Bonjour,

est ce que tes conteneurs sont des vectors ?

**olivier21c** · 26/05/2011, 11h59

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...

**pyros** · 26/05/2011, 12h27

essaye

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/

**Goten** · 26/05/2011, 13h01

Envoyé par pyros

essaye

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 )

**r0d** · 26/05/2011, 13h55

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?

**3DArchi** · 26/05/2011, 14h24

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 :

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

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)

**pyros** · 26/05/2011, 14h27

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

**olivier21c** · 26/05/2011, 14h32

merci pour toutes ses réponses, quel succès

!

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 !

**olivier21c** · 26/05/2011, 15h12

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 :

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

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

@3DArchi :

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...

screetch · 26/05/2011, 15h18

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

**olivier21c** · 26/05/2011, 15h22

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

screetch · 26/05/2011, 15h26

dacodac.
des instructions SSE?

**Joel F** · 26/05/2011, 15h35

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

**pyros** · 26/05/2011, 15h43

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.

**r0d** · 26/05/2011, 16h00

What about utiliser le GPU?

**olivier21c** · 26/05/2011, 16h31

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!

**Joel F** · 26/05/2011, 16h58

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.

**Joel F** · 26/05/2011, 17h01

J'avais pas vu ce poste :

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.

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.