量子アニーリングを用いた高性能コンピューティングの負荷分散: 適応メッシュ改良

リンク一覧

概要と序論

方法

結果

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

アダプティブメッシュリファインメント

AMR の負荷分散をアニーラーに適したイジング問題として定式化するために、ナビエ-ストークス方程式の完全圧縮性有限差分フロー ソルバーである CompReal(66) を使用してデータを収集しました。フロー ソルバーは、AMR アプリケーションで広く使用されている BoxLib(16)、(67) と呼ばれる一般的なソフトウェア フレームワークとインターフェイスします。BoxLib は、超並列ソフトウェアを構築するためのプラットフォームとして設計されており、最大 100,000 コアで優れたスケーラビリティを実証しています(68)。BoxLib に基づく研究コードは数多くあり、多様ですが、天体物理学 (69)、(70)、計算宇宙論 (69)、地下の流れ (71)、燃焼 (72) などの分野が含まれます。

シミュレーションされた特定のテスト ケースには、図 2 に示すように、発達中の球状の爆風が含まれます。最も急峻な勾配は、外側に移動する衝撃波の端を囲む非常に細いゾーンにあります。そのため、メッシュは定期的に更新され、その位置を追跡します。データは、グリッド (またはパッチ) と呼ばれる論理的に長方形のセルの集合のネストされた階層で定義されます。これはレベルに分割され、各レベルは同じメッシュ間隔を共有するすべてのグリッドの結合を指します。最も粗いレベルを除き、より細かいレベルは分離されており、シミュレーション ドメイン全体をカバーしないため、必要な領域にリソースを割り当てることが容易になります。各グリッドは多数のセルで構成されていますが、これはすべてのグリッドで必ずしも同じではありません。セルは、同じグリッド内では内部接続性が高く、隣接するグリッドとの相互接続性は低くなります。したがって、作業分散の観点からは、可能な場合はほぼ同じ合計セル数を維持しながら、グリッド全体を個々のプロセッサに割り当てることが望ましいです。

各ネストされたグリッドに関連する計算負荷を定量化するために、そのパッチ内のセルの総数がカウントされます。また、「負荷」の代替測定法もあります。たとえば、各パッチが割り当てられたタスクを完了するのにかかる時間を実際に記録すると、異なるセルが異なる方程式を解くマルチフィジックス シミュレーションの代表性が高まります。これは重みの値に影響しますが、Ising 定式化自体には影響しないため、この方法は完全に一般的なままです。

古典的シミュレーションは、このようにして各グリッドの名目コストを表す一連の数値を提供し、これを所定の数のプロセッサに公平に分配する必要がある。このプロセスは、古典的シミュレーション全体にわたって一定の間隔で繰り返す必要がある。これらのグリッドは内部接続性が高いため分割することは望ましくないため、問題は基本的に数値分割の問題に帰着する。N 個の数値セット (N はパッチの数、S = {n1,…,nN}) が与えられた場合、タスクは、このセットを 2 つの互いに素なサブセットに分割し、両方の要素の合計が同じになるか、少なくとも不一致が最小になるようにすることである。これは、次のイジング モデル (22) として表現される。

ここで、ni はセット内の数値、si はイジングスピン変数、A は一般的なスケーリング定数で、今後は 1 に設定されます。モデルには線形バイアスがありませんが、結合項は量子プロセッサにマッピングされると完全に接続されたグラフの形成につながります。2 つのサブセットが等しいかどうかの決定問題として表現される数値分割は NP 完全 (73) に分類されることは注目に値します。ただし、このモデルはシミュレーションからの実際のデータに基づいているため、完全にバランスのとれた分割を達成することは基本的にほぼ不可能です。したがって、目的はサブセット間の不一致を最小化することに移りますが、これは NP 困難なタスクです。このプロセスを再帰的に適用して、3 つ以上のプロセッサの分割を実現できます。現在、BoxLib はサブセット間でグリッドを分散するために単純なラウンドロビン戦略を使用しています。