(57)【特許請求の範囲】
【請求項１】
ｎ（ｎは１以上の整数）ビットの検索データを入力とし、転送先のネットワークアドレスを特定するアドレス出力信号を出力する連想メモリ・システムにおいて、
ｉ）１ワードが各ｎビットの１次記憶データとマスク情報とから構成される構造化データをｍ（ｍは２以上の整数）個格納し、各ワード毎に、前記検索データと前記１次記憶データとを対応する前記マスク情報を考慮しつつ比較し、一致する前記１次記憶データ同士に対して論理演算を行い、演算結果をｎビットの中間データとして出力するｐ（ｐは２以上の整数）個の１次検索用連想メモリと；
ii）ｐ個の前記中間データの中から、無効状態にあるビットの数が最も少ない中間データを選択し、ｎビットの最適化中間データとして出力する中間データ演算部と；
iii)前記１次記憶データに対応する１ワードがｎビットの２次記憶データをｍ個格納し、各ワード毎に、前記最適化中間データと前記２次記憶データとを比較し、一致する場合には有効状態を、不一致の場合には無効状態を各ワードに対応するｍ個の一致線に割当てるｐ個の２次検索用連想メモリと；
iv）ｍ×ｐ個の前記一致線の状態を検索し、有効状態に割当てられている前記一致線に対応する前記２次記憶データ中から前記転送先のネットワークアドレスを特定するアドレス出力信号を生成するアドレス信号生成部と；
を具備することを特徴とする連想メモリ・システム。
【請求項２】
ｎ（ｎは１以上の整数）ビットの検索データを入力とし、転送先のネットワークアドレスを特定するアドレス出力信号を出力する連想メモリ・システムにおいて、
ｉ）１ワードが各ｎビットの１次記憶データとマスク情報とから構成される構造化データをｍ（ｍは２以上の整数）個格納し、各ワード毎に、前記検索データと前記１次記憶データとを対応する前記マスク情報を考慮しつつ比較し、一致する前記１次記憶データ同士に対して論理演算を行い、演算結果をｎビットの中間データとして出力するｐ（ｐは２以上の整数）個の１次検索用連想メモリと；
ii）ｐ個の前記中間データの中から、無効状態にあるビットの数が最も少ない中間データを最適化中間データとして選択し、この最適化中間データと各中間データとを比較し、一致する場合には有効状態を、不一致の場合には無効状態を各中間データに対応するｎ個の検出信号線に割当てる中間データ判定部と；
iii)前記１次記憶データに対応し、１ワードがｎビットの２次記憶データをｍ個格納し、各ワード毎に、前記中間データと前記２次記憶データとを比較し、一致する場合には有効状態を、不一致の場合には無効状態を各ワードに対応するｍ個の一致線に割当てるｐ個の２次検索用連想メモリと；
iv）前記検出信号線に有効状態が割当てられている場合には前記一致線に割当てられた状態を、無効状態が割当てられている場合には無効状態を、前記一致線に対応する実効一致線に割当てる一致信号出力手段と；
ｖ）ｍ×ｐ個の前記実効一致線の状態を検索し、有効状態に割当てられている前記実効一致線に対応する前記２次記憶データ中から前記転送先のネットワークアドレスを特定するアドレス出力信号を生成するアドレス信号生成部と；
を具備することを特徴とする連想メモリ・システム。
【請求項３】
優先順位を有するｋ（ｋは２以上の整数）個の部分検索領域から構成されるｎ（ｎは１以上の整数）ビットの検索データを入力し、転送先のネットワークアドレスを特定するアドレス出力信号を出力する連想メモリ・システムにおいて、
ｉ）１ワードがｋ個の検索領域から構成される各ｎビットの１次記憶データとマスク情報とから構成される構造化データをｍ（ｍは２以上の整数）個格納し、各ワード毎に、前記検索データと前記１次記憶データとを対応する前記マスク情報を考慮しつつ比較し、一致する前記１次記憶データ同士に対して論理演算を行い、演算結果中の第１の優先順位を持つ部分検索領域に対応するビット領域のみを第１の中間データとして出力するｐ（ｐは２以上の整数）個の１次検索用連想メモリと；
ii）ｐ個の前記第１の中間データについて、無効状態にあるビット数が最も少ない第１の中間データに対して有効状態を、他に対して無効状態を各第１の中間データに対応するｎ個の検出信号線に割当てる中間データ判定部と；
iii)前記１次記憶データに対応し、１ワードがｎビットの２次記憶データをｍ個格納し、各ワード毎に、前記検索データの第ｈ（ｈは１以上、ｋ−１以下の整数）番目の優先順位を持つ部分領域に対応するビット領域のみを対象として、第ｈの中間データと比較し、一致する前記２次記憶データ同士に対して論理演算を行い、演算結果中の第（ｈ＋１）の優先順位を持つ部分検索領域に対応するビット領域のみを第（ｈ＋１）の中間データとして出力するｐ個の第１乃至第（ｋ−１）部分２次検索用連想メモリと；
iv）ｐ個の前記第（ｈ＋１）の中間データについて、前段の前記検出信号線に有効状態が割当てられている場合には、無効状態にあるビット数が最も少ない第（ｈ＋１）の中間データに対して有効状態を、他に対して無効状態を各第（ｈ＋１）の中間データに対応するｎ個の検出信号線に割当てる第１乃至第（ｋ−１）２次中間データ判定部と；
ｖ）前記１次記憶データに対応し、１ワードがｎビットの２次記憶データをｍ個格納し、各ワード毎に、前記検索データの第ｋ番目の優先順位を持つ部分領域に対応するビット領域のみを対象として、第（ｈ＋１）の中間データと比較し、一致する場合には有効状態を、不一致の場合には無効状態を各ワードに対応するｍ個の一致線に割当てるｐ個の第ｋ部分２次検索用連想メモリと；
vi）第ｈの２次中間データ判定部の前記検出信号線に有効状態が割当てられている場合には前記一致線に割当てられた状態を、無効状態が割当てられている場合には無効状態を、前記一致線に対応する実効一致線に割当てる一致信号出力手段と；
vii)ｍ×ｐ個の前記実効一致線の状態を検索し、有効状態に割当てられている前記実効一致線に対応する前記２次記憶データ中から前記転送先のネットワークアドレスを特定するアドレス出力信号を生成するアドレス信号生成部と；
を具備することを特徴とする連想メモリ・システム。
【請求項４】
ｋ個の前記中間データの中から１つを選択する選択手段と、ｋ個の前記部分検索領域の中から１つを選択する制御手段とを設け、
第１乃至第ｋの部分２次検索用連想メモリおよび／又は第１乃至第（ｋ−１）２次中間データ判定部の一部又は全てを共有することを特徴とする請求項３に記載の連想メモリ・システム。
【請求項５】
優先順位を有するｑ（ｑは２以上の整数）個の部分検索領域から構成されるｎ（ｎは１以上の整数）ビットの検索データを入力し、転送先のネットワークアドレスを特定するアドレス出力信号を出力する連想メモリ・システムにおいて、
ｉ）１ワードがｑ個の検索領域から構成される各ｎビットの記憶データとマスク情報とから構成される構造化データをｍ（ｍは２以上の整数）個格納し、各ワード毎に、前記検索データと前記記憶データとを対応するマスク情報を考慮しつつ比較し、一致する前記記憶データ同士に対して論理演算を行い、演算結果中の第１の優先順位を持つ部分検索領域に対応するビット領域のみを中間データとして出力し、一致したワードに対応する一致線に有効状態を割当てる１次検索と、
前記検索データの第ｈ（ｈは１以上、ｑ以下の整数）番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、前回のクロック動作で得られた中間データとの比較を行い、一致する前記記憶データ同士に対して論理演算を行い、演算結果中の第（ｈ＋１）の優先順位を持つ部分検索領域に対応するビット領域のみを中間データとして出力し、一致したワードに対応する前記一致線に有効状態を割当てる２次検索と、を行うｐ（ｐは２以上の整数）個の１次２次検索兼用連想メモリと；
ii）ｐ個の前記中間データについて、対応する有効保持信号が有効状態のもののみを対象とし、無効状態にあるビット数が最も少ない中間データに対して有効状態を、他に対して無効状態を、各中間データに対応するｎ個の検出信号線に割当てる中間データ判定部と；
iii)記憶制御信号に応答し、前記ｎ個の検出信号線の検出状態を格納し、それぞれ対応する保持信号線に格納状態を割当てる記憶手段と；
iv）前記保持信号線に有効状態が割当てられている場合には、前記一致線に割当てられた状態を、無効状態が割当てられている場合には無効状態を、前記一致線に対応する実効一致線に割当てる一致信号出力手段と；
ｖ）ｍ×ｐ個の前記実効一致線の状態を検索し、有効状態に割当てられている前記実効一致線に対応する前記記憶データ中から前記転送先のネットワークアドレスを特定するアドレス出力信号を生成するアドレス信号生成部と；
を具備することを特徴とする連想メモリ・システム。
【請求項６】
前記中間データ判定部は、
入力された前記中間データの中で、無効状態のビットが最少の中間データを選択し、最適化中間データとして出力する中間データ演算部と、
前記最適化中間データと一致する中間データの前記検出信号線のみに有効状態を出力する中間データ比較手段と、を
有することを特徴とする請求項５に記載の連想メモリ・システム。
【請求項７】
前記中間データ判定部は、
入力された前記中間データの中で、無効状態のビットが最少の中間データを選択し、最適化中間データとして出力する中間データ演算部と、
前記最適化中間データと一致する中間データの前記検出信号線のみに有効状態を出力する中間データ比較手段と、を
有することを特徴とする請求項２に記載の連想メモリ・システム。
【請求項８】
前記中間データ演算部は、
前記複数の中間データの同一ビット位置同士を記憶データの有効状態を真として論理和演算する論理和手段を有することを特徴とする請求項１、６又は７のいずれかに記載の連想メモリ・システム。
【請求項９】
前記中間データ演算部は、
前記中間データを記憶データの有効状態を真とする２進表記の数値とみなしたとき、前記複数の中間データの中で最大値を選択する最大値選択手段を有することを特徴とする請求項１、６又は７のいずれかに記載の連想メモリ・システム。
【請求項１０】
前記中間データ演算部は、
入力された前記中間データの中で、無効状態にあるビット数を計数する複数の無効状態計数手段と、
前記複数の無効状態計数手段が出力する計数結果の中で最小値を選択する最小値選択手段と、
前記最小値に対応する中間データを選択し、前記最適化中間データとして出力する選択手段と、を有することを特徴とする請求項１、６又は７のいずれかに記載の連想メモリ・システム。
【請求項１１】
前記中間データ演算部は、
前記中間データの出力端子と前記最適化中間データの入力端子とを共用すべく、前記中間データ同士の、記憶データの有効状態を真とする結線論理和回路により構成されることを特徴とする請求項１に記載の連想メモリ・システム。
【請求項１２】
前記中間データ判定部は、
入力された前記中間データの中で、無効状態にあるビット数を計数する複数の無効状態計数手段と、
前記複数の無効状態計数手段が出力する計数結果の中で最小値を選択する最小値選択手段と、
前記最小値に対応する中間データの前記検出信号線のみに有効状態を出力する最小値比較手段とを
有することを特徴とする請求項５に記載の連想メモリ・システム。
【請求項１３】
前記中間データ判定部は、
入力された前記中間データの中で、無効状態にあるビット数を計数する複数の無効状態計数手段と、
前記複数の無効状態計数手段が出力する計数結果の中で最小値を選択する最小値選択手段と、
前記最小値に対応する中間データの前記検出信号線のみに有効状態を出力する最小値比較手段とを
有することを特徴とする請求項２に記載の連想メモリ・システム。
【請求項１４】
前記一致信号出力手段は、
前記保持信号線に無効状態が割当てられている場合に、前記一致線に割当てられた状態にかかわらず無効状態を前記実効一致線に出力する論理積手段を含むことを特徴とする請求項５に記載の連想メモリ・システム。
【請求項１５】
前記中間データ判定部は、
入力された前記中間データの中で、無効状態のビット数を計数する複数の無効状態計数手段と；
無効状態が出力されている前記検出信号線に対応する前記無効状態計数手段の計数結果を、前記中間データのビット数と等しいかまたは大きい数に変更する手段と、
前記複数の無効状態計数手段が出力する計数結果の中で最小値を選択する最小値選択手段と、
前記最小値に対応する中間データの前記検出信号線のみに有効状態を出力する最小値比較手段とを
有することを特徴とする請求項５に記載の連想メモリ・システム。
【請求項１６】
前記無効状態計数手段は、
記憶データの無効状態のビット数を、前記中間データの一側のビット位置から他側に向って、最初の記憶データの有効状態のビットが現われるまで計数することを特徴とする請求項１０に記載の連想メモリ・システム。
【請求項１７】
前記無効状態計数手段は、
記憶データの無効状態のビット数を、前記中間データの一側のビット位置から他側に向って、最初の記憶データの有効状態のビットが現われるまで計数することを特徴とする請求項１２、１３又は１５のいずれかに記載の連想メモリ・システム。
【請求項１８】
前記無効状態計数手段は、
対応する連想メモリに内蔵されていることを特徴とする請求項１０に記載の連想メモリ・システム。
【請求項１９】
前記無効状態計数手段は、
対応する連想メモリに内蔵されていることを特徴とする請求項１２、１３又は１５のいずれかに記載の連想メモリ・システム。
【請求項２０】
前記中間データ演算部は、
パイプライン処理を実行可能とするように記憶手段を有することを特徴とする請求項１、６又は７のいずれかに記載の連想メモリ・システム。
【請求項２１】
前記中間データ判定部は、
前記検出信号線に検出信号を出力するタイミングを、並行して実行している２次検索の終了と同期させるための手段を含むことを特徴とする請求項２又は５に記載の連想メモリ・システム。
【請求項２２】
前記１次記憶データを格納するメモリと前記２次記憶データを格納するメモリとを共用することを特徴とする請求項１乃至３のいずれかに記載の連想メモリ・システム。
【請求項２３】
前記アドレス信号生成部は、
対応する前記一致線に有効状態が割当てられているか否かを検出する一致検出手段と、
前記一致線上の信号を論理和演算する論理和手段と、
前記論理和手段の出力をアドレス信号の一つの領域として符号化する第１の符号化手段と、
前記一致検出手段の出力を前記アドレス信号の他の領域として符号化する第２の符号化手段と、を有することを特徴とする請求項１、２、３又は５のいずれかに記載の連想メモリ・システム。
【請求項２４】
前記アドレス信号生成部は、
対応する前記一致線に有効状態が割当てられているか否かを検出する一致検出手段と、
前記一致線上の信号をアドレス信号の１つの領域として符号化する第１の符号化手段と、
前記一致検出手段の出力を前記アドレス信号の他の領域として符号化する第２の符号化手段と、
前記第２の符号化手段の演算結果に応答して、前記第１の符号化手段の出力信号を選択する選択手段と、を有することを特徴とする請求項１、２、３又は５のいずれかに記載の連想メモリ・システム。
【請求項２５】
前記一致検出手段と前記第１の符号化手段とを対応する連想メモリに内蔵させたことを特徴とする請求項２４に記載の連想メモリ・システム。
【発明の詳細な説明】
技術分野
本発明は、連想メモリ・システムおよびネットワーク機器およびネットワークシステムに関する。特に検索マスク機能を有する連想メモリとそれを複数個接続した連想メモリ・システムおよびそれを用いたネットワーク機器およびネットワーク・システムに関する。
背景技術
一般的にネットワーク・システムでは、ネットワークに参加しているユーザ端末（例えばパーソナル・コンピュータなど）に対して、他のユーザ端末と識別するためのネットワーク・アドレスを、内部のグループごとに階層的に割り当てる。したがって、階層が上のグループほどネットワーク・アドレスの有効部分が短く、下の階層のグループほど長くなる。そのため、ネットワークに参加しているユーザ端末間の通信データの転送を制御するためのネットワーク機器（例えばネットワーク・ルータなど）に通信データが入力された場合、その宛先ネットワーク・アドレスおよび送出元ネットワーク・アドレスから、転送先を決定する処理や、転送可否を判定する処理には、ネットワーク・アドレスの有効部分の長さを考慮して比較する機能が不可欠であり、この機能を実現するため連想メモリが用いられている。
従来のコンピュータ・ネットワークの構成例を示す接続図を図２４に示す。ネットワークに参加しているユーザ端末には上述のように、その端末の属するグループに応じてあらかじめ決められた規則により階層的にネットワーク・アドレスが割り当てられる。ここではネットワーク・アドレスは複数桁の数値、例えば４桁の数値（ａ．ｂ．ｃ．ｄ）で表現されるものとして説明する。また、あらかじめ決められた規則は、例えばネットワーク・アドレスの先頭の数値でイギリス、ドイツ、日本などの国を示し、第２番目の数値で国の中の都市名を示し、更に第３番目の数値で都市の中の企業名を示し、最後の数値で該企業の中の端末を区別する、というように階層構造をとっている。以降、この階層をセグメントと呼ぶこととする。図２４においては、セグメントの階層構造を模擬的に示したものである。図において太線で囲まれた１つの矩形が１つのセグメントである。図２４では、ネットワーク・アドレスの先頭の数値が１であるセグメント１と、先頭の数値が２であるセグメント２と、先頭の数値が３であるセグメント３が、最上位のセグメントとして存在している。セグメント１の下の階層に、上位２つの数値が１．２であるネットワーク・アドレスを持つセグメント４があり、更にその下に上位３つの数値が１．２．２であるネットワーク・アドレスを持つセグメント６があり、更にその中にネットワーク・アドレス（１．２．２．１）を持つユーザ端末ＰＣ４０１−１が接続されている。また、セグメント２の下の階層に、上位２つの数値が２．１であるネットワーク・アドレスを持つセグメント５があり、更にその下に上位３つの数値が２．１．２であるネットワーク・アドレスを持つセグメント７があり、更にその中にネットワーク・アドレス（２．１．２．３）を持つユーザ端末ＰＣ４０１−２が接続されている。また、セグメント３の下の階層に、上位２つの数値が３．１であるネットワーク・アドレスを持つセグメント８がある。図に例示されているアドレスにおいて、＊はドント・ケアを意味する。
各セグメントは、ネットワークに参加しているユーザ端末間の通信データの転送を制御するためにネットワーク機器を有している。図２４の構成例では、セグメント１はネットワーク機器４００−１を、セグメント２はネットワーク機器４００−２を、セグメント３はネットワーク機器４００−３を、セグメント４はネットワーク機器４００−４を、セグメント５はネットワーク機器４００−５を、セグメント６はネットワーク機器４００−６を、セグメント７はネットワーク機器４００−７を、セグメント８はネットワーク機器４００−８を、それぞれ有している。セグメントが有するネットワーク機器は、そのネットワーク機器に接続されているユーザ端末または他のネットワーク機器から入力された通信データを、通信データに付随する転送先アドレスとネットワーク機器の接続関係を基に最適な転送ルートを計算し、その最適なルートを経由して転送先にデータを転送する機能を有する。図２４の構成例では、各ネットワーク機器はそのセグメント直下のネットワーク機器またはユーザ端末と接続されている。また、ネットワーク機器４００−３は、ネットワーク機器４００−１、ネットワーク機器４００−６、ネットワーク機器４００−２、ネットワーク機器４００−７とも接続している。
これら各ネットワーク・アドレスは、その各桁を４進数で表現した全体で８ビットのビット列で表現されるものと仮定する。例えば、４進表記のネットワーク・アドレス（１．２．＊．＊）はビット列（０１．１０．００．００）で表現される。以降、この表現のビット列を記憶データと呼ぶ。ここで、ネットワーク・アドレスの中の＊はドント・ケアであるので、対応する記憶データ“０１．１０．００．００”のビット列の上位４ビットが有効であり、それ以下のビットは無効であることを示す必要がある。そこで、マスク情報と呼ばれる情報を記憶データと、対にして記憶させている。以降、この対を構造化データと呼ぶ。前記の例では、ビット列“１１．１１．００．００”で表現される。ここで、“１”がマスク無効状態を、“０”がマスク有効状態を示している。マスク有効状態となっているマスク情報に対応する記憶データのビットには、記憶データの無効状態“０”を格納することにする。
各セグメントに入力された通信データに対してネットワーク機器が有する通信データ制御機能としては、通信データに付随する送出元ネットワーク・アドレスと宛先ネットワーク・アドレスおよびあらかじめ設定されている転送規則を基に転送の可否を計算する機能や、前記宛先アドレスとネットワーク機器の接続関係を基に最適な転送ルートを計算し転送先ネットワーク・アドレスを生成する機能などがある。
例えば、図２４において４進表記の宛先ネットワーク・アドレスがＰＣ４０１−２に対応する（２．１．２．３）であるような通信データを、ネットワーク機器４００−３が転送する場合、図から明らかに分かるように、４進表記のネットワーク・アドレス（２．＊．＊．＊）に対応するネットワーク機器４００−２に転送するよりも、４進表記のネットワーク・アドレス（２．１．２．＊）に対応するネットワーク機器４００−７に転送する方が、最適である。つまり、マスク情報を考慮して宛先ネットワーク・アドレスと比較した結果一致するネットワーク・アドレスに対応するネットワーク機器の中で、そのネットワーク・アドレスにおけるマスク有効状態のビット数が最も少ないマスク情報を持つ、ネットワーク機器を選ぶのが最適である。
このように、各ユーザ端末同士を直接通信回線で接続するのではなくネットワーク機器により通信データの転送を制御して通信を行うことにより、有限の通信回線を、安全性を確保しながら効率よく使用している。
次に図面を参照して、従来のネットワーク機器の説明を行う。図２５は従来のネットワーク機器の一構成例を示すブロック図である。図２５では従来のネットワーク機器４００について、図２４のネットワーク機器４００−３に適用した場合を例にして、その構成と動作を説明する。
ネットワーク機器４００は、入力通信データ４０７を入力とし、出力通信データ４０８を出力する。入力通信データ４０７は、送出元ネットワーク・アドレス４０９と、転送先ネットワーク・アドレス４１０と、宛先ネットワーク・アドレス４１１を有している。出力通信データ４０８は、送出元ネットワーク・アドレス４０９と、第２の転送先ネットワーク・アドレス４１２と、宛先ネットワーク・アドレス４１１を有している。図２５では従来のネットワーク機器４００を、図２４のネットワーク機器４００−３に適用した場合を例にして説明するので、入力通信データ４０７の転送先ネットワーク・アドレス４１０は当然ネットワーク機器４００−３のネットワーク・アドレスとなっている。
ネットワーク機器４００は、宛先ネットワーク・アドレス抽出部４０５と、連想メモリ３００と、エンコーダ３０８と、転送先ネットワーク・アドレス格納メモリ４０２と、転送先ネットワーク・アドレス変更部４０６と、により構成される。宛先ネットワーク・アドレス抽出部４０５は、入力通信データ４０７の宛先ネットワーク・アドレス４１０を抽出し、検索データ３０７として連想メモリ３００に入力する。
ネットワーク機器４００には、ネットワーク中でネットワーク機器４００に接続されているネットワーク機器の中で、自分自身が属するセグメントの外部にあるネットワーク機器の属するセグメントのネットワーク・アドレスを、連想メモリ３００の連想メモリ・ワード３０５−０〜３０５−３にそれぞれ格納している。図２５では従来のネットワーク機器４００を、図２４のネットワーク機器４００−３に適用した場合を例にして説明しているので、連想メモリ・ワード３０５−０には、ネットワーク機器４００−１が属するセグメント１の４進表記のネットワーク・アドレス（１．＊．＊．＊）を前述のように記憶データ“０１．００．００．００”とマスク情報“１１．００．００．００”の対で表現される構造化データの形式で記憶している。同様に、連想メモリ・ワード３０５−１にはネットワーク機器４００−２が属するセグメント２の４進表記のネットワーク・アドレス（２．＊．＊．＊）を、連想メモリ・ワード３０５−２にはネットワーク機器４００−６が属するセグメント６の４進表記のネットワーク・アドレス（１．２．２．＊）を、連想メモリ・ワード３０５−３にはネットワーク機器４００−７が属するセグメント７の４進表記のネットワーク・アドレス（２．１．２．＊）を記憶している。連想メモリ３００は、通常のメモリと同様にアドレスを指定して記憶データの書き込み、読み出しを行う機能のほかに、対応するマスク情報を考慮して入力された検索データ３０７と比較した結果一致する記憶データの中でマスク情報のマスク有効状態のビットが最も少ない記憶データに対応する一致線３０１−０〜３０１−３を有効状態にする機能を有している。この機能は、構造化データの形式の定義より、対応するマスク情報を考慮して入力された検索データ３０７と比較した結果、一致する記憶データの中で記憶データの無効状態のビットが最も少ない記憶データに対応する一致線３０１−０〜３０１−３を有効状態にする機能と同等である。従来、この種の連想メモリ３００としては、例えば、特願２０００−１８１４０６、特願２０００−２４３４８５、国際出願番号ＰＣＴ／ＪＰ０１／０３５６２がある。
連想メモリ３００が出力した一致線３０１−０〜３０１−３はエンコーダ３０８によりアドレス出力信号３０９に符号化される。転送先ネットワーク・アドレス格納メモリ４０２には、連想メモリ３００の各連想メモリ・ワード３０５−０〜３０５−３に構造化データの形式で格納されているセグメントのネットワーク・アドレスに対応するネットワーク機器のネットワーク・アドレスを、連想メモリ３００の格納アドレスと同一のアドレスのメモリ・ワード４０３−０〜４０３−３に記憶させてある。たとえば、連想メモリ３００の連想メモリ・ワード３０５−０には４進表記のアドレス（１．＊．＊．＊）が記憶されているが、これに対応する図２４のネットワーク機器４００−１のネットワーク・アドレスが転送先ネットワーク・アドレス格納メモリ４０２のメモリ・ワード４０３−０に格納されている。同様に転送先ネットワーク・アドレス格納メモリ４０２のメモリ・ワード４０３−１にはネットワーク機器４００−２のアドレスが、メモリ・ワード４０３−２にはネットワーク機器４００−６のアドレスが、メモリ・ワード４０３−３にはネットワーク機器４００−７のアドレスが格納されている。転送先ネットワーク・アドレス格納メモリ４０２はアドレス出力信号３０９をリード・アドレスとして指定される格納データを、メモリ・データ信号４０４として出力する。
転送先ネットワーク・アドレス変更部４０６は、入力通信データ４０７の転送先ネットワーク・アドレス４１０をメモリ・データ信号４０４に応じて第２の転送先ネットワーク・アドレス４１２に変更し、出力通信データ４０８として第２の転送先ネットワーク・アドレス４１２に対応するネットワーク機器に向けて転送を行う。
たとえば入力通信データ４０７の４進表記の宛先ネットワーク・アドレス４１１が（１．２．２．１）の場合、連想メモリ３００での検索動作終了時には、連想メモリ・ワード３０５−２が格納している４進表記の（１．２．２．＊）に対応する一致線３０１−２のみが有効状態となる。これにより、エンコーダ３０８はアドレス出力信号３０９として１０進表記で“２”を出力し、転送先ネットワーク・アドレス格納メモリ４０２はネットワーク機器４００−６のネットワーク・アドレスをメモリ・データ信号４０４として出力する。転送先ネットワーク・アドレス変更部４０６により、出力通信データ４０８の第２の転送先ネットワーク・アドレス４１２としてネットワーク機器４００−６のネットワーク・アドレスを設定し、ネットワーク機器４００−６に向けて出力通信データ４０８を転送する。
〔従来の連想メモリの説明〕
図２３は、従来の連想メモリの一構成例を示すブロック図である。図２３では、図２４のネットワーク機器４００−３に適用した場合を例にして、その構成と動作を説明する。したがって、連想メモリ３００は８ビット４語の構成と仮定する。
連想メモリ３００は、８ビット４語構成の１次検索用連想メモリ３０２と、８ビット４語構成の２次検索用連想メモリ３０３とから構成される。１次検索用連想メモリ３０２は、各８ビットの記憶データおよびマスク情報から構成される構造化データを格納できる１次連想メモリ・ワード３０５−０〜３０５−３を有する。ここで、構造化データのドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態とし、マスク情報の該当ビットをマスク・データの有効状態とすることにより表現される。１次検索用連想メモリ３０２は、対応するマスク情報を考慮して検索データ３０７と比較した結果一致する記憶データを検索する１次検索を行い、一致した記憶データ同士に対して記憶データの有効状態を真とした論理和演算を行い、得られた値を中間データ３０４−１〜３０４−８として出力する。２次検索用連想メモリ３０３は、対応する１次連想メモリ・ワード３０５−０〜３０５−３に格納されている８ビットの記憶データと同じ値を２次記憶データとして格納している連想メモリ・ワード３０６−０〜３０６−３を有し、８ビットの中間データ３０４−１〜３０４−８と一致する２次記憶データを検索する２次検索を行い、一致する２次記憶データを格納している連想メモリ・ワード３０６−０〜３０６−３に対応する一致線３０１−０〜３０１−３を有効状態にする。一致線３０１−０〜３０１−３はエンコーダ３０８により、図示しないメモリをアクセスするためのアドレス出力信号３０９に符号化される。なお、エンコーダ３０８はプライオリティ機能を有する必要はない。
なお、本例では、マスク情報の有効状態を“０”、無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”とする。記憶データと同様に、中間データ３０４−１〜３０４−８の有効状態を“１”、無効状態を“０”とする。一致線３０１−０〜３０１−３の有効状態を“１”、無効状態を“０”とする。
ここで、１次検索用連想メモリ３０２の各１次連想メモリ・ワード３０５−０〜３０５−３に格納されている記憶データ、マスク情報には、図２５と同様にネットワーク機器４００−３の４進表記のネットワーク・アドレス（３．＊．＊．＊）以外の接続情報を記憶しているものとする。このとき、接続情報の中のドント・ケア“＊”状態のビットは、マスク情報の該当ビットをマスク情報の有効状態“０”とすることで表現される。記憶データの該当ビットには、記憶データの無効状態“０”を格納する。
つまり、１次連想メモリ・ワード３０５−０には４進表記の（１．＊．＊．＊）を表現するため、記憶データには２進表記で“０１．００．００．００”を、マスク情報として“１１．００．００．００”を格納してある。同様に１次連想メモリ・ワード３０５−１には４進表記の（２．＊．＊．＊）を表現するため、記憶データには２進表記で“１０．００．００．００”を、マスク情報として“１１．００．００．００”を格納してある。１次連想メモリ・ワード３０５−２には４進表記の（１．２．２．＊）を表現するため、記憶データには２進表記で“０１．１０．１０．００”を、マスク情報として“１１．１１．１１．００”を格納してある。１次連想メモリ・ワード３０５−３には４進表記の（２．１．２．＊）を表現するため、記憶データには２進表記で“１０．０１．１０．００”を、マスク情報として“１１．１１．１１．００”を格納してある。
１次検索用連想メモリ３０２は、対応するマスク情報を考慮して比較した結果、外部から入力された検索データ３０７と一致する記憶データを１次連想メモリ・ワード３０５−０〜３０５−３の中で検索する１次検索を行う。前記の従来のネットワーク機器の動作説明と同様に、図２３では検索データ３０７として図２４のＰＣ４０１−２の４進表記のネットワーク・アドレス（１．２．２．１）を入力した場合の動作を示す。このとき１次検索の結果として、１次連想メモリ・ワード３０５−０に格納されている４進表記の（１．＊．＊．＊）と、１次連想メモリ・ワード３０５−２に格納されている４進表記の（１．２．２．＊）が検索データ３０７と一致する。１次検索用連想メモリ３０２は、検索データ３０７と一致する１次連想メモリ・ワード３０５−０、３０５−２の中に格納されている２進表記の記憶データ“０１．００．００．００”、“０１．１０．１０．００”に対し、記憶データの有効状態を真とした論理和演算を行い、得られた８ビットの値“０１．１０．１０．００”を中間データ３０４−１〜３０４−８として出力する。
２次検索用連想メモリ３０３の各連想メモリ・ワード３０６−０〜３０６−３に格納する２次記憶データとして、１次検索用連想メモリ３０２の対応する１次連想メモリ・ワード３０５−０〜３０５−３に格納されている記憶データと、同じ値を格納する。つまり２進表記で、連想メモリ・ワード３０６−０には“０１．００．００．００”を、連想メモリ・ワード３０６−１には“１０．００．００．００”を、連想メモリ・ワード３０６−２には“０１．１０．１０．００”を、連想メモリ・ワード３０６−３には“１０．０１．１０．００”を、それぞれ格納してある。
２次検索用連想メモリ３０３は、１次検索用連想メモリ３０２から入力された中間データ３０４−１〜３０４−８の２進表記の状態“０１１０１０００”と全ビットが一致する２次記憶データを連想メモリ・ワード３０６−０〜３０６−３の中で検索する２次検索を実行する。本例では、連想メモリ・ワード３０６−２が格納する２次記憶データが完全に一致し、対応する一致線３０１−２に有効状態“１”を出力する。不一致であった残りの一致線３０１−０、３０１−１、および３０１−３には無効状態“０”を出力する。エンコーダ３０８は、連想メモリ３００から入力される一致線３０１−０〜３０１−３の状態“０１００”を符号化した結果、２進表記の“１０”、１０進表記の“２”をアドレス出力信号３０９として出力する。
したがって、連想メモリ３００は、対応するマスク情報を考慮して入力された検索データ３０７と比較した結果一致する記憶データの中で、マスク情報の有効状態のビットが最も少ない記憶データ、したがって対応するマスク情報を考慮して入力された検索データ３０７と比較した結果一致する記憶データの中で記憶データの無効状態のビットが最も少ない記憶データに対応する一致線３０１−２のみに有効状態を出力することができる。そのため、プライオリティ機能のないエンコーダ３０８を用いてもアドレス出力信号３０９として１０進表記の“２”が正しく得られることが分かる。また、上述のように構造化データをソートすることなしにランダムな順番で１次連想メモリ・ワード３０５−０〜３０５−３に格納しているが、格納する順番によらずに正しい結果が得られていることも分かる。
従来の連想メモリ３００では次に示すように、格納容量を増大するために連想メモリ３００を複数接続した場合、構造化データをソート処理して格納し、かつプライオリティ・エンコーダを用いなければ正しいアドレス出力信号を得ることができない。
図２６は、従来の連想メモリ３００−０、３００−１を接続したときの第１の構成例と動作例を示すブロック図である。本例では図２３の説明と同様に、連想メモリ３００−０、３００−１は、それぞれ８ビット４語構成とし、連想メモリ３００−１が上位側のアドレス空間を占めることとする。したがって、全体で８語の容量があることになる。
検索データ３０７は接続されているすべての連想メモリ３００−０、３００−１に入力される。連想メモリ３００−０は一致線３０１−０−０〜３０１−３−０を、連想メモリ３００−１は一致線３０１−０−１〜３０１−３−１を、それぞれプライオリティ機能のないエンコーダ３１０に出力する。エンコーダ３１０は一致線３０１−０−０〜３０１−３−１を図示しないメモリをアクセスするためのアドレス出力信号３０９に符号化する。
連想メモリ３００−０は１次検索用連想メモリ３０２−０と２次検索用連想メモリ３０３−０から構成され、１次検索用連想メモリ３０２−０から中間データ３０４−１−０〜３０４−８−０が２次検索用連想メモリ３０３−０に出力される。１次検索用連想メモリ３０２−０が有する１次連想メモリ・ワード３０５−０−０〜３０５−３−０には、図２３の説明と同様に４進表記の構造化データとしてそれぞれ（１．＊．＊．＊）、（２．＊．＊．＊）、（１．２．２．＊）、（２．１．２．＊）を表現するように、記憶データ、マスク情報が格納されているものとする。また、２次検索用連想メモリ３０３−０が有する連想メモリ・ワード３０６−０−０〜３０６−３−０には、図２３の説明と同様に、１次検索用連想メモリ３０２−０の対応する１次連想メモリ・ワード３０５−０−０〜３０５−３−０が格納している記憶データと同じ４進表記の値、（１．０．０．０）、（２．０．０．０）、（１．２．２．０）、（２．１．２．０）を２次記憶データとして格納しているものとする。
連想メモリ３００−１は１次検索用連想メモリ３０２−１と２次検索用連想メモリ３０３−１から構成され、１次検索用連想メモリ３０２−１から中間データ３０４−１−１〜３０４−８−１が２次検索用連想メモリ３０３−１に出力される。図２４に示すネットワーク接続図には記載されていないが説明のため、１次検索用連想メモリ３０２−１が有する１次連想メモリ・ワード３０５−０−１〜３０５−３−１には、４進表記の構造化データとしてそれぞれ（３．１．＊．＊）、（１．２．＊．＊）、（２．１．＊．＊）、（３．＊．＊．＊）を表現するように、記憶データ、マスク情報が格納されているものとする。また、２次検索用連想メモリ３０３−１が有する連想メモリ・ワード３０６−０−１〜３０６−３−１には、１次検索用連想メモリ３０２−１の対応する１次連想メモリ・ワード３０５−０−１〜３０５−３−１が格納している記憶データと同じ４進表記の値、（３．１．０．０）、（１．２．０．０）、（２．１．０．０）、（３．０．０．０）を２次記憶データとして格納しているものとする。
ここで検索データ３０７として図２４に示すＰＣ４０１−２の４進表記のネットワーク・アドレス（２．１．２．３）を入力した場合の動作について説明する。
連想メモリ３００−０では、まず１次検索用連想メモリ３０２−０が、対応するマスク情報を考慮して検索データ３０７と比較した結果一致する記憶データを検索する１次検索を行い、結果として１次連想メモリ・ワード３０５−１−０、３０５−３−０に格納されている４進表記の構造化データ（２．＊．＊．＊）、（２．１．２．＊）が一致する。１次検索用連想メモリ３０２−０は、一致した１次連想メモリ・ワード３０５−１−０、３０５−３−０の中に格納されている４進表記の記憶データ（２．０．０．０）、（２．１．２．０）に対して記憶データの有効状態を真とした論理和演算を行い、得られた４進表記で（２．１．２．０）の８ビットの演算結果を、中間データ３０４−１−０〜３０４−８−０として２次検索用連想メモリ３０３−０に出力する。２次検索用連想メモリ３０３−０は、中間データ３０４−１−０〜３０４−８−０と完全に一致する２次記憶データを検索する２次検索を行い、結果として連想メモリ・ワード３０６−３−０に格納されている２次記憶データのみが一致する。２次検索用連想メモリ３０３−０は、対応する一致線３０１−３−０に有効状態“１”を出力し、他の一致線３０１−０−０、３０１−１−０、３０１−２−０には無効状態“０”を出力する。このように連想メモリ３００−０単体としては、入力された検索データ３０７と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報の有効状態のビットが最も少ない記憶データに対応する一致線３０１−３−０のみに有効状態を出力していることになる。
連想メモリ３００−１では、まず１次検索用連想メモリ３０２−１が、対応するマスク情報を考慮して検索データ３０７と比較した結果一致する記憶データを検索する１次検索を行い、結果として１次連想メモリ・ワード３０５−２−１に格納されている４進表記の構造化データ（２．１．＊．＊）が一致する。１次検索用連想メモリ３０２−１は、一致した１次連想メモリ・ワード３０５−２−１の中に格納されている４進表記の記憶データ（２．１．０．０）を中間データ３０４−１−１〜３０４−８−１として２次検索用連想メモリ３０３−１に出力する。２次検索用連想メモリ３０３−１は中間データ３０４−１−１〜３０４−８−１と完全に一致する２次記憶データを検索する２次検索を行い、結果として連想メモリ・ワード３０６−２−１に格納されている２次記憶データのみが一致する。２次検索用連想メモリ３０３−１は、対応する一致線３０１−２−１に有効状態“１”を出力し、他の一致線３０１−０−１、３０１−１−１、３０１−３−１には無効状態“０”を出力する。このように連想メモリ３００−１単体としては、入力された検索データ３０７と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報の有効状態のビットが最も少ない記憶データに対応する一致線３０１−２−１のみに有効状態を出力していることになる。
ここでエンコーダ３１０に入力されている一致線３０１−０−０〜３０１−３−１のうち、一致線３０１−３−０、３０１−２−１の２本が有効状態“１”となっている。したがって、プライオリティ機能を有しないエンコーダ３１０はアドレス出力信号３０９として“不定”を出力することになる。エンコーダ３１０が上位側アドレスを優先するプライオリティ機能を有していると仮定しても、アドレス出力信号３０９として、２進表記で“１１０”、１０進表記で“６”を出力することになる。これらは図から明らかに分かる最適な４進表記の構造化データ（２．１．２．＊）を格納している１次連想メモリ・ワード３０５−３−０に対応する値、２進表記で“０１１”とは異なり、不正な状態を示している。したがって、図２６に示す従来の連想メモリを複数接続するときの第１の構成例のように、構造化データをソート処理することなしにランダムな順番で１次連想メモリ・ワード３０５−０−０〜３０５−３−１に格納した場合には、正しい結果を得ることができないことが分かる。
図２７は従来の連想メモリ３００−０、３００−１を複数接続するときの第２の構成例と動作例を示すブロック図である。本例では図２６の説明と同様に、連想メモリ３００−０、３００−１は、それぞれ８ビット４語構成とし、連想メモリ３００−１が上位側のアドレス空間を占めることとする。
図２６と同様に、検索データ３０７は接続されているすべての連想メモリ３００−０、３００−１に入力される。連想メモリ３００−０は一致線３０１−０−０〜３０１−３−０を、連想メモリ３００−１は一致線３０１−０−１〜３０１−３−１を、それぞれアドレス信号生成部３１９に出力する。アドレス信号生成部３１９は、一致線３０１−０−０〜３０１−３−１を図示しないメモリをアクセスするためのアドレス出力信号３０９に符号化する。
連想メモリ３００−０、３００−１は、図２６とまったく同様に構成される。ただし、構造化データは、記憶データの値を数値とみなして小さい順から大きい順にソート処理を行った結果の順番に従って１次連想メモリ・ワード３０５−０−０〜３０５−３−１に格納するものとする。図２６と同様の８個の構造化データを例とすると、１次連想メモリ・ワード３０５−０−０には記憶データが４進表記で（１．０．０．０）と最小である４進表記の構造化データ（１．＊．＊．＊）を表現する記憶データ、マスク情報を格納する。以下、順番に１次連想メモリ・ワード３０５−１−０には４進表記の構造化データ（１．２．＊．＊）を、１次連想メモリ・ワード３０５−２−０には４進表記の構造化データ（１．２．２．＊）を、１次連想メモリ・ワード３０５−３−０には４進表記の構造化データ（２．＊．＊．＊）を、１次連想メモリ・ワード３０５−０−１には４進表記の構造化データ（２．１．＊．＊）を、１次連想メモリ・ワード３０５−１−１には４進表記の構造化データ（２．１．２．＊）を、１次連想メモリ・ワード３０５−２−１には４進表記の構造化データ（３．＊．＊．＊）を、１次連想メモリ・ワード３０５−３−１には４進表記の構造化データ（３．１．＊．＊）を、それぞれ表現する記憶データ、マスク情報を格納する。
２次検索用連想メモリ３０３−０、３０３−１の連想メモリ・ワード３０６−０−０〜３０６−３−１には、対応する１次検索用連想メモリ３０２−０、３０２−１の１次連想メモリ・ワード３０５−０−０〜３０５−３−１に格納されている記憶データと同じ値を、２次記憶データとして格納する。したがって、連想メモリ・ワード３０６−０−０〜３０６−３−１には順番に４進表記で（１．０．０．０）、（１．２．０．０）、（１．２．２．０）、（２．０．０．０）、（２．１．０．０）、（２．１．２．０）、（３．０．０．０）、（３．１．０．０）を、それぞれ格納する。
アドレス信号生成部３１９では、連想メモリ３００−ｋ（ｋ＝０，１）ごとに一致線３０１−０−ｋ〜３０１−３−ｋを入力とするエンコーダ３１１−ｋと一致検出手段３１３−ｋを有し、またプライオリティ・エンコーダ３１５と選択手段３１６を有している。
エンコーダ３１１−ｋは、入力された一致線３０１−０−ｋ〜３０１−３−ｋを符号化し、その結果を一致アドレス信号３１２−ｋとして選択手段３１６に出力する。
一致検出手段３１３−ｋは、入力された一致線３０１−０−ｋ〜３０１−３−ｋに有効状態の信号が一つでも含まれる場合には一致検出信号３１４−ｋに一致線の有効状態“１”を出力し、それ以外の場合には一致検出信号３１４−ｋに一致線の無効状態“０”を出力する。一致検出手段３１３−ｋは、例えば一致線の有効状態を真とした論理和演算器で構成することができる。
プライオリティ・エンコーダ３１５は、一致検出信号３１４−０〜３１４−１を入力とし、符号化した結果を上位アドレス信号３１７として選択手段３１６に出力するとともにアドレス信号生成部３１９の外部にも出力する。一致検出信号３１４−０〜３１４−１の中に有効状態の信号が２つ以上ある場合には、アドレス空間で上位側に割り当てられている連想メモリ３００に対応する一致検出信号３１４を優先する。
選択手段３１６は、入力された一致アドレス信号３１２−０〜３１２−１の中から、プライオリティ・エンコーダ３１６から入力された上位アドレス信号３１７に対応する一致アドレス信号３１２を選択し、下位アドレス信号３１８としてアドレス信号生成部３１９の外部に出力する。
アドレス信号生成部３１９から出力された上位アドレス信号３１７、下位アドレス信号３１８は、それぞれアドレス出力信号３０９の上位側、下位側として連結され、図示しないメモリをアクセスするためのアドレス信号となる。
ここで検索データ３０７として、図２６の説明と同様に、図２４に示すＰＣ４０１−２の４進表記のネットワーク・アドレス（２．１．２．３）を入力した場合の動作について説明する。
連想メモリ３００−０では、まず１次検索用連想メモリ３０２−０が、対応するマスク情報を考慮して検索データ３０７と比較した結果一致する記憶データを検索する１次検索を行い、結果として１次連想メモリ・ワード３０５−３−０に格納されている４進表記の構造化データ（２．＊．＊．＊）が検索データ３０７と一致する。１次検索用連想メモリ３０２−０は、一致した１次連想メモリ・ワード３０５−３−０の中に格納されている４進表記の記憶データ（２．０．０．０）を中間データ３０４−１−０〜３０４−８−０として２次検索用連想メモリ３０３−０に出力する。２次検索用連想メモリ３０３−０は、中間データ３０４−１−０〜３０４−８−０と完全に一致する２次記憶データを検索する２次検索を行い、結果として連想メモリ・ワード３０６−３−０に格納されている２次記憶データのみが中間データ３０４−１−０〜３０４−８−０と一致する。２次検索用連想メモリ３０３−０は、対応する一致線３０１−３−０に有効状態“１”を出力し、他の一致線３０１−０−０、３０１−１−０、３０１−２−０には無効状態“０”を出力する。このように連想メモリ３００−０単体としては、入力された検索データ３０７と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報の有効状態のビットが最も少ない記憶データに対応する一致線３０１−３−０のみに有効状態を出力していることになる。
連想メモリ３００−１では、まず１次検索用連想メモリ３０２−１が、対応するマスク情報を考慮して検索データ３０７と比較した結果一致する記憶データを検索する１次検索を行い、結果として１次連想メモリ・ワード３０５−０−１、３０５−１−１に格納されている４進表記の構造化データ（２．１．＊．＊）、（２．１．２．＊）が検索データ３０７と一致する。１次検索用連想メモリ３０２−１は、一致した１次連想メモリ・ワード３０５−０−１、３０５−１−１の中に格納されている４進表記の記憶データ（２．１．０．０）、（２．１．２．０）に対して記憶データの有効状態を真とした論理和演算を行い、得られた４進表記で（２．１．２．０）の８ビットの演算結果を、中間データ３０４−１−１〜３０４−８−１として２次検索用連想メモリ３０３−１に出力する。２次検索用連想メモリ３０３−１は、中間データ３０４−１−１〜３０４−８−１と完全に一致する２次記憶データを検索する２次検索を行い、結果として連想メモリ・ワード３０６−１−１に格納されている２次記憶データのみが中間データ３０４−１−１〜３０４−８−１と一致する。２次検索用連想メモリ３０３−１は、対応する一致線３０１−１−１に有効状態“１”を出力し、他の一致線３０１−０−１、３０１−２−１、３０１−３−１には無効状態“０”を出力する。このように連想メモリ３００−１単体としては、入力された検索データ３０７と、対応するマスク情報を考慮して比較した結果一致する記憶データの中で、マスク情報の有効状態のビットが最も少ない記憶データに対応する一致線３０１−１−１のみに有効状態を出力していることになる。
ここでアドレス信号生成部３１９に入力されている一致線３０１−０−０〜３０１−３−０の中では一致線３０１−３−０のみが有効状態“１”となっており、一致線３０１−０−１〜３０１−３−１の中では３０１−１−１のみが有効状態“１”となっている。したがって、連想メモリ３００−０に対応するプライオリティ機能を有しないエンコーダ３１１−０は一致アドレス信号３１２−０として２進表記で“１１”を選択手段３１６に出力し、一致検出手段３１３−０は一致検出信号３１４−０に有効状態“１”を出力する。連想メモリ３００−１に対応するプライオリティ機能を有しないエンコーダ３１１−１は一致アドレス信号３１２−１として２進表記で“０１”を選択手段３１６に出力し、一致検出手段３１３−１は一致検出信号３１４−１に有効状態“１”を出力する。
プライオリティ・エンコーダ３１５に入力されている一致検出信号３１４−０〜３１４−１の中で一致検出信号３１４−０、３１４−１の２本が有効状態“１”であるため、アドレス空間で上位側に割り当てられている連想メモリ３００−１に対応する一致検出信号３１４−１を、プライオリティ・エンコーダ３１５は優先する。その結果２進表記で“１”を、上位アドレス信号３１７として選択手段３１６に出力するとともに、アドレス信号生成部３１９の外部にも出力する。
選択手段３１６は、プライオリティ・エンコーダ３１５から入力された上位アドレス信号３１７が２進表記で“１”であるため、対応する２進表記で“０１”の一致アドレス信号３１２−１を選択し、下位アドレス信号３１８としてアドレス信号生成部３１９の外部に出力する。
アドレス信号生成部３１９から出力された２進表記でそれぞれ“１”、“０１”の上位アドレス信号３１７、下位アドレス信号３１８は、それぞれアドレス出力信号３０９の上位側、下位側として連結され２進表記で“１０１”となる。つまり、従来の連想メモリを複数接続するときの第２の構成例では図２６と異なり、最適な４進表記の構造化データ（２．１．２．＊）を格納している１次連想メモリ・ワード３０５−１−１に対応する値、２進表記で“１０１”が、アドレス出力信号３０９として正しく得られている。
したがって、連想メモリ３００単体の場合には、構造化データをソート処理することなしにランダムな順番で１次連想メモリ・ワード３０５に格納しても正しい検索結果が得られるにもかかわらず、記憶容量を増大させるために連想メモリ３００を複数接続する場合には、図示しないＣＰＵなどにより構造化データの記憶データの値を数値とみなして小さい順から大きい順にソート処理を行った結果の順番に従って構造化データを１次連想メモリ・ワード３０５に格納しなければならない。
ここで、例えば図２５に示す転送先アドレス計算に連想メモリ３００を使用する場合、ネットワーク機器同士の接続追加、接続切断などの接続状況の変更は頻繁に行われているので、これらを反映させるためネットワーク機器同士が一定周期で接続状況を交信しあい、連想メモリ３００に格納している構造化データを最新の状況に更新する必要がある。ところが、例えばインターネットの場合、接続状況は１０万ワード以上にもなり、ソート処理実行には高速なＣＰＵを用いても数秒を要し、そのネットワーク機器は、ソート処理実行期間中は転送処理が実行できないという問題があった。
また、連想メモリ３００を複数接続するときには、連想メモリ３００単体で使用時には不要であった高価な高速ＣＰＵシステムを搭載しなければならず、ネットワーク機器全体としての価格が上昇してしまうという問題があった。
また、アドレス信号生成部３１９に、１本の一致線３０１でも有効状態を出力している連想メモリ３００の中で、アドレス空間において上位のアドレスを占める連想メモリ３００を識別するための上位アドレス信号３１７を生成するためにはプライオリティ・エンコーダ３１５が必要であり、通常のエンコーダに比べて、プライオリティ機能の部分だけ面積が大きくなるとともに、符号化処理時間も著しく長くなってしまう。したがって、ネットワーク機器全体としての価格が上昇するとともに、処理速度も低下してしまうという問題があった。
また、上述のようにソート処理が必要なために、連想メモリ３００を用いたネットワーク機器では、単純に連想メモリ３００を追加するだけでは、記憶容量を増加させることができないという問題点があった。
そこで、本発明の目的は、ソート処理を伴わずに記憶データの書き込み、更新および削除を実行した場合においても、検索時に複数の記憶データが検索データと一致したときに、その中で最適な一つを高速に選択して出力することが可能な、複数個の連想メモリから構成される連想メモリ・システムを提供することである。
更に他の目的として、ネットワーク機器のトータルコストを削減することである。
更に他の目的として、転送動作を中断せずに、連想メモリに格納しているデータの削除、追加、変更を実行することができるネットワーク機器を提供することにある。
更に他の目的として、プライオリティ・エンコーダを必要としないネットワーク機器を提供することにある。
更に他の目的として、記憶容量の増大、減少に合わせて、連想メモリの追加、削除を容易に行うことができるネットワーク機器を提供することにある。
更に他の目的として、高速にデータを転送できるネットワーク・システムを提供することにある。
発明の開示
本発明の連想メモリ・システムは、手段１として、記憶データの１ビットまたは複数ビットごとに検索対象から除外するか否かを、有効状態、無効状態により設定可能なマスク情報を該記憶データの１ワードまたは複数ワードごとに有し、
１ワードごとに該マスク情報がマスク有効状態の場合に対応する該記憶データの１ビットまたは複数ビットを検索対象から除外し、入力された検索データと一致するワードを選択する１次検索を実行する１次検索手段と、
前記１次検索手段における選択されたワードの中で、記憶データの無効状態のビットが最も少ない記憶データの値を、中間データとして出力する中間データ生成手段と、
から構成される１次連想メモリを複数個有する連想メモリ・システムにおいて、
前記複数個の中間データ生成手段が出力する前記中間データの中で、記憶データの無効状態のビットが最も少ない中間データを選択し、最適化中間データとして出力する中間データ演算手段と、
前記複数個の１次検索手段に格納されている前記記憶データの値を格納し、前記最適化中間データと一致する記憶データの値を選択する２次検索を実行する一つ又は複数の２次検索手段と、
２次検索の終了後に選択されている前記記憶データの値に対応する一致信号に有効状態を出力する一致信号出力手段と、
を有するものである。
本発明の連想メモリ・システムは、手段２として、記憶データの１ビットまたは複数ビットごとに検索対象から除外するか否かを、有効状態、無効状態により設定可能なマスク情報を該記憶データの１ワードまたは複数ワードごとに有し、
１ワードごとにマスク情報がマスク有効状態の場合に対応する該記憶データの１ビットまたは複数ビットを検索対象から除外し、入力された検索データと一致するワードを選択する１次検索を実行する１次検索手段と、
前記１次検索手段における該選択されたワードの中で、記憶データの無効状態のビットが最も少ない記憶データの値を中間データとして出力する中間データ生成手段と、
から構成される１次連想メモリを複数個有する連想メモリ・システムにおいて、
前記複数個の１次連想メモリが出力する前記中間データの中で、記憶データの無効状態のビットが最も少ない中間データを出力している１次連想メモリに対応する検出信号のみに有効状態を出力する中間データ判定手段と、
対応する前記１次検索手段に格納されている前記記憶データの値を格納し、該１次検索手段に対応する前記中間データ生成手段が出力する前記中間データと一致する記憶データの値を選択する２次検索を実行する複数の２次検索手段と、
前記各１次連想メモリに対応する前記検出信号が無効状態の場合には対応する一致信号にすべて無効状態を出力し、該検出信号が有効状態の場合には２次検索の終了後に選択されている前記記憶データの値に対応する前記一致信号に有効状態を出力する一致信号出力手段と、を有するものである。
本発明の連想メモリ・システムは、手段３として、記憶データの１ビットまたは複数ビットごとに検索対象から除外するか否かを、有効状態、無効状態により設定可能なマスク情報を該記憶データの１ワードまたは複数ワードごとに有し、
優先順位を有するｋ個（Ｋは２以上の整数）の検索領域から構成される検索データを入力とし、
１ワードごとに前記マスク情報がマスク有効状態の場合に対応する該記憶データの１ビットまたは複数ビットを検索対象から除外し、入力された検索データと一致するワードを選択する１次検索を実行する１次検索手段と、
１次検索の終了後に選択されているワードが格納している記憶データにおける第１の優先順位の検索領域に対応する領域の中で、記憶データの無効状態のビットが最も少ない第１の優先順位の検索領域に対応する領域の記憶データの値を、第１の中間データとして出力する第１の中間データ生成手段と、
第（ｉ−１）の２次検索終了後（ｉは２以上ｋ以下の整数）に選択されているワードが格納している記憶データにおける第ｉの優先順位の検索領域に対応する領域の中で、記憶データの無効状態のビットが最も少ない第ｉの優先順位の検索領域に対応する領域の記憶データの値を、第ｊの中間データとして出力する、第２乃至第ｋの中間データ生成手段と、
から構成される１次連想メモリを複数個有する連想メモリ・システムにおいて、
前記複数個の第ｊの中間データ（ｊは１以上ｋ以下の整数）の中で、記憶データの無効状態のビットが最も少ない第ｊの中間データを選択し、第ｊの最適化中間データとして出力する、第１乃至第ｋの中間データ演算手段と、
前記複数個の１次検索手段に格納されている第ｊの検索領域に対応する領域の記憶データの値を格納し、前記第ｊの最適化中間データと一致する記憶データの値を選択する第ｊの２次検索を実行する、一つ又は複数の第１乃至第ｋの２次検索手段と、
第ｋの２次検索の終了後に選択されている前記記憶データの値に対応する一致信号に有効状態を出力する一致信号出力手段と、を有するものである。
本発明の連想メモリ・システムは、手段４として、前記第１乃至第ｋの２次検索手段において、
該第１乃至第ｋの最適化中間データの中の複数から一つを選択する選択手段と、２次検索の対象とする検索領域を選択する制御手段とを有することにより、
前記２次検索手段、および前記中間データ演算手段の、それぞれ第１乃至第ｋの中の一部または全てを共有するものである。
本発明の連想メモリ・システムは、手段５として、記憶データの１ビットまたは複数ビットごとに検索対象から除外するか否かを、有効状態、無効状態により設定可能なマスク情報を該記憶データの１ワードまたは複数ワードごとに有し、
優先順位を有するｋ個（Ｋは２以上の整数）の検索領域から構成される検索データを入力とし、
１ワードごとに前記マスク情報がマスク有効状態の場合に対応する該記憶データの１ビットまたは複数ビットを検索対象から除外し、入力された検索データと一致するワードを選択する１次検索を実行する１次検索手段と、
１次検索の終了後に選択されているワードが格納している記憶データにおける第１の優先順位の検索領域に対応する領域の中で、記憶データの無効状態のビットが最も少ない第１の優先順位の検索領域に対応する領域の記憶データの値を、第１の中間データとして出力する第１の中間データ生成手段と、
第（ｉ−１）の２次検索終了後（ｉは２以上ｋ以下の整数）に選択されているワードが格納している記憶データにおける第ｉの優先順位の検索領域に対応する領域の中で、記憶データの無効状態のビットが最も少ない第ｉの優先順位の検索領域に対応する領域の記憶データの値を、第ｉの中間データとして出力する第２乃至第ｋの中間データ生成手段と、
から構成される１次連想メモリを複数個有する連想メモリ・システムにおいて、
前記複数個の第ｊの中間データ（ｊは１以上ｋ以下の整数）の中で、対応する第（ｊ−１）の検出信号が有効状態の該第ｊの中間データのみを選択する、第ｊの無効化手段と、
第ｊの無効化手段が選択した複数の第ｊの中間データの中で、記憶データの無効状態のビットが最も少ない第ｊの中間データを出力している１次連想メモリに対応する第ｊの検出信号のみに有効状態を出力する、第１乃至第ｋの中間データ判定手段と、
１次検索開始前にすべての第０の検出信号を有効状態とする初期化手段と、
前記複数個の１次検索手段に格納されている第ｊの検索領域に対応する領域の記憶データの値を格納し、対応する１次連想メモリが出力する前記第ｊの中間データと一致する記憶データの値を選択する第ｊの２次検索を実行する、複数の第１乃至第ｋの２次検索手段と、
各１次連想メモリに対応する第ｋの検出信号が、無効状態の場合には対応する一致信号にすべて無効状態を出力し、有効状態の場合には第ｋの２次検索の終了後に選択されている記憶データの値に対応する前記一致信号に有効状態を出力する一致信号出力手段と、を有するものである。
本発明の連想メモリ・システムは、手段６として、前記第１乃至第ｋの２次検索手段において、
該第１乃至第ｋの中間データの中の複数から一つを選択する選択手段と、２次検索の対象とする検索領域を選択する制御手段とを有し、
各１次連想メモリに対応する前記検出信号が検索開始から有効状態を保持しているか否かを記憶する一つまたは複数の記憶手段を有することにより、
前記２次検索手段、前記無効化手段、および前記中間データ判定手段の、それぞれ第１乃至第ｋの中の一部または全てを共有するものである。
本発明の連想メモリ・システムは、手段７として、前記中間データ判定手段は、
入力された前記中間データの中で、記憶データの無効状態のビットが最少の中間データを選択し、最適化中間データとして出力する中間データ演算手段と、
前記最適化中間データと一致する前記中間データを出力している前記１次連想メモリに対応する前記検出信号のみに有効状態を出力する中間データ比較手段とを有する
本発明の連想メモリ・システムは、手段８として、前記中間データ演算手段は、前記複数の中間データの同一ビット位置同士を記憶データの有効状態を真として論理和演算することにより構成されるものである。
本発明の連想メモリ・システムは、手段９として、前記中間データ演算手段は、記憶データの有効状態を真とする２進表記の数値とみなしたときに、前記複数の中間データの中で最大値を選択するものである。
本発明の連想メモリ・システムは、手段１０として、前記中間データ演算手段は、
対応する前記１次連想メモリが出力する前記中間データの中で記憶データの無効状態のビット数を計数する複数の無効状態計数手段と、
前記複数の無効状態計数手段の計数結果の中で最小値を演算する最小値演算手段と、
前記最小値に対応する該中間データを選択し前記最適化中間データとして出力する選択手段とを、有するものである。
本発明の連想メモリ・システムは、手段１１として、前記中間データ演算手段は、前記複数個の１次連想メモリにおける、前記中間データの出力端子と前記最適化中間データの入力端子を共用するために、前記中間データ同士の、記憶データの有効状態を真とする結線論理和回路により構成するものである。
本発明の連想メモリ・システムは、手段１２として、前記中間データ判定手段は、
前記１次連想メモリが出力する前記中間データの中で記憶データの無効状態のビット数を計数する複数の無効状態計数手段と、
前記複数の無効状態計数手段が出力する計数結果の中で最小値を演算する最小値演算手段と、
前記最小値に対応する該中間データを出力している前記１次連想メモリに対応する検出信号のみに有効状態を出力する最小値比較手段と、
を有するものである。
本発明の連想メモリ・システムは、手段１３として、前記第ｊの無効化手段は、無効状態が入力されている第ｊの検出信号に対応する、第ｊの中間データの全ビットを、すべて記憶データの無効状態に変更する論理積手段により構成されるものである。
本発明の連想メモリ・システムは、手段１４として、前記第ｊの無効化手段、および前記第ｊの中間データ判定手段は、
前記１次連想メモリが出力する前記第ｊの中間データの中で記憶データの無効状態のビット数を計数する複数の無効状態計数手段と、
無効状態が入力されている前記検出信号に対応する無効状態計数手段の計数結果を、前記第ｊの中間データのビット数と等しい数またはビット数より大きい数に変更する手段と、
前記複数の無効状態計数手段が出力する前記計数結果の中で最小値を演算する最小値演算手段と、
前記最小値に対応する中間データを出力している前記１次連想メモリに対応する検出信号のみに有効状態を出力する最小値比較手段と、を有するものである。
本発明の連想メモリ・システムは、手段１５として、前記無効状態計数手段は、記憶データの無効状態のビット数を、前記中間データの一側のビット位置から他側に向かって、最初の記憶データの有効状態のビットが現れるまで計数するものである。
本発明の連想メモリ・システムは、手段１６として、前記無効状態計数手段は、対応する１次連想メモリに内蔵されるものである。
本発明の連想メモリ・システムは、手段１７として、前記中間データ演算手段は、パイプライン処理を実行可能とする記憶手段を有するものである。
本発明の連想メモリ・システムは、手段１８として、前記中間データ判定手段は、該中間データ判定手段が検出信号を出力するタイミングを、並行して実行している２次検索の終了と同期させるための一つまたは複数の手段を有するものである。
本発明の連想メモリ・システムは、手段１９として、前記１次検索手段において、前記記憶データを格納する手段と、前記２次検索手段における該記憶データの値を格納する手段とを共用するものである。
本発明の連想メモリ・システムは、手段２０として、前記連想メモリ・システムにおいて、前記１次連想メモリ毎に対応する前記一致信号に有効状態の信号が含まれるか否かを検出する検出手段を有し、かつ前記一致信号同士を論理和演算する論理和手段と、前記論理和手段の出力をアドレス信号の一つの領域として符号化する第１の符号化手段と、前記検出手段の出力をアドレス信号の他の領域として符号化する第２の符号化手段とを、有するものである。
本発明の連想メモリ・システムは、手段２１として、前記連想メモリ・システムにおいて、前記１次連想メモリ毎に対応する前記一致信号に有効状態の信号が含まれるか否かを検出する検出手段と、該一致信号をアドレス信号の一つの領域として符号化する第１の符号化手段とを有し、前記検出手段の出力を該アドレス信号の他の領域として符号化する第２の符号化手段と、前記各１次連想メモリに対応する前記第１の符号化手段の中から前記第２の符号化手段の演算結果に対応して、前記第１の符号化手段の出力信号を選択するものである。
本発明の連想メモリ・システムは、手段２２として、前記連想メモリ・システムにおいて、前記検出手段と前記第１の符号化手段を対応する１次連想メモリに内蔵するものである。
本発明のネットワーク機器は、手段２３として、手段１から手段２２に記載の連想メモリ・システムを用いて一つまたは複数のネットワーク・アドレスの検索を行うものである。
本発明のネットワーク・システムは、手段２４として、手段２３の前記ネットワーク機器を介してネットワークに接続された機器間でデータ通信を行うものである。
発明を実施するための最良の形態
〔第１の実施例の構成〕
次に、本発明の第１の実施の形態の連想メモリ・システムについて図面を参照して詳細に説明する。以降の説明では、ｎは１以上の整数、ｍ、ｐ、ｑは２以上の整数とし、ｍ、ｐ、ｑよりも１小さい整数をそれぞれｓ、ｒ、ｔで表すこととする。図１は、本発明の第１の実施の形態のｎビット（ｍ×ｐ）語の連想メモリ・システム２００の構成例を示すブロック図である。連想メモリ・システム２００は、ｐ個のｍ語ｎビットの連想メモリ１−０〜１−ｒと、中間データ演算部９と、アドレス信号生成部１１とから構成され、ｎビットの検索データ２を入力とし、アドレス出力信号１２を出力とする。
ｋ番目（ｋは０以上ｒ以下の整数）の連想メモリ１−ｋは、ｎビットｍ語の１次検索用連想メモリ４−ｋと、ｎビットｍ語の２次検索用連想メモリ５−ｋから構成され、ｎビットの検索データ２と、ｎビットの最適化中間データ１０−１〜１０−ｎを入力とし、ｎビットの中間データ６−１−ｋ〜６−ｎ−ｋと、ｍ本の一致線３−０−ｋ〜３−ｓ−ｋを出力とする。
１次検索用連想メモリ４−ｋは、各ｎビットの記憶データおよびマスク情報から構成される構造化データをｍ個格納できる１次連想メモリ・ワード７−０−ｋ〜７−ｓ−ｋを有する。ここで、構造化データのドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態とし、マスク情報の該当ビットをマスク・データの有効状態とすることにより表現される。また、１次検索用連想メモリ４−ｋは、対応するマスク情報を考慮して検索データ２と比較した結果一致する記憶データを検索する１次検索を１次連想メモリ・ワード７−０−ｋ〜７−ｓ−ｋの中で行い、一致する記憶データ同士に対して記憶データの有効状態を真とした論理和演算を行い、得られた値を中間データ６−１−ｋ〜６−ｎ−ｋとして、中間データ演算部９に出力する。つまり、１次検索用連想メモリ４−ｋは、中間データ６−１−ｋ〜６−ｎ−ｋを連想メモリ１−ｋの外部の中間データ演算部９に出力することを除くと、図２３に示した従来の連想メモリ３００の１次検索用連想メモリ３０２と全く同様に構成することができる。
２次検索用連想メモリ５−ｋは、各ｎビットの２次記憶データを格納できる連想メモリ・ワード８−０−ｋ〜８−ｓ−ｋを有する。ここでｉ番目（ｉは０以上ｍ以下の整数）の連想メモリ・ワード８−ｉ−ｋには、対応する１次連想メモリ・ワード７−ｉ−ｋが格納している記憶データと同じ値を２次記憶データとして格納する。２次検索用連想メモリ５−ｋは、中間データ演算部９から入力される最適化中間データ１０−１〜１０−ｎと完全に一致する２次記憶データを検索する２次検索を連想メモリ・ワード８−０−ｋ〜８−ｓ−ｋの中で行い、一致した２次記憶データに対応する一致線３−０−ｋ〜３−ｓ−ｋに一致線の有効状態を出力する。つまり、２次検索用連想メモリ５−ｋは、中間データ６−１−ｋ〜６−ｎ−ｋの代わりに最適化中間データ１０−１〜１０−ｎが入力されることを除くと、図２３に示した従来の連想メモリ３００の２次検索用連想メモリ３０３と全く同様に構成することができる。
したがって、連想メモリ１−ｋは、１次検索終了後に中間データ６−１−ｋ〜６−ｎ−ｋを中間データ演算部９に出力し、２次検索の検索データとして中間データ演算部９から入力される最適化中間データ１０−１〜１０−ｎを用いることを除くと、図２３に示した従来の連想メモリ３００と全く同様に構成することができる。
中間データ演算部９は、ｐ個の連想メモリ１−０〜１−ｒから入力されるｐ個のｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）の中で、最も中間データの無効状態のビット数が少ないものをｎビットの最適化中間データ１０−１〜１０−ｎとして出力する。図１に示す本発明の第１の実施の形態の中間データ演算部９は、入力されたｐ個のｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）の同一ビット位置同士に対して、中間データの有効状態を真とした論理和演算を行った結果を、ｎビットの最適化中間データ１０−１〜１０−ｎとして出力する、論理和手段１３により構成される。
アドレス信号生成部１１は、ｐ個のｍビットの一致線（３−０−０〜３−ｓ−０）〜（３−０−ｒ〜３−ｓ−ｒ）を入力とし、図示しないメモリをアクセスするためのアドレス出力信号１２に符号化して出力する。図１に示す本発明の第１の実施の形態のアドレス信号生成部１１は、図２７に示したアドレス信号生成部３１９と異なり、連想メモリ１−ｋ（ｋは０以上ｒ以下の整数）ごとに一致線３−０−ｋ〜３−ｓ−ｋを入力とする一致検出手段１６−ｋと、すべての一致線（３−０−０〜３−ｓ−０）〜（３−０−ｒ〜３−ｓ−ｒ）を入力とする論理和手段１４と、エンコーダ１８と、エンコーダ２０とを、有している
一致検出手段１６−ｋは、入力された一致線３−０−ｋ〜３−ｓ−ｋに有効状態の信号が一つでも含まれる場合には一致検出信号１７−ｋに一致線の有効状態を出力し、それ以外の場合には一致検出信号１７−ｋに一致線の無効状態を出力する。一致検出手段１６−ｋは、例えば一致線の有効状態を真とした論理和演算器で構成することができる。
論理和手段１４は、入力されたｐ個のｍビットの一致線（３−０−０〜３−ｓ−０）〜（３−０−ｒ〜３−ｓ−ｒ）の同一ビット位置同士に対して、一致線の有効状態を真とした論理和演算を行った結果を、ｍビットの最適一致信号１５−０〜１５−ｓとしてエンコーダ２０に出力する。
エンコーダ２０は、入力された最適一致信号１５−０〜１５−ｓを符号化し、その結果を下位アドレス信号２１としてアドレス信号生成部１１の外部に出力する。以降の説明では、２進数に符号化する場合を例とするが、他の符号化処理でもよいことはいうまでもない。また、図示しないメモリのワード線として直接出力してもよいこともいうまでもない。
エンコーダ１８は、一致検出信号１７−０〜１７−ｒを入力とし、符号化した結果を上位アドレス信号１９としてアドレス信号生成部１１の外部に出力する。以降の説明では、２進数に符号化する場合を例とするが、他の符号化処理でもよいことはいうまでもない。また、図示しないメモリのワード線として直接出力してもよいこともいうまでもない。
アドレス信号生成部１１から出力された上位アドレス信号１９、下位アドレス信号２１は、それぞれ、図示しないメモリをアクセスするためのアドレス出力信号１２の上位側、下位側として連結される。
〔第１の実施例の動作〕
次に図面を参照して、本発明の第１の実施の形態の連想メモリ・システムの動作を説明する。図２は、本発明の第１の実施の形態の連想メモリ・システム２００を、図２６の従来の連想メモリを複数接続するときの第１の構成例の説明と同様に、４語８ビット構成の連想メモリ１−０、１−１を２個を接続し、かつ、構造化データをソート処理することなしにランダムな順番で１次連想メモリ・ワード７−０−０〜７−３−１に格納した場合の動作例を示す図である。ここで、全体で８語のアドレス空間の中で連想メモリ１−１が上位側のアドレス空間を占めることとする。
本例では以降、マスク情報の有効状態を“０”、無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”として説明する。また、記憶データと同様に、中間データ６の有効状態を“１”、無効状態を“０”とする。一致線３の有効状態を“１”、無効状態を“０”として説明する。
１次検索用連想メモリ４−０が有する１次連想メモリ・ワード７−０−０〜７−３−０には、図２６の説明と同様に、４進表記の構造化データとしてそれぞれ（１．＊．＊．＊）、（２．＊．＊．＊）、（１．２．２．＊）、（２．１．２．＊）を表現するように、記憶データ、マスク情報を、ソート処理することなしに格納しているものとする。また、２次検索用連想メモリ５−０が有する連想メモリ・ワード８−０−０〜８−３−０には、図２６の説明と同様に、１次検索用連想メモリ４−０の対応する１次連想メモリ・ワード７−０−０〜７−３−０が格納している記憶データと同じ４進表記の値、（１．０．０．０）、（２．０．０．０）、（１．２．２．０）、（２．１．２．０）を２次記憶データとして格納しているものとする。１次検索用連想メモリ４−１が有する１次連想メモリ・ワード７−０−１〜７−３−１には、図２６の説明と同様に、４進表記の構造化データとしてそれぞれ（３．１．＊．＊）、（１．２．＊．＊）、（２．１．＊．＊）、（３．＊．＊．＊）を表現するように、記憶データ、マスク情報を、ソート処理することなしに格納しているものとする。また、２次検索用連想メモリ５−１が有する連想メモリ・ワード８−０−１〜８−３−１には、図２６の説明と同様に、１次検索用連想メモリ４−１の対応する１次連想メモリ・ワード７−０−１〜７−３−１が格納している記憶データと同じ４進表記の値、（３．１．０．０）、（１．２．０．０）、（２．１．０．０）、（３．０．０．０）を２次記憶データとして格納しているものとする。
ここで図２６の説明と同様に、検索データ２として図２４に示すＰＣ４０１−２の４進表記のネットワーク・アドレス（２．１．２．３）を入力した場合の動作について説明する。
連想メモリ１−０では、まず１次検索用連想メモリ４−０が、対応するマスク情報を考慮して検索データ２と比較したときに一致する記憶データを検索する１次検索を行い、結果として１次連想メモリ・ワード７−１−０、７−３−０に格納されている４進表記の構造化データ（２．＊．＊．＊）、（２．１．２．＊）が検索データ２と一致する。１次検索用連想メモリ４−０は、一致した１次連想メモリ・ワード７−１−０、７−３−０の中に格納されている４進表記の記憶データ（２．０．０．０）、（２．１．２．０）に対して記憶データの有効状態を真とした論理和演算を行い、得られた２進表記で“１０．０１．１０．００”の８ビットの演算結果を、中間データ６−１−０〜６−８−０として中間データ演算部９に出力する。同様に、連想メモリ１−１では、まず１次検索用連想メモリ４−１が、対応するマスク情報を考慮して検索データ２と比較したときに一致する記憶データを検索する１次検索を行い、結果として１次連想メモリ・ワード７−２−１に格納されている４進表記の構造化データ（２．１．＊．＊）が検索データ２と一致する。１次検索用連想メモリ４−１は、一致した１次連想メモリ・ワード７−２−１の中に格納されている４進表記の記憶データ“１０．０１．００．００”を中間データ６−１−１〜６−８−１として中間データ演算部９に出力する。
中間データ演算部９は、中間データ６−１−０〜６−８−０の２進表記の値“１０．０１．１０．００”と、中間データ６−１−１〜６−８−１の２進表記の値“１０．０１．００．００”の中で、最も中間データの無効状態のビット数が少ないものを８ビットの最適化中間データ１０−１〜１０−８として出力する。図１の構成例では、論理和手段１３により、同一ビット位置同士に対して、中間データの有効状態を真とした論理和演算を行い、得られた２進表記の演算結果“１０．０１．００．００”を、８ビットの最適化中間データ１０−１〜１０−８として連想メモリ１−０、１−１に出力する。
２次検索用連想メモリ５−０は、最適化中間データ１０−１〜１０−８と完全に一致する２次記憶データを検索する２次検索を行う。結果として連想メモリ・ワード８−３−０に格納されている２次記憶データのみが一致し、２次検索用連想メモリ５−０は対応する一致線３−３−０に有効状態“１”を出力し、他の一致線３−０−０、３−１−０、３−２−０には無効状態“０”を出力する。同様に、２次検索用連想メモリ５−１は、最適化中間データ１０−１〜１０−８と完全に一致する２次記憶データを検索する２次検索を行う。結果として、すべての連想メモリ・ワード８−０−１〜８−３−１に格納している２次記憶データが不一致となり、２次検索用連想メモリ５−１は、対応するすべての一致線３−０−１〜３−３−１に無効状態“０”を出力する。
したがって、アドレス信号生成部１１には、連想メモリ１−０から一致線３−０−０〜３−３−０として２進表記で“１０００”が入力され、連想メモリ１−１から一致線３−０−１〜３−３−１として２進表記で“００００”が入力されることになる。論理和手段１４は、一致線３−０−０〜３−３−０と一致線３−０−１〜３−３−１の同一ビット位置同士に対して、一致線の有効状態を真とした論理和演算を行い、得られた２進表記の結果“１０００”を、４ビットの最適一致信号１５−０〜１５−３としてエンコーダ２０に出力する。エンコーダ２０は、入力された最適一致信号１５−０〜１５−３を２進数に符号化し、得られた２進表記の結果“１１”を、下位アドレス信号２１としてアドレス信号生成部１１の外部に出力する。
また、一致検出手段１６−０は一致線３−０−０〜３−３−０に有効状態の信号が含まれるので一致検出信号１７−０として有効状態“１”をエンコーダ１８に出力し、一致検出手段１６−１は一致線３−０−１〜３−３−１に有効状態の信号が含まれないので一致検出信号１７−１として無効状態“０”をエンコーダ１８に出力する。エンコーダ１８は、入力された一致検出信号１７−０〜１７−１の２進表記の値“０１”を２進数に符号化し、得られた２進表記の結果“０”を上位アドレス信号１９としてアドレス信号生成部１１の外部に出力する。
アドレス信号生成部１１から出力された２進表記で“０”の上位アドレス信号１９、２進表記で“１１”の下位アドレス信号２１を、それぞれアドレス出力信号１２の上位側、下位側として連結することにより、２進表記で“０１１”のアドレス出力信号１２が得られることになる。
したがって、図１に示す本発明の第１の実施の形態の連想メモリ・システム２００では、構造化データをソート処理することなしにランダムな順番で１次連想メモリ・ワード７−０−０〜７−３−１に格納しているにも関わらず、最適な４進表記の構造化データ（２．１．２．＊）を格納している１次連想メモリ・ワード７−３−０に対応する値、２進表記で“０１１”が、アドレス出力信号１２として正しく得られることが分かる。
また、図２７に示した従来の連想メモリを複数接続するときの第２の構成例と異なり、図１に示す本発明の第１の実施の形態の連想メモリ・システム２００では、プライオリティ・エンコーダを有していないにもかかわらず、正しい値が得られることが分かる。
これらは、中間データ演算部９が、中間データ６−１−０〜６−８−０と中間データ６−１−１〜６−８−１の中で最も中間データの無効状態のビット数が少ないものを、８ビットの最適化中間データ１０−１〜１０−８として、各連想メモリ１−０、１−１に、２次検索時の検索データとして出力するため、連想メモリ・システム２００全体として最適な２次検索を実行することができるからである。したがって、最適な結果を格納していない連想メモリ１−１の一致線３−０−１〜３−３−１はすべて無効状態となり、プライオリティ・エンコーダを有する必要がなくなる。さらに最適な結果を格納している連想メモリ１−０については１次検索により生成した中間データ６−１−０〜６−８−０の値が２次検索の検索データとなるので、図２３に示す従来の連想メモリ３００と同様に構造化データをソート処理することなしにランダムな順番で１次連想メモリ・ワード７−０−０〜７−ｓ−ｒに格納しても構わないことがわかる。
最適一致信号１５−０〜１５−ｓおよび一致検出信号１７−０〜１７−ｒ、あるいは一致線３−０−０〜３−ｓ−ｒなどに記憶手段を適宜挿入してパイプラインを構成することにより、動作周波数を向上できることはいうまでもない。
また、中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）、あるいは最適化中間データ１０−１〜１０−ｎなどに記憶手段を適宜挿入しパイプラインを構成することにより動作周波数を向上できることはいうまでもない。
また、本例では連想メモリ１−ｋは、１次検索を１次検索用連想メモリ４−ｋで実行し、２次検索を２次検索用連想メモリ５−ｋで実行する場合を例として説明したが、構成要素を共有することにより１個の連想メモリで１次検索と２次検索を実行する場合においても、まったく同様に連想メモリ・システム２００を構成できることはいうまでもない。また、２次検索用連想メモリ５−１〜５−ｒは、ｎビット（ｍ×ｐ）語の１個の連想メモリにより構成してもよいことはいうまでもない。また、全体でｎビット（ｍ×ｐ）語を容量を持つ任意の個数の連想メモリによっても構成できることも明らかである。
〔第２の実施例の構成〕
次に、本発明の第２の実施の形態の連想メモリ・システムについて図面を参照して詳細に説明する。図３は、本発明の第２の実施の形態のｎビット（ｍ×ｐ）語の連想メモリ・システム２０１の構成例と動作例を示すブロック図である。
連想メモリ・システム２０１は、ｐ個のｍ語ｎビットの連想メモリ１−０〜１−ｒと、中間データ演算部９と、アドレス信号生成部２５とから構成され、ｎビットの検索データ２を入力とし、アドレス出力信号１２を出力とする。図３に示す連想メモリ・システム２０１は、図２に示した第１の実施の形態の動作例の説明と同様に、４語８ビット構成の連想メモリ１−０、１−１を２個を接続し、かつ、構造化データをソート処理することなしにランダムな順番で１次連想メモリ・ワード７−０−０〜７−３−１に格納した場合の動作を例にして説明する。また、全体で８語のアドレス空間の中で連想メモリ１−１が上位側のアドレス空間を占めることとする。もちろん、任意のビット長、ワード数のｎビットｍ語の連想メモリ１を、任意個数接続した場合にも同様に構成できることはいうまでもない。
図１に示す本発明の第１の実施の形態の連想メモリ・システム２００と比較すればわかるとおり、図３に示す本発明の第２の実施の形態の連想メモリ・システム２０１は、連想メモリ１−０〜１−ｒ、中間データ演算部９は、第１の実施の形態の連想メモリ・システム２００と同様に構成され、アドレス信号生成部２５の内部構成のみが異なる。したがって、異なる部分のみの説明を行う。
アドレス信号生成部２５は、連想メモリ１−ｋ（ｋは０以上ｒ以下の整数）ごとに一致線３−０−ｋ〜３−ｓ−ｋを入力とするエンコーダ２２−ｋと一致検出手段１６−ｋを有し、またエンコーダ１８と選択手段２４とを有している。
図２７に示す従来の連想メモリを複数接続するときの第２の構成例のアドレス信号生成部３１９と比較すればわかるとおり、図３に示す本発明の第２の実施の形態の連想メモリ・システム２０１のアドレス信号生成部２５は、エンコーダ２２−０〜２２−ｒと、一致検出手段１６−０〜１６−ｒと、選択手段２４は、図２７に示した従来のアドレス信号生成部３１９と同様に構成される。図２７に示した従来のアドレス信号生成部３１９のプライオリティ・エンコーダ３１５が、図３に示す本発明の第２の実施の形態の連想メモリ・システム２０１のアドレス信号生成部２５ではエンコーダ１８に置き換わっていることのみが異なる。エンコーダ１８は、プライオリティ機能がないことことのみが図２７のプライオリティ・エンコーダ３１５と異なり、一致検出手段１６−０〜１６−ｒが生成する一致検出信号１７−０〜１７−ｒを入力とし、符号化した結果を上位アドレス信号１９として選択手段２４に出力するとともにアドレス信号生成部２５の外部にも出力する機能を有している。以降の説明では、エンコーダ２２−０、２２−１、およびエンコーダ１８は、２進数に符号化する場合を例とするが、他の符号化処理でもよいことはいうまでもない。また、図示しないメモリのワード線として直接出力してもよいこともいうまでもない。次に図３を参照して、本発明の第２の実施の形態の連想メモリの・システムの動作を説明する。図１と同様に、本例では以降、マスク情報の有効状態を“０”、無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”として説明する。また、記憶データと同様に、中間データ６の有効状態を“１”、無効状態を“０”とする。一致線３の有効状態を“１”、無効状態を“０”として説明する。
１次検索用連想メモリ４−０、４−１が有する１次連想メモリ・ワード７−０−０〜７−３−１には、図１の説明と同様に、４進表記の構造化データとしてそれぞれ（１．＊．＊．＊）、（２．＊．＊．＊）、（１．２．２．＊）、（２．１．２．＊）、（３．１．＊．＊）、（１．２．＊．＊）、（２．１．＊．＊）、（３．＊．＊．＊）を表現するように、記憶データ、マスク情報を、ソート処理することなしに格納しているものとする。また、２次検索用連想メモリ５−０、５−１が有する連想メモリ・ワード８−０−０〜８−３−１には、図１の説明と同様に、１次検索用連想メモリ４−０、４−１の対応する１次連想メモリ・ワード７−０−０〜７−３−１が格納している記憶データと同じ４進表記の値、（１．０．０．０）、（２．０．０．０）、（１．２．２．０）、（２．１．２．０）、（３．１．０．０）、（１．２．０．０）、（２．１．０．０）、（３．０．０．０）を２次記憶データとして格納しているものとする。
ここで図１の説明と同様に検索データ２として図２４に示すＰＣ４０１−２の４進表記のネットワーク・アドレス（２．１．２．３）を入力した場合には、連想メモリ１−０、１−１、および中間データ演算部９は図１の説明と同様に動作し、結果として一致線３−０−０〜３−３−１の中で、一致線３−３−０のみが一致線の有効状態“１”をアドレス信号生成部２５に出力し、残りの一致線３−０−０〜３−２−０、３−０−１〜３−３−１には一致線の無効状態“０”を出力することになる。したがってアドレス信号生成部２５には、連想メモリ１−０から一致線３−０−０〜３−３−０として２進表記で“１０００”が入力され、連想メモリ１−１から一致線３−０−１〜３−３−１として２進表記で“００００”が入力されることになる。
したがって、連想メモリ１−０に対応するプライオリティ機能を有しないエンコーダ２２−０は一致アドレス信号２３−０として２進表記で“１１”を選択手段２４に出力し、一致検出手段１６−０は一致検出信号１７−０に有効状態“１”を出力する。連想メモリ１−１に対応するプライオリティ機能を有しないエンコーダ２２−１は一致アドレス信号２３−１として２進表記で“００”を選択手段２４に出力し、一致検出手段１６−１は一致検出信号１７−１に無効状態“０”を出力する。
図２７のプライオリティ・エンコーダ３１５の場合と異なり、図３のエンコーダ１８に入力されている一致検出信号１７−０〜１７−１の中で有効状態“１”であるものは、一致検出信号１７−０のみであるため、エンコーダ１８は２進表記で“０”を、上位アドレス信号１９として選択手段２４に出力するとともに、アドレス信号生成部２５の外部にも出力する。
選択手段２４は、エンコーダ１８から入力された上位アドレス信号１９が２進表記で“０”であるため、対応する２進表記で“１１”の一致アドレス信号２３−０を選択し、下位アドレス信号２１としてアドレス信号生成部２５の外部に出力する。
アドレス信号生成部２５から出力された２進表記で“０”の上位アドレス信号１９、２進表記で“１１”の下位アドレス信号２１を、それぞれアドレス出力信号１２の上位側、下位側として連結することにより、２進表記で“０１１”のアドレス出力信号１２が得られる。したがって、図２７に示した従来の連想メモリを複数接続するときの第２の構成例と異なり図３に示す本発明の第２の実施の形態の連想メモリ・システム２０１ではプライオリティ・エンコーダを有していないにもかかわらず、図２の第１の実施の形態の連想メモリ・システム２００の動作例と同様に、検索データ２に対する正しい検索結果が得られることが分かる。
これは、第１の実施の形態の連想メモリ・システム２００と同様に、中間データ演算部９が、中間データ６−１−０〜６−８−０と中間データ６−１−１〜６−８−１の中で最も中間データの無効状態のビット数が少ないものを、８ビットの最適化中間データ１０−１〜１０−８として、各連想メモリ１−０、１−１に、２次検索時の検索データとして出力するため、連想メモリ・システム２０１全体として最適な２次検索を実行することができるからである。したがって、最適な結果を格納していない連想メモリ１−１の一致線３−０−１〜３−３−１はすべて無効状態となり、プライオリティ・エンコーダを有する必要がなくなる。
本例のアドレス信号生成部２５は、図１に示したアドレス信号生成部１１よりも構成が複雑であるが、各連想メモリ１−ｋ（ｋは０以上ｒ以下の整数）ごとに、対応するエンコーダ２２−ｋ、一致検出手段１６−ｋを、物理的に近い位置に配置することにより、長い配線の本数を削減することが可能となる。各連想メモリ１−０〜１−ｒの面積は一般に非常に大きいので、各連想メモリ間を結線する一致線３−０−０〜３−ｓ−ｒの配線は非常に長くなる。そのため、本例のアドレス信号生成部２５は、図１に示したアドレス信号生成部１１に比べて、信号遅延時間、配線容量による消費電力などを削減できる。また、配線領域の減少により、さらに面積が削減可能である。
もちろん、図２７に示したプライオリティ・エンコーダ３１５を有するアドレス信号生成部３１９を、本例のアドレス信号生成部２５の代わりに用いても正しい結果が得られることは明らかである。。また、この場合においても、構造化データを１次連想メモリ・ワード７−０−０〜７−３−１に格納する際にソート処理が不要であることは言うまでもない。
一致アドレス信号２３−０〜２３−ｒおよび一致検出信号１７−０〜１７−ｒ、あるいは一致線３−０−０〜３−ｓ−ｒなどに記憶手段を適宜挿入してパイプラインを構成することにより、動作周波数を向上できることはいうまでもない。
また、本例では連想メモリ１−ｋは、１次検索を１次検索用連想メモリ４−ｋで実行し、２次検索を２次検索用連想メモリ５−ｋで実行する場合を例として説明したが、構成要素を共有することにより１個の連想メモリで１次検索と２次検索を実行する場合においても、まったく同様に連想メモリ・システム２０１を構成できることはいうまでもない。
〔中間データ演算部の第２の構成例〕
次に、本発明の連想メモリ・システムの中間データ演算部の第２の構成例について説明する。図４は、本発明の連想メモリ・システムの中間データ演算部の第２の構成例を示すブロック図である。中間データ演算部２６は、図１に示す中間データ演算部９と同様に、図示しないｐ個の連想メモリから入力されるｐ個のｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）の中で、最も中間データの無効状態のビット数が少ないものをｎビットの最適化中間データ１０−１〜１０−ｎとして出力する。図４に示す第２の構成例の中間データ演算部２６は、入力されたｐ個のｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）を、それぞれ２進数の数値と見なして比較したときに最大値となるものをｎビットの最適化中間データ１０−１〜１０−ｎとして出力する、最大値選択手段２７により構成される。これは図２４に示すように、ネットワーク・アドレスが階層構造を持つため、最も中間データの無効状態のビット数が少ないものが２進数の数値と見なしたときに最大値となるからである。
次に図５を参照して、本発明の第２の構成例の中間データ演算部２６の動作を、図１と同様に、図示しない２個の８ビット構成の連想メモリ２個から、４進表記で（２．１．２．０）の中間データ６−１−０〜６−８−０、４進表記で（２．１．０．０）の中間データ６−１−１〜６−８−１が、それぞれ中間データ演算部２６に入力されている場合を例として説明する。また、図１と同様に、本例では以降、中間データ６の有効状態を“１”、無効状態を“０”とする。
中間データ６−１−０〜６−８−０の値は、２進表記で“１００１１０００”、１０進表記で“１５２”となる。中間データ６−１−１〜６−８−１の値は、２進表記で“１００１００００”、１０進表記で“１４４”となる。したがって、最大値選択手段２７は、中間データ６−１−０〜６−８−０と中間データ６−１−１〜６−８−１を比較した結果最大値となる中間データ６−１−０〜６−８−０を選択し、最適化中間データ１０−１〜１０−８として、中間データ演算部２６の外部に出力する。したがって、最適化中間データ１０−１〜１０−８として正しい値が得られることが分かる。
ここで、中間データ６の有効状態が“０”、無効状態が“１”の場合には、入力されたｐ個のｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）を、それぞれ２進数の数値と見なして比較したときに最小値となるものをｎビットの最適化中間データ１０−１〜１０−ｎとして出力する、最小値選択手段により構成すればよいことは言うまでもない。
また、中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）、あるいは最適化中間データ１０−１〜１０−ｎなどに記憶手段を適宜挿入しパイプラインを構成することにより動作周波数を向上できることはいうまでもない。
〔中間データ演算部の第３の構成例〕
次に、本発明の連想メモリ・システムの中間データ演算部の第３の構成例について説明する。図６は、本発明の連想メモリ・システムの中間データ演算部の第３の構成例を示すブロック図である。中間データ演算部２８は、図１に示す中間データ演算部９と同様に、図示しないｐ個の連想メモリから入力されるｐ個のｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）の中で、最も中間データの無効状態のビット数が少ないものをｎビットの最適化中間データ１０−１〜１０−ｎとして出力する。図６に示す第３の構成例の中間データ演算部２８は、無効状態ビット数計数手段２９−０〜２９−ｒと、比較手段３３−０〜３３−ｒと、最小値選択手段３１と、選択手段３５とを有している。
ｋ番目の無効状態ビット数計数手段２９−ｋは、対応するｎビットの中間データ６−１−ｋ〜６−ｎ−ｋを入力とし、ネットワーク・アドレスの最下位階層側から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数する。無効状態ビット数計数手段２９−ｋは、計数結果を無効状態ビット数信号３０−ｋとして最小値選択手段３１および比較手段３３−ｋに出力する。
最小値選択手段３１は、無効状態ビット数計数手段２９−０〜２９−ｒからそれぞれ入力される無効状態ビット数信号３０−０〜３０−ｒを比較し、その中の最小値を最小値信号３２として比較手段３３−０〜３３−ｒに出力する。
ｋ番目の比較手段３３−ｋは、対応する無効状態ビット数信号３０−ｋと、最小値信号３２とを比較し、一致する場合には選択許可信号３４−ｋに有効状態を、それ以外の場合には無効状態を出力する。したがって、無効状態ビット数信号３０−０〜３０−ｒの中でｋ番目の無効状態ビット数信号３０−ｋが最小の場合のみ、選択許可信号３４−ｋは有効状態となる。
選択手段３５は、選択許可信号３４−０〜３４−ｒの中で有効状態である選択許可信号３４−ｋに対応する中間データ６−１−ｋ〜６−ｎ−ｋを、最適化中間データ１０−１〜１０−ｎとして中間データ演算部２８の外部に出力する。つまり、ネットワーク・アドレスの最下位階層側から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数した場合に最小となるような中間データ６−１−ｋ〜６−ｎ−ｋが、最適化中間データ１０−１〜１０−ｎとして出力されることになる。
次に図７を参照して、本発明の第３の構成例の中間データ演算部２８の動作を、図１と同様に、図示しない２個の８ビット構成の連想メモリ２個から、４進表記で（２．１．２．０）の中間データ６−１−０〜６−８−０、４進表記で（２．１．０．０）の中間データ６−１−１〜６−８−１が、それぞれ中間データ演算部２８に入力されている場合を例として説明する。また、図１と同様に、本例では以降、中間データ６の有効状態を“１”、無効状態を“０”とする。また、図２４に示すように、ネットワーク・アドレスの最上位階層は左側、最下位階層は右側とする。
無効状態ビット数計数手段２９−０は、中間データ６−１−０〜６−８−０の２進表記の値“１００１１０００”の中で、最初の有効状態“１”が現れるまで、右側のビットから無効状態“０”を計数し、結果として得られる１０進表記で“３”の値を無効状態ビット数信号３０−０として出力する。無効状態ビット数計数手段２９−１は、中間データ６−１−１〜６−８−１の２進表記の値“１００１００００”の中で、最初の有効状態“１”が現れるまで、右側のビットから無効状態“０”を計数し、結果として得られる１０進表記で“４”の値を無効状態ビット数信号３０−１として出力する。
最小値選択手段３１は、無効状態ビット数計数手段２９−０〜２９−１からそれぞれ入力される無効状態ビット数信号３０−０、３０−１を比較し、その中の最小値である１０進表記の値“３”を最小値信号３２として比較手段３３−０〜３３−１に出力する。
比較手段３３−０は、対応する無効状態ビット数信号３０−０の１０進表記の値“３”と、最小値信号３２の１０進表記の値“３”とを比較し、一致するので選択許可信号３４−０に有効状態を出力する。比較手段３３−１は、対応する無効状態ビット数信号３０−１の１０進表記の値“４”と、最小値信号３２の１０進表記の値“３”とを比較し、一致しないので選択許可信号３４−１に無効状態を出力する。選択手段３５は、入力された選択許可信号３４−０、３４−１の中で有効状態である選択許可信号３４−０に対応する中間データ６−１−０〜６−８−０の４進表記の値（２．１．２．０）を、最適化中間データ１０−１〜１０−８として中間データ演算部２８の外部に出力する。したがって、最適化中間データ１０−１〜１０−８として正しい値が得られることが分かる。これは、各連想メモリ１−０〜１−ｒにおいて、構造化データのドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態とし、マスク情報の該当ビットをマスク・データの有効状態とすることにより表現しているため、ネットワーク・アドレスの最下位階層側から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数した場合に最小となるような中間データ６−１−ｋ〜６−ｎ−ｋが、最適化中間データ１０−１〜１０−ｎとなるからである。
また、中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）、あるいは最適化中間データ１０−１〜１０−ｎなどに記憶手段を適宜挿入しパイプラインを構成することにより動作周波数を向上できることはいうまでもない。
また、本例の無効状態ビット数計数手段２９−ｋは、回路規模を削減するために、中間データ６−１−ｋ〜６−ｎ−ｋにおけるネットワーク・アドレスの最下位階層側から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数しているが、単純に中間データ６−１−ｋ〜６−ｎ−ｋの全ビットにおける無効状態の数を計数してもよいことは明らかである。
〔第３の実施例の構成〕
次に、本発明の第３の実施の形態の連想メモリ・システムについて図面を参照して詳細に説明する。図８は、本発明の第３の実施の形態のｎビット（ｍ×ｐ）語の連想メモリ・システム２０３の構成例を示すブロック図である。
連想メモリ・システム２０３は、ｐ個のｍ語ｎビットの連想メモリ２０２−０〜２０２−ｒと、ｎ個の抵抗３８−１〜３８−ｎと、アドレス信号生成部１１とから構成され、ｎビットの検索データ２を入力とし、アドレス出力信号１２を出力とする。図１に示す本発明の第１の実施の形態の連想メモリ・システム２００と比較すればわかるとおり、図８に示す本発明の第３の実施の形態の連想メモリ・システム２０３は、アドレス信号生成部１２は第１の実施の形態の連想メモリ・システム２００と同様に構成され、連想メモリ２０２−０〜２０２−ｒの内部構造、および中間データ演算部９の代わりに抵抗３８−１〜３８−ｎを有する点のみが異なる。したがって、異なる部分のみの説明を行う。
連想メモリ２０２−ｋは（ｋは０以上ｒ以下の整数）、１次検索用連想メモリ４−ｋと、２次検索用連想メモリ５−ｋと、出力手段３６−１−ｋ〜３６−ｎ−ｋと、入力手段３７−１−ｋ〜３７−ｎ−ｋとにより構成される。図１に示す連想メモリ１−ｋと比較すればわかるとおり、図８に示す連想メモリ２０２−ｋは、１次検索用連想メモリ４−ｋと、２次検索用連想メモリ５−ｋは、図１に示す連想メモリ１−ｋと同様に構成される。１次検索用連想メモリ４−ｋから出力される中間データ６−１−ｋ〜６−ｎ−ｋに出力手段３６−１−ｋ〜３６−ｎ−ｋが接続されている点と、２次検索用連想メモリ５−ｋに入力される最適化中間データ３７−１−ｋ〜３７−ｎ−ｋを入力手段３７−１−ｋ〜３７−ｎ−ｋが生成している点と、および出力手段３６−１−ｋ〜３６−ｎ−ｋの出力信号である結線論理和信号３９−１〜３９−ｎが連想メモリ２０２−ｋの外部に出力されるとともに入力手段３７−１−ｋ〜３７−ｎ−ｋにそれぞれ入力されている点のみが、図１に示す連想メモリ１−ｋと異なる。したがって、異なる部分についてのみ説明を行う。
ｊ番目（ｊは１以上ｎ以下の整数）の出力手段３６−ｊ−ｋは、中間データの無効状態の電位と結線論理和信号３９−ｊの間に挿入され、中間データ３６−ｊ−ｋが有効状態の時に導通状態となり、中間データ３６−ｊ−ｋが無効状態の場合には開放状態となる。したがって出力手段３６−ｊ−ｋは、中間データ３６−ｊ−ｋが有効状態の時に結線論理和信号３９−ｊに中間データの無効状態を出力し、中間データ３６−ｊ−ｋが無効状態の場合には結線論理和信号３９−ｊを開放状態にする。
またｊ番目の入力手段３７−ｊ−ｋは、入力された結線論理和信号３９−ｊの状態を反転して最適化中間データ４０−ｊ−ｋとして２次検索用連想メモリ５−ｋに出力する。
各連想メモリ２０２−０〜２０２−ｒが出力する結線論理和信号３９−１〜３９−ｎは対応するビット同士が相互に接続されるとともに、対応する抵抗３８−１〜３８−ｎを介して中間データの有効状態の電位に接続されている。
これにより、１つの１次連想メモリ４−ｋでもｊビット目の中間データ６−ｊ−ｋに有効状態を出力していると、すべての２次連想メモリ５−０〜５−ｒに入力されるｊビット目の最適化中間データ線４０−ｊ−０〜４０−ｊ−ｒは中間データの有効状態となるようなワイアードＯＲ接続を構成していることになり、図１に示す中間データ演算部９の論理和手段１３と、論理的に等価となる。したがって、連想メモリ・システム２０３全体として、図１に示した連想メモリ・システム２００と論理的に等価であることがわかる。
本例の連想メモリ・システム２０３では、ワイアードＯＲ接続により、図１の中間データ演算部と等価な構成を実現しているため、一致線（３−０−０〜３−ｓ−０）〜（３−０−ｒ〜３−ｓ−ｒ）を除くと、連想メモリ・システム２０３は結線論理和信号３９−１〜３９−ｎのｎ本の配線しか有していない。また、連想メモリ２０２−ｋは、検索データおよび一致線３−０−ｋ〜３−ｓ−ｋを除くと、必要な端子は結線論理和信号３９−１〜３９−ｎを入出力するためのｎ個の端子のみである。例えば４個の６４ビットの連想メモリ１−０〜１−３で図８の連想メモリ・システム２０３を構成したい場合、連想メモリ間の前記の配線は６４本となり、連想メモリ２０２−ｋに必要な前記の端子は６４個となる。
図１に示した連想メモリ・システム２００では、ｐ個の連想メモリ１−０〜１−ｒがそれぞれｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）を中間データ演算部９に出力するｎ×ｐ本の配線と、中間データ演算部９が連想メモリ１−０〜１−ｒに出力する最適化中間データ１０−１〜１０−ｎのｎ本の配線を有する。したがって、連想メモリ・システム２００は、一致線（３−０−０〜３−ｓ−０）〜（３−０−ｒ〜３−ｓ−ｒ）を除いて、連想メモリ１−０〜１−ｒ間にｎ×（ｐ＋１）本の配線を有することになる。また、各連想メモリ１−ｋは検索データおよび一致線３−０−ｋ〜３−ｓ−ｋを除くと、ｎビットの中間データ６−１−ｋ〜６−ｎ−ｋを出力するためのｎ個の端子と、ｎビットの最適化中間データ１０−１〜１０−ｎを入力するためのｎ個の端子の、合計２ｎ個の端子が必要である。例えば４個の６４ビットの連想メモリ１−０〜１−３で図１の連想メモリ・システム２００を構成したい場合、連想メモリ間の前記の配線は３２０本となり、連想メモリ１−ｋに必要な前記の端子は１２８個となる。
したがって、図８に示す第３の実施の形態の連想メモリ・システム２０３は、図１に示した連想メモリ・システム２００よりも、大幅に長い配線の本数を削減することが可能となるとともに、各連想メモリ２０２に必要な端子の数を大幅に削減することができる。各連想メモリ２０２の面積は一般に非常に大きいので、各連想メモリ間の配線は非常に長くなる。そのため、本例の連想メモリ・システム２０３は、図１に示した連想メモリ・システム２００に比べて、信号遅延時間、配線容量による消費電力などを削減可能である。また、配線領域の減少により、さらに面積を削減することができる。また、各連想メモリの端子数が大幅に削減されるため面積をさらに削減することが可能である。
本例では連想メモリ２０２−ｋは、１次検索を１次検索用連想メモリ４−ｋで実行し、２次検索を２次検索用連想メモリ５−ｋで実行する場合を例として説明したが、構成要素を共有することにより１個の連想メモリで１次検索と２次検索を実行する場合においても、まったく同様に連想メモリ・システム２０３を構成できることはいうまでもない。
また、結線論理和信号３９−１〜３９−ｎを、抵抗３８−１〜３８−ｎを介して中間データの有効状態に接続する代わりに、１次検索の開始前に中間データの有効状態にプリ・チャージすることによっても構成できることはいうまでもない。
〔第４の実施例の構成〕
次に、本発明の第４の実施の形態の連想メモリ・システムについて図面を参照して詳細に説明する。図９は、本発明の第４の実施の形態のｎビット（ｍ×ｐ）語の連想メモリ・システム２０５の構成例を示すブロック図である。
連想メモリ・システム２０５は、ｐ個のｍ語ｎビットの連想メモリ２０４−０〜２０４−ｒと、ｐ個の論理積手段４６−０〜４６−ｒと、中間データ判定部４１と、アドレス信号生成部１１とから構成され、ｎビットの検索データ２を入力とし、アドレス出力信号１２を出力とする。
ｋ番目の連想メモリ２０４−ｋは、図２７に示す従来の連想メモリ３００−ｋと比較すればわかるとおり、中間データ６−１−ｋ〜６−ｎ−ｋを２次検索用連想メモリ５−ｋに入力するとともに連想メモリ２０４−ｋ外部に出力することを除けば、図２７に示す従来の連想メモリ３００−ｋと同様に構成することができる。
アドレス信号生成部１１は、入力が一致線３−０−０〜３−ｓ−ｒでなく、実効一致線４７−０−０〜４７−ｓ−ｒに代わった点を除けば、図１のアドレス信号生成部１１と全く同様に構成することができる。もちろん、図３に示したアドレス信号生成部２５を用いても構成できることは言うまでもない。
中間データ判定部４１は、ｐ個の連想メモリ２０４−０〜２０４−ｒから入力されるｐ個のｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）の中で、最も中間データの無効状態のビット数が少ないものに対応する有効検出信号４５−０〜４５−ｒに有効状態を出力する。中間データ判定部４１は、中間データ演算部４２と、ｐ個の比較手段４４−０〜４４−ｒとから構成される。中間データ演算部４１は、ｐ個の連想メモリ２０４−０〜２０４−ｒから入力されるｐ個のｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）の中で、最も中間データの無効状態のビット数が少ないものをｎビットの最適化中間データ４３−１〜４３−ｎとして比較手段４４−０〜４４−ｒに出力する。したがって、中間データ演算部４２は、図１に示す中間データ演算部９と全く同様に構成することができる。もちろん、図４に示す第２の構成例の中間データ演算部２６、図６に示す第３の構成例の中間データ演算部２８を用いても構成できることは言うまでもない。
ｋ番目の比較手段４４−ｋは、対応する中間データ６−１−ｋ〜６−ｎ−ｋと、最適化中間データ４３−１〜４３−ｎとを比較し、一致する場合には有効検出信号４５−ｋに有効状態を、それ以外の場合には無効状態を出力する。したがって、ｐ個のｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）の中で、ｋ番目の中間データ６−１−ｋ〜６−ｎ−ｋが最も中間データの無効状態のビット数が少ない場合のみ、有効検出信号４５−ｋは有効状態となる。
ｋ番目の連想メモリ２０４−ｋに対応する論理積手段４６−ｋは、対応する有効検出信号４５−ｋが有効状態の場合には、連想メモリ２０４−ｋから入力される一致線３−０−ｋ〜３−ｓ−ｋを実効一致線４７−０−ｋ〜４７−ｓ−ｋとしてアドレス信号生成部１１に出力し、有効検出信号４５−ｋが無効状態の場合には、ｍ本の実効一致線４７−０−ｋ〜４７−ｓ−ｋすべてに一致線の無効状態を出力する。
〔第４の実施例の動作〕
次に図１０を参照して、本発明の第４の実施の形態の連想メモリの・システムの動作を、図１、および図２６と同様に４語８ビット構成の連想メモリ２０４−０、２０４−１の２個を接続し、かつ、構造化データをソート処理することなしにランダムな順番で１次連想メモリ・ワード７−０−０〜７−３−１に格納した場合の動作を例にして説明する。ここで、図１、および図２６と同様に全体で８語のアドレス空間の中で連想メモリ２０４−１が上位側のアドレス空間を占めることとする。
図１、および図２６と同様に、本例では以降、マスク情報の有効状態を“０”、無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”として説明する。また、記憶データと同様に、中間データ６の有効状態を“１”、無効状態を“０”とする。一致線３の有効状態を“１”、無効状態を“０”として説明する。
１次検索用連想メモリ４−０、４−１が有する１次連想メモリ・ワード７−０−０〜７−３−１には、図１、および図２６の説明と同様に、４進表記の構造化データとしてそれぞれ（１．＊．＊．＊）、（２．＊．＊．＊）、（１．２．２．＊）、（２．１．２．＊）、（３．１．＊．＊）、（１．２．＊．＊）、（２．１．＊．＊）、（３．＊．＊．＊）を表現するように、記憶データ、マスク情報を、ソート処理することなしに格納しているものとする。また、２次検索用連想メモリ５−０、５−１が有する連想メモリ・ワード８−０−０〜８−３−１には、図１、図２６の説明と同様に、１次検索用連想メモリ４−０、４−１の対応する１次連想メモリ・ワード７−０−０〜７−３−１が格納している記憶データと同じ４進表記の値、（１．０．０．０）、（２．０．０．０）、（１．２．２．０）、（２．１．２．０）、（３．１．０．０）、（１．２．０．０）、（２．１．０．０）、（３．０．０．０）を２次記憶データとして格納しているものとする。
ここで図２６の説明と同様に、検索データ２として図２４に示すＰＣ４０１−２の４進表記のネットワーク・アドレス（２．１．２．３）を入力した場合、連想メモリ２０４−０、２０４−１は図２６の従来の連想メモリ３００−０、３００−１と同様に動作する。連想メモリ２０４−０の１次検索用連想メモリ４−０では検索データ２を入力とする１次検索の結果１次連想メモリ・ワード７−１−０、７−３−０が一致し中間データ６−１−０〜６−８−０として４進表記で（２．１．２．０）、２進表記で“１００１１０００”を２次検索用連想メモリ５−０と中間データ判定部４１に出力する。２次検索用連想メモリ５−０では中間データ６−１−０〜６−８−０を入力とする２次検索の結果連想メモリ・ワード８−３−０が一致し一致線３−０−０〜３−３−０に２進表記で“１０００”を出力することになる。連想メモリ２０４−１の１次検索用連想メモリ４−０では検索データ２を入力とする１次検索の結果１次連想メモリ・ワード７−２−１が一致し中間データ６−１−１〜６−８−１として４進表記で（２．１．０．０）、２進表記で“１００１００００”を２次検索用連想メモリ５−１と中間データ判定部４１に出力する。２次検索用連想メモリ５−１では中間データ６−１−１〜６−８−１を入力とする２次検索の結果連想メモリ・ワード８−２−１が一致し一致線３−０−１〜３−３−１に２進表記で“０１００”を出力することになる。
中間データ判定部４１の中間データ演算部４２は、中間データ６−１−０〜６−８−０の２進表記の値“１００１１０００”と、中間データ６−１−１〜６−８−１の２進表記の値“１００１００００”の中で、最も中間データの無効状態のビット数が少ない２進表記の値“１００１１０００”、４進表記で（２．１．２．０）を最適化中間データ４３−１〜４３−８として出力する。
比較手段４４−０は、対応する中間データ６−１−０〜６−８−０の２進表記の値“１００１１０００”と、最適化中間データ４３−１〜４３−８の値を比較し、一致するので有効検出信号４５−０に有効状態を出力する。比較手段４４−１は、対応する中間データ６−１−１〜６−８−１の２進表記の値“１００１００００”と、最適化中間データ４３−１〜４３−８の値を比較し、一致しないので有効検出信号４５−１に無効状態を出力する。
論理積手段４６−０は、対応する有効検出信号４５−０が有効状態であるので、連想メモリ２０４−０から出力される一致線３−０−０〜３−３−０の２進表記の値“１０００”を実効一致線４７−０−０〜４７−３−０に出力する。論理積手段４６−１は、対応する有効検出信号４５−１が無効状態であるので、実効一致線４７−０−１〜４７−３−１すべてに一致線の無効状態を出力する。したがって、実効一致線４７−０−１〜４７−３−１は２進表記で“００００”となる。したがって、アドレス信号生成部１１に入力される信号の中で有効状態である信号は図２の説明と同様に実効一致線４７−３−０の一本のみとなり、アドレス信号生成部１１はアドレス出力信号１２に図２と同様に正しい２進数の値“０１１”を出力できることがわかる。
本実施例では、ｋ番目の連想メモリ２０４−ｋは１次検索用連想メモリ４−ｋで生成した中間データ６−１−ｋ〜６−８−ｋを２次検索用連想メモリ５−ｋの入力として２次検索を行った結果得られる一致線３−０−ｋ〜３−ｓ−ｋに対して、中間データ６−１−ｋ〜６−８−ｋがｐ個の中間データ（６−１−０〜６−８−０）〜（６−１−ｒ〜６−８−ｒ）の中で最適でない場合には、一致線３−０−ｋ〜３−ｓ−ｋをすべて無効状態に変更した後にアドレス信号生成部１１に入力することにより、連想メモリ・システム２０５全体としての最適なアドレス出力信号１２を得る構成となっている。それに対して、本発明の第１の連想メモリ・システム２００では中間データ演算部９によりｐ個の中間データ（６−１−０〜６−８−０）〜（６−１−ｒ〜６−８−ｒ）の中からから連想メモリ・システム２００全体として最適なデータとして選択された最適化中間データ１０−１〜１０−８を入力とする２次検索を２次検索用連想メモリ５−０〜５−ｒで行うことにより連想メモリ・システム全体としての最適なアドレス信号出力１２を得る構成となっている。したがって、本発明の第１の実施の形態の連想メモリ・システム２００では中間データ演算部９の結果が得られるまでは２次検索用連想メモリ５−０〜５−ｒは２次検索を開始ができなかったが、本実施例では、中間データ判定部４１の動作と、２次検索用連想メモリ５−０〜５−ｒによる２次検索を並列実行することができるため、連想メモリ・システム２０５全体の演算速度を大幅に向上させることが可能である。
また、ｎビットの最適化中間データをｐ個の連想メモリ２０４−０〜２０４−ｒに入力する必要がなくなるため、連想メモリ・システム２０５全体として長い配線をｎ×ｐ本削減することができるとともに、連想メモリ２０４の端子をｎ個削減することができる。そのため、本例の連想メモリ・システム２０５は、図１に示した連想メモリ・システム２００に比べて、信号遅延時間、配線容量による消費電力などを削減できる。また、配線領域の減少により、さらに面積を削減可能である。また、各連想メモリの端子数が大幅に削減されるため面積をさらに削減することができる。
また、本例では連想メモリ２０４−ｋは、１次検索を１次検索用連想メモリ４−ｋで実行し、２次検索を２次検索用連想メモリ５−ｋで実行する場合を例として説明したが、構成要素を共有することにより１個の連想メモリで１次検索と２次検索を実行する場合においても、まったく同様に連想メモリ・システム２０５を構成できることはいうまでもない。
〔中間データ判定部の第２の構成例と動作例〕
次に、本発明の連想メモリ・システムの中間データ判定部の第２の構成例について説明する。図１１は、本発明の連想メモリ・システム２０６の中間データ判定部４８の第２の構成例と連想メモリ・システム２０６内部での動作例を示すブロック図である。
連想メモリ・システム２０６は、ｐ個のｍ語ｎビットの連想メモリ２０４−０〜２０４−ｒと、中間データ判定部４８と、アドレス信号生成部１１とから構成され、ｎビットの検索データ２を入力とし、アドレス出力信号１２を出力とする。図９に示す連想メモリ・システム２０５と比較すると、中間データ判定部４１が、第２の実施の形態の中間データ判定部４８に置き換わっている点のみが異なり、他は全く同様に構成することができる。図１１に示す連想メモリ・システム２０６は、図１０に示した第４の実施の形態の動作例の説明と同様に、４語８ビット構成の連想メモリ２０４−０、２０４−１を２個を接続し、かつ、１次連想メモリ・ワード７−０−０〜７−３−１、連想メモリ・ワード８−０−０〜８−３−１に図１０と同様なデータを格納した場合の動作を例にして説明する。また、全体で８語のアドレス空間の中で連想メモリ２０４−１が上位側のアドレス空間を占めることとする。もちろん、任意のビット長、ワード数のｎビットｍ語の連想メモリ２０４を、任意個数接続した場合にも同様に構成できることはいうまでもない。
中間データ判定部４８は、図９に示す中間データ判定部４１と同様に、ｐ個の連想メモリから入力されるｐ個のｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）の中で、最も中間データの無効状態のビット数が少ないものに対応する有効検出信号４５−０〜４５−ｒに有効状態を出力する。中間データ判定部４８は、無効状態ビット数計数手段４９−０〜４９−ｒと、比較手段５３−０〜５３−ｒと、最小値選択手段５１とを有している。
ｋ番目の無効状態ビット数計数手段４９−ｋは、対応するｎビットの中間データ６−１−ｋ〜６−ｎ−ｋを入力とし、ネットワーク・アドレスの最下位階層側から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数する。無効状態ビット数計数手段４９−ｋは、計数結果を無効状態ビット数信号５０−ｋとして最小値選択手段５１および比較手段５３−ｋに出力する。
最小値選択手段５１は、無効状態ビット数計数手段４９−０〜４９−ｒからそれぞれ入力される無効状態ビット数信号５０−０〜５０−ｒを比較し、その中の最小値を最小値信号５２として比較手段５３−０〜５３−ｒに出力する。
ｋ番目の比較手段５３−ｋは、対応する無効状態ビット数信号５０−ｋと、最小値信号５２とを比較し、一致する場合には有効検出信号４５−ｋに有効状態を、それ以外の場合には無効状態を出力する。したがって、無効状態ビット数信号５０−０〜５０−ｒの中でｋ番目の無効状態ビット数信号５０−ｋが最小のばあいのみ、有効検出信号４５−ｋは有効状態となる。つまり、ネットワーク・アドレスの最下位階層側から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数した場合に最小となるような中間データ６−１−ｋ〜６−ｎ−ｋに対応する有効検出信号４５−ｋのみに有効状態が出力されることになる。
次に図１１を参照して、本発明の第２の構成例の中間データ判定部４８の動作を説明する。本例では以降、中間データ６の有効状態を“１”、無効状態を“０”とする。また、図２４に示すように、ネットワーク・アドレスの最上位階層は左側、最下位階層は右側とする。連想メモリ２０４−０、２０４−１は図１０と同様に動作し、４進表記で（２．１．２．０）の中間データ６−１−０〜６−８−０、４進表記で（２．１．０．０）の中間データ６−１−１〜６−８−１をそれぞれ中間データ判定部４８に入力しているものとする。
無効状態ビット数計数手段４９−０は、中間データ６−１−０〜６−８−０の２進表記の値“１００１１０００”の中で、最初の有効状態“１”が現れるまで、右側のビットから無効状態“０”を計数し、結果として得られる１０進表記で“３”の値を無効状態ビット数信号５０−０として出力する。無効状態ビット数計数手段４９−１は、中間データ６−１−１〜６−８−１の２進表記の値“１００１００００”の中で、最初の有効状態“１”が現れるまで、右側のビットから無効状態“０”を計数し、結果として得られる１０進表記で“４”の値を無効状態ビット数信号５０−１として出力する。
最小値選択手段５１は、無効状態ビット数計数手段４９−０〜４９−１からそれぞれ入力される無効状態ビット数信号５０−０、５０−１を比較し、その中の最小値である１０進表記の値“３”を最小値信号５２として比較手段５３−０〜５３−１に出力する。
比較手段５３−０は、対応する無効状態ビット数信号５０−０の１０進表記の値“３”と、最小値信号５２の１０進表記の値“３”とを比較し、一致するので有効検出信号４５−０に有効状態を出力する。比較手段５３−１は、対応する無効状態ビット数信号５０−１の１０進表記の値“４”と、最小値信号５２の１０進表記の値“３”とを比較し、一致しないので有効検出信号４５−１に無効状態を出力する。したがって、有効検出信号４５−０〜４５−１として正しい状態が得られることが分かる。これは、各連想メモリ２０４−０〜２０４−ｒにおいて、構造化データのドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態とし、マスク情報の該当ビットをマスク・データの有効状態とすることにより表現しているため、ネットワーク・アドレスの最下位階層側から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数した場合に最小となるような中間データ６−１−ｋ〜６−ｎ−ｋを出力している連想メモリ２０４−ｋのみが最適な検索を実行していることになるからである。
図１１に示す連想メモリ・システム２０６において、連想メモリ２０４−ｋに対応する無効状態ビット数計数手段４９−ｋを連想メモリ２０４−ｋに内蔵した場合には、次のように、長い配線本数削減、連想メモリ２０４の端子数を削減することができる。
連想メモリ・システム２０６の構成要素同士を接続するための長い配線は一致線（３−０−０〜３−ｓ−０）〜（３−０−ｒ〜３−ｓ−ｒ）を除くと、ｐ組の無効状態ビット数信号５０−ｋのみであり、無効状態ビット数計数手段の出力がバイナリ・データに符号化されている場合、これらの配線本数はｐ×［１＋ｌｏｇ２ｎ］となる（［］はガウス記号）。また、連想メモリ２０４−ｋは、検索データおよび一致線３−０−ｋ〜３−ｓ−ｋを除くと、必要な端子は無効状態ビット数信号５０−ｋを出力するための端子のみである。例えば４個の６４ビットの連想メモリ１−０〜１−３で連想メモリ・システム２０６を構成したい場合、無効状態ビット数信号５０のビット数は１０進数で“０”から“６４”を表現するため７本となり、連想メモリ間の前記の配線は合計２８本となる。また、連想メモリ２０４−ｋに必要な前記の端子は７個となる。
図９に示した連想メモリ・システム２０５では、ｐ個の連想メモリ２０４−０〜２０４−ｒがそれぞれｎビットの中間データ（６−１−０〜６−ｎ−０）〜（６−１−ｒ〜６−ｎ−ｒ）を中間データ判定部４１に出力するｎ×ｐ本の配線を有する。したがって、連想メモリ・システム２０５は、一致線（３−０−０〜３−ｓ−０）〜（３−０−ｒ〜３−ｓ−ｒ）を除いて、連想メモリ２０４−０〜２０４−ｒ間にｎ×ｐ本の配線を有することになる。また、各連想メモリ２０４−ｋは検索データおよび一致線３−０−ｋ〜３−ｓ−ｋを除くと、ｎビットの中間データ６−１−ｋ〜６−ｎ−ｋを出力するためのｎ個の端子が必要である。例えば４個の６４ビットの連想メモリ２０４−０〜２０４−３で図９の連想メモリ・システム２０５を構成したい場合、連想メモリ間の前記の配線は２５６本となり、連想メモリ２０４−ｋに必要な前記の端子は６４個となる。
したがって、図１１に示す連想メモリ・システム２０６において、連想メモリ２０４−ｋに対応する無効状態ビット数計数手段４９−ｋを連想メモリ２０４−ｋに内蔵した場合には、図９に示した連想メモリ・システム２０５よりも、大幅に長い配線の本数を削減することが可能となるとともに、各連想メモリ２０４に必要な端子の数を大幅に削減することが可能である。各連想メモリ２０４の面積は一般に非常に大きいので、各連想メモリ間の配線は非常に長くなる。そのため、本例の連想メモリ・システム２０６は、図９に示した連想メモリ・システム２０５に比べて、信号遅延時間、配線容量による消費電力などを削減することができる。また、配線領域の減少により、さらに面積を削減可能である。また、各連想メモリの端子数が大幅に削減されるため、面積をさらに削減することができる。
本例では連想メモリ２０４−ｋは、１次検索を１次検索用連想メモリ４−ｋで実行し、２次検索を２次検索用連想メモリ５−ｋで実行する場合を例として説明したが、構成要素を共有することにより１個の連想メモリで１次検索と２次検索を実行する場合においても、まったく同様に連想メモリ・システム２０６を構成できることはいうまでもない。
また、本例の無効状態ビット数計数手段４９−ｋは、回路規模を削減するために、中間データ６−１−ｋ〜６−ｎ−ｋにおけるネットワーク・アドレスの最下位階層側から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数しているが、単純に中間データ６−１−ｋ〜６−ｎ−ｋの全ビットにおける無効状態の数を計数してもよいことは明らかである。
〔第５の実施例の構成〕
次に、本発明の第５の実施の形態の連想メモリ・システムについて図面を参照して詳細に説明する。図１２は、本発明の第５の実施の形態のｎビット（ｍ×ｐ）語の連想メモリ・システム２０８の構成例を示すブロック図である。
連想メモリ・システム２０８は、ｐ個のｍ語ｎビットの連想メモリ２０７−０〜２０７−ｒと、ｐ個の論理積手段４６−０〜４６−ｒと、中間データ判定部４１と、アドレス信号生成部１１と、ｐ個の記憶回路５４−０〜５４−ｒとから構成され、ｎビットの検索データ２とクロック信号５５とを入力とし、アドレス出力信号１２を出力とする。図９に示す本発明の第４の実施の形態の連想メモリ・システム２０５と比較すればわかるとおり、図１２に示す本発明の第５の実施の形態の連想メモリ・システム２０８は、連想メモリ２０７−０〜２０７−ｒにクロック信号５５が入力されている点と、中間データ判定部４１と各論理積手段４６−０〜４６−ｒとの間にクロック信号５５を入力とする記憶回路５４−０〜５４−ｒがそれぞれ挿入されている点と、論理積手段４６−０〜４６−ｒの入力信号が記憶回路５４−０〜５４−ｒが出力する同期化有効検出信号５６−０〜５６−ｒに変更されている点のみが異なる。したがって、異なる部分のみの説明を行う。
本発明の第５の実施の形態の連想メモリ・システム２０８では、連想メモリ２０７−ｋ（ｋは０以上ｒ以下の整数）の１次検索用連想メモリ４−ｋが中間データ６−１−ｋ〜６−ｎ−ｋを出力してから、２次検索用連想メモリ５−ｋが一致線３−０−ｋ〜３−ｓ−ｋを出力するまでにクロック信号５５でαクロック（αは１以上の整数）の時間を要するものとする。したがって、記憶回路５４−ｋによりクロック信号でαクロックの時間だけ有効検出信号４５−ｋを遅延させた同期化有効検出信号５６−ｋを生成し、論理積手段４６−ｋに入力されるタイミングを一致線３−０−ｋ〜３−ｓ−ｋと同期させている。ここで記憶回路５４−ｋを挿入する位置は、図１２に示した位置に限定されず、１次検索用連想メモリ２０７−ｋの中間データ６−１−ｋ〜６−ｎ−ｋの出力端子から、論理積手段４６−ｋの入力端子までの適宜挿入しても連想メモリ・システム２０８を構成することができることはいうまでもない。また、このとき、αが２以上の整数の場合には記憶手段を複数箇所に分散して挿入してもよいことも言うまでもない。これによりパイプライン動作を構成することになるため動作周波数を向上させることができる。
また、論理積手段４６−ｋに入力されるタイミングを一致線３−０−ｋ〜３−ｓ−ｋと同期させるために、記憶手段を挿入する代わりに遅延手段を挿入しても構わないことは言うまでもない。
図１２では、図９と同様に中間データ判定部４１、アドレス信号生成部１１により連想メモリ・システム２０８を構成した例を示したが、図１１に示した第２の構成例の中間データ判定部４８、図３に示したアドレス信号生成部２５などを用いても同様に構成できることはいうまでもない。
本例では連想メモリ２０７−ｋは、１次検索を１次検索用連想メモリ４−ｋで実行し、２次検索を２次検索用連想メモリ５−ｋで実行する場合を例として説明したが、構成要素を共有することにより１個の連想メモリで１次検索と２次検索を実行する場合においても、まったく同様に連想メモリ・システム２０８を構成できることはいうまでもない。
また、以上説明した第１乃至第５の本発明の連想メモリ・システムを構成する各１次検索用連想メモリの構成要素と、対応する各２次検索用連想メモリの構成要素の一部を兼用することにより面積を削減できることも明らかである。例えば、ｉ番目の１次連想メモリ・ワードにおける記憶データを格納するための手段と、対応する２次検索用連想メモリの対応する連想メモリ・ワードにおける２次記憶データを格納するための手段には、同じ値が格納されるため、兼用することが可能である。
〔第６の実施例の構成〕
次に、本発明の第６の実施の形態の連想メモリ・システムについて図面を参照して詳細に説明する。第６の実施の形態は、複数の部分検索領域から構成される検索データに対して、マスク情報を考慮して検索を行ったときに、入力データに対応する記憶データがすべて一致するワードが複数個あった場合に、優先順位を考慮して検索領域ごとに構造化データを構成するマスク情報のマスク有効状態のビット数について、一致したワードの中で比較した結果、最少となるようなワードを識別する信号を出力する、例えば国際出願番号ＰＣＴ／ＪＰ０１／０３５６２に示される連想メモリを、複数個接続した場合の連想メモリ・システムの構成例である。
図１３は、本発明の第６の実施の形態のｎビット（ｍ×ｐ）語の連想メモリ・システム２１０の構成例を示すブロック図である。連想メモリ・システム２１０は、ｑ個の部分検索領域から構成される検索データ７０を入力とするｐ個のｍ語ｎビットの連想メモリ２０９−０〜２０９−ｒと、ｐ個の論理積手段４６−０〜４６−ｒと、中間データ判定部７１と、（ｑ−１）個の２次中間データ判定部６０−１〜６０−ｈ（ｈは１以上ｔ以下の整数）と、アドレス信号１２を出力するアドレス信号生成部１１と、から構成される。ｋ番目の連想メモリ２０９−ｋは、１次検索用連想メモリ５７−ｋと、検索データ７０のｑ個の部分検索領域に対応する領域ごとに２次検索を実行するｑ個の部分２次検索用連想メモリ５８−１−ｋ〜５８−ｑ−ｋとから構成される。
図１３は、検索データ７０が３個の部分検索領域から構成される場合を例とした連想メモリ・システム２１０のブロック図である。もちろん、検索データ７０の部分検索領域の個数が任意の場合でも構成できることはいうまでもない。
１次検索用連想メモリ５７−ｋは、検索データ７０の全ての部分検索領域を検索対象とする各ｎビットの記憶データおよびマスク情報から構成される構造化データをｍ個格納できる１次連想メモリ・ワード７−０−ｋ〜７−ｓ−ｋを有する。ここで、構造化データのドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態とし、マスク情報の該当ビットをマスク・データの有効状態とすることにより表現される。また、１次検索用連想メモリ５７−ｋは、対応するマスク情報を考慮して検索データ７０の全ての部分検索領域と比較した結果一致する記憶データを検索する１次検索を１次連想メモリ・ワード７−０−ｋ〜７−ｓ−ｋの中で行い、一致する記憶データ同士に対して記憶データの有効状態を真とした論理和演算を行い、得られた値の中で検索データの第１の優先順位を持つ部分検索領域に対応するビット領域のみを中間データ５９−１−ｋとして、中間データ判定部７１、および部分２次検索用連想メモリ５８−１−ｋに出力する。つまり、検索データの第１の優先順位を持つ部分検索領域に対応するビット領域のみから中間データ５９−１−ｋを生成すること以外は、図２６に示す従来の１次検索用連想メモリ３０２と同様に構成することができる。
ｈ番目（ｈは１以上、ｔ以下の整数）の部分２次検索用連想メモリ５８−ｈ−ｋは、連想メモリ・ワード６８−０−ｈ−ｋ〜６８−ｓ−ｈ−ｋを有し、ｉ番目（ｉは０以上ｍ以下の整数）の連想メモリ・ワード６８−ｉ−ｈ−ｋには、対応する１次連想メモリ・ワード７−ｉ−ｋが格納している記憶データと同じ値を第ｈの２次記憶データとして格納する。部分２次検索用連想メモリ５８−ｈ−ｋは、連想メモリ・ワード６８−０−ｈ−ｋ〜６８−ｓ−ｈ−ｋが格納している第ｈの２次記憶データの中で、検索データの第ｈ番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、中間データ５９−ｈ−ｋと比較を行い、一致する第ｈの２次記憶データ同士に対して記憶データの有効状態を真とした論理和演算を行い、得られた値の中で検索データの第（ｈ＋１）の優先順位を持つ部分検索領域に対応するビット領域のみを中間データ５９−（ｈ＋１）−ｋとして２次中間データ判定部６０−ｈ、および部分２次検索用連想メモリ５８−（ｈ＋１）−ｋに出力する。つまり第ｈの２次記憶データの中で検索データの第ｈ番目の優先順位を持つ部分検索領域に対応するビット領域のみを２次検索の対象とすることと、検索データの第（ｈ＋１）の優先順位を持つ部分検索領域に対応するビット領域のみから中間データ５９−ｈ−ｋを生成する機能が追加されていること以外は、図２６に示す従来の２次検索用連想メモリ３０３と同様に構成することができる。ｉ番目（ｉは０以上ｍ以下の整数）の連想メモリ・ワード６８−ｉ−ｈ−ｋには、対応する１次連想メモリ・ワード７−ｉ−ｋが格納している記憶データの中で、検索データの第ｈ番目と第（ｈ＋１）番目の優先順位を持つ部分検索領域に対応するビット領域と同じ値のみを第ｈの記憶データとして格納してもよいことはいうまでもない。
ｑ番目の部分２次検索用連想メモリ５８−ｑ−ｋは、連想メモリ・ワード６８−０−ｑ−ｋ〜６８−ｓ−ｑ−ｋを有し、ｉ番目（ｉは０以上ｍ以下の整数）の連想メモリ・ワード６８−ｉ−ｑ−ｋには、対応する１次連想メモリ・ワード７−ｉ−ｋが格納している記憶データと同じ値を第ｑの２次記憶データとして格納する。部分２次検索用連想メモリ５８−ｑ−ｋは、連想メモリ・ワード６８−０−ｑ−ｋ〜６８−ｓ−ｑ−ｋが格納している第ｑの２次記憶データの中で、検索データの第ｑ番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、中間データ５９−ｑ−ｋと比較を行い、一致する第ｑの２次記憶データに対応する一致線３−０−ｋ〜３−ｓ−ｋに一致線の有効順位を出力する。つまり第ｑの２次記憶データの中で検索データの第ｑ番目の優先順位を持つ部分検索領域に対応するビット領域のみを２次検索の対象とすること以外は、図２６に示す従来の２次検索用連想メモリ３０３と同様に構成することができる。ｉ番目（ｉは０以上ｍ以下の整数）の連想メモリ・ワード６８−ｉ−ｑ−ｋには、対応する１次連想メモリ・ワード７−ｉ−ｋが格納している記憶データの中で、検索データの第ｑ番目の優先順位を持つ部分検索領域に対応するビット領域と同じ値のみを第ｑの２次記憶データとして格納してもよいことはいうまでもない。
中間データ判定部７１は、図１１の中間データ判定部４８と比較すると、連想メモリ２０９−０〜２０９−ｒから入力される信号が中間データ５９−１−０〜５９−１−ｒに変更された他は、図１１の中間データ判定部４８と同様に構成することができる。図９の中間データ判定部４１に対して前記の修正を施すことによっても構成できることはいうまでもない。また、その場合には図９の中間データ演算部４２として、図１の中間データ演算部９、または図４の中間データ演算部２６、または図６の中間データ演算部、またはその他論理的に等価な手段にて構成できることもいうまでもない。中間データ判定部７１は、ｐ個の連想メモリ２０４−０〜２０４−ｒから入力されるｐ個の中間データ５９−１−０〜５９−１−ｒの中で、最も中間データの無効状態のビット数が少ないものに対応する有効検出信号６９−１−０〜６９−１−ｒに有効状態を出力する。
２次中間データ判定部６０−ｈ（ｈは１以上ｔ以下の整数）は、図１１の中間データ判定部４８と比較すると、連想メモリ２０９−０〜２０９−ｒから入力される信号が中間データ５９−（ｈ＋１）−０〜５９−（ｈ＋１）−ｒに変更された点と、有効検出信号６９−ｈ−０〜６９−ｈ−ｒが対応する無効状態ビット数計数手段６１−ｈ−０〜６１−ｈ−ｒと比較手段６５−ｈ−０〜６５−ｈ−ｒにそれぞれ入力される点のみが異なる。
ｋ番目の無効状態ビット数計数手段６１−ｈ−ｋは、対応する有効検出信号６９−ｈ−ｋが有効状態の時には、図１１の無効状態ビット数整数手段４９と同様に、対応する中間データ５９−（ｈ＋１）−ｋの中でネットワーク・アドレスの最下位階層側から上位階層側に連続している中間データの無効状態のビット数を最初の中間データの有効状態のビットが現れるまで計数した結果を無効状態ビット数信号６２−ｈ−ｋに出力し、対応する有効検出信号６９−ｈ−ｋが無効状態の時には無効状態ビット数信号６２−ｈ−ｋに対応する中間データ５９−（ｈ＋１）−ｋのビット数と同じ値を出力する。
最小値選択手段６３−ｈは、無効状態ビット数計数手段６１−ｈ−０〜６１−ｈ−ｒからそれぞれ入力される無効状態ビット数信号６２−ｈ−０〜６２−ｈ−ｒを比較し、その中の最小値を最小値信号６４−ｈとして比較手段６５−ｈ−０〜６５−ｈ−ｒに出力する。
ｋ番目の比較手段６５−ｈ−ｋは、有効検出信号６９−ｈ−ｋが有効状態の場合、かつ対応する無効状態ビット数信号６２−ｈ−ｋと最小値信号６４−ｈとを比較したときに一致する場合にのみ、対応する有効検出信号６９−（ｈ＋１）−ｋに有効状態を出力し、それ以外の場合には、対応する有効検出信号６９−（ｈ＋１）−ｋに無効状態を出力する。
これにより２次中間データ判定部６０−ｈは、ｐ個の連想メモリ２０９−０〜２０９−ｒから入力されるｐ個の中間データ５９−（ｈ＋１）−０〜５９−（ｈ＋１）−ｒの中で、対応する有効検出信号６９−ｈ−ｋが有効状態のもののみを対象として比較したときに最も中間データの無効状態のビット数が少ないものに対応する有効検出信号６９−（ｈ＋１）−０〜６９−（ｈ＋１）−ｒのみに有効状態を出力することになる。
論理積手段４６−０〜４６−ｒは、入力が有効検出信号６９−ｑ−０〜６９−ｑ−ｒに代わった点を除けば、図９の論理積手段４６−０〜４６−ｒと全く同様に構成することができる。また、アドレス信号生成部１１は、入力が一致線３−０−０〜３−ｓ−ｒでなく、実効一致線４７−０−０〜４７−ｓ−ｒに代わった点を除けば、図１のアドレス信号生成部１１と全く同様に構成することができる。もちろん、図３に示したアドレス信号生成部２５を用いても構成できることは言うまでもない。
また、本例の無効状態ビット数計数手段４９−０〜４９−ｒ、無効状態ビット数計数手段６１−ｈ−０〜６１−ｈ−ｒは、回路規模を削減するために、それぞれ対応する中間データにおけるネットワーク・アドレスの最下位階層側から上位階層側に連続している中間データの無効状態のビット数を、最初の中間データの有効状態のビットが現れるまで計数しているが、単純に対応する中間データの全ビットにおける無効状態の数を計数してもよいことは明らかである。
〔第６の実施例の動作〕
次に図１４を参照して、本発明の第６の実施の形態の連想メモリ・システム２１０の動作を、第１の優先順位を持つ４進表記で（２．１）と、第２の優先順位を持つ（１．３）の２個の部分検索領域を持つ８ビットの検索データ７０を入力とする４語８ビット構成の連想メモリ２０９−０、２０９−１の２個を接続し、かつ、構造化データをソート処理することなしにランダムな順番で１次連想メモリ・ワード７−０−０〜７−３−１に格納した場合の動作を例にして説明する。ここで、図１と同様に全体で８語のアドレス空間の中で連想メモリ２０９−１が上位側のアドレス空間を占めることとする。
図１と同様に、本例では以降、マスク情報の有効状態を“０”、無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”として説明する。また、記憶データと同様に、中間データ５９の有効状態を“１”、無効状態を“０”とする。一致線３の有効状態を“１”、無効状態を“０”として説明する。
１次検索用連想メモリ５７−０の４語の１次連想メモリ・ワード７−０−０〜７−３−０には、それぞれ４進表記の構造化データ（３．＊．１．３）、（２．＊．１．＊）、（１．＊．３．２）、（２．＊．１．３）を表現するように記憶データ、マスク・データを格納しているものとする。１次検索用連想メモリ５７−１の４語の１次連想メモリ・ワード７−０−１〜７−３−１には、それぞれ４進表記の構造化データ（２．３．１．３）、（２．１．１．＊）、（２．＊．＊．＊）、（２．１．＊．＊）を表現するように記憶データ、マスク情報を格納しているものとする。図２３で説明した従来の１次検索用連想メモリ３０２と同様に、ドント・ケア“＊”状態を表現するために、マスク情報の該当ビットにはマスク情報の有効状態“０”を、記憶データの該当ビットには記憶データの無効状態“０”を、それぞれ格納する。つまり１次連想メモリ・ワード７−０−０〜７−３−０には、記憶データとしてそれぞれ４進表記で（３．０．１．３）、（２．０．１．０）、（１．０．３．２）、（２．０．１．３）を格納し、マスク情報としてそれぞれ４進表記で（３．０．３．３）、（３．０．３．０）、（３．０．３．３）、（３．０．３．３）を格納している。１次連想メモリ・ワード７−０−１〜７−３−１には、記憶データとしてそれぞれ４進表記で（２．３．１．３）、（２．１．１．０）、（２．０．０．０）、（２．１．０．０）を格納し、マスク情報としてそれぞれ４進表記で（３．３．３．３）、（３．３．３．０）、（３．０．０．０）、（３．３．０．０）を格納している。また、各記憶データ、各マスク情報の上位４ビットが検索データ７０の第１の優先順位の部分検索領域に対応する領域とし、各記憶データ、各マスク情報の下位４ビットが検索データ７０の第２の優先順位の部分検索領域に対応する領域とする。
部分２次検索用連想メモリ５８−１−０の連想メモリ・ワード６８−ｉ−１−０（ｉは０以上３以下の整数）、および部分２次検索用連想メモリ５８−２−０の連想メモリ・ワード６８−ｉ−２−０には、１次検索用連想メモリ５７−０の対応する１次連想メモリ・ワード７−ｉ−０が格納している記憶データと同じ４進表記の値、（３．０．１．３）、（２．０．１．０）、（１．０．３．２）、（２．０．１．３）を、それぞれ第１の２次記憶データ、第２の２次記憶データとして格納しているものとする。
部分２次検索用連想メモリ５８−１−１の連想メモリ・ワード６８−ｉ−１−１（ｉは０以上３以下の整数）、および部分２次検索用連想メモリ５８−２−１の連想メモリ・ワード６８−ｉ−２−１には、１次検索用連想メモリ５７−１の対応する１次連想メモリ・ワード７−ｉ−１が格納している記憶データと同じ４進表記の値、（２．３．１．３）、（２．１．１．０）、（２．０．０．０）、（２．１．０．０）を、それぞれ第１の２次記憶データ、第２の２次記憶データとして格納しているものとする。
次に、４進表記で（２．１．１．３）の検索データ７０を入力したときの、連想メモリ２０９−０，２０９−１の動作について説明する。連想メモリ２０９−０では、まず１次検索用連想メモリ５７−０が、対応するマスク情報を考慮して検索データ７０と全ビットについて比較したときに一致する記憶データを検索する１次検索を行い、結果として１次連想メモリ・ワード７−１−０、７−３−０に格納されている４進表記の構造化データ（２．＊．１．＊）、（２．＊．１．３）が検索データ７０と一致する。１次検索用連想メモリ５７−０は、一致した１次連想メモリ・ワード７−１−０、７−３−０の中に格納されている４進表記の記憶データにおける、検索データ７０の第１の優先順位の部分検索領域に対応する領域、４進表記でそれぞれ（２．０）、（２．０）に対して記憶データの有効状態を真とした論理和演算を行い、得られた４進表記で（２．０）、２進表記で“１０００”の４ビットの演算結果を、中間データ５９−１−０として中間データ判定部７１と部分２次検索用連想メモリ５８−１−０に出力する。同様に、連想メモリ２０９−１では、まず１次検索用連想メモリ５７−１が、対応するマスク情報を考慮して検索データ７０と全ビットについて比較したときに一致する記憶データを検索する１次検索を行い、結果として１次連想メモリ・ワード７−１−１、７−２−１、７−３−１に格納されている４進表記の構造化データ（２．１．１．＊）、（２．＊．＊．＊）、（２．１．＊．＊）が検索データ７０と一致する。１次検索用連想メモリ５７−１は、一致した１次連想メモリ・ワード７−１−１、７−２−１、７−３−１の中に格納されている４進表記の記憶データにおける、検索データ７０の第１の優先順位の部分検索領域に対応する領域、４進表記でそれぞれ（２．１）、（２．０）、（２．１）に対して記憶データの有効状態を真とした論理和演算を行い、得られた４進表記で（２．１）、２進表記で“１００１”の４ビットの演算結果を、中間データ５９−１−１として中間データ判定部７１と部分２次検索用連想メモリ５８−１−１に出力する。
部分２次検索用連想メモリ５８−１−０では、連想メモリ・ワード６８−０−１−０〜６８−３−１−０に格納している第１の２次記憶データの中で検索データ７０の第１番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、４進表記で（２．０）の中間データ５９−１−０と比較する２次検索を行い、その結果連想メモリ・ワード６８−１−１−０、６８−３−１−０が一致する。部分２次検索用連想メモリ５８−１−０は、一致した連想メモリ・ワード６８−１−１−０、６８−３−１−０の中に格納されている第１の２次記憶データにおける、検索データ７０の第２の優先順位の部分検索領域に対応する領域、４進表記でそれぞれ（１．０）、（１．３）に対して記憶データの有効状態を真とした論理和演算を行い、得られた４進表記で（１．３）、２進表記で“０１１１”の４ビットの演算結果を、中間データ５９−２−０として２次中間データ判定部６０−１と部分２次検索用連想メモリ５８−２−０に出力する。同様に、部分２次検索用連想メモリ５８−１−１では、連想メモリ・ワード６８−０−１−１〜６８−３−１−１に格納している第１の２次記憶データの中で検索データ７０の第１番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、４進表記で（２．１）の中間データ５９−１−１と比較する２次検索を行い、その結果連想メモリ・ワード６８−１−１−１、６８−３−１−１が一致する。部分２次検索用連想メモリ５８−１−１は、一致した連想メモリ・ワード６８−１−１−１、６８−３−１−１の中に格納されている第１の２次記憶データにおける、検索データ７０の第２の優先順位の部分検索領域に対応する領域、４進表記でそれぞれ（１．０）、（０．０）に対して記憶データの有効状態を真とした論理和演算を行い、得られた４進表記で（１．０）、２進表記で“０１００”の４ビットの演算結果を、中間データ５９−２−１として２次中間データ判定部６０−１と部分２次検索用連想メモリ５８−２−１に出力する。
部分２次検索用連想メモリ５８−２−０では、連想メモリ・ワード６８−０−２−０〜６８−３−２−０に格納している第２の２次記憶データの中で検索データ７０の第２番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、４進表記で（１．３）の中間データ５９−２−０と比較する２次検索を行い、その結果連想メモリ・ワード６８−３−２−０が一致する。部分２次検索用連想メモリ５８−２−０は、一致した連想メモリ・ワード６８−３−２−０に対応する一致線３−３−０に一致線の有効状態を出力し、残りの一致線には無効状態を出力する。部分２次検索用連想メモリ５８−２−１では、連想メモリ・ワード６８−０−２−１〜６８−３−２−１に格納している第２の２次記憶データの中で検索データ７０の第２番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、４進表記で（１．０）の中間データ５９−２−１と比較する２次検索を行い、その結果連想メモリ・ワード６８−１−２−１が一致する。部分２次検索用連想メモリ５８−２−１は、一致した連想メモリ・ワード６８−１−２−１に対応する一致線３−１−１に一致線の有効状態を出力し、残りの一致線には無効状態を出力する。
中間データ判定部７１の無効状態ビット数計数手段４９−０は、中間データ５９−１−０の２進表記の値“１０００”の中で、最初の有効状態“１”が現れるまで、右側のビットから無効状態“０”を計数し、結果として得られる１０進表記で“３”の値を無効状態ビット数信号５０−０として出力する。無効状態ビット数計数手段４９−１は、中間データ５９−１−１の２進表記の値“１００１”の中で、最初の有効状態“１”が現れるまで、右側のビットから無効状態“０”を、計数し、結果として得られる１０進表記で“０”の値を無効状態ビット数信号５０−１として出力する。最小値選択手段５１は、無効状態ビット数計数手段４９−０〜４９−１からそれぞれ入力される無効状態ビット数信号５０−０、５０−１を比較し、その中の最小値である１０進表記の値“０”を最小値信号５２として比較手段５３−０〜５３−１に出力する。比較手段５３−０は、対応する無効状態ビット数信号５０−０の１０進表記の値“３”と、最小値信号５２の１０進表記の値“０”とを比較し、一致しないので有効検出信号６９−１−０に無効状態を出力する。比較手段５３−１は、対応する無効状態ビット数信号５０−１の１０進表記の値“０”と、最小値信号５２の１０進表記の値“０”とを比較し、一致するので有効検出信号６９−１−１に有効状態を出力する。
２次中間データ判定部６０−１の無効状態ビット数計数手段６１−１−０は、中間データ５９−２−０の２進表記の値“０１１１”の中で、最初の有効状態“１”が現れるまで、右側のビットから無効状態“０”を計数した結果、１０進表記で“０”の値を得る。ここで対応する有効検出信号６９−１−０が無効状態であるため無効状態ビット数計数手段６１−１−０は、１０進表記の計数結果“０”ではなく計数結果中間データ５９−２−０のビット数の１０進表記の値“４”を、無効状態ビット数信号６２−１−０として出力する。無効状態ビット数計数手段６１−１−１は、中間データ５９−２−１の２進表記の値“０１００”の中で、最初の有効状態“１”が現れるまで、右側のビットから無効状態“０”を計数した結果１０進表記で“２”の値を得る。ここで対応する有効検出信号６９−１−１が有効状態であるため無効状態ビット数計数手段６１−１−１は、１０進表記の計数結果“２”を無効状態ビット数信号６２−１−１として出力する。最小値選択手段６３−１は、無効状態ビット数計数手段６１−１−０〜６１−１−１からそれぞれ入力される無効状態ビット数信号６２−１−０、６２−１−１を比較し、その中の最小値である１０進表記の値“２”を最小値信号６４−１として比較手段６５−１−０〜６５−１−１に出力する。比較手段６５−１−０は、有効検出信号６９−１−０が無効状態であるので、有効検出信号６９−２−０に無効状態を出力する。比較手段６５−１−１は、有効検出信号６９−１−０が有効状態であるため、対応する無効状態ビット数信号６２−１−１の１０進表記の値“２”と最小値信号６４−１の１０進表記の値“２”とを比較し、一致するので有効検出信号６９−２−１に有効状態を出力する。検索データ７０の２番目の優先順位の部分ビット領域に対応する中間データ５９−２−０〜５９−２−１の中だけで判定したときには、連想メモリ２０９−０が出力する中間データ５９−２−０が最適であるが、すでに連想メモリ２０９−０は中間データ判定部７１により有効でないと判定されているため、中間データ５９−２−０は判定対象から除外されることになる。
論理積手段４６−０は、対応する有効検出信号６９−２−０が無効状態であるので、実効一致線４７−０−０〜４７−３−０すべてに一致線の無効状態を出力する。したがって、実効一致線４７−０−０〜４７−３−０は２進表記で“００００”となる。論理積手段４６−１は、対応する有効検出信号６９−２−１が有効状態であるので、連想メモリ２０９−１から出力される一致線３−０−１〜３−３−１の２進表記の値“００１０”を実効一致線４７−０−１〜４７−３−１に出力する。
したがって、アドレス信号生成部１１に入力される信号の中で有効状態である信号は実効一致線４７−１−１の一本のみとなり、アドレス信号生成部１１は２進表記の値“１０１”をアドレス出力信号１２として出力する。図１４の例では、４進表記で（２．１）の第１の優先順位の部分検索領域と４進表記で（１．３）の第２の優先順位の部分検索領域を有する検索データ７０に対して一致する構造化データの中で、マスク情報の有効状態のビット数が最小のものは、連想メモリ２０９−１の１次連想メモリ・ワード７−１−１に格納している４進表記で（２．１．１．＊）であることは明らかである。したがって、アドレス信号生成部１１は正しいアドレス出力信号１２を出力していることが分かる。
本実施例の連想メモリ２０９−ｋでは、中間データ５９−１−ｋを入力とした部分２次検索用連想メモリ５８−１−ｋによる部分２次検索と、中間データ判定部７１による連想メモリ２０９−ｋが格納している構造化データが最適かどうかの判断を並列実行し、また、中間データ５９−（ｈ＋１）−ｋ（ｈは１以上ｔ以下の整数）を入力とした部分２次検索用連想メモリ５８−（ｈ＋１）−ｋによる部分２次検索と、２次中間データ判定部６０−ｈによる連想メモリ２０９−ｋの格納している構造化データが最適であり続けているかどうかの判断を並列実行し、最終的に論理積手段４６−ｋにより連想メモリ２０９−ｋの格納している構造化データが最適であり続けた場合のみ、連想メモリ２０９−ｋが出力する一致線３−０−ｋ〜３−ｓ−ｋの状態をアドレス信号生成部１１に出力することによって、連想メモリ・システム２１０全体として最適なアドレス信号１２を得る構成となっている。したがって、２次検索と中間データの判定を並列実行することができるため、連想メモリ・システム２１０全体としての演算速度が連想メモリ２０９単体の演算速度から低下することはない。
中間データ５９−ｈ−ｋを部分２次検索用連想メモリ５８−ｈ−ｋに入力してから中間データ５９−（ｈ＋１）−ｋが出力されるまでに図示しないクロック信号により遅延が生じる場合、または中間データ５９−ｑ−ｋを部分２次検索用連想メモリ５８−ｑ−ｋに入力してから一致線３−０−ｋ〜３−ｓ−ｋに出力されるまでに図示しないクロック信号により遅延が生じる場合には、同期を取るために有効検出信号６９−ｈ−ｋ、６９−ｑ−ｋにクロック信号を入力とする記憶手段を適宜挿入すればよいことは明らかである。例えば図１３の場合、中間データ５９−１−ｋが入力されてから中間データ５９−２−ｋが出力されるまで、および中間データ５９−２−ｋが入力されてから一致線３−０−ｋ〜３−３−ｋが出力されるまで、それぞれ図示しないクロック信号で１クロックずつ要する場合には、同期を取るために有効検出信号６９−１−ｋ、６９−２−ｋに１クロック遅延する記憶手段を１個挿入することにより、パイプライン構成を実現できる。これにより、連想メモリ・システムの最高動作周波数を大きく向上させることができる。
もちろん中間データ判定部７１と、２次中間データ判定部６０−１〜６０−ｑと、論理積手段４６−０〜４６−ｒを有さずに、図１に示す本発明の第１の実施の形態の連想メモリ・システム２００と同様に、連想メモリ２０９−０〜２０９−ｒが出力する中間データ５９−ｊ−０〜５９−ｊ−ｒ（ｊは１以上ｑ以下の整数）を、図１に示す中間データ演算部９と同様に構成されるｊ番目の中間データ演算部に入力した結果得られるｊ番目の最適化中間データを部分２次検索用連想メモリ５８−ｊ−０〜５９−ｊ−ｒに入力し、連想メモリ２０９−０〜２０９−ｒが出力する一致線３−０−０〜３−ｓ−ｒをアドレス信号生成部１１に直接入力するように構成しても、正しいアドレス出力信号１２を得られることは明らかである。このとき、ｊ番目の中間データ演算部としては、図４に示した中間データ演算部２６、または図６に示した中間データ演算部２８と同様に構成できることは言うまでもない。また、図８に示した第３の実施の形態の連想メモリ・システム２０３のように、ｊ番目の最適化中間データを結線論理により生成する構成にしても構わないことも明らかである。これらにより回路構成を簡略化することが可能である。また、この場合には、部分２次検索用連想メモリ５８−ｊ−０〜５８−ｊ−ｒは、（ｍ×ｐ）語の１個の連想メモリにより構成してもよいことはいうまでもない。また、全体で（ｍ×ｐ）語を容量を持つ任意の個数の連想メモリによっても構成できることも明らかである。
また、本例では、無効状態ビット数計数手段６１−ｈ−ｋは、有効検出信号６９−ｈ−ｋが無効状態の場合には、中間データ５９−（ｈ＋１）−ｋのビット数を出力したが、中間データ５９−（ｈ＋１）−ｋのビット数よりも大きい値を出力してもよいことはいうまでもない。ここで、図１３に示す連想メモリ・システム２１０において、連想メモリ２０９−ｋに対応する無効状態ビット数計数手段４９−ｋ、無効状態ビット数計数手段６１−１−ｋ〜６１−ｈ−ｋを連想メモリ２０９−ｋに内蔵した場合には、図１１に示す連想メモリ・システム２０６の説明と同様に、大幅に長い配線の本数を削減することが可能となるとともに、各連想メモリ２０９に必要な端子の数を大幅に削減することができる。さらに、信号遅延時間、配線容量による消費電力などを削減できる。配線領域の減少によりさらに面積を削減可能である。また、各連想メモリの端子数が大幅に削減されるため面積をさらに削減することが可能である。また、１次検索終了時に有効検出信号６９にすべて有効状態が入力されている２次中間データ判定部６０を、中間データ判定部７１の代わりに用いることができるのは明らかである
〔２次中間データ判定部の第２の構成例〕
次に、本発明の連想メモリ・システムの２次中間データ判定部の第２の構成例について説明する。図１５は、本発明の連想メモリ・システム２１０の２次中間データ判定部の第２の構成例を示すブロック図である。第２の構成例の、ｈ番目（ｈは１以上ｔ以下の整数）の２次中間データ判定部７２−ｈは、中間データ演算部７５−ｈと、ｐ個の比較手段７８−ｈ−０〜７８−ｈ−ｒと、ｐ個の無効化手段７３−ｈ−０〜７３−ｈ−ｒから構成される。
第２の構成例の２次中間データ判定部７２−ｈは、図９の中間データ判定部４１と比較すると、有効検出信号６９−ｈ−０〜６９−ｈ−ｒが入力されている点と、ｋ番目の連想メモリ２０９−ｋから入力される中間データ５９−（ｈ＋１）−ｋと中間データ演算部７５−ｈの間に無効化手段７３−ｈ−ｋが挿入されている点と、有効検出信号６９−ｈ−ｋが無効化手段７３−ｈ−ｋと比較手段７８−ｈ−ｋに入力されている点のみが異なり、他は同様に構成される。
ｋ番目の無効化手段７３−ｈ−ｋは、有効検出信号６９−ｈ−ｋが有効状態の場合には、実効中間データ７４−ｈ−ｋとして中間データ５９−（ｈ＋１）−ｋを出力し、有効検出信号６９−ｈ−ｋが無効状態の場合には、実効中間データ７４−ｈ−ｋの全ビットに中間データの無効状態を出力する。
中間データ演算部７５−ｈは、ｐ個の実効中間データ７４−ｈ−０〜７４−ｈ−ｒの中で、最も中間データの無効状態のビット数が少ないものを最適化中間データ７７−ｈとして比較手段７８−ｈ−０〜７８−ｈ−ｒに出力する。図１５に示す中間データ演算部７５−ｈは、図１に示した中間データ演算部９と全く同様に、論理和手段７６−ｋから構成される。無効状態の有効検出信号６９−ｈ−０〜６９−ｈ−ｒに対応する実効中間データ７４−ｈ−０〜７４−ｈ−ｒの全ビットは中間データの無効状態となっているため、論理和演算結果には影響しないことになる。
ｋ番目の比較手段７８−ｈ−ｋは、有効検出信号６９−ｈ−ｋが有効状態の場合、かつ対応する実効中間データ７４−ｈ−ｋと最適化中間データ７７−ｈとを比較したときに一致する場合にのみ、対応する有効検出信号６９−（ｈ＋１）−ｋに有効状態を出力し、それ以外の場合には、対応する有効検出信号６９−（ｈ＋１）−ｋに無効状態を出力する。
これにより２次中間データ判定部７２−ｈは、図１３に示す２次中間データ判定部６０−ｈと同様に、ｐ個の連想メモリ２０９−０〜２０９−ｒから入力されるｐ個の中間データ５９−（ｈ＋１）−０〜５９−（ｈ＋１）−ｒの中で、対応する有効検出信号６９−ｈ−ｋが有効状態のもののみを対象として比較したときに最も中間データの無効状態のビット数が少ないものに対応する有効検出信号６９−（ｈ＋１）−０〜６９−（ｈ＋１）−ｒに有効状態を出力することになる。
〔２次中間データ判定部の第３の構成例〕
次に、本発明の連想メモリ・システムの２次中間データ判定部の第３の構成例について説明する。図１６は、本発明の連想メモリ・システム２１０の２次中間データ判定部の第３の構成例を示すブロック図である。第３の構成例の、ｈ番目（ｈは１以上ｔ以下の整数）の２次中間データ判定部７９−ｈは、中間データ演算部８０−ｈと、ｐ個の比較手段７８−ｈ−０〜７８−ｈ−ｒと、ｐ個の無効化手段７３−ｈ−０〜７３−ｈ−ｒから構成される。
第２の構成例の２次中間データ判定部７９−ｈは、図１５の第２の構成例の２次中間データ判定部７２−ｈと比較すると、中間データ演算部８０−ｈが図４に示す中間データ演算部２６と同様に最大値選択手段８１−ｈにより構成されている点のみが異なり、他は同様に構成される。
ここで無効状態の有効検出信号６９−ｈ−０〜６９−ｈ−ｒに対応する実効中間データ７４−ｈ−０〜７４−ｈ−ｒの全ビットは中間データの無効状態となっているため、最大値選択の結果には影響しないことになる。
したがって、２次中間データ判定部７９−ｈは、図１３に示す２次中間データ判定部６０−ｈと同様に、ｐ個の連想メモリ２０９−０〜２０９−ｒから入力されるｐ個の中間データ５９−（ｈ＋１）−０〜５９−（ｈ＋１）−ｒの中で、対応する有効検出信号６９−ｈ−ｋが有効状態のもののみを対象として比較したときに最も中間データの無効状態のビット数が少ないものに対応する有効検出信号６９−（ｈ＋１）−０〜６９−（ｈ＋１）−ｒに有効状態を出力することになる。ここで、図６に示す中間データ演算部２８を用いて２次中間データ判定部７２−１〜７２−ｔを構成しても、正しい有効検出信号有効検出信号６９−（ｈ＋１）−０〜６９−（ｈ＋１）−ｒが得られることは言うまでもない。
また、以上説明した第６の本発明の連想メモリ・システム２１０を構成するｋ番目の１次検索用連想メモリ５７−ｋの構成要素と、対応する部分２次検索用連想メモリ５８−１−ｋ〜５８−ｑ−ｋの構成要素の一部を兼用することにより面積を削減できることも明らかである。例えば、ｉ番目の１次連想メモリ・ワード７−ｉ−ｋにおける記憶データを格納するための手段と、対応する連想メモリ・ワード６８−ｉ−１−ｋ〜６８−ｉ−ｑ−ｋにおける第１乃至第ｑの２次記憶データを格納するための手段には、同じ値が格納されるため、兼用することが可能である。
〔第７の実施例の構成〕
次に、本発明の第７の実施の形態の連想メモリ・システムについて図面を参照して詳細に説明する。第７の実施の形態は、複数の部分検索領域から構成される検索データに対してマスク情報を考慮して検索を行ったときに入力データに対応する記憶データがすべて一致するワードが複数個あった場合に優先順位を考慮して部分検索領域ごとに構造化データを構成するマスク情報のマスク有効状態のビット数を一致したワードの中で比較した結果、最少となるようなワードを識別する信号を出力する機能を、クロック信号に応じて１次検索、および各部分２次検索の実行を選択するための信号を出力する制御回路を内蔵することにより１次検索用連想メモリ、２次検索用連想メモリの構成手段を共有する、例えば国際出願番号ＰＣＴ／ＪＰ０１／０３５６２に示される連想メモリを、複数個接続した場合の連想メモリ・システムの構成例である。
図１７は、本発明の第７の実施の形態のｎビット（ｍ×ｐ）語の連想メモリ・システム２１２の構成例を示すブロック図である。連想メモリ・システム２１２は、ｑ個の部分検索領域から構成される検索データ７０を入力とするｐ個のｍ語ｎビットの連想メモリ２１１−０〜２１１−ｒと、ｐ個の論理積手段９９−０〜９９−ｒと、ｐ個の記憶手段８９−０〜８９−ｒと、制御手段９１と、中間データ判定部８５と、アドレス信号１２を出力するアドレス信号生成部１１と、から構成される。ｋ番目の連想メモリ２１１−ｋは、それぞれクロック信号５５によって制御される、記憶手段８７−ｋと１次２次検索兼用連想メモリ８２−ｋとを有する。
１次２次検索兼用連想メモリ８２−ｋは、検索データ７０の全ての部分検索領域を検索対象とする各ｎビットの記憶データおよびマスク情報から構成される構造化データをｍ個格納できる連想メモリ・ワード８４−０−ｋ〜８４−ｓ−ｋを有する。ここで、構造化データのドント・ケア“＊”状態のビットは、記憶データの該当ビットを記憶データの無効状態とし、マスク情報の該当ビットをマスク・データの有効状態とすることにより表現される。クロック信号５５の１クロック目では、１次２次検索兼用連想メモリ８２−ｋは、対応するマスク情報を考慮して検索データ７０の全ての部分検索領域と比較した結果一致する記憶データを検索する１次検索を連想メモリ・ワード８４−０−ｋ〜８４−ｓ−ｋの中で行い、一致する記憶データ同士に対して記憶データの有効状態を真とした論理和演算を行い、得られた値の中で検索データの第１の優先順位を持つ部分検索領域に対応するビット領域のみを中間データ８３−ｋとして、中間データ判定部８５に出力するとともに、次のクロックへの移行時に記憶手段８７−ｋに格納する。（ｈ＋１）クロック目（ｈは１以上ｑ以下の整数）の動作では、１次２次検索兼用連想メモリ８２−ｋは、連想メモリ・ワード８４−０−ｋ〜８４−ｓ−ｋが格納している記憶データの中で、検索データの第ｈ番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、記憶手段８７−ｋから出力される前段中間データ８８−ｋと比較を行い、一致する記憶データ同士に対して記憶データの有効状態を真とした論理和演算を行い、得られた値の中で検索データの第（ｈ＋１）の優先順位を持つ部分検索領域に対応するビット領域のみを中間データ８３−ｋとして中間データ判定部８５に出力するとともに、次のクロックへの移行時に記憶手段８７−ｋに格納する。また、各１次検索、２次検索実行毎に、一致した連想メモリ・ワード８４−０−ｋ〜８４−ｓ−ｋに対応する一致線３−０−ｋ〜３−ｓ−ｋに有効状態を出力する。ｑ番目の優先順位を持つ部分検索領域に対応する２次検索実行後のみ一致した一致した連想メモリ・ワード８４−０−ｋ〜８４−ｓ−ｋに対応する一致線３−０−ｋ〜３−ｓ−ｋに有効状態を出力し、その他の検索動作終了時には一致線の値を保持する構成にしてもよいことは言うまでもない。また、ｑ番目の優先順位を持つ部分検索領域に対応する２次検索実行後には、中間データ８３−ｋとして任意の値を出力して構わない。例えば全ビットが中間データの有効状態、または無効状態を出力しても構わないし、直前の値を保持しても構わないことはいうまでもない。
中間データ判定部８５は、図１３の２次中間データ判定部６０と比較すると、入力信号の名称が中間データ８３−０〜８３−ｒ、有効保持信号９０−０〜９０−ｒに変更された他は、図１３の２次中間データ判定部６０と全く同様に構成することができる。中間データ判定部８５は、ｐ個の連想メモリ２１１−０〜２１１−ｒから入力されるｐ個の中間データ８３−０〜８３−ｒの中で、対応する有効保持信号９０−ｋが有効状態のもののみを対象として比較したときに最も中間データの無効状態のビット数が少ないものに対応する有効検出信号８６−０〜８６−ｒに有効状態を出力する。
論理積手段９９−０〜９９−ｒは、入力信号の名称が有効保持信号９０−０〜９０−ｒに変更された他は、図１３の論理積手段４６−０〜４６−ｒと全く同様に構成することができる。また、アドレス信号生成部１１は、入力が一致線３−０−０〜３−ｓ−ｒでなく、実効一致線４７−０−０〜４７−ｓ−ｒに代わった点を除けば、図１のアドレス信号生成部１１と全く同様に構成することができる。もちろん、図３に示したアドレス信号生成部２５を用いても構成できることは言うまでもない。ここで、１次２次兼用連想メモリ８２−０〜８２−ｒが、１次検索、２次検索毎に一致した連想メモリ・ワード８４−０−０〜８４−ｓ−ｒに対応する一致線３−０−０〜３−ｓ−ｒに有効状態を出力する場合、ｑ番目の優先順位を持つ部分検索領域に対応する２次検索実行後のアドレス出力信号１２が、検索データ７０に対する正しい検索結果であり、他の検索実行後のアドレス出力信号１２の値は無視するものとする。もちろん、ｑ番目の優先順位を持つ部分検索領域に対応する２次検索実行後のアドレス出力信号１２の値を、他の検索実行後にも保持し続けるように構成してもよいことは言うまでもない。
制御手段９１は、クロック信号５５に応じて、１次検索の実行前に初期化信号９２に有効状態を出力し、１次検索、２次検索が終了するたびに記憶制御信号９３に有効状態を出力する。ｑ番目の優先順位を持つ部分検索領域に対応する２次検索実行後には記憶制御信号９３に無効状態を出力してもよい。また、前記の１次２次兼用連想メモリ８２−０〜８２−ｒは、１次検索、２次検索ともに１クロックで終了する場合を例として説明したが、複数クロックを要する場合には、中間データ８３−０〜８３−ｒ、一致線（３−０−０〜３−ｓ−０）〜（３−０−ｒ〜３−ｓ−ｒ）の出力されるタイミングに同期するように、制御手段９１は記憶制御信号９３に有効状態を出力すればよいことは言うまでもない。
記憶手段８９−０〜８９−ｒは、初期化信号９２が有効状態の時には、格納している状態を有効状態に変更する。また、記憶制御信号９３が有効状態の時には、対応する有効検出信号８６−０〜８６−ｒの状態を格納する。記憶手段８９−０〜８９−ｒは、格納している状態を、それぞれ対応する有効保持信号９０−０〜９０−ｒに出力する。
〔第７の実施例の動作〕
次に図１８、図１９、および図２０を参照して、本発明の第７の実施の形態の連想メモリ・システム２１２の動作を、第１の優先順位を持つ４進表記で（２．１）と、第２の優先順位を持つ（１．３）の２個の部分検索領域を持つ８ビットの検索データ７０を入力とする４語８ビット構成の連想メモリ２１１−０、２１１−１の２個を接続し、かつ、構造化データをソート処理することなしにランダムな順番で連想メモリ・ワード８４−０−０〜８４−３−１に格納した場合の動作を例にして説明する。ここで、図１と同様に全体で８語のアドレス空間の中で連想メモリ２１１−１が上位側のアドレス空間を占めることとする。また、１次２次兼用連想メモリ８２−０〜８２−１は、１次検索、２次検索ともに１クロックで終了するものとする。また、１次検索、２次検索毎に一致した連想メモリ・ワード８４−０−０〜８４−３−１に対応する一致線３−０−０〜３−３−１に有効状態を出力するものとする。
図１と同様に、本例では以降、マスク情報の有効状態を“０”、無効状態を“１”とし、記憶データの有効状態を“１”、無効状態を“０”として説明する。また、記憶データと同様に、中間データ５９の有効状態を“１”、無効状態を“０”とする。一致線３の有効状態を“１”、無効状態を“０”として説明する。
図１４の１次検索メモリ５７−０と同様に、１次２次検索兼用連想メモリ８２−０の４語の連想メモリ・ワード８４−０−０〜８４−３−０には、それぞれ４進表記の構造化データ（３．＊．１．３）、（２．＊．１．＊）、（１．＊．３．２）、（２．＊．１．３）を表現するように記憶データ、マスク・データを格納しているものとし、１次２次検索兼用連想メモリ８２−１の４語の連想メモリ・ワード８４−０−１〜８４−３−１には、それぞれ４進表記の構造化データ（２．３．１．３）、（２．１．１．＊）、（２．＊．＊．＊）、（２．１．＊．＊）を表現するように記憶データ、マスク情報を格納しているものとする。図２３で説明した従来の１次検索用連想メモリ３０２と同様に、ドント・ケア“＊”状態を表現するために、マスク情報の該当ビットにはマスク情報の有効状態“０”を、記憶データの該当ビットには記憶データの無効状態“０”を、それぞれ格納する。つまり連想メモリ・ワード８４−０−０〜８４−３−０には、記憶データとしてそれぞれ４進表記で（３．０．１．３）、（２．０．１．０）、（１．０．３．２）、（２．０．１．３）を格納し、マスク情報としてそれぞれ４進表記で（３．０．３．３）、（３．０．３．０）、（３．０．３．３）、（３．０．３．３）を格納している。連想メモリ・ワード８４−０−１〜８４−３−１には、記憶データとしてそれぞれ４進表記で（２．３．１．３）、（２．１．１．０）、（２．０．０．０）、（２．１．０．０）を格納し、マスク情報としてそれぞれ４進表記で（３．３．３．３）、（３．３．３．０）、（３．０．０．０）、（３．３．０．０）を格納している。また、各記憶データ、各マスク情報の上位４ビットが検索データ７０の第１の優先順位の部分検索領域に対応する領域とし、各記憶データ、各マスク情報の下位４ビットが検索データ７０の第２の優先順位の部分検索領域に対応する領域とする。
次に４進表記で（２．１．１．３）の検索データ７０を入力したときの連想メモリ・システム２１２の１クロック目の動作例について、図１８を参照して説明する。
連想メモリ２１１−０では、まず１次２次検索兼用連想メモリ８２−０が、対応するマスク情報を考慮して検索データ７０と全ビットについて比較したときに一致する記憶データを検索する１次検索を行い、結果として連想メモリ・ワード８４−１−０、８４−３−０に格納されている４進表記の構造化データ（２．＊．１．＊）、（２．＊．１．３）が検索データ７０と一致する。１次２次検索兼用連想メモリ８２−０は、一致した１次連想メモリ・ワード８４−１−０、８４−３−０の中に格納されている４進表記の記憶データにおける、検索データ７０の第１の優先順位の部分検索領域に対応する領域、４進表記でそれぞれ（２．０）、（２．０）に対して記憶データの有効状態を真とした論理和演算を行い、得られた４進表記で（２．０）、２進表記で“１０００”の４ビットの演算結果を、中間データ８３−０として中間データ判定部８５に出力するとともに１クロック目から２クロック目に移行する時に記憶手段８７−０に格納する。
同様に、連想メモリ２１１−１では、まず１次２次検索兼用連想メモリ８２−１が、対応するマスク情報を考慮して検索データ７０と全ビットについて比較したときに一致する記憶データを検索する１次検索を行い、結果として連想メモリ・ワード８４−１−１、８４−２−１、８４−３−１に格納されている４進表記の構造化データ（２．１．１．＊）、（２．＊．＊．＊）、（２．１．＊．＊）が検索データ７０と一致する。１次２次検索兼用連想メモリ８２−１は、一致した連想メモリ・ワード８４−１−１、８４−２−１、８４−３−１の中に格納されている４進表記の記憶データにおける、検索データ７０の第１の優先順位の部分検索領域に対応する領域、４進表記でそれぞれ（２．１）、（２．０）、（２．１）に対して記憶データの有効状態を真とした論理和演算を行い、得られた４進表記で（２．１）、２進表記で“１００１”の４ビットの演算結果を、中間データ８３−１として中間データ判定部８５に出力するとともに１クロック目から２クロック目に移行する時に記憶手段８７−１に格納する。
連想メモリ２１１−０、２１１−１が１次検索を開始する前に、記憶手段８９−０，８９−１がそれぞれ格納している値は、制御手段９１から入力される初期化信号９２によって、有効状態に初期化されているものとする。したがって、記憶手段８９−０は有効保持信号９０−０に有効状態“１”を、記憶手段８９−１は有効保持信号９０−１に有効状態“１”を出力している。
連想メモリ２１１−０からは一致線３−１−０、３−３−０に有効状態が出力され、連想メモリ２１１−１からは一致線３−１−１，３−２−１、３−３−１に有効状態が出力される。有効保持信号９０−０、９０−１がそれぞれ有効状態のため、論理積手段９９−０、９９−１から入力される実行一致線４７−０−０〜４７−３−１によって、アドレス信号生成部１１から“不定”状態のアドレス出力信号１２が出力される。ここで、１クロック目の連想メモリ２１１−０〜２１１−１の動作は２番目の優先順位を持つ部分検索領域に対応する２次検索の実行ではないため、アドレス出力信号１２の値は無効であり、本動作例では無視する。
有効保持信号９０−０、９０−１がそれぞれ有効状態のため、中間データ判定部８５は中間データ８３−０、８３−１の無効状態のビット数を比較し、最も無効状態のビット数が少ない中間データ８３−１に対応する有効検出信号８６−１に有効状態“１”を出力し、他の有効検出信号８６−０には無効状態“０”を出力する。
制御手段９１が記憶制御信号９３に有効状態を出力しているため、１クロック目から２クロック目に移行するときに記憶手段８９−０は有効検出信号８６−０の無効状態“０”を、記憶手段８９−１は有効検出信号８６−１の有効状態“１”を、それぞれ格納する。
次に４進表記で（２．１．１．３）の検索データ７０を入力したときの連想メモリ・システム２１２の２クロック目の動作例について、図１９を参照して説明する。
１次２次検索兼用連想メモリ８２−０では、連想メモリ・ワード８４−０−０〜８４−３−０に格納している記憶データの中で検索データ７０の第１番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、記憶手段８７−０から出力される４進表記で（２．０）の前段中間データ８８−０と対応するマスク情報を考慮せずに比較する２次検索を行い、その結果連想メモリ・ワード８４−１−０、８４−３−０が一致する。１次２次検索兼用連想メモリ８２−０は、一致した連想メモリ・ワード８４−１−０、８４−３−０の中に格納されている４進表記の記憶データにおける、検索データ７０の第２の優先順位の部分検索領域に対応する領域、４進表記でそれぞれ（１．０）、（１．３）に対して記憶データの有効状態を真とした論理和演算を行い、得られた４進表記で（１．３）、２進表記で“０１１１”の４ビットの演算結果を、中間データ８３−０として中間データ判定部８５に出力するとともに２クロック目から３クロック目に移行する時に記憶手段８７−０に格納する。
同様に、１次２次検索兼用連想メモリ８２−１では、連想メモリ・ワード８４−０−１〜８４−３−１に格納している記憶データの中で検索データ７０の第１番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、記憶手段８７−１から出力される４進表記で（２．１）の前段中間データ８８−１と対応するマスク情報を考慮せずに比較する２次検索を行い、その結果連想メモリ・ワード８４−１−１、８４−３−１が一致する。１次２次検索兼用連想メモリ８２−１は、一致した連想メモリ・ワード８４−１−１、８４−３−１の中に格納されている４進表記の記憶データにおける、検索データ７０の第２の優先順位の部分検索領域に対応する領域、４進表記でそれぞれ（１．０）、（０．０）に対して記憶データの有効状態を真とした論理和演算を行い、得られた４進表記で（１．０）、２進表記で“０１００”の４ビットの演算結果を、中間データ８５−１として中間データ判定部８５に出力するとともに２クロック目から３クロック目に移行する時に記憶手段８７−１に格納する。
連想メモリ２１１−０からは一致線３−１−０、３−３−０に有効状態が出力され、連想メモリ２１１−１からは一致線３−１−１，３−３−１に有効状態が出力される。有効保持信号９０−１が有効状態のため、論理積手段９９−０、９９−１から入力される実行一致線４７−０−０〜４７−３−１によって、アドレス信号生成部１１から“不定”状態のアドレス出力信号１２が出力される。ここで、２クロック目の連想メモリ２１１−０〜２１１−１の動作は２番目の優先順位を持つ部分検索領域に対応する２次検索の実行ではないため、アドレス出力信号１２の値は無効であり、本動作例では無視する。
有効保持信号９０−０が無効状態のため、中間データ判定部８５は中間データ８３−１を対象として無効状態のビット数を比較し、最も無効状態のビット数が少ない中間データ８３−１に対応する有効検出信号８６−１に有効状態“１”を出力し、他の有効検出信号８６−０には無効状態“０”を出力する。
制御手段９１が記憶制御信号９３に有効状態を出力しているため、２クロック目から３クロック目に移行するときに記憶手段８９−０は有効検出信号８６−０の無効状態“０”を、記憶手段８９−１は有効検出信号８６−１の有効状態“１”を、それぞれ格納する。
次に４進表記で（２．１．１．３）の検索データ７０を入力したときの連想メモリ・システム２１２の３クロック目の動作例について、図２０を参照して説明する。
１次２次検索兼用連想メモリ８２−０では、連想メモリ・ワード８４−０−０〜８４−３−０に格納している記憶データの中で検索データ７０の第２番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、記憶手段８７−０から出力される４進表記で（１．３）の前段中間データ８８−０と対応するマスク情報を考慮せずに比較する２次検索を行い、その結果連想メモリ・ワード８４−３−０が一致し、対応する一致線３−３−０に一致線の有効状態を出力する。１次２次検索兼用連想メモリ８２−０は、検索データ７０のすべての部分検索領域に対して２次検索を終了したため、本例では中間データ８３−０として中間データの全ビットが有効状態の値を中間データ判定部８５に出力するとともに３クロック目から４クロック目に移行する時に記憶手段８７−０に格納する。
同様に、１次２次検索兼用連想メモリ８２−１では、連想メモリ・ワード８４−０−１〜８４−３−１に格納している記憶データの中で検索データ７０の第２番目の優先順位を持つ部分検索領域に対応するビット領域のみを対象として、記憶手段８７−１から出力される４進表記で（１．０）の前段中間データ８８−１と対応するマスク情報を考慮せずに比較する２次検索を行い、その結果連想メモリ・ワード８４−１−１が一致し、対応する一致線３−１−１に一致線の有効状態を出力する。１次２次検索兼用連想メモリ８２−１は、検索データ７０のすべての部分検索領域に対して２次検索を終了したため、本例では中間データ８５−１として中間データの全ビットが有効状態の値を中間データ判定部８５に出力するとともに３クロック目から４クロック目に移行する時に記憶手段８７−１に格納する。
有効保持信号９０−０が無効状態のため、中間データ判定部８５は中間データ８３−１を対象として無効状態のビット数を比較し、最も無効状態のビット数が少ない中間データ８３−１に対応する有効検出信号８６−１に有効状態“１”を出力し、他の有効検出信号８６−０には無効状態“０”を出力する。
制御手段９１が記憶制御信号９３に無効状態を出力しているため、記憶手段８９−０は無効状態“０”を、記憶手段８９−１は有効状態“１”を、それぞれ保持し続ける。
論理積手段９９−０は、対応する有効保持信号９０−０が無効状態であるので、実効一致線４７−０−０〜４７−３−０すべてに一致線の無効状態を出力する。したがって、実効一致線４７−０−０〜４７−３−０は２進表記で“００００”となる。論理積手段９９−１は、対応する有効保持信号９０−１が有効状態であるので、連想メモリ２１１−１から出力される一致線３−０−１〜３−３−１の２進表記の値“００１０”を実効一致線４７−０−１〜４７−３−１に出力する。したがって、アドレス信号生成部１１に入力される信号の中で有効状態である信号は実効一致線４７−２−１の一本のみとなり、アドレス信号生成部１１は２進表記の値“１０１”をアドレス出力信号１２として出力する。図１８，図１９、図２０の例では、４進表記で（２．１）の第１の優先順位の部分検索領域と４進表記で（１．３）の第２の優先順位の部分検索領域を有する検索データ７０に対して、一致する連想メモリ・システム２１２が格納している構造化データの中で、マスク情報の優先状態のビット数が最小のものは、連想メモリ２１１−１の連想メモリ・ワード８４−１−１に格納している４進表記で（２．１．１．＊）であることは明らかである。したがって、アドレス信号生成部１１は正しいアドレス出力信号１２を出力していることが分かる。
もちろん中間データ判定部８５と、論理積手段９９−０〜９９−ｒと、記憶手段８９−０〜８９−ｒと、制御手段９１とを有さずに、図１に示す本発明の第１の実施の形態の連想メモリ・システム２００と同様に、連想メモリ２１１−０〜２１１−ｒが出力する中間データ８３−０〜８３−ｒを、図１に示す中間データ演算部９と同様に構成される中間データ演算部に入力した結果得られる最適化中間データを記憶手段８７−０〜８７−ｒに入力し、連想メモリ２１１−０〜２１１−ｒが出力する一致線３−０−０〜３−ｓ−ｒをアドレス信号生成部１１に直接入力するように構成しても、正しいアドレス出力信号１２を得られることは明らかである。このとき、中間データ演算部としては、図４に示した中間データ演算部２６、または図６に示した中間データ演算部２８と同様に構成できることは言うまでもない。また、図８に示した第３の実施の形態の連想メモリ・システム２０３のように、最適化中間データを結線論理により生成する構成にしても構わないことも明らかである。これらにより回路構成を簡略化することが可能である。
また、本例では、無効状態ビット数計数手段９４−ｋは、有効保持信号９０−ｋが無効状態の場合には、中間データ８３−ｋのビット数を出力したが、中間データ８０−ｋのビット数よりも大きい値を出力してもよいことはいうまでもない。
ここで、図１７に示す連想メモリ・システム２１２において、連想メモリ２１１−ｋに対応する無効状態ビット数計数手段９４−ｋを連想メモリ２１１−ｋに内蔵した場合には、図１１に示す連想メモリ・システム２０６の説明と同様に、大幅に長い配線の本数を削減することが可能となるとともに、各連想メモリ２１１に必要な端子の数を大幅に削減することができる。さらに、信号遅延時間、配線容量による消費電力などを削減できる。配線領域の減少によりさらに面積を削減可能である。また、各連想メモリの端子数が大幅に削減されるため面積をさらに削減することが可能である。
以上説明した第３乃至第７の実施の形態の本発明の連想メモリ・システムにおいて、アドレス信号生成部１１の代わりに図３に示すアドレス信号生成部２５を用いた場合には、連想メモリ２１１−ｋに対応するエンコーダ２２−ｋ、一致検出手段１６−ｋも連想メモリ２１１−ｋに内蔵することにより、前述のように、さらに面積削減、端子数削減が可能なことは言うまでもない。
〔第８の実施例〕
次に図面を参照して、本発明の第１の実施の形態の連想メモリ・システム２００を転送先アドレス計算に用いた本発明の第１の実施の形態のネットワーク機器の構成例を説明する。図２１は、本発明の第１の実施の形態のネットワーク機器の構成例を示すブロック図である。図２１のネットワーク機器１０１は、図２５に示した従来のネットワーク機器４００と同様に、入力通信データ４０７を入力とし、出力通信データ４０８を出力する。入力通信データ４０７は、送出元ネットワーク・アドレス４０９と、転送先ネットワーク・アドレス４１０と、宛先ネットワーク・アドレス４１１を有している。出力通信データ４０９は、送出元ネットワーク・アドレス４０９と、第２の転送先ネットワーク・アドレス４１２と、宛先ネットワーク・アドレス４１１を有している。入力通信データ４０７の転送先ネットワーク・アドレス４１０は、図２１におけるネットワーク機器１０１のネットワーク・アドレスとなっている。
図２１に示す本発明のネットワーク機器１０１は、宛先ネットワーク・アドレス抽出部４０５と、本発明の第１の実施の形態の連想メモリ・システム２００と、転送先ネットワーク・アドレス格納メモリ１０２と、転送先ネットワーク・アドレス変更部４０６と、により構成される。
図２５で説明した従来のネットワーク機器４００と比較すると、図２５において宛先ネットワーク・アドレス抽出部４０５から入力される検索データ３０７に対して最適な構造化データを検索する従来のｎビットｍ語の連想メモリ３００と、連想メモリ３００から入力された一致線３０１−０〜３０１−３をアドレス出力信号３０９に符号化するエンコーダ３０８とを、図２１の本発明のネットワーク機器１０１では、ｐ個のｎビットｍ語の連想メモリ１−０〜１−ｒを有する本発明の第１の実施の形態のｎビット（ｍ×ｐ）語の連想メモリ・システム２００を用いて構成している点と、また、それに伴い、ｍ語の転送先ネットワーク・アドレス格納メモリ４０２が、（ｍ×ｐ）語の転送先ネットワーク・アドレス格納メモリに変更されている点と、が異なり他の要素は同様に構成される。
図２１の連想メモリ・システム２００は、図１と同様に、ｐ個のｍ語ｎビットの連想メモリ１−０〜１−ｒと、中間データ演算部９と、アドレス信号生成部１１とから構成され、ｎビットの検索データ２を入力とし、アドレス出力信号１２を出力とする。したがって、第１の実施の形態の連想メモリ・システム２００の動作説明から明らかなように、図２５の従来のｎビットｍ語の連想メモリ３００とエンコーダ３０８の組み合わせと比較すると、格納可能な構造化データの数がｐ倍に増加した他は、全く同様に動作することが分かる。
これにより、複数の連想メモリ１−０〜１−ｒを有する本発明の連想メモリ・システム２００から構成されるネットワーク機器１０１は、格納している構造化データを最新の状況に更新する場合においても、ソート処理が不要であるため転送処理が中断せず、ネットワーク全体の転送速度を大幅に向上させることができる。
また、ソート処理を実行するための高価な高速ＣＰＵシステムが不要であるため、ネットワーク機器全体としての価格を削減できる。また、プライオリティ・エンコーダが不要となるため、符号化処理時間が短縮されるため、通信データの転送速度をさらに向上できる効果と、ネットワーク機器の価格をさらに削減することが可能である。
また、ソート処理が必要なために、本発明のネットワーク機器１０１では、容易に連想メモリ１を追加または削除することが可能であり、ネットワーク規模に応じて、柔軟に構造化データの格納容量を変更することができる。
〔第９の実施例〕
次に図面を参照して、本発明の第７の実施の形態の連想メモリ・システム２１２を転送可否演算に用いた本発明の第２の実施の形態のネットワーク機器の構成例を説明する。図２２は、本発明の第２の実施の形態のネットワーク機器の構成例を示すブロック図である。
図２２のネットワーク機器１０３は、入力通信データ４０７を入力とし、出力通信データ４０８を出力する。入力通信データ４０７は、送出元ネットワーク・アドレス４０９と、転送先ネットワーク・アドレス４１０と、宛先ネットワーク・アドレス４１１を有している。出力通信データ４０８は、送出元ネットワーク・アドレス４０９と、第２の転送先ネットワーク・アドレス４１２と、宛先ネットワーク・アドレス４１１を有している。入力通信データ４０７の転送先ネットワーク・アドレス４１０は、図２２におけるネットワーク機器１０３のネットワーク・アドレスとなっている。
図２２に示す本発明のネットワーク機器１０３は、送出元ネットワーク・アドレスおよび宛先ネットワーク・アドレス抽出部１０４と、本発明の第７の実施の形態の連想メモリ・システム２１２と、転送可否情報格納メモリ１０５と、転送先ネットワーク・アドレス演算部１０８と、転送先ネットワーク・アドレス変更部４０６と、データ転送部１０７とにより構成される。
送出元ネットワーク・アドレスおよび宛先ネットワーク・アドレス抽出部１０４は、入力通信データ４０７の送出元ネットワーク・アドレス４０９と宛先ネットワーク・アドレス４１０を抽出し、宛先ネットワーク・アドレス４１０を検索データ２として転送先ネットワーク・アドレス演算部１０８に出力する。また、抽出した送出元ネットワーク・アドレス４０９と宛先ネットワーク・アドレス４１０の双方を部分検索領域とする検索データ７０を連想メモリ・システム２１２に出力する。
転送先ネットワーク・アドレス演算部１０８は、内部に格納している構造化データで表現されたネットワーク・アドレスの中で、検索データ２として入力された宛先ネットワーク・アドレス４１０と一致するものを検索し、一致する構造化データの中でマスク情報の有効状態のビット数が最小のものを選択し、該構造化データで表現されたネットワーク・アドレスに対応する第２の転送先ネットワーク・アドレスを、メモリ・データ信号４０４として出力する機能を有している。転送先ネットワーク・アドレス変更部４０６は、入力通信データ４０７の転送先ネットワーク・アドレス４１０をメモリ・データ信号４０４に応じて第２の転送先ネットワーク・アドレス４１２に変更し、変更済み通信データ１０９としてデータ転送部１０７に出力する。
したがって、入力通信データの転送先ネットワーク・アドレス４１０に対する送出元ネットワーク・アドレスおよび宛先ネットワーク・アドレス抽出部１０４と転送先ネットワーク・アドレス演算部１０８と転送先ネットワーク・アドレス変更部４０６の動作は、図２３の従来のネットワーク機器４００と全く同様である。したがって、転送先ネットワーク・アドレス演算部１０８は、図２１に示した本発明のネットワーク機器１０１における連想メモリ・システム１０１と転送先ネットワーク・アドレス格納メモリ４０２により容易に構成することができる。
図２２の連想メモリ・システム２１２の構成は、図１７と同様である。連想メモリ・システム２１２は、ｐ個の連想メモリ２１１−０〜２１１−ｒを持ち、ｋ番目の連想メモリ２１１−ｋの各ワードには送出元ネットワーク・アドレスと転送先ネットワーク・アドレスを連結した構造化データを格納している。本例では検索データ７０を構成する部分検索領域の中で送出元ネットワーク・アドレス４０９に対応する領域が第１の優先順位を有するものとして説明する。もちろん、宛先ネットワーク・アドレス４１１に対応する部分検索領域が第１の優先順位を有していてもよいことはいうまでない。
前述の第７の連想メモリ・システム２１２の動作の説明と同様に、連想メモリ・システム２１２は、送出元ネットワーク・アドレスおよび宛先ネットワーク・アドレス抽出部１０４から入力される送出元ネットワーク・アドレス４０９と宛先ネットワーク・アドレス４１０を部分検索領域とする検索データ７０に対して、ｐ個の連想メモリ２１１−０〜２１１−ｒに格納している構造化データの中でマスク情報を考慮して比較する１次検索を実行したときに記憶データがすべて一致するワードが複数個あった場合、一致したワードの記憶データの中で第１の優先順位を持つ送出元ネットワーク・アドレス４０９に対応するビット領域に含まれる無効状態のビット数が最小である記憶データを選択し、さらに選択された記憶データの中で第２の優先順位を持つ宛先ネットワーク・アドレス４１１に対応するビット領域に含まれる無効状態のビット数が最小のものを選択し、該記憶データに対応する転送可否情報格納メモリ１０５のワードをアクセスするためのアドレス出力信号１２を出力する。
転送可否情報格納メモリには、連想メモリ・システム２１２が各ワードに格納している送出元ネットワーク・アドレスと転送先ネットワーク・アドレスを連結した構造化データに対応するワードに、該構造化データと一致する入力通信データに対する転送の許可、拒絶を示す制御データを格納しており、アドレス出力信号１２により、対応するワードが格納している制御データを、転送制御信号１０６としてデータ転送部に出力する。
データ転送部１０７は、転送制御信号１０７が転送許可を示している場合には、変更済み通信データ１０９を第２の転送先ネットワーク・アドレス４１２に対応するネットワーク機器に対して転送し、転送制御信号１０７が転送拒絶を示している場合には、変更済み通信データ１０９の転送を行わない。これにより、いわゆるパケット・フィルタリング処理が実現できる。
本例では、第７の実施の形態の連想メモリ・システム２１２により構成したが、第６の実施の形態の連想メモリ・システム２１０によっても構成できることはいうまでもない。
上述のように、複数の連想メモリ２１１−０〜２１１−ｒを有する本発明の連想メモリ・システム２１２から構成されるネットワーク機器１０３は、格納している構造化データを最新の状況に更新する場合においても、ソート処理が不要であるため転送処理が中断せず、ネットワーク全体の転送速度を大幅に向上させることができる。
また、ソート処理を実行するための高価な高速ＣＰＵシステムが不要であるため、ネットワーク機器全体としての価格を削減できる。
また、プライオリティ・エンコーダが不要となるため、符号化処理時間が短縮されるため、通信データの転送速度をさらに向上できる効果と、ネットワーク機器の価格をさらに削減することが可能である。また、ソート処理が必要なために、本発明のネットワーク機器１０３では、容易に連想メモリ２１１を追加または削除することが可能であり、ネットワーク規模に応じて、柔軟に構造化データの格納容量を変更することができる。
産業上の利用可能性
上述のように、本発明の連想メモリ・システムは、記憶容量を増大させるために複数個接続した連想メモリに対してソート処理を伴わずに構造化データの書き込み、更新および削除を実行した場合においても、検索時に複数の記憶データが検索データと一致したときに、その中で最適な構造化データを識別する信号を出力することができるという効果を有する。また、第４の実施の形態のように中間データの判定を２次検索と並列に実行するように構成した本発明の連想メモリ・システムの検索時間は、連想メモリ単体の検索時間と同一であり、高速に検索できるという効果も有する。
また、本発明の連想メモリ・システムでは、中間データ、一致線の双方または一方を符号化して出力する機能を各連想メモリの内部に組み込むことにより、大きな配線寄生容量を持つ長い配線の本数を、連想メモリ全体として大幅に削減できるため、信号遅延時間の短縮による検索時間の短縮、配線容量減少による消費電力の削減という効果を有する。また、配線領域の減少および各連想メモリの端子数が大幅に削減されるため、連想メモリ・システム全体としての面積を大幅に削減でき、システム全体としての価格を安価にできるという効果を有する。また、プライオリティ・エンコーダが不要となるため、システム全体としての検索速度をさらに向上させることができるとともに、さらに面積を削減できるという効果を有する。
また、記憶容量を増大するために複数の連想メモリを接続するために、本発明の連想メモリ・システムを組み込んだネットワーク機器では、転送動作を中断せずに構造化データ表現のネットワーク・アドレスの削除、追加、変更を行うことができるという利点を有する。上述のように、本発明の連想メモリ・システムを用いれば、構造化データ表現のネットワーク・アドレスの削除、追加、変更は、ソート処理を伴わずに通常のメモリ・アクセスに要する時間で実行できるからである。これにより、従来のネットワーク機器で必要であったソート処理実行中のためのネットワークの通信不能時間が不要になるともに、運用管理が容易になるという利点も有する。さらに、構造化データ表現のネットワーク・アドレスの削除、追加、変更が迅速に反映されるため、ネットワーク全体の転送速度、安全性が向上するという効果を有する。さらに、連想メモリ・システムの構造化データを管理するソフトウエア処理が簡単になるという効果もある。
また、本発明の連想メモリ・システムを組み込んだネットワーク機器では、転送先アドレス計算や転送可否判定を、高速に実行可能なネットワーク機器のトータルコストを削減できるという効果を有する。上述のように転送可否判定を高速に演算可能な本発明の連想メモリ・システムを搭載することにより、ソート処理を実行するための高価な高速ＣＰＵシステムを搭載する必要がなくなるからと、連想メモリ・システム全体としての面積を大幅に削減できるからである。
また、本発明のネットワーク機器を用いることにより、ネットワーク規模の増減に応じて記憶容量を柔軟に増減でき、かつ、高速にデータを転送でき、さらに運用管理の容易なネットワーク・システムを構築することができるという利点を有する。
【図面の簡単な説明】
図１は、本発明の第１の実施の形態の連想メモリ・システムの構成例を示すブロック図である。
図２は、本発明の第１の実施の形態の連想メモリ・システムの動作例を示す図である。
図３は、本発明の第２の実施の形態の連想メモリ・システムの構成例と動作例を示すブロック図である。
図４は、本発明の連想メモリ・システムの中間データ演算部の第２の構成例を示すブロック図である。
図５は、本発明の連想メモリ・システムの第２の構成例の中間データ演算部の動作例を示す図である。
図６は、本発明の連想メモリ・システムの中間データ演算部の第３の構成例を示すブロック図である。
図７は、本発明の連想メモリ・システムの第３の構成例の中間データ演算部の動作例を示す図である。
図８は、本発明の第３の実施の形態の連想メモリ・システムの構成例を示すブロック図である。
図９は、本発明の第４の実施の形態の連想メモリ・システムの構成例を示すブロック図である。
図１０は、本発明の第４の実施の形態の連想メモリ・システムの動作例を示す図である。
図１１は、本発明の連想メモリ・システムの中間データ判定部の第２の構成例と動作例を示すブロック図である。
図１２は、本発明の第５の実施の形態の連想メモリ・システムの構成例を示すブロック図である。
図１３は、本発明の第６の実施の形態の連想メモリ・システムの構成例を示すブロック図である。
図１４は、本発明の第６の実施の形態の連想メモリ・システムの動作例を示す図である。
図１５は、本発明の連想メモリ・システムのｈ番目の２次中間データ判定部の第２の構成例を示すブロック図である。
図１６は、本発明の連想メモリ・システムのｈ番目の２次中間データ判定部の第３の構成例を示すブロック図である。
図１７は、本発明の第７の実施の形態の連想メモリ・システムの構成例を示すブロック図である。
図１８は、本発明の第７の実施の形態の連想メモリ・システムの１クロック目の動作例を示す図である。
図１９は、本発明の第７の実施の形態の連想メモリ・システムの２クロック目の動作例を示す図である。
図２０は、本発明の第７の実施の形態の連想メモリ・システムの３クロック目の動作例を示す図である。
図２１は、本発明の連想メモリを転送先アドレス計算に用いた本発明の第１の実施の形態のネットワーク機器の構成例を示すブロック図である。
図２２は、本発明の連想メモリを転送可否演算に用いた本発明の第２の実施の形態のネットワーク機器の構成例を示すブロック図である。
図２３は、従来の連想メモリの一構成例を示すブロック図である。
図２４は、ネットワークの構成例を示す接続図である。
図２５は、従来の連想メモリを転送先アドレス計算に用いた従来のネットワーク機器の構成例を示すブロック図である。
図２６は、従来の連想メモリを複数接続するときの第１の構成例と動作例を示すブロック図である。
図２７は、従来の連想メモリを複数接続するときの第２の構成例と動作例を示すブロック図である。
【図１】
0003845845.tif 000002
【図２】
0003845845.tif 000003
【図３】
0003845845.tif 000004
【図４】
0003845845.tif 000005
【図５】
0003845845.tif 000006
【図６】
0003845845.tif 000007
【図７】
0003845845.tif 000008
【図８】
0003845845.tif 000009
【図９】
0003845845.tif 000010
【図１０】
0003845845.tif 000011
【図１１】
0003845845.tif 000012
【図１２】
0003845845.tif 000013
【図１３】
0003845845.tif 000014
【図１４】
0003845845.tif 000015
【図１５】
0003845845.tif 000016
【図１６】
0003845845.tif 000017
【図１７】
0003845845.tif 000018
【図１８】
0003845845.tif 000019
【図１９】
0003845845.tif 000020
【図２０】
0003845845.tif 000021
【図２１】
0003845845.tif 000022
【図２２】
0003845845.tif 000023
【図２３】
0003845845.tif 000024
【図２４】
0003845845.tif 000025
【図２５】
0003845845.tif 000026
【図２６】
0003845845.tif 000027
【図２７】
0003845845.tif 000028