Ví dụ tìm nạp trước?

Question

Bất cứ ai có thể đưa ra một ví dụ hoặc một liên kết đến một ví dụ sử dụng __builtin_prefetch trong GCC (hoặc chỉ là hướng dẫn asm prefetcht0 nói chung) để đạt được một lợi thế hiệu suất đáng kể? Cụ thể, tôi muốn ví dụ đáp ứng các tiêu chí sau:

1. Đây là ví dụ đơn giản, nhỏ gọn.
2. Xóa kết quả chỉ dẫn __builtin_prefetch trong giảm hiệu suất.
3. Thay thế hướng dẫn __builtin_prefetch với kết quả truy cập bộ nhớ tương ứng trong quá trình giảm hiệu suất.

Tức là, tôi muốn ví dụ ngắn nhất hiển thị __builtin_prefetch thực hiện tối ưu hóa không thể quản lý mà không có nó.

Answer 1

Dưới đây là một mảnh thực tế của mã mà tôi đã rút khỏi một dự án lớn hơn. (Xin lỗi, đó là đoạn ngắn nhất tôi có thể thấy có tốc độ đáng chú ý khi tìm nạp trước.) Mã này thực hiện chuyển dữ liệu rất lớn.

Ví dụ này sử dụng hướng dẫn tìm nạp trước SSE, có thể giống như hướng dẫn mà GCC phát ra.

Để chạy ví dụ này, bạn sẽ cần phải biên dịch mã này cho x64 và có nhiều hơn 4GB bộ nhớ. Bạn có thể chạy nó với một dữ liệu nhỏ hơn, nhưng nó sẽ là quá nhanh để thời gian.

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

Khi tôi chạy nó với ENABLE_PREFETCH bật, đây là kết quả:

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

Khi tôi chạy nó với ENABLE_PREFETCH tàn tật, đây là kết quả:

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

Vì vậy, có một Tăng tốc 13% từ tìm nạp trước.

EDIT:

Dưới đây là một số kết quả hơn:

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

Từ 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

tìm kiếm nhị phân là một ví dụ đơn giản mà có thể được hưởng lợi từ tìm nạp trước rõ ràng. Mẫu truy cập trong tìm kiếm nhị phân trông khá ngẫu nhiên đối với trình tìm nạp trước phần cứng, do đó, rất ít khả năng nó sẽ dự đoán chính xác những gì cần tìm nạp.

Trong ví dụ này, tôi tìm nạp trước hai vị trí 'trung bình' có thể có của vòng lặp tiếp theo trong phép lặp hiện tại. Một trong những tìm nạp trước có thể sẽ không bao giờ được sử dụng, nhưng cái kia sẽ (trừ khi đây là lần lặp cuối cùng).

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

Khi tôi biên dịch và chạy ví dụ này với DO_PREFETCH kích hoạt, tôi thấy một sự giảm 20% trong thời gian chạy:

$ 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 

Chú ý rằng chúng ta đang làm gấp đôi so với nhiều tải bộ nhớ cache L1 trong phiên bản prefetch.Chúng tôi đang thực sự làm nhiều công việc hơn nhưng mẫu truy cập bộ nhớ thân thiện hơn với đường dẫn. Điều này cũng cho thấy sự cân bằng. Trong khi khối mã này chạy nhanh hơn trong sự cô lập, chúng tôi đã tải rất nhiều rác vào bộ đệm và điều này có thể gây áp lực nhiều hơn cho các phần khác của ứng dụng.