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，其中包含 10 亿个随机整数 range [0,9]。然后，代码循环v计算每个不同整数有多少个实例（即，在v中找到多少个，有多少个二等）

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

我的问题是当我尝试使计数循环并行时。没有该#pragma OpenMP语句，我的代码需要20秒，而使用60 多秒。pragma

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

4

2 回答 2

6

您的代码显示：

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

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

当两个线程写入彼此靠近的内存位置以导致在同一高速缓存行上时，就会发生错误共享。这导致缓存线在多插槽系统中不断地从内核跳到内核或 CPU 到 CPU，并导致缓存一致性消息过多。每个缓存行 32 个字节，向量的 8 个元素可以放在一个缓存行中。每个缓存行有 64 个字节，整个向量d适合一个缓存行。这使得代码在 Core 2 处理器上变慢，而在 Nehalem 和 post-Nehalem（例如 Sandy Bridge）处理器上稍慢（但不如 Core 2 慢）。真正的共享发生在两个或多个线程同时访问的那些元素上。您应该将增量放在 OpenMPatomic构造中（慢），使用 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()or gettimeofday()（或其他一些高分辨率计时器 API）。

于 2012-07-25T17:39:29.367 回答
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/

于 2012-07-25T16:57:32.350 回答