划分4D笛卡尔网格进行并行处理
Divide 4D cartesian grid for parallel processing
我正在尝试为 4D 输入向量的给定网格上的所有点计算一些函数（作为计算成本很高的迭代算法实现）（网格是笛卡尔坐标，每个维度上的点等距，由段指定 [a, b] 和该段/恒定步长上等距点的数量 - 对于每个维度（总共 4 个））。我们可以从 "real-world" 值中抽象出来，并将网格视为具有给定维度的 4D 数组（[5, 4, 3, 7] - 5x4x3x7 笛卡尔网格）并在它们上使用索引 - 用于引用一些 slices/points.
我的计算算法将该向量（指定 4D 网格上的点）作为输入并计算（可能在相当长的时间内）一些结果（它们是什么并不重要）。
我需要并行化程序以加速对所有网格顶点的相当长的计算过程。所以我想将输入网格拆分为子网格，每个网格上的点数尽可能接近，以平衡不同 threads/processes.
上的工作负载
最简单的解决方案是在 1 个选定的维度上划分网格 - 但问题是，这个孤立维度上的切片数量可能少于 "virtual computing devices"（不同的 threads/processes 使用 -我将它们称为 VCD）。使用的 VCD 数量是非常数，等于我们需要的子网格数量。所以我需要为 "splitting" 使用更多维度 - 我认为使用 2-3 维度（由于特定输入 - 我们可以假设某些维度大于某些值）产生足够的切片来划分 VCD。
为了更好地解释，请举个例子。我们在每个维度上都有 [2, 2, 10, 7] 个 4D 网格大小的向量。子网格的数量是 20。所以我们不能将其中一个维度分成 20 个部分，我们必须以某种方式将它们组合起来。在这种情况下，我们很幸运地注意到 2,3 维恰好给出了 2x10 点 = 20 VCD。所以我们只是将网格拆分为 20 [2, 1, 1, 7] 个子网格（在 2,3 维上退化）并将它们传递给 VCD。
none维度产品除以VCD张数不留余数就比较难了，所以需要分配somehow/we需要用到更多的维度一起拆分。例如，[2, 3, 4, 5] for VCD count = 11.
所以，问题是 - 如何将给定的笛卡尔 4D 网格拆分为 N 个子网格（网格上的点数大于 N），可能同时使用多个维度（可以假设某些维度的互补条件（至少 3 个）产生比 N 多的切片 - dim[1] x dim[2] x dim[3] > N)
我接受任何语言的回答，但最好使用 C 风格的伪代码。
编辑：正如 Nico Schertler 指出的那样，我意识到我根本不需要拆分网格。我知道序列化索引的技巧（多亏了矩阵和堆的实现），但我被 "multi-dimensional" 的思维方式误导了。另外，我忘了指定网格上的计算是完全独立的。我最初必须解决的问题是 "How to divide 4D-grid for parallel processing" - 建立一个序列化索引并根据它在处理器之间将点序列分成多个段是一个聪明而简单的解决方案（但对我来说并不明显）。此外，这个答案也适合 N 维网格。
所以我学到的教训是 - 迭代（甚至并行）只需要一个维度，所以尝试序列化。
如果只是计算值（并且没有依赖关系），则根本不必在网格上工作。相反，将网格序列化为一维序列并将该序列均匀分布在处理器之间。
最简单的序列化是：
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])
我正在尝试为 4D 输入向量的给定网格上的所有点计算一些函数（作为计算成本很高的迭代算法实现）（网格是笛卡尔坐标，每个维度上的点等距，由段指定 [a, b] 和该段/恒定步长上等距点的数量 - 对于每个维度（总共 4 个））。我们可以从 "real-world" 值中抽象出来，并将网格视为具有给定维度的 4D 数组（[5, 4, 3, 7] - 5x4x3x7 笛卡尔网格）并在它们上使用索引 - 用于引用一些 slices/points.
我的计算算法将该向量（指定 4D 网格上的点）作为输入并计算（可能在相当长的时间内）一些结果（它们是什么并不重要）。
我需要并行化程序以加速对所有网格顶点的相当长的计算过程。所以我想将输入网格拆分为子网格，每个网格上的点数尽可能接近，以平衡不同 threads/processes.
上的工作负载最简单的解决方案是在 1 个选定的维度上划分网格 - 但问题是，这个孤立维度上的切片数量可能少于 "virtual computing devices"（不同的 threads/processes 使用 -我将它们称为 VCD）。使用的 VCD 数量是非常数，等于我们需要的子网格数量。所以我需要为 "splitting" 使用更多维度 - 我认为使用 2-3 维度（由于特定输入 - 我们可以假设某些维度大于某些值）产生足够的切片来划分 VCD。
为了更好地解释，请举个例子。我们在每个维度上都有 [2, 2, 10, 7] 个 4D 网格大小的向量。子网格的数量是 20。所以我们不能将其中一个维度分成 20 个部分，我们必须以某种方式将它们组合起来。在这种情况下，我们很幸运地注意到 2,3 维恰好给出了 2x10 点 = 20 VCD。所以我们只是将网格拆分为 20 [2, 1, 1, 7] 个子网格（在 2,3 维上退化）并将它们传递给 VCD。
none维度产品除以VCD张数不留余数就比较难了，所以需要分配somehow/we需要用到更多的维度一起拆分。例如，[2, 3, 4, 5] for VCD count = 11.
所以，问题是 - 如何将给定的笛卡尔 4D 网格拆分为 N 个子网格（网格上的点数大于 N），可能同时使用多个维度（可以假设某些维度的互补条件（至少 3 个）产生比 N 多的切片 - dim[1] x dim[2] x dim[3] > N)
我接受任何语言的回答，但最好使用 C 风格的伪代码。
编辑：正如 Nico Schertler 指出的那样，我意识到我根本不需要拆分网格。我知道序列化索引的技巧（多亏了矩阵和堆的实现），但我被 "multi-dimensional" 的思维方式误导了。另外，我忘了指定网格上的计算是完全独立的。我最初必须解决的问题是 "How to divide 4D-grid for parallel processing" - 建立一个序列化索引并根据它在处理器之间将点序列分成多个段是一个聪明而简单的解决方案（但对我来说并不明显）。此外，这个答案也适合 N 维网格。 所以我学到的教训是 - 迭代（甚至并行）只需要一个维度，所以尝试序列化。
如果只是计算值（并且没有依赖关系），则根本不必在网格上工作。相反，将网格序列化为一维序列并将该序列均匀分布在处理器之间。
最简单的序列化是：
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])