(57)【要約】データの取り出しに対するメモリ参照の平均待ち時間を減少するためにデータフェッチが使用される。プリエッチ処理は、典型的には未来のプロセッサデータ参照の予想に基づく。実施例において、第１メモリ回路（６１０）と、ストライド予測（６１１）テーブル（ＳＰＴ）と、キャッシュメモリ回路（６１２）とを設けるステップを有するデータ取り出しの方法が存在する。前記第１メモリ内のデータにアクセス（６１３）する命令が実行される。キャッシュミス（６１４）が検出される。キャッシュミスが検出される場合のみ、前記ＳＰＴがアクセス及び更新される（６１５）。この実施例のフィーチャは、ストリームバッファを前記キャッシュメモリ回路として使用することを含む。他のフィーチャは、ランダムアクセス・キャッシュメモリを前記キャッシュメモリ回路として使用することを含む。
2006516168.tif 000002
【特許請求の範囲】
【請求項１】
第１メモリ回路を設けるステップと、ストライド予測テーブルを設けるステップと、キャッシュメモリ回路を設けるステップと、前記第１メモリ内のデータにアクセスする命令を実行するステップと、キャッシュミスを検出するステップと、キャッシュミスが検出された場合のみに前記ストライド予測テーブルにアクセス及び更新するステップとを有するデータ取り出しの方法。
【請求項２】
前記キャッシュメモリ回路がストリームバッファである、請求項１に記載の方法。
【請求項３】
前記キャッシュメモリ回路が、ランダムアクセス・キャッシュメモリである、請求項１に記載の方法。
【請求項４】
前記キャッシュメモリ回路及び前記ストライド予測テーブルが、同じ物理メモリ空間内にある、請求項１に記載の方法。
【請求項５】
前記第１メモリが、前記命令を実行するプロセッサから離れた外部メモリ回路である、請求項１に記載の方法。
【請求項６】
前記キャッシュミスを検出するステップが、前記プロセッサにより実行される命令がメモリアクセス命令であるかどうかを決定するステップと、前記命令がメモリアクセス命令である場合に、前記メモリアクセス命令のメモリ位置におけるデータが前記キャッシュ内に存在するかどうかを決定するステップと、前記データが前記キャッシュ内に存在するものではない場合に、キャッシュミスを検出するステップとを含む、請求項１に記載の方法。
【請求項７】
前記キャッシュミスを検出するステップが、前記プロセッサにより実行されるべき命令がメモリアクセス命令であるかどうかを決定するステップと、前記命令がメモリアクセス命令である場合に、前記メモリアクセス命令のメモリ位置におけるデータが前記キャッシュ内に存在するかどうかを決定するステップと、前記データが前記キャッシュ内に存在するものではない場合に、キャッシュミスを検出するステップと、前記キャッシュミスが生じた場合のみに前記ストライド予測テーブルにアクセスし、更新するステップとを含む、請求項１に記載の方法。
【請求項８】
前記アクセス及び更新するステップが、前記ストライド予測テーブル内のエントリに対する不必要なアクセス及び更新を防止するフィルタリングするステップを設ける、請求項１に記載の方法。
【請求項９】
前記キャッシュメモリ回路が、前記命令を実行するプロセッサと一体になっている、請求項１に記載の方法。
【請求項１０】
前記ストライド予測テーブルがアドレスフィールドを有し、前記アドレスフィールドのサイズが、前記ストライド予測テーブルにインデックスをつけるために使用されるアドレス空間より小さい、請求項１に記載の方法。
【請求項１１】
ストライド予測テーブルと、前記ストライド予測テーブルと共に使用するフィルタ回路とを有する装置において、前記フィルタ回路が、前記ストライド予測テーブルがアクセス及び更新されるべきであるインスタンスを決定し、前記インスタンスが、キャッシュミスが検出される場合のみに生じる装置。
【請求項１２】
前記ストライド予測テーブルを記憶するメモリ回路を有する請求項１１に記載の装置。
【請求項１３】
前記メモリ回路内に存在するキャッシュメモリを有する請求項１２に記載の装置。
【請求項１４】
前記メモリ回路が、シングルポート型メモリ回路である、請求項１３に記載の装置。
【請求項１５】
前記メモリ回路が、ランダムアクセスメモリ回路である、請求項１３に記載の方法。
【請求項１６】
前記キャッシュメモリ回路が、ストリームバッファである、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データプリフェッチの分野に関し、特に、ハードウェア主導型（hardware directed）のメモリからのデータのプリフェッチの分野に関する。
【背景技術】
【０００２】
現在、プロセッサは、ＲＡＭメモリからデータを取り出す場合にプロセッサ・ストールサイクルが生じる典型的なＲＡＭより大幅に速い。このプロセッサ・ストールサイクルは、データアクセス動作が完了することを可能にする処理時間を増大させる。ＲＡＭメモリからのデータのプリフェッチの処理は、プロセッサ・ストールサイクルを減少させる試みで実行される。したがって、異なるメモリアクセス速度をサポートするキャッシュメモリの異なるレベルが、異なるプリフェッチデータを記憶するために使用される。アクセスされたデータが、前記キャッシュメモリ内にプリフェッチされたデータ内に存在するものではない場合に、プロセッサ・ストールサイクルの挿入により解決可能であるキャッシュミス状態が生じる。更に、前記プロセッサにより要求されるものではないが、前記キャッシュメモリにプリフェッチされるデータは、キャッシュ汚染、即ち非有用なプリフェッチデータに対して場所を空けるための有用なキャッシュデータの除去を起こす可能性がある。これは、前記プロセッサにより再び要求される置き換えられたデータから生じる不必要なキャッシュミスを起こす可能性がある。
【０００３】
データプリフェッチは、当業者にとって既知の技術であり、メモリからデータを取り出すためのメモリ参照の平均待ち時間を減少するために使用される。プリフェッチ処理は、典型的には未来のプロセッサデータ参照の予想に基づく。前記データ要素が前記プロセッサにより必要とされる前の、メモリ階層内の低いレベルから前記プロセッサによりより容易にアクセスされることができる前記メモリ階層内のより高いレベルへのデータ要素の移動は、前記プロセッサにより観測される平均データ取り出し待ち時間を減少する。結果として、プロセッサ性能は大幅に向上される。
【０００４】
完全にソフトウェアベースのプリフェッチ実装から完全にハードウェアベースのプリフェッチ実装までの範囲に及ぶ複数のプリフェッチアプローチが従来技術において開示されている。ソフトウェアベースのプリフェッチ及びハードウェアベースのプリフェッチの混合を使用するアプローチも既知である。Mehrotraに付与された米国特許番号5822790において、ハードウェア及びソフトウェアベースのプリフェッチにおいて使用する共有プリフェッチデータ記憶構造が開示される。不幸なことに、前記キャッシュメモリは、ストライド予測の目的で前記キャッシュメモリのデータ部分に対して行われた全てのデータ参照に対してアクセスされ、したがって、これらのアクセス動作により消費される時間を減少する又は取り除くことは有益である。
【０００５】
ストライド検出及びストライド予測に必要なＳＰＴアクセスは、問題を引き起こす。時間内の多すぎるアクセスは、プロセッサ・ストールサイクルを起こす可能性がある。しかしながら、前記問題は、前記ＳＰＴ構造をマルチポート化することにより対処されることができ、したがって、前記構造に対する複数の同時アクセスを可能にする。不幸なことに、マルチポート化は、前記構造に対する増大されたダイ領域（die area）を生じ、これはもちろん望ましくない。
【発明の開示】
【課題を解決するための手段】
【０００６】
本発明によると、ストライド予測テーブル（ＳＰＴ）と、前記ＳＰＴと共に使用されるフィルタ回路とを有する装置であって、前記フィルタ回路が、前記ＳＰＴがアクセス及び更新されるべきであるインスタンスを決定し、前記インスタンスが、キャッシュミスが検出される場合のみに生じる当該装置が提供される。
【０００７】
本発明によると、第１メモリ回路を設けるステップと、ストライド予測テーブル（ＳＰＴ）を設けるステップと、キャッシュメモリ回路を設けるステップと、前記第１メモリ内のデータにアクセスする命令を実行するステップと、キャッシュミスを検出するステップと、キャッシュミスが検出される場合のみに前記ＳＰＴにアクセスし、更新するステップとを有するデータ取り出し方法が提供される。
【０００８】
本発明は、ここで図面を参照して記載される。
【発明を実施するための最良の形態】
【０００９】
本発明の実施例により、ストリームバッファアプローチからの技術とＳＰＴベースのアプローチからの技術とを組み合わせるプリフェッチアプローチが提案される。
【００１０】
ハードウェアベースのプリフェッチに対する既存のアプローチは、以下の従来技術を含む。Jouppi et al.に付与された米国特許番号5261066（‘066）の従来技術は、ストリームバッファの概念を開示している。２つの構造が前述の特許において提案され、犠牲になるキャッシュラインを保持し、キャッシュ競合に対処するために使用される、犠牲キャッシュとしても知られる、小さな完全アソシエイティブ・キャッシュ（fully associative cache）は、低アソシエイティブ（low associative）又はダイレクト・マップド（direct mapped）キャッシュ設計においてミスをする。しかしながら、この小さな完全アソシエイティブ・キャッシュは、プリフェッチに関係しない。他の提案された構造はストリームバッファであり、これはプリフェッチに関係する。この構造は、典型的には、容量及び強制キャッシュミスに対処するために使用される。図１ａにおいて、従来技術のストリームバッファ・アーキテクチャが図示される。
【００１１】
ストリームバッファはプリフェッチに関係し、これらは、メモリからのデータ要素のプリフェッチされたシーケンシャルストリームを記憶するために使用される。アプリケーションストリームの実行において、メモリからラインを取り出すために、プロセッサ１００は、初めに、前記ラインがキャッシュメモリ１０４内に存在するキャッシュラインであるかどうかを決定するためにキャッシュメモリ１０４を確認する。前記ラインが前記キャッシュメモリ内に存在するものではない場合に、キャッシュミスが生じ、ストリームバッファ１０１が割り当てられる。ストリームバッファ・コントローラは、前記キャッシュミスが生じたキャッシュラインの後に続いて、前記割り当てられたストリームバッファのキャッシュライン容量が満杯になるまで、自発的にメインメモリ１０２からのシーケンシャルキャッシュラインのプリフェッチを開始する。したがって、未来のキャッシュミスは随意でストリームバッファ１０１に存在するプリフェッチされたキャッシュラインにより補修されるので、前記ストリームバッファは、前記プロセッサに増大された処理効率をもたらす。前記プリフェッチされたキャッシュラインは、この場合、好ましくは、ストリームバッファ１０１からキャッシュメモリ１０４にコピーされる。これは、有利には、前記ストリームバッファの記憶容量を解放し、新しいプリフェッチされたキャッシュラインを受信する際に前記ストリームバッファ内のこのメモリ位置を使用することができるようにする。ストリームバッファを使用すると、割り当てられたストリームバッファの量は、特定の時間フレーム内の実行中に存在するデータストリームの量をサポートすることができるために決定される。
【００１２】
典型的には、ストリーム検出は、キャッシュラインミス情報に基づき、複数のストリームバッファの場合には、各単一のストリームバッファは、アプリケーションストリームを検出する論理回路と、前記アプリケーションストリームに関連付けられたプリフェッチされたキャッシュラインデータを記憶する記憶回路との両方を含む。更に、プリフェッチされたデータは、前記キャッシュメモリに直接的に記憶されるのではなく、前記ストリームバッファに記憶される。
【００１３】
少なくともデータストリームと同じだけ多くのストリームバッファが存在する場合、前記ストリームバッファは効率的に機能する。アプリケーションストリームの量が、割り当てられたストリームバッファの量より大きい場合、異なるアプリケーションストリームに対するストリームバッファの再割り当ては、不幸なことに、このアプローチにより実現された潜在的な性能利益を取り消す可能性がある。したがって、ストリームバッファプリフェッチのハードウェア実装は、異なるソフトウェアアプリケーション及びストリームに対するサポートが望ましい場合には難しい。このストリームバッファアプローチは、異なるストライドを用いるプリフェッチをサポートするように拡張する。前記拡張されたアプローチは、もはやシーケンシャル・キャッシュライン・ミス・パターンに制限されず、一定のストライドで分離された連続したリファレンスを持つキャッシュライン・ミス・パターンをサポートする。
【００１４】
Kessler et al.に付与された従来技術の米国特許番号5761706は、前記ストリームバッファに加えてフィルタを設けることにより前記‘066特許に開示されたストリームバッファ構造を基づく。従来技術の図１ｂは、ストリームバッファを含む典型的なシングルプロセッサシステムの論理構成を図示する。このシステムは、フィルタリングされたストリームバッファモジュール１０３及びメインメモリ１０２に接続されたプロセッサ１００を含む。フィルタリングされたストリームバッファモジュール１０３は、メインメモリ１０２からキャッシュブロックをプリフェッチし、オンチップキャッシュ及びメインメモリ１０２のみを有するシステムより速いオンチップ・ミスの補修をもたらす。フィルタリングの処理は、全てのメモリアクセスのサブセットを選択するように定められ、これは、ストリームバッファ１０１の使用からより高い可能性で利益を得ることになり、このサブセット内のアクセスに対してのみストリームバッファ１０１を割り当てる。各アプリケーションストリームに対し、別個のストリームバッファ１０１が、前記従来技術の‘066特許のように割り当てられる。更に、Kessler et al.は、単位ストライド（unit stride）プリフェッチ及び非単位ストライドプリフェッチの両方を開示しているが、‘066は単位ストライドプリフェッチに制限される。
【００１５】
他の一般的な従来技術のプリフェッチに対するアプローチは、従来技術の図２に示されるようなストライド予測テーブル（ＳＰＴ）２００により、このＳＰＴ２００は、以下の刊行物、即ちここに参照により組み込まれるJ. W. Fu、J. H. Patel及びB. L. Janssens、“Stride Directed Prefetching in Scalar Processors”、Proceedings of the 25th
Annual International Symposium on Microarchitecture（Portland, OR）、pp. 102-110、１９９２年１２月に開示されるように、アプリケーションストリームを予測するために使用される。
【００１６】
ＳＰＴ動作フローチャートは図３に示される。ＳＰＴアプローチにおいて、アプリケーションストリーム検出は、典型的には、プログラムカウンタ（ＰＣ）並びにロード命令及び記憶命令のデータ参照アドレスに基づき、前記ＰＣのアドレスでインデックスを付けられたルックアップテーブルを使用する。更に、複数のストリームは、ＳＰＴ２００内の異なるエントリにインデックスを付ける限り、ＳＰＴ２００によりサポートされることができる。前記ＳＰＴアプローチを使用すると、プリフェッチされたデータは、キャッシュメモリに直接的に記憶され、ＳＰＴ２００には記憶されない。
【００１７】
ＳＰＴ２００は、アプリケーションストリームを実行する場合に、キャッシュメモリに対してプロセッサにより発行されるデータ参照に対するロード及び記憶命令のパターンを記録する。このアプローチは、これらの命令のＰＣを使用して、ＳＰＴ２００にインデックスを付ける３３０。ＳＰＴ２００内のSPTEntry.pcフィールド２１０は、前記ＳＰＴ内のエントリにインデックスを付けるのに使用された命令のＰＣに対して記憶された値を持ち、データ参照アドレスは、SPTEntry.addressフィールド２１１に記憶され、随意に、ストライドサイズがSPTEntry.strideフィールド２１２に記憶され、カウンタ値がSPTEntry.counterフィールド２１３に記憶される。ＰＣフィールド２１０は、ＳＰＴ２００にインデックスを付ける前記アプリケーションストリーム内の命令のＰＣ値を照合３００するタグフィールドとして使用される。ＳＰＴ２００は、複数のこれらのエントリからなる。前記ＳＰＴが８ビットアドレスでインデックスを付けられる場合、典型的には２５６のこれらのエントリが存在する。
【００１８】
前記データ参照アドレスは、典型的には、SPTEntry.pcフィールド２１０に記憶された値のアドレスに位置する命令に対してデータ参照アクセスパターンを決定するために使用される。参照によりここに組み込まれるT. F. Chen及びJ. L. Baerによる刊行物、“Effective Hardware-Based Data Prefetching for High-Performance Processors”、IEEE Transactions on Computer、vol. 44、pp. 609-623、１９９５年５月に開示されるように、ストライド型アプリケーションストリームが検出される場合、オプションのSPTEntry.strideフィールド２１２及びSPTEntry.counterフィールド２１３は、前記ＳＰＴアプローチが増大された確実性で動作することを可能にする。
【００１９】
もちろん、このＳＰＴベースのアプローチも制限を持つ。即ち、典型的なプロセッサは、シングルプロセッサ・クロックサイクルで実行される複数の並列ロード及び記憶命令をサポートする。結果として、前記ＳＰＴベースのアプローチは、クロックサイクル毎に複数のＳＰＴ管理タスクをサポートする。図３に示されるフローチャートによると、このような管理タスクは、典型的にはＳＰＴ２００に対する２つのアクセスを実行する。第１アクセスは、ＳＰＴエントリフィールドをフェッチする３０１のに使用され、他のアクセス３０２は、ＳＰＴ２００内のエントリを更新するために使用される。ＳＰＴ２００は、前記アプリケーションストリームに対して前記ＰＣの下位の８ビットを使用してインデックスを付けられ、前記ＰＣの下位の８ビットは、SPTEntry.pc２１０と比較され３００、照合する３０１か否３０２かを決定する。
【００２０】
ＳＰＴエントリフィールドをフェッチ中に３０１、ストライドは、現在のアドレス及びSPTEntry.address２１１から決定され３１０、この場合、１ブロックのメモリが、前記現在のアドレスに前記ストライドを加えた位置にあるアドレスにおけるメインメモリからプリフェッチされる３１１。この後、SPTEntry.address２１１は、前記現在のアドレスで置き換えられる３１２。ＳＰＴ２００内のエントリ３０２を更新する処理において、SPTEntry.pc２１０は、現在のＰＣで更新され３２０、SPTEntry.address２１１は、前記現在のアドレスで更新される３２１。
【００２１】
図４に示されるフローチャートによると、SPTEntry.counterフィールド及びSPTEntry.strideフィールドが、ＳＰＴ２００内で更にアクセスされ、このような管理タスクは、典型的には前記ＳＰＴに対する２つ以上のアクセスを使用する。第１アクセスは、ＳＰＴエントリフィールド４０１をフェッチするために使用され、他のアクセス４０２は、ＳＰＴ２００内のエントリを更新するために使用される。ＳＰＴ２００は、前記アプリケーションストリームに対して前記ＰＣの下位の８ビットを使用してインデックスを付けられ、前記ＰＣの下位の８ビットは、SPTEntry.pc２１０と比較されて４００、これらが照合する４０１か否４０２か決定する。照合が見つけられる場合、前記ストライドが計算され４１０、このストライドは、前記現在のアドレスからSPTEntry.address２１１を減算した位置に等しい。次に、SPTEntry.stride２１２は、前記ストライドと比較され、これらが等しいかどうか確認し、前記SPTEntry.counterは、これが３に等しいかどうか確認するために比較される４１１。前記比較の結果が満たされる場合４１２、前記現在のアドレスに前記ストライドを加えた位置にあるメモリブロックは、メインメモリからプリフェッチされる。そうではなく、前記比較の結果が満たされない場合４１３、前記SPTEntry.addressは、現在のアドレスにセットされ４１５、前記SPTEntry.strideは、前記ストライドにセットされる４１６。次に、前記SPTEntry.counterが３より小さいかどうかが決定され４１７、３より小さい場合４１８、前記SPTEntry.counterはインクリメントされる４１９。前記ＳＰＴにおけるエントリの更新４０２に関して、前記SPTEntry.pcは現在のＰＣに等しくセットされ４２０、前記SPTEntry.addressは現在のアドレスにセットされ４２１、前記SPTEntry.counterは１にセットされる４２２。
【００２２】
結果として、並列に実行される３つの同時のロード及び記憶命令に対して、図３及び図４に詳しく示される前記管理タスクが、好ましくは実行される。したがって、ＳＰＴ２００は、好ましくは、シングルプロセッサ・クロックサイクル内に３×２＝６アクセスをサポートすることができるように設計される。これは、前記ＳＰＴが、典型的には、ＳＰＴ２００を往復するデータを記憶及び提供することを容易にするために前記プロセッサのクロックレートより高いクロックレートで動作することを意味する。もちろん、前記ＳＰＴは、マルチポート化又はコピーされることができるが、不幸なことに、これはより大きなダイ領域を生じ、これは好ましくない。
【００２３】
もちろん、前記ＳＰＴにインデックスを付ける際に使用するために、前記ＰＣの下位の８ビットを使用することは可能であるが、命令セットアーキテクチャ（ＩＳＡ）に基づき、プロセッサの型に基づく代替例が存在する。例えば、MIPS ISAに対し、全ての命令は４バイトのサイズであり、結果として、前記ＰＣは常に４の倍数で変更され、ＰＣビット１及び０は常に‘０’である。したがって、この場合、９から２のＰＣビット、ＰＣ[９：２]が使用される。同様に、ＶＬＩＷマシンに対しては、命令サイズはより大きくなる傾向にあり、２ないし２８バイトのサイズを持つ。したがって、７から０のビットではんく、より大きなビットの幾つかを使用することが好ましいかもしれない。前記ＳＰＴにインデックスを付けるために使用されるビットは、必ずしも前記ＰＣの最下位の８ビットでなくてもよく、他のビットの組み合わせが、より好ましいかもしれない。
【００２４】
加えて、ストリーム検出は、命令データ参照アドレスに基づく。プリフェッチされるべきデータが依然としてキャッシュメモリ内に無いことを確認するために、プリフェッチ・キャッシュライン・タグ・ルックアップが好ましくは使用され、前記キャッシュメモリ内に既に存在するキャッシュラインのプリフェッチを防止する。キャッシュメモリ内に既に存在するキャッシュラインのプリフェッチは、臨界メモリ帯域幅を不必要に使用する結果となる。プリフェッチされたデータは、典型的にはキャッシュメモリに直接的に記憶される。したがって、小さなキャッシュメモリサイズに対して、これは、プリフェッチされたキャッシュラインに対して場所を空けるために前記キャッシュメモリから有用なキャッシュラインを除去する結果となる。これは、潜在的に不必要なプリフェッチされたキャッシュラインが既存のキャッシュラインを置き換えるキャッシュ汚染を引き起こし、したがってキャッシュの効率を低下する。もちろん、キャッシュ汚染問題は、前記キャッシュメモリにより実現される性能利益を低下する。
【００２５】
キャッシュ汚染の克服法は、ここに参照により組み込まれる、D. F. Zucker et al.による刊行物、“Hardware
and Software Cache Prefetching Techniques for MPEG Benchmarks”、IEEE
Transactions on Circuits and Systems for Video Technology、vol.
10、pp. 782-796、２０００年８月において提案されている。この刊行物において、直列ストリーム（従来技術の図５ａ）キャッシュ及び並列ストリーム（従来技術の図５ｂ）キャッシュが提案されている。これらのアプローチは、プリフェッチされたキャッシュラインを保持する小さな完全アソシエイティブ・キャッシュ構造を加える。
【００２６】
図５ａに示されるような直列ストリームキャッシュ・アーキテクチャにおいて、ストリームキャッシュ５０３は、キャッシュメモリ５０１と直列に接続される。直列ストリームキャッシュ５０３は、キャッシュメモリ５０１がミスをした後に検索され、プロセッサ５００により望まれるデータでキャッシュメモリ５０１を満たすために使用される。データがキャッシュメモリ５０１においてミスされ、前記データがストリームキャッシュ５０３内に無い場合、前記データは、メインメモリ５０４から直接的にキャッシュメモリ５０１に取り出される。新しいデータは、ＳＰＴ５０２ヒットが生じる場合のみに前記ストリームキャッシュ内にフェッチされる。
【００２７】
図５ｂに示されるような並列ストリームキャッシュは、ストリームキャッシュ５０３の位置が、キャッシュメモリ５０１のリフィル経路からキャッシュメモリ５０１と並列な位置に移動されることを除き、前記直列ストリームキャッシュと同様である。プリフェッチされたデータは、ストリームキャッシュ５０３に運ばれるが、キャッシュメモリ５０１にコピーされない。したがって、キャッシュアクセスは、キャッシュメモリ５０１及びストリームキャッシュ５０３の両方を並列に検索する。キャッシュメモリ５０１又はストリームキャッシュ５０３の何れからも満たされることができないキャッシュミスが起こると、前記データは、メインメモリ５０４から直接的に前記キャッシュメモリにフェッチされ、結果としてプロセッサ・ストールサイクルを生じる。
【００２８】
ストリームキャッシュ記憶容量は、アプリケーション内の異なるアプリケーションストリーム間で共有される。結果として、これらのストリームキャッシュは、前記ストリームバッファアプローチに対して記載されたような欠点を被らない。このアプローチにおいて、アプリケーションストリーム検出は、前記ＳＰＴにより可能にされ、キャッシュラインデータの記憶に対する記憶容量は、ストリームキャッシュ５０３により与えられる。
【００２９】
前記ストリームバッファアプローチからの技術と前記ＳＰＴベースのアプローチからの技術とを組み合わせるプリフェッチ・アーキテクチャのハードウェア実装は、図６に示される。このアーキテクチャにおいて、プロセッサ６０１は、フィルタ回路６０２及びデータキャッシュメモリ６０３に結合される。ストライド予測テーブル６０４は、フィルタ回路６０２によるアクセスに対して設けられる。メインメモリ６０５と前記データキャッシュとの間に、ストリームキャッシュ６０６が設けられる。本実施例において、ＳＰＴ６０４及びデータキャッシュ６０３は、共有メモリ回路６０７内に設けられる。
【００３０】
図６ａに示されるアーキテクチャの使用中に、プロセッサ６０１は、アプリケーションストリームを実行する。前記ＳＰＴは、図６ｂに図示されるステップによりアクセスされ、ここで最初に第１メモリ回路が設けられ６１０、ＳＰＴが設けられ６１１、キャッシュメモリ回路が設けられる６１２。前記アプリケーションストリームは、典型的には、ロード及び記憶命令の形式の複数のメモリアクセス命令を含む。ロード命令が前記プロセッサにより処理される６１３場合、データは、キャッシュラインミスがデータキャッシュ６０３において生じたかどうかに基づいてキャッシュメモリ６０３又はメインメモリ６０５の何れかから取り出される。キャッシュラインミスが前記データキャッシュにおいて生じる６１４場合、ＳＰＴ６０４は、好ましくは、メインメモリ６０５のアクセスの前にストライドを決定するためにアクセス及び更新される６１５。
【００３１】
全てのロード及び記憶命令に対してではなく、キャッシュラインミスが生じる６１４場合にＳＰＴアクセス動作を制限することは、図６ａに示されるシステムの性能の大幅な変更無しで前記ＳＰＴ及び前記データキャッシュの両方の効率的な実装を可能にする。好ましくは、プリフェッチされたキャッシュラインは、ストリームキャッシュ６０６の形式のストリームバッファのような一時バッファに記憶されるか、又は代替的にデータキャッシュメモリ６０３に直接的に記憶される。
【００３２】
前記ＳＰＴを使用してキャッシュラインミス情報に基づくストリーム検出を実行することにより、以下の利点が実現される。キャッシュミスは、典型的には頻繁ではなく、結果としてシングルポート型ＳＲＡＭメモリがＳＰＴ６０４の実装に十分であるので、ＳＰＴ６０４の単純な実装が可能である。これは、結果としてより小さなチップ面積をもたらし、全体的な電力消費を減少する。前記ＳＰＴは、キャッシュラインミス情報でインデックスを付けられるので、前記ＳＰＴエントリのアドレスフィールド及びストライドフィールドは、好ましくはサイズが減少される。３２ビットのアドレス空間及び６４バイトのキャッシュラインサイズに対し、前記アドレスフィールドのサイズは、より慣習的な３２ビットではなく、随意に２６ビットまで減少される。同様に、ＳＰＴ内の前記ストライドフィールド２１２は、データ参照ストライドではなく、キャッシュラインストライドを表し、したがって随意にサイズが減少される。更に、プリフェッチスキームがより積極的であるべき場合に、プリフェッチ・カウンタ値を３の代わりに２にセットすることが好ましい。
【００３３】
前記ＳＰＴ及び前記キャッシュメモリに対する共有記憶構造の実装は、有利には、より高いダイ領域効率を可能にする。更に、ストリームバッファが異なるデータ処理レートを持ち、結果として複数のストリームバッファに対する共有記憶容量を持つことが、有利には、異なるストリームバッファデータ処理レートの改良された操作を可能にすることは、当業者にとって既知である。
【００３４】
有利には、プリフェッチをデータキャッシュラインミス情報に制限することにより、前記ＳＰＴ内のエントリに対する不必要なアクセス及び更新を防止する効率的なフィルタが実現される。ミス情報の場合のみに前記ＳＰＴにアクセスすることは、典型的には、前記ＳＰＴ内のより少ないエントリを必要とし、更に性能を犠牲にしない。
【００３５】
図７ａにおいて、第２アレイｂ[ｉ]７０２から第１アレイａ[ｉ]７０１にＮ個のエントリをコピーするコピー機能を実現するループを含む第１擬似コードＣプログラムが示される。前記ループのＮ回の実行中に、第２アレイ７０２の全てのエントリは、第１アレイ７０１にコピーされる。図７ｂにおいて、図７ａに示されるものと同じコピー機能を実現する第２擬似コードＣプログラムが示される。前記第１プログラムは、２つのアプリケーションストリームを持ち、したがって２つのＳＰＴエントリが、本発明の実施例及び従来技術のＳＰＴベースのプリフェッチアプローチと併せて使用される。前記第２プログラムにおいて、前記ループは２回展開され（unrolled）、即ち前記ループはＮ／２回実行され、１回毎に完全に巻かれたループの必要な動作を２回実行し、したがって、２つのコピー命令は、前記ループの各パス内で実行される。両方のプログラムが同じ２つのアプリケーションストリームを持ち、２つのＳＰＴエントリが本発明の実施例により使用される。不幸なことに、前記従来技術のＳＰＴベースのプリフェッチアプローチで実行される場合には、展開されたループに対して４つのＳＰＴエントリが必要とされる。これは、もちろん、キャッシュラインが、２の倍数の３２ビット整数サイズのデータ要素を保持すると仮定している。ループ展開は、ループ制御オーバーヘッドを減少するためにしばしば使用される技術であり、前記ループ展開は、実行されるループパス毎に前記ＳＰＴに対する２より多いアクセスを必要とすることによりＳＰＴアクセスを難しくする。
【００３６】
図７ｃにおいて、擬似コードＣプログラムは、３２ビット整数合計変数７０３に基づいて第２アレイｂ[ｉ]７０２の要素を第１アレイａ[ｉ]７０１に追加する。不幸なことに、前記従来技術のＳＰＴベースのプリフェッチアプローチを使用すると、データアクセス動作の規則性は、入力ストリームｂ[ｉ]のアクセスパターンにおいて検出されることができない。したがって、前記データキャッシュ内のラインがｂ[ｉ]に関係する複数のストリームデータ要素を保持する場合、性能の増大は、コピー機能が本発明の実施例によって実行され、前記ループにおける条件ａ[ｉ]≧０が、少なくともキャッシュライン毎に満たされる場合に実現される。
【００３７】
実験的に、本発明をテストするために実装される本発明の実施例が非常に超長命令語（ＶＬＩＷ）プロセッサに対して使用される場合に、プロセッサ・クロックサイクル毎に２つのデータ参照まで実行されることができ、前記データキャッシュにおいてミスされたデータ参照の量は、１００プロセッサ・クロックサイクルに１回前後であることが発見された。更に、本発明の実施例によるＳＰＴ実装は、製造される場合に小さなダイ領域を占める。
【００３８】
多くの他の実施例が、本発明の精神及び範囲から外れることなく考えられることができる。
【図面の簡単な説明】
【００３９】
【図１ａ】従来技術のストリームバッファ・アーキテクチャを図示する。
【図１ｂ】ストリームバッファを含む典型的なシングルプロセッサシステムの従来技術の論理構成を図示する。
【図２】複数のエントリからなる従来技術のストライド予測テーブル（ＳＰＴ）を図示する。
【図３】管理タスクを有する従来技術のＳＰＴアクセスフローチャートを図示する。
【図４】管理タスクを有する、より詳細な従来技術のＳＰＴアクセスフローチャートを図示する。
【図５ａ】従来技術の直列ストリーム・キャッシュメモリを図示する。
【図５ｂ】従来技術の並列ストリーム・キャッシュメモリを図示する。
【図６ａ】本発明の実施例と共に使用するアーキテクチャを図示する。
【図６ｂ】本発明の実施例を実行する際に使用する方法ステップを図示する。
【図７ａ】Ｎ個のエントリをコピーするコピー機能を実現するループを含む第１擬似コードＣプログラムを図示する。
【図７ｂ】図７ａに示されるものと同じコピー機能を実現する第２擬似コードＣプログラムを図示する。
【図７ｃ】第１アレイから第２アレイに要素を加える擬似コードＣプログラムを図示する。
2006516168.tif 000003
2006516168.tif 000004
【図２】
2006516168.tif 000005
【図４】
2006516168.tif 000006
2006516168.tif 000007
2006516168.tif 000008
2006516168.tif 000009
2006516168.tif 000010