量子アニーリングを用いた高性能コンピューティングの負荷分散: 平滑化粒子流体力学

リンク一覧

概要と序論

方法

結果

結論と展望、謝辞、参考文献

平滑化粒子流体力学

この論文では、SPH 演算子を使用して支配方程式のセットを離散化する技術的な詳細については取り上げません。これはアプリケーション固有のものであり、興味のある読者は関連文献 (18)、(20) を参照できます。代わりに、ここでの重要なポイントは、この一連の方法では粒子データの保存が必要であるということです。さらに、これらの粒子は空間内で不規則に配置され、各タイム ステップで移動します。これは、特定の関心領域で粒子を集約し、他の領域でまばらに分散できるようにするため、SPH の主な強みですが、実際にこの利点を活用するには、効率的なメモリと作業割り当てが必要です。

カーネルのコンパクト サポートにより、粒子はスムージング長の範囲内にある近隣粒子のみの影響を受けるようになります。したがって、プロセッサ間の通信を制限するために、プロセッサに作業を割り当てるときにドメインをセクションに分割するのが理にかなっています。ただし、粒子は無秩序であるため、一部の領域は他の領域よりも密集していることを覚えておくことが重要です。したがって、作業配分を作成するときに、プロセッサ内通信の 2 番目の手段も考慮する必要があります。

本研究で QA を使用して分割される古典データは、100,000 コアで優れたスケーラビリティを実証した人気の高い天体物理学コードである SWIFT(74) を介して取得されました。SWIFT は、バックボーンとして各ノード内の共有メモリのパフォーマンスを最適化するために、タスク ベースの並列処理(75) に依存しています。これは、グラフ分割アルゴリズムを使用して複数の分散メモリ ノードにまたがる作業割り当てを作成するために簡単に一般化できます。要約すると、ドメインは最初にセルのセットに分割され、各セルには粒子のコレクションが含まれており、2 つの粒子が相互作用する場合は、同じセルまたは最大で隣接するセルのいずれかになります。

負荷分散の観点では、このドメイン分割アプローチはグラフとして効率的にモデル化できます。グラフでは、各ノードがいくつかの粒子を含む個々のセルを表します。このグラフのエッジは、これらのセル間の通信を必要とする、別々のセルにある粒子に依存する共有タスクを表します。さらに、異なるパーティションのセルを含むタスクは、それぞれのプロセッサの両方で処理する必要がありますが、同じパーティション内のタスクは、対応するプロセッサによってのみ評価されます。最適な負荷分散戦略は、各サブセットのノードの重みの合計と、これらのサブセットをブリッジするエッジの重みの合計の両方を最小化することを目的とします。前者の目標は、各ステップで最も遅いプロセッサによって発生する待機時間を削減することであり、後者は、プロセッサ間通信に必要な帯域幅を減らすことに重点を置いています。この 2 つの目的により、効率的な処理と最小限の通信オーバーヘッドの両方が保証されます。

重みの値は、SWIFT の例スイートで見つかり、図 3 に示されているように、暗黒物質を含む小さな宇宙体積をシミュレートすることによって取得されました。シミュレーションには 64(3) 個の粒子が関係し、重みは、ノード/エッジの重みについてそれぞれセル内/セル間タスクの時間を計測することによって抽出されました。領域分割パラメータは、問題を現在のアニーリング装置に適応させるためにセルの数を減らすように設計によって変更されました。セルは立方体であるため、3 次元では、各セルに 6 つの面隣接、12 のエッジ隣接、8 つのコーナー隣接があるため、最小ノード/セル数は 27 になります。共有タスク用に以前に定義された 1 セルの範囲内に 26 個の隣接セルがすべて存在するため、完全に接続されたグラフになります。

この負荷分散問題に対するイジングモデル(22)は、各ノードにスピン変数(−1/+1)を配置し、そのノードが最終的に「+」サブセットに属するか「−」サブセットに属するかを決定する。エネルギー関数は2つの要素から構成される。

ここで、ラグランジュパラメータ（γ）は、矛盾する効果を調査するためにγを変更できるように導入されている。モデルには、集合+のノードの重みが集合−のノードの重みと等しくない場合のペナルティ項が含まれる。

ここで、合計はすべてのノードにわたっており、各ノードの重みは wi である。さらに、異なるサブセットのノードを接続するエッジが切断されるたびにペナルティ項がある。

ここで、合計はすべてのエッジ接続ノードにわたっており、eiはエッジの重みを表します。これはNP困難問題(73)であり、多くの粒子ベースのコードが将来のHPCシステムで有意な優位性を維持することを保証する上で重要な価値があります。現在、SWIFTはグラフ分割ソフトウェアMETIS(76)に依存しています。