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?

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