プリフェッチの例？

Question

GCCの中で__builtin_prefetch（あるいは単にasm命令のprefetcht0）を使用して、パフォーマンスを大幅に向上させた例へのリンクや例を挙げることはできますか？具体的には、次の基準を満たす例をお伝えしたいと思います。

1. これは、単純で小さな、自立型の例です。
2. __builtin_prefetch命令を削除すると、パフォーマンスが低下します。
3. __builtin_prefetch命令を対応するメモリアクセスに置き換えると、パフォーマンスが低下します。

つまり、__builtin_prefetchという最適化を実行している最短の例が必要です。 the documentationから

Answer 1

は、ここで私は大きなプロジェクトから引き出されたコードの実際の作品です。 （申し訳ありませんが、私が見つけることができる最短のものです。プリフェッチからの顕著な高速化がありました。） このコードは非常に大きなデータ転置を行います。

この例では、SSEプリフェッチ命令を使用します。これは、GCCが発行する命令と同じでもかまいません。

この例を実行するには、x64でこれをコンパイルし、4GBを超えるメモリが必要です。小さなデータサイズで実行することはできますが、時間がかかり過ぎます。私は無効になっENABLE_PREFETCHでそれを実行すると

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

、これが出力されます：

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

そうそこだ

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

私はENABLE_PREFETCHでそれを実行し、これが出力され、有効になってプリフェッチから13％のスピードアップ。

EDIT：

ここではいくつかのより多くの結果です：

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

：

 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

バイナリ検索は、明示的なプリフェッチから利益を得ることができる簡単な例です。バイナリ検索のアクセスパターンは、ハードウェアのプリフェッチャにはほとんど無作為に見えるので、フェッチするものを正確に予測する機会はほとんどありません。

この例では、現在の反復で次のループ反復の2つの可能な中間位置をプリフェッチします。プリフェッチの1つはおそらく決して使用されませんが、もう1つは（これが最後の反復でない限り）使用されます。私たちは、プリフェッチ・バージョンで2倍のL1キャッシュの負荷を行っている

$ 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 

お知らせ：

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

私がコンパイルしDO_PREFETCHでこの例を実行する私は、ランタイムでの20％削減を参照してください、有効。私たちは実際にはもっと多くの作業をしていますが、メモリアクセスパターンはパイプラインにとってより使いやすいものです。これはまた、トレードオフを示す。このコードブロックは孤立して高速で実行されますが、キャッシュには多くの迷惑メールがロードされており、アプリケーションの他の部分に大きな負担をかける可能性があります。