(57)【要約】  規模と精度とを可変にすること。  記憶部（１１）は、イジングモデルの状態を表すスピンビット列のうちのビット間の相互作用の大きさを示す係数を記憶する。ビット演算回路（１ａ１〜１ａＮ）の各々は、スピンビット列のうちの何れかのビットが反転されると、記憶部から読み出した反転されたビットと自ビットとに対応する係数を用いたエネルギー変化の計算に応じて、自ビットの反転可否を示す信号を出力する。選択回路部（２）は、スピンビット列の第１のビット数（Ｋ）のビット演算回路（１ａ１〜１ａＫ）の各々から出力された反転可否を示す信号に基づいて選択した反転させるビットを示す信号をビット演算回路（１ａ１〜１ａＫ）の各々に出力する。設定変更部（５）は、選択回路部（２）に対する第１のビット数（Ｋ）の変更およびビット演算回路（１ａ１〜１ａＫ）に対する係数の第２のビット数の変更を行う。
2020054061.tif 000002
【特許請求の範囲】
【請求項１】
イジングモデルの状態を表すビット列のうちのビット間の相互作用の大きさを示す係数を記憶する記憶部と、
前記ビット列のうちの何れかのビットが反転されると、前記記憶部から読み出した反転された前記ビットと自ビットとに対応する係数を用いた前記イジングモデルのエネルギー変化の計算に応じて、前記自ビットの反転可否を示す信号を出力する複数のビット演算回路と、
前記複数のビット演算回路のうち前記ビット列の第１のビット数のビット演算回路の各々から出力された反転可否を示す信号に基づいて選択した前記ビット列のうち反転させるビットを示す信号を、前記第１のビット数のビット演算回路の各々に出力する選択回路部と、
前記選択回路部に対する前記第１のビット数の変更、および、前記第１のビット数のビット演算回路の各々に対する前記係数の第２のビット数の変更を行う設定変更部と、
を有する最適化装置。
【請求項２】
前記複数のビット演算回路の各々は、前記設定変更部による前記第２のビット数の変更に応じて、前記記憶部から読み出す係数の第２のビット数を変更する精度切替回路を有する、
請求項１記載の最適化装置。
【請求項３】
前記記憶部は、前記複数のビット演算回路の各々に設けられており、
前記精度切替回路は、前記設定変更部による前記第２のビット数の変更に応じて、前記自ビットと他ビットとに関する係数のうちの一部を、前記複数のビット演算回路のうち、前記ビット列に使用されない他のビット演算回路が有する前記記憶部から読み出す、
請求項２記載の最適化装置。
【請求項４】
前記複数のビット演算回路は、複数のグループに分けられており、
前記選択回路部は、前記設定変更部による前記第１のビット数の変更に応じて、前記複数のビット演算回路のうち、前記第１のビット数のビット演算回路を含むように、１以上のグループを組合せる規模結合回路を有する、
請求項１記載の最適化装置。
【請求項５】
前記選択回路部は、１つのグループに属する各ビット演算回路から出力された前記反転可否を示す信号に基づいて選択したビットを示す信号を、前記規模結合回路に出力するセレクタ部を、前記複数のグループの各々に対して有し、
前記規模結合回路は、前記１以上のグループの各々に対応する前記セレクタ部により選択された前記ビットを示す信号に基づいて選択した反転させる前記ビットを示す信号を、前記１以上のグループに属する各ビット演算回路に出力する、
請求項４記載の最適化装置。
【請求項６】
前記規模結合回路は、前記設定変更部による複数の前記ビット列の各々に対する前記第１のビット数の設定を受け付け、複数の前記ビット列の各々に対して、前記１以上のグループを組合せる、
請求項４記載の最適化装置。
【請求項７】
グループの複数の組合せのうち、第１の組合せによる前記イジングモデルに対する演算と、第２の組合せによる前記イジングモデルまたは他のイジングモデルに対する演算とを並列に実行させる制御部、
を更に有する請求項６記載の最適化装置。
【請求項８】
前記設定変更部は、グループの複数の組合せのうち、第１の組合せに対応する第１のビット列の前記第１のビット数と第２の組合せに対応する第２のビット列の前記第１のビット数とを、同じビット数、または、異なるビット数に設定する、
請求項６記載の最適化装置。
【請求項９】
前記設定変更部は、グループの複数の組合せのうち、第１の組合せに属するビット演算回路に対する前記第２のビット数と第２の組合せに属するビット演算回路に対する前記第２のビット数とを、同じビット数、または、異なるビット数に設定する、
請求項６記載の最適化装置。
【請求項１０】
前記選択回路部は、前記複数のビット演算回路のうち、前記第１のビット数のビット演算回路以外の他のビット演算回路により出力された反転可否を示す信号を、強制的に反転不可に設定し、前記第１のビット数のビット演算回路により出力された反転可否を示す信号および前記他のビット演算回路に対して設定した反転不可を示す信号に基づいて選択した反転させる前記ビットを示す信号を、前記第１のビット数のビット演算回路だけでなく前記他のビット演算回路にも出力する、
請求項１記載の最適化装置。
【請求項１１】
入力された問題に応じて前記第１のビット数と前記第２のビット数とを決定する演算部による、前記第１のビット数と前記第２のビット数とを示す情報の入力を受け付け、前記第１のビット数と前記第２のビット数とを前記設定変更部に入力する制御部、
を更に有する請求項１記載の最適化装置。
【請求項１２】
最適化装置の制御方法において、
前記最適化装置が有する複数のビット演算回路が、イジングモデルの状態を表すビット列のうちの何れかのビットが反転されると、前記ビット列のうちの自ビットと他ビットとの相互作用の大きさを示す係数を記憶する記憶部から読み出した、反転された前記ビットに対応する係数を用いた前記イジングモデルのエネルギー変化の計算に応じて前記自ビットの反転可否を示す信号を出力し、
前記最適化装置が有する選択回路部が、前記複数のビット演算回路のうち前記ビット列の第１のビット数のビット演算回路の各々から出力された反転可否を示す信号に基づいて選択した前記ビット列のうち反転させるビットを示す信号を、前記第１のビット数のビット演算回路の各々に出力し、
前記最適化装置が有する設定変更部が、前記選択回路部に対する前記第１のビット数の変更、および、前記第１のビット数のビット演算回路の各々に対する前記係数の第２のビット数の変更を行う、
最適化装置の制御方法。
【請求項１３】
最適化装置の制御プログラムにおいて、
前記最適化装置が有する複数のビット演算回路に、イジングモデルの状態を表すビット列のうちの何れかのビットが反転されると、前記ビット列のうちの自ビットと他ビットとの相互作用の大きさを示す係数を記憶する記憶部から読み出した、反転された前記ビットに対応する係数を用いた前記イジングモデルのエネルギー変化の計算に応じて前記自ビットの反転可否を示す信号を出力させ、
前記最適化装置が有する選択回路部に、前記複数のビット演算回路のうち前記ビット列の第１のビット数のビット演算回路の各々から出力された反転可否を示す信号に基づいて選択した前記ビット列のうち反転させるビットを示す信号を、前記第１のビット数のビット演算回路の各々に出力させ、
前記最適化装置が有する設定変更部に、前記選択回路部に対する前記第１のビット数の変更、および、前記第１のビット数のビット演算回路の各々に対する前記係数の第２のビット数の変更を行わせる、
最適化装置の制御プログラム。
【請求項１４】
解くべき問題と動作条件とを入力する入力部と、
入力した前記問題をイジングモデルの基底状態の探索問題に変換するとともに、前記探索問題の規模を示す規模情報と、前記探索問題の表現の精度を表す精度情報と、前記探索問題のエネルギーの初期値を表すエネルギー情報と、規模および精度に応じた規模精度モード情報とを生成する変換部と、
前記規模情報と、前記精度情報と、前記エネルギー情報を入力するとともに前記動作条件と前記規模精度モード情報とを入力し、基底状態の探索を行う演算を実行して解を出力する制御部と、
前記制御部による基底状態の探索の結果として得られた解を表示する表示部と、
を有する最適化装置。
【請求項１５】
前記変換部は、前記基底状態の探索の結果として得られた解を、可視化した表示情報に変換し、
前記表示部は、前記可視化した表示情報を表示する請求項１４の最適化装置。
【請求項１６】
前記規模情報は、規模の基準となる規模基準値に対する規模比により表され、
前記精度情報は、精度の基準となる精度基準値に対する精度比により表される、
請求項１４又は１５に記載の最適化装置。
【請求項１７】
最適化装置の制御方法において、
前記最適化装置が有する入力部が、解くべき問題と動作条件とを入力し、
前記最適化装置が有する変換部が、入力した前記問題をイジングモデルの基底状態の探索問題に変換するとともに、前記探索問題の規模を示す規模情報と、前記探索問題の表現の精度を表す精度情報と、前記探索問題のエネルギーの初期値を表すエネルギー情報と、規模および精度に応じた規模精度モード情報とを生成し、
前記最適化装置が有する制御部が、前記規模情報と、前記精度情報と、前記エネルギー情報を入力するとともに前記動作条件と前記規模精度モード情報とを入力し、基底状態の探索を行う演算を実行して解を出力し、
前記最適化装置が有する表示部が、前記制御部による基底状態の探索の結果として得られた解を表示する、
最適化装置の制御方法。
【請求項１８】
最適化装置の制御プログラムにおいて、
前記最適化装置が有する入力部から、解くべき問題と動作条件とを入力させ、
前記最適化装置が有する変換部に、入力した前記問題をイジングモデルの基底状態の探索問題に変換させるとともに、前記探索問題の規模を示す規模情報と、前記探索問題の表現の精度を表す精度情報と、前記探索問題のエネルギーの初期値を表すエネルギー情報と、規模および精度に応じた規模精度モード情報とを生成させ、
前記最適化装置が有する制御部に、前記規模情報と、前記精度情報と、前記エネルギー情報を入力するとともに前記動作条件と前記規模精度モード情報とを入力し、基底状態の探索を行う演算を実行して解を出力させ、
前記最適化装置が有する表示部に、前記制御部による基底状態の探索の結果として得られた解を表示させる、
最適化装置の制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は最適化装置、最適化装置の制御方法および最適化装置の制御プログラムに関する。
【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする多変数の最適化問題を解く方法として、イジング型のエネルギー関数を用いた最適化装置（イジングマシンまたはボルツマンマシンと呼ばれる場合もある）がある。最適化装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。【０００３】
最適化装置は、例えば、ニューラルネットワークを用いてモデル化することもできる。その場合、イジングモデルに含まれる複数のスピンに対応した複数のビット（スピンビット）のそれぞれが、他のビットと自身のビットとの相互作用の大きさを示す重み係数（結合係数とも呼ばれる）とに応じて０または１を出力するニューロンとして機能する。最適化装置は、例えば、シミュレーテッド・アニーリングなどの確率的探索法により、上記のようなエネルギー関数（コスト関数、目的関数とも呼ばれる）の値（エネルギーと言う）の最小値が得られる各ビットの値の組合せを、解として求める。【０００４】
例えば、スピンに対応する単位素子を複数搭載する半導体チップを用いてイジングモデルの基底状態を探索する半導体システムの提案がある。提案の半導体システムでは、大規模な問題に対応可能な半導体チップを実現するに際しては、ある程度の数の単位素子が搭載された半導体チップを複数使用して構築する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第２０１７／０３７９０３号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
最適化装置では、解くべき問題に応じて、利用されるスピンビット数（問題の規模に相当）や重み係数のビット数（問題における条件表現の精度に相当）が変わり得る。例えば、ある分野の問題では、スピンビット数が比較的多く用いられ、重み係数のビット数が比較的少なくてよいことがある。一方、他の分野の問題では、スピンビット数が比較的少なくてよいが、重み係数のビット数が比較的多く用いられることがある。しかし、各問題に適合したスピンビット数と重み係数のビット数とを備えた最適化装置を、問題毎に個別に製造するのは非効率である。【０００７】
１つの側面では、本発明は、規模と精度とを可変にできる最適化装置、最適化装置の制御方法および最適化装置の制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの態様では、最適化装置が提供される。最適化装置は、記憶部と複数のビット演算回路と選択回路部と設定変更部とを有する。記憶部は、イジングモデルの状態を表すビット列のうちのビット間の相互作用の大きさを示す係数を記憶する。複数のビット演算回路の各々は、ビット列のうちの何れかのビットが反転されると、記憶部から読み出した反転されたビットと自ビットとに対応する係数を用いたイジングモデルのエネルギー変化の計算に応じて、自ビットの反転可否を示す信号を出力する。選択回路部は、複数のビット演算回路のうちビット列の第１のビット数のビット演算回路の各々から出力された反転可否を示す信号に基づいて選択したビット列のうち反転させるビットを示す信号を、第１のビット数のビット演算回路の各々に出力する。設定変更部は、選択回路部に対する第１のビット数の変更、および、第１のビット数のビット演算回路の各々に対する係数の第２のビット数の変更を行う。【０００９】
また、１つの態様では、最適化装置が提供される。最適化装置は、入力部と変換部と制御部と表示部とを有する。入力部は、解くべき問題と動作条件とを入力する。変換部は、入力した問題をイジングモデルの基底状態の探索問題に変換するとともに、探索問題の規模を示す規模情報と、探索問題の表現の精度を表す精度情報と、探索問題のエネルギーの初期値を表すエネルギー情報と、規模および精度に応じた規模精度モード情報とを生成する。制御部は、規模情報と、精度情報と、エネルギー情報を入力するとともに動作条件と規模精度モード情報とを入力し、基底状態の探索を行う演算を実行して解を出力する。表示部は、制御部による基底状態の探索の結果として得られた解を表示する。【００１０】
また、１つの態様では、最適化装置の制御方法が提供される。
また、１つの態様では、最適化装置の制御プログラムが提供される。
【発明の効果】
【００１１】
１つの側面では、規模と精度とを可変にできる。
本発明の上記および他の目的、特徴および利点は本発明の例として好ましい実施の形態を表す添付の図面と関連した以下の説明により明らかになるであろう。
【図面の簡単な説明】
【００１２】
【図１】第１の実施の形態の最適化装置を示す図である。
【図２】第２の実施の形態の情報処理システムの例を示す図である。
【図３】情報処理装置のハードウェア例を示すブロック図である。
【図４】情報処理システムにおけるハードウェアの関係の例を示す図である。
【図５】制御部のハードウェア例を示すブロック図である。
【図６】組合せ最適化問題の例を示す図である。
【図７】最少エネルギーとなるバイナリ値の探索例を示す図である。
【図８】最適化装置の回路構成例を示す図である。
【図９】ランダムセレクタ部の回路構成例を示す図である。
【図１０】規模と精度とのトレードオフ関係の例を示す図である。
【図１１】重み係数の格納例（その１）を示す図である。
【図１２】重み係数の格納例（その２）を示す図である。
【図１３】重み係数の格納例（その３）を示す図である。
【図１４】重み係数の格納例（その４）を示す図である。
【図１５】初期化処理の例を示すフローチャートである。
【図１６】演算処理の例を示すフローチャートである。
【図１７】結合係数の格納例（その５）を示す図である。
【図１８】第３の実施の形態の最適化装置の例を示す図である。
【図１９】ＬＦＢの回路構成例を示す図である。
【図２０】規模結合回路の回路構成例を示す図である。
【図２１】問題毎の規模／精度の必要範囲の例を示す図である。
【図２２】規模精度の選択可能範囲の例を示す図である。
【図２３】ＬＦＥの使用パターンの例を示す図である。
【図２４】最適化装置の利用フローの例を示す図である。
【発明を実施するための形態】
【００１３】
以下、本実施の形態について図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。
【００１４】
図１は、第１の実施の形態の最適化装置を示す図である。
最適化装置１は、計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応する複数のビット（スピンビット）のそれぞれの値の組合せ（状態）のうち、エネルギー関数が最小値となるときの各ビットの値（基底状態）を探索する。
【００１５】
イジング型のエネルギー関数Ｅ（ｘ）は、例えば、以下の式（１）で定義される。
【００１６】
【数１】
2020054061.tif 000003
【００１７】
右辺第１項は、イジングモデルに含まれる全ビットから選択可能な２つのビットの全組合せについて、漏れと重複なく、２つのビットの値（０または１）と結合係数との積を積算したものである。イジングモデルに含まれる全ビット数をＫ個（Ｋは２以上の整数）とする。また、ｉ，ｊの各々を、０以上Ｋ−１以下の整数とする。ｘｉは、ｉ番目のビットの値を表す変数（状態変数とも呼ばれる）である。ｘｊは、ｊ番目のビットの値を表す変数である。Ｗｉｊは、ｉ番目とｊ番目のビットの相互作用の大きさを示す重み係数である。なお、Ｗｉｉ＝０である。また、Ｗｉｊ＝Ｗｊｉであることが多い（すなわち、重み係数による係数行列は対称行列である場合が多い）。
【００１８】
右辺第２項は、全ビットのそれぞれのバイアス係数とビットの値との積の総和を求めたものである。ｂｉは、ｉ番目のビットのバイアス係数を示している。
また、変数ｘｉの値が変化して１−ｘｉとなると、変数ｘｉの増加分は、Δｘｉ＝（１−ｘｉ）−ｘｉ＝１−２ｘｉと表せる。したがって、スピン反転（値の変化）に伴うエネルギー変化ΔＥｉは、以下の式（２）で表される。
【００１９】
【数２】
2020054061.tif 000004
【００２０】
ｈｉはローカルフィールド（局所場）と呼ばれ、式（３）で表される。
【００２１】
【数３】
2020054061.tif 000005
【００２２】
Δｘｉに応じてローカルフィールドｈｉに符号（＋１または−１）を乗じたものがエネルギー変化ΔＥｉとなる。ローカルフィールドｈｉの変化分Δｈｉは式（４）で表される。
【００２３】
【数４】
2020054061.tif 000006
【００２４】
ある変数ｘｊが変化したときのローカルフィールドｈｉを更新する処理は並列に行われる。
最適化装置１は、例えば、１チップの半導体集積回路であり、ＦＰＧＡ（Field Programmable Gate Array）などを用いて実現される。最適化装置１は、ビット演算回路１ａ１，…，１ａＫ，…，１ａＮ（複数のビット演算回路）、選択回路部２、閾値生成部３、乱数生成部４、設定変更部５および制御部６を有する。ここで、Ｎは、最適化装置１が備えるビット演算回路の総数である。Ｎは、Ｋ以上の整数である。ビット演算回路１ａ１，…，１ａＫ，…，１ａＮの各々には、識別情報（ｉｎｄｅｘ＝０，…，Ｋ−１，…，Ｎ−１）が対応付けられている。
【００２５】
ビット演算回路１ａ１，…，１ａＫ，…，１ａＮは、イジングモデルの状態を表すビット列に含まれる１ビットを提供する単位素子である。当該ビット列は、スピンビット列や状態ベクトルなどと呼ばれてもよい。ビット演算回路１ａ１，…，１ａＫ，…，１ａＮの各々は、自ビットと他ビットの間の重み係数を記憶し、重み係数に基づいて他ビットの反転に応じた自ビットの反転可否を判定し、自ビットの反転可否を示す信号を選択回路部２に出力する。
【００２６】
選択回路部２は、スピンビット列のうち、反転させるビット（反転ビット）を選択する。具体的には、選択回路部２は、ビット演算回路１ａ１，…，１ａＫ，…，１ａＮのうち、イジングモデルの基底状態の探索に用いられているビット演算回路１ａ１，…，１ａＫの各々から出力された反転可否の信号を受け付ける。選択回路部２は、ビット演算回路１ａ１，…，１ａＫのうち、反転可の信号を出力したビット演算回路に対応するビットを優先的に１つ選択し、反転ビットとする。例えば、選択回路部２は、乱数生成部４により出力される乱数ビットに基づいて当該反転ビットの選択を行う。選択回路部２は、選択した反転ビットを示す信号を、ビット演算回路１ａ１，…，１ａＫに出力する。反転ビットを示す信号は、反転ビットの識別情報（ｉｎｄｅｘ＝ｊ）と、反転可否を示すフラグ（ｆｌｇｊ＝１）と、反転ビットの現在の値ｑｊ（今回の反転前の値）とを示す信号を含む。ただし、何れのビットも反転されないこともある。何れのビットも反転されない場合、選択回路部２は、ｆｌｇｊ＝０を出力する。
【００２７】
閾値生成部３は、ビット演算回路１ａ１，…，１ａＫ，…，１ａＮの各々に対し、ビットの反転可否を判定する際に用いられる閾値を生成する。ビット演算回路１ａ１，…，１ａＫ，…，１ａＮの各々に当該閾値を示す信号を出力する。後述するように、閾値生成部３は、閾値の生成に、温度を示すパラメータ（温度パラメータ）Ｔと乱数とを用いる。閾値生成部３は、当該乱数を発生させる乱数発生器を有する。閾値生成部３は、ビット演算回路１ａ１，…，１ａＫ，…，１ａＮの各々に対して個別に乱数発生器を有し、個別に閾値の生成と供給とを行うことが好ましい。ただし、閾値生成部３は、所定数のビット演算回路で乱数発生器を共用してもよい。
【００２８】
乱数生成部４は、乱数ビットを生成し、選択回路部２に出力する。乱数生成部４により生成された乱数ビットは、選択回路部２による反転ビットの選択に用いられる。
設定変更部５は、ビット演算回路１ａ１，…，１ａＫ，…，１ａＮのうち、計算対象のイジングモデルの状態を表すビット列（スピンビット列）の第１のビット数（スピンビット数）の変更を行う。また、設定変更部５は、第１のビット数のビット演算回路の各々に対する、重み係数の第２のビット数の変更を行う。
【００２９】
制御部６は、温度パラメータＴやビット演算回路１ａ１，…，１ａＮの各々の記憶部に対する重み係数の設定を行い、ビット演算回路１ａ１，…，１ａＮによる演算の開始や終了を制御する。制御部６は、演算結果の出力を行う。例えば、制御部６は、ビット演算回路１ａ１，…，１ａＫを用いた演算が終了すると、ビット演算回路１ａ１，…，１ａＫに保持されるスピンビット列を読み出して出力する。
【００３０】
次に、ビット演算回路の回路構成を説明する。ビット演算回路１ａ１（ｉｎｄｅｘ＝０）を主に説明するが、他のビット演算回路も同様の回路構成で実現される（例えば、Ｘ番目（Ｘは１以上Ｎ以下の整数）のビット演算回路に対して、ｉｎｄｅｘ＝Ｘ−１とすればよい）。
【００３１】
ビット演算回路１ａ１は、記憶部１１、精度切替回路１２、反転判定部１３、ビット保持部１４、エネルギー変化計算部１５および状態遷移判定部１６を有する。
記憶部１１は、例えば、レジスタやＳＲＡＭ（Static Random Access Memory）などである。記憶部１１は、スピンビット列のうちのビット間の相互作用の大きさを示す係数を記憶する。より具体的には、記憶部１１は、自ビット（ここでは、ｉｎｄｅｘ＝０のビット）と他ビットとの間の重み係数を記憶する。ここで、スピンビット数（第１のビット数）Ｋに対して、重み係数の総数はＫ２である。記憶部１１には、ｉｎｄｅｘ＝０のビットに対して、Ｋ個の重み係数Ｗ００，Ｗ０１，…，Ｗ０，Ｋ−１が記憶される。ここで、重み係数は第２のビット数Ｌで表される。したがって、記憶部１１では重み係数を格納するために、Ｋ×Ｌビットが所要される。なお、記憶部１１は、ビット演算回路１ａ１の外部であって、最適化装置１の内部に設けられてもよい（他のビット演算回路の記憶部も同様）。
【００３２】
精度切替回路１２は、スピンビット列の何れかのビットが反転されると反転されたビットに対する重み係数を自身の（ビット演算回路１ａ１の）記憶部１１から読み出し、読み出した重み係数をエネルギー変化計算部１５に出力する。すなわち、精度切替回路１２は、選択回路部２から反転ビットの識別情報を受け付け、記憶部１１から反転ビットと自ビットとの組に対応する重み係数を読み出して、エネルギー変化計算部１５に出力する。
【００３３】
このとき、精度切替回路１２は、設定変更部５により設定された第２のビット数で表される重み係数の読み出しを行う。精度切替回路１２は、設定変更部５による第２のビット数の変更に応じて、記憶部１１から読み出す係数の第２のビット数を変更する。
【００３４】
例えば、精度切替回路１２は、記憶部１１から所定ビット数のビット列を読み出すセレクタを有する。セレクタが読み出す所定ビット数が、第２のビット数よりも大きい場合、精度切替回路１２は、当該セレクタにより反転ビットに対応する重み係数を含む単位ビット列を読み出し、読み出した単位ビット列から第２のビット数で表される重み係数を抽出する。あるいは、精度切替回路１２は、セレクタが読み出す所定ビット数が、第２のビット数よりも小さい場合、当該セレクタにより読み出された複数のビット列を結合することで、第２のビット数で表される重み係数を記憶部１１から抽出してもよい。
【００３５】
反転判定部１３は、選択回路部２により出力されたｉｎｄｅｘ＝ｊとｆｌｇｊとを示す信号を受け付け、当該信号に基づいて反転ビットとして自ビットが選択されたか否かを判定する。反転ビットとして自ビットが選択された場合（すなわち、ｉｎｄｅｘ＝ｊが自ビットを示し、ｆｌｇｊが反転可を示す場合）、反転判定部１３は、ビット保持部１４に記憶されたビットを反転させる。すなわち、ビット保持部１４に保持されたビットが０の場合、当該ビットを１に変更する。また、ビット保持部１４に保持されたビットが１の場合、当該ビットを０に変更する。
【００３６】
ビット保持部１４は、１ビットを保持するレジスタである。ビット保持部１４は、保持するビットをエネルギー変化計算部１５および選択回路部２に出力する。
エネルギー変化計算部１５は、記憶部１１から読み出した重み係数を用いたイジングモデルのエネルギー変化値ΔＥ０を計算し、状態遷移判定部１６に出力する。具体的には、エネルギー変化計算部１５は、反転ビットの値（今回の反転前の値）を選択回路部２から受け付け、反転ビットが、１から０、または、０から１のどちらに反転するかに応じて、式（４）により、Δｈ０を計算する。そして、エネルギー変化計算部１５は、前回のｈ０にΔｈ０を加算することで、ｈ０を更新する。エネルギー変化計算部１５は、ｈ０を保持するレジスタを有し、当該レジスタにより更新後のｈ０を保持する。
【００３７】
更に、エネルギー変化計算部１５は、ビット保持部１４より現在の自ビットを受け付け、自ビットが０であれば０から１へ、自ビットが１であれば１から０へ、反転する場合のイジングモデルのエネルギー変化値ΔＥ０を式（２）により計算する。エネルギー変化計算部１５は、計算したエネルギー変化値ΔＥ０を、状態遷移判定部１６に出力する。
【００３８】
状態遷移判定部１６は、エネルギー変化計算部１５によるエネルギー変化の計算に応じて、自ビットの反転可否を示す信号ｆｌｇ０を選択回路部２に出力する。具体的には、状態遷移判定部１６は、エネルギー変化計算部１５により計算されたエネルギー変化値ΔＥ０を受け付け、閾値生成部３により生成された閾値との比較に応じて、自ビットの反転可否を判定する比較器である。ここで、状態遷移判定部１６による判定について説明する。
【００３９】
シミュレーテッド・アニーリングでは、あるエネルギー変化ΔＥを引き起こす状態遷移の許容確率ｐ（ΔＥ，Ｔ）を以下の式（５）のように決めれば、時刻（反復回数）無限大の極限で状態が最適解（基底状態）に到達することが知られている。
【００４０】
【数５】
2020054061.tif 000007
【００４１】
式（５）においてＴは、前述の温度パラメータＴである。ここで、関数ｆとして、式（６）（メトロポリス法）、または、式（７）（ギブス法）が用いられる。
【００４２】
【数６】
2020054061.tif 000008
【００４３】
【数７】
2020054061.tif 000009
【００４４】
温度パラメータＴは、例えば、式（８）で表される。すなわち、温度パラメータＴは、反復回数ｔに対して対数的に減少する関数で与えられる。例えば、定数ｃは問題に応じて決定される。
【００４５】
【数８】
2020054061.tif 000010
【００４６】
ここで、Ｔ０は、初期温度値であり問題に応じて十分に大きくとることが望ましい。
式（５）で表される許容確率ｐ（ΔＥ，Ｔ）を用いた場合、ある温度における状態遷移の十分な反復後に定常状態に達したとすると、当該状態はボルツマン分布に従って生成される。すなわち、各状態の占有確率は熱力学における熱平衡状態に対するボルツマン分布に従う。よって、ある温度でボルツマン分布に従った状態を生成し、その後、当該温度よりも低い温度でボルツマン分布に従った状態を生成し、というように徐々に温度を下げていくことで、各温度におけるボルツマン分布に従った状態を追えることになる。そして、温度０としたときに、温度０でのボルツマン分布により最低エネルギーの状態（基底状態）が高確率で実現される。この様子が材料を焼き鈍したときの状態変化とよく似ているため、この方法はシミュレーテッド・アニーリングと呼ばれる。このとき、エネルギーが上がる状態遷移が確率的に起こることは、物理学における熱励起に相当する。
【００４７】
例えば、許容確率ｐ（ΔＥ，Ｔ）でエネルギー変化ΔＥを引き起こす状態遷移を許容することを示すフラグ（ｆｌｇ＝１）を出力する回路は、ｆ（−ΔＥ／Ｔ）と、区間［０，１）の値をとる一様乱数ｕとの比較に応じた値を出力する比較器により実現できる。
【００４８】
ただし、次のような変形を行っても同じ機能を実現可能である。２つの数に同じ単調増加関数を作用させても大小関係は変化しない。したがって、比較器の２つの入力に同じ単調増加関数を作用させても比較器の出力は変わらない。例えば、ｆ（−ΔＥ／Ｔ）に作用させる単調増加関数としてｆ（−ΔＥ／Ｔ）の逆関数ｆ−１（−ΔＥ／Ｔ）、一様乱数ｕに作用させる単調増加関数としてｆ−１（−ΔＥ／Ｔ）の−ΔＥ／Ｔをｕとしたｆ−１（ｕ）を用いることができる。その場合、上記の比較器と同様の機能を有する回路は、−ΔＥ／Ｔがｆ−１（ｕ）より大きいとき１を出力する回路でよい。更に、温度パラメータＴが正であることから、状態遷移判定部１６は、−ΔＥがＴ・ｆ−１（ｕ）より大きいとき（あるいは、ΔＥが−（Ｔ・ｆ−１（ｕ））より小さいとき）、ｆｌｇ０＝１を出力する回路でよい。
【００４９】
閾値生成部３は、一様乱数ｕを生成し、上記のｆ−１（ｕ）の値に変換する変換テーブルを用いて、ｆ−１（ｕ）の値を出力する。メトロポリス法が適用される場合、ｆ−１（ｕ）は、式（９）で与えられる。また、ギブス法が適用される場合、ｆ−１（ｕ）は、式（１０）で与えられる。
【００５０】
【数９】
2020054061.tif 000011
【００５１】
【数１０】
2020054061.tif 000012
【００５２】
変換テーブルは、例えば、閾値生成部３に接続されたＲＡＭ（Random Access Memory）、フラッシュメモリなどのメモリ（図示を省略している）に記憶される。閾値生成部３は、温度パラメータＴと、ｆ−１（ｕ）との積（Ｔ・ｆ−１（ｕ））を閾値として出力する。ここで、Ｔ・ｆ−１（ｕ）は、熱励起エネルギーに相当する。
【００５３】
なお、選択回路部２から状態遷移判定部１６に対してｆｌｇｊを入力し、当該ｆｌｇｊが状態遷移を許容しないことを示すとき（つまり状態遷移が生じないとき）、状態遷移判定部１６により−ΔＥ０にオフセット値を加算してから、閾値との比較を行ってもよい。また、状態遷移判定部１６は、状態遷移が生じないことが継続する場合に、加算するオフセット値を増加させてもよい。一方、状態遷移判定部１６は、ｆｌｇｊが、状態遷移を許容することを示すとき（つまり状態遷移が生じるとき）には、オフセット値を０にする。−ΔＥ０へのオフセット値の加算やオフセット値の増加により、状態遷移が許容されやすくなり、現在の状態が局所解にある場合、その局所解からの脱出が促進される。
【００５４】
こうして、温度パラメータＴが徐々に小さく設定され、例えば、温度パラメータＴの値を所定回数、小さくした場合（または、温度パラメータＴが最小値に達した場合）のスピンビット列が、ビット演算回路１ａ１，…，１ａＫに保持される。最適化装置１は、温度パラメータＴの値を所定回数、小さくした場合（または、温度パラメータＴが最小値に達した場合）のスピンビット列を解として出力する。
【００５５】
最適化装置１では、前述の設定変更部５により、イジングモデルのスピンビット数（第１のビット数）と、ビット間の重み係数のビット数（第２のビット数）とを変更可能である。ここで、スピンビット数は、イジングモデルを実現する回路の規模（問題の規模）に相当する。規模が大きいほど、多数の組合せ候補をもつ組合せ最適化問題に最適化装置１を適用できる。また、重み係数のビット数は、ビット間の相互関係の表現の精度（問題における条件表現の精度）に相当する。精度が高いほど、スピン反転時のエネルギー変化ΔＥに対する条件を詳細に設定できる。ある問題では、スピンビット数が大きく、重み係数を表すビット数が小さいことがある。あるいは、別の問題では、スピンビット数が小さく、重み係数を表すビット数が大きいこともある。一方、問題に応じて、各問題に適合した最適化装置を個別に製造することは非効率である。
【００５６】
そこで、最適化装置１では、設定変更部５によりイジングモデルの状態を表すスピンビット数と重み係数のビット数との設定を可能とすることで、規模と精度とを可変にできる。その結果、１つの最適化装置１において、問題に合った規模および精度を実現できる。
【００５７】
より具体的には、ビット演算回路１ａ１，…，１ａＫ，…，１ａＮの各々は、精度切替回路を有し、当該精度切替回路によって、設定変更部５の設定に応じて、自身の記憶部から読み出す重み係数のビット長を切り替える。また、選択回路部２は、設定変更部５により設定されたスピンビット数に相当する数（例えば、Ｋ個）のビット演算回路に対して、反転ビットを示す信号を入力し、当該数（Ｋ個）のビット演算回路に対応するビットの中から反転ビットを選択する。これにより、問題に応じた規模および精度を備えた最適化装置を個別に製造しなくても、１つの最適化装置１によって、問題に応じた規模および精度でイジングモデルを実現できる。
【００５８】
ここで、前述のように、ビット演算回路１ａ１，…，１ａＮの各々が備える記憶部は、ＳＲＡＭなどの比較的小容量の記憶デバイスにより実現される。このため、スピンビット数が増えると、重み係数のビット数によっては、記憶部の容量が不足することも考えられる。一方、最適化装置１によれば、設定変更部５により、記憶部の容量の制限を満たすように、規模および精度を設定することも可能になる。具体的には、設定変更部５は、スピンビット数が増えるほど、重み係数のビット数を減らすように設定することが考えられる。また、設定変更部５は、重み係数のビット数が増えるほど、スピンビット数を減らすように設定することも考えられる。
【００５９】
また、上記の例では、Ｎ個のビット演算回路のうちのＫ個を、イジングモデルに使用するものとした。最適化装置１は、残りのＮ−Ｋ個のビット演算回路を不使用としてもよい。その場合、選択回路部２は、残りのＮ−Ｋ個のビット演算回路により出力されるフラグｆｌｇを全て、強制的に０に設定し、残りのＮ−Ｋ個のビット演算回路に対応するビットが反転候補として選択されないようにしてもよい。
【００６０】
あるいは、最適化装置１は、Ｎ−Ｋ≧Ｋの場合、残りのＮ−Ｋ個のビット演算回路のうちのＫ個のビット演算回路により、前述のイジングモデルと同じイジングモデルを実現し、両イジングモデルにより同一問題処理の並列度を高めて計算を高速化してもよい。
【００６１】
更に、最適化装置１は、残りのＮ−Ｋ個のビット演算回路のうちの一部を用いて、他の問題に対応する他のイジングモデルを実現し、前述のイジングモデルで表される問題と並列に、当該他の問題の演算を行ってもよい。
【００６２】
以下では、最適化装置１を用いる情報処理システムを例示し、最適化装置１の機能を更に詳細に説明する。
［第２の実施の形態］
次に、第２の実施の形態を説明する。
【００６３】
図２は、第２の実施の形態の情報処理システムの例を示す図である。
第２の実施の形態の情報処理システムは、情報処理装置２０とクライアント３０とを有する。情報処理装置２０およびクライアント３０は、ネットワーク４０に接続されている。ネットワーク４０は、例えば、ＬＡＮ（Local Area Network）でもよいし、ＷＡＮ（Wide Area Network）やインターネットなどでもよい。
【００６４】
情報処理装置２０は、組合せ最適化問題をイジングモデルに置き換え、イジングモデルの基底状態の探索により、組合せ最適化問題を高速に解く機能を提供する。
クライアント３０は、ユーザにより使用されるクライアントコンピュータであり、ユーザが解くべき問題の、情報処理装置２０への入力に用いられる。
【００６５】
図３は、情報処理装置のハードウェア例を示すブロック図である。
情報処理装置２０は、ＣＰＵ（Central Processing Unit）２１、ＤＲＡＭ（Dynamic Random Access Memory）２２、記憶装置２３、ＮＩＣ（Network Interface Card）２４、最適化装置２５および媒体リーダ２８を有する。
【００６６】
ＣＰＵ２１、ＤＲＡＭ２２、記憶装置２３、ＮＩＣ２４、最適化装置２５および媒体リーダ２８は、情報処理装置２０のバス２９に接続されている。バス２９は、例えば、ＰＣＩｅ（Peripheral Component Interconnect Express）バスである。
【００６７】
ＣＰＵ２１は、ＤＲＡＭ２２に格納されたプログラムの命令を実行するプロセッサである。ＣＰＵ２１は、記憶装置２３に記憶されたプログラムやデータの少なくとも一部をＤＲＡＭ２２にロードし、プログラムを実行する。ＣＰＵ２１は、当該プログラムを実行することで発揮される機能により、最適化装置２５に対する設定や動作の制御を行う。
【００６８】
ＤＲＡＭ２２は、情報処理装置２０の主記憶装置であり、ＣＰＵ２１により実行されるプログラムや最適化装置２５に設定されるデータなどを一時的に記憶する。
記憶装置２３は、情報処理装置２０の補助記憶装置であり、ＣＰＵ２１により実行されるプログラムや最適化装置２５に設定されるデータなどを記憶する。記憶装置２３は、例えば、ＳＳＤ（Solid State Drive）やＨＤＤ（Hard Disk Drive）などである。
【００６９】
ＮＩＣ２４は、ネットワーク４０に接続され、ネットワーク４０を介してクライアント３０と通信する通信インタフェースである。ＮＩＣ２４は、例えば、ネットワーク４０に属するスイッチやルータなどの通信装置とケーブルで接続される。
【００７０】
最適化装置２５は、ＣＰＵ２１の制御により、イジングモデルの基底状態を探索する。最適化装置２５は、例えば、１チップの半導体集積回路であり、ＦＰＧＡなどにより実現される。最適化装置２５は、第１の実施の形態の最適化装置１の一例である。
【００７１】
媒体リーダ２８は、記録媒体４１に記録されたプログラムやデータを読み取る読み取り装置である。記録媒体４１として、例えば、磁気ディスク、光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。磁気ディスクには、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤが含まれる。光ディスクには、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）が含まれる。
【００７２】
媒体リーダ２８は、例えば、記録媒体４１から読み取ったプログラムやデータを、ＤＲＡＭ２２や記憶装置２３などの他の記録媒体にコピーする。読み取られたプログラムは、例えば、ＣＰＵ２１によって実行される。なお、記録媒体４１は可搬型記録媒体であってもよく、プログラムやデータの配布に用いられることがある。また、記録媒体４１や記憶装置２３を、コンピュータ読み取り可能な記録媒体と言うことがある。
【００７３】
なお、クライアント３０はＣＰＵ、主記憶装置、補助記憶装置、ＮＩＣ、マウスやキーボードなどの入力デバイスおよびディスプレイを有する。
図４は、情報処理システムにおけるハードウェアの関係の例を示す図である。
【００７４】
クライアント３０は、ユーザプログラム３１を実行する。ユーザプログラム３１は、情報処理装置２０への各種データ（例えば、解くべき問題の内容や最適化装置２５の利用スケジュールなどの動作条件）の入力、および、最適化装置２５による演算結果の表示などを行う。クライアント３０と、ＮＩＣ２４とにより、情報処理装置２０への各種データを入力する入力部および基底状態探索の結果として得られた解を、そのまま通知したり、或いは、ユーザに分かり易い結果情報（例えば、結果をグラフとして可視化した表示画面の情報）として表示する表示部が実現される。
【００７５】
ＣＰＵ２１は、ライブラリ２１ａおよびドライバ２１ｂを実行するプロセッサ（演算部）である。ライブラリ２１ａのプログラム、および、ドライバ２１ｂのプログラムは、記憶装置２３に格納されており、ＣＰＵ２１による実行時にＤＲＡＭ２２にロードされる。
【００７６】
ライブラリ２１ａは、ユーザプログラム３１により入力された各種データを受け付け、ユーザが解くべき問題を、イジングモデルの最低エネルギー状態を探索する問題に変換する。ライブラリ２１ａは、変換後の問題に関する情報（例えば、スピンビット数、重み係数を表すビット数、重み係数の値、温度パラメータの初期値など）を、ドライバ２１ｂに提供する。また、ライブラリ２１ａは、最適化装置２５による解の探索結果をドライバ２１ｂから取得し、当該探索結果をユーザに分かり易い結果情報に変換して、ユーザプログラム３１に提供する。
【００７７】
ドライバ２１ｂは、ライブラリ２１ａから提供された情報を最適化装置２５に供給する。また、ドライバ２１ｂは、イジングモデルによる解の探索結果を最適化装置２５から取得し、ライブラリ２１ａに提供する。
【００７８】
最適化装置２５は、ハードウェアとして、制御部２５ａおよびＬＦＢ（Local Field Block）５０を有する。
制御部２５ａは、ドライバ２１ｂから受け付けたＬＦＢ５０の動作条件を記憶するＲＡＭを有し、当該動作条件に基づいてＬＦＢ５０による演算を制御する。また、制御部２５ａは、ＬＦＢ５０が備える各種のレジスタへの初期値の設定、ＳＲＡＭへの重み係数の格納、および、演算終了後のスピンビット列（探索結果）の読み出しなどを行う。制御部２５ａは、例えば、ＦＰＧＡにおける回路などによって実現される。
【００７９】
ＬＦＢ５０は、複数のＬＦＥ（Local Field Element）を有する。ＬＦＥは、スピンビットに対応する単位素子である。１つのＬＦＥは、１つのスピンビットに対応する。後述するように、最適化装置２５は、複数のＬＦＢを有してもよい。
【００８０】
図５は、制御部のハードウェア例を示すブロック図である。
制御部２５ａは、ＣＰＵ入出力部２５ａ１、制御レジスタ２５ａ２、ＬＦＢ送信部２５ａ３およびＬＦＢ受信部２５ａ４を有する。
【００８１】
ＣＰＵ入出力部２５ａ１は、ＣＰＵ２１から受け付けたデータを、制御レジスタ２５ａ２またはＬＦＢ５０に入力する。例えば、ＣＰＵ入出力部２５ａ１は、ＣＰＵ２１により入力された規模や精度や各パラメータの初期値や結合定数などの設定データやＬＦＢ５０の動作条件のデータを、制御レジスタ２５ａ２を介してＬＦＢ５０に入力することもできるし、ＬＦＢ５０内の各レジスタやＲＡＭに入力することもできる。
【００８２】
制御レジスタ２５ａ２は、ＣＰＵ入出力部２５ａ１によるＬＦＢ５０に対する各種の設定データを保持し、ＬＦＢ送信部２５ａ３に出力する。また、制御レジスタ２５ａ２は、ＬＦＢ受信部２５ａ４によりＬＦＢ５０から受信されたデータを保持し、ＣＰＵ入出力部２５ａ１に出力する。
【００８３】
ＬＦＢ送信部２５ａ３は、制御レジスタ２５ａ２に保持された設定データを、ＬＦＢ５０に送信する。
ＬＦＢ受信部２５ａ４は、ＬＦＢ５０からデータ（演算結果などのデータ）を受信し、制御レジスタ２５ａ２に格納する。
【００８４】
図６は、組合せ最適化問題の例を示す図である。
組合せ最適化問題の一例として、巡回セールスマン問題を考える。ここでは、簡単のため、Ａ都市，Ｂ都市，Ｃ都市，Ｄ都市，Ｅ都市の５つの都市を、最少コスト（距離や料金など）で回る経路を求めるとする。グラフ２０１は、都市をノード、都市間の移動をエッジとした１つの経路を示す。この経路は、例えば、行を回る順番、列を都市に対応付けた行列２０２で表される。行列２０２は、行の小さい順に、ビット「１」が設定された都市を回ることを示す。更に、行列２０２は、スピンビット列に相当するバイナリ値２０３に変換できる。行列２０２の例では、バイナリ値２０３は、５×５＝２５ビットとなる。バイナリ値２０３（スピンビット列）のビット数は、巡回対象の都市が増すほど増加する。すなわち、組合せ最適化問題の規模が大きくなれば、より多くのスピンビットが所要され、スピンビット列のビット数（規模）が大きくなる。
【００８５】
次に、最少エネルギーとなるバイナリ値の探索例を説明する。
図７は、最少エネルギーとなるバイナリ値の探索例を示す図である。
まず、バイナリ値２２１のうちの１ビットを反転させる前（スピン反転前）のエネルギーをＥｉｎｉｔとする。
【００８６】
最適化装置２５は、バイナリ値２２１の任意の１ビットを反転させたときのエネルギー変化量ΔＥを計算する。グラフ２１１は、横軸をバイナリ値、縦軸をエネルギーとして、エネルギー関数に応じた１ビット反転に対するエネルギー変化を例示している。最適化装置２５は、式（２）によりΔＥを求める。
【００８７】
最適化装置２５は、上記の計算を、バイナリ値２２１の全ビットに適用し、各々のビットの反転に対して、エネルギー変化量ΔＥを計算する。例えば、バイナリ値２２１のビット数がＮのとき、反転パターン２２２はＮ個になる。グラフ２１２は、反転パターン毎のエネルギー変化の様子を例示する。
【００８８】
最適化装置２５は、反転パターン毎のΔＥに基づいて、反転条件（閾値とΔＥとの所定の判定条件）を満たした反転パターン２２２のうちからランダムで１つを選択する。最適化装置２５は、選択された反転パターンに対応するΔＥを、スピン反転前のＥｉｎｉｔに加減算し、スピン反転後のエネルギー値Ｅを計算する。最適化装置は、求めたエネルギー値ＥをＥｉｎｉｔとし、スピン反転後のバイナリ値２２３を用いて、上記の手順を繰り返し行う。
【００８９】
ここで、前述のように、式（２），（３）で用いられるＷの１要素は、ビット間の相互作用の大きさを示すスピン反転の重み係数である。重み係数を表すビット数を精度と呼ぶ。精度が高いほど、スピン反転時のエネルギー変化量ΔＥに対する条件を詳細に設定できる。例えば、Ｗの総サイズは、スピンビット列に含まれる２つのビットの全結合に対して「精度×スピンビット数×スピンビット数」である。一例として、スピンビット数が８ｋ（＝８１９２）の場合、Ｗの総サイズは、「精度×８ｋ×８ｋ」ビットとなる。
【００９０】
次に、図７で例示した探索を行う最適化装置２５の回路構成を説明する。
図８は、最適化装置の回路構成例を示す図である。
最適化装置２５（あるいは、最適化装置２５のＬＦＢ５０）は、ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎ、ランダムセレクタ部５２、閾値生成部５３、乱数生成部５４、モード設定レジスタ５５、加算器５６およびＥ格納レジスタ５７を有する。
【００９１】
ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎの各々は、スピンビットの１ビットとして用いられる。ｎは、２以上の整数であり、ＬＦＢ５０が備えるＬＦＥの数を示す。ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎの各々には、ＬＦＥの識別情報（ｉｎｄｅｘ）が対応付けられている。ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎの各々に対して、ｉｎｄｅｘ＝０，１，…，ｎ−１である。ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎは、第１の実施の形態のビット演算回路１ａ１，…，１ａＮの一例である。
【００９２】
以下では、ＬＦＥ５１ａ１の回路構成を説明する。ＬＦＥ５１ａ２，…，５１ａｎも、ＬＦＥ５１ａ１と同様の回路構成により実現される。ＬＦＥ５１ａ２，…，５１ａｎの回路構成の説明については、以下の説明における各要素の符号の末尾の「ａ１」の部分を、「ａ２」，…，「ａｎ」の各々に置換して（例えば、「６０ａ１」の符号を「６０ａｎ」のように置換して）読み替えればよい。また、ｈ，ｑ，ΔＥ，Ｗなどの各値の添え字についても、「ａ２」，…，「ａｎ」の各々に対応する添え字に置換して読み替えればよい。
【００９３】
ＬＦＥ５１ａ１は、ＳＲＡＭ６０ａ１、精度切替回路６１ａ１、Δｈ生成部６２ａ１、加算器６３ａ１、ｈ格納レジスタ６４ａ１、反転判定部６５ａ１、ビット格納レジスタ６６ａ１、ΔＥ生成部６７ａ１、判定部６８ａ１を有する。
【００９４】
ＳＲＡＭ６０ａ１は、重み係数Ｗを格納する。ＳＲＡＭ６０ａ１は、第１の実施の形態の記憶部１１に対応する。ＳＲＡＭ６０ａ１には、全スピンビットの重み係数Ｗのうち、ＬＦＥ５１ａ１で使用される分だけ格納される。このため、スピンビット数をＫ（Ｋは２以上ｎ以下の整数）とすると、ＳＲＡＭ６０ａ１に格納される全重み係数のサイズは、「精度×Ｋ」ビットとなる。図８では、一例として、スピンビット数Ｋ＝ｎの場合を例示している。この場合、ＳＲＡＭ６０ａ１には、重み係数Ｗ００，Ｗ０１，…，Ｗ０，ｎ−１が格納される。
【００９５】
精度切替回路６１ａ１は、反転ビットの識別情報であるｉｎｄｅｘと反転可を示すフラグＦとをランダムセレクタ部５２から取得し、反転ビットに対応する重み係数をＳＲＡＭ６０ａ１から抽出する。精度切替回路６１ａ１は、抽出した重み係数を、Δｈ生成部６２ａ１に出力する。例えば、精度切替回路６１ａ１は、ランダムセレクタ部５２によりＳＲＡＭ６０ａ１に格納されたｉｎｄｅｘとフラグＦとを、ＳＲＡＭ６０ａ１から取得してもよい。あるいは、精度切替回路６１ａ１は、ランダムセレクタ部５２からｉｎｄｅｘとフラグＦとの供給を受ける信号線を有してもよい（図示を省略している）。
【００９６】
ここで、精度切替回路６１ａ１は、モード設定レジスタ５５に設定された重み係数のビット数（精度）の設定を受け付け、当該設定に応じて、ＳＲＡＭ６０ａ１から読み出す重み係数のビット数を切り替える。
【００９７】
具体的には、精度切替回路６１ａ１は、ＳＲＡＭ６０ａ１から所定の単位ビット数のビット列（単位ビット列）を読み出すセレクタを有する。精度切替回路６１ａ１は、当該セレクタにより反転ビットに対応する重み係数を含むビット数ｒの単位ビット列を読み出す。例えば、当該セレクタが読み出す単位ビット数ｒが、重み係数のビット数ｚよりも大きい場合、精度切替回路１２は、読み出したビット列に対して、反転ビットに対応する重み係数を示すビット部分をＬＳＢ（Least Significant Bit）側にシフトさせ、それ以外のビット部分に０を代入することで、重み係数の読み出しを行う。あるいは、単位ビット数ｒが、モード設定レジスタ５５により設定されたビット数ｚより小さい場合も考えられる。この場合、精度切替回路６１ａ１は、当該セレクタにより読み出された複数の単位ビット列を結合することで、設定されたビット数ｚでの重み係数を抽出してもよい。
【００９８】
なお、精度切替回路６１ａ１は、ＬＦＥ５１ａ２が備えるＳＲＡＭ６０ａ２にも接続される。後述するように、精度切替回路６１ａ１は、ＳＲＡＭ６０ａ２から重み係数を読み出すことも可能である。
【００９９】
Δｈ生成部６２ａ１は、ランダムセレクタ部５２から反転ビットの現在のビット値（今回の反転前のビット値）を受け付け、精度切替回路６１ａ１から取得した重み係数を用いて、式（４）により、ローカルフィールドｈ０の変化量Δｈ０を計算する。Δｈ生成部６２ａ１は、Δｈ０を加算器６３ａ１に出力する。
【０１００】
加算器６３ａ１は、ｈ格納レジスタ６４ａ１に格納されたローカルフィールドｈ０にΔｈ０を加算し、ｈ格納レジスタ６４ａ１に出力する。
ｈ格納レジスタ６４ａ１は、図示しないクロック信号に同期して、加算器６３ａ１が出力する値（ローカルフィールドｈ０）を取り込む。ｈ格納レジスタ６４ａ１は、例えば、フリップフロップである。なお、ｈ格納レジスタ６４ａ１に格納されるローカルフィールドｈ０の初期値は、バイアス係数ｂ０である。当該初期値は、制御部２５ａにより設定される。
【０１０１】
反転判定部６５ａ１は、反転ビットのｉｎｄｅｘ＝ｊと、反転可否を示すフラグＦｊとをランダムセレクタ部５２から受け付け、自ビットが反転ビットとして選択されたか否かを判定する。自ビットが反転ビットとして選択された場合、反転判定部６５ａ１は、ビット格納レジスタ６６ａ１に格納されたスピンビットを反転させる。
【０１０２】
ビット格納レジスタ６６ａ１は、ＬＦＥ５１ａ１に対応するスピンビットを保持する。ビット格納レジスタ６６ａ１は、例えば、フリップフロップである。ビット格納レジスタ６６ａ１に格納されたスピンビットは、反転判定部６５ａ１により反転される。ビット格納レジスタ６６ａ１は、ΔＥ生成部６７ａ１およびランダムセレクタ部５２にスピンビットを出力する。
【０１０３】
ΔＥ生成部６７ａ１は、ｈ格納レジスタ６４ａ１のローカルフィールドｈ０およびビット格納レジスタ６６ａ１のスピンビットに基づいて、自ビットの反転に応じたイジングモデルのエネルギー変化量ΔＥ０を、式（２）により計算する。ΔＥ生成部６７ａ１は、エネルギー変化量ΔＥ０を、判定部６８ａ１およびランダムセレクタ部５２に出力する。
【０１０４】
判定部６８ａ１は、ΔＥ生成部６７ａ１により出力されたエネルギー変化量ΔＥ０と、閾値生成部５３により生成された閾値との比較により、自ビットの反転を許容するか否かを示す（自ビットの反転可否を示す）フラグＦ０を、ランダムセレクタ部５２に出力する。具体的には、判定部６８ａ１は、ΔＥ０が閾値−（Ｔ・ｆ−１（ｕ））より小さいときＦ０＝１（反転可）を出力し、ΔＥ０が閾値−（Ｔ・ｆ−１（ｕ））以上のときＦ０＝０（反転不可）を出力する。ここで、ｆ−１（ｕ）は、適用法則に応じて、式（９），（１０）の何れかで与えられる関数である。また、ｕは、区間［０，１）の一様乱数である。
【０１０５】
ランダムセレクタ部５２は、ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎの各々から、エネルギー変化量、スピンビットの反転可否を示すフラグおよびスピンビットを受け付け、反転可であるスピンビットのうち反転させるビット（反転ビット）を選択する。
【０１０６】
ランダムセレクタ部５２は、選択した反転ビットの現在のビット値（ビットｑｊ）を、ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎが備えるΔｈ生成部６２ａ１，６２ａ２，…，６２ａｎに供給する。ランダムセレクタ部５２は、第１の実施の形態の選択回路部２の一例である。
【０１０７】
ランダムセレクタ部５２は、反転ビットのｉｎｄｅｘ＝ｊと、反転可否を示すフラグＦｊとを、ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎが備えるＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｎに出力する。なお、ランダムセレクタ部５２は、前述のように、反転ビットのｉｎｄｅｘ＝ｊと、反転可否を示すフラグＦｊとを、ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎが備える精度切替回路６１ａ１，６１ａ２，…，６１ａｎに出力してもよい。
【０１０８】
また、ランダムセレクタ部５２は、反転ビットのｉｎｄｅｘ＝ｊと、反転可否を示すフラグＦｊとを、ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎが備える反転判定部６５ａ１，６５ａ２，…，６５ａｎに供給する。
【０１０９】
更に、ランダムセレクタ部５２は、選択した反転ビットに対応するΔＥｊを、加算器５６に供給する。
ここで、ランダムセレクタ部５２は、あるイジングモデルにおけるスピンビット数（すなわち、使用するＬＦＥの数）の設定を、モード設定レジスタ５５から受け付ける。例えば、ランダムセレクタ部５２は、ｉｎｄｅｘの小さい方から順に、設定されたスピンビット数に相当する数のＬＦＥを使用して、解の探索が行われるようにする。例えば、ランダムセレクタ部５２は、ｎ個のＬＦＥのうち、Ｋ個のＬＦＥを用いる場合、ＬＦＥ５１ａ１，…，ＬＦＥ５１ａＫのＬＦＥに対応するスピンビット列から反転ビットを選択する。このとき、ランダムセレクタ部５２は、例えば、使用しないｎ−Ｋ個のＬＦＥ５１ａ（Ｋ−１），…，５１ａｎの各々から出力されるフラグＦを、強制的に０に設定することが考えられる。
【０１１０】
閾値生成部５３は、ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎが備える判定部６８ａ１，６８ａ２，…，６８ａｎに対して、エネルギー変化量ΔＥとの比較に用いられる閾値を生成し、供給する。前述のように、閾値生成部５３は、温度パラメータＴと、区間［０，１）の一様乱数ｕと、式（９）または式（１０）で示されるｆ−１（ｕ）とを用いて、閾値を生成する。閾値生成部５３は、例えば、ＬＦＥ毎に個別に、乱数発生器を有し、ＬＦＥ毎の乱数ｕを用いて閾値を生成する。ただし、幾つかのＬＦＥで乱数発生器が共有されてもよい。温度パラメータＴの初期値やシミュレーテッド・アニーリングにおける温度パラメータＴの減少サイクルや減少量などは、制御部２５ａによって制御される。
【０１１１】
乱数生成部５４は、ランダムセレクタ部５２における反転ビットの選択に用いられる乱数ビットを生成し、ランダムセレクタ部５２に供給する。
モード設定レジスタ５５は、ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎが備える精度切替回路６１ａ１，６１ａ２，６１ａｎに対して、重み係数のビット数（すなわち、精度）を示す信号を供給する。また、モード設定レジスタ５５は、ランダムセレクタ部５２に対して、スピンビット数（すなわち、規模）を示す信号を供給する。モード設定レジスタ５５に対するスピンビット数や重み係数のビット数の設定は、制御部２５ａにより行われる。モード設定レジスタ５５は、第１の実施の形態の設定変更部５の一例である。
【０１１２】
加算器５６は、ランダムセレクタ部５２により出力されたエネルギー変化量ΔＥｊを、Ｅ格納レジスタ５７に格納されたエネルギー値Ｅに加算し、Ｅ格納レジスタ５７に出力する。
【０１１３】
Ｅ格納レジスタ５７は、図示しないクロック信号に同期して、加算器５６が出力するエネルギー値Ｅを取り込む。Ｅ格納レジスタ５７は、例えば、フリップフロップである。なお、エネルギー値Ｅの初期値は、制御部２５ａによって式（１）を用いて計算され、Ｅ格納レジスタ５７に設定される。
【０１１４】
例えば、解の探索にＫ個のＬＦＥが用いられる場合、制御部２５ａはビット格納レジスタ６６ａ１，…，６６ａＫの各スピンビットを読み出すことで、スピンビット列を得る。
図９は、ランダムセレクタ部の回路構成例を示す図である。
【０１１５】
ランダムセレクタ部５２は、フラグ制御部５２ａと複数段にわたってツリー状に接続された複数の選択回路とを有する。
フラグ制御部５２ａは、モード設定レジスタ５５のスピンビット数の設定に応じて、初段の選択回路５２ａ１，５２ａ２，５２ａ３，５２ａ４，…，５２ａｑの各々に入力されるフラグの値を制御する。図９では、選択回路５２ａｑの１つの入力（ＬＦＥ５１ａｎの出力に相当）に対するフラグの値を制御する部分回路５２ｘｎが例示されている。部分回路５２ｘｎのフラグ設定部５２ｙｎは、使用しないＬＦＥ５１ａｎから出力されるフラグＦｎを強制的に０に設定するスイッチである。
【０１１６】
初段の選択回路５２ａ１，５２ａ２，５２ａ３，５２ａ４，…，５２ａｑの各々には、ＬＦＥ５１ａ１，５１ａ２，…，５１ａｎのそれぞれが出力する変数ｑｉとＦｉとΔＥｉの組が２組ずつ入力される。例えば、選択回路５２ａ１には、ＬＦＥ５１ａ１が出力する変数ｑ０とＦ０とΔＥ０による組と、ＬＦＥ５１ａ２が出力する変数ｑ１とＦ１とΔＥ１による組とが入力される。また、選択回路５２ａ２には、変数ｑ２とＦ２とΔＥ２による組と変数ｑ３とＦ３とΔＥ３による組が入力され、選択回路５２ａ３には、変数ｑ４とＦ４とΔＥ４による組と変数ｑ５とＦ５とΔＥ５による組が入力される。更に、選択回路５２ａ４には、変数ｑ６とＦ６とΔＥ６による組と変数ｑ７とＦ７とΔＥ７による組が入力され、選択回路５２ａｑには、変数ｑｎ−２とＦｎ−２とΔＥｎ−２による組と変数ｑｎ−１とＦｎ−１とΔＥｎ−１による組が入力される。
【０１１７】
そして、選択回路５２ａ１，…，５２ａｑの各々は、入力された２組の変数ｑｉとＦｉとΔＥｉと、乱数生成部５４が出力する１ビット乱数に基づいて、一方の組の変数ｑｉとＦｉとΔＥｉを選択する。このとき、選択回路５２ａ１，…，５２ａｑの各々は、Ｆｉが１である組を優先的に選択し、両方の組が１の場合には１ビット乱数に基づいて何れか一方の組を選択する（他の選択回路も同様）。ここで、乱数生成部５４は、１ビット乱数を選択回路毎に個別に生成し、各選択回路に供給する。また、選択回路５２ａ１，…，５２ａｑの各々は、どちらの組の変数ｑｉとＦｉとΔＥｉを選択したかを示す１ビットの識別値を生成し、選択した変数ｑｉとＦｉとΔＥｉと識別値とを含む信号（状態信号と言う）を出力する。なお、初段の選択回路５２ａ１〜５２ａｑの数は、ＬＦＥ５１ａ１，…，５１ａｎの数の１／２、つまり、ｎ／２である。
【０１１８】
２段目の選択回路５２ｂ１，５２ｂ２，…，５２ｂｒの各々には、選択回路５２ａ１，…，５２ａｑが出力する状態信号が２つずつ入力される。例えば、選択回路５２ｂ１には、選択回路５２ａ１，５２ａ２が出力する状態信号が入力され、選択回路５２ｂ２には、選択回路５２ａ３，５２ａ４が出力する状態信号が入力される。
【０１１９】
そして、選択回路５２ｂ１，…，５２ｂｒの各々は、２つの状態信号と、乱数生成部５４が出力する１ビット乱数に基づいて、２つの状態信号の何れか一方を選択する。また、選択回路５２ｂ１，…，５２ｂｒのそれぞれは、選択した状態信号に含まれる識別値について何れの状態信号を選択したかを示すように１ビットを付加して更新し、選択した状態信号を出力する。
【０１２０】
３段目以降の選択回路においても同様の処理が行われ、各段の選択回路で１ビットずつ識別値のビット幅が増えていき、最後段の選択回路５２ｐから、ランダムセレクタ部５２の出力である状態信号が出力される。ランダムセレクタ部５２が出力する状態信号に含まれる識別値が、２進数で表された、反転ビットを示すｉｎｄｅｘである。
【０１２１】
ただし、ランダムセレクタ部５２は、各ＬＦＥからフラグＦとともに当該ＬＦＥに対応するｉｎｄｅｘを受け付け、変数ｑｉとＦｉとΔＥｉと同様に、各選択回路によりｉｎｄｅｘの選択を行うことで、反転ビットに対応するｉｎｄｅｘを出力してもよい。この場合、各ＬＦＥは、ｉｎｄｅｘ格納用のレジスタを有し、当該レジスタからランダムセレクタ部５２へｉｎｄｅｘを出力する。
【０１２２】
このように、ランダムセレクタ部５２は、ＬＦＥ５１ａ１，…，５１ａｎのうち、設定されたスピンビット数ＫのＬＦＥ５１ａ１，…，５１ａＫ以外の他のＬＦＥ５１ａ（Ｋ＋１），…，５１ａｎにより出力された反転可否を示す信号を強制的に反転不可に設定する。ランダムセレクタ部５２は、ＬＦＥ５１ａ１，…，５１ａＫにより出力された反転可否を示す信号およびＬＦＥ５１ａ（Ｋ＋１），…，５１ａｎに対して設定した反転不可を示す信号に基づいて、反転ビットを選択する。ランダムセレクタ部５２は、反転ビットを示す信号を、ＬＦＥ５１ａ１，…，５１ａＫに加えてＬＦＥ５１ａ（Ｋ＋１），…，５１ａｎにも出力する。
【０１２３】
こうして、フラグ制御部５２ａの制御により、使用されないＬＦＥのフラグＦが強制的に０に設定されるので、スピンビット列に使用されないＬＦＥに対応するビットを反転候補から除外できる。
【０１２４】
次に、ＬＦＥ５１ａ１，…，５１ａｎの各々のＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｎに対する重み係数の格納例を説明する。まず、ＳＲＡＭ容量に対する規模と精度とのトレードオフ関係について説明する。
【０１２５】
図１０は、規模と精度とのトレードオフ関係の例を示す図である。
前述したように、組合せ最適化問題の一例として、巡回セールスマン問題が挙げられる。巡回セールスマン問題は、巡回する都市数が多く、巡回条件（移動時間、移動距離、移動費等）が少なければ、低精度の問題となり、巡回条件が多い場合は高精度が必要となる。他にも、比較的低精度となる最適化問題として、エイトクイーン問題や四色問題といった、条件がある程度定まっている問題が挙げられる。一方、ポートフォリオ最適化問題は、金額や期間など条件が多くあるため、高精度が求められる。
【０１２６】
ＬＦＥ毎のＳＲＡＭの容量に制限があると、規模と精度とにトレードオフ関係が生ずる。グラフ３００は、ＬＦＥ毎のＳＲＡＭにおいて重み係数の格納のための容量の上限が１２８ｋ（キロ）ビットである場合の規模と精度とのトレードオフ関係を示している。ここで、１ｋ（キロ）＝１０２４とする。グラフ３００の横軸は規模（ｋビット）であり、縦軸は精度（ビット）である。なお、一例として、ｎ＝８１９２であるとする。
【０１２７】
この場合、規模１ｋビットに対して、精度は最大１２８ビットである。また、規模２ｋビットに対して、精度は最大６４ビットである。規模４ｋビットに対して、精度は最大３２ビットである。規模８ｋビットに対して、精度は最大１６ビットである。
【０１２８】
そこで、最適化装置２５では、例えば、次の４つのモードを利用可能にする。第１のモードは、規模１ｋビット／精度１２８ビットのモードである。第２のモードは、規模２ｋビット／精度６４ビットのモードである。第３のモードは、規模４ｋビット／精度３２ビットのモードである。第４のモードは、規模８ｋビット／精度１６ビットのモードである。次に、これら４種のモードの各々に応じた重み係数の格納例を説明する。重み係数は、制御部２５ａにより、ＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｎの各々に格納される。なお、精度切替回路６１ａ１，６１ａ２，…，６１ａｎの各々のセレクタによりＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｎから読み出される単位ビット数は、一例として、１２８ビットであるとする。
【０１２９】
図１１は、重み係数の格納例（その１）を示す図である。
前述の第１のモード（規模１ｋビット／精度１２８ビット）を用いる場合、重み係数Ｗは式（１１）で表される。
【０１３０】
【数１１】
2020054061.tif 000013
【０１３１】
データ１ｄ１，１ｄ２，…，１ｄｓは、前述の第１のモード（規模１ｋビット／精度１２８ビット）を用いる場合のＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｓに対する重み係数の格納例を示す。ここで、ｓ＝１０２４である。データ１ｄ１，１ｄ２，…，１ｄｓは、各々、ＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｓに格納される。このモードでは、ＬＦＥは１ｋ個（＝１０２４個）使用される。なお、図中、ＬＦＥ５１ａ１，…，５１ａｓを、各々の識別番号を用いて、ＬＦＥ０，…，ＬＦＥ１０２３のように表記することがある（以降の図も同様）。
【０１３２】
データ１ｄ１は、ＬＦＥ５１ａ１（ＬＦＥ０）のＳＲＡＭ６０ａ１に格納されるＷ０，０〜Ｗ０，１０２３を示す。データ１ｄ２は、ＬＦＥ５１ａ２（ＬＦＥ１）のＳＲＡＭ６０ａ２に格納されるＷ１，０〜Ｗ１，１０２３を示す。データ１ｄｓは、ＬＦＥ５１ａｓ（ＬＦＥ１０２３）のＳＲＡＭ６０ａｓに格納されるＷ１０２３，０〜Ｗ１０２３，１０２３を示す。１つの重み係数Ｗｉｊのビット数は１２８ビットである。
【０１３３】
図１２は、重み係数の格納例（その２）を示す図である。
前述の第２のモード（規模２ｋビット／精度６４ビット）を用いる場合、重み係数Ｗは式（１２）で表される。
【０１３４】
【数１２】
2020054061.tif 000014
【０１３５】
データ２ｄ１，２ｄ２，…，２ｄｔは、前述の第２のモード（規模２ｋビット／精度６４ビット）を用いる場合のＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｔに対する重み係数の格納例を示す。ここで、ｔ＝２０４８である。データ２ｄ１，２ｄ２，…，２ｄｔは、各々、ＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｔに格納される。このモードでは、ＬＦＥは２ｋ個（＝２０４８個）使用される。
【０１３６】
データ２ｄ１は、ＬＦＥ５１ａ１（ＬＦＥ０）のＳＲＡＭ６０ａ１に格納されるＷ０，０〜Ｗ０，２０４７を示す。データ２ｄ２は、ＬＦＥ５１ａ２（ＬＦＥ１）のＳＲＡＭ６０ａ２に格納されるＷ１，０〜Ｗ１，２０４７を示す。データ２ｄｔは、ＬＦＥ５１ａｔ（ＬＦＥ２０４７）のＳＲＡＭ６０ａｔに格納されるＷ２０４７，０〜Ｗ２０４７，２０４７を示す。１つの重み係数Ｗｉｊのビット数は６４ビットである。
【０１３７】
図１３は、重み係数の格納例（その３）を示す図である。
前述の第３のモード（規模４ｋビット／精度３２ビット）を用いる場合、重み係数Ｗは式（１３）で表される。
【０１３８】
【数１３】
2020054061.tif 000015
【０１３９】
データ３ｄ１，３ｄ２，…，３ｄｕは、前述の第３のモード（規模４ｋビット／精度３２ビット）を用いる場合のＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｕに対する重み係数の格納例を示す。ここで、ｕ＝４０９６である。データ３ｄ１，３ｄ２，…，３ｄｕは、各々、ＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｕに格納される。このモードでは、ＬＦＥは４ｋ個（＝４０９６個）使用される。
【０１４０】
データ３ｄ１は、ＬＦＥ５１ａ１（ＬＦＥ０）のＳＲＡＭ６０ａ１に格納されるＷ０，０〜Ｗ０，４０９５を示す。データ３ｄ２は、ＬＦＥ５１ａ２（ＬＦＥ１）のＳＲＡＭ６０ａ２に格納されるＷ１，０〜Ｗ１，４０９５を示す。データ３ｄｕは、ＬＦＥ５１ａｕ（ＬＦＥ４０９５）のＳＲＡＭ６０ａｕに格納されるＷ４０９５，０〜Ｗ４０９５，４０９５を示す。１つの重み係数Ｗｉｊのビット数は３２ビットである。
【０１４１】
図１４は、重み係数の格納例（その４）を示す図である。
前述の第４のモード（規模８ｋビット／精度１６ビット）を用いる場合、重み係数Ｗは式（１４）で表される。
【０１４２】
【数１４】
2020054061.tif 000016
【０１４３】
データ４ｄ１，４ｄ２，…，４ｄｎは、前述の第４のモード（規模８ｋビット／精度１６ビット）を用いる場合のＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｎに対する重み係数の格納例を示す。ここで、ｎ＝８１９２である。データ４ｄ１，４ｄ２，…，４ｄｎは、各々、ＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｎに格納される。このモードでは、ＬＦＥは８ｋ個（＝８１９２個）使用される。
【０１４４】
データ４ｄ１は、ＬＦＥ５１ａ１（ＬＦＥ０）のＳＲＡＭ６０ａ１に格納されるＷ０，０〜Ｗ０，８１９１を示す。データ４ｄ２は、ＬＦＥ５１ａ２（ＬＦＥ１）のＳＲＡＭ６０ａ２に格納されるＷ１，０〜Ｗ１，８１９１を示す。データ４ｄｎは、ＬＦＥ５１ａｎ（ＬＦＥ８１９１）のＳＲＡＭ６０ａｎに格納されるＷ８１９１，０〜Ｗ８１９１，８１９１を示す。１つの重み係数Ｗｉｊのビット数は１６ビットである。
【０１４５】
次に、最適化装置２５の処理手順を説明する。まず、最適化装置２５の初期化処理の例を説明する。
図１５は、初期化処理の例を示すフローチャートである。
【０１４６】
（Ｓ１０）ＣＰＵ２１は、問題に応じた初期値および動作条件を最適化装置２５に入力する。初期値は、例えば、エネルギー値Ｅ、ローカルフィールドｈｉ、スピンビットｑｉ、温度パラメータＴの初期値および重み係数Ｗなどを含む。また、動作条件は、１つの温度パラメータでの状態の更新回数Ｎ１、温度パラメータの変更回数Ｎ２および温度パラメータの下げ幅などを含む。制御部２５ａは、入力された初期値および重み係数を、前述の各ＬＦＥのレジスタおよびＳＲＡＭに設定する。なお、制御部２５ａは、使用されないＬＦＥがある場合、当該ＬＦＥのＳＲＡＭに、Ｗとして、例えば全て０を設定する。スピンビット間の重み係数Ｗは、問題に応じた精度に対応するビット数で表される。
【０１４７】
（Ｓ１１）ＣＰＵ２１は、問題に応じたスピンビット数（規模）および重み係数のビット数（精度）を、最適化装置２５に入力する。制御部２５ａは、ＣＰＵ２１からスピンビット数および重み係数のビット数を受け付け、モード設定レジスタ５５に入力する。モード設定レジスタ５５に入力された重み係数のビット数は、各ＬＦＥの精度切替回路に入力される。また、モード設定レジスタ５５に入力されたスピンビット数は、ランダムセレクタ部５２に入力される。
【０１４８】
（Ｓ１２）ＣＰＵ２１は、最適化装置２５に演算開始フラグ（例えば、演算開始フラグ＝１）を入力する。制御部２５ａは、演算開始フラグの入力を受け付け、ＬＦＢ５０による演算を開始する。こうして、初期化処理が終了する。
【０１４９】
図１６は、演算処理の例を示すフローチャートである。
ここで、図１６の説明では、ｉｎｄｅｘ＝ｉに対応するＬＦＥをＬＦＥ５１ａｘ（１番目のＬＦＥはＬＦＥ５１ａ１であり、ｎ番目のＬＦＥは５１ａｎである）と表記する。ＬＦＥ５１ａｘに含まれる各部についても、例えば、ＳＲＡＭ６０ａｘのように、符号の末尾に「ｘ」を付して表記する。ＬＦＥ５１ａ１，…，ＬＦＥ５１ａｎの各々による演算は並列に実行される。
【０１５０】
（Ｓ２０）ΔＥ生成部６７ａｘは、ｈ格納レジスタ６４ａｘに格納されたローカルフィールドｈｉおよびビット格納レジスタ６６ａｘに格納されたビットｑｉに基づいて、当該ビットｑｉを反転させた場合のエネルギー変化量ΔＥｉを生成する。ΔＥｉの生成には、式（２）が用いられる。
【０１５１】
（Ｓ２１）判定部６８ａｘは、ΔＥ生成部６７ａｘにより生成されたエネルギー変化量ΔＥｉと、閾値生成部５３により生成された閾値（＝−（Ｔ・ｆ−１（ｕ）））とを比較し、閾値＞ΔＥｉであるか否かを判定する。閾値＞ΔＥｉの場合、ステップＳ２２に処理が進む。閾値≦ΔＥｉの場合、ステップＳ２３に処理が進む。
【０１５２】
（Ｓ２２）判定部６８ａｘは、反転候補信号（Ｆｉ＝１）をランダムセレクタ部５２に出力する。そして、ステップＳ２４に処理が進む。
（Ｓ２３）判定部６８ａｘは、非反転信号（Ｆｉ＝０）をランダムセレクタ部５２に出力する。そして、ステップＳ２４に処理が進む。
【０１５３】
（Ｓ２４）ランダムセレクタ部５２は、ＬＦＥ５１ａ１，…，ＬＦＥ５１ａｎの各々から出力された全反転候補（Ｆｉ＝１であるＬＦＥに対応するビット）から、反転ビットを１つ選択する。ランダムセレクタ部５２は、選択した反転ビットに対応するｉｎｄｅｘ＝ｊ、Ｆｊ、ｑｊをＬＦＥ５１ａ１，…，ＬＦＥ５１ａｎに出力する。また、ランダムセレクタ部５２は、選択した反転ビットに対応するΔＥｊを、加算器５６に出力する。すると、次のステップＳ２５（エネルギー更新処理），Ｓ２６（状態更新処理）が並列に開始される。
【０１５４】
（Ｓ２５）加算器５６は、反転ビットに対応するエネルギー変化量ΔＥを、エネルギー値Ｅに加算することで、Ｅ格納レジスタ５７に格納されたエネルギー値Ｅを更新する。すなわち、Ｅ＝Ｅ＋ΔＥである。そして、エネルギー更新処理が終了する。
【０１５５】
（Ｓ２６）精度切替回路６１ａｘは、反転ビットに対応するｉｎｄｅｘ＝ｊとフラグＦｊとを取得し、当該反転ビットに対応する重み係数を含む単位ビット列をＳＲＡＭ６０ａｘから読み出す。単位ビット列とは、精度切替回路６１ａｘのセレクタが、ＳＲＡＭ６０ａｘから一度に読み出すビット列の単位である。単位ビット列のビット数（単位ビット数）は、一例では、１２８ビットである（他の値でもよい）。この場合、ステップＳ２６ではＳＲＡＭ６０ａｘから１２８ビットの単位ビット列が読み出される。
【０１５６】
例えば、精度として、１２８／ａ（ａ＝１，２，４，８）ビットが選択されている場合、精度切替回路６１ａｘは、ＳＲＡＭ６０ａｘの先頭（先頭を０番目とする）の単位ビット列から数えて「Ｉｎｔｅｇｅｒ（ｊ／ａ）」番目の単位ビット列を読み出す。ここで、Ｉｎｔｅｇｅｒ（ｊ／ａ）は、（ｊ／ａ）の値から整数部を抽出する関数である。
【０１５７】
（Ｓ２７）精度切替回路６１ａｘは、ステップＳ２６で読み出された単位ビット列から、モード設定レジスタ５５により設定されたモード選択に応じたビット数の重み係数（反転ビットｑｊに対応する重み係数）Ｗｉｊを抽出する。例えば、精度切替回路６１ａｘは、１２８ビットの単位ビット列からｚビットのビット列を抽出する場合、前述のように反転ビットに対応するｚビットのビット範囲をＬＳＢ側へシフトし、それ以外の上位ビットに０を設定することで、ｚビットの重み係数を抽出する。
【０１５８】
なお、精度切替回路６１ａｘは、ステップＳ２６で読み出した単位ビット列を、先頭から精度に応じたビット長の区画に分けたときに、反転ビットに対応するビット範囲が先頭（０番目）から何番目の区画に対応するかにより当該ビット範囲を特定する。
【０１５９】
図１２〜図１４の例によれば、精度６４ビットの場合、ｊが偶数のときに０番目の区画、ｊが奇数のときに１番目の区画である。また、精度３２ビットの場合、ｍｏｄ（ｊ，４）番目＝０のときに０番目の区画、ｍｏｄ（ｊ，４）＝１のときに１番目の区画、ｍｏｄ（ｊ，４）＝２のときに２番目の区画、ｍｏｄ（ｊ，４）＝３のときに３番目の区画である。ここで、ｍｏｄ（ｕ，ｖ）は、ｕをｖで除したときの剰余を示す関数である。更に、精度１６ビットの場合も同様に、読み出した１２８ビットの単位ビット列の先頭から「ｍｏｄ（ｊ，８）」番目の区画が、反転ビットに対応するビット範囲となる。なお、精度１２８ビットの場合、精度切替回路６１ａｘは、ステップＳ２６で読み出された１２８ビットの単位ビット列を、そのまま反転ビットに対応する重み係数とする。
【０１６０】
上記の例では、１２８／ａ（ａ＝１，２，４，８）ビットの精度に対し、ステップＳ２６で読み出された１２８ビットの単位ビット列の先頭から「ｍｏｄ（ｊ，ａ）」番目の区画（１区画のサイズは１２８／ａビット）が、反転ビットに対応する重み係数を示すビット範囲である。
【０１６１】
（Ｓ２８）Δｈ生成部６２ａｘは、反転ビットの反転方向と、精度切替回路６１ａｘにより抽出された重み係数Ｗｉｊとに基づいて、Δｈｉを生成する。Δｈｉの生成には、式（４）が用いられる。また、反転ビットの反転方向は、ランダムセレクタ部５２により出力される反転ビットｑｊ（今回の反転前のビット）により判別される。
【０１６２】
（Ｓ２９）加算器６３ａｘは、Δｈ生成部６２ａｘにより生成されたΔｈｉを、ｈ格納レジスタ６４ａｘに格納されたローカルフィールドｈｉに加算することで、ｈ格納レジスタ６４ａｘに格納されたローカルフィールドｈｉを更新する。また、反転判定部６５ａｘは、ランダムセレクタ部５２により出力されたｉｎｄｅｘ＝ｊおよびフラグＦｊに基づいて、自ビットが反転ビットとして選択されたか否かを判定する。反転判定部６５ａｘは、自ビットが反転ビットとして選択された場合、ビット格納レジスタ６６ａｘに格納されたスピンビットを反転させ、自ビットが反転ビットとして選択されなかった場合、ビット格納レジスタ６６ａｘのスピンビットを維持する。ここで、自ビットが反転ビットとして選択された場合とは、ランダムセレクタ部５２により出力された信号について、ｉｎｄｅｘ＝ｊ＝ｉ、かつ、Ｆｊ＝１の場合である。
【０１６３】
（Ｓ３０）制御部２５ａは、現在の温度パラメータＴにおいて、ＬＦＥ５１ａ１，…，ＬＦＥ５１ａｎに保持される各スピンビットの更新処理回数がＮ１に達したか（更新処理回数＝Ｎ１であるか）否かを判定する。更新処理回数がＮ１に達した場合、ステップＳ３１に処理が進む。更新処理回数がＮ１に達していない場合、制御部２５ａは、更新処理回数に１を加算して、ステップＳ２０に処理を進める。
【０１６４】
（Ｓ３１）制御部２５ａは、温度パラメータＴの変更回数がＮ２に達したか（温度変更回数＝Ｎ２であるか）否かを判定する。温度変更回数がＮ２に達した場合、ステップＳ３３に処理が進む。温度変更回数がＮ２に達していない場合、制御部２５ａは、温度変更回数に１を加算して、ステップＳ３２に処理を進める。
【０１６５】
（Ｓ３２）制御部２５ａは、温度パラメータＴを変更する。具体的には、制御部２５ａは、動作条件に応じた下げ幅で、温度パラメータＴの値を減少させる（温度を下げることに相当する）。そして、ステップＳ２０に処理が進む。
【０１６６】
（Ｓ３３）制御部２５ａは、ビット格納レジスタ６６ａｘに格納されたスピンビットを読み出し、演算結果として出力する。具体的には、制御部２５ａは、モード設定レジスタ５５により設定されたスピンビット数Ｋに対応するビット格納レジスタ６６ａ１，…，６６ａＫの各々に格納されたスピンビットを読み出し、ＣＰＵ２１に出力する。すなわち、制御部２５ａは、読み出したスピンビット列をＣＰＵ２１に供給する。そして、演算処理が終了する。
【０１６７】
なお、ステップＳ２４において、ランダムセレクタ部５２は、モード設定レジスタ５５の設定に応じて、使用されないＬＦＥにより出力されるＦの値を、強制的に０に設定することで、使用されないＬＦＥをビット反転の候補から除外することができる。
【０１６８】
最適化装置２５によれば、モード設定レジスタ５５によりイジングモデルの状態を表すスピンビット数と重み係数のビット数との設定を可能とし、１チップの最適化装置２５において、問題に合った規模および精度を実現できる。
【０１６９】
より具体的には、精度切替回路６１ａｘは、モード設定レジスタ５５の設定に応じて、ＳＲＡＭ６０ａｘから読み出す重み係数のビット長を切り替える。精度切替回路６１ａｘを用いることで、ステップＳ２７で示したように、精度切替回路６１ａｘのセレクタがＳＲＡＭ６０ａｘから読み出す単位ビット数を変更せずに、種々の精度を実現できる。例えば、精度切替回路６１ａｘのセレクタによるＳＲＡＭ６０ａｘからの単位ビット数分の読み出し用の信号線の作り変えを要さずに、精度を可変にできる。
【０１７０】
また、ランダムセレクタ部５２は、モード設定レジスタ５５により設定されたスピンビット数に相当する数（例えば、Ｋ個）のＬＦＥに対して、反転ビットを示す信号を入力し、当該数（Ｋ個）のＬＦＥに対応するビットの中から反転ビットを選択する。ランダムセレクタ部５２は、使用されないｎ−Ｋ個のＬＦＥにも反転ビットを示す信号を入力するが、当該ｎ−Ｋ個のＬＦＥから出力されるフラグＦを強制的に０（反転不可）に設定することで、使用されないＬＦＥを反転ビットの選択候補から除外する。
【０１７１】
これにより、問題に応じた規模および精度を備えた最適化装置を個別に製造しなくても、１つの最適化装置２５によって、問題に応じた規模および精度でイジングモデルを実現できる。
【０１７２】
次に、モード設定の他の例を説明する。例えば、最適化装置２５は、次のようにＳＲＡＭ６０ａ１，…，６０ａｎに重み係数を格納することで、前述の４種類のモードに加え、規模４ｋビット／精度６４ビットの第５のモードを提供することもできる。
【０１７３】
図１７は、結合係数の格納例（その５）を示す図である。
データ５ｄ１，５ｄ２，…，５ｄｎは、前述の第５のモード（規模４ｋビット／精度６４ビット）を用いる場合のＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｎに対する重み係数の格納例を示す。ここで、ｎ＝８１９２である。データ５ｄ１，５ｄ２，…，５ｄｎは、各々、ＳＲＡＭ６０ａ１，６０ａ２，…，６０ａｎに格納される。このモードでは、スピンビット列として、ＬＦＥは４ｋ個（＝４０９６個）使用され、重み係数の格納のみの用途として、更に４ｋ個（＝４０９６個）のＬＦＥが使用される。
【０１７４】
データ５ｄ１は、ＬＦＥ５１ａ１（ＬＦＥ０）のＳＲＡＭ６０ａ１に格納されるＷ０，０〜Ｗ０，２０４７を示す。データ５ｄ２は、ＬＦＥ５１ａ２（ＬＦＥ１）のＳＲＡＭ６０ａ２に格納されるＷ０，２０４８〜Ｗ０，４０９５を示す。データ５ｄｎは、ＬＦＥ５１ａｎ（ＬＦＥ８１９１）のＳＲＡＭ６０ａｎに格納されるＷ４０９５，２０４８〜Ｗ４０９５，４０９５を示す。１つの重み係数Ｗｉｊのビット数は６４ビットである。
【０１７５】
ここで、前述のように、ＬＦＥ５１ａ１の精度切替回路６１ａ１は、ＬＦＥ５１ａ２のＳＲＡＭ６０ａ２からも重み係数を取得することができる。すなわち、精度切替回路６１ａ１は、例えば、隣接するＬＦＥ５１ａ２のＳＲＡＭ６０ａ２からの読み出し経路を利用することで、ＬＦＥ５１ａ２のＳＲＡＭ６０ａ２以外の機能を停止させ、ＳＲＡＭ６０ａ２の容量をＬＦＥ５１ａ１に貸し出す方法を採れる。例えば、奇数番目（先頭を１番目とする）のＬＦＥにより偶数番目のＬＦＥのＳＲＡＭを利用可能にする（あるいは、先頭を０番目とした場合は偶数番目のＬＦＥにより奇数番目のＬＦＥのＳＲＡＭを利用可能にするとも言える）。
【０１７６】
このように、精度切替回路６１ａ１，…，６１ａｎは、重み係数のビット数の変更に応じて、自ビットと他ビットとに関する重み係数のうちの一部を、スピンビットとして使用されない他のＬＦＥが有するＳＲＡＭから読み出す。この場合、ランダムセレクタ部５２は、例えば、スピンビットとして使用されない他のＬＦＥから出力されるフラグＦを強制的に０（反転不可）に設定することで、当該他のＬＦＥに対応するビットを反転ビットの選択候補から除外してもよい。
【０１７７】
これにより、規模４ｋビット／精度６４ビットの第５のモードを実現できる。同様に、規模を小さくすることで、更に大きな精度を実現することもできる。このように、最適化装置２５によれば、問題に応じて、規模および精度をより柔軟に変更することができる。
【０１７８】
［第３の実施の形態］
次に、第３の実施の形態を説明する。前述の第２の実施の形態と相違する事項を主に説明し、共通する事項の説明を省略する。
【０１７９】
第３の実施の形態では、第２の実施の形態の機能に加え、ＬＦＥを効率的に利用可能にする機能を提供する。
ここで、第３の実施の形態の情報処理システムの装置構成および情報処理装置２０のハードウェア構成は、図２，図３と同様であるため、説明を省略する。第３の実施の形態の最適化装置は、第２の実施の形態の最適化装置２５と回路構成の一部が異なる。
【０１８０】
図１８は、第３の実施の形態の最適化装置の例を示す図である。
最適化装置２６は、例えば、１チップの半導体集積回路であり、ＦＰＧＡなどにより実現される。最適化装置２６は、第１の実施の形態の最適化装置１の一例である。最適化装置２６は、複数のＬＦＢを有する。最適化装置２６は、当該複数のＬＦＢを制御する制御部２５ａを有する（図示を省略している）。
【０１８１】
第３の実施の形態では、一例として、１つのＬＦＢに属するＬＦＥの数をｍ個（ｍは２以上の整数）とし、最適化装置２６は、ＬＦＢ７０ａ，７０ｂ，７０ｃ，７０ｄ，７０ｅ，７０ｆ，７０ｇ，７０ｈを有するものとする。この場合、最適化装置２６は、合計で８ｍ個のＬＦＥを有し、最大規模８ｍビットを実現可能である。ただし、最適化装置２６が備えるＬＦＢの個数は、８個に限らず、他の個数でもよい。
【０１８２】
ＬＦＢ７０ａ，…，７０ｈが備える複数のＬＦＥは、第１の実施の形態のビット演算回路１ａ１，…，１ａＮの一例である。ＬＦＢ７０ａ，…，７０ｈの各々は、所定数（ｍ個）のＬＦＥを要素に含む、ＬＦＥの１つのグループであると言える。また、ＬＦＢ７０ａ，…，７０ｈの各々には、識別番号＃０〜＃７が割り当てられている。
【０１８３】
最適化装置２６は、更に、規模結合回路９１、モード設定レジスタ９２、加算器９３ａ，９３ｂ，９３ｃ，９３ｄ，９３ｅ，９３ｆ，９３ｇ，９３ｈおよびＥ格納レジスタ９４ａ，９４ｂ，９４ｃ，９４ｄ，９４ｅ，９４ｆ，９４ｇ，９４ｈを有する。
【０１８４】
ここで、ＬＦＢ７０ａは、ＬＦＥ７１ａ１，…，ＬＦＥ７１ａｍ、ランダムセレクタ部７２、閾値生成部７３、乱数生成部７４およびモード設定レジスタ７５を有する。ＬＦＥ７１ａ１，…，ＬＦＥ７１ａｍ、ランダムセレクタ部７２、閾値生成部７３、乱数生成部７４およびモード設定レジスタ７５は、図８で説明した第２の実施の形態の同名のハードウェアに相当するため、説明を省略する。ただし、ランダムセレクタ部７２は、選択した反転ビットに対する状態信号（フラグＦｘ０、スピンビットｑｘ０およびエネルギー変化量ΔＥｘ０）の組を、規模結合回路９１に出力する。また、ランダムセレクタ部７２は、フラグ制御部５２ａを有さなくてよい（ただし、有してもよい）。例えば、ランダムセレクタ部７２では、各ＬＦＥからの状態信号が、フラグ制御部５２ａを介さずに、ランダムセレクタ部７２の初段の各選択回路に２つずつ入力される。なお、ＬＦＢ７０ｂ，…，７０ｈも、ＬＦＢ７０ａと同様の回路構成を有する。
【０１８５】
規模結合回路９１は、ＬＦＢ７０ａ，…，７０ｈの各々から状態信号を受け付け、状態信号に基づいて反転ビットの選択を行う。規模結合回路９１は、反転ビットに関する信号を、ＬＦＢ７０ａ，…，７０ｈの各ＬＦＥに供給する。
【０１８６】
具体的には、規模結合回路９１は、フラグＦｙ０、ビットｑｙ０および反転ビットを示すｉｎｄｅｘ＝ｙ０をＬＦＢ７０ａ１のＬＦＥ７１ａ１，…，７１ａｍに出力する。ここで、以降の図では、ランダムセレクタ部７２および規模結合回路９１により出力される「ｉｎｄｅｘ＝ｘ０」などの表記を「ｘ０」のように略記することがある。規模結合回路９１は、エネルギー変化量ΔＥｙ０を加算器９３ａに出力する。
【０１８７】
また、規模結合回路９１は、フラグＦｙ１、ビットｑｙ１および反転ビットを示すｉｎｄｅｘ＝ｙ１をＬＦＢ７０ｂの各ＬＦＥに供給する。エネルギー変化量ΔＥｙ１を加算器９３ｂに出力する。
【０１８８】
規模結合回路９１は、フラグＦｙ２、ビットｑｙ２および反転ビットを示すｉｎｄｅｘ＝ｙ２をＬＦＢ７０ｃの各ＬＦＥに出力する。規模結合回路９１は、エネルギー変化量ΔＥｙ２を加算器９３ｃに出力する。
【０１８９】
規模結合回路９１は、フラグＦｙ３、ビットｑｙ３および反転ビットを示すｉｎｄｅｘ＝ｙ３をＬＦＢ７０ｄの各ＬＦＥに出力する。規模結合回路９１は、エネルギー変化量ΔＥｙ３を加算器９３ｄに出力する。
【０１９０】
規模結合回路９１は、フラグＦｙ４、ビットｑｙ４および反転ビットを示すｉｎｄｅｘ＝ｙ４をＬＦＢ７０ｅの各ＬＦＥに出力する。規模結合回路９１は、エネルギー変化量ΔＥｙ４を加算器９３ｅに出力する。
【０１９１】
規模結合回路９１は、フラグＦｙ５、ビットｑｙ５および反転ビットを示すｉｎｄｅｘ＝ｙ５をＬＦＢ７０ｆの各ＬＦＥに出力する。規模結合回路９１は、エネルギー変化量ΔＥｙ５を加算器９３ｆに出力する。
【０１９２】
規模結合回路９１は、フラグＦｙ６、ビットｑｙ６および反転ビットを示すｉｎｄｅｘ＝ｙ６をＬＦＢ７０ｇの各ＬＦＥに出力する。規模結合回路９１は、エネルギー変化量ΔＥｙ６を加算器９３ｇに出力する。
【０１９３】
規模結合回路９１は、フラグＦｙ７、ビットｑｙ７および反転ビットを示すｉｎｄｅｘ＝ｙ７をＬＦＢ７０ｈの各ＬＦＥに出力する。規模結合回路９１は、エネルギー変化量ΔＥｙ７を加算器９３ｈに出力する。
【０１９４】
ＬＦＢ７０ａ，…，７０ｈの各々が有するランダムセレクタ部（ランダムセレクタ部７２を含む）および規模結合回路９１は、第１の実施の形態の選択回路部２の一例である。
モード設定レジスタ９２は、規模結合回路９１に対する動作モードの設定を行う。モード設定レジスタ９２は、モード設定レジスタ７５によりＬＦＥ７１ａ１，…，７１ａｍおよびランダムセレクタ部７２に設定される動作モードと同じ動作モードを規模結合回路９１に設定する。モード設定レジスタ７５，９２によるモード設定の詳細は後述される。ＬＦＢ７０ａ，…，７０ｈの各々が有するモード設定レジスタ（モード設定レジスタ７５を含む）およびモード設定レジスタ９２は、第１の実施の形態の設定変更部５の一例である。
【０１９５】
加算器９３ａは、ΔＥｙ０を、Ｅ格納レジスタ９４ａに格納されているエネルギー値Ｅ０に加算することで、当該エネルギー値Ｅ０を更新する。Ｅ格納レジスタ９４ａは、例えば、クロック信号（図示を省略している）に同期して（他のＥ格納レジスタも同様）、加算器９３ａにより計算されたエネルギー値Ｅ０を取り込む。
【０１９６】
加算器９３ｂは、ΔＥｙ１を、Ｅ格納レジスタ９４ｂに格納されているエネルギー値Ｅ１に加算することで、当該エネルギー値Ｅ１を更新する。Ｅ格納レジスタ９４ｂは、加算器９３ｂにより計算されたエネルギー値Ｅ１を取り込む。
【０１９７】
加算器９３ｃは、ΔＥｙ２を、Ｅ格納レジスタ９４ｃに格納されているエネルギー値Ｅ２に加算することで、当該エネルギー値Ｅ２を更新する。Ｅ格納レジスタ９４ｃは、加算器９３ｃにより計算されたエネルギー値Ｅ２を取り込む。
【０１９８】
加算器９３ｄは、ΔＥｙ３を、Ｅ格納レジスタ９４ｄに格納されているエネルギー値Ｅ３に加算することで、当該エネルギー値Ｅ３を更新する。Ｅ格納レジスタ９４ｄは、加算器９３ｄにより計算されたエネルギー値Ｅ３を取り込む。
【０１９９】
加算器９３ｅは、ΔＥｙ４を、Ｅ格納レジスタ９４ｅに格納されているエネルギー値Ｅ４に加算することで、当該エネルギー値Ｅ４を更新する。Ｅ格納レジスタ９４ｅは、加算器９３ｅにより計算されたエネルギー値Ｅ４を取り込む。
【０２００】
加算器９３ｆは、ΔＥｙ５を、Ｅ格納レジスタ９４ｆに格納されているエネルギー値Ｅ５に加算することで、当該エネルギー値Ｅ５を更新する。Ｅ格納レジスタ９４ｆは、加算器９３ｆにより計算されたエネルギー値Ｅ５を取り込む。
【０２０１】
加算器９３ｇは、ΔＥｙ６を、Ｅ格納レジスタ９４ｇに格納されているエネルギー値Ｅ６に加算することで、当該エネルギー値Ｅ６を更新する。Ｅ格納レジスタ９４ｇは、加算器９３ｇにより計算されたエネルギー値Ｅ６を取り込む。
【０２０２】
加算器９３ｈは、ΔＥｙ７を、Ｅ格納レジスタ９４ｈに格納されているエネルギー値Ｅ７に加算することで、当該エネルギー値Ｅ７を更新する。Ｅ格納レジスタ９４ｈは、加算器９３ｈにより計算されたエネルギー値Ｅ７を取り込む。
【０２０３】
Ｅ格納レジスタ９４ａ，…，９４ｈの各々は、例えば、フリップフロップである。
次に、ＬＦＢ７０ａの回路構成例を説明する。ＬＦＢ７０ｂ，…，７０ｈもＬＦＢ７０ａと同様の回路構成である。
【０２０４】
図１９は、ＬＦＢの回路構成例を示す図である。
ＬＦＥ７１ａ１，７１ａ２，…，７１ａｍの各々は、スピンビットの１ビットとして用いられる。ｍは、２以上の整数であり、ＬＦＢ７０ａが備えるＬＦＥの数を示す。図１９では、一例として、ｍ＝１０２４としている。ただし、ｍは他の値でもよい。
【０２０５】
ＬＦＥ７１ａ１，７１ａ２，…，７１ａｍの各々には、識別情報（ｉｎｄｅｘ）が対応付けられている。ＬＦＥ７１ａ１，７１ａ２，…，７１ａｍの各々に対して、ｉｎｄｅｘ＝０，１，…，１０２３である。
【０２０６】
以下では、ＬＦＥ７１ａ１の回路構成を説明する。ＬＦＥ７１ａ２，…，７１ａｍも、ＬＦＥ７１ａ１と同様の回路構成により実現される。ＬＦＥ７１ａ２，…，７１ａｍの回路構成の説明については、以下の説明における各要素の符号の末尾の「ａ１」の部分を、「ａ２」，…，「ａｍ」の各々に置換して（例えば、「８０ａ１」の符号を「８０ａｍ」のように置換して）読み替えればよい。
【０２０７】
ＬＦＥ７１ａ１は、ＳＲＡＭ８０ａ１、精度切替回路８１ａ１、Δｈ生成部８２ａ１、加算器８３ａ１、ｈ格納レジスタ８４ａ１、反転判定部８５ａ１、ビット格納レジスタ８６ａ１、ΔＥ生成部８７ａ１、判定部８８ａ１を有する。
【０２０８】
ここで、ＳＲＡＭ８０ａ１、精度切替回路８１ａ１、Δｈ生成部８２ａ１、加算器８３ａ１、ｈ格納レジスタ８４ａ１、反転判定部８５ａ１、ビット格納レジスタ８６ａ１、ΔＥ生成部８７ａ１、判定部８８ａ１は、各々、図８で説明した同名のハードウェアと同様の機能を有する。ただし、ＳＲＡＭ８０ａ１（または精度切替回路８１ａ１）および反転判定部８５ａ１には、規模結合回路９１により出力されたｉｎｄｅｘ＝ｙ０および反転可否を示すフラグＦｙ０が供給される。また、Δｈ生成部８２ａ１には、規模結合回路９１により出力された反転ビットｑｙ０が供給される。
【０２０９】
モード設定レジスタ７５は、精度切替回路８１ａ１，８１ａ２，…，８１ａｍに対する重み係数のビット数（精度）の設定を行う。モード設定レジスタ７５は、ランダムセレクタ部７２に対して設定を行う信号線を有していない（ただし、当該信号線を有してもよい）。第３の実施の形態では、一例として、第２の実施の形態で示した次の５種類のモードを利用可能である。
【０２１０】
第１のモードは、規模１ｋビット／精度１２８ビットのモードである。規模１ｋビット／精度１２８ビットのモードは、ＬＦＢを１個使用する。当該モードは、ＬＦＢ７０ａ，…，７０ｈの何れか１個だけで実現可能である。
【０２１１】
第２のモードは、規模２ｋビット／精度６４ビットのモードである。規模２ｋビット／精度６４ビットのモードは、ＬＦＢを２個使用する。例えば、当該モードは、ＬＦＢ７０ａ，７０ｂの組合せ、ＬＦＢ７０ｃ，７０ｄの組合せ、ＬＦＢ７０ｅ，７０ｆの組合せ、および、ＬＦＢ７０ｇ，７０ｈの組合せのうちの何れか１つの組合せで実現可能である。
【０２１２】
第３のモードは、規模４ｋビット／精度３２ビットのモードである。規模４ｋビット／精度３２ビットのモードは、ＬＦＢを４個使用する。例えば、当該モードは、ＬＦＢ７０ａ，７０ｂ，７０ｃ，７０ｄの組合せ、および、ＬＦＢ７０ｅ，７０ｆ，７０ｇ，７０ｈの組合せのうちの何れか１つの組合せで実現可能である。
【０２１３】
第４のモードは、規模４ｋビット／精度６４ビットのモードである。規模４ｋビット／精度６４ビットのモードは、ＬＦＢを８個使用する。当該モードは、ＬＦＢ７０ａ，…，７０ｈの組合せを用いて実現可能である。ただし、図１７で説明したように、１つのＬＦＢにおいて使用されるＬＦＥの数は、ＬＦＢ１つが備えるＬＦＥの数の半分となる。
【０２１４】
第５のモードは、規模８ｋビット／精度１６ビットのモードである。規模８ｋビット／精度１６ビットのモードは、ＬＦＢを８個使用する。当該モードは、ＬＦＢ７０ａ，…，７０ｈの組合せを用いて実現可能である。
【０２１５】
また、第３の実施の形態の最適化装置２６は、上記の規模１ｋビット／精度１２８ビットのモード、規模２ｋビット／精度６４ビットのモード、規模４ｋビット／精度３２ビットのモードを組合せて、同一問題または他の問題の演算を並列に実行可能にする。
【０２１６】
そのため、規模結合回路９１は、複数のＬＦＢ（ＬＦＢの組合せ）に対し、モード設定レジスタ９２によるスピンビット数の変更に応じて、スピンビット数に相当する数のＬＦＥを含むように、組合せるＬＦＢ数（組合せるグループ数）を選択する。規模結合回路９１は、例えば次の回路構成を有する。
【０２１７】
図２０は、規模結合回路の回路構成例を示す図である。
規模結合回路９１は、複数段にわたってツリー状に接続された選択回路９１ａ１，９１ａ２，９１ａ３，９１ａ４，９１ｂ１，９１ｂ２，９１ｃ１と、乱数生成部９１ｄと、モード選択回路９１ｅ１，９１ｅ２，９１ｅ３，９１ｅ４，９１ｅ５，９１ｅ６，９１ｅ７，９１ｅ８を有する。
【０２１８】
初段の選択回路９１ａ１，…，９１ａ４の各々には、ＬＦＢ７０ａ，…，７０ｈのそれぞれが出力する変数ｑｉとＦｉとΔＥｉとｉｎｄｅｘ＝ｉの組（状態信号）が２組ずつ入力される。例えば、選択回路９１ａ１には、ＬＦＢ７０ａ（＃０）が出力する（ｑｘ０，Ｆｘ０，ΔＥｘ０，ｉｎｄｅｘ＝ｘ０）の組と、ＬＦＢ７０ｂ（＃１）が出力する（ｑｘ１，Ｆｘ１，ΔＥｘ１，ｉｎｄｅｘ＝ｘ１）の組が入力される。また、選択回路９１ａ２には、ＬＦＢ７０ｃ（＃２）が出力する（ｑｘ２，Ｆｘ２，ΔＥｘ２，ｉｎｄｅｘ＝ｘ２）の組とＬＦＢ７０ｄ（＃３）が出力する（ｑｘ３，Ｆｘ３，ΔＥｘ３，ｉｎｄｅｘ＝ｘ３）の組が入力される。選択回路９１ａ３には、ＬＦＢ７０ｅ（＃４）が出力する（ｑｘ４，Ｆｘ４，ΔＥｘ４，ｉｎｄｅｘ＝ｘ４）の組とＬＦＢ７０ｆ（＃５）が出力する（ｑｘ５，Ｆｘ５，ΔＥｘ５，ｉｎｄｅｘ＝ｘ５）の組が入力される。選択回路９１ａ４には、ＬＦＢ７０ｇ（＃６）が出力する（ｑｘ６，Ｆｘ６，ΔＥｘ６，ｉｎｄｅｘ＝ｘ６）の組とＬＦＢ７０ｈ（＃７）が出力する（ｑｘ７，Ｆｘ７，ΔＥｘ７，ｉｎｄｅｘ＝ｘ７）の組が入力される。
【０２１９】
そして、選択回路９１ａ１，…，９１ａ４の各々は、乱数生成部９１ｄが出力する１ビット乱数に基づいて、２組のうちの一方の組の（ｘｉ，Ｆｉ，ΔＥｉ，ｉｎｄｅｘ＝ｉ）を選択する。このとき、選択回路９１ａ１，…，９１ａ４の各々は、Ｆｉが１である組を優先的に選択し、両方の組が１の場合には１ビット乱数に基づいて何れか一方の組を選択する（なお、選択回路９１ｂ１，９１ｂ２，９１ｃ１も同様）。ここで、乱数生成部９１ｄは、１ビット乱数を選択回路毎に個別に生成し、各選択回路に供給する。また、選択回路９１ａ１，…，９１ａ４の各々は、どちらの組を選択したかを示す識別値を、両組に含まれるｉｎｄｅｘに基づいて生成し、選択した変数ｑｉとＦｉとΔＥｉと識別値とを含む状態信号を出力する。なお、選択回路９１ａ１，…，９１ａ４の各々が出力する識別値は、入力されたｉｎｄｅｘよりも１ビット増える。
【０２２０】
２段目の選択回路９１ｂ１，９１ｂ２の各々には、選択回路９１ａ１，…，９１ａ４が出力する状態信号が２つずつ入力される。例えば、選択回路９１ｂ１には、選択回路９１ａ１，９１ａ２が出力する状態信号が入力され、選択回路９１ｂ２には、選択回路９１ａ３，９１ａ４が出力する状態信号が入力される。
【０２２１】
そして、選択回路９１ｂ１，９１ｂ２の各々は、２つの状態信号と、乱数生成部９１ｄが出力する１ビット乱数に基づいて、２つの状態信号の何れか一方を選択する。また、選択回路９１ｂ１，９１ｂ２の各々は、選択した状態信号に含まれる識別値について、何れの状態信号を選択したかを示すように１ビットを付加して更新し、選択した状態信号を出力する。
【０２２２】
最終段の選択回路９１ｃ１には、選択回路９１ｂ１，９１ｂ２が出力する状態信号が２つ入力される。選択回路９１ｃ１は、２つの状態信号と乱数生成部９１ｄが出力する１ビット乱数に基づいて、２つの状態信号の何れか一方を選択する。また、選択回路９１ｃ１は、選択した状態信号に含まれる識別値について、何れの状態信号を選択したかを示すように１ビットを付加して更新し、選択した状態信号を出力する。
【０２２３】
前述のように、識別値はｉｎｄｅｘに相当する。規模結合回路９１は、変数ｑｉとＦｉとΔＥｉと同様にして、各選択回路により、各ランダムセレクタ部から入力されたｉｎｄｅｘの選択を行うことで、反転ビットに対応するｉｎｄｅｘを出力してもよい。この場合、各ランダムセレクタ部は、各ＬＦＥから変数ｑやフラグＦと共にｉｎｄｅｘの供給を受けることになる。制御部２５ａは、各ＬＦＥの所定のｉｎｄｅｘ格納用のレジスタに対してＬＦＢの組合せに応じたｉｎｄｅｘの設定を行うことが考えられる。
【０２２４】
モード選択回路９１ｅ１，…，９１ｅ８の各々は、規模（すなわち、１ｋビット、２ｋビット、４ｋビットおよび８ｋビット）に応じた入力端子を有する。図中、モード選択回路９１ｅ１，…，９１ｅ８の各々に表記された「１」は規模１ｋビットに対応する入力端子を示す。同「２」は規模２ｋビットに対応する入力端子を示す。同「４」は規模４ｋビット（ただし、精度３２ビット）に対応する入力端子を示す。同「８」は規模８ｋビット（または規模４ｋビット／精度６４ビット）に対応する入力端子を示す。
【０２２５】
モード選択回路９１ｅ１の規模１ｋビットの入力端子には、ＬＦＢ７０ａ（＃０）が出力する状態信号が入力される。モード選択回路９１ｅ２の規模１ｋビットの入力端子には、ＬＦＢ７０ｂ（＃１）が出力する状態信号が入力される。モード選択回路９１ｅ３の規模１ｋビットの入力端子には、ＬＦＢ７０ｃ（＃２）が出力する状態信号が入力される。モード選択回路９１ｅ４の規模１ｋビットの入力端子には、ＬＦＢ７０ｄ（＃３）が出力する状態信号が入力される。モード選択回路９１ｅ５の規模１ｋビットの入力端子には、ＬＦＢ７０ｅ（＃４）が出力する状態信号が入力される。モード選択回路９１ｅ６の規模１ｋビットの入力端子には、ＬＦＢ７０ｆ（＃５）が出力する状態信号が入力される。モード選択回路９１ｅ７の規模１ｋビットの入力端子には、ＬＦＢ７０ｇ（＃６）が出力する状態信号が入力される。モード選択回路９１ｅ８の規模１ｋビットの入力端子には、ＬＦＢ７０ｈ（＃７）が出力する状態信号が入力される。
【０２２６】
モード選択回路９１ｅ１，９１ｅ２の各々の規模２ｋビットの入力端子には、選択回路９１ａ１が出力する状態信号が入力される。モード選択回路９１ｅ３，９１ｅ４の各々の規模２ｋビットの入力端子には、選択回路９１ａ２が出力する状態信号が入力される。モード選択回路９１ｅ５，９１ｅ６の各々の規模２ｋビットの入力端子には、選択回路９１ａ３が出力する状態信号が入力される。モード選択回路９１ｅ７，９１ｅ８の各々の規模２ｋビットの入力端子には、選択回路９１ａ４が出力する状態信号が入力される。
【０２２７】
モード選択回路９１ｅ１，９１ｅ２，９１ｅ３，９１ｅ４の各々の規模４ｋビットの入力端子には、選択回路９１ｂ１が出力する状態信号が入力される。モード選択回路９１ｅ５，９１ｅ６，９１ｅ７，９１ｅ８の各々の規模４ｋビットの入力端子には、選択回路９１ｂ２が出力する状態信号が入力される。
【０２２８】
モード選択回路９１ｅ１，…，９１ｅ８の各々の規模８ｋビットの入力端子には、選択回路９１ｃ１が出力する状態信号が入力される。
モード選択回路９１ｅ１，…，９１ｅ８の各々は、モード設定レジスタ９２による規模（スピンビット数）の設定を受け付ける。ただし、図２０では、モード設定レジスタ９２からモード選択回路９１ｅ２，…，９１ｅ８の各々に対する信号線を「…」の表記により略記している。モード選択回路９１ｅ１，…，９１ｅ８の各々は、設定された規模に応じた入力端子に入力された状態信号を選択して、（ｘｊ，Ｆｊ，ｉｎｄｅｘ＝ｊ）をＬＦＢ７０ａ，…，７０ｈへ出力し、ΔＥｊを加算器９３ａ，…，９３ｈへ出力する。
【０２２９】
例えば、モード選択回路９１ｅ１は、（ｘｙ０，Ｆｙ０，ｉｎｄｅｘ＝ｙ０）をＬＦＢ７０ａへ出力し、ΔＥｙ０を加算器９３ａへ出力する。加算器９３ａは、ΔＥｙ０を基にＥ０を更新する。モード選択回路９１ｅ２は、（ｘｙ１，Ｆｙ１，ｉｎｄｅｘ＝ｙ１）をＬＦＢ７０ｂへ出力し、ΔＥｙ１を加算器９３ｂへ出力する。加算器９３ｂは、ΔＥｙ１を基にＥ１を更新する。モード選択回路９１ｅ３は、（ｘｙ２，Ｆｙ２，ｉｎｄｅｘ＝ｙ２）をＬＦＢ７０ｃへ出力し、ΔＥｙ２を加算器９３ｃへ出力する。加算器９３ｃは、ΔＥｙ２を基にＥ２を更新する。モード選択回路９１ｅ４は、（ｘｙ３，Ｆｙ３，ｉｎｄｅｘ＝ｙ３）をＬＦＢ７０ｄへ出力し、ΔＥｙ３を加算器９３ｄへ出力する。加算器９３ｄは、ΔＥｙ３を基にＥ３を更新する。モード選択回路９１ｅ５は、（ｘｙ４，Ｆｙ４，ｉｎｄｅｘ＝ｙ４）をＬＦＢ７０ｅへ出力し、ΔＥｙ４を加算器９３ｅへ出力する。加算器９３ｅは、ΔＥｙ４を基にＥ４を更新する。モード選択回路９１ｅ６は、（ｘｙ５，Ｆｙ５，ｉｎｄｅｘ＝ｙ５）をＬＦＢ７０ｆへ出力し、ΔＥｙ５を加算器９３ｆへ出力する。加算器９３ｆは、ΔＥｙ５を基にＥ５を更新する。モード選択回路９１ｅ７は、（ｘｙ６，Ｆｙ６，ｉｎｄｅｘ＝ｙ６）をＬＦＢ７０ｇへ出力し、ΔＥｙ６を加算器９３ｇへ出力する。加算器９３ｇは、ΔＥｙ６を基にＥ６を更新する。モード選択回路９１ｅ８は、（ｘｙ７，Ｆｙ７，ｉｎｄｅｘ＝ｙ７）をＬＦＢ７０ｈへ出力し、ΔＥｙ７を加算器９３ｈへ出力する。加算器９３ｈは、ΔＥｙ７を基にＥ７を更新する。
【０２３０】
すなわち、第３の実施の形態の最適化装置２６は、あるＬＦＢ（グループ）に属する各ＬＦＥから出力された反転可否を示す信号に基づいて何れかのビットを選択し、選択したビットを示す信号を規模結合回路９１に出力するランダムセレクタ部をＬＦＢ毎に有する。規模結合回路９１は、スピンビット数の変更に応じて１以上のＬＦＢを組合せ、当該１以上のＬＦＢの各々に対応するランダムセレクタ部により選択されたビットを示す信号に基づいて反転させるビットを選択する。規模結合回路９１は、反転させるビットを示す信号を当該１以上のＬＦＢに属する各ＬＦＥに出力する。
【０２３１】
ここで、モード設定レジスタ９２は、モード選択回路９１ｅ１，…，９１ｅ８に対して、個別に規模の設定を行う。ただし、ある規模のモードにおいて、組合せて利用されるＬＦＢに対応するモード選択回路には、共通の規模が設定される。
【０２３２】
例えば、モード設定レジスタ９２は、ＬＦＢの第１の組合せに対応する第１のスピンビット列のスピンビット数とＬＦＢの第２の組合せに対応する第２のスピンビット列のスピンビット数とを、同じビット数、または、異なるビット数に設定してもよい。また、モード設定レジスタ７５を含む各ＬＦＢのモード設定レジスタは、ＬＦＢの第１の組合せに属するＬＦＥに対する重み係数のビット数とＬＦＢの第２の組合せに属するＬＦＥに対する重み係数のビット数とを、同じビット数、または、異なるビット数に設定してもよい。
【０２３３】
例えば、ＬＦＢ７０ａ，７０ｂを組合せて利用して規模２ｋビットのモードを利用する場合、モード設定レジスタ９２からモード選択回路９１ｅ１，９１ｅ２へ、規模２ｋビットのモードを選択する選択信号が供給される。このとき、例えば、最適化装置２６は、モード設定レジスタ９２の設定により残りの６つのＬＦＢを利用して、ＬＦＢ７０ａ，７０ｂによる演算と同じ問題、または、別の問題を並列に実行することが可能である。例えば、規模結合回路９１は、残りの６つのＬＦＢに対して、６つのＬＦＢの各々で規模１ｋビットのモードを６つ実現してもよい。また、規模結合回路９１は、６つのＬＦＢのうちの２つずつ組合せにより、規模２ｋビットのモードを３つ実現してもよい。更に、規模結合回路９１は、６つのＬＦＢのうち２つのＬＦＢの組合せにより、規模２ｋビットのモードを実現し、他の４つのＬＦＢの組合せにより、規模４ｋビットのモードを実現してもよい。
【０２３４】
並列に実現するモードの組合せは、上記の組合せに限らず、例えば、規模１ｋビットのモードが８つの組合せ、規模２ｋビットのモードが４つの組合せ、規模１ｋビットのモードが４つと規模２ｋビットのモードが２つの組合せなど、種々の組合せが考えられる。
【０２３５】
このように、規模結合回路９１は、モード設定レジスタ９２により複数のスピンビット列の各々に対するスピンビット数の設定を受け付け、複数のスピンビット列の各々のスピンビット数に対して、組合せるＬＦＢ数（グループ数）を選択し、ＬＦＢを組合せる。これにより、１つの最適化装置２６上に複数のイジングモデルを実現できる。
【０２３６】
なお、組合せて利用されるＬＦＢの組に対応するＥ格納レジスタの組には、共通のエネルギーが格納される。例えば、ＬＦＢ７０ａ，７０ｂの組合せで利用する場合、Ｅ格納レジスタ９４ａ，９４ｂに格納されるＥ０，Ｅ１は同じ値となる。この場合、当該ＬＦＢ７０ａ，７０ｂの組に対するエネルギー値を読み出すとき、制御部２５ａは、Ｅ格納レジスタ９４ａ，９４ｂの何れか一方（例えば、ＬＦＢ７０ａに対応するＥ格納レジスタ９４ａ）に格納されたエネルギー値を読み出せばよい。制御部２５ａは、ＬＦＢの他の組合せに対しても同様にしてエネルギー値を読み出す。
【０２３７】
第３の実施の形態では、制御部２５ａは、図１５のステップＳ１０として並列に演算する各問題に対する初期値や動作条件のＣＰＵ２１による入力を受け付ける。そして、制御部２５ａは、ステップＳ１１において、各問題に応じた規模／精度を、１つの問題に対して利用するＬＦＢのグループ毎に、ＬＦＢのモード設定レジスタおよびモード設定レジスタ９２に設定する。
【０２３８】
例えば、制御部２５ａは、第１の問題について、規模２ｋビット／精度６４ビットをＬＦＢ７０ａ，７０ｂのモード設定レジスタに設定すると共に、モード選択回路９１ｅ１，９１ｅ２に規模２ｋビットに対する出力を行うようモード設定レジスタ９２に設定する。また、制御部２５ａは、第２の問題について、規模２ｋビット／精度６４ビットをＬＦＢ７０ｃ，７０ｄのモード設定レジスタに設定すると共に、モード選択回路９１ｅ３，９１ｅ４に規模２ｋビットに対する出力を行うようモード設定レジスタ９２に設定する。
【０２３９】
この場合、最適化装置２６では、２つの問題（あるいは、両問題は同一問題でもよい）を並列に演算可能である。具体的には、制御部２５ａは、各問題に対応するＬＦＢの組合せに対して、図１６で示したフローチャートの手順を行うように各ＬＦＢを制御する。例えば、制御部２５ａは、問題毎に、温度パラメータＴなどの各種パラメータの初期値、重み係数、ある温度パラメータでのビット更新の回数および温度変更回数などを、個別に受け付けて、該当の問題の演算を行うＬＦＢの組合せに属する各ＬＦＢに入力し、ＬＦＢの各組合せにより演算を並列実行させる。
【０２４０】
制御部２５ａは、演算終了後、ＬＦＢ７０ａ，７０ｂの各ＬＦＥから第１の問題に対するスピンビット列を読み出して、第１の問題の解とする。また、制御部２５ａは、演算終了後、ＬＦＢ７０ｃ，７０ｄの各ＬＦＥから第２の問題に対するスピンビット列を読み出して、第２の問題の解とする。３以上の問題も同様にして、並列に演算可能である。これにより、複数の問題に対する演算を効率的に実行できる。
【０２４１】
また、同一問題をＬＦＢの複数の組により並列に解く場合、制御部２５ａは、例えば、レプリカ交換法と呼ばれる手法により、演算を高速化することが考えられる。レプリカ交換法では、ＬＦＢの各組（各レプリカ）で異なる温度パラメータによるスピンビット列の更新を行い、所定回数の更新後に、所定確率で温度パラメータをＬＦＢの組の間（すなわち、レプリカ間）で交換することで、解の探索を高速化する。
【０２４２】
あるいは、解の探索方法として、図１６の開始から終了までの手順を繰り返し行い、複数の演算結果の中から、最小となるエネルギーのスピンビット列を解として求める方法も考えられる。この場合、制御部２５ａは、ＬＦＢの複数の組を用いて同一問題を並列に解くことで、上記繰り返し回数を減らし、演算を高速化することができる。
【０２４３】
ところで、第２，第３の実施の形態で例示した最適化装置２５，２６を用いて演算可能な最適化問題には、種々の分野の問題が考えられる。例えば、学問や業種などの分野に応じて、求められる問題の規模や、問題の表現の精度が変わり得る。
【０２４４】
図２１は、問題毎の規模／精度の必要範囲の例を示す図である。
グラフ４００は、横軸を規模比（規模の大きさを示す度合い）、縦軸を精度比（精度の大きさを示す度合い）とし、３種類の分野の問題に対して求められる規模精度の範囲を例示している。規模比は、規模の基準となる規模基準値に対して実際に所要される規模値（スピンビット数）の比である。精度比は、精度の基準となる精度基準値に対して実際に所要される精度値（結合係数のビット数）の比である。
【０２４５】
領域４０１は、電力分野の問題に対して求められる規模比／精度比の範囲を示す。領域４０２は、金融分野の問題に対して求められる規模比／精度比の範囲を示す。領域４０３は、生命科学分野の問題に対して求められる規模比／精度比の範囲を示す。
【０２４６】
例えば、領域４０１によれば、電力分野の問題では、比較的高い精度比が求められることが多い。また、領域４０２によれば、金融分野の問題では、規模比は比較的小さくてよいが、比較的高い精度比が求められることがある。更に、生命科学分野の問題では、精度比は比較的低くてよいが、比較的大きい規模比が求められることがある。ただし、ここで例示した各分野において所要される規模比／精度比は一例であり、今後、各分野で扱われる問題に応じて、所要される規模比／精度比の範囲は変わり得る。
【０２４７】
一方、問題毎の規模および精度に合った最適化装置を製造することも考えられるが、効率的ではない。
そこで、第２，第３の実施の形態では、１チップの最適化装置２５，２６によって、種々の規模／精度のモードを実現可能とすることで、種々の分野の組合せ最適化問題に対応可能になる。
【０２４８】
図２２は、規模精度の選択可能範囲の例を示す図である。
グラフ５００は、最適化装置２５，２６により実現可能な規模精度の選択可能範囲の例を示す。ここで、ＬＦＥ毎のＳＲＡＭにおいて重み係数の格納のために確保される容量の上限が１２８ｋビットであり、最適化装置２５，２６の各々の全体におけるＬＦＥの数ｎ＝８１９２であるとする。上記で説明したように、最適化装置２５，２６は、例えば、５種類のモードを実現可能である。ただし、グラフ５００のハッチングされた領域で示される範囲内において、他の規模／精度のモードを利用可能としてもよい。ＬＦＥ毎のＳＲＡＭの容量を増やすことで、更に大きな規模／精度のモードも実現可能である。
【０２４９】
最適化装置２５，２６では、規模／精度のモードを可変とした上で、各ＬＦＥの種々の使用パターンを実現する。
図２３は、ＬＦＥの使用パターンの例を示す図である。
【０２５０】
図２３（Ａ）は、第２，第３の実施の形態で実現可能なｎ個のＬＦＥの使用パターン例（その１）を示す。例えば、最適化装置２６は、ｎ個のＬＦＥのうち、α個のＬＦＥを含むＬＦＥ群７１０（すなわち、ＬＦＢの第１の組合せ）を用いて第１のイジングモデルＸを実現する。また、最適化装置２６は、残りのβ個のＬＦＥを含むＬＦＥ群７２０を不使用とする。最適化装置２５も同様に、ＬＦＥ群７１０により第１のイジングモデルＸを実現し、ＬＦＥ群７２０を不使用としてもよい。
【０２５１】
図２３（Ｂ）は、第３の実施の形態で実現可能なｎ個のＬＦＥの使用パターン例（その２）を示す。例えば、最適化装置２６は、ｎ個のＬＦＥのうち、α個のＬＦＥを含むＬＦＥ群７１０（すなわち、ＬＦＢの第１の組合せ）を用いて、第１のイジングモデルＸを実現する。また、最適化装置２６は、残ったＬＦＥのうち、α個のＬＦＥを含むＬＦＥ群７３０（すなわち、ＬＦＢの第２の組合せ）を用いて、第１のイジングモデルＸを実現する。同一問題に対する演算の並列度を高めることで、解の収束性を早め演算を高速化することができる。
【０２５２】
図２３（Ｃ）は、第３の実施の形態で実現可能なｎ個のＬＦＥの使用パターン例（その３）を示す。例えば、最適化装置２６は、ｎ個のＬＦＥのうち、α個のＬＦＥを含むＬＦＥ群７１０（すなわち、ＬＦＢの第１の組合せ）を用いて、第１のイジングモデルＸを実現する。また、最適化装置２６は、残ったＬＦＥのうち、γ個（γ＝αでもよいし、γ≠αでもよい）のＬＦＥを含むＬＦＥ群７４０（すなわち、ＬＦＢの第２の組合せ）を用いて、第２のイジングモデルＹを実現する。これにより、異なる問題を並列に演算することができる。
【０２５３】
次に、ユーザによる最適化装置２６の利用フローの例を説明する。以下では、主に最適化装置２６を例示するが、最適化装置２５の場合も同様の利用フローである。
図２４は、最適化装置の利用フローの例を示す図である。
【０２５４】
（Ｓ１０１）ＣＰＵ２１は、ユーザが解きたい問題を示すデータ６０１を、クライアント３０からＮＩＣ２４を介して受け付ける。クライアント３０と、ＮＩＣ２４とにより、情報処理装置２０への各種データを入力する入力部および基底状態探索の結果として得られた解を、ユーザに把握しやすい結果情報として通知する通知部が実現される。ＣＰＵ２１は、ライブラリ２１ａの機能により、データ６０１をイジングモデルの基底状態の探索問題に変換する。その結果、ＣＰＵ２１は、問題の規模（スピンビット数）を示す規模データ６１１、問題の表現の精度を表す精度データ６１２、エネルギーの初期値を表すエネルギーデータ６１３および規模／精度に応じた規模精度モードデータ６１４を生成する。規模データ６１１は、スピンビット列を示すバイナリデータでもよい。精度データ６１２は、該当の精度で表されたスピンビット間の重み係数を含んでもよい。ＣＰＵ２１は、問題から適切な規模精度モードを決定し、規模精度モードデータ６１４を生成する。
【０２５５】
（Ｓ１０２）ＣＰＵ２１は、規模データ６１１、精度データ６１２、エネルギーデータ６１３を、初期値として制御部２５ａに入力する。
（Ｓ１０３）ＣＰＵ２１は、ユーザ指定動作条件６０２の入力を受け付ける。ユーザ指定動作条件６０２は、例えば、ある温度パラメータにおける状態更新の回数、温度パラメータの更新回数、温度パラメータの下げ幅および温度パラメータの初期値などを含む。また、ユーザ指定動作条件６０２は、組み合せるＬＦＢの数を含んでもよい。ＣＰＵ２１は、当該組み合せるＬＦＢの数を、規模精度モードデータ６１４に含める。ＣＰＵ２１は、規模精度モードデータ６１４およびユーザ指定動作条件６０２を、動作条件として制御部２５ａに入力する。規模精度モードデータ６１４は、モード設定レジスタ７５を含む各ＬＦＥのモード設定レジスタおよびモード設定レジスタ９２に設定される。
【０２５６】
（Ｓ１０４）ＣＰＵ２１は、ステップＳ１０２，Ｓ１０３が完了すると、制御部２５ａに対して基底状態の探索を行う演算の実行開始を指示する。
（Ｓ１０５）ＣＰＵ２１は、最適化装置２６による演算が完了すると、最適化装置２６から演算結果６１５を取得し、ユーザにとって把握し易い結果情報（例えば、結果表示画面の情報）に変換する。ＣＰＵ２１は、変換後の結果情報を、ユーザが解きたい問題の解６１６として、クライアント３０に送信する。
【０２５７】
このように、ＣＰＵ２１は、ユーザにより入力された問題に応じてスピンビット数と重み係数のビット数とを決定する。制御部２５ａは、スピンビット数と重み係数のビット数と重み係数とを示す情報をＣＰＵ２１から受け付ける。制御部２５ａは、スピンビット数と重み係数のビット数とをモード設定レジスタ５５（あるいは、モード設定レジスタ７５，９２）に設定する。制御部２５ａは、スピンビット数に相当する数のＬＦＥの各々のＳＲＡＭに格納する。
【０２５８】
こうして、ユーザは、自身が解きたい問題に応じた規模／精度により、最適化装置２５，２６による演算を実行させることが可能になる。例えば、最適化装置２６により、同一のユーザによる同一問題、または、異なる問題を並列に演算することも可能である。また、最適化装置２６により、異なるユーザによる異なる問題を並列に演算することも可能である。すなわち、解きたい問題に応じた適切な規模／精度で演算可能にすることで、空きＬＦＢ（あるいは空きＬＦＥ）を用いて、他の問題を並列に演算可能になる。また、複数のユーザで１チップの最適化装置２５，２６を共用可能になる。更に、複数の問題で１チップの最適化装置２５，２６を共用可能になる。
【０２５９】
また、上記に例示した機能を有する最適化装置（あるいは、最適化システム）も考えられる。当該最適化装置（あるいは、最適化システム）は、入力部と変換部と制御部と表示部とを有する。
【０２６０】
入力部は、解くべき問題と動作条件とを入力する。入力部は、例えば、マウスやキーボードなどの入力デバイスでもよいし、ＮＩＣ（例えば、ＮＩＣ２４）およびクライアント端末（例えば、クライアント３０）により実現されてもよい。
【０２６１】
変換部は、入力した問題をイジングモデルの基底状態の探索問題に変換するとともに、探索問題の規模を示す規模情報と、探索問題の表現の精度を表す精度情報と、探索問題のエネルギーの初期値を表すエネルギー情報と、規模および精度に応じた規模精度モード情報とを生成する。変換部は、例えば、ライブラリ２１ａおよびドライバ２１ｂの機能を発揮するＣＰＵ（例えば、ＣＰＵ２１）などのプロセッサでもよい。変換部は、ＦＰＧＡなどの半導体集積回路により実現されてもよい。
【０２６２】
制御部は、規模情報と、精度情報と、エネルギー情報（あるいは、規模情報と精度情報とエネルギー情報とに応じたスピンビット列の初期値、結合係数およびエネルギーの初期値）を入力するとともに動作条件と規模精度モード情報とを入力し、基底状態の探索を行う演算を実行して解を出力する。制御部は、例えば、ＬＦＢ５０（あるいはＬＦＢ７０ａ，…，７０ｈ）に対して、規模情報と、精度情報と、エネルギー情報（あるいは、規模情報と精度情報とエネルギー情報とに応じたスピンビット列の初期値、結合係数およびエネルギーの初期値）を入力するとともに動作条件と規模精度モード情報とを入力し、ＬＦＢを用いて基底状態の探索を行う演算を実行して解を出力する制御部２５ａでもよい。制御部は、例えば制御部２５ａとＬＦＢ５０（あるいはＬＦＢ７０ａ，…，７０ｈ）とを含む半導体チップであって、イジングモデルの基底状態の探索を行う半導体チップでもよい。すなわち、制御部は、規模情報と、精度情報と、エネルギー情報（あるいは、規模情報に応じたビット数のスピンビット列、精度情報に応じたビット数の結合係数およびエネルギー情報に応じたエネルギーの初期値）および、動作条件、並びに、規模精度モード情報に基づいて、イジングモデルの基底状態の探索を行う演算を実行して解を出力する半導体チップでもよい。規模情報は、規模の基準となる規模基準値に対する規模比により表されてもよい。精度情報は、精度の基準となる精度基準値に対する精度比により表されてもよい。
【０２６３】
表示部は、制御部による基底状態の探索の結果として得られた解を表示する。表示部は、ディスプレイでもよいし、ＮＩＣおよびクライアント端末により実現されてもよい。例えば、変換部は、基底状態の探索の結果として得られた解を、可視化した表示情報に変換する。表示部は、当該可視化した表示情報を表示する。
【０２６４】
例示した最適化装置により、規模／精度を可変にできる。ユーザは、解きたい問題に応じた規模／精度により、最適化装置による演算を実行させることが可能になる。
なお、第１の実施の形態の最適化装置１の制御は、最適化装置１を制御するコンピュータが備えるプロセッサがプログラムを実行することで実現されてもよい。例えば、プログラムは当該コンピュータが備えるＲＡＭに格納される。第２，第３の実施の形態の最適化装置２５，２６の制御は、ＣＰＵ２１にプログラムを実行させることで実現されてもよい。プログラムは、コンピュータ読み取り可能な記録媒体４１に記録できる。
【０２６５】
例えば、プログラムを記録した記録媒体４１を配布することで、プログラムを流通させることができる。また、プログラムを他のコンピュータに格納しておき、ネットワーク経由でプログラムを配布してもよい。コンピュータは、例えば、記録媒体４１に記録されたプログラムまたは他のコンピュータから受信したプログラムを、ＤＲＡＭ２２や記憶装置２３に格納し（インストールし）、ＤＲＡＭ２２や記憶装置２３からプログラムを読み込んで実行してもよい。
【０２６６】
上記については単に本発明の原理を示すものである。更に、多数の変形や変更が当業者にとって可能であり、本発明は上記に示し、説明した正確な構成および応用例に限定されるものではなく、対応する全ての変形例および均等物は、添付の請求項およびその均等物による本発明の範囲とみなされる。
【符号の説明】
【０２６７】
１  最適化装置
１ａ１，…，１ａＫ，…，１ａＮ  ビット演算回路
２  選択回路部
３  閾値生成部
４  乱数生成部
５  設定変更部
６  制御部
１１  記憶部
１２  精度切替回路
１３  反転判定部
１４  ビット保持部
１５  エネルギー変化計算部
１６  状態遷移判定部
【図１】
2020054061.tif 000017
【図２】
2020054061.tif 000018
【図３】
2020054061.tif 000019
【図４】
2020054061.tif 000020
【図５】
2020054061.tif 000021
【図６】
2020054061.tif 000022
【図７】
2020054061.tif 000023
【図８】
2020054061.tif 000024
【図９】
2020054061.tif 000025
【図１０】
2020054061.tif 000026
【図１１】
2020054061.tif 000027
【図１２】
2020054061.tif 000028
【図１３】
2020054061.tif 000029
【図１４】
2020054061.tif 000030
【図１５】
2020054061.tif 000031
【図１６】
2020054061.tif 000032
【図１７】
2020054061.tif 000033
【図１８】
2020054061.tif 000034
【図１９】
2020054061.tif 000035
【図２０】
2020054061.tif 000036
【図２１】
2020054061.tif 000037
【図２２】
2020054061.tif 000038
【図２３】
2020054061.tif 000039
【図２４】
2020054061.tif 000040
【国際調査報告】
2020054061.tif 000041
2020054061.tif 000042