(57)【特許請求の範囲】
【請求項１】
加算と乗算を組み合わせた演算を実行して（ｎ＋ｍ）ビット（ｎは１以上の整数であり、ｍは２以上の整数である）の第１計算値を出力する演算部と、
前記第１計算値の下位（ｍ−ｋ）ビット（ｋは１以上、（ｍ−１）以下の整数である）に対してＯＲ演算を実行して１ビットの第２計算値を生成する丸め前処理部と、
前記第１計算値の上位（ｎ＋ｋ）と前記第２計算値を連接した（ｎ＋ｋ＋１）ビットの第３計算値を記憶するレジスタと、
前記第３計算値の最上位ビット及び前記第３計算値の下位（ｋ＋１）ビットから１ビットのキャリービット値を計算し、前記第３計算値の上位ｎビットと前記キャリービット値を加算する丸め後処理部と、
を具備する演算回路。
【請求項２】
前記ｋは１である、請求項１に記載の演算回路。
【請求項３】
前記丸め後処理部は、前記第３計算値の最上位ビットがゼロであり、且つ、前記第３計算値の第ｋビットが１である場合に、及び前記第３計算値の最上位ビットが１であり、且つ、前記第３計算値の第ｋビットが１であり、且つ、前記第３計算値の下位ｋビットが１を含む場合に、キャリービットを１とする、請求項１又は２に記載の演算回路。
【請求項４】
前記丸め後処理部は、前記第３計算値の最上位ビットがゼロであり、且つ、前記第３計算値の第ｋビットが１であり、且つ、前記第３計算値の上位ｎビットの下位（ｎ−１）ビットがゼロを含む場合に、及び前記第３計算値の最上位ビットが１であり、且つ、前記第３計算値の第ｋビットが１であり、且つ、前記第３計算値の下位ｋビットが１を含む場合に、キャリービットを１とする、請求項１又は２に記載の演算回路。
【請求項５】
前記丸め前処理部は、前記演算部によって前記第１計算値の下位（ｍ−ｋ）ビットのうちのいずれかが確定し次第に前記ＯＲ演算を開始する、請求項１乃至４のいずれか１項に記載の演算回路。
【請求項６】
前記演算部は、複数の部分積を計算する部分積計算部、該複数の部分積を２つの部分積に変換する部分積加算部、及び該２つの部分積を加算する最終加算部を備え、
前記最終加算部のビット幅をｇ、前記丸め前処理部への入力ビット幅を（ｍ−ｋ）とすると、ｘ、ｍ、ｋは下記数式を満たす、
ceil(log2(x))≧1.5×ceil(log2(m-k))
ここで、ceil(z)はｚ以上の最小の整数値を表す、請求項１乃至５のいずれか１項に記載の演算回路。
【請求項７】
加算と乗算を組み合わせた演算を実行して（ｎ＋ｍ）ビット（ｎは１以上の整数であり、ｍは２以上の整数である）の第１計算値を出力することと、
前記第１計算値の下位（ｍ−ｋ）ビット（ｋは１以上、（ｍ−１）以下の整数である）に対してＯＲ論理を実行して１ビットの第２計算値を生成することと、
前記第１計算値の上位（ｎ＋ｋ）と前記第２計算値を連接した（ｎ＋ｋ＋１）ビットの第３計算値を記憶することと、
前記第３計算値の最上位ビット及び前記第３計算値の下位（ｋ＋１）ビットから１ビットのキャリービット値を計算し、前記第３計算値の上位ｎビットと前記キャリービット値を加算することと、
を具備する演算方法。
【請求項８】
加算と乗算を組み合わせた演算を実行して（ｎ＋ｍ）ビット（ｎは１以上の整数であり、ｍは２以上の整数である）の第１計算値を出力する演算部と、
前記第１計算値の下位（ｍ−１）ビットに対してＯＲ演算を実行して１ビットの第２計算値を生成する丸め前処理部と、
前記第１計算値の上位（ｎ＋１）と前記第２計算値を連接した（ｎ＋２）ビットの第３計算値を記憶するレジスタと、
前記第３計算値の最上位ビットに応じて２ビットの加算値を決定し、該加算値を前記第３計算値に加算して第４計算値を生成し、該第４計算値の下位２ビットを除去する丸め後処理部と、
を具備する演算回路。
【請求項９】
加算と乗算を組み合わせた演算を実行して（ｎ＋ｍ）ビット（ｎは１以上の整数であり、ｍは２以上の整数である）の第１計算値を出力することと、
前記第１計算値の下位（ｍ−１）ビットに対してＯＲ演算を実行して１ビットの第２計算値を生成することと、
前記第１計算値の上位（ｎ＋１）と前記第２計算値を連接した（ｎ＋２）ビットの第３計算値を記憶することと、
前記第３計算値の最上位ビットに応じて２ビットの加算値を決定し、該加算値を前記第３計算値に加算して第４計算値を生成し、該第４計算値の上位２ビットを除去することと、
を具備する演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、演算回路及び方法に関する。
【背景技術】
【０００２】
乗算処理と丸め処理を実行する演算回路がある。この演算回路は、乗算結果の正負に応じて加算値を決定し、加算値を乗算結果に加算して下位ビットを切り捨てる。このような演算回路では、演算処理と丸め処理を一度で実行しているので、演算処理のみと比べて処理遅延が増加する問題がある。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平６−３４８４５５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明が解決しようとする課題は、高速な演算処理を実現する丸め付きの演算回路及び方法を提供することである。
【課題を解決するための手段】
【０００５】
一実施形態に係る演算回路は、演算部、丸め前処理部、レジスタ、及び丸め後処理部を備える。演算部は、加算と乗算を組み合わせた演算を実行して（ｎ＋ｍ）ビットの第１計算値を出力する。ここで、ｎは１以上の整数であり、ｍは２以上の整数である。丸め前処理部は、前記第１計算値の下位（ｍ−ｋ）ビットに対してＯＲ演算を実行して１ビットの第２計算値を生成する。ここで、ｋは１以上、（ｍ−１）以下の整数である。レジスタは、前記第１計算値の上位（ｎ＋ｋ）と前記第２計算値を連接した（ｎ＋ｋ＋１）ビットの第３計算値を記憶する。丸め後処理部は、前記第３計算値の最上位ビット及び前記第３計算値の下位（ｋ＋１）ビットから１ビットのキャリービット値を計算し、前記第３計算値の上位ｎビットと前記キャリービット値を加算する。
【図面の簡単な説明】
【０００６】
【図１】第１の実施形態に係る演算回路を概略的に示すブロック図。
【図２】（ａ）及び（ｂ）は四捨五入計算を説明する図である。
【図３】第２の実施形態に係る演算回路を概略的に示すブロック図。
【図４】第３の実施形態に係る演算回路を概略的に示すブロック図。
【図５】図１に示した演算部及び丸め前処理部の構成例を概略的に示すブロック図。
【図６】図５に示した部分積計算部の動作の一例を説明する図。
【図７】図５に示した部分積計算部の動作の他の例を説明する図。
【図８】図５に示した部分積加算部の動作の一例を説明する図。
【図９】全加算器及び半加算器を説明する図。
【図１０】図５に示した部分積加算部の一例を示すブロック図。
【図１１】図５に示した最終加算部の一例を示すブロック図。
【図１２】図１０に示した部分積加算部と図１１に示した最終加算部を組み合わせた演算部を示すブロック図。
【図１３】リップルキャリー加算器による最終加算部と丸め前処理部の構成例を示すブロック図。
【図１４】図５に示した最終加算部の他の例を示すブロック図。
【図１５】Kogge-Stone加算器による最終加算部と丸め前処理部の構成例を示すブロック図。
【発明を実施するための形態】
【０００７】
以下、必要に応じて図面を参照しながら、実施形態に係る演算回路及び方法を説明する。  
実施形態の説明では、Verilog HDL言語に沿ったビット記述方法を用いる。例えば、ｎビットの値ｘは、x[n-1:0]={x[n-1],x[n-2],…,x[0]}として、最上位ビット（ＭＳＢ：Most Significant Bit）がx[n-1]であり、最下位ビット（ＬＳＢ：Least Significant Bit）がx[0]であるｎビットのベクトルで定義される。値ｘの全ビットを表す場合には、[n-1:0]は省略することができる。また、値ｘの特定のビット範囲の指定は、x[a:b]のように表すことができる。例えば、x[4:2]={x[4],x[3],x[2]}である。ｎビットの値ａとｍビットの値ｂを連接した（ｎ＋ｍ）ビットの値ｃは、c={a,b}として表記することができる。複数ビットの数値は、基本的には２の補数表記で符号付きの整数を意味する。
【０００８】
図１は、第１の実施形態に係る演算回路１００を概略的に示している。この演算回路１００は、パイプライン化した丸め付き演算回路である。具体的には、演算回路１００は、図１に示すように、演算部１０１、丸め前処理部１０２、記憶部としてのレジスタ１０３、及び丸め後処理部１０４を備える。本実施形態では、演算部１０１の出力データに対する丸め処理は、２段階（即ち、丸め前処理及び丸め後処理）に分けて実行され、即ち、レジスタ１０３を挟んで配置される丸め前処理部１０２及び丸め後処理部１０４によって実行される。丸め前処理部１０２は、演算部１０１の出力データのビット数を圧縮するものであって、演算部１０１と並行して動作することができる。この丸め前処理部１０２を設けることにより、要求される動作速度を満たしながら、レジスタ１０３のビット数を削減することが可能になる。
【０００９】
演算部１０１は、加算、乗算、及び加算と乗算を組み合わせた演算を実行する。演算部１０１が実行する演算には、例えば、複素乗算のようなＡＢ＋ＣＤといった形式の演算なども含まれる。ここで、Ａ、Ｂ、Ｃ、Ｄは整数である。演算部１０１は演算結果として（ｎ＋ｍ）ビットの計算値ｘを出力するものとする。ここで、ｎは１以上の整数であり、ｍは２以上の整数である。
【００１０】
丸め前処理部１０２は、値ｘの下位（ｍ−１）ビットに対してＯＲ演算を実行して１ビットの計算値を生成し、値ｘの上位（ｎ＋１）ビットと生成した値を連接して（ｎ＋２）ビットの値ｙを出力する。例えば、丸め前処理部１０２は、下記数式（１）のように（ｎ＋２）ビットの値ｙを生成する。
【数１】
0005450781.tif 000002
【００１１】
値ｙのＬＳＢビットy[0]は、丸め前処理部１０２で生成される計算値であり、値ｘの下位（ｍ−１）ビットが全てゼロである場合にゼロになり、値ｘの下位（ｍ−１）ビットのうちの少なくとも１つのビットが１である場合に１になる。丸め前処理部１０２の出力ｙはレジスタ１０３によって記憶される。図１のレジスタ１０３は（ｎ＋２）ビットのレジスタである。レジスタ１０３に保持されている値ｙは値ｚとして丸め後処理部１０４へ与えられる。
【００１２】
丸め後処理部１０４は、レジスタ１０３に保持されている（ｎ＋２）ビットの値ｚに対して丸め後処理を行い、丸め処理されたｎビットの値ｐを出力する。例えば、丸め後処理部１０４は、下記数式（２）及び（３）のように、値ｚのＭＳＢビット（即ち、符号ビット)及び値zの下位２ビットから１ビットのキャリービット値ｃを計算し、キャリービット値ｃを値ｚの上位ｎビットに加算する。
【数２】
0005450781.tif 000003
【００１３】
ここで、ｃはキャリービット値を表し、“〜”は否定論理（即ち、ビット反転）を表し、“＆”はＡＮＤ論理を表し、“｜”はＯＲ論理を表す。
【００１４】
数式（２）において、値ｚの上位ｎビットであるz[n+1:2]が２の補数表記で正の最大値であり（即ち、z[n+1:2]={0,1,1,…,1}）、且つ、キャリービット値ｃが１である場合、桁上がりが発生し、出力ｐの正しい表記にはｎ＋１ビット必要になる。出力ｐをｎビットに収めるには、z[n+1:2]が２の補数表記で正の最大値になる可能性がある場合には、丸め後処理部１０４は、数式（３）の代わりに下記数式（４）のようにキャリービット値ｃを計算することができる。数式（４）は、数式（３）にオーバーフロー判定を追加したものであって、z[n+1:2]={0,1,1,…,1}の場合にキャリービット値ｃがゼロになるように数式（３）を修正したものである。
【数３】
0005450781.tif 000004
【００１５】
数式（２）と数式（３）（又は数式（４））の組み合わせと等価な計算としては、例えば、値ｚに丸め処理（具体的には四捨五入）のための加算値を加え、その結果得られた値ｐ´の上位ｎビットを取り出す方法もある。この方法では、キャリービット値を直接計算する必要がない。この方法では、例えば、数式（２）と数式（３）を組み合わせた計算は、下記数式（５）のように表すことができる。
【数４】
0005450781.tif 000005
【００１６】
図１に示す回路構成では、演算部１０１と丸め前処理部１０２が順番に動作するように示されているが、実際の回路構成では、後述するように、丸め前処理部１０２の処理の少なくとも一部は演算部１０１の処理の一部と並行して実行される。具体的には、丸め前処理部１０２は、演算部１０１において全てのビットが確定するより先に、演算部１０１の出力データのビット数を圧縮する処理を開始することができる。特に、演算部１０１の処理が完了する前に、丸め前処理部１０２の処理が完了することも可能である。この場合、演算部１０１の動作速度を全く低下させることなく、丸め前処理部１０２の処理を追加することが可能である。本実施形態では、丸め処理の一部（即ち、丸め前処理）が演算部１０１の処理と並列して実行されるので、丸め処理をより高速に実行することが可能になる。さらに、演算部１０１の出力データのビット数が丸め前処理部１０２によって圧縮されるので、パイプライン化した際に設けられるレジスタ１０３のビット数を削減することができる。その結果、回路規模を縮小することができる。従って、丸め前処理部１０２を設けることにより、動作速度を維持若しくは向上しつつ、回路規模を縮小することができる。演算部１０１と丸め前処理部１０２の動作については後に詳細に説明する。
【００１７】
なお、図１では演算部１０１の出力ｘが丸め処理部１０２に与えられるように示されているが、出力ｘの上位（ｎ＋１）ビットは、レジスタ１０３へ直接与えられてもよい。
【００１８】
図２（ａ）は、値（例えば、演算部１０１の出力）ｘが正の数である場合のビット構成の一例を示し、図２（ｂ）は、値ｘが負の数である場合のビット構成の一例を示す。図２（ａ）及び（ｂ）において、値ｘのＭＳＢビット（即ち、第（ｎ＋ｍ−１）ビット）が符号ビットを表し、第（ｎ＋ｍ−２）ビットから第ｍビットまでのビットが整数部分を表し、第（ｍ−１）ビットから第０ビットまでのビット（即ち、下位ｍビット）が小数部分を表す。値ｘが正の数である場合、ＭＳＢビットはゼロであり、値ｘが負の数である場合、ＭＳＢビットは１である。
【００１９】
演算部１０１の出力ｘが正の数である場合、図２（ａ）に示されるように、出力ｘの上位ｎビットを四捨五入によってインクリメントする条件は、出力ｘの下位ｍビットが｛１，０，０,…，０｝以上（即ち、２ｍ−１以上）であることである。一方、演算部１０１の出力ｘが負の数である場合、図２（ｂ）に示されるように、出力ｘの上位ｎビットを四捨五入によってインクリメントする条件は、出力ｘの下位ｍビットが｛１，０，０,…，１｝以上（即ち、２ｍ−１＋１以上）であることである。演算回路１００では、丸め前処理部１０２において出力ｘの下位（ｍ−１）ビットをＯＲ演算によって圧縮した値をレジスタ１０３に保持し、丸め後処理１０４においてレジスタ１０３に保持されている値を元に正負に基づいた四捨五入計算を実行する。
【００２０】
図３は、第２の実施形態に係る演算回路３００を概略的に示している。図３に示す演算回路３００と図１に示した演算回路１００との異なる点は、最終出力のビット数である。演算回路３００の最終出力のビット数はｊ（ここでｊは０＜ｊ＜ｎを満たす整数）である。具体的には、図３に示す演算回路３００は、図１に示した演算回路１００に、オーバーフロー処理を実行するオーバーフロー処理部３０５を追加したものである。オーバーフロー処理部３０５は、丸め後処理部１０４の後段に配置される。
【００２１】
演算回路３００において、丸め後処理部１０４までの構成及び動作は基本的に演算回路１００と同じである。ただし、数式（４）に示されるようなオーバーフロー判定は、オーバーフロー処理部３０５に吸収されるため不要であり、丸め後処理部１０４は、数式（２）及び（３）に従って丸め後処理を行い、丸め処理された値ｐを出力する。丸め後処理部１０４の出力ｐの値は、演算部１０１での演算によっては桁数がｎ＋１になる場合もある。ここでは出力ｐの桁数をｎ＋１ビットとして扱う。ただし、先に述べたように、演算部１０１の演算によっては、桁数がｎに保証される場合もあり、そのような場合にはｐをｎビットとして扱えばよい。
【００２２】
オーバーフロー処理部３０５は、ｎ＋１ビットの値ｐをｊビットに頭打ちするためのオーバーフロー計算を実行する。例えば、オーバーフロー計算は、下記数式（６）のように実行される。
【数５】
0005450781.tif 000006
【００２３】
数式（６）は、符号付きの整数として考えれば、下記数式（７）と等価である。
【数６】
0005450781.tif 000007
【００２４】
数式（６）及び（７）では、正負の範囲が対称になるよう定義したが、数式（６）の代わりに下記数式（８）を用いてもよい。この場合は、負の数が１つ多く定義される。
【数７】
0005450781.tif 000008
【００２５】
図４は、第３の実施形態に係る演算回路４００を概略的に示している。図４に示す演算回路４００と図１に示した演算回路１００の違いは、ブロック図レベルではビット幅のみである。演算回路４００では、丸め前処理部１０２のビット幅が変更され、それに伴って丸め後処理部１０４の動作が変更される。ただし、演算回路４００の最終出力は、演算回路１００で得られる値に等しい。演算回路４００では、丸め前処理部１０２がＯＲ論理を実行するビット幅は（ｍ−ｋ）ビットである。ここで、ｋは０＜ｋ＜ｍ−１を満たす整数である。ｋ＝１とすると、演算回路４００は演算回路１００と等価なものになる。従って、第３の実施形態の演算回路４００は第１の実施形態の演算回路１００の一般化と考えることができる。
【００２６】
丸め前処理部１０２のビット幅を規定するパラメータｋは回路構成に応じて決定される。回路構成によっては、丸め前処理部１０２の処理により生じる処理遅延によって、演算回路４００の動作速度が低下する場合がある。動作速度の低下を防ぐためには、パラメータｋを大きい値に設定することで丸め前処理部１０２のビット幅を小さくする必要がある。ただし、後述するように、丸め前処理部１０２の処理によって処理遅延を生じない場合が多いので、そのような場合には、パラメータｋを１にすることができ、即ち、第１の実施形態の演算回路１００を用いることができる。
【００２７】
演算回路４００では、数式（１）から（４）の代わりに下記数式（９）から（１２）をそれぞれ使用する。具体的には、丸め前処理部１０２は、数式（９）に従って、演算部１０１の出力ｘの下位（ｍ−ｋ）ビットに対してＯＲ演算を実行して１ビットの計算値を生成し、値ｘの上位（ｎ＋ｋ）ビットと生成した計算値を連接して（ｎ＋ｋ＋１）ビットの値ｙを出力する。図４の演算回路４００では、丸め前処理部１０２の出力ｙは（ｎ＋ｋ＋１）であるので、レジスタ１０３は（ｎ＋ｋ＋１）ビットのレジスタである。パラメータｋが大きくなるほど、より長いビット数のレジスタが必要になる。回路規模の小型化の観点からは、パラメータｋは小さい方が好ましい、即ち、丸め前処理部１０２がＯＲ論理を実行するビット幅は大きい方が好ましい。丸め後処理部１０４は、下記数式（１０）及び（１１）のように、レジスタ１０３に保持されている値ｚのＭＳＢビット（即ち、符号ビット)及び値zの下位（ｋ＋１）ビットからキャリービット値ｃを計算し、キャリービット値ｃを値ｚの上位ｎビットz[n+k:k+1]に加算する。z[n+k:k+1]が２の補数表記で正の最大値になる可能性がある場合には、丸め後処理部１０４は、数式（１１）の代わりに下記数式（１２）を用いてキャリービットｃを計算する。
【数８】
0005450781.tif 000009
【００２８】
上述したように丸め後処理部１０４の出力は演算回路４００と演算回路１００で同じであるので、図４の演算回路４００においても、丸め後処理部１０４の後段にオーバーフロー処理部３０５（図３）を設けることができる。演算回路４００において丸め後処理部１０４の後段にオーバーフロー処理部３０５を設けた場合の説明は、図３を参照して演算回路３００に関して説明したものと同じになるので省略する。
【００２９】
以上説明した各実施形態に係る演算回路によれば、演算部１０１と並列して動作し、演算部１０１の出力データのビット数を圧縮する丸め前処理部１０２を設けることにより、高速動作を維持しながら、レジスタ１０３のビット数を削減することができる。
【００３０】
次に、図１から図４を参照して説明した演算回路１００、３００、及び４００の各々に含まれる演算部１０１及び丸め前処理部１０２について詳細に説明する。丸め前処理部１０２の処理の少なくとも一部は演算部１０１の計算処理の一部と並列に実行される。そのため、丸め前処理部１０２の処理（具体的には数式（１）又は数式（９）に示されるy[0]の計算）を追加したことによる処理遅延の増加を最小限に抑える若しくはゼロにすることができる。
【００３１】
図５は、図１に示した演算部１０１及び丸め処理部１０２をより詳細に示している。演算部１０１は、部分積計算部５０１、部分積加算部５０２、及び最終加算部５０３を備える。前述したように丸め前処理部１０２の処理の少なくとも一部は演算部１０１の処理の一部と並行して実行されるので、以下では、これらの処理を纏めて説明する。
【００３２】
本実施形態の演算部１０１は、加算（又は減算）、乗算、及びこれらを組み合わせた演算を実行する。ここでは、一例として、下記数式（１３）のような乗算と加算を組み合わせた演算を考える。
【数９】
0005450781.tif 000010
【００３３】
ここで、Ａ、Ｂ、Ｃはそれぞれ２の補数で符号化された４ビットの符号付きの数値であり、Ｘは２の補数で符号化された８ビットの符号付きの数値であるとする。ここで、A=a[3:0]、B=b[3:0]、C=c[3:0]、X=x[7:0]と表す。
【００３４】
図６は、部分積計算部５０１によって計算される部分積の一例を示している。ここでは、図６に示すように、乗算と加算が全て加算に分解されたものを部分積と呼ぶ。この例では、５つの（５行の）部分積が部分積計算部５０１によって生成される。図６において、di[n]=a[i]&b[n]であり、ここでｉ＝０，１，２，３である。図６に示す例では、符号付きの演算のためにＭＳＢビット（即ち、符号ビット）がビット拡張されている。
【００３５】
図７は、部分積計算部５０１によって計算される部分積の他の例を示している。図７に示す例では、乗算部分においてビット拡張の代わりに一部のビットの反転やＭＳＢビットのさらに上位に１を付加するなどの方法で符号付き演算の部分積を実現している。
【００３６】
図８は、部分積加算部５０２が図６に示した部分積を加算する方法例を示す。図８において、白丸及び黒丸は対応する位置の１ビットの数値を表す。部分積加算部５０２は、全加算器（ＦＡ：Full Adder）と半加算器（ＨＡ：Half Adder）によって３行の部分積を２行の部分積に変換するステージを繰り返し、最終的に２行の部分積を得る。図８に示す例では、部分積加算部５０２は、第１ステージにおいて５行の部分積を４行の部分積に低減し、第２ステージにおいて４行の部分積を３行の部分積に低減し、第３ステージにおいて３行の部分積を２行の部分積に低減している。
【００３７】
図９は、全加算器及び半加算器の動作を概略的に示している。図９に示すように、全加算器は、３ビットの加算結果をキャリービット（carry）とサムビット（sum）の２ビットで表すことができ、半加算器は、２ビットの加算結果をキャリービット（carry）とサムビット（sum）の２ビットで表すことができる。例えば、図８において、全加算器は、第１ステージに示される実線で囲まれる同じ桁の３つのビットを、第２ステージに示される実線で囲まれる２ビットに変換する。半加算器は、第１ステージに示される点線で囲まれる同じ桁の２つのビットを、第２ステージに示される点線で囲まれる２ビットに変換する。各ステージにおいて、部分積加算部５０２は、全加算器及び半加算器を用いることで３行の部分積を２行の部分積に変換する。このような計算は、Wallace Treeで実現することができる。
【００３８】
Wallace Treeでは、第ｎステージにおける部分積数（行数）をＬ（ｎ）と表すと、第ｎ＋１ステージの部分積数Ｌ（ｎ＋１）は、下記数式（１４）のような値になる。
【数１０】
0005450781.tif 000011
【００３９】
ここで、floor(x)はｘ以下の最大の整数値を表し、ceil(x)はｘ以上の最小の整数値を表し、mod(a,b)はａをｂで割ったときの剰余を表す。即ち、Wallace Treeでは、３行の部分積が２行に変換され、２行以下の余りの部分積はそのままである。このような処理を最終的に部分積が２行になるまで繰り返す。そして、最後の２行の部分積が最終加算器５０３によって加算される。また、これと並行して、出力ｘのＬＳＢ側のビットの値が確定し次第、丸め前処理部１０２においてＯＲ演算が開始される。
【００４０】
図１０は、Wallace Treeに従う部分積加算部５０２を詳細に示している。図１０は、図８をWallace Treeに変換したものである。図１０において、ＦＡは全加算器を示し、ＨＡは半加算器を示す。なお、演算部１０１の出力ｘの下位３ビットx[2:0]は、最終加算部５０３では処理されず、部分積加算部５０２において確定する。図８及び図１０からは、最終加算部５０３の処理を待たずに、演算部１０１の出力ｘの下位３ビットx[2:0]の値が確定していることが判る。さらに細かく見ると、下位３ビットは、x[0]、x[1]、x[2]の順に値が計算されていることが判る。より具体的には、x[0]は第１ステージで確定し、x[1]は第２ステージで確定し、x[2]は第３ステージで確定している。この例のように、一般的にWallace Treeでの計算では、あるビット位置まではＬＳＢ側ほど計算に必要な処理遅延が小さいことが多い。この理由の１つは、乗算では、そもそも部分積の和を計算する行数がＬＳＢ側ほど小さい傾向にあるからである。丸め前処理部１０２の処理遅延が演算部１０１の全体の処理遅延より小さくできることの理由の１つは、ここにある。
【００４１】
図１１は、最終加算部５０３の構成例を示している。図１１に示す例では、最終加算部５０３は、リップルキャリー加算器（ＲＣＡ：Ripple Carry Adder）であり、４つの全加算器及び１つの半加算器を含む。最終加算部５０３は、２つの数値の加算器であり、部分積加算部５０２のようなステージ毎の完全な並列処理での加算処理とは異なり、実装方法に違いがあっても本質的にはキャリービットが伝搬するような加算器が必要になる。これは、ＬＳＢ側ほど小さい処理遅延で加算値が計算できることを意味する。最終加算部５０３がキャリー先読み加算器で実現される場合であっても、上位のキャリービットほど計算に必要な処理遅延は大きくなる。
【００４２】
図１２は、図１０と図１１を組み合わせた演算部１０１と丸め前処理部１０２を概略的に示している。ここでは、丸め前処理部１０２がＯＲ演算を実行するビット数は４としている。図１２に示すように、演算部１０１の出力ｘの下位４ビットは丸め前処理部１０２に与えられる。丸め前処理部１０２は、３つのＯＲ回路（又は論理和ゲート）を含み、演算部１０１の出力ｘの下位４ビットに対してＯＲ演算を実行して１ビットの計算値を生成する。演算部１０１の出力ｘの上位４ビットは、丸め前処理部１０２を経由せずに、レジスタ１０３（図１２には図示されていない。）に直接に与えられることができる。レジスタ１０３は、演算部１０１の出力ｘの上位４ビットと丸め前処理部１０２で生成された計算値を連接した中間値である５ビットの値ｙを保持する。
【００４３】
図１２の例からも明らかなように、演算部１０１がy[4:1]の全てを計算するのに必要な処理遅延よりも、丸め前処理部１０２がy[0]を計算するのに必要な処理遅延の方が小さいことが判る。つまり、丸め前処理部１０２を追加しても演算部１０１の演算処理そのものの処理遅延は増加しない。
【００４４】
例えば、最終加算部５０３にリップルキャリー加算器を適用した場合には、常にＬＳＢ側から値が決定するので、丸め前処理部１０２においてＬＳＢ側からＯＲ演算を連接して行ったとしても、全加算器のキャリー計算の処理遅延は、ＯＲ演算の処理遅延よりも大きいので、最終加算部５０３の加算処理が終了するよりも先に丸め前処理部１０２の計算を完了することできる。
【００４５】
図１３は、リップルキャリー加算器による最終加算部５０３と丸め前処理部１０２の構成例を示している。図１３において、最終加算部５０３への入力が全て同時であると仮定したとしても、丸め前処理部１０２の処理が演算部１０１の処理より先に完了することを説明する。丸め前処理部１０２のＯＲ回路に入力される２ビットをx[n]とc[n-1]とする。図１３からは、c[n-1]を計算するのに必要な処理は、x[n-1]の計算とＯＲ演算であることが判る。また、x[n]を計算するのに必要な処理は、x[n-1]の計算と全加算器の計算である。全加算器の処理遅延よりＯＲ演算の処理遅延の方が小さいので、x[n]とc[n-1]では、c[n-1]を計算する処理遅延の方が小さいことが判る。つまり、任意のビット幅に対して、y[0]とy[1]では、y[0]の方が常に小さい処理遅延で計算されることを意味している。このように、仮に部分積加算部５０２における処理遅延の差が無い場合においても、丸め前処理部１０２の処理は、演算部１０１の処理よりも先に完了することが可能である。
【００４６】
図１４は、最終加算部５０３の他の構成例を示している。図１４に示す例では、最終加算部５０３は、キャリー先読み加算器の１つであって、最も高速な加算器の１つであるKogge-Stone加算器（ＫＳＡ：Kogge-Stone Adder）である。図１４は、１０ビットの加算処理の例を示す。ＫＳＡは、ｎビット加算処理では、各ステージにおいて、キャリービットを計算するのに必要なｎビットのＧ（ｔ）とＰ（ｔ）を計算する。ａとｂを加算する場合を考えると、ＫＳＡは、初期ステージにおいて、下記数式（１５）のように値Ｇ（０）及びＰ（０）を計算する。これは、図１４の白丸の動作に対応する。
【数１１】
0005450781.tif 000012
【００４７】
第ｔステージにおけるキャリーオペレータφによって、第（ｔ−１）ステージの値から、下記（１６）及び（１７）に示す計算処理がなされる。
【数１２】
0005450781.tif 000013
【００４８】
必要な計算ステージ数Ｔは、ｇビットの加算器では、T=ceil(log2(g))である。
【００４９】
最終ステージ後のＧ（Ｔ）とＰ（Ｔ）とから、ａとｂの加算値x[n:0]は、下記数式（１８）のように計算することができる。
【数１３】
0005450781.tif 000014
【００５０】
次に、最終加算部５０３がＫＳＡである場合における、丸め前処理部１０２の動作と処理遅延について説明する。ＫＳＡは、ビット数が２倍になると、キャリービットを計算するのに必要なステージ数が１つ増加する。丸め前処理部１０２の実装もこれを踏まえた構成にすることで処理遅延を小さくすることが可能になる。
【００５１】
図１５は、Kogge-Stone加算器による最終加算部５０３と丸め前処理部１０２の構成例を示している。図１５に示す例では、丸め前処理部１０２は最終加算部５０３の出力ｘの下位４ビットに対してＯＲ演算を実行する。ＯＲ演算を２分木構造で実現する場合、丸め前処理に必要な処理遅延は、ｈビットのＯＲ演算ではceil(log2(h))個のＯＲ処理分の遅延が発生する。図１５の例では、ceil(log2(4))=2である。数式（１６）に示したように、キャリーオペレータの計算は、ＡＮＤ処理及びＯＲ処理が必要である。仮にＡＮＤ処理とＯＲ処理の遅延が同じであるとすれば、キャリーオペレータ処理は２つのＯＲ処理遅延に相当する。
【００５２】
ＫＳＡのビット幅がｇであり、丸め前処理部１０２が出力ｘの下位ｈビットに対してＯＲ演算を実行するとする。この場合、ｈビットのキャリーオペレータ処理とｈビットの丸め前処理の合計処理遅延が、ｇビットのキャリーオペレータ処理の遅延以下であれば、丸め前処理を追加したとしても加算計算そのものには余分な遅延が発生しないことになる。そのための条件は下記の不等式で表すことができる。
【数１４】
0005450781.tif 000015
【００５３】
図１５の例では、数式（２０）の左辺が４、右辺が３であるので、数式（２０）の不等式を満たす。このため、丸め前処理部１０２の追加によって演算部１０１だけの処理と比べて遅延が発生しないことになる。実際には、部分積加算部５０２のビット毎の処理遅延の違いや、ＡＮＤやＯＲの実装にも依存するので数式（２０）は絶対的な条件ではないが、高速なキャリー先読み加算器を用いる場合の設計の目安にすることができる。
【００５４】
以上のように、丸め前処理部１０２の処理の一部又は全部は演算部１０１の計算処理の一部と並列に実行されるので、丸め前処理部１０２の処理を追加したことによる処理遅延の増加を最小限に抑える若しくはゼロにすることができる。
【００５５】
以上説明した実施形態の少なくとも１つに係る演算回路によれば、演算部１０１と並列して動作し、演算部１０１の出力データのビット数を圧縮する丸め前処理部１０１を設けることにより、高速動作を維持したまま、レジスタ１０３のビット数を削減することができる。
【００５６】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００５７】
１００，３００，４００…演算回路、１０１…演算部、１０２…丸め前処理部、１０３…レジスタ、１０４…丸め後処理部、３０５…オーバーフロー処理部、５０１…部分積計算部、５０２…部分積加算部、５０３…最終加算部。
【要約】
【課題】  高速な演算処理を実現する丸め付きの演算回路及び方法を提供する。
【解決手段】  一実施形態に係る演算回路は、演算部、丸め前処理部、レジスタ、及び丸め後処理部を備える。演算部は、加算と乗算を組み合わせた演算を実行して（ｎ＋ｍ）ビットの第１計算値を出力する。ここで、ｎは１以上の整数であり、ｍは２以上の整数である。丸め前処理部は、前記第１計算値の下位（ｍ−ｋ）ビットに対してＯＲ演算を実行して１ビットの第２計算値を生成する。ここで、ｋは１以上、（ｍ−１）以下の整数である。レジスタは、前記第１計算値の上位（ｎ＋ｋ）と前記第２計算値を連接した（ｎ＋ｋ＋１）ビットの第３計算値を記憶する。丸め後処理部は、前記第３計算値の最上位ビット及び前記第３計算値の下位（ｋ＋１）ビットから１ビットのキャリービット値を計算し、前記第３計算値の上位ｎビットと前記キャリービット値を加算する。
【選択図】図１【図１】
0005450781.tif 000016
【図２】
0005450781.tif 000017
【図３】
0005450781.tif 000018
【図４】
0005450781.tif 000019
【図５】
0005450781.tif 000020
【図６】
0005450781.tif 000021
【図７】
0005450781.tif 000022
【図８】
0005450781.tif 000023
【図９】
0005450781.tif 000024
【図１０】
0005450781.tif 000025
【図１１】
0005450781.tif 000026
【図１２】
0005450781.tif 000027
【図１３】
0005450781.tif 000028
【図１４】
0005450781.tif 000029
【図１５】
0005450781.tif 000030