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_pidsfrom 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=mmi=1此外,和的总内部迭代次数i=m-1m。实际上,对于和的任何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 回答