划分四维笛卡尔网格并行处理

Question

我试图为给定的四维输入向量网格上的所有点计算一些函数(作为相当的计算-代价高昂的迭代算法)(网格是笛卡儿的，每个维上的等距点，由分段[a, b]指定，在这段上的点的等距数/常数步长-对于每个维(4总))。我们可以从“现实世界”的值中抽象出来，并将网格看作具有给定维度([5, 4, 3, 7]- 5x4x3x7笛卡尔网格)的4D数组，并在其上使用索引来引用某些切片/点。

我的计算算法以该向量(在指定的4D网格上)作为输入，并计算(可能在相当长的时间内)一些结果(不管它们是什么)。

我需要并行程序，以加快相当长的计算过程中的所有网格的顶点。所以我想把输入网格分割成子网格，每个网格上有尽可能多的点，以平衡不同线程/进程上的工作负载。

最简单的解决方案是在一个选择的维度上划分网格--但问题是，这个孤立维度上的片数可能少于“虚拟计算设备”的数量(使用中的不同线程/进程--我将它们称为VCD)。使用中的VCD数量是非常数的，等于我们需要的子网格数.所以我需要使用更多的维度来“分裂”-我认为使用2-3维(由于特定的输入-我们可以假设一些维度大于某个值)产生足够的切片来划分之间的VCD。

为了更好地解释，有个例子。我们在每个维度上都有四维网格大小的[2, 2, 10, 7]矢量。子网格数为20.所以我们不能用一个维度把它们分成20个部分，我们要把它们组合在一起。在这种情况下，我们很幸运地注意到，2,3维正好给出了2x10点=20个VCD。所以我们将网格划分为20 [2, 1, 1, 7]子网格(在2,3维上退化)，并将它们传递给VCD。

当没有一个维度产品除以没有剩余部分的VCD数量时，这就变得更加困难了，所以我们需要以某种方式分发它/我们需要使用更多的维度来分割。例如，VCD = [2, 3, 4, 5] = 11。

因此，问题是-如何将给定的笛卡尔4D-网格划分为N个子网格(网格上的点数大于N)，可能同时使用多个维度(假设某些维度(至少3)产生的切片大于N- dim[1] x dim[2] x dim[3] > N)。

我接受任何语言的答案，但C风格的伪代码更好。

编辑：正如Nico所指出的，我意识到我根本不需要分割网格。我知道序列化索引的诀窍(多亏了矩阵和堆实现)，但我被我的“多维”思维方式误导了。另外，我忘记指定网格上的计算是完全独立的。我最初要解决的问题是“如何将4D网格划分为并行处理”--建立一个序列化索引，并根据它在处理器之间将点划分成分段，这是一个明亮而简单的解决方案(但对我来说并不明显)。同样，这个答案也适用于N维网格。所以我学到的是-迭代(甚至并行)只需要一个维度，所以尝试序列化。

Answer 1

如果只是计算值(并且没有依赖项)，则根本不必在网格上工作。相反，将网格序列化为一维序列，并在处理器之间均匀地分配此序列。

最简单的序列化是：

i = x + dim[1] * (y + dim[2] * (z + dim[3] * w))

逆变换是：

x = i % dim[1]
y = (i / dim[1]) % dim[2]
z = (i / dim[1] / dim[2]) % dim[3]
w = (i / dim[1] / dim[2] / dim[3])