使用 OpenMP 在 Fortran 中并行化分支递归子例程时创建线程失败

Question

我正在用 Fortran 编写递归子例程，它扩展为二叉树（即过程调用自身两次，直到到达分支的末尾）。大致的算法逻辑是：

'''

call my_subroutine(inputs, output)
  use input to generate possible new_input(:,1) and new_input(:,2)
  do i=1,2
    call my_subroutine(new_input(:,i), new_output(i))
  enddo
  output = best(new_output(1), new_output(2))

'''

原则上，这可以通过并行计算大大加速，但是当我使用 OpenMP 并行化循环时，运行生成的可执行文件中止并出现错误：

libgomp：线程创建失败：资源暂时不可用线程创建失败：资源暂时不可用

我猜测堆栈大小太大，但我还没有找到解决方法或解决方法。有什么方法可以使用并行计算来提高这种算法的性能吗？

-OpenMP 或 gfortran 是否有帮助避免这些问题的选项？

-仅在树中特定级别之上或之下并行化是否有帮助？

-对于此应用程序，c 或 c++ 是更好的选择吗？

我正在使用 macOS Catalina。堆栈大小的上限为 65532。我的环境变量是：

OMP_NESTED=真

OMP_DYNAMIC=真

Answer 1

这听起来更像是您的代码由于非常深的递归而创建了太多线程。有一些方法可以减轻它。例如，OpenMP 4.5 引入了由 max-active-levels-var ICV（内部控制变量）控制的最大活动级别的概念。您可以通过设置 OMP_MAX_ACTIVE_LEVELS 环境变量或调用 omp_set_max_active_levels() 来设置它的值。一旦嵌套级别达到 max-active-levels-var 指定的级别，嵌套更深的并行区域将被停用，即它们将按顺序执行而不会产生新线程。

如果您的编译器不支持 OpenMP 4.5，或者如果您希望代码向后兼容旧版编译器，那么您可以通过跟踪嵌套级别和停用并行区域来手动完成。对于后者，有 if(b) 子句，当应用于并行区域时，仅当 b 计算为 .true. 时才激活它。您的代码的示例并行实现：

subroute my_subroutine(inputs, output, level)
  use input to generate possible new_input(:,1) and new_input(:,2)
!$omp parallel do schedule(static,1) if(level<max_levels)
  do i=1,2
    call my_subroutine(new_input(:,i), new_output(i), level+1)
  enddo
!$omp end parallel do
  output = best(new_output(1), new_output(2))
end subroutine my_subroutine

对 my_subroutine 的顶级调用必须使用等于 0 的 level。

无论您如何精确地实现它，您都需要试验最高级别的值。最佳值将取决于CPUs/cores的数量和代码的运算强度，并且会因系统而异。

parallel do 构造的更好替代方法是再次使用 OpenMP 任务，并在一定的嵌套级别进行截止。任务的好处是您可以预先固定 OpenMP 线程的数量，任务运行时将负责工作负载分配。

subroutine my_subroutine(inputs, output, level)
  use input to generate possible new_input(:,1) and new_input(:,2)
!$omp taskloop shared(new_input, new_output) final(level>=max_levels)
  do i=1,2
    call my_subroutine(new_input(:,i), new_output(i), level+1)
  end do
!$omp taskwait
  output = best(new_output(1), new_output(2))
end subroutine my_subroutine

在这里，循环的每次迭代都成为一个单独的任务。如果已达到 max_levels 嵌套，则任务变为 final，这意味着它们不会被延迟（即，将按顺序执行）并且每个嵌套任务也将是 final，从而有效地停止在递归树下进一步并行执行。任务循环是 OpenMP 4.5 中引入的一项便利功能。对于早期的编译器，以下等效代码将执行：

subroutine my_subroutine(inputs, output, level)
  use input to generate possible new_input(:,1) and new_input(:,2)
  do i=1,2
!$omp task shared(new_input, new_output) final(level>=max_levels)
    call my_subroutine(new_input(:,i), new_output(i), level+1)
!$omp end task
  end do
!$omp taskwait
  output = best(new_output(1), new_output(2))
end subroutine my_subroutine

任务代码中没有 parallel 结构。相反，您需要从并行区域内调用 my_subroutine，惯用的方法是这样做：

!$omp parallel
!$omp single
  call my_subroutine(inputs, output, 0)
!$omp end single
!$omp end parallel

嵌套并行版本与使用任务的版本之间存在根本区别。在前一种情况下，在每个递归级别，当前线程一分为二，每个线程并行执行一半的计算。此处需要限制活动并行级别，以防止运行时生成过多线程并耗尽系统资源。在后一种情况下，在每个递归级别创建两个新任务并延迟以供稍后执行，可能由与并行区域关联的线程组并行执行。线程数保持不变，这里的截止限制了任务开销的累积，这比产生新的并行区域的开销要小得多。因此，任务代码的最佳值 max_levels 将与嵌套并行代码的最佳值大不相同。

使用 OpenMP 在 Fortran 中并行化分支递归子例程时创建线程失败

Failed thread creation when parallelizing a branching recursive subroutine in Fortran with OpenMP

parallel-processing

recursion

performance

fortran

openmp