(57)【特許請求の範囲】
【請求項１】
タグメモリとしてCAM（Content Addressable Memory）とSRAM（Static Random Access Memory）を有し、
タグアドレスの一部をCAMサブタグアドレスとして、前記タグアドレスの他の部分をSRAMサブタグアドレスとして設定し、同一の前記CAMサブタグアドレスに対し、複数の前記SRAMサブタグアドレスを対応付けることを容認し、
ヒットミス判定時に、前記CAMサブタグアドレスで前記CAM内の比較対象となるラインを検索し、
前記CAMサブタグアドレスが一致するラインが存在する場合、
前記CAMサブタグアドレスが一致するラインのうち、少なくとも、最近読み出しが要求された第１世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索し、
前記第１世代のラインに前記SRAMサブタグアドレスが一致するラインが存在しないとき、
前記CAMサブタグアドレスが一致するラインのうち、前記最近ではない時期に読み出しが要求された第２世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索する
キャッシュメモリ。
【請求項２】
タグメモリとしてCAM（Content Addressable Memory）とSRAM（Static Random Access Memory）を有するキャッシュメモリであって、
前記タグメモリのアドレスであるタグアドレスの一部がCAMサブタグアドレスとして、前記タグアドレスの他の部分がSRAMサブタグアドレスとしてそれぞれ設定され、かつ、同一の前記CAMサブタグアドレスに対し、複数の前記SRAMサブタグアドレスが対応付けられることが容認されており、
ヒットミス判定時に、前記CAMサブタグアドレスで前記CAM内の比較対象となるラインを検索する第１検索手段と、
前記CAMサブタグアドレスが一致するラインが存在する場合、
前記CAMサブタグアドレスが一致するラインのうち、少なくとも、最近読み出しが要求された第１世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索し、
前記第１世代のラインに前記SRAMサブタグアドレスが一致するラインが存在しないとき、
前記CAMサブタグアドレスが一致するラインのうち、前記最近ではない時期に読み出しが要求された第２世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索する第２検索手段と
を含むキャッシュメモリ。
【請求項３】
前記第１検索手段による前記CAMサブタグアドレスの比較によりラインが検索されないとき、または前記第２検索手段により前記SRAMサブタグアドレスの比較により第２世代のラインが検索されないとき、接続するメインメモリより前記読み出しが要求されたタグアドレスに対応するラインを読み出し、前記第２世代のラインのうち、最も古く読み出されたラインを、前記メインメモリより読み出されたラインで置換し、併せて前記CAMサブタグアドレス、およびSRAMサブタグアドレスを置換する置換手段をさらに含む
ことを特徴とする請求項２に記載のキャッシュメモリ。
【請求項４】
前記置換手段は、一の前記CAMサブタグアドレスに対し、複数の前記SRAMサブタグアドレスが対応付けられて置換されることを許容する
ことを特徴とする請求項３に記載のキャッシュメモリ。
【請求項５】
前記SRAMサブタグアドレスにより管理される各ラインが読み出された時期に基づいて、前記ラインが第１世代であるか、または、前記第２世代であるかを世代管理リストにより管理し、前記置換手段により前記メインメモリより読み出されたラインで、前記最も古く読み出されたラインが置換されるとき、前記SRAMサブタグアドレスにより管理されるラインが読み出された時期が、最も古く読み出されたラインを削除し、前記メインメモリより読み出されたラインを、最近読み出された時期として世代管理リストを更新する世代管理手段をさらに含む
ことを特徴とする請求項３に記載のキャッシュメモリ。
【請求項６】
前記世代管理手段は、前記世代管理リストに基づいて、前記SRAMサブタグアドレスにより管理される各ラインについて、最近読み出されたラインを第１世代のラインとし、最近ではない時期に読み出されたラインを第２世代のラインとして、世代管理する
ことを特徴とする請求項５に記載のキャッシュメモリ。
【請求項７】
前記CAMおよび前記SRAMの連想度ｎが連想度３２であって、前記タグアドレスが２４ビットの場合、前記CAMサブタグアドレスが２ビットであり、前記SRAMサブタグアドレスが２２ビットである
ことを特徴とする請求項２に記載のキャッシュメモリ。
【請求項８】
前記連想度ｎが連想度３２の前記CAMサブタグアドレスで管理されるラインのうち、前記第１世代のラインは、読み出された時期が最近に近い順に上位２位までのラインである
ことを特徴とする請求項７に記載のキャッシュメモリ。
【請求項９】
複数の請求項２乃至８のいずれかに記載のキャッシュメモリと、
前記CAMおよび前記SRAMと接続されたCPU（Central Processing Unit）と、
前記CPUより前記タグアドレスで指定されるラインの読み出し、または書き込みが要求された場合、前記タグアドレスより前記CAMサブタグアドレスを抽出するCAMサブタグアドレス抽出手段と、
前記CPUより前記タグアドレスで指定されるラインの読み出し、または書き込みが要求された場合、前記タグアドレスより前記SRAMサブタグアドレスを抽出するSRAMサブタグアドレス抽出手段とを含むことを特徴とするプロセッサ。
【請求項１０】
タグメモリとしてCAM（Content Addressable Memory）とSRAM（Static Random Access Memory）を有するキャッシュメモリの制御方法であって、
前記タグメモリのアドレスであるタグアドレスの一部がCAMサブタグアドレスとして、前記タグアドレスの他の部分がSRAMサブタグアドレスとしてそれぞれ設定され、かつ、同一の前記CAMサブタグアドレスに対し、複数の前記SRAMサブタグアドレスが対応付けられることが容認されており、
ヒットミス判定時に、前記CAMサブタグアドレスで前記CAM内の比較対象となるラインを検索する第１検索ステップと、
前記CAMサブタグアドレスが一致するラインが存在する場合、
前記CAMサブタグアドレスが一致するラインのうち、少なくとも、最近読み出しが要求された第１世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索し、
前記第１世代のラインに前記SRAMサブタグアドレスが一致するラインが存在しないとき、
前記CAMサブタグアドレスが一致するラインのうち、前記最近ではない時期に読み出しが要求された第２世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索する第２検索ステップと
を含むキャッシュメモリの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュメモリおよびその制御方法に関し、特に、性能を低減させること無く、低電力で動作できるようにしたキャッシュメモリおよびその制御方法に関する。
【背景技術】
【０００２】
近年、パーソナルコンピュータなどの情報処理装置において、CPU（Central Processing Unit）とメインメモリとの性能差を吸収し、処理を円滑に実行させるものとしてキャッシュメモリが欠かせない存在となっている。【０００３】
キャッシュメモリとは、CPUなど処理装置がデータや命令などの情報を取得または更新する際にメインメモリやバスなどの遅延または低帯域を隠蔽化させ、処理装置と記憶装置の性能差を埋めるために用いる高速小容量メモリである。【０００４】
コンピュータは以前から記憶装置の性能が処理装置の性能に追いつけず、この差が全体性能に対するボトルネックとされてきた（ノイマンズ・ボトルネック）。そして、ムーアの法則に基づく処理装置の加速度的な高性能化により現在ではますますこの差が拡大されている。キャッシュメモリは、記憶階層の観点からこれを解消しようとするものであり、一般に、主記憶装置（メインメモリ）とCPUなど処理装置との間に構成される。【０００５】
従来のキャッシュメモリの構成として、図１で示される４ウェイセットアソシアティブ方式のものが知られている。【０００６】
図１の場合、キャッシュメモリは、４ウェイ（連想度４）のSRAM（Static Random Access Memory）から構成されており、各ウェイ毎に、インデックスアドレスが設定され、そのインデックスアドレス毎にタグアドレスが設けられており、このタグに対応付けてデータが記憶されている。図１においては、各ウェイは、００，０１，１０，１１の２ビットの識別情報で区別されて管理されている。また、アドレスは、図１の上部で示されるように、タグアドレスとインデックスアドレスから構成されている。すなわち、図１においては、１個のインデックスアドレスが特定されると、４個のタグが特定される。ここで、ウェイとは、同一のインデックスアドレスにより指定できるタグアドレスの数のことであり、連想度とも言う。【０００７】
図１のキャッシュメモリの場合、CPUがアドレスを指定して、データの読み出しを要求すると、まず、アドレスのうち、インデックスアドレスに基づいてデータが特定される。図１の場合、４ウェイで構成されているため、インデックスアドレスが特定されることにより、同一のインデックスアドレスに対して、４個の各ウェイのタグアドレスが指定されるため、４個の読み出しデータの候補が特定される。【０００８】
次に、CPUにより指定されたアドレスのうちのタグアドレスの情報と、各ウェイのタグアドレスとを比較し、比較結果を出力すると共に、タグアドレスで指定される４個のデータが同時に読み出される。この結果、一致するタグアドレスが存在した場合、キャッシュメモリには、CPUから要求されたデータが存在する（キャッシュヒットする）ことになる。そこで、出力された４個のデータのうち、同一のタグアドレスで管理されていたデータのみがCPUに供給され、その他のデータは破棄される。一方、同一のタグアドレスがない場合、キャッシュメモリには、CPUから要求されたデータが存在しない（キャッシュミスする）ことになるので、キャッシュメモリは、要求されたアドレスのデータをメインメモリより読み出して、CPUに供給すると共に、最も前のタイミングで読み出されたデータに上書き更新する。【０００９】
しかしながら、この手法では、アドレスのうちインデックスアドレスで特定できるのはウェイ数分の候補だけであり、さらに、この中で必要とされるデータは０または１であることから、インデックスアドレスで特定されたデータが、仮に用いられても、（ウェイ数−１）個分のミスが発生することとなる。SRAMは、読み出しの際に消費される電力が大きいため、ミスを低減させない限り消費電力の低減を期待できない。このため、インデックスアドレスで特定されるデータの個数、つまり、ウェイ数を減らさない限り消費電力を低減させることができない。しかしながら、ウェイ数が減れば、キャッシュヒット率は低減することとなるため、性能を低減させる一因となってしまう。【００１０】
そこで、このように１のインデックスアドレスで特定されるデータ数に起因するミスを低減させるために、CAM（Content Addressable Memory）を用いた高連想度キャッシュメモリが提案されている。【００１１】
図２は、この高連想度キャッシュメモリの構成を示している。図２の高連想度キャッシュメモリは、ラインサイズが３２bytesであり、容量が８KBとなる３２ウェイの高連想度キャッシュメモリである。図２の高連想度キャッシュメモリにおいては、上述したインデックスアドレスに対応する８個のサブバンク（各１KB）に区切ることにより、１回のCPUからの要求（以下キャッシュアクセスとも称する）に対して、１のサブバンクだけをアクティブにし、他のサブバンクの電力消費を低減することで、電力削減が図られている。【００１２】
すなわち、アドレスのうちインデックスアドレスの情報がデコーダ（decoder）によりデコードされて、キャッシュアクセスすべきサブバンクに供給される。これにより、特定されたサブバンクのみがアクティブにされ、アクティブにされたバンクにおける、タグアドレスを管理するCAMにタグアドレスの情報を供給する。CAMは、供給されたタグアドレスに基づいて、全ウェイについて検索する。そして、アクティブな１個のサブバンクにおいては、CAMにより全ウェイに対して並列にタグアドレスとの比較が行われ、一致したタグアドレスに対応して格納されているデータだけがSRAMより出力される。
【００１３】
しかしながら、CAMを駆動させる場合、各ウェイについて全てのタグアドレスとの比較が実行されるため、１回のCPUからの読み出しに対して、連想度分のCAMが駆動されることにより電力消費が大きいという問題があった。【００１４】
そこで、この問題を解決させるために、いくつかの手法が提案されているが、その中にLPHAC（Low Power Highly Associa-tive Cache）法と呼ばれるものがある（非特許文献１参照）。【００１５】
LPHAC法は、タグアドレスが２４ビットで構成される場合、図３で示されるように、タグアドレス（以下、単にタグとも称する）を上位ビットと下位ビットの２つのサブタグアドレス（以下、単にサブタグとも称する）に分ける手法である。従来の高連想度キャッシュでは、図３のタグアドレス構成（ａ）で示されるように、全てCAMで管理するタグアドレス（以下、CAMタグとも称する）で構成されている。これに対し、LPHAC法では、図３のタグアドレス構成（ｂ）で示されるように、タグアドレスの下位ｓビットのサブタグアドレスをCAMで管理し（以下、CAMサブタグアドレスまたはCAMサブタグとも称する）、上位ビット（この例では２４−ｓビット）のサブタグアドレスをSRAMで管理する（以下、SRAMサブタグアドレスまたはSRAMサブタグとも称する）。例えば、ウェイ数が３２の場合、各ラインを区別するにはｓ≧５ビット以上必要となる。【００１６】
動作は、はじめにCAMサブタグアドレスとの部分的な比較検索が行われ、このときに検索できなければ（ミスすれば）キャッシュミスとなる。非特許文献１によれば、ｓ＝８のとき、CAMサブタグアドレスとの部分的な比較検索のみでキャッシュミスの８５％が判明するといわれている。そして、CAMサブタグアドレスでヒットした場合は、ヒットしたラインに対してSRAMサブタグアドレスとの比較検索が行われる。より詳細には、最初の半クロックでCAMサブタグアドレスとの部分的な比較検索が行われ、後半の半クロックで、CAMサブタグアドレスで特定されたラインについて、SRAMサブタグアドレスによる部分的な比較検索が行われ、同時に、データが読み出される。【００１７】
ここで、図４を参照して、具体的な比較検索例を参照して説明する。尚、図４においては、説明の便宜上、アドレスが、６ビットからなる場合の比較検索例について説明する。【００１８】
まず、図４の比較例ａで示されるように、アドレスが「１０１０００」であって、CAMサブタグが「１０００」、およびSRAMサブタグが「１０」である場合、図示せぬキャッシュメモリにCAMサブタグとして、「１１１１」、「０１０１」、および「１０００」が登録されており、それらに対応付けて、SRAMサブタグが「１１」、「１０」、および「１０」として登録されているものとする。すなわち、比較例ａにおいては、アドレス「１１１１１１」，「１００１０１」，「１０１０００」に対応するデータが図示せぬキャッシュメモリに記憶されている。【００１９】
比較例ａの場合、入力されたアドレス（入力アドレス）のCAMサブタグが用いられて、キャッシュメモリ内のCAMサブタグが部分的に比較検索されることにより、図中丸印で囲まれて示されるように、３段目の「１０００」が一致するものとして検索されることになるので、キャッシュヒットとなる。このため、CAMサブタグ「１０００」に対応付けて登録されているSRAMサブタグ「１０」と、入力アドレスのSRAMサブタグと比較検索されるが一致するので、同時に読み出されたデータがCPUに読み出されることになる。【００２０】
また、図４の比較例ｂで示されるように、アドレスが「１０００００」であって、CAMサブタグが「００００」、およびSRAMサブタグが「１０」である場合、図示せぬキャッシュメモリには、CAMサブタグとして、「１１１１」、「０１０１」、および「１０００」が登録されており、それらに対応付けて、SRAMサブタグが「１１」、「１０」、および「１０」として登録されているものとする。すなわち、比較例ｂにおいては、アドレス「１１１１１１」，「１００１０１」，「１０１０００」に対応するデータが図示せぬキャッシュメモリに記憶されている。【００２１】
比較例ｂの場合、まず、入力アドレスのCAMサブタグが用いられて、キャッシュメモリ内のCAMサブタグが比較検索されることにより、「００００」が検索されるが一致するCAMサブタグがない。すなわち、この場合、キャッシュミスとなる。ところが、CAMサブタグは、４ウェイであり、図４の比較例ｂにおいては、１ウェイ分の空きがある。そこで、メインメモリよりアドレス「１０００００」に対応するデータが読み出されて、CPUに供給されると共に、図４の比較例ｃで示されるように、キャッシュメモリには、空いている最下段の１ウェイにCAMサブタグ「００００」が登録され、さらに、対応付けてSRAMサブタグ「１０」が登録されて、今メインメモリから読み出されたデータが登録される。【００２２】
さらに、図４の比較例ｄで示されるように、入力アドレスが「００１０００」であって、CAMサブタグが「１０００」、およびSRAMサブタグが「００」である場合、CAMサブタグとして、「１１１１」、「０１０１」、および「１０００」が登録されており、それらに対応付けて、SRAMサブタグが「１１」、「１０」、および「００」として登録されているものとする。すなわち、比較例ｄにおいては、アドレス「１１１１１１」，「１００１０１」，「１０１０００」に対応するデータが図示せぬキャッシュメモリに記憶されている。【００２３】
このとき、まず、入力アドレスのCAMサブタグが用いられて、キャッシュメモリ内のCAMサブタグが比較検索されることにより、「１０００」が検索されて、図中丸印で囲んで示されるように、同一のものが検索される。次に、入力アドレスのSRAMサブタグと、検索されたSRAMサブタグ「１０」とが比較検索されるが、図中の×印で示されるように一致しない。すなわち、この場合、キャッシュミスとなる。しかしながら、既に、CAMサブタグとして「１０００」が登録されていることから、１ウェイ分の空きがあっても、メインメモリから新たにアドレスが「００１０００」に対応するデータが読み出されて登録されると、CAMサブタグ「１０００」に対して重複して、SRAMサブタグ「００」が登録されてしまう。すなわち、同一のCAMサブタグ「１０００」が重複して登録されて、それぞれSRAMサブタグ「１０」、および「００」が登録されてしまう。【００２４】
ところが、LPHAC法においては、同一のCAMサブタグの重複が回避されるように登録が管理される。このため、メインメモリよりアドレス「００１０００」に対応するデータが読み出されて、CPUに供給されると共に、図４の比較例ｅで示されるように、登録済みのCAMサブタグ「１０００」に対応付けて、新たに読み出されたSRAMサブタグ「００」が上書きされて、図示せぬ今メインメモリから読み出されたデータが登録される。すなわち、この場合、登録されていたアドレス「１０１０００」に対応するデータは、破棄され、CAMサブタグ「１０００」に対応付けて登録されるSRAMサブタグが１に維持される。
【先行技術文献】
【非特許文献】
【００２５】
【非特許文献１】Zhang, C.: A Low Power Highly Associa-tive Cache for Embedded Systems, Proc. IEEE ICCD, pp.31-36 (2006).
【発明の概要】
【発明が解決しようとする課題】
【００２６】
ところで、上述したLPHAC法では、CAMサブタグのミスによる置換はLRU（Least Recently Used）方式で行うことが前提とされている。LRU方式とは、最も古くアクセスされたデータを、最近読み出されたデータで上書きする方式である。すなわち、時間的局所性に鑑みれば、過去最もアクセスのなかったデータは将来にわたってもアクセスされる可能性は少ないと言える。従って、この方法はヒット率を向上させるための方法としてよく採用されている。【００２７】
従って、CAMサブタグでヒットした場合、一般には複数のSRAMサブタグに対応するCAMサブタグと一致することになるが、LPHAC法ではCAMサブタグとの部分的な比較検索において、ヒットするデータが上述したように1個に絞られる。【００２８】
すなわち、CAMサブタグでヒットし、SRAMサブタグでミスした場合、ミスしたデータが置換される対象のデータとされる（新たに読み出されたデータにより置換されて、消滅してしまうデータとされる）。これにより、CAMサブタグのビット数ｓ≧５ビットであればCAMサブタグの部分的な比較検索により複数のデータと一致しないようにできる。【００２９】
しかしながら、LPHAC法では、CAMサブタグでヒットし、SRAMサブタグでミスした場合、ミスしたデータが置換される対象データとされることによりヒットするデータが1個に絞られる。この場合、LRU方式とは異なる置換方式を取らざるを得ず、比較的最近アクセスがあったデータであっても置換により消滅してしまう可能性があり、結果として、ヒット率が低下してしまう原因となっていた。【００３０】
また、CAMサブタグのビット数ｓを小さく設定すると、このようなケースが増加し、LRU方式とは異なる置換方式を取る頻度が上がる。これにより、CAMサブタグのビット数ｓを小さく設定することができないため、LPHAC法では、消費電力の大きなCAM部分の縮小に限界があり、消費電力の低減には限界があった。【００３１】
本発明はこのような状況に鑑みてなされたものであり、特に、キャッシュメモリのヒット率を低減させること無く、消費電力を低減できるようにするものである。
【課題を解決するための手段】
【００３２】
本発明の第１の側面のキャッシュメモリは、タグメモリとしてCAM（Content Addressable Memory）とSRAM（Static Random Access Memory）を有し、タグアドレスの一部をCAMサブタグアドレスとして、前記タグアドレスの他の部分をSRAMサブタグアドレスとして設定し、同一の前記CAMサブタグアドレスに対し、複数の前記SRAMサブタグアドレスを対応付けることを容認し、ヒットミス判定時に、前記CAMサブタグアドレスで前記CAM内の比較対象となるラインを検索し、前記CAMサブタグアドレスが一致するラインが存在する場合、前記CAMサブタグアドレスが一致するラインのうち、少なくとも、最近読み出しが要求された第１世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索し、前記第１世代のラインに前記SRAMサブタグアドレスが一致するラインが存在しないとき、前記CAMサブタグアドレスが一致するラインのうち、前記最近ではない時期に読み出しが要求された第２世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索する。
【００３３】
本発明の第２の側面のキャッシュメモリは、タグメモリとしてCAM（Content Addressable Memory）とSRAM（Static Random Access Memory）を有するキャッシュメモリであって、前記タグメモリのアドレスであるタグアドレスの一部がCAMサブタグアドレスとして、前記タグアドレスの他の部分がSRAMサブタグアドレスとしてそれぞれ設定され、かつ、同一の前記CAMサブタグアドレスに対し、複数の前記SRAMサブタグアドレスが対応付けられることが容認されており、ヒットミス判定時に、前記CAMサブタグアドレスで前記CAM内の比較対象となるラインを検索する第１検索手段と、前記CAMサブタグアドレスが一致するラインが存在する場合、前記CAMサブタグアドレスが一致するラインのうち、少なくとも、最近読み出しが要求された第１世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索し、前記第１世代のラインに前記SRAMサブタグアドレスが一致するラインが存在しないとき、前記CAMサブタグアドレスが一致するラインのうち、前記最近ではない時期に読み出しが要求された第２世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索する第２検索手段とを含む。
【００３５】
前記第１検索手段による前記CAMサブタグアドレスの比較によりラインが検索されないとき、または前記第２検索手段により前記SRAMサブタグアドレスの比較により第２世代のラインが検索されないとき、接続するメインメモリより前記読み出しが要求されたタグアドレスに対応するラインを読み出し、前記第２世代のラインのうち、最も古く読み出されたラインを、前記メインメモリより読み出されたラインで置換し、併せて前記CAMサブタグアドレス、およびSRAMサブタグアドレスを置換する置換手段をさらに含ませるようにすることができる。
【００３６】
前記置換手段には、一の前記CAMサブタグアドレスに対し、複数の前記SRAMサブタグアドレスが対応付けられて置換されることを許容するようにさせることができる。
【００３７】
前記SRAMサブタグアドレスにより管理される各ラインが読み出された時期に基づいて、前記ラインが第１世代であるか、または、前記第２世代であるかを世代管理リストにより管理し、前記置換手段により前記メインメモリより読み出されたラインで、前記最も古く読み出されたラインが置換されるとき、前記SRAMサブタグアドレスにより管理されるラインが読み出された時期が、最も古く読み出されたラインを削除し、前記メインメモリより読み出されたラインを、最近読み出された時期として世代管理リストを更新する世代管理手段をさらに含ませるようにすることができる。
【００３８】
前記世代管理手段には、前記世代管理リストに基づいて、前記SRAMサブタグアドレスにより管理される各ラインについて、最近読み出されたラインを第１世代のラインとし、最近ではない時期に読み出されたラインを第２世代のラインとして、世代管理させるようにすることができる。
【００３９】
前記CAMおよび前記SRAMの連想度ｎが連想度３２であって、前記タグアドレスが２４ビットの場合、前記CAMサブタグアドレスが２ビットとし、前記SRAMサブタグアドレスが２２ビットとすることができる。
【００４０】
前記連想度ｎが連想度３２の前記CAMサブタグアドレスで管理されるラインのうち、前記第１世代のラインは、読み出された時期が最近に近い順に上位２位までのラインとすることができる。
【００４１】
本発明のプロセッサは、複数の請求項２乃至８のいずれかに記載のキャッシュメモリと、
前記CAMおよび前記SRAMと接続されたCPU（Central Processing Unit）と、前記CPUより前記タグアドレスで指定されるラインの読み出し、または書き込みが要求された場合、前記タグアドレスより前記CAMサブタグアドレスを抽出するCAMサブタグアドレス抽出手段と、前記CPUより前記タグアドレスで指定されるラインの読み出し、または書き込みが要求された場合、前記タグアドレスより前記SRAMサブタグアドレスを抽出するSRAMサブタグアドレス抽出手段とを含むことを特徴とする。
【００４２】
本発明の第２の側面のキャッシュメモリの制御方法は、タグメモリとしてCAM（Content Addressable Memory）とSRAM（Static Random Access Memory）を有するキャッシュメモリの制御方法であって、前記タグメモリのアドレスであるタグアドレスの一部がCAMサブタグアドレスとして、前記タグアドレスの他の部分がSRAMサブタグアドレスとしてそれぞれ設定され、かつ、同一の前記CAMサブタグアドレスに対し、複数の前記SRAMサブタグアドレスが対応付けられることが容認されており、ヒットミス判定時に、前記CAMサブタグアドレスで前記CAM内の比較対象となるラインを検索する第１検索ステップと、前記CAMサブタグアドレスが一致するラインが存在する場合、前記CAMサブタグアドレスが一致するラインのうち、少なくとも、最近読み出しが要求された第１世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索し、前記第１世代のラインに前記SRAMサブタグアドレスが一致するラインが存在しないとき、前記CAMサブタグアドレスが一致するラインのうち、前記最近ではない時期に読み出しが要求された第２世代のラインだけを比較対象とするラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインを検索する第２検索ステップとを含む。
【００４３】
本発明の第１の側面においては、タグメモリとしてCAM（Content Addressable Memory）とSRAM（Static Random Access Memory）を有し、タグアドレスの一部がCAMサブタグアドレスとして、前記タグアドレスの他の部分がSRAMサブタグアドレスとして設定され、同一の前記CAMサブタグアドレスに対し、複数の前記SRAMサブタグアドレスが対応付けられることが容認され、ヒットミス判定時に、前記CAMサブタグアドレスで前記CAM内の比較対象となるラインが検索され、前記CAMサブタグアドレスが一致するラインが存在する場合、前記CAMサブタグアドレスが一致するラインのうち、少なくとも、最近読み出しが要求された第１世代のラインだけが比較対象とされるラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象とされるラインが検索され、前記第１世代のラインに前記SRAMサブタグアドレスが一致するラインが存在しないとき、前記CAMサブタグアドレスが一致するラインのうち、前記最近ではない時期に読み出しが要求された第２世代のラインだけが比較対象とされるラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象とされるラインが検索される。
【００４４】
本発明の第２の側面においては、タグメモリとしてCAM（Content Addressable Memory）とSRAM（Static Random Access Memory）を有し、前記タグメモリのアドレスであるタグアドレスの一部がCAMサブタグアドレスとして、前記タグアドレスの他の部分がSRAMサブタグアドレスとしてそれぞれ設定され、かつ、同一の前記CAMサブタグアドレスに対し、複数の前記SRAMサブタグアドレスが対応付けられることが容認され、ヒットミス判定時に、前記CAMサブタグアドレスで前記CAM内の比較対象とされるラインが検索され、前記CAMサブタグアドレスが一致するラインが存在する場合、前記CAMサブタグアドレスが一致するラインのうち、少なくとも、最近読み出しが要求された第１世代のラインだけが比較対象とされるラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象とされるラインが検索され、前記第１世代のラインに前記SRAMサブタグアドレスが一致するラインが存在しないとき、前記CAMサブタグアドレスが一致するラインのうち、前記最近ではない時期に読み出しが要求された第２世代のラインだけが比較対象とされるラインとして、前記SRAMサブタグアドレスで前記SRAM内の比較対象となるラインが検索される。
【発明の効果】
【００４５】
本発明の一側面によれば、キャッシュメモリのヒット率を低減させること無く、消費電力を低減させることが可能となる。
【図面の簡単な説明】
【００４６】
【図１】従来のキャッシュメモリの構成を示す図である。
【図２】その他の従来のキャッシュメモリの構成を示す図である。
【図３】LPHAC法を説明する図である。
【図４】LPHAC法を説明する図である。
【図５】本発明を適用した一実施の形態の構成例であるキャッシュメモリにより実現される機能を説明する機能ブロック図である。
【図６】キャッシュメモリに格納されるデータの管理構造を説明する図である。
【図７】プログラム実行処理を説明するフローチャートである。
【図８】命令キャッシュ処理を説明するフローチャートである。
【図９】キャッシュヒットミス判定処理を説明するフローチャートである。
【図１０】キャッシュヒットミス判定処理を説明する図である。
【図１１】データキャッシュ（書き込み）処理を説明するフローチャートである。
【図１２】データキャッシュ（読み出し）処理を説明するフローチャートである。
【図１３】本発明の効果を説明する図である。
【図１４】本発明の効果を説明する図である。
【図１５】本発明の効果を説明する図である。
【図１６】本発明の効果を説明する図である。
【発明を実施するための最良の形態】
【００４７】
［本発明を適用したキャッシュメモリの構成例］
図５は、本発明を適用したキャッシュメモリにより実現される機能の一実施の形態の構成例を示す機能ブロック図である。【００４８】
CPU（Central Processing Unit）１１は、各種の処理を実行させるとき、プログラムカウンタより実行すべき命令のアドレスをアドレス入力部１２に供給し、キャッシュメモリ１３に対してデータを要求すると共に取得して実行する。【００４９】
アドレス入力部１２は、CPU１１より命令を指定するアドレスが供給されると、インデックスアドレスをキャッシュメモリ１３のデコード部４１に供給すると共に、タグアドレスのうち、CAM（Content Addressable Memory）サブタグアドレスをキャッシュメモリ１３のCAM５１に供給すると共に、SRAM（Static Random Access Memory）サブタグアドレスをSRAM５２に供給する。より詳細には、アドレス入力部１２は、インデックスアドレス抽出部２１、およびタグアドレス抽出部２２を備えている。インデックスアドレス抽出部２１は、入力されたアドレスよりインデックスアドレスを抽出し、抽出したインデックスアドレスをデコード部４１に供給する。【００５０】
タグアドレス抽出部２２は、さらにCAMサブタグアドレス抽出部２２ａおよびSRAMサブタグアドレス抽出部２２ｂを備えている。CAMサブタグアドレス抽出部２２ａは、入力アドレスに含まれるタグアドレスが、例えば、Xビットである場合、その下位sビットをCAMサブタグアドレスとして抽出してキャッシュメモリ１３内にある各サブバンク４２のCAM５１に供給する。また、SRAMサブタグアドレス抽出部２２ｂは、入力アドレスに含まれるタグアドレスのうち、CAMサブタグアドレス以外の上位（X−s）ビットをSRAMサブタグとして抽出してキャッシュメモリ１３内にある各サブバンク４２のSRAM５２に供給する。【００５１】
キャッシュメモリ１３は、デコード部４１、およびサブバンク４２より構成されている。デコード部４１は、アドレス入力部１２より供給されてくるインデックスアドレスを解析し、いずれのサブバンク４２を起動させるかを判定し、起動させるべきサブバンク４２に対して起動を指示する信号を供給する。尚、図５においては、サブバンク４２の構成を示すため、便宜上サブバンク４２が１個のみ表示されているが、実際には、複数のサブバンク４２が設けられている。すなわち、デコード部４１とサブバンク４２の関係については、図２で示される構成と同様の関係となっており、デコード部４１より起動を指示する信号が供給されたサブバンクのみがオンの状態とされ、オンの状態となったサブバンク４２のみが、タグアドレスの情報に基づいて処理を実行する。【００５２】
サブバンク４２には、CAM５１、SRAM５２、LRU管理部５３、読出部５４、および置換部５５を備えている。CAM５１は、デコード部４１より供給されてくる起動を指示する信号に基づいて動作を開始し、CAMサブタグアドレス抽出部２２ａより供給されてくるCAMサブタグアドレスに基づいて、CPU１１で指定したアドレスのデータの候補を検索し、検索結果をヒットフラグとしてSRAM５２に供給する。【００５３】
SRAM５２は、CAM５１からのヒットフラグの情報、およびSRAMサブタグアドレスに基づいて、CPU１１がアドレスで指定したデータを検索し、データが検索できた場合、CPU１１に出力する。また、SRAM５２は、CPU１１がアドレスで指定したデータが検索できなかった場合、メインメモリ１４にアクセスし、そのデータを読み出して、CPU１１に供給すると共に、最も古いデータと置換して新たに記憶する。【００５４】
より詳細には、SRAM５２は、比較検索部７１、出力部７２、書戻部７３、世代管理部７４、書戻管理部７５、書込部７６、書換部７７、および格納部７８を備えている。比較検索部７１は、世代判定部８１を制御して、CAM５１からのヒットフラグの情報により特定されている、検索されるデータの候補のうち、まず、最初の処理で第１世代のもののみを特定させる。
【００５５】
ここでいう世代とは、世代管理部７４により管理されるものであり、SRAM５２の格納部７８に格納されている各データが最近アクセスされた日時により設定される順序のうち、例えば、上位２位までのデータが第１世代に設定され、それ以下の順位のデータが第２世代に設定される。つまり、最近アクセスされた、読み出される可能性の比較的高いデータが第１世代に設定され、それ以外のデータが第２世代に設定される。尚、上位２位までが第１世代に設定される例について説明したが、それ以外の順位までを第１世代とし、それ以外のデータを第２世代としてもよいものである。【００５６】
比較検索部７１は、最初の処理で世代判定部８１を制御して、CPU１１によりアドレスで特定される読み出しが要求されたデータの候補のうち、最新のものとして分類されている第１世代のデータを特定させる。そして、比較検索部７１は、第１世代のものとして特定されたCAMサブタグアドレスで検索されたアドレスにより指定されたデータの候補のぞれぞれのSRAMサブタグアドレスと、SRAMサブタグアドレス抽出部２２ｂより供給されてきたSRAMサブタグアドレスとを比較して検索し、一致するものが検索できた場合、検索されたデータを出力部７２に供給する。【００５７】
出力部７２は、検索されたデータを取得すると、CPU１１によりアドレスで指定されている要求されたデータとして供給する。また、第１世代のものとして特定されたCAMサブタグで検索されたアドレスにより指定されたデータの候補のSRAMサブタグアドレスのうち、抽出されたSRAMサブタグアドレスと一致するものが検索できなかった場合、比較検索部７１は、世代判定部８１により第１世代と判定されなかった、すなわち、第２世代のデータのSRAMサブタグアドレスと、SRAMサブタグアドレス抽出部２２ｂより供給されてきたSRAMサブタグアドレスとを比較検索し、一致するものが検索された場合、検索されたデータを出力部７２に供給する。
【００５８】
一方、比較検索部７１は、いずれの世代においてもCPU１１によりアドレスで特定されたデータが検索できない場合、CAMサブタグアドレスの情報、およびSRAMサブタグアドレスの情報と共に、対応するデータをメインメモリ１４より読み出すように読出部５４に通知する。読出部５４は、CAMサブタグアドレス、およびSRAMサブタグアドレスの情報に基づいて、タグアドレスを特定し、メインメモリ１４にアクセスして、そのタグアドレスに対応するデータを読み出し、CPU１１に供給すると共に、CAM５１、SRAM５２、および置換部５５に対して読み出したデータのCAMサブタグ、SRAMサブタグ、およびデータそのものを供給する。【００５９】
書戻部７３は、CPU１１からの命令が書き込み処理である場合、サブバンク４２により管理するべきデータが更新されるとき、SRAM５２の格納部７８に格納されているデータを置換して更新する前に、メインメモリ１４に対応するデータを書き戻す。【００６０】
置換部５５は、CPU１１からの命令により指定されたタグアドレスの情報が検出できず、メインメモリ１４からデータが読み出された場合、新たなデータとタグアドレスとで、それまで記憶していたデータとタグアドレスとを置換して更新する。【００６１】
書込部７６は、CPU１１からの命令が書き込み処理の場合、格納部７８に格納されているデータをCPU１１からの処理結果であるデータで書き換える。【００６２】
書換部７７は、CPU１１からの命令が書き込み処理の場合、書込部７６が格納部７８に格納されているデータをCPU１１からの処理結果であるデータで書き換える前に、メインメモリにアクセスし、対応するデータを書き換える。【００６３】
尚、LRU管理部５３、世代管理部７４、および書戻管理部７５の詳細については、後述するデータ管理構造と併せて説明するものとする。【００６４】
［データ管理構造］
次に、図６を参照して、格納部７８に格納されるデータの管理構造について説明する。図６においては、垂直方向に各データ単位のラインが形成されており、ラインＬ１乃至Ｌ３２までの合計３２データが記録されていることが示されている。尚、このラインＬ１乃至Ｌ３２のそれぞれを特に区別する必要がない場合、単にラインＬと称するものとする。【００６５】
図６の各ラインＬには、左からCAMサブタグアドレス、SRAMサブタグアドレス、データ、アクセス日時情報、世代情報、および書戻フラグが含まれており、データ単位で管理される情報が示されている。このラインＬの数は、CAM５１およびSRAM５２の物理的な構成により決定されるウェイ数に相当しており、図６の例では、３２ウェイの例であることが示されている。ただし、このウェイ数は、ハードウェアの構成により決まるものであるので、ハードウェアの構成により、ウェイ数は様々な数をとることが可能であり、例えば、２，４，８，１６，３２などでもよいし、これ以外のウェイ数であってもよい。【００６６】
尚、図６においては、各データを特定するタグアドレスは、図６の左側の２列で示されている。すなわち、CAMサブタグアドレスとSRAMサブタグアドレスとが特定されることにより、CPU１１により指定されたタグアドレスのデータが検索されることになる。【００６７】
アクセス日時情報は、LRU（Least Recently Used）管理部５３のLRU管理リスト５３ａによりデータ単位（ライン単位）で管理されている情報である。すなわち、LRU（Least Recently Used）管理部５３は、LRU管理リスト５３ａを備えており、LRU管理リスト５３ａ上にデータ単位で（ライン単位で）、図６中のデータ列の右側に表示されている最近アクセスされたアクセス日時情報をデータ単位（ライン単位）で管理している。すなわち、LRU管理部５３は、SRAM５２のアクセスがある度に、LRU管理リスト５３ａを更新して、図６におけるデータ毎（ライン毎）のアクセス日時の情報を管理している。また、図６には図示されていないが、LRU管理部５３は、LRU管理リスト５３ａの情報に基づいて、各ラインを最近アクセスされた日時順に並び替えて、ライン毎の順位を求める。【００６８】
世代情報は、世代管理部７４の世代管理リスト７４ａによりデータ単位（ライン単位）で管理されている情報である。すなわち、世代管理部７４は、世代管理リスト７４ａを備えており、LRU管理部５３のLRU管理リスト５３ａにアクセスし、最近アクセスされたライン毎の日時順の情報に基づいて、世代管理リスト７４ａに、ライン単位で最近アクセスされた上位２位までのデータに第１世代データであることを示すフラグを立て、それ以外のデータについては第２世代データであることを示すため、第１世代であること示すフラグを立てないようにして管理する。【００６９】
書戻フラグは、書戻管理部７５の書戻管理リスト７５ａによりデータ単位（ライン単位）で管理されている情報である。すなわち、書戻管理部７５は、書戻管理リスト７５ａを備えており、CPU１１からの指令が書き込み処理である場合、データが更新される度に、SRAM５２のデータを更新する前に、先にメインメモリ１４のデータを書き戻して更新する必要があるので、書戻が必要となるデータにフラグを立てて管理する。すなわち、書戻管理部７５は、指令が書き込み処理であるか否かにより、書戻管理リスト７５ａを更新し、図６におけるデータ毎（ライン毎）の書戻フラグを管理している。
【００７０】
［プログラム実行処理］
次に、図７のフローチャートを参照して、プログラム実行処理について説明する。【００７１】
ステップＳ１において、CPU１１は、図示せぬプログラムカウンタより実行すべき命令のアドレスを取得し、アドレス入力部１２に供給する。この処理により、アドレス入力部１２は、CPU１１よりアドレスの入力を受け付ける。【００７２】
インデックスアドレス抽出部２１は、入力されたアドレスよりインデックスアドレスを抽出する。また、タグアドレス抽出部２２は、入力されたアドレスよりタグアドレスを抽出し、CAMサブタグアドレス抽出部２２ａおよびSRAMサブタグアドレス抽出部２２ｂに供給する。CAMサブタグアドレス抽出部２２ａは、タグアドレスの、下位sビットをCAMサブタグアドレスとして抽出してキャッシュメモリ１３内にある各サブバンク４２のCAM５１に供給する。SRAMサブタグアドレス抽出部２２ｂは、タグアドレスのうち、CAMサブタグアドレス以外の上位（X−s）ビットをSRAMサブタグアドレスとして抽出してキャッシュメモリ１３内にある各サブバンク４２のSRAM５２に供給する。【００７３】
ステップＳ２において、キャッシュメモリ１３は、命令キャッシュ処理を実行し、CPU１１に入力されたアドレスに対応するデータを読み出し、CPU１１に供給する。【００７４】
［命令キャッシュ処理］
ここで、図８のフローチャートを参照して、命令キャッシュ処理について説明する。【００７５】
ステップＳ２１において、キャッシュメモリ１３は、いずれかのサブバンク４２を指定してキャッシュヒットミス判定処理を実行させる。【００７６】
［キャッシュヒットミス判定処理］
ここで、図９のフローチャートを参照して、キャッシュヒットミス判定処理について説明する。【００７７】
ステップＳ４１において、インデックスアドレス抽出部２１は、抽出したインデックスアドレスをデコード部４１に供給する。デコード部４１は、インデックスアドレスを解析し、解析結果からキャッシュヒットミス処理を実行させるサブバンク４２を特定し、特定したサブバンク４２に対して起動を指示する信号を供給する。この処理により、起動が指示されたサブバンク４２は、電力供給を受けて起動を開始する。一方、起動が指示されていないサブバンク４２は起動されず、結果として、処理が必要とされていないサブバンク４２の電力消費が低減される。【００７８】
ステップＳ４２において、CAM５１は、タグアドレス抽出部２２のCAMサブタグアドレス抽出部２２ａより供給されてくるCAMタグアドレスと、SRAM５２内に管理されるデータに対応付けて登録されているCAMタグアドレスとを比較し、一致するものが検索されるか否かを判定する。【００７９】
すなわち、例えば、図１０の左部で示されるように、ラインＬ０のCAMサブタグアドレスが「０００１」であり、ラインＬ１が「０１０１」であり、ラインＬ２が「１００１」であり、ラインＬ３が「００００」であり、ラインＬ４が「１００１」であり、ラインＬ５が「０００１」であり、ラインＬ６が「００１０」であり、・・・ラインＬ２８が「０００１」であり、ラインＬ２９が「０１１１」であり、ラインＬ３０が「１００１」であり、ラインＬ３１が「１０００」である場合、入力されたアドレスから抽出されたCAMサブタグアドレスが「１００１」であるとき、CAM５１は、全てのラインＬのCAMサブアドレスとを比較して検索すると、図中の矢印で示されているラインＬ２，Ｌ４，Ｌ３０のCAMサブタグアドレスがヒットすることになる。そこで、このような場合、ステップＳ４２において、CAM５１は、タグアドレス抽出部２２のCAMサブタグアドレス抽出部２２ａより供給されてくるCAMサブタグアドレスと、SRAM５２内に管理されるデータに対応付けて登録されているCAMサブタグアドレスとに一致するものがあると判定し、処理は、ステップＳ４３に進む。
【００８０】
尚、図１０においては、垂直方向にラインＬごとに左からCAMサブタグアドレス、SRAMサブタグアドレス、データ、および世代情報が対応付けて示されている。また、図１０の世代情報においては、ラインＬ２，Ｌ３，Ｌ２９のみが第１世代（1st）であり、それ以外が第２世代（2nd）であることが示されている。【００８１】
ステップＳ４３において、CAM５１は、一致したCAMタグアドレス、および一致したラインＬを示す情報として、一致したラインＬに対してヒットフラグを立ててSRAM５２に供給する。この処理により、SRAM５２の比較検索部７１は、一致したCAMタグアドレスとラインＬの情報を取得する。すなわち、図１０の左部においては、ラインＬ２，Ｌ４，Ｌ３０についてヒットフラグが付されることになる。【００８２】
そして、比較検索部７１は、世代判定部８１を制御して、CAMタグアドレスが一致したラインＬのうち、第１世代のラインＬの情報を比較対象のラインＬとして検索させる。例えば、図１０の左部の場合、ラインＬ２のデータのみが第１世代に設定されているので、ラインＬ２のみが検索される。さらに、比較検索部７１は、検索されたCAMタグアドレスが一致したラインＬのうち、第１世代の、比較対象となったラインＬ２のSRAMサブタグアドレスと、SRAMサブタグアドレス抽出部２２ｂより供給されてきたSRAMサブタグアドレスとを比較すると共に、比較対象となったラインＬ２で管理されているデータを格納部７８より比較検出部７１に対して出力させる。【００８３】
ステップＳ４４において、比較検索部７１は、比較対象となった第１世代のラインＬのSRAMサブタグアドレスと、SRAMサブタグアドレス抽出部２２ｂより供給されてきたSRAMサブタグアドレスとを比較して、一致するものがあるか否かを検索する。例えば、図１０の左部の場合、検索されたのはラインＬ２のデータのみであるので、ラインＬ２のSRAMサブタグデータと、SRAMサブタグアドレス抽出部２２ｂより供給されてきたSRAMサブタグアドレスとが比較される。【００８４】
ステップＳ４４において、例えば、図１０の左部で「hit」と示されるように、SRAMサブタグアドレスの両者が一致した場合、ステップＳ４５において、比較検索部７１は、キャッシュヒットしたことを認識し、一致したSRAMサブタグアドレスに対応して格納部７８より出力されてきたデータを出力部７２に供給する。【００８５】
一方、ステップＳ４４において、一致するSRAMサブタグアドレスがない場合、ステップＳ４６において、比較検索部７１は、世代判定部８１を制御して、CAMタグアドレスが一致したラインＬのうち、第２世代のラインＬの情報を比較対象のラインＬとして検索させる。例えば、図１０の右部で示されるように、ラインＬ４，Ｌ３０のデータのみが第２世代のデータ（ラインＬ）として検索される。さらに、比較検索部７１は、検索されたCAMタグアドレスが一致したラインＬのうち、第２世代の、すなわち、比較対象となったラインＬのSRAMサブタグアドレスと、SRAMサブタグアドレス抽出部２２ｂより供給されてきたSRAMサブタグアドレスとを比較すると共に、比較対象となったラインＬで管理されているデータを格納部７８より比較検出部７１に対して出力させる。【００８６】
ステップＳ４７において、比較検索部７１は、比較対象となった第２世代のラインＬのSRAMサブタグアドレスと、SRAMサブタグアドレス抽出部２２ｂより供給されてきたSRAMサブタグアドレスとを比較して、一致するものがあるか否かを検索する。例えば、図１０の右部の場合、検索されたのはラインＬ４，Ｌ３０のデータであるので、ラインＬ４，Ｌ３０のSRAMサブタグデータと、SRAMサブタグアドレス抽出部２２ｂより供給されてきたSRAMサブタグアドレスとが比較される。【００８７】
ステップＳ４７において、例えば、図１０の右部でラインＬ３０において「hit」と示されるように、両者が一致した場合、ステップＳ４５において、比較検索部７１は、キャッシュヒットしたことを認識し、一致したSRAMサブタグアドレスに対応して格納部７８より出力されてきたデータを出力部７２に供給する。すなわち、この場合、ラインＬ４，Ｌ３０の両方のデータが格納部７８から比較検索部７１に出力されている。しかしながら、SRAMサブタグアドレスが一致したのは、図中（hit）と示されたラインＬ３０のものであるので、比較検索部７１は、ラインＬ３０のデータのみを出力部７２に供給すると共に、ラインＬ４のデータを破棄する。このように、比較検索部７１は、ヒットしたデータのみを出力部７２に供給し、キャッシュミスとなったデータを破棄する。【００８８】
一方、ステップＳ４２において、CAMサブタグアドレスに一致するものがない場合、または、ステップＳ４７において、例えば、比較対象となるSRAMタグアドレスとSRAMサブタグアドレス抽出部２２ｂより供給されてきたSRAMサブタグアドレスが一致しない場合、ステップＳ４８において、比較検索部７１は、格納部７８には、CPU１１より供給されてきたアドレスに対応するデータが格納されていない、すなわち、キャッシュミスであるものと認識し、処理は終了する。【００８９】
すなわち、まず、CAMサブタグアドレスで比較対象となるラインを検索し、一致するものがあった場合、最初は、CAMサブタグアドレスが一致するラインのうち、第１世代のものだけを比較対象とするラインとして、SRAMサブタグアドレスで検索し、一致すればキャッシュヒットであるものと判定する。また、CAMサブタグアドレスが一致するラインのうち、第１世代の比較対象とするラインを、SRAMサブタグアドレスで検索しても一致するものがないとき、CAMサブタグアドレスが一致するラインのうち、第２世代の比較対象とするラインを、SRAMサブタグアドレスで検索するようにした。【００９０】
このため、SRAMサブタグアドレスが一致する可能性の高い最近のデータを含む第１世代となる一部のラインのみを比較対象とすることができるので、SRAMサブタグアドレスでの一致の可能性の低いラインを排除することで、CAMサブタグアドレスで一致する全てのラインに対してSRAMサブタグアドレスによる検索をしないようにすることができる。【００９１】
結果として、全てのラインを比較対照としないため、キャッシュミスとなるラインが低減されてSRAM５２の消費電力としてインパクトの大きな格納部７８からの出力動作を低減させることができ、全体として消費電力を低減させることが可能となる。また、SRAMサブタグアドレスが一致する可能性の高い最近のデータを含む第１世代となる一部のラインのみを比較対象とすることができるので、ヒット率を低減させずに、消費電力を低減させることが可能となる。【００９２】
ここで、図８のフローチャートの説明に戻る。【００９３】
ステップＳ２２において、比較検索部７１は、キャッシュヒットであるか否かを判定する。【００９４】
ステップＳ２２において、例えば、上述したステップＳ４５の処理により、キャッシュヒットである場合、処理は、ステップＳ２３に進む。【００９５】
ステップＳ２３において、出力部７２は、比較検索部７１より供給されてきたデータをCPU１１に供給する。【００９６】
ステップＳ２４において、比較検出部７１は、出力部７２に供給したデータ（ライン）のCAMサブタグアドレスおよびSRAMサブタグアドレスを供給し、対応するデータにアクセスがあったことをLRU管理部５３に通知する。LRU管理部５３は、アクセスがあったことを示す情報に基づいて、LRU管理リスト５３ａを更新する。より詳細には、LRU管理部５３は、LRU管理リスト５３ａの情報のうち、アクセスがあったとして通知されてきたCAMサブタグアドレスおよびSRAMサブタグアドレスのデータの最近読み出された日時の情報を現在時刻に更新すると共に、読み出された日時の順位を第１位に更新する。尚、日時の順位を管理するに当たり、日時の情報をそのまま用いて管理すると、膨大なデータを管理する必要が生じる恐れがある。そこで、日時の順位の管理には、日時の情報をそのまま扱うのではなく、例えば、３２ウェイであれば、５ビットのカウンタビットを用いるようにして、データの順位のみを管理するようにしてもよい。【００９７】
ステップＳ２５において、世代管理部７４は、LRU管理部５３に対してLRU管理リスト５３ａを要求し、取得する。そして、世代管理部７４は、LRU管理リスト５３ａにおける上位２位までのラインについて、世代管理リスト７４ａの世代情報を第１世代に更新し、併せて、それ以外のラインについて、世代情報を第２世代に更新する。【００９８】
一方、ステップＳ２２において、キャッシュヒットではない、すなわち、キャッシュミスであったと判定された場合、処理は、ステップＳ２６に進む。【００９９】
ステップＳ２６において、比較検索部７１は、読出部５４に対して、CPU１１よりアドレスにより指定されたデータが存在しないため、メインメモリ１４より読み出すように指示すると共に、CAMサブタグアドレスおよびSRAMサブタグアドレスを供給する。読出部５４は、この指示に応じて、CAMサブタグアドレスおよびSRAMサブタグアドレスに基づいてタグアドレスを特定し、メインメモリ１４にアクセスして、データを読み出すと共に、CAM５１、比較検索部７１および置換部５５に供給する。【０１００】
ステップＳ２７において、置換部５５は、LRU管理部５３に対してLRU管理リスト５３ａを要求し、取得する。そして、置換部５５は、LRU管理リスト５３ａにおいて、最下位となるライン、すなわち、最も古いデータとタグアドレスとを検索し、読出部５４より供給されてきたデータとタグアドレスとで置換してCAM５１およびSRAM５２の格納部７８の情報を更新する。【０１０１】
以上のように命令キャッシュ処理により、CPU１１により命令の読み出しが指示されたデータについて、LRU管理リスト５３ａのアクセスされた日時が更新されて、さらに、日時に応じて設定される順位が順次更新することが可能となる。また、LRU管理リスト５３ａの更新に応じて、世代管理部７４における世代管理リスト７４ａも併せて更新することが可能となり、最近アクセスされた日時に応じて世代情報を更新させることが可能となる。【０１０２】
また、以上の処理においては、置換部５５は、同一のCAMサブタグアドレスに対して、異なる複数のSRAMサブタグアドレスが格納部７８に重複するようなデータが置換されることも認めるように処理する。この結果、格納部７８に格納されるデータは、同一のCAMサブタグアドレスに対して、SRAMサブタグアドレスが１に絞られるようなことがなく、LRU法に則って、最近アクセスされたデータが確実に置換されて格納されることとなるので、LPHAC法で見られたようなキャッシュヒット率の低下を抑制することが可能となる。【０１０３】
ここで、図７のフローチャートの説明に戻る。【０１０４】
ステップＳ２において、命令キャッシュ処理が終了すると、ステップＳ３において、CPU１１は、使用するレジスタオペランドを指定する。【０１０５】
ステップＳ４において、CPU１１は、キャッシュメモリ１３より供給されてきたデータからなる命令に対応する計算、演算、または比較等の処理を実行する。【０１０６】
ステップＳ５において、CPU１１は、実行している命令がストア命令であるか否かを判定する。ステップＳ５において、例えば、実行している命令がストア命令である場合、処理は、ステップＳ６に進む。【０１０７】
ステップＳ６において、CPU１１は、キャッシュメモリ１３に対してステップＳ１と同様にアドレスを指定してデータキャッシュ処理を指示する。これに応じてアドレス入力部１２は、入力されたアドレスにより、インデックスアドレス、CAMサブタグアドレス、およびSRAMサブタグアドレスをキャッシュメモリ１３に供給する。キャッシュメモリ１３は、このインデックスアドレス、CAMサブタグアドレス、およびSRAMサブタグアドレスに基づいて、データキャッシュ（書き込み）処理を実行する。【０１０８】
［データキャッシュ（書き込み）処理］
ここで、図１１のフローチャートを参照して、データキャッシュ（書き込み）処理について説明する。尚、図１１のフローチャートにおいて、ステップＳ６１，Ｓ６２，Ｓ６５，Ｓ６６の処理については、図８のフローチャートを参照して説明したステップＳ２１，Ｓ２２，Ｓ２４，Ｓ２５の処理と同様であるので、その説明は省略するものとする。【０１０９】
すなわち、ステップＳ６２において、例えば、キャッシュヒットであった場合、処理は、ステップＳ６３に進む。【０１１０】
ステップＳ６３において、比較検索部７１は、キャッシュヒットしたものとして検索されたラインの情報（CAMサブタグアドレス、およびSRAMサブタグアドレスの情報）を書戻管理部７５、および書込部７６に供給する。そして、書込部７６は、CPU１１の書き込み指示に従って、検索されたCAMサブタグアドレス、およびSRAMサブタグアドレスで特定されるラインに対応付けて、演算結果のデータを格納部７８に書き込む。【０１１１】
ステップＳ６４において、書戻管理部７５は、CAMサブタグアドレス、およびSRAMサブタグアドレスで特定されるラインの書き戻しフラグをオンの状態にして、書戻管理リスト７５ａを更新し、以降の処理において、そのラインが書き戻し対象であることを記録する。【０１１２】
一方、ステップＳ６２において、キャッシュヒットではない、すなわち、キャッシュミスであった場合、処理は、ステップＳ６７に進む。【０１１３】
ステップＳ６７において、比較検索部７１は、キャッシュミスしたことを示す情報を書換部７７に供給する。書換部７７は、メインメモリ１４にアクセスし、CAMサブタグアドレス、およびSRAMサブタグアドレスで特定されるタグアドレスのデータを、CPU１１より供給されてくるデータで書き換える。【０１１４】
ステップＳ６８において、書戻部７３は、LRU管理部５３および書戻管理部７５に対して、それぞれLRU管理リスト５３ａおよび書戻管理リスト７５ａを要求し、取得する。そして、書戻部７３は、LRU管理リスト５３ａにおいて、最下位となるライン、すなわち、最も古いラインを検索し、さらに、その最も古いラインについて、書戻管理リスト７５ａで照合し、書戻フラグがオンの状態であるか否かを判定する。ステップＳ６８において、例えば、最下位となるライン、すなわち、最も古いデータであって置換されるラインの書戻フラグがオンであり、書き戻し対象となっている場合、処理は、ステップＳ６９に進む。【０１１５】
ステップＳ６９において、書戻部７３は、メインメモリ１４にアクセスし、最下位となるライン、すなわち、最も古いデータであって置換される対象となっているラインの書戻フラグがオンとなっているデータをメインメモリ１４に書き戻す。【０１１６】
すなわち、この処理により、新たにCPU１１より供給されてくるデータで書き換えられて、キャッシュメモリ１３内から消滅する前に、データがメインメモリ１４に書き戻されることになる。【０１１７】
一方、ステップＳ６８において、最も古いデータであって置換されるラインの書戻フラグがオンではなく、オフとされており、書き戻し対象のラインではない場合、ステップＳ６９の処理は、スキップされる。【０１１８】
ステップＳ７０において、置換部５５は、LRU管理部５３に対してLRU管理リスト５３ａを要求し、取得する。そして、置換部５５は、LRU管理リスト５３ａにおいて、最下位となるライン、すなわち、最も古いデータとタグアドレスとを検索し、CPU１１より供給されてきたデータとタグアドレスとで置換してCAM５１およびSRAM５２の格納部７８の情報を更新する。【０１１９】
以上の処理により、書き込みデータのデータキャッシュが管理されるので、アクセス頻度の高い書き込みデータのみがキャッシュメモリ１３内で管理され、それ以外のデータについては、順次メインメモリ１４に書き戻されていく。【０１２０】
ここで、図７のフローチャートの説明に戻る。【０１２１】
ステップＳ６の処理により、データキャッシュ（書き込み）処理が完了すると、プログラム実行処理は終了する。【０１２２】
一方、ステップＳ５において、実行している命令がストア命令ではないと判定された場合、処理は、ステップＳ７に進む。ステップＳ７において、CPU１１は、実行している命令がロード命令であるか否かを判定する。ステップＳ７において、例えば、実行している命令がロード命令である場合、処理は、ステップＳ８に進む。【０１２３】
ステップＳ８において、CPU１１は、キャッシュメモリ１３に対してステップＳ１と同様にアドレスを指定してデータキャッシュ処理を指示する。これに応じてアドレス入力部１２は、入力されたアドレスにより、インデックスアドレス、CAMサブタグアドレス、およびSRAMサブタグアドレスをキャッシュメモリ１３に供給する。キャッシュメモリ１３は、このインデックスアドレス、CAMサブタグアドレス、およびSRAMサブタグアドレスに基づいて、データキャッシュ（読み出し）処理を実行する。【０１２４】
［データキャッシュ（読み出し）処理］
ここで、図１２のフローチャートを参照して、データキャッシュ（読み出し）処理について説明する。尚、図１２のフローチャートにおけるステップＳ８１乃至Ｓ８９の処理は、図１１のフローチャートにおけるステップＳ６１，Ｓ６２、図８のフローチャートにおけるステップＳ２３乃至Ｓ２６、並びに、図１１のフローチャートにおけるステップＳ６８乃至Ｓ７０の処理と同様であるので、その説明は省略する。【０１２５】
すなわち、図１２のフローチャートにおいては、図１１のフローチャートを参照して説明した処理における書き込みを対象とした処理が省略され、メインメモリ１４からの読み出し処理のみとなる。【０１２６】
ここで、図７のフローチャートの説明に戻る。【０１２７】
ステップＳ８において、データキャッシュ（読み出し）処理が終了すると、ステップＳ９において、CPU１１は、図示せぬレジスタファイルに処理結果を書き込み、処理を終了する。【０１２８】
また、ステップＳ７において、命令がロード命令ではない場合、ステップＳ１０において、CPU１１は、図示せぬレジスタファイルに処理結果を書き込み、さらに、図示せぬプログラムカウンタを更新して、処理を終了する。【０１２９】
以上の一連の処理のうち、特に、タグアドレスの一部をSRAMサブタグアドレスとして設定し、SRAM５２により管理させるようにし、さらに、最近アクセスされた第１世代のデータを優先的に検索させるようにした。このため、CAMサブタグアドレスにより検索されたラインであって、第１世代のラインのみを、SRAMサブタグアドレスで検索するようにしたので、対応付けて格納されているデータのうち、SRAM５２の検索に伴って同時に読み出されるデータ数を絞り込むことが可能となり、結果として、SRAM５２の消費電力として大きな出力動作を制限させることができ、消費電力を低減させることが可能となる。また、最初の処理で、アクセスされる頻度が高い第１世代のラインを優先的に検索させることにより、キャッシュヒット率の低減を抑制することが可能となる。【０１３０】
さらに、１のCAMサブタグアドレスに対して、複数のSRAMサブタグアドレスであっても、重複してデータを格納させることを認めて、LRU法に則って、アクセスされる可能性の高いデータを格納できるようにしたので、１のCAMサブタグアドレスに対して、１のSRAMサブタグアドレスに絞られることによりキャッシュヒット率が低減してしまうことを抑制することが可能となる。【０１３１】
このように、１のCAMサブタグアドレスに重複して複数のSRAMサブタグアドレスとなるデータの格納を認めて、かつ、最近アクセスされた第１世代のデータを優先的に検索させることにより、キャッシュヒット率を低減させることなく、消費電力を低減させることが可能となる。【０１３２】
［ベンチマークプログラムによるミス率の比較］
次に、図１３を参照して、本発明を適用したキャッシュメモリを用いた場合のミス率と、その平均値について説明する。尚、図１３においては、上段に命令キャッシュによる結果が示されており、下段にデータキャッシュによる結果が示されている。また、図１３における横軸に対応する番号１乃至２１のベンチマークプログラムは、１から順に、bitcount，qsort，susan_e，susan_c，susan_s，lame，tiff2bw，tiff2rgba，dijkstra，patricia，ispell，stringsearch，blow_d，blow_e，rijndael_d，rijndael_e，sha，crc，rawcaudio(adpcm)，rawdaudio(adpcm)，untoast(gsm)であり、番号２２は全体の平均値（average）である。【０１３３】
また、各プログラム毎のミス率は、左から従来型の４ウェイのSRAM、８ウェイのSRAM、３２ウェイのCAM、タグアドレスを24ビットとしたときのCAMサブタグアドレスのビット数sを、s=5,8,9,11としたLPHAC法、および本発明の例（s=4）（黒で表記されている）である。【０１３４】
図１３の上段で示されるように命令キャッシュのミス率は、番号２２で示される平均値から、LPHAC法は従来型のCAMよりも高い値であることがわかる。特に、CAMサブタグアドレスのビット数s=5の場合、ミス率が際立って高い。これは、CAMサブタグアドレスの比較検索で検索できる（ヒットする）が、SRAMタグアドレスの比較検索で検索できない（ミスする）場合が多いためと思われる。また、CAMサブタグアドレスのビット数s=8，9の場合、多くのベンチマークプログラムでのミス率は、従来型のCAMに近い値となるがrijndael dやqsortでは、ミス率は大きい。ミス率は、CAMサブタグアドレスのビット数s=11では全てのベンチマークプログラムにおいて従来型のCAMとほぼ同等となる。一方、本発明のキャッシュメモリにおいては，CAMサブタグアドレスのビット数s=4としても、ミス率には影響を与えないことがわかる。
【０１３５】
すなわち、平均値をみると、LPHAC法ではCAMサブタグアドレスのビット数s =5，8，9，11のとき、それぞれ0.75%，0.43%，0.43%，0.42%となるのに対し、本発明のキャッシュメモリにおいては、CAMサブタグアドレスのビット数s=4において、従来型のCAMと同じ0.42%である。【０１３６】
また、図１３の下段で示されるように、データキャッシュについても命令キャッシュと同様の傾向が見られる。すなわち、LPHAC法では、CAMサブタグアドレスのビット数s=8の場合、rijndael_dやrijndael eはミス率が高く、patriciaやcrcではCAMサブタグアドレスのビット数s=9でもミス率が高い。【０１３７】
一方、本発明のキャッシュメモリの場合、命令キャッシュと同様、従来型のCAMと同様のミス率となっており、CAMサブタグアドレスのビット数s=4でも影響を受けない。番号２２で示される平均値をみると、LPHAC法がs=5，8，9，11のとき、それぞれ1.95%，0.91%，0.80%，0.67%となるのに対し、本発明のキャッシュメモリにおいてはCAMサブタグアドレスのビット数s=4において従来型のCAMと同じ0.66%である。【０１３８】
このように、本発明のキャッシュメモリにおいてはCAMサブタグアドレスとの部分的な比較検索において、ヒットするキャッシュラインを１つに絞らないため、常にLRU方式を採用できるので、ヒット率の低下を抑制することができる。また，LPHAC法のようにCAMアブタグアドレスのビット数sの大きさによって、特定のベンチマークのミス率が大きな影響を受けることはない。【０１３９】
なお、従来型のCAMと本発明のキャッシュメモリは、4，8ウェイの従来型のSRAMと比較し、命令キャッシュでそれぞれ10.7%，8.6%となり、データキャッシュにおいてそれぞれ11.6%，5.0%平均ミス率が小さい。【０１４０】
［消費電力量の比較］
次に、図１４乃至図１６を参照して、消費電力量の評価について説明する。本発明の消費電力量の評価は、上述したベンチマークプログラムを実行したときの平均値に基づいて行うものとし、以下の式（１）で表される消費電力量Ｅで表現されるものとする。
E=Etag+Edata                                      ・・・（１）【０１４１】
ここで、Etagは、以下の式（２）で表される。
Etag=ECAM +ESRAM                                ・・・（２）【０１４２】
ここで、式（２）におけるECAMおよびESRAMは以下の式（３），式（４）で表される。
ECAM=α×w×s×NC                                ・・・（３）
ESRAM = (t−s)×(NS1+NS2)                          ・・・（４）【０１４３】
ここで、αはCAM５１の1ビット検出に要する消費電力量を、wはウェイ数を、sはCAMサブタグアドレスのビット数を、tはタグアドレスのビット数を、NCはCAMへのアクセス数を、NS1は第１世代として管理されているSRAMのデータへのアクセス数を、NS2は第２世代として管理されているSRAMのデータへのアクセス数をそれぞれ示している。【０１４４】
さらに、Edataは、以下の式（５）で表される。
Edata =β×l×(NS1+NS2)                          ・・・（５）【０１４５】
ここで、βはSRAMのデータ1ビットの出力に要する消費電力量を、lは１ライン当たりのデータビット長をそれぞれ表している。【０１４６】
まず、図１４を参照して、タグアドレスの検出に要する消費電力量Etagおよびデータ出力に要する消費電力量Edataと、それぞれのCAMサブタグアドレスのビット長sとの関係について説明する。【０１４７】
図１４においては、左部が命令キャッシュ処理であり、右部がデータキャッシュ処理である。また、いずれも実線および1点鎖線がタグアドレスの検出に要する消費電力量Etagを、点線および２点鎖線がデータ出力に要する消費電力量Edataをそれぞれ表している。タグアドレスの検出に要する消費電力量Etagは、SRAMタグアドレス1ビット検出に要する電力量を単位とする。データ出力に要する消費電力量Edataは、SRAMデータ1ビットの出力に要する電力量を単位とする。尚、1ラインは256ビットとしている。また、CAM５１の1ビット検出に要する消費電力量α=5とし、CAMサブタグアドレスのビット数s=0乃至8、第1世代ウェイ数r =0，4について比較している。比較のために、CAMサブタグアドレスのビット数s=8におけるLPHAC法のタグアドレスの検出に要する消費電力量Etag（×印）およびデータ出力に要する消費電力量Edata（十字マーク）も示している。【０１４８】
LPHAC法では、CAMサブタグアドレスのビット数sを小さくするとミス率が大きくなるため、CAMサブタグアドレスのビット数s≧8でなければならないのに対し、本発明のキャッシュメモリでは、CAMサブタグアドレスのビット数s<8とすることが可能である。【０１４９】
タグアドレスの検出に要する消費電力量Etagは、CAMサブタグアドレスのビット数sを小さくすると線形に減少する。CAMサブタグアドレスのビット数s=8に対して、CAMサブタグアドレスのビット数s=4では、タグアドレス検出に要する消費電力量はほぼ1/2となる。【０１５０】
データ出力に要する消費電力量Edataは、CAMサブタグアドレスのビット数sを小さくするとある値以下では急激に増加する。急激に増加するときのCAMサブタグアドレスのビット数sの値は、第1世代SRAMのウェイ数rによって異なる。ウェイ数r=0のときはCAMサブタグアドレスのビット数sはs≦6で急激に増加するのに対し、ウェイ数r=4とすれば、CAMサブタグアドレスのビット数s=4まであまり変化しない。LPHAC法は、タグアドレスの検出に要する消費電力量Etagおよびデータ出力に要する消費電力量Edata共に本発明のキャッシュメモリと同程度の値をとるが、CAMサブタグアドレスのビット数sを小さくすることが難しい。【０１５１】
本発明のキャッシュメモリは、ウェイ数r=0のときは世代を分けていないため、CAMサブタグアドレスのビット数sを小さくすることが難しいが、図１５の波形図ａ，ｂで示されるように、ウェイ数r=4ならば、世代を分けた効果が表れる。【０１５２】
ここで、図１５の波形図ａ，ｂは、それぞれ命令キャッシュとデータキャッシュについて、CAMサブタグアドレスのビット数sをs=4とし、ウェイ数rをr=0，1，2，4，8，16，32と変えたとき、点線で示されるタグアドレスの検出に要する消費電力量Etagおよび実線で示されるデータ出力に要する消費電力量Edataのウェイ数rとの関係が示されている。【０１５３】
すなわち、命令キャッシュ、およびデータキャッシュのどちらの場合も、ウェイ数r=2乃至4の近傍で消費電力量が最少となる。ウェイ数rの値により消費電力量に最小値が現れるのは、ウェイ数rが小さいと第２世代に設定されたデータとの比較検索回数が増加し、ウェイ数rが大きいと第１世代に設定されたデータで複数比較検索の頻度が上がるためである。【０１５４】
ところで、SRAMにおいて、デコーダや比較器のような論理回路の電力が、ワードライン駆動時に流れるビットラインキャパシタンスの充放電に要する電力と比較して十分小さいという原理が知られている（Itoh, K., Sasaki, K. and Nakagome, Y.: Trends in low-power RAM circuit technologies, Proceedings of the IEEE, Vol.83, No.4, pp.524-543(1995).参照）。そこで、本発明のキャッシュメモリの消費電力量Eについて考えるに当たっては、その原理に則り、SRAMサブタグアドレス1ビットの検出に要する電力量は、SRAMデータ1ビット出力に要する電力量に等しいとする近似を用いる。すなわち、式（５）においてSRAMのデータ1ビットの出力に要する消費電力量β=1とする。【０１５５】
図１５の波形図ｃ，ｄは、それぞれ命令キャッシュとデータキャッシュについて、CAMサブタグアドレスのビット数sを変えたときの命令キャッシュとデータキャッシュの消費電力量Eを示しており、点線はウェイ数rがr=0のときであり、実線はウェイ数rがr=4のときの波形である。また、図１５の波形図ｅ，ｆは、それぞれウェイ数r=4とし、第１世代のウェイ数rを変えたときの命令キャッシュとデータキャッシュの消費電力量Eを示している。これらの波形図から、本発明のキャッシュメモリにおいては、ウェイ数r=4の場合、CAMサブタグアドレスのビット数sがs=2のとき、消費電力量が最小となる。
【０１５６】
次に、図１６を参照して、従来のSRAM、CAM、およびLPHAC法、並びに本発明のキャッシュメモリの消費電力量を比較する。比較対象は、図１６の左から、4，8ウェイの従来型（Traditional）SRAM、32ウェイの従来型CAM、CAMサブタグアドレスのビット数sがs=8のLPHAC法、並びに、ウェイ数rがr=4であって、かつ、CAMサブタグアドレスのビット数sがs=2の本発明のキャッシュメモリ（proposed）である。なお、いずれの場合もラインサイズが32bytesであり、キャッシュ容量が8KBである。また、従来型のCAMとLPHAC法、および本発明のキャッシュメモリについては、図１６の左からCAMの消費電力量α= 5，7，10と値を変えて比較を行った命令キャッシュ（図１６上段）、およびデータキャッシュ（図１６下段）の消費電力量の比較結果が示されている。【０１５７】
命令キャッシュ、およびデータキャッシュの消費電力量は、共に従来型のCAMが、いずれの場合と比較しても消費電力量が一番高いことが示されている。LPHAC法は従来型のCAMに比べると消費電力量を抑えることができている。しかしながら、従来型のSRAMと比べると、CAMの消費電力量α≦7のとき、ウェイ数rがr=8のSRAMの消費電力量より小さくなるが、ウェイ数rがr＝4のSRAMの消費電力量と比べるといずれも大きくなる。これに対して、消費電力量は、本発明のキャッシュメモリではαによらず従来型CAMとLPHAC法のいずれよりも小さくなる。CAMの消費電力量α=10において、従来型のウェイ数rがr=4のSRAMと同程度の消費電力量となっており、CAMの消費電力量αによらず、略同等の消費電力量になっている。
【０１５８】
このように、本発明のキャッシュメモリはキャッシュヒット率の低下を抑制しつつ、消費電力を低減させることが可能となっている。
【０１５９】
尚、本明細書において、プログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理は、もちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理を含むものである。
【符号の説明】
【０１６０】
１１  CPU，  １２  アドレス入力部，  １３  キャッシュメモリ，  １４  メインメモリ，  ２１  インデックスアドレス抽出部，  ２２  タグアドレス抽出部，  ２２ａ  CAMサブタグアドレス抽出部，  ２２ｂ  SRAMサブタグアドレス抽出部，  ４１  デコード部，  ４２  サブバンク，  ５１  CAM，  ５２  SRAM，  ５３  LRU管理部，  ５３ａ  LRU管理リスト，  ５４  読出部，  ５５  置換部，  ７１  比較検索部，  ７２  出力部，  ７３  書戻部，  ７４  世代管理部，  ７４ａ  世代管理リスト，  ７５  書戻管理部，  ７６  書込部，  ７７  書換部，  ７８  格納部，  ８１  世代判定部
【図１】
0005622155.tif 000002
【図２】
0005622155.tif 000003
【図３】
0005622155.tif 000004
【図４】
0005622155.tif 000005
【図５】
0005622155.tif 000006
【図６】
0005622155.tif 000007
【図７】
0005622155.tif 000008
【図８】
0005622155.tif 000009
【図９】
0005622155.tif 000010
【図１０】
0005622155.tif 000011
【図１１】
0005622155.tif 000012
【図１２】
0005622155.tif 000013
【図１３】
0005622155.tif 000014
【図１４】
0005622155.tif 000015
【図１５】
0005622155.tif 000016
【図１６】
0005622155.tif 000017