(57)【要約】【課題】タグ記憶部のデータサイズを少なくすることができるキャッシュメモリ装置を提供すること【解決手段】タグ記憶部１２０は、キャッシュデータを参照するために用いるタグの上位側の値を格納するタグ上位テーブル１２１と、タグ上位テーブル１２１内に格納された値のいずれかと関連付けるポインタ及びタグの下位側の値をキャッシュインデックス数と同数だけ格納するタグ下位テーブル１２２を備える。キャッシュデータ記憶部１３０はタグと関連付けられたキャッシュデータを格納する。アクセス制御部１１０はデータアクセスに応じてタグ記憶部１２０を検索し、検索結果に基づいてキャッシュデータ記憶部１３０にアクセスする。タグ上位テーブル１２１は、当該テーブルのデータサイズとタグ下位テーブル１２２のデータサイズの和が、タグのビット幅とキャッシュインデックス数との乗数より少なく構成される。【選択図】図１
2012003314.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュデータを参照するために用いるタグの上位側の値を格納するタグ上位テーブルと、前記タグ上位テーブル内に格納された値のいずれかと関連付けるポインタ及び前記タグの下位側の値をキャッシュインデックス数と同数だけ格納するタグ下位テーブルと、を含むタグ記憶部と、
前記タグと関連付けられた前記キャッシュデータを格納するキャッシュデータ記憶部と、
データアクセスに応じて前記タグ記憶部を検索するとともに、検索結果に基づいて前記キャッシュデータ記憶部にアクセスするアクセス制御部と、を備え、
前記タグ上位テーブルは、当該テーブルのデータサイズと、前記タグ下位テーブルのデータサイズとの和が、前記タグのビット幅と前記キャッシュインデックス数との乗数より少なくなるように構成され、
前記アクセス制御部は、入力アドレスに含まれるインデックスに応じたタグの上位値及び下位値を前記入力アドレスから読み出し、読み出した上位値と、前記インデックスに対応する前記タグ上位テーブル内のデータと、の一致判定をするとともに、読み出した下位値と、前記インデックスに対応する前記タグ下位テーブル内のデータと、の一致判定をし、読み出した下位値が一致しない下位値不一致判定の場合には当該インデックスに応じて前記タグ下位テーブル及び前記キャッシュデータ記憶部を更新するキャッシュメモリ装置。
【請求項２】
前記アクセス制御部は、読み出した上位値と、前記インデックスに対応する前記タグ上位テーブル内のデータと、が一致しない上位値不一致判定の場合、当該インデックスに対応する前記タグ上位テーブル内のデータと関連付けられている前記タグ下位値テーブル内の全てのデータである無効対象下位値データに対して、有効／無効を表わす活性化ビットを無効に設定するとともに、当該インデックスに応じて前記タグ上位テーブル、前記タグ下位テーブル、及び前記キャッシュデータ記憶部を更新することを特徴とする請求項１に記載のキャッシュメモリ装置。
【請求項３】
前記キャッシュデータ記憶部に格納された各データは、メインメモリに前記キャッシュデータを反映させるか否かを示すダーティビットを含み、
前記アクセス制御部は、前記上位値不一致判定の場合、前記無効対象下位値データと関連付けられている前記キャッシュデータに対して前記ダーティフラグが設定されている否かを判定し、前記ダーティフラグが設定されている前記キャッシュデータの値を前記メインメモリに反映させ、
前記下位値不一致判定の場合、一致判定に用いた前記インデックスに対応する前記キャッシュデータに対して前記ダーティフラグが設定されている否かを判定し、前記ダーティフラグが設定されている場合に当該キャッシュデータの値を前記メインメモリに反映させることを特徴とする請求項２に記載のキャッシュメモリ装置。
【請求項４】
前記タグ上位値テーブルは当該テーブル内に無効データを表わす無効化データを格納し、
前記タグ下位値テーブルの各データは、前記無効化データと関連付けられるか否かにより有効／無効が設定されることを特徴とする請求項１乃至請求項３のいずれか１項に記載のキャッシュメモリ装置。
【請求項５】
データビットを処理する複数のフリップフロップ回路を備え、
前記ポインタは前記上位タグテーブル内のデータ列と同数のデータビット列から構成され、
前記複数のフリップフロップ回路の各々は、前記ポインタの各データビットを操作することを特徴とする請求項１乃至請求項４のいずれか１項に記載のキャッシュメモリ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はキャッシュメモリ装置に関する。
【背景技術】
【０００２】
一般に、ＣＰＵ（Central Processing Unit）等からメインメモリに対するアクセス時間を短縮するためにキャッシュメモリが利用される。キャッシュメモリには、アクセス頻度の高いデータがメインメモリからコピーされて格納される。ＣＰＵからアクセスしようとしたメインメモリのアドレスに記憶されているデータがキャッシュメモリに存在するときはヒットと呼ばれ、キャッシュメモリ内のデータがＣＰＵに与えられる。また、ＣＰＵがアクセスしようとしたアドレスに記憶されているデータがキャッシュメモリ内に存在しないときは、ミスヒットと呼ばれ、メインメモリのデータがＣＰＵに与えられると同時に、そのデータがキャッシュメモリに格納される。
【０００３】
キャッシュメモリは一般に、複数のタグとそれぞれのタグに対応したデータとを保持するキャッシュテーブルを備えており、入力アドレスに含まれるタグがキャッシュテーブルに格納されたタグと比較される。詳細には、ＣＰＵは入力アドレスをキャッシュメモリに入力し、キャッシュメモリは当該入力アドレスに含まれるタグ及びインデックスと、キャッシュテーブル内のタグ及びインデックスと、を比較する。両者が一致した場合、キャッシュメモリは当該タグ及びインデックスに対応するデータをＣＰＵに供給する。
【０００４】
キャッシュメモリは使用頻度が高いため、キャッシュメモリにかかる消費電力の低減が必要である。特許文献１には、消費電力の低減が可能となるキャッシュメモリ装置に関する技術が開示されている。当該キャッシュメモリ装置は、キャッシュデータを判別するためのタグと、タグに対応づけられたデータと、を異なるテーブルにより管理する。詳細には、当該キャッシュメモリ装置は、タグを格納するタグ記憶部と、タグ記憶部と関連付けられ、タグに対応づけられたデータを格納するキャッシュデータ記憶部と、を備える。図１４は、特許文献１に記載のキャッシュメモリ装置内のタグ記憶部の構成を示す図である。
【０００５】
当該キャッシュメモリ装置は、ＣＰＵ等のデータ処理ユニットからの入力アドレスに含まれるインデックスに応じて、タグ記憶部にのみアクセスして当該入力アドレスに含まれるタグと、タグ記憶部内のタグと、の比較を行う。データ処理ユニットにはタグが一致した場合にのみキャッシュデータ記憶部からのデータが送信される。
【０００６】
図１４では、入力アドレスは３２ビットのアドレス空間を持つ。タグ領域は２２ビットであり、インデックス領域は６ビットであり、オフセット領域は４ビットである。また、タグ記憶部は、各インデックスに応じたタグ及びデータの有効／無効を示すバリッドフラグを備える。キャッシュメモリ装置に入力アドレスが入力された場合、当該キャッシュメモリ装置は入力アドレスのインデックス（００００１０）を読み出す。そして、当該キャッシュメモリ装置は、読み出したインデックスに対応するタグ記憶部内のタグと、入力アドレスのタグと、が一致するか否かを判定する。この場合、両者のタグは一致するため（両者ともに１００００００００００００００１００００００）、当該キャッシュメモリ装置はキャッシュヒットと判定する。そして当該キャッシュメモリ装置は、インデックスに応じたデータをキャッシュデータ記憶部から取得し、取得したキャッシュデータをデータ処理ユニットに供給する。
【０００７】
また、タグが不一致の場合には、当該キャッシュメモリ装置はキャッシュデータ記憶部にアクセスしない。キャッシュデータ記憶部に必要な場合にのみアクセスすることにより、当該キャッシュメモリ装置は消費電力を低減することができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００６−３１８０８０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上述のキャッシュメモリ装置ではキャッシュデータのサイズが増加することに伴い、タグ記憶部のデータサイズが大きくなってしまうという問題がある。上述のキャッシュメモリ装置の構成では、タグ記憶部内のテーブル（以下の記載ではタグテーブルとも記載する。）はタグのビット幅と、バリッドフラグのビット幅を加算した値にインデックス数を乗じたサイズのビットサイズが必要となる。図１４では、タグのビット幅が２２ビットであり、バリッドフラグが１ビットであり、インデックス数が６４ビットである。よって、タグテーブルは１４７２ビットのデータサイズが必要となる。
【００１０】
すなわち、上述のキャッシュメモリ装置では、タグテーブルのデータサイズが常に以下の式が示す値となり、データサイズが大きくなってしまう。
（タグのビット幅＋バリッドフラグのビット幅）×インデックス数
【００１１】
図１５は、特許文献１にかかるキャッシュメモリ装置の概念を示す図である。図示したようにタグ記憶部は、インデックスと同数のタグ及びバリッドフラグを備える構成であり、そのデータサイズが大きくなる。
【課題を解決するための手段】
【００１２】
本発明にかかるキャッシュメモリ装置の一態様は、キャッシュデータを参照するために用いるタグの上位側の値を格納するタグ上位テーブルと、前記タグ上位テーブル内に格納された値のいずれかと関連付けるポインタと前記タグの下位側の値をキャッシュインデックス数と同数だけ格納するタグ下位テーブルと、を含むタグ記憶部と、前記タグと関連付けられた前記キャッシュデータを格納するキャッシュデータ記憶部と、データアクセスに応じて前記タグ記憶部を検索するとともに、検索結果に基づいて前記キャッシュデータ記憶部にアクセスするアクセス制御部と、を備え、前記タグ上位テーブルは、当該テーブルのデータサイズと、前記タグ下位テーブルのデータサイズとの和が、前記タグのビット幅と前記キャッシュインデックス数との乗数より少なくなるように構成され、前記アクセス制御部は、入力アドレスに含まれるインデックスに応じたタグの上位値及び下位値を前記入力アドレスから読み出し、読み出した上位値と、前記インデックスに対応する前記タグ上位テーブル内のデータと、の一致判定をするとともに、読み出した下位値と、前記インデックスに対応する前記タグ下位テーブル内のデータと、の一致判定をし、読み出した下位値が一致しない下位値不一致判定の場合には当該インデックスに応じて前記タグ下位テーブル及び前記キャッシュデータ記憶部を更新するものである。
【００１３】
本発明においては、キャッシュメモリ装置は、タグをタグ上位テーブルとタグ下位テーブルに分けて保持する。一般にキャッシュメモリ装置に入力されるタグのビット列は、上位側のビット列にほとんど変更がなく、下位側のビット列にのみ変更がある。これにより、タグ上位テーブルは、変更の少ないデータ（同じビット列を持つデータ）を保持することからインデックスと同数のデータ列を持つ必要性が少ない。タグ上位テーブルを上述のデータサイズとなるように構成することにより、キャッシュメモリ装置はタグ記憶部のデータサイズを小さくできるとともに、キャッシュミス率の大幅な増加を防止できる。
【発明の効果】
【００１４】
本発明によれば、タグ記憶部のデータサイズを少なくすることができるキャッシュメモリ装置を提供することができる。
【図面の簡単な説明】
【００１５】
【図１】実施の形態１にかかるキャッシュメモリ装置の構成を示すブロック図である。
【図２】実施の形態１にかかるキャッシュメモリ装置の概念図である。
【図３】実施の形態１にかかるキャッシュメモリ装置のタグ記憶部の構成図である。
【図４】実施の形態１にかかるキャッシュメモリ装置のヒット／ミスヒットの判定を示す図である。
【図５】実施の形態１にかかるキャッシュメモリ装置のヒット／ミスヒットの判定を示す図である。
【図６】実施の形態１にかかるキャッシュメモリ装置のヒット／ミスヒットの判定を示す図である。
【図７】実施の形態１にかかるキャッシュメモリ装置のヒット／ミスヒットの判定を示す図である。
【図８】実施の形態１にかかるキャッシュメモリ装置のヒット／ミスヒットの判定を示す図である。
【図９】実施の形態１にかかるキャッシュメモリ装置のヒット／ミスヒットの判定を示す図である。
【図１０】実施の形態２にかかるキャッシュメモリ装置の概念図である。
【図１１】実施の形態２にかかるキャッシュメモリ装置の概念図である。
【図１２】実施の形態３にかかるキャッシュメモリ装置の概念図である。
【図１３】実施の形態４にかかるキャッシュメモリ装置の概念図である。
【図１４】特許文献１にかかるキャッシュメモリ装置のタグ記憶部の構成図である。
【図１５】特許文献１にかかるキャッシュメモリ装置の概念図である。
【発明を実施するための形態】
【００１６】
＜実施の形態１＞
一般にキャッシュメモリを用いるデータ処理部が入力するアドレスは、全体のアドレス空間内のうち限られた所定範囲内のアドレス空間となる。すなわち、データ処理部の入力するアドレスのビット列（タグのビット列）は、上位側のビット列にほとんど変更がなく、下位側のビット列にのみ変更がある。本実施の形態にかかるキャッシュメモリ装置は、この特徴に着目した構成となっている。以下、図面を参照して本発明の実施の形態について説明する。図１は、本実施の形態にかかるキャッシュメモリメモリ装置の構成を示すブロック図である。
【００１７】
キャッシュメモリ１０は、ＣＰＵ（Central Processing Unit）２０と、メインメモリ３０との間に設けられる。ＣＰＵ２０は、キャッシュメモリ１０内またはメインメモリ３０内にあるデータを用いてデータ処理を行う処理部である。また、メインメモリ３０はいわゆる主記憶装置であり、データやプログラムを記憶する装置である。
【００１８】
キャッシュメモリ１０は、アクセス制御部１１０と、タグ記憶部１２０と、キャッシュデータ記憶部１３０と、を備える。タグ記憶部１２０はタグ上位テーブル１２１と、タグ下位テーブル１２２と、を備える。
【００１９】
アクセス制御部１１０には、ＣＰＵ２０から所望のデータに対応する入力アドレスが入力される。アクセス制御部１１０は、入力アドレスを解析し、インデックス、タグ、及びオフセットを読み出す。アクセス制御部１１０は、入力アドレスから読み出したインデックス及びタグを用いてタグ記憶部１２０内に格納されたタグとの一致判定をする。また、アクセス制御部１１０は、タグ記憶部１２０内のバリッドフラグを用いた有効／無効判定を行う。当該タグの一致判定及び有効／無効判定は、図４乃至図９を用いて後述する。
【００２０】
タグが一致し、バリッドフラグが有効を示す値である場合（キャッシュヒットである場合）、アクセス制御部１１０は入力アドレスのインデックス及びオフセットに対応するキャッシュデータをキャッシュデータ記憶部１３０から読み出す。アクセス制御部１１０は、読み出したキャッシュデータをＣＰＵ２０に転送する。
【００２１】
タグが一致しない場合またはバリッドフラグが無効を示す値である場合（ミスヒットである場合）、アクセス制御部１１０はメインメモリ３０から入力アドレスのインデックスに対応するデータを読み出す。そして、アクセス制御部１１０は読み出したデータをＣＰＵ２０に転送する。
【００２２】
タグ記憶部１２０は、タグ及びデータの有効／無効を示すバリッドフラグを格納する。タグ記憶部１２０は、タグの上位値を格納するタグ上位テーブル１２１と、タグの下位値を格納するタグ下位テーブル１２２と、を備える。タグ上位テーブル１２１は、当該テーブルのデータサイズと、タグ下位テーブル１２２のデータサイズとの和が、タグのビット幅とインデックス数との乗数より少なくなるように構成される。タグ記憶部１２０内の各テーブル（タグ上位テーブル１２１及びタグ下位テーブル１２２）は例えばＤＲＡＭ（Dynamic Random Access Memory）メモリセルアレイにより構成される。タグ記憶部１２０内の各テーブルのデータは、ミスヒットの場合に書き換えられる。タグ記憶部１２０の構成、データ例、及び書き換え処理については後述する。
【００２３】
なお、バリッドフラグは該当データを明示的に無効にしたい場合等に"０"に設定され、該当データが有効である場合には"１"に設定される。バリッドフラグは任意のタイミングにより設定可能である。
【００２４】
キャッシュデータ記憶部１３０は、各インデックスに対応するキャッシュデータを格納する。キャッシュデータ記憶部１３０内のデータは、ミスヒットの場合にメインメモリ３０から読み出したデータと等しくなるように書き換えられる。
【００２５】
次に、図２を用いて本実施の形態にかかるキャッシュメモリ装置の概念を説明する。図２は、タグ記憶部１２０の構成及びアクセス制御部１１０の動作を示す概念図である。
【００２６】
タグ上位テーブル１２１は、タグ上位値とバリッドフラグとの組を複数格納する。前述のようにＣＰＵ２０の入力するアドレスのビット列（すなわちタグ部分のビット列）は、上位側のビット列にほとんど変更がなく、下位側のビット列にのみ変更がある。タグ上位テーブル１２１はこの上位側のビットを保持するためのテーブルである。タグ下位テーブル１２２は、タグ下位値と、タグ上位テーブル１２１内のタグ上位値との関連を示すポインタと、バリッドフラグと、の組を複数格納する。本例では、タグ上位テーブル１２１は４列のデータのみを格納する。また、タグ下位テーブル１２２は、インデックスの数と同数となる列数のデータを格納する。
【００２７】
アクセス制御部１１０（図示せず）は、入力アドレスを解析する。すなわちアクセス制御部１１０は、入力アドレスからタグ上位値、タグ下位値、インデックス、及びオフセットを読み出す。アクセス制御部１１０は、読み出したインデックスと対応するタグ下位テーブル１２２のデータ列を抽出する。そして、アクセス制御部１１０は該当列のタグ下位値と、入力アドレスから読み出したタグ下位値が一致するか否かを判定する（判定１）。また、アクセス制御部１１０は該当列のバリッドフラグが有効を示す値か否かを判定する（判定２）。アクセス制御部１１０は、タグ下位テーブル１２２を用いた一致判定と並列して、タグ上位テーブル１２１と、入力アドレスから読み出したタグ上位値との一致判定を行う（判定３）。当該一致判定は、入力アドレスから読み出したインデックスと対応するタグ下位テーブル１２２の列のポインタが指し示しているタグ上位テーブル１２１の列を用いて行う。また、アクセス制御部１１０は、タグ上位テーブル１２１の該当列のバリッドフラグが有効を示す値か否かを判定する（判定４）。
【００２８】
アクセス制御部１１０は、上述の判定１から判定４が全て満たされる場合にキャッシュヒットと判定する。キャッシュヒットと判定した場合、アクセス制御部１１０は入力アドレスのインデックスに対応するキャッシュデータ記憶部１３０（図示せず）のデータ列からキャッシュデータを読み出す。
【００２９】
一方、上述の判定１から判定４のいずれかが満たされない場合、アクセス制御部１１０はミスヒットと判定する。ミスヒットと判定した場合、アクセス制御部１１０は入力アドレスから読み出したタグ上位値、タグ下位値、及びインデックスを用いてメインメモリ３０（図示せず）からデータを読み出す。そして、アクセス制御部１１０は入力アドレスから読み出したデータ（タグ上位値、タグ下位値、インデックス）を用いてタグ記憶部１２０内のデータを更新する。また、アクセス制御部１２０はメインメモリ３０から読み出したデータを用いてキャッシュデータ記憶部１３０を更新する。ミスヒット時のタグ記憶部１２０の更新処理は、図５から図９を用いて後述する。
【００３０】
続いて、図３を用いて本実施の形態にかかるタグ記憶部１２０の構成例を説明する。本例では、入力アドレスは１５ビットのタグ上位部、７ビットのタグ下位部、６ビットのインデックス部、及び４ビットのオフセット部から構成される。タグ記憶部１２０は前述のようにタグ上位テーブル１２１とタグ下位テーブル１２２とを備える。タグ下位テーブル１２２は、インデックスと同数（６４）のデータ列が格納される。タグ下位テーブル１２２の各データ列は、ポインタによりタグ上位テーブル１２１のデータ列と関連付けられている。タグ下位テーブル１２２の各データ列は、バリッドフラグによりデータの有効性が設定されている。
【００３１】
タグ上位テーブル１２１は、４列のデータ列を格納している。各データ列は、バリッドフラグによりデータの有効性が設定されている。タグ上位テーブル１２１は、図示するようにキャッシュインデックスの数（６４）に関わらず少数のデータ列により構成する。具体的には、タグ上位テーブル１２１のテーブルサイズは、前述のように当該テーブルのデータサイズと、タグ下位テーブル１２２のデータサイズとの和が、タグのビット幅とインデックス数との乗数より少なくなるように構成される。
【００３２】
図３の構成では、タグ記憶部１２０のデータサイズは、以下の式により算出できる。
（タグ下位値のビット幅＋バリッドフラグのビット幅＋ポインタのビット幅）×インデックス数  ＋  （タグ上位値のビット幅＋バリッドフラグのビット幅）× タグ上位テーブルのデータ列数
【００３３】
上述の式に図３の構成の各値を代入して算出したタグ記憶部１２０のデータサイズは以下のように７０４ビットとなる。
（７ビット＋１ビット＋２ビット）×６４＋（１５ビット＋１ビット）×４＝７０４ビット
【００３４】
なお、ＣＰＵ２０が扱うプログラム等の性質に応じてタグ上位値のビット幅及びタグ下位値のビット幅を任意に変更することが可能である。また、ＣＰＵ２０が扱うプログラム等の性質に応じてタグ上位テーブルのデータ列数を任意に変更することも可能である。
【００３５】
次に、本実施の形態にかかるキャッシュメモリ１０によるヒット判定（キャッシュヒット／ミスヒット）及びミスヒット時のデータ更新について図４〜図９を用いて説明する。図４はキャッシュヒット判定時の概念を示す図である。アクセス制御部１１０（図示せず）は、入力アドレスから読み出したインデックス（００００１０）に該当するタグ下位テーブル１２２の列２を読み出す。そして、アクセス制御部１１０は、入力アドレスのタグ下位部（１００００００）と列２のタグ下位値（１００００００）が一致していると判定する。また、アクセス制御部１１０は、タグ下位テーブル１２２の列２のバリッドフラグが有効を示す"１"であると判定する。
【００３６】
アクセス制御部１１０は、タグ下位テーブル１２２の判定処理と並行してタグ上位テーブル１２１の各列のタグ上位値と、入力アドレスのタグ上位値（１００００００００００００００）と、が一致するか否かを判定する。本例では、アクセス制御部１１０はタグ上位テーブル１２１の列１のタグ上位値と、入力アドレスのタグ上位値と、が一致すると判定する。また、アクセス制御部１１０は、タグ上位テーブルの列１のバリッドフラグが有効を示す"１"であると判定する。アクセス制御部１１０は、タグ下位テーブル１２２の列２と、タグ上位テーブル１２１の列１と、がポインタにより関連付けられていると判定する。アクセス制御部１１０は、上記の判定よりキャッシュヒットであると判定する。キャッシュヒットと判定したため、アクセス制御部１１０はインデックス（００００１０）に基づいてキャッシュデータ記憶部１３０からデータを読み出す。
【００３７】
次に図５を用いてタグ上位値にかかるミスヒット判定及びタグ記憶部１２０内のデータ更新について説明する。アクセス制御部１１０は図４と同様の手法によりタグ下位テーブル１２２と、入力アドレスのタグ下位値との一致性、及びバリッドフラグに関する判定を行う。またアクセス制御部１１０はタグ上位テーブル１２１の各列のタグ上位値と、入力アドレスのタグ上位値（１００００００００００００００）と、が一致するか否かを判定する。ここでアクセス制御部１１０は、タグ上位テーブル１２１内に入力アドレスのタグ上位値と一致するタグ上位値がないためミスヒットと判定する。
【００３８】
タグ上位値のミスヒットが生じた場合、アクセス制御部１１０は以下のようにタグ記憶部１２０の値を更新する。アクセス制御部１１０は、インデックス（００００１０）と対応するタグ上位テーブル１２１の列１を入力アドレスのタグ上位値（１０００００００００１００００）を用いて更新する。次にアクセス制御部１１０は、タグ上位テーブル１２１の列１と関連付けられていたタグ下位テーブル１２２の各列（本例ではポインタ"０１"を持つ列０、列２、列４である。当該データ列を「無効対象下位値データ」とも記載する。）を無効化する（バリッドフラグを"０"に設定する）。続いて、アクセス制御部１１０はインデックス（００００１０）に該当するタグ下位テーブル１２２の列２を入力アドレスのタグ下位部（１００００００）を用いて更新する。また、アクセス制御部１１０はタグ下位テーブル１２２の列２を有効化する（バリッドフラグを"１"に設定する）。図６は、アクセス制御部１１０による更新処理後のタグ記憶部１２０を示す図である。また、アクセス制御部１１０はメインメモリ３０から読み出した値を用いてキャッシュデータ記憶部１３０（図示せず）のインデックス（００００１０）に対応する箇所を更新する。
【００３９】
次に、図７を用いてタグ上位テーブル１２１の無効化にかかるミスヒット判定及びタグ記憶部１２０内のデータ更新について説明する。アクセス制御部１１０は、図４及び図５に示した場合と同様にタグ下位テーブル１２２と、入力アドレスのタグ下位値との一致性、及びバリッドフラグに関する判定を行う。またアクセス制御部１１０はタグ上位テーブル１２１の各列のタグ上位値と、入力アドレスのタグ上位値（１００００００００００００００）と、が一致するか否かを判定する。この場合、タグ下位テーブル１２２との一致判定及びタグ上位値との一致判定は成功する。しかし、タグ上位テーブル１２１の列１のバリッドフラグは無効を示す"０"である。そのため、アクセス制御部１１０はミスヒットと判定する。
【００４０】
バリッドフラグによるタグ上位テーブル１２１のミスヒットが生じた場合、アクセス制御部１１０は該当するタグ上位テーブル１２１の該当列の有効化する。本例では、アクセス制御部１１０はタグ上位テーブル１２１の列１のバリッドフラグを"１"に設定する。タグ下位テーブル１２２に関するデータ更新（無効対象下位値データの無効化処理）は図５に示した手法と同様であるため説明を省略する。また、アクセス制御部１１０はメインメモリ３０から読み出した値を用いてキャッシュデータ記憶部１３０のインデックス（００００１０）に対応する箇所を更新する。
【００４１】
次に、図８を用いてタグ下位値にかかるミスヒット判定及びタグ記憶部１２０内のデータ更新について説明する。アクセス制御部１１０は、入力アドレスから読み出したインデックス（００００１０）に該当するタグ下位テーブル１２２の列２を読み出す。そして、アクセス制御部１１０は、入力アドレスのタグ下位部（１０００００１）と列２のタグ下位値（１００００００）が一致しているか否かを判定する。両者が一致していないため、アクセス制御部１１０はタグ下位値にかかるミスヒットと判定する。
【００４２】
タグ下位値にかかるミスヒットが生じた場合、アクセス制御部１１０はタグ下位テーブル１２２の該当列を入力アドレスのタグ下位部の値により更新する。また、アクセス制御部１１０はメインメモリ３０から読み出した値を用いてキャッシュデータ記憶部１３０のインデックス（００００１０）に対応する箇所を更新する。
【００４３】
次に、図９を用いてタグ下位テーブル１２２の無効化にかかるミスヒット判定及びタグ記憶部１２０内のデータ更新について説明する。アクセス制御部１１０は、入力アドレスから読み出したインデックス（００００１０）に該当するタグ下位テーブル１２２の列２を読み出す。そして、アクセス制御部１１０は、当該列のバリッドフラグが"０"に設定されているためミスヒットと判定する。
【００４４】
タグ下位テーブル１２２の無効化にかかるミスヒットが生じた場合、アクセス制御部１１０はタグ下位テーブル１２２の該当列を有効化する（バリッドフラグを"１"に設定する）。また、アクセス制御部１１０はメインメモリ３０から読み出した値を用いてキャッシュデータ記憶部１３０のインデックス（００００１０）に対応する箇所を更新する。
【００４５】
続いて、本実施の形態にかかるキャッシュメモリ装置の効果について説明する。本実施の形態にかかるキャッシュメモリ装置は、タグ記憶部内にタグ上位値を保持するタグ上位テーブル１２１と、タグ下位値を保持するタグ下位テーブル１２２を備える。前述のようにＣＰＵ２０が入力するタグのビット列は、上位側のビット列にほとんど変更がなく、下位側のビット列にのみ変更がある。タグ上位テーブル１２１は、変更の少ないデータ（同じビット列を持つデータ）を保持することからインデックスと同数のデータ列を持つ必要性が少ない。このため、タグ上位テーブル１２１はインデックス数よりも少ないデータ列を保持するように構成する。これにより、タグ記憶部１２０のデータサイズを小さくすることができる。
【００４６】
また、ＣＰＵ２０が入力するタグのビット列の上位側のビット列にほとんど変更がないため、上述の構成であってもミスヒット率が大幅に上がることがない。
【００４７】
さらにまた、キャッシュメモリ１０は、前述のようにタグ下位値のミスヒットの場合と、タグ上位値のミスヒットの場合と、に応じて適切にタグ記憶部１２０のデータ更新を行う。それぞれのミスヒットの場合に応じてデータ更新をおこなうことにより、キャッシュメモリ装置１０は、データ不整合が生じることを防止できる。
【００４８】
＜実施の形態２＞
本実施の形態にかかるキャッシュメモリ装置は、ライトバック方式に対応できることを特徴とする。本実施の形態にかかるキャッシュメモリ装置について、実施の形態１との相違点を以下に説明する。なお、本実施の形態にかかるキャッシュメモリ装置の基本構成は実施の形態１（図１）と略同一である。
【００４９】
図１０はタグ上位値のミスヒット及び当該ミスヒット時のキャッシュデータ記憶部１３０に対する処理を示す図である。図１０（Ａ）では、タグ上位テーブル１２１の列１と入力アドレスのタグ上位値が不一致となる。ミスヒット判定処理は、実施の形態１と同様であるため詳細は省略する。図１０（Ｂ）は、タグ記憶部１２０と対応するキャッシュデータ記憶部１３０の構成を示す図である。キャッシュデータ記憶部１３０は、ライトバック方式に対応できるようにダーティビットを備える構成である。
【００５０】
図１０（Ｂ）において、キャッシュデータ記憶部１３０は、インデックス毎にダーティビットとキャッシュデータを格納する。ダーティビットは、キャッシュメモリ２０内のデータとメインメモリ３０とが相違しているか否かを示すビットである。本例では、ダーティビットが"１"である場合、キャッシュメモリ２０内のデータとメインメモリ３０とが相違していることを示す。一方、ダーティビットが"０"である場合、キャッシュメモリ２０内のデータとメインメモリ３０とが一致していることを示す。
【００５１】
タグ上位値が不一致であった場合、アクセス制御部１１０は、検索対象となったインデックスに対応するタグ上位値を参照するタグ下位値のインデックス全てについてダーティビットが設定されているか否かを判定する。図１０では、アクセス制御部１１０は入力アドレスのインデックス（００００１０）に対応するタグ上位値（列１）を参照するタグ下位テーブル１２２のインデックス（インデックス０、インデックス２、インデックス４）を読み出す。すなわち、アクセス制御部１１０は無効対象下位値データのインデックスを読み出す。
【００５２】
アクセス制御部１１０は、読み出したインデックス（インデックス０、インデックス２、インデックス４）に対応するキャッシュデータ記憶部１３０のデータ列を読み出す。アクセス制御部１１０は、読み出した各データ列のダーティビットが"１"に設定されているか否かを判定する。アクセス制御部１１０は、ダーティビットが"１"に設定されているインデックスのキャッシュデータをメインメモリ３０に書き込む。この場合、インデックス０及びインデックス２のダーティビットが"１"に設定されているため、アクセス制御部１１０はインデックス０及びインデックス２のキャッシュデータ（"１０００"、"１１１０"）をメインメモリ３０に書き込む。
【００５３】
メインメモリ３０へのデータ更新が終了した後に、アクセス制御部１１０はタグ記憶部１２０及びキャッシュデータ記憶部１３０のデータの更新を行う。当該更新処理は実施の形態１と同様であるため、詳細は省略する。
【００５４】
図１１はタグ下位値のミスヒット及び当該ミスヒット時のキャッシュデータ記憶部１３０に対する処理を示す図である。図１１（Ａ）はタグ下位値のミスヒットを示す図である。図１１（Ａ）では、タグ下位テーブル１２２の列２と入力アドレスのタグ下位値が不一致となる。ミスヒット判定処理は、実施の形態１と同様であるため詳細は省略する。図１１（Ｂ）は、タグ記憶部１２０と対応するキャッシュデータ記憶部１３０の構成を示す図である。図１０と同様にキャッシュデータ記憶部１３０は、ライトバック方式に対応できるようにダーティビットを備える構成である。
【００５５】
タグ下位値が不一致であった場合、アクセス制御部１１０は、検索対象となったインデックスについてダーティビットが設定されているか否かを判定する。図１１では、アクセス制御部１１０は入力アドレスのインデックスに対応するキャッシュデータ記憶部１３０のデータ列を読み出す。アクセス制御部１１０は、読み出したデータ列のダーティビットが"１"に設定されているか否かを判定する。アクセス制御部１１０は、ダーティビットが"１"に設定されている場合、当該インデックスのキャッシュデータをメインメモリ３０に書き込む。この場合、インデックス２のダーティビットが"１"に設定されているため、アクセス制御部１１０はインデックス２のキャッシュデータ（"１１１０"）をメインメモリ３０に書き込む。
【００５６】
続いて、本実施の形態にかかるキャッシュメモリ装置の効果について説明する。上述のように、キャッシュデータ記憶部１３０はダーティビットを備える構成である。アクセス制御部１１０は、ミスヒット時に関連するインデックスであってダーティビットが設定されているキャッシュデータ記憶部１３０のデータ列のキャッシュデータをメインメモリ３０に反映させる。これにより、キャッシュメモリ装置１０はメインメモリ３０とのデータの不整合を起こすことなくライトバック方式に対応することが可能となる。
＜実施の形態３＞
本実施の形態にかかるキャッシュメモリ装置は、タグ上位テーブル１２１にのみデータの無効化を示すインバリデイト値が設定されていることを特徴とする。本実施の形態にかかるキャッシュメモリ装置について、実施の形態１及び実施の形態２との相違点を以下に説明する。
【００５７】
図１２を用いて本実施の形態にかかるキャッシュメモリ装置の概念を説明する。タグ上位テーブル１２１は、データの無効化を示すインバリデイト値を格納している。当該インバリデイト値が格納されたデータ列は一切書き換えられることがない。
【００５８】
一方、タグ下位テーブル１２２の各データ列は、ポインタ及びタグ下位値のみを備え、バリッドフラグを含まない。タグ下位値が無効化されたデータである場合、当該タグ下位値にかかるポインタはタグ上位テーブル１２１のインバリデイト値と関連付けられる。
【００５９】
なお、タグ上位テーブル１２１内のタグ上位値が無効である場合、当該タグ上位値に対応するバリッドフラグが無効を示す値に設定される。
【００６０】
続いて、本実施の形態にかかるキャッシュメモリ装置の効果について説明する。上述の構成によればタグ下位テーブルはデータの有効／無効を示すバリッドフラグを保持する必要がない。これにより、実施の形態１または実施の形態２に示した構成と比べてタグ下位テーブル１２２のデータサイズを減少させることができる。タグ下位テーブル１２２のデータサイズが減少することにより、タグ記憶部１２０内のデータサイズを減少させることができる。
【００６１】
＜実施の形態４＞
本実施の形態にかかるキャッシュメモリ装置は、タグ下位テーブルのポインタがタグ上位テーブルのデータ列数と同数のビットにより構成されていることを特徴とする。本実施の形態にかかるキャッシュメモリ装置について、実施の形態１から実施の形態３との相違点を以下に説明する。
【００６２】
図１３を用いて本実施の形態にかかるキャッシュメモリ装置の概念を説明する。タグ上位テーブル１２１は、タグ上位値とバリッドフラグからなるデータ列を複数備える。タグ下位テーブル１２２は、タグ上位テーブル１２１のデータ列数と同数（図１３の例では４）のビット列（以下の記載では「ポインタビット列」とも記載する。）と、タグ下位値と、からなるデータ列をインデックスの数と同数だけ備える。
【００６３】
タグ下位テーブル１２２のポインタビット列は、全てのビットが"０"である場合にデータの無効を示す。また、タグ下位テーブル１２２のポインタビット列は、全てのビットが"０"であるか、一つのビットが"１"であり他のビットが全て"０"となるビット列である。ポインタビット列の各ビットは、タグ上位テーブル１２１の各データ列と対応している。
【００６４】
たとえば、ポインタビット列"１０００"は、タグ上位テーブル１２１の列０と対応する。同様にポインタビット列"０１００"は、タグ上位テーブル１２１の列１と対応する。ポインタビット列"００１０"は、タグ上位テーブル１２１の列２と対応する。ポインタビット列"０００１"は、タグ上位テーブル１２１の列３と対応する。このようにポインタビット列のどのビットに"１"が設定されているかにより、タグ下位値が関連付けられるタグ上位テーブル１２１のデータ列が設定される。
【００６５】
本実施の形態にかかるキャッシュメモリ装置は、タグ下位テーブル１２２のポインタビット列を操作する複数のフリップフロップ回路（図示せず）を備える。各フリップフロップ回路は、タグ下位テーブル１２２の全てのポインタビット列の所定ビット（例えば図１２の破線部分）を操作するように構成されている。ポインタビット列が４ビットのビット列である場合、あるフリップフロップ回路は左から１ビット目のビット列を操作（"０"または"１"に設定）する。
【００６６】
続いて、本実施の形態にかかるキャッシュメモリ装置の効果について説明する。上述のように、本実施の形態にかかるキャッシュメモリ装置は、タグ下位テーブル１２２のポインタをビット列により構成し、当該ビット列の各ビットを操作するフリップフロップ回路を設ける。フリップフロップ回路は、ビットを０または１に設定するのみである。例えば、タグ上位テーブル１２１の列０を更新する場合、列０に対応するポインタビット列のビットを操作するフリップフロップ回路がビット列を変更（０に設定）すればよい。これにより、本実施の形態にかかるキャッシュメモリ装置は、実施の形態１から実施の形態３にかかるキャッシュメモリ装置に比べて高速に処理ができる。
【００６７】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【符号の説明】
【００６８】
１０    キャッシュメモリ
１１０  アクセス制御部
１２０  タグ記憶部
１２１  タグ上位テーブル
１２２  タグ下位テーブル
１３０  キャッシュデータ記憶部
２０    ＣＰＵ
３０    メインメモリ
【図１】
2012003314.tif 000003
【図２】
2012003314.tif 000004
【図３】
2012003314.tif 000005
【図４】
2012003314.tif 000006
【図５】
2012003314.tif 000007
【図６】
2012003314.tif 000008
【図７】
2012003314.tif 000009
【図８】
2012003314.tif 000010
【図９】
2012003314.tif 000011
【図１０】
2012003314.tif 000012
【図１１】
2012003314.tif 000013
【図１２】
2012003314.tif 000014
【図１３】
2012003314.tif 000015
【図１４】
2012003314.tif 000016
【図１５】
2012003314.tif 000017