multithreading - OpenMP:堆数组性能较差(堆栈数组工作正常)

Question

我是一位相当有经验的 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).

非常感谢任何帮助!

Answer 1

这是一个可爱的问题:使用上面的代码(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);
 }