跨 OpenMP 线程的向量填充

Question

我有一个算法，其一个目标是填充向量。为了提高性能，算法的迭代分布在 OpenMP 线程中。我想知道哪种方式可以提供 better/safer 填充向量的方式。

请注意向量的顺序必须一致（即 vec1 的值 n 必须来自与 vec2 的值 n 相同的迭代。）

假设一：

std::vector<BasicType> vec1;
std::vector<BasicType> vec2;
#pragma opm parallel for
for(...)
{
    // Do some intensive stuff to compute val1 and val2
    // ...

    #pragma omp critical
    {
        vec1.push_back(val1);
        vec2.push_back(val2);
    }
}
// Then go on to work with vec1 and vec2...

假设二：

std::vector<BasicType> vec1;
std::vector<BasicType> vec2;
#pragma opm parallel
{
    std::vector<BasicType> vec1local;
    std::vector<BasicType> vec2local;
    #pragma omp for
    for(...)
    {
        // Do some intensive stuff to compute val1 and val2
        // ...

        vec1local.push_back(val1);
        vec2local.push_back(val2);
    }

    #pragma omp critical
    {
        // See note 1 below
        vec1.insert(vec1.end(), vec1local.begin(), vec1local.end());
        vec2.insert(vec2.end(), vec2local.begin(), vec2local.end());
    }
}
// Then go on to work with vec1 and vec2...

注 1： 这是取自 Best way to append vector to vector

注2：似乎可以将val1和val2组合在某个对象中以保持一致性并仅使用一个向量，但目前看来其余部分不切实际算法。

注 3： 为了给出数量级，for 循环包含大约 100 次迭代，分布在 4 个线程中。除了极少数例外，每次迭代都应具有相同的工作负载（这带来了关键部分大约同时发生的问题。）

注 4： 仅作记录，整个过程涉及图像稳定，并在 Tegra K1 架构上运行。使用的编译器是 gcc 4.8.4.

Answer 1

从你的两个建议中，我更喜欢第一个。它更简单，不需要额外的内存。但是，我会建议没有 critical 部分的替代方案：

std::vector<BasicType> vec1(size);
std::vector<BasicType> vec2(size);
#pragma opm parallel for
for(...)
{
    // Do some intensive stuff to compute val1 and val2
    // ...

    vec1[i] = val1;
    vec2[i] = val2;
}

请注意，由于缓存行窃取，这可能会产生一些性能问题。但是，我不会担心这一点，除非事实证明这是一个通过实际性能分析验证的实际问题。解决方案可能是：

使用你的第二个解决方案。（这会消耗内存和额外的 post-处理）
Align your vector 并为循环使用适当的块。（这样每个线程都有本地缓存行）
使用内部包含局部向量但向外部提供必要的全局向量操作的数据结构。（这可能是总体上最好的解决方案。）

Answer 2

我将假设您需要使用向量而不能使用数组（否则您的问题不是很有趣）。使用 t = omp_get_num_threads()，您可以并行填充向量，然后将它们合并到 log2(t) 操作中，而不是 t 操作（就像您现在所做的那样）

void reduce(std::vector<BasicType> *v1, std::vector<BasicType> *v2, int begin, int end) {
    if(end - begin == 1) return;
    int pivot = (begin+end)/2;
    #pragma omp task
    reduce(v, begin, pivot);
    #pragma omp task
    reduce(v, pivot, end);
    #pragma omp taskwait
    v1[begin].insert(v1[begin].end(), v1[pivot].begin(), v1[pivot].end());
    v2[begin].insert(v2[begin].end(), v2[pivot].begin(), v2[pivot].end());
}

和

std::vector<BasicType> v1, v2;
std::vector<BasicType> *v1p, *v2p;
#pragma omp parallel
{
    #pragma omp single
    {
        v1p = new std::vector<BasicType>[omp_get_num_threads()];
        v2p = new std::vector<BasicType>[omp_get_num_threads()];
    }
    #pragma omp for
    for(...) {
        // Do some intensive stuff to compute val1 and val2
        // ...
       v1p[omp_get_thread_num()].push_back(val1);
       v2p[omp_get_thread_num()].push_back(val2);
    }
    #pragma omp single
    reduce(v1p, v2p, 0, omp_get_num_threads());
}
v1 = v1p[0], v2 = v2p[0];
delete[] v1p;
delete[] v2p;

例如，对于 8 个线程，这将加入线程的向量

(0,1) (2,3) (4,5) (6,7)
(0,2) (4,6)
(0,4)

有关并行填充向量的详细信息，请参阅 this. For more information about merging threads in log2(t) operations see the answer to 。

跨 OpenMP 线程的向量填充

Vector filling across OpenMP threads

c++

vector

std

openmp