トップ :: G 物理学 :: G11 情報記憶




【発明の名称】 連想メモリとその検索方法及びルータとネットワークシステム
【発明者】 【氏名】小倉 直志
【要約】 【課題】データ転送速度の高いネットワーク・システムの消費電力を削減する。

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