8

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 の値が大きいほど効率的ではありません (または収束することさえありません)。

この問題にどのように取り組むことができるか、誰にも分かりませんか?

4

4 に答える 4

3

（これが明確に表現されていない場合は申し訳ありませんが、私の頭の中では理にかなっています）。

1 から N までのすべての数字を合計すると、N + 1 = (N - 1) + 2 = (N - 2) + 3 などであることがわかります。

では、各スレッドが 1 つの小さい i と 1 つの大きい i を使用して、合計が常に合計されるようにするとどうなるでしょうか?

または、常に 5 つのスレッドを使用したいとします。スレッド 1 は最初の 10% と最後の 10% を実行し、スレッド 2 は 2 番目の 10% と最後から 2 番目の 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                  -

それは私の言いたいことをより明確に示していますか？

于 2012-05-09T23:05:04.483 に答える
3

オブジェクトをk大まかなN/k体のグループに分割し、これを使用して相互作用の最初の三角形をk*(k + 1)/2細かく分割できます。

   0 1 2 3 4 5 6 7 8
                      -- N=9;  k=3;  N/k=3
0  - A A B B B C C C
1    - A B B B C C C  -- diagonal pieces:  A, D, F
2      - B B B C C C
3        - D D E E E  -- non-diagonal pieces: B, C, E
4          - D E E E
5            - E E E
6              - F F
7                - F
8                  -

(N/k)*(N/k - 1)/2このビューは、対角線に沿ったもの (要素を持つ三角形) とそうでないもの (要素を持つ正方形)の 2 種類のピースがあるという事実によって複雑になり(N/k)*(N/k)ます。ただし、斜めの部分は正方形の部分の約半分のサイズであるため、各スレッドに 2 つを割り当てて負荷のバランスをとることができます。つまり、k*k/2タスクの合計がほぼ同じになります。

この方法の利点は、各タスクが2*N/kボディのデータにアクセスするだけでよいことです。これにより、キャッシュ フレンドリーになる可能性があります。

于 2012-05-10T00:30:26.237 に答える
2

コンパイラが OpenMP をサポートしているとしたら、単純にやろうとしないのはなぜですか

#pragma omp parallel for schedule(dynamic) // or: schedule(guided)
for (i = 0; i < n; i++)
    for (j = i+1; j < n; j++)
        // calculate interaction

または（どちらがより優れたパフォーマンスを発揮するかを理解するには、ベンチマークする必要があります）

#pragma omp parallel
const int stride = omp_get_num_threads() + 1; 
for (i = omp_get_thread_num(); i < n; i += stride)
    for (j = i+1; j < n; j++)
        // calculate interaction
于 2012-05-10T09:40:39.640 に答える
0

今日、私はちょうど解決策を見つけました。誰かがそれを確認するまで私はそれを受け入れません

f [a_k]をkに関して定数関数にするために、

f [a_ {k + 1}]-f [a_k] = 0

k = 1,2,3、...、p-1の場合は真でなければなりません。

質問に投稿した定義を使用してこの方程式を拡張すると、a_k、k = 1,2,3、...、pに関する「p」2º次の代数方程式のシステムに到達します。任意のpの閉じた解は見当たりませんが、pごとに解析的に解くことができます。

私はそれを確認しました：

  1. 合計は、私が計算したa_kを使用した場合、n（n-1）/ 2であり、この問題の相互作用の総数です。

  2. スレッドあたりの相互作用の数は、p = 2、3、4、5、および10で実際に一定です（ここで、p = 10はmathematica®で計算するのに時間がかかりました）。

編集

pのさまざまな値について解を詳細に調べた後、一般的な閉じた解に到達しました。

a_k = 1 /（2 p）（-p + 2 pn --sqrt [p ^ 2 + 4 p（p + 1 --k）（n --1）n]）

これは、すべてのp> = 2、n>1に対して有効です。

これで答えは完成です。

于 2012-05-10T08:35:35.337 に答える