(57)【要約】【課題】特に弱く順序付けられたマルチプロセッサ・システムに関連する、短待ち時間メモリ・システム・アクセスを提供すること。【解決手段】短待ち時間メモリ・システム・アクセスを、弱く順序付けれられたマルチプロセッサ・システムに関連して提供する。マルチプロセッサ内の各プロセッサが、リソースを共用し、各共用リソースは、マルチプロセッサ内の複数のプロセッサの間の同期化のサポートおよびリソースの秩序だった共用を提供するロック装置内の関連するロックを有する。プロセッサは、リソースに関連するロックを所有する時に限ってリソースにアクセスする許可を有し、プロセッサによるロックを所有する試みは、従来のアトミックなロードおよびその後のストアではなく、単一のロード動作だけを必要とし、プロセッサが、読取動作だけを実行し、プロセッサではなくハードウェア・ロック装置が、後続の書込動作を実行する。不連続データ構造の単純な事前取出しも開示される。メモリ・ラインが再定義され、その結果、通常の物理メモリ・データのほかに、すべてのラインに、メモリ内の他のラインをポイントするのに十分に大きいポインタが含まれるようになり、他の予測アルゴリズムではなくこのポインタによって、どのメモリ・ラインを事前取出しするかが決定される。これによって、ハードウェアによって、不連続だが繰り返されるメモリ・アクセス・パターンを効率的に事前取出しできるようになる。
2004529415.tif 000002
【特許請求の範囲】
【請求項１】
マルチプロセッサであって、前記マルチプロセッサ内の各プロセッサが、リソースを共用し、
前記マルチプロセッサ内の複数のプロセッサの間の同期化のサポートおよび前記リソースの秩序だった共用を提供するハードウェア・ロック装置であって、プロセッサが、リソースに関連するロックを所有する時に限って前記リソースへのアクセスの許可を有し、前記プロセッサが、読取動作だけを実行し、前記プロセッサではなく前記ハードウェア・ロック装置が、後続の書込動作を実行するように、プロセッサによるロックを所有する試みが、従来のアトミックなロードおよびそれに続くストアではなく、単一のロード動作だけを必要とする、ハードウェア・ロック装置
を含むマルチプロセッサ。
【請求項２】
前記ハードウェア・ロック装置が、弱く順序付けられたマルチプロセッサ・システムで実施される、請求項１に記載のメモリ・システム。
【請求項３】
前記ハードウェア・ロック装置が、テストアンドセット・ロックを含み、前記テストアンドセット・ロックが、その動作に関してプロセッサによるメモリ読取に頼り、自動的に前記ロックに値を書き込み、前記書込の前に前記ロックに前に保管された値を返す、請求項１に記載のメモリ・システム。
【請求項４】
前記ハードウェア・ロック装置が、チップの一部として実施される、請求項１に記載のメモリ・システム。
【請求項５】
前記ハードウェア・ロック装置が、独立のデバイスとして実施される、請求項１に記載のメモリ・システム。
【請求項６】
各プロセッサが、別々の書込バスおよび読取バスを有し、前記書込バスおよび前記読取バスの動作が、相対的に独立である、請求項１に記載のメモリ・システム。
【請求項７】
前記マルチプロセッサが、マルチプロセッサ・システム・オンチップ（ＳＯＣ）構造を含む、請求項１に記載のメモリ・システム。
【請求項８】
前記マルチプロセッサ・システムが、２つのＣＰＵコアを含み、前記ＣＰＵコアのそれぞれが、内部第１レベル・キャッシュを有し、各プロセッサが、相対的に独立である別々の書込バスおよび読取バスを有する、請求項７に記載のメモリ・システム。
【請求項９】
不連続なデータ構造を事前取出しする方法であって、
前記不連続なデータ構造をポイントし、そのアクセス順序を示すポインタを各データ構造に組み込むステップと、
前記ポインタによって示される前記アクセス順序に基づいてターゲット・データ構造を事前取出しするステップと
を含む方法。
【請求項１０】
不連続に保管されるが同一の順序で繰り返してアクセスされる大きいデータ構造を事前取出しするステップをさらに含む、請求項９に記載の方法。
【請求項１１】
前記事前取出しが、メモリ・ラインに基づき、メモリ・ラインが、メモリがラインに分割されるように、連続する物理メモリ位置の位置合せされたセクションであり、前記ラインのある部分を、所与の時に少なくとも１つのキャッシュに保管することができ、通常の物理メモリ・データの他に、各メモリ・ラインが前記メモリ内の他のメモリ・ラインをポイントするのに十分に大きいポインタを含むように、各メモリ・ラインが、再定義される、請求項９に記載の方法。
【請求項１２】
各メモリ・ラインが、前記データおよび前記ポインタのほかに、前記ポインタを自動的にセットし、使用するアルゴリズムを実施する追加ビットを含む、請求項１１に記載の方法。
【請求項１３】
各メモリ・ラインが、前記ポインタの状況を示す２つのビットを含む、請求項１２に記載の方法。
【請求項１４】
メモリ・ラインがアクセスされ、前記メモリ・ラインが有効なポインタを有しない時に、前記メモリ・ラインが親状況に昇格され、次に取出しを要求されるメモリ・ラインが、その子とみなされ、子メモリ・ラインが既知になった後に、前記親メモリ・ラインの前記ポインタが、前記子メモリ・ラインをポイントし、さらに、保護観察ビットが、前記ポインタが有用でない可能性があることを示すようにセットされるようにする機構によって、前記ポインタがセットされ、前記機構が、子メモリ・ラインが別の後続のメモリ・ラインの親メモリ・ラインでもあるという点で再帰的である、請求項１１に記載の方法。
【請求項１５】
保護観察ポインタがセットされたメモリ・ラインが参照される時に、前記メモリ・ラインが親メモリ・ラインとみなされるが、子メモリ・ラインが取り出されず、次のメモリ・ラインが要求された後に、そのアドレスが前記保護観察子メモリ・ラインの前記ポインタと比較され、これらが一致する場合に、前記親のポインタが既知状況に昇格され、これらが一致しない場合に、前記親のポインタが無効とマークされ、既知ポインタを有するメモリ・ラインが参照される時に、ポイントされる子メモリ・ラインが、即座に事前取出しされ、次に参照されるメモリ・ラインが、その子メモリ・ラインでない場合に、前記親のポインタ状況が、保護観察状況に降格される、請求項１４に記載の方法。
【請求項１６】
前記メモリが、複数の異なるレベルのキャッシュを含み、メモリ・ラインが、異なるレベルのキャッシュの間でメモリ階層の上に移動される際に、前記メモリ・ラインおよびそれに関連するポインタが、一緒のままになり、したがって、事前取出しを実施するキャッシュ・レベルより下のキャッシュ・レベル内のすべての他のキャッシュが、単純に、メモリ・ライン・データと共に前記ポインタをキャッシングする、請求項１１に記載の方法。
【請求項１７】
親子関係を記憶する内容アドレス事前取出しテーブルをさらに含み、前記テーブルが、３つのフィールドすなわち親、子、および状況を有する、請求項１４に記載の方法。
【請求項１８】
メモリ・ラインが、取り出され、無効なポインタを有する時に、次に取り出されるメモリ・ラインが、その子とみなされ、親のポインタに、前記子メモリ・ラインがセットされ、前記ポインタ状況に、保護観察がセットされ、既知ポインタを有するラインが、取り出されるか事前取出しされる時に、ポイントされる前記子メモリ・ラインが、即座に事前取出しされ、
保護観察ポインタまたは既知ポインタを有するメモリ・ラインが、取り出され、前記事前取出しテーブル内で親メモリ・ラインでないことがわかる時に、前記メモリ・ラインが、その子ポインタおよびポインタ状況と共に前記テーブルに入力され、
メモリ・ラインが参照される時に、前記メモリのアドレスが、前記事前取出しテーブル内のすべての前記子ポインタと比較され、一致が見つかる場合に、関連する親の状況が更新され、保護観察ポインタが既知状況に昇格され、さらに、前記事前取出しテーブル内の一致する項目が除去され、複数の子項目が一致する場合に、各子項目が、同一の形で扱われる
請求項１７に記載の方法。
【請求項１９】
項目が、容量の欠如に起因して前記事前取出しテーブルから追い出される時に、前記親のポインタ状況が更新され、有効ポインタが保護観察にされ、保護観察ポインタが無効化され、メモリ・ラインが、キャッシュから追い出され、そのメモリ・ラインが、前記事前取出しテーブル内で親であることがわかる時に、前記テーブル項目も、無効化され、事前取出しテーブル追出しとして扱われる、請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的には短待ち時間メモリ・システムに関し、具体的には、弱く順序付けられた（weakly-ordered）（疎に同期化される（loosely synchronized））マルチプロセッサ・システムに関連し、複数プロセッサのアクティビティの効率的な同期化を提供する。
【０００２】
本発明は、不連続なデータ構造の事前取出しの効率的で単純な方法も提供する。
【０００３】
本発明は、全般的に、たとえば生命科学の分野の計算に適用される、分散メモリ・メッセージ受渡並列コンピュータ設計の分野に関する。
【背景技術】
【０００４】
重要な計算の大きいクラスを、大量並列コンピュータ・システムによって実行することができる。そのようなシステムは、多数の同一の計算ノードからなり、各計算ノードは、通常は、１つまたは複数のＣＰＵ、メモリ、およびそのノードを他のノードに接続する１つまたは複数のネットワーク・インターフェースからなる。
【０００５】
大量並列スーパーコンピュータに関する、２００１年２月２４日出願の米国仮出願番号６０／２７１，１２４に記載のコンピュータでは、システムオンアチップ（ＳＯＣ）技術を活用して、高いスループットを有する、スケーラブルでコスト効率のよいコンピューティング・システムが作成される。ＳＯＣ技術によって、集積された第１レベル・キャッシュを伴うＣＰＵコアを含む組込み構成要素のライブラリを使用して、単一のチップ上でマルチプロセッサ・ノード全体を作ることが可能になった。そのようなパッケージ化によって、ノードの構成要素カウントが大きく減り、信頼性がある大スケール計算機の作成が可能になる。第１レベル・キャッシュは、一般にプロセッサに非常に近いキャッシュであり、一般に、第２レベル・キャッシュと比較した時により小さく、高速であり、第２レベル・キャッシュは、プロセッサから遠く、一般に、より大きく、低速であり、さらに上のレベルのキャッシュについても同様である。
【０００６】
マルチプロセッサが直面する一般的な問題が、リソースの秩序だった共用である。これは、しばしば、ロックの使用を介して達成され、この場合に、プロセッサは、リソースに割り当てられたロックを獲得することによって、そのリソースを使用する使用許可を得る。プロセッサは、ロックを保持（所有）する限り、そのリソースに関する許可を保持し、ロックを解放することによってその許可を放棄する。非常に一般的なタイプのロックが、テストアンドセット・ロックであり、これは、実施が単純で、一般に、十分広範囲に応用できる。
【０００７】
テストアンドセット・ロックは、一般に、実装に関してハードウェアＲＭＷ（read-modify-write）動作に頼る。この動作を用いると、ある値をメモリ位置に書き込み、前にその位置にあった（書込の前）値を返せるようになる。すなわち、この動作は、読取と、その直後の割込みなしの書込からなる。
【０００８】
テストアンドセット・ロックのセマンティクスは、次の通りである。アンロック状態が０、ロック状態が１であるものとする。プロセッサは、ロックに対してＲＭＷ動作を実行することによってロックの獲得を試み、このＲＭＷ動作で書き込まれる値は、１である。返された値が０である場合には、そのロックは、ＲＭＷの前にロック解除されており、１の書込に起因してロックされている。返された値が１である場合には、そのロックは既にロックされており、書込は効果がなかった。ロックを解放するには、単純に０を書き込む。
【０００９】
本発明のもう１つの態様は、事前取出しを含むが、事前取出しは、特にアプリケーションが予測可能なアクセス・パターンを示す時に、キャッシュを含むメモリ・システムの性能を強化する周知の技法である。一般に、事前取出しは、ソフトウェア・ディレクティブの使用を介する、または特殊なハードウェアを介するのいずれかで達成される。順次事前取出しなど、一部のハードウェア方式は、単純であるが、ストライデッド・ストリーム・バッファ（strided stream buffer）などの方式は、より洗練されている。しかし、ハードウェア技法のすべてが、アドレス・シーケンスの予測可能性に頼る。従来の事前取出し技法の完全な調査については、ファンダビール（Vanderwiel）およびリリア（Lilja）を参照されたい。
【００１０】
現代の仮想メモリ・システムは、ハードウェア事前取出しの有効性に影響する可能性がある。というのは、仮想メモリで連続する大きいデータ構造が、物理メモリで連続している必要がなく、ハードウェア事前取出しが、通常は物理メモリ・アドレスを扱うからである。大きいデータ構造が、連続的にトラバースされる場合であっても、しばしばそうであるように、実際のメモリ参照は、連続しておらず、したがって、予測が困難である。しかし、多くのアプリケーションが、非常に反復的に振る舞い、したがって、繰り返されるアクセス・パターンを学習できる機構によって、事前取出しが有効になる可能性がある。
【００１１】
そのような機構の１つが、ポマリン（Pomerene）他の米国特許第４８０７１１０号、PrefetchingSystem for a Cache Having a Second Directory for Sequentially Accessed Blocksに記載されている。この発想は、連続してアクセスされるキャッシュ・ライン間の関係を保管する大きい２レベル・テーブルを設け、これらの関係をキャッシュへの事前取出しに活用できるようにすることである。この関係を確立し、維持するさまざまな方法が記述されている。この手法の重要な短所は、テーブルのサイズが固定され、最終的に満杯になることである。その時点で、既知の関係を追い出して、新しい関係のための余地を作らなければならない。これは、テーブルが、実効ページ・セットを取り込むのに十分に大きい限り、問題ではないが、２００１年２月２４日出願の関連する米国仮出願番号６０／２７１，１２４、MassivelyParallel Supercomputerに記載のスケーラブル・コンピュータで動作するものなどの多数の科学アプリケーションの実効ページ・セットは、主記憶ほどに大きくなる可能性がある。この場合に、キャッシュ・ライン間の後続の関係が、事前取出しに使用できるようになるよりかなり前に、制限された容量に起因して追い出されるので、テーブルは、ほとんど利益をもたらさない。
【特許文献１】
米国仮出願番号６０／２７１，１２４
【特許文献２】
米国特許第４８０７１１０号
【発明の開示】
【発明が解決しようとする課題】
【００１２】
したがって、本発明の主目的は、特に弱く順序付けられたマルチプロセッサ・システムに関連する、短待ち時間メモリ・システム・アクセスを提供することである。
【課題を解決するための手段】
【００１３】
メモリ待ち時間は、一般に、メモリから情報を送達するのにディジタル・コンピュータが必要とする時間、または中央処理装置（ＣＰＵ）がメモリ・データに関する要求を開始する時刻とメモリ・システムがＣＰＵにそのデータを返す時刻との間の間隔として知られる。
【００１４】
マルチプロセッサ内の各プロセッサが、リソースを共用し、各共用リソースは、ロック装置内に関連するロックを有する。ロックは、マルチプロセッサ内の複数のプロセッサの間の同期化のサポートと、リソースの秩序だった共用を提供する。プロセッサは、リソースに関連するロックを所有する時に限ってリソースへのアクセスの許可を有し、プロセッサによるロックを所有（別名獲得）する試みは、従来のアトミックなロードおよびその後のストアではなく、単一のロード動作だけを必要とし、プロセッサが、読取動作だけを実行し、プロセッサではなくハードウェア・ロック装置が、後続の書込動作を実行する。
【００１５】
本発明のもう１つの目的は、不連続に保管されるが同一の順序で繰り返してアクセスされる非常に長いデータ構造など、不連続なデータ構造の事前取出しの単純な機構を提供することである。基本的な発想は、データ構造にポインタを組み込んで、アクセスの順序を示し、ポインタのターゲットを事前取出しすることである。
【００１６】
事前取出しは、一般に、キャッシュ・ラインに基づき、ラインは、連続する物理メモリ位置の位置合せされたチャンクである。システムのメモリ全体を、ラインに分割されるものとみなすことができ、これらのラインの一部が、任意の所与の時にキャッシュに保管される（おそらくは修正される）。本発明では、メモリ・ラインを再定義し、その結果、通常の物理メモリ・データのほかに、すべてのラインに、メモリ内の他のラインをポイントするのに十分に大きいポインタを含める。データおよびポインタのほかに、ポインタをセットし、使用するアルゴリズムを実施するための追加ビットを設けることができる。たとえば、本明細書で説明する好ましい実施形態には、ポインタの状況を示す２つのビットが含まれる。基本的な発想は、他の予測アルゴリズムではなく、ポインタを使用して、事前取出しされるメモリ・ラインを判定することである。これによって、ハードウェアが、不連続だが反復的なメモリ・アクセス・パターンを効率的に事前取出しできるようになる。本発明の好ましい実施形態には、自動的にアクセス・パターンを検出し、メモリ・ライン・ポインタをセットする機構が含まれる。さらに、ある機構によって、ソフトウェアからポインタを静的にセットできるようになる。
【００１７】
短待ち時間メモリおよび同期化に関する本発明の前述の目的および長所は、添付図面と共に下記の複数の実施形態の詳細な説明を参照することによって、当業者がすぐに理解することができる。図面では、類似する要素が、複数の図面を通じて同一の符号によって示される。
【発明を実施するための最良の形態】
【００１８】
チップ上のマルチプロセッサが、ロックを実施するカスタム・ハードウェアを含めることによって、ロックの性能を改善する機会を提供する。このハードウェアは、個々のプロセッサの間など、プロセッサの近くに配置され、極端に短い待ち時間のアクセスがもたらされる。さらに、アトミック（割込みなしで実行される）ＲＭＷ（read-modify-write）動作を必要とするではなく、通常のロードおよびストアを用いて働くロックを実施することができる。
【００１９】
本発明は、マルチプロセッサ・システムオンチップ（ＳＯＣ）キャッシュ構造に関連して開発されつつある。マルチプロセッサ・システムには、それぞれが内部第１レベル・キャッシュを有する２つのＣＰＵコアが含まれ、各プロセッサは、相対的に独立に動作する別々の書込バスおよび読取バスを有する。本発明が、３つ以上のＣＰＵコアと共に働くことを理解されたい。
【００２０】
本発明は、マルチプロセッサＳＯＣなどのマルチプロセッサ内の複数のプロセッサの間の同期化のサポートを提供するハードウェア・ロック装置を提供する。ハードウェア・ロック装置を、個々のプロセッサの間に配置して、待ち時間を最小限まで減らすことができる。ハードウェア・ロック装置を用いると、各プロセッサが、ロックを獲得するために単純に読取動作を実行できるようになる。というのは、関連する書込動作が、暗黙であり、ハードウェア・ロック装置によって実行されるからである。ロック装置は、チップ上で非常に効率的に実施することができ、あるいは、独立のデバイスとして実施することもできる。
【００２１】
図１に、共用されるロック装置が、２つのプロセッサ１２−１および１２−２によって、そのメモリ・バス１４および１５を介してどのように接続され、アクセスされるかを示す。ロック装置１０は、他のアドレス可能装置と同様に、プロセッサ１のメモリ・バス１４に接続される。同様に、ロック装置１０は、他のアドレス可能装置と同様に、プロセッサ２のメモリ・バス１５に接続される。あるアドレス範囲が、プロセッサのそれぞれでロック装置アクセス用に予約される。ロック装置には、普通のメモリ・ロードおよびメモリ・ストアを介してアクセス可能な複数の独立のロックが含まれる。これを、しばしば、「メモリ・マップ入出力」と称する。各ロックは、２つの別個のアドレスすなわち、アクティブ・アドレスおよびパッシブ・アドレスを介してアクセス可能である。このアクティブ・アドレスを用いると、プロセッサが、まずロックを獲得でき、その後にロックを解放できるようになり、パッシブ・アドレスは、ロックの現在の状況のみを供給する。
【００２２】
図２に、２つのロック装置１および２の、プロセッサ２０のアドレス空間への通常のマッピングを示す。各ロックは、１つはアクティブ、１つはパッシブという２つの物理アドレスを介してアクセス可能である。アクティブ・アドレスのすべてが、物理アドレス空間内で一緒にグループ化されて、ロック装置１０がアクティブ・アクセスを簡単にデコードできるようにされる。同様に、すべてのパッシブ・アドレスが、物理アドレス空間内で一緒にグループ化される。図２では、物理アドレスｉおよびｊが、アクティブ・アドレスであり、物理アドレスｋおよびｌが、パッシブである。
【００２３】
アプリケーションは、図２に示されているように、ロックのアクティブ・アドレスとパッシブ・アドレスをその仮想アドレス空間内に一緒に対にすることを好む場合がある。ここでは、ロック１のアクティブ・アドレスが、仮想アドレスｐであり、そのパッシブ・アドレスが、仮想アドレスｑである。同様に、ロック２のアクティブ・アドレスおよびパッシブ・アドレスは、それぞれ仮想アドレスｒおよび仮想アドレスｓである。
【００２４】
ロック装置は、仮想メモリを介してアクセス可能なので、オペレーティング・システムは、仮想メモリ・マッピングを介してロックへのアクセスを制御する。図２の仮想アドレスから物理アドレスへのマッピングが、通常のメモリ管理ユニット内にある普通の機構によってもたらされることに留意されたい。物理アドレスからロック装置へのマッピングは、ロック装置のアドレス・デコーダによって決定される。そのような通常のマッピングの１つが、オペレーティング・システム・ページごとに単一のロック・アクセス・アドレスを設けることである。これによって、保護された形でアプリケーションにロックを割り当てる際のオペレーティング・システムの最大の柔軟性が可能になる。多数の他のマッピングが可能であることと、複数のプロセッサが、ロック装置デコード制約の対象になる異なるマッピングを使用することができることに留意されたい。
【００２５】
特定のロックの獲得を試みるために、プロセッサは、そのロックのアクティブ・アドレスを読み取る。この読取によって、１の暗黙のＲＭＷ（read-modify-write）が実行され、ロックの前の状態が返される。成功の際には０が返され、失敗の際には１が返される。ロックを解放するには、ロックのアクティブ・アドレスに０を書き込む。ロックに対応するパッシブ・アドレスに対する読取では、ロックを修正せずに、ロックの現在の状態が単純に返される。
【００２６】
複数のプロセッサが、ロック装置のロックを参照するのに同一のアドレスを使用する必要はないが、特定のロックを共用できるようにするために、使用可能なロックのどれが特定の目的に使用されるかに関して合意しなければならない。ロック装置は、非常に効率的である。というのは、ロック獲得の試みに、従来のアトミックなロード（読取）とその後のストア（書込）ではなく、単一のロード（読取）動作だけが必要であり、プロセッサが、読取動作だけを実行し、後続の書込動作を実行する必要がなく、この書込動作は、その代わりにハードウェア・ロックによって実行される。これは、プロセッサが別々の書込バスおよび読取バスを有する時に特に有利であり、この別々のバスの動作は、アトミックＲＭＷを提供するために調整されなければならないが、これは、待ち時間の増加をもたらす。
【００２７】
本発明は、不連続に保管されるが同一の順序で繰り返してアクセスされる非常に大きいデータ構造の効率的な事前取出しの機構にも関し、これを提供する。基本的な発想は、アクセス順序を示すポインタをデータ構造に組み込み、ポインタのターゲットを事前取出しすることである。
【００２８】
事前取出しは、一般に、キャッシュ・ラインに基づき、ラインは、連続する物理メモリ位置の位置合せされたチャンクである。システムのメモリ全体を、ラインに分割されるものとみなすことができ、これらのラインの一部が、任意の所与の時にキャッシュに保管される（おそらくは修正される）。
【００２９】
図３に、メモリ・ラインが再定義され、その結果、通常の物理メモリ・データ３１のほかに、すべてのラインに、メモリ内の他のラインをポイントするのに十分に大きいポインタ３２が含まれるようになる、本発明の１つの概念を示す。図３のラインには、Ｍビットのデータが含まれ、このラインは、メモリ全体を構成する２＾Ｎ（２のＮ乗）個のメモリ・ラインの１つである。データおよびポインタのほかに、ポインタをセットし、使用するアルゴリズムを実施するためのビットを設けることができる。たとえば、本明細書に記載の好ましい実施形態には、ポインタの状況を示す２つのビット３３および３４が含まれる。
【００３０】
基本的な発想は、他の予測アルゴリズムではなく、ポインタを使用して、事前取出しされるメモリ・ラインを判定することである。これによって、ハードウェアが、不連続だが反復的なメモリ・アクセス・パターンを効率的に事前取出しできるようになる。本発明の好ましい実施形態には、自動的にアクセス・パターンを検出し、メモリ・ライン・ポインタをセットする機構が含まれる。さらに、ある機構によって、ソフトウェアからポインタを静的にセットできるようになる。
【００３１】
メモリ・ラインおよびそれに関連するポインタは、ラインがメモリ階層の上に移動される際に、一緒のままになる。たとえば、事前取出しを使用して、ＣＰＵの近くの第２レベル・キャッシュのヒット率を改善することができ、したがって、第３レベルなど、その下の他のキャッシュは、単に、メモリ・ライン・データと共にポインタをキャッシングする。第２レベル・キャッシュも、下で説明するように、状況変更を実施するためにポインタを保管する。ポインタをセットする単純な機構は、すべてのポインタが「無効」とみなされる状態から自動的に開始する。無効なポインタは、事前取出しに絶対に使用されない。これは、追加のビットを用いて、または特定のポインタ値をこの状態の専用にすることによって、示すことができる。ラインがアクセスされ、ラインが有効なポインタを有しない時に、そのラインが、「親」状況に昇格される。次に取出しが要求されるラインが、その「子」とみなされる。子がわかったならば、親のポインタを、その子をポイントするように修正し、有効にする。さらに、「保護観察」ビットをセットして、そのポインタが推測であり、有用でない可能性があることを示す。子が別の後続ラインの親でもあるという点で、このアルゴリズムが再帰的であることに留意されたい。
【００３２】
保護観察ポインタがセットされたラインが参照され、おそらくは取り出される時に、そのラインが、もう一度親とみなされるが、子は取り出されない。次のラインが要求されたならば、そのアドレスが、保護観察の子ポインタと比較される。それらが一致する場合に、親のポインタが、「既知」状況に昇格される。一致しない場合には、親のポインタが無効とマークされる。というのは、事前取出しが有用でないと仮定されるからである。
【００３３】
既知ポインタを有するラインが参照され、おそらくは取り出される時に、ポイントされる子が、即座に事前取出しされる。次に参照されるラインが、その子でない場合には、親のポインタ状況が、また保護観察状況に降格される。
【００３４】
この単純な方式では、アクセス・パターンの変動の余地が許容されず、１を超える事前取出し深さ（すなわち、保留中の事前取出しの数、通常は３または４）がサポートされない。この単純な方式を機能強化して、ある期間にわたって親子関係を記憶する、小さい内容アドレス事前取出しテーブルを含めることができる。このテーブルは、３つのフィールドすなわち、親、子、および状況を有する。
【００３５】
ラインが取り出され、無効ポインタを有する時には、そのラインは、単純な方式と同一の形で扱われる。すなわち、次に取り出されるラインが子と見なされ、親のポインタに子がセットされ、ポインタ状況に保護観察がセットされる。既知ポインタを有するラインが、取り出されるか事前取出しされる時には、事前取出し深さを超えない限り、ポイントされる子が即座に事前取出しされる。
【００３６】
保護観察ポインタまたは既知ポインタを有するラインが取り出され、事前取出しテーブルでそのラインが親でないことがわかる時には、そのラインが、子ポインタおよびポインタ状況と共にテーブルに入力される。
【００３７】
ラインが参照され、おそらくは取り出される時に、必ず、そのラインのアドレスが、事前取出しテーブル内のすべての子ポインタと比較される。一致が見つかる場合には、関連する親の状況が、単純な方式と同様に更新される。すなわち、保護観察ポインタが、既知の状況に昇格される。さらに、事前取出しテーブル内の一致する項目が、除去される。複数の子項目が一致する場合には、そのそれぞれが同一の形で扱われる。
【００３８】
ある項目が、容量に起因して事前取出しテーブルから追い出される時に、親のポインタ状況が、単純な方式で次の参照が期待される子と一致しない時と同様に更新される。すなわち、有効ポインタは、保護観察ポインタにされ、保護観察ポインタは、無効化される。ラインがキャッシュから追い出され、そのラインが、事前取出しテーブルで親であることがわかる時には、そのテーブル項目も、無効化され、事前取出しテーブル追出しとして扱われる。
【００３９】
事前取出しハードウェアに、事前取出しポインタを事前設定し、事前設定された事前取出しポインタを尊重するが、その状況を変更しない動作モードが含まれる。すなわち、自動ポインタ設定機構が使用不可にされるが、ポインタに基づく事前取出し機構は使用不可にされない。これは、データ構造の仮想対物理マッピングが固定され、データ構造のトラバース順序が既知である時に有用である。この場合に、物理メモリ内のポインタを、アクセス順序に対応するようにセットすることができ、これによって、データ構造を効率的に事前取出しできるようになる。
【００４０】
短待ち時間メモリ・システム・アクセスおよび不連続データ構造の単純な事前取出しに関する本発明の複数の実施形態および変形形態を、本明細書で詳細に説明したが、本発明の開示および教示によって、当業者に多数の代替設計が提案されることは明白である。
【図面の簡単な説明】
【００４１】
【図１】ロック装置が、どのようにして２つのプロセッサに接続され、２つのプロセッサによってアクセスされるかを示す図である。
【図２】ロックのアドレス・マッピングの例を示し、複数のロックがプロセッサのアドレス空間にどのようにマッピングされるかを示す図である。
【図３】本発明のもう１つの概念を示す図である。この図では、メモリ・ラインが再定義され、その結果、通常の物理メモリ・データのほかに、すべてのラインに、メモリ内の他のラインをポイントするのに十分に大きいポインタが含まれるようになる。
【図１】
2004529415.tif 000003
【図２】
2004529415.tif 000004
【図３】
2004529415.tif 000005
【国際公開パンフレット】
2004529415.tif 000006
2004529415.tif 000007
2004529415.tif 000008
2004529415.tif 000009
2004529415.tif 000010
2004529415.tif 000011
2004529415.tif 000012
2004529415.tif 000013
2004529415.tif 000014
2004529415.tif 000015
2004529415.tif 000016
2004529415.tif 000017
2004529415.tif 000018
2004529415.tif 000019
2004529415.tif 000020
2004529415.tif 000021
2004529415.tif 000022
2004529415.tif 000023
【国際公開パンフレット（コレクトバージョン）】
2004529415.tif 000024
【国際調査報告】
2004529415.tif 000025
2004529415.tif 000026
2004529415.tif 000027