著者:
（１）オマー・ラソーレ、ダラム大学物理学科
（２）アラステア・バスデン、ダラム大学物理学科
（３）ニコラス・チャンセラー、ダラム大学物理学科、ニューカッスル大学コンピューター学部
（4）ハリム・クスマートマジャ、ダラム大学物理学科、エディンバラ大学工学部マルチスケール熱流体研究所
リンク一覧
概要と序論
方法
結果
結論と展望、謝辞、参考文献
粒子ベースのアプリケーション
SPH の負荷分散を表すグラフは、図 9a に示すように、完全に接続されているため、非常に密です。最適化されたパーティションは、合計ノード重みのサブセット間の不一致を最小限に抑えると同時に、カット エッジ重みの合計も最小化することを目標とする必要があります。2 つの目的のどちらがより重要であるかは、HPC アーキテクチャ、特に CPU スタックの制限要因がプロセッサ内帯域幅かプロセッサ間帯域幅のどちらであるかに多少依存する可能性が高いため、事前に明確ではありません。たとえば、後者の場合、ノードの不均衡がわずかに高くなることを犠牲にしても、可能であればカット エッジ重みをさらに最小化する方が戦略的であり、前者の場合はその逆になります。したがって、一般性を保つために、ここではタスクを多目的最適化問題と見なします。
ラグランジュパラメータ γ は、式 6 に示すように、これら 2 つの目的の相対的な重要性を決定します。値が高いほど、2 つのサブセット間のノードの重みの差を最小化することの重要性が高くなります。γ が非常に大きい場合、エッジの相対的な影響は無視できるため、問題は基本的に数値分割に戻ります。興味深い発見は、このパラメータを変更すると、チェーンの切断率に予期しない影響があったことです。これは、図 9b に示されています。値が小さいと、同じサイズのグラフであっても、グリッドベースの数値分割の例で観察されたよりもチェーンの切断が少なくなります。実際、ラグランジュパラメータが増加すると、問題は数値分割に戻り、チェーンの切断がより頻繁になります。これは、基礎となるグラフ構造が変更されていないにもかかわらず、27 ノードのクリークのままです。さらに、数値は量子プロセッサへのマッピング プロセスで自動的にスケーリングされるため、重みの値の違いだけではチェーンの切断に大きな影響を与えないはずです。 これは、基礎となる埋め込みの性質は変更されていないにもかかわらず、ここでの負荷分散問題は、グリッド ベースの場合よりもチェーンの切断に対して本質的に耐性が高いことを意味します。
今のところ、ラグランジュパラメータが 1 の中立値であるとします。1,000 回のアニールと、最先端の古典的なグラフ分割ソフトウェアである METIS を使用して取得されたパーティションと比較した最低エネルギー解を使用して、単一の QA が実行されました。これは、カットエッジマトリックスをヒートマップとして表示した図 10 に示されています。マトリックスの各エントリは、対応する軸インデックスを持つノードを接続するエッジを表し、色の強度はそのエッジの重みを示しています。色の値が null (つまり、濃い紫色) の場合、そのエッジはカットされていません。QA と METIS はどちらも、それぞれ合計 182 回のカットを行い、単一の最大カットに関しては同じ大きさを共有しています。ただし、QA はエネルギーランドスケープの探索において一貫してより適切な選択を行い、より安価なエッジを切断することで、合計で約 33% の節約を実現しています。この QA 実行からのカットエッジの合計重みは、METIS の対応するものの 66% のサイズにすぎませんでした。 さらに、これによりノードバランスも改善され、QA を使用した場合の不均衡の度合いは、METIS によって割り当てられた不均衡の 34% に過ぎませんでした。
QA 実行を 5 回繰り返して平均すると、表 1 に示すように同じ傾向が依然として維持され、この方法は確率的変動に対して耐性があることを示しています。ノードとエッジの重みは、両方の方法が同じデータ セットで動作するため、同じ係数で正規化されていることに注意してください。さらに、表の「パフォーマンス比」エントリは、対応する METIS エントリを QA の対応するエントリで割った分数結果です。両方の目的が最小化されるように調整されているため、パフォーマンス比が 1 より大きい場合は、量子的利点があることを示しています。さらに、QA は両方の目的を同時に満たしてより優れたパフォーマンスを発揮します。
これに加えて、ラグランジュパラメータを調整することで、量子アニーリングの結果をさらに微調整して、HPCクラスターの特定のニーズを満たすことができます。幅広い適用性を維持するために、この研究では、1000回のアニーリングとラグランジュパラメータの0から1000までの均等間隔の値を100回繰り返して、パラメータの状態空間を広範囲に調査しました。
50. このプロセスから得られた 2 つの目的関数に関するパレート優位解を図 11 に示します。ここでのパレート フロントは、1 つの目的関数を改善すると 2 番目の目的に悪影響が及ぶような一連の解を表しています。パレート フロントの右側は水平にかなり近いため、右端からアプローチすると、カット エッジの重みをごくわずかに増やすだけで、解の不一致を大幅に改善できることが示唆されます。逆に、最初は左から始めて右に向かって進むと、ノード バランスをほとんど犠牲にすることなく、カット エッジを大幅に改善できます。METIS の解も比較対象に含まれていますが、明らかに両方の目的を改善できるという点で劣っています。さらに、後者は、少数のラッキー アニールだけでなく、パレート フロントから外れているが METIS 出力に対して依然としてパレート優位である QA ポイントのコレクションで見られるように、大部分で当てはまります。 これは、合計 100,000 個のサンプル ソリューションのうち 41,000 個近くに相当し、複雑な問題に対する QA の回復力を示しています。この領域以外でも、候補ソリューションのほとんどは、1 つの目的においてのみ METIS より劣っています。これは、非常に大きいか非常に小さいラグランジュ パラメータを適用した結果であると考えられます。これにより、他の目的が損なわれる可能性があっても、1 つの目的が自然に優先されます。
