我是一位相当有经验的 OpenMP 用户,但我刚刚遇到了一个令人费解的问题,我希望这里有人可以提供帮助。问题在于,简单的哈希算法对于堆栈分配的数组表现良好,但对于堆上的数组表现不佳。
下面的示例使用 i%M(i 模 M)来计算各个数组元素中的每个第 M 个整数。为简单起见,假设 N=1000000,M=10。如果N%M==0,那么结果应该是bins[]的每个元素都等于N/M:
#pragma omp for
for (int i=0; i<N; i++)
bins[ i%M ]++;
数组 bins[] 是每个线程私有(private)的(之后我将关键部分中所有线程的结果相加)。
当 bins[] 在堆栈上分配时,程序运行良好,性能与核心数量成正比。
但是,如果 bins[] 位于堆上(指向 bins[] 的指针位于堆栈上),性能会急剧下降。这是一个大问题!
我希望使用 OpenMP 将某些数据并行装箱(散列)到堆数组中,这会对性能造成重大影响。
这绝对不是像所有线程都试图写入同一内存区域那样愚蠢的事情。 这是因为每个线程都有自己的 bins[] 数组,堆分配的 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: %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).
非常感谢任何帮助!
最佳答案
这是一个可爱的问题:使用上面的代码(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).
这里的问题是false sharing 。默认的 malloc 非常(空间)高效,并将请求的小分配全部放在一个内存块中,彼此相邻;但由于分配非常小,以至于多个适契约(Contract)一缓存行,这意味着每次一个线程更新其值时,它都会弄脏相邻线程中值的缓存行。通过使请求的内存足够大,这不再是问题。
顺便说一句,应该清楚为什么堆栈分配的情况不会出现这个问题;不同的线程 - 不同的堆栈 - 内存足够大,错误共享不是问题。
顺便说一句——对于您在这里使用的 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);
}
关于multithreading - OpenMP:堆数组性能较差(堆栈数组工作正常),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6605677/