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




【発明の名称】 Ｍビット競合遅延加算器及び動作方法
【発明者】 【氏名】ウィリアム イー． バッラチーノ
【要約】 【課題】２つの引数を迅速に加算することが可能な加算器回路を提供する。

【解決手段】本発明によれば、第一Ｍビット引数、第二Ｍビット引数、キャリィイン（ＣＩ）ビットを受取ることが可能なＭビット加算器が提供される。該Ｍビット加算器はＲ個の行に配列されているＭ個の加算器セルを有しており、加算器セルからなる行のうちの第一の行における最小桁加算器セルは第一Ｍビット引数からの第一データビットＡX及び第二Ｍビット引数からの第一データビットＢXを受取り、且つ第一条件付きキャリィアウトビットＣX（１）及び第二条件付きキャリィアウトビットＣX（０）を発生する。ＣX（１）ビットは、第一行に先行する加算器セルからなる第二行からの行キャリィアウトビットが１であると仮定して計算され、且つＣX（０）ビットは、第二行からの行キャリィアウトビットが０であると仮定して計算される。
【特許請求の範囲】
【請求項１】 第一Ｍビット引数と、第二Ｍビット引数と、キャリィイン（ＣＩ）ビットとを受取ることが可能なＭビット加算器において、Ｍ個の加算器セルがＲ個の行に配列されており、前記加算器セルの行のうちの第一行内の最小桁加算器セルが前記第一Ｍビット引数から第一データビットＡXと前記第二Ｍビット引数から第一データビットＢXとを受取り且つ第一条件付きキャリィアウトビットＣX（１）及び第二条件付きキャリィアウトビットＣX（０）を発生し、前記ＣX（１）ビットは前記第一行に先行する加算器セルの第二行からの行キャリィアウトビットが１であることを仮定して計算され且つ前記ＣX（０）ビットが前記第二行からの前記行キャリィアウトビットが０であることを仮定して計算される、ことを特徴とするＭビット加算器。
【請求項２】 請求項１において、前記最小桁加算器セルが第一条件付き和ビットＳX（１）及び第二条件付き和ビットＳX（０）を発生することを特徴とするＭビット加算器。
【請求項３】 請求項２において、前記ＳX（１）ビットが前記第二行からの行キャリィアウトビットが１であることを仮定して計算され且つ前記ＳX（０）ビットが前記第二行からの前記行キャリィアウトビットが０であることを仮定して計算されることを特徴とするＭビット加算器。
【請求項４】 請求項３において、前記行キャリィアウトビットが前記最小桁加算器セルによって出力されるべき前記ＳX（１）ビット及び前記ＳX（０）ビットのうちの１つを選択することを特徴とするＭビット加算器。
【請求項５】 請求項４において、前記加算器セルの第一行が、更に、前記最小桁加算器セルへ接続されている第二加算器セルを有しており、前記第二加算器セルが前記第一Ｍビット引数から第二データビットＡX+1及び前記第二Ｍビット引数から第二データビットＢX+1を受取り且つ前記最小桁加算器セルから前記ＣX（１）ビット及び前記ＣX（０）ビットを受取ることを特徴とするＭビット加算器。
【請求項６】 請求項５において、前記第二加算器セルが第一条件付きキャリィアウトビットＣX+1（１）を発生し、前記ＣX+1（１）ビットは前記ＡX+1データビット、前記ＤX+1データビット、及び前記最小桁加算器セルからの前記ＣX（１）ビットから発生されることを特徴とするＭビット加算器。
【請求項７】 請求項６において、前記第二加算器セルが第二条件付きキャリィアウトビットＣX+1（０）を発生し、前記ＣX+1（０）ビットが前記ＡX+1データビット、前記ＤX+1データビット、及び前記最小桁加算器セルからの前記ＣX（０）ビットから発生されることを特徴とするＭビット加算器。
【請求項８】 請求項７において、前記第二加算器セルが第一条件付き和ビットＳX+1（１）を発生し、前記ＳX+1（１）ビットは前記ＡX+1データビット、前記ＢX+1データビット、及び前記最小桁加算器セルからの前記ＣX（１）ビットから発生されることを特徴とするＭビット加算器。
【請求項９】 請求項８において、前記第二加算器セルが第二条件付き和ビットＳX+1（０）を発生し、前記ＳX+1（０）ビットは前記ＡX+1データビット、前記ＢX+1データビット、及び前記最小桁加算器セルからの前記ＣX（０）ビットから発生されることを特徴とするＭビット加算器。
【請求項１０】 請求項９において、前記行キャリィアウトビットが前記第二加算器セルによって出力されるべき前記ＳX+1（１）ビット及び前記ＳX+1（０）ビットのうちの１つを選択することを特徴とするＭビット加算器。
【請求項１１】 請求項１において、前記加算器セルの第一行がＮ個の加算器セルを包含しており且つ前記第一行に先行する前記加算器セルの第二行がＮ個未満の加算器セルを包含していることを特徴とするＭビット加算器。
【請求項１２】 データプロセッサにおいて、Ｎ個の処理段を具備している命令実行パイプラインが設けられており、前記Ｎ個の処理段の各々は前記命令実行パイプラインによって実行中の未決の命令と関連している複数個の実行ステップのうちの１つを実行することが可能であり、前記Ｎ個の処理段のうちの少なくとも１つが第一Ｍビット引数と、第二Ｍビット引数と、キャリィイン（ＣＩ）ビットとを受取ることが可能なＭビット加算器を有しており、前記Ｍビット加算器がＲ個の行に配列されているＭ個の加算器セルを有しており、前記加算器セルの行のうちの第一行における最小桁加算器セルが前記第一Ｍビット引数からの第一データビットＡX及び前記第二Ｍビット引数からの第一データビットＢXを受取り且つ第一条件付きキャリィアウトビットＣX（１）及び第二条件付きキャリィアウトビットＣX（０）を発生し、前記ＣX（１）ビットは前記第一行に先行する加算器セルの第二行からの行キャリィアウトビットが１であることを仮定して計算され且つ前記ＣX（０）ビットは前記第二行からの前記行キャリィアウトビットが０であることを仮定して計算される、ことを特徴とするデータプロセッサ。
【請求項１３】 請求項１２において、前記最小桁加算器セルが第一条件付き和ビットＳX（１）及び第二条件付き和ビットＳX（０）を発生することを特徴とするデータプロセッサ。
【請求項１４】 請求項１３において、前記ＳX（１）ビットが前記第二行からの前記行キャリィアウトビットが１であることを仮定して計算され且つ前記ＳX（０）ビットが前記第二行からの前記行キャリィアウトビットが０であることを仮定して計算されることを特徴とするデータプロセッサ。
【請求項１５】 請求項１４において、前記行キャリィアウトビットが前記最小桁加算器セルによって出力されるべき前記ＳX（１）ビット及び前記ＳX（０）ビットのうちの１つを選択することを特徴とするデータプロセッサ。
【請求項１６】 請求項１５において、前記加算器セルの第一行が、更に、前記最小桁加算器セルへ結合されている第二加算器セルを有しており、前記第二加算器セルが前記第一Ｍビット引数からの第二データビットＡX+1及び前記第二Ｍビット引数からの第二データビットＢX+1を受取り且つ前記最小桁加算器セルから前記ＣX（１）ビット及び前記ＣX（０）ビットを受取ることを特徴とするデータプロセッサ。
【請求項１７】 請求項１６において、前記第二加算器セルが第一条件付きキャリィアウトビットＣX+1（１）を受取り、前記ＣX+1（１）ビットは前記ＡX+1データビット、前記ＢX+1データビット、及び前記最小桁加算器セルからの前記ＣX（１）から発生されることを特徴とするデータプロセッサ。
【請求項１８】 請求項１７において、前記第二加算器セルが第二条件付きキャリィアウトビットＣX+1（０）を発生し、前記ＣX+1（０）ビットは前記ＡX+1データビット、前記ＢX+1データビット、及び前記最小桁加算器セルからの前記ＣX（０）ビットから発生されることを特徴とするデータプロセッサ。
【請求項１９】 請求項１８において、前記第二加算器セルが第一条件付き和ビットＳX+1（１）を発生し、前記ＳX+1（１）ビットは前記ＡX+1データビット、前記ＢX+1データビット、及び前記最小桁加算器セルからの前記ＣX（１）ビットから発生されることを特徴とするデータプロセッサ。
【請求項２０】 請求項１９において、前記第二加算器セルは第二条件付き和ビットＳX+1（０）を発生し、前記ＳX+1（０）ビットは前記ＡX+1データビット、前記ＢX+1データビット、及び前記最小桁加算器セルからの前記ＣX（０）ビットから発生されることを特徴とするデータプロセッサ。
【請求項２１】 請求項２０において、前記行キャリィアウトビットが前記第二加算器セルによって出力されるべき前記ＳX+1（１）ビット及び前記ＳX+1（０）ビットのうちの１つを選択することを特徴とするデータプロセッサ。
【請求項２２】 請求項１２において、前記加算器セルの第一行がＮ個の加算器セルを包含しており且つ前記第一行に先行する前記加算器セルの第二行がＮ個未満の加算器セルを包含していることを特徴とするデータプロセッサ。
【請求項２３】 Ｒ個の行に配列されているＭ個の加算器セルを具備しているＭビット加算器において第一Ｍビット引数と第二Ｍビット引数とを加算する方法において、前記加算器セルの行のうちの第一行における最小桁加算器セルにおいて前記第一Ｍビット引数から第一データビットＡX及び前記第二Ｍビット引数から第一データビットＢXを受取り、前記第一行に先行する加算器セルの第二行からの行キャリィアウトビットが１であると仮定して前記最小桁加算器セルにおいて第一条件付きキャリィアウトビットＣX（１）を計算し、前記第二行からの前記行キャリィアウトビットが０であると仮定して前記最小桁加算器セルにおいて第二条件付きキャリィアウトビットＣX（０）を計算し、前記第二行からの行キャリィアウトビットが１であると仮定して前記最小桁加算器セルにおいて第一条件付き和ビットＳX（１）を計算し、前記第二行からの行キャリィアウトビットが０であると仮定して前記最小桁加算器セルにおいて第二条件付き和ビットＳX（０）を計算し、前記ＣX（１）ビット及び前記ＣX（０）ビットを前記加算器セルの第一行における第二加算器セルへ伝播させ、前記第二行からの行キャリィアウトビットの値に従って前記最小桁加算器セルから出力されるべき前記ＳX（１）ビット及び前記ＳX（０）ビットのうちの１つを選択する、ことを特徴とする方法。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、大略、データプロセッサに関するものであって、更に詳細には、データプロセッサにおいて使用するピラミッド加算器としても知られているＭビット競合遅延加算器に関するものである。
【０００２】
【従来の技術】高性能コンピュータ及び通信装置に対する要求は、技術水準のデジタル信号プロセッサ（ＤＳＰ）及び例えばｘ８６をベースとしたマイクロプロセッサ等の汎用マイクロプロセッサが最小の時間の量で命令を実行することを必要とする。命令実行時間を減少させ、それによりプロセッサの処理能力を増加させるために多数の異なるアプローチが取られている。プロセッサの処理能力を増加させる１つの方法は、パイプラインアーキテクチャを使用することであり、その場合には、プロセッサがパイプラインを形成する別個の処理段に分割される。命令が基本的なステップに分解され、それらは組立ラインの態様で異なる段において実行される。
【０００３】スーパーパイプラインはパイプラインにおいての複数個の命令の同時的処理を意味している。例えば、プロセッサが５個の段において各命令を実行し且つ各段がその機能を実施するために単一のクロックサイクルを必要とする場合には、パイプラインにおいて５個の別個の命令を同時的に処理することが可能であり、各クロックサイクル期間中に１個の命令の処理が完了される。従って、Ｎ段パイプラインアーキテクチャの命令処理能力は、理論的には、Ｎクロックサイクル毎に１個の命令を完了するに過ぎない非パイプライン型アーキテクチャの処理能力よりもＮ倍大きいものである。然しながら、パイプラインアーキテクチャ及びスーパーパイプライン処理によって与えられる速度の改良は、究極的には、パイプラインにおける個々の段が実行する速度によって制限される。従って、命令の各部分を実行するのに必要な時間を最小とさせることが重要である。
【０００４】数学的演算は、しばしば、値を計算する場合、特に多数のビットを有している２個の引数の加算において実質的な時間遅延を発生する。例えば、２個の３２ビット数又は２個の６４ビット数の加算は、しばしば、実質的な時間的ペナルティを発生する。この遅延は、通常、和の長さにわたってのキャリィビットの伝播遅延に関連している。例えば、典型的な３２ビット加算器はその入力として第一の３２ビット引数と、第二の３２ビット引数と、前の段からのキャリィインビットとを受取る場合がある。該３２ビット加算器は３２個のキャリィ和セルを有している場合があり、その場合には各セルは各引数から１個のビット及びより低い次数のセルからのキャリィビットを受取り且つ和ビット及びキャリィビットを発生する。例えば、５番目のキャリィ和セルは第一の３２ビット引数からの５番目のビット、第二の３２ビット引数からの５番目のビット、４番目のセルからのキャリィビットを受取る。然しながら、該３２ビット加算器の出力は、該キャリィビットが３２個のセル全てを介してリップル即ち通り抜けるまで正しいものとはならない。このことは、著しい時間遅延を発生させる。
【０００５】従って、命令処理能力を最大とさせる改良したデータプロセッサに対する必要性が存在している。特に、多数のバイトを有する２個の引数を迅速に加算することが可能な改良した加算器回路に対する必要性が存在している。更に詳細には、２個の大きな引数を加算することによって発生されるキャリィリップル遅延を最小とさせる改良した加算器回路が必要とされている。
【０００６】
【発明が解決しようとする課題】本発明は、以上の点に鑑みなされたものであって、上述した如き従来技術の欠点を解消し、処理能力を改善したデータプロセッサを提供することを目的とする。本発明の別の目的とするところは、多数のバイトを有する２個の引数を迅速に加算することが可能な加算器を提供することである。本発明の更に別の目的とすることは、２個の引数を加算することによって発生するキャリィリップル遅延を最小とさせる改良した加算器を提供することである。
【０００７】
【課題を解決するための手段】上述した従来技術の問題を解決するために、本発明の主要な目的とするところは、第一のＭビット引数と、第二のＭビット引数と、キャリィイン（ＣＩ）ビットとを受取ることが可能なＭビット加算器を提供することである。本発明の好適な実施形態によれば、該Ｍビット加算器はＲ個の行に配列されたＭ個の加算器セルを有しており、該加算器セルの行のうちの第一の行における最小桁加算器セルが第一Ｍビット引数からの第一データビットＡX及び第二のＭビット引数からの第一データビットＢXを受取り且つ第一条件付けキャリィアウトビットＣX（１）及び第二条件付きキャリィアウトビットＣX（０）を発生し、該ＣX（１）ビットは該第一行に先行する加算器セルからなる第二行からの行キャリィアウトビットが１であることを仮定して計算され且つ該ＣX（０）ビットは該第二行からの行キャリィアウトビットが０であることを仮定して計算される。
【０００８】本発明の１実施例によれば、該最小桁加算器セルは第一条件付き和ビットＳX（１）及び第二条件付き和ビットＳX（０）を発生する。
【０００９】本発明の別の実施例によれば、該ＳX（１）ビットは該第二行からの行キャリィアウトビットが１であると仮定して計算され、且つ該ＳX（０）ビットは該第二行からの行キャリィアウトビットが０である仮定して計算される。
【００１０】本発明の更に別の実施例によれば、該行キャリィアウトビットは該最小桁加算器セルによって出力されるべき該ＳX（１）ビット及び該ＳX（０）ビットのうちの１つを選択する。
【００１１】本発明の更に別の実施例によれば、該加算器セルからなる第一行は、更に、該最小桁加算器セルへ結合されている第二加算器セルを有しており、該第二加算器セルは、該第一のＭビット引数からの第二データビットＡX+1及び該第二のＭビット引数からの第二データビットＢX+1を受取り且つ該最小桁加算器セルから該ＣX（１）ビット及び該ＣX（０）ビットを受取る。
【００１２】本発明の更なる実施例によれば、該第二加算器セルは第一条件付きキャリィアウトビットＣX+1（１）を発生し、該ＣX+1（１）ビットは該ＡX+1データビット、該ＢX+1データビット、及び該最小桁加算器セルからの該ＣX+1（１）ビットから発生される。
【００１３】本発明の更に別の実施例によれば、該第二加算器セルは第二条件付きキャリィアウトビットＣX+1（０）を発生し、該ＣX+1（０）ビットは該ＡX+1データビット、該ＢX+1データビット、及び該最小桁加算器セルからの該ＣX+1（０）ビットから発生される。
【００１４】本発明の更に別の実施例によれば、該第二加算器セルは第一条件付き和ビットＳX+1（１）を発生し、該ＳX+1（１）ビットは該ＡX+1データビット、該ＢX+1データビット、及び該最小桁加算器セルからの該ＣX（１）ビットから発生される。
【００１５】本発明の１実施例においては、該第二加算器セルは第二条件付き和ビットＳX+1（０）を発生し、該ＳX+1（０）ビットは該ＡX+1データビット、該ＢX+1データビット、及び該最小桁加算器セルからの該ＣX（０）ビットから発生される。
【００１６】本発明の別の実施例においては、該行キャリィアウトビットは該第二加算器セルによって出力されるべき該ＳX+1（１）ビット及び該ＳX+1（０）ビットのうちの１つを選択する。
【００１７】本発明の更に別の実施例においては、該加算器セルからなる第一行がＮ個の加算器セルを包含しており、且つ該第一行に先行する加算器セルからなる該第二行はＮ個未満の加算器セルを包含している。
【００１８】前述した説明は、当業者が以下に続く本発明の詳細な説明をより良く理解することが可能であるように、本発明の特徴及び技術的利点について広義に概観したものである。本発明の付加的な特徴及び利点については以下に説明するが、それらも本発明の要旨を構成するものである。当業者は、本発明と同一の目的を達成するために、修正を行うか又はその他の構成を設計する基礎として本明細書に記載した概念及び特定の実施例を容易に使用することが可能であることは明らかである。当業者は、又、このような均等な構成は本発明の技術的範囲を逸脱するものでないことを理解することが可能である。
【００１９】本発明の詳細な説明を行う前に、本明細書において使用する用語についての定義及び説明を行うことが有益的であると考える。例えば、「有する」及び「含む」及びそれらに類似した意味の用語は、限定なしで包含していることを意味しており、「又は」の用語は及び／又はの意味を包含しており、「関連する」という用語は、含んでいること、含まれていること、相互接続していること、包含していること、包含されていること、接続していること、結合していること、通信可能であること、共同すること、インターリーブすること、並置していること、近接していること、結ばれていること、持っていること、特性を持っていること、等を意味する場合があり、且つ「制御器」という用語は少なくとも１つの動作を制御する任意の装置、システム又はその一部であることを意味し、且つこのような装置はハードウエア、ファームウエア、又はソフトウエア、又はそれらの少なくとも２つの何等かの組合わせとすることが可能である。更に注意すべきことであるが、いずれか特定の制御器に関連する機能は集中化させるか、又は局所的又は遠隔的に分散させたものとすることが可能である。
【００２０】
【発明の実施の形態】図１は例示的な処理システム、即ちパソコン（ＰＣ）１００を例示しており、それは本発明の原理に基づくＭビット競合遅延加算器を有している。パソコン１００は着脱自在な（即ち、フロッピィ）ディスクドライブ（ＦＤＤ）１０２、ハードディスクドライブ（ＨＤＤ）１０３、モニタ１０４、キーボード１０５、プロセッサ（ＣＰＵ）１０６、メインメモリ１０７、マウス１０８等のポインティングデバイスを有している。モニタ１０４、キーボード１０５、マウス１０８はその他の入力／出力（Ｉ／Ｏ）装置と置換させるか又は結合させることが可能である。着脱自在なディスクドライブ１０２は着脱自在なフロッピィディスケットを読取且つ書込を行うことが行うことが可能である。ハードディスクドライブ１０５はアプリケーションプログラム及びデータの格納及び検索に対して高速なアクセスを与える。
【００２１】キーボード１０５及びマウス１０８は入力／出力（Ｉ／Ｏ）インターフェース（ＩＦ）１１０を介してＰＣ１００へ結合されている。モニタ１０４はビデオ／オーディオインターフェース（ＩＦ）１１２を介してＰＣ１００へ結合されている。フロッピィディスクドライブ１０２、ハードディスクドライブ１０３、プロセッサ１０６、メインメモリ１０７、Ｉ／Ｏインターフェース１１０、ビデオ／オーディオインターフェース１１２を包含するＰＣ１００の内部コンポーネントは通信バス１１５へ結合されており且つそれを介して通信を行う。
【００２２】本発明の例示的な実施例においては、メインメモリ１０７は例えばダイナミックランダムアクセスメモリ（ＲＡＭ）等の揮発性の記憶装置を有している。プロセッサ１０６は、レベル１（Ｌ１）キャッシュ及びレベル２（Ｌ２）キャッシュを包含するオンボードの２レベルキャッシュシステムを有することが可能である。この２レベルキャッシュは、小型の高速のキャッシュ（Ｌ１キャッシュ）がより低速でより大型のキャッシュ（Ｌ２キャッシュ）ヘ接続されているシステムである。プロセッサ１０６の中央処理装置（ＣＰＵ）コア論理がメインメモリ１０７におけるメモリ位置からデータを読取るか又はそこへデータを書込む場合に、該キャッシュシステムは、最初に、その位置に属するデータがＬ１キャッシュ内にあるか否かを判別するためにテストを行う。そのデータがＬ１キャッシュ内に存在している場合には、そのデータがＬ１キャッシュによって迅速に供給されるか又はアップデートされる。そのデータがＬ１キャッシュ内に存在しない場合には、Ｌ１キャッシュ読取「ミス」又はＬ１キャッシュ書込「ミス」が発生する。
【００２３】次いで、Ｌ２キャッシュによってプロセッサ１０６のＣＰＵコア論理に対してそのデータが供給されるか又はアップデートされる。Ｌ１キャッシュ読取ミスの場合には、要求されたデータを包含しているラインもＬ２キャッシュからＬ１キャッシュへ転送され、従ってプロセッサ１０６が次にそのデータへアクセスする場合にそのデータをより迅速に供給することが可能である。このことはＬ１キャッシュラインフィルとして知られている。そのデータがＬ２キャッシュ内にも存在しない場合には、Ｌ２キャッシュミスが発生し、且つ要求されたデータを包含するラインがメインメモリ１０７からフェッチされ、次いで、そのデータが次に要求された場合により高速のアクセスを与えるためにＬ２キャッシュ内にロードされる。このことはＬ２キャッシュラインフィルとして知られている。
【００２４】図２は本発明の１実施例に基づく例示的なプロセッサ１０６をより詳細に示している。プロセッサ１０６は、命令フェッチ（ＩＦ）段２０５、デコード段２１０、オペランドフェッチ段２１５、実行段２２０、ライトバック段２２５を有する命令パイプラインを包含している。プロセッサ１０６は、更に、レジスタスタック２３０、命令（ＩＮＳＴＲ）キャッシュ２３５、データキャッシュ２４０を有している。
【００２５】プロセッサ１０６は、命令をフェッチし且つ解釈し、データを検索し、命令を実行し、結果を格納することが可能な中央処理装置（ＣＰＵ）である。例示した命令パイプラインは幾つかの異なる動作を同時的に実行することが可能なメカニズムである。パイプラインは各主要なタスクに対する処理ステップを幾つかの個別的な処理フェーズへ分解することによってこのことを行い、各処理フェーズは別個のパイプライン段によって実行される。各タスクは、その実行を完了するために、各処理フェーズ、従って各パイプライン段を介して逐次的に通過せねばならない。
【００２６】命令フェッチ段２０５は命令キャッシュ２３５から実行すべき命令をフェッチし且つフェッチした命令を命令フェッチバッファ（ＩＦＢ）内に格納する。デコード段２１０によってＩＦＢから取られた命令は高度にコンパクトな形式にエンコードされている。デコード段２１０は該命令をその後のパイプライン段による実行のために直接的に使用することが可能であるより大きな組の信号へデコードする。オペランドフェッチ段２１５はメモリから又はレジスタスタック２３０からオペランドをフェッチする。実行段２２０はオペランドフェッチ段２１５によってフェッチされたオペランドに関して実際の処理（例えば、加算、乗算、除算等）を実施し且つその結果を発生する。ライトバック段２２５は実行段２２０によって発生された結果をデータキャッシュ２４０内又はレジスタスタック２３０におけるレジスタにおける１つの中に書込む。
【００２７】実行段２２０は本発明の原理に基づく１個又はそれ以上のＭビットレースディレイ即ち競合遅延加算器（即ちピラミッド加算器）を有することが可能である。Ｍビット競合遅延加算器は複数個の加算器セルからなるＲ個の行を有しており、各行は、通常、先行する（即ち、より低い次数の）行よりも１個多い加算器セルを有している。従って、最大の行から最小の行へ各行におけるセル数は、一般的な形式、即ちＮ，Ｎ−１，Ｎ−２，Ｎ−３，．．．，Ｎ−ｐ＋１，Ｎ−ｐ，Ｋを有している。最大行はＮ個の加算器セルを包含しており、２番目に大きな行はＮ−１個の加算器セルを包含しており、以下同様である。最も小さな行はＫ個のセルを包含しており、それは１個を超えるセルだけ２番目に小さな行（即ち、Ｎ−ｐ）よりも小さいものとすることが可能である。何故ならば、Ｍビット競合遅延加算器の加算器セルの総数Ｍが連続する計数の和に正確に等しいという保証は存在しないからである（即ち、Ｍは１＋２＋３＋．．．＋（Ｎ−１）＋Ｎと等しくない場合がある）。
【００２８】１例として、Ｍ＝３２である場合には、３２ビット競合遅延加算器は６個の行（即ち、行０、行１、行２、行３、行４、行５）に配列された３２個の加算器セルを有しており、夫々、２個、４個、５個、６個、７個、８個の加算器セルを包含している。この場合には、Ｎ＝８、（Ｎ−ｐ）＝４、Ｋ＝２である。別の例示的な実施例においては、Ｍ＝６４である場合には、６４ビット競合遅延加算器は１０個の行（即ち、行０乃至行９）に配列された６４個の加算器セルを有しており、夫々、１個、３個、４個、５個、６個、７個、８個、９個、１０個、１１個の加算器セルを包含している。この場合には、Ｎ＝１１、（Ｎ−ｐ）＝３、Ｋ＝１である。
【００２９】注意すべきことであるが、別の実施例においては、６４ビット競合遅延加算器は８個の行（即ち、行０乃至行７）に配列された６４個の加算器セルを有することが可能であり、夫々、１個、６個、７個、８個、９個、１０個、１１個、１２個の加算器セルを包含している。この場合には、Ｎ＝１２、（Ｎ−ｐ）＝６、Ｋ＝１である。然しながら、以下に詳細に説明するように、Ｍビット競合遅延加算器のキャリィリップル遅延（従って、その速度）は、最も長い行の長さによって決定される。Ｎ＝１２の最も長い行を有している６４ビット競合遅延加算器はＮ＝１１の最も長い行を有している６４ビット競合遅延加算器よりもより長い遅延を有している。従って、Ｍビット競合遅延加算器において最も長い行の長さを最小とさせることが重要である。
【００３０】図３は本発明の１実施例に基づくプロセッサ１０６における例示的な３２ビット競合遅延加算器３００のアーキテクチャを例示した論理的ブロック図である。３２ビット競合遅延加算器３００は６５個の入力と３３個の出力とを有している。これら６５個の入力は第一の３２ビット引数（Ａ０乃至Ａ３１）、第二の３２ビット引数（Ｂ０乃至Ｂ３１）、存在する場合に、前の段からのキャリィイン（ＣＩ）ビットを包含している。３３個の出力は３２ビット和（Ｓ０乃至Ｓ３１）及び、存在する場合に、次の段へのキャリィアウト（ＣＯＵＴ）ビットを包含している。入力ピンと３２個の加算器セルとの間及び出力ピンと３２個の加算器セルとの間の物理的接続は、３２ビット競合遅延加算器３００の動作をより明確に説明するために図示していない。
【００３１】２つの３２ビット入力がＣ０乃至Ｃ３１の符号を付けた３２個の加算器セルによって加算される。最小桁加算器セル、即ちセル０（Ｃ０）及び最大桁加算器セル、即ちセル３１（Ｃ３１）の拡大図も示されている。行０はセル０及びセル１を有している。行１はセル２、セル３、セル４、セル５を有している。行２はセル６乃至セル１０を有している。行３はセル１１乃至セル１６を有している。行４はセル１７乃至セル２３を有している。最後に、行５はセル２４乃至セル３１を有している。
【００３２】各行はキャリィアウトビットを発生し、それは次のより高い行へのキャリィインビットである。行０は前の加算器段からの３２ビット競合遅延加算器３００のＣＩビットを受取る。行０からのキャリィアウト０ビットは行１に対するキャリィイン１ビットである。行１からのキャリィアウト１ビットは行２へのキャリンイン２ビットである。行２からのキャリィアウト２ビットは行３に対するキャリンイン３ビットである。行３からのキャリィアウト３ビットは行４に対するキャリィイン４ビットである。行４からのキャリィアウト４ビットは行５に対するキャリィ５ビットである。行５からのキャリィアウト５ビットは３２ビット競合遅延加算器３００からのＣＯＵＴビットを発生し、それは次の加算器段へ送られる。
【００３３】本発明の原理によれば、３２ビット競合遅延加算器３００における３２個の加算器セルの各々は、実際には、２個の和ビット及び２個のキャリィビットを計算するデュアル（二重）加算器である。１個の和ビット及び１個のキャリィビットが、前の行からのキャリィビットが論理０であったものとの仮定に基づいて計算される。他方の和ビット及び他方のキャリィビットは、前の段からのキャリィビットが論理１であったものとの仮定に基づいて計算される。各行のスタートにおけるセル（Ｃ０，Ｃ２，Ｃ６，Ｃ１１，Ｃ１７，Ｃ２４）は、２個の和ビット及び２個のキャリィビットを発生し且つ該２個のキャリィビットをその行内における次のより高いセルへパスすることによって処理を開始する。これら２つのキャリィビットが各行における加算器セルを介してリップル即ち通過し且つ各行の終りにおける行マルチプレクサへ出力される。前の行からのキャリィビットは各加算器セル内のマルチプレクサを制御し、それはＳ０乃至Ｓ３１へ出力されるべき正しい和ビットを選択する。前の行からのキャリィビットも次のより高い行へ出力されるべき正しいキャリィビットを選択するために各行の終りにおける行マルチプレクサを制御する。
【００３４】拡大して示したセル０は２個の入力、即ちＡ０及びＢ０を受取る。セル０は２つの和ビット、即ちＳ０（０）及びＳ０（１）、及び２つのキャリィビット、即ちＣ０（０）及びＣ０（１）を発生する。Ｓ０（０）ビットは、キャリィイン０（即ち、ＣＩ）が０であったと仮定した場合のＡ０及びＢ０の和である。Ｓ０（１）ビットは、キャリィイン０（即ち、ＣＩ）が１であったと仮定した場合のＡ０及びＢ０の和である。同様に、Ｃ０（０）ビットは、キャリィイン０が０であったと仮定した場合のＡ０＋Ｂ０のキャリィアウトであり、且つＣ０（１）ビットは、キャリィイン０が１であったと仮定した場合のＡ０＋Ｂ０のキャリィアウトである。内部マルチプレクサが３２ビット競合遅延カウンタ３００のＳ０出力ピンへ出力されるべきＳ０（０）及びＳ０（１）のうちの１つのみを選択する。然しながら、Ｃ０（０）及びＣ０（１）の両方が行０における次の加算器セル、即ち、セル１（Ｃ１）ヘ出力される。
【００３５】セル１は外部入力Ａ１及びＢ１及びセル０からの２つのキャリィビット、即ちＣ０（０）及びＣ０（１）を受取る。セル０は２つの和ビット、即ちＳ１（０）及びＳ１（１）、及び２つのキャリィビット、即ちＣ１（０）及びＣ１（１）を発生する。Ｓ１（０）ビットはＡ１，Ｂ１，Ｃ０（０）の和である（即ち、キャリィイン０が０であったと仮定している）。Ｓ１（１）ビットはＡ１，Ｂ１，Ｃ０（１）の和である（即ち、キャリィイン０が１であったと仮定している）。Ｃ１（０）ビットはＡ１＋Ｂ１＋Ｃ０（０）のキャリィアウトであり、且つＣ１（１）ビットはＡ１＋Ｂ１＋Ｃ０（１）のキャリィアウトである。内部マルチプレクサが３２ビット競合遅延遅延加算器３００のＳ１出力ピンへ出力されるべきＳ１（０）及びＳ１（１）のうちの１つのみを選択する。然しながら、Ｃ１（０）及びＣ１（１）の両方が行０マルチプレクサ（ＭＵＸ）ヘ出力される。
【００３６】ＣＩ（即ち、キャリィイン０）は行０ＭＵＸを制御する。ＣＩ＝０か又はＣＩ＝１のいずれであるかに依存して、行０ＭＵＸはＣ１（０）か又はＣ１（１）のいずれかを行０からのキャリィアウト（即ちキャリィアウト０）に選択する。図３において、行０における左側に向いた矢印は、出力ピンへ送られるべき正しい和ビット（Ｓ０及びＳ１）を選択するために行０における全ての加算器セル（セル０及びセル１）ヘキャリィイン０ビットが適用されることを表わしている。行０における右側に向いた矢印は、行０ＭＵＸへ適用されるＣ１（０）及びＣ１（１）キャリィビットを発生するために行０におけるセル０及びセル１を介してデュアル即ち二重のキャリィビットがリップル即ち通過する方向を表している。
【００３７】行１は、行０において発生するデュアル加算処理と同様なデュアル加算処理を実行する。セル２はセル０と同様である。セル２は２つの入力、即ちＡ２及びＢ２を受取る。セル２は２つの和ビット、即ちＳ２（０）及びＳ２（１）、及び２つのキャリィビット、即ちＣ２（０）及びＣ２（１）を発生する。Ｓ２（０）ビットは、キャリンイン１（即ち、キャリィアウト０）が０であったものと仮定した場合のＡ２及びＢ２の和である。Ｓ２（１）ビットは、キャリィイン１（即ち、キャリィアウト０）が１であったものと仮定した場合のＡ２及びＢ２の和である。同様に、Ｃ２（０）ビットは、キャリィイン１が０であったと仮定した場合のＡ２＋Ｂ２のキャリィアウトであり、且つＣ２（１）ビットは、キャリィイン１が１であったと仮定した場合のＡ２＋Ｂ２のキャリィアウトである。内部マルチプレクサが３２ビット競合遅延加算器３００のＳ２の出力ピンへ出力されるべきＳ２（０）及びＳ２（１）のうちの１つのみを選択する。然しながら、Ｃ２（０）及びＣ２（１）の両方が行１における次の加算器セル、即ちセル３（Ｃ３）ヘ出力される。
【００３８】セル３は外部入力Ａ３及びＢ３及びセル２からの２つのキャリィビット、即ちＣ２（０）及びＣ２（１）を受取る。セル３は２つの和ビット、即ちＳ３（０）及びＳ３（１）、及び２つのキャリィビット、即ちＣ３（０）及びＣ３（１）を発生する。Ｓ３（０）ビットはＡ３，Ｂ３，Ｃ２（０）の和である（即ち、キャリィイン１が０であったと仮定している）。Ｓ３（１）ビットはＡ３，Ｂ３，Ｃ２（１）の和である（即ち、キャリィイン１が１であったと仮定している）。Ｃ３（０）ビットはＡ３＋Ｂ３＋Ｃ２（０）のキャリィアウトであり、且つＣ３（１）ビットはＡ３＋Ｂ３＋Ｃ２（１）のキャリィアウトである。内部マルチプレクサが３２ビット競合遅延加算器３００のＳ３出力ピンへ出力されるべきＳ３（０）及びＳ３（１）のうちの１つのみを選択する。然しながらＣ３（０）及びＣ３（１）の両方が行１における次の加算器セル、即ちセル４（Ｃ４）ヘ出力される。
【００３９】セル４はセル３と同様である。セル４は外部入力Ａ４及びＢ４及びセル３からの２つのキャリィビット、即ちＣ３（０）及びＣ３（１）を受取る。セル４は２つの和ビット、即ちＳ４（０）及びＳ４（１）、及び２つのキャリィビット、即ちＣ４（０）及びＣ４（１）を発生する。Ｓ４（０）ビットはＡ４、Ｂ４、Ｃ３（０）の和である。Ｓ４（１）ビットはＡ４，Ｂ４，Ｃ３（１）の和である。Ｃ４（０）ビットはＡ４＋Ｂ４＋Ｃ３（０）のキャリィアウトであり、且つＣ４（１）ビットはＡ４＋Ｂ４＋Ｃ３（１）のキャリィアウトである。内部マルチプレクサが３２ビット競合遅延加算器３００のＳ４出力ピンへ出力されるべきＳ４（０）及びＳ４（１）のうちの１つのみを選択する。然しながら、Ｃ４（０）及びＣ４（１）の両方が行１における次の加算器セル、即ちセル５（Ｃ５）ヘ出力される。
【００４０】セル５はセル３及びセル４と同様である。セル５は外部入力Ａ５及びＢ５及びセル４からの２つのキャリィビット、即ちＣ４（０）及びＣ４（１）を受取る。セル５は２つの和ビット、即ちＳ５（０）及びＳ５（１）、及び２つのキャリィビット、即ちＣ５（０）及びＣ５（１）を発生する。Ｓ５（０）ビットはＡ５，Ｂ５，Ｃ４（０）の和である。Ｓ５（１）ビットはＡ５，Ｂ５，Ｃ４（１）の和である。Ｃ５（０）ビットはＡ５＋Ｂ５＋Ｃ４（０）のキャリィアウトであり、且つＣ５（１）ビットはＡ５＋Ｂ５＋Ｃ４（１）のキャリィアウトである。内部マルチプレクサが３２ビット競合遅延加算器３００のＳ５出力ピンへ出力されるべきＳ５（０）及びＳ５（１）のうちの１つのみを選択する。然しながら、Ｃ５（０）及びＣ５（１）の両方が行１マルチプレクサ（ＭＵＸ）ヘ出力される。
【００４１】キャリィイン１は行１ＭＵＸを制御する。キャリィイン１＝０であるか又はキャリィイン１＝１であるかに依存して、行１ＭＵＸは行１からのキャリィアウト（即ちキャリィアウト１）としてＣ５（０）か又はＣ５（１）を選択する。図３において、行１における左側に向いた矢印は、出力ピンへ送られるべき正しい和ビット（Ｓ２，Ｓ３，Ｓ４，Ｓ５）を選択するために行１における全ての加算器セル（セル２乃至セル５）ヘキャリィイン１ビットが印加されることを表わす。行１における右側に向いた矢印は、行１ＭＵＸへ印加されるＣ５（０）及びＣ５（１）キャリィビットを発生するために行１におけるセル２、セル３、セル４、セル５を介してデュアル即ち２つのキャリィビットがリップル即ち通過する方向を表している。
【００４２】行２、行３、行４、行５は行０及び行１と同様の態様で動作する。説明の便宜上、行２、行３、行４、行５の動作についてはこの時点において詳細な説明は割愛する。
【００４３】全ての行において、最初の加算器セル（即ち、Ｃ０，Ｃ２，Ｃ６，Ｃ１１，Ｃ１７，Ｃ２４）は２つの入力、即ちＡｘ及びＢｘを受取り、且つ前の行からのキャリィインビットが０であったと仮定して第一和ビットＳｘ（０）及び第一キャリィビットＣｘ（０）及び、前の行からのキャリィンビットが１であったと仮定して第二和ビットＳｘ（１）及び第二キャリィビットＣｘ（１）を発生する。
【００４４】全ての行において、第一加算器セルの後の各加算器セルは２つの外部入力Ａｘ及びＢｘ、及び同一の行における前の加算器セルからの２つの内部入力Ｃｘ−１（０）及びＣｘ−１（１）を受取る。第一加算器セルの後の各加算器セルは、前の加算器セルからのＣｘ−１（０）ビットを使用して、第一和ビットＳｘ（０）及び第一キャリィビットＣｘ（０）を発生し、且つ前の加算器セルからのＣｘ−１（１）ビットを使用して、第二和ビットＳｘ（１）及び第二キャリィビットＣｘ（１）を発生する。各行における最後の加算器セルはその２つのキャリィビットＣｘ（０）及びＣｘ（１）をその行の終りにおける行マルチプレクサへ送る。次いで、前の行からのキャリィインビットが次続の行へ送られるべき正しいキャリィアウトビットを選択する。
【００４５】各行は次に続く行よりも一層短いので、各行からのキャリィアウトビットは次に続く行における最後の加算器セルがその２つのキャリィビットＣｘ（０）及びＣ（１）を計算する前に、次に続く行へのキャリィインビットとして使用可能となる。従って、行からのキャリィアウトビットは、デュアル即ち２つのキャリィビットが各行における加算器セルを介してリップル即ち通過するよりも速く、行マルチプレクサを介して上方へリップル即ち通過する。
【００４６】例えば、時間ｔ１において、加算器セルＣ０，Ｃ２，Ｃ６，Ｃ１１，Ｃ１７，Ｃ２４は、初期的な組のキャリィアウトビット及びキャリィインビットの各場合（即ち、１又は０）に対する和を計算している。セルＣ０，Ｃ２，Ｃ６，Ｃ１１，Ｃ１７，Ｃ２４からのデュアルキャリィアウトビットはセルＣ１，Ｃ３，Ｃ７，Ｃ１２，Ｃ１３，Ｃ２５へ横方向に伝播する。
【００４７】時間ｔ２において、加算器セルＣ１，Ｃ３，Ｃ７，Ｃ１２，Ｃ１８，Ｃ２５は別の組のキャリィアウトビット及びキャリィインビットの各場合（即ち、１又は０）に対する和を計算する。この時点において、行０は完了しており且つＣＩは行０に対するキャリィアウト０（即ち、行１に対するキャリィイン１）としてＣ１からのキャリィアウトビットＣ１（０）又はＣ１（１）のうちの１つを選択する。セルＣ３，Ｃ７，Ｃ１２，Ｃ１８，Ｃ２５からのデュアルのキャリィアウトビットはセルＣ４，Ｃ８，Ｃ１３，Ｃ１９，Ｃ２６へ横方向に伝播する。
【００４８】時間ｔ３において、加算器セルＣ４，Ｃ８，Ｃ１３，Ｃ１９，Ｃ２６は別の組のキャリィアウトビット及びキャリィインビットの各場合（即ち、１又は０）に対する和を計算する。セルＣ４，Ｃ８，Ｃ１３，Ｃ１９，Ｃ２６からのデュアルキャリィアウトビットはセルＣ５，Ｃ９，Ｃ１４，Ｃ２０，Ｃ２７ヘ横方向に伝播する。時間ｔ４において、セルＣ５，Ｃ９，Ｃ１４，Ｃ２０，Ｃ２７は別の組のキャリィアウトビット及びキャリィインビットの各場合（即ち、１又は０）に対する和を計算する。この時点において、行１は完了しており且つキャリィイン１は行１に対するキャリィアウト１（即ち、行２に対するキャリィイン２）としてＣ５からのキャリィアウトビットＣ５（０）又はＣ５（１）のうちの１つを選択する。セルＣ９，Ｃ１４，Ｃ２０，Ｃ２７からのデュアルキャリィアウトビットはセルＣ１０，Ｃ１５，Ｃ２１，Ｃ２８へ横方向に伝播する。
【００４９】時間ｔ５において、加算器セルＣ１０，Ｃ１５，Ｃ２１，Ｃ２８が別の組のキャリィアウトビット及びキャリィインビットの各場合（即ち、１又は０）に対する和を計算する。この時点において、行２は完了しており且つキャリィイン２は行２に対するキャリィアウト２（即ち、行３に対するキャリィイン３）としてＣ１０からのキャリィアウトビットＣ１０（０）又はＣ１０（１）のうちの１つを選択する。セルＣ１５，Ｃ２１，Ｃ２８からのデュアルキャリィアウトビットはセルＣ１６，Ｃ２２，Ｃ２９へ横方向に伝播する。
【００５０】時間ｔ６において、加算器セルＣ１６，Ｃ２２，Ｃ２９は別の組のキャリィアウトビット及びキャリィインビットの各場合（即ち、１又は０）に対する和を計算する。この時点において、行３は完了しており且つキャインイン３は行３に対するキャリィアウト３（即ち、行４に対するキャリィイン４）としてＣ１６からのキャリィアウトビットＣ１６（０）又はＣ１６（１）のうちの１つを選択する。セルＣ２２，Ｃ２９からのデュアルキャリィアウトビットはセルＣ２３，Ｃ３０へ横方向に伝播する。
【００５１】時間ｔ７において、加算器セルＣ２３，Ｃ３０は別の組のキャリィアウトビット及びキャリィインビットの各場合（即ち、１又は０）に対する和を計算する。この時点において、行４は完了しており且つキャリィイン４は行４に対するキャリィアウト４（即ち、行５に対するキャリィイン５）としてＣ２３からのキャリィアウトビットＣ２３（０）又はＣ２３（１）のうちの１つを選択する。セルＣ３０からのデュアルキャリィアウトビットはセルＣ３１へ横方向に伝播する。
【００５２】時間ｔ８において、加算器セルＣ３１は最終的なキャリィアウトビット及びキャリィインビットの各場合（即ち、１又は０）に対する和を計算する。この時点において、行５は完了しており且つキャリィイン５は行５に対するキャリィアウト５（即ち、３２ビット競合遅延カウンタ３００に対するＣＯＵＴ）としてＣ３１からのキャリィアウトビットＣ３１（０）又はＣ３１（１）のうちの１つを選択する。
【００５３】３２ビット競合遅延加算器３００の独特のアーキテクチャは、３２ビット加算の遅延時間を８ビット加算の遅延時間へ減少させている。３２ビット競合遅延加算器３００の遅延は行５における８個の加算器セルのキャリィリップル遅延＋行５ＭＵＸの伝播遅延と等しい。これは従来の３２ビット加算器のリップル遅延と比較して著しい改良である。
【００５４】図４は本発明の１実施例に基づく例示的な３２ビット競合遅延加算器３００における加算器セルの配列を例示した物理的なレイアウト図である。３２ビット競合遅延加算器３００によって占有される集積回路のスペースを最小とさせるために、行１−５の各々における最初のセル（即ち、Ｃ２，Ｃ６，Ｃ１１，Ｃ１７，Ｃ２４）はその下側の行の終りに移動されている。例えば、セル２は行０の終わりに移動されており、セル６は行１の終わりに移動されており、以下同様である。行１−５の各々はＬ形状とされている。然しながら、この新しい物理的レイアウトは、図３において上述したように、３２ビット競合遅延加算器３００の機能的な動作に影響を与えるものではない。換言すると、セル２からのデュアルキャリィビット、即ちＣ２（０）及びＣ２（１）は、未だに、セル３へ伝播し、セル６からのデュアルキャリィビット、即ちＣ６（０）及びＣ６（１）は、未だに、セル７へ伝播し、以下同様である。
【００５５】更に、３２ビット競合遅延加算器３００における加算器セルの各々はスタート（ＳＴＡＲＴ）セルか、ポジティブ（ＰＯＳ）セルか、又はネガティブ（ＮＥＧ）セルのうちの１つとして識別されている。ＳＴＡＲＴセル、ＰＯＳセル、及びＮＥＧセルの用語は、３２ビット競合遅延加算器３００においては３つのタイプの加算器セルが存在している事実を表わしている。各行における加算器セルを介しての時間がクリチカル即ち臨界的なデータ経路はデュアルキャリィ経路、即ちＣｘ（０）及びＣｘ（１）である。以下の説明から理解されるように、各加算器セルは次のセルへデュアルキャリィビットを伝播させるパスゲート（即ちスイッチ）を包含している。各パスゲートはキャリィ信号を減衰させ、従って２個又は３個のパスゲートの後に、キャリィ信号は不正確に読取られる場合がある。このことに対する典型的な解決方法は、キャリィ信号をブーストさせるために各セル内にバッファを付加することである。
【００５６】該バッファは、典型的に、直列した一対のインバータゲートである。然しながら、このことは時間的にクリチカルなデータ経路内に加算器セル当たり２個のゲート遅延を付加することとなる。８個の加算器セルを有している行５においては、このことは約１６個のインバータゲート遅延を付加することとなる。この問題を解消するために、本発明は該バッファゲートを１個の加算器セルにおける第一インバータと次に続く加算器セルにおける第二インバータとに分割している。先行する加算器セルからの正論理デュアルキャリィインビットを受取り且つそれらを負論理デュアルキャリィアウトビットへ反転させる加算器セルはＮＥＧセルと呼称される。先行する加算器セルから負論理デュアルキャリィインビットを受取り且つそれらを正論理デュアルキャリィアウトビットへ反転させる加算器セルはＰＯＳセルと呼称される。
【００５７】各行における最初のセルはスタート（ＳＴＡＲＴ）セル（即ち、Ｃ０，Ｃ２，Ｃ６，Ｃ１１，Ｃ１７，Ｃ２４）である。スタートセルの全ては負論理デュアルキャリィアウトビットを発生する。各行における偶数番目のセルの位置はＰＯＳセルである。従って、各行における２番目のセル（即ち、Ｃ１，Ｃ３，Ｃ７，Ｃ１２，Ｃ１８，Ｃ２５）はＰＯＳセルであり、各行における４番目のセル（即ち、Ｃ５，Ｃ９，Ｃ１４，Ｃ２０，Ｃ２７）はＰＯＳセルであり、各行における６番目のセル（即ち、Ｃ１６，Ｃ２２，Ｃ２９）はＰＯＳセルであり、且つ各行における８番目のセル（即ち、Ｃ３１）はＰＯＳセルである。
【００５８】これと対応して、各行における奇数番目のセルの位置はＮＥＧセル（スタートセルである最初のセルをのぞく）である。従って、各行における３番目のセル（即ち、Ｃ４，Ｃ８，Ｃ１３，Ｃ１９，Ｃ２６）はＮＥＧセルであり、各行における５番目のセル（即ち、Ｃ１０，Ｃ１５，Ｃ２１，Ｃ２８）はＮＥＧセルであり、各行における７番目のセル（即ち、Ｃ２３，Ｃ３０）はＮＥＧセルである。
【００５９】入力ピンと出力ピンとの間に正論理を維持するためには各行における反転総数は偶数でなければならない。幾つかの行は偶数の加算器セル（及び反転）を有しており且つ幾つかは奇数の加算器セル（及び反転）を有しているので、行マルチプレクサは補償を行うために反転用マルチプレクサか又は非反転用マルチプレクサとすることが可能である。行０においては、第一反転がセル０（スタートセル）において発生し且つ第二反転はセル１（ＰＯＳセル）において発生する。これは偶数個の反転であるので、行０ＭＵＸは非反転（ＮＩＮＶ）である。
【００６０】行１においては、第一反転がセル２（スタートセル）において発生し、第二反転がセル３（ＰＯＳセル）において発生し、第三反転がセル４（ＮＥＧセル）において発生し、且つ第四反転がセル５（ＰＯＳセル）において発生する。これも偶数個の反転であるので、行１ＭＵＸは非反転（ＮＩＮＶ）である。この論理に従って、行２ＭＵＸは反転（ＩＮＶ）であり、行３ＭＵＸは非反転（ＮＩＮＶ）であり、行４ＭＵＸは反転（ＩＮＶ）であり、行５ＭＵＸは非反転（ＮＩＮＶ）であることを理解することが可能である。
【００６１】図５−７は本発明の１実施例に基づく例示的な３２ビット競合遅延加算器３００における行０、行１、行２における反転論理をより詳細に例示した概略図である。図５−７において、信号の名称の終わりに使用した文字Ｎは負論理（即ちアクティブ低信号）を表わしている。信号の名前の終わりに文字Ｎがない場合には、その信号は正論理（即ちアクティブ高信号）である。
【００６２】図５−７に示されるように、各スタートセル（即ち、図５におけるＣ０、図６におけるＣ２、図７におけるＣ６）は３個の入力（Ａ，Ｂ，ＣＩ）及び３個の出力（Ｓ，ＣＯＵＴ０Ｎ，ＣＯＵＴ１Ｎ）を有している。引数ビットＡ及びＢはその加算器セルに対するＡ０−Ａ３１及びＢ０−Ｂ３１における対応するビットへ結合される。和ビットＳはＳ０−Ｓ３１における対応するビットへ結合される。ＣＩはその行に対するキャリィインビットを受取る。ＣＩ入力はスタートセルによって発生される２個の内部和ビットのうちの１つを選択する各スタートセルにおける内部マルチプレクサを制御する。ＣＩ入力はデュアルキャリィアウトビットの値に影響をあたえるものではない。各スタートセルからのデュアルキャリィアウトビット、即ちＣＯＵＴ０Ｎ及びＣＯＵＮＴ１Ｎは負論理信号である。ＣＯＵＴ０Ｎは、その行に対するキャリィインが論理０であったことを仮定するキャリィアウトビットである。ＣＯＵＴ１Ｎは、その行に対するキャリィインが論理１であったことを仮定するキャリィアウトビットである。
【００６３】図５−７に示されるように、各ＰＯＳセル（即ち、図５におけるＣ１、図６におけるＣ３及びＣ５、図７におけるＣ７及びＣ９）は５個の入力（Ａ，Ｂ，ＣＩ，ＣＩＮ０Ｎ，ＣＩＮ１Ｎ）及び３個の出力（Ｓ，ＣＯＵＴ０，ＣＯＵＴ１）を有している。引数ビットＡ及びＢはその加算器セルに対するＡ０−Ａ３１及びＢ０−Ｂ３１における対応するビットへ結合される。和ビットＳはＳ０−Ｓ３１における対応するビットへ結合される。ＣＩはその行に対するキャリィインビットを受取る。ＣＩ入力は、ＰＯＳセルによって発生される２個の内部和ビットのうちの１つを選択する各ＰＯＳセルにおける内部マルチプレクサを制御する。ＣＩ入力はデュアルキャリィアウトビットの値に影響を与えるものではない。各ＰＯＳセルからのデュアルキャリィアウトビット、即ちＣＯＵＴ０及びＣＯＵＴ１は正論理信号である。ＣＯＵＴ０は、その行に対するキャリィインが論理０であったことを仮定するキャリィアウトビットである。ＣＯＵＴ１は、その行に対するキャリィインが論理１であったことを仮定するキャリィアウトビットである。各ＰＯＳセルに対するデュアルキャリィインビット、即ちＣＩＮ０Ｎ及びＣＩＮ１Ｎは負論理信号である。何故ならば、ＰＯＳセルは、常に、スタートセル又はＮＥＧセルの出力へ結合されているからである。ＣＩＮ０Ｎは、その行に対するキャリィインが論理０であったことを仮定するキャリィインビットである。ＣＩＮ１Ｎは、その行に対するキャリィインが論理１であったことを仮定するキャリィインビットである。
【００６４】図６及び７に示されるように、各ＮＥＧセル（即ち、図６におけるＣ４、図７におけるＣ８及びＣ１０）は５個の入力（Ａ，Ｂ，ＣＩ，ＣＩＮ０，ＣＩＮ１）及び３個の出力（Ｓ，ＣＯＵＴ０Ｎ，ＣＯＵＴ１Ｎ）を有している。引数ビットＡ及びＢはその加算器セルに対するＡ０−Ａ３１及びＢ０−Ｂ３１における対応するビットへ結合される。和ビットＳはＳ０−Ｓ３１における対応するビットヘ結合される。ＣＩはその行に対するキャリィインビットを受取る。ＣＩ入力は、ＮＥＧセルによって発生される２個の内部和ビットのうちの１つを選択する各ＮＥＧセルにおける内部マルチプレクサを制御する。ＣＩ入力はデュアルキャリィアウトビットの値に影響を与えるものではない。各ＮＥＧセルからのデュアルキャリィアウトビット、即ちＣＯＵＴ０Ｎ及びＣＯＵＮＴ１Ｎは負論理信号である。ＣＯＵＴ０Ｎは、その行に対するキャリィインが論理０であったことを仮定するキャリィアウトビットである。ＣＯＵＴ１Ｎは、その行に対するキャリィインが論理１であったことを仮定するキャリィアウトビットである。各ＮＥＧセルに対するデュアルキャリィインビット、即ちＣＩＮ０及びＣＩＮ１は正論理信号である。何故ならば、ＮＥＧセルは、常に、ＰＯＳセルの出力へ結合されているからである。ＣＩＮ０は、その行に対するキャリィインが論理０であったことを仮定するキャリィインビットである。ＣＩＮ１は、その行に対するキャリィインが論理１であったことを仮定するキャリィインビットである。
【００６５】行０及び行１は非反転マルチプレクサ、即ち、夫々、行０ＭＵＸ及び行１ＭＵＸで終了している。行２は反転マルチプレクサ、即ち行２ＭＵＸで終了している。行２ＭＵＸの出力上の丸印は行２ＭＵＸの反転特性を表している。
【００６６】行３、行４、行５の動作は行０、行１、行２の動作に非常に類似している。行３−５の各々はスタート加算器セルで始まっており且つ一連の交互のＰＯＳ加算器セル及びＮＥＧ加算器セルを包含している。行３−５の各々は反転マルチプレクサか又は非反転マルチプレクサかのいずれかで終了している。本発明の動作の説明が冗長になることを回避するために、行３−５の動作の更なる詳細な説明は割愛する。
【００６７】以下の表１は入力Ａ，Ｂ，ＣＩ（即ち、キャリィインビット）を受取り且つ出力Ｓ（和ビット）及びＣＯ（キャリィアウトビット）を発生する一般的な加算器セルに対する真理値表である。
【００６８】
【表１】

【００６９】図８は本発明の１実施例に基づく例示的な３２ビット競合遅延加算器３００における例示的なスタート加算器セル８００の概略図である。例示的なスタート加算器セル８００は加算器セルＣ０，Ｃ２，Ｃ６，Ｃ１１，Ｃ１７，Ｃ２４のうちのいずれか１つとすることが可能である。スタート加算器セル８００は排他的ＮＯＲ（ＸＮＯＲ）ゲート８０１、排他的ＯＲ（ＸＯＲ）ゲート８０２、ＮＯＲゲート８０３、ＮＡＮＤゲート８０４、反転用マルチプレクサ（ＭＵＸ）８０５を有している。ＮＯＲゲート８０３の出力は負論理信号ＣＯＵＴ１Ｎ（キャリィイン、ＣＩ、１であると仮定）であり、且つＮＡＮＤゲート８０４の出力は負論理信号ＣＯＵＴ０Ｎ（キャリィイン、ＣＩ、０であると仮定）である。ＸＮＯＲゲート８０１は条件付き和Ｘ０Ｎを発生し、それは負論理信号（キャリィイン、ＣＩ、０であると仮定）である。ＸＯＲゲート８０２は条件付き信号Ｓ１Ｎを発生し、それは負論理信号（キャリィイン、１であると仮定）である。反転用ＭＵＸ８０５の出力は和ビットＳであり、それは正論理信号である。キャリィイン信号ＣＩは、ＣＩが最終的に前の行から使用可能となる場合に、Ｓ０Ｎ及びＳ１Ｎのうちの正しい１つを選択する。然しながら、デュアルキャリィアウト信号ＣＯＵＴ０Ｎ及びＣＯＵＴ１ＮはＣＩを待機することはなく、その代わりに、Ａ及びＢが使用可能となると否や伝播する。
【００７０】以下の表は負論理信号ＣＯＵＴ１Ｎ及びＣＯＵＴ０Ｎに対する真理値表である。
【００７１】
【表２】

【００７２】表２が示すように、キャリィインビットＣＩが論理０であると仮定した場合に、ＣＯＵＴ０Ｎは、常に、その真実のキャリィ値が何であるかの反転したものである。同様に、キャリィインビットＣＩが論理１であると仮定した場合に、ＣＯＵＴ１Ｎは、常に、その真実のキャリィ値が何であるかの反転したものである。
【００７３】以下の表は反転用ＭＵＸ８０５の負論理信号Ｓ０Ｎ及びＳ１Ｎ及び出力Ｓに対する真理値表である。
【００７４】
【表３】

【００７５】表３に示されるように、キャリィインビットＣＩが論理０であると仮定した場合に、Ｓ０Ｎは、常に、その真実の和ビットＳが何であるかの反転したものである。然しながら、ＣＩ＝０が、最終的に、反転用ＭＵＸ８０５へ印加される場合に、Ｓ０Ｎは反転されてＣＩ＝０である場合の和ビットＳの真実の値（正論理）を与える。同様に、キャリィインビットＣＩが論理１であると仮定した場合に、Ｓ１Ｎは、常に、真実の和ビットＳが何であるかの反転したものである。然しながら、ＣＩ＝１が、最終的に、反転用ＭＵＸ８０５へ印加される場合に、Ｓ１Ｎは反転され、ＣＩ＝１である場合の和ビットＳの真実の値（正論理）を与える。
【００７６】図９は本発明の１実施例に基づく例示的な３２ビット競合遅延加算器３００における例示的なＰＯＳ加算器セル９００の概略図である。ＰＯＳ加算器セル９００は加算器セルＣ１，Ｃ３，Ｃ５，Ｃ７，Ｃ９，Ｃ１２，Ｃ１４，Ｃ１６，Ｃ１８，Ｃ２０，Ｃ２２，Ｃ２５，Ｃ２７，Ｃ２９，Ｃ３１のうちのいずれか１つとすることが可能である。ＰＯＳ加算器セル９００は排他的ＮＯＲ（ＸＮＯＲ）ゲート９０１、排他的ＯＲ（ＸＯＲ）ゲート９０２、ＸＯＲゲート９０３、ＸＯＲゲート９０４、反転用マルチプレクサ（ＭＵＸ）９０５を有している。ＰＯＳ加算器セル９００も、パスゲート９０６、パスゲート９０７、インバータ９０８、インバータ９０９、スタックインバータ９１０、スタックインバータ９２０を有している。ＰＯＳ加算器セル９００への入力は引数ビットＡ及びＢ、及び先行するＮＥＧ加算器セル又はスタート加算器セルからの一対の負論理キャリィインビットＣＩＮ１Ｎ及びＣＩＮ０Ｎである。
【００７７】以下の表４は、前の行からのキャリィインが論理１（即ち、ＣＩ＝１）である場合の、反転用ＭＵＸ９０５の負論理信号Ｓ１Ｎ及び出力Ｓに対する真理値表である。信号ＡＢはＸＯＲゲート９０２の出力である。
【００７８】
【表４】

【００７９】注意すべきことであるが、前の段からのキャリィインが存在している場合には、ＣＩＮ１Ｎは０（負論理信号）であり、且つ前の段からキャリィインが存在しない場合には、ＣＩＮ１Ｎは１である。従って、表４における和ビット出力Ｓは表１における一般的な加算器セルの和ビット出力Ｓと等価である。
【００８０】以下の表５は、前の行からのキャリィインが論理０（即ち、ＣＩ＝０）である場合の反転用ＭＵＸ９０５の負論理信号Ｓ０Ｎ及び出力Ｓに対する真理値表である。信号ＡＢはＸＯＲゲート９０２の出力である。
【００８１】
【表５】

【００８２】注意すべきことであるが、前の段からのキャリィインが存在している場合には、ＣＩＮ０Ｎは０（負論理信号）であり、且つ前の段からのキャリィインが存在しない場合には、ＣＩＮ０Ｎは１である。従って、表５における和ビット出力Ｓは表１における一般的な加算器セルの和ビット出力Ｓと等価である。
【００８３】一般的な加算器セルに対する表１は、入力ビットＡ及びＢが両方とも０である場合には、キャリィインビットＣＩの値に拘わらずに、キャリィアウトビットＣＯは常に０であることを示している。表１は、又、入力ビットＡ及びＢが両方とも１である場合には、キャリィインビットＣＩの値に拘わらずに、キャリィアウトビットＣＯは常に１であることを示している。Ａ及びＢが異なる場合にのみＣＩビットはキャリィアウトビットＣＯの値に影響を与える。
【００８４】ＰＯＳ加算器セル９００においては、Ａ及びＢが等しい場合にデュアルキャリィアウトビットＣＯＵＴ１及びＣＯＵＴ０の値を決定するためにスタックインバータ９１０及び９２０が使用されている。Ａ及びＢが等しい場合には、ＸＯＲゲート９０２の出力ＡＢは０であり、且つＸＮＯＲゲート９０１の出力ＡＢＮは１である。このことはパスゲート９０６及び９０７をシャットオフ即ち遮断させ、従ってインバータ９０８及び９０９はスタックインバータ９１０及び９２０によって駆動される。
【００８５】Ａ及びＢの両方が０である場合には、スタックインバータ９１０の底部におけるＮ型トランジスタはオフであり且つスタックインバータ９１０の上部におけるＰ型トランジスタはオンである。このことはスタックインバータ９１０の出力を１（即ち、Ｖｄｄ供給電圧）ヘプル即ち移行させ、それはインバータ９０８によって０へ反転される（即ち、ＣＯＵＴ１＝０）。Ａ及びＢの両方が１である場合には、スタックインバータ９１０の底部におけるＮ型トランジスタはオンであり且つスタックインバータ９１０の上部におけるＰ型トランジスタはオフである。このことはスタックインバータ９２０の出力を０（即ち、接地）ヘプル即ち移行させ、それはインバータ９０８によって１へ反転される（即ちＣＯＵＴ１＝１）。
【００８６】同様に、Ａ及びＢの両方が０である場合には、スタックインバータ９２０の底部におけるＮ型トランジスタはオフであり且つスタックインバータ９２０の上部におけるＰ型トランジスタはオンである。このことは、スタックインバータ９２０の出力を１（即ち、Ｖｄｄ供給電圧）ヘプル即ち移行させ、それはインバータ９０９によって０へ反転される（即ち、ＣＯＵＴ０＝０）。Ａ及びＢの両方が１である場合には、スタックインバータ９２０の底部におけるＮ型トランジスタはオンであり且つスタックインバータ９２０の上部におけるＰ型トランジスタはオフである。このことは、スタックインバータ９２０の出力を０（即ち、接地）ヘプル即ち移行させ、それはインバータ９０９によって１へ反転される（即ち、ＣＯＵＴ０＝１）。
【００８７】Ａ及びＢが等しくない場合には、両方のスタックインバータ９１０及びスタックインバータ９２０におけるＮ型トランジスタのうちの１つ及びＰ型トランジスタのうちの１つがオフである。このことはスタックインバータ９１０及び９２０をシャットオフし且つスタックインバータ９１０及び９２０の出力を高インピーダンス状態とさせる。従って、パスゲート９０６及び９０７はインバータ９０８及び９０９の入力を駆動することが可能である。
【００８８】Ａ及びＢが等しくない場合には、ＸＯＲゲート９０２の出力ＡＢは１であり、且つＸＮＯＲゲート９０１の出力ＡＢＮは０である。このことはパスゲート９０６及びパスゲート９０７の両方をターンオンさせる。この時点において、先行する加算器セルからのキャリィインビットＣＩＮ１Ｎはインバータ９０８の入力へ印加され且つ反転されてキャリィアウトビットＣＯＵＴ１を発生する。従って、負論理キャリィインビット（ＣＩＮ１Ｎ）は正論理キャリィアウトビット（ＣＯＵＴ１）ヘ変換される。同様に、先行する加算器セルからのキャリィインビットＣＩＮ０Ｎはインバータ９０９の入力へ印加され且つ反転されてキャリィアウトビットＣＯＵＴ０を発生する。従って、負論理キャリィインビット（ＣＩＮ０Ｎ）は正論理キャリィアウトビット（ＣＯＵＴ０）ヘ変換される。
【００８９】図１０は本発明の１実施例に基づく例示的な３２ビット競合遅延加算器３００における例示的なＮＥＧ加算器セル１０００の概略図である。ＮＥＧ加算器セル１０００は加算器セルＣ４，Ｃ８，Ｃ１０，Ｃ１３，Ｃ１５，Ｃ１９，Ｃ２１，Ｃ２３，Ｃ２６，Ｃ２８，Ｃ３０のうちのいずれか１つとすることが可能である。ＮＥＧ加算器セル１０００は排他的ＮＯＲ（ＸＮＯＲ）ゲート１００１、排他的ＯＲ（ＸＯＲ）ゲート１００２、ＸＯＲゲート１００３、ＸＯＲゲート１００４、反転用マルチプレクサ（ＭＵＸ）１００５を有している。ＮＥＧ加算器セル１０００は、又、パスゲート１００６、パスゲート１００７、インバータ１００８、インバータ１００９、スタックインバータ１０１０、スタックインバータ１０２０を有している。ＮＥＧ加算器セル１０００への入力は引数ビットＡ及びＢ及び先行するＰＯＳ加算器セルからの一対の正論理キャリィインビットＣＩＮ１及びＣＩＮ０である。
【００９０】ＮＥＧ加算器セル１０００は以下の２，３の僅かな差異を除いてＰＯＳ加算器セル９００と多くの点で類似している。
【００９１】１．ＸＮＯＲゲート１００１の出力ＡＢＮはＸＯＲゲート１００２の出力ＡＢではなくＸＯＲゲート１００３及び１００４へ印加される。
【００９２】２．パスゲート１００６及び１００７及びインバータ１００８及び１００９の順番が逆である。
【００９３】ＣＩＮ１及びＣＩＮ０は正論理信号であるので、和ビットＳ１Ｎ及びＳ０ＮはＰＯＳ加算器セル９００の場合におけるようなＡＢではＡＢＮを使用してＸＯＲゲート１００３及び１００４によって発生される。
【００９４】ＮＥＧ加算器セル１０００においては、Ａ及びＢが同一である場合には、パスゲート１００６及び１００７がオフであり且つスタックインバータ１０１０及び１０２０の出力は夫々反転なしで出力線ＣＯＵＴ１Ｎ及びＣＯＵＴ０Ｎを駆動する。従って、Ａ＝Ｂ＝０である場合には、ＣＯＵＴ１Ｎ＝ＣＯＵＮＴ０Ｎ＝１であり、且つＡ＝Ｂ＝１である場合には、ＣＯＵＴ１Ｎ＝ＣＯＵＮＴ０Ｎ＝０である。
【００９５】Ａ及びＢが等しくない場合には、パスゲート１００６及び１００７はオンであり且つスタックインバータ１０１０及び１０２０はオフである。この場合には、インバータ１００８及び１００９は入力ＣＩＮ１及びＣＩＮ０を反転させて負論理キャリィアウト信号ＣＯＵＴ１Ｎ及びＣＯＵＮＴ０Ｎを駆動する。
【００９６】以上、本発明の具体的実施の態様について詳細に説明したが、本発明は、これら具体例にのみ制限されるべきものではなく、本発明の技術的範囲を逸脱することなしに種々の変形が可能であることは勿論である。
【出願人】 【識別番号】５９１２３６４４８
【氏名又は名称】エスティーマイクロエレクトロニクス，インコーポレイテッド
【氏名又は名称原語表記】ＳＴＭｉｃｒｏｅｌｅｃｔｒｏｎｉｃｓ，Ｉｎｃ
【出願日】 平成１３年９月２１日（２００１．９．２１）
【代理人】 【識別番号】１０００７６１８５
【弁理士】
【氏名又は名称】小橋 正明
【公開番号】 特開２００２−１０８６０７（Ｐ２００２−１０８６０７Ａ）
【公開日】 平成１４年４月１２日（２００２．４．１２）
【出願番号】 特願２００１−２８９０４４（Ｐ２００１−２８９０４４）