キャッシュ・ディレクトリ内の実ページ番号ビットのテスト方法、装置、およびコンピュータ記録可能な媒体
【課題】キャッシュ・ディレクトリ内の実ページ番号ビットのテストを提供する。
【解決手段】テスト対象のキャッシュに関連付けられたキャッシュ・ディレクトリの実ページ番号ビットをテストするために、当該キャッシュの仕様が検索される。キャッシュ・ディレクトリの実ページ番号アドレス内のある範囲が、キャッシュの仕様を使用してページ割り当てを行うために特定される。テスト対象の実ページ番号ビットの部分を特定するランダム値ｘが生成される。テスト対象のキャッシュの部分内の合同クラスのセットから第１の合同クラスを特定する第１のランダム値ｙが生成される。第１の合同クラスが所定の回数割り当てられなかったことに応じて、第１の合同クラスについてのメモリの１ページ分のサイズが割り当てられ、第１の割り当て値が１の値で増分される。
【解決手段】テスト対象のキャッシュに関連付けられたキャッシュ・ディレクトリの実ページ番号ビットをテストするために、当該キャッシュの仕様が検索される。キャッシュ・ディレクトリの実ページ番号アドレス内のある範囲が、キャッシュの仕様を使用してページ割り当てを行うために特定される。テスト対象の実ページ番号ビットの部分を特定するランダム値ｘが生成される。テスト対象のキャッシュの部分内の合同クラスのセットから第１の合同クラスを特定する第１のランダム値ｙが生成される。第１の合同クラスが所定の回数割り当てられなかったことに応じて、第１の合同クラスについてのメモリの１ページ分のサイズが割り当てられ、第１の割り当て値が１の値で増分される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には、改良されたデータ処理装置および方法に関し、より特定的には、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための装置および方法に関する。
【背景技術】
【０００２】
従来のコンピュータ・システムは、１つ以上の処理ユニットを有し得、当該処理ユニットは、入力／出力（Ｉ／Ｏ）デバイス（表示モニタ、キーボード、または常設の記憶デバイスなど）、処理ユニットがプログラム命令を実行するのに使用されるメモリ・デバイス（ランダム・アクセス・メモリ、すなわちＲＡＭ）、およびコンピュータに最初に電源が投入される度に周辺機器のうちの１つ（通常は常設のメモリ・デバイス）からオペレーティング・システムをシークしてロードするのが主要な目的であるファームウェアを含む様々な周辺デバイスに接続されている。処理ユニットは、汎用の相互接続またはバスを含む様々な手段によって周辺デバイスと通信する。また、従来のコンピュータ・システムは、例えばモデムまたはプリンタに接続するためのシリアル・ポートおよびパラレル・ポートなどの数多くのさらなる構成要素を含み得る。従来のコンピューティング・システムにおいて使用され得る構成要素は他にもあって、例えば、ビデオ・ディスプレイ・モニタを制御するためにディスプレイ・アダプタが使用されることもあるし、メモリにアクセスするためにメモリ・コントローラが使用されることもあることを、当業者はさらに理解するだろう。入出力（Ｉ／Ｏ）デバイスを直接バスに接続する代わりに、Ｉ／Ｏデバイスは、バスへのＩ／Ｏブリッジにさらに接続されている２次（Ｉ／Ｏ）バスに接続されてもよい。また、コンピュータは、２つより多くの処理ユニットを有してもよい。
【０００３】
対称マルチプロセッサ（ｓｙｍｍｅｔｒｉｃ ｍｕｌｔｉ−ｐｒｏｃｅｓｓｏｒ：ＳＭＰ）コンピュータにおいて、処理ユニットのすべては、一般的には同一であり、すなわち、それらすべては命令およびプロトコルの一般的なセットまたはサブセットを使用して動作し、一般的には同一のアーキテクチャを有する。そのようなＳＭＰコンピュータは、プロセッサ・コアを含む処理ユニットを含むことがあり、当該プロセッサ・コアは、コンピュータを動作させるためにプログラム命令を実行する複数のレジスタおよび実行ユニットを有する。また、処理ユニットは、命令キャッシュおよびデータ・キャッシュなどの１つ以上のキャッシュを有し得、当該キャッシュは、高速メモリデバイスを使用して実施される。命令およびデータは、オペランドが命令対データである動作を処理ユニットが要求しているかどうかを示す信号を検査することによって各キャッシュに向けて送り出されてもよい。キャッシュは、メモリから値をロードするという時間がかかるステップを回避することによって処理を高速化するために、プロセッサによって繰り返しアクセスされ得るような値を一時的に記憶するために通常使用される。これらのキャッシュは、プロセッサ・コアと共に単一の集積チップ上に一体化してパッケージされる場合には「オン・ボード（ｏｎ−ｂｏａｒｄ）」と称される。各キャッシュは、一般的には、プロセッサ・コアとキャッシュ・メモリとの間のデータの転送を管理するキャッシュ・コントローラに関連付けられている。
【０００４】
処理ユニットは、オン・ボードの第１レベル・キャッシュをサポートする第２レベル（Ｌ２）キャッシュなどのさらなるキャッシュを含んでもよい。言い換えれば、Ｌ２キャッシュは、メモリとオン・ボードのキャッシュとの間の媒介物として作用し、オン・ボードのキャッシュよりも遥かに多くの情報量（命令およびデータ）を記憶することができるが、アクセスには時間がかかるのが不利益な点である。例えば、Ｌ２キャッシュは、２５６または５１２キロバイトの記憶容量を有するチップであってもよいが、プロセッサは、全ストレージが６４キロバイトであるオン・ボード・キャッシュを有するＩＢＭＰｏｗｅｒＰＣ（ＩＢＭ社の登録商標）６０４シリーズのプロセッサであってもよい。Ｌ２キャッシュは、一般的にはバスに接続され、メモリからプロセッサ・コアへの情報の全ローディングは、Ｌ２キャッシュを通じて行われなければならない。加えて、コンピューティング・システムは、シリアルに接続されたキャッシュのレベルが数多くあるマルチ・レベルのキャッシュ階層を含んでもよい。
【０００５】
キャッシュは、様々な命令およびデータ値を個別に記憶する数多くの「ブロック」を有する。任意のキャッシュ内のブロックについて、「セット」と称されるブロックの群に分割される。セットは、所与のメモリ・ブロックが存在し得るキャッシュ・ブロックの集まりである。任意の所与のメモリ・ブロックには、予め設定されたマッピング機能に従って当該ブロックがマップされ得る固有のセットがキャッシュ内にある。１セット内のブロック数は、当該キャッシュの連想度（ａｓｓｏｃｉａｔｉｖｉｔｙ）と称され、例えば、２ウェイ（ｗａｙ）セット・アソシアティブは、任意の所与のメモリ・ブロックについて、当該メモリ・ブロックがマッピングされ得るブロックがキャッシュ内に２つあるが、メイン・メモリ内にあるいくつかの異なるブロックは任意の所与のセットにマッピングされ得ることを意味する。１ウェイ・セット・アソシアティブ・キャッシュは、直接マッピングされる。すなわち、特定のメモリ・ブロックを包含し得るキャッシュ・ブロックは１つだけである。メモリ・ブロックが任意のキャッシュ・ブロックを占有し得る場合には、キャッシュは、完全にアソシアティブであるといえ、すなわち、セットは１つであり、アドレス・タグは、メモリ・ブロックのフル・アドレスである。
【０００６】
キャッシュ・ライン（ブロック）の一例は、アドレス・タグ・フィールドと、状態ビット・フィールドと、包括ビット・フィールドと、実命令またはデータを記憶するための値フィールドとを含む。状態ビット・フィールドおよび包括ビット・フィールドは、マルチプロセッサ・コンピュータ・システムにおけるキャッシュの一貫性を維持するために使用される。アドレス・タグは、対応するメモリ・ブロックのフル・アドレスのサブセットである。入力有効アドレスと、アドレス・タグ・フィールド内のタグのうちの１つとの比較一致は、キャッシュ「ヒット」を示す。キャッシュ内のすべてのアドレス・タグ（および時には状態ビット・フィールドおよび包括ビット・フィールド）の集まりは、ディレクトリと称され、すべての値フィールドの集まりは、キャッシュ・エントリ・アレイである。
【０００７】
所与のキャッシュについてのセット内のすべてのブロックがフルであって、フル・セットへマッピングするメモリ位置に対する「読み出し」または「書き出し」という要求を当該キャッシュが受信すると、キャッシュは、セット内に現在あるブロックのうちの１つを「エビクト（ｅｖｉｃｔ）」しなければならない。キャッシュは、エビクトすべきブロックを、当業者に周知の複数の手段（最長時間未使用法（ｌｅａｓｔ ｒｅｃｅｎｔｌｙ ｕｓｅｄ：ＬＲＵ）、ランダム、擬似ＬＲＵなど）のうちの１つによって選択する。選択されたブロック内のデータが修正される場合には、当該データは、メモリ階層のうちで最下位から２番目に低いレベルに書き込まれ、このレベルは、他のキャッシュ（Ｌ１またはオン・ボードのキャッシュの場合）またはメイン・メモリ（Ｌ２キャッシュの場合）であってもよい。包含の原理により、階層の最下層は、書き込まれた修正済みのデータを保持するために利用可能なブロックを既に有することになる。しかしながら、選択されたブロック内のデータが修正されない場合には、ブロックはそのまま破棄され、階層内の再開から２番目に低いレベルに書き込まれない。階層の１つのレベルからブロックを除去するというこの処理は、「エビクション（ｅｖｉｃｔｉｏｎ）」として知られている。この処理の終わりでは、キャッシュは、もはや、エビクトされたブロックのコピーを有さない。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
プロセッサ上で実行する手順（プログラム）の中には、限られた数のセット（合同（ｃｏｎｇｒｕｅｎｃｅ）クラス）を繰り返し使用するのでキャッシュが効率的でなくなるという予期せぬ効果を有するものがある。言い換えると、ある手順が少数の合同クラス要素内で多数のエビクションを生じさせる一方で多数の他の要素を使用しない場合には、メモリ・レイテンシ遅延が増加する。この効果はストライド（ｓｔｒｉｄｅ）と称され、合同マッピング機能と、特定の手順がメイン・メモリ・デバイス内にメモリ・ブロックを割り当てている手法とに関連する。
【０００９】
一般的には、データ処理システム内のキャッシュのテストは、Ｌ２キャッシュ量の２倍の割り当てを要する。単一の指標に指標付けするページが既存のエントリを除去またはエビクトさせる場合には、このＬ２キャッシュ量を使用することによって、キャッシュの中には、ローリングまたは置換を要するものもあり、よって、より多くのストレスおよびキャッシュ・ラインのテストを生じさせることがある。キャッシュの同一のストレスを達成するためにキャッシュのメモリ量を増加させる場合があるが、メモリを追加するのは最善策ではない。キャッシュ・ディレクトリ内の実ページ番号（ｒｅａｌ ｐａｇｅ ｎｕｍｂｅｒｓ：ＲＰＮ）ビットをテストするために、テスト・プログラムは、典型的には、大量のメモリを経由する。製造およびシミュレーション・テストにおいても、時間は重要な要素である。カードの製造、モジュールの製造、およびウェハの製造において利用可能な総テスト時間量は、典型的には秒単位である。しかしながら、シミュレーションにおいても、周期が正確なモデルでシミュレートするために時間の制約があるのは明白である。
【課題を解決するための手段】
【００１０】
例示の一実施形態において、データ処理システムにおいて、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための方法が提供される。例示の実施形態は、テスト対象のキャッシュに関連付けられたキャッシュ・ディレクトリの実ページ番号ビットをテストするために、当該キャッシュの仕様が検索（ｒｅｔｒｉｅｖｅ）される。例示の実施形態は、キャッシュの仕様を使用してページ割り当てを行うためにキャッシュ・ディレクトリの実ページ番号アドレス内の範囲を特定する。例示の実施形態は、テスト対象の実ページ番号ビットの部分を特定するランダム値ｘを生成する。例示の実施形態は、テスト対象のキャッシュの部分内の合同クラスのセットから第１の合同クラスを特定する第１のランダム値ｙを生成する。例示の実施形態は、第１のランダム値ｙに関連付けられた第１の合同クラスが所定の回数割り当てられたかどうかを判断する。例示の実施形態は、第１のランダム値ｙに関連付けられた第１の合同クラスについて、メモリの１ページ分のサイズを割り当て、第１の合同クラスに関連付けられた第１の割り当て値を１の値で増分する。
【００１１】
例示の他の実施形態において、コンピュータ読み出し可能なプログラムを有するコンピュータ使用可能または読み出し可能な媒体を備えるコンピュータ・プログラム製品が提供される。当該コンピュータ読み出し可能なプログラムは、コンピューティング・デバイス上で実行されると、方法の例示の実施形態に関して先に概説した様々な動作およびその組み合わせを当該コンピューティング・デバイスに行わせる。
【００１２】
さらに他の例示の実施形態において、システム／装置が提供される。当該システム／装置は、１つ以上のプロセッサと、当該１つ以上のプロセッサに結合されたメモリとを備えてもよい。当該メモリは、当該１つ以上のプロセッサによって実行されると、方法の例示の実施形態に関して先に概説した様々な動作およびその組み合わせを当該１つ以上のプロセッサに行わせる命令を備えてもよい。
【００１３】
本発明のこれらおよび他の特徴および利点は、本発明の実施形態例の以下の詳細な説明において説明されるか、または当該詳細な説明を考慮すれば当業者にとって明らかになるだろう。
【図面の簡単な説明】
【００１４】
【図１】例示の実施形態の局面が実施され得る分散型データ処理システム例の実体表現を示す。
【図２】例示の実施形態の局面が実施され得るデータ処理システム例のブロック図を示す。
【図３】例示の一実施形態に係る、キャッシュ・ディレクトリ内の実ページ番号（ＲＰＮ）アドレス・ビットをテストするためのキャッシュ・テスト・アプリケーションの機能ブロック図を示す。
【図４】例示の一実施形態に係る、Ｌ２キャッシュ例についてＣＯＮＧＳＥＴＳＩＺＥが１６の場合のテストを表すアレイ例を示す。
【図５】例示の一実施形態に係る、キャッシュ・ディレクトリ内の実ページ番号（ＲＰＮ）アドレス・ビットをテストするためのキャッシュ・テスト・アプリケーションの動作例を示す。
【図６】例示の一実施形態に係る、キャッシュ・ディレクトリ内の実ページ番号（ＲＰＮ）アドレス・ビットをテストするためのキャッシュ・テスト・アプリケーションの動作例を示す。
【発明を実施するための形態】
【００１５】
本発明ならびに好ましい使用態様およびさらにその目的および利点は、添付の図面と共に解釈される場合に例示の実施形態の以下の詳細な説明を参照することによって、最もよく理解されるだろう。
【００１６】
当業者によって理解されるように、本発明は、システム、方法、またはコンピュータ・プログラム製品によって具体化されてもよい。したがって、本発明は、完全にハードウェアによる実施形態、完全にソフトウェアによる実施形態（ファームウェア、常駐ソフトウェア、マイクロ・コードなどを含む）、またはすべてが一般的に本明細書において「回路」、「モジュール」、または「システム」と称され得るソフトウェアの局面とハードウェアの局面とを組みあわせる実施形態の形式を取ってもよい。さらに、本発明は、媒体において具体化されたコンピュータ使用可能なプログラム・コードを有する有形の媒体表現に具体化されたコンピュータ・プログラム製品の形式を取ってもよい。
【００１７】
１つ以上のコンピュータ使用可能またはコンピュータ読み出し可能な媒体の任意の組み合わせが使用されてもよい。コンピュータ使用可能またはコンピュータ読み出し可能な媒体は、例えば、電子、磁気、光学、電磁、赤外線、または半導体のシステム、装置、デバイス、または伝搬媒体であってもよいが、これらに限定されない。コンピュータ読み出し可能な媒体のより特定的な例（非網羅的リスト）は、以下のものを含むことになろう。１つ以上の電線を有する電気接続、携帯型コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ：ＲＡＭ）、読み出し専用メモリ（ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ：ＲＯＭ）、消去可能プログラム可能読み出し専用メモリ（ｅｒａｓａｂｌｅ ｐｒｏｇｒａｍｍａｂｌｅ ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ：ＥＰＲＯＭ、またはフラッシュ・メモリ）、光ファイバ、携帯型コンピュータ・ディスク読み出し専用メモリ（ｃｏｍｐａｃｔ ｄｉｓｃ ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ：ＣＤＲＯＭ）、光学記憶デバイス、インターネットまたはイントラネットをサポートするなどの送信媒体、または磁気記憶デバイスである。なお、コンピュータ使用可能またはコンピュータ読み出し可能な媒体は、プログラムが印刷されている用紙または他の適切な媒体でさえあり得る。というのは、当該プログラムは、例えば当該用紙または他の媒体の光学スキャニングを介して電子的に取り入れられ、その後、コンパイルされ、解釈され、または必要があれば別の適切な手法で処理され、その後コンピュータ・メモリに記憶され得るからである。本明細書の場合においては、コンピュータ使用可能またはコンピュータ読み出し可能な媒体は、命令実行システム、装置またはデバイスによってまたはそれとともに使用されるプログラムを包含、記憶、通信、伝搬、または転送できる任意の媒体であってもよい。コンピュータ使用可能な媒体は、ベースバンドでまたは搬送波の一部としてのいずれかで、共に具体化されたコンピュータ使用可能なプログラム・コードを伴う伝搬データ信号を含んでもよい。コンピュータ使用可能なプログラム・コードは、無線、有線ライン、光ファイバ・ケーブル、無線周波数（ｒａｄｉｏ ｆｒｅｑｕｅｎｃｙ：ＲＦ）などの任意の適切な媒体を使用して送信されてもよい。
【００１８】
本発明の動作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ（商標）、Ｓｍａｌｌｔａｌｋ（商標）、またはＣ＋＋などのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語または同様のプログラミング言語などの従来の手続きプログラミング言語を含む１つ以上のプログラミング言語の任意の組み合わせで書き込まれてもよい。プログラム・コードは、ユーザのコンピュータ上で全面的に、ユーザのコンピュータ上で部分的に、独立型のソフトウェア・パッケージとして、ユーザのコンピュータ上で部分的にかつリモート・コンピュータ上で部分的に、またはリモート・コンピュータまたはサーバ上で全面的に実行してもよい。後者の場合において、リモート・コンピュータは、ローカル・エリア・ネットワーク（ｌｏｃａｌ ａｒｅａ ｎｅｔｗｏｒｋ：ＬＡＮ）またはワイド・エリア・ネットワーク（ｗｉｄｅ ａｒｅａ ｎｅｔｗｏｒｋ：ＷＡＮ）を含む任意の種類のネットワークを通じてユーザのコンピュータに接続されてもよく、または、当該接続は、（例えば、インターネット・サービス・プロバイダを使用してインターネットを通じて）外部コンピュータに対してなされてもよい。
【００１９】
本発明の例示の実施形態に係る方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート図またはブロック図あるいはその両方を参照して、例示の実施形態を以下に説明する。フローチャート図またはブロック図あるいはその両方の各ブロック、およびフローチャート図またはブロック図あるいはその両方におけるブロックの組み合わせは、コンピュータ・プログラム命令によって実施され得ることが理解されるだろう。これらのコンピュータ・プログラム命令は、汎用コンピュータ、専用コンピュータ、または他のプログラム可能データ処理装置のプロセッサに対して提供されて、コンピュータまたは他のプログラム可能なデータ処理装置のプロセッサを介して実行する命令が、フローチャートまたはブロック図あるいはその両方における１つまたは複数のブロックにおいて指定される機能／動作を実施するための手段を作成するようにマシンを生じさせてもよい。
【００２０】
これらのコンピュータ・プログラム命令は、コンピュータ読み出し可能な媒体に記憶されてもよく、当該コンピュータ読み出し可能な媒体は、コンピュータ読み出し可能な媒体に記憶された命令がフローチャートまたはブロック図あるいはその両方における１つまたは複数のブロックにおいて指定される機能／動作を実施する命令手段を含む製品を生じさせるような特定な手法で、コンピュータまたは他のプログラム可能なデータ処理装置を機能させることができる。
【００２１】
コンピュータ・プログラム命令は、コンピュータまたは他のプログラム可能なデータ処理装置にロードされて、一連の動作ステップが当該コンピュータまたは他のプログラム可能な装置上で実施されて、当該コンピュータまたは他のプログラム可能な装置上で実行する命令がフローチャートまたはブロック図あるいはその両方における１つまたは複数のブロックにおいて指定される機能／動作を実施するための処理を提供するように、コンピュータによって実施された処理を生じさせるようにしてもよい。
【００２２】
図面におけるフローチャートおよびブロック図は、本発明の様々な実施形態に係るシステム、方法、およびコンピュータ・プログラム製品の実現可能な実施のアーキテクチャ、機能、および動作を示す。これに関して、フローチャートまたはブロック図における各ブロックは、指定された（複数の）論理機能を実施するための１つ以上の実行可能な命令を備えるモジュール、セグメント、またはコードの一部を表してもよい。また、ある代替実施においては、ブロックに記された機能は、図に記された順序とは異なるように生じてもよいことに注意すべきである。例えば、連続して示された２つのブロックは、実際には、実質的に並列的に実行されてもよく、または、関与する機能によっては、ブロックはときには逆順で実行されてもよい。また、ブロック図またはフローチャート図あるいはその両方における各ブロックおよびブロック図またはフローチャート図あるいはその両方におけるブロックの組み合わせは、指定された機能または動作あるいは専用ハードウェアとコンピュータ命令との組み合わせを行う、専用ハードウェア・ベースのシステムによって実施され得ることに注意されたい。
【００２３】
例示の実施形態は、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための機構を提供する。よって、例示の実施形態は、分散型データ処理環境または単一のデータ処理デバイスなどを含む数多くの異なる種類のデータ処理環境において利用されてもよい。例示の実施形態の特定の要素および機能を説明するための状況を提供するために、例示の実施形態の局面が実施され得る環境例として図１および図２が以下に提供される。図１および図２に続く説明では、主に、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための機構を単一のデータ処理デバイスによって実施することに主に主眼が置かれることになるが、これは一例に過ぎず、本発明の特徴に対する制限を何ら表明するものでも示唆するものでもない。逆に、例示の実施形態は、キャッシュ・ディレクトリ内の実ページ番号ビットがテストされ得る分散型データ処理環境および実施形態を含むことが意図されている。図示の環境に対する数多くの変更が、本発明の精神および範囲から逸脱することなく行われてもよい。
【００２４】
今度は図面を参照すると、図１は、例示の実施形態の局面が実施され得る分散型データ処理システム例の実体表現を示す。分散型データ処理システム１００は、例示の実施形態の局面が実施され得るコンピュータのネットワークを含んでもよい。分散型データ処理システム１００は、少なくとも１つのネットワーク１０２を包含し、当該ネットワーク１０２は、分散型データ処理システム１００内で共に接続された様々なデバイスおよびコンピュータ間の通信リンクを提供するために使用される媒体である。ネットワーク１０２は、有線、無線通信リンクまたは光ファイバ・ケーブルなどの接続を含んでもよい。
【００２５】
図示の例において、サーバ１０４およびサーバ１０６は、記憶ユニット１０８と共にネットワーク１０２に接続される。加えて、クライアント１１０，１１２，および１１４もネットワーク１０２に接続される。これらのクライアント１１０，１１２，および１１４は、例えば、パーソナル・コンピュータまたはネットワーク・コンピュータなどであってもよい。図示の例において、サーバ１０４は、ブート・ファイル、オペレーティング・システムの画像、およびアプリケーションなどのデータをクライアント１１０，１１２，および１１４へ提供する。クライアント１１０，１１２，および１１４は、図示の例におけるサーバ１０４に対するクライアントである。分散型データ処理システム１００は、さらなるサーバ、クライアント、および図示しない他のデバイスを含んでもよい。
【００２６】
図示の例において、分散型データ処理システム１００は、伝送制御プロトコル／インターネット・プロトコル（Ｔｒａｎｓｍｉｓｓｉｏｎ Ｃｏｎｔｒｏｌ Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ：ＴＣＰ／ＩＰ）というプロトコルのスイート（ｓｕｉｔｅ）を使用して互いに通信するネットワークおよびゲートウェイの世界的な集まりを表すネットワーク１０２を伴うインターネットである。インターネットの中心には、主要ノードまたはホスト・コンピュータ間の高速データ通信回線のバックボーンがあり、データおよびメッセージを経路設置する数千の商用、政府、教育、およびその他のコンピュータ・システムからなる。当然ながら、分散型データ処理システム１００は、例えばイントラネット、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）などの複数の異なる種類のネットワークを含んで実施されてもよい。上述のように、図１は一例であって、本発明の異なる実施形態に対してアーキテクチャの制限を加えるものではないので、図１の特定の要素が本発明の例示の実施形態が実施され得る環境に関する制限とみなされるべきではない。
【００２７】
図２を参照すると、例示の実施形態の局面が実施され得るデータ処理システム例のブロック図が示されている。データ処理システム２００は、図１のクライアント１１０などのコンピュータの一例であって、本発明の例示の実施形態のための処理を実施するコンピュータ使用可能なコードまたは命令が位置し得るものである。
【００２８】
図示の例において、データ処理システム２００は、ノース・ブリッジおよびメモリ・コントローラ・ハブ（ｎｏｒｔｈ ｂｒｉｄｇｅ ａｎｄ ｍｅｍｏｒｙ ｃｏｎｔｒｏｌｌｅｒ ｈｕｂ：ＮＢ／ＭＣＨ）２０２と、サウス・ブリッジおよび入出力コントローラ・ハブ（ｓｏｕｔｈ ｂｒｉｄｇｅ ａｎｄ ｉｎｐｕｔ／ｏｕｔｐｕｔ（Ｉ／Ｏ） ｃｏｎｔｒｏｌｌｅｒ ｈｕｂ：ＳＢ／ＩＣＨ）２０４とを含むハブ・アーキテクチャを用いる。処理ユニット２０６、メイン・メモリ２０８、およびグラフィックス・プロセッサ２１０がＮＢ／ＭＣＨ２０２に接続される。グラフィックス・プロセッサ２１０は、アクセラレィティッド・グラフィックス・ポート（ａｃｃｅｌｅｒａｔｅｄ ｇｒａｐｈｉｃｓ ｐｏｒｔ：ＡＧＰ）を通じてＮＢ／ＭＣＨ２０２と接続されてもよい。
【００２９】
図示の例において、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ２１２がＳＢ／ＩＣＨ２０４に接続する。音声アダプタ２１６、キーボードおよびマウス・アダプタ２２０、モデム２２２、読み出し専用メモリ（ＲＯＭ）２２４、ハード・ディスク・ドライブ（ｈａｒｄ ｄｉｓｋ ｄｒｉｖｅ：ＨＤＤ）２２６、ＣＤ−ＲＯＭドライブ２３０、ユニバーサル・シリアル・バス（ｕｎｉｖｅｒｓａｌ ｓｅｒｉａｌ ｂｕｓ：ＵＳＢ）ポートおよび他の通信ポート２３２、ならびにＰＣＩ／ＰＣＩｅデバイス２３４がバス２３８およびバス２４０を通じてＳＢ／ＩＣＨ２０４に接続する。ＰＣＩ／ＰＣＩｅデバイスは、例えばイーサネット（Ｒ）アダプタ、アドイン・カード、およびノートブック・コンピュータ用のＰＣカードを含んでもよい。ＰＣＩはカード・バス・コントローラを使用するが、ＰＣＩｅは使用しない。ＲＯＭ２２４は、例えばフラッシュ基本入出力システム（ｂａｓｉｃ ｉｎｐｕｔ／ｏｕｔｐｕｔ ｓｙｓｔｅｍ：ＢＩＯＳ）であってもよい。
【００３０】
ＨＤＤ２２６およびＣＤ−ＲＯＭドライブ２３０は、バス２４０を通じてＳＢ／ＩＣＨ２０４に接続する。ＨＤＤ２２６およびＣＤ−ＲＯＭドライブ２３０は、例えば、統合ドライブ・エレクトロニクス（ｉｎｔｅｇｒａｔｅｄ ｄｒｉｖｅ ｅｌｅｃｔｒｏｎｉｃｓ：ＩＤＥ）またはシリアル・アドバンスト・テクノロジー・アタッチメント（ｓｅｒｉａｌ ａｄｖａｎｃｅｄ ｔｅｃｈｎｏｌｏｇｙ ａｔｔａｃｈｍｅｎｔ：ＳＡＴＡ）インターフェースを使用してもよい。スーパーＩ／Ｏ（ＳＩＯ）ドライブ２３６がＳＢ／ＩＣＨ２０４に接続されてもよい。
【００３１】
オペレーティング・システムが処理ユニット２０６上で実行される。オペレーティング・システムは、図２におけるデータ処理システム２００内の様々な構成要素の制御を調和させて提供する。クライアントとして、オペレーティング・システムは、マイクロソフト（Ｍｉｃｒｏｓｏｆｔ）（Ｒ）ウィンドウズ（Ｗｉｎｄｏｗｓ）（Ｒ）ＸＰ（マイクロソフトおよびウィンドウズは、米国および他の諸国またはその両方におけるマイクロソフト社の商標である）などの市販のオペレーティング・システムであってもよい。Ｊａｖａ（商標）プログラミング・システムなどのオブジェクト指向プログラミング・システムがオペレーティング・システムと共に実行されてもよく、データ処理システム２００上で実行するＪａｖａ（商標）プログラムまたはアプリケーションからのオペレーティング・システムに対する呼び出しを提供する（Ｊａｖａは、米国および他の諸国またはその両方におけるサン・マイクロシステムズ社の商標である）。
【００３２】
サーバとして、データ処理システム２００は、例えばＩＢＭ（ＩＢＭ社の登録商標）ｅＳｅｒｖｅｒ（商標）Ｓｙｓｔｅｍ ｐ（ＩＢＭ社の登録商標）コンピュータ・システムであってもよく、アドバンスト・インタラクティブ・エグゼキュティブ（Ａｄｖａｎｃｅｄ Ｉｎｔｅｒａｃｔｉｖｅ Ｅｘｅｃｔｕｉｖｅ：ＡＩＸ）（ＩＢＭ社の登録商標）オペレーティング・システムまたはリナックス（ＬＩＮＵＸ）（Ｒ）オペレーティング・システム（ｅＳｅｒｖｅｒ、Ｓｙｓｔｅｍ ｐ、およびＡＩＸは、米国および他の諸国またはその両方におけるＩＢＭ社の商標であり、ＬＩＮＵＸは、米国および他の諸国またはその両方におけるリーナス・トーバルズ（Ｌｉｎｕｓ Ｔｏｒｖａｌｄｓ）の商標である）。データ処理システム２００は、処理ユニット２０６に複数のプロセッサを含む対称マルチプロセッサ（ｓｙｍｍｅｔｒｉｃ ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ：ＳＭＰ）システムであってもよい。代わりに、単一のプロセッサ・システムが用いられてもよい。
【００３３】
オペレーティング・システム、オブジェクト指向プログラミング・システム、ならびにアプリケーションまたはプログラムに関する命令は、ＨＤＤ２２６などの記憶デバイス上にあり、処理ユニット２０６によって実行するためにメイン・メモリ２０８にロードされてもよい。本発明の例示の実施形態についての処理は、処理ユニット２０６がコンピュータ使用可能なプログラム・コードを使用して行われてもよく、コンピュータ使用可能なプログラム・コードは、例えばメイン・メモリ２０８、ＲＯＭ２２４、または例えば１つ以上の周辺デバイス２２６および２３０にあってもよい。
【００３４】
図２に示すようなバス２３８またはバス２４０などのバス・システムは、１つ以上のバスからなってもよい。当然ながら、バス・システムは、任意の種類の通信組織またはアーキテクチャを使用して実施されてもよく、当該通信組織またはアーキテクチャは、それらに付属する異なる構成要素またはデバイス間のデータ転送を提供するものである。図２のモデム２２２またはネットワーク・アダプタ２１２などの通信ユニットは、データを送受信するために使用される１つ以上のデバイスを含んでもよい。メモリは、例えば、図２のメイン・メモリ２０８、ＲＯＭ２２４、またはＮＢ／ＭＣＨ２０２に見受けられるようなキャッシュであってもよい。
【００３５】
図１〜図２におけるハードウェアは実施によって異なってもよいことを当業者は理解するだろう。フラッシュ・メモリ、同等の不揮発性メモリ、または光ディスク・ドライブなどの他の内部ハードウェアまたは周辺機器が、図１〜図２に示すハードウェアに加えてまたはその代わりに使用されてもよい。また、例示の実施形態の処理は、本発明の精神および範囲を逸脱せずに上述のＳＭＰシステム以外のマルチプロセッサ・データ処理システムに適用されてもよい。
【００３６】
さらに、データ処理システム２００は、クライアント・コンピューティング・デバイス、サーバ・コンピューティング・デバイス、タブレット・コンピュータ、ラップトップ・コンピュータ、電話または他の通信デバイス、携帯情報端末（ｐｅｒｓｏｎａｌ ｄｉｇｉｔａｌ ａｓｓｉｓｉｔａｎｔ：ＰＤＡ）などを含む任意の複数の異なるデータ処理システムの形態を取ってもよい。例示のある例においては、データ処理システム２００は、例えばオペレーティング・システム・ファイルまたはユーザが生成したデータあるいはその両方を記憶するための不揮発性メモリを提供するためにフラッシュ・メモリを伴って構成された携帯型コンピューティング・デバイスであってもよい。本質的には、データ処理システム２００は、アーキテクチャ上の制限なく、任意の周知または後に開発されたデータ処理システムであってもよい。
【００３７】
特定のアドレスから開始して２倍のＬ２に等しい連続メモリを割り当てることによって、キャッシュ内のすべてのキャッシュ・ラインを完全にテストしてもよい。しかしながら、そのような場合において、実ページ番号（ＲＰＮ）ビットの小さな部分のみがテストされるようにしてもよい。例示の実施形態は、ＲＰＮビットをα、β、およびγビットと称される３つの部分に分割する。割り当てられたメモリは、γ−ＲＰＮビットに依存して特定のキャッシュ・ラインに存在する。α−ＲＰＮビットは、利用可能なメモリに依存して割り当て可能なメモリアドレスの境界を規定する。例示の実施形態における考え方は、α−ＲＰＮおよびγ−ＲＰＮビットを別個に考慮してアドレスを生成して割り当てることによって、各ＲＰＮビットについてメモリの１ページのサイズを割り当てるというものである。提示された考え方は、α−ＲＰＮおよびγ−ＲＰＮビットと、α−ＲＰＮおよびγ−ＲＰＮビットの組み合わせを知的に選択して、メモリの１ページ分のサイズ割り当てのためのアドレスを取得して、ＲＰＮビットと共に合同クラス毎に異なるキャッシュ・ラインを同時にテストすることになるというものである。このような割り当てによって、例示の実施形態は、全キャッシュ内の合同クラスのすべてと共にキャッシュ・ディレクトリ内にあり得るすべてのＲＰＮビットを確実に対象とするものである。
【００３８】
図３は、例示の一実施形態に係る、キャッシュ・ディレクトリ内の実ページ番号（ＲＰＮ）アドレス・ビットをテストするためのキャッシュ・テスト・アプリケーションの機能ブロック図を示す。キャッシュ・ディレクトリ内のＲＰＮアドレス・ビットのテストは、チップ認証においてより多くの対象範囲を提供するものであり、ＲＰＮの実施において任意の（複数の）バグをよりよく特定できるものである。キャッシュ・テスト・アプリケーション３０２は、既存のキャッシュ・ライン・テストと共に、キャッシュ・ディレクトリ３０４内のＲＰＮアドレス・ビットについて、最適な対象範囲および最小限の時間で最大のストレスを与えることになるメモリの割り当てを決定するための最適なアルゴリズムを用いる。キャッシュ・テスト・アプリケーション３０２がキャッシュ・ディレクトリ３０４内のＲＰＮアドレス・ビットを最適化するために、仕様検索モジュール３０５がキャッシュ仕様データ構造３０６からキャッシュの仕様を検索する。キャッシュ仕様データ構造３０６は、図２のメイン・メモリ２０８などのデータ構造であってもよい。キャッシュ仕様は、キャッシュのサイズ、キャッシュの連想度、キャッシュ内のページのサイズ、キャッシュ内のキャッシュ・ラインのサイズなどを含んでもよい。例示の本実施形態においては、キャッシュのサイズはバイト単位で２ｐによって表されてもよく、連想度は２ｋによって表されてもよく、ページのサイズはバイト単位で２ｏによって表されてもよく、キャッシュ・ラインのサイズもバイト単位で２ｃで表されてもよい。キャッシュは、サイズがアーキテクチャに依存するキャッシュ・ラインからなる。よって、キャッシュのキャッシュ・ラインの総数は、キャッシュのサイズをキャッシュのキャッシュ・ラインのサイズで除することによって決定されてもよく、これは２ｐ−ｃで表されてもよい。
【００３９】
連想度によっては、メイン・メモリ内の位置は、キャッシュ内におけるキャッシュ・ライン数と同数にキャッシュされてもよい。連想度が２ｋである場合、メイン・メモリ内の各位置は、２ｋ分のキャッシュ・ラインにキャッシュされてもよい。この２ｋ分のキャッシュ・ラインの群は、特定のメモリ位置をキャッシュする限りにおいてそれらは互い位置合同しているので、合同クラスと称されてもよい。合同クラスの総数は、キャッシュ・ライン数を連想度で除することによって決定されてもよく、２ｐ−ｃ−ｋで表されてもよい。
【００４０】
例示の実施形態において、ページ割り当てモジュール３０８がメモリの１ページ分のサイズを１回割り当てる場合には、キャッシュ・テスト・アプリケーション３０２は、複数の合同クラスを１回テストすることができてもよい。１ページ内の合同クラスの数は、ページのサイズをキャッシュ・ラインのサイズで除することによって計算されてもよく、２ｏ−ｃで表されてもよい。よって、各合同クラスを１回テストするために必要なページの総数は、ＣＯＮＧＳＥＴＳＩＺＥと称されてもよく、これは、合同クラスの総数を１ページ内の合同クラスの数で除することによって決定されてもよく、２ｐ−ｃ−ｋ−（ｏ−ｃ）で表されてもよい。例示の実施形態において、各合同クラスをテストするのに必要なページの総数は、γ−ＲＰＮ３１２で表されるようなＲＰＮアドレス３１０内の最も右側にあるビットとして特定される。ＲＰＮアドレス３１０のサイズは一例に過ぎず、例示の実施形態は、ＲＰＮアドレス３１０は他の構成を有してもよいことを認めるものである。
【００４１】
キャッシュ・テスト・アプリケーション３０２が動作するキャッシュのサイズは、通常大きくない。例示の実施形態は、テストされる利用可能なメモリ上の上限および下限があってもよいことを認めるものである。よって、例示の実施形態は、キャッシュ・テスト・アプリケーション３０２が動作し得る利用可能なメモリ領域を、下限はＬＯで、上限はＨＩでそれぞれ示す。割り当てが行われ得る範囲を規定するようなＲＰＮアドレス３１０内の対応ビットが特定されてもよく、それぞれｈビット３１４およびｌビット３１６で表される。限界特定モジュール３１８がｈビット３１４を計算するためには、限界特定モジュール３１８は、２ｈキロバイト＜ＨＩであって２ｈ＋１キロバイト＞ＨＩであるようにＲＰＮアドレス３１０内のｈビット３１４を特定する。同様に、限界特定モジュール３１８がｌビット３１６を特定するためには、限界特定モジュール３１８は、２ｌキロバイト＞ＬＯであって２ｌ−１キロバイト＜ＬＯであるようにＲＰＮアドレス３１０内のｌビット３１６を特定する。
【００４２】
ｌビット３１６を下回りかつｈビット３１４を上回るＲＰＮアドレス３１０内のメモリは割り当てられなくてもよい。ｌビット３１６の場合には、ビット複製モジュール３２２がこれらのビットを、αビットで表されるｌビット３１６より大きなあるビットと組み合わせて複製してもよく、よって、領域３２０はα−ＲＰＮ３２０として示されてもよい。ビットは、メモリの制限によって複製されてもよい。例示の実施形態は領域（α−ＲＰＮ３２０）から少なくとも１ビットを選択するという制約があってもよいので、ｌビット３１６を下回りかつｈビット３１４を上回る位置領域３２０は、選択的にではなく制約によって複製されてもよい。例示の実施形態は、α−ＲＰＮ３２０を、オペレーティング・システムが常駐する領域にメモリが割り当てられていないか、または利用可能なメモリよりも高いところにある領域にメモリが割り当てられていないことを保証するために設定される必要があるビットとして規定する。ｈビット３１４の左側にある領域３２４内のビットは、テストされなくてもよい。ｈビット３１４の左側にある領域３２４内の任意のビットに対応するアドレスは、物理的なメモリのＨＩ限界よりも大きなアドレスに対応することになろう。
【００４３】
よって、ＲＰＮアドレス３１０内のビットは、説明を簡略にするために、３つの部分に
分割されてもよい。
１．第１の部分は、ＲＰＮアドレス３１０のビットｈビット３１４からビットｌビット３１６までであって、α−ＲＰＮ３２０として規定される。
２．第２の部分は、ビットｌ＋１から５１−（ｐ−ｋ−ｏ＋１）であって、β−ＲＰＮ３２６として規定される。
３．第３の部分は、ビットｐ−ｋ−ｏ−１から５１−ｏであって、γ−ＲＰＮ３１２として規定される。
【００４４】
限界特定モジュール３１８がＲＰＮアドレス３１０内のｈビット３１４およびｌビット３１６を特定すると、ランダムｘ値生成器モジュール３２８が、ｘがＲａｎｄｒａｎｇｅ（ｌ，ｈ）と等しくなるように、ｈビット３１４とｌビット３１６との間のランダム値ｘを生成する。ランダムｘ値生成器モジュール３２８によるランダム値ｘの生成は、α−ＲＰＮ３２０からビットを選択する。ｘ番目のビットのみを「オン」に設定することによって与えられたアドレスは、ａｄｄｒ＝１＜＜ｘによって与えられ、チェック・アドレス・モジュール３３０が、ａｄｄｒ＜＝ＨＩかつａｄｄｒ＞＝ＬＯを保証するようにチェックを行う。アドレスが確認されると、ランダムｙ値生成器モジュール３３２が、ｙがＲａｎｄｒａｎｇｅ（０，ＣＯＮＧＳＥＴＳＩＺＥ−１）に等しくなるように、０からＣＯＮＧＥＳＥＴＳＩＺＥ−１の間の値ｙをランダムに生成する。ランダムｙ値生成器モジュール３３２によるランダム値ｙの生成は、γ−ＲＰＮ３１２から値を選択する。ｙ値は、ＣＯＮＧＳＥＴ番号（キャッシュ内の合同クラスの特定のセット）または指標と称されてもよい。
【００４５】
ｙ番目のＣＯＮＧＳＥＴがページにこれまで何回割り当てられたかを判断するために、ＣＯＮＧＳＥＴ特定モジュール３３４が、ｙというＣＯＮＧＳＥＴ値をチェックする。ｙが２ｋまたは場合によっては２＊２ｋであると判断された場合には、ｙ番目のＣＯＮＧＳＥＴは飽和していると判断される。すなわち、ｙ番目のＣＯＮＧＳＥＴは許容される所定の最大回数割り当てられている。よって、現在のｙ値とは異なる不飽和の合同クラスの異なるセットが割り当てられる必要がある。ランダムｙ値生成器モジュール３３２が飽和していると判断された値ｙをランダムに生成したとＣＯＮＧＳＥＴ特定モジュール３３４が特定した場合には、ＣＯＮＧＳＥＴ特定モジュール３３４は、フェール・カウントを１だけ増分する。
【００４６】
ランダムｙ値生成器モジュール３３２が飽和していると判断された値ｙを所定の回数連続してランダムに生成しているとＣＯＮＧＳＥＴ特定モジュール３３４が判断した場合には、ランダムｙ値生成器モジュール３３２は値ｙをランダムに生成して、スキャニング・モジュール３３６がＲＰＮアドレス３１０をスキャンして、ランダムなｙ値の右から連続して開始する不飽和の第１の指標を決定する。ランダムに生成されたｙ値の右へ向かうすべての指標が飽和している場合には、スキャニング・モジュール３３６は、指標０から開始してランダムに生成されたｙ値−１の指標が到達するまでスキャンする。スキャニング・モジュール３３６が不飽和のｙ値を特定すると、ページ割り当てモジュール３０８は、特定されたｙ値または１＜＜ｘ＋ｙのアドレスにページを割り当てて、関連付けられたＣＯＮＧＳＥＴ値を１だけ増分して、フェール（ｆａｉｌ）カウントを０に等しく設定する。このページ割り当て処理は、対象とする必要があるかまたはすべてのキャッシュを飽和させる必要があるページすべてが割り当てられるまで継続する。
【００４７】
キャッシュ・ディレクトリ３０４内のＲＰＮアドレス・ビットをテストするキャッシュ・テスト・アプリケーション３０２の一例は以下の通りである。キャッシュ・テスト・アプリケーション３０２がキャッシュ・ディレクトリ３０４内のＲＰＮアドレス・ビットを最適化するために、仕様検索モジュール３０５は、キャッシュ仕様データ構造３０６からキャッシュの仕様を検索する。本例において、レベル２（ｌｅｖｅｌ ｔｗｏ：Ｌ２）のサイズは、５１２ＫＢ＝２９ＫＢ＝２１９バイトであってもよいので、２ｐで表され得るバイト単位のキャッシュのサイズは、本例においてはｐ＝１９についての値を与える。加えて、本例においては、Ｌ２キャッシュの連想度は８ウェイ＝２３であってもよい、２ｋで表され得るキャッシュの連想度は、本例においてはｋ＝３についての値を与える。さらに、本例においては、Ｌ２キャッシュ内のページのサイズは、４ＫＢ＝２２ＫＢ＝２１２バイトであってもよいので、２ｏで表され得るバイト単位のページのサイズは、本例においてはｏ＝１２についての値を与える。最後に、本例においては、Ｌ２キャッシュ内のキャッシュ・ラインのサイズは１２８バイト＝２７バイトなので、２ｃで表され得るバイト単位のキャッシュ・ラインのサイズは、本例においてはｃ＝７についての値を与える。
【００４８】
よって、本例について、キャッシュのキャッシュ・ラインの総数は、キャッシュのサイズをキャッシュのキャッシュ・ラインのサイズで除することによって決定され、２ｐ−ｃ＝２１９−７＝２１２で表され得る。連想度によっては、キャッシュ内にあるキャッシュ・ラインの数だけ、メイン・メモリ内の位置がキャッシュされてもよい。本例においては、連想度は２３であるので、メイン・メモリ内の各位置は、８つのキャッシュ・ラインにキャッシュされてもよい。本例において、８つのキャッシュ・ラインの群が合同クラスであって、キャッシュ・ライン数を連想度で除することによって決定される合同クラスの総数は、２ｐ−ｃ−ｋ＝２１９−７−３＝２９＝５１２個の合同クラスで表され得る。
【００４９】
本例において、ページ内の合同クラスの数は、ページのサイズをキャッシュ・ラインのサイズで除することによって計算されてもよく、ページ内の２ｏ−ｃ＝２１２−７＝２５＝３２個の合同クラスで表されてもよい。加えて、各合同クラスを１回テストするために必要ページの総数（ＣＯＮＧＳＥＴＳＩＺＥ）は、合同クラスの総数をページ内の合同クラスの数で除することによって決定され、２ｐ−ｃ−ｋ（ｏ−ｃ）＝２１９−７−３−（１２−７）＝２４＝１６個の各合同クラスをテストするために必要なページの総数で表されてもよい。
【００５０】
図４は、例示の一実施形態に係る、Ｌ２キャッシュ例についてＣＯＮＧＳＥＴＳＩＺＥが１６の場合のテストを表すアレイ例を示す。最初に、アレイ４０２内のＣＯＮＧＳＥＴＳＩＺＥについてのすべてのＣＯＮＧＳＥＴ値が０に初期化される。ＨＩ，ＬＯ，ｈ、およびｌについての値が見つかった後に、上述のようなやり方で、ランダム値ｘおよびランダム値ｙが取得される。ｙが４ということになると仮定すると、ページ割り当てモジュールは、ＣＯＮＧＳＥＴ４内の３２個のＣＯＮＧＣＬＡＳＳ（９７−１２８）をすべて対象とするために、ｙ値または（１＜＜ｘ）＋ｙのアドレスにあるページを割り当てる。アレイ４０４は、４であるｙ値に関連付けられたＣＯＮＧＳＥＴ値を０から１へ更新または増分することを示す。
【００５１】
次の反復手順においてランダム値ｙが０ということになると仮定すると、同様にＣＯＮＧＣＬＡＳＳ（０〜３２）が１回割り当てられ、アレイ４０６に示すように、対応するＣＯＮＧＳＥＴ値０が１に更新または増分される。今度は、次の７回目の反復手順において、生成された値ｙが４だけということになったと仮定する。ページ割り当てモジュールは、反復手順毎に同一の４番目のＣＯＮＧＳＥＴであるＣＯＮＧＣＬＡＳＳ（９７〜１２８）でページを割り当て、関連付けられたＣＯＮＧＳＥＴ値を１だけ増分する。このＣＯＮＧＳＥＴは、このように７回以上も対象とされている。ｙ値である４に対応するＣＯＮＧＳＥＴ値は、アレイ４０８に示すように、これら７回の割り当て後に８に更新される。
【００５２】
次の反復手順において、ランダム値ｙが再び４ということになると、ページ割り当てモジュールによるページ割り当ては、このアドレスについては行われるべきでない（１＜＜ｘ＋ｙであって、ｈとｌと間のランダム値ｘが各反復手順毎に生成されることに留意）。なぜならば、本例では許可されていない、ＣＯＮＧＣＬＡＳＳ（９７〜１２８）の９回の割り当てを意味することになるからである。よって、４というｙ値は飽和しているか、または所定の最大回数割り当てられており、アレイは以前と同じ状態のままである。その後、ランダムｙ値生成器は、ｙ値を再びランダムに生成し、ｙが不飽和でない値になった場合に、上述と同様に割り当てが行われることになる。このランダムに生成されたｙ値が再び飽和する場合には、ランダムｙ値生成器は、もう１回ｙ値をランダムに生成する。ｙ値が不飽和である場合には、上述と同様に割り当てが行われることになる。所定の連続試行数の後にランダムｙ値生成器がｙ値をランダムに生成して飽和することになると、スキャニング・モジュールがＲＰＮアドレスをスキャンして、ランダムに生成されたｙ値の右側へ連続して開始する不飽和の第１のｙ値を決定する。本例において、ランダムに生成されたｙ値の右側へ連続して開始する不飽和の第１のｙ値である４は８になり、その後、当該ｙ値は９というｙ値であることになろう。アレイ４１０は、９であるｙ値の０から１への更新を示す。
【００５３】
ランダムに生成されたｙ値の右側へ連続したｙ値のすべてが飽和した場合には、スキャニング・モジュールが０というｙ値から開始して、−１というランダムに生成されたｙ値に到達するまでスキャンする。アレイ４１２は、ランダムに生成されたｙ値が１３であって、１４および１５というｙ値が飽和している場合を示す。本例と同様に、スキャニング・モジュールは、０というｙ値からスキャニングを戻し、本例においては、０というｙ値が不飽和であるとわかる。その後、上述と同様に割り当てが行われることになるので、０というｙ値に対応して割り当てられたページが増分される。このように、８＊１６回の割り当てが行われた最後の反復手順において、ＣＯＮＧＳＥＴ内のすべてのＹ値は、アレイ４１４に示すように、８というＣＯＮＧＳＥＴ値を有することになる。
【００５４】
図５および図６は、例示の一実施形態に係る、キャッシュ・ディレクトリ内の実ページ番号（ＲＰＮ）アドレス・ビットをテストするためのキャッシュ・テスト・アプリケーションの動作例を示す。動作が開始されると、キャッシュ・テスト・アプリケーションは、仕様検索モジュールを使用して、キャッシュ仕様データ構造からキャッシュの仕様を検索する（ステップ５０２）。キャッシュ仕様は、キャッシュのサイズ、キャッシュの連想度、ページのサイズ、キャッシュ・ラインのサイズなどを含んでもよい。キャッシュの仕様を使用して、キャッシュ・テスト・アプリケーションは、バイト単位でのキャッシュのサイズ、キャッシュの連想度、バイト単位でのキャッシュ内のページのサイズ、またはバイト単位でのキャッシュ・ラインのサイズあるいはそれらすべてを特定する（ステップ５０４）。これらの変数を使用して、キャッシュ・テスト・アプリケーションは、キャッシュのキャッシュ・ラインの総数、キャッシュ内の合同クラスの総数、１ページ内の合同クラスの数、または、ＣＯＮＧＥＳＴＳＩＺＥと称される、各合同クラスを１回テストするために必要なページの総数あるいはそれらすべてを決定する（ステップ５０６）。
【００５５】
ＲＰＮアドレスを使用して、限界特定モジュールが、キャッシュ・テスト・アプリケーションが動作し得る使用可能なメモリ領域を決定し、これは、下限はＬＯで、上限はＨＩでそれぞれ特定される（ステップ５０８）。その後、限界特定モジュールは、ページ割り当てがページ割り当てモジュールによって行われ得る範囲を特定し、これはｈおよびｌによって表されてもよい（ステップ５１０）。
【００５６】
図３における限界特定モジュール３１８がＲＰＮアドレス内でビットｈとビットｌとを特定すると、ランダムｘ値生成器モジュールが、ｘがＲａｎｄｒａｎｇｅ（ｌ，ｈ）と等しくなるように、ビットｈとビットｌとの間のランダム値ｘを生成する（ステップ５１２）。ランダムｘ値生成器モジュールによるランダム値ｘの生成は、ＲＰＮアドレスのα−ＲＰＮからビットを選択する。その後、ランダムｙ値生成器モジュールが、ＲＰＮアドレスのγ−ＲＰＮから値を選択することによって、ランダム値ｙを生成する（ステップ５１４）。ランダムｙ値生成器によるランダム値ｙの生成は、テスト対象のキャッシュの部分に関連付けられた合同クラスから合同クラスを選択する。
【００５７】
ｙ番目のＣＯＮＧＳＥＴがページ内に既に何回割り当てられたかを判断するために、ＣＯＮＧＳＥＴ特定モジュールが、特定されたｙ値に関連付けられたＣＯＮＧＳＥＴ値をチェックして、特定されたｙ値が飽和したか、所定の最大回数割り当てられたかを判断する（ステップ５１６）。ステップ５１６においてＣＯＮＧＳＥＴ値が飽和していない場合には、ページ割り当てモジュールは、ｙ値または１＜＜ｘ＋ｙに関連付けられたアドレスにページを割り当て、関連付けられたＣＯＮＧＳＥＴ値を１だけ増分して、フェール・カウントを０に等しく設定する（ステップ５１８）。その後、ページ割り当てモジュールは、キャッシュ全体を対象とするのに必要な全ページが割り当てられたかを判断する（ステップ５２０）。ステップ５２０においてすべてのページが割り当てられた場合には、動作は終了する。ステップ５２０においてページがすべて割り当てられているわけではない場合には、動作はステップ５１２へ戻る。
【００５８】
ステップ５１６に戻って、ランダムに生成されたｙ値が飽和していると、ＣＯＮＧＳＥＴ特定モジュールは、フェール・カウントを１だけ増分し（ステップ５２２）、フェール・カウントが所定の値に等しいかどうかが判断される（ステップ５２４）。ステップ５２４においてフェール・カウントが所定の値と等しくない場合には、動作はステップ５１４へ戻る。ステップ５２４においてフェール・カウントが所定の値と等しい場合には、ランダムｙ値生成器は、ｙ値をランダムに生成する（ステップ５２６）。スキャニング・モジュールが、ＲＰＮアドレスをスキャンして、ランダムｙ値から右側へ連続して開始してＣＯＮＧＳＥＴＳＩＺＥの最大値まで、不飽和の第１のｙ値を特定する（ステップ５２８）。その後、スキャニング・モジュールは、不飽和のｙ値がＣＯＮＧＳＥＴＳＩＺＥの最大値に到達する前に不飽和のｙ値が特定されたかどうかを判断する（ステップ５３０）。ステップ５３０においてＣＯＮＧＳＥＴＳＩＺＥの最大値に到達する前にスキャニング・モジュールが不飽和のｙ値を特定した場合には、スキャニング・モジュールは、決定されたＣＯＮＧＳＥＴのｙ値をランダムに生成されたｙ値に割り当て（ステップ５３２）、動作はステップ５１８へ進む。
【００５９】
ステップ５３０においてスキャニング・モジュールが最大のＣＯＮＧＳＥＴＳＩＺＥに到達し、不飽和のｙ値を特定できなかった場合には、スキャニング・モジュールは、０というｙ値から開始して、ランダムに生成された−１というｙ値に到達するまでスキャンする（ステップ５３４）。その後、スキャニング・モジュールは、０というｙ値から開始してランダムに生成された−１というｙ値まで、不飽和のｙ値が特定可能かどうかを判断する。ステップ５３６においてスキャニング・モジュールが不飽和のｙを０というｙ値からの範囲内で識別してランダムに生成された−１というｙ値までスキャンした場合には、スキャニング・モジュールは、決定されたＣＯＮＧＳＥＴのｙ値をランダムに生成されたｙ値に割り当て（ステップ５３２）、動作はステップ５１８へ進む。ステップ５３６においてスキャニング・モジュールが０というｙ値から開始してランダムに生成された−１というｙ値まで不飽和のｙ値を特定できなかった場合には、キャッシュ・テスト・アプリケーションは、すべてのページが割り当てられていると特定し、動作は終了する。
【００６０】
よって、例示の実施形態は、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための機構を提供する。例示の実施形態は、ＲＰＮビットをα、β、およびγビットと称される３つの部分に分割する。割り当てられたメモリは、γ−ＲＰＮビットに依存して特定のキャッシュ・ラインに存在する。α−ＲＰＮビットは、利用可能なメモリに依存して割り当て可能なメモリアドレスの境界を規定する。例示の実施形態における考え方は、α−ＲＰＮおよびγ−ＲＰＮビットを別個に考慮してメモリを割り当てることによって、割り当て用のアドレスを生成するというものである。提示された考え方は、α−ＲＰＮおよびγ−ＲＰＮビットと、α−ＲＰＮおよびγ−ＲＰＮビットの組み合わせとを知的に選択して、割り当てのためのアドレスを取得して、合同クラス毎に異なるキャッシュ・ラインと共にＲＰＮビットを同時にテストすることになるというものである。このような割り当てによって、完全なキャッシュのほか、すべての可能なＲＰＮビットが確実に対象となる。
【００６１】
上述のように、当然のことながら、例示の実施形態は、完全にハードウェアによる実施形態、完全にソフトウェアによる実施形態、または、ハードウェアおよびソフトウェア要素の両方を包含する実施形態の形式を取ってもよい。一実施形態例において、例示の実施形態の機構は、ソフトウェアまたはプログラム・コードで実施され、これにはファームウェア、常駐ソフトウェア、マイクロ・コードなどが含まれるが、これらに限定されない。
【００６２】
プログラム・コードを記憶または実行あるいはその両方を行うのに適したデータ処理システムは、システムバスを通じてメモリ要素に直接または間接的に結合された少なくとも１つのプロセッサを含むことになる。メモリ要素は、プログラム・コードの実際の実行中に用いられるローカル・メモリ、大容量ストレージ、および、実行中に大容量ストレージからコードを検索しなければならない回数を減らすために少なくともいくつかのプログラム・コードの一次的な記憶を提供するキャッシュ・メモリを含むことができる。
【００６３】
入出力すなわちＩ／Ｏデバイス（キーボード、ディスプレイ、ポインティング・デバイスなどを含むが、それらに限定されない）は、直接か、または介在するＩ／Ｏコントローラを通じるかのいずれかで、システムと結合され得る。ネットワーク・アダプタもシステムと結合されて、介在する私設または公衆ネットワークを通じて他のデータ処理システムまたはリモート・プリンタまたは記憶デバイスと結合されるようになってもよい。モデム、ケーブル・モデム、およびイーサネット（Ｒ）カードは、現在利用可能なネットワーク・アダプタの種類のうちのいくつかに過ぎない。
【００６４】
本発明の説明は、例示および説明の目的で提示されてきており、網羅的であることも、または開示された形式の本発明に制限されるものでもない。数多くの変更および変形が当業者にとって明らかであろう。実施形態は、本発明の原則および実際の応用を最もよく説明するために、かつ、予期される特定の使用に適するような様々な修正を伴う様々な実施形態について本発明を当業者が理解できるようにするために選択および記載されたものである。
【符号の説明】
【００６５】
３０２ キャッシュ・テスト・アプリケーション
３０４ キャッシュ・ディレクトリ
３０５ 仕様検索モジュール
３０６ キャッシュ仕様
３０８ ページ割り当てモジュール
３１８ 限界特定モジュール
３２２ ビット複製モジュール
３２８ ランダムｘ値生成器モジュール
３３０ チェック・アドレス・モジュール
３３２ ランダムｙ値生成器モジュール
３３４ ＣＯＮＧＳＥＴ特定モジュール
３３６ スキャニング・モジュール
【技術分野】
【０００１】
本発明は、一般的には、改良されたデータ処理装置および方法に関し、より特定的には、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための装置および方法に関する。
【背景技術】
【０００２】
従来のコンピュータ・システムは、１つ以上の処理ユニットを有し得、当該処理ユニットは、入力／出力（Ｉ／Ｏ）デバイス（表示モニタ、キーボード、または常設の記憶デバイスなど）、処理ユニットがプログラム命令を実行するのに使用されるメモリ・デバイス（ランダム・アクセス・メモリ、すなわちＲＡＭ）、およびコンピュータに最初に電源が投入される度に周辺機器のうちの１つ（通常は常設のメモリ・デバイス）からオペレーティング・システムをシークしてロードするのが主要な目的であるファームウェアを含む様々な周辺デバイスに接続されている。処理ユニットは、汎用の相互接続またはバスを含む様々な手段によって周辺デバイスと通信する。また、従来のコンピュータ・システムは、例えばモデムまたはプリンタに接続するためのシリアル・ポートおよびパラレル・ポートなどの数多くのさらなる構成要素を含み得る。従来のコンピューティング・システムにおいて使用され得る構成要素は他にもあって、例えば、ビデオ・ディスプレイ・モニタを制御するためにディスプレイ・アダプタが使用されることもあるし、メモリにアクセスするためにメモリ・コントローラが使用されることもあることを、当業者はさらに理解するだろう。入出力（Ｉ／Ｏ）デバイスを直接バスに接続する代わりに、Ｉ／Ｏデバイスは、バスへのＩ／Ｏブリッジにさらに接続されている２次（Ｉ／Ｏ）バスに接続されてもよい。また、コンピュータは、２つより多くの処理ユニットを有してもよい。
【０００３】
対称マルチプロセッサ（ｓｙｍｍｅｔｒｉｃ ｍｕｌｔｉ−ｐｒｏｃｅｓｓｏｒ：ＳＭＰ）コンピュータにおいて、処理ユニットのすべては、一般的には同一であり、すなわち、それらすべては命令およびプロトコルの一般的なセットまたはサブセットを使用して動作し、一般的には同一のアーキテクチャを有する。そのようなＳＭＰコンピュータは、プロセッサ・コアを含む処理ユニットを含むことがあり、当該プロセッサ・コアは、コンピュータを動作させるためにプログラム命令を実行する複数のレジスタおよび実行ユニットを有する。また、処理ユニットは、命令キャッシュおよびデータ・キャッシュなどの１つ以上のキャッシュを有し得、当該キャッシュは、高速メモリデバイスを使用して実施される。命令およびデータは、オペランドが命令対データである動作を処理ユニットが要求しているかどうかを示す信号を検査することによって各キャッシュに向けて送り出されてもよい。キャッシュは、メモリから値をロードするという時間がかかるステップを回避することによって処理を高速化するために、プロセッサによって繰り返しアクセスされ得るような値を一時的に記憶するために通常使用される。これらのキャッシュは、プロセッサ・コアと共に単一の集積チップ上に一体化してパッケージされる場合には「オン・ボード（ｏｎ−ｂｏａｒｄ）」と称される。各キャッシュは、一般的には、プロセッサ・コアとキャッシュ・メモリとの間のデータの転送を管理するキャッシュ・コントローラに関連付けられている。
【０００４】
処理ユニットは、オン・ボードの第１レベル・キャッシュをサポートする第２レベル（Ｌ２）キャッシュなどのさらなるキャッシュを含んでもよい。言い換えれば、Ｌ２キャッシュは、メモリとオン・ボードのキャッシュとの間の媒介物として作用し、オン・ボードのキャッシュよりも遥かに多くの情報量（命令およびデータ）を記憶することができるが、アクセスには時間がかかるのが不利益な点である。例えば、Ｌ２キャッシュは、２５６または５１２キロバイトの記憶容量を有するチップであってもよいが、プロセッサは、全ストレージが６４キロバイトであるオン・ボード・キャッシュを有するＩＢＭＰｏｗｅｒＰＣ（ＩＢＭ社の登録商標）６０４シリーズのプロセッサであってもよい。Ｌ２キャッシュは、一般的にはバスに接続され、メモリからプロセッサ・コアへの情報の全ローディングは、Ｌ２キャッシュを通じて行われなければならない。加えて、コンピューティング・システムは、シリアルに接続されたキャッシュのレベルが数多くあるマルチ・レベルのキャッシュ階層を含んでもよい。
【０００５】
キャッシュは、様々な命令およびデータ値を個別に記憶する数多くの「ブロック」を有する。任意のキャッシュ内のブロックについて、「セット」と称されるブロックの群に分割される。セットは、所与のメモリ・ブロックが存在し得るキャッシュ・ブロックの集まりである。任意の所与のメモリ・ブロックには、予め設定されたマッピング機能に従って当該ブロックがマップされ得る固有のセットがキャッシュ内にある。１セット内のブロック数は、当該キャッシュの連想度（ａｓｓｏｃｉａｔｉｖｉｔｙ）と称され、例えば、２ウェイ（ｗａｙ）セット・アソシアティブは、任意の所与のメモリ・ブロックについて、当該メモリ・ブロックがマッピングされ得るブロックがキャッシュ内に２つあるが、メイン・メモリ内にあるいくつかの異なるブロックは任意の所与のセットにマッピングされ得ることを意味する。１ウェイ・セット・アソシアティブ・キャッシュは、直接マッピングされる。すなわち、特定のメモリ・ブロックを包含し得るキャッシュ・ブロックは１つだけである。メモリ・ブロックが任意のキャッシュ・ブロックを占有し得る場合には、キャッシュは、完全にアソシアティブであるといえ、すなわち、セットは１つであり、アドレス・タグは、メモリ・ブロックのフル・アドレスである。
【０００６】
キャッシュ・ライン（ブロック）の一例は、アドレス・タグ・フィールドと、状態ビット・フィールドと、包括ビット・フィールドと、実命令またはデータを記憶するための値フィールドとを含む。状態ビット・フィールドおよび包括ビット・フィールドは、マルチプロセッサ・コンピュータ・システムにおけるキャッシュの一貫性を維持するために使用される。アドレス・タグは、対応するメモリ・ブロックのフル・アドレスのサブセットである。入力有効アドレスと、アドレス・タグ・フィールド内のタグのうちの１つとの比較一致は、キャッシュ「ヒット」を示す。キャッシュ内のすべてのアドレス・タグ（および時には状態ビット・フィールドおよび包括ビット・フィールド）の集まりは、ディレクトリと称され、すべての値フィールドの集まりは、キャッシュ・エントリ・アレイである。
【０００７】
所与のキャッシュについてのセット内のすべてのブロックがフルであって、フル・セットへマッピングするメモリ位置に対する「読み出し」または「書き出し」という要求を当該キャッシュが受信すると、キャッシュは、セット内に現在あるブロックのうちの１つを「エビクト（ｅｖｉｃｔ）」しなければならない。キャッシュは、エビクトすべきブロックを、当業者に周知の複数の手段（最長時間未使用法（ｌｅａｓｔ ｒｅｃｅｎｔｌｙ ｕｓｅｄ：ＬＲＵ）、ランダム、擬似ＬＲＵなど）のうちの１つによって選択する。選択されたブロック内のデータが修正される場合には、当該データは、メモリ階層のうちで最下位から２番目に低いレベルに書き込まれ、このレベルは、他のキャッシュ（Ｌ１またはオン・ボードのキャッシュの場合）またはメイン・メモリ（Ｌ２キャッシュの場合）であってもよい。包含の原理により、階層の最下層は、書き込まれた修正済みのデータを保持するために利用可能なブロックを既に有することになる。しかしながら、選択されたブロック内のデータが修正されない場合には、ブロックはそのまま破棄され、階層内の再開から２番目に低いレベルに書き込まれない。階層の１つのレベルからブロックを除去するというこの処理は、「エビクション（ｅｖｉｃｔｉｏｎ）」として知られている。この処理の終わりでは、キャッシュは、もはや、エビクトされたブロックのコピーを有さない。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
プロセッサ上で実行する手順（プログラム）の中には、限られた数のセット（合同（ｃｏｎｇｒｕｅｎｃｅ）クラス）を繰り返し使用するのでキャッシュが効率的でなくなるという予期せぬ効果を有するものがある。言い換えると、ある手順が少数の合同クラス要素内で多数のエビクションを生じさせる一方で多数の他の要素を使用しない場合には、メモリ・レイテンシ遅延が増加する。この効果はストライド（ｓｔｒｉｄｅ）と称され、合同マッピング機能と、特定の手順がメイン・メモリ・デバイス内にメモリ・ブロックを割り当てている手法とに関連する。
【０００９】
一般的には、データ処理システム内のキャッシュのテストは、Ｌ２キャッシュ量の２倍の割り当てを要する。単一の指標に指標付けするページが既存のエントリを除去またはエビクトさせる場合には、このＬ２キャッシュ量を使用することによって、キャッシュの中には、ローリングまたは置換を要するものもあり、よって、より多くのストレスおよびキャッシュ・ラインのテストを生じさせることがある。キャッシュの同一のストレスを達成するためにキャッシュのメモリ量を増加させる場合があるが、メモリを追加するのは最善策ではない。キャッシュ・ディレクトリ内の実ページ番号（ｒｅａｌ ｐａｇｅ ｎｕｍｂｅｒｓ：ＲＰＮ）ビットをテストするために、テスト・プログラムは、典型的には、大量のメモリを経由する。製造およびシミュレーション・テストにおいても、時間は重要な要素である。カードの製造、モジュールの製造、およびウェハの製造において利用可能な総テスト時間量は、典型的には秒単位である。しかしながら、シミュレーションにおいても、周期が正確なモデルでシミュレートするために時間の制約があるのは明白である。
【課題を解決するための手段】
【００１０】
例示の一実施形態において、データ処理システムにおいて、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための方法が提供される。例示の実施形態は、テスト対象のキャッシュに関連付けられたキャッシュ・ディレクトリの実ページ番号ビットをテストするために、当該キャッシュの仕様が検索（ｒｅｔｒｉｅｖｅ）される。例示の実施形態は、キャッシュの仕様を使用してページ割り当てを行うためにキャッシュ・ディレクトリの実ページ番号アドレス内の範囲を特定する。例示の実施形態は、テスト対象の実ページ番号ビットの部分を特定するランダム値ｘを生成する。例示の実施形態は、テスト対象のキャッシュの部分内の合同クラスのセットから第１の合同クラスを特定する第１のランダム値ｙを生成する。例示の実施形態は、第１のランダム値ｙに関連付けられた第１の合同クラスが所定の回数割り当てられたかどうかを判断する。例示の実施形態は、第１のランダム値ｙに関連付けられた第１の合同クラスについて、メモリの１ページ分のサイズを割り当て、第１の合同クラスに関連付けられた第１の割り当て値を１の値で増分する。
【００１１】
例示の他の実施形態において、コンピュータ読み出し可能なプログラムを有するコンピュータ使用可能または読み出し可能な媒体を備えるコンピュータ・プログラム製品が提供される。当該コンピュータ読み出し可能なプログラムは、コンピューティング・デバイス上で実行されると、方法の例示の実施形態に関して先に概説した様々な動作およびその組み合わせを当該コンピューティング・デバイスに行わせる。
【００１２】
さらに他の例示の実施形態において、システム／装置が提供される。当該システム／装置は、１つ以上のプロセッサと、当該１つ以上のプロセッサに結合されたメモリとを備えてもよい。当該メモリは、当該１つ以上のプロセッサによって実行されると、方法の例示の実施形態に関して先に概説した様々な動作およびその組み合わせを当該１つ以上のプロセッサに行わせる命令を備えてもよい。
【００１３】
本発明のこれらおよび他の特徴および利点は、本発明の実施形態例の以下の詳細な説明において説明されるか、または当該詳細な説明を考慮すれば当業者にとって明らかになるだろう。
【図面の簡単な説明】
【００１４】
【図１】例示の実施形態の局面が実施され得る分散型データ処理システム例の実体表現を示す。
【図２】例示の実施形態の局面が実施され得るデータ処理システム例のブロック図を示す。
【図３】例示の一実施形態に係る、キャッシュ・ディレクトリ内の実ページ番号（ＲＰＮ）アドレス・ビットをテストするためのキャッシュ・テスト・アプリケーションの機能ブロック図を示す。
【図４】例示の一実施形態に係る、Ｌ２キャッシュ例についてＣＯＮＧＳＥＴＳＩＺＥが１６の場合のテストを表すアレイ例を示す。
【図５】例示の一実施形態に係る、キャッシュ・ディレクトリ内の実ページ番号（ＲＰＮ）アドレス・ビットをテストするためのキャッシュ・テスト・アプリケーションの動作例を示す。
【図６】例示の一実施形態に係る、キャッシュ・ディレクトリ内の実ページ番号（ＲＰＮ）アドレス・ビットをテストするためのキャッシュ・テスト・アプリケーションの動作例を示す。
【発明を実施するための形態】
【００１５】
本発明ならびに好ましい使用態様およびさらにその目的および利点は、添付の図面と共に解釈される場合に例示の実施形態の以下の詳細な説明を参照することによって、最もよく理解されるだろう。
【００１６】
当業者によって理解されるように、本発明は、システム、方法、またはコンピュータ・プログラム製品によって具体化されてもよい。したがって、本発明は、完全にハードウェアによる実施形態、完全にソフトウェアによる実施形態（ファームウェア、常駐ソフトウェア、マイクロ・コードなどを含む）、またはすべてが一般的に本明細書において「回路」、「モジュール」、または「システム」と称され得るソフトウェアの局面とハードウェアの局面とを組みあわせる実施形態の形式を取ってもよい。さらに、本発明は、媒体において具体化されたコンピュータ使用可能なプログラム・コードを有する有形の媒体表現に具体化されたコンピュータ・プログラム製品の形式を取ってもよい。
【００１７】
１つ以上のコンピュータ使用可能またはコンピュータ読み出し可能な媒体の任意の組み合わせが使用されてもよい。コンピュータ使用可能またはコンピュータ読み出し可能な媒体は、例えば、電子、磁気、光学、電磁、赤外線、または半導体のシステム、装置、デバイス、または伝搬媒体であってもよいが、これらに限定されない。コンピュータ読み出し可能な媒体のより特定的な例（非網羅的リスト）は、以下のものを含むことになろう。１つ以上の電線を有する電気接続、携帯型コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ：ＲＡＭ）、読み出し専用メモリ（ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ：ＲＯＭ）、消去可能プログラム可能読み出し専用メモリ（ｅｒａｓａｂｌｅ ｐｒｏｇｒａｍｍａｂｌｅ ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ：ＥＰＲＯＭ、またはフラッシュ・メモリ）、光ファイバ、携帯型コンピュータ・ディスク読み出し専用メモリ（ｃｏｍｐａｃｔ ｄｉｓｃ ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ：ＣＤＲＯＭ）、光学記憶デバイス、インターネットまたはイントラネットをサポートするなどの送信媒体、または磁気記憶デバイスである。なお、コンピュータ使用可能またはコンピュータ読み出し可能な媒体は、プログラムが印刷されている用紙または他の適切な媒体でさえあり得る。というのは、当該プログラムは、例えば当該用紙または他の媒体の光学スキャニングを介して電子的に取り入れられ、その後、コンパイルされ、解釈され、または必要があれば別の適切な手法で処理され、その後コンピュータ・メモリに記憶され得るからである。本明細書の場合においては、コンピュータ使用可能またはコンピュータ読み出し可能な媒体は、命令実行システム、装置またはデバイスによってまたはそれとともに使用されるプログラムを包含、記憶、通信、伝搬、または転送できる任意の媒体であってもよい。コンピュータ使用可能な媒体は、ベースバンドでまたは搬送波の一部としてのいずれかで、共に具体化されたコンピュータ使用可能なプログラム・コードを伴う伝搬データ信号を含んでもよい。コンピュータ使用可能なプログラム・コードは、無線、有線ライン、光ファイバ・ケーブル、無線周波数（ｒａｄｉｏ ｆｒｅｑｕｅｎｃｙ：ＲＦ）などの任意の適切な媒体を使用して送信されてもよい。
【００１８】
本発明の動作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ（商標）、Ｓｍａｌｌｔａｌｋ（商標）、またはＣ＋＋などのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語または同様のプログラミング言語などの従来の手続きプログラミング言語を含む１つ以上のプログラミング言語の任意の組み合わせで書き込まれてもよい。プログラム・コードは、ユーザのコンピュータ上で全面的に、ユーザのコンピュータ上で部分的に、独立型のソフトウェア・パッケージとして、ユーザのコンピュータ上で部分的にかつリモート・コンピュータ上で部分的に、またはリモート・コンピュータまたはサーバ上で全面的に実行してもよい。後者の場合において、リモート・コンピュータは、ローカル・エリア・ネットワーク（ｌｏｃａｌ ａｒｅａ ｎｅｔｗｏｒｋ：ＬＡＮ）またはワイド・エリア・ネットワーク（ｗｉｄｅ ａｒｅａ ｎｅｔｗｏｒｋ：ＷＡＮ）を含む任意の種類のネットワークを通じてユーザのコンピュータに接続されてもよく、または、当該接続は、（例えば、インターネット・サービス・プロバイダを使用してインターネットを通じて）外部コンピュータに対してなされてもよい。
【００１９】
本発明の例示の実施形態に係る方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート図またはブロック図あるいはその両方を参照して、例示の実施形態を以下に説明する。フローチャート図またはブロック図あるいはその両方の各ブロック、およびフローチャート図またはブロック図あるいはその両方におけるブロックの組み合わせは、コンピュータ・プログラム命令によって実施され得ることが理解されるだろう。これらのコンピュータ・プログラム命令は、汎用コンピュータ、専用コンピュータ、または他のプログラム可能データ処理装置のプロセッサに対して提供されて、コンピュータまたは他のプログラム可能なデータ処理装置のプロセッサを介して実行する命令が、フローチャートまたはブロック図あるいはその両方における１つまたは複数のブロックにおいて指定される機能／動作を実施するための手段を作成するようにマシンを生じさせてもよい。
【００２０】
これらのコンピュータ・プログラム命令は、コンピュータ読み出し可能な媒体に記憶されてもよく、当該コンピュータ読み出し可能な媒体は、コンピュータ読み出し可能な媒体に記憶された命令がフローチャートまたはブロック図あるいはその両方における１つまたは複数のブロックにおいて指定される機能／動作を実施する命令手段を含む製品を生じさせるような特定な手法で、コンピュータまたは他のプログラム可能なデータ処理装置を機能させることができる。
【００２１】
コンピュータ・プログラム命令は、コンピュータまたは他のプログラム可能なデータ処理装置にロードされて、一連の動作ステップが当該コンピュータまたは他のプログラム可能な装置上で実施されて、当該コンピュータまたは他のプログラム可能な装置上で実行する命令がフローチャートまたはブロック図あるいはその両方における１つまたは複数のブロックにおいて指定される機能／動作を実施するための処理を提供するように、コンピュータによって実施された処理を生じさせるようにしてもよい。
【００２２】
図面におけるフローチャートおよびブロック図は、本発明の様々な実施形態に係るシステム、方法、およびコンピュータ・プログラム製品の実現可能な実施のアーキテクチャ、機能、および動作を示す。これに関して、フローチャートまたはブロック図における各ブロックは、指定された（複数の）論理機能を実施するための１つ以上の実行可能な命令を備えるモジュール、セグメント、またはコードの一部を表してもよい。また、ある代替実施においては、ブロックに記された機能は、図に記された順序とは異なるように生じてもよいことに注意すべきである。例えば、連続して示された２つのブロックは、実際には、実質的に並列的に実行されてもよく、または、関与する機能によっては、ブロックはときには逆順で実行されてもよい。また、ブロック図またはフローチャート図あるいはその両方における各ブロックおよびブロック図またはフローチャート図あるいはその両方におけるブロックの組み合わせは、指定された機能または動作あるいは専用ハードウェアとコンピュータ命令との組み合わせを行う、専用ハードウェア・ベースのシステムによって実施され得ることに注意されたい。
【００２３】
例示の実施形態は、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための機構を提供する。よって、例示の実施形態は、分散型データ処理環境または単一のデータ処理デバイスなどを含む数多くの異なる種類のデータ処理環境において利用されてもよい。例示の実施形態の特定の要素および機能を説明するための状況を提供するために、例示の実施形態の局面が実施され得る環境例として図１および図２が以下に提供される。図１および図２に続く説明では、主に、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための機構を単一のデータ処理デバイスによって実施することに主に主眼が置かれることになるが、これは一例に過ぎず、本発明の特徴に対する制限を何ら表明するものでも示唆するものでもない。逆に、例示の実施形態は、キャッシュ・ディレクトリ内の実ページ番号ビットがテストされ得る分散型データ処理環境および実施形態を含むことが意図されている。図示の環境に対する数多くの変更が、本発明の精神および範囲から逸脱することなく行われてもよい。
【００２４】
今度は図面を参照すると、図１は、例示の実施形態の局面が実施され得る分散型データ処理システム例の実体表現を示す。分散型データ処理システム１００は、例示の実施形態の局面が実施され得るコンピュータのネットワークを含んでもよい。分散型データ処理システム１００は、少なくとも１つのネットワーク１０２を包含し、当該ネットワーク１０２は、分散型データ処理システム１００内で共に接続された様々なデバイスおよびコンピュータ間の通信リンクを提供するために使用される媒体である。ネットワーク１０２は、有線、無線通信リンクまたは光ファイバ・ケーブルなどの接続を含んでもよい。
【００２５】
図示の例において、サーバ１０４およびサーバ１０６は、記憶ユニット１０８と共にネットワーク１０２に接続される。加えて、クライアント１１０，１１２，および１１４もネットワーク１０２に接続される。これらのクライアント１１０，１１２，および１１４は、例えば、パーソナル・コンピュータまたはネットワーク・コンピュータなどであってもよい。図示の例において、サーバ１０４は、ブート・ファイル、オペレーティング・システムの画像、およびアプリケーションなどのデータをクライアント１１０，１１２，および１１４へ提供する。クライアント１１０，１１２，および１１４は、図示の例におけるサーバ１０４に対するクライアントである。分散型データ処理システム１００は、さらなるサーバ、クライアント、および図示しない他のデバイスを含んでもよい。
【００２６】
図示の例において、分散型データ処理システム１００は、伝送制御プロトコル／インターネット・プロトコル（Ｔｒａｎｓｍｉｓｓｉｏｎ Ｃｏｎｔｒｏｌ Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ：ＴＣＰ／ＩＰ）というプロトコルのスイート（ｓｕｉｔｅ）を使用して互いに通信するネットワークおよびゲートウェイの世界的な集まりを表すネットワーク１０２を伴うインターネットである。インターネットの中心には、主要ノードまたはホスト・コンピュータ間の高速データ通信回線のバックボーンがあり、データおよびメッセージを経路設置する数千の商用、政府、教育、およびその他のコンピュータ・システムからなる。当然ながら、分散型データ処理システム１００は、例えばイントラネット、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）などの複数の異なる種類のネットワークを含んで実施されてもよい。上述のように、図１は一例であって、本発明の異なる実施形態に対してアーキテクチャの制限を加えるものではないので、図１の特定の要素が本発明の例示の実施形態が実施され得る環境に関する制限とみなされるべきではない。
【００２７】
図２を参照すると、例示の実施形態の局面が実施され得るデータ処理システム例のブロック図が示されている。データ処理システム２００は、図１のクライアント１１０などのコンピュータの一例であって、本発明の例示の実施形態のための処理を実施するコンピュータ使用可能なコードまたは命令が位置し得るものである。
【００２８】
図示の例において、データ処理システム２００は、ノース・ブリッジおよびメモリ・コントローラ・ハブ（ｎｏｒｔｈ ｂｒｉｄｇｅ ａｎｄ ｍｅｍｏｒｙ ｃｏｎｔｒｏｌｌｅｒ ｈｕｂ：ＮＢ／ＭＣＨ）２０２と、サウス・ブリッジおよび入出力コントローラ・ハブ（ｓｏｕｔｈ ｂｒｉｄｇｅ ａｎｄ ｉｎｐｕｔ／ｏｕｔｐｕｔ（Ｉ／Ｏ） ｃｏｎｔｒｏｌｌｅｒ ｈｕｂ：ＳＢ／ＩＣＨ）２０４とを含むハブ・アーキテクチャを用いる。処理ユニット２０６、メイン・メモリ２０８、およびグラフィックス・プロセッサ２１０がＮＢ／ＭＣＨ２０２に接続される。グラフィックス・プロセッサ２１０は、アクセラレィティッド・グラフィックス・ポート（ａｃｃｅｌｅｒａｔｅｄ ｇｒａｐｈｉｃｓ ｐｏｒｔ：ＡＧＰ）を通じてＮＢ／ＭＣＨ２０２と接続されてもよい。
【００２９】
図示の例において、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ２１２がＳＢ／ＩＣＨ２０４に接続する。音声アダプタ２１６、キーボードおよびマウス・アダプタ２２０、モデム２２２、読み出し専用メモリ（ＲＯＭ）２２４、ハード・ディスク・ドライブ（ｈａｒｄ ｄｉｓｋ ｄｒｉｖｅ：ＨＤＤ）２２６、ＣＤ−ＲＯＭドライブ２３０、ユニバーサル・シリアル・バス（ｕｎｉｖｅｒｓａｌ ｓｅｒｉａｌ ｂｕｓ：ＵＳＢ）ポートおよび他の通信ポート２３２、ならびにＰＣＩ／ＰＣＩｅデバイス２３４がバス２３８およびバス２４０を通じてＳＢ／ＩＣＨ２０４に接続する。ＰＣＩ／ＰＣＩｅデバイスは、例えばイーサネット（Ｒ）アダプタ、アドイン・カード、およびノートブック・コンピュータ用のＰＣカードを含んでもよい。ＰＣＩはカード・バス・コントローラを使用するが、ＰＣＩｅは使用しない。ＲＯＭ２２４は、例えばフラッシュ基本入出力システム（ｂａｓｉｃ ｉｎｐｕｔ／ｏｕｔｐｕｔ ｓｙｓｔｅｍ：ＢＩＯＳ）であってもよい。
【００３０】
ＨＤＤ２２６およびＣＤ−ＲＯＭドライブ２３０は、バス２４０を通じてＳＢ／ＩＣＨ２０４に接続する。ＨＤＤ２２６およびＣＤ−ＲＯＭドライブ２３０は、例えば、統合ドライブ・エレクトロニクス（ｉｎｔｅｇｒａｔｅｄ ｄｒｉｖｅ ｅｌｅｃｔｒｏｎｉｃｓ：ＩＤＥ）またはシリアル・アドバンスト・テクノロジー・アタッチメント（ｓｅｒｉａｌ ａｄｖａｎｃｅｄ ｔｅｃｈｎｏｌｏｇｙ ａｔｔａｃｈｍｅｎｔ：ＳＡＴＡ）インターフェースを使用してもよい。スーパーＩ／Ｏ（ＳＩＯ）ドライブ２３６がＳＢ／ＩＣＨ２０４に接続されてもよい。
【００３１】
オペレーティング・システムが処理ユニット２０６上で実行される。オペレーティング・システムは、図２におけるデータ処理システム２００内の様々な構成要素の制御を調和させて提供する。クライアントとして、オペレーティング・システムは、マイクロソフト（Ｍｉｃｒｏｓｏｆｔ）（Ｒ）ウィンドウズ（Ｗｉｎｄｏｗｓ）（Ｒ）ＸＰ（マイクロソフトおよびウィンドウズは、米国および他の諸国またはその両方におけるマイクロソフト社の商標である）などの市販のオペレーティング・システムであってもよい。Ｊａｖａ（商標）プログラミング・システムなどのオブジェクト指向プログラミング・システムがオペレーティング・システムと共に実行されてもよく、データ処理システム２００上で実行するＪａｖａ（商標）プログラムまたはアプリケーションからのオペレーティング・システムに対する呼び出しを提供する（Ｊａｖａは、米国および他の諸国またはその両方におけるサン・マイクロシステムズ社の商標である）。
【００３２】
サーバとして、データ処理システム２００は、例えばＩＢＭ（ＩＢＭ社の登録商標）ｅＳｅｒｖｅｒ（商標）Ｓｙｓｔｅｍ ｐ（ＩＢＭ社の登録商標）コンピュータ・システムであってもよく、アドバンスト・インタラクティブ・エグゼキュティブ（Ａｄｖａｎｃｅｄ Ｉｎｔｅｒａｃｔｉｖｅ Ｅｘｅｃｔｕｉｖｅ：ＡＩＸ）（ＩＢＭ社の登録商標）オペレーティング・システムまたはリナックス（ＬＩＮＵＸ）（Ｒ）オペレーティング・システム（ｅＳｅｒｖｅｒ、Ｓｙｓｔｅｍ ｐ、およびＡＩＸは、米国および他の諸国またはその両方におけるＩＢＭ社の商標であり、ＬＩＮＵＸは、米国および他の諸国またはその両方におけるリーナス・トーバルズ（Ｌｉｎｕｓ Ｔｏｒｖａｌｄｓ）の商標である）。データ処理システム２００は、処理ユニット２０６に複数のプロセッサを含む対称マルチプロセッサ（ｓｙｍｍｅｔｒｉｃ ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ：ＳＭＰ）システムであってもよい。代わりに、単一のプロセッサ・システムが用いられてもよい。
【００３３】
オペレーティング・システム、オブジェクト指向プログラミング・システム、ならびにアプリケーションまたはプログラムに関する命令は、ＨＤＤ２２６などの記憶デバイス上にあり、処理ユニット２０６によって実行するためにメイン・メモリ２０８にロードされてもよい。本発明の例示の実施形態についての処理は、処理ユニット２０６がコンピュータ使用可能なプログラム・コードを使用して行われてもよく、コンピュータ使用可能なプログラム・コードは、例えばメイン・メモリ２０８、ＲＯＭ２２４、または例えば１つ以上の周辺デバイス２２６および２３０にあってもよい。
【００３４】
図２に示すようなバス２３８またはバス２４０などのバス・システムは、１つ以上のバスからなってもよい。当然ながら、バス・システムは、任意の種類の通信組織またはアーキテクチャを使用して実施されてもよく、当該通信組織またはアーキテクチャは、それらに付属する異なる構成要素またはデバイス間のデータ転送を提供するものである。図２のモデム２２２またはネットワーク・アダプタ２１２などの通信ユニットは、データを送受信するために使用される１つ以上のデバイスを含んでもよい。メモリは、例えば、図２のメイン・メモリ２０８、ＲＯＭ２２４、またはＮＢ／ＭＣＨ２０２に見受けられるようなキャッシュであってもよい。
【００３５】
図１〜図２におけるハードウェアは実施によって異なってもよいことを当業者は理解するだろう。フラッシュ・メモリ、同等の不揮発性メモリ、または光ディスク・ドライブなどの他の内部ハードウェアまたは周辺機器が、図１〜図２に示すハードウェアに加えてまたはその代わりに使用されてもよい。また、例示の実施形態の処理は、本発明の精神および範囲を逸脱せずに上述のＳＭＰシステム以外のマルチプロセッサ・データ処理システムに適用されてもよい。
【００３６】
さらに、データ処理システム２００は、クライアント・コンピューティング・デバイス、サーバ・コンピューティング・デバイス、タブレット・コンピュータ、ラップトップ・コンピュータ、電話または他の通信デバイス、携帯情報端末（ｐｅｒｓｏｎａｌ ｄｉｇｉｔａｌ ａｓｓｉｓｉｔａｎｔ：ＰＤＡ）などを含む任意の複数の異なるデータ処理システムの形態を取ってもよい。例示のある例においては、データ処理システム２００は、例えばオペレーティング・システム・ファイルまたはユーザが生成したデータあるいはその両方を記憶するための不揮発性メモリを提供するためにフラッシュ・メモリを伴って構成された携帯型コンピューティング・デバイスであってもよい。本質的には、データ処理システム２００は、アーキテクチャ上の制限なく、任意の周知または後に開発されたデータ処理システムであってもよい。
【００３７】
特定のアドレスから開始して２倍のＬ２に等しい連続メモリを割り当てることによって、キャッシュ内のすべてのキャッシュ・ラインを完全にテストしてもよい。しかしながら、そのような場合において、実ページ番号（ＲＰＮ）ビットの小さな部分のみがテストされるようにしてもよい。例示の実施形態は、ＲＰＮビットをα、β、およびγビットと称される３つの部分に分割する。割り当てられたメモリは、γ−ＲＰＮビットに依存して特定のキャッシュ・ラインに存在する。α−ＲＰＮビットは、利用可能なメモリに依存して割り当て可能なメモリアドレスの境界を規定する。例示の実施形態における考え方は、α−ＲＰＮおよびγ−ＲＰＮビットを別個に考慮してアドレスを生成して割り当てることによって、各ＲＰＮビットについてメモリの１ページのサイズを割り当てるというものである。提示された考え方は、α−ＲＰＮおよびγ−ＲＰＮビットと、α−ＲＰＮおよびγ−ＲＰＮビットの組み合わせを知的に選択して、メモリの１ページ分のサイズ割り当てのためのアドレスを取得して、ＲＰＮビットと共に合同クラス毎に異なるキャッシュ・ラインを同時にテストすることになるというものである。このような割り当てによって、例示の実施形態は、全キャッシュ内の合同クラスのすべてと共にキャッシュ・ディレクトリ内にあり得るすべてのＲＰＮビットを確実に対象とするものである。
【００３８】
図３は、例示の一実施形態に係る、キャッシュ・ディレクトリ内の実ページ番号（ＲＰＮ）アドレス・ビットをテストするためのキャッシュ・テスト・アプリケーションの機能ブロック図を示す。キャッシュ・ディレクトリ内のＲＰＮアドレス・ビットのテストは、チップ認証においてより多くの対象範囲を提供するものであり、ＲＰＮの実施において任意の（複数の）バグをよりよく特定できるものである。キャッシュ・テスト・アプリケーション３０２は、既存のキャッシュ・ライン・テストと共に、キャッシュ・ディレクトリ３０４内のＲＰＮアドレス・ビットについて、最適な対象範囲および最小限の時間で最大のストレスを与えることになるメモリの割り当てを決定するための最適なアルゴリズムを用いる。キャッシュ・テスト・アプリケーション３０２がキャッシュ・ディレクトリ３０４内のＲＰＮアドレス・ビットを最適化するために、仕様検索モジュール３０５がキャッシュ仕様データ構造３０６からキャッシュの仕様を検索する。キャッシュ仕様データ構造３０６は、図２のメイン・メモリ２０８などのデータ構造であってもよい。キャッシュ仕様は、キャッシュのサイズ、キャッシュの連想度、キャッシュ内のページのサイズ、キャッシュ内のキャッシュ・ラインのサイズなどを含んでもよい。例示の本実施形態においては、キャッシュのサイズはバイト単位で２ｐによって表されてもよく、連想度は２ｋによって表されてもよく、ページのサイズはバイト単位で２ｏによって表されてもよく、キャッシュ・ラインのサイズもバイト単位で２ｃで表されてもよい。キャッシュは、サイズがアーキテクチャに依存するキャッシュ・ラインからなる。よって、キャッシュのキャッシュ・ラインの総数は、キャッシュのサイズをキャッシュのキャッシュ・ラインのサイズで除することによって決定されてもよく、これは２ｐ−ｃで表されてもよい。
【００３９】
連想度によっては、メイン・メモリ内の位置は、キャッシュ内におけるキャッシュ・ライン数と同数にキャッシュされてもよい。連想度が２ｋである場合、メイン・メモリ内の各位置は、２ｋ分のキャッシュ・ラインにキャッシュされてもよい。この２ｋ分のキャッシュ・ラインの群は、特定のメモリ位置をキャッシュする限りにおいてそれらは互い位置合同しているので、合同クラスと称されてもよい。合同クラスの総数は、キャッシュ・ライン数を連想度で除することによって決定されてもよく、２ｐ−ｃ−ｋで表されてもよい。
【００４０】
例示の実施形態において、ページ割り当てモジュール３０８がメモリの１ページ分のサイズを１回割り当てる場合には、キャッシュ・テスト・アプリケーション３０２は、複数の合同クラスを１回テストすることができてもよい。１ページ内の合同クラスの数は、ページのサイズをキャッシュ・ラインのサイズで除することによって計算されてもよく、２ｏ−ｃで表されてもよい。よって、各合同クラスを１回テストするために必要なページの総数は、ＣＯＮＧＳＥＴＳＩＺＥと称されてもよく、これは、合同クラスの総数を１ページ内の合同クラスの数で除することによって決定されてもよく、２ｐ−ｃ−ｋ−（ｏ−ｃ）で表されてもよい。例示の実施形態において、各合同クラスをテストするのに必要なページの総数は、γ−ＲＰＮ３１２で表されるようなＲＰＮアドレス３１０内の最も右側にあるビットとして特定される。ＲＰＮアドレス３１０のサイズは一例に過ぎず、例示の実施形態は、ＲＰＮアドレス３１０は他の構成を有してもよいことを認めるものである。
【００４１】
キャッシュ・テスト・アプリケーション３０２が動作するキャッシュのサイズは、通常大きくない。例示の実施形態は、テストされる利用可能なメモリ上の上限および下限があってもよいことを認めるものである。よって、例示の実施形態は、キャッシュ・テスト・アプリケーション３０２が動作し得る利用可能なメモリ領域を、下限はＬＯで、上限はＨＩでそれぞれ示す。割り当てが行われ得る範囲を規定するようなＲＰＮアドレス３１０内の対応ビットが特定されてもよく、それぞれｈビット３１４およびｌビット３１６で表される。限界特定モジュール３１８がｈビット３１４を計算するためには、限界特定モジュール３１８は、２ｈキロバイト＜ＨＩであって２ｈ＋１キロバイト＞ＨＩであるようにＲＰＮアドレス３１０内のｈビット３１４を特定する。同様に、限界特定モジュール３１８がｌビット３１６を特定するためには、限界特定モジュール３１８は、２ｌキロバイト＞ＬＯであって２ｌ−１キロバイト＜ＬＯであるようにＲＰＮアドレス３１０内のｌビット３１６を特定する。
【００４２】
ｌビット３１６を下回りかつｈビット３１４を上回るＲＰＮアドレス３１０内のメモリは割り当てられなくてもよい。ｌビット３１６の場合には、ビット複製モジュール３２２がこれらのビットを、αビットで表されるｌビット３１６より大きなあるビットと組み合わせて複製してもよく、よって、領域３２０はα−ＲＰＮ３２０として示されてもよい。ビットは、メモリの制限によって複製されてもよい。例示の実施形態は領域（α−ＲＰＮ３２０）から少なくとも１ビットを選択するという制約があってもよいので、ｌビット３１６を下回りかつｈビット３１４を上回る位置領域３２０は、選択的にではなく制約によって複製されてもよい。例示の実施形態は、α−ＲＰＮ３２０を、オペレーティング・システムが常駐する領域にメモリが割り当てられていないか、または利用可能なメモリよりも高いところにある領域にメモリが割り当てられていないことを保証するために設定される必要があるビットとして規定する。ｈビット３１４の左側にある領域３２４内のビットは、テストされなくてもよい。ｈビット３１４の左側にある領域３２４内の任意のビットに対応するアドレスは、物理的なメモリのＨＩ限界よりも大きなアドレスに対応することになろう。
【００４３】
よって、ＲＰＮアドレス３１０内のビットは、説明を簡略にするために、３つの部分に
分割されてもよい。
１．第１の部分は、ＲＰＮアドレス３１０のビットｈビット３１４からビットｌビット３１６までであって、α−ＲＰＮ３２０として規定される。
２．第２の部分は、ビットｌ＋１から５１−（ｐ−ｋ−ｏ＋１）であって、β−ＲＰＮ３２６として規定される。
３．第３の部分は、ビットｐ−ｋ−ｏ−１から５１−ｏであって、γ−ＲＰＮ３１２として規定される。
【００４４】
限界特定モジュール３１８がＲＰＮアドレス３１０内のｈビット３１４およびｌビット３１６を特定すると、ランダムｘ値生成器モジュール３２８が、ｘがＲａｎｄｒａｎｇｅ（ｌ，ｈ）と等しくなるように、ｈビット３１４とｌビット３１６との間のランダム値ｘを生成する。ランダムｘ値生成器モジュール３２８によるランダム値ｘの生成は、α−ＲＰＮ３２０からビットを選択する。ｘ番目のビットのみを「オン」に設定することによって与えられたアドレスは、ａｄｄｒ＝１＜＜ｘによって与えられ、チェック・アドレス・モジュール３３０が、ａｄｄｒ＜＝ＨＩかつａｄｄｒ＞＝ＬＯを保証するようにチェックを行う。アドレスが確認されると、ランダムｙ値生成器モジュール３３２が、ｙがＲａｎｄｒａｎｇｅ（０，ＣＯＮＧＳＥＴＳＩＺＥ−１）に等しくなるように、０からＣＯＮＧＥＳＥＴＳＩＺＥ−１の間の値ｙをランダムに生成する。ランダムｙ値生成器モジュール３３２によるランダム値ｙの生成は、γ−ＲＰＮ３１２から値を選択する。ｙ値は、ＣＯＮＧＳＥＴ番号（キャッシュ内の合同クラスの特定のセット）または指標と称されてもよい。
【００４５】
ｙ番目のＣＯＮＧＳＥＴがページにこれまで何回割り当てられたかを判断するために、ＣＯＮＧＳＥＴ特定モジュール３３４が、ｙというＣＯＮＧＳＥＴ値をチェックする。ｙが２ｋまたは場合によっては２＊２ｋであると判断された場合には、ｙ番目のＣＯＮＧＳＥＴは飽和していると判断される。すなわち、ｙ番目のＣＯＮＧＳＥＴは許容される所定の最大回数割り当てられている。よって、現在のｙ値とは異なる不飽和の合同クラスの異なるセットが割り当てられる必要がある。ランダムｙ値生成器モジュール３３２が飽和していると判断された値ｙをランダムに生成したとＣＯＮＧＳＥＴ特定モジュール３３４が特定した場合には、ＣＯＮＧＳＥＴ特定モジュール３３４は、フェール・カウントを１だけ増分する。
【００４６】
ランダムｙ値生成器モジュール３３２が飽和していると判断された値ｙを所定の回数連続してランダムに生成しているとＣＯＮＧＳＥＴ特定モジュール３３４が判断した場合には、ランダムｙ値生成器モジュール３３２は値ｙをランダムに生成して、スキャニング・モジュール３３６がＲＰＮアドレス３１０をスキャンして、ランダムなｙ値の右から連続して開始する不飽和の第１の指標を決定する。ランダムに生成されたｙ値の右へ向かうすべての指標が飽和している場合には、スキャニング・モジュール３３６は、指標０から開始してランダムに生成されたｙ値−１の指標が到達するまでスキャンする。スキャニング・モジュール３３６が不飽和のｙ値を特定すると、ページ割り当てモジュール３０８は、特定されたｙ値または１＜＜ｘ＋ｙのアドレスにページを割り当てて、関連付けられたＣＯＮＧＳＥＴ値を１だけ増分して、フェール（ｆａｉｌ）カウントを０に等しく設定する。このページ割り当て処理は、対象とする必要があるかまたはすべてのキャッシュを飽和させる必要があるページすべてが割り当てられるまで継続する。
【００４７】
キャッシュ・ディレクトリ３０４内のＲＰＮアドレス・ビットをテストするキャッシュ・テスト・アプリケーション３０２の一例は以下の通りである。キャッシュ・テスト・アプリケーション３０２がキャッシュ・ディレクトリ３０４内のＲＰＮアドレス・ビットを最適化するために、仕様検索モジュール３０５は、キャッシュ仕様データ構造３０６からキャッシュの仕様を検索する。本例において、レベル２（ｌｅｖｅｌ ｔｗｏ：Ｌ２）のサイズは、５１２ＫＢ＝２９ＫＢ＝２１９バイトであってもよいので、２ｐで表され得るバイト単位のキャッシュのサイズは、本例においてはｐ＝１９についての値を与える。加えて、本例においては、Ｌ２キャッシュの連想度は８ウェイ＝２３であってもよい、２ｋで表され得るキャッシュの連想度は、本例においてはｋ＝３についての値を与える。さらに、本例においては、Ｌ２キャッシュ内のページのサイズは、４ＫＢ＝２２ＫＢ＝２１２バイトであってもよいので、２ｏで表され得るバイト単位のページのサイズは、本例においてはｏ＝１２についての値を与える。最後に、本例においては、Ｌ２キャッシュ内のキャッシュ・ラインのサイズは１２８バイト＝２７バイトなので、２ｃで表され得るバイト単位のキャッシュ・ラインのサイズは、本例においてはｃ＝７についての値を与える。
【００４８】
よって、本例について、キャッシュのキャッシュ・ラインの総数は、キャッシュのサイズをキャッシュのキャッシュ・ラインのサイズで除することによって決定され、２ｐ−ｃ＝２１９−７＝２１２で表され得る。連想度によっては、キャッシュ内にあるキャッシュ・ラインの数だけ、メイン・メモリ内の位置がキャッシュされてもよい。本例においては、連想度は２３であるので、メイン・メモリ内の各位置は、８つのキャッシュ・ラインにキャッシュされてもよい。本例において、８つのキャッシュ・ラインの群が合同クラスであって、キャッシュ・ライン数を連想度で除することによって決定される合同クラスの総数は、２ｐ−ｃ−ｋ＝２１９−７−３＝２９＝５１２個の合同クラスで表され得る。
【００４９】
本例において、ページ内の合同クラスの数は、ページのサイズをキャッシュ・ラインのサイズで除することによって計算されてもよく、ページ内の２ｏ−ｃ＝２１２−７＝２５＝３２個の合同クラスで表されてもよい。加えて、各合同クラスを１回テストするために必要ページの総数（ＣＯＮＧＳＥＴＳＩＺＥ）は、合同クラスの総数をページ内の合同クラスの数で除することによって決定され、２ｐ−ｃ−ｋ（ｏ−ｃ）＝２１９−７−３−（１２−７）＝２４＝１６個の各合同クラスをテストするために必要なページの総数で表されてもよい。
【００５０】
図４は、例示の一実施形態に係る、Ｌ２キャッシュ例についてＣＯＮＧＳＥＴＳＩＺＥが１６の場合のテストを表すアレイ例を示す。最初に、アレイ４０２内のＣＯＮＧＳＥＴＳＩＺＥについてのすべてのＣＯＮＧＳＥＴ値が０に初期化される。ＨＩ，ＬＯ，ｈ、およびｌについての値が見つかった後に、上述のようなやり方で、ランダム値ｘおよびランダム値ｙが取得される。ｙが４ということになると仮定すると、ページ割り当てモジュールは、ＣＯＮＧＳＥＴ４内の３２個のＣＯＮＧＣＬＡＳＳ（９７−１２８）をすべて対象とするために、ｙ値または（１＜＜ｘ）＋ｙのアドレスにあるページを割り当てる。アレイ４０４は、４であるｙ値に関連付けられたＣＯＮＧＳＥＴ値を０から１へ更新または増分することを示す。
【００５１】
次の反復手順においてランダム値ｙが０ということになると仮定すると、同様にＣＯＮＧＣＬＡＳＳ（０〜３２）が１回割り当てられ、アレイ４０６に示すように、対応するＣＯＮＧＳＥＴ値０が１に更新または増分される。今度は、次の７回目の反復手順において、生成された値ｙが４だけということになったと仮定する。ページ割り当てモジュールは、反復手順毎に同一の４番目のＣＯＮＧＳＥＴであるＣＯＮＧＣＬＡＳＳ（９７〜１２８）でページを割り当て、関連付けられたＣＯＮＧＳＥＴ値を１だけ増分する。このＣＯＮＧＳＥＴは、このように７回以上も対象とされている。ｙ値である４に対応するＣＯＮＧＳＥＴ値は、アレイ４０８に示すように、これら７回の割り当て後に８に更新される。
【００５２】
次の反復手順において、ランダム値ｙが再び４ということになると、ページ割り当てモジュールによるページ割り当ては、このアドレスについては行われるべきでない（１＜＜ｘ＋ｙであって、ｈとｌと間のランダム値ｘが各反復手順毎に生成されることに留意）。なぜならば、本例では許可されていない、ＣＯＮＧＣＬＡＳＳ（９７〜１２８）の９回の割り当てを意味することになるからである。よって、４というｙ値は飽和しているか、または所定の最大回数割り当てられており、アレイは以前と同じ状態のままである。その後、ランダムｙ値生成器は、ｙ値を再びランダムに生成し、ｙが不飽和でない値になった場合に、上述と同様に割り当てが行われることになる。このランダムに生成されたｙ値が再び飽和する場合には、ランダムｙ値生成器は、もう１回ｙ値をランダムに生成する。ｙ値が不飽和である場合には、上述と同様に割り当てが行われることになる。所定の連続試行数の後にランダムｙ値生成器がｙ値をランダムに生成して飽和することになると、スキャニング・モジュールがＲＰＮアドレスをスキャンして、ランダムに生成されたｙ値の右側へ連続して開始する不飽和の第１のｙ値を決定する。本例において、ランダムに生成されたｙ値の右側へ連続して開始する不飽和の第１のｙ値である４は８になり、その後、当該ｙ値は９というｙ値であることになろう。アレイ４１０は、９であるｙ値の０から１への更新を示す。
【００５３】
ランダムに生成されたｙ値の右側へ連続したｙ値のすべてが飽和した場合には、スキャニング・モジュールが０というｙ値から開始して、−１というランダムに生成されたｙ値に到達するまでスキャンする。アレイ４１２は、ランダムに生成されたｙ値が１３であって、１４および１５というｙ値が飽和している場合を示す。本例と同様に、スキャニング・モジュールは、０というｙ値からスキャニングを戻し、本例においては、０というｙ値が不飽和であるとわかる。その後、上述と同様に割り当てが行われることになるので、０というｙ値に対応して割り当てられたページが増分される。このように、８＊１６回の割り当てが行われた最後の反復手順において、ＣＯＮＧＳＥＴ内のすべてのＹ値は、アレイ４１４に示すように、８というＣＯＮＧＳＥＴ値を有することになる。
【００５４】
図５および図６は、例示の一実施形態に係る、キャッシュ・ディレクトリ内の実ページ番号（ＲＰＮ）アドレス・ビットをテストするためのキャッシュ・テスト・アプリケーションの動作例を示す。動作が開始されると、キャッシュ・テスト・アプリケーションは、仕様検索モジュールを使用して、キャッシュ仕様データ構造からキャッシュの仕様を検索する（ステップ５０２）。キャッシュ仕様は、キャッシュのサイズ、キャッシュの連想度、ページのサイズ、キャッシュ・ラインのサイズなどを含んでもよい。キャッシュの仕様を使用して、キャッシュ・テスト・アプリケーションは、バイト単位でのキャッシュのサイズ、キャッシュの連想度、バイト単位でのキャッシュ内のページのサイズ、またはバイト単位でのキャッシュ・ラインのサイズあるいはそれらすべてを特定する（ステップ５０４）。これらの変数を使用して、キャッシュ・テスト・アプリケーションは、キャッシュのキャッシュ・ラインの総数、キャッシュ内の合同クラスの総数、１ページ内の合同クラスの数、または、ＣＯＮＧＥＳＴＳＩＺＥと称される、各合同クラスを１回テストするために必要なページの総数あるいはそれらすべてを決定する（ステップ５０６）。
【００５５】
ＲＰＮアドレスを使用して、限界特定モジュールが、キャッシュ・テスト・アプリケーションが動作し得る使用可能なメモリ領域を決定し、これは、下限はＬＯで、上限はＨＩでそれぞれ特定される（ステップ５０８）。その後、限界特定モジュールは、ページ割り当てがページ割り当てモジュールによって行われ得る範囲を特定し、これはｈおよびｌによって表されてもよい（ステップ５１０）。
【００５６】
図３における限界特定モジュール３１８がＲＰＮアドレス内でビットｈとビットｌとを特定すると、ランダムｘ値生成器モジュールが、ｘがＲａｎｄｒａｎｇｅ（ｌ，ｈ）と等しくなるように、ビットｈとビットｌとの間のランダム値ｘを生成する（ステップ５１２）。ランダムｘ値生成器モジュールによるランダム値ｘの生成は、ＲＰＮアドレスのα−ＲＰＮからビットを選択する。その後、ランダムｙ値生成器モジュールが、ＲＰＮアドレスのγ−ＲＰＮから値を選択することによって、ランダム値ｙを生成する（ステップ５１４）。ランダムｙ値生成器によるランダム値ｙの生成は、テスト対象のキャッシュの部分に関連付けられた合同クラスから合同クラスを選択する。
【００５７】
ｙ番目のＣＯＮＧＳＥＴがページ内に既に何回割り当てられたかを判断するために、ＣＯＮＧＳＥＴ特定モジュールが、特定されたｙ値に関連付けられたＣＯＮＧＳＥＴ値をチェックして、特定されたｙ値が飽和したか、所定の最大回数割り当てられたかを判断する（ステップ５１６）。ステップ５１６においてＣＯＮＧＳＥＴ値が飽和していない場合には、ページ割り当てモジュールは、ｙ値または１＜＜ｘ＋ｙに関連付けられたアドレスにページを割り当て、関連付けられたＣＯＮＧＳＥＴ値を１だけ増分して、フェール・カウントを０に等しく設定する（ステップ５１８）。その後、ページ割り当てモジュールは、キャッシュ全体を対象とするのに必要な全ページが割り当てられたかを判断する（ステップ５２０）。ステップ５２０においてすべてのページが割り当てられた場合には、動作は終了する。ステップ５２０においてページがすべて割り当てられているわけではない場合には、動作はステップ５１２へ戻る。
【００５８】
ステップ５１６に戻って、ランダムに生成されたｙ値が飽和していると、ＣＯＮＧＳＥＴ特定モジュールは、フェール・カウントを１だけ増分し（ステップ５２２）、フェール・カウントが所定の値に等しいかどうかが判断される（ステップ５２４）。ステップ５２４においてフェール・カウントが所定の値と等しくない場合には、動作はステップ５１４へ戻る。ステップ５２４においてフェール・カウントが所定の値と等しい場合には、ランダムｙ値生成器は、ｙ値をランダムに生成する（ステップ５２６）。スキャニング・モジュールが、ＲＰＮアドレスをスキャンして、ランダムｙ値から右側へ連続して開始してＣＯＮＧＳＥＴＳＩＺＥの最大値まで、不飽和の第１のｙ値を特定する（ステップ５２８）。その後、スキャニング・モジュールは、不飽和のｙ値がＣＯＮＧＳＥＴＳＩＺＥの最大値に到達する前に不飽和のｙ値が特定されたかどうかを判断する（ステップ５３０）。ステップ５３０においてＣＯＮＧＳＥＴＳＩＺＥの最大値に到達する前にスキャニング・モジュールが不飽和のｙ値を特定した場合には、スキャニング・モジュールは、決定されたＣＯＮＧＳＥＴのｙ値をランダムに生成されたｙ値に割り当て（ステップ５３２）、動作はステップ５１８へ進む。
【００５９】
ステップ５３０においてスキャニング・モジュールが最大のＣＯＮＧＳＥＴＳＩＺＥに到達し、不飽和のｙ値を特定できなかった場合には、スキャニング・モジュールは、０というｙ値から開始して、ランダムに生成された−１というｙ値に到達するまでスキャンする（ステップ５３４）。その後、スキャニング・モジュールは、０というｙ値から開始してランダムに生成された−１というｙ値まで、不飽和のｙ値が特定可能かどうかを判断する。ステップ５３６においてスキャニング・モジュールが不飽和のｙを０というｙ値からの範囲内で識別してランダムに生成された−１というｙ値までスキャンした場合には、スキャニング・モジュールは、決定されたＣＯＮＧＳＥＴのｙ値をランダムに生成されたｙ値に割り当て（ステップ５３２）、動作はステップ５１８へ進む。ステップ５３６においてスキャニング・モジュールが０というｙ値から開始してランダムに生成された−１というｙ値まで不飽和のｙ値を特定できなかった場合には、キャッシュ・テスト・アプリケーションは、すべてのページが割り当てられていると特定し、動作は終了する。
【００６０】
よって、例示の実施形態は、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための機構を提供する。例示の実施形態は、ＲＰＮビットをα、β、およびγビットと称される３つの部分に分割する。割り当てられたメモリは、γ−ＲＰＮビットに依存して特定のキャッシュ・ラインに存在する。α−ＲＰＮビットは、利用可能なメモリに依存して割り当て可能なメモリアドレスの境界を規定する。例示の実施形態における考え方は、α−ＲＰＮおよびγ−ＲＰＮビットを別個に考慮してメモリを割り当てることによって、割り当て用のアドレスを生成するというものである。提示された考え方は、α−ＲＰＮおよびγ−ＲＰＮビットと、α−ＲＰＮおよびγ−ＲＰＮビットの組み合わせとを知的に選択して、割り当てのためのアドレスを取得して、合同クラス毎に異なるキャッシュ・ラインと共にＲＰＮビットを同時にテストすることになるというものである。このような割り当てによって、完全なキャッシュのほか、すべての可能なＲＰＮビットが確実に対象となる。
【００６１】
上述のように、当然のことながら、例示の実施形態は、完全にハードウェアによる実施形態、完全にソフトウェアによる実施形態、または、ハードウェアおよびソフトウェア要素の両方を包含する実施形態の形式を取ってもよい。一実施形態例において、例示の実施形態の機構は、ソフトウェアまたはプログラム・コードで実施され、これにはファームウェア、常駐ソフトウェア、マイクロ・コードなどが含まれるが、これらに限定されない。
【００６２】
プログラム・コードを記憶または実行あるいはその両方を行うのに適したデータ処理システムは、システムバスを通じてメモリ要素に直接または間接的に結合された少なくとも１つのプロセッサを含むことになる。メモリ要素は、プログラム・コードの実際の実行中に用いられるローカル・メモリ、大容量ストレージ、および、実行中に大容量ストレージからコードを検索しなければならない回数を減らすために少なくともいくつかのプログラム・コードの一次的な記憶を提供するキャッシュ・メモリを含むことができる。
【００６３】
入出力すなわちＩ／Ｏデバイス（キーボード、ディスプレイ、ポインティング・デバイスなどを含むが、それらに限定されない）は、直接か、または介在するＩ／Ｏコントローラを通じるかのいずれかで、システムと結合され得る。ネットワーク・アダプタもシステムと結合されて、介在する私設または公衆ネットワークを通じて他のデータ処理システムまたはリモート・プリンタまたは記憶デバイスと結合されるようになってもよい。モデム、ケーブル・モデム、およびイーサネット（Ｒ）カードは、現在利用可能なネットワーク・アダプタの種類のうちのいくつかに過ぎない。
【００６４】
本発明の説明は、例示および説明の目的で提示されてきており、網羅的であることも、または開示された形式の本発明に制限されるものでもない。数多くの変更および変形が当業者にとって明らかであろう。実施形態は、本発明の原則および実際の応用を最もよく説明するために、かつ、予期される特定の使用に適するような様々な修正を伴う様々な実施形態について本発明を当業者が理解できるようにするために選択および記載されたものである。
【符号の説明】
【００６５】
３０２ キャッシュ・テスト・アプリケーション
３０４ キャッシュ・ディレクトリ
３０５ 仕様検索モジュール
３０６ キャッシュ仕様
３０８ ページ割り当てモジュール
３１８ 限界特定モジュール
３２２ ビット複製モジュール
３２８ ランダムｘ値生成器モジュール
３３０ チェック・アドレス・モジュール
３３２ ランダムｙ値生成器モジュール
３３４ ＣＯＮＧＳＥＴ特定モジュール
３３６ スキャニング・モジュール
【特許請求の範囲】
【請求項１】
データ処理システムにおいて、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための方法であって、
テスト対象のキャッシュに関連付けられた前記キャッシュ・ディレクトリの前記実ページ番号ビットをテストするために、前記キャッシュの仕様を検索するステップと、
前記キャッシュの前記仕様を使用してページ割り当てを行うために、前記キャッシュ・ディレクトリの実ページ番号アドレス内の範囲を特定するステップと、
テスト対象の前記実ページ番号ビットの部分を特定するランダム値ｘを生成するステップと、
テスト対象の前記キャッシュの前記部分内の合同クラスのセットから第１の合同クラスを特定する第１のランダム値ｙを生成するステップと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが所定の回数割り当てられたかどうかを判断するステップと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第１のランダム値ｙに関連付けられた前記第１の合同クラスについて、メモリの１ページ分のサイズを割り当てるステップと、
前記第１の合同クラスに関連付けられた第１の割り当て値を１の値で増分するステップ
とを含む、方法。
【請求項２】
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられたことに応じて、フェール・カウンタを１の値で増分するステップと、
前記フェール・カウンタが所定の値に等しいかどうかを判断するステップと、
前記フェール・カウンタが前記所定の値に等しくないことに応じて、テスト対象の前記キャッシュの前記部分内の合同クラスの前記セットから第２の合同クラスを特定する第２のランダム値ｙを生成するステップと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられたかどうかを判断するステップと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第２のランダム値ｙに関連付けられた前記第２の合同クラスについてメモリの１ページ分のサイズを割り当てるステップと、
前記第２の合同クラスに関連付けられた第２の割り当て値を１の前記値で増分するステップ
とをさらに含む、請求項１に記載の方法。
【請求項３】
前記フェール・カウンタが前記所定の値に等しいことに応じて、第３のランダム値ｙを生成するステップと、
前記所定の回数割り当てられなかった次の合同クラスを特定するステップと、
前記次の合同クラスに関連付けられた次の値ｙを特定するステップと、
前記関連付けられた次の値ｙを使用して、前記次の合同クラスが前記所定の回数割り当てられたかどうかを判断するステップと、
前記次の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第３のランダム値ｙに関連付けられた前記次の合同クラスについてメモリの１ページ分のサイズを割り当てるステップと、
前記次の合同クラスに関連付けられた次の割り当て値を１の前記値で増分するステップ
とをさらに含む、請求項２に記載の方法。
【請求項４】
前記所定の回数割り当てられなかった前記次の合同クラスを特定する前記ステップは、
前記第３のランダム値ｙに関連付けられた第３の合同クラスから合同クラスの前記セットの最大合同セット・サイズまで順に、合同クラスの前記セット内の各合同クラスをスキャンするステップと、
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に、前記所定の回数割り当てられなかった合同クラスを特定するステップ
とを含む、請求項３に記載の方法。
【請求項５】
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に前記所定の回数割り当てられなかった前記合同クラスを特定できなかったことに応じて、合同クラスの前記セット内の最初の合同クラスから前記第３の合同クラスまでだが前記第３の合同クラスは含まないところを、前記所定回数割り当てられなかった前記合同クラスを特定するためにスキャンするステップをさらに含む、請求項４に記載の方法。
【請求項６】
合同クラスの前記セット内のすべての合同クラスについて、ランダム値ｙの前記生成ステップと、前記判断ステップと、前記割り当てステップと、前記増分ステップとを、前記合同クラスのすべてが前記所定の回数割り当てられるまで繰り返すステップをさらに含む、請求項１に記載の方法。
【請求項７】
ページ割り当てを行うために前記キャッシュ・ディレクトリの前記実ページ番号アドレス内の前記範囲を特定する前記ステップは、
前記キャッシュ・ディレクトリ内の実ページ番号ビットと共に前記メモリの領域のテストが行われることになる、前記キャッシュ内の利用可能なメモリ領域を判断するステップ
を含む、請求項１に記載の方法。
【請求項８】
キャッシュ・ディレクトリ内の実ページ番号ビットと共にメモリ領域のテストが行われることになる、前記キャッシュ内の前記利用可能なメモリ領域を判断する前記ステップは、
前記キャッシュのサイズを特定するために必要な、バイト単位での１つ以上の変数と、前記キャッシュの連想度と、前記キャッシュ内のページのバイト単位でのサイズと、キャッシュ・ラインのバイト単位でのサイズとを判断するステップと、
前記キャッシュ・ディレクトリに関連付けられた前記キャッシュのキャッシュ・ラインの総数と、前記キャッシュ内の合同クラスの総数と、前記キャッシュの１ページ内の合同クラスの数と、各合同クラスを１回テストするために必要なページの総数とを判断するステップ
とを含む、請求項７に記載の方法。
【請求項９】
コンピュータ読み出し可能なプログラムが記録されたコンピュータ記録可能な媒体であって、前記コンピュータ読み出し可能なプログラムは、コンピューティング・デバイス上で実行されると、前記コンピューティング・デバイスに、
テスト対象のキャッシュに関連付けられたキャッシュ・ディレクトリの実ページ番号ビットをテストするために、前記キャッシュの仕様を検索することと、
前記キャッシュの前記仕様を使用してページ割り当てを行うために、前記キャッシュ・ディレクトリの実ページ番号アドレス内の範囲を特定することと、
テスト対象の前記実ページ番号ビットの部分を特定するランダム値ｘを生成することと、
テスト対象の前記キャッシュの前記部分内の合同クラスのセットから第１の合同クラスを特定する第１のランダム値ｙを生成することと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが所定の回数割り当てられたかどうかを判断することと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第１のランダム値ｙに関連付けられた前記第１の合同クラスについて、メモリの１ページ分のサイズを割り当てることと、
前記第１の合同クラスに関連付けられた第１の割り当て値を１の値で増分すること
とを行わせる、コンピュータ記録可能な媒体。
【請求項１０】
前記コンピュータ読み出し可能なプログラムは、前記コンピューティング・デバイスに、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられたことに応じて、フェール・カウンタを１の値で増分することと、
前記フェール・カウンタが所定の値に等しいかどうかを判断することと、
前記フェール・カウンタが前記所定の値に等しくないことに応じて、テスト対象の前記キャッシュの前記部分内の合同クラスの前記セットから第２の合同クラスを特定する第２のランダム値ｙを生成することと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられたかどうかを判断することと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第２のランダム値ｙに関連付けられた前記第２の合同クラスについてメモリの１ページ分のサイズを割り当てることと、
前記第２の合同クラスに関連付けられた第２の割り当て値を１の前記値で増分すること
とをさらに行わせる、請求項９に記載のコンピュータ記録可能な媒体。
【請求項１１】
前記コンピュータ読み出し可能なプログラムは、前記コンピューティング・デバイスに、
前記フェール・カウンタが前記所定の値に等しいことに応じて、第３のランダム値ｙを生成することと、
前記所定の回数割り当てられなかった次の合同クラスを特定することと、
前記次の合同クラスに関連付けられた次の値ｙを特定することと、
前記関連付けられた次の値ｙを使用して、前記次の合同クラスが前記所定の回数割り当てられたかどうかを判断することと、
前記次の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第３のランダム値ｙに関連付けられた前記次の合同クラスについてメモリの１ページ分のサイズを割り当てることと、
前記次の合同クラスに関連付けられた次の割り当て値を１の前記値で増分すること
とをさらに行わせる、請求項１０に記載のコンピュータ記録可能な媒体。
【請求項１２】
前記所定の回数割り当てられなかった前記次の合同クラスを特定するために、前記コンピュータ読み出し可能なプログラムは、前記コンピューティング・デバイスに、
前記第３のランダム値ｙに関連付けられた第３の合同クラスから合同クラスの前記セットの最大合同セット・サイズまで順に、合同クラスの前記セット内の各合同クラスをスキャンすることと、
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に、前記所定の回数割り当てられなかった合同クラスを特定すること
とをさらに行わせる、請求項１１に記載のコンピュータ記録可能な媒体。
【請求項１３】
前記コンピュータ読み出し可能なプログラムは、前記コンピューティング・デバイスに、
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に前記所定の回数割り当てられなかった前記合同クラスを特定できなかったことに応じて、合同クラスの前記セット内の最初の合同クラスから前記第３の合同クラスまでだが前記第３の合同クラスは含まないところを、前記所定回数割り当てられなかった前記合同クラスを特定するためにスキャンすることをさらに行わせる、請求項１２に記載のコンピュータ記録可能な媒体。
【請求項１４】
前記コンピュータ読み出し可能なプログラムは、前記コンピューティング・デバイスに、
合同クラスの前記セット内のすべての合同クラスについて、ランダム値ｙを生成し、判断し、割り当て、増分するために、前記合同クラスのすべてが前記所定の回数割り当てられるまで前記コンピュータ読み出し可能なプログラムを繰り返すことをさらに行わせる、請求項９に記載のコンピュータ記録可能な媒体。
【請求項１５】
プロセッサと、
前記プロセッサに結合されたメモリとを備える装置であって、前記メモリは、前記プロセッサによって実行されると、前記プロセッサに、
テスト対象のキャッシュに関連付けられたキャッシュ・ディレクトリの実ページ番号ビットをテストするために、前記キャッシュの仕様を検索することと、
前記キャッシュの前記仕様を使用してページ割り当てを行うために、前記キャッシュ・ディレクトリの実ページ番号アドレス内の範囲を特定することと、
テスト対象の前記実ページ番号ビットの部分を特定するランダム値ｘを生成することと、
テスト対象の前記キャッシュの前記部分内の合同クラスのセットから、第１の合同クラスを特定する第１のランダム値ｙを生成することと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが所定の回数割り当てられたかどうかを判断することと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第１のランダム値ｙに関連付けられた前記第１の合同クラスについて、メモリの１ページ分のサイズを割り当てることと、
前記第１の合同クラスに関連付けられた第１の割り当て値を１の値で増分すること
とを行わせる命令を備える、装置。
【請求項１６】
前記命令は、前記プロセッサに、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられたことに応じて、フェール・カウンタを１の値で増分することと、
前記フェール・カウンタが所定の値に等しいかどうかを判断することと、
前記フェール・カウンタが前記所定の値に等しくないことに応じて、テスト対象の前記キャッシュの前記部分内の合同クラスの前記セットから第２の合同クラスを特定する第２のランダム値ｙを生成することと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられたかどうかを判断することと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第２のランダム値ｙに関連付けられた前記第２の合同クラスについてメモリの１ページ分のサイズを割り当てることと、
前記第２の合同クラスに関連付けられた第２の割り当て値を１の前記値で増分すること
とをさらに行わせる、請求項１５に記載の装置。
【請求項１７】
前記命令は、前記プロセッサに、
前記フェール・カウンタが前記所定の値に等しいことに応じて、第３のランダム値ｙを生成することと、
前記所定の回数割り当てられなかった次の合同クラスを特定することと、
前記次の合同クラスに関連付けられた次の値ｙを特定することと、
前記関連付けられた次の値ｙを使用して、前記次の合同クラスが前記所定の回数割り当てられたかどうかを判断することと、
前記次の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第３のランダム値ｙに関連付けられた前記次の合同クラスについてメモリの１ページ分のサイズを割り当てることと、
前記次の合同クラスに関連付けられた次の割り当て値を１の前記値で増分すること
とをさらに行わせる、請求項１６に記載の装置。
【請求項１８】
前記所定の回数割り当てられなかった前記次の合同クラスを特定するために、前記命令は、前記プロセッサに、
前記第３のランダム値ｙに関連付けられた第３の合同クラスから合同クラスの前記セットの最大合同セット・サイズまで順に、合同クラスの前記セット内の各合同クラスをスキャンすることと、
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に、前記所定の回数割り当てられなかった合同クラスを特定すること
とをさらに行わせる、請求項１７に記載の装置。
【請求項１９】
前記命令は、前記プロセッサに、
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に前記所定の回数割り当てられなかった前記合同クラスを特定できなかったことに応じて、合同クラスの前記セット内の最初の合同クラスから前記第３の合同クラスまでだが前記第３の合同クラスは含まないところを、前記所定回数割り当てられなかった前記合同クラスを特定するためにスキャンすることをさらに行わせる、請求項１８に記載の装置。
【請求項２０】
前記命令は、前記プロセッサに、
合同クラスの前記セット内のすべての合同クラスについて、ランダム値ｙを生成し、判断し、割り当て、増分するために、前記合同クラスのすべてが前記所定の回数割り当てられるまで前記命令を繰り返すことをさらに行わせる、請求項１５に記載の装置。
【請求項１】
データ処理システムにおいて、キャッシュ・ディレクトリ内の実ページ番号ビットをテストするための方法であって、
テスト対象のキャッシュに関連付けられた前記キャッシュ・ディレクトリの前記実ページ番号ビットをテストするために、前記キャッシュの仕様を検索するステップと、
前記キャッシュの前記仕様を使用してページ割り当てを行うために、前記キャッシュ・ディレクトリの実ページ番号アドレス内の範囲を特定するステップと、
テスト対象の前記実ページ番号ビットの部分を特定するランダム値ｘを生成するステップと、
テスト対象の前記キャッシュの前記部分内の合同クラスのセットから第１の合同クラスを特定する第１のランダム値ｙを生成するステップと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが所定の回数割り当てられたかどうかを判断するステップと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第１のランダム値ｙに関連付けられた前記第１の合同クラスについて、メモリの１ページ分のサイズを割り当てるステップと、
前記第１の合同クラスに関連付けられた第１の割り当て値を１の値で増分するステップ
とを含む、方法。
【請求項２】
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられたことに応じて、フェール・カウンタを１の値で増分するステップと、
前記フェール・カウンタが所定の値に等しいかどうかを判断するステップと、
前記フェール・カウンタが前記所定の値に等しくないことに応じて、テスト対象の前記キャッシュの前記部分内の合同クラスの前記セットから第２の合同クラスを特定する第２のランダム値ｙを生成するステップと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられたかどうかを判断するステップと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第２のランダム値ｙに関連付けられた前記第２の合同クラスについてメモリの１ページ分のサイズを割り当てるステップと、
前記第２の合同クラスに関連付けられた第２の割り当て値を１の前記値で増分するステップ
とをさらに含む、請求項１に記載の方法。
【請求項３】
前記フェール・カウンタが前記所定の値に等しいことに応じて、第３のランダム値ｙを生成するステップと、
前記所定の回数割り当てられなかった次の合同クラスを特定するステップと、
前記次の合同クラスに関連付けられた次の値ｙを特定するステップと、
前記関連付けられた次の値ｙを使用して、前記次の合同クラスが前記所定の回数割り当てられたかどうかを判断するステップと、
前記次の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第３のランダム値ｙに関連付けられた前記次の合同クラスについてメモリの１ページ分のサイズを割り当てるステップと、
前記次の合同クラスに関連付けられた次の割り当て値を１の前記値で増分するステップ
とをさらに含む、請求項２に記載の方法。
【請求項４】
前記所定の回数割り当てられなかった前記次の合同クラスを特定する前記ステップは、
前記第３のランダム値ｙに関連付けられた第３の合同クラスから合同クラスの前記セットの最大合同セット・サイズまで順に、合同クラスの前記セット内の各合同クラスをスキャンするステップと、
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に、前記所定の回数割り当てられなかった合同クラスを特定するステップ
とを含む、請求項３に記載の方法。
【請求項５】
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に前記所定の回数割り当てられなかった前記合同クラスを特定できなかったことに応じて、合同クラスの前記セット内の最初の合同クラスから前記第３の合同クラスまでだが前記第３の合同クラスは含まないところを、前記所定回数割り当てられなかった前記合同クラスを特定するためにスキャンするステップをさらに含む、請求項４に記載の方法。
【請求項６】
合同クラスの前記セット内のすべての合同クラスについて、ランダム値ｙの前記生成ステップと、前記判断ステップと、前記割り当てステップと、前記増分ステップとを、前記合同クラスのすべてが前記所定の回数割り当てられるまで繰り返すステップをさらに含む、請求項１に記載の方法。
【請求項７】
ページ割り当てを行うために前記キャッシュ・ディレクトリの前記実ページ番号アドレス内の前記範囲を特定する前記ステップは、
前記キャッシュ・ディレクトリ内の実ページ番号ビットと共に前記メモリの領域のテストが行われることになる、前記キャッシュ内の利用可能なメモリ領域を判断するステップ
を含む、請求項１に記載の方法。
【請求項８】
キャッシュ・ディレクトリ内の実ページ番号ビットと共にメモリ領域のテストが行われることになる、前記キャッシュ内の前記利用可能なメモリ領域を判断する前記ステップは、
前記キャッシュのサイズを特定するために必要な、バイト単位での１つ以上の変数と、前記キャッシュの連想度と、前記キャッシュ内のページのバイト単位でのサイズと、キャッシュ・ラインのバイト単位でのサイズとを判断するステップと、
前記キャッシュ・ディレクトリに関連付けられた前記キャッシュのキャッシュ・ラインの総数と、前記キャッシュ内の合同クラスの総数と、前記キャッシュの１ページ内の合同クラスの数と、各合同クラスを１回テストするために必要なページの総数とを判断するステップ
とを含む、請求項７に記載の方法。
【請求項９】
コンピュータ読み出し可能なプログラムが記録されたコンピュータ記録可能な媒体であって、前記コンピュータ読み出し可能なプログラムは、コンピューティング・デバイス上で実行されると、前記コンピューティング・デバイスに、
テスト対象のキャッシュに関連付けられたキャッシュ・ディレクトリの実ページ番号ビットをテストするために、前記キャッシュの仕様を検索することと、
前記キャッシュの前記仕様を使用してページ割り当てを行うために、前記キャッシュ・ディレクトリの実ページ番号アドレス内の範囲を特定することと、
テスト対象の前記実ページ番号ビットの部分を特定するランダム値ｘを生成することと、
テスト対象の前記キャッシュの前記部分内の合同クラスのセットから第１の合同クラスを特定する第１のランダム値ｙを生成することと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが所定の回数割り当てられたかどうかを判断することと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第１のランダム値ｙに関連付けられた前記第１の合同クラスについて、メモリの１ページ分のサイズを割り当てることと、
前記第１の合同クラスに関連付けられた第１の割り当て値を１の値で増分すること
とを行わせる、コンピュータ記録可能な媒体。
【請求項１０】
前記コンピュータ読み出し可能なプログラムは、前記コンピューティング・デバイスに、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられたことに応じて、フェール・カウンタを１の値で増分することと、
前記フェール・カウンタが所定の値に等しいかどうかを判断することと、
前記フェール・カウンタが前記所定の値に等しくないことに応じて、テスト対象の前記キャッシュの前記部分内の合同クラスの前記セットから第２の合同クラスを特定する第２のランダム値ｙを生成することと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられたかどうかを判断することと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第２のランダム値ｙに関連付けられた前記第２の合同クラスについてメモリの１ページ分のサイズを割り当てることと、
前記第２の合同クラスに関連付けられた第２の割り当て値を１の前記値で増分すること
とをさらに行わせる、請求項９に記載のコンピュータ記録可能な媒体。
【請求項１１】
前記コンピュータ読み出し可能なプログラムは、前記コンピューティング・デバイスに、
前記フェール・カウンタが前記所定の値に等しいことに応じて、第３のランダム値ｙを生成することと、
前記所定の回数割り当てられなかった次の合同クラスを特定することと、
前記次の合同クラスに関連付けられた次の値ｙを特定することと、
前記関連付けられた次の値ｙを使用して、前記次の合同クラスが前記所定の回数割り当てられたかどうかを判断することと、
前記次の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第３のランダム値ｙに関連付けられた前記次の合同クラスについてメモリの１ページ分のサイズを割り当てることと、
前記次の合同クラスに関連付けられた次の割り当て値を１の前記値で増分すること
とをさらに行わせる、請求項１０に記載のコンピュータ記録可能な媒体。
【請求項１２】
前記所定の回数割り当てられなかった前記次の合同クラスを特定するために、前記コンピュータ読み出し可能なプログラムは、前記コンピューティング・デバイスに、
前記第３のランダム値ｙに関連付けられた第３の合同クラスから合同クラスの前記セットの最大合同セット・サイズまで順に、合同クラスの前記セット内の各合同クラスをスキャンすることと、
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に、前記所定の回数割り当てられなかった合同クラスを特定すること
とをさらに行わせる、請求項１１に記載のコンピュータ記録可能な媒体。
【請求項１３】
前記コンピュータ読み出し可能なプログラムは、前記コンピューティング・デバイスに、
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に前記所定の回数割り当てられなかった前記合同クラスを特定できなかったことに応じて、合同クラスの前記セット内の最初の合同クラスから前記第３の合同クラスまでだが前記第３の合同クラスは含まないところを、前記所定回数割り当てられなかった前記合同クラスを特定するためにスキャンすることをさらに行わせる、請求項１２に記載のコンピュータ記録可能な媒体。
【請求項１４】
前記コンピュータ読み出し可能なプログラムは、前記コンピューティング・デバイスに、
合同クラスの前記セット内のすべての合同クラスについて、ランダム値ｙを生成し、判断し、割り当て、増分するために、前記合同クラスのすべてが前記所定の回数割り当てられるまで前記コンピュータ読み出し可能なプログラムを繰り返すことをさらに行わせる、請求項９に記載のコンピュータ記録可能な媒体。
【請求項１５】
プロセッサと、
前記プロセッサに結合されたメモリとを備える装置であって、前記メモリは、前記プロセッサによって実行されると、前記プロセッサに、
テスト対象のキャッシュに関連付けられたキャッシュ・ディレクトリの実ページ番号ビットをテストするために、前記キャッシュの仕様を検索することと、
前記キャッシュの前記仕様を使用してページ割り当てを行うために、前記キャッシュ・ディレクトリの実ページ番号アドレス内の範囲を特定することと、
テスト対象の前記実ページ番号ビットの部分を特定するランダム値ｘを生成することと、
テスト対象の前記キャッシュの前記部分内の合同クラスのセットから、第１の合同クラスを特定する第１のランダム値ｙを生成することと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが所定の回数割り当てられたかどうかを判断することと、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第１のランダム値ｙに関連付けられた前記第１の合同クラスについて、メモリの１ページ分のサイズを割り当てることと、
前記第１の合同クラスに関連付けられた第１の割り当て値を１の値で増分すること
とを行わせる命令を備える、装置。
【請求項１６】
前記命令は、前記プロセッサに、
前記第１のランダム値ｙに関連付けられた前記第１の合同クラスが前記所定の回数割り当てられたことに応じて、フェール・カウンタを１の値で増分することと、
前記フェール・カウンタが所定の値に等しいかどうかを判断することと、
前記フェール・カウンタが前記所定の値に等しくないことに応じて、テスト対象の前記キャッシュの前記部分内の合同クラスの前記セットから第２の合同クラスを特定する第２のランダム値ｙを生成することと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられたかどうかを判断することと、
前記第２のランダム値ｙに関連付けられた前記第２の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第２のランダム値ｙに関連付けられた前記第２の合同クラスについてメモリの１ページ分のサイズを割り当てることと、
前記第２の合同クラスに関連付けられた第２の割り当て値を１の前記値で増分すること
とをさらに行わせる、請求項１５に記載の装置。
【請求項１７】
前記命令は、前記プロセッサに、
前記フェール・カウンタが前記所定の値に等しいことに応じて、第３のランダム値ｙを生成することと、
前記所定の回数割り当てられなかった次の合同クラスを特定することと、
前記次の合同クラスに関連付けられた次の値ｙを特定することと、
前記関連付けられた次の値ｙを使用して、前記次の合同クラスが前記所定の回数割り当てられたかどうかを判断することと、
前記次の合同クラスが前記所定の回数割り当てられなかったことに応じて、前記第３のランダム値ｙに関連付けられた前記次の合同クラスについてメモリの１ページ分のサイズを割り当てることと、
前記次の合同クラスに関連付けられた次の割り当て値を１の前記値で増分すること
とをさらに行わせる、請求項１６に記載の装置。
【請求項１８】
前記所定の回数割り当てられなかった前記次の合同クラスを特定するために、前記命令は、前記プロセッサに、
前記第３のランダム値ｙに関連付けられた第３の合同クラスから合同クラスの前記セットの最大合同セット・サイズまで順に、合同クラスの前記セット内の各合同クラスをスキャンすることと、
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に、前記所定の回数割り当てられなかった合同クラスを特定すること
とをさらに行わせる、請求項１７に記載の装置。
【請求項１９】
前記命令は、前記プロセッサに、
前記第３のランダム値ｙに関連付けられた前記第３の合同クラスから合同クラスの前記セットの前記最大合同セット・サイズまで順に前記所定の回数割り当てられなかった前記合同クラスを特定できなかったことに応じて、合同クラスの前記セット内の最初の合同クラスから前記第３の合同クラスまでだが前記第３の合同クラスは含まないところを、前記所定回数割り当てられなかった前記合同クラスを特定するためにスキャンすることをさらに行わせる、請求項１８に記載の装置。
【請求項２０】
前記命令は、前記プロセッサに、
合同クラスの前記セット内のすべての合同クラスについて、ランダム値ｙを生成し、判断し、割り当て、増分するために、前記合同クラスのすべてが前記所定の回数割り当てられるまで前記命令を繰り返すことをさらに行わせる、請求項１５に記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１０−３３５６４（Ｐ２０１０−３３５６４Ａ）
【公開日】平成２２年２月１２日（２０１０．２．１２）
【国際特許分類】
【出願番号】特願２００９−１５３８９９（Ｐ２００９−１５３８９９）
【出願日】平成２１年６月２９日（２００９．６．２９）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２２年２月１２日（２０１０．２．１２）
【国際特許分類】
【出願日】平成２１年６月２９日（２００９．６．２９）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]