積和演算回路、その設計装置、プログラム
【課題】行列の積和演算の技術に関し、回路の利用効率および演算性能を向上させることが可能な積和演算回路を提供することにある。
【解決手段】乗算器１０２〜１０７は、行列Ａの行を分割した部分行ベクトルと行列Ｂの列を分割した部分列ベクトルとの乗算を並列に実行し、加算器１０８〜１１２は乗算結果を加算し、部分積和演算結果を出力する。１２個の部分積和演算結果は、レイテンシ＝１２の加算器１１６に順次溜め込まれた後、その出力側から入力側にフィードバックされながら、次のタイミングにおける新たな１２個の部分積和演算結果に順次加算される。上記レイテンシに対応する１２進カウンタ１１３と上記分割の数に対応する２２進カウンタ１１４のカウント動作に従って、加算器１１６にて累算された積和演算結果が、１２×２２＝２６４クロック毎に１２個ずつ出力される。
【解決手段】乗算器１０２〜１０７は、行列Ａの行を分割した部分行ベクトルと行列Ｂの列を分割した部分列ベクトルとの乗算を並列に実行し、加算器１０８〜１１２は乗算結果を加算し、部分積和演算結果を出力する。１２個の部分積和演算結果は、レイテンシ＝１２の加算器１１６に順次溜め込まれた後、その出力側から入力側にフィードバックされながら、次のタイミングにおける新たな１２個の部分積和演算結果に順次加算される。上記レイテンシに対応する１２進カウンタ１１３と上記分割の数に対応する２２進カウンタ１１４のカウント動作に従って、加算器１１６にて累算された積和演算結果が、１２×２２＝２６４クロック毎に１２個ずつ出力される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、行列の積和演算の技術に関する。
【背景技術】
【０００２】
近年、ハードウェアにより行列の積和演算回路を実現する場合に、回路規模を縮小するとともに演算時間の短縮が求められている。
例えば、図１２に示されるように、それぞれ１３２行×１３２列の行列ＡとＢの積Ａ×Ｂが算出される場合、通常の演算方法では、行列Ｂの列（ｊ）が固定され、行列Ａの行（ｉ）がｉ＝０〜１３１の順で演算され、行列Ｃの列（ｊ）の解が算出される。
【０００３】
次に、行列Ｂの列（ｊ）が＋１された後、行列Ａの行（ｉ）がｉ＝０〜１３１の順で演算されることにより、行列Ｃの次の列（ｊ）の解が算出される。
この演算方法からわかるように、行列Ａ×Ｂの演算には、膨大な量の積和演算が必要となる。
【０００４】
この演算時間を短縮するために、例えば下記特許文献１では、行列とベクトルの積を複数の乗算器と加算器で求める積和演算回路の技術が開示されている。
また、下記特許文献２では、３×３の空間積和を求める回路において、最初の３個の部分積和が算出されて結果がシフトレジスタに入力され、その後、別の積和が２５５回計算された後に次の３個の積和が計算され、シフトレジスタ内の結果と加算されて空間積和が出力される技術が開示されている。
【特許文献１】特開２００３−５８８７６号公報
【特許文献２】特公平７−３８２１７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、上記特許文献１に記載の従来技術では、複数の乗算器と加算器が使用されるため、行列が大きくなると回路規模が縮小できないという問題点を有している。
また、上記特許文献２に記載の従来技術では、行の大きさに対応したシフトレジスタを用意する必要があるため、数値シミュレーションで用いられる要素数の多い行列の積和演算においてシフトレジスタの段数で対応するのは現実的でないという問題点を有している。
【課題を解決するための手段】
【０００６】
本発明の課題は、回路の利用効率および演算性能を向上させることが可能な積和演算回路を提供することにある。
本発明の第１の態様は、複数の演算回路を並列処理させることにより積和演算を行う積和演算回路を前提とする。
【０００７】
並列演算手段（１０２〜１１２）は、所定行分を並列入力としたデータを並列演算処理する。
積算手段（１１３〜１１７）は、並列演算手段に並列入力される行数に対応したレイテンシを有し、並列演算手段の演算結果を積算する。この積算手段は例えば、並列演算手段に並列入力される行数と同じレイテンシを有する。
【０００８】
本発明の第２の態様は、複数の演算回路を並列処理させることにより積和演算を行う積和演算回路をフイールド・プログラマブル・ロジツクアレイに配置指示を行う設計装置又
は設計プログラムを前提とする。
【０００９】
そして、対象のフイールド・プログラマブル・ロジツクアレイに対し、並列処理された演算結果を加算する積算器のレイテンシを元に求められる所定行分を1ブロックとしたデータを並列演算処理する並列演算回路を配置する指示を行う配置手段（９０３）を含む。この配置手段は例えば、並列処理された演算結果を加算する積算器のレイテンシと同じ所定行分を1ブロックとしたデータを並列演算処理する並列演算回路の配置指示を行う。
【発明の効果】
【００１０】
本発明では、加算器等によって実現される積算手段のレイテンシを利用することにより、シフトレジスタ無しに効率的な並列積和演算を実現することが可能となる。これにより、レイテンシをカウントするカウンタのカウント数のみの変更で、レイテンシを処理時間から隠蔽しかつ、行列要素の大きさに応じた積和演算を可能にする。
【発明を実施するための最良の形態】
【００１１】
以下図面に基づいて、本発明の実施形態について詳細に説明する。
図１は、本発明による積和演算回路の実施形態を示す構成図である。
通常の行列演算、例えば行列Ａ（１３２×１３２）と行列Ｂ（１３２×１３２）の積の演算では、図１３で説明したように、下記数１式に示す計算が実行されることにより、行列Ｃ（１３２×１３２）の１要素（例えばＣ０，０）が算出され同様に他の要素も算出される。
【数１】
【００１２】
ところが、上記１３２×１３２のようにサイズ大きい多入力の積和演算がＦＰＧＡ（Field Programmable Gate Array）やＣＰＬＤ（Complex Programmable Logic Device）のようなプログラマブルデバイスにより実現される場合、積和演算の実行のために並列に１３２個の乗算器を設けなければならない。しかし、単に並列化をすると演算器の数が多くなり回路規模が膨大なものとなるため、実際にハードウェアとしてインプリメントするには複数のプログラマブルデバイスが必要となってしまう。
【００１３】
そこで、回路規模を縮小して１３２×１３２の演算を行うためには、演算器の数を減らしてインプリメントしなければならない。そのために、例えば下記数２式に基づいて回路規模が削減される。
【数２】
【００１４】
しかしこの場合、積和演算を実行する際に、最終段の加算器部分のレイテンシの存在により連続して演算が実行できない。例えば、上記数２式に基づいて並列数が１３２から６に削減された場合、演算性能は、６／１３２＝１／２２になるのではなく、連続演算ができない分が加わって１／２６４程度に落ちてしまう。
【００１５】
そこで、本発明の実施形態では、図１に示される積和演算回路１０１の構成により、並列数の削減比にほぼ等しい演算性能（＝１／２２）が達成されるものである。
積和演算回路１０１は、乗算器１０２（ｍｕｌ０）、１０３（ｍｕｌ１）、１０４（ｍｕｌ２）、１０５（ｍｕｌ３）、１０６（ｍｕｌ４）、１０７（ｍｕｌ５）と、加算器１０８（ａｄｄ０）、１０９（ａｄｄ１）、１１０（ａｄｄ２）、１１１（ａｄｄ３）、１１２（ａｄｄ４）、１１６（ａｄｄ５）、１２進カウンタ１１３（レイテンシカウンタ）、２２進カウンタ１１４、セレクタ１１５、論理積回路１１７（ａｎｄ０）を備え、１３２×１３２の行列演算を実行する。
【００１６】
本実施形態では、積和演算回路１０１の最終段の加算器１１６（ａｄｄ５）のレイテンシ（＝１２）を考慮し、連続演算を可能にするため、行列Ａの１２行を１ブロックとして演算が行われる。また、行列Ａ、行列Ｂ共に６要素ごとに分割され、６要素ごとに演算が行われる。
【００１７】
図２〜図５を用いて、上記分割処理について説明する。
例えば行列Ａ及びＢともに、１３２行×１３２列のサイズを有するとする。
図２の例では、まず、行列Ａについて、その行が６要素ごとの部分行ベクトルに分割される。例えば行ｉ＝０は、「（０，０）（０，１）（０，２）（０，３）（０，４）（０，５）」「（０，６）（０，７）（０，８）（０，９）（０，１０）（０，１１）」・・・「（０，１２０）（０，１２１）（０，１２２）（０，１２３）（０，１２４）（０，１２５）」「（０，１２６）（０，１２７）（０，１２８）（０，１２９）（０，１３０）（０，１３１）」のように分割される。同様に行ｉ＝０以外の各行ｉ＝１〜１３１についても、６要素ずつの部分行ベクトルに分割される。
【００１８】
次に、行列Ｂについて、その列が６要素ごとの部分列ベクトルに分割される。例えば、列ｊ＝０は、「（０，０）（１，０）（２，０）（３，０）（４，０）（５，０）」「（６，０）（７，０）（８，０）（９，０）（１０，０）（１１，０）」・・・「（１２０，０）（１２１，０）（１２２，０）（１２３，０）（１２４，０）（１２５，０）」「（１２６，０）（１２７，０）（１２８，０）（１２９，０）（１３０，０）（１３１，０）」のように分割される。同様に列ｊ＝０以外の各列ｊ＝１〜１３１についても、６要素ずつの部分列ベクトルに分割される。
【００１９】
そして、図２に示す矢印の示す順に行列Ａと行列Ｂの要素データがブロック単位で入力されて、並列積和演算が実行される。
最初は、行列Ａの部分行ベクトル「（０，０）（０，１）（０，２）（０，３）（０，４）（０，５）」と行列Ｂの部分列ベクトル「（０，０）（１，０）（２，０）（３，０）（４，０）（５，０）」の並列積和演算が行われる。この並列積和演算は図１の１０２〜１１２の回路群によって実行される。そして、その並列積和演算結果は、０行０列の積和演算出力Ｃ0,0 のための部分的な演算結果として、加算器１１６（ａｄｄ５）に溜め込まれる。
【００２０】
このａｄｄ５は、レイテンシ＝１２を有するため、１２回分の演算結果を溜め込むことができる。
次に、行列Ａの部分行ベクトル「（１，０）（１，１）（１，２）（１，３）（１，４）（１，５）」と行列Ｂの部分列ベクトル「（０，０）（１，０）（２，０）（３，０）（４，０）（５，０）」の並列積和演算が行われる。その並列積和演算結果は、１行０列の積和演算出力Ｃ1,0 のための部分的な演算結果として、ａｄｄ５に溜め込まれる。
【００２１】
以下同様にして、行列Ａの部分行ベクトルが、ブロック０の最終行ｉ＝１１まで処理される、つまり部分行ベクトル「（１１，０）（１１，１）（１１，２）（１１，３）（１１，４）（１１，５）」まで処理される。
【００２２】
以上の動作の様子を、図３のｃｌｏｃｋ＝１〜１２として示す。同図において、ピリオドで区切られた数値において、左側の数値は行番号を示し、右側の数値は列番号を示す。そして例えば、Ａ０とｃｌｏｃｋ＝１とで決まる枠内に記載される「０．０」は、ｃｌｏ
ｃｋ＝１のタイミングにおいて入力値Ａ０（図１参照）として、行列データＡの０行０列の要素値が入力されることを示す。
【００２３】
図３からわかるように、入力Ｂ０〜Ｂ５（図１参照）の各値は、ｃｌｏｃｋ＝１〜１２の１２クロックの間一定値とされ、入力Ａ０〜Ａ５のみが順次変更されてゆく。このクロック数＝１２は、図１の加算器１１６（ａｄｄ５）のレイテンシに一致するように設定される。
【００２４】
そして、ｃｌｏｃｋ＝１〜１２の１２回の動作により、０行０列〜１１行０列の各積和演算出力Ｃ０,0 〜Ｃ11,0 のための１回目の１２個の部分的な演算結果Ｓ０５〜Ｓ１１５（図３参照）がａｄｄ５に溜め込まれる。
【００２５】
ｃｌｏｃｋ＝１２の動作が完了したら、図３に示されるように、行列Ｂの部分列ベクトルが次の部分列ベクトル「（６，０）（７，０）（８，０）（９，０）（１０，０）（１１，０）」に変更される。
【００２６】
そして、行列Ａの部分行ベクトル「（０，６）（０，７）（０，８）（０，９）（０，１０）（０，１１）」と行列Ｂの部分列ベクトル「（６，０）（７，０）（８，０）（９，０）（１０，０）（１１，０）」の並列積和演算が行われる。その演算結果Ｓ０１１（図３参照）は、加算器１１６（ａｄｄ５）において、その出力値ａｄａｔａ５（図１）として出力されている０行０列の積和演算出力Ｃ0,0 の演算のための１２クロック前の並列積和演算結果Ｓ０５と加算されて、その加算結果Ｓ０５＋Ｓ０１１が再びａｄｄ５に溜め込まれる。
【００２７】
次に、行列Ａの部分行ベクトル「（１，６）（１，７）（１，８）（１，９）（１，１０）（１，１１）」と行列Ｂの部分列ベクトル「（６，０）（７，０）（８，０）（９，０）（１０，０）（１１，０）」の並列積和演算が行われる。その演算結果Ｓ１１１（図３参照）は、加算器１１６（ａｄｄ５）において、その出力値ａｄａｔａ５（図１）として出力されている１行０列の積和演算出力Ｃ1,０ の演算のための１２クロック前の並列積和演算結果Ｓ１５と加算されて、その加算結果Ｓ１５＋Ｓ１１１が再びａｄｄ５に溜め込まれる。
【００２８】
以下同様にして、行列Ａの部分行ベクトルが、ブロック０の最終行ｉ＝１１まで処理される、つまり部分行ベクトル「（１１，６）（１１，７）（１１，８）（１１，９）（１１，１０）（１１，１１）」まで処理される。
【００２９】
以上の動作の様子を、図３のｃｌｏｃｋ＝１３〜２４として示す。このｃｌｏｃｋ＝１３〜２４の１２回の動作により、０行０列〜１１行０列の各積和演算出力Ｃ０,0 〜Ｃ11,0 のための２回目の１２個の部分的な演算結果Ｓ０５＋Ｓ０１１〜Ｓ１１５＋Ｓ１１１１（図３参照）がａｄｄ５に溜め込まれる。
【００３０】
ｃｌｏｃｋ＝１２の動作が完了したら、図３に示されるように、行列Ｂの部分列ベクトルが次の部分列ベクトル「（１２，０）（１３，０）（１４，０）（１５，０）（１６，０）（１７，０）」に変更される。
【００３１】
以上の１２クロックずつの動作が２２回繰り返される、即ち１２×２２＝２６４クロック分の動作が繰り返されることによって、０行０列〜１１行０列の１２個の積和演算出力Ｃ０,0 〜Ｃ11,0 が確定する。図３では、行列Ａ×行列Ｂ＝行列Ｃの演算において、ｂｌｏｃｋ０のブロックにおける１２個のデータが確定する様子が示されている。
【００３２】
次に、ブロック０と同様にブロック１の演算が行われ、以下順次ブロック１０までの１１ブロック分の演算が行われる。また、演算結果は列順で確定するため、結果順にＳＤＲＡＭメモリなどへ転送して記録される。
【００３３】
上述の説明は、例えば行列Ａ及びＢともに１３２行×１３２列のサイズを有する場合の例についてのものであるが、そのほかに行列Ａ及びＢが例えば６６行×６６列のサイズを有するような場合には、図１の加算器１１６（ａｄｄ５）のレイテンシに対応させて各行列要素を１ブロック＝１２要素ずつに分割した場合、余りが出てしまう。
【００３４】
このような場合には、図４に示されるように、各行列要素数を１２で割り切れるように拡張し、拡張部分には値０を有するｄｕｍｍｙ（ダミー）値を補充すればよい。
次に図５は、図１を構成する各演算器１０２〜１１２、及び１１６の機能を示す図である。
【００３５】
基本的に、各演算器は３入力、２出力のポートを備えている。入力ポートは、データを入力する２ポートと、演算を有効にするイネーブル信号を取得する１ポートの計３ポートを有する。出力ポートは、データを出力するポートと、次段に接続される演算を有効にするイネーブル信号を出力するための１ポートの計２ポートを有する。また、演算器内に示されている「数値１」はスループットを示し、「数値２」はレイテンシを示している。
【００３６】
図１の乗算器１０２〜１０７は、行列Ａの行ベクトルごとの各要素Ａ０〜Ａ５と行列Ｂの各要素Ｂ０〜Ｂ５を取得する２つの各入力ポートと、乗算器の演算を行うかどうかを決定するイネーブル信号を取得する各ポートと、次段に接続される加算器１０８への出力信号（ｍｄａｔａ０〜５）を出力する各出力ポートと、加算器１０８〜１１０の各演算を有効にすることを通知する信号（ｍｒｄｙ０，ｍｒｄｙ２，ｍｒｄｙ４）を出力するポートを備えている。乗算器１０２は、イネーブル信号が有効を示しているときに、入力ポートＡ０、Ｂ０に入力された要素を乗算する。
【００３７】
本例では乗算器１０２〜１０７は６４ビット浮動小数点の乗算器を用いているが、６４ビット浮動小数点の乗算器に限定するものではなく乗算ができれば固定小数点型であってもよい。
【００３８】
加算器１０８〜１１０はそれぞれ、乗算器１０２と１０３、乗算器１０４と１０５、及び乗算器１０６と１０７の各出力ポートと接続される各入力ポートを備え、乗算結果であるｍｄａｔａ０とｍｄａｔａ１、ｍｄａｔａ２とｍｄａｔａ３、及びｍｄａｔａ４とｍｄａｔａ５を取得する。また、乗算器１０２，１０４，１０６からそれぞれ出力されるｍｒｄｙ０，ｍｒｄｙ２，ｍｒｄｙ４信号をそれぞれ取得する各入力ポートを備えている。加算器１０８〜１１０は、ｍｒｄｙ０，ｍｒｄｙ２，ｍｒｄｙ４がそれぞれ有効であるときに各加算動作を実行し、各出力ａｄａｔａ０〜２を出力する。
【００３９】
加算器１０８は、次段の加算器１１１にイネーブル信号ａｒｄｙ０信号を出力する。
加算器１１１は、加算器１０８と１０９の各出力ポートと接続される各入力ポートを備え、加算結果であるａｄａｔａ０とａｄａｔａ１を取得する。また、加算器１０８から出力されるａｒｄｙ０信号を取得する入力ポートを備えている。加算器１１１は、ａｒｄｙ０信号が有効であるときに加算動作を実行し、出力ａｄａｔａ３を出力する。また、加算器１１１は、次段の加算器１１２にイネーブル信号ａｒｄｙ３信号を出力する。
【００４０】
加算器１１２は、加算器１１１と１１０の各出力ポートと接続される各入力ポートを備え、加算結果であるａｄａｔａ３とａｄａｔａ２を取得する。また、加算器１１１から出
力されるａｒｄｙ３信号を取得する入力ポートを備えている。加算器１１２は、ａｒｄｙ３信号が有効であるときに加算動作を実行し、出力ａｄａｔａ４を出力する。また、加算器１１２は、次段の加算器１１６等にイネーブル信号ａｒｄｙ４信号を出力する。
【００４１】
加算器１１６は、ａｄａｔａ４を取得するＡポートと、ａｒｄｙ４信号を取得するｖａｌｉｄポートとセレクタ１１５の出力信号を取得するＢポートを備えている。また、加算器１１６は、加算演算結果ａｄａｔａ５（ＲＥＳＵＬＴ）を出力する出力ポートと、次段に接続されている論理積回路１１７にイネーブル信号ａｒｄｙ５信号を出力するポートを有する。加算器１１６は、ａｒｄｙ４信号が有効のときにａｄａｔａ４とセレクタ１１５の出力（ａｄａｔａ５又は値０）の加算を行う。
【００４２】
加算器１０８〜１１２，１１６は、６４ビット浮動小数点の加算器を用いているが、６４ビット浮動小数点の加算器に限定するものではなく加算ができれば固定小数点型であってもよい。
【００４３】
本例では、乗算器１０２〜１０７はレイテンシが９であり、加算器１０８〜１１２，１１６はレイテンシが１２である。
１２進カウンタ１１３（レイテンシカウンタ）は、加算器１１６の出力レイテンシを計測（カウント）するカウンタであり、加算器１１２の出力データイネーブル信号であるａｒｄｙ４信号をカウントし１２カウントすると、ｃａｒｒｙ信号であるｃｏｕｎｔ＿ｕｐを「１」にする。なお、本例では加算器１１６のレイテンシが１２であるので１２進カウンタを用いているが、レイテンシが異なる場合はレイテンシに合わせたカウンタにすることで対応できる。
【００４４】
２２進カウンタ１１４は、１２進カウンタ１１３の出力であるｃｏｕｎｔ＿ｕｐ信号の「１」を取得してカウントするカウンタである。積和演算回路１０１では、前述したように、１３２×１３２の行列積演算が実行される場合には、１２×２２＝２６４クロックに１回の割合で１２個の出力が得られるため、１２進カウンタ１１３と２２進カウンタ１１４の組合せにより上記２６４クロックを計測している。
【００４５】
そして、２２進カウンタ１１４は、２２回に１回、演算結果を選択出力するための信号(ｃｏｕｎｔ０)を出力する。
このカウンタ１１４のカウント数は、行列サイズに応じて決定すればよい。
【００４６】
セレクタ１１５は、２入力から１つを選択するセレクタであり、加算器１１６への入力データを選択するセレクタである。加算器１１６のＢポートへは、例えばｃｏｕｎｔ０信号が「１」の場合は値「０」を選択し、それ以外の場合は加算器１１６の演算結果であるフィードバック値ａｄａｔａ５を選択する。
【００４７】
論理積回路１１７は、積和演算結果の出力タイミングを選択する。加算器１１６の出力データが有効であることを示すＲＤＹ信号を生成する。
図６及び図７は、図１の積和演算回路１０１において１組の行列演算を実行した場合の動作を示す動作タイミングチャートである。図６は、積和演算回路１０１への行列データの入力から加算器１１２（ａｄｄ４）からの出力までのタイミング、図７は、加算器１１２（ａｄｄ４）の出力から積和演算回路１０１からの出力までのタイミングを示している。
【００４８】
まず、図６において、積和演算回路１０１へのデータ入力タイミングはグループ１とグループ２がある。
グループ１は、乗算器１０２〜１０５への入力のグループであり、ＶＡＬＩＤ信号＝１
で入力が行われる。
【００４９】
グループ２は、乗算器１０６及び１０７への入力のグループであり、ＶＡＬＩＤ＿ＬＡＴ１２信号＝１で入力が行われる。グループ２に属する入力データ群は、後続の加算器が１段少ないため、加算器１１２（ａｄｄ４）の入力タイミングを合わせるために、加算器１１１（ａｄｄ３）のレイテンシの分＝１２クロック分遅延させられて、乗算器１０６及び１０７への入力が行われる。
【００５０】
行列Ａの入力データＡ０〜Ａ５と行列Ｂの入力データＢ０〜Ｂ５の関係は、図３等で説明した通りである。
乗算器１０２〜１０７のレイテンシ＝９、加算器１０８〜１１０のレイテンシ＝１２、加算器１１１のレイテンシ＝１２、及び加算器１１２のレイテンシ＝１２であるため、乗算器１０２〜１０７への入力から加算器１１２からの出力までのレイテンシは、９＋１２＋１２＋１２＝４５である。従って、加算器１１２（ａｄｄ４）は、クロックＣＬＫ＝０でグループ１の入力が開始された後、クロックＣＬＫ＝４５で有効データを出力し、データ有効を示す信号ａｒｄｙ４信号＝１を出力する。
【００５１】
次に、図７において、クロックＣＬＫ＝４５で加算器１１２（ａｄｄ４）のデータが有効（ａｒｄｙ４信号＝１）になると、加算器１１６（ａｄｄ５）での加算が開始され、これと同時に、１２進カウンタ１１３（レイテンシカウンタ：ｃｏｕｎｔｅｒ０）でのカウント動作が開始される。
【００５２】
最終段の加算器１１６（ａｄｄ５）はａｒｄｙ４信号＝１の間、加算動作を行う。具体的な加算動作については、図２及び図３で説明した通りである。
１２進カウンタ１１３（レイテンシカウンタ：ｃｏｕｎｔｅｒ０）でのカウント値が１１になるとｃｏｕｎｔ＿ｕｐ信号＝１となり、２２進カウンタ１１４（ｃｏｕｎｔｅｒ１）がカウントされる（図７のクロックＣＬＫ＝６７のタイミング）。
【００５３】
ａｒｄｙ４信号＝１のとき２２進カウンタ１１４（ｃｏｕｎｔｅｒ１）のカウント値が０になるとｃｏｕｎｔ０信号＝１となり、積和演算結果の出力（ａｄａｔａ５／ＲＥＳＵＬＴ）が有効であることを示すＲＤＹ信号＝１が出力される（図７のクロックＣＬＫ＝３０９のタイミング）。このタイミングは前述したように、加算器１１２が出力を開始してから１２×２２＝２６４クロック目である。図１の積和演算回路１０１に入力されてからのクロック数は、前記レイテンシ４５＋２６４＝３０９クロックである。
【００５４】
積和演算結果の出力（ａｄａｔａ５／ＲＥＳＵＬＴ）が有効であることを示すＲＤＹ信号は、ａｒｄｙ４信号＝１となってから２６４クロック毎にＲＤＹ＝１となり、そこから１２クロック間ＲＤＹ＝１となる。これにより、前述した２６４クロック毎に１２個ずつの積和演算結果データ（図７のＲ０〜Ｒ１１）が出力される。
この間、セレクタ１１５は、値０を選択し、加算器１１６が実質的な加算動作を行わないように制御する。
【００５５】
図１の構成における演算性能について考察する。
本実施形態では、前述したように、加算器１１６（ａｄｄ５）のレイテンシ＝１２を考慮した積和演算回路設計により、１３２行×１３２列のサイズを有する行例ＡとＢについてのＡ×Ｂ演算は、前述したように２６４クロック毎に１２個の演算結果を得ることができる。これから、本実施形態による１３２×１３２行列の６並列ＦＰＧＡ処理時間は、２６４クロック×１３２行／１２×１３２列＝３８３，３２８クロックとなる。
【００５６】
一方、１３２×１３２行列の積和計算の逐次処理時間は、各乗算及び加算のスループット＝１として、１３２×１３２×１３２＝２，２９９，９６８クロックである。
従って、本実施形態は、３８３，３２８／２，２９９，９６８＝１／６となり、並列数に対応する積和演算性能を達成することができる。これは、部分的な積和演算結果を積算する最終段の加算器１１６（ａｄｄ５）のスタートアップステージの全段に異なった行の部分積和結果を溜め込み、それらの部分的な積和演算結果の積算を２つのカウンタ１１３及び１１４によって制御することにより、最終段のａｄｄ５加算器及び積和演算器のレイテンシを最小に隠蔽させることが可能となり、これにより演算器並列の並列処理性能が最大限に発揮されるためである。
【００５７】
最終段の加算器１１６（ａｄｄ５）がもし無いと仮定すると、加算器１１２（ａｄｄ４）の結果をメモリに格納する必要が生じる。この場合、Ａ×Ｂの部分積和が演算されるごとにレイテンシ４５クロックがかかる。その上で、例えば本実施形態と同じように６要素ごとに計算が実行された場合、（４５＋２６４）クロック×１３２行／１２×１３２列＝４４８，６６８クロックがかかる。また、ａｄｄ５相当の演算のために、２２回×１３２行×１３２列＋１２＝３８３，３４０クロックがかかる。従って、全体では、４４８，６６８＋３８３，３４０＝８３２，００８クロックがかかる。逐次演算との比較は、８３２，００８／２，２９９，９６８＝１／２．７６となってしまい、演算性能が大幅にダウンすることがわかる。
これにより、本発明の実施形態の演算性能が高いことは明らかである。
【００５８】
図８は、図１の構成を有する行列積和演算回路の、ＦＰＧＡへの具体的な実装例を示した図である。ＭＡＴ＿ＣＡＬＣとして示されたブロックが図１に対応しており、これに、メモリ転送を制御するインタフェース回路、演算データ制御を実行する回路等が実装される。
【００５９】
図９は、図１又は図８の構成を有するＦＰＧＡを設計する装置の構成図である。
この設計装置９０１は、入力手段９０２からの配置データの入力に従って、ＦＰＧＡ９０４（図１又は図８に対応）に対して演算回路の配置指示を行う配置手段９０３を有する。
【００６０】
図１０は、図９の配置手段９０３が実行する配置動作を示す動作フローチャートである。
利用者はまず、図９の入力手段９０２から、クロック速度を入力する（ステップＳ１００１）。例えば、クロック速度＝１ＧＨｚと入力されたとする。
【００６１】
配置手段９０３は、回路処理速度データベース１００１より、対象となる加算回路の処理速度を抽出し、レイテンシを算出する（ステップ１００２）。図１１は、回路速度データベース１００１のデータ構成例を示した図である。演算回路毎に処理時間が記録されている。ここでは、加算回路が１６ｎｓの処理時間を要すると認識できる。
【００６２】
レイテンシは、加算回路が何クロックで処理できるかという性能を表し、
レイテンシ＝加算回路の処理時間／（１／クロック）
となる。本実施の形態では、上記のようにクロック：１ＧＨｚ、加算回路の処理時間：１６ｎｓなので、
レイテンシ＝１６ｎｓ／（１／１ＧＨｚ）
＝１６
となる。
【００６３】
続いて、配置手段９０３は、算出されたレイテンシ＝１６に合わせて、入力数を設定し、回路構成を生成する（ステップＳ１００３）。
そして、配置手段９０３は、ＦＰＧＡ９０４（図９）に対して、回路の再構築を指示する（ステップＳ１００４）。
【００６４】
実施例では積和演算回路について説明しているが、同一の演算アルゴリズムによって多数の独立した演算結果を得る場合には、例えば図１において入力の乗算器１０２の一部または全部を他の演算器（加減算器、除算器、あるいは複数の演算器の組合せなど）で置き換えて構成される、積和と単純加算との混合演算手段あるいは多数の数値の総和を計算する積算手段あるいはその他の演算手段としても、本発明が適用可能である。
【００６５】
本発明は、上記実施の形態に限定されるものでなく、本発明の要旨を逸脱しない範囲内で種々の改良、変更が可能である。
【図面の簡単な説明】
【００６６】
【図１】積和演算回路の実施形態を示す構成図である。
【図２】実施形態の積和演算方式の説明図（Ｎ＝１３２（１１ブロック）の場合）である。
【図３】実施形態の説明図（Ｎ＝１３２（１１ブロック）の場合）である。
【図４】実施形態の積和演算方式の説明図（Ｎ＝６６（６ブロック）の場合）である。
【図５】演算器の機能の説明図である。
【図６】実施形態に示す積和演算回路の動作タイミングチャート（その１）である。
【図７】実施形態に示す積和演算回路の動作タイミングチャート（その２）である。
【図８】実施形態に示す積和演算回路が構成されるＦＰＧＡの全体ブロック図である。
【図９】本実施形態のＦＰＧＡを設計する装置の構成図である。
【図１０】配置動作を示す動作フローチャートである。
【図１１】回路処理速度データベースのデータ構成図である。
【図１２】従来の積和演算方式の説明図である。
【符号の説明】
【００６７】
１０１ 積和演算回路
１０２〜１０７ 乗算器
１０８〜１１２，１１６ 加算器
１１３ １２進カウンタ（レイテンシカウンタ）
１１４ ２２進カウンタ
１１５ セレクタ
１１７ 論理回路
９０１ ＦＰＧＡ設計装置
９０２ 入力手段
９０３ 配置手段
９０４ ＦＰＧＡ
【技術分野】
【０００１】
本発明は、行列の積和演算の技術に関する。
【背景技術】
【０００２】
近年、ハードウェアにより行列の積和演算回路を実現する場合に、回路規模を縮小するとともに演算時間の短縮が求められている。
例えば、図１２に示されるように、それぞれ１３２行×１３２列の行列ＡとＢの積Ａ×Ｂが算出される場合、通常の演算方法では、行列Ｂの列（ｊ）が固定され、行列Ａの行（ｉ）がｉ＝０〜１３１の順で演算され、行列Ｃの列（ｊ）の解が算出される。
【０００３】
次に、行列Ｂの列（ｊ）が＋１された後、行列Ａの行（ｉ）がｉ＝０〜１３１の順で演算されることにより、行列Ｃの次の列（ｊ）の解が算出される。
この演算方法からわかるように、行列Ａ×Ｂの演算には、膨大な量の積和演算が必要となる。
【０００４】
この演算時間を短縮するために、例えば下記特許文献１では、行列とベクトルの積を複数の乗算器と加算器で求める積和演算回路の技術が開示されている。
また、下記特許文献２では、３×３の空間積和を求める回路において、最初の３個の部分積和が算出されて結果がシフトレジスタに入力され、その後、別の積和が２５５回計算された後に次の３個の積和が計算され、シフトレジスタ内の結果と加算されて空間積和が出力される技術が開示されている。
【特許文献１】特開２００３−５８８７６号公報
【特許文献２】特公平７−３８２１７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、上記特許文献１に記載の従来技術では、複数の乗算器と加算器が使用されるため、行列が大きくなると回路規模が縮小できないという問題点を有している。
また、上記特許文献２に記載の従来技術では、行の大きさに対応したシフトレジスタを用意する必要があるため、数値シミュレーションで用いられる要素数の多い行列の積和演算においてシフトレジスタの段数で対応するのは現実的でないという問題点を有している。
【課題を解決するための手段】
【０００６】
本発明の課題は、回路の利用効率および演算性能を向上させることが可能な積和演算回路を提供することにある。
本発明の第１の態様は、複数の演算回路を並列処理させることにより積和演算を行う積和演算回路を前提とする。
【０００７】
並列演算手段（１０２〜１１２）は、所定行分を並列入力としたデータを並列演算処理する。
積算手段（１１３〜１１７）は、並列演算手段に並列入力される行数に対応したレイテンシを有し、並列演算手段の演算結果を積算する。この積算手段は例えば、並列演算手段に並列入力される行数と同じレイテンシを有する。
【０００８】
本発明の第２の態様は、複数の演算回路を並列処理させることにより積和演算を行う積和演算回路をフイールド・プログラマブル・ロジツクアレイに配置指示を行う設計装置又
は設計プログラムを前提とする。
【０００９】
そして、対象のフイールド・プログラマブル・ロジツクアレイに対し、並列処理された演算結果を加算する積算器のレイテンシを元に求められる所定行分を1ブロックとしたデータを並列演算処理する並列演算回路を配置する指示を行う配置手段（９０３）を含む。この配置手段は例えば、並列処理された演算結果を加算する積算器のレイテンシと同じ所定行分を1ブロックとしたデータを並列演算処理する並列演算回路の配置指示を行う。
【発明の効果】
【００１０】
本発明では、加算器等によって実現される積算手段のレイテンシを利用することにより、シフトレジスタ無しに効率的な並列積和演算を実現することが可能となる。これにより、レイテンシをカウントするカウンタのカウント数のみの変更で、レイテンシを処理時間から隠蔽しかつ、行列要素の大きさに応じた積和演算を可能にする。
【発明を実施するための最良の形態】
【００１１】
以下図面に基づいて、本発明の実施形態について詳細に説明する。
図１は、本発明による積和演算回路の実施形態を示す構成図である。
通常の行列演算、例えば行列Ａ（１３２×１３２）と行列Ｂ（１３２×１３２）の積の演算では、図１３で説明したように、下記数１式に示す計算が実行されることにより、行列Ｃ（１３２×１３２）の１要素（例えばＣ０，０）が算出され同様に他の要素も算出される。
【数１】
【００１２】
ところが、上記１３２×１３２のようにサイズ大きい多入力の積和演算がＦＰＧＡ（Field Programmable Gate Array）やＣＰＬＤ（Complex Programmable Logic Device）のようなプログラマブルデバイスにより実現される場合、積和演算の実行のために並列に１３２個の乗算器を設けなければならない。しかし、単に並列化をすると演算器の数が多くなり回路規模が膨大なものとなるため、実際にハードウェアとしてインプリメントするには複数のプログラマブルデバイスが必要となってしまう。
【００１３】
そこで、回路規模を縮小して１３２×１３２の演算を行うためには、演算器の数を減らしてインプリメントしなければならない。そのために、例えば下記数２式に基づいて回路規模が削減される。
【数２】
【００１４】
しかしこの場合、積和演算を実行する際に、最終段の加算器部分のレイテンシの存在により連続して演算が実行できない。例えば、上記数２式に基づいて並列数が１３２から６に削減された場合、演算性能は、６／１３２＝１／２２になるのではなく、連続演算ができない分が加わって１／２６４程度に落ちてしまう。
【００１５】
そこで、本発明の実施形態では、図１に示される積和演算回路１０１の構成により、並列数の削減比にほぼ等しい演算性能（＝１／２２）が達成されるものである。
積和演算回路１０１は、乗算器１０２（ｍｕｌ０）、１０３（ｍｕｌ１）、１０４（ｍｕｌ２）、１０５（ｍｕｌ３）、１０６（ｍｕｌ４）、１０７（ｍｕｌ５）と、加算器１０８（ａｄｄ０）、１０９（ａｄｄ１）、１１０（ａｄｄ２）、１１１（ａｄｄ３）、１１２（ａｄｄ４）、１１６（ａｄｄ５）、１２進カウンタ１１３（レイテンシカウンタ）、２２進カウンタ１１４、セレクタ１１５、論理積回路１１７（ａｎｄ０）を備え、１３２×１３２の行列演算を実行する。
【００１６】
本実施形態では、積和演算回路１０１の最終段の加算器１１６（ａｄｄ５）のレイテンシ（＝１２）を考慮し、連続演算を可能にするため、行列Ａの１２行を１ブロックとして演算が行われる。また、行列Ａ、行列Ｂ共に６要素ごとに分割され、６要素ごとに演算が行われる。
【００１７】
図２〜図５を用いて、上記分割処理について説明する。
例えば行列Ａ及びＢともに、１３２行×１３２列のサイズを有するとする。
図２の例では、まず、行列Ａについて、その行が６要素ごとの部分行ベクトルに分割される。例えば行ｉ＝０は、「（０，０）（０，１）（０，２）（０，３）（０，４）（０，５）」「（０，６）（０，７）（０，８）（０，９）（０，１０）（０，１１）」・・・「（０，１２０）（０，１２１）（０，１２２）（０，１２３）（０，１２４）（０，１２５）」「（０，１２６）（０，１２７）（０，１２８）（０，１２９）（０，１３０）（０，１３１）」のように分割される。同様に行ｉ＝０以外の各行ｉ＝１〜１３１についても、６要素ずつの部分行ベクトルに分割される。
【００１８】
次に、行列Ｂについて、その列が６要素ごとの部分列ベクトルに分割される。例えば、列ｊ＝０は、「（０，０）（１，０）（２，０）（３，０）（４，０）（５，０）」「（６，０）（７，０）（８，０）（９，０）（１０，０）（１１，０）」・・・「（１２０，０）（１２１，０）（１２２，０）（１２３，０）（１２４，０）（１２５，０）」「（１２６，０）（１２７，０）（１２８，０）（１２９，０）（１３０，０）（１３１，０）」のように分割される。同様に列ｊ＝０以外の各列ｊ＝１〜１３１についても、６要素ずつの部分列ベクトルに分割される。
【００１９】
そして、図２に示す矢印の示す順に行列Ａと行列Ｂの要素データがブロック単位で入力されて、並列積和演算が実行される。
最初は、行列Ａの部分行ベクトル「（０，０）（０，１）（０，２）（０，３）（０，４）（０，５）」と行列Ｂの部分列ベクトル「（０，０）（１，０）（２，０）（３，０）（４，０）（５，０）」の並列積和演算が行われる。この並列積和演算は図１の１０２〜１１２の回路群によって実行される。そして、その並列積和演算結果は、０行０列の積和演算出力Ｃ0,0 のための部分的な演算結果として、加算器１１６（ａｄｄ５）に溜め込まれる。
【００２０】
このａｄｄ５は、レイテンシ＝１２を有するため、１２回分の演算結果を溜め込むことができる。
次に、行列Ａの部分行ベクトル「（１，０）（１，１）（１，２）（１，３）（１，４）（１，５）」と行列Ｂの部分列ベクトル「（０，０）（１，０）（２，０）（３，０）（４，０）（５，０）」の並列積和演算が行われる。その並列積和演算結果は、１行０列の積和演算出力Ｃ1,0 のための部分的な演算結果として、ａｄｄ５に溜め込まれる。
【００２１】
以下同様にして、行列Ａの部分行ベクトルが、ブロック０の最終行ｉ＝１１まで処理される、つまり部分行ベクトル「（１１，０）（１１，１）（１１，２）（１１，３）（１１，４）（１１，５）」まで処理される。
【００２２】
以上の動作の様子を、図３のｃｌｏｃｋ＝１〜１２として示す。同図において、ピリオドで区切られた数値において、左側の数値は行番号を示し、右側の数値は列番号を示す。そして例えば、Ａ０とｃｌｏｃｋ＝１とで決まる枠内に記載される「０．０」は、ｃｌｏ
ｃｋ＝１のタイミングにおいて入力値Ａ０（図１参照）として、行列データＡの０行０列の要素値が入力されることを示す。
【００２３】
図３からわかるように、入力Ｂ０〜Ｂ５（図１参照）の各値は、ｃｌｏｃｋ＝１〜１２の１２クロックの間一定値とされ、入力Ａ０〜Ａ５のみが順次変更されてゆく。このクロック数＝１２は、図１の加算器１１６（ａｄｄ５）のレイテンシに一致するように設定される。
【００２４】
そして、ｃｌｏｃｋ＝１〜１２の１２回の動作により、０行０列〜１１行０列の各積和演算出力Ｃ０,0 〜Ｃ11,0 のための１回目の１２個の部分的な演算結果Ｓ０５〜Ｓ１１５（図３参照）がａｄｄ５に溜め込まれる。
【００２５】
ｃｌｏｃｋ＝１２の動作が完了したら、図３に示されるように、行列Ｂの部分列ベクトルが次の部分列ベクトル「（６，０）（７，０）（８，０）（９，０）（１０，０）（１１，０）」に変更される。
【００２６】
そして、行列Ａの部分行ベクトル「（０，６）（０，７）（０，８）（０，９）（０，１０）（０，１１）」と行列Ｂの部分列ベクトル「（６，０）（７，０）（８，０）（９，０）（１０，０）（１１，０）」の並列積和演算が行われる。その演算結果Ｓ０１１（図３参照）は、加算器１１６（ａｄｄ５）において、その出力値ａｄａｔａ５（図１）として出力されている０行０列の積和演算出力Ｃ0,0 の演算のための１２クロック前の並列積和演算結果Ｓ０５と加算されて、その加算結果Ｓ０５＋Ｓ０１１が再びａｄｄ５に溜め込まれる。
【００２７】
次に、行列Ａの部分行ベクトル「（１，６）（１，７）（１，８）（１，９）（１，１０）（１，１１）」と行列Ｂの部分列ベクトル「（６，０）（７，０）（８，０）（９，０）（１０，０）（１１，０）」の並列積和演算が行われる。その演算結果Ｓ１１１（図３参照）は、加算器１１６（ａｄｄ５）において、その出力値ａｄａｔａ５（図１）として出力されている１行０列の積和演算出力Ｃ1,０ の演算のための１２クロック前の並列積和演算結果Ｓ１５と加算されて、その加算結果Ｓ１５＋Ｓ１１１が再びａｄｄ５に溜め込まれる。
【００２８】
以下同様にして、行列Ａの部分行ベクトルが、ブロック０の最終行ｉ＝１１まで処理される、つまり部分行ベクトル「（１１，６）（１１，７）（１１，８）（１１，９）（１１，１０）（１１，１１）」まで処理される。
【００２９】
以上の動作の様子を、図３のｃｌｏｃｋ＝１３〜２４として示す。このｃｌｏｃｋ＝１３〜２４の１２回の動作により、０行０列〜１１行０列の各積和演算出力Ｃ０,0 〜Ｃ11,0 のための２回目の１２個の部分的な演算結果Ｓ０５＋Ｓ０１１〜Ｓ１１５＋Ｓ１１１１（図３参照）がａｄｄ５に溜め込まれる。
【００３０】
ｃｌｏｃｋ＝１２の動作が完了したら、図３に示されるように、行列Ｂの部分列ベクトルが次の部分列ベクトル「（１２，０）（１３，０）（１４，０）（１５，０）（１６，０）（１７，０）」に変更される。
【００３１】
以上の１２クロックずつの動作が２２回繰り返される、即ち１２×２２＝２６４クロック分の動作が繰り返されることによって、０行０列〜１１行０列の１２個の積和演算出力Ｃ０,0 〜Ｃ11,0 が確定する。図３では、行列Ａ×行列Ｂ＝行列Ｃの演算において、ｂｌｏｃｋ０のブロックにおける１２個のデータが確定する様子が示されている。
【００３２】
次に、ブロック０と同様にブロック１の演算が行われ、以下順次ブロック１０までの１１ブロック分の演算が行われる。また、演算結果は列順で確定するため、結果順にＳＤＲＡＭメモリなどへ転送して記録される。
【００３３】
上述の説明は、例えば行列Ａ及びＢともに１３２行×１３２列のサイズを有する場合の例についてのものであるが、そのほかに行列Ａ及びＢが例えば６６行×６６列のサイズを有するような場合には、図１の加算器１１６（ａｄｄ５）のレイテンシに対応させて各行列要素を１ブロック＝１２要素ずつに分割した場合、余りが出てしまう。
【００３４】
このような場合には、図４に示されるように、各行列要素数を１２で割り切れるように拡張し、拡張部分には値０を有するｄｕｍｍｙ（ダミー）値を補充すればよい。
次に図５は、図１を構成する各演算器１０２〜１１２、及び１１６の機能を示す図である。
【００３５】
基本的に、各演算器は３入力、２出力のポートを備えている。入力ポートは、データを入力する２ポートと、演算を有効にするイネーブル信号を取得する１ポートの計３ポートを有する。出力ポートは、データを出力するポートと、次段に接続される演算を有効にするイネーブル信号を出力するための１ポートの計２ポートを有する。また、演算器内に示されている「数値１」はスループットを示し、「数値２」はレイテンシを示している。
【００３６】
図１の乗算器１０２〜１０７は、行列Ａの行ベクトルごとの各要素Ａ０〜Ａ５と行列Ｂの各要素Ｂ０〜Ｂ５を取得する２つの各入力ポートと、乗算器の演算を行うかどうかを決定するイネーブル信号を取得する各ポートと、次段に接続される加算器１０８への出力信号（ｍｄａｔａ０〜５）を出力する各出力ポートと、加算器１０８〜１１０の各演算を有効にすることを通知する信号（ｍｒｄｙ０，ｍｒｄｙ２，ｍｒｄｙ４）を出力するポートを備えている。乗算器１０２は、イネーブル信号が有効を示しているときに、入力ポートＡ０、Ｂ０に入力された要素を乗算する。
【００３７】
本例では乗算器１０２〜１０７は６４ビット浮動小数点の乗算器を用いているが、６４ビット浮動小数点の乗算器に限定するものではなく乗算ができれば固定小数点型であってもよい。
【００３８】
加算器１０８〜１１０はそれぞれ、乗算器１０２と１０３、乗算器１０４と１０５、及び乗算器１０６と１０７の各出力ポートと接続される各入力ポートを備え、乗算結果であるｍｄａｔａ０とｍｄａｔａ１、ｍｄａｔａ２とｍｄａｔａ３、及びｍｄａｔａ４とｍｄａｔａ５を取得する。また、乗算器１０２，１０４，１０６からそれぞれ出力されるｍｒｄｙ０，ｍｒｄｙ２，ｍｒｄｙ４信号をそれぞれ取得する各入力ポートを備えている。加算器１０８〜１１０は、ｍｒｄｙ０，ｍｒｄｙ２，ｍｒｄｙ４がそれぞれ有効であるときに各加算動作を実行し、各出力ａｄａｔａ０〜２を出力する。
【００３９】
加算器１０８は、次段の加算器１１１にイネーブル信号ａｒｄｙ０信号を出力する。
加算器１１１は、加算器１０８と１０９の各出力ポートと接続される各入力ポートを備え、加算結果であるａｄａｔａ０とａｄａｔａ１を取得する。また、加算器１０８から出力されるａｒｄｙ０信号を取得する入力ポートを備えている。加算器１１１は、ａｒｄｙ０信号が有効であるときに加算動作を実行し、出力ａｄａｔａ３を出力する。また、加算器１１１は、次段の加算器１１２にイネーブル信号ａｒｄｙ３信号を出力する。
【００４０】
加算器１１２は、加算器１１１と１１０の各出力ポートと接続される各入力ポートを備え、加算結果であるａｄａｔａ３とａｄａｔａ２を取得する。また、加算器１１１から出
力されるａｒｄｙ３信号を取得する入力ポートを備えている。加算器１１２は、ａｒｄｙ３信号が有効であるときに加算動作を実行し、出力ａｄａｔａ４を出力する。また、加算器１１２は、次段の加算器１１６等にイネーブル信号ａｒｄｙ４信号を出力する。
【００４１】
加算器１１６は、ａｄａｔａ４を取得するＡポートと、ａｒｄｙ４信号を取得するｖａｌｉｄポートとセレクタ１１５の出力信号を取得するＢポートを備えている。また、加算器１１６は、加算演算結果ａｄａｔａ５（ＲＥＳＵＬＴ）を出力する出力ポートと、次段に接続されている論理積回路１１７にイネーブル信号ａｒｄｙ５信号を出力するポートを有する。加算器１１６は、ａｒｄｙ４信号が有効のときにａｄａｔａ４とセレクタ１１５の出力（ａｄａｔａ５又は値０）の加算を行う。
【００４２】
加算器１０８〜１１２，１１６は、６４ビット浮動小数点の加算器を用いているが、６４ビット浮動小数点の加算器に限定するものではなく加算ができれば固定小数点型であってもよい。
【００４３】
本例では、乗算器１０２〜１０７はレイテンシが９であり、加算器１０８〜１１２，１１６はレイテンシが１２である。
１２進カウンタ１１３（レイテンシカウンタ）は、加算器１１６の出力レイテンシを計測（カウント）するカウンタであり、加算器１１２の出力データイネーブル信号であるａｒｄｙ４信号をカウントし１２カウントすると、ｃａｒｒｙ信号であるｃｏｕｎｔ＿ｕｐを「１」にする。なお、本例では加算器１１６のレイテンシが１２であるので１２進カウンタを用いているが、レイテンシが異なる場合はレイテンシに合わせたカウンタにすることで対応できる。
【００４４】
２２進カウンタ１１４は、１２進カウンタ１１３の出力であるｃｏｕｎｔ＿ｕｐ信号の「１」を取得してカウントするカウンタである。積和演算回路１０１では、前述したように、１３２×１３２の行列積演算が実行される場合には、１２×２２＝２６４クロックに１回の割合で１２個の出力が得られるため、１２進カウンタ１１３と２２進カウンタ１１４の組合せにより上記２６４クロックを計測している。
【００４５】
そして、２２進カウンタ１１４は、２２回に１回、演算結果を選択出力するための信号(ｃｏｕｎｔ０)を出力する。
このカウンタ１１４のカウント数は、行列サイズに応じて決定すればよい。
【００４６】
セレクタ１１５は、２入力から１つを選択するセレクタであり、加算器１１６への入力データを選択するセレクタである。加算器１１６のＢポートへは、例えばｃｏｕｎｔ０信号が「１」の場合は値「０」を選択し、それ以外の場合は加算器１１６の演算結果であるフィードバック値ａｄａｔａ５を選択する。
【００４７】
論理積回路１１７は、積和演算結果の出力タイミングを選択する。加算器１１６の出力データが有効であることを示すＲＤＹ信号を生成する。
図６及び図７は、図１の積和演算回路１０１において１組の行列演算を実行した場合の動作を示す動作タイミングチャートである。図６は、積和演算回路１０１への行列データの入力から加算器１１２（ａｄｄ４）からの出力までのタイミング、図７は、加算器１１２（ａｄｄ４）の出力から積和演算回路１０１からの出力までのタイミングを示している。
【００４８】
まず、図６において、積和演算回路１０１へのデータ入力タイミングはグループ１とグループ２がある。
グループ１は、乗算器１０２〜１０５への入力のグループであり、ＶＡＬＩＤ信号＝１
で入力が行われる。
【００４９】
グループ２は、乗算器１０６及び１０７への入力のグループであり、ＶＡＬＩＤ＿ＬＡＴ１２信号＝１で入力が行われる。グループ２に属する入力データ群は、後続の加算器が１段少ないため、加算器１１２（ａｄｄ４）の入力タイミングを合わせるために、加算器１１１（ａｄｄ３）のレイテンシの分＝１２クロック分遅延させられて、乗算器１０６及び１０７への入力が行われる。
【００５０】
行列Ａの入力データＡ０〜Ａ５と行列Ｂの入力データＢ０〜Ｂ５の関係は、図３等で説明した通りである。
乗算器１０２〜１０７のレイテンシ＝９、加算器１０８〜１１０のレイテンシ＝１２、加算器１１１のレイテンシ＝１２、及び加算器１１２のレイテンシ＝１２であるため、乗算器１０２〜１０７への入力から加算器１１２からの出力までのレイテンシは、９＋１２＋１２＋１２＝４５である。従って、加算器１１２（ａｄｄ４）は、クロックＣＬＫ＝０でグループ１の入力が開始された後、クロックＣＬＫ＝４５で有効データを出力し、データ有効を示す信号ａｒｄｙ４信号＝１を出力する。
【００５１】
次に、図７において、クロックＣＬＫ＝４５で加算器１１２（ａｄｄ４）のデータが有効（ａｒｄｙ４信号＝１）になると、加算器１１６（ａｄｄ５）での加算が開始され、これと同時に、１２進カウンタ１１３（レイテンシカウンタ：ｃｏｕｎｔｅｒ０）でのカウント動作が開始される。
【００５２】
最終段の加算器１１６（ａｄｄ５）はａｒｄｙ４信号＝１の間、加算動作を行う。具体的な加算動作については、図２及び図３で説明した通りである。
１２進カウンタ１１３（レイテンシカウンタ：ｃｏｕｎｔｅｒ０）でのカウント値が１１になるとｃｏｕｎｔ＿ｕｐ信号＝１となり、２２進カウンタ１１４（ｃｏｕｎｔｅｒ１）がカウントされる（図７のクロックＣＬＫ＝６７のタイミング）。
【００５３】
ａｒｄｙ４信号＝１のとき２２進カウンタ１１４（ｃｏｕｎｔｅｒ１）のカウント値が０になるとｃｏｕｎｔ０信号＝１となり、積和演算結果の出力（ａｄａｔａ５／ＲＥＳＵＬＴ）が有効であることを示すＲＤＹ信号＝１が出力される（図７のクロックＣＬＫ＝３０９のタイミング）。このタイミングは前述したように、加算器１１２が出力を開始してから１２×２２＝２６４クロック目である。図１の積和演算回路１０１に入力されてからのクロック数は、前記レイテンシ４５＋２６４＝３０９クロックである。
【００５４】
積和演算結果の出力（ａｄａｔａ５／ＲＥＳＵＬＴ）が有効であることを示すＲＤＹ信号は、ａｒｄｙ４信号＝１となってから２６４クロック毎にＲＤＹ＝１となり、そこから１２クロック間ＲＤＹ＝１となる。これにより、前述した２６４クロック毎に１２個ずつの積和演算結果データ（図７のＲ０〜Ｒ１１）が出力される。
この間、セレクタ１１５は、値０を選択し、加算器１１６が実質的な加算動作を行わないように制御する。
【００５５】
図１の構成における演算性能について考察する。
本実施形態では、前述したように、加算器１１６（ａｄｄ５）のレイテンシ＝１２を考慮した積和演算回路設計により、１３２行×１３２列のサイズを有する行例ＡとＢについてのＡ×Ｂ演算は、前述したように２６４クロック毎に１２個の演算結果を得ることができる。これから、本実施形態による１３２×１３２行列の６並列ＦＰＧＡ処理時間は、２６４クロック×１３２行／１２×１３２列＝３８３，３２８クロックとなる。
【００５６】
一方、１３２×１３２行列の積和計算の逐次処理時間は、各乗算及び加算のスループット＝１として、１３２×１３２×１３２＝２，２９９，９６８クロックである。
従って、本実施形態は、３８３，３２８／２，２９９，９６８＝１／６となり、並列数に対応する積和演算性能を達成することができる。これは、部分的な積和演算結果を積算する最終段の加算器１１６（ａｄｄ５）のスタートアップステージの全段に異なった行の部分積和結果を溜め込み、それらの部分的な積和演算結果の積算を２つのカウンタ１１３及び１１４によって制御することにより、最終段のａｄｄ５加算器及び積和演算器のレイテンシを最小に隠蔽させることが可能となり、これにより演算器並列の並列処理性能が最大限に発揮されるためである。
【００５７】
最終段の加算器１１６（ａｄｄ５）がもし無いと仮定すると、加算器１１２（ａｄｄ４）の結果をメモリに格納する必要が生じる。この場合、Ａ×Ｂの部分積和が演算されるごとにレイテンシ４５クロックがかかる。その上で、例えば本実施形態と同じように６要素ごとに計算が実行された場合、（４５＋２６４）クロック×１３２行／１２×１３２列＝４４８，６６８クロックがかかる。また、ａｄｄ５相当の演算のために、２２回×１３２行×１３２列＋１２＝３８３，３４０クロックがかかる。従って、全体では、４４８，６６８＋３８３，３４０＝８３２，００８クロックがかかる。逐次演算との比較は、８３２，００８／２，２９９，９６８＝１／２．７６となってしまい、演算性能が大幅にダウンすることがわかる。
これにより、本発明の実施形態の演算性能が高いことは明らかである。
【００５８】
図８は、図１の構成を有する行列積和演算回路の、ＦＰＧＡへの具体的な実装例を示した図である。ＭＡＴ＿ＣＡＬＣとして示されたブロックが図１に対応しており、これに、メモリ転送を制御するインタフェース回路、演算データ制御を実行する回路等が実装される。
【００５９】
図９は、図１又は図８の構成を有するＦＰＧＡを設計する装置の構成図である。
この設計装置９０１は、入力手段９０２からの配置データの入力に従って、ＦＰＧＡ９０４（図１又は図８に対応）に対して演算回路の配置指示を行う配置手段９０３を有する。
【００６０】
図１０は、図９の配置手段９０３が実行する配置動作を示す動作フローチャートである。
利用者はまず、図９の入力手段９０２から、クロック速度を入力する（ステップＳ１００１）。例えば、クロック速度＝１ＧＨｚと入力されたとする。
【００６１】
配置手段９０３は、回路処理速度データベース１００１より、対象となる加算回路の処理速度を抽出し、レイテンシを算出する（ステップ１００２）。図１１は、回路速度データベース１００１のデータ構成例を示した図である。演算回路毎に処理時間が記録されている。ここでは、加算回路が１６ｎｓの処理時間を要すると認識できる。
【００６２】
レイテンシは、加算回路が何クロックで処理できるかという性能を表し、
レイテンシ＝加算回路の処理時間／（１／クロック）
となる。本実施の形態では、上記のようにクロック：１ＧＨｚ、加算回路の処理時間：１６ｎｓなので、
レイテンシ＝１６ｎｓ／（１／１ＧＨｚ）
＝１６
となる。
【００６３】
続いて、配置手段９０３は、算出されたレイテンシ＝１６に合わせて、入力数を設定し、回路構成を生成する（ステップＳ１００３）。
そして、配置手段９０３は、ＦＰＧＡ９０４（図９）に対して、回路の再構築を指示する（ステップＳ１００４）。
【００６４】
実施例では積和演算回路について説明しているが、同一の演算アルゴリズムによって多数の独立した演算結果を得る場合には、例えば図１において入力の乗算器１０２の一部または全部を他の演算器（加減算器、除算器、あるいは複数の演算器の組合せなど）で置き換えて構成される、積和と単純加算との混合演算手段あるいは多数の数値の総和を計算する積算手段あるいはその他の演算手段としても、本発明が適用可能である。
【００６５】
本発明は、上記実施の形態に限定されるものでなく、本発明の要旨を逸脱しない範囲内で種々の改良、変更が可能である。
【図面の簡単な説明】
【００６６】
【図１】積和演算回路の実施形態を示す構成図である。
【図２】実施形態の積和演算方式の説明図（Ｎ＝１３２（１１ブロック）の場合）である。
【図３】実施形態の説明図（Ｎ＝１３２（１１ブロック）の場合）である。
【図４】実施形態の積和演算方式の説明図（Ｎ＝６６（６ブロック）の場合）である。
【図５】演算器の機能の説明図である。
【図６】実施形態に示す積和演算回路の動作タイミングチャート（その１）である。
【図７】実施形態に示す積和演算回路の動作タイミングチャート（その２）である。
【図８】実施形態に示す積和演算回路が構成されるＦＰＧＡの全体ブロック図である。
【図９】本実施形態のＦＰＧＡを設計する装置の構成図である。
【図１０】配置動作を示す動作フローチャートである。
【図１１】回路処理速度データベースのデータ構成図である。
【図１２】従来の積和演算方式の説明図である。
【符号の説明】
【００６７】
１０１ 積和演算回路
１０２〜１０７ 乗算器
１０８〜１１２，１１６ 加算器
１１３ １２進カウンタ（レイテンシカウンタ）
１１４ ２２進カウンタ
１１５ セレクタ
１１７ 論理回路
９０１ ＦＰＧＡ設計装置
９０２ 入力手段
９０３ 配置手段
９０４ ＦＰＧＡ
【特許請求の範囲】
【請求項１】
複数の演算回路を並列処理させることにより積和演算を行う積和演算回路であって、
所定行分を並列入力としたデータを並列演算処理する並列演算手段と、
前記並列演算手段に並列入力される行数に対応したレイテンシを有し、前記並列演算手段の演算結果を積算する積算手段と、
を含むことを特徴とする積和演算回路。
【請求項２】
前記積算手段は、前記並列演算手段に並列入力される行数と同じレイテンシである、
ことを特徴とする請求項１に記載の積和演算回路。
【請求項３】
複数の演算回路を並列処理させることにより積和演算を行う積和演算回路をフイールド・プログラマブル・ロジツクアレイに配置指示を行う設計装置であって、
対象のフイールド・プログラマブル・ロジツクアレイに対し、並列処理された演算結果を加算する積算器のレイテンシを元に求められる所定行分を1ブロックとしたデータを並列演算処理する並列演算回路を配置する指示を行う配置手段を含む、
ことを特徴とする設計装置。
【請求項４】
前記配置手段は、並列処理された演算結果を加算する積算器のレイテンシと同じ所定行分を1ブロックとしたデータを並列演算処理する並列演算回路の配置指示を行う、
ことを特徴とする請求項３に記載の設計装置。
【請求項５】
コンピュータに、複数の演算回路を並列処理させることにより積和演算を行う積和演算回路をフイールド・プログラマブル・ロジツクアレイに配置指示を行わせる設計プログラムであって、
前記コンピュータを、
対象のフイールド・プログラマブル・ロジツクアレイに対し、並列処理された演算結果を加算する積算器のレイテンシを元に求められる所定行分を1ブロックとしたデータを並列演算処理する並列演算回路を配置する指示を行う配置手段
として機能させることを特徴とする設計プログラム。
【請求項６】
前記配置手段は、並列処理された演算結果を加算する積算器のレイテンシと同じ所定行分を1ブロックとしたデータを並列演算処理する並列演算回路を配置する、
ことを特徴とする請求項５に記載の設計プログラム。
【請求項１】
複数の演算回路を並列処理させることにより積和演算を行う積和演算回路であって、
所定行分を並列入力としたデータを並列演算処理する並列演算手段と、
前記並列演算手段に並列入力される行数に対応したレイテンシを有し、前記並列演算手段の演算結果を積算する積算手段と、
を含むことを特徴とする積和演算回路。
【請求項２】
前記積算手段は、前記並列演算手段に並列入力される行数と同じレイテンシである、
ことを特徴とする請求項１に記載の積和演算回路。
【請求項３】
複数の演算回路を並列処理させることにより積和演算を行う積和演算回路をフイールド・プログラマブル・ロジツクアレイに配置指示を行う設計装置であって、
対象のフイールド・プログラマブル・ロジツクアレイに対し、並列処理された演算結果を加算する積算器のレイテンシを元に求められる所定行分を1ブロックとしたデータを並列演算処理する並列演算回路を配置する指示を行う配置手段を含む、
ことを特徴とする設計装置。
【請求項４】
前記配置手段は、並列処理された演算結果を加算する積算器のレイテンシと同じ所定行分を1ブロックとしたデータを並列演算処理する並列演算回路の配置指示を行う、
ことを特徴とする請求項３に記載の設計装置。
【請求項５】
コンピュータに、複数の演算回路を並列処理させることにより積和演算を行う積和演算回路をフイールド・プログラマブル・ロジツクアレイに配置指示を行わせる設計プログラムであって、
前記コンピュータを、
対象のフイールド・プログラマブル・ロジツクアレイに対し、並列処理された演算結果を加算する積算器のレイテンシを元に求められる所定行分を1ブロックとしたデータを並列演算処理する並列演算回路を配置する指示を行う配置手段
として機能させることを特徴とする設計プログラム。
【請求項６】
前記配置手段は、並列処理された演算結果を加算する積算器のレイテンシと同じ所定行分を1ブロックとしたデータを並列演算処理する並列演算回路を配置する、
ことを特徴とする請求項５に記載の設計プログラム。
【図９】
【図１０】
【図１１】
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１２】
【図１０】
【図１１】
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１２】
【公開番号】特開２００９−２４５３８１（Ｐ２００９−２４５３８１Ａ）
【公開日】平成２１年１０月２２日（２００９．１０．２２）
【国際特許分類】
【出願番号】特願２００８−９３９８５（Ｐ２００８−９３９８５）
【出願日】平成２０年３月３１日（２００８．３．３１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【出願人】（０００２３７１５６）株式会社富士通アドバンストエンジニアリング (100)
【Ｆターム（参考）】
【公開日】平成２１年１０月２２日（２００９．１０．２２）
【国際特許分類】
【出願日】平成２０年３月３１日（２００８．３．３１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【出願人】（０００２３７１５６）株式会社富士通アドバンストエンジニアリング (100)
【Ｆターム（参考）】
[ Back to top ]