(57)【要約】【課題】Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置において、参照履歴に冗長ビットを付加することなく、参照履歴のビットエラーを検出する。【解決手段】Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置（Ｎは２以上の整数）であって、ウェイ間の勝敗関係を示すビットであって特定の強さの一のウェイを示すように更新される参照履歴に基づいて、前記特定の強さの一のウェイを検出するウェイ検出部と、前記ウェイ検出部によって特定の強さの一のウェイが検出されない場合に、参照履歴のビット誤りを検出する誤り検出部とを備える。【選択図】　　　図１
2004038299.tif 000002
【特許請求の範囲】
【請求項１】
Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置（Ｎは２以上の整数）であって、
ウェイ間の勝敗関係を示すビットであって特定の強さの一のウェイを示すように更新される参照履歴に基づいて、前記特定の強さの一のウェイを検出するウェイ検出部と、
前記ウェイ検出部によって特定の強さの一のウェイが検出されない場合に、参照履歴のビット誤りを検出する誤り検出部とを備える、キャッシュメモリ装置。
【請求項２】
前記参照履歴は、最新に参照又は更新されたウェイが特定の強さの一のウェイであることを示すように更新される、請求項１に記載のキャッシュメモリ装置。
【請求項３】
前記参照履歴に基づいて置換対象のウェイを選択するウェイ選択部をさらに備える、請求項２に記載のキャッシュメモリ装置。
【請求項４】
前記誤り検出部は、前記ウェイ選択部によって置換対象のウェイが選択された後に、参照履歴のビット誤りを検出する、請求項３に記載のキャッシュメモリ装置。
【請求項５】
前記ウェイ選択部は、特定のアドレスに対するアクセス要求がいずれのウェイにもヒットしなかった場合に、置換対象のウェイを選択する、請求項３に記載のキャッシュメモリ装置。
【請求項６】
前記誤り検出部によって参照履歴のビット誤りが検出された場合に、エラーを報告するエラー報告部をさらに備える、請求項１に記載のキャッシュメモリ装置。
【請求項７】
Ｎウェイ（Ｎは２以上の整数）・セット・アソシアティブ方式のキャッシュメモリ装置において参照履歴のビット誤りを検出する方法であって、
ウェイ間の勝敗関係を示すビットであって特定の強さの一のウェイを示すように更新される参照履歴に基づいて、前記特定の強さの一のウェイを検出するステップ、
その特定の強さの一のウェイが検出されない場合に、参照履歴のビット誤りを検出するステップとを備える参照履歴のビット誤り検出方法。
【請求項８】
前記参照履歴は、最新に参照又は更新されたウェイが特定の強さの一のウェイであることを示すように更新される、請求項７に記載の参照履歴のビット誤り検出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置、特に、参照履歴のビット誤りをパリティビット等の冗長ビットを用いることなく検出できるキャッシュメモリ装置、及び、参照履歴のビット誤り検出方法に関する。
【０００２】
【従来の技術】
従来、Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置においては、同一セット内でＬＲＵ（Ｌｅａｓｔ　Ｒｅｃｅｎｔｌｙ　Ｕｓｅｄ）アルゴリズムによって示される、最後に参照（又は更新）された時刻が最も古いウェイの情報を主記憶装置（メインメモリ）へ書き戻すのが、性能上有利であることが知られている。
【０００３】
従来のキャッシュメモリ装置の動作について図面を参照しながら説明する。図８は、従来のキャッシュメモリ装置の動作を説明するためのフローチャートである。
【０００４】
メインメモリのアドレス空間の特定のアドレスに対するアクセス要求があった場合には（Ｓ２００）、まず、そのアドレスがマッチアドレス（ｍａｔｃｈ　ａｄｄｒｅｓｓ）とラインアドレス（ｌｉｎｅ　ａｄｄｒｅｓｓ）に分離される。各ウェイのタグＲＡＭがラインアドレスで検索され、タグＲＡＭから読み出されたエントリアドレスとマッチアドレスとが比較される（Ｓ２０１）。エントリアドレスとマッチアドレスが同じであれば、そのウェイにヒットしたことになる（Ｓ２０２：Ｙｅｓ）。この場合には、ヒットしたウェイが返され、そのウェイのデータＲＡＭが保持しているメインメモリのコピーに対してアクセスされる（Ｓ２０３）。
【０００５】
一方、マッチアドレスがどのウェイのエントリアドレスにもヒットしなかった場合には（Ｓ２０２：Ｎｏ）、あるウェイの情報を書き戻して（又は無効にして）タグＲＡＭのエントリから追い出し、アクセス要求のあったアドレスのメインメモリのコピーをキャッシュに読み込む。この追い出しウェイ（置換対象のウェイ）の選択のために参照履歴が読み出される（Ｓ２０４）。次に、参照履歴に１ビット誤りが検出されたか否かが判定される（Ｓ２０５）。この誤り検出は、読み出された参照履歴に付加されている冗長ビットに基づいて行われる（例えばパリティチェック）。そして、パリティエラーが起こった場合には（Ｓ２０５：Ｙｅｓ）、その参照履歴に誤りがあるとみなし、エラー報告を行い（Ｓ２０６）、有効なウェイのうち最若番のものを返す（Ｓ２０７）。また、参照履歴で勝敗を決定する際に、参照時刻の関係に矛盾が生じるような場合には、ウェイのゼロセレクトやダブルセレクトを防ぐためにパリティエラーが起きたときと同じ処理を行っていた。
【０００６】
メインメモリへの書き戻しを行うには、タグメモリ（あるいはそれと同等のセットで引くことのできるメモリ領域）内に、同一セット内での参照時刻の新旧を比較できる参照履歴（ＬＲＵビットともいう）を保持しておく必要がある。また、特に信頼性が要求される装置では、参照履歴を保護するために、パリティビットやＥＣＣ（Ｅｒｒｏｒ　Ｃｏｒｒｅｃｔｉｎｇ　Ｃｏｄｅ）等の冗長ビットが参照履歴に付加されることがある。
【０００７】
しかしながら、システムが巨大になりアドレス空間が増えると、キャッシュしなければならないアドレス空間も増大する。キャッシュのブロックサイズが同じであれば、キャッシュ可能なアドレス空間が２倍になるごとに、タグ・メモリのエントリアドレスの情報量が１ビット増えることになる。このとき、タグメモリの情報量の制約等により、参照履歴のエラー検出のための冗長ビットを充分に確保できない場合がある。
【０００８】
【発明が解決しようとする課題】
本発明の課題は、Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置において、参照履歴に冗長ビットを付加することなく、参照履歴のビットエラーを検出することにある。
【０００９】
【課題を解決するための手段】
本発明は、上記の課題を解決するために、Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置（Ｎは２以上の整数）であって、ウェイ間の勝敗関係を示すビットであって特定の強さの一のウェイを示すように更新される参照履歴に基づいて、前記特定の強さの一のウェイを検出するウェイ検出部と、前記ウェイ検出部によって特定の強さの一のウェイが検出されない場合に、参照履歴のビット誤りを検出する誤り検出部とを備える、キャッシュメモリ装置。
【００１０】
本発明によれば、特定の強さの一のウェイを示すように更新されるようになっている参照履歴に基づいてビット誤りを検出する。したがって、Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置において、参照履歴に冗長ビットを付加することなく、参照履歴のビットエラーを検出することが可能となる。
【００１１】
上記のＮウェイ・セット・アソシアティブ方式のキャッシュメモリ装置においては、例えば、前記参照履歴は、最新に参照又は更新されたウェイが特定の強さの一のウェイであることを示すように更新される。
【００１２】
上記のＮウェイ・セット・アソシアティブ方式のキャッシュメモリ装置においては、例えば、前記特定の強さの一のウェイは、Ｎウェイの中で最も強いウェイである。また、前記特定の強さの一のウェイは、Ｎウェイの中で最も弱いウェイであってもよい。
【００１３】
上記のＮウェイ・セット・アソシアティブ方式のキャッシュメモリ装置においては、例えば、前記参照履歴に基づいて置換対象のウェイを選択するウェイ選択部をさらに備える。
【００１４】
上記のＮウェイ・セット・アソシアティブ方式のキャッシュメモリ装置においては、例えば、前記ウェイ選択部は、置換対象のウェイとしてＮウェイの中で最も弱いウェイを選択する。
【００１５】
上記のＮウェイ・セット・アソシアティブ方式のキャッシュメモリ装置においては、例えば、前記誤り検出部は、前記ウェイ選択部によって置換対象のウェイが選択された後に、参照履歴のビット誤りを検出する。
【００１６】
上記のＮウェイ・セット・アソシアティブ方式のキャッシュメモリ装置においては、例えば、前記ウェイ選択部は、特定のアドレスに対するアクセス要求がいずれのウェイにもヒットしなかった場合に、置換対象のウェイを選択する。
【００１７】
上記のＮウェイ・セット・アソシアティブ方式のキャッシュメモリ装置においては、例えば、前記誤り検出部によって参照履歴のビット誤りが検出された場合に、エラーを報告するエラー報告部をさらに備える。例えば、特定アプリケーションやユニット等に報告することが考えられる。
【００１８】
本発明は、方法の発明として次のように特定できる。Ｎウェイ（Ｎは２以上の整数）・セット・アソシアティブ方式のキャッシュメモリ装置において参照履歴のビット誤りを検出する方法であって、ウェイ間の勝敗関係を示すビットであって特定の強さの一のウェイを示すように更新される参照履歴に基づいて、前記特定の強さの一のウェイを検出するステップ、その特定の強さの一のウェイが検出されない場合に、参照履歴のビット誤りを検出するステップとを備える参照履歴のビット誤り検出方法。
【００１９】
【発明の実施の形態】
以下、本発明の実施形態であるＮウェイ・セット・アソシアティブ方式のキャッシュメモリ装置について図面を参照しながら説明する。Ｎは、２、４、８、１６、３２・・・等の２以上の整数である。本実施形態においてはＮ＝４の４ウェイ・セット・アソシアティブ方式のキャッシュメモリ装置について説明する。
【００２０】
図１は、４ウェイ・セット・アソシアティブ方式のキャッシュメモリ装置の概略構成を説明するための図である。キャッシュメモリ装置１００は、ウェイ（タグＲＡＭ）１０１ａから１０１ｄ、メインメモリの内容がコピーされるウェイ（データＲＡＭ）１０２ａから１０２ｄ、及び、置換ウェイ選択部１０３等を備えている。
【００２１】
ウェイ１０１ａは参照履歴を格納している。参照履歴は、ウェイ間の勝敗関係（参照又は更新時刻の新旧関係ともいえる）を示すビット０からビット５（以下、＃０から＃５と呼ぶ）の合計６ビット（４Ｃ２＝６）である。参照履歴は、特定の強さの一のウェイを示すように更新される。例えば、参照履歴は、最新に参照又は更新されたウェイが特定の強さの一のウェイであることを示すように更新される。参照履歴はウェイ１０１ａに、セットごとに格納されている。
【００２２】
図２は、参照履歴の意味を説明するための図である。＃５は、ウェイ０とウェイ１間の勝敗関係を示す。例えば、＃５＝１であれば、ウェイ１がウェイ０に勝っている（即ち、ウェイ１の方がウェイ０より参照時刻が新しい）ことを示す。＃５と排反関係にある［＃５］＝１であれば、ウェイ０がウェイ１に勝っていることを示す。
【００２３】
＃４は、ウェイ０とウェイ２間の勝敗関係を示す。例えば、＃４＝１であれば、ウェイ２がウェイ０に勝っている（即ち、ウェイ２の方がウェイ０より参照時刻が新しい）ことを示す。＃４と排反関係にある［＃４］＝１であれば、ウェイ０がウェイ２に勝っていることを示す。
【００２４】
＃３は、ウェイ０とウェイ３間の勝敗関係を示す。例えば、＃３＝１であれば、ウェイ３がウェイ０に勝っている（即ち、ウェイ３の方がウェイ０より参照時刻が新しい）ことを示す。＃３と排反関係にある［＃３］＝１であれば、ウェイ０がウェイ３に勝っていることを示す。
【００２５】
＃２は、ウェイ１とウェイ２間の勝敗関係を示す。例えば、＃２＝１であれば、ウェイ２がウェイ１に勝っている（即ち、ウェイ２の方がウェイ１より参照時刻が新しい）ことを示す。＃２と排反関係にある［＃２］＝１であれば、ウェイ１がウェイ２に勝っていることを示す。
【００２６】
＃１は、ウェイ１とウェイ３間の勝敗関係を示す。例えば、＃１＝１であれば、ウェイ３がウェイ１に勝っている（即ち、ウェイ３の方がウェイ１より参照時刻が新しい）ことを示す。＃１と排反関係にある［＃１］＝１であれば、ウェイ１がウェイ３に勝っていることを示す。
【００２７】
＃０は、ウェイ２とウェイ３間の勝敗関係を示す。例えば、＃０＝「１」であれば、ウェイ３がウェイ２に勝っている（即ち、ウェイ３の方がウェイ２より参照時刻が新しいこと）を示す。＃０と排反関係にある［＃０］＝「１」であれば、ウェイ２がウェイ３に勝っていることを示す。
【００２８】
図３は、置換ウェイ選択部１０３の概略構成を説明するための図である。置換ウェイ選択部１０３は、主に、ウェイ検出部１０３ａ、誤り検出部１０３ｂ、及び、ウェイ選択部１０３ｃを含む。
【００２９】
ウェイ検出部１０３ａは、参照履歴に基づいて、４ウェイの中で最も強いウェイを検出するための論理回路である。ウェイ検出部１０３ａは、各ウェイごとにそのウェイが他の３つのウェイよりも強いか（即ちそのウェイが４ウェイの中で最も強いウェイか）どうかを検出するためのＮＡＮＤ演算回路Ｃ７０からＣ７３を含む。
【００３０】
ＮＡＮＤ演算回路Ｃ７０は、ウェイ０が他の３つのウェイよりも強いかどうかを検出する。ウェイ０が他の３つのウェイよりも強ければ（即ちウェイ０が４ウェイの中で最も強い一のウェイであれば）、ＮＡＮＤ演算回路Ｃ７０はＷＡＹ０＿ＷＩＮ＝”０”を出力する。一方、ウェイ０が他の３つのウェイのいずれかに負けていれば（即ちウェイ０よりも強いウェイが存在すれば）、ＮＡＮＤ演算回路Ｃ７０はＷＡＹ０＿ＷＩＮ＝”１”を出力する。同様に、ＮＡＮＤ演算回路Ｃ７１は、ウェイ１が他の３つのウェイよりも強いかどうかを検出する。ＮＡＮＤ演算回路Ｃ７２は、ウェイ２が他の３つのウェイよりも強いかどうかを検出する。ＮＡＮＤ演算回路Ｃ７３は、ウェイ３が他の３つのウェイよりも強いかどうかを検出する。
【００３１】
参照履歴は、最新に参照（又は更新）されたウェイが特定の強さのウェイであることを示すように更新される。本実施形態においては、参照履歴は、最新に参照又は更新されたウェイが４ウェイの中で最も強いウェイであることを示すように更新されるものとする。即ち、ウェイが参照（又は更新）された場合には、参照履歴は、その参照されたウェイが４つのウェイの中で最も強いウェイであることを示すように更新される。このため、ウェイ検出部１０３ａは通常、４つのウェイの中で最も強いウェイを検出する。
【００３２】
例えば、図４に示すように、参照履歴が１１１１１１である場合には、縦に３つの１が並んでいるウェイ３が最も強い（他の全てのウェイに勝っている）ことを示す。この参照履歴１１１１１１がウェイ検出部１０３ａに入力された場合には、図３から明らかなように、ＮＡＮＤ演算回路Ｃ７３はＷＡＹ３＿ＷＩＮ＝”０”を出力し、その他のＮＡＮＤ演算回路Ｃ７０からＣ７２はそれぞれ”１”を出力する。これは、ウェイ検出部１０３ａが４つのウェイの中で最も強いウェイとしてウェイ３を検出したことを示す。
【００３３】
ここで、ウェイ２が参照（又は更新）されたとする。この場合、参照履歴は、その最新に参照（又は更新）されたウェイ２が４つのウェイの中で最も強いウェイであることを示すように更新される。図５は、ウェイ２が最も強い一のウェイであることを示すように更新されたことを示している。この参照履歴は、図４に示す参照履歴のうち、［＃０」を１に、［＃０］と排反関係にある＃０を０にそれぞれ更新したものである。この更新後の参照履歴０１１１１１がウェイ検出部１０３ａに入力された場合には、図３から明らかなように、ＮＡＮＤ演算回路Ｃ７２はＷＡＹ２＿ＷＩＮ＝”０”を出力し、その他のＮＡＮＤ演算回路Ｃ７０、Ｃ７１、及び、Ｃ７３はそれぞれ”１”を出力する。これは、ウェイ検出部１０３ａが４つのウェイの中で最も強いウェイとしてウェイ２を検出したことを示す。
【００３４】
このように、参照履歴は、最新に参照（又は更新）されたウェイが４ウェイの中で最も強いウェイであることを示すように更新される。このため、ウェイ検出部１０３ａは通常、４つのウェイの中で最も強い一のウェイを検出する。
【００３５】
一方、図６は、上記のルールで更新した場合には出現し得ない参照履歴のパターンを示している。この参照履歴１１１０１１は、縦に２つの１が並んでいるウェイ２及び３が強いが、最も強いウェイが存在しないことを示す。
この参照履歴１１１０１１がウェイ検出部１０３ａに入力された場合には、図３から明らかなように、ＮＡＮＤ演算回路Ｃ７０からＣ７３はそれぞれ”１”を出力する。”０”は出力されない。これは、ウェイ検出部１０３ａによって４つのウェイの中で最も強いウェイが検出されないことを示す。
【００３６】
誤り検出部１０３ｂは、ウェイ検出部１０３ａによって４つのウェイの中で最も強い一のウェイが検出されない場合に、参照履歴のビット誤りを検出するための論理回路である。
【００３７】
図３に示すように、誤り検出部１０３ｂは、ウェイ検出部１０３ａ（各ＮＡＮＤ演算回路Ｃ７０からＣ７３）からの出力に基づいて参照履歴のビット誤りを検出するＮＯＲ演算回路を含む。例えば、図４に示す参照履歴１１１１１１がウェイ検出部１０３ａに入力された場合には、図３から明らかなように、ＮＡＮＤ演算回路Ｃ７３は”０”を出力し、その他のＮＡＮＤ演算回路Ｃ７０からＣ７２はそれぞれ”１”を出力し、ビット誤り検出部１０３ｂはＬＲＵ＿ＳＢＥ＝０を出力する。ＬＲＵ＿ＳＢＥ＝０は、ビット誤り検出部１０３ｂが参照履歴のビット誤りを検出しなかったことを示す。同様に、図５に示す参照履歴０１１１１１がウェイ検出部１０３ａに入力された場合も、ビット誤り検出部１０３ｂはＬＲＵ＿ＳＢＥ＝０を出力する。
【００３８】
一方、上記ルールで更新した場合には出現し得ない参照履歴１１１０１１がウェイ検出部１０３ａに入力された場合には、図３から明らかなように、ＮＡＮＤ演算回路Ｃ７０からＣ７３はそれぞれ”１”を出力し、ビット誤り検出部１０３ｂはＬＲＵ＿ＳＢＥ＝”１”を出力する。ＬＲＵ＿ＳＢＥ＝”１”は、誤り検出部１０３ｂが参照履歴のビット誤りが検出されたことを示す。
【００３９】
ウェイ選択部１０３ｃは、参照履歴に基づいて置換対象のウェイ（Ｎウェイの中で最も弱いウェイ）を選択するための論理回路である。例えば、ウェイ０とウェイ１の勝敗とウェイ２とウェイ３の勝敗をとり、その敗者同士の比較で最も負けたウェイを置換対象のウェイとする。図３に示すように、ウェイ選択部１０２ｃは、ＮＡＮＤ演算回路Ｃ００からＣ３１と、ＯＲ演算回路Ｃ０２からＣ３２とを含む。例えば、ＮＡＮＤ演算回路Ｃ００は、ウェイ０がウェイ１に負け（ウェイ１よりも古く）かつウェイ２がウェイ３に負けた（ウェイ３よりも古い）場合、ウェイ０がウェイ２に負けていれば（ウェイ２よりも古ければ）、最も負けた（古い）ウェイ０を置換対象とすることを示す。ここでは、それ以外の関係には着目していないため、参照履歴がいかなる状態にあっても必ず１つのウェイが選択される。
【００４０】
次に、上記構成のキャッシュメモリ装置１００の動作について、図面を参照しながら説明する。図７は、キャッシュメモリ装置１００の動作を説明するためのフローチャートである。
【００４１】
メインメモリのアドレス空間の特定のアドレスに対するアクセス要求があった場合には（Ｓ１００）、まず、そのアドレスがマッチアドレス（ｍａｔｃｈ　ａｄｄｒｅｓｓ）とラインアドレス（ｌｉｎｅ　ａｄｄｒｅｓｓ）に分離される。各ウェイ１０１ａから１０１ｄ（タグＲＡＭ）がラインアドレスで検索され、各ウェイから読み出されたエントリアドレスとマッチアドレスとが比較される（Ｓ１０１）。エントリアドレスとマッチアドレスが同じであれば、そのウェイにヒットしたことになる（Ｓ１０２：Ｙｅｓ）。この場合には、ヒットしたウェイが返され、そのウェイのデータＲＡＭが保持しているメインメモリのコピーに対してアクセスされる（Ｓ１０３）。
【００４２】
一方、マッチアドレスがどのウェイのエントリアドレスにもヒットしなかった場合には（Ｓ１０２：Ｎｏ）、あるウェイの情報を書き戻して（又は無効にして）タグＲＡＭのエントリから追い出し、アクセス要求のあったアドレスのメインメモリのコピーをキャッシュに読み込む。この追い出しウェイ（置換対象のウェイ）の選択のために参照履歴が読み出される（Ｓ１０４）。ここでは、参照履歴として１１１１１１が読み出されたとする。ウェイ選択部１０２ｃは、その読み出された参照履歴に基づいて置換対象のウェイを選択する。
【００４３】
ここでは参照履歴として１１１１１１が読み出されたので、図３から明らかなように、ＯＲ演算回路Ｃ０２は”１”を出力し、その他のＯＲ演算回路Ｃ１２、Ｃ２２、及び、Ｃ３２はそれぞれ＝”０”を出力する。これは、ウェイ選択部１０２ｃがその読み出された参照履歴１１１１１１に基づいて置換対象のウェイとしてウェイ０を選択したことを示す。
【００４４】
次に、参照履歴に１ビット誤りが検出されたか否かが判定される（Ｓ１０６）。ここでは参照履歴として１１１１１１が読み出されたので、図３から明らかなように、ＮＡＮＤ演算回路Ｃ７３はＷＡＹ３＿ＷＩＮ＝”０”を出力し、その他のＮＡＮＤ演算回路Ｃ７０からＣ７２はそれぞれ”１”を出力する。これは、ウェイ検出部１０２ａがその読み出された参照履歴１１１１１１に基づいて４つのウェイの中で最も強い一のウェイとしてウェイ３を検出したことを示す。誤り検出部１０２ｂは、ウェイ検出部１０２ａによって最も強いウェイを検出できなかった場合に、参照履歴のビット誤りを検出する。ここでは、ウェイ検出部１０２ａによって最も強いウェイ（ウェイ３）が検出されるため、誤り検出部１０２ｂは、参照履歴のビット誤りを検出しない（Ｓ１０６：Ｎｏ）。この場合、エラー報告がなされることなく、追い出しウェイが返される（Ｓ１０７）。例えば、データＲＡＭに置換対象ウェイが通知される。
【００４５】
参照履歴は、最新に参照（又は更新）されたウェイが４つのウェイの中で最も強いウェイであることを示すように更新される。このルールで参照履歴を更新する限り、ウェイ検出部１０３ａによって通常、４つのウェイの中で最も強いウェイが検出されるため、誤り検出部１０３ｂは、参照履歴のビット誤りを検出しない（Ｓ１０６：Ｎｏ）。
【００４６】
一方、Ｓ１０４において、参照履歴として１１１０１１が読み出されたとする。この参照履歴１１１０１１は、上記のルールで更新する限り、出現し得ないものである。ウェイ選択部１０３ｃは、その読み出された参照履歴に基づいて置換対象のウェイを選択する。
【００４７】
ここでは参照履歴として１１１０１１が読み出されたので、図３から明らかなように、ＯＲ演算回路Ｃ０２は”１”を出力し、その他のＯＲ演算回路Ｃ１２、Ｃ２２、及び、Ｃ３２はそれぞれれぞれ”０”を出力する。これは、ウェイ選択部１０３ｃがその読み出された参照履歴１１１０１１に基づいて置換対象のウェイとしてウェイ０を選択したことを示す。このように、本実施形態のウェイ選択部１０３ｃによれば、必ず一の置換対象のウェイが選択される。
【００４８】
次に、参照履歴に１ビット誤りが検出されたか否かが判定される（Ｓ１０６）。ここでは参照履歴として１１１０１１が読み出されたので、図３から明らかなように、ＮＡＮＤ演算回路Ｃ７０からＣ７３はそれぞれ”１”を出力する。”０”は出力されない。これは、ウェイ検出部１０３ａがその読み出された参照履歴１１１０１１に基づいて最も強いウェイが検出されなかったことを示す。誤り検出部１０３ｂは、ウェイ検出部１０３ａによって最も強いウェイを検出できなかった場合に、参照履歴のビット誤りを検出する。ここでは、ウェイ検出部１０３ａによって最も強いウェイが検出されなかったため、誤り検出部１０３ｂは、参照履歴のビット誤りを検出する（Ｓ１０６：Ｙｅｓ）。この場合、特定のアプリケーション等へエラー報告がなされ（Ｓ１０８）、追い出しウェイが返される（Ｓ１０７）。例えば、データＲＡＭに置換対象ウェイが通知される。
【００４９】
以上説明したように、本実施形態においては、Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置１００において、参照履歴に冗長ビットを付加することなく、誤り検出部１０３ｂの出力により、参照履歴のビットエラーを検出することが可能となる。
【００５０】
［その他］　本発明は、以下のように特定することができる。
（付記１）　Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置（Ｎは２以上の整数）であって、ウェイ間の勝敗関係を示すビットであって特定の強さの一のウェイを示すように更新される参照履歴に基づいて、前記特定の強さの一のウェイを検出するウェイ検出部と、前記ウェイ検出部によって特定の強さの一のウェイが検出されない場合に、参照履歴のビット誤りを検出する誤り検出部とを備える、キャッシュメモリ装置。（１）
（付記２）　前記参照履歴は、最新に参照又は更新されたウェイが特定の強さの一のウェイであることを示すように更新される、付記１に記載のキャッシュメモリ装置。（２）
（付記３）　前記特定の強さの一のウェイは、Ｎウェイの中で最も強いウェイである、付記２に記載のキャッシュメモリ装置。（３）
（付記４）　前記参照履歴に基づいて置換対象のウェイを選択するウェイ選択部をさらに備える、付記３に記載のキャッシュメモリ装置。（４）
（付記５）　前記ウェイ選択部は、置換対象のウェイとしてＮウェイの中で最も弱いウェイを選択する、付記４に記載のキャッシュメモリ装置。（５）
（付記６）　前記誤り検出部は、前記ウェイ選択部によって置換対象のウェイが選択された後に、参照履歴のビット誤りを検出する、付記５に記載のキャッシュメモリ装置。（６）
（付記７）　前記ウェイ選択部は、特定のアドレスに対するアクセス要求がいずれのウェイにもヒットしなかった場合に、置換対象のウェイを選択する、付記４に記載のキャッシュメモリ装置。（７）
（付記８）　前記誤り検出部によって参照履歴のビット誤りが検出された場合に、エラーを報告するエラー報告部をさらに備える、付記１に記載のキャッシュメモリ装置。（８）
（付記９）　Ｎウェイ（Ｎは２以上の整数）・セット・アソシアティブ方式のキャッシュメモリ装置において参照履歴のビット誤りを検出する方法であって、ウェイ間の勝敗関係を示すビットであって特定の強さの一のウェイを示すように更新される参照履歴に基づいて、前記特定の強さの一のウェイを検出するステップ、その特定の強さの一のウェイが検出されない場合に、参照履歴のビット誤りを検出するステップとを備える参照履歴のビット誤り検出方法。（９）
（付記１０）　前記参照履歴は、最新に参照又は更新されたウェイが特定の強さの一のウェイであることを示すように更新される、付記９に記載の参照履歴のビット誤り検出方法。（１０）
【００５１】
本発明は、その精神または主要な特徴から逸脱することなく、他の様々な形で実施することができる。このため、上記の実施形態は、あらゆる点で単なる例示にすぎず、限定的に解釈されるものではない。
【００５２】
【発明の効果】
以上説明したように、本発明によれば、Ｎウェイ・セット・アソシアティブ方式のキャッシュメモリ装置において、参照履歴に冗長ビットを付加することなく、参照履歴のビットエラーを検出することが可能になる。
【図面の簡単な説明】
【図１】本発明の実施形態である４ウェイ・セット・アソシアティブ方式のキャッシュメモリ装置の概略構成を説明するための図である。
【図２】本発明の実施形態である４ウェイ・セット・アソシアティブ方式のキャッシュメモリ装置における参照履歴の意味を説明するための図である。
【図３】本発明の実施形態である４ウェイ・セット・アソシアティブ方式のキャッシュメモリ装置における置換ウェイ選択部１０３の概略構成を説明するための図である。
【図４】本発明の実施形態である４ウェイ・セット・アソシアティブ方式のキャッシュメモリ装置における参照履歴の例である。
【図５】本発明の実施形態である４ウェイ・セット・アソシアティブ方式のキャッシュメモリ装置における参照履歴の例である。
【図６】本発明の実施形態である４ウェイ・セット・アソシアティブ方式のキャッシュメモリ装置における参照履歴の例である。
【図７】本発明の実施形態である４ウェイ・セット・アソシアティブ方式のキャッシュメモリ装置の動作を説明するためのフローチャートである。
【図８】本発明の実施形態である４ウェイ・セット・アソシアティブ方式のキャッシュメモリ装置の従来例の動作を説明するためのフローチャートである。
【符号の説明】
１００　　　キャッシュメモリ装置
１０１　　　ウェイ（タグＲＡＭ）
１０２　　　ウェイ（データＲＡＭ）
１０３　　　置換ウェイ選択部
１０３ａ　　ウェイ検出部
１０３ｂ　　誤り検出部
１０３ｃ　　ウェイ選択部
【図１】
2004038299.tif 000003
【図２】
2004038299.tif 000004
【図３】
2004038299.tif 000005
【図４】
2004038299.tif 000006
【図５】
2004038299.tif 000007
【図６】
2004038299.tif 000008
【図７】
2004038299.tif 000009
【図８】
2004038299.tif 000010