(57)【要約】【課題】構成の異なる複数の連想メモリを使用するシステムにおいて、コスト的に無駄がなく、制御しやすい連想メモリを提供する。【解決手段】本発明の連想メモリは、各々異なる構成に設定可能な複数の物理バンクに分割された連想メモリアレイと、論理バンクの構成に応じて、対応付けられている各々の物理バンクの構成を設定し、制御する論理・物理信号変換回路と、論理バンクに対応する各々の物理バンクに対して検索が行われると、あらかじめ設定されている優先順位に従って、各々の物理バンクから出力される検索結果を順次出力するプライオリティ回路と、複数の連想メモリをカスケード接続して使用する場合に、プライオリティ回路から出力される連想メモリの検索結果と、上位の連想メモリから供給される検索結果との論理をとって、その演算結果を下位の連想メモリに順次伝達するカスケード制御回路とを備えている。【選択図】図１
2004265528.tif 000002
【特許請求の範囲】
【請求項１】
複数の物理バンクに分割され、各々の前記物理バンクを異なる構成に設定可能に構成された連想メモリアレイと、
論理バンクの構成に応じて、当該論理バンクに対応付けられている前記連想メモリアレイの各々の物理バンクの構成を設定し、各々の前記物理バンクを制御する論理・物理信号変換回路と、
前記論理バンクに対応する各々の前記物理バンクに対して検索が行われると、あらかじめ設定されている優先順位に従って、各々の前記物理バンクから出力される検索結果を順次出力するプライオリティ回路と、
複数の連想メモリをカスケード接続して使用する場合に、前記プライオリティ回路から出力される当該連想メモリの検索結果と、上位の連想メモリから供給される検索結果との論理をとって、その演算結果を下位の連想メモリに順次伝達するカスケード制御回路とを備えていることを特徴とする連想メモリ。
【請求項２】
前記論理・物理信号変換回路は、複数の前記論理バンクを設定可能に構成され、これら複数の論理バンクの中から選択された論理バンクの構成に応じて、当該選択された論理バンクに対応付けられている前記連想メモリアレイの各々の物理バンクの構成を動的に設定する請求項１に記載の連想メモリ。
【請求項３】
前記論理・物理信号変換回路は、２つ以上の前記論理バンクに、同じ１つの前記物理バンクを対応付けることが可能に構成されている請求項２に記載の連想メモリ。
【請求項４】
前記カスケード制御回路は、複数の連想メモリをカスケード接続して使用する場合に、前記論理バンクに対応する物理バンクが当該連想メモリの中に存在しない場合には、当該連想メモリの検索結果として、一致が存在しない状態を表す検索結果を使用する請求項１〜３のいずれかに記載の連想メモリ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、異なる構成の複数の連想メモリの機能を１つのデバイスで、もしくは複数のデバイスを組み合わせて実現する連想メモリに関するものである。
【０００２】
【従来の技術】
スイッチやルータ等のネットワーク装置においては、高速性、高機能を実現するために、連想メモリ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ：以下、ＣＡＭという）が使用されることが多い。
【０００３】
ネットワーク装置では、ＯＳＩ（Ｏｐｅｎ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ  ）の各層（レイヤ）に応じて様々な形式のデータを扱う必要がある。例えば、レイヤ２のアドレス情報は、ビット長は長いがワード数は少ない２値データとして扱い、レイヤ３のアドレス情報は、ビット長は短いがワード数は多い３値データとして扱う。
また、複数の層の情報を組み合わせて利用することもあり、その場合は必然的にビット長が長くなる。
【０００４】
このようなネットワーク装置を実現するためには、これら複数のデータの種類に応じて、例えば２値データを扱うバイナリＣＡＭ／３値データを扱うターナリＣＡＭという種類の違いや、ビット長の違い等のそれぞれ構成の異なる複数のＣＡＭを使用する必要がある。なお、２値データは、‘０’または‘１’のデータのみを持つものであり、３値データは、‘０’、‘１’もしくは‘Ｘ（ドントケア）’のデータを持つものである。
【０００５】
従来は、上記のようなネットワーク装置の実現方法として、例えば下記（１）〜（３）が提案されている。
【０００６】
（１）それぞれのレイヤのアドレス情報に対応して、種類やビット長等の構成の異なる複数のＣＡＭデバイスを使用する。
【０００７】
（２）特許文献１に記載されているように、連想メモリアレイが複数の物理バンクに分割されたＣＡＭデバイスを用い、それぞれのレイヤのアドレス情報に対応して、それぞれの物理バンクの構成を静的に設定して使用する。
【０００８】
（３）１つのＣＡＭデバイス、または１つの物理バンクにビット長の異なるデータを混在させる。
【０００９】
上記（３）について一例を挙げて説明すると、３１ビットのデータと６２ビットのデータを混在させる場合、図１０に示すように、１ワードが６４ビットのターナリＣＡＭを用いる。
【００１０】
３１ビットのデータは、６４ビットのうちのＭＳＢ（上位ビット）側の３２ビット、ＬＳＢ（下位ビット）側の３２ビットの両方にそれぞれ格納する。この時、ＭＳＢ側およびＬＳＢ側の３２ビットのうちの最上位の１ビットをそれぞれフラグ用のビット、残りの３１ビットをデータ用のビットとし、フラグとして、３１ビットデータであることを示す‘１’を格納する。
【００１１】
また、６２ビットのデータは、３１ビットずつ２つのデータに分けて格納し、ＭＳＢ側およびＬＳＢ側のフラグとして共に、６２ビットデータであることを示す‘０’を格納する。
【００１２】
３１ビットデータの検索時には、フラグに対応するデータが‘１’である３２ビットの検索キーデータを用い、ＭＳＢ側およびＬＳＢ側の２回に分けて３２ビットのデータの検索を行う。
【００１３】
例えば、ＭＳＢ側の３２ビットの検索キーデータを用いてＭＳＢ側の３２ビットのデータの一致検索を行う。この時、ＬＳＢ側の３２ビットの検索キーデータは全て‘Ｘ’とする。続いて、ＬＳＢ側の３２ビットの検索キーデータを用いてＬＳＢ側の３２ビットのデータの一致検索を行う。この時は、ＭＳＢ側の３２ビットの検索キーデータを全て‘Ｘ’とする。そして、ＭＳＢ側およびＬＳＢ側の検索結果のうちプライオリティの高い方を最終検索結果とする。
【００１４】
一方、６２ビットデータの検索時には、２つのフラグに対応するデータが共に‘０’である６４ビットの検索キーデータを用いて６４ビットのデータの検索を行う。
【００１５】
近年ではＣＡＭが大容量化されており、上記（１）、（２）の方法では、全容量のうち無駄になる部分が大きく、コストが高くなるという問題があった。また、（２）の方法では、複数個のＣＡＭデバイスをカスケード接続して使用する場合が考慮されていないという問題もあった。また、（３）の方法では、一致検索を２回に分けて行い、検索結果から優先順位の高いものを選択的に出力する必要があるため外部回路が複雑になり、処理時間も増大するという問題があった。
【００１６】
【特許文献１】
特開２００１−２３６７９０号公報
【００１７】
【発明が解決しようとする課題】
本発明の目的は、前記従来技術に基づく問題点を解消し、構成の異なる複数の連想メモリを使用するシステムにおいて、コスト的に無駄がなく、制御しやすい連想メモリを提供することにある。
【００１８】
【課題を解決するための手段】
上記目的を達成するために、本発明は、複数の物理バンクに分割され、各々の前記物理バンクを異なる構成に設定可能に構成された連想メモリアレイと、
論理バンクの構成に応じて、当該論理バンクに対応付けられている前記連想メモリアレイの各々の物理バンクの構成を設定し、各々の前記物理バンクを制御する論理・物理信号変換回路と、
前記論理バンクに対応する各々の前記物理バンクに対して検索が行われると、あらかじめ設定されている優先順位に従って、各々の前記物理バンクから出力される検索結果を順次出力するプライオリティ回路と、
複数の連想メモリをカスケード接続して使用する場合に、前記プライオリティ回路から出力される当該連想メモリの検索結果と、上位の連想メモリから供給される検索結果との論理をとって、その演算結果を下位の連想メモリに順次伝達するカスケード制御回路とを備えていることを特徴とする連想メモリを提供するものである。
【００１９】
ここで、前記論理・物理信号変換回路は、複数の前記論理バンクを設定可能に構成され、これら複数の論理バンクの中から選択された論理バンクの構成に応じて、当該選択された論理バンクに対応付けられている前記連想メモリアレイの各々の物理バンクの構成を動的に設定するのが好ましい。
【００２０】
また、前記論理・物理信号変換回路は、２つ以上の前記論理バンクに、同じ１つの前記物理バンクを対応付けることが可能に構成されているのが好ましい。
【００２１】
また、前記カスケード制御回路は、複数の連想メモリをカスケード接続して使用する場合に、前記論理バンクに対応する物理バンクが当該連想メモリの中に存在しない場合には、当該連想メモリの検索結果として、一致が存在しない状態を表す検索結果を使用するのが好ましい。
【００２２】
【発明の実施の形態】
以下に、添付の図面に示す好適実施形態に基づいて、本発明の連想メモリを詳細に説明する。
【００２３】
図１は、本発明の連想メモリの一実施形態の構成概略図である。同図に示す連想メモリ（以下、ＣＡＭという）１０は、バイナリＣＡＭ／ターナリＣＡＭという種類の違いや、ビット長、ワード数等の違いを持つ、異なる構成の複数のＣＡＭの機能を１つのデバイスで、もしくは複数のデバイスを組み合わせて実現可能なものである。ＣＡＭ１０は、連想メモリアレイ１２と、論理・物理信号変換回路１４と、デコーダ１６と、プライオリティ回路１８と、カスケード制御回路２０とを備えている。
【００２４】
図示例のＣＡＭ１０において、連想メモリアレイ１２は、ブロック分割された８個の物理バンク０〜７を備えている。各々の物理バンクの構成は、次に述べる論理・物理信号変換回路１４から供給される信号ＣＯＮＦＩＧ＜２：０＞に応じて、バイナリＣＡＭあるいはターナリＣＡＭとして使用するかを設定することができ、また、あらかじめ用意されている複数種類のビット長の中から任意のビット長に設定することができる。
【００２５】
論理・物理信号変換回路１４は、必要とするＣＡＭの構成に応じて論理バンクの構成が設定され、論理バンクと連想メモリアレイ１２の物理バンクとの間の対応関係が設定されると、設定された論理バンクの構成に応じて、連想メモリアレイ１２の各々の物理バンクの構成を動的に設定し、論理バンクに対応する物理バンクに対して正しくアクセスが行われるように、連想メモリアレイ１２の各々の物理バンクを制御する。
【００２６】
論理・物理信号変換回路１４には、信号ＩＮ＜６３：０＞、信号ＬＢＡＮＫ＜２：０＞、信号ＳＥＡＲＣＨ、信号ＧＥＮＦＵＬ、信号ＰＵＲＧＥ＿ＨＩＴ、信号ＴＡＢＬＥ＿ＷＲが入力されている。また、論理・物理信号変換回路１４からは、連想メモリアレイ１２のそれぞれの物理バンク０〜７に対して個別に供給される信号ＳＲＣＨ、信号ＧＮＦＬ、信号ＰＲＧ＿ＨＩＴおよび信号ＣＯＮＦＩＧ＜２：０＞と、信号ＰＡＳＳが出力されている。
【００２７】
ここで、物理バンクとは、連想メモリアレイ１２を物理的に複数のブロックに分割した時の各々のブロックのことである。これに対して、論理バンクとは、論理的に物理バンクのメモリ空間を割り当てたもので、必要なワード数に応じて複数の物理バンクを連結し、これを１つのメモリ空間として使用することもできる。この論理バンクの概念により、外部からは個々の物理バンクのメモリ空間を意識することなく、論理バンクのメモリ空間を使用することができる。
【００２８】
ＣＡＭ１０では、同じ１つの物理バンクを複数の論理バンクの一部として対応付けることができる。各々の論理バンクの構成が異なる場合、物理バンクの構成は、各々の論理バンクが選択される毎に、論理・物理信号変換回路１４から供給される信号ＣＯＮＦＩＧ＜２：０＞に応じて動的に変更される。なお、各々の物理バンクは、連想メモリアレイ１２に記憶されているデータの内容を保持したままの状態で構成の設定変更を行うことが可能である。
【００２９】
例えば、図３に示すように、論理バンク１の構成が６４ビットバイナリ、論理バンク２の構成が１２８ビットバイナリであり、これら論理バンク１，２が共に物理バンク１と対応付けられている場合、論理バンク１が選択されると、そのＣＯＮＦＩＧ＜２：０＞に応じて、物理バンク１の構成は６４ビットバイナリに動的に設定され、論理バンク２が選択されると、そのＣＯＮＦＩＧ＜２：０＞に応じて、物理バンク１の構成は１２８ビットバイナリに動的に設定される。
【００３０】
続いて、デコーダ１６は、連想メモリアレイ１２へのデータの書き込み、連想メモリアレイ１２からのデータの読み出しを制御する。
【００３１】
デコーダ１６には、信号ＲＥＡＤ，ＷＲＩＴＥ、信号ＡＤＤＲＥＳＳ＜１４：０＞が入力されている。また、デコーダ１６からは、連想メモリアレイ１２の各バンクに対して信号ＲＤ，ＷＲが、全ての物理バンク０〜７に対して共通に供給される信号ＡＤＤＲＥＳＳ＜１１：０＞が出力されている。
【００３２】
また、連想メモリアレイ１２の各々の物理バンク０〜７には、論理・物理信号変換回路１４から出力される信号ＳＲＣＨ、信号ＧＮＦＬ、信号ＰＲＧ＿ＨＩＴ、信号ＣＯＮＦＩＧ＜２：０＞がそれぞれ個別に入力され、デコーダ１６から出力される信号ＲＤ，ＷＲがそれぞれ個別に、信号ＡＤＤＲＥＳＳ＜１１：０＞、および信号ＤＡＴＩＮ＜６３：０＞が共通に入力されている。また、連想メモリアレイ１２の各々の物理バンク０〜７からは信号ＤＡＴＯＵＴ＜６３：０＞が出力され、ワイヤード接続されている。
【００３３】
続いて、プライオリティ回路１８は、あらかじめ設定されている優先順位に従って、連想メモリアレイ１２の各々の物理バンクから供給される信号ＨＨＡ／ＨＥＡ＜１１：０＞、信号ＨＩＴ、信号ＦＵＬＬに対応する信号ＨＨＡ／ＨＥＡ＜１４：０＞、信号ＨＩＴ、信号ＦＵＬＬを順次出力する。本実施形態では、物理バンク０の優先順位が最も高く、以下順次優先順位が低くなり、物理バンク７の優先順位が最も低いものとする。
【００３４】
プライオリティ回路１８には、連想メモリアレイ１２の各々の物理バンクから出力される信号ＨＨＡ／ＨＥＡ＜１１：０＞、信号ＨＩＴ、信号ＦＵＬＬが全て入力されている。また、プライオリティ回路１８からは、信号ＨＨＡ／ＨＥＡ＜１４：０＞、信号ＨＩＴ、信号ＦＵＬＬが出力されている。
【００３５】
最後に、カスケード制御回路２０は、図８に示すように、複数のＣＡＭデバイスをカスケード接続して使用する場合に、上位側のＣＡＭデバイスから下位側のＣＡＭデバイスに信号ＨＩＴ、信号ＦＵＬＬを順次伝達する。
【００３６】
カスケード制御回路２０には、プライオリティ回路１８から供給される信号ＨＩＴ、信号ＦＵＬＬ、論理・物理信号変換回路１４から供給される信号ＰＡＳＳの他、上位側のＣＡＭデバイスから供給される信号ＨＩ、信号ＦＬＩが入力されている。また、カスケード制御回路２０からは、下位側のＣＡＭデバイスに対して供給される信号ＨＯ、信号ＦＬＯが出力されている。また、カスケード制御回路２０からは信号ＨＩＴ、信号ＦＵＬＬが出力されている。
【００３７】
次に、連想メモリアレイ１２の物理バンクについて説明する。
【００３８】
図２は、物理バンクに接続される信号を表す一実施形態の概念図である。同図は、図１に示すＣＡＭ１０の連想メモリアレイ１２の１つの物理バンクを表すもので、物理バンクには、図１と同じ各信号ＣＯＮＦＩＧ＜２：０＞、ＳＲＣＨ、ＧＮＦＬ、ＰＲＧ＿ＨＩＴ、ＷＲ、ＲＤ、ＤＡＴＩＮ＜６３：０＞、ＡＤＤＲＥＳＳ＜１１：０＞、ＨＨＡ／ＨＥＡ＜１１：０＞、ＨＩＴ、ＦＵＬＬ、ＤＡＴＯＵＴ＜６３：０＞が接続されている。
【００３９】
まず、信号ＣＯＮＦＩＧ＜２：０＞は、連想メモリアレイ１２の物理バンクの構成を設定するための信号である。本実施形態では、図４の表に示すように、物理バンクをバイナリＣＡＭとして使用するのか、あるいは、ターナリＣＡＭとして使用するのかのＣＡＭの種類の違い、また、ビット長を６４，１２８，２５６ビットのうちのどのビット長とするのかの違いに応じて、３ビットの信号により、各々の物理バンクの機能構成を６通りの中から指定することができる。
【００４０】
次に、ＡＤＤＲＥＳＳ＜１１：０＞は、この物理バンクのメモリアドレスを指定する入力信号である。
【００４１】
ＤＡＴＩＮ＜６３：０＞は、この物理バンクに対するエントリデータや検索キーデータの入力信号である。
【００４２】
ＤＡＴＯＵＴ＜６３：０＞は、物理バンクに格納されているエントリデータを読み出した出力信号である。
【００４３】
ＷＲは、ＤＡＴＩＮ＜６３：０＞として入力される６４ビットの信号を、ＡＤＤＲＥＳＳ＜１１：０＞によって指定されるメモリアドレスに書き込むための入力信号である。
【００４４】
ＲＤは、ＡＤＤＲＥＳＳ＜１１：０＞によって指定される物理バンクのメモリアドレスに格納されているエントリデータをＤＡＴＯＵＴ＜６３：０＞として読み出すための入力信号である。
【００４５】
ＳＲＣＨは、物理バンクに対して検索開始を指示する入力信号である。
【００４６】
ＨＩＴは、一致検索の結果、物理バンク内にヒットエントリ、すなわち検索キーデータと一致するエントリデータが存在するか否かを表す出力信号である。ＨＩＴは、本実施形態の場合、エントリデータの中にヒットエントリが１つでも存在する場合にはハイレベルとなり、ヒットエントリが１つも存在しない場合にローレベルとなる。
【００４７】
ＨＨＡ＜１１：０＞は、最優先順位のヒットアドレス（Ｈｉｇｈｅｓｔ  Ｈｉｔ  Ａｄｄｒｅｓｓ  ）の出力信号である。ＨＨＡ＜１１：０＞としては、一致検索の結果、前述のＨＩＴがハイレベルとなり、ヒットエントリが存在する場合に、最も優先順位の高いヒットエントリが格納されているメモリアドレス、すなわち最優先順位のヒットアドレスが出力される。本実施形態の場合、ヒットアドレスの内の最も小さいアドレスが出力される。
【００４８】
ＰＲＧ＿ＨＩＴは、一致検索の結果、ＨＩＴがハイレベルとなり、物理バンク内にヒットエントリが存在する場合に、このヒットエントリを消去するための入力信号である。このＰＲＧ＿ＨＩＴにより、最優先順位のヒットエントリを消去すると、次回の一致検索ではその次の優先順位のヒットエントリが最優先順位のヒットエントリとなる。これにより、複数のヒットエントリが存在する場合に、そのヒットアドレスを順次出力することができる。
【００４９】
ＧＮＦＬは、物理バンク内の最優先順位のエンプティアドレス（ＨＥＡ：Ｈｉｇｈｅｓｔ  Ｅｍｐｔｙ  Ａｄｄｒｅｓｓ  ）を検索するための入力信号である。このＧＮＦＬを入力することにより、ＨＥＡ＜１１：０＞が出力される。
【００５０】
ＦＵＬＬは、物理バンクに対して前述のＧＮＦＬを入力した結果、この物理バンク内にエンプティエントリ、すなわち一致検索の対象となる有効なエントリデータが格納されていないメモリアドレスが存在するかどうかを表すための出力信号である。ＦＵＬＬは、本実施形態の場合、エンプティエントリが全く存在しない場合（フル状態の場合）にハイレベルとなり、１つでもエンプティエントリが存在する場合にはローレベルとなる。
【００５１】
最後に、ＨＥＡ＜１１：０＞は、前述の最優先順位のエンプティアドレスの出力信号である。ＨＥＡ＜１１：０＞としては、ＧＮＦＬを入力した結果、ＦＵＬＬがローレベルとなり、物理バンク内にエンプティエントリが存在する場合に、最も優先順位の高いエンプティエントリが格納されているメモリアドレスが出力される。本実施形態では、エンプティアドレスの内の最も小さいアドレスが出力される。
【００５２】
なお、信号ＳＲＣＨ、信号ＧＮＦＬ、信号ＰＲＧ＿ＨＩＴは、それぞれ論理・物理信号変換回路１４に入力される信号ＳＥＡＲＣＨ、信号ＧＥＮＦＵＬ、信号ＰＵＲＧＥ＿ＨＩＴと図６に示す論理物理変換テーブルからの出力との論理積をとることにより、信号ＬＢＡＮＫ＜２：０＞によって指定される論理バンクで、なおかつ論理物理変換テーブルに‘１’が設定されている物理バンクに対してのみ出力される信号である。
【００５３】
図示例の物理バンクは、物理的には６４ビット長、４Ｋワードでメモリ容量２５６ＫビットのターナリＣＡＭ構成の連想メモリアレイのブロックである。例えば、この物理バンクを１２８ビット長のバイナリＣＡＭとして設定した場合、異なる６４ビットの検索キーデータを用いて２回の一致検索が行われ、検索結果のＡＮＤがとられて最終的な検索結果として出力される。これにより、見かけ上、１２８ビット長のＣＡＭとして動作する。
【００５４】
この場合、物理バンクのワード数は、見かけ上半分の２Ｋワードになる。従って、１２８ビット長、４ＫワードのＣＡＭが必要な場合には、２つの物理バンクを連結して１つの論理バンクとして使用することになる。また、２５６ビット長のＣＡＭの場合には合計４回のＡＮＤ検索が行われる。なお、ターナリＣＡＭは、その‘Ｘ（ドントケア）’のデータを利用しないことによってバイナリＣＡＭとして使用することができる。
【００５５】
以下、図３〜図７を参照し、最大８個までの論理バンクを設定可能な場合を例に挙げて、ＣＡＭ１０の動作を具体的に説明する。
【００５６】
図３は、各論理バンクと各物理バンクとの対応関係を表す一実施形態の概念図である。同図には、論理バンク０〜４の５つの論理バンクが設定されている。なお、論理バンク５〜７には物理バンクが対応付けされていない。論理バンク０は１２８ビット長のターナリＣＡＭとして設定され、以下同様に、論理バンク１は６４ビット長のバイナリＣＡＭ、論理バンク２は１２８ビット長のバイナリＣＡＭ、論理バンク３は２５６ビット長のバイナリＣＡＭ、論理バンク４は２５６ビット長のターナリＣＡＭとして設定されている。
【００５７】
既に述べたように、各々の物理バンクの構成は、選択された論理バンクに応じて、論理・物理信号変換回路１４から出力される信号ＣＯＮＦＩＧ＜２：０＞により動的に設定される。この信号ＣＯＮＦＩＧ＜２：０＞は、本実施形態の場合、論理・物理信号変換回路１４の内部にある、それぞれの論理バンク０〜７に対応する３ビット×８個のレジスタ（図示省略）によって定義される。これらのレジスタの内容は、信号ＴＡＢＬＥ＿ＷＲを与えることにより、ＣＡＭ１０の外部から設定される。
【００５８】
図示例では、論理バンク０として、物理バンク０，２を連結して得られる１２８ビット長、４ＫワードのターナリＣＡＭが対応付けられ、以下同様に、論理バンク１として、物理バンク１の６４ビット長、４ＫワードのバイナリＣＡＭ、論理バンク２として、物理バンク１，４を連結して得られる１２８ビット長、４ＫワードのバイナリＣＡＭ、論理バンク３として、物理バンク３，７を連結して得られる２５６ビット長、２ＫワードのバイナリＣＡＭ、論理バンク４として、物理バンク５，６を連結して得られる２５６ビット長、２ＫワードのターナリＣＡＭがそれぞれ対応付けられている。
【００５９】
図３に示す各論理バンクと各物理バンクとの対応関係を図５の表に示す。論理バンクの指定は、論理・物理信号変換回路１４に入力される信号ＬＢＡＮＫ＜２：０＞で行われる。論理バンクと物理バンクとの対応関係は、図６に示すように、例えば論理・物理信号変換回路１４の内部にある論理物理変換テーブルによって定義される。この論理物理変換テーブルは、図５に示す各論理バンクと各物理バンクとの対応関係の表に対応するもので、図５の‘Ａｓｓｉｇｎ（対応付けあり）’、‘Ｎｏ  Ａｓｓｉｇｎ  （対応付けなし）’にそれぞれ対応して‘１’、‘０’が設定されている。
【００６０】
この論理物理変換テーブルには、信号ＴＡＢＬＥ＿ＷＲを与えることにより、図７にその対応関係を表すように、信号ＩＮ＜６３：０＞から入力される値が設定される。必要とするＣＡＭの構成に応じてそれぞれの論理バンクの構成を決定し、論理バンクの構成に応じて、図６に示す論理物理変換テーブルおよび信号ＣＯＮＦＩＧ＜２：０＞の内容を設定することにより、信号ＬＢＡＮＫ＜２：０＞で論理バンクを指定した時に、対応する物理バンクの構成を動的に変更して制御することができる。
【００６１】
ＣＡＭ１０では、一致検索を行う前に、各々の論理バンクに対応する連想メモリアレイ１２の各物理メモリに対してエントリデータの書き込みが行われる。エントリデータは、信号ＷＲＩＴＥを与えることにより、信号ＡＤＤＲＥＳＳ＜１４：０＞で指定される論理バンクのメモリアドレス、すなわちこの論理バンクに対応する物理バンクのメモリアドレスに対して信号ＤＡＴＩＮ＜６３：０＞が書き込まれる。
【００６２】
一例として、論理バンク２の１２８ビット長のバイナリＣＡＭに対してヒットアドレスの検索を行う場合、まず、信号ＬＢＡＮＫ＜２：０＞＝‘０１０（２進数）’として論理バンク２を指定する。この指定により、図６に示す論理物理変換テーブルの論理バンク２に対応する行の物理バンクの対応付けの設定＝‘０１００１０００’から対応する物理バンクは物理バンク１，４であることがわかる。そして、論理バンク２に対応するＣＯＮＦＩＧ＜２：０＞＝‘００１’が物理バンク１，４に対して与えられ、これらの物理バンク１，４の構成は１２８ビット長のバイナリＣＡＭに設定される。
【００６３】
ＤＡＴＩＮ＜６３：０＞として検索キーデータを入力し、かつ信号ＳＥＡＲＣＨを入力して検索の開始を指示すると、論理・物理信号変換回路１４から、物理バンク１，４に対してのみ信号ＳＲＣＨが与えられ、これらの物理バンク１，４でのみ一致検索が開始される。論理バンク２は１２８ビット長のバイナリＣＡＭであるから、既に述べたように、異なる６４ビットの検索キーデータを用いて２回のＡＮＤ検索が行われる。
【００６４】
その結果、これらの物理バンク１，４に登録されたエントリデータの中で、合計１２８ビット長の検索キーデータに一致するヒットエントリが存在する場合、信号ＨＩＴがハイレベルとなり、対応する物理バンク１，４から、ヒットエントリが登録されているヒットアドレスである信号ＨＨＡ＜１１：０＞が出力される。これらの信号ＨＩＴおよび信号ＨＨＡ＜１１：０＞は全てプライオリティ回路１８に入力される。なお、一致検索の結果、物理バンク１，４の中でヒットエントリが存在しない物理バンク、および信号ＳＲＣＨが与えられていない物理バンク０，２，３，５〜７からは、信号ＨＩＴとしてローレベルが出力される。
【００６５】
プライオリティ回路１８では、各々の物理バンクから入力される信号ＨＩＴによって優先順位を決定し、最優先順位の信号ＨＨＡ＜１１：０＞に最優先順位を持った物理バンクの番号３ビットを上位に付加した信号ＨＨＡ＜１４：０＞を出力する。例えば、信号ＨＩＴがハイレベルである最優先順位の物理バンクが‘５’ならば、付加される３ビットは‘１０１’となる。また、プライオリティ回路１８からは同時に信号ＨＩＴも出力される。
【００６６】
前述の通り、本実施形態では、物理バンクの番号が小さいほど優先順位が高いので、例えば物理バンク１にヒットエントリが存在する場合には、物理バンク４の状態に係わらず、プライオリティ回路１８からは物理バンク１の信号ＨＨＡ＜１１：０＞が出力され、ＨＨＡ＜１４：１２＞は‘００１’となる。また、プライオリティ回路１８から出力される信号ＨＩＴは、各々の物理バンク０〜７から供給される信号ＨＩＴの論理和をとったもので、物理バンク０〜７のいずれかにヒットエントリが存在すればハイレベルとなる。
【００６７】
同様に、エンプティアドレスの検索を行う場合、論理バンク２を指定すると、これに対応する物理バンク１，４に対してのみ、論理・物理信号変換回路１４から信号ＧＮＦＬが与えられる。信号ＧＥＮＦＵＬを入力して、エンプティアドレスの検索を開始すると、前述のように、物理バンク１，４に対してのみ信号ＧＮＦＬが与えられ、これらの物理バンク１，４においてエンプティアドレスの検索が開始される。
【００６８】
その結果、エンプティアドレスが存在する物理バンク１，４の信号ＦＵＬＬはローレベルとなり、対応する物理バンク１，４から、エンプティアドレスである信号ＨＥＡ＜１１：０＞が出力される。なお、エンプティアドレスの検索の結果、物理バンク１，４の中でエンプティアドレスが存在しない物理バンク、および信号ＧＮＦＬが与えられていない物理バンク０，２，３，５〜７からは、信号ＦＵＬＬとしてハイレベルが出力される。
【００６９】
プライオリティ回路１８では、各々の物理バンクから入力される信号ＦＵＬＬによって優先順位を決定し、優先順位に従って、最優先順位の信号ＨＥＡ＜１１：０＞に最優先順位の物理バンクの番号３ビットを上位に付加した信号ＨＥＡ＜１４：０＞を出力する。また、プライオリティ回路１８からは同時に信号ＦＵＬＬも出力される。信号ＦＵＬＬは、各々の物理バンク０〜７から入力される信号ＦＵＬＬの論理積をとったもので、物理バンク０〜７のいずれかにエンプティアドレスが存在すればローレベルとなる。
【００７０】
以上のように、ＣＡＭ１０では、大容量の連想メモリアレイ１２を複数の物理バンクのブロックに分割し、必要とするＣＡＭの構成に応じて、これらの物理バンクを論理バンクとして再構成することができる。これにより、複数の異なる構成のＣＡＭの機能を１つのＣＡＭデバイスで実現することができ、コストを大幅に削減することができる。
【００７１】
また、ＣＡＭ１０では、一つの物理バンクを複数の論理バンクに対応させることにより検索の度に異なる構成の連想メモリとして使用することができるため、従来の技術（３）の方法を外部回路および処理時間の増加なしに実現可能である。これにより、１物理バンクの容量よりも少ないデータを、他のデータと混在させて同一物理バンクに格納することが可能となり、連想メモリの容量を有効活用できる。
【００７２】
また、ＣＡＭ１０では、複数の構成の異なるＣＡＭの機能を論理バンクという概念で扱うことができるため、外部からの制御が容易であるという利点がある。また、大容量の連想メモリアレイ１２を分割して検索動作を行わせるため、つまり論理バンクに対応付けされている物理バンクにおいてのみ検索動作が行われるため、消費電力を低減することができる。
【００７３】
続いて、図１に示す複数のＣＡＭデバイスをカスケード接続して使用する場合を説明する。
【００７４】
図８は、複数のＣＡＭデバイスをカスケード接続した状態を表す一実施形態の概略図である。同図は、図１に示すＣＡＭデバイスを（ｎ＋１）個カスケード接続した状態を表す。本実施形態では、デバイスＣＡＭ０が最上位のＣＡＭデバイスであり、デバイスＣＡＭｎが最下位のＣＡＭデバイスである。複数のＣＡＭデバイスを使用する場合、信号ＨＩＴ、信号ＦＵＬＬに相当する信号が最上位のＣＡＭデバイスから最下位のＣＡＭデバイスに向かって順次伝達される。
【００７５】
最上位のデバイスＣＡＭ０のＨＩ端子はローレベルとされ、ＦＬＩ端子はハイレベルとされている。すなわち、デバイスＣＡＭ０のカスケード制御回路２０に入力される信号ＨＩはヒットエントリが存在しないことを表す状態とされ、信号ＦＬＩはエンプティエントリが存在しないフル状態であることを表す状態とされる。
【００７６】
最上位のデバイスＣＡＭ０のＨＯ端子およびＦＬＯ端子から出力される信号、すなわちデバイスＣＡＭ０のカスケード制御回路２０から出力される信号ＨＯおよび信号ＦＬＯは、それぞれ次段のデバイスＣＡＭ１のＨＩ端子およびＦＬＩ端子に入力されている。以下同様にして、前段のＣＡＭデバイスのＨＯ端子およびＦＬＯ端子から出力される信号が、次段のＣＡＭデバイスのＨＩ端子およびＦＬＩ端子に入力されている。
【００７７】
また、図示を省略しているが、それぞれのＣＡＭデバイスには図１に示すＣＡＭ１０に入力されている各種の信号が共通に入力されている。それぞれのＣＡＭデバイスからは信号ＨＨＡ／ＨＥＡ＜１４：０＞が出力され、ワイヤード接続されている。また、最下位のデバイスＣＡＭｎからは信号ＨＩＴおよび信号ＦＵＬＬが出力されている。この最下位のデバイスＣＡＭｎから出力される信号ＨＩＴおよび信号ＦＵＬＬが最終的な検索結果となる。
【００７８】
本実施形態の場合、それぞれのＣＡＭデバイスにおいて、信号ＨＩＴは、ヒットエントリが１つでも存在する場合にはハイレベルとなり、ヒットエントリが全く存在しない場合にのみローレベルとなる。カスケード制御回路２０は、自分自身の検索結果の信号ＨＩＴと、前段のＣＡＭデバイスから入力される信号ＨＩＴ、すなわち前段のカスケード制御回路２０の端子ＨＯから出力される信号との論理和をとって、その演算結果を自分自身の端子ＨＯから出力する。
【００７９】
従って、デバイスＣＡＭ０〜ＣＡＭｎのうちの少なくとも１つのＣＡＭデバイスにおいてヒットエントリが存在する場合、最下位のデバイスＣＡＭｎから出力される信号ＨＩＴはハイレベルとなる。これに対し、全てのデバイスＣＡＭ０〜ＣＡＭｎにおいて全くヒットエントリが存在しない場合にのみ、最下位のデバイスＣＡＭｎから出力される信号ＨＩＴはローレベルとなる。
【００８０】
また、信号ＨＨＡ／ＨＥＡ＜１４：０＞としては、ヒットエントリが存在する、最優先順位のＣＡＭデバイスから出力される信号ＨＨＡ＜１４：０＞が出力される。
【００８１】
また、それぞれのＣＡＭデバイスにおいて、信号ＦＵＬＬは、エンプティエントリが１つでも存在する場合にはローレベルとなり、エンプティエントリが全く存在しない場合にのみハイレベルとなる。カスケード制御回路２０は、自分自身の検索結果の信号ＦＵＬＬと、前段のＣＡＭデバイスから入力される信号ＦＵＬＬ、すなわち前段のカスケード制御回路２０の端子ＦＬＯから出力される信号との論理積をとって、その演算結果を自分自身の端子ＦＬＯから出力する。
【００８２】
従って、デバイスＣＡＭ０〜ＣＡＭｎのうちの少なくとも１つのＣＡＭデバイスにおいてエンプティエントリが存在する場合、最下位のデバイスＣＡＭｎから出力される信号ＦＵＬＬはローレベルとなる。これに対し、全てのデバイスＣＡＭ０〜ＣＡＭｎにおいて全くエンプティエントリが存在しない場合にのみ、最下位のデバイスＣＡＭｎから出力される信号ＦＵＬＬはハイレベルとなる。
【００８３】
また、信号ＨＨＡ／ＨＥＡ＜１４：０＞としては、エンプティエントリが存在する、最優先順位のＣＡＭデバイスから出力される信号ＨＥＡ＜１４：０＞が出力される。
【００８４】
図示例のように、複数のＣＡＭデバイスをカスケード接続して使用する場合、外部からは、あたかも大容量の１つのＣＡＭデバイスを使用するのと全く同じように扱うことができる。
【００８５】
なお、複数のＣＡＭデバイスを接続して使用する場合、どのＣＡＭデバイスにアクセスするかは、例えばＣＡＭデバイスの外部でアドレスをデコードして、個々のＣＡＭデバイスにアクセスするための制御信号を発生して、それぞれのＣＡＭデバイスに入力するようにしてもよいし、ＣＡＭデバイスの内部でアドレスをデコードして、ＣＡＭデバイス自身がアクセスされていることを検出して動作するようにしてもよい。
【００８６】
また、ＨＨＡ／ＨＥＡの出力には、例えば、上位にビット＜１７：１５＞を付加し、アドレスを拡張してこの部分にＣＡＭデバイスの番号を入れる処理が必要となるが、これはどのデバイスが有効な結果を出力したかを判定して処理する回路を外部に付加してもよいし、ＣＡＭデバイス内部で生成させるようにしてもよい。
【００８７】
以下同様に、図９を参照し、最大８個までの論理バンクを設定可能な場合を例に挙げて、複数のＣＡＭデバイスをカスケード接続して使用する場合の動作を説明する。
【００８８】
図９は、各論理バンクと各ＣＡＭデバイスの物理バンクとの対応関係を表す一実施形態の概念図である。同図には、論理バンク０〜５の６つの論理バンクが設定されている。なお、論理バンク６，７には物理バンクが対応付けされていない。論理バンク０は１２８ビット長のバイナリＣＡＭとして設定され、以下同様に、論理バンク１は６４ビット長のターナリＣＡＭ、論理バンク２は１２８ビット長のターナリＣＡＭ、論理バンク３は２５６ビット長のターナリＣＡＭ、論理バンク４は１２８ビット長のターナリＣＡＭ、論理バンク５は６４ビット長のターナリＣＡＭとして設定されている。
【００８９】
また、論理バンク０として、デバイス０の物理バンク０，２、デバイス１の物理バンク２、デバイス２の物理バンク１を連結して得られる１２８ビット長、８ＫワードのバイナリＣＡＭが対応付けられ、以下同様に、論理バンク１として、デバイス０の物理バンク１、デバイス１の物理バンク０、デバイス２の物理バンク２を連結して得られる６４ビット長、１２ＫワードのターナリＣＡＭ、論理バンク２として、デバイス０の物理バンク１、デバイス１の物理バンク０を連結して得られる１２８ビット長、４ＫワードのターナリＣＡＭ、論理バンク３として、デバイス１の物理バンク１，３を連結して得られる２５６ビット長、２ＫワードのターナリＣＡＭ、論理バンク４として、デバイス０の物理バンク３、デバイス２の物理バンク０を連結して得られる１２８ビット長、４ＫワードのターナリＣＡＭ、論理バンク５として、デバイス２の物理バンク３の６４ビット長、４ＫワードのターナリＣＡＭがそれぞれ対応付けられている。
【００９０】
この場合、それぞれのデバイス０〜２の論理・物理信号変換回路１４が備える論理・物理変換テーブルには、論理バンク０〜７と自分自身の物理バンクとの対応付けを表す情報が格納される。
【００９１】
例えば、デバイス０の論理・物理変換テーブルにおいて、論理バンク０は物理バンク０，２に対応付けられ、以下同様に、論理バンク１は物理バンク１、論理バンク２も物理バンク１、論理バンク３は対応付けなし、論理バンク４は物理バンク３、論理バンク５は対応付けなし、論理バンク６，７も対応付けなしとなる。また、デバイス１，２についても同様である。
【００９２】
検索動作は、ＣＡＭ１０を単体で使用する場合と同じである。すなわち、論理バンクが指定されると、それぞれのデバイス０〜２において、選択された論理バンクに対応する信号ＣＯＮＦＩＧ＜２：０＞が、選択された論理バンクに対応付けられている物理バンクに対して与えられ、その構成が動的に設定される。そして、選択された論理バンクに対応付けられている物理バンクにおいてのみ検索動作が行われる。
【００９３】
検索の結果、最上位のＣＡＭデバイスから最下位のＣＡＭデバイスに向かって信号ＨＩＴおよび信号ＦＵＬＬが伝達される。既に述べたように、カスケード制御回路２０は、論理バンクに対応する物理バンクが存在するデバイスでは、自分自身の検索結果と、上位側のデバイスから供給される信号ＨＩＴ、信号ＦＵＬＬとの論理をとって、その演算結果を下位側のデバイスに順次伝達する。
【００９４】
ここで、複数のＣＡＭデバイスをカスケード接続して使用する場合、例えば検索対象の論理バンクに対応する物理バンクが、あるデバイスには存在するが、あるデバイスには存在しない場合があり得る。例えば、図９に示す例の場合、論理バンク０はデバイス０の物理バンク０，２にのみ対応付けがなされており、デバイス１，２の物理バンクには対応付けされていない。この場合、論理バンク０に対応する物理バンクが存在するデバイス０では検索動作が行われるが、存在しないデバイス１，２では検索動作が行われない。
【００９５】
このような場合でも正しい検索結果が得られるように、論理・物理信号変換回路１４は、論理物理変換テーブルに基づいて、自分自身のＣＡＭデバイスの中に、選択された論理バンクに対応する物理バンクが存在するのかしないのかを示す信号ＰＡＳＳを出力する。
【００９６】
カスケード制御回路２０は、論理・物理信号変換回路１４から供給される信号ＰＡＳＳに応じて、論理バンクに対応する物理バンクが存在しないデバイスでは、自分自身の検索結果として、一致が存在しない状態の検索結果、すなわちヒットエントリが存在しない状態の信号ＨＩＴ、本実施形態の場合はローレベル、およびエンプティエントリが存在しない状態の信号ＦＵＬＬ、本実施形態の場合はハイレベルと、上位側のデバイスから供給される信号ＨＩＴ、信号ＦＵＬＬとの論理をとって、その演算結果を下位側のデバイスへ供給する。
【００９７】
これにより、最下位のＣＡＭデバイスから出力される信号ＨＩＴ、信号ＦＵＬＬとして常に正しい検索結果を得ることができる。
【００９８】
以上のように、複数のＣＡＭデバイスをカスケード接続して使用することによって、１個のＣＡＭデバイスでは実現不可能な、より多数の、複数種類の異なる構成のＣＡＭの機能を効率よく実現することができ、さらにコストを削減することができる。
【００９９】
なお、物理バンクの個数は、２つ以上いくつの物理バンクに分割してもよいし、論理バンクの個数は１つ以上いくつの論理バンクを設定可能としてもよい。また、カスケード接続して使用するＣＡＭデバイスの個数も何ら制限されない。また、論理バンクおよび物理バンクに設定可能なビット長やその個数も何ら限定されない。また、論理バンクおよび物理バンクの構成の設定、論理バンクと物理バンクとの対応付け設定も何ら限定されず自由に設定することができる。
【０１００】
また、上記実施形態では、物理バンクの構成を決定する要素として、バイナリＣＡＭなのかターナリＣＡＭなのかというＣＡＭの種類、およびビット長の２つを挙げて説明している。しかし、本発明はこれに限定されず、例えばこれ以外の機能的な違い等を物理バンクの構成を決定する要素として選択可能としてもよい。また、物理バンクの構成を決定する要素として、本発明は、少なくとも１つの要素を含んでいればよい。
【０１０１】
さらに、上記実施形態では、連想メモリアレイ１２、論理・物理信号変換回路１４、デコーダ１６、プライオリティ回路１８、カスケード制御回路２０の具体的な構成回路を図示していないが、本発明では、これらの具体的な回路構成は何ら限定されず、上述する機能を実現する回路であればどのような構成のものであってもよい。特に、論理・物理信号変換回路１４は、レジスタやテーブルを用いて構成する場合を例示したが、何ら限定されず、他の回路を用いて構成してもよい。
【０１０２】
また、本発明は、ネットワーク装置に好適に適用可能なものであるが、ネットワーク装置だけに限定されるわけではなく、構成の異なる複数のＣＡＭを使用するどのようなシステムにも適用可能である。
【０１０３】
本発明の連想メモリは、基本的に以上のようなものである。
以上、本発明の連想メモリについて詳細に説明したが、本発明は上記実施形態に限定されず、本発明の主旨を逸脱しない範囲において、種々の改良や変更をしてもよいのはもちろんである。
【０１０４】
【発明の効果】
以上詳細に説明した様に、本発明の連想メモリによれば、大規模な連想メモリを使用用途に応じて分割して使用することができ、構成の異なる複数の連想メモリの機能を１つのデバイスで、もしくは複数のデバイスを組み合わせて実現することができるため、コストを削減することができる。また、本発明の連想メモリによれば、論理バンクの概念により、物理バンクのメモリ空間を意識する必要がないため、制御が容易であるという利点がある。また、本発明の連想メモリによれば、論理バンクに対応する物理バンクに対してのみ検索動作が行われるため、全ての連想メモリセルが同時動作する連想メモリでは常に問題となる消費電力も低減することができる。
【図面の簡単な説明】
【図１】本発明の連想メモリの一実施形態の構成概略図である。
【図２】物理バンクに接続される信号を表す一実施形態の概念図である。
【図３】各論理バンクと各物理バンクとの対応関係を表す一実施形態の概念図である。
【図４】信号ＣＯＮＦＩＧ＜２：０＞と論理バンクの構成との対応を表す一実施形態の表である。
【図５】各論理バンクと各物理バンクとの対応関係を表す一実施形態の表である。
【図６】各論理バンクと各物理バンクとの対応関係を表す一実施形態のテーブルである。
【図７】図６のテーブルと信号ＩＮ＜６３：０＞の各ビットとの間の関係を表す一実施形態の表である。
【図８】複数のＣＡＭデバイスをカスケード接続した状態を表す一実施形態の概略図である。
【図９】各論理バンクと各ＣＡＭデバイスの物理バンクとの対応関係を表す一実施形態の概念図である。
【図１０】従来の連想メモリを利用したシステムの一例の構成概略図である。
【符号の説明】
１０  連想メモリ
１２  連想メモリアレイ
１４  論理・物理信号変換回路
１６  デコーダ
１８  プライオリティ回路
２０  カスケード制御回路
【図１】
2004265528.tif 000003
【図２】
2004265528.tif 000004
【図３】
2004265528.tif 000005
【図４】
2004265528.tif 000006
【図５】
2004265528.tif 000007
【図６】
2004265528.tif 000008
【図７】
2004265528.tif 000009
【図８】
2004265528.tif 000010
【図９】
2004265528.tif 000011
【図１０】
2004265528.tif 000012