(57)【特許請求の範囲】
【請求項１】
データ処理システムにおける、割り当て解除されたロード命令を追跡するための方法であって、
発行キューにおける命令セットの中のロード命令がミスしたかどうかを検出することと、
前記ロード命令のミスに応答して、前記ロード命令をロード・ミス・キューに割り当てることと、
前記ロード命令を前記発行キューから割り当て解除することと、
前記ロード命令についての依存関係エントリが依存行列の発行キュー部分に存在するかどうかを判定することと、
前記ロード命令についての前記依存関係エントリが前記依存行列の前記発行キュー部分に存在することに応答して、前記依存行列の前記発行キュー部分の前記依存関係エントリから、前記ロード命令に依存する依存命令セットを指定するデータを読み取ることと、
前記データを、前記ロード・ミス・キューと関連付けられた前記依存行列のロード・ミス・キュー部分における新しいエントリに書き込むことと、
を含む方法。
【請求項２】
前記検出することは、前記データ処理システム内のプロセッサによって行われ、前記割り当てることと、前記割り当て解除することと、前記判定することと、前記読み取ることと、前記書き込むこととは、前記データ処理システムにおける命令スケジューラによって行われる、請求項１に記載の方法。
【請求項３】
前記発行キューにおける前記命令セットに基づいて、依存アナライザによって前記依存行列を生成することをさらに含み、前記依存行列の前記発行キュー部分は、前記発行キューにおける前記命令セットに含まれる命令間における依存関係についてのエントリを含むものであり、前記依存行列の前記ロード・ミス・キュー部分は、前記発行キューにおける前記命令セットに含まれる命令と、前記ロード・ミス・キューにおける前記ロード命令の間における依存関係についてのエントリを含むものである、請求項１又は請求項２に記載の方法。
【請求項４】
前記ロード・ミス・キューに割り当てられた前記命令セットの中の１つ又は複数の命令に基づいて、命令スケジューラによって前記依存行列に付加的なエントリを割り当てることをさらに含む、請求項３に記載の方法。
【請求項５】
マッパによって前記発行キューにおける前記依存命令セットのキュー位置を追跡することをさらに含む、請求項１乃至請求項４のいずれか１項に記載の方法。
【請求項６】
前記依存行列は、前記発行キューにおける前記命令セットと前記ロード・ミス・キューにおける命令セットとの間の依存関係を追跡する、請求項１乃至請求項５のいずれか１項に記載の方法。
【請求項７】
前記発行キューにおける前記命令セットの中の第２の命令に対するある命令の依存関係が、前記発行キューの外部にある前記第２の命令に対する依存関係に変換される、請求項１乃至請求項６のいずれか１項に記載の方法。
【請求項８】
前記ロード命令の前記ミスは、第１層（Ｌ１）キャッシュにおけるものである、請求項１乃至請求項７のいずれか１項に記載の方法。
【請求項９】
命令スケジューラと、
発行キューと、
ロード・ミス・キューと、
を含むプロセッサであって、前記命令スケジューラは、
前記発行キューにおける命令セットの中のロード命令のミスが前記プロセッサによって検出されたことに応答して、前記ロード命令を前記ロード・ミス・キューに割り当て、
前記ロード命令を前記発行キューから割り当て解除し、
前記ロード命令についての依存関係エントリが依存行列の発行キュー部分に存在するかどうかを判定し、
前記ロード命令についての前記依存関係エントリが前記依存行列の前記発行キュー部分に存在することに応答して、前記依存行列の前記発行キュー部分の前記依存関係エントリから、前記ロード命令に依存する依存命令セットを指定するデータを読み取り、
前記データを、前記ロード・ミス・キューと関連付けられた前記依存行列のロード・ミス・キュー部分における新しいエントリに書き込む、
プロセッサ。
【請求項１０】
前記プロセッサは、依存アナライザをさらに含み、
前記依存アナライザは、前記発行キューにおける前記命令セットに基づいて前記依存行列を生成し、前記依存行列の前記発行キュー部分は、前記発行キューにおける前記命令セットに含まれる命令間における依存関係についてのエントリを含むものであり、前記依存行列の前記ロード・ミス・キュー部分は、前記発行キューにおける前記命令セットに含まれる命令と、前記ロード・ミス・キューにおける前記ロード命令の間における依存関係についてのエントリを含むものである、請求項９に記載のプロセッサ。
【請求項１１】
前記命令スケジューラは、さらに、前記ロード・ミス・キューに割り当てられた前記命令セットの中の１つ又は複数の命令に基づいて、前記依存行列に付加的なエントリを割り当てる、請求項９に記載のプロセッサ。
【請求項１２】
前記プロセッサは、マッパをさらに含み、
前記マッパは、前記発行キューにおける前記依存命令セットのキュー位置を追跡する、請求項９乃至請求項１１のいずれか１項に記載のプロセッサ。
【請求項１３】
前記依存行列は、前記発行キューにおける前記命令セットと前記ロード・ミス・キューにおける命令セットとの間の依存関係を追跡する、請求項９乃至請求項１２のいずれか１項に記載のプロセッサ。
【請求項１４】
前記発行キューにおける前記命令セットの中の第２の命令に対するある命令の依存関係が、前記発行キューの外部にある前記第２の命令に対する依存関係に変換される、請求項９乃至請求項１３のいずれか１項に記載のプロセッサ。
【請求項１５】
プロセッサと、
前記プロセッサに結合されたメモリと、
を備える装置であって、前記メモリは、前記プロセッサによって実行されたときに、前記プロセッサに、
発行キューにおける命令セットの中のロード命令がミスしたかどうかを検出させ、
前記ロード命令のミスに応答して、前記ロード命令をロード・ミス・キューに割り当てさせ、
前記ロード命令を前記発行キューから割り当て解除させ、
前記ロード命令についての依存関係エントリが依存行列の発行キュー部分に存在するかどうかを判定させ、
前記ロード命令についての前記依存関係エントリが前記依存行列の前記発行キュー部分に存在することに応答して、前記依存行列の前記発行キュー部分の前記依存関係エントリから、前記ロード命令に依存する依存命令セットを指定するデータを読み取らせ、
前記データを、前記ロード・ミス・キューと関連付けられた前記依存行列のロード・ミス・キュー部分における新しいエントリに書き込ませる、
命令を含む、装置。
【請求項１６】
前記命令は、さらに、前記プロセッサに、前記発行キューにおける前記命令セットに基づいて前記依存行列を生成させ、前記依存行列の前記発行キュー部分は、前記発行キューにおける前記命令セットに含まれる命令間における依存関係についてのエントリを含むものであり、前記依存行列の前記ロード・ミス・キュー部分は、前記発行キューにおける前記命令セットに含まれる命令と、前記ロード・ミス・キューにおける前記ロード命令の間における依存関係についてのエントリを含むものである、請求項１５に記載の装置。
【請求項１７】
前記命令は、さらに、前記プロセッサに、前記ロード・ミス・キューに割り当てられた前記命令セットの中の１つ又は複数の命令に基づいて前記依存行列に付加的なエントリを割り当てさせる、請求項１６に記載の装置。
【請求項１８】
前記命令は、さらに、前記プロセッサに、前記発行キューにおける前記依存命令セットのキュー位置を追跡させる、請求項１５乃至請求項１７のいずれか１項に記載の装置。
【請求項１９】
前記依存行列は、前記発行キューにおける前記命令セットと前記ロード・ミス・キューにおける命令セットとの間の依存関係を追跡する、請求項１５乃至請求項１８のいずれか１項に記載の装置。
【請求項２０】
前記発行キューにおける前記命令セットの中の第２の命令に対するある命令の依存関係が、前記発行キューの外部にある前記第２の命令に対する依存関係に変換される、請求項１５乃至請求項１９のいずれか１項に記載の装置。
【請求項２１】
コンピュータに請求項１乃至請求項８のいずれか１項に記載の方法を実行させるためのコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、一般に、データ処理装置及び方法の改善に関し、より具体的には、依存行列を用いて割り当て解除されたロード命令を追跡するための装置及び方法に関する。
【背景技術】
【０００２】
マイクロプロセッサは、演算ユニット、キャッシュ・メモリ及びメモリ管理、予測論理、並びにデータ移動を含む特定の機能動作ユニットに編成された何百万ものトランジスタ及び他の素子から構成されるチップであり、現在のコンピュータの心臓部である。現在のコンピュータにおけるプロセッサは、過去十年にわたり、性能、能力、及び複雑性が著しく高まってきた。どのコンピュータ・プログラムも、データを操作するための多数の命令から構成されている。プロセッサは、イン・オーダー・プロセッサとアウト・オブ・オーダー・プロセッサとに分類することができる。
【０００３】
現代の高性能プロセッサにおいては、命令は、アウト・オブ・オーダーで実行されるようにスケジューリングすることができる。命令は、そのソース・オペランドが利用可能となった後で実行されるように、スケジューリングすることができる。既知の動的命令スケジューラは、依存行列（ウェイクアップ・アレイとも呼ばれる）を用いてソース・オペランドを追跡することができる。依存行列は元来、プロセッサにおいて、ロード及びストアの間のメモリ依存関係を追跡する手段として用いるために導入されたもので、発行キューにおけるレジスタ依存関係を追跡するために用いられている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
幾つかの実装形態においては、新しい命令のために場所を空けるように、命令が発行された後にできるだけ早く発行キューから命令を割り当て解除することが望ましい場合がある。しかしながら、既知の依存行列は、プロデューサと関連付けられた命令が発行キュー内にまだ残っている場合には、そのプロデューサの利用可能性のみを追跡する。従って、コンシューマ命令が自分の実行結果の利用可能性をまだ追跡している場合には、命令がキューから割り当て解除されない場合がある。
【課題を解決するための手段】
【０００５】
第１の態様によれば、データ処理システムにおいて、割り当て解除されたロード命令を追跡するための方法が提供され、本方法は、発行キューにおける命令セットの中のロード命令がミスしたかどうかを検出することと、ロード命令のミスに応答して、ロード命令をロード・ミス・キューに割り当てることと、ロード命令を発行キューから割り当て解除することと、ロード命令についての依存関係エントリが依存行列の発行キュー部分に存在するかどうかを判定することと、ロード命令についての依存関係エントリが依存行列の発行キュー部分に存在することに応答して、依存行列の発行キュー部分の依存関係エントリから、ロード命令に依存する依存命令セットを指定するデータを読み取ることと、そのデータを、ロード・ミス・キューと関連付けられた依存行列のロード・ミス・キュー部分における新しいエントリに書き込むこととを含む。
【０００６】
第２の態様によれば、命令スケジューラと、発行キューと、ロード・ミス・キューとを含むプロセッサが提供され、命令スケジューラは、発行キューにおける命令セットの中のロード命令のミスがプロセッサによって検出されたことに応答して、ロード命令をロード・ミス・キューに割り当て、ロード命令を発行キューから割り当て解除し、ロード命令についての依存関係エントリが依存行列の発行キュー部分に存在するかどうかを判定し、ロード命令についての依存関係エントリが依存行列の発行キュー部分に存在することに応答して、依存行列の発行キュー部分の依存関係エントリから、ロード命令に依存する依存命令セットを指定するデータを読み取り、そのデータを、ロード・ミス・キューと関連付けられた依存行列のロード・ミス・キュー部分における新しいエントリに書き込む。
【０００７】
第３の態様によれば、プロセッサと、プロセッサに結合されたメモリとを備える装置が提供され、メモリは、プロセッサによって実行されたときに、プロセッサに、発行キューにおける命令セットの中のロード命令がミスしたかどうかを検出させ、ロード命令のミスに応答して、ロード命令をロード・ミス・キューに割り当てさせ、ロード命令を発行キューから割り当て解除させ、ロード命令についての依存関係エントリが依存行列の発行キュー部分に存在するかどうかを判定させ、ロード命令についての依存関係エントリが依存行列の発行キュー部分に存在することに応答して、依存行列の発行キュー部分の依存関係エントリから、ロード命令に依存する依存命令セットを指定するデータを読み取らせ、そのデータを、ロード・ミス・キューと関連付けられた依存行列のロード・ミス・キュー部分における新しいエントリに書き込ませる、命令を含む。
【０００８】
例示的な実施形態においては、コンピュータ可読プログラムを有するコンピュータ使用媒体又は可読媒体を含むコンピュータ・プログラム製品が提供される。コンピュータ可読プログラムは、コンピュータ・デバイス上で実行されたときに、コンピュータ・デバイスに、本方法に関して上記で概説された種々の操作又は操作の組み合わせを実施させる。
【０００９】
さらに別の実施形態においては、システム／装置が提供される。システム／装置は、１つ又は複数のプロセッサと、１つ又は複数のプロセッサに結合されたメモリとを含むことができる。メモリは命令を含むことができ、命令は、１つ又は複数のプロセッサによって実行されたときに、１つ又は複数のプロセッサに、本方法に関して上記で概説された種々の操作又は操作の組み合わせを実施させる。
【００１０】
本発明のこれら及び他の特徴及び利点は、本発明の例示的な実施形態の以下の詳細な説明において説明され、又は当業者には以下の詳細な説明に照らして明らかであろう。
【図面の簡単な説明】
【００１１】
【図１】例示的な実施形態の態様を実装することができる例示的な分散型データ処理システムの図を示す。
【図２】例示的な実施形態の態様を実装することができる例示的なデータ処理システムのブロック図を示す。
【図３】例示的な実施形態による機能ユニット及びレジスタを示す従来のデュアル・スレッド・プロセッサ設計の例示的なブロック図を示す。
【図４】例示的な実施形態による、依存行列を用いて割り当て解除されたロード命令を追跡する例示的なブロック図を示す。
【図５】例示的な実施形態による例示的な基本依存行列を示す。
【図６】例示的な実施形態による例示的な拡張依存行列を示す。
【図７】例示的な実施形態による、依存行列を用いて割り当て解除されたロード命令を追跡する際に行われる操作についてのフローチャートを示す。
【発明を実施するための形態】
【００１２】
ここでは、本発明の実施形態が、添付の図面を参照して例示のみの目的で説明される。
【００１３】
例示的な実施形態は、ロードが発行キューから割り当て解除される前と後の両方においてロードの結果の利用可能性をロード命令の依存者が追跡できるようにする機構を提供する。例示的な実施形態は、Ｎ行Ｎ列ではなく付加的なＬ列によって拡張される依存行列を提供し、Ｌは、ロード・ミス・キューの中のエントリの数である。ロード命令が、Ｌ１キャッシュにおいてミスしたことが知られ、ロード・ミス・キューに割り当てられているときに、発行キューにおけるそのロード命令のエントリを割り当て解除することができる。ロード命令が割り当て解除されたときには、そのロード命令の依存者の全てをマークしている行列の列が読み取られ、この列は、ロード・ミス・キューのエントリに属する新しい列に書き込まれる。このようにして、例示的な実施形態は、依存命令が依存行列を用いて自らのソース・オペランドの利用可能性を追跡することを可能にしながら、ロード命令の結果が利用可能となる前に発行キューからロード命令を割り当て解除できるようにする。ロード命令の結果が利用可能となる前にロード命令を割り当て解除することによって、新しい命令が発行キューに配置される。キュー利用の増加は、プロセッサ性能を改善する。さらに、例示的な実施形態は、命令が発行キューに配置された後でその命令の依存情報を修正することを可能にするが、このことはこれまで依存行列では不可能であったものであり、即ち、任意の時点における命令のプロデューサの位置は、命令が発行キューに最初に配置されたときにその命令によって追跡されるリソースと同一である場合も異なる場合もある。
【００１４】
当業者であれば分かるように、本発明は、システム、方法、又はコンピュータ・プログラム製品として具体化することができる。従って、本発明は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロ・コードなどを含む）、又は、ソフトウェア及びハードウェアの態様を組み合わせた実施形態の形を取ることができ、本明細書ではその全てを一般的に「回路」、「モジュール」、又は「システム」と呼ぶことがある。さらにまた、本発明は、コンピュータ使用可能プログラム・コードが具体化されたいずれかの有形の表現媒体として具体化されたコンピュータ・プログラム製品の形を取ることができる。
【００１５】
１つ又は複数のコンピュータ使用可能媒体又はコンピュータ可読媒体のいずれの組み合わせも用いることができる。コンピュータ使用可能媒体又はコンピュータ可読媒体は、例えば、電子、磁気、光学、電磁気、赤外線、若しくは半導体のシステム、装置、デバイス又は伝搬媒体とすることができるが、これらに限定されるものではない。コンピュータ可読媒体のより詳細な例（非網羅的なリスト）として、１つ又は複数の配線を有する電気接続、携帯可能コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭ又はフラッシュ・メモリ）、光ファイバ、携帯可能コンパクト・ディスク読み取り専用メモリ（ＣＤＲＯＭ）、光ストレージ・デバイス、インターネット若しくはイントラネットをサポートするような伝送媒体、又は磁気ストレージ・デバイスが挙げられる。例えば、紙又は他の媒体の光学的なスキャンによってプログラムを電気的にキャプチャし、次いで、必要であればそれをコンパイルし、解釈し、又は他の適切な手法で処理し、次いでコンピュータ・メモリに格納することが可能なので、プログラムが印刷された紙又は別の適切な媒体でさえコンピュータ使用可能媒体又はコンピュータ可読媒体となり得ることに留意されたい。本文書の文脈においては、コンピュータ使用可能媒体又はコンピュータ可読媒体は、命令実行システム、装置、若しくはデバイスによって、又はこれらと共に、用いるためのプログラムを含み、格納し、通信し、伝搬し、又は搬送することができるいずれかの媒体とすることができる。コンピュータ使用可能媒体は、ベースバンドにおいて又は搬送波の一部として、コンピュータ使用可能プログラム・コードを具体化した伝搬データ信号を含むことができる。コンピュータ使用可能プログラム・コードは、無線、有線、光ファイバ・ケーブル、無線周波数（ＲＦ）などを含むがこれらに限定されないいずれかの適切な媒体を用いて、伝送することができる。
【００１６】
本発明の操作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ（商標）、ＳｍａｌｌＴａｌｋ（商標）、Ｃ＋＋などのようなオブジェクト指向型プログラミング言語と、「Ｃ」プログラミング言語又は同様のプログラミング言語のような従来の手続き型プログラミング言語とを含む、１つ又は複数のプログラミング言語のいずれかの組み合わせで書くことができる。（Ｊａｖａ及び全てのＪａｖａベースの商標並びにロゴは、米国、その他の国々、又はその両方におけるＳｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ，Ｉｎｃ．の商標であり、他の製品及びサービス名は、ＩＢＭ又は他の会社の商標である。）プログラム・コードは、完全にユーザのコンピュータ上で実行するか、スタンドアロンのソフトウェア・パッケージとして部分的にユーザのコンピュータ上で実行するか、一部はユーザのコンピュータ上で実行し、一部はリモート・コンピュータ上で実行するか、又は、完全にリモート・コンピュータ若しくはサーバ上で実行することができる。後者の場合には、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）又は広域エリア・ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを通じてユーザのコンピュータに接続することができ、又は、（例えば、インターネット・サービス・プロバイダを用いてインターネットを通じて）外部コンピュータに接続することもできる。
【００１７】
例示的な実施形態は、本発明の例示的な実施形態による方法、装置（システム）及びコンピュータ・プログラム製品のフローチャート図及び／又はブロック図を参照して、以下で説明される。フローチャート図及び／又はブロック図の各ブロック、及び、フローチャート図及び／又はブロック図におけるブロックの組み合わせは、コンピュータ・プログラム命令によって実装できることが理解されるであろう。これらのコンピュータ・プログラム命令を汎用コンピュータ、専用コンピュータ、又は他のプログラム可能データ処理装置のプロセッサに与えてマシンを生成、それにより、コンピュータ又は他のプログラム可能データ処理装置のプロセッサによって実行される命令が、フローチャート及び／又はブロック図のブロック又は複数のブロックにおいて指定される機能／動作を実装するための手段を生成するようにしてもよい。
【００１８】
また、これらのコンピュータ命令を、特定の方法で機能するようにコンピュータ又は他のプログラム可能データ処理装置に向けることができるコンピュータ可読媒体に格納し、それにより、そのコンピュータ可読媒体に格納された命令が、フローチャート及び／又はブロック図のブロック又は複数のブロックにおいて指定される機能／動作を実装する命令手段を含む製品を作るようにしてもよい。
【００１９】
また、コンピュータ・プログラム命令をコンピュータ又は他のプログラム可能データ処理装置にロードし、コンピュータ又は他のプログラム可能データ処理装置上で一連の操作ステップを行わせて、コンピュータ実装プロセスを生成し、それにより、コンピュータ又は他のプログラム可能装置上で実行される命令が、フローチャート及び／又はブロック図のブロック又は複数のブロックにおいて指定される機能／動作を実行するためのプロセスを提供するようにしてもよい。
【００２０】
図におけるフローチャート及びブロック図は、本発明の種々の実施形態によるシステム、方法、及びコンピュータ・プログラム製品の可能な実装形態のアーキテクチャ、機能、及び操作を示す。この点に関して、フローチャート又はブロック図の中の各ブロックは、特定の１つ又は複数の論理機能を実装するための１つ又は複数の実行可能命令を含むコードのモジュール、セグメント、又は一部を表すことができる。幾つかの代替的な実装においては、ブロックに記載された機能が図に示される順序通りに行われない場合があることにも留意すべきである。例えば、連続して示される２つのブロックは、関与する機能に応じて、実際には、実質的に同時に実行されることがあり、ブロックが逆順に実行されることもある。ブロック図及び／又はフローチャート図の各ブロック、及び、ブロック図及び／又はフローチャート図におけるブロックの組み合わせは、指定の機能又は動作を行う専用ハードウェア・ベースのシステムによって、又は専用ハードウェアとコンピュータ命令との組み合わせによって、実装できることにも留意されたい。
【００２１】
従って、例示的な実施形態は、分散型データ処理環境、単一のデータ処理デバイスなどを含む多数の異なるタイプのデータ処理環境において利用することができる。例示的な実施形態の特定の要素及び機能の説明のための文脈を提供するために、例示的な実施形態の態様を実装することができる例示的な環境として、後に図１及び図２が提供される。図１及び図２に続く説明は、主として、アウト・オブ・オーダー・プロセッサにおいて、偽の依存関係を用いて命令をイン・オーダーで発行するための単一のデータ処理デバイス実装に焦点を当てることになるが、これは単なる一例であり、本発明の特徴に関していずれかの限定を主張又は意味することを意図するものではない。逆に、例示的な実施形態は、命令がアウト・オブ・オーダー・プロセッサにおいて偽の依存関係を用いてイン・オーダーで命令として発行される分散型データ処理環境及び実施形態を含むように意図されている。
【００２２】
ここで、図、特に図１−図２を参照して、本発明の例示的な実施形態を実装することができるデータ処理環境の例の図が提供される。図１−図２は、単なる例であり、本発明の態様又は実施形態を実装することができる環境に関していずれかの限定を主張又は意味することを意図するものではないことを認識されたい。本発明の精神及び範囲から逸脱することなく、示される環境に対して多くの修正を行うことができる。
【００２３】
ここで図を参照すると、図１は、例示的な実施形態の態様を実装することができる分散型データ処理システムの例の図形表現を示す。分散型データ処理システム１００は、例示的な実施形態の態様を実装することができるコンピュータのネットワークを含むことができる。分散型データ処理システム１００は、少なくとも１つのネットワーク１０２を含み、このネットワーク１０２は、分散型データ処理システム１００内において互いに接続された種々のデバイス及びコンピュータの間の通信リンクを提供するのに用いられる媒体である。ネットワーク１０２は、有線、無線通信リンク、又は光ファイバ・ケーブルといった接続を含むことができる。
【００２４】
示される例においては、サーバ１０４及びサーバ１０６は、ストレージ・ユニット１０８と共にネットワーク１０２に接続される。さらに、クライアント１１０、１１２、及び１１４もまた、ネットワーク１０２に接続される。これらのクライアント１１０、１１２、及び１１４は、例えば、パーソナル・コンピュータ、ネットワーク・コンピュータなどとすることができる。示される例においては、サーバ１０４は、ブート・ファイル、オペレーティング・システム・イメージ、及びアプリケーションといったデータを、クライアント１１０、１１２、及び１１４に提供する。クライアント１１０、１１２、及び１１４は、示される例においてはサーバ１０４のクライアントである。分散型データ処理システム１００は、図示されない付加的なサーバ、クライアント、及び他のデバイスを含むことができる。
【００２５】
示される例においては、分散型データ処理システム１００は、Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ（ＴＣＰ／ＩＰ）のプロトコル・スイートを用いて互いに通信するネットワーク及びゲートウェイのワールドワイドな集積体を表すネットワーク１０２を伴うインターネットである。インターネットの中心にあるのが、データ及びメッセージを送付する何千もの商用システム、行政システム、教育システム、及び他のコンピュータ・システムから成る主要ノード又はホスト・コンピュータの間の高速データ通信線のバックボーンである。言うまでもなく、分散型データ処理システム１００はまた、例えばイントラネット、ローカル・エリア・ネットワーク（ＬＡＮ）、広域エリア・ネットワーク（ＷＡＮ）などといった多数の異なるタイプのネットワークを含むように実装することができる。上記で述べたように、図１は、本発明の異なる実施形態についてのアーキテクチャ上の限定としてではなく、一例として意図されており、従って、図１において示される特定の要素は、本発明の例示的な実施形態を実装することができる環境に関して限定するものであると見なされるべきではない。
【００２６】
ここで図２を参照すると、例示的な実施形態の態様を実装することができるデータ処理システムの例のブロック図が示される。データ処理システム２００は、図１におけるクライアント１１０のようなコンピュータの一例であり、ここに、本発明の例示的な実施形態のプロセスを実装するコンピュータ使用可能コード又は命令を置くことができる。
【００２７】
示される例においては、データ処理システム２００は、ノース・ブリッジ及びメモリ・コントローラ・ハブ（ＮＢ／ＭＣＨ）２０２と、サウス・ブリッジ及び入力／出力（Ｉ／Ｏ）コントローラ・ハブ（ＳＢ／ＩＣＨ）２０４とを含むハブ・アーキテクチャを採用する。処理ユニット２０６、メイン・メモリ２０８、及びグラフィックス・プロセッサ２１０は、ＮＢ／ＭＣＨ２０２に接続される。グラフィックス・プロセッサ２１０は、Ａｃｃｅｌｅｒａｔｅｄ  ｇｒａｐｈｉｃｓ  ｐｏｒｔ（ＡＧＰ）を通じてＮＢ／ＭＣＨ２０２に接続することができる。
【００２８】
示される例においては、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ２１２がＳＢ／ＩＣＨ２０４に接続する。オーディオ・アダプタ２１６、キーボード及びマウス・アダプタ２２０、モデム２２２、読み取り専用メモリ（ＲＯＭ）２２４、ハード・ディスク・ドライブ（ＨＤＤ）２２６、ＣＤ−ＲＯＭドライブ２３０、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ（ＵＳＢ）ポート及び他の通信ポート２３２、並びにＰＣＩ／ＰＣＩｅデバイス２３４は、バス２３８及びバス２４０を通じてＳＢ／ＩＣＨ２０４に接続する。ＰＣＩ／ＰＣＩｅデバイスは、例えば、イーサネット・アダプタ、アドイン・カード、及びノートブック・コンピュータのためのＰＣカードを含むことができる。ＰＣＩがカード・バス・コントローラを用いるのに対し、ＰＣＩｅは用いない。ＲＯＭ２２４は、例えば、フラッシュ型ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ（ＢＩＯＳ）とすることができる。
【００２９】
ＨＤＤ２２６及びＣＤ−ＲＯＭドライブ２３０は、バス２４０を通じてＳＢ／ＩＣＨ２０４に接続する。ＨＤＤ２２６及びＣＤ−ＲＯＭドライブ２３０は、例えば、ｉｎｔｅｇｒａｔｅｄ  ｄｒｉｖｅ  ｅｌｅｃｔｒｏｎｉｃｓ（ＩＤＥ）又はｓｅｒｉａｌ  ａｄｖａｎｃｅｄ  ｔｅｃｈｎｏｌｏｇｙ  ａｔｔａｃｈｍｅｎｔ（ＳＡＴＡ）インターフェースを用いることができる。Ｓｕｐｅｒ  Ｉ／Ｏ（ＳＩＯ）デバイス２３６は、ＳＢ／ＩＣＨ２０４に接続することができる。
【００３０】
オペレーティング・システムは、処理ユニット２０６上で動作する。オペレーティング・システムは、図２におけるデータ処理システム２００内の種々のコンポーネントを調整し、制御を行う。クライアントとして、オペレーティング・システムは、Ｍｉｃｒｏｓｏｆｔ（登録商標）Ｗｉｎｄｏｗｓ（登録商標）ＸＰ（Ｍｉｃｒｏｓｏｆｔ及びＷｉｎｄｏｗｓは、米国及び他の国々又はその両方におけるＭｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎの商標である）のような市販のオペレーティング・システムとすることができる。Ｊａｖａ（商標）プログラミング・システムのようなオブジェクト指向プログラミング・システムは、オペレーティング・システムと共に動作し、データ処理システム２００上で実行されるＪａｖａ（商標）プログラム又はアプリケーションからオペレーティング・システムへの呼び出しを提供することができる（Ｊａｖａは、米国及び他の国々又はその両方におけるＳｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ，Ｉｎｃ．の商標である）。
【００３１】
サーバとして、データ処理システム２００は、例えば、Ａｄｖａｎｃｅｄ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｅｘｅｃｕｔｉｖｅ（ＡＩＸ（登録商標））オペレーティング・システム又はＬＩＮＵＸ（登録商標）オペレーティング・システムを動作させるＩＢＭ（登録商標）ｅＳｅｒｖｅｒ（商標）Ｓｙｓｔｅｍ  ｐ（登録商標）コンピュータ・システムとすることができる（ｅＳｅｒｖｅｒ、Ｓｙｓｔｅｍ  ｐ、及びＡＩＸは、米国及び他の国々又はその両方におけるＩｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎの商標であり、ＬＩＮＵＸは、米国及び他の国々又はその両方におけるＬｉｎｕｓ  Ｔｏｒｖａｌｄｓの商標である）。データ処理システム２００は、処理ユニット２０６に複数のプロセッサを含む対称型マルチプロセッサ（ＳＭＰ）システムとすることができる。代替的に、単一プロセッサ・システムを採用することもできる。
【００３２】
オペレーティング・システム、オブジェクト指向プログラミング・システム、及びアプリケーション又はプログラムのための命令は、ＨＤＤ２２６のようなストレージ・デバイスに置かれ、処理ユニット２０６によって実行するためにメイン・メモリ２０８にロードすることができる。本発明の例示的な実施形態についてのプロセスは、コンピュータ使用可能プログラム・コードを用いて処理ユニット２０６によって実施することができ、コンピュータ使用可能プログラム・コードは、例えばメイン・メモリ２０８、ＲＯＭ２２４のようなメモリ、又は例えば１つ又は複数の周辺デバイス２２６及び２３０に置くことができる
【００３３】
図２に示されるバス２３８又はバス２４０のようなバス・システムは、１つ又は複数のバスから構成することができる。言うまでもなく、バス・システムは、通信ファブリック又はアーキテクチャに取り付けられた異なるコンポーネント又はデバイスの間でデータを転送するいずれかのタイプの通信ファブリック又はアーキテクチャを用いて実装することができる。図２のモデム２２２又はネットワーク・アダプタ２１２のような通信ユニットは、データを送信及び受信するのに用いられる１つ又は複数のデバイスを含むことができる。メモリは、例えば、メイン・メモリ２０８、ＲＯＭ２２４、又は、図２のＮＢ／ＭＣＨ２０２において見られるようなキャッシュとすることができる。
【００３４】
当業者であれば、図１−図２におけるハードウェアは実装形態に応じて変わる場合があることが分かるであろう。図１−図２において示されるハードウェアに加えて、又はその代わりに、フラッシュ・メモリ、等価の不揮発性メモリ、又は光ディスク・ドライブなどのような他の内蔵ハードウェア又は周辺デバイスを用いることができる。また、例示的な実施形態のプロセスは、本発明の精神及び範囲から逸脱することなく、上述されたＳＭＰシステム以外にマルチプロセッサ・データ処理システムにも適用することができる。
【００３５】
さらに、データ処理システム２００は、クライアント・コンピュータ・デバイス、サーバ・コンピュータ・デバイス、タブレット・コンピュータ、ラップトップ・コンピュータ、電話機又は他の通信デバイス、個人用携帯型端末（ＰＤＡ）などを含む多くの異なるデータ処理システムのいずれかの形態を取ることができる。幾つかの例示的な例においては、データ処理システム２００は、例えばオペレーティング・システム・ファイル及び／又はユーザ生成データを格納するための不揮発性メモリを提供するフラッシュ・メモリを用いて構成されるポータブル・コンピュータ・デバイスとすることができる。本質的には、データ処理システム２００は、アーキテクチャ上の限定なしに、任意の既知の又は今後開発されるデータ処理システムとすることができる。
【００３６】
図３を参照すると、例示的な一実施形態による機能ユニット及びレジスタを示す従来のデュアル・スレッド・プロセッサ設計の例示的なブロック図が示される。これらの例示的な例においては、プロセッサ３００は、図２における処理ユニット２０６として実装することができる。プロセッサ３００は、単一スレッド・モードで動作することもできるデュアル・スレッド同時マルチスレッディング（ＳＭＴ）を有する単一の集積回路スーパースカラ・マイクロプロセッサを含む。従って、本明細書において以下でさらに説明されるように、プロセッサ３００は、様々なユニット、レジスタ、バッファ、メモリ、及び他のセクションを含み、それらの全てが集積回路によって形成されている。また、例示的な実施形態においては、プロセッサ３００は、縮小命令セット・コンピュータ（ＲＩＳＣ）技術に従って動作する。
【００３７】
図３において示されるように、命令フェッチ・ユニット（ＩＦＵ）３０２が、命令キャッシュ３０４に接続する。命令キャッシュ３０４は、実行される多数のプログラム（スレッド）についての命令を保持する。命令キャッシュ３０４はまた、レベル２（Ｌ２）キャッシュ／メモリ３０６とのインターフェースを有する。ＩＦＵ３０２は、命令アドレスに従って命令キャッシュ３０４から命令を要求し、命令デコード・ユニット３０８に命令を渡す。例示的な実施形態においては、ＩＦＵ３０２は、命令キャッシュ３０４から、多数の命令を同時に２スレッドまで要求することができる。命令デコード・ユニット３０８は、多数の命令を同時に２スレッドまでデコードし、デコードされた命令を命令ディスパッチ・ユニット（ＩＤＵ）３０９に渡す。
【００３８】
ＩＤＵ３０９が、命令デコード・ユニット３０８からデコードされた命令を受信し、デコードされた命令をスレッドごとに選択的にグループ化することができる。ＩＤＵ３０９は、依存行列を用いて命令と関連付けられたソース・オペランドを追跡する命令スケジューラ３１０に、命令を出力する。ＩＤＵ３０９が、受信した命令の間の依存関係を特定すると、命令スケジューラ３１０は命令を発行キュー３１１に発行し、発行キュー３１１は、スレッドごとの命令グループをプロセッサの実行ユニット３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６、及び３２８に出力又は発行する。ロード命令がＬ１キャッシュ（図示せず）においてミスしたときには、命令スケジューラ３１０は、そのロード命令をロード・ミス・キュー３６０に割り当て、発行キュー３１１から命令を割り当て解除する。命令スケジューラ３１０によって実施されるプロセスの詳細な説明は、以下で詳細に説明される。
【００３９】
例示的な実施形態においては、プロセッサの実行ユニットは、分岐ユニット３１２と、ロード／ストア・ユニット（ＬＳＵＡ）３１４及び（ＬＳＵＢ）３１６と、固定小数点実行ユニット（ＦＸＵＡ）３１８及び（ＦＵＸＢ）３２０と、浮動小数点実行ユニット（ＦＰＵＡ）３２２及び（ＦＰＵＢ）３２４と、ベクトル・マルチメディア拡張ユニット（ＶＭＸＡ）３２６及び（ＶＭＸＢ）３２８とを含むことができる。実行ユニット３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６、及び３２８は、両方のスレッド間で完全に共有されており、これは、実行ユニット３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６、及び３２８がどちらか一方のスレッド又は両方のスレッドから命令を受信できることを意味する。プロセッサは、多数のレジスタ・セット３３０、３３２、３３４、３３６、３３８、３４０、３４２、３４４、及び３４６を含み、これらは、アーキテクチャ化されたレジスタ・ファイル（ＡＲＦ）と呼ばれることもある。
【００４０】
ＡＲＦは、命令が実行を完了したときに完了データが格納されるファイルである。ＡＲＦ３３０、３３２、３３４、３３６、３３８、３４０、３４２、３４４、及び３４６は、２つのスレッドごとに、命令のタイプによってデータを別々に格納することができ、即ち、汎用レジスタ（ＧＰＲ）３３０及び３３２、浮動小数点レジスタ（ＦＰＲ）３３４及び３３６、専用レジスタ（ＳＰＲ）３３８及び３４０、並びにベクトル・レジスタ（ＶＲ）３４４及び３４６である。完了データをタイプ及びスレッドごとに別々に格納することは、命令を処理する際のプロセッサ競合を低減することに役立つ。
【００４１】
プロセッサは、さらに、一方又は両方のスレッドからの命令に対して用いることができる、例えば命令ポインタ、スタック・ポインタ、又はプロセッサ状態ワードのようなプログラム状態を保持するための共有専用レジスタ（ＳＰＲ）３４２を含む。実行ユニット３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６、及び３２８は、簡略化された内部バス構造３４９を通じて、ＡＲＦ３３０、３３２、３３４、３３６、３３８、３４０、３４２、３４４、及び３４６に接続される。
【００４２】
浮動小数点命令を実行するために、命令を実行するのに必要なデータが完了している場合、又はデータがパイプラインのフラッシュ・ポイントを過ぎている場合には、ＦＰＵＡ３２２及びＦＰＵＢ３２４は、命令を実行するのに必要な入力データであるレジスタ・ソース・オペランド情報をＦＰＲ３３４及び３３６から取り出す。完了データは、命令が実行を完了した時点で実行ユニットによって生成され、ＡＲＦ３３０、３３２、３３４、３３６、３３８、３４０、３４２、３４４、及び３４６のようなＡＲＦに格納されるデータである。未完了データは、命令が実行を完了していない命令実行中に生成されたデータである。ＦＰＵＡ３２２及びＦＰＵＢ３２４は、各々の実行している命令がどのスレッドに属するかに応じて自らのデータを入力する。例えば、ＦＰＵＡ３２２、ＦＰＵＢ３２４、及びＦＰＲ３３４並びに３３６はスレッド指定であるため、ＦＰＵＡ３２２は完了データをＦＰＲ３３４に入力し、ＦＰＵＢ３２４は完了データをＦＰＲ３３６に入力する。
【００４３】
命令の実行中に、ＦＰＵＡ３２２及びＦＰＵＢ３２４は、命令がパイプラインのフラッシュ・ポイントを過ぎたときに、自らの宛先レジスタ・オペランド・データ又は命令実行中に生成された命令データを、ＦＰＲ３３４及び３３６に出力する。命令の実行中に、ＦＸＵＡ３１８、ＦＸＵＢ３２０、ＬＳＵＡ３１４、及びＬＳＵＢ３１６は、命令がパイプラインのフラッシュ・ポイントを過ぎたときに、自らの宛先レジスタ・オペランド・データ又は命令実行中に生成された命令データを、ＧＰＲ３３０及び３３２に出力する。命令の実行中に、ＦＸＵＡ３１８、ＦＸＵＢ３２０及び分岐ユニット３１２は、命令がパイプラインのフラッシュ・ポイントを過ぎたときに、自らの宛先レジスタ・オペランド・データを、ＳＰＲ３３８、３４０及び３４２に出力する。命令の実行中に、ＶＭＸＡ３２６及びＶＭＸＢ３２８は、命令がパイプラインのフラッシュ・ポイントを過ぎたときに、自らの宛先レジスタ・オペランド・データを、ＶＲ３４４及び３４６に出力する。
【００４４】
データ・キャッシュ３５０もまた、プロセッサからデータを受け付け、それをレベル２キャッシュ／メモリ３０６に直接書き込む、キャッシュ不可能ユニット（図示せず）と関連付けることができる。このように、キャッシュ不可能ユニットは、キャッシュへの格納に必要なコヒーレンス・プロトコルをバイパスする。
【００４５】
命令キャッシュ３０４から入力され、命令デコード・ユニット３０８によってデコードされた命令に応答して、ＩＤＵ３０９は、命令を、命令タイプ及びスレッドに関して選択的に実行ユニット３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６、及び３２８にディスパッチする。次に、実行ユニット３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６、及び３２８は、特定のクラス又はタイプの命令のうちの１つ又は複数の命令を実行する。例えば、ＦＸＵＡ３１８及びＦＸＵＢ３２０は、レジスタ・ソース・オペランドに、加算、減算、論理積演算、論理和演算、又は排他的論理和演算のような固定小数点数数学演算を実行する。ＦＰＵＡ３２２及びＦＰＵＢ３２４は、レジスタ・ソース・オペランドに、浮動小数点数乗算及び除算のような浮動小数点数数学演算を実行する。ＬＳＵＡ３１４及びＬＳＵＢ３１６は、オペランド・データをデータ・キャッシュ３５０とＡＲＦ３３０、３３２、３３４、及び３３６との間で移動させるロード及びストア命令を実行する。ＶＭＸＡ３２６及びＶＭＸＢ３２８は、多数のデータを含む単一の命令演算を実行する。分岐ユニット３１２は、命令キャッシュ３０４から命令を要求するためにＩＦＵ３０２によって用いられる命令アドレスを修正することによって、プログラムを通して実行の流れを条件付きで変更する分岐命令を実行する。
【００４６】
ＩＤＵ３０９は、同時に実行されるように命令デコード・ユニット３０８によってデコードされた命令を、デコードされた命令と、各々の命令について必要な演算を行うのに利用可能な実行ユニット３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６、及び３２８との組み合わせに応じて、グループ化する。例えば、ロード／ストア・ユニット３１４及び３１６が２つしか存在しないため、最大で２つのロード／ストア・タイプの命令をグループ化することができる。例示的な一実施形態においては、最大で７つの命令をグループ化する（２つの固定小数点数算術演算、２つのロード／ストア、３つの浮動小数点数算術演算又は２つのベクトル・マルチメディア拡張、及び１つの分岐）ことができ、同一のスレッドには最大で５つの命令が属することができる。ＩＤＵ３０９は、優先順位の低いスレッドからの命令をグループに含める前に、優先順位の高いスレッドから可能な限り多く、最大で５つまでの命令を、グループに含める。スレッドの優先順位は、スレッドの優先順位値とそのプロセスの優先順位クラスとによって決定される。処理システムは、全ての実行可能スレッドのベース優先順位レベルを用いて、どのスレッドを次のプロセッサ時間に割り当てるかを決定する。命令スケジューラ３１０は、各々の優先順位レベルにおいてスレッドをラウンドロビン方式でスケジューリングし、より高いレベルに実行可能スレッドが存在しないときにのみ、より低いレベルのスレッドのスケジューリングが行われる。
【００４７】
しかしながら、ＩＤＵ３０９は、ＦＸＵ命令３１８及び３２０と同一のグループ内にあるＦＰＵ命令３２２及び３２４又はＶＭＸ命令３２６及び３２８をディスパッチする。即ち、ＩＤＵ３０９は、同一のグループ内にあるＦＰＵ命令３２２及び３２４とＶＭＸ命令３２６及び３２８とをディスパッチすることはない。ＳＰＲ３３８及び３４０に格納された、例えば命令ポインタ、スタック・ポインタ、又はプロセッサ状態ワードのようなプログラム状態は、スレッドの優先順位３５２をＩＤＵ３０９に示す。
【００４８】
命令完了ユニット３５４は、内部バス構造３４９を監視して、実行ユニット３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６、及び３２８において実行される命令がいつオペランドの結果をＡＲＦ３３０、３３２、３３４、３３６、３３８、３４０、３４２、３４４、及び３４６に書き込むのを終了したかを判断する。分岐ユニット３１２、ＦＸＵＡ３１８、ＦＸＵＢ３２０、ＬＳＵＡ３１４、及びＬＳＵＢ３１６によって実行される命令は、実行するのに同じ数のサイクルを必要とするが、一方、ＦＰＵＡ３２２、ＦＰＵＢ３２４、ＶＭＸＡ３２６、及びＶＭＸＢ３２８によって実行される命令は、変数を必要とし、従って、実行するのにより多くの数のサイクルを必要とする。従って、グループ化され、同時に実行を開始する命令は、必ずしも同時に実行を終了するとは限らない。命令の「完了」は、命令が実行ユニット３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６、又は３２８において実行を終了しつつあること、フラッシュ・ポイントを過ぎていること、命令は順序通りに完了される必要があるため全ての古い命令はアーキテクチャ化された状態で既に更新されていること、を意味する。よって、このとき命令は、完了してアーキテクチャ化された状態で更新される準備ができており、このことは、命令が完了されたときにデータの最終状態を更新することを意味する。アーキテクチャ化された状態は、順序通りにのみ更新され、即ち、命令は、ディスパッチされた順序で完了される必要があり、完了されたデータは、次の命令が最新の完了データを用いるように、各々の命令が完了されたときに更新される必要がある。
【００４９】
命令完了ユニット３５４は、命令の完了を監視し、制御情報３５６をＩＤＵ３０９に送信して、更に多くの命令のグループを実行ユニット３１２、３１４、３１６、３１８、３２０、３２２、３２４、３２６、及び３２８にディスパッチできることをＩＤＵ３０９に通知する。ＩＤＵ３０９は、更に多くの命令がパイプラインを下ってＩＤＵ３０９にもたらされるためのスロットルとして機能するディスパッチ信号３５８を、ＩＦＵ３０２及び命令デコード・ユニット３０８に送信して、更に多くのデコードされた命令を受信する準備ができたことを示す。
【００５０】
図４は、例示的な一実施形態による、依存行列を用いて割り当て解除されたロード命令を追跡する例示的なブロック図を示す。命令スケジューラ４０２は、命令ディスパッチ・ユニット４０４から命令を受信し、ソース・オペランド、即ち命令の実行に用いられるデータを追跡するために、依存アナライザ４０６を用いて依存行列を生成する。依存行列は、ロード及びストアの間のメモリの依存関係と、発行キュー４０８における命令からの追跡レジスタの依存関係とを追跡する。図５は、例示的な一実施形態による例示的な基本依存行列を示す。基本依存行列５００においては、Ｎ個の行５０２とＮ個の列５０４とが存在し、ここでＮは発行キュー４０８における命令の数である。発行キュー４０８において実行を待っている命令ごとに１つの行が存在する。所与の行及び列について、行列の行及び列におけるビットが「１」である場合には、行における命令は、列における命令の結果の利用可能性に依存する。実行ユニットのような他のリソース間の依存関係を示すために、付加的な列が存在することもある。例えば、図５においては、行３における加算命令５０６は、行１におけるレジスタｒ５のロード５０８の結果に依存する。従って、命令スケジューラ４０２は、ロード命令を表す列１、加算命令を表す行３のビットを、「１」に更新する。
【００５１】
図４に戻ると、新しい命令のための空きを作るために、命令が発行された後にできるだけ迅速に命令を発行キュー４０８から割り当て解除することが望ましいが、図５の基本依存行列５００のような従来の依存行列に伴う１つの不利な点は、命令が、プロデューサが発行キュー４０８内にまだ置かれている場合にはそのプロデューサの利用可能性のみを追跡することである。従って、コンシューマ命令、即ち以前の命令の結果に依存する命令が、自らの結果の利用可能性を依然として追跡している場合には、命令スケジューラ４０２は、命令を発行キュー４０８から割り当て解除しない可能性がある。
【００５２】
例示的な実施形態は、ロード命令の依存者が、ロードが発行キューから割り当て解除される前後の両方においてロードの結果の利用可能性を追跡できるようにする方法を説明する。従って、依存アナライザ４０６は、Ｎ個の行とＮ＋Ｌ個の列とを含む依存行列４１４を生成し、ここでＮは発行キュー４０８における命令の数であり、Ｌはロード・ミス・キュー４１０における命令の数である。発行キュー４０８がロード命令を発行し、そのロード命令が第１レベル（Ｌ１）のデータ・キャッシュにおいてミスした場合には、ロード・ミス・キュー４１０が、そのロード命令についてのエントリを割り当てる。依存行列４１４において、行４１８における命令４１６が、例えば発行キューと関連付けられた列４２０における１によって示される、命令４２６に対する依存性のような依存関係を有する場合には、命令スケジューラ４０２は、列４２０において示される依存関係を割り当て解除し、その依存関係をロード・ミス・キューと関連付けられた列４２２に割り当てる。即ち、命令スケジューラ４０２は、ロード命令４２６と関連付けられた依存関係を示す列内のすべてのエントリを読み取り、その依存関係を、依存行列４１４のロード・ミス・キューと関連付けられた関連する列４２２に書き込む。この例において、そのエントリは矢印４２４によって示される。
【００５３】
図６は、例示的な一実施形態による例示的な拡張依存行列を示す。拡張依存行列は、ロードが発行キューに割り当てられている間、及び、ロード・ミスの場合にロード命令が発行キューから割り当て解除されてロード・ミス・キューに割り当てられた後に、ロード命令の依存者がロード命令の結果の利用可能性を追跡できるようにする方法を提供する。拡張依存行列６００においては、Ｎ−１個の行６０２と、発行キュー４０８及びロード・ミス・キュー４１０と関連付けられたＮ＋Ｌ−１個の列６０４とが存在する。上記の例を続けると、行３における加算命令６０６は、行１におけるレジスタｒ５のロード６０８の結果に依存する。発行キュー４０８がロード命令６０８を発行し、ロード命令６０８が第１レベル（Ｌ１）データ・キャッシュにおいてミスした場合には、命令スケジューラ４０２は、ロード命令６０８についての関連エントリを列６１０から割り当て解除し、そのエントリを、拡張依存行列６００におけるロード・ミス・キューと関連付けられた列６１２に割り当てる。即ち、命令スケジューラ４０２は、依存関係を有するロード命令が特定された拡張依存行列６００における列６１０のエントリを読み取り、そのエントリを、矢印６１４によって示される、拡張依存行列６００の列Ｎ＋ｋ１６１２に書き込む。このように、例示的な実施形態においては、発行キューにおける第２の命令に対するある命令の依存関係は、発行キューの外部にある第２の命令に対する依存関係に変換される。
【００５４】
図４に戻ると、命令スケジューラ４０２はまた、発行キュー４０８において待機中の全ての命令のキュー位置を追跡するマッパ４１２を含むこともできる。命令スケジューラ４０２が、最初に命令を発行キュー４０８に割り当てたときに、命令は、マッパ４１２を読み取ることによって自らのソース・オペランドの位置を得る。命令スケジューラ４０２が、ロード命令をロード・ミス・キュー４１０に割り当てるために、ロード命令を発行キュー４０８から割り当て解除したときには、マッパ４１２は、そのロード命令の発行キュー・エントリをロード・ミス・キュー・エントリと置き換える。
【００５５】
図７は、例示的な一実施形態による、依存行列を用いて割り当て解除されたロード命令を追跡する際に行われる操作についてのフローチャートを示す。操作が開始するとき、プロセッサは、ロード命令が第１層（Ｌ１）キャッシュにおいてミスしたことを検出する（ステップ７０２）。ステップ７０２において、プロセッサがミスを検出するのに失敗した場合には、操作はステップ７０２に戻る。ステップ７０２において、プロセッサが、ロード命令がＬ１キャッシュにおいてミスしたと判断した場合には、命令スケジューラは、ロード命令をロード・ミス・キューに割り当てる（ステップ７０４）。次いで、命令スケジューラは、ロード命令を発行キューから割り当て解除する（ステップ７０６）。
【００５６】
次いで、命令スケジューラは、依存行列の発行キュー部分においてロード命令についての依存関係エントリが存在するかどうかを判断する（ステップ７０８）。ステップ７０８において、命令スケジューラが、依存行列の発行キュー部分においてロード命令についての依存関係エントリが存在しないと判断した場合には、操作はステップ７０２に戻る。ステップ７０８において、命令スケジューラが、依存行列の発行キュー部分においてロード命令についての依存関係エントリが存在すると判断した場合には、命令スケジューラは、依存行列のロード命令と関連付けられた列から、どの命令がロード命令に依存するかを指定するデータを読み取る（ステップ７１０）。次いで、命令スケジューラは、そのデータを、ロード・ミス・キューと関連付けられた依存行列のロード命令と関連する新しい列に書き込み（ステップ７１２）、操作はその後ステップ７０２に戻る。
【００５７】
このように、例示的な実施形態は、ロードが発行キューから割り当て解除される前後の両方において、ロード命令の依存者がロードの結果の利用可能性を追跡できるようにする機構を提供する。例示的な実施形態は、Ｎ行Ｎ列の代わりにＬ個の付加的な列によって拡張される依存行列を提供し、ここでＬはロード・ミス・キューにおけるエントリの数である。ロード命令が、Ｌ１キャッシュにおいてミスしたことが知られ、ロード・ミス・キューに割り当てられているときには、そのロード命令の発行キューにおけるエントリを割り当て解除することができる。ロード命令が割り当て解除されたときには、そのロード命令の依存者の全てをマークしている行列の列が読み取られ、この列は、ロード・ミス・キュー・エントリに属する新しい列に書き込まれる。
【００５８】
例示的な実施形態は、依存している命令が依存行列を用いて自らのソース・オペランドの利用可能性を追跡することを可能にしながら、ロード命令の結果が利用可能となる前に、発行キューからロード命令を割り当て解除できるようにする。結果が利用可能となる前にロード命令を割り当て解除することによって、新しい命令が発行キューに置かれる。キュー利用の増加によって、プロセッサ性能が改善される。さらに、例示的な実施形態は、命令が発行キューに置かれた後でその命令の依存情報を修正することを可能にするが、このことは、以前は依存行列では不可能であった。即ち、任意の時点における命令のプロデューサの位置は、命令が発行キューに最初に置かれたときにその命令によって追跡されるリソースと同一の場合も異なる場合もある。
【００５９】
上記に記されたように、例示的な実施形態は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態、又はハードウェア要素とソフトウェア要素の両方を含む実施形態の形を取ることができることを認識されたい。１つの例示的な実施形態においては、例示的な実施形態の機構は、ファームウェア、常駐ソフトウェア、マイクロ・コードなどを含むがこれらに限定されない、ソフトウェア又はプログラム・コードに実装される。
【００６０】
プログラム・コードを格納及び／又は実行するのに適したデータ処理システムは、システム・バスを通してメモリ要素に直接又は間接に接続された少なくとも１つのプロセッサを含む。メモリ要素は、プログラム・コードの実際の実行中に用いられるローカル・メモリと、大容量記憶装置と、実行中に大容量記憶装置からコードを取得しなければならない回数を減らすために少なくとも幾つかのプログラム・コードの一時的な記憶場所を提供するキャッシュ・メモリとを含むことができる。
【００６１】
入出力デバイス即ちＩ／Ｏデバイス（キーボード、ディスプレイ、ポインティング・デバイスなどを含むがこれらに限定されない）は、システムに、直接的に、又は介在するＩ／Ｏコントローラを通して、結合することができる。データ処理システムが、介在するプライベート・ネットワーク又は公開ネットワークを通じて他のデータ処理システム又は遠隔プリンタ若しくはストレージ装置に結合されることを可能にするために、ネットワーク・アダプタをシステムに結合することもできる。モデム、ケーブル・モデム、及びイーサネット・カードは、現時点で利用可能なネットワーク・アダプタのタイプのうちのごく一部である。
【００６２】
本発明の説明は、例示及び説明を目的として提示されており、網羅的であることも、開示された形態の発明に限定されることも、意図されていない。当業者には、多くの修正及び変形が明らかであろう。本実施形態は、本発明の原理及び実際の用途を最も良く説明するために、並びに、考慮される特定の用途に適した種々の修正を伴う種々の実施形態について当業者以外が本発明を理解できるように、選択され説明されたものである。
【図１】
0005474176.tif 000002
【図２】
0005474176.tif 000003
【図３】
0005474176.tif 000004
【図４】
0005474176.tif 000005
【図５】
0005474176.tif 000006
【図６】
0005474176.tif 000007
【図７】
0005474176.tif 000008