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