(57)【特許請求の範囲】
【請求項１】
プログラムの命令を実行するための実行パイプラインであって、それらの命令のうちの少なくとも一部が推論実行される実行パイプラインを具備し、
前記実行パイプラインの外部に設けられ、推論実行される少くとも一部の命令と、それらの命令の実行結果とを少なくとも含むトレース・バッファを具備し、
前記トレース・バッファに保持された命令中の、推論エラーに関係している少くとも一部は、プログラムの実行の一部として前記トレース・バッファから前記実行パイプライン内で再実施される、
ことを特徴とするプロセッサ。
【請求項２】
請求項１記載のプロセッサにおいて、前記少なくとも一部の命令は、前記実行パイプライン内での実行後に前記実行パイプラインからリタイヤされるが、正しく実行されるまでは前記トレース・バッファ内に存続する、ことを特徴とするプロセッサ。
【請求項３】
命令を実行するための実行パイプラインであって、それらの命令のうちの少なくとも一部が推論実行される実行パイプラインを具備し、
前記実行パイプラインの外部に設けられ、推論実行される少くとも一部の命令と、それらの命令の実行結果とを少なくとも含むトレース・バッファを具備し、
前記少なくとも一部の命令は、前記実行パイプライン内での実行後に前記実行パイプラインからリタイヤされるが、正しいソース・オペランドで実行されるまで前記トレース・バッファ内に存続する、
ことを特徴とするプロセッサ。
【請求項４】
異なるスレッドの少くとも一部を同時に実行する実行パイプラインを具備し、
各スレッドの命令をそれぞれ保持するトレース・バッファであって、前記実行パイブラインの外部に設けられたトレース・バッファを具備し、
前記トレース・バッファのそれぞれが、関係する１つのスレッドのレジスタ・コンテキストを保持する出力レジスタ・ファイルを有し、且つ、プログラム順序で直前のスレッドのレジスタ・コンテキストを受ける入力レジスタ・ファイルを有する、
ことを特徴とするプロセッサ。
【請求項５】
請求項４記載のプロセッサにおいて、前記トレース・バッファは、出力レジスタ・ファイルの内容を、対応する入力レジスタ・ファイルの内容と比較する比較器を有している、ことを特徴とするプロセッサ。
【発明の詳細な説明】
【０００２】
（発明の背景）
発明の技術分野：本発明は、プロセッサに関し、より詳細には、１つまたは複数のトレース・バッファを有するプロセッサに関する。
【０００３】
背景技術：マイクロプロセッサなど、現行のスーパスカラ・プロセッサは、パフォーマンスを強化するために分岐予測および不適正順序実行（out of order execution）などの技法を実行する。不適正順序実行パイプラインを有するプロセッサは、所与の命令がフェッチされデコードされた順序とは異なる順序でその命令を実行する。命令は、それに関する依存関係が存在しない命令に対して不適正順序で実行することができる。不適正順序実行では、単にプログラム命令順序のために実行ユニットがアイドル状態にならないようにすることにより、プロセッサのパフォーマンスが向上する。命令結果は、実行後にリオーダされる。
【０００４】
データの依存関係を処理する作業は、命令でコードを適正順序であることに制限することによって簡略化される。その場合、プロセッサは、データがレジスタによりある命令から後続命令にどのように流れるかを識別することができる。プログラムの正確さを保証するため、レジスタはリネームされ、命令はその入力オペランドが生成されるまで予約ステーションで待機し、生成された時点で実行のために適切な機能ユニットに発行される。レジスタ・リネーマ、予約ステーション、および関連機構は、従属命令が依存している命令より先に実行されないように、依存関係を有する複数の命令をまとめてリンクする。したがって、このようなプロセッサは、適正順序のフェッチおよびデコードによって制限される。
【０００５】
命令キャッシュからの命令がミスするかまたは分岐予測が間違っている場合、プロセッサは、より高レベルのキャッシュまたはメモリから命令ブロックがフェッチされるまで、または予測が間違っている分岐が解決されるまで、待機しなければならず、間違った経路の実行はリセットされる。このような挙動の結果として、命令キャッシュのミスおよび予測が間違っている分岐の前後の独立命令は並列実行することができないが、そのようにすることは正しいことである可能性がある。
【０００６】
様々な推論は推論エラーに至る可能性がある。プロセッサが推論エラーから回復できるようにする改良された機構をプロセッサ内に設ける必要がある。
【０００７】
（発明の概要）
本発明の一実施態様では、プロセッサは命令を実行するための実行パイプラインを含み、その命令のうちの少なくとも一部が推論実行される。また、プロセッサは命令を保持するために実行パイプラインの外部にあるトレース・バッファも含み、推論エラーに関連する命令がトレース・バッファから実行パイプライン内で再実施される。
【０００８】
他の実施態様では、プロセッサは命令を実行するための実行パイプラインを含み、その命令のうちの少なくとも一部が推論実行される。また、プロセッサは命令と命令の実行結果を保持するために実行パイプラインの外部にあるトレース・バッファも含み、その命令のうちの少なくとも一部はパイプライン内での実行後に初期リタイヤされるが、最終リタイヤまでトレース・バッファ内に存続する。
【０００９】
本発明は、以下に示す詳細な説明ならびに本発明の実施形態の添付図面によりより完全に理解されるだろうが、添付図面は、記載した特定の実施形態に本発明を限定するものと解釈すべきではなく、説明および理解のみを目的とするものである。
【００１０】
（好ましい実施形態の詳細な説明）
Ａ．スレッドの作成およびパイプライン１０８の概要
Ｂ．トレース・バッファ１１４に関する詳細
１．トレース・バッファ１１４Ａ
ａ．命令待ち行列アレイ２０２Ａ
ｂ．ＤＡＤアレイ２０６Ａおよび依存関係生成回路２１２Ａ
ｃ．出力レジスタ・ファイル２１０Ａと入力レジスタ・ファイル２０８Ａ
２．トレース・バッファ１１４’
Ｃ．再実施シーケンス・アルゴリズム
Ｄ．第２レベルまたは最終リタイヤ
Ｅ．メモリ・システム
１．ストア・バッファおよびロード・バッファ
２．ロード・アドレスとストア・アドレスの比較
ａ．ロード命令の実行
ｂ．ストア命令の実行
ｃ．リセット
３．ストア命令の再実施
４．複数ロード命令の再実施
５．ロード命令とストア命令の最終リタイヤ
Ｆ．スレッド管理ロジックおよび最終リタイヤ・ロジックに関する追加情報
Ｇ．マルチスレッド化を含まない実施形態
Ｈ．追加情報および実施形態
【００１１】
図１は、プロセッサ１０の所与の構成要素を示している。プロセッサ１０は、実行パイプライン１２と、実行パイプライン１２の外部にあるトレース・バッファ１４とを含む。実行パイプライン１２は、メモリ・オーダ・バッファを含む場合もある。導体１８上の命令は、実行のために実行パイプライン１２に供給される。また、命令は、導体２２を介してトレース・バッファ１４にも供給される。命令は、実行パイプライン１２内で推論実行することができる。推論の例としては、データ推論および依存関係推論を含む。多種多様の推論のいずれも含むことができる。プロセッサ１０は、推論エラー（誤推論）を検出し、それから回復するための機構をトレース・バッファ１４に含む。
【００１２】
誤推論が検出されると、誤推論された命令は、トレース・バッファ１４から導体２４を介して実行パイプライン１２に供給され、実行パイプライン１２内で再実施される。命令が「再実施」される場合、その命令とその命令に依存するすべての命令は再実行されるが、必ずしも同時に行われるわけではない。命令が「完全再実施」される場合、その命令とプログラム順序でその命令に続くすべての命令が再実行される。プログラム順序とは、複数の命令が適正順序プロセッサ内で実行されると思われる順序である。命令は、完全にプログラム順序でまたはプログラム順序以外の何らかの順序で導体１８を通過することができる。プロセッサ１０は、適正順序プロセッサである場合もあれば、不適正順序プロセッサである場合もある。従属命令の再実行の結果、従属命令に依存する命令が再実施される場合もある。命令の再実行の回数は、再実施をトリガする事象を制御することによって制御することができる。一般に、実行という用語は、最初の実行と、再実行を含むことができる。命令の少なくとも一部の結果は、導体２６を介してトレース・バッファに供給される。最終リタイヤ・ロジック３４は、命令が初めからまたは再実行時に正しく実行されたことが保証された後で、トレース・バッファ１４内の命令を最終的にリタイヤする。
【００１３】
実行パイプライン１２は、多種多様の実行パイプラインのいずれでもよく、より大きいパイプラインの一セクションにすることもできる。実行パイプライン１２は、多種多様のプロセッサとともに使用することができる。図２と図３に例を示すが、図２は実行パイプライン１０８を有するプロセッサ５０の構成要素を示し、図３は実行パイプライン３０８を有するプロセッサ１０８を示している。図２の本発明の実施形態の実行パイプライン１０８はレジスタ・リネームを含む。他の実施形態の実行パイプラインはレジスタ・リネームを含まない。プロセッサは、（図２のプロセッサ５０の場合のように）複数のスレッドを同時に処理する場合もあれば、（図３のプロセッサ１００の場合のように）複数のスレッドを同時に処理しない場合もある。プロセッサ５０について、まず説明する。
【００１４】
本明細書において「一実施の形態」または「一実施形態」に言及する場合、その実施形態に関して記載した特定の特徴、構造、または特性が本発明の少なくとも１つの実施形態に含まれることを意味する。本明細書の様々な箇所に「一実施形態では」という句が現れても、必ずしもすべて同じ実施形態について言及しているわけではない。
【００１５】
Ａ．スレッドの作成およびパイプライン１０８の概要
命令は、導体１０２を介して命令キャッシュ（Ｉキャッシュ）１０４に供給される。デコーダ１０６は、Ｉキャッシュ１０４から命令を受け取るものとして示されているが、命令がＩキャッシュ１０４に到達する前にその命令をデコードすることもできる。選択したコンテキストおよび実施によっては、「命令」という用語は、マクロ演算（マクロｏｐ）、マイクロ演算（μｏｐ）、またはその他の形式の命令を含むことができる。縮小命令セット・コンピューティング（ＲＩＳＣ）命令または複雑命令セット・コンピューティング（ＣＩＳＣ）命令を含むがこれに限定されない様々な命令セットのいずれでも使用することができる。さらに、デコーダ１０６は、ＣＩＳＣ命令をＲＩＳＣ命令にデコードすることができる。Ｉキャッシュ１０４からの命令は、ＭＵＸ１１０を介してパイプライン１０８に供給され、かつ、導体１１８を介してトレース・バッファ１１４に供給される。
【００１６】
トレースとは１組の命令セットである。スレッドは、そのトレースと、レジスタ値およびプログラム・カウンタ値などの関連信号とを含む。
【００１７】
スレッド管理ロジック１２４は、導体１３０を介してプログラム・カウンタ１１２Ａ、１１２Ｂ、・・・、１１２Ｘに開始計数値を供給することにより（Ｘはプログラム・カウンタの数を表す）、Ｉキャッシュ１０４内のプログラムまたはプロセスから様々なスレッドを作成する。一例として、Ｘは４またはそれ以上あるいはそれ以下にすることができる。スレッド管理ロジック１２４は、関連のプログラム・カウンタを停止することにより、スレッドを終了する。その後、スレッド管理ロジック１２４は、プログラム・カウンタに他のスレッドを開始させることもできる。様々なスレッドの一部分はＩキャッシュ１０４から同時に読み取られる。
【００１８】
プログラムまたはプロセス内のどこでスレッドを作成すべきかを判定するために、スレッド管理ロジック１２４は、導体１２８を介してデコーダ１０６から命令を読み取ることができる。スレッドは、プログラマまたはコンパイラによって挿入され、スレッドの開始および終了を明示的に決定する命令を含むことができる。あるいは、スレッド管理ロジック１２４は、プログラムまたはプロセスの命令を分析し、Ｉキャッシュ１０４に供給されたプログラムまたはプロセスを様々なスレッドに分解することができる。たとえば、分岐、ループ、逆方向分岐、復帰、ジャンプ、手続き呼出し、関数呼出しは、スレッドを分離するために適当なポイントである場合もある。スレッド管理ロジック１２４は、潜在的なスレッドの長さ、含まれる変数の数、連続するスレッド間に共通する変数の数、ならびにどこでスレッドを開始するかを考慮する際のその他の要因を考慮することができる。スレッド管理ロジック１２４は、スレッドの境界を決定する際にプログラム順序を考慮することができる。プログラム順序とは、スレッドとスレッド内の命令が適正順序プロセッサ上で実行されると思われる順序である。スレッド内の命令は、（プログラム順序とは反対の）不適正順序で実行することができる。スレッドは、本質的には、パイプライン１０８によって独立して処理することができる。スレッド管理ロジック１２４は、最適とは言えない選択を回避するために履歴テーブルを含む予測機構を含むことができる。たとえば、スレッド管理ロジック１２４は、スレッドを作成し、次に、そのスレッドが実際にはプログラム順序の一部ではなかったと後で判定する場合がある。その場合同じコードがもう一度検出された場合、予測機構を使用して、同じスレッドをもう一度作成すべきかどうかを判定することができるだろう。スレッド管理ロジック１２４は、スレッドの動的作成と、コンパイラまたはプログラマからの明示的な命令ヒントの使用との組合せを使用して、命令内のどこでスレッドを作成すべきかを判定することができる。
【００１９】
スレッドを動的に作成することは、マルチスレッド化のために特に作成またはコンパイルされたわけではないプログラムからスレッドを作成することであり、スレッドの少なくとも１つは他のスレッドに依存する。プログラムは、実行パイプライン１０８およびスレッド管理ロジック１２４を含むチップから離れて作成することができる。スレッドを動的に作成し、スレッドを実行し、実行時に推論エラーを検出して訂正することを、動的マルチスレッド化と呼ぶ。
【００２０】
図４は、条件付き分岐命令を含むスレッドＴ１を示している。プログラム順序では、スレッドＴ２は条件付き分岐命令の次に実行される。時間順序では、スレッドＴ２は、スレッドＴ１が最初に条件付き分岐命令に到達した時点から推論実行される。したがって、スレッドＴ１およびＴ２の一部分は同時に実行される。スレッドＴ２が誤推論を含む場合、スレッドＴ２の実施済み命令が再実施される。
【００２１】
スレッド管理ロジック１２４は、導体１３０を介してプログラム・カウンタの計数値をモニタすることができる。計数値をモニタする目的は、スレッドがいつ終了すべきかを判定することである。たとえば、条件付き分岐の条件が満たされないときに、スレッドＴ１のプログラム・カウンタが続行可能になっている場合、それはスレッドＴ２の第１の命令まで進むことになるだろう。したがって、スレッド管理ロジック１２４は、条件が満たされないときにスレッドＴ１のプログラム・カウンタを停止する。
【００２２】
図５は、関数呼出し命令を含むスレッドＴ１を示している。プログラム順序では、呼出し命令に到達したときに、プログラム・カウンタはその関数の位置までジャンプして復帰命令まで実行し、復帰命令の時点でプログラム・カウンタは呼出し後の命令に復帰する。プログラム順序では、スレッドＴ２は復帰後の命令から始まる。時間順序では、スレッドＴ２は、スレッドＴ１が最初に呼出しに到達した時点から推論実行される。スレッドＴ２が誤推論を含む場合、スレッドＴ２の実施済み命令が再実施される。スレッドＴ１は、そのプログラム・カウンタがスレッドＴ２の第１の命令に到達したときに終了する。図５のロードＭＸ命令およびストアＭＸ命令について以下に説明する。
【００２３】
図６は、あるプログラムの一セクションの一部であるスレッドＴ１、Ｔ２、Ｔ３、Ｔ４を示している。様々なプログラム・カウンタがスレッドＴ１、Ｔ２、Ｔ３、Ｔ４を生成する。スレッドＴ１は、ポイントＡ（関数呼出し命令）までの命令を含み、次にポイントＢからポイントＣ（条件付き逆方向分岐命令）、ポイントＤまで、さらにもう一度ポイントＣまでの命令を含む（このループは数回繰り返すことができる）。スレッドＴ２は、プログラム順序でポイントＡで呼び出された関数の復帰命令の直後にある命令から始まる。スレッドＴ３は、プログラム順序でポイントＣの条件付き逆方向分岐の直後にある命令から始まり、ポイントＥ、ポイントＦ、ポイントＧ、ポイントＨ、さらにポイントＩまで継続し、ポイントＩはスレッドＴ２が始まるポイントＡの直後の命令への復帰命令である。素レットＴ４は、プログラム順序でポイントＥの条件付き逆方向分岐の直後にある命令から始まる。
【００２４】
図７に示すように、スレッドＴ１、Ｔ２、Ｔ３、Ｔ４の一部分は同時にフェッチされ、デコードされ、実行される。プログラム順序に従わないので、これらのスレッドは不適正順序でフェッチされ、デコードされ、実行される。時間順序では、スレッドＴ２、Ｔ３、Ｔ４の実行はポイントＡ、Ｃ、Ｅの命令の直後にそれぞれ始まる。垂直破線は親子関係を示している。スレッドＴ２、Ｔ３、Ｔ４は、レジスタまたはメモリ位置にあるデータが正確であることが確実になる前にそのデータを頼りにすることにより、推論実行される。プロセッサ１００は、誤推論を検出し、誤推論した命令を再実施させるための機構を有する。スレッドＴ４がプログラム順序の一部ではないことが判明する。スレッドＴ４は、スレッドＴ４がプログラム順序の一部ではないことをスレッド管理ロジック１２４が判定するまで実行することができる。その時点でスレッドＴ４はリセットすることができ、プロセッサ１００内のスレッドＴ４を保持または処理する資源は、割振り解除し、次に他のスレッドのために割り振ることができる。プログラム順序では、スレッドＴ１、Ｔ２、Ｔ３は、まずスレッドＴ１、次にスレッドＴ３、次にスレッドＴ２という順序で実行されることになる。
【００２５】
図２を参照すると、ＭＵＸ  １１０からの命令はリネーム／割振りユニット１５０によって受け取られ、そのユニットはレジスタ・ファイル１５２内のリネームした物理レジスタの物理レジスタ識別子（ＰＲＩＤ）を供給する。このＰＲＩＤはバイパス導体１２６を介してトレース・バッファ１１４に供給される。割振りは、命令にレジスタを割り当てることと、スケジュール／発行ユニット１５６の予約ステーションの項目を割り当てることを含む。予約ステーション内の特定の命令のためにオペランドの準備ができると、実行ユニット１５８のうちの１つの実行ユニット（たとえば、整数、浮動小数点）またはアドレス生成ユニット（ＡＧＵ）１７２と、メモリ・オーダ・バッファ（ＭＯＢ）１７８と、データ・キャッシュ１７６とを含むメモリ実行パイプラインにその命令が発行される。命令によっては、オペランドは導体１６８を介してレジスタ・ファイル１５２から供給される場合もある。本発明の一実施形態では、１つのスレッド内の従属命令は、不適正順序で実行されないようにリンクすることができる。しかし、様々なスレッドからの従属命令は、同時にフェッチし、デコードし、不適正順序で実行することができる。所与のスレッドの実行は推論実行にすることができる。
【００２６】
高いパフォーマンスのため、予約ステーションおよび関連機構は、低待ち時間と高帯域幅命令発行の両方を有するように設計されている。この待ち時間と帯域幅の要件は、予約ステーション内で待機できる命令の数に制限を加えるものである。トレース・バッファ１１４をパイプライン１０８の外部に位置決めすることにより、パイプライン１０８のスループットを大幅に低下させることなく、多数の命令を実行／再実施に使用イネーブルにすることができる。実行パイプライン１０８とトレース・バッファ１１４との間の待ち時間の影響はパイプライン化により低減することができる。
【００２７】
実行の結果と関連情報は、ライトバック・ユニット１６２から導体１２２（レジスタの場合）を介し、さらにＭＵＸ  １９２と導体１９６を介してトレース・バッファ１１４に書き込まれる。この結果と関連情報は、レジスタ・ファイル１５２と関連リオーダ・バッファ（ＲＯＢ）１６４に書き込むこともできる。ある命令の結果と情報がレジスタ・ファイル１５２およびＲＯＢ１６４に書き込まれると、その命令は、パイプライン１０８に関する限り、適正順序でリタイヤされる。このリタイヤは第１レベルまたは初期リタイヤと呼ばれる。第１レベル・リタイヤ時またはその前に、予約ステーション、レジスタ・ファイル１５２、ＲＯＢ１６４を含む、スケジュール／発行ユニット１５６内のリタイヤした命令用の資源の割振りが解除される。しかし、その命令に関して必要なすべての詳細は、後述する最終的なリタイヤまでトレース・バッファ１１４およびＭＯＢ１７８内に維持される。
【００２８】
プログラム順序で後のスレッドで使用するデータが前のスレッドで生成される場合、後のスレッドと前のスレッドとの間に依存関係が存在する。このデータは、メモリ命令または非メモリ命令によって前のスレッドで生成された可能性がある。たとえば、後のスレッド内のロード命令が前のスレッド内のストア命令と同じアドレスを有する場合、後のスレッドは前のスレッドに依存する可能性がある。また、後のスレッド内のある命令が前のスレッドで変更されたレジスタを必要とする場合も、後のスレッドは前のスレッドに依存する可能性がある。同様に、プログラム順序で後の命令が前の命令によって生成されたデータを使用する場合、後の命令は前の命令に依存する。「依存関係」という用語は「依存関係推論」という句でも使用する。依存関係推論の一例は、ロード命令と前のストア命令との間に依存関係がまったくないと推論することである。アドレスの突合せは、依存関係推論エラーをチェックするための技法の一例である。データ推論の一例は、レジスタ内のデータが正しいデータであると推論することである。レジスタの突合せは、データ推論エラーをチェックするための技法の一例である。
【００２９】
Ｂ．トレース・バッファ１１４に関する詳細
図８を参照すると、トレース・バッファ１１４はトレース・バッファ１１４Ａ、１１４Ｂ、１１４Ｃ、・・・、１１４Ｙを含む。Ｙはトレース・バッファの数を表す。たとえば、Ｙ＝４（すなわち、Ｙ＝Ｄ）である場合、４つのトレース・バッファが存在する。Ｙが３未満である場合、トレース・バッファ１１４は図８に示すトレース・バッファをすべて含むわけではなくなる。ＹはＸ（プログラム・カウンタの数）と同じかまたはＸとは異なるものにすることができる。トレース・バッファ１１４は、個別トレース・バッファに分割された単一メモリにするか、物理的に別々のトレース・バッファにするか、あるいは両者の組合せにすることができる。
【００３０】
図９を参照すると、一実施形態では、スレッド管理ロジック１２４は、スレッドＩＤのプログラム順序（リタイヤ順序でもある）を指定するアレイ１９８を含む。この例では、各トレース・バッファは固有のスレッドＩＤを有するかまたはスレッドＩＤに対する１対１のマッピングを有する。たとえば、トレース・バッファ１１４ＡにはスレッドＩＤ１が割り当てられ、トレース・バッファ１１４ＢにはスレッドＩＤ２割り当てられ、以下同様である。スレッドＩＤはハードワイヤードにするかまたはプログラミングすることができる。一実施形態では、各プログラム・カウンタは特定のスレッドＩＤおよびトレース・バッファに関連付けられる。（あるいは、このような制限された関係が存在しない。）
【００３１】
図９は、時点ｔ１と時点ｔ２におけるスレッドのリタイヤ順序の一例を示している。この例では、４つのトレース・バッファと４つのスレッドＩＤのみが存在する。関連スレッド番号は括弧内に示す。実施によっては、括弧内のスレッド番号は実際にはアレイ１９８に含まれなくなる。時点ｔ１では、図６の例のように、プログラムおよびリタイヤ順序はスレッドＴ１、Ｔ３、Ｔ２、Ｔ４になる。時点ｔ１と時点ｔ２との間には、スレッドＴ４がプログラム順序内にないことが判定される。したがって、スレッドＴ４はリセットされ、トレース・バッファ１１４Ｄ内にスレッドＴ５（図５には図示せず）のためのスペースができる。スレッドＴ５はスレッドＩＤ４に関連付けられる。スレッドＴ１はリタイヤし、トレース・バッファ１１４Ａ内にスレッドＴ６のためのスペースができる。スレッドＴ６はスレッドＩＤ１に関連付けられる。時点ｔ２では、プログラムおよびリタイヤ順序はＴ３、Ｔ２、Ｔ５、Ｔ６になる。（スレッドＴ４がリセットされる前にスレッドＴ１がリタイヤした場合、スレッドＴ５およびＴ６は異なるスレッドＩＤを有することになるが、プログラムおよびリタイヤ順序は変わらないだろう。）使用するアルゴリズムによっては、スレッドＴ２は最初はアレイ１９８内のスレッドＴ３より前にあった可能性があるが、プログラムおよびリタイヤ順序は時点ｔ１におけるアレイ１９８のように訂正されることになるだろう。
【００３２】
前述のように、スレッドのプログラム順序は、スレッドが適正順序プロセッサで実行されると思われる順序である。また、命令のプログラム順序は、命令が適正順序プロセッサで実行されると思われる順序である。スレッド管理ロジック１２４は必ずしも最初にそのスレッド用の真のプログラム順序を決定するわけではない。しかし、スレッド管理ロジック１２４は結局、真のプログラム順序を決定する。
【００３３】
図８を参照すると、トレース・バッファ１１４Ａ、１１４Ｂ、・・・、１１４Ｙは、導体１１８に接続された導体１１８Ａ、１１８Ｂ、・・・、１１８Ｙを介して命令を受け取る。導体１１８Ａ、１１８Ｂ、・・・、１１８Ｙの間にはデマルチプレクシング回路が存在する場合もある。あるいは、どのトレース・バッファが活動化されるかをイネーブル信号によって制御することもできる。さらに、並列トランザクションを処理するために十分な並列導体が存在する場合もある。トレース・バッファ１１４Ａ、１１４Ｂ、・・・、１１４Ｙは、導体１２０に接続された導体１２０Ａ、１２０Ｂ、・・・、１２０Ｙを介してパイプライン１０８に対して再実施のために命令および関連情報を供給する。ただし、トレース・バッファ１１４からの複数の命令が再実行のために導体１２０およびＭＵＸ  １１０を同時に通過する場合もあることに留意されたい。同時に、デコーダ１０６からの複数の命令も初めてＭＵＸ  １１０を通過することができる。スレッドＩＤおよび命令ＩＤ（ｉｎｓｔｒＩＤ）はパイプラインにより各命令に付随する。また、再実施計数値もその命令に付随する場合がある。ロード命令およびストア命令の場合、ロード・バッファＩＤ（ＬＢＩＤ）とストア・バッファＩＤ（ＳＢＩＤ）もその命令に付随する場合がある。一実施形態では、ＬＢＩＤとＳＢＩＤがどの命令にも付随するが、ロードまたはストアではない命令の場合、ＬＢＩＤ値とＳＢＩＤ値は無意味なものになる可能性がある。以下に説明するように、ＰＲＩＤまたは値が再実行中の命令に付随する場合もある。
【００３４】
トレース・バッファ１１４Ａ、１１４Ｂ、・・・、１１４Ｙは、導体１２６に接続されたバイパス導体１２６Ａ、１２６Ｂ、・・・、１２６Ｙを介してリネーム／割振りユニット１５０からＰＲＩＤ値、ＬＢＩＤ値、ＳＢＩＤ値を受け取る。また、トレース・バッファ１１４Ａ、１１４Ｂ、・・・、１１４Ｙは、導体１２２に接続された導体１２２Ａ、１２２Ｂ、・・・、１２２Ｙと、導体１９６に接続された導体１９６Ａ、１９６Ｂ、・・・、１９６Ｙを介してライトバック結果情報と関連信号を受け取る。再実施信号は、導体１９４に接続された導体１９４Ａ、１９４Ｂ、・・・、１９４Ｙを介して供給される。導体１２０、１２６、１２２、１９４、１９６では、多重化またはイネーブル回路あるいは相当な数の並列導体を使用することができる。トレース・バッファは同一またはいくらか異なるものにすることができる。
【００３５】
図１０のトレース・バッファ１１４Ａは、トレース・バッファの第１の実施形態を示している。図１１のトレース・バッファ１１４Ａ’は、トレース・バッファの第２の実施形態を示している。トレース・バッファの他の実施形態は、トレース・バッファ１１４Ａおよび１１４Ａ’の変形形態あるいはまったく異なるアーキテクチャを含むことができるだろう。
【００３６】
１．トレース・バッファ１１４Ａ
図１０を参照すると、トレース・バッファ１１４Ａは、命令待ち行列アレイ２０２Ａと、データ及び依存関係（ＤＡＤ）アレイ２０６Ａと、入力レジスタ・ファイル２０８Ａと、出力レジスタ・ファイル２１０Ａと、依存関係生成回路２１２Ａと、制御回路２２４Ａとを含む。「アレイ」という用語は、特定の形式に制限せず、広い意味で複数方向の情報を含むためのものである。
【００３７】
ａ．命令待ち行列アレイ２０２Ａ
図１２に関連して、本発明の一実施形態による命令待ち行列アレイ２０２Ａの構造と、それと他の構成要素との対話について、以下に説明する。命令待ち行列アレイ２０２Ａは、特定のスレッドの一部であるＩキャッシュ１０４からフェッチされた命令を受け取る。１つのスレッド内の命令は、適正順序でフェッチされ、命令待ち行列アレイ２０２Ａに書き込まれる。他のスレッドの一部である命令は、異なるトレース・バッファの命令待ち行列内に書き込まれるか、または異なる時点で命令待ち行列アレイ２０２Ａによって書き込まれる。命令待ち行列アレイ２０２Ａは、各命令識別子（ｉｎｓｔｒＩＤ）に関する様々な情報フィールドを含む。様々な実施形態は、いくらか異なるフィールドと、異なる数の行を含むことができるだろう。命令待ち行列アレイ２０２Ａのこの実施形態では、プログラム・カウンタ値は考慮されないが、他の実施形態では考慮される可能性がある。命令待ち行列アレイ２０２Ａと添付図面に示す他のすべての構成要素は、図示していない様々なフィールド、信号、および構造を含むことができる。このようなフィールド、信号、構造は図示していない。というのは、これらは実施に応じて変化するものであり、当業者によって理解されており、本明細書を非常に複雑にし、本発明を不明確にする傾向があるからである。
【００３８】
命令は、（たとえば、そのスレッドがプログラムの適正順序実行の一部ではないと判定されたという理由で）最終的にリタイヤまたは廃棄されるまで、トレース・バッファ１１４Ａ内で待機する。まだ実行されていない命令が依然としてトレース内に存在する間に命令待ち行列アレイ２０２Ａがいっぱいになった場合、１つの命令が最終的に命令待ち行列アレイ２０２Ａからリタイヤされ、１つの行の割振りが解除されるまで、トレース内の命令はトレース・バッファ１１４またはリネーム／割振りユニット１５０によって受け取られない。システム１００内の様々なアレイの項目は、先頭ポインタおよび末尾ポインタの移動によって割振りおよび割振り解除を行うことができる。
【００３９】
以下のコード行に関連して、命令待ち行列アレイ２０２Ａについて説明する。
Ｉ０：ｍｕｌ  Ｒ１，Ｒ２→Ｒ１
Ｉ１：ｍｕｌ  Ｒ３，Ｒ４→Ｒ２
Ｉ２：ａｄｄ  Ｒ１，Ｒ２→Ｒ１
Ｉ３：ａｄｄ  １０，Ｒ１→Ｒ４
Ｉ４：ｓｔｏｒｅ    Ｒ２→Ｍｘ
Ｉ５：ｓｔｏｒｅ    Ｒ１→Ｍｙ
これらは、１つのスレッド内の最初の６つの命令である。トレース・バッファ１１４Ａ以外のトレース・バッファはプログラム順序でトレース・バッファ１１４Ａより前にあることは明らかになるだろう。
【００４０】
「命令コード」フィールドは、特定の命令に関連する命令コードを含む。「宛先」、「ソース１」、「ソース２」の各フィールドは、命令の宛先、ソース１、ソース２を識別する。「ソース１のインデックス」は、そのソースを含むトレース・バッファ１１４Ａ内の命令項目を識別する。たとえば、ｉｎｓｔｒＩＤ０の宛先はｉｎｓｔｒＩＤ２のソース１に使用される。したがって、ｉｎｓｔｒＩＤ２の「ソース１のインデックス」フィールドには０が入る。ｉｎｓｔｒＩＤ２の宛先はｉｎｓｔｒＩＤ３のソース２に使用される。したがって、ｉｎｓｔｒＩＤ３の「ソース２のインデックス」フィールドには２が入る。×は指定なしを意味する。
【００４１】
「有効１」と「有効２」のフィールドは、トレース・バッファ１１４Ａ内のスレッドの外部からの命令によってあるｉｎｓｔｒＩＤの対応するソース・オペランドが事前に生成されたときに第１の値（たとえば、論理０）にセットされ、そのスレッド内の命令によってあるｉｎｓｔｒＩＤのソース・オペランドが事前に生成されたときに第２の値（たとえば、論理１）にセットされるビットである。ｉｎｓｔｒＩＤ０のソース１（Ｒ１）は、命令待ち行列アレイ２０２Ａ内のトレースの外部で生成される。したがって、ｉｎｓｔｒＩＤ０の有効１は論理０になる。ｉｎｓｔｒＩＤ３のソース２はｉｎｓｔｒＩＤ２の宛先から得られる。したがって、ｉｎｓｔｒＩＤ３の有効２は論理１になる。
【００４２】
命令Ｉ３は、定数「１０」にＲ１を加算することを含む。この定数は、命令とともに、特殊レジスタ（図示せず）に、ソース１フィールドに、または他の何らかの機構により格納することができる。図１２では、ｉｎｓｔｒＩＤ３のソース１フィールドに×（指定なし）が示されている。あるいは、ソース１フィールドに何らかのインジケータを入れることができるだろう。
【００４３】
ストア・バッファＩＤ（ＳＢＩＤ）フィールドは、後述するストア・バッファ内のストア命令に関連するＳＢＩＤを保持する。ロード・バッファ（ＬＢＩＤ）フィールドは、後述するロード・バッファ内のロード命令に関連するＬＢＩＤ項目を保持する。ＳＢＩＤ値とＬＢＩＤ値は、リネーム／割振りユニット１５０によって割り当てられ、バイパス導体１２６を介して命令待ち行列アレイに書き込まれる。スレッドＩＤ番号フィールドは命令待ち行列アレイ２０２Ａに含めることができるだろうが、暗黙のものなのでその必要はない。
【００４４】
ｂ．ＤＡＤアレイ２０６Ａおよび依存関係生成回路２１２Ａ
図１３を参照すると、ＤＡＤアレイ２０６Ａの一実施形態は、１対１方式で命令待ち行列アレイ２０２ＡのｉｎｓｔｒＩＤ項目に対応する「ｉｎｓｔｒＩＤ」項目（行）を含む。実際に、命令待ち行列アレイ２０２ＡとＤＡＤアレイ２０６Ａは同じアレイの異なる部分にすることもできるだろう。しかし、一部の実施形態では、命令待ち行列アレイ２０２ＡとＤＡＤアレイ２０６Ａに関連する別々の読取りポートが存在する。
【００４５】
ＤＡＤアレイ２０６Ａは、命令によって生成された値またはレジスタ・ファイル１５２内のＰＲＩＤのいずれかを含む「値またはＰＲＩＤ」フィールドを含む。この値は、ライトバック・ユニット１６２とライトバック・バス１２２および１９６を介して実行ユニットからトレース・バッファ１１４Ａにライトバックされる。「状況」フィールドは、２ビットにすることができるものであり、「値またはＰＲＩＤ」フィールドが「値」を含むか「ＰＲＩＤ」を含むかを示す。一実施形態では、「値またはＰＲＩＤ」が有効な「値」または有効な「ＰＲＩＤ」のいずれも保持しないことが可能である。「再実施計数値」フィールドは、命令ディスパッチを明確に識別するものであり、同じｉｎｓｔｒＩＤの命令がパイプライン１０８で再実施されるたびに増分される。一実施形態では、パイプライン１０８内で１つの命令を複数回同時に再実施することも可能である。この場合、一実施形態では、最高「再実施計数値」に関連する情報だけがＤＡＤアレイ２０６Ａにライトバックされる。
【００４６】
「依存関係フィールド」は、各論理レジスタに関するビットを含む。図１３では、簡略化のため、４つの論理レジスタ（Ｒ１、Ｒ２、Ｒ３、Ｒ４）だけが表されている。しかし、この数ははるかに大きいものにすることもできる。この例では、依存関係フィールド項目は、トレースへの入力値と命令項目との間にデータ依存関係連鎖が存在することを示すために１にセットされ、依存関係がまったくない場合に０にセットされる。依存関係フィールド項目は、入力値が受け取られた場合に（値の誤推論が検出されたときなどに）トレース内のどの命令を実行する必要があるかを識別する。
【００４７】
命令がフェッチされ、デコードされ、トレース・バッファ１１４Ａに書き込まれると、依存関係ビットが順次計算され、ＤＡＤアレイ２０６Ａに書き込まれる。依存関係ビットは、命令を再実施すべきかどうかが判定される前に生成することができる。図１３の依存関係ビットは、Ｂ．１．ａ項に前述したように６つの命令Ｉ１〜Ｉ５に関するものである。
【００４８】
依存関係フィールドは、機械的手法により作成することができる。このような手法の１つを説明する前に、より直観的なレベルでの作成について説明する。
【００４９】
ｉ．直観レベル
命令Ｉ０の結果はレジスタＲ１およびＲ２のみに依存する。したがって、ｉｎｓｔｒＩＤ０のＲ１列とＲ２列には１が入り、Ｒ３列とＲ４列は０のままになる（命令Ｉ０に関する情報を保持する）。
【００５０】
命令Ｉ１の結果はレジスタＲ３およびＲ４のみに依存する。したがって、ｉｎｓｔｒＩＤ１のＲ１列とＲ２列には０が入り、Ｒ３列とＲ４列には１が入る。
【００５１】
命令Ｉ２の結果は、命令Ｉ０およびＩ１で生成されたレジスタＲ１およびＲ２にそれぞれ直接依存する。命令Ｉ０では、Ｒ１はトレースの先頭にあるＲ１値とＲ２値に依存する。命令Ｉ２では、Ｒ２はトレースの先頭にあるＲ２値とＲ４値に依存する。したがって、命令Ｉ２はトレースの先頭にあるＲ１〜Ｒ４値に間接的に依存し、ｉｎｓｔｒＩＤ２のＲ１〜Ｒ４列には１が入る。
【００５２】
命令Ｉ３の結果は、命令Ｉ２で生成されたレジスタＲ１に直接依存する。したがって、命令Ｉ２がトレースの先頭にあるＲ１〜Ｒ４値に依存するので、命令Ｉ３はこれらの値に間接的に依存し、ｉｎｓｔｒＩＤ３のＲ１〜Ｒ４列には１が入る。
【００５３】
命令Ｉ４の結果は、命令Ｉ１で生成されたレジスタＲ２に直接依存する。Ｒ２はトレースの先頭にあるレジスタＲ３値とＲ４値に依存する。したがって、ｉｎｓｔｒＩＤ４のＲ１列とＲ２列には０が入り、Ｒ３列とＲ４列には１が入る。
【００５４】
命令Ｉ５の結果は、命令Ｉ２で生成されたレジスタＲ１に直接依存し、これはトレースの先頭にあるレジスタＲ１〜Ｒ４に依存する。したがって、ｉｎｓｔｒＩＤ５のＲ１〜Ｒ４列には１が入る。
【００５５】
ｉｉ．機械的手法
本発明の一実施形態による依存関係フィールドを生成するために使用できるレジスタおよびアルゴリズムについて以下に説明する。図１４を参照すると、依存関係生成回路２１２Ａは、各論理レジスタごとに１つずつの一時レジスタ２３０、２３２、２３４、２３６と、追加の一時レジスタ２４０とを含む。一時レジスタ２３０、２３２、２３４、２３６は、論理レジスタＲ１、Ｒ２、Ｒ３、Ｒ４用の修飾子を含む。変更レジスタ２４０は、トレース内の命令によってどの論理レジスタを変更すべきかを示す１組のビットを含む。レジスタ２３０、２３２、２３４、２３６、２４０は、新しい命令がトレース・バッファに書き込まれるたびに更新される。レジスタ間の境界はいくらか任意のものである。たとえば、これらはすべて１つの結合レジスタ内に入れることができる。
【００５６】
各論理レジスタごとにトレース・バッファ・アドレス・レジスタが設けられ、それが論理レジスタを変更するためのトレース・バッファ１１４Ａ内の最後の命令を指し示す。変更ビットおよび最後の修飾子アドレスは、トレース・バッファ１１４Ａに書き込むべき次の命令に関する依存関係ビットを計算するために使用する。
【００５７】
ただし、ここで使用するレジスタの変更とは、そのレジスタの値を書き込むことを意味するだけであることに留意されたい。そのレジスタの内容が命令の結果として異なるものになることを必ずしも意味するわけではない。たとえば、（命令Ｉ０内のように）Ｒ１およびＲ２の内容が乗算され、その結果がレジスタＲ１に書き込まれる場合、Ｒ１の内容は必ずしも命令Ｉ０の結果として異なるものになるわけではない。たとえば、命令前にＲ１の内容が「０」であるかまたはＲ２が「１」である場合、命令後のＲ１の内容は異なるものにはならないだろう。
【００５８】
図１６の流れ図２５０は、ＤＡＤアレイ２０６Ａの依存関係フィールドを作成するためにある命令の各ソース・オペランド（たとえば、ソース１とソース２）ごとに実行されるアルゴリズムを表している。ステップ２５２では、レジスタ２４０に関連ビットがセットされているかどうかが判定される。ステップ２５４に記載するように、レジスタ２４０内のビットがセットされていない場合、そのレジスタに関連する依存関係フィールドのビットは論理１にセットされる。ステップ２５８に記載するように、レジスタ２４０内のビットがセットされている場合、関連レジスタ用の指標レジスタ（２３０、２３２、２３４、または２３６）から作成されたインデックスを使用してソース依存関係フィールドが読み取られる。次に、ステップ２６２に記載するように、論理ＯＲ演算を使用してソース依存関係ビットが現行命令の依存関係ビットとマージされる。このような論理ＯＲ演算は図１５のＯＲゲート２４４に示す（同図では複数のビットが入力側に表されている）。図１６のアルゴリズムを実行する際に参照される変更レジスタおよび修飾子は、ある命令を実行する直前に存在したものである。
【００５９】
Ｉ０に関して説明すると、命令Ｉ０の前にレジスタ２４０はＲ１、Ｒ２、Ｒ３、Ｒ４用として論理０を有し、レジスタ２３０、２３２、２３４、２３６の値は×（指定なし）になる。ステップ２５２では、Ｒ１およびＲ２用のレジスタ２４０内の変更ビットはそれぞれ０になる。したがって、ステップ２５４では、Ｒ１およびＲ２用の依存関係フィールド・ビットは、ＤＡＤアレイ２０６ＡのｉｎｓｔｒＩＤ０行でそれぞれ１にセットされる。レジスタＲ３およびＲ４は含まれないので、ｉｎｓｔｒＩＤ０の行は０のままになる。命令Ｉ０はレジスタＲ１を変更するものである。したがって、レジスタ２３０には０が入り、命令Ｉ０がレジスタＲ１を変更するための最も最新の命令であることを示す。レジスタ２３２、２３４、２３６内の値は×（指定なし）のままになる。レジスタ２４０のＲ１ビットは１にセットされ、そのトレース内の命令によってＲ１が変更されたことを示す。
【００６０】
命令Ｉ１の依存関係フィールドは、命令Ｉ０のものと同様に生成される。変更レジスタ２４０のＲ１論理レジスタ列は１にセットされたままになる。変更レジスタ２４０のＲ２列には論理１が入る。レジスタ２３２内の１は命令Ｉ１を表す。
【００６１】
Ｉ２に関して説明すると、命令Ｉ２の前にステップ２５２では、Ｒ１およびＲ２用のレジスタ２４０内の変更ビットはそれぞれ論理１になる（すなわち、セットされる）。ステップ２５８では、命令Ｉ２の直前のＲ１（２３０）およびＲ２（２３２）用の指標レジスタがインデックスとして使用される。レジスタ２３０は命令Ｉ０に関する０を含む。ＤＡＤアレイ２０６ＡのｉｎｓｔｒＩＤ０の命令Ｉ０用の依存関係フィールドは００１１になる。レジスタ２３２は命令Ｉ１に関する１を含む。ｉｎｓｔｒＩＤ１の命令Ｉ１用の依存関係フィールドは１１００になる。ステップ２６２では、００１１と１１００の論理ＯＲが１１１１になる。したがって、ｉｎｓｔｒＩＤ２用のＤＡＤアレイ２０６Ａの依存関係フィールドには１１１１が入る。Ｒ１は命令Ｉ２によって変更される。しかし、レジスタＲ１用のレジスタ２４０にはすでに１が入っている。レジスタ２３０にはＡ２が入り、命令Ｉ２が命令Ｒ１を変更するための最も最新の命令であることを示す。
【００６２】
命令Ｉ３の依存関係フィールドは、命令Ｉ２のものと同様に生成される。変更レジスタ２４０のＲ４列には論理１が加算され、レジスタ２３６には命令Ｉ３を表す３が入る。論理ＯＲは１１１１を生成する。
【００６３】
Ｉ４に関して説明すると、命令Ｉ４の前にステップ２５２では、Ｒ２用のレジスタ２４０内の変更ビットは１にセットされる。ステップ２５８では、命令Ｉ４の直前のＲ２（２３２）用の指標レジスタがインデックスとして使用される。レジスタ２３２は命令Ｉ１に関する１を含む。ＤＡＤアレイ２０６ＡのｉｎｓｔｒＩＤ１の命令Ｉ１用の依存関係フィールドは１１００になる。ステップ２６２では、１１００（ｉｎｓｔｒＩＤ１からのソース１）と００００（ソース２がまったくない）の論理ＯＲが１１００になる。したがって、ｉｎｓｔｒＩＤ４行用のＤＡＤアレイ２０６Ａの依存関係フィールドには１１００が入る。
【００６４】
命令Ｉ５の依存関係フィールドは、命令Ｉ４のものと同様に生成される。命令Ｉ５およびＩ６は外部メモリ位置を変更するものであり、レジスタ２３０、２３２、２３４、２３６、２４０内の変更は行わない。
【００６５】
この依存関係情報がスケジュール／発行ユニット１５６によって使用される場合もあれば、スケジュール／発行ユニット１５６がそれ専用の依存関係情報を導出するだけの場合もある。
【００６６】
再実施時に一連の命令シーケンスまたは命令ストリングをトレース・バッファ１１４Ａから発行できる方法は様々である。１つの方法は、トレース・バッファを順次読み取って、依存関係ビットがセットされた命令を抽出し、それを再実施のために送信する方法である。しかし、ゼロはパイプライン内にバブルを作り出す効果を有する可能性がある。もう１つの手法は、実行／再実施のために命令を送信する前に論理をパックすることによりバブルを除去させる方法である。図１７を参照すると、もう１つの手法は、各論理レジスタごとにアレイ２６８を含む追加のハードウェアを必要とする。アレイ２６８は、レジスタＲ１に依存する命令のｉｎｓｔｒＩＤ値を含む。アレイ２６８内の値は、命令待ち行列アレイ２０２Ａ内のｉｎｓｔｒＩＤ項目全体を指すポインタとして動作する。このため、命令バッファからの非常に高速な読取りが可能になる。１ブロック分の命令（おそらく、２つまたは４つ）が一度に読み取られる。トレース・バッファ１１４Ａは、マルチポート化し、４つのデコーダを有し、レジスタ・アレイから得られたインデックスのそれぞれ１つをデコーダ内に渡すことができるので、命令Ｉ０、Ｉ２、Ｉ３、Ｉ５は１サイクルで読み取ることができる。レジスタＲ１アレイは、再実施が始まる前に依存関係フィールドを作成したときにアセンブルすることができるだろう。
【００６７】
ｃ．出力レジスタ・ファイル２１０Ａおよび入力レジスタ・ファイル２０８Ａ
トレース・バッファ１１４は、所与の推論エラーを検出するための検出回路を含む。本発明の一実施形態により、各トレース・バッファは、関連スレッドのレジスタ・コンテキストを保持する出力レジスタ・ファイルと、プログラム順序で直前のスレッドのレジスタ・コンテキストを受け取るための入力レジスタ・ファイルとを有する。レジスタ・コンテキストは、論理レジスタの内容または状態である。出力レジスタ・ファイル変更の内容はしばしば更新され、おそらく、レジスタ内で変更が行われるたびに更新される。入力レジスタ・ファイルの内容は、後述する比較の後でのみ更新される。
【００６８】
図１８および図１９は、出力レジスタ・ファイル２０８Ａ（トレース・バッファ１１４Ａ内）と入力レジスタ・ファイル２０８Ｂ（トレース・バッファ１１４Ｂ内）の実施形態を示すが、他の実施形態も使用できる。出力レジスタ・ファイル２０８Ａおよび入力レジスタ・ファイル２１０Ｂは、値またはＰＲＩＤフィールドと状況フィールドとを含む。状況フィールドは、有効な値または有効なＰＲＩＤが値またはＰＲＩＤフィールド内に保持されているかどうかを示す。一実施形態では、有効な値または有効なＰＲＩＤのいずれかが存在する。他の実施形態では、どちらも存在しないことがあり、その場合は、入力レジスタ・ファイルに依存する命令が一方が存在するまで待機することがある。
【００６９】
ただし、上記の例の命令Ｉ０はレジスタＲ１およびＲ２を含み、そのいずれも以前は命令Ｉ０を含むスレッド内の命令の宛先ではなかったことに留意されたい。しかし、レジスタＲ１およびＲ２の値またはＰＲＩＤは入力レジスタ・ファイル２０８Ａから入手可能であり、命令Ｉ０の実行時に使用されるだろう。
【００７０】
図２０を参照すると、比較器２８０Ｂは、現行スレッドに関する入力レジスタ・ファイル２０８Ｂ（トレース・バッファ１１４Ｂ内）の内容と、プログラム順序で直前のスレッドに関する出力レジスタ・ファイル２１０Ａ（トレース・バッファ１１４Ａ内）の内容を比較する。この比較は、直前のスレッドの実行終了時または先行スレッドの最初の実行中に行うことができる。また、この比較は、先行スレッドのリタイヤ終了時にも行われる。一実施形態では、この比較は、先行スレッドのリタイヤ終了時のみに行われる。
【００７１】
比較器２８０Ｂによる比較は、様々な事象によってトリガされる可能性がある。この比較は推論エラーを検出するために行われる。入力レジスタ・ファイルと出力レジスタ・ファイルとの間に違いがある場合、直前のスレッドの出力レジスタのうちの１つまたは複数の値が変更されている。これに応答して、入力レジスタ・ファイル２０８Ｂが更新され、再実施トリガ・ロジック２８４Ｂにより変更されたレジスタ値とともに実施済み命令が再実施される。依存関係フィールドは再実施トリガ・ロジック２８４Ｂによって使用できる。変更された値が結局正しい値（すなわち、純粋に適正順序プロセッサ内で生成されたと思われるレジスタ値）であるという保証はまったくない。その命令は、もう一度、おそらく数回再実施する必要がある場合もある。
【００７２】
一実施形態では、スレッド用の検出回路は、出力レジスタ・ファイルと、入力レジスタ・ファイルと、比較器と、その入力レジスタ・ファイルを含むトレース・バッファ内に保持された命令内の所与の推論エラーを検出するための関連制御回路とを含む。他の実施形態では、検出回路は多少異なる回路を含む可能性がある。
【００７３】
一例として、図２１を参照すると、スレッドＴ２は現行スレッドであり、トレース・バッファ１１４Ｂに関連付けられている。スレッドＴ１はスレッドＴ２の直前のスレッドであり、トレース・バッファ１１４Ａに関連付けられている。スレッドＴ１は、関数呼出しと、その関数と、関数呼出しからの復帰とを含む。スレッドＴ２の実行は関数呼出しの直後に始まる。関数呼出し時に存在した出力レジスタ２１０Ａの内容は、入力レジスタ・ファイル２０８Ｂ内にコピーされる。スレッドＴ２の命令は、入力レジスタ・ファイル２０８Ｂ内のレジスタ・コンテキストに基づいて推論実行される。復帰命令の時点で入力レジスタ・ファイル２０８Ｂの内容は、比較器２８０Ｂによって出力レジスタ・ファイル２１０Ａの内容と比較される。違いがある場合、入力レジスタ・ファイル２０８Ｂは更新され、スレッドＴ２内の実施済み命令が再実施される。この比較は、１つまたは複数の中間時点で行うこともできる。これは、命令の再実施をより均一に分散することによりボトルネックを防止するのに役立つことがあるが、たとえば、出力レジスタ・ファイルの内容がその関数中に複数回変更された場合に追加の再実施を引き起こす可能性がある。出力レジスタ・ファイルは絶えず変化しているので、出力レジスタ・ファイル２１０Ａの内容を受け取る中間バッファを備えていることが望ましいであろう。その場合、比較は中間バッファと入力レジスタ・ファイル２０８Ｂの内容同士で行われることがある。
【００７４】
図８および図１０に示すように、レジスタ・コンテキストは導体２１６により出力レジスタ・ファイルと入力レジスタ・ファイルとの間で渡される。導体２１６は、直前のスレッド用のトレースを保持することができる各トレース・バッファの出力レジスタ・ファイルと各入力レジスタ・ファイルとを接続する。プログラム順序がいつでも特定のトレース・バッファ順序に従うことが保証できる場合、導体２１６のレイアウトはかなり単純なものになる可能性がある。出力レジスタ・ファイルと入力レジスタ・ファイルは、図１０および図１１に示す制御回路２２４Ａによって制御することができる。
【００７５】
出力レジスタ・ファイルと入力レジスタ・ファイルは値またはＰＲＩＤのいずれかを供給することになるので、入力レジスタ・ファイル内の内容を受け取ってから、ソース・オペランドとして入力レジスタからのレジスタを使用して命令を実行できるようになるまでに非常に小さい待ち時間が存在する可能性がある。値が入手できない場合、パイプライン１０８内での実行のためにレジスタ・ファイル１５２へのＰＲＩＤを使用することができる。
【００７６】
正しいソース・オペランドが様々なスレッドのレジスタ・ファイルを通過するときに多くの命令が複数回再実施されることが予想される。しかし、多くのプログラムでは、大量の命令をまったく再実施しないか、あるいは比較的少数回再実施することが必要になり、その結果、単位時間あたりに正しく実行される命令が大幅に増加し、１つのプログラムを実行するのに必要な全時間が減少することも予想される。
【００７７】
２．トレース・バッファ１１４’
図１１を参照すると、トレース・バッファ１１４Ａ’はトレース・バッファ（図１０）と同様のものである。しかし、トレース・バッファ１１４Ａ’内の依存関係フィールドは、ある命令を再実施すべきであると決定された後で、依存関係生成デコード回路２１８Ａ内で生成される。これにより再実施時に何らかの初期待ち時間が発生する可能性があるが、再実施用の命令の発行と依存関係の判定がパイプライン方式で実行される場合、いったんプロセスが開始されると、追加の待ち時間はほとんど発生しない可能性がある。
【００７８】
一実施形態では、依存関係生成デコード回路２１８Ａは依存関係情報用のフィールドを１つだけ保持する。（図１３では、４つのフィールドが存在する。）この同一フィールドは再使用可能である。たとえば、レジスタＲ１に依存する命令の再実施中に、このフィールドを使用してレジスタＲ１に依存する命令をリストすることができるだろう。また、レジスタＲ２に依存する命令の再実施中に、同じフィールドを使用してレジスタＲ２に依存する命令をリストすることができ、以下同様である。依存関係生成デコード回路２１８Ａは、唯一の修飾子フィールドと１つの変更レジスタとを含むことができるだろう。（図１４では、４つ存在する。）あるいは、依存関係生成デコード回路２１８Ａは複数の依存関係フィールドとレジスタとを含むことができるだろう。依存関係生成デコード回路２１８Ａは、一度に数個の命令のみの依存関係を判定することができる。
【００７９】
データ・アレイ２１４Ａは、（図１０および図１３のＤＡＤアレイ２０６Ａと同様に）各ｉｎｓｔｒＩＤ項目ごとの値またはＰＲＩＤフィールドと、状況ビット・フィールドと、再実施計数値フィールドとを含む。あるいは、データ・アレイ２１４Ａの内容を依存関係生成デコード回路２１８Ａに入れて、データ・アレイ２１４Ａを不要にすることができるだろう。データ・アレイ２１４Ａと依存関係生成デコード回路２１８Ａを別々のものとして維持することが有利になりうる理由は２つある。第１に、それらは異なる読取りポートを含む可能性があることである。第２に、一実施形態では、依存関係生成デコード回路２１８Ａは、命令待ち行列アレイ２０２Ａおよびデータ・アレイ２１４Ａと同じ数の行を有していないことである。換言すれば、一実施形態では、依存関係デコード回路２１８Ａは、それが依存関係フィールドを再使用できるのと同様に、行を再使用する。当然のことながら、多くの可能性が存在する。
【００８０】
以下に詳述するように、ＭＯＢ  １７８は、導体１９４を介してロード命令をいつ再実施すべきかを通知する。依存関係フィールド（図１３のＲ１用のものと同様）を有するアレイを生成して、再実施すべきロード命令に依存する命令をリストすることができる。しかし、ロード命令の場合、従属命令のリストは、レジスタの場合のようにトレース内の最初の命令ではなく、そのロード命令から始まる。ロード命令用の依存関係フィールドは、依存関係生成デコード回路２１８Ａ（図１１）内にある可能性がある。（当然のことながら、他のトレース用のロード命令は他のトレース・バッファから再実施されるだろう。）一実施形態では、依存関係生成デコード回路２１８Ａは、ロード命令とレジスタの両方のための依存関係フィールドに使用する。この同一フィールドは両方に使用することができる。他の実施形態では、レジスタ用の依存関係フィールドはＤＡＤアレイ２０６Ａ内にあり、ロード用の依存関係フィールドは依存関係生成デコード回路２１８Ａ内にある。
【００８１】
他の実施形態では、依存関係フィールドが不要になるように、ロード命令は完全に再実施される（すなわち、ロード後のすべての命令が再実行される）。
【００８２】
Ｃ．再実施シーケンス・アルゴリズム
ソース・オペランド（またはその他の入力値）の予測が間違っていると再実施トリガ・ロジック（再実施トリガ・ロジック２８４Ｂなど）が判定すると、そのロジックは対応するトレース・バッファ（トレース・バッファ１１４Ｂなど）をトリガして、予測が間違っているソース・オペランドに直接的または間接的に依存する、パイプライン１０８で再実施すべき命令をディスパッチする。直接的または間接的に依存する命令は、トレース・バッファ内のＤＡＤアレイの依存関係フィールドからまたは図１３のように他のアレイにより識別することができる。
【００８３】
識別された命令は、その命令がトレース・バッファ内に存在する順序（プログラム順序である）で実行するようにトレース・バッファからディスパッチされる。たとえば、ｉｎｓｔｒＩＤ０項目内の命令は、ｉｎｓｔｒＩＤ１項目内の命令より前にまたはその命令と同時にディスパッチされる。しかし、命令は、不適正順序プロセッサの場合のように、スケジュール／発行ユニット１５６の制御下で不適正順序で実行することができる。トレース・バッファからディスパッチされる命令には制御ビットが付加され、（１）レジスタ・リネームを実行すべきか、（２）リネーム／割振りユニット１５０内のリネーム別名（alias）テーブル・ルックアップをバイパスし、代わりに対応するトレース・バッファからのＰＲＩＤを使用すべきか、（３）リネームを完全にバイパスし、それが命令内の定数オペランドである場合と同様にＤＡＤアレイからの値を使用すべきかをリネーム／割振りユニット１５０に示す。
【００８４】
図８に関連して説明したように、「有効１」フィールドと「有効２」フィールドは、ｉｎｓｔｒＩＤの対応するソース・オペランドがトレース・バッファ１１４Ａ内のスレッド外部からの命令（たとえば、その宛先）によって生成されたときに第１の値（たとえば、論理０）にセットされ、ｉｎｓｔｒＩＤ用のソース・オペランドがスレッド内の命令によって生成されたときに第２の値（たとえば、論理１）にセットされるビットである。トレース・バッファ１１４Ａからディスパッチされる再実施された命令は以下のように決定されたソース・オペランドを持つであろう。
【００８５】
（１）有効ビット１。命令待ち行列アレイ２０２Ａ内の有効ビットが論理１にセットされた場合、ソース・オペランドを使用して、ＤＡＤアレイ２０６Ａ内の対応する値またはＰＲＩＤを読み取る。ＤＡＤアレイ状況フィールドの値ビットまたはＰＲＩＤビットのいずれも有効ではない場合、ソース・オペランド・レジスタがまだリネームされていないことを意味する。この場合、導体１２０およびＭＵＸ  １１０により論理０値を有する値およびＰＲＩＤ状況ビットとともにその命令がディスパッチされ、リネーム／割振りユニット１５０はそれが通常行うように別名テーブル・ルックアップ（レジスタ・リネーム）を実行することができる。ＰＲＩＤまたは値が有効である場合、それは導体１２０およびＭＵＸ  １１０により命令とともにリネーム／割振りユニット１５０に渡され、それに応答してそのユニットはリネーム・ステージをバイパスする。
【００８６】
（２）有効ビット０。ソース・オペランド用の有効ビットが論理０にセットされた場合、入力オペランドはトレース外部から得られる。ソース・レジスタ名を使用して入力レジスタ・ファイル２０８Ａにアクセスする。入力レジスタ・ファイル２０８Ａからの値またはＰＲＩＤは命令とともにリネーム／割振りユニット１５０に渡され、それに応答してそのユニットはリネーム・ステージをバイパスする。
【００８７】
有効ビットが０であろうが１であろうが、各ディスパッチ済み命令ごとにＤＡＤアレイ２０６Ａ内の値およびＰＲＩＤ状況フィールド・ビットが論理０にリセットされるか、または論理０のままになる。これにより２つの目的が達成される。第１に、ＰＲＩＤの前にディスパッチされたその後の従属命令がリネーム・ステージからその項目にコピーされ、リネーム別名テーブルからリネームできることが保証され、トレース・バッファ１１４Ａからの古くなったＰＲＩＤの使用が回避される。第２に、最後の実行インスタンスがライトバックされるまで命令がリタイヤしないことが保証され、したがって、すべてのデータ予測間違いが訂正された場合のみ命令がリタイヤ可能になる。
【００８８】
Ｄ．第２レベルまたは最終リタイヤ
すべての先行スレッド用のすべての命令がリタイヤし、ある命令に属すすべての再実施事象が処理されると、その命令はトレース・バッファ１１４から最終的にリタイヤされる。言い換えると、ある命令が正しいソース・オペランドとともに実行されたことを保証できる場合に、その命令は最終的にリタイヤされる。スレッドは適正順序でリタイヤされる。たとえば、スレッドＸ内の命令は、すべての先行スレッドがリタイヤされる（すなわち、すべての先行スレッドの命令がリタイヤされる）まで、リタイヤすることができない。あるスレッド内の命令は適正順序でリタイヤされるが、リタイヤの準備ができているすべての命令は同時にリタイヤすることができる。
【００８９】
最終的なリタイヤは最終リタイヤ・ロジック１３４によって制御される。本発明の一実施形態では、最終リタイヤは、（１）適正順序レジスタ・ファイルへの結果のコミットメントと、（２）サービス割込み、例外、および／または分岐予測間違いと、（３）トレース・バッファおよびＭＯＢ  １７８の資源項目の割振り解除と、（４）リタイヤ済みとしてストアにマークを付け、それをメモリに対して発行するようＭＯＢに通知することを含む。項目の割振り解除は、ヘッド・ポインタの移動を含むことができる。後述するように、ＭＯＢ  １７８内のストア命令は、関連データがデータ・キャッシュ１７６または他のメモリにコピーされたことが確実になるまで割振り解除されない。ＭＯＢ  １７８内のロード命令およびストア命令の最終リタイヤに関する詳細については以下に説明する。
【００９０】
Ｅ．メモリ・システム
図２２は、図２のＭＯＢ  １７８の一実施形態がＭＯＢ  １７８Ａ、１７８Ｂ、・・・、１７８Ｙを含み、ＹがＭＯＢの数を表し、トレース・バッファ１１４の数と一致することを示している。ＭＯＢ  １７８Ａ、１７８Ｂ、・・・、１７８Ｙは、トレース・バッファ１１４Ａ、１１４Ｂ、・・・、１１４Ｙ内のトレースのロード命令およびストア命令のコピーをそれぞれ保持する。ロード命令はロード・バッファ１８２Ａ、１８２Ｂ、・・・、１８２Ｙ内に保持される。ストア命令はストア・バッファ１８４Ａ、１８４Ｂ、・・・、１８４Ｙ内に保持される。導体２９２は、ＭＯＢ  １７８との間で信号を伝達する様々な導体を表している。再実施導体１９４は、ロード命令を再実施すべきであることをトレース・バッファ１１４に警告する信号をＭＯＢ  １７８からトレース・バッファ１１４に供給する。制御回路３０２は様々な制御機能を実行する。
【００９１】
１．ストア・バッファおよびロード・バッファ
図２３はストア・バッファ１８４Ａの一実施形態を示しているが、これはストア・バッファ１８４Ｂ、・・・、１８４Ｙを代表するものである。他の様々な実施形態も使用できるだろう。ストア・バッファ１８４Ａは、ストア・バッファ項目の行に関する様々なフィールドを含む。各項目はストア・バッファＩＤ（ＳＢＩＤ）によって識別される。リネーム／割振りユニット１５０は、各ストア命令が再実施時ではなく最初にフェッチされ実行されたときに、その命令にＳＢＩＤ項目を割り振る。このストア命令は、最終リタイヤまで同じＳＢＩＤ値を有する。たとえば、図２３では、ストア０という命令の場合に項目ＳＢＩＤ０が割り振られる。ストア１という命令の場合に項目ＳＢＩＤ１が割り振られ、以下同様である。後述する「ストアＬＢＩＤ」値を保持するＬＢＩＤフィールドが図２３に示されている。一実施形態では、命令待ち行列アレイ２０２Ａ（図１２）の項目がストア命令を保持する場合、命令待ち行列アレイ２０２ＡのＳＢＩＤフィールドはストア命令を保持するストア・バッファ１８４Ａ内の項目を識別するＳＢＩＤを保持し、ＬＢＩＤフィールドはそのストア命令用として１つ存在する場合にそのストアＬＢＩＤを保持する。ＳＢＩＤおよびストアＬＢＩＤはパイプライン１０８によりストア命令に付随する。その実施形態では、ＬＢＩＤフィールドはストア・バッファ１８４Ａに含まれない可能性もある。
【００９２】
ｉｎｓｔｒＩＤフィールドは、命令待ち行列アレイ２０２Ａ内のストア命令の命令ＩＤを保持する。スレッド・バッファＩＤは、ストア・バッファ１８４Ａとトレース・バッファ１１４Ａのどちらでも暗黙のものである。命令コード・フィールドはストア命令の命令コードを保持する。ストア・アドレス・フィールドはそれに対してストア命令が向けられるアドレスを保持する。図示の実施形態では、アドレスはＡＧＵ  １７２によって生成される。ＳＢアドレス有効フィールドは、ストア・アドレスが有効アドレスであるかどうかを示すビットを含む。データ・フィールドは記憶すべきデータを保持する。データ有効フィールドは、そのデータが有効であるかどうかを示すビットを含む。有効アドレスは有効データとは異なる時点に到着する可能性があるので、アドレス有効ビットとデータ有効ビットとして別々のビットを使用することができる。アドレスとデータはどちらもストア命令が実行される前に到着する。一実施形態では、データは命令の一部として含まれる。リタイヤ済みフィールドは、ストア命令がリタイヤすべきであることを最終リタイヤ・ロジック１３４が示すときにセットされ、メモリへのストアが完了したという確認をメモリから受け取ったときにリセットされるビットを含む。ロードおよびストアのリタイヤについては後述する。再実施計数値フィールドは再実施計数値数を含む（図１３のＤＡＤアレイ２０６Ａの再実施計数値フィールドと同様のものである）。再実施計数値フィールドは必須のものではない。一実施形態では、ストア命令は一度に１回しか再実施できないので、再実施計数値フィールドはまったく存在しない。
【００９３】
図２４はロード・バッファ１８２Ａの一実施形態を示しているが、これはロード・バッファ１８２Ｂ、・・・、１８２Ｙを代表するものである。他の様々な実施形態も使用できるだろう。ロード・バッファ１８２Ａは、ロード・バッファ項目の行に関する様々なフィールドを含む。各項目はロード・バッファＩＤ（ＬＢＩＤ）によって識別される。リネーム／割振りユニット１５０は、各ロード命令が再実施時ではなく最初にフェッチされ実行されたときに、その命令にＬＢＩＤ項目を割り振る。このロード命令は、最終リタイヤまで同じＬＢＩＤ値を有する。たとえば、図２４では、ロード０という命令の場合に項目ＬＢＩＤ０が割り振られる。ロード１という命令の場合に項目ＬＢＩＤ１が割り振られ、以下同様である。（ＬＢＩＤ項目番号とＳＢＩＤフィールドはＭＯＢ  ＩＤと呼ぶことができる。）後述する「ロードＳＢＩＤ」値を保持するＳＢＩＤフィールドについては図２４に示す。一実施形態では、命令待ち行列アレイ２０２Ａ（図１２）の項目がロード命令を保持する場合、命令待ち行列アレイ２０２ＡのＬＢＩＤフィールドはロード命令を保持するロード・バッファ１８２Ａ内の項目を識別するＬＢＩＤを保持し、ＳＢＩＤフィールドはそのロード命令用として１つ存在する場合にそのロードＳＢＩＤを保持する。ＬＢＩＤおよびロードＳＢＩＤはパイプライン１０８によりロード命令に付随する。その実施形態では、ＳＢＩＤフィールドはロード・バッファ１８２Ａに含まれない可能性もある。
【００９４】
ｉｎｓｔｒＩＤフィールドは、命令待ち行列アレイ２０２Ａ内のロード命令の命令ＩＤを保持する。スレッド・バッファＩＤは、ロード・バッファ１８２Ａとトレース・バッファ１１４Ａのどちらでも暗黙のものである。命令コード・フィールドはロード命令の命令コードを保持する。ロード・アドレス・フィールドはそれからロード命令がロードされるアドレスを保持する。項目有効フィールドは有効ロード命令によってその項目が占有されることを示すビットを含む。図示の実施形態では、アドレスはＡＧＵ  １７２によってすでに生成されているので、アドレス有効フィールドは含まれない。ＰＲＩＤフィールドは、レジスタ・ファイル１５２内のロード命令の宛先を示す、リネーム／割振りユニット１５２からのＰＲＩＤを保持する。ＳＢヒット、ＳＢＩＤ、スレッドＩＤ、再実施計数値フィールド（１つ存在する場合）は、状況フィールドの一部と見ることができ、ストア命令の実行に関連して後述する。
【００９５】
ストア命令およびロード命令がリネーム／割振りユニット１５０によって最初に受け取られた時点で、ストア命令およびロード命令用の項目がストア・バッファ１８４およびロード・バッファ１８２内に割り振られ、ロードした値を受け取るためのレジスタ用の項目はレジスタ・ファイル１５０およびＲＯＢ  １６４内に割り振られる。これらの項目は第１レベル・リタイヤの対象にはならないが、トレース・バッファ１１４内の同様の項目は最終リタイヤまで割り振られたままになる。したがって、再実施時に項目の再割当ては行われない。ストア・バッファまたはロード・バッファがいっぱいである場合、それぞれＩキャッシュ１０４からのストア命令またはロード命令は、ある項目が解放されるまでリネーム／割振りユニット１５０を通過することはない。しかし、トレース・バッファから再実行中のロード命令またはストア命令はリネーム／割振りユニット１５０を通過することになる。
【００９６】
２．ロード・アドレスとストア・アドレスの比較
図５を参照すると、プログラム順序では、ロードＭＸがスレッドＴ２で実行される前にスレッドＴ１内のストアＭＸが実行される。しかし、同時実行であるので、時間順序では、ロードＭＸの前または後にストアＭＸを実行することができる。時間順序でロードＭＸの前にストアＭＸが実行される場合、ロードＭＸの推論実行はストアＭＸに関して正しい順序で行われることになる。プログラム順序でストアＭＸの前にあるすべての命令がリタイヤされた場合、ロードＭＸがメモリ位置ＭＸから正しい値をロードすることが確実になる。この正しい値は、適正順序プロセッサによってスレッドが実行された場合にロードされたと思われる値である。プログラム順序でストアＭＸの前にあるすべての命令がリタイヤされたわけではない場合、ストアＭＸ用のデータが間違っている可能性が常にある。
【００９７】
対照してみると、時間順序でロードＭＸの後にストアＭＸが実行される場合、ロードＭＸの推論実行はストアＭＸに関して正しい順序で行われず、ロードＭＸが正しい値をロードするという保証はまったくない。正しい値がたまたまメモリ位置ＭＸ（またはストアＭＸが最終リタイヤされるまでストアＭＸを保持するストア・バッファ項目のデータ・フィールド）にあるのは単に偶然にすぎないだろう。実行の最終的な正確さを保証するため、ＭＯＢ  １７８は、スレッド間のメモリ・データの一貫性を保証するための様々な機構を含む。
【００９８】
ａ．ロード命令の実行
ロード命令が実行される前に、そのアドレスとストア命令のアドレスが比較され、ストア命令がある場合にどのストア命令が最接近先行一致ストア命令（ＣＥＭＳＩ）であるかを判定する。「一致」とは、ロード命令と同じアドレスを有することを意味する。「先行」とは、ＣＥＭＳＩがプログラム順序でロード命令より前であることを意味する。「最接近」とは、ＣＥＭＳＩと実行すべきロード命令との間に他の一致ストア命令がまったくないことを意味する。先行一致ストア命令が１つだけ存在する場合、それがＣＥＭＳＩになる。
【００９９】
ＣＥＭＳＩが存在する場合、ロード命令はＣＥＭＳＩのデータ・フィールドからそのデータを読み取る。ＣＥＭＳＩが存在しない場合、ロード命令はデータ・キャッシュ１７６、Ｌ２キャッシュ、メイン・メモリなどのメモリからそのデータを取る。ストア・バッファ１８４またはメモリからのデータはＭＵＸ１９２を通過し、スレッドＩＤおよびｉｎｓｔｒＩＤによって指定されたトレース・バッファ１１４内の項目に書き込まれる。また、このデータは、ＰＲＩＤによって指定されたレジスタ・ファイル１５２内のレジスタにも書き込むことができる。また、このデータは、キャッシュ規則（たとえば、ライトバック、ライトスルーなど）に応じてデータ・キャッシュ１７６に記憶することもできる。ＭＵＸ  １９２は、データ・キャッシュ１７６、Ｌ２キャッシュ、メイン・メモリなどのメモリをバイパスすることができるので、バイパスになる。
【０１００】
一実施形態では、実行すべきロードのアドレスとストア命令のアドレスとの比較を行うために、各ストア・バッファ１８４の各項目に異なる比較器が関連付けられている。図２５の比較器３２０は一例であり、ストア・バッファ１８４Ａ内の項目ＳＢＩＤ１のストア・アドレスとロード命令アドレスを受け取る。導体３２２ならびに他の比較器からの出力導体はＭＯＢ制御回路３０２に接続される。
【０１０１】
ロードＳＢＩＤは、実行すべきロード命令に関する最接近先行ストア命令（ＣＥＳＩ）のＬＢＩＤを指し示す。ＣＥＳＩは、ロード命令と同じスレッドＩＤを有するストア・バッファ内にある。ＣＥＭＳＩが存在する場合、それは、ＣＥＳＩになるかまたはプログラム順序でＣＥＳＩより前になる。リネーム／割振りユニット１５０は、プログラム内のストア命令およびロード命令の順序を追跡し、ＳＢＩＤ値およびＬＢＩＤ値を供給する。これらは、導体１２６を介してトレース・バッファ１１４に書き込むことができる。一実施形態では、ロード命令に関するＣＥＳＩがまったく存在しない場合、その命令に関連するロードＳＢＩＤはまったく存在しない。これは、トレース内の第１のメモリ命令がロードである場合に発生する。有効ロードＳＢＩＤがまったく存在しないことを示すためにリネーム／割振りユニット１５０が所与の信号を送信することを含み、このような状況を処理するために様々な技法を使用することができる。後述するアレイ・ラップアラウンド・ビットはこの目的に使用することができる。
【０１０２】
以下のプログラム順序のストア命令およびロード命令について検討する。
ストア０
ストア１
ロード０
ストア２
ロード１
ストア３
ストア４
ロード２
ＬＢＩＤフィールド内のストアＬＢＩＤ値はストア・バッファ１８２Ａ内に示されている。ＳＢＩＤフィールド内のロードＳＢＩＤ値はロード・バッファ１８４Ａ内に示されている。たとえば、ＬＢＩＤ項目１のＳＢＩＤフィールド内の２は、ストア・バッファ１８４Ａ内の項目ＳＢＩＤ２にあるストア命令がＬＢＩＤ項目１内のロード命令に関するＣＥＳＩを保持することを示している。ストア０、ストア１、ストア２、ロード０という命令はロード１より古い、すなわち前のものである。ストア３、ストア４、ロード２という命令はロード１より新しい、すなわち後のものである。
【０１０３】
ストア命令がある場合にどのストア命令がＣＥＭＳＩであるかを制御回路３０２が判定するための様々な方法がある。この方法の例については図２７に関連して説明するが、同図ではストア・バッファ１８４Ａ、１８４Ｂ、１８４Ｃ、１８４ＤだけがＭＯＢ  １７８内のストア・バッファであり、スレッドＡ、Ｂ、Ｃ、Ｄにそれぞれ関連付けられている。プログラム順序がスレッドＡ、スレッドＢ、スレッドＣ、スレッドＤであると想定する。この例では、実行すべきロード命令はロード・バッファ１８２Ｃ内にある。ＣＥＳＩが存在し、ストア・バッファ１８４Ｃ内にある。
【０１０４】
導体３４２、３４４、３４６、３４８は様々な比較器の出力導体である。導体３６２、３６４、３６６、３６８は、比較器が比較を実行できるようにする制御信号を供給する。様々な実施形態では、制御回路３０２は、（１）各ストア・バッファ内のすべての項目用の比較器をイネーブルにするか、（２）プログラム順序でロード命令のスレッドＩＤと同じであるかまたはそれより前のスレッドＩＤを有するストア・バッファ内にある比較器のみをイネーブルにするか、あるいは（３）プログラム順序でロード命令より前の項目に関連する比較器のみをイネーブルにする。
【０１０５】
一致判定ロジック３５６は、ストア命令がある場合にそのうちのどれがＣＥＭＳＩであるかを判定する。図２７では、ストア・バッファ１８４Ｃの上部部分内のストアＭＸ命令がＣＥＭＳＩになる。ストアＭＸ命令がストア・バッファ１８４Ｃ内にない場合、ＣＥＭＳＩは、ストア・バッファ１８４Ｂ内のストアＭＸ命令になるだろう。比較器および一致判定ロジック３５６がＣＥＭＳＩが存在するかどうかを判定する間に、ＣＥＭＳＩが存在しない場合に用意すべきデータ・キャッシュ１７６（および他のメモリ）内でルックアップが行われる可能性がある。一致判定ロジック３５６はデータ経路制御ロジック３９０を含み、これはＭＵＸ  １９２がメモリまたはストア・バッファからのデータを渡すかどうかを制御するための信号を導体３７０で供給する。
【０１０６】
１つの手法では、ＭＯＢ制御回路３０２によって２通りの優先順位判定が行われる。一方は、ストア・バッファ内のストア命令の優先順位を判定するためのものである。もう一方は、ストア・バッファの優先順位を判定するためのものである。これらの判定はいずれの順序で行うこともできる。桁上げ連鎖構造は、ストア・バッファ内の優先順位の判定の際に使用することができる。たとえば、一実施形態では、ロード命令と同じスレッドＩＤを有するもの以外の各ストア・バッファごとに、一致ストア命令がある場合にどの一致ストア命令がプログラム順序で最も新しいかが判定される。ロード命令と同じスレッドＩＤを有するストア・バッファの場合、一致命令がある場合にどの一致命令がプログラム順序でＣＥＳＩに最も近い（等しいものを含む）かが判定される。次に、一致命令を有するストア・バッファのうち、どのストア・バッファがプログラム順序でロード命令のスレッドＩＤに最も近いスレッドＩＤを有するかが判定される。
【０１０７】
ストア・バッファ１８４は、それぞれ先頭と末尾を有する循環アレイでよい。最初は、ＳＢＩＤ値が大きいストア命令の方が新しい。しかし、ストア命令が割振り解除され、割り振られるにつれて、末尾は結局、折り返すことになり、先頭は末尾より大きいＳＢＩＤ項目を指し示すことになる。一実施形態では、末尾が最高値から最低ＳＢＩＤ値へ移行すると、ラップアラウンド・ビットが切り替えられ、最接近一致判定ロジック３５６に供給される。
【０１０８】
ｂ．ストア命令の実行
ストア命令が実行されると、そのアドレスがロード命令のアドレスと比較され、（同じスレッドまたはそれより新しいスレッドから）プログラム順序でそれより後のロード命令がある場合に、どのロード命令がストア命令と同じアドレスを有するかを判定する。ストアＳＢＩＤによって指し示された最接近後続ロード命令（ＣＬＬＩ）は、考慮可能な最も早いロード命令を示す。
【０１０９】
一実施形態では、このような比較を行うために各ロード・バッファ１８２の各項目ごとに異なる比較器が関連付けられている。比較器の１つは図２６に示す比較器３２４である。単に一例にすぎないが、比較器３２４はロード・バッファ１８２Ａの項目ＬＢＩＤ１に関連付けられている。比較器３２４は、一方の入力でストア命令のアドレスを受け取り、もう一方の入力でロード・バッファ１８２Ａ内の項目ＬＢＩＤ１のロード・アドレス・フィールド内のアドレスを受け取る。出力導体３２６上の信号は、両方のアドレスが同じであるかどうかを通知する。導体３２６ならびに他の比較器からの出力導体はＭＯＢ制御回路３０２に接続されている。比較器（比較器３２４など）は、後述するように、ストア命令の状況ビットとロード・バッファ内の状況ビットとの比較も行うことができる。
【０１１０】
図２８は図２７と同様のものである。しかし、図２８では、ロード・バッファ１８２Ａ〜１８２Ｄ内のロード命令アドレスが実行すべきスト命令のアドレスと比較され、一致判定ロジック３５６は、ロード命令を再実施すべきかどうかを判定する。一実施形態では、一致判定ロジックは、どのロード命令を再実施すべきかをトレース・バッファに示すための信号を導体１９４上に供給する再実施トリガ・ロジック３９４を含む。一実施形態では、一致判定ロジック３５６は、ＣＬＬＩから始めて、ストア命令とロード命令との一致について考慮する。様々なアルゴリズムを使用することができる。スレッド管理ロジック１２４は、プログラム順序で実行中のストア命令のスレッドＩＤより後のスレッドＩＤを示す。一実施形態では、すべての比較器が使用可能になっている。他の実施形態では、プログラム順序でロード命令のスレッドＩＤと等しいかまたはそれより後のスレッドＩＤを有するロード・バッファ内の導体だけが使用可能になる。さらに他の実施形態では、ＣＬＬＩおよびその後の命令に関連するロード・バッファ内の導体だけが使用可能になる。考慮すべきスレッドは、ロード・バッファ内のロード命令がプログラム順序でストア命令より後になっているかに関する判定前、判定後、あるいは判定中に決定することができる。
【０１１１】
一実施形態では、ロード命令の実行時に所与の推論エラーを検出するための検出回路は、ロード・バッファに関連する比較器と、一致判定ロジック３５６の一部分と、関連の制御回路とを含む。他の実施形態では、この検出回路は多少異なる回路を含むことができるだろう。推論エラーを検出するための検出回路が実行パイプライン内にあることは必須ではない。データ経路制御ロジックおよび再実施トリガ・ロジックに関連して異なる一致判定ロジックを使用することができるだろう。
【０１１２】
ｉ．アドレス一致が存在するケース
再実施すべきかどうかを判定する際に、アドレス一致が存在する新しい命令に関する状況フィールド（ＳＢヒット、ＳＢＩＤ、スレッドＩＤ、再実施計数値（使用する場合））が考慮される。状況フィールドは、ロード命令がそのデータをメモリ（たとえば、データ・キャッシュ１７６）から獲得したかまたはストア・バッファのデータ・フィールドから獲得したかを示す。ＳＢヒット・フィールドは、たとえば、データがメモリから得られた場合に０を有し、データがストア・バッファから得られた場合に１を有する。ＳＢＩＤフィールドとスレッドＩＤフィールドは、そこからデータが得られたストア命令のＳＢＩＤとスレッドＩＤを保持する。ストア命令のスレッドＩＤは、必ずしも、アドレス一致が存在するロード命令のスレッドＩＤではない。ロード命令のスレッドＩＤはロード・バッファ内では暗黙のものである。再実施計数値フィールド（使用する場合）は、どの再実施が含まれるかを示す。（ＳＢヒットが０である場合、ＳＢＩＤフィールド、スレッドＩＤフィールド、再実施計数値フィールド内のデータは無意味なものになる。）
【０１１３】
ＳＢヒット＝０（メモリからの前のデータ）である場合、再実施事象は導体１９４によりロード・バッファからロード命令のスレッドＩＤによって識別されるトレース・バッファに通知され、そのロード命令とすべての従属命令はそのトレース・バッファから再実施される。ｉｎｓｔｒＩＤとスレッドＩＤは、どの命令が再実施されるかを示すために導体１９４を通して渡される。
【０１１４】
ＳＢヒット＝１（ストア・バッファからの前のデータ）である場合、ＳＢＩＤフィールド、スレッドＩＤフィールド、再実施計数値フィールド（使用する場合）の値は、再実施をトリガするかどうかを制御する。第１のケースでは、特定のロード命令に関する状況フィールドのスレッドＩＤはストア命令のスレッドＩＤと等しく、特定のロード命令の状況フィールド内のＳＢＩＤはストア命令のＳＢＩＤと一致する。この第１のケースでは、ロード命令の再実施計数値が状況フィールド内の再実施計数値より大きい場合にそのロード命令が再実施される。再実施計数値が存在しない場合（ストア命令は一度に１回しか再実施できないため）、ロード命令は再実施される。
【０１１５】
第２のケースでは、状況フィールド内のスレッドＩＤはストア命令のスレッドＩＤと等しいが、状況フィールド内のＳＢＩＤはストア命令のＳＢＩＤと一致しない。この第２のケースでは、状況フィールド内のＳＢＩＤがストア命令のＳＢＩＤより小さい場合にそのロード命令が再実施され、状況フィールド内のＳＢＩＤがストア命令のＳＢＩＤより大きい場合にそのロード命令は再実施されない。
【０１１６】
第３のケースでは、状況フィールドとストア命令のスレッドＩＤは一致しない。これはまれなケースであると予想される。単純にするため、一実施形態では、（プログラム順序に反する可能性がある場合でも）ロード命令が再実施される。これは間違った再実施である可能性がある。ロード命令は、再実施されると、正しいストア・データを受け取ることになる。他の手法を使用することもできるが、このようなまれなケースに妥当なものよりかなり複雑なものである可能性がある。
【０１１７】
ｉｉ．アドレス一致が存在しないケース
アドレスが一致しない場合、以下に示すまれなケースを除き、再実施は一切トリガされない。ＳＢヒット＝１である場合、状況フィールドのスレッドＩＤはストア命令のスレッドＩＤと一致し、状況フィールドのＳＢＩＤはストア命令のＳＢＩＤと一致する。このケースでは、再実施が行われ、再実施したロード命令はそのデータを新しい項目またはメモリから受け取る。
【０１１８】
ｃ．リセット
スレッドがプログラム順序になっていないと判定されると、そのスレッドはリセットされる。しかし、他のスレッドからのロードによって、そのスレッド内のストア命令に関連するデータ・フィールドからデータが取られている可能性がある。スレッド管理ロジック１２４は制御回路３０２に信号を送信する。一実施形態では、スレッドがリセットされると、リセットされたスレッドのスレッドＩＤが（おそらくリセットされたスレッドに対応するロード・バッファは除く）すべてのロード・バッファ内のすべてのロードと比較される。状況フィールド内のスレッドＩＤがリセットされたスレッドのスレッドＩＤと一致する場合、ロード命令に関する再実施がトリガされる。ロード命令は適切なトレース・バッファから再実施される。
【０１１９】
３．ストア命令の再実施
前述のように、ストア命令の実行に応答してロード命令が再実施される。一実施形態では、レジスタ値が変更されたことを示すトレース・バッファ内のレジスタ比較に応答してストア命令が再実施される。たとえば、図１２および図１３を参照すると、トレース・バッファ１１４Ａ内のｉｎｓｔｒＩＤ４およびｉｎｓｔｒＩＤ５はストア命令であり、レジスタＲ１〜ｒ４に依存するものとして示されている。
【０１２０】
４．複数ロード命令の再実施
ロード・バッファ内の複数のロード命令がストア命令との状況フィールド一致を有することは可能である。複雑なロジックを回避するための１つの手法では、制御回路３０２が複数のロード・アドレス一致が存在する場合を検出し、トレース内で最も早いロード以降のすべての命令を再実行させる。
【０１２１】
５．ロード命令とストア命令の最終リタイヤ
ロード命令またはストア命令を最終リタイヤすべき場合、最終リタイヤ・ロジック１３４は、命令を最終リタイヤすべきであることを示す信号をトレース・バッファ１１４およびＭＯＢ１８４に供給する。（ｉｎｓｔｒＩＤおよびスレッドＩＤによって識別される）トレース・バッファ内の項目の割振りが解除される。ロード命令の場合には、（スレッドＩＤおよびＬＢＩＤによって識別される）ロード・バッファ内の項目の割振りが解除される。ロード命令の場合には、最終リタイヤが完了する。ストア命令の場合には、割振り解除の前にデータ・フィールド内のデータをメモリにコミットしなければならない。ストア・バッファ内の項目の割振り解除と、それ故の最終リタイヤは、そのストアが完了したという確認を受け取るまで行われない。あるいは、確認前にその項目の最終リタイヤを行うことができるが、確認を受け取るまでその項目の再割振りを行うことができない。導体２００上の信号は、ストアの最終リタイヤが完了し、次のスレッドを開始することができる時期をスレッド管理ロジック１２４に示すことができる。
【０１２２】
ＳＢリタイヤ済みは、命令がリタイヤされたことを示す。命令をリタイヤすべきであることを最終リタイヤ・ロジック１３４が示した時点で、ＳＢリタイヤ済みフィールド内のビットがアサートされる。ＳＢリタイヤ済みフィールドがアサートされると、関連命令が適正順序でメモリに書き込まれる。命令がメモリに書き込まれたことをＭＯＢ  １８４Ａが知ると直ちにＳＢリタイヤ済みフィールドがアサート解除され、その命令の割振りが解除される。
【０１２３】
ロード・バッファ１８２Ａおよびストア・バッファ１８４Ａは、先頭と末尾を備えた待ち行列にすることができる。命令の割振りが解除されると、先頭は移動する。ロード・バッファ１８４Ａおよびトレース・バッファ１１４では、リタイヤと割振り解除が同時に行われる場合もある。最終リタイヤ・ロジック１３４は、導体１３６および１４０を介して信号を供給する。デマルチプレクサ１８８は、ロード・バッファ１８２またはストア・バッファ１８４のうちの一方がリタイヤ信号を受け取ることになることを選択する。デマルチプレクサ１８８は任意選択のものであり、ロード・バッファ１８２およびストア・バッファ１８４内のイネーブル・ポートで置き換えることができるだろう。
【０１２４】
Ｆ．スレッド管理ロジックおよび最終リタイヤ・ロジックに関する追加情報
一実施形態では、スレッド管理ロジック１２４は、スレッド順序を追跡するためにツリー構造を使用する。このツリー構造では、プログラム順序（リタイヤ順序でもある）は上から下に流れ、右側のノードはプログラム順序で左側のノードより早い。ルートはプログラム順序で最初のものである。ツリーとは抽象概念であり、ツリー構造はそのツリーを実施する回路である。
【０１２５】
スレッドは、逆方向分岐または関数呼出し後の命令から始まる。すなわち、（図４および図５のスレッドＴ２が示すように）逆方向分岐が行われなかったかまたは関数が呼び出されなかったと想定して、スレッドは次の命令から始まる。このように行う場合、スレッド（ノード）の見地によると、そのスレッドの子ノードのプログラム順序は、スレッドが開始（作成）された順序の逆になる。たとえば、図６では、時間順序ではスレッドＴ２の実行がスレッドＴ３の実行前に始まるが、プログラム順序ではスレッドＴ３がスレッドＴ２の前に行われる。
【０１２６】
一実施形態では、３通りの事象によりスレッドがツリーから除去される場合がある。すなわち、（１）ツリーのルートにあるスレッドは、そのスレッドがリタイヤされると除去される。ルートにあるスレッドがリタイヤされると、プログラム順序で次のスレッド（ノード）がルートになり、それに応じてノードの再割当てが行われる。（２）プログラム順序で最後のスレッドはツリーから除去され、プログラム順序でより上位にあり、ツリーに追加すべきスレッドのためのスペースができる。これに関して、ツリーは後入れ先出し法（ＬＩＦＯ）スタックとして動作する。（３）その親スレッドのプログラム・カウンタが開始計数値から終了計数値までの範囲の外にあることが発見されると、スレッドはリセットされ、それによりツリーから除去することができる。逆方向分岐で子スレッド（たとえば、図６および図２９のスレッドＴ４）が作成される場合、開始計数値は逆方向分岐のターゲットになり、終了計数値は逆方向分岐命令におけるプログラム・カウンタ値になる。関数呼出し後に開始されたスレッドもリセットすることができる。というのは、このようなことが起こるのは極めてまれなことであるが、関数からの復帰がまったく存在しないからである。関数からの復帰がまったく存在しない可能性を処理するための手法の１つは、この可能性を無視し、事象（２）のようにそれがプログラム順序の最下位になると結局、システムにツリーからスレッドを除去させることである。スレッドがツリーから除去されると、そのスレッドに割り振られた資源（トレース・バッファ、ストア・バッファ、ロード・バッファなど）の割振りが解除される。
【０１２７】
事象（１）および（３）は図２９に示されているが、同図は図６の例のスレッドを含み、スレッドＴ５およびＴ６が追加されている。スレッドＴ５はポイントＪの逆方向分岐命令に続いて開始され、スレッドＴ６はポイントＫの関数呼出しに続いて開始される。トレース・バッファは４つだけであると想定する。図３０は時点ｔ１におけるツリー構造を示している。スレッドＴ２は、スレッドＴ３がツリーに追加される前にツリーに追加される。スレッドＴ４は、スレッドＴ３がツリーに追加された後でツリーに追加される。スレッドＴ２およびＴ２はスレッドＴ１の子である。スレッドＴ４はスレッドＴ３の子である。上から下へ、右から左へという規則に従うと、プログラム順序およびリタイヤ順序はスレッドＴ１、Ｔ３、Ｔ４、Ｔ２になる。図３１は、スレッドＴ１がリタイヤする前にスレッドＴ４がリセットされると想定した時点ｔ２におけるツリー構造を示している。プログラム順序およびリタイヤ順序はスレッドＴ１、Ｔ３、Ｔ２、Ｔ５になる。図３２は、スレッドＴ４がリセットされる前にスレッドＴ１がリタイヤすると想定した時点ｔ２におけるツリー構造を示している。プログラム順序およびリタイヤ順序はスレッドＴ３、Ｔ４、Ｔ２、Ｔ５になる。図３３は、時点ｔ３におけるツリー構造を示しているが、これはスレッドＴ１がリタイヤし、スレッドＴ４がリセットされた後である。プログラム順序およびリタイヤ順序はＴ３、Ｔ２、Ｔ５、Ｔ６になる。
【０１２８】
事象（２）は図３４に示されているが、同図はネストされた関数を含む。時間順序では、スレッドはＴ１、Ｔ２、Ｔ３、Ｔ４、Ｔ５の順序で作成（開始）される。しかし、プログラム順序はＴ１、Ｔ５、Ｔ４、Ｔ３、Ｔ２である。この例では、トレース・バッファは４つだけである。したがって、５つのスレッドがすべて同時に存在するわけではない。図３５は、時点ｔ１におけるツリー構造を示しているが、これはスレッドＴ５が開始される前である。プログラム順序およびリタイヤ順序はスレッドＴ１、Ｔ４、Ｔ３、Ｔ２になる。スレッドＴ５はまだツリー構造の一部になっていない。図３６は、時点ｔ２におけるツリー構造を示しているが、これはスレッドＴ５が開始された後である。スレッドＴ２はプログラム順序で最下位であり、スレッドＴ５のためのスペースを作るためにツリー構造から除去される。ツリーから除去されたスレッドは、後で再開することができる。あるいは、他のスレッドでは、ツリーから除去されたスレッドの命令の全部または一部を実行することができる。一実施形態では、リセットの場合、スレッドはリセットされたスレッドではなく、次に続くスレッドを結合しようとする可能性がある。あるいは、そのスレッドはその他の方法で終了されるまで続行される可能性がある。アレイ１９８の関数はツリーのノードで実行することができる。
【０１２９】
子スレッドのスレッドＩＤは、ツリー構造内のプログラム順序に応じて適切に位置決めされる。（ただし、スレッド管理ロジック１２４によって決定されたプログラム順序は変わらない可能性がある。）あるスレッドは、プログラム順序でツリー内の次のスレッドを結合するかまたはそのプログラム計数値と一致する場合に終了する。スレッドの子が１つだけである場合、それはプログラム順序で次のスレッドになる。たとえば、図３３では、スレッドＴ２はプログラム順序でツリー内の次のスレッドになる。
【０１３０】
最終リタイヤ・ロジック１３４は、アレイ１９８をアセンブルするためにツリー構造からまたはツリー構造の回路から直接に、情報を獲得する。ツリー構造と、スレッド管理ロジック１２４の他のロジックおよび最終リタイヤ・ロジック１３４のロジックとの間にデコード回路が存在する可能性がある。アレイ１９８は必須ではない場合がある。
【０１３１】
要約すると、このツリー構造は、少なくとも以下に示す目的のために情報を提供する。すなわち、（１）ツリーはリタイヤ順序を指定し、（２）ツリーは前述のようにたとえばＭＯＢ  １７８が使用するプログラム順序を指定し、（３）ツリーは他のスレッドの開始命令を示すことによりスレッドの終了点を指定し、（４）ツリーはどの資源が使用可能であり、どの資源が割振り解除されているかを示すことによりスレッド資源割振りの際に使用する。
【０１３２】
Ｇ．マルチスレッド化を含まない実施形態
図３は、パイプライン３０８を含むプロセッサ１００を示している。プロセッサ１００はプロセッサ５０と同様のものである。しかし、トレース・バッファ３００は唯一のトレース・バッファであり、ＭＯＢ  ３１０は唯一のＭＯＢである。プロセッサ５０は、複数スレッドを処理するように設計されていない。したがって、プロセッサ１００にはスレッド管理ロジックは不要である。トレース・バッファ３００は、たとえばトレース・バッファ１１４Ａと同様のものにすることができるが、マルチスレッド特有の構成要素は不要である。たとえば、導体２１６および出力レジスタ・ファイル２１０は不要になるだろう。周知の回路を含む様々な回路を使用して推論エラーを検出することができる。ＭＯＢ  ３１０はたとえばＭＯＢ  １７８Ａと同様のものにすることができるが、マルチスレッド特有の特徴は不要である。たとえば、ロード・バッファではスレッドＩＤフィールドは不要になるだろう。プロセッサ１００の他の構成要素は、マルチスレッド化関連の特徴を除去するためにプロセッサ５０内のそれぞれの構成に関して多少変更される可能性がある。トレース・バッファ３００およびＭＯＢ  ３１０は様々な推論ならびにその際のエラーからの回復に関連して使用することができる。トレース・バッファにより、最終リタイヤ前に可能な再実施のために、多数の命令をパイプライン外部に保持することができる。
【０１３３】
プロセッサ５０は非マルチスレッド・プログラムに関連して使用することができるだろう。その場合、スレッド管理ロジック１２４は必ず同じスレッドＩＤをプログラム順序で維持することができるだろう。あるいは、スレッド管理ロジック１２４は使用不能にすることができるだろう。非マルチスレッドの場合、唯一のトレース・バッファ１１４と唯一のＭＯＢ  １７８が使用される。あるいは、複数のトレース・バッファを結合してより大きいトレース・バッファにすることができ、複数のＭＯＢを結合してより大きいＭＯＢにすることができるだろう。
【０１３４】
Ｈ．追加情報および実施形態
図３７を参照すると、プロセッサ４００は、マルチパイプライン・ユニット４０２を含むマルチプロセッサ（ＭＰ）チップである。マルチパイプライン・ユニット４００は、パイプライン全体（たとえば、各パイプラインごとに別々のリネーム／割振りユニット）がマルチパイプライン・ユニット４０２の各パイプライン０、１、・・・、Ｗとともに含まれるという点で図２の共用資源パイプライン１０８とは異なる。（ＷはＸと等しいかあるいはそれより大きいかまたは小さいものにすることができる。）そうではない場合、プロセッサ４００はプロセッサ５０と本質的に同じであるかまたはプロセッサ５０とは非常に異なる可能性がある。他のプロセッサは、マルチパイプライン・ユニット４０２の何らかの特徴と、パイプライン１０８の何らかの特徴を含むことができる。
【０１３５】
ここで言及する各プロセッサは、様々なコンピュータ・システムの一部に含めることができる。図３８を参照すると、単に一例にすぎないが、プロセッサ５０はコンピュータ・システム４３０の一部にすることができる。システム４３０は第２のプロセッサ４３４も含むことができる。オンチップの第２レベル（Ｌ２）キャッシュはプロセッサ５０内に含まれていてもよい。プロセッサ５０は、プロセッサ・バス４４２を介してメモリ・コントローラ４４０とやりとりすることができる。メモリ・コントローラ４４０はバス４５２および４５４を介してメイン・メモリ４４６および周辺装置４４８とやりとりすることができる。
【０１３６】
パイプライン１０８または３０８（図２および図３）と同様のパイプラインは、レジスタ・リネームを使用しないプロセッサで使用することができるだろう。このような場合、レジスタ・リネームに含まれる構成要素（たとえば、リネーム／割振りユニット１５０）は、リネーム関連特徴を除去するために変更することができるだろう。
【０１３７】
ここに記載し例示した回路および詳細は例示的なものにすぎない。その代わりに様々な他の回路および詳細を使用することができるだろう。さらに、サイズ、待ち時間などの点で、様々な設計上の兼ね合いが存在する可能性がある。たとえば、（たとえば、予約ステーション、レジスタ・ファイル、ＲＯＢ内など）実行経路内のバッファが大きすぎる場合、最大動作クロック周波数は低減しなければならない可能性がある。ここに例示する構成要素は、様々な技法に応じて設計し構築することができる。
【０１３８】
例示した２通りの構造の間に中間構造（バッファなど）または信号が存在する可能性がある。導体によっては、例示したように連続的なものではなく、むしろ中間構造によって分割することができる。図中のボックスの枠は例示のためのものである。実際の装置はこのように定義された境界を備えた構成要素を含まなければならないわけではないだろう。例示した構成要素の相対サイズは実際の相対サイズを示唆するためのものではない。矢印は、所与の実施形態における所与のデータ・フローを示すが、データ要求など、すべての信号を示すわけではない。論理ハイ信号が前述されている場合には論理ロー信号によって置き換えることができ、その逆も可能である。
【０１３９】
プロセッサ内に示した構成要素はすべて同じプロセッサ・チップ上に置くことができる。あるいは、たとえば、トレース・バッファは実行パイプラインとは異なるチップ上に置くことができるだろう。
【０１４０】
「接続」「結合」という用語、ならびに関連用語は直接接続または直接結合に限定されないが、間接接続または間接結合を含むことができる。「応答」という用語および関連用語は、１つの信号または事象がある程度他の信号または事象の影響を受けるが、必ずしも完全または直接的に影響を受けるわけではないことを意味する。ある構成要素を含む「可能性がある」、含む「ことができるだろう」、あるいは含む「ことが好ましい」と本明細書に記載されている場合、その特定の構成要素を含むことが必須であるわけではない。
【０１４１】
ＭＯＢは、予測間違いを検出するためにアドレスの突合せではなくデータの突合せを使用できるだろう。
【０１４２】
本開示の恩恵を受ける当業者は、本発明の範囲内で上記の説明および添付図面から他の多くの変形形態が可能であることが分かるだろう。したがって、本発明の範囲を定義するものは、それに対する補正を含む、特許請求の範囲である。
【図面の簡単な説明】
【図１】  プロセッサの一実施形態における所与の構成要素の高レベル・ブロック図表現である。
【図２】  本発明の一実施形態によるプロセッサのブロック図である。
【図３】  本発明の他の実施形態によるプロセッサのブロック図である。
【図４】  ２つのスレッドの一例を示す流れ図である。
【図５】  ２つのスレッドの他の例を示す流れ図である。
【図６】  ４つのスレッドの一例を示す流れ図である。
【図７】  図６のスレッドのオーバラップ実行を示すグラフである。
【図８】  本発明の一実施形態による個別トレース・バッファを示すブロック図である。
【図９】  ２通りの時点におけるプログラムおよびリタイヤ順序を示すアレイを示す図である。
【図１０】  図８のトレース・バッファの一実施形態における所与の構成要素のブロック図表現である。
【図１１】  図８のトレース・バッファの他の実施形態における所与の構成要素のブロック図表現である。
【図１２】  図１０のトレース・バッファの命令待ち行列アレイの一実施形態の一部分を示す図表表現である。
【図１３】  図１０のトレース・バッファのデータおよび依存関係アレイの一実施形態の一部分を示す図表表現である。
【図１４】  図１０のアレイの依存関係フィールドを作成する際に使用する指標レジスタおよび変更レジスタの一実施形態を示す図である。
【図１５】  図１３のアレイの依存関係フィールドを作成する際に使用する論理ＯＲゲートを示す図である。
【図１６】  図１３のアレイの依存関係フィールドを作成するために使用する操作の一実施形態を示す流れ図である。
【図１７】  本発明の一実施形態によりそれに対する依存関係を有するトレース・バッファ内の位置および特定のレジスタを示す図表表現である。
【図１８】  図１０のトレース・バッファの出力レジスタ・ファイルの一実施形態の一部分を示す図表表現である。
【図１９】  図１０のトレース・バッファの入力レジスタ・ファイルの一実施形態の一部分を示す図表表現である。
【図２０】  本発明の一実施形態による図１８の出力レジスタ・ファイルおよび図１９の入力レジスタ・ファイルとともに使用する比較器および再実施トリガ・ロジックのブロック図である。
【図２１】  出力レジスタ・ファイルの内容を使用できる時点を示す流れ図である。
【図２２】  本発明の一実施形態による図２のメモリ・オーダ・バッファ（ＭＯＢ）内の個別ＭＯＢを示すブロック図である。
【図２３】  図２２のＭＯＢの１つのストア・バッファの一実施形態の一部分を示す図表表現である。
【図２４】  図２２のＭＯＢの１つのロード・バッファの一実施形態の一部分を示す図表表現である。
【図２５】  ロード命令とストア命令のアドレスを比較する比較器を示す図である。
【図２６】  ストア命令とロード命令のアドレスを比較する比較器を示す図である。
【図２７】  本発明の一実施形態によるＭＯＢ制御回路およびストア・バッファを示すブロック図表現である。
【図２８】  本発明の一実施形態によるＭＯＢ制御回路およびロード・バッファを示すブロック図表現である。
【図２９】  ６つのスレッドの一例を示す流れ図である。
【図３０】  時点ｔ１における図２９のスレッド内の関係を示すツリーである。
【図３１】  スレッドＴ１がリタイヤする前にスレッドＴ４がリセットされると想定し、時点ｔ２における図２９のスレッド内の関係を示すツリーである。
【図３２】  スレッドＴ４がリセットされる前にスレッドＴ１がリタイヤすると想定し、時点ｔ２における図２９のスレッド内の関係を示すツリーである。
【図３３】  時点ｔ３における図２９のスレッド内の関係を示すツリーである。
【図３４】  ５つのスレッドを含む一例を示す流れ図である。
【図３５】  時点ｔ１における図３４のスレッド内の関係を示すツリーである。
【図３６】  時点ｔ２における図３４のスレッド内の関係を示すツリーである。
【図３７】  図２のものに代わる実施形態によるプロセッサのブロック図表現である。
【図３８】  図２のプロセッサを含むコンピュータ・システムである。
【図１】
0003971893.tif 000002
【図２】
0003971893.tif 000003
【図３】
0003971893.tif 000004
【図４】
0003971893.tif 000005
【図５】
0003971893.tif 000006
【図６】
0003971893.tif 000007
【図７】
0003971893.tif 000008
【図８】
0003971893.tif 000009
【図９】
0003971893.tif 000010
【図１０】
0003971893.tif 000011
【図１１】
0003971893.tif 000012
【図１２】
0003971893.tif 000013
【図１３】
0003971893.tif 000014
【図１４】
0003971893.tif 000015
【図１５】
0003971893.tif 000016
【図１６】
0003971893.tif 000017
【図１７】
0003971893.tif 000018
【図１８】
0003971893.tif 000019
【図１９】
0003971893.tif 000020
【図２０】
0003971893.tif 000021
【図２１】
0003971893.tif 000022
【図２２】
0003971893.tif 000023
【図２３】
0003971893.tif 000024
【図２４】
0003971893.tif 000025
【図２５】
0003971893.tif 000026
【図２６】
0003971893.tif 000027
【図２７】
0003971893.tif 000028
【図２８】
0003971893.tif 000029
【図２９】
0003971893.tif 000030
【図３０】
0003971893.tif 000031
【図３１】
0003971893.tif 000032
【図３２】
0003971893.tif 000033
【図３３】
0003971893.tif 000034
【図３４】
0003971893.tif 000035
【図３５】
0003971893.tif 000036
【図３６】
0003971893.tif 000037
【図３７】
0003971893.tif 000038
【図３８】
0003971893.tif 000039