OpenMP 并行递归与分支

Question

我正在尝试使用 OpenMP 加快计算速度，但我不确定并行化是否适用于分支。

这是代码（删除了不必要的部分）：

if (flag) {
    int val;
    for (int i = 0; i < size; i ++) {
       val = 2 + recursion(i, flag = 0));
    }
    return val;
} else {
    int val;
    for (int i = 0; i < size; i ++) {
       val = 1 + recursion(i, flag = 1);
    }
    return val;
}

我不知道如何并行化这个函数。

Answer 1

这种情况下的一般策略是跟踪递归深度，并仅在第一次调用函数时应用循环的条件并行化。

问题中的代码不完整，甚至没有意义（例如

val

仅从最后一次迭代确定）。所以我采用了它的工作变体（并且是 Fortran 语言）。

我首先尝试：

integer recursive function recursion(size,flag,depth) result(val)
USE OMP_LIB
implicit none
integer, intent(in) :: size, depth
logical, intent(in) :: flag

integer :: i, addval

val = 0
addval = 1; if (flag) addval = 2

!$OMP PARALLEL DO REDUCTION(+:val) SCHEDULE(DYNAMIC,1) IF(depth==0)
do i = 0, size-1
   val = val + addval + recursion(i, .not. flag, depth+1)
end do
!$OMP END PARALLEL DO

end function


program recurtest
USE OMP_LIB
implicit none

integer :: i
integer :: N = 28
double precision :: tic, toc
integer, external :: recursion

tic = omp_get_wtime()
    write(*,*) recursion(N,.false.,0)
toc = omp_get_wtime()
write(*,*) toc-tic

end program

但是性能很糟糕，比顺序版本慢得多。所以我复制了这样的代码，效果更好：

if (depth==0) then
    !$OMP PARALLEL DO REDUCTION(+:val) SCHEDULE(DYNAMIC,1)
    do i = 0, size-1
        val = val + addval + recursion(i, .not. flag, depth+1)
    end do
    !$OMP END PARALLEL DO
else
    do i = 0, size-1
        val = val + addval + recursion(i, .not. flag, depth+1)
    end do
end if

完全顺序（初始调用时深度=1，因此永远不会使用并行部分）：

N=          28 result=   402653182
runtime=   2.1809919998049736    

使用 2 个线程运行：

 N=          28 result=   402653182
 runtime=   1.4617079999297857     

以 4 个线程运行：

 N=          28 result=   402653182
 runtime=   1.2100369995459914     

4 个线程上的加速甚至不到 2 倍。问题在于，在这种情况下，迭代之间的工作负载高度不平衡。

SCHEDULE(DYNAMIC,1)

有很大帮助（否则根本没有加速），但很可能使用更多线程不会获得进一步的加速。通过修改示例以实现平衡迭代（使用

size-1

而不是 `i 调用递归，但结果当然不同......）我在 4 个线程上获得了 3 倍的加速（并且它可能会在上面更好地扩展） 4 个线程）。

（用gfortran 12编译）

编辑

我提出了另一个版本，考虑到最后一次迭代具有迄今为止最高的工作负载。

size-1

第一次迭代在第一次调用时并行化，并且递归不会进一步并行化。最后一次迭代在下一个递归级别并行化。最初的通话是

omp=.true.

integer recursive function recursion2(size,flag,omp) result(val)
USE OMP_LIB
implicit none
integer, intent(in) :: size
logical, intent(in) :: flag, omp

integer :: i, addval

val = 0
addval = 1; if (flag) addval = 2

if (omp) then
    !$OMP PARALLEL DO REDUCTION(+:val) SCHEDULE(DYNAMIC,1)
    do i = 0, size-2
        val = val + addval + recursion2(i, .not. flag, .false.)
    end do
    !$OMP END PARALLEL DO
    if (size-1 >= 0) val = val + addval + recursion2(size-1, .not. flag, .true.)
else
    do i = 0, size-1
        val = val + addval + recursion2(i, .not. flag, .false.)
    end do
end if

end function

速度提升不是很好，但线程数越多，提升的机会就越大。有 4 个线程：

 N=          28 result=   402653182
 runtime=   1.1320059997960925