(57)【特許請求の範囲】
【請求項１】
少なくとも１つのレベル１（Ｌ１）キャッシュを含むデータをキャッシュするための複数のキャッシュレベルの階層と、
１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断するキャッシュ占有決定ロジックと、
前記１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かの前記判断に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングするスケジューリングロジックとを備え、
前記キャッシュ占有決定ロジックは、前記１または複数の後続のオペレーションに関連する前記データが格納される特定の前記キャッシュレベルを更に決定し、
前記スケジューリングロジックは、
前記１または複数の後続のオペレーションに関連する前記データが格納される特定の前記キャッシュレベルの前記決定に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングし、
キャッシュ階層において比較的低次のデータおよび／またはキャッシュレベルにないデータを用いた複数のオペレーションの前に、前記キャッシュ階層において比較的高次のデータを用いた複数のオペレーションをスケジューリングする、プロセッサ。
【請求項２】
前記キャッシュ占有決定ロジックは、前記１または複数の後続のオペレーションに関連する前記データが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断するためのキャッシュ占有命令を実行する実行ロジックを含む、請求項１に記載のプロセッサ。
【請求項３】
前記キャッシュ占有命令は、前記１または複数の後続のオペレーションに関連する前記データに関連する１または複数のアドレスを読み取り、前記データが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断するべく、前記１または複数のアドレスを用いるための命令である、請求項２に記載のプロセッサ。
【請求項４】
前記１または複数のアドレスを用いることは、前記１または複数のアドレスを用いたキャッシュ検索オペレーションを実行することを含む、請求項３に記載のプロセッサ。
【請求項５】
前記キャッシュ占有決定ロジックは、前記データにアクセスするのに予期される時間、および指定閾値に基づいた前記データが遠すぎるか否かの表示のうち少なくとも１つを更に決定する、請求項１から４のいずれか１項に記載のプロセッサ。
【請求項６】
前記スケジューリングロジックは、前記決定された、前記データにアクセスするのに予期される時間、および指定閾値に基づいた、前記データが遠すぎるか否かの表示のうち少なくとも１つに基づいて、前記１または複数の後続のオペレーションをスケジューリングする、請求項５に記載のプロセッサ。
【請求項７】
前記複数のキャッシュレベルは、レベル２（Ｌ２）キャッシュおよび低次のレベルのキャッシュ（ＬＬＣ）を更に含む、請求項１から６のいずれか１項に記載のプロセッサ。
【請求項８】
少なくとも１つのレベル１（Ｌ１）キャッシュを含む複数のキャッシュレベルの階層内にデータをキャッシュする段階と、
１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断する段階と、
前記１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かの前記判断に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングする段階とを備え、
前記判断する段階は、
前記１または複数の後続のオペレーションに関連する前記データが格納される特定の前記キャッシュレベルを決定する段階を有し、
前記スケジューリングする段階は、
前記１または複数の後続のオペレーションに関連する前記データが格納される特定の前記キャッシュレベルの前記決定に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングする段階を有し、
前記１または複数の後続のオペレーションに関連する前記データが格納される特定の前記キャッシュレベルの前記決定に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングする段階は、キャッシュ階層において比較的低次のデータおよび／またはキャッシュレベルにないデータを用いた複数のオペレーションの前に、前記キャッシュ階層において比較的高次のデータを用いた複数のオペレーションをスケジューリングする段階を含む、方法。
【請求項９】
前記１または複数の後続のオペレーションに関連する前記データが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断するためのキャッシュ占有命令を実行する段階を更に備える、請求項８に記載の方法。
【請求項１０】
前記キャッシュ占有命令は、前記１または複数の後続のオペレーションに関連する前記データに関連する１または複数のアドレスを読み取り、前記データが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断するべく、前記１または複数のアドレスを用いるための命令である、請求項９に記載の方法。
【請求項１１】
１または複数のアドレスを用いる段階は、前記１または複数のアドレスを用いたキャッシュ検索オペレーションを実行する段階を備える、請求項１０に記載の方法。
【請求項１２】
前記データにアクセスするのに予期される時間、および指定閾値に基づいた前記データが遠すぎるか否かの表示のうち少なくとも１つを決定する段階を更に備える、請求項８から１１のいずれか１項に記載の方法。
【請求項１３】
前記決定された、前記データにアクセスするのに予期される時間、および指定閾値に基づいた、前記データが遠すぎるか否かの表示のうち少なくとも１つに基づいて、前記１または複数の後続のオペレーションをスケジューリングする段階を更に備える、請求項１２に記載の方法。
【請求項１４】
前記複数のキャッシュレベルは、レベル２（Ｌ２）キャッシュおよび低次のレベルのキャッシュ（ＬＬＣ）を更に含む、請求項８から１３のいずれか１項に記載の方法。
【請求項１５】
システムであって、
プログラムコードおよびデータを格納するためのメモリと、
１または複数の周辺機器デバイスと通信するための入力／出力（ＩＯ）通信インターフェースと、
前記システムをネットワークに通信可能に結合するためのネットワーク通信インターフェースと、
プロセッサとを備え、
前記プロセッサは、
少なくとも１つのレベル１（Ｌ１）キャッシュを含む、データをキャッシュするための複数のキャッシュレベルの階層と、
１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断する、キャッシュ占有決定ロジックと、
前記１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かの前記判断に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングするスケジューリングロジックとを有し、
前記キャッシュ占有決定ロジックは、前記１または複数の後続のオペレーションに関連する前記データが格納される特定の前記キャッシュレベルを更に決定し、
前記スケジューリングロジックは、
前記１または複数の後続のオペレーションに関連する前記データが格納される特定の前記キャッシュレベルの前記決定に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングし、
キャッシュ階層において比較的低次のデータおよび／またはキャッシュレベルにないデータを用いた複数のオペレーションの前に、前記キャッシュ階層において比較的高次のデータを用いた複数のオペレーションをスケジューリングする、システム。
【発明の詳細な説明】
【背景技術】
【０００１】
本発明は、概ね、コンピュータプロセッサの分野に関する。より具体的には、本発明は、キャッシュ占有決定および命令スケジューリングのための装置および方法に関する。
【０００２】
動作を実行することを必要とするデータがキャッシュに格納されていないと、メモリからデータを取得するべく相当な量の時間（例えば、マイクロプロセッサのサイクル）を費やさなければならないので、データキャッシュミスは、プログラムコードの非効率的な実行をもたらすことになる。この問題に対する以前の１つの解決法は、明示的なアーキテクチャサポートが提供され、必要とされることになるデータを予期して当該データをキャッシュにプリフェッチする、データプリフェッチである。別の解決法は、いずれの特別なアーキテクチャサポートまたはインタラクションも用いることなく、メモリ内のデータ構造のレイアウトをどのように最適化するかを決定するキャッシュを意識しないアルゴリズムおよびキャッシュを認識するアルゴリズムを用いることである。
【図面の簡単な説明】
【０００３】
本発明のより良い理解は、以下の図面と併せて以下の詳細な説明から得られることができる。
【０００４】
【図１Ａ】本発明の複数の実施形態による、例示的なインオーダパイプライン、および例示的なレジスタリネーム、アウトオブオーダ発行／実行パイプラインの双方を図示するブロック図である。
【０００５】
【図１Ｂ】本発明の複数の実施形態による、プロセッサに含まれるインオーダアーキテクチャコアの例示的な実施形態、および例示的なレジスタリネーム、アウトオブオーダ発行／実行アーキテクチャコアの双方を図示するブロック図である。
【図２】本発明の複数の実施形態による統合メモリコントローラおよびグラフィックを有するシングルコアプロセッサおよびマルチコアプロセッサのブロック図である。
【図３】本発明の一実施形態によるシステムのブロック図を図示する。
【図４】本発明の一実施形態による第２のシステムのブロック図を図示する。
【図５】本発明の一実施形態による第３のシステムのブロック図を図示する。
【図６】本発明の一実施形態による、システムオンチップ（ＳｏＣ）のブロック図を図示する。
【図７】本発明の複数の実施形態による、ソース命令セットのバイナリ命令を変換するソフトウェア命令変換器の使用と、ターゲット命令セットのバイナリ命令とを対比するブロック図を図示する。
【図８】キャッシュ占有を決定するためのロジックを有するアーキテクチャの一実施形態を図示する。
【図９】キャッシュ占有を決定し、決定に基づいて後の動作を実行する方法の一実施形態を図示する。
【０００６】
【図１０】キャッシュ占有を決定し、決定に基づいて作業待ち行列から作業項目を実行する方法の一実施形態を図示する。
【発明を実施するための形態】
【０００７】
以下の説明において、説明の目的のために、後述される本発明の複数の実施形態の完全な理解を提供するべく、様々な具体的詳細が記載される。しかし、当業者には、本発明の複数の実施形態がこれらの具体的な詳細のいくつかを用いることなく実施され得ることが明らかであろう。本発明の複数の実施形態の基礎となる原理を不明瞭にするのを避けるべく、複数の他の例において、周知の複数の構造およびデバイスがブロック図の形態で示される。
【０００８】
例示的なプロセッサアーキテクチャおよびデータタイプ
図１Ａは、本発明の複数の実施形態による、例示的なインオーダパイプライン、および例示的なレジスタリネーム、アウトオブオーダ発行／実行パイプラインの双方を図示するブロック図である。図１Ｂは、本発明の複数の実施形態による、プロセッサに含まれるインオーダアーキテクチャコアの例示的な実施形態、および例示的なレジスタリネーム、アウトオブオーダ発行／実行アーキテクチャコアの双方を図示するブロック図である。図１Ａ〜図１Ｂにおける実線で囲まれた複数のボックスは、インオーダパイプラインおよびインオーダコアを図示するが、複数の破線ボックスの任意選択の追加により、レジスタリネーム、アウトオブオーダ発行／実行パイプライン、およびコアを図示する。インオーダ態様がアウトオブオーダ態様のサブセットであると仮定して、アウトオブオーダ態様が説明される。図１Ａにおいて、プロセッサパイプライン１００は、フェッチステージ１０２、長さデコードステージ１０４、デコードステージ１０６、割り当てステージ１０８、リネームステージ１１０、スケジューリングステージ１１２（ディスパッチもしくは発行ステージとしても既知）、レジスタ読み取り／メモリ読み取りステージ１１４、実行ステージ１１６、ライトバック／メモリライトステージ１１８、例外処理ステージ１２２、およびコミットステージを含む。
【０００９】
図１Ｂは、実行エンジンユニット１５０に結合されたフロントエンドユニット１３０を含む。双方は、メモリユニット１７０に結合されたプロセッサコア１９０を示す。コア１９０は、縮小命令セットコンピューティング（ＲＩＳＣ）コア、複合命令セットコンピューティング（ＣＩＳＣ）コア、超長命令語（ＶＬＩＷ）コア、またはハイブリッドもしくは代替的なコアタイプであってもよい。なおも別の選択肢において、コア１９０は、例えば、ネットワークもしくは通信コア、圧縮エンジン、コプロセッサコア、汎用コンピューテインググラフィクス処理ユニット（ＧＰＧＰＵ）コア、グラフィックコア等の専用コアであってもよい。
【００１０】
フロントエンドユニット１３０は、命令キャッシュユニット１３４に結合される分岐予測ユニット１３２を含む。命令キャッシュユニット１３４は、命令変換索引バッファ（ＴＬＢ）１３６に結合される。ＴＬＢ１３６は、命令フェッチユニット１３８に結合される。命令フェッチユニット１３８は、デコードユニット１４０に結合される。デコードユニット１４０（またはデコーダ）は、複数の命令をデコードし、出力として１もしくは複数のマイクロオペレーション、マイクロコードエントリーポイント、マイクロ命令、他の命令、または他の制御信号を生成することができ、これらは、複数の元の命令からデコードされ、またはこれらを反映し、あるいはこれらから派生する。デコードユニット１４０は、様々な異なるメカニズムを用いて実装され得る。好適なメカニズムの例としては、ルックアップテーブル、ハードウェア実装、プログラマブルロジックアレイ（ＰＬＡ）、マイクロコードリードオンリメモリ（ＲＯＭ）等が挙げられるが、これらに限定されない。一実施形態において、コア１９０は、複数の一定のマクロ命令に対するマイクロコードを（例えば、デコードユニット１４０またはフロントエンドユニット１３０内に）格納する、マイクロコードＲＯＭまたは他の媒体を含む。デコードユニット１４０は、実行エンジンユニット１５０内のリネーム／アロケータユニット１５２に結合される。
【００１１】
実行エンジンユニット１５０は、リタイアメントユニット１５４および１もしくは複数のスケジューラユニット１５６のセットに結合されたリネーム／アロケータユニット１５２を含む。スケジューラユニット１５６は、複数のリザベーションステーション、中央命令ウィンドウ等を含む、任意の数の異なるスケジューラを表す。スケジューラユニット１５６は、物理レジスタファイルユニット１５８に結合される。物理レジスタファイルユニット１５８の各々は、１または複数の物理レジスタファイルを表し、それらのうちの異なるものが、スカラ整数、スカラ浮動小数点、パックド整数、パックド浮動小数点、ベクトル整数、ベクトル浮動小数点、状態（例えば、実行される次の命令のアドレスである命令ポインタ）等、１または複数の異なるデータタイプを格納する。一実施形態において、物理レジスタファイルユニット１５８は、複数のベクトルレジスタユニット、ライトマスクレジスタユニット、およびスカラレジスタユニットを備える。これらのレジスタユニットは、複数のアーキテクチャベクトルレジスタ、ベクトルマスクレジスタ、および汎用レジスタを提供し得る。物理レジスタファイルユニット１５８は、リタイアメントユニット１５４と重なり、レジスタリネームおよびアウトオブオーダ実行が（例えば、リオーダバッファおよびリタイアメントレジスタファイルを用いることにより、フューチャファイル、履歴バッファ、およびリタイアメントレジスタファイルを用いることにより、複数のレジスタのレジスタマップおよびプール等を用いることにより）実装され得る様々な様式を図示する。リタイアメントユニット１５４および物理レジスタファイルユニット１５８は、実行クラスタ１６０に結合される。実行クラスタ１６０は、１もしくは複数の実行ユニット１６２のセット、および１もしくは複数のメモリアクセスユニット１６４のセットを含む。複数の実行ユニット１６２は、様々なオペレーション（例えば、シフト、加算、減算、乗算）を、様々なタイプのデータ（例えば、スカラ浮動小数点、パックド整数、パックド浮動小数点、ベクトル整数、ベクトル浮動小数点）に対して実行し得る。いくつかの実施形態は、複数の特定の関数または複数のセットの関数に専用のいくつかの実行ユニットを含み得るが、他の実施形態は、１つのみ実行ユニットまたは複数の実行ユニットを含み、それらの全てがあらゆる関数を実行し得る。スケジューラユニット１５６、物理レジスタファイルユニット１５８、および実行クラスタ１６０は、場合によっては複数であるものとして示される。これは、複数の一定の実施形態が特定の複数のタイプのデータ／オペレーションのための複数の別個のパイプラインを作成するからである（例えば、各々が、自身のスケジューラユニット、物理レジスタファイルユニット、および／または実行クラスタを有する、スカラ整数パイプライン、スカラ浮動小数点／パックド整数／パックド浮動小数点／ベクトル整数／ベクトル浮動小数点パイプライン、および／またはメモリアクセスパイプライン。別個のメモリアクセスパイプラインの場合には、このパイプラインの実行クラスタのみがメモリアクセスユニット１６４を有する複数の一定の実施形態が実装される）。別個の複数のパイプラインが使用される場合、これらのパイプラインのうち１または複数は、アウトオブオーダ発行／実行であり、残余はインオーダであり得ることを理解されたい。
【００１２】
複数のメモリアクセスユニット１６４のセットは、メモリユニット１７０に結合される。メモリユニット１７０は、データＴＬＢユニット１７２を含む。データＴＬＢユニット１７２は、データキャッシュユニット１７４に結合される。データキャッシュユニット１７４は、レベル２（Ｌ２）キャッシュユニット１７６に結合される。例示的な一実施形態において、複数のメモリアクセスユニット１６４は、ロードユニット、ストアアドレスユニット、およびストアデータユニットを含み得、その各々がメモリユニット１７０内のデータＴＬＢユニット１７２に結合される。命令キャッシュユニット１３４は、メモリユニット１７０におけるレベル２（Ｌ２）キャッシュユニット１７６に更に結合される。Ｌ２キャッシュユニット１７６は、１または複数の他のレベルのキャッシュに、そして最終的にはメインメモリに結合される。
【００１３】
例として、例示的なレジスタリネーム、アウトオブオーダ発行／実行コアアーキテクチャは、パイプライン１００を以下のように実装し得る。１）命令フェッチ１３８は、フェッチおよび長さデコードステージ１０２および１０４を実行する。２）デコードユニット１４０はデコードステージ１０６を実行する。３）リネーム／アロケータユニット１５２は、割り当てステージ１０８およびリネームステージ１１０を実行する。４）スケジューラユニット１５６は、スケジューリングステージ１１２を実行する。５）物理レジスタファイルユニット１５８およびメモリユニット１７０は、レジスタ読み取り／メモリ読み取りステージ１１４を実行し、実行クラスタ１６０は、実行ステージ１１６を実行する。６）メモリユニット１７０および物理レジスタファイルユニット１５８は、ライトバック／メモリライトステージ１１８を実行する。７）様々なユニットは、例外処理ステージ１２２に関与してもよく、８）リタイアメントユニット１５４および物理レジスタファイルユニット１５８は、コミットステージ１２４を実行する。
【００１４】
コア１９０は、本明細書において説明される命令を含む、１または複数の命令セット（例えば、ｘ８６命令セット（複数のより新しいバージョンを追加された、いくつかの拡張を伴う）、カリフォルニア州サニーベールのＭＩＰＳ  ＴｅｃｈｎｏｌｏｇｙのＭＩＰＳ命令セット、カリフォルニア州サニーベールのＡＲＭ  ＨｏｌｄｉｎｇのＡＲＭ命令セット（ＮＥＯＮ等の複数の任意選択の追加拡張を伴う）をサポートし得る。一実施形態において、コア１９０は、パックドデータ命令セット拡張（例えば、ＡＶＸ１、ＡＶＸ２、および／または後述されるいくつかの形態の一般的ベクトルフレンドリ命令フォーマット（Ｕ＝０および／またはＵ＝１））をサポートし、それによりパックドデータを用いて実行される多くのマルチメディアアプリケーションにより用いられる複数の動作を可能にする、ロジックを含む。
【００１５】
コアは、マルチスレッド化（２もしくはそれより多い並列セットのオペレーションもしくはスレッドを実行する）をサポートし、タイムスライスマルチスレッド化、同時マルチスレッド化（１つの物理コアが、物理コアが同時に、マルチスレッド化する複数のスレッドの各々に対する論理コアを提供する）、またはそれらの組み合わせ（例えば、タイムスライスフェッチおよびデコード、ならびにインテル（登録商標）ハイパースレッディング技術等における以後の同時マルチスレッド化）を含む様々な様式でサポートし得ることを理解されたい。
【００１６】
レジスタリネームは、アウトオブオーダ実行の文脈において説明されるが、レジスタリネームは、インオーダアーキテクチャにおいて用いられ得ることを理解されたい。プロセッサの図示される実施形態は、別個の命令および複数のデータキャッシュユニット１３４／１７４、ならびに共有Ｌ２キャッシュユニット１７６も含むが、複数の代替的な実施形態は、例えば、レベル１（Ｌ１）内部キャッシュまたは内部キャッシュの複数のレベル等、複数の命令およびデータの双方に対する１つの内部キャッシュを有し得る。いつかの実施形態において、システムは、内部キャッシュおよびコアおよび／またはプロセッサの外部にある外部キャッシュの組み合わせを含みえる。あるいは、キャッシュの全てがコアおよび／またはプロセッサの外部にあってもよい。
【００１７】
図２は、本発明の複数の実施形態による、２以上のコアを有し、統合メモリコントローラを有し、また統合グラフィックスを有し得るプロセッサ２００のブロック図である。図２において実線で囲まれた複数のボックスは、シングルコア２０２Ａと、システムエージェント２１０と、１もしくは複数のバスコントローラユニット２１６のセットとを有するプロセッサ２００を図示するが、破線で囲まれた複数のボックスの任意選択の追加は、複数のコア２０２Ａ〜Ｎと、システムエージェントユニット２１０内の１または複数の統合メモリコントローラユニット２１４のセットと、特定用途用ロジック２０８とを有する代替的プロセッサ２００を図示する。
【００１８】
従って、プロセッサ２００の複数の異なる実装は、１）統合グラフィックスおよび／または科学的（スループット）ロジック（１または複数のコアを含み得る）である特定用途用ロジック２０８、および１または複数の汎用コア（例えば、汎用インオーダコア、汎用アウトオブオーダコア、２つの組み合わせ）である複数のコア２０２Ａ〜Ｎを用いるＣＰＵ、２）主にグラフィックスおよび／または科学的（スループット）用の多数の特定用途用コアである複数のコア２０２Ａ〜Ｎを用いるコプロセッサ、および３）多数の汎用インオーダコアである複数のコア２０２Ａ〜Ｎを用いるコプロセッサを含み得る。従って、プロセッサ２００は、例えば、ネットワークもしくは通信プロセッサ、圧縮エンジン、グラフィクスプロセッサ、ＧＰＧＰＵ（汎用グラフィクス処理ユニット）、ハイスループットの多集積コア（ＭＩＣ）コプロセッサ（３０もしくはそれよりも多いコアを含む）、エンベデッドプロセッサ等の汎用プロセッサ、コプロセッサまたは特定用途用プロセッサであってもよい。プロセッサは１または複数のチップ上に実装され得る。プロセッサ２００は、１または複数の基板の一部であってもよく、および／または、例えばＢｉＣＭＯＳ、ＣＭＯＳ、またはＮＭＯＳ等、いくつかの処理技術のうちのいずれかを用いてそれらの上に実装されてもよい。
【００１９】
メモリ階層は、複数の統合メモリコントローラユニット２１４のセットに結合される複数のコア、セットまたは１もしくは複数の共有キャッシュユニット２０６、および外部メモリ（図示せず）内に１もしくは複数のレベルのキャッシュを含む。複数の共有キャッシュユニット２０６のセットは、レベル２（Ｌ２）、レベル３（Ｌ３）、レベル４（Ｌ４）等の１または複数の中間レベルのキャッシュ、他の複数のレベルのキャッシュ、最後のレベルのキャッシュ（ＬＬＣ）、および／またはこれらの組み合わせを含み得る。一実施形態において、リングベースの相互接続ユニット２１２は、統合グラフィックスロジック２０８、複数の共有キャッシュユニット２０６のセット、およびシステムエージェントユニット２１０／統合メモリコントローラユニット２１４を相互接続し、複数の代替的な実施形態は、そのような複数のユニットを相互接続する、任意の数の周知技術を使用し得る。一実施形態において、コヒーレンシは、１もしくは複数のキャッシュユニット２０６と複数のコア２０２Ａ〜Ｎとの間で維持される。いくつかの実施形態において、コア２０２Ａ〜Ｎのうちの１または複数は、マルチスレッディングが可能である。
【００２０】
システムエージェント２１０は、コア２０２を調整して動作させる複数のコンポーネントを含む。システムエージェントユニット２１０は、例えば、電力制御ユニット（ＰＣＵ）およびディスプレイユニットを含み得る。ＰＣＵは、複数のコア２０２Ａ〜Ｎおよび統合グラフィックスロジック２０８の電力状態を調整するのに必要とされるロジックおよび複数のコンポーネントであってもよく、またはこれらを含んでもよい。ディスプレイユニットは、１または複数の外部接続されたディスプレイを駆動するためのものである。
【００２１】
複数のコア２０２Ａ〜Ｎは、アーキテクチャ命令セットの面で同種または異種であってよい。すなわち、コア２０２Ａ〜Ｎのうちの２またはそれよりも多いコアは、同一の命令セットを実行し得るが、他のものは、その命令セットまたは異なる命令セットのサブセットのみを実行し得る。一実施形態において、複数のコア２０２Ａ〜Ｎは、異種であり、後述される複数の「小さい」コアおよび複数の「大きい」コアの双方を含む。
【００２２】
図３〜図６は、例示的なコンピュータアーキテクチャのブロック図である。ラップトップ、デスクトップ、ハンドヘルド型ＰＣ、携帯情報端末、工学ワークステーション、サーバ、ネットワークデバイス、ネットワークハブ、スイッチ、エンベデッドプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、グラフィックデバイス、ビデオゲームデバイス、セットトップボックス、マイクロコントローラ、携帯電話、ポータブルメディアプレーヤ、ハンドヘルドデバイス、および様々な他の電子デバイスの技術分野において既知の他の複数のシステム設計および構成も好適である。一般に、本明細書において開示されるプロセッサおよび／または他の実行ロジックを組み込むことができる多種多様なシステムまたは電子デバイスに対して、概ね適用可能である。
【００２３】
ここで図３を参照すると、本発明の一実施形態によるシステム３００のブロック図が示される。システム３００は、１または複数のプロセッサ３１０、３１５を含み、１または複数のプロセッサ３１０、３１５は、コントローラハブ３２０に結合され得る。一実施形態において、コントローラハブ３２０は、グラフィックスメモリコントローラハブ（ＧＭＣＨ）３９０および入力／出力ハブ（ＩＯＨ）３５０（複数の別個のチップ上にあり得る）を含む。ＧＭＣＨ３９０は、メモリコントローラおよびグラフィックスコントローラを含み、これらにメモリ３４０およびコプロセッサ３４５が結合される。ＩＯＨ３５０は、入力／出力（Ｉ／Ｏ）デバイス３６０をＧＭＣＨ３９０に結合する。あるいは、メモリおよび複数のグラフィックスコントローラの一方または双方は、（本明細書において説明されるように）プロセッサ内に統合され、メモリ３４０およびコプロセッサ３４５は、プロセッサ３１０に直接に結合され、シングルチップ内のコントローラハブ３２０は、ＩＯＨ３５０と結合される。
【００２４】
複数の追加のプロセッサ３１５の任意選択の性質は、図３内の複数の破線で示される。各プロセッサ３１０、３１５は、本明細書において説明される複数の処理コアのうち１または複数を含み、いくつかのバージョンのプロセッサ２００であり得る。
【００２５】
メモリ３４０は、例えば、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、相変化メモリ（ＰＣＭ）、または２つの組み合わせであってよい。少なくとも１つの実施形態については、コントローラハブ３２０は、フロントサイドバス（ＦＳＢ）等のマルチドロップバス、ＱｕｉｃｋＰａｔｈ相互接続（ＱＰＩ）等のポイントツーポイントインターフェース、または類似の接続３９５を介してプロセッサ３１０、３１５と通信する。
【００２６】
一実施形態において、コプロセッサ３４５は、例えば、ハイスループットＭＩＣプロセッサ、ネットワークもしくは通信プロセッサ、圧縮エンジン、グラフィクスプロセッサ、ＧＰＧＰＵ、エンベデッドプロセッサ等の特定用途用プロセッサである。一実施形態において、コントローラハブ３２０は、統合グラフィックスアクセラレータを含み得る。
【００２７】
アーキテクチャ、マイクロアーキテクチャ、熱、電力消費の複数の特性等を含む、様々な性能の測定基準の観点において、物理リソース３１０、３１５の間には様々な差異が存在し得る。
【００２８】
一実施形態において、プロセッサ３１０は、通常のタイプの複数のデータ処理オペレーションを制御する複数の命令を実行する。複数のコプロセッサ命令が、複数の命令に埋め込まれ得る。プロセッサ３１０は、取り付けられたコプロセッサ３４５により実行されるべきタイプであるものとして、これらのコプロセッサ命令を認識する。従って、プロセッサ３１０は、コプロセッサバスまたは他の相互接続上で、これらのコプロセッサ命令（または複数のコプロセッサ命令を表す複数の制御信号）をコプロセッサ３４５に発行する。コプロセッサ３４５は、複数の受信済みコプロセッサ命令を受け取り、実行する。
【００２９】
ここで図４を参照すると、本発明の一実施形態による、第１のより具体的な例示的なシステム４００のブロック図が示される。図４に示されるように、マルチプロセッサシステム４００は、ポイントツーポイント相互接続システムであり、第１のプロセッサ４７０、およびポイントツーポイント相互接続４５０を介して結合される第２のプロセッサ４８０を含む。プロセッサ４７０および４８０の各々は、いくつかのバージョンのプロセッサ２００であり得る。本発明の一実施形態において、プロセッサ４７０および４８０は各々、プロセッサ３１０および３１５であるが、コプロセッサ４３８は、コプロセッサ３４５である。別の実施形態において、プロセッサ４７０および４８０は各々、プロセッサ３１０およびコプロセッサ３４５である。
【００３０】
統合メモリコントローラ（ＩＭＣ）ユニット４７２および４８２を各々含む、プロセッサ４７０および４８０が示される。また、プロセッサ４７０は、その複数のバスコントローラユニットの一部として、ポイントツーポイント（Ｐ―Ｐ）インターフェース４７６および４７８を含む。同様に、第２のプロセッサ４８０は、Ｐ―Ｐインターフェース４８６および４８８を含む。プロセッサ４７０、４８０は、複数のＰ―Ｐインターフェース回路４７８、４８８を用いて、ポイントツーポイント（Ｐ―Ｐ）インターフェース４５０を介して情報を交換し得る。図４に示されるように、ＩＭＣ４７２および４８２は、複数のプロセッサを各メモリ、すなわち、メモリ４３２およびメモリ４３４に結合させるが、メモリ４３２およびメモリ４３４は、各プロセッサにローカルに取り付けられたメインメモリの一部であり得る。
【００３１】
プロセッサ４７０、４８０は各々、ポイントツーポイントインターフェース回路４７６、４９４、４８６、４９８を用いて、個々のＰ―Ｐインターフェース４５２、４５４を介してチップセット４９０と情報を交換し得る。チップセット４９０は、任意選択で、高性能インターフェース４３９を介してコプロセッサ４３８と情報を交換してもよい。一実施形態において、コプロセッサ４３８は、例えば、ハイスループットＭＩＣプロセッサ、ネットワークもしくは通信プロセッサ、圧縮エンジン、グラフィクスプロセッサ、ＧＰＧＰＵ、エンベデッドプロセッサ等の特定用途用プロセッサである。
【００３２】
共有キャッシュ（図示せず）は、どちらかのプロセッサ内または双方のプロセッサの外側に含まれるが、Ｐ―Ｐ相互接続を介して複数のプロセッサとなおも接続され得、従って、プロセッサが低電力モードに置かれると、どちらかまたは双方のプロセッサのローカルキャッシュ情報は、共有キャッシュ内に格納され得る。
【００３３】
チップセット４９０は、インターフェース４９６を介して第１のバス４１６に結合され得る。一実施形態において、第１のバス４１６は、周辺構成要素相互接続（ＰＣＩ）バス、またはＰＣＩ  Ｅｘｐｒｅｓｓバスまたは別の第３世代Ｉ／Ｏ相互接続バス等のバスであり得るが、本発明の範囲は、そのようには限定されない。
【００３４】
図４に示されるように、様々なＩ／Ｏデバイス４１４は、第１のバス４１６を第２のバス４２０に結合するバスブリッジ４１８と共に第１のバス４１６に結合され得る。一実施形態において、コプロセッサ、ハイスループットＭＩＣプロセッサ、ＧＰＧＰＵ、アクセラレータ（例えば、グラフィックスアクセラレータまたはデジタル信号処理（ＤＳＰ）ユニット等）、フィールドプログラマブルゲートアレイ、またはその他のプロセッサ等、１または複数の追加のプロセッサ４１５は、第１のバス４１６に結合される。一実施形態において、第２のバス４２０は、低ピンカウント（ＬＰＣ）バスであり得る。様々なデバイスは、一実施形態において、例えば、キーボードおよび／またはマウス４２２、通信デバイス４２７、ならびに複数の命令／コードおよびデータ４３０を含み得るディスクドライブもしくは他の大容量ストレージデバイス等のストレージユニット４２８を含む第２のバス４２０に結合され得る。更に、オーディオＩ／Ｏ４２４は、第２のバス４２０に結合されてもよい。他の複数のアーキテクチャが可能であることに留意されたい。例えば、図４のポイントツーポイントアーキテクチャに代えて、システムは、マルチドロップバスまたは他のそのようなアーキテクチャを実装してもよい。
【００３５】
ここで図５を参照すると、本発明の一実施形態による、第２のより具体的な例示的なシステム５００のブロック図が示される。図４および図５における複数の同一の要素は、複数の同一の参照番号を有し、図４の複数の一定の態様は、図５の他の複数の態様を不明瞭にするのを避けるべく、図５から省略されている。
【００３６】
図５は、プロセッサ４７０、４８０が統合メモリおよびＩ／Ｏ制御ロジック（「ＣＬ」）４７２および４８２を各々含み得ることを図示する。従って、ＣＬ４７２、４８２は、統合メモリコントローラユニットを含み、Ｉ／Ｏ制御ロジックを含む。図５は、メモリ４３２、４３４のみが制御ロジック４７２、４８２に結合されるのみならず、複数のＩ／Ｏデバイス５１４もＣＬ４７２、４８２に結合されることを図示する。複数のレガシＩ／Ｏデバイス５１５は、チップセット４９０に結合される。
【００３７】
ここで図６を参照すると、本発明の実施形態による、ＳｏＣ６００のブロック図が示される。図２における複数の類似の要素は、同一の参照番号を有する。また、複数の破線ボックスは、より高度なＳｏＣにおける複数の任意選択の特徴である。図６において、相互接続ユニット６０２は、１もしくは複数のコア２０２Ａ〜Ｎおよび共有キャッシュユニット２０６のセットを含むアプリケーションプロセッサ６１０、システムエージェントユニット２１０、バスコントローラユニット２１６、統合メモリコントローラユニット２１４、統合グラフィックスロジック、画像プロセッサ、オーディオプロセッサ、およびビデオプロセッサを含み得るコプロセッサ６２０のセットまたは１もしくは複数、スタティックランダムアクセスメモリ（ＳＲＡＭ）ユニット６３０、ダイレクトメモリアクセス（ＤＭＡ）ユニット６３２、および１または複数の外部ディスプレイを結合するディスプレイユニット６４０に結合される。一実施形態において、コプロセッサ６２０は、例えば、ネットワークもしくは通信プロセッサ、圧縮エンジン、ＧＰＧＰＵ、ハイスループットＭＩＣプロセッサ、エンベデッドプロセッサ等の特定用途用プロセッサを含む。
【００３８】
本明細書において開示されるメカニズムの複数の実施形態は、ハードウェア、ソフトウェア、ファームウェア、またはそのような複数の実装アプローチの組み合わせで実装され得る。本発明の複数の実施形態は、少なくとも１つのプロセッサ、ストレージシステム（揮発性および不揮発性メモリ、ならびに／または複数のストレージ要素を含む）、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスを有する複数のプログラマブルシステム上で実行する複数のコンピュータプログラムまたはプログラムコードとして実装され得る。
【００３９】
図４で図示されるコード４３０等のプログラムコードは、複数の命令を入力し、本明細書において説明される複数の関数を実行し、出力情報を生成するべく適用され得る。出力情報は、既知の様式で、１または複数の出力デバイスに適用され得る。本願において、処理システムは、例えば、デジタル信号プロセッサ（ＤＳＰ）、マイクロコントローラ、特定用途向け集積回路（ＡＳＩＣ）、またはマイクロプロセッサ等のプロセッサを有するいずれのシステムも含む。
【００４０】
プログラムコードは、処理システムと通信するべく、ハイレベルプロシージャ型またはオブジェクト指向プログラミング言語で実装されてもよい。また、プログラムコードは、所望であれば、アセンブリ言語または機械言語で実装されてもよい。実際には、本明細書において説明される複数のメカニズムは、範囲において、いずれの特定のプログラミング言語にも限定されない。いずれの場合にも、言語は、コンパイル型言語またはインタープリタ型言語であってもよい。
【００４１】
少なくとも１つの実施形態の１または複数の態様は、プロセッサ内の様々なロジックを表す機械可読媒体上に格納された複数の代表的命令により実装され得、複数の代表的命令は、機械により読み取られると、機械に、本明細書において説明される複数の技術を実行するロジックを作成させる。「ＩＰコア」として既知のそのような複数の表現は、有形機械可読媒体上に格納され、様々な顧客、または実際にロジックまたはプロセッサを作製する複数の製造機械にロードする複数の製造設備に提供され得る。
【００４２】
そのような機械可読記憶媒体としては、ハードディスク、フロッピー（登録商標）ディスク、光ディスク、コンパクトディスクリードオンリメモリ（ＣＤ―ＲＯＭ）、書き換え可能コンパクトディスク（ＣＤ―ＲＷ）、および光磁気ディスク等、その他のタイプのディスクを含む記憶媒体、リードオンリメモリ（ＲＯＭ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）等のランダムアクセスメモリ（ＲＡＭ）、消去可能プログラマブルリードオンリメモリ（ＥＰＲＯＭ）、フラッシュメモリ、電気的消去可能プログラマブルリードオンリメモリ（ＥＥＰＲＯＭ）、および相変化メモリ（ＰＣＭ）等の半導体デバイス、磁気もしくは光カード、または複数の電子命令を格納するのに好適なその他のタイプの媒体を含む、機械またはデバイスにより製造または形成される、非一時的で有形な複数の構成の物品が挙げられ得るが、これらに限定されない。
【００４３】
従って、本発明の複数の実施形態は、本明細書において説明される複数の構造、回路、装置、プロセッサ、および／またはシステムの特徴を定義する、ハードウェア記述言語（ＨＤＬ）等の複数の命令または設計データを格納する、非一時的で有形の機械可読媒体も含む。そのような複数の実施形態は、プログラム製品とも呼ばれ得る。
【００４４】
いくつかの場合に、命令変換器は、ソース命令セットからターゲット命令セットに、命令を変換するべく使用され得る。例えば、命令変換器は、命令を、コアにより処理される１または複数の他の命令にトランスレート（例えば、静的バイナリトランスレーション、動的コンパイルを含む動的バイナリトランスレーションを用いる）、モーフィング、エミュレート、または変換し得る。命令変換器は、ソフトウェア、ハードウェア、ファームウェア、またはこれらの組み合わせで実装され得る。命令変換器は、プロセッサ上にあってもよく、プロセッサから離れてもよく、または一部がプロセッサ上にあり、一部がプロセッサから離れてもよい。
【００４５】
図７は、本発明の複数の実施形態による、ソース命令セットのバイナリ命令を変換するソフトウェア命令変換器の使用と、ターゲット命令セットのバイナリ命令とを対比するブロック図を図示する。図示される実施形態において、命令変換器は、ソフトウェア命令変換器であるが、別法では、命令変換器は、ソフトウェア、ファームウェア、ハードウェア、またはこれらの様々な組み合わせで実装され得る。図７は、ｘ８６コンパイラ７０４を用いてコンパイルされ、少なくとも１つのｘ８６命令セットコアを用いるプロセッサ７１６によりネイティブに実行され得るｘ８６バイナリコード７０６を生成し得る、ハイレベル言語７０２のプログラムを示す。少なくとも１つのｘ８６命令セットコアを用いるプロセッサ７１６は、少なくとも１つのｘ８６命令セットコアを用いるインテル（登録商標）プロセッサと実質的に同一の結果を実現するべく、（１）インテル（登録商標）ｘ８６命令セットコアの命令セットの実質的部分、または（２）少なくとも１つのｘ８６命令セットコアを用いるインテル（登録商標）プロセッサ上で起動することを目的とする、複数のオブジェクトコードバージョンの複数のアプリケーションまたは他のソフトウェアを互換的に実行または処理することにより、少なくとも１つのｘ８６命令セットコアを用いるインテル（登録商標）プロセッサと実質的に同一の複数の機能を実行し得るいずれのプロセッサも表す。ｘ８６コンパイラ７０４は、追加のリンケージ処理を用い、もしくは用いずに、少なくとも１つのｘ８６命令セットコア７１６を用いるプロセッサ上で実行され得る、ｘ８６バイナリコード７０６（例えば、オブジェクトコード）を生成するように動作可能なコンパイラを表す。
【００４６】
同様に、図７は、代替的な命令セットのコンパイラ７０８を用いてコンパイルされ、少なくとも１つのｘ８６命令セットコアを用いないプロセッサ７１４（例えば、カルフォルニア州サニーベールのＭＩＰＳ  ＴｅｃｈｎｏｌｏｇｙのＭＩＰＳ命令セットを実行し、および／またはカリフォルニア州サニーベールのＡＲＭ  ＨｏｌｄｉｎｇのＡＲＭ命令セットを実行する複数のコアを用いるプロセッサ）によりネイティブに実行され得る、代替的な命令セットバイナリコード７１０を生成し得る、ハイレベル言語７０２のプログラムを示す。命令変換器７１２は、ｘ８６バイナリコード７０６を、ｘ８６命令セットコア７１４を用いないプロセッサによりネイティブに実行され得るコードに変換するべく、使用される。この変換済みコードは、代替的な命令セットバイナリコード７１０と同一である可能性が高くない。これを行うことができる命令変換器は、作製するのが困難なためである。しかし、変換済みコードは、汎用オペレーションを遂行し、代替的な命令セットの複数の命令からなるであろう。従って、命令変換器７１２は、エミュレーション、シミュレーション、またはその他の処理により、ｘ８６命令セットプロセッサまたはコアを有しないプロセッサまたは他の電子デバイスがｘ８６バイナリコード７０６を実行することを可能にする、ソフトウェア、ファームウェア、ハードウェア、またはこれらの組み合わせを表す。
【００４７】
キャッシュ占有決定および命令スケジューリングのための装置および方法
本発明の一実施形態は、データに関連するアドレスを用いて、データの項目が現在、キャッシュに格納されているか否かを判断し、この判断に基づいて１または複数の後続のオペレーション（例えば、マクロ命令、マイクロオペレーション等）をスケジューリングする。「スケジューリング」という用語は、本明細書において広範に用いられ、作業の特定部分があるスレッドから別のスレッド（例えば、スレッドが以下の例に説明される複数の他のスレッドの作業待ち行列から作業をスティールするように見える場合の）に再割り当てすることができるか否かに関する決定を含めて、特定の命令、マイクロオペレーションが実行されるべきか否か、および／またはいつ実行されるべきかに関する任意の決定を指す。
【００４８】
データがキャッシュであるか否かを判断することに加えて、一実施形態は、データが格納される特定のキャッシュレベル（例えば、レベル１（Ｌ１）、レベル２（Ｌ３）、より低次レベルのキャッシュ（ＬＬＣ）等）の表示、（例えば、プロセッササイクルにおける）データにアクセスするのに必要とされる予期される量の「時間」の表示、および／または（例えば、プロセッササイクルの閾値番号を用いる）指定レベルの探索によると、アドレスが「遠すぎる」か否かについての表示も提供し得る。
【００４９】
本発明の一実施形態は、入力をアドレスとして受け取り、アドレスにより識別されたデータ項目が現在キャッシュされているか否かについての表示を提供する命令として実装され得る。以下に詳細に検討されるように、この命令の複数の結果は、実行の後続の複数の命令（例えば、複数のアドレスがキャッシュされる複数の命令を選択する）をスケジューリングする場合に用いられ得る。例として、この「キャッシュ占有決定」命令は、以下の形式を取り得る。
INC ACHE SRC1. DST1
データのアドレスは、ソースレジスタＳＲＣ１内に格納され、判断の複数の結果（すなわち、データがキャッシュされているか否か、どのレベルで、予期されるアクセス「時間」、アドレスが「遠すぎる」ことの表示等）がデスティネーションレジスタＤＳＴ１に書き込まれる。
【００５０】
一実施形態において、キャッシュ占有決定命令は、（例えば、単一のベクトルレジスタが複数のアドレスオペランドを格納し得る）１もしくは複数のベクトルソースレジスタから複数のアドレスを読み取り、複数の結果を１もしくは複数のベクトルデスティネーションレジスタを書き込む（例えば、単一のベクトルデスティネーションレジスタは、複数の結果を格納する）アドバンストベクトルエクステンション（ａｄｖａｎｃｅｄ  ｖｅｃｔｏｒ  ｅｘｔｅｎｓｉｏｎ、ＡＶＸ）またはＡＶＸ２命令等のベクトル命令である。しかし、本発明の基礎となる原理は、ベクトル実装に限定されないことに留意されたい。
【００５１】
図８に図示されるように、一実施形態において、プロセッサにおける実行ロジック８３０は、本明細書において説明される複数のキャッシュ占有決定オペレーションを実行する、キャッシュ占有決定ロジック８００を含む。例えば、ＩＮＣＡＣＨＥ命令の実行に応答してキャッシュ占有決定ロジック８００は、１または複数のアドレス８０１が複数のキャッシュレベル８１０―８１２のうち１つに現在格納されているデータに関連するか否かを判断し得る。上述のように、複数の結果８０２は、この情報、ならびに特定のキャッシュレベルの表示、（例えば、プロセッササイクルにおける）アクセスするのに予期される時間、および／または（例えば、複数のプロセッササイクルの指定閾値に基づいた）アドレスが遠すぎることの表示を含み得る。一実施形態において、判断は、アドレスを用いて（例えば、アドレスもしくはアドレスの一部を既存の複数のキャッシュタグと比較する）キャッシュ検索オペレーションを実行することにより行われる。
【００５２】
一実施形態において、複数の結果８０２が判断されると、後続の複数のオペレーションの実行をスケジューリングするスケジューリングロジック８２０により用いられ得る。例えば、ＬＩキャッシュに格納されたデータを用いる複数のオペレーションがまず実行されてもよく、この後にＬ２キャッシュに格納されたデータを伴う複数のオペレーションが続き、この後にキャッシュ階層の更に下（例えば、低次レベルのキャッシュ（ＬＬＣ）または他のより低いキャッシュレベルのストア）の複数のオペレーションが続く。図８に具体的には示されないが、スケジューリングロジック８２０は、プロセッサもしくはコアの命令デコードステージ（例えば、リザベーションステーションもしくは他のスケジューリングユニット）内に実装され得る。
【００５３】
一実施形態において、命令は、後続のオペレーションの示唆として機能する。アドレスに関連するキャッシュラインは、命令が戻された後（例えば、後続のオペレーションがデータを必要とするまでに）キャッシュから追い出され、その結果を古いとみなし得る。そのような場合には、性能のみが影響され、既知の技術を用いてアドレスは、キャッシュに単に戻される。
【００５４】
一実施形態において、命令は、キャッシュラインをキャッシュ８１０〜８１２に保持することを試みることができる。例えば、占有決定ロジック８００により実行される検索は、キャッシュライン（例えば、少なくとも最近用いられた（ＬＲＵ）ポリシ、または他の追い出しポリシに対するものであり、またはラインがどのくらい長くキャッシュ内に留まり／どのくらい最近用されたかの表示を提供する）を用いるものとして扱われ、後続の命令により用いられるのに十分長く、ラインがキャッシュ内に維持される確率を高め得る。
【００５５】
上述のように、次いで、後続の複数の命令および／またはスレッドの実行をスケジューリングするべく、キャッシュ占有命令により提供された情報（例えば、キャッシュにあるか否か、キャッシュレベル等）が用いられ得る。例えば、キャッシュ占有命令は、作業待ち行列の周囲でサイクルさせる作業待ち行列アルゴリズムを含み（しかしこれに限定されない）、イタレーション毎に作業の項目を抽出して処理し、場合によっては追加の複数の項目を用いて作業待ち行列を拡張する、様々なタイプの処理がより効率的なキャッシュ認識の態様で実行されることを可能にし得る。同時実行される場合、任意の項目が作業待ち行列から取り出され、実行され得る。並列処理があってもよく、またはなくてもよい。いくつかの場合、複数の項目を１つずつ処理する必要があり得る（シングルスレッドを付けられる）。他のシナリオにおいて、いくつかのワーカ（ｗｏｒｋｅｒ）が別個の項目を並列に処理し得る（以下の「作業スティール」の検討を参照されたい）。
【００５６】
本発明の一実施形態は、処理する作業待ち行列から次の項目を選択するべく用いられる。全ての物は等しく（公平性の問題は無視する）、データがすでに複数のキャッシュのうち１つに存在する（具体的には、ＬＩキャッシュ８１０等、キャッシュ階層の更に上にあるもの）項目を選択することは、性能に有益であろう。これは、実行される処理がメモリバインドされ、次にどのアドレスが必要とされるかを予測することが困難である場合に、特に有益であり得る。
【００５７】
本発明の一実施形態において、本発明の複数の実施形態を利用する処理は、（例えば、本明細書において説明されるキャッシュ占有命令を利用して）「キャッシュされた」項目を探索して作業待ち行列をスキャンし、発見された第１のものを処理する。代替的に、または更に、処理は、キャッシュされ、キャッシュ階層において比較的高次の（例えば、ＬＩキャッシュの）１または複数の作業項目を選択する複数の項目を識別し得る。キャッシュ内に項目が見つからない場合、（例えば、標準的技術を用いて）作業待ち行列上の第１の項目が取り出され、処理される。
【００５８】
本発明の複数の実施形態は、複数のノードがメモリ内に分散されているツリーをスキャンする場合に、特に適用可能であり得る。この実装において、作業待ち行列上の各項目は、ノードに対するポインタを指定する。そのようないくつかのノードが、同一のキャッシュラインに存在し得るが、任意の順序または位置にある。空間的位置関係を最適化することを希望するときに、多くの場合、予期されるキャッシュ動作に基づいて、例えば、ツリーに横断的な幅優先探索（ＢＦＳ）または深さ優先探索（ＤＦＳ）を選択し得る。
【００５９】
本発明の複数の実施形態を用いて、キャッシュにスキャンを導かせることにより、より大きな精度が得られ得る（上述の通り）。そのようなスキャンの例として、例えば任意の順序でリーフを処理するカッド／オクトツリーおよび複数のマーク・アンド・スイープ・ガーベッジ型コイレクタ（すなわち、プログラムにより最早用いられないメモリ部分を回収する処理）のスキャンが挙げられる。
【００６０】
別の例は、スレッドビルディングブロック（ＴＢＢ）、本願の譲受人により開発された、マルチコアプロセッサを利用する複数のソフトウェアプログラムを書くためのＣ＋＋テンプレートライブラリ等の並列実行フレームワークにおける作業スティールを含む。スレッドが複数の他のスレッドの作業待ち行列の作業をスティールするように見える場合、スティールするスレッドのキャッシュ内にすでに存在する作業をスティールするのが好ましい。作業がすでにキャッシュ内に存在するか否かの判断は、本明細書に説明される複数の技術を用いて実現され得る。
【００６１】
具体的な例として、本発明の一実施形態は、ＢＦＳスキャンの以下のテキストブック実装の文脈において説明される（ウィキペディアより）。
【数１】
0006375379.tif 000002
【００６２】
一実施形態は、キャッシュ内に存在するエントリを探索してＱまたはＱの限定部分をスキャンする（例えば、上記のキャッシュ占有命令を実行する）ループにより、ライン６"t <- Q.dequeue()")を実装する。１つが見つかると、（場合によってはＱの中央から）「デキュー」され、戻される。そのようなエントリが見つからない場合、Ｑの第１の要素がデキューされる。探索は、最早幅優先でないことに留意されたい。
【００６３】
別の用途は、ライン１３をチェックし、ｕがキャッシュ内に存在するか否かを判断する。存在する場合、継続してマークをチェックし、「キャッシュされたキュー」の状態でエンキューする。ｕがキャッシュ内に存在しない場合、「キャッシュされないキュー」の状態でエンキューする。一実施形態において、複数の作業項目は、まず「キャッシュされたキュー」から実行される。キャッシュされた行列が空である場合、複数の作業項目は、「キャッシュされないキュー」から実行される。
【００６４】
データがキャッシュ内に格納されているか否かを判断するための方法の一実施形態は、図９に図示されている。９０１において、（例えば、実行を待機する１または複数の命令から判断された）処理されるデータに関連する１または複数のアドレスが識別される。すでに言及されたように、一実施形態において、複数のアドレスは、同時に読み取られて処理され得る（例えば、ベクトル命令によりベクトルレジスタから読み取られる）。９０２において、各アドレスに関連するデータが複数のキャッシュレベルのうち１つに格納されているか否かについて判断される。格納されていない場合、９０４において、データがキャッシュ内（例えば、デスティネーション／結果レジスタに）に存在しないことを示す結果が格納される。格納されている場合、９０３において、データが複数のキャッシュレベルのうち１つに、潜在的にはキャッシュレベルの識別および／または他の関連する情報（例えば、アクセスするのに予期される「時間」、アドレスが「遠すぎる」ことの表示等）と共に格納されていることを示す結果が、格納される。
【００６５】
９０５において、１または複数の後続のオペレーションは、複数の結果に基づいてスケジューリングされる。例えば、データのいずれもキャッシュレベルに格納されていない場合、後続の複数のオペレーションは、既存の複数のスケジューリング技術を用いてスケジューリングされ得る。しかし、保留中の複数のオペレーションのうち１または複数のデータがキャッシュに格納されている場合、これらの動作は、キャッシュ内に格納されたデータを有しないオペレーションの前に実行するべくスケジューリングされ得る。一実施形態において、データが格納されるキャッシュレベルの識別は、スケジューリングに用いられ得る。例えば、ＬＩキャッシュに格納されたデータを用いる複数のオペレーションがまず実行されてもよく、この後にＬ２キャッシュに格納されたデータを伴う複数のオペレーション、次いでキャッシュ階層の更に下（例えば、低次レベルのキャッシュ（ＬＬＣ）または他のより低いキャッシュレベルのストア）の複数のオペレーションが続く。
【００６６】
本明細書に説明される複数の技術を用いてスケジューリングされる複数の「オペレーション」は、例えばマクロ命令またはマイクロオペレーションを含む任意の形式のオペレーションを含み得ることに留意されたい。更に、本発明の基礎となる複数の原理は、複合命令セットコンピュータ（ＣＩＳＣ）アーキテクチャおよび縮小命令セットコンピュータ（ＲＩＳＣ）アーキテクチャを含む、任意のタイプの命令セットアーキテクチャ上に実装され得る。
【００６７】
各作業項目のデータがキャッシュ内に格納されているか否かに基づいて作業待ち行列から複数の作業項目をスケジューリングするための方法の一実施形態は、図１０に図示されている。１００１において、１または複数の作業項目が評価のために選択される。上述のように、各作業項目は、実行を保留している作業待ち行列を格納し得、複数の作業項目は、並列に評価され得る。１００２において、（例えば、上述のデータのアドレスを用いて）１または複数の作業項目を実行するのに必要とされるデータがキャッシュ内に格納されたか否かについて判断される。格納されていない場合、１００４において、データがキャッシュされていないことを示す結果が格納され、複数の作業項目は、１００５において既存の複数の技術を用いて（例えば、ＢＦＳスキャンを用いて）スケジューリングされる。
【００６８】
しかし、１００２において、１または複数の作業項目のデータがキャッシュされたと判断される場合、１００３において、データが複数のキャッシュレベルのうち１つに、潜在的にはキャッシュレベルの識別および／または他の関連する情報（例えば、アクセスするのに予期される「時間」、アドレスが「遠すぎる」ことの表示等）と共に格納されていることを示す結果が、格納される。１００５において、データがキャッシュされる複数の作業項目は、キャッシュ内に格納されたデータを有しない複数の作業項目の前に実行するべくスケジューリングされ得る。一実施形態において、データが格納されるキャッシュレベルの識別は、スケジューリングに用いられ得る。例えば、図９に示される実施形態におけるように、ＬＩキャッシュに格納されたデータを有する複数の作業項目がまず実行され、その後にＬ２キャッシュに格納されたデータを有する複数の作業項目、次にキャッシュ階層の更に下の複数の作業項目（例えば、低次レベルのキャッシュ（ＬＬＣ）または他のより低いキャッシュレベルに格納された）が続いてもよい。
【００６９】
本発明の複数の実施形態は、上記の様々な段階を含み得る。複数の段階は、汎用または特定用途用プロセッサに複数の段階を実行させるべく用いられ得る複数の機械実行可能命令に実施され得る。あるいは、これらの段階は、複数の段階を実行するためのハードワイヤードロジックを含む特定の複数のハードウェアコンポーネントにより、またはプログラミングされたコンピュータコンポーネントおよびカスタムハードウェアコンポーネントの任意の組み合わせにより、実行され得る。
【００７０】
本明細書において説明されるように、複数の命令は、特定の複数のオペレーションを実行するよう構成され、または予め定められた機能または非一時的コンピュータ可読媒体に実施されるメモリに格納された複数のソフトウェア命令を有する特定用途向け集積回路（ＡＳＩＣ）等のハードウェアの特定の構成を指し得る。従って、図に示される複数の技術は、１または複数の電子デバイス（例えば、終端局およびネットワーク要素等）上に格納され、実行されるコードおよびデータを用いて実装され得る。そのような電子デバイスは、非一時的コンピュータ機械可読記憶媒体（例えば、磁気ディスク、光ディスク、ランダムアクセスメモリ、リードオンリメモリ、フラッシュメモリデバイス、相変化メモリ）および一時的コンピュータ機械可読通信媒体（例えば、搬送波、赤外線信号、デジタル信号等の伝搬信号の電気、光、音響、又は他の形体）等、コンピュータ機械可読媒体を用いてコードおよびデータを（内部で、および／またはネットワークを介して他の電子デバイスを用いて）格納および通信する。更に、そのような電子デバイスは通常、１もしくは複数のストレージデバイス（非一時的機械可読記憶媒体）、ユーザ入力／出力デバイス（例えば、キーボード、タッチスクリーン、および／またはディスプレイ）、ならびにネットワーク接続等、１または複数の他のコンポーネントに結合された１もしくは複数のプロセッサのセットを含む。複数のプロセッサのセットおよび他の複数のコンポーネントの結合は通常、１または複数のバスおよびブリッジ（バスコントローラとも呼ばれる）を介して行われる。ストレージデバイスおよびネットワークトラフィックを搬送する複数の信号は、各々、１または複数の機械可読記憶媒体および機械可読通信媒体を表す。従って、所与の電子デバイスのストレージデバイスは通常、当該電子デバイスの１または複数のプロセッサのセット上で実行するためのコードおよび／またはデータを格納する。勿論、本発明の実施形態の１または複数の部分は、ソフトウェア、ファームウェア、および／またはハードウェアの異なる組み合わせを用いて実装され得る。詳細な説明を通じて、説明の目的のために、様々な特定の詳細が、本発明の完全な理解を提供するために記載された。しかし、当業者には本発明がこれら具体的な詳細のいくつかがなくても実施され得ることが明らかであろう。特定の例において、周知の構造および機能は、本発明の主題を不明瞭にするのを避けるべく、精巧詳細に説明されていない。従って、発明の範囲および趣旨は、以下の特許請求の範囲の観点から判断されるべきである。本明細書によれば、以下の各項目に記載の事項もまた開示される。
［項目１］
少なくとも１つのレベル１（Ｌ１）キャッシュを含むデータをキャッシュするための複数のキャッシュレベルの階層と、
１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断するキャッシュ占有決定ロジックと、
前記１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルに格納されているか否かの前記判断に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングするスケジューリングロジックとを備える、プロセッサ。
［項目２］
前記キャッシュ占有決定ロジックは、前記１または複数の後続の命令に関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断する、キャッシュ占有命令を実行する実行ロジックを含む、項目１に記載のプロセッサ。
［項目３］
前記キャッシュ占有命令は、前記１または複数の後続の命令の前記データに関連する１または複数のアドレスを読み取り、前記データが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断するべく、前記１または複数のアドレスを用いる、項目２に記載のプロセッサ。
［項目４］
前記１または複数のアドレスを用いることは、前記１または複数のアドレスを用いたキャッシュ検索オペレーションを実行することを含む、項目３に記載のプロセッサ。
［項目５］
前記キャッシュ占有決定ロジックは、前記１または複数の後続のオペレーションに関連する前記データが格納される特定の前記複数のキャッシュレベルを更に決定する、項目１に記載のプロセッサ。
［項目６］
前記スケジューリングロジックは、前記１または複数の後続のオペレーションの前記データが格納される特定の前記複数のキャッシュレベルの前記決定に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングする、項目５に記載のプロセッサ。
［項目７］
前記スケジューリングロジックは、キャッシュ階層において比較的低次のデータおよび／またはキャッシュレベルにないデータを用いた複数のオペレーションの前に、前記キャッシュ階層において比較的高次のデータを用いた複数のオペレーションをスケジューリングする、項目６に記載のプロセッサ。
［項目８］
前記キャッシュ占有決定ロジックは、前記データにアクセスするのに予期される時間、および指定閾値に基づいた前記データが遠すぎるか否かの表示のうち少なくとも１つを更に決定する、項目１に記載のプロセッサ。
［項目９］
前記スケジューリングロジックは、前記決定された、前記データにアクセスするのに予期される時間、および指定閾値に基づいた、前記データが遠すぎるか否かの表示のうち少なくとも１つに基づいて、前記１または複数の後続のオペレーションをスケジューリングする、項目８に記載のプロセッサ。
［項目１０］
前記複数のキャッシュレベルは、レベル２（Ｌ２）キャッシュおよび低次のレベルのキャッシュ（ＬＬＣ）を更に含む、項目１に記載のプロセッサ。
［項目１１］
少なくとも１つのレベル１（Ｌ１）キャッシュを含む複数のキャッシュレベルの階層内のデータをキャッシュする段階と、
１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断する段階と、
前記１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルに格納されているか否かの前記判断に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングする段階とを備える、方法。
［項目１２］
前記１または複数の後続の命令に関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断する、キャッシュ占有命令を実行する段階を更に備える、項目１１に記載の方法。
［項目１３］
前記キャッシュ占有命令は、前記１または複数の後続の命令の前記データに関連する１または複数のアドレスを読み取り、前記データが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断するべく、前記１または複数のアドレスを用いる、項目１２に記載の方法。
［項目１４］
１または複数のアドレスを用いる段階は、前記１または複数のアドレス用いたキャッシュ検索オペレーションを実行する段階を備える、項目１３に記載の方法。
［項目１５］
前記１または複数の後続のオペレーションに関連する前記データが格納される特定の前記複数のキャッシュレベルを決定する段階を更に備える、項目１１に記載の方法。
［項目１６］
前記１または複数の後続のオペレーションの前記データが格納される特定の前記複数のキャッシュレベルの前記決定に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングする段階を更に備える、項目１５に記載の方法。
［項目１７］
キャッシュ階層において比較的低次のデータおよび／またはキャッシュレベルにないデータを用いた複数のオペレーションの前に、キャッシュ階層において比較的高次のデータを用いた複数のオペレーションをスケジューリングする段階を更に備える、項目１６に記載の方法。
［項目１８］
前記データにアクセスするのに予期される時間、および指定閾値に基づいた前記データが遠すぎるか否かの表示のうち少なくとも１つを決定する段階を更に備える、項目１１に記載の方法。
［項目１９］
前記決定された、前記データにアクセスするのに予期される時間、および指定閾値に基づいた、前記データが遠すぎるか否かの表示のうち少なくとも１つに基づいて、前記１または複数の後続のオペレーションをスケジューリングする段階を更に備える、項目１８に記載の方法。
［項目２０］
前記複数のキャッシュレベルは、レベル２（Ｌ２）キャッシュおよび低次のレベルのキャッシュ（ＬＬＣ）を更に含む、項目１１に記載の方法。
［項目２１］
システムであって、
プログラムコードおよびデータを格納するためのメモリと、
１または複数の周辺機器デバイスと通信するための入力／出力（ＩＯ）通信インターフェースと、
前記システムをネットワークに通信可能に結合するためのネットワーク通信インターフェースと、
プロセッサとを備え、
前記プロセッサは、
少なくとも１つのレベル１（Ｌ１）キャッシュを含む、データをキャッシュするための複数のキャッシュレベルの階層と、
１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルのうち１つに格納されているか否かを判断する、キャッシュ占有決定ロジックと、
前記１または複数の後続のオペレーションに関連するデータが前記複数のキャッシュレベルに格納されているか否かの前記判断に基づいて、前記１または複数の後続のオペレーションの実行をスケジューリングするスケジューリングロジックとを有する、システム。
【図１Ａ】
0006375379.tif 000003
【図１Ｂ】
0006375379.tif 000004
【図２】
0006375379.tif 000005
【図３】
0006375379.tif 000006
【図４】
0006375379.tif 000007
【図５】
0006375379.tif 000008
【図６】
0006375379.tif 000009
【図７】
0006375379.tif 000010
【図８】
0006375379.tif 000011
【図９】
0006375379.tif 000012
【図１０】
0006375379.tif 000013