雅子 訳
香港科技大学（HKUST）とHuawei Technologiesの研究者らは、FPGAベースのスパースイジングマシンを設計した。このマシンは、驚くほど単純なアプローチ、すなわちスパース問題をスパースなまま扱うことで、従来のFPGA実装と比較して最大68倍高速に組合せ最適化問題を解決する。
Nature Communicationsに掲載されたこの研究は、Max-Cut問題を対象としている。Max-CutはNP困難な組合せ最適化タスクであり、グラフの頂点を2つの集合に分割し、分割を横切る辺の数を最大化することを目的とする。Max-Cutは回路設計、統計物理学、機械学習に応用があり、イジングマシンが加速するよう設計されている問題と同じクラスに属する。
スパース性への着眼
現実のMax-Cutグラフは典型的にスパースであり、ノード数に比べて辺の数が比較的少ない。しかし従来のFPGAベースのイジングマシンはこれらを密なものとして扱い、ゼロエントリでオンチップメモリを浪費し、1つのチップに収まる問題サイズを制限していた。
研究チームはタイル化座標リスト（TCOO）データ形式を導入した。これは非ゼロエントリをFPGAのオンチップブロックRAM（BRAM/URAM）アーキテクチャに合わせた固定サイズのタイルにグループ化するもので、ストリーミングのオーバーヘッドなしにFPGA上で直接効率的なスパース行列ベクトル乗算を可能にし、問題のネイティブなスパース性を活用する。
従来の32ビット浮動小数点と比較してメモリフットプリントを4分の1に削減する8ビット整数量子化と組み合わせることで、ソリューション品質を損なうことなく、最大20,000変数を単一のFPGAチップに収めることができる。
パフォーマンス
標準的なMax-CutベンチマークであるGsetグラフコレクションにおいて、本設計は従来の最先端FPGAベースイジングマシンに対して10～68倍の高速化を達成した。マルチFPGAネットワークやGPUクラスターは不要で、計算全体が単一チップ上で実行された。
HKUSTのBaijian Yao、Xu Shi、Wei Zhang、およびHuawei TechnologiesのDaniel Ebler、Juntao Wang、Fan Zhang、Jie Sunからなるチームは、ハードウェアとソフトウェアを共同で設計した。データフロー、パイプラインアーキテクチャ、メモリ階層は、レイテンシを最小化しスループットを最大化するために共最適化された。
この成果は、単一チップ上で20,000スピンを処理できる初のFPGAベースイジングマシンであり、従来はマルチFPGAまたはGPUベースのシステムを必要とした規模である。
ソース：
1. Yao B, Shi X, Zhang W, Ebler D, Wang J, Zhang F, Sun J. 「Precision meets speed through an FPGA-based natively sparse Ising machine for combinatorial optimization.」 Nature Communications. 2026. DOI：10.1038/s41467-026-75119-0