(57)【特許請求の範囲】
【請求項１】
クロックと、
複数の行および１つまたは複数のポートを有する電子ハードウェア構造であって、各行が前記ポートのうち１つのポートを介して書き込まれた待ち時間ベクトルを記録するように構成され、格納された待ち時間ベクトルは前記クロックに応答する電子ハードウェア構造と、
あらかじめ選択された数のクロック・サイクルだけ入力信号を遅延させるように構成されたシャドウ・レジスタの組の列であって、各組が前記電子ハードウェア構造の各行に対して１つのレジスタを有するシャドウ・レジスタの組の列と、
を備える装置。
【請求項２】
さらに、
マルチプレクサであって第１の入力、第２の入力および出力を有し、前記第１の入力は待ち時間ベクトルを受け取り、前記第２の入力は前記シャドウ・レジスタの組の列の出力から信号を受け取り、前記マルチプレクサの出力は、前記電子ハードウェア構造と前記シャドウ・レジスタの組の列との両方の入力に並列に接続されているマルチプレクサ
を備えた請求項１記載の装置。
【請求項３】
複数のレジスタを含むレジスタ・ファイルと、
命令を実行する複数の実行ユニットであって、前記命令の一部が前記レジスタから読出しと書込みのうち１つを実行する複数の実行ユニットと、
前記レジスタの予想されるレジスタ待ち時間を追跡するレジスタ待ち時間表と、
前記レジスタ待ち時間表の待ち時間を更新するクロックと、
あらかじめ選択された数のクロック・サイクルだけ入力信号を遅延させるように構成されたシャドウ・レジスタの組の列と、
を備えるプロセッサ。
【請求項４】
さらに、
マルチプレクサであって、待ち時間ベクトルを受け取る第１の入力、前記シャドウ・レジスタの組の列から信号を受け取る第２の入力、および前記レジスタ待ち時間表と前記シャドウ・レジスタの組の列との両方の入力に並列に接続されている出力とを有するマルチプレクサ
を備えた請求項３記載のプロセッサ。
【請求項５】
複数の予想される待ち時間を、レジスタ待ち時間表の特定のレジスタに対応する行の一部に更新書き込みするステップと、
クロック・パルスに応答して前記行のうち他の行に残っている予想される待ち時間を削減するステップと、
シャドウ・レジスタの組の列によってあらかじめ選択された数のクロック・サイクルだけ入力信号を遅延させるステップと
を含むプロセッサ内で命令をディスパッチする方法。
【請求項６】
命令のイシュー・グループを受け取るステップと、
前記イシュー・グループの前記命令に割り当てられた前記レジスタの一部の予想される待ち時間から前記イシュー・グループに関して予想される待ち時間を決定するステップと、
前記イシュー・グループによって書き込まれるべきと決定されたレジスタの予想されるレジスタ待ち時間を更新するステップと、
前記イシュー・グループを命令待ち行列に書き込むステップと、
前記イシュー・グループに関して予想される待ち時間が終了したことに応答して、前記イシュー・グループをディスパッチし実行するステップと、
シャドウ・レジスタの組の列によってあらかじめ選択された数のクロック・サイクルだけ入力信号を遅延させるステップと
を含むプロセッサ内で命令を実行する方法。
【請求項７】
命令のイシュー・グループを受け取るステップと、
前記イシュー・グループの前記命令によって書き込まれるべきレジスタに関する待ち時間の内最大の待ち時間を該イシュー・グループに関して予想される待ち時間と定めるステップと、
前記イシュー・グループを命令待ち行列に書き込むステップと、
前記イシュー・グループに関して予想される待ち時間が終了したことに応答して、前記イシュー・グループをディスパッチし実行するステップと、
シャドウ・レジスタの組の列によってあらかじめ選択された数のクロック・サイクルだけ入力信号を遅延させるステップと
を含むプロセッサ内で命令を実行する方法。
【請求項８】
命令を検索する命令フェッチ・ユニットと、
複数のレジスタと、
前記レジスタの予想されるレジスタ待ち時間を追跡するレジスタ待ち時間表であって、所定の命令のディスパッチに応答して所定のレジスタの予想レジスタ待ち時間が更新されるレジスタ待ち時間表と、
複数の命令のイシュー・グループを格納する命令待ち行列と、
前記命令待ち行列から受け取られた各イシュー・グループの前記命令を並列に実行するように整列された複数の実行ユニットと、
前記イシュー・グループを前記命令待ち行列に書き込むスケジューラであって、前記命令待ち行列は特定のイシュー・グループの予想される待ち時間が終了したことに応答して前記特定のイシュー・グループをディスパッチするスケジューラと、
あらかじめ選択された数のクロック・サイクルだけ入力信号を遅延させるように構成されたシャドウ・レジスタの組の列であって、各組が前記レジスタ待ち時間表の各行に対して１つのレジスタを有するシャドウ・レジスタの組の列と、
を備えるプロセッサ。
【請求項９】
さらに、
マルチプレクサであって、待ち時間ベクトルを受け取る第１の入力、前記シャドウ・レジスタの組の最後から信号を受け取る第２の入力、および前記レジスタ待ち時間表と前記シャドウ・レジスタの組の列との両方の入力に並列に接続されている出力とを有するマルチプレクサ
を備えた請求項８記載のプロセッサ。
【請求項１０】
イシュー・グループのスケジューリングに応答して、レジスタ待ち時間表およびシャドウ・レジスタの組の列の両方に、命令のイシュー・グループに割り当てられたレジスタの一部の待ち時間ベクトルを書き込むステップと、
前記実行ユニットが使用可能であるかどうかを決定せずに前記イシュー・グループを実行ユニットへディスパッチするステップと、
前記列へ書き込まれる待ち時間ベクトルをあらかじめ選択された時間だけ遅延するステップと、
前記イシュー・グループの実行に応答して、実行例外およびエラーのうち１つを検出することに応答して前記列から前記レジスタ待ち時間表に前記遅延された待ち時間ベクトルを書き込むステップと
を含む命令を実行し再生する方法。
【発明の詳細な説明】
【０００１】
（発明の背景）
（１．発明の分野）
本発明は一般にコンピュータおよびプロセッサに関し、より詳細には、異なる待ち時間を伴う命令をスケジューリングすることに関する。
【０００２】
（２．関連技術の説明）
プロセッサは、１つまたは複数のメモリ内に格納された命令のシーケンスを検索し実行する。実行された命令の多くは、前記シーケンスのより先の命令にデータ依存性および／または制御依存性を有する。プロセッサは通常、この依存性を尊重する方法で命令をスケジューリングし実行する。
【０００３】
このような依存性の１つは、ソース・オペランドおよび宛先オペランドの使用可能度に関係する。ソース・オペランドおよび宛先オペランドは命令が読み出すおよび書き込む各レジスタ・アドレスであろう。ソース・オペランドは、命令シーケンスのより先の命令が書込みを完了した後、正しいデータが格納されると使用可能になる。宛先オペランドは、命令シーケンスのより先の命令のすべてがアドレスの読出しを完了した後に命令をアドレスへ書き込みできると使用可能になる。多くのプロセッサは命令のオペランドが使用可能であると決定されたことに応じて、命令をスケジューリングし実行する。オペランドの使用可能度を決定することは、各スケジュール・サイクル内で多数のオペランドをチェックしなければならない時には、時間を消費し、命令処理を遅らせるであろう。
【０００４】
最近のプロセッサは、順次（順序どおり）プロセッサの処理スピードよりスピードを増すための種々の機能を含んでいる。このような機能の１つが推論実行である。推論実行においては、プロセッサは実行の前に依存性に関して予想を決定し、実行の後にその予想が真であったかどうかをチェックする。予想が間違っていることが分かった場合、プロセッサは影響を受けた命令を再実行する。推論実行は依存性に関する予想が正確である時に、決定されていない命令の依存性によって起こされる遅延をなくすことができる。いくつかのプロセッサが使用している第２の機能は、スーパースカラ処理である。スーパースカラ処理では、別の入力ポートを伴ういくつかの実行ユニットがある。スーパースカラ・プロセッサは、１つのクロック・サイクルの間にいくつかの命令のイシュー・グループをディスパッチすることができる。イシュー・グループの各命令は、異なる入力ポートにディスパッチされる。推論実行およびスーパースカラ処理は一般に、決定されない命令の依存性を処理する技法を必要とする。
【０００５】
いくつかのプロセッサ・パイプラインをストールし、続く命令を実行する前にオペランドの使用可能度を解決させる。ストール可能なパイプラインは、ストール制御ネットワークを使用してストールを処理する。ストール制御ネットワークは、種々のパイプラインステージからストール・コントローラおよびネットワークへ状態信号を送るためのネットワークを含み、ストール・コントローラからパイプラインの種々のステージへ「ストール」信号または「アドバンス」信号をブロードキャストする。状態信号はストール・コントローラに、その結果を１つのステージから次のステージへ送ってさらに処理できるかどうかを伝える。「アドバンス」信号によって、たとえば、並列フリップ・フロップのバンクが結果を１つのステージから次のステージへ送る。受け取りネットワークおよびブロードキャスト・ネットワークはキャパシタンスおよびそれに関連した過渡時間を伴うワイヤを使用するので、これらのネットワークは時間遅延を起こし、それがパイプラインステージの間で結果を送るために達成可能な最小の時間を制限する。
【０００６】
ストール制御ネットワークの時間遅延は最近のチップではより悪化し、かなりの物理的な大きさに達し、多くのステージを伴うパイプラインを使用することになる。どちらの特性もストール制御ネットワークに必要なワイヤを増加する傾向があるので、キャパシタンスによって起こされる関連した時間遅延を増加させる。
【０００７】
ストール・ネットワークがない場合、プロセッサは各ディスパッチ・サイクルの間１つのイシュー・グループをスケジューリングする必要がある。イシュー・グループの各命令のオペランドとして現れるレジスタが次のイシュー・グループをディスパッチする間の時間に使用可能かどうかをプロセッサが決定しなければならない場合、このようなタイミング要件は達成するのが困難である。これらのタイミング要件はイシュー・グループの大きさが増大するにつれて達成するのがさらに困難になる。
【０００８】
本発明は上記の１つまたは複数の問題を克服するかまたは少なくともその問題の影響を削減することに関する。
【０００９】
（発明の概要）
本発明の一態様では、装置が提供される。この装置はパルスを生成するクロックと、複数の行および１つまたは複数のポートを有する電子ハードウェア構造を含む。各行は、ポートのうち１つのポートを介して書き込まれる別の待ち時間ベクトルを記録するように構成される。そこに記録された待ち時間ベクトルはクロックに応答する。
【００１０】
本発明の別の態様では、プロセッサ内で命令をディスパッチする方法が提供される。この方法は複数の予想される待ち時間をレジスタ待ち時間表の行の一部で更新し、他の行に残っている予想される待ち時間をクロック・パルスに応答して削減することを含む。その部分の行は特定のレジスタに対応する。
【００１１】
本発明の他の目的および利点は、次の詳細な説明を読み、図面を参照すると明らかになろう。
【００１２】
（具体的な実施形態の詳細な説明）
本発明の例としての実施形態が次に説明される。明確にするために、本明細書では実際の実装におけるすべての機能が説明されているわけではない。もちろん、このような実際の実施形態の開発においては、実装に特有な多くの決定を行って、システム関連の制約や業務関連の制約に従うなど、実装によって変化する開発者の特有の目的を達成しなければならないことを理解されよう。さらに、このような開発努力は複雑で時間のかかるものである場合があるが、この開示から利点を得られる当業者であれば日常業務の仕事であることを理解されよう。
【００１３】
今後、イシュー・グループは、実質的に同時、すなわち同じクロックまたはディスパッチ・サイクルの間にディスパッチされ実行される命令のグループを意味する。いくつかの実施形態では、イシュー・グループは命令を１つだけ含む。
【００１４】
特定の命令における「実際の待ち時間」は、その特定の命令がレジスタに書き込むかまたはそこから読み出すかによって異なる。特定の命令がレジスタから読み出す場合、「実際の待ち時間」は命令シーケンスのより先の命令がレジスタへの書込みを実行するための時間と定義される。特定の命令がレジスタに書き込む場合、「実際の待ち時間」は命令シーケンスのより先の命令がレジスタへの書込みとそこからの読出しを実行するための時間である。本発明の実施形態は、「予想される待ち時間」に基づいて各命令をスケジューリングする。本発明の実施形態は、命令が読出しまたは書込みのどちらを実行する場合でも「予想される待ち時間」を使用する。
【００１５】
本発明の実施形態は、「実際の」レジスタ待ち時間ではなく「予想される」レジスタ待ち時間の決定に基づいて命令をスケジューリングする。「予想される」レジスタ待ち時間はプロセッサの起動時にゼロにリセットされる。次いで、「予想される」レジスタ待ち時間は命令タイプに基づいて更新される。たとえば、一実施形態では、任意のロード命令、任意の整数計算命令、および任意の浮動小数点計算命令によって書き込まれたレジスタに関して、それぞれ２クロック・パルス、１クロック・パルス、５クロック・パルスで予想されるレジスタ待ち時間を更新する。予想されるレジスタ待ち時間への更新の特定の値は、特定のハードウェア実装態様によって異なり、本発明にとっては本質的ではない。スケジューリングは予想されるレジスタ待ち時間を使用するので、いくつかの実施形態は新しい命令がスケジューリングされるごとに予想を更新し、他の実施形態は新しい命令がディスパッチされ実行されるごとに予想を更新する。
【００１６】
図１は、命令をスケジューリングして実行するのに使用されるレジスタ待ち時間表１０に関する一実施形態を示す。レジスタ待ち時間表１０はいくつかの行１４、１６、１８を有する電子ハードウェア構造であり、対応するレジスタ（図示せず）のバイナリの待ち時間ベクトル、すなわち、レジスタ待ち時間を格納する。レジスタ待ち時間表１０はまた、それぞれそこから待ち時間ベクトルを読み出し、そこへ待ち時間ベクトルを書き込むための少なくとも１つのポート１２を有する。レジスタ待ち時間表１０の各行１４、１６、１８は、クロック２０からのパルスに応答して残りの予想される待ち時間間隔をカウントダウンする、すなわち行１４、１６、１８は、時間内の予想されるレジスタ待ち時間を追跡する。
【００１７】
図２は図１のレジスタ待ち時間表１０の行１４、１６、１８に関する１つの特定の実施形態２２を示すが、本発明はこのように限定されるものではない。示された実施形態では各行１４、１６、１８はシフト・レジスタであり、ベクトルをシフトする、すなわち２で整数除算することによってそこに格納された待ち時間ベクトルをカウントダウンする。レジスタ待ち時間表１０の１４、１６、１８の各行は、「有限状態マシン」として作用する。「有限状態マシン」は、ハードウェアと１つまたは複数のレジスタの組合せであり、ハードウェアはレジスタ内に格納された物理量を発展させるように構成されており、たとえば、行１４、１６、１８は予想されるレジスタ待ち時間を一時的に発展させ、現在の値を反映するように構成されている。
【００１８】
図２は、図１のレジスタ待ち時間表１０の一実施形態において行１４、１６、１８のうち１つの状態を時間発展させたところを示す。最初の時に、制御論理（図示せず）はＭバイナリ桁のバイナリ待ち時間ベクトル２４の並列ロードをシフト・レジスタ内に作成し、Ｍバイナリ桁を格納する。Ｎクロック・サイクルの待ち時間に対応する待ち時間ベクトルは値１を伴うＮ個の連続する桁および、値０を有するＭ−Ｎ個の連続する桁を有する。図１のクロック２０からの第１のパルス２５の後、レジスタは１つのバイナリ桁だけ待ち時間ベクトル２４をシフトし、値１を伴うＮ−１個の連続する桁および、値０を伴うＭ−Ｎ＋１個の連続する桁を有する新しい待ち時間ベクトル２６を生成する。図１のクロック２０から第２のパルス２７の後、レジスタは別のバイナリ桁だけ待ち時間ベクトル２６をシフトし、値１を伴うＮ−２個の連続する桁および、値０を伴うＭ−Ｎ＋２個の連続する桁を有する新しい待ち時間ベクトル２８を生成する。Ｎクロック・サイクルの後、待ち時間ベクトル（図示せず）は値０を伴うＭ桁を含むことになる。図１のレジスタ待ち時間表１０の各行１４、１６、１８は、そこに格納された待ち時間ベクトルを図１のクロック２０の各パルスで１バイナリ桁だけシフトする。レジスタ待ち時間表１０は、予想される待ち時間をシフトすることにより予想されるレジスタ待ち時間を「追跡」し、それによって予想されるレジスタ待ち時間の残りを格納する。
【００１９】
予想されるレジスタ待ち時間の残りは、最後の更新から経過した時間を引いた後に残る予想されるレジスタ待ち時間である。種々の実施形態は命令を検索すること、命令をスケジューリングすること、命令をディスパッチすることに応答して、または実行の前の命令処理シーケンス内の別の時間のいずれかで、予想されるレジスタ待ち時間を更新することができる。
【００２０】
別の実施形態は他の方法を使用して、レジスタ待ち時間表１０の各行１４、１６、１８内の予想されるレジスタ待ち時間の残りを追跡することができる。このような一実施形態では、レジスタ待ち時間表の行１４、１６、１８はデクリメントするカウンタとして作用する、すなわち、クロック２０の各パルスで現在の予想されるレジスタ待ち時間から１を引く場合がある。行１４、１６、１８は、そこに格納された予想される待ち時間を修正して現在の物理値を反映する「有限状態マシン」として作用する。
【００２１】
図３は、図１のレジスタ待ち時間表１０を使用して命令のディスパッチをスケジューリングし実行するプロセッサ３０の一部を示す。プロセッサ３０は複数の内部レジスタ３２、３３、３４を含み、命令によって読み出されおよび書き込まれるデータを格納する。レジスタ３２、３３、３４はレジスタ・ファイル３６を形成する。いくつかの実施形態では、レジスタ待ち時間表１０およびレジスタ・ファイル３６は、同じ数の読出しポート１２、３７および同じ数の書込みポート１２、３７を有する。レジスタ待ち時間表１０の各行１４、１６、１８は、レジスタ３２、３３、３４のうち１つに関して静的待ち時間ベクトルを格納する。レジスタ待ち時間表１０およびレジスタ・ファイル３６は両方とも、内部レジスタ３２、３４、３６のそれぞれに関して１つの行を有する。プロセッサ３０は複数の実行ユニット４６、４８を有する。プロセッサ３０は、その中に命令があるレジスタ３２、３３、３４が使用可能になると予想される時間においてまたはその時間の後に、すなわち、レジスタ待ち時間表１０の待ち時間ベクトルによって決定されたように、実行ユニット４６、４８にディスパッチされるべき命令のイシュー・グループをスケジューリングする。
【００２２】
図３をさらに参照すると、プロセッサ３０はレジスタ待ち時間表１０を使用してプログラム依存性を静的に実行する、すなわち、命令のタイプの関数である予想された依存性を実行する。レジスタ待ち時間表１０はレジスタ３２、３３、３４の一部の待ち時間に対して、命令が読出しか書込みかの静的な予想を提供する。プロセッサ３０は、静的な予想される待ち時間、すなわちより先の命令の予想された待ち時間がレジスタ３２、３３、３４の一部へ書込みを終了するまで、命令をディスパッチしない。静的な予想される待ち時間に基づいたスケジューリングは、命令依存性の違反の数を削減することができる。
【００２３】
代替の実施形態では、命令が最終的には予想される正しい待ち時間で実行ステージに到着するように、命令は実行ステージより早くパイプラインステージにスケジューリングされディスパッチされる。
【００２４】
図４Ａは、図１のレジスタ待ち時間表１０を使用するパイプライン式プロセッサ５０を示す。フェッチャ／復号器５２は、メモリ（図示せず）から命令を検索し、ハードウェア実行ユニット４６、４８上で実行可能な命令の復号化されたイシュー・グループを生成する。リネーマ５４はプロセッサ５０の内部にあるレジスタ３２、３３、３４の一部を、復号化された命令のダミー・オペランドへ割り当てる。スケジューラ５６は各イシュー・グループに関して予想される待ち時間を静的に決定し、イシュー・グループおよび予想される待ち時間を命令待ち行列５８内の行（図示せず）に書き込む。「静的に決定する」とは、プロセッサ・ハードウェアが固定された「予想される待ち時間」を命令クラスに依存する命令に割り当てることを意味する。たとえば、一実施形態では、すべてのロード命令、すべての整数計算命令およびすべての浮動小数点命令によって書き込まれたレジスタに、２クロック・パルス、１クロック・パルスおよび５クロック・パルスなどの各予想される待ち時間を割り当てる。命令待ち行列５８はイシュー・グループの命令の実行が並列に開始するように、複数の整列した実行ユニット４６、４８に各イシュー・グループをディスパッチするように構成される。プロセッサ５０は、レジスタ待ち時間表１０を使用して各イシュー・グループの予想される待ち時間、すなわち、イシュー・グループのすべての命令がディスパッチの準備をする時間を決定する。リタイアメント・ユニット６０は、イシュー・グループが正しく実行されていれば、イシュー・グループの命令をリタイアし命令待ち行列５８を更新する。
【００２５】
図４Ｂは、図４Ａのプロセッサ５０の一実施形態に関するパイプライン６２を示す。フェッチ／復号ステージ（ＦＤ）では、フェッチャ／復号器５２は命令のイシュー・グループを生成してリネーマ５４に送る。リネーマステージ（ＲＥ）では、リネーマ５４は内部レジスタ３２、３３、３４の一部を命令のダミー・オペランドへ割り当てる。待ち時間決定ステージ（ＬＡ）では、スケジューラ５６は図４Ａのレジスタ待ち時間表１０の中にある命令のレジスタ３２、３４、３６の待ち時間ベクトルを検索し、命令のソース・レジスタが使用可能になる前に予想されるクロックの数を決定する。ＬＡステージでは、スケジューラ５６はまたイシュー・グループ自体に関して予想される待ち時間を決定する。待ち行列ステージ（ＱＵ）では、いくつかの実施形態ではスケジューラ５６はイシュー・グループに関して予想される待ち時間の決定を完了する。ＱＵステージでは、スケジューラ５６はイシュー・グループを命令待ち行列５８内のアドレスに書き込み、予想される待ち時間に関してバイナリの符号セグメントを付与する。ＱＵステージでは、スケジューラ５６はレジスタ待ち時間表１０の待ち時間ベクトルを更新する。実行ステージ（ＥＸ）では、命令待ち行列５８はイシュー・グループに関して予想される待ち時間をカウントダウンした後に、次のイシュー・グループをディスパッチして実行する。リタイアメントステージ（ＲＴ）では、リタイアメント・ユニット６０は正しく実行された命令をリタイアする。当業者であれば、プロセッサ・パイプライン６２内のＦＤ、ＲＥ、ＬＡ、ＱＵ、ＥＸおよびＲＴの各ステージの区分は、図４Ｂに現れるように区別できない場合があることを理解されるであろう。たとえば、１つまたは複数のステージが他のステージと重複する場合がある。
【００２６】
図４Ｂをさらに参照すると、ステージＦＤ、ＲＥ、ＬＡ、ＱＵ、ＥＸおよびＲＴは代表的なものにすぎず、種々の代替の実施形態に存在するようなステージを網羅的または限定的に表したものではない。したがって、パイプライン６２のステージの正確な構造は本発明の実施には直接関係がない。
【００２７】
図５は、図１、図３および図４Ａのレジスタ待ち時間表１０で命令をスケジューリングする方法６３を示すフローチャートである。ブロック６４では、スケジューラ５６は入力イシュー・グループから命令のオペランドとして現れるレジスタ３２、３３、３４の一部に関して予想される待ち時間を読み出す、すなわち図４Ｂの中のＬＡステージである。ブロック６５では、スケジューラ５６はそこに現れるレジスタ３２、３３、３４の一部の予想される待ち時間から、イシュー・グループに関して予想される待ち時間を生成する、すなわち、図４ＢのＬＡステージまたはＱＵステージである。一実施形態では、イシュー・グループの予想される待ち時間は、イシュー・グループの命令によって書き込まれるべきレジスタに関する最大の待ち時間と等しい。ブロック６６では、命令待ち行列５８は、イシュー・グループの予想される待ち時間が終了したことに応答して実行ユニット４６、４８にイシュー・グループをディスパッチする、すなわち、図４ＢのＱＵステージからＥＸステージである。ブロック６７では、スケジューラ５６はイシュー・グループによってレジスタ３２、３３、３４のうちどれが書き込まれるかを決定する、すなわち、ＱＵステージである。ブロック６８では、スケジューラ５６はたとえばレジスタ３２、３３、３４の残りの待ち時間からイシュー・グループの待ち時間を引くことによって、イシュー・グループによって書き込まれるレジスタ３２、３３、３４の一部に関してレジスタ待ち時間表１０を更新する。ブロック６９では、レジスタ待ち時間表１０はクロック・パルスに応答して、イシュー・グループによって書き込まれない各レジスタの予想される待ち時間を減少させる。ブロック６７、６８および６９は１レジスタについてレジスタごとに実行される。一実施形態では、更新は図４ＢのステージＱＵで発生する。他の実施形態では、更新は図４ＢのステージＥＸで発生する、すなわちスケジューリングの間ではなくディスパッチの時に起きる。
【００２８】
さらに図５を参照すると、種々の実施形態はブロック６８で異なる公式を使用して予想されるレジスタ待ち時間を更新する。たとえば、更新はレジスタ待ち時間表１０の予想されるレジスタ待ち時間を、現在の予想されるレジスタ待ち時間と、レジスタに書き込まれる次のイシュー・グループの予想される待ち時間のうち大きな方で置き換える。レジスタを更新するための他の公式も可能である。種々の公式は予想されるレジスタ待ち時間の更新を、各イシュー・グループのディスパッチ時またはディスパッチ前に可能にする。
【００２９】
図４Ａを参照すると、命令待ち行列５８はイシュー・グループを連続的にディスパッチする循環バッファでよい。命令待ち行列５８のポインタ（図示せず）は、ディスパッチされた最後のイシュー・グループを示す。命令待ち行列５８は次のイシュー・グループに関して残りの待ち時間をカウントダウンし、次のイシュー・グループの待ち時間が終了したことに応答して、ポインタを進めて次のイシュー・グループをディスパッチする。命令待ち行列５８は非命令イシュー・グループ、すなわち実行動作のないイシュー・グループを、待ち時間がカウントダウンされているディスパッチ・サイクルの間にディスパッチする。実行ユニット４６、４８は非命令イシュー・グループを実行せず、リタイアメント・ユニット６０はそこからの結果をアーキテクチャの状態にゆだねずに、非命令イシュー・グループをリタイアする。実施形態によっては、実行ユニット４６、４８およびリタイアメント・ユニット６０は、保持された１つまたは複数の特別ビットによって非命令イシュー・グループを認識し、「非命令」状態を示す。こうして、図４Ａのプロセッサ５０は、実行の準備ができていると予想されるイシュー・グループがない時には、図４Ｂの命令パイプライン６２をストールしない。図４Ｂのパイプライン６２におけるＲＥステージの後の例外または実行エラーに応答して、図４Ａのプロセッサ５０は非命令イシュー・グループをディスパッチし、実行ユニット４６、４８は、そこから命令を実行しない。図４Ａのプロセッサ５０は他の装置および／または待ち行列を有し、図４Ｂのパイプライン６２のＬＡステージより早いステージで発生するエラーを処理する。図４Ｂのパイプライン６２はストール可能なパイプラインにおけるように動作速度を低減する可能性のあるストール・ネットワークを有しない。
【００３０】
図４Ａおよび図５を参照すると、ブロック６８においてプロセッサ５０は第２の公式を使用してレジスタ待ち時間表１０を更新することができる。たとえばＩＧ１とＩＧ２など２つの連続的なイシュー・グループのディスパッチの間に、プロセッサ５０は第２のイシュー・グループの予想される待ち時間に等しいＸ個の非命令イシュー・グループをディスパッチする、すなわち、ＸはＩＧ２に関して予想される待ち時間である。スケジューリングにおいてＩＧ２による更新が起きた場合、すなわち、ブロック６８がブロック６４または６５と同時である場合、上記の第１の更新公式は後者のイシュー・グループの待ち時間を多く見積もりすぎた可能性がある。たとえば、次のイシュー・グループＩＧ３はＩＧ２に関してＸ個の非命令イシュー・グループがディスパッチされている間、命令待ち行列５８の中で待つ。レジスタ待ち時間表１０の予想は、ＩＧ２のディスパッチと完了の間の時間を考慮するが、Ｘ個の非命令がディスパッチされている間の待ち時間は考慮しない。
【００３１】
さらに図４Ａおよび図５を参照すると、ＩＧ２がスケジューリングされている間に待ち時間表を更新するための第２の公式は２つのステップを有する。まず、スケジューラ５６はＩＧ２の予想される待ち時間Ｘをレジスタ待ち時間表１０の予想されるレジスタ待ち時間のすべてから差し引く。負の予想されるレジスタ待ち時間はゼロと見なされる。第２に、スケジューラ５６は残りの予想されるレジスタ待ち時間とイシュー・グループＩＧ２の待ち時間のうち大きい方によってレジスタ待ち時間表１０の各残りの予想されるレジスタ待ち時間を置き換える。これはレジスタに書き込まれる。第２の公式を使用する実施形態はより短い待ち時間を、続くイシュー・グループすなわちＩＧ３にあてることができる。
【００３２】
図６は、図４Ａのプロセッサ５０における命令の処理に関する方法７０のフローチャートである。ブロック７１で、スケジューラ５６はリネーマ５４から新しい命令のイシュー・グループを受け取る。ブロック７２で、スケジューラ５６はレジスタ待ち時間表１０の中の予想されるレジスタ待ち時間から、イシュー・グループに関して予想される待ち時間を決定する。一実施形態では、予想される待ち時間はレジスタ３２、３３、３４の一部の最大の待ち時間であり、これはイシュー・グループの命令のソース・オペランドである。ブロック７３では、スケジューラ５６はイシュー・グループおよび予想される待ち時間を、命令待ち行列５８内の次の位置に書き込む。ブロック７４では、命令待ち行列５８はイシュー・グループの予想される待ち時間が終了したことに応答して、イシュー・グループを実行ユニット４６、４８にディスパッチする。ブロック７５では、スケジューラ５６はイシュー・グループがレジスタ３２、３３、３４のそれぞれに書き込むかどうかを決定する。ブロック７６では、スケジューラ５６はディスパッチされたイシュー・グループによって書き込まれると決定されたレジスタ３２、３３、３４の一部の待ち時間を更新する。ブロック７７では、クロック２０はクロック・パルスに応答して、レジスタ待ち時間表１０のレジスタ３２、３３、３４のイシュー・グループによって書き込まれない一部の待ち時間を減少させる。ブロック７６、７７で実行される待ち時間の更新および減少は、ブロック７２において続くイシュー・グループのスケジューリングに関して、レジスタ待ち時間表１０内の待ち時間を「追跡」する。
【００３３】
図７は、図１、図３および図４Ａのレジスタ待ち時間表１０に関する再生構造１００の一実施形態を示す。回線１０２は入力待ち時間ベクトルをレジスタ待ち時間表１０へ運ぶ。回線１０２はマルチプレクサ（ＭＵＸ）１０４の入力の第１の組に接続する。ＭＵＸ１０４の出力はレジスタ待ち時間表１０の書込みポート１０８および、シャドウ・レジスタ１１２の第１の組の書込みポート１１０に接続する。図１および図３に示されるように、シャドウ・レジスタ１１２の第１の組は、レジスタ待ち時間表１０の各行１４、１６、１８に関して別のレジスタを有する。シャドウ・レジスタ１１２の第１の組は、直列に接続された出力および入力を有するシャドウ・レジスタ１１２、１１６と同じ組の列１１４の第１の成分である。クロック１２２はシャドウ・レジスタ１１２、１１６のイネーブル入力１１８、１２０を制御し、その結果、クロック・パルスにより、データは列１１４に送られるようにされる。図示された列１１４は、Ｑクロック・パルスだけ遅延されているレジスタ待ち時間表１０の状態を出力する。シャドウ・レジスタ１１６の最後の組の出力１２４は、ＭＵＸ１０４の入力１２６の第２の組に接続する。再生制御１２８は、入力待ち時間ベクトルに関して回線１０２を選択するか、または、シャドウ列１１４によって遅延された待ち時間ベクトル、すなわち再生された待ち時間ベクトル関して第２の入力１２６を選択するかのいずれかである。
【００３４】
図７をさらに参照すると、再生制御１２８は回線１０２から新しい待ち時間を格納するか、または回線１２６からレジスタ待ち時間表１０へクロック１２２のＱサイクルだけ遅延された古い待ち時間ベクトルを再コピーするかのいずれかを選択することができる。列１１４のシャドウ・レジスタ１１２、１１６の組のそれぞれは、再生された待ち時間ベクトルを、クロック１２２の１サイクル分だけ遅延する。再生制御１２８は、例外または実行エラーに応答して、遅延された待ち時間ベクトルをレジスタ待ち時間表１０に再コピーすることを選択する。再コピーのステップは、図４Ｂのパイプライン６２の残りをレジスタ待ち時間表１０の遅延されたコピーで再生することによって、ＲＥステージの後のパイプラインステージに発生するエラーおよび（１つまたは複数の）例外からの回復を可能にする。ハードウェア（図示せず）が例外および／またはエラーを検出し、再生を順序づけるための時間遅延は、必要な遅延および列１１４の長さを決定する。したがって、列１１４の長さは実装態様に依存する。
【００３５】
図４Ａ、図４Ｂおよび図７を参照すると、レジスタ待ち時間表１０における待ち時間ベクトルの再生は、例外エラーおよび／または実行エラーを処理および／または修正するように順序づけられる場合がある。レジスタ待ち時間表１０は、イシュー・グループに関連づけられたより早い状態に戻り、再ディスパッチされ再実行されて、図４Ａ〜４Ｂのストール不能パイプライン５０、６２内の例外エラーおよび／または実行エラーから回復する。再生構造１００は、図１、図３、図４Ａのレジスタ待ち時間表の待ち時間ベクトルを遅延し再生する手段であり、再生によって図４Ｂのストール不能パイプライン６２内の実行例外およびエラーを処理するための実施形態でもある。
【００３６】
図８は、図７の再生構造１００でレジスタ待ち時間表１０の待ち時間ベクトルを再生する方法１３４を示すフローチャートである。ブロック１３５では、図３または図４Ａのプロセッサ３０、５０はＲＥステージの後に図４Ｂのパイプライン６２の一部の再生をするかどうかを決定し、たとえば、実行例外またはエラーから回復する。ブロック１３６では、図３または図４Ａのプロセッサ３０、５０が再生することを決定した場合に、再生制御１２８はＭＵＸ１０４へ新しい待ち時間ベクトル、すなわち、更新を運ぶ回線１０２を選択する。ブロック１３８では、スケジューラ５６は新しい待ち時間ベクトルをレジスタ待ち時間表１０に書き込むことによって、レジスタ待ち時間表１０を更新する。スケジューラ５６は同時に、その更新をシャドウ・レジスタ１１２の第１の組に書き込む。ブロック１４０では、クロック１２２からのタイミング・パルスは、待ち時間ベクトルをシャドウ・レジスタ１１２、１１６の組の列１１４へ送る。ブロック１４２では、再生コントローラ１２８はＭＵＸ１０４の第２の入力１２６を選択し、ＲＥステージの後に、図４Ａのプロセッサ５０がパイプライン６２の再生を決定したことに応答して、シャドウ・レジスタ１１６の最後の組から遅延された待ち時間ベクトルを受け取る。ブロック１４４では、再生構造１００は、ＭＵＸ１０４から再生された待ち時間ベクトルで、レジスタ待ち時間表１０およびシャドウ・レジスタ１１２の第１の組を更新する。図４Ａの命令待ち行列５８は次いで、レジスタ待ち時間表１０に関して再コピーされ遅延された入力に関連づけられたイシュー・グループを再ディスパッチすることによって再生を開始する。
【００３７】
このようにして、本発明は異なる待ち時間の命令の実行を静的にスケジューリングして、実行の時にオペランドを使用可能にするメカニズムを提供する。このメカニズムはパイプラインをストールする必要なくイシュー・グループが使用可能になり実行できるように、オペランドの予想される使用可能度を前もって決定し、必要であれば非命令をディスパッチする。したがって、本発明はこれに限定されるものではないが、本発明はストールではなく再生を使用しているようなストール不能なパイプラインで特に役に立つ。本発明はこのようなストール不能なパイプラインで、これまでは非ユニット待ち時間の命令に直面した時にパイプラインをストールすることによって導入されてきた遅延の導入を可能にする。
【００３８】
本発明はその教示から利益を受ける当業者であれば明らかな、異なるが等化な方法で修正、実行できるため、上記に開示された特定の実施形態は例示のためのものである。さらに、ここに示された構造または設計の詳細は、首記の請求項で記述される以外の限定を目的としていない。したがって、上記に開示された特定の実施形態は変更または修正される可能性があり、このような変形例のすべては本発明の範囲と精神の中にあることは明らかである。したがって、ここで求められている保護は首記の請求項で示されている通りのものである。
【図面の簡単な説明】
【図１】  レジスタ待ち時間表を示すレベルの高い図である。
【図２】  クロック・パルスで、図１のレジスタ待ち時間表の行の中にある待ち時間ベクトルを更新するための一実施形態を示す図である。
【図３】  図１のレジスタ待ち時間表を使用して命令をスケジューリングし、並列実行ユニット上で実行するプロセッサの一部を示す図である。
【図４Ａ】  命令をスケジューリングし並列実行ユニット上で実行するプロセッサのレベルの高い構成図である。
【図４Ｂ】  図４Ａのプロセッサの一実施形態に関するパイプラインを示す図である。
【図５】  図１、図３、および図４Ａのレジスタ待ち時間表で命令をスケジューリングする方法を示すフローチャートである。
【図６】  図４Ａのプロセッサ内で命令を処理する第１の方法を示すフローチャートである。
【図７】  Ｎクロック・サイクルだけ遅延されたベクトル待ち時間でフラッシュ・コピーすることによって、レジスタ待ち時間表内で待ち時間ベクトルを再生するための構造を示す図である。
【図８】  図７の再生構造の動作を示すフローチャートである。
【図１】
0003984786.tif 000002
【図２】
0003984786.tif 000003
【図３】
0003984786.tif 000004
【図４Ａ】
0003984786.tif 000005
【図４Ｂ】
0003984786.tif 000006
【図５】
0003984786.tif 000007
【図６】
0003984786.tif 000008
【図７】
0003984786.tif 000009
【図８】
0003984786.tif 000010