OpenMP和C++并行for循环：为什么使用OpenMP时我的代码会变慢？

Question

OpenMP和C++并行for循环：为什么使用OpenMP时我的代码会变慢？

4

我有一个简单的关于使用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，其中包含范围在[0,9]内的10亿个随机整数。然后，代码循环遍历v，计算每个不同整数的实例数量（即，在v中找到多少个1、多少个2等）。

每次遇到特定整数时，通过递增向量d的相应元素来进行计数。因此，d[0]计算有多少个零，d[6]计算有多少个六，以此类推。到目前为止还清楚吗？

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

显然，我误解了与OpenMP相关的某些概念（也许是数据共享/访问方式？）。请问有人能解释我的错误或指点一些关键字和有见地的文献来帮助我的搜索吗？

- Dan

你的算法并发处理方式有误。按照你的方式，两个线程可能同时访问同一个索引。 - Ian Medeiros

时间问题没有复现，但是你的代码明显存在竞态条件。 - kennytm

6

正如 @IanMedeiros 指出的那样，许多人混淆了“parallelising”和“paralysing”的词语。数据竞争通常会使并行化程序瘫痪。请重复30次。 - High Performance Mark

@IanMedeiros 你能向我解释一下它们之间的区别吗？ - pooria

2个回答

1

编辑一旦您通过正确的同步解决了竞争条件，那么以下段落适用于此，在此之前，您的数据竞争条件不幸地使速度比较无效：

您的程序正在减速，因为在pragma部分中有10个可能的输出，这些输出是随机访问的。由于OpenMP不能访问任何这些元素而不使用锁定（您需要通过同步提供），因此锁定将导致线程的开销比并行计数所获得的收益更高。

加速的解决方案是，为每个OpenMP线程创建一个本地变量，该变量计算特定线程已看到的所有0-10值。然后在主计数向量中对它们进行求和。这将很容易地并行化，并且比线程不需要在共享写入向量上锁定的方法快得多。我预计会获得接近Nx的加速，其中N是来自OpenMP的线程数，因为应该只需要非常有限的锁定。此解决方案还避免了代码中当前存在的许多竞争条件。

有关线程本地OpenMP的更多详细信息，请参见http://software.intel.com/en-us/articles/use-thread-local-storage-to-reduce-synchronization/。

- Pyrce

1

提出的解决方案很好，但是为什么它会变慢的解释是错误的。OpenMP默认情况下不会同步访问共享变量 - 必须显式地进行同步。 - Hristo Iliev

@HristoIliev 哦，是的，我错过了他没有同步，并更关注问题的整体解决方案，然后再解决冲突 - 我添加了一个编辑来反映这一点。 - Pyrce

1

OpenMP无法访问...相反，它可以。这就是为什么OpenMP提供了显式同步机制的原因。 - Hristo Iliev

是的，这是真的。我最初忽略了缺乏同步。我更新了我的答案，声明只有在正确实施同步后才是真的。 - Pyrce

如果变量很大，为每个omp线程制作本地副本将消耗更多的内存，对吗？ - avocado

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hristo Iliev · Accepted Answer

您的代码表现出以下问题：

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

当多个线程同时更新向量 d 的相同元素时，就会出现竞争条件。注释掉 srand() 行，并使用相同数量的线程（但不止一个线程）运行您的代码数次。比较不同运行的输出。

虚假共享发生在两个线程写入靠近彼此的内存位置，以至于它们在同一缓存行中。这会导致缓存行在多核心或多CPU系统中不断地从核心到核心或从CPU到CPU跳动，并产生过多的缓存一致性消息。每个缓存行有32字节，则8个向量元素可以放在一个缓存行中。每个缓存行有64字节，则整个向量 d 可以放在一个缓存行中。这使得该代码在 Core 2 处理器上变慢，并且在 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）。