OpenMP：堆阵列性能差（堆栈阵列工作正常）
我是一个相当有经验的OpenMP用户，但我遇到了一个令人困惑的问题，我希望这里的某个人能够提供帮助。 问题是一个简单的哈希算法对堆栈分配的数组执行效果很好，但对堆中的数组效果不佳。
下面的示例使用i％M（i模数M）来计算相应数组元素中的每个第M个整数。 为了简单起见，设想N = 1000000，M = 10。 如果N％M == 0，那么结果应该是每个元素的bin []等于N / M：
#pragma omp for
for (int i=0; i<N; i++)
bins[ i%M ]++;
Array bins []对每个线程都是私有的（之后，我将关键部分中所有线程的结果相加）。
当堆栈[]分配给堆栈时，该程序运行良好，性能按比例与核心数量成比例。
但是，如果堆栈[]位于堆栈上（指向堆栈[]的堆栈），则性能会急剧下降。 这是一个主要问题！
我想用OpenMP将某些数据的binning（hashing）并行化成堆数组，这是一个主要的性能问题。
这绝对不是像所有试图写入相同内存区域的线程都是愚蠢的。 这是因为每个线程都有自己的bin []数组，结果对堆和堆栈分配的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: %dn", 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).
我非常感谢任何帮助！
这是一个可爱的问题：使用上面的代码（gcc4.4，Intel 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).
这里的问题是错误的分享。 默认的malloc非常（空间）高效，并且将所请求的小分配全部放在一块内存中，彼此相邻; 但是由于分配太小以至于多个适配在同一个缓存行中，这意味着每当一个线程更新其值时，它就会使相邻线程中的值的缓存行变脏。 通过使请求的内存足够大，这不再是问题。
顺便说一句，应该清楚为什么堆栈分配的情况没有看到这个问题; 不同的线程 - 不同的堆栈 - 内存足够远以至于虚假共享不成问题。
作为一个观点 - 对于你在这里使用的大小的M来说并不重要，但是如果你的M（或者线程数量）更大，那么omp临界值将是一个很大的系列瓶颈; 您可以使用OpenMP减少来更有效地对校验和进行求和
#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);
}
上一篇: OpenMP: poor performance of heap arrays (stack arrays work fine)