(57)【特許請求の範囲】
【請求項１】
複数のワードを備える連想記憶メモリ装置において、現在の期間におけるヒットの有無を記憶する第１の記憶素子と、現在の期間に先行する期間におけるヒットの有無を記憶する第２の記憶素子とをワード毎に備え、前記第１及び第２の記憶素子が記憶する値に応じてエージアウトすべきワードを定めるワード選択手段を備えることを特徴とする連想記憶メモリ装置。
【請求項２】
請求項１に記載の連想記憶メモリ装置において、前記第２の記憶素子は、先行する２以上の期間のそれぞれにおけるヒットの有無を記憶する２以上の記憶素子からなることを特徴とする連想記憶メモリ装置。
【請求項３】
請求項１及び２のいずれかに記載の連想記憶メモリ装置において、前記ワード選択手段は、あるワードの前記第１及び第２の記憶素子が全てヒットなしを示す値を記憶しているとき、該当するワードをエージアウトすべきワードと定めることを特徴とする連想記憶メモリ装置。
【請求項４】
請求項２に記載の連想記憶メモリ装置において、前記ワード選択手段は、前記第１及び第２の記憶素子が記憶する値のうち、ヒットなしを示す値の個数が、予め定められた閾値以上のとき、該当するワードをエージアウトすべきワードと定めることを特徴とする連想記憶メモリ装置。
【請求項５】
請求項４に記載の連想記憶メモリ装置において、複数の前記ワード選択手段を備え、前記複数のワード選択手段はそれぞれ異なる前記閾値を有することを特徴とする連想記憶メモリ装置。
【請求項６】
請求項１乃至５のいずれかに記載の連想記憶メモリ装置において、期間の区切りを示す信号を供給する信号供給手段を備えることを特徴とする連想記憶メモリ装置。
【請求項７】
請求項６に記載の連想記憶メモリ装置において、前記信号は予め定められた周期を有することを特徴とする連想記憶メモリ装置。
【請求項８】
請求項６に記載の連想記憶メモリ装置において、
互いに独立した信号を供給する複数の前記信号供給手段と、前記第１及び第２の記憶素子からなる系列をワード毎に複数備え、
前記信号供給手段は、夫々の系列毎に独立した信号を供給する
ことを特徴とする連想記憶メモリ装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はメモリキャッシングに関し、特に、アクセス頻度の低い情報をキャッシュメモリから削除してキャッシュメモリに空き空間を確保する処理、いわゆるエージング処理に関する。
【０００２】
【従来の技術】
使用頻度の高い情報を、安価で広大なメモリ空間を有するが低速なメインメモリから、高価で小さいメモリ空間しか持たないが高速なキャッシュメモリに記憶することにより、アクセス速度を向上する技術、所謂キャッシングが、コンピュータやルータにおけるルーティングエントリで一般的に利用されている。
【０００３】
キャッシュメモリのメモリ空間を有効に活用するためにエージング処理が行なわれる。エージング処理では、使用頻度の低い情報をエントリへの登録から外す。使用頻度の高低は、エントリ毎のヒットの履歴をチェックして、ある程度の時間が経過する間にヒットがない、即ちエージアウトしたエントリを検索する処理により行われる。以下、この履歴チェックをエントリチェックと呼ぶ。
【０００４】
【発明が解決しようとする課題】
従来のエントリチェックはソフトウェアで実行していた。このため、ソフトウェアを実行する処理装置に対して大きな負荷を与えるという問題があった。また、ソフトウェア的に実行されることから高速化が困難であった。
【０００５】
本発明はこのような状況に鑑みてなされたものであり、本発明が解決しようとする課題は、エントリチェックを実行するハードウェアを備えた連想記憶メモリ装置を提供することである。
【０００６】
【課題を解決するための手段】
上記の課題を解決するため、本発明は次のような手段を提供する。本発明は複数のワードを備える連想記憶メモリ装置で次のような特徴を有するものを提供する。即ち、現在の期間におけるヒットの有無を記憶する第１の記憶手段と、現在の期間に先行する期間におけるヒットの有無を記憶する第２の記憶手段とをワード毎に備える。また、第１及び第２の記憶手段が記憶する値に応じてエージアウトすべきワードを定めるワード選択手段を備える。このような連想記憶メモリ装置によれば、現期間と先行する期間におけるヒットの有無を履歴として残すことができる。この履歴をハードウェアでチェックすれば、エージアウトするエントリを高速に検索することができる。
【０００７】
第２の記憶手段は、先行する２以上の期間のそれぞれにおけるヒットの有無を記憶する２以上の記憶素子からなることとしてもよい。この場合、第１及び第２の記憶手段を合わせてワード毎に３個以上の記憶素子を備えることになるので、現在を含む過去３期間分のヒットの履歴を残すことができる。
【０００８】
ワード選択手段は、あるワードの第１及び第２の記憶手段が全てヒットなしを示す値を記憶しているとき、該当するワードをエージアウトすべきワードと定めることとしてもよいし、あるいは、第１及び第２の記憶手段が記憶する値のうち、ヒットなしを示す値の個数が、予め定められた閾値以上のとき、該当するワードをエージアウトすべきワードと定めることとしてもよい。
【０００９】
また、複数の前記ワード選択手段を備え、複数のワード選択手段はそれぞれ異なる閾値を有することとしてもよい。
【００１０】
期間の区切りを示す信号を供給する信号供給手段を備えることとしてもよい。この場合、信号は予め定められた周期を有することとしてもよいし、任意のタイミングで供給されてもよい。
【００１１】
互いに独立した信号を供給する複数の前記信号供給手段を備えることとしてもよい。この場合、第１及び第２の記憶手段からなる系列をワード毎に複数備え、信号供給手段は、夫々の系列毎に独立した信号を供給することとしてもよい。
【００１２】
【発明の実施の形態】
１．第１の実施の形態
本発明の第１の実施の形態である連想記憶メモリ装置１０について以下に説明する。図１に示すように、連想記憶メモリ装置１０は、ＣＡＭ(content addressable memory)制御回路１１及びＣＡＭアレー１２からなる。ＣＡＭ制御回路１１とＣＡＭアレー１２は制御信号１３、１４及びタイミング信号１５をやりとりしている。ＣＡＭ制御回路１１は、ＣＡＭアレー１２を制御するための制御信号１３を生成してＣＡＭアレー１２に送信する一方、ＣＡＭアレー１２から制御信号１４を受信する。更に、ＣＡＭ制御回路１１は、エージングのタイミングを制御するタイミング信号１５を生成してＣＡＭアレー１２に送信する。タイミング信号１５は予め決められたエージングの周期毎にＨｉｇｈパルスを発生するタイミングパルスである。
【００１３】
図２を参照してＣＡＭアレー１２について説明する。ＣＡＭアレー１２は、通常の記憶素子１６に加えて、後述するエージング回路付き記憶素子群１７を各ワード毎に備える。ＣＡＭアレー１２では、記憶素子１６だけではなく、これに加えてエージング回路付き記憶素子群１７をも検索対象とすることができる。検索対象とするか否かは検索時に与えるマスク情報により制御される。
【００１４】
エージング回路付き記憶素子群１７について図３を参照して説明する。記憶素子２１及び２２にはセレクタ３１及び３２が接続されている。
【００１５】
記憶素子２１にはセレクタ回路３１の出力情報が保持される。セレクタ回路３１は記憶素子２１及び２２の出力のうち、いずれか一方を選択する回路であり、その切替はタイミング信号１５により制御される。セレクタ回路３１は、タイミング信号１５がＨｉｇｈパルスのときのみ記憶素子２２の出力を選択し、それ以外のときは記憶素子２１の出力を選択する。
【００１６】
記憶素子２２にはセレクタ回路３２の出力情報が保持される。セレクタ回路３２は、記憶素子３２の出力、及び、ヒット信号３３のうち、いずれか一方を選択する回路であり、その切替はヒット信号３３により制御される。ヒット信号３３はＣＡＭアレー１２を検索した時に該当ワードがヒットするとＨｉｇｈパルスが発生する信号である。従って、セレクタ回路３２は該当ワードが検索時にヒットしたときにヒット信号３３を選択することになる。更に、記憶素子２２はリセット機能を有し、タイミング信号１５がＨｉｇｈのとき、Ｌｏｗにリセットされる。
【００１７】
連想記憶メモリ装置１０では、該当するワードに対する検索ヒットの有無が、タイミング信号１５が定める期間毎に記憶される。現在の期間中での検索ヒットの有無は記憶素子２２に記憶される。直前の期間中での検索ヒットの有無は記憶素子２１に記憶される。
【００１８】
連想記憶メモリ装置１０の動作について図４を参照して具体的に説明する。ここでは、説明を簡単にするため、ＣＡＭアレー１２はワード０からワード３までの計４ワードで構成されるものとする。上述したように、これらの４ワードのそれぞれにエージング回路付き記憶素子群１７が設けられ、図４では、それぞれ、ワード０記憶素子２１、２２、ワード１記憶素子２１、２２、ワード２記憶素子２１、２２、ワード３記憶素子２１、２２として記されている。タイミング信号１５により区切られる期間を順にエージング周期１〜４とする。
【００１９】
エージング周期１の直前では、記憶素子２１及び２２は全ワードでＬｏｗである。
【００２０】
エージング周期１において、検索の結果、ワード０、１、２の順番にヒットしたものとする。このとき、ワード０記憶素子２２、ワード１記憶素子２２、ワード２記憶素子２２の順番にＬｏｗからＨｉｇｈに変化する（ｔ１、ｔ２、ｔ３）。エージング周期１の末期にエージアウトしたエントリをサーチする（ｔ４）ためには、記憶素子２１及び２２の両方がＬｏｗであるエントリをサーチすればよい。これらの記憶素子が共にＬｏｗであることは、直前のエージング周期と現在のエージング周期の間に一度も該当するワードに対して検索ヒットがなかったことを意味する。ここで該当するワードはワード３である。そこでワード３はエージアウトしたものとして扱う。
【００２１】
エージング周期２の開始時点でタイミング信号１５がＨｉｇｈとなるので、ワード０、１及び２の記憶素子２２のＨｉｇｈ出力は、それぞれのワードの記憶素子２１に入力されると共に、対応する記憶素子２２はＬｏｗにリセットされる。ワード３については記憶素子２２の値が元々Ｌｏｗであったため、記憶素子２１及び２２のどちらの値も変化しない。エージング周期２では、検索の結果、ワード０及び２の順にヒットしたものとする。このとき、ワード０記憶素子２２及びワード２記憶素子２２が順にＬｏｗからＨｉｇｈに変化する（ｔ５、ｔ６）。エージング周期２の末期にエージアウトしたエントリをサーチする（ｔ７）と、再度ワード３が該当するワードとなる。
【００２２】
エージング周期３の開始時点でタイミング信号１５がＨｉｇｈになる。この時点で、ワード０記憶素子２１はＨｉｇｈ、ワード０記憶素子２２はＬｏｗ、ワード１記憶素子２１はＬｏｗ、ワード１記憶素子２２はＬｏｗ、ワード２記憶素子２１はＨｉｇｈ、ワード２記憶素子２２はＬｏｗ、ワード３記憶素子２１はＬｏｗ、ワード３記憶素子２２はＬｏｗである。エージング周期３では、ワード２及び３の順にヒットしたものとする。このとき、ワード２記憶素子２２及びワード３記憶素子２２が順にＬｏｗからＨｉｇｈに変化する（ｔ８、ｔ９）。エージング周期３の末期にエージアウトしたエントリをサーチする（ｔ１０）と、今回はワード１が該当する。
【００２３】
このようにして、連想記憶メモリ装置１０では、現在のエージング周期と、その前のエージング周期の両方を通じて一度も検索でヒットしなかったエントリを、ＣＡＭアレー１２の検索を行なうことによりサーチすることができる。このエントリをエージアウトしたエントリとして定義すれば、エージングをハードウェア的に高速実行することができる。
【００２４】
２．第２の実施の形態
本発明の第２の実施の形態について説明する。第１の実施の形態では、エージング周期の末期毎にエージアウトしたエントリをサーチした。これに対して、第２の実施の形態では、任意のタイミングでエージアウトしたエントリをサーチする点が異なる。このようにすることにより、エージアウトをしたエントリを検索する処理を必要なとき、例えば新たにＣＡＭアレー１２にエントリを登録しようとしたが空き領域がないときにだけ実行することができる。こうすれば、ＣＡＭアレー１２のエントリの空き領域を少なく抑えることが可能となり、ＣＡＭアレー１２の利用効率を向上させることができる。
【００２５】
例えば、図５を参照すると、エージング周期１において、ワード０、１、２の順にヒットしている（ｕ１、ｕ３、ｕ４）が、ここでは、エージング周期１の末期ではなく、ｕ１とｕ３の間でエージアウトしたエントリをサーチしている。ｕ２の時点で記憶素子２１及び２２の両方がＬｏｗであるワードはワード１、２及び３である。エージング周期２ではエージアウトしたエントリをサーチしていないが、他方、エージング周期３では２回サーチを行なっている（ｕ８、ｕ１０）。ｕ８の時点ではワード１及び３がエージアウトしたエントリに該当する。しかしｕ９においてワード３がヒットしているので、ｕ１０の時点においてサーチすると、ワード１のみが該当する。
【００２６】
３．第３の実施の形態
第１の実施の形態では、現在及び直前の２つのエージング周期におけるヒットの有無を記憶した。これに対して、第３の実施の形態では、現在、直前、及び２つ前のエージング周期におけるヒットの有無を記憶する。このため、第３の実施の形態では、ＣＡＭアレー１２の各ワードのエージング回路付き記憶素子群１７は、それぞれ３つの記憶素子からなる。
【００２７】
第３の実施の形態では、ＣＡＭアレー１２の各ワードは、図６のようなエージング回路付き記憶素子群６０を備える。第１の実施の形態の要素に対応するものについては同一の参照符号を付してある。これらの実施の形態の相違点を挙げると、第３の実施の形態では、図３の回路に加えて記憶素子６１及びセレクタ回路６２を備える。記憶素子２１の出力はセレクタ回路６２に入力されている。また、セレクタ回路６２の出力が記憶素子６１に入力されている。セレクタ回路６２は記憶素子２１及び６１の出力のいずれかを選択する回路であり、その切替はタイミング信号１５によって制御される。セレクタ回路６２は、タイミング信号１５がＨｉｇｈのタイミングで記憶素子２１の出力を選択し、それ以外のときは記憶素子６１の出力を選択する。つまり、タイミング信号１５がＨｉｇｈのタイミングで、記憶素子２２の値は記憶素子２１に移動し、記憶素子２１の値は記憶素子６１に移動すると考えることができる。
【００２８】
本実施の形態の動作について説明する。第１及び第２の実施の形態では、記憶素子２１及び２２の両方がＬｏｗであるワードをサーチした。これは、Ｌｏｗである記憶素子が２以上のワードをサーチしたと考えることもできる。これに対して、第３の実施の形態では、記憶素子２１、２２、６１の全てがＬｏｗであることを検索キーとしてワードをサーチする場合と、記憶素子２１及び２２がＬｏｗであることを検索キーとしてワードをサーチする（即ち、記憶素子６１の値は問わない）場合との２種類のサーチを行なうことができる。このように、エージング回路付き記憶素子群として記憶素子をワード毎に３個ずつ備えることとすれば、ヒットの履歴を３回分残すことができるので、エージアウトしたエントリを検索する際の検索キーを複数利用することができる。これらの検索キーを使い分けることにより、例えば、ＣＡＭアレー１２に新たに必要となる空き容量の大きさに応じて検索キーを使い分けることができるようになり、ＣＡＭアレー１２の利用効率を改善することができる。エージング回路付き記憶素子群の記憶素子を４個以上に増やせば、更に検索キーの種類を増やすことができるのは、当業者には自明であろう。
【００２９】
図７を参照して具体的に説明する。ｖ４におけるエージアウトしたエントリの検索は、記憶素子２１、２２及び６１の全てがＬｏｗであることを検索キーとしている。ここで検索キーの条件を満足するのはワード３である。また、ｖ９における検索は、記憶素子２１及び２２の両方がＬｏｗであることを検索キーとしている。ここではワード１がヒットしている。仮にｖ９のタイミングで全記憶素子がＬｏｗであることを検索キーとしていたら、条件を満足するワードは存在しなかった点に注意されたい。
【００３０】
４．第４の実施の形態
第４の実施の形態におけるＣＡＭアレー１２では、第１の実施の形態のエージング回路付き記憶素子群１７が二組ずつワード毎に設けられる。図８を参照して説明すると、第４の実施の形態では、第１の実施の形態の記憶素子２１及び２２、セレクタ回路３１及び３２を備え、更に、記憶素子８１及び８２、セレクタ回路８３及び８４を備える。記憶素子２１及び２２はそれぞれ記憶素子８１及び８２と等価である。同様に、セレクタ回路３１及び３２はそれぞれセレクタ回路８３及び８４と等価である。
【００３１】
ここで、記憶素子２１及び２２を第１系列、記憶素子８１及び８２を第２系列と呼ぶ。該当するワードへのヒットの有無は、同じヒット信号３３が第１及び第２系列の両方に供給される。しかし、エージング周期を決定するタイミング信号については、第１系列と第２系列では異なるタイミング信号１５及び８５が供給される。タイミング信号１５及び８５は互いに独立した周期を有する信号である。
【００３２】
このように、互いに独立した周期を有する信号で動作する複数の系列を用いることにより、複数のエージング周期に基づいてエージアウトしたエントリを検索することができる。第３の実施の形態では、タイミング信号１５の整数倍の周期を有する複数のエージング周期を設定可能であったのに対して、第４の実施の形態では、タイミング信号１５の周期に無関係に複数のエージング周期を設定可能である。
【００３３】
尚、第４の実施の形態に対して、第３の実施の形態を適用可能であることは、当業者には明らかであろう。即ち、上述の例では第１及び第２系列は、記憶素子及びセレクタ回路を、それぞれ２組ずつ備えているが、これを３組、４組と増やせば、第１及び第２系列のそれぞれに対して、タイミング信号１５及び８５の整数倍長さの周期を有する複数のエージング周期を設定可能である。
【００３４】
５．第５の実施の形態
第５の実施の形態では、第４の実施の形態における第１及び第２系列に加えて更に第３系列を備える。図９を参照すると、ＣＡＭアレー１２のワードはそれぞれ、第４の実施の形態の記憶素子及びセレクタ回路に加えて、更に、第３系列として、記憶素子９１及び９２、セレクタ回路９３及び９４を備える。第３系列はタイミング信号９５が供給される。タイミング信号１５、８５及び９５は互いに独立した周期を有する。
【００３５】
このように、３つ以上の系列を備えることとすれば、互いに独立した３つ以上のエージング周期に基づいてエージアウトしたエントリを検索することができる。
【００３６】
６．以上、本発明を実施の形態に基づいて説明したが、本発明はこれに限定されるものではなく、当業者の通常の知識の範囲内でその変更や改良が可能であることは勿論である。
【００３７】
【発明の効果】
本発明によれば、外部からタイミング信号を供給するだけで、ＣＡＭの中で現在時刻までのある期間内にヒットしなかったエントリを見つけるために必要な情報を生成することができる。エージアウトしたエントリを見つける処理（エントリチェック）を行なうためには、エージング回路を実装したビットを検索キーとして、周期的に検索を実行すればよい。この処理はハードウェアにより自律的に実行することが可能であり、ソフトウェアによる処理は不要である。
【００３８】
このため、従来のようにソフトウェアでエージアウトしたエントリを探すのと比較すると、検索時間を大幅に短縮することができる。また、エントリチェックを制御するためにソフトウェアが介入しないので、ハードウェアの処理能力に対する負荷を軽減することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態の連想記憶メモリ装置１０である。
【図２】ＣＡＭアレー１２を構成する記憶素子を説明する図である。
【図３】本発明の第１の実施の形態に係るエージング回路付き記憶素子群１７を説明するためのブロック図である。
【図４】本発明の第１の実施の形態の動作を説明するためのタイミングチャートである。
【図５】本発明の第２の実施の形態の動作を説明するためのタイミングチャートである。
【図６】本発明の第３の実施の形態に係るエージング回路付き記憶素子群６０を説明するためのブロック図である。
【図７】本発明の第３の実施の形態の動作を説明するためのタイミングチャートである。
【図８】本発明の第４の実施の形態に係るエージング回路付き記憶素子群８０を説明するためのブロック図である。
【図９】本発明の第５の実施の形態に係るエージング回路付き記憶素子群９０を説明するためのブロック図である。
【符号の説明】
１０  連想記憶メモリ装置
１１  ＣＡＭ制御回路
１２  ＣＡＭアレー
１３、１４  制御信号
１５、８５、９５  タイミング信号
１７、６０、８０、９０  エージング回路付き記憶素子群
２１、２２、６１、８１、８２、９１、９２  記憶素子
３１、３２、６２、８３、８４、９３、９４  セレクタ回路
３３  ヒット信号
【図１】
0003702950.tif 000002
【図２】
0003702950.tif 000003
【図３】
0003702950.tif 000004
【図４】
0003702950.tif 000005
【図５】
0003702950.tif 000006
【図６】
0003702950.tif 000007
【図７】
0003702950.tif 000008
【図８】
0003702950.tif 000009
【図９】
0003702950.tif 000010