命令実行方法

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

【発明の名称】	命令実行方法
【発明者】	【氏名】ガーブサンジブ【氏名】アイアドナトケブンレイ
【要約】	【課題】データ依存性を防止し、複数の命令を同時に実行可能とする。【解決手段】複数のレジスタ及びインデックスでアドレス指定可能な複数の一時記憶ロケーションを含むレジスタファイル（１１７）を有するシステムの命令実行方法であって、入出力を有する複数の命令を命令バッファ内に記憶する段階と、複数の一時記憶ロケーションの１つを、命令バッファ内の複数の各命令の１つに割り当て、複数の命令の所定の１つに対応する出力を、一時記憶ロケーションに記憶する段階と、命令バッファ内の複数の命令の１つが、依存性命令であるかどうかを決定する段階であって、依存性命令は１つの入力を有する前回の命令の出力であり、前回の命令は所定のプログラム順序では依存性命令に先行する命令バッファ内の命令である段階と、前回の命令に割り当てられた一時記憶ロケーションと入力とを関係づける段階とによって構成されるものである。

【特許請求の範囲】
【請求項１】複数のレジスタと、インデックスでアドレス指定可能な複数の一時記憶ロケーションとを含むレジスタファイルを有するコンピュータシステムにおいて、所定のプログラム順序を有する命令を実行するための方法であって、（１）それぞれ入力と出力を有する複数の命令を命令バッファ内に記憶する段階と、（２）インデックスでアドレス指定可能な複数の一時記憶ロケーションの１つを、前記命令バッファ内の前記複数の命令のそれぞれ１つに割り当てる段階であって、前記複数の命令の所定の１つに対応する出力が、前記複数の命令の前記所定の１つに割り当てられた前記インデックスでアドレス指定可能な一時記憶ロケーションに記憶される段階と、（３）前記命令バッファ内の前記複数の命令の１つが、依存性命令であるかどうかを決定する段階であって、前記依存性命令は１つの入力を有し、これは前回の命令の出力であり、前記前回の命令は所定のプログラム順序では前記依存性命令に先行する前記命令バッファ内の命令である段階と、（４）前記前回の命令に割り当てられた前記インデックスでアドレス指定可能な一時記憶ロケーションと前記入力とを関係づける段階とによって構成される命令実行方法。
【請求項２】（５）前記前回の命令が出力を出したあとにだけ前記依存性命令を実行する段階と、（６）前記出力を、前記前回の命令に割り当てられた前記インデックスでアドレス指定可能な一時記憶ロケーションに記憶する段階と、（７）前記前回の命令に割り当てられた前記インデックスでアドレス指定可能な一時記憶ロケーションに記憶された前記出力を前記入力として用いて、前記依存性命令に対応する演算を実行する段階とをさらに含むことを特徴とする請求項１記載の命令実行方法。
【請求項３】前回の命令の状態を示す実行した信号と前記入力とを関係づける段階をさらに含むことを特徴とする請求項１記載の命令実行方法。
【請求項４】前記前回の命令が退避されるとき、適切なレジスタに前記出力を記憶する段階をさらに含むことを特徴とする請求項１記載の命令実行方法。
【請求項５】複数のレジスタと、インデックスでアドレス指定可能な複数の一時記憶ロケーションとを含むレジスタ・ファイルを有するコンピュータシステムにおいて、入力と出力を有し所定のプログラム順序を有する命令を実行するための方法であって、（１）インデックスでアドレス指定可能な複数の一時記憶ロケーションの１つを、前記命令バッファ内の前記複数の命令のそれぞれ１つに割り当てる段階であって、前記複数の命令の所定の１つに対応する出力は、前記複数の命令の前記所定の１つに割り当てられた前記一時記憶ロケーションに記憶される段階と、（２）前記命令バッファ内の前記複数の命令の１つが、依存性命令であるかどうかを決定する段階であって、前記依存性命令は前回の命令に依存している入力を有し、前記前回の命令は所定のプログラム順序では前記依存性命令に先行する前記命令バッファ内の命令である段階と、（３）前記前回の命令に割り当てられた前記一時記憶ロケーションと前記前回の命令に依存している入力とを関係づける段階とによって構成される命令実行方法。

【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明はスーパースカラー限定命令セット計算機（ＲＩＳＣ）に関するものであり、更に具体的に言えばスーパースカラーＲ１ＳＣコンピュータ用の、レジスタの名称変更および命令発行を含む命令スケジュール化に関するものである。以下は同一承継人の出願に係る係属中の出願である。「半導体フロアープランおよびレジスタ名称変更回路の方法」、米国出願番号０７／８６０，７１８号、１９９２年３月３１日、本発明と同時に出願（代理人整理番号ＳＰ０４１）。「高速ＲＩＳＣマイクロプロセッサ・アーキテクチャ」、米国出願番号０７／８１７，８１０号、１９９２年１月８日出願（代理人整理番号ＳＰ０５１）。「拡張可能ＲＩＳＣマイクロプロセッサ・アーキテクチャ」、米国出願番号０７／８１７，８０９号、１９９２年１月８日出願（代理人整理番号ＳＰ０２１）。本願に於いて上記の出願の開示を参照することによって当該米国特許出願の明細書の記載内容が本明細書の一部分を構成するものとする。
【０００２】
【従来の技術】本出願で説明する基本的概念の詳細については以下の幾つかの参考文献に記述されている。ＭｉｋｅＪｏｈｎｓｏｎ著ＳｕｐｅｒｓｃａｌａｒＭｉｃｒｏｐｒｏｃｅｓｓｏｒＤｅｓｉｇｎ（Ｐｒｅｎｔｉｃｅ－Ｈａｌｌ，Ｉｎｃ．，ＥｎｇｌｅｗｏｏｄＣｌｉｆｆｓ，ＮｅｗＪｅｒｓｅｙ，１９９１）；ＪｏｈｎＬ．Ｈｅｎｎｅｓｓｙその他著、ＣｏｍｐｕｔｅｒＡｒｃｈｉｔｅｃｔｕｒｅ－ＡＱｕａｎｔｉｔａｔｉｖｅＡｐｐｒｏａｃｈ（ＭｏｒｇａｎＫａｕｆｍａｎｎＰｕｂｌｉｓｈｅｒ，ＳａｎＭａｔｅｏ，Ｃａｌｉｆｏｒｎｉａ，１９９０）。ジョンソンの著書、特に第２、６、および７章に、本発明によって扱われたレジスタ名称変更問題の優れた解説が記述されている。
【０００３】スーパースカラーＲＩＳＣプロセッサに於ける大きな課題は如何にして、斯かる命令実行の本質的な問題である依存性によるデータ・エラーの発生を回避しつつ、複数の命令を平行処理的に、順不同に実行できるか、という点に関する。データ依存性検査、レジスタ名称変更、および命令スケジュール化は問題解決の根本的要素である。
〔記憶競合およびレジスタ名称変更〕真の依存性（「フロー依存性（ｆｌｏｗｄｅｐｅｎｄｅｎｃｉｅｓ）」または「書き込み・読み出し（ｗｒｉｔｅ－ｒｅａｄ）」依存性とも呼ばれる）は、しばしば反依存性（「読み出し・書き込み（ｒｅａｄ－ｗｒｉｔｅ）」依存性とも呼ばれる）および出力依存性（「書き込み・書き込み（ｗｒｉｔｅ－ｗｒｉｔｅ）」依存性とも呼ばれる）と共に命令依存性の単一グルーブに分類される。このように分類をする理由は、これらの依存性のひとつひとつが、レジスタまたは他の記憶ロケーションの使用によってそれ自体を証明するからである。しかしながら、真の依存性を他の二つの依存性と区別することもまた重要である。真の依存性は、プログラムを通してデータおよび情報が流れるということである。反および出力依存性が発生するのは、異なった時点に於いて、レジスタまたは他の記憶ロケーションが異なった計算の為の異なった値を保持するからである。
【０００４】命令が順序通りに発行され、順序通りに完了される場合、レジスタと値の間には一対一の対応が存在する。実行のどの過程に於いても、対応するレジスタに格納されている値はレジスタ識別子によって正確に識別される。命令が順不同に発行され、順不同に実行される場合、レジスタと値の間の対応が崩れ、値同士の間でレジスタをめぐっての競合が発生する。レジスタ割り当ての目的が出来るだけ多くの値を出来るだけ少数のレジスタに保存することである時、これは深刻な問題となる。多数の値を少数のレジスタに保存すると、実行の順序をレジスタ・アロケータが仮定する順序から変更した場合、多数の競合をもたらす。
【０００５】反および出力依存性は正確には「記億競合」と呼ばれる。なぜならば、たとえ互いに競合する命令が独立していても、記憶のロケーション（レジスタを含む）を再使用しようとすると命令同士問で干渉が発生するからである。記憶に対する競合は命令の発行の抑制と、実行速度の低下という弊害を生む。しかし、問題となるリソースの数を増やすことにより、他のリソース競合と同じように、記憶競合を減少あるいは解消できる。
〔依存性のメカニズム〕ジヨンソンは次の項目を含む、様々な依存性のメカニズムを詳しく論じている。すなわち、ソフトウェア、レジスタの名称変更、リオーダー・バッファを用いたレジスタの名称変更、未来バッファを用いたレジスタ名称の変更、インターロツク、依存性を回避するために命令ウィンドウ中でオペランドをコピーすること、および部分的名称変更、等である。
【０００６】従来のハードウェア・インプリメンテーションは命令間の依存性はソフトウェアが管理するようになつている。命令が真の依存性または記憶競合から完全に抜け出すまでハードウェアが命令を扱うことのないように、コンパイラや他のコードジェネレータは命令の順序を変更できる。しかし、不幸にしてこの手法では幾つかの問題が生じる。ソフトウェアはプロセッサによる操作の遅延時間を考慮に入れることができず、したがって依存性を防止するためにどのように命令の順序を変えていいかということを常には判断できない。命令が依存性のない状態になるまでハードウェアがその命令を扱わないように、如何にしてソフトウェアがハードウェアをして制御できるか、ということも問題点のひとつである。操作遅延時間が短いスカラー・プロセッサの場合、ソフトウェアはオーバーヘッドを極端に増大することなく、コードに“ｎｏーｏｐｓ”を挿入してデータ依存性の要求を満たすことができる。プロセッサが１サイクルあたり幾つかの命令を取り出そうとする場合、あるいはいくつかのオペレーションを完了するのに何サイクルかがかかる場合、プロセッサが依存性命令を扱わないようにするために挿入しなければならない“ｎｏーｏｐｓ”の数は急速に増える。その結果、コード・サイズが容認し難い程増大する。命令間の依存性をエンコードするためｎｏーｏｐｓは命令キャッシュという貴重なリソースを使う。
【０００７】順不同の命令発行をプロセッサが許容する場合、どんなメカニズムのソフトウェアを、依存性を実施するのに使用すべきかは全く明らかでない。ソフトウェアはプロセッサの挙動を制御しないので、ソフトウェアが如何にしてプロセッサに依存性命令を解読させないようにするかということは困難である。二番目の問題は、スーパースカラー・プロセッサに於ける依存性を実施するスカラー・プロセッサ用の既存のバイナリ・コードは存在しないことである。なぜならば、実行モードはスーパースカラー・プロセッサにおいては非常に異なったものであるからである。依存性の管理をソフトウェアに委ねるには、スーパースカラー・プロセッサ用にコードを再生成する必要がある。そして、コードの依存性はハードウェアの遅延時間によって直接決定されるので、各スーパースカラー・プロセッサの各バージヨンの最良のコードはそのバージョンのインプリメンテーションに依存する。
【０００８】一方、ハードウェアの依存性対処手法は本質的に複雑であるという理由で望ましくない場合もある。典型的なＲＩＳＣ命令がそうであるように、各命令に２個の入力オペランドと１個の出力値があると仮定すると、どの２個の命令の間にも５つの依存性が存在する。すなわち、２つの真の依存性、２つの反依存性、および１つの出力依存性である。更に、ウィンドウ中の命令のグループのような、一つの命令グループの間の依存性の数は、そのグループ中の命令の数の自乗に比例する。なぜなら、各命令は他の命令の一つ一つに対して考慮されなければならないからである。
【０００９】プロセッサが１つのサイクル内で解読し、発行し、実行しようとする命令の数によって、複雑さは更に増大する。これらのアクションによって依存性が導入される。複雑さを減少させる唯一の助けは、依存性ハードウェァのスコープと複雑さの減少を助けるために、依存性を幾つものサイクルにわたって増分変化量的に決定できるということである。
【００１０】記憶競合を除外するひとつの手法は、レジスタと値との対応性を再設立するための、レジスタを追加導入することである。これらの追加されたレジスタは従来通り、ハードウェアによって動的に割り当てられ、そしてそれらのレジスタは「レジスタ名称変更（ｒｅｇｉｓｔｅｒｒｅｎａｍｉｎｇ）」を使用するプログラムに必要な値に対応させられる。レジスタ名称変更を実現するために、通常プロセッサは生成される新しい値一つ一つに対して（すなわち、レジスタに書き込む命令一つ一つに対して）新しいレジスタを割り当てる。元のレジスタを識別する命令は、そのレジスタの値を読む目的で、新規に割り当てられたレジスタの値を代わりに取得する。従って、ハードウェアは命令中の元のレジスタ識別子を名称変更して、新しいレジスタおよび正しい値と識別する。レジスタ割り当てに関してはレジスタ参照のロケーシヨンに依って、幾つもの異なった命令中の同一のレジスタ識別子は、異なったハードウェア・レジスタにアクセスすることがある。
【００１１】以下のコード・シーケンスを考える。式中、“ｏｐ”はオペレーションを意味し、“Ｒｎ”は番号の付いているレジスタを表わし、“：＝”は割り当てを表わす。
【００１２】Ｒ３ｂ：＝Ｒ３ａｏｐＲ５ａ（１）
Ｒ４ｂ：＝Ｒ３ｂ＋１（２）
Ｒ３ｃ：＝Ｒ５ａ＋１（３）
Ｒ７ｂ：＝Ｒ３ｃｏｐＲ４ｂ（４）
レジスタヘの各割り当てによって、そのレジスタの新しい「インスタンス（ｉｎｓｔａｎｃｅ）」、英字の添え字で表記さているもの、が生成される。第３命令でＲ３用の新しいインスタンスが生成されることによって、第２および第１命令の反および出力依存性がそれぞれ回避されるが、第４命令に正しくオペランドを供給することについては何も影響を与えない。第３命令におけるＲ３への割り当ては第１命令に於けるＲ３への割り当てに優先するものである。従って、次の命令で見られるＲ３Ｃが新しいＲ３となり、その状態は別の命令が値をＲ３に割り当てるまで続く。
【００１３】名称変更を行なうハードウェアは新しいレジスタ・インスタンスを生成し、そのインスタンスの値が他のものによって変更されて、その値への参照が存在しなくなった時点でそのインスタンスを破壊する。これによって、反および出力依存性が解消され、さらに多くの命令パラレリズムが可能となる。レジスタは再利用されるが、再利用はパラレル実行要件と一致している。これは特に順不同の命令発行に役立つものである。なぜならば、記憶競合は正しい結果を生成するのに必ずしも必要ではない命令発行抑制をもたらすからである。例えば、前記の命令シーケンスに於いては、名称変更によって第３命令は直ちに発行されるが、名称変更がない場合、第３命令は第１命令が完了し第２命令が発行されるまでこの命令を遅らせなければならないのである。
【００１４】依存性を軽減するもう一つの手法は単一のビット（スコアーボード・ビット（ｓｃｏｒｅｂｏａｒｄｂｉｔ）と呼ばれる）を各レジスタと対応させることである。スコアーボード・ビットはレジスタに処理待ちの更新が存在することを示すために使用される。レジスタに書き込む命令が解読されると、プロセッサは対応するスコアーボード・ビットを設定する。書き込みが実際に実行されるとスコアーボード・ビットは再設定される。処理待ちの更新が存在するか否かを示すスコアーボード・ビットは一つだけしか存在しないので、各レジスタには斯かる更新は一つしかあり得ない。解読された命令が、処理待ちの更新（設定されているスコアーボード・ビットによって示される）を既に持つレジスタを更新するような場合、スコアーボードは命令の解読を遅らせる。こうして、どの時点に於いてもレジスタ当たり一つの処理待ちの更新を受け付けることによって出力依存性が防止される。
【００１５】一方、レジスタの名称変更は複数のビットを持つタグを使用して様々な未計算の値を識別する。この場合、これらの値のうち幾つかは同一のプロセッサ・レジスタ（すなわち、同一の、プログラムから見えるレジスタ）に振り向けられていることも可能である。従来の名称変更では、ハードウェアは、現在どのような値とも対応していない使用可能なタグのプールからタグを割り当てることが求められ、また、ハードウェアは値の計算が完了するとタグを解放してそのプールに戻す必要がある。更に、スコアーボード化では各レジスタは一つの処理待ち更新しか受け入れることができないので、プロセッサはどの更新が最新のものであるかということを考慮しない。
【００１６】依存性を軽減する更なる手法は、アソシアティブ・ルックアップを使用する「リオーダー・バッファ（ｒｅｏｒｄｅｒｂｕｆｆｅｒ）」を用いてレジスタの名称変更手法を使用することである。アソシアティブ・ルックアップはリオーダー・バッファ項目が割り当てられると直ちにレジスタの識別子をそのリオーダー・バッファ項目に写像する。更に、出力依存性を防止するために、ルックアップは優先順位で行われ、その結果、レジスタが２回以上割り当てられた場合、最新の割り当て値だけが得られる。この結果が利用可能でない場合は、タグが得られる。一つのレジスタに対し、リオーダー・バッファ項目の数と同じ数のインスタンスがあつても構わない。従つて、命令間で記憶競合が発生することはない。異なったインスタンスの各値はリオーダー・バッファからレジスタ・ファイルに順次書き込まれる。最後のインスタンスの値がレジスタ・ファイルに書き込まれると、リオーダー・バッファはもはやレジスタに写像しない。その場合、レジスタ・ファイルにはこのレジスタのインスタンスのみが含まれ、これが最も新しいインスタンスとなる。
【００１７】
【発明が解決しようとする課題】しかし、リオーダー・バッファを用いた名称変更は、レジスタ識別子を値に写像するために、リオーダー・バッファ中のアソシアティブ・ルックアップを必要とする。リオーダー・バッファでは、アソシアティブ・ルックアップは優先順位付けられていて、リオーダー・バッファは常に最新値を対象となるレジスタ（あるいはタグ）に供給するようになっている。リオーダー・バッファもまた、種々の値をレジスタ・ファイルに順次書き込むので、値がリオーダー・バッファ中に存在しない場合でも、レジスタ・ファイルには最新値が必ず格納されている。
【００１８】依存性軽減の更なる手法では、「未来ファイル（ｆｕｔｕｒｅｆｉ１ｅ）」を使用することによってアソシアティブ・ルックアップを削減できる。未来ファイルは前のパラグラフで述べたリオーダー・バッファの特性は持たないファイルである。未来ファイル書き込み用に与えられた値は対応するレジスタに振り向けられた最新の値ではないこともあり、それが実際に最新の値でなければ値は最新のもとのして扱われない。従って、未来ファイルは最新の更新を記憶していて、実際に書き込みを行なう前に、各書き込みが最新の更新に対応することを検査するものである。
【００１９】命令が解読されると、それはオペランド値と一緒に未来ファイル中のタグにアクセスする。レジスタに一つ以上の処理待ちの更新がある場合、タグは解読された命令が必要とする更新値を識別する。ひとつの命令が一旦解読されると、他の命令は反依存性に制約されることなくこの命令のソース・オペランドに上書きすることができる。なぜならば、このオペランドは命令ウィンドウにコピーされるからである。結果が最新の値のタグを持たない場合、その結果が未来ファイルに書き込まれることを防止することによって出力依存性は処理される。反および出力依存性は両方共、命令の発行を遅延させることなく処理される。
【００２０】名称変更で依存性が解消されない場合、依存性を管理するために「インターロツク（ｉｎｔｅｒｌｏｃｋｓ）」を使用しなければならない。インターロックは単に、命令が依存性から解放されるまでその命令の実行を遅延させるものである。命令の実行を抑制するには２つの方法がある。すなわち、命令の解読の抑制と、命令の発行の抑制である。
【００２１】スコアーボード化以上にパーフォーマンスを改善するために、インターロックは「ディスパツチ・スタツク（ｄｉｓｐａｔｃｈｓｔａｃｋ）」を使用してデコーダから命令ウィンドウに移される。ディスパッチ・スタックとは命令ウィンドウの一種で、ウィンドウ中の各命令を依存性カウントと共に増加させるものである。ウィンドウ中の各命令ごとのソース・レジスタに対応する依存性カウントが存在する。このカウントはソース・レジスタの処理待ちの先行更新の数を示すもので、従って、全ての真の依存性が解消される前に終了しなければならない更新の数を示すものである。ウィンドウ中の各命令の行き先レジスタに対応する２個の同じ様な依存性カウントが存在する。これらのカウントで処理待ちのレジスタの使用の数（すなわち反依存性の数）および処理待ちのレジスタの更新の数（すなわち出力依存性の数）が示される。
【００２２】一つの命令が解読され、ディスパッチ・スタックにロードされると、依存性カウントはその命令のレジスタ識別子と、当ディスパッチ・スタックに既に存在する全ての命令のレジスタ識別子とを比較することによって設定される。命令が完了すると、まだウィンドウ中に存在する命令の依存性カウントは、実行される命令のソースおよび行き先レジスタ識別子に基づいて減少する（カウントは完了された命令の数に応じて可変の数で減少する）。命令はその全てのカウントがゼロの場合、独立した命令となる。カウントを使用することによって、ディスパッチ・スタツク中の全ての命令を各サイクルの他の全ての命令と比較する必要がなくなる。
【００２３】反依存性は命令の解読中にオペランドを命令ウィンドウ（例えば予約ステーシヨン）にコピーすることによって防止できる。こうすることによって、オペランドが以降のレジスタの更新の段階で上書きされることがなくなる。レジスタの名称変更とは別に、反依存性を解消させるためにどんな手法でもオペランドはコピーできる。オペランドをコピーする代わりに、反依存性をインターロックすることもできるが、これらのインターロックのために必要なコンパレータおよび／またはカウンタは、比較するソースおよび結果レジスタの組み合わせの数を考慮すると高額である。
【００２４】オペランドそのものの代わりにタグをオペランドとして供給できる。このタグはハードウェアにとっては単に、命令がどの値を必要とするかを識別するための手段である。従って、オペランド値が生成されると、それは命令とマッチさせることができる。レジスタ当たり１個の処理待ちの更新だけしかあり得ない場合、レジスタ識別子がタグとして使用できる（スコアーボード化の場合のように）。レジスタ当たり複数の処理待ちの更新があり得る場合（名称変更の場合のように）、結果タグを割り当てて、そして一意性を保証するためのメカニズムが必要である。
【００２５】スコアーボード・インターロツキングの代わりとなる手法は、レジスタの複数の処理待ち更新を、出力依存性のためにデコーダを遅延させないようにし、且つデコードの過程に於いてオペランド（あるいはタグ）をコピーすることによって反依存性を処理することである。ウィンドウ中の命令は出力依存性から解放されない限り発行されないので、各レジスタの更新は順序通りの実行で行われるのと同じ順序で実行される。但し、異なるレジスタの更新は例外で、お互いに順不同である。この手法はレジスタ名称変更と殆ど同じ機能を持つものであるが、同一のレジスタの更新が順不同に発生するように命令を発行する能力だけは持たない。
【００２６】リオーダ・バツファーを用いる以外に、名称変更にとって代わる良い方法はないように見える。依存性に関する議論の根底を成すものは、プロセッサは順不同の発行を行い、間違って予報された分岐から回復するためのリオーダー・バッファを既に持つている、という前提である。順不同の発行により、依存性を待つためにデコーダを遅延させることが許容できないこととなる。プロセッサに命令ウィンドウがある場合、デコーダをインターロックしてプロセッサのルックアヘッド機能を制限することは矛盾しているのである。従って、二つの選択肢しかない。すなわち、ウィンドウ中で反および出力依存性インタロックを実現させるか、あるいはこれらの依存性を名称変更によって完全に除去することである。
【００２７】
【課題を解決するための手段】本発明はスパースカラーＲＩＳＣコンピュータ用の、レジスタ名称変更および命令発行を含む、命令スケジューングに関するものである。スケジューリング論理の一部であるレジスタ名称変更回路（ＲＲＣ）によって、コンピュータの命令実行ユニツト（ＩＥＵ）は依存性を防止しつつ複数の命令を同時に実行することが可能になる。従来のレジスタ名称変更と比較して、本発明ではレジスタ・アドレスは実際には名称変更されない。本発明のＲＲＣは一時的に命令の結果をバッファに入れ、順不同の命令の実行の結果は全ての先行する命令の実行が終わるまでレジスタ・フアイルに転送されない。ＲＲＣはまた一時的にバッファに入れられたオペランド（結果）を依存命令に供給するために結果の前向き送りを行なう。ＲＲＣには３個のサブセクシヨンが含まれている。すなわち、データ依存性チェッカー（ＤＤＣ）、タグ割り当て論理（ＴＡＬ）、およびレジスタファイル・ポートＭＵＸ（ＲＰＭ）である。
【００２８】ＤＤＣの役割は命令のグループ中の命令間の依存性を検出することである。ＤＤＣは各命令のソース・レジスタのアドレスと、グループ中の以前の各命令の行き先レジスタのアドレスを比較することによって命令間の依存性を検出する。例えば、命令Ａが命令Ｂによつて書き込まれたレジスタからの値を読み出す場合、命令Ａは命令Ｂに依存し、命令Ａは命令Ｂが完了するまで開始できない。ＤＤＣの出力はこれらの依存性を示す。
【００２９】ＤＤＣの出力はＴＡＬに送られる。一つの命令が先行する複数の命令に依存することが起こり得るので、ＴＡＬはこれらの先行する命令のうちどれが最後に実行されるものであるかを決定する必要がある。本発明では、各命令を自動的に、所定の一時的バッファ位置に写像する。従って、本発明は従来のリオーダー・バッファで使用されるような優先順位化されたアソシアティブ・ルックアップを必要とせず、従ってチップの面積／コスト、および実行速度を節約する。
【００３０】同時に実行される複数の命令の順不同の結果は、命令によって指定されたファイル・レジスタではなく、一連の一時的バッファに格納される。例えば、ＤＤＣが、命令６のソースが命令２、３、および５によって書き込まれるレジスタ、〔ＩＮＣＯＭＰＬＥＴＥＳＥＮＴＥＮＣＥ〕であると決定した場合、ＴＡＬは命令６に代わって命令５の「タグ（ｔａｇ）」を出力することによって、命令６は命令５が完了するまで待たなければならないことを表示する。命令５のタグは命令５の結果が格納されている一時的バツフア位置を示す。このタグはまた、命令５が済んだかどうかを示す１ビットの信号（「済みフラグ（ｄｏｎｅｆｌａｇ）」と呼ばれる）を含む。各命令は３個のソース・レジスタを持つことができるので、ＴＡＬは各命令ごとに３個のタグを出力する。命令が先行するどの命令にも依存しない場合、ＴＡＬは一時的バッファのアドレスではなく、その命令の入力のレジスタ・ファイル・アドレスを出力する。
【００３１】ＲＲＣの最後の要素はＲＰＭ、すなわちレジスタファイル・ポートＭＵＸｅｓである。ＲＰＭの入力はＴＡＬの出力であり、ＲＰＭの選択ラインは命令スケジューラ（または、イシュア）と呼ばれるＩＥＵのもう一つの要素から来る。命令スケジューラはどの命令を実行するか（この決定は済みフラグにも基づくものである）を選択し、次にＲＰＭを使用してその命令のタグを選択する。これらのタグはコンピュータのレジスタ・ファイルの読み出しアドレス・ポートに送られる。前述の例では、命令５が完了した後、命令スケジューラは命令６を開始し、命令５の結果（タグ）のアドレスがレジスタ・ファイルに送られるようにＲＰＭを選択する。そして、レジスタ・ファイルは命令５の結果を命令６で使用できるようにする。
【００３２】
【発明の実施の形態】以下、本発明の実施の形態を図面を参照しつつ説明する。
【００３３】本発明の上記および他の特徴と利点は、添付図の中で説明されるように、以下の推奨実施例の更に具体的な説明で明らかになるであろう。
【００３４】図１に本発明の命令実行ユニット（ＩＥＵ）１００の代表的ハイレベルブロック図を示す。ＩＥＵ１００の目的は最短時間で最大数の命令を実行することである。これを遂行するには二つの基本的な方法がある。すなわち、各命令が出来るだけ短時間で実行できるようにＩＥＵ１００を最適化するか、複数の命令を同時に実行できるようにＩＥＵ１００を最適化することである。
【００３５】命令は「バケット」と呼ばれる４つのグループ中のＦＩＦＯ（先入れ先出し方式レジスタ・スタツク記憶装置）命令１０１を通して、命令取り出しユニット（ＩＦＵ、図示せず）からＩＥＵ１００に送られる。ＩＥＵ１００は最大２個の命令バケットを同時に解読し、スケジユールできる。ＦＩＦＯ１０１はＯ－３とラベルされた４個のバケットに全部で１６個の命令が格納できる。ＩＥＵ１００は命令ウィンドウ１０２を調べる。本発明の一実施例では、ウィンドウ１０２は８個の命令（バケット０および１）で構成されている。各サイクルで、ＩＥＵ１００はウィンドウ１０２から最大数の命令を発行しようとする。ウィンドウ１０２は命令バッファ・レジスタとして機能する。一旦、バケット中の命令が実行され、その結果がプロセッサのレジスタ・ファイル（ブロック１１７を参照）に格納されると、バケットは底部１０４から掃き出され、新しいバケットが上部１０６から落とされる。
【００３６】命令を並列あるいは順不同に実行するためには、各命令が必要とする時に、必要なデータが使用可能であるように、また、各命令の実行の結果が、将来の命令においてそれが必要になった時に使用可能であるように配慮する必要がある。
【００３７】レジスタ名称変更回路（ＲＲＣ）はコンピュータのＩＥＵのスケジュール論理の一部であるが、ＲＲＣはカレント命令間の依存性を検出し、命令のソース（入力）を名称変更することによってこの機能を行なうものである。
【００３８】前述のように三種類の依存性が存在する。すなわち、入力依存性、出力依存性、反依存性、である。入力依存性は、例えばＡと呼ばれる命令が、仮にＢと呼ばれる先行の命令の結果に基づいてオペレーションを実行する場合に発生する。出力依存性は、ＡとＢの出力が同じ場所に格納されるような場合に発生する。反依存性は、命令のストリ一ムに於いて命令Ａが命令Ｂの前に現れ、Ｂの結果がＡの入力の一つと同じ場所に格納されなければならない場合に発生する。
【００３９】入力依存性の扱い方は、必要な入力が使用可能になるまで命令を実行しないことである。ＲＲＣ１１２は、カレント命令間の入力依存性を検出するために、そして特定の命令のための全ての入力が使用可能になると命令スケジューラまたはイシュア１１８に合図するために、使用される。これらの依存性を検出するために、ＲＲＣ１１２はデータ依存性回路（ＤＤＣ）１０８を使用して、各命令の入力のレジスタ・ファイル・アドレスと各先行命令の出力のアドレスとを比較する。先行する命令の出力が格納されるべきレジスタから一つの命令の入力が得られる場合、後者の命令は前者の命令の実行が終わるまで待たねばならない。
【００４０】ＲＲＣ１１２のこのインプリメンテーションでは、８個の命令を同時に検査できるので、カレント命令はウィンドウ１０２からこれらの８個の命令のうちの一つとして定義される。当業者にとって、本発明はこれよりも多くの命令、あるいはこれよりも少ない命令を検査できるように容易に変更できるということは明らかであろう。
【００４１】本発明の一実施例では、命令は０から３の入力および０または１の出力を持ち得る。多くの命令の入力および出力は、幾つかのレジスタ・ファイルのうち一つから取得されるか格納されている。各レジスタ・ファイルｌｌ７（例えば別個の、整数、浮動、およびブールレジスタ・ファイル）は３２個の実エントリに加え、８個の一時バツファ１１６のグループを持つことができる。ある命令が完了すると（「完了（ｃｏｍｐｌｅｔｅ）」とは、オペレーションが完了し、オペランドはその行き先レジスタに書き込まれる用意があることを意味する）、その結果は一時バッファ１１６の予め指定されたロケーションに格納される。全ての先行する命令の結果がレジスタ・ファイル中の定められた場所に移された後、この完了した命令の結果はレジスタ・ファイル１１７の適切な場所に移される。このような、一時バッファ１１６からレジスタ・ファイル１１７への結果の移動は「退避（ｒｅｔｉｒｅｍｅｎｔ）」と呼ばれ、終了論理で制御されるもので、当業者にとっては明らかなものであろう。複数の命令が同時に退避可能である。退避とは、コンピュータのプログラム・カウンタを含む、マシンの「正式な状態（ｏｆｆｉｃｉａｌｓｔａｔｅ）」を更新することであり、これもまた当業者にとっては明らかなものであろう。例えば、命令Ｉ０が命令Ｉ１の直前に完了すると、両方の命令の結果をレジスタ・ファイル１１７に直接格納することができる。しかし、その後命令Ｉ３が完了すると、その結果は命令Ｉ２が完了するまで一時バッファ１１６に格納されなければならない。ＩＥＵ１００に各命令の結果を一時バッファ１１６の予め指定された場所に格納させることによって、ＩＥＵ１００はプログラムでの順序とは異なった順序で命令を実行でき、しかも出力依存性および反依存性によって生じる問題も回避できる。
【００４２】ＲＲＣ１１２はビットマツプをバス１２０を経て命令スケジューラ１１８に送り、ウィンドウ１０２中のどの命令が発行の用意ができているかを表示する。命令解読論理（図示せず）はイシュア１１８にバス１２３を経て各命令のリソースの要件を通知する。ＩＥＵ１００中の各リソースごとに（すなわち、各機能ユニットは一つの加算器、乗算器、シフト器、等である）イシュアｌｌ８はこの情報を走査し、バス１２１を経て発行信号を送ることにより、発行するための最初の命令および以降の命令を選択する。発行命令はＲＲＣ１１２内の一組のレジスタファイル・ポートＭＵＸｅｓ（ＲＰＭｓ）１２４を選択する。これらの入力は各命令の入力のアドレスである。
【００４３】これらの結果はレジスタ・ファイルｌｌ７に送られる前に数サイクル分一時バッファ１１６に保存されるので、これらがレジスタ・ファイルｌｌ７に送られる前に一時バッファ１１６から取得するメカニズムが設定されている。このようにして、その情報は他の命令のオペランドとして使用可能となる。このメカニズムは「結果の前送り（ｒｅｓｕｒｔｆｏｒｗａｒｄｉｎｇ）」と呼ばれ、これなしにはイシュア１１８は順不同での命令の発行ができない。この結果の前送りはレジスタ・ファイル１１７に於いて行われ、ＲＲＣ１１２によって制御されるものである。結果の前送りの実行に必要な制御信号、そして斯かる制御信号の生成に使用されるランダム論理は、当業者にとっては明らかであろう。
【００４４】与えられた命令がカレント命令のうちどの命令にも依存しない場合、この命令の入力は既にレジスタ・ファイル１１７に存在するので、結果の前送りは不要となる。イシュア１１８がその命令の実行を決定すると、ＲＲＣ１１２はレジスタ・ファイルｌ１７にそのデータを出力するよう指示する。
【００４５】ＲＲＣ１１２は次の三つの部分が含まれる。すなわち、データ依存性チェッカー（ＤＤＣ）１０８、タグ割り当て論理（ＴＡＬ）１２２、およびレジスタファイル・ポートＭＵＸｅｓ（ＲＰＭ）１２４である。ＤＤＣ１０８はカレント命令間の何処に入力依存性が存在するかを決定する。ＴＡＬ１２２はイシュア１１８のために依存性を監視し、結果の前送りを制御する。ＲＰＭ１２４はイシュア１１８によって制御され・ＴＡＬ１２２の出力を適切なレジスタ・ファイル・アドレス・ポート１１９に差し向ける。各命令はバス１１０を経てＤＤＣ１０８に送られる。全てのソース・レジスタは、ウィンドウ１０２の命令ごとに、全ての以前の行き先レジスタと比較される。
【００４６】各命令の行き先は１つだけであり、これは一実施例ではダブルレジスタとなる。ひとつの命令は先行する命令だけに依存し、最大３個のソース・レジスタを持つことができる。依存性の存在を検出するために、相互に検査される必要がある様々なレジスタ・ファイルのソースおよび行き先アドレスがある。上記の如く、下部の２個のバケットに対応する下部の８個の命令はＤＤＣ１０８によって検査される。全てのソースレジスタ・アドレスは全ての先行の行き先レジスタ・アドレスと比較されて、ウィンドウ１０２中の命令が存在するかどうかが調べられる。
【００４７】例えば、一つのプログラムに下記の命令シーケンスがあるとする。
【００４８】ａｄｄＲ０，Ｒ１，Ｒ２（０）
ａｄｄＲ０，Ｒ２，Ｒ３（１）
ａｄｄＲ４，Ｒ５，Ｒ２（２）
ａｄｄＲ２，Ｒ３，Ｒ４（３）
各命令０－３の最初の２個のレジスタはソース・レジスタであり、各命令の最後のレジスタは行き先レジスタである。例えばＲ０とＲ１は命令０のソース・レジスタであり、Ｒ２は行き先レジスタである。命令０はレジスタ０および１の内容を加算し、結果をＲ２に格納する。この例の命令１－３で、全ての依存性を評価するために必要な比較は次の通りである。
【００４９】ＩｌＳ１、Ｉ１Ｓ２対Ｉ０ＤＩ２Ｓ１，Ｉ２Ｓ２対Ｉ１Ｄ，Ｉ０ＤＩ３Ｓ１，Ｉ３Ｓ２対Ｉ２Ｄ，Ｉ１Ｄ，Ｉ０Ｄ上記を説明すれば次の通りである。ＩＸＲＳ１は命令Ｘの第１ソース（入力）のアドレスであり、ＩＸＲＳ２は命令Ｘの第２ソース（入力）のアドレスであり、ＩＸＤは命令Ｘの行き先（出力）のアドレスである。
【００５０】更に、プロセツサには一時バッファがあり、そこに命令０の結果に干渉することなしに命令２の結果が格納できるので、ＲＲＣｌ１２は、命令２は命令０に依存して出力されることを無視できる。前述の、命令０と１の結果がレジスタ・ファイル１１７に移されるまで、命令２の結果は一時バッファ１１６からレジスタファイルｌ１７に移されないのである。
【００５１】ＲＲＣｌ１２によつて検査される命令の数は容易にスケール可能である。４個の命令でなく、８個の命令を同時に検査するためには、下記の更なる比較を行わなければならない。
Ｉ４Ｓｌ，Ｉ４Ｓｌ対Ｉ３Ｄ，Ｉ２Ｄ，Ｉ１Ｄ，Ｉ０ＤＩ５Ｓｌ，Ｉ５Ｓ２対Ｉ４Ｄ，Ｉ３Ｄ，Ｉ２Ｄ，Ｉ１Ｄ，Ｉ０ＤＩ６Ｓｌ，Ｉ６Ｓ２対Ｉ５Ｄ，Ｉ４Ｄ，Ｉ３Ｄ，Ｉ２Ｄ，Ｉ１Ｄ，Ｉ０ＤＩ７Ｓｌ，Ｉ７Ｓ２対Ｉ６Ｄ，Ｉ５Ｄ，Ｉ４Ｄ，Ｉ３Ｄ，Ｉ２Ｄ，Ｉ１ＤＩ０Ｄ依存性の検査を行なうために、ＲＲＣ１１２が扱わねばならない特殊なケースが幾つかある。第一に、ある命令では同じレジスタを入力と出力の両方に使用する。従つて、ＲＲＣ１１２はこのソース／行き先レジスタ・アドレスを全ての先行する命令の行き先レジスタ・アドレスと比較する必要がある。従って、命令７のためには下記の比較が必要である。
【００５２】Ｉ７Ｓ１，Ｉ７Ｓ２，Ｉ７Ｓ／Ｄ対Ｉ６Ｄ，Ｉ５Ｄ，Ｉ４Ｄ，Ｉ３Ｄ，Ｉ２Ｄ，Ｉ１Ｄ，Ｉ０Ｄ更に、別の特殊なケースは、６４ビットの出力（長語オペレーション）を生成する命令がプログラムに含まれている場合である。これらの命令は、結果を格納するための２個のレジスタが必要である。本実施例ではこれらのレジスタは順次レジスタでなけれぱならない。従って、ＲＲＣｌｌ２が命令４の依存性を検査していて、命令１が長語オペレーションである場合、ＲＲＣｌｌ２は下記の比較を行なわなければならない。
Ｉ４Ｓ１，Ｉ４Ｓ２対Ｉ３Ｄ，Ｉ２Ｄ，Ｉ１Ｄ，Ｉ１Ｄ＋１，Ｉ０Ｄ場合によっては、命令は行き先レジスタを持たない。従って、ＲＲＣ１１２は行き先レジスタなしの命令と如何なる将来の命令との間のどんな依存性をも一切無視しなければならない。更に、命令は１個の有効なソース・レジスタだけを持つとは限らないので、ＲＲＣ１ｌ２は未使用のソース・レジスタ（通常はＳ２）と全ての先行する命令との間のどんな依存性をも一切無視しなければならない。
【００５３】ＲＲＣ１１２はまた複数のレジスタ・ファイルを扱うことができ、複数のレジスタ・ファイルが使用される場合、一つの命令のソース・レジスタが他の命令の行き先レジスタと同じアドレスを持ち、同じレジスタ・ファイルに存在する場合のみ依存性が発生する。ＲＲＣｌｌ２は特定のアドレスがどのレジスタ・ファイルからのものであるかという情報をそのアドレスの一部として扱う。例えば、４個のＲＲＣ１１２は５ビット・レジスタ・ファイルを使用するインプリメンテーションに於いて、ＲＲＣ１１２は５ビットの比較のかわりに７ビットの比較を行なう（５ビットはアドレスで、２ビットはレジスタ・ファイル用である）。
【００５４】どの命令が長語オペレーションであるか、あるいはどの命令に不正なソースまたは行き先レジスタが含まれているかを示す信号は命令解読論理（ＩＤＬ、図示せず）からＲＲＣ１１２に送られる。またＩＤＬはどのレジスタ・ファイルから各命令のソースと行き先を取得するか、またどのレジスタ・ファイルにそれらを送るかをＲＲＣｌ１２に通知する。
【００５５】図２はＤＤＣ１０８のブロック図である。ウィンドウ１０２の８個の命令すべてのためのソース・アドレス信号はＩＦＩＦＯ１０１から来着する。更なる入力には、８個の命令すべてのための長語ロード・オペレーション・フラグ・レジスタ・ファイル解読信号、不正行き先レジスタ・フラグ、行き先アドレス信号、アドレッシング・モードフラグ、等が含まれている。
【００５６】ＤＤＣ２０８は２８個の依存性ブロック２０４で構成されている。各ブロック２０４はＫＥＹ２０６で記述されている。各ブロック２０４はＩＸＳ１，ＩＸＳ２，およびＩＸＳ／Ｄ、の３個の入力を受け取る。ＩＸＳ１は命令Ｘの第一ソース（入力）のアドレスであり、ＩＸＳ／Ｄは命令Ｘの第二ソース（入力）のアドレスであり、ＩＸＳ／Ｄは命令Ｘのソース／行き先（入力）のアドレスである。各ブロック２０４はまた入力ＩＹＳ／Ｄを受け取るが、これはある先行命令Ｙの行き先レジスタ・アドレスである。例えば、最上行２０８はＩ０Ｓ／Ｄを受け取るが、これは命令０の行き先レジスタ・アドレスである。各ブロック２０４はデータ依存性の結果を対応するバスライン１１４の一つに出力する。例えば、Ｉ２Ｓ／Ｄのアドレスは命令７、６、５、４および３のオペランドアドレスＳ１，Ｓ２、およびＳ／Ｄと比較されなくてはならない。
【００５７】各ブロック２０４は三つの比較を行なう。これらの比較を理解するために図８に示される汎用的ブロック７００を考察してみる。このブロックは命令Ｙのソース／行き先オペランドと命令Ｘの各オペランドとを比較する。この例に於いて、下記の三つの比較が行なわれなくてはならない。
【００５８】ＩＸＳ１＝ＩＹＳ／ＤＩＸＳ２＝ＩＹＳ／ＤＩＸＳ／Ｄ＝ＩＹＳ／Ｄこれらの比較は３個のコンパレータブロック７０２、７０４、および７０６でそれぞれ表わされる。コンパレータブロック７０２、７０４および７０６への１組の入力はＩＹＳ／Ｄフィールドのビットであって、このフィールドは番号７０８で表わされる。コンパレータブロック７０２はその入力の第二セットとしてＩＸＳ１のビットを持つ。同じく、コンパレータブロック７０４はその入力の第二セットとしてＩＸＳ１のビットを持つ。また、コンパレータブロック７０６はその入力の第二セットとしてＩＸＳ／Ｄのビットを持つ。
【００５９】推奨実施例では、ブロック７０２，７０４、および７０６で実行される比較はランダム論理で実行できる。コンパレータブロック７０６のランダム論理の一例を図９に示す。命令Ｙのソース／行き先ビット［６：０］を参照番号８０２で右側からの入力として示す。同じく、命令Ｘのソース／行き先ビット［６：０］を参照番号８０４で上側からの入力として示す。最上位ビット（ＭＳＢ）はビット６であり、最下位ビット（ＬＳＢ）はビット０である。これら２個のオペランドからの、対応するビットは７個の排他的ＮＯＲゲート（ＸＮＯＲ）８０６に送られる。ＸＮＯＲ８０６の出力は次に７個の入力ＡＮＤゲート８０８によってＡＮＤをとられる。対応するビットが同一であるならば、ＸＮＯＲ８０６の出力のすべてはロジック・ハイである。全てのビットが同一であるならば、７個のＸＮＯＲ８０６の出力のすべてはロジック・ハイであり、ＡＮＤゲート８０８の出力はロジツク・ハイである。これは、ＩＸＳ／ＤとＩＹＳ／Ｄとの間に依存性が存在することを示す。
【００６０】コンパレータブロック７０２および７０４のランダム論理は図９に示したものと同じである。本発明ではデータ依存性検査を行なうために幾多の他のランダム論理回路が可能であり、これはこの実施例の精神から逸脱することなく、当業者にとって明らかであろう。
【００６１】また、当業者にとって更に明らかになるであろうが、種々のインプリメンテーシヨン固有のケースの発生が可能であるが、そのためにはデータ依存性検査を行なう更なるランダム論理が必要となる。代表的な特殊なデータ依存性検査のケースは長語の処理である。
【００６２】前述の如く、長語オペレーションがレジスタＸに書き込むと、最初の３２ビットはレジスタＸに書き込まれ、二番目の３２ビットはレジスタＸ＋１に書き込まれる。従って、データ依存性チェッカーは比較を行なうに当たって両方のレジスタを検査する必要がある。推奨実施例では、レジスタＸは偶数レジスタであり、レジスタＸ＋１は奇数レジスタである。従って両者の違いはＬＳＢの差だけである。両方のレジスタを同時に検査する最も簡単な方法はＬＳＢを無視することである。ストア・ロング（ＳＴＬＧ）またはロード・ロング（ＬＤＬＧ）オペレーションの場合、ＸとＹがＬＳＢ（０）ビットだけの差で違うならば、図９の論理では、依存性が実際は存在していてもそれがあたかも全然ない状態を生み出す。従って、長語オペレーシヨンのためには、全ての依存性が確実に検出できるように、ＳＴＬＧおよびＬＤＬＧフラグは［０］ビットＸＮＯＲの出力とＯＲがとられなければならない。
【００６３】図５にＩＸＳ１およびＩＹＳ／Ｄのデータ依存性検査フローチャートを示す。条件付きブロック５０２で示されるように、ＤＤＳ１０８は最初にＩＸＳ１およびＩＸＳ／Ｄが同じレジスタ・ファイルに在るかどうかを検査する。もし同じレジスタ・ファイルに存在しないならば依存性はない。これを、ブロック５０６に示す。依存性が存在するならば、ＤＤＣ１０８は、ブロック５０６に示すように、次にＩＸＳ１およびＩＹＳ／Ｄが同じレジスタに在るかどうかを決定する。同じレジスタに存在しない場合、フローは条件付きブロック５０８へ進み、そこでＤＤＣｌ０８はＩＹが長語オペレーションであるか否かを決定する。ＩＹが長語オペレーションでない場合、依存性は存在せず、フローはブロック５０４に進む。ＩＹが長語オペレーションである場合、フローは条件付き文５０１に進む。そこで、ＤＤＣ１０８はＩＸＳ１およびＩＹＳ／Ｄ＋１が同じレジスタに存在するか否かを決定する。同しレジスタに存在しない場合、依存性はなく、フローはブロックに進む。ＩＸＳ１およびＩＹＳ／＋１が同じレジスタに存在するならば、条件付きブロック５１２に進み、そこでＤＤＣ１０８はＩＹが有効な行き先を持っているか否かを決定する。有効な行き先がない場合、依存性は存在せず、フローはブロック５０４に進む。ＩＹに有効な行き先がある場合、条件付きブロック５１４に進み、そこでＤＤＣ１０８はＩＸＳ１が有効なソースレジスタを持っているか否かを決定する。ここでも、有効なソースレジスタが検出されないならば依存性は存在せず、フローはブロック５０４に進む。有効なソースレジスタが検出されれば、ＤＤＣ１０８はＩＸＳ１およびＩＹＳ／Ｄの間に依存性があることを検出したことになる。これはブロック５１６で示されている。
【００６４】データ依存性検査については、同一承継人の出願に係る継続中の出願、関連特許申請、米国出願番号０７／８６０，７１８号（代理人整理番号ＳＰ０４１）に更に詳しく説明されている。この出願の開示はここに参照文献として含まれているものとする。ある命令がその入力の一つを、他の幾つかの命令によって既に書き込まれているレジスタから取得することが可能であるので、本発明ではどの入力が真の依存性であるかを選択しなければならない。例えば、命令２および５がレジスタ４に書き込み、命令７がレジスタ４から読み出す場合、命令７には二つの依存性があり得る。この場合、プログラムでは命令５は命令２に後続するので、プログラマーの意図とすることは、命令７が命令２の結果ではなく、命令５の結果を使用することであると仮定される。従って、一つの命令が先行する幾つかの命令に依存する場合、ＲＲＣ１１２はその命令は先行する命令のうち最高の番号を持つ命令に依存するものとして扱う。
【００６５】ＴＡＬ１１２は一旦、真の依存性が何処に存在するかを決定した後、各命令の入力を探す必要がある。本発明の推奨実施例では、入力は実際のレジスタ・ファイルまたは一時バッファ１１６の配列から取得できる。ＲＲＣ１１２は、依存性を持たない命令の場合、その命令の全ての入力はレジスタ・ファイルに存在すると仮定する。この場合、ＲＲＣ１１２はＩＦＩＦＯ１０２から取得されたＩＸＳ１、ＩＸＳ２およびＩＸＳ／Ｄアドレスをレジスタ・ファイルに渡す。依存性のある命令の場合、ＲＲＣ１１２はデータは一時バッファ１１６に格納されていると仮定する。ＲＲＣ１１２は各命令がどの先行命令に依存するかが分かっているので、そして各命令は常に一時バッファ１１６中の同じ場所に書き込むので、ＲＲＣ１１２は一時バッファ１１６の何処に命令の入力が保存されているかを決定することができる。ＲＲＣ１１２はこれらのアドレスをレジスタ・ファイル読み出しポートｌ１９に送り、レジスタ・ファイル１１７はその命令がデータを使用できるようにを一時バッファｌ１６から出力する。
【００６６】タグ割り当て例を下記に記す。
【００６７】０：ａｄｄｒ０，ｒ１，ｒ２１：ａｄｄｒ０，ｒ２，ｒ３２：ａｄｄｒ４，ｒ５，ｒ２３：ａｄｄｒ２，ｒ３，ｒ４上記のオペレーションの依存性は下記の通りである（依存性を＃記号で記す）。
【００６８】Ｉ１Ｓ２＃Ｉ０Ｓ／ＤＩ３Ｓ１＃Ｉ０Ｓ／ＤＩ３Ｓ１＃Ｉ２Ｓ／ＤＩ３Ｓ２＃Ｉ１Ｓ／Ｄ先ずＩ０に注目するならば、Ｉ０は依存性を持たないので、そのタグはその元のソース・レジスタ・アドレスに等しい。
【００６９】Ｉ０Ｓｌタグ＝Ｉ０Ｓｌ＝ｒ０Ｉ０Ｓ２タグ＝Ｉ０Ｓ２＝ｒ１Ｉ０Ｓ／Ｄタグ＝Ｉ０Ｓ／Ｄ＋ｒ２Ｉ１は１個の依存性を持つのでＩ１のタグは次の通りである。
【００７０】ＩｌＳ１タグ＝ＩｌＳ１＝ｒ０Ｉ１Ｓ２タダ＝Ｉ０Ｓ／Ｄ＝ｔ０式中、（ｔ０＝一時バッファ中の命令０のスロット）
Ｉ１Ｓ／Ｄタグ＝ＩｌＳ／Ｄ＝ｒ３Ｉ２もまた依存性を持たない、独立したものである。
【００７１】Ｉ２Ｓ１タグ＝Ｉ２Ｓ１＝ｒ４Ｉ２Ｓ２タグ＝Ｉ２Ｓ２＝ｒ５Ｉ３Ｓ／Ｄタグ＝Ｉ２Ｓ／Ｄ＝ｒ２Ｉ３Ｓ１にはＩ０Ｓ／ＤおよびＩ２Ｓ／Ｄの二つの依存性が有り得る。ＴＡＬ２２は最後の依存性（最大の番号を持つ依存性）を選択しなければならないので、Ｉ２Ｓ／Ｄが選択される。
【００７２】Ｉ３Ｓ１タグ＝Ｉ２Ｓ／Ｄ＝ｔ２Ｉ３Ｓ２タグ＝Ｉ１Ｓ／Ｄ＝ｔ１Ｉ３Ｓ／Ｄタグ＝Ｉ３Ｓ／Ｄ＝ｔ４これらのタグは次にバス１２６を経てＲＰＭ１２４に送られ、イシュア１１８によって選択される。ＴＡＬ１２２はタグを準備すると同時にＤＣＬ１３０の出力を監視し、それらの出力をバス１２０を使用してイシュア１１８に送る。それを行なうに当たり、ＴＡＬ１２２はＲＰＭ１２４に送るタグを選ぶのと同じ方法でＤＣＬ１３０の適切な出力を選択してイシュア１１８に送る。
【００７３】この例を更に説明するならば、ＴＡＬ１２２は下記のレディー信号をイシュア１１８に送る。
【００７４】Ｉ０Ｓ１ＩＮＦＯ＝１（命令０は独立した命令であるので、直ちに起動できる）。
【００７５】Ｉ０Ｓ２ＩＮＦＯ＝１Ｉ０Ｓ／ＤＩＮＦＯ＝１ＩｌＳ１ＩＮＦＯ＝１ＩｌＳ２１ＮＦＯ＝ＤＯＮＥ［０］
（Ｉ０が済んだ時ＤＯＮＥ［０］＝１）
Ｉ１Ｓ／ＤＩＮＦＯ＝１Ｉ２Ｓ１ＩＮＦＯ＝１Ｉ２Ｓ２ＩＮＦＯ＝１Ｉ２Ｓ／ＤＩＮＦＯ＝１Ｉ３Ｓ１ＩＮＦＯ＝ＤＯＮＥ［２］
Ｉ３Ｓ２ＩＮＦＯ＝ＤＯＮＥ［１］
Ｉ３Ｓ／ＤＲＥＡＤ＝１（ＤＯＮＥ信号はバス１３２を経てＤＣＬ１３０から送られる。本発明においては「済んだ（ｄｏｎｅ）」とは命令の結果が一時バッファに在るか、さもなくば機能ユニットの出力に於いて使用可能であることを意味する。一方、「終了（ｔｅｒｍｉｎａｔｅ）」とは命令の結果がレジスタ・ファイルに存在することを意味する）
次に図３を参照しつつＴＡＬ１２２の代表的ブロック図を説明する。ＴＡＬ１２２は８個のタグ割り当て論理ブロック３０４で構成されている。各ＴＡＬブロック３０２は対応するデータ依存性結果、およびコンピュータの命令解読および制御論理（図示せず）から送られる更なる信号を複数のバス１１４を経て受け取る。ＢＫＴビット信号はタグの最下位ビットを形成する。ＤＯＮＥ［Ｘ］フラグは命令０から６までのものであり、命令Ｘが済んだか否かを通知する。ＤＢＬＲＥＧ［Ｘ］フラグは命令のうち一つが倍長ワードであるならば、どれが倍長ワードであるかを通知する。各ＴＡＬブロック３０２はそれ自身の命令レジスタ・アドレスを入力として受け取る。その他の信号であるＤＢＬＲＥＧおよびＢＫＴ信号は全てインプリメンテーション依存の制御信号である。各ＴＡＬブロック３０２はＩＸＳ１、ＩＸＳ２およびＩＸＳ／Ｄというラベルを持つ６ビットの、３個のタグ１２６を出力する。ＴＡＬ１２２は各タグ信号の最下位の５ビットをＲＰＭｓ１２４に出力し、最上位のタグをイシュア１１８に出力する。
【００７６】図３の各ブロック３０２は３個の優先エンコーダ（ＰＥ）で構成されている。これらのＰＥはそれぞれＳ１、Ｓ２、およびＳ／Ｄ用である。しかし、一つの例外がある。すなわち、Ｉ０はタグの割り当てを必要としないのである。Ｉ０は常に独立しているので、その各タグは元のＳ１、Ｓ２、およびＳ／Ｄのアドレスと同一である。
【００７７】典型的なＰＥを図１０に示す。ＰＥ９０２は８個の入力９０４および８個の出力９０６を持つ。ＰＥ９０２の入力９０４はＤＤＣ１０８からの出力１１４であり、これらの出力は何処に依存性が存在するかを示すものである。例えば、ソース・レジスタ１（Ｓ１）の場合、Ｉ７Ｓ１タグ割り当てＰＥ９０２の７個の入力はＤＤＣ１０８の７個の出力１１４であり、それらはＩ７Ｓ１が１６Ｄに依存しているか否か、Ｉ７Ｓ１がＩ５Ｄに依存しているか否か、等、そしてＩ７Ｓ１がＩ０Ｄに依存しているか否か、までを通知する。参照番号９０８で示される第８入力は常にＰＥ９０２からの出力であるので、常に高位でタイとなる。
【００７８】上記のように、一つの命令が先行する幾つかの命令に依存する場合、ＰＥ９０２は依存性が存在する先行命令のうち最も古い（プログラム順で）命令だけを選択し、出力する。これは、最も古い先行命令への依存性があるか否かを示す信号をＰＥ９０２の最優先順位の入力に接続し、２番目に古い先行命令への依存性があるか否かを示す信号をＰＥ９０２の最優先順位が２番目の入力に接続する、というふうに、すべての先行命令を接続することによって行なわれる。ＰＥ９０２の最低優先順位の最も低い入力は常に高位にタイとなり、従って、ＰＥ９０２の出力のうち少なくとも１個のものが確定される。
【００７９】出力９０６はＭＵＸ９１０の選択ラインとして使用されるＭＵＸ９１０には８個の入力９１２があり、それらに各命令のタグが付く。
【００８０】これを理解するために、Ｉ７がＩ６およびＩ５に依存すると仮定する。Ｉ６の優先順位はＩ５より高いので、ＰＥ９０２の出力９０６に於いてＩ６に対応するビットはハイである。ＭＵＸ９１Ｏの対応する入力９１２にはＳ１用のＩ６のタグがある（ＰＥ９０２はＩ７Ｓ１の為のものである）。Ｉ７はＩ６に依存するので、Ｉ６の結果のロケーションは、Ｉ７が使用可能になるように、ＭＵＸ９１０から出力しなければならない。従って、Ｉ６のタグが選択され出力ライン９１４に出力される。Ｉ６の済みフラグであるＤＯＮＥ［６］もまたＭＵＸ９１４から出力して、イシュアｌｌ８が、いつＩ７の入力がレディーであるか分かるようにしなければならない。このデータはバス１２０を経てイシュアｌ１８に送られる。命令には最大３個までのソースがあるので、ＴＡＬ１２２は各命令に対して最大３個までの依存性を監視し、各命令に関して３個のベクトル（合計２４個のベクトル）をイシュアｌｌ８に送る。独立した命令の場合、ＴＡＬ１２２はその命令は直ちに開始できることをイシュアｌ１８に通知する。
【００８１】ＲＰＭｓ１２４に送られるタグ出力のＭＳＢは、アドレスがレジスタ・ファイル・アドレスであるか、一時バッファ・アドレスであるかを通知するのに使用される。独立した命令の場合、５個のＬＳＢ出力はソース・レジスタ・アドレスを示す。依存性を持つ命令の場合、第２ＭＳＢはアドレスが６４ビット・バルブのためのものであることを示す。第３から第５ＭＳＢ出力は一時バッファ・アドレスを指定するものである。そしてＬＳＢ出力はどのバケットがカレント・バケットであるかを示し、このバケットはＴＡＬ１２２中のＢＫＴ信号に等しい。
【００８２】ＤＤＣｌ０８と同じく、ＴＡＬ１２２は多数のインプリメンテーション依存（すなわち、特殊なケース）を待つ。先ず、本発明の一実施例では、レジスタ・ファイルのレジスタ番号０は常に０に等しい。斯くして、一つの命令がレジスタ０に書き込み、別の命令がレジスタ０から読み出すことがあっても、これらの命令間には依存性はない。各命令に関し、ＴＡＬ１２２は命令解読論理（ＩＬＤ、図示せず）から３個の信号を受け取る。これらの信号はその命令のソースの一つがレジスタ０であるか否かを通知するものである。それらのソースのうち一つでも確定されると、ＴＡＬ１２２はその命令のその特定の入力に関連する一切の依存性を無視する。
【００８３】ある条件下で別の特殊なケースが発生するが、その条件とはバケット０中の命令がバケット１中のどの命令からも依存されないことが保証されているということである。ＢＫＴｌ＿ＮＯＤＥＰ＿と呼ばれる４ビットの信号がＩＥＵ制御論理（図示せず）からＲＲＣｌ１２に送られ、ＢＫＴ１＿ＮＯＤＥＰ［Ｘ］＝１である場合、ＲＲＣｌ１２は命令４、５、６、または７と命令Ｘとの間の依存性を一切無視すべきものとして扱う。
【００８４】命令７のソース１（Ｉ７Ｓ１）のタグ割り当ての一例を図６、図７のフローチャートに示す。条件付きブロック６０２に示す如く、ＴＡＬ１２２は最初にＩ７Ｓｌがレジスタ０であるか否かを決定する。Ｉ７の第１ソースオペランドがレジスタ０であるならば、タグはゼロに設定され、Ｉ７ＳｌのＩＮＦＯフラグもブロック６０４に示される如く１に設定される。Ｉ７の第１ソースオペランド（Ｓ１）がレジスタ０でない場合、条件付きブロック６０６に示すように、ＴＡＬ１２２は次にＩ７ＳｌがＩ６Ｓ／Ｄに依存するか否かを決定する。Ｉ７Ｓ１がＩ６Ｓ／Ｄに依存する場合、フローはブロック６１０に進む。ここで、ブロック６１０に示すように、Ｉ７Ｓｌのタグは｛１，ＤＢＬＲＥＧ［６］，０，１，０，ＢＫＴ｝に等しいように設定され、Ｉ７Ｓ１のＩＮＦＯフラグはＤＯＮＥ［６］に等しいように設定される。条件付きブロック６０６でテストされた条件のうちどちらかが満たされない場合、フローは条件付きブロック６１２に進む。ここで、ＴＡＬ１２２はＩ７ＳｌがＩ５Ｓ／Ｄに依存しているか否かを決定する。依存性がある場合、フローはブロック６１６に進み、ここでＴＡＬ１２２はＩ７Ｓ１のタグを［１，ＤＢＬＲＥＧ［５］，０，０，１，ＢＴＫ］に設定し、Ｉ７Ｓ１のＩＮＦＯフラグをＤＯＮＥ［５］に設定する。条件付きブロック６１２でテストされた条件が満たされない場合、フローはブロック６１８に進み、ここで、ＴＡＬ１２２はＩ７Ｓ１がＩ４Ｓ／Ｄに依存しているか否かを決定する。
【００８５】図６および図７の残りの部分を一見すれば明らかな如く、Ｉ７Ｓ１がＩ４Ｓ／Ｄ、Ｉ３Ｓ／Ｄ、Ｉ２Ｓ／Ｄ、Ｉ１Ｓ／Ｄ、およびＩ０Ｓ／Ｄに依存しているか否かに基づいて、同じようなタグの決定が行なわれる。これをセクション６２０、６２２、６２４、６２６、および６２８でそれぞれ示す。そして最後に、命令７が命令０から独立しているか、あるいは条件付きブロック６３０でテストされるように、バケット１の全ての命令が命令０から独立しているならば（すなわち、ＢＫＴ１＿ＮＯＤＥＰ［０］＝１であるならば）、フローはブロック６３２に進み、ここでＴＡＬ１２２はＩ７Ｓｌのタグを｛０，Ｉ７Ｓｌ｝に設定し、Ｉ７ＳｌのＩＮＦＯフラグを１に設定する。上記の例で留意すべきことは、Ｉ７Ｓ１タグ信号にはレジスタ・ファイル１１７のレジスタ・ファイル・ポートＭＵＸｅｓが直接送られることである。１７のＳ１入力がレディーになると、イシュアｌ１８に通知するためにＩ７Ｓ１ＩＮＦＯ信号がイシュア１１８に送られる。
【００８６】図１１にイシュアｌ１８の代表的ブロック図を示す。推奨実施例では、確保する必要のある各リソース（機能ユニット）ごとに、イシュア１１８はスキャナーブロック１００２を持っている。この例では、イシュア１１８はスキャナーブロックＦＵｌ、ＦＵ２、ＦＵ３、ＦＵ４、……、ＦＵｎを持っている。機能ユニットヘの要求は既知の方法で解読論理（図示せず）によって命令情報から発せられる。これらの要求はバス１２３を経てスキャナーブロック１００２に送られる。各スキャナーブロック１００２は命令Ｉ０からＩ７をスキャンし、そのサイクルでサービスされるように、対応する機能ユニットの最初の要求を選択する。
【００８７】複数のレジスタ・ファイル（整数、浮動小数および／またはブール値）の場合、イシュア１１８は異なるレジスタ・ファイルに格納されたオペランドを持つ命令を発行することができる。例えば、ＡＤＤ命令は浮動小数レジスタ・ファイルからの第一オペランド、および整数レジスタからの第二オペランドを持っことができる。一般に、異なるレジスタ・ファイルからのオペランドを持つ命令は高い発行優先順位を与えられる（すなわち、これらの命令は最初に発行される）。この発行手法により、プロセッサの実行時間および機能ユニットのリソースの節約が可能となる。
【００８８】ＩＥＵｌ００に２個のＡＬＵが含まれている更なる実施例では、ＡＬＵのスキャンは更に複雑になる。実行速度を上げるために、１個のＡＬＵスキャナーブロックはＩ０からＩ７をスキャンし、もう１個のＡＬＵスキャナーブロックはＩ７からＩ０をスキャンする。このようにして２個のＡＬＵ要求が選択される。この方法では、バケット１にあるＡＬＵ命令の前にバケット１にあるＡＬＵ命令が発行されることが可能であり、同時にスキャニングの効率の向上が計れる。
【００８９】スキャナー出力１００３はＭＵＸｉｎｇｌｏｇｉｃ１００４によって選択される。ＭＵＸ１００４の１組のＳＥＬｅｃｔ入力１００６はパス１２０を経てＴＡＬ１２２から３個の８ビットベクトル（各オペランドに１個）を受け取る。ベクトルは８個の命令のうちどれが依存性なしの命令で、発行可能な状態にあるかを通知する。イシュア１１８は命令を発行する前にこの情報を待たなければならない。イシュア１１８はこれらのベクトルを監視し、これら３個のベクトルの全てが特定の命令に対してハイになると、イシュア１１８はその命令がレディーであると関知する。必要な機能ユニットがレディーになると、イシュアはその命令を発行して、選択信号をレジスタ・ファイル・ポートＭＵＸｅｓに送り、対応する命令の出力をレジスタ・ファイル１１７に送ることができる。
【００９０】本発明の推奨実施例では、イシュア１１８が済んだ後、イシュア１１８は各レジスタ・ファイルごとに２個の８ビットベクトルをＲＲＣ１１２に返しＭＵＸＯＵＴｐｕｔｓ１００８を通してパス１２１に送る。これらのベクトルはこのサイクルでどの命令が発行されたかを示し、ＲＰＭｓ１２４用のラインを選択するために用いられる。
【００９１】各レジスタ・ファイルが同時に発行できる命令の最大数は使用可能なレジスタ・ファイル読み出しポートの数で制約されている。データ依存性に先行する未完了の命令があると、命令の発行が抑制されることがある。更に、必要な機能ユニットが別の命令に割り当てられていても命令の発行が抑制されることがある。
【００９２】ロード・イミディエイト命令、ブール値オペレーション、および相対的条件分岐のような幾つかの命令は他に依存せずに発行できる。なぜならば、レジスタ・ファイル読み出しポート以外のリソースを必要としない、あるいは依存性を持つ可能性がないからである。
【００９３】ＲＲＣ１１２の最後のセクションはレジスタ・ファイル・ポートＭＵＸ（ＲＰＭ）セクション１２４である。ＲＰＭｓ１２４の役割は、イシュア１１８がレジスタ・ファイル１１７からデータを取得して各命令が使用できるような方法を提供することである。ＲＰＭｓ１２４はバス１２６を経てタグ情報を受け取り、ＲＰＭｓ１２４用の選択ラインはバス１２１を経てイシュア１１８から、またコンピュータのＩＥＵ制御論理からも得られる。選択されたタグは、バス１２８を用いてレジスタ・ファイル１１７の所定の１組のポート１１９に送られる読み出しアドレスで構成されている。
【００９４】ＲＰＭｓ１２４の数とデザインはレジスタ・ファイルの数、および各レジスタ・ファイル上のポートの数に依存する。図４にＲＰＭｓ１２４の一実施例を示す。この実施例において、ＲＰＭｓ１２４は３個のレジスタ・ポート・ファイルＭＵＸｅｓ、４０２，４０４、および４０６で構成されている。ＭＵＸ４０２はＴＡＬ１２２によって生成されたソース・レジスタ・フィールドＳ１に対応する命令０－７のタグを入力としい受け取る。ＭＵＸ４０４はＴＡＬ１２２によって生成されたソース・レジスタ・フィールドＳ２に対応する命令０－７のタグを入力として受け取る。ＭＵＸ４０６はＴＡＬ１２２によって生成されたソース／行き先レジスタ・フィールドＳ／Ｄに対応する命令０－７のタグを入力として受け取る。ＭＵＸｅｓ４０２、４０４、および４０６の出力はバス１２８を通してレジスタ・ファイル１１７の読み出しアドレス・ポートに接続される。
【００９５】ＲＲＣ１１２およびイシュア１１８によって、プロセッサは命令を同時に、しかもプログラムに依る順序とは別の順序で実行できる。本発明で使用されるＩＥＵは同一承継人の、関連特許出願、米国出願番号０７／８１７，８１０号（代理人整理番号ＳＰ０１５／１３９７．０２８０００１）に開示されている。この開示はここに参照文献として含まれているものとする。
【００９６】本発明の様々な実施例を上述したが、これらはあくまでも例であり、本発明を制限するものではないことは無論である。従って、本発明の範囲および広がりは上記の実施例で制限されるものではなく、下記の特許請求範囲およびそれと同等のものによってのみ定義されるものである。

【出願人】	【識別番号】０００００２３６９【氏名又は名称】セイコーエプソン株式会社
【出願日】	平成５年３月２６日（１９９３．３．２６）
【代理人】	【識別番号】１０００９２４９５【弁理士】【氏名又は名称】蛭川昌信（外７名）
【公開番号】	特開２０００－１４８４８７（Ｐ２０００－１４８４８７Ａ）
【公開日】	平成１２年５月３０日（２０００．５．３０）
【出願番号】	特願２０００－８１４７（Ｐ２０００－８１４７）