JPH0962572A - ストリーム・フィルタ装置及び方法 - Google Patents

Abstract

(57)【要約】 【課題】ストリームの活動レベルに基づいてストリーム
の割振り解除を遅らせ、それによって、ストリーム・ス
ラッシュ状況が生じるのを防ぐためにストリーム・フィ
ルタを使用するシステム及び方法を提供する。 【解決手段】ＬＲＵストリームは、多数の潜在的な新し
いストリームが検出された後にだけ割振り解除される。
データ処理システムにおいて、バスによりプロセッサに
接続されたメイン・メモリから、そのプロセッサに接続
されたＬ１キャッシュにキャッシュ・ラインをプリフェ
ッチするための方法であって、そのプリフェッチはスト
リーム・バッファ及びストリーム・フィルタの利用によ
って増大し、ストリーム・バッファはアドレス・バッフ
ァ及びデータ・バッファを含み、ストリーム・バッファ
は１つ又は複数のアクティブ・ストリームを保持し、ス
トリーム・フィルタは１つ又は複数のアクティブ・スト
リームに対応した１つ又は複数のエントリを含む。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、概して云えば、デ
ータ処理システムに関するものであり、詳しく云えば、
データ・キャッシュに関してデータの進行的プリフェッ
チを行うためのシステム及び方法に関するものである。

【０００２】

【従来の技術】現在のプログラム及びデータを高速度で
プロセッサ（ＣＰＵ）にとって使用可能にすることによ
ってデータ処理システムにおける処理の速度を高めさせ
るために、特別の非常に高速度のメモリが使用されるこ
とが時々ある。そのような高速度のメモリはキャッシュ
として知られており、メイン・メモリのアクセス時間と
プロセッサ・ロジックとの間の速度差を補償するため
に、大型のコンピュータシステムにおいて使用されるこ
とが時々ある。プロセッサ・ロジックは、通常、メイン
・メモリのアクセス・タイムよりも速く、その結果、処
理速度はメイン・メモリの速度によって最も制限され
る。オペレーティング・システムの不一致を補償するた
めに使用されるテクニックは、ＣＰＵとメイン・メモリ
との間に極めて速い小型のメモリを使用することであ
る。そのメモリのアクセス・タイムはプロセッサのロジ
ック伝播遅延に近い。それは、ＣＰＵにおいて現在実行
されているプログラムのセグメント及び現在の計算にお
いて頻繁に使用される一時的なデータを記憶するために
使用される。プログラム（命令）及びデータを高速度で
使用可能にすることによって、プロセッサのパフォーマ
ンス・レートを向上させることが可能である。

【０００３】多数の一般的なプログラムの分析の結果、
任意の所与のタイム・インターバルにおけるメモリへの
参照は、メモリにおける僅かなローカライズされた領域
に制限される傾向があるがわかった。この現象は、「参
照の局所性」という特性として知られている。この特性
の理由は、一般的なコンピュータ・プログラムは、頻繁
に遭遇するプログラム・ループ及びサブルーチン・コー
ルを伴って直線的に流れるということを考慮すればこの
特性の理由は理解されるであろう。プログラム・ループ
が実行される時、ＣＰＵは、そのループを構成するメモ
リ内の命令のセットを繰り返し参照する。所与のサブル
ーチンが呼び出される時、それの命令セットがメモリか
らフェッチされる。従って、ループ及びサブルーチンは
命令のフェッチのためにメモリへの参照をローカライズ
する傾向がある。更に低い程度まで、データに対するメ
モリ参照もローカライズされる傾向がある。テーブル・
ルックアップ手順は、そのテーブルが記憶されているメ
モリ内の部分を繰り返し参照する。反復的手順は共通の
メモリ・ロケーションを参照し、多くの数字がメモリの
ローカル部分内に制限される。これらのすべてを注目し
た結果が参照の局所性特性であり、短期間にわたって一
般的なプログラムによって発生される命令のアドレスが
メモリの僅かなローカライズされた領域を繰り返し参照
し、一方、メモリの残り部分は滅多にアクセスされな
い。

【０００４】プログラム及びデータのアクティブナ部分
が高速の小型メモリ内に置かれている場合、平均的なメ
モリ・アクセス・タイムは減少し、従って、プログラム
の合計実行時間を減少させる。そのような高速の小型メ
モリは、前述のように、キャッシュ・メモリと呼ばれ
る。キャッシュ・メモリのアクセス・タイムはメイン・
メモリのアクセス・タイムよりも小さく５分の１乃至１
０分の１となることが多い。キャッシュ・メモリはメモ
リ・ハイアラーキにおける最高速のコンポーネントであ
り、ＣＰＵコンポーネントの速度に近い。

【０００５】キャッシュ機構の基本的な理念は、最も頻
繁にアクセスされる命令及びデータを高速度キャッシュ
・メモリに保持することによって、平均的なメモリ・ア
クセス・タイムがキャッシュ・メモリのアクセス・タイ
ムに近づくようにすることである。キャッシュ・メモリ
はメイン・メモリの数分の１のサイズしかないけれど
も、メモリ・リクエストの大部分は、プログラムの参照
の局所性のために高速度キャッシュ・メモリ内で検出さ
れるであろう。

【０００６】キャッシュ・メモリの基本的オペレーショ
ンは次のようである。ＣＰＵがメモリにおけるワードを
アクセスする必要がある時、キャッシュ・メモリが調べ
られる。そのワードがキャッシュ・メモリにおいて見つ
かる場合、それはその高速キャッシュ・メモリから読み
取られる。ＣＰＵによってアクセスされたワードがキャ
ッシュ・メモリにおいて見つからなかった場合、そのワ
ードを読み取るためにメイン・メモリがアクセスされ
る。そこで、そのアクセスされたワードを含むワード・
ブロックがメイン・メモリからキャッシュ・メモリに転
送される。このように、メイン・メモリへのその後の参
照によって必要なワードが高速キャッシュ・メモリにお
いて見つかるよう、幾つかのデータがキャッシュ・メモ
リに転送される。

【０００７】コンピュータ・システムの平均的メモリ・
アクセス・タイムは、キャッシュ・メモリの使用によっ
てかなり改善可能である。キャッシュ・メモリのパフォ
ーマンスは、「ヒット率」と呼ばれる数値によって測定
されることが多い。ＣＰＵがメモリを参照し、キャッシ
ュにおいてそのワードを見つける時、それは「ヒット」
を生じたと云われる。そのワードがキャッシュ・メモリ
において見つからなかった場合、それはメイン・メモリ
内にあり、「ミス」としてカウントされる。ＣＰＵが、
殆ど時間、メイン・メモリの代わりにキャッシュ・メモ
リをアクセスするほどにヒット率が十分に高い場合、平
均的アクセス時間は高速キャッシュ・メモリのアクセス
時間に近くなる。例えば、１００ｎｓのキャッシュ・ア
クセス・タイム、１０００ｎｓのメイン・メモリアクセ
ス・タイム、及び０.９のヒット率を持ったコンピュー
タは２００ｎｓの平均アクセス・タイムを生じる。これ
は、キャッシュ・メモリのない同様のコンピュータ（そ
のアクセス・タイムは１０００ｎｓ）に比べてかなりの
改善である。

【０００８】最近のマイクロプロセッサでは、プロセッ
サ・サイクル・タイムはテクノロジの発展に伴って改善
し続けている。又、思惑的な実行、深いパイプライン、
多くの実行エレメント等の設計テクニックはマイクロプ
ロセッサのパフォーマンスを改善し続けている。その改
善されたパフォーマンスは、マイクロプロセッサに与え
るために多くのデータ及び命令を要求するので、メモリ
・インターフェースに重い負荷を課している。メモリ待
ち時間の減少を援助するために大きなオン・チップ・キ
ャッシュ（Ｌ１キャッシュ）が使用される。それらは、
大型のオフ・チップ・キャッシュ（Ｌ２キャッシュ）に
よって拡張されることが多い。

【０００９】待ち時間を減少させるのに先立ってメモリ
・データをＬ１キャッシュに供給しようとするプリフェ
ッチ・テクニックが実施されることが多い。理想的に
は、プロセッサがメモリ・データを必要とする時、その
メモリ・データのコピーがいつもＬ１キャッシュ内にあ
るよう、プログラムはデータ及び命令を十分に前もって
プリフェッチするであろう。

【００１０】問題は、すべての場合において、必要とさ
れるデータ・アドレスを明示的に決定するに十分な先回
り情報を、マイクロプロセッサ・アーキテクチャが与え
てないことである。例えば、メモリにおけるデータ・オ
ペランドに対するアドレス自身はメモリ内にあり、メモ
リ命令によって使用されるべき第１命令によってフェッ
チされなければならない。そのようなシーケンスの場
合、プリフェッチを行うために、プロセッサは前もって
そのアドレスを持っていない。

【００１１】命令又はデータのプリフェッチはその分野
ではよく知られている。しかし、既存のプリフェッチ・
テクニックは命令又はデータを早くプリフェッチし過ぎ
ることが多い。プリフェッチしそしてその後そのプリフ
ェッチされた命令又はデータを使用しないという問題
は、第１に、プロセッサが必要とするデータをプリフェ
ッチ・データが変位してしまうことがあること、及び、
第２に、プリフェッチ・メモリ・アクセスはその後のプ
ロセッサ・キャッシュ再ロードがそのプリフェッチ・ア
クセスを待つようにさせ、従って、必要なデータの待ち
時間を増加させることがあることである。これらの影響
は両方ともＣＰＵの効率を低下させる。

【００１２】インクレメンタル・メモリ・ロケーション
への持続したアクセスの存在が検出される時、ストリー
ム・バッファはメモリからのデータのプリフェッチを援
助するために利用される。

【００１３】問題は、Ｎ個のストリームが如何なる時で
もアクティブである（割振り可能である）という有限の
数のストリーム・バッファによって、Ｎ個の割振られた
ストリームが尽きる前に新しい潜在的なストリームのス
トリーム割振りがある場合、「スラッシング」状態が存
在し得るし、その新しいストリームは、プリフェッチさ
れたデータが使用される前にアクティブ・ストリームの
１つを変位することができる。従って、データ処理シス
テムにおけるプリフェッチ・ストリームにおいて利用さ
れるストリーム・バッファ内のストリームのスラッシン
グを減少させるためのシステム及び方法に対する要求が
その分野にはある。

【００１４】

【発明が解決しようとする課題】本発明の目的は、スト
リームの活動レベルに基づいてストリームの割振り解除
を遅らせ、それによってストリーム・スラッシング状況
が生じるのを防ぐために、ストリーム・フィルタを使用
するシステム及び方法を提供することにある。最近最も
使用されなかった（ＬＲＵ）ストリームは、潜在的な新
しいストリームが検出された後にだけ割振り解除され
る。

【００１５】

【課題を解決するための手段】開示された実施例は、い
つでも４つまでのストリームを割り振ることができるス
トリーム・バッファを実施するためのものである。実施
例に関連したフィルタ・バッファはＬＲＵベースで割り
振られる１０個のエントリを有する。

【００１６】正規のオペレーションでは、そのフィルタ
によってストリーム・アクセスが検出された時、そのス
トリームに対するフィルタ・エントリがそのフィルタの
最近最も使用された（ＭＲＵ）位置にセットされる。新
しいラインが関連のストリームにおいてアクセスされる
時、いつも、エントリはＭＲＵ位置に戻る。例えば、ア
クティブな４つのストリーム（１、２、３、４）が存在
した場合、及び他のキャッシュ・ミス存在しなかった場
合、その４つのストリームは、いつも、フィルタ・バッ
ファの４つのＭＲＵ位置の１つを占めるであろう。その
後のストリーム・アクセスの間にキャッシュ・ミスがあ
った場合、フィルタはそれらに対するエントリも含むで
あろうし、従って、４つのストリームはその４つのＭＲ
Ｕ位置以外の位置を時々占めるであろう。１０個のエン
トリのフィルタの場合、任意の２つの連続したストリー
ム・アクセスの間のキャッシュ・ミスが９個よりも少な
い限り、ストリームは割り振られたままである。明らか
に、ストリーム・アクセス相互間に１０個のキャッシュ
・ミスがあった場合、ＬＲＵポリシは１０個のフィルタ
・エントリすべてをそのミスしたラインに割り振ること
によってストリーム割振りをエージ・アウト（無効に）
するであろう。４つのストリームが割り振られた場合、
（フィルタは４つのストリーム及び６つの他のフィルタ
・エントリに対して十分なエントリを有するので）７つ
のキャッシュ・ミスが介在する限り、ストリームはフィ
ルタをエージ・オフ（無効に）しないであろう。

【００１７】

【発明の実施の形態】以下の説明では、本発明の十分な
理解を与えるために、特定のワード長又はバイト長等の
ような数多くの特定の細部を説明する。しかし、本発明
がそのような特定の細部の説明なしでも実施可能である
ことは当業者には明らかであろう。他の例では、不必要
な詳述で本発明を不明瞭にしないようにするために、周
知の回路はブロック図形式で示される。大部分に対し
て、タイミング事項等に関する詳細については、それが
本発明の十分な理解を得るために必要ない限り及び当業
者のスキルの範囲にある限り省略した。

【００１８】図面を参照すると、示されたエレメントは
必ずしも縮尺して示されたものではない。同様の又は同
じエレメントはそれらの図面を通して同じ参照番号によ
って表される。

【００１９】図１を参照すると、本発明を有利に具体化
するデータ処理システムが示される。マルチプロセッサ
・システム１００は、システム・バス１２４に動作的に
接続された多数のプロセッサ装置１０６、１０８、１１
０を含む。システム１００では、任意の数のプロセッサ
装置が利用可能であることに注意してほしい。又、シス
テム・バス１２４には、システム・メモリ１０２へのア
クセスを制御するメモリ・コントローラ１０４が接続さ
れる。メモリ・コントローラ１０４は、Ｉ／Ｏ装置１２
８に結合されたＩ／Ｏコントローラ１２６にも接続され
る。プロセッサ装置１０６、１０８、１１０、Ｉ／Ｏコ
ントローラ１２６、及びＩ／Ｏ装置１２８は、すべて、
ここではバス装置と呼ぶこともできる。図示のように、
各プロセッサ装置１０６、１０８、１１０は、それぞ
れ、プロセッサとＬ１キャッシュ１１２、１１４、１１
６とを含む。Ｌ１キャッシュはそれぞれのプロセッサと
同じチップ上に設置可能である。プロセッサ装置１０
６、１０８、１１０には、それぞれ、Ｌ２キャッシュ、
１１８、１２０、１２２が接続される。これらのＬ２キ
ャッシュは、それが接続されたプロセッサ装置を介して
システム・バス１２４に接続される。

【００２０】Ｌ１及びＬ２キャッシュの各対は、通常、
直列的に関連している。Ｌ１キャッシュはストア・イン
或いはライトスルーとして実現可能であり、一方、大型
で遅いＬ２キャッシュはライトバック・キャッシュとし
て実現される。Ｌ１及びＬ２キャッシュの両方とも物理
的にはプロセッサ装置の一部分として実現され、プロセ
ッサ装置の内部バスを介して接続される。Ｌ２コントロ
ーラはチップ外にあってもよく、本発明が依然として適
用可能である。

【００２１】次に、図２を参照すると、本発明に従って
動作するように構成可能なデータ処理システム２００が
示される。そのシステム２００はシステム１００とは別
のアーキテクチャのものである。システム１００及び２
００では、プロセッサ及びキャッシュの基本的なオペレ
ーションは同じである。メモリ・コントローラ１０４及
びノード・コントローラ２０５の制御及び機能は、本発
明に関しては同じである。

【００２２】システム２００において、プロセッサ２０
１は内部Ｌ１キャッシュ２０２を有し、それは外部Ｌ２
キャッシュ２０３に接続される。プロセッサ２０１はバ
ス２０４によってノード・コントローラ２０５に接続さ
れる。ノード・コントローラ２０５は、プロセッサ２０
１とシステム２００の残りの部分との接続に関してその
分野では知られた基本的機能を遂行する。ノード・コン
トローラ２０５はバス２０６によってスイッチ２０７に
接続される。スイッチ２０７はクロス・ポイント・スイ
ッチでよく、他のプロセッサ及びＩ／Ｏ装置をバス２０
８によってシステム・メモリ２０９に結合することがで
きる。この説明の残り部分はシステム２００に関するも
のである。しかし、本発明に関する説明も関連してお
り、それはシステム１００においても実施可能である。

【００２３】本発明の目的は、プロセッサ２０１がＬ１
キャッシュ２０２におけるキャッシュ・ラインにおいて
かなりの時間量をヒットし、従ってシステム・メモリ２
０９からのアドレス及びデータ情報の検索（それはプロ
セッサ２０１のパフォーマンスを低下させる）を最小に
するように、キャッシュ・ラインをＬ１キャッシュ２０
２にプリフェッチするための効率的且つ正確なテクニッ
クを提供することである。

【００２４】プロセッサ・オペレーションのパフォーマ
ンスを改善するために設定された１つの従来技術は、キ
ャッシュ・ラインをプリフェッチするためにストリーム
・フィルタ及びストリーム・バッファを利用することで
あった。図３を参照すると、その分野で知られているス
トリーム・フィルタ及びストリーム・バッファが示され
る。ストリーム・フィルタは、使用されないデータのプ
リフェッチの発生を減少させるものである。これらのフ
ィルタは、アドレス及び方向情報を含むヒストリ・バッ
ファである。そのフィルタは、Ｌ１キャッシュにおいて
ミスしたラインから見て直列的には次に高いラインであ
るキャッシュ・ラインのアドレスを含む。次に高いその
キャッシュ・ラインへのアクセスが行われる場合、スト
リーム状態が検出され、ストリーム・バッファが割り当
てられる。フィルタは、ライン・アドレス「Ｘ」へのア
クセスがあった場合、ライン・アドレス「Ｘ＋１」を書
き込まれるであろう。アドレス「Ｘ＋１」が依然として
ストリーム・フィルタに存在する時に次のアクセスがそ
のアドレス「Ｘ＋１」に対して行われる場合、「Ｘ＋
１」がストリームとして割り当てられる。

【００２５】ストリーム・バッファは、可能性あるキャ
ッシュ・データを保持するプリフェッチ・バッファであ
る。その考えは、そのプロセッサ内で実行中のプログラ
ムがデータ／命令の順次ストリームを実行している場
合、更なるラインをストリーム・バッファにプリフェッ
チすることは有用なことになる。従って、その後のキャ
ッシュ・ミスは、ストリーム・バッファにおいてデータ
を見つけることができるかも知れない。

【００２６】ストリーム・フィルタ及びストリーム・バ
ッファは、ストリーム・バッファをミスするＬ１キャッ
シュ・ミスが存在する場合、そのミス・アドレスがスト
リーム・フィルタに記憶されたアドレスと比較されるよ
うに共同する。ストリーム・フィルタにおいてヒットが
ある（データの直列ラインへの順次的アクセスが存在し
たことを意味する）場合、次のラインも将来必要となる
高い可能性がある。ストリーム・バッファ及びストリー
ム・フィルタに関する更なる説明に関しては、１９９４
年発行のＩＥＥＥの１０６３乃至６８７９ページの S.P
alacharla 及びR.Kessler による記事「二次キャッシュ
置換としてのストリーム・バッファの評価（Evaluating
Stream Buffers as a Secondary Cache Replacemen
t）」を参照して欲しい。

【００２７】次に、図４を参照すると、本発明に従って
構成されたシステム２００の更に詳細な図及びＣＰＵ２
０１通したデータ・フローが示される。命令及びデータ
に対する別のＬ１キャッシュの使用を含むそのフローの
変形がその分野では知られている。Ｌ１キャッシュ２０
２は、その分野では知られた任意の置換ポリシを使用し
てメモリ２０９からの使用されたデータのコピーを頻繁
に保持する。大型のＬ２キャッシュ２０３はＬ１キャッ
シュ２０２よりも多くのデータを保持し、通常は、メモ
リ・コヒーレンシ・プロトコルを制御する。本発明で
は、Ｌ１キャッシュ２０２におけるデータはＬ２キャッ
シュ２０３におけるデータのサブセットでよい。Ｌ１キ
ャッシュ２０２及びＬ２キャッシュ２０３は「ストア・
イン」キャッシュである。他の機能的エレメント（Ｉ／
Ｏを含む）はその分野で知られたスヌープ・プロトコル
を使用してデータを争う。スヌーピングの一例は、米国
特許出願第０８/４４２,７４０に開示されている。

【００２８】ＣＰＵ２０１に対して示された境界はチッ
プ境界及び機能的境界を表し、本発明の技術的範囲に関
する制限を意味するものではない。ＰＣＣ４０４はプロ
セッサ・キャッシュ・コントローラであり、メモリ・サ
ブシステムに対するフェッチ及びストアを制御する。Ｐ
ＣＣ４０４は、Ｌ１キャッシュ２０２に対するディレク
トリの実施及び実アドレスへの有効アドレスの変換及び
その逆の変換のようなその分野では知られた他の機能を
有する。プリフェッチ・バッファ（ＰＢＦＲ）４０２
は、ＣＰＵ２０１及びＬ１キャッシュ２０２にステージ
されるべきメモリ・データの或数のラインを保持する。
ＰＢＦＲ４０２はストリーム・バッファである。

【００２９】ＰＣＣ４０４がデータをフェッチする時、
それがＬ１キャッシュ２０２にある（Ｌ１ヒットであ
る）場合、それはＰＣＣ４０４に送られる。それがＬ１
キャッシュ２０２にない（Ｌ１ミスである）がＬ２キャ
ッシュ２０３にある（Ｌ２ヒットである）場合、Ｌ１キ
ャッシュ２０２のラインがＬ２キャッシュ２０３からの
このデータでもって置換される。この場合、データはＬ
１キャッシュ２０２及びＰＣＣ４０４に同時に送られ
る。同様に、Ｌ２キャッシュ２０３においてミスがある
場合、データはメモリ２０９からＢＩＵ４０１にフェッ
チされ、Ｌ１キャッシュ２０２、Ｌ２キャッシュ２０
３、及びＰＣＣ４０４に同時にロードされる。このオペ
レーションに関する変形はその分野では知られている。
データ・ストア・オペレーションは、データがＬ１ライ
ンに記憶されてオペレーションを完了することを除け
ば、フェッチ・オペレーションと同じである。

【００３０】以下の説明では、ストリーム・バッファの
種々な部分がシステム２００の種々な部分に設けられ
る。図５に関連して更に説明するシステム・バッファは
ストリーム・アドレス・バッファ及びストリーム・デー
タ・バッファを含んでいる。この実施例では、ストリー
ム・バッファは４つのキャッシュ・ラインをストアする
機能を有するが、任意の数のキャッシュ・ラインがその
ストリーム・バッファにおいて実施可能である。そのス
トリーム・バッファの１つのキャッシュ・ラインがＬ１
キャッシュ２０２において実施される。特に、Ｌ１キャ
ッシュ２０２におけるキャッシュ・ラインの１つが、ス
トリーム・バッファのキャッシュ・ラインの１つの機能
に対して利用される。ストリーム・バッファの第２キャ
ッシュ・ラインはＰＢＦＲ４０２に設けられる。ストリ
ーム・バッファの他の２つのキャッシュ・ラインは、ノ
ード・コントローラ２０５におけるＰＢＦＲ２（４０
５）及びＰＢＦＲ３（４０６）に設けられる。ノード・
コントローラ２０５は、バス２０４に沿ったＣＰＵ２０
１から下流のチップ上に設けることが可能である。メモ
リ・コントローラ１０４は、システム１００のアーキテ
クチャが利用される場合、これらのストリーム・バッフ
ァ・ラインを含んでもよい。

【００３１】上記のＩＥＥＥの記事において検討されて
いるように、ストリーム・フィルタ及びストリーム・バ
ッファの基本的なオペレーションは、リクエストされた
キャッシュ・ラインにおいてＬ１キャッシュ・ミスがあ
る時、そのキャッシュ・ラインのアドレスがインクレメ
ントされ（一般には、１アドレスずつ）、このインクレ
メントされたアドレスがストリーム・フィルタ４０３に
挿入されることである。Ｌ１キャッシュ２０２における
キャッシュ・ラインのその後のミスの発生時に、このＬ
１キャッシュ・ミスのアドレスがフィルタ４０３に含ま
れたアドレスに比較される。アドレスの一致が得られた
場合、キャッシュ・ラインのストリームがそのストリー
ム・バッファ内に割り当てられる。

【００３２】上記のように、キャッシュ・ミスがある
時、フィルタ・バッファは次の逐次キャッシュ・ライン
のアドレスを書き込まれる。そのフィルタは、そのよう
な事象の「ヒストリ」より成るそのようなアドレスを保
持し得る多数のロケーションを含む。それらはＬＲＵベ
ースで置換可能である。キャッシュ・ミスがある時はい
つも、フィルタにおけるアドレスがキャッシュ・ライン
・ミスのアドレスと比較される。ヒットがある場合、フ
ィルタ・ヒットが存在すると云われ、ストリームが割り
当てられる。ストリーム・モードでは、エクストラ・キ
ャッシュ・ラインが、ストリームの一部分としてＬ１キ
ャッシュがそれを必要とすることを期待して、ストリー
ム・バッファにプリフェッチされる。

【００３３】図５は、本発明に従ってストリーム・バッ
ファのオペレーションの高レベルの機能的な図を表す。
ＣＰＵ２０１は、使用されるアーキテクチャに従って有
効アドレス（ＥＡ）を発生する。ＥＡは、潜在的にはオ
フセットを有するプログラム・アドレスである。ＰＣＣ
４０４において実施可能な変換回路５０３は変換アドレ
ス、即ち、ＥＡに対応した実アドレス（ＲＡ）を発生す
る。その実アドレスはフィルタ待ち行列５０２によって
使用されるが、フィルタ待ち行列５０２がその有効アド
レスを代替えとして使用することは本発明の技術的範囲
内であろう。そのＲＡはフィルタ待ち行列５０２におけ
るＲＡと一斉に比較される。そのエントリがそれの有効
ビット（Ｖ）によって表されるように有効である場合、
比較一致はフィルタ・ヒットと呼ばれる。又、フィルタ
待ち行列５０２は、予測ストリームがインクレメント或
いはデクレメント（＋／−１、又はアップ／ダウン）さ
れるべきことを表す各エントリに対する予測方向インデ
ィケータも含む。各フィルタ待ち行列エントリは、その
アドレスに対応するストリームがあるかどうか及び、そ
れが肯定される場合、そのストリームのストリーム番号
を表すフィールドを含む。

【００３４】よく知られているように、メモリ２０９は
サブセクションに論理的に分割されることが多い。特
に、メモリ２０９は、オペレーティング・システムによ
ってプログラムに割り当てられたメモリのインクレメン
トであるページに分割され、ＤＡＳＤ（ダイレクト・ア
クセス記憶装置）とメモリ２０９の間で「ページング」
データを制御するために使用可能である。ページは順次
的ＥＡに関して非順次的に割り当て可能である。従っ
て、ＥＡがストリーム・データのプリフェッチのために
使用される場合、ページ境界を横切った時に変換器（Ｘ
ＬＡＴＥ）５０３においてアドレス変換が行われなけれ
ばならない。それは、そのストリーム・バッファが、前
述のように順次的でない実アドレスを含むためである。
各ページは、更に、ラインに分割される。キャッシュの
実施によってライン・サイズが決定され、それはキャッ
シュ・ラインにおけるメモリ・データの量に対応する。
キャッシュ・ミスの結果、１ラインのデータがキャッシ
ュに転送される。

【００３５】フィルタ・ヒットがある時、ストリームが
ストリーム・アドレス待ち行列５０１に割当可能であ
り、ストリーム・データ・バッファ５０６への対応する
割当が行われる。ストリーム・アドレス・エントリは、
特定の割当てられたストリームに対する次のデータ・ラ
インの予測有効アドレスを含む。もう一度云えば、これ
は実施上の選択事項であり、代替えとして、実アドレス
を使用してもよかった。ストリーム・アドレス・エント
リは、そのストリームが割当てられることを表す有効ビ
ット（Ｖ）も含む。ストリームの状態を追跡するために
使用される状態フィールドもある。又、予測方向のコピ
ーもストリーム・バッファに保持される。比較器５０５
はプロセッサＥＡとストリーム・アドレス待ち行列に含
まれたページ及びライン・アドレスとを比較する。一致
が生じた場合、それはストリーム・ヒットと呼ばれる。

【００３６】図５に示された機能性は別の方法でも実施
可能であり、それも依然として本発明の技術的範囲内で
ある。

【００３７】メモリ２０９におけるメモリ・スペースは
１２８個のバイト・ラインに分割可能である。各ライン
は半分に分割可能であるので、１つのラインの偶数番の
半分はアドレス０から６３までであり、奇数の半分はア
ドレス６４から１２７までである。前述のように、ＣＰ
Ｕ２０１は、メモリにおけるキャッシュ可能なラインに
対する実アドレスに変換される論理的アドレス（ＥＡ）
を発生する。メモリは２＊Ｎバイトのページに分割され
る。それらのページはサイズ的にキャッシュ・エントリ
に対応するラインに分割される。キャッシュ・ミスがあ
る度に、関連する実アドレスが分析される。その実アド
レスがラインの偶数の半分にある場合、潜在的ストリー
ムはインクレメント１である。待ち行列５０２における
ＬＲＵフィルタ待ち行列は「アップ」の方向をマークさ
れ、ライン・ミスＲＡは「１」だけインクレメントされ
てそのエントリに保管される。ＲＡがそのラインの奇数
側にある場合、待ち行列５０２におけるＲＡエントリは
１だけデクレメントされ、「ダウン」がそのエントリに
マークされる。

【００３８】ミスの場合にフィルタ・エントリにＲＡを
保管すること及びその後のミスをそのエントリと比較し
てアップ又はダウンの方向を決定することは、別の実施
例として本発明の範囲内である。

【００３９】ストリームが割り当てられる時、「次の」
有効ライン・アドレスがストリーム・アドレス・バッフ
ァ５０１に保管される。バッファ５０１は各アクティブ
・ストリームに対するエントリを含む。有効ビット
「Ｖ」は、そのエントリが使用中であることを表し、方
向インディケータは、そのストリームがアップであるか
又はダウンであるか（＋／−）を表す。状態フィールド
は、そのストリームの状態を表すために使用される。ス
トリーム・アドレス・バッファ５０１と関連してストリ
ーム・データ・バッファ５０６があり、それは、プリフ
ェッチされたデータのラインを保持する。フィルタ待ち
行列５０２及びストリーム・バッファ５０１の両方の予
測アドレスとも、ページ境界が遭遇する時に終了する。
これは、そのような事象が新しい変換を必要とするため
である。

【００４０】Ｌ１キャッシュ２０２及びＬ２キャッシュ
２０３のキャッシュ・ミスがある場合、メモリ２０９を
アクセスする前にストリーム・バッファが調べられる。
フィルタ待ち行列５０２及びストリーム・アドレス・バ
ッファ５０１の回路を結合することは本発明の明らかな
実施例である。

【００４１】前述のストリーム・フィルタ及びストリー
ム・バッファに関する及び前述のＩＥＥＥの記事におけ
る従来方法はＬ２キャッシュの代替えとしてストリーム
・バッファの効果を分析している。この場合、プリフェ
ッチはいつもインクレメント的なものとして予測され
る。更に、１つのライン或いはワードではなく１つの
「ストライド」とバッファに保管されたストライド長と
によってアドレスがインクレメントされるというストラ
イド・フィルタを説明し、図示することにする。ストラ
イド・フィルタの概念は別の実施例として実現され、本
発明の技術的範囲内であろう。

【００４２】図６乃至図９を参照すると、本発明の進行
的プリフェッチ・モードの流れ図が示される。前述のよ
うに、本発明は３つの進行的プリフェッチ・モード、即
ち、正規モード、データ・プリフェッチ・モード、及び
ブラスト・モードを可能にする。正規モードでは、デー
タはプリフェッチされない。データ・プリフェッチ・モ
ードでは、２つのライン、即ち、Ｌ１キャッシュに対す
る１つのライン及びストリーム・バッファに対する１つ
のラインがプリフェッチされる。ブラスト・モードで
は、２つよりも多くのラインが一時にプリフェッチされ
る。本発明の好適な実施例では、ブラスト・モードにお
いて、４つのライン、即ち、データ・プリフェッチ・モ
ードにおけるような２つのライン及びストリーム・バッ
ファに対する２つの更なるラインがプリフェッチされ
る。何れのモードにおいても、プリフェッチされたバッ
ファは、プロセッサ・チップ、キャッシュ・チップ、外
部チップ、又はメモリ・カード上にパッケージ可能であ
り、依然として、本発明の技術的範囲内にある。図６乃
至図９は、どの方向にストリームが流れるかを予測する
ための方向がインクレメントする例を示す。デクレメン
トする例はこの例の明らかな修正となるであろう。図６
乃至図９はデータ・プリフェッチ及びブラスト・モード
に入る方法を示す。

【００４３】ステップ６０１において、ＣＰＵ２０１は
キャッシュ・ラインＡで開始するデータをアクセスし始
める。ステップ６０２において、キャッシュ・ラインＡ
がＬ１キャッシュ２０２内にあるかどうかの決定が行わ
れる。それが肯定される場合、プロセスはステップ６０
３に進む。そこでは、キャッシュ・ラインＡがＣＰＵ２
０１に戻され、プロセスはステップ６０４において終了
する。

【００４４】しかし、キャッシュ・ラインＡにおいてミ
スがある場合、プロセスはステップ６０５に進む。そこ
では、キャッシュ・ラインＡのアドレスがストリーム・
フィルタ４０３に含まれたすべてのアドレスに比較され
る。

【００４５】キャッシュ・ラインＡがフィルタ４０３内
に存在しない場合、プロセスはステップ６０６に進み、
そこでは、キャッシュ・ラインＡのアドレスが１だけイ
ンクレメントされ、フィルタ４０３内に挿入される。し
かる後、ステップ６０７において、キャッシュ・ライン
ＡはＬ２キャッシュ２０３又はメモリ２０９からＬ１キ
ャッシュ２０２にフェッチされる。このステップはその
分野ではよく知られている。

【００４６】図６乃至図９におけるステップ６０７から
ステップ６０８への点線の矢印は、ステップ６０８がス
テップ６０７に続いて直ちに生じてもよく、或いは生じ
なくてもよいことを表す。一般には、ストリーム・フィ
ルタ内に存在するアドレス・エントリの数と同じ数のミ
スがキャッシュ・ラインＡ＋１に対するリクエストの前
に生じることがある。

【００４７】或時間遅れで、ＣＰＵ２０１はキャッシュ
・ラインＡ＋１をリクエストするかもしれない。再び、
ＰＣＣ４０４はキャッシュ・ラインＡ＋１がＬ１キャッ
シュ２０２内に存在するかどうかを決定する（ステップ
６０９）。それが肯定される場合、キャッシュ・ライン
Ａ＋１がステップ６１０においてＣＰＵ２０１に戻さ
れ、プロセスはステップ６１１において終了する。キャ
ッシュ・ラインＡ＋１はＬ１キャッシュ２０２内にある
ので、ストリーム・フィルタ４０３との比較一致はな
く、Ａ＋１エントリは、それがフィルタ置換アルゴリズ
ムによって再試行されるまでフィルタ４０３に留まる。
そのフィルタ置換アルゴリズムは、以下で教示するとこ
ろに従って遂行可能である。しかし、Ｌ１キャッシュ２
０２内のキャッシュ・ラインＡ＋１においてミスがある
場合、フィルタ・ヒットが存在し（ステップ６３７）、
プロセスをステップ６１２へ進めさせる。そこでは、リ
クエストされたキャッシュ・ラインＡ＋１のアドレスが
フィルタ４０３にあるアドレスＡ＋１と一致した結果フ
ィルタ４０３においてヒットが生じるので、キャッシュ
Ａ＋２でもって始まるキャッシュ・ラインのストリーム
が割り当てられる。次に、ステップ６１３において、キ
ャッシュ・ラインＡ＋１がＬ２キャッシュ２０３又はメ
モリ２０９からＬ１キャッシュ２０２にフェッチされ
る。又、Ｌ１キャッシュ２０２は、キャッシュ・ライン
Ａ＋２が存在するかどうかを決定するためにチェックさ
れる。それが存在しない場合、キャッシュ・ラインＡ＋
２がＬ２キャッシュ２０３又はメモリ２０９からフェッ
チされる。

【００４８】しかる後、ステップ６１４において、キャ
ッシュ・ラインＡ＋３がＬ２キャッシュ２０３内に存在
するかどうかの決定が行われる。それが存在しない場
合、プロセスはステップ６１５に進み、そこでは、キャ
ッシュ・ラインＡ＋３がメモリ２０９からプリフェッチ
され、プリフェッチ・バッファ４０２内に挿入される。
しかし、キャッシュ・ラインＡ＋３がキャッシュ２０３
内に存在する場合、プロセスはステップ６１５をスキッ
プする。

【００４９】再び、ステップ６１５からステップ６１６
への点線矢印は、ステップ６１６がステップ６１５の後
直ちには生じないことがあることを表す。

【００５０】ステップ６１６において、プロセッサ２０
１はキャッシュ・ラインＡ＋２にリクエストし、ライン
Ａ＋２に関してＬ１キャッシュ２０２へのアクセスを生
じさせる。ステップ６１３において、キャッシュ・ライ
ンＡ＋２がＬ１キャッシュ２０２にフェッチされたの
で、Ｌ１キャッシュ２０２はこのキャッシュ・ラインを
ＣＰＵ２０１に供給することができるであろう。ステッ
プ６１７において、ストリーム・アドレス・バッファ５
０１におけるストリーム・アドレスがそのストリームの
先頭においてアドレスＡ＋３を有するように更新され
る。しかる後、ステップ６１８において、Ｌ１キャッシ
ュ２０２は、キャッシュ・ラインＡ＋３が存在するかど
うかを決定するためにチェックされる。それが存在しな
い場合、キャッシュ・ラインＡ＋３がＬ２キャッシュ２
０３又はバッファ４０２からＬ１キャッシュ２０２にフ
ェッチされる。次に、ステップ６１９において、キャッ
シュ・ラインＡ＋４がＬ２キャッシュ２０３又はメモリ
２０９からプリフェッチ・バッファ４０２にフェッチさ
れるであろう。

【００５１】しかる後、ブラスト・モードがシステム２
００においてイネーブルされない場合（ステップ６２
０）、プロセスはステップ６１６に戻り、ＣＰＵ２０１
が図示のようなインクレメント順次態様でキャッシュ・
ラインを通してインクレメントし続ける限り、ステップ
６１６乃至６２１を通してループする。ステップ６２１
は、ステップ６１６において、ラインＡ＋３に対するＬ
１キャッシュ・アクセスが存在し得ることを表す。そこ
で、ステップ６１７において、ストリームはアドレスＡ
＋３でもって更新され、ステップ６１８において、ライ
ンＡ＋４がＬ１キャッシュ２０２にフェッチされ、そし
てステップ６１９において、キャッシュ・ラインＡ＋４
がバッファ４０２にフェッチされる。

【００５２】次に、データ・プリフェッチ・モードを説
明する。ステップ６２０では、ブラスト・モードがシス
テム２００においてイネーブルされる場合、キャッシュ
・ラインＡ＋３に対するＣＰＵ２０１からのリクエスト
が存在する時、プロセスはステップ６２２へ進むであろ
う。ステップ６２２において、そのようなリクエストに
対して、ＰＣＣ４０４はＬ１キャッシュ２０２内でキャ
ッシュ・ラインＡ＋３を捜すであろう。キャッシュ・ラ
インＡ＋３がＬ１キャッシュ２０２に存在するので、キ
ャッシュ・ラインＡ＋３がＣＰＵ２０１へ戻されるであ
ろう。しかる後、ステップ６２３において、ストリーム
・アドレス・バッファ５０１におけるストリーム・アド
レスがＡ＋４に更新される。ステップ６２４において、
キャッシュ・ラインＡ＋４が存在するかどうかを決定す
るためにＬ１キャッシュ２０２がチェックされる。それ
が存在しない場合、キャッシュ・ラインＡ＋４がバッフ
ァ４０２からＬ１キャッシュ２０２において実施された
プリフェッチ・バッファ位置にフェッチされるであろ
う。

【００５３】しかる後、ステップ６２５において、キャ
ッシュ・ラインＡ＋５がＬ２キャッシュ２０３に存在す
るかどうかの決定が行われる。それが存在する場合、プ
ロセスはステップ６２７へ進行するであろう。その実施
は、ノード・コントローラ２０５がすべてのストリーム
・バッファ・アクセスを通知されることを必要とするで
あろう。次のストリーム・バッファ・ラインがＬ２キャ
ッシュ２０３内になく、従って、フェッチされることを
必要とする場合の通知にその通知を限定することはノー
ド・コントローラ・バッファ４０５及び４０６をプロセ
ッサ２０１との同期から一時的に外させるであろう。こ
の設計トレード・オフの利点は、ステップ６２６及び６
２７が結合され、ノード・コントローラ２０５に対する
アドレス・バス・トラフィックを減少させることができ
ることである。カバーされる主要なケースでは、Ａ、Ａ
＋１等のラインはプリフェッチ前にはキャッシュ２０２
に全く存在しないので、キャッシュ・ラインＡ＋５は、
通常は、Ｌ２キャッシュ２０３にあるとは考えられない
ことに注目すべきである。

【００５４】ステップ６２６及び６２７が上記の理由で
結合される時、ステップ６２７の通知はステップ６２６
のプリフェッチに加えられた４つの追加制御ビットでも
って実施可能である。その４ビットは１ビットの有効プ
リフェッチ、２ビットのストリーム識別、及び１ビット
のプリフェッチ方向である。キャッシュ・ラインＡ＋５
及びこれらのビットに対するアドレスを使用して、ノー
ド・コントローラ２０５はキャッシュ・ラインＡ＋６及
びＡ＋７に対してメモリ・リクエストを発生することが
できる。前述のように、ノード・コントローラ２０５
は、任意の数のキャッシュ・ラインをプリフェッチする
ために実施可能である。ステップ６２８において、ノー
ド・コントローラ２０５は、キャッシュ・ラインＡ＋６
をプリフェッチ・バッファ４０５（ＰＢＦＲ２）にプリ
フェッチし、キャッシュ・ラインＡ＋７をバッファ４０
６（ＰＢＦＲ３）にプリフェッチするであろう。

【００５５】ステップ６２８及び６２９の間の点線は、
キャッシュ・ラインＡ＋４に対するＣＰＵ２０１からの
リクエストがステップ６２８に続いて直ちに生じないこ
とがあることを表す。

【００５６】ステップ６２９において、Ｌ１キャッシュ
２０２は、ＣＰＵ２０１によってリクエストされたキャ
ッシュ・ラインＡ＋４に関してアクセスされる。キャッ
シュ・ラインＡ＋４はステップ６２４においてＬ１キャ
ッシュ２０２に挿入されたので、キャッシュ・ラインＡ
＋４はＣＰＵ２０１へ戻されるであろう。ステップ６３
０において、ストリーム・アドレスがインクレメントさ
れてアドレスＡ＋５を先頭にされる。ステップ６３１に
おいて、Ｌ１キャッシュ２０２は、キャッシュ・ライン
Ａ＋５が存在するかどうかを決定するためにチェックさ
れる。それが否定される場合、キャッシュ・ラインＡ＋
５がＬ２キャッシュ２０３又はバッファ４０２からＬ１
キャッシュ２０２にフェッチされる。

【００５７】しかる後、ステップ６３２において、キャ
ッシュ・ラインＡ＋６はバッファ４０５からバッファ４
０２に移動する。ステップ６３３において、キャッシュ
・ラインＡ＋７がバッファ４０６からバッファ４０５に
移動する。しかる後、ステップ６３４において、ノード
・コントローラ２０５はキャッシュ・ラインＡ＋８をプ
リフェッチするように通知される。この実施例では、ス
テップ６３２におけるキャッシュ・ラインＡ＋６のフェ
ッチは、キャッシュ・ラインＡ＋８をプリフェッチする
ようにノード・コントローラ２０５へ通知することであ
る。ステップ６３５において、ノード・コントローラ２
０５はキャッシュ・ラインＡ＋８をメモリ２０９からバ
ッファ４０６にプリフェッチする。

【００５８】しかる後、ＣＰＵ２０１がインクレメンタ
ル順次態様でキャッシュ・ラインのアクセスを継続する
（即ち、ＣＰＵ２０１がその割り当てられたストリーム
におけるキャッシュ・ラインのアクセスを継続する）限
り、プロセスは、ステップ６２９−６３６を通してルー
プ動作をインクレメンタル態様で継続するであろう（ス
テップ６３６）。

【００５９】上記の説明において、バス・インターフェ
ース装置（ＢＩＵ）４０１がメモリ２０９からのキャッ
シュ・ラインのフェッチを遂行してもよい。ノード・コ
ントローラ２０５はスイッチ２０７における一部分であ
ってもよい。

【００６０】有効アドレスはページ境界に跨って連続的
であり、実アドレスはそのように連続的ではないので、
ストリーム・アドレス・バッファ５０１における２つの
アドレスを比較する時に有効アドレスを利用することは
有利であることが多い。更に、上記のため、インクレメ
ンタル・アドレスを生じさせるために、カウンタを使用
してもよい。

【００６１】前述のように、ＢＩＵ４０１からメモリ２
０９へのフェッチにおいて、それがキャッシュ・ライン
をバッファ４０５及び４０６にプリフェッチするためで
あることをノード・コントローラ２０５に通知するため
に、制御ビットを利用してもよい。ノード・コントロー
ラ２０５がそれのバッファへのプリフェッチを遂行する
ことをこの特定のライン・リクエストが要求すること
を、１つのビットがノード・コントローラ２０５に知ら
せるようにしてもよい。どのストリーム番号がプリフェ
ッチと関連するかを、他の２つのビットがノード・コン
トローラ２０５に知らせるようにしてもよい。キャッシ
ュ・ラインにおけるどの方向にアドレスが向いているか
を、他のビットが表すようにしてもよい。ノード・コン
トローラ２０５は、プリフェッチを行うように通知され
る時、ＣＰＵ２０１の動作とは無関係にそのようなプリ
フェッチを行ってもよい。

【００６２】Ｌ１キャッシュ２０２内にストリーム・バ
ッファ・ラインの１つを有する利点は、Ｌ１キャッシュ
２０２におけるそのバッファ・ラインに含まれる特定の
キャッシュ・ラインがプロセッサ２０１によってリクエ
ストされる時、Ｌ１キャッシュ２０２においてヒットが
生じ、ミスは生じない。一般に、ミスは、たとえリクエ
ストされたキャッシュ・ラインがＬ１キャッシュ２０２
に接続された別のバッファに含まれるものであっても生
じるであろう。そのようなミスのため、そのキャッシュ
・ラインをストリーム・バッファからＣＰＵ２０１へ検
索するためには余分なハードウエアが必要であろう。ス
トリーム・バッファ・キャッシュ・ラインの１つとして
作用するＬ１キャッシュ２０２は、論理的には、プリフ
ェッチ・ストリーム・バッファに含まれるといえる。

【００６３】Ｌ１キャッシュ２０２及びＬ２キャッシュ
２０３に関する組込みを維持する場合、キャッシュ・ラ
インが上記の手順におけるバッファ４０２からＬ１キャ
ッシュ２０２へ移動する時、同じキャッシュ・ラインが
Ｌ２キャッシュ２０３にも含まれるであろう。

【００６４】伝統的な実施方法では、Ｌ２キャッシュは
Ｌ１キャッシュにおけるデータのスーパセットを含んで
いる。この「包含（inclusion)」アルゴリズムはデータ
処理システムにおけるコヒーレンシを確保するための手
段を与える。本質的には、包含は、Ｌ１キャッシュにあ
るすべてにキャッシュ・ラインがＬ２キャッシュに存在
することを意味する。Ｌ１キャッシュは、例えば、Ｌ１
キャッシュにおけるデータの如何なる修正もＬ２キャッ
シュにおいてミラーされるようなライトバックを遂行す
ることができる。キャッシュ・ラインがＬ１キャッシュ
から除去される時、そのデータはＬ２キャッシュにも存
在するので、それは廃棄可能である。

【００６５】Ｌ２キャッシュ２０３は直接マップ可能で
あり、それは、メモリにおけるすべてのラインがＬ２キ
ャッシュ２０３における唯一のロケーションに存在する
ことが可能であることを意味する。逆に、連想キャッシ
ュは、特定のキャッシュ・ラインが同時に存在し得る幾
つかのロケーションを有する。例えば、そのような構造
に対して、０で終わる（即ち、０でもって連結された）
アドレスを持ったすべてのキャッシュ・ラインがＬ２キ
ャッシュ２０３では０スロットにおいて終わるであろ
う。１で終わるすべてのキャッシュラインは１スロット
において終わるであろうし、１５で終わるすべてのキャ
ッシュ・ラインは１５スロットにおいて終わるであろ
う。

【００６６】逆に、Ｌ１キャッシュ２０２はセット・ア
ソシアティブである。従って、キャッシュ・ラインはＬ
１キャッシュにおける多数の場所において現れることが
起こり得る。その結果、例えば、Ｌ１キャッシュ２０２
は、１５で終わるＸＹＺライン及び１５で終わるＡＢＣ
ラインを同時に有することが起こり得る。そのような例
は、「包含」がＬ１キャッシュ２０２及びＬ２キャッシ
ュ２０３に間に維持されない場合に生じることがある。
しかし、システム２００がそれらのキャッシュの間に
「包含」を維持しようとする場合、ＣＰＵ２０１がＸＹ
ＺをロードしたいがそれがＡＢＣラインも含んでいる場
合、Ｌ２キャッシュ２０３は、たとえＬ１キャッシュ２
０２がそれをロードすべき多数の場所を持っていても、
それを置くべき１つの場所しか持たないので、それがＸ
ＹＺをロードする前にＣＰＵ２０１にＡＢＣラインを投
棄させるであろう。例えば、図６乃至図９に関して示さ
れたアルゴリズムに従って、キャッシュ・ラインＸＹＺ
１５がバッファ４０２内にあり、ＣＰＵ２０１がＬ１キ
ャッシュ２０２内に存在するＸＹＺ１４においてヒット
を得るものと仮定する。その流れ図によれば、バッファ
４０２におけるＸＹＺ１５はＬ１キャッシュ２０２にプ
リフェッチされるであろう。「包含」が維持される場
合、ＸＹＺ１５はＬ２キャッシュ２０３にもロードされ
るであろう。Ｌ２キャッシュ２０３がＡＢＣ１５も含む
場合、後述のプリフェッチ・オペレーションがＬ１キャ
ッシュ２０２におけるキャッシュ・ラインをスラッシュ
或いはキック・アウトさせるであろう。

【００６７】ＸＹＺ１５をＬ１キャッシュ２０２にプリ
フェッチするためにＬ１キャッシュ２０２におけるライ
ンが廃棄させられるのみならず、Ｌ２キャッシュ２０３
におけるＡＢＣ１５もＸＹＺ１５の包含（Ｌ２キャッシ
ュ２０３が直接マップされることを想起して欲しい）の
ためにキック・アウトされるであろうし、Ｌ１キャッシ
ュ２０２におけるキャッシュ・ラインはキャッシュ・ラ
インＡＢＣも含む可能性がある。ＸＹＺ１５の包含のた
めにＡＢＣ１５がＬ２キャッシュ２０３から廃棄される
場合、キャッシュ・ラインＡＢＣ１５もＬ１キャッシュ
２０２から廃棄されなければならないであろう。

【００６８】上記のシナリオは、ランダム・データ及び
ストリーム・データの両方を使用するアプリケーション
・プログラムにおけるように、ＣＰＵ２０１がランダム
・データを使用しようとする時の問題である。このラン
ダム・データはＬ２キャッシュ２０３内に置かれるであ
ろう。しかし、上記のシナリオの場合、及びデータ包含
の場合、ＸＹＺ１５がＬ１キャッシュ２０２にプリフェ
ッチされる時、それはＬ２キャッシュ２０３におけるキ
ャッシュ・ラインにも含まれるであろう。そのキャッシ
ュ・ラインはＬ２キャッシュ２０３におけるそのロケー
ションに既に存在しているデータを変位するであろう。
このデータがＣＰＵ２０１によって処理されているラン
ダム・データの一部分であった場合、ＣＰＵ２０１がそ
の特定のデータ片の使用を必要とする次の時に、それは
メモリ２０９からそれをリクエストしなければならない
であろう。その結果、前述のように、かなりのメモリ待
ち時間問題を生じるであろう。

【００６９】その他の或オペレーションでは、データの
ストリングが、それらの修正の意図なしにＣＰＵ２０１
へ読み込まれることがある。１つの例は、そのストリン
グが特定のレコードの発生のために読み取られるデータ
ベース・アプリケーション・サーチであろう。そのよう
なレコードに遭遇する時、それはそこに書き込まれても
よく、書き込まれなくてもよい。これらのケースでは、
読み取られるデータはＬ２キャッシュ２０３においては
必要とされず、実際に、Ｌ２キャッシュ２０３へのデー
タの書込は除去による更なるバス輻輳を生じさせるであ
ろう。Ｌ２キャッシュ２０３における必要なデータを一
時的読み取り専用データでもって変位させることによっ
て、パフォーマンスは衝撃を受けるであろう。

【００７０】ブラスト・モードでは、図６乃至図９に関
して上述したように、プリフェッチ・データはＬ１キャ
ッシュ２０２に書き込まれ、Ｌ２キャッシュ２０３には
書き込まれない。これは、Ｌ２キャッシュ２０３に含ま
れてないラインをＬ１キャッシュ２０２において作成す
る。ディレクトリ・ベースのシステムでは、未修整のラ
インがキャッシュ・コントローラ４１１において廃棄さ
れる（割振り解除される）時、その割振り解除はシステ
ム・メモリのためのディレクトリに信号されなければな
らない。それは、どのプロセッサがどのラインを持つか
を追跡する。従って、Ｌ１キャッシュ・コントローラ４
１１がＬ２キャッシュ２０３に含まれてない未修整のラ
インを割振り解除した時、この事象はメモリ・ディレク
トリに信号されなければならない。上記の実施例では、
この事象を信号することは、ＣＰＵ２０１からメモリ２
０９のディレクトリに送られた「リセット包含」コマン
ドを介するものである。

【００７１】次に、図１０を参照すると、新しいキャッ
シュ・ラインがＬ１キャッシュ２０２にロードされ、Ｌ
２キャッシュ２０３にはロードされない（排他）時の流
れ図が示される。プロセスはステップ７００で始まり、
そこでは、Ｌ１キャッシュ２０２からのリクエストされ
たキャッシュ・ラインに関してミスが生じている。この
ミスは通常の要求ミスか或いは図６乃至図９に示された
プリフェッチ・リクエストである。しかる後、ステップ
７０１において、ブラスト・モードがイネーブルされて
いるかどうかの決定が行われる。それが否定される場
合、プロセスはステップ７０５に進み、プリフェッチが
リクエストされたかどうかを決定する。それが否定され
る場合、プロセスはステップ７０１に戻る。しかし、ス
テップ７０５において、プリフェッチがリクエストされ
た場合、プロセスはステップ７０６に進み、フェッチさ
れるべき所望のラインがＬ２キャッシュ２０３に存在す
るかどうかを決定する。それが否定される場合、ステッ
プ７０８において、リクエストされたキャッシュ・ライ
ンがメモリ２０９から又はストリーム・バッファ４０
２、４０５、又は４０６の１つからＬ１キャッシュ２０
２及びＬ２キャッシュ２０３にプリフェッチされる。

【００７２】更に、排他タグ（１つ又は複数のビット）
がＬ１キャッシュ・ディレクトリ４１０においてリセッ
トされる。ディレクトリ４１０はキャッシュ・ディレク
トリの典型的な機能を遂行する。この場合、プリフェッ
チされたキャッシュ・ラインと関連したディレクトリ・
フィールドにおけるエントリは、そのプリフェッチされ
たキャッシュ・ラインがＬ１キャッシュ２０２及びＬ２
キャッシュ２０３の両方に存在することをその排他タグ
・ビットが表すようにリセットされる。後述するよう
に、Ｌ１キャッシュ・コントローラ４１１における制御
ロジックは、キャッシュ・ラインを割振り解除する時に
この排他タグをモニタするように図１１の流れ図に従っ
て修正される。

【００７３】プリフェッチされるべきラインがＬ２キャ
ッシュ２０３に存在する場合、プロセスはステップ７０
４に進み、Ｌ２キャッシュ２０３からＬ１キャッシュ２
０２にそのキャッシュ・ラインをプリフェッチする。ス
テップ７００、７０４、７０５、７０６、７０７、及び
７０８に関して説明した上記手順は、本質的に、要約さ
れた形式で図６乃至図９に示されたステップ６０１乃至
６２１に対応する。ステップ７０４及び７０８はステッ
プ６０７、６１３、６１８、及び６１９に対応する。

【００７４】ステップ７０１において、ブラスト・モー
ドがイネーブルされた場合、プロセスはステップ７０２
に進み、ブラスト・モードにおけるプリフェッチがイネ
ーブルされたかどうかを決定する。しかし、ブラスト・
モードにおけるプリフェッチが開始された場合、プロセ
スはステップ７０３に進み、プリフェッチされるべきラ
インがＬ２キャッシュ２０３に存在するかどうかを決定
する。それが肯定される場合、プロセスはステップ７０
４に進み、そのラインをＬ２キャッシュ２０３からＬ１
キャッシュ２０２にプリフェッチする。更に、Ｌ１ディ
レクトリ４１０における排他タグがステップ７０８に関
連して上述したようにリセットされる。

【００７５】そのキャッシュ・ラインがＬ２キャッシュ
２０３において存在しない場合、プロセスはステップ７
０７に進み、メモリ２０９から又はバッファ４０２、４
０５、４０６の１つからＬ１キャッシュ２０２にそのキ
ャッシュ・ラインをプリフェッチする。更に、上記の排
他タグはＬ１ディレクトリ４１０においてセットされ、
メモリ２０９又はストリーム・バッファの１つからプリ
フェッチされたキャッシュ・ラインの１つがＬ１キャッ
シュ２０２に存在し、Ｌ２キャッシュ２０３に存在しな
いことを表す。

【００７６】図１０の流れ図によって示されるように、
ブラスト・モードがイネーブルされなかった時、「包
含」が維持される。一方、「包含」が維持されてないブ
ラスト・モードでは、ステップ７０７においてプリフェ
ッチがＬ１キャッシュ２０２に対して生じるだけであ
る。

【００７７】次に、図１０を参照すると、「包含」がＬ
１キャッシュ２０２及びＬ２キャッシュ２０３の間で維
持されてない時（ブラスト・モードがイネーブルされて
いる時）のキャッシュ・ラインの割振り解除の流れ図が
示される。プロセスはステップ８０１において開始し、
ステップ８０２に進む。そこでは、そのキャッシュ・ラ
インが割振り解除されるべきかどうかの決定が行われ
る。それが否定される場合、特定のキャッシュ・ライン
を割振り解除する決定が行われるまでプロセスはループ
する。プロセスはステップ８０３に進み、そこでは、割
振り解除されるべきキャッシュ・ラインが修正されたか
どうかの決定が行われる。それが否定される場合、その
割振り解除されべきキャッシュ・ラインがＬ２キャッシ
ュ２０３にも存在するかどうかの決定が行われる。この
決定は、コントローラ４１１がディレクトリ４１０にお
いて排他タグをモニタすることによって行うことが可能
である。

【００７８】キャッシュ・ラインがＬ２キャッシュ２０
３にも存在しないことを表す排他タグがこのキャッシュ
・ラインに関してセットされた場合、プロセスはステッ
プ８０９に進む。そこでは、システム２００は「リセッ
ト包含」信号を信号され、割り振られるべきキャッシュ
・ラインに対応するアドレスがシステム２００を通して
バス２０４によって送られ、そのキャッシュラインは割
振り解除される。

【００７９】ステップ８０８において、キャッシュ・ラ
インがＬ２キャッシュ２０３に存在するという決定が行
われる（即ち、排他タグがセットされなかった）場合、
プロセスはステップ８１０に進み、「包含」に後続する
時の従来の方法でキャッシュ・ラインを割振り解除す
る。

【００８０】ステップ８０３において、ＣＰＵによって
割振り解除されるべきキャッシュ・ラインが修正された
ことが決定される場合、プロセスはステップ８０４に進
み、そのキャッシュ・ラインがＬ２キャッシュ２０３に
存在するかどうかを決定する。上記のように、これは、
ディレクトリ４１０における排他タグがセットされたか
どうかをコントローラ４１１が決定することによって達
成可能である。排他タグがセットされなかった場合、ス
テップ８０６において、そのキャッシュ・ラインはＬ１
キャッシュ２０２からＬ２キャッシュ２０３に書き込ま
れる。それは、システム２００におけるデータ・コヒー
レンシに原因がある。

【００８１】ステップ８０４におけるキャッシュ・ライ
ンがＬ２キャッシュ２０３に存在しない（即ち、排他タ
グがこのキャッシュ・ラインに関してセットされた）場
合、プロセスはステップ８０５に進み、そのキャッシュ
・ラインをメモリ２０９に書き込む。

【００８２】上記のように、ストリーム・フィルタ・エ
ントリ及びストリーム・アドレス・バッファ・エントリ
（及び対応するストリーム・データ・バッファ・エント
リ）の割振りを管理するためにフィルタ置換アルゴリズ
ムが実施される。図６乃至図９に関する上記の説明に従
って、フィルタ・ヒットの発生（ステップ６３７）時に
ストリームが割振り可能である（ステップ６１２）。そ
のようなストリームの割振り時に、ストリーム・アドレ
ス・バッファに既に存在するストリームはスラッシュ
（置換）されるであろう。更に、ストリーム・エントリ
の新しいセット全体が種々のプリフェッチ・バッファに
プリフェッチされるであろう。

【００８３】図６乃至図９の説明において、ＣＰＵ２０
１がプリフェッチ・バッファに存在するストリーム・デ
ータに対するリクエスト相互間で非ストリーム・データ
をリクエストし得る可能性に関するいくつかの検討事項
がある。問題は、そのようなリクエストの結果、ストリ
ーム・アドレス・バッファにおける新しいストリームの
割振りを生じ、ＣＰＵ２０１によってアクセスされてい
る既存のストリームを置換する。既存のストリームは繰
り返しアクセスされる「非常に良好な」ストリームであ
ることが多く、新たに割り振られたストリームは非常に
頻繁にはアクセスされないで終わることが多いので、こ
れは効率的ではない。従って、本発明の最終目的は、ス
トリーム・バッファからのストリームを、それが最近ア
クセスされてなく且つ新しいストリームが検出された時
にだけ割り振ることによって、プロセッサのパフォーマ
ンスを増大させることである。

【００８４】以下の説明は下記の表に関連するものであ
る。「相対的時間」は、時間０で始まりそして左から右
へ時間１７まで進行する。従って、各列はその列の最上
部に示される相対的時間に対応する。「キャッシュ・ミ
ス・シーケンス」は例示的シーケンスであり、本質的に
は、表示されたキャッシュ・ラインに関してＬ１キャッ
シュ・ミスがあるステップ６０１及び６０２に対応す
る。上記のように、「ストリーム・アドレス・バッフ
ァ」は４つのストリームに対する容量を有する。しか
し、本発明では、任意の数のストリームが実施可能であ
る。「ストリーム・フィルタ」は１０個のエントリに対
する容量を有する。しかし、本発明では、任意の数のエ
ントリが実施可能である。

【００８５】開示された発明の実施例は、いつでも４つ
までのストリームを割り振ることができるストリーム・
バッファを実現するためのものである。その実施例に関
連したフィルタ・バッファは、ＬＲＵに基づいて割り振
られた１０個のエントリを有する。

【００８６】通常のオペレーションでは、ストリーム・
アクセスがフィルタによって検出された時、そのストリ
ームに対するフィルタ・エントリはそのフィルタのＭＲ
Ｕ位置にセットされる。新しいラインがその関連のスト
リームにおいてアクセスされる度に、そのエントリはＭ
ＲＵ位置に戻る。例えば、４つのアクティブなストリー
ム（１、２、３、４）があった場合、及び他のキャッシ
ュ・ミスがなかった場合、それらの４つのストリームは
いつもフィルタ・バッファの４つのＭＲＵ位置の１つを
占めるであろう。その後のストリーム・アクセス相互間
でキャッシュ・ミスがあった場合、フィルタはそれらに
対するエントリも含み、従って、４つのストリームは、
時々、４つのＭＲＵ位置以外の位置を占めるであろう。
１０個のエントリのフィルタの場合、２つの連続したス
トリーム・アクセスの１０個より少ないキャッシュ・ミ
スのインスタンスがある限り、ストリームはフィルタ内
に割り振られたままであろう。ＬＲＵ法は、１０個のフ
ィルタ・エントリすべてをそのミスしたラインに割り振
ることによってストリーム・フィルタ・エントリをエー
ジ・アウトするであろう。４つのストリームが割り振ら
れた場合、ストリーム・フィルタ・エントリは、７つの
介在キャッシュ・ミスがあるまでフィルタをエージ・オ
フしないであろう（それは、そのフィルタが４つのスト
リームに対する十分なエントリ及び６つの他のフィルタ
・エントリを有するためである）。

【００８７】下記の表を参照すると、一連のキャッシュ
・アクセスを通して進行するストリーム・バッファ及び
フィルタの状態が示される。その例は一連のキャッシュ
・ミス・ラインを示す。思惑的にロードされたラインが
第１時間（第１ヒット）に対してアクセスされる時、ス
トリーム・バッファにおいてデータ・プリフェッチ・モ
ード又はブラスト・モードにあるラインがフィルタのＭ
ＲＵ位置まで移動することを理解してほしい。

【表１】

【００８８】その例では、開始時（相対時間０）におい
て４つのアクティブなストリーム（Ａ，Ｂ，Ｃ，Ｄ）が
あり、それらはストリーム・アドレス・バッファに含ま
れる。最後の１０個のＬ１ミスが、位置１における最も
最近のエントリと共にストリーム・フィルタ内容によっ
て示される。そのストリーム・フィルタにおける「Ｎ」
個のエントリはここでは重要でないミスを示す。

【００８９】相対時間１では、ストリームＡに対するＬ
１へのもう１つのライン・ロードがある。その結果生じ
るストリーム・フィルタの内容がこの列に示される。Ａ
が最も最近のミスであるので、Ａエントリが位置１まで
移動し、位置８におけるＡエントリを置換する。別の方
法では、エントリ８は無効にされるが、フィルタからは
除去されない。

【００９０】ミス・シーケンスは、ストリーム割振りを
トリガする新しいストリームを示すＸ１、Ｘ２によって
処理される。相対時間７において、Ｘ４ミスによって、
Ｄに対するストリーム・エントリがそのフィルタから除
去される。しかし、この時点で、ストリームＤは依然と
してストリーム・アドレス・バッファにおいて有効であ
り、従って、このストリームに対するアクセスは依然と
して検出されるであろうし、そのストリームはプリフェ
ッチされ続けるであろう。その例では、相対時間８にお
いて、ストリームＤは再びアクセスされ、Ｄをストリー
ム・フィルタに戻す。

【００９１】相対時間１３において、ストリームＸ５に
対する第２のミスが生じる。この時点で、ストリームＢ
は最早ストリーム・フィルタにはないので、Ｘ５がスト
リーム・アドレス・バッファ２に割り当てられる。相対
時間１４において、ストリームＸ２に対する第２のミス
が生じる。４つのアクティブなストリーム（Ａ，Ｘ５，
Ｃ，Ｄ）がストリーム・フィルタに含まれるので、Ｘ２
はストリームとして割振りされない。更に、他のＸ２エ
ントリ（幾つかある）は、それがエージ・アウトされる
までストリーム・フィルタに残る。同様に、相対時間１
５において、そのフィルタにおける他のＸ３エントリが
行われる。

【００９２】相対時間１７において、ストリームＸ６が
割り振られるが、Ｘ６に対するフィルタ・ヒットがない
時、ストリームＣは最早そのフィルタにはない。

【００９３】この機構を使用することは、アプリケーシ
ョンにおいて４つより多くのデータ・ストリームが存在
する場合、ストリーム・アドレス・バッファが４つのア
クティブ・ストリームを保持することを可能にする。こ
の機構がない場合、４つよりも多くのアクティブ・スト
リームは連続的に新しいストリーム割振りを生じさせ、
データは廃棄のためにのみプリフェッチ・バッファに読
み込まれる。その結果、プロセッサ・パフォーマンスは
低下するであろう。

【００９４】本発明の別の実施例は、割り振られたスト
リームに対するフィルタ・エントリを使用しないでスト
リームが割振り解除されるべきことを決定するために、
ストリーム・ヒット相互間の所定数のキャッシュ・ライ
ン・アクセスをカウントするカウンタを提供するための
ものである。そのようなカウンタは、特定のキャッシュ
・ラインに対するキャッシュ・ミス及びヒットをカウン
トするようにＰＣＣ４０４において実施可能である。本
発明の技術的範囲内おける他の機構も、同様に、当業者
によって考え得ることである。

【００９５】まとめとして、本発明の構成に関して以下
の事項を開示する。

【００９６】（１）メイン・メモリからメモリ・サブシ
ステムにデータをプリフェッチするように動作可能な装
置にして、前記メモリ・サブシステムは前記メイン・メ
モリに結合されたプロセッサと関連付けられるものにお
いて、Ｘ個（Ｘは正の整数）のストリームを含むように
動作可能なストリーム・バッファと、所定数の潜在的な
新しいストリームが検出された後、前記Ｘ個のストリー
ムの１つを割振り解除するように動作可能な手段と、を
含む装置。 （２）前記所定数の後、前記ストリーム・バッファに新
しいストリームを割り振るように動作可能な手段を含
み、前記新しいストリームは前記Ｘ個（Ｘは前記ストリ
ーム・バッファにおけるストリームの最大数）のストリ
ームの１つを置換することを特徴とする上記（１）に記
載の装置。 （３）前記メモリ・サブシステムは前記プロセッサと関
連したキャッシュであることを特徴とする上記（１）に
記載の装置。 （４）前記Ｘ個のストリームの１つは前記新しいストリ
ームが割り振られるまで前記ストリーム・バッファに残
ることを特徴とする上記（２）に記載の装置。 （５）前記割振り解除するように動作可能な手段はＹ個
（Ｙは正の整数）のエントリを含むように動作可能なス
トリーム・フィルタを含むこと、前記Ｙ個のエントリは
ＬＲＵに基づいてベースで割り振られること、前記Ｙ個
のエントリはメモリ・サブシステム・ミスに対応するこ
と、及び前記所定数の後に前記ストリーム・フィルタか
らエントリがエージ・アウトされること、を特徴とする
上記（１）に記載の装置。 （６）前記割振り解除するように動作可能な手段は前記
所定数をカウントするための手段を有することを特徴と
する上記（１）に記載の装置。 （７）前記Ｙ個のエントリのうちの２つは同じものであ
ることを特徴とする上記（５）に記載の装置。 （８）前記所定数はＹに等しいことを特徴とする上記
（５）に記載の装置。 （９）前記新しいストリームに対してメモリ・サブシス
テムがアクセスする前に前記Ｘ個のストリームの１つに
対するメモリ・サブシステム・アクセスがある時、前記
Ｘ個のストリームの１つを再割り振りするように動作可
能な手段を含むことを特徴とする上記（５）に記載の装
置。 （１０）メイン・メモリから、バスによって前記メイン
・メモリに接続されたプロセッサと関連したキャッシュ
にデータをプリフェッチするためのシステムにして、Ｘ
個のストリームを割り振るためのストリーム・バッファ
と、それぞれがキャッシュ・ミスを表すＹ個のエントリ
を有するストリーム・フィルタであって、前記Ｘ及びＹ
は正の整数であり、前記Ｘ個のストリームの各々は前記
Ｙ個のエントリのうちの少なくとも１つによって表され
るものと、前記ストリームを表す前記Ｙ個のエントリの
うちの少なくとも１つのすべてが前記ストリーム・フィ
ルタから割振り解除されてしまうまで前記ストリーム・
バッファにおいてストリームを維持するための手段と、
を含むシステム。 （１１）前記ストリームを表す前記Ｙ個のエントリのう
ちの少なくとも１つのすべてが前記ストリーム・フィル
タから割振り解除された後、前記ストリーム・バッファ
において新しいストリームを、前記新しいストリームに
対応したデータのキャッシュ・ミスに応答して割り振る
ための手段を含むことを特徴とする上記（１０）に記載
のシステム。 （１２）前記ストリームに対応するキャッシュ・ミスが
生じる時、前記ストリームを表す前記Ｙ個のエントリの
少なくとも１つのすべてが前記ストリーム・フィルタか
ら割振り解除された後、前記ストリーム・バッファにお
けるストリームを再割振りするための手段を含むことを
特徴とする上記（１０）に記載のシステム。 （１３）前記Ｙ個のエントリはＬＲＵに基づいて前記ス
トリーム・フィルタから割振り解除されることを特徴と
する上記（１０）に記載のシステム。 （１４）前記ストリームは前記新しいストリームが前記
ストリーム・バッファにおいて割り振られるまで前記ス
トリーム・バッファに残ることを特徴とする上記（１
１）に記載のシステム。 （１５）データ処理システムにおいてバスによりプロセ
ッサに接続されたメイン・メモリから、前記プロセッサ
に接続されたＬ１キャッシュにキャッシュ・ラインをプ
リフェッチするための方法にして、前記プリフェッチす
ることはストリーム・バッファ及びストリーム・フィル
タを増大し、前記ストリーム・バッファはアドレス・バ
ッファ及びデータ・バッファを含み、前記ストリーム・
バッファは１つ又は複数のアクティブ・ストリームを保
持し、前記ストリーム・フィルタは前記１つ又は複数の
アクティブ・ストリームに対応した１つ又は複数のエン
トリを含むものにおいて、一連のＬ１キャッシュ・ミス
をモニタするステップと、前記Ｌ１キャッシュ・ミスに
応答してＬＲＵに基づき前記ストリーム・フィルタにお
けるエントリを置換するステップと、前記１つ又は複数
のアクティブ・ストリームに対応した前記１つ又は複数
のエントリのすべてが前記置換するステップによって置
換されるまで、前記ストリーム・バッファにおける前記
１つ又は複数のアクティブ・ストリームの１つを維持す
るステップと、を含む方法。 （１６）前記１つ又は複数のアクティブ・ストリームの
１つに対応した前記１つ又は複数のエントリのすべてが
前記置換するステップによって置換された後、前記スト
リーム・バッファにおける新しいアクティブ・ストリー
ムを、前記新しいアクティブ・ストリームに対応したデ
ータのキャッシュ・ミスに応答して割り振るステップを
含むことを特徴とする上記（１５）に記載の方法。 （１７）前記１つ又は複数のアクティブ・ストリームの
１つに対応したキャッシュ・ミスが生じた時、前記１つ
又は複数のアクティブ・ストリームの１つに対応した前
記１つ又は複数のエントリのすべてが前記置換するステ
ップによって置換された後、前記ストリーム・バッファ
における前記１つ又は複数のアクティブ・ストリームの
１つを再割振りするステップを含むことを特徴とする上
記（１５）に記載の方法。 （１８）前記新しいアクティブ・ストリームが前記スト
リーム・バッファにおいて割り振られるまで、前記１つ
又は複数のアクティブ・ストリームの１つが前記ストリ
ーム・バッファに残ることを特徴とする上記（１６）に
記載の方法。

【図面の簡単な説明】

【図１】本発明に従って構成可能なマルチプロセッサ・
システムを示す。

【図２】本発明に従って構成可能なデータ処理システム
を示す。

【図３】ストリーム・フィルタ及びストリーム・バッフ
ァを示す。

【図４】図２に示されたシステムの更に詳細な図を示
す。

【図５】本発明に従って機能的な図を示す。

【図６】本発明の流れ図の一部分を示す。

【図７】本発明の流れ図の一部分を示す。

【図８】本発明の流れ図の一部分を示す。

【図９】本発明の流れ図の一部分を示す。

【図１０】Ｌ１キャッシュへのキャッシュ・ラインのプ
リフェッチ及びそのプリフェッチされたキャッシュ・ラ
インと関連したディレクトリ・フィールドにおけるタグ
・ビットの設定の流れ図を示す。

【図１１】図１０の流れ図と関連してプリフェッチされ
たプリフェッチ・キャッシュ・ラインの割振り解除を示
す。

Claims (18)

【特許請求の範囲】
1. 【請求項１】メイン・メモリからメモリ・サブシステム
   にデータをプリフェッチするように動作可能な装置にし
   て、前記メモリ・サブシステムは前記メイン・メモリに
   結合されたプロセッサと関連付けられるものにおいて、 Ｘ個（Ｘは正の整数）のストリームを含むように動作可
   能なストリーム・バッファと、 所定数の潜在的な新しいストリームが検出された後、前
   記Ｘ個のストリームの１つを割振り解除するように動作
   可能な手段と、 を含む装置。
2. 【請求項２】前記所定数の後、前記ストリーム・バッフ
   ァに新しいストリームを割り振るように動作可能な手段
   を含み、 前記新しいストリームは前記Ｘ個（Ｘは前記ストリーム
   ・バッファにおけるストリームの最大数）のストリーム
   の１つを置換することを特徴とする請求項１に記載の装
   置。
3. 【請求項３】前記メモリ・サブシステムは前記プロセッ
   サと関連したキャッシュであることを特徴とする請求項
   １に記載の装置。
4. 【請求項４】前記Ｘ個のストリームの１つは前記新しい
   ストリームが割り振られるまで前記ストリーム・バッフ
   ァに残ることを特徴とする請求項２に記載の装置。
5. 【請求項５】前記割振り解除するように動作可能な手段
   はＹ個（Ｙは正の整数）のエントリを含むように動作可
   能なストリーム・フィルタを含むこと、 前記Ｙ個のエントリはＬＲＵに基づいてベースで割り振
   られること、 前記Ｙ個のエントリはメモリ・サブシステム・ミスに対
   応すること、及び前記所定数の後に前記ストリーム・フ
   ィルタからエントリがエージ・アウトされること、 を特徴とする請求項１に記載の装置。
6. 【請求項６】前記割振り解除するように動作可能な手段
   は前記所定数をカウントするための手段を有することを
   特徴とする請求項１に記載の装置。
7. 【請求項７】前記Ｙ個のエントリのうちの２つは同じも
   のであることを特徴とする請求項５に記載の装置。
8. 【請求項８】前記所定数はＹに等しいことを特徴とする
   請求項５に記載の装置。
9. 【請求項９】前記新しいストリームに対してメモリ・サ
   ブシステムがアクセスする前に前記Ｘ個のストリームの
   １つに対するメモリ・サブシステム・アクセスがある
   時、前記Ｘ個のストリームの１つを再割り振りするよう
   に動作可能な手段を含むことを特徴とする請求項５に記
   載の装置。
10. 【請求項１０】メイン・メモリから、バスによって前記
    メイン・メモリに接続されたプロセッサと関連したキャ
    ッシュにデータをプリフェッチするためのシステムにし
    て、 Ｘ個のストリームを割り振るためのストリーム・バッフ
    ァと、 それぞれがキャッシュ・ミスを表すＹ個のエントリを有
    するストリーム・フィルタであって、前記Ｘ及びＹは正
    の整数であり、前記Ｘ個のストリームの各々は前記Ｙ個
    のエントリのうちの少なくとも１つによって表されるも
    のと、 前記ストリームを表す前記Ｙ個のエントリのうちの少な
    くとも１つのすべてが前記ストリーム・フィルタから割
    振り解除されてしまうまで前記ストリーム・バッファに
    おいてストリームを維持するための手段と、 を含むシステム。
11. 【請求項１１】前記ストリームを表す前記Ｙ個のエント
    リのうちの少なくとも１つのすべてが前記ストリーム・
    フィルタから割振り解除された後、前記ストリーム・バ
    ッファにおいて新しいストリームを、前記新しいストリ
    ームに対応したデータのキャッシュ・ミスに応答して割
    り振るための手段を含むことを特徴とする請求項１０に
    記載のシステム。
12. 【請求項１２】前記ストリームに対応するキャッシュ・
    ミスが生じる時、前記ストリームを表す前記Ｙ個のエン
    トリの少なくとも１つのすべてが前記ストリーム・フィ
    ルタから割振り解除された後、前記ストリーム・バッフ
    ァにおけるストリームを再割振りするための手段を含む
    ことを特徴とする請求項１０に記載のシステム。
13. 【請求項１３】前記Ｙ個のエントリはＬＲＵに基づいて
    前記ストリーム・フィルタから割振り解除されることを
    特徴とする請求項１０に記載のシステム。
14. 【請求項１４】前記ストリームは前記新しいストリーム
    が前記ストリーム・バッファにおいて割り振られるまで
    前記ストリーム・バッファに残ることを特徴とする請求
    項１１に記載のシステム。
15. 【請求項１５】データ処理システムにおいてバスにより
    プロセッサに接続されたメイン・メモリから、前記プロ
    セッサに接続されたＬ１キャッシュにキャッシュ・ライ
    ンをプリフェッチするための方法にして、前記プリフェ
    ッチすることはストリーム・バッファ及びストリーム・
    フィルタの利用を増大し、前記ストリーム・バッファは
    アドレス・バッファ及びデータ・バッファを含み、前記
    ストリーム・バッファは１つ又は複数のアクティブ・ス
    トリームを保持し、前記ストリーム・フィルタは前記１
    つ又は複数のアクティブ・ストリームに対応した１つ又
    は複数のエントリを含むものにおいて、 一連のＬ１キャッシュ・ミスをモニタするステップと、 前記Ｌ１キャッシュ・ミスに応答してＬＲＵに基づき前
    記ストリーム・フィルタにおけるエントリを置換するス
    テップと、 前記１つ又は複数のアクティブ・ストリームに対応した
    前記１つ又は複数のエントリのすべてが前記置換するス
    テップによって置換されるまで、前記ストリーム・バッ
    ファにおける前記１つ又は複数のアクティブ・ストリー
    ムの１つを維持するステップと、 を含む方法。
16. 【請求項１６】前記１つ又は複数のアクティブ・ストリ
    ームの１つに対応した前記１つ又は複数のエントリのす
    べてが前記置換するステップによって置換された後、前
    記ストリーム・バッファにおける新しいアクティブ・ス
    トリームを、前記新しいアクティブ・ストリームに対応
    したデータのキャッシュ・ミスに応答して割り振るステ
    ップを含むことを特徴とする請求項１５に記載の方法。
17. 【請求項１７】前記１つ又は複数のアクティブ・ストリ
    ームの１つに対応したキャッシュ・ミスが生じた時、前
    記１つ又は複数のアクティブ・ストリームの１つに対応
    した前記１つ又は複数のエントリのすべてが前記置換す
    るステップによって置換された後、前記ストリーム・バ
    ッファにおける前記１つ又は複数のアクティブ・ストリ
    ームの１つを再割振りするステップを含むことを特徴と
    する請求項１５に記載の方法。
18. 【請求項１８】前記新しいアクティブ・ストリームが前
    記ストリーム・バッファにおいて割り振られるまで、前
    記１つ又は複数のアクティブ・ストリームの１つが前記
    ストリーム・バッファに残ることを特徴とする請求項１
    ６に記載の方法。