2020.01.23 Thursday

世界で初めての全結合型半導体アニーリング方式人工知能チップを開発
~512スピン実装により22都市巡回セールスマン問題求解を瞬時に
(ノイマン型高性能CPUではおよそ1200年が必要)~

研究の要旨とポイント

  • 組み合わせ最適化問題の解のより高速かつ低電力な探索のため、世界で初めて全結合型半導体アニーリング方式を使用したAIチップを開発し、LSIに実装しました。
  • 新開発のLSIでは、22都市の巡回セールスマン問題を1秒以下で解くことができます。従来のノイマン型の高性能CPUでは1200年かかり、アニーリング方式の中でも隣接結合型と呼ばれる別の手法では、現状最大16都市に相当する問題を解くのが限界となっていました。
  • 今回の技術を応用すると、小型・低電力ながら高性能なシステムを実現することができるため、オフィスや個人のタブレット型端末などの身近な環境で、多くの組み合わせの中から最適な解を容易に求められるようになるなど、これまでにない幅広い応用が可能になると期待されます。

東京理科大学工学部電気工学科の河原尊之教授の研究グループは、組み合わせ最適化問題1の求解用に世界で初めて全結合型半導体アニーリング方式2を搭載した人工知能集積回路(AIチップ)を開発致しました。新しいチップアーキテクチャにより512個の全結合型スピンを搭載しています(チップ面積は28 nm CMOS半導体プロセスで2.16 mm×2.70 mm)。
半導体アニーリング方式は、組み合わせ最適化問題に適した方式であり、今回開発したAIチップは、22都市の巡回セールスマン問題3を瞬時に解くことが可能です。一方、従来のノイマン型4の高性能CPUでは、都市数と共に計算量が急増し、22都市では計算に1200年かかります。半導体アニーリング方式のAIチップとしては、ほかに隣接結合型と呼ばれるものが知られていますが、16都市相当分(ノイマン型CPUでも12分で計算可能)のスピン数しか搭載されていませんでした。
今回の開発技術を応用すると、小型・低電力ながら高性能なシステムを実現できるようになります。多数の組み合わせの中から最適な解を求める、という課題をオフィス内やタブレット端末上で容易に解けるようになるため、これまでにない幅広い展開が期待されています。

【研究の背景】

組み合わせ最適化問題は、私たちの生活のごく身近なところに多数存在しています。図書館に返却された複数の本をそれぞれの書棚に戻す時や、宅配便のトラックが多くの荷物を複数の箇所へ届ける時などに最短経路を求めたり、予算の限度を越えない範囲で複数の部品を最大数購入できる組み合わせを考えたりと、日常生活の中でよく見かけるこれらの問題が、組み合わせ最適化問題です。
組み合わせ最適化問題には、問題の大きさ(訪れる書棚や届け先)が増えると共に、探索すべき経路の数が極めて大きくなるという特徴があります。例えば届け先数が4カ所の時は経路の候補は24通りで済みますが、8カ所では4万通り、そして12か所では4億7千9百万通りにもなります。この膨大な候補の中から最も効率が良い経路を探索する、計算時間もまた膨大になってしまいます。日常的な問題をオフィス内や個人のタブレット端末などで手軽に解決するには、消費電力が小さく高性能な人工知能による処理が必要です。

このような課題に対して、複数の計算要素(スピン。スピン一つにつき、上向きか下向きの二つの状態のいずれかを持つ)と、スピンの間の結合の強さ(相互作用)を調整し、スピンの向きを計算するための磁性体モデル(イジングモデル5)の原理を応用した「アニーリング方式」によるAIチップの開発(図1)と、半導体集積回路(LSIチップ)化が盛んに進められています。

世界で初めての全結合型半導体アニーリング方式人工知能チップを開発 ~512スピン実装により22都市巡回セールスマン問題求解を瞬時に(ノイマン型高性能CPUではおよそ1200年が必要)~

図1 組み合わせ最適化問題求解性能比較

アニーリング方式では、組み合わせ最適化問題の複数の解の候補(宅配の例ではトラックの経路。以下、具体例では宅配の最短ルートを探索した場合について述べます)を複数のスピン回路(スピンセル)のデータで表現し、スピンセルのデータと、スピン同士を結合させる強さを格納した回路(結合セル)のデータを使って、個々の要素の関係(例:2つの届け先間の距離など)を表現します。更にこれらのセルのデータを用いて積和演算(乗算の結果を順次加算する演算)を行い、この結果を用いて別途定義したエネルギーを計算し、更にその結果と、別途定義した温度と乱数を用いて確率的な計算を行うことで、エネルギーが最低となる状態(スピンセル状態)を得ます。この状態が組み合わせ最適化問題の解(例:トラックの最短経路)を表します。ノイマン型CPUでは膨大な候補の各々のエネルギーを総当たりで計算して比較するため、最適解を得るのに長い時間を要してしまいますが、アニーリング方式ではイジングモデルの原理を応用して、低電力かつ極めて高速でエネルギーが最低となる条件を得ることができます。
これまでの研究では、隣り合うスピン同士にのみ相互作用があると仮定し、スピンの結合をイジングモデルで考える「隣接結合」と呼ばれる方式が主に用いられていました。LSIに使用できる配線の数には限りがありますが、隣接結合方式は限られた条件の中で容易に接続できるため、実装に適した方式であると考えられてきました。しかし、実際に計算を行うには前処理が必要であることや、また、解くべき問題が大きくなると問題や解を表すスピンや結合の数が増えるため、実装面積に課題があること、更にはスピンセルや結合セルの増加により、チップ外部からデータを入出力するためのオーバーヘッド時間が大きくなったことなどから、アニーリング方式による計算の高速化を活かせなくなっていました。

【研究成果の概要】

今回、東京理科大学工学部電気工学科河原尊之教授の研究グループはスピン同士のすべてを結合させる全結合方式のAIチップを開発し、世界で初めてLSIに実装致しました。搭載したスピン数は512個であり、22都市の巡回セールスマン問題を1秒以下で解くことが可能です。
全結合方式には、少ないスピン数で幅広い問題が解けるという利点があることは既に知られていましたが、LSIチップ化のためには、配線層数の制限から、すべてのスピンの結合を実装できる方法の開発が難しい課題でした。今回、新しいチップアーキテクチャにより512個の全結合型スピンを搭載することが可能となりました。

今回開発した主要な技術は以下の通りです。

  1. 分離アレー型全結合方式
    • 新しいチップアーキテクチャとして、結合セルを2次元アレー上に配置し、これと分離してスピンセルを1次元的に配置しました。結合セル2次元アレーから行単位でデータを読み出し、これとスピンセルのデータを用いて並列積和演算を行い、温度と乱数を用いて確率的な計算を行います。更に今回この計算結果の符号のみで、スピンの状態を更新します。これを繰り返すことで解である複数スピンセルの状態を容易に決定できる独自の全結合方式となります。全結合方式のため、スピンセル数は隣接方式スピンセル数の平方根の値に減少し、また、結合セル数も数分の一となりました。
  2. 多スピンスレッド方式
    • アニーリング方式では温度と乱数を用いた確率的な計算のため、解が一義に決まるわけではありません。繰り返し試行が複数回必要となる場合があります。今回、1次元のスピンセル部分と2次元アレーの結合セル部分を分離したことにより、スピンセル部分を複数個設ければ、あたかも複数回数又は複数チップ分の動作を一度に行うことができます。この複数の1次元スピンセル配列を多スピンスレッドと名付け、今回のチップでは8スピンスレッド搭載しました。これにより、外部からスピンセル部分と2次元アレーの結合セル部分へのデータの出し入れは1回であっても、8回分の計算が一度にできることになりました。
  3. 折り畳み半減結合セル配置方式
    • 今回提案の全結合方式では、結合セルを2次元アレーとするチップアーキテクチャとしましたが、更に結合セル数を半減させました。単純な2次元アレーの配置のままでは、2つのセルを入れ替えた場合の結合セルを別個のものと取り扱ってしまいます。また、自分自身との結合も入ってしまいます。これらを取り除きました。しかしながら、2次元アレーをLSI上にそのまま配置すると、そのレイアウトは三角形になってしまいます。そこで更にこの三角形の一部を切り取り、折り畳むように移動させることにより結合セルアレー全体のレイアウトを矩形にし、結合セル部の面積削減を実現しました。

これらを、28nmCMOS半導体プロセス技術を用いてLSIチップ化しました(図2)。更に評価ボードを開発し、実証実験を行いました。その結果、8スピンスレッドが同時に室温で動作することを確認致し、すなわち、8チップ分の結果を一回の動作で取り出すことに成功致しました。

なお、従来の隣接結合方式で今回の全結合型512スピンを実現しようとすると、およそ26万個のスピンが必要であり、更にこの26万個のスピン各々に対して、隣接結合ながら4~8個の結合回路が必要です。実装面積が増大し、かつオーバーヘッド時間もこれに比例して大きくなってしまいます。また、今回搭載したスピン数512個では22都市の巡回セールスマン問題を解くことが可能ですが、隣接結合LSIチップにおける既発表ではおよそ3万個のスピンを搭載したとされ、チップを2個使ったとしても16都市に相当した問題を解くのが限度でした。22都市の場合と16都市の場合のそれぞれの解を30 GOPSの従来型高性能CPUを想定して総当たり的に探索すると、前者ではおよそ1200年、後者ではおよそ12分が必要となります。

【今後の展望】

開発したLSIの高位記述をIP(知的財産)として提供し、企業などとの実証実験へ繋げることを探って行きます。

※なお、本発表の研究成果の一部は国立研究開発法人新エネルギー・産業技術総合開発機構(NEDO)の委託業務の結果得られたものです。

世界で初めての全結合型半導体アニーリング方式人工知能チップを開発 ~512スピン実装により22都市巡回セールスマン問題求解を瞬時に(ノイマン型高性能CPUではおよそ1200年が必要)~

図2 全結合半導体アニーリングLSIチップ

【学会発表】

学会名 IEEE 18th World Symposium on Applied Machine Intelligence and Informatics (SAMI 2020) (「IEEE 第18回応用機械知能と情報学に関する世界シンポジウム」):
http://conf.uni-obuda.hu/sami2020/
開催期間 2020年1月23日(木)~1月25日(土)
論文タイトル "AI Chips on Things for Sustainable Society: A 28-nm CMOS, Fully Spin-to-spin Connected 512-Spin, Multi-Spin-Thread, Folded Halved-Interaction Circuits Method, Annealing Processing Chip"
発表日 2020年1月25日(土)

【用語】

  1. 組み合わせ最適化問題:与えられた条件を満たす中で多数の選べる組合せの中から、ある価値において最も良いものをなるべく短時間で探し出す問題。
  2. アニーリング方式:下記5のイジングモデルを応用して組み合わせ最適化問題を解く場合、解へ至るためにスピンの状態をあえて乱雑にするために温度という項目を導入し、次いでこの温度下げることで正しい解を得る。この過程が焼きなまし(アニーリング)に相当するためにアニーリング方式と呼ばれる。
  3. 巡回セールスマン問題:セールスマンがある都市から出発し、全ての都市をちょうど一度ずつ訪問して出発点に戻ってくるときに、移動距離が最小になる経路を求める組合せ最適化問題。
  4. ノイマン型:記憶部に計算手続きのプログラムが内蔵され逐次処理方式で処理するというコンピュータの基本構成。
  5. イジングモデル:二つの状態をとるスピンが格子点に配置され、最隣接するスピン間の結合を考慮する模型。強磁性体のふるまいを説明できる。

サステナブル電子工学研究室のページ
河原教授のページ:https://www.tus.ac.jp/fac_grad/p/index.php?69ac

記事トップ

お問い合わせ

東京理科大学 広報課

e-mail: koho(アットマーク)admin.tus.ac.jp

〒162-8601 東京都新宿区神楽坂1-3

ページのトップへ