c++ - OpenMP 和 C++ 并行 for 循环 : why does my code slow down when using OpenMP?

Question

我有一个关于使用 OpenMP(与 C++)的简单问题，我希望有人能帮助我。我在下面提供了一个小示例来说明我的问题。

#include<iostream>
#include<vector>
#include<ctime>
#include<omp.h>

using namespace std;

int main(){
  srand(time(NULL));//Seed random number generator                                                                               

  vector<int>v;//Create vector to hold random numbers in interval [0,9]                                                                                   
  vector<int>d(10,0);//Vector to hold counts of each integer initialized to 0                                                                    

  for(int i=0;i<1e9;++i)
    v.push_back(rand()%10);//Push back random numbers [0,9]                                                                      

  clock_t c=clock();

  #pragma omp parallel for
  for(int i=0;i<v.size();++i)
    d[v[i]]+=1;//Count number stored at v[i]                                                                                     

  cout<<"Seconds: "<<(clock()-c)/CLOCKS_PER_SEC<<endl;

  for(vector<int>::iterator i=d.begin();i!=d.end();++i)
  cout<<*i<<endl;

  return 0;
}

上述代码创建了一个 vector v，其中包含 [0,9] 范围内的 10 亿个随机整数。然后，代码循环遍历 v，计算每个不同整数的实例数量(即，在 v 中找到了多少个，有多少两个，等等)

每次遇到特定整数时，都会通过递增 vector d 的适当元素来对其进行计数。因此，d[0] 计算了多少个零，d[6] 计算了多少个六，等等。到目前为止有意义吗？

我的问题是当我试图使计数循环并行时。如果没有 #pragma OpenMP 语句，我的代码需要 20 秒，但是使用 pragma 需要超过 60 秒.

显然，我误解了一些与 OpenMP 相关的概念(可能是如何共享/访问数据？)。有人可以解释我的错误，或者用适当的关键字为我指出一些有见地的文献的方向以帮助我进行搜索吗？

Answer 1

您的代码展示:

• 由于对共享变量的未同步访问而导致的竞争条件
• 真假共享缓存问题
• 错误的运行时间测量

出现竞争条件是因为您在多个线程中同时更新 vector d 的相同元素。注释掉 srand() 行并使用相同数量的线程(但不止一个线程)多次运行您的代码。比较不同运行的输出。

当两个线程写入彼此靠近的内存位置以导致同一缓存行时，就会发生错误共享。这会导致缓存行在多路系统中不断地从一个内核跳到另一个内核或从一个 CPU 跳到另一个 CPU，并且缓存一致性消息过多。每个缓存行 32 个字节， vector 的 8 个元素可以放在一个缓存行中。每个缓存行 64 字节，整个 vector d 适合一个缓存行。这使得代码在 Core 2 处理器上变慢，在 Nehalem 和后 Nehalem(例如 Sandy Bridge)处理器上稍微慢一些(但不像 Core 2 慢)。真正的共享发生在那些被两个或多个线程同时访问的元素上。您应该将增量放在 OpenMP atomic 构造中(慢)，使用一组 OpenMP 锁来保护对 d 元素的访问(更快或更慢，具体取决于您的OpenMP 运行时)或累积本地值，然后进行最终的同步缩减(最快)。第一个是这样实现的:

#pragma omp parallel for
for(int i=0;i<v.size();++i)
  #pragma omp atomic
  d[v[i]]+=1;//Count number stored at v[i]   

第二个是这样实现的:

omp_lock_t locks[10];
for (int i = 0; i < 10; i++)
  omp_init_lock(&locks[i]);

#pragma omp parallel for
for(int i=0;i<v.size();++i)
{
  int vv = v[i];
  omp_set_lock(&locks[vv]);
  d[vv]+=1;//Count number stored at v[i]
  omp_unset_lock(&locks[vv]);
}

for (int i = 0; i < 10; i++)
  omp_destroy_lock(&locks[i]);

(包含 omp.h 以访问 omp_* 函数)

第三个选项的实现由您来决定。

您正在使用 clock() 测量耗时，但它测量的是 CPU 时间，而不是运行时间。如果您有一个线程以 100% 的 CPU 使用率运行 1第二，然后 clock() 将指示 CPU 时间增加 1 秒。如果您有 8 个线程以 100% 的 CPU 使用率运行 1 秒，clock() 将指示 increate in CPU 时间为 8 秒(即 8 个线程乘以每个线程 1 个 CPU 秒)。请改用 omp_get_wtime() 或 gettimeofday()(或其他一些高分辨率计时器 API)。