打开 MP 瓶颈问题

Question

我试图通过以下代码观察基于 openMP 的基本并行性，

#include<stdio.h>
#include<omp.h>
#include<stdlib.h>
#include <time.h>
int main(){
  long i;
  long x[] = {0,0,0,0};
  omp_set_num_threads(4);
  clock_t time=clock();
  #pragma omp parallel for
  for(i=0;i<100000000;i++){
    x[omp_get_thread_num()]++;
  }
  double time_taken = (double)(clock() - time) / CLOCKS_PER_SEC;
  printf("%ld %ld %ld %ld %lf\n",x[0],x[1],x[2],x[3],time_taken);
}

现在，我使用的是四核 i5 处理器。我检查了线程的 4 个不同值。找到以下结果，

Set: omp_set_num_threads(1);
Out: 100000000 0 0 0 0.203921

Set: omp_set_num_threads(2);
Out: 50000000 50000000 0 0 0.826322

Set: omp_set_num_threads(3);
Out: 33333334 33333333 33333333 0 1.448936

Set: omp_set_num_threads(4);
Out: 25000000 25000000 25000000 25000000 1.919655

x 数组值是准确的。但是随着线程数量的增加，时间惊人地增加了。我无法得到任何 explanation/justification 背后的现象。不知何故，omp_get_thread_num() 函数本质上是原子的？或者我错过了什么？

编译为，gcc -o test test.c -fopenmp

更新

所以，根据接受的答案中的建议，我将代码修改如下，

#include<stdio.h>
#include<omp.h>
#include<stdlib.h>
int main(){
  long i, t_id, fact=1096;
  long x[fact*4];
  x[0]=x[fact]=x[2*fact]=x[3*fact]=0;
  omp_set_num_threads(4);
  double time = omp_get_wtime();
  #pragma omp parallel for private(t_id)
    for(i=0;i<100000000;i++){
      t_id = omp_get_thread_num();
      x[t_id*fact]++;
  }
  double time_taken = omp_get_wtime() - time;
  printf("%ld %ld %ld %ld %lf\n",x[0],x[fact],x[2*fact],x[3*fact],time_taken);
}

现在，结果是可以理解的，

Set: omp_set_num_threads(1)
Out: 100000000 0 0 0 0.250205

Set: omp_set_num_threads(2)
Out: 50000000 50000000 0 0 0.154980

Set: omp_set_num_threads(3)
Out: 33333334 33333333 33333333 0 0.078874

Set: omp_set_num_threads(4)
Out: 25000000 25000000 25000000 25000000 0.061155

因此，它与接受的答案中解释的缓存行大小有关。看看那里得到答案。

Answer 1

请注意，您正在操作的 4 个整数非常靠近，可能在一个 cache line. Since cache lines are loaded into the CPU cache in one go, each thread needs to ensure that it has the latest version of that cache line. Since all threads want to modify (and not just read) that one cache line, they are constantly invalidating one another's copy. Welcome to false sharing!

上

要解决这个问题，请确保整数（物理上）彼此足够远，例如，通过分配结构来填充（至少）一个完整的缓存行供每个线程使用。

在我的一台机器上使用 4 个线程执行示例程序时，我得到以下结果：

25000000 25000000 25000000 25000000 5.049694

修改程序，使数组有4096个元素，使用元素0、1024、2048、3072（保证足够的距离），程序运行速度会快很多：

25000000 25000000 25000000 25000000 1.617231

请注意，虽然你是counting the processor time used by the whole process，但如果没有虚假共享，时间应该不会显着增加，而是或多或少是恒定的（涉及一些额外的锁定，但通常不应该在增加 10 倍）。事实上，上面显示的性能提升也转化为 wall-clock 时间（~1.25 秒到~500 毫秒）。

Answer 2

如 gha.st 所述，您观察的原因是错误共享和 clock 函数的属性。

因此 x[omp_get_thread_num()]，是一个 anti-pattern。当然，您可以通过在记忆中增加一步来利用您的新知识。但这也会将 hardware-specific 属性（即缓存行大小）编码到您的数据结构中。这可能会导致难以理解且性能仍然不佳的令人讨厌的代码 可移植性。

惯用的解决方案是使用以下任一方法：

如果您只对聚合感兴趣，请使用 reduction 子句，即：

long x = 0;
#pragma omp parallel for reduction(+:x)
for(i=0;i<100000000;i++){
    x++;
}
// total sum is now in x

如果您需要线程中的单个值，只需使用 private 变量，最好按范围隐式使用。或者，如果您需要从构造外部进行特定初始化，请使用 firstprivate.

#pragma omp parallel
{
    long local_x = 0; // implicitly private by scope!
    #pragma omp for
    for(i=0;i<100000000;i++) {
        local_x++;
    }
    // can now do something with the the sum of the current thread.
}

而如果你需要外面的per-thread结果，你可以使用第二种形式，只写一次结果：

#pragma omp parallel
{
    long local_x = 0; // implicitly private by scope!
    #pragma omp for
    for(i=0;i<100000000;i++) {
        local_x++;
    }
    x[omp_get_thread_num()] = local_x;
}

这并不是说您永远不需要在设计数据结构时考虑 false-sharing。但它并不像你想象的那么普遍。

打开 MP 瓶颈问题

Open MP bottleneck issue

c

c++

multithreading

pthreads

openmp