OpenMP任务的递归因子行为？

Question

我想知道以下代码的行为是什么.这是一个使用OpenMP任务并行化的简单因子程序.当我运行这个程序时,输出为0.我知道缺少共享(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;

}

我不明白为什么没有共享(b)结果是错误的,为什么它与共享(b)是正确的.我正在寻找这样的运行时图:

我知道,一旦第1步完成,线程就会开始处理任务,但是他们正在使用什么？什么变数？他们真的在做什么吗？我们真的能加速像这样的递归计算吗？有时在树中有足够的叶子,我们可以使用多个线程加速合并操作,但在这种情况下,最后只有一片叶子.如果有人能解释这段代码的行为,我真的很感激.提前致谢.

Answer 1

我无法理解为什么结果不正确

对于数据共享属性b的任务是firstprivate按照标准规定2.15.1.1

在任务生成构造中,如果不存在缺省子句,则上述规则未确定数据共享属性的变量是firstprivate.

从逻辑上讲,你的任务看起来像这样:

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

firstprivate的结果b刚刚被丢弃.

我们真的能加速像这样的递归计算吗？

没有*.你没有真正的树 - 只是一个链.如果树中某些节点上有多个子节点,则只能加速递归计算.

*:如果每个节点上有大量工作,并且该工作的某些部分不依赖于递归调用,则可以进行一些流水线操作.

编辑:

为什么这段代码通过添加共享(b)来工作

因为那时结果fact不会被丢弃并b从外部范围写入变量.

我在理解taskwait的工作方式时遇到了问题.那真的等待队列中的所有任务完成吗？

它等待所有(直接)子任务完成.因为孩子的任务也在等待他们的孩子任务,所以即使对于孙子女来说,它也是可以传递的.

你可以这样想:

| 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)这样的中间任务,而其结果尚未解决(因为它的结果也在taskwait等待!).

不是.