(57)【要約】【課題】  ＭＣＭＣを高速化させるハードウェアを実現する。【解決手段】  複数のイジングチップと、複数のイジングチップを制御するコントローラを含む情報処理装置である。複数のイジングチップの其々は複数のユニットを備え、複数のユニットの其々はスピン状態を保持する。コントローラは、複数のイジングチップのうち一組のイジングチップに対して、対応するユニットのスピン状態の値を比較するよう指示し、一組のイジングチップに対して、対応するユニットのスピン状態の値が異なるスピンのうち、一部のスピンの値を反転するよう指示する。【選択図】  図６
2018206127.tif 000002
【特許請求の範囲】
【請求項１】
第１のアレイ回路と第２のアレイ回路を備える情報処理装置であって、
前記アレイ回路の其々は複数のユニットを備え、
前記複数のユニットの其々は、
相互作用モデルの１つのノードの状態を示す値を記憶する第１のメモリセルと、
自己と同一のアレイ回路内で自己ユニットに接続された隣接ユニットのノードからの、相互作用を示す相互作用係数を記憶する第２のメモリセルと、
前記第１のメモリセルの値を制御するためのフラグを記憶する第３のメモリセルと、
前記隣接ユニットのノードの状態を示す値および前記相互作用係数に基づいて、前記１つのノードの次状態を示す値を決定する第１の論理回路と、
前記フラグの値に応じて前記第１のメモリセルの値を変更する第２の論理回路と、を有し、
前記複数のユニットの其々が、自己ユニットの前記第１のメモリセルの内容を、他のアレイ回路の対応するユニットに送信し、かつ前記対応するユニットの前記第１のメモリセルの内容を受信するための、アレイ間配線を有し、
前記フラグは前記アレイ間配線で受信される情報に基づいて生成される、
情報処理装置。
【請求項２】
前記第２の論理回路は、
自己ユニットの前記第１のメモリセルの内容と、前記対応するユニットの前記第１のメモリセルの内容の異同を判定し、異同判定結果を得る異同判定回路を有し、
前記異同判定結果を用いて、前記フラグを生成する、
請求項１記載の情報処理装置。
【請求項３】
前記第２の論理回路は、
自己と同一のアレイ回路内で自己ユニットに接続された隣接ユニットの前記異同判定結果、前記第２のメモリセルに記憶された前記相互作用係数、および自己ユニットの前記異同判定結果に基づいて、前記フラグを決定するクラスター化回路と、
前記決定されたフラグに基づいて前記第１のメモリセルの内容を変更する状態交換回路を有する、
請求項２記載の情報処理装置。
【請求項４】
前記クラスター化回路は、
自己ユニットに接続された隣接ユニットのうち、前記異同判定結果が「異なる」であって当該隣接ユニットのノードからの相互作用を示す相互作用係数が０でないものが少なくとも一つあり、かつ、自己の前記異同判定結果が「異なる」である場合、前記第１のメモリセルの内容を変更するフラグを生成する、
請求項３記載の情報処理装置。
【請求項５】
前記第１のメモリセルの内容は、スピンの値に対応するＨＩＧＨまたはＬＯＷであり、
前記フラグに基づいて前記第１のメモリセルの内容を反転させる、
請求項４記載の情報処理装置。
【請求項６】
前記第１の論理回路を複数サイクル動作させ、当該サイクル動作の間の所定タイミングに、前記第２の論理回路の動作を挿入する、
請求項１記載の情報処理装置。
【請求項７】
複数のイジングチップと、前記複数のイジングチップを制御するコントローラを含む情報処理装置において、
前記複数のイジングチップの其々は複数のユニットを備え、
前記複数のユニットの其々はスピン状態を保持し、
前記コントローラは、前記複数のイジングチップのうち一組のイジングチップに対して、対応するユニットのスピン状態の値を比較するよう指示し、
前記コントローラは、前記一組のイジングチップに対して、対応するユニットのスピン状態の値が異なるスピンのうち、一部のスピンの値を反転するよう指示する、
情報処理装置。
【請求項８】
前記コントローラは、
相互作用演算による前記スピン状態の更新を行う第１の情報処理と、前記スピン状態の値の比較と反転を行う第２の情報処理との処理タイミングの切り替えの指示を行い、
所定サイクルで繰り返される前記第１の情報処理のサイクルの間に、前記第２の情報処理を挿入する、
請求項７記載の情報処理装置。
【請求項９】
前記対応するユニットのスピン状態の値が異なるスピンのうち、一部のスピンとは、
前記第１の情報処理において自己のスピン状態の変更に影響がある他のスピンがあり、当該他のスピンの値が対応するユニットのスピン状態の値と異なっているスピンである、
請求項８記載の情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置に関し、特に、相互作用モデルの計算を行う半導体装置をアクセラレータとして制御する情報処理装置に適用して好適なものである。
【背景技術】
【０００２】
種々の物理現象や社会現象は相互作用モデルで表現することができる。相互作用モデルとは、モデルを構成する複数個のノードと、ノード間の相互作用、さらに必要であればノード毎のバイアスで定義されるモデルである。物理学や社会科学では種々のモデルが提案されているが、いずれも相互作用モデルの一形態であると解釈できる。
【０００３】
物理学の世界で代表的な相互作用モデルの例として、イジングモデルをあげることができる。イジングモデルは磁性体の振舞いを説明するための統計力学のモデルである。イジングモデルは、＋１／−１（ないしは、０／１、上／下）の２値をとるスピンと、スピン間の相互作用を示す相互作用係数、および、スピン毎にある外部磁場係数で定義される。
【０００４】
イジングモデルは、与えられたスピン配列、相互作用係数、および、外部磁場係数で構成される。イジングモデルのエネルギー関数（一般にハミルトニアンとも呼ばれる）は次式で表わされる。
【０００５】
【数１】
2018206127.tif 000003
【０００６】
…（１）
【０００７】
なお、σｉ、σｊはそれぞれｉ番目とｊ番目のスピンの値、Ｊｉ，ｊはｉ番目とｊ番目のスピンの間の相互作用係数、ｈｉはｉ番目のスピンに対する外部磁場係数、σはスピンの配列を表わすものとする。
【０００８】
（１）式において、第一項は、スピン間の相互作用に起因するエネルギーを計算するものである。一般的にイジングモデルは無向グラフとして表現され、ｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を区別することはない。そのため、第一項ではｉ＜ｊを満たすσｉ、σｊの組み合わせについて、相互作用係数の影響を計算している。また第二項は、各スピンに対する外部磁場に起因するエネルギーを計算するものである。
【０００９】
イジングモデルの基底状態探索は、イジングモデルのエネルギー関数を最小化するスピン配列を求める最適化問題である。非平面グラフで表されるイジングモデルの基底状態探索はＮＰ困難であることが知られている。近年、この問題を効率的に解くため基底状態を探索する装置が提案されている（特許文献１、特許文献２）。
【００１０】
また、ある条件下においてイジングモデルのサンプリングを実行して統計量の期待値を算出することによって、機械学習の一手法であるボルツマン機械学習を実現できることが知られている（非特許文献１）。
【００１１】
また、クラスターモンテカルロアルゴリズム（クラスター交換モンテカルロ法；後述）についても知られている（非特許文献２）。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】国際公開２０１４／１９２１５３号
【特許文献２】特開２０１６−５１３１３号公報
【非特許文献】
【００１３】
【非特許文献１】S.  Yamanaka,  M.  Ohzeki,  and  A.  Decelle,  “Detection  of  Cheating  by  Decimation  Algorithm,”  Journal  of  the  Physical  Society  of  Japan,  vol.  84,  no.  2,  p.  024801,  2015.
【非特許文献２】Houdayer, J. “A cluster Monte Carlo algorithm for 2-dimensional spin glasses.” The European Physical Journal B-Condensed Matter and Complex Systems 22.4 (2001): 479-484.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
イジングモデルの基底状態探索やサンプリングを実行するにあたり、一般に、マルコフ連鎖モンテカルロ法（以降、ＭＣＭＣと呼ぶ）が用いられる。ＭＣＭＣは、状態間を確率的に遷移しつつ状態のサンプリングを行うことで所望の統計量を推定する手法である。
【００１５】
図１にイジングモデルのエネルギーランドスケープの概念図を示す。これは横軸にスピン配列、縦軸にそのスピン配列におけるエネルギーをプロットしたものである。
【００１６】
確率的な遷移では、現在の状態σの近傍のある状態σ’へ確率的に遷移を繰り返す。状態σから状態σ’へ遷移する確率を、遷移確率Ｐ（σ，σ’）と呼ぶ。遷移確率としてメトロポリス法や熱浴法などが知られている。例えば、メトロポリス法の遷移確率は（２）式、熱浴法の遷移確率は（３）式である。Ｔは一般に温度と呼ばれるパラメータで、状態間の遷移のし易さを表す。
【００１７】
【数２】
2018206127.tif 000004
【００１８】
…（２）
【００１９】
【数３】
2018206127.tif 000005
【００２０】
…（３）
【００２１】
近傍の状態σ’を生成する方法として、現在の状態σから一つのスピンの値を変えることが一般的である。変更するスピンを一つずつ順番に変えることで、スピン全体の探索を行う。たとえば、図１の場合は、状態Ａから一つのスピンが反転すると状態Ｂ、そしてさらに一つのスピンが反転すると状態Ｃとなる。
【００２２】
しかしながら、スピンを順番に一つずつ更新する場合、状態遷移において高いエネルギー壁を越えることは困難であり，特定領域のスピン配列にトラップされる確率が高まる。たとえば、図１に示す例の場合、状態Ａから状態Ｃへ一度に遷移することは出来ず、状態Ｂを経由して遷移しなければならない。しかし状態Ｂのエネルギーが状態Ａのエネルギーよりも充分に大きい場合、状態Ａから状態Ｂに遷移する確率は低くなる。結果として、有限な回数の状態遷移では、状態Ｃへ遷移が発生せず、この領域に訪れる可能性が低くなる。
【００２３】
本来は各スピン状態を、適切な重みづけに基づいて探索しなければならないにも関わらず、状態間の遷移が困難になることでサンプリングの精度や基底状態探索の解精度を低下させる。結果としてＭＣＭＣのサンプリング回数を増加させなければならず，計算システム全体のエネルギー効率が低下する。
【００２４】
複数のスピンの値を同時に変更し、変更前後のエネルギー差を計算して（２）式に基づく確率的な遷移の有無を決定することで、この課題は解決される。一例としては、クラスターモンテカルロアルゴリズム（Cluster Monte Carlo Algorithm）が知られている（非特許文献２）。たとえば、図１に示す例の場合、状態Ａの近傍として状態Ｃを認めるということである。
【００２５】
しかし、複数のスピンを変更した場合は、エネルギー差の計算のためにスピンの値を外部接続のＣＰＵ（中央処理装置）に転送して計算する必要がある。一般に、この通信は時間を要するもので、計算時間の増加およびエネルギー効率の低下などの問題を発生させる。そこで、ＭＣＭＣを高速化させるハードウェアの実現が求められる。
【課題を解決するための手段】
【００２６】
以下において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
【００２７】
本発明の一側面は、第１のアレイ回路と第２のアレイ回路を備える情報処理装置である。アレイ回路の其々は複数のユニットを備える。複数のユニットの其々は、相互作用モデルの１つのノードの状態を示す値を記憶する第１のメモリセルと、自己と同一のアレイ回路内で自己ユニットに接続された隣接ユニットのノードからの、相互作用を示す相互作用係数を記憶する第２のメモリセルと、第１のメモリセルの値を制御するためのフラグを記憶する第３のメモリセルと、隣接ユニットのノードの状態を示す値および相互作用係数に基づいて、１つのノードの次状態を示す値を決定する第１の論理回路と、フラグの値に応じて第１のメモリセルの値を変更する第２の論理回路と、を有する。さらに、複数のユニットの其々が、自己ユニットの第１のメモリセルの内容を、他のアレイ回路の対応するユニットに送信し、かつ前記対応するユニットの前記第１のメモリセルの内容を受信するための、アレイ間配線を有し、フラグは前記アレイ間配線で受信される情報に基づいて生成される。
【００２８】
本発明の他の一側面は、複数のイジングチップと、複数のイジングチップを制御するコントローラを含む情報処理装置である。複数のイジングチップの其々は複数のユニットを備え、複数のユニットの其々はスピン状態を保持する。コントローラは、複数のイジングチップのうち一組のイジングチップに対して、対応するユニットのスピン状態の値を比較するよう指示し、一組のイジングチップに対して、対応するユニットのスピン状態の値が異なるスピンのうち、一部のスピンの値を反転するよう指示する。
【発明の効果】
【００２９】
ＭＣＭＣを高速化させるハードウェアの実現が可能となる。
【図面の簡単な説明】
【００３０】
【図１】イジングモデルのエネルギーランドスケープの概念図。
【図２】実施の形態における半導体装置を含む情報処理装置の全体構成の一例を示すブロック図。
【図３】実施の形態において、マルチイジングチップの構成の一例を示すブロック図。
【図４】実施の形態において、イジングチップの構成の一例を示すブロック図。
【図５】実施の形態において、２次元格子のスピンアレイの構成の一例を説明する概念図。
【図６】実施の形態において、スピンユニットの構成の一例を示す回路図。
【図７】実施例の処理手順を示すフロー図。
【図８Ａ】処理中のスピンユニットの動作状態の一例を示す回路図。
【図８Ｂ】処理中のスピンユニットの動作状態の一例を示す回路図。
【図８Ｃ】処理中のスピンユニットの動作状態の一例を示す回路図。
【図８Ｄ】処理中のスピンユニットの動作状態の一例を示す回路図。
【図８Ｆ】処理中のスピンユニットの動作状態の一例を示す回路図。
【図９Ａ】実施例の処理の概念を示す模式図。
【図９Ｂ】実施例の処理の概念を示す模式図。
【図１０】ＭＣＭＣの処理手順を示すフロー図。
【発明を実施するための形態】
【００３１】
以下の実施の形態においては、便宜上その必要があるときは、複数のセクションまたは実施の形態に分割して説明するが、特に明示した場合を除き、それらは互いに無関係なものではなく、一方は他方の一部または全部の変形例、詳細、補足説明等の関係にある。また、以下の実施の形態において、要素の数等（個数、数値、量、範囲等を含む）に言及する場合、特に明示した場合および原理的に明らかに特定の数に限定される場合等を除き、その特定の数に限定されるものではなく、特定の数以上でも以下でもよい。
【００３２】
さらに、以下の実施の形態において、その構成要素（要素ステップ等も含む）は、特に明示した場合および原理的に明らかに必須であると考えられる場合等を除き、必ずしも必須のものではないことは言うまでもない。同様に、以下の実施の形態において、構成要素等の形状、位置関係等に言及するときは、特に明示した場合および原理的に明らかにそうでないと考えられる場合等を除き、実質的にその形状等に近似または類似するもの等を含むものとする。このことは、上記数値および範囲についても同様である。
【００３３】
以下、実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一の部材には原則として同一の符号または関連する符号を付し、その繰り返しの説明は省略する。また、以下の実施の形態では、特に必要なとき以外は同一または同様な部分の説明を原則として繰り返さない。同一あるいは同様な機能を有する要素が複数ある場合には、同一の符号に異なる添字を付して説明する場合がある。ただし、複数の要素を区別する必要がない場合には、添字を省略して説明する場合がある。
【００３４】
本明細書等における「第１」、「第２」、「第３」などの表記は、構成要素を識別するために付するものであり、必ずしも、数、順序、もしくはその内容を限定するものではない。また、構成要素の識別のための番号は文脈毎に用いられ、一つの文脈で用いた番号が、他の文脈で必ずしも同一の構成を示すとは限らない。また、ある番号で識別された構成要素が、他の番号で識別された構成要素の機能を兼ねることを妨げるものではない。
【００３５】
実施の形態は、安価かつ容易に製造でき、例えばイジングモデルなどのような任意の相互作用モデルの計算を行うことが可能な半導体装置および情報処理装置に関する。
【００３６】
実施の形態で説明される一つの例は、複数のイジングチップと、複数のイジングチップを制御するコントローラを含む半導体集積回路装置において、コントローラと、複数のイジングチップと接続された状態交換クロック生成部を備えるものである。コントローラは、状態交換クロック生成部が生成するクロック信号に対応して、複数のイジングチップのうち隣接するイジングチップに対して、対応するスピンどうしの値を比較するよう指示する。コントローラは、状態交換クロック生成部が生成するクロック信号に対応して、対応するスピンどうしの値を比較した隣接するイジングチップに対して、対応するスピンどうしの値が異なるスピンのうち、一部のスピンの値を反転するよう指示する。
【００３７】
実施の形態における半導体装置は、単一の変数を逐次的に更新するのではなく、複数の変数を同時に更新しつつマルコフ連鎖モンテカルロ法に基づく計算を実行する半導体装置である。この半導体装置は、メモリと、メモリからデータを読む読み出し部と、読み出し部が読み出したデータに対して所定の演算を行った結果を入力する多数決回路と、多数決回路の出力を入力する書き込み回路と、を備え、多数決回路の前段で所定の信号の値を確率的に反転する。このような例によれば、相互作用ネットワークのスピンの状態を高速かつ大幅に変化することができる。
【００３８】
一実施の形態によれば、安価かつ容易に製造でき、例えばイジングモデルなどのような任意の相互作用モデルの計算を行うことが可能な半導体装置および情報処理装置を提供することができる。
【００３９】
＜（１）相互作用モデル＞
前述のように、種々の物理現象や社会現象は相互作用モデルで表現することができる。相互作用モデルの特徴として、ノード間の影響を２個のノード間の相互作用に限定している（２体間の相互作用）ことがあげられる。例えば、宇宙空間にある惑星の力学を考えてみると、惑星というノードの間に万有引力による相互作用がある点で相互作用モデルの一種とも解釈できるが、惑星間の影響は２個の惑星間にとどまらず、３個以上の惑星が互いに影響し合って複雑な挙動を示す（いわゆる３体問題や多体問題と言われる問題になる）。物理学の世界で代表的な相互作用モデルの例として、前述のイジングモデルをあげることができる。
【００４０】
また、生物学の世界では、脳をモデル化したニューラルネットワークが相互作用モデルの一例である。ニューラルネットワークは、神経細胞のニューロンを模した人工ニューロンをノードとして、人工ニューロン間はシナプス結合という相互作用を持つ。また、各ニューロンにバイアスを与える場合もある。
【００４１】
社会科学の世界では、例えば人間のコミュニケーションを考えると、人間というノードと言語や通信で成される相互作用があることは容易に理解できよう。また、各人間には個別にバイアスがあることも想像できる。そのため、人間のコミュニケーションを、相互作用モデルという点で共通なイジングモデル等に模してその特性を明らかにしようという研究もなされている。
【００４２】
以下においては、イジングモデルの基底状態探索またはサンプリングを行う半導体装置と、その半導体装置をアクセラレータとして制御する情報処理装置の例を説明する。
【００４３】
＜（２）有向グラフに拡張したイジングモデル＞
本実施の形態では、イジングモデルを拡張した、以下の（４）式で示されるモデルを、以降イジングモデルと呼ぶ。
【００４４】
【数４】
2018206127.tif 000006
【００４５】
…（４）
【００４６】
（１）式で示したイジングモデルとの違いは、（４）式では有向グラフで示されるような相互作用が許されることにある。一般的に、イジングモデルはグラフ理論では無向グラフとして描画することができる。それは、イジングモデルの相互作用は、ｉ番目スピンからｊ番目スピンへの相互作用係数Ｊｉ，ｊとｊ番目スピンからｉ番目スピンへの相互作用係数Ｊｊ，ｉとを区別していないことによる。
【００４７】
本実施例はイジングモデルを拡張し、Ｊｉ，ｊとＪｊ，ｉを区別しても適用できるため、有向グラフ化したイジングモデルを取り扱う。なお、無向グラフのイジングモデルを有向グラフのイジングモデルで取り扱う場合には、単にＪｉ，ｊとＪｊ，ｉとの双方向に同じ相互作用係数を定義することで可能である。この場合、同じモデルでも（１）式のエネルギー関数に対して（４）式のエネルギー関数ではエネルギーの値が２倍になる。
【００４８】
＜（３）本実施の形態における情報処理装置の構成＞
＜＜（３−１）半導体装置を含む情報処理装置の全体構成＞＞
半導体装置を含む情報処理装置の全体構成について、図２および図３を用いて説明する。図２は、本実施の形態における半導体装置を含む情報処理装置の全体構成の一例を示すブロック図である。図３は、本実施の形態において、マルチイジングチップの構成の一例を示すブロック図である。
【００４９】
図２において、本実施の形態による情報処理装置を示す。この情報処理装置１は、パーソナルコンピュータやワークステーションまたはサーバなどから構成され、システムバス２を介して接続されたＣＰＵ（Central  Processing  Unit）３、メモリ４、記憶装置５および複数のマルチイジングチップ６を備える。
【００５０】
ＣＰＵ３は、情報処理装置１全体の動作制御を司るプロセッサである。またメモリ４は、例えば揮発性の半導体メモリから構成され、各種プログラム等を記憶するために利用される。記憶装置５は、例えばハードディスク装置やＳＳＤ（Solid  State  Drive）などから構成され、プログラムやデータを長期間保持するために利用される。
【００５１】
本実施の形態の場合、記憶装置５には、本情報処理装置１が解くべき単一かつイジングモデル形式の問題の問題データ７が格納され、メモリ４には、マルチイジングチップ制御プログラム９が格納される。マルチイジングチップ制御プログラム９は、個々のマルチイジングチップ６で問題を解くための制御を行うためのプログラムである。
【００５２】
なお、イジングモデル形式でない問題データをイジングモデル形式の問題データ７に変換するプログラムをメモリ４に格納しておくようにしてもよい。このようにすることによりイジングモデル形式でない問題についても対応可能となり、本情報処理装置１の有用性を向上させることができる。
【００５３】
マルチイジングチップ６は、イジングモデルの基底状態探索を行う専用ハードウェアであり、例えば画面描画処理のための専用ハードウェアであるＧＰＵ（Graphics  Processing  Unit）のように、情報処理装置１に装着する拡張カードの形態を取る。
【００５４】
図３はマルチイジングチップの構成ブロック図である。マルチイジングチップ６は、図３に示すように、インタフェース（Ｉ／Ｆ）１０、イジングチップ群１１および制御部１２を備えて構成され、インタフェース１０およびシステムバス２（図２）を介してＣＰＵ３（図２）との間でコマンドや情報の送受を行う。
【００５５】
イジングチップ群１１は、それぞれがイジングモデルの基底状態探索やサンプリングを行う専用のハードウェアである複数のイジングチップ１３から構成される。イジングチップ１３間はチップ間配線１４により接続されており、このチップ間配線１４を介してイジングチップ１３同士が必要な情報を送受する。
【００５６】
制御部１２は、イジングチップ群１１を構成する各イジングチップ１３を制御する機能を有し、コントローラ１５、相互作用クロック生成器１６、状態交換クロック生成器１７、および乱数発生器８を備えて構成される。
【００５７】
コントローラ１５は、マルチイジングチップ６全体の動作制御を司るプロセッサであり、情報処理装置１のＣＰＵ３（図２）からシステムバス２（図２）およびインタフェース１０を介して与えられるコマンドに従ってイジングチップ群１１を構成する各イジングチップ１３の動作や、相互作用クロック生成器１６、状態交換クロック生成器１７、および乱数発生器８を制御する。
【００５８】
また相互作用クロック生成器１６は、相互作用クロックＩＣＬＫを生成するクロック生成器である。相互作用クロックＩＣＬＫは、イジングチップ群１１を構成する各イジングチップ１３にそれぞれ与えられる。乱数発生器８は、各イジングチップ１３において実行する処理で用いるランダムなビット列である乱数ＲＮＤを発生させる。乱数ＲＮＤは、各イジングチップ１３にそれぞれ与えられる。
【００５９】
また状態交換クロック生成器１７は、状態交換クロックＥＣＬＫを生成するクロック生成器である。状態交換クロックＥＣＬＫは、イジングチップ群１１を構成する各イジングチップ１３にそれぞれ与えられる。
【００６０】
＜＜（３−２）イジングチップの構成＞＞
図４を用いてイジングチップ１３の構成について説明する。図４は、本実施の形態において、イジングチップ１３の構成の一例を示すブロック図である。イジングチップは、スピンアレイを内包し各スピンの値を相互作用計算により更新処理する半導体集積回路である。
【００６１】
図４に示すように、イジングチップ１３は、スピンアレイ２０、Ｉ／Ｏ（Input/output）アドレスデコーダ２１、Ｉ／Ｏドライバ２２、相互作用アドレスデコーダ２３、状態交換アドレスデコーダ４０３、およびチップ間接続部２４を備えて構成される。本実施の形態では、イジングチップ１３は現在広く用いられているＣＭＯＳ（Complementary  Metal-Oxide  Semiconductor）集積回路として実装されていることを想定して説明するが、他の固体素子でも実現可能である。
【００６２】
イジングチップ１３は、スピンアレイ２０のメモリセルにリード／ライトを行うためのＳＲＡＭ互換インタフェース３０として、アドレスバス３１、データバス３２、Ｒ／Ｗ制御線３３およびＩ／Ｏクロック線３４を備える。またイジングチップ１３は、イジングモデルの基底状態探索の制御を行うための相互作用制御インタフェース３５として、相互作用アドレス線３６および相互作用クロック線３７も備える。
【００６３】
イジングチップ１３では、イジングモデルのスピンσｉ、相互作用係数Ｊｉ，ｊおよび外部磁場係数ｈｉをすべてスピンアレイ２０内のメモリセルに記憶する情報で表現する。スピンσｉの初期状態の設定やＭＣＭＣを実施後のスピン配列の読み出しはＳＲＡＭ互換インタフェース３０を介して行う。またイジングチップ１３では、ＭＣＭＣを実行すべきイジングモデルをスピンアレイ２０に設定するための相互作用係数Ｊｉ，ｊおよび外部磁場係数ｈｉのリード／ライトもＳＲＡＭ互換インタフェース３０を介して行う。
【００６４】
そのため、スピンアレイ２０内のスピンσｉ、相互作用係数Ｊｉ，ｊおよび外部磁場係数ｈｉにはアドレスが付与されている。そしてイジングチップ１３にスピンσｉ、相互作用係数Ｊｉ，ｊまたは外部磁場係数ｈｉをリード／ライトする場合、対応するアドレスがコントローラ１５からアドレスバス３１を介してＩ／Ｏアドレスデコーダ２１に与えられ、これらスピンσｉ、相互作用係数Ｊｉ，ｊおよび外部磁場係数ｈｉのリード／ライトを制御するＲ／Ｗ制御信号がコントローラ１５からＲ／Ｗ制御線３３を介してＩ／Ｏドライバ２２に与えられる。
【００６５】
かくしてＩ／Ｏアドレスデコーダ２１は、アドレスバス３１を介して与えられたアドレスに基づいてスピンアレイ２０のワード線をアクティベートし、Ｉ／Ｏドライバ２２は、Ｒ／Ｗ制御線３３を介して与えられたＲ／Ｗ制御信号に基づいてスピンアレイ２０内の対応するビット線を駆動する。これによりデータバス３２を介して与えられたスピンσｉの初期値や、相互作用係数Ｊｉ，ｊおよび外部磁場係数ｈｉの設定値がスピンアレイ２０に設定され、または、ＭＣＭＣを実施後の解がスピンアレイ２０から読み出されてデータバス３２を介して外部に出力される。
【００６６】
なお、ＳＲＡＭ互換インタフェース３０を構成するアドレスバス３１、データバス３２およびＲ／Ｗ制御線３３は、Ｉ／Ｏクロック線３４を介して制御部１２からイジングチップ１３に与えられるＩ／Ｏクロックに同期する。
【００６７】
また、イジングチップ１３は、ＭＣＭＣを行うために、スピンアレイ２０の内部でスピン間の相互作用を実現する。この相互作用を外部から制御するのが相互作用制御インタフェース３５である。イジングチップ１３は、コントローラ１５から与えられる相互作用を行うスピン群を指定するアドレスを相互作用アドレス線３６経由で入力し、相互作用クロック線３７を介して入力される相互作用クロック生成器１６からの相互作用クロックに同期して相互作用を行う。相互作用アドレスデコーダ２３は、相互作用アドレス線３６を介して与えられたアドレスに基づいて、スピンアレイ２０に対するスピンの値、相互作用係数Ｊｉ，ｊおよび外部磁場係数ｈｉのリード／ライトを行う。
【００６８】
イジングチップ１３は、後述のようにスピンアレイ２０内のメモリから読み出したデータ、またはこのデータに所定の演算を行った結果を確率的に反転させるため、乱数ＲＮＤを注入する乱数信号線３８を有する。図３について上述した乱数発生器８により発生された乱数ＲＮＤは、この乱数信号線３８を介してスピンアレイ２０に与えられる。
【００６９】
また、イジングチップ１３は、スピンアレイ２０の内部でクラスター交換（状態交換）を実現する。このクラスター交換を外部から制御するのが状態交換制御インタフェース４００である。イジングチップ１３は、コントローラ１５から与えられる状態交換を行うスピン群を指定するアドレスを状態交換アドレス線４０１経由で入力し、状態交換クロック線４０２を介して入力される状態交換クロック生成器１７からの状態交換クロックに同期してクラスター交換を行う。状態交換アドレスデコーダ４０３は、状態交換アドレス線４０１を介して与えられたアドレスに基づいてスピンアレイ２０に対するクラスター交換のため、後述のメモリセルＮおよびメモリセルＭのリード／ライトを行う。
【００７０】
チップ間接続部２４は、隣接して配置されたイジングチップ１３との間で必要なスピンσｉの値を送受する際のインタフェースとして機能する。
【００７１】
＜＜（３−３）スピンアレイの構成＞＞
図５は２次元格子のスピンアレイおよびその接続関係について模式的に説明する概念図である。スピンアレイ２０は、１個のスピンσｉならびにそれに付随する相互作用係数Ｊｉ，ｊおよび外部磁場係数ｈｉを保持するメモリと、ＭＣＭＣを実現する演算回路を有するスピンユニット４０を基本構成単位として、スピンユニット４０を多数個並べた構成を有する。
【００７２】
図５において、スピンアレイ２０は３×３の９個のスピンユニット４０を持つこととし、スピンユニット４０が持つスピンを丸で示している。ここでは２つのスピンアレイ２０Ａと２０Ｂに着目して示している。スピンアレイ２０は一つのイジングチップ１３によって実現される
図５に示す１個のスピンユニット４０には、他のスピンユニットのスピンの値が入力される。図５では便宜的に上下左右に配置された４個のスピンユニットのスピンの値を入力することとした。あるスピンユニットに対してスピンの値を入力するスピンユニットを便宜上、「隣接スピンユニット（隣接ノード）」ということにする。ただしこれは必ずしも物理的あるいは幾何学的にスピンユニットが隣接配置されていることを意味しない。
【００７３】
スピンユニット４０は、スピンの値を保持するためのメモリセルＮを有している。スピンの値は、たとえばスピンの上／下の値を、ＨＩＧＨ／ＬＯＷで表す。図５では各スピンアレイ２０の中央のスピンユニットに着目して、スピンの値の入出力を矢印で示している。またスピンユニット４０は、かかるスピンの値に加え、外部磁場係数と、上述した隣接スピンユニットとの相互作用係数をそれぞれ保持するメモリセルも有している。このような相互作用を行うスピンアレイの構成については、例えば特許文献２に記載がある。
【００７４】
本実施例では、スピンユニット４０はさらに、他のスピンアレイ２０が持つ対応するスピンユニット４０のスピンとの異同を表すメモリセルＭを有する。すなわち、図５に示すように、一組のスピンアレイ２０Ａと２０Ｂは、其々スピンユニット４０のスピンの値を、チップ間配線１４を用いて対応するスピンユニット４０に送信する。図５では対応するスピンユニットにはＮ１１のように同じ符号を付している。以降これらを便宜上「対応スピンユニット」ということにする。対応スピンユニットのスピンの値を受信したスピンユニット４０は、自己のスピンの値との異同を判定し、結果をメモリセルＭに格納する。
【００７５】
なお、図５ではスピンユニットの位置をＮｘｙというように、横方向および縦方向の位置によって示している。スピンユニット４０をタイル状に配置することでスピンアレイ２０が実現される。図５では、スピンユニット４０が含むスピンアレイを２個ずつ組にしてスピンの値を交換することにしたが、３個以上を組にして相互にスピンの値を交換することにしてもよい。
【００７６】
＜＜（３−４）スピンユニットの構成＞＞
図６は、本実施の形態において、スピンユニット４０の構成の一例を示す回路ブロック図である。一つのスピンユニットは、イジングモデルの一つのノードに対応する。図示しないが、スピンユニット４０が有するメモリセルには、イジングチップ１３外からアクセスするためのインタフェースであるビット線とワード線が配置され、リード/ライトのタイミングが制御される。これは従来の半導体メモリの制御方式を踏襲するものであり、本明細書で特記する以外の部分は、例えば特許文献２に記載の技術を適用可能である。
【００７７】
図６を参照しつつスピンユニット４０の構成を説明する。メモリセルＮはスピンを表現するためのメモリセルであり、スピンの値を保持する。スピンの値はイジングモデルでは＋１／−１（＋１を上、−１を下とも表現する）であるが、これをメモリセルが保持可能な２値である０／１に対応させる。例えば、＋１を１、−１を０に対応させる。
【００７８】
メモリセルＭは、異なるイジングチップ１３の対応スピンユニットのスピンと値が異なるかどうかを表現したり、クラスターに含めるかどうかを表現したりするためのメモリセルである。本実施例では、マルチイジングチップ６内の各イジングチップ１３は、同一モデルの基底状態探索を行う前提である。
【００７９】
イジングモデルを有向グラフとして捉えた場合に、あるスピンから見ると他のスピンが自スピンに及ぼす影響の係数を持つことになる。自スピンが他のスピンに与える影響の係数は、それぞれの他のスピンに属する。
【００８０】
図５および図６の例では、このスピンユニット４０は最大で５個のスピンユニットと接続される。すなわち、図５のＮ１１に着目すれば、Ｎ０１、Ｎ１０，Ｎ１２，Ｎ２１の４個のスピンユニットからそれらのスピンの値Ｓ１〜Ｓ４を得、また自分のスピンＳ（自分のメモリセルＮに格納された値）をこれらに送信する。また、チップ間配線１４を用いて対応スピンユニット４０と接続され、スピンの値を送受信することができる。
【００８１】
スピンユニット４０は、自スピンに及ぼす影響を示す相互作用係数Ｊ１〜Ｊ４を格納する４組のメモリセルを備える。さらに、外部磁場係数Ｈを格納する一組のメモリセルを備える。
【００８２】
本実施の形態のイジングチップ１３では、外部磁場係数Ｈおよび相互作用係数Ｊ１〜Ｊ４を、それぞれ＋１／０／−１の３値に対応させる。そのため、外部磁場係数および相互作用係数を表わすためには、それぞれ２ビットのメモリセルが必要となる。このため、本実施例では其々の係数のために、１ビットのメモリセルを一組用いることにしている。
【００８３】
メモリセルＨ［０］、Ｊｋ［０］（１≦ｋ≦４）はそれぞれ対応する外部磁場係数および相互作用係数が正のとき１、０以下のとき０とする。またメモリセルＨ［１］、Ｊｋ［１］はそれぞれが対応する係数の絶対値が１のとき１、０のとき０を与える。例えばスピンユニットの保持する外部磁場係数が−１のときＨ［０］＝０、Ｈ［１］＝１である。
【００８４】
スピンユニット４０内のメモリセルＮ、メモリセルＭ、Ｈ［ｕ］、Ｊｋ［ｕ］（０≦ｕ≦１、１≦ｉ≦４）は、それぞれイジングチップ１３の外部からリード／ライト可能でなければならない。そのために、前述のように、スピンユニット４０はビット線とワード線とをそれぞれ有している（図示せず）。
【００８５】
そしてイジングチップ１３では、スピンユニット４０が半導体基板上にタイル状に並べられてビット線とワード線とが接続されており、Ｉ／Ｏアドレスデコーダ２１とＩ／Ｏドライバ２２でこれらのスピンユニット４０を駆動、制御または読み出しすることにより、一般的なＳＲＡＭ（Static  Random  Access  Memory）と同様に、スピンユニット４０内のメモリセルをイジングチップ１３のＳＲＡＭ互換インタフェース３０でリード／ライトすることができる。かかるＳＲＡＭ互換インタフェースについては、特許文献２に開示がある。
【００８６】
また、スピンユニット４０は同時に更新を行うために、相互作用を計算して次のスピンの状態を決定するための回路を、スピンユニット４０毎に独立して持っている。図６では、スピンユニット４０は、外部とのインタフェースと、信号ＩＡ、Ｎ’、Ｏ、Ｋ、ＳＷ、Ｓｋ（１≦ｋ≦４）、ＲＮＤ、ＲＶ、およびＥＸをやり取りする。
【００８７】
信号ＩＡは、状態交換制御インタフェース４００から供給され、当該スピンユニット４０のスピンの更新を許可する切替え信号を入力する。この切替え信号でセレクタ４３を制御する。
【００８８】
信号Ｎ’は他のイジングチップ（図５でチップ間配線１４を介して接続されるイジングチップ１３）が持つスピンアレイにおいて、対応スピンユニット４０が有するメモリセルＮの値を渡す。これはチップ間接続部２４から入力される。
【００８９】
信号Ｏは、当該スピンユニット４０の出力である。信号Ｏの内容は信号Ｋにより制御されるセレクタ５５により、メモリセルＮの内容とメモリセルＭの内容が切り替わる。また、信号Ｏの出力先は信号ＳＷで切り替わるセレクタ５９により、同一イジングチップ内の他のスピンユニットと、他のイジングチップ内の対応スピンユニットとの間で出力先が切り替わる。すなわち、図５の矢印で示す信号経路のうち、チップ間配線１４とイジングチップ１３内のチップ内配線６００とで出力先を切り替える。
【００９０】
信号Ｋは、上記のセレクタ５５の出力を切り替え、メモリセルＮの内容とメモリセルＭの内容を選択出力する信号であり、状態交換制御インタフェース４００から供給される。ＫがＨＩＧＨの場合には出力はメモリセルＭの内容であり、ＫがＬＯＷの場合には出力はメモリセルＮの内容である。セレクタ５５の出力はセレクタ５９の入力となる。
【００９１】
信号ＳＷは、上記のセレクタ５９の出力先を切り替える信号であり、状態交換制御インタフェース４００から供給される。ＳＨがＨＩＧＨの場合には出力はチップ間配線１４へ出力され、ＳＨがＬＯＷの場合には出力はチップ内の他のスピンユニットへ出力される。
【００９２】
信号Ｓｋ（１≦ｋ≦４）は、それぞれ他のスピンユニット４０（図５のトポロジで、イジングチップ１３内の隣接スピンユニット）から、そのスピンの値の信号を受け取る。
【００９３】
信号ＲＮＤはビット確率を変更する乱数であり、乱数信号線３８から供給される。
【００９４】
信号ＲＶは、状態交換制御インタフェース４００から供給され、セレクタ５８を制御する。セレクタ５８の入力のうち、メモリセルＭと繋がっていない側の信号は常にＨＩＧＨとする。
【００９５】
信号ＥＸは、状態交換制御インタフェース４００から供給され、セレクタ５２を制御する。ＥＸがＨＩＧＨのとき、セレクタ５２はＡＮＤゲート６０１の出力を出力し、ＥＸがＬＯＷのとき、セレクタ５２はＸＯＲゲート５３の出力を出力する。
【００９６】
演算回路４４はメモリセルＨ［ｕ］、Ｊｋ［ｕ］（０≦ｕ≦１、１≦ｉ≦４）から読み出した値および信号ＲＮＤを受け取り、メトロポリス法または熱浴法などＭＣＭＣが求める確率的な振る舞いを実行する。
【００９７】
＜＜（３−５）スピンユニットの動作＞＞
本実施例のスピンユニットでは、クラスター交換モンテカルロ法をハードウェア的に実現し、複数のスピンの値を同時に変更することで、ＭＣＭＣのサンプリング回数の増加を抑制し、計算システム全体のエネルギー効率を改善する。図７は本実施例のスピンユニット４０の動作概略を示す流れ図である。図８Ａ〜Ｆは各動作における信号経路を太線の矢印で示す図である。
【００９８】
図７に加えて図８Ａ〜Ｆを参照して、スピンユニットで行われる一連の処理を説明する。まず、信号Ｋ，ＳＥ，ＲＶおよび信号ＩＡがＬＯＷのとき、メモリセルＮにはスピンの値Ｓ１〜Ｓ４に基づいて演算回路４４の出力が書き込まれる。スピンの値Ｓ１〜Ｓ４は同一イジングチップ内の隣接スピンユニットから得る値である。セレクタ５５はメモリセルＮの値をスピンＳとして出力する。スピンＳの値はセレクタ５９により、同一イジングチップ内の他のスピンユニットに送られる。
【００９９】
演算回路４４は、メモリセルＨ［ｕ］、Ｊｋ［ｕ］から読み出した相互作用係数、スピンの値Ｓ１〜Ｓ４、および乱数ＲＮＤによって、スピンの次状態を示す値を決定し、メモリセルＮに格納する。よってこの状態では、スピンユニットは隣接スピンユニットの情報を用いた、従来から実現している相互作用演算によるスピン更新を実行する（スピン更新処理Ｓ７１０、図８Ａ参照）。処理のタイミングは相互作用クロックＩＣＬＫに基づき制御する。相互作用演算によるスピン更新については、例えば特許文献１や特許文献２にも記載があるので、詳細は省略する。
【０１００】
次に、クラスター交換のプロセス（処理Ｓ７３０）を説明する。このプロセスは、従来から実現している上記スピン更新の途中の所望のタイミングで実行される。タイミングや回数はハードウェア構成や解決する問題にも依存するが、任意である。この制御は、マルチイジングチップ制御プログラム９の制御により、状態交換制御インタフェース４００から開始タイミングを指示することにより行うことができる（処理Ｓ７２０）。タイミングは状態交換クロックＥＣＬＫに基づき制御する。この処理Ｓ７３０はたとえば、基底状態探索の初期段階でより多く（高頻度）、後半で少なく（低頻度）行うことが考えられる。
【０１０１】
クラスター交換のプロセスでは、信号ＩＡをＨＩＧＨに定め、通常のスピン更新は停止する。図７に示すようにクラスター交換のプロセス（処理Ｓ７３０）は、３つのステップを含む。対応スピンユニットとのスピン異同判定（処理Ｓ７３１）、スピンユニットのクラスター化（処理Ｓ７３２）、クラスター化されたスピンユニットのスピン値の変更（処理Ｓ７３３）である。
【０１０２】
スピンユニットのクラスター化（処理Ｓ７３２）の結果として、メモリセルＭの内容はクラスター交換モンテカルロ法において、自スピンユニットをクラスターに含めるかどうかを表す。メモリセルＭがＬＯＷならばクラスターに含めず、ＨＩＧＨならクラスターに含めることとする。そして、クラスターに属するスピンユニットのスピンを纏めて変更する。
【０１０３】
対応スピンユニットとのスピン異同判定（処理Ｓ７３１）では、信号ＩＡがＨＩＧＨの状態において、信号ＫをＬＯＷのまま、信号ＥＸをＬＯＷに、信号ＳＷをＨＩＧＨに定める（図８Ｂ参照）。この結果、メモリセルＮの内容であるスピンの値は、チップ間配線１４を経由して、隣接するイジングチップ１３の対応スピンユニット４０に送られる。これは例えば図５のイジングチップ１３Ａと１３Ｂで、中央のスピンユニットがスピンの状態を通知し合うことに相当する。
【０１０４】
受信側では、セレクタ５２はＸＯＲゲート５３の値を出力する。ＸＯＲゲート５３の出力は、自スピンＮおよび隣接する系の対応スピンＮ’（対応するイジングチップ１３の対応スピンユニット４０のスピン）が異なる値かどうかを表し、この結果がメモリセルＭに書き込まれる。排他的論理和の結果、スピンが同じであればＬＯＷが書き込まれ、異なればＨＩＧＨが書き込まれる。メモリセルＭにＨＩＧＨが書き込まれているスピンユニットを、便宜上「不一致スピンユニット」という。
【０１０５】
次に、信号ＩＡをＨＩＧＨのまま、信号ＫをＨＩＧＨに、信号ＳＷをＬＯＷにする（図８Ｃ参照）。この結果、スピンの異同を示すメモリセルＭの内容は、チップ内配線６００により、同一チップ内の隣接スピンユニットに送られる。隣接スピンユニットでは、メモリセルＭの内容（Ｍ１〜Ｍ４で示す）を受信する。このとき、信号ＩＡはＨＩＧＨであり、演算回路４４からの出力はメモリセルＮには供給されない。
【０１０６】
次に、スピンユニットのクラスター化（処理Ｓ７３２）では、不一致スピンユニットの一部の集合をクラスターとして抽出する。本実施例では、一例として以下のように構成した。
【０１０７】
すなわち、信号ＩＡはＨＩＧＨのまま、信号ＥＸをＨＩＧＨに定める（図８Ｄ参照）。すると、セレクタ５２はＡＮＤゲート６０１の値を出力する。ＡＮＤゲート６０１はＯＲゲート５６の値とメモリセルＭの値の論理積を出力する。ＯＲゲート５６は複数のＡＮＤゲート５４の出力を入力とする。ＡＮＤゲート５４は隣接のスピンユニットから出力される信号Ｍｋ（１≦ｋ≦４）およびメモリセルＪｋ［１］（１≦ｉ≦４）を入力とする。前述の通り、Ｊｋ［１］は対応する係数の絶対値を表すと約束しているため、相互作用係数が０のとき、対応するＡＮＤゲート５４はＬＯＷを出力する。
【０１０８】
図８Ｄの処理では、隣接スピンユニットと０でない相互作用があり、かつ、隣接スピンユニットが不一致スピンユニットの場合のみ、対応するＡＮＤゲート５４はＨＩＧＨを出力し、これらはＯＲゲート５６に入力される。
【０１０９】
また、隣接スピンユニットと０でない相互作用があり、かつ、その隣接スピンユニットが不一致スピンユニットである場合が少なくとも１つある場合、ＯＲゲート５６はＨＩＧＨを出力する。
【０１１０】
ＡＮＤゲート６０１によって、ＯＲゲート５６の出力とメモリセルＭの出力との論理積を生成する。すなわち、自分が不一致スピンユニットであり、かつ、隣接スピンユニットの少なくとも一つが不一致スピンユニットであって０でない相互作用がある場合、ＡＮＤゲート６０１はＨＩＧＨを出力し、その結果はメモリセルＭに書き込まれる。
【０１１１】
図９ＡおよびＢにより上記処理の意味を説明する。図９Ａは、一組のイジングチップ１３Ａのスピンの値を(a)に、１３Ｂのスピンユニットのスピンの値を(b)に、模式的に示したものである。白と黒の丸がスピンの上下を示している。各スピンユニットは、自分の上下左右の４個のスピンユニットと相互作用を持つものとする。図８Ｂの処理では、一組のイジングチップ１３Ａと１３Ｂは、チップ間配線１４経由で自分のスピンの値を互いに知らせ、スピンの値が相手と異なる場合、メモリセルＭにＨＩＧＨを書き込む。図９Ｂ(a)に、メモリセルＭにＨＩＧＨが書き込まれたスピンユニットの様子を、斜線を付した丸により示す。
【０１１２】
次に、図８ＣおよびＤの処理では、メモリセルＭにＨＩＧＨが書き込まれており、かつ、隣接スピンユニットのメモリセルＭにＨＩＧＨが書き込まれており、かつ、その隣接スピンユニットとの相互作用係数が０でない場合、メモリセルＭの内容はＨＩＧＨに維持される。
【０１１３】
図９Ｂ(b)に、メモリセルＭにＨＩＧＨが維持されたスピンユニットの様子を、斜線を付した丸により示し、０でない相互作用を二重線で示す。すなわち、不一致スピンユニットであるが孤立したスピンユニット９０１を除き、クラスター（集団）となっているスピンユニット９０２を抽出することができる。
【０１１４】
これらのクラスターは、不一致スピンユニットであって、相互作用計算において自己のスピン状態の変更に影響がある他のスピンを持ち、当該他のスピンも不一致スピンユニットであるものの集合といえる。
【０１１５】
以上はクラスタリング手法の一例である。上記の他にも、自分が不一致スピンユニットであり、かつ、隣接スピンユニットの少なくとも２つ（あるいは任意の数）が不一致スピンユニットであって０でない相互作用がある場合、のようにクラスタリング条件は適宜設定することができる。
【０１１６】
クラスター化の後、状態交換を行う（処理Ｓ７３３）。ここで信号ＲＶをＨＩＧＨとする。このときセレクタ５８はメモリセルＭからの信号を出力する。そしてＸＯＲゲート５７は、メモリセルＭの値およびメモリセルＮの値の排他的論理和を出力してメモリセルＮに書き込む（図８Ｆ）。この結果、メモリセルＭの値がＨＩＧＨの場合にはメモリセルＮの値は反転し、メモリセルＭの値がＬＯＷの場合にはメモリセルＮの値は変化しない。この動作は、図９Ｂ(b)の斜線で示すスピンユニットの値を反転させることに相当し、クラスター交換モンテカルロ法におけるクラスター交換に相当する。
【０１１７】
以上の処理が１つの単位となり、基本的にすべてのスピンユニットで並列処理が行われる。この処理により、他のイジングチップとスピンの値が異なる領域を抽出し、纏めてスピンを反転させることにより、イジングチップ内の処理だけで複数のスピンの値を同時に変更し、効率的に基底状態を探索することができる。前記処理を繰り返すことで、クラスター交換モンテカルロ法を実現することが可能となる。
【０１１８】
相互作用演算は所定の探索完了条件を達成した際には、終了となる（処理Ｓ７１５）。
【０１１９】
＜（４）イジングチップの制御手順＞
イジングチップの制御手順について説明する。図１０は、本実施の形態において、ＭＣＭＣの処理手順を示すフローチャートである。
【０１２０】
図１０は、本実施の形態の情報処理装置１において、ＣＰＵ３（図１）により実行される基底状態探索処理の処理手順を示す。この処理は、主に図７の相互作用演算によるスピン更新処理Ｓ７１０に対応する。
【０１２１】
ＣＰＵ３は、ステップＳＰ１については図示しない問題変換プログラムに基づいて処理する。これ以降の処理（ステップＳＰ２〜ステップＳＰ１１）についてはマルチイジングチップ制御プログラム９（図１）に基づいて、必要なマルチイジングチップ６（図２）のコントローラ１５（図２）を介して当該マルチイジングチップ６内のイジングチップ１３を制御することにより、これらのイジングチップ１３において基底状態探索を実行させる。なお、ステップＳＰ１の処理と、ステップＳＰ２〜ステップＳＰ１１の処理とを別々のタイミングで実行するようにしてもよい。
【０１２２】
またＣＰＵ３は、各マルチイジングチップ６内のイジングチップ１３や、イジングチップ１３内のスピンユニット４０をマルチイジングチップ６内のコントローラ１５（図２）を介して制御するが、以下においては理解の容易化のため、コントローラ１５の存在を省略して説明を行う。
【０１２３】
ＣＰＵ３は、ユーザからの指示等によりこの基底状態探索処理を開始すると、まず、問題データ７（図１）をイジングモデルの形式のデータに変換する（ステップＳＰ１）。問題データ７がすでにイジングモデルの形式のデータである場合、ステップＳＰ１は省略する。
【０１２４】
続いて、ＣＰＵ３は、変換後のイジングモデルの相互作用係数および外部磁場係数を必要なマルチイジングチップ６の各イジングチップ１３内の各スピンユニット４０にそれぞれ設定する（ステップＳＰ２）。
【０１２５】
次に初期スピン配列を生成してスピンを初期化する。本実施例では、数値はすべて同じ値でもよいが、通常はスピンの初期値はランダムな値とする。メモリマップに基づいて、係数と初期スピン配列をスピンアレイに書き込む。（ステップＳＰ３）。
【０１２６】
モデルに基づいてビット確率を設定し（ステップＳＰ４）、相互作用回数を設定する（ステップＳＰ５）。相互作用演算を実行し（ステップＳＰ６）、すべてのスピンアレイについて実行が完了したかどうかを判定する（ステップＳＰ７）。未完了ならば、次のスピンアレイに対して相互作用演算を実行する（ステップＳＰ６）。すべてのスピンアレイに実行が完了したら、規定の相互作用回数を実行したかどうか判定する（ステップＳＰ８）。未完了であれば、ビット確率を更新し（ステップＳＰ９）、相互作用回数をインクリメントし（ステップＳＰ１０）、相互作用計算を継続する。
【０１２７】
図７で説明したように、相互作用演算によるスピン更新の間に、適宜クラスター交換処理を挿入する。挿入回数は１回もしくは複数回である。挿入のタイミングは、相互作用回数を設定する際に同時に定めておいてもよい（ステップＳＰ５）。
【０１２８】
ビット確率の更新は、乱数ＲＮＤを調整することで行う。本実施例では、スピンの値を所定確率で反転させるために、乱数発生器８を用いる。更新においては、例えばスピンの値を仮想的な温度Ｔで決まる確率で反転させ、基底状態探索の初期では高い確率でスピンの値を反転させ、終期では低い確率でスピンの値を反転させるように調整する。このようにすると、基底状態探索の過程で、高い温度から徐々に冷却する物理的なアニーリングを模倣することができる。
【０１２９】
規定の相互作用回数を実行済であれば、スピンの値を読みだす（ステップＳＰ１１）。そしてＣＰＵ３は、この後、この基底状態探索処理を終了する。以上のようにして、ＭＣＭＣを実行することができる。
【０１３０】
本実施例では、各イジングチップ１３は同一モデルの基底状態探索を行っており、係数設定（ステップｐＳＰ２）〜相互作用回数の設定（ステップＳＰ５）まで共通の設定がなされる。しかし、ＳＰ６以降の相互作用演算では、各スピンユニットは乱数ＲＮＤにより確率的に異なる結果を導くことになる。
【０１３１】
＜（５）本実施の形態の効果＞
以上説明した本実施の形態の半導体装置および情報処理装置によれば、安価かつ容易に製造でき、例えばイジングモデルなどのような任意の相互作用モデルの計算を行うことが可能となる。すなわち、本実施の形態の情報処理装置では、単一の変数を逐次的に更新するのではなく、複数の変数を同時に更新しつつＭＣＭＣを実行することができる。かくして、イジングモデルの基底状態または当該基底状態の近似解を精度高く得ることやサンプリングを高精度に行うための情報処理装置を、安価かつ容易に製造できる。より詳細には、以下の通りである。
【０１３２】
本実施例によれば、イジングモデルに代表される相互作用モデルに対してＭＣＭＣを実現する場合において、効率的な状態探索に求められる状態遷移を、データ転送を抑制して高速に実現可能となる。すなわち、外部接続の計算機へ情報を転送する負荷を低減し，例えばイジングモデルなどのような任意の相互作用ネットワークに対して高速に計算することが可能となる。本実施例によれば、適切なサンプリングを実現するための条件を満たしつつスピン配列を大幅に変えることなどによって、ＭＣＭＣを高速化させるハードウェアが実現される。
【０１３３】
以上、本発明者によってなされた発明をその実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。
【０１３４】
例えば、上述した実施の形態は、本発明を分かり易く説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施の形態の構成の一部を他の実施の形態の構成に置き換えることが可能であり、また、ある実施の形態の構成に他の実施の形態の構成を加えることも可能である。また、各実施の形態の構成の一部について、他の構成の追加・削除・置換をすることが可能である。
【符号の説明】
【０１３５】
１…情報処理装置、２…システムバス、３…ＣＰＵ、４…メモリ、５…記憶装置、６…マルチイジングチップ、７…問題データ、８…乱数発生器、９…マルチイジングチップ制御プログラム、１１…イジングチップ群、１２…制御部、１３…イジングチップ、１４…チップ間配線、１５…コントローラ、１６…相互作用クロック生成器、２０…スピンアレイ、２４…チップ間接続部、４０…スピンユニット、４４…演算回路、３８…乱数信号線
【図１】
2018206127.tif 000007
【図２】
2018206127.tif 000008
【図３】
2018206127.tif 000009
【図４】
2018206127.tif 000010
【図５】
2018206127.tif 000011
【図６】
2018206127.tif 000012
【図７】
2018206127.tif 000013
【図８Ａ】
2018206127.tif 000014
【図８Ｂ】
2018206127.tif 000015
【図８Ｃ】
2018206127.tif 000016
【図８Ｄ】
2018206127.tif 000017
【図８Ｆ】
2018206127.tif 000018
【図９Ａ】
2018206127.tif 000019
【図９Ｂ】
2018206127.tif 000020
【図１０】
2018206127.tif 000021