(57)【特許請求の範囲】
【請求項１】
コンピュータ処理システムにおいて、述語命令を非プログラム順序で処理することができる装置であって、
少なくとも１つの述語命令を含む、命令のグループをメモリからフェッチする手段、
該グループ内の命令の実行をスケジュールして、該述語命令を命令の順序付けシーケンス内の元の位置から、非プログラム順序位置に移動する手段、
非プログラム順序位置に移動された該述語命令の述語値を予測する手段、
予測された述語値が「真」である場合、該述語命令を実行する手段、
実行された該述語命令を退去キューに送る手段、
予測された述語値が「偽」である場合、該述語命令を実行すること無く退去キューに送る手段、
を含むことを特徴とする装置。
【請求項２】
非プログラム順序で実行された述語命令の実行結果を記録するためのフューチャ・レジスタ、
プログラム順序で実行された命令の実行結果を記録するための体系化レジスタ、
をさらに含む、請求項１記載の装置。
【請求項３】
予測に基いて非プログラム順序で実行された述語命令についての予測が正しかったか誤っていたかを判断する手段、
予測が正しかったと判断された場合、退去キューに送られた述語命令を該述語命令の実行結果が記録されたフューチャ・レジスタの名前と共に体系化レジスタに記録する手段、
予測が誤っていたと判断された場合、該述語命令の実行結果を取り消して、プログラムの実行を再スタートする手段と、
をさらに含む、請求項１または２記載の装置。
【請求項４】
予測に基いて非プログラム順序で実行された述語命令の実行結果をフューチャ・レジスタに記録する前に、該述語命令の述語値が既に計算されているか否かについてフューチャ・レジスタを検索する手段、
該述語命令の述語値が既に計算されていた場合、該実行結果を無効化してフューチャ・レジスタへの記録を抑制する手段、
をさらに含む、請求項２または３記載の装置。
【請求項５】
体系化レジスタをリネームしてフューチャ・レジスタを生成するリネーム手段、
体系化レジスタ名とフューチャ・レジスタ名との変換マップを生成する手段、
をさらに含む、請求項２〜４のいずれか１項記載の装置。
【請求項６】
コンピュータ処理システムにおいて、述語命令を非プログラム順序で処理する方法であって、
少なくとも１つの述語命令を含む、命令のグループをメモリからフェッチするステップ、
該グループ内の命令の実行をスケジュールして、該述語命令を命令の順序付けシーケンス内の元の位置から、非プログラム順序位置に移動するステップ、
非プログラム順序位置に移動された該述語命令の述語値を予測するステップ、
予測された述語値が「真」である場合、該述語命令を実行するステップ、
実行された該述語命令を退去キューに送るステップ、
予測された述語値が「偽」である場合、該述語命令を実行すること無く退去キューに送るステップ、
を含むことを特徴とする方法。
【請求項７】
非プログラム順序で実行された述語命令の実行結果をフューチャ・レジスタに記録するステップ、
さらに含む、請求項６記載の方法。
【請求項８】
コンピュータ処理システムが、プログラム順序で実行された命令の実行結果を記録するための体系化レジスタを含み、
予測に基いて非プログラム順序で実行された述語命令についての予測が正しかったか誤っていたかを判断するステップ、
予測が正しかったと判断された場合、退去キューに送られた述語命令を該述語命令の実行結果が記録されたフューチャ・レジスタの名前と共に体系化レジスタに記録するステップ、
をさらに含む、請求項７記載の方法。
【請求項９】
予測に基いて非プログラム順序で実行された述語命令の実行結果をフューチャ・レジスタに記録する前に、該述語命令の述語値が既に計算されているか否かについてフューチャ・レジスタを検索するステップ、
該述語命令の述語値が既に計算されていた場合、該実行結果を無効化してフューチャ・レジスタへの記録を抑制するステップ、
をさらに含む、請求項７または８記載の方法。
【請求項１０】
体系化レジスタをリネームしてフューチャ・レジスタを生成するステップ、
体系化レジスタ名とフューチャ・レジスタ名との変換マップを生成するステップ、
をさらに含む、請求項７〜９のいずれか１項記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般にコンピュータ処理システムに関し、特に、コンピュータ処理システムにおいて、実行述語（ｅｘｅｃｕｔｉｏｎ  ｐｒｅｄｉｃａｔｅｓ）を実現する方法及び装置に関する。
【０００２】
【従来の技術】
初期のマイクロプロセッサは一般に、命令を１つずつ処理した。各命令は順次ステージ、すなわち命令フェッチ、命令解読、命令実行、及び結果のライトバックを用いて処理された。こうしたマイクロプロセッサ内では、異なる専用の論理ブロックが各異なる処理ステージを実行した。各論理ブロックはそのオペレーションを開始する前に、全ての先行する論理ブロックがオペレーションを完了するのを待機した。
【０００３】
コンピュータ・ハードウェアの動作スピードを増加することにより、及び並列処理を様々な形態で導入することにより、コンピュータ・スピードの改善が達成された。並列処理の１形態は、並列命令計算を実行する最近の”スーパスカラ”・タイプのマイクロプロセッサの導入に関連する。一般に、スーパスカラ・マイクロプロセッサは、命令を実行する複数の実行ユニット（例えば複数の整数演算論理ユニット（ＡＬＵ））を、従って複数の”パイプライン”を有する。従って、複数のマシン命令がスーパスカラ・マイクロプロセッサ内で同時に実行されて、装置及びそのシステム・アプリケーションの全体性能の点で、明らかな利点を提供する。
【０００４】
本議論の目的のために、命令のフェッチ・ステージと命令の実行ステージ間の遅延として、待ち時間（ｌａｔｅｎｃｙ）が定義される。ここで指定レジスタ内に記憶されるデータを参照する命令について考えてみよう。こうした命令は完了するために、少なくとも４マシン・サイクルを要する。第１サイクルでは、命令がメモリからフェッチされる。第２サイクルでは、命令が解読される。第３サイクルでは、命令が実行され、第４サイクルで、データが適切な位置にライトバックされる。
【０００５】
効率を改善し、命令待ち時間を低減するために、マイクロプロセッサ設計者は、フェッチ、解読、実行、及びライトバック論理ステージのオペレーションをオーバラップさせることにより、マイクロプロセッサが同時に幾つかの命令に作用するようにした。オペレーションにおいて、フェッチ、解読、実行、及びライトバック論理ステージが、異なる命令を並列に処理する。各クロック・パルスにおいて、各処理ステージの結果が続く処理ステージに渡される。フェッチ、解読、実行及びライトバック・ステージをオーバラップさせる技術を使用するマイクロプロセッサは、”パイプライン式”マイクロプロセッサとして知られる。原則的に、パイプライン式マイクロプロセッサは、既知の命令シーケンスが実行されているとき、１マシン・サイクルにつき１命令の実行を完了できる。従ってパイプライン式マイクロプロセッサでは、１番目の命令の実際の実行が完了される前に、２番目の命令の処理を開始することにより、待ち時間の影響が低減される。
【０００６】
一般に、マイクロプロセッサでの命令フローは、メモリ内の順次位置から命令がフェッチされ、解読されることを要求する。あいにく、コンピュータ・プログラムは分岐命令を含む。分岐命令はこのフローの崩壊を生じる命令である。例えば、分岐の発生は順次パスに沿った解読の中断を生じ、メモリ内の新たな位置からの再開を生じる。パイプライン式命令フロー内におけるこうした中断は、パイプライン性能の実質的な悪化を生じる。
【０００７】
従って、多くのパイプライン式マイクロプロセッサは、命令ストリーム内での分岐命令の存在及び結果（すなわち分岐が発生するか否か）を予測する分岐予測機構を使用する。命令フェッチ・ユニットが分岐予測を用いて、続く命令をフェッチする。
【０００８】
プロセッサは命令のプールから、所与の時点にディスパッチされる命令を選択するが、この命令のプールが非プログラム順序の実行の使用により拡大される。非プログラム順序の実行は、命令の順次ストリーム内のオペレーションが再順序付けされる技術であり、後に現れるオペレーションにより要求される資源が未使用の場合、後に現れるオペレーションが先に実行される。従って、非プログラム順序の実行は、複数の機能ユニットの可用性を利用して、遊休状態の資源を使用することにより、プログラムの全体的な実行時間を低減する。オペレーションの実行の再順序付けは、それらのオペレーションにより生成される結果の再順序付けを要求するので、プログラムの機能的な振舞いは、命令がそれらの元の順序で実行された場合に獲得されるものと同一である。
【０００９】
一般に、命令の実行をスケジュールする２つのアプローチが存在し、それらは動的スケジューリング及び静的スケジューリングである。動的スケジューリングでは、命令が実行時に分析され、命令がハードウェアによりスケジュールされる。静的スケジューリングでは、命令が生成されるとき、コンパイラ／プログラマが命令を分析及びスケジュールする。従って、静的スケジューリングはソフトウェアを通じて達成される。これらの２つのアプローチは、共同で実現され得る。
【００１０】
パイプライン式アーキテクチャにおける効果的な実行は、パイプラインが高利用率を有すること、すなわち、パイプライン内の各ユニットが命令を着実に実行することを要求する。一部のオペレーション、例えば分岐命令またはキャッシュ・ミスなどの予測不能な動的事象などは、この利用の崩壊を招く。
【００１１】
これらの問題を解決する多数の技術が開発されてきた。例えば、分岐ペナルティを除去または低減して、分岐を正しく予測するために、分岐予測が利用される。更に、非プログラム順序のスーパスカラ・プロセッサ内での命令の動的スケジューリングは、事象が動的に発生しても、高利用率を維持するために使用される。
【００１２】
しかしながら、分岐予測は分岐の犠牲を完全には除去しない。なぜなら、正しく予測された分岐であっても、新たな命令のフェッチの崩壊を生じるからである。更に、分岐は命令を静的にスケジュールするコンパイラの能力を低減する。このことはプログラム実行の性能を低下させ、これは特に、命令を順序通りに実行する超長命令語（ＶＬＩＷ）などに当てはまる。
【００１３】
これらの問題を解決するために、述語化（ｐｒｅｄｉｃａｔｉｏｎ）と呼ばれる技術が導入され、一部のコード・シーケンスにおいて分岐を除去する。この技術は、制御フロー命令を条件付きに実行される命令（”述語命令（ｐｒｅｄｉｃａｔｅｄ  ｉｎｓｔｒｕｃｔｉｏｎ）”と呼ばれる）により置換する。述語命令は、特定の条件（述語）が真または偽の場合に実行される。述語命令に関する論文については、”Ｏｎ  Ｐｒｅｄｉｃａｔｅｄ  Ｅｘｅｃｕｔｉｏｎ”、Ｐａｒｋ  ａｎｄ  Ｓｃｈｌａｎｋｅｒ、Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  Ｎｏ．ＨＰＬ−９１−５８、Ｈｅｗｌｅｔｔ−Ｐａｃｋａｒｄ、Ｐａｌｏ  Ａｌｔｏ、ＣＡ、Ｍａｙ  １９９１を参照されたい。
【００１４】
述語化は、制御依存性をデータ依存性に還元する方法として論じられた。これは条件付き分岐を、条件付きパス上の各命令のための保護（ｇｕａｒｄ）に変換することにより達成される。このプロセスは”ｉｆ変換”と呼ばれる。述語アーキテクチャは、実行されなければならない分岐の数を低減するので、利点を提供する。これは特に、静的にスケジュールされたアーキテクチャにおいて重要であり、そこではｉｆ変換が分岐の両方のパス上の命令の実行を可能にし、分岐ペナルティを除去する。
【００１５】
次のコード・シーケンス例について考えてみよう。
【数１】
0003565499.tif 000002
【００１６】
更に、述語化機構を有さないマイクロプロセッサにおける、このコードの変換について考え、変数”ａ”が汎用レジスタｒ３に割当てられるものとする。ＩＢＭＰｏｗｅｒＰＣ（商標）アーキテクチャなどのアーキテクチャでは、これは２つの分岐を有する命令シーケンスに変換される。
【数２】
0003565499.tif 000003
【００１７】
ＩＢＭ  ＰｏｗｅｒＰＣ（商標）に類似するが、述語機構を有するマイクロプロセッサ上では、この変換コード・シーケンスは分岐の無いシーケンスに変換される。以下の例では、述語命令が、命令の直後に述語を指定する条件節（ｉｆ  ｃｌａｕｓｅ）により示される。
【数３】
0003565499.tif 000004
【００１８】
述語化を使用することにより、一部の分岐が除去され、それにより命令をスケジュールするコンパイラの能力を改善し、犠牲の大きい分岐予測ミスの潜在性を除去する。しかしながら、従来の予測アーキテクチャは、世代間の互換性や、動的事象及び可変待ち時間オペレーション（メモリ・アクセスなど）に対する適切な動的適応化に十分に対応していない。特に、述語アーキテクチャの実施例は、静的スケジューリング及び固定実行順序に頼ったため、動的事象に応答する能力を低下させる。また、各述語は追加の入力オペランドを形成するので、述語命令は述語が評価されるまで待機しなければならないのに対して、分岐予測ベースの方式では、実行が条件の予測にもとづき継続できる。
【００１９】
結果的に、現予測方式は、命令をプログラム順序にまたは非プログラム順序に実行できる命令セット・アーキテクチャの要求を十分に解決しない。更に、現予測方式は様々な性能レベルを有する実施例をサポートしない。
【００２０】
次に、述語化を扱う関連技術の概要について述べることにする。図１は、従来技術による述語実行及び実行抑制を有する述語予測アーキテクチャを示す。特に、図１のアーキテクチャは、Ｃｙｄｒａ５スーパコンピュータの述語化の実施例に対応し、これについてはＲａｕらによる論文”Ｔｈｅ  Ｃｙｄｒａ  ５  ｄｅｐａｒｔｍｅｎｔａｌ  ｓｕｐｅｒｃｏｍｐｕｔｅｒ”、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ、Ｖｏｌ．２２、Ｎｏ．１、ｐ．１２−３５、Ｊａｎｕａｒｙ  １９８９で述べられている。Ｃｙｄｒａ５スーパコンピュータでは、他のオペランドと同様に、オペランド・フェッチの間に述語値がフェッチされる。述語オペランドが偽（ＦＡＬＳＥ）の場合、述語オペレーションの実行は抑制される。この設計は概念的な単純化、並びに静的にスケジュールされたアーキテクチャのスケジューリングの改善のために、実行パスを結合する能力を提供する。しかしながら、述語は実行フェーズの早期に使用可能である必要がある。
【００２１】
別の述語予測アーキテクチャが図２に示され、これは従来技術に従う述語実行及びライトバック抑制を有する述語予測アーキテクチャを示す図ある。図２のアーキテクチャは、Ｄ．Ｌｉｎの修士論文”Ｃｏｍｐｉｌｅｒ  Ｓｕｐｐｏｒｔ  ｆｏｒ  Ｐｒｅｄｉｃａｔｅｄ  Ｅｘｅｃｕｔｉｏｎ  ｉｎ  ＳｕｐｅｒＳｃａｌａｒ  Ｐｒｏｃｅｓｓｏｒｓ”、Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｉｌｌｉｎｏｉｓ、Ｓｅｐｔｅｍｂｅｒ  １９９０、及びＭａｈｌｋｅらによる”Ｅｆｆｅｃｔｉｖｅ  Ｃｏｍｐｉｌｅｒ  Ｓｕｐｐｏｒｔ  ｆｏｒ  Ｐｒｅｄｉｃａｔｅｄ  Ｅｘｅｃｕｔｉｏｎ  Ｕｓｉｎｇ  ｔｈｅ  Ｈｙｐｅｒｂｌｏｃｋ”、Ｐｒｏｃ．  ｏｆ  ｔｈｅ  ２５ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｍｉｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ、ｐｐ．４５−５４、Ｄｅｃｅｍｂｅｒ  １９９２で述べられている。Ｃｙｄｒａ５の功績にもとづくこのアーキテクチャでは、全てのオペレーションが常に実行されるが、述語が真（ＴＲＵＥ）であると評価されるオペレーションだけが、マシン状態に書込まれる。この方式はライトバック抑制（ｗｒｉｔｅｂａｃｋ  ｓｕｐｐｒｅｓｓｉｏｎ）と呼ばれる。ライトバック抑制方式では、述語レジスタが後にパイプライン内で評価される。適切な転送機構により、これは依存距離を０に低減することを可能にする。すなわち、述語が評価され、同一長の命令ワード・アーキテクチャ内で使用される。
【００２２】
静的にオペレーションを推測するために、予測がコンパイラ・ベースの方式と結合されて、前述のＣｙｄｒａ５アーキテクチャの制限を克服する。このアプローチは追加の演算コード・ビットの使用により、命令を静的に識別することにもとづく。こうしたアプローチが、Ｋ．Ｅｂｃｉｏｇｌｕにより”Ｓｏｍｅ  Ｄｅｓｉｇｎ  Ｉｄｅａｓ  ｆｏｒ  ａ  ＶＬＩＷ  ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｓｅｑｕｅｎｔｉａｌ−Ｎａｔｕｒｅｄ  Ｓｏｆｔｗａｒｅ”、Ｐａｒａｌｌｅｌ  Ｐｒｏｃｅｓｓｉｎｇ、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＦＩＰ  ＷＧ  １０．３  Ｗｏｒｋｉｎｇ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐａｒａｌｌｅｌ  Ｐｒｏｃｅｓｓｉｎｇ、Ｎｏｒｔｈ  Ｈｏｌｌａｎｄ、Ｃｏｓｎａｒｄ  ｅｔ  ａｌ．、ｅｄｓ．、ｐｐ．３−２１（１９８８）で述べられている。
【００２３】
この概念の拡張は、Ｋ．Ｅｂｃｉｏｇｌｕ及びＲ．Ｇｒｏｖｅｓにより、”Ｓｏｍｅ  Ｇｌｏｂａｌ  Ｃｏｍｐｉｌｅｒ  Ｏｐｔｉｍａｚａｔｉｏｎｓ  ａｎｄ  Ａｒｃｈｉｔｅｃｔｕｒａｌ  Ｆｅａｔｕｒｅｓ  ｆｏｒ  Ｉｍｐｒｏｖｉｎｇ  Ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  Ｓｕｐｅｒｓｃａｌａｒｓ”、Ｒｅｓｅａｒｃｈ  Ｒｅｐｏｒｔ  Ｎｏ．ＲＣ１６１４５、ＩＢＭ  Ｔ．Ｊ．Ｗａｔｓｏｎ  Ｒｅｓｅａｒｃｈ  Ｃｅｎｔｅｒ、Ｙｏｒｋｔｏｗｎ  Ｈｅｉｇｈｔｓ、ＮＹ、Ｏｃｔｏｂｅｒ  １９９０で、また本出願人による１９９８年８月２５日発行の米国特許第５７９９１７９号”Ｈａｎｄｌｉｎｇ  ｏｆ  Ｅｘｃｅｐｔｉｏｎｓ  ｉｎ  Ｓｐｅｃｕｌａｔｉｖｅ  Ｉｎｓｔｒｕｃｔｉｏｎｓ”で述べられている。このアプローチを実現するアーキテクチャが、Ｋ．Ｅｂｃｉｏｇｌｕ、Ｊ．Ｆｒｉｔｔｓ、Ｓ．Ｋｏｓｏｎｏｃｋｙ、Ｍ．Ｇｓｃｈｗｉｎｄ、Ｅ．Ａｌｔｍａｎ、Ｋ．Ｋａｉｌａｓ、Ｔ．Ｂｒｉｇｈｔにより、”Ａｎ  Ｅｉｇｈｔ−Ｉｓｓｕｅ  Ｔｒｅｅ−ＶＬＩＷ  Ｐｒｏｃｅｓｓｏｒ  ｆｏｒ  Ｄｙｎａｍｉｃ  Ｂｉｎａｒｙ  Ｔｒａｎｓｌａｔｉｏｎ”、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｄｅｓｉｇｎ、Ａｕｓｔｉｎ、ＴＸ、Ｏｃｔｏｂｅｒ  １９９８で述べられている。また関連アプローチについても、Ｍａｈｌｋｅらにより、”Ｓｅｎｔｉｎｅｌ  Ｓｃｈｅｄｕｌｉｎｇ  ｆｏｒ  ＶＬＩＷ  ａｎｄ  Ｓｕｐｅｒｓｃａｌａｒ  Ｐｒｏｃｅｓｓｏｒｓ”、Ｆｉｆｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ａｒｃｈｉｔｅｃｔｕｒａｌ  Ｓｕｐｐｏｒｔ  ｆｏｒ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅｓ  ａｎｄ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ、Ｂｏｓｔｏｎ、ＭＡ、Ｏｃｔｏｂｅｒ  １９９２で概要が述べられている。
【００２４】
しかしながら、静的推測はコンパイラがオペレーションを適切にスケジュールするために、命令待ち時間に気遣うことを要求する。これは一般に、静的にスケジュールされたアーキテクチャに対する業界のぐずぐずした容認に寄与する２つの要因のために実現可能でない。第１に、多くの事象が動的であり、従って静的に予測可能でない（例えば、キャッシュ・ミスの発生によるメモリ・アクセス・オペレーションの待ち時間）。更に、業界アーキテクチャは、様々な内部構造及び設計の複数の実施例により、及び高度に差別化された性能レベルにより、数年間（一般に１０年またはそれ以上）は存続し得ると予想される。
【００２５】
従って、動的にスケジュールされる非プログラム順序のスーパスカラ命令プロセッサにおいて、述語実行を組み込む方法及びシステムを有することが待望され、高度に有利である。好適には、こうした方法及びシステムは、プログラム順序の実行のための静的スケジューリングもサポートする。
【００２６】
【発明が解決しようとする課題】
本発明はコンピュータ処理システムにおいて、実行述語を実現する方法及び装置に関する。本発明は述語実行の利点と、スーパスカラ・プロセッサの実施例により提供される動的事象に応答する能力とを結合する。本発明はプログラム順序の実行の静的スケジューリングをサポートする一方で、非プログラム順序の実行を可能にすることにより、予測された条件にもとづき、コードをより積極的に実行する。
【００２７】
【課題を解決するための手段】
本発明の第１の態様によれば、コンピュータ処理システムにおいて、命令の順序付けシーケンスを実行する方法が提供される。命令のシーケンスが、システムのメモリ内に記憶される。命令の少なくとも１つが、関連フラグ値にもとづき条件付きで実行される、少なくとも１つのオペレーションを表す述語命令を含む。この方法は、メモリから命令のグループをフェッチするステップを含む。命令の実行がグループ内でスケジュールされ、述語命令が命令の順序付けシーケンス内のその元の位置から、命令のシーケンス内の非プログラム順序位置に移動される。命令はスケジューリングに応答して実行される。
【００２８】
本発明の第２の態様によれば、この方法は更に、実行ステップの結果を命令の順序付けシーケンスに対応する順序で、体系化レジスタまたはメモリのいずれか一方に書込むステップを含む。
【００２９】
本発明の第３の態様によれば、この方法は更に、関連フラグ値が述語命令の実行において使用可能でないとき、関連フラグ値の予測値を生成するステップを含む。
【００３０】
本発明の第４の態様によれば、この方法は更に、予測値にもとづき、述語命令により表されるオペレーションの実行を変更するステップを含む。
【００３１】
本発明の第５の態様によれば、変更するステップが、予測値にもとづき、述語命令により表されるオペレーションにより生成される結果のライトバックを、選択的に抑制するステップを含む。
【００３２】
本発明の第６の態様によれば、変更するステップが、予測値にもとづき、述語命令により表されるオペレーションを選択的に発行するステップを含む。
【００３３】
本発明の第７の態様によれば、この方法は更に、述語命令の実行または退去のいずれかに際して、関連フラグ値の予測値が正しいか否かを判断するステップを含む。関連フラグ値の予測値が正しくない場合、述語命令は正しい予測を用いて実行される。関連フラグ値の予測値が正しい場合、述語命令の実行に対応する結果が、体系化レジスタまたはメモリのいずれか一方に書込まれる。
【００３４】
本発明の第８の態様によれば、命令をコンピュータ処理システムにおいて実行する方法が提供される。命令はシステムのメモリに記憶される。命令の少なくとも１つは、少なくとも１つの関連フラグ値にもとづき条件付きで実行される、少なくとも１つのオペレーションを表す述語命令を含む。この方法は、メモリから命令のグループをフェッチするステップを含む。グループが、その関連フラグ値が使用可能でない特定の述語命令を含む場合、関連フラグ値の予測値を表すデータが生成される。特定の述語命令により表されるオペレーションの実行が、予測値にもとづき変更される。
【００３５】
本発明の第９の態様によれば、コンピュータ処理システムにおいて命令を実行する方法が提供される。命令はシステムのメモリに記憶される。この方法は、メモリから命令のグループをフェッチするステップを含み、グループは少なくとも１つの関連フラグ値にもとづき条件付きで実行される、少なくとも１つのオペレーションを表す少なくとも１つの述語命令を含む。たとえ述語命令の関連フラグ値が使用不能であっても、述語命令を含む命令のグループが実行される。未解決の述語の結果に対して、レジスタ名または値のいずれか一方のリストが記憶される。複数の名前または複数の値のいずれか一方が入手可能なレジスタを使用する命令が識別される。所与の識別された命令に対して、複数の名前または複数の値のいずれか一方だけが選択される。所与の識別された命令に対応する述語の解析に際して、選択が正しいか否かが判断される。選択が正しくない場合、所与の命令に続くオペレーションの実行が変更される。
【００３６】
本発明の第１０の態様によれば、退去される命令の体系化ソース・レジスタ名から、フューチャ・レジスタ名の予測を検証する方法が提供される。この方法は、命令内の各所与のソース・オペランドが、複数のフューチャ・レジスタ名に対応するか否かを判断するステップを含む。所与のソース・オペランドの各々に対して使用される実際の名前が使用可能でない場合、ソース・オペランドの各々の実際の名前が、ソース・オペランドの各々に対して予測される名前に対応するか否かが判断される。少なくとも１つのソース・オペランド名が予測ミスされた場合、命令に対して予測ミス修復が実行される。ソース・オペランドの各々の実際の名前が、ソース・オペランドの各々に対して予測される名前に対応する場合、命令は退去される。
【００３７】
【発明の実施の形態】
本発明はコンピュータ処理システムにおいて、実行述語を実現する方法及び装置に関する。本発明は、動的にスケジュールされる非プログラム順序のスーパスカラ命令プロセッサを用いるコンピュータ処理システムにおいて、述語実行を実行するために使用され得る。こうした実施例において、本発明は非プログラム順序の実行を可能にし、予測条件にもとづき、コードをより積極的に実行する。更に、本発明はプログラム順序の実行の静的スケジューリングをサポートする。
【００３８】
本発明の理解を容易にするために、ここで使用される用語の定義について述べることにする。述語化は、一部のコード・シーケンスに対して、分岐を除去するために導入された技術である。述語化は、制御フロー命令を条件付きで実行される命令（”述語命令”と呼ばれる）により置換するもので、述語命令は、特定の条件（”述語”）が真または偽のいずれかである場合に実行される。非プログラム順序の実行は、命令の順次ストリーム内のオペレーションを再順序付けする技術であり、後に出現するオペレーションにより要求される資源が未使用の場合、後に出現するオペレーションが先に実行される。投機オペレーションは、必ずしも実行されなくてよい非プログラム順序のオペレーションである。なぜなら、例えばそれが配置される実行パスが続行されずに、代わりに別の実行パスが続行され得るからである。
【００３９】
レジスタ・ファイルは、レジスタ指定子によりアドレス指定される複数のレジスタを参照する。整数、浮動小数点、条件コード（述語）データなどの異なるデータ・タイプを、異なるレジスタ・ファイルに記憶するために、複数のレジスタ・ファイルがアーキテクチャ内でサポートされ得る（例えば、ＩＢＭ  ＰｏｗｅｒＰＣ（商標）アーキテクチャはこの構成をサポートする）。或いは、複数のデータ・タイプが単一のレジスタ・ファイルに記憶され得る（例えばＤＥＣ  ＶＡＸアーキテクチャはこの構成をサポートする）。こうした単一レジスタ・ファイルは一般に、汎用レジスタ・ファイルと呼ばれる。一部の構成では、特殊なデータ・タイプのためのレジスタ・ファイルと、全ての残りのデータ・タイプの値を記憶するための汎用レジスタ・ファイルとが存在する。スーパスカラ・プロセッサの１実施例によれば、レジスタ内容に関するデータが、レジスタ・ファイルの複数のコピー内に記憶され得る。”体系化レジスタ・ファイル”は、プログラム順序実行ポイントのプロセッサ状態に対応する。オペレーションの非プログラム順序のまたは投機実行の結果は、”フューチャ・レジスタ・ファイル”に書込まれる。（例えば、整数、浮動小数点、及び条件／述語データのための）複数のレジスタ・ファイルが存在する場合、体系化レジスタ・ファイル及びフューチャ・レジスタ・ファイルが、これらのレジスタ・ファイルの各々に対して存在し得る。この技術はＪ．Ｓｍｉｔｈ及びＡ．Ｐｌｅｚｋｕｎにより、”Ｉｍｐｌｅｍｅｎｔｉｎｇ  Ｐｒｅｃｉｓｅ  Ｉｎｔｅｒｒｕｐｔｓ  ｉｎ  Ｐｉｐｅｌｉｎｅｄ  Ｐｒｏｃｅｓｓｏｒｓ”、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ、Ｖｏｌ．３７、Ｎｏ．５、ｐｐ．５６２−７３、Ｍａｙ  １９８８で述べられている。
【００４０】
本発明の理解を容易にするため、単一の述語が、あらゆる命令内の１つの固定のフィールド内で符号化されると仮定する。しかしながら、２つ以上の述語が単一命令内に含まれ得ることが理解されよう。或いは、単一命令が述語を含まなくても良い。複数の述語が単一命令内に含まれる場合、こうした述語は任意のタイプの論理関数（例えば論理積、論理和、排他的論理和など）を用いて結合され得る。更に、発行される命令に応じて、述語が可変の位置に存在し得、また一部の命令が他の命令よりも多くの述語を含み得ることが理解されよう。
【００４１】
レジスタ・リネーミングはここでは通り一遍に述べられるが、レジスタ・リネーミングは本発明に関連して、当業者により容易に実現されよう。実行抑制を使用する実施例では、レジスタ・リネーミングの好適な実現は、抑制される命令の宛先レジスタとして、リネーム・レジスタを割当てない。ライトバック抑制を使用する実施例では、体系化レジスタとして新たなリネーム・レジスタを割当てられた各オペレーションが、こうしたアーキテクチャに割当てられた前のリネーム・レジスタの名前を維持する。命令が後に抑制される場合、前のリネーム・レジスタ名が、抑制されるオペレーションの物理（リネーム・）レジスタの参照を含む全てのオペレーションに同報される。他方、命令が抑制されない場合、実際のオペレーション結果が代わりに同報される。第３の実施例はデータ依存予測機構を用いて、後述のようにリネーミングを導く。
【００４２】
分岐予測についてはここでは詳述しないが、これは本発明に関連して当業者により容易に実現され得る別の機構である。述語実行及び分岐予測をサポートするプロセッサの設計におけるトレードオフが、”Ｇｕａｒｄｅｄ  Ｅｘｅｃｕｔｉｏｎ  ａｎｄ  Ｂｒａｎｃｈ  Ｐｒｅｄｉｃｔｉｏｎ  ｉｎ  Ｄｙｎａｍｉｃ  ＩＬＰ  Ｐｒｏｃｅｓｓｏｒｓ”、２１ｓｔ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ、Ｃｈｉｃａｇｏ、Ｉ１、１９９４で述べられている。好適には、分岐予測は本発明の高性能実施例において実現される。こうした実施例では、述語及び分岐予測の両方のために、同一の予測器が使用され得る。代替実施例では、別々の予測器が使用され得る。
【００４３】
命令を動的にスケジュール可能なプロセッサ（非プログラム順序実行プロセッサ）の従来の実施例は、次の機構を含む。
（１）命令を非プログラム順序に発行する第１の機構Ａであって、命令間の依存性を検出する能力、命令により使用されるレジスタをリネームする能力、及び命令により要求される資源の可用性を検出する能力を含む。
（２）プロセッサの非プログラム順序状態を維持する第２の機構Ｂであって、命令が（非プログラム順序で）実行される時に、それらの結果を反映する。
（３）命令をプログラム順序に退去し、同時にプログラム順序状態を、退去される命令の結果により更新する第３の機構Ｃ。
（４）プログラム順序状態を更新すること無く、命令をプログラム順序に退去し（退去される命令の結果を事実上取り消す）、退去される命令から、プログラムのプログラム順序の実行を再開する（非プログラム順序状態で存在する全ての結果を取り消すことを意味する）第４の機構Ｄ。
【００４４】
第３の機構Ｃは、退去される命令の結果が正しい場合に、命令を退去するために使用される。他方、第４の機構Ｄは、退去される命令の実行、または特定の外部事象に由来する異常条件が存在する度に使用される。
【００４５】
図３は、本発明に従う命令の再順序付けをサポートするスーパスカラ・プロセッサ及びハードウェア資源を含む、コンピュータ処理システムの図である。前述の機構（Ａ乃至Ｄ）は、図３のシステムに組み込まれる。
【００４６】
システム３００は、メモリ・サブシステム３０５、命令キャッシュ３１０、データ・キャッシュ３１５、及びプロセッサ・ユニット３２０を含む。プロセッサ・ユニット３２０は命令バッファ３２５、命令リネーム及びディスパッチ・ユニット３３０（ここでは”ディスパッチ・ユニット”と呼ぶ）、フューチャ汎用レジスタ・ファイル３３５（ここでは”フューチャ・レジスタ・ファイル”と呼ぶ）、分岐ユニット（ＢＵ）３４０、及び整数、論理及び浮動小数点演算の実行のための複数の機能ユニット（ＦＵ）３４５、ロード及びストア・オペレーションのための複数のメモリ・ユニット（ＭＵ）３５０、退去キュー３５５、体系化プログラム順序汎用レジスタ・ファイル３６０（ここでは”体系化レジスタ・ファイル”と呼ぶ）、及びプログラム・カウンタ（ＰＣ）３６５を含む。命令メモリ・サブシステムは主メモリを含み、任意的にキャッシング階層を含むことが理解されよう。
【００４７】
本発明の様々な実施例が、図３に示されるプロセッサ・アーキテクチャに関連して述べられるが、当業者であれば、本発明を他のプロセッサ設計、例えばスーパスカラ・プロセッサの実施例や、超長命令語（ＶＬＩＷ）の実施例の変形などに容易に適応化できよう。
【００４８】
メモリ・サブシステム３０５は、プログラム命令を記憶する。命令キャッシュ３１０は、命令のための高速アクセス・バッファとして作用する。命令が命令キャッシュ３１０内で使用可能でないとき、命令キャッシュ３１０はメモリ・サブシステム３０５の内容を用いて充填される。各サイクルにおいて、プログラム・カウンタ３６５を用いて、命令キャッシュ３１０が命令フェッチ論理（図示せず）により、次の命令セットを問い合わされる。命令フェッチ論理は任意的に、分岐予測論理及び分岐予測テーブル（図示せず）を含む。問い合わせに応答して、命令キャッシュ３１０が１つ以上の命令を返却し、これが命令バッファ３２５に同一の相対順序で入力する。命令バッファ３２５内の各命令に対して、命令アドレス（ＩＡ）も保持される。命令バッファ３２５に関連付けられる論理が、退去キュー３５５（再順序付けバッファとも呼ばれる）内のエントリを、各命令のために割当てる。退去キュー３５５内のエントリの順序付けは、命令フェッチのそれと相対的に同一である。退去キュー３５５については、以下で詳述する。
【００４９】
命令バッファ３２５は命令をディスパッチ・ユニット３３０にコピーし、ディスパッチ・ユニットが次の複数のタスクを実行する。すなわち、
（１）ディスパッチ・ユニット３３０が各命令を解読する。
（２）ディスパッチ・ユニット３３０が各命令内の宛先オペランド指定子をリネームし、各命令内において、体系化宛先レジスタ・オペランド指定子がプロセッサ内の別個の物理レジスタ指定子にマップされる。物理レジスタ指定子は、フューチャ・レジスタ・ファイル３３５及び体系化レジスタ・ファイル３６０内のレジスタを指定する。ディスパッチ・ユニット３３０はまた、レジスタ・リネーム論理（図示せず）に関連付けられる関連テーブルを更新する。
（３）ディスパッチ・ユニット３３０は、体系化レジスタ・ファイル３６０及びフューチャ・レジスタ・ファイル３３５の順に、タイプ汎用レジスタ、浮動小数点レジスタ、条件レジスタ、または任意の他のレジスタ・タイプのソース・オペランドの可用性を問い合わせる。任意のオペランドが現在体系化レジスタ・ファイル３６０内で使用可能な場合、それらの値が命令と一緒にコピーされる。オペランドの値が（先行命令により計算されているために）現在使用可能でない場合、体系化レジスタ・ファイル３６０がその結果に指示を記憶し、その際、この値が使用可能であったはずの物理レジスタ名（これは体系化レジスタ・ファイル３６０からも使用可能）を用いて、フューチャ・レジスタ・ファイル３３５がこの値を問い合わされる。値が見い出されると、値が命令と一緒にコピーされる。値が見い出されない場合、その値が将来使用可能になるはずの物理レジスタ名がコピーされる。
（４）ディスパッチ・ユニット３３０は命令を実行のために、次の実行ユニット、すなわち、分岐ユニット３４０、機能ユニット３４５、及びメモリ・ユニット３５０にディスパッチする。どの命令が実行のために予約ステーション（図示せず）（キューとして構成される）に入力するかに関する決定が、命令の実行資源要求及び実行ユニットの可用性にもとづき下される。
【００５０】
一旦、命令の実行のために必要な全てのソース・オペランド値が使用可能になると、命令が実行ユニット内で実行され、結果の値が計算される。計算された値が命令に対して、退去キュー３５５のエントリに書込まれ（後述）、予約ステーション内で値を待機する命令が、実行準備完了としてマークされる。
【００５１】
前述のように、退去キュー３５５は命令をプログラム順序通りに記憶する。退去キュー３５５はまた、各命令に対して、その命令アドレス、その宛先レジスタの体系化名、及び体系化宛先レジスタがマップされたフューチャ・レジスタの名前を記憶する。退去キュー３５５は更に、各命令に対して、宛先レジスタの値（すなわち命令のために実行された計算結果）を記憶する空間を含む。
【００５２】
分岐命令では、予測結果（分岐方向及びターゲット・アドレスの両方）も退去キュー３５５内に保持される。すなわち、退去キュー３５５内に、実際の分岐方向、及び分岐が制御を渡した実際のターゲット・アドレスを記憶する空間が割当てられる。
【００５３】
命令が実行を完了し、その結果が使用可能なとき、結果が退去キュー３５５の対応エントリ内のこの空間にコピーされる。分岐命令では、実際の結果もまたコピーされる。一部の命令は異常条件により、それらの実行の間に例外を生じる。例外は、例外条件に対して適切なアクションを取るために要求されるデータと一緒に書留められる。前述のように、異常状況を生じた命令は、第４の機構Ｄを用いる退去論理により退去される。命令は実行を非プログラム順序で完了し得（すなわちプログラム順序と必ずしも同一順序でない）、結果的に退去キュー３５内のエントリが非プログラム順序で充填され得る。
【００５４】
退去論理（図示せず）のオペレーションは、退去キュー３５５内に保持される情報を用いて行われるが、これについて次に述べる。各サイクルにおいて、退去キュー３５５が走査されて、退去キュー３５５の先頭のエントリを識別する（退去キュー３５５は本質的にＦＩＦＯ（先入れ先出しキュー）である）。先頭の命令が実行を完了した場合、その命令が第３の機構Ｃまたは第４の機構Ｄを用いて退去される。第３の機構Ｃの場合、オペレーションのあらゆる結果値が体系化レジスタ・ファイル３６０に、または体系化プログラム順序マシン状態の任意の他の部分に退去される。第４の機構Ｄの場合、この命令の結果及び全ての続く結果が取り消され、実行が現命令からプログラム順序に再スタートされる。メモリのデータ部分に値を記憶する命令のあらゆる結果が、データ・キャッシュ３１５に書込まれる。データ・キャッシュ３１５は、メモリ・サブシステム３０５に保持されるプログラム・データのための、高速アクセス・バッファとして作用し、データがデータ・キャッシュ３１５内で使用可能でないとき、それはメモリ・サブシステム３０５から充填される。プロセッサ３００から退去される命令が分岐の場合、分岐の実際の方向が予測方向と突き合わされ、実際のターゲット・アドレスが予測ターゲット・アドレスと突き合わされる。両方のケースにおいて一致が存在する場合、特別のアクション無しに、分岐退去が発生する。他方、不一致が存在する場合、分岐予測ミスという結果に終わり、第４の機構Ｄを用いて、分岐予測ミス修復オペレーションを導く。
【００５５】
分岐予測ミスの間、分岐に続く退去キュー３５５内の全ての命令（これらはプログラム・メモリ内の誤って予測された分岐ターゲット・アドレスにも存在する）が、スカッシング（ｓｑｕａｓｈｉｎｇ）とマークされる（それらの計算結果はプロセッサ体系化状態に退去されない）。更に、分岐予測器及び関連テーブルの状態が、予測ミスを反映するように更新される。プログラム・カウンタ３６５は、分岐が実際に制御を移した命令アドレスの新たな値を与えられ、命令フェッチがそのポイントから再開される。
【００５６】
前述のコンポーネントに加え、スーパスカラ・プロセッサ（本発明に従うものも含む）は任意的に、例えば値予測のための手段、メモリ命令再順序付けのための手段、及び必要に際して未解決のメモリ命令を取り消す手段などの、他のコンポーネントを含み得る。これらはスーパスカラ技術の公知の要素であり、本発明を理解する上で本質的でなく、従ってここでは詳述しない。
【００５７】
図４は、本発明の実施例に従い、述語命令を実行するスーパスカラ・プロセッサ及びハードウェア資源を含む、コンピュータ処理システム４００の図である。システム４００は、メモリ・サブシステム３０５、命令キャッシュ３１０、データ・キャッシュ３１５、及びプロセッサ・ユニット４２５を含む。プロセッサ・ユニット４２５は命令バッファ３２５、ディスパッチ・ユニット３３０、フューチャ・レジスタ・ファイル３３５、分岐ユニット（ＢＵ）３４０、複数の機能ユニット（ＦＵ）３４５、複数のメモリ・ユニット（ＭＵ）３５０、退去キュー３５５、体系化レジスタ・ファイル３６０、プログラム・カウンタ（ＰＣ）３６５、及び述語命令の実行をサポートするフューチャ述語レジスタ・ファイル４０５及び体系化プログラム順序述語レジスタ・ファイル４１０（以下では”体系化述語レジスタ・ファイル”と呼ぶ）を含む。
【００５８】
命令がディスパッチ・ユニット３３０により処理されるとき、述語レジスタの参照が汎用レジスタ参照と同様に解析される。特に、ディスパッチ・ユニット３３０は、体系化述語レジスタ・ファイル４１０及びフューチャ・レジスタ・ファイル３３５の順に、タイプ述語レジスタのソース・オペランドの可用性を問い合わせる。任意のこうしたオペランドが現在体系化述語レジスタ・ファイル４１０内で使用可能な場合、それらの値が命令と一緒にコピーされる。オペランドの値が（先行命令により計算されているために）現在使用可能でない場合、体系化述語レジスタ・ファイル４１０がその結果に指示を記憶し、その際、この値が使用可能であったはずの物理レジスタ名（体系化述語レジスタ・ファイル４１０からも使用可能）を用いて、フューチャ・レジスタ・ファイル３３５がこの値を問い合わされる。値が見い出されると、値が命令と一緒にコピーされる。値が見い出されない場合、その値が将来使用可能になるはずの物理レジスタ名がコピーされる。
【００５９】
更に、退去論理が述語条件の評価にもとづき、結果のライトバックを選択的に抑制するように拡張される。先頭の命令が実行を完了し、命令が述語化されないか、または命令が述語化されて、述語条件が真と評価される場合、命令が第３の機構Ｃまたは第４の機構Ｄのいずれかを用いて、退去される。第３の機構の場合、オペレーションのあらゆる結果値が、体系化レジスタ・ファイル３６０及び体系化述語レジスタ・ファイル４１０に、または体系化プログラム順序マシン状態の任意の他の部分に退去される。第４の機構の場合、退去される命令の結果及び全ての続く結果が取り消され、実行が現命令からプログラム順序に再スタートされる。退去キュー３５５の先頭の命令が述語化されて、述語条件が偽と評価される場合、このオペレーションの結果が抑制され、退去は次の命令に継続する。
【００６０】
最適化された実施例は、述語条件が偽と評価される場合、述語を有するオペレーションに応じて、オペレーションの実行を抑制し得る。更に別の最適化された実施例は、（例えば述語条件の評価のための入力として作用する、ソース述語レジスタの使用不能により、）述語条件が評価される前に、オペレーションをディスパッチし、述語条件を退去時にだけ評価する。
【００６１】
更に本発明の別の実施例によれば、命令実行述語の予測をサポートし、実行抑制にもとづき実現されるスーパスカラ・プロセッサに、次の機構が追加される。
（１）述語を予測する第１の機構１。
（２）述語予測をアクセスする第２の機構２。
（３）命令の述語が値”偽”を有すると予測される場合、その命令の実行を抑制し、こうした命令を直接退去キュー３５５にバイパスする第３の機構３。
（４）予測の正当性をチェックする第４の機構４。
（５）予測テーブル内の不正な予測を更新し、予測ミスされた命令ポイントから実行を再スタートする第５の機構５。
【００６２】
前述の機構（１乃至５）は、本発明の趣旨及び範囲を維持したまま、異なるオペレーションに、またはオペレーションの処理内の異なるフェーズに関連付けられる。例えば、（述語を予測する）第１の機構１は、述語を計算する命令がフェッチされるとき、またはこの述語を使用する命令がフェッチされるとき、使用され得る。第１の機構１が述語を使用する命令によりトリガされるとき、第１の機構１は命令がフェッチされている間に（すなわち命令の命令アドレスにより）、若しくは命令が解読されたとき、または命令が機能ユニット３４５に発行される準備が完了するとき、トリガされる。
【００６３】
説明の都合上、（ｉ）予測をする機構が、こうした予測を使用する命令のフェッチに関連付けられ（すなわちフェッチの間のその命令アドレスにより関連付けられる）、（ｉｉ）予測がこのまたは他の述語使用オペレーションによる将来の使用のために、予測述語レジスタ・ファイルにより記憶されると仮定する。しかしながら、予測をする機構は、例えば命令解読または命令発行などの、命令処理の他のステージにも関連付けられ得る。更に、予測は予測テーブルまたは他の手段に記憶され得て、それにより予測述語レジスタ・ファイルが省略され得る。当業者であれば、本発明の趣旨及び範囲を維持したまま、ここで開示される本発明の様々な実施例を容易に変更できよう。
【００６４】
第２の機構２は、命令フェッチの後に、述語レジスタ番号が使用可能になるとき使用される。次に予測述語レジスタ・ファイル５１０がプログラム順序にアクセスされて、予測述語レジスタ値を決定する。
【００６５】
ディスパッチ・ユニット３３０は命令を機能ユニット３４５に発行するか、命令の実行を抑制し、即時命令を退去キュー３５５に受け渡す（後者は命令が実行されないと予測されるときに発生する）。
【００６６】
予測の正当性をチェックする機構は、プロセッサの退去ステージ内で実現され、述語命令がプログラム順序に退去されるとき、それらのために実行される。比較論理５２０は、予測を体系化述語レジスタ・ファイル４１０のプログラム順序状態と比較することにより、述語予測の正当性をチェックする。予測が正しくない場合、予測器が退去フェーズの間に更新され、命令の実行が正しい予測により再スタートされる。
【００６７】
この処理シーケンス、並びに実行述語の予測及び命令実行の抑制をサポートするプロセッサ内に存在する機構にもとづき、プロセッサは各命令を次のように処理する。
（１）命令をフェッチし、同時に予測器にプログラム・カウンタ３６５の値を問い合わせる。
（２）予測値を全体的な予測述語状態に追加する。
（３）命令により使用されるあらゆる述語を探索する。
（４）命令を命令バッファ３２５に入力する。
（５）命令を発行する。
（６）命令が実行されると予測される場合、それを実行する。それ以外では、命令の実行をバイパスする。
（７）命令が実行された場合、フューチャ・レジスタ・ファイル３３５を更新する。
（８）（命令が実行されたか否かに関わらず、）命令を述語及びその予測に関する情報と共に、退去キュー３５５に入力する。
（９）命令を退去する時期が到来するとき、予測が正しかったか否かをチェックする。
（１０）予測が正しくなかった場合、投機状態情報を廃棄し、プログラム・カウンタ値に対応するアドレスから、実行を再スタートすることにより、予測ミス修復を実行する。述語予測ミス修復は、分岐予測ミス修復と同様に実行される。
（１１）予測が正しかった場合、フューチャ・レジスタ・ファイル３５５及び体系化述語レジスタ・ファイル４１０のプログラム順序状態を更新する。
【００６８】
図５は、本発明に従う述語予測により、非プログラム順序のスーパスカラ実行を実行するシステム５００を示す。システム５００は、メモリ・サブシステム３０５、命令キャッシュ３１０、データ・キャッシュ３１５、及びプロセッサ・ユニット５２５を含む。プロセッサ・ユニット５２５は命令バッファ３２５、ディスパッチ・ユニット３３０、フューチャ・レジスタ・ファイル３３５、分岐ユニット（ＢＵ）３４０、複数の機能ユニット（ＦＵ）３４５、複数のメモリ・ユニット（ＭＵ）３５０、退去キュー３５５、体系化レジスタ・ファイル３６０、プログラム・カウンタ（ＰＣ）３６５、体系化述語レジスタ・ファイル４１０、予測器５０５、予測述語レジスタ・ファイル５１０、制御論理５１５、及び予測検証論理５２０を含む。
【００６９】
図６は、本発明の実施例に従い、述語予測を用いて述語命令を実行する方法を示すフローチャートである。この方法は単一パイプライン構造の典型的なオペレーションに対応する。しかしながら、本発明の趣旨及び範囲を維持する上で、他のパイプライン構造を使用する様々な他の実施例が、当業者により容易に決定され、実現されよう。
【００７０】
命令キャッシュ３１０をプログラム・カウンタ３６５の値（アドレス）によりアクセスすることにより、命令が命令キャッシュ３１０から（またはキャッシュ・ミスの場合、命令メモリ・サブシステム３０５から）フェッチされる（ステップ６０５）。
【００７１】
好適には、ステップ６０５の実行と同時に、予測器５０５が命令の予測を記憶するか否かが決定される（ステップ６１０）。この決定は、プログラム・カウンタ３６５に記憶される値（アドレス）を予測器５０５に提供し、その値がそこに記憶される命令アドレスに一致するか否かを判断することにより下される。一致する場合、その命令の予測が予測器５０５から出力される。
【００７２】
予測器５０５に記憶される予測は、予測される述語レジスタ番号と、その述語レジスタに対して予測される値とから成る。予測器５０５は１つの予測において、複数の予測レジスタを予測するように実現される。任意の予測が予測器５０５から返却される場合、予測が予測述語レジスタ・ファイル５１０内で更新される（ステップ６１５）。
【００７３】
命令キャッシュ３１０により返却される命令の述語フィールドにより、予測述語レジスタ・ファイル５１０をアクセスすることにより、命令の述語の予測が検索される（ステップ６２０）。フェッチされた命令を記述する記録が、次に命令バッファ３２５に記憶される（ステップ６２５）。記録は命令アドレス、命令、述語レジスタ番号、及びその述語レジスタの予測述語値を含む。
【００７４】
命令はディスパッチ・ユニット３３０により、命令バッファ３２５から発行される（ステップ６３０）。次に、命令の述語が真と予測されるか否かが判断される（ステップ６３５）。否定の場合、命令が直接退去キュー３５５にバイパスされ（ステップ６４０）、方法はステップ６６０に移行する。しかしながら、命令の述語が真と予測される場合、命令は１つ以上の実行ユニット（３４０、３４５、３５０）に渡され、これらが命令を実行する（ステップ６４５）。実行ユニットは１つ以上のパイプライン・ステージを含み得る。実行ユニットはそれらの入力をフューチャ・レジスタ・ファイル３３５から受信し、オペランド参照を解析する。
【００７５】
命令が実行ユニット（３４０、３４５、３５０）内で実行を完了するとき、命令結果がフューチャ・レジスタ・ファイル３３５内で更新され（ステップ６５０）、体系化状態に対するプログラム順序のコミットメントのために、退去キュー３５５に追加される（ステップ６５５）。エラー及び例外ステータスに関する追加の情報が退去キュー３５５に追加されて、投機的に実行される例外のために、例外を順番に発生する。
【００７６】
次に、命令の述語の予測が正しかったか否か、更に命令が例外無しに実行されたか否かが判断される（ステップ６６０）。ステップ６６０は予測検証論理５２０により、予測された述語レジスタを、現プログラム順序体系化状態と比較することにより実行される。
【００７７】
予測が正しく、命令が例外の発生無しに実行された場合、命令が体系化レジスタ・ファイル３６０及び体系化述語レジスタ・ファイル４１０に、プログラム順序に退去される（ステップ６６５）。
【００７８】
しかしながら、予測が正しくないか、命令が例外を発生した場合（または他のエラーに遭遇した場合）、制御論理５１５がこの命令を更に処理する（ステップ６７０）。例えば、述語予測ミスの場合、予測器５０５が述語レジスタの正しい予測により更新され、予測ミス・ポイントのプログラム順序状態が復元されて、プログラム・カウンタ３６５が更新される。予測器５０５はその情報を用いて、任意の既存の予測方式にもとづくその予測機構を更新する。実行は予測ミス・ポイントから再開する。例外は、例外ポイントでのプログラム順序状態を復元し、例外ハンドラを開始することにより同様に処理される。
【００７９】
本発明の別の実施例では、予測述語値が予測器から、フェッチされた命令を含むキュー・エントリに直接転送される。この実施例は、予測述語レジスタ・ファイル５１０へのアクセスを除去することにより、特定の命令に対する予測を獲得するためのステップ数（及び遅延）を低減する。すなわち、ある実施例では実際に予測述語レジスタ・ファイルを省略するが、予測テーブル内により多くのエントリを要求する犠牲を伴う。前述の実施例では、予測述語レジスタ・ファイル５１０が、同一の述語をアクセスする複数の命令間で、予測述語値の共用を可能にしたが、予測器５０５内で単一のエントリを要求するだけであった。
【００８０】
図７は、本発明の実施例に従い、実行抑制を用いて、非プログラム順序のスーパスカラ実行を実行し、未解決の述語のために述語予測を使用するシステムを示す図である。図７は、データ・パスの関連部分だけを示すように、単純化されている。
【００８１】
システム７００は、命令キャッシュ３１０及びプロセッサ・ユニット７２０を含む。プロセッサ・ユニット７２０は命令バッファ３２５、ディスパッチ・ユニット３３０、フューチャ・レジスタ・ファイル３３５、退去キュー３５５、体系化レジスタ・ファイル３６０、プログラム・カウンタ（ＰＣ）３６５、体系化述語レジスタ・ファイル４１０、予測器５０５、予測述語レジスタ・ファイル５１０、制御論理５１５、予測検証論理５２０、命令実行ユニット７１０（分岐ユニット（ＢＵ）３４０、複数の機能ユニット（ＦＵ）３４５、及び複数のメモリ・ユニット（ＭＵ）３５０を集合的に含む）、及びバイパス手段７０５を含む。
【００８２】
バイパス手段７０５は、フューチャ述語レジスタ・ファイル４０５から述語値をバイパスする。このバイパスは、正しい結果が既に計算された値に対する予測を無効にする機能を提供する。これは予測精度の向上につながる。なぜなら、より少数の予測が記憶されなければならず、同一のテーブル・サイズを有する予測器５０５の効率を向上させるからである。
【００８３】
述語値が次に、前述の実施例の場合同様にテストされ、処理が前述のように継続する。述語が予測されたか、または実際に使用可能かに関する処理には区別は無いが、実行の前に有効な述語が知れた命令は、命令がプログラム順序に退去されるとき、必ず体系化述語レジスタ状態に一致しなければならない。従って、こうしたオペレーションは、他の場合のように、予測ミスのペナルティを招かない。
【００８４】
この最適化は好適には、述語レジスタのレジスタ・リネーミングに関連付けられる。使用される実際のレジスタ・リネーミング方式は、本発明にとって重要ではなく、任意のレジスタ・リネーミング方式が使用され得る。
【００８５】
本発明の実施例によれば、命令実行述語の予測をサポートし、命令実行後のライトバック抑制にもとづき実現されるスーパスカラ・プロセッサが、次の機構を追加される。
（１）述語を予測する第１の機構（ｉ）。
（２）述語予測をアクセスする第２の機構（ｉｉ）。
（３）実行述語の実際の値を選択するか、こうした述語が計算されなかった場合、こうした実行述語の予測値を選択する第３の機構（ｉｉｉ）。
（４）予測の正当性をチェックする第４の機構（ｉｖ）。
（５）予測テーブル内の不正な予測を更新し、予測ミスされた命令ポイントから実行を再スタートする第５の機構（ｖ）。
【００８６】
前述の機構は本発明の趣旨及び範囲を維持したまま、異なるオペレーションに、またはオペレーションの処理内の異なるフェーズに関連付けられる。例えば、（述語を予測する）第１の機構（ｉ）は、述語を計算する命令がフェッチされるときに、またはこの述語を使用する命令により使用され得る。第１の機構（ｉ）が述語を使用する命令によりトリガされるとき、こうした機構はこうした命令がフェッチされている間に（すなわちこうした命令の命令アドレスにより）、若しくはこうした命令が解読されたとき、またはこうした命令が機能ユニット３４５に発行される準備が完了するとき、トリガされる。
【００８７】
説明の都合上、第１の機構（ｉ）が、こうした予測を使用する命令のフェッチに関連付けられ（すなわちフェッチの間のその命令アドレスにより関連付けられる）、予測がこのまたは他の述語使用オペレーションによる将来の使用のために、予測述語レジスタ・ファイル５１０により記憶されると仮定する。しかしながら、第１の機構（ｉ）は、例えば命令解読または命令発行などの、命令処理の他のステージにも関連付けられ得る。更に、予測は予測テーブルまたは他の手段に記憶され得て、それにより予測述語レジスタ・ファイルが省略され得る。当業者であれば、本発明の趣旨及び範囲を維持したまま、ここで開示される本発明の様々な実施例を容易に変更できよう。
【００８８】
第２の機構（ｉｉ）は、命令フェッチの後に、述語レジスタ番号が使用可能になるときアクセスされる。次に予測述語レジスタ・ファイル５１０がプログラム順序にアクセスされて、予測述語レジスタ・ファイル５１０の値を決定する。
【００８９】
命令が実行された後、実際の実行述語が使用可能な場合、第３の機構（ｉｉｉ）がそれを選択し、実際に計算された値が使用可能でない場合には、その予測値を選択する。そして、フューチャ・レジスタ・ファイル３３５及びフューチャ述語レジスタ・ファイル４０５の更新を抑制する。
【００９０】
第４の機構（ｉｖ）はプロセッサの退去ステージ内で実現され、述語命令がプログラム順序に退去されるとき、それらのために実行される。第４の機構（ｉｖ）は、予測を体系化述語レジスタ・ファイル４１０のプログラム順序状態と比較することにより、述語予測の正当性をチェックする。予測が正しくない場合、予測器５０５が退去フェーズの間に更新されて、述語予測ミス修復が実行され、命令の実行が正しい予測により再スタートされる。
【００９１】
図８は、本発明の実施例に従い、ライトバック抑制を用いて、非プログラム順序のスーパスカラ実行を実行し、未解決の述語のために述語予測を使用するシステムを示す図である。図８は、データ・パスの関連部分だけを示すように単純化されている。
【００９２】
システム１０００は、命令キャッシュ３１０及びプロセッサ・ユニット１０２０を含む。プロセッサ・ユニット１０２０は命令バッファ３２５、ディスパッチ・ユニット３３０、フューチャ・レジスタ・ファイル３３５、退去キュー３５５、体系化レジスタ・ファイル３６０、プログラム・カウンタ（ＰＣ）３６５、体系化述語レジスタ・ファイル４１０、予測器５０５、予測述語レジスタ・ファイル５１０、制御論理５１５、予測検証論理５２０、命令実行ユニット７１０（分岐ユニット（ＢＵ）３４０、複数の機能ユニット（ＦＵ）３４５、及び複数のメモリ・ユニット（ＭＵ）３５０を集合的に含む）、及び述語バイパス１００５を含む。
【００９３】
命令メモリ・サブシステム３０５（任意的にキャッシング階層を含む）は、プログラム・カウンタ３６５のアドレスによりアクセスされ、対応する命令ワードをキャッシュから（或いはキャッシュ・ミスが発生したとき、またはキャッシュが特定のシステム内に存在しない場合には、主メモリから）返却する。
【００９４】
同時に、プログラム・カウンタ３６５に記憶される値が、予測器５０５に対し、任意の予測がその命令アドレスに関連付けられるか否かを問い合わせるために使用される。予測は予測される述語レジスタ番号と、その述語レジスタに対して予測される値とから成る。予測器は１つの予測において、複数の予測レジスタを予測するように実現される。任意の予測が予測器から返却される場合、予測が予測述語レジスタ・ファイル５１０内で更新される。
【００９５】
命令キャッシュ（図示せず）により返却される命令ワードの述語フィールドが、予測述語レジスタ・ファイル５１０をアクセスするために使用され、その述語の予測が検索される。フェッチされた命令ワードを記述する記録が、次に命令バッファ３２５に記憶される。記録は命令アドレス、命令ワード、述語レジスタ、及びその述語レジスタの予測値を含む。
【００９６】
命令はディスパッチ・ユニット３３０により、命令バッファ３２５から発行される。命令は命令実行ユニット７１０により実行される。命令実行ユニット７１０は１つまたは複数のパイプライン・ステージから成り、１つ以上の機能ユニット３４５を有する。実行ユニット７１０はフューチャ・レジスタ・ファイル３３５及びフューチャ述語レジスタ・ファイル４０５と通信して、オペランド参照を解析する。命令が実行ユニット７１０内で実行を完了するとき、実行述語がフューチャ述語レジスタ・ファイル４０５から探索される。値が既に計算されている場合、それが述語バイパス１００５によりバイパスされ、予測を無効にする。
【００９７】
結果は、予測されるまたは正確な結果である実行述語である。この実行述語が真と評価される場合、オペレーションの結果がフューチャ・レジスタ・ファイル３３５またはフューチャ述語レジスタ・ファイル４０５にコミットされる。両方の場合に（実行述語が真または偽のいずれかであるとき）、実行ユニット７１０内の実行の結果が退去キュー３５５に追加される。
【００９８】
命令がプログラム順序に退去されるとき、予測検証論理５２０により、予測された述語レジスタが現プログラム順序体系化状態と比較される。正しい述語値が述語バイパス１００５によりバイパスされた場合、この検証は定義ごとに必然的に正しい。予測が正しく、命令が例外を生じなかった場合、命令が体系化レジスタ・ファイル３６０及び体系化述語レジスタ・ファイル４１０にプログラム順序に退去される。
【００９９】
予測が正しくなかった場合、または命令が例外を生じた場合（または他のエラーに遭遇した場合）、制御論理５１５がこの命令を更に処理する。述語予測ミスは、予測器５０５を述語レジスタの正しい予測により更新することにより処理される。予測器５０５はその情報を用いて、任意の既存の予測方式にもとづくその予測機構を更新する。更に述語が予測ミスされた場合、予測ミス・ポイントでのプログラム順序状態が復元され、プログラム・カウンタ３６５が更新される。実行は予測ミス・ポイントから再開する。例外は、例外ポイントでのプログラム順序状態を復元し、例外ハンドラを開始することにより、同様に処理される。
【０１００】
図９は、本発明の実施例に従い、述語予測精度を改善するシステム１２００を示す図である。システム１２００は、命令ストリームをスヌープし、予測述語レジスタ・ファイル５１０上で単純な述語オペレーションを実行することにより、予測精度を改善する。システム１２００は命令スヌープ論理１２０５、及び述語操作オペレーションのサブセットを実行する述語予測エンハンスメント論理１２１０を含む。
【０１０１】
スヌープ論理１２０５は命令ストリームを”スヌープ”して、述語計算命令がフェッチされたか否かを判断するが、命令ストリームを未変更のまま維持する。スヌープ論理１２０５は、命令メモリ・サブシステム３０５からフェッチされた命令が、述語予測エンハンスメント論理１２１０により実現される述語計算オペレーションのサブセット（実施例に依存する）の一部であるか否かをテストする。
【０１０２】
このサブセットは、例えば全ての述語操作オペレーション、それらのサブセット、または述語移動オペレーションなどの単一命令から成る。述語操作オペレーションは、例えばＰｏｗｅｒＰＣ（商標）アーキテクチャなどの幾つかのアーキテクチャにおいてサポートされる。
【０１０３】
スヌープ論理１２０５がこうしたオペレーションを検出するとき、それは命令ストリームからコピーを抽出し（但し命令ストリームから命令を除去しない）、述語予測エンハンスメント論理１２１０に、予測述語レジスタ・ファイル上でオペレーションを実行するように指示する（この実行は好適にはプログラム順序に実行される）。
【０１０４】
実行される述語オペレーションのサブセットが、単に単一命令（述語レジスタ移動オペレーション）から成り、次の命令シーケンスが実行されるケースについて考えてみよう。
【数４】
0003565499.tif 000005
【０１０５】
前記模範的な命令シーケンス（命令１乃至４）は、ＩＢＭ  ＰｏｗｅｒＰＣ（商標）アーキテクチャにもとづくもので、条件節により示される追加の予測機能を有する。ここで条件節は任意的に命令を従え、どの述語が命令の実行のために真に評価されなければならないかを示す。
【０１０６】
述語予測エンハンスメント論理１２１０が述語予測と併せて、条件レジスタ移動を実現するために使用されるとき（条件レジスタはＩＢＭ  ＰｏｗｅｒＰＣ（商標）アーキテクチャにおける４つの述語の集まりである）、４番目の命令が実行される前に、述語ｃｒ５．ｅｑのために追加の予測は要求されない。これはプログラム内で要求される予測の数を低減し、予測器により使用される所与のテーブル・サイズの全体的な予測有効性を向上させる。更に、命令２だけが予測ミス・ペナルティを招き得る。なぜなら、命令４は常に、命令２に対して生成された予測を使用することが保証されているからである。従って、命令２の述語予測が正しかった場合、命令４の述語予測も正しい。しかしながら、命令２の述語予測が正しくなかった場合、追加の予測ミス・ペナルティは命令４により生成されない。なぜなら、制御論理５１５が予測器に命令２の予測を更新し、命令２から実行を再スタートするように指示するからである。
【０１０７】
前述の述語予測の使用により、実行が”ｉｆ”文の正に１つの分岐に沿って進むことになる。なぜなら、実行が命令の”最も有望な”シーケンスに還元されるからである。別の実施例では、予測実行パラダイムに従い、しかしながら非プログラム順序の実行及びレジスタ・リネーミングと併せて、複数のパスの積極的な同時実行を可能にする。
【０１０８】
本発明の以下の実施例では、実行述語を有する命令の実行が、データ依存性予測機構と関連して実行される。データ依存性予測機構は、ある命令のどの結果レジスタが、別の命令のどの入力レジスタにより参照されるかを予測する。
【０１０９】
再度、この例のために、追加の１文により拡張された前述のコード・フラグメントについて考えてみよう。
【数５】
0003565499.tif 000006
【０１１０】
ＩＢＭ  ＰｏｗｅｒＰＣ（商標）の非予測命令シーケンスは次のようである（ソース・コード・ライン５の文に対応するコードは、ラベルＬ２に当たる）。
【数６】
0003565499.tif 000007
【０１１１】
同様に、予測をサポートするように変更される、ＩＢＭ  ＰｏｗｅｒＰＣ（商標）アーキテクチャを使用するこのコードの命令シーケンスは、次のようになる。
【数７】
0003565499.tif 000008
【０１１２】
このコード・シーケンス例のレジスタ・リネーミングによる、非プログラム順序の実行について考えてみよう。命令はプログラム順序にフェッチされ、次にプログラム順序に解読される。それらがディスパッチ・ユニット３３０に達すると、各命令の宛先レジスタ指定子が適宜、フューチャ・レジスタ・ファイル３３５及びフューチャ述語レジスタ・ファイル４０５内のレジスタにリネームされる。
【０１１３】
Ｉ１の宛先ｃｒ０が（フューチャ述語レジスタ・ファイル４０５内の）ＰＲ６５にリネームされ、Ｉ２の宛先ｒ３がＲ６６にリネームされ、Ｉ３の宛先ｒ３がＲ６７にリネームされ、Ｉ４の宛先ｒ２０がＲ６８にリネームされると仮定する（Ｒ６６、Ｒ６７、Ｒ６８の各々は、フューチャ・レジスタ・ファイル３３５内に存在する）。ディスパッチ・ユニット３３０はまた、体系化レジスタ・ファイル３６０及び体系化述語レジスタ・ファイル４１０に、これらの命令のソース・レジスタ・オペランドの値をプログラム順序で問い合わせる。従って、最初に、Ｉ１内のソース・オペランドであるｒ３の値が問い合わされ、体系化レジスタ・ファイル３６０から獲得される。次に、Ｉ２内のソース・オペランドであるｒ３の値が問い合わされ、体系化レジスタ・ファイル３６０から獲得される。次に、Ｉ３内のソース・オペランドであるｒ３の値が問い合わされ、命令Ｉ２の宛先レジスタに割当てられるフューチャ・レジスタ・ファイルから、ｒ３の値を割当てられる。次に、Ｉ４内のソース・レジスタであるｒ３の値が、体系化レジスタ・ファイル３６０から問い合わされる。この時点で、ディスパッチ・ユニット３３０は、Ｉ３により生成されたｒ３の値が、Ｉ４により使用されるべきことを検出する（再度、純粋な依存性の場合）。従って、Ｉ４により使用される値が使用不能であることが宣言され、一旦値が生成されると、フューチャ・レジスタ名すなわちこの場合Ｒ６７がＩ４と共に、値を獲得する場所の指示としてコピーされる。
【０１１４】
前述のスケジューリング及びリネーミング・アクションの結果、次のスケジュールが生成される。
【数８】
0003565499.tif 000009
【０１１５】
これは明らかに誤りである。なぜなら、加算命令３の入力依存性がｒ３の前の体系化値により満足されるべきであるからである。同様に、ｒ３＜０の場合、命令４への入力依存性が、命令２により計算されるレジスタｒ３のリネーム名により、Ｒ６６に帰着されるべきである。
【０１１６】
本発明に従うプロセッサの次の実施例は、データ依存性を予測し、レジスタ・リネーミングを導くことにより、この状況を修正する技術を提供する。プロセッサは次のコンポーネントを含む。
（Ａ）リネームされた各体系化レジスタに関連付けられるフューチャ・レジスタ名のリストを保持する第１の機構Ｉ（例えばリストはｒ３に対して［Ｒ６７、Ｒ６８］を含む）。
（Ｂ）述語命令の体系化宛先レジスタをリネームし、その体系化レジスタに対して、フューチャ・レジスタ名をフューチャ・レジスタ名のリストに追加する第２の機構ＩＩ（例えば、ｒ３に対するリストが最初に空の場合、リストはＩ２内のｒ３がリネームされるとき、［Ｒ６７］を含み、Ｉ２内のｒ３がリネームされるとき、［Ｒ６７、Ｒ６８］を含む）。
（Ｃ）ソース・レジスタ名として使用されるフューチャ・レジスタ名の１つ（例えばｒ３に対するリストからのＲ６７またはＲ６８）を正確に予測する第３の機構ＩＩＩ。
（Ｄ）この予測を、予測が実施されなければならなかった命令に関連付ける第４の機構ＩＶ（例えばＲ６７が予測された名前の場合、命令Ｉ４がそれと一緒にその情報を伝搬する）。情報はこうした各命令のソース・オペランドの各々に対して伝搬される。
（Ｅ）命令が退去される準備が完了した時点、及び命令に関連付けられるフューチャ・レジスタ名が正しいか否かを検出する第５の機構Ｖ。フューチャ・レジスタ名が正しくない場合、この機構は当業者には明らかな分岐予測ミスの修正と同様に、退去キュー３５５の内容をスカッシュする。
（Ｆ）予測ミスの検出に際して、前記の第３の機構内に導入された予測器の状態を修正する第６の機構ＶＩ。
【０１１７】
第１（Ｉ）、第２（ＩＩ）、第３（ＩＩＩ）の機構が図１０に示され、これは図４に示されるディスパッチ・ユニット３３０に組み込まれるハードウェアを含む。
【０１１８】
図１０は、本発明の実施例に従い、コンピュータ処理システムにおいて、データ依存性を予測する装置１４００を示す図である。装置１４００はリネーム論理１４０５、体系化−フューチャ・レジスタ名変換マップ１４１０、及び予測器５０５を含む。
【０１１９】
図１０では、リネーム論理１４０５が第２の機構ＩＩを含み、体系化−フューチャ・レジスタ名変換マップ１４１０が第１の機構Ｉを含む。第３の機構ＩＩＩは予測器５０５として示される。命令の体系化宛先レジスタがリネームされるとき、体系化名がリネーム論理１４０５に提供される。リネーム論理１４０５は内部状態を有し、これを調べることにより、体系化宛先レジスタに割当てられる新たなフューチャ・レジスタ名を生成する。このペア（体系化宛先レジスタ名、フューチャ・レジスタ名）が、体系化−フューチャ・レジスタ名変換マップ１４１０内の体系化宛先レジスタ名に対して、リスト内のエントリを更新するために使用される。説明の都合上、図１０では最大４個のエントリが各リストに対して選択される。しかしながら、本発明に従う他の実施例では、リスト内に単一のエントリを含んだり、４以外の複数のエントリを含み得る。
【０１２０】
体系化ソース・レジスタがリネーム論理１４０５に提供されて、そのフューチャ・レジスタ名を獲得するとき、体系化ソース・レジスタ名が予測器５０５に提供される。予測器５０５は体系化−フューチャ・レジスタ名変換マップ１４１０内の名前のエントリを指標付けし、予測技法を用いて、この変換マップ１４１０から、複数のフューチャ・レジスタ名の１つ（または体系化名）を予測する。この予測は命令と共に退去キュー３５５にコピーされる。
【０１２１】
第４の機構ＩＶを実現するために必要とされる余分な情報は、退去キュー３５５に組み込まれると仮定するので、別途示されていない。
【０１２２】
第５（Ｖ）及び第６（ＶＩ）の機構は図１１に示され、これは本発明の実施例に従い、退去される命令の体系化ソース・レジスタ名から、フューチャ・レジスタ名の予測を検証する方法を示すフローチャートである。
【０１２３】
命令が退去されるとき、命令内の各所与のソース・オペランドが、体系化−フューチャ・レジスタ名変換マップ１４１０（特に、変換マップ１４１０のフューチャ・レジスタ名１４１０ｂのリスト）内において、複数のフューチャ・レジスタ名に対応するか否かが判断される（ステップ１５０２）。否定の場合、この方法は終了する（ステップ１５０４）。肯定の場合、方法はステップ１５０６に移行する。
【０１２４】
各ソース・オペランドの実際の名前（予測器自身内で実際の結果として保持される）が、予測された名前（退去キュー３５５内に命令と共に保持される）に対応するか否かが判断される（ステップ１５１０）。
【０１２５】
各ソース・オペランドに対して、実際の名前が予測された名前に対応しない（すなわち一致が存在しない）場合、予測ミス修復が命令に対して開始される（ステップ１５１２）。予測ミス修復は、退去キュー３５５内の全てのオペレーションを無効とマークするステップと、退去キュー３５５をフラッシュするステップと、マシンをリセットして、予測ミスが検出された命令から再度命令をフェッチするステップとを含む。他方、各ソース・オペランドに対して、実際の名前が予測された名前に対応する（すなわち一致が存在する）場合、予測は正しいと見なされ、方法はステップ１５１４に移行する。
【０１２６】
ステップ１５１４で、通常の退去アクションが実行される。例えば、それが述語命令であり、制御述語の値が真の場合、そのフューチャ宛先レジスタの内容が前述のように、体系化レジスタ・ファイルにコピーされる。述語の値が偽と判明したため、述語オペレーションが退去されない場合、その宛先レジスタに割当てられるフューチャ・レジスタの名前が、割当て解除される。従って名前が再度使用可能になる。
【０１２７】
図１０に示される本発明の好適な実施例は、ソース・オペランドの処理、及びその予測ミスのためのチェックを同時に実行する。しかしながら、本発明の他の実施例は、ソース・オペランドの処理、及びその予測ミスのためのチェックを順次的に実行する。当業者であれば、本発明の趣旨及び範囲を維持しながら、これらの及び様々な他の実施例が考えられることが理解できよう。
【０１２８】
名前予測器の１実施例は、位置に関わる。体系化レジスタに対するネーム・リスト内の各位置が、それに関連付けられる状態を有する。新たな名前がリストに入力されるとき、名前により保持される位置が有効にされる。リスト上の多くのエントリの１つが、ヒステリシス・ベースの１または２レベル適応分岐予測器（またはそれらの組み合わせ）に類似の様々な技法を用いて、予測結果として選択される。
【０１２９】
予測ミスを修正するために、所与の体系化名の正しい名前が退去キュー３５５から受信される。名前の”位置”の”ヒステリシス”が低減される。名前内のヒステリシスのレベルが最低レベルの時、予測器のバイアスが実際の結果にシフトされる。予測器５０５に関連付けられる状態マシンは当業者にとって認識可能であり、様々な態様で実現され得る。
【０１３０】
最適化された実施例では、名前そのものではなく、予測器内の名前の位置が、予測時にオペレーションに関連付けられる。この最適化は予測ミス修復の性能を大幅に改善する。
【０１３１】
別の最適化された実施例は、機構全体を通じて単に位置標識を使用する。これは、たとえ異なるフューチャ・レジスタ名が同一のコード部分の実行において異なる時点に使用されても（例えばループ内で、または関数がプログラム内の異なる場所から複数回呼び出されるとき）、実行内の異なる場所の各々においてリネーム名の予測可能性を妨げることなく、位置割当てが同一順序に維持されることを保証する。
【０１３２】
予測器の更に別の実施例は、予測器状態をリスト内での予測名の位置だけではなく、実際の予測名に関連付ける。この方法は、この名前を予測器ルックアップ及び訂正論理（すなわち体系化−フューチャ・レジスタ名変換マップ１４１０）内で使用する。別の可能性は、命令アドレスを予測器状態に関連付け、それらを予測器をアクセス及び更新するために使用することである。ここでの教示にもとづき、当業者であれば、本発明の趣旨及び範囲を維持したまま、これらの及び様々な他の実施例を容易に決定できよう。
【０１３３】
別の実施例では、命令が、その述語条件がまだ解析されていない別の述語命令の結果に依存するとき、述語予測が使用されない。図９を参照して、ソース・レジスタが２つ以上の名前を含む場合、こうしたソース・レジスタを参照する命令が命令ストリーム内に複数回入力される。入力される命令はソース・レジスタの組み合わせを含み、命令が条件付き構成に述語化される。従って、制御が現命令にプログラム順序に達するときに、命令のこの実体化により使用される入力レジスタが、プロセッサの状態に対応する場合に限り、述語は真である。
【０１３４】
別の実施例では、データ依存性予測が、ソース・レジスタの複数のリネーム・レジスタ名を提供する。こうした命令の複数のコピーが発行され、各々が異なるリネーム・レジスタを参照する。図１０を参照すると、体系化レジスタがそれに関連付けられる複数のリネーム・レジスタを有し得る。例えば前述の例のＩＢＭＰｏｗｅｒＰＣ（商標）命令Ｉ４などの命令が、複数のリネーム候補を有するソース・オペランドを含むとき（この場合、候補はリネーム・レジスタＲ６６及びＲ６７の他に、ｒ３の体系化値である）、データ依存性予測が複数の予測を生成する。前述のコード例では、これらの予測はリネーム・レジスタＲ６６及びＲ６７を参照する。次にディスパッチ・ユニットが命令（この例ではＩ４）を複数回、入力オペランドの各適切な組み合わせに対して１回発行し（全ての組み合わせが発行される必要はない）、リネーム・レジスタの選択された組み合わせが、発行される命令における体系化状態に対応するケースを示す条件で、述語を発行する。命令Ｉ４の場合、ｒ３はＰＲ６５．ｌｔが真の場合、正にＲ６６の値を有し、ＰＲ６５．ｌｔが偽の場合、Ｒ６７の値を有する。
【０１３５】
前述のスケジューリング及びリネーミング・アクションの結果、サンプル例は次の命令シーケンスとして発行される。
【数９】
0003565499.tif 000010
【０１３６】
これは命令実行の間のハイパブロック構造の形成に対応し、従ってコード部分が複製されて、全ての実行述語が使用可能になる前に、複数の可能なパスに沿って投機的に実行される。
【０１３７】
最適化された実施例では、ソース・レジスタの予測が十分に困難な場合、コード複製及び再発行（すなわちハードウェア・ベースのハイパブロック形成）が実行される。従って、十分な予測精度が獲得される場合、データ依存性予測が使用される。一部のソース・レジスタでは、複数のレジスタ名が供給されて、コード複製が実行される。リネーム・レジスタの供給数は、リネーム・リスト全体であるか、最も有望なソース・レジスタに対応するサブセットである。
【０１３８】
まとめとして、本発明の構成に関して以下の事項を開示する。
【０１３９】
（１）コンピュータ処理システムにおいて、命令の順序付けシーケンスを実行する方法であって、命令のシーケンスがシステムのメモリに記憶され、命令の少なくとも１つが、関連フラグ値にもとづき条件付きで実行される少なくとも１つのオペレーションを表す述語命令を含むものにおいて、
メモリから命令のグループをフェッチするステップと、
グループ内の命令の実行をスケジュールして、述語命令を命令の順序付けシーケンス内のその元の位置から、命令のシーケンス内の非プログラム順序位置に移動するステップと、
前記スケジューリングに応答して、命令を実行するステップと
を含む、方法。
（２）前記実行するステップの結果を、命令の順序付けシーケンスに対応する順序で、体系化レジスタまたはメモリのいずれか一方に書込むステップを含む、前記（１）記載の方法。
（３）関連フラグ値が述語命令の実行において使用可能でないとき、関連フラグ値の予測値を生成するステップを含む、前記（１）記載の方法。
（４）予測値にもとづき、述語命令により表されるオペレーションの実行を変更するステップを含む、前記（３）記載の方法。
（５）前記変更するステップが、予測値にもとづき、述語命令により表されるオペレーションにより生成される結果のライトバックを、選択的に抑制するステップを含む、前記（４）記載の方法。
（６）前記変更するステップが、予測値にもとづき、述語命令により表されるオペレーションを選択的に発行するステップを含む、前記（４）記載の方法。
（７）述語命令の実行または退去のいずれかに際して、関連フラグ値の予測値が正しいか否かを判断するステップと、
関連フラグ値の予測値が正しくない場合、正しい予測を用いて述語命令を実行するステップと、
関連フラグ値の予測値が正しい場合、述語命令の実行に対応する結果を、体系化レジスタまたはメモリのいずれか一方に書込むステップと
を含む、前記（３）記載の方法。
（８）コンピュータ処理システムにおいて命令を実行する方法であって、命令がシステムのメモリに記憶され、命令の少なくとも１つが、少なくとも１つの関連フラグ値にもとづき条件付きで実行される少なくとも１つのオペレーションを表す述語命令を含むものにおいて、
メモリから命令のグループをフェッチするステップと、
グループが、その関連フラグ値が使用可能でない特定の述語命令を含む場合、関連フラグ値の予測値を表すデータを生成するステップと、
予測値にもとづき、特定の述語命令により表されるオペレーションの実行を変更するステップと
を含む、方法。
（９）前記変更するステップが、予測値にもとづき、特定の述語命令により表されるオペレーションを選択的に発行するステップを含む、前記（８）記載の方法。
（１０）前記変更するステップが、予測値にもとづき、特定の述語命令により表されるオペレーションにより生成される結果のライトバックを、選択的に抑制するステップを含む、前記（８）記載の方法。
（１１）命令をスケジューリングして、少なくとも１つの命令を命令のシーケンス内の原位置から、もっと前の位置に移動するステップを含む、前記（８）記載の方法。
（１２）前記スケジューリングが実行時に実行される、前記（１１）記載の方法。
（１３）前記スケジューリングに従い命令を実行するステップを含む、前記（１１）記載の方法。
（１４）もっと前の位置に移動される少なくとも１つの命令が特定の述語命令である、前記（１１）記載の方法。
（１５）特定の述語命令の実行または退去のいずれかに際して、関連フラグ値の予測値が正しいか否かを判断するステップと、
関連フラグ値の予測値が正しくない場合、正しい予測を用いて特定の述語命令を実行するステップと、
関連フラグ値の予測値が正しい場合、特定の述語命令の実行に対応する結果を、体系化レジスタまたはメモリのいずれか一方に書込むステップと
を含む、前記（８）記載の方法。
（１６）関連フラグ値の予測値が正しくない場合、特定の述語命令に依存する命令の結果を取り消すステップを含む、前記（１５）記載の方法。
（１７）関連フラグ値の予測値が正しいか否かを判断するステップが、予測値を体系化レジスタのプログラム順序状態と比較するステップを含む、前記（１５）記載の方法。
（１８）予測値にもとづき、特定の述語命令に依存する命令の実行を変更するステップを含む、前記（８）記載の方法。
（１９）複数の述語に対応して予測を生成し、テーブル内に記憶するステップを含む、前記（８）記載の方法。
（２０）テーブルが複数のエントリを含み、各エントリが、それぞれが少なくとも１つの述語レジスタに対応する少なくとも１つの予測述語レジスタ番号と、それぞれが少なくとも１つの述語レジスタに対応する少なくとも１つの予測フラグ値とを含む、前記（１９）記載の方法。
（２１）関連フラグ値が真または偽のいずれかであり、
複数の述語に対応する予測をテーブルに記憶するステップと、
複数の述語の少なくとも１つを含む命令の実行に際して、記憶された述語をアクセスするステップと、
その述語が真であると予測される命令を実行するステップと
を含む、前記（８）記載の方法。
（２２）予測値に対する実際の結果が既に計算されている場合、予測値を無効にするステップを含む、前記（８）記載の方法。
（２３）特定の述語命令に関連付けられる予測値にもとづき、分岐命令が実行されると予測されるか、或いは実行されないと予測されるかを決定するステップを含む、前記（８）記載の方法。
（２４）少なくとも１つの述語に対応する少なくとも１つの予測をテーブルに記憶するステップと、
少なくとも１つの予測が分岐命令に対応するとき、分岐命令が分岐し得るアドレスをテーブルに記憶するステップと
を含む、前記（８）記載の方法。
（２５）コンピュータ処理システムにおいて命令を実行する方法であって、命令がシステムのメモリに記憶されるものにおいて、
メモリから命令のグループをフェッチするステップであって、グループが少なくとも１つの関連フラグ値にもとづき条件付きで実行される、少なくとも１つのオペレーションを表す少なくとも１つの述語命令を含み、
たとえ述語命令の関連フラグ値が使用不能であっても、述語命令を含む命令のグループを実行するステップと、
未解決の述語の結果に対して、レジスタ名または値のいずれか一方のリストを記憶するステップと、
複数の名前または複数の値のいずれか一方が入手可能なレジスタを使用する命令を識別するステップと、
所与の識別された命令に対して、複数の名前または複数の値のいずれか一方の１つだけを選択するステップと、
所与の識別された命令に対応する述語の解析に際して、選択が正しいか否かを判断するステップと、
選択が正しくない場合、所与の命令に続くオペレーションの実行を変更するステップと
を含む、方法。
（２６）前記変更するステップが、所与の命令に続く、それに依存するオペレーションの実行を変更する、前記（２５）記載の方法。
（２７）コンピュータ処理システムにおいて命令を実行する方法であって、命令がシステムのメモリに記憶されるものにおいて、
メモリから命令のグループをフェッチするステップであって、グループが少なくとも１つの関連フラグ値にもとづき条件付きで実行される、少なくとも１つのオペレーションを表す少なくとも１つの述語命令を含み、
たとえ述語命令の関連フラグ値が使用不能であっても、述語命令を含む命令のグループを実行するステップと、
未解決の述語の結果に対して、レジスタ名または値のいずれか一方のリストを記憶するステップと、
複数の名前または複数の値のいずれか一方が入手可能なレジスタを使用する命令を識別するステップと、
所与の識別された命令に対して、複数の名前または複数の値のいずれか一方の少なくとも２つを選択するステップと、
選択された少なくとも２つの複数の名前または少なくとも２つの複数の値が、発行される所与の命令のプログラム順序位置における体系化状態に対応する条件で、述語を生成するステップと、
選択された少なくとも２つの複数の名前または少なくとも２つの複数の値の可能な組み合わせの各々に対して、所与の命令を複数回実行するステップと、
所与の識別された命令に対応する述語の解析に際して、どの選択が正しいかを決定するステップと、
どの選択も正しくない場合、所与の命令に続くオペレーションの実行を変更するステップと
を含む、方法。
（２８）退去される命令の体系化ソース・レジスタ名から、フューチャ・レジスタ名の予測を検証する方法であって、
命令内の各所与のソース・オペランドが、複数のフューチャ・レジスタ名に対応するか否かを判断するステップと、
所与のソース・オペランドの各々に対して使用される実際の名前が使用可能でない場合、ソース・オペランドの各々の実際の名前が、ソース・オペランドの各々に対して予測される名前に対応するか否かを判断するステップと、
少なくとも１つのソース・オペランド名が予測ミスされた場合、命令に対して予測ミス修復を実行するステップと、
ソース・オペランドの各々の実際の名前が、ソース・オペランドの各々に対して予測される名前に対応する場合、命令を退去するステップと
を含む、方法。
（２９）コンピュータ処理システムにおいて、命令の順序付けシーケンスを実行する装置であって、命令のシーケンスがシステムのメモリに記憶され、命令の少なくとも１つが、関連フラグ値にもとづき条件付きで実行される少なくとも１つのオペレーションを表す述語命令を含むものにおいて、
メモリから命令のグループをフェッチする手段と、
グループ内の命令の実行をスケジュールして、述語命令を命令の順序付けシーケンス内のその元の位置から、命令のシーケンス内の非プログラム順序位置に移動する手段と、
前記スケジューリングに応答して、命令を実行する手段と
を含む、装置。
（３０）関連フラグ値が使用不能な場合、関連フラグ値を予測する手段を含む、前記（２９）記載の装置。
（３１）関連フラグ値が偽と予測される場合、述語命令の実行を抑制する手段を含む、前記（３０）記載の装置。
（３２）予測フラグ値が正しいか否かを判断する手段と、
予測フラグ値が正しくない場合、予測フラグ値を更新し、予測フラグ値に関連付けられる命令から実行を再スタートする手段と
を含む、前記（３０）記載の装置。
（３３）予測フラグ値が正しい場合、システムのプログラム順序状態を更新する手段を含む、前記（３２）記載の装置。
（３４）たとえ述語命令の関連フラグ値が使用不能であっても、前記実行手段が述語命令を実行する、前記（２９）記載の装置。
（３５）未解決の述語の結果に対して、レジスタ名または値のいずれか一方のリストを記憶する手段と、
複数の名前または複数の値のいずれか一方が入手可能なレジスタを使用する述語命令を識別する手段と、
所与の識別された命令に対して、複数の名前または複数の値のいずれか一方の１つだけを選択する手段と、
所与の識別された命令に対応する述語の解析に際して、選択が正しいか否かを判断する手段と、
選択が正しくない場合、所与の命令に続くオペレーションの実行を変更する手段と
を含む、前記（３４）記載の装置。
【図面の簡単な説明】
【図１】従来技術に従う述語実行及び実行抑制を有する述語予測アーキテクチャを示す図である。
【図２】従来技術に従う述語実行及びライトバック抑制を有する述語予測アーキテクチャを示す図である。
【図３】本発明に従う命令の再順序付けをサポートするスーパスカラ・プロセッサ及びハードウェア資源を含む、コンピュータ処理システムを示す図である。
【図４】本発明の実施例に従い、述語命令を実行するスーパスカラ・プロセッサ及びハードウェア資源を含むコンピュータ処理システムを示す図である。
【図５】本発明の実施例に従う述語予測により、非プログラム順序のスーパスカラ実行を実行するシステムを示す図である。
【図６】本発明の実施例に従い、述語予測を用いて述語命令を実行する方法を示すフローチャートである。
【図７】本発明の実施例に従い、実行抑制を用いて、非プログラム順序のスーパスカラ実行を実行し、未解決の述語のために述語予測を使用するシステムを示す図である。
【図８】本発明の実施例に従い、ライトバック抑制を用いて、非プログラム順序のスーパスカラ実行を実行し、未解決の述語のために述語予測を使用するシステムを示す図である。
【図９】本発明の実施例に従い、述語予測精度を改善するシステムを示す図である。
【図１０】本発明の実施例に従い、コンピュータ処理システムにおいて、データ依存性を予測する装置を示す図である。
【図１１】本発明の実施例に従い、退去される命令の体系化ソース・レジスタ名から、フューチャ・レジスタ名の予測を検証する方法を示すフローチャートである。
【符号の説明】
３００、４００、７００、１０００  システム
３０５  メモリ・サブシステム
３１０  命令キャッシュ
３１５  データ・キャッシュ
３２０、４２５、５２５、７２０、１０２０  プロセッサ・ユニット
３２５  命令バッファ
３３０  命令リネーム及びディスパッチ・ユニット
３３５  フューチャ汎用レジスタ・ファイル
３４０  分岐ユニット（ＢＵ）
３４５  機能ユニット（ＦＵ）
３５０  メモリ・ユニット（ＭＵ）
３５５  退去キュー
３６０  体系化プログラム順序汎用レジスタ・ファイル（体系化レジスタ・ファイル）
３６５  プログラム・カウンタ（ＰＣ）
４０５  フューチャ述語レジスタ・ファイル
４１０  体系化プログラム順序述語レジスタ・ファイル（体系化述語レジスタ・ファイル）
５０５  予測器
５１０  予測述語レジスタ・ファイル
５１５  制御論理
５２０  予測検証論理
７０５、１００５  述語バイパス手段
７１０  命令実行ユニット
１２０５  命令スヌープ論理
１２１０  述語予測エンハンスメント論理
１４００  装置
１４０５  リネーム論理
１４１０  体系化−フューチャ・レジスタ名変換マップ
【図１】
0003565499.tif 000011
【図２】
0003565499.tif 000012
【図３】
0003565499.tif 000013
【図４】
0003565499.tif 000014
【図５】
0003565499.tif 000015
【図６】
0003565499.tif 000016
【図７】
0003565499.tif 000017
【図８】
0003565499.tif 000018
【図９】
0003565499.tif 000019
【図１０】
0003565499.tif 000020
【図１１】
0003565499.tif 000021