gcc - etiqueta - meta title seo

¿Ejemplos de captura previa?

Question

¿Alguien puede dar un ejemplo o un enlace a un ejemplo que utiliza __builtin_prefetch en GCC (o simplemente la instrucción asm prefetcht0 en general) para obtener una ventaja de rendimiento sustancial? En particular, me gustaría que el ejemplo cumpla con los siguientes criterios:

1. Es un ejemplo simple, pequeño e independiente.
2. Al eliminar la instrucción __builtin_prefetch , se __builtin_prefetch rendimiento.
3. Reemplazar la instrucción __builtin_prefetch con el acceso de memoria correspondiente produce una degradación del rendimiento.

Es decir, quiero que el ejemplo más breve muestre __builtin_prefetch realizando una optimización que no podría gestionarse sin él.

Answer 1

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

Hay tres posibles cuellos de botella para las arquitecturas modernas: velocidad de CPU, ancho de banda de memoria y latencia de memoria. La captura previa se trata de reducir la latencia de los accesos a la memoria.

En un escenario perfecto, donde la latencia corresponde a los pasos de cálculo X, tendríamos un oráculo, que nos diría a qué memoria accederíamos en X pasos de cálculo, se lanzaría la captación previa de estos datos y llegaría solo a Cálculo del tiempo X: pasos más adelante.

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

Esa es la razón, por la cual hay una mejora tan modesta para el ejemplo de @Mystical: el captador previo ya es bastante bueno; simplemente no hay mucho margen de mejora. La tarea también está vinculada a la memoria, por lo que probablemente no quede mucho ancho de banda, podría convertirse en el factor limitante. Pude ver, en el mejor de los casos, una mejora del 8% en mi máquina.

La idea crucial del ejemplo de @JamesScriven: ni nosotros ni la CPU conocemos la siguiente dirección de acceso antes de que se obtengan los datos actuales de la memoria: esta dependencia es muy importante, de lo contrario, la ejecución desordenada daría lugar a una mirada anticipada. y el hardware sería capaz de captar previamente los datos. Sin embargo, como podemos especular sobre un solo paso, no hay mucho potencial. No pude obtener más del 40% en mi máquina.

Así que manipulemos la competencia y preparemos los datos de tal forma que sepamos a qué dirección se accede en X pasos, pero imposibilite que el hardware lo descubra debido a las dependencias de los datos aún no accedidos (consulte el programa completo 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 están preparados de tal manera que el oráculo siempre está en lo cierto.
2. Sorprendentemente, cuanto menor sea la tarea vinculada a la CPU, mayor será la aceleración: podemos ocultar la latencia casi por completo, por lo tanto, la aceleración es CPU-time+original-latency-time/CPU-time .

Compilando y ejecutando clientes potenciales:

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

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

 }

Answer 2

Aquí hay una pieza real de código que he sacado de un proyecto más grande. (Lo siento, es el más corto que puedo encontrar que tuvo una aceleración notable de la captación previa.) Este código realiza una transposición de datos muy grande.

Este ejemplo utiliza las instrucciones de captación previa de SSE, que pueden ser las mismas que emite GCC.

Para ejecutar este ejemplo, deberá compilar esto para x64 y tener más de 4 GB de memoria. Puede ejecutarlo con un tamaño de datos más pequeño, pero será demasiado rápido para el tiempo.

#include <iostream>
using std::cout;
using std::endl;

#include <emmintrin.h>
#include <malloc.h>
#include <time.h>
#include <string.h>

#define ENABLE_PREFETCH


#define f_vector    __m128d
#define i_ptr       size_t
inline void swap_block(f_vector *A,f_vector *B,i_ptr L){
    //  To be super-optimized later.

    f_vector *stop = A + L;

    do{
        f_vector tmpA = *A;
        f_vector tmpB = *B;
        *A++ = tmpB;
        *B++ = tmpA;
    }while (A < stop);
}
void transpose_even(f_vector *T,i_ptr block,i_ptr x){
    //  Transposes T.
    //  T contains x columns and x rows.
    //  Each unit is of size (block * sizeof(f_vector)) bytes.

    //Conditions:
    //  - 0 < block
    //  - 1 < x

    i_ptr row_size = block * x;
    i_ptr iter_size = row_size + block;

    //  End of entire matrix.
    f_vector *stop_T = T + row_size * x;
    f_vector *end = stop_T - row_size;

    //  Iterate each row.
    f_vector *y_iter = T;
    do{
        //  Iterate each column.
        f_vector *ptr_x = y_iter + block;
        f_vector *ptr_y = y_iter + row_size;

        do{

#ifdef ENABLE_PREFETCH
            _mm_prefetch((char*)(ptr_y + row_size),_MM_HINT_T0);
#endif

            swap_block(ptr_x,ptr_y,block);

            ptr_x += block;
            ptr_y += row_size;
        }while (ptr_y < stop_T);

        y_iter += iter_size;
    }while (y_iter < end);
}
int main(){

    i_ptr dimension = 4096;
    i_ptr block = 16;

    i_ptr words = block * dimension * dimension;
    i_ptr bytes = words * sizeof(f_vector);

    cout << "bytes = " << bytes << endl;
//    system("pause");

    f_vector *T = (f_vector*)_mm_malloc(bytes,16);
    if (T == NULL){
        cout << "Memory Allocation Failure" << endl;
        system("pause");
        exit(1);
    }
    memset(T,0,bytes);

    //  Perform in-place data transpose
    cout << "Starting Data Transpose...   ";
    clock_t start = clock();
    transpose_even(T,block,dimension);
    clock_t end = clock();

    cout << "Done" << endl;
    cout << "Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl;

    _mm_free(T);
    system("pause");
}

Cuando lo ejecuto con ENABLE_PREFETCH habilitado, este es el resultado:

bytes = 4294967296
Starting Data Transpose...   Done
Time: 0.725 seconds
Press any key to continue . . .

Cuando lo ejecuto con ENABLE_PREFETCH desactivado, este es el resultado:

bytes = 4294967296
Starting Data Transpose...   Done
Time: 0.822 seconds
Press any key to continue . . .

Así que hay un 13% de aceleración de la captación previa.

EDITAR:

Aquí hay algunos más resultados:

Operating System: Windows 7 Professional/Ultimate
Compiler: Visual Studio 2010 SP1
Compile Mode: x64 Release

Intel Core i7 860 @ 2.8 GHz, 8 GB DDR3 @ 1333 MHz
Prefetch   : 0.868
No Prefetch: 0.960

Intel Core i7 920 @ 3.5 GHz, 12 GB DDR3 @ 1333 MHz
Prefetch   : 0.725
No Prefetch: 0.822

Intel Core i7 2600K @ 4.6 GHz, 16 GB DDR3 @ 1333 MHz
Prefetch   : 0.718
No Prefetch: 0.796

2 x Intel Xeon X5482 @ 3.2 GHz, 64 GB DDR2 @ 800 MHz
Prefetch   : 2.273
No Prefetch: 2.666

Answer 3

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);
          /* ... */
        }

Answer 4

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

En este ejemplo, prefiero las dos ubicaciones "intermedias" posibles de la siguiente iteración de bucle en la iteración actual. Es probable que nunca se use uno de los prefetches, pero el otro lo hará (a menos que sea la iteración final).

 #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 ejecuto este ejemplo con DO_PREFETCH activado, 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

Tenga en cuenta que estamos haciendo el doble de cargas de caché L1 en la versión de búsqueda previa. De hecho, estamos trabajando mucho más, 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 memorias caché y esto puede ejercer más presión sobre otras partes de la aplicación.