メモリシステム、キャッシュメモリ制御方法及びメモリ制御プログラム
【課題】ストアイン方式のメモリシステムにおいて、アクセス頻度が高いアドレスのリプレース頻度を減らし、メモリシステムの性能悪化を軽減することができるメモリシステムを提供すること
【解決手段】本発明のメモリシステムは、１ｓｔキャッシュメモリ１０と１ｓｔキャッシュメモリ１０に優先してプロセッサからアクセスされる１ｓｔキャッシュメモリ２０と、１ｓｔキャッシュメモリ１０においてキャッシュデータのリプレースを行う場合に、１ｓｔキャッシュメモリ１０に格納されているキャッシュデータのうち、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定し、１ｓｔキャッシュメモリ２０に格納されているキャッシュデータのうちリプレース対象のキャッシュデータと同一のキャッシュデータを無効化するリプレース部４と、を備える。
【解決手段】本発明のメモリシステムは、１ｓｔキャッシュメモリ１０と１ｓｔキャッシュメモリ１０に優先してプロセッサからアクセスされる１ｓｔキャッシュメモリ２０と、１ｓｔキャッシュメモリ１０においてキャッシュデータのリプレースを行う場合に、１ｓｔキャッシュメモリ１０に格納されているキャッシュデータのうち、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定し、１ｓｔキャッシュメモリ２０に格納されているキャッシュデータのうちリプレース対象のキャッシュデータと同一のキャッシュデータを無効化するリプレース部４と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はメモリシステム、キャッシュメモリ制御方法及びメモリ制御プログラムに関し、特に階層化されたキャッシュメモリにより構成されるメモリシステム、そのメモリシステムにおけるキャッシュメモリ制御方法及びそのメモリシステムに用いられるメモリ制御方法に関する。
【背景技術】
【０００２】
一般的に、ＣＰＵ（Central Processing Unit）等のプロセッサの性能と比較して、記憶装置に用いられるメモリの性能が劣ることが知られている。このように、メモリの性能が劣っていることにより、プロセッサの性能を十分に発揮することができないことが問題となっていた。そこで、プロセッサとメモリとの性能差を補うために、キャッシュメモリを用いる構成が用いられている。キャッシュメモリは、メモリ（メインメモリ）よりも記憶容量は小さいが、処理能力が高い。そのため、プロセッサは、キャッシュメモリにアクセスすることにより、処理能力の向上を実現している。
【０００３】
ここで、キャッシュメモリを用いるメモリシステムとして、ストアイン方式の階層キャッシュメモリを持つメモリシステムについて説明する。
【０００４】
ＣＰＵがメインメモリのあるアドレスをリードするとメインメモリからデータが読み出される。さらに、上位キャッシュメモリおよび下位キャッシュメモリへデータが登録される。キャッシュメモリが無効化されるまではＣＰＵが同一アドレスをリードすると上位キャッシュメモリまたは下位キャッシュメモリからキャッシュデータが読み出される。
【０００５】
ＣＰＵがメインメモリのあるアドレスに対してリードを発行し、上位キャッシュメモリにキャッシュデータが登録されていれば、ＣＰＵは、上位キャッシュメモリからキャッシュデータを読み出す。そのため、同一アドレスのキャッシュデータが格納された下位キャッシュメモリのアクセス頻度が下がる。これにより、下位キャッシュメモリにおいて、上位キャッシュメモリに登録されているデータと同一のアドレスのキャッシュデータは、ＬＲＵ（Least Recently Used）方式に従いリプレース対象になりやすい。
【０００６】
ストアイン方式の階層キャッシュメモリをもつメモリシステムでは、キャッシュメモリが無効化されるまでは上位キャッシュメモリと下位キャッシュメモリとメインメモリとでデータが異なる事がある。そのため、キャッシュメモリのリプレースの際にはキャッシュコヒーレンシの保障のため、全キャッシュにおいて、対象となるアドレスのデータを無効化する必要がある。
【０００７】
続いて、図７を用いて一般的に用いられるメモリシステムの構成について説明する。図７は、２ｎｄキャッシュメモリ装置３００の構成とＣＰＵ１００及びＣＰＵ２００と、メインメモリ４００との関係を示している。本図に示したＣＰＵ１００とＣＰＵ２００とは、コア１１０又はコア２１０からメインメモリ４００へのアクセス時間を短縮するために、上位キャッシュ又は下位キャッシュにアクセスを行う。上位キャッシュは、１ｓｔキャッシュメモリ装置１００と１ｓｔキャッシュメモリ装置２００とに相当する。下位キャッシュは、キャッシュタグ部３１０と、キャッシュデータ部３２０とを備えた２ｎｄキャッシュメモリ装置３００に相当する。
【０００８】
ＣＰＵ１００内のコア１１０およびＣＰＵ２００内のコア２１０は、１ｓｔキャッシュメモリ装置１２０および１ｓｔキャッシュメモリ装置２２０に対して、データのリードまたはライトに関するリクエストを発行する。ＣＰＵ１００内のコア１１０およびＣＰＵ２００内のコア２１０は、１ｓｔキャッシュメモリ装置、１ｓｔキャッシュメモリ装置２２０、２ｎｄキャッシュメモリ装置３００またはメインメモリ４００からデータのリード／ライトを行う。
【０００９】
メインメモリ４００は、大容量であってかつアクセス時間が２ｎｄキャッシュタグメモリ３１１および２ｎｄキャッシュデータメモリ３２１より遅いという特性を備えている。また２ｎｄキャッシュメモリ装置３００内の２ｎｄキャッシュタグメモリ３１１および２ｎｄキャッシュデータメモリ３２１は、ＣＰＵ１００内の１ｓｔキャッシュメモリ装置１２０およびＣＰＵ２００内の１ｓｔキャッシュメモリ装置２２０より大容量であってかつアクセス時間が遅いという特性を備えている。
【００１０】
ここで２ｎｄキャッシュメモリ装置３００は、データ格納方式としてセットアソシアティブ方式を採用している。このセットアソシアティブ方式は、図８に示すように２ｎｄキャッシュメモリ（２ｎｄキャッシュタグメモリ３１１および２ｎｄキャッシュデータメモリ３２１を含む、以下にも同様に記載する。）を複数のウェイ（ウェイ０およびウェイ１）に分割し、各ウェイにおける決められたラインにデータを格納する方式である。同図に示した２ｎｄキャッシュタグメモリ３１１においては、例えば、ウェイ０のラインＮにアドレスＡが格納されており、ウェイ１のラインＮにアドレスＢが格納されている。また、２ｎｄキャッシュデータメモリ３２１には、例えばウェイ０のラインにデータＡが格納されており、ウェイ１のラインＮにデータＢが格納されている。２ｎｄキャッシュタグメモリ３１１と２ｎｄキャッシュデータメモリ３２１とは、アドレスＡとデータＡとが、アドレスＢとデータＢとがそれぞれ一対一で対応している。
【００１１】
図７に戻り、２ｎｄキャッシュタグ部３１０は、ＣＰＵ１００およびＣＰＵ２００からのリクエストを受け付ける。また、２ｎｄキャッシュタグ部３１０は、２ｎｄキャッシュタグメモリ３１１とキャッシュヒット判定回路３１２と選択回路３１３とから構成されている。
【００１２】
２ｎｄキャッシュタグメモリ３１１は、２ｎｄキャッシュデータメモリ３２０に格納されているデータに対応するアドレス（タグ）を格納している。キャッシュヒット判定回路３１２は、ＣＰＵ１００およびＣＰＵ２００から出力されるアドレスと２ｎｄキャッシュタグメモリ３１１に格納されているアドレスとを比較し、両者が一致した場合、ヒット判定結果を「キャッシュヒット」とする。「キャッシュヒット」の場合には、当該アドレスに対応するデータが２ｎｄキャッシュデータメモリ３２１に存在する事を意味する。一方、ＣＰＵ１００およびＣＰＵ２００から出力されるアドレスと２ｎｄキャッシュタグメモリ３１１に格納されているアドレスとが不一致である場合、キャッシュヒット判定回路３１２はヒット判定結果を「キャッシュミス」とする。
【００１３】
「キャッシュミス」の場合には、当該アドレスに対応するデータが２ｎｄキャッシュデータメモリ３２１に存在しない事を意味する。「キャッシュミス」の場合には、メインメモリ４００から当該アドレスに対応するデータが読み出され、２ｎｄキャッシュデータメモリ３２１において当該データがリプレースされた後、ＣＰＵ１００およびＣＰＵ２００へ当該アドレスに対応するデータが出力される。
【００１４】
ここで、リプレースする場合には、２ｎｄキャッシュデータメモリ３２１のウェイに格納されているデータを追い出す必要がある。そして、上記ウェイにメインメモリ４００から出力されたデータが格納される。ここで、一般的な２ｎｄキャッシュメモリ装置３００において、複数のウェイの中からリプレース対象のウェイ（以下、リプレースウェイとする）を選択するアルゴリズムとしては、最も使用されていなかったデータが格納されたウェイを選択するというＬＲＵ方式が採用されている。
【００１５】
図７に戻り、キャッシュヒット判定回路３１２は、ヒット判定結果を２ｎｄキャッシュデータメモリ３２１及びリプレース部３３０の２ｎｄＬＲＵメモリ３３１へ通知する。
【００１６】
リプレース部３３０は、ヒット判定結果が「キャッシュミス」である場合に２ｎｄキャッシュデータメモリ３２１においてリプレースすべきウェイを選択する機能を備えている。リプレース部３３０は、２ｎｄＬＲＵメモリ３３１およびリプレースウェイ判定回路３３２から構成されている。２ｎｄＬＲＵメモリ３３１は、一つの入力ポートを備えており、２ｎｄキャッシュデータメモリ３２１においてデータをリプレースする場合に、前述したＬＲＵ方式により選択されたリプレースウェイを表すリプレースウェイ情報を格納している。具体的には、図８に示すように、２ｎｄＬＲＵメモリ３３１にはラインごとにリプレースウェイの番号に対応するリプレースウェイ情報が格納されている。同図ではラインＮに、リプレースウェイがウェイ０であることを示すリプレースウェイ情報が格納されている。つまり、２ｎｄキャッシュデータメモリ３２１のラインＮにおいてはウェイ０に格納されているデータＡが最も使用もしくはアクセスされていないデータである。
【００１７】
図７に戻り、リプレースウェイ判定回路３３２は、２ｎｄキャッシュメモリにおける複数のウェイの中から、リプレースウェイを選択する。リプレースウェイ判定回路３３２は、２ｎｄＬＲＵメモリ３２０を参照してＬＲＵ方式によりリプレースウェイを選択する。リプレースウェイ判定回路３３２は、リプレースウェイを選択した後、リプレース要求を選択回路３１３及び３２２へ発行する。
【００１８】
メインメモリ４００は、ＣＰＵ１００又は２００からリクエストされたアドレスに対応するデータを読み出し、これを２ｎｄキャッシュデータメモリ３２１のリプレースウェイに格納する。このようにして、メモリシステムは、リプレース処理を実行する。
【００１９】
１ｓｔキャッシュメモリ装置１２０および１ｓｔキャッシュメモリ装置２２０についても２ｎｄキャッシュメモリ装置３と同様にキャッシュヒット判定を行い、「キャッシュヒット」したときは１ｓｔキャッシュメモリよりデータが読み出され、「キャッシュミス」したときは２ｎｄキャッシュメモリにリクエストを発行する。
【００２０】
ストアイン方式の階層キャッシュメモリをもつメモリシステムにおいては、コア１１０およびコア２１０からのリード／ライトにより１ｓｔキャッシュまたは２ｎｄキャッシュの内容が変更されても無効化（インバリデート）されるまではメインメモリ４００と１ｓｔキャッシュメモリ装置１２０内のキャッシュメモリおよび１ｓｔキャッシュメモリ装置２２０内のキャッシュメモリおよび２ｎｄキャッシュメモリの内容が異なる場合がある。そしてキャッシュコヒーレンシを保障するためには、１ｓｔキャッシュまたは２ｎｄキャッシュのリプレースの際には、当該アドレスに対応する両キャッシュのキャッシュデータを無効化する必要がある。
【００２１】
リプレース部３３０は、１ｓｔキャッシュメモリ装置１２０および１ｓｔキャッシュメモリ装置２２０に対して当該アドレスに対する無効化要求を発行する。要求を受けたＣＰＵ１００の１ｓｔキャッシュメモリ装置１２０およびＣＰＵ２００の１ｓｔキャッシュメモリ装置２２０は、該当するアドレスのデータを無効化し、リプレース部３３０へ報告する。
【００２２】
次に、コア１１０およびコア２１０から出力されるリクエストに対し、１ｓｔキャッシュメモリ装置１２０、１ｓｔキャッシュメモリ装置２２０及び２ｎｄキャッシュメモリ装置３００の動作について、図９及び図１０を用いて説明する。
【００２３】
ステップ１において、コア１１０がメインメモリ４００のアドレスＡ０に対してリクエストを発行すると１ｓｔキャッシュメモリ装置１２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、１ｓｔキャッシュメモリ装置１２０内のキャッシュデータメモリのウェイ０および２ｎｄキャッシュデータメモリ３２１のウェイ０にデータＡ０が格納される。さらに、１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリおよび２ｎｄＬＲＵメモリ３３１にウェイ１を示す１が格納される。
【００２４】
ステップ２において、コア１１０がメインメモリ４００のアドレスＡ１に対してリクエストを発行すると１ｓｔキャッシュメモリ装置１２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、１ｓｔキャッシュメモリ装置１２０内のキャッシュデータメモリのウェイ１および２ｎｄキャッシュデータメモリ３２１のウェイ１にデータＡ１が格納される。さらに、１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリおよび２ｎｄＬＲＵメモリ３３１にウェイ０を示す０が格納される。
【００２５】
ステップ３、ステップ４及びステップ５において、コア１１０がメインメモリ４００のアドレスＡ０に対してリクエストを発行すると１ｓｔキャッシュメモリ装置１２０において「キャッシュヒット」と判定され、データＡ０を読み出す。さらに、ＬＲＵ方式により１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリに１が格納される。
【００２６】
ステップ６において、コア２１０がメインメモリ４００のアドレスＡ２に対してリクエストを発行すると１ｓｔキャッシュメモリ装置２２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、ＬＲＵ方式により２ｎｄキャッシュデータメモリ３１０のウェイ０よりデータＡ０がリプレースされる。さらに、１ｓｔキャッシュメモリ装置１２０のウェイ０にデータＡ０が格納されているため、キャッシュコヒーレンシ保障のためこのデータを無効化する。さらに、メインメモリ４００より１ｓｔキャッシュメモリ装置２２０のキャッシュデータメモリのウェイ０および２ｎｄキャッシュデータメモリ３２１のウェイ０にデータＡ２が格納される。また、１ｓｔキャッシュメモリ装置２２０内の１ｓｔＬＲＵメモリおよび２ｎｄＬＲＵメモリ３３１に１が格納される。１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリには、０が格納される。
【００２７】
ステップ７において、コア１１０がメインメモリ４００のアドレスＡ０に対してリクエストを発行すると１ｓｔキャッシュメモリ装置１２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、ＬＲＵ方式により２ｎｄキャッシュデータメモリ３１０のウェイ１よりデータＡ１がリプレースされる。さらに、１ｓｔキャッシュメモリ装置１２０のウェイ１にデータＡ１が格納されているためキャッシュコヒーレンシ保障のためこのデータを無効化する。さらに、メインメモリ４００より１ｓｔキャッシュメモリ装置１２０のキャッシュデータメモリのウェイ０および２ｎｄキャッシュデータメモリ３２１のウェイ０にデータＡ０が格納される。また、１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリに１が格納され、２ｎｄＬＲＵメモリ３３１に０が格納される。
【００２８】
ステップ８において、コア２１０がメインメモリ４００のアドレスＡ３に対してリクエストを発行すると１ｓｔキャッシュメモリ装置２２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、ＬＲＵ方式により２ｎｄキャッシュデータメモリ３２１のウェイ０よりデータＡ２がリプレースされる。さらに、１ｓｔキャッシュメモリ装置２２０のウェイ０にデータＡ２が格納されているためキャッシュコヒーレンシ保障のためこのデータを無効化する。さらに、メインメモリ４００より１ｓｔキャッシュメモリ装置２２０のキャッシュデータメモリのウェイ１および２ｎｄキャッシュデータメモリ３２１のウェイ０にデータＡ３が格納される。また、１ｓｔキャッシュメモリ装置２２０内の１ｓｔＬＲＵメモリに０が格納され、２ｎｄＬＲＵメモリ３３１に１が格納される。
【００２９】
ステップ９において、コア１１０がメインメモリ４００のアドレスＡ４に対してリクエストを発行すると１ｓｔキャッシュメモリ装置１２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、ＬＲＵ方式により２ｎｄキャッシュデータメモリ３２１のウェイ１よりデータＡ０がリプレースされる。さらに、１ｓｔキャッシュメモリ装置１２０のウェイ０にデータＡ０が格納されているためキャッシュコヒーレンシ保障のためこのデータを無効化する。さらに、メインメモリ４００より１ｓｔキャッシュメモリ装置１２０のキャッシュデータメモリのウェイ１および２ｎｄキャッシュデータメモリ３２１のウェイ１にデータＡ４が格納される。また、１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリに０が格納され、２ｎｄＬＲＵメモリ３３１に０が格納される。
【先行技術文献】
【特許文献】
【００３０】
【特許文献１】特開２０００−２００２２１号公報
【特許文献２】特開平０６−２６６６２３号公報
【発明の概要】
【発明が解決しようとする課題】
【００３１】
しかし、上述したストアイン方式の階層キャッシュを持つメモリシステムにおいて、アクセス頻度の高いアドレスは常に上位キャッシュメモリにヒットし、下位キャッシュメモリではアクセス頻度が低くなる。そのため、上位キャッシュメモリにおいてアクセス頻度の高いアドレスは、下位キャッシュメモリにおいてＬＲＵ方式によりリプレース対象になりやすい。その結果、リプレース時にコヒーレンシ保障のため上位キャッシュメモリにおけるアドレスも無効化対象となるため、アクセス頻度の高いアドレスにアクセスするために、メインメモリに再度アクセスする必要があり、性能が悪化するという問題がある。
【００３２】
アクセス頻度の高いアドレスに対しリプレースを行わないようにする方法として、特許文献１に記載されているように、キャッシュメモリの中に書き換え不可のエリアを設ける、という方法がある。また、特許文献２にも、追い出し禁止フラグを設けて、追い出し禁止フラグがセットされたブロックは、リプレース対象となっても、リプレースされないように制御される、という内容が開示されている。しかし、常にアクセス頻度の高いアドレスに対しては、上述した方法は有効であるが、処理に応じてアクセス頻度が変わるアドレスに対しては有効ではない。
【００３３】
本発明は、このような課題を解決するためになされたものであり、ストアイン方式の階層キャッシュメモリを持つメモリシステムにおいて、アクセス頻度が高いアドレスのリプレース頻度を減らし、メモリシステムの性能悪化を軽減することができるメモリシステム、キャッシュメモリ制御方法及びメモリ制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３４】
本発明の第１の態様にかかるメモリシステムは、第１のキャッシュメモリと、前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定し、前記第２のキャッシュメモリに格納されているキャッシュデータのうち前記リプレース対象のキャッシュデータと同一のキャッシュデータを無効化するリプレース部と、を備えるものである。
【００３５】
本発明の第２の態様にかかるキャッシュメモリ制御方法は、第１のキャッシュメモリと、前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、を備えるメモリシステムにおけるキャッシュメモリ制御方法であって、前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定し、前記第２のキャッシュメモリに格納されているキャッシュデータのうち、前記第１のキャッシュメモリにおいて決定されたリプレース対象キャッシュデータと同一のキャッシュデータを無効化するものである。
【００３６】
本発明の第３の態様にかかるメモリ制御プログラムは、第１のキャッシュメモリと、前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、を備えるメモリシステムにおけるメモリ制御プログラムであって、前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定するステップと、前記第２のキャッシュメモリに格納されているキャッシュデータのうち、前記第１のキャッシュメモリにおいて決定されたリプレース対象データと同一のデータを無効化するステップと、をコンピュータに実行させるものである。
【発明の効果】
【００３７】
本発明を用いることにより、ストアイン方式の階層キャッシュメモリを持つメモリシステムにおいて、アクセス頻度が高いアドレスのリプレース頻度を減らし、メモリシステムの性能悪化を軽減することができるメモリシステム、キャッシュメモリ制御方法及びメモリ制御プログラムを提供することができる。
【図面の簡単な説明】
【００３８】
【図１】実施の形態１にかかるメモリシステムの構成図である。
【図２】実施の形態１にかかるメモリシステムの構成図である。
【図３】実施の形態１にかかる２ｎｄキャッシュメモリのデータ格納方式を説明する図である。
【図４】実施の形態１にかかるフラグの値と、選択されるリプレースウェイの関係を示す図である。
【図５】実施の形態１にかかるキャッシュメモリへデータが格納される状態を示す図である。
【図６】実施の形態１にかかるキャッシュメモリへデータが格納される状態を示す図である。
【図７】一般的なメモリシステムの構成図である。
【図８】一般的なメモリシステムにおけるデータ格納方式を説明する図である。
【図９】一般的なキャッシュメモリへデータが格納される状態を示す図である。
【図１０】一般的なキャッシュメモリへデータが格納される状態を示す図である。
【発明を実施するための形態】
【００３９】
（実施の形態１）
以下、図面を参照して本発明の実施の形態について説明する。図１を用いて本発明の実施の形態１にかかるメモリシステムの構成例について説明する。図１におけるメモリシステムは、プロセッサ１と、上位キャッシュメモリ２と、下位キャッシュメモリ３と、リプレース部４と、を備えている。
【００４０】
プロセッサ１は、コンピュータもしくは回路等を制御するために用いられ、例えば、ＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）等により構成される。プロセッサ１は、メインメモリ（図示せず）に格納されているデータにアクセスする際に、高速処理を実現するために、処理速度がメインメモリよりも高いキャッシュメモリへアクセスする。
【００４１】
キャッシュメモリは、上位キャッシュメモリ２と下位キャッシュメモリ３とを有しており、階層的に構成されている。プロセッサ１は、優先的に上位キャッシュメモリ２へアクセスし、上位キャッシュメモリ２に必要とするデータが存在しない場合、下位キャッシュメモリ３へアクセスする。上位キャッシュメモリ２及び下位キャッシュメモリ３に、プロセッサ１からのアクセス対象となるデータが存在しない場合、プロセッサ１は、メインメモリからデータを取得する。また、上位キャッシュメモリ２及び下位キャッシュメモリ３は、プロセッサ１がメインメモリから取得したデータを格納（キャッシュ）する。上位キャッシュメモリ２又は下位キャッシュメモリ３は、メインメモリよりも記憶容量が小さい。そのため、メインメモリから新たにデータを取得して格納する場合、上位キャッシュメモリ２又は下位キャッシュメモリ３は、すでに格納しているデータ（キャッシュデータ）を削除して、メインメモリから新たなデータを取得する。キャッシュメモリにおけるこのような動作を、キャッシュデータのリプレースと称する。
【００４２】
下位キャッシュメモリ３においてキャッシュデータのリプレースを行う場合に、リプレース部４は、下位キャッシュメモリ３に格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いてリプレース対象キャッシュデータを決定し、上位キャッシュメモリ２に格納されており、下位キャッシュメモリ３におけるリプレース対象のキャッシュデータと同一のキャッシュデータを無効化する。
【００４３】
リプレース部４は、上位キャッシュメモリ２と下位キャッシュメモリ３とのキャッシュコヒーレンシの保障のため、下位キャッシュメモリ３においてリプレースされたデータと同一のデータを、上位キャッシュメモリ２において無効化する。
【００４４】
以上説明したように、図１におけるメモリシステムを用いることにより、リプレース部４は、下位キャッシュメモリ３に格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定することができる。つまり、過去にリプレース対象となり、再度下位キャッシュメモリ３に格納されているデータは、プロセッサ１からのアクセス頻度が高いため、このようなデータをリプレース対象外、もしくはリプレースする優先順位を下げることにより、上位キャッシュメモリ２においてもキャッシュデータは有効に存在することになる。その結果、アクセス頻度が高いキャッシュデータを、上位キャッシュメモリ２に格納しておくことができるため、プロセッサ１が、メインメモリへアクセスすることによるアクセス性能の低下を防止することができる。
【００４５】
続いて、図２を用いて本発明の実施の形態１にかかるメモリシステムの詳細な構成例について説明する。図２におけるメモリシステムは、ＣＰＵ１０及び２０と、２ｎｄキャッシュメモリ３０と、メインメモリ８０と、を備えている。
【００４６】
ＣＰＵ１０は、コア１１と、１ｓｔキャッシュメモリ１２とを有している。コア１１は、メモリアクセスを発行し、１ｓｔキャッシュメモリ１２へ出力する。１ｓｔキャッシュメモリ１２は、コア１１から受けたメモリアクセスに対応するキャッシュデータが１ｓｔキャッシュメモリ１２に格納されているか判定する。１ｓｔキャッシュメモリ１２は、キャッシュヒットと判定したらキャッシュデータをコア１１に返却する。１ｓｔキャッシュメモリ１２は、キャッシュミスと判定したらメモリアクセスを発行し、２ｎｄキャッシュメモリ３０へ出力する。また、１ｓｔキャッシュメモリ１２は、２ｎｄキャッシュメモリ３０より無効化要求を受け取ったら、対象となるキャッシュデータを無効化する。さらに、１ｓｔキャッシュメモリ１２は、コア１１がアクセスを希望するデータであって、２ｎｄキャッシュメモリ３０から出力されたデータを格納する。
【００４７】
ＣＰＵ２０は、コア２１と、１ｓｔキャッシュメモリ２２とを有している。ＣＰＵ２０における構成は、ＣＰＵ１０と同様であるため、詳細な説明を省略する。
【００４８】
２ｎｄキャッシュメモリ３０は、キャッシュタグ部４０と、キャッシュデータ部５０と、リプレース部６０と、バッファ部７０と、を有している。以下に、それぞれの構成について説明する。
【００４９】
キャッシュタグ部４０は、２ｎｄキャッシュタグメモリ４１と、キャッシュヒット判定回路４２と、選択回路４３とを有している。２ｎｄキャッシュタグメモリ４１は、キャッシュデータ部５０に格納されているデータに対応付けられているタグを格納している。２ｎｄキャッシュタグメモリ４１に格納されているタグは、アドレスと称してもよい。
【００５０】
ここで、２ｎｄキャッシュタグメモリ４１のデータ格納方式について、図３を用いて説明する。２ｎｄキャッシュタグメモリ４１のデータ格納方式には、セットアソシアティブ方式が採用されている。２ｎｄキャッシュタグメモリ４１においては、メモリが複数のウェイに分割される。さらに、それぞれのウェイは、複数のラインに分割される。タグは、それぞれのラインに格納される。図３においては、２ｎｄキャッシュタグメモリ４１は、ウェイ０及びウェイ１に分割されている例を示している。また、ウェイ０のラインＮにアドレスＡが格納されており、ウェイ１のラインＮにアドレスＢが格納されている例を示している。また、それぞれのアドレスには、フラグ（Ｆ）が関連付けられている。フラグは、関連付けられているアドレスが、過去にリプレース対象のアドレスとなっていたかを示している。フラグについては、後に詳述する。
【００５１】
図２に戻り、キャッシュヒット判定回路４２は、ＣＰＵ１０もしくはＣＰＵ２０からメモリアクセスを受け取ると、メモリアクセスに含まれるタグと、２ｎｄキャッシュタグメモリ４１に格納されているタグとを比較する。キャッシュヒット判定回路４２は、メモリアクセスに含まれるタグと、２ｎｄキャッシュタグメモリ４１に格納されているタグとが一致した場合、キャッシュヒットと判定し、メモリアクセスに含まれるタグと、２ｎｄキャッシュタグメモリ４１に格納されているタグとが一致しない場合、キャッシュミスと判定する。
【００５２】
選択回路４３は、リプレース部６０から、リプレースされたキャッシュデータに関する情報を受け取ると、リプレースされたキャッシュデータに対応するタグをバッファ部７０へ出力する。
【００５３】
続いて、キャッシュデータ部５０は、２ｎｄキャッシュデータメモリ５１と、選択回路５２とを有している。２ｎｄキャッシュデータメモリ５１は、２ｎｄキャッシュタグメモリ４１に格納されているタグと対応付けられているキャッシュデータを格納している。２ｎｄキャッシュデータメモリ５１は、キャッシュヒット判定回路４２からキャッシュヒットとの通知を受け取った場合、選択回路５２を介して、該当するキャッシュデータをＣＰＵ１０又は２０へ出力する。
【００５４】
２ｎｄキャッシュデータメモリ５１は、２ｎｄキャッシュタグメモリ４１と同様に、セットアソシアティブ方式が採用されている。図３に示されるように、２ｎｄキャッシュデータメモリ５１は、例えば、ウェイ０のラインＮにデータＡを格納し、ウェイ１のラインＮにデータＢを格納している。データＡは、２ｎｄキャッシュタグメモリ４１のアドレスＡと対応付けられている。データＢは、２ｎｄキャッシュタグメモリ４１のアドレスＢと対応付けられている。
【００５５】
続いて、リプレース部６０は、２ｎｄＬＲＵメモリ６１と、リプレースウェイ判定回路６２とを有している。２ｎｄＬＲＵメモリ６１は、２ｎｄキャッシュデータメモリ５１の各ラインに格納されているウェイ０及びウェイ１のデータのうち、どちらが古いデータかを示している。つまり、２ｎｄＬＲＵメモリ６１は、ウェイ０及びウェイ１のデータのうち、アクセスされたタイミングが古い方を示している。たとえば、２ｎｄＬＲＵメモリ６１のラインＮに、「０」が設定されている場合、データＡは、データＢがアクセスされたタイミングよりも後に、アクセスされていないことを示している。
【００５６】
リプレースウェイ判定回路６２は、２ｎｄキャッシュタグメモリ４１におけるフラグの情報と、２ｎｄＬＲＵメモリ６１が保持する情報とを用いて、リプレース対象となるウェイを判定する。たとえば、２ｎｄキャッシュタグメモリ４１におけるウェイ０及び１のフラグが設定されていない場合、つまり、フラグに「０」が設定されている場合であって、２ｎｄＬＲＵメモリ６１にウェイ０を示す「０」が設定されている場合、リプレース対象となるウェイは、ウェイ０と判定される。また、２ｎｄキャッシュタグメモリ４１において、ウェイ０のフラグに「１」が設定されており、２ｎｄＬＲＵメモリ６１にウェイ０を示す「０」が設定されている場合、アドレスＡにおけるデータのアクセス頻度が高いと考えられるため、２ｎｄＬＲＵメモリ６１の設定にかかわらず、リプレース対象となるウェイは１と判定される。フラグの設定と、２ｎｄＬＲＵメモリ６１の設定とから決定されるリプレース対象ウェイは、図４に示すとおりに決定される。
【００５７】
図４の項番１及び２は、フラグ０及び１に０が設定されているため、リプレース対象となるウェイは、２ｎｄＬＲＵメモリの値に従って決定される。リプレース後は、リプレースされたウェイとは異なるウェイが２ｎｄＬＲＵメモリに設定される。項番３及び４は、ウェイ１のフラグに１が設定されているため、２ｎｄＬＲＵメモリの設定によらず、リプレース対象となるウェイは、ウェイ０となる。項番３において、リプレース後は、ウェイ１のフラグは１に設定されたまま、２ｎｄＬＲＵメモリの値が１に設定される。項番４において、リプレース後は、２ｎｄＬＲＵメモリの値によらずリプレース対象となるウェイが決定されたため、ウェイ１のフラグは０に設定され、さらに２ｎｄＬＲＵメモリは０に設定される。
【００５８】
図４の項番５及び６は、ウェイ０のフラグが１に設定されているため、リプレース対象となるウェイは、２ｎｄＬＲＵメモリの値によらず、ウェイ１となる。項番５において、リプレース後は、２ｎｄＬＲＵメモリの値によらずリプレース対象となるウェイが決定されたため、ウェイ０のフラグは０に設定され、さらに２ｎｄＬＲＵメモリは１に設定される。項番６において、リプレース後は、ウェイ０のフラグは１に設定されたまま、２ｎｄＬＲＵメモリの値が０に設定される。
【００５９】
図４の項番７及び８は、ウェイ０及び１のフラグに１が設定されているため、リプレース対象となるウェイは、２ｎｄＬＲＵメモリに従って決定される。リプレース後は、リプレース対象となったウェイのフラグが０に設定され、２ｎｄＬＲＵメモリは、リプレース対象となったウェイとは異なるウェイが設定される。
【００６０】
図２に戻り、リプレースウェイ判定回路６２は、リプレース対象となったウェイに関する情報を、選択回路４３及び選択回路５２へ出力する。選択回路５２は、リプレース対象となったデータを、２ｎｄキャッシュデータメモリ５１から削除する。
【００６１】
続いて、バッファ部７０は、バッファ７１と、ヒット判定回路７２とを有している。バッファ７１は、選択回路４３から出力されるリプレース対象となったデータのタグ（アドレス）を格納する。
【００６２】
ヒット判定回路７２は、コア１１もしくはコア２１から発行されるメモリアクセスにより、メインメモリ８０から新たに２ｎｄキャッシュメモリ３０に格納されるデータのタグと、バッファ７１に格納されているタグとを比較する。ヒット判定回路７２は、比較した結果を、２ｎｄキャッシュタグメモリ４１へ出力する。新たに２ｎｄキャッシュメモリ３０に格納されるデータのタグと、バッファ７１に格納されているタグとが一致した場合、２ｎｄキャッシュタグメモリ４１は、該当するデータのフラグを「１」にセットする。新たに２ｎｄキャッシュメモリ３０に格納されるデータのタグと、バッファ７１に格納されているタグとが一致しない場合、２ｎｄキャッシュタグメモリ４１は、該当するデータのフラグを「０」にセットする。
【００６３】
続いて、図５及び図６を用いて本発明の実施の形態１にかかる１ｓｔキャッシュメモリ１２及び２２と、２ｎｄキャッシュタグメモリ４１とにデータを格納する動作について説明する。
【００６４】
はじめに、ステップ１の動作を説明する。コア１１は、１ｓｔキャッシュメモリ１２へアドレスＡ０に対するリードリクエストを発行する。アドレスＡ０へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ０へのリードリクエストを発行する。アドレスＡ０へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０に対して、アドレスＡ０へのリードリクエストを発行する。
【００６５】
メインメモリ８０は、アドレスＡ０に格納されたデータＡ０を２ｎｄキャッシュメモリ３０に返却する。つまり、メインメモリ８０は、アドレスＡ０に格納されたデータＡ０を２ｎｄキャッシュメモリ３０へ出力する。２ｎｄキャッシュメモリ３０に返却されたアドレスＡ０とデータＡ０とは、それぞれラインＮのウェイ０の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。さらに、２ｎｄＬＲＵメモリ６１のラインＮには１が格納される。また、２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ０とデータＡ０をＣＰＵ１０の１ｓｔキャッシュメモリ１２へ出力する。１ｓｔキャッシュメモリ１２は、２ｎｄキャッシュメモリ３０と同様に、１ｓｔキャッシュタグメモリ（図示せず）と１ｓｔキャッシュデータメモリ（図示せず）のラインＮのウェイ０にそれぞれアドレスＡ０とデータＡ０を格納する。さらに、１ｓｔキャッシュメモリ１２は、コア１１へデータＡ０を出力し、１ｓｔＬＲＵメモリ（図示せず）のラインＮに１が格納される。
【００６６】
次に、ステップ２の動作を説明する。コア１１は１ｓｔキャッシュメモリ１２へアドレスＡ１に対するリードリクエストを発行する。アドレスＡ１へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ１へのリードリクエストを発行する。アドレスＡ１へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０にアドレスＡ１へのリードリクエストを発行する。
【００６７】
メインメモリ８０は、アドレスＡ１に格納されたデータＡ１を２ｎｄキャッシュメモリ３０に返却する。２ｎｄキャッシュメモリ３０に返却されたアドレスＡ１とデータＡ１とは、それぞれラインＮのウェイ１の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。さらに、２ｎｄＬＲＵメモリ６１のラインＮに、０が格納される。また、２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ１とデータＡ１をＣＰＵ１０の１ｓｔキャッシュメモリ１２へ出力する。１ｓｔキャッシュメモリ１２は、１ｓｔキャッシュタグメモリと１ｓｔキャッシュデータメモリのラインＮのウェイ１にそれぞれアドレスＡ１とデータＡ１を格納する。さらに、１ｓｔキャッシュメモリ１２は、コア１１にデータＡ１を送出し１ｓｔＬＲＵメモリのラインＮに０が格納される。
【００６８】
次に、ステップ３、ステップ４及びステップ５の動作を説明する。コア１１は、１ｓｔキャッシュメモリ１２へアドレスＡ０に対するリードリクエストを発行する。アドレスＡ０へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュヒットと判定すると、１ｓｔキャッシュデータメモリのラインＮのウェイ０からデータＡ０を読み出しコア１１へ出力する。また、１ｓｔＬＲＵメモリのラインＮに１が格納される。２ｎｄキャッシュメモリ３０には、リードリクエストは、発行されない。
【００６９】
次に、ステップ６の動作を説明する。コア２１は、１ｓｔキャッシュメモリ２２へアドレスＡ２に対するリードリクエストを発行する。アドレスＡ２へのリードリクエストを受けた１ｓｔキャッシュメモリ２２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ２へのリードリクエストを発行する。アドレスＡ２へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０にアドレスＡ２へのリードリクエストを発行する。
【００７０】
メインメモリ８０は、アドレスＡ２に格納されたデータＡ２を２ｎｄキャッシュメモリ３０に返却する。２ｎｄキャッシュメモリ３０がアドレスＡ２とデータＡ２を受け付けると、リプレース部６０は、２ｎｄＬＲＵメモリ６１のラインＮに格納された値を読み出し、リプレースウェイ判定回路６２へ出力する。リプレースウェイ判定回路６２は、リプレースするウェイを０と決定する。リプレースウェイ判定回路６２は、決定した情報を、選択回路４３および選択回路５２へ出力する。
【００７１】
選択回路４３は、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ０からアドレスＡ０のリプレースを実行する。リプレースされたアドレスＡ０は、バッファ７１のエントリ０に格納される。選択回路５２は、２ｎｄキャッシュデータメモリ５１のラインＮのウェイ０からのデータＡ０のリプレースを実行する。リプレースが発生したため、リプレース部６０は、ＣＰＵ１０およびＣＰＵ２０に対してリプレースされたデータＡ０の無効化リクエストを発行する。１ｓｔキャッシュメモリ１２は、１ｓｔキャッシュメモリに格納されているデータＡ０の無効化を行いリプレース部６０へ報告する。１ｓｔキャッシュメモリ２２は、対象となるデータがないので完了報告のみをリプレース部６０に通知する。
【００７２】
リプレース及び無効化が完了した後、メインメモリ８０から返却されたアドレスＡ２とデータＡ２は、それぞれラインＮのウェイ０の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。さらに、２ｎｄＬＲＵメモリ６１のラインＮに１が、格納される。また２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ２とデータＡ２とをＣＰＵ２０の１ｓｔキャッシュメモリ２２へ出力する。１ｓｔキャッシュメモリ２２は、１ｓｔキャッシュタグメモリと１ｓｔキャッシュデータメモリのラインＮのウェイ０とにそれぞれアドレスＡ２とデータＡ２を格納する。さらに１ｓｔキャッシュメモリ２２は、コア２１にデータＡ２を出力する。１ｓｔＬＲＵメモリのラインＮには、１が格納される。
【００７３】
次に、ステップ７の動作を説明する。コア１１は、１ｓｔキャッシュメモリ１２へアドレスＡ０に対するリードリクエストを発行する。アドレスＡ０へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ０へのリードリクエストを発行する。アドレスＡ０へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０にアドレスＡ０へのリードリクエストを発行する。
【００７４】
メインメモリ８０は、アドレスＡ０に格納されたデータＡ０を２ｎｄキャッシュメモリ３０に返却する。２ｎｄキャッシュメモリ３０がアドレスＡ０とデータＡ０を受け付けると、リプレース部６０は、２ｎｄＬＲＵメモリ６１のラインＮに格納された値を読み出しリプレースウェイ判定回路６２へ出力する。リプレースウェイ判定回路６２は、リプレースするウェイを１と決定する。リプレースウェイ判定回路６２は、決定した情報を選択回路４３および選択回路５２へ出力する。
【００７５】
選択回路４３は、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ１からアドレスＡ１のリプレースを実行する。リプレースされたアドレスＡ１は、バッファ７１のエントリ１に格納される。選択回路５２は、２ｎｄキャッシュデータメモリ５１のラインＮのウェイ１からデータＡ１のリプレースを実行する。リプレースが発生したのでリプレース部６０は、ＣＰＵ１０およびＣＰＵ２０にリプレースされたデータＡ１の無効化リクエストを発行する。１ｓｔキャッシュメモリ１２は、格納しているデータＡ１の無効化を行いリプレース部３２１に報告する。１ｓｔキャッシュメモリ２２は、対象となるデータがないので完了報告のみリプレース部６０へ通知する。
【００７６】
リプレース及び無効化が完了したら、メインメモリ８０から返却されたアドレスＡ０とデータＡ０は、それぞれラインＮのウェイ１の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。また、２ｎｄＬＲＵメモリ６１のラインＮに０が格納される。さらに、ヒット判定回路７２は、２ｎｄキャッシュタグメモリ４１に新たに格納したアドレスＡ０とバッファ７１に格納されているアドレスとを比較する。ヒット判定回路７２は、新たに格納したアドレスＡ０と、バッファ７１のエントリ０のアドレスとが一致するため、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ１に対応するフラグに１を格納する。また２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ０とデータＡ０とをＣＰＵ１０の１ｓｔキャッシュメモリ１２へ出力する。１ｓｔキャッシュメモリ１２は、１ｓｔキャッシュタグメモリと１ｓｔキャッシュデータメモリとのラインＮのウェイ０にそれぞれアドレスＡ０とデータＡ０を格納する。さらに、１ｓｔキャッシュメモリ１２は、コア１１にデータＡ０を送出する。１ｓｔＬＲＵメモリのラインＮには、１が格納される。
【００７７】
次に、ステップ８の動作を説明する。コア２１は、１ｓｔキャッシュメモリ１２へアドレスＡ３に対するリードリクエストを発行する。アドレスＡ３へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ３へのリードリクエストを発行する。アドレスＡ３へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０にアドレスＡ３へのリードリクエストを発行する。
【００７８】
メインメモリ８０は、アドレスＡ３に格納されたデータＡ３を２ｎｄキャッシュメモリ３０に返却する。２ｎｄキャッシュメモリ３０がアドレスＡ３とデータＡ３を受け付けると、リプレース部６０は、２ｎｄＬＲＵメモリ６１のラインＮに格納された値を読み出しリプレースウェイ判定回路６２へ出力する。リプレースウェイ判定回路６２は、リプレースするウェイを０と決定し選択回路４３および選択回路５２へ出力する。
【００７９】
選択回路４３は、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ０からアドレスＡ２のリプレースを実行する。リプレースされたアドレスＡ２は、バッファ７１のエントリ２に格納される。選択回路５２は、２ｎｄキャッシュデータメモリ５１のラインＮのウェイ０からデータＡ２のリプレースを実行する。リプレースが発生したため、リプレース部６０は、ＣＰＵ１０およびＣＰＵ２０に対して、リプレースされたデータＡ２の無効化リクエストを発行する。１ｓｔキャッシュメモリ１２は、対象となるデータがないので完了報告のみリプレース部６０へ通知する。１ｓｔキャッシュメモリ２２は、格納しているデータＡ２の無効化を行いリプレース部６０に報告する。
【００８０】
リプレース及び無効化が完了した後、メインメモリ８０から出力されたアドレスＡ３とデータＡ３は、それぞれラインＮのウェイ０の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。２ｎｄＬＲＵメモリ３２０のラインＮには、１が格納される。また２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ３とデータＡ３をＣＰＵ２０の１ｓｔキャッシュメモリ２２へ出力する。１ｓｔキャッシュメモリ２２は、１ｓｔキャッシュタグメモリと１ｓｔキャッシュデータメモリとのラインＮのウェイ１にそれぞれアドレスＡ３とデータＡ３とを格納する。さらに、１ｓｔキャッシュメモリ２２は、コア２１にデータＡ３を出力し１ｓｔＬＲＵメモリのラインＮに０を格納する。
【００８１】
次に、ステップ９の動作を説明する。コア１１は、１ｓｔキャッシュメモリ１２へアドレスＡ４に対するリードリクエストを発行する。アドレスＡ４へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ４へのリードリクエストを発行する。アドレスＡ４へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０にアドレスＡ４へのリードリクエストを発行する。
【００８２】
メインメモリ８０は、アドレスＡ４に格納されたデータＡ４を２ｎｄキャッシュメモリ３０に返却する。２ｎｄキャッシュメモリ装置３０がアドレスＡ３とデータＡ３を受け付けると、リプレース部６０は、２ｎｄＬＲＵメモリ６１のラインＮに格納された値を読み出しリプレースウェイ判定回路６２へ出力する。リプレースウェイ判定回路６２は、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ１のフラグが１になっていて、２ｎｄＬＲＵメモリ６１のラインＮのウェイ１が１になっているため図４の項番４に従い、リプレースするウェイを０と決定する。リプレースウェイ判定回路６２は、決定した情報を選択回路４３および選択回路５２へ出力する。
【００８３】
選択回路４３は、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ０からアドレスＡ３のリプレースを実行する。リプレースされたアドレスＡ３は、バッファ７１のエントリ３に格納される。選択回路３１１は、２ｎｄキャッシュデータメモリ５２のラインＮのウェイ０からデータＡ３のリプレースを実行する。リプレースが発生したため、リプレース部６０は、ＣＰＵ１０およびＣＰＵ２０にリプレースされたデータＡ３の無効化リクエストを発行する。１ｓｔキャッシュメモリ１２は、対象となるデータがないため完了報告のみリプレース部６０へ通知する。１ｓｔキャッシュメモリ１２は、１ｓｔキャッシュメモリの無効化を行いリプレース部６０に報告する。
【００８４】
リプレース及び無効化が完了したら、メインメモリ８０から出力されたアドレスＡ４とデータＡ４とは、それぞれラインＮのウェイ０の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。２ｎｄＬＲＵメモリ３２０のラインＮには０が格納される。さらに、図４の項番４に従い、２ｎｄキャッシュタグメモリ３００のラインＮのウェイ１に対応するフラグに０を格納する。また２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ４とデータＡ４とをＣＰＵ１０の１ｓｔキャッシュメモリ１２へ出力する。１ｓｔキャッシュメモリ１２は、１ｓｔキャッシュタグメモリと１ｓｔキャッシュデータメモリのラインＮのウェイ１にそれぞれアドレスＡ４とデータＡ４を格納する。さらに、１ｓｔキャッシュメモリ１２は、コア１１にデータＡ４を送出し１ｓｔＬＲＵメモリのラインＮに０を格納する。
【００８５】
以上説明したように、本発明の実施の形態１にかかるメモリシステムを用いることにより、２ｎｄキャッシュメモリにおいてリプレース対象となるウェイを決定する際に、ウェイに格納されているデータが、過去にリプレース対象となったデータであるか否かを考慮して、リプレース対象となるウェイを決定することができる。過去にリプレースされて、再度２ｎｄキャッシュメモリに登録されているデータのアクセス頻度は高いと考えられるため、このようなデータが再度リプレース対象となることを防止することができる。これより、アクセス頻度の高いデータがリプレース対象となる頻度を低下させることができる。
【００８６】
上述の実施の形態では、本発明をハードウェアの構成として説明したが、本発明は、これに限定されるものではない。本発明は、図５及び図６において説明した１ｓｔキャッシュメモリ１２及び２２と、２ｎｄキャッシュタグメモリ４１とにデータを格納する処理及び１ｓｔキャッシュメモリ１２及び２２のデータを無効化する処理を、ＣＰＵ（Central Processing Unit）にコンピュータプログラムを実行させることにより実現することも可能である。
【００８７】
上述の例において、プログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ−ＲＯＭ（Read Only Memory）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Programmable ROM）、ＥＰＲＯＭ（Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ（Random Access Memory））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【００８８】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。例えば、上述した例においては、１ｓｔキャッシュメモリがＣＰＵに備えられている構成例について説明したが、１ｓｔキャッシュメモリは、ＣＰＵの外部に備えられてもよい。また、図４において、フラグとの関係においてリプレース対象となるウェイを決定するパターンについて説明したが、異なるパターンを設定してもよい。
【符号の説明】
【００８９】
１ プロセッサ
２ 上位キャッシュメモリ
３ 下位キャッシュメモリ
４ リプレース部
１０ ＣＰＵ
１１ コア
１２ １ｓｔキャッシュメモリ
２０ ＣＰＵ
２１ コア
２２ １ｓｔキャッシュメモリ
３０ ２ｎｄキャッシュメモリ
４０ キャッシュタグ部
４１ ２ｎｄキャッシュタグメモリ
４２ キャッシュヒット判定回路
４３ 選択回路
５０ キャッシュデータ部
５１ ２ｎｄキャッシュデータメモリ
５２ 選択回路
６０ リプレース部
６１ ２ｎｄＬＲＵメモリ
６２ リプレースウェイ判定回路
７０ バッファ部
７１ バッファ
７２ ヒット判定回路
８０ メインメモリ
【技術分野】
【０００１】
本発明はメモリシステム、キャッシュメモリ制御方法及びメモリ制御プログラムに関し、特に階層化されたキャッシュメモリにより構成されるメモリシステム、そのメモリシステムにおけるキャッシュメモリ制御方法及びそのメモリシステムに用いられるメモリ制御方法に関する。
【背景技術】
【０００２】
一般的に、ＣＰＵ（Central Processing Unit）等のプロセッサの性能と比較して、記憶装置に用いられるメモリの性能が劣ることが知られている。このように、メモリの性能が劣っていることにより、プロセッサの性能を十分に発揮することができないことが問題となっていた。そこで、プロセッサとメモリとの性能差を補うために、キャッシュメモリを用いる構成が用いられている。キャッシュメモリは、メモリ（メインメモリ）よりも記憶容量は小さいが、処理能力が高い。そのため、プロセッサは、キャッシュメモリにアクセスすることにより、処理能力の向上を実現している。
【０００３】
ここで、キャッシュメモリを用いるメモリシステムとして、ストアイン方式の階層キャッシュメモリを持つメモリシステムについて説明する。
【０００４】
ＣＰＵがメインメモリのあるアドレスをリードするとメインメモリからデータが読み出される。さらに、上位キャッシュメモリおよび下位キャッシュメモリへデータが登録される。キャッシュメモリが無効化されるまではＣＰＵが同一アドレスをリードすると上位キャッシュメモリまたは下位キャッシュメモリからキャッシュデータが読み出される。
【０００５】
ＣＰＵがメインメモリのあるアドレスに対してリードを発行し、上位キャッシュメモリにキャッシュデータが登録されていれば、ＣＰＵは、上位キャッシュメモリからキャッシュデータを読み出す。そのため、同一アドレスのキャッシュデータが格納された下位キャッシュメモリのアクセス頻度が下がる。これにより、下位キャッシュメモリにおいて、上位キャッシュメモリに登録されているデータと同一のアドレスのキャッシュデータは、ＬＲＵ（Least Recently Used）方式に従いリプレース対象になりやすい。
【０００６】
ストアイン方式の階層キャッシュメモリをもつメモリシステムでは、キャッシュメモリが無効化されるまでは上位キャッシュメモリと下位キャッシュメモリとメインメモリとでデータが異なる事がある。そのため、キャッシュメモリのリプレースの際にはキャッシュコヒーレンシの保障のため、全キャッシュにおいて、対象となるアドレスのデータを無効化する必要がある。
【０００７】
続いて、図７を用いて一般的に用いられるメモリシステムの構成について説明する。図７は、２ｎｄキャッシュメモリ装置３００の構成とＣＰＵ１００及びＣＰＵ２００と、メインメモリ４００との関係を示している。本図に示したＣＰＵ１００とＣＰＵ２００とは、コア１１０又はコア２１０からメインメモリ４００へのアクセス時間を短縮するために、上位キャッシュ又は下位キャッシュにアクセスを行う。上位キャッシュは、１ｓｔキャッシュメモリ装置１００と１ｓｔキャッシュメモリ装置２００とに相当する。下位キャッシュは、キャッシュタグ部３１０と、キャッシュデータ部３２０とを備えた２ｎｄキャッシュメモリ装置３００に相当する。
【０００８】
ＣＰＵ１００内のコア１１０およびＣＰＵ２００内のコア２１０は、１ｓｔキャッシュメモリ装置１２０および１ｓｔキャッシュメモリ装置２２０に対して、データのリードまたはライトに関するリクエストを発行する。ＣＰＵ１００内のコア１１０およびＣＰＵ２００内のコア２１０は、１ｓｔキャッシュメモリ装置、１ｓｔキャッシュメモリ装置２２０、２ｎｄキャッシュメモリ装置３００またはメインメモリ４００からデータのリード／ライトを行う。
【０００９】
メインメモリ４００は、大容量であってかつアクセス時間が２ｎｄキャッシュタグメモリ３１１および２ｎｄキャッシュデータメモリ３２１より遅いという特性を備えている。また２ｎｄキャッシュメモリ装置３００内の２ｎｄキャッシュタグメモリ３１１および２ｎｄキャッシュデータメモリ３２１は、ＣＰＵ１００内の１ｓｔキャッシュメモリ装置１２０およびＣＰＵ２００内の１ｓｔキャッシュメモリ装置２２０より大容量であってかつアクセス時間が遅いという特性を備えている。
【００１０】
ここで２ｎｄキャッシュメモリ装置３００は、データ格納方式としてセットアソシアティブ方式を採用している。このセットアソシアティブ方式は、図８に示すように２ｎｄキャッシュメモリ（２ｎｄキャッシュタグメモリ３１１および２ｎｄキャッシュデータメモリ３２１を含む、以下にも同様に記載する。）を複数のウェイ（ウェイ０およびウェイ１）に分割し、各ウェイにおける決められたラインにデータを格納する方式である。同図に示した２ｎｄキャッシュタグメモリ３１１においては、例えば、ウェイ０のラインＮにアドレスＡが格納されており、ウェイ１のラインＮにアドレスＢが格納されている。また、２ｎｄキャッシュデータメモリ３２１には、例えばウェイ０のラインにデータＡが格納されており、ウェイ１のラインＮにデータＢが格納されている。２ｎｄキャッシュタグメモリ３１１と２ｎｄキャッシュデータメモリ３２１とは、アドレスＡとデータＡとが、アドレスＢとデータＢとがそれぞれ一対一で対応している。
【００１１】
図７に戻り、２ｎｄキャッシュタグ部３１０は、ＣＰＵ１００およびＣＰＵ２００からのリクエストを受け付ける。また、２ｎｄキャッシュタグ部３１０は、２ｎｄキャッシュタグメモリ３１１とキャッシュヒット判定回路３１２と選択回路３１３とから構成されている。
【００１２】
２ｎｄキャッシュタグメモリ３１１は、２ｎｄキャッシュデータメモリ３２０に格納されているデータに対応するアドレス（タグ）を格納している。キャッシュヒット判定回路３１２は、ＣＰＵ１００およびＣＰＵ２００から出力されるアドレスと２ｎｄキャッシュタグメモリ３１１に格納されているアドレスとを比較し、両者が一致した場合、ヒット判定結果を「キャッシュヒット」とする。「キャッシュヒット」の場合には、当該アドレスに対応するデータが２ｎｄキャッシュデータメモリ３２１に存在する事を意味する。一方、ＣＰＵ１００およびＣＰＵ２００から出力されるアドレスと２ｎｄキャッシュタグメモリ３１１に格納されているアドレスとが不一致である場合、キャッシュヒット判定回路３１２はヒット判定結果を「キャッシュミス」とする。
【００１３】
「キャッシュミス」の場合には、当該アドレスに対応するデータが２ｎｄキャッシュデータメモリ３２１に存在しない事を意味する。「キャッシュミス」の場合には、メインメモリ４００から当該アドレスに対応するデータが読み出され、２ｎｄキャッシュデータメモリ３２１において当該データがリプレースされた後、ＣＰＵ１００およびＣＰＵ２００へ当該アドレスに対応するデータが出力される。
【００１４】
ここで、リプレースする場合には、２ｎｄキャッシュデータメモリ３２１のウェイに格納されているデータを追い出す必要がある。そして、上記ウェイにメインメモリ４００から出力されたデータが格納される。ここで、一般的な２ｎｄキャッシュメモリ装置３００において、複数のウェイの中からリプレース対象のウェイ（以下、リプレースウェイとする）を選択するアルゴリズムとしては、最も使用されていなかったデータが格納されたウェイを選択するというＬＲＵ方式が採用されている。
【００１５】
図７に戻り、キャッシュヒット判定回路３１２は、ヒット判定結果を２ｎｄキャッシュデータメモリ３２１及びリプレース部３３０の２ｎｄＬＲＵメモリ３３１へ通知する。
【００１６】
リプレース部３３０は、ヒット判定結果が「キャッシュミス」である場合に２ｎｄキャッシュデータメモリ３２１においてリプレースすべきウェイを選択する機能を備えている。リプレース部３３０は、２ｎｄＬＲＵメモリ３３１およびリプレースウェイ判定回路３３２から構成されている。２ｎｄＬＲＵメモリ３３１は、一つの入力ポートを備えており、２ｎｄキャッシュデータメモリ３２１においてデータをリプレースする場合に、前述したＬＲＵ方式により選択されたリプレースウェイを表すリプレースウェイ情報を格納している。具体的には、図８に示すように、２ｎｄＬＲＵメモリ３３１にはラインごとにリプレースウェイの番号に対応するリプレースウェイ情報が格納されている。同図ではラインＮに、リプレースウェイがウェイ０であることを示すリプレースウェイ情報が格納されている。つまり、２ｎｄキャッシュデータメモリ３２１のラインＮにおいてはウェイ０に格納されているデータＡが最も使用もしくはアクセスされていないデータである。
【００１７】
図７に戻り、リプレースウェイ判定回路３３２は、２ｎｄキャッシュメモリにおける複数のウェイの中から、リプレースウェイを選択する。リプレースウェイ判定回路３３２は、２ｎｄＬＲＵメモリ３２０を参照してＬＲＵ方式によりリプレースウェイを選択する。リプレースウェイ判定回路３３２は、リプレースウェイを選択した後、リプレース要求を選択回路３１３及び３２２へ発行する。
【００１８】
メインメモリ４００は、ＣＰＵ１００又は２００からリクエストされたアドレスに対応するデータを読み出し、これを２ｎｄキャッシュデータメモリ３２１のリプレースウェイに格納する。このようにして、メモリシステムは、リプレース処理を実行する。
【００１９】
１ｓｔキャッシュメモリ装置１２０および１ｓｔキャッシュメモリ装置２２０についても２ｎｄキャッシュメモリ装置３と同様にキャッシュヒット判定を行い、「キャッシュヒット」したときは１ｓｔキャッシュメモリよりデータが読み出され、「キャッシュミス」したときは２ｎｄキャッシュメモリにリクエストを発行する。
【００２０】
ストアイン方式の階層キャッシュメモリをもつメモリシステムにおいては、コア１１０およびコア２１０からのリード／ライトにより１ｓｔキャッシュまたは２ｎｄキャッシュの内容が変更されても無効化（インバリデート）されるまではメインメモリ４００と１ｓｔキャッシュメモリ装置１２０内のキャッシュメモリおよび１ｓｔキャッシュメモリ装置２２０内のキャッシュメモリおよび２ｎｄキャッシュメモリの内容が異なる場合がある。そしてキャッシュコヒーレンシを保障するためには、１ｓｔキャッシュまたは２ｎｄキャッシュのリプレースの際には、当該アドレスに対応する両キャッシュのキャッシュデータを無効化する必要がある。
【００２１】
リプレース部３３０は、１ｓｔキャッシュメモリ装置１２０および１ｓｔキャッシュメモリ装置２２０に対して当該アドレスに対する無効化要求を発行する。要求を受けたＣＰＵ１００の１ｓｔキャッシュメモリ装置１２０およびＣＰＵ２００の１ｓｔキャッシュメモリ装置２２０は、該当するアドレスのデータを無効化し、リプレース部３３０へ報告する。
【００２２】
次に、コア１１０およびコア２１０から出力されるリクエストに対し、１ｓｔキャッシュメモリ装置１２０、１ｓｔキャッシュメモリ装置２２０及び２ｎｄキャッシュメモリ装置３００の動作について、図９及び図１０を用いて説明する。
【００２３】
ステップ１において、コア１１０がメインメモリ４００のアドレスＡ０に対してリクエストを発行すると１ｓｔキャッシュメモリ装置１２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、１ｓｔキャッシュメモリ装置１２０内のキャッシュデータメモリのウェイ０および２ｎｄキャッシュデータメモリ３２１のウェイ０にデータＡ０が格納される。さらに、１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリおよび２ｎｄＬＲＵメモリ３３１にウェイ１を示す１が格納される。
【００２４】
ステップ２において、コア１１０がメインメモリ４００のアドレスＡ１に対してリクエストを発行すると１ｓｔキャッシュメモリ装置１２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、１ｓｔキャッシュメモリ装置１２０内のキャッシュデータメモリのウェイ１および２ｎｄキャッシュデータメモリ３２１のウェイ１にデータＡ１が格納される。さらに、１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリおよび２ｎｄＬＲＵメモリ３３１にウェイ０を示す０が格納される。
【００２５】
ステップ３、ステップ４及びステップ５において、コア１１０がメインメモリ４００のアドレスＡ０に対してリクエストを発行すると１ｓｔキャッシュメモリ装置１２０において「キャッシュヒット」と判定され、データＡ０を読み出す。さらに、ＬＲＵ方式により１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリに１が格納される。
【００２６】
ステップ６において、コア２１０がメインメモリ４００のアドレスＡ２に対してリクエストを発行すると１ｓｔキャッシュメモリ装置２２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、ＬＲＵ方式により２ｎｄキャッシュデータメモリ３１０のウェイ０よりデータＡ０がリプレースされる。さらに、１ｓｔキャッシュメモリ装置１２０のウェイ０にデータＡ０が格納されているため、キャッシュコヒーレンシ保障のためこのデータを無効化する。さらに、メインメモリ４００より１ｓｔキャッシュメモリ装置２２０のキャッシュデータメモリのウェイ０および２ｎｄキャッシュデータメモリ３２１のウェイ０にデータＡ２が格納される。また、１ｓｔキャッシュメモリ装置２２０内の１ｓｔＬＲＵメモリおよび２ｎｄＬＲＵメモリ３３１に１が格納される。１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリには、０が格納される。
【００２７】
ステップ７において、コア１１０がメインメモリ４００のアドレスＡ０に対してリクエストを発行すると１ｓｔキャッシュメモリ装置１２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、ＬＲＵ方式により２ｎｄキャッシュデータメモリ３１０のウェイ１よりデータＡ１がリプレースされる。さらに、１ｓｔキャッシュメモリ装置１２０のウェイ１にデータＡ１が格納されているためキャッシュコヒーレンシ保障のためこのデータを無効化する。さらに、メインメモリ４００より１ｓｔキャッシュメモリ装置１２０のキャッシュデータメモリのウェイ０および２ｎｄキャッシュデータメモリ３２１のウェイ０にデータＡ０が格納される。また、１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリに１が格納され、２ｎｄＬＲＵメモリ３３１に０が格納される。
【００２８】
ステップ８において、コア２１０がメインメモリ４００のアドレスＡ３に対してリクエストを発行すると１ｓｔキャッシュメモリ装置２２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、ＬＲＵ方式により２ｎｄキャッシュデータメモリ３２１のウェイ０よりデータＡ２がリプレースされる。さらに、１ｓｔキャッシュメモリ装置２２０のウェイ０にデータＡ２が格納されているためキャッシュコヒーレンシ保障のためこのデータを無効化する。さらに、メインメモリ４００より１ｓｔキャッシュメモリ装置２２０のキャッシュデータメモリのウェイ１および２ｎｄキャッシュデータメモリ３２１のウェイ０にデータＡ３が格納される。また、１ｓｔキャッシュメモリ装置２２０内の１ｓｔＬＲＵメモリに０が格納され、２ｎｄＬＲＵメモリ３３１に１が格納される。
【００２９】
ステップ９において、コア１１０がメインメモリ４００のアドレスＡ４に対してリクエストを発行すると１ｓｔキャッシュメモリ装置１２０および２ｎｄキャッシュメモリ装置３００において「キャッシュミス」と判定される。そのため、ＬＲＵ方式により２ｎｄキャッシュデータメモリ３２１のウェイ１よりデータＡ０がリプレースされる。さらに、１ｓｔキャッシュメモリ装置１２０のウェイ０にデータＡ０が格納されているためキャッシュコヒーレンシ保障のためこのデータを無効化する。さらに、メインメモリ４００より１ｓｔキャッシュメモリ装置１２０のキャッシュデータメモリのウェイ１および２ｎｄキャッシュデータメモリ３２１のウェイ１にデータＡ４が格納される。また、１ｓｔキャッシュメモリ装置１２０内の１ｓｔＬＲＵメモリに０が格納され、２ｎｄＬＲＵメモリ３３１に０が格納される。
【先行技術文献】
【特許文献】
【００３０】
【特許文献１】特開２０００−２００２２１号公報
【特許文献２】特開平０６−２６６６２３号公報
【発明の概要】
【発明が解決しようとする課題】
【００３１】
しかし、上述したストアイン方式の階層キャッシュを持つメモリシステムにおいて、アクセス頻度の高いアドレスは常に上位キャッシュメモリにヒットし、下位キャッシュメモリではアクセス頻度が低くなる。そのため、上位キャッシュメモリにおいてアクセス頻度の高いアドレスは、下位キャッシュメモリにおいてＬＲＵ方式によりリプレース対象になりやすい。その結果、リプレース時にコヒーレンシ保障のため上位キャッシュメモリにおけるアドレスも無効化対象となるため、アクセス頻度の高いアドレスにアクセスするために、メインメモリに再度アクセスする必要があり、性能が悪化するという問題がある。
【００３２】
アクセス頻度の高いアドレスに対しリプレースを行わないようにする方法として、特許文献１に記載されているように、キャッシュメモリの中に書き換え不可のエリアを設ける、という方法がある。また、特許文献２にも、追い出し禁止フラグを設けて、追い出し禁止フラグがセットされたブロックは、リプレース対象となっても、リプレースされないように制御される、という内容が開示されている。しかし、常にアクセス頻度の高いアドレスに対しては、上述した方法は有効であるが、処理に応じてアクセス頻度が変わるアドレスに対しては有効ではない。
【００３３】
本発明は、このような課題を解決するためになされたものであり、ストアイン方式の階層キャッシュメモリを持つメモリシステムにおいて、アクセス頻度が高いアドレスのリプレース頻度を減らし、メモリシステムの性能悪化を軽減することができるメモリシステム、キャッシュメモリ制御方法及びメモリ制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３４】
本発明の第１の態様にかかるメモリシステムは、第１のキャッシュメモリと、前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定し、前記第２のキャッシュメモリに格納されているキャッシュデータのうち前記リプレース対象のキャッシュデータと同一のキャッシュデータを無効化するリプレース部と、を備えるものである。
【００３５】
本発明の第２の態様にかかるキャッシュメモリ制御方法は、第１のキャッシュメモリと、前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、を備えるメモリシステムにおけるキャッシュメモリ制御方法であって、前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定し、前記第２のキャッシュメモリに格納されているキャッシュデータのうち、前記第１のキャッシュメモリにおいて決定されたリプレース対象キャッシュデータと同一のキャッシュデータを無効化するものである。
【００３６】
本発明の第３の態様にかかるメモリ制御プログラムは、第１のキャッシュメモリと、前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、を備えるメモリシステムにおけるメモリ制御プログラムであって、前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定するステップと、前記第２のキャッシュメモリに格納されているキャッシュデータのうち、前記第１のキャッシュメモリにおいて決定されたリプレース対象データと同一のデータを無効化するステップと、をコンピュータに実行させるものである。
【発明の効果】
【００３７】
本発明を用いることにより、ストアイン方式の階層キャッシュメモリを持つメモリシステムにおいて、アクセス頻度が高いアドレスのリプレース頻度を減らし、メモリシステムの性能悪化を軽減することができるメモリシステム、キャッシュメモリ制御方法及びメモリ制御プログラムを提供することができる。
【図面の簡単な説明】
【００３８】
【図１】実施の形態１にかかるメモリシステムの構成図である。
【図２】実施の形態１にかかるメモリシステムの構成図である。
【図３】実施の形態１にかかる２ｎｄキャッシュメモリのデータ格納方式を説明する図である。
【図４】実施の形態１にかかるフラグの値と、選択されるリプレースウェイの関係を示す図である。
【図５】実施の形態１にかかるキャッシュメモリへデータが格納される状態を示す図である。
【図６】実施の形態１にかかるキャッシュメモリへデータが格納される状態を示す図である。
【図７】一般的なメモリシステムの構成図である。
【図８】一般的なメモリシステムにおけるデータ格納方式を説明する図である。
【図９】一般的なキャッシュメモリへデータが格納される状態を示す図である。
【図１０】一般的なキャッシュメモリへデータが格納される状態を示す図である。
【発明を実施するための形態】
【００３９】
（実施の形態１）
以下、図面を参照して本発明の実施の形態について説明する。図１を用いて本発明の実施の形態１にかかるメモリシステムの構成例について説明する。図１におけるメモリシステムは、プロセッサ１と、上位キャッシュメモリ２と、下位キャッシュメモリ３と、リプレース部４と、を備えている。
【００４０】
プロセッサ１は、コンピュータもしくは回路等を制御するために用いられ、例えば、ＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）等により構成される。プロセッサ１は、メインメモリ（図示せず）に格納されているデータにアクセスする際に、高速処理を実現するために、処理速度がメインメモリよりも高いキャッシュメモリへアクセスする。
【００４１】
キャッシュメモリは、上位キャッシュメモリ２と下位キャッシュメモリ３とを有しており、階層的に構成されている。プロセッサ１は、優先的に上位キャッシュメモリ２へアクセスし、上位キャッシュメモリ２に必要とするデータが存在しない場合、下位キャッシュメモリ３へアクセスする。上位キャッシュメモリ２及び下位キャッシュメモリ３に、プロセッサ１からのアクセス対象となるデータが存在しない場合、プロセッサ１は、メインメモリからデータを取得する。また、上位キャッシュメモリ２及び下位キャッシュメモリ３は、プロセッサ１がメインメモリから取得したデータを格納（キャッシュ）する。上位キャッシュメモリ２又は下位キャッシュメモリ３は、メインメモリよりも記憶容量が小さい。そのため、メインメモリから新たにデータを取得して格納する場合、上位キャッシュメモリ２又は下位キャッシュメモリ３は、すでに格納しているデータ（キャッシュデータ）を削除して、メインメモリから新たなデータを取得する。キャッシュメモリにおけるこのような動作を、キャッシュデータのリプレースと称する。
【００４２】
下位キャッシュメモリ３においてキャッシュデータのリプレースを行う場合に、リプレース部４は、下位キャッシュメモリ３に格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いてリプレース対象キャッシュデータを決定し、上位キャッシュメモリ２に格納されており、下位キャッシュメモリ３におけるリプレース対象のキャッシュデータと同一のキャッシュデータを無効化する。
【００４３】
リプレース部４は、上位キャッシュメモリ２と下位キャッシュメモリ３とのキャッシュコヒーレンシの保障のため、下位キャッシュメモリ３においてリプレースされたデータと同一のデータを、上位キャッシュメモリ２において無効化する。
【００４４】
以上説明したように、図１におけるメモリシステムを用いることにより、リプレース部４は、下位キャッシュメモリ３に格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定することができる。つまり、過去にリプレース対象となり、再度下位キャッシュメモリ３に格納されているデータは、プロセッサ１からのアクセス頻度が高いため、このようなデータをリプレース対象外、もしくはリプレースする優先順位を下げることにより、上位キャッシュメモリ２においてもキャッシュデータは有効に存在することになる。その結果、アクセス頻度が高いキャッシュデータを、上位キャッシュメモリ２に格納しておくことができるため、プロセッサ１が、メインメモリへアクセスすることによるアクセス性能の低下を防止することができる。
【００４５】
続いて、図２を用いて本発明の実施の形態１にかかるメモリシステムの詳細な構成例について説明する。図２におけるメモリシステムは、ＣＰＵ１０及び２０と、２ｎｄキャッシュメモリ３０と、メインメモリ８０と、を備えている。
【００４６】
ＣＰＵ１０は、コア１１と、１ｓｔキャッシュメモリ１２とを有している。コア１１は、メモリアクセスを発行し、１ｓｔキャッシュメモリ１２へ出力する。１ｓｔキャッシュメモリ１２は、コア１１から受けたメモリアクセスに対応するキャッシュデータが１ｓｔキャッシュメモリ１２に格納されているか判定する。１ｓｔキャッシュメモリ１２は、キャッシュヒットと判定したらキャッシュデータをコア１１に返却する。１ｓｔキャッシュメモリ１２は、キャッシュミスと判定したらメモリアクセスを発行し、２ｎｄキャッシュメモリ３０へ出力する。また、１ｓｔキャッシュメモリ１２は、２ｎｄキャッシュメモリ３０より無効化要求を受け取ったら、対象となるキャッシュデータを無効化する。さらに、１ｓｔキャッシュメモリ１２は、コア１１がアクセスを希望するデータであって、２ｎｄキャッシュメモリ３０から出力されたデータを格納する。
【００４７】
ＣＰＵ２０は、コア２１と、１ｓｔキャッシュメモリ２２とを有している。ＣＰＵ２０における構成は、ＣＰＵ１０と同様であるため、詳細な説明を省略する。
【００４８】
２ｎｄキャッシュメモリ３０は、キャッシュタグ部４０と、キャッシュデータ部５０と、リプレース部６０と、バッファ部７０と、を有している。以下に、それぞれの構成について説明する。
【００４９】
キャッシュタグ部４０は、２ｎｄキャッシュタグメモリ４１と、キャッシュヒット判定回路４２と、選択回路４３とを有している。２ｎｄキャッシュタグメモリ４１は、キャッシュデータ部５０に格納されているデータに対応付けられているタグを格納している。２ｎｄキャッシュタグメモリ４１に格納されているタグは、アドレスと称してもよい。
【００５０】
ここで、２ｎｄキャッシュタグメモリ４１のデータ格納方式について、図３を用いて説明する。２ｎｄキャッシュタグメモリ４１のデータ格納方式には、セットアソシアティブ方式が採用されている。２ｎｄキャッシュタグメモリ４１においては、メモリが複数のウェイに分割される。さらに、それぞれのウェイは、複数のラインに分割される。タグは、それぞれのラインに格納される。図３においては、２ｎｄキャッシュタグメモリ４１は、ウェイ０及びウェイ１に分割されている例を示している。また、ウェイ０のラインＮにアドレスＡが格納されており、ウェイ１のラインＮにアドレスＢが格納されている例を示している。また、それぞれのアドレスには、フラグ（Ｆ）が関連付けられている。フラグは、関連付けられているアドレスが、過去にリプレース対象のアドレスとなっていたかを示している。フラグについては、後に詳述する。
【００５１】
図２に戻り、キャッシュヒット判定回路４２は、ＣＰＵ１０もしくはＣＰＵ２０からメモリアクセスを受け取ると、メモリアクセスに含まれるタグと、２ｎｄキャッシュタグメモリ４１に格納されているタグとを比較する。キャッシュヒット判定回路４２は、メモリアクセスに含まれるタグと、２ｎｄキャッシュタグメモリ４１に格納されているタグとが一致した場合、キャッシュヒットと判定し、メモリアクセスに含まれるタグと、２ｎｄキャッシュタグメモリ４１に格納されているタグとが一致しない場合、キャッシュミスと判定する。
【００５２】
選択回路４３は、リプレース部６０から、リプレースされたキャッシュデータに関する情報を受け取ると、リプレースされたキャッシュデータに対応するタグをバッファ部７０へ出力する。
【００５３】
続いて、キャッシュデータ部５０は、２ｎｄキャッシュデータメモリ５１と、選択回路５２とを有している。２ｎｄキャッシュデータメモリ５１は、２ｎｄキャッシュタグメモリ４１に格納されているタグと対応付けられているキャッシュデータを格納している。２ｎｄキャッシュデータメモリ５１は、キャッシュヒット判定回路４２からキャッシュヒットとの通知を受け取った場合、選択回路５２を介して、該当するキャッシュデータをＣＰＵ１０又は２０へ出力する。
【００５４】
２ｎｄキャッシュデータメモリ５１は、２ｎｄキャッシュタグメモリ４１と同様に、セットアソシアティブ方式が採用されている。図３に示されるように、２ｎｄキャッシュデータメモリ５１は、例えば、ウェイ０のラインＮにデータＡを格納し、ウェイ１のラインＮにデータＢを格納している。データＡは、２ｎｄキャッシュタグメモリ４１のアドレスＡと対応付けられている。データＢは、２ｎｄキャッシュタグメモリ４１のアドレスＢと対応付けられている。
【００５５】
続いて、リプレース部６０は、２ｎｄＬＲＵメモリ６１と、リプレースウェイ判定回路６２とを有している。２ｎｄＬＲＵメモリ６１は、２ｎｄキャッシュデータメモリ５１の各ラインに格納されているウェイ０及びウェイ１のデータのうち、どちらが古いデータかを示している。つまり、２ｎｄＬＲＵメモリ６１は、ウェイ０及びウェイ１のデータのうち、アクセスされたタイミングが古い方を示している。たとえば、２ｎｄＬＲＵメモリ６１のラインＮに、「０」が設定されている場合、データＡは、データＢがアクセスされたタイミングよりも後に、アクセスされていないことを示している。
【００５６】
リプレースウェイ判定回路６２は、２ｎｄキャッシュタグメモリ４１におけるフラグの情報と、２ｎｄＬＲＵメモリ６１が保持する情報とを用いて、リプレース対象となるウェイを判定する。たとえば、２ｎｄキャッシュタグメモリ４１におけるウェイ０及び１のフラグが設定されていない場合、つまり、フラグに「０」が設定されている場合であって、２ｎｄＬＲＵメモリ６１にウェイ０を示す「０」が設定されている場合、リプレース対象となるウェイは、ウェイ０と判定される。また、２ｎｄキャッシュタグメモリ４１において、ウェイ０のフラグに「１」が設定されており、２ｎｄＬＲＵメモリ６１にウェイ０を示す「０」が設定されている場合、アドレスＡにおけるデータのアクセス頻度が高いと考えられるため、２ｎｄＬＲＵメモリ６１の設定にかかわらず、リプレース対象となるウェイは１と判定される。フラグの設定と、２ｎｄＬＲＵメモリ６１の設定とから決定されるリプレース対象ウェイは、図４に示すとおりに決定される。
【００５７】
図４の項番１及び２は、フラグ０及び１に０が設定されているため、リプレース対象となるウェイは、２ｎｄＬＲＵメモリの値に従って決定される。リプレース後は、リプレースされたウェイとは異なるウェイが２ｎｄＬＲＵメモリに設定される。項番３及び４は、ウェイ１のフラグに１が設定されているため、２ｎｄＬＲＵメモリの設定によらず、リプレース対象となるウェイは、ウェイ０となる。項番３において、リプレース後は、ウェイ１のフラグは１に設定されたまま、２ｎｄＬＲＵメモリの値が１に設定される。項番４において、リプレース後は、２ｎｄＬＲＵメモリの値によらずリプレース対象となるウェイが決定されたため、ウェイ１のフラグは０に設定され、さらに２ｎｄＬＲＵメモリは０に設定される。
【００５８】
図４の項番５及び６は、ウェイ０のフラグが１に設定されているため、リプレース対象となるウェイは、２ｎｄＬＲＵメモリの値によらず、ウェイ１となる。項番５において、リプレース後は、２ｎｄＬＲＵメモリの値によらずリプレース対象となるウェイが決定されたため、ウェイ０のフラグは０に設定され、さらに２ｎｄＬＲＵメモリは１に設定される。項番６において、リプレース後は、ウェイ０のフラグは１に設定されたまま、２ｎｄＬＲＵメモリの値が０に設定される。
【００５９】
図４の項番７及び８は、ウェイ０及び１のフラグに１が設定されているため、リプレース対象となるウェイは、２ｎｄＬＲＵメモリに従って決定される。リプレース後は、リプレース対象となったウェイのフラグが０に設定され、２ｎｄＬＲＵメモリは、リプレース対象となったウェイとは異なるウェイが設定される。
【００６０】
図２に戻り、リプレースウェイ判定回路６２は、リプレース対象となったウェイに関する情報を、選択回路４３及び選択回路５２へ出力する。選択回路５２は、リプレース対象となったデータを、２ｎｄキャッシュデータメモリ５１から削除する。
【００６１】
続いて、バッファ部７０は、バッファ７１と、ヒット判定回路７２とを有している。バッファ７１は、選択回路４３から出力されるリプレース対象となったデータのタグ（アドレス）を格納する。
【００６２】
ヒット判定回路７２は、コア１１もしくはコア２１から発行されるメモリアクセスにより、メインメモリ８０から新たに２ｎｄキャッシュメモリ３０に格納されるデータのタグと、バッファ７１に格納されているタグとを比較する。ヒット判定回路７２は、比較した結果を、２ｎｄキャッシュタグメモリ４１へ出力する。新たに２ｎｄキャッシュメモリ３０に格納されるデータのタグと、バッファ７１に格納されているタグとが一致した場合、２ｎｄキャッシュタグメモリ４１は、該当するデータのフラグを「１」にセットする。新たに２ｎｄキャッシュメモリ３０に格納されるデータのタグと、バッファ７１に格納されているタグとが一致しない場合、２ｎｄキャッシュタグメモリ４１は、該当するデータのフラグを「０」にセットする。
【００６３】
続いて、図５及び図６を用いて本発明の実施の形態１にかかる１ｓｔキャッシュメモリ１２及び２２と、２ｎｄキャッシュタグメモリ４１とにデータを格納する動作について説明する。
【００６４】
はじめに、ステップ１の動作を説明する。コア１１は、１ｓｔキャッシュメモリ１２へアドレスＡ０に対するリードリクエストを発行する。アドレスＡ０へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ０へのリードリクエストを発行する。アドレスＡ０へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０に対して、アドレスＡ０へのリードリクエストを発行する。
【００６５】
メインメモリ８０は、アドレスＡ０に格納されたデータＡ０を２ｎｄキャッシュメモリ３０に返却する。つまり、メインメモリ８０は、アドレスＡ０に格納されたデータＡ０を２ｎｄキャッシュメモリ３０へ出力する。２ｎｄキャッシュメモリ３０に返却されたアドレスＡ０とデータＡ０とは、それぞれラインＮのウェイ０の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。さらに、２ｎｄＬＲＵメモリ６１のラインＮには１が格納される。また、２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ０とデータＡ０をＣＰＵ１０の１ｓｔキャッシュメモリ１２へ出力する。１ｓｔキャッシュメモリ１２は、２ｎｄキャッシュメモリ３０と同様に、１ｓｔキャッシュタグメモリ（図示せず）と１ｓｔキャッシュデータメモリ（図示せず）のラインＮのウェイ０にそれぞれアドレスＡ０とデータＡ０を格納する。さらに、１ｓｔキャッシュメモリ１２は、コア１１へデータＡ０を出力し、１ｓｔＬＲＵメモリ（図示せず）のラインＮに１が格納される。
【００６６】
次に、ステップ２の動作を説明する。コア１１は１ｓｔキャッシュメモリ１２へアドレスＡ１に対するリードリクエストを発行する。アドレスＡ１へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ１へのリードリクエストを発行する。アドレスＡ１へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０にアドレスＡ１へのリードリクエストを発行する。
【００６７】
メインメモリ８０は、アドレスＡ１に格納されたデータＡ１を２ｎｄキャッシュメモリ３０に返却する。２ｎｄキャッシュメモリ３０に返却されたアドレスＡ１とデータＡ１とは、それぞれラインＮのウェイ１の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。さらに、２ｎｄＬＲＵメモリ６１のラインＮに、０が格納される。また、２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ１とデータＡ１をＣＰＵ１０の１ｓｔキャッシュメモリ１２へ出力する。１ｓｔキャッシュメモリ１２は、１ｓｔキャッシュタグメモリと１ｓｔキャッシュデータメモリのラインＮのウェイ１にそれぞれアドレスＡ１とデータＡ１を格納する。さらに、１ｓｔキャッシュメモリ１２は、コア１１にデータＡ１を送出し１ｓｔＬＲＵメモリのラインＮに０が格納される。
【００６８】
次に、ステップ３、ステップ４及びステップ５の動作を説明する。コア１１は、１ｓｔキャッシュメモリ１２へアドレスＡ０に対するリードリクエストを発行する。アドレスＡ０へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュヒットと判定すると、１ｓｔキャッシュデータメモリのラインＮのウェイ０からデータＡ０を読み出しコア１１へ出力する。また、１ｓｔＬＲＵメモリのラインＮに１が格納される。２ｎｄキャッシュメモリ３０には、リードリクエストは、発行されない。
【００６９】
次に、ステップ６の動作を説明する。コア２１は、１ｓｔキャッシュメモリ２２へアドレスＡ２に対するリードリクエストを発行する。アドレスＡ２へのリードリクエストを受けた１ｓｔキャッシュメモリ２２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ２へのリードリクエストを発行する。アドレスＡ２へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０にアドレスＡ２へのリードリクエストを発行する。
【００７０】
メインメモリ８０は、アドレスＡ２に格納されたデータＡ２を２ｎｄキャッシュメモリ３０に返却する。２ｎｄキャッシュメモリ３０がアドレスＡ２とデータＡ２を受け付けると、リプレース部６０は、２ｎｄＬＲＵメモリ６１のラインＮに格納された値を読み出し、リプレースウェイ判定回路６２へ出力する。リプレースウェイ判定回路６２は、リプレースするウェイを０と決定する。リプレースウェイ判定回路６２は、決定した情報を、選択回路４３および選択回路５２へ出力する。
【００７１】
選択回路４３は、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ０からアドレスＡ０のリプレースを実行する。リプレースされたアドレスＡ０は、バッファ７１のエントリ０に格納される。選択回路５２は、２ｎｄキャッシュデータメモリ５１のラインＮのウェイ０からのデータＡ０のリプレースを実行する。リプレースが発生したため、リプレース部６０は、ＣＰＵ１０およびＣＰＵ２０に対してリプレースされたデータＡ０の無効化リクエストを発行する。１ｓｔキャッシュメモリ１２は、１ｓｔキャッシュメモリに格納されているデータＡ０の無効化を行いリプレース部６０へ報告する。１ｓｔキャッシュメモリ２２は、対象となるデータがないので完了報告のみをリプレース部６０に通知する。
【００７２】
リプレース及び無効化が完了した後、メインメモリ８０から返却されたアドレスＡ２とデータＡ２は、それぞれラインＮのウェイ０の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。さらに、２ｎｄＬＲＵメモリ６１のラインＮに１が、格納される。また２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ２とデータＡ２とをＣＰＵ２０の１ｓｔキャッシュメモリ２２へ出力する。１ｓｔキャッシュメモリ２２は、１ｓｔキャッシュタグメモリと１ｓｔキャッシュデータメモリのラインＮのウェイ０とにそれぞれアドレスＡ２とデータＡ２を格納する。さらに１ｓｔキャッシュメモリ２２は、コア２１にデータＡ２を出力する。１ｓｔＬＲＵメモリのラインＮには、１が格納される。
【００７３】
次に、ステップ７の動作を説明する。コア１１は、１ｓｔキャッシュメモリ１２へアドレスＡ０に対するリードリクエストを発行する。アドレスＡ０へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ０へのリードリクエストを発行する。アドレスＡ０へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０にアドレスＡ０へのリードリクエストを発行する。
【００７４】
メインメモリ８０は、アドレスＡ０に格納されたデータＡ０を２ｎｄキャッシュメモリ３０に返却する。２ｎｄキャッシュメモリ３０がアドレスＡ０とデータＡ０を受け付けると、リプレース部６０は、２ｎｄＬＲＵメモリ６１のラインＮに格納された値を読み出しリプレースウェイ判定回路６２へ出力する。リプレースウェイ判定回路６２は、リプレースするウェイを１と決定する。リプレースウェイ判定回路６２は、決定した情報を選択回路４３および選択回路５２へ出力する。
【００７５】
選択回路４３は、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ１からアドレスＡ１のリプレースを実行する。リプレースされたアドレスＡ１は、バッファ７１のエントリ１に格納される。選択回路５２は、２ｎｄキャッシュデータメモリ５１のラインＮのウェイ１からデータＡ１のリプレースを実行する。リプレースが発生したのでリプレース部６０は、ＣＰＵ１０およびＣＰＵ２０にリプレースされたデータＡ１の無効化リクエストを発行する。１ｓｔキャッシュメモリ１２は、格納しているデータＡ１の無効化を行いリプレース部３２１に報告する。１ｓｔキャッシュメモリ２２は、対象となるデータがないので完了報告のみリプレース部６０へ通知する。
【００７６】
リプレース及び無効化が完了したら、メインメモリ８０から返却されたアドレスＡ０とデータＡ０は、それぞれラインＮのウェイ１の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。また、２ｎｄＬＲＵメモリ６１のラインＮに０が格納される。さらに、ヒット判定回路７２は、２ｎｄキャッシュタグメモリ４１に新たに格納したアドレスＡ０とバッファ７１に格納されているアドレスとを比較する。ヒット判定回路７２は、新たに格納したアドレスＡ０と、バッファ７１のエントリ０のアドレスとが一致するため、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ１に対応するフラグに１を格納する。また２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ０とデータＡ０とをＣＰＵ１０の１ｓｔキャッシュメモリ１２へ出力する。１ｓｔキャッシュメモリ１２は、１ｓｔキャッシュタグメモリと１ｓｔキャッシュデータメモリとのラインＮのウェイ０にそれぞれアドレスＡ０とデータＡ０を格納する。さらに、１ｓｔキャッシュメモリ１２は、コア１１にデータＡ０を送出する。１ｓｔＬＲＵメモリのラインＮには、１が格納される。
【００７７】
次に、ステップ８の動作を説明する。コア２１は、１ｓｔキャッシュメモリ１２へアドレスＡ３に対するリードリクエストを発行する。アドレスＡ３へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ３へのリードリクエストを発行する。アドレスＡ３へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０にアドレスＡ３へのリードリクエストを発行する。
【００７８】
メインメモリ８０は、アドレスＡ３に格納されたデータＡ３を２ｎｄキャッシュメモリ３０に返却する。２ｎｄキャッシュメモリ３０がアドレスＡ３とデータＡ３を受け付けると、リプレース部６０は、２ｎｄＬＲＵメモリ６１のラインＮに格納された値を読み出しリプレースウェイ判定回路６２へ出力する。リプレースウェイ判定回路６２は、リプレースするウェイを０と決定し選択回路４３および選択回路５２へ出力する。
【００７９】
選択回路４３は、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ０からアドレスＡ２のリプレースを実行する。リプレースされたアドレスＡ２は、バッファ７１のエントリ２に格納される。選択回路５２は、２ｎｄキャッシュデータメモリ５１のラインＮのウェイ０からデータＡ２のリプレースを実行する。リプレースが発生したため、リプレース部６０は、ＣＰＵ１０およびＣＰＵ２０に対して、リプレースされたデータＡ２の無効化リクエストを発行する。１ｓｔキャッシュメモリ１２は、対象となるデータがないので完了報告のみリプレース部６０へ通知する。１ｓｔキャッシュメモリ２２は、格納しているデータＡ２の無効化を行いリプレース部６０に報告する。
【００８０】
リプレース及び無効化が完了した後、メインメモリ８０から出力されたアドレスＡ３とデータＡ３は、それぞれラインＮのウェイ０の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。２ｎｄＬＲＵメモリ３２０のラインＮには、１が格納される。また２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ３とデータＡ３をＣＰＵ２０の１ｓｔキャッシュメモリ２２へ出力する。１ｓｔキャッシュメモリ２２は、１ｓｔキャッシュタグメモリと１ｓｔキャッシュデータメモリとのラインＮのウェイ１にそれぞれアドレスＡ３とデータＡ３とを格納する。さらに、１ｓｔキャッシュメモリ２２は、コア２１にデータＡ３を出力し１ｓｔＬＲＵメモリのラインＮに０を格納する。
【００８１】
次に、ステップ９の動作を説明する。コア１１は、１ｓｔキャッシュメモリ１２へアドレスＡ４に対するリードリクエストを発行する。アドレスＡ４へのリードリクエストを受けた１ｓｔキャッシュメモリ１２は、キャッシュミスと判定すると２ｎｄキャッシュメモリ３０にアドレスＡ４へのリードリクエストを発行する。アドレスＡ４へのリードリクエストを受けた２ｎｄキャッシュメモリ３０は、キャッシュミスと判定するとメインメモリ８０にアドレスＡ４へのリードリクエストを発行する。
【００８２】
メインメモリ８０は、アドレスＡ４に格納されたデータＡ４を２ｎｄキャッシュメモリ３０に返却する。２ｎｄキャッシュメモリ装置３０がアドレスＡ３とデータＡ３を受け付けると、リプレース部６０は、２ｎｄＬＲＵメモリ６１のラインＮに格納された値を読み出しリプレースウェイ判定回路６２へ出力する。リプレースウェイ判定回路６２は、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ１のフラグが１になっていて、２ｎｄＬＲＵメモリ６１のラインＮのウェイ１が１になっているため図４の項番４に従い、リプレースするウェイを０と決定する。リプレースウェイ判定回路６２は、決定した情報を選択回路４３および選択回路５２へ出力する。
【００８３】
選択回路４３は、２ｎｄキャッシュタグメモリ４１のラインＮのウェイ０からアドレスＡ３のリプレースを実行する。リプレースされたアドレスＡ３は、バッファ７１のエントリ３に格納される。選択回路３１１は、２ｎｄキャッシュデータメモリ５２のラインＮのウェイ０からデータＡ３のリプレースを実行する。リプレースが発生したため、リプレース部６０は、ＣＰＵ１０およびＣＰＵ２０にリプレースされたデータＡ３の無効化リクエストを発行する。１ｓｔキャッシュメモリ１２は、対象となるデータがないため完了報告のみリプレース部６０へ通知する。１ｓｔキャッシュメモリ１２は、１ｓｔキャッシュメモリの無効化を行いリプレース部６０に報告する。
【００８４】
リプレース及び無効化が完了したら、メインメモリ８０から出力されたアドレスＡ４とデータＡ４とは、それぞれラインＮのウェイ０の２ｎｄキャッシュタグメモリ４１および２ｎｄキャッシュデータメモリ５１に格納される。２ｎｄＬＲＵメモリ３２０のラインＮには０が格納される。さらに、図４の項番４に従い、２ｎｄキャッシュタグメモリ３００のラインＮのウェイ１に対応するフラグに０を格納する。また２ｎｄキャッシュメモリ３０は、返却されたアドレスＡ４とデータＡ４とをＣＰＵ１０の１ｓｔキャッシュメモリ１２へ出力する。１ｓｔキャッシュメモリ１２は、１ｓｔキャッシュタグメモリと１ｓｔキャッシュデータメモリのラインＮのウェイ１にそれぞれアドレスＡ４とデータＡ４を格納する。さらに、１ｓｔキャッシュメモリ１２は、コア１１にデータＡ４を送出し１ｓｔＬＲＵメモリのラインＮに０を格納する。
【００８５】
以上説明したように、本発明の実施の形態１にかかるメモリシステムを用いることにより、２ｎｄキャッシュメモリにおいてリプレース対象となるウェイを決定する際に、ウェイに格納されているデータが、過去にリプレース対象となったデータであるか否かを考慮して、リプレース対象となるウェイを決定することができる。過去にリプレースされて、再度２ｎｄキャッシュメモリに登録されているデータのアクセス頻度は高いと考えられるため、このようなデータが再度リプレース対象となることを防止することができる。これより、アクセス頻度の高いデータがリプレース対象となる頻度を低下させることができる。
【００８６】
上述の実施の形態では、本発明をハードウェアの構成として説明したが、本発明は、これに限定されるものではない。本発明は、図５及び図６において説明した１ｓｔキャッシュメモリ１２及び２２と、２ｎｄキャッシュタグメモリ４１とにデータを格納する処理及び１ｓｔキャッシュメモリ１２及び２２のデータを無効化する処理を、ＣＰＵ（Central Processing Unit）にコンピュータプログラムを実行させることにより実現することも可能である。
【００８７】
上述の例において、プログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ−ＲＯＭ（Read Only Memory）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Programmable ROM）、ＥＰＲＯＭ（Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ（Random Access Memory））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【００８８】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。例えば、上述した例においては、１ｓｔキャッシュメモリがＣＰＵに備えられている構成例について説明したが、１ｓｔキャッシュメモリは、ＣＰＵの外部に備えられてもよい。また、図４において、フラグとの関係においてリプレース対象となるウェイを決定するパターンについて説明したが、異なるパターンを設定してもよい。
【符号の説明】
【００８９】
１ プロセッサ
２ 上位キャッシュメモリ
３ 下位キャッシュメモリ
４ リプレース部
１０ ＣＰＵ
１１ コア
１２ １ｓｔキャッシュメモリ
２０ ＣＰＵ
２１ コア
２２ １ｓｔキャッシュメモリ
３０ ２ｎｄキャッシュメモリ
４０ キャッシュタグ部
４１ ２ｎｄキャッシュタグメモリ
４２ キャッシュヒット判定回路
４３ 選択回路
５０ キャッシュデータ部
５１ ２ｎｄキャッシュデータメモリ
５２ 選択回路
６０ リプレース部
６１ ２ｎｄＬＲＵメモリ
６２ リプレースウェイ判定回路
７０ バッファ部
７１ バッファ
７２ ヒット判定回路
８０ メインメモリ
【特許請求の範囲】
【請求項１】
第１のキャッシュメモリと、
前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定し、前記第２のキャッシュメモリに格納されているキャッシュデータのうち前記リプレース対象のキャッシュデータと同一のキャッシュデータを無効化するリプレース部と、を備えるメモリシステム。
【請求項２】
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースが行われた場合に、前記リプレースされたキャッシュデータに関連付けられているアドレスを格納するバッファをさらに備え、
前記リプレース部は、
前記第１のキャッシュメモリに新たにキャッシュデータが格納される際に、前記新たなキャッシュデータに関連付けられているアドレスと、前記バッファに格納されているアドレスとを比較して、前記新たなキャッシュデータに関連付けられているアドレスと、前記バッファに格納されているアドレスとが一致した場合、前記新たなキャッシュデータに過去にリプレースされたデータである旨の情報を付加する、請求項１記載のメモリシステム。
【請求項３】
前記リプレース部は、
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記過去にリプレースされたデータである旨の情報が付加されたキャッシュデータのリプレース優先順位を下げて前記リプレース対象キャッシュデータを決定する、請求項２記載のメモリシステム。
【請求項４】
前記リプレース部は、
前記過去にリプレースされたデータである旨の情報が付加されたキャッシュデータが複数あり、前記過去にリプレースされたデータである旨の情報が付加された複数のキャッシュデータのいずれかを選択してリプレースする場合、アクセスされたタイミングが古いキャッシュデータを選択してリプレースする、請求項２又は３記載のメモリシステム。
【請求項５】
第１のキャッシュメモリと、前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、を備えるメモリシステムにおけるキャッシュメモリ制御方法であって、
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定し、
前記第２のキャッシュメモリに格納されているキャッシュデータのうち、前記第１のキャッシュメモリにおいて決定されたリプレース対象キャッシュデータと同一のキャッシュデータを無効化する、キャッシュメモリ制御方法。
【請求項６】
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースが行われた場合に、前記キャッシュデータに関連付けられているアドレスをバッファに格納し、
前記第１のキャッシュメモリに新たにキャッシュデータが格納される際に、前記新たなキャッシュデータに関連付けられているアドレスと、前記バッファに格納されているアドレスとを比較し、
前記新たなキャッシュデータに関連付けられているアドレスと、前記バッファに格納されているアドレスとが一致した場合、前記新たなキャッシュデータに過去にリプレースされたデータである旨の情報を付加する、請求項５記載のキャッシュメモリ制御方法。
【請求項７】
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記過去にリプレースされたデータである旨の情報が付加されたキャッシュデータのリプレース優先順位を下げて前記リプレース対象キャッシュデータを決定する、請求項６記載のキャッシュメモリ制御方法。
【請求項８】
前記過去にリプレースされたデータである旨の情報が付加されたキャッシュデータが複数あり、前記過去にリプレースされたデータである旨の情報が付加された複数のキャッシュデータのいずれかを選択してリプレースする場合、アクセスされたタイミングが古いキャッシュデータを選択してリプレースする、請求項６又は７記載のキャッシュメモリ制御方法。
【請求項９】
第１のキャッシュメモリと、前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、を備えるメモリシステムにおけるメモリ制御プログラムであって、
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定するステップと、
前記第２のキャッシュメモリに格納されているキャッシュデータのうち、前記第１のキャッシュメモリにおいて決定されたリプレース対象データと同一のデータを無効化するステップと、をコンピュータに実行させるメモリ制御プログラム。
【請求項１】
第１のキャッシュメモリと、
前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定し、前記第２のキャッシュメモリに格納されているキャッシュデータのうち前記リプレース対象のキャッシュデータと同一のキャッシュデータを無効化するリプレース部と、を備えるメモリシステム。
【請求項２】
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースが行われた場合に、前記リプレースされたキャッシュデータに関連付けられているアドレスを格納するバッファをさらに備え、
前記リプレース部は、
前記第１のキャッシュメモリに新たにキャッシュデータが格納される際に、前記新たなキャッシュデータに関連付けられているアドレスと、前記バッファに格納されているアドレスとを比較して、前記新たなキャッシュデータに関連付けられているアドレスと、前記バッファに格納されているアドレスとが一致した場合、前記新たなキャッシュデータに過去にリプレースされたデータである旨の情報を付加する、請求項１記載のメモリシステム。
【請求項３】
前記リプレース部は、
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記過去にリプレースされたデータである旨の情報が付加されたキャッシュデータのリプレース優先順位を下げて前記リプレース対象キャッシュデータを決定する、請求項２記載のメモリシステム。
【請求項４】
前記リプレース部は、
前記過去にリプレースされたデータである旨の情報が付加されたキャッシュデータが複数あり、前記過去にリプレースされたデータである旨の情報が付加された複数のキャッシュデータのいずれかを選択してリプレースする場合、アクセスされたタイミングが古いキャッシュデータを選択してリプレースする、請求項２又は３記載のメモリシステム。
【請求項５】
第１のキャッシュメモリと、前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、を備えるメモリシステムにおけるキャッシュメモリ制御方法であって、
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定し、
前記第２のキャッシュメモリに格納されているキャッシュデータのうち、前記第１のキャッシュメモリにおいて決定されたリプレース対象キャッシュデータと同一のキャッシュデータを無効化する、キャッシュメモリ制御方法。
【請求項６】
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースが行われた場合に、前記キャッシュデータに関連付けられているアドレスをバッファに格納し、
前記第１のキャッシュメモリに新たにキャッシュデータが格納される際に、前記新たなキャッシュデータに関連付けられているアドレスと、前記バッファに格納されているアドレスとを比較し、
前記新たなキャッシュデータに関連付けられているアドレスと、前記バッファに格納されているアドレスとが一致した場合、前記新たなキャッシュデータに過去にリプレースされたデータである旨の情報を付加する、請求項５記載のキャッシュメモリ制御方法。
【請求項７】
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記過去にリプレースされたデータである旨の情報が付加されたキャッシュデータのリプレース優先順位を下げて前記リプレース対象キャッシュデータを決定する、請求項６記載のキャッシュメモリ制御方法。
【請求項８】
前記過去にリプレースされたデータである旨の情報が付加されたキャッシュデータが複数あり、前記過去にリプレースされたデータである旨の情報が付加された複数のキャッシュデータのいずれかを選択してリプレースする場合、アクセスされたタイミングが古いキャッシュデータを選択してリプレースする、請求項６又は７記載のキャッシュメモリ制御方法。
【請求項９】
第１のキャッシュメモリと、前記第１のキャッシュメモリに優先してプロセッサからアクセスされる第２のキャッシュメモリと、を備えるメモリシステムにおけるメモリ制御プログラムであって、
前記第１のキャッシュメモリにおいてキャッシュデータのリプレースを行う場合に、前記第１のキャッシュメモリに格納されているキャッシュデータの中から、それぞれのキャッシュデータが過去にリプレース対象となったか否かを示す履歴情報を用いて、リプレース対象キャッシュデータを決定するステップと、
前記第２のキャッシュメモリに格納されているキャッシュデータのうち、前記第１のキャッシュメモリにおいて決定されたリプレース対象データと同一のデータを無効化するステップと、をコンピュータに実行させるメモリ制御プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１２−１８５６４９（Ｐ２０１２−１８５６４９Ａ）
【公開日】平成２４年９月２７日（２０１２．９．２７）
【国際特許分類】
【出願番号】特願２０１１−４７９０６（Ｐ２０１１−４７９０６）
【出願日】平成２３年３月４日（２０１１．３．４）
【出願人】（０００１６８２８５）エヌイーシーコンピュータテクノ株式会社 (572)
【Ｆターム（参考）】
【公開日】平成２４年９月２７日（２０１２．９．２７）
【国際特許分類】
【出願日】平成２３年３月４日（２０１１．３．４）
【出願人】（０００１６８２８５）エヌイーシーコンピュータテクノ株式会社 (572)
【Ｆターム（参考）】
[ Back to top ]