(57)【要約】【課題】ＣＰＵの負荷を増大させることなく、キャッシュ・ミス時の置き換えペナルティを減少させる。【解決手段】キャッシュメモリのウェイ毎に対応してウェイ制御部を設け、各ウェイ制御部には、ウェイ内の各エントリに対応してアクセスサイクル数保持部１５１、カウント値保持部１５２及びカウンタ部１５３を設ける。このアクセスサイクル数保持部１５１では、対応するエントリが対応するメモリのサイクル数を保持する。カウント値保持部１５２の値は、対応するエントリにデータが格納される場合と当該エントリがキャッシュ・ヒットした場合に初期化し、カウンタ部１５３で一定のサイクルで更新する。そして、リプレイス時には、リプレイス決定部１７０で、各ウェイの前記カウント値保持部の値、又は各ウェイの前記アクセスサイクル数保持部と前記カウント値保持部の両方の値に応じ、リプレイス対象のエントリを決定する。【選択図】図１
2008181190.tif 000002
【特許請求の範囲】
【請求項１】
アクセスサイクル数が異なる複数のメモリをキャッシュの対象とし、複数のウェイを有するキャッシュメモリを制御するキャッシュ制御装置であって、
リプレイス対象のエントリを決定するリプレイス決定部と、
前記ウェイ毎に対応したウェイ制御部とを備え、
前記ウェイ制御部は、対応するウェイ内のエントリ毎に対応して設けられたアクセスサイクル数保持部及びカウント値保持部と、対応するウェイにおけるＮ個（Ｎは自然数）のエントリに対して１つずつ対応して設けられたカウンタ部とを有し、
前記アクセスサイクル数保持部は、対応するエントリが対応するメモリのサイクル数を保持し、
前記カウント値保持部は、対応するエントリにデータが格納される場合と当該エントリがキャッシュ・ヒットした場合とに初期化され、
前記カウンタ部は、対応するＮ個の前記カウント値保持部の値を、一定のサイクルで順次更新し、
前記リプレイス決定部は、各ウェイの前記カウント値保持部の値、又は各ウェイの前記アクセスサイクル数保持部と前記カウント値保持部の両方の値に応じ、リプレイス対象のエントリを決定することを特徴とするキャッシュ制御装置。
【請求項２】
請求項１のキャッシュ制御装置であって、
前記Ｎの値は、１であることを特徴とするキャッシュ制御装置。
【請求項３】
請求項１のキャッシュ制御装置であって、
前記カウント値保持部は、対応するエントリにデータが格納される場合には、データアクセスに要したサイクル数の値で初期化され、当該エントリがキャッシュ・ヒットした場合には、前記アクセスサイクル数保持部の値で初期化され、
前記カウンタ部は、ダウンカウンタであり、前記カウント値保持部の値を、一定の周期でデクリメントし、
前記リプレイス決定部は、各ウェイの前記カウント値保持部の値を比較して、値が最小のカウント値保持部に対応したエントリをリプレイス対象として決定することを特徴とするキャッシュ制御装置。
【請求項４】
請求項１のキャッシュ制御装置であって、
前記カウント値保持部は、対応するエントリへのデータ格納時と該当エントリがキャッシュ・ヒット時は０で初期化され、
前記カウンタ部は、アップカウンタであり、前記カウント値保持部の値を、一定の周期でインクリメントし、
前記リプレイス決定部は、エントリ毎の前記アクセスサイクル数保持部の値と前記カウント値保持部の値の差分値を各ウェイについて比較し、差分値が最小のエントリをリプレイス対象として決定することを特徴とするキャッシュ制御装置。
【請求項５】
請求項３のキャッシュ制御装置であって、
各カウンタ部は、何れかの前記カウント値保持部の値が０になった場合には、カウント動作を止めることを特徴とするキャッシュ制御装置。
【請求項６】
請求項４のキャッシュ制御装置であって、
各カウンタ部は、何れかのエントリに対応する前記カウント値保持部の値が、当該エントリに対応するアクセスサイクル数保持部の値になった場合には、カウント動作を止めることを特徴とするキャッシュ制御装置。
【請求項７】
アクセスサイクル数が異なる複数のメモリをキャッシュの対象とし、複数のウェイを有するキャッシュメモリを制御するキャッシュ制御装置であって、
リプレイス対象のエントリを決定するリプレイス決定部と、
前記ウェイ毎に対応したウェイ制御部とを備え、
前記ウェイ制御部は、カウンタ部と、対応するウェイ内のエントリ毎に対応して設けられたアクセスサイクル数保持部及びカウント値保持部とを有し、
前記アクセスサイクル数保持部は、対応するエントリが対応するメモリのサイクル数を保持し、
前記カウント値保持部は、対応するエントリにデータが格納される場合と当該エントリがキャッシュ・ヒットした場合とに初期化され、
前記カウンタ部は、エントリにデータが格納される場合には、データが格納されるウェイ以外のウェイで当該エントリに対応するエントリに対応したカウント値保持部の値を更新し、エントリがキャッシュ・ヒットした場合には、キャッシュ・ヒットしたウェイ以外のウェイで当該エントリに対応するエントリに対応したカウント値保持部の値を更新し、
前記リプレイス決定部は、各ウェイの前記カウント値保持部の値、又は各ウェイの前記アクセスサイクル数保持部と前記カウント値保持部の両方の値に応じ、リプレイス対象のエントリを決定することを特徴とするキャッシュ制御装置。
【請求項８】
請求項３のキャッシュ制御装置であって、
前記カウント値保持部及び前記カウンタ部は、共通のコンデンサを備えており、
前記コンデンサは、対応するエントリへのデータ格納時とキャッシュ・ヒット時は、メモリアクセスサイクル数の期間だけ充電され、キャッシュ・ミス時は放電させられ、
前記リプレイス決定部は、各コンデンサの電位を測定し、電位が最小のコンデンサが対応するエントリをリプレイス対象エントリとして選択することを特徴とするキャッシュ制御装置。
【請求項９】
請求項４のキャッシュ制御装置であって、
前記カウント値保持部及び前記カウンタ部は、共通のコンデンサを備えており、
前記コンデンサは、対応するエントリへのデータ格納時とキャッシュ・ヒット時は、放電させられ、キャッシュ・ミス時は、充電され、
前記リプレイス決定部は、同じエントリに対応する、アクセスサイクル数保持部の値とコンデンサの電位から求められる値との差分値を比較し、差分値が最小のエントリを、リプレイス対象として選択することを特徴とするキャッシュ制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アクセスサイクル数が異なる複数のメモリをキャッシュの対象とし、複数のウェイ（Ｗａｙ）を有するキャッシュメモリを制御するキャッシュ制御装置に関するものである。
【背景技術】
【０００２】
一般に、セット・アソシアティブ・キャッシュ構成のキャッシュメモリでは、キャッシュ・ミスが発生した場合は、例えばＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）方式のように、アクセス履歴を指標として置き換えエントリの選択を行う。
【０００３】
しかしながら、組み込みシステムのように、メモリアクセスサイクル数が不均一のシステムにおいては、アクセス履歴を指標として置き換えエントリを選択すると、アクセスサイクル数の大きなメモリが頻繁に置き換えられる可能性があり、キャッシュ・ミス時の置き換えペナルティが大きくなる可能性がある。
【０００４】
メモリアクセスサイクル数が不均一の複数種類のメモリを有するシステムにおけるキャッシュ制御装置の一例としては、置き換えの順位付けの指針を示すデータを格納するキャッシュ置き換え制御アレイ（ＣＲＣＡ）を備え、ＣＲＣＡのデータを書き換えることで、キャッシュ・ミス時の置き換えエントリ選択方法を動的に再構築できるキャッシュ制御装置がある（例えば、特許文献１参照）。
【０００５】
特許文献１に記載のキャッシュ制御装置では、キャッシュ・ヒットの回数やメモリアクセスサイクル数、メモリアクセス回数などの統計を収集し、収集された統計から、キャッシュ・ミス時の置き換えペナルティを算出する。そして、算出された置き換えペナルティをＣＲＣＡに設定することで、キャッシュ・ミス時の予期される置き換えペナルティが最小になるような、置き換えエントリ選択方法を構築する。このキャッシュ制御装置では、統計の収集や置き換えペナルティの算出、算出されたペナルティのＣＲＣＡへの設定は、すべてソフトウェアによって行われている。
【０００６】
この特許文献１に記載のキャッシュ制御装置を用いれば、メモリアクセスサイクル数が不均一のシステムにおいても、キャッシュ・ミス時の予期される置き換えペナルティが最小になるような、置き換えエントリ選択方法の構築が可能である。
【特許文献１】特開２００４−１６４６０６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１に記載のキャッシュ制御装置では、キャッシュ・ミス時の置き換えペナルティの算出に、統計の収集が必要であるので、以下に挙げる問題点がある。
【０００８】
まず、特許文献１に記載のキャッシュ制御装置では、統計の収集をソフトウェアによって周期的に行い、都度キャッシュ・ミス時の置き換えペナルティを算出し、ＣＲＣＡを設定しなおしている。つまり、統計の収集毎に置き換えペナルティを再算出するわけである。このことは言い換えれば、都度算出される置き換えペナルティは、統計的に予期される最小の置き換えペナルティであり、そのシステムにおけるキャッシュ・ミス時の置き換えペナルティを、必ずしも正確に見積もっていないことを表している。
【０００９】
よって、統計の収集が必要なキャッシュ制御装置では、メモリアクセスサイクル数が不均一なシステムにおいて、必ずしも、キャッシュ・ミス時の置き換えペナルティが最小になるような、置き換えエントリ選択方法は提供できない。
【００１０】
キャッシュ・ミス時の置き換えペナルティをより正確に見積もるためには、周期的に行われる統計の収集の頻度を上げればよい。しかし、統計の収集や置き換えペナルティの算出、ＣＲＣＡの設定の一連の処理は、ソフトウェアによって行われるため、統計の収集の頻度を上げると、一連の処理によるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）の占有時間が増加してしまうという新たな問題が発生する。
【００１１】
本発明は、上記の問題に着目してなされたものであり、アクセスサイクル数が異なる複数種類のメモリを有するシステムにおいて、ＣＰＵの負荷を増大させることなく、キャッシュ・ミス時の置き換えペナルティを減少させるようにすることを目的としている。
【課題を解決するための手段】
【００１２】
前記の課題を解決するため、本発明の一態様は、
アクセスサイクル数が異なる複数のメモリをキャッシュの対象とし、複数のウェイを有するキャッシュメモリを制御するキャッシュ制御装置であって、
リプレイス対象のエントリを決定するリプレイス決定部と、
前記ウェイ毎に対応したウェイ制御部とを備え、
前記ウェイ制御部は、対応するウェイ内のエントリ毎に対応して設けられたアクセスサイクル数保持部及びカウント値保持部と、対応するウェイにおけるＮ個（Ｎは自然数）のエントリに対して１つずつ対応して設けられたカウンタ部とを有し、
前記アクセスサイクル数保持部は、対応するエントリが対応するメモリのサイクル数を保持し、
前記カウント値保持部は、対応するエントリにデータが格納される場合と当該エントリがキャッシュ・ヒットした場合とに初期化され、
前記カウンタ部は、対応するＮ個の前記カウント値保持部の値を、一定のサイクルで順次更新し、
前記リプレイス決定部は、各ウェイの前記カウント値保持部の値、又は各ウェイの前記アクセスサイクル数保持部と前記カウント値保持部の両方の値に応じ、リプレイス対象のエントリを決定することを特徴とする。
【００１３】
また、本発明の一態様は、
アクセスサイクル数が異なる複数のメモリをキャッシュの対象とし、複数のウェイを有するキャッシュメモリを制御するキャッシュ制御装置であって、
リプレイス対象のエントリを決定するリプレイス決定部と、
前記ウェイ毎に対応したウェイ制御部とを備え、
前記ウェイ制御部は、カウンタ部と、対応するウェイ内のエントリ毎に対応して設けられたアクセスサイクル数保持部及びカウント値保持部とを有し、
前記アクセスサイクル数保持部は、対応するエントリが対応するメモリのサイクル数を保持し、
前記カウント値保持部は、対応するエントリにデータが格納される場合と当該エントリがキャッシュ・ヒットした場合とに初期化され、
前記カウンタ部は、エントリにデータが格納される場合には、データが格納されるウェイ以外のウェイで当該エントリに対応するエントリに対応したカウント値保持部の値を更新し、エントリがキャッシュ・ヒットした場合には、キャッシュ・ヒットしたウェイ以外のウェイで当該エントリに対応するエントリに対応したカウント値保持部の値を更新し、
前記リプレイス決定部は、各ウェイの前記カウント値保持部の値、又は各ウェイの前記アクセスサイクル数保持部と前記カウント値保持部の両方の値に応じ、リプレイス対象のエントリを決定することを特徴とする。
【発明の効果】
【００１４】
本発明によれば、アクセスサイクル数が異なる複数種類のメモリを有するシステムにおいて、ＣＰＵの負荷を増大させることなく、キャッシュ・ミス時の置き換えペナルティを減少させることが可能になる。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施形態について図面を参照しながら説明する。なお、以下の各実施形態の説明において、一度説明した構成要素と同様の機能を有する構成要素については、同一の符号を付して説明を省略する。
【００１６】
《発明の実施形態１》
図１は、本発明の実施形態１に係るキャッシュ制御装置１００の構成を示すブロック図である。キャッシュ制御装置１００は、２ウェイ・セット・アソシアティブ構成のキャッシュ制御装置の例である。
【００１７】
（キャッシュ制御装置１００の構成）
キャッシュ制御装置１００は、図１に示すように、キャッシュメモリ１１０、置き換えエントリ選択部１２０、及びメモリコントローラ１３０を備え、メモリ１４０〜メモリ１４２へのアクセスを制御する。
【００１８】
キャッシュメモリ１１０は、ウェイ０及びウェイ１の２ウェイを有したキャッシュメモリである。各ウェイの各エントリには、バリッドビット（以下、Ｖビットという。）が対応して設けられている。Ｖビットは、対応するエントリが有効であるかどうかを示すビットである。本実施形態では、Ｖ＝０のときは、エントリが無効であり、Ｖ＝１のときは、エントリが有効であるものとする。
【００１９】
置き換えエントリ選択部１２０は、ウェイ０制御部１５０、ウェイ１制御部１６０、及びリプレイス決定部１７０を備えている。
【００２０】
ウェイ０制御部１５０は、ウェイ０のエントリ毎に対応した、アクセスサイクル数保持部１５１、カウント値保持部１５２、及びカウンタ部１５３を備えている。例えば、キャッシュメモリ１１０のウェイ０に、エントリ０からエントリｎ−１（ｎは２以上の整数）までのｎ個のエントリがあるとすれば、アクセスサイクル数保持部１５１、カウント値保持部１５２、及びカウンタ部１５３もそれぞれｎ個ある。なお、図中などでは、例えばアクセスサイクル数保持部１５１−０、カウント値保持部１５２−０、カウンタ部１５３−０のように、対応するエントリの番号を符号の後に付記して、対応関係を識別する。
【００２１】
各アクセスサイクル数保持部１５１は、対応するエントリが同じであるカウント値保持部１５２を初期化する。例えば、エントリ０に対応するアクセスサイクル数保持部１５１−０は、カウント値保持部１５２−０を初期化する。また、初期化は、対応するエントリに対するキャッシュ・ヒット時と該当エントリへのデータ格納（以降、このことを“リフィル”と呼ぶ）時に行なう。初期値は、リフィル時は、データアクセスに要したサイクル数の値であり、キャッシュ・ヒット時は、アクセスサイクル数保持部１５１が保持している値である。
【００２２】
各カウント値保持部１５２は、リフィルの対象となるエントリを決定するための値（指標）を保持するようになっている。カウント値保持部１５２は、データアクセスに要したサイクル数、あるいはアクセスサイクル数保持部１５１によって、初期値を設定され、また、カウンタ部１５３によって、保持した値が更新されるようになっている。
【００２３】
各カウンタ部１５３は、対応するカウント値保持部１５２を、一定のサイクルで更新するようになっている。ただし、カウント値保持部１５２が、そのサイクルで初期化される場合には、更新は行なわれない。カウンタ部１５３は、具体的には、後述するようにダウンカウンタによってもアップカウンタによっても構成できるが、実施形態１ではダウンカウンタによって構成した例を説明する。
【００２４】
図２は、ウェイ０制御部１５０及びウェイ１制御部１６０のカウンタ部１５３をダウンカウンタ１８０で構成した例を示す図である。ダウンカウンタ１８０は、一定のサイクルで、対応するカウント値保持部１５２の値をデクリメントする。
【００２５】
なお、ダウンカウンタ１８０によるカウント値保持部１５２の更新方法には、両ウェイのカウント値保持部１５２が０になるまでデクリメントする方法や、どちらか一方のウェイのカウント値保持部１５２が０になった段階で、もう一方のウェイにおいて同一エントリに対応したカウント値保持部１５２のデクリメントを停止する方法等がある。
【００２６】
ウェイ１制御部１６０も、ウェイ０制御部１５０と同様に、ウェイ１のエントリ毎に対応したアクセスサイクル数保持部１５１、カウント値保持部１５２、及びカウンタ部１５３（ダウンカウンタ１８０）を備えている。ウェイ１制御部１６０でも、アクセスサイクル数保持部１５１、カウント値保持部１５２、及びカウンタ部１５３（ダウンカウンタ１８０）は、ウェイ１のエントリに対応した数が設けられている。
【００２７】
リプレイス決定部１７０は、両ウェイのカウント値保持部１５２の値に応じ、ウェイ０及びウェイ１のうちの何れのエントリをリプレイスするかを決定するようになっている。
【００２８】
図２のように、カウンタ部１５３をダウンカウンタ１８０で構成した場合には、リプレイス決定部１７０には、ウェイ０のカウント値保持部の出力値とウェイ１のカウント値保持部の出力値とを比較する比較器１９０を設ける。
【００２９】
メモリコントローラ１３０は、キャッシュ・ミスした場合にはメモリ１４０〜メモリ１４２からデータを読み出して出力するようになっている。また、このメモリコントローラ１３０は、ウェイ０制御部１５０とウェイ１制御部１６０とに、メモリ１４０、メモリ１４１、及びメモリ１４２のメモリアクセスサイクル数を出力する。
【００３０】
メモリ１４０〜メモリ１４２は、キャッシュの対象となるメモリである。本実施形態では、メモリ１４０は、３サイクルアクセスのメモリ、メモリ１４１は、１０サイクルアクセスのメモリ、メモリ１４２は、２０サイクルアクセスのメモリであるものとする。
【００３１】
（キャッシュ制御装置１００の動作）
キャッシュ制御装置１００の動作について、図３のフローチャートを参照して説明する。
【００３２】
キャッシャブル空間へのアクセスが発生したら、まず、ステップＳ１０１では、キャッシュ・ヒットかキャッシュ・ミスかを判定する。
【００３３】
キャッシュ・ヒットした場合には、ステップＳ１０２の処理に移行する。ステップＳ１０２では、ヒットしたウェイのエントリに対応するカウント値保持部１５２の値を、ヒットしたウェイのエントリに対応するアクセスサイクル数保持部１５１の値で初期化する。例えばウェイ０のエントリ１がヒットした場合には、ウェイ０制御部１５０のカウント値保持部１５２−１の値を、ウェイ０制御部１５０のアクセスサイクル数保持部１５１−１の値で初期化する。
【００３４】
また、キャッシュ・ミスした場合は、ステップＳ１０３の処理に移行する。ステップＳ１０３では、まずＶビットの値を確認する。確認の結果、Ｖ＝０のウェイがある場合は、ステップＳ１０４に移行する。
【００３５】
ステップＳ１０４では、そのウェイのエントリを、リフィル対象エントリとして選択する。Ｖビットが０のウェイが複数ある場合（すなわち、本実施形態では両ウェイのＶビットが０の場合）は、何れのウェイを選択するか予め定めておき、それを選択する。Ｖビットが０のウェイが複数ある場合の選択方法としては、例えば最小のウェイ番号のウェイ（この例ではウェイ０）を選択する方法などが考えられる。なお、Ｖビットを用いた以上の動作は、従来のキャッシュ制御装置と同様である。
【００３６】
また、この時、リフィル対象エントリに対応したアクセスサイクル数保持部１５１、及びカウント値保持部１５２には、リフィル時のメモリアクセスサイクル数を設定する。
【００３７】
一方、ステップＳ１０３において、両ウェイともにＶ＝１と判定した場合（すなわち、キャッシュ・ミスかつ両ウェイのＶビットが１）には、ステップＳ１０５の処理に移行する。この場合、両ウェイのＶビットが１であるので、両ウェイのエントリが有効である。キャッシュ・ミスによるリフィルのためには、リプレイス対象エントリを選択する必要がある。
【００３８】
そのため、ステップＳ１０５では、ウェイ０制御部１５０及びウェイ１制御部１６０のそれぞれにおいてアクセスするエントリに対応するカウント値保持部１５２の出力値の値を、それぞれリプレイス決定部１７０に出力する。リプレイス決定部１７０では、入力された値を比較器１９０で比較する。
【００３９】
その結果、ウェイ１制御部１６０の出力値よりも、ウェイ０制御部１５０の出力値の方が小さいか、あるいは同じ値の場合には、ステップＳ１０６の処理に移行する。
【００４０】
ステップＳ１０６では、ウェイ０のエントリをリプレイス対象エントリとして選択する。そして、リフィル時のメモリアクセスサイクル数を、ウェイ０のリプレイス対象エントリに対応するアクセスサイクル数保持部１５１、及びカウント値保持部１５２に設定する。
【００４１】
また、ステップＳ１０５での比較の結果、ウェイ０の出力値よりもウェイ１の出力値の方が小さい場合には、ステップＳ１０７の処理に移行する。
【００４２】
ステップＳ１０７では、ウェイ１のエントリをリプレイス対象エントリとして選択する。そして、リフィル時のメモリアクセスサイクル数を、ウェイ１のリプレイス対象エントリに対応するアクセスサイクル数保持部１５１、及びカウント値保持部１５２に設定する。
【００４３】
一方、リフィルやキャッシュ・ヒットにともなって初期化されるカウント値保持部１５２以外のカウント値保持部１５２（ウェイ０及びウェイ１の両方）は、ダウンカウンタ１８０によって、一定のサイクルでデクリメントされる。
【００４４】
なお、本実施形態では、ウェイ０のカウント値保持部１５２とウェイ１のカウント値保持部１５２の出力値が同じである場合は、ウェイ番号が小さい方（ウェイ０）のエントリをリプレイス対象エントリとして選択したが、ウェイ番号が大きい方を選択したり、あるいはアクセスサイクル数保持部の値の大小でリプレイス対象エントリを選択したりすることも可能である。
【００４５】
（具体的な動作例１）
次に、アクセスサイクル数の大きなメモリが、アクセスサイクル数の小さなメモリよりも先に、キャッシュにリフィルされた場合を例に、キャッシュ制御装置１００の動作を説明する。図４は、この場合のウェイ０及びウェイ１のカウント値保持部１５２の値の変化を示す図である。
【００４６】
図４において、例えばメモリ１４２のデータがサイクルＣ４０１でウェイ０にリフィルされたとする。この場合、サイクルＣ４０１で、ウェイ０のカウント値保持部１５２は、メモリ１４２のアクセスサイクル数である２０で初期化され、それ以降はダウンカウンタ１８０によりデクリメントされる。
【００４７】
また、メモリ１４１のデータがサイクルＣ４０２でウェイ１にリフィルされたとする。この場合、サイクルＣ４０２で、ウェイ１のカウント値保持部１５２の値は、メモリ１４１のアクセスサイクル数である１０に初期化され、それ以降ダウンカウンタによりデクリメントされる。
【００４８】
この状態において、サイクルＣ４０３でメモリ１４０へのアクセスによりキャッシュ・ミスが発生し、エントリのリプレイスが必要になったとする。この場合に、両ウェイのカウント値保持部１５２の値を比較すると、ウェイ１のアクセスサイクル数保持部１５１の値の方が小さい。したがって、アクセスサイクル数が小さい方のメモリ１４１のデータが格納されている、ウェイ１のエントリがリプレイス対象エントリとして選択される。また、ウェイ１のカウント値保持部１５２の値は、サイクルＣ４０４で、メモリ１４０のアクセスサイクル数である３に初期化される。
【００４９】
なお、従来のＬＲＵ方式であれば、最近アクセスがあった方のデータをキャッシュに残すので、この例の場合、サイクルＣ４０３では、メモリアクセスサイクル数に関係なく、メモリ１４２（アクセスサイクル数が大きい方のメモリ）のデータが格納されている、ウェイ０のエントリをリプレイス対象エントリとして選択していた。
【００５０】
（具体的な動作例２）
図５は、ウェイ１にキャッシュ・ヒットが発生した場合の、ダウンカウンタの動作を例示する図である。
【００５１】
図５において、メモリ１４２のデータ及びメモリ１４１のデータがリフィルされるタイミングは、図４の場合と同様である（サイクルＣ５０１及びサイクルＣ５０２）。この例では、ウェイ０のカウント値保持部は、サイクルＣ５０１では、メモリ１４２のアクセスサイクル数である２０が格納されている。また、ウェイ１のカウント値保持部は、サイクルＣ５０２では、メモリ１４１のアクセスサイクル数である１０が格納されている。
【００５２】
例えば、サイクルＣ５０３において、ウェイ１にキャッシュ・ヒットした場合には、ウェイ１のカウント値保持部１５２の値は、サイクルＣ５０４で、アクセスサイクル数保持部１５１に保持されているリフィル時のメモリアクセスサイクル数（メモリ１４１のメモリアクセスサイクル数である１０）に初期化される。
【００５３】
この状態で、サイクルＣ５０５でキャッシュ・ミスが発生し、エントリのリプレイスが必要になったとする。この場合に、両ウェイのカウント値保持部１５２を比較すると、キャッシュ・ミスした期間が長いウェイ０のカウント値保持部１５２の方が小さい。そのため、ウェイ０のエントリがリプレイス対象エントリとして選択される。
【００５４】
つまり、アクセスサイクル数の大きなメモリのデータであっても、キャッシュ・ミスした期間が続くと、いずれはリプレイス対象エントリとして選択されることになる。
【００５５】
以上をまとめると、キャッシュ制御装置１００では、アクセスサイクル数保持部１５１によって、該当エントリへのリフィル時のデータアクセスに要したサイクル数を常に観測することが可能となる。
【００５６】
また、カウント値保持部１５２の値を、リフィル時とキャッシュ・ヒット時は初期化する。そして、カウンタ部１５３によって一定のサイクルでカウント値保持部１５２の保持内容を更新することで、各エントリのデータのキャッシュ・ミス期間を常に観測することが可能となる。
【００５７】
また、リプレイス決定部１７０では、カウント値保持部１５２の出力値を用いて、リフィル時のメモリアクセスサイクル数とキャッシュ・ミス期間を指標とした、リプレイス対象エントリの選択が可能となる。
【００５８】
例えば、カウンタ部１５３をダウンカウンタで構成した場合には、カウント値保持部１５２を、該当エントリのリフィル時は、メモリアクセスサイクル数で初期化し、ヒット時は、アクセスサイクル数保持部１５１の値で初期化する。そして、ダウンカウンタ１８０によって一定サイクルでカウント値保持部１５２の値をデクリメントし、リプレイス対象エントリ選択時は、カウント値保持部１５２の出力値が最小のエントリをリプレイス対象として選択する。これらにより、アクセスサイクル数が最小のメモリのデータが格納されているエントリを、リプレイス対象として選択可能となる。
【００５９】
また、カウント値保持部１５２の値を、ダウンカウンタ１８０によって一定サイクルでデクリメントするので、アクセスサイクル数の大きなメモリのデータが格納されたエントリにおいても、キャッシュ・ミス期間が続くと、リプレイス対象として選択される。
【００６０】
また、どちらか一方のウェイのカウント値保持部１５２が０になった段階で、もう一方のウェイの同一エントリに対応したカウント値保持部１５２のデクリメントを停止すれば、カウント値保持部１５２の値が複数ウェイで０にならないので、カウント値保持部１５２の値による置き換えエントリの選択が不可能になることを防ぐことができる。
【００６１】
以上のように、本実施形態によれば、メモリのアクセスサイクル数及びキャッシュ・ミスの続いた期間に応じて、リプレイス対象のエントリが決定される。それゆえ、アクセスサイクル数が異なる複数種類のメモリを有するシステムにおいて、ＣＰＵの負荷を増大させることなく、キャッシュ・ミス時の置き換えペナルティを減少させることが可能になる。
【００６２】
《発明の実施形態２》
実施形態２では、ダウンカウンタ１８０の代わりにアップカウンタを用いるキャッシュ制御装置の例を説明する。
【００６３】
図６は、本発明の実施形態２に係るキャッシュ制御装置の一部を抜粋したブロック図である。実施形態２に係るキャッシュ制御装置は、キャッシュ制御装置１００のウェイ０制御部１５０及びウェイ１制御部１６０をそれぞれウェイ０制御部２１０及びウェイ１制御部２２０に置き換え、リプレイス決定部１７０をリプレイス決定部２３０に置き換えて構成したものである。
【００６４】
ウェイ０制御部２１０は、ウェイ０制御部１５０のカウンタ部１５３をアップカウンタ２１１によって構成したものである。
【００６５】
アップカウンタ２１１は、一定のサイクルで、対応するカウント値保持部１５２の値をインクリメントするようになっている。ただし、そのサイクルで、リフィルやキャッシュ・ヒットにより、カウント値保持部１５２が初期化される場合にはインクリメントされない。
【００６６】
なお、カウント値保持部１５２の値が対応するアクセスサイクル数保持部１５１の値に達した時には、そのカウント値保持部１５２が対応したエントリと同一エントリのアップカウンタ２１１のインクリメント動作を、全ウェイにおいて止めるようにする。
【００６７】
また、本実施形態では、対応するエントリのキャッシュ・ヒット時とリフィル時に、対応するカウント値保持部１５２を０で初期化するように構成する。
【００６８】
ウェイ１制御部２２０は、ウェイ０制御部２１０と同様に、ウェイ１制御部１６０のカウンタ部１５３をアップカウンタ２１１によって構成したものである。
【００６９】
リプレイス決定部２３０は、各ウェイにおける、アクセスサイクル数保持部１５１の値とカウント値保持部１５２の値とに応じ、ウェイ０及びウェイ１のうちの何れのエントリをリプレイスするかを決定するようになっている。具体的には、リプレイス決定部２３０は、演算器２３１、演算器２３２、及び比較器２３３を備えている。
【００７０】
演算器２３１は、ウェイ０制御部２１０のアクセスサイクル数保持部１５１の値とカウント値保持部１５２の値の差分値を求めるようになっている。また、演算器２３２は、ウェイ１制御部２２０のアクセスサイクル数保持部１５１の値とカウント値保持部１５２の値の差分値を求めるようになっている。
【００７１】
比較器２３３は、演算器２３１の出力と演算器２３２の出力を比較し、比較結果を出力するようになっている。
【００７２】
（実施形態２に係るキャッシュ制御装置の動作）
本実施形態では、各ウェイのカウント値保持部１５２は、リフィル時とキャッシュ・ヒット時は０で初期化され、それ以外は、一定のサイクルでアップカウンタ２１１によってインクリメントされる。
【００７３】
リプレイス対象エントリの選択時は、エントリ毎の各ウェイのアクセスサイクル数保持部１５１の値とカウント値保持部１５２の値の差分値を、リプレイス決定部２３０内の演算器２３１及び演算器２３２でそれぞれ求める。そして、得られたそれぞれの差分値を比較器２３３で比較し、差分値が最小のエントリをリプレイス対象エントリとして選択する。
【００７４】
以上をまとめると、実施形態２に係るキャッシュ制御装置では、カウンタ部をアップカウンタで構成し、カウント値保持部１５２を、該当エントリのリフィル時とヒット時は０で初期化し、アップカウンタ２１１によって一定サイクルでカウント値保持部１５２の値をインクリメントする。また、リプレイス対象エントリ選択時は、アクセスサイクル数保持部１５１の値とカウント値保持部１５２の値の差分値が最小のウェイのエントリをリプレイス対象として選択する。これらにより、アクセスサイクル数が最小のメモリのデータが格納されているエントリを、リプレイス対象として選択可能となる。
【００７５】
また、アップカウンタ２１１によるカウント値保持部１５２のインクリメントによって、アクセスサイクル数の大きなメモリのデータが格納されたエントリにおいても、キャッシュ・ミス期間が続くと、リプレイス対象として選択される。
【００７６】
また、何れかのカウント値保持部１５２が、対応するアクセスサイクル数保持部１５１の値に達した場合、全ウェイの同一エントリにおいて、アップカウンタ２１１によるカウントを止める。これにより、アクセスサイクル数保持部１５１の値とカウント値保持部１５２の値の差分値が全ウェイで０にならないようにできるので、差分値による置き換えエントリの選択が不可能になることを防ぐことができる。
【００７７】
以上のように、本実施形態においてもやはり、メモリのアクセスサイクル数及びキャッシュ・ミスの続いた期間に応じて、リプレイス対象のエントリが決定される。すなわち、カウンタ部１５３をアップカウンタで構成しても、実施形態１のキャッシュ制御装置（カウンタ部をダウンカウンタで構成したキャッシュ制御装置）と同様の効果が得られる。
【００７８】
《発明の実施形態３》
次に、本発明の実施形態３に係るキャッシュ制御装置について説明する。実施形態３に係るキャッシュ制御装置は、図２に示したキャッシュ制御装置１００のウェイ０制御部１５０及びウェイ１制御部１６０のそれぞれを、図７に示すウェイ制御部３００で置き換えたものである。すなわち、本実施形態でも、ウェイ０制御部とウェイ１制御部は同様の構成をしている。
【００７９】
図７に示すように、各ウェイ制御部３００は、ｎ個（ｎは自然数）のエントリに対応したアクセスサイクル数保持部１５１−０〜７，・・・，ｎ−１（ｎ個のアクセスサイクル数保持部）、カウント値保持部１５２−０〜７，・・・，ｎ−１（ｎ個のカウント値保持部）、ダウンカウンタ３１０、及びセレクタ３２０を備えている。なお、図７には、アクセスサイクル数保持部１５１−８以降、及びカウント値保持部１５２−８以降については、図示を省略している。
【００８０】
ダウンカウンタ３１０は、４つのエントリに対して１つが対応して設けられており、その４つのエントリに対応したカウント値保持部１５２（４つある）の値を一定のサイクルで順次デクリメントする。
【００８１】
セレクタ３２０は、各ダウンカウンタ３１０に対応して設けられており、対応するダウンカウンタ３１０がデクリメントするカウント値保持部１５２を選択する。なお、セレクタ３２０は、選択するカウント値保持部１５２を１サイクル毎に切り替える。すなわち、本実施形態では、カウント値保持部１５２は、４サイクルに一度、セレクタ３２０によって選択されて、ダウンカウンタ３１０によってデクリメントされる。
【００８２】
次に、実施形態３に係るキャッシュ制御装置の動作を、図８を用いて説明する。図８は、カウント値保持部１５２の値の変化を示す図である。
【００８３】
まず、図８に示すサイクルＣ８０１において、セレクタ３２０によってカウント値保持部１５２−０が選択されたとすると、その値がダウンカウンタ３１０によってデクリメントされる。そして、次のサイクルＣ８０２では、デクリメントされた値がカウント値保持部１５２−０に格納される。
【００８４】
以下同様に、サイクルＣ８０３ではカウント値保持部１５２−１がデクリメントされ、サイクルＣ８０４ではカウント値保持部１５２−２がデクリメントされ、サイクルＣ８０５ではカウント値保持部１５２−３がデクリメントされる。
【００８５】
このように、４エントリ分のカウント値保持部１５２−０〜３のデクリメントが行われると、再びサイクルＣ８０６から、カウント値保持部１５２−０〜３のデクリメントが再開される。
【００８６】
また、同時に、カウント値保持部１５２−４〜７も同様にして、４サイクル掛けて４エントリ分がデクリメントされる。また、図８には示されていないカウント値保持部１５２−８以降も、同様にして４サイクル掛けて４エントリ分がデクリメントされる。
【００８７】
なお、リプレイス対象エントリ選択時には、実施の形態１と同様に、エントリ毎に各ウェイのカウント値保持部１５２の値を比較し、その値が小さい方のエントリをリプレイス対象エントリとして選択する。
【００８８】
以上のように、本実施形態では、ダウンカウンタ３１０を４エントリ分のカウント値保持部１５２毎に１つを設け、各カウント値保持部１５２のデクリメントの頻度を４サイクルに１回の割合にしたので、図２に示した構成のように、エントリ毎にダウンカウンタを備える場合よりも、回路面積の削減が図れる。
【００８９】
なお、本実施形態では、ダウンカウンタを４エントリ毎に１つを備える構成例を示したが、１つのダウンカウンタが受け持つエントリ数は、この例には限定されない。例えば、１つのダウンカウンタで、５つ以上のカウント値保持部の値を順次更新するように構成してもよい。
【００９０】
また、本実施形態では、カウンタ部がダウンカウンタの例を説明したが、カウンタ部をアップカウンタで構成してもよい。
【００９１】
《発明の実施形態４》
次に、本発明の実施形態４に係るキャッシュ制御装置について説明する。実施形態４に係るキャッシュ制御装置は、図２に示したキャッシュ制御装置１００のウェイ０制御部１５０及びウェイ１制御部１６０のそれぞれを、図９に示すウェイ制御部４００で置き換えたものである。すなわち、本実施形態でも、ウェイ０制御部とウェイ１制御部は同様の構成をしている。
【００９２】
図９に示すように、各ウェイ制御部４００は、アクセスサイクル数保持部１５１−０〜７，・・・，ｎ−１（ｎ個のアクセスサイクル数保持部）、カウント値保持部１５２−０〜７，・・・，ｎ−１（ｎ個のカウント値保持部）、ダウンカウンタ４１０、及びセレクタ４２０を備えている。なお、図９には、アクセスサイクル数保持部１５１−８以降と、カウント値保持部１５２−８以降とについては、図示を省略している。
【００９３】
ダウンカウンタ４１０は、各ウェイ制御部４００に１つが設けられており、セレクタ４２０によって選択されたカウント値保持部１５２の値をデクリメントする。
【００９４】
セレクタ４２０は、各ウェイ制御部４００に１つが設けられており、ダウンカウンタ４１０がデクリメントするカウント値保持部１５２を選択する。
【００９５】
詳しくは、リフィル時は、リフィル対象エントリが属するのとは異なるウェイにおけるセレクタ４２０が、そのエントリと同一のエントリに対応するカウント値保持部１５２がデクリメントされるように選択を行なう。また、ヒット時には、ヒットしたエントリが属するのとは異なるウェイにおけるセレクタ４２０が、そのエントリと同一のエントリに対応するカウント値保持部１５２がデクリメントされるように選択を行なう。
【００９６】
次に、実施形態４に係るキャッシュ制御装置の動作を、図１０を用いて説明する。図１０は、カウント値保持部１５２の値の変化を示す図である。なお、ウェイ０のカウント値保持部１５２は、メモリ１４２のサイクル数である２０に初期化されるものとする。
【００９７】
まず、図１０に示すサイクルＣ１００１において、例えばメモリ１４０のデータがウェイ１にリフィルされるとすると、ウェイ１のリフィル対象エントリに対応するカウント値保持部１５２の値が、メモリ１４０のサイクル数である３に初期化される。また、同時に、ウェイ０においてそのエントリと同じエントリに対応するカウント値保持部１５２の値が、デクリメントされる。ここでは、デクリメントされて、値が１９になったものとする。
【００９８】
次に、サイクルＣ１００２において、メモリ１４１のデータがウェイ１にリフィルされるとすると、ウェイ１のリフィル対象エントリに対応するカウント値保持部１５２の値が、メモリ１４１のサイクル数である１０に初期化される。また、同時にウェイ０において、そのエントリと同じエントリに対応するカウント値保持部１５２の値が、デクリメントされる。
【００９９】
次に、サイクルＣ１００３で、例えばメモリ１４２にアクセスして、ウェイ０にキャッシュ・ヒットしたとすると、ウェイ０のキャッシュ・ヒットしたエントリに対応したカウント値保持部１５２の値が、サイクル数２０で初期化される。また、同時にウェイ１においてそのエントリと同じエントリに対応するカウント値保持部１５２の値が、デクリメントされる。
【０１００】
なお、該当エントリへのリフィルもヒットもない、サイクルＣ１００１、Ｃ１００２、Ｃ１００３以外のサイクルでは、両ウェイのカウント値保持部１５２の値は保持される。
【０１０１】
なお、本実施形態でも、リプレイス対象エントリ選択時には、実施の形態１に示した場合と同様に、エントリ毎に各ウェイのカウント値保持部１５２の値を比較し、その値が小さい方のエントリを、リプレイス対象エントリとして選択する。
【０１０２】
以上のように、本実施形態では、カウンタ部（ダウンカウンタ４１０）をウェイ毎に１つ備える構成にし、エントリへのリフィル時とヒット時に、リフィル対象ウェイ以外のウェイ、あるいはヒットしたウェイ以外のウェイの、該当エントリと同一エントリに対応したカウント値保持部１５２の値の更新するようにした。それゆえ、各エントリに対応してカウンタ部を設けるよりも回路規模が小さくなる。
【０１０３】
なお、本実施形態は、カウンタ部がダウンカウンタの例を説明したが、カウンタ部をアップカウンタで構成してもよい。
【０１０４】
《発明の実施形態５》
次に、本発明の実施形態５に係るキャッシュ制御装置について説明する。実施形態５に係るキャッシュ制御装置は、図１に示したキャッシュ制御装置１００のウェイ０制御部１５０及びウェイ１制御部１６０のそれぞれを、図１１に示すウェイ制御部５００で置き換えたものである。すなわち、本実施形態でも、ウェイ０制御部とウェイ１制御部は同様の構成をしている。
【０１０５】
ウェイ制御部５００は、ｎ個（ｎは自然数）のエントリに対応したアクセスサイクル数保持部１５１−０〜５，・・・，ｎ−１（ｎ個のアクセスサイクル数保持部）と、充放電部５１０−０〜５，・・・，ｎ−１（ｎ個の充放電部）とを備えている。
【０１０６】
各充放電部５１０は、電荷を蓄積するコンデンサ５１１、コンデンサ５１１を充電するためのスイッチであるスイッチ５１２、及びコンデンサ５１１を放電するためのスイッチであるスイッチ５１３を備えている。充放電部５１０では、このコンデンサ５１１によって、カウント値保持部とダウンカウンタの両方の機能を実現する。
【０１０７】
実施形態５に係るキャッシュ制御装置では、リフィル時とキャッシュ・ヒット時は、メモリアクセスサイクル数の期間だけスイッチ５１２を閉じて、コンデンサ５１１を充電する。
【０１０８】
また、キャッシュ・ミス時は、スイッチ５１３を閉じて、コンデンサ５１１を、抵抗５１４を介して放電する。
【０１０９】
また、リプレイス対象のエントリ選択時は、エントリ毎の各ウェイの電位測定ポイントＰ１（図１１を参照）の電位を測定するとともに、測定した電位を比較し、電位が最小のウェイのエントリをリプレイス対象エントリとして選択する。なお、コンデンサの電位の比較には、電位そのものを比較する方法や、あるいはＡ／Ｄ変換によって電位をデジタル値に変換し、デジタル値を比較する方法などが考えられる。
【０１１０】
これにより、充放電部５１０は、図２に示すカウント値保持部１５２とダウンカウンタ１８０の両方の機能を発揮する。
【０１１１】
本実施形態では、カウント値保持部及びダウンカウンタがコンデンサによって構成されているので、実施形態１のキャッシュ制御装置のように、エントリ毎にカウント値保持部やダウンカウンタを備える場合と比べ、回路面積の削減が図れる。
【０１１２】
なお、本実施形態は、コンデンサ５１１をダウンカウンタとして用いた例を説明したが、コンデンサ５１１をアップカウンタとして用いるように構成してもよい。
【０１１３】
具体的には、リフィル対象エントリへのデータ格納時と、対応するエントリのヒット時は、コンデンサ５１１を放電する。また、キャッシュ・ミス時は、コンデンサ５１１を充電する。また、リプレイス決定部１７０は、エントリ毎の各ウェイの、アクセスサイクル数保持部１５１の値と、電位測定ポイントＰ１の電位から求められる値との差分値を比較し、差分値が最小のウェイのエントリを、リプレイス対象として選択するように構成する。
【０１１４】
なお、上記の各実施形態では、２ウェイ・セット・アソシアティブ構成のキャッシュについての例を説明したが、任意のウェイ数のキャッシュに対して適用してもよい。
【産業上の利用可能性】
【０１１５】
本発明に係るキャッシュ制御装置は、アクセスサイクル数が異なる複数種類のメモリを有するシステムにおいて、ＣＰＵの負荷を増大させることなく、キャッシュ・ミス時の置き換えペナルティを減少させることが可能になるという効果を有し、アクセスサイクル数が異なる複数のメモリをキャッシュの対象とし、複数のウェイを有するキャッシュメモリを制御するキャッシュ制御装置等として有用である。
【図面の簡単な説明】
【０１１６】
【図１】実施形態１に係るキャッシュ制御装置１００の構成を示すブロック図である。
【図２】ウェイ０制御部１５０及びウェイ１制御部１６０のカウンタ部をダウンカウンタ１８０で構成した例を示す図である。
【図３】キャッシュ制御装置１００の動作を説明するフローチャートである。
【図４】アクセスサイクル数の大きなメモリが、アクセスサイクル数の小さなメモリよりも先に、キャッシュにリフィルされた場合のウェイ０及びウェイ１のカウント値保持部１５２の値の変化を示す図である。
【図５】ウェイ１にキャッシュ・ヒットが発生した場合の、ダウンカウンタの動作を例示する図である。
【図６】実施形態２に係るキャッシュ制御装置の一部を抜粋したブロック図である。
【図７】実施形態３に係るウェイ制御部の構成を示すブロック図である。
【図８】実施形態３に係るキャッシュ制御装置における、カウント値保持部１５２の値の変化を示す図である。
【図９】実施形態４に係るウェイ制御部の構成を示すブロック図である。
【図１０】実施形態４に係るキャッシュ制御装置における、カウント値保持部１５２の値の変化を示す図である。
【図１１】実施形態５に係るウェイ制御部の構成を示すブロック図である。
【符号の説明】
【０１１７】
１００      キャッシュ制御装置
１１０      キャッシュメモリ
１２０      置き換えエントリ選択部
１３０      メモリコントローラ
１４０      メモリ
１４１      メモリ
１４２      メモリ
１５０      ウェイ０制御部
１５１      アクセスサイクル数保持部
１５２      カウント値保持部
１５３      カウンタ部
１６０      ウェイ１制御部
１７０      リプレイス決定部
１８０      ダウンカウンタ
１９０      比較器
２１０      ウェイ０制御部
２１１      アップカウンタ
２２０      ウェイ１制御部
２３０      リプレイス決定部
２３１      演算器
２３２      演算器
２３３      比較器
３００      ウェイ制御部
３１０      ダウンカウンタ
３２０      セレクタ
４００      ウェイ制御部
４１０      ダウンカウンタ
４２０      セレクタ
５００      ウェイ制御部
５１０      充放電部
５１１      コンデンサ
５１２      スイッチ
５１３      スイッチ
５１４      抵抗
Ｐ１      電位測定ポイント
【図１】
2008181190.tif 000003
【図２】
2008181190.tif 000004
【図３】
2008181190.tif 000005
【図４】
2008181190.tif 000006
【図５】
2008181190.tif 000007
【図６】
2008181190.tif 000008
【図７】
2008181190.tif 000009
【図８】
2008181190.tif 000010
【図９】
2008181190.tif 000011
【図１０】
2008181190.tif 000012
【図１１】
2008181190.tif 000013