OpenMP：堆阵列性能不佳（堆栈阵列工作正常）

Question

我是一个相当有经验的OpenMP用户，但我遇到了一个令人困惑的问题，我希望这里有人能够提供帮助。问题是一个简单的哈希算法对堆栈分配的数组执行效果很好，但对堆中的数组效果不佳。

以下示例使用i％M（i模数M）来计算各个数组元素中的每个第M个整数。为了简单起见，设想N = 1000000，M = 10。如果N％M == 0，则结​​果应该是仓[]中的每个元素是等于N/M：

#pragma omp for 
    for (int i=0; i<N; i++) 
    bins[ i%M ]++; 

阵列仓[]是私有的每个线程的所有线程的（I总和结果之后的关键部分）。

当在堆栈上分配了bins []时，该程序效果很好，性能与核心数成正比。但是，如果bin []位于堆栈上（指向bin []的指针位于堆栈上），则性能会急剧下降。这是一个主要问题！

我想要使用OpenMP将某些数据的binning（hashing）并行化成堆数组，这是一个主要的性能问题。

这绝对不是像所有线程试图写入同一个内存区域一样愚蠢。 这是因为每个线程都有自己的bin []数组，堆和堆栈分配的结果都是正确的，并且单线程运行的性能没有差别。 我使用GCC和Intel C++编译器在不同的硬件（Intel Xeon和AMD Opteron）上重现了这个问题。所有测试都在Linux（Ubuntu和RedHat）上进行。

似乎没有理由将OpenMP的良好性能限制为堆栈阵列。

任何猜测？也许线程访问堆通过Linux上的某种共享网关？我如何解决这个问题？

完整的程序一起玩周围低于：

#include <stdlib.h> 
#include <stdio.h> 
#include <omp.h> 

int main(const int argc, const char* argv[]) 
{ 
    const int N=1024*1024*1024; 
    const int M=4; 
    double t1, t2; 
    int checksum=0; 

    printf("OpenMP threads: %d\n", omp_get_max_threads()); 

    ////////////////////////////////////////////////////////////////// 
    // Case 1: stack-allocated array 
    t1=omp_get_wtime(); 
    checksum=0; 
#pragma omp parallel 
    { // Each openmp thread should have a private copy of 
    // bins_thread_stack on the stack: 
    int bins_thread_stack[M]; 
    for (int j=0; j<M; j++) bins_thread_stack[j]=0; 
#pragma omp for 
    for (int i=0; i<N; i++) 
     { // Accumulating every M-th number in respective array element 
     const int j=i%M; 
     bins_thread_stack[j]++; 
     } 
#pragma omp critical 
    for (int j=0; j<M; j++) checksum+=bins_thread_stack[j]; 
    } 
    t2=omp_get_wtime(); 
    printf("Time with stack array: %12.3f sec, checksum=%d (must be %d).\n", t2-t1, checksum, N); 
    ////////////////////////////////////////////////////////////////// 

    ////////////////////////////////////////////////////////////////// 
    // Case 2: heap-allocated array 
    t1=omp_get_wtime(); 
    checksum=0; 
    #pragma omp parallel 
    { // Each openmp thread should have a private copy of 
    // bins_thread_heap on the heap: 
    int* bins_thread_heap=(int*)malloc(sizeof(int)*M); 
    for (int j=0; j<M; j++) bins_thread_heap[j]=0; 
    #pragma omp for 
    for (int i=0; i<N; i++) 
     { // Accumulating every M-th number in respective array element 
     const int j=i%M; 
     bins_thread_heap[j]++; 
     } 
    #pragma omp critical 
    for (int j=0; j<M; j++) checksum+=bins_thread_heap[j]; 
    free(bins_thread_heap); 
    } 
    t2=omp_get_wtime(); 
    printf("Time with heap array: %12.3f sec, checksum=%d (must be %d).\n", t2-t1, checksum, N); 
    ////////////////////////////////////////////////////////////////// 

    return 0; 
} 

程序的样本输出是如下：

为OMP_NUM_THREADS = 1

OpenMP threads: 1 
Time with stack array: 2.973 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array: 3.091 sec, checksum=1073741824 (must be 1073741824). 

和OMP_NUM_THREADS = 10

OpenMP threads: 10 
Time with stack array: 0.329 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array: 2.150 sec, checksum=1073741824 (must be 1073741824). 

我非常感谢任何帮助！

Answer 1

这是一个可爱的问题：使用上面的代码（gcc4。4，英特尔酷睿i7）有4个线程，我得到

OpenMP threads: 4 
Time with stack array:  1.696 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array:  5.413 sec, checksum=1073741824 (must be 1073741824). 

，但如果我malloc的线路改变为

int* bins_thread_heap=(int*)malloc(sizeof(int)*M*1024); 

（更新：甚至

int* bins_thread_heap=(int*)malloc(sizeof(int)*16); 

）

然后我得到

OpenMP threads: 4 
Time with stack array:  1.578 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array:  1.574 sec, checksum=1073741824 (must be 1073741824). 

这里的问题是false sharing。默认的malloc非常（空间）高效，并且将所请求的小分配全部放在一块内存中，彼此相邻;但是由于分配太小以至于多个适配在同一个缓存行中，这意味着每当一个线程更新其值时，它就会使相邻线程中的值的缓存行变脏。通过使请求的内存足够大，这不再是问题。

顺便说一句，应该清楚为什么堆栈分配的情况下没有看到这个问题;不同的线程 - 不同的堆栈 - 内存足够远以至于虚假共享不成问题。作为一个观点 - 对于你在这里使用的大小的M来说并不重要，但是如果你的M（或者线程的数量）更大，那么omp临界值将是一个很大的系列瓶颈;你可以使用OpenMP reductions来更有效地求和校验和

#pragma omp parallel reduction(+:checksum) 
    { // Each openmp thread should have a private copy of 
     // bins_thread_heap on the heap: 
     int* bins_thread_heap=(int*)malloc(sizeof(int)*M*1024); 
     for (int j=0; j<M; j++) bins_thread_heap[j]=0; 
#pragma omp for 
     for (int i=0; i<N; i++) 
     { // Accumulating every M-th number in respective array element 
      const int j=i%M; 
      bins_thread_heap[j]++; 
     } 
     for (int j=0; j<M; j++) 
      checksum+=bins_thread_heap[j]; 
     free(bins_thread_heap); 
}