(57)【特許請求の範囲】
【請求項１】
ビットＸｉを有するワードＸの内容とビットＹｉを有するワードＹの内容について演算を行ってビットＺｉを有する結果ワードＺを生成する装置であって、ｉ＝0〜N-1であり、Ｚ０が前記結果ワードＺの最下位ビットであり、ＺＮ−１が前記結果ワードＺの最上位ビットであり、
前記ワードＸと前記ワードＹと前記結果ワードＺとをそれぞれ、複数のサブワードへと区画化する手段であって、前記ワードＸの各サブワードに対応して前記ワードＹのサブワードおよび前記結果ワードＺのサブワードが１つずつ存在することからなる、手段と、
演算手段
を備え、
前記演算手段は、第１の命令に応じて前記Ｘの各サブワードの各ビットとそれに対応する前記Ｙの各サブワードの各ビットとを加算する第１の演算を実施し、及び、第２の命令に応じて、前記Ｘの各サブワードの各ビットとそれに対応する前記Ｙの各サブワードの各ビットとを加算し、かつ、その加算結果を２で除算する第２の演算を実施するものであり、さらに、前記第１の演算中の前記加算と前記第２の演算中の前記加算のそれぞれにおいて、Ｎ個のビットＸi (i＝0〜N-1)のそれぞれに対応する、Ｎ個の各生成ビットＳi(i＝0〜N-1)およびＮ個の各伝搬ビットを生成し、
前記区画化する手段は、前記ワードＸの前記ビットがサブワードの最上位ビットである場合には、前記生成ビットおよび前記伝搬ビットを、実行されている演算によって決定される値にする第１のビット値設定手段を備え、
前記演算手段は、Ｎ個の第１の多重化手段を備え、該Ｎ個の第１の多重化手段の各々は、前記結果ワードＺのビットの内の１つを表す信号を生成し、該第１の多重化手段は、前記結果ワードＺの各ビットＺｐ(p＝0〜N-1)毎に１つずつあり、Ｚｐに対応する前記第１の多重化手段の各々は、前記第１の命令に応じてＳｐをＺｐに接続することからなる、装置。
【請求項２】
サブワードの最上位ビットである各ビットＸｐに対応する桁上げビットＣｐを生成する手段を更に備え、Ｚｐに対応する前記第１の多重化手段が、前記第２の命令に応じて、Ｚｐが前記サブワードの内の１つの内側にある場合にはＺｐをＳｐ＋１に接続し、Ｚｐが前記結果ワードＺのサブワードの内の１つの最上位ビットである場合には、ＺｐをＣｐに接続し、Ｃｐが、Ｚｐを含む前記結果ワードＺのサブワードに対応する前記Ｘのサブワードの最上位ビットについて演算を行う前記演算手段により生成される前記桁上げビットである、請求項１の装置。
【請求項３】
Ｚｐに対応する前記第１の多重化手段が、Ｚｐが前記結果ワードＺのサブワードの内の１つの最下位ビットである場合に、Ｚｐを(Ｓｐ＋１  ＯＲ Ｓｐ)へ接続する手段を更に備える、請求項２の装置。
【請求項４】
サブワードの最上位ビットである各ビットＸｐに対応する桁上げビットＣｐを生成する手段を更に備え、Ｚｐに対応する前記第１の多重化手段が、前記第２の命令に応じて、Ｚｐが前記結果ワードＺのサブワードの内の１つの内側にある場合にはＺｐをＳｐ＋１に接続し、Ｚｐが前記結果ワードＺのサブワードの内の１つの最上位ビットである場合には、ＺｐをＳｐに接続する、請求項１の装置。
【請求項５】
桁上げビット伝搬手段を備え、さらに、前記演算手段の代わりとして、直列に接続された複数の加算段を備えており、その各加算段が、前記ワードＸからの１つ以上のビットとそれに対応する前記ワードＹから得たビットとについて演算を行う手段を備え、前記桁上げビット伝搬手段は、前記各加算段からの桁上げビットを前記直列接続中の次の加算段へ伝搬させ、前記区画化する手段は、前記第１のビット値設定手段に代えて第２のビット値設定手段を備え、該第２のビット値設定手段は、前記加算段が前記ワードＸ中の異なるサブワード間のビットについて演算を行う場合には、前記桁上げビットを、実行されている演算により決定される値にすることからなる、請求項１の装置。
【請求項６】
前記加算段が、Ｘｉ(i＝0〜N-1)についての演算から導出される結果ワードＺのＮ個のビットＳi(i＝0〜N-1)を生成し、前記演算手段が、前記Ｎ個の第１の多重化手段に代えて、Ｎ個の第２の多重化手段を備え、該Ｎ個の第２の多重化手段の各々は、前記結果ワードＺの各ビットを表す信号を生成し、該第２の多重化手段は、前記結果ワードＺの各ビットＺｐ(p＝0〜N-1)毎に１つずつあり、Ｚｐに対応する前記第２の多重化手段の各々は、前記第１の命令に応じてＳｐをＺｐに接続する、請求項５の装置。
【請求項７】
Ｚｐに対応する前記第２の多重化手段が、前記第２の命令に応じて、Ｚｐが前記結果ワードＺのサブワードの内の１つの内側にある場合にはＺｐをＳｐ＋１に接続し、Ｚｐが前記結果ワードＺのサブワードの内の１つの最上位ビットである場合にはＺｐをＣｐに接続し、そのＣｐは、Ｚｐを含む前記結果ワードＺのサブワードに対応する前記Ｘのサブワードの最上位ビットについて演算を行う前記加算段により生成される前記桁上げビットである、請求項６の装置。
【請求項８】
Ｚｐに対応する前記第２の多重化手段が、Ｚｐが前記結果ワードＺのサブワードの内の１つの最下位ビットである場合にＺｐを(Ｓｐ＋１  ＯＲ Ｓｐ)へ接続する手段を更に備える、請求項７の装置。
【請求項９】
ビットＸｉを有するワードＸの内容とビットＹｉを有するワードＹの内容について演算を行ってビットＺｉを有する結果ワードＺを生成する装置（ｉ＝0〜N-1）であって、Ｚ０が前記結果ワードＺの最下位ビットであり、ＺＮ−１が前記結果ワードＺの最上位ビットであり、
前記ワードＸと前記ワードＹと前記結果ワードＺとをそれぞれ、複数のサブワードへと区画化する手段であって、前記ワードＸの各サブワードに対応して前記ワードＹのサブワードおよび前記結果ワードＺのサブワードが１つずつ存在することからなる、手段と、
演算手段と、
丸め手段
を備え、
前記演算手段は、第１の命令に応じて前記Ｘの各サブワードの各ビットとそれに対応する前記Ｙの各サブワードの各ビットとを加算する第１の演算を実施し、及び、第２の命令に応じて、前記Ｘの各サブワードの各ビットとそれに対応する前記Ｙの各サブワードの各ビットとを加算し、かつ、その加算結果を２で除算する第２の演算を実施するものであり、さらに、前記第１の演算中の前記加算と前記第２の演算中の前記加算のそれぞれにおいて、Ｎ個のビットＸi (i＝0〜N-1)のそれぞれに対応する、Ｎ個の各生成ビットＳi(i＝0〜N-1)およびＮ個の各伝搬ビットを生成し、
前記区画化する手段は、前記ワードＸの前記ビットがサブワードの最上位ビットである場合には、前記生成ビットおよび前記伝搬ビットを、実行されている演算によって決定される値にする手段を備え、
前記演算手段は、Ｎ個の第１の多重化手段を備え、該Ｎ個の第１の多重化手段の各々は、前記結果ワードＺのビットの内の１つを表す信号を生成し、該第１の多重化手段は、前記結果ワードＺの各ビットＺｐ(p＝0〜N-1)毎に１つずつあり、Ｚｐに対応する前記第１の多重化手段の各々は、前記第１の命令に応じてＳｐをＺｐに接続し、
前記丸め手段は、前記２での除算の結果として丸め誤差が生じた場合に、その除算結果を１つ下の奇数整数に丸めることからなる、装置。
【請求項１０】
ビットＸｉを有するワードＸの内容とビットＹｉを有するワードＹの内容について演算を行ってビットＺｉを有する結果ワードＺを生成する装置であって、ｉ＝0〜N-1であり、Ｚ０が前記結果ワードＺの最下位ビットであり、ＺＮ−１が前記結果ワードＺの最上位ビットであり、
前記ワードＸと前記ワードＹと前記結果ワードＺとをそれぞれ、複数のサブワードへと区画化する手段であって、前記ワードＸの各サブワードに対応して前記ワードＹのサブワードおよび前記結果ワードＺのサブワードが１つずつ存在することからなる、手段と、
演算手段
を備え、
前記演算手段は、第１の命令に応じて前記Ｘの各サブワードの各ビットとそれに対応する前記Ｙの各サブワードの各ビットとを加算する第１の演算を実施し、第２の命令に応じて前記Ｘの各サブワードの各ビットとそれに対応する前記Ｙの各サブワードの各ビットとの減算を行う第２の演算を実施し、第３の命令に応じて前記Ｘの各サブワードの各ビットとそれに対応する前記Ｙの各サブワードの各ビットとの減算を行い、かつ、その減算結果を２で除算する第３の演算を実施するものであり、さらに、前記第１の演算中の前記加算、前記第２の演算中の前記減算及び前記第３の演算中の前記減算のそれぞれにおいて、Ｎ個のビットＸi (i＝0〜N-1)のそれぞれに対応する、Ｎ個の各生成ビットＳi(i＝0〜N-1)およびＮ個の各伝搬ビットを生成し、
前記区画化する手段は、前記ワードＸの前記ビットがサブワードの最上位ビットである場合には、前記生成ビットおよび前記伝搬ビットを、実行されている演算によって決定される値にする手段を備え、
前記演算手段は、Ｎ個の多重化手段を備え、該Ｎ個の多重化手段の各々が、前記結果ワードＺの各ビットを表す信号を生成し、該多重化手段は、前記結果ワードＺの各ビットＺｐ(p＝0〜N-1)毎に１つずつあり、Ｚｐに対応する前記多重化手段の各々は、前記第１の命令及び前記第２の命令に応じてＳｐをＺｐに接続することからなる、装置。
【請求項１１】
前記第２の命令が平均命令であり、前記除算がシフト操作によって行われる、請求項９の装置。
【請求項１２】
前記装置が、前記演算手段に代えて、直列に接続された複数の加算段を備えており、その各加算段が、前記ワードＸからの１つ以上のビットとそれに対応する前記ワードＹから得たビットとを加算する演算を行う手段を備えており、それら加算段が、Ｘｉ(ｉ＝0〜N-1)についての演算から導出されるＮ個の生成ビットＳｉと、桁上げ出力ビットＣＮ−１を生成し、および、前記装置が、前記Ｎ個の第１の多重化手段に代えて、Ｎ個の第２の多重化手段を備えており、その第２の多重化手段の各々が、前記結果ワードＺの各ビットの内の１つを表す信号を生成し、かつ、前記結果ワードＺの各ビットＺｐ(ｐ＝0〜N-1)毎に１つずつ存在し、Ｚｐに対応する前記第２の多重化手段が前記平均命令に応じてＳｐをＺｐ＋１に接続する、請求項１１の装置。
【請求項１３】
Ｚｐに対応する前記第２の多重化手段が、p＝0〜N-2である場合には前記平均命令に応じてＺｐをＳｐ＋１へ接続し、p＝N-1である場合にはＺｐをＣＮ−１へ接続する、請求項１２の装置。
【請求項１４】
Ｚｐに対応する前記第２の多重化手段が、p＝0である場合にはＺｐを(Ｓｐ＋１  ＯＲ Ｓｐ)へ接続する手段を更に備える、請求項１３の装置。
【請求項１５】
減算命令に応じて前記ワードＸと前記ワードＹとの差を２で除算した値を生成する手段を更に備えており、その生成結果が前記結果ワードを決定することからなる、請求項１１の装置。
【請求項１６】
前記１つ下の奇数整数への丸めは、前記シフト操作によるシフトの結果として丸め誤差が生じた場合に行われる、請求項１１の装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明はコンピュータに関し、特に、コンピュータで使用するための算術演算装置に関する。
【０００２】
【従来の技術】
コンピュータは通常、所定の最大ビット数の数値を加算する加算器を含む算術演算論理装置を備えている。マイクロプロセッサ等では、32ビット長および64ビット長のワード用の加算器が一般的である。それら加算器はまた、それよりもずっと小さなワードについても機能するが、その場合には、加算器に含まれる論理回路の大部分がアイドル状態となる。例えば、64ビット加算器を使用して２つの８ビットワードを加算することができる。この加算は、対応する64ビットワードの最下位部分に各８ビットワードを置き、次いでその64ビットワードを加算することにより行われる。この加算処理中には、各ワードの上位７バイトの加算に関する論理回路が事実上アイドル状態になる。したがって、この演算中には加算器の能力の７／８が無駄になっている。
【０００３】
マルチメディアデータ処理では、多数の小さなワード対の加算を伴う計算に出会うことが多い。例えば、２つのグレースケール画像を加算して加算画像を生成することに関する問題について考察する。画像の各画素は典型的には、その画像中の対応する一点における光強度を表す１バイトの整数として格納される。記憶空間は常に貴重なものであるので、画像の画素は一般にはワードへとパックされる。コンピュータの基本ワードサイズが32ビットであれば、１ワードにつき４つの画素をパックすることができる。各画像は100万個の画素を有することができる。したがって、加算画像の計算には、構成要素となる各画像から得た２つの画素を加算して加算画像中の対応画素を生成することが含まれる。各画像に100万個の画素が存在する場合には、そのような加算を100万回実行しなければならない。各加算では、構成要素となる各画像から１つずつ得た２ワードの「アンパック」を行い、そのアンパックが行われた２つの１バイトを加算し、その結果を加算画像における１ワード内の正しい１バイト中に記憶させる、ということが必要とされる。
【０００４】
コンピュータの基本ワードサイズが32ビットである場合、そのコンピュータは、32ビット加算器を有するのが普通である。上述のような計算時には、加算器の加算能力の75％がアイドル状態となる。したがって、従来の算術演算論理装置は、この種の画像計算を実行する際には最適には使用されていない。
【０００５】
この種の演算で行われる計算の回数は過度なものとなり得る。このため、特殊並列コンピュータアーキテクチャを使用して、加算画像コマンドを実行してから加算画像が完成するまでの時間を短縮させることが多い。その全ての加算は互いに独立したものであり、このため、その加算は順序にかかわらず並列に実行することができる。Ｍ個の加算器を備えたコンピュータは、原則的には、メモリから加算器への画素の移動がネックにならない限り、１／Ｍの時間で結果を提供することができる。したがって、多数の加算を並列に実行することが可能なコンピュータアーキテクチャを提供するのが有用であろう。残念ながら、このような追加の加算器とそれらを制御するのに必要なハードウェアとを提供するコストは法外な金額になることが多い。
【０００６】
上述の画像加算に関する問題には平均画像の生成が含まれることが多いことにも留意されたい。構成要素となる各画像中の対応画素の平均である画素を有する画像は、上述の加算画像の画素を生成してその各加算画像画素の強度を２で除算したものと等価である。この種の画像計算は、それによりオーバーフローが防止されるので好適なものである。構成要素となる各画像の２つの対応する画素値が128よりも大きな値を有する場合には、その加算画像画素は８ビットの整数として表すことができないものとなる。この問題を回避するために平均画像が使用される。これは、構成要素となる画像の画素が１バイト整数であれば平均画像画素は常に１バイト整数として表すことができるからである。
【０００７】
【発明が解決しようとする課題】
広範には、本発明の目的は、改良された加算器を提供することにある。
【０００８】
本発明の別の目的は、加算器の幅よりも小さなワードを伴う多数の加算を行う際に高効率で動作する加算器を提供することにある。
【０００９】
本発明のもう１つの目的は、単一のマシンサイクルで２つの数の平均を生成することのできる加算器を提供することにある。
【００１０】
本発明の更なる目的は、加算器の幅よりも小さな数の対の多数の平均値を計算するように適応させた加算器を提供することにある。
【００１１】
本発明の上述その他の目的は、本発明の以下の詳細な説明および図面から当業者にとって明らかなものとなろう。
【００１２】
【課題を解決するための手段】
本発明は、２つの整数の平均を生成するためにも使用することのできる算術演算論理装置である。この算術演算論理装置は、入力された整数のサブワードについて並列に演算を行う複数の副加算器へと分割可能な加算器を含む。したがって、この加算器は、各整数がある所定の長さのものである１組の２つの整数を加算するために、また、各整数の長さの合計が所定の長さ以下である場合には複数組の２つの整数を加算するために使用することができる。この加算器は、順序正しく接続された複数の加算器段から構成される。各加算器段は、１つ以上のビットについて演算を行って合計ビットおよび桁上げ出力ビットを生成する。入力されたワードがサブワードへと区画化される際に桁上げ出力がサブワードの境界を横切って伝搬するのを防止するために、サブワードの考え得る境界に切断回路が設けられる。
【００１３】
２つのオペランドの平均を計算することのできる本発明の実施例では、算術演算論理装置の各出力ビットに、副加算器によって生成された結果に対して右シフト演算を実施するマルチプレクサが含まれる。結果の最上位ビットに接続されたマルチプレクサは、対応するサブワードの最上位ビットを加算することにより生成された桁上げビットへと前記最上位ビットを接続する。各結果の最下位ビットに接続されたマルチプレクサは、平均結果の偏りを防ぐために奇数丸め(round odd)方式を実施するよう修正可能なものである。
【００１４】
【実施例】
本発明は、複数の部分ワード加算または平均演算を並列に実行するように構成することのできる改良された加算器である。図１を参照すると、本発明による加算器10は、２つのＮビットオペランド12,14を受容する。第１オペランドの各ビットをＸi(i=0〜N-1)で示し、第２オペランドの各ビットをＹiで示す。それらオペランドは、通常はコンピュータのプロセッサ中の２つのレジスタに格納される。しかし、本発明は、コンピュータ中に含まれない回路という形で実施することができる。加算器10は、従来の加算器として動作する場合には、ＸおよびＹの２の補数の和と１ビット桁上げ出力とを有するＮビット出力ワード16を生成する。以下の説明では、加算器10の出力16の各ビットをＺiで示すこととする。加算結果は通常は、ＣＰＵのレジスタの１つに再び格納される。
【００１５】
以下の説明では、様々なワード中のビットに最下位のものから最上位のものへと番号付けしてある。即ち、Ｘ0はオペランドＸの最下位ビットであり、ＸN-1はオペランドＸの最上位ビットである。ワードＹ,Ｚについても同様の規則を用いることとする。
【００１６】
本発明は、各オペランドを複数のサブワードへと分割することを可能にする。説明を簡単にするため、まず、各オペランドを部分オペランドへと１回だけ分割することに関して本発明を説明することとする。この場合、オペランドＸの最初のｋビットＸ0〜Ｘk-1は、ワードＸの第１の部分オペランド18の各ビットであり、残りのビットＸk〜ＸN-1は、ワードＸの第２の部分オペランド17の各ビットである。同様に、オペランドＹを部分ワード19,20へと分割する。この態様では、ビットＺ0〜Ｚk-1は部分オペランド18,20の和のビットであり、ビットＺk〜ＺN-1は部分オペランド17,19の和のビットである。以下の説明では、それら２つの結果を部分和またはサブワード和と称することとする。以下で詳細に説明するように、本発明は、２つの部分オペランドの各々の平均値を計算するのに使用することも可能なものである。平均値を計算する場合、ビットＺ0〜Ｚk-1は部分オペランド18,20の平均のビットであり、ビットＺk〜ＺN-1は部分オペランド17,19の平均のビットである。
【００１７】
まず、桁上げ伝搬(carry propagate)アーキテクチャとしても知られるリップル桁上げ(ripple carry)アーキテクチャを利用した単一ビット加算段から構成された加算器に関して本発明を説明することとする。また、本発明による教示を他の加算器アーキテクチャに利用する方法については後に詳述することとする。次に図２を参照する。同図は、加算のみを実行する本発明による加算器30の一部を示すブロック図である。即ち、加算器30は平均計算を実行しない。加算器30は、１ビット加算器段のアレイで構成されている。本発明は、加算器が部分ワードについて並列加算を実行できるように段を減結合させる(decouple)ことができる点で従来の加算器とは異なるものである。各々の単一ビット加算器は、オペランドＸからの１ビットおよびオペランドＹからの１ビットの２ビットと、ｉ番目の段に関してＣiで示す加算器の前段からの桁上げビットとを加算して、和ビットおよび新しい桁上げビットを生成する。図２に示す２つの段は、部分オペランド18,20の最上位ビットと部分オペランド17,19の最下位ビットとを加算するのに使用される単一ビット加算器である。例えば、単一ビット加算器31は、ビットＣk-2,Ｘk-1,Ｙk-1を加算して和ビットＳk-1および桁上げビットＣk-1を生成する。以下の説明では、ビットＸp,Ｙpを加算して和ビットＳpを生成する加算器の段を、加算器のｐ番目の段と称することにする。桁上げ伝搬を使用する従来の加算器では、各段からの桁上げビットは、１ビット加算器のアレイにおいて各段の桁上げビット入力をその前段の桁上げビット出力に接続することにより、次の段へ伝搬される。
【００１８】
本発明では、２つの部分オペランドを分離する境界の直前の段からの桁上げビットがブロック化回路33に接続されている。単一のワードとして扱われるレジスタ12,14の内容全体について演算を行う従来の加算器として加算器30を使用する場合には、ブロック化回路33が、単一ビット加算器31の桁上げ出力を単一ビット加算器32の桁上げ入力に接続する。加算器30を使用して各レジスタ中のビットk-1とビットkとの間の部分ワード境界で２つの加算を並列に実行する場合には、ブロック化回路33は単に、単一ビット加算器31からの桁上げビットが単一ビット加算器32の桁上げ入力に伝搬するのを防止する。これは、１ビット信号Ｍkに応じて行われる。ビットＭkを指定する方法について以下で詳述する。加算器30の残りの段では、他の全ての単一ビット加算器の桁上げ出力が従来の態様で接続される。このため、桁上げビットは、特定の部分オペランドについて演算を行う加算器30の各セクション内で従来の態様で伝搬する。各加算器段からの和ビットは、対応する出力ポートのビットに接続される。
【００１９】
従来の加算器では、オペランドの最上位ビットについて演算を行う単一ビット加算器からの桁上げビットを使用してオーバーフローを検出する。この態様を各部分オペランド毎に実施する場合には、各部分オペランドの最上位ビットの加算による桁上げビットが適当なオーバーフロー回路に接続される。本発明の一実施例では、桁上げビットの論理和が求められ、その結果として得られるビットを使用してオーバーフローが検出される。そのビットは、オーバーフロー時にトラップをトリガするのに使用可能なものであり、また、そのビットと単一ビットレジスタの内容との論理和を求めることもできる。後者の場合、プログラムは、レジスタの内容を検査して、最後にレジスタが検査されてからの演算でオーバーフローになったものがあるか否かを判定することができる。
【００２０】
平均計算を実施しない場合には、本発明は、２つの部分オペランド間の境界にまたがる可能性のある各々の段対の間にブロック化回路33等のブロック化回路を単に設けることにより、従来の加算器から構成することができる。Ｘ入力およびＹ入力を任意の数の任意のサイズの部分オペランドへと分割する場合には、各々の単一ビット加算器対の間にブロック化セクションを設ける。このブロック化セクションは、各部分オペランドの最上位ビットの位置を指定するビットＭkを有するマスクにより構成される。以下の説明では、このマスクを境界マスクと称することにする。この境界マスクの各ビットは、加算器中のレジスタに格納可能なものであり、また、加算器が存在するプロセッサの命令デコード回路により実行される命令から直接生成することも可能なものである。
【００２１】
本発明の上記実施例は、オペランドの加算を実行する。ブロック化回路33は、ブロック化回路のところに境界を有する副加算器へと加算器が分割される加算中に、桁上げビットを０と置換する。また、加算器が同様に分割される２の補数の減算に加算器を使用する場合には、桁上げビットを０ではなく１にしなければならない。図２に示すブロック化回路33は、「０」または「１」の値を有する入力Ｆを供給することにより加算および減算を両方とも実施する。ブロック化回路33で境界が活動状態である場合、Ｆの値は、次の段に与えられる値となる。また境界が非活動状態である場合には、ブロック化回路33は単に桁上げビットＣk-1を次段に送る。
【００２２】
本発明の上述の実施例は平均計算を実行しないものである。これらの実施例は従来に勝る重要な利点を提供するものであるが、本発明の好適実施例は、平均を計算する機能を提供する追加的なハードウェアを提供するものとなる。次いで、平均計算を実行するのに必要となる追加的なハードウェアについて説明することとする。２つのオペランドの平均は、２つのオペランドの和を２で除算した値である。２で除算することは、２つのオペランドの和を右に１ビットだけシフトさせることと等価である。その和の最下位ビットは失われる。平均の最上位ビットは、部分オペランドの最上位ビットについて演算を行う単一ビット加算器の桁上げ出力となる。例えば、部分オペランド18,20の平均は、ＳiをＺi-1(ｉ＝1,..,k-1)に経路指定し、Ｓ0を廃棄し、Ｃk-1をＺk-1に経路指定することによって計算することができる。
【００２３】
入力の部分オペランドへの所与の分割に関し、３種類の段がある。部分オペランドの最下位ビットの加算を行う段は、平均計算を実行する際にその和ビットを廃棄する。以下の説明では、この種の段を最下位ビット段と称することにする。また、部分オペランドの最上位ビットの加算を行う段は、その加算により生成された桁上げビットをその加算結果の最上位ビットへ経路指定し、その和ビットをその加算結果の最上位ビットの次のビットへ経路指定すると共に、桁上げ伝搬チェーンを断たなければならない。以下の説明では、この種の段を最上位ビット段と称することにする。また、最下位ビットと最上位ビットとの間のビットの加算を行う段は、その段が加算を実行する際に使用する位置の１つ右の位置にその段の和ビットを経路指定しなければならない。即ち、ｉ番目の段は、その和ビットをＺi-1に経路指定する。以下の説明では、この種の段を内側ビット段と称することにする。
【００２４】
部分オペランドの境界をワード中の任意の点に位置させることができる実施例が可能ではあるが、一般には、少数の位置にのみ境界を設ける方が有用となる。例えば、通常32ビットワードの加算を行うコンピュータで加算器を使用する場合には、そのような４バイトのワードを分割する境界が一層有用なものとなる。これは、そのようなシステムでは部分オペランドが通常は１バイトまたは２バイトとなるからである。この場合、各加算器段は、上述の３つの役割のうちの多くとも２つで機能することができなければならない。段(N-1)は最上位ビット段として働くだけでよい。同様に、段０は最下位ビット段として働くだけでよい。その他の全ての段は、加算器を全ワード加算に使用する場合には内側ビット段として機能することができなければならない。更に、並列サブワード加算または平均の最上位ビット段または最下位ビット段になることができる段は、それらの構成へと切り替えることができなければならない。
【００２５】
各段の間には差が存在し、その差は、加算器段がＸレジスタおよびＹレジスタのビットから和ビットを如何に生成するかの詳細にではなく、各々の加算器段により生成される和信号Ｓiが加算器の出力ビットＺiに経路指定される態様にある。次に図３を参照する。同図は、本発明による加算器100の一部を示すブロック図である。加算器100は、加算セクション102が典型例である複数の４ビット加算セクションから構成されている。加算セクション102は、Ｘ,Ｙレジスタのビットq〜q+3について演算を行って和ビットＳq〜Ｓq+3を生成する。各加算セクションは、Ｘレジスタから４ビット、Ｙレジスタから４ビットを受容してそれらに対応する４つの和ビットを生成する点で、４つの上述の単一ビット加算器と機能的に等価なものである。更に、加算セクション102は、桁上げビットＣq+3を生成し、桁上げビットＣq-1を受容する。ブロック化回路110,112は、加算セクション102の両側に示されている。
【００２６】
加算器100は、Ｎ個の和ビットＳi(i=0〜N-1)を生成する。加算器100を単一オペランド加算器として使用する場合には、i番目の和ビットＳiはその加算器のi番目の出力ビットＺiに経路指定される。各出力ラインＺiはマルチプレクサに接続される。典型的なマルチプレクサを図３に符号121,124で示す。マルチプレクサは、平均信号Ａにより制御される。Ａが偽である場合、ＳiはＺiに接続される(i=0〜N-1)。またＡが真である場合には、段の種類に関して上記説明の３つの可能性が存在する。結果の内側のビットにのみなることができる出力ラインに接続されたマルチプレクサは、Ｓi+1をＺiに接続する。マルチプレクサ122,123はそのようなマルチプレクサの例である。
【００２７】
第２の種類のマルチプレクサは、結果の内側ビットまたは最上位ビットのいずれかになることのできる出力ラインに接続されたものである。そのようなマルチプレクサを符号121で示す。これらのマルチプレクサを最上位ビットマルチプレクサと称することとする。最上位ビットマルチプレクサは、３→１マルチプレクサであり、この３→１マルチプレクサは、Ａと、そのマルチプレクサが結果の最上位ビットに接続されているか否かを判定するマスクビットとに応じて動作する。Ａが偽である場合、最上位ビットマルチプレクサはＺiをＳiに接続する。また、Ａが真であり、マスクビットもまた真である場合には、最上位ビットマルチプレクサはＺiをＣiに接続する。ここで、Ｃiは、Ｓiを生成した段により生成される桁上げビットである。また、Ａが真であり、マスクビットが偽である場合には、最上位ビットマルチプレクサはＺiをＳi+1に接続する。ＺN-1に接続されたマルチプレクサは、２→１マルチプレクサで十分である最上位ビットマルチプレクサである、ということに留意されたい。これは、そのマルチプレクサが内側マルチプレクサになり得ないからである。
【００２８】
第３の種類のマルチプレクサは、結果の内側ビットまたは最下位ビットのいずれかとなることのできる出力ラインに接続されたものである。このようなマルチプレクサを符号124で示す。これを最下位ビットマルチプレクサと称することにする。平均演算の結果を切り捨てることになる場合、即ち、結果の決定時にシフトアウトされたビットを無視することになる場合には、最下位ビットマルチプレクサは、内側ビットマルチプレクサと同じである。
【００２９】
切り捨ては、右にシフトすることにより整数除算の結果を丸める方法として使用することができるが、他の形の丸めでは防止可能な望ましくない問題を発生させることがある。画像中の隣接画素の平均を求めることによりその画像のサイズを縮小する場合を考察する。即ち、４画素からなる各グループを１画素に置き換え、その１画素が、置換される４画素の平均と等しい値を有している、といった場合である。画像はＩ×Ｉ画素アレイにより表される。画素の削減は、アレイ中の奇数行および偶数行の平均を求めてＩ×Ｉ／２画素アレイを生成することにより達成することができる。次いで、その中間アレイの奇数列および偶数列の平均を求めて最終的な(Ｉ／２)×(Ｉ／２)アレイを生成する。様々な平均演算が常に切り捨てられる場合には、最終的な画像は元の画像とは異なる統計的特性を有するものとなる。例えば、縮小された画像は、元のアレイよりも低い平均光強度を有するものとなる。この種のアーチファクトを避けることが重要であることが多い。本発明は、この種の偏った(biased)丸めを避けるための手段を提供する。
【００３０】
本発明の好適実施例では、奇数丸め論理を使用してこの偏りを防止している。奇数丸めシステムでは、右シフトにより丸め誤差が発生した場合に、最も近い奇数の整数に結果が丸められる。丸めを行う前の答えが正確である場合には変更は加えられない。丸め誤差は、結果から１がシフトオフされる場合に必ず発生する。これは、シフトされる前の最下位ビットが「１」である場合に発生する。この場合、結果の最下位ビットは「１」にセットされる。また、シフトアウトされるビットが「０」である場合には、そのシフトを行った後でも結果は正確であり、結果の最下位ビットは変更されない。本発明が奇数丸めを使用するのは、単一のＯＲゲート131をマルチプレクサに追加することで奇数丸めシステムを実施できるからである。したがって、偏らない丸めが使用される最下位ビットマルチプレクサでは、Ａが真であり、当該マルチプレクサが結果の最下位ビットであることをマスクビットが示す場合に、前記マルチプレクサが、Ｚiに接続するための信号（Ｓi+1 ＯＲ Ｓi）を選択する。また、Ａが偽である場合にはＳiがＺiに接続される。また、Ａが真であり、出力ラインが結果の内側ビットに接続されていることをマスクビットが示す場合には、マルチプレクサはＺiをＳi+1に接続する。
【００３１】
Ｓの値が一様に分散されている場合にはこの形態の丸めで得られる平均誤差が０であることを示すことができる。偶数丸め(round even)システムもまた丸めの偏りを防止することが可能であるということに留意されたい。偶数丸めシステムでは、丸め誤差が発生し、丸めを行う前の結果が奇数である場合に、その結果が最も近い偶数整数に丸められる。しかし、偶数丸め機構を実施するのに必要とされるハードウェアの方がはるかに複雑なものである。
【００３２】
上述のマルチプレクサは、限られた数の考え得る部分オペランド境界しか実施されないことを仮定したものである。しかし、加算器が任意の境界を有する場合には、０番目の段および(N-1)番目の段を除いた各出力ラインに取り付けられたマルチプレクサは、３つの考え得るマルチプレクサ機能のうちのいずれをも機能することができなければならない。これら機能を提供するマルチプレクサ構成200のブロック図を図４に示す。マルチプレクサ構成200は、４→１マルチプレクサ201から構成される。以下の説明では、マルチプレクサ200が出力ラインＺqに接続されているものと仮定する。マルチプレクサ201は、平均信号およびマスクビットの状態に応じてＳq+1、Ｓq、Ｃq、または（Ｓq+1 ＯＲ Ｓq）をＺqに接続する。マルチプレクサ201は、最下位ビットマルチプレクサまたは最上位ビットマルチプレクサとして両方とも適切に機能しなければならないので、ＭqおよびＭq+1の状態を共に判定することができなければならない。
【００３３】
本発明は、従来の加算器に比較してわずかしか複雑でない加算器での並列加算または平均を提供することに加え、計算の始めにデータがワードとしてパックされる多種類の計算の全体的な計算効率も向上させるものである。ここで、32ビットワードサイズを有するコンピュータ上で上述の画像サイズの縮小を行う際の問題について考察する。各画素が１バイトの整数で表される場合、記憶空間を節約するために画像データは通常はワードとしてパックされる。したがって、画像中の各水平ラインはＩ／４個の32ビットワードで表される。奇数ラインの画素をその奇数ラインに続く偶数ラインの画素に加算するために、その奇数ラインの４画素を含む１ワードをＸレジスタに入力し、そのワードに対応する偶数ラインからのワードをＹレジスタに入力することができる。次いで、結果的に得られる画像ラインのパックされた１ワードとしてＺレジスタの内容を直接メモリに格納することができる。この演算は、個々のバイトをアンパックして結果を再パックする必要なしに実行することができる。したがって、本発明は、単一の加算命令で４画素を処理することを可能にし、従来の加算器で必要とされるパック命令およびアンパック命令を不要とするものである。最後に、本発明は、２つの画素の平均を自動的に生成し、これにより、各加算後の１回のシフト演算を不要にする。
【００３４】
更に、並列サブワード加算命令は、従来の全ワード加算命令以下の複雑さを有するものである。従来の全ワード加算では、オペランドを有する２つのレジスタ、および結果を保持するための第３のレジスタを、プログラマが指定する。本発明も同様に、３つのレジスタを指定するだけでよい。部分オペランドフィールドにおいて考え得る加算器の構成が少数しかない場合には、それら構成を加算命令に含めることができ、この場合には、対応するマスクビットを命令デコード回路が生成することができる。したがって、加算器のセットアップを行うための命令が別に必要となることはない。
【００３５】
上記説明は、入力ワードおよび出力ワードがプロセッサのレジスタ中に格納されていると仮定したものである。出力値および／または入力値が加算命令または平均命令で指定された場所に送られ、あるいはその場所から受容される本発明の実施例は、当業者には明らかなものであろう。例えば、加算命令は、レジスタの最下位ビットにそれぞれロードされる和を受容するための複数のレジスタを指定することができる。同様に、レジスタ以外の場所、例えばメモリやその他の機能ユニットに直接結果を送ることができる。更に、他の機能ユニットまたはメモリから各オペランドを送り出すことが可能であることも明らかであろう。
【００３６】
上記実施例は、並列部分サブワード平均に関して説明したものであるが、本発明を使用してワードＸおよびワードＹの内容全体に対して平均命令を実行することも可能であることは当業者には明らかであろう。そのような実施例は、１マシンサイクル中に２つの演算、即ち加算と２による除算とを行うことができる、という利益を提供するものである。
【００３７】
本発明の上記実施例は、桁上げ伝搬型の加算器に関して説明したものである。本発明の好適実施例では、キャリールックアヘッドアーキテクチャが使用される。これは、遅延が一層少ないからである。キャリールックアヘッド加算器では、桁上げ生成回路が、加算器の各ビットに対応して伝搬信号および生成信号を１つずつ生成する。これらの信号を上述の桁上げビットと類似の態様で使用して、加算器を並列サブワード加算器に分割することが可能となる。段ｋがサブワード結果の最上位ビットについて演算を行うように加算器を分割する場合を考察する。図２に示したブロック化回路33等のブロック化回路を桁上げ生成論理回路中に挿入して、伝搬ビットおよび生成ビットが実行中の演算の種類に応じて、即ち加算または減算に応じて強制的に適当な値になるようにすることができる。段ｋで、分割されていないワードについて加算器を使用している場合には、そのブロック化回路は、その段ｋに対応する伝搬ビットおよび生成ビットの値の修正を行うことはない。
【００３８】
本発明の上記実施例は、本発明により実行される様々な演算をトリガするための手段としての命令に関して説明したものであるが、本発明の演算は、予め格納されているコンピュータプログラムの命令により生成されたのではない電気信号によってトリガ可能なものである、ということが当業者には明らかであろう。したがって、特許請求の範囲で使用する「命令」という用語は、他の形態の信号によりトリガされる演算もまた含むものである。更に、コンピュータの一部ではない回路で本発明を使用することも可能であることが当業者には明らかであろう。
【００３９】
本発明の上記実施例は、符号なし整数の平均を求めることに関して説明したものであるが、本発明の教示は符号付き整数にも適用可能であることが当業者には明らかであろう。この場合には、和の最上位ビットから結果の最上位ビットへと桁上げ出力ビットを移動させる代わりに、結果の最上位ビットが次のようにして求められる。即ち、２つのオペランドが同じ符号のものである場合には、上記と同様に結果の最上位ビットが桁上げ出力ビットとなる。また、２つのオペランドが異なる符号のものである場合には、結果の最上位ビットは、右シフトを行う前の和の最上位ビットとなる。即ち、結果の最上位ビットは、(Ｘp ＡＮＤ Ｙp) ＯＲ (Ｘp ＯＲ Ｙp) ＡＮＤ バーＣp-1となる。キャリールックアヘッド加算器の場合には、この式は、Ｇp ＯＲ Ｐp ＡＮＤ バーＣp-1となる。ここで、Ｇp,Ｐpは、最上位ビットに関する生成ビットおよび伝搬ビットである。
【００４０】
当業者であれば、上記説明および図面から本発明の様々な修正例が明らかとなろう。したがって、本発明は特許請求の範囲によってのみ制限されるものである。
【００４１】
以下においては、本発明の種々の構成要件の組み合わせからなる例示的な実施態様を示す。
【００４２】
１．ビットＸiを有するワードＸとビットＹiを有するワードＹとの内容について演算を行ってビットＺiを有する結果ワードを生成する装置であって、ｉ＝0〜N-1であり、Ｚ0が前記サブワードの内の１つの最下位ビットであり、ＺN-1が前記サブワードの内の１つの最上位ビットである、前記装置において、この装置が、前記ワードＸと前記ワードＹと前記結果ワードとを複数のサブワードへと区画化する手段であって、前記ワードＸの各サブワードに対応して前記ワードＹおよび前記結果ワードのサブワードが１つずつ存在する、前記区画化手段と、
第１の命令に応じて前記Ｘの各サブワードとそれに対応する前記Ｙの各サブワードとの和を生成する手段であって、その結果が、前記結果ワードの対応するサブワードを決定する、前記和生成手段と
を備えていることを特徴とする、前記装置。
２．第２の命令に応じて前記ワードＸ中の各サブワードとそれに対応する前記ワードＹ中のサブワードとの差を生成する手段であって、その結果が、前記結果ワードの対応するサブワードを決定する、前記手段を更に備えている、前項１記載の装置。
【００４３】
３．第３の命令に応じて前記ワードＸ中の各サブワードとそれに対応する前記ワードＹ中のサブワードとの和を２で除算した値を生成する手段であって、その結果が、前記結果ワードの対応するサブワードを決定する、前記手段を更に備えている、前項１記載の装置。
【００４４】
４．前記の２での除算の結果として丸め誤差が生じた場合に、前記の各結果が１つ下の奇数整数に丸められる、前項３記載の装置。
【００４５】
５．第４の命令に応じて前記ワードＸ中の各サブワードとそれに対応する前記ワードＹ中のサブワードとの差を２で除算した値を生成する手段であって、その結果が、前記結果ワードの対応するサブワードを決定する、前記手段を更に備えている、前項２記載の装置。
【００４６】
６．前記装置が、前記ワードＸからの１つ以上のビットと前記ワードＹから得た対応するビットとについて演算を行う演算手段と、前記ワードＸの各ビットに対応して生成ビットおよび伝搬ビットを１つずつ生成する手段とを備え、前記区画化手段が、前記生成ビットおよび前記伝搬ビットを強制的に、前記ワードＸの前記ビットがサブワードの最上位ビットである場合に実行される演算により決定される値にする手段を備えている、前項１記載の装置。
【００４７】
７．前記装置が、直列に接続された複数の加算段を備えており、その各加算段が、前記ワードＸからの１つ以上のビットとそれに対応する前記ワードＹから得たビットとについて演算を行う手段と、前記加算段からの桁上げビットを前記直列接続中の次の加算段へ伝搬させる手段とを備えており、前記区画化手段が、前記桁上げビットを強制的に、前記加算段が前記ワードＸ中の異なるサブワードのビットについて演算を行う場合に実行される演算により決定される値にする手段を備えている、前項１記載の装置。
【００４８】
８．前記加算段が、Ｘiについての演算から導出されるＮ個の結果ビットＳi(i＝0〜N-1)を生成し、前記装置が、前記結果ビットの内の１つを示す信号を各々が生成するＮ個の多重化手段を更に備え、その多重化手段は、前記の各結果ビットＺp(p＝0〜N-1)毎に１つずつあり、Ｚpに対応する前記多重化手段が、前記第１の命令に応じてＳpをＺpに接続する、前項７記載の装置。
【００４９】
９．Ｚpに対応する前記多重化手段が、Ｚpが１つの前記サブワードの内側にある場合に前記第３の命令に応じてＺpをＳp+1に接続し、Ｚpが前記結果サブワードの内の１つの最上位ビットである場合にはＺpをＣpに接続し、そのＣpは、Ｚpを含む結果サブワードに対応する前記Ｘのサブワードの最上位ビットについて演算を行う前記加算段により生成される前記桁上げビットである、前項８記載の装置。
【００５０】
１０．Ｚpに対応する前記多重化手段が、Ｚpが前記結果サブワードの内の１つの最下位ビットである場合にＺpを(Ｓp+1 ＯＲ Ｓp)へ接続する手段を更に備えている、前項９記載の装置。
【００５１】
１１．前記演算手段が、Ｘiについての演算から導出されるＮ個の結果ビットＳi(i＝0〜N-1)を生成し、前記装置が、前記結果ビットの内の１つを示す信号を生成するＮ個の多重化手段を更に備えており、前記多重化手段が前記の各結果ビットＺp(ｐ＝0〜N-1)毎に１つずつあり、Ｚpに対応する前記多重化手段が前記第１の命令に応じてＳpをＺpに接続する、前項６記載の装置。
【００５２】
１２．サブワードの最上位ビットとなることができる各ビットＸpに対応する桁上げビットＣpを生成する手段を更に備え、Ｚpに対応する前記多重化手段が、Ｚpが前記サブワードの内の１つの内側にある場合に前記第３の命令に応じてＺpをＳp+1に接続し、Ｚpが前記結果サブワードの内の１つの最上位ビットである場合にＺpをＣpに接続し、Ｃpが、Ｚpを含む結果サブワードに対応するＸのサブワードの最上位ビットについて演算を行う前記加算段により生成される桁上げビットである、前項１１記載の装置。
【００５３】
１３．Ｚpに対応する前記多重化手段が、Ｚpが前記結果サブワードの内の１つの最下位ビットである場合にＺpを(Ｓp+1 ＯＲ Ｓp)に接続する手段を更に備えている、前項１２記載の装置。
【００５４】
１４．ビットＸiを有するワードＸと、ビットＹiを有するワードＹとの内容について演算を行ってビットＺiを有する結果ワードを生成する装置であって、ｉ＝0〜N-1であり、Ｚ0が最下位ビットであり、ＺN-1が最上位ビットである、前記装置において、平均命令に応じて前記ワードＸおよび前記ワードＹの和を生成する手段と、その和をシフトさせて前記ワードＺを生成する手段とを備えることを特徴とする、前記装置。
【００５５】
１５．前記シフトの結果として丸め誤差が生じた場合に、前記ワードＺが１つ下の奇数整数へと丸められる、前項１４記載の装置。
【００５６】
１６．前記装置が、直列に接続された複数の加算段を備えており、その各加算段が、前記ワードＸからの１つ以上のビットとそれに対応する前記ワードＹから得た対応するビットとについて演算を行う手段を備えており、それら加算段がＮ個の結果ビットＳi(ｉ＝0〜N-1)を生成し、ＳiがＸiおよび桁上げ出力ビットＣN-1についての演算から導出され、および、前記装置がＮ個の多重化手段を更に備えており、その各多重化手段が、前記結果ビットの内の１つを示す信号を生成し、前記の各結果ビットＺp(ｐ＝0〜N-1)毎に１つずつ存在し、そのＺpに対応する前記多重化手段が前記平均命令に応じてＳpをＺpに接続する、前項１４記載の装置。
【００５７】
１７．差命令に応じて前記ワードＸと前記ワードＹとの差を２で除算した値を生成する手段を更に備えており、その生成結果が前記結果ワードを決定する、前項１４記載の装置。
【００５８】
１８．Ｚpに対応する前記多重化手段が、p＝0〜N-2である場合に前記平均命令に応じてＺpをＳp+1へ接続し、p＝N-1である場合にはＺpをＣN-1へ接続する、前項１６記載の装置。
【００５９】
１９．Ｚpに対応する前記多重化手段が、p＝0である場合にＺpを(Ｓp+1 ＯＲ Ｓp)へ接続する手段を更に備えている、前項１８記載の装置。
【００６０】
２０．サブワードの最上位ビットとなることができる各ビットＸpに対応する桁上げビットＣpを生成する手段を更に備え、Ｚpに対応する前記多重化手段が、Ｚpが前記サブワードの内の１つの内側にある場合に前記第３の命令に応じてＺpをＳp+1へ接続し、Ｚpが前記結果サブワードの内の１つの最上位ビットである場合にはＺpをＳpに接続する、前項１１記載の装置。
【００６１】
【発明の効果】
本発明は上述のように構成したので、加算器の幅よりも小さなワードを伴う多数の加算を行う際に高効率で動作し、また単一のマシンサイクルで２つの数の平均を生成することのできる加算器を提供することができる。
【図面の簡単な説明】
【図１】本発明による加算器を示すブロック図である。
【図２】加算のみを実行する本発明による加算器の一部を示すブロック図である。
【図３】本発明による加算器の一部を示すブロック図である。
【図４】本発明の実施例を構築するのに利用可能なマルチプレクサ構成を示すブロック図である。
【符号の説明】
10             加算器
12,14          Ｎビットオペランド
16             Ｎビット出力ワード
Ｘi,Ｙi        ビット
Ｘ0, Ｙ0       最下位ビット
ＸN-1,ＹN-1    最上位ビット
17,18,19,20    部分オペランド
【図１】
0003729881.tif 000002
【図２】
0003729881.tif 000003
【図３】
0003729881.tif 000004
【図４】
0003729881.tif 000005