C++ OpenMP Parallel For Loop - 替代std :: vector

Question

基于这个线程,OpenMP和STL向量,哪些数据结构是并行for循环中共享 std :: vector的好选择？主要方面是速度,矢量可能需要在循环期间调整大小.

Answer 1

我认为你可以std::vector在大多数时间使用OpenMP并且仍然具有良好的性能.例如,以下代码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,然后将它们串行合并到并行区域之外.我在这里了解了这个"技巧" .对于用户定义的缩减,我不确定如何做到这一点(或者甚至可能)..用户定义的缩减不可能做到这一点.

我刚刚意识到关键部分是不必要的,我从这个问题中找到了parallel-cumulative-prefix-sums-in-openmp-communic-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;

Answer 2

您链接的问题是在"多个线程写入单个容器的情况下,STL向量容器不是线程安全的"这一事实.如果您调用可能导致重新分配std::vector持有的基础数组的方法,那么这只是正确的说法.push_back(),pop_back()并且insert()是这些危险方法的例子.

如果您需要线程安全重新分配,那么库intel线程构建块为您提供并发向量容器.您不应该在单线程程序中使用tbb :: concurrent_vector,因为访问随机元素所花费的时间高于std :: vector执行相同操作所需的时间(即O(1)).然而,并发矢量电话push_back(),pop_back(),insert()在一个线程安全的方式,甚至当再分配发生.

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

编辑2:顺便说一句,如果你开始使用英特尔Tread Building Block(它是开源的,它适用于大多数编译器,它与C++/C++ 11功能集成得比openmp好得多),那么你不需要使用openmp创建parallel_for,这是使用tbb的parallel_for的一个很好的例子.