新しいものづくりがわかるメディア

RSS


1枚のFPGAで最大3万変数の組合せ最適化問題を1秒で解く——単細胞生物アメーバを応用したコンピューター開発

Amoeba Energyとベクトロジーは2021年3月4日、1枚のFPGAで最大3万変数の組合せ最適化問題の解を1秒で導き出せる「アメーバコンピュータ」の共同開発に成功したと発表した

運行計画やスケジュールを効率化する課題は、最適な変数の組合せを探し出す数学的問題(組合せ最適化問題)を解くことで解決できる。しかし、組合せ最適化はシステムサイズが大きくなると組合せ爆発が生じるため、従来型コンピューターが苦手とするタスクだった。

近年は、量子コンピューターやアニーリング方式に基づく組合せ最適化専用マシンの提案が相次いでいるが、導入/計算コストの高さが実用上のネックとなっていた。また、1枚のFPGAやGPUで、数万変数以上の規模の問題を実用的な時間で解くことは困難という課題もあった。

そこでAmoeba Energyと北海道大学の共同研究グループは、単細胞アメーバ生物(粘菌)の環境適応能力をヒントに、アナログ電子回路中にアメーバ素子を高密度で配置できる電子アメーバのプロトタイプを考案し、2020年11月に発表した。電子アメーバは、難度の高い組合せ最適化問題(巡回セールスマン問題)の良い解を高速に探索でき、他のさまざまな最適化アプリを回路に入力する際の導入/計算コストも低く抑えられる。

そして今回、 Amoeba Energyとベクトロジーは、電子アメーバのコンセプトをデジタル回路の表現に落とし込み、PALTEK製のFPGA基板「M-KUBOS」を用いることで、実用的規模の問題を扱えるアメーバコンピュータを開発した。アメーバコンピュータは、論理的制約条件の集合としてさまざまなアプリケーションを表現する定式化がすでになされている充足可能性問題(SAT)を、Amoeba Energyが開発したアルゴリズム「AmoebaSAT」で解く方式を採用している。

AmoebaSATは、多数の素子の並行的状態更新と確率的動作を再現できるアーキテクチャを前提に設計されているが、量子効果が現れるような特殊な回路の使用は不要。各変数へ任意の重み付けが可能で、実社会のさまざまな最適化アプリの目的関数を表現できる。また、任意の制約条件や初期状態をファイル入力によってプログラムすることが可能だ。

従来方式のアメーバコンピュータは、最適化アプリを変更する際に数時間におよぶFPGAの合成工程が必要だった。しかし、新たに開発されたアメーバコンピュータでは、入力ファイルを指定するだけで問題の解を探索することが可能だ。さらに、制約条件を回路として表現するためのルールの数を大幅に削減し、回路資源を活用することで、アメーバ素子を高密度で集積できる。これらの新技術により、重み付けされた3万変数のSAT問題例(3-SAT)の解を1秒以内に導出できるようになったという。

アメーバコンピュータはさまざまなIoTデバイスに組み込める。スマート工場における自動搬送システムやスマート病院における手術スケジュールの最適化など、アメーバコンピュータを用いた組合せ最適化アプリの実現に向けた共同研究開発がすでに進行している。

関連情報

おすすめ記事

 

コメント

ニュース

編集部のおすすめ

連載・シリーズ

注目のキーワード

もっと見る