Избыточные вычисления при попытке распараллелить рекурсивную функцию с помощью OpenMP

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

Основная программа пытается вычислить вспомогательный граф, который является промежуточной структурой данных, необходимой для вычисления всех компонентов связности k-ребер графа.

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

Я попытался использовать сингл #pragma omp nowwait, но это привело только к последовательному выполнению кода.

Я попытался использовать cilk_spawn еще раз, но это привело только к тому, что моему компьютеру не хватило памяти. Я предполагаю, что было создано слишком много процессов.

Я извлек суть проблемы в минимальный рабочий пример, который прикрепляю ниже.

Приведенный ниже код повторяет каждое вычисление примерно восемь раз. Я предполагаю, что восемь разных процессов запускают отдельную копию программы вместо того, чтобы работать над частями проблемы одновременно.

#include <iostream>
#include <omp.h>
#include <numeric>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;

int foo(std::vector<int> V, int s){
    int n = V.size();

    if (n>1){
    std::cout<<n<<" ";
    std::random_device rd; // obtain a random number from hardware
    std::mt19937 eng(rd()); // seed the generator
    std::uniform_int_distribution<int> distr(0, n-1); // define the range
    int t = 1;

    auto first = V.begin();
    auto mid = V.begin() + (t);
    auto mid_1 = V.begin() + (t);

    std::vector<int> S(first, mid);
    std::vector<int> T(mid_1, V.end());

    #pragma omp parallel
    {
    #pragma omp task
    foo(S, s);
    #pragma omp task
    foo(T, t); 
    }
    }
   return 0;
}



int main(){
    std::vector<int> N(100);
    iota(N.begin(), N.end(), 0);
    int p = foo(N,0);
    return (0);
}

Моя цель состоит в том, чтобы все процессы/потоки работали вместе для завершения рекурсии.


c++ openmp parallel-processing cilk-plus
person Kofi Amanfu    schedule 26.04.2019    source источник
comment
Это попытается создать задачи на многих уровнях рекурсии. Добавьте переменную, отслеживающую вашу глубину, и появляйтесь только тогда, когда глубина мала. Также обратите внимание, что накладные расходы на синхронизацию при параллелизме будут препятствовать увеличению скорости, если только проблема не станет достаточно серьезной.   -  person Richard    schedule 26.04.2019
comment
@Richard, я рассмотрю предложение по отслеживанию глубины. Я считаю, что каждое вычисление достаточно велико. Основной цикл задачи вычисляет поток st_max между двумя вершинами графа.   -  person Kofi Amanfu    schedule 26.04.2019

Ответы (1)


arrow_upward
0
arrow_downward

Правильный способ применения параллелизма задач с OpenMP для вашего примера будет следующим.

int foo(std::vector<int> V, int s)
{
    int n = V.size();

    if (n > 1)
    {
        std::cout << n << " ";
        std::random_device rd;                              // obtain a random number from hardware
        std::mt19937 eng(rd());                             // seed the generator
        std::uniform_int_distribution<int> distr(0, n - 1); // define the range
        int t = 1;

        auto first = V.begin();
        auto mid = V.begin() + (t);
        auto mid_1 = V.begin() + (t);

        std::vector<int> S(first, mid);
        std::vector<int> T(mid_1, V.end());

        #pragma omp task
        foo(S, s);
        #pragma omp task
        foo(T, t);
    }
    return 0;
}

int main()
{
    std::vector<int> N(10000);
    std::iota(N.begin(), N.end(), 0);
    #pragma omp parallel
    #pragma omp single
    {
        int p = foo(N, 0);
    }
    return (0);
}

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

person Zulan    schedule 26.04.2019
comment
Спасибо @Зулан. Это сделало именно то, что я хотел. - person Kofi Amanfu; 26.04.2019