Рекурсивное факториальное поведение с задачами OpenMP?

Question

Мне интересно, каково поведение следующего кода. Это простая факторная программа, которая распараллеливается с использованием задач OpenMP. Когда я запускаю эту программу, я получаю 0 в качестве вывода. Мне известно о пропущенном предложении shared (b) . Вот как я называю факт из основного.

#pragma omp parallel
{
    #pragma omp single nowait
    {
        fact_result = fact(4);
    }
}

Вот фактическая факторная функция.

int fact(int n) {

    if(n == 0)
        return 1;

    int b = 0;

    #pragma omp task
    b = fact(n - 1);

    #pragma omp taskwait
    return n * b;

}

Я не могу понять, почему результат неверен без shared (b) и почему он верен с shared (b) . Я ищу диаграмму времени выполнения, подобную этой:

Я знаю, что потоки начинают работать над задачами, как только завершается шаг 1, но с чем они работают? Какие переменные? Они действительно что-то делают? Можем ли мы действительно ускорить рекурсивные вычисления, как это? Иногда в дереве много листьев, которые мы можем ускорить слияние, используя несколько потоков, но в этом случае в конце остается только 1 лист. Я действительно ценю, если кто-то может объяснить поведение этого кода. Заранее спасибо.

Answer 1

Я не могу понять, почему результат неверен

Атрибут совместного использования данных для b в задании равен firstprivate согласно стандартным правилам 2.15.1.1

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

Итак, логично, ваша задача выглядит так:

#pragma omp task
{
    int n_private = n;
    int b_private = b;
    b_private = fact(n_private - 1);
}

Результат первого частного b просто отбрасывается.

Можем ли мы действительно ускорить рекурсивные вычисления, подобные этой?

Нет *. У вас нет настоящего дерева - просто цепочка. Вы можете ускорить рекурсивные вычисления, только если у вас есть несколько дочерних узлов в некоторых узлах дерева.

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

Edit:

почему этот код работает путем добавления общего (б)

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

У меня проблемы с пониманием того, как работает задача. Это действительно ждет ВСЕХ задач в очереди, чтобы быть законченным?

Он ожидает завершения всех (прямых) дочерних задач. Поскольку дочерние задачи также ждут своих дочерних задач, в вашем случае это транзитивно даже для внуков.

Вы можете думать об этом так:

| time
V
fact(4)
*-----> fact(3)
twait   *-----> fact(2)
 |      twait   *-----> fact(1)
 |       |      twait   *-----> fact(0)
 |       |       |      twait   return
 |       |       |      done  
 |       |       |      return
 |       |      done
 |       |      return
 |      done
 |      return
done
return

Если да, то как выполняется промежуточная задача, такая как b = fact (3), в то время как ее результат еще не решен (потому что ее результат также ожидает в очереди!).

Это не так.