Esempi di prefetching?

Question

Qualcuno può dare un esempio o un collegamento a un esempio che utilizza __builtin_prefetch in GCC (o solo l'istruzione asm prefetcht0 in generale) per ottenere un sostanziale vantaggio prestazionale? In particolare, mi piacerebbe che l'esempio soddisfi i seguenti criteri:

1. È un esempio semplice, piccolo e autonomo.
2. Rimozione dei risultati dell'istruzione __builtin_prefetch in termini di riduzione delle prestazioni.
3. Sostituendo l'istruzione __builtin_prefetch con l'accesso alla memoria corrispondente si ottiene un peggioramento delle prestazioni.

Cioè, voglio l'esempio più breve che mostri __builtin_prefetch eseguendo un'ottimizzazione che non può essere gestita senza di essa.

Answer 1

Ecco un vero pezzo di codice che ho tirato fuori di un progetto più ampio. (Siamo spiacenti, è il più breve che riesco a trovare con un notevole aumento della velocità di precaricamento.) Questo codice esegue una trasposizione dei dati molto ampia.

Questo esempio utilizza le istruzioni di precaricamento SSE, che possono essere uguali a quelle emesse da GCC.

Per eseguire questo esempio, è necessario compilarlo per x64 e avere più di 4 GB di memoria. È possibile eseguirlo con un datasize più piccolo, ma sarà troppo veloce per volta.

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

Quando eseguo con ENABLE_PREFETCH abilitato, questo è l'output:

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

quando l'eseguo con ENABLE_PREFETCH disattivato, questo è l'output:

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

Quindi c'è una 13% di accelerazione dal prefetching.

EDIT:

Ecco altri risultati:

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 2

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

Answer 3

La ricerca binaria è un semplice esempio che potrebbero beneficiare di prefetching esplicita. Il modello di accesso in una ricerca binaria sembra piuttosto casuale al prefetcher hardware, quindi ci sono poche possibilità che predichi con precisione cosa recuperare.

In questo esempio, pre-prelevo le due possibili posizioni "intermedie" dell'iterazione del ciclo successivo nell'iterazione corrente. Uno dei prefetcher probabilmente non verrà mai usato, ma l'altro lo farà (a meno che questa non sia l'iterazione finale).

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

Quando ho compilare ed eseguire questo esempio con DO_PREFETCH abilitato, vedo una riduzione del 20% in fase di esecuzione:

$ 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 

Si noti che stiamo facendo il doppio dei carichi di cache L1 nella versione prefetch.In realtà stiamo facendo molto più lavoro, ma il pattern di accesso alla memoria è più amichevole per la pipeline. Questo mostra anche il compromesso. Mentre questo blocco di codice viene eseguito più rapidamente, abbiamo caricato un sacco di cianfrusaglie nelle cache e questo potrebbe mettere più pressione su altre parti dell'applicazione.