0

我有一个 n 平方循环，我想将其分成块以同时运行。循环如下所示：

for i = n to m
    for j = i to m
       // Do something

根据评论编辑： n = 0，m = 60000 的具体示例：

for i = 0 to 60000
  for j = i to 60000

所以，我并没有真正进行 n 平方迭代，而是 n 平方 / 2。随着 i 变大，内部外观中的迭代次数变得更少。

假设 n = 0 和 m = 60000，我想将其分解为 5 个单独的进程以并行运行。如何选择 n 和 m 以使 5 个不同的过程具有相等的迭代？

我知道 60000 / 5 = 12000。所以，我们可以这样分解：

0 - 11999
12000 - 23999
24000 - 35999
36000 - 47999
48000 - 60000

想法是将其分解为具有相同迭代次数的 x 个循环（此处 x 为 5）。像这样的东西：

for i = 0 to 11999
    for j = i to 60000

for i = 12000 to 23999
    for j = i to 60000

for i = 24000 to 35999
    for j = i to 60000

for i = 36000 to 47999
    for j = i to 60000

for i = 48000 to 60000
    for j = i to 60000

但是，最后的循环将进行较少的比较。所以，这不是正确的答案。

似乎这是一个微积分问题，您需要计算出曲线下的相等面积。但是，这个数学对我来说已经生疏了大约 20 年。当然，我正在寻找一个给定 n = 0 和 m > 0 的通用解决方案。

编辑2： 澄清上述问题。

谢谢

4

2 回答 2

2

下面是我如何用一种语言编写嵌套循环，例如 Fortran 或 Matlab，它允许指定循环的步幅。我希望这可以用循环翻译成大多数其他编程语言。

我假设您的并发程序分布在线程（或进程，哪个无关紧要）中，并且有一个函数num_pids返回计算中的进程数和另一个函数 , my_pid，它返回整数范围0..num_pids-1。

然后，在伪 Fortran 中我会写

do i = my_pid, m, num_pids
    do j = i, m
    ....
    end do
end do

将三连音解释my_pid, m, num_pids为from my_pid to m in steps of num_pids. 这不会提供完全平衡的负载，但平衡对于大多数用途来说应该足够好。

于 2013-05-23T15:37:43.053 回答
1

内部循环中的迭代次数有一个独特的模式，可以用来更均匀地划分工作。内循环的迭代次数随着外循环的每次迭代而减一。因此，内循环迭代次数为：

       inner
 i   iterations
---  ----------
 0     m
 1     m-1
 2     m-2
 .     .
 .     .
 .     .
m-2    2
m-1    1 
 m     0

从这个表中可以看出， 和 的总内部迭代i=0次数i=m为m。i=1此外，和的总内部迭代次数i=m-1为m。实际上，对于和的任何c总内部迭代都是（保存外部迭代次数为奇数的情况）。i=ci=m-cm

有了这个事实，可以在每个外部迭代的基础上完成分配过程，以更好地平均分配负载。只需以蛇形方式将整个内部循环分配给进程。对于 5 个进程的情况，分配遵循以下模式：

 i   process 
---  --------
 0     1     
 1     2     
 2     3     
 3     4
 4     5
 5     5
 6     4
 7     3 
 8     2
 9     1
 .     .
 .     .
 .     .

使用这种方法，每个进程将处理大约相同数量的内部循环迭代，尤其是对于大m值。

于 2013-05-23T16:16:12.410 回答