JP6979331B2 - 情報処理装置および情報処理方法 - Google Patents

Description

本発明は、情報処理装置及び方法に関し、特に、相互作用モデルの計算を行う半導体装置をアクセラレータとして制御する情報処理装置に適用して好適なものである。

種々の物理現象や社会現象は相互作用モデルで表現することができる。相互作用モデルとは、モデルを構成する複数個のノードと、ノード間の相互作用、さらに必要であればノード毎のバイアスで定義されるモデルである。物理学や社会科学では種々のモデルが提案されているが、いずれも相互作用モデルの一形態であると解釈できる。

物理学の世界で代表的な相互作用モデルの例として、イジングモデルをあげることができる。イジングモデルは磁性体の振舞いを説明するための統計力学のモデルである。イジングモデルは、＋１／−１（ないしは、０／１、上／下）の２値をとるスピンと、スピン間の相互作用を示す相互作用係数、および、スピン毎にある外部磁場係数で定義される。

イジングモデルは、与えられたスピン配列、相互作用係数、および、外部磁場係数で構成される。イジングモデルのエネルギー関数（一般にハミルトニアンとも呼ばれる）は次式で表わされる。

なお、σ_ｉ、σ_ｊはそれぞれｉ番目とｊ番目のスピンの値、Ｊ_ｉ，ｊはｉ番目とｊ番目のスピンの間の相互作用係数、ｈ_ｉはｉ番目のスピンに対する外部磁場係数、σはスピンの配列を表わすものとする。

（１）式において、第一項は、スピン間の相互作用に起因するエネルギーを計算するものである。一般的にイジングモデルは無向グラフとして表現され、ｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を区別することはない。そのため、第一項ではｉ＜ｊを満たすσ_ｉ、σ_ｊの組み合わせについて、相互作用係数の影響を計算している。また第二項は、各スピンに対する外部磁場に起因するエネルギーを計算するものである。

イジングモデルの基底状態探索は、イジングモデルのエネルギー関数を最小化するスピン配列を求める最適化問題である。非平面グラフで表されるイジングモデルの基底状態探索はＮＰ困難であることが知られている。近年、この問題を効率的に解くため、半導体デバイス技術を応用して基底状態を探索する装置が提案されている（特許文献１）。

特開２０１６−５１３１３号公報

Isakov, Sergei V., et al. "Optimised simulated annealing for Ising spin glasses." Computer Physics Communications 192 (2015): 265-271. Fischer, Thomas H., H. P. Luthi, and W. P. Petersen. A New Optimization Technique for Artificial Neural Networks Used in Prediction of Force Constants of Large Molecules. Eidgenossische Technische Hochschule Zurich, Interdisziplinares Projektzentrum fur Supercomputing, 1994 Zuehlsdorff, Tim Joachim. Computing the Optical Properties of Large Systems. Springer, 2015.

イジングモデルの基底状態探索やサンプリングを実行するにあたり、一般に、マルコフ連鎖モンテカルロ法（以降、ＭＣＭＣと呼ぶ）が用いられる。ＭＣＭＣは、状態間を確率的に遷移しつつ状態のサンプリングを行うことで所望の統計量を推定する手法である。

図１にイジングモデルのエネルギーランドスケープの概念図を示す。これは横軸にスピン配列、縦軸にそのスピン配列におけるエネルギーをプロットしたものである。確率的な遷移では、現在の状態σの近傍のある状態σ’へ確率的に遷移を繰り返す。状態σから状態σ’へ遷移する確率を、遷移確率Ｐ（σ，σ’）と呼ぶ。遷移確率としてメトロポリス法や熱浴法などが知られている。例えば、メトロポリス法の遷移確率は以下（２）式である。Ｔは一般に温度と呼ばれるパラメータで、状態間の遷移のし易さを表す。

近傍の状態σ’を生成する方法として、現在の状態σから一つのスピンの値を変えることが一般的である。変更するスピンを一つずつ順番に変えることで、スピン全体の探索を行う。たとえば、図１の場合は、状態Ａから一つのスピンが反転すると状態Ｂ、そしてさらに一つのスピンが反転すると状態Ｃとなる。

パラメータＴを大きな値から徐々に減少させつつＭＣＭＣを実行するとき、エネルギーが最も低い状態に漸近的に収束する。これにより最小化問題の最適解または近似解を求める手法はシミュレーティッド・アニーリング法（以降、ＳＡと呼ぶ）として知られる。

イジングモデルに対してＭＣＭＣやＳＡを適用するとき、（２）式に基づいてスピン値を確率的に決定する。非隣接のスピンに対して（２）式に基づく状態遷移を同時に適用可能である。そのため、（２）式に基づく確率的処理を実現する回路を複数用意して、並列してスピンの値を更新することで高速にＭＣＭＣやＳＡを実行することができる（例えば特許文献１参照）。

ただし、（２）式に基づく確率的処理を論理回路で実行する場合、指数関数や乗算の計算、乱数生成などが必要である。そのための回路は多くの物量を要する。よって、前述の通り複数並べることが好ましくとも、大規模な装置を限られた回路面積で実現することを前提にすると、充分に（２）式に基づく回路を設けることが困難となる。

本発明の一側面は、１あるいは複数のアレイ回路を備える情報処理装置である。この装置では、アレイ回路の其々は複数のユニットを備え、複数のユニットの其々は、相互作用モデルの１つのノードの状態を示す値を記憶する第１のメモリと、自己ユニットに接続された他のユニットのノードからの、相互作用を示す相互作用係数を記憶する第２のメモリと、他のユニットのノードの状態を示す値および相互作用係数に基づいて、１つのノードの次状態を示す値を決定する論理回路を有する。そして、論理回路はパラメータθの指数分布に従う第１の確率変数を入力とする。

本発明の他の一側面は、アレイ回路を備える情報処理装置を用いた情報処理方法である。この方法では、情報処理装置のアレイ回路の其々は複数のユニットを備え、複数のユニットの其々は、相互作用モデルの１つのノードの状態を示す値を記憶する第１のメモリと、自己ユニットに接続された他のユニットのノードからの、相互作用を示す相互作用係数を記憶する第２のメモリと、他のユニットのノードの状態を示す値および相互作用係数に基づいて、１つのノードの次状態を示す値を決定する論理回路を有する。ここで、１つのノードの状態の遷移のしやすさを示すパラメータを温度Ｔとしたとき、論理回路による１つのノードの状態の次状態への更新処理を、温度Ｔの逆数が等間隔ｃとなるスケジュールを前提として行ない、−Ｔ・ｌｎ（ｕ）（ただしｕは０より大きく１以下の一様乱数）で表される第１の確率変数を、複数のユニットに共通に設けられた第１の乱数発生器によって生成し、複数のユニットを直列に経由する第１の信号経路により供給する。

回路の物量を削減しつつ、メトロポリス法に基づく確率的な処理を可能とする。

イジングモデルのエネルギーランドスケープの概念図。 実施の形態における半導体装置を含む情報処理装置の全体構成の一例を示すブロック図。 実施の形態において、マルチイジングチップの構成の一例を示すブロック図。 実施の形態において、イジングチップの構成の一例を示すブロック図。 実施の形態において、２次元格子のスピンアレイの構成の一例を説明する概念図。 実施の形態において、スピンユニットの構成の一例を示す回路図。 スピンユニットの構成を示すブロック図。 スピンユニットへの乱数の供給方法を示す概念図。 キンググラフが高さ方向に積み重なった形状のイジングモデルの概念図。 スピンユニットの他の構成を示すブロック図。 実施の形態において、マルチイジングチップの構成の他の例を示すブロック図。 ＭＣＭＣの処理手順を示すフロー図。

以下の実施の形態においては、便宜上その必要があるときは、複数のセクションまたは実施の形態に分割して説明するが、特に明示した場合を除き、それらは互いに無関係なものではなく、一方は他方の一部または全部の変形例、詳細、補足説明等の関係にある。また、以下の実施の形態において、要素の数等（個数、数値、量、範囲等を含む）に言及する場合、特に明示した場合および原理的に明らかに特定の数に限定される場合等を除き、その特定の数に限定されるものではなく、特定の数以上でも以下でもよい。

さらに、以下の実施の形態において、その構成要素（要素ステップ等も含む）は、特に明示した場合および原理的に明らかに必須であると考えられる場合等を除き、必ずしも必須のものではないことは言うまでもない。同様に、以下の実施の形態において、構成要素等の形状、位置関係等に言及するときは、特に明示した場合および原理的に明らかにそうでないと考えられる場合等を除き、実質的にその形状等に近似または類似するもの等を含むものとする。このことは、上記数値および範囲についても同様である。

以下、実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一の部材には原則として同一の符号または関連する符号を付し、その繰り返しの説明は省略する。また、以下の実施の形態では、特に必要なとき以外は同一または同様な部分の説明を原則として繰り返さない。同一あるいは同様な機能を有する要素が複数ある場合には、同一の符号に異なる添字を付して説明する場合がある。ただし、複数の要素を区別する必要がない場合には、添字を省略して説明する場合がある。

本明細書等における「第１」、「第２」、「第３」などの表記は、構成要素を識別するために付するものであり、必ずしも、数、順序、もしくはその内容を限定するものではない。また、構成要素の識別のための番号は文脈毎に用いられ、一つの文脈で用いた番号が、他の文脈で必ずしも同一の構成を示すとは限らない。また、ある番号で識別された構成要素が、他の番号で識別された構成要素の機能を兼ねることを妨げるものではない。

実施の形態では、安価かつ容易に製造でき、例えばイジングモデルなどのような任意の相互作用モデルの計算を行うことが可能な半導体装置および情報処理装置について説明する。具体的には、イジングモデルに代表される相互作用モデルに対してメトロポリス法に従う確率的処理を実行させるため、指数分布に従う独立な複数の乱数を入力に取る最小値関数を備える情報処理装置が説明される。

＜（１）相互作用モデル＞
前述のように、種々の物理現象や社会現象は相互作用モデルで表現することができる。相互作用モデルの特徴として、ノード間の影響を２個のノード間の相互作用に限定している（２体間の相互作用）ことがあげられる。物理学の世界で代表的な相互作用モデルの例として、前述のイジングモデルをあげることができる。以下においては、イジングモデルの基底状態探索またはサンプリングを行う半導体装置と、その半導体装置をアクセラレータとして制御する情報処理装置の例を説明する。

＜（２）有向グラフに拡張したイジングモデル＞
本実施の形態では、イジングモデルを拡張した、以下の（３）式で示されるモデルを、以降イジングモデルと呼ぶ。

（１）式で示したイジングモデルとの違いは、（３）式では有向グラフで示されるような相互作用が許されることにある。一般的に、イジングモデルはグラフ理論では無向グラフとして描画することができる。それは、イジングモデルの相互作用は、ｉ番目スピンからｊ番目スピンへの相互作用係数Ｊ_ｉ，ｊと、ｊ番目スピンからｉ番目スピンへの相互作用係数Ｊ_ｊ，ｉとを区別していないことによる。

本実施例はイジングモデルを拡張し、Ｊ_ｉ，ｊとＪ_ｊ，ｉを区別しても適用できるため、有向グラフ化したイジングモデルを取り扱う。なお、無向グラフのイジングモデルを有向グラフのイジングモデルで取り扱う場合には、単にＪ_ｉ，ｊとＪ_ｊ，ｉとの双方向に同じ相互作用係数を定義することで可能である。

＜（３）本実施の形態における情報処理装置の構成＞
＜＜（３−１）半導体装置を含む情報処理装置の全体構成＞＞
半導体装置を含む情報処理装置の全体構成について、図２および図３を用いて説明する。図２は、本実施の形態における半導体装置を含む情報処理装置の全体構成の一例を示すブロック図である。図３は、本実施の形態において、マルチイジングチップの構成の一例を示すブロック図である。

図２において、本実施の形態による情報処理装置を示す。この情報処理装置１は、パーソナルコンピュータやワークステーションまたはサーバなどから構成され、システムバス２を介して接続されたＣＰＵ（Central Processing Unit）３、メモリ４、記憶装置５および複数のマルチイジングチップ６を備える。図示していないが、情報処理装置として通常備える各種の入力装置、出力装置を備えていても良い。

ＣＰＵ３は、情報処理装置１全体の動作制御を司るプロセッサである。またメモリ４は、例えば揮発性の半導体メモリから構成され、各種プログラム等を記憶するために利用される。記憶装置５は、例えばハードディスク装置やＳＳＤ（Solid State Drive）などから構成され、プログラムやデータを長期間保持するために利用される。

本実施の形態の場合、記憶装置５には、本情報処理装置１が解くべきイジングモデル形式の問題の問題データ７が格納され、メモリ４には、マルチイジングチップ制御プログラム９が格納される。マルチイジングチップ制御プログラム９は、個々のマルチイジングチップ６で問題を解くための制御を行うためのプログラムである。

なお、イジングモデル形式でない問題データをイジングモデル形式の問題データ７に変換するプログラムをメモリ４に格納しておくようにしてもよい。このようにすることによりイジングモデル形式でない問題についても対応可能となり、本情報処理装置１の有用性を向上させることができる。

マルチイジングチップ６は、イジングモデルの基底状態探索を行う専用ハードウェアであり、例えば画面描画処理のための専用ハードウェアであるＧＰＵ（Graphics Processing Unit）のように、情報処理装置１に装着する拡張カードの形態を取る。

図３はマルチイジングチップの構成ブロック図である。マルチイジングチップ６は、図３に示すように、インタフェース（Ｉ／Ｆ）１０、イジングチップ群１１および制御部１２を備えて構成され、インタフェース１０およびシステムバス２（図２）を介してＣＰＵ３（図２）との間でコマンドや情報の送受を行う。

イジングチップ群１１は、それぞれがイジングモデルの基底状態探索やサンプリングを行う専用のハードウェアである複数のイジングチップ１３から構成される。イジングチップ１３間はチップ間配線１４により接続されており、このチップ間配線１４を介してイジングチップ１３同士が必要な情報を送受することができる。

制御部１２は、イジングチップ群１１を構成する各イジングチップ１３を制御する機能を有し、コントローラ１５を備えて構成される。コントローラ１５は、タイミングを制御するためのクロック生成機能を備えているものとする。

コントローラ１５は、マルチイジングチップ６全体の動作制御を司るプロセッサであり、情報処理装置１のＣＰＵ３（図２）からシステムバス２（図２）およびインタフェース１０を介して与えられるコマンドに従ってイジングチップ群１１を構成する各イジングチップ１３の動作や、動作タイミングを制御する。また、記憶装置５から送信される問題データ７をイジングチップ１３に格納し、また、イジングチップ１３から読み出した解データを記憶装置５に送信するための制御を行なう。

コントローラ１５は、各イジングチップ１３に対してＳＲＡＭ（Static Random Access Memory）互換インタフェース３０を用い、初期値データとなる問題データ７の書き込みおよび結果データとなる解データの読み出しを行なう。また、コントローラ１５は、各イジングチップ１３に制御コマンドＣＯＮＴを送信して、イジングチップ１３の動作をコントロールする。また、コントローラ１５は、各イジングチップ１３に対して相互作用制御インタフェース３５を介して、相互作用計算の制御を行なう。

＜＜（３−２）イジングチップの構成＞＞
図４を用いてイジングチップ１３の構成について説明する。図４は、本実施の形態において、イジングチップ１３の構成の一例を示すブロック図である。イジングチップは、スピンアレイ２０を内包し各スピンの値を相互作用計算により更新処理する半導体集積回路である。

図４に示すように、イジングチップ１３は、スピンアレイ２０、Ｉ／Ｏ（Input/output）アドレスデコーダ２１、Ｉ／Ｏドライバ２２、相互作用アドレスデコーダ２３、およびチップ間接続部２４を備えて構成される。本実施の形態では、イジングチップ１３は現在広く用いられているＣＭＯＳ（Complementary Metal-Oxide Semiconductor）集積回路として実装されていることを想定して説明するが、他の固体素子でも実現可能である。

イジングチップ１３は、スピンアレイ２０のメモリセルにリード／ライトを行うためのＳＲＡＭ互換インタフェース３０として、アドレスバス３１、データバス３２、Ｒ／Ｗ制御線３３およびＩ／Ｏクロック線３４を備える。またイジングチップ１３は、イジングモデルの基底状態探索の制御を行うための相互作用制御インタフェース３５として、相互作用アドレス線３６および相互作用クロック線３７も備える。

イジングチップ１３では、イジングモデルのスピンσ_ｉ、相互作用係数Ｊ_ｉ，ｊおよび外部磁場係数ｈ_ｉをすべてスピンアレイ２０内のメモリセルに記憶する情報で表現する。スピンσ_ｉの初期状態の設定やＭＣＭＣを実施後のスピン配列の読み出しはＳＲＡＭ互換インタフェース３０を介して行う。またイジングチップ１３では、ＭＣＭＣを実行すべきイジングモデルをスピンアレイ２０に設定するための相互作用係数Ｊ_ｉ，ｊおよび外部磁場係数ｈ_ｉのリード／ライトもＳＲＡＭ互換インタフェース３０を介して行う。

そのため、スピンアレイ２０内のスピンσ_ｉ、相互作用係数Ｊ_ｉ，ｊおよび外部磁場係数ｈ_ｉにはアドレスが付与されている。そしてイジングチップ１３にスピンσ_ｉ、相互作用係数Ｊ_ｉ，ｊまたは外部磁場係数ｈ_ｉをリード／ライトする場合、対応するアドレスがコントローラ１５からアドレスバス３１を介してＩ／Ｏアドレスデコーダ２１に与えられ、これらスピンσ_ｉ、相互作用係数Ｊ_ｉ，ｊおよび外部磁場係数ｈ_ｉのリード／ライトを制御するＲ／Ｗ制御信号がコントローラ１５からＲ／Ｗ制御線３３を介してＩ／Ｏドライバ２２に与えられる。

かくしてＩ／Ｏアドレスデコーダ２１は、アドレスバス３１を介して与えられたアドレスに基づいてスピンアレイ２０のワード線をアクティベートし、Ｉ／Ｏドライバ２２は、Ｒ／Ｗ制御線３３を介して与えられたＲ／Ｗ制御信号に基づいてスピンアレイ２０内の対応するビット線を駆動する。これによりデータバス３２を介して与えられたスピンσ_ｉの初期値や、相互作用係数Ｊ_ｉ，ｊおよび外部磁場係数ｈ_ｉの設定値がスピンアレイ２０に設定され、または、ＭＣＭＣを実施後の解がスピンアレイ２０から読み出されてデータバス３２を介して外部に出力される。

なお、ＳＲＡＭ互換インタフェース３０を構成するアドレスバス３１、データバス３２およびＲ／Ｗ制御線３３は、Ｉ／Ｏクロック線３４を介して制御部１２からイジングチップ１３に与えられるＩ／Ｏクロックに同期する。

また、イジングチップ１３は、ＭＣＭＣを行うために、スピンアレイ２０の内部でスピン間の相互作用を実現する。この相互作用を外部から制御するのが相互作用制御インタフェース３５である。イジングチップ１３は、コントローラ１５から与えられる相互作用を行うスピン群を指定するアドレスを相互作用アドレス線３６経由で入力する。また、同じくコントローラ１５から与えられる相互作用クロックを相互作用クロック線３７から入力し、これに同期して相互作用を行う。相互作用アドレスデコーダ２３は、相互作用アドレス線３６を介して与えられたアドレスに基づいて、スピンアレイ２０に対するスピンの値、相互作用係数Ｊ_ｉ，ｊおよび外部磁場係数ｈ_ｉのリードあるいはライトを行う。

相互作用アドレス線３６と相互作用クロック線３７は、イジングチップ１３内において、隣接スピンユニットのスピンを同時に更新しないように、更新するスピンユニットの更新タイミングを指定する。隣接スピンユニットのスピンを同時に更新すると、両方の更新が重複してエネルギー最小化ができず振動してしまうためである。

イジングチップ１３は、スピンアレイ２０内のメモリから読み出したデータと併せて計算に用いるため、後述のように乱数発生器８と乱数を注入する乱数信号線を有する。乱数発生器８により発生された乱数は、この乱数信号線を介してスピンアレイ２０に与えられる。乱数発生器８の構成と乱数のスピンアレイ２０への供給方法については、後に詳細に説明する。

チップ間接続部２４は、複数のイジングチップ１３を協同して動作させる際には、隣接して配置されたイジングチップ１３との間で必要なスピンσ_ｉの値を送受する際のインタフェースとして、あるいは乱数の経路として機能する。制御信号ＣＯＮＴは、後に説明する切替え信号の信号線ＥＮやＳＷを含み、その他の必要な制御用の信号も含んでよい。

以上で説明した、スピンアレイ２０、ＳＲＡＭ互換インタフェース３０、および相互作用制御インタフェース３５は、本明細書で特に説明する部分以外は、基本的に特許文献１に開示のものと同様に構成できる。

＜＜（３−３）スピンアレイの構成＞＞
図５はキンググラフ状のスピンアレイおよびその接続関係について模式的に説明する概念図である。本発明はキンググラフ以外のグラフに対しても適用可能であるが、本実施例ではキンググラフを例に説明する。スピンアレイ２０は、１個のスピンσ_ｉならびにそれに付随する相互作用係数Ｊ_ｉ，ｊおよび外部磁場係数ｈ_ｉを保持するメモリと、ＭＣＭＣを実現する演算回路を有するスピンユニット４０を基本構成単位として、スピンユニット４０を多数個並べた構成を有する。

図６はキンググラフの概念を示す。キンググラフは図６に示すように格子グラフに対角線が加わったグラフである。

図５において、スピンアレイ２０は３×３の９個のスピンユニット４０を持つこととし、スピンユニット４０が持つスピンを丸で示している。スピンアレイ２０は一つのイジングチップ１３によって実現される。１個のスピンユニット４０には、他のスピンユニットのスピンの値が入力される。図５では８個のスピンユニットのスピンの値を入力することとした。あるスピンユニットに対してスピンの値を入力するスピンユニットを便宜上、「隣接スピンユニット（隣接ノード）」ということにする。ただしこれは必ずしも物理的あるいは幾何学的にスピンユニットが隣接配置されていることを意味しない。

スピンユニット４０は、スピンの値を保持するためのメモリセルを有している。スピンの値は、たとえばスピンの上／下の値を、ＨＩＧＨ／ＬＯＷで表す。図５では各スピンアレイ２０の中央のスピンユニットＮ_１１に着目して、スピンの値の入出力を矢印で示している。またスピンユニット４０は、かかるスピンの値に加え、外部磁場係数ｈ_ｉと、上述した隣接スピンユニットとの相互作用係数Ｊ_ｉ，ｊをそれぞれ保持するメモリセルも有している。このような相互作用を行うスピンアレイ２０の構成については、例えば特許文献１に記載があり、本実施例で特記する以外の構成は、これに従って構成してよい。

なお、図５ではスピンユニットの位置をＮｘｙというように、横方向および縦方向の位置によって示している。スピンユニット４０をタイル状に配置することでスピンアレイ２０が実現される。

＜＜（３−４）スピンユニットの構成＞＞
図７は、本実施の形態において、スピンユニット４０の構成の一例を示す回路ブロック図である。一つのスピンユニットは、イジングモデルの一つのノードに対応する。図示しないが、スピンユニット４０が有するメモリセルには、イジングチップ１３外からアクセスするためのインタフェースであるビット線とワード線が配置され、リード/ライトのタイミングが制御される。これは従来の半導体メモリの制御方式を踏襲するものであり、前述のＳＲＡＭ互換インタフェース３０により実現される。

図７を参照しつつスピンユニット４０の構成を説明する。メモリセルＮはスピンを表現するためのメモリセルであり、スピンの値を保持する。スピンの値はイジングモデルでは＋１／−１（＋１を上、−１を下とも表現する）であるが、これをメモリセルが保持可能な２値である０／１に対応させる。例えば、＋１を１、−１を０に対応させる。

イジングモデルを有向グラフとして捉えた場合に、あるスピンから見ると他のスピンが自スピンに及ぼす影響の係数を持つことになる。自スピンが他のスピンに与える影響の係数は、それぞれの他のスピンに属する。

図５および図６の例では、このスピンユニット４０は最大で８個のスピンユニットと接続される。すなわち、図５のＮ_１１に着目すれば、Ｎ_００、Ｎ_１１、Ｎ_２０、Ｎ_０１、Ｎ_２１、Ｎ_０２、Ｎ_１２、Ｎ_２２の８個のスピンユニットからそれらのスピンの値Ｓ_１〜Ｓ_８を得て、また自分のメモリセルＮに格納された値をこれらに送信する。上記例に限らず、接続されるスピンユニットの個数は８個より多くても少なくてもよい。

図７の場合には、スピンユニット４０は自スピンに及ぼす影響を示す相互作用係数Ｊ_１〜Ｊ_８を格納する８組のメモリセルを備える。さらに、外部磁場係数ｈを格納するメモリセルＨを備える。本実施の形態のイジングチップ１３では、外部磁場係数ｈおよび相互作用係数Ｊ_１〜Ｊ_８を、それぞれＭビットの値に対応させる。そのため、外部磁場係数および相互作用係数を表わすためには、それぞれＭビットのメモリセルが必要となる。

スピンユニット４０内のメモリセルＮ、メモリセルＨ、Ｊ_ｋ（１≦ｋ≦８）は、それぞれイジングチップ１３の外部からリード／ライト可能でなければならない。そのために、前述のように、スピンユニット４０はビット線とワード線とをそれぞれ有している（図７には図示せず）。そしてイジングチップ１３では、スピンユニット４０が半導体基板上にタイル状に並べられてビット線とワード線とが接続されており、Ｉ／Ｏアドレスデコーダ２１とＩ／Ｏドライバ２２でこれらのスピンユニット４０を駆動、制御または読み出しすることにより、一般的なＳＲＡＭと同様に、スピンユニット４０内のメモリセルを、イジングチップ１３のＳＲＡＭ互換インタフェース３０でリード／ライトすることができる。

イジングチップ１３では、ＳＲＡＭ互換インタフェース３０で問題データをメモリに記憶した後、相互作用計算を行なってメモリの値を更新して解を探索し、得られた解をＳＲＡＭ互換インタフェース３０で読み出す。ここで実行される相互作用計算は、具体的にはイジングモデルに対するメトロポリス法に基づいたＭＣＭＣ（基底状態探索やサンプリングなど）である。以下に相互作用計算を行なって、メモリのスピンの値を更新するための回路について説明する。本実施例では、回路規模を縮小しつつ基底状態探索を可能とする例について説明する。その際に、温度スケジュールを逆温度（温度の逆数）で等間隔なるスケジュールとすることを前提にする（後に（１２）式で表す）。

図７において、１ビット乗算器４１Ａ、隣接スピンの値Ｓ_１〜Ｓ_８を示す１ビット信号、および係数Ｊ_１〜Ｊ_８であるＭビット信号を受け取り、１ビット信号の値に応じてＭビット信号をそのまま、または符号反転して出力する。１ビット乗算器４１Ｂは、自スピンの値を示す１ビット信号、および乱数Ｒ_Ｔを受け取り、１ビット信号の値に応じて乱数Ｒ_Ｔをそのまま、または符号反転して出力する。加算器４２は複数の１ビット乗算器４１Ａの出力値およびメモリセルＨから受け取る外部磁場係数ｈの総和を求める。この値は演算器４３で２倍される。２倍された信号は、比較器４４に入力される。

比較器４４は演算器４３と１ビット乗算器４１Ｂの大小関係を比較する。演算器４３の出力値が１ビット乗算器４１Ｂの出力値以上のとき、比較器は１を出力する。また、演算器４３の出力値が１ビット乗算器４１Ｂの出力値未満のとき、比較器は０を出力する。比較器４４の出力は、セレクタ４５の一方の入力に接続され、このセレクタ４５の他方の入力にはメモリセルＮの出力が接続されている。セレクタ４５には、当該スピンユニット４０のスピンの更新を許可する切替え信号の信号線ＥＮが接続されている。セレクタ４５の出力はメモリセルＮの入力に接続され、このメモリセルＮの出力は当該スピンユニット４０のスピンの値を他のスピンユニット４０に出力する信号線ＯＳに接続されている。信号線ＥＮの切替信号は、前述の相互作用制御インタフェース３５によって制御されている。

図７の回路により、メトロポリス法に基づく状態遷移が実現可能である理由について、以下の数式を用いて説明する。スピンユニット４０の表すスピンを現在の値σ_ｉから反転させたとき、エネルギーは次式で計算されるΔＨだけ増加する。

メトロポリス法は温度Ｔにおける状態遷移の受理確率（遷移確率）を（２）式で表す。ゆえに０より大きく１以下の一様乱数ｕを用いると、状態遷移が受理される条件は以下の通りである。

ここで状態遷移後にスピンがσ_ｉ＝＋１となる場合を考える。遷移前の値が＋１ならばΔＨ＞−Ｔ・ｌｎ（ｕ）、つまり以下の不等式が成り立つ場合に条件を満たす。

同様に、遷移前の値が−１ならばΔＨ≦−Ｔ・ｌｎ（ｕ）、つまり以下の不等式が成り立つとき、状態遷移後にスピンがσ_ｉ＝＋１となる。

ゆえに遷移前のスピンσ_ｉの値に依らず，以下の不等式を満たすならば遷移後にスピンがσ_ｉ＝＋１となることが得られる。

よって、メトロポリス法に従った状態遷移を実行するためには、スピンσ_ｉの次状態を表すメモリセルＮの値を（９）式に基づいて与えれば良い。ただしｓｉｇｎ（ｘ）はｘ≧０ならば＋１、ｘ＜０ならば−１を返す関数である。

以上により、メトロポリス法に従った状態遷移を実行するためには、（９）式の演算が可能な回路を準備すればよい。処理を高速化するために、スピンアレイ２０内では、各スピンユニット４０が（９）式に基づいて並列計算を行う必要がある。この際，一様乱数ｕの生成や非線形関数ｌｎの計算、温度Ｔとｌｎ（ｕ）の乗算などを各スピンユニット４０内で各々実行することは、回路規模の増大および動作周波数の低下を引き起こすため好ましくない。以降、この課題を回避しつつ（４）式を実現する方式について、図７および図８を用いて説明する。本実施例では、演算回路が所定の信号Ｒ_ＴおよびＲ_ｃを入力に取ることで、半導体装置の回路規模を抑制する。

（９）式において、確率変数−Ｔ・ｌｎ（ｕ）はパラメータ１／Ｔの指数分布に従う。ただし、一般にパラメータθの指数分布は以下の確率密度関数を持つ分布である。

時刻ｋにおいて、信号Ｒ_ＴおよびＲ_ｃは各スピンユニット４０内でパラメータ１／Ｔ_ｋ、パラメータｃの指数分布に従う値をそれぞれ持つとする。すなわち、（１０）式において、其々θ＝１／Ｔ_ｋ、θ＝ｃをとる。このために、乱数発生器で指数分布に従う乱数を生成するとき，この前提を満たすよう制御するものとする。信号Ｒ_Ｔは各スピンユニット内で同値とは限らないことに注意されたい。あくまでも確率分布の性質を表すパラメータのみが同じである。これは信号Ｒ_ｃに関しても同様である。Ｔ_ｋはアニーリングにおいてｋ番目に使用する温度を表す。温度を時間的に線形に低下させる場合は、ｋは経過時間と同義である。ｃはアニーリングにおいて温度Ｔ_ｋの逆数の間隔を表す。これらは、アニーリング開始前にユーザがパラメータとして設定する。

（９）式と図７の演算回路の対応を式の左側から示す。演算「ｓｉｇｎ」は比較器４４で実行される。「２の乗算」は演算器４３で実行される。「ｈ_ｉ＋Σｊ_ｉｋσ_ｋ」のｈ_ｉはメモリＨに格納されているｉ番目のスピン（自スピン）に対する外部磁場係数である。Σ演算は加算器４２で実行される。ｊ_ｉｋは自スピン（ｉ番目）と隣接スピン（ｋ番目）の間の相互作用係数であり、これはメモリＪ_１〜Ｊ_８に格納されている。σ_ｋは隣接スピンの値であり、信号線s_１〜s_８から入力される。σ_ｉはメモリＮに格納される自スピンの値である。−T・ｌｎ（ｕ）はパラメータ１／Ｔの指数分布に従う確率変数であり、入力信号Ｒ_Ｔで与えられる。

これにより、比較器４４の２入力はそれぞれ、２（ｈ_ｉ＋Σｊ_ｉｋσ_ｋ）、−σ_ｉ・Ｔ_ｋ・ｌｎ（ｕ）となる。ゆえに（９）式に鑑みると、温度Ｔ_ｋにおけるメトロポリス法に基づいて確率的に決まる値σ_ｉが次の状態としてメモリセルＮに保存される。

温度Ｔ_ｋ,定数ｃはユーザが与えるパラメータである。本実施例のアニーリングでは（１２）式に示した温度系列を用いる。この系列は、温度スケジュールを逆温度で等間隔ｃとなるスケジュールを示す。温度Ｔ_ｋ，定数ｃはスケジュールによって定まるが、ユーザはアニーリング開始に先立って、温度の初期値Ｔと定数ｃを設定して入力しておくものとする。スピンユニット内の乱数には、後述する最小値関数の機能により、自然とＴ_１,Ｔ_２・・・に対応したパラメータを持つ指数乱数が現れる。なお、（１２）式でｃ＝０とした場合はＴ_１＝Ｔ_２＝・・・＝Ｔ_ｋを表す。この場合には，（１２）式は温度一定のスケジュールを表すことになる。

スピンユニット４０から出力する乱数線ＯＲ_Ｔ、ＯＲ_ｃは、他のスピンユニット４０において各々乱数線Ｒ_Ｔ、Ｒ_ｃとして用いる。

図８に、イジングチップ１３における乱数線のスピンユニット間の接続関係を示す。イジングチップ１３は、乱数発生器８として２つの乱数発生器８Ａ、８Ｂを持ち、それぞれ独立に指数分布に従う確率変数を生成する。ここでは、乱数発生器８Ａは１／Ｔの指数分布に従う確率変数を乱数線Ｒ_Ｔに供給し、乱数発生器８Ｂはｃの指数分布に従う確率変数を乱数線Ｒ_Ｃに供給するものとする。確立変数は非負値（マイナスでない値）をとる。そして各乱数発生器で生成した信号は乱数線Ｒ_Ｔ，Ｒ_Ｃを介して各スピンユニット４０を順番に流れる。各乱数の伝搬方向は逆方向になるよう定める。たとえばＮ_１１の信号ＯＲ_ＴはＮ_２１の信号Ｒ_Ｔ、Ｎ_１１の信号ＯＲ_ＣはＮ_０１の信号Ｒ_Ｃに次のタイミングで供給される。

（１０）式より、パラメータθに従う指数乱数は−ｌｎ（ｕ）／θで求まる。ここでｕは０〜１の一様乱数である。よって，乱数発生器８Ａ、８Ｂでは、ＬＳＦＲ（線形帰還シフトレジスタ）などで一様乱数ｕを生成し，対数をとれば指数分布に従う確率変数が得られる。

（１０）式において、確率変数Ｘ_１、Ｘ_２をそれぞれパラメータθ_１、θ_２の指数分布に従うとする。互いに独立なとき、Ｘ_１およびＸ_２がｘより大きい確率は（１１）式で表される。Ｘ_１およびＸ_２がｘより大きい事象は、Ｘ_１とＸ_２の最小値がｘより大きい事象と等価であり、この事象の発生確率が（１０）式で表せるのである。つまりＸ_１、Ｘ_２の最小値はパラメータθ_１＋θ_２の指数分布に従う。なお、記号Ｐｒは事象が起こる確率を意味する。

ゆえに、Ｒ_Ｔ、Ｒ_ｃを上記のように設定した場合、最小値関数４６はパラメータ１／Ｔ_ｋ＋ｃの指数分布に従う確率変数を出力する。この値または信号Ｒ_Ｔの持つ値のいずれかをセレクタ４７で選択して信号線ＯＲ_Ｔに与える。この切替えは信号線ＳＷによって制御する。また信号線ＯＲ_ｃは乱数線Ｒ_ｃの値をそのまま出力する。信号線ＳＷは、コントローラ１５から供給される制御信号ＣＯＮＴに含まれるものとする。信号線ＳＷはコントローラ１５から各スピンユニット共通に与えられる信号である。ＳＷは、状態遷移の実行に際して、温度Ｔを変更するか維持するかを定めるものとして用いられる。すなわち、ＯＲ_ＴとしてＲ_Ｔをそのまま出力しているということは、温度が変化していないということを示す。また、ＯＲ_Ｔとして最小値関数４６の出力を出力しているということは、温度が変化（たとえばＴ_ｋ→Ｔ_ｋ＋１）になることを示す。これはセレクタ４７を切り替えることで制御される。セレクタ４７を制御する信号線ＳＷの信号をどのように制御するかは、アニーリングにおいてどのように温度を制御するかに依存する。したがって、信号線ＳＷの信号のプログラムは、アニーリング開始に先立って設定されるが、予めユーザが入力しておくものとする。また、何回温度Ｔを変化させるかも、ユーザが設定することができる。

各スピンユニットで用いる乱数Ｒ_Ｔは空間的および時間的に独立であることが望まれる。仮に伝搬方向が同じ場合，最小値関数４６の出力であるｍｉｎ(Ｒ_Ｔ，Ｒ_Ｃ)＝ｍｉｎ(ＯＲ_Ｔ，Ｒ_Ｃ)となり，あるスピンユニットで使われた乱数が，次のスピンユニット（隣接スピンユニット）でもそのまま使われてしまう。このような事態を避けるため，本実施例では図８に示したように、２つの乱数の伝搬方向は逆方向としている。ただし、２本の乱数線Ｒ_Ｔ，Ｒ_Ｃの情報が同じ経路を通らずに混合されればよいので，必ずしも逆方向である必要はない。例えば、互いの乱数線を９０度回転させて配線する，など他の方式も考えられる。

信号線ＳＷを制御して最小値関数４６の出力がＯＲ_Ｔに与えられる場合を想定する。上記のように、時刻ｋにて信号Ｒ_ＴおよびＲ_ｃは各スピンユニット４０内でパラメータ１／Ｔ_ｋ、パラメータｃの指数分布に従う確率乱数を持つ。そのため、次のタイミングである時刻ｋ＋１には、信号Ｒ_ＴおよびＲ_ｃは各スピンユニット４０内でパラメータ１／Ｔ_ｋ＋ｃ、パラメータｃの指数分布に従う確率乱数を持つ。よって、時刻ｋ＋１では（１２）式で与えられる温度Ｔ_ｋ＋１を用いてメトロポリス法に基づくスピン更新を実行することになる。

以上で説明したスピンユニット４０内の演算は並列的に行なわれる。その結果、ＯＲ_Ｔは制御信号ＳＷで固定されない限り変化してゆく。これは、アニーリングにおいて温度Ｔが変化することによって遷移確率が変化していくことに相当する。また、各スピンユニット４０スピンの値σもその都度計算されるが、値を更新するかどうかは制御信号ＥＮによって定められる。

非特許文献１、２に記された通り、（１２）式に基づく温度スケジューリングはＳＡ法で一般的に用いられる。本実施例により、この汎用的な温度制御法を実現するに際して、乗算や非線形関数の計算は乱数発生器８内のみに留め、並列計算部（本実施例ではスピンユニット４０）では最小値関数４６および加算器４２のみで実現できるようになった。すなわち、乱数発生器８では、一様乱数ｕの生成、一様乱数を受け取るlog関数や，その値に１／θを掛け合わせる処理を、配下のスピンユニット４０共通で行なう。スピンユニット４０は、最小値関数４６、加算器４２、比較器４４など、回路規模の小さい構成による処理を並列で行なうことができる。

図７で、セレクタ４７が信号Ｒ_Ｔを常に選択するよう信号線ＳＷを制御すると、温度一定のメトロポリス法が実行可能である。これはボルツマン機械学習や自由エネルギーに基づく強化学習などのアルゴリズムで必要となる統計量計算に必要な処理であり、本実施例はこの用途に対しても好適である。

また、温度一定の下でイジングモデルに対してメトロポロス法に基づく状態遷移を実現することは、Ｓｉｍｕｌａｔｅｄ Ｑｕａｎｔｕｍ Ａｎｎｅａｌｉｎｇ（以降、ＳＱＡと呼ぶ）を実行する際にも有用である。以下ＳＱＡの実行に適した実施例を説明する。

経路積分モンテカルロ法に基づくＳＱＡは（１３）式のハミルトニアンＨ_ｑを考える。ただしσ_i ^x、σ_i ^zはパウリ行列のｘ成分、ｚ成分を表す。またΓ(t)は横磁場の大きさを表し、アニーリングが進むにつれて０へ漸近的に小さくなる。

鈴木・トロッター分解を（１３）式に適用することにより、（１３）式のダイナミクスは（１４）式で疑似的に再現されることが知られている（非特許文献３）。レプリカ数Ｌが大きいほど、（１３）式および（１４）式がそれぞれ表す分配関数の差は小さい。（１４）式は古典的なイジングモデルであり、ディジタル回路で計算可能である。レプリカ数ＬやΓ(t)はユーザが定める定数や関数で与えられる。

（１４）式は（１）式を拡張し、レプリカ数Ｌとレプリカ間相互作用Ｗ（かっこ内第３項の係数に相当）を導入したものと解釈することができるので、実施例１と同様にこの処理についても類似の構成を適用できる。

図９は、図６に示すキンググラフ状のイジングモデルに対してＳＱＡを実行するための状態遷移の概念図である。図９に示す通り、レプリカ数Ｌのキンググラフが高さ方向に、第１レプリカ９−１〜第Ｌレプリカ９−Ｌまで積み重なった形状のイジングモデルに対して、メトロポリス法に基づく状態遷移を行えばよい。そしてアニーリング中は温度Ｔを固定しつつ、高さ方向の相互作用係数Ｗのみを変化させる。例えば相互作用係数Ｗを徐々に強める。

（１４）式が示す通り、各レプリカは同じ相互作用ｊ_ｉｊ・外部磁場係数ｈ_ｉの組み合わせを持つ。よって、イジングモデルに対してＳＱＡを実現する回路を構成する場合は、スピンユニット４０内で係数ｊ_ｉｊ，ｈ_ｉを表すメモリセルを、複数のスピンユニットで共有することが可能である。すなわち、一つのスピンユニット４０で、複数のレプリカの動作を再現することができる。これによってメモリ消費の増加が抑制されるため、レプリカ数Ｌを大きくすることが可能となる。

図１０に、スピンを表すメモリセルを共有する方式のスピンユニットの構成例を示す。図７の構成と同様の構成は同じ符号を付して説明を省略する。主たる相違点はスピンの値を格納するメモリＮがレプリカ数Ｌ分のスピンを格納できることと、レプリカ間の相互作用係数Ｗが導入されている点である。また制御上、制御信号ＳＷは温度を一定にするために常にＲ_Ｔを出力するようにセレクタ４７を固定するため、常にＯＲ_Ｔ＝Ｒ_Ｔとなる。もっとも、温度Ｔを変える必要がある場合は変化させても良い。図５で説明したＮ_１１のスピンユニットは、図９の縦方向に積層されるＬ層の各レプリカの、Ｎ_１１に対応するスピンユニットのスピン値を保持する。ゆえに図９に示すようにＬ層のレプリカを実現する場合、メモリセル４８の容量はＬビットとする。

信号線ＲＰはスピン更新の対象とするレプリカを示す。たとえばＲＰ＝１ならば図９に示す最上位層（第１レプリカ）９−１，ＲＰ＝２ならば２つ目の層（第２レプリカ）９−２に含まれるスピンを示す。信号線ＲＰは、全てのスピンユニット４０に対して同じレプリカを指定する。すなわち、本実施例ではレプリカを一つずつ順番に処理していく。例えば、ＲＰの値は１つずつインクリメントされ、Ｌに至ると１に戻る。信号ＲＰに従って、メモリセル４８から対応するレプリカ（層）のスピンσを読み書きする。相互作用計算を行なう際には、レプリカごとに処理を行なうので、図１０の信号ＯＳ、Ｓ_１〜Ｓ_８は、ＲＰ＝１のときは第１レプリカのスピンを、ＲＰ＝２のときは第２レプリカのスピンを入出力する。

信号Ｗはレプリカ間に働く相互作用を表す。これは（１４）式のかっこ内第３項の係数であり、この数式が示すようにレプリカ間の相互作用はすべて等しい。この値は例えばＭビットであって乱数発生器８と同様に、マルチイジングチップ６で生成して各スピンユニット４０に分配する。乗算器４１C，４１Ｄは１ビット乗算器である。それぞれの入力信号のうち、１ビット側の信号は、信号線ＲＰが指定するレプリカの上下に存在するレプリカのスピンＵＰとＤＮがメモリセル４８から与えられる。乗算器４１Ｃ，４１Ｄはレプリカのスピンの示す値に基づいて相互作用係数Ｗの符号をそのまま、または反転して出力する。

なお、一番上のレプリカ９−１と一番下のレプリカ間９−Ｌの間にも高さ方向の相互作用Ｗが働くとして、一番上のレプリカ９−１では上側のスピンＵＰとして最下層のレプリカ９−Ｌからスピン値を読み出す。また、最下層のレプリカ９−Ｌは下側のスピンＤＮとして一番上のレプリカ９−１からスピン値を読む。この場合は、高さ方向に周期境界条件を設定していることになる。

別の計算方法としては、高さ方向が開放境界条件であるとすることもできる。この場合は、一番上のレプリカ９−１と一番下のレプリカ９−Ｌ間に相互作用が無いとし、一番上のレプリカでは上側のスピンがないため，スピン値を０、または相互作用Ｗを０とする。一番下のレプリカ９−Ｌでも同様である。これらの条件はユーザが設定可能である。

図１１に示すスピンユニットの構成例において、レプリカ数Ｌの増加に伴って増加する回路はメモリセル４８のみである。レプリカ数Ｌを大きくすることはＳＱＡの解精度を向上させる上で重要である。

図１１は、マルチイジングチップ６の他の構成例を示す図である。実施例１の図３の例と同様の部分は同一の符号を付して説明は省略する。また説明上、図３のＳＲＡＭ互換インタフェース３０、および相互作用制御インタフェース３５を省略しているが、この部分は図３の例と同様に構成しているものとする。

実施例１の図８では、乱数発生器８Ａおよび８Ｂをイジングチップ１３毎に備えていたが、図１１の例では、乱数発生器８Ａおよび８Ｂをイジングチップ１３で共通としている。

乱数発生器８Ａは一様乱数発生器８１Ａと対数計算および温度Ｔとの乗算を行なう演算器８２Ａを含む。演算器８２Ａにはコントローラ１５から、ユーザが設定したパラメータである温度Ｔが与えられる。一様乱数発生器８１Ａは一様乱数ｕを生成し、演算器８２Ａは−Ｔ・ｌｎ（ｕ）の対数演算を行なう。確立変数は非負値なので符号を反転させる。その結果、乱数発生器８Ａが生成する乱数Ｒ_Ｔはイジングチップ１３の一つに入力される。

乱数発生器８Ｂは一様乱数発生器８１Ｂと対数計算および温度１／ｃとの乗算を行なう演算器８２Ｂを含む。演算器８２Ｂにはコントローラ１５から、ユーザが設定したパラメータである定数ｃが与えられる。一様乱数発生器８１Ｂは一様乱数ｕを生成し、演算器８２Ｂは−（１／ｃ）／ｌｎ（ｕ）の対数演算を行なう。確立変数は非負値なので符号を反転させる。乱数発生器８Ｂが生成する乱数Ｒ_Ｃはイジングチップ１３の一つに入力される。

一つのイジングチップ１３に入力された乱数Ｒ_Ｔと乱数Ｒ_Ｃは、それぞれがチップ間配線１４を経由して全てのイジングチップ１３を通るように送信される。各イジングチップ１３内でも、全てのスピンユニットを経由するように送信される。図８では、乱数発生器８Ａおよび８Ｂからの乱数の経路は、経路が同一で向きが逆としていた。しかし、乱数はスピンユニットごと、なるべく独立であれば良いので、あるスピンユニットに着目した場合、乱数Ｒ_Ｔと乱数Ｒ_Ｃが別々のスピンユニットから入ってくればよい。具体的には、乱数Ｒ_Ｔと乱数Ｒ_Ｃの経路か方向の少なくとも一方が異なればよい。

乱数Ｒ_Ｔと乱数Ｒ_Ｃの生成やスピンユニット４０内の演算が、クロックで規定される所定周期内で実行されると考えると、全てのスピンユニットに２種類の乱数がいきわたらないと演算できないので、最大で「スピンユニット数×周期」の準備期間が必要となる。例えば、図１１のように複数イジングチップ１３で乱数発生器８Ａおよび８Ｂを共通とする場合には、合計スピンユニット数は「イジングチップの数×１イジングチップあたりのスピンユニットの数」となる。１イジングチップあたりのスピンユニットの数は、例えば10000個（100×100）である。この場合は、4×10000周期（図１１の場合）の準備期間が必要である。

準備期間中は、例えばスピンの値は固定で、乱数Ｒ_Ｔ＝ＯＲ_Ｔとして変更しないものとする。このためには、図７の信号ＥＮでセレクタ４５を制御してメモリＮの値を固定とし、信号ＳＷでセレクタ４７を制御して乱数Ｒ_Ｔをそのまま流し続ける。

なお、乱数の経路とＳＲＡＭ互換インタフェース３０の経路が独立しているため、上記の準備期間中に、メモリ４から係数を読み出して各スピンユニットのメモリセルＨ，Ｊ、あるいはＮに値を格納する処理を行なうことにより、乱数の供給とデータおよび係数の格納を並行して行なうことが可能である。

本実施例では、マルチイジングチップはFPGA（Field Programmable Gate Array）、ASIC（Application Specific Integrated Circuit）などのハードウェアで構成することにした。もっとも同様の機能は汎用のプロセッサにプログラムを実行させるソフトウェア構成とすることも可能である。なお、図８でも同様であるが、乱数Ｒ_Ｔと乱数Ｒ_Ｃの終端ではそれ以上出力を出さないことにして、処理を打ち切ればよい。

イジングチップの制御手順について説明する。図１２は、本実施の形態において、ＭＣＭＣの処理手順を示すフローチャートである。

図１２は、本実施の形態の情報処理装置１において、ＣＰＵ３（図１）により実行される基底状態探索処理の処理手順を示す。この処理は、主に相互作用演算によるスピン更新処理を説明している。

ＣＰＵ３は、ステップＳＰ１については図示しない問題変換プログラムに基づいて処理する。これ以降の処理（ステップＳＰ２〜ステップＳＰ１１）についてはマルチイジングチップ制御プログラム９（図１）に基づいて、必要なマルチイジングチップ６（図２）のコントローラ１５（図２）を介して当該マルチイジングチップ６内のイジングチップ１３を制御することにより、これらのイジングチップ１３において基底状態探索を実行させる。なお、ステップＳＰ１の処理と、ステップＳＰ２〜ステップＳＰ１１の処理とを別々のタイミングで実行するようにしてもよい。

またＣＰＵ３は、実際には各マルチイジングチップ６内のイジングチップ１３や、イジングチップ１３内のスピンユニット４０をマルチイジングチップ６内のコントローラ１５（図２）を介して制御するが、以下においては理解の容易化のため、コントローラ１５の存在を省略して説明を行う。

ＣＰＵ３は、ユーザからの指示等によりこの基底状態探索処理を開始すると、まず、問題データ７（図１）をイジングモデルの形式のデータに変換する（ステップＳＰ１）。問題データ７がすでにイジングモデルの形式のデータである場合、ステップＳＰ１は省略する。

続いて、ＣＰＵ３は、変換後のイジングモデルの相互作用係数Ｊ_ｉおよび外部磁場係数ｈを必要なマルチイジングチップ６の各イジングチップ１３内の各スピンユニット４０にそれぞれ設定する。また、ＣＰＵ３は予めユーザによって入力された基底状態探索処理実行のためのパラメータである、温度Ｔ，定数ｃ，温度の変化回数ｋ，セレクタ４５の制御信号ＥＮ，セレクタ４７の制御信号ＳＷをコントローラ１５内に格納する（ステップＳＰ２）。

次に初期スピン配列を生成してスピンを初期化する。本実施例では、数値はすべて同じ値でもよいが、通常はスピンの初期値はランダムな値とする。メモリマップに基づいて、係数と初期スピン配列をスピンアレイのメモリＮに書き込む。（ステップＳＰ３）。

相互作用回数ｍを設定する（ステップＳＰ４）。相互作用演算を実行し（ステップＳＰ５）、すべてのスピンアレイ２０について実行が完了したかどうかを判定する（ステップＳＰ６）。未完了ならば、次のスピンアレイ２０に対して相互作用演算を実行する（ステップＳＰ５）。すべてのスピンアレイ２０に実行が完了したら、規定の相互作用回数（ｍ回）を実行したかどうか判定する（ステップＳＰ７）。未完了であれば、ビット確率を更新し（ステップＳＰ８）、相互作用回数をインクリメントし（ステップＳＰ９）、相互作用計算を継続する。ここで、ビット確率の更新は、セレクタ４７の切替により最小値関数４６の出力をＯＲ_Ｔとすることで実行される。

規定の相互作用回数を実行済であれば、スピンの値を読みだす（ステップＳＰ１０）。そしてＣＰＵ３は、この後、この基底状態探索処理を終了する。以上のようにして、ＭＣＭＣを実行することができる。

本実施例では、各イジングチップ１３は同一モデルの基底状態探索を行っており、係数設定（ステップＳＰ２）〜相互作用回数の設定（ステップＳＰ４）まで共通の設定がなされる。しかし、ＳＰ５以降の相互作用演算では、各スピンユニットは乱数Ｒ_Ｔと乱数Ｒ_Ｃにより確率的に異なる結果を導くことになる。

以上説明した本実施の形態の半導体装置および情報処理装置は、安価かつ容易に製造でき、例えばイジングモデルなどのような任意の相互作用モデルの計算を行うことが可能となる。すなわち、本実施の形態の情報処理装置では、乗算器や非線形関数の演算回路を抑制しつつ、メトロポリス法に基づく状態遷移の並列計算を実行することができる。具体的には、乱数発生器は複数スピンユニット４０で共通とし、乱数とパラメータを乗算する回路も複数スピンユニット４０で共通とした。スピンユニット４０内では最小値関数による指数分布の混合を活用することで、乗算・非線形関数に係わる部分は乱数発生器８に集約することができる。かくして、イジングモデルの基底状態または当該基底状態の近似解を精度高く得ることやサンプリングを高精度に行うための情報処理装置を、安価かつ容易に製造できる。

本実施例によれば、イジングモデルに代表される相互作用モデルに対してメトロポリス法に基づく状態遷移を、回路規模を抑制しつつ高精度に実行可能となる。すなわち、疑似乱数発生器や乗算、非線形関数など負荷の大きな計算を並列計算部から排し，例えばイジングモデルなどのような任意の相互作用ネットワークに対して高速に計算することが可能となる。本実施例によれば、一般的に用いられる温度スケジューリングを用いたシミュレーティッド・アニーリング法を、並列計算部で乗算器の代わりに最小値関数を用いて実現される。

また、温度を一定としてメトロポリス法に基づく状態遷移を行うことにより、イジングモデルに対して経路積分法に基づくシミュレーティッド・量子アニーリング法を実現することも可能である。この場合は前記と同様、疑似乱数発生器や乗算、非線形関数など負荷の大きな計算を並列計算部から排して高速に計算可能である。また、鈴木・トロッター分解を適用して得られるハミルトニアンにおいて、各レプリカは係数が共通であるため、メモリセルが共有できる。この構造を用いることでメモリ消費を抑えつつイジングモデルに対するシミュレーティッド・量子アニーリング法が実現される。

以上、本発明者によってなされた発明をその実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。

例えば、上述した実施の形態は、本発明を分かり易く説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施の形態の構成の一部を他の実施の形態の構成に置き換えることが可能であり、また、ある実施の形態の構成に他の実施の形態の構成を加えることも可能である。また、各実施の形態の構成の一部について、他の構成の追加・削除・置換をすることが可能である。

１…情報処理装置、２…システムバス、３…ＣＰＵ、４…メモリ、５…記憶装置、６…マルチイジングチップ、７…問題データ、８…乱数発生器、９…マルチイジングチップ制御プログラム、１１…イジングチップ群、１２…制御部、１３…イジングチップ、１４…チップ間配線、１５…コントローラ、１６…相互作用クロック生成器、２０…スピンアレイ、２４…チップ間接続部、４０…スピンユニット、４４…比較器

Claims (13)

1. １あるいは複数のアレイ回路を備える情報処理装置であって、
   前記アレイ回路の其々は複数のユニットを備え、
   前記複数のユニットの其々は、
   相互作用モデルの１つのノードの状態を示す値を記憶する第１のメモリと、
   自己ユニットに接続された他のユニットのノードからの、相互作用を示す相互作用係数を記憶する第２のメモリと、
   前記他のユニットのノードの状態を示す値および前記相互作用係数に基づいて、前記１つのノードの次状態を示す値を決定する論理回路を有し、
   前記論理回路はパラメータθの指数分布に従う第１の確率変数を入力とし、該第１の確率変数を用いて前記次状態を示す値を決定し、
   前記相互作用モデルの１つのノードの状態の遷移のしやすさを示すパラメータを温度Ｔとしたとき、前記論理回路による前記１つのノードの状態の更新処理を、前記温度Ｔの逆数が等間隔ｃとなるスケジュールを前提として行ない、
   前記第１の確率変数を−Ｔ・ｌｎ（ｕ）（ただしｕは０より大きく１以下の一様乱数）として、前記第１の確率変数がθ＝１／Ｔの指数分布に従うようにし、
   前記第１の確率変数を生成する第１の乱数発生器を前記複数のユニットで共用し、
   前記ユニットの其々は、入力された前記第１の確率変数をそのまま他のユニットに入力可能とする、
   情報処理装置。
2. 前記論理回路は、
   前記他のユニットのノードの状態を示す値および前記相互作用係数を入力とし、前記他のユニットのノードの状態を示す値に基づいて前記相互作用係数の符号をそのまま、または反転して出力する第１の演算器と、
   前記１つのノードの状態を示す値と前記第１の確率変数とを入力とし、前記１つのノードの状態を示す値に基づいて前記第１の確率変数の符号をそのまま、または反転して出力する第２の演算器と、
   前記第１の演算器の出力を２倍する第３の演算器と、
   前記第２の演算器と前記第３の演算器の出力を入力とし、２入力の大小関係にもとづいた値を択一的に出力する比較器と、
   前記比較器の出力を前記第１のメモリに記憶させる信号線を備える、
   請求項１記載の情報処理装置。
3. 前記論理回路は、
   複数の他のユニットのノードの状態を示す値を入力とし、
   前記複数の他のユニットのノードにそれぞれ対応付けられる複数の前記第２のメモリを備え、
   前記他のユニットのノードの状態を示す値とそれに対応付けられる前記第２のメモリに格納される前記相互作用係数を入力とする複数の前記第１の演算器を備え、
   複数の前記第１の演算器の出力を加算する加算器を備え、
   前記第３の演算器は前記加算器の出力を２倍する、
   請求項２記載の情報処理装置。
4. 前記比較器は、
   前記第３の演算器の出力が前記第２の演算器の出力以上のとき、第１の値を出力し、
   前記第３の演算器の出力が前記第２の演算器の出力未満のとき、第２の値を出力する、
   請求項３記載の情報処理装置。
5. 前記論理回路はパラメータθの指数分布に従う第２の確率変数を入力とし、
   前記第２の確率変数を生成する第２の乱数発生器を前記複数のユニットで共用し、
   前記第２の確率変数は−（１／ｃ）・ｌｎ（ｕ）（ただしｕは０より大きく１以下の一様乱数）であり、
   前記論理回路は、
   前記第１の確率変数と前記第２の確率変数を入力として最小値関数を演算する第４の演算器を備え、
   前記第１の確率変数と前記第４の演算器の出力を選択して他のユニットに入力可能とする、
   請求項１記載の情報処理装置。
6. 前記第１の確率変数を前記複数のユニットの論理回路に供給する第１の信号経路と、前記第２の確率変数を前記複数のユニットの論理回路に供給する第２の信号経路とは、経路および信号の伝播方向の少なくとも１つが異なるように構成される、
   請求項５記載の情報処理装置。
7. 前記ユニットの其々は、入力された前記第２の確率変数をそのまま他のユニットに入力可能とする、
   請求項６記載の情報処理装置。
8. 前記第１の乱数発生器および前記第２の乱数発生器は、
   前記アレイ回路ごとに配置されるか、あるいは、複数のアレイ回路で共通に配置されている、
   請求項５記載の情報処理装置。
9. 前記第１の確率変数と前記第４の演算器の出力を選択して他のユニットに入力可能とするセレクタを備え、
   前記セレクタを制御する制御信号ＳＷにより前記温度Ｔの時間的変化を制御する、
   請求項５記載の情報処理装置。
10. 前記複数のユニットの其々は、
    前記相互作用モデルの１つのノードの状態の複数のレプリカを示す値を記憶する前記第１のメモリを備え、
    前記複数のレプリカ間の相互作用係数Ｗを入力とし、
    前記論理回路は、
    前記レプリカのうち第１のレプリカを示す値と前記相互作用係数Ｗを入力とし、前記第１のレプリカを示す値に基づいて前記相互作用係数Ｗの符号をそのまま、または反転して出力する第５の演算器を備え、
    前記第５の演算器の出力を前記加算器に入力して加算し、
    前記比較器の出力に基づいて、前記レプリカのうち第２のレプリカを示す値の次状態を示す値を決定する、
    請求項３記載の情報処理装置。
11. アレイ回路を備える情報処理装置を用いた情報処理方法であって、
    前記アレイ回路の其々は複数のユニットを備え、
    前記複数のユニットの其々は、
    相互作用モデルの１つのノードの状態を示す値を記憶する第１のメモリと、
    自己ユニットに接続された他のユニットのノードからの、相互作用を示す相互作用係数を記憶する第２のメモリと、
    前記他のユニットのノードの状態を示す値および前記相互作用係数に基づいて、前記１つのノードの次状態を示す値を決定する論理回路を有し、
    前記１つのノードの状態の遷移のしやすさを示すパラメータを温度Ｔとしたとき、前記論理回路による前記１つのノードの状態の前記次状態への更新処理を、前記温度Ｔの逆数が等間隔ｃとなるスケジュールを前提として行ない、
    −Ｔ・ｌｎ（ｕ）（ただしｕは０より大きく１以下の一様乱数）で表される第１の確率変数を、前記複数のユニットに共通に設けられた第１の乱数発生器によって生成し、前記複数のユニットを直列に経由する第１の信号経路により供給する、
    情報処理方法。
12. −（１／ｃ）・ｌｎ（ｕ）（ただしｕは０より大きく１以下の一様乱数）で表される第２の確率変数を、前記複数のユニットに共通に設けられた第２の乱数発生器によって生成し、前記複数のユニットを直列に経由する第２の信号経路により供給し、
    前記ユニットにおいて、前記第１の確率変数と前記第２の確率変数に基づいて、パラメータ１／Ｔ＋ｃの指数分布に従う第３の確率変数を得、該第３の確率変数を前記第１の確率変数に代えて他のユニットに送信を可能とする、
    請求項１１記載の情報処理方法。
13. 前記第１の信号経路と前記第２の信号経路は、前記複数のユニットに対して、経路および信号の伝播方向の少なくとも１つが異なるように信号を供給する、
    請求項１２記載の情報処理方法。

Images