C++ OpenMP并行循环 - std::vector的替代方案

Question

C++ OpenMP并行循环 - std::vector的替代方案

c++openmpstd

22

基于这个线程，OpenMP和STL向量，在并行for循环中，有哪些数据结构可以替代共享的std:: vector？主要方面是速度，并且在循环期间可能需要调整向量大小。

- Armin Meisterhirn

3

展示一些代码，描述你的具体情况...向量中将存储什么？你的循环将如何处理它？很可能使用std::vector是完全安全的。 - LihO

如链接串中所说，您只需要注意在循环中调整向量大小并可能重新分配时不要使用std::vector。如果您只是更改对象，则可以完全正常使用它。您能详细说明一下您的要求以及为什么vector不适合您的需求吗？ - SinisterMJ

我认为只有当std::vector是共享的时候才会出现问题。如果它是私有的，那么使用push_back或resize应该没有问题。 - Z boson

2个回答

17

该链接中讨论了“在多个线程写入单个容器的情况下，STL向量容器不是线程安全的”这一事实。只有在调用能够导致底层数组重新分配的方法时，才会出现这种情况，如std::vector所持有的push_back()，pop_back()和insert()等危险方法。如果需要线程安全的重新分配，则库intel thread building block提供了concurrent vector containers。您不应该在单线程程序中使用tbb::concurrent_vector，因为访问随机元素所需的时间比std::vector执行相同操作所需的时间长（即O(1)）。但是，concurrent vector以线程安全的方式调用push_back()，pop_back()和insert()，即使发生重新分配也是如此。

编辑1：以下英特尔演示文稿的幻灯片46和47给出了使用tbb::concurrent_vector进行并发重新分配的说明性示例。

编辑2：顺便提一下，如果你开始使用英特尔线程构建块（它是开源的，适用于大多数编译器，并且比openmp更好地集成了C++/C++11功能），那么你不需要使用openmp来创建parallel_for，这里有一个使用tbb的不错的parallel_for示例。

- Vivian Miranda

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

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

- Z boson · Accepted Answer

我认为大部分情况下你可以使用带有OpenMP的std::vector，同时仍然保持良好的性能。以下代码示例并行地填充std::vectors，然后在最后将它们合并。只要你的主循环/填充函数是瓶颈，这通常应该能够很好地工作并且是线程安全的。

std::vector<int> vec;
#pragma omp parallel
{
    std::vector<int> vec_private;
    #pragma omp for nowait //fill vec_private in parallel
    for(int i=0; i<100; i++) {
        vec_private.push_back(i);
    }
    #pragma omp critical
    vec.insert(vec.end(), vec_private.begin(), vec_private.end());
}

编辑：

OpenMP 4.0 允许使用#pragma omp declare reduction定义用户自定义的缩减操作符。以上代码可以简化为以下形式：

#pragma omp declare reduction (merge : std::vector<int> : omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end()))

std::vector<int> vec;
#pragma omp parallel for reduction(merge: vec)
for(int i=0; i<100; i++) vec.push_back(i);

编辑：到目前为止，我展示的内容并没有按顺序填充向量。如果顺序很重要，那么可以像这样完成。

std::vector<int> vec;
#pragma omp parallel
{
    std::vector<int> vec_private;
    #pragma omp for nowait schedule(static)
    for(int i=0; i<N; i++) { 
        vec_private.push_back(i);
    }
    #pragma omp for schedule(static) ordered
    for(int i=0; i<omp_get_num_threads(); i++) {
        #pragma omp ordered
        vec.insert(vec.end(), vec_private.begin(), vec_private.end());
    }
}

这可以避免每个线程保存一个 std::vector，然后在并行区域外串行地合并它们。我从这里了解到了这个"技巧"here。对于用户定义的约简操作，我不确定如何做到这一点（或者是否可能）。对于用户定义的约简操作，这是不可能的。

我刚意识到临界区并不必要，我从这篇文章中找到了答案parallel-cumulative-prefix-sums-in-openmp-communicating-values-between-thread。这种方法也正确排序。

std::vector<int> vec;
size_t *prefix;
#pragma omp parallel
{
    int ithread  = omp_get_thread_num();
    int nthreads = omp_get_num_threads();
    #pragma omp single
    {
        prefix = new size_t[nthreads+1];
        prefix[0] = 0;
    }
    std::vector<int> vec_private;
    #pragma omp for schedule(static) nowait
    for(int i=0; i<100; i++) {
        vec_private.push_back(i);
    }
    prefix[ithread+1] = vec_private.size();
    #pragma omp barrier
    #pragma omp single 
    {
        for(int i=1; i<(nthreads+1); i++) prefix[i] += prefix[i-1];
        vec.resize(vec.size() + prefix[nthreads]);
    }
    std::copy(vec_private.begin(), vec_private.end(), vec.begin() + prefix[ithread]);
}
delete[] prefix;