(57)【要約】【課題】大規模なイジングモデルの基底状態を探索可能な半導体装置において、半導体チップを接続するチップ間配線の配線量を抑えて半導体装置を安価かつ容易に製造可能にする。【解決手段】処理装置は、隣接するイジングボードの間でスピン値の送受信を行う相互作用演算モードと、イジングボードとの間でイジングモデルの制御情報の送受信を行う制御モードとを通信路を時分割に共有して実行する。【選択図】図１
2020160755.tif 000002
【特許請求の範囲】
【請求項１】
処理装置と、通信路を介して接続された複数のイジングボードとを有し、イジングモデルの基底状態探索を行う半導体装置であって、
前記処理装置は、
隣接する前記イジングボードの間でスピン値の送受信を行う相互作用演算モードと、前記イジングボードとの間で前記イジングモデルの制御情報の送受信を行う制御モードとを前記通信路を時分割に共有して実行することを特徴とする半導体装置。
【請求項２】
前記イジングボードは、
前記相互作用演算モードと前記制御モードを判別する振り分け部を更に有することを特徴とする請求項１に記載の半導体装置。
【請求項３】
前記振り分け部が前記相互作用演算モードと判別した場合は、
相互作用演算中に、隣接する前記イジングボード同士で前記イジングボードの端部に位置する前記スピン値を有するデータパケットを前記通信路を介してやり取りし、
前記振り分け部が前記制御モードと判別した場合は、
前記イジングモデルの前記制御情報として、前記イジングボードを特定するためのアドレス、前記スピン値、相互作用係数及び外部磁場係数を有する制御パケットを前記通信路を介してやり取りすることを特徴とする請求項２に記載の半導体装置。
【請求項４】
前記イジングボードは、
前記スピン値を持つスピンアレイを有するイジングコアと、
前記振り分け部と前記イジングコアとの間に設けられたバッファと、
前記振り分け部に接続された制御部と、を更に有し、
前記振り分け部は、
前記相互作用演算モードと判別した場合は、相互作用演算中の前記スピン値を前記バッファに入力し、
前記制御モードと判別した場合は、前記制御情報を前記制御部に入力することを特徴とする請求項３に記載の半導体装置。
【請求項５】
前記イジングボードは、
前記制御部に接続された制御レジスタを更に有し、
前記制御部は、
前記振り分け部から入力された前記制御パケットの前記アドレスを確認し、自身の前記イジングボードに割り当てられたアドレス範囲であれば、前記制御パケットの前記スピン値、前記相互作用係数及び前記外部磁場係数を前記制御レジスタに書き込み、
自身の前記イジングボードに割当たられた前記アドレス範囲でなければ、前記制御パケットを隣接する前記イジングボードに転送することを特徴とする請求項４に記載の半導体装置。
【請求項６】
前記処理装置は、
前記相互作用演算モードと前記制御モードに応じて、前記通信路を流れる前記制御パケットと前記データパケットとの比率を切り替えることを特徴とする請求項１に記載の半導体装置。
【請求項７】
前記処理装置は、
前記相互作用演算モードにおいては、前記データパケットの数を前記制御パケットの数よりも多く設定し、
前記制御モードにおいては、前記制御パケットの数を前記データパケットの数よりも多く設定することを特徴とする請求項６に記載の半導体装置。
【請求項８】
前記イジングボードは、
前記処理装置との間で情報の授受を行うホストインターフェースを更に有することを特徴とする請求項１に記載の半導体装置。
【請求項９】
前記処理装置は、
前記イジングモデルを前記イジングボードが一度に処理できるスピン数に応じて分割して、隣接する前記イジングボードに順次割り当てることを特徴とする請求項１に記載の半導体装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体装置に関する。
【背景技術】
【０００２】
イジングモデルは磁性体の振舞いを説明するための統計力学のモデルである。イジングモデルは＋１／−１（ないしは、０／１、上／下）の２値をとるスピンと、スピン間の相互作用を示す相互作用係数と、スピン毎にある外部磁場係数とで定義される。
【０００３】
イジングモデルは与えられたスピン配列、相互作用係数、及び、外部磁場係数から、その時のエネルギーを計算することができる。イジングモデルのエネルギー関数は一般的に（数１）で表わされる。
【０００４】
【数１】
2020160755.tif 000003
【０００５】
なお、σｉ，σｊはそれぞれｉ番目とｊ番目のスピンの値、Ｊｉ，ｊはｉ番目とｊ番目のスピンの間の相互作用係数、ｈｉはｉ番目のスピンに対する外部磁場係数、σはスピンの配列を表わすものとする。
【０００６】
数１において、第一項は、スピン間の相互作用に起因するエネルギーを計算するものである。一般的にイジングモデルは無向グラフとして表現され、ｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を区別することはない。そのため、第一項ではｉ＜ｊを満たすσｉ，σｊの組み合わせについて、相互作用係数の影響を計算している。また第二項は、各スピンに対する外部磁場に起因するエネルギーを計算するものである。
【０００７】
イジングモデルの基底状態探索とは、イジングモデルのエネルギー関数を最小化するスピンの配列を求める最適化問題である。相互作用係数及び外部磁場係数の値域に制限を付けないときには、トポロジが非平面グラフになるイジングモデルの基底状態を求めることはＮＰ困難問題であることが知られている。
【０００８】
イジングモデルの基底状態探索は、元々イジングモデルが対象としていた磁性体の振る舞いを説明することのみならず、様々な用途に用いられている。これは、イジングモデルが相互作用に基づく最も単純なモデルであり、同様に相互作用に起因する様々な事象を表現する能力を持っているためであると言える。例えば、特許文献１には、イジングモデルの基底状態探索を用いて、職場組織などの集団におけるストレス度を推定する方法が開示されている。
【０００９】
また、イジングモデルの基底状態探索は、ＮＰ困難なグラフ問題として知られている最大カット問題とも対応している。このようなグラフ問題は、ソーシャルネットワークにおけるコミュニティの検出や、画像処理におけるセグメンテーションなど、幅広い応用を持っている。そのため、イジングモデルの基底状態探索を行うソルバがあれば、このような様々な問題に適用することができる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２０１２−２１７５１８号公報
【特許文献２】国際公開第２０１２／１１８０６４号公報
【特許文献３】特開平３−８０３７９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
イジングモデルの基底状態を求めることは、上述のようにＮＰ困難問題であることから、イノマン型コンピュータで解くことは計算時間の面で困難を伴う。ヒューリステックを導入して高速化を図るアルゴリズムも提案されているものの、イノマン型コンピュータではなく物理現象をより直接的に利用した計算、すなわちアナログコンピュータでイジングモデルの基底状態を高速に求める方法が提案されている（例えば、特許文献２参照）。
【００１２】
このような装置では、解くべき問題に対応した並列度が必要になってくる。イジングモデルの場合では、基底状態を探索すべきイジングモデルのスピン数に対応して、それぞれ１つのスピンや、当該スピンにおける他のスピンとの相互作用を表現する素子（以下、これを単位素子と呼ぶ）が必要となる。
【００１３】
例えば、特許文献３に開示された装置では、スピンとレーザを対応させているため、スピン数に比例した数のレーザが必要となる。すなわち、多数の単位素子を搭載可能なスケーラビリティの高さが必要となる。
【００１４】
以上のことを考慮した場合、単位素子を規則的に多数並べて実現できる半導体装置のような固体素子でイジングモデルの基底状態探索を行えることが望ましい。特に、ＤＲＡＭ（Dynamic Random Access Memory）やＳＲＡＭ（Static Random Access Memory）などの記憶装置に代表されるようなアレイ構造であり、かつ集積性を高められるように単位要素が単純な構造であることが望ましい。
【００１５】
ところで、このような半導体装置として、例えば、多数のスピンを含む大規模なイジングモデルの基底状態を探索可能な半導体装置を構築するためには、単位素子をスピン数に応じた数だけ半導体チップに搭載する必要がある。
【００１６】
しかし、このような半導体装置は、チップサイズが大きく、また製造コストも高くなる。従って、このような半導体装置を実現するに際しては、ある程度の数の単位素子が搭載された半導体チップを複数接続するようにして構築することが望ましい。
【００１７】
しかしながら、このような方法によると、半導体チップ間の配線量が大きくなるために製造コストが増大したり、実装上の困難が生じたりする問題がある。
【００１８】
本発明の目的は、大規模なイジングモデルの基底状態を探索可能な半導体装置において、半導体チップを接続するチップ間配線の配線量を抑えて半導体装置を安価かつ容易に製造可能にすることにある。
【課題を解決するための手段】
【００１９】
本発明の一態様の半導体装置は、処理装置と、通信路を介して接続された複数のイジングボードとを有しイジングモデルの基底状態探索を行う半導体装置であって、前記処理装置は、隣接する前記イジングボードの間でスピン値の送受信を行う相互作用演算モードと、前記イジングボードとの間で前記イジングモデルの制御情報の送受信を行う制御モードとを前記通信路を時分割に共有して実行することを特徴とする。
【発明の効果】
【００２０】
本発明の一態様によれば、大規模なイジングモデルの基底状態を探索可能な半導体装置において、半導体チップを接続するチップ間配線の配線量を抑えて半導体装置を安価かつ容易に製造することができる。
【図面の簡単な説明】
【００２１】
【図１】情報処理装置の全体構成を示すブロック図である。
【図２】イジングボードの構成を示すブロック図である。
【図３】イジングボードの別の構成を示すブロック図である。
【図４】イジングコアの構成を示すブロック図である。
【図５】スピンユニットの説明に供する概念図である。
【図６】スピンユニットの説明に供する概念図である。
【図７】スピンユニットの説明に供する概念図である。
【図８】スピンユニットの構成を示すブロック図である。
【図９】スピンユニットの構成を示すブロック図である。
【図１０】スピンユニットの配置例を示す概念図である。
【図１１】スピンユニット間の配線例を示す概念図である。
【図１２Ａ】入力のイジングモデルとイジングボードの対応関係を示す概念図である。
【図１２Ｂ】入力のイジングモデルとイジングボードの対応関係を示す概念図である。
【図１３】イジングボード間の結線を示す概念図である。
【図１４】イジングボード間の制御信号の伝送路を示す概念図である。
【図１５】イジングボード間で授受されるデータを示す概念図である。
【図１６】情報処理装置の処理の流れを示すフローチャートである。
【図１７】振り分け部の構成例を示すブロック図である。
【図１８】相互作用動作中のパケット振り分け例を示す概念図である。
【図１９】ボード間通信路を流れるパケットの時間変化を示す概念図である。
【発明を実施するための形態】
【００２２】
以下、図面を用いて実施形態について説明する。
【００２３】
＜有向グラフに拡張したイジングモデル＞
実施形態では、イジングモデルを拡張した、以下の（数２）で示されるモデルを、これ以降イジングモデルと呼ぶものとする。
【００２４】
【数２】
2020160755.tif 000004
【００２５】
（数１）で示したイジングモデルとの違いは、（数２）では有向グラフで示されるような相互作用が許されることにある。一般的にイジングモデルはグラフ理論では無向グラフとして描画することができる。それは、イジングモデルの相互作用は、ｉ番目スピンからｊ番目スピンへの相互作用係数Ｊｉ，ｊとｊ番目スピンからｉ番目スピンへの相互作用係数Ｊｊ，ｉとを区別していないことによる。
【００２６】
実施形態はイジングモデルを拡張し、Ｊｉ，ｊとＪｊ，ｉとを区別しても適用できるため、本実施の形態でも有向グラフ化したイジングモデルを取り扱う。なお、無向グラフのイジングモデルを有向グラフのイジングモデルで取り扱う場合には、単にＪｉ，ｊとＪｊ，ｉとの双方向に同じ相互作用係数を定義することで可能である。この場合、同じモデルでも（数１）のエネルギー関数に対して（数２）のエネルギー関数ではエネルギーの値が２倍になる。
【００２７】
＜情報処理装置の全体構成＞
図１は、実施の形態による情報処理装置（半導体装置）の全体構成を示す。この情報処理装置１は、パーソナルコンピュータやワークステーション又はサーバなどから構成され、システムバス２を介して構成されたＣＰＵ（処理装置）３、メモリ４、記憶装置５及び１つ又は複数のイジングボード６ａを備える。また、システムバス２とは直接接続せず、イジングボード６ａとボード間通信路１８を介して情報処理装置１に接続されるイジングボード６ｂを備える。
【００２８】
記憶装置５には、情報処理装置１が解くべき単一の問題の問題データ７が格納され、メモリ４には、問題変換プログラム８及びイジングボード制御プログラム９が格納される。問題変換プログラムは、かかる問題を必要に応じて単一のイジングモデル形式の問題に変換すると共に、かかるイジングモデル形式の問題を必要に応じて複数の部分問題に分割し、これらの部分問題を個々のイジングボード６ａおよび６ｂにそれぞれ振り分けるプログラムである。またイジングボード制御プログラム９は、個々のイジングボード６ａおよび６ｂにおいて対応する部分問題を解くための制御を行うためのプログラムである。なお部分問題は、それ自体が他の部分問題と独立した単一のイジングモデル形式の問題である。
【００２９】
＜イジングボードの構成＞
イジングボード６ａは、イジングモデルの基底状態探索を行う専用ハードウェアであり、例えば画面描画処理のための専用ハードウェアであるＧＰＵ（Graphics Processing Unit）のように、情報処理装置１に装着する拡張カードの形態を取る。
【００３０】
イジングボード６ａは、図２に示すように、イジングコア１９、送信部３１、受信部３７バッファ３２、振り分け部３３、制御部３４、制御レジスタ３５、乱数発生器１７とホストＩ／Ｆ３６を備える。ホストＩ／Ｆ３６およびシステムバス２（図１）を介してＣＰＵ３（図１）との間でコマンドや情報の授受を行う。
【００３１】
イジングボード６ａは隣接するイジングボード６ａ及びイジングボード６ｂと接続するために、上下左右に送信部３１及び受信部３７を備える。送信部３１及び受信部３７の動作については後述するが、本実施の形態においては相互作用演算中に隣接するイジングボード同士６ａ及び６ｂでイジングコア１９の端部に位置するスピンσｉの値をやり取りするほか、ホストＩ／Ｆ３６を持たないボードに対してスピン・相互作用係数、および外部磁場係数を読み書きするための制御情報をやり取りする。
【００３２】
振り分け部３３は、受信部３７から入力を受け取り、相互作用演算中のスピン値であるか、隣接するイジングボード６ａおよび６ｂから転送された制御情報かを判別し、前者であればスピン値をバッファ３２に入力し、後者であれば制御部３４に入力する。バッファ３２はイジングボード６ａに隣接するボード上にあるイジングコア１９の端部のスピン値を格納しており、自身のイジングボード６ａ上のイジングコア１９の端部に位置するスピンからみて隣接するスピンのように接続されている。
【００３３】
なお、図１３と図１４を用いて後述するように、相互作用演算中のスピン値を伝送する結線と制御情報を伝送する論理的な結線は異なる。本実施形態では図１４で示すように制御情報が各イジングボード６ａ及び６ｂから見て決まった方向に伝達されることを想定している。このため、各イジングボード６ａ及び６ｂの下方向及び右方向の受信部３７に入力されるデータは常にデータパケット５１（後述）となるので振り分け部３３を省略して直接バッファ３２に入力する構成をとっている。
【００３４】
制御部３４は振り分け部３３から入力された制御パケット５０（後述）のアドレスを確認し、自身のイジングボードに割り当てられたアドレス範囲であれば、制御パケット５０のデータを制御レジスタ３５またはイジングコア１９上のメモリに対する読書きを行う。一方、自身のイジングボードに割当たられたアドレス範囲でなければ、受け取った制御パケットを送信部３１ｂおよび３１ｃに入力し、隣接するイジングボード６ａ及び６ｂに転送する。
【００３５】
制御レジスタ３５はイジングコア１９の動作状態を格納したり、後述する振り分け部３３の動作モードを設定する。乱数発生器１７はイジングコア１９の相互演算動作において、局所解を避けるために必要な乱数ビット列を発生させる。イジングコア１９はイジングモデルの相互作用演算を実行する部分で、詳細は図４を用いて後述する。
【００３６】
図３はイジングボード６ａの別の構成を図示したものである。図３のイジングボード６ｂは、図２のイジングボード６ａと異なりホストＩ／Ｆ３６を持たない。イジングボード６ｂは隣接するイジングボード６ａから制御情報を受け取ってイジングコア１９に対してスピン値、相互作用係数および外部磁場係数の読み書きを行う。ホストＩ／Ｆ３６を除いた部分は図２のイジングボード６ａと同様である。
【００３７】
＜イジングコアの構成＞
図４は、イジングコア１９の概略構成を示す。イジングコア１９は、ＣＭＯＳ（Complementary Metal-Oxide Semiconductor）集積回路やＦＰＧＡ(Field Programmable Gate Array)上の論理回路として実装されていることを想定して説明するが、他の固体素子でも実現可能である。
【００３８】
イジングコア１９は、スピンアレイ２０にリード／ライトを行うためのＳＲＡＭ互換インタフェース３０としてアドレスバス３１、データバス３２、Ｒ／Ｗ制御線３３及びＩ／Ｏクロック線３４を備える。またイジングチップ１３は、イジングモデルの基底状態探索の制御を行うための相互作用制御インタフェース３５として、相互作用アドレス線３６及び相互作用クロック線３７をも備える。
【００３９】
イジングコア１９では、イジングモデルのスピンσｉ、相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉをすべてスピンアレイ２０内のメモリセルに記憶する情報で表現する。スピンσｉの初期状態の設定や基底探索完了後の解読み出しはＳＲＡＭ互換インターフェース３０を介して行う。またイジングコア１９では、基底状態を探索すべきイジングモデルをスピンアレイ２０に設定するための相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉのリード／ライトもＳＲＡＭ互換インターフェース３０を介して行う。
【００４０】
そして、イジングチップ１３にスピンσｉ、相互作用係数Ｊｉ，ｊ又は外部磁場係数ｈｉをリード／ライトする場合、対応するアドレスがコントローラ１５からアドレスバス３１を介してＩ／Ｏアドレスデコーダ２１に与えられ、これらスピンσｉ、相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉのリード／ライトを制御するＲ／Ｗ制御信号がコントローラ１５からＲ／Ｗ制御線３３を介してＩ／Ｏドライバ２２に与えられる。
【００４１】
＜スピンアレイの構成＞
スピンアレイ２０は、１個のスピンσｉ並びにそれに付随する相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉの保持と、基底状態探索演算とを実現するスピンユニットを基本構成単位として、スピンユニットを多数個並べた構成を有する。
【００４２】
図５は、スピンユニット４０を複数個並べることで、３次元格子状のトポロジを持つイジングモデルを構成する例を示している。図５の例は、３（Ｘ軸方向）×３（Ｙ軸方向）×２（Ｚ軸方向）の大きさの３次元格子である。座標軸の定義は図示した通り、図面右方向をＸ軸、図面下方向をＹ軸、図面奥行き方向をＺ軸としているが、この座標軸は実施の形態の説明上便宜的に必要なだけであり、本発明とは関係しない。
【００４３】
３次元格子以外のトポロジ、例えばツリー状のトポロジなどを利用する場合には、座標軸とは別にツリーの段数等で表現することになる。図５の３次元格子状のトポロジにおいて、スピン間の相互作用をグラフとしてとらえると、最大で次数５のスピン（頂点）が必要となる。なお、外部磁場係数の接続も含めて考えると、最大で次数６が必要となる。
【００４４】
図５に示す１個のスピンユニット４０には、隣接するスピン（例えば隣接するスピンが５個の場合σｊ、σｋ、σｌ、σｍ、σｎ）の値が入力される。このためスピンユニット４０は、これら入力する隣接するスピンの値を保持するためのメモリセルを有している。またスピンユニット４０は、かかるスピンの値に加え、外部磁場係数と、上述した隣接するスピンとの相互作用係数（隣接する５スピンとの相互作用係数Ｊｊ，ｉ、Ｊｋ，ｉ、Ｊｌ，ｉ、Ｊｍ，ｉ、Ｊｎ，ｉ）とをそれぞれ保持するメモリセルをも有している。
【００４５】
ところで、先に述べたようにイジングモデルは一般的に無向グラフで表現される相互作用を有している。上述した（１）式では、相互作用を表わす項として、Ｊｉ，ｊ×σｉ×σｊがあるが、これはｉ番目スピンからｊ番目スピンへの相互作用を示している。この場合、一般的なイジングモデルではｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を区別することはない。
【００４６】
つまり、Ｊｉ，ｊとＪｊ，ｉは同一である。しかし、本実施の形態のイジングコア１９では、先に述べたようにこのイジングモデルを有向グラフに拡張し（数２）、ｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を非対称にすることを実現している。これにより、モデルの表現能力が高まり、多くの問題をより小規模のモデルで表現することが可能になる。
【００４７】
そのため、１個のスピンユニットをｉ番目スピンσｉと考えた時に、このスピンユニット４０が保持する相互作用係数であるＪｊ，ｉ、Ｊｋ，ｉ、Ｊｌ，ｉ、Ｊｍ，ｉ、Ｊｎ，ｉは、隣接するｊ番目、ｋ番目、ｌ番目、ｍ番目、ｎ番目のスピンσｊ、σｋ、σｌ、σｍ、σｎから、ｉ番目スピンσｉへの相互作用を決めるものである。このことは、図５において、スピンユニット４０に含まれている相互作用係数が対応する矢印（相互作用）が、図示されているスピンユニット４０の外部のスピンから、スピンユニット４０の内部のスピンに向かっていることに対応している。
【００４８】
＜スピンユニットの構成＞
スピンユニット４０の一構成例を図８及び図９を用いて説明する。
スピンユニット４０は２つの側面をもっており、便宜上、図８及び図９に分けて説明するが、１個のスピンユニット４０は図８及び図９の構成の双方を含む。図８はスピンユニット４０間の相互作用を実現するための回路を示し、図９はスピンユニット４０が有するメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１にイジングコア１９外からアクセスするためのインタフェースであるビット線４１とワード線４２とに注目してスピンユニット４０の構成を図示したものである。
【００４９】
スピンユニット４０は、イジングモデルのスピンσｉ、相互作用係数Ｊｊ，ｉ〜Ｊｎ，ｉ及び外部磁場係数ｈｉを保持するために、複数の１ビットのメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１を備えている。なお、メモリセルＩＳ０及びＩＳ１、メモリセルＩＵ０及びＩＵ１、メモリセルＩＬ０及びＩＬ１、メモリセルＩＲ０及びＩＲ１、メモリセルＩＤ０及びＩＤ１、並びに、メモリセルＩＦ０及びＩＦ１は、それぞれ２個１組で役割を果たすものであるため、適宜、これらをそれぞれまとめてメモリセル対ＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ又はＩＦｘと略記する（図６参照）。
【００５０】
ここで、スピンユニット４０はｉ番目のスピンを表現するものとして説明を行う。メモリセルＮはスピンを表現するためのメモリセルであり、スピンの値を保持する。スピンの値はイジングモデルでは＋１／−１（＋１を上、−１を下とも表現する）であるが、これをメモリセルが保持可能な２値である０／１に対応させる。例えば、＋１を１、−１を０に対応させる。
【００５１】
図６を用いて、スピンユニット４０が有するメモリセル対ＩＳｘ、ＩＵｘ、ＩＬｘ、ＩＲｘ、ＩＤｘ及びＩＦｘと、図５に示したイジングモデルのトポロジとの対応関係を示す。メモリセル対ＩＳｘは外部磁場係数を記憶する。また、メモリセル対ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘは、それぞれ相互作用係数を記憶する。具体的に、メモリセル対ＩＵｘは上側のスピン（Ｙ軸方向で−１）、メモリセル対ＩＬｘは左側のスピン（Ｘ軸方向で−１）、メモリセル対ＩＲｘは右側のスピン（Ｘ軸方向で＋１）、メモリセル対ＩＤｘは下側のスピン（Ｙ軸方向で＋１）、メモリセル対ＩＦｘは奥行き方向に接続するスピン（Ｚ軸方向で＋１ないしは−１）との相互作用係数をそれぞれ記憶する。
【００５２】
また、イジングモデルを有向グラフとして捉えた場合に、あるスピンから見ると他のスピンが自スピンに及ぼす影響の係数を持つことになる。自スピンが他のスピンに与える影響の係数は、それぞれの他のスピンに属する。すなわち、このスピンユニット４０は最大で５個のスピンと接続される。本実施の形態のイジングコア１９では、外部磁場係数及び相互作用係数として＋１／０／−１の３値に対応する。そのため、外部磁場係数及び相互作用係数を表わすためには、それぞれ２ビットのメモリセルが必要となる。
【００５３】
メモリセル対ＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘは、末尾の数字が０と１の２つのメモリセル（例えばメモリセル対ＩＳｘの場合にはメモリセルＩＳ０及びＩＳ１）の組合せで、＋１／０／−１の３値を表現する。例えば、メモリセル対ＩＳｘの場合には、メモリセルＩＳ１で＋１／−１を表現し、メモリセルＩＳ１が保持する値が１の時は＋１、メモリセルＩＳ１が保持する値が０の時には−１を表す。
【００５４】
これに加えて、メモリセルＩＳ０が保持する値が０の時には外部磁場係数を０と見なし、メモリセルＩＳ０が保持する値が１の時にはメモリセルＩＳ１が保持する値で決まる＋１／−１のいずれかを外部磁場係数とする。外部磁場係数が０の時は外部磁場係数をディセーブルしていると考えれば、メモリセルＩＳ０に保持された値は外部磁場係数のイネーブルビットであると言うことができる（ＩＳ０＝１の時に、外部磁場係数がイネーブルされる）。相互作用係数を記憶するメモリセル対ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘも同様に係数とビットの値とを対応させている。
【００５５】
スピンユニット４０内のメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０及びＩＦ１は、それぞれイジングコア１９の外部からリード／ライト可能でなければならない。そのために、図９に示すように、スピンユニット４０はビット線４１とワード線４２とをそれぞれ有している。
【００５６】
そしてイジングコア１９では、図１０に示すように、スピンユニット４０が半導体基板上にタイル状に並べられてビット線４１とワード線４２とが接続されており、Ｉ／Ｏアドレスデコーダ２１とＩ／Ｏドライバ２２とでこれらのスピンユニット４０を駆動、制御又は読み出しすることにより、一般的なＳＲＡＭ（Static Random Access Memory）と同様にスピンユニット４０内のメモリセルをイジングコア１９のＳＲＡＭ互換インタフェース３０でリード／ライトすることができるようになされている。
【００５７】
なお、図１０上で表現されているスピンユニット（ＮxyzというようにＸ軸、Ｙ軸及びＺ軸上の位置によって符号を付与している）が、３次元格子のトポロジでどの頂点に対応するかを図７に示す。３×３×２の３次元格子頂点を２次元平面上に配置するために、Ｘ軸方向の格子頂点配列の間隔にＺ軸方向の格子頂点配列の各格子頂点を挿入するように配置している。すなわち、図１０の２次元平面上でのＹ軸方向（図面下側がＹ軸の正方向）にはＮx0z、Ｎx1z、Ｎx2zというように配置されるが、Ｘ軸方向（図面右側がＸ軸の正方向）にはＮ0y0、Ｎ0y1、Ｎ1y0、Ｎ1y1、Ｎ2y0、Ｎ2y1というように、Ｚ軸方向座標が０と１のスピンユニットが交互に配置される。
【００５８】
またスピンユニット４０は同時に更新を行うために、相互作用を計算して次のスピンの状態を決定するための回路を、スピンユニット４０毎に独立して持っている。図８では、スピンユニット４０は、外部とのインタフェースとして、信号線ＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦ，ＯＮ，ＤＩＦＦＮ及びＲＮＤを有する。
【００５９】
信号線ＯＮは、当該スピンユニット４０のスピンの値を他のスピンユニット４０（図５のトポロジで隣接するユニット）に出力するインタフェースである。信号線ＮＵ，ＮＬ，ＮＲ，ＮＤ及びＮＦは、それぞれ他のスピンユニット４０（図５のトポロジで隣接するユニット）が保持するスピンの値を入力するためのインタフェースである。信号線ＮＵは上側のスピン（Ｙ軸方向で−１）、信号線ＮＬは左側のスピン（Ｘ軸方向で−１）、信号線ＮＲは右側のスピン（Ｘ軸方向で＋１）、信号線ＮＤは下側のスピン（Ｙ軸方向で＋１）、信号線ＮＦは奥行き方向に接続するスピン（Ｚ軸方向で＋１ないしは−１）からの入力である。
【００６０】
スピンユニット４０では隣接スピンとの間でエネルギーを最小化するようにスピンの次状態を決定するが、それは隣接スピンと相互作用係数の積、及び、外部磁場係数を見たときに、正の値と負の値のどちらが支配的か判断することと等価である。例えば、ｉ番目スピンσｉに、スピンσｊ、σｋ、σｌ、σｍ及びσｎが隣接しているとして、スピンσｉの次状態は以下のように決まる。
【００６１】
まず、隣接スピンの値はσｊ＝＋１、σｋ＝−１、σｌ＝＋１、σｍ＝−１、σｎ＝＋１とし、相互作用係数はＪｊ，ｉ＝＋１、Ｊｋ，ｉ＝＋１、Ｊｌ，ｉ＝＋１、Ｊｍ，ｉ＝−１、Ｊｎ，ｉ＝−１、外部磁場係数ｈｉ＝＋１とする。このとき、相互作用係数と隣接スピンの積、及び、外部磁場係数をそれぞれ並べると、σｊ×Ｊｊ，ｉ＝＋１、σｋ×Ｊｋ，ｉ＝−１、σｌ×Ｊｌ，ｉ＝＋１、σｍ×Ｊｍ，ｉ＝＋１、σｎ×Ｊｎ，ｉ＝−１、ｈｉ＝＋１となる。外部磁場係数は、常に値が＋１のスピンとの相互作用係数と読み替えて良い。
【００６２】
ここで、ｉ番目のスピンと隣接スピンとの間での局所的なエネルギーは、前述した係数にそれぞれｉ番目スピンの値を乗じて、さらに符号を反転させたものになる。例えば、ｊ番目スピンとの間での局所的なエネルギーは、ｉ番目スピンを＋１とした時には−１、ｉ番目スピンを−１としたときには＋１となるので、ｉ番目スピンを＋１にするほうが、ここでの局所的なエネルギーを小さくする方向に働く。
【００６３】
このような局所的なエネルギーを全ての隣接スピン間と外部磁場係数について考えたときに、ｉ番目スピンを＋１／−１のどちらにしたほうがエネルギーを小さくできるかを計算する。これは、先程示した相互作用係数及び隣接スピンの積と、外部磁場係数とをそれぞれ並べたものにおいて、＋１と−１のどちらが多いか数えれば良い。先程の例では、＋１が４個、−１が２個である。仮に、ｉ番目スピンを＋１とすると、エネルギーの総和は−２、ｉ番目スピンを−１とするとエネルギーの総和は＋２になる。よって、＋１の個数が多い時にはｉ番目スピンの次状態を＋１とし、−１の個数が多い時にはｉ番目スピンの次状態を−１にするという多数決で、エネルギーを最小化するｉ番目スピンの次状態を決定することができる。
【００６４】
図８に示した論理回路４６は、上述の相互作用を行うための回路である。まず、隣接スピンの状態と、相互作用係数の＋１／−１を示すメモリセルＩＵ１，ＩＬ１，ＩＲ１，ＩＤ１，ＩＦ１が保持する値との排他的論理和の否定（ＸＮＯＲ）をＸＮＯＲ回路４７で求める。これにより、その相互作用だけを見た時にエネルギーを最小化するスピンの次状態を計算することができる（＋１は１、−１は０にエンコードされているものとする）。
【００６５】
もし、相互作用係数が＋１／−１だけであれば、ＸＮＯＲ回路４７の出力のうち＋１／−１のどちらが多いかを多数決論理回路４４において多数決論理で判定すればスピンの次状態を決定することができる。外部磁場係数に関しては、常に状態＋１のスピンとの相互作用係数に相当するものと考えれば、単に外部磁場係数の値がスピンの次状態を決定する多数決論理回路４４に入力すべき値となる。
【００６６】
次に、係数０の実現方法について考える。ｎ入力の多数決論理ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ）があるとき、以下の命題は真であると言える。まず、入力Ｉ１，Ｉ２，Ｉ３，……，Ｉｎの複製Ｉ’１，Ｉ’２，Ｉ’３，……，Ｉ’ｎがあるとする（任意のｋについて、Ｉｋ＝Ｉ’ｋである）。このとき、ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ）の出力は、複製もあわせて入力したｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ、Ｉ’１，Ｉ’２，Ｉ’３，……，Ｉ’ｎ）と等しい。つまり、各入力変数をそれぞれ２個ずつ入れても、出力は不変である。さらに、入力Ｉ１、Ｉ２、Ｉ３，……，Ｉｎの他に、もう一つの入力Ｉｘと、その反転Ｉｘがあるとする。このとき、ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ，Ｉｘ，反転Ｉｘ）の出力は、ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ）と等しい。つまり、入力変数とその反転を入力すると、多数決においてその入力変数の影響をキャンセルするように働く。多数決論理のこの性質を利用して係数０を実現する。
【００６７】
具体的には、図８に示すように、ＸＯＲ回路４８を利用して、係数のイネーブルを決めるビット（ビットセルＩＳ０，ＩＵ０，ＩＬ０，ＩＲ０，ＩＤ０及びＩＦ０にそれぞれ保持されたビット）の値により、多数決論理回路４４に、先に述べたスピン次状態の候補となる値の複製か、その反転を同時に入力する。例えば、メモリセルＩＳ０が保持するビットの値が０の場合、メモリセルＩＳ１が保持するビットの値と、メモリセルＩＳ１が保持するビットの値を反転させた値が同時に多数決論理回路４４に入力されるので、外部磁場係数の影響は無い（外部磁場係数が０に相当する）ことになる。また、メモリセルＩＳ０が保持するビットの値が１の場合には、メモリセルＩＳ１が保持するビットの値と、その値と同じ値（複製）が同時に多数決論理回路４４に入力されることになる。
【００６８】
上述したスピン間の相互作用によるエネルギー最小化で、適用されたイジングモデルの基底状態探索を実現することができるが、これだけでは局所最適解に陥ってしまう可能性がある。基本的に、エネルギーを小さくする方向の動きしかないため、一旦局所最適解に陥るとそこから抜け出すことができず、大域最適解に到達しない。そのため、局所最適解から脱出するための作用として、スピンを表現するメモリセルの値を確率的に反転されるために、スピンユニット４０はインタフェースとしてＲＮＤ線４９を有する。
【００６９】
そしてスピンユニット４０には、上述のように乱数発生器１７（図２）から乱数注入線３８（図４）を介してスピンアレイ２０（図４）に与えられた乱数がこのＲＮＤ線４９を介して与えられ、この乱数がＸＯＲ回路４５に入力することで、スピンの値が確率的に反転される。
【００７０】
なお、図８に示したスピンユニット４０のインタフェースであるＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦのスピンユニット４０間の配線例を図１１に示す。この図１１は、「Ｎxyz」というある１個のスピンユニット４０に注目したときに、図５に示すようなトポロジを図１０のようなスピンユニット配置で実現するために必要な配線を示している。このような配線をスピンユニット４０ごとに行うことで、図５のトポロジを実現することができる。
【００７１】
＜イジングボード間の配線方法＞
図１２Ａは、情報処理システム１に入力される入力データであるイジングモデルと、イジングモデルの各部分の計算を行うイジングボード６ａ及び６ｂとの対応を示す模式図である。イジングモデルは、各イジングボード６ａ及び６ｂが一度に処理できるスピンの数に応じて分割され、隣接するボードに順次割り当てられる。このとき、前述の通りＣＰＵ３上のイジングボード制御プログラム９がこのイジングモデルの分割処理を担当し、割当先に応じて適切な書き込み先を決定したうえでイジングボード６ａ上のホストＩ／Ｆ３６を介して書き込む。このときは、ＣＰＵ３から見て各イジングボード６ａおよび６ｂ上のスピンアレイ２０に含まれるスピンに対してアドレスを付与して管理することが望ましい。
【００７２】
一方で、図１２Ｂに示すように相互作用動作の実施中には、スピンアレイ２０の境界部分に位置するスピンの情報を隣接するイジングボード６ａ及び６ｂ同士でやり取りする。このとき、イジングボード６ａ及び６ｂ上の送信部３１と受信部３７は隣接するイジングボード６ａ及び６ｂ間で１対１で接続されるため、アドレスの情報を必要とせず、かえってアドレスの情報を含まないことによってアドレスの伝送にかかる帯域や、アドレス情報の処理にかかる回路上の遅延時間を削減できる。
【００７３】
図１３はイジングボード６ａおよび６ｂ間の結線を示す模式図である。３ｘ３のイジングボード６ａ及び６ｂをタイル状に接続する例を示している。ＣＰＵ３とイジングボード６ａはシステムバス２を介して接続される。イジングボード６ａ及び６ｂの間はボード間通信路１８を介して接続する。隣接ボード間を上下左右にそれぞれ接続し、端部のボードは逆側の端部のボードと接続する所謂２次元トーラスと呼ばれる構成となっている。この接続構成は物理的な結線を示すと同時に、相互作用動作を実施する際にそのまま使用される。
【００７４】
図１４はＣＰＵ３からスピンの初期値、相互作用係数、外部磁場係数を書き込んだり、各イジングボード６ａおよび６ｂ上の制御レジスタ３５を読み書きする制御用通信の際に用いる論理的な接続関係を示した図である。これは図１３の結線から一部を除去したものとなっており、所謂ツリー状の構成となっている。制御用としてより単純な接続を用いることで、宛先アドレスまでのルーティングを単純化することができる。
【００７５】
＜制御用通信と相互作用中の通信＞
図１５は制御用の通信と相互作用時の通信の内容を示した模式図である。制御パケット５０は制御用の通信の内容を示したものである。ＣＰＵ３から見てアクセス対象となるイジングボード６ａおよび６ｂを特定するためのアドレス情報を含み、これに読み書きすべき内容であるスピン値・相互作用係数・外部磁場係数の情報が続く。一方、データパケット５１は相互作用時の通信の内容を示したものであり、前述のとおりイジングボード６ａおよび６ｂ間が１対１で通信するため、アドレス情報を排してスピンアレイ端部のスピン値のみを送受信することで帯域を最大限活用している。
【００７６】
＜制御フロー＞
図１６は情報処理装置１の使用に関する全体の動作フローを示したものである。まず、ステップＳ１５０１で計算開始に先立って、各イジングボード６ａおよび６ｂをリセットする。続いて、ステップＳ１５０２でＣＰＵ３から各イジングボード６ａおよび６ｂに対して、スピン初期値・相互作用係数値および外部磁場係数値を書き込む。この際、ＣＰＵ３がイジングボード制御プログラム９を実行して計算対象となるイジングモデルの分割処理を行い、分割の結果得られた宛先のイジングボード６ａおよび６ｂに対応するアドレスを付与する。ＣＰＵ３はアドレスを付与した制御パケット５０を生成し、システムバス２を介してイジングボード６ａに書き込む。
【００７７】
イジングボード６ａは受信部３７を通してパケットを受信し、振り分け部３３に入力する。振り分け部３３は受け取った制御パケットのアドレスを確認し、自身に割り当てられたアドレスの範囲であれば制御部３４を介してイジングコア１９内の該当するスピンユニットに値を書き込む。受け取ったデータが自身に割り当てられたアドレスの範囲でなければ受け取ったデータを制御部３４を介して送信部３１ｂ及び３１ｃに入力し、隣接するイジングボード６ｂに転送する。
【００７８】
書き込み完了後、ステップＳ１５０３でＣＰＵ３は相互作用動作を開始するにあたってスピン値の伝送に適した転送モードに切り替えるよう各イジングボード６ａおよび６ｂに通知する。通知は各イジングボード６ａ及び６ｂの制御レジスタ３５に対する書き込みの形で行う。
【００７９】
その後、ステップＳ１５０４でＣＰＵ３は相互作用動作を開始するよう各イジングボード６ａ及び６ｂに通知する。各イジングボード６ａ及び６ｂは夫々のイジングコア１９に対して相互作用クロックを入力し、相互作用動作を開始する。また、各イジングボード６ａ及び６ｂは夫々の制御レジスタ３５に対して相互作用演算中であることを示す値を設定する。相互作用動作が実行されている間、ＣＰＵ３は定期的に各イジングボード６ａ及び６ｂの制御ジスタ３５の値を読み取り、相互作用動作が完了したかどうかを確認する。
【００８０】
相互作用動作の完了後、ステップＳ１５０５でＣＰＵ３は制御用通信に適した転送モードに切り替えるよう各イジングボード６ａ及び６ｂに通知する。ステップＳ１５０３と同様、通知は各イジングボード６ａ及び６ｂの制御レジスタ３５に対する書き込みの形で行う。
【００８１】
その後、ステップＳ１５０６でＣＰＵ３は計算結果であるスピン値を読み取る。ＣＰＵ３はすべてのスピンユニットのスピン値に対応するアドレスを含んだ値の読み取りを要求する制御パケット生成し、システムバス２を通じてイジングボード６ａに書き込む。ステップＳ１５０２と同様に、イジングボード６ａは受信部３７を通してパケットを受信し、振り分け部３３に入力する。
【００８２】
振り分け部３３は受け取った制御パケットのアドレスを確認し、自身に割り当てられたアドレスの範囲であれば制御部３４を介してイジングコア１９内の該当するスピンユニットの値を読み取り、制御パケットに読み取った値を書き込んで送信部３１を介してＣＰＵ３に応答する。受け取ったデータが自身に割り当てられたアドレスの範囲でなければ受け取ったデータを制御部３４を介して送信部３１ｂ及び３１ｃに入力し、隣接するイジングボード６ｂに転送する。すべてのスピンユニットの値を読み取り終わったら、処理を終了する。
【００８３】
＜振り分け部の構成例＞
図１７に振り分け部３３の構成例を示す。振り分け部３３はモードレジスタ１７０とカウンタ１７１と閾値レジスタ１７２と剰余演算器１７３とＮＯＴ演算器１７４とＯＲ演算器１７５とデマルチプレクサ１７６とを備える。モードレジスタ１７０は振り分け部の動作を切り替えるモードレジスタで、値が０であれば相互作用演算中に用いるデータパケットを主として受け取る転送モードを表し、値が１であれば初期化中等に用いる制御パケットのみを入力として受け取る転送モードを表すものとする。
【００８４】
カウンタ１７１は振り分け部３３が入力のパケットを受け取るたびにインクリメントされる。カウンタの値は予め定数が設定された閾値レジスタ１７２の値とともに剰余演算器１７３に入力される。剰余演算器１７３は剰余の値が０のとき０を、それ以外のとき１を出力するものとする。この値はＮＯＴ演算器１７４に入力され、値が反転されたのちＯＲ演算器１７５へと入力される。デマルチプレクサ１７６はＯＲ演算器１７５の出力を選択信号として入力されたパケットをバッファ３２又は送信部３１へと振り分ける。
【００８５】
ここでは、選択信号が０のとき、バッファ３２へ出力し、選択信号が１のとき送信部３１へ出力する。これにより、モードレジスタ１７０の値が０のときは、原則として入力されたパケットをデータパケットとして振り分け、閾値レジスタで指定されるパケット数毎に１度制御パケットとして振り分ける。一方、モードレジスタ１７０の値が１のときは常に制御パケットとして振り分ける動作となる。
【００８６】
図１８は相互作用動作中の通信に対応する振り分け部の状態遷移を示した図である。相互作用動作中はスピン値のやり取りが主であるため、データパケットの割合を高めることで帯域を無駄なく活用する。相互作用動作中も、イジングボードが計算中であるかどうかを確認するために、ＣＰＵ３から各イジングボードの制御レジスタ３５を読み取る必要があるため制御パケットも一部含める。
【００８７】
図１９にボード間通信路１８を通るパケット種別の時間変化の例を示す。図１６に示したフローチャートに沿って計算を実行する際、リセット後は各イジングボード６ａ及び６ｂの振り分け部３３は制御用通信を行うモードとなり、ボード間通信路１８に制御パケット５０が連続して流れることとなる。図１６のステップ１５０３で転送モードを変更すると、隣接するイジングボード６ａ及び６ｂの間でスピン値をやり取りするためにボード間通信路１８には制御パケット５０に加えてデータパケット５１も流れる。
【００８８】
相互作用演算が終了し、図１６のステップＳ１５０５で再び転送モードを変更すると、ボード間通信路１８に制御パケット５０が連続して流れるようになる。このようにして、同一のボード間通信路１８上で、制御時に適した通信と演算時に適した通信とを時分割的に共有して行うことでチップ間配線を抑えて効率よく通信することが可能となる。
【００８９】
尚、本発明は、イジングモデルの基底状態探索を行う半導体装置に広く適用することができる。
【符号の説明】
【００９０】
１  情報処理装置
２  システムバス
３  ＣＰＵ
４  メモリ
５  記憶装置
６ａ  イジングボード
６ｂ  イジングボード
１７  乱数発生器
１８  ボード間通信路
１９  イジングコア
３１  送信部
３２  バッファ
３３  振り分け部
３４  制御部
３５  制御レジスタ
３６  ホストＩ／Ｆ
３７  受信部
５０  制御パケット
５１  データパケット
【図１】
2020160755.tif 000005
【図２】
2020160755.tif 000006
【図３】
2020160755.tif 000007
【図４】
2020160755.tif 000008
【図５】
2020160755.tif 000009
【図６】
2020160755.tif 000010
【図７】
2020160755.tif 000011
【図８】
2020160755.tif 000012
【図９】
2020160755.tif 000013
【図１０】
2020160755.tif 000014
【図１１】
2020160755.tif 000015
【図１２Ａ】
2020160755.tif 000016
【図１２Ｂ】
2020160755.tif 000017
【図１３】
2020160755.tif 000018
【図１４】
2020160755.tif 000019
【図１５】
2020160755.tif 000020
【図１６】
2020160755.tif 000021
【図１７】
2020160755.tif 000022
【図１８】
2020160755.tif 000023
【図１９】
2020160755.tif 000024