Chapel 中的正交递归二分法（Barnes-Hut 算法）

Question

我正在 Chapel 中实现 Barnes-Hut n 体模拟的分布式版本。我已经实现了在我的 GitHub.

上可用的顺序和共享内存版本

我遵循概述的算法 here（第 7 章）：

执行正交递归二分法并分配主体，使每个进程的工作量相等
在每个进程上构造局部基本树
计算力和前进体

我非常清楚如何在 C/MPI 中使用 MPI_Allreduce 进行二分法和简单的消息传递以进行进程间通信（用于正文传输）来实现算法。而且 MPI_Comm_split 是一个非常方便的函数，它允许我在 ORB 的每个步骤拆分进程。

我在使用 Chapel 提供的 parallel/distributed 构造执行 ORB 时遇到了一些问题。我需要一些方法来汇总（减少）跨进程（Chapel 中的区域设置）的工作，将进程分成组，并将进程到进程的通信传递给主体。

对于如何在 Chapel 中实现这一点的任何建议，我将不胜感激。如果另一种方法对教堂更好，那也很好。

Answer 1

在经历了很多死锁和崩溃之后，我确实设法在 Chapel 中实现了算法。可以在这里找到：https://github.com/novoselrok/parallel-algorithms/tree/75312981c4514b964d5efc59a45e5eb1b8bc41a6/nbody-bh/dm-chapel

我无法使用 Chapel 提供的许多 fancy 并行设备。我只依赖于具有 sync 元素的块分布式数组。我还复制了 SPMD 模型。

在 main.chpl 中，我设置了所有用于传输数据的必要数组。每个数组都有对应的sync数组用于同步。然后每个工人都从其身体份额和前面提到的数组开始。 Worker.chpl 包含大部分算法。

我用自定义函数 determineGroupPartners 替换了 MPI_Comm_split 功能，我手动执行相同的操作。至于 MPI_Allreduce 我发现了一个可以随处使用的漂亮小模式：

var localeSpace = {0..#numLocales};
var localeDomain = localeSpace dmapped Block(boundingBox=localeSpace);

var arr: [localeDomain] SomeType;
var arr$: [localeDomain] sync int; // stores the ranks of inteded receivers
var rank = here.id;

for i in 0..#numLocales-1 {
    var intendedReceiver = (rank + i + 1) % numLocales;
    var partner = ((rank - (i + 1)) + numLocales) % numLocales;

    // Wait until the previous value is read
    if (arr$[rank].isFull) {
        arr$[rank];
    }

    // Store my value
    arr[rank] = valueIWantToSend;
    arr$[rank] = intendedReceiver;

    // Am I the intended receiver?
    while (arr$[partner].readFF() != rank) {}

    // Read partner value
    var partnerValue = arr[partner];

    // Do something with partner value

    arr$[partner]; // empty

    // Reset write, which blocks until arr$[rank] is empty
    arr$[rank] = -1;
}

这是一种实现 FIFO 通道的复杂方法（请参阅 Julia RemoteChannel，我从中获得了此 "pattern" 的灵感）。概述：

首先，每个语言环境计算其预期接收者及其伙伴（语言环境将从中读取值）
区域设置检查是否读取了先前的值
Locales 通过将 arr$[rank] 设置为预期的接收者
Locale 等待其合作伙伴设置值并设置适当的预期接收者
一旦语言环境成为预期的接收者，它就会读取伙伴值并对其进行一些操作
然后 locale empties/unlocks 通过读取值 arr$[partner]
最后它通过写入 -1 重置其 arr$[rank]。通过这种方式，我们还可以确保预期的接收者读取了语言环境设置的值

我意识到对于这个问题，这可能是一个过于复杂的解决方案。可能存在一种更适合 Chapels 的并行计算全局观点的算法。我实现的算法适用于 SPMD 计算模型。

话虽如此，我认为 Chapel 仍然做得很好 [=74=]。 Here 是针对 Julia 和 C/MPI 的性能基准。随着进程数量的增加，性能会提高很多。我没有机会运行在具有 >4 个节点的集群上进行基准测试，但我认为 Chapel 最终会获得可观的基准测试。

Chapel 中的正交递归二分法（Barnes-Hut 算法）

Orthogonal Recursive Bisection in Chapel (Barnes-Hut algorithm)

parallel-processing

chapel