3

在我的代码中的某个时刻，我必须对 unordered_map 中的所有元素进行操作。为了加速这个过程，我想使用 openMP，但天真的方法不起作用：

std::unordered_map<size_t, double> hastTable;

#pragma omp for
for(auto it = hastTable.begin();
    it != hastTable.end();
    it ++){
//do something
}

原因是 unordered_map 的迭代器不是随机访问迭代器。作为替代方案，我尝试了在 for_each 上工作的 __gnu_parallel 指令。但是下面的代码

#include <parallel/algorithm>
#include <omp.h>

__gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair<const size_t, double> & item)
                        {
                          //do something with item.secon
                        });

用（gcc 4.8.2）编译

 g++ -fopenmp -march=native -std=c++11

不并行运行。使用向量切换 unordered_map 并使用相同的 __gnu_parallel 指令并行运行。

为什么在无序地图的情况下它不并行运行？有解决方法吗？

下面我给你一些简单的代码，它重现了我的问题。

#include <unordered_map>
#include <parallel/algorithm>
#include <omp.h>

int main(){

//unordered_map                                                                                                                                      
std::unordered_map<size_t, double> hashTable;
double val = 1.;
for(size_t i = 0; i<100000000; i++){
  hashTable.emplace(i, val);
  val += 1.;
}
__gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair<const size_t, double> & item)
                        {
                          item.second *= 2.;
                        });

//vector                                                                                                                                             
std::vector<double> simpleVector;
val = 1.;
for(size_t i = 0; i<100000000; i++){
  simpleVector.push_back(val);
  val += 1.;
}
__gnu_parallel::for_each (simpleVector.begin(), simpleVector.end(),[](double & item)
                        {
                          item *= 2.;
                        });

}

我期待着您的回答。

4

3 回答 3

7

不支持随机迭代器的容器的规范方法是使用显式 OpenMP 任务：

std::unordered_map<size_t, double> hastTable;

#pragma omp parallel
{
   #pragma omp single
   {
      for(auto it = hastTable.begin(); it != hastTable.end(); it++) {
         #pragma omp task
         {
            //do something
         }
      }
   }
}

这会为每次迭代创建一个单独的任务，这会带来一些开销，因此只有在//do something实际意味着//do quite a bit of work.

于 2014-09-25T12:07:45.217 回答
1

您可以在桶索引范围内拆分循环，然后创建一个桶内迭代器来处理元素。 unordered_maphas和特定于存储桶的.bucket_count()iterator-yielding允许这样做。假设您没有从 1.0 修改默认值并且具有合理的散列函数，您将平均每个存储桶 1 个元素，并且不应该在空存储桶上浪费太多时间。begin(bucket_number)end(bucket_number)max_load_factor()

于 2014-09-25T09:30:41.223 回答
1

您可以通过遍历 的桶来做到这一点unordered_map，如下所示：

#include <cmath>
#include <iostream>
#include <unordered_map>

int main(){
  const int N = 10000000;
  std::unordered_map<int, double> mymap(1.5*N);

  //Load up a hash table
  for(int i=0;i<N;i++)
    mymap[i] = i+1;

  #pragma omp parallel for default(none) shared(mymap)
  for(size_t b=0;b<mymap.bucket_count();b++)
  for(auto bi=mymap.begin(b);bi!=mymap.end(b);bi++){
    for(int i=0;i<20;i++)
      bi->second += std::sqrt(std::log(bi->second) + 1);
  }

  std::cout<<mymap.begin()->first<<" "<<mymap.begin()->second<<std::endl;

  return 0;
}
于 2019-06-21T21:44:19.140 回答