[最新ニュース] IT・マテハン

「アメーバコンピュータ」でモノの流れの組合せを最適化

2021/03/04

アメーバ型組合せ最適化アルゴリズムを提供するAmoeba Energy(株)とFPGAコンピューティングのエキスパート、(株)ベクトロジーは3月4日、AMOEBA ENERGYが考案した新方式の高密度・高汎用性アルゴリズム「AmoebaSAT」をベクトロジーのFPGAコンピューティング技術で実装することにより、実社会の様々な最適化アプリの目的関数を表現できるよう重み付け可能な充足可能性問題(SAT)を高速に解く「アメーバコンピュータ」の共同開発に成功したと発表した。

製造、物流、通信等の様々な社会システムで運行計画やスケジュールを効率化する課題は、最適な変数の組合せを探し出す「組合せ最適化問題」と呼ばれる数学的問題を解くことで解決できるが、組合せ最適化はシステムサイズが大きくなると「組合せ爆発」が生じるため、従来型コンピュータ(Central Processing Unit:CPU)が苦手とするタスクで、世界最速スパコンでも手に負えなくなるほどに複雑化してしまう課題となっている。そこで近年、「量子コンピュータ」や、そこから着想を得た「アニーリング方式」に基づく組合せ最適化専用マシンの提案が相次いでいるが、同方式は解くべき問題をマシンが扱える「イジングモデル」の形式に変換する際に高度な専門知識の提供や技術的制約の解決が必要となり、そのために生じる導入・計算コストの高さが実用上のネックとなっていた。また、同方式の素子を回路上に高密度で配置することは容易ではなく、1枚のFPGA(Field Programmable Gate Array)やGPU(Graphics Processing Unit)で、数万変数以上の規模の問題を実用的な時間で解くことは困難になっていた。

2020年11月、AMOEBA ENERGYと北海道大学の共同研究グループは単細胞アメーバ生物「粘菌」が不定形の体を環境に適した最も良い形に変えられるメカニズムをヒントに、アナログ電子回路中にアメーバ素子を高密度で配置する「電子アメーバ」のプロトタイプを発表。電子アメーバは難度の高い組合せ最適化問題「巡回セールスマン問題」の良い解を高速に探索でき、他の様々な最適化アプリを回路に入力する際の導入・計算コストも低く抑えられる点が大きな魅力となっている。今回の研究成果は、Nature Researchの学術論文誌「Scientific Reports」に掲載されると、国内外の多数のオンラインメディアに取り上げられ大きな注目を集めたとしている。

●開発成果
「アメーバコンピュータ」は論理的制約条件の集合として様々なアプリケーションを表現する定式化がすでになされている「充足可能性問題(Boolean Satisfiability Problem:SAT)」を、AMOEBA ENERGYが独自に開発したアルゴリズム「AmoebaSAT」により解く方式。AmoebaSATは多数の素子の並行的状態更新と確率的動作を再現できるアーキテクチャを前提に設計されているが、そのためのハードウェアとして量子効果が現れるような特殊な回路の使用は不要。従来の半導体技術で構築されるFPGAは、AmoebaSATの並行的・確率的プロセスの実装に適しており、その効果的な解探索能力を発揮。AMOEBA ENERGYとベクトロジーはアナログ回路からなる電子アメーバのコンセプトをデジタル回路の表現に落とし込み、(株)PALTEK製FPGA基板「M-KUBOS」を用いることで、実用的規模の問題を扱えるアメーバコンピュータを開発することに成功した。

今回、AMOEBA ENERGYが開発した新方式のAmoebaSATは各変数へ任意の重み付けが可能で、実社会の様々な最適化アプリの目的関数を表現できる。また、任意の制約条件や初期状態をファイル入力によりプログラムが可能。従来方式のアメーバコンピュータは扱う最適化アプリを変更する際に数時間におよぶFPGAの合成工程が必要だったが、新方式の高汎用性アルゴリズムを搭載したアメーバコンピュータでは、入力ファイルを指定するだけで直ちに新たな問題の解探索を可能としている。さらに制約条件を回路として表現するためのルールの数を大幅に削減し、ベクトロジーの培ってきたFPGAコンピューティング技術により、回路資源をフル活用することでアメーバ素子の高密度集積を実現した。これらの新技術により、アメーバコンピュータは重み付けされた3万変数のSAT問題例(3-SAT)の解を1秒以内に導出することが可能になり、新方式アルゴリズムを従来型コンピュータで実装した場合と比較すると300倍以上の高速化を達成した。

●アメーバコンピュータの用途】
組合せ最適化問題として定式化される様々なアプリケーション
スマート工場/倉庫:自動搬送システム最適化
スマートオフィス:勤務スケジュール最適化
スマート病院:手術スケジュール最適化
スマート物流/交通:配車計画最適化
ロボット制御:アーム等による物体移動プランニング
P2P取引:モノ・サービス・エネルギー等の取引
通信:無線ネットワークにおけるリアルタイムルーティング

●今後への期待
1枚のFPGAで最大3万変数の組合せ最適化問題を自在にプログラムして解くことが可能なアメーバコンピュータは、小型で省電力性に優れており、様々なIoTデバイスに組み込むことが可能で、モノづくりやモノの流れをエッジで高速に最適化したいニーズに応える。こうして「考える力」を獲得したエッジデバイスは超スマート社会「Society 5.0」の実現に向け、様々な場面で活躍を期待されている。

現在、AMOEBA ENERGYはスマート工場における自動搬送システムやスマート病院における手術スケジュールの最適化等、アメーバコンピュータを用いた組合せ最適化アプリの実現に向けた共同研究開発を複数のパートナーと進めている。ベクトロジーのFPGAコンピューティング技術は高汎用性設計となっているアメーバコンピュータを、より個別のアプリに特化した構成に変更することで、さらなる高速化を可能にする。アプリの仕様に応じ、書換えが不要になる制約条件は固定回路にすることで、さらに数桁の速度向上が見込まれている。また、FPGAを複数接続したクラスターを形成することにより、さらなる大規模化も可能になる。両社の技術をベースに、新たなアプリケーションの創造やデジタルトランスフォーメーションの実現に向け、協力パートナーを、広く募集いたしている。

|↑一覧に戻る|