スティッキービット生成回路及び乗算器

トップ :: G 物理学 :: G06 計算;計数

【発明の名称】	スティッキービット生成回路及び乗算器
【発明者】	【氏名】井出進博
【要約】	【課題】スティッキービット生成の処理を高速化して丸め処理に掛かる時間を短縮化することにより、乗算速度を更に向上させること。【解決手段】乗算結果を求める前のキャリー・セーブ・フォーマットの部分積の和より直接スティッキービット生成を行う。具体的には、キャリー・セーブ・フォーマットの部分積の和成分とキャリー成分の対応するビットごとの論理和の反転Ｇ、排他的論理和Ｐ、論理積Ｇを求め、各ビットの隣接上位ビットとキャリー伝搬を考慮した仮想和を求め、その全論理和をとることによりスティッキービット生成するため、キャリーの伝播がなく、高速にスティッキービットを生成することができる。

【特許請求の範囲】
【請求項１】２個の正規化オペランドを乗算する乗算手段と、前記乗算手段から得られる部分積の和成分の下位ビットとキャリー成分の下位ビットから論理和の反転ＫＢ（キャリー伝播の停止）、排他的論理和Ｐ（キャリーの伝播）、論理積Ｇ（キャリーの生成）を生成するＰＫＧ生成手段と、前記ＰＫＧ生成手段により得られた反転ＫＢ、排他的論理和Ｐ、論理積Ｇよりスティッキービットを生成するスティッキービット生成手段と、を具備することを特徴とするスティッキービット生成回路。
【請求項２】前記スティッキービット生成手段は、前記和成分とキャリー成分の対応するビットとその隣接上位ビットとの排他的論理和Ｐ、論理積Ｇ、反転ＫＢの各信号から、そのビットが１とならないことを示す信号を求めた後、前記各ビットが１とならないことを示す信号の全論理和をとることによりスティッキービットを生成することを特徴とする請求項１記載のスティッキービット生成回路。
【請求項３】前記ＰＫＧ生成手段はビットスライスで演算して前記排他的論理和Ｐ、論理積Ｇ、反転ＫＢの各信号を求め、前記スティッキービット生成手段はスティッキービットを複数ブロックに分割して求めることを特徴とする請求項１又は２記載のスティッキービット生成回路。
【請求項４】２個の正規化オペランドを乗算する乗算手段と、前記乗算手段から得られる部分積の和成分の下位ビットとキャリー成分の下位ビットから論理和の反転ＫＢ（キャリー伝播の停止）、排他的論理和Ｐ（キャリーの伝播）、論理積Ｇ（キャリーの生成）を生成するＰＫＧ生成手段と、前記ＰＫＧ生成手段により得られた反転ＫＢ、排他的論理和Ｐ、論理積Ｇよりスティッキービットを生成するスティッキービット生成手段と、前記乗算手段から得られる部分積の和成分の上位ビットとキャリー成分の上位ビットを加算する第１の加算手段と、前記スティッキービット生成手段により生成されたスティッキービットより乗算結果に丸め処理を行うかどうかを判定する判定手段と、前記ＰＫＧ生成手段により得られた反転ＫＢ、排他的論理和Ｐ、論理積Ｇよりキャリーを生成するキャリー生成手段と、前記第１の加算手段から得られる乗算結果に前記キャリー生成手段より生成されたキャリーを加算すると共に、前記判定手段により丸め処理を行うと判定された場合に１を加える第２の加算手段と、を具備することを特徴とする乗算器。
【請求項５】前記第１の加算手段による加算処理と前記ＰＫＧ生成手段及びスティッキービット生成手段の処理を並列に行うことを特徴とする請求項４記載の乗算器。

【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、浮動小数点演算器に係り、特に計算誤差を少なくするための補助用のビットであるスティッキービットを生成するスティッキービット生成回路及びこのスティッキービット生成回路を用いた乗算器に関する。
【０００２】
【従来の技術】従来より、コンピュータで使用するための高速乗算器の構成は様々に提案されている。このような高速乗算器では、基本的には、乗数の各ビットに対応する部分積を求め、１ビットだけ左にずれている複数の部分積を加算することにより積を求める。高速化のため、ブースのアルゴリズムなどのように乗数の複数ビットに対応する部分積を求めることで、部分積の数を減らし、加算作業を少なくする方法、加算器を木構造状に構成し、並列に加算する方法「ワラスの方法」、キャリー・セーブ加算器を用いて部分積を加算する方法、などが知られている。多くの高速乗算器は、これらの手法を用いており、部分積の和は、キャリー成分、和成分のキャリー・セーブ・フォームで求め、最後に１回だけ、桁上げ伝搬加算を実行する。以上は整数の乗算の方法であるが、浮動小数点において仮数を生成するときにも用いられる。
【０００３】図４は典型的な従来の浮動小数点乗算器の構成例である。５２ビットのオペランドＳと５２ビットのオペランドＴが乗算器２０１に入力され、ここで乗算されて、部分積の１０５ビットの和成分ＳＳ、１０５ビットのキャリー成分ＣＣが得られる。これら部分積の和成分ＳＳ、キャリー成分ＣＣは加算器２０２で加算されて、最終的な乗算結果が得られる。スティッキービット生成回路２０３は得られた乗算結果のシフトビットの論理和を取ることにより、スティッキービットを生成し、それを丸め回路２０４に渡す。
【０００４】丸め回路２０４は前記スティッキービットから乗算結果を丸めるかどうかを判定し、丸める場合は加算値１を加算器２０５に供給する。加算器２０５の出力値は選択回路（マルチプレクサ）２０６に入力され、ここで、１ビットシフトしたものとしないものとをオーバーフローするかどうかによって選択し、最終乗算結果を出力する。
【０００５】浮動小数点乗算器構成で乗算する場合、積は特定のフォーマットで定められたビット数に結果を丸めなければならないことが多い。例えば、二倍精度２進数に関する規格は５３ビット［整数部１ビット、小数点以下５２ビット］である。
【０００６】２つの５３ビット２進数の積は１０６ビットの長さである。ところが、二倍精度の結果はこの積のうち上位の５４ビットしか使用しない。ここで最上位ビットは桁あふれを示す。また、下位の５３ビットは、下位ビットから桁上げが生成されるか否か、丸めが必要であるか否か、さらに丸め値を確定するためにのみ使用され、値そのものは破棄される。
【０００７】
【発明が解決しようとする課題】ところで上記した積の丸めを行うには、まず、仮数を正規化しなければならない。２つの正規化オペランドＳ、Ｔの乗算を行う乗算器では、そのために仮数の右への１ビットシフトが生じる場合がある。仮数が正規化されるまでは、丸めが実行されるビット位置が確定しない。結局、演算は、最悪、最下位からのキャリーが最上位まで伝搬し、最上位の結果により正規化が施され、丸めの位置および丸め処理の有無の判定に必要なビットの位置が確定するのを待っていなければならないのが普通である。
【０００８】従って、下位ビットからの桁上げはクリテイカルパスに入っている。このような乗算器においては、通常、［１］積のキャリー成分、和成分の加算を加算器２０２で行い、［２］正規化、［３］スティッキービット生成を２０３の回路で行なった後、この結果を用いて、［４］丸めの判定を２０４の回路で行い、［５］丸めのインクリメントを加算器２０５で施すという手順で結果を発生するのが典型的である。
【０００９】しかしながら、このような構成では、スティッキービット生成の前に加算器２０２で最終加算を行う必要が必須であり、この加算に時間が掛かると共に、スティッキービット生成に全シフトビットの論理和を取らなければならず、スティッキービット生成までに時間が掛かり、一連の丸め処理に時間を要することになる。それ故、乗算器の速度が遅くなる。
【００１０】本発明は、上述の如き従来の課題を解決するためになされたもので、その目的は、スティッキービット生成の処理を高速化して丸め処理に掛かる時間を短縮化することにより、乗算速度を更に向上させることができるスティッキービット生成回路及びこのスティッキービット生成回路を用いた浮動小数点乗算器を提供することである。
【００１１】
【課題を解決するための手段】上記目的を達成するために、請求項１の発明の特徴は、２個の正規化オペランドを乗算する乗算手段と、前記乗算手段から得られる部分積の和成分の下位ビットとキャリー成分の下位ビットから論理和の反転ＫＢ（キャリー伝播の停止）、排他的論理和Ｐ（キャリーの伝播）、論理積Ｇ（キャリーの生成）を生成するＰＫＧ生成手段と、前記ＰＫＧ生成手段により得られた反転ＫＢ、排他的論理和Ｐ、論理積Ｇよりスティッキービットを生成するスティッキービット生成手段とを具備することにある。
【００１２】請求項２の発明の前記スティッキービット生成手段は、前記和成分とキャリー成分の対応するビットとその隣接上位ビットとの排他的論理和Ｐ、論理積Ｇ、反転ＫＢの各信号から、そのビットが１とならないことを示す信号を求めた後、前記各ビットが１とならないことを示す信号の全論理和をとることによりスティッキービットを生成することを特徴とする。
【００１３】請求項３の発明の前記ＰＫＧ生成手段はビットスライスで演算して前記排他的論理和Ｐ、論理積Ｇ、反転ＫＢの各信号を求め、前記スティッキービット生成手段はスティッキービットを複数ブロックに分割して求めることを特徴とする。
【００１４】請求項４の発明の特徴は、２個の正規化オペランドを乗算する乗算手段と、前記乗算手段から得られる部分積の和成分の下位ビットとキャリー成分の下位ビットから論理和の反転ＫＢ（キャリー伝播の停止）、排他的論理和Ｐ（キャリーの伝播）、論理積Ｇ（キャリーの生成）を生成するＰＫＧ生成手段と、前記ＰＫＧ生成手段により得られた反転ＫＢ、排他的論理和Ｐ、論理積Ｇよりスティッキービットを生成するスティッキービット生成手段と、前記乗算手段から得られる部分積の和成分の上位ビットとキャリー成分の上位ビットを加算する第１の加算手段と、前記スティッキービット生成手段により生成されたスティッキービットより乗算結果に丸め処理を行うかどうかを判定する判定手段と、前記ＰＫＧ生成手段により得られた反転ＫＢ、排他的論理和Ｐ、論理積Ｇよりキャリーを生成するキャリー生成手段と、前記第１の加算手段から得られる乗算結果に前記キャリー生成手段より生成されたキャリーを加算すると共に、前記判定手段により丸め処理を行うと判定された場合に１を加える第２の加算手段とを具備することにある。請求項５の発明の特徴は、前記第１の加算手段による加算処理と前記ＰＫＧ生成手段及びスティッキービット生成手段の処理を並列に行うことにある。
【００１５】
【発明の実施の形態】以下、本発明の実施の形態を図面に基づいて説明する。図１は、本発明の乗算器の一実施形態の構成を示したブロック図である。乗算回路１は、正規化オペランドＳ、Ｔを入力して乗算する乗算回路１と、乗算回路１から出力される和成分ＳＳ、キャリー成分ＣＣの上位ビットを加算して、２個のオペランドＳ（５２：０）とオペランドＴ（５２：０）の乗算結果を算出する加算回路２、論理和の反転ＫＢ（キャリー伝播の停止）、排他的論理和Ｐ（キャリーの伝播）、論理積Ｇ（キャリーの生成）を生成するＰＫＧ生成回路３、スティッキービット１００を発生するスティッキービット生成回路４、キャリーを生成するキャリー生成回路５、乗算結果に丸めを施すかどうかを判定する丸め回路６、乗算結果に丸めを施したり、或いはキャリーを加算する加算回路７、乗算結果の１ビットシフトしたものとしないものとをオーバーフローするかどうかによって選択する選択回路（マルチプレクサ）８を有している。
【００１６】図２は、ＰＫＧ生成回路３の構成例を示した回路図である。ＰＫＧ生成回路３は排他的論理和回路、論理和回路、論理積回路より構成されている。
【００１７】排他的論理和回路では、乗算回路１の演算結果ＳＳ、およびＣＣの各ビットを入力とし、対応するビットにおけるキャリーの伝播を示す信号Ｐを生成する。図中の信号ＰＢは、Ｐの反転である。
【００１８】論理和回路は、同様に前記演算結果ＳＳ、およびＣＣの各ビットを入力とし、対応するビットにおけるキャリーの消滅を示す信号Ｋを生成する。図中の信号ＫＢは、Ｋの反転を示す。
【００１９】論理積回路は、同様に前記演算結果ＳＳ、およびＣＣの各ビットを入力とし、対応するビットにおけるキャリーの生成を示す信号Ｇを生成する。
【００２０】図３は、スティッキー・ビット生成回路４の構成例を示した回路図である。
【００２１】スティッキー・ビット生成回路４は構成部材１０３，１０５，１０７，１０９の排他的論理和回路、構成部材１０４，１０６，１０８，１１０の論理和回路から構成されている。本回路は、ＰＫＧ生成回路の出力、反転ＫＢ信号、Ｐ信号を入力とし、スティッキー信号を生成する。処理がビット・スライスになっている点に注意されたい。
【００２２】本実施例では、倍精度の乗算結果の下位ＳＳ＜５０：０＞，ＣＣ＜５０：０＞を演算結果が得られる順番にビットごとに４つのフィールドに分割して求めているが、一度に演算しても何ら演算結果に変わりはない。本実施例のように分割することにより、乗算結果が得られた部分から計算できるので、一度に実行するより高速にスティッキー・ビット生成を行うことができる。
【００２３】次に、本実施形態の動作について説明する。乗算回路１は正規化オペランドＳ、Ｔを乗算して、部分積の和成分ＳＳとキャリー成分ＣＣを出力するもので、部分積の和がキャリーセーブ・フォームで生成され、倍精度の場合を仮定すると、和成分ＳＳ（１０５：０）、キャリー成分ＣＣ（１０５：０）となる。和成分ＳＳとキャリー成分ＣＣの上位ビットは加算回路２に入力され、下位ビットはＰＫＧ生成回路３に入力される。
【００２４】ＰＫＧ生成回路３はキャリー・セーブ・フォーマットの部分積の和成分ＳＳ（５０：０）とキャリー成分ＣＣ（５０：０）を入力とし、各対応するビットごとの論理和の反転ＫＢ、排他的論理和Ｐ、論理積Ｇをビットスライスで求める。論理和の反転ＫＢ、排他的論理和Ｐ、論理積Ｇはスティッキービット生成回路４に渡され、スティッキービット生成回路４は論理和の反転ＫＢ、排他的論理和Ｐ、論理積Ｇに基づいてスティッキービット１００を生成し、得られたスティッキービット１００を丸め回路６に出力する。
【００２５】スティッキービット生成回路４は入力される各ビットのキャリー情報をもとに、スティッキービットを段階的に生成する。スティッキービット生成回路４は複数のＸＯＲなる論理ゲートと複数の論理和ゲートを備え、各ビットのＰ信号と１ビット上位のＫとのＸＯＲをとり、各ビットに１が立つか否かを求め、前記各ビットに１が立つか否かを示す信号の論理和を取ることにより、スティッキービット１００を生成する。スティッキービット生成回路４はこのようにキャリーの生成過程で加算を行っていないので、キャリーの伝播がなく、ステッキービットを高速に求めることが出来る。
【００２６】ここで、本例では、スティッキービットを４つのブロックに分割して求めている。これは乗算アレーをワラスの方法で加算しているためである。部分積の部分和は下位の部分から順番に確定していく。本例では、倍精度の乗算アレーを構成しているので、下位よりＳＳ（３：０、ＣＣ（３：０）の４ビット、ＳＳ（１１：４）、ＣＣ（１１：４）の８ビット、ＳＳ（２５：１５）、ＣＣ（２５：１５）の１４ビット、残りＳＳ（１０５：２６）、ＣＣ（１０５：２６）が段階的に確定していく。
【００２７】本方式では、スティッキービットはビット・スライスで行った演算結果の論理和をとればいいので、どのビットから計算を開始してもかまわない。一般に多ビットの論理和をとる処理は、木構造で段階的に行う必要があり、本質的に時間のかかる処理である。スティッキービットの生成を更に高速化するため、本例では確定した部分積の部分より、段階的にスティッキービットの生成を行っている。
【００２８】丸め回路６は入力されるスティッキービットから丸めを行うかどうかを判定し、丸めを行う場合は加算回路７に加算値“１”を出力する。加算回路７は丸めを行う場合に限り、加算回路２の乗算結果に“１”を加算して、丸めを行うがその他の場合は乗算結果をそのまま選択回路８に出力する。また、キャリー生成回路５は、キャリー・セーブ・フォーマットの部分積の和成分ＳＳ（５０：０）とキャリー成分ＣＣ（５０：０）を入力とし、部分積の下位のキャリ－Ｃ５１を求め、求めたキャリーを加算回路７に送る。これにより、加算回路７では加算回路２から入力される乗算結果にキャリーを加算し、正しい乗算結果を得ている。
【００２９】選択回路８は乗算結果の１ビットシフトしたものとしないものとをオーバーフローするかどうかによって選択し、最終の乗算結果を出力する。
【００３０】本実施形態によれば、乗算回路１の部分積の和成分ＳＳとキャリー成分ＣＣからＰ、Ｋ、Ｇ信号を生成し、これらＰ、Ｋ、Ｇ信号からスティッキービット１００をビットスライスで求めることにより、キャリーの伝搬がないことと、加算回路２による部分積の和成分ＳＳとキャリー成分ＣＣの加算処理と並列にスティッキービット１００を求める処理を行うことにより、スティッキービット１００を高速に生成することができる。これにより、乗算結果を得る時間を短縮化でき、回路の乗算速度を向上させることができる。
【００３１】尚、本発明は上記実施形態に限定されることなく、その要旨を逸脱しない範囲において、具体的な構成、機能、作用、効果において、他の種々の形態によっても実施することができる。
【００３２】
【発明の効果】以上詳細に説明したように、本発明によれば、浮動小数点演算器に於けるスティッキービット生成回路において、乗算結果を求める前のキャリー・セーブ・フォーマットの部分積の和成分とキャリー成分の対応するビットごとの論理和の反転Ｇ、排他的論理和Ｐ、論理積Ｇを求め、得られＰ、Ｋ、Ｇ信号からスティッキービットを求めることにより、スティッキービット生成の処理を高速化して丸め処理に掛かる時間を短縮化することにより、乗算速度を更に向上させることができる。

【出願人】	【識別番号】０００００３０７８【氏名又は名称】株式会社東芝
【出願日】	平成１２年９月２６日（２０００．９．２６）
【代理人】	【識別番号】１０００８３８０６【弁理士】【氏名又は名称】三好秀和（外７名）
【公開番号】	特開２００２－１０８６０６（Ｐ２００２－１０８６０６Ａ）
【公開日】	平成１４年４月１２日（２００２．４．１２）
【出願番号】	特願２０００－２９２６５４（Ｐ２０００－２９２６５４）