Discussion :

[yan]

Mongaulois : déplacement provenant de ce thread http://www.developpez.net/forums/sho...d.php?t=521229



Salut.
J'aurais peut être un piste, mais ca va être dure l'expliquer
A mon boulot, nous avons constater des problème de performance significative sur du filtrage d'image dans des cas particulier avec les proc intel avec 2 et 4 coeur (je ne sait pas pour AMD).
C'est assez difficile à expliquer donc voici un code tout bête qui créé deux mémoire de même taille puis copie une partie de l'une vers l'autre avec un décalage s dans les indices :

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
29
#include <iostream>
#include <fstream>
#include <ctime>
 
#define TYPE long
 
const int size = 1920*1080*2;
const int sborn = 1400;
int main(int argc, char** argv)
{
    TYPE *tab1 = new TYPE[size];
    TYPE *tab2 = new TYPE[size];
    std::ofstream fout("courbe.txt");
    for (int s=-sborn;s<=sborn;++s)
    {
        std::clock_t time1 =std::clock();
        int aa;
        //pour un meilleur calcul de temps
        for (aa=0;aa<20;++aa)
            for (int i =1500;i<size-1500;++i)
            {
                //on fait une copie avec un décalage s
                tab1[i] = tab2[i+s];
            }
        std::clock_t dif = std::clock()-time1;
        fout<<s<<"  "<<static_cast<double>(dif)/aa<<std::endl;
    }
	return 0;
}

En fonction du décalage de s les performance peuvent être un multiple de 10 !!!
et cela avec s =-1, s=1024 s =-1024 (dépend de la taille et proc et je ne sais pô)
On pense à un problème de prédiction du proc.
Si vous avez plus d'indice ca m'interrese.
Le plus grave dans tout ca est comme le problème apparait avec s=-1, un simple filtrage sur x de taille 3 est moins performant qu'un filtrage sur y de taille 3!!!!


Voici un pdf qu'il apperemment explique tout sur la memoire. Pas encore regarder
http://people.redhat.com/drepper/cpumemory.pdf

[screetch]

tab[i] = tab[i-1];

c'est une operation qui "stall" car elle doit attendre la complétion de l'operation precedente tab[i-1] = tab[i-2] pour reutiliser la valeur tab[i-1]

tab[i] = tab[i+1023] (pour moi) c'est peut etre du a la taille d'une page physique. J'attaque ce probleme la =)

[screetch]

ok, voila mes conclusions!

comme je te le disais, lorsque tu effectues l'operation
tab[i] = tab[i-1]

le processeur effectue l'operation, et avant de stocker le resultat en memoire, poursuit sur l'evaluation de l'instuction suivante.
or, l'instruction suivante (tab[i+1] = tab[i]) relit tab[i]. le programme doita alors s'arreter, attendre la fin de l'ecriture de tab[i] pour le relire.

il le fait de la facon assez complexe decrite ici
http://en.wikipedia.org/wiki/Memory_...oad_forwarding

en gros, il mets dans une memoire speciale la valeur qu'il inscrira plus tard :

When a load executes, it searches the store queue for in-flight stores to the same address that are logically earlier in program order. If a matching store exists, the load obtains its data value from that store instead of the memory system. If there is no matching store, the load accesses the memory system as usual; any preceding, matching stores must have already retired and committed their values. This technique allows loads to obtain correct data if their producer store has completed but not yet retired.

lorsque s vaut -1, on est un peu couillonné, on doit attendre que l'operation precedente aie fini pour charger la valeur.
fait interessant, cette memoire speciale ne fait pas 4Go (ca serait trop facile); celle ci occuppe en general 4ko. Le processeur n'enregistre pas toute les valeurs dans cette memoire; il peut donc y avoir des collisions. que ce passe t'il en cas de collision ? on croit que l'on doit attendre la fin d'une operation, alors qu'en fait c'est pas vrai, elle doit se passer a un autre emplacement en memoire. cela fonctionne comme le cache L1 et L2 :
http://en.wikipedia.org/wiki/CPU_cache#Associativity

c'est a dire que, comme dans ce schema, 0 et 4 partagent le meme cache, 1 et 5 un autre, etc etc

et si 0 utilise le cache, il jette la valeur que 4 y avait placée.

OR, donc, je disais que la memoire du store-and-load-forward faisait 4096 octets. nous savons qu'en accedant a l'octet -4 (sizeof float) on doit attendre la fin de l'operation, c'est vrai si une operation a aussi touché l'octet
-4 +- 4096! soit, en travaillant avec des int,
-1, -1-1024, -1-2048, -1+1024, -1+2048

voila donc pourquoi les ecritures -1, -1025, +1023 sont plus lentes.

[Charlemagne]

c'est a dire que, comme dans ce schema, 0 et 4 partagent le meme cache, 1 et 5 un autre, etc etc

Oui, c'est le genre de trucs auquel il faut faire gaffe quand on optimise un algo pour le cache.
Le processeur prend les n bits de poids faible de l'adresse , n varie bien sûr selon la taille du cache. C'est pour ça que toutes les adresses identiques modulo n se partagent le même emplacement du cache.
Par contre pour chaque emplacement il y a visiblement 2 cases. (sinon je comprends plus rien du tout au cache). Quand le programme fait une lecture en mémoire, je pense le processeur remplace la case la plus anciennement utilisée.

[yan]

Le code que j'ai mis est avec deux memoire distinct
tab1[i] = tab2[i+s];

[Charlemagne]

Le code que j'ai mis est avec deux memoire distinct
tab1[i] = tab2[i+s];

J'y verrai peut-être également une histoire de page physique, mais sans conviction. Je crois savoir que les processeurs préchargent les pages entières à l'avance.

Sinon, pour optimiser ta boucle, tu peux calculer l'adresse avec l'offset plutôt que de faire un "+s" à chaque accès mémoire.
Du genre

Code :

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

1
2
3
tab3=tab2+s;
for (...)
  tab1[i]=tab3[i];

[yan]

Sinon, pour optimiser ta boucle, tu peux calculer l'adresse avec l'offset plutôt que de faire un "+s" à chaque accès mémoire.

le compilot doit le faire.. non?

[yan]

Voici la courbe que j'obtiens avec mon core2Duo6400

Le plus drôle est que l'on peut décaler le problème en faisant :

Code :

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

1
2
TYPE *tab2 = new TYPE[size];
TYPE *tab2 = new TYPE[size+96]+96;

Ce qui permet d'optimiser un filtrage sur x

et que si l'on fait

Code :

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

1
2
3
 
TYPE *tab2 = new TYPE[size+96]+96;
TYPE *tab2 = new TYPE[size+96]+96;

on retombe sur 1... Le filtrage sur x perd sa performance

[edit]
incroyable j'envoie mon message et le tiens est après. Si ça c'est pas synchro

[Charlemagne]

le compilot doit le faire.. non?

Pas d'après mon expérience. Et pourtant j'utilise principalement le compilo d'Intel, qui me donne des résultats meilleurs que Visual ou GCC.
Dans un cas trivial comme celui là, peut-être, mais j'en doute.
Et ça dépend de toute façon du compilo. Dans l'ensemble il vaut mieux l'aider du mieux qu'on peut.

[screetch]

Le code que j'ai mis est avec deux memoire distinct
tab1[i] = tab2[i+s];

ca n'empeche pas tab1 et tab2 d'etre align+e modulo 4096

[screetch]

dans ton resultat, affiche aussi la valeur (&tab1[i] - &tab2[i+s]) modulo 4096 pour voir que ca tombe mochement quand le modulo devient 0.

[yan]

dans ton resultat, affiche aussi la valeur (&tab1[i] - &tab2[i+s]) modulo 4096 pour voir que ca tombe mochement quand le modulo devient 0.

Je regarderais ca ce soir

[screetch]

d'ailleurs je dis des betises. verifie que le resultat est 1 (ou -1 selon ta difference) pour montrer que ca depend de l'operation precedente.

je te fais un code optimisé entre temps.

[screetch]

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
29
30
31
 
int main(int argc, char** argv)
{
    TYPE *tab1 = new TYPE[size];
    TYPE *tab2 = new TYPE[size];
    std::ofstream fout("courbe.txt");
    for (int s=-sborn;s<=sborn;++s)
    {
        std::clock_t time1 =std::clock();
        int aa;
        //pour un meilleur calcul de temps
        for (aa=0;aa<20;++aa)
		{
			for (int i =1500;i<size-1500;i+=8)
			{
				//on fait une copie avec un décalage s
				tab1[i] = tab2[i+s];
				tab1[i+1] = tab2[i+1+s];
				tab1[i+3] = tab2[i+3+s];
				tab1[i+6] = tab2[i+6+s];
				tab1[i+2] = tab2[i+2+s];
				tab1[i+7] = tab2[i+7+s];
				tab1[i+5] = tab2[i+5+s];
				tab1[i+4] = tab2[i+4+s];
			}
		}
        std::clock_t dif = std::clock()-time1;
        fout<<s<<"  "<<static_cast<double>(dif)/aa<<std::endl;
    }
	return 0;
}

voila j'explique ce que ce code fait :
il copie les valeurs dans un ordre assez bizarre qui est censé lisser la courbe

lorsque du fait tab1[i] = tab2[i+s] a repetition, en deroulant, voila ce que ca donne :

Code :

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

1
2
3
4
5
6
 
tab1[0] = tab2[s]
tab1[1] = tab2[s+1]  //tab2[s+1] ets aligne avec tab1[s]
tab1[2] = tab2[s+2]  //une fois sur 1024
tab1[3] = tab2[s+3]  // de meme ici, tab2[s+3] est aligne avec tab1[2]
...

donc une fois sur 1024 ton code est tout lent.
avec mon code cela s'etend comme ca :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
tab1[0] = tab2[0+s];
tab1[1] = tab2[1+s]; //peut etre 1+s aligné avec 0, si s=-1
tab1[3] = tab2[3+s]; //mais alors 3+s est pas aligné sur 1
tab1[6] = tab2[6+s]; //ni 6+s sur 3
tab1[2] = tab2[2+s]; //ni 2+s sur 6
tab1[7] = tab2[7+s]; //ni 7+s sur 2
tab1[5] = tab2[5+s]; //ni 5+s sur 7
tab1[4] = tab2[4+s]; //ni 4+s sur 5
tab1[8] = tab2[8+s]; //ni 8+s sur 4
tab1[9] = tab2[9+s]; //mais 9+s est aligne sur 8

cette suite a la propriete de faire dependre toute les ecritures sur des offset differents; d'abord 1, puis 2, puis 3, pus 4, puis 5, puis 6, puis 7, puis 8, puis 1 de nouveau, etc etc

c'est a dire que quel que soit s, a chaque boucle, une de tes affectations va dependre de la precedente, mais une seule sur les 8. cela repartit la dependance sur toute tes boucles, c'est a dire que chacune est imperceptiblement plus lente (1/8 de l'overhead seulement), mais aucune ne devrait etre plus lente que les autres.

[Charlemagne]

cette suite a la propriete de faire dependre toute les ecritures sur des offset differents; d'abord 1, puis 2, puis 3, pus 4, puis 5, puis 6, puis 7, puis 8, puis 1 de nouveau, etc etc

c'est a dire que quel que soit s, a chaque boucle, une de tes affectations va dependre de la precedente, mais une seule sur les 8. cela repartit la dependance sur toute tes boucles, c'est a dire que chacune est imperceptiblement plus lente (1/8 de l'overhead seulement), mais aucune ne devrait etre plus lente que les autres.

C'est peut-être aussi une question d'aliasing.
Le C/C++ autorise l'aliasing, alors que le Fortran ne l'autorise pas. C'est à ma connaissance la SEULE VRAIE raison des meilleures perfs du Fortran vis-à-vis du C/C++, car les compilos fortran peuvent optimiser un peu plus le code.

En tout cas, rien à voir avec le mono/bi/quadri-noyaux. Et je ne comprendrais pas qu'il y ait une différence sensible d'un processeur à l'autre.

[screetch]

bordel vous voulez un screenshot de la simulation sous code analyst ?

quand je dis que c'est un probleme de store-to-load dependency je sais quoi que je dis!!

[Charlemagne]

quand je dis que c'est un probleme de store-to-load dependency je sais quoi que je dis!!

"store-to-load dependency": ça m'a tout l'air de ressembler aux syndromes de l'aliasing.
Je te crois sur parole, pas la peine de t'énerver... Je ne fais qu'émettre des hypothèses...

[yan]

En tout cas, rien à voir avec le mono/bi/quadri-noyaux. Et je ne comprendrais pas qu'il y ait une différence sensible d'un processeur à l'autre.

Voici ce que j'obtiens avec mon code sur un p4 normal.
Y as pas le problème... C'est lent tous le temps

[screetch]

non, pas vraiment, ca arrve quand l'operation suivante depend de la completion de l'operation precedente

lorsque tu fais :

a = 1
a ++;

tu peux commencer dans le pipeline deux operations a = 1 puis immediatement lancer l'operation suivante sans attendre la fin. le probleme c'est que la deuxdieme operation relit la valeur de a (load) et doit attendre la fin de l'operation.

comme je l'ai expliqué plus haut, dans le cas que l'on a vu plus haut on avait pas un reel probleme de store to load mais simplement le processeur le croyait du a l'alignement des cibles et sources. les operations etaient independantes mais ont ete percues comme dependantes.


L'aliasing maintenant, c'est lorsqu'une operation peut affecter une variable a priori non liée car elles pointes en fait sur le meme emplacement; le compilateur suppose toujours que deux variables peuvent etre liées sauf si il peut demontrer qu'elles ne le sont pas (par exemple, si l'une d'entre elle est sur la pile locale et pas l'autre, si elles ne sont pas de meme type, etc)
dans le cas ou il ne peut pas le determiner, il devra recharger la valeur de la variable depuis son emplacement memoire pares une operation sur une autre variable; et il ne pourra pas reordonner les operations non plus.
c'est un phénomène tout a fait different; cela voudrait dire par exemple, que le code suivant ne peut pas etre optimisé :

Code :

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

1
2
3
4
5
			for (int i =1500;i<size-1500;i++)
			{
				//on fait une copie avec un décalage s
				tab1[i] = tab2[1500];
			}

car a force de taper dans tab1[] on pourrait changer des variables qui sont dans tab2, et il faut donc verifier que tab2 n'a pas changer.

voila le code assembleur genere par visual c++ :

Code :

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

1
2
3
		tab1[i] = tab2[1500];
00401400  mov         edi,dword ptr [esi+1770h] 
00401406  mov         dword ptr [edx+eax*4],edi

comme tu peux le voir, il relit toujours tab2[1500] depuis la memoire.

en aidant un peu le compilateur (en stockant dans une variable locale par exemple), voila le nouveau code genere :

Code :

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

00401401  mov         dword ptr [esi+eax*4],ecx

ecx etant constant.

[Charlemagne]

Voici ce que j'obtiens avec mon code sur un p4 normal.
Y as pas le problème... C'est lent tous le temps

Si j'ai bien compris ton programme fait des recopies plus ou moins compliquées de zones de mémoires.

Mes recettes d'optimisation:
- instructions SIMD
- pré-calculs des offsets de pointeurs
- développement des boucles. Exemple:

Code :

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

1
2
3
4
5
6
7
8
9
 
for (int i=0; i<n; i+=16)
{
  p=tab1+i;
  q=tab2+i;
  p[0]=q[0];
  p[1]=q[1];
...
}

explication: l'idée cruciale ici est d'utiliser des index à valeur constante, pour lesquelles le compilo peut d'emblée calculer l'offset et utiliser des instructions assembleur plus rapides.
- éviter les accès mémoires, il faut garder les valeurs dans des variables locales: Le compilos savent plutôt bien optimiser les registres (ça je confirme) alors que quand on fait plusieurs accès de la même variable par un pointeur, les compilos font à chaque fois un load.
- Optimisation du cache (de loin l'optimisation la plus délicate ,en tout cas pour moi!). Mais s'il s'agit de recopier des grandes zones de mémoire contiguës, alors y'a peut-être pas une grande marge de manœuvre...

Je confirme qu'aucun compilo testé (Visual, GCC et ICL) n'optimise automatiquement suivant ces techniques. Ça se comprend...