使用 MPI 在三角矩阵上进行 for 循环迭代的分布

Question

我有一个 MPI 和 openMP 程序，可以计算粒子之间的一些相互作用。在此过程中，我有一个粒子 i 和 j 之间可能相互作用的对称矩阵 A，我必须循环遍历该矩阵。因此，我将 n x n 矩阵拆分为相同大小的列，并将每个部分发送给不同的 MPI 进程处理。然后，分割的各个列由 openMP 在本地进行处理。 Fortran 循环的工作原理如下：

1. 第一个循环遍历分割中的不同列；
2. 然后它查看给定列的 kd 树，并仅保留相关的交互；
3. 然后它循环这些交互作用，如果与此交互作用相关的索引不在下三角矩阵中（利用 $A_{ij}=A_{ji}$ 的对称性），那么它会循环。

这是一些伪代码来理解：

iter_per_rank = n/n_ranks

if ( mod(n, n_ranks) > 0 ) then
    iter_per_rank = iter_per_rank + 1
end if

first_iter = rank * iter_per_rank + 1
last_iter = first_iter + iter_per_rank - 1

!$omp start
do i = last_iter, first_iter, -1
    idx = search%kdtree(array(i))
    do k = 1, size(idx%i%values) -1
        j = idx%i%values(k+1)

        if (i .ge. j) then
            cycle
        end if

        [...]

    end do
end do
!$omp end

call mpi_comms(...)

我遇到的问题是，当这段代码运行时，由于矩阵 A 的粗略（相等）分离，并非所有核心都一直在使用。如果我要遍历所有索引，那就没问题了，但因为我有了这个 kd 树和矩阵的对称性，这些实际上使初始分离发生偏差，使得最后分割中的列比第一个分割中的列更早地完成其计算部分。

因此，我的问题是：如果给出第一列中相关索引的最大数量的估计，是否可以进行更好的分割（比统一分割）？

我想到的是，第一次分割会很小，然后随着我们从一个流程到另一个流程，稳步增加到更大的分割。

我还没有尝试任何东西，我希望有人对如何做到这一点有一个好主意。

Answer 1

原则上，

schedule(dynamic)

子句是不平衡迭代的解决方案：

!$OMP PARALLEL DO SCHEDULE(DYNAMIC)
do i = n, 1, -1
   ...
end do
!$OMP END PARALLEL DO

然而，在实践中，动态调度比静态默认调度成本更高，并且根据实际工作负载，其效率可能更高或更低。如果您有一个实现最新 OpenMP 功能的编译器，您可以测试

nonmonotonic

修饰符，该修饰符应该能够充分利用静态和动态调度：

SCHEDULE(NONMONOTONIC:DYNAMIC)

。您还可以调整块大小（默认为 1，但较大的块可能会有所帮助...或没有）：

SCHEDULE(DYNAMIC,10)

Tasks 是解决此问题的另一种方法，但它们的效率可能更高或更低，具体取决于实际计算： !$OMP 并行 !$OMP 单人 我 = n, 1, -1 !$OMP 任务 ... !$OMP 结束任务 结束做 !$OMP 结束单曲 !$OMP 结束并行

With tasks, you have to be especially careful about the shared/private status of the variables, but to go further some real code would be needed.