OpenMP和C++并行for循环:为什么我的代码在使用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;
}

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

每次遇到特定的整数时,都会通过递增向量的适当元素来计算d.因此,d[0]计算多少个零,d[6]计算多少六个,依此类推.到目前为止有道理吗？

我的问题是当我尝试使计数循环并行时.如果没有#pragma OpenMP声明,我的代码需要20秒,但pragma需要超过60秒.

很明显,我误解了一些与OpenMP相关的概念(也许是如何共享/访问数据的？).有人可以解释我的错误,或者指点我用一些有见识的文献和适当的关键词来帮我搜索？

Answer 1

你的代码exibits:

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

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

当两个线程写入彼此接近的内存位置以产生相同的高速缓存行时,就会发生错误共享.这导致高速缓存行在多串口系统中不断地从核心跳转到核心或CPU到CPU,以及过多的高速缓存一致性消息.每个高速缓存行有32个字节,向量的8个元素可以放在一个高速缓存行中.每个高速缓存行有64个字节,整个向量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()表示CPU时间增加8秒(即8个线程乘以每个线程1个CPU秒).请改用omp_get_wtime()或使用gettimeofday()(或其他一些高分辨率计时器API).