¿Prefetching Ejemplos?

La búsqueda binaria es un ejemplo simple que podría beneficiarse de la prefetching explícita. El patrón de acceso en una búsqueda binaria parece bastante aleatorio para el prefetcher de hardware, por lo que hay pocas posibilidades de que prediga con precisión qué buscar.

En este ejemplo, preestablezco las dos posibles ubicaciones 'intermedias' de la siguiente iteración de bucle en la iteración actual. Uno de los prefetches probablemente nunca se utilizará, pero el otro (a menos que este sea el final iteración).

 #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);
 }

Cuando compilo y corro este ejemplo con DO_PREFETCH habilitado, veo una reducción del 20% en el tiempo de ejecución:

 $ 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

Observe que estamos haciendo el doble de cargas de caché L1 en la versión prefetch. En realidad estamos haciendo mucho más trabajo, pero el patrón de acceso a la memoria es más amigable con la tubería. Esto también muestra la compensación. Si bien este bloque de código se ejecuta más rápido de forma aislada, hemos cargado una gran cantidad de basura en las cachés y esto puede poner más presión en otras partes de aplicación.

Aprendí mucho de las excelentes respuestas proporcionadas por @JamesScriven y @Mystical. Sin embargo, sus ejemplos solo dan un impulso modesto - el objetivo de esta respuesta es presentar un ejemplo (debo confesar algo artificial), donde la prefetching tiene un impacto mayor (sobre el factor 4 en mi máquina).

Hay tres cuellos de botella posibles para las arquitecturas modernas: velocidad de CPU, ancho de banda de memoria y latencia de memoria. Prefetching se trata de reducir la latencia de la memoria-accesos.

En un escenario perfecto, donde la latencia corresponde a X pasos de cálculo, tendríamos un oracle, que nos diría a qué memoria accederíamos en X pasos de cálculo, se iniciaría la prefetching de estos datos y llegaría justo a tiempo X pasos de cálculo más tarde.

Para muchos algoritmos estamos (casi) en este mundo perfecto. Para un simple bucle for, es fácil predecir qué datos se necesitarán X pasos más adelante. Ejecución fuera de orden y otros los trucos de hardware están haciendo un muy buen trabajo aquí, ocultando la latencia casi por completo.

Esa es la razón, por la que hay una mejora tan modesta para el ejemplo de @Mystical: El prefetcher ya es bastante bueno - simplemente no hay mucho espacio para mejorar. La tarea también está limitada a la memoria, por lo que probablemente no queda mucho ancho de banda, podría estar convirtiéndose en el factor limitante. Pude ver, en el mejor de los casos, alrededor de un 8% de mejora en mi máquina.

La visión crucial de @JamesScriven ejemplo: ni nosotros ni la CPU conocemos la siguiente dirección de acceso antes de que los datos actuales se obtengan de la memoria-esta dependencia es bastante importante, de lo contrario la ejecución fuera de orden llevaría a una mirada hacia adelante y el hardware sería capaz de prefetch los datos. Sin embargo, debido a que podemos especular sobre un solo paso, no hay mucho potencial. No pude obtener más del 40% en mi máquina.

Así que vamos a amañar la competencia y preparar los datos de tal manera que sepamos a qué dirección se accede en X pasos, pero hacen imposible que el hardware la encuentre debido a dependencias en datos aún no accedidos (ver todo el programa al final de la respuesta):

//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
    }
}

Algunas observaciones:

1. los datos se preparan de tal manera que el oráculo siempre tiene razón.
2. tal vez sorprendentemente, cuanto menos tarea vinculada a la CPU, mayor es la velocidad: somos capaces de ocultar la latencia casi por completo, por lo que la velocidad es CPU-time+original-latency-time/CPU-time.

Compilación y leads de ejecución:

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

A una aceleración entre 4 y 5.

Lista 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";
     }

 }

De la documentación:

      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 búsqueda previa de datos se puede optimizar al tamaño de la línea de caché, que para la mayoría de los procesadores modernos de 64 bits es de 64 bytes para, por ejemplo, cargar previamente un uint32_t[16] con una instrucción.

Por ejemplo, en ARMv8 descubrí a través de la experimentación que lanzaba el puntero de memoria a un vector de matriz uint32_t 4x4 (que tiene un tamaño de 64 bytes) redujo a la mitad las instrucciones requeridas como antes tuve que incrementar en 8 ya que solo estaba cargando la mitad de los datos, a pesar de que una línea de caché completa.

Obtener previamente un ejemplo de código original de 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]);

Después...

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

Por alguna razón int datatype para el índice/desplazamiento de direcciones dio un mejor rendimiento. Probado con GCC 8 en Cortex-a53. El uso de un vector equivalente de 64 bytes en otras arquitecturas podría dar la misma mejora de rendimiento si encuentra que no está obteniendo previamente todos los datos como en mi caso. En mi aplicación con un bucle de iteración de un millón, mejoró el rendimiento en un 5% sólo haciendo esto. Hay otras necesidades para la mejora.

La asignación de memoria "V" de 128 megabytes tuvo que ser alineada a 64 bytes.

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

Además, tuve que usar operadores C en lugar de Intrínsecos de Neón, ya que requieren punteros de tipo de datos regulares (en mi caso fue uint32_t *) de lo contrario, el nuevo método prefetch incorporado tenía una regresión de rendimiento.

Mi ejemplo del mundo real se puede encontrar en https://github.com/rollmeister/veriumMiner/blob/main/algo/scrypt.c en scrypt_core() y su función interna que son fáciles de leer. El trabajo duro es hecho por GCC8. La mejora general del rendimiento fue del 25%.