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)
これは、函数が
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 の値が大きいほど効率的ではありません (または収束することさえありません)。
この問題にどのように取り組むことができるか、誰にも分かりませんか?