c++ - 跨 OpenMP 线程的 vector 填充

Question

我有一个算法，其一个目标是填充 vector 。为了提高性能，算法的迭代分布在 OpenMP 线程中。我想知道哪种方式可以提供更好/更安全的载体填充方式。

请注意， vector 的顺序必须一致(即 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 可以在某个对象中组合以保持一致性并仅使用一个 vector ，但目前对于算法的其余部分来说似乎不切实际。

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

注意 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;
}

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

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