(57)【要約】【課題】　データ転送速度の高いネットワーク・システムの消費電力を削減する。【解決手段】　検索データ１２と一致した記憶データのすべてに対して記憶データの有効状態を真とする論理和演算を行った結果の一致データ論理和情報を生成する連想メモリ１を用いて、連想メモリ１に検索データ１２を入力して１次検索を行い一致データ論理和線上に一致データ論理和情報を取り出し、１次検索にて一致した記憶データに対して得られた一致データ論理和情報を検索データとして２次検索を行い、一致データ論理和情報と一致したワードの一致線５のみを検索結果として選択する。選択された一致線５をエンコードして最適のメモリ・アドレス信号４０３を求め、最短ネットワーク接続を可能とする転送先アドレス４０５を得、入力転送データ４０８中のデータ部４１２及び目的地ネットワーク・アドレス４１１を合成して出力転送データ４０９を生成するものである。【選択図】　　　図１
2004134081.tif 000002
【特許請求の範囲】
【請求項１】
　ａ）ｎビット長のｍ個の記憶データを格納するｎ個のデータ・セルと；
　前記記憶データの各ビットを検索対象から除外するか否かを対応するビットのマスク有効状態、マスク無効状態により設定するマスク情報を格納するｎ個のマスク・セルと；
　入力データと前記記憶データとをワード単位で比較し、比較結果が一致するワードに対して一致信号を一致線上に出力するｎ個の比較器と；
　前記一致線上のデータと前記記憶データとをビット列単位で論理演算し、演算結果を一致データ中間論理線上に出力するｎ個の論理ゲートと；を含む
　ｍ個の連想メモリ・ワードと（ｍ，ｎは自然数）、
　ｂ）前記一致データ中間論理線上に出力されたｎビットの中間一致データを格納するラッチ回路と、
　ｃ）検索データと前記中間一致データのいずれか一方を前記入力データとして前記連想メモリ・ワードに選択的に供給するセレクタ回路と、
　ｄ）前記入力データとして前記検索データが選択された場合には前記マスク情報を考慮して比較を行い、前記中間一致データが選択された場合には無視して比較を行うよう前記比較器を制御する制御回路と、
を具備したことを特徴とする連想メモリ。
【請求項２】
　請求項１に記載の連想メモリにおいて、
　前記比較器は、前記検索データを対象とする比較結果と前記中間一致データを対象とする比較結果とを同一の一致線上に出力することを特徴とする連想メモリ。
【請求項３】
　請求項１に記載の連想メモリにおいて、
　検索動作に先立って前記一致線及び前記一致データ中間論理線を所定電位にプリ・チャージするプリ・チャージ手段を設けたことを特徴とする連想メモリ。
【請求項４】
　請求項１に記載の連想メモリにおいて、
　前記マスク情報の有効状態を"０"、無効状態を"１"とし、
　前記記憶データの有効状態を"１"、無効状態を"０"とし、
　前記一致データ中間論理線の有効状態を"１"、無効状態を"０"とし、
　前記一致線の有効状態を"１"、無効状態を"０"とするよう設定することを特徴とする連想メモリ。
【請求項５】
　請求項４に記載の連想メモリにおいて、
　前記比較器が前記一致線の有効状態"１"を真としたワイアードＡＮＤ論理接続を構成することを特徴とする連想メモリ。
【請求項６】
　請求項４に記載の連想メモリにおいて、
　前記論理ゲートが前記一致データ中間論理線の有効状態"１"を真としたワイアードＡＮＤ論理接続を構成することを特徴とする連想メモリ。
【請求項７】
　請求項４に記載の連想メモリにおいて、
　前記中間一致データとして前記記憶データの有効状態"１"を真とした論理和演算データを得ることを特徴とする連想メモリ。
【請求項８】
　請求項１に記載の連想メモリにおいて、
　前記マスク情報の有効状態を"０"、無効状態を"１"とし、
　前記記憶データの有効状態を"０"、無効状態を"１"とし、
　前記一致データ中間論理線の有効状態を"１"、無効状態を"０"とし、
　前記一致線の有効状態を"１"、無効状態を"０"とするよう設定することを特徴とする連想メモリ。
【請求項９】
　請求項８に記載の連想メモリにおいて、
　前記比較器が前記一致線の有効状態"１"を真としたワイアードＡＮＤ論理接続を構成することを特徴とする連想メモリ。
【請求項１０】
　請求項８に記載の連想メモリにおいて、
　前記論理ゲートが前記一致データ中間論理線の有効状態"１"を真としたワイアードＡＮＤ論理接続を構成することを特徴とする連想メモリ。
【請求項１１】
　請求項８に記載の連想メモリにおいて、
　前記中間一致データとして前記記憶データの有効状態"０"を真とした論理和演算データを得ることを特徴とする連想メモリ。
【請求項１２】
　ａ）ｎビット長のｍ個の記憶データを格納するｍ×ｎ個の第１のデータ・セルと；
　前記記憶データの各ビットを検索対象から除外するか否かを対応するビットのマスク有効状態、マスク無効状態により設定するマスク情報を格納するｍ×ｎ個のマスクセルと；
　検索データと前記記憶データとを前記マスク情報を考慮してワード単位で比較し、比較結果が一致するワードに対して一致信号を中間一致線上に出力するｍ×ｎ個の第１の比較器と；
　前記中間一致線上のデータと前記記憶データとをビット列単位で論理演算し、
　演算結果を一致データ論理和線上に出力するｍ×ｎ個の論理ゲートと；
を含む第１のメモリと、
　ｂ）前記記憶データをワード毎に前記第１のデータ・セルに対応付けて格納するｍ×ｎ個の第２のデータ・セルと；
　前記一致データ論理和線上のデータと前記第２のデータ・セルに格納された前記記憶データとをワード単位で比較し、比較結果が一致するワードに対して一致信号を一致線上に出力するｍ×ｎ個の第２の比較器と；を具備したことを特徴とする連想メモリ。
【請求項１３】
　請求項１２に記載の連想メモリにおいて、
　検索動作に先立って前記一致線、前記中間一致線及び前記一致データ論理和線を所定電位にプリ・チャージするプリチャージ手段を設けたことを特徴とする連想メモリ。
【請求項１４】
　請求項１２に記載の連想メモリにおいて、
　前記マスク情報の有効状態を"０"、無効状態を"１"とし、
　前記記憶データの有効状態を"１"、無効状態を"０"とし、
　前記一致データ論理和線の有効状態を"０"、無効状態を"１"とし、
　前記中間一致線の有効状態を"１"、無効状態を"０"とし、
　前記一致線の有効状態を"１"、無効状態を"０"とするよう設定する
ことを特徴とする連想メモリ。
【請求項１５】
　請求項１４に記載の連想メモリにおいて、
　前記第１の比較器が前記中間一致線の有効状態"１"を真としたワイアードＡＮＤ論理接続を構成することを特徴とする連想メモリ。
【請求項１６】
　請求項１４に記載の連想メモリにおいて、
　前記一致データ論理和線上のデータをいったん格納する記憶手段を前記第１のメモリと第２のメモリとの間に介挿することを特徴とする連想メモリ。
【請求項１７】
　目的地ネットワークアドレスを検索データとする連想メモリを内蔵するルータにおいて、
　前記連想メモリとして請求項１乃至１６に記載の連想メモリを備えたことを特徴とするルータ。
【請求項１８】
　請求項１６に記載のルータを介してネットワークに接続された機器間でデータ通信を行うことを特徴とするネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は、連想メモリおよびその検索方法およびルータおよびネットワークシステムに関する。特に検索マスク機能を有する連想メモリとその検索方法およびそれを用いたルータおよびネットワークシステムに関する。
【背景技術】
【０００２】
　従来のコンピュータ・ネットワーク・システムに用いられるネットワーク・ルータ（以後「ルータ」という）では、次に示すように最適転送先を計算する機能が不可欠である。
【０００３】
　従来のコンピュータ・ネットワークの構成の接続例を図１９に示す。ネットワークに参加しているユーザ機器（例えばコンピュータ端末など）は、他のユーザ機器と識別するために、その機器がネットワークに参加するときに、あらかじめ決められた規則に従って特定のネットワーク・アドレスを割り当てられる。ここではネットワーク・アドレスは複数桁の数値、例えば４桁の数値（ａ．ｂ．ｃ．ｄ）で表現されるものとして説明する。また、あらかじめ決められた規則は、例えばネットワーク・アドレスの先頭の数値でイギリス、ドイツ、日本などの国を示し、第２番目の数値で国の中の都市名を示し、更に第３番目の数値で都市の中の企業名を示す、というように階層構造をとっている。以降、この階層をセグメントと呼ぶこととする。図１９においては、セグメントの階層構造を模擬的に示したものである。図において太線で囲まれた１つの矩形が１のセグメントである。図１９では、ネットワーク・アドレスの先頭の数値が１であるセグメント１と、先頭の数値が２であるセグメント２と、先頭の数値が３であるセグメント３が、最上位のセグメントとして存在している。セグメント１の下の階層に、上位２つの数値が１．２であるネットワーク・アドレスを持つセグメント４があり、更にその下に上位３つの数値が１．２．２であるネットワーク・アドレスを持つセグメント６があり、更にその中にネットワーク・アドレス１．２．２．１を持つユーザ機器ＰＣ４０１−１が接続されている。また、セグメント２の下の階層に、上位２つの数値が２．１であるネットワーク・アドレスを持つセグメント５があり、更にその下に上位３つの数値が２．１．１であるネットワーク・アドレスを持つセグメント７がある。図に例示されているアドレスにおいて、＊はドント・ケアを意味する。
【０００４】
　各セグメントは、ネットワークに参加しているユーザ機器間の通信データを転送するためにルータを有している。図１９の構成例では、セグメント１はルータ４００−１を、セグメント２はルータ４００−２を、セグメント３はルータ４００−３を、セグメント４はルータ４００−４を、セグメント５はルータ４００−５を、セグメント６はルータ４００−６を、セグメント７はルータ４００−７を、それぞれ有している。セグメントが有するルータは、そのルータに接続されているユーザ機器または他のルータから入力された転送データを、転送データに付随する転送先アドレスとネットワーク機器の接続関係を基に最適な転送ルートを計算し、その最適なルートを経由して転送先にデータを転送する。図１９の構成例では、各ルータはそのセグメント直下のルータまたはユーザ機器と接続されている。また、ルータ４００−３は、ルータ４００−１、ルータ４００−４、ルータ４００−６、ルータ４００−２、ルータ４００−７とも接続している。
【０００５】
　各ユーザ機器同士を直接通信回線で接続するのではなく、ルータの通信制御機能を用いて通信データの転送を制御して通信を行うことにより、有限の通信回線を効率よく使用している。
【０００６】
　次に、これらルータの説明を図２０を用いて行う。図ではルータ４００−３を例に示しているが、他のルータもこれと同様の構成である。
　ルータ４００−３には自分自身が属するセグメントのネットワーク・アドレス（３．＊．＊．＊）以外のセグメントのネットワーク・アドレス情報を記憶させている。これら各ネットワーク・アドレスは、その各桁を４進数で表現した全体で８ビットのビット列で表現されるものと仮定する。例えば、ネットワーク・アドレス（１．＊．＊．＊）はビット列（０１．００．００．００）で表現される。以降、この表現のビット列を記憶データと呼ぶ。ここで、＊はドント・ケアであるので、（０１．００．００．００）のビット列の上位２ビットが有効でありそれ以下のビットは無効であることを示す必要がある。そこで、マスク情報と呼ばれる情報を記憶データと対になって記憶させている。この例では、（００．１１．１１．１１）としている。ここで、“０”がマスク無効状態を“１”がマスク有効状態を示している。これら記憶データおよびマスク情報は、図示のようにルータの中で連想メモリ１１６に格納されている。連想メモリ・ワード１１７−１には、ルータ４００−１が属するセグメント１のネットワーク・アドレス（１．＊．＊．＊）が記憶されている。連想メモリ・ワード１１７−２には、ルータ４００−２が属するセグメント２のネットワーク・アドレス（２．＊．＊．＊）が記憶されている。連想メモリ・ワード１１７−３には、ルータ４００−６が属するセグメント６のネットワーク・アドレス（１．２．２．＊）が記憶されている。連想メモリ・ワード１１７−４には、ルータ４００−４が属するセグメント４のネットワーク・アドレス（１．２．＊．＊）が記憶されている。連想メモリ・ワード１１７−５には、ルータ４００−７が属するセグメント７のネットワーク・アドレス（２．１．１．＊）が記憶されている。連想メモリ１１６は、通常のメモリと同様にアドレスを指定して記憶データの書き込み、読み出しを行う機能のほかに、入力した検索データ１０２と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報の有効状態のビットが最も少ない記憶データに対応するマスク一致線１１９−１〜１１９−５を有効状態にする機能を有している。連想メモリ１１６が出力したマスク一致線１１９−１〜１１９−５はエンコーダ４０２によりメモリ・アドレス信号４０３に符号化される。
【０００７】
　メモリ４０４には、連想メモリ１１６の各連想メモリ・ワードに格納されている記憶データ、マスク情報により構成されるセグメントのネットワーク・アドレスに対応するルータのネットワーク・アドレスを、連想メモリ１１６の格納アドレスと同一のアドレスのワードに記憶させてある。たとえば、連想メモリ１１６の連想メモリ・ワード１にはアドレス（１．＊．＊．＊）が記憶されているが、これに対応する図１９のルータ４００−１のネットワーク・アドレスがメモリ４０４のワード１に格納されている。同様にメモリ４０４のワード２にはルータ４００−２のアドレスが、ワード３にはルータ４００−６のアドレスが、ワード４にはルータ４００−４のアドレスが、ワード５にはルータ４００−７のアドレスが格納されている。メモリ４０４はメモリ・アドレス信号４０３をリード・アドレスとして指定される格納データを、メモリ・データ信号４０５として出力する。
【０００８】
　冷却装置４１４は、発熱量の多い従来の連想メモリ１１６を冷却する。これは、例えば空冷ファンなどで構成される。
【０００９】
　なお、図には示していないが、各ルータはその内部にＣＰＵを有しており、そのＣＰＵにより上述したルータの動作の制御が行われる。
【００１０】
　次に、各ルータによって制御される従来のネットワークのデータ転送の動作例を説明する。例えばルータ４００−３に入力された転送データの目的地ネットワーク・アドレスが（１．２．１．１）の場合、従来の連想メモリ１１６で検索すると連想メモリ・ワード１の（１．＊．＊．＊）、および連想メモリ・ワード４の（１．２．＊．＊）が一致するが、その中でマスク情報の有効状態のビットが最も少ない連想メモリ・ワード４に対応するマスク一致線１１９−４のみが有効状態となる。これにより、エンコーダ４０２はメモリ・アドレス４０３として“４”を出力し、メモリ４０４はルータ４００−４のネットワーク・アドレスをメモリ・データ信号４０５として出力する。これにより、ルータ４００−３は、目的地アドレス（１．２．１．１）の入力転送データを、ルータ３００−４に向けて転送する。ルータ３００−４は転送されてきたデータに基づいて上述したのと同様な動作を行い、次々とルータにデータを転送して最終目的地のネットワーク・アドレス（１．２．１．１）に接続しているユーザ機器にデータを転送する。
【００１１】
　図１５は、従来の連想メモリの一構成例を示すブロック図である。従来、この種の連想メモリとしては、例えば特開平１１−０７３７８２号に示すものが挙げられる。連想メモリ１１６は、ｎビット２入力１出力セレクタ１２８と、ｎビットｍ語の連想メモリ・ワード１１７−１〜１１７−ｍと、ｎビット・ラッチ１２６と制御回路１３１を有しており、各連想メモリ・ワード１１７−ｊは、ｎ個の連想メモリ・セル１１８−ｊ−１〜１１８−ｊ−ｎと１個のラッチ１２３−ｊを備えている。各連想メモリ・ワード１１７−ｊには、対応するデータ・ワード線１０６−ｊ、マスク・ワード線１１１−ｊが入力のために接続され、対応するマスク一致線１１９−ｊ、およびｎ本の最短マスク線１２２−１〜１２２−ｎが出力のために接続され、ｎ本のビット線１０３−１〜１０３−ｎが入出力のために接続されている。
【００１２】
　各連想メモリ・セル１１８−ｊ−ｋには、対応するデータ・ワード線１０６−ｊ、マスク・ワード線１１１−ｊが入力のために接続され、対応するデータ一致線１０７−ｊ、マスク一致線１１９−ｊ、および最短マスク線１２２−ｋが出力のために接続され、ビット線１０３−ｋが入出力のために接続されている。
【００１３】
　各連想メモリ・セル１１８−ｊ−ｋは、ビット線１０３−ｋを介して外部から入力される記憶データの対応するビット情報を格納するデータ・セル１０８−ｊ−ｋと、データ・セルに記憶されたビット情報と外部から入力される検索データ１０２の対応するビット情報１０２−ｋとを比較する比較器１１３−ｊ−ｋと、外部からビット線１０３−ｋを介して入力されるマスク情報の対応するビット情報を格納するマスク・セル１１２−ｊ−ｋと、マスク・セルに記憶されたビット情報とｎビット・ラッチ１２６から出力された最短マスク情報１２７の対応するビット情報１２７−ｋとを比較するマスク比較器１２０−ｊ−ｋと、および論理ゲート１２１−ｊ−ｋとを備えている。
【００１４】
　なお、本例では、マスク情報の有効状態を“１”、無効状態を“０”とし、最短マスク線１２２−１〜１２２−ｎの有効状態を“１”、無効状態を“０”とする。データ一致線１０７−１〜１０７−ｍの有効状態を“１”、無効状態を“０”とする。また、マスク一致線１１９−１〜１１９−ｍの有効状態を“１”、無効状態を“０”とする。
【００１５】
　データ・セル１０８−１−１〜１０８−ｍ−ｎは、対応するデータ・ワード線１０６が有効状態の場合、対応するビット線１０３に書き込みデータがドライブされていれば記憶データとして格納し、対応するビット線１０３がドライブされていなければ格納している記憶データを対応するビット線１０３に出力する。対応するデータ・ワード線１０６が無効状態ならば、ビット線１０３に対してなんら操作は行わない。また、対応するデータ・ワード線１０６の値にかかわらず、格納している記憶データを同一の連想メモリ・セル１１８−１−１〜１１８−ｍ−ｎの中の比較器１１３に出力する。
【００１６】
　マスク・セル１１２―１−１〜１１２−ｍ−ｎは、対応するマスク・ワード線１１１が有効状態の場合、対応するビット線１０３に書き込みデータがドライブされていれば書き込みデータをマスク情報として格納し、対応するビット線１０３がドライブされていなければ、格納しているマスク情報を対応するビット線１０３に出力する。対応するマスク・ワード線１１１が無効状態ならば、ビット線１０３に対してなんら操作は行わない。また、対応するマスク・ワード線１１１の値にかかわらず、格納しているマスク情報を同一の連想メモリ・セル１１８−１−１〜１１８−ｍ−ｎの中の比較器１１３に出力する。
【００１７】
　データ一致線１０７は、検索動作の開始前には、ハイ・レベルにプリ・チャージされているか、図示しない抵抗によりプル・アップされ、有効状態“１”になっているものとする。
【００１８】
　比較器１１３は、対応するビット線１０３と、それに同一の連想メモリ・セル１１８−１−１〜１１８−ｍ−ｎの中のデータ・セル１０８の記憶データおよびマスク・セル１１２のマスク情報を入力とし、マスク情報が有効状態、またはビット線１０３の値と記憶データが一致するならば対応するデータ一致線１０７を開放状態にし、それ以外の場合には無効状態“０”を出力する。連想メモリ・ワード１１７の中のｎ個の比較器１１３がすべてデータ一致線１０７を開放状態にしているときに、データ一致線１０７は有効状態“１”となり、それ以外の場合には無効状態“０”となるワイアードＡＮＤ論理接続を構成している。つまり、検索動作時には、連想メモリ・ワード１１７が格納している記憶データとビット線１０３−１〜１０３−ｎがマスク情報により比較対象から除外されたビットを除いて完全に一致する場合に限り、データ一致線１０７は有効状態“１”となり、それ以外の場合は無効状態“０”となる。もちろん同様の動作となるように通常の論理ゲートを用いて構成してもかまわない。
【００１９】
　論理ゲート１２１−１−１〜１２１−ｍ−ｎは、同一の連想メモリ・ワード１１７−１〜１１７−ｍの中のデータ一致線１０７−１〜１０７−ｍが有効状態“１”かつ、同一の連想メモリ・セル１１８−１−１〜１１８−ｍ−ｎの中のマスク・セル１１２−１−１〜１１２−ｍ−ｎに格納されたマスク情報が無効状態“０”のときに、対応する最短マスク線１２２−１〜１２２−ｎに無効状態“０”を出力し、それ以外の場合には開放状態にする。
【００２０】
　各最短マスク線１２２−１〜１２２−ｎは、抵抗１２５−１〜１２５−ｎによりプル・アップされており、対応するｍ個の論理ゲート１２１−１−１〜１２１−ｍ−ｎとワイアードＡＮＤ論理接続を構成している。従って、接続されているｍ個の論理ゲート１２１がすべて最短マスク線１２２を開放状態にしているときに、最短マスク線１２２は有効状態“１”となり、それ以外の場合には無効状態“０”となる。
【００２１】
　ラッチ１２３−１〜１２３−ｍは、同一の連想メモリ・ワード１１７−１〜１１７−ｍの中のデータ一致線１０７−１〜１０７−ｍの状態を、ラッチ制御線１２４が有効状態の時に内部に格納する。また、格納した状態を出力するため、同一の連想メモリ・ワード１１７−１〜１１７−ｍの中にあるマスク一致線１１９―１〜１１９−ｍと対応し、ワイアード論理接続されている。ラッチ１２３−１〜１２３−ｍは対応するマスク一致線１１９−１〜１１９−ｍに対して、格納されたデータが無効状態“０”の場合には“０”を出力し、格納されたデータが有効状態“１”の場合には対応するマスク一致線１１９−１〜１１９−ｍを開放状態とする。
【００２２】
　マスク一致線１１９−１〜１１９−ｍは、検索動作の終了時に、検索データ１０２と一致した記憶データの中で、マスク情報により検索対象から除外されたビット数が最も少ない記憶データに対応するものだけが有効状態となり、それ以外は無効状態となる。マスク一致線１１９−１〜１１９−ｍは検索動作開始前に図示しない抵抗によりプル・アップされているか、ハイ・レベルにプリ・チャージされることにより、有効状態“１”になっているものとする。
【００２３】
　マスク比較器１２０は、対応するマスク・セル１１２が格納するマスク情報の状態と対応するビット線１０３上の最短マスク情報を比較し、一致しているならば対応するマスク一致線１１９を開放状態にし、不一致ならば対応するマスク一致線１１９に無効状態“０”を出力する。従って、連想メモリ・ワード１１７の中のｎ個の連想メモリ・セル１１８と、１個のラッチ１２３がすべてマスク一致線１１９を開放状態にしているときに、マスク一致線１１９は有効状態“１”となり、それ以外の場合には無効状態“０”となるワイアードＡＮＤ論理接続を構成している。
【００２４】
　つまり、検索動作時には、連想メモリ・ワード１１７が格納しているマスク情報とビット線１０３−１〜１０３−ｎが完全に一致し、かつ、ラッチ１２３に格納されているデータ一致線１０７の状態が有効状態“１”の場合に限り、マスク一致線１１９は有効状態“１”となり、それ以外の場合は無効状態“０”となる。ｎビット・ラッチ１２６は、ラッチ制御信号１２４が有効状態の時に、最短マスク線１２２−１〜１２２−ｎの状態を内部に格納する。また、格納した状態をラッチ出力線１２７−１〜１２７−ｎに出力する。
【００２５】
　ｎビット２入力１出力セレクタ１２８は、ビット線１０３−１〜１０３−ｎに出力するデータを、選択信号１２９の状態により、検索データ１０２−１〜１０２−ｎとラッチ出力線１２７−１〜１２７−ｎの一方から選択する。
【００２６】
　制御回路１３０は、連想メモリ１１６の動作を制御するため、クロック信号１３０に同期して、ラッチ制御信号１２４、選択信号１２９を出力する。
【００２７】
　次に、図１６に従来の連想メモリ・セル１１８の一構成例を示す。ここで、２本のビット線１０３ａ，１０３ｂは図１５に示されている各ビット線に対応するものであるが、図１５においては１０３−ｉで代表して表現している。この２本のビット線を介してメモリ・セルへのデータの読み書きや、検索データ１０２の入力を行う。データを書き込む場合、および検索データの入力を行う場合には、ビット線１０３ｂにはビット線１０３ａの値を反転した値を入力する。 データ・セル１０８は、入出力が相互に接続された反転論理ゲート（Ｇ１０１）３０１、反転論理ゲート（Ｇ１０２）３０２と、反転論理ゲート（Ｇ１０２）３０２の出力をビット線１０３ａに接続しデータ・ワード線１０６がハイ・レベルのときに導通状態となるＭＯＳトランジスタ（Ｔ１０１）３０３と、反転論理ゲート（Ｇ１０１）３０１の出力をビット線１０３ｂに接続しデータ・ワード線１０６がハイ・レベルのときに導通状態となるＭＯＳトランジスタ（Ｔ１０２）３０４とにより構成される一般的なスタティックＳＲＡＭ素子である。
【００２８】
　また、マスク・セル１１２も、入出力が相互に接続された反転論理ゲート（Ｇ１０３）３０９、反転論理ゲート（Ｇ１０４）３１０と、反転論理ゲート（Ｇ１０４）３１０の出力をビット線１０３ａに接続しマスク・ワード線１１１がハイ・レベルのときに導通状態となるＭＯＳトランジスタ（Ｔ１０７）３１１と、反転論理ゲート（Ｇ１０３）３０９の出力をビット線１０３ｂに接続しマスク・ワード線１１１がハイ・レベルのときに導通状態となるＭＯＳトランジスタ（Ｔ１０８）３１２とにより構成される一般的なスタティックＳＲＡＭ素子である。
【００２９】
　比較器１１３はＭＯＳトランジスタ（Ｔ１０３）３０５、ＭＯＳトランジスタ（Ｔ１０４）３０６、ＭＯＳトランジスタ（Ｔ１０５）３０７、ＭＯＳトランジスタ（Ｔ１０６）３０８により構成される。ＭＯＳトランジスタ（Ｔ１０３）３０５とＭＯＳトランジスタ（Ｔ１０４）３０６はビット線１０３ａ，１０３ｂの間に直列に挿入される。ＭＯＳトランジスタ（Ｔ１０３）３０５は、データ・セル１０８内の反転論理ゲート（Ｇ１０１）３０１の出力がハイ・レベルのときに導通状態となる。ＭＯＳトランジスタ（Ｔ１０４）３０６は、データ・セル１０８内の反転論理ゲート（Ｇ１０２）３０２の出力がハイ・レベルのときに導通状態となる。ＭＯＳトランジスタ（Ｔ１０５）３０７とＭＯＳトランジスタ（Ｔ１０６）３０８は、低電位と、データ一致線１０７の間に直列に挿入される。ＭＯＳトランジスタ（Ｔ１０５）３０７は、ＭＯＳトランジスタ（Ｔ１０３）３０５とＭＯＳトランジスタ（Ｔ１０４）３０６の接続点の電位がハイ・レベルの時に導通状態となる。ＭＯＳトランジスタ（Ｔ１０６）３０８は、マスク・セル１１２内の反転論理ゲート（Ｇ１０３）３０９の出力がハイ・レベルの時に導通状態となる。ビット線１０３ａと反転論理ゲート（Ｇ１０１）３０１の出力がともにハイ・レベル、またはビット線１０３ｂと反転論理ゲート（Ｇ１０２）３０２の出力がともにハイ・レベルのときに、ＭＯＳトランジスタ（Ｔ１０３）３０５とＭＯＳトランジスタ（Ｔ１０４）３０６の接続点はハイ・レベルとなり、ＭＯＳトランジスタ（Ｔ１０５）３０７を導通状態とする。
【００３０】
　従って、データ・セル１０８に格納されている記憶データと、ビット線１０３ａ，１０３ｂ上の検索データ１０２が異なる場合にＭＯＳトランジスタ（Ｔ１０５）３０７は導通状態になる。またＭＯＳトランジスタ（Ｔ１０６）３０８はマスク・セル１１２内に格納されているマスク情報が“１”のときには開放状態であり、“０”のときに導通状態となる。データ一致線１０７は、図示しない抵抗により高電位にプル・アップされているか、または、検索動作を開始する前に高電位にプリ・チャージされているものとする。これにより、複数の連想メモリ・セル１１８がデータ一致線１０７にＭＯＳトランジスタ（Ｔ１０６）３０８を介して接続されているとき、１つの連想メモリ・セル１１８でもロウ・レベルを出力しているとデータ一致線１０７はロウ・レベルとなるようなワイアードＡＮＤ接続となる。
【００３１】
　ＭＯＳトランジスタ（Ｔ１０５）３０７、ＭＯＳトランジスタ（Ｔ１０６）３０８がともに導通状態のときに連想メモリ・セル１１８はデータ一致線１０７に無効状態“０”を出力し、それ以外の時にはデータ一致線１０７を開放状態とする。すなわち、マスク情報が“１”の場合にはデータ一致線１０７を必ず開放状態とし、マスク情報が“０”の場合にはビット線１０３ａ，１０３ｂ上の検索データ１０２とデータ・セルに格納されている記憶データが一致するときに開放状態とし、異なる場合には無効状態“０”を出力する。
【００３２】
　次に、論理ゲート１２１と最短マスク線１２２の働きを説明する。最短マスク線１２２は図１５の抵抗１２５によりプル・アップされ検索動作前には有効状態“１”になっている。論理ゲート１２１は、最短マスク線１２２と低電位との間に直列に挿入されたＭＯＳトランジスタ（Ｔ１０９）３１３と、ＭＯＳトランジスタ（Ｔ１１０）３１４で構成されている。ＭＯＳトランジスタ（Ｔ１０９）３１３は、データ一致線１０７が有効状態“１”のときに導通状態となり、無効状態“０”のときには開放状態となる。ＭＯＳトランジスタ（Ｔ１１０）３１４は、マスク・セル１１２内部の反転論理ゲート（Ｇ１０３）３０９の出力がハイ・レベルの場合に導通状態となり、ロウ・レベルの場合には開放状態となる。つまり、マスク・セル１１２に格納されているマスク情報が無効状態“０”のときに導通状態となり、有効状態“１”のときには開放状態となる。これにより論理ゲート１２１は、データ一致線１０７が有効状態“１”かつマスク・セル１１２に格納されたマスク情報が無効状態“０”のときに、最短マスク線１２２に無効状態“０”を出力し、それ以外の場合には開放状態にする。
【００３３】
　次に、マスク比較器１２０とマスク一致線１１９の働きを説明する。マスク一致線１１９は、図示しない抵抗により高電位にプル・アップされているか、または、検索動作を開始する前に高電位にプリ・チャージされているものとする。
【００３４】
　マスク比較器１２０は、ＭＯＳトランジスタ（Ｔ１１１）３１５、ＭＯＳトランジスタ（Ｔ１１２）３１６、ＭＯＳトランジスタ（Ｔ１１３）３１７により構成される。ＭＯＳトランジスタ（Ｔ１１１）３１５とＭＯＳトランジスタ（Ｔ１１２）３１６はビット線１０３ａ，１０３ｂの間に直列に挿入される。ＭＯＳトランジスタ（Ｔ１１１）３１５は、マスク・セル１１２内の反転論理ゲート（Ｇ１０３）３０９の出力がハイ・レベルのときに導通状態となる。ＭＯＳトランジスタ（Ｔ１１２）３１６は、マスク・セル１１２内の反転論理ゲート（Ｇ１０４）３１０の出力がハイ・レベルのときに導通状態となる。ＭＯＳトランジスタ（Ｔ１１３）３１７は、低電位と、マスク一致線１１９の間に挿入される。ＭＯＳトランジスタ（Ｔ１１３）３１７は、ＭＯＳトランジスタ（Ｔ１１１）３１５とＭＯＳトランジスタ（Ｔ１１２）３１６の接続点の電位がハイ・レベルの時に導通状態となる。
【００３５】
　ビット線１０３ａと反転論理ゲート（Ｇ１０３）３０９の出力がともにハイ・レベル、またはビット線１０３ｂと反転論理ゲート（Ｇ１０４）３１０の出力がともにハイ・レベルのときに、ＭＯＳトランジスタ（Ｔ１１１）３１５とＭＯＳトランジスタ（Ｔ１１２）３１６の接続点はハイ・レベルとなり、ＭＯＳトランジスタ（Ｔ１１３）３１７は導通状態になり、その他の場合は開放状態となる。
【００３６】
　従って、マスク・セル１１２に格納されているマスク情報と、ビット線１０３ａ，１０３ｂ上の検索データ１０２が異なる場合にＭＯＳトランジスタ（Ｔ１１３）３１７は導通状態になりマスク一致線１１９に無効状態“０”を出力し、一致する場合にはマスク一致線１１９を開放状態にする。
【００３７】
　これにより、複数の連想メモリ・セル１１８がマスク一致線１１９にＭＯＳトランジスタ（Ｔ１１３）３１７を介して接続されているとき、１つの連想メモリ・セルでもロウ・レベルを出力しているとマスク一致線１１９はロウ・レベルとなり、それ以外の場合はハイ・レベルにするワイアードＡＮＤ接続を構成している。
【００３８】
　次に、上述の従来の連想メモリ１１６を、図１９のルータ４００−３における転送先ネットワーク・アドレスの計算に用いた場合の動作を、図１７を用いて説明する。そのときのタイミングチャートを図１８に示す。
　連想メモリ１１６を８ビット５語の構成と仮定する。従って、各連想メモリ・ワード１１７−１〜１１７−５に格納されている記憶データ、マスク情報は、図２０の連想メモリの場合と全く同一であり、図１９のルータ４００−３のネットワーク・アドレス（３．＊．＊．＊）以外の接続情報を記憶している。つまり、連想メモリ・ワード１１７−１には（１．＊．＊．＊）を実現するため２進数で、記憶データには（０１．００．００．００）を、マスク情報として（００．１１．１１．１１）を格納してある。同様に連想メモリ・ワード１１７−２には（２．＊．＊．＊）を、１１７−３には（１．２．２．＊）を、１１７−４には（１．２．＊．＊）を、１１７−５には（２．１．１．＊）を格納してある。
【００３９】
　以降、検索データ１０２として図１９のＰＣ４０１−１の４進数のネットワーク・アドレス（１．２．２．１）を入力し検索動作を行った場合の動作説明をする。
【００４０】
　まず、図１８のタイミング（１）で、すべてのデータ一致線１０７−１〜１０７−８は、ハイ・レベルにプリ・チャージされ、有効状態“１”になっている。
　次に図１８のタイミング（２）で、制御回路１３１が出力する選択信号１２９により、ｎビット２入力１出力セレクタ１２８は検索データ１０２を選択し、ビット線１０３−１〜１０３−８に出力する。これにより、連想メモリ１１６の連想メモリ・ワード１１７−１に格納されている４進表現の（１．＊．＊．＊）と、連想メモリ・ワード１１７−３に格納されている４進表現の（１．２．２．＊）と、連想メモリ・ワード１１７−４に格納されている４進表現の（１．２．＊．＊）がビット線１０３−１〜１０３−８上のデータと一致する。従って、データ一致線１０７−１、１０７−３および１０７−４の３本が有効状態“１”となり、残りのデータ一致線１０７−２、１０７−５は無効状態“０”となる。
【００４１】
　ここで、最短マスク線１２２−１からは、連想メモリ・ワード１１７−１内の最短マスク線１２２−１に対応するマスク情報“０”と、連想メモリ・ワード１１７−３内の最短マスク線１２２−１に対応するマスク情報“０”と、連想メモリ・ワード１１７−４内の最短マスク線１２２−１に対応するマスク情報“０”の論理積“０”が出力される。最短マスク線１２２−２からは、連想メモリ・ワード１１７−１内の最短マスク線１２２−２に対応するマスク情報“０”と、連想メモリ・ワード１１７−３内の最短マスク線１２２−２に対応するマスク情報“０”と、連想メモリ・ワード１１７−４内の最短マスク線１２２−２に対応するマスク情報“０”の論理積“０”が出力される。以降同様に、最短マスク線１２２−３からは“１”と“０”と“０”の論理積“０”が、最短マスク線１２２−４からは“１”と“０”と“０”の論理積“０”が、最短マスク線１２２−５からは“１”と“０”と“１”の論理積“０”が、最短マスク線１２２−６からは“１”と“０”と“１”の論理積“０”が、最短マスク線１２２−７からは“１”と“１”と“１”の論理積“１”が、最短マスク線１２２−８からは“１”と“１”と“１”の論理積“１”が、それぞれ出力される。従って、最短マスク線１２２−１〜１２２−８には、２進表現で“００００００１１”が出力される。この状態で、制御回路１３１が出力するラッチ制御信号１２４が有効状態になり、ラッチ１２３−１〜１２３−５は対応する一致線１０７−１〜１０７−５の状態を内部に格納し、ｎビット・ラッチ１２６は最短マスク線１２２−１〜１２２−８の状態を内部に格納する。従って、ラッチ１２３−１には“１”が、ラッチ１２３−２には“０”が、ラッチ１２３−３には“１”が、ラッチ１２３−４には“１”が、ラッチ１２３−５には“０”が、それぞれ格納され、ｎビット・ラッチ１２６には２進表現で“００００００１１”が格納される。また、ｎビット・ラッチ１２６は、格納した状態“００００００１１”をラッチ出力線１２７−１〜１２７−８に出力する。
【００４２】
　次に図１８のタイミング（３）で、すべてのマスク一致線１１９−１〜１１９−８はハイ・レベルにプリ・チャージされ、有効状態“１”になっている。
【００４３】
　次に図１８のタイミング（４）で、制御回路１３１が出力する選択信号１２９により、ｎビット２入力１出力セレクタ１２８はラッチ出力線１２７を選択し、その情報“００００００１１”を対応するビット線１０３−１〜１０３−８に出力した後、連想メモリは２回目の検索動作を開始する。２回目の検索動作では、マスク一致線１１９−１〜１１９−８の状態を利用し、データ一致線１０７−１〜１０７−８の状態は無視される。
【００４４】
　ビット線１０３−１〜１０３−８の状態“００００００１１”に対して、連想メモリ・ワード１１７−３と１１７−５が格納するマスク情報が完全に一致し、対応するマスク一致線１１９−３，１１９−５を開放状態にする。他の連想メモリ・ワード１１７−１，１１７−２および１１７−４が格納するマスク情報は一致しないので、対応するマスク一致線１１９−１，１１９−２、および１１９−４に無効状態“０”を出力する。
【００４５】
　また、ラッチ１２３−１は格納した状態が“１”なので対応するマスク一致線１１９−１を解放状態にし、ラッチ１２３−２は格納した状態“０”を対応するマスク一致線１１９−２に出力し、ラッチ１２３−３は格納した状態が“１”なので対応するマスク一致線１１９−３を開放状態にし、ラッチ１２３−４は格納した状態が“１”なので対応するマスク一致線１１９−４を開放状態にし、ラッチ１２３−５は格納した状態“０”を対応するマスク一致線１１９−５に出力する。
【００４６】
　従って、マスク一致線１１９−１は、ラッチ１２３−１が解放状態にしているが、連想メモリ・ワード１１７−１内のマスク比較器１２０−１−１〜１２０−１−８が“０”を出力しているので、無効状態“０”になる。マスク一致線１１９−２は、連想メモリ・ワード１１７−２のマスク比較器１２０−２−１〜１２０−２−８が“０”を出力しラッチ１２３−２も“０”を出力しているので無効状態“０”となる。マスク一致線１１９−３は、連想メモリ・ワード１１７−３のマスク比較器１２０−３−１〜１２０−３−８がすべて開放状態でありラッチ１２３−３も開放状態であるので有効状態“１”を保持する。マスク一致線１１９−４は、ラッチ１２３−４が開放状態にしているが、連想メモリ・ワード１１７−４のマスク比較器１２０−４−１〜１２０−４−８が “０”を出力しているので無効状態“０”となる。マスク一致線１１９−５は、連想メモリ・ワード１１７−５のマスク比較器１２０−５−１〜１２０−５−８が開放状態にしているが、ラッチ１２３−５が“０”を出力しているので、マスク一致線１１９−５は無効状態“０”となる。
【００４７】
　これにより、タイミング（２）の１回目の検索動作で、予め格納されている記憶データがマスク情報を考慮して検索データ１０２と一致し、かつタイミング（４）の２回目の検索動作で、予め格納されているマスク情報が１回目の検索動作の結果得られた最短マスク線１２２−１〜１２２−８の状態と一致するような連想メモリ・ワード１１７−１〜１１７−５に対応するマスク一致線１１９−３のみが、２回目の検索動作終了時に有効状態“１”になる。従って、入力した検索データ１０２と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報の有効状態のビットが最も少ない記憶データに対応するマスク一致線１１９−３のみに有効状態を出力することがわかる。
【発明の開示】
【発明が解決しようとする課題】
【００４８】
　上述した従来の連想メモリ１１６は、１回目の検索動作では、ｍ語の連想メモリ・ワード１１７―１〜１１７−ｍに格納された記憶データと検索データ１０２を比較した結果をｍ本のデータ一致線１０７−１〜１０７−ｍに出力し、２回目の検索動作では、ｍ語の連想メモリ・ワード１１７―１〜１１７−ｍに格納されたマスク情報とラッチ出力線１２７の値を比較した結果をｍ本のマスク一致線１１９−１〜１１９−ｍに出力する。そのため、各連想メモリ・ワード１１７−１〜１１７−ｍの中のｎ個の連想メモリ・セル１１８−１−１〜１１８−ｍ−ｎは、記憶データを比較するための比較器１１３−１−１〜１１３−ｍ−ｎと、マスク情報を比較するためのマスク比較器１２０−１−１〜１２０−ｍ−ｎの２つの比較手段が必要である。
【００４９】
　ここで反転論理ゲートが２個のＭＯＳトランジスタから構成されるとすると、連想メモリ・セル１１８は図１６に示すように２１個のＭＯＳトランジスタから構成される。この中で、データ・セル１０８、マスク・セル１１２はスタティックＲＡＭ素子であるため、これらを構成する各ＭＯＳトランジスタの面積は、一般的に、従来の連想メモリ１１６を製造する際に許される最小面積のＭＯＳトランジスタと等しい。
【００５０】
　ところが、図１５に示すように、各データ一致線１０７−１〜１０７−ｍは１語の連想メモリ・ワード１１７の中のｎ個の比較器１１３とワイアード論理接続をするための配線長が必要であるために配線容量は非常に大きく、その配線容量を駆動するため、比較器１１３を構成するＭＯＳトランジスタの面積は非常に大きくなる。例えば、０．２５μｍ製造プロセスの場合、６４個の比較器を接続するためには１ｍｍほどの配線長が必要となり、この配線長の配線容量はおよそ０．３ｐＦ程度となる。この容量を駆動するためのトランジスタ・サイズは製造プロセスで許される最小面積のＭＯＳトランジスタの１０〜３０倍は必要である。同様に、各マスク一致線１１９−１〜１１９−ｍもｎ個のマスク比較器１２０とワイアード論理接続をするための配線長が必要であり、論理ゲート１２１を構成するＭＯＳトランジスタの面積も、最小面積のＭＯＳトランジスタの１０〜３０倍は必要である。また、図１５に示すように、各最短マスク線１２２−１〜１２２−ｎもｍ個の論理ゲート１２１とワイアード論理接続をするための配線長が必要であり、論理ゲート１２１を構成するＭＯＳトランジスタの面積も、最小面積のＭＯＳトランジスタの１０〜３０倍は必要であることになる。
【００５１】
　従って、比較器１１３，マスク比較器１２０、および論理ゲート１２１を構成するＭＯＳトランジスタの面積を、最小面積のＭＯＳトランジスタの１０倍、一般的なスタティックＲＡＭ素子の面積は最小面積のＭＯＳトランジスタの６倍と仮定すると、図１６から容易に分かるように連想メモリ・セル１１８の面積は、最小面積のＭＯＳトランジスタの１０２倍となる。すなわち、同じチップ面積のスタティックＳＲＡＭの記憶容量と比べると従来の連想メモリ１１６は１７分の１しか格納できないという問題があった。
【００５２】
　また、上述したように、１回目の検索動作の結果が出力されるのはｍ本のデータ一致線１０７−１〜１０７−ｍであり、２回目の検索動作の結果が出力されるのはｍ本のマスク一致線１１９−１〜１１９−ｍである。このため、１回目の検索動作の結果を２回目の検索動作を実行するまで保持する必要がある。ここで、例えば、連想メモリ１１６が１語６４ビットで３２７６８語の構成の場合、ラッチ１２３が１０個のＭＯＳトランジスタから構成されていると仮定すると、３２７６８個のラッチ１２３を構成するためには、およそ３３万個のＭＯＳトランジスタが必要となる。すなわち、記憶データのビット数ｎとは無関係に、ｍ個のラッチ１２３−１〜１２３−ｍの分だけチップ面積が大きくなってしまうという問題があった。
【００５３】
　また、それぞれｍ本あるデータ一致線１０７−１〜１０７−ｍ、マスク一致線１１９−１〜１１９−ｍは、検索動作のたびに最終的に有効状態を出力する一本を除いて、検索前に有効状態にプリ・チャージした電荷をそれぞれ対応するＭＯＳトランジスタを介して放電することになる。従って、１語６４ビットで３２７６８語構成の場合、データ一致線１０７、マスク一致線１１９を合わせて、３２７６８×２−１＝６５５３５本の配線容量を検索動作のたびにプリ・チャージしなければならない。最短マスク線１２２−１〜１２２−ｎはｎ本であり、上述の例では６４本であるので無視できる。すなわち、従来の連想メモリの消費電力は、ほとんど、データ一致線１０７、マスク一致線１１９を検索動作のたびにプリ・チャージするのに要する電力であることがわかる。ここで、前述のように０．２５μｍ製造プロセスの場合、データ一致線１０７、マスク一致線１１９の配線容量をそれぞれ０，３ｐＦと仮定し、電源電圧を２．５Ｖ、クロック信号１３０の周期を２０ｎｓとすると、チップ全体の消費電力は、（０．３ｐＦ×２．５Ｖ）÷２０ｎｓ×２．５Ｖ×６５５３５本＝６．１Ｗと非常に大きい。従って、従来の連想メモリ１１６には、それぞれｍ本あるデータ一致線１０７−１〜１０７−ｍ、マスク一致線１１９−１〜１１９−ｍは、検索動作のたびに最終的に有効状態を出力する一本を除いて、検索前に有効状態にプリ・チャージする必要があるため、消費電力が非常に大きいという問題があった。
【００５４】
　また、上述のように、従来の連想メモリ１１６は記憶容量が小さいために、ルータを用いた場合には、複数個の連想メモリ１１６を使用する必要があった。そのためルータの発熱量が非常に大きくなり、図２０に示すように冷却装置４１４を内蔵する必要があった。また、複数個の連想メモリ１１６の検索結果を比較し最終的な検索結果を求める必要があるため、データ転送速度が低下するという問題があった。
【００５５】
　そこで、本発明の目的は、検索データと一致する記憶データの中で対応するマスク情報の有効状態のビット数が最も少ない記憶データを識別する信号を出力し、なおかつ単位チップ面積あたりの記憶容量の大きい連想メモリを提供することにある。
【００５６】
　更に他の目的として、検索データと一致する記憶データの中で対応するマスク情報の有効状態のビット数が最も少ない記憶データを識別する信号を出力し、なおかつ語数あたりの消費電力の小さい連想メモリを提供すること、冷却装置を必要としないルータを提供すること、及び高速にデータを転送できるネットワークシステムを提供することにある。
【課題を解決するための手段】
【００５７】
　上記目的を達成するために、本発明の連想メモリは、ａ）ｎビット長のｍ個の記憶データを格納するｎ個のデータ・セルと；前記記憶データの各ビットを検索対象から除外するか否かを対応するビットのマスク有効状態、マスク無効状態により設定するマスク情報を格納するｎ個のマスク・セルと；入力データと前記記憶データとをワード単位で比較し、比較結果が一致するワードに対して一致信号を一致線上に出力するｎ個の比較器と；前記一致線上のデータと前記記憶データとをビット列単位で論理演算し、演算結果を一致データ中間論理線上に出力するｎ個の論理ゲートと；を含むｍ個の連想メモリ・ワードと（ｍ，ｎは自然数）、ｂ）前記一致データ中間論理線上に出力されたｎビットの中間一致データを格納するラッチ回路と、ｃ）検索データと前記中間一致データのいずれか一方を前記入力データとして前記連想メモリ・ワードに選択的に供給するセレクタ回路と、ｄ）前記入力データとして前記検索データが選択された場合には前記マスク情報を考慮して比較を行い、前記中間一致データが選択された場合には無視して比較を行うよう前記比較器を制御する制御回路とを具備したことを特徴とする。
【００５８】
　本発明の連想メモリは、前記比較器は、前記検索データを対象とする比較結果と前記中間一致データを対象とする比較結果とを同一の一致線上に出力することを特徴とする。
【００５９】
　本発明の連想メモリは、検索動作に先立って前記一致線及び前記一致データ中間論理線を所定電位にプリ・チャージするプリ・チャージ手段を設けたことを特徴とする。
【００６０】
　本発明の連想メモリは、前記マスク情報の有効状態を"０"、無効状態を"１"とし、前記記憶データの有効状態を"１"、無効状態を"０"とし、前記一致データ中間論理線の有効状態を"１"、無効状態を"０"とし、前記一致線の有効状態を"１"、無効状態を"０"とするよう設定することを特徴とする。
【００６１】
　本発明の連想メモリは、前記比較器が前記一致線の有効状態"１"を真としたワイアードＡＮＤ論理接続を構成することを特徴とする。
【００６２】
　本発明の連想メモリは、前記論理ゲートが前記一致データ中間論理線の有効状態"１"を真としたワイアードＡＮＤ論理接続を構成することを特徴とする。
【００６３】
　本発明の連想メモリは、前記中間一致データとして前記記憶データの有効状態"１"を真とした論理和演算データを得ることを特徴とする。
【００６４】
　本発明の連想メモリは、前記マスク情報の有効状態を"０"、無効状態を"１"とし、前記記憶データの有効状態を"０"、無効状態を"１"とし、前記一致データ中間論理線の有効状態を"１"、無効状態を"０"とし、前記一致線の有効状態を"１"、無効状態を"０"とするよう設定することを特徴とする。
【００６５】
　本発明の連想メモリは、前記比較器が前記一致線の有効状態"１"を真としたワイアードＡＮＤ論理接続を構成することを特徴とする。
【００６６】
　本発明の連想メモリは、前記論理ゲートが前記一致データ中間論理線の有効状態"１"を真としたワイアードＡＮＤ論理接続を構成することを特徴とする。
【００６７】
　本発明の連想メモリは、前記中間一致データとして前記記憶データの有効状態"０"を真とした論理和演算データを得ることを特徴とする。
【００６８】
　また、本発明の連想メモリは、ａ）ｎビット長のｍ個の記憶データを格納するｍ×ｎ個の第１のデータ・セルと；前記記憶データの各ビットを検索対象から除外するか否かを対応するビットのマスク有効状態、マスク無効状態により設定するマスク情報を格納するｍ×ｎ個のマスクセルと；検索データと前記記憶データとを前記マスク情報を考慮してワード単位で比較し、比較結果が一致するワードに対して一致信号を中間一致線上に出力するｍ×ｎ個の第１の比較器と；前記中間一致線上のデータと前記記憶データとをビット列単位で論理演算し、演算結果を一致データ論理和線上に出力するｍ×ｎ個の論理ゲートと；を含む第１のメモリと、ｂ）前記記憶データをワード毎に前記第１のデータ・セルに対応付けて格納するｍ×ｎ個の第２のデータ・セルと；前記一致データ論理和線上のデータと前記第２のデータ・セルに格納された前記記憶データとをワード単位で比較し、比較結果が一致するワードに対して一致信号を一致線上に出力するｍ×ｎ個の第２の比較器と；を具備したことを特徴とする。
【００６９】
　本発明の連想メモリは、検索動作に先立って前記一致線、前記中間一致線及び前記一致データ論理和線を所定電位にプリ・チャージするプリチャージ手段を設けたことを特徴とする。
【００７０】
　本発明の連想メモリは、前記マスク情報の有効状態を"０"、無効状態を"１"とし、前記記憶データの有効状態を"１"、無効状態を"０"とし、前記一致データ論理和線の有効状態を"０"、無効状態を"１"とし、前記中間一致線の有効状態を"１"、無効状態を"０"とし、前記一致線の有効状態を"１"、無効状態を"０"とするよう設定することを特徴とする。
【００７１】
　本発明の連想メモリは、前記第１の比較器が前記中間一致線の有効状態"１"を真としたワイアードＡＮＤ論理接続を構成することを特徴とする。
【００７２】
　本発明の連想メモリは、前記一致データ論理和線上のデータをいったん格納する記憶手段を前記第１のメモリと第２のメモリとの間に介挿することを特徴とする。
【００７３】
　本発明のルータは、目的地ネットワークアドレスを検索データとする連想メモリを内蔵するルータにおいて、前記連想メモリとして請求項１乃至１６に記載の連想メモリを備えたことを特徴とする。
【００７４】
　本発明のネットワークシステムは、前記ルータを介してネットワークに接続された機器間でデータ通信を行うことを特徴とする。
【発明の効果】
【００７５】
　上述のように、本発明の連想メモリは、外部から与えられる検索データを、格納しているマスク情報を考慮して、格納している記憶データと比較する第１の検索動作と、第１の検索動作の結果を利用して計算される値を格納している前記記憶データと比較する第２の検索動作の２回の検索動作を、各ワードごとに同一の比較器を用いて同一の一致線に出力する手段を有しているため、従来の連想メモリと比較して１ビットを格納する単位セルのトランジスタ面積を２５％程度削減できる。つまり単位チップ面積あたりの記憶容量を約３３％程度増大できる。また、面積削減に伴い、配線容量も削減されるため、従来の連想メモリと比較して、動作周波数を３２％程度高くすることができる。
【００７６】
　また、同一の語数で比較した場合、従来の連想メモリの消費電力に対して５０％程度削減できる。
【００７７】
　更に、本発明の連想メモリをネットワーク・アドレス計算を行うルータに組み込めば、従来に比較して消費電力が小さくなるために、冷却装置が不要になりコストが削減できる、等の優れた効果を有する。
【００７８】
　コンピュータ・ネットワーク・システムのルータに適用した場合は、データ転送速度を高速化できる。上述のように動作周波数を向上できるためと、およびチップあたりの記憶容量増加によりルータに内蔵する連想メモリのチップ数を削減することにより複数チップが出力した検索結果の比較処理が不要になるためである。
【発明を実施するための最良の形態】
【００７９】
[第一の実施例の構成]
　次に、本発明の第一の実施の形態について図面を参照して詳細に説明する。図１は、本発明の連想メモリ１の構成例を示すブロック図である。連想メモリ１は、ｎビット２入力１出力セレクタ２３と、ｎビットｍ語の連想メモリ・ワード２−１〜２−ｍと、ｎビット・ラッチ２１と、制御回路３０と、論理ゲート１６−１〜１６−ｎを有しており、各連想メモリ・ワード２−ｊは、ｎ個の連想メモリ・セル７−ｊ−１〜７−ｊ−ｎを備えている。各連想メモリ・ワード２−ｊには、対応するデータ・ワード線３−ｊと、マスク・ワード線６−ｊと、および比較制御信号４が入力のために接続され、対応する一致線５−ｊ、およびｎ本の一致データ中間論理線１４−１〜１４−ｎが出力のために接続され、ｎ本のビット線１３−１〜１３−ｎが入出力のために接続されている。
【００８０】
　各連想メモリ・セル７−ｊ−ｋには、対応するデータ・ワード線３−ｊと、マスク・ワード線６−ｊと、および比較制御信号４が入力のために接続され、対応する一致線５−ｊ、および一致データ中間論理線１４−ｋが出力のために接続され、ビット線１３−ｋが入出力のために接続されている。
【００８１】
　各連想メモリ・セル７−ｊ−ｋは、ビット線１３−ｋを介して外部から入力される記憶データの対応するビット情報を格納するデータ・セル８−ｊ−ｋと、データ・セル８−ｊ−ｋに記憶されたビット情報と外部からビット線１３−ｋを介して入力される情報とを比較する比較器１０−ｊ−ｋと、外部からビット線１３−ｋを介して入力されるマスク情報の対応するビット情報を格納するマスク・セル９−ｊ−ｋと、および論理ゲート１１−ｊ−ｋとを備えている。ここで、マスク・セル９−ｊ−ｋに格納されたビット情報がマスク情報の有効状態の場合には、対応するデータ・セル８−ｊ−ｋには、記憶データの無効状態を格納する。
【００８２】
　なお、本例では、マスク情報の有効状態を“０”、無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”とする。記憶データと同様に、一致データ論理和線１７−１〜１７−ｎの有効状態を“１”、無効状態を“０”とする。一致線５−１〜５−ｍの有効状態を“１”、無効状態を“０”とする。
【００８３】
　データ・ワード線３−１〜３−ｍと、データ・セル８−１−１〜８−ｍ−ｎの動作は、従来の連想メモリのデータ・ワード線１０６−１〜１０６−ｍと、データ・セル１０８−１−１〜１０８−ｍ−ｎの動作と同じである。また、マスク・ワード線６−１〜６−ｍと、マスク・セル９−１−１〜９−ｍ−ｎの動作は、従来の連想メモリのマスク・ワード線１１１−１〜１１１−ｍと、マスク・セル１１２−１−１〜１１２−ｍ−ｎの動作と同じである。
【００８４】
　一致線５は、検索動作の開始前には、ハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。
【００８５】
　比較器１０は、対応するビット線１３と、それに同一の連想メモリ・セル７−１−１〜７−ｍ−ｎの中のデータ・セル８に格納されている記憶データと、マスク・セル９に格納されているマスク情報と、および比較制御信号４を入力とする。比較器１０は、比較制御信号４が無効状態“０”かつマスク情報が有効状態ならば、対応する一致線５を解放状態にし、それ以外の場合には、ビット線１３の値と記憶データが一致するならば対応する一致線５を開放状態にし、一致しないならば無効状態“０”を出力する。連想メモリ・ワード２の中のｎ個の比較器１０がすべて一致線５を開放状態にしているときに、一致線５は有効状態“１”となり、それ以外の場合には無効状態“０”となる、一致線５の有効状態“１”を真としたワイアードＡＮＤ論理接続を構成している。つまり、検索動作時には、比較制御信号４が無効状態“０”かつマスク情報が有効状態“０”のために比較対象から除外されたビットを除いて、連想メモリ・ワード２が格納している記憶データとビット線１３−１〜１３−ｎが完全に一致する場合に限り、一致線５は有効状態“１”となり、それ以外の場合は無効状態“０”となる。もちろん同様の動作となるように通常の論理ゲートを用いて構成してもかまわない。
【００８６】
　論理ゲート１１−１−１〜１１−ｍ−ｎは、同一の連想メモリ・ワード２−１〜２−ｍの中の一致線５−１〜５−ｍが有効状態“１”かつ、同一の連想メモリ・セル７−１−１〜７−ｍ−ｎの中のデータ・セル８−１−１〜８−ｍ−ｎに格納された記憶データが有効状態のときに、対応する一致データ中間論理線１４−１〜１４−ｎに“０”を出力し、それ以外の場合には開放状態にする。ここで本例では記憶データの有効状態が“１”であるので、データ・セル８−１−１〜８−ｍ−ｎに格納された記憶データが“１”かつ一致線５−１〜５−ｍが“１”のときに、対応する一致データ中間論理線１４−１〜１４−ｎに“０”を出力し、それ以外の場合には解放状態を出力する。
【００８７】
　各一致データ中間論理線１４−１〜１４−ｎは、抵抗１５−１〜１５−ｎによりプル・アップされており、対応するｍ個の論理ゲート１１−１−１〜１１−ｍ−ｎとワイアード論理接続を構成している。従って、接続されているｍ個の論理ゲート１１がすべて一致データ中間論理線１４を開放状態にしているときに、一致データ中間論理線１４は“１”となり、それ以外の場合には“０”となる。つまり“１”を真としたワイアードＡＮＤ接続となっている。もちろん同様の動作となるように通常の論理ゲートを用いて構成してもかまわない。
【００８８】
　論理ゲート１６−１〜１６−ｎは、対応する一致データ中間論理線１４−１〜１４−ｎの論理状態を反転し、一致データ論理和線１７−１〜１７−ｎとして出力する。
【００８９】
　従って、一致データ論理和線１７−ｋには、ｍ個の論理ゲート１１―１−ｋ〜１１−ｍ−ｋと一致データ中間論理線１４―ｋ、抵抗１５−ｋ、および論理ゲート１６−ｋにより、検索動作時に有効状態“１”となっている一致線５―１〜５−ｍを有するすべての連想メモリ・セル７―１−ｋ〜７−ｍ−ｋの中のデータ・セル８−１−ｋ〜８−ｍ−ｋに格納されている記憶データ同士を、記憶データの有効状態を真とした論理和演算した結果が得られることになる。本例では、記憶データの有効状態“１”を真とした論理和演算した結果が得られる。もちろん同様の動作となるように通常の論理ゲートを用いて構成してもかまわない。これらの動作により、一致データ論理和線１７−１〜１７−ｎには、検索動作時に検索データ１２と一致した記憶データの中で、最も無効状態“０”のビット数が少ない記憶データと同じ値が出力されることになる。ｎビット・ラッチ２１は、ラッチ制御信号２２が有効状態の時に、一致データ論理和線１７−１〜１７−ｎの状態を内部に格納する。また、格納した状態をラッチ出力線２０−１〜２０−ｎに出力する。
【００９０】
　ｎビット２入力１出力セレクタ２３は、ビット線１３−１〜１３−ｎに出力するデータを、選択信号２４の状態により、検索データ１２−１〜１２−ｎとラッチ出力線２０−１〜２０−ｎの一方から選択する。
【００９１】
　制御回路３０は、連想メモリ１の動作を制御するため、クロック信号３１に同期して、ラッチ制御信号２２、選択信号２４、および比較制御信号４を出力する。
【００９２】
[第一の実施例の構成詳細]
　次に、上述の連想メモリ・セル７の構成例を図２を用いて説明する。図１６に示す従来の連想メモリ・セル１１８と比較すれば分かるように、本発明の連想メモリ・セル７の、ビット線１３ａ、１３ｂ、データ・ワード線３、データ・セル８、マスク・ワード線６、およびマスク・セル９は、従来の連想メモリ・セル１１８と同様である。
【００９３】
　従って従来と異なる部分のみの説明を行う。なお、従来の連想メモリ・セル１１８が有していたマスク比較器１２０およびマスク一致線１１９は、本発明の連想メモリ・セルでは不要である。
【００９４】
　比較器１０はＭＯＳトランジスタ（Ｔ３）２０５、ＭＯＳトランジスタ（Ｔ４）２０６、ＭＯＳトランジスタ（Ｔ５）２０７、ＭＯＳトランジスタ（Ｔ６）２０８、およびＭＯＳトランジスタ（Ｔ７）２０９により構成される。ＭＯＳトランジスタ（Ｔ３）２０５とＭＯＳトランジスタ（Ｔ４）２０６はビット線１３ａ，１３ｂの間に直列に挿入される。ＭＯＳトランジスタ（Ｔ３）２０５は、データ・セル８内の反転論理ゲート（Ｇ１）２０１の出力がハイ・レベルのときに導通状態となる。ＭＯＳトランジスタ（Ｔ４）２０６は、データ・セル８内の反転論理ゲート（Ｇ２）２０２の出力がハイ・レベルのときに導通状態となる。ＭＯＳトランジスタ（Ｔ６）２０８とＭＯＳトランジスタ（Ｔ７）２０９は並列接続され、この並列接続された２つのＭＯＳトランジスタは、ＭＯＳトランジスタ（Ｔ５）２０７とともに、一致線５と低電位の間に直列に挿入される。ＭＯＳトランジスタ（Ｔ６）２０８は、マスク・セル９内の反転論理ゲート（Ｇ４）２１１の出力がハイ・レベルの時に導通状態となる。ＭＯＳトランジスタ（Ｔ７）２０９は、比較制御信号４が有効状態“１”の時に導通状態となる。
【００９５】
　ＭＯＳトランジスタ（Ｔ５）２０７は、ＭＯＳトランジスタ（Ｔ３）２０５とＭＯＳトランジスタ（Ｔ４）２０６の接続点の電位がハイ・レベルの時に導通状態となる。ビット線１３ａと反転論理ゲート（Ｇ１）２０１の出力がともにハイ・レベル、またはビット線１３ｂと反転論理ゲート（Ｇ２）２０２の出力がともにハイ・レベルのときに、ＭＯＳトランジスタ（Ｔ３）２０５とＭＯＳトランジスタ（Ｔ４）２０６の接続点はハイ・レベルとなり、ＭＯＳトランジスタ（Ｔ５）２０７を導通状態とする。
【００９６】
　従って、データ・セル８に格納されている記憶データと、ビット線１３ａ，１３ｂ上の検索データ１２が異なる場合にＭＯＳトランジスタ（Ｔ５）２０７は導通状態になる。またＭＯＳトランジスタ（Ｔ６）２０８はマスク・セル９内に格納されているマスク情報が“０”のときには開放状態であり、“１”のときに導通状態となる。一致線５は検索動作を開始する前に高電位にプリ・チャージされているものとする。これにより、複数の連想メモリ・セル７が一致線５にＭＯＳトランジスタ（Ｔ６）２０８、およびＭＯＳトランジスタ（Ｔ７）２０９を介して接続されているとき、１つの連想メモリ・セル７でもロウ・レベルを出力していると一致線５はロウ・レベルとなるようなワイアードＡＮＤ接続となる。
【００９７】
　ＭＯＳトランジスタ（Ｔ５）２０７が導通状態のときに、並列接続されたＭＯＳトランジスタ（Ｔ６）２０８、ＭＯＳトランジスタ（Ｔ７）２０９のどちらか１つでも導通状態の場合に連想メモリ・セル７は一致線５に無効状態“０”を出力し、それ以外の時には一致線５を開放状態とする。すなわち、マスク情報が有効状態“０”かつ比較制御信号４が無効状態“０”の場合には検索データ１２と記憶データの比較結果によらず一致線５を開放状態とし、それ以外の場合にはビット線１３ａ，１３ｂ上の検索データ１２とデータ・セル８に格納されている記憶データが一致するときに開放状態とし、異なる場合には無効状態“０”を出力する。
【００９８】
　次に、論理ゲート１１と一致データ中間論理線１４の働きを説明する。一致データ中間論理線１４は図１の抵抗１５によりプル・アップされ検索動作前には“１”になっている。論理ゲート１１は、一致データ中間論理線１４と低電位との間に直列に挿入されたＭＯＳトランジスタ（Ｔ１０）２１４と、ＭＯＳトランジスタ（Ｔ１１）２１５で構成されている。ＭＯＳトランジスタ（Ｔ１０）２１４は、一致線５が有効状態“１”のときに導通状態となり、無効状態“０”のときには開放状態となる。ＭＯＳトランジスタ（Ｔ１１）２１５は、データ・セル８内部の反転論理ゲート（Ｇ２）２０２の出力がハイ・レベルの場合に導通状態となり、ロウ・レベルの場合には開放状態となる。つまり、データ・セル８に格納されている記憶データが有効状態“１”のときに導通状態となり、無効状態“０”のときには開放状態となる。これにより論理ゲート１１は、一致線５が有効状態“１”かつデータ・セル８に格納された記憶データが有効状態“１”のときに、一致データ中間論理線１４に“０”を出力し、それ以外の場合には開放状態にする。
【００９９】
[第一の実施例の動作]
　次に、上述の連想メモリ１を、図１９のルータ４００−３における転送先ネットワーク・アドレスの計算に用いた場合の動作を、図３を用いて説明する。そのときのタイミングチャートを図４に示す。
　連想メモリ１を８ビット５語の構成と仮定し、各連想メモリ・ワード２−１〜２−５に格納されている記憶データ、マスク情報には、図１９のルータ４００−３のネットワーク・アドレス（３．＊．＊．＊）以外の接続情報を記憶しているものとする。このとき、接続情報の中のドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態“０”、マスク情報の該当ビットをマスク・データの有効状態“０”とすることで表現される。
【０１００】
　つまり、連想メモリ・ワード２−１には（１．＊．＊．＊）を実現するため２進数で、記憶データには（０１．００．００．００）を、マスク情報として（１１．００．００．００）を格納してある。同様に連想メモリ・ワード２−２には（２．＊．＊．＊）を実現するため２進数で、記憶データには（１０．００．００．００）を、マスク情報として（１１．００．００．００）を格納してある。連想メモリ・ワード２−３には（１．２．２．＊）を実現するため２進数で、記憶データには（０１．１０．１０．００）を、マスク情報として（１１．１１．１１．００）を格納してある。連想メモリ・ワード２−４には（１．２．＊．＊）を実現するため２進数で、記憶データには（０１．１０．００．００）を、マスク情報として（１１．１１．００．００）を格納してある。連想メモリ・ワード２−５には（２．１．１．＊）を実現するため２進数で、記憶データには（１０．０１．０１．００）を、マスク情報として（１１．１１．１１．００）を格納してある。
【０１０１】
　以降、検索データ１２として図１９のＰＣ４０１−１の４進数のネットワーク・アドレス（１．２．２．１）を入力し検索動作を行った場合の動作説明をする。
【０１０２】
　まず、図４のタイミング（１）で、すべての一致線５−１〜５−５は、ハイ・レベルにプリ・チャージされ、有効状態“１”になっている。
　次に図４のタイミング（２）で、制御回路３０が出力する選択信号２４により、ｎビット２入力１出力セレクタ２３は検索データ１２を選択し、ビット線１３−１〜１３−８に出力する。また、制御回路３０は比較制御信号４に無効状態“０”を出力し、各連想メモリ・セル７−１−１〜７−ｍ−ｎにおいて、その中の記憶データと検索データ１２の対応ビットの比較結果によらずに、その中のマスク情報が有効状態“０”の場合には対応する一致線５を解放状態とすることを許可する。つまりドント・ケア“＊”も考慮して比較する。これにより、連想メモリ１の連想メモリ・ワード２−１に格納されている４進表現の（１．＊．＊．＊）と、連想メモリ・ワード２−３に格納されている４進表現の（１．２．２．＊）と、連想メモリ・ワード２−４に格納されている４進表現の（１．２．＊．＊）がビット線１３−１〜１３−８上の検索データ１２と一致する。従って、一致線５−１、５−３および５−４の３本が有効状態“１”となり、残りの一致線５−２、５−５は無効状態“０”となる。
【０１０３】
　ここで、一致データ論理和線１７−１からは、連想メモリ・ワード２−１内の一致データ中間論理線１４−１に対応する記憶データ“０”と、連想メモリ・ワード２−３内の一致データ中間論理線１４−１に対応する記憶データ“０”と、連想メモリ・ワード２−４内の一致データ中間論理線１４−１に対応する記憶データ“０”に対しての“１”を真とした論理和結果“０”が出力される。一致データ論理和線１７−２からは、連想メモリ・ワード２−１内の一致データ中間論理線１４−２に対応する記憶データ“１”と、連想メモリ・ワード２−３内の一致データ中間論理線１４−２に対応する記憶データ“１”と、連想メモリ・ワード２−４内の一致データ中間論理線１４−２に対応する記憶データ“１” に対しての“１”を真とした論理和結果“１”が出力される。以降同様に、一致データ論理和線１７−３からは“０”と“１”と“１” に対しての“１”を真とした論理和結果“１”が、一致データ論理和線１７−４からは“０”と“０”と“０” に対しての“１”を真とした論理和結果“０”が、一致データ論理和線１７−５からは“０”と“１”と“０” に対しての“１”を真とした論理和結果“１”が、一致データ論理和線１７−６からは“０”と“０”と“０” に対しての“１”を真とした論理和結果“０”が、一致データ論理和線１７−７からは“０”と“０”と“０” に対しての“１”を真とした論理和結果“０”が、一致データ論理和線１７−８からは“０”と“０”と“０” に対しての“１”を真とした論理和結果“０”が、それぞれ出力される。従って、一致データ論理和線１７−１〜１７−８には、２進表現で“０１１０１０００”が出力されることになる。
【０１０４】
　この状態で、制御回路３０が出力するラッチ制御信号２２が有効状態になり、ｎビット・ラッチ２１は一致データ論理和線１７−１〜１７−８の状態を内部に格納する。従って、ｎビット・ラッチ２１は２進表現で“０１１０１０００”を格納し、その値をラッチ出力線２０−１〜２０−８に出力する。
【０１０５】
　図４のタイミング（３）は、本例では、タイミング（２）とタイミング（４）双方のクロック信号３１の状態を同一にするために挿入されており、連想メモリ１は、タイミング（２）の最終状態を保持し続ける。タイミング（２）とタイミング（４）双方のクロック信号３１の状態を同一でなくても制御回路３０が動作する場合には、タイミング（３）を挿入する必要ない。
【０１０６】
　次に図４のタイミング（４）で、制御回路３０が出力する選択信号２４により、ｎビット２入力１出力セレクタ２３はラッチ出力線２０を選択し、その情報“０１１０１０００”を対応するビット線１３−１〜１３−８に出力した後、連想メモリ１は２回目の検索動作を開始する。２回目の検索動作では、一致線５−１〜５−５に保持されている、タイミング（２）で実行した１回目の検索動作の結果を利用する。本例では、一致線５−１、５−３および５−４の３本が有効状態“１”を保持しており、データ一致線５−２、５−５は無効状態“０”を保持している。１回目の検索動作の結果を記憶手段に格納し、タイミング（４）での検索時にその格納状態を利用してもよいことは、言うまでもない。また、制御回路３０は比較制御信号４に有効状態“１”を出力する。これにより、各連想メモリ・セル７−１−１〜７−ｍ−ｎは、その中のマスク情報によらず、その中の記憶データと対応するビット線１３の比較結果が不一致の場合には、一致線５に無効状態“０”を出力する。つまりドント・ケア“＊”を考慮せず、各連想メモリ・ワード２−１〜２−５に格納されている記憶データ自体とビット線１３―１〜１３−８の状態“０１１０１０００”とを比較し、不一致の場合には対応する一致線５−１〜５−５に無効状態“０”を出力することになる。
【０１０７】
　本例では、ビット線１３−１〜１３−８の状態“０１１０１０００”に対して、連想メモリ・ワード２−３が格納する記憶データが完全に一致し、対応する一致線５−３を開放状態にする。他の連想メモリ・ワード２−１，２−２、２−４、および２−５が格納する記憶データは一致しないので、対応する一致線５−１，５−２、５−４、および５−５に無効状態“０”を出力する。従って、２回目の検索動作開始前に有効状態“１”を保持していた一致線５−１，５−３，５−４の３本の中で、２回目の検索動作後も有効状態“１”を保持し続けるのは、一致線５−３のみとなる。
【０１０８】
　従って、入力した検索データ１２と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報の有効状態のビットが最も少ない記憶データに対応する一致線５−３のみに有効状態を出力することがわかる。
【０１０９】
　上述のように、本発明の第一の実施例の連想メモリ１は、１回目の検索動作、２回目の検索動作ともに、比較器１０−１−１〜１０−ｍ−ｎで実行し、結果を一致線５−１〜５−ｍに出力する。従って図２に示すように連想メモリ・セル７は、図１６に示す連想メモリ・セル１１８と比較して、マスク・比較器が削除することができる。ここで、従って、比較器１０，および論理ゲート１１を構成するＭＯＳトランジスタの面積を、最小面積のＭＯＳトランジスタの１０倍、一般的なスタティックＲＡＭ素子の面積は最小面積のＭＯＳトランジスタの６倍と仮定すると、図２から容易に分かるように連想メモリ・セル７の面積は、最小面積のＭＯＳトランジスタの８２倍となる。従来の連想メモリ・セル１１８の面積は前述のように最小面積のＭＯＳトランジスタの１０２倍であったから、本発明の連想メモリ・セル７は、従来の連想メモリ・セル１１８に比べて２０％程度面積を削減できることになる。
【０１１０】
　また、１回目の検索動作の結果も、２回目の検索動作の結果も同一の一致線５−１〜５−ｍに出力されるため、従来の連想メモリ１１６で必要であった１回目の検索動作の結果を２回目の検索動作を実行するまで保持するためのラッチ１２３−１〜１２３−ｍが不要である。従って、従来の連想メモリ１１６に比べて、さらに面積削減が可能である。例えば、１語６４ビットで３２７６８語の構成の場合、ラッチ１２３が１０個のＭＯＳトランジスタから構成されていると仮定すると、およそ３３万個のＭＯＳトランジスタ分の面積が削減できることになる。従って、上記の連想メモリ・セルの面積削減分と合わせると、チップ全体で２５％程度の面積削減が可能となる。
【０１１１】
　また、１回目の検索動作の結果も、２回目の検索動作の結果も同一の一致線５−１〜５−ｍに出力されるため、検索動作のごとのプリ・チャージもｍ本の一致線５−１〜５−ｍとｎ本の一致データ中間論理線１４−１〜１４−ｎのみでよい。つまり検索動作のたび（ｍ＋ｎ）本プリ・チャージすればよい。従来の連想メモリ１１６では、前述のとおり、ｍ本のデータ一致線１０７−１〜１０７−ｍ、ｍ本のマスク一致線１１９−１〜１１９−ｍ、およびｎ本の最短マスク線１２２−１〜１２２−ｎのプリ・チャージが必要であり、従って、検索動作のたびに（２ｍ＋ｎ）本プリ・チャージすることになる。ここで１語６４ビットで３２７６８語の構成の場合、チップ全体でプリ・チャージする配線の本数は、従来の連想メモリ１１６では６５６００本、本発明の連想メモリ１では３２８３２本となり、従って、従来の連想メモリ１１６と比較して消費電力が５０％程度削減できることになる。
【０１１２】
　また、連想メモリ・セル７の面積削減に伴い、ビット線１３−１〜１３−ｎ、一致データ中間論理線１４−１〜１４−ｎの配線長も短縮される。連想メモリ・セル７を構成するＭＯＳトランジスタの大きさが前述の例のとおりだとすると、図２から容易に分かるように、従来の連想メモリ・セル１１８に比べて２５％程度配線長が短縮されることになる。配線容量がその分減少するので、クロック信号３１の周波数を３２％程度高くすることができるという効果もある。
【０１１３】
[第二の実施例の構成]
　次に、本発明の第二の実施の形態について図５および図６を参照して詳細に説明する。本例の連想メモリ２８は、第一の実施の形態の連想メモリ１と比較すると、記憶データの有効状態を“０”、無効状態を“１”としていることと、論理ゲート１６−１〜１６−ｎが論理ゲート２７−１〜２７−ｎに変更されていることと、および連想メモリ・ワード２−１〜２−ｍの中の連想メモリ・セル７−１−１〜７−ｍ−ｎが連想メモリ・セル２６−１−１〜２６−ｍ−ｎに変更されていることのみが異なり、他の部分は同様に構成される。連想メモリ・セル２６−１−１〜２６−ｍ−ｎは、第一の実施の形態の連想メモリ・セル７−１−１〜７−ｍ−ｎと比較すると、論理ゲート１１−１−１〜１１−ｍ−ｎが論理ゲート２５−１−１〜２５−ｍ−ｎに変更されていることのみが異なり、他の部分は同様に構成される。従って、第一の実施例と異なる点についてのみ説明を行う。なお、第一の実施例と同様に、マスク・セル９−ｊ−ｋに格納されたビット情報がマスク情報の有効状態の場合には、対応するデータ・セル８−ｊ−ｋには、記憶データの無効状態を格納する。
【０１１４】
　論理ゲート２５−１−１〜２５−ｍ−ｎは、第一の実施の形態の論理ゲート１１−１−１〜１１−ｍ−ｎと同様に、同一の連想メモリ・ワード２−１〜２−ｍの中の一致線５−１〜５−ｍが有効状態“１”かつ、同一の連想メモリ・セル７−１−１〜７−ｍ−ｎの中のデータ・セル８−１−１〜８−ｍ−ｎに格納された記憶データが有効状態のときに、対応する一致データ中間論理線１４−１〜１４−ｎに“０”を出力し、それ以外の場合には開放状態にする。ここで本例では記憶データの有効状態が“０”であるので、データ・セル８−１−１に格納された記憶データが“０”かつ一致線５−１〜５−ｍが“１”のときに、対応する一致データ中間論理線１４−１〜１４−ｎに“０”を出力し、それ以外の場合には解放状態を出力する。
【０１１５】
　各一致データ中間論理線１４−１〜１４−ｎは、第一の実施の形態と同様に抵抗１５−１〜１５−ｎによりプル・アップされており、対応するｍ個の論理ゲート２５−１−１〜２５−ｍ−ｎとワイアード論理接続を構成している。従って、接続されているｍ個の論理ゲート２５がすべて一致データ中間論理線１４を開放状態にしているときに、一致データ中間論理線１４は“１”となり、それ以外の場合には“０”となる。つまり“１”を真としたワイアードＡＮＤ接続となっている。もちろん同様の動作となるように通常の論理ゲートを用いて構成してもかまわない。
【０１１６】
　論理ゲート２７−１〜２７−ｎは、対応する一致データ中間論理線１４−１〜１４−ｎの論理状態をそのまま一致データ論理和線１７−１〜１７−ｎとして出力する。論理ゲート２７−１〜２７−ｎは、論理的には意味はなく、ワイアードＡＮＤ論理により生成された信号を整形するために挿入されている。クロック信号３１による動作周波数が十分に低ければ論理ゲート２７−１〜２７−ｎは不要であることはいうまでもない。
【０１１７】
　従って、一致データ論理和線１７−ｋには、ｍ個の論理ゲート２５―１−ｋ〜２５−ｍ−ｋと一致データ中間論理線１４―ｋ、抵抗１５−ｋ、および論理ゲート２７−ｋにより、検索動作時に有効状態“１”となっている一致線５―１〜５−ｍを有するすべての連想メモリ・セル２６―１−ｋ〜２６−ｍ−ｋの中のデータ・セル８−１−１〜８−ｍ−ｋに格納されている記憶データ同士を、記憶データの有効状態を真とした論理和演算した結果が得られることになる。本例では、記憶データの有効状態“０”を真とした論理和演算した結果が得られる。もちろん同様の動作となるように通常の論理ゲートを用いて構成してもかまわない。これらの動作により、一致データ論理和線１７−１〜１７−ｎには、検索動作時に検索データ１２と一致した記憶データの中で、最も無効状態“１”のビット数が少ない記憶データと同じ値が出力されることになる。
【０１１８】
[第二の実施例の動作]
　次に、上述の連想メモリ２８を、図１９のルータ４００−３における転送先ネットワーク・アドレスの計算に用いた場合の動作を、図７を用いて説明する。
　連想メモリ２８を８ビット５語の構成と仮定し、各連想メモリ・ワード２−１〜２−５に格納されている記憶データ、マスク情報には、図１９のルータ４００−３のネットワーク・アドレス（３．＊．＊．＊）以外の接続情報を記憶しているものとする。このとき、接続情報の中のドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態“１”、マスク情報の該当ビットをマスク情報の有効状態“０”とすることで表現される。
【０１１９】
　つまり、連想メモリ・ワード２−１には（１．＊．＊．＊）を実現するため２進数で、記憶データには（０１．１１．１１．１１）を、マスク情報として（１１．００．００．００）を格納してある。同様に連想メモリ・ワード２−２には（２．＊．＊．＊）を実現するため２進数で、記憶データには（１０．１１．１１．１１）を、マスク情報として（１１．００．００．００）を格納してある。連想メモリ・ワード２−３には（１．２．２．＊）を実現するため２進数で、記憶データには（０１．１０．１０．１１）を、マスク情報として（１１．１１．１１．００）を格納してある。連想メモリ・ワード２−４には（１．２．＊．＊）を実現するため２進数で、記憶データには（０１．１０．１１．１１）を、マスク情報として（１１．１１．００．００）を格納してある。連想メモリ・ワード２−５には（２．１．１．＊）を実現するため２進数で、記憶データには（１０．０１．０１．１１）を、マスク情報として（１１．１１．１１．００）を格納してある。
【０１２０】
　以降、検索データ１２として図１９のＰＣ４０１−１の４進数のネットワーク・アドレス（１．２．２．１）を入力し検索動作を行った場合の動作を、第一の実施の形態と異なる点についてのみ説明する。
　１回目の検索動作においては、第一の実施の形態と同様に、連想メモリ・ワード２−１、２−３，および２−４が一致する。従って、一致線５−１、５−３および５−４の３本が有効状態“１”となり、残りの一致線５−２、５−５は無効状態“０”となる。
【０１２１】
　ここで、一致データ論理和線１７−１からは、連想メモリ・ワード２−１内の一致データ中間論理線１４−１に対応する記憶データ“０”と、連想メモリ・ワード２−３内の一致データ中間論理線１４−１に対応する記憶データ“０”と、連想メモリ・ワード２−４内の一致データ中間論理線１４−１に対応する記憶データ“０”に対しての前述のとおり“０”を真とした論理和結果“０”が出力される。一致データ論理和線１７−２からは、連想メモリ・ワード２−１内の一致データ中間論理線１４−２に対応する記憶データ“１”と、連想メモリ・ワード２−３内の一致データ中間論理線１４−２に対応する記憶データ“１”と、連想メモリ・ワード２−４内の一致データ中間論理線１４−２に対応する記憶データ“１”に対しての“０”を真とした論理和結果“１”が出力される。以降同様に、一致データ論理和線１７−３からは“１”と“１”と“１”に対しての“０”を真とした論理和結果“１”が、一致データ論理和線１７−４からは“１”と“０”と“０”に対しての“０”を真とした論理和結果“０”が、一致データ論理和線１７−５からは“１”と“１”と“１”のに対しての“０”を真とした論理和結果“１”が、一致データ論理和線１７−６からは“１”と“０”と“１”
に対しての“０”を真とした論理和結果“０”が、一致データ論理和線１７−７からは“１”と“１”と“１” に対しての“０”を真とした論理和結果“１”が、一致データ論理和線１７−８からは“１”と“１”と“１” に対しての“０”を真とした論理和結果“１”が、それぞれ出力される。従って、一致データ論理和線１７−１〜１７−８には、２進表現で“０１１０１０１１”が出力され、ｎビット・ラッチ２１に格納される。
【０１２２】
　２回目の検索動作においては、ビット線１３−１〜１３−８の状態“０１１０１０１１”に対して、連想メモリ・ワード２−３が格納する記憶データが完全に一致し、対応する一致線５−３を開放状態にする。他の連想メモリ・ワード２−１，２−２、２−４、および２−５が格納する記憶データは一致しないので、対応する一致線５−１，５−２、５−４、および５−５に無効状態“０”を出力する。従って、２回目の検索動作開始前に有効状態“１”を保持していた一致線５−１，５−３，５−４の３本の中で、２回目の検索動作後も有効状態“１”を保持し続けるのは、一致線５−３のみとなる。
【０１２３】
　従って、入力した検索データ１２と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報の有効状態のビットが最も少ない記憶データに対応する一致線５−３のみに有効状態を出力することがわかる。
【０１２４】
　第一の実施の形態、第二の実施の形態ともにマスク情報の有効状態を“０”として説明したが、マスク情報の有効状態を“１”とした場合においても、前述と同様に、各連想メモリ・ワードにおいて、マスク有効状態となっているマスク情報のビットに対応する記憶データのビットに記憶データの無効状態を格納しておき、第１回目の検索動作時に有効状態となっている一致線を有する連想メモリ・ワードの中の記憶データのすべてに対して、記憶データの有効状態を真とした論理和演算を行った結果を２回目の検索動作時のビット線の状態とするように構成すれば、本発明の連想メモリを実現できることは言うまでもない。
【０１２５】
　また、第一の実施の形態、第二の実施の形態ともに各連想メモリ・ワードにおいて、マスク有効状態となっているマスク情報のビットに対応する記憶データのビットに記憶データの無効状態を格納したが、比較制御信号４が有効状態となる２回目の検索動作時には、比較器１０においてマスク有効状態なっているマスク情報のビットに対応する記憶データには記憶データの無効状態が記憶されているものとみなして比較を行っても同じ結果が得られることは容易に分かる。
【０１２６】
[第三の実施例の構成]
　次に、本発明の第三の実施の形態について図面を参照して詳細に説明する。図８は本発明の第三の実施の形態の連想メモリ４２の構成を示すブロック図である。
【０１２７】
　連想メモリ４２は、ｎビットｍ語の一致データ論理和信号出力機能付連想メモリ３３と、ｎビットｍ語のマスク機能無し連想メモリ１０１とから構成される。本例では、一致データ論理和信号出力機能付連想メモリ３３が１回目の検索動作を行い一致データ論理和信号３８を計算し、得られた一致データ論理和信号３８を用いてマスク機能無し連想メモリ１０１が２回目の検索動作を行い一致線５−１〜５−ｍを出力する。
【０１２８】
　ｎビットｍ語の一致データ論理和信号出力機能付連想メモリ３３は、ｎ本のビット線１３−１〜１３−ｎに入力された検索データ１２と、ｍ個の連想メモリ・ワード４３−１〜４３−ｍごとに内部のデータ・セル８−１−１〜８−ｍ−ｎに格納されている記憶データおよびマスク・セル９−１−１〜９−ｍ−ｎに格納されたマスク情報を用いて、計算された一致データ論理和信号３８をｎ本の一致データ論理和線１７−１〜１７−ｎに出力する。一致データ論理和信号３８は、第一の実施の形態の連想メモリ１と同様な操作により計算される。ここで、マスク・セル９−ｊ−ｋに格納されたビット情報がマスク情報の有効状態の場合には、対応するデータ・セル８−ｊ−ｋには記憶データの無効状態を格納する。
【０１２９】
　マスク機能無し連想メモリ１０１は、ビット線１０３−１〜１０３−ｎから入力された一致データ論理和信号３８を、ｍ個の連想メモリ・ワード１０４−１〜１０４−ｍごとに内部のデータ・セル１０５−１−１〜１０５−ｍ−ｎに格納している第二の記憶データと一致しているかを比較した結果、一致した連想メモリ・ワード１０４に対応するデータ一致線１０７−１〜１０７−ｍに有効状態“１”を出力する。データ一致線１０７−１〜１０７−ｍの状態は、一致線５−１〜５−ｍとして連想メモリ４２から出力される。ここで、一致データ論理和信号出力機能付連想メモリ３３のマスク・セル９−ｊ−ｋに格納されたビット情報がマスク情報の有効状態の場合には、対応するデータ・セル１０５−ｊ−ｋには、記憶データの無効状態を格納する。
【０１３０】
　なお、本例では、マスク情報の有効状態を“０”、無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”とする。記憶データと同様に、一致データ論理和線１７−１〜１７−ｎの有効状態を“１”、無効状態を“０”とする。一致線５−１〜５−ｍの有効状態を“１”、無効状態を“０”とする。
【０１３１】
　ｎビットｍ語の一致データ論理和信号出力機能付連想メモリ３３の構成例を図９に示す。一致データ論理和信号出力機能付連想メモリ３３は、ｎビットｍ語の連想メモリ・ワード４３−１〜４３−ｍと、論理ゲート１６−１〜１６−ｎを有しており、各連想メモリ・ワード４３−ｊは、ｎ個の連想メモリ・セル４４−ｊ−１〜４４−ｊ−ｎを備えている。論理ゲート１６−１〜１６−ｎの動作は第一の実施の形態の連想メモリ１と全く同様である。
【０１３２】
　各連想メモリ・ワード４３−ｊには、対応するデータ・ワード線３−ｊと、マスク・ワード線６−ｊが入力のために接続され、対応する中間一致線４１−ｊ、およびｎ本の一致データ中間論理線１４−１〜１４−ｎが出力のために接続され、ｎ本のビット線１３−１〜１３−ｎが入出力のために接続されている。
【０１３３】
　各連想メモリ・セル４４−ｊ−ｋには、対応するデータ・ワード線３−ｊと、マスク・ワード線６−ｊが入力のために接続され、対応する中間一致線４１−ｊ、および一致データ中間論理線１４−ｋが出力のために接続され、ビット線１３−ｋが入出力のために接続されている。
【０１３４】
　各連想メモリ・セル４４−ｊ−ｋは、ビット線１３−ｋを介して外部から入力される記憶データの対応するビット情報を格納するデータ・セル８−ｊ−ｋと、データ・セル８−ｊ−ｋに記憶されたビット情報と外部からビット線１３−ｋを介して入力される情報とを比較する比較器３２−ｊ−ｋと、外部からビット線１３−ｋを介して入力されるマスク情報の対応するビット情報を格納するマスク・セル９−ｊ−ｋと、および論理ゲート１１−ｊ−ｋとを備えている。
【０１３５】
　連想メモリ・セル４４の、データ・ワード線３，マスク・ワード線６、一致データ中間論理線１４、ビット線１３、データ・セル８，マスク・セル９、論理ゲート１１の動作は、第一の実施例の連想メモリ１の連想メモリ・セル７と全く同様である。第一の実施例の連想メモリ１の連想メモリ・セル７の一致線５は、中間一致線４１に名称変更されている。従って、第一の実施例の連想メモリ１の連想メモリ・セル７と異なる点についてのみ説明する。
【０１３６】
　本例では各データ・セル８に対応するマスク・セル９に格納されているマスク情報が有効状態の場合、該当データ・セル８には記憶データの無効状態を格納する。
【０１３７】
　中間一致線４１は、検索動作の開始前には、ハイ・レベルにプリ・チャージされているか、図示しない抵抗によりプル・アップされ、有効状態“１”になっているものとする。
【０１３８】
　比較器３２は、対応するビット線１３と、それに同一の連想メモリ・セル４４−１−１〜４４−ｍ−ｎの中のデータ・セル８に格納されている記憶データと、マスク・セル９に格納されているマスク情報を入力とする。比較器３２は、マスク情報が有効状態ならば、対応する中間一致線４１を解放状態にし、それ以外の場合には、ビット線１３の値と記憶データが一致するならば対応する中間一致線４１を開放状態にし、一致しないならば無効状態“０”を出力する。連想メモリ・ワード４３の中のｎ個の比較器３２がすべて中間一致線４１を開放状態にしているときに、中間一致線４１は有効状態“１”となり、それ以外の場合には無効状態“０”となる、中間一致線４１の有効状態“１”を真としたワイアードＡＮＤ論理接続を構成している。つまり、検索動作時には、マスク情報が有効状態“０”のために比較対象から除外されたビットを除いて、連想メモリ・ワード４３が格納している記憶データとビット線１３−１〜１３−ｎが完全に一致する場合に限り、中間一致線４１は有効状態“１”となり、それ以外の場合は無効状態“０”となる。もちろん同様の動作となるように通常の論理ゲートを用いて構成してもかまわない。
【０１３９】
　次に、上述の連想メモリ・セル４４の構成例を図１０を用いて説明する。図２に示す第一の実施例の連想メモリ・セル７と比較すれば分かるように、本発明の連想メモリ・セル４４は、比較制御線４と、比較器内ＭＯＳトランジスタ（Ｔ７）２０９が削除され、一致線５が中間一致線４１に名称変更されている点を除くと、第一の実施例の連想メモリ・セル７と同様である。従って連想メモリ・セル７と異なる部分のみの説明を行う。
【０１４０】
　比較器３２はＭＯＳトランジスタ（Ｔ３）２０５、ＭＯＳトランジスタ（Ｔ４）２０６、ＭＯＳトランジスタ（Ｔ５）２０７、およびＭＯＳトランジスタ（Ｔ６）２０８により構成され、それらの動作は第一の実施例の連想メモリ・セル７と同様である。
【０１４１】
　従って、ＭＯＳトランジスタ（Ｔ５）２０７が導通状態のときに、ＭＯＳトランジスタ（Ｔ６）２０８が導通状態の場合に連想メモリ・セル４４は中間一致線４１に無効状態“０”を出力し、それ以外の時には中間一致線４１を開放状態とする。すなわち、マスク情報が無効状態“０”の場合には検索データ１２と記憶データの比較結果によらず中間一致線４１を開放状態とし、それ以外の場合にはビット線１３ａ，１３ｂ上の検索データ１２とデータ・セル８に格納されている記憶データが一致するときに開放状態とし、異なる場合には無効状態“０”を出力する。
【０１４２】
　ｎビットｍ語のマスク機能無し連想メモリ１０１の構成例を図１１に示す。マスク機能無し連想メモリ１０１は、連想メモリ・ワード１０４−１〜１０４−ｍから構成され、各連想メモリ・ワード１０４−ｊは、ｎ個の連想メモリ・セル１０５−ｊ−１〜１０５−ｊ−ｎを備えている。各連想メモリ・ワード１０４−ｊには、対応するデータ・ワード線１０６−ｊが入力のために接続され、対応するデータ一致線１０７−ｊが出力のために接続され、ｎ本のビット線１０３−１〜１０３−ｎが入出力のために接続されている。
【０１４３】
　各連想メモリ・セル１０５−ｊ−ｋには、対応するデータ・ワード線１０６−ｊが入力のために接続され、対応するデータ一致線１０７−ｊが出力のために接続され、ビット線１０３−ｋが入出力のために接続されている。また、各連想メモリ・セル１０５−ｊ−ｋは、第二の記憶データの対応するビット情報を格納するデータ・セル１０８−ｊ−ｋと、ビット線１０３−ｋを介して入力される一致データ論理和信号３８とデータ・セル１０８−ｊ−ｋに記憶されたビット情報とを比較する比較器１０９−ｊ−ｋとを備えている。一致データ論理和信号出力機能付連想メモリ３３の対応する連想メモリ・ワード４３−ｊのマスク・セル９−ｊ−１〜９−ｊ−ｎの中でマスク情報の有効状態となっているビットと対応するデータ・セル１０８―ｊ−１〜１０８−ｊ−ｎには、記憶データの無効状態をあらかじめ格納する。それ以外のビットのデータ・セル１０８―ｊ−１〜１０８−ｊ−ｎには、一致データ論理和信号出力機能付連想メモリ３３の対応するデータ・セル８−ｊ−１〜８−ｊ−ｎと同一の値をあらかじめ格納しておく。
【０１４４】
　各連想メモリ・セル１０５−１−１〜１０５−ｍ−ｎにおいて、ビット線１０３、データ・ワード線１０６，データ・セル１０８、およびデータ一致線１０７の動作は、従来の連想メモリ１１６と同様である。
【０１４５】
　データ一致線１０７は、検索動作の開始前には、ハイ・レベルにプリ・チャージされているか、図示しない抵抗によりプル・アップされ、有効状態“１”になっているものとする。
【０１４６】
　比較器１０９は、対応するビット線１０３と、それに同一の連想メモリ・セル１０５−１−１〜１０５−ｍ−ｎの中のデータ・セル１０８に格納されている第二の記憶データとを比較し、一致するならば対応するデータ一致線１０７を開放状態にし、一致しないならば無効状態“０”を出力する。連想メモリ・ワード１０４の中のｎ個の比較器１０９がすべてデータ一致線１０７を開放状態にしているときに、データ一致線１０７は有効状態“１”となり、それ以外の場合には無効状態“０”となる、データ一致線１０７の有効状態“１”を真としたワイアードＡＮＤ論理接続を構成している。つまり、検索動作時には、連想メモリ・ワード１０４が格納している第二の記憶データとビット線１０３−１〜１０３−ｎが完全に一致する場合に限り、データ一致線１０７は有効状態“１”となり、不一致の場合には無効状態“０”となる。もちろん同様の動作となるように通常の論理ゲートを用いて構成してもかまわない。
【０１４７】
　次に、マスク機能無し連想メモリ１０１の連想メモリ・セル１０５の構成例を図１２を用いて説明する。図１６に示す従来の連想メモリ・セル１１８と比較すれば分かるように、マスク機能無し連想メモリ１０１の連想メモリ・セル１０５の、ビット線１０３ａ、１０３ｂ、データ・ワード線１０６、データ・セル１０８は、従来の連想メモリ・セル１１８と同様である。従って従来と違う部分のみの説明を行う。
【０１４８】
　比較器１０９は、ＭＯＳトランジスタ（Ｔ１０３）３０５、ＭＯＳトランジスタ（Ｔ１０４）３０６、およびＭＯＳトランジスタ（Ｔ１０５）３０７により構成される。従来の連想メモリ・セル１１８の比較器１１３とは、データ一致線１０７と低電位の間に直列に挿入されるＭＯＳトランジスタからＭＯＳトランジスタ（Ｔ１０６）３０８が削除され、データ一致線１０７とＭＯＳトランジスタＴ１０５（３０７）を介してワイアードＡＮＤ接続している点のみが異なる。
【０１４９】
　従って、検索動作時には、データ・セル１０８に格納されている第二の記憶データと、ビット線１０３ａ，１０３ｂ上の検索データ１０２が異なる場合にＭＯＳトランジスタ（Ｔ１０５）３０７は導通状態になり、連想メモリ・セル１０５はデータ一致線１０７に無効状態“０”を出力し、それ以外の時にはデータ一致線１０７を開放状態とする。
【０１５０】
［第三の実施例の動作］
　次に、上述の連想メモリ４２を、図１９のルータ４００−３における転送先ネットワーク・アドレスの計算に用いた場合の動作を、図１３を用いて説明する。
【０１５１】
　連想メモリ４２を８ビット５語の構成と仮定し、一致データ論理和信号出力機能付連想メモリ３３の各連想メモリ・ワード４３−１〜４３−５に格納されている記憶データ、マスク情報には、図１９のルータ４００−３のネットワーク・アドレス（３．＊．＊．＊）以外の接続情報を記憶しているものとする。このとき、接続情報の中のドント・ケア“＊”状態のビットは、マスク情報の該当ビットをマスク・データの有効状態“０”とすることで表現される。記憶データの該当ビットには記憶データの無効状態“０”を格納する。
【０１５２】
　つまり、連想メモリ・ワード４３−１には（１．＊．＊．＊）を実現するため２進数で、記憶データには（０１．００．００．００）を、マスク情報として（１１．００．００．００）を格納してある。同様に連想メモリ・ワード４３−２には（２．＊．＊．＊）を実現するため２進数で、記憶データには（１０．００．００．００）を、マスク情報として（１１．００．００．００）を格納してある。連想メモリ・ワード４３−３には（１．２．２．＊）を実現するため２進数で、記憶データには（０１．１０．１０．００）を、マスク情報として（１１．１１．１１．００）を格納してある。連想メモリ・ワード４３−４には（１．２．＊．＊）を実現するため２進数で、記憶データには（０１．１０．００．００）を、マスク情報として（１１．１１．００．００）を格納してある。連想メモリ・ワード４３−５には（２．１．１．＊）を実現するため２進数で、記憶データには（１０．０１．０１．００）を、マスク情報として（１１．１１．１１．００）を格納してある。
【０１５３】
　マスク機能無し連想メモリ１０１の各連想メモリ・ワード１０４−１〜１０４−５に格納されている第二の記憶データとして、図１９のルータ４００−３の接続情報においてドント・ケア“＊”状態のビットを記憶データの無効状態“０”とした値を記憶しているものとする。つまり、連想メモリ・ワード１０４−１には（０１．００．００．００）を、連想メモリ・ワード１０４−２には（１０．００．００．００）を、連想メモリ・ワード１０４−３には（０１．１０．１０．００）を、連想メモリ・ワード１０４−４には（０１．１０．００．００）を、連想メモリ・ワード１０４−５には（１０．０１．０１．００）を、それぞれ格納してある。
【０１５４】
　以降、検索データ１２として図１９のＰＣ４０１−１の４進数のネットワーク・アドレス（１．２．２．１）を入力し検索動作を行った場合の動作説明をする。
【０１５５】
　まず、検索動作の前に、すべての中間一致線４１−１〜４１−５、およびデータ一致線１０７−１〜１０７−５は、ハイ・レベルにプリ・チャージされているか、図示しない抵抗によりプル・アップされ、有効状態“１”になっているものとする。
【０１５６】
　検索データ１２をビット線１３−１〜１３−８に入力すると、一致データ論理和信号出力機能付連想メモリ３３の連想メモリ・ワード４３−１に格納されている４進表現の（１．＊．＊．＊）と、連想メモリ・ワード４３−３に格納されている４進表現の（１．２．２．＊）と、連想メモリ・ワード４３−４に格納されている４進表現の（１．２．＊．＊）がビット線１３−１〜１３−８上の検索データ１２と一致する。従って、中間一致線４１−１、４１−３および４１−４の３本が有効状態“１”となり、残りの中間一致線４１−２、４１−５は無効状態“０”となる。
【０１５７】
　ここで、一致データ論理和線１７−１からは、連想メモリ・ワード４３−１内の一致データ中間論理線１４−１に対応する記憶データ“０”と、連想メモリ・ワード４３−３内の一致データ中間論理線１４−１に対応する記憶データ“０”と、連想メモリ・ワード４３−４内の一致データ中間論理線１４−１に対応する記憶データ“０”に対しての“１”を真とした論理和結果“０”が出力される。一致データ論理和線１７−２からは、連想メモリ・ワード４３−１内の一致データ中間論理線１４−２に対応する記憶データ“１”と、連想メモリ・ワード４３−３内の一致データ中間論理線１４−２に対応する記憶データ“１”と、連想メモリ・ワード４３−４内の一致データ中間論理線１４−２に対応する記憶データ“１”に対しての“１”を真とした論理和結果“１”が出力される。以降同様に、一致データ論理和線１７−３からは“０”と“１”と“１” に対しての“１”を真とした論理和結果“１”が、一致データ論理和線１７−４からは“０”と“０”と“０”に対しての“１”を真とした論理和結果“０”が、一致データ論理和線１７−５からは“０”と“１”と“０” に対しての“１”を真とした論理和結果“１”が、一致データ論理和線１７−６からは“０”と“０”と“０”に対しての“１”を真とした論理和結果“０”が、一致データ論理和線１７−７からは“０”と“０”と“０”に対しての“１”を真とした論理和結果“０”が、一致データ論理和線１７−８からは“０”と“０”と“０”に対しての“１”を真とした論理和結果“０”が、それぞれ出力される。従って、一致データ論理和線１７−１〜１７−８には、２進表現で“０１１０１０００”が、一致データ論理和信号３８として出力されることになる。
【０１５８】
　一致データ論理和信号３８の状態“０１１０１０００”は、マスク機能無し連想メモリ１０１のビット線１０３−１〜１０３−８に入力され、マスク機能無し連想メモリ１０１は２回目の検索動作を開始する。本例では、ビット線１０３−１〜１０３−８の状態“０１１０１０００”に対して、連想メモリ・ワード１０４−３が格納する第二の記憶データが完全に一致し、対応するデータ一致線１０７−３を開放状態にする。他の連想メモリ・ワード１０４−１，１０４−２、１０４−４、および１０４−５が格納する第二の記憶データは一致しないので、対応するデータ一致線１０７−１，１０７−２、１０７−４、および１０７−５に無効状態“０”を出力する。従って、データ一致線１０７−１〜１０７−５の中で２回目の検索動作後も有効状態“１”を保持し続けるのは、データ一致線１０７−３のみとなる。データ一致線１０７−１〜１０７−５の状態は、一致線５−１〜５−５として外部に出力されるので、２回目の検索動作後も有効状態を出力しているのは一致線５−３のみとなる。
【０１５９】
　従って、入力した検索データ１２と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報の有効状態のビットが最も少ない記憶データに対応する一致線５−３のみに有効状態を出力することがわかる。
【０１６０】
　上述のように、第三の実施の形態の連想メモリを使用すれば１クロックで最短マスク情報を持つワードを選択できる。ここで、記憶手段をビット線１０３−１〜１０３−ｎと、一致データ論理和線１７−１〜１７−ｎの間に挿入し、マスク機能無し連想メモリ１０１が格納された一致データ論理和信号３８に対する２回目の検索動作を実行するのと同時に、一致データ論理和信号出力機能付連想メモリ３３が次の検索データ１２に対する１回目の検索動作を実行するようにパイプライン処理を構成することができるのも言うまでもない。もちろん、記憶手段を挿入する場所は、上述の場所に限らないことも言うまでもない。
【０１６１】
［第四の実施例］
　次に、本発明の第一の実施の形態の連想メモリ１を転送先ネットワーク・アドレス計算に用いたルータの構成例を示すブロック図を図１４に示す。ルータ４００は、入力転送データ４０８を入力とし、出力転送データ４０９を出力する。入力転送データ４０８は、目的地ネットワーク・アドレス４１１と、転送先ネットワーク・アドレス４１０とデータ部４１２を有している。出力転送データ４０９は、目的地ネットワーク・アドレス４１１と、第２の転送先ネットワーク・アドレス４１３とデータ部４１２を有している。図２０に示す従来のルータでは、従来の連想メモリ１１６の消費電力が大きいために冷却装置４１４を有していたが、本発明の連想メモリ１を用いた本発明のルータでは冷却装置４１４は不要である。
【０１６２】
　入力転送データ４０８の転送先ネットワーク・アドレス４１０は当然ルータ４００のネットワーク・アドレスとなっている。ルータ４００は、目的地ネットワーク・アドレス抽出部４０６と、連想メモリ１と、エンコーダ４０２と、メモリ４０４と転送先ネットワーク・アドレス変更部４０７とにより構成される。
ここでは、図１９のルータ４００−３に適用した場合において、ネットワーク・アドレス（３．＊．＊．＊）の機器から、ネットワーク・アドレス（１．＊．＊．＊）または（２．＊．＊．＊）の機器に転送する場合について説明する。図１４では、記憶データの有効状態は“１”、無効状態は“０”とする。マスク情報の有効状態は“０”、無効状態は“１”である。また、一致線５−１〜５−５の有効状態は“１”、無効状態は“０”とする。
【０１６３】
　目的地ネットワーク・アドレス抽出部４０６は、入力転送データ４０８の目的地ネットワーク・アドレス４１１を抽出し、検索データ１２として、連想メモリ１に入力する。
【０１６４】
　連想メモリ１にはルータ４００−３のネットワーク・アドレス（３．＊．＊．＊）以外の接続情報を記憶している。このとき、接続情報の中のドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態“０”、マスク情報の該当ビットをマスク・データの有効状態“０”とすることで表現される。つまり、連想メモリ・ワード２−１には（１．＊．＊．＊）を実現するため２進数で、記憶データには（０１．００．００．００）を、マスク情報として（１１．００．００．００）を格納してある。同様に連想メモリ・ワード２−２には（２．＊．＊．＊）を実現するため２進数で、記憶データには（１０．００．００．００）を、マスク情報として（１１．００．００．００）を格納してある。連想メモリ・ワード２−３には（１．２．２．＊）を実現するため２進数で、記憶データには（０１．１０．１０．００）を、マスク情報として（１１．１１．１１．００）を格納してある。連想メモリ・ワード２−４には（１．２．＊．＊）を実現するため２進数で、記憶データには（０１．１０．００．００）を、マスク情報として（１１．１１．００．００）を格納してある。連想メモリ・ワード２−５には（２．１．１．＊）を実現するため２進数で、記憶データには（１０．０１．０１．００）を、マスク情報として（１１．１１．１１．００）を格納してある。
【０１６５】
　連想メモリ・ワード２−１〜連想メモリ・ワード２−５に対応する一致線５−１〜５−５はエンコーダ４０２に出力される。エンコーダ４０２は一致線５−１〜５−５を、メモリ・アドレス信号４０３にエンコードし、メモリ４０４に出力する。
【０１６６】
　メモリ４０４には、連想メモリ１の各連想メモリ・ワード２−１〜２−５の記憶データ、マスク情報により構成されるネットワーク・アドレスに対応するルータのネットワーク・アドレスを、同一のワードに記憶してある。たとえば、連想メモリ１の連想メモリ・ワード２−１にはネットワーク・アドレス（１．＊．＊．＊）が記憶されているが、これに対応するルータ４００−１のネットワーク・アドレスがメモリ４０４の同じくワード１に格納されている。同様にメモリ４０４のワード２にはルータ４００−２のネットワーク・アドレスが、ワード３にはルータ４００−６のネットワーク・アドレスが、ワード４にはルータ４００−４のネットワーク・アドレスが、ワード５にはルータ４００−７のネットワーク・アドレスが格納されている。また、メモリ４０４は、メモリ・アドレス信号４０３をリード・アドレスとして指定されるワードに格納されているデータを、メモリ・データ信号４０５として出力する。
【０１６７】
　転送先ネットワーク・アドレス変更部４０７は、出力転送データ４０９の第２の転送先アドレス４１３を、メモリ・データ信号４０５の値に変更した後、第２のネットワーク・アドレスに対応するネットワーク機器に転送を行う。
【０１６８】
　たとえば入力転送データ４０８の目的地ネットワーク・アドレス４１１が（１．２．２．１）の場合、連想メモリ１での検索動作終了時には、連想メモリ・ワード２−３が格納している（１．２．２．＊）に対応する一致線５−３のみが有効状態となる。これにより、エンコーダ４０２はメモリ・アドレス４０３として“３”を出力し、メモリ４０４はルータ４００−６のネットワーク・アドレスをメモリ・データ信号４０５として出力する。転送先ネットワーク・アドレス変更部４０７により、出力転送データ４０９の第２の転送先ネットワーク・アドレス４１３を、ルータ４００−６のネットワーク・アドレスに変更し、ルータ４００−６に向けて出力転送データ４０９を転送する。
【０１６９】
　このように、本発明の連想メモリ１をネットワーク・アドレス計算を行うルータ４００に組み込めば、従来に比較して消費電力が小さくなるため、冷却装置４１４が不要になりコストが削減することができる。
【０１７０】
　また、チップあたりの記憶容量増加に伴いルータ４００に内蔵する連想メモリ１の個数を削減するができる。従って、複数の連想メモリが出力した検索結果の比較処理が不要になるため、ルータ４００を用いたコンピュータ・ネットワーク・システムのデータ転送速度を高速化することができる。
【図面の簡単な説明】
【０１７１】
【図１】本発明の第一の実施の形態の連想メモリの構成例を示すブロック図である。
【図２】本発明の第一の実施の形態の連想メモリ・セルの構成例を示す回路図である。
【図３】本発明の第一の実施の形態の連想メモリの動作例を示す図である。
【図４】本発明の第一の実施の形態の連想メモリの動作タイミング・チャートである。
【図５】本発明の第二の実施の形態の連想メモリの構成例を示すブロック図である。
【図６】本発明の第二の実施の形態の連想メモリ・セルの構成例を示す回路図である。
【図７】本発明の第二の実施の形態の連想メモリの動作例を示す図である。
【図８】本発明の第三の実施の形態の連想メモリの構成例を示すブロック図である。
【図９】本発明の第三の実施の形態の一致データ論理和信号出力機能付連想メモリの構成例を示すブロック図である。
【図１０】本発明の第三の実施の形態の連想メモリ・セルの構成例を示す回路図である。
【図１１】マスク機能無し連想メモリの構成例を示すブロック図である。
【図１２】マスク機能無し連想メモリの連想メモリ・セルの構成例を示す回路図である。
【図１３】本発明の第三の実施の形態の連想メモリの動作例を示す図である。
【図１４】本発明の連想メモリを転送先ネットワーク・アドレス計算に用いたルータの構成例を示すブロック図である。
【図１５】従来の連想メモリの一構成例を示すブロック図である。
【図１６】従来の連想メモリ・セルの一構成例を示す回路図である。
【図１７】従来の連想メモリの動作例を示す図である。
【図１８】従来の連想メモリの動作タイミング・チャートである。
【図１９】ネットワークの構成例を示す接続図である。
【図２０】従来の連想メモリをルータの転送先アドレス計算に用いた場合の説明図である。
【符号の説明】
【０１７２】
　　１　　連想メモリ
　　２―１〜２−ｍ　　連想メモリ・ワード
　　３−１〜３−ｍ　　データ・ワード線
　　４　　　　　　　　比較制御信号
　　５−１〜５−ｍ　　一致線
　　６−１〜６−ｍ　　マスク・ワード線
　　７−１−１〜７−ｍ−ｎ　　連想メモリ・セル
　　８−１−１〜８−ｍ−ｎ　　データ・セル
　　９−１−１〜９−ｍ−ｎ　　マスク・セル
　１０−１−１〜１０−ｍ−ｎ　　比較器
　１１−１−１〜１１−ｍ−ｎ　　論理ゲート
　１２−１〜１２−ｎ　　検索データ
　１３−１〜１３−ｎ　　ビット線
　１４−１〜１４−ｎ　　一致データ中間論理線
　１５−１〜１５−ｎ　　抵抗
　１６−１〜１６−ｎ　　論理ゲート
　１７−１〜１７−ｎ　　一致データ論理和線
　２０−１〜２０−ｎ　　ラッチ出力線
　２１　　ｎビット・ラッチ
　２２　　ラッチ制御信号
　２３　　ｎビット２入力１出力セレクタ
　２４　　選択信号
　２５−１−１〜２５−ｍ−ｎ　　論理ゲート
　２６−１−１〜２６−ｍ−ｎ　　連想メモリ・セル
　２７−１〜２７−ｎ　　論理ゲート
　２８　　連想メモリ
　３０　　制御回路
　３１　　クロック信号
　３２−１−１〜３２−ｍ−ｎ　　比較器
　３３　　一致データ論理和信号出力機能付連想メモリ
　３８　　一致データ論理和信号
　４１−１〜４１−ｍ　　中間一致線
　４２　　連想メモリ
　４３―１〜４３−ｍ　　連想メモリ・ワード
　４４−１−１〜４４−ｍ−ｎ　　連想メモリ・セル
１０１　　マスク機能無し連想メモリ
１０２−１〜１０２−ｎ　　検索データ
１０３−１〜１０３−ｎ　　ビット線
１０４−１〜１０４−ｍ　　連想メモリ・ワード
１０５−１−１〜１０５−ｍ−ｎ　　連想メモリ・セル
１０６−１〜１０６−ｍ　　データ・ワード線
１０７−１〜１０７−ｍ　　データ一致線
１０８−１−１〜１０８−ｍ−ｎ　　データ・セル
１０９−１−１〜１０９−ｍ−ｎ　　比較器
１１０　　連想メモリ
１１１−１〜１１１−ｍ　　マスク・ワード線
１１２−１−１〜１１２−ｍ−ｎ　　マスク・セル
１１３−１−１〜１１３−ｍ−ｎ　　比較器
１１６　　連想メモリ
１１７−１〜１１７−ｍ　　連想メモリ・ワード
１１８−１−１〜１１８−ｍ−ｎ　　連想メモリ・セル
１１９−１〜１１９−ｍ　　マスク一致線
１２０−１−１〜１２０−ｍ−ｎ　　マスク比較器
１２１−１−１〜１２１−ｍ−ｎ　　論理ゲート
１２２−１〜１２２−ｎ　　最短マスク線
１２３−１〜１２３−ｍ　　ラッチ
１２４　　ラッチ制御信号
１２５−１〜１２５−ｎ　　抵抗
１２６　　ｎビット・ラッチ
１２７−１〜１２７−ｎ　　ラッチ出力線
１２８　　ｎビット２入力１出力セレクタ
１２９　　選択信号
１３０　　クロック信号
１３１　　制御回路
２０１　　反転論理ゲートＧ１
２０２　　反転論理ゲートＧ２
２０３　　ＭＯＳトランジスタＴ１
２０４　　ＭＯＳトランジスタＴ２
２０５　　ＭＯＳトランジスタＴ３
２０６　　ＭＯＳトランジスタＴ４
２０７　　ＭＯＳトランジスタＴ５
２０８　　ＭＯＳトランジスタＴ６
２０９　　ＭＯＳトランジスタＴ７
２１０　　反転論理ゲートＧ３
２１１　　反転論理ゲートＧ４
２１２　　ＭＯＳトランジスタＴ８
２１３　　ＭＯＳトランジスタＴ９
２１４　　ＭＯＳトランジスタＴ１０
２１５　　ＭＯＳトランジスタＴ１１
３０１　　反転論理ゲートＧ１０１
３０２　　反転論理ゲートＧ１０２
３０３　　ＭＯＳトランジスタＴ１０１
３０４　　ＭＯＳトランジスタＴ１０２
３０５　　ＭＯＳトランジスタＴ１０３
３０６　　ＭＯＳトランジスタＴ１０４
３０７　　ＭＯＳトランジスタＴ１０５
３０８　　ＭＯＳトランジスタＴ１０６
３０９　　反転論理ゲートＧ１０３
３１０　　反転論理ゲートＧ１０４
３１１　　ＭＯＳトランジスタＴ１０７
３１２　　ＭＯＳトランジスタＴ１０８
３１３　　ＭＯＳトランジスタＴ１０９
３１４　　ＭＯＳトランジスタＴ１１０
３１５　　ＭＯＳトランジスタＴ１１１
３１６　　ＭＯＳトランジスタＴ１１２
３１７　　ＭＯＳトランジスタＴ１１３
４００−１〜４００−７　　ルータ
４０１−１　　ＰＣ
４０２　　エンコーダ
４０３　　メモリ・アドレス信号
４０４　　メモリ
４０５　　メモリ・データ信号
４０６　　目的地ネットワーク・アドレス抽出部
４０７　　転送先ネットワーク・アドレス変更部
４０８　　入力転送データ
４０９　　出力転送データ
４１０　　転送先ネットワーク・アドレス
４１１　　目的地ネットワーク・アドレス
４１２　　データ部
４１３　　第２の転送先ネットワーク・アドレス
４１４　　冷却装置
【図１】
2004134081.tif 000003
【図２】
2004134081.tif 000004
【図３】
2004134081.tif 000005
【図４】
2004134081.tif 000006
【図５】
2004134081.tif 000007
【図６】
2004134081.tif 000008
【図７】
2004134081.tif 000009
【図８】
2004134081.tif 000010
【図９】
2004134081.tif 000011
【図１０】
2004134081.tif 000012
【図１１】
2004134081.tif 000013
【図１２】
2004134081.tif 000014
【図１３】
2004134081.tif 000015
【図１４】
2004134081.tif 000016
【図１５】
2004134081.tif 000017
【図１６】
2004134081.tif 000018
【図１７】
2004134081.tif 000019
【図１８】
2004134081.tif 000020
【図１９】
2004134081.tif 000021
【図２０】
2004134081.tif 000022