C++ : Accélération mystérieusement énorme en gardant un opérande dans un registre

Question

J'ai essayé de me faire une idée de l'impact d'avoir un tableau dans le cache L1 par rapport à la mémoire en chronométrant une routine qui met à l'échelle et additionne les éléments d'un tableau en utilisant le code suivant (je suis conscient que je devrais simplement mettre à l'échelle le résultat par 'a' à la fin ; le but est de faire à la fois une multiplication et une addition dans la boucle - jusqu'à présent, le compilateur n'a pas compris comment factoriser 'a') :

double sum(double a,double* X,int size)
{
    double total = 0.0;
    for(int i = 0;  i < size; ++i)
    {
        total += a*X[i];
    }
    return total;
}

#define KB 1024
int main()
{
    //Approximately half the L1 cache size of my machine
    int operand_size = (32*KB)/(sizeof(double)*2);
    printf("Operand size: %d\n", operand_size);
    double* X = new double[operand_size];
    fill(X,operand_size);

    double seconds = timer();
    double result;
    int n_iterations = 100000;
    for(int i = 0; i < n_iterations; ++i)
    {
        result = sum(3.5,X,operand_size);
        //result += rand();  
    }
    seconds = timer() - seconds; 

    double mflops = 2e-6*double(n_iterations*operand_size)/seconds;
    printf("Vector size %d: mflops=%.1f, result=%.1f\n",operand_size,mflops,result);
    return 0;
}

Notez que les routines timer() et fill() ne sont pas incluses pour des raisons de brièveté ; leur source complète peut être trouvée ici si vous voulez exécuter le code :

http://codepad.org/agPWItZS

Maintenant, c'est là que ça devient intéressant. Voici la sortie :

Operand size: 2048
Vector size 2048: mflops=588.8, result=-67.8

Il s'agit d'une performance totalement hors cache, malgré le fait que tous les éléments de X devraient être conservés en cache entre les itérations de la boucle. En regardant le code d'assemblage généré par :

g++ -O3 -S -fno-asynchronous-unwind-tables register_opt_example.cpp

Je remarque une bizarrerie dans la boucle de la fonction somme :

L55:
    movsd   (%r12,%rax,8), %xmm0
    mulsd   %xmm1, %xmm0
    addsd   -72(%rbp), %xmm0
    movsd   %xmm0, -72(%rbp)
    incq    %rax
    cmpq    $2048, %rax
    jne L55

Les instructions :

    addsd   -72(%rbp), %xmm0
    movsd   %xmm0, -72(%rbp)

indiquent qu'il stocke la valeur de "total" dans sum() sur la pile, et la lit et l'écrit à chaque itération de la boucle. J'ai modifié l'assemblage pour que cet opérande soit conservé dans un registre :

...
addsd   %xmm0, %xmm3
...

Ce petit changement crée un énorme une augmentation des performances :

Operand size: 2048
Vector size 2048: mflops=1958.9, result=-67.8

tl;dr Ma question est la suivante : pourquoi le remplacement d'un accès à un emplacement mémoire unique par un registre accélère-t-il autant le code, étant donné que cet emplacement unique devrait être stocké dans le cache L1 ? Quels sont les facteurs architecturaux qui rendent cela possible ? Il semble très étrange que l'écriture répétée d'un emplacement de pile détruise complètement l'efficacité d'un cache.

Annexe

Ma version de gcc est :

Target: i686-apple-darwin10
Configured with: /var/tmp/gcc/gcc-5646.1~2/src/configure --disable-checking --enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin10 --with-gxx-include-dir=/include/c++/4.2.1 --program-prefix=i686-apple-darwin10- --host=x86_64-apple-darwin10 --target=i686-apple-darwin10
Thread model: posix
gcc version 4.2.1 (Apple Inc. build 5646) (dot 1)

Mon processeur est :

Intel Xeon X5650

Answer 1

Il s'agit probablement de la combinaison d'une chaîne de dépendance plus longue et d'une mauvaise prédiction de la charge*.

---

Chaîne de dépendance plus longue :

Tout d'abord, nous identifions les chemins de dépendance critiques. Ensuite, nous examinons les latences des instructions fournies par : http://www.agner.org/optimize/instruction_tables.pdf (page 117)

Dans la version non optimisée, le chemin de dépendance critique est le suivant :

• addsd -72(%rbp), %xmm0
• movsd %xmm0, -72(%rbp)

En interne, il se décompose probablement en :

• charge (2 cycles)
• ajouted (3 cycles)
• magasin (3 cycles)

Si on regarde la version optimisée, c'est juste :

• ajouted (3 cycles)

Vous avez donc 8 cycles contre 3 cycles. Presque un facteur de 3.

Je ne suis pas sûr de la sensibilité de la gamme de processeurs Nehalem aux dépendances magasin-charge et de la façon dont elle s'en sort. redirection . Mais il est raisonnable de croire que ce n'est pas zéro.

---

Mauvaise prédiction de la charge :

Les processeurs modernes utilisent la prédiction de bien plus de façons que vous ne pouvez l'imaginer. La plus célèbre d'entre elles est probablement Prévision de la branche . L'une des moins connues est la prédiction de charge.

Lorsqu'un processeur voit une charge, il la charge immédiatement avant que toutes les écritures en attente ne se terminent. Il suppose que ces écritures n'entreront pas en conflit avec les valeurs chargées.

Si une écriture antérieure entre en conflit avec un chargement, le chargement doit être réexécuté et le calcul ramené au point du chargement. (de la même manière que les erreurs de prédiction de branche).

En quoi cela est pertinent ici :

Il va sans dire que les processeurs modernes seront capables d'exécuter plusieurs itérations de cette boucle simultanément. Le processeur tentera donc d'effectuer la charge ( addsd -72(%rbp), %xmm0) avant de terminer le magasin ( movsd %xmm0, -72(%rbp) ) de l'itération précédente.

Le résultat ? Le magasin précédent est en conflit avec la charge - donc une mauvaise prédiction et un retour en arrière.

_{*Notez que je ne suis pas sûr du nom "Load Prediction". Je l'ai seulement lu dans les documents d'Intel et ils n'ont pas semblé lui donner un nom.}

Answer 2

Je suppose que le problème ne se situe pas au niveau de l'accès au cache/mémoire mais au niveau du processeur (exécution de votre code). Il y a plusieurs goulots d'étranglement visibles ici.

Les performances indiquées ici sont basées sur les boîtiers que j'ai utilisés (soit sandybridge, soit westmere).

La performance de pointe pour les mathématiques scalaires est de 2,7Ghz x2 FLOPS/Clock x2 puisque le processeur peut faire une addition et une multiplication simultanément. L'efficacité théorique du code est de 0,6/(2,7*2) = 11%.

Bande passante nécessaire : 2 doubles par (+) et (x) -> 4 octets/Flop 4 octets * 5.4GFLOPS = 21.6GB/s

Si vous savez qu'il a été lu récemment, il est probable qu'il se trouve dans L1 (89GB/s), L2 (42GB/s) ou L3 (24GB/s), ce qui nous permet d'exclure la présence d'un cache B/W.

Le susbsystem de mémoire est de 18.9 GB/s, donc même en mémoire principale, la performance maximale devrait approcher 18.9/21.6GB/s = 87.5 %.

• On peut vouloir regrouper les demandes (via unrolling) le plus tôt possible.

Même avec une exécution spéculative, tot += a *X[i] les ajouts seront sérialisés parce que tot(n) doit être évalué avant que tot(n+1) puisse être lancé.

Première boucle de déroulage
déplacer i par 8 et faire

{//your func
    for( int i = 0; i < size; i += 8 ){
        tot += a * X[i];
        tot += a * X[i+1];
        ...
        tot += a * X[i+7];
    }
    return tot
}

Utiliser plusieurs accumulateurs
Cela brisera les dépendances et nous permettra d'éviter de bloquer le pipeline d'ajouts.

{//your func//
    int tot,tot2,tot3,tot4;
    tot = tot2 = tot3 = tot4 = 0
    for( int i = 0; i < size; i += 8 ) 
        tot  += a * X[i];
        tot2 += a * X[i+1];
        tot3 += a * X[i+2];
        tot4 += a * X[i+3];
        tot  += a * X[i+4];
        tot2 += a * X[i+5];
        tot3 += a * X[i+6];
        tot4 += a * X[i+7];
    }
    return tot + tot2 + tot3 + tot4;
}

MISE À JOUR Après avoir exécuté ceci sur une boîte SandyBridge à laquelle j'ai accès : (2.7GHZ SandyBridge avec -O2 -march=native -mtune=native

Code original :

Operand size: 2048  
Vector size 2048: mflops=2206.2, result=61.8  
2.206 / 5.4 = 40.8%

Code amélioré :

Operand size: 2048  
Vector size 2048: mflops=5313.7, result=61.8  
5.3137 / 5.4 = 98.4%

Answer 3

Je ne peux pas reproduire ce problème parce que mon compilateur (gcc 4.7.2) conserve les données suivantes total dans un registre.

Je soupçonne que la principale raison de la lenteur n'a rien à voir avec le cache L1, mais est plutôt due à la dépendance des données entre le magasin en

movsd   %xmm0, -72(%rbp)

et la charge de l'itération suivante :

addsd   -72(%rbp), %xmm0