Векторное заполнение в потоках OpenMP

Question

Векторное заполнение в потоках OpenMP

У меня есть алгоритм, для которого одна цель-заполнить векторы. Для повышения производительности итерации алгоритма распределяются по потокам OpenMP. Мне было интересно, какой способ обеспечит лучший/безопасный способ заполнения векторов.

Обратите внимание, что порядок векторов должен быть последовательным (т. е. значение n век1 должно исходить из той же итерации, что и значение n век2.)

Гипотеза 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 содержит около 100 итераций, разбитых на 4 потока. За исключением очень немногих исключений, ожидается, что каждая итерация будет иметь та же рабочая нагрузка (что приводит к тому, что проблема критических разделов происходит примерно в одно и то же время.)

примечание 4: только для записей, все это имеет дело со стабилизацией изображения и работает на архитектуре Tegra K1. Используемый компилятор-gcc 4.8.4.

754 2

c++vector std

2 ответов:

Comments

Ничего не найдено.

Z boson · Accepted Answer · 2017-05-23 14:55:19

Я предполагаю, что вам нужно использовать вектор и нельзя использовать массив (в противном случае ваш вопрос не очень интересен). Используя 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 . Для большего информацию о слиянии потоков в операциях log2(t) смотрите в ответе на этот вопрос.

Zulan · Accepted Answer · 2017-05-23 13:33:53

Из ваших двух предложений я бы предпочел первое. Он проще и не требует дополнительной памяти. Однако я бы предложил альтернативу без раздела 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;
}
Обратите внимание, что это может иметь некоторые проблемы с производительностью из-за кражи строки кэша. Однако я бы не беспокоился об этом, если бы это не оказалось реальной проблемой, подтвержденной фактическим анализом производительности. Тогда решение может быть следующим:

переходите ко второму решению. (что стоит памяти и дополнительная постобработка)

выровняйте вектор и используйте соответствующие фрагменты для цикла. (таким образом, что каждый поток имеет локальные строки кэша)

используйте структуру данных, которая внутренне содержит локальные векторы, но вовне обеспечивает необходимые глобальные вектор-операции. (Это, вероятно, в целом лучшее решение.)