(57)【要約】【課題】入力データ数やビット幅が大きい場合の多入力加算、符号付のビット幅混合加算における高速な演算が可能な演算器、及び演算器の設計方法を提供することを目的とする。【解決手段】演算器１は、レジスタ１００と、入力信号１０２が入力される部分積展開部１０４と、部分積展開部１０４から信号１０６が入力されるカウンタ部１１０と、カウンタ部１１０から出力信号１１５が入力されるｓｕｍ部レジスタ１２０と、カウンタ部１１０から出力信号１１５の桁の桁上げとして出力信号１２５が入力されるｃａｒｒｙ部レジスタ１３０を備え、桁毎の遅延を予測し、予測した遅延に影響しない範囲でカウンタの適用とキャリーセーブのビット幅を最適化し、次の演算器を含めた演算器全体の遅延を最適化したことにより高速な演算器１及び演算器１の設計方法を得ることができる。【選択図】図１
2010072919.tif 000002
【特許請求の範囲】
【請求項１】
複数の多ビット入力信号を演算する演算器の設計方法において、
前記演算器は、キャリーセーブ機能を有し、加算部の一部として複数の多ビット信号を１または複数のカウンタにより演算処理するカウンタ部を備え、該多ビット信号に対して該カウンタを適用する場合、前記多ビット入力信号及びカウンタ適用後に加算される該多ビット信号と、該多ビット入力信号及び該多ビット信号が有効となる時刻とを用いて、桁毎の演算完了までの信号の遅延を予測する第１のステップと、
前記第１のステップで予測した遅延と、前記多ビット入力信号と、カウンタ適用後に加算される前記多ビット信号と、該多ビット入力信号及び該多ビット信号が有効となる時刻とに基づいて前記カウンタを適用し、該多ビット入力信号及びカウンタ適用後に加算される該多ビット信号と、該多ビット入力信号及び該多ビット信号が有効となる時刻とを更新する第２のステップと、を実行し、
前記多ビット入力信号の前記カウンタ部への入力時刻を初期の演算時刻とし初期のカウンタ適用を行った後、前記第１のステップと前記第２のステップとを繰り返す処理を行うことを特徴とする演算器設計方法。
【請求項２】
複数の多ビット入力信号を演算する演算器において、
前記演算器は、加算部の一部として複数の多ビット信号を１または複数のカウンタにより演算処理するカウンタ部と、
前記多ビット入力信号の符号ビットの桁の内、最大桁以上の桁を前記演算器の出力信号の符号ビットとするとき、該多ビット入力信号の符号ビットであって、該出力信号の符号ビットの桁より下位の桁の符号ビットのみを反転した該多ビット入力信号を前記カウンタ部に入力し、該カウンタ部の所定の桁に“１”を入力する前処理部と、を備え、
前記多ビット入力信号の符号ビットに対し符号ビットＳの変換であるＳ＝（Ｓの反転）−１で生じる“−１”を符号ビットから上位の桁に伝搬させる場合、該多ビット入力信号の符号ビットの桁の内、最小桁を始点の桁とすることから始めて、（１）該始点の桁にひとつの“−１”があるときは該始点の桁に“１”を残して該始点の桁のひとつ上の桁へ“−１”を伝搬させ、（２）該始点の桁に複数の“−１”があるときは２個の“−１”を一組として該始点の桁のひとつ上の桁へ“−１”を伝搬するとりまとめを行った後、“−１”がひとつ残されたときは該始点の桁に“１”を残して該始点の桁のひとつ上の桁へ“−１”を伝搬させ、（３）該始点の桁のひとつ上の桁を新たに該始点の桁とし、前記（１）または前記（２）の処理を実行した後に前記（３）の処理を実行する処理を前記出力信号の符号ビットの桁の一つ下位の桁まで繰り返すことにより、“１”が残った桁を前記所定の桁とすることを特徴とする演算器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乗算または線形補間並びに加算など演算を実行するための演算器と、その設計方法に関する。
【背景技術】
【０００２】
近年、大規模なシステムを搭載したＳｏＣ（Ｓｙｓｔｅｍｓ  ｏｎ  ａ  Ｃｈｉｐ）などのＬＳＩの設計においては、一般に、演算回数の多い複雑な演算を専用演算器で処理することが多く、専用演算器の性能がＳｏＣの性能に大きく影響する。特に画像処理や音声処理を行うＳｏＣを設計する場合、画像処理や音声処理におけるフィルタリングや補間演算は多項式で記述出来ることが多く、多項式表現される専用演算器をいかに設計するかが重要となる。多項式は、加算と乗算で記述されるため、一般に高性能な専用演算器を設計する場合、演算遅延の短い高速な加算器と演算遅延の短い高速な乗算器を用意する必要がある。本来加算器は、一桁ずつキャリーを上位桁へ伝搬させる必要があり、キャリー計算が遅延時間上のボトルネックとなる。また乗算は、まず部分積を計算し、最後にそれらの値を加算するため、加算器と同様にキャリーの伝搬が遅延時間上のボトルネックとなる。
【０００３】
複数の演算器を組み合わせて専用演算器を設計する場合に桁上げ処理の伝搬による遅延の問題を解消するために、演算器の桁上げ処理を完結させずに、桁上げ信号を桁上げ先見加算のような次の演算に持ち越し、キャリー伝搬の遅延を削減する、キャリーセーブ手法が提案されている。キャリーセーブを用いた専用演算器の設計では、一つの桁を、その桁の値と下の桁からのキャリーの２つの値で表現し、専用演算器の最終段階で、２値で表された各桁を加算することで、専用演算器内でのキャリーの収束を１回にしている。キャリーセーブ方式を採用することで、専用演算器は、キャリーを１回だけ収束させればよいので、遅延時間を短くすることができる。例えば、非特許文献１に、キャリーセーブ方式を使用することにより、複数の演算器を用いたときの桁上げ処理を削減し、高速化するように設計することが示されている。さらに乗算に対して、例えば、特許文献１に示されているように、キャリーセーブ方式とリップルキャリー方式を組み合わした演算器が提案されている。
【０００４】
また、従来、専用演算器の設計には、既存の加減乗除程度の演算器ライブラリを利用して設計してきた。しかし、目的の演算機能を最適に実行するような専用演算器を設計するためには、加減乗除程度の演算器ライブラリの組み合わせだけでは不十分であり、より目的の演算機能に適した演算器を用いる必要がある。多項式演算の、加減乗除程度の演算器ライブラリ以外のブロックへの分割を求めるため、多項式のオーナー法による変換を考える。多項式演算は線形補間演算の組み合わせで表現できるため、線形補間演算器は多項式演算の基本演算器とみなすことができる。例えば、特許文献２に示されているように、線形補間演算では、２の補数表現とセレクタを巧みに利用することにより、効率的な演算器を構成することができる。また、セレクタ論理を使う形にすると乗算の部分積と同様な項を桁ごとに和を取る必要がある。
【０００５】
加算器では部分積の展開は必要なく、桁ごとの和項を求めればよい。ただし、入力に符号付きのデータが含まれ、入力ごとのビット幅が異なる場合、出力の符号桁以外の桁に符号ビットが含まれる可能性がある。符号ビットが出力の符号桁以外の桁に存在する場合、そのまま足し合わせると正しい解を求めることはできない。正しい解を求めるためには、符号付きデータを符号拡張し、符号ビットの位置を出力の符号桁と一致させる必要がある。
例えば、特許文献３には、同一ビット幅の複数の入力信号の加算回路において、符号拡張をすることと入力データの符号ビットを反転して符号ビットの上位ビット側に“１１・・・１１”を足すことは同じであることに着目して、複数の入力データの上位ビット側の“１１・・・１１”の合計を求めるため先に加算しておき、入力データ（符号ビットは反転）とともに順次加算する加算器が開示されている。
【特許文献１】特開２００１−９２６５５号公報
【特許文献２】特開２００７−２１９７１４号公報
【特許文献３】特開平５−６１６４６号公報
【非特許文献１】デザインウェーブマガジン（２００６年８月号、ｐ．１２０-１２６）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１によれば、キャリーセーブ方式の乗算器及び加算器の加算部分の構成としてカウンタの組み合わせ方について述べられているが、具体的な基準や方法については明示されていないため高速な演算器を得るためには設計において試行錯誤的にならざるを得ず、入力データ数が多くかつビット幅が大きい加算器の適切な設計は困難である。また、特許文献２によれば、セレクタ論理を用いるため乗算の部分積と同様な項を桁ごとに和を取る必要があった。また、特許文献３によれば、入力ビット幅が異なる場合、入力の小数点位置が異なる場合、入力ビット幅が出力ビット幅より大きい場合、及び符号付／符号なしのデータが混在する場合に対応が困難であった。そこで、本発明では、各入出力信号にそれぞれ任意のビット幅、符号付き/符号なし、小数点位置を指定することができる、高速な多入力加算が可能な演算器と、その設計方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために請求項１の発明は、複数の多ビット入力信号を演算する演算器の設計方法において、演算器は、キャリーセーブ機能を有し、加算部の一部として複数の多ビット信号を１または複数のカウンタにより演算処理するカウンタ部を備え、多ビット信号に対してカウンタを適用する場合、多ビット入力信号及びカウンタ適用後に加算される多ビット信号と、多ビット入力信号及び多ビット信号が有効となる時刻とを用いて、桁毎の演算完了までの信号の遅延を予測する第１のステップと、第１のステップで予測した遅延と、多ビット入力信号と、カウンタ適用後に加算される多ビット信号と、多ビット入力信号及び多ビット信号が有効となる時刻とに基づいてカウンタを適用し、多ビット入力信号及びカウンタ適用後に加算される多ビット信号と、多ビット入力信号及び多ビット信号が有効となる時刻とを更新する第２のステップと、を実行し、多ビット入力信号のカウンタ部への入力時刻を初期の演算時刻とし初期のカウンタ適用を行った後、第１のステップと第２のステップとを繰り返す処理を行うようにしたものである。
【０００８】
また、請求項２の発明は、複数の多ビット入力信号を演算する演算器において、演算器は、加算部の一部として複数の多ビット信号を１または複数のカウンタにより演算処理するカウンタ部と、多ビット入力信号の符号ビットの桁の内、最大桁以上の桁を演算器の出力信号の符号ビットとするとき、多ビット入力信号の符号ビットであって、出力信号の符号ビットの桁より下位の桁の符号ビットのみを反転した多ビット入力信号をカウンタ部に入力し、カウンタ部の所定の桁に“１”を入力する前処理部と、を備え、多ビット入力信号の符号ビットに対し符号ビットＳの変換であるＳ＝（Ｓの反転）−１で生じる“−１”を符号ビットから上位の桁に伝搬させる場合、多ビット入力信号の符号ビットの桁の内、最小桁を始点の桁とすることから始めて、（１）始点の桁にひとつの“−１”があるときは始点の桁に“１”を残して始点の桁のひとつ上の桁へ“−１”を伝搬させ、（２）始点の桁に複数の“−１”があるときは２個の“−１”を一組として始点の桁のひとつ上の桁へ“−１”を伝搬するとりまとめを行った後、“−１”がひとつ残されたときは始点の桁に“１”を残して始点の桁のひとつ上の桁へ“−１”を伝搬させ、（３）始点の桁のひとつ上の桁を新たに始点の桁とし、（１）または（２）の処理を実行した後に（３）の処理を実行する処理を出力信号の符号ビットの桁の一つ下位の桁まで繰り返すことにより、“１”が残った桁を所定の桁とするようにしたものである。
【発明の効果】
【０００９】
請求項１の発明によれば、演算器は、桁毎の遅延を予測し、予測した遅延に影響しない範囲でカウンタの適用を最適化する。キャリーセーブのビット幅を最適化できるので演算器の遅延時間の増加を抑えかつ次の演算器による遅延の増加を抑えることが出来るので、次の演算器も合わした全体的な遅延を最適化でき、従来よりも高速な専用演算器を得ることができる。
【００１０】
さらに、請求項２の発明によれば、演算器は、ビット幅が異なりかつ符号付きの複数の多ビット信号が入力され、所定の符号ビットの桁を持つ出力信号を出力する。この場合、符号ビットの−Ｓ＝（Ｓの反転）−１の変換で生じた“−１”を、“１”が特定の桁に１つ残るような状態を作り出すように上位の桁に伝搬させて、“１”を付加する桁を決定する。これにより、ビット拡張を行うことなくまた所定の桁のひとつの“１”の付加項のみで高速に演算を行うことができる。
【発明を実施するための最良の形態】
【００１１】
以下、図面に従って本発明の第１及び第２の実施形態について説明する。但し、本発明の技術的範囲はこれらの実施形態に限定されず、特許請求の範囲に記載された事項とその均等物まで及ぶものである。図１は、本発明の第１の実施形態に係る乗算または線形補間演算における演算器の構成を示すブロック図である。演算器１は、乗算または線形補間演算をそれぞれ部分積またはセレクタ論理形の項の部分積を用いた積和型の表現を基に、全ての積項を演算し桁ごとに整列し和項に展開した後、加算演算を行う構成をとる。レジスタ１００に格納された複数の多ビット信号は、入力信号１０２で示されるように部分積展開部１０４に入力される。部分積展開部１０４は、部分積の桁ごとに和項をまとめた信号１０６を、カウンタ部１１０に出力する。
【００１２】
カウンタ部１１０は、１または複数のカウンタで構成され、さらに複数の段数をなし、各段のカウンタにその段以前のカウンタの出力が入力される形態を含んでいる。なお、各段のカウンタに入力される信号はその桁のカウンタに限るものではなくその桁より下位の他の桁のカウンタから出力された信号も含む。カウンタ部１１０は、キャリーセーブ機能がついた桁の演算部分とキャリーセーブ機能がつかない桁の演算部分とに分かれている。すなわち、カウンタ部１１０は、下位桁から所定の桁まではその桁の和（サム）として出力信号１１５をｓｕｍ部レジスタ１２０に出力する。カウンタ部１１０は、所定の桁を超える上位の桁においては、キャリーセーブ機能を使いその桁の和（サム）として出力信号１１５をｓｕｍ部レジスタ１２０に出力し、その桁の桁上げ（キャリー）として出力信号１２５をｃａｒｒｙ部レジスタ１３０に出力する。なお、ｓｕｍ部レジスタ１２０とｃａｒｒｙ部レジスタ１３０は同じビット幅でもよい。
【００１３】
なお、キャリーセーブ機能を実現するためには、キャリーセーブを使用する各桁の和項が残り２個になるまでカウンタの適用を繰り返す。２個残った和項の内、一方がサム出力、もう一方がキャリーセーブ出力となる。キャリーセーブを出力しない桁は、和項が１個になるまでカウンタを割り当てる必要があるため、下位桁のキャリー伝搬を待つ必要があり、桁上げ伝搬により演算器の遅延が増加する。一方、キャリーセーブを出力する桁は、和項を２個残すことができるので、下位桁のキャリー伝搬を待つことなく次の演算を完了させることができるが、キャリーセーブ出力のビット幅が増加すると、桁上げ先見加算器のような次の演算器で演算すべき項が増加し、次の演算器の遅延が増加する。従って、キャリーセーブ機能で次の演算に繰り越すキャリーの数すなわち所定の桁の位置を最適化する必要がある。後述する本願発明の演算器の設計方法では、桁毎の遅延を予測し、予測した遅延に影響しない範囲でカウンタの適用とキャリーセーブのビット幅を最適化したため、次の演算器を含めた演算器全体の遅延を最適化することにより高速な演算器を得ることができる。なお、図１に示してはいないが次の演算器を含めた演算器全体を演算器１としてもよい。
【００１４】
ここで、演算器１の構造を表す接続情報及び時刻情報のデータを時刻情報付きネットリストとする。時刻情報付きネットリストでは、演算器１をドット及びカウンタの２種類のデータで表現する。ドットは演算対象の和項を表し、ネットリスト上ではカウンタ間の配線を表現し、識別符号を示す「ＩＤ」と、配線先のカウンタが属する桁の位置を示す「桁の位置」と、前のカウンタから出力された信号を介した配線によって接続先のカウンタで演算可能となる時刻を示す「演算可能時刻」の情報を保持する。また、演算可能時刻は信号が有効となる時刻でもある。カウンタは、カウンタの名を例えば２−２カウンタなどで示す「カウンタ名」と、ポート名、入力時刻、及びポートに接続されるドットのＩＤを示す「入力ポート情報」と、ポート名、出力桁、出力時刻、及びポートに接続されるドットのＩＤを示す「出力ポート情報」の情報を保持する。
【００１５】
図２（Ａ）乃至（Ｃ）は３−２カウンタの構造を示す。図２（Ａ）は、３−２カウンタの論理回路を示し、図２（Ｂ）は、３−２カウンタの模式図を示し、図２（Ｃ）は、３−２カウンタの有向グラフを示す。図２（Ａ）において、３−２カウンタは、３つの入力ポートｉ１乃至ｉ３と、２つの排他論理和（ＸＯＲ）である排他的論理和２及び排他論理和３と、１つのセレクタ４とを備える。図２（Ｂ）において、３−２カウンタは模式的に示されている。図２（Ｃ）において、丸で示されたノードは、ドットを表し、各々３つの入力ポートｉ１乃至ｉ３と、２つの出力ポートｓ０及びｓ１に接続されるカウンタ間の配線を示す。２重線を始点とする矢印のついた２つの辺は３−２カウンタの適用を表し、３つの入力ポートｉ１乃至ｉ３からの入力により、それぞれｓ０またはｓ１に接続されるドットへの出力となっていることを示している。２重線で結ばれたドットがひとつのカウンタへの入力となっていることを表す。
【００１６】
カウンタの入力信号は、すべて同じタイミングで処理が開始されるのではなく、他の信号の演算結果を待って処理が開始される信号もある。同様に、出力信号も、信号ごとに演算結果が出力されるタイミングが異なる。入力待ち時刻を削減するため、および早いタイミングの出力信号を次の演算に早い段階で使用するため、ポートごとに入力時刻あるいは出力時刻を設定する。カウンタをセレクタ論理で表現したとき、最も早いタイミング要求される信号を基準とし、ある入力信号を待つべき信号処理のセレクタの段数を、その入力ポートの入力時刻とする。
【００１７】
図２（Ａ）に示される３−２カウンタの論理回路からわかるように、入力ポートｉ１、ｉ２、ｉ３の入力時刻はそれぞれ０、０、１となる。また、入力時刻０の信号を基準に、ある出力信号が得られるまでに必要とするセレクタの段数をその出力ポートの時刻とする。出力ポートｓ０、ｓ１の出力時刻はそれぞれ２、２となる。出力ポートは、上位のビットへの出力であることがある。他の桁への出力を表現するために、出力ポート情報として、出力桁をパラメータとして与える。入力ポートの桁の位置から繰り上がる桁数を出力桁とする。出力ポートｓ０、ｓ１の出力桁はそれぞれ０、１となる。すなわち、入力ポート情報は、[ポート名（入力時刻）]という形式で表現する。また、出力ポート情報は、[ポート名（出力桁、出力時刻）]という形式で表現する。入力ポート情報はｉ１（０）、ｉ２（０）、ｉ３（１）となり、出力ポート情報はｓ０（０、２）、ｓ１（１、２）となる。図３は、他のカウンタに対する入力ポートと出力ポートのポート情報を示す。
【００１８】
次に、演算器１の設計方法について説明する。図４は、演算器１の設計方法を示すフローである。まず、時刻ｔ＝０の初期入力では各桁に入力される入力すなわち和項に応じたカウンタを適用する（Ｓ１１）。１つの和項は１つのドットに対応付けられる。その結果の初期データは時刻情報付きネットリストとして格納部５に格納される。ここで、時刻ｔ＝０でのカウンタの適用方法について説明する。時刻ｔ＝０のドットは、すべて同じタイミングで演算が可能になるとみなすことができるので、できるだけ大きいカウンタを適用し、上位の桁へ伝搬するキャリーの数を削減する。時刻ｔ＝０のドットに対しては、下位の桁から順にドットの個数に応じた操作を行う。ドットが２個のとき２−２カウンタを使用し、ドットが３個のとき３−２カウンタを使用し、ドットが４または５個のとき４−２コンプレッサを使用し、ドットが６、７、または８個のとき７−３カウンタを使用する。また、ドットが９個以上の場合、ｎをドット数、ｍを自然数とすると、ｎ−７×ｍ=２のときｍ個の７−３カウンタと１個の２−２カウンタを使用し、ｎ−７×ｍ=３のときｍ個の７−３カウンタと１個の３−２カウンタを使用し、ｎ−７×ｍ=４または５のときｍ個の７−３カウンタと１個の４−２コンプレッサを使用し、ｎ−７×ｍ=０、１、または６のときｍ個の７−３カウンタを使用する。
【００１９】
次に、時刻ｔを１だけ進める（Ｓ１２）。ここで時刻ｔの単位は基本動作時間であるが、クロック周波数等で異なるため基本動作時間で規格化したものとする。時刻ｔにおいて桁ごとの処理をする桁の設定をする（Ｓ１３）。すなわち、最下位の桁ｉ＝１を処理する桁とすることから始め、現在の処理をする桁ｉがｉ＞１のときは、次の桁を処理する桁とする。次に、格納部５から読み出した時刻情報付きネットリストを用い現在の桁の演算完了までの信号処理にかかる時間をその桁の遅延として予測する（Ｓ１４）。格納部５から読み出した時刻情報付きネットリストとステップＳ１４で予測した遅延を用いカウンタを適用し、時刻情報付きネットリストを更新し格納部５に格納する（Ｓ１５）。
【００２０】
その後、現在の処理をする桁ｉが最上位桁でない場合（Ｓ１６でＮｏ）、ステップＳ１３に戻る。一方、現在の処理をする桁ｉが最上位桁の場合（Ｓ１６でＹｅｓ）、ステップＳ１７に進む。ステップＳ１７において、すべての桁のドットが２個以下かどうかつまりキャリーセーブを出力する桁（ドット２個）か和のみの桁（ドット１個）になったか否かを判断し（Ｓ１７）、２個を超える場合（Ｓ１７でＮｏ）、ステップＳ１２戻り、２個以下になった場合（Ｓ１７でＹｅｓ）、カウンタ部１１０の設計を終了する。
【００２１】
ここで、ステップＳ１４における遅延の予測について説明する。最初に、各ドットの遅延への影響度を考える。演算可能時刻がｔのドット２個と演算可能時刻がｔ＋１のドット１個は、遅延への影響が同等であり、また、演算可能時刻がｔのドット４個は、演算可能時刻がｔ＋２のドット１個と同等であると考えられるため、演算可能時刻が１大きくなるごとに遅延への影響度は２倍になると考え、演算可能時刻がｔのドットの重みを２tとする。桁ｊのドットの重みの総和は、桁ｊのドットにカウンタを適用し、ドットを１個まで減らしたときの残ったドットの重みと同等であるとみることができる。桁ｊのドットのｉ番目のドットをｄｊｉとし、ｄｊｉの演算可能時刻をｔｄｊｉとすると、桁ｊの重みｗｊは「数１」式で表される。
【数１】
2010072919.tif 000003
ここで、ｎｊを桁ｊのドットの総数とするとΣはｉ＝１〜ｎｊで和を取る。
【００２２】
遅延を予測するためには、下位桁からのキャリーを考慮する必要がある。下位桁からのキャリーを求めるためには、該当桁より下位の全ての桁のドットの分布を求める必要があり、キャリーの正確な予測は困難である。実際より多数、または遅延の遅いキャリーを予測した場合、遅延を大きく予測し、予測最大遅延が実際の最小の遅延より大きくなる可能性がある。したがって、予測する遅延の値の下界を求めるために、下位桁からのキャリーの重みの総和の下界を求める。演算可能時刻tのドットの重みが２tであるため、ドットが２個にまとめられる時刻は、重みの総和の半分の対数をとった値である。本実施形態で使用するカウンタは、サムと同じ時刻へのキャリーを出力するため、キャリーが最も少ない場合でも、該当桁の重みの総和と等しい重みのドットを上位桁へキャリーとして伝搬する。
従って、桁jへのキャリーの重みの総和ｗｃjは「数２」式で予測される。
【数２】
2010072919.tif 000004
桁ｊの遅延Ｄｊは「数３」式で予測される。
【数３】
2010072919.tif 000005
ここで、ｃｅｉｌ（ｘ）は天井関数をあらわし、実数ｘに対しｘ以上の最小の整数をとることを意味する。また、演算器全体の遅延の予測のため、「数４」式で求められるＤｍａｘを予測最大遅延とする。
【数４】
2010072919.tif 000006
【００２３】
図５は、遅延予測の一例を示す。図５における丸はドット1個を表し、点線で示された丸は予測により生じたドットを表す。丸内の数字はドットの重みを表す。縦軸は演算可能時刻を表し、横軸は桁を表す。ただし、最下段の行は予測により発生したキャリーを表現する。図５(Ａ)は遅延を予測する前のカウンタ適用状態である。この状態の桁ｊの遅延および桁ｊ＋１へのキャリーの重みを予測する。桁ｊ−１では、１つの２−２カウンタが適用済みであり、演算可能時刻２のキャリーが桁ｊ−２から繰り上がっている。また、簡単化のため、桁ｊ−２では、カウンタの適用が完了しており、これ以上のキャリーは発生しないものとする。本実施形態により遅延及びキャリーの重みを予測した結果を図５(Ｂ)に示す。桁ｊ−２からのキャリーはこれ以上発生しないため、ｗｃｊ−１＝０である。また、「数１」式より、ｗｊ−１＝８である。これらの値と「数２」式より、ｗｃｊ＝４を得る。「数１」式より、ｗｊ＝６であるから、「数３」式よりＤｊ＝３を得て、漸化式である「数２」式より、ｗｃｊ＋１＝５が得られる。図５(Ｂ)においては、桁ｊでの予測の結果生じたドットは一旦演算可能時刻３に２つの点線の丸で表示されており、計算の結果、一方の点線の丸が点線の矢印の先の点線の丸として予測により発生したキャリーとして重み５が桁ｊ+１の最下段に表示されている。なお、桁ｊ−１の予測の結果生じたドットは省略されており、予測により発生したキャリーのみを最下段に重み４を表示して点線の丸として桁ｊに示めされている。図５(Ｃ)は、図５(Ａ)の桁jに、桁ｊ＋１への重みの総和が最小となるように、設計者が本願発明に依拠することなく手設計で試行錯誤的にカウンタを適用した例である。桁jの遅延に関して、(Ｃ)と同等の値が(Ｂ)で予測されている。また、キャリーの重みの総和は、最小値として(Ｃ)の適用方法による１２をとるが、より小さい値５が(Ｂ)で予測されていることが確認できる。どのようなカウンタの組み合わせでもキャリーの重みの総和が（Ｂ）で予測される値５を下回ることはなく下界となっている。
【００２４】
次に、ステップＳ１５におけるカウンタ適用の一例について説明する。本例においては入力待ち時間を削減するために、入力数が少なく、大きな入力待ちが発生しにくい３−２カウンタを主に使用する。まず、演算可能時刻の小さいドットから順に３−２カウンタおよび２−２カウンタを適用する。カウンタのみによる演算では、キャリー伝播により遅延が大きくなる。キャリー伝播のための遅延を削減するため、上位の桁でドットを２個残し、一方を出力、もう一方をキャリーセーブ出力とする。このとき、キャリーセーブのビット幅を、遅延に影響しない範囲で最小化する必要がある。キャリーセーブを出力する最小の桁をｒｃｓとする。桁ｒｃｓ未満の桁において、各桁のカウンタ未適用のドットが１個になるようにカウンタを適用し、桁ｒｃｓ以上の桁において、各桁のカウンタ未適用のドットが２個以下になるようにカウンタを適用する。ステップＳ１２において時刻ｔを１増加させた時に、以下の操作を行う。まず、各桁のドットの数を調べ、ドットが３個以上である桁のうち、最小の桁から最上位の桁の集合をＲ３とする。また、ドットが２個である桁のうち、最小の桁から、ドットが３個以上である桁のうち、最小の桁より１つ下位までの桁の集合をＲ２とする。Ｒ３およびＲ２に含まれない桁の集合をＲ１とする。
【００２５】
図６（Ａ）（Ｂ）（Ｃ）は、カウンタの適用を示す。図６（Ａ）において、各集合の領域の一例として、８桁の場合を示している。丸で表した図形がドットである。各桁の境界を点線で示している。桁は右方向から左方向に向かって上位の桁となる。次に、時刻ｔのドットが存在する桁に対して、以下の操作を行う。このとき、桁ｊの演算可能時刻最大のドットの演算可能時刻をＤｍａｘｊとする。
（１）ｊ∈Ｒ３かつｊ−１∈Ｒ３である場合
下位桁からのより時刻が遅いキャリーが必ず発生する。３−２カウンタを適用する。
（２）ｊ∈Ｒ３かつｊ−１∈Ｒ２である場合
桁ｊ−１より下位の桁ですべてドットが２個以下になっているため、桁ｊはキャリーセーブを出力する可能性のある桁である。下位桁からのキャリーが発生する可能性があるため、下位桁からのキャリー伝搬の可能性により、適用するカウンタを決定する。Ｄｍａｘｊ＋２≦Ｄｍａｘのとき、下位桁からのキャリーが伝搬されるため、演算可能時刻が早い順にドットを３個選択し、３−２カウンタを適用する。Ｄｍａｘｊ＋２＞Ｄｍａｘのとき、下位桁からのキャリーが伝搬される可能性が小さいため、ドットを２個残し、桁ｊにおいてキャリーセーブも出力する。演算可能時刻が早い順にドットを２個選択し、２−２カウンタを適用する。ここで、ドットが３個残っている桁ｊが、キャリーセーブを出力しない桁にするためには、３個のドットに３−２カウンタを適用し、ｊ桁のドットを１個にまとめる必要がある。このとき、３−２カウンタの適用結果として発生するドットは、３−２カウンタの適用前のドットのうち、演算可能時刻が最も遅いものより演算可能時刻が２大きい。したがって、キャリーセーブのビット幅を、遅延に影響しない範囲で最小化するため、３−２カウンタの適用結果として発生するドットの遅延をＤｍａｘｊ＋２とし、Ｄｍａｘと比較している。
【００２６】
（３）ｊ∈Ｒ３かつｊ−１∈Ｒ１である場合
桁ｊ−１より下位の桁ですべてドットが１個以下になっているため、桁ｊはキャリーセーブを適用する可能性のある桁である。下位桁からのキャリーは発生しないため、桁ｊのドットの演算可能時刻が演算器全体の遅延より早い場合、桁ｊがキャリーセーブを出力しないことにより、キャリーセーブのビット幅を削減する。Ｄｍａｘｊ＋２≦Ｄｍａｘのとき、キャリーを上位桁に伝搬しても遅延には影響しないため、残り３個のドットに３−２カウンタを適用する。Ｄｍａｘｊ＋２＞Ｄｍａｘのとき、キャリーを上位桁に伝搬すると遅延に影響するため、演算可能時刻が早い順にドットを２個選択し、２−２カウンタを適用する。
（４）ｊ∈Ｒ２かつｊ−１∈Ｒ２である場合
桁ｊより下位の桁ですべてドットが２個以下になっているため、桁ｊはキャリーセーブを出力する可能性のある桁である。下位桁にカウンタが適用されて桁ｊにキャリーが伝搬される可能性があるため、キャリーが伝搬されるのを待つ。
（５）ｊ∈Ｒ２かつｊ−１∈Ｒ１である場合
桁ｊより下位の桁ですべてドットが２個以下になっているため、桁ｊはキャリーセーブを出力する可能性のある桁である。下位桁からのキャリーは発生しないため、ｊのドットの演算可能時刻が演算器全体の遅延より早い場合、桁ｊがキャリーセーブを出力しないことにより、キャリーセーブのビット幅を削減する。Ｄｍａｘｊ＋１≦Ｄｍａｘのとき、キャリーを上位桁に伝搬しても全体の遅延には影響しないため、残り２個のドットに２−２カウンタを適用する。Ｄｍａｘｊ＋１＞Ｄｍａｘのとき、キャリーを上位桁に伝搬すると全体の遅延には影響するため、カウンタを適用せずに桁ｊがキャリーセーブを出力する桁とする。図６（Ｂ）（Ｃ）は、Ｒ２に含まれ、かつ１つ下位の桁がＲ１に含まれる桁の例を示している。各桁の境界の点線に加えて、水平方向に演算可能時間の境界を点線で示している。また、Ｄｍａｘに対応する演算可能時刻を矢印で示している。
【００２７】
図６（Ｂ）では、２個のドットの演算可能時刻はそれぞれＤｍａｘより１小さいため、２−２カウンタを適用することによって演算可能時刻が１大きいドットが発生しても全体の遅延への影響はない。したがって、（Ｂ）の場合では、２個のドットに２−２カウンタを適用し、キャリーセーブビット幅を小さくすることが示されている。一方、図６（Ｃ）では、２個のドットの演算可能時刻はそれぞれＤｍａｘと等しいため、２−２カウンタを適用することによって演算可能時刻が１大きいドット（点線で示されたドット）が発生すると全体の遅延も１大きくなる可能性がある。したがって、（Ｃ）の場合では、カウンタを適用せず、２個のドットのうち片方をサム（ｓで示されたドット）、もう一方をキャリーセーブ（ｃで示されたドット）として出力する。各桁について該当桁にカウンタが適用されなくなるまで繰り返し、満たさなくなれば操作を１つ上位の桁に移す。繰り返し終了時点でＲ２に属する桁がキャリーセーブを出力する桁となり、キャリーセーブを出力する最小の桁である桁ｒｃｓが決まる。なお、ここで桁毎にカウンタを適用する例をあげたが、桁をまたがって適用できるカウンタを用いて、予測した遅延に影響しない範囲でカウンタの適用とキャリーセーブのビット幅を最適化することも可能である。
【００２８】
このように、桁毎の遅延を予測し、予測した遅延に影響しない範囲でカウンタの適用とキャリーセーブのビット幅を最適化する。すなわち、桁毎の遅延を予測し、予測した遅延に影響しない範囲でカウンタの適用とキャリーセーブのビット幅を最適化したため、次の演算器を含めた演算器全体の遅延を最適化したことにより高速な演算器を得ることができる。なお、本実施形態では、演算器として乗算または線形補間演算の部分積を用いた積和型の表現を基に、全ての積項を演算し、桁ごとに整列し和項に展開した後、加算演算を行う構成をとるものとしたが、図７に示すような複数の多ビット入力信号の和をとる加算器でもカウンタ部１１０を同様に構成することができる。この場合、多ビット入力信号のビット幅が異なっていてもよい。また、本願発明の設計方法で生成される時刻情報付きネットリストを用いれば、カウンタ設計後の回路調整やパイプライン化が容易にできる。さらに、入力信号の数が大量になる場合はこの設計方法をプログラムとして実現してもよい。
【００２９】
次に、本発明の第２の実施形態について説明する。ビット幅が異なりかつ符号付きの複数の多ビット信号が入力され、所定の符号ビットの桁を持つ出力信号を出力する場合に、一律に符号拡張を行うことなくまた少ない付加項で高速な加算が可能な演算器の構成例を示す。ここで、所定の符号ビットの桁とは、複数の多ビット信号の符号ビットの桁のうち最大の桁以上の指定された桁である。図８は、第２の実施形態の演算器の構成のブロック図である。すなわち、図８において、レジスタ８００に格納された複数のビット幅が異なる符号付の多ビット信号は、入力信号８０２で示されるように前処理部８０４に入力される。前処理部８０４では、入力信号８０２の異なる符号ビットの桁の位置を基に入力信号の桁ごとに付加項として“１”を加える所定の桁の位置が一括して決められ、入力信号８０２の符号ビットのみを反転させた信号の桁ごとの和項にまとめられた信号が所定の桁に“１”が付加されて信号８０６として出力されカウンタ部８１０に入力される。なお、所定の符号ビットの桁が複数の多ビット入力信号の符号ビットの桁の内の最大桁に一致する場合は、その最大桁の符号ビットは反転しなくともよい。
【００３０】
カウンタ部８１０は桁ごとに１つもしくは複数のカウンタで構成され、さらに複数の段数をなし各段のカウンタにその段以前のカウンタの出力が入力される形態を含んでいる。なお、各段のカウンタに入力される信号はその桁のカウンタに限るものではなくその桁より下位の他の桁のカウンタから出力された信号も含む。カウンタ部８１０はキャリーセーブ機能がついた桁の演算部分とキャリーセーブ機能がつかない桁の演算部分とに分かれている。すなわちカウンタ部８１０は下位桁から所定の桁まではその桁の和（サム）として出力信号８１５をｓｕｍ部レジスタ８２０に出力する。カウンタ部８１０は、所定の桁を超える上位の桁ではキャリーセーブ機能を使いその桁の和（サム）として出力信号８１５をｓｕｍ部レジスタ８２０に出力し、その桁の桁上げ（キャリー）として出力信号８２５をｃａｒｒｙ部レジスタ８３０に出力する。なお、複数の多ビット信号の符号ビットの桁が常に決まっている場合は、あらかじめ入力信号８０２の異なる符号ビットの桁の位置を基に入力信号の桁ごとに付加項として“１”を加える所定の桁の位置を一括して決めておき前処理部８０４をなくすか、前処理部８０４を１回だけ通し所定の桁の位置を記憶しておき以降は前処理部８０４を通さないようにしてもよい。また、ｓｕｍ部レジスタ８２０とｃａｒｒｙ部レジスタ８３０は同じビット幅でもよい。なお、図８には示していないが、第１の実施形態と同じく桁上げ先見加算器のような次の演算器を含めた全体の演算器より最終の出力信号が得られる。
【００３１】
次に、前処理部８０４の処理について説明する。図９は、前処理部８０４の処理フローを示す。図９において、入力信号８０２の異なる符号ビットの桁の位置を基に入力信号の桁ごとに付加項として“１”を加える所定の桁の位置が決められる（Ｓ２１）。入力信号８０２の符号ビットのみを反転させ、桁ごとの和項にまとめる（Ｓ２２）。ステップＳ２１で決められた所定の桁への“１”の付加とステップＳ２２でまとめられた桁ごとの和項を合わせてカウンタ部８１０に出力する（Ｓ２３）。なお、ステップＳ２２で所定の符号ビットの桁が複数の多ビット入力信号の符号ビットの桁の内の最大桁に一致する場合は、その最大桁の符号ビットは反転しなくともよい。
【００３２】
図１０は、図９におけるステップＳ２１の処理の詳細なフローである。図１０において、入力信号８０２の符号ビットを反転させかつ符号ビットの桁に−１を発生させる（Ｓ２１１）。これは符号ビットをＳとした時、−Ｓ＝（Ｓの反転）−１の変換を行ったことになる。以降のステップにおいて、この符号ビットの桁に発生させた“−１”を上位の桁に伝搬させていく。すなわち、桁ｊに発生した“−１”は−２ｊであるので−２ｊ＝−２ｊ＋１＋２ｊの等式により、桁ｊに“１”を残し桁ｊ＋１に“−１”を発生させればよい。また、桁ｊに“−１”が２個発生した場合は、−２ｊ−２ｊ＝−２ｊ＋１の等式により、桁ｊ＋１に“−１”を発生させるだけでよい。これらの等式を用いて上位桁に“−１”を発生させていくことを伝搬という。この伝搬は多入力信号８０２の桁ごとに一括して行っていく。
【００３３】
次に、伝搬の処理を行う処理桁すなわち“−１”が発生した桁を決定する（Ｓ２１２）。最初は多入力信号８０２の符号ビットの桁のうち最小の桁とする。処理桁に“−１”が複数あるかどうかを判断する（Ｓ２１３）。“−１”が１個の場合（Ｓ２１３でＮｏ）、“−１”を処理桁の１つ上の桁に伝搬し“１”を処理桁に残す（Ｓ２１４）。一方、ステップＳ２１３において、“−１”が複数ある場合（Ｓ２１３でＮｏ）、２個の“−１”を一組として処理桁の１つ上の桁に各々“−１”を伝搬する（Ｓ２１５）。すなわち、組の数に応じた“−１”を上位の桁に発生させる。ステップＳ２１５の伝搬後、処理桁に“−１”が残るかどうかを判断する（Ｓ２１６）。これは伝搬前の“−１”の個数が奇数であったかどうかと等価である。処理桁に“−１”が残る場合（Ｓ２１６でＹｅｓ）、ステップＳ２１４で残った“−１”を処理桁の１つ上の桁に伝搬し“１”を処理桁に残す。一方、ステップＳ２１６において、処理桁に“−１”が残らない場合（Ｓ２１６でＮｏ）、処理桁の１つ上の桁を新たな処理桁とする（Ｓ２１７）。ステップＳ２１４の処理の後も同様に処理桁の１つ上の桁を新たな処理桁とする（Ｓ２１７）。
【００３４】
次に、新たな処理桁が出力信号の符号ビットの桁かどうかを判断する（Ｓ２１８）。新たな処理桁が出力信号の符号ビットの桁でない場合（Ｓ２１８でＮｏ）、出力信号の符号ビットの桁より下位の桁であるので、ステップＳ２１２に戻る。一方、ステップＳ２１８において、新たな処理桁が出力信号の符号ビットの桁である場合（Ｓ２１８でＹｅｓ）、この伝搬処理を終了する。すなわち、伝搬の処理を行う桁は出力信号の符号ビットの桁のひとつ下の桁までとする。これら一連の処理により“１”が残った桁が“１”を付加する所定の桁となる。なお、ステップＳ２１５で組とする個数を２の階乗個でまとめてより上位の桁に伝搬させるものがあってもよい。この場合、処理を進めてステップＳ２１７で新たな処理桁を発生させたとき“−１”が発生している桁が新たな処理桁でない場合があるので、ステップＳ２１２に戻った時により上位の桁で“−１”が発生している桁で最小の桁を処理桁として決定する必要がある。また、ステップＳ２１２で“−１”が発生している桁が新たな処理桁から出力信号の符号ビットの桁のひとつ下の桁まで桁に見つからない場合は伝搬処理を終了することになる。
【００３５】
次に、図９のステップＳ２１における入力信号８０２について説明する。図１１（Ａ）（Ｂ）は、ステップＳ２１における入力信号８０２の初期状態と終了状態を示す。図１１（Ａ）は、入力信号８０２の初期状態を示し、図１１（Ｂ）は、入力信号８０２の終了状態を示す。この例では、ビット幅及び符号ビットの桁の位置が異なる５個の入力信号８０２を示しており、所定の符号ビットの桁はその内の最大の符号ビットの桁と一致している。図１１（Ａ）において、四角形は、ビットの位置を表し、−Ｓは符号ビットの値を示し、空白の部分はビットの値を明示していない。すなわち、行方向に並んだ四角形の連なりがひとつの入力信号８０２を示し、同じ列方向の四角形の連なりは同一の桁にある各信号のビットを表す。図１１（Ｂ）においては、伝搬処理が終わり“１”が残った桁は、入力信号８０２に対して前処理部８０４で“１”を加える桁を示している。ここで、バーの付いたＳはＳの反転を示し、付加された四角形の中に発生した“−１”と残された“１”を示している。
【００３６】
図１２（Ａ）乃至（Ｆ）は、図１１（Ａ）の状態から図１１（Ｂ）の状態へ至るまでの入力信号８０２の状態を示す。図１２（Ａ）は所定の符号ビットの桁より下位の符号ビットの桁に“−１”を発生させた状態を示す。図１２（Ｂ）は最小の符号ビットの桁から始めて“−１”を上位に２桁伝搬させた状態を示す。図１２（Ｃ）は、図１２（Ｂ）で最上位の符号桁から数えて５桁目に“−１”が２個発生しているので、これを一組にまとめて一桁上に“−１”を発生した状態を示す。図１２（Ｄ）は、図１２（Ｃ）で最上位の符号桁から数えて４桁目に“−１”が３個発生しているので、２個を一組にまとめてひとつ上の桁に“−１”を発生させ、残り１個の“−１”をひとつ上の桁に伝搬させた状態を示す。図１２（Ｅ）は、図１２（Ｄ）で最上位の符号桁から数えて３桁目に“−１”が２個発生しているので、２個を一組にまとめてひとつ上の桁に“−１”を発生させた状態を示す。図１２（Ｆ）は、図１２（Ｅ）で最上位の符号桁から数えて２桁目に“−１”が１個発生しているので、この１個の“−１”をひとつ上の桁に伝搬させた状態を示し、図１１（Ｂ）の終了状態と同じである。ここで省略したが１個の“−１”をひとつ上の桁に伝搬させたときは、ステップＳ２１４で説明したように“１”をその桁に残している。このように“１”が特定の桁に１つ残るような状態を作り出すことが可能である。
【００３７】
なお、最終的に“１”が特定の桁に１つ残るような状態が作れれば他の方法も変形例として考えられる。例えば図１２（Ａ）の状態から、１個の“−１”を最上位の符号桁から数えて７桁目から４桁目に伝搬させ、５桁目に残った“１”と５桁目に発生している“−１”を相殺すると図１２（Ｃ）の状態に移ることが可能である。さらに、符号ビットの反転を一括して行うのではなく“−１”の下位桁からの伝搬に応じて、都度発生させてもよい。また、所定の符号ビットの桁が入力信号の内の最大の符号ビットの桁より上位の桁である時は、図１２（Ｆ）の状態から最大の符号ビットを反転させて“−１”を発生させ所定の符号ビットまで伝搬させればよい。
【００３８】
このように、本実施形態によれば、ビット幅が異なりかつ符号付きの複数の多ビット信号が入力され、所定の符号ビットの桁を持つ出力信号を出力する場合に、符号ビットの−Ｓ＝（Ｓの反転）−１の変換で生じた“−１”を、“１”が特定の桁に１つ残るような状態を作り出すように上位の桁に伝搬させて、“１”を付加する桁を決定することで、一律に符号拡張を行うことなくまた所定の桁のひとつの“１”の付加項のみで高速な演算が可能な演算器を提供することができる。
【図面の簡単な説明】
【００３９】
【図１】本発明の第１の実施形態に係る演算器の構成を示すブロック図。
【図２】（Ａ）乃至（Ｃ）は本実施形態に係る演算器の構造を示す図。
【図３】本実施形態に係るポート情報を示す図。
【図４】本実施形態に係る演算器の設計方法を示すフローチャート。
【図５】（Ａ）乃至（Ｃ）は本実施形態に係る遅延予測の一例を示す模式図。
【図６】（Ａ）乃至（Ｃ）は本実施形態に係るカウンタの適用を示す模式図。
【図７】本実施形態に係る演算器の構成を示すブロック図。
【図８】本発明の第２の実施形態に係る演算器の構成を示すブロック図。
【図９】本実施形態に係る前処理部における処理を示すフローチャート。
【図１０】本実施形態に係る前処理部における処理を示すフローチャート。
【図１１】（Ａ）（Ｂ）は本実施形態における入力信号の状態を示す図。
【図１２】（Ａ）乃至（Ｆ）は本実施形態に係る入力信号の状態を示す図。
【符号の説明】
【００４０】
１  演算器
５  時刻情報付きネットリスト
１０２  入力信号
１１０  カウンタ部
１２０  ｓｕｍ部レジスタ
１３０  ｃａｒｒｙ部レジスタ
８０２  入力信号
８０４  前処理部
８１０  カウンタ部
【図１】
2010072919.tif 000007
【図２】
2010072919.tif 000008
【図３】
2010072919.tif 000009
【図４】
2010072919.tif 000010
【図５】
2010072919.tif 000011
【図６】
2010072919.tif 000012
【図７】
2010072919.tif 000013
【図８】
2010072919.tif 000014
【図９】
2010072919.tif 000015
【図１０】
2010072919.tif 000016
【図１１】
2010072919.tif 000017
【図１２】
2010072919.tif 000018