N-Body问题:双循环的高效并行化

Question

关于N体问题的一个非常普遍的问题是使用双循环来计算粒子之间的相互作用.考虑到n个粒子的N体问题,可以编写循环

for (i = 0, i < n; i++)
    for (j = i+1, j < n; j++)
        // calculate interaction

我的问题是如何使用不同的线程并行化这个循环.目标是每个线程"理想地"必须计算相同数量的交互.

我的想法是在不同的时间间隔上分离外部循环,即i循环,例如a_k = a(k),其中k = 1,2,...,p其中p是我们想要划分的线程数问题进入.

因此,循环可以写成

for (k = 1, k < p; k++)
    for (i = a(k), i < a(k+1); i++)
        for (j = i+1, j < n; j++)
            // calculate interaction

最外循环,即k循环,是要并行化的循环.

因为最内循环(j循环)的交互次数是n-(i + 1),所以每个线程计算的交互次数是

\ sum_ {i = a(k)} ^ {a(k + 1)} n - (i + 1)

这意味着人们希望找到离散函数a_k以使其具有功能性

f [a_k] =\sum_ {i = a(k)} ^ {a(k + 1)} n - (i + 1)

边界条件a(1)= 0且a(p)= n是常数函数,因此迫使每个线程上的交互次数相同.

我尝试过使用不同的"启发式"(例如a_k多项式,指数,对数),到目前为止还没有人给我一个满意的答案.这个问题的直接解决方案对我来说并不明显.

对于小p,这个问题可以放在"最小化问题"上,其中基本上每个a_k都是一个变量来最小化函数

f(a_1,a_2,a_3,...)= sum(| f [a_k] - n/p | ^ 2)

但是你可能猜到,对于更高的p值,这是无效的(甚至收敛).

有没有人知道如何解决这个问题？

Answer 1

（抱歉，如果没有表达清楚，这在我的脑海中是有道理的）。

将 1 到 N 的所有数字相加时，您会发现 N + 1 = (N - 1) + 2 = (N - 2) + 3 等。

那么，如果每个线程使用一个小 i 和一个大 i，这样总和总是相加呢？

或者，假设您希望始终使用 5 个线程。线程 1 将执行前 10% 和最后 10%，线程 2 将执行第二个 10% 和倒数第二个 10%，依此类推。“早期”和“晚期”部分的每次配对都会增加相同的交互总数。

编辑：

盗用另一个帖子的图...

   0 1 2 3 4 5 6 7 8

0  - A B C D D C B A
1    - B C D D C B A  
2      - C D D C B A
3        - D D C B A  
4          - D C B A
5            - C B A
6              - B A
7                - A
8                  -

这是否更清楚地表明了我的意思？