openMp：并行化 std::map 次迭代

Question

有一些关于此问题的帖子，但其中 none 令我满意。我没有 openMp 3.0 支持，我需要在地图上并行化迭代。我想知道这个解决方案是否有效：

auto element = myMap.begin();

#pragma omp parallel for shared(element)
for(int i = 0 ; i < myMap.size() ; ++i){
 MyKeyObject * current_first = nullptr;
 MyValueObject * current_second = nullptr;
#pragma omp critical
{
    current_first = element->first;
    current_second = element->second;
    ++element;
}

// Here I can use 'current' as in a usual loop
}

所以我使用 for 循环只是为了确保线程将同样处理相同数量的地图元素。这是一个正确的猜测还是会失败？

ps : 我正在研究 visual studio 2012 所以如果你有关于如何让我的编译器支持 openMp 3.0 的提示，那也解决我的问题..

Answer 1

您的方法行不通 - 因为概念上的问题和一些错误。

[bug] 你总是会错过第一个元素，因为你做的第一件事就是增加元素迭代器。
[bug] 所有线程都将遍历整个地图，因为元素迭代器不是共享的。顺便说一句，您的代码中的共享变量 'part' 是什么不清楚。
如果您使元素共享，那么访问它的代码（在关键部分之外）将看到它当前指向的任何内容，而不管线程。您最终会不止一次地处理某些元素，而有些元素 - 根本不会。

没有简单的方法可以使用迭代器并行访问地图，因为地图迭代器不是随机访问的。您可能希望手动拆分密钥，然后在不同线程上使用密钥集的不同部分。

Answer 2

这不是对你问题的直接回答，但我会尽量为你节省一些以后不好的"OpenMP with Visual Studio"经验。

Microsoft C/C++ 编译器仅支持 OpenMP 2.0。没有办法让它支持 OpenMP 3.0 或更高版本，因为 OpenMP 内置在编译器核心中而不是附加包（除非有人提出外部源到源转换引擎）并且 Microsoft 似乎不是有兴趣在推出自己的解决方案的同时提供进一步的 OpenMP 支持（见下文）。因此，您应该获得与 Visual Studio 集成的 Intel C/C++ 编译器或独立编译器，如 GCC 或 PGI C/C++ 编译器。

如果您是专门为 Windows 开发的，那么您可能想要放弃 OpenMP 并改用 Concurrency Runtime，特别是 PPL。 PPL 附带 Visual Studio 2012 及更新版本，并提供与 STL 中的某些算法等效的数据和任务并行。你感兴趣的是concurrency::parallel_for_each()，也就是std::for_each()的平行版本。它适用于前向迭代器，尽管不如随机迭代器有效。但是你必须确保处理地图的一个元素至少需要一千条指令，否则并行化将无益。

如果您的目标是跨平台兼容性，那么 Intel Threading Building Blocks（简称 Intel TBB）是 PPL 的替代方案。它提供了 tbb::parallel_do() 算法，专门设计用于前向迭代器。关于每个地图元素的工作量的警告同样适用。

Answer 3

您的方法将起作用，因为您在关键部分访问并迭代了共享对象 element。这是否对性能有好处，您将必须进行测试。这是您可能要考虑的替代方法。让我称之为 "fast-forward" 方法。

假设您想并行执行此操作

for(auto element = myMap.begin(); element !=myMap.end(); ++element) {
    foo(element->first, element->second);
}

您可以使用 OpenMP 2.0 做到这一点

#pragma omp parallel
{
    size_t cnt = 0;
    int ithread = omp_get_thread_num();
    int nthreads = omp_get_num_threads();
    for(auto element = myMap.begin(); element !=myMap.end(); ++element, cnt++) {
        if(cnt%nthreads != ithread) continue;
        foo(element->first, element->second);
    }
}

每个线程都运行 myMap.size() 个 iteartors。但是，每个线程只调用foomyMap.size()/num_threads。您的方法仅通过 myMap.size()/num_threads 个迭代器运行。但是，它需要在每次迭代时都使用临界区。

只要通过 nthreads 迭代器 "fast-forward" 的时间比 foo 的时间少得多，快进方法就是有效的，即：

nthreads*time(++elements) << time(foo)

但是，如果 foo 的时间符合迭代时间并且 foo 是 reading/writing 内存，那么 foo 可能是内存带宽限制并赢得了无论如何都要随线程数缩放。

openMp：并行化 std::map 次迭代

openMp : parallelize std::map iteration

c++

stdmap

openmp