JPH0827708B2 - Ａｌｕ状況判定装置 - Google Patents

Description

【発明の詳細な説明】 ［関連特許出願］ 本特許出願は、優先権を主張し、下記の特許出願の米
国一部継続特許出願として取り扱うべきものである。

（１）1990年４月４日出願の“Data Dependency Collap
sing Hardware Apparatus"と題する、スタマティス・ヴ
ァッシリアディス（Stamatis Vassiliadis）他の米国特
許出願第07/504910号（IBMドケットEN9−90−014）。

（２）1990年11月28日出願の“Overflow Determination
for Three−Operand ALUS in a Scalable Compound In
struction Set Machine"と題するスタマティス・ヴァッ
シリアディス他の米国特許出願第07/619868号（IBMドケ
ットEN9−90−033）。

本特許出願は、下記の特許出願に開示された内容と関
係がある。

（３）1991年３月29日出願の本願と同時に出願された
“High Performance Interlock Collapsing ALU Appara
tus"と題するスタマティス・ヴァッシリアディス他米国
特許出願第677079号（IBMドケットEN9−91−005）。

さらに、本出願の内容は、他の応用分野および用途も
有するが、下記の追加の特許出願によって定義されるス
ケーラブル複合命令セット計算機（SCISM）に関連して
使用することができる。

本特許出願は、下記の同時係属の米国特許出願に関係
する。

（１）1990年５月４日出願の、“Scalable Compound In
struction Set Machine Architecture"と題するスタマ
ティス・ヴァッシリアディス他の米国特許出願第07/519
384号（IBMドケットEN9−90−020）。

（２）1990年５月４日出願の“General Purpose Compou
nd Apparatus For Instruction−Level Parallel Proce
ssors"と題するリチャード・Ｊ・アイケマイヤー（Rich
ard J.Eichemeyer）他の米国特許出願第07/519382号（I
BMドケットEN9−90−019）。

（３）1990年５月10日出願の“Compounding Preprocess
or For Cache"と題するバーソロミュー・ブラナー（Bar
tholomew Blaner）他の米国特許出願第07/522219号（IB
MドケットEN9−90−012）。

（４）1990年６月26日出願の“An In−Memory Preproce
ssor for a Scalable Compound Instruction Set Machi
ne Processor"と題するリチャード・Ｊ・アイケマイヤ
ー他の米国特許出願第07/543464号（IBMドケットEN9−9
0−018）。

（５）1990年６月26日出願の“Memory Management for
Scalable Compound Instruction Set Machines With In
−Memory Compounding"と題するリチャード・Ｊ・アイ
ケマイヤー他の米国特許出願第07/543458号（IBMドケッ
トEN9−90−042）。

（６）1991年１月16日出願の“Compounding Preprocess
or for Cache"と題するバーソロミュー・ブラナー他の
米国特許出願第07/642011号（IBMドケットEN9−90−04
9）。

（７）1991年３月29日出願の“System for Compounding
Instructions for an Instruction Processor With Di
fferent Attributes With Apparatus for Handling Tes
t and Data With Differing Reference Point Informat
ion and Backward Compounding Apparatus for Compoun
d Instructions"と題するリチャード・アイケマイヤー
他の米国特許出願第677066号（IBMドケットEN9−90−03
9）。

（８）1991年３月29日出願の“System for Preparing I
nstructions for Instruction Parallel Processor and
System with Mechanism for Branching in the Middle
of a Compound Instruction"と題するＳ・ヴァッシリ
アディス他の米国特許出願第677685号（IBMドケットEN9
−90−040）。

これらの同時係属出願および本願は、同一の譲受人、
すなわち米国ニューヨーク州アーモンクのインターナシ
ョナル・ビジネス・マシーンズ・コーポレーション（In
ternational Business Machines Corporation）が所有
する。

［技術分野］ 本発明は、演算論理機構（ALU）の分野に関し、「加
算／論理組合せ演算」を有する命令対を並列に実行す
る、新しい計算機編成に関する。「加算／論理組合せ演
算」とは、加算−加算、加算−論理、論理−加算、およ
び論理−論理機能という４つの組合せのすべてを組み合
わせることを意味する。本発明はまた、それぞれがALU
演算を指定する複数の別々の命令の並列発行に応答し、
命令を並列に実行する単一のALUによって、２つ以上の
分離されたALU演算が指定される計算機編成に関し、具
体的には、３−１演算論理機構またはALUの状況の予測
に関する。

［背景技術］ 従来のアーキテクチャは、RISC、IBMシステム/360、
システム/370等のシステムによって代表されるスカラー
型のものである。さらに、ウルフ（Wulf）他の米国特許
第4819155号明細書、およびオオタ（Oota）の米国特許
第485204号明細書に記載されているような装置がある。
W.A.ウルフの論文"The WM Computer Architecture",Com
puter Architecture News,1988年３月も参照されたい。
ウルフの装置は、スカラー処理ではなくてベクトル処理
用であるが、２つのオペランドを１つのALU内で組み合
わせて第１実行サイクルで結果を得、続いて、この結果
と第３のオペランドを第２のALUに供給して、第２実行
サイクルで結果を得ることが教示されている。この参考
文献は、既知のスーパースカラー計算機に類似したパイ
プライン方式を、性能向上の１つの方法として示唆して
いる。

パイプライン方式は、コンピュータ・システムの性能
を向上させるため、コンピュータ設計者によって使用さ
れる標準的な技法である。パイプライン方式では、１つ
の命令を複数のステップまたは段に分割し、それらに対
して独自のハードウェアを割り振って、その段に割り当
てられた機能を実施する。パイプラインを使用しない対
応する実施様態のサイクル・タイムをｍとすると、ｎ段
パイプライン実施様態のサイクル・タイムがm/nである
と仮定した場合、最適のパイプライン実施様態のサイク
ル・タイムはm/nとなる。もう１つの既知の技法がスー
パースカラーであるが、これを用いると、厳密に先入れ
先出しの原則に基づいてグループ化された命令が、同時
に発行できるようになる。スーパースカラー計算機は、
スケーラブル複合命令セット用には設計されなかった。
スケーラブル複合命令セットでは、元来一緒に記述する
必要のない関連する命令を、並列実行のため、複数セッ
トの単位命令として発行することができる。

命令の並列実行は、妥当なコストでプロセッサ性能を
改善するための一般的な技法になっている。基本命令の
並列実行が本発明によって達成されるにもかかわらず、
本発明では命令の並列実行自体を新規なものとは見なさ
ない。そうではなくて、本発明は、３−１加算器の状況
の予測に関する。上記の加算器は、命令を並列に処理す
るシステムで使用できる。

３−１加算器を実施することは既知である。これは、
３−２桁上げ保存加算器（CSA）と、それに続く２−１
桁上げ先見加算器（CLA）からなる。S.ヴァッシリアデ
ィスおよびM.プトリノ（Putrino）は、ALU内のクリティ
カル・パスが、結果がゼロに等しいとの判定によって、
通常は制限されることを知った。彼等は、論文"Conditi
on code predictor for fixed−point arithmetic unit
s",Int.J.Electronics,Vol.66,No.6,pp.887−890,1989
年で、２−１の２の補数加算器について結果がゼロに等
しいことを予測する方法を提案した。しかしながら、そ
の著者と本発明の共同発明者の１人が認める所では、そ
の方法は、３−１加算器には適用できない。

１つの既知の形態２−1CLAについての議論が、S.ヴァ
ッシリアディスの論文"Recursive Equations for Hardw
are Binary Adders",Int.J.Electronics,Vol.67,No.2,p
p.201−213,1989年に見られる。この論文は、ハードワ
イヤ式２進加算器について論じたものである。この論文
から、本発明の好ましい実施例で使用されるCLAの段を
記述するのに使用するブール式中のビット位置ｎでの擬
似生成と伝達を表わす既知の量▲G^x _n▼とT_nの定義を参
照することができる。本発明の理解を容易にするため、
これらについては、好ましい実施例の説明中で述べるブ
ール式およびブックセット中で正確に詳述する。以下の
説明では、１変数の真の論理値の生成だけを、段毎の遅
延の形で提示する。ただし、上記のブックセットは、現
在利用可能な技術に共通しており、そのブックセット内
に類似の特性または等価な機能能力を有する他の技術に
拡張できるので、これらの仮定は、この議論の適用可能
性を制限しようとするものではなく、また実際にも制限
していない。

関連発明の背景 インターナショナル・ビジネル・マシーンズ社から市
販されているシステム/370は、ある種のインターロック
式命令を並列に実行されるようにすることができ、参照
特許出願で最初に開示されたように、スケーラブル複合
命令セット計算機の用件を制限付きで実現することがで
き、たとえば米国特許出願第07/642011号（IBMドケット
EN9−90−049）など他の特許出願で、スケーラブル複合
命令セット計算機用の他のALUとして使用できる可能性
などの提案がなされている。これらの既存のプロセッサ
は、このようなものとして広く使用されてきたわけでは
なく、このような使用の可能性に関する刊行物も存在し
ていないが、本明細書で優先権が主張された後に出願さ
れた特許出願中で、いくつかの態様でこの可能性が述べ
られている。

さらに、背景として、最初のインターロック解消ALU
は、1990年４月４日出願の"Data Dependency Collapsin
g Ilardware Apparatus"と題するスタマティス・ヴァッ
シリアディス他の米国特許出願第07/504910号（IBMドケ
ットEN9−90−014）および1990年11月28日出願の"Overf
low Determination for Three−Operand ALUs in a Sca
lable Compound Instruction Set Machine"と題するス
タマティス・ヴァッシリアディス他の米国特許出願第07
/619868号（IBMドケットEN9−91−033）に記載されてい
る。本出願は、これらの発明から優先権を主張する。本
発明の目的は、演算論理機構（ALU）用の新装置と、加
算−加算、加算−論理、論理−加算および論理−論理機
能という４つの組合せのすべてを組み合わせることを意
味する「加算／論理組合せ演算」を有する命令を定義す
るアーキテクチャと共に実施できる装置を提供するこ
と、およびそれぞれがALU演算を指定する複数の別々の
命令の並列発行に応答し、命令を並列に実行する単一の
インターロック解消ALUによって、２つ以上の分離され
たALU演算が指定されるアーキテクチャを提供すること
である。したがって、本発明が提供する特徴として、複
数の別々のオペランドが、同一の実行サイクル中に実行
ユニット（ALU）に渡され、また、これらを第３のオペ
ランドと共に実行ユニットに渡すこともできる。単一の
実行サイクルの終りに、２つの結果が生成され、使用可
能になる。一方の結果は、第1ALUによって生成すること
ができ、もう一方の結果は、第2ALUによって生成するこ
とができる。

したがって、データ依存性解消ハードウェア装置に
は、大まかにいって、第１の命令が結果を生成しそれを
第２の命令が使用するような複数のスカラー命令を受け
取る命令装置があり、少なくともそのうちの２つが第１
と第２のスカラー命令によって使用されるような複数の
オペランドを同時に発行する装置があり、実行ユニット
は、複数のスカラー命令を実行する動作を指示する制御
信号の下で、単一のサイクル中に、オペランド群に基づ
く動作群の実行に対応する単一の結果を生成する。（こ
のような装置の提案の詳細については、上記に参照し
た、米国特許出願第07/504910号を参照されたい。） SCISMアーキテクチャは、370アーキテクチャのみなら
ず、RISCを含む他のアーキテクチャにも適用可能であ
る。この場合、あるALUに対して指定された複数の命令
が並列に発行され実行される場合に、望ましくはより高
速で動作する開発済みのアプリケーションの性能を向上
させることが望ましい。上記のシステムによって、新規
のハードウェアが、旧来の命令をより高速で実行できる
ようになり、新規のアーキテクチャを有する新規の計算
機用に旧来のプログラムをプログラミングし直す必要が
少なくなる。

本明細書の開示対象である装置は、命令の並列実行に
適用でき、関連発明の環境で特に有利であり、スケーラ
ブル複合命令セット計算機アーキテクチャ（以下ではSC
ISMアーキテクチャと称する）など、複数の命令を並列
に発行し実行するアーキテクチャにとって特に有利であ
る。

命令の並列実行によって得られるスピードアップは、
一部にはインターロックとも称するデータ依存性が原因
で、理想値を下回っていた。このインターロックに起因
する性能低下を減少させるために、インターロック解消
ALUが、前述の米国特許出願第07/504910号で提供され、
すべての「加算／論理組合せ演算」を処理する装置が、
高性能インターロック解消ALU装置に関する上記の特許
出願で開示された。インターロック解消ALUは、インタ
ーロックを有する命令対の第１の命令が従来のALUで実
行されると同時に、両方の命令がインターロック解消AL
U内で同時に実行されるという形で、従来の２−1ALUと
共に使用される。命令対がインターロックを有さない場
合には、従来のALUが第１の命令を実行すると同時に、
インターロック解消ALUが第２の命令だけを実行する。

ALUは、正しい結果を生じるのみならず、状況を正確
に報告しなければならない。この状況としては、負の結
果、正の結果、ゼロに等しい結果、およびオーバーフロ
ーを含めることができる。インターロック解消ALUで
は、この状況は、上記の1990年11月28日出願の米国特許
出願第07/619868号に示されるように、第１の命令の結
果を使用して第２の命令が単独に実行される場合と同様
に報告しなければならない。ALU状況は、最上位ビット
（MSB）へのまたはそこからの桁上げが既知で、結果が
ゼロに等しいと判定できる場合に決定できる。ゼロに等
しい結果の判定は、その結果を予測する方法が見つから
ない場合、最悪でも結果から行なうことができる。演算
が正しい場合、インターロック解消ALUから得られた結
果は、逐次式実施態様を介して得られる結果と同じにな
るので、この方法を用いたゼロに等しい結果の生成は、
正確である。したがって、インターロック解消ALU内でA
LU状況を生成するという問題は、第２の命令の実行に起
因するMSBへの桁上げまたはそのMSBからの桁上げを抽出
するという問題に還元することができる。これらの桁上
げは、インターロック解消ALUの実行中に明示的に作成
されるものではないので、インターロックを有する命令
対の同時実行中に生成される情報から抽出しなければな
らない。３−１加減演算中にこれらの桁上げを抽出する
ためのアルゴリズムも、上記の1990年11月28日に出願さ
れた米国特許出願第07/619868号に示されている。３−
１加減演算は、２つの算術命令間のインターロックを解
消することから生じる。そのアルゴリズムを以下に示
す。

c₀＝κ₀∀λ₀∀φ₀ c₁＝κ₁∀λ₁∀φ₁ 上式で、c₀とc₁は、第２の演算から生じたMSBからの
桁上げまたはそのMSBへの桁上げを表わし、κ₀とκ
₁は、第１の命令の実行中に作成された桁上げを表わ
し、λ₀とλ₁は、桁上げ保存加算器CSAで生成された桁
上げを表わし、φ₀とφ₁は、３−１加算器に使用される
桁上げ先見加算器CLAで生成された桁上げを表わす。式
中、∀は、ビットごとの排他的論理和演算を表わす。し
たがって、第１の関数カテゴリーを実行する際にc₀とc₁
を抽出するための、実施可能なアルゴリズムが既知であ
る。

上記の我々自身の成果は、下記の領域で改良すること
ができる。

1.本システムは、３−1ALUで実行する必要のあるすべて
の関数カテゴリーに適用可能にすることができる。

2.本システムは、適用可能なカテゴリーでも、サイクル
・タイムを延長しないクリティカル・パスを作成する。

3.追加の要素と機能を設けて、これまでには処理されな
かった、ALUの制御に必要な複雑なことをすべて処理す
ることができる。

ただし、関数カテゴリーとは、下記を意味する。

Ａ＋Ｂ＋Γ 算術演算とそれに続く算術演算 Ｂ＋（A LOP Γ） 論理演算とそれに続く算術演算 B LOP（Ａ＋Γ） 算術演算とそれに続く論理演算 B LOP（A LOP Γ） 論理演算とそれに続く論理演算 従来の研究では、算術演算に続いて算術演算のカテゴ
リーしか考察していない。

［発明の開示］ 本明細書では、すべての関数カテゴリーを含む桁上げ
抽出を提示する。また、３−1ALU演算のオーバーフロー
を予測する手段を提供する。算術演算とその後に続く算
術演算と、論理演算とその後に続く算術演算のカテゴリ
ー用の、ゼロに等しい結果を予測するハードウェアを提
示する。高速３−1ALUと比較すると、ここに提案する装
置はクリティカル・パスを構成しないことを証明する。
２つの実施カテゴリーに分類される３種の高速３−1ALU
に関する並列状況判定を提供する。

本発明者等の各発明の好ましい実施例の実施様態を、
以下の詳細な説明で詳述する。本発明ならびにその長所
および特徴をよりよく理解するため、より詳細な背景に
ついて、関連発明の明細書を参照されたい。さらに、特
に本明細書に記載の改良に関しては、下記の説明と添付
の図面を参照されたい。

［図面の簡単な説明］ 第１図は、３−1ALUと並列状況予測機構を示す図であ
る。

第２図は、並列状況予測のための桁上げの並列抽出を
示す図である（第１実施例）。

第３図は、並列状況予測のための桁上げの並列抽出を
示す図である（第２実施例）。

第４図は、並列状況予測のためのオーバーフローの並
列抽出を示す図である（第１実施例）。

第５図は、並列状況予測のためのオーバーフローの並
列抽出を示す図である（第２実施例）。

第６図は、並列状況予測のためのゼロに等しい結果の
並列抽出を示す図である（全実施例）。

［発明の好ましい実施例］ 並列状況判定の実施例の実現可能性を証明するために
は、クリティカル・パスの比較を行なうための基礎とし
て高速ALU実施様態を仮定しなければならない。我々
は、既知の最高速の３−1ALU実施様態、すなわち、本発
明と同時に出願され、上記の参照によって本明細書に合
体された米国特許出願第07/677079号（IBMドケットEN9
−91−005）に開示される装置によって実現されるALU実
施様態を仮定する。本発明を説明する際、それぞれが方
式として公知になっている可能性のある、本発明者等の
様々な発明の好ましい実施例の実施様態を実現する方程
式の開示によって、本発明を例示する。

第１の実施方式の桁上げ抽出 この実施方式では、ビット位置ｉのCSAからの桁上げ
を次式で表わす。

λ_i＝α_iβ_i＋α_iγ_i＋β_iγ_i 上式で、α_i、β_i、γ_iは、それぞれALUの入力、A_i、
B_i、Γ_iに対応するCSAへの入力を表わす。式中、＋は、
ビットごとの論理和（OR）を表わし、項の隣接は、ビッ
トごとの論理積（AND）を表わす。入力ＡおよびΓは、
第１の命令用のオペランドを含み、入力Ｂは、第２のイ
ンターロックを有する命令用の独立したオペランドを含
む。CSAへの入力はいずれも、第１図に示すように、強
制的に０にされるか、あるいは対応する入力を供給され
る。

まず、３−１加算について検討する。この場合、CSA
桁上げは、 λ_i＝A_iB_i＋A_iΓ_i＋B_iΓ_i すなわち、上記の桁上げ抽出アルゴリズムで望まれる、
３−１加算に適したCSA桁上げである。さらに、第１の
命令に起因するビット位置ｉの桁上げは、CSA入力α_iお
よびγ_iから生成することができる。CLA技法を使用する
と、下記のように、このビット位置０および１の桁上げ
κ₀およびκ₁は、仮定されたブックセットを使用して次
のように３段で生成できる。

上式で、▲G^*m _n▼、▲T^m _n▼、▲φ^m _n▼は、それぞれビ
ット位置ｍからビット位置ｎへの、擬似伝播、伝達、新
桁上げを表わし、▲G^* _n▼およびTnは、それぞれビット
位置ｎでの擬似生成と伝達を表わす。これらの数量の定
義は、上記のInt.J.Elec.Vol.67,No.2に見られる。ま
た、τ₂は、第１命令の実行中に供給されたホット・ワ
ンを表わす。３−１加減演算で有効な結果を得るため
の、十分要件ではあるが多分必要要件ではない、τ₂に
関する１組の要件が、上記の1990年11月28日に出願され
た米国特許出願第07/619868号に示されている。この要
件を要約すると、次の通りである。

（１）３−1ALUに２個のホット・ワンが供給される場
合、τ₂＝１である。

（２）３−1ALUにホット・ワンが供給されない場合は、
τ₂＝０である。

（３）論理演算の結果と第３のオペランドを加減算する
場合は、τ₂＝０である。

上記の論理式によれば、第２の関数カテゴリーを実行
する時には、κ₀とκ₁が共に０になる。この結果が生ず
るのは、この関数カテゴリーの実行時にαとγが共に強
制的に０にされるからであるあ。αとγが共に０である
と、擬似生成と伝達のすべてが０になる。さらに、τ₂
が０であるので、新桁上げφ_iもすべて０になる。した
がって、κ₀とκ₁の式の文字項のすべてが０になり、こ
の式の結果も０になる。κ₀とκ₁が共に０であり、上述
したようにλ₀とλ₁が共に０であるので、桁上げc₀およ
びc₁を抽出するアルゴリズムは、 c₀＝０∀０∀φ₀＝φ₀ c₁＝０∀０∀φ₁＝φ₁ となる。したがって、抽出された桁上げは、望まれるCL
Aからの桁上げと等しくなる。

複合命令対の第２の命令から生じた桁上げを抽出する
必要があるのは、［背景技術］の項で、特に上記の米国
特許出願第07/619868号に関して論じた関数カテゴリー
のうち最初の２つの場合だけである。

κ₀とκ₁を生成するための段ごとの実施様態は、上記
の通りである。この実施様態に、λ₀、λ₁、φ₀、φ₁を
導き、最終的にC₀とc₁を導く式を追加して、C₀とc₁を生
成する実施様態を完成しなければならない。第１の実施
方式の段ごとの説明を以下で行なう。この説明では、κ
₀とκ₁を生成するための擬似生成と伝達には、下付き文
字cc（桁上げ補正）を付けて、φ₀とφ₁を生成する３−
１加算／減算で使用されるCLAの擬似生成と伝達から区
別する。各段の式を以下に示す。

c₀の計算を除く上記のすべての式は、第２の命令に起
因する桁上げを抽出するアルゴリズムを直接適用する
か、あるいは上記Int.J.Elec.Vol.67,No.2に記載のハー
ドワイヤ式２進加算器用の帰納式から得られたものであ
る。c₀を求める式は、次のように導かれる。

ところが、φ₀は、次のように表わすことができる。

φ₀＝T₀Φ₀ 下記のΦ₀の式 をφ₀の式に代入すると、次式が得られる。

T₁Φ₁はφ₁であるので、φ₀は、次式で表わせる。

c₀を生成する式にこのφ₀の式を代入すると、次式が得
られる。

上記の式を排他的論理和の標準的な積和に展開すると、
次式が得られる。

ところが、T₀G^* ₀は、次式のように変形できるので、 これをc₀の式に代入すると、次式が得られる。

これが、５段の実施様態で使用される式である。したが
って、c₀とc₁は共に、この実施方式に対して仮定したブ
ックセットを用いて５段で生成することができる。第１
の実施方式のc₀とc₁の生成の論理図を第２図に示す。

第２の実施方式の桁上げ抽出 桁上げ抽出アルゴリズムを第２の方式に適用してSCIS
M ALUを実施しようとすると、複雑になる。この複雑さ
が生じるのは、３−１加算が望まれない時にλ_iとκ_iが
論理０になる保証がないためである。たとえば、この実
施様態のCSA桁上げは、上記米国特許出願第07/504910号
によって、次のように計算される。

λ₀＝Ω₁α₀β₀＋Ω₂α₀γ₀＋Ω₁β₀γ₀ λ_i＝Ω₁α_iβ_i＋Ω₂α_iβ_i＋Ω₁β_iγ_i＋Ω₃β_i-1１
ｉ31 λ₃₂＝Ω₃β₃₁＋₃τ₂ この実施様態で第２の関数カテゴリーを実行するに
は、１≦ｉ≦32のときにλ_iがB_i-1に等しくなることが
必要である。これは、Ω₁、Ω₂、τ₂を論理０にすると
同時にΩ₃を論理１にすることによって達成できる。し
たがって、λ₁は、ALU入力の値B_i-1をとる。その結果、
１≦ｉ≦32の場合にλ_iが論理０になることは保証でき
ない。同様に、第１の命令に対応するオペランドは強制
的に論理０にされないので、κ_iが論理０になることは
保証できない。これらの結果から、桁上げ抽出アルゴリ
ズムの実施様態に制御信号を追加して、λ_iとκ_iが論理
０であるかのように所望の桁上げを抽出するが、３−１
加減算に起因する桁上げを抽出する時には、λ_iとκ
_iを、それが生成された状況で使用できるようにしなけ
ればならない。

利用されない時にλ_iが論理０でないことに起因する
複雑さは、実行中の演算が３−１加減算であることを示
す制御信号によってゲートされる、従来型のCSA桁上げ
を作成することによって克服できる。この信号は、ビッ
ト位置０および１に生成される桁上げだけを制御しなけ
ればならない。というのは、これらのビット位置だけ
が、ALU状況を生成するために第２の命令に起因する桁
上げを抽出する必要のある位置であるからである。この
追加の桁上げ信号、λ_CC0およびλ_CC1は、次のように生
成される。

λ_CC0＝Ω_3to1α₀β₀＋Ω_3to1α₀γ₀＋Ω_3to1β₀γ₀ λ_CC1＝Ω_3to1α₁β₁＋Ω_3to1α₁γ₁＋Ω_3to1β₁γ₁ 上式で、Ω_3to1は、制御信号であり、３−１加減算を
実行中の場合は論理１になる。これらの余分の桁上げ信
号は、３−１加減算を実行中の時はCSA桁上げになり、
それ以外の時は論理０になるという望ましい性質をも
つ。したがって、c₀とc₁を抽出する時、これらの信号を
桁上げ抽出アルゴリズムのλ₀とλ₁に代入することがで
きる。

利用されない時にκ₁が論理０でないことに起因する
複雑さは、κ₀とκ₁の生成の第３段を検討することによ
って克服できる。この段では、これらの値は次式から得
られる。

κ₁の式は、2x4 AOブックによって、仮定されたブッ
クセット内で直接に実施されるので、３−１加減演算を
実行中であることを示すゲート制御信号を直接に印加す
ることができ、これによって3x4 AOブックがもたらさ
れる。したって、κ₁は、次式から求めることができ
る。

この信号は、３−１加減演算が指定されない時は０で
あり、３−１加減演算が指定される時は、第１の命令の
実行中にMSBに持ち込まれる桁上げであるという望まし
い性質をもつ。κ₀を生成する式は、既に3x4 AOブック
を必要としているので、この式を一見すると、同様の手
法を使用しても無駄に思われる。しかし、第１段で生成
できる文字項T₀の式は、次の通りである。

T₀＝α₀＋γ₀ この式は、ゲート信号を加えると2x2 AOブックが得
られる２入力ORブックを必要とする。したがって、ゲー
トされたT₀（これをT^* ₀と表記する）を第１段で生成
し、第３段のκ₀を生成する式のT₀に代入することがで
きる。その結果は次のようになる。

この形で生成されるκ₀とκ₁はどちらも、３−１加減算
の実行時には第１の命令の実行に起因する桁上げとなる
が、それ以外の時には論理０となるという望ましい性質
をもつ。

上記の結果から、次式からc₀とc₁を求めることができ
る。

c₀＝κ₀∀λ_CC0∀φ₀ c₁＝κ₁∀λ_CC1∀φ₁ ただし、κ₀とκ₁は、上記に従って生成される。この技
法では、ALUに対するホット・ワンの供給に対して、追
加の制限はない。

c₀とc₁は共に、この実施方式の５つの段で生成するこ
とができる。したがって、この実施様態からは、追加の
遅延が発生しない。次に、桁上げ抽出を段ごとに説明す
る。第１の実施方式の説明と同様に、κ₀とκ₁の生成に
関連する擬似生成と伝達には、下付き文字ccを付けて、
３−１加算の実行用のものと区別した。段ごとの実施様
態は次の通りである。

第２の命令から桁上げを抽出する上記の実施様態の式
は、第２段で発生する、３つのビット位置にまたがって
生成される伝達▲Tⁱ⁺² _i▼を除き、すべて、仮定された
ブックセットを用いて実施できる。この伝達は、第４段
でφ₁を作成するのに必要である。第４段のφ₁は、第５
段でc₀とc₁を決定するのに使用される。この伝達の生成
を避けたい場合は、φ₁を明示的に生成することなし
に、c₀とc₁を生成しなければならない。

φ₁を明示的に生成することなしにc₀とc₁を生成する
には、帰納式を用いてφ₁を展開しなければならない。
この展開は、次式で示される。

この式を段５段のc₀とc₁の式のφ₁に代入すると、次式
が得られる。

このc₁の式は、標準的なブール代数の技法を使用して、
下記のように展開することができる。

第４段で、 を生成できる場合には、仮定されたブックセットを使用
して、第５段でこのc₁の式を生成することができる。

次に、c₀の式を検討する。この式は、標準的なブール
代数の技法を使用して、次のように展開することができ
る。

c₁の生成に必要な値のほかに下記の値が第４段で生成さ
れる場合には、この最後の式を使用して、仮定されたブ
ックセットを用いて、第５段でc₀を生成することができ
る。

上記の信号がこの実施様態の第４段で生成できるか否
かを判定するには、式▲Φ^y _x+1▼および▲G^** ₁▼のｘと
ｙとの値を求めなければならない。これらの値は、仮定
されたブックセットを用いて、３つの段にまたがること
のできる新しい桁上げ▲Φ^m _n▼のビット位置の数によっ
て決定される。２進加算器用の帰納式を適用することに
よって、仮定されたブックセットでまたがることのでき
るビット位置の数は、次のようになる。

第１段 上記に従って、CSAと論理機能ブロックに関する結果を
生成する。

上記から、ｘは８、ｙは26と決定できる。第４段で生
成しなければならない式にこれらの値を代入することに
よって、仮定されたブックセットを用いて５つの段でc₀
とc₁を生成するための必要条件が与えられる。この必要
条件は、第４段で、 を生成すること、および▲Φ²⁶ ₉▼を生成することであ
る。▲Φ²⁶ ₉▼は、上記の第４段で生成できる。残りの
式も、以下のようにして第４段で生成できる。

第１段 上記に従って、CSAと論理機能ブロックに関する結果
を生成する。

上記の考察から、５つの段でc₁とc₁を生成するための
段ごとの実施様態は、次のようになる。

第２の実施方式のc₀とc₁を生成するための論理図を第３
図に示す。

オーバーフローの生成 前節では、インターロックを有する命令対の第２の命
令だけの実行に起因する桁上げを抽出するための実施様
態を、２つのALU実施方式について提示した。MSBへの桁
上げまたはMSBからの桁上げが、仮定されたブックセッ
トを使用して５段で計算可能であることが示された。算
術オーバーフローは、２の補数の加算の場合、MSBへの
桁上げとMSBからの桁上げの排他的論理和によって決定
できることがよく知られている。したがって、第２の命
令の実行のみに起因するオーバーフローは、c₀とc₁の排
他的論理和から作成できる。この手法を使用すると、c₀
とc₁が５つの段で生成されるので、仮定されたブックセ
ットの６つの段でオーバーフローを生成することができ
る。これは、ALUのクリティカル・パスをもたらすはず
である。本節では、オーバーフローの早期生成を追求す
る。まず、２つの実施方式の両方に共通する論理式の展
開を提示する。次に、仮定されたブックセットに対する
実施様態を提示して、第１の実施方式について検討す
る。最後に、第２のALU実施方式の実施様態を展開す
る。

前節で説明した信号から次式によって、オーバーフロ
ーを明示的に計算することができる。

OF＝κ₀∀κ₁∀λ_cc0∀λ_cc1∀φ₀∀φ₁ ２進加算器の２つの桁上げ、θ₀およびθ₁の排他的論
理和は、従来型のCLAを使用すると、次のようになる。

κ₀とκ₁は、暗示的な従来型のCLAによって導かれるの
で、上記の結果がこれらの排他的論理和に直接に適用で
きる。ところが、φ₀とφ₁を生じるCLAへの入力は変更
されているので、上記の結果はこれらの排他的論理和に
は直接に適用できない。したがって、κ₀∀κ₁は、次の
ように表わせる。

しかし、φ₀∀φ₁を表わすには、より一般的な式を使用
しなければならない。この式を展開するには、φ₁を使
ってφ₀を表わす必要がある。

と仮定する（上記Int.J.Elec.Vol.67,No.2による）。こ
の排他的論理和を標準的な積和に展開すると、次式が得
られる。

これらの式をさらに展開してオーバーフローの式を導
く際には、ALU実施様態が問題となる。というのは、λ
_cc0、λ_cc1、T₀および▲G^* ₀▼の式が、２つの実施方式
で異なるからである。これらの各方式でオーバーフロー
の式を、以下に展開する。これらの式を導く前に、その
導出に有用な次の定理を証明する。

定理１ ａ、ｂ、ｃおよびｄがブール変数であるなら
ば、（ｄ＋ab）∀ｃ＝（＋ab）ｄ∀（ｃ＋
ｃ＋ab）である。

第１の実施例方式のオーバーフロー生成 この実施方式では、λ_cc0がλ₀と等価である。したが
って、次式が成立する。

この結果をオーバーフローの式に代入すると、次式が得
られる。

次に、φ₀∀φ₁を検討する。上記の展開から、これを
次のように表わすことができる。

この実施方式でのCLAへの入力は変更されており、その
結果、一方の入力には、CSAからの桁上げと、そこから
適当な信号を選択しなければならない論理機能ブロック
の出力が供給され、他方の入力には和が供給されるの
で、T₀と▲G^* ₀▼式は、従来型のCLAの場合の式とは異な
ってくる。この実施例のビット位置０での信号を表わす
式は、次の通りである。

これらの式をφ₀∀φ₁の式に代入すると、次式が得られ
る。

λ_cc1はλ₁と等しいので、φ₀∀φ₁∀λ_cc1は次のよう
に表わすことができる。

したがって、定理１により、 この式をオーバーフローを生成する式に代入すると、次
式が得られる。

オーバーフローをこの形で表わすと、これを５つの段
で計算できるようになる。この計算は、次のように段ご
とに進行する。

第１の実施例のオーバーフロー計算の論理図を第４図に
示す。図を簡単にするために、κ₁とφ₁を生成する式
を、段ごとの説明の中の適当な段に示し、その前段階の
生成は省略した。これらの値の段ごとの生成の詳細は、
「第１の実施方式の桁上げ抽出」の節にある。

第２の実施方式のオーバーフロー生成 第２の実施方式では、λ_cc0とλ_cc1を、λ₀とλ₁を使
って、次のように表わすことができる。

λ_cc0＝Ω_3to1λ₀ λ_cc1＝Ω_3to1λ₁ さらに、第１の演算から生じた桁上げκ₀およびκ₁は、
３−１加算を実行中であることを示す信号を用いて、対
応する式をゲートすることによって生成される。ゲート
されない信号を▲κ⁺ ₀▼と▲κ⁺ ₁▼で表わすものとする
と、κ₀およびκ₁は、次のように表わせる。

この表記法を使用すると、オーバーフローは次のように
表わせる。

ところが、 AB∀AD＝Ａ（Ｂ∀Ｄ） であるので、次式が成立する。

κ₀∀κ₁∀λ₀の式を利用し、仮定された用語を使用す
ると、次のように表わせる。

したがって、次式が得られる。

次に、式φ₀∀φ₁を検討する。これは、上記から次のよ
うに表わせる。

第１の実施方式の場合と同様に、この実施例でもCLA
への入力が変更されているので、ビット位置０での擬似
生成と伝達が、従来型のCLAのそれと異なってくる。こ
れらの値の式は、上記のスタマティス・ヴァッシリアデ
ィス他の米国特許出願第677079号から次のようになる。

ただし、Ω₄は、指定された機能を実行するのにCSAから
の和が不要である時に、この和を０にする制御信号であ
る。これをφ₀∀φ₁の式に代入すると、次式が得られ
る。

したって、φ₀∀φ₁∀λ_cc1は次のように表わすことが
できる。

ここで、 ν＝Ω₄σ₀＋L₀ と置くと、定理１により次式が成立し、 したがって、次式が成立する。

これをオーバーフローの式に代入すると、次式が得られ
る。

「第２の実施方式の桁上げ抽出」の節では、この実施
方式に対して仮定されたブックセットを用いて、φ₁を
４段で生成できないことが示された。したがって、オー
バーフローを５段で実施しようとする場合には、φ₁を
明示的に計算することなしにこれを実施しなければなら
ない。また「第２の実施方式の桁上げ抽出」では、第５
段で使用できるφ₁の式は、次のようであった。

とりあえず、 が第４段で生成できるものと仮定し、この値を、X₈で表
わす。さらに、 が第４段で生成できるものと仮定し、これをX_dで表わ
す。これらの仮定が真であることを、以下の段ごとの実
施様態で示す。これらの仮定によれば、OFは次のように
計算することができる。

X_dを分配すると、次のようになる。

次に、 と置くと、次式が得られる。

この式は、排他的論理和を分配し、ブール等式を適用す
ることによって、次のように展開することができる。

この式は、第４段で が生成できるならば、第５段で実施できる。他の値が第
４段で実施できることは、「第２の実施方式の桁上げ抽
出」で示した。

まず、X₆の生成について検討する。これは、次式で表
わせる。

ただし、νは、次の通りである。

ν＝Ω₄σ₀＋L₀ Ω₄は、ALUへの制御信号入力であり、σ₀とL₀は、共にA
LUの第１段で計算されるので、第２段でνが計算でき
る。また、T₁ならびにλ₁は、第２段で計算可能である
ことを既に示した。したがって、X₆は、次式によって第
３段で計算することができる。

X₉はX₆▲T⁹ ₂▼であり、X₆と▲T⁹ ₂▼が第３段で計算され
るので、第４段で計算可能である。

次に、 の生成について検討する。▲G^*8 ₁▼の生成については、
既に論じた。この結果を利用し、 をX₁₀で表わすと、次式が得られる。

この式に含まれる値はすべて、３段で計算可能であるこ
とを既に示した。したがって、X₁₀は、第４段で計算可
能である。

OFが５段で生成できることを示すためには、さらに、
X₈が４段で生成できることを示さなければならない。４
段でのX₈の生成は、次の通りである。

上記の提示のうち、第３段で行なわれるκ₁の計算は、
その方法を既に示したので、省略した。上記の値を用い
ると、OFを、第５段で次のように計算することができ
る。

第２の実施方式のオーバーフロー生成の論理図を第５図
に示す。

ゼロに等しい結果の判定 ゼロに等しい結果の検出は、２つの部分からなる。第
１の部分では、０≦ｉ≦31に対するALU出力Λ_iが、すべ
てのｉについて０であることを実際に判定する。この判
定結果を、R₌₀と表記する。第２の部分は、オーバーフ
ロー条件を考慮するためのR₌₀の検定である。R₌₀の検出
方法は、両方の命令がALU演算を指定し第２の命令が論
理演算を指定する、２つの命令の間のインターロックの
解消をALUがサポートするか否かによって変わる。上記
のインターロックの解消がサポートされる場合、すなわ
ちケース１では、R₌₀の検出は、その結果から直接行な
われる。上記のインターロックの解消がサポートされな
い場合、すなわちケース２では、R₌₀を予測して、R₌₀の
判定を実行サイクルの早期に行なうことができる。

ケース１の場合、R₌₀の判定は、ALUからの結果Λ_iに
直接基づいて行なわれる。この出力が、５段で得られる
ことは既に示した（上記米国特許出願第07/504910
号）。この結果は、結果のすべてのビットが０である場
合に、０である。これは、 すなわち、反転されたすべてのALU出力ビットの32入力
論理積として表わせる。この式は、８入力ANDゲートと
それに続く４入力ANDゲートを用いて、２段で実施でき
る。また、R₌₀を次のように表わすこともできる。

R₌₀をこの形で表わすと、８入力ORゲートとそれに続く
４入力ANDゲートによってこれを生成することができ、
結果Λ_iの１の補数を生成する必要がなくなる。どちら
の場合でも、結果が５段で生成されるので、R₌₀は仮定
されたブックセットを用いて７段で生成できる。

上述したように、特定のインターロックの解消がALU
でサポートされていない場合には、R₌₀の検出を予測す
ることができる。３−1ALUについてのこのような予測方
式の論理式の展開を以下に示す。

ALUで必要な関数は、４つのカテゴリーに分けられる
（上記米国特許出願第07/504910号、および同第677079
号を参照されたい）。このカテゴリーは、次の通りであ
る。

Ａ＋Ｂ＋Γ 算術演算とそれに続く算術演算 Ｂ＋（A LOP Γ） 論理演算とそれに続く算術演算 B LOP （Ａ＋Γ） 算術演算とそれに続く論理演算 B LOP （A LOP Γ） 論理演算とそれに続く論理演算 これらのうち、３番目と４番目の２つのカテゴリー
は、両方の命令がALU演算を指定し、第２の命令が論理
演算を指定する２つの命令の間のインターロックが解消
される時に発生する。これらのカテゴリーでは、加算器
の出力が、論理演算によって変更される。これらの条件
で、R₌₀を早期に生成する方法は知られていない。した
がって、R₌₀の早期の生成が望まれる場合には、これら
の関数が発生する命令シーケンス間のインターロックの
解消をALUによってサポートすることができない。これ
らの命令シーケンスは、順次発行し実行しなければなら
ない。従って、R₌₀の早期の生成を検討する際には、上
記リストの最初の２つのカテゴリーに含まれる関数につ
いて検討するだけで十分である。以下では、まず、早期
予測方式を、３−１加算が実行される第１のカテゴリー
に適用する。次に、上記リストに含まれる第２のカテゴ
リーもカバーされるように、これらの結果を拡張する。

第１のカテゴリーに含まれる３−１加算には、２つの
オペランドの加算と第３オペランドの減算、２つのオペ
ランドの第３オペランドからの減算、ならびに３つのオ
ペランドの加算が含まれる。これらの関数は、次のよう
に表わせる。

Ａ＋Ｂ＋Γ Ａ＋Ｂ−Γ Ａ−Ｂ＋Γ Ａ−Ｂ−Γ 上式で、＋は加算、−は減算を表わし、Ａ、Ｂ、および
Γは、３つのオペランドである。各オペランドを２の補
数として表わすことによって、これらの関数を次のよう
に書き直すことができる。

Ａ＋Ｂ＋Γ Ａ＋Ｂ＋（＋１） Ａ＋（＋１）＋Γ Ａ＋（＋１）＋（＋１） または Ａ＋Ｂ＋Γ Ａ＋Ｂ＋＋１ Ａ＋＋１＋Γ Ａ＋＋１＋＋１ 表記B^*を使って、行なおうとする演算の必要に応じて
オペランドまたはそのオペランドの１の補数を表わすこ
とにより、これらの関数を次のように表わすことができ
る。

Ａ＋B^*＋Γ^*＋τ₂＋τ₁ ただし、τ₂とτ₁は、演算の必要に応じて０または１に
なる。加法の同一性により、この式は次式と等価であ
る。

Ａ＋B^*＋Γ^*＋τ₂−１＋τ₁＋１ この式の最初の３項、 Ａ＋B^*＋Γ^* は、次のように表わされる３−２加算と見なすことがで
きる。

τ₂は、１または０であるので、次のように表わせる。

00…τ₂ したがって、桁上げλは、和σに加算される前に、１ビ
ット左にシフトされるので、次のようにτ₂を桁上げに
加算することができる。

λ₀λ₁…λ₃₁ ０…０ τ₂ λ₀λ₁…λ₃₁τ₂ この結果を使用すると、式Ａ＋B^*＋Γ^*＋τ₂を、次のよ
うに生成することができる。

２の補数表現では、−１は次のように１の列として表
わされる。

11…１ したがって、Ａ＋B^*＋Γ^*＋τ₂−１は、次のように１連
の２つの３−２加算として表わすことができる。

これによって、２つの変数P_xおよびP_yが得られる。τ₁
の２の補数表現は、 00…τ₁ であるので、Ａ＋B^*＋Γ^*＋τ₂−１＋τ₁は、P_x＋P_y＋
τ₁によって計算できる。P_yとτ₁は、λとτ₂を加算し
たのと同様に加算できるので、次式が得られる。P_y0P_y1…P_y31 ０…０ τ₁ P_y0P_y1…P_y31τ₁ したがって、この３−１加算の最終的な結果は、P_xと
（P_y＋τ₁）の２−１加算によって得られる。この加算
は、次のように表わせる。

P_x0P_x1…P_x31 P_y0P_y1P_y2…τ₁ Ｘ S₀ S₁…S₃₁ ただし、Ｓは、演算Ａ＋B^*＋Γ^*＋τ₂＋τ₁−１の最終
結果である。この２−１加算では、１がキャリー・イン
として供給される。最終的な結果が０になるのは、すべ
ての０≦ｉ≦31についてS_iが０の場合である。

上記の最終結果Ａ＋B^*＋Γ^*＋τ₂＋τ₁＋１−１の生
成を要約すると、次の通りである。

σ₀σ₁……σ₃₁ λ₀λ₁λ₂……τ₂ 1 1 1……１ P_x0P_x1…P_x30P_x31 P_y0P_y1P_y2…P_y31τ₁ ０ ０ ０ …０ １ Ｘ S₀S₁…S₃₀S₃₁ ３−１加算を上記の形で表現することの利点は、以下の
説明から明らかになるはずである。

上記の表記の利点は、次の定理から生ずる。説明を簡
単にするため、P_y32＝τ₁と置き、P_x0P_x1…P_x31をP_xで
表わし、P_y1P_y2…P_y31P_y32をP_yで表わす。

定理1:S_i＝０ならば、すべての０≦ｉ≦31について、
P_x、P_yおよび１の加算によって生成される位置ｉでの桁
上げφ_iは、１に等しい。

証明： 定理１は、帰納法によって証明できる。

帰納法の底 ビット位置31の和の式は、次の通りである。

S₃₁＝０と仮定すると、 したがって、次式が成立する。

P_x31∀P_y32＝１ ビット位置31で生じる桁上げφ₃₁は、次のようになる。

φ₃₁＝P_x31P_y32＋P_x31（１）＋P_y32（１） ただし、＋は論理和を表わす。これを整理すると、次式
が得られる。

φ₃₁＝P_x31＋P_y32 S₃₁＝０ならば、次式が成立し、 P_x31∀P_y32＝１ また、この排他的論理和は、P_x31またはP_y32のうちの一
方だけが１の場合に１になるので、次式が成立する。

P_x31＋P_y32＝１ したがって、次のようになる。

φ₃₁＝１ 従って、ビット31からビット30への桁上げは、ビット31
の加算の和S₃₁が０に等しいならば、１になることが保
証される。

帰納ステップ S_i＝０かつφ_i+1＝１と仮定する。ｉでの和S_iは、 S_i＝P_xi∀P_yi+1∀φ_i+1 であるので、 P_x1∀P_yi+1∀１＝０ または である。ｉでの桁上げは、次式で表せる。

φ_i＝P_xiP_yi+1＋P_xiP_yi+1φ_i+1 φ_i+1＝１であるので、次式が成立する。

φ_i＝P_xiP_yi+1＋P_xi ＝P_xi＋P_yi+1 ところが、上記から、 P_xi∀P_yi+1＝１ であることから、次の式が得られる。

P_xi＋P_yi+1＝１ および φ_i＝１ 上記の２つのステップから、数学的帰納法により、すべ
ての０≦ｉ≦31についてφ_i＝１である。

証明終わり 定理2:すべての０≦ｉ≦31についてP_xi∀P_yi+1＝１であ
れば、和Ｓは０である。

証明： 十分条件の証明 Ｓ＝０ならば、定理１から、すべてのｉについてφ_i+1
＝１である。したがって、S_iが０であるから、次式が成
立する。

P_xi∀P_yi+1＝１ 必要条件の証明 ｉで成立される桁上げφ_iについて考える。この桁上げ
は、次式で表わされる。

仮定により、 P_xi∀P_yi+1＝１ であるので、次式が成立する。

φ_i＝φ_i+1 これは、すべてのｉについて成立しなければならず、ま
た、キャリー・インが１であるので、次式が成立する。

φ_i＝φ_i+1＝…＝１ ここでS_i＝１と置く。ところで、S_iは次のように表わさ
れる。

S_i＝P_xi∀P_yi+1∀φ_i+1 しかし、 P_xi∀P_yi+1＝１ であることから、次式が得られる。

φ_i+1＝０ したがって、S_i＝１という仮定は矛盾し、誤りである。
したがってS_iは、０でなければならない。

証明終り ３−１加算型の演算結果が０になる条件は、定理１と
定理２から導かれる。この条件は、すべての０≦ｉ≦30
について、 P_x31∀τ₁＝１ かつ P_xi∀P_yi+1＝１ である。したがって、R₌₀と表記するゼロに等しい結果
は、次式から判定できる。

R₌₀＝（P_x0∀P_y1）（P_x1∀P_y2）…（P_x30∀P_y31）（P
_x31∀τ₁） これらの結果を、論理命令が算術命令と複合された、イ
ンターロックを有する命令シーケンスに対してR₌₀が作
成できるように、拡張する必要がある。このケースは、
前述の第２のカテゴリーに含まれる。上記米国特許出願
第677079号に示されるALUから、所望の結果を生じるた
めに３つの実施様態が提案された。上記の明細書では、
第２の関数カテゴリーに対するゼロに等しい結果を生成
する機構が、実施様態の選択によって影響を受ける。具
体的にいうと、ゼロに等しい結果の生成は、CSAで生成
される出力と、ALU内の論理機能ブロックで生成される
出力に応じて変わる。上記米国特許出願第677079号の３
つの実施様態のうちの２つは、同じCSAおよび論理機能
ブロックの出力を作成するが、第３の実施様態では、独
自の１組の出力を作成するので、オーバーフローの議論
で行なったのと同様に、これらの実施様態を２つの実施
方式に分けて、R₌₀の生成を論ずることができる。ゼロ
に等しい結果を生成する機構のこれら２つの方式への適
用について次に論ずる。その議論と共に、この機構の段
ごとの説明をも提示する。

第１の実施方式では、３−2CSAを変更せずに使用し
て、和σと桁上げλを生成する。ただし、CSAへの入力
が、第２の関数カテゴリーの実行時には、和が第２オペ
ランドに等しくなり、桁上げが０になるように制御され
る。これと並行して、論理機能ブロックが、所望の論理
演算結果を生成する。０と30の間のすべてのｉについ
て、２−１加算器のビット位置ｉへの第１の入力は、CS
A和σ_iであり、同じ位置への第２の入力は、CSAからの
ビット位置ｉ＋１の桁上げλ_i+1と、論理機能ブロック
からのビット位置ｉの出力L_iの論理和をとることによっ
て得られる。ビット位置31では、第１の入力はσ₃₁であ
り、第２の入力はL₃₁とτ₂の論理和である。ただし、τ
₂は、ALUに供給されるホット・ワンの１つである。これ
らの結果から示唆されるように、すべての０≦ｉ≦30に
ついてP_xiおよびP_yiの生成時にλ_i+1をλ_i+1＋L_i（この
＋は論理和機能を表わす）で置き換えることによって、
上記から導かれるゼロに等しい結果方式を、検討中のAL
U実施様態の第２の関数カテゴリーを含むように、変更
することができる。

これらの変更を加えると、ゼロに等しい結果の段ごと
の実施様態は、以下のようになる。第１段で、CSA和
σ、CSA桁上げλ、および論理機能ブロックの出力を生
成する。以下の式では、CSAへの入力を、当該のALU入力
に対応する小文字のギリシャ文字で表わす。これは、強
制的に０にされる可能性のある制御されたCSA入力を、
対応するALU入力から区別するためである。３−１加算
では、ALU入力がCSAに渡され、たとえば、α_iがA_iと等
しくなるはずである。ところが、論理演算の結果を第３
のALU入力と加算する場合には、α_iとγ_iが強制的に０
にされる。この表記を用いると、第１段からの結果は次
のように表わされる。

σ_i＝α_i∀β_i∀γ_i λ_i＝α_iβ_i＋α_iγ_i＋β_iγ_i 上式で、Ω_OALASL、Ω_XAAL、およびΩ_XOSLは、ALUに供
給される制御信号を表わす。この実施様態の詳細は、参
照によって本明細書に合体された上記のスタマティス・
ヴァッシリアディス他の米国特許出願第677079号に出て
いる。次の段では、CSA和と、上記で論じたようにCSA桁
上げ、またはτ₂と論理ブロック出力の論理和と、−１
との、３−２加算として、P_xとP_yが生成される。その結
果は次の通りである。

P_xi＝σ_i∀（λ_i+1＋L_i）∀１ ０≦ｉ≦30 P_x31＝σ₃₁∀（τ₂＋L₃₁）∀１ P_y1＝σ_i（λ_i+1＋L_i）＋σ_i（１）＋（λ_i+1＋L_i）
（１） ０≦ｉ≦31 P_y31＝σ₃₁（τ₂＋L₃₁）＋σ₃₁（１）＋（τ₂＋L₃₁）
（１） これらの式を、 Ｘ∀１＝ Ｘ（１）＝Ｘ XY＋Ｘ＋Ｙ＝Ｘ＋Ｙ であることを利用して簡単にすると、次式が得られる。

P_xiとP_x31の式は、仮定されたブックセットを用いて１
段で実施できない。しかし、これらの式は、次のように
書き直すことができる。

および どちらの式も、仮定されたブックセットを用いて１段で
実施できる。

第３段では、R₌₀の生成に備えて、２入力XORを生成で
きる。所望のXORは、次の通りである。

R₌₀（ｉ）＝P_xi∀P_yi+1 ０≦ｉ≦30 R₌₀（31）＝P_x31∀τ₁ 第４段では、これらの信号に８入力ANDを適用して、単
一のゼロに等しい結果信号の生成を開始することができ
る。所望の式は、次の通りである。

R₌₀（0:7）＝R₌₀（０）R₌₀（１）…R₌₀（７） R₌₀（8:15）＝R₌₀（８）R₌₀（９）…R₌₀（15） R₌₀（16:23）＝R₌₀（16）R₌₀（17）…R₌₀（23） R₌₀（24:31）＝R₌₀（24）R₌₀（25）…R₌₀（31） 最後に、所望の信号R₌₀が、第５段で４入力ANDを用いて
次式によって作成される。

R₌₀＝R₌₀（0:7）R₌₀（8:15）R₌₀（16:23）R₌₀（24:31） このゼロに等しい結果を生成するための論理図を、第６
図に示す。

第２の実施方式では、CSAと論理機能ブロックが、上
記のスタマティス・ヴァッシリアディス他の米国特許出
願第677079号に従って実施され、下記の出力が得られ
る。

σ_i＝α_i∀β_i∀γ_i ０≦ｉ≦31 λ₀＝α₀β₀Ω₁＋α₀γ₀Ω₂＋β₀γ₀Ω₁ λ_i＝α_iβ_iΩ₁＋α_iγ_iΩ₂＋β_iγ_iΩ₁＋β_i-1Ω₃１≦
ｉ≦31 上記の式の表記法は、前述の定義に従い、ALUに供給さ
れる制御信号であるΩ₁、Ω₂、およびΩ₃を追加したも
のである。ただし、２−1CLAへの入力は、第１の実施方
式の場合とは異なる形で導かれる。この場合、０≦ｉ≦
31について、CLAへのビット位置ｉの第１の入力は、λ
_i+1である。しかし、ビット位置ｉの第２の入力は、次
のブール式で表わせる。

Ω₄σ_i＋L_i ただし、Ω₄は、ALUに供給される制御信号であり、０≦
ｉ≦31である。したがって、これらの入力について、σ
_iをΩ₄σ_i＋L_iで置き換えることによって、このALU実施
様態に対するの第２の関数カテゴリーを含むようにゼロ
に等しい結果方式を変更することができる。

これらの変更を加えると、R₌₀の生成は、次のように
行なわれる。第１段で、 σ_i＝α_i∀β_i∀γ_i ０≦ｉ≦31 λ₀＝α₀β₀Ω₁＋α₀γ₀Ω₂＋β₀γ₀Ω₁ λ_i＝α_iβ_iΩ₁＋α_iγ_iΩ₂＋β_iγ_iΩ₁＋β_i-1Ω₃１≦
ｉ≦31 が生成できる。前の場合と同様に、この実施様態の詳細
は、上記のスタマティス・ヴァッシリアディス他の米国
特許出願第677079号に出ている。P_xとP_yの生成は、第２
段で行なえる。これらの信号は、０≦ｉ≦31のすべての
ｉについて、次式によって生成される。

P_x1＝（Ω₄σ_i＋L_i）∀λ_i+1∀１ P_y1＝（Ω₄σ_i＋L_i）λ_i+1＋（Ω₄σ_i＋L_i）（１）＋λ
_i+1（１） これらの式を整理すると、次式が得られる。

このP_xの式は、そのままでは１段で実施できないが、次
のように書き直せる。

上式は、仮定されたブックセットを用いて１段で実施で
きる。第３段、第４段、第５段からなる、R₌₀の生成の
残りの部分は、第１の実施方式で使用されたものと同一
の回路を用いて実現できる。したがって、ALUの出力が
生成されるのと同じ段である第５段で、R₌₀を得ること
ができる（上記のスタマティス・ヴァッシリアディス他
の米国特許出願第677079号を参照されたい）。

明らかに、実施方式の例または好ましい実施例と、発
明を実施するのに最適の様態の例示を用いて説明してき
た本発明は、プロセッサ性能の潜在的な向上の基礎とな
るものである。したがって、当業者なら本発明を実施す
るために今回企図した実施態様を検討すれば、現在およ
び将来に発明となる可能性もあるさらに進んだ改良およ
び機能強化を思いつくであろうことが理解されよう。こ
れらの改良および機能強化は、第１発明者の権利を維持
するように解釈すべきである。下記の特許請求の範囲の
所期の範囲内にあると理解すべきである。

Claims (4)

【特許請求の範囲】
1. 【請求項１】桁上げ保存加算器と２−１加算器とを含む
   ３−1 2進加算器から成り且つＡ、ＢおよびΓと表記さ
   れる３つのオペランドを有する、複数の命令を実行する
   ための３−1ALU手段と、 前記２−１加算器に入力を供給するための論理演算ブロ
   ック手段と、 前記３−1ALU手段のゼロに等しい演算結果を予測するた
   めのゼロ手段とを備え、 前記ゼロ手段が、Ａ＋Ｂ^★＋Γ^★＋τ₂＋τ₁＋１−１の
   計算を表す によって演算を予測して、算術演算とそれに続く算術演
   算の加算減算という最悪条件のシナリオを計算し、前記
   演算が、 Ａ＋Ｂ＋Γ Ａ＋Ｂ＋（＋１） Ａ＋（＋１）＋Γ Ａ＋（＋１）＋（＋１） または Ａ＋Ｂ＋Γ Ａ＋Ｂ＋＋１ Ａ＋＋１＋Γ Ａ＋＋１＋＋１ によって表されることを特徴とする、ALU状況判定装
   置。
2. 【請求項２】桁上げ保存加算器と２−１加算器とを含む
   ３−1 2進加算器から成り且つＡ、ＢおよびΓと表記さ
   れる３つのオペランドを有する、複数の命令を実行する
   ための３−1ALU手段と、 前記２−１加算器に入力を供給するための論理演算ブロ
   ック手段と、 前記３−1ALU手段のゼロに等しい演算結果を予測するた
   めのゼロ手段とを備え、 前記ゼロに等しい演算結果が、 R₌₀＝（P_x0∀P_y1）（P_x1∀P_y2）…（P_x30∀P_y31）（P
   _x31∀τ₁） ただし、 σ_i＝α_i∀β_i∀γ_i λ_i＝α_iβ_i＋α_iγ_i＋β_iγ_i Ｌ_i＝Ａ_iΩ_OALASL＋Γ_iΩ_OALASL＋Ａ_iΓ_iΩ_XAAL＋_{i
   i}Ω_XOSL P_xi＝σ_i∀（λ_i+1＋L_i）∀１ ０ｉ30 P_x31＝σ₃₁∀（τ₂＋L₃₁）∀１ P_yi＝σ_i（λ_i+1＋L_i）＋σ_i（１）＋（λ_i+1＋L_i）
   （１） ０ｉ30 P_y31＝σ₃₁（τ₂＋L₃₁）＋σ₃₁（１）＋（τ₂＋L₃₁）
   （１） によって計算されることを特徴とする、ALU状況判定装
   置。
3. 【請求項３】桁上げ保存加算器と２−１加算器とを含む
   ３−1 2進加算器から成り且つＡ、ＢおよびΓと表記さ
   れる３つのオペランドを有する、複数の命令を実行する
   ための３−1ALU手段と、 前記２−１加算器に入力を供給するための論理演算ブロ
   ック手段と、 前記３−1ALU手段のゼロに等しい演算結果を予測するた
   めのゼロ手段とを備え、 前記ゼロに等しい演算結果が、 第５段 R₌₀＝R₌₀（0:7）R₌₀（8:15）R₌₀（16:23）R₌₀（24:31） によって、５つの論理段を通して計算されることを特徴
   とする、ALU状況判定装置。
4. 【請求項４】桁上げ保存加算器と２−１加算器とを含む
   ３−1 2進加算器から成り且つＡ、ＢおよびΓと表記さ
   れる３つのオペランドを有する、複数の命令を実行する
   ための３−1ALU手段と、 前記２−１加算器に入力を供給するための論理演算ブロ
   ック手段と、 前記３−1ALU手段のゼロに等しい演算結果を予測するた
   めのゼロ手段とを備え、 論理演算とその後に続く算術演算を計算する場合、前記
   桁上げ保存加算器の入力であるＡとΓがゼロに等しく、
   前記２−１加算器の２つの入力のうち一方が当該論理演
   算の結果を含み、算術演算とその後に続く算術演算を計
   算する場合は、前記桁上げ保存加算器の入力が前記オペ
   ランドに等しく、前記２−１加算器の２つの入力のうち
   一方が、論理オペランドを抑止させて、前記桁上げ保存
   加算器の桁上げを通過させ、 前記論理演算ブロック手段が、前記３−1 2進加算器と
   並列であり且つＡ＋Ｂ^★＋Γ^★＋τ₂＋τ₁＋１−１の計
   算を行って、算術演算とそれに続く算術演算の加算減算
   という最悪条件のシナリオを計算し、前記演算が、 Ａ＋Ｂ＋Γ Ａ＋Ｂ＋（＋１） Ａ＋（＋１）＋Γ Ａ＋（＋１）＋（＋１） または Ａ＋Ｂ＋Γ Ａ＋Ｂ＋＋１ Ａ＋＋１＋Γ Ａ＋＋１＋＋１ によって表されることを特徴とする、ALU状況判定装
   置。