openMp：并行化std :: map迭代

有一些关于这个问题的文章，但他们都不满足我。我没有openMp 3.0支持，我需要在地图上并行化迭代。我想知道，如果这个解决方案将工作或没有：openMp：并行化std :: map迭代

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的提示，这也将解决我的问题..

来源

2015-05-29 Arcyno

OpenMP 3.0有什么好处呢？如果你想在Visual Studio中使用OpenMP 3.0，那么你需要一个集成到Visual Studio中的新编译器（例如英特尔编译器）。 –

@Zboson，OpenMP 3.0具有明确的任务，并允许在地图上进行迭代并行执行，如show [here]（http://stackoverflow.com/a/22936165/1374437）。 –

@HristoIliev，谢谢你，我认为任务可能是正确的方法，因为它是（std :: map）作为二叉树实现，据我了解。是时候学习OpenMP中的任务了。 –

由于您在关键部分访问并迭代了共享对象element，因此您的方法可以正常工作。不管这对于性能是否有利，您都必须进行测试。以下是您可能需要考虑的另一种方法。让我称之为“快进”方法。

让我们假设你想通过myMap.size() iteartors使用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); 
    } 
}

每个线程运行，以做到这一点并行

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

你可以做到这一点。但是，每个线程只能调用foomyMap.size()/num_threads。您的方法只能通过myMap.size()/num_threads迭代器运行。但是，它需要在每次迭代中使用关键部分。

快进的方法是有效的，只要时间到“快进”，通过来确定nthreads itererators要少得多，则时间foo，即：

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

然而，如果该时间foo是在迭代的时间，而foo是读/写内存，foo可能是内存带宽的限制，并且不会随着线程的数量扩展。

来源

2015-06-01 08:41:02

好办法！（但没有人回答我的解决方案..是否好？） – Arcyno

为什么这不起作用？我在通常的循环中使用'omp parallel for' – Arcyno

@Arcyno，我把它拿回来，'omp parallel for'可以工作，但如果它是好的（性能明智）或者不好，你将不得不测试。将您的方法与我的“快进”方法进行比较将会很有趣。 –

你的做法是行不通的 - 因为这是一个概念性问题和一些错误的混合体。

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

因为地图迭代器不是随机访问，所以没有简单的方法使用迭代器并行访问地图。您可能想要手动分割键，然后使用不同线程上的键集的不同部分。

来源

2015-05-29 13:46:08

你是对的，但是我对这篇文章所做的修改呢？ – Arcyno

您的更改只解决了我提到的第一个问题。他们仍然不会给你并行迭代。事实上，关键部分甚至不是必需的，因为你的元素迭代器每个线程都是唯一的，所以没有争用。 –

再一次你是对的！现在，与共享元素？ – Arcyno

这不是对您的问题的直接回答，但我会尽力为您节省一些未来的“OpenMP with Visual Studio”经验。

Microsoft C/C++编译器仅支持OpenMP 2.0。由于OpenMP内置于编译器内核中，因此无法支持OpenMP 3.0或更高版本，并且不是附加软件包（除非有人提出了外部源到源转换引擎），而且Microsoft似乎不适用有兴趣在推动他们自己的解决方案时提供进一步的OpenMP支持（见下文）。因此，您应该获得与Visual Studio集成的英特尔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()算法，该算法专门设计用于使用正向迭代器。关于每个贴图元素的工作量的警告同样适用。

来源

2015-05-29 14:51:35

openMp：并行化std :: map迭代

回答

相关问题