JP5298826B2 - キャッシュメモリ及びプリフェッチ方法 - Google Patents

Description

本発明は、プロセッサ及び主記憶装置に接続されるキャッシュメモリに関し、特に、空間的局所性を動的に検出するキャッシュメモリ、及びそのプリフェッチ方法に関する。

従来、中央演算処理装置において、プリフェッチは主記憶装置（メインメモリ）とプロセッサの演算処理部との速度差を生めるために利用されている。

たとえば、特許文献１、特許文献２には、プロセッサの実行するループ構造を検出して、プリフェッチ情報を生成する装置が記載されている。ループを検出してプリフェッチ要求を生成することで実効性能を向上させるものである。
しかし、これらの手法には次のような問題点があった。まず、非常に大きなループ検出装置が必要となり、性能の向上幅に見合わないハードウェア量を要求されていた。また、これらの手法は、応用範囲が限定されていた。例えば、これらの手法ではストライドアクセスしかサポートされないため、Ｃ言語で多用されるスタック型のメモリ構成などではその効果を十分に発揮できなかった。

また、ハードウェアプリフェッチのプリフェッチ幅は装置によって静的に定められ、動的に適切なプリフェッチ幅に変更する機能を持たない、あるいは、精度の低い予測によりプリフェッチ幅を決定していた。このため、プログラムの挙動に応じたプリフェッチ幅の設定を実現することが困難であった。

さらには、不適切なプリフェッチ幅が設定された場合には、プログラムの実効性能が低下するという問題点があった。
特開２００５−２４２５２７号公報 特開２００２−２９７３７９号公報

本発明は、このような事情に鑑みてなされたものであり、動作状況に応じて、プリフェッチ幅を動的に変更するキャッシュメモリ及びプリフェッチ方法を提供することを目的とする。

本発明に係るキャッシュメモリの一態様は、プロセッサ及び主記憶装置に接続され、前記主記憶装置が保存するデータのコピーをライン単位に保持するデータアレイと、前記主記憶装置からデータを読み出し、前記データのコピーを前記データアレイの各ラインに書き込むメモリ制御手段と、各ラインに保持されるデータのコピーを管理する管理情報と、各ラインに保持されたデータのコピーの使用状況を示す使用情報とを保持する制御情報メモリと、前記プロセッサからの要求に応じて、データのコピーが前記データアレイに保持されているかを前記管理情報に基づいて判断し、保持されている場合、前記データアレイからデータを読み出し、保持されていない場合、前記主記憶装置からデータを読み出すことを前記メモリ制御手段に指示するキャッシュ制御手段と、前記使用情報に基づいて、前記メモリ制御手段がプリフェッチするプリフェッチライン数を決定するプリフェッチ制御手段と、を備え、前記メモリ制御手段は、前記キャッシュ制御手段からの指示に応じて前記主記憶装置からデータを読み出すときに、前記プリフェッチライン数に従って、プリフェッチを行う。

また、本発明に係るキャッシュメモリのプリフェッチ方法の一態様は、プロセッサ及び主記憶装置に接続されるキャッシュメモリのプリフェッチ方法であって、前記プロセッサからの要求に応じて、前記主記憶装置からデータを読み出すとともにプリフェッチを行い、読み出したデータのコピーとプリフェッチしたデータのコピーとデータアレイの各ラインに書き込み、前記プリフェッチを用いて書き込まれたラインが保持するデータの使用状況を監視し、前記使用状況に基づいて、プリフェッチするライン数を決定する。

本発明によれば、動作状況に応じて、プリフェッチ幅を動的に変更するキャッシュメモリ及びプリフェッチ方法を提供することが可能となる。

以下、本発明の実施形態について、図面を参照しながら説明する。説明の明確化のため、以下の記載及び図面は、適宜、省略、及び簡略化がなされている。各図面において同一の構成または機能を有する構成要素および相当部分には、同一の符号を付し、その説明は省略する。

本発明のキャッシュメモリが実現するプリフェッチ方式及びその方法は、プリフェッチしたラインが保持するデータの使用状況を監視し、使用状況に応じて、プリフェッチするライン数を動的に変化させる。すなわち、動作中のシステムに利用環境における、主記憶装置のデータの空間的／時間的局所性の程度を、プリフェッチしたデータの利用状況を用いて推定し、推定結果に基づいてプリフェッチするデータ量を決定するプリフェッチ方式である。以下、各実施形態において詳細に説明する。

（実施形態１）
図１は、本発明の実施形態１に係るキャッシュメモリの構成例を示すブロック図である。図１を参照すると、本発明のキャッシュメモリ１は、プロセッサ２、主記憶装置（メインメモリ）３に接続されている。キャッシュメモリ１の内部には、メモリコントローラ（メモリ制御手段）１０、キャッシュコントローラ（キャッシュ制御手段）１１、プリフェッチ制御部（プリフェッチ制御手段）１２、制御情報メモリ１３、及びデータアレイ１４を含んで構成される。

キャッシュコントローラ１１は、プロセッサ２からメモリアクセス要求を受け取り、キャッシュメモリにデータがあるかどうかをチェックする。具体的には、キャッシュコントローラ１１は、制御情報メモリ１３を参照し、メモリアクセス要求が要求するデータのコピーがデータアレイ１４に保持されているかチェックする。キャッシュヒットした場合、データアレイ１４からデータを読み出しプロセッサにリプライとして返す。キャッシュミスした場合、メモリコントローラ１０に対して要求されたデータを主記憶装置３から読み出すように指示する（読み出し要求）。このとき、メモリアクセス要求が要求しているアドレス（リクエストのアドレス）を通知する。

メモリコントローラ１０は、キャッシュコントローラ１１から主記憶装置３の読み出し要求が受けた際に、そのリクエストのアドレスで主記憶装置３に対してアクセスを行う。その後、プリフェッチ動作を行う。具体的には、まず、プリフェッチ制御部１２からプリフェッチ幅（プリフェッチ幅については、後述する）を取得する。続いて、プリフェッチ幅に従ってプリフェッチのメモリアクセスを実施する。
メモリコントローラ１０は、主記憶装置３へアクセスして読み出したデータをデータアレイ１４に書き込む。データの書き込みが終了すると制御情報メモリ１３に対して、アクセスした主記憶装置３の情報を書き込む。プリフェッチで読み出したデータに関しても制御情報メモリ１３へ情報を書き込む。制御情報メモリ１３へ書き込むデータについては、制御情報メモリ１３の説明で詳述する。

データアレイ１４は、キャッシュメモリに格納されている主記憶装置３のデータのコピー（以下、「コピーデータ」ともいう）を保持するＲＡＭ（Random Access Memory）である。データアレイ１４は、コピーデータをライン（キャッシュライン、ブロック）という単位を用いて保持する。各ラインを管理する情報が制御情報メモリ１３に保持される。データアレイ１４は通常のキャッシュメモリでも利用されている機能と同様であるため詳細な説明を省略する。

制御情報メモリ１３は、有効ビット１３１、タグアドレス１３２、ＬＲＵ（Least Recently Used）情報１３３、プリフェッチビット（プリフェッチ情報）１３４の４種類の情報を格納する。制御情報メモリ１３は、これら４種類の情報を、データアレイ１４の各ラインに対応させて格納する。また、４種類の情報のうち、有効ビット１３１とタグアドレス１３２とを管理情報、ＬＲＵ情報１３３とプリフェッチビットとを使用情報ということもある。管理情報は、データアレイ１４の各ラインに保持されるデータのコピーを管理する情報であり、使用情報は、各ラインに保持されたデータのコピーの使用状況を示す情報である。また、制御情報メモリ１３は、上述した４種類以外の情報を含んでいてもよい。
有効ビット１３１は、対応するラインが有効であるか否かを示す。タグアドレス１３２は、対応するラインに格納されているデータのコピーの主記憶装置３上のアドレス（もしくはアドレスを導く情報）を保持する。有効ビット１３１、タグアドレス１３２に関しては通常のキャッシュメモリと同様であるため詳しい説明を省略する。

ＬＲＵ情報１３３はキャッシュメモリの各ラインへのアクセスの最も古かったものを表す整数値である。例えば、Ｎウェイのセットアソシアティブメモリでは０、１、２、・・・、Ｎ−１の値をとる。ＬＲＵ情報は、最近アクセスされたラインが最小の値となる。キャッシュミスが発生した際には、ＬＲＵ情報の値が最も大きいラインを置き換え対象とする。
ＬＲＵ情報は、キャッシュコントローラ１１がデータアレイにアクセスしたときに、アクセスしたラインに対応するＬＲＵ情報が更新される。また、メモリコントローラ１０がデータアレイを置き換えたときに、置き換えたラインに対応するＬＲＵ情報が更新される。

プリフェッチビット１３４は、プリフェッチによってフィルされたキャッシュラインであることを示すビットである。
プリフェッチビット１３４は、プリフェッチ動作に応じて、設定される。ここでは、１（ＯＮ）に設定されることを前提とする。具体的には、メモリコントローラ１０が、コピーデータを書き込んだラインに対応するプリフェッチビット１３４を１に設定する。
また、プリフェッチビット１３４は、対応するラインがアクセスされたときにクリア（ゼロクリア、ＯＦＦ）される。具体的には、キャッシュコントローラ１１が、メモリアクセス要求に応じて、アクセスしたラインに対応するプリフェッチビット１３４をクリアする。このとき、キャッシュコントローラ１１は、アクセスされたラインに対応するＬＲＵ情報１３３をプリフェッチ制御部１２に引き渡す。プリフェッチ制御部１２ではこの情報を元にプリフェッチ幅の決定を行うためのプリフェッチ成功失敗カウンタ１２１を更新する。

プリフェッチ制御部１２は、プリフェッチされたラインの使用状況に基づいて、プリフェッチするライン数（プリフェッチ幅）を算出する。プリフェッチ制御部１２は、プリフェッチ幅の決定をするためのプリフェッチ成功失敗カウンタ１２１（以下、「カウンタ１２１」ともいう）を有する。プリフェッチ成功失敗カウンタ１２１は、プリフェッチされたラインの使用状況を数値化して示す。プリフェッチ制御部１２は、プリフェッチ成功失敗カウンタ１２１の値によってプリフェッチ幅（プリフェッチライン数）を決定する。カウンタの更新アルゴリズムに関しては後述する。決定したプリフェッチ幅は、前述のようにメモリコントローラ１０から主記憶装置３へのアクセス要求の際に利用される。

プリフェッチ成功失敗カウンタ１２１は、１６ビット程度の飽和カウンタで構成する。プリフェッチ成功失敗カウンタ１２１の情報は符号なし整数として扱う。プリフェッチ成功失敗カウンタ１２１の更新アルゴリズムは以下のとおりである。

１．プリフェッチ成功失敗カウンタ１２１を更新するアルゴリズム
１−１． プリフェッチ成功失敗カウンタ１２１は、プリフェッチしたラインがアクセスされた場合に更新される。具体的には、プリフェッチ成功失敗カウンタ１２１は、キャッシュメモリアクセスが発生した際に、制御情報メモリ１３で読み出されたラインのプリフェッチビット１３４が１であった場合に更新される。あるいは、キャッシュメモリの置き換え対象となったラインのプリフェッチビット１３４が１であった場合に更新される。

１−２． 更新時に、そのメモリアクセス（キャッシュリプレース）について、成功失敗度数を計算する。ここでは、Ｎウェイのセットアソシアティブ方式のキャッシュメモリを一例として説明する。Ｎウェイのセットアソシアティブ方式の場合には、以下の計算式で計算する。ただし、Ｎは２の倍数とする。
（ア） キャッシュヒットした場合： Ｎ／２−（ＬＲＵ情報１３３の値）
（イ） キャッシュミスした場合 ： −Ｎ／２

１−３． 上記１−２．で計算した値をプリフェッチ成功失敗カウンタに足しこむ。飽和カウンタなので計算結果がオーバーフローやアンダーフローになることはない。すなわち、計算結果が最小値を下回る場合には最小値、最大値を上回る場合には最大値となる。

また、要求するプリフェッチ幅は以下のアルゴリズムで決定する。プリフェッチ成功失敗カウンタ１２１が保持するカウンタ値に基づいて決定する。以下は８ウェイのセットアソシアティブキャッシュメモリの場合には以下のようになる。

２．プリフェッチ幅を決定するアルゴリズム
２−１． カウンタ値が２５６未満の場合にはキャッシュライン１つ分のプリフェッチを要求する。
２−２． カウンタ値が２５６以上、５１２未満の場合にはキャッシュライン２つ分のプリフェッチを要求する。
２−３． カウンタ値が５１２以上、１０２４未満の場合にはキャッシュライン３つ分のプリフェッチを要求する。
２−４． カウンタ値が１０２４以上の場合にはキャッシュライン４つ分のプリフェッチを要求する。

なお、このカウンタ値と要求するプリフェッチ幅の相関はキャッシュメモリのウェイ数にも依存するため、採用するキャッシュメモリのウェイ数に依存して変更する必要がある。また、キャッシュライン５つ分以上のプリフェッチ要求をすることも考えられる。
ここで、「キャッシュライン１つ分のプリフェッチ」とは図２に示すように、本来メモリアクセス要求が要求したラインと、その後１つ分のラインを指し示すものとする。これが、２つ分なら２ライン分、３つ分なら３ラインとなる。図２では、左側にライン１つ分をプリフェッチする場合、右側にライン２つ分をプリフェッチする場合を示している。
プリフェッチ制御部１２は、プリフェッチ成功失敗カウンタ１２１のカウンタ値に基づいてプリフェッチ幅を決定する。これにより、キャッシュメモリへ書き込んだコピーデータの再利用の度合いを推定する。言い換えれば、キャッシュメモリ登録後の空間的／時間的局所性を推定する。この推定結果（カウンタ値）に基づいてプリフェッチ幅を決定する。プリフェッチ幅で決定した複数のラインをあらかじめ取得することによりキャッシュヒット率を高めることができる。このようにして、プロセッサの実効性能を高めることが可能になる。

以上説明したように、キャッシュメモリ１は、キャッシュメモリ１の各ラインに対して、プリフェッチビット１３４を備える。そして、プリフェッチ制御部１２は、キャッシュメモリ１へのアクセス、すなわち、キャッシュメモリ１からのデータ読み出しとキャッシュメモリ１のデータを置き換えるときに、プリフェッチビット１３４に従って、プリフェッチしたラインの使用状況をチェックする。また、プリフェッチ制御部１２は、チェック結果を数値化（得点化）してその値を累積するプリフェッチ成功失敗カウンタ１２１を有する。さらに、プリフェッチ制御部１２は、プリフェッチ成功失敗カウンタ１２１を参照してプリフェッチ幅を決定し、プリフェッチリクエストを送出する。

次にキャッシュメモリ１（回路）の動作に関して、図３から図５を用いて説明する。図３は、実施形態１のキャッシュメモリの動作例を示すフローチャートである。図４は、キャッシュヒット時の処理の動作例を示すフローチャートであり、図５は、キャッシュミス時の処理の動作例を示すフローチャートである。プロセッサ２の内部においてロード命令などのメモリアクセス命令（主記憶装置３へのアクセス命令）が発行されると（Ｓ１１）、メモリアクセス命令はキャッシュコントローラ１１に渡される。このとき、キャッシュコントローラ１１は、制御情報メモリ１３へアクセスする。キャッシュコントローラ１１は、制御情報メモリ１３に保持する情報に従って動作する。具体的には、制御情報メモリ１３を参照し、アクセスする主記憶装置３のデータのコピーがデータアレイ１４に保持されているか（キャッシュヒット）否か（キャッシュミス）を判定する（Ｓ１２）。キャッシュコントローラ１１は、キャッシュヒットの場合（Ｓ１２でＹｅｓ）、キャッシュヒット時の処理（Ｓ１３）を実施し、キャッシュミスの場合（Ｓ１２でＮｏ）、キャッシュミス時の処理（Ｓ１４）を実施する。以下、図４、図５を用いてキャシュヒットの場合とキャッシュミスの場合との制御の相違を説明する。

まず、図４を用いて、キャッシュヒットの場合の動作を説明する。キャッシュコントローラ１１は、制御情報メモリ１３のプリフェッチビット１３４をチェックする（Ｓ２１）。プリフェッチビット１３４が１の場合（Ｓ２２でＹｅｓ）、キャッシュコントローラ１１は、プリフェッチ制御部１２に対してプリフェッチ成功失敗カウンタ１２１の更新指示を出す。このときにＬＲＵ情報１３３もプリフェッチ制御部１２に引き渡す。プリフェッチ制御部１２は、成功失敗度数を計算し（Ｓ２３）、プリフェッチ成功失敗カウンタ１２１を更新する（Ｓ２４）。その後、キャッシュコントローラ１１は、プリフェッチビット１３４をクリアする（Ｓ２５）。プリフェッチビット１３４が１以外の場合（Ｓ２２でＮｏ）、後述するステップＳ２６の処理へ進む。
また、キャッシュコントローラ１１は、ＬＲＵ情報を更新する（Ｓ２６）。具体的には、同一のセット中の他のラインでアクセスされたＬＲＵ情報１３３よりも小さいＬＲＵ情報１３３に対して＋１を実施する。また、アクセスされたラインのＬＲＵ情報を０にセットする。この処理は通常のＬＲＵ制御であり、広く知られた手法である。

キャッシュコントローラ１１は、データアレイ１４から要求された値を読み出して、リプライデータとする。

次に、図５を用いて、キャッシュミスの場合の動作を説明する。キャッシュコントローラ１１は、メモリコントローラ１０に対して主記憶装置３へのアクセス指示（以下、「主記憶アクセス要求」ともいう）を出す（Ｓ３１）。メモリコントローラ１０は、キャッシュコントローラ１１から主記憶アクセス要求を受け取ると、その要求されたアドレスに基づいて主記憶装置３に対してアクセスを実施する。メモリコントローラ１０は、要求されたアドレスに応じてデータがリプライとしてかえってくると、データアレイ１４にリプライデータを書き戻すため、データアレイ１４の書き戻し先を決定する。具体的には、メモリコントローラ１０は、キャッシュフィルする対象となるセットのＬＲＵ情報１３３を参照し、最も大きい値を持つラインを追い出されるラインとして決定する（Ｓ３２）。

続いて、メモリコントローラ１０は、追い出し対象のキャッシュラインのプリフェッチビット１３４を確認し、プリフェッチビット１３４が１の場合（Ｓ３３でＹｅｓ）、メモリコントローラ１０は、プリフェッチ制御部１２に対してプリフェッチ成功失敗カウンタ１２１の更新指示を出す。プリフェッチ制御部１２は、成功失敗度数を計算し（Ｓ３４）、プリフェッチ成功失敗カウンタ１２１を更新する（Ｓ３５）。
メモリコントローラ１０は、リプライデータを制御情報メモリ１３とデータアレイ１４に対して書き戻す（Ｓ３６：キャッシュの置き換え）。具体的には、メモリコントローラ１０は、リプライデータに応じて制御情報メモリ１３を更新し、リプライデータをデータアレイ１４にコピーする。このときに、ＬＲＵ情報１３３は０として書き戻す。また、制御情報メモリ１３にはプリフェッチビット１３４を０として書き込む。キャッシュの置き換え後、ステップＳ３９のプリフェッチ動作に取り掛かる。

メモリコントローラ１０は、キャッシュメモリへのフィルと平行して、プリフェッチを実施する。主記憶アクセス要求で要求されたアドレスがＡであった場合、Ａ＋１、Ａ＋２、Ａ＋３、・・・がプリフェッチ対象となる。メモリコントローラ１０は、プリフェッチの要求個数をプリフェッチ制御部１２に対して問い合わせる。プリフェッチ制御部１２は、メモリコントローラ１０からの問い合わせに応じて、プリフェッチ成功失敗カウンタ１２１が保持するカウンタ値に基づいて、プリフェッチ幅を決定し、通知する。メモリコントローラ１０は、通知されたプリフェッチ幅をプリフェッチ個数として決定する。メモリコントローラ１０は、プリフェッチ個数を確認し（Ｓ３９）、プリフェッチ要求がある場合（Ｓ４０でＹｅｓ）、プリフェッチ動作を、ステップＳ３１以降と同様の処理を用いて進める。プリフェッチ個数がゼロの場合（Ｓ４０でＮｏ）処理を終了する。

メモリコントローラ１０は、プリフェッチリクエストを主記憶装置３に対して送出する（Ｓ３１）。リプライが返ってくると、ステップＳ３２からＳ３６の手順で書き戻しを実施する。キャッシュの置き換え（Ｓ３６）終了後、メモリコントローラ１０は、今回のキャッシュの置き換えがプリフェッチアクセスであるかを判定し（Ｓ３７）、プリフェッチアクセスであるので（Ｓ３７でＹｅｓ）、制御情報メモリ１３にはプリフェッチビットを１として書き込む（Ｓ３８）。メモリコントローラ１０は、プリフェッチ個数を確認する（Ｓ３９）。プリフェッチ要求が残っている場合（Ｓ４０でＹｅｓ）、ステップＳ３１以降の処理をプリフェッチ要求がなくなるまで繰り返し、プリフェッチ個数の処理実施後（Ｓ４０でＮｏ）終了する。

以上説明したように、本実施形態のキャッシュメモリ１は、プログラムの実行時のプリフェッチの成功度合いを利用してプログラムの空間的局所性を動的に収集し、プリフェッチの要求量を動的に適切な量に変化させることで効率的なハードウェアプリフェッチ方式を実現する。具体的には、プリフェッチ成功失敗カウンタ１２１、プリフェッチビット１３４を用いて、プリフェッチ個数を動的に決定する。そして決定したプリフェッチ個数を用いて、主記憶装置３からデータを読み出すときに、読み出すデータに続けて格納されているデータを、プリフェッチ動作によってプリフェッチ個数分読み出す。その結果、データアレイ１４は、読み出したコピーデータのラインに加え、プリフェッチ動作によって書き込まれたプリフェッチ個数のラインが書き込まれる。このようにして、ハードウェアによるシーケンシャルプリフェッチ方式を実現する。

（実施形態２）
実施形態１では、Ｎウェイのセットアソシアティブ方式のキャッシュメモリを一例として説明したが、他の方式のキャッシュメモリに本発明を適用することも可能である。実施形態１では、成功失敗度数を計算する場合に、数値Ｎを用いて算出したが、ダイレクトマップ方式では、Ｎ＝１、フルアソシアティブ方式では、Ｎをエントリー数（総ライン数）として算出する。また、Ｎ＝１のセットアソシアティブ方式では、Ｎ＝１として算出する。
また、実施形態１で示した成功失敗度数の計算式は一例であり、この計算式に限られることはない、システムの動作状況等に基づいて、プリフェッチ成功失敗カウンタに適切な値が保持されることが好ましい。すなわち、最大値または最小値が継続して保持されることを避けるように計算式を決定することが好ましい。

（その他の実施形態）
本発明に係るキャッシュメモリ１を、１次キャッシュ、２次キャッシュという階層型のキャッシュメモリの構成をとるものに対しても構成することが可能である。この場合、各階層から見てプロセッサ側の階層を全てプロセッサ２として扱い、主記憶装置３を含む側の階層をすべて主記憶装置３として扱う。これにより、本発明を利用することができる。

以上説明したように、本発明のキャッシュメモリの一態様、及びキャッシュメモリが実現するプリフェッチ方法（プリフェッチ方式）の一態様によれば、次のような効果を奏する。第１の効果は、実行時の履歴を動的に収集し、プリフェッチ幅を決定できることである。メモリの空間的局所性はプログラム毎に大きく挙動の異なるふるまいをするため、実行時の情報を収集することで効率的なプリフェッチが実現できる。また、ＬＲＵ情報などの既存の情報を有効利用することで収集した情報の信頼度を高めている。

第２の効果は、小さいコストで実現可能なことである。本発明の追加コストはプリフェッチビットとプリフェッチ成功失敗カウンタのみである。このコストは制御情報メモリやデータアレイと比して非常に小さい。たとえば、ラインサイズ３２Ｂ（バイト）で論理アドレスが８Ｂのキャッシュメモリ上の各ラインに対するハードウェア増加分は０．３％程度である。

また、本発明は、高速な処理を要求されるプロセッサ、階層間の速度差を埋めるためにキャッシュ型のバッファ構造を持つ装置に対して、その性能を向上させるために適用することができる。

なお、本発明は上記に示す実施形態に限定されるものではない。本発明の範囲において、上記実施形態の各要素を、当業者であれば容易に考えうる内容に変更、追加、変換することが可能である。

本発明の実施形態１に係るキャッシュメモリの構成例を示すブロック図である。 プリフェッチを要求するラインを説明する図である。 実施形態１のキャッシュメモリの動作例を示すフローチャートである。 キャッシュヒット時の処理の動作例を示すフローチャートである。 キャッシュミス時の処理の動作例を示すフローチャートである。

符号の説明

１ キャッシュメモリ
２ プロセッサ
３ 主記憶装置
１０ メモリコントローラ
１１ キャッシュコントローラ
１２ プリフェッチ制御部
１３ 制御情報メモリ
１４ データアレイ
１２１ プリフェッチ成功失敗カウンタ
１３１ 有効ビット
１３２ タグアドレス
１３３ ＬＲＵ情報
１３４ プリフェッチビット

Claims (8)

1. プロセッサ及び主記憶装置に接続されるキャッシュメモリであって、
   前記主記憶装置が保存するデータのコピーをライン単位に保持するデータアレイと、
   前記主記憶装置からデータを読み出し、前記データのコピーを前記データアレイの各ラインに書き込むメモリ制御手段と、
   各ラインに保持されるデータのコピーを管理する管理情報と、各ラインに保持されたデータのコピーの使用状況を示す使用情報とを保持する制御情報メモリと、
   前記プロセッサからの要求に応じて、データのコピーが前記データアレイに保持されているかを前記管理情報に基づいて判断し、保持されている場合、前記データアレイからデータを読み出し、保持されていない場合、前記主記憶装置からデータを読み出すことを前記メモリ制御手段に指示するキャッシュ制御手段と、
   前記使用情報に基づいて、前記メモリ制御手段がプリフェッチするプリフェッチライン数を決定するプリフェッチ制御手段と、を備え、
   前記メモリ制御手段は、前記キャッシュ制御手段からの指示に応じて前記主記憶装置からデータを読み出すときに、前記プリフェッチライン数に従って、プリフェッチを行い、
   前記制御情報メモリは、前記使用情報として、ＬＲＵ（Least Recently Used）情報と、プリフェッチしたラインであることを示すプリフェッチ情報とを、各ラインに対応させて保持し、
   前記プリフェッチ制御手段は、前記ＬＲＵ情報を用いて、前記プリフェッチしたラインが利用される度合いを推定し、推定結果に基づいて前記プリフェッチライン数を決定する
   キャッシュメモリ。
2. 前記プリフェッチ制御手段は、前記度合いを推定し、数値化した推定結果を保持するカウンタを備え、前記プリフェッチしたラインが使用された場合、及び前記プリフェッチしたラインが使用されることなく置き換えられた場合に、前記推定結果を算出し、前記推定結果を前記カウンタが保持する値へ足すことを特徴とする請求項１記載のキャッシュメモリ。
3. 前記プリフェッチ制御手段は、前記プリフェッチしたラインが使用された場合、前記ＬＲＵ情報に基づいて、前記推定結果を増加させる値を算出し、前記プリフェッチしたラインが使用されることなく置き換えられた場合、前記推定結果を減少させる値を算出することを特徴とする請求項２記載のキャッシュメモリ。
4. 前記プリフェッチ制御手段は、前記プリフェッチしたラインが使用された場合、前記ＬＲＵ情報が最近アクセスしたことを示すほど、前記度合いを推定した算出結果を大きくすることを特徴とする請求項３記載のキャッシュメモリ。
5. 前記メモリ制御手段は、前記プリフェッチしたラインに対応するプリフェッチ情報を、プリフェッチしたことを示すＯＮに設定し、
   前記キャッシュ制御手段は、前記プリフェッチしたラインへアクセスしたときに前記プリフェッチ情報をＯＮからＯＦＦに更新し、前記プリフェッチ制御手段へ、前記推定結果の更新を指示することを特徴とする請求項２乃至４のいずれか一項に記載のキャッシュメモリ。
6. 前記メモリ制御手段は、前記プリフェッチしたラインに対応するプリフェッチ情報がＯＮであり、かつ、前記プリフェッチしたラインを置き換える場合に、前記プリフェッチ制御手段へ、前記推定結果の更新を指示することを特徴とする請求項５記載のキャッシュメモリ。
7. プロセッサ及び主記憶装置に接続されるキャッシュメモリのプリフェッチ方法であって、
   前記プロセッサからの要求に応じて、前記主記憶装置からデータを読み出すとともにプリフェッチを行い、
   読み出したデータのコピーとプリフェッチしたデータのコピーとデータアレイの各ラインに書き込み、
   前記プリフェッチを用いて書き込まれたラインが保持するデータの使用状況を監視し、
   前記使用状況として、前記プリフェッチを用いて書き込まれたラインであることを示すプリフェッチ情報と、ラインへのアクセス状況を示すＬＲＵ情報とを用いて、プリフェッチしたラインが利用される度合いを数値化してカウンタに保持し、
   前記カウンタに保持した値に従って、プリフェッチするライン数を決定する
   プリフェッチ方法。
8. 前記カウンタの値を、前記プリフェッチしたラインにアクセスがあったとき、及び、前記プリフェッチしたラインが利用されることなく置き換えられたときに更新することを特徴とする請求項７記載のプリフェッチ方法。

Images