Omnisolver: An extensible interface to Ising spin-glass and QUBO solvers: adding a distributed GPU brute-force plugin

現代のコンピューティングという広大な風景の中に、ある種の複雑な問題が存在します。それは、単に最高の解を見つけ出すことが、一歩進むごとに大きくなる砂漠の中で特定の砂粒を探すようなものだと感じられるほど困難なものです。これらは最適化の課題であり、多くの場合、パーツが相互に作用するネットワークとしてモデル化され、エネルギーやコストが最も低い状態に到達するようにパーツを配置することを目的としています。科学者やエンジニアは、原子レベルでの物質の振る舞いから、交通量の制御や金融ポートフォリオの管理に至るまで、あらゆる事象を理解するためにこれらのモデルを使用しています。数十年にわたり、これらのパズルを解くための最も信頼できる方法は、あらゆる可能な配置をすべてチェックすることであり、これは「総当たり探索（exhaustive search）」として知られています。しかし、パーツの数が増えるにつれて、可能な配置の数は爆発的に増加するため、世界最強のスーパーコンピュータであっても、人間の生涯のうちにその作業を終えることはできません。これは重大なギャップを生み出します。つまり、絶対的な正解を見つける方法がなければ、研究者は、彼らが「十分に良い」答えを見つけるために用いている巧妙なショートカットが、実際に真実に近いものなのかどうかを確信することができないのです。

ポーランドの研究チームは、この特定の範囲の困難な問題に対して、このギャップを埋めるために設計された新しいツールを構築しました。彼らは、ハイエンドのゲームやビデオ用のコンピュータに見られるような標準的なグラフィックスカードを、最大60個のパーツを持つ問題のあらゆる配置をチェックできるマシンへと変貌させるソフトウェア・アップデートを作成しました。この生のチェック能力と、複数のコンピュータ間で作業を分割するシステムを組み合わせることで、彼らは以前は完全には解くことができなかった規模の問題に対して、完璧な解を見出すことに成功しました。この成果は、他のより高速なプログラムがテストするための「ゴールドスタンダード（黄金基準）」となる回答を提供し、それによって科学者が、自分たちのショートカットが本当に機能しているのか、あるいは最善の解を見逃しているのかを検証できるようにします。

この研究の核心は、「Omnisolver-bruteforce」と呼ばれるソフトウェア・プラグインであり、これは異なる種類のコンピュータ・ソルバーのためのユニバーサル・トランスレーター（汎用翻訳機）として機能します。これは、研究者がさまざまなツールを同じ問題に取り組むために接続できるようにする「マスターキー」のようなものです。研究者たちは、単一のグラフィックスカード上であらゆる可能性をチェックできる既存のツールを取り上げ、それを8枚の強力なカードを用いたネットワーク上で動作するようにアップグレードしました。彼らは、膨大な探索空間を小さく独立したチャンク（塊）に分割することでこれを実現しました。図書館で特定の書籍を見つける必要がある場面を想像してみてください。一人の人がすべての棚をチェックする代わりに、タスクが分割され、8人が同時に異なるセクションをチェックし、ターゲットを見つけたときだけ報告を行うのです。この場合、「図書館」は問題のあらゆる配置の集合であり、「探索者」は並列して動作するグラフィックスカードです。

研究者たちは、大容量のメモリを備えた8枚の高パフォーマンス・グラフィックスカードのクラスターを用いて、この新システムをテストしました。彼らは、これらの最適化問題のランダムなバージョンを解くようにシステムを設定し、問題のサイズを40個のパーツから60個へと段階的に増やしていきました。結果は驚くべきものでした。60個のパーツを持つ問題に対して、システムは約3日間で全可能性をチェックし、最善の答えを確認しました。これは長い時間のように聞こえるかもしれませんが、この新しい手法がなければ、このタスクを合理的な時間内に完了させることは不可能でした。チームは、問題にパーツが1つ追加されるごとに、解決に必要な時間がほぼ倍増するという現象を観察しましたが、このパターンはすべてのテストにおいて一貫して成立していました。この予測可能な挙動は、彼らのシステムが、この種の総当たり探索に関する物理学および数学の法則通りに正確に動作していることを裏付けました。

革新の重要な部分は、膨大な量の作業を行っている間にコンピュータが小さなミスを犯さないようにすることにありました。グラフィックスカードは高速であるように設計されており、しばしば極端な精度を犠牲にしているため、時間の経過とともに蓄積される微細なエラーが発生することがあります。研究者たちは、これらの微細なエラーが発生した瞬間に自動的に修正する方法を開発し、最終的な回答が数学的に正確であることを保証しました。彼らは、より小さな問題に対する既知の完璧な解と比較することでこれを検証し、最後の桁に至るまで回答が一致することを確認しました。このレベルの信頼性は、このツールがビジネス向けの日常的な問題を解決するためのものではなく、参照点として機能することを目的としているため、非常に重要です。これにより、科学者は、量子物理学や生物学的システムから着想を得たような、より高速なアルゴリズが、本当に最善の解を見つけているのか、それとも単に推測しているだけなのかをテストすることができます。

また、研究ではさらに大規模なコンピュータ・クラスターで何が可能になるかについても考察されました。研究者たちは、もし216枚のグラフィックスカードを接続できれば、60個のパーツを持つ問題をわずか33秒で解決できると計算しました。さらに、このような大規模なネットワークがあれば、理論的には最大76個のパーツを持つ問題を1か月以内に解決できると推定しました。しかし、これらは現在のデータに基づいた投影であり、コンピュータ間の通信遅延などの現実世界の要因によって正確な数値が変わる可能性があることを、彼らは慎重に注記しました。現在のシステムは、ソフトウェアによるカウントの方法により、64個のパーツまでの問題に制限されていますが、その制限内においては、決定的な回答を提供します。

この研究は、あらゆる最適化問題を解決したと主張するものでも、総当たり探索が日常的な使用におけるより高速な近似手法に取って代わることを示唆するものでもありません。むしろ、それらより高速な手法の品質を証明する方法を提供するものです。ある規模の問題に対して保証された正しい答えを提供することで、研究者たちは科学界に対し、新しい技術の精度を測定するための「定規」を与えました。コンピューティングの分野がより複雑な課題へと進む中で、「これが最善の答えである」と断言できるツールを持つことは不可欠なベンチマークとなります。研究者たちは、この新しい能力を使用して自身の発見を検証し、計算可能な限界を押し広げることができるよう、ソフトウェアを公開し、コミュニティに利用を呼びかけています。