(57)【要約】【課題】簡易な構成で最適化問題を解く。【解決手段】実施形態に係る計算装置は、行列乗算部と、時間発展部と、管理部と、出力部とを備える。行列乗算部は、第１時刻におけるＮ個（Ｎは２以上の整数）の第１中間変数と、予め設定されたＮ行×Ｎ列の係数を含む係数行列とを行列乗算することにより、第１時刻におけるＮ個の第２中間変数を算出する。時間発展部は、第１時刻におけるＮ個の第２中間変数に基づき、第１時刻から１サンプリング期間後の第２時刻におけるＮ個の第１変数および第２時刻におけるＮ個の第１中間変数を算出する。管理部は、開始時刻からサンプリング期間毎で時刻を増加させ、それぞれの時刻に対する処理を行列乗算部および時間発展部に実行させる。出力部は、予め設定された終了時刻におけるＮ個の第１変数を出力する。【選択図】図３
2020046887.tif 000002
【特許請求の範囲】
【請求項１】
第１時刻におけるＮ個（Ｎは２以上の整数）の第１中間変数と、予め設定されたＮ行×Ｎ列の係数を含む係数行列とを行列乗算することにより、前記第１時刻におけるＮ個の第２中間変数を算出する行列乗算部と、
前記第１時刻における前記Ｎ個の第２中間変数に基づき、前記第１時刻から１サンプリング期間後の第２時刻におけるＮ個の第１変数および前記第２時刻におけるＮ個の第１中間変数を算出する時間発展部と、
開始時刻からサンプリング期間毎で時刻を増加させ、それぞれの時刻に対する処理を前記行列乗算部および前記時間発展部に実行させる管理部と、
予め設定された終了時刻におけるＮ個の第１変数を出力する出力部と、
を備える計算装置。
【請求項２】
前記時間発展部は、前記第１時刻における前記Ｎ個の第２中間変数に基づき、前記第２時刻におけるＮ個の第２変数をさらに算出する
請求項１に記載の計算装置。
【請求項３】
前記時間発展部は、前記第１時刻におけるＮ個の第２変数に、前記第１時刻における前記Ｎ個の第２中間変数を加算することにより、前記第１時刻におけるＮ個の第２変数を更新する第１加算部を有する
請求項２に記載の計算装置。
【請求項４】
前記時間発展部は、
第１のＦＸ演算部と、
第１のＦＸ加算部と、
第１のＦＹ演算部と、
第１のＦＹ加算部と、
をさらに有し、
前記第１のＦＸ演算部は、前記第１時刻におけるＮ個の第１変数のそれぞれに対して第１関数演算をすることにより、Ｎ個の第２微分値を算出し、
前記第１のＦＸ加算部は、前記第１のＦＸ演算部が算出した前記Ｎ個の第２微分値と前記第１加算部が算出した更新された前記Ｎ個の第２変数とを加算することにより、Ｎ個の第２更新値を算出し、
前記第１のＦＹ演算部は、前記第１のＦＸ加算部が算出した前記Ｎ個の第２更新値のそれぞれに対して第２関数演算をすることにより、Ｎ個の第１微分値を算出し、
前記第１のＦＹ加算部は、前記第１のＦＹ演算部が算出した前記Ｎ個の第１微分値と前記第１時刻における前記Ｎ個の第１変数とを加算することにより、Ｎ個の第１更新値を算出する
請求項３に記載の計算装置。
【請求項５】
前記時間発展部は、
第１のＦＹ演算部と、
第１のＦＹ加算部と、
第１のＦＸ演算部と、
第１のＦＸ加算部と、
をさらに有し、
前記第１のＦＹ演算部は、前記第１加算部が算出した更新された前記Ｎ個の第２変数のそれぞれに対して第２関数演算をすることにより、Ｎ個の第１微分値を算出し、
前記第１のＦＹ加算部は、前記第１のＦＹ演算部が算出した前記Ｎ個の第１微分値と前記第１時刻におけるＮ個の第１変数とを加算することにより、Ｎ個の第１更新値を算出し、
前記第１のＦＸ演算部は、前記第１のＦＹ加算部が算出した前記Ｎ個の第１更新値のそれぞれに対して第１関数演算をすることにより、Ｎ個の第２微分値を算出し、
前記第１のＦＸ加算部は、前記第１のＦＸ演算部が算出した前記Ｎ個の第２微分値と前記第１加算部が算出した更新された前記Ｎ個の第２変数とを加算することにより、Ｎ個の第２更新値を算出する
請求項３に記載の計算装置。
【請求項６】
前記第１のＦＹ加算部が算出した前記Ｎ個の第１更新値を、前記第２時刻における前記Ｎ個の第１変数として記憶する第１変数メモリと、
前記第１のＦＸ加算部が算出した前記Ｎ個の第２更新値を、前記第２時刻における前記Ｎ個の第２変数として記憶する第２変数メモリと、
をさらに備える請求項４または５に記載の計算装置。
【請求項７】
前記時間発展部は、
第２から第Ｍ（Ｍは２以上の整数）までの（Ｍ−１）個のＦＸ演算部と、
第２から第Ｍまでの（Ｍ−１）個のＦＸ加算部と、
第２から第Ｍまでの（Ｍ−１）個のＦＹ演算部と、
第２から第Ｍまでの（Ｍ−１）個のＦＹ加算部と、
をさらに有し、
第ｍ（ｍは２からＭまでの整数）のＦＸ演算部は、第（ｍ−１）のＦＹ加算部が算出したＮ個の第１更新値のそれぞれに対して前記第１関数演算をすることにより、Ｎ個の第２微分値を算出し、
第ｍのＦＸ加算部は、前記第ｍのＦＸ演算部が算出した前記Ｎ個の第２微分値と第（ｍ−１）のＦＸ加算部が算出したＮ個の第２更新値とを加算することにより、新たなＮ個の第２更新値を算出し、
第ｍのＦＹ演算部は、前記第ｍのＦＸ加算部が算出した前記Ｎ個の第２更新値のそれぞれに対して前記第２関数演算をすることにより、Ｎ個の第１微分値を算出し、
第ｍのＦＹ加算部は、前記第ｍのＦＹ演算部が算出した前記Ｎ個の第１微分値と第（ｍ−１）のＦＹ加算部が算出したＮ個の第１更新値とを加算することにより、新たなＮ個の第１更新値を算出する
請求項４に記載の計算装置。
【請求項８】
前記時間発展部は、
第２から第Ｍ（Ｍは２以上の整数）までの（Ｍ−１）個のＦＹ演算部と、
第２から第Ｍまでの（Ｍ−１）個のＦＹ加算部と、
第２から第Ｍまでの（Ｍ−１）個のＦＸ演算部と、
第２から第Ｍまでの（Ｍ−１）個のＦＸ加算部と、
をさらに有し、
第ｍ（ｍは２からＭまでの整数）のＦＹ演算部は、第（ｍ−１）のＦＸ加算部が算出した前記Ｎ個の第２更新値のそれぞれに対して前記第２関数演算をすることにより、Ｎ個の第１微分値を算出し、
第ｍのＦＹ加算部は、第ｍのＦＹ演算部が算出した前記Ｎ個の第１微分値と第（ｍ−１）のＦＹ加算部が算出したＮ個の第１更新値とを加算することにより、新たなＮ個の第１更新値を算出し、
第ｍのＦＸ演算部は、前記第ｍのＦＹ加算部が算出した前記Ｎ個の第１更新値のそれぞれに対して前記第１関数演算をすることにより、Ｎ個の第２微分値を算出し、
第ｍのＦＸ加算部は、前記第ｍのＦＸ演算部が算出した前記Ｎ個の第２微分値と第（ｍ−１）のＦＸ加算部が算出したＮ個の第２更新値とを加算することにより、新たなＮ個の第２更新値を算出する
請求項５に記載の計算装置。
【請求項９】
第ＭのＦＹ加算部が算出した前記Ｎ個の第１更新値を、前記第２時刻における前記Ｎ個の第１変数として記憶する第１変数メモリと、
第ＭのＦＸ加算部が算出した前記Ｎ個の第２更新値を、前記第２時刻における前記Ｎ個の第２変数として記憶する第２変数メモリと、
をさらに備える請求項７または８に記載の計算装置。
【請求項１０】
前記第１関数演算は、
ｄｔ´×｛−Ｄ＋ｐ−Ｋｘｉ２｝ｘｉ−ｃ×ｈｉ×ａ…（１０１）
であり、
前記第２関数演算は、
ｄｔ´×Ｄ×ｙｉ…（１０２）
であり、
ｘｉは、前記第１時刻における前記Ｎ個の第１変数のうちのｉ番目の第１変数、または、前記Ｎ個の第１更新値のうちのｉ番目の第１更新値であり、
ｙｉは、前記第１加算部が算出した更新された前記Ｎ個の第２変数のうちのｉ番目の更新された第２変数、または、前記Ｎ個の第２更新値のうちのｉ番目の第２更新値であり、
ｄｔ´は、予め設定された微小時間であり、
Ｄ、ｃ、Ｋは、予め設定された定数であり、
ｈｉは、ｉ毎に設定された係数であり、
ｐおよびａは、予め定められた演算式に従って時刻毎に増加する値である
請求項４から９の何れか１項に記載の計算装置。
【請求項１１】
前記第１関数演算は、
ｄｔ´×｛［（−Ｄ＋ｐ）（１＋ｘｉｎ）−Ｋｘｉｎ＋２］ｘｉ−ｃ×ｈｉ×ａ｝…（１０３）
であり、
前記第２関数演算は、
ｄｔ´×Ｄ×ｙｉ…（１０４）
であり、
ｘｉは、前記第１時刻における前記Ｎ個の第１変数のうちのｉ番目の第１変数、または、前記Ｎ個の第１更新値のうちのｉ番目の第１更新値であり、
ｙｉは、前記第１加算部が算出した更新された前記Ｎ個の第２変数のうちのｉ番目の更新された第２変数、または、前記Ｎ個の第２更新値のうちのｉ番目の第２更新値であり、
ｄｔ´は、予め設定された微小時間であり、
Ｄ、ｃ、Ｋは、予め設定された係数であり、
ｈｉは、ｉ毎に設定された係数であり、
ｐおよびａは、予め定められた演算式に従って時刻毎に増加する値である
請求項４から９の何れか１項に記載の計算装置。
【請求項１２】
前記時間発展部は、
前記第２時刻における前記Ｎ個の第１変数のそれぞれに予め設定された値を乗じることにより、前記第２時刻における前記Ｎ個の第１中間変数を算出する第１乗算部と、
前記第１乗算部が算出した前記第２時刻における前記Ｎ個の第１中間変数を記憶する第１中間変数メモリと、
をさらに有する請求項３から１１の何れか１項に記載の計算装置。
【請求項１３】
前記時間発展部は、
前記第２時刻における前記Ｎ個の第１変数を、前記第２時刻における前記Ｎ個の第１中間変数として記憶する第１中間変数メモリと、
前記行列乗算部から出力された前記第１時刻における前記Ｎ個の第２中間変数のそれぞれに予め設定された値を乗じる第１乗算部と、
をさらに有し、
前記第１加算部は、前記第１時刻における前記Ｎ個の第２変数に、前記第１乗算部が予め設定された値を乗じた前記第１時刻における前記Ｎ個の第２中間変数を加算することにより、前記第１時刻における前記Ｎ個の第２変数を更新する
をさらに有する請求項３から１１の何れか１項に記載の計算装置。
【請求項１４】
前記開始時刻におけるＮ個の第１中間変数を前記行列乗算部に与える入力部をさらに備える
請求項１から１３の何れか１項に記載の計算装置。
【請求項１５】
前記時間発展部は、前記第１時刻における前記Ｎ個の第１中間変数を、１クロックサイクルに第１数の第１中間変数を含む第１中間ストリームとして前記行列乗算部へと出力し、
前記行列乗算部は、前記第１時刻における前記Ｎ個の第２中間変数を、１クロックサイクルに第２数の第２中間変数を含む第２中間ストリームとして前記時間発展部へと出力する
請求項１から１４の何れか１項に記載の計算装置。
【請求項１６】
前記係数行列は、それぞれが（Ｎ／Ｐｒ３）行（Ｐｒ３は、Ｎの約数）×Ｎ列の係数を含むＰｒ３個の分割行列に分割され、
前記Ｎ個の第２中間変数は、それぞれが（Ｎ／Ｐｒ３）個の第２中間変数を含むＰｒ３個のブロックに分割され、
前記Ｐｒ３個のブロックは、前記Ｐｒ３個の分割行列に一対一で対応付けられ、
前記行列乗算部は、前記Ｐｒ３個の分割行列に一対一で対応付けられたＰｒ３個の分割行列乗算部を有し、
前記Ｐｒ３個の分割行列乗算部のそれぞれは、前記第１中間変数と、対応する分割行列とを行列乗算することにより、対応するブロックに含まれる（Ｎ／Ｐｒ３）個の第２中間変数を算出する
請求項１５に記載の計算装置。
【請求項１７】
前記Ｐｒ３個の分割行列乗算部は、直列に接続され、
前記Ｐｒ３個の分割行列乗算部のそれぞれは、バッファ部を含み、
先頭の分割行列乗算部の前記バッファ部は、前記時間発展部から出力された前記第１中間ストリームを取得し、取得した前記第１中間ストリームを一定時間記憶して出力し、
先頭以外の分割行列乗算部の前記バッファ部は、直前段の分割行列乗算部から出力された前記第１中間ストリームを取得し、取得した前記第１中間ストリームを一定時間記憶して出力する
請求項１６に記載の計算装置。
【請求項１８】
前記Ｐｒ３個の分割行列乗算部および前記時間発展部は、それぞれが独立した（Ｐｒ３＋１個）のチップに含まれる
請求項１６または１７に記載の計算装置。
【請求項１９】
前記第１中間ストリームおよび前記第２中間ストリームを伝送する（Ｐｒ３＋１個）の通信リンクをさらに備え、
前記（Ｐｒ３＋１個）のチップのうちの第ｋ（ｋは、１以上、Ｐｒ３以下の整数）のチップの出力端子は、第（ｋ＋１）のチップの入力端子に、前記（Ｐｒ３＋１個）の通信リンクのうちの第ｋの通信リンクを介して接続され、
第（Ｐｒ３＋１）のチップの出力端子は、第１のチップ７０−１の入力端子に、第（Ｐｒ３＋１）の通信リンクを介して接続される
請求項１８に記載の計算装置。
【請求項２０】
前記Ｐｒ３個の分割行列のそれぞれは、それぞれがＰｒ１行×Ｎ列の係数を含むＰｒ２個のサブ行列に分割され、Ｐｒ１およびＰｒ２は、Ｎの約数であり、Ｐｒ１×Ｐｒ２×Ｐｒ３＝Ｎであり、
前記Ｐｒ３個のブロックのそれぞれは、それぞれがＰｒ１個の第２中間変数を含むＰｒ２個のサブブロックに分割され、
ｋ番目（ｋは、１以上、Ｐｒ３以下の整数）のブロックに含まれる前記Ｐｒ２個のサブブロックは、ｋ番目の分割行列に含まれるＰｒ２個のサブ行列に一対一で対応付けられ、
前記Ｐｒ３個の分割行列乗算部のそれぞれは、対応する分割行列に含まれる前記Ｐｒ２個のサブ行列に一対一で対応付けられたＰｒ２個のサブ行列乗算部をさらに含み、
第ｋ番目の分割行列乗算部に含まれる前記Ｐｒ２個のサブ行列乗算部のそれぞれは、前記Ｎ個の第１中間変数と、対応するサブ行列とを行列乗算することにより、対応するサブブロックに含まれるＰｒ１個の第２中間変数を算出する
請求項１７に記載の計算装置。
【請求項２１】
前記バッファ部は、シフトレジスタとして機能するＰｒ２段のレジスタを含み、
前記Ｐｒ２段のレジスタは、前記Ｐｒ２個のサブ行列乗算部に一対一に対応付けられ、
前記Ｐｒ２段のレジスタのそれぞれは、Ｐｃ個（Ｐｃは、Ｎの約数）の第１中間変数を並列に１クロックサイクル記憶し、次のクロックサイクルにおいて、記憶している前記Ｐｃ個の第１中間変数を次段のレジスタに並列に転送する
請求項２０に記載の計算装置。
【請求項２２】
前記Ｐｒ２個のサブ行列乗算部のそれぞれは、対応するサブ行列に含まれるＰｒ１個の行に一対一で対応付けられたＰｒ１個の乗累算部を含み、
前記Ｐｒ１個の乗累算部のそれぞれは、
前記Ｐｒ２段のレジスタのうちの対応するレジスタに順次に記憶される、前記第１中間ストリームの先頭から末尾までのＮ個の前記第１中間変数を、クロックサイクル毎に取得し、
取得したそれぞれの第１変数と、前記係数行列における対応する行に含まれる、前記取得した第１中間変数に対応する列の係数とを乗算し、
前記第１中間変数と前記係数との乗算結果を、前記第１中間ストリームの先頭の前記第１中間変数から末尾の第１中間変数まで累積加算することにより、
対応するサブブロックに含まれる対応する位置の第２中間変数を算出する
請求項２１に記載の計算装置。
【請求項２３】
前記Ｐｒ２個のサブ行列乗算部のそれぞれは、対応するサブブロックに含まれる前記Ｐｒ１個の第２中間変数を１クロックサイクルで並列に出力し、且つ、他のサブ行列乗算部とは異なるクロックサイクルにおいて前記Ｐｒ１個の第２中間変数を出力する
請求項２０から２２の何れか１項に記載の計算装置。
【請求項２４】
前記Ｐｒ３個の分割行列乗算部のそれぞれは、前記Ｐｒ２個のサブ行列乗算部のそれぞれから出力された前記Ｐｒ１個の第２中間変数を多重化することにより、１クロックサイクルにＰｒ１個の第２中間変数を含む前記第２中間ストリームを生成する多重化部をさらに含む
請求項２３に記載の計算装置。
【請求項２５】
前記Ｐｒ３個の分割行列乗算部のそれぞれは、前記バッファ部に記憶された前記第１中間ストリームに基づき、対応するブロックに含まれる（Ｎ／Ｐｒ３）個の第２中間変数を算出する実行部をさらに含み、
前記実行部は、
対応するブロックに含まれる（Ｎ／Ｐｒ３）個の第２中間変数を、１クロックサイクルにＰｒ１個（Ｐｒ１は、Ｎの約数）の第２中間変数を含む前記第２中間ストリームとして出力し、且つ、他の分割行列乗算部とは異なるクロックサイクルにおいて前記第２中間ストリームを出力する
請求項２０から２４の何れか１項に記載の計算装置。
【請求項２６】
前記Ｐｒ３個の分割行列乗算部のそれぞれは、セレクタを含み、
先頭の分割行列乗算部の前記セレクタは、
前記先頭の分割行列乗算部の前記実行部が前記第２中間ストリームを出力したクロックサイクルにおいて、前記先頭の分割行列乗算部の前記行列乗算実行部が出力した前記第２中間ストリームを選択して出力し、
先頭を除いた前記ｋ番目の分割行列乗算部の前記セレクタは、
前記ｋ番目の分割行列乗算部の前記実行部が前記第２中間ストリームを出力したクロックサイクルにおいて、前記ｋ番目の分割行列乗算部の前記実行部が出力した前記第２中間ストリームを選択して出力し、
前記ｋ番目の分割行列乗算部の前記実行部が前記第２中間ストリームを出力していないクロックサイクルにおいて、前段の分割行列乗算部の前記セレクタが出力した前記第２中間ストリームを選択して出力する
請求項２５に記載の計算装置。
【請求項２７】
前記時間発展部は、１クロックサイクルに含まれるＰｒ１個の第２中間変数に対して、前記Ｎ個の第１変数の算出処理を、Ｐｒ１の並列度で実行する
請求項２５または２６に記載の計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、計算装置に関する。
【背景技術】
【０００２】
イジングモデルを用いて最適化問題を解くための様々なアルゴリズムが提案されている。また、イジングモデルを用いて最適化問題を解くハードウェアも提案されている。
【０００３】
このような最適化問題を解くハードウェアは、簡易な構成で、高速に問題が解けることが好ましい。また、このような最適化問題を解くハードウェアは、取り扱うことが可能な変数の個数が多い方が好ましい。また、このような最適化問題を解くハードウェアは、取り扱う変数の個数が変わっても、大幅な設計変更をすることなく、自在に対応できることが好ましい。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第５８６５４５６号公報
【特許文献２】特開２０１８−００５５４１号公報
【特許文献３】特開２０１８−０１０４７４号公報
【非特許文献】
【０００５】
【非特許文献１】T.  Inagaki  et  al.,“A  coherent  Ising  machine  for  2000-node  optimization  problems”,  Science  354,  603  (2016).
【非特許文献２】H.  Goto,“Bifurcation-based  adiabatic  quantum  computation  with  a  nonlinear  oscillator  network”,  Sci.  Rep.  6,  21686  (2016).
【非特許文献３】Y.  Haribara  et  al.,  “Performance  evaluation  of  coherent  Ising  machines  against  classical  neural  networks”,  Quantum  Sci.  Technol.  2,  044002  (2017).
【発明の概要】
【発明が解決しようとする課題】
【０００６】
発明が解決しようとする課題は、簡易な構成で最適化問題を解くことである。
【課題を解決するための手段】
【０００７】
実施形態に係る計算装置は、行列乗算部と、時間発展部と、管理部と、出力部とを備える。前記行列乗算部は、第１時刻におけるＮ個（Ｎは２以上の整数）の第１中間変数と、予め設定されたＮ行×Ｎ列の係数を含む係数行列とを行列乗算することにより、前記第１時刻におけるＮ個の第２中間変数を算出する。前記時間発展部は、前記第１時刻における前記Ｎ個の第２中間変数に基づき、前記第１時刻から１サンプリング期間後の第２時刻におけるＮ個の第１変数および前記第２時刻におけるＮ個の第１中間変数を算出する。前記管理部は、開始時刻からサンプリング期間毎で時刻を増加させ、それぞれの時刻に対する処理を前記行列乗算部および前記時間発展部に実行させる。前記出力部は、予め設定された終了時刻におけるＮ個の第１変数を出力する。
【図面の簡単な説明】
【０００８】
【図１】第１実施形態に係る計算装置の構成図。
【図２】演算部の処理の流れを示すフローチャート。
【図３】第２実施形態に係る演算部の構成図。
【図４】第２実施形態での変数および係数行列の関係図。
【図５】関数演算部の構成の第１例を示す図。
【図６】関数演算部の構成の第２例を示す図。
【図７】関数演算部の構成の第３例を示す図。
【図８】関数演算部の構成の第４例を示す図。
【図９】第３実施形態での変数および係数行列の関係図。
【図１０】第３実施形態に係る行列乗算部の構成図。
【図１１】第３実施形態に係る実装例を示す図。
【図１２】第４実施形態での変数および係数行列の関係図。
【図１３】第４実施形態に係る分割行列乗算部の構成図。
【図１４】第５実施形態での変数および係数行列の関係図。
【図１５】第６実施形態に係るサブ行列乗算部の構成図。
【図１６】分割行列メモリに記憶された分割行列を示す図。
【図１７】乗累算部に送信されるサブ行列を示す図。
【図１８】乗累算部の構成図。
【図１９】第５実施形態におけるパラメータおよびタイミングを示す図。
【図２０】第６実施形態に係る時間発展部の構成図。
【図２１】第１中間変数および第２中間変数のタイミングチャート。
【発明を実施するための形態】
【０００９】
以下、図面を参照しながら実施形態に係る計算装置１０について詳細に説明する。実施形態に係る計算装置１０は、イジングモデルを用いた最適化問題を解くことを目的とする。
【００１０】
（前提）
まず、計算装置１０において実行される処理の前提について説明する。
【００１１】
イジングモデルのエネルギーＥＩｓｉｎｇは、下記の式（１）により表される。
【数１】
2020046887.tif 000003
【００１２】
式（１）において、Ｎはスピンの数を表す。ｓｉは、ｉ番目のスピンの状態を表す。例えば、ｓｉ＝±１である。ｓｊは、ｊ番目のスピンの状態を表す。例えば、ｓｊ＝±１である。ｉおよびｊは、０以上、（Ｎ−１）以下の整数である。
【００１３】
式（１）において、Ｊｉ，ｊは、Ｎ行×Ｎ列の係数行列Ｊに含まれるｉ行、ｊ列の係数である。Ｊｉ，ｊは、ｉ番目のスピンとｊ番目のスピンとの間の相互作用を表す。係数行列Ｊは、例えば実対称行列である。実対称行列は、対角成分（対角要素）が全てゼロである行列である。ｈｉは、Ｎ個の係数配列に含まれるｉ番目の係数である。ｈｉは、ｉ番目のスピンに単独に加わる作用を表す。イジングモデルのエネルギーＥＩｓｉｎｇを最小とするスピン状態（基底状態）を探索する問題をイジング問題という。イジング問題を解く機械をイジングマシンと呼んでもよい。イジングマシンは、係数行列Ｊとｈを入力され、基底状態もしくはよりエネルギーの低い近似解を計算し出力する。
【００１４】
量子分岐マシンの古典モデル（以下、古典分岐マシンと呼ぶ）が提案されている。古典分岐マシンは、式（２）、式（３）および式（４）に示す連立常微分方程式で表された運動方程式を用いて、式（１）の最適解を算出する。
【００１５】
【数２】
2020046887.tif 000004
【数３】
2020046887.tif 000005
【数４】
2020046887.tif 000006
【００１６】
式（２）、式（３）および式（４）において、Ｎは、質点の数を表し、２以上の整数である。Ｎは、スピンの数に対応する。ｘｉは、ｉ番目の質点の位置を表す実数である。ｙｉは、ｉ番目の質点の運動量を表す実数である。ｉおよびｊは、０から（Ｎ−１）までの整数である。
【００１７】
式（２）、式（３）および式（４）において、Ｊｉ，ｊは、予め定められたＮ行×Ｎ列の係数を含む係数行列Ｊに含まれるｉ行、ｊ列の係数である。係数行列Ｊは、例えば実対称行列である。ｈｉは、予め定められたＮ個の係数配列に含まれるｉ番目の係数である。式（２）、式（３）および式（４）において、ｈｉの項は、無くてもよい。
【００１８】
式（２）、式（３）および式（４）において、Ｄは、例えば離調に対応する定数である。ｃは、定数である。Ｋは、例えばカー係数に対応する定数である。例えば、Ｄ、ｃおよびＫは、予め定められている。
【００１９】
式（２）、式（３）および式（４）において、ｔは、時刻を表す。ｐ（ｔ）は、例えば、ｔを変数とする関数であり、ポンプレートである。ａ（ｔ）は、ｔを変数とする関数である。ａ（ｔ）は、例えば、下記の式（５）により表される。
【数５】
2020046887.tif 000007
【００２０】
古典分岐マシンは、ｔをゼロから十分大きな値へ微小時間ずつ増加させて、ｔ毎に、式（２）および式（３）を用いてｘｉおよびｙｉを更新する。そして、古典分岐マシンは、ｔを十分に大きくした場合のｘｉの最終値の符号（±１）を、ｓｉの最適解として出力する。このように、古典分岐マシンは、イジングモデルを、式（２）、式（３）および式（４）のＨをハミルトニアンとしたハミルトン力学系であると見なしている。
【００２１】
また、イジングモデルの最適解を算出する方法として、シミュレーティッドアニーリングが知られている。この方法では、逐次更新アルゴリズムが採用される。逐次更新アルゴリズムは、複数のスピンを１つずつ選択して順次に更新する。このような逐次更新アルゴリズムは、並列計算に適しておらず高速化することは困難である。
【００２２】
これに対して、古典分岐マシンの運動方程式をデジタル計算機で離散解法によって解くアルゴリズムが考えられる。このアルゴリズムは、シミュレーティッドアニーリングとは異なり、複数の変数を同時に更新することができる。
【００２３】
しかし、古典分岐マシンは、最も計算量が大きい係数行列Ｊを用いた行列乗算を、ｘｉおよびｙｉの両者の算出のために、実行しなければならなかった。また、古典分岐マシンは、式（２）、式（３）および式（４）により表される運動方程式を、計算コストの大きい離散解法（４次のルンゲ・クッタ法等）を実行することにより、解かなければならなかった。このため、古典分岐マシンは、計算量が膨大となってしまっていた。
【００２４】
これに対して、実施形態に係る計算装置１０は、下記の式（６）、式（７）および式（８）に示す新規な連立常微分方程式で表された運動方程式を用いて、式（１）の最適解を算出する。
【００２５】
【数６】
2020046887.tif 000008
【数７】
2020046887.tif 000009
【数８】
2020046887.tif 000010
【００２６】
式（６）、式（７）および式（８）において、Ｎ、ｘｉ、ｙｉ、ｉ、ｊ、Ｊｉ，ｊ、ｈｉ、Ｄ、ｃ、Ｋ、ｔ、ｐ（ｔ）およびａ（ｔ）は、式（２）〜式（４）と同様である。
【００２７】
実施形態に係る計算装置１０は、ｔをゼロから十分大きな値へと微小時間ずつ増加させて、ｔ毎に、式（６）および式（７）を用いてｘｉおよびｙｉを更新する。そして、実施形態に係る計算装置１０は、ｔを十分に大きくした場合のｘｉの最終値の符号（±１）を、ｓｉの最適解として出力する。このように、実施形態に係る計算装置１０は、イジング問題を、式（８）のＨをハミルトニアンとしたハミルトン力学系の時間発展をシミュレートすることで解く。
【００２８】
式（６）、式（７）および式（８）において、最も計算量が大きい係数行列Ｊに対する行列乗算は、式（７）には含まれるが、式（６）には含まれない。従って、実施形態に係る計算装置１０は、最も計算量が大きい係数行列Ｊに対する行列乗算を、ｙｉの更新のためにのみ実行すればよく、ｘｉの更新のためには実行しなくてよい。また、ｘｉの時間微分値（ｄｘｉ／ｄｔ）を算出するための式（６）は、ｐ（ｔ）が消去されている。従って、実施形態に係る計算装置１０は、少ない計算量でイジングモデルの最適解を算出することができる。
【００２９】
また、ｘｉの時間微分値（ｄｘｉ／ｄｔ）を算出するための式（６）は、ｙｉを含むが、ｘｉを含まない。また、ｙｉの時間微分値（ｄｙｉ／ｄｔ）を算出するための式（７）は、ｘｉを含むが、ｙｉを含まない。
【００３０】
つまり、式（６）および式（７）を用いる場合、ハミルトニアンにおいて、ｘｉとｙｉとは、互いに分離されている。従って、実施形態に係る計算装置１０は、計算量が小さく安定な離散解法を適用して、ｘｉおよびｙｉを更新することが可能となる。例えば、実施形態に係る計算装置１０は、シンプレクティック・オイラー法等を適用して、ｘｉおよびｙｉを更新する。従って、実施形態に係る計算装置１０は、簡易な演算および簡易な構成で、イジングモデルを用いた最適化問題の最適解を算出することができる。
【００３１】
また、実施形態に係る計算装置１０は、下記の式（９）および式（１０）に示す新規な連立常微分方程式で表された運動方程式を用いて、式（１）の最適解を算出してもよい。
【００３２】
【数９】
2020046887.tif 000011
【数１０】
2020046887.tif 000012
【００３３】
式（９）および式（１０）において、Ｎ、ｘｉ、ｙｉ、ｉ、ｊ、Ｊｉ，ｊ、ｈｉ、Ｄ、ｃ、Ｋ、ｔ、ｐ（ｔ）およびａ（ｔ）は、式（２）〜式（４）と同様である。式（９）および式（１０）において、ｎは、２以上の偶数である。
【００３４】
この場合、実施形態に係る計算装置１０は、ｔをゼロから十分大きな値へと微小時間ずつ増加させて、ｔ毎に、式（９）および式（１０）を用いてｘｉおよびｙｉを更新する。そして、実施形態に係る計算装置１０は、ｔを十分に大きくした場合のｘｉの最終値の符号（±１）を、ｓｉの最適解として出力する。
【００３５】
ここで、最も計算量が大きい係数行列Ｊに対する行列乗算は、式（９）に含まれ、式（１０）には含まれない。従って、式（９）および式（１０）を用いる場合も、実施形態に係る計算装置１０は、最も計算量が大きい係数行列Ｊに対する行列乗算を、ｙｉの更新のためにのみ実行すればよく、ｘｉの更新のためには実行しなくてよい。また、ｘｉの時間微分値（ｄｘｉ／ｄｔ）を算出するための式（９）は、ｐ（ｔ）が消去されている。従って、式（９）および式（１０）を用いる場合も、実施形態に係る計算装置１０は、少ない計算量でイジングモデルを用いた最適化問題の最適解を算出することができる。
【００３６】
また、ｘｉの時間微分値（ｄｘｉ／ｄｔ）を算出するための式（９）は、ｙｉを含むが、ｘｉを含まない。また、ｙｉの時間微分値（ｄｙｉ／ｄｔ）を算出するための式（１０）は、ｘｉを含むが、ｙｉを含まない。
【００３７】
つまり、式（９）および式（１０）を用いる場合も、ハミルトニアンにおいて、ｘｉとｙｉとは、互いに分離されている。従って、式（９）および式（１０）を用いる場合も、式（６）および式（７）を用いる場合と同様に、実施形態に係る計算装置１０は、簡易な演算および簡易な構成で、イジングモデルを用いた最適化問題の最適解を算出することができる。
【００３８】
（第１実施形態）
第１実施形態に係る計算装置１０について説明する。なお、各実施形態の説明において、それまでに説明した装置、ブロックまたは回路等と、略同一の機能および構成を有する装置、ブロックまたは回路には同一の符号を付けて、相違点を除き詳細な説明を省略する。
【００３９】
図１は、第１実施形態に係る計算装置１０の構成を示す図である。計算装置１０は、式（７）および式（８）に示した連立常微分方程式、または、式（９）および式（１０）に示した連立常微分方程式を用いて、イジングモデルを用いた最適化問題を解く装置である。
【００４０】
計算装置１０は、演算部２０と、入力部２２と、出力部２４と、設定部２６とを備える。
【００４１】
演算部２０は、例えば１または複数のＣＰＵ（Central  Processing  Unit）等のプロセッサおよびメモリを備える演算処理装置である。また、演算部２０は、第２実施形態以降の回路であってもよい。
【００４２】
演算部２０は、サンプリング時刻を表すパラメータであるｔを開始時刻（例えば０）から微小時間（ｄｔ）ずつ増加させる。演算部２０は、それぞれのサンプリング時刻毎に、式（６）および式（７）に示した連立常微分方程式、または、式（９）および式（１０）に示した連立常微分方程式を用いて、Ｎ個の第１変数ｘｉおよびＮ個の第２変数ｙｉを更新する。そして、演算部２０は、予め定められたサンプリング時刻である終了時刻ＴにおけるＮ個の第１変数ｘｉを出力する。
【００４３】
入力部２２は、演算部２０による演算処理に先だって、開始時刻におけるＮ個の第１変数ｘｉおよびＮ個の第２変数ｙｉを取得して、演算部２０に与える。開始時刻におけるＮ個の第１変数ｘｉおよびＮ個の第２変数ｙｉは、例えば、乱数により発生された値であってもよいし、予め設定された値（例えば、全て０または全て所定値）であってもよい。
【００４４】
出力部２４は、演算部２０による演算処理の終了後に、終了時刻ＴにおけるＮ個の第１変数ｘｉを取得する。そして、出力部２４は、終了時刻ＴにおけるＮ個の第１変数ｘｉの符号を表す値（例えば、＋１，−１）を、イジングモデルにおけるＮ個のスピンの状態の組み合わせの最適解として出力する。
【００４５】
設定部２６は、演算部２０による演算処理に先だって、式（６）および式（７）に示した連立常微分方程式、および、式（９）および式（１０）に示した連立常微分方程式に用いられる各パラメータを演算部２０に対して設定する。より具体的には、設定部２６は、Ｎ、Ｊ、ｈ、Ｄ、ｃ、Ｋ、ｐ（ｔ）およびａ（ｔ）を設定する。
【００４６】
Ｎは、第１変数および第２変数の数を表す２以上の整数である。
Ｊは、Ｎ行×Ｎ列の係数行列である。Ｊｉ，ｊは、係数行列Ｊに含まれるｉ行、ｊ列の係数である。
ｈは、Ｎ個の係数を含む係数配列である。ｈｉは、係数配列ｈにおけるｉ番目の係数である。
Ｄ、ｃ、Ｋは、定数である。
ｐ（ｔ）は、サンプリング時刻を変数とする関数である。
ａ（ｔ）は、サンプリング時刻を変数とする関数である。
【００４７】
さらに、設定部２６は、ｄｔ、ＴおよびＭを設定してもよい。
ｄｔは、サンプリング期間（微小時間）を表す定数である。
Ｔは、終了時刻に相当するサンプリング時刻を表す定数である。
Ｍは、式（６）および式（７）の演算の繰り返し数、または、式（９）および式（１０）の演算の繰り返し数を表す１以上の整数である。
【００４８】
なお、設定部２６は、これらのパラメータのうち一部を、ユーザ操作に応じて任意に変更してもよい。また、設定部２６は、これらのパラメータを演算毎に変更せずに固定した値としてもよい。
【００４９】
図２は、演算部２０の処理の流れを示すフローチャートである。
【００５０】
まず、Ｓ１１において、演算部２０は、ｔ、ｐおよびａを初期化する。例えば、演算部２０は、ｔ、ｐおよびａを全て０にする。ｔは、サンプリング時刻を表すパラメータである。ｐは、時刻ｔにおけるｐ（ｔ）の値を表すパラメータである。ａは、時刻ｔにおけるａ（ｔ）の値を表すパラメータである。
【００５１】
続いて、演算部２０は、ｔが予め設定された終了時刻Ｔ以上となるまでＳ１３からＳ２０までの処理を繰り返す（Ｓ１２とＳ２１との間のループ処理）。なお、ａ（ｔ）が増加関数である場合、演算部２０は、ａが予め定められた値以上となるまで、Ｓ１３からＳ２０までの間の処理を繰り返してもよい。
【００５２】
Ｓ１３において、演算部２０は、Ｎ個の第１変数ｘｉのそれぞれに、サンプリング期間（微小時間）ｄｔと、予め設定された係数ｃとを乗じることにより、Ｎ個の第１中間変数ｘｉ´を算出する。すなわち、Ｓ１３において、演算部２０は、下記の式（２１）の演算を実行する。
ｘｉ´＝ｄｔ×ｃ×ｘｉ…（２１）
【００５３】
続いて、Ｓ１４において、演算部２０は、Ｎ個の第１中間変数ｘｉ´と、予め設定されたＮ行×Ｎ列の係数を含む係数行列Ｊとを行列乗算することにより、Ｎ個の第２中間変数ｂｉを算出する。すなわち、Ｓ１４において、演算部２０は、下記の式（２２）の演算を実行する。
【数１１】
2020046887.tif 000013
【００５４】
なお、演算部２０は、Ｓ１４の処理を実行した後、Ｓ１３の処理を実行してもよい。この場合、Ｓ１４において、演算部２０は、Ｎ個の第１変数ｘｉと係数行列Ｊとを行列乗算することにより、Ｎ個の値を算出する。続いて、Ｓ１３において、演算部２０は、Ｓ１４で算出したＮ個の値のそれぞれに、（ｄｔ×ｃ）を乗じることにより、Ｎ個の第２中間変数ｂｉを算出する。
【００５５】
続いて、Ｓ１５において、演算部２０は、Ｎ個の第２変数ｙｉのそれぞれに、対応する第２中間変数ｂｉを加算することにより、Ｎ個の第２変数ｙｉを更新する。すなわち、Ｓ１５において、演算部２０は、下記の式（２３）の演算を実行する。
ｙｉ＋＝ｂｉ…（２３）
【００５６】
続いて、演算部２０は、Ｓ１７からＳ１８までの処理を、Ｍ回繰り返して実行する（Ｓ１６とＳ１９との間のループ処理）。なお、Ｍは、１以上の整数である。
【００５７】
Ｓ１７において、演算部２０は、式（７）または式（１０）に従った演算を実行することにより、第２変数ｙｉを更新する。例えば、Ｓ１７において、演算部２０は、式（７）に従った演算を実行する場合、下記の式（２４）の演算を実行する。
ｙｉ＋＝ｄｔ´×［（−Ｄ＋ｐ−Ｋｘｉ２）ｘｉ−ｃ×ｈｉ×ａ］…（２４）
【００５８】
また、例えば、Ｓ１７において、演算部２０は、式（１０）に従った演算を実行する場合、下記の式（２５）の演算を実行する。なお、式（２５）において、ｎは、２以上の偶数である。
ｙｉ＋＝ｄｔ´×｛［（−Ｄ＋ｐ）（１＋ｘｉｎ）−Ｋｘｉｎ＋２］ｘｉ−ｃ×ｈｉ×ａ｝…（２５）
【００５９】
続いて、Ｓ１８において、演算部２０は、式（６）または式（９）に従った演算を実行することにより、第１変数ｘｉを更新する。なお、式（６）および式（９）は、同一の式である。例えば、Ｓ１８において、演算部２０は、式（６）または式（９）に従った演算を実行する場合、下記の式（２６）の演算を実行する。
ｘｉ＋＝ｄｔ´×Ｄ×ｙｉ…（２６）
【００６０】
Ｓ１６からＳ１９までのループ処理は、シンプレクティック・オイラー法における繰り返し演算に対応する。なお、演算部２０は、Ｓ１７の処理とＳ１８の処理を逆に実行してもよい。すなわち、演算部２０は、第１変数ｘｉを更新した後に、第２変数ｙｉを更新してもよい。
【００６１】
Ｓ１６からＳ１９までのループ処理を実行した後、演算部２０は、処理をＳ２０に進める。Ｓ２０において、演算部２０は、ｔにｄｔを加算することにより、ｔを更新する。さらに、演算部２０は、ｐおよびａを更新する。例えば、演算部２０は、ｐに、予め設定されたｄｐを加算することにより、ｐを更新する。また、演算部２０は、更新後のｐの平方根を演算することにより、ａを更新する。
【００６２】
Ｓ２０の処理を実行した後、演算部２０は、ｔがＴ以上となったか否かを判断する。演算部２０は、ｔがＴより小さい場合には、処理をＳ１３に戻して、Ｓ１３から処理を繰り返す。ｔがＴ以上となった場合には、演算部２０は、本フローを終了する。
【００６３】
以上のような処理を実行することにより、第１実施形態に係る計算装置１０は、式（６）および式（７）に示す連立常微分方程式、または、式（９）および式（１０）に示す連立常微分方程式を用いて、最適化問題を解くことができる。第１実施形態に係る計算装置１０によれば、第１変数ｘｉおよび第２変数ｙｉを簡単な演算または簡単な構成で、高速に更新することができる。従って、第１実施形態に係る計算装置１０によれば、小さいコストで、高速に最適化問題の最適解を算出することができる。
【００６４】
（第２実施形態）
第２実施形態に係る計算装置１０について説明する。
【００６５】
図３は、第２実施形態に係る演算部２０の構成を示す図である。第２実施形態において、計算装置１０は、１または複数の半導体装置により実現された回路である。計算装置１０は、例えば、ＦＰＧＡ（Field  Programmable  Gate  Array）、ゲートアレイまたは特定用途向け集積回路（ＡＳＩＣ）等であってもよい。また、計算装置１０は、一部にプロセッサを含んでもよい。
【００６６】
第２実施形態に係る演算部２０は、行列乗算部２８と、時間発展部３０と、管理部３２とを備える。
【００６７】
行列乗算部２８は、任意のサンプリング時刻を表す第１時刻ｔ１におけるＮ個の第１中間変数ｘｉ´（ｔ１）を時間発展部３０から取得する。行列乗算部２８は、第１時刻ｔ１におけるＮ個の第１中間変数ｘｉ´（ｔ１）と、係数行列Ｊとを行列乗算することにより、第１時刻ｔ１におけるＮ個の第２中間変数ｂｉ（ｔ１）を算出する。
【００６８】
例えば、行列乗算部２８は、係数行列メモリ３６と、行列乗算実行部３８とを有する。係数行列メモリ３６は、係数行列Ｊを記憶する。行列乗算実行部３８は、第１時刻ｔ１におけるＮ個の第１中間変数ｘｉ´（ｔ１）と、係数行列Ｊとを行列乗算する。
【００６９】
時間発展部３０は、第１時刻ｔ１におけるＮ個の第２中間変数ｂｉ（ｔ１）を行列乗算部２８から取得する。時間発展部３０は、第１時刻ｔ１におけるＮ個の第２中間変数ｂｉ（ｔ１）に基づき、第１時刻ｔ１から１サンプリング期間後のサンプリング時刻を表す第２時刻ｔ２におけるＮ個の第１変数ｘｉ（ｔ２）、第２時刻ｔ２におけるＮ個の第２変数ｙｉ（ｔ２）および第２時刻ｔ２におけるＮ個の第１中間変数ｘｉ´（ｔ２）を算出する。
【００７０】
管理部３２は、開始時刻からサンプリング期間毎にサンプリング時刻を増加させる。そして、管理部３２は、それぞれのサンプリング時刻に対する処理を、行列乗算部２８および時間発展部３０に実行させる。
【００７１】
すなわち、管理部３２は、例えば、行列乗算部２８に、第１時刻ｔ１におけるＮ個の第２中間変数ｂｉ（ｔ１）を算出させる。続いて、管理部３２は、時間発展部３０に、第２時刻ｔ２におけるＮ個の第１変数ｘｉ（ｔ２）、Ｎ個の第２変数ｙｉ（ｔ２）およびＮ個の第１中間変数ｘｉ´（ｔ２）を算出させる。続いて、管理部３２は、行列乗算部２８に、第２時刻ｔ２におけるＮ個の第２中間変数ｂｉ（ｔ２）を算出させる。続いて、管理部３２は、時間発展部３０に、第２時刻ｔ２から１サンプリング期間後のサンプリング時刻を表す第３時刻ｔ３におけるＮ個の第１変数ｘｉ（ｔ３）、Ｎ個の第２変数ｙｉ（ｔ３）およびＮ個の第１中間変数ｘｉ´（ｔ３）を算出させる。このように、管理部３２は、サンプリング時刻を増加させながら、行列乗算部２８および時間発展部３０に交互に処理を実行させる。
【００７２】
なお、開始時刻（例えば、ｔ０）におけるＮ個の第１変数ｘｉ（ｔ０）およびＮ個の第２変数ｙｉ（ｔ０）は、例えば、演算処理に先だって、入力部２２により予め与えられる。
【００７３】
例えば、時間発展部３０は、第１変数メモリ４０と、第２変数メモリ４２と、第１加算部４４と、関数演算部４６と、第１乗算部４８と、第１中間変数メモリ５０とを有する。
【００７４】
第１変数メモリ４０は、第１時刻ｔ１におけるＮ個の第１変数ｘｉ（ｔ１）を記憶する。第２変数メモリ４２は、第１時刻ｔ１におけるＮ個の第２変数ｙｉ（ｔ１）を記憶する。
【００７５】
第１加算部４４は、行列乗算部２８が算出した第１時刻ｔ１におけるＮ個の第２中間変数ｂｉ（ｔ１）を取得する。第１加算部４４は、第２変数メモリ４２に記憶された第１時刻ｔ１におけるＮ個の第２変数ｙｉ（ｔ１）に、第１時刻ｔ１におけるＮ個の第２中間変数ｂｉ（ｔ１）を加算することにより、第１時刻ｔ１におけるＮ個の第２変数ｙｉ（ｔ１）を更新する。例えば、第１加算部４４は、先頭のインデックス（ｉ＝０）の第２変数ｙ０（ｔ１）から、最後のインデックス（ｉ＝Ｎ−１）の第２変数ｙＮ−１（ｔ１）まで、インデックス順に、Ｎ個の第２変数ｙｉ（ｔ１）を更新する。
【００７６】
なお、実施形態において、Ｎ個の第１値とＮ個の第２値とを加算するとは、同一のインデックスの値同士を加算することにより、Ｎ個の第３値を生成することをいう。
【００７７】
関数演算部４６は、第１変数メモリ４０に記憶された第１時刻ｔ１におけるＮ個の第１変数ｘｉ（ｔ１）、および、第１加算部４４が算出した第１時刻ｔ１における更新されたＮ個の第２変数ｙｉ（ｔ１）に基づき、第２時刻ｔ２におけるＮ個の第１変数ｘｉ（ｔ２）および第２時刻ｔ２におけるＮ個の第２変数ｙｉ（ｔ２）を算出する。例えば、関数演算部４６は、先頭のインデックス（ｉ＝０）の第１変数ｘ０（ｔ２）および第２変数ｙ０（ｔ２）から、最後のインデックス（ｉ＝Ｎ−１）の第１変数ｘＮ−１（ｔ２）および第２変数ｙＮ−１（ｔ２）まで、インデックス順に、Ｎ個の第１変数ｘｉ（ｔ２）およびＮ個の第２変数ｙｉ（ｔ２）を算出する。
【００７８】
関数演算部４６は、第２時刻ｔ２におけるＮ個の第１変数ｘｉ（ｔ２）を第１変数メモリ４０に書き込む。例えば、関数演算部４６は、第２時刻ｔ２におけるＮ個の第１変数ｘｉ（ｔ２）のそれぞれを、先頭のインデックス（ｉ＝０）の第１変数ｘ０（ｔ２）から順次に第１変数メモリ４０に書き込む。第１変数メモリ４０は、例えば、デュアルポートメモリであり、あるアドレスのデータの読み出しをしながら、他のアドレスにデータを書き込むことができる。第１変数メモリ４０がデュアルポートメモリである場合、関数演算部４６は、第２時刻ｔ２におけるＮ個の第１変数ｘｉ（ｔ２）を、第１時刻ｔ１におけるＮ個の第１変数ｘｉ（ｔ１）が記憶されていたアドレスに上書きすることができる。
【００７９】
関数演算部４６は、第２時刻ｔ２におけるＮ個の第２変数ｙｉ（ｔ２）を第２変数メモリ４２に書き込む。例えば、関数演算部４６は、第２時刻ｔ２におけるＮ個の第２変数ｙｉ（ｔ２）のそれぞれを、先頭のインデックスの第２変数ｙ０（ｔ２）から順次に第２変数メモリ４２に書き込む。第２変数メモリ４２は、例えば、デュアルポートメモリである。第２変数メモリ４２がデュアルポートメモリである場合、関数演算部４６は、第２時刻ｔ２におけるＮ個の第２変数ｙｉ（ｔ２）を、第１時刻ｔ１におけるＮ個の第２変数ｙｉ（ｔ１）が記憶されていたアドレスに上書きすることができる。
【００８０】
第１乗算部４８は、第２時刻ｔ２におけるＮ個の第１変数ｘｉ（ｔ２）のそれぞれに、予め設定された値（本実施形態においては、（ｄｔ×ｃ））を乗じることにより、第２時刻ｔ２におけるＮ個の第１中間変数ｘｉ´（ｔ２）を算出する。第１中間変数メモリ５０は、第１乗算部４８が算出した第２時刻ｔ２におけるＮ個の第１中間変数ｘｉ´（ｔ２）を記憶する。なお、第２時刻ｔ２におけるＮ個の第１中間変数ｘｉ´（ｔ２）は、第１中間変数メモリ５０に一時的に記憶された後に、行列乗算部２８に送信される。第１中間変数メモリ５０は、第２時刻ｔ２におけるＮ個の第１中間変数ｘｉ´（ｔ２）のそれぞれを、第１乗算部４８により生成されてから、行列乗算部２８へと送信されるまでの期間保持する。第１中間変数メモリ５０は、例えば、ＦＩＦＯ（First  IN  First  Out）メモリを含んでいてもよい。
【００８１】
このような構成において、行列乗算部２８は、第１実施形態において説明したＳ１４の処理を実行する。また、第１加算部４４は、Ｓ１５の処理を実行する。関数演算部４６は、Ｓ１６からＳ１９までの処理を実行する。また、第１乗算部４８は、Ｓ１３の処理を実行する。また、管理部３２は、Ｓ１１、Ｓ２０、および、Ｓ１２とＳ２１との間のループ処理の管理を実行する。従って、第２実施形態に係る演算部２０によれば、第１実施形態と同様に、小さいコストで高速に最適化問題の最適解を算出することができる。
【００８２】
なお、第１乗算部４８は、第１中間変数メモリ５０の前段に代えて、第１加算部４４の前段に設けられてもよい。この配置の変更は、第１実施形態のＳ１３とＳ１４との処理を逆にした処理に対応する。ただし、第２時刻ｔ２におけるＮ個の第１変数ｘｉ（ｔ２）のそれぞれに乗算する値（本実施形態においては（ｄｔ×ｃ））が１より小さい場合には、第１乗算部４８は、第１中間変数メモリ５０の前段に設けられている方がよい。これにより、第１乗算部４８は、第２時刻ｔ２におけるＮ個の第１中間変数ｘｉ´（ｔ２）の桁数を小さくして、行列乗算部２８でのオーバフローの確率を少なくすることができる。
【００８３】
第１乗算部４８が第１加算部４４の前段に設けられた場合、第１中間変数メモリ５０は、第２時刻ｔ２におけるＮ個の第１変数ｘｉ（ｔ２）を、第２時刻ｔ２におけるＮ個の第１中間変数ｘｉ´（ｔ２）として記憶する。また、この場合、第１乗算部４８は、行列乗算部２８から出力された第１時刻ｔ１におけるＮ個の第２中間変数ｂｉ（ｔ１）のそれぞれに、予め設定された値（ｄｔ×ｃ）を乗じる。そして、この場合、第１加算部４４は、第１時刻ｔ１におけるＮ個の第２変数ｙｉ（ｔ１）に、第１乗算部４８が予め設定された値（ｄｔ×ｃ）を乗じた第１時刻ｔ１におけるＮ個の第２中間変数ｂｉ（ｔ１）を加算することにより、第１時刻ｔ１におけるＮ個の第２変数ｙｉ（ｔ１）を更新する。
【００８４】
また、時間発展部３０は、第１時刻ｔ１におけるＮ個の第１中間変数ｘｉ´（ｔ１）を、１クロックサイクルに第１数（第１数は１以上の整数）の第１中間変数ｘｉ´（ｔ１）を含む第１中間ストリームＸ´として行列乗算部２８へと出力してもよい。また、行列乗算部２８は、第１時刻ｔ１におけるＮ個の第２中間変数ｂｉ（ｔ１）を、１クロックサイクルに第２数（第２数は１以上の整数）の第２中間変数ｂｉ（ｔ１）を含む第２中間ストリームＢとして時間発展部３０へと出力してもよい。
【００８５】
ここで、ストリームとは、時系列データをいう。より具体的には、ストリームとは、Ｎ個のデータを例えばＰ個（Ｐは１以上の整数）ずつのデータセットに分割し、１クロックサイクル毎に、Ｐ個のデータセットを含むデータ列をいう。
【００８６】
行列乗算部２８および時間発展部３０は、このようなストリームを取得した場合、先に取得したデータセットから順に処理を実行する。これにより、行列乗算部２８および時間発展部３０は、ストリームに含まれる全てのデータの取得が完了する前に、処理を開始することができる。また、行列乗算部２８および時間発展部３０は、Ｎ個のデータの先頭のデータセットの算出が完了した場合、算出が完了したデータセットから順次に送信を開始する。これにより、行列乗算部２８および時間発展部３０は、全てのデータの算出が完了する前に、次のユニットに処理を開始させることができる。
【００８７】
図４は、第２実施形態でのＮ個の第１中間変数ｘｉ´、係数行列ＪおよびＮ個の第２中間変数ｂｉの関係を示す図である。行列乗算部２８は、サンプリング時刻毎に、Ｎ個の第１中間変数（ｘ０´，ｘ１´，ｘ２´，…，ｘｉ´，…，ｘＮ−１´）を取得する。また、行列乗算部２８は、Ｎ行×Ｎ列の係数を含む係数行列（Ｊ０，０，Ｊ０，１，Ｊ０，２，…，Ｊｉ，ｊ，…，ＪＮ−１，Ｎ−１）を記憶する。
【００８８】
そして、行列乗算部２８は、Ｎ個の第１中間変数（ｘ０´，ｘ１´，ｘ２´，…，ｘｉ´，…，ｘＮ−１´）と、係数行列（Ｊ０，０，Ｊ０，１，Ｊ０，２，…，Ｊｉ，ｊ，…，ＪＮ−１，Ｎ−１）とを行列乗算することにより、Ｎ個の第２中間変数（ｂ０，ｂ１，ｂ２，…，ｂｉ，…，ｂＮ−１）を算出する。
【００８９】
第２実施形態において、行列乗算部２８は、どのような処理により行列乗算を実行してもよい。また、第２実施形態において、行列乗算部２８は、例えば内部にプロセッサ等を含み、プログラムにより行列乗算を実行してもよい。
【００９０】
図５は、関数演算部４６の構成の第１例を示す図である。第１例に係る関数演算部４６は、第１のＦＸ演算部５１−１と、第１のＦＸ加算部５２−１と、第１のＦＹ演算部５３−１と、第１のＦＹ加算部５４−１とを有する。
【００９１】
第１のＦＸ演算部５１−１は、第１時刻におけるＮ個の第１変数のそれぞれに対して、第１関数演算（ＦＸ（ｘｉ））をすることにより、Ｎ個の第２微分値を算出する。第１のＦＸ加算部５２−１は、第１のＦＸ演算部５１−１が算出したＮ個の第２微分値と、第１加算部４４が算出したＮ個の更新された第２変数とを加算することにより、Ｎ個の第２更新値を算出する。
【００９２】
第１のＦＹ演算部５３−１は、第１のＦＸ加算部５２−１が算出したＮ個の第２更新値のそれぞれに対して第２関数演算（ＦＹ（ｙｉ））をすることにより、Ｎ個の第１微分値を算出する。第１のＦＹ加算部５４−１は、第１のＦＹ演算部５３−１が算出したＮ個の第１微分値と第１時刻におけるＮ個の第１変数とを加算することにより、Ｎ個の第１更新値を算出する。
【００９３】
そして、関数演算部４６は、第１のＦＹ加算部５４−１が算出したＮ個の第１更新値を第１変数メモリ４０に与える。第１変数メモリ４０は、第１のＦＹ加算部５４−１が算出したＮ個の第１更新値を、第２時刻におけるＮ個の第１変数として記憶する。
【００９４】
また、関数演算部４６は、第１のＦＸ加算部５２−１が算出したＮ個の第２更新値を第２変数メモリ４２に与える。第２変数メモリ４２は、第１のＦＸ加算部５２−１が算出したＮ個の第２更新値を、第２時刻におけるＮ個の第２変数として記憶する。
【００９５】
ここで、第１関数演算は、下記の式（３１）の演算である。
ＦＸ（ｘｉ）＝ｄｔ´×［（−Ｄ＋ｐ−Ｋｘｉ２）ｘｉ−ｃ×ｈｉ×ａ］…（３１）
【００９６】
また、第２関数は、下記の式（３２）の演算である。
ＦＹ（ｙｉ）＝ｄｔ´×Ｄ×ｙｉ…（３２）
【００９７】
また、第１関数演算は、下記の式（３３）の演算であってもよい。
ＦＸ（ｘｉ）＝ｄｔ´×｛［（−Ｄ＋ｐ）（１＋ｘｉｎ）−Ｋｘｉｎ＋２］ｘｉ−ｃ×ｈｉ×ａ｝…（３３）
【００９８】
式（３１）、（３２）および（３３）において、ｘｉは、第１時刻におけるＮ個の第１変数のうちのｉ番目の第１変数、または、Ｎ個の第１更新値のうちのｉ番目の第１更新値である。ｙｉは、第１加算部４４が算出した更新されたＮ個の第２変数のうちのｉ番目の第２変数、または、Ｎ個の第２更新値のうちのｉ番目の第２更新値である。
【００９９】
ｄｔ´は、予め設定された微小時間である。Ｄ、ｃ、Ｋは、予め設定された定数である。ｈｉは、ｉ毎に設定された係数である。ｐおよびａは、予め定められた演算式に従ってサンプリング時刻毎に増加する値である。
【０１００】
このような第１例の構成の関数演算部４６は、第１実施形態におけるＳ１６からＳ１９までのループ処理を、Ｓ１７→Ｓ１８の順で、１回実行することができる。これにより、関数演算部４６によれば、シンプレクティック・オイラー法と呼ばれる方法を用いて、第１時刻におけるＮ個の第１変数およびＮ個の第２変数を時間発展させて、第２時刻におけるＮ個の第１変数およびＮ個の第２変数を算出することができる。
【０１０１】
さらに、第１例に係る関数演算部４６は、パイプライン処理により演算を実現してもよい。パイプライン処理を実行する場合、例えば、関数演算部４６は、第１変数ＸＩＮおよび第２変数ＹＩＮを含む１つの変数ペアを、クロックサイクル毎にインデックス順に受け取る。そして、関数演算部４６は、受け取った変数ペアに対して演算を実行することにより、演算処理後の第１変数ＸＯＵＴおよび第２変数ＹＯＵＴを含む１つの変数ペアを算出する。
【０１０２】
具体的には、パイプライン処理を実行する場合、関数演算部４６は、２段のＸ転送レジスタ５５−１〜５５−２と、２段のＹ転送レジスタ５６−１〜５６−２と、１つのＸ出力レジスタ５７と、１つのＹ出力レジスタ５８とを、さらに有する。
【０１０３】
１段目のＸ転送レジスタ５５−１は、クロックサイクル毎に、第１変数メモリ４０から、第１時刻におけるＮ個の第１変数の中から１つの第１変数ＸＩＮを取得し、取得した１つの第１変数ＸＩＮを、１クロックサイクル期間保持する。１段目のＹ転送レジスタ５６−１は、クロックサイクル毎に、第１加算部４４が算出した更新されたＮ個の第２変数の中から、１つの第２変数ＹＩＮを取得し、取得した１つの第２変数ＹＩＮを、１クロックサイクル期間保持する。なお、１段目のＸ転送レジスタ５５−１および１段目のＹ転送レジスタ５６−１は、同一のクロックサイクルにおいて、同一のインデックスｉの１つの第１変数および１つの第２変数を取得する。
【０１０４】
第１のＦＸ演算部５１−１は、クロックサイクル毎に、１段目のＸ転送レジスタ５５−１に格納された第１変数ＸＩＮに対して、第１関数演算を実行することにより、第２微分値を算出する。第１のＦＸ加算部５２−１は、クロックサイクル毎に、第１のＦＸ演算部５１−１が当該クロックサイクルにおいて算出した第２微分値と、１段目のＹ転送レジスタ５６−１に格納された第２変数ＹＩＮとを加算することにより、第２更新値Ｙ１を算出する。
【０１０５】
２段目のＸ転送レジスタ５５−２は、クロックサイクル毎に、直前のクロックサイクルにおいて１段目のＸ転送レジスタ５５−１が保持していた第１変数ＸＩＮを取得し、取得した第１変数ＸＩＮを、１クロックサイクル期間保持する。２段目のＹ転送レジスタ５６−２は、クロックサイクル毎に、第１のＦＸ加算部５２−１が直前のクロックサイクルにおいて算出した第２更新値Ｙ１を取得し、取得した第２更新値Ｙ１を１クロックサイクル期間保持する。
【０１０６】
第１のＦＹ演算部５３−１は、クロックサイクル毎に、２段目のＹ転送レジスタ５６−２に格納された第２更新値Ｙ１に対して、第２関数演算を実行することにより、第１微分値を算出する。第１のＦＹ加算部５４−１は、クロックサイクル毎に、第１のＦＹ演算部５３−１が当該クロックサイクルにおいて算出した第１微分値と、２段目のＸ転送レジスタ５５−２に格納された第１変数ＸＩＮとを加算することにより、第１更新値Ｘ１を算出する。
【０１０７】
Ｘ出力レジスタ５７は、クロックサイクル毎に、第１のＦＹ加算部５４−１が直前のクロックサイクルにおいて算出した第１更新値Ｘ１を取得し、取得した第１更新値Ｘ１を第２時刻における１つの第１変数ＸＯＵＴとして第１変数メモリ４０に記憶させる。
【０１０８】
Ｙ出力レジスタ５８は、クロックサイクル毎に、第２段目のＹ転送レジスタ５６−２に格納された第２更新値Ｙ１を取得し、取得した第２更新値Ｙ１を第２時刻における１つの第２変数ＹＯＵＴとして第２変数メモリ４２に記憶させる。
【０１０９】
このようなパイプライン処理を実行することにより、第１例に係る関数演算部４６は、クロックサイクル毎に、下記のような演算を実行することができる。
【０１１０】
Ｙ１＝ＦＸ（ＸＩＮ）＋ＹＩＮ
Ｘ１＝ＦＹ（Ｙ１）＋ＸＩＮ
ＹＯＵＴ＝Ｙ１
ＸＯＵＴ＝Ｘ１
【０１１１】
このような第１例に係る関数演算部４６は、同一のインデックスｉの１つの第１変数ＸＩＮおよび１つの第２変数ＹＩＮを含む変数ペアに対して、第１関数演算→ＦＸ加算→第２関数演算→ＦＹ加算の一連の演算セットを、１回実行することができる。さらに、第１例に係る関数演算部４６は、パイプライン処理を実行するので、複数の変数ペアに対して並列して演算を実行することができる。これにより、第１例に係る関数演算部４６は、Ｎ個の変数ペアに対する演算を、短時間で完了させることができる。
【０１１２】
図６は、関数演算部４６の構成の第２例を示す図である。関数演算部４６は、図６に示すような、第２例の構成であってもよい。第２例に係る関数演算部４６は、第１例と同一の構成要素を有するが、各構成要素の配置が異なる。第２例を説明するに当たり、第１例と同一の動作をする構成要素については、同一の符号を付けて相違点を除き詳細な説明を省略する。
【０１１３】
第１のＦＹ演算部５３−１は、第１加算部４４が算出した更新されたＮ個の第２変数のそれぞれに対して第２関数演算（ＦＹ（ｙｉ））をすることにより、Ｎ個の第１微分値を算出する。第１のＦＹ加算部５４−１は、第１のＦＹ演算部５３−１が算出したＮ個の第１微分値と第１時刻におけるＮ個の第１変数とを加算することにより、Ｎ個の第１更新値を算出する。
【０１１４】
第１のＦＸ演算部５１−１は、第１のＦＹ加算部５４−１が算出したＮ個の第１更新値のそれぞれに対して、第１関数演算（ＦＸ（ｘｉ））をすることにより、Ｎ個の第２微分値を算出する。第１のＦＸ加算部５２−１は、第１のＦＸ演算部５１−１が算出したＮ個の第２微分値と、第１加算部４４が算出した更新されたＮ個の第２変数とを加算することにより、Ｎ個の第２更新値を算出する。
【０１１５】
このような第２例の構成の関数演算部４６は、第１実施形態におけるＳ１６からＳ１９までのループ処理を、Ｓ１８→Ｓ１７の順で、１回実行することができる。これにより、関数演算部４６によれば、シンプレクティック・オイラー法と呼ばれる方法を用いて、第１時刻におけるＮ個の第１変数およびＮ個の第２変数を時間発展させて、第２時刻におけるＮ個の第１変数およびＮ個の第２変数を算出することができる。
【０１１６】
さらに、第２例に係る関数演算部４６は、パイプライン処理により演算を実現してもよい。この場合も、第２例に係る関数演算部４６は、第１例と同一の構成要素を有するが、各構成要素の配置が異なる。
【０１１７】
第１のＦＹ演算部５３−１は、クロックサイクル毎に、１段目のＹ転送レジスタ５６−１に格納された、更新された第２変数ＹＩＮに対して、第２関数演算を実行することにより、第１微分値を算出する。第１のＦＹ加算部５４−１は、クロックサイクル毎に、第１のＦＹ演算部５３−１が当該クロックサイクルにおいて算出した第１微分値と、１段目のＸ転送レジスタ５５−１に格納された第１変数ＸＩＮとを加算することにより、第１更新値Ｘ１を算出する。
【０１１８】
２段目のＸ転送レジスタ５５−２は、クロックサイクル毎に、第１のＦＹ加算部５４−１が直前のクロックサイクルにおいて算出した第１更新値Ｘ１を取得し、取得した第１更新値Ｘ１を１クロックサイクル期間保持する。２段目のＹ転送レジスタ５６−２は、クロックサイクル毎に、直前のクロックサイクルにおいて１段目のＹ転送レジスタ５６−１が保持していた第２変数ＹＩＮを取得し、取得した第２変数ＹＩＮを、１クロックサイクル期間保持する。
【０１１９】
第１のＦＸ演算部５１−１は、クロックサイクル毎に、２段目のＸ転送レジスタ５５−２に格納された第１更新値Ｘ１に対して、第１関数演算を実行することにより、第２微分値を算出する。第１のＦＸ加算部５２−１は、クロックサイクル毎に、第１のＦＸ演算部５１−１が当該クロックサイクルにおいて算出した第１微分値と、２段目のＹ転送レジスタ５６−２に格納された第２変数ＹＩＮとを加算することにより、第２更新値Ｙ１を算出する。
【０１２０】
このようなパイプライン処理を実行することにより、第２例に係る関数演算部４６は、クロックサイクル毎に、下記のような演算を実行することができる。
【０１２１】
Ｘ１＝ＦＹ（ＹＩＮ）＋ＸＩＮ
Ｙ１＝ＦＸ（Ｘ１）＋ＹＩＮ
ＸＯＵＴ＝Ｘ１
ＹＯＵＴ＝Ｙ１
【０１２２】
このような第２例に係る関数演算部４６は、同一のインデックスｉの１つの第１変数ＸＩＮおよび１つの第２変数ＹＩＮを含む変数ペアに対して、第２関数演算→ＦＹ加算→第１関数演算→ＦＸ加算の一連の演算セットを、１回実行することができる。さらに、第２例に係る関数演算部４６は、パイプライン処理を実行するので、複数の変数ペアに対して並列して演算を実行することができる。これにより、第２例に係る関数演算部４６は、Ｎ個の変数ペアに対する演算を、短時間で完了させることができる。
【０１２３】
図７は、関数演算部４６の構成の第３例を示す図である。関数演算部４６は、図７に示すような、第３例の構成であってもよい。第３例に係る関数演算部４６は、第１例と略同一の構成を有する。第３例を説明するに当たり、第１例と同一の動作をする構成要素については、同一の符号を付けて相違点を除き詳細な説明を省略する。
【０１２４】
第３例に係る関数演算部４６は、第１例の構成に加えて、第２から第Ｍ（Ｍは２以上の整数）までの（Ｍ−１）個のＦＸ演算部５１−２〜５１−Ｍと、第２から第Ｍまでの（Ｍ−１）個のＦＸ加算部５２−２〜５２−Ｍと、第２から第Ｍまでの（Ｍ−１）個のＦＹ演算部５３−２〜５３−Ｍと、第２から第Ｍまでの（Ｍ−１）個のＦＹ加算部５４−２〜５４−Ｍと、をさらに有する。
【０１２５】
第ｍのＦＸ演算部５１−ｍ（ｍは、２からＭまでの任意の整数）は、第（ｍ−１）のＦＹ加算部５４−（ｍ−１）が算出したＮ個の第１更新値のそれぞれに対して第１関数演算をすることにより、Ｎ個の第２微分値を算出する。第ｍのＦＸ加算部５２−ｍは、第ｍのＦＸ演算部５１−ｍが算出したＮ個の第２微分値と第（ｍ−１）のＦＸ加算部５２−（ｍ−１）が算出したＮ個の第２更新値とを加算することにより、新たなＮ個の第２更新値を算出する。
【０１２６】
第ｍのＦＹ演算部５３−ｍは、第ｍのＦＸ加算部５２−ｍが算出したＮ個の第２更新値のそれぞれに対して第２関数演算をすることにより、Ｎ個の第１微分値を算出する。第ｍのＦＹ加算部５４−ｍは、第ｍのＦＹ演算部５３−ｍが算出したＮ個の第１微分値と第（ｍ−１）のＦＹ加算部５４−（ｍ−１）が算出したＮ個の第１更新値とを加算することにより、新たなＮ個の第１更新値を算出する。
【０１２７】
そして、関数演算部４６は、第ＭのＦＹ加算部５４−Ｍが算出したＮ個の第１更新値を第１変数メモリ４０に与える。第１変数メモリ４０は、第ＭのＦＹ加算部５４−Ｍが算出したＮ個の第１更新値を、第２時刻におけるＮ個の第１変数として記憶する。
【０１２８】
また、関数演算部４６は、第ＭのＦＸ加算部５２−Ｍが算出したＮ個の第２更新値を第２変数メモリ４２に与える。第２変数メモリ４２は、第ＭのＦＸ加算部５２−Ｍが算出したＮ個の第２更新値を、第２時刻におけるＮ個の第２変数として記憶する。
【０１２９】
このような第３例の構成の関数演算部４６は、第１実施形態におけるＳ１６からＳ１９までのループ処理を、Ｓ１７→Ｓ１８の順で、Ｍ回実行することができる。これにより、関数演算部４６によれば、シンプレクティック・オイラー法と呼ばれる方法を用いて、第１時刻におけるＮ個の第１変数およびＮ個の第２変数を時間発展させて、第２時刻におけるＮ個の第１変数およびＮ個の第２変数を算出することができる。
【０１３０】
さらに、第３例に係る関数演算部４６は、パイプライン処理により演算を実現してもよい。この場合、関数演算部４６は、２Ｍ段のＸ転送レジスタ５５−１〜５５−２Ｍと、２Ｍ段のＹ転送レジスタ５６−１〜５６−２Ｍと、１つのＸ出力レジスタ５７と、１つのＹ出力レジスタ５８とを、さらに有する。なお、これらの構成のうちの第１例で示した構成は、Ｘ出力レジスタ５７およびＹ出力レジスタ５８を除いて第１例と同様の動作をする。
【０１３１】
（２ｍ−１）段目のＸ転送レジスタ５５−（２ｍ−１）は、クロックサイクル毎に、第（ｍ−１）のＦＹ加算部５４−（ｍ−１）が直前のクロックサイクルにおいて算出した第１更新値Ｘｍ−１を取得し、取得した第１更新値Ｘｍ−１を１クロックサイクル期間保持する。（２ｍ−１）段目のＹ転送レジスタ５６−（２ｍ−１）は、クロックサイクル毎に、直前のクロックサイクルにおいて（２ｍ−２）段目のＹ転送レジスタ５６−（２ｍ−２）が保持していた第２更新値Ｙｍ−１を取得し、取得した１つの第２更新値Ｙｍ−１を、１クロックサイクル期間保持する。
【０１３２】
第ｍのＦＸ演算部５１−ｍは、クロックサイクル毎に、（２ｍ−１）段目のＸ転送レジスタ５５−（２ｍ−１）に格納された第１更新値Ｘｍ−１に対して、第１関数演算を実行することにより、第２微分値を算出する。第ｍのＦＸ加算部５２−ｍは、クロックサイクル毎に、第ｍのＦＸ演算部５１−ｍが当該クロックサイクルにおいて算出した第２微分値と、（２ｍ−１）段目のＹ転送レジスタ５６−（２ｍ−１）に格納された第２更新値Ｙｍ−１とを加算することにより、新たな第２更新値Ｙｍを算出する。
【０１３３】
２ｍ段目のＸ転送レジスタ５５−２ｍは、クロックサイクル毎に、直前のクロックサイクルにおいて（２ｍ−１）段目のＸ転送レジスタ５５−（２ｍ−１）が保持していた第１更新値Ｘｍ−１を取得し、取得した１つの第１更新値Ｘｍ−１を、１クロックサイクル期間保持する。２ｍ段目のＹ転送レジスタ５６−２ｍは、クロックサイクル毎に、第ｍのＦＸ加算部５２−ｍが直前のクロックサイクルにおいて算出した第２更新値Ｙｍを取得し、取得した第２更新値Ｙｍを１クロックサイクル期間保持する。
【０１３４】
第ｍのＦＹ演算部５３−ｍは、クロックサイクル毎に、２ｍ段目のＹ転送レジスタ５６−２ｍに格納された第２更新値Ｙｍに対して、第２関数演算を実行することにより、第１微分値を算出する。第ｍのＦＹ加算部５４−ｍは、クロックサイクル毎に、第ｍのＦＹ演算部５３−ｍが当該クロックサイクルにおいて算出した第１微分値と、２ｍ段目のＸ転送レジスタ５５−２ｍに格納された第１更新値Ｘｍ−１とを加算することにより、新たな第１更新値Ｘｍを算出する。
【０１３５】
Ｘ出力レジスタ５７は、クロックサイクル毎に、第ＭのＦＹ加算部５４−Ｍが直前のクロックサイクルにおいて算出した第１更新値ＸＭを取得し、取得した第１更新値ＸＭを第２時刻における１つの第１変数ＸＯＵＴとして第１変数メモリ４０に記憶させる。
【０１３６】
Ｙ出力レジスタ５８は、クロックサイクル毎に、第２Ｍ段目のＹ転送レジスタ５６−２Ｍに格納された第２更新値ＹＭを取得し、取得した第２更新値ＹＭを第２時刻における１つの第２変数ＹＯＵＴとして第２変数メモリ４２に記憶させる。
【０１３７】
このようなパイプライン処理を実行することにより、第３例に係る関数演算部４６は、クロックサイクル毎に、下記のような演算を実行することができる。
【０１３８】
Ｙ１＝ＦＸ（ＸＩＮ）＋ＹＩＮ
Ｘ１＝ＦＹ（Ｙ１）＋ＸＩＮ
…
Ｙｍ＝ＦＸ（Ｘｍ−１）＋Ｙｍ−１
Ｘｍ＝ＦＹ（Ｙｍ）＋Ｘｍ−１
…
ＹＭ＝ＦＸ（ＸＭ−１）＋ＹＭ−１
ＸＭ＝ＦＹ（ＹＭ）＋ＸＭ−１
ＹＯＵＴ＝ＹＭ
ＸＯＵＴ＝ＸＭ
【０１３９】
このような第３例に係る関数演算部４６は、同一のインデックスｉの１つの第１変数ＸＩＮおよび１つの第２変数ＹＩＮを含む変数ペアに対して、第１関数演算→ＦＸ加算→第２関数演算→ＦＹ加算の一連の演算セットを、Ｍ回実行することができる。さらに、第３例に係る関数演算部４６は、パイプライン処理により実行するので、複数の変数ペアに対して並列して演算を実行することができる。これにより、第３例に係る関数演算部４６は、Ｎ個の変数ペアに対する演算を、短時間で完了させることができる。
【０１４０】
図８は、関数演算部４６の構成の第４例を示す図である。関数演算部４６は、図８に示すような、第４例の構成であってもよい。第４例に係る関数演算部４６は、第２例と略同一の構成を有する。第４例を説明するに当たり、第２例と同一の動作をする構成要素については、同一の符号を付けて相違点を除き詳細な説明を省略する。
【０１４１】
第ｍのＦＹ演算部５３−ｍ（ｍは、２からＭまでの任意の整数）は、第（ｍ−１）のＦＸ加算部５２−（ｍ−１）が算出したＮ個の第２更新値のそれぞれに対して第２関数演算をすることにより、Ｎ個の第１微分値を算出する。第ｍのＦＹ加算部５４−ｍは、第ｍのＦＹ演算部５３−ｍが算出したＮ個の第１微分値と第（ｍ−１）のＦＹ加算部５４−ｍが算出したＮ個の第１更新値とを加算することにより、新たなＮ個の第１更新値を算出する。
【０１４２】
第ｍのＦＸ演算部５１−ｍは、第ｍのＦＹ加算部５４−ｍが算出したＮ個の第１更新値のそれぞれに対して第１関数演算をすることにより、Ｎ個の第２微分値を算出する。第ｍのＦＸ加算部５２−ｍは、第ｍのＦＸ演算部５１−ｍが算出したＮ個の第２微分値と第（ｍ−１）のＦＸ加算部５２−（ｍ−１）が算出したＮ個の第２更新値とを加算することにより、新たなＮ個の第２更新値を算出する。
【０１４３】
このような第４例の構成の関数演算部４６は、第１実施形態におけるＳ１６からＳ１９までのループ処理を、Ｓ１８→Ｓ１７の順で、Ｍ回実行することができる。これにより、関数演算部４６によれば、シンプレクティック・オイラー法と呼ばれる方法を用いて、第１時刻におけるＮ個の第１変数およびＮ個の第２変数を時間発展させて、第２時刻におけるＮ個の第１変数およびＮ個の第２変数を算出することができる。
【０１４４】
さらに、第４例に係る関数演算部４６は、パイプライン処理により演算を実現してもよい。この場合も、関数演算部４６は、２Ｍ段のＸ転送レジスタ５５−１〜５５−２Ｍと、２Ｍ段のＹ転送レジスタ５６−１〜５６−２Ｍと、１つのＸ出力レジスタ５７と、１つのＹ出力レジスタ５８とを、さらに有する。なお、これらの構成のうちの第２例で示した構成は、Ｘ出力レジスタ５７およびＹ出力レジスタ５８を除いて第２例と同様の動作をする。
【０１４５】
（２ｍ−１）段目のＸ転送レジスタ５５−（２ｍ−１）は、クロックサイクル毎に、直前のクロックサイクルにおいて（２ｍ−２）段目のＸ転送レジスタ５５−（２ｍ−２）が保持していた第１更新値Ｘｍ−１を取得し、取得した１つの第１更新値Ｘｍ−１を、１クロックサイクル期間保持する。（２ｍ−１）段目のＹ転送レジスタ５６−（２ｍ−１）は、クロックサイクル毎に、第（ｍ−１）のＦＸ加算部５２−（ｍ−１）が直前のクロックサイクルにおいて算出した第２更新値Ｙｍ−１を取得し、取得した第２更新値Ｙｍ−１を１クロックサイクル期間保持する。
【０１４６】
第ｍのＦＹ演算部５３−ｍは、クロックサイクル毎に、（２ｍ−１）段目のＹ転送レジスタ５６−（２ｍ−１）に格納された第２更新値Ｙｍ−１に対して、第２関数演算を実行することにより、第１微分値を算出する。第ｍのＦＹ加算部５４−ｍは、クロックサイクル毎に、第ｍのＦＹ演算部５３−ｍが当該クロックサイクルにおいて算出した第１微分値と、（２ｍ−１）段目のＸ転送レジスタ５５−（２ｍ−１）に格納された第１更新値Ｘｍ−１とを加算することにより、新たな第１更新値Ｘｍを算出する。
【０１４７】
２ｍ段目のＸ転送レジスタ５５−２ｍは、クロックサイクル毎に、第ｍのＦＹ加算部５４−ｍが直前のクロックサイクルにおいて算出した第１更新値Ｘｍを取得し、取得した第１更新値Ｘｍを１クロックサイクル期間保持する。２ｍ段目のＹ転送レジスタ５６−２ｍは、クロックサイクル毎に、直前のクロックサイクルにおいて（２ｍ−１）段目のＹ転送レジスタ５６−（２ｍ−１）が保持していた第２更新値Ｙｍ−１を取得し、取得した１つの第２更新値Ｙｍ−１を、１クロックサイクル期間保持する。
【０１４８】
第ｍのＦＸ演算部５１−ｍは、クロックサイクル毎に、２ｍ段目のＸ転送レジスタ５５−２ｍに格納された第１更新値Ｘｍに対して、第１関数演算を実行することにより、第２微分値を算出する。第ｍのＦＸ加算部５２−ｍは、クロックサイクル毎に、第ｍのＦＸ演算部５１−ｍが当該クロックサイクルにおいて算出した第２微分値と、２ｍ段目のＹ転送レジスタ５６−２ｍに格納された第２更新値Ｙｍ−１とを加算することにより、新たな第２更新値Ｙｍを算出する。
【０１４９】
Ｘ出力レジスタ５７は、クロックサイクル毎に、第２Ｍ段目のＸ転送レジスタ５５−２Ｍに格納された第１更新値ＸＭを取得し、取得した第１更新値ＸＭを第２時刻における１つの第１変数ＸＯＵＴとして第１変数メモリ４０に記憶させる。
【０１５０】
Ｙ出力レジスタ５８は、クロックサイクル毎に、第ＭのＦＸ加算部５２−Ｍが直前のクロックサイクルにおいて算出した第２更新値ＹＭを取得し、取得した第２更新値ＹＭを第２時刻における１つの第２変数ＹＯＵＴとして第２変数メモリ４２に記憶させる。
【０１５１】
このようなパイプライン処理を実行することにより、第４例に係る関数演算部４６は、クロックサイクル毎に、下記のような演算を実行することができる。
【０１５２】
Ｘ１＝ＦＹ（ＹＩＮ）＋ＸＩＮ
Ｙ１＝ＦＸ（Ｘ１）＋ＹＩＮ
…
Ｘｍ＝ＦＹ（Ｙｍ−１）＋Ｘｍ−１
Ｙｍ＝ＦＸ（Ｘｍ）＋Ｙｍ−１
…
ＸＭ＝ＦＹ（ＹＭ−１）＋ＸＭ−１
ＹＭ＝ＦＸ（ＸＭ）＋ＹＭ−１
ＸＯＵＴ＝ＸＭ
ＹＯＵＴ＝ＹＭ
【０１５３】
このような第４例に係る関数演算部４６は、同一のインデックスｉの１つの第１変数ＸＩＮおよび１つの第２変数ＹＩＮを含む変数ペアに対して、第２関数演算→ＦＹ加算→第１関数演算→ＦＸ加算の一連の演算セットを、Ｍ回実行することができる。さらに、第４例に係る関数演算部４６は、パイプライン処理により実行するので、複数の変数ペアに対して並列して演算を実行することができる。これにより、第４例に係る関数演算部４６は、Ｎ個の変数ペアに対する演算を、短時間で完了させることができる。
【０１５４】
（第３実施形態）
第３実施形態に係る計算装置１０について説明する。
【０１５５】
図９は、第３実施形態でのＮ個の第１中間変数ｘｉ´、係数行列ＪおよびＮ個の第２中間変数ｂｉの関係を示す図である。
【０１５６】
係数行列Ｊは、Ｐｒ３個の分割行列（ＪＧ０，ＪＧ１，…ＪＧｋ，…，ＪＧＰｒ３−１）に分割される。Ｐｒ３個の分割行列のそれぞれは、（Ｎ／Ｐｒ３）行×Ｎ列の係数Ｊｉ，ｊを含む。Ｐｒ３は、Ｎの約数である。また、ｋは、０からＰｒ３−１までの任意の整数である。
【０１５７】
また、Ｎ個の第２中間変数ｂｉは、Ｐｒ３個のブロック（ＢＧ０，ＢＧ１，…ＢＧｋ，…，ＢＧＰｒ３−１）に分割される。Ｐｒ３個のブロックのそれぞれは、（Ｎ／Ｐｒ３）個の第２中間変数ｂｉを含む。さらに、Ｐｒ３個のブロックは、Ｐｒ３個の分割行列に一対一で対応付けられる。例えば、ｋ番目のブロックＢＧｋは、ｋ番目の分割行列ＪＧｋに対応する。
【０１５８】
第３実施形態において、行列乗算部２８は、Ｎ個の第１中間変数ｘｉ´と、Ｐｒ３個の分割行列のそれぞれとを別個に行列乗算することにより、Ｐｒ３個のブロックを算出する。
【０１５９】
図１０は、第３実施形態に係る行列乗算部２８の構成を、時間発展部３０とともに示す図である。
【０１６０】
行列乗算部２８は、Ｐｒ３個の分割行列に一対一で対応付けられたＰｒ３個の分割行列乗算部６０を有する。Ｐｒ３個の分割行列乗算部６０のそれぞれは、Ｎ個の第１中間変数ｘｉ´と、対応する分割行列とを行列乗算することにより、対応するブロックに含まれる（Ｎ／Ｐｒ３）個の第２中間変数ｂｉを算出する。
【０１６１】
Ｐｒ３個の分割行列乗算部６０は、同一の構成を有する。Ｐｒ３個の分割行列乗算部６０は、例えば、互いに異なる半導体装置に実装された回路であってよい。
【０１６２】
Ｐｒ３個の分割行列乗算部６０のそれぞれは、Ｎ個の第１中間変数ｘｉ´をストリーム化した第１中間ストリームＸ´およびＮ個の第２中間変数ｂｉをストリーム化した第２中間ストリームＢを受信する。また、Ｐｒ３個の分割行列乗算部６０のそれぞれは、第１中間ストリームＸ´および第２中間ストリームＢを送信する。
【０１６３】
Ｐｒ３個の分割行列乗算部６０は、直列に接続される。先頭の分割行列乗算部６０は、時間発展部３０から第１中間ストリームＸ´を受信する。また、先頭の分割行列乗算部６０は、第２中間ストリームＢとして、ダミーデータを受信する。なお、ダミーデータは、どのブロックから送信されてもよい。先頭以外の分割行列乗算部６０は、直前段の分割行列乗算部６０から送信された第１中間ストリームＸ´および第２中間ストリームＢを受信する。
【０１６４】
末尾以外の分割行列乗算部６０は、直後段の分割行列乗算部６０へ第１中間ストリームＸ´および第２中間ストリームＢを送信する。末尾の分割行列乗算部６０は、第２中間ストリームＢを時間発展部３０へと送信する。末尾の分割行列乗算部６０から送信された第１中間ストリームＸ´は、廃棄される。なお、末尾の分割行列乗算部６０から送信された第１中間ストリームＸ´は、時間発展部３０に受信された後、時間発展部３０内で廃棄されてもよい。
【０１６５】
Ｐｒ３個の分割行列乗算部６０のそれぞれは、バッファ部６２と、分割行列メモリ６４と、実行部６６と、セレクタ６８とを有する。
【０１６６】
先頭の分割行列乗算部６０のバッファ部６２は、時間発展部３０から出力された第１中間ストリームＸ´を取得し、取得した第１中間ストリームＸ´を一定時間記憶して出力する。先頭以外の分割行列乗算部６０のバッファ部６２は、直前段の分割行列乗算部６０から出力された第１中間ストリームＸ´を取得し、取得した第１中間ストリームＸ´を一定時間記憶して出力する。
【０１６７】
分割行列メモリ６４は、対応する分割行列に含まれる（Ｎ／Ｐｒ３）行×Ｎ列の係数Ｊｉ，ｊを記憶する。実行部６６は、バッファ部６２に記憶された第１中間ストリームＸ´および分割行列メモリ６４に記憶された分割行列に基づき、対応するブロックに含まれる（Ｎ／Ｐｒ３）個の第２中間変数ｂｉを算出する。
【０１６８】
ここで、実行部６６は、対応するブロックに含まれる（Ｎ／Ｐｒ３）個の第２中間変数ｂｉを、１クロックサイクルにＰｒ１個の第２中間変数ｂｉを含む第２中間ストリームＢとして出力する。Ｐｒ１は、Ｎの約数である。
【０１６９】
さらに、実行部６６は、他の分割行列乗算部６０に含まれる実行部６６とは異なるクロックサイクルにおいて、第２中間ストリームＢを出力する。従って、第２中間ストリームＢは、同一のクロックサイクルに、複数の分割行列乗算部６０から出力されることはない。
【０１７０】
先頭の分割行列乗算部６０のセレクタ６８は、先頭の分割行列乗算部６０の実行部６６が第２中間ストリームＢを出力したクロックサイクルにおいて、先頭の分割行列乗算部６０の実行部６６が出力した第２中間ストリームＢを選択して出力する。また、先頭の分割行列乗算部６０のセレクタ６８は、先頭の分割行列乗算部６０の実行部６６が第２中間ストリームＢを出力していないクロックサイクルにおいて、ダミーデータを選択して出力する。
【０１７１】
また、先頭を除いたｋ番目の分割行列乗算部６０のセレクタ６８は、ｋ番目の分割行列乗算部６０の実行部６６が第２中間ストリームＢを出力したクロックサイクルにおいて、ｋ番目の分割行列乗算部６０の実行部６６が出力した第２中間ストリームＢを選択して出力する。また、ｋ番目の分割行列乗算部６０の実行部６６が第２中間ストリームＢを出力していないクロックサイクルにおいて、前段の分割行列乗算部６０のセレクタ６８が出力した第２中間ストリームＢを選択して出力する。
【０１７２】
図１１は、第３実施形態に係る行列乗算部２８および時間発展部３０の実装例を示す図である。
【０１７３】
第３実施形態に係るＰｒ３個の行列乗算部２８および時間発展部３０は、例えば、それぞれが独立した半導体チップである、（Ｐｒ３＋１）個のチップ７０−１〜７０−（Ｐｒ３＋１）に実装することができる。
【０１７４】
第１から第Ｐｒ３のチップ７０−１〜７０−Ｐｒ３のそれぞれは、分割行列乗算部６０を含む。第（Ｐｒ３＋１）のチップ７０−（Ｐｒ３＋１）は、時間発展部３０を含む。
【０１７５】
また、それぞれのチップ７０は、受信部７４および送信部７６を含む。受信部７４は、データ受信用のリンクポートである。送信部７６は、データ送信用のリンクポートである。受信部７４および送信部７６は、全二重通信をする送受信部であってもよい。また、それぞれのチップ７０は、さらなる通信ポートを含んでもよい。例えば、それぞれのチップ７０は、２つの独立な受信用リンクポートおよび２つの独立な送信用リンクポートを含んでもよい。
【０１７６】
送信部７６は、１クロックサイクル分の第１中間変数ｘｉ´および第２中間変数ｂｉを合成して、合成ストリームとして出力する。第１中間ストリームＸ´のビット幅がＷｘ´であり、第２中間ストリームＢのビット幅がＷｂとした場合、合成ストリームは、Ｗｘ´＋Ｗｂ以上のビット幅を有する。
【０１７７】
受信部７４および送信部７６のそれぞれは、例えば、ＦＩＦＯメモリを含む。送信部７６は、第１中間ストリームＸ´および第２中間ストリームＢを合成して、ＦＩＦＯに書き込む。そして、送信部７６は、ＦＩＦＯに格納された合成ストリームを順次に送信する。また、受信部７４は、受信した合成ストリームをＦＩＦＯに書き込む。そして、受信部７４は、ＦＩＦＯから合成ストリームを順に読み出して、第１中間ストリームＸ´および第２中間ストリームＢに分離する。
【０１７８】
２つのチップ７０の間は、通信リンク７２を介して接続される。第１のチップ７０−１の出力端子は、第２のチップ７０−２の入力端子に、第１の通信リンク７２−１を介して接続される。第ｋのチップ７０−ｋの出力端子は、第（ｋ＋１）のチップ７０−（ｋ＋１）の入力端子に、第ｋの通信リンク７２−ｋを介して接続される。そして、第（Ｐｒ３＋１）のチップ７０−（Ｐｒ３＋１）の出力端子は、第１のチップ７０−１の入力端子に、第（Ｐｒ３＋１）の通信リンク７２−（Ｐｒ３＋１）を介して接続される。このように、（Ｐｒ３＋１）個のチップ７０−１〜７０−（Ｐｒ３＋１）は、リングトポロジの態様で相互接続される。
【０１７９】
例えば、チップ７０の入力端子および出力端子は、ＱＳＦＰ（Quad  Small  Form-factor  Pluggable）ポートであってよい。また、通信リンク７２は、ＱＳＦＰ対応光学ケーブルまたはＱＳＦＰ対応メタルケーブルであってよい。また、２つのチップ７０の間の通信リンク７２は、高速シリアルリンク，イーサーネットリンクまたはｐｅｅｒ−ｔｏ−ｐｅｅｒリンクであってもよい。
【０１８０】
なお、本実施形態では、それぞれのチップ７０は、合成ストリームを送受信しているが、第１中間ストリームＸ´および第２中間ストリームＢをそれぞれ別個に送受信してもよい。この場合、（Ｐｒ３＋１）個のチップ７０−１〜７０−（Ｐｒ３＋１）は、２系統のリングトポロジの態様で相互接続される。
【０１８１】
このような第３実施形態に係る計算装置１０は、最適化問題により決定すべき第１変数ｘｉの個数が変更しても、分割行列乗算部６０の個数を変更することにより、対応することができる。従って、計算装置１０は、最適化問題により決定すべき第１変数ｘｉの個数が大幅に増加した場合、例えば、同一の構成のチップ７０の数を増加させれば、対応することができる。また、計算装置１０は、複数の分割行列乗算部６０により並列的に行列演算が実行されるので、最適化問題を短時間で完了させることができる。
【０１８２】
（第４実施形態）
第４実施形態に係る計算装置１０について説明する。
【０１８３】
図１２は、第４実施形態でのＮ個の第１中間変数ｘｉ´、係数行列ＪおよびＮ個の第２中間変数ｂｉの関係を示す図である。第４実施形態において、Ｎ個の第１中間変数ｘｉ´、係数行列ＪおよびＮ個の第２中間変数ｂｉは、第３実施形態と同様の関係に加えて、さらに、図１２に示すような関係がある。
【０１８４】
Ｎ個の第１中間変数ｘｉ´は、Ｎｓ個のデータセットに分割される。Ｎｓ個のデータセットのそれぞれは、Ｐｃ個の第１中間変数ｘｉ´を含む。ＮｓおよびＰｃは、Ｎの約数である。例えば、Ｎ個の第１中間変数ｘｉ´は、ｘ´ｂ０、ｘ´ｂ１、…、ｘ´ｂＮｓのＮｓ個のデータセットに分割される。
【０１８５】
Ｐｒ３個の分割行列のそれぞれは、Ｐｒ２個のサブ行列に分割される。Ｐｒ２個のサブ行列のそれぞれは、Ｐｒ１行×Ｎ列の係数Ｊｉ，ｊを含む。例えば、ＪＧ０の分割行列は、ｊｂ０、ｊｂ１、…、ｊｂｓ、…、ｊｂＰｒ２−１のＰｒ２個のサブ行列に分割される。
【０１８６】
Ｐｒ１およびＰｒ２は、Ｎの約数であり、Ｐｒ１×Ｐｒ２×Ｐｒ３は、Ｎとなる。ｓは、０からＰｒ２−１までの任意の整数である。
【０１８７】
Ｎ個の第２中間変数ｂｉに含まれるＰｒ３個のブロックのそれぞれは、Ｐｒ２個のサブブロックに分割される。Ｐｒ２個のサブブロックのそれぞれは、Ｐｒ１個の第２中間変数ｂｉを含む。例えば、ＢＧ０のブロックは、ｂｂ０、ｂｂ１、…、ｂｂｓ、…、ｂｂＰｒ２−１のＰｒ２個のサブブロックに分割される。
【０１８８】
そして、ｋ番目のブロックに含まれるＰｒ２個のサブブロックは、ｋ番目の分割行列に含まれるＰｒ２個のサブ行列に一対一で対応付けられる。例えば、ｋ番目のブロックＢＧｋに含まれるｓ番目のサブブロックは、ｋ番目の分割行列ＪＧｋに含まれるｓ番目のサブ行列ｊｂｓに対応する。
【０１８９】
第４実施形態において、分割行列乗算部６０は、対応する分割行列に含まれるサブ行列毎に、Ｎ個の第１中間変数ｘｉ´との行列乗算を実行する。例えば、ｋ番目の分割行列乗算部６０は、Ｎ個の第１中間変数ｘｉ´と、ｋ番目の分割行列ＪＧｋに含まれるＰｒ２個のサブ行列のそれぞれとを別個に行列乗算をすることにより、ｋ番目のブロックＢＧｋに含まれるＰｒ２個のサブブロックを算出する。
【０１９０】
図１３は、第４実施形態に係る分割行列乗算部６０の構成を示す図である。分割行列乗算部６０に含まれる実行部６６は、Ｐｒ２個のサブ行列乗算部８０と、多重化部８２とを含む。
【０１９１】
Ｐｒ２個のサブ行列乗算部８０は、対応する分割行列に含まれるＰｒ２個のサブ行列に一対一で対応付けられる。例えば、ｋ番目の分割行列に対応付けられた分割行列乗算部６０に含まれるＰｒ２個のサブ行列乗算部８０は、ｋ番目の分割行列に含まれるＰｒ２個のサブ行列に一対一で対応付けられる。
【０１９２】
第ｋ番目の分割行列乗算部６０に含まれるＰｒ２個のサブ行列乗算部８０のそれぞれは、Ｎ個の第１中間変数ｘｉ´と、対応するサブ行列とを行列乗算することにより、対応するサブブロックに含まれるＰｒ１個の第２中間変数ｂｉを算出する。
【０１９３】
また、Ｐｒ２個のサブ行列乗算部８０のそれぞれは、対応するサブブロックに含まれるＰｒ１個の第２中間変数ｂｉを１クロックサイクルで並列に出力する。例えば、ｋ番目の分割行列乗算部６０に含まれるｓ番目のサブ行列乗算部８０は、ｋ番目のブロックに含まれるｓ番目のサブブロックに含まれるＰｒ１個の第２中間変数ｂｉを、同一のクロックサイクルに出力する。
【０１９４】
さらに、Ｐｒ２個のサブ行列乗算部８０のそれぞれは、他のサブ行列乗算部８０とは異なるクロックサイクルにおいて、Ｐｒ１個の第２中間変数ｂｉを出力する。つまり、第２中間変数ｂｉは、同一のクロックサイクルに、複数のサブ行列乗算部８０から出力されることはない。
【０１９５】
多重化部８２は、Ｐｒ２個のサブ行列乗算部８０のそれぞれから出力されたＰｒ１個の第２中間変数ｂｉのセットを多重化することにより、１クロックサイクルにＰｒ１個の第２中間変数ｂｉを含む第２中間ストリームＢを生成する。例えば、ｋ番目の分割行列乗算部６０に含まれる多重化部８２は、ｋ番目のブロックに含まれるＰｒ２個のサブブロックを含む第２中間ストリームＢを、Ｐｒ２クロックサイクルで出力する。
【０１９６】
分割行列乗算部６０に含まれるバッファ部６２は、シフトレジスタとして機能するＰｒ２段のレジスタ８４と、バッファ内受信部８６と、バッファ内送信部８８とを含む。
【０１９７】
Ｐｒ２段のレジスタ８４は、Ｐｒ２個のサブ行列乗算部８０に一対一に対応付けられる。Ｐｒ２段のレジスタ８４のそれぞれは、Ｐｃ個の第１中間変数ｘｉ´を含むデータセットを１クロックサイクル記憶する。Ｐｒ２段のレジスタ８４のそれぞれは、次のクロックサイクルにおいて、記憶しているＰｃ個の第１中間変数ｘｉ´を含むデータセットを次段のレジスタ８４に並列に転送する。
【０１９８】
バッファ内受信部８６は、第１中間ストリームＸ´を受信し、受信した第１中間ストリームＸ´をＰｃ個のワード幅のストリームに変換する。そして、バッファ内受信部８６は、１クロックサイクル毎に、Ｐｃ個の第１中間変数ｘｉ´を含むデータセットを先頭のレジスタ８４に書き込む。
【０１９９】
バッファ内送信部８８は、１クロックサイクル毎に、最終段のレジスタ８４からＰｃ個の第１中間変数ｘｉ´を含むデータセットを読み出し、第１中間ストリームＸ´に変換する。そして、バッファ内送信部８８は、第１中間ストリームＸ´を送信する。
【０２００】
Ｐｒ２個のサブ行列乗算部８０のそれぞれは、対応するレジスタ８４に格納されているＰｃ個の第１中間変数ｘｉ´を含むデータセットを１クロックサイクル毎に読み出す。Ｐｒ２個のサブ行列乗算部８０のそれぞれは、１クロックサイクル毎に、読み出したＰｃ個の第１中間変数ｘｉ´のそれぞれと、対応するサブ行列における対応する列の係数Ｊｉ，ｊと乗算する。そして、Ｐｒ２個のサブ行列乗算部８０のそれぞれは、対応するサブ行列に含まれる行毎に、第１中間変数ｘｉ´と係数Ｊｉ，ｊとの乗算結果を累積加算する。これにより、Ｐｒ２個のサブ行列乗算部８０のそれぞれは、対応するサブブロックに含まれるＰｒ１個の第２中間変数ｂｉを算出することができる。
【０２０１】
ここで、Ｐｒ２個のサブ行列乗算部８０のそれぞれは、対応するレジスタ８４に、Ｎ個の第１中間変数ｘｉ´のうちの先頭の第１中間変数ｘ０´から末尾の第１中間変数ｘＮ−１´が格納される前の期間、乗算および累積加算を実行する。そして、Ｐｒ２個のサブ行列乗算部８０のそれぞれは、対応するレジスタ８４に末尾の第１中間変数ｘＮ−１´が格納されたクロックサイクルから所定数のクロックサイクル経過後に、対応するサブブロックに含まれるＰｒ１個の第２中間変数ｂｉを出力する。従って、Ｐｒ２個のサブ行列乗算部８０のそれぞれは、互いに異なるクロックサイクルに、対応するサブブロックに含まれるＰｒ１個の第２中間変数ｂｉを出力することができる。
【０２０２】
このような構成の第４実施形態に係る計算装置１０は、Ｐｒ３×Ｐｒ２の並列度で行列乗算をすることができる。これにより、第４実施形態に係る計算装置１０によれば、行列乗算を高速に実行することができる。
【０２０３】
（第５実施形態）
第５実施形態に係る計算装置１０について説明する。
【０２０４】
図１４は、第５実施形態でのＮ個の第１中間変数ｘｉ´、係数行列ＪおよびＮ個の第２中間変数ｂｉの関係を示す図である。第５実施形態において、Ｎ個の第１中間変数ｘｉ´、係数行列ＪおよびＮ個の第２中間変数ｂｉは、第４実施形態と同様の関係に加えて、さらに、図１４に示すような関係がある。
【０２０５】
Ｐｒ３個の分割行列のそれぞれは、Ｐｒ２個のサブ行列に分割される。さらに、Ｐｒ２個のサブ行列のそれぞれは、Ｐｃ個の列単位で、Ｎｓ個の係数セットに分割される。それぞれの係数セットは、Ｐｒ１行×Ｐｃ列の係数Ｊｉ，ｊを含む。例えば、ＪＧ０の分割行列に含まれるｊｂ０のサブ行列は、ｊｂ０（０）、ｊｂ０（１）、…、ｊｂ０（Ｎｓ−１）のＮｓ個の係数セットに分割される。
【０２０６】
また、Ｎｓ個の係数セットは、Ｎ個の第１中間変数ｘｉ´をＰｃ個毎に分割したＮｓ個のデータセットに一対一に対応する。
【０２０７】
第５実施形態において、サブ行列乗算部８０は、１つの係数セットに含まれるＰｒ１個の行のそれぞれについて、Ｐｃ個の係数Ｊｉ，ｊと対応するＰｃ個の第１中間変数ｘｉ´との乗累算値を算出する。そして、サブ行列乗算部８０は、Ｐｒ１個の行毎に、Ｎｓ個の係数セットのそれぞれについて算出した全ての乗累算値を加算する。これにより、サブ行列乗算部８０は、Ｐｒ１個の行のそれぞれについて、Ｎ個の係数Ｊｉ，ｊとＮ個の第１中間変数ｘｉ´とを乗累算することができる。
【０２０８】
図１５は、第６実施形態に係るサブ行列乗算部８０の構成を、対応するレジスタ８４とともに示す図である。それぞれのサブ行列乗算部８０は、Ｐｒ１個の乗累算部９０を含む。
【０２０９】
Ｐｒ１個の乗累算部９０は、対応するサブ行列に含まれるＰｒ１個の行に一対一で対応付けられる。例えば、ｋ番目の分割行列に対応付けられた分割行列乗算部６０に含まれるｓ番目のサブ行列に対応付けられたＰｒ１個の乗累算部９０は、ｋ番目の分割行列に含まれるｓ番目のサブ行列に含まれるＰｒ１個の行に一対一で対応付けられる。
【０２１０】
Ｐｒ１個の乗累算部９０は、全て同一の構成である。Ｐｒ１個の乗累算部９０のそれぞれは、係数行列Ｊにおける対応する行と、Ｎ個の第１中間変数ｘｉ´とを乗累算することにより、対応するサブブロックに含まれる対応する位置の第２中間変数ｂｉを算出する。Ｐｒ１個の乗累算部９０は、第２中間変数ｂｉを並行に算出して、同一のクロックサイクルに出力する。
【０２１１】
より詳しくは、Ｐｒ１個の乗累算部９０のそれぞれは、Ｐｒ２段のレジスタ８４のうちの対応するレジスタ８４に順次に記憶される、第１中間ストリームＸ´の先頭の第１中間変数ｘ０´から末尾のＮ個の第１中間変数ｘＮ−１´までを、クロックサイクル毎に取得する。この場合、Ｐｒ１個の乗累算部９０のそれぞれは、１クロックサイクルに、Ｐｃ個の第１中間変数ｘｉ´を含むデータセットを取得する。そして、Ｐｒ１個の乗累算部９０のそれぞれは、データセットの取得をＮｓ（Ｎｓ＝Ｎ／Ｐｃ）クロックサイクルに渡って実行することにより、Ｎｓ個のデータセットを取得する。また、Ｐｒ１個の乗累算部９０のうちのｐ番目（ｐは、０からＰｒ１−１までの任意の整数）の乗累算部９０は、１クロックサイクルに、取得したデータセットに対応する係数セットに含まれる、ｐ番目に対応する行に含まれるＰｃ個の係数（（ｊｐ，ｓ０）〜（ｊｐ，ＳＰｃ−１））を取得する。そして、Ｐｒ１個の乗累算部９０のそれぞれは、係数セットに含まれる対応するＰｃ個の係数を、Ｎｓクロックサイクルに渡って取得する。Ｐｒ１個の乗累算部９０のそれぞれは、１クロックサイクル毎に、Ｐｃ個の第１中間変数ｘｉ´と、対応する行に含まれる対応するＰｃ個の係数Ｊｉ，ｊとを乗累算する。そして、Ｐｒ１個の乗累算部９０のそれぞれは、乗累算結果を、Ｎｓクロックサイクルに渡って累積加算することにより、第２中間変数ｂｉを算出する。
【０２１２】
図１６は、分割行列メモリ６４に記憶された分割行列を示す図である。分割行列メモリ６４は、分割行列をＰｒ２個のサブ行列に分割して記憶する。Ｐｒ２個のサブ行列のそれぞれは、対応するサブ行列乗算部８０へと並列に出力される。
【０２１３】
Ｐｒ２個のサブ行列のそれぞれは、Ｎｓ個の係数セットを含む。Ｎｓ個の係数セットのそれぞれは、Ｐｃ×Ｐｒ１個の係数を含む。分割行列メモリ６４は、Ｐｒ２個のサブ行列のそれぞれについて、１クロックサイクルにおいて、１つの係数セットに含まれるＰｃ×Ｐｒ１個の係数を並列に出力することが可能となっている。
【０２１４】
図１７は、１つのサブ行列乗算部８０に含まれるＰｒ１個の乗累算部９０と、そのサブ行列乗算部８０に送信されるサブ行列を示す図である。
【０２１５】
１つのサブ行列乗算部８０に含まれるＰｒ１個の乗累算部９０のそれぞれには、１クロックサイクル毎に、対応するレジスタ８４に格納されたＰｃ個の第１中間変数ｘｉ´を含むデータセットがブロードキャストされる。
【０２１６】
分割行列メモリ６４は、それぞれのサブ行列について、Ｎｓ個の係数セットを含む。分割行列メモリ６４は、１クロックサイクル毎に、それぞれのサブ行列に含まれる１つの係数セットが、ポインタにより特定される。より具体的には、分割行列メモリ６４は、そのサブ行列に対応するレジスタ８４に格納されたデータセットに対応する係数セットが、特定される。
【０２１７】
分割行列メモリ６４は、クロックサイクル毎に、ポインタにより特定された係数セットに含まれるＰｃ×Ｐｒ１個の係数を並列に出力する。係数セットに含まれるＰｃ×Ｐｒ１個の係数のそれぞれは、出力先の乗累算部９０が予め定められている。分割行列メモリ６４は、１つの係数セットに含まれるＰｃ×Ｐｒ１個の係数のそれぞれを、予め定められた乗累算部９０へと出力する。例えば、係数セットにおける先頭からＰｃ番目までのＰｃ個の係数は、１番目の乗累算部９０に出力される。また、例えば、（Ｐｃ＋１）番目から（２×Ｐｃ）個目までのＰｃ個の係数は、２番目の乗累算部９０に出力される。また、（Ｐｒ１−Ｐｃ）番目からＰｒ１番目までのＰｃ個の係数は、Ｐｒ１番目の乗累算部９０に出力される。
【０２１８】
図１８は、乗累算部９０の構成を示す図である。乗累算部９０は、Ｐｃ個の乗算器９２と、加算器９４と、累加算器９６とを含む。乗累算部９０は、クロックサイクル毎に、Ｐｃ個の第１中間変数ｘｉ´を含むデータセットと、Ｐｃ個の係数Ｊｉ，ｊを含む係数セットとを取得する。
【０２１９】
データセットに含まれるＰｃ個の第１中間変数ｘｉ´と、係数セットに含まれるＰｃ個の係数Ｊｉ，ｊとは、一対一で対応する。また、Ｐｃ個の乗算器９２は、データセットに含まれるＰｃ個の第１中間変数ｘｉ´、および、係数セットに含まれるＰｃ個の係数Ｊｉ，ｊに一対一で対応する。Ｐｃ個の乗算器９２のそれぞれは、データセットに含まれる対応する１つの第１中間変数ｘｉ´と、係数セットに含まれる対応する１つの係数Ｊｉ，ｊとを乗算することにより、乗算値を出力する。Ｐｃ個の乗算器９２のそれぞれは、クロックサイクル毎に、乗算値を出力する。
【０２２０】
加算器９４は、クロックサイクル毎に、Ｐｃ個の乗算器９２から出力されたＰｃ個の乗算値を加算することにより、乗累算値を算出する。累加算器９６は、クロックサイクル毎に、加算器９４から出力された乗累算値を累積加算する。また、累加算器９６は、対応するレジスタ８４に、第１中間ストリームＸ´における先頭の第１中間変数ｘ０´が格納されたタイミング（Ｓ０＝０）において、累積加算値を０にリセットする。
【０２２１】
このような構成の乗累算部９０は、Ｐｒ２段のレジスタ８４のうちの対応するレジスタ８４に順次に記憶される、第１中間ストリームＸ´の先頭の第１中間変数ｘ０´から末尾の第１中間変数ｘＮ−１´までのＮ個の第１中間変数ｘｉ´を、クロックサイクル毎に取得する。さらに、乗累算部９０は、取得したそれぞれの第１中間変数ｘｉ´と、係数行列Ｊにおける対応する行に含まれる、取得した第１中間変数ｘｉ´に対応する列の係数Ｊｉ，ｊとを乗算する。そして、乗累算部９０は、第１中間変数ｘｉ´と係数Ｊｉ，ｊとの乗算結果を、第１中間ストリームＸ´の先頭の第１中間変数ｘ０´から末尾の第１中間変数ｘＮ−１´まで累積加算する。このような処理により、乗累算部９０は、対応するサブブロックに含まれる対応する位置の第２中間変数ｂｉを算出することができる。
【０２２２】
図１９は、第５実施形態におけるパラメータの具体的な値の一例、および、処理タイミングの一例を示す図である。
【０２２３】
図１９の例において、Ｎ＝１６３８４である。また、図１９の例において、Ｐｃ＝４、ＮＳ＝４０９６である。また、図１９の例において、Ｐｒ１＝８、Ｐｒ２＝２５６、Ｐｒ３＝８である。また、図１９において、ｔ０、ｔ１、ｔ２、…、ｔ６１４３は、クロックサイクルの順序を表す。
【０２２４】
Ｎ個の第１中間変数ｘｉ´における先頭のデータセットは、ｔ０に、先頭の行列乗算部２８における先頭のレジスタ８４に格納される。従って、ＪＧ０の分割行列におけるｊｂ０のサブ行列における先頭の係数セットは、ｔ０に読み出される。
【０２２５】
また、Ｎ個の第１中間変数ｘｉ´における末尾のデータセットは、ｔ４０９５に、先頭の行列乗算部２８における先頭のレジスタ８４に格納される。従って、ＪＧ０の分割行列におけるｊｂ０のサブ行列における末尾の係数セットは、ｔ４０９５に読み出される。
【０２２６】
そして、Ｎ個の第２中間変数ｂｉにおける先頭のブロックは、ＪＧ０の分割行列におけるｊｂ０のサブ行列における末尾の係数セットの乗累算が完了したクロックサイクル（ｔ４０９５）以後に、出力可能となる。従って、第２中間変数ｂｉにおける先頭のブロックは、ｔ４０９５＋α（αは、所定の遅延時間）に出力される。
【０２２７】
Ｎ個の第１中間変数ｘｉ´における先頭のデータセットは、ｔ０から（Ｐｒ１×Ｐｒ３＝２０４８）クロックサイクル遅延された後に、最後の行列乗算部２８における最後のレジスタ８４に格納される。従って、ＪＧＰｒ３−１の分割行列におけるｊｂＰｒ２−１のサブ行列における先頭の係数セットは、ｔ２０４７に読み出される。
【０２２８】
また、Ｎ個の第１中間変数ｘｉ´における末尾のデータセットは、ｔ４０９５から（Ｐｒ１×Ｐｒ３＝２０４８）クロックサイクル遅延された後に、最後の行列乗算部２８における最後のレジスタ８４に格納される。従って、ＪＧＰｒ３−１の分割行列におけるｊｂＰｒ２−１のサブ行列における末尾の係数セットは、ｔ６１４３に読み出される。
【０２２９】
そして、Ｎ個の第２中間変数ｂｉにおける末尾のブロックは、ＪＧＰｒ３−１の分割行列におけるｊｂＰｒ２−１のサブ行列における末尾の係数セットの乗累算が完了したクロックサイクル（ｔ６１４３）以後に、出力可能となる。従って、第２中間変数ｂｉにおける末尾のブロックは、ｔ６１４３＋αにおいて、出力される。
【０２３０】
このような構成の第５実施形態に係る計算装置１０は、Ｐｒ３×Ｐｒ２×Ｐｒ１の並列度で行列乗算をすることができる。これにより、第５実施形態に係る計算装置１０によれば、行列乗算を高速に実行することができる。
【０２３１】
（第６実施形態）
第６実施形態に係る計算装置１０について説明する。
【０２３２】
図２０は、第６実施形態に係る時間発展部３０の構成を、複数の行列乗算部２８とともに示す図である。第６実施形態において、それぞれの行列乗算部２８は、１クロックサイクルにＰｒ１個の第２中間変数ｂｉを含む第２中間ストリームＢを出力する。そして、第６実施形態において、時間発展部３０は、１クロックサイクルにＰｒ１個の第２中間変数ｂｉを含む第２中間ストリームＢを受信する。
【０２３３】
そして、第６実施形態に係る時間発展部３０は、Ｐｒ１個の第１変数メモリ４０と、Ｐｒ１個の第２変数メモリ４２と、Ｐｒ１個の第１加算部４４と、Ｐｒ１個の関数演算部４６と、Ｐｒ１個の第１乗算部４８と、１個の第１中間変数メモリ５０とを有する。
【０２３４】
Ｐｒ１個の第１変数メモリ４０、Ｐｒ１個の第２変数メモリ４２、Ｐｒ１個の第１加算部４４、Ｐｒ１個の関数演算部４６およびＰｒ１個の第１乗算部４８は、１クロックサイクルに含まれるＰｒ１個の第２中間変数ｂｉに一対一で対応する。
【０２３５】
そして、Ｐｒ１個の第１加算部４４のそれぞれおよびＰｒ１個の関数演算部４６のそれぞれは、１クロックサイクルに含まれるＰｒ１個の第２中間変数ｂｉのうち対応する１つの第２中間変数ｂｉについての演算処理を実行する。また、Ｐｒ１個の第１変数メモリ４０のそれぞれおよびＰｒ１個の第２変数メモリ４２のそれぞれは、１クロックサイクルに含まれるＰｒ１個の第２中間変数ｂｉのうち対応する１つの第２中間変数ｂｉを用いて算出された第１変数ｘｉおよび第２変数ｙｉを記憶する。また、Ｐｒ１個の第１乗算部４８のそれぞれは、１クロックサイクルに含まれるＰｒ１個の第２中間変数ｂｉのうち対応する１つの第２中間変数ｂｉを用いて算出された第１変数ｘｉに対する演算処理を実行する。
【０２３６】
このように、第６実施形態に係る時間発展部３０は、１クロックサイクルに含まれるＰｒ１個の第２中間変数ｂｉに対して、Ｎ個の第１変数ｘｉおよびＮ個の第２変数ｙｉの算出処理を、Ｐｒ１の並列度で実行する。これにより、第６実施形態に係る計算装置１０は、Ｎ個の第１変数ｘｉおよびＮ個の第２変数ｙｉの算出処理を高速に実行することができる。
【０２３７】
図２１は、第１中間変数ｘｉ´および第２中間変数ｂｉの出力タイミングを示す図である。より詳しくは、図２１の（Ａ）は、時間発展部３０から先頭の行列乗算部２８に第１中間変数ｘｉ´が出力されるタイミングを示す。図２１の（Ｂ）は、末尾の行列乗算部２８から時間発展部３０へ第２中間変数ｂｉが出力されるタイミングを示す。図２１の（Ｃ）は、時間発展部３０による第１中間変数ｘｉ´の算出タイミングを示す。
【０２３８】
第１中間変数ｘｉ´は、Ｐｃ個の並列度で転送がされる。従って、図２１の（Ａ）に示すように、第１時刻における第１中間変数（ｘ´ｂ０〜ｘ´ｂ４０９５（ｔ１））の転送期間は、ＮＳ（＝Ｎ／Ｐｃ）クロックサイクルとなる。
【０２３９】
また、第２中間変数ｂｉは、Ｐｒ１個の並列度で転送がされる。従って、図２１の（Ｂ）に示すように、第１時刻における第２中間変数（ｂｂ０〜ｂｂ２０４７（ｔ１））の転送期間は、Ｎ／Ｐｒ１クロックサイクルとなる。
【０２４０】
また、時間発展部３０は、Ｐｒ１個の並列度で処理が実行される。従って、図２１の（Ｃ）に示すように、第２時刻における第２中間変数（ｂｂ０〜ｂｂ２０４７（ｔ２））の演算期間は、Ｎ／Ｐｒ１クロックサイクルとなる。
【０２４１】
ここで、Ｌａは、第１時刻における最後の第１中間変数（ｘ´ｂ４０９５（ｔ１））の出力が完了してから、第１時刻における最初の第２中間変数（ｂｂ０（ｔ１））の出力が開始するまでの遅延時間である。Ｌｂは、第１時刻における最初の第２中間変数（ｂｂ０（ｔ１））の出力が開始してから、第２時刻における最初の第１中間変数（ｘ´ｂ０（ｔ２））が算出されるまでの遅延時間である。Ｌｃは、第２時刻における最初の第１中間変数（ｘ´ｂ０（ｔ２））が算出されてから、第２時刻における最初の第１中間変数（ｘ´ｂ０（ｔ２））が出力されるまでの遅延時間である。
【０２４２】
ここで、あるループ処理の開始から次のループ処理の開始までの期間（１ループ期間）は、ＮＳ＋Ｌａ＋Ｌｂ＋Ｌｃとなる。計算装置１０は、（Ｌｂ＋Ｌｃ）を、第１時刻における第２中間変数（ｂｂ０〜ｂｂ２０４７（ｔ１））の転送期間（Ｎ／Ｐｒ１）より短くすることができる。従って、計算装置１０では、第１時刻における第２中間変数（ｂｂ０〜ｂｂ２０４７（ｔ１））の出力が完了する前に、第２時刻における第１中間変数（ｘ´ｂ０〜ｘ´ｂ４０９５（ｔ２））の出力が開始される。すなわち、計算装置１０は、ループ処理のオーバラップを実現している。計算装置１０によれば、このようなオーバラップの実現により、高速に処理を実行することができる。
【０２４３】
また、Ｎが大きい場合、ＮＳ＞＞Ｌａ＋Ｌｂ＋Ｌｃとなる。従って、Ｎが大きい場合、Ｌａ＋Ｌｂ＋Ｌが全体の実行時間に対して無視できる程度に短くなる。この場合、計算装置１０での行列乗算時間は、ＮＳ（＝Ｎ／Ｐｃ）クロックサイクルとみなすことができる。
【０２４４】
例えば、シングルコアのプロセッサによるサイズがＮの行列演算時間は、（Ｎ×Ｎ）クロックサイクルである。シングルコアのプロセッサによる行列乗算時間に対する、計算装置１０での行列乗算時間は、（Ｎ／Ｐｃ）／Ｎ×Ｎである。従って、計算装置１０は、シングルコアのプロセッサに対して、１／（Ｐｃ×Ｎ）の時間で行列乗算を実行することができる。
【０２４５】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０２４６】
１０  計算装置
２０  演算部
２２  入力部
２４  出力部
２６  設定部
２８  行列乗算部
３０  時間発展部
３２  管理部
３６  係数行列メモリ
３８  行列乗算実行部
４０  第１変数メモリ
４２  第２変数メモリ
４４  第１加算部
４６  関数演算部
４８  第１乗算部
５０  第１中間変数メモリ
６０  分割行列乗算部
６２  バッファ部
６４  分割行列メモリ
６６  実行部
６８  セレクタ
８０  サブ行列乗算部
８２  多重化部
８４  レジスタ
８６  バッファ内受信部
８８  バッファ内送信部
９０  乗累算部
９２  乗算器
９４  加算器
９６  累加算器
【図１】
2020046887.tif 000014
【図２】
2020046887.tif 000015
【図３】
2020046887.tif 000016
【図４】
2020046887.tif 000017
【図５】
2020046887.tif 000018
【図６】
2020046887.tif 000019
【図７】
2020046887.tif 000020
【図８】
2020046887.tif 000021
【図９】
2020046887.tif 000022
【図１０】
2020046887.tif 000023
【図１１】
2020046887.tif 000024
【図１２】
2020046887.tif 000025
【図１３】
2020046887.tif 000026
【図１４】
2020046887.tif 000027
【図１５】
2020046887.tif 000028
【図１６】
2020046887.tif 000029
【図１７】
2020046887.tif 000030
【図１８】
2020046887.tif 000031
【図１９】
2020046887.tif 000032
【図２０】
2020046887.tif 000033
【図２１】
2020046887.tif 000034