프리 페치 예제?

Question

누구나 GCC에서 __builtin_prefetch을 사용하는 예제 (또는 일반적으로 asm 명령어 prefetcht0)를 사용하여 상당한 성능 이점을 얻을 수있는 예제 또는 링크를 제공 할 수 있습니까? 특히이 예가 다음 기준을 충족하고 싶습니다.

1. 이 예제는 간단하고 작지만 독립적 인 예제입니다.
2. __builtin_prefetch 명령어를 제거하면 성능이 저하됩니다.
3. __builtin_prefetch 명령어를 해당 메모리 액세스로 바꾸면 성능이 저하됩니다.

즉, __builtin_prefetch이없는 최적화를 수행하는 가장 짧은 예제를 원합니다. the documentation에서

Answer 1

는 여기에 내가 큰 프로젝트에서 철수 한 코드의 실제 조각입니다. (미안하지만, 내가 발견 할 수있는 가장 빠른 것은 프리 페치에서 눈에 띄는 속도 향상이 있습니다.) 이 코드는 매우 큰 데이터 전치를 수행합니다.

이 예에서는 GCC에서 방출하는 것과 동일한 SSE 프리 페치 지침을 사용합니다.

이 예제를 실행하려면 x64의 경우이 파일을 컴파일해야하고 4GB 이상의 메모리가 있어야합니다. 더 작은 데이터 크기로 실행할 수는 있지만 너무 빠르다. 내가 ENABLE_PREFETCH 활성화와 실행

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

, 이것은 출력입니다 :

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

은 그래서 거기 :

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

내가 ENABLE_PREFETCH 장애인과 실행, 이것은 출력 프리 페칭에서 13 %의 속도 향상.

편집 :

가 여기 좀 더 결과 :

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

이진 검색이 명시 적으로 프리 페치 혜택을 누릴 수있는 간단한 예입니다. 이진 검색의 액세스 패턴은 하드웨어 프리 페처에 대해 거의 무작위로 표시되므로 페치 할 대상을 정확하게 예측할 가능성은 거의 없습니다.

이 예제에서 나는 현재 반복에서 다음 루프 반복의 두 개의 가능한 '중간'위치를 프리 페치합니다. 프리 페치 중 하나는 아마 사용되지 않지만 다른 페치는 사용됩니다 (이것이 최종 반복이 아니면). 우리는 프리 페치 버전에서 많은 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 % 감소를 참조하십시오.우리는 실제로 더 많은 작업을하고 있지만 메모리 액세스 패턴은 파이프 라인에보다 친숙합니다. 이것은 또한 절충을 보여줍니다. 이 코드 블록은 독립적으로 더 빠르게 실행되지만 캐시에 많은 양의 정크가로드되어 애플리케이션의 다른 부분에 더 많은 압력을 가할 수 있습니다.