उदाहरण प्रीफेचिंग?

Question

कोई भी उदाहरण के लिए एक उदाहरण या एक लिंक दे सकता है जो पर्याप्त प्रदर्शन लाभ प्राप्त करने के लिए जीसीसी में __builtin_prefetch (या सामान्य रूप से एएसएम निर्देश prefetcht0) का उपयोग करता है? विशेष रूप से, मुझे निम्नलिखित मानदंडों को पूरा करने के लिए उदाहरण चाहिए:

1. यह एक सरल, छोटा, आत्मनिर्भर उदाहरण है।
2. प्रदर्शन गिरावट में __builtin_prefetch निर्देश परिणामों को हटा रहा है।
3. प्रदर्शन गिरावट में संबंधित स्मृति पहुंच परिणामों के साथ __builtin_prefetch निर्देश को प्रतिस्थापित करना।

यही है, मैं सबसे कम उदाहरण चाहता हूं कि __builtin_prefetch एक अनुकूलन निष्पादित कर रहा है जिसे इसके बिना प्रबंधित नहीं किया जा सका।

Answer 1

यहाँ कोड का एक वास्तविक टुकड़ा है कि मैं एक बड़ी परियोजना के बाहर निकाला गया है। (क्षमा करें, यह सबसे छोटा है जिसे मैं पा सकता हूं जिसमें प्रीफेचिंग से एक उल्लेखनीय गति थी।) यह कोड एक बहुत बड़ा डेटा ट्रांसफर करता है।

यह उदाहरण एसएसई प्रीफेच निर्देशों का उपयोग करता है, जो कि जीसीसी उत्सर्जित करने जैसा ही हो सकता है।

इस उदाहरण को चलाने के लिए, आपको इसे x64 के लिए संकलित करने और 4GB से अधिक स्मृति होने की आवश्यकता होगी। आप इसे छोटे डेटासाइज के साथ चला सकते हैं, लेकिन यह समय के लिए बहुत तेज़ होगा।

#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 सक्षम चलाने के लिए, यह उत्पादन होता है:

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 विकलांग के साथ इसे चलाने के लिए, यह उत्पादन होता है Prefetching से 13% speedup।

संपादित करें:

यहाँ कुछ और परिणाम:

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

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

द्विआधारी खोज एक सरल उदाहरण है कि स्पष्ट प्रीफेचिंग से फायदा हो सकता है है। बाइनरी खोज में एक्सेस पैटर्न हार्डवेयर प्रीफेचर के लिए बहुत यादृच्छिक दिखता है, इसलिए कम संभावना है कि यह सटीक रूप से भविष्यवाणी करेगा कि क्या हासिल करना है।

इस उदाहरण में, मैं वर्तमान पुनरावृत्ति में अगले लूप पुनरावृत्ति के दो संभावित 'मध्य' स्थानों को पूर्ववत करता हूं। Prefetches में से एक शायद कभी इस्तेमाल नहीं किया जाएगा, लेकिन दूसरा होगा (जब तक यह अंतिम पुनरावृत्ति नहीं है)।

$ 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 

सूचना है कि हम प्रीफ़ेच संस्करण में कई एल 1 कैश लोड होने पर दो बार कर रहे हैं:

#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% कटौती को देखते हैं।हम वास्तव में बहुत अधिक काम कर रहे हैं लेकिन मेमोरी एक्सेस पैटर्न पाइपलाइन के लिए अधिक अनुकूल है। यह ट्रेडऑफ भी दिखाता है। हालांकि कोड का यह ब्लॉक अलगाव में तेजी से चलता है, हमने कैश में बहुत जंक लोड किया है और यह एप्लिकेशन के अन्य हिस्सों पर अधिक दबाव डाल सकता है।