首页 文章

预取示例?

提问于
浏览
57

任何人都可以举例或链接到在GCC中使用 __builtin_prefetch 的示例(或者通常只是asm指令prefetcht0)以获得实质性的性能优势吗?特别是,我希望这个例子符合以下标准:

  • 这是一个简单,小巧,独立的例子 .

  • 删除 __builtin_prefetch 指令会导致性能下降 .

  • 用相应的内存访问替换 __builtin_prefetch 指令会导致性能下降 .

也就是说,我想要最短的例子显示 __builtin_prefetch 执行一个没有它就无法管理的优化 .

5 回答

  • 60

    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);
              /* ... */
            }
    
  • 0

    这是我从一个更大的项目中抽出的一段实际代码 . (对不起,这是我能找到的最短的一个,它具有预取的显着加速 . )此代码执行非常大的数据转置 .

    此示例使用SSE预取指令,该指令可能与GCC发出的指令相同 .

    要运行此示例,您需要为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.725 seconds
    Press any key to continue . . .
    

    当我在禁用ENABLE_PREFETCH的情况下运行它时,这是输出:

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

    因此预取的速度提高了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
    
  • 2

    我从@JamesScriven和@Mystical提供的优秀答案中学到了很多东西 . 然而,他们的例子只给予了适度的提升 - 这个答案的目的是提出一个(我必须承认有点人为)的例子,其中预取具有更大的影响(在我的机器上大约是因子4) .

    现代架构有三种可能的瓶颈:CPU速度,内存带宽和内存延迟 . 预取就是减少内存访问的延迟 .

    在一个完美的场景中,延迟对应于X计算步骤,我们将有一个oracle,它会告诉我们在X计算步骤中将访问哪些内存,这些数据的预取将被启动并且它将仅在以下情况下到达 - 时间X计算 - 稍后的步骤 .

    对于很多算法,我们(几乎)在这个完美的世界中 . 对于简单的for循环,很容易预测X步之后需要哪些数据 . 乱序执行和其他硬件技巧在这里做得非常好,几乎完全隐藏了延迟 .

    这就是为什么@ Mystical的例子有这么小的改进的原因:预取器已经相当不错 - 没有太大的改进空间 . 任务也受内存限制,因此可能没有多少带宽 - 它可能成为限制因素 . 我的机器最多可以看到8%的改进 .

    来自@JamesScriven示例的重要见解:在从内存中获取当前数据之前,我们和CPU都不知道下一个访问地址 - 这种依赖性非常重要,否则无序执行会导致前瞻性并且硬件将能够预取数据 . 但是,因为我们只能推测一步没有那么大的潜力 . 我的机器无法超过40% .

    因此,让我们以竞争对手的方式准备数据,以便我们知道在X步骤中访问哪个地址,但由于依赖于尚未访问的数据,硬件无法找到它(最后查看整个程序)答案):

    //making random accesses to memory:
    unsigned int next(unsigned int current){
       return (current*10001+328)%SIZE;
    }
    
    //the actual work is happening here
    void operator()(){
    
        //set up the oracle - let see it in the future oracle_offset steps
        unsigned int prefetch_index=0;
        for(int i=0;i<oracle_offset;i++)
            prefetch_index=next(prefetch_index);
    
        unsigned int index=0;
        for(int i=0;i<STEP_CNT;i++){
            //use oracle and prefetch memory block used in a future iteration
            if(prefetch){
                __builtin_prefetch(mem.data()+prefetch_index,0,1);    
            }
    
            //actual work, the less the better
            result+=mem[index];
    
            //prepare next iteration
            prefetch_index=next(prefetch_index);  #update oracle
            index=next(mem[index]);               #dependency on `mem[index]` is VERY important to prevent hardware from predicting future
        }
    }
    

    一些评论:

    • 数据以这样的方式准备,即oracle总是正确的 .

    • 可能令人惊讶的是,CPU加载任务越少,加速越大:我们几乎可以完全隐藏延迟,因此加速是 CPU-time+original-latency-time/CPU-time .

    编译和执行潜在客户:

    >>> g++ -std=c++11 prefetch_demo.cpp -O3 -o prefetch_demo
    >>> ./prefetch_demo
    #preloops   time no prefetch    time prefetch   factor
    ...
    7   1.0711102260000001  0.230566831 4.6455521002498408
    8   1.0511602149999999  0.22651144600000001 4.6406494398521474
    9   1.049024333 0.22841439299999999 4.5926367389641687
    ....
    

    加速到4到5之间 .


    prefetch_demp.cpp 的清单:

    //prefetch_demo.cpp
    
    #include <vector>
    #include <iostream>
    #include <iomanip>
    #include <chrono>
    
    const int SIZE=1024*1024*1;
    const int STEP_CNT=1024*1024*10;
    
    unsigned int next(unsigned int current){
       return (current*10001+328)%SIZE;
    }
    
    
    template<bool prefetch>
    struct Worker{
       std::vector<int> mem;
    
       double result;
       int oracle_offset;
    
       void operator()(){
            unsigned int prefetch_index=0;
            for(int i=0;i<oracle_offset;i++)
                prefetch_index=next(prefetch_index);
    
            unsigned int index=0;
            for(int i=0;i<STEP_CNT;i++){
                //prefetch memory block used in a future iteration
                if(prefetch){
                    __builtin_prefetch(mem.data()+prefetch_index,0,1);    
                }
                //actual work:
                result+=mem[index];
    
                //prepare next iteration
                prefetch_index=next(prefetch_index);
                index=next(mem[index]);
            }
       }
    
       Worker(std::vector<int> &mem_):
           mem(mem_), result(0.0), oracle_offset(0)
       {}
    };
    
    template <typename Worker>
        double timeit(Worker &worker){
        auto begin = std::chrono::high_resolution_clock::now();
        worker();
        auto end = std::chrono::high_resolution_clock::now();
        return std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count()/1e9;
    }
    
    
     int main() {
         //set up the data in special way!
         std::vector<int> keys(SIZE);
         for (int i=0;i<SIZE;i++){
           keys[i] = i;
         }
    
         Worker<false> without_prefetch(keys);
         Worker<true> with_prefetch(keys);
    
         std::cout<<"#preloops\ttime no prefetch\ttime prefetch\tfactor\n";
         std::cout<<std::setprecision(17);
    
         for(int i=0;i<20;i++){
             //let oracle see i steps in the future:
             without_prefetch.oracle_offset=i;
             with_prefetch.oracle_offset=i;
    
             //calculate:
             double time_with_prefetch=timeit(with_prefetch);
             double time_no_prefetch=timeit(without_prefetch);
    
             std::cout<<i<<"\t"
                      <<time_no_prefetch<<"\t"
                      <<time_with_prefetch<<"\t"
                      <<(time_no_prefetch/time_with_prefetch)<<"\n";
         }
    
     }
    
  • 28

    预取数据可以优化为高速缓存行大小,对于大多数现代64位处理器来说,这是64字节,例如用一条指令预加载uint32_t [16] .

    例如,在ArmV8上,我通过实验发现,将内存指针转换为uint32_t 4x4矩阵向量(大小为64字节),需要将所需的指令减半,因为它只需加载一半数据,因为它只加载了一半的数据,即使我的理解是它获取了一个完整的缓存行 .

    预取uint32_t [32]原始代码示例......

    int addrindex = &B[0];
        __builtin_prefetch(&V[addrindex]);
        __builtin_prefetch(&V[addrindex + 8]);
        __builtin_prefetch(&V[addrindex + 16]);
        __builtin_prefetch(&V[addrindex + 24]);
    

    后...

    int addrindex = &B[0];
    __builtin_prefetch((uint32x4x4_t *) &V[addrindex]);
    __builtin_prefetch((uint32x4x4_t *) &V[addrindex + 16]);
    

    由于某种原因,地址索引/偏移量的int数据类型提供了更好的性能 . 在Cortex-a53上使用GCC 8进行测试 . 如果您发现它不是像我的情况那样预取所有数据,那么在其他体系结构上使用等效的64字节向量可能会提供相同的性能提升 . 在我的应用程序中有一百万个迭代循环,只需这样做就可以将性能提高5% . 对改进还有进一步的要求 .

    128兆字节的“V”内存分配必须与64对齐字节 .

    uint32_t *V __attribute__((__aligned__(64))) = (uint32_t *)(((uintptr_t)(__builtin_assume_aligned((unsigned char*)aligned_alloc(64,size), 64)) + 63) & ~ (uintptr_t)(63));
    

    此外,我不得不使用C运算符而不是Neon Intrinsics,因为它们需要常规数据类型指针(在我的情况下它是 uint32_t * ),否则新的内置预取方法会有性能回归 .

    我的真实世界示例可以在scrypt_core()中的https://github.com/rollmeister/veriumMiner/blob/main/algo/scrypt.c找到,它的内部函数都很容易阅读 . 辛勤工作由GCC8完成 . 整体性能提升为25% .

  • 0

    二进制搜索是一个可以从显式预取中受益的简单示例 . 二进制搜索中的访问模式对于硬件预取器来说几乎是随机的,因此它几乎不可能准确地预测要获取的内容 .

    在这个例子中,我预先获取当前迭代中下一个循环迭代的两个可能的“中间”位置 . 其中一个预取可能永远不会被使用,但另一个将被使用(除非这是最后的迭代) .

    #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%:

    $ 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
    

    请注意,我们在预取版本中执行的L1缓存加载量是其两倍 . 我们实际上做了很多工作,但内存访问模式对管道更友好 . 这也显示了权衡 . 虽然这段代码在隔离时运行得更快,但我们已经在缓存中加载了大量垃圾,这可能会给应用程序的其他部分带来更大的压力 .

相关问题