使用OpenMP并行化此递归的最佳方法

Question

我有以下递归函数（注意：它删除了所有不重要的细节）

int recursion(...) {

  int minimum = INFINITY;
  for(int i=0; i<C; i++) {
      int foo = recursion(...);

      if (foo < minimum) {
          minimum = foo;
      }
  }

  return minimum;
}

注意2：这是有限的，但在此简化示例中不是，所以请忽略它。这个问题的重点是如何正确地解决这个问题。

我当时正在考虑使用任务，但是我不确定如何正确使用它-如何使内部循环并行化。

编辑1：递归树不平衡。它与动态编程方法一起使用，因此随着时间的流逝，很多值会在以前的过程中重复使用。这让我很担心，我认为这将是一个很大的瓶颈。

C在20左右。

最好的指标是最快的:)

它将在2x Xeon上运行，因此有足够的硬件电源可用。

Answer 1

是的，您可以使用OpenMP任务在多个递归级别上利用并行性，并确保不平衡不会导致浪费的周期。

我将在中收集结果vector并计算最小的外部。您还可以在任务内执行受保护的（关键/锁定）最小计算。

如果您在递归中太深，则避免产生任务/分配内存，因为递归/工作比率太差了。最强大的解决方案是创建两个单独的（并行/串行）递归函数。这样，一旦切换到串行函数，您的运行时开销为零-与每次在统一函数中对照阈值检查递归深度相反。

int recursion(...) {
    #pragma omp parallel
    #pragma omp single
    return recursion_par(..., 0);
}

int recursion_ser(...) {
    int minimum = INFINITY;
    for(int i=0; i<C; i++) {
        int foo = recursion_ser(...);
        if (foo < minimum) {
            minimum = foo;
        }
    }
    return minimum;
}

int recursion_par(..., int depth) {
    std::vector<int> foos(C);
    for(int i=0; i<C; i++) {
        #pragma omp task
        {
            if (depth < threshhold) {
                foos[i] = recursion_par(..., depth + 1);
            } else {
                foos[i] = recursion_ser(...);
            }
        }
    }
    #pragma omp taskwait
    return *std::min_element(std::begin(foos), std::end(foos));
}

显然，您不得在不重要的细节内对全局/共享状态进行任何令人讨厌的事情。