矢量填充跨OpenMP线程

Question

我有一个算法,其中一个目标是填充向量.出于性能考虑,算法的迭代遍布OpenMP线程.我想知道哪种方式可以提供更好/更安全的填充向量的方法.

注意,向量的排序必须是一致的(即vec1的值n必须来自与vec2的值n相同的迭代.)

假设1:

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...

假设2:

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:这是从最佳方式将向量追加到向量

注2:似乎val1和val2可以组合在某个对象中以保持一致性并且仅与一个向量一起工作,但是现在对于算法的其余部分来说似乎是不切实际的.

注3:为了给出一个数量级,for循环包含在4个线程中分割的大约100次迭代.除了极少数例外情况,每次迭代都应该具有相同的工作负载(这会导致关键部分的问题在同一时间发生.)

注4:仅仅是为了记录,整个事情处理图像稳定,并在Tegra K1架构上运行.使用的编译器是gcc 4.8.4.

Answer 1

我假设您需要使用向量而不能使用数组（否则您的问题不是很有趣）。使用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)

有关并行填充向量的更多信息，请参阅此。有关在操作中合并线程的更多信息，请参阅此问题log2(t)的答案。