Prefetching Exemples?

La recherche binaire est un exemple simple qui pourrait bénéficier d'une recherche préalable explicite. Le modèle d'accès dans une recherche binaire semble assez aléatoire pour le prefetcher matériel, donc il y a peu de chance qu'il prédit avec précision ce qu'il faut chercher.

Dans cet exemple, Je prélève les deux emplacements "intermédiaires" possibles de l'itération de boucle suivante dans l'itération en cours. L'un des préréglages ne sera probablement jamais utilisé, mais l'autre le sera (à moins que ce ne soit le final itération).

 #include <time.h>
 #include <stdio.h>
 #include <stdlib.h>

 int binarySearch(int *array, int number_of_elements, int key) {
         int low = 0, high = number_of_elements-1, mid;
         while(low <= high) {
                 mid = (low + high)/2;
            #ifdef DO_PREFETCH
            // low path
            __builtin_prefetch (&array[(mid + 1 + high)/2], 0, 1);
            // high path
            __builtin_prefetch (&array[(low + mid - 1)/2], 0, 1);
            #endif

                 if(array[mid] < key)
                         low = mid + 1; 
                 else if(array[mid] == key)
                         return mid;
                 else if(array[mid] > key)
                         high = mid-1;
         }
         return -1;
 }
 int main() {
     int SIZE = 1024*1024*512;
     int *array =  malloc(SIZE*sizeof(int));
     for (int i=0;i<SIZE;i++){
       array[i] = i;
     }
     int NUM_LOOKUPS = 1024*1024*8;
     srand(time(NULL));
     int *lookups = malloc(NUM_LOOKUPS * sizeof(int));
     for (int i=0;i<NUM_LOOKUPS;i++){
       lookups[i] = rand() % SIZE;
     }
     for (int i=0;i<NUM_LOOKUPS;i++){
       int result = binarySearch(array, SIZE, lookups[i]);
     }
     free(array);
     free(lookups);
 }

Lorsque je compile et exécute cet exemple avec DO_PREFETCH activé, je vois une réduction de 20% du temps d'exécution:

 $ gcc c-binarysearch.c -DDO_PREFETCH -o with-prefetch -std=c11 -O3
 $ gcc c-binarysearch.c -o no-prefetch -std=c11 -O3

 $ perf stat -e L1-dcache-load-misses,L1-dcache-loads ./with-prefetch 

  Performance counter stats for './with-prefetch':

    356,675,702      L1-dcache-load-misses     #   41.39% of all L1-dcache hits  
   861,807,382      L1-dcache-loads                                             

   8.787467487 seconds time elapsed

 $ perf stat -e L1-dcache-load-misses,L1-dcache-loads ./no-prefetch 

 Performance counter stats for './no-prefetch':

   382,423,177      L1-dcache-load-misses     #   97.36% of all L1-dcache hits  
   392,799,791      L1-dcache-loads                                             

  11.376439030 seconds time elapsed

Notez que nous faisons deux fois plus de charges de cache L1 dans la version prefetch. Nous faisons en fait beaucoup plus de travail, mais le modèle d'accès à la mémoire est plus convivial pour le pipeline. Cela montre également le compromis. Bien que ce bloc de code s'exécute plus rapidement isolément, nous avons chargé beaucoup d'ordure dans les caches et cela peut mettre plus de pression sur d'autres parties de application.

J'ai beaucoup appris des excellentes réponses fournies par @ JamesScriven et @ Mystical. Cependant, leurs exemples ne donnent qu'un coup de pouce modeste - l'objectif de cette réponse est de présenter un exemple (je dois avouer un peu artificiel), où le prefetching a un impact plus important (environ le facteur 4 sur ma machine).

Il existe trois goulots d'étranglement possibles pour les architectures modernes: la vitesse du processeur, la largeur de bande mémoire et la latence de la mémoire. Prefetching est tout au sujet de réduire la latence du mémoire-les accès.

Dans un scénario parfait, où la latence correspond à X étapes de calcul, nous aurions un oracle, qui nous indiquerait à quelle mémoire nous accéderions dans X étapes de calcul, le préchargement de ces données serait lancé et il arriverait juste à temps X étapes de calcul plus tard.

Pour beaucoup d'algorithmes, nous sommes (presque) dans ce monde parfait. Pour une boucle for simple, il est facile de prédire quelles données seront nécessaires X étapes plus tard. Exécution hors ordre et autres les astuces matérielles font un très bon travail ici, cachant presque complètement la latence.

C'est la raison pour laquelle il y a une amélioration si modeste pour l'exemple de @Mystical: le prefetcher est déjà assez bon - il n'y a tout simplement pas beaucoup de place pour l'amélioration. La tâche est également liée à la mémoire, donc il ne reste probablement pas beaucoup de largeur de bande-cela pourrait devenir le facteur limitant. Je pouvais voir au mieux environ 8% d'amélioration sur ma machine.

L'aperçu crucial du @ JamesScriven exemple: ni nous ni le CPU ne connaissons l'adresse d'accès suivante avant que les données actuelles ne soient récupérées de la mémoire-cette dépendance est assez importante, sinon l'exécution hors ordre conduirait à un regard vers l'avenir et le matériel serait capable de pré-récupérer les données. Cependant, parce que nous pouvons spéculer sur une seule étape, il n'y a pas beaucoup de potentiel. Je n'ai pas pu obtenir plus de 40% sur ma machine.

Donc, nous allons truquer la concurrence et de préparer les données de telle sorte que nous savons quelle adresse est accessible en X étapes, mais il est impossible pour le matériel de la trouver en raison des dépendances sur les données non encore accédées (voir l'ensemble du programme à la fin de la réponse):

//making random accesses to memory:
unsigned int next(unsigned int current){
   return (current*10001+328)%SIZE;
}

//the actual work is happening here
void operator()(){

    //set up the oracle - let see it in the future oracle_offset steps
    unsigned int prefetch_index=0;
    for(int i=0;i<oracle_offset;i++)
        prefetch_index=next(prefetch_index);

    unsigned int index=0;
    for(int i=0;i<STEP_CNT;i++){
        //use oracle and prefetch memory block used in a future iteration
        if(prefetch){
            __builtin_prefetch(mem.data()+prefetch_index,0,1);    
        }

        //actual work, the less the better
        result+=mem[index];

        //prepare next iteration
        prefetch_index=next(prefetch_index);  #update oracle
        index=next(mem[index]);               #dependency on `mem[index]` is VERY important to prevent hardware from predicting future
    }
}

Quelques remarques:

1. les données sont préparées de telle sorte que l'oracle ait toujours raison.
2. peut-être étonnamment, moins la tâche est liée au processeur, plus l'accélération est grande: nous sommes capables de masquer la latence presque complètement, donc l'accélération est CPU-time+original-latency-time/CPU-time.

Compilation et exécution des pistes:

>>> g++ -std=c++11 prefetch_demo.cpp -O3 -o prefetch_demo
>>> ./prefetch_demo
#preloops   time no prefetch    time prefetch   factor
...
7   1.0711102260000001  0.230566831 4.6455521002498408
8   1.0511602149999999  0.22651144600000001 4.6406494398521474
9   1.049024333 0.22841439299999999 4.5926367389641687
....

À une vitesse comprise entre 4 et 5.

Liste de prefetch_demp.cpp:

//prefetch_demo.cpp

#include <vector>
#include <iostream>
#include <iomanip>
#include <chrono>

const int SIZE=1024*1024*1;
const int STEP_CNT=1024*1024*10;

unsigned int next(unsigned int current){
   return (current*10001+328)%SIZE;
}


template<bool prefetch>
struct Worker{
   std::vector<int> mem;

   double result;
   int oracle_offset;

   void operator()(){
        unsigned int prefetch_index=0;
        for(int i=0;i<oracle_offset;i++)
            prefetch_index=next(prefetch_index);

        unsigned int index=0;
        for(int i=0;i<STEP_CNT;i++){
            //prefetch memory block used in a future iteration
            if(prefetch){
                __builtin_prefetch(mem.data()+prefetch_index,0,1);    
            }
            //actual work:
            result+=mem[index];

            //prepare next iteration
            prefetch_index=next(prefetch_index);
            index=next(mem[index]);
        }
   }

   Worker(std::vector<int> &mem_):
       mem(mem_), result(0.0), oracle_offset(0)
   {}
};

template <typename Worker>
    double timeit(Worker &worker){
    auto begin = std::chrono::high_resolution_clock::now();
    worker();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count()/1e9;
}


 int main() {
     //set up the data in special way!
     std::vector<int> keys(SIZE);
     for (int i=0;i<SIZE;i++){
       keys[i] = i;
     }

     Worker<false> without_prefetch(keys);
     Worker<true> with_prefetch(keys);

     std::cout<<"#preloops\ttime no prefetch\ttime prefetch\tfactor\n";
     std::cout<<std::setprecision(17);

     for(int i=0;i<20;i++){
         //let oracle see i steps in the future:
         without_prefetch.oracle_offset=i;
         with_prefetch.oracle_offset=i;

         //calculate:
         double time_with_prefetch=timeit(with_prefetch);
         double time_no_prefetch=timeit(without_prefetch);

         std::cout<<i<<"\t"
                  <<time_no_prefetch<<"\t"
                  <<time_with_prefetch<<"\t"
                  <<(time_no_prefetch/time_with_prefetch)<<"\n";
     }

 }

À Partir de la documentation:

      for (i = 0; i < n; i++)
        {
          a[i] = a[i] + b[i];
          __builtin_prefetch (&a[i+j], 1, 1);
          __builtin_prefetch (&b[i+j], 0, 1);
          /* ... */
        }

La pré-récupération des données peut être optimisée à la taille de la ligne de Cache, qui pour la plupart des processeurs 64 bits modernes est de 64 octets pour par exemple précharger un uint32_t[16] avec une instruction.

Par exemple sur ArmV8, j'ai découvert par expérimentation que le pointeur de mémoire vers un vecteur matriciel uint32_t 4x4 (de taille 64 octets) réduisait de moitié les instructions requises comme auparavant je devais incrémenter de 8 car il ne chargeait que la moitié des données, même si ma compréhension était qu'il récupère une ligne de cache complète.

Pré-extraction d'un exemple de code d'origine uint32_t[32]...

int addrindex = &B[0];
    __builtin_prefetch(&V[addrindex]);
    __builtin_prefetch(&V[addrindex + 8]);
    __builtin_prefetch(&V[addrindex + 16]);
    __builtin_prefetch(&V[addrindex + 24]);

Après...

int addrindex = &B[0];
__builtin_prefetch((uint32x4x4_t *) &V[addrindex]);
__builtin_prefetch((uint32x4x4_t *) &V[addrindex + 16]);

Pour une raison quelconque int datatype pour l'index d'adresse / offset a donné de meilleures performances. Testé avec GCC 8 sur Cortex-a53. L'utilisation d'un vecteur équivalent de 64 octets sur d'autres architectures pourrait donner la même amélioration des performances si vous trouvez qu'il ne pré-récupère pas toutes les données comme dans mon cas. Dans mon application avec une boucle d'un million d'itérations, il a amélioré les performances de 5% seulement en faisant cela. Il y avait d'autres exigences pour l'amélioration.

L'allocation de mémoire "V" de 128 mégaoctets devait être alignée sur 64 octets.

uint32_t *V __attribute__((__aligned__(64))) = (uint32_t *)(((uintptr_t)(__builtin_assume_aligned((unsigned char*)aligned_alloc(64,size), 64)) + 63) & ~ (uintptr_t)(63));

En outre, j'ai dû utiliser des opérateurs C au lieu de Neon Intrinsics, car ils nécessitent des pointeurs de type de données réguliers (dans mon cas c'était uint32_t *) sinon la nouvelle méthode intégrée de prefetch avait une régression de performance.

Mon exemple du monde réel peut être trouvé à https://github.com/rollmeister/veriumMiner/blob/main/algo/scrypt.c dans le scrypt_core () et sa fonction interne qui sont tous faciles à lire. Le travail acharné est fait par GCC8. L'amélioration globale du rendement a été de 25%.