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