(57)【要約】【課題】カスケード接続に関連する入力端子数（ピン数）や配線の増加を最小とし得る連想メモリ装置を提供する。【解決手段】Ｎ個（但し、Ｎ≧２）の連想メモリチップがカスケード接続された連想メモリ装置において、各連想メモリチップ１０ｎは、連想メモリ２０、（Ｎ−１）個の入力端子ＩＮｎ＿ｍ、少なくとも１つの第１信号保持手段３０、少なくとも１つの第２信号保持手段４０、出力端子ＯＵＴｎ、及び、出力制御回路５０を備えており、第ｎ番目の連想メモリチップ１０ｎにおいて、第ｍ番目の入力端子ＩＮｎ＿ｍは、第ｍ番目の連想メモリチップ１０ｍの出力端子ＯＵＴｍに接続されている。【選択図】  図２
2004295938.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ個（但し、Ｎは２以上の整数）の連想メモリチップがカスケード接続された連想メモリ装置であって、
各連想メモリチップは、
（Ａ）連想メモリ、
（Ｂ）（Ｎ−１）個の入力端子、
（Ｃ）少なくとも１つの第１信号保持手段、
（Ｄ）少なくとも１つの第２信号保持手段、
（Ｅ）出力端子、及び、
（Ｆ）出力制御回路、
を備え、
第ｎ番目（但し、ｎ＝１，２，・・・Ｎ）の連想メモリチップにおいて、第ｍ番目（但し、ｍ＝１，２，・・・であり、且つ、ｍ＜ｎ）の入力端子は、第ｍ番目の連想メモリチップの出力端子に接続されており、
複数のデータ検索コマンドのそれぞれが第ｎ番目の連想メモリチップにおいて実行されることによって得られるプライオリティ信号が、第ｎ番目の連想メモリチップを構成する第２信号保持手段において保持され、
第ｍ番目の連想メモリチップを構成する第２信号保持手段において保持されたプライオリティ信号は、第ｍ番目の連想メモリチップを構成する出力端子及び第ｎ番目の連想メモリチップを構成する第ｍ番目の入力端子を介して、第ｎ番目の連想メモリチップを構成する第１信号保持手段に送られ、第ｎ番目の連想メモリチップを構成する第１信号保持手段においてカスケード・プライオリティ信号として保持され、
第ｎ番目の連想メモリチップを構成する出力制御回路において、第１信号保持手段に保持されたカスケード・プライオリティ信号と、第２信号保持手段に保持されたプライオリティ信号とが比較され、その比較結果に基づき、第ｎ番目の連想メモリチップを構成する出力制御回路から該データ検索コマンドの実行結果が出力されることを特徴とする連想メモリ装置。
【請求項２】
第１信号保持手段及び第２信号保持手段の数は、前記データ検索コマンドの種類の数と等しいことを特徴とする請求項１に記載の連想メモリ装置。
【請求項３】
前記データ検索コマンドは、連想メモリに格納されたワードに相当するデータを検索するコマンド、及び、連想メモリにおける空きアドレスの有無を検索するコマンドの２種類のコマンドであることを特徴とする請求項２に記載の連想メモリ装置。
【請求項４】
各連想メモリチップは、連想メモリチップの識別番号に対応するデータを格納する識別番号格納手段を更に有し、
連想メモリ装置の初期化時に、入力端子に入力される初期状態信号に基づき、連想メモリチップの識別番号に対応するデータが識別番号格納手段に格納されることを特徴とする請求項１に記載の連想メモリ装置。
【請求項５】
Ｎ個（但し、Ｎは２以上の整数）の連想メモリチップがカスケード接続され、
各連想メモリチップは、
（Ａ）連想メモリ、
（Ｂ）（Ｎ−１）個の入力端子、
（Ｃ）少なくとも１つの第１信号保持手段、
（Ｄ）少なくとも１つの第２信号保持手段、
（Ｅ）出力端子、及び、
（Ｆ）出力制御回路、
を備え、
第ｎ番目（但し、ｎ＝１，２，・・・Ｎ）の連想メモリチップにおいて、第ｍ番目（但し、ｍ＝１，２，・・・であり、且つ、ｍ＜ｎ）の入力端子は第ｍ番目の連想メモリチップの出力端子に接続されている連想メモリ装置を用い、連想メモリに格納されたデータを検索する方法であって、
（ａ）複数のデータ検索コマンドのそれぞれを第ｎ番目の連想メモリチップにおいて実行し、得られたプライオリティ信号を第ｎ番目の連想メモリチップを構成する第２信号保持手段において保持し、
（ｂ）第ｍ番目の連想メモリチップを構成する第２信号保持手段において保持されたプライオリティ信号を、第ｍ番目の連想メモリチップを構成する出力端子及び第ｎ番目の連想メモリチップを構成する第ｍ番目の入力端子を介して、第ｎ番目の連想メモリチップを構成する第１信号保持手段に送出し、第ｎ番目の連想メモリチップを構成する第１信号保持手段においてカスケード・プライオリティ信号として保持し、
（ｃ）第ｎ番目の連想メモリチップを構成する出力制御回路において、第１信号保持手段に保持されたカスケード・プライオリティ信号と、第２信号保持手段に保持されたプライオリティ信号とを比較し、その比較結果に基づき、第ｎ番目の連想メモリチップを構成する出力制御回路から該データ検索コマンドの実行結果を出力することを特徴とする連想メモリ装置に格納されたデータの検索方法。
【請求項６】
第１信号保持手段及び第２信号保持手段の数は、前記データ検索コマンドの種類の数と等しいことを特徴とする請求項５に記載の連想メモリ装置に格納されたデータの検索方法。
【請求項７】
前記データ検索コマンドは、連想メモリに格納されたワードに相当するデータを検索するコマンド、及び、連想メモリにおける空きアドレスの有無を検索するコマンドの２種類のコマンドであることを特徴とする請求項６に記載の連想メモリ装置に格納されたデータの検索方法。
【請求項８】
各連想メモリチップは、連想メモリチップの識別番号に対応するデータを格納する識別番号格納手段を更に有し、
連想メモリ装置の初期化時に、入力端子に入力される初期状態信号に基づき、連想メモリチップの識別番号に対応するデータを識別番号格納手段に格納することを特徴とする請求項５に記載の連想メモリ装置に格納されたデータの検索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、連想メモリチップがカスケード接続された連想メモリ装置、及び、係る連想メモリ装置に格納されたデータの検索方法に関する。
【０００２】
【従来の技術】
インタネットの発展に伴って、パケットの高速経路探索やセキュリティ確保のために、予め決められたルールデータとパケットデータとの高速な検索比較が要求されている。このような要求から、高速データ検索が可能な連想メモリ［Ａｓｓｏｃｉａｔｉｖｅ  Ｍｅｍｏｒｙ、あるいは、内容アドレス式メモリ，ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  ｍｅｍｏｒｙ）とも呼ばれる］を備えた連想メモリチップが必須のデバイスとなりつつある。連想メモリは機能メモリとも呼ばれ、通常のメモリの１ビット毎に一致検索論理を有しているが故に、高集積化が困難である。ところで、上述の高速経路探索のためのテーブルサイズは日増しに大きくなっており、そのために、連想メモリチップを複数個カスケード接続し、連想メモリチップに格納し得るワード数を増加させることが求められている。そのために、例えば、特開平８−１３８３８４号に開示された連想メモリのように、連想メモリチップそれ自体に複数チップの接続機能を持たせるようになっている。
【０００３】
一般に、連想メモリは、Ｑビットのメモリと１ビットのフラグがＰ個、並置された構造を有する。ここで、各メモリにおいては、Ｑビットによってワードメモリが構成され、１ビットのフラグは空きアドレスであるか否かを表す（空きアドレス・フラグ）。検索すべきデータは、Ｑビットによって構成されたワードメモリに格納されたワードデータ、あるいは又、空きアドレス・フラグである。ここで、空きアドレスとは、連想メモリのなかに検索対象データを新たに格納するために空いているワードメモリのアドレスを指す。
【０００４】
連想メモリに格納されるワードデータとして、上記のような経路情報やセキュリティ情報などを挙げることができ、連想メモリに格納されたワードデータと外部からのワードデータとの一致がとられるようになっている。このとき、外部からのワードデータと連想メモリに格納されたワードデータの複数とが一致する場合もあり、このような場合には、一般にアドレスの小さいものを優先して出力するように設計されている。従って、各連想メモリチップ間でプライオリティ情報を交換して、最もプライオリティの高いアドレスを出力する機能を有している。
【０００５】
複数の連想メモリチップをカスケード接続して成る連想メモリ装置の概念図を図７に示す。ここでは、８個の連想メモリチップ１００１〜１００８がカスケード接続されているとする。この連想メモリチップ１００１〜１００８にあっては、連想メモリチップ間で交換される情報として２つの信号を挙げることができる。即ち、ワード検索コマンド（各連想メモリチップを構成する連想メモリに格納されたワードに相当するデータを検索するコマンド）の実行によって得られる信号であって、ワードデータがヒット（一致）したかどうかを示すヒット（一致）信号ＳＨ、並びに、空きアドレス出力要求コマンド（連想メモリにおける空きアドレスの有無を検索するコマンド）の実行によって得られる信号であるエンプティ信号ＳＥである。
【０００６】
ここで、ヒット信号ＳＨが信号「Ｈ」のとき、検索ワードデータと一致するデータを格納したワードメモリが連想メモリに存在することを示し、信号「Ｌ」のとき、検索ワードデータと一致するデータを格納したワードメモリが連想メモリに存在しないことを示す。また、エンプティ信号ＳＥが信号「Ｈ」のとき、新たなデータを格納し得るメモリが連想メモリに存在することを示し、信号「Ｌ」のとき、新たなデータを格納し得るメモリが連想メモリに存在しないことを示す。
【０００７】
また、一般に、各連想メモリチップ１００１〜１００８はデバイス番号（ＩＤ）を有し、デバイス番号（ＩＤ）の小さい連想メモリチップが優先チップとして取り扱われ、デバイス番号（ＩＤ）の一番大きいものが、その連想メモリ装置中で最もプライオリティが低いものとして取り扱われる。
【０００８】
図７に示した連想メモリ装置においては、８個の連想メモリチップ１００１〜１００８がカスケード接続されている。そして、連想メモリチップ１００ｎ（ここで、ｎ＝１，２，・・・８のいずれか）は、他の連想メモリチップ１００ｎ’（ｎ’≠ｎ）からの２種類の優先（プライオリティ）信号（ヒット信号ＳＨ及びエンプティ信号ＳＥ）を得るために、（８−１）×２＝１４個の入力端子ＩＮｎ＿Ｈｍ，ＩＮｎ＿Ｅｍ（ここで、ｍ＝１，２，・・・７）を有し、また、連想メモリチップ１００ｎからの２種類の優先（プライオリティ）信号（ヒット信号ＳＨ及びエンプティ信号ＳＥ）を出力するための２個の出力端子ＯＵＴＨ，ＯＵＴＥを有している。出力端子ＯＵＴＨと入力端子ＩＮｎ＿Ｈｍとは配線ＬＨｎによって接続され、出力端子ＯＵＴＥと入力端子ＩＮｎ＿Ｅｍとは配線ＬＥｎによって接続されている。
【０００９】
このような連想メモリ装置において、例えば、第ｎ番目の連想メモリチップ１００ｎは、第ｎ番目の連想メモリチップ１００ｎよりもプライオリティが高い連想メモリチップ［第１番目の連想メモリチップ１００１，第２番目の連想メモリチップ１００２，・・・，第（ｎ−１）番目の連想メモリチップ１００（ｎ−１）］からのプライオリティ信号（ヒット信号ＳＨ又はエンプティ信号ＳＥ）を加味して、自らの制御を行う。具体的には、例えば、第ｎ番目の連想メモリチップ１００ｎが、第ｎ番目の連想メモリチップ１００ｎよりもプライオリティが高いいずれかの連想メモリチップからプライオリティ情報（信号「Ｈ」のヒット信号ＳＨ又は信号「Ｈ」のエンプティ信号ＳＥ）を受け取った場合、たとえ、第ｎ番目の連想メモリチップ１００ｎにおいて、検索ワードデータと一致するデータを格納したワードメモリが存在したとしても、あるいは又、新たなデータを格納し得るメモリが存在したとしても、第ｎ番目の連想メモリチップ１００ｎからは何ら出力しない。第ｎ番目の連想メモリチップ１００ｎからは、第（ｎ＋１）番目以降の連想メモリチップ１００（ｎ＋１），・・・に、プライオリティ信号（ヒット信号ＳＨ又はエンプティ信号ＳＥ）を送出するだけである。一方、例えば、第ｎ番目の連想メモリチップ１００ｎが、第ｎ番目の連想メモリチップ１００ｎよりもプライオリティが高いいずれかの連想メモリチップからプライオリティ情報（信号「Ｈ」のヒット信号ＳＨ又は信号「Ｈ」のエンプティ信号ＳＥ）を受け取らず（言い換えれば、信号「Ｌ」のヒット信号ＳＨ又は信号「Ｌ」のエンプティ信号ＳＥしか受け取らず）、且つ、第ｎ番目の連想メモリチップ１００ｎにおいて、検索ワードデータと一致するデータを格納したワードメモリが存在し、あるいは又、新たなデータを格納し得るメモリが存在した場合には、第ｎ番目の連想メモリチップ１００ｎからデータ検索コマンドの実行結果が出力される。
【００１０】
尚、このような動作を保証するために、入力端子ＩＮｎ＿Ｈｍ，ＩＮｎ＿Ｅｍにあっては、第ｍ’番目の入力端子ＩＮｎ＿Ｈｍ’，ＩＮｎ＿Ｅｍ’［但し、ｍ’＝ｎ］から第Ｎ番目の入力端子ＩＮｎ＿Ｈｍ’，ＩＮｎ＿Ｅｍ’［但し、ｍ’＝Ｎ］までは、「Ｌ」状態に固定されており、第ｎ番目の連想メモリチップ１００ｎよりもプライオリティが低い第ｍ’番目の連想メモリチップ１００ｍ’（但し、ｎ≦ｍ’≦Ｎ）からのプライオリティ情報を常にディスエーブル状態にしている。
【００１１】
【特許文献１】特開平８−１３８３８４号
【００１２】
【発明が解決しようとする課題】
しかしながら、このような構成を採用した場合、カスケード接続する連想メモリチップの数やプライオリティ情報（信号）の種類が増えると、これに伴い、カスケード接続に関連する入力端子数（ピン数）や配線が増加するといった問題がある。
【００１３】
従って、本発明の目的は、カスケード接続される連想メモリチップの数やプライオリティ情報（信号）の種類が増加しても、カスケード接続に関連する入力端子数（ピン数）や配線の増加を最小とし得る連想メモリ装置、及び、係る連想メモリ装置に格納されたデータの検索方法を提供することにある。
【００１４】
【課題を解決するための手段】
上記の目的を達成するための本発明の連想メモリ装置は、Ｎ個（但し、Ｎは２以上の整数）の連想メモリチップがカスケード接続された連想メモリ装置であって、
各連想メモリチップは、
（Ａ）連想メモリ、
（Ｂ）（Ｎ−１）個の入力端子、
（Ｃ）少なくとも１つの第１信号保持手段、
（Ｄ）少なくとも１つの第２信号保持手段、
（Ｅ）出力端子、及び、
（Ｆ）出力制御回路、
を備え、
第ｎ番目（但し、ｎ＝１，２，・・・Ｎ）の連想メモリチップにおいて、第ｍ番目（但し、ｍ＝１，２，・・・であり、且つ、ｍ＜ｎ）の入力端子は、第ｍ番目の連想メモリチップの出力端子に接続されており、
複数のデータ検索コマンドのそれぞれが第ｎ番目の連想メモリチップにおいて実行されることによって得られるプライオリティ信号が、第ｎ番目の連想メモリチップを構成する第２信号保持手段において保持され、
第ｍ番目の連想メモリチップを構成する第２信号保持手段において保持されたプライオリティ信号は、第ｍ番目の連想メモリチップを構成する出力端子及び第ｎ番目の連想メモリチップを構成する第ｍ番目の入力端子を介して、第ｎ番目の連想メモリチップを構成する第１信号保持手段に送られ、第ｎ番目の連想メモリチップを構成する第１信号保持手段においてカスケード・プライオリティ信号として保持され、
第ｎ番目の連想メモリチップを構成する出力制御回路において、第１信号保持手段に保持されたカスケード・プライオリティ信号と、第２信号保持手段に保持されたプライオリティ信号とが比較され、その比較結果に基づき、第ｎ番目の連想メモリチップを構成する出力制御回路から該データ検索コマンドの実行結果が出力されることを特徴とする。
【００１５】
上記の目的を達成するための本発明の連想メモリに格納されたデータを検索する方法は、
Ｎ個（但し、Ｎは２以上の整数）の連想メモリチップがカスケード接続され、
各連想メモリチップは、
（Ａ）連想メモリ、
（Ｂ）（Ｎ−１）個の入力端子、
（Ｃ）少なくとも１つの第１信号保持手段、
（Ｄ）少なくとも１つの第２信号保持手段、
（Ｅ）出力端子、及び、
（Ｆ）出力制御回路、
を備え、
第ｎ番目（但し、ｎ＝１，２，・・・Ｎ）の連想メモリチップにおいて、第ｍ番目（但し、ｍ＝１，２，・・・であり、且つ、ｍ＜ｎ）の入力端子は第ｍ番目の連想メモリチップの出力端子に接続されている連想メモリ装置を用い、連想メモリに格納されたデータを検索する方法であって、
（ａ）複数のデータ検索コマンドのそれぞれを第ｎ番目の連想メモリチップにおいて実行し、得られたプライオリティ信号を第ｎ番目の連想メモリチップを構成する第２信号保持手段において保持し、
（ｂ）第ｍ番目の連想メモリチップを構成する第２信号保持手段において保持されたプライオリティ信号を、第ｍ番目の連想メモリチップを構成する出力端子及び第ｎ番目の連想メモリチップを構成する第ｍ番目の入力端子を介して、第ｎ番目の連想メモリチップを構成する第１信号保持手段に送出し、第ｎ番目の連想メモリチップを構成する第１信号保持手段においてカスケード・プライオリティ信号として保持し、
（ｃ）第ｎ番目の連想メモリチップを構成する出力制御回路において、第１信号保持手段に保持されたカスケード・プライオリティ信号と、第２信号保持手段に保持されたプライオリティ信号とを比較し、その比較結果に基づき、第ｎ番目の連想メモリチップを構成する出力制御回路から該データ検索コマンドの実行結果を出力することを特徴とする。
【００１６】
本発明の連想メモリ装置、若しくは、連想メモリ装置に格納されたデータの検索方法（以下、これらを総称して、単に、本発明と呼ぶ場合がある）にあっては、連想メモリは周知の回路構成とすることができる。一般に、連想メモリは、Ｑビットのメモリと１ビットのフラグがＰ個、並置された構造を有する。ここで、各メモリにおいては、Ｑビットによってワードメモリが構成され、１ビットのフラグは空きアドレスであるか否かを表す（空きアドレス・フラグ）。検索すべきデータは、Ｑビットによって構成されたワードメモリに格納されたデータ、あるいは又、空きアドレス・フラグである。Ｑの値として、例えば、８、１６、３２、６４、７２等を例示することができる。また、Ｐの値として、２１０、２１１、２１２、２１３、２１４、・・・を例示することができる。
【００１７】
本発明において、第１信号保持手段及び第２信号保持手段の数は、少なくとも１つであればよいが、前記データ検索コマンドの種類の数と等しい構成とすることが好ましい。
【００１８】
そして、この場合、前記データ検索コマンドを、連想メモリに格納されたワードに相当するデータを検索するコマンド（ワード検索コマンドと呼ぶ場合がある）、及び、連想メモリにおける空きアドレスの有無を検索するコマンド（空きアドレス出力要求コマンドと呼ぶ場合がある）の２種類のコマンドとすることができる。そして、この場合、プライオリティ信号は、ワード検索コマンド（各連想メモリチップを構成する連想メモリに格納されたワードに相当するデータを検索するコマンド）の実行によって得られる信号であって、ヒット（一致）したかどうかを示すヒット（一致）信号ＳＨ、並びに、空きアドレス出力要求コマンド（連想メモリにおける空きアドレスの有無を検索するコマンド）の実行によって得られる信号であるエンプティ信号ＳＥの２種類の信号である。
【００１９】
ここで、ヒット信号ＳＨが信号「Ｈ」のとき、検索ワードデータと一致するデータを格納したワードメモリが連想メモリに存在することを示し、信号「Ｌ」のとき、検索ワードデータと一致するデータを格納したワードメモリが存在しないことを示す。また、エンプティ信号ＳＥが信号「Ｈ」のとき、新たなデータを格納し得るメモリが連想メモリに存在することを示し、信号「Ｌ」のとき、新たなデータを格納し得るメモリが連想メモリに存在しないことを示す。
【００２０】
第１信号保持手段は、１ビット・レジスタから構成することもできるし、（Ｎ−１）ビット・レジスタから構成することもできる。第２信号保持手段は、１ビット・レジスタから構成することが好ましい。
【００２１】
入力端子の数は、（Ｎ−１）個であればよく、場合によっては、（Ｎ−１）個を越える数であってもよい。後者の場合、（Ｎ−１）個を越える入力端子は、所謂ダミー入力端子であり、実質的には何ら機能しない。また、出力端子は１つ有ればよく、複数であってもよい。
【００２２】
本発明にあっては、各連想メモリチップは、連想メモリチップの識別番号に対応するデータを格納する識別番号格納手段を有し；連想メモリ装置の初期化時に、入力端子に入力される初期状態信号に基づき、連想メモリチップの識別番号に対応するデータが識別番号格納手段に格納される構成とすることができる。ここで、識別番号格納手段を、Ｎビット・レジスタから構成し、０，１，２，・・・（Ｎ−１）に相当するデータを、それぞれの連想メモリチップの識別番号に対応するデータとして、それぞれの連想メモリチップの識別番号格納手段に格納する構成としてもよいし、識別番号格納手段を、１ビット・レジスタから構成し、カスケード接続された連想メモリチップの内、最後の連想メモリチップにおける識別番号格納手段に、識別番号に対応するデータとしてのデータ「１」を格納し、その他の連想メモリチップにおける識別番号格納手段に、識別番号に対応するデータとしてのデータとしてのデータ「０」を格納する構成とすることもできる。
【００２３】
本発明においては、Ｎ個（但し、Ｎは２以上の整数）の連想メモリチップがカスケード接続されている。これによって、連想メモリ装置に格納し得る検索ワード数の増加を図ることができる。しかも、複数のコマンド（例えば、ワード検索コマンド、及び、空きアドレス出力要求コマンドの２種類のコマンド）のそれぞれを実行するに際しても、それぞれの連想メモリチップには（Ｎ−１）個の入力端子を設けるだけでよいので、カスケード接続される連想メモリチップの数が増加しても、カスケード接続に関連する入力端子数（ピン数）や配線の増加を最小とすることができる。また、プライオリティ情報（信号）の数が増加しても、カスケード接続に関連する入力端子数（ピン数）や配線を増加させる必要はない。
【００２４】
【発明の実施の形態】
以下、図面を参照して、発明の実施の形態（以下、実施の形態と略称する）に基づき本発明を説明する。
【００２５】
（実施の形態１）
実施の形態１の連想メモリ装置の回路図を図１に示す。実施の形態１の連想メモリ装置にあっては、Ｎ（＝８）個の連想メモリチップ１０１〜１０８がカスケード接続されている。
【００２６】
そして、各連想メモリチップ（例えば、第ｎ番目の連想メモリチップ１０ｎ，但し、ｎ＝１，２，・・・Ｎ）は、回路図を図２に示すように、
（Ａ）連想メモリ２０、
（Ｂ）（Ｎ−１）個の入力端子ＩＮｎ＿ｍ［ここで、ｍ＝１，２，・・・，（Ｎ−１）］、
（Ｃ）少なくとも１つの第１信号保持手段３０、
（Ｄ）少なくとも１つの第２信号保持手段４０、
（Ｅ）出力端子ＯＵＴｎ、及び、
（Ｆ）出力制御回路５０、
を備えている。
【００２７】
ここで、図１に示すように、第ｎ番目（但し、ｎ＝１，２，・・・Ｎ）の連想メモリチップ１０ｎにおいて、第ｍ番目（但し、ｍ＝１，２，・・・であり、且つ、ｍ＜ｎ）の入力端子ＩＮｎ＿ｍは、配線Ｌｍを介して、第ｍ番目の連想メモリチップ１０ｍの出力端子ＯＵＴｍに接続されている。具体的には、例えば、第１番目の連想メモリチップ１０１における入力端子は、他の連想メモリチップの出力端子に接続されていない。また、例えば、第３番目の連想メモリチップ１０３において、第１番目の入力端子ＩＮ３＿１は、第１番目の配線Ｌ１を介して、第１番目の連想メモリチップ１０１の出力端子ＯＵＴ１に接続されており、第２番目の入力端子ＩＮ３＿２は、第２番目の配線Ｌ２を介して、第２番目の連想メモリチップ１０２の出力端子ＯＵＴ２に接続されている。更には、第８番目の連想メモリチップ１０８において、第ｍ番目（但し、ｍ＝１，２，・・・７）の入力端子ＩＮ８＿ｍは、第ｍ番目の配線Ｌｍを介して、第ｍ番目の連想メモリチップ１０ｍの出力端子ＯＵＴｍに接続されている。ここで、図７の従来例と比べて、カスケード接続のための入力端子ＩＮｎ＿ｍの数や配線Ｌｎの数が、１４本から７本と、１／２になっており、非常に単純化されている。
【００２８】
更には、第ｎ番目の連想メモリチップ１０ｎにおける入力端子ＩＮｎ＿ｍにあっては、第ｍ’番目の入力端子ＩＮｎ＿ｍ’（但し、ｍ’＝ｎ）から第Ｎ番目の入力端子ＩＮｎ＿ｍ’（但し、ｍ’＝Ｎ）までは、「Ｌ」状態（接地状態）に固定されており、第ｎ番目の連想メモリチップ１０ｎよりもプライオリティが低い第ｍ’番目の連想メモリチップ１０ｍ’（但し、ｎ≦ｍ’≦Ｎ）からのプライオリティ情報を常にディスエーブル状態にしている。つまり、連想メモリチップ１０ｎよりも低いプライオリティを有する連想メモリチップからのプライオリティ情報（入力信号）に関しては、常に、ロー状態に固定している。また、連想メモリチップ１０ｎよりも高いプライオリティを有する連想メモリチップからのプライオリティ情報（入力信号）がハイ「Ｈ」の場合、連想メモリチップ１０ｎよりもプライオリティの高い連想メモリチップが、データ検索コマンドの実行結果の出力を優先的に行う権利を有し、連想メモリチップ１０ｎからはデータ検索コマンドの実行結果の出力は行われない。
【００２９】
図２に示すように、第ｎ番目の連想メモリチップ１０ｎにおいて、全ての入力端子ＩＮｎ＿ｍと第２のスイッチ回路ＳＷｎ＿２の入力部との間には、第１のスイッチ回路ＳＷｎ＿１並びにＯＲ回路及びＡＮＤ回路が配置され、第２のスイッチ回路ＳＷｎ＿２の出力部は、１ビット構成のヒット・プライオリティ・レジスタ３１、及び、１ビット構成のエンプティ・プライオリティ・レジスタ３２に接続されている。ここで、ヒット・プライオリティ・レジスタ３１及びエンプティ・プライオリティ・レジスタ３２が、第１信号保持手段３０に相当する。
【００３０】
また、ヒット・プライオリティ・レジスタ３１及びエンプティ・プライオリティ・レジスタ３２の出力部は、第３のスイッチ回路ＳＷｎ＿３を介して、出力制御回路５０に接続されている。出力制御回路５０には、出力バスラインＯＤが接続されている。
【００３１】
更には、連想メモリ２０の第１の出力部は、出力制御回路５０に接続されている。また、連想メモリ２０の第２の出力部は、第４のスイッチ回路ＳＷｎ＿４を介して、１ビット構成のデバイス・ヒット・レジスタ４１、及び、１ビット構成のデバイス・エンプティ・レジスタ４２に接続されている。ここで、デバイス・ヒット・レジスタ４１及びデバイス・エンプティ・レジスタ４２が、第２信号保持手段４０に相当する。
【００３２】
デバイス・ヒット・レジスタ４１及びデバイス・エンプティ・レジスタ４２の出力部は、第５のスイッチ回路ＳＷｎ＿５を介して、出力端子ＯＵＴｎに接続され、出力端子ＯＵＴｎには配線Ｌｎが接続されている。また、出力制御回路５０は、第５のスイッチ回路ＳＷｎ＿５にも接続されている。
【００３３】
連想メモリチップ１０ｎは、連想メモリチップ１０ｎの識別番号（ＩＤ）に対応するデータを格納する識別番号格納手段６０を有している。具体的には、識別番号格納手段６０は、出力制御回路５０に接続されている。
【００３４】
連想メモリ２０の回路図を図３に示す。連想メモリ２０は、（Ｑ＋１）ビット（例えば、Ｑ＝７２）のメモリ２３ｎ＿ｐ（但し、ｐ＝１，２，・・・Ｐ）がＰ個、並置された構造を有する。ここで、各メモリ２３ｎ＿ｐにおいては、Ｑビットによってワードメモリが構成され、残りの１ビットに空きアドレスであるか否かを表すフラグ（空きアドレス・フラグ）が格納される。検索すべきデータは、Ｑビットによって構成されたワードメモリに格納されたデータ及び空きアドレス・フラグであり、あるいは又、空きアドレス・フラグである。
【００３５】
連想メモリ２０は、更に、検索データが入力され、ラッチされる検索データレジスタ２１、検索データをビット毎にマスクするマスクデータが格納されるマスクデータレジスタ２２、メモリ２３ｎ＿ｐに接続された一致線２４ｎ＿ｐ、一致線２４ｎ＿ｐに接続された一致フラグレジスタ２５ｎ＿ｐ、一致線２４ｎ＿ｐに接続されたＯＲ回路２６、一致フラグレジスタ２５ｎ＿ｐが接続されたアドレス・プライオリティ・エンコーダ２８を備えている。アドレス・プライオリティ・エンコーダ２８の出力部は、連想メモリ２０の第１の出力部に相当し、出力制御回路５０に接続されている。また、ＯＲ回路２６の出力部は、連想メモリ２０の第２の出力部に相当し、第４のスイッチ回路ＳＷｎ＿４に接続されている。
【００３６】
そして、複数のデータ検索コマンドのそれぞれ（具体的には、連想メモリ２０に格納されたワードに相当するデータを検索するコマンドであるワード検索コマンド、あるいは又、連想メモリ２０における空きアドレスの有無を検索する空きアドレス出力要求コマンド）が第ｎ番目の連想メモリチップ１０ｎにおいて実行されることによって得られるプライオリティ信号が、第ｎ番目の連想メモリチップ１０ｎを構成する第２信号保持手段４０において保持される。
【００３７】
より具体的には、プライオリティ信号は、ヒット（一致）信号ＳＨ、及び、エンプティ信号ＳＥである。ここで、ヒット（一致）信号ＳＨは、ワード検索コマンドの実行に基づき得ることができ、各連想メモリチップ１０ｎを構成するメモリ２３ｎ＿ｐに格納されたワードデータを検索し、ヒット（一致）したかどうかを示す信号である。また、エンプティ信号ＳＥは、空きアドレス出力要求コマンドに実行に基づき得ることができ、各連想メモリチップ１０ｎを構成するメモリ２３ｎ＿ｐが新たなデータを格納し得るメモリであるかどうかを示す信号である。そして、１ビットのヒット信号ＳＨはデバイス・ヒット・レジスタ４１に格納され、１ビットのエンプティ信号ＳＥはデバイス・エンプティ・レジスタ４２に格納される。
【００３８】
ここで、第１信号保持手段３０及び第２信号保持手段４０の数は、データ検索コマンドの種類の数（具体的には、連想メモリ２０に格納されたワードに相当するデータを検索するコマンドであるワード検索コマンド、及び、連想メモリ２０における空きアドレスの有無を検索する空きアドレス出力要求コマンドの２種類のコマンド）と等しい。
【００３９】
また、第ｍ番目の連想メモリチップ１０ｍを構成する第２信号保持手段４０（具体的には、デバイス・ヒット・レジスタ４１又はデバイス・エンプティ・レジスタ４２）において保持されたプライオリティ信号（具体的には、ヒット信号ＳＨ又はエンプティ信号ＳＥ）は、第ｍ番目の連想メモリチップ１０ｍを構成する出力端子ＯＵＴｍ及び第ｎ番目の連想メモリチップ１０ｎを構成する第ｍ番目の入力端子ＩＮｎ＿ｍを介して、第ｎ番目の連想メモリチップ１０ｎを構成する第１信号保持手段３０（ヒット・プライオリティ・レジスタ３１又はエンプティ・プライオリティ・レジスタ３２）に送られる。そして、第ｎ番目の連想メモリチップ１０ｎを構成する第１信号保持手段３０においてカスケード・プライオリティ信号（具体的には、カスケード・プライオリティ・ヒット信号ＣＰＳＨ又はカスケード・プライオリティ・エンプティ信号ＣＰＳＥ）として保持される。
【００４０】
そして、第ｎ番目の連想メモリチップ１０ｎを構成する出力制御回路５０において、第１信号保持手段３０に保持されたカスケード・プライオリティ信号と、第２信号保持手段４０に保持されたプライオリティ信号とが比較され、その比較結果に基づき、第ｎ番目の連想メモリチップ１０ｎを構成する出力制御回路５０からデータ検索コマンドの実行結果が出力される。
【００４１】
［ワード検索コマンドの実行］
以下、連想メモリ２０に格納されたワードに相当するデータを検索するコマンドであるワード検索コマンドの実行について、より具体的に説明を行う。
【００４２】
尚、各連想メモリチップ１０ｎを構成する連想メモリ２０におけるメモリ２３ｎ＿ｐにあっては、Ｑビットによって構成されたワードメモリにワードデータが格納されている場合、残りの１ビットに格納された空きアドレス・フラグは「０」である。一方、Ｑビットによって構成されたワードメモリにワードデータが格納されていない場合、残りの１ビットに格納された空きアドレス・フラグは「１」である。メモリ２３ｎ＿ｐへのデータの格納は周知の方法で行えばよい。
【００４３】
そして、検索データレジスタ２１にラッチされた検索ワードデータの内、マスクデータレジスタ２２に格納されたマスクデータによりマスクされていない全部、若しくは、所定の一部のビットパターンと、各メモリ２３ｎ＿ｐに格納されたデータのうち、上記ビットパターンと対応する部分のビットパターンとの一致不一致が比較され、各メモリ２３ｎ＿ｐのそれぞれに対応して備えられた一致線２４ｎ＿ｐのうち、ビットパターンが一致したメモリ２３ｎ＿ｐに対する一致線２４ｎ＿ｐに、信号「Ｈ」（一致信号）が出力される。それ以外の一致線２４ｎ＿ｐには、信号「Ｌ」（不一致信号）が出力される。
【００４４】
これらの一致線２４ｎ＿ｐに出力された信号は、各一致フラグレジスタ２５ｎ＿ｐに格納される。ここでは、一例として、図示したように、各一致フラグレジスタ２５ｎ＿ｐにそれぞれ「Ｌ」，「Ｈ」，「Ｈ」，「Ｌ」，・・・「Ｌ」，「Ｌ」が格納されたものとする。これらの一致フラグレジスタ２５ｎ＿ｐに格納された信号は、アドレス・プライオリティ・エンコーダ２８に入力され、このアドレス・プライオリティ・エンコーダ２８からは、一致信号「Ｈ」が格納された一致フラグレジスタ（ここでは、一致フラグレジスタ２５ｎ＿２及び一致フラグレジスタ２５ｎ＿３の２つ）のうちの優先度の最も高い一致フラグレジスタに対応するメモリアドレス信号が出力される。具体的には、添字「ｐ」が小さい程、優先順位が高いものとする。従って、ここでは一致フラグレジスタ２５ｎ＿２に対応するメモリアドレス信号が出力制御回路５０に出力される。
【００４５】
尚、一致線２４ｎ＿ｐは、ＯＲ回路２６にも接続されている。そして、一致線２４ｎ＿ｐのいずれかに一致信号「Ｈ」が流れたとき、ＯＲ回路２６から一致信号「Ｈ」が第４のスイッチ回路ＳＷｎ＿４に送出される。一方、全ての一致線２４ｎ＿ｐに不一致信号「Ｌ」が流れたとき、ＯＲ回路２６から不一致信号「Ｌ」が第４のスイッチ回路ＳＷｎ＿４に送出される。
【００４６】
以上に説明した動作は、各連想メモリチップ１０ｎ（ｎ＝１，２，・・・Ｎ）において、同時に実行される。
【００４７】
そして、ワード検索コマンドに基づき、ＯＲ回路２６の出力信号（一致信号「Ｈ」あるいは不一致信号「Ｌ」）が、第４のスイッチ回路ＳＷｎ＿４を介して、第２信号保持手段４０（具体的にはデバイス・ヒット・レジスタ４１）において、プライオリティ信号（具体的にはヒット信号ＳＨである一致信号「Ｈ」あるいは不一致信号「Ｌ」）として保持される。更には、このプライオリティ信号（具体的にはヒット信号ＳＨである一致信号「Ｈ」あるいは不一致信号「Ｌ」）は、ワード検索コマンドに基づき、第５のスイッチ回路ＳＷｎ＿５を介して、出力端子ＯＵＴｎに送られる。
【００４８】
更には、このプライオリティ信号（具体的にはヒット信号ＳＨである一致信号「Ｈ」あるいは不一致信号「Ｌ」）は、第ｎ’番目（但し、ｎ＜ｎ’≦Ｎ）の連想メモリチップ１０ｎ’を構成する第ｍ番目の入力端子ＩＮｎ’＿ｍに送られ、第ｎ’番目の連想メモリチップ１０ｎ’を構成するＯＲ回路に入力される。いずれかの入力端子ＩＮｎ’＿ｍにヒット信号ＳＨの内の一致信号「Ｈ」が入力された場合には、このＯＲ回路からは信号「Ｈ」が出力される。一方、全ての入力端子ＩＮｎ’＿ｍに不一致信号「Ｌ」が入力された場合には、このＯＲ回路からは信号「Ｌ」が出力される。そして、ワード検索コマンドに基づき、第２のスイッチ回路ＳＷｎ’＿２を介して、このＯＲ回路の出力は、第ｎ’番目の連想メモリチップ１０ｎ’を構成する第１信号保持手段３０（より具体的にはヒット・プライオリティ・レジスタ３１）に送られ、第ｎ’番目の連想メモリチップ１０ｎ’を構成する第１信号保持手段３０においてカスケード・プライオリティ信号（具体的にはカスケード・プライオリティ・ヒット信号ＣＰＳＨ）として保持される。
【００４９】
次いで、ワード検索コマンドに基づき、第ｎ’番目の連想メモリチップ１０ｎ’を構成する第３のスイッチ回路ＳＷｎ’＿３を介して、第１信号保持手段３０（具体的にはヒット・プライオリティ・レジスタ３１）において保持されたカスケード・プライオリティ・ヒット信号ＣＰＳＨは、出力制御回路５０に送られる。同時に、第ｎ’番目の連想メモリチップ１０ｎ’を構成する第２信号保持手段４０（具体的にはデバイス・ヒット・レジスタ４１）において保持されていたプライオリティ信号（具体的には、ヒット信号ＳＨ）も、ワード検索コマンドに基づき、第５のスイッチ回路ＳＷｎ’＿５を介して、出力制御回路５０に送られる。
【００５０】
そして、第ｎ’番目の連想メモリチップ１０ｎ’を構成する出力制御回路５０において、第１信号保持手段３０に保持されたカスケード・プライオリティ信号（具体的には、カスケード・プライオリティ・ヒット信号ＣＰＳＨ）と、第２信号保持手段４０に保持されたプライオリティ信号（具体的には、ヒット信号ＳＨ）とが比較される。
【００５１】
比較結果は、以下の表１のとおりとなる。
【００５２】
2004295938.tif 000003
【００５３】
ケース１及びケース２の場合、例えば、第ｎ’番目の連想メモリチップ１０ｎ’よりもプライオリティが高い連想メモリチップ１０ｎ（ｎ＜ｎ’）からのプライオリティ情報（カスケード・プライオリティ・ヒット信号ＣＰＳＨにおける一致信号「Ｈ」）が存在するが故に、たとえ、第ｎ’番目の連想メモリチップ１０ｎ’において、検索ワードデータと一致するデータを格納したワードメモリが存在したとしても、第ｎ’番目の連想メモリチップ１０ｎ’からは何ら出力しない。第ｎ’番目の連想メモリチップ１０ｎ’からは、第（ｎ’＋１）番目以降の連想メモリチップ１０（ｎ’＋１），・・・に、プライオリティ信号（カスケード・プライオリティ・ヒット信号ＣＰＳＨを構成する一致信号「Ｈ」あるいは不一致信号「Ｌ」）を送出するだけである。
【００５４】
一方、ケース３の場合、例えば、第ｎ’番目の連想メモリチップ１０ｎ’よりもプライオリティが高い連想メモリチップ１０ｎ（ｎ＜ｎ’）からのプライオリティ情報（カスケード・プライオリティ・ヒット信号ＣＰＳＨにおける一致信号「Ｈ」）が存在せず、且つ、第ｎ’番目の連想メモリチップ１０ｎ’において、検索ワードデータと一致するデータを格納したワードメモリが存在しているので、第ｎ’番目の連想メモリチップ１０ｎ’からデータ検索コマンドの実行結果（即ち、係るワードメモリのメモリアドレス信号）が出力制御回路５０を介して出力バスラインＯＤに出力される。尚、連想メモリ２０に格納されたワードデータの複数が一致する場合もあるが、このような場合には、一般にアドレスの小さいものを優先して出力するようにする。更には、第ｎ’番目の連想メモリチップ１０ｎ’からは、第（ｎ’＋１）番目以降の連想メモリチップ１０（ｎ’＋１），・・・に、プライオリティ信号（カスケード・プライオリティ・ヒット信号ＣＰＳＨを構成する一致信号「Ｈ」）を送出する。
【００５５】
また、ケース４の場合、例えば、第ｎ’番目の連想メモリチップ１０ｎ’よりもプライオリティが高い連想メモリチップ１０ｎ（ｎ＜ｎ’）からのプライオリティ情報（カスケード・プライオリティ・ヒット信号ＣＰＳＨにおける一致信号「Ｈ」）が存在せず、且つ、第ｎ’番目の連想メモリチップ１０ｎ’において、検索ワードデータと一致するデータを格納したワードメモリが存在しないので、第ｎ’番目の連想メモリチップ１０ｎ’からは何ら出力しない。第ｎ’番目の連想メモリチップ１０ｎ’からは、第（ｎ’＋１）番目以降の連想メモリチップ１０（ｎ’＋１），・・・に、プライオリティ信号（カスケード・プライオリティ・ヒット信号ＣＰＳＨを構成する不一致信号「Ｌ」）を送出するだけである。
【００５６】
［空きアドレス出力要求コマンドの実行］
次に、連想メモリ２０における空きアドレスの有無を検索する空きアドレス出力要求コマンドの実行について、より具体的に説明を行う。
【００５７】
尚、各連想メモリチップ１０ｎを構成する連想メモリ２０におけるメモリ２３ｎ＿ｐにあっては、Ｑビットによって構成されたワードメモリにワードデータが格納されている場合、残りの１ビットに格納された空きアドレス・フラグは「０」である。一方、Ｑビットによって構成されたワードメモリにワードデータが格納されていない場合、残りの１ビットに格納された空きアドレス・フラグは「１」である。メモリ２３ｎ＿ｐへのデータの格納は周知の方法で行えばよい。
【００５８】
そして、検索データレジスタ２１において空きアドレス・フラグを「１」にセットする。次いで、各メモリ２３ｎ＿ｐに格納されたデータのうち、空きアドレス・フラグが「１」であるか否かが比較され、各メモリ２３ｎ＿ｐのそれぞれに対応して備えられた一致線２４ｎ＿ｐのうち、空きアドレス・フラグが「１」であるメモリ２３ｎ＿ｐに対する一致線２４ｎ＿ｐに、信号「Ｈ」（一致信号）が出力される。それ以外の一致線２４ｎ＿ｐには、信号「Ｌ」（不一致信号）が出力される。
【００５９】
これらの一致線２４ｎ＿ｐに出力された信号は、各一致フラグレジスタ２５ｎ＿ｐに格納される。ここでは、一例として、図示したように、各一致フラグレジスタ２５ｎ＿ｐにそれぞれ「Ｌ」，「Ｈ」，「Ｈ」，「Ｌ」，・・・「Ｌ」，「Ｌ」が格納されたものとする。これらの一致フラグレジスタ２５ｎ＿ｐに格納された信号は、アドレス・プライオリティ・エンコーダ２８に入力され、このアドレス・プライオリティ・エンコーダ２８からは、一致信号「Ｈ」が格納された一致フラグレジスタ（ここでは、一致フラグレジスタ２５ｎ＿２及び一致フラグレジスタ２５ｎ＿３の２つ）のうちの優先度の最も高い一致フラグレジスタに対応するメモリアドレス信号が出力される。具体的には、添字「ｐ」が小さい程、優先順位が高いものとする。従って、ここでは一致フラグレジスタ２５ｎ＿２に対応するメモリアドレス信号が出力制御回路５０に出力される。
【００６０】
尚、一致線２４ｎ＿ｐは、ＯＲ回路２６にも接続されている。そして、一致線２４ｎ＿ｐのいずれかに一致信号「Ｈ」が流れたとき、ＯＲ回路２６から一致信号「Ｈ」が第４のスイッチ回路ＳＷｎ＿４に送出される。一方、全ての一致線２４ｎ＿ｐに不一致信号「Ｌ」が流れたとき、ＯＲ回路２６から不一致信号「Ｌ」が第４のスイッチ回路ＳＷｎ＿４に送出される。
【００６１】
以上に説明した動作は、各連想メモリチップ１０ｎ（ｎ＝１，２，・・・Ｎ）において、同時に実行される。
【００６２】
そして、空きアドレス出力要求コマンドに基づき、ＯＲ回路２６の出力信号（一致信号「Ｈ」あるいは不一致信号「Ｌ」）が、第４のスイッチ回路ＳＷｎ＿４を介して、第２信号保持手段４０（具体的にはデバイス・エンプティ・レジスタ４２）において、プライオリティ信号（具体的にはエンプティ信号ＳＥである一致信号「Ｈ」あるいは不一致信号「Ｌ」）として保持される。更には、このプライオリティ信号（具体的にはエンプティ信号ＳＥである一致信号「Ｈ」あるいは不一致信号「Ｌ」）は、空きアドレス出力要求コマンドに基づき、第５のスイッチ回路ＳＷｎ＿５を介して、出力端子ＯＵＴｎに送られる。
【００６３】
更には、このプライオリティ信号（具体的にはエンプティ信号ＳＥである一致信号「Ｈ」あるいは不一致信号「Ｌ」）は、第ｎ’番目（但し、ｎ＜ｎ’≦Ｎ）の連想メモリチップ１０ｎ’を構成する第ｍ番目の入力端子ＩＮｎ’＿ｍに送られ、第ｎ’番目の連想メモリチップ１０ｎ’を構成するＯＲ回路に入力される。いずれかの入力端子ＩＮｎ’＿ｍにエンプティ信号ＳＥの内の一致信号「Ｈ」が入力された場合には、このＯＲ回路からは信号「Ｈ」が出力される。一方、全ての入力端子ＩＮｎ’＿ｍに不一致信号「Ｌ」が入力された場合には、このＯＲ回路からは信号「Ｌ」が出力される。そして、空きアドレス出力要求コマンドに基づき、第２のスイッチ回路ＳＷｎ’＿２を介して、このＯＲ回路の出力は、第ｎ’番目の連想メモリチップ１０ｎ’を構成する第１信号保持手段３０（より具体的にはエンプティ・プライオリティ・レジスタ３２）に送られ、第ｎ’番目の連想メモリチップ１０ｎ’を構成する第１信号保持手段３０においてカスケード・プライオリティ信号（具体的にはカスケード・プライオリティ・エンプティ信号ＣＰＳＥ）として保持される。
【００６４】
次いで、空きアドレス出力要求コマンドに基づき、第ｎ’番目の連想メモリチップ１０ｎ’を構成する第３のスイッチ回路ＳＷｎ’＿３を介して、第１信号保持手段３０（具体的にはエンプティ・プライオリティ・レジスタ３２）において保持されたカスケード・プライオリティ・エンプティ信号ＣＰＳＥは、出力制御回路５０に送られる。同時に、第ｎ’番目の連想メモリチップ１０ｎ’を構成する第２信号保持手段４０（具体的にはデバイス・エンプティ・レジスタ４２）において保持されていたプライオリティ信号（具体的には、エンプティ信号ＳＥ）も、空きアドレス出力要求コマンドに基づき、第５のスイッチ回路ＳＷｎ’＿５を介して、出力制御回路５０に送られる。
【００６５】
そして、第ｎ’番目の連想メモリチップ１０ｎ’を構成する出力制御回路５０において、第１信号保持手段３０に保持されたカスケード・プライオリティ信号（具体的には、カスケード・プライオリティ・エンプティ信号ＣＰＳＥ）と、第２信号保持手段４０に保持されたプライオリティ信号（具体的には、エンプティ信号ＳＥ）とが比較される。
【００６６】
比較結果は、以下の表２のとおりとなる。
【００６７】
2004295938.tif 000004
【００６８】
ケース１及びケース２の場合、例えば、第ｎ’番目の連想メモリチップ１０ｎ’よりもプライオリティが高い連想メモリチップ１０ｎ（ｎ＜ｎ’）からのプライオリティ情報（カスケード・プライオリティ・エンプティ信号ＣＰＳＥにおける一致信号「Ｈ」）が存在するが故に、たとえ、第ｎ’番目の連想メモリチップ１０ｎ’において、空きアドレス・フラグが「１」であるメモリ２３ｎ’＿ｐが存在したとしても、第ｎ’番目の連想メモリチップ１０ｎ’からは何ら出力しない。第ｎ’番目の連想メモリチップ１０ｎ’からは、第（ｎ’＋１）番目以降の連想メモリチップ１０（ｎ’＋１），・・・に、プライオリティ信号（カスケード・プライオリティ・エンプティ信号ＣＰＳＥを構成する一致信号「Ｈ」あるいは不一致信号「Ｌ」）を送出するだけである。
【００６９】
一方、ケース３の場合、例えば、第ｎ’番目の連想メモリチップ１０ｎ’よりもプライオリティが高い連想メモリチップ１０ｎ（ｎ＜ｎ’）からのプライオリティ情報（カスケード・プライオリティ・エンプティ信号ＣＰＳＥにおける一致信号「Ｈ」）が存在せず、且つ、第ｎ番目の連想メモリチップ１０ｎ’において、空きアドレス・フラグが「１」であるメモリ２３ｎ’＿ｐが存在しているので、第ｎ’番目の連想メモリチップ１０ｎ’からデータ検索コマンドの実行結果（即ち、係るメモリ２３ｎ’＿ｐのアドレス）が出力制御回路５０を介して出力バスラインＯＤに出力される。尚、連想メモリ２０中にこのようなメモリ２３ｎ’＿ｐが複数、存在する場合もあるが、このような場合には、一般にアドレスの小さいものを優先して出力するようにする。更には、第ｎ’番目の連想メモリチップ１０ｎ’からは、第（ｎ’＋１）番目以降の連想メモリチップ１０（ｎ’＋１），・・・に、プライオリティ信号（カスケード・プライオリティ・エンプティ信号ＣＰＳＥを構成する一致信号「Ｈ」）を送出する。
【００７０】
また、ケース４の場合、例えば、第ｎ’番目の連想メモリチップ１０ｎ’よりもプライオリティが高い連想メモリチップ１０ｎ（ｎ＜ｎ’）からのプライオリティ情報（カスケード・プライオリティ・エンプティ信号ＣＰＳＥにおける一致信号「Ｈ」）が存在せず、且つ、第ｎ’番目の連想メモリチップ１０ｎ’において、空きアドレス・フラグが「１」であるメモリ２３ｎ’＿ｐが存在しないので、第ｎ’番目の連想メモリチップ１０ｎ’からは何ら出力しない。第ｎ’番目の連想メモリチップ１０ｎ’からは、第（ｎ’＋１）番目以降の連想メモリチップ１０（ｎ’＋１），・・・に、プライオリティ信号（カスケード・プライオリティ・エンプティ信号ＣＰＳＥを構成する不一致信号「Ｌ」）を送出するだけである。
【００７１】
尚、ワード検索コマンドの実行及び空きアドレス出力要求コマンドの実行が完了した時点で、検索によってヒットしたアドレスを再度読み出すコマンド（検索結果を利用したコマンド）が入力されると、ワード検索コマンドの実行結果としてプライオリティを持つ連想メモリチップのヒットアドレスレジスタ（図示せず）に保持されたメモリ２３ｎ’＿ｐのメモリアドレス信号ＡＤがデコーダ２９ｎ’＿ｐに入力される。デコーダ２９ｎ’＿ｐでは、この入力されたメモリアドレス信号ＡＤをデコードして、各メモリ２３ｎ’＿ｐのそれぞれに対応して備えられたワード線の内の入力されたメモリアドレス信号ＡＤに対応する、いずれか１本のワード線（ここでは、メモリ２３ｎ’＿２におけるワード線）にアクセス信号を出力する。これにより、アクセス信号の出力されたワード線に対応するメモリ２３ｎ’＿２に格納されているワードデータが出力レジスタ２７に読み出される。
【００７２】
ここで、データ検索コマンドの実行の結果、どの連想メモリチップにもヒットデータが存在しない場合がある。即ち、図１において、最もプライオリティの低い連想メモリチップ１０８に着目すると、データ検索コマンドの実行の結果、上位の連想メモリチップ１０１〜１０７の出力端子ＯＵＴ１〜ＯＵＴ７に接続された入力端子ＩＮ７＿１〜ＩＮ７＿７における入力信号が全て「Ｌ」、つまり、連想メモリチップ１０１〜１０７の全てでヒットが無く、しかも、連想メモリチップ１０８におけるデータ検索コマンドの実行の結果、ヒットが無い場合、出力バスラインＯＤに出力される信号が不定になる虞がある。このような場合のために、連想メモリチップ１０８が、連想メモリ装置における最後の連想メモリチップ（即ち、最もプライオリティの低い連想メモリチップ）であるとの特定がなされ、この連想メモリ装置における最後の連想メモリチップから、連想メモリ装置全体にヒットがなかったことを出力する必要がある。
【００７３】
そのために、実施の形態１における連想メモリ装置にあっては、リセット端子（ＲＥＳＥＴ）によるリセット時（あるいは、連想メモリ装置の初期化時）における入力端子の状態を利用する（図４参照）。具体的には、リセット端子（ＲＥＳＥＴ）によるリセット時（あるいは、連想メモリ装置の初期化時）、第１番目〜第７番目の連想メモリチップ１０１〜１０７の出力端子ＯＵＴ１〜ＯＵＴ７から信号「Ｈ」を出力する。具体的には、リセット時（あるいは、連想メモリ装置の初期化時）、出力制御回路５０から第５のスイッチ回路ＳＷｎ＿５を介して、出力端子ＯＵＴｎから信号「Ｈ」が出力される。
【００７４】
そして、第ｎ番目の連想メモリチップ１０ｎにおいて、全ての入力端子ＩＮｎ＿ｍと第２のスイッチ回路ＳＷｎ＿２の入力部との間には、第１のスイッチ回路ＳＷｎ＿１を介してＡＮＤ回路が配置されている。このＡＮＤ回路は、リセット時（あるいは、連想メモリ装置の初期化時）のみ動作し、通常の動作においては、全ての入力端子ＩＮｎ＿ｍと第２のスイッチ回路ＳＷｎ＿２の入力部との間に配置されたＯＲ回路が、第１のスイッチ回路ＳＷｎ＿１を介して、動作する。そして、リセット時（あるいは、連想メモリ装置の初期化時）、第２のスイッチ回路ＳＷｎ＿２の出力部は、１ビット構成のヒット・プライオリティ・レジスタ３１に接続される。
【００７５】
リセット時（あるいは、連想メモリ装置の初期化時）、連想メモリ装置における最後の連想メモリチップ（即ち、最もプライオリティの低い連想メモリチップ）である第８番目の連想メモリチップ１０８にあっては、全ての入力端子ＩＮｎ＿ｍの受け取る信号は「Ｈ」であるが故に、１ビット構成のヒット・プライオリティ・レジスタ３１の状態は「Ｈ」となる。一方、それ以外の連想メモリチップ１０１〜１０７にあっては、１ビット構成のヒット・プライオリティ・レジスタ３１の状態は「Ｌ」となる。第３のスイッチ回路ＳＷｎ＿３を介してヒット・プライオリティ・レジスタ３１の状態を受け取った出力制御回路５０は、ヒット・プライオリティ・レジスタ３１の状態が「Ｈ」である場合には、デバイスＩＤレジスタである識別番号格納手段６０に、連想メモリチップの識別番号に対応するデータであるデータ「１」を書き込み、ヒット・プライオリティ・レジスタ３１の状態が「Ｌ」である場合には、デバイスＩＤレジスタである識別番号格納手段６０に、連想メモリチップの識別番号に対応するデータであるデータ「０」を書き込む。これによって、デバイスＩＤレジスタである識別番号格納手段６０にデータ「１」が書き込まれている場合には、係る連想メモリチップは、連想メモリ装置における最後の連想メモリチップ（即ち、最もプライオリティの低い連想メモリチップ）であると、出力制御回路５０において判断することができ、係る連想メモリチップから、連想メモリ装置全体にヒットがなかったことを出力することができる。
【００７６】
以上、本発明を、発明の実施の形態に基づき説明したが、本発明はこれらに限定されるものではない。連想メモリ装置、連想メモリチップ、連想メモリの構造、構成は例示であり、適宜変更することができる。
【００７７】
第１信号保持手段３０及び第２信号保持手段４０をそれぞれ２つのレジスタから構成しているが、このような構成は必須ではない。例えば、ワード検索コマンドの実行が完了した時点で、直ちに、検索によってヒットしたアドレスを再度読み出すコマンド（検索結果を利用したコマンド）が入力されるような場合には、第１信号保持手段３０及び第２信号保持手段４０をそれぞれ１つとすることもできる。即ち、入力端子を介して伝播する情報が変化する前に、その情報がどのプライオリティに相当するかを識別し、識別と同時にプライオリティ・レジスタである第１信号保持手段３０及び第２信号保持手段４０に情報（値）を保持することが可能である。このような状態において、新たな種類のプライオリティ信号が入力端子から入力されたときには、入力端子からの入力信号がもう１つのプライオリティ信号を表現していることになる。
【００７８】
図１〜図４に示した連想メモリ装置にあっては、連想メモリチップを８個、カスケード接続した例とした。一方、図５及び図６には、連想メモリチップを５個、カスケード接続した例を示す。第１番目の連想メモリチップ１０１から第４番目の連想メモリチップ１０４までは、実施の形態１にて説明した第１番目の連想メモリチップ１０１から第４番目の連想メモリチップ１０４までの構造と同じである。一方、連想メモリ装置における最後の連想メモリチップ（即ち、最もプライオリティの低い連想メモリチップ）である第５番目の連想メモリチップ１０５における入力端子ＩＮ５＿５〜ＩＮ５＿７は、スイッチ回路ＳＷＡ，ＳＷＢの切り替えによって、データ検索コマンドの実行時には接地され、リセット時（あるいは、連想メモリ装置の初期化時）には電源Ｖｃｃに接続される。尚、スイッチ回路ＳＷＡ，ＳＷＢの切り替えは、コマンドに基づく。このような構成にすることで、リセット時（あるいは、連想メモリ装置の初期化時）、第５番目の連想メモリチップ１０５における入力端子ＩＮ５＿５〜ＩＮ５＿７の状態は全て「Ｈ」状態となる。尚、図６においては、入力端子ＩＮ５＿５〜ＩＮ５＿７の状態を「Ｈ＊」で示す。従って、第５番目の連想メモリチップ１０５が、連想メモリ装置における最後の連想メモリチップ（即ち、最もプライオリティの低い連想メモリチップ）であることを認識することができる。
【００７９】
第ｎ番目の連想メモリチップ１０ｎの入力端子ＩＮｎ＿ｍの「Ｈ」状態及び「Ｌ」状態を、ＡＮＤ回路を介在させることなく、出力制御回路５０を介して（Ｎ−１）ビット構成のレジスタから成る識別番号格納手段６０に格納すれば、識別番号格納手段６０においてデバイスＩＤを保存することが可能となる。また、以上に説明した連想メモリ装置において、信号「Ｈ」と、信号「Ｌ」とを置き換える構成とすることもできる。
【００８０】
【発明の効果】
本発明にあっては、従来の連想メモリ装置における大きな問題点であったカスケード接続に関連する入力端子数（ピン数）や配線の増加を最小化することが可能となる。これによって、連想メモリ装置のパッケージにおけるピン数の減少並びに実装基板上の配線を著しく減少させることができ、よりコンパクトなデータ検索装置を構築することができる。
【図面の簡単な説明】
【図１】図１は、発明の実施の形態１の連想メモリ装置の回路図である。
【図２】図２は、各連想メモリチップの回路図である。
【図３】図３は、連想メモリの回路図である。
【図４】図４は、発明の実施の形態１における連想メモリ装置において、リセット端子によるリセット時（あるいは、連想メモリ装置の初期化時）における入力端子の状態を示す図である。
【図５】図１は、発明の実施の形態１の連想メモリ装置の変形例の回路図である。
【図６】図６は、発明の実施の形態１における連想メモリ装置の変形例において、リセット端子によるリセット時（あるいは、連想メモリ装置の初期化時）における入力端子の状態を示す図である。
【図７】図７は、複数の連想メモリチップをカスケード接続したときの概念図である。
【符号の説明】
１０ｎ・・・連想メモリチップ、２０・・・連想メモリ、２１・・・検索データレジスタ、２２・・・マスクデータレジスタ、２３ｎ＿ｐ・・・メモリ、２４ｎ＿ｐ・・・一致線、２５ｎ＿ｐ・・・一致フラグレジスタ、２６・・・ＯＲ回路、２７・・・出力レジスタ、２８・・・アドレス・プライオリティ・エンコーダ、２９ｎ＿ｐ・・・デコーダ、３０・・・第１信号保持手段、３１・・・ヒット・プライオリティ・レジスタ、３２・・・エンプティ・プライオリティ・レジスタ、４０・・・第２信号保持手段、４１・・・デバイス・ヒット・レジスタ、４２・・・デバイス・エンプティ・レジスタ、５０・・・出力制御回路、６０・・・識別番号格納手段、ＩＮｎ＿ｍ・・・入力端子、ＯＵＴｎ・・・出力端子、ＳＷｎ＿１，ＳＷｎ＿２，ＳＷｎ＿３，ＳＷｎ＿４，ＳＷｎ＿５・・・スイッチ回路、ＯＤ・・・出力バスライン、Ｌｎ・・・配線
【図１】
2004295938.tif 000005
【図２】
2004295938.tif 000006
【図３】
2004295938.tif 000007
【図４】
2004295938.tif 000008
【図５】
2004295938.tif 000009
【図６】
2004295938.tif 000010
【図７】
2004295938.tif 000011