惯用的教堂方式造成分布不均

Question

我正在努力将分布式内存 Samplesort 从 MPI+C 移植到 Chapel，但我一直无法找到 idiomatic/clean 方法来 return 单个分布式数据中的排序数据数组。

C Samplesort 从每个 MPI 进程中调用，并传递一部分全局数据进行排序。这在 Chapel 中非常简单 - 我创建了一个块分布式数组，每个子域的所有者将适当的数据从磁盘读取到它的数组部分。

然后实际的 Samplesort 可以运行，数据在每个语言环境中均匀分布。困难的部分出现在排序的最后；由于数据是随机的，因此 Samplesort 为每个 Locale 分配了不均匀（但大致相似）的元素范围。也就是说，如果我在 P 节点上对 N 记录进行排序，则每个节点都以 N/ 开头P 条记录，但在洗牌后，有些可能最终会略多于 N/P 条记录。

在 MPI+C 中，这并不难处理 - 我知道每个进程将从所有其他进程接收多少元素，因此我可以在每个节点上动态分配足够的内存以接收来自其他过程。这在 Chapel 中也很容易实现——每个语言环境（需要一些簿记）都可以计算出需要从其他语言环境中获取多少条记录，因此它可以创建一个正确大小的本地数组。但是，为了使 API 方便且独立，我想将 Samplesort 过程传递给块分布式数组，并取回对另一个包含排序数据的块分布式数组的引用。

为此，我一直无法找到创建分布式数组的好方法，该数组将 space 分配给每个语言环境，以存储它们在结束时最终得到的不均匀数量的元素那种。 Chapel 中是否有内置的惯用方法？

我想出的最佳替代方法是填充一个分布式引用数组，每个区域设置一个，它指向大小不等的特定于区域设置的数组。但是，这看起来有点像 hack，因为您为 Samplesort 提供了一个数组，并且您收到了对其他数组的引用数组。

Answer 1

[抱歉回复晚了]

我们目前不在 Chapel 中提供 Block-like 的分布，但每个语言环境具有任意数量的元素（而不是 Block 采用的 n/p +/-1 方法） .过去，我们有一个用户在 Chapel 中实现了这样的分布（用户可以在 Chapel 中为数组编写自己的分布和布局）；但不幸的是，该代码没有回馈给该项目。如果您愿意支持我们创建和提供此类发行版，欢迎将其添加为 Chapel's GitHub issues page.

上的功能请求

如果在排序完成后保持不平衡负载对您的计算不重要，您可能会考虑的一种方法是简单地将结果 return 作为 block-distributed 数组，依靠Chapel 的全局地址 space 用于处理 non-local 访问。例如，如果我的语言环境使用大小为 [0..<myLocElems] 的缓冲区在逻辑上存储全局元素 [lo..#myLocElems]，我可以使用从缓冲区到全局数组的适当切片的赋值来将它们放在正确的位置，不管它们都是本地的还是一些（或全部）是远程的。

画出可能的样子：

proc CountingSort(InputArr: [?D] ?t) {
  // an array for the result
  //   (note that InputArr could potentially be re-used instead,
  //   depending on the interface you want)
  var ResultArr[D] t;

  coforall loc in Locales do on loc {
    var myLocElems: int;

    // ... start counting sort, determining `myLocElems`...

    var myBuff: [0..<myLocElems] t;  // a bucket for elements I receive
    const lo: int;                   // the global index of myBuff[0]

    // ... continue sort, filling myBuff and computing lo...

    // copy my elements to the appropriate place in the result array
    ResultArr[lo..#myLocElems] = myBuff; 
  }
  return ResultArr;
}

虽然这会引发一些与使用“不平衡块”分布有关的通信，该分布可以将所有 myBuff 存储到本地的分布式阵列中，但与费用相比，这种开销似乎很可能是噪音自己做那种事。使用 Block 的好处是 (a) 对数组的后续操作将是 load-balanced 和 (b) 可以使用 O(1) 数学找到任何元素的位置。

这并不是说“不平衡块”分布在某些情况下不会引起人们的兴趣。请注意，每个语言环境可能需要 O(numLocales) 内存来存储全局索引集的分区，并且需要 O(lg(numLocales)) 时间来确定任何给定元素所在的位置。但这些都不太可能成为当今系统的大问题。所以主要的缺点是它是一个尚未编写的发行版（尚未）。

惯用的教堂方式造成分布不均

Idiomatic Chapel Way to Create Uneven Distribution

chapel