(57)【特許請求の範囲】
【請求項１】
第１ワード線及び第２ワード線を含む複数のワード線と、
前記第１ワード線に接続する第１の複数のターナリセルに含まれる第１のターナリセル、及び、前記第２ワード線に接続する第２の複数のターナリセルに含まれ、前記第１のターナリセルのビット位置に対応するビット位置の第２のターナリセルであって、有効データである０と１、及び無効データの３値のデータの何れか１つを格納する前記第１のターナリセル及び前記第２のターナリセルと、
前記第１のターナリセルの該ビット位置に対応して設けられた広報信号線と、
前記広報信号線に接続され、前記第１のターナリセルのエントリデータがエントリキーと一致し、且つ前記第１のターナリセルの内容が有効データであるとき、前記第１のターナリセルの該ビット位置における有効データの存在を示す広報信号を前記広報信号線に出力する有効データ検出回路と、
前記複数のワード線に対してワード線毎に設けられ、対応するターナリセルのエントリデータがエントリキーと不一致の場合に、第１の状態から、不一致を示す第２の状態に変化する複数のマッチラインと、
前記広報信号線に接続され、前記広報信号に応答して、前記第２のターナリセルに無効データが存在する場合に、前記複数のマッチラインにおける前記第２のワード線に対応するマッチラインを前記第２状態に変化させるロンゲストマッチ検出回路と
を含むことを特徴とする連想記憶装置。
【請求項２】
該有効データ検出回路及び該ロンゲストマッチ検出回路は、各ターナリセルに対して設けられることを特徴とする請求項１記載の連想記憶装置。
【請求項３】
前記マッチラインは初期状態で前記第１の状態であり、各々のターナリセルは格納内容が該エントリキーの対応する部分と不一致の場合に該マッチラインを前記第２の状態とする構成であることを特徴とする請求項１記載の連想記憶装置。
【請求項４】
最長有効データ長を記憶するレジスタと、
該レジスタが示す有効データ部分では該有効データ検出回路と該ロンゲストマッチ検出回路の動作を停止させ、該レジスタが示す無効データ部分で該有効データ検出回路と該ロンゲストマッチ検出回路を動作させる回路
を更に含むことを特徴とする請求項１記載の連想記憶装置。
【請求項５】
各ビット位置毎に該有効データ検出回路が有効データの存在を広報する広報信号線と、
該広報信号線の信号に応じて該ロンゲストマッチ検出回路に有効データの存在を知らせる通知信号線
を更に含むことを特徴とする請求項１記載の連想記憶装置。
【請求項６】
該通知信号線は該広報信号線の論理反転信号を送信することを特徴とする請求項５記載の連想記憶装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に半導体記憶装置に関し、詳細には連想記憶装置に関する。
【従来の技術】
連想記憶装置（ＣＡＭ：Content Addressable Memory）は、データを入力としてアドレスを出力する記憶装置であり、入力データと一致するデータを記憶領域内で検出して、一致するデータが格納されているアドレスを出力する。この入力データをエントリキーと呼び、記憶されているデータをエントリデータと呼ぶ。
【０００２】
通常の半導体記憶装置では、１つのアドレス入力に対してデータ出力が一意に決定されるが、ＣＡＭではエントリキー（入力データ）と一致するエントリデータ（記憶データ）が複数個存在する場合があり、一致検出だけでは出力データを一意に決定することが出来ない。このような場合に備えて、ＣＡＭ内部では、エントリデータに対して優先順位が割り振られており、複数のエントリデータが一致する場合には、優先順位が一番高いエントリデータのアドレスが出力される。
【０００３】
エントリデータの優先順位を決定するためには、各アドレスに優先順位を割り当てておき、優先順位が一番高いアドレスを出力する構成が一般的である。この場合、例えば、先頭アドレスを最優先の優先順位として、アドレスが大きくなるほど優先順位が下がるように構成する。複数のエントリデータがエントリキーに一致する場合には、一致するエントリデータのアドレスのうちで最も小さいアドレスを検出し、そのアドレスを出力する。
【発明が解決しようとする課題】
上記のような構成において、所定の優先順位を有するエントリデータを書き込む際、アドレス空間内において優先順位の順に並べられた既存のエントリデータが存在するので、順番に並べられた既存のエントリデータの途中に新たなエントリデータを挿入する必要がある。即ち例えば、既存のエントリデータと比較して３番目に重要なエントリデータを書き込む際には、既存のエントリデータのうちで優先順位が３番目以降のエントリデータを全て、夫々１つ大きいアドレスに格納し直して、優先順位が３番目に対応するアドレスを空ける必要がある。このように既存データのうちで、移動が必要な部分全体をアドレス空間内でシフトした後に、空いたアドレスに新規のエントリデータを書き込むことになる。
【０００４】
このように、アドレスに優先順位を付けてアドレス空間内でエントリデータをプライオリティー順に並べる方式では、上記のようにエントリデータ書き込み時に、既存のエントリデータの一部を全体的に移動する必要があり、システムの実効性能が著しく低下するという問題がある。
【０００５】
以上を鑑みて、本発明は、アドレスと優先順位とを関係付けることなく、最優先のエントリデータを検出可能な連想記憶装置を提供することを目的とする。
【課題を解決するための手段】
本発明の連想記憶装置は、第１ワード線及び第２ワード線を含む複数のワード線と、前記第１ワード線に接続する第１の複数のターナリセルに含まれる第１のターナリセル、及び、前記第２ワード線に接続する第２の複数のターナリセルに含まれ、前記第１のターナリセルのビット位置に対応するビット位置の第２のターナリセルであって、有効データである０と１、及び無効データの３値のデータの何れか１つを格納する前記第１のターナリセル及び前記第２のターナリセルと、前記第１のターナリセルの該ビット位置に対応して設けられた広報信号線と、前記広報信号線に接続され、前記第１のターナリセルのエントリデータがエントリキーと一致し、且つ前記第１のターナリセルの内容が有効データであるとき、前記第１のターナリセルの該ビット位置における有効データの存在を示す広報信号を前記広報信号線に出力する有効データ検出回路と、前記複数のワード線に対してワード線毎に設けられ、対応するターナリセルのエントリデータがエントリキーと不一致の場合に、第１の状態から、不一致を示す第２の状態に変化する複数のマッチラインと、前記広報信号線に接続され、前記広報信号に応答して、前記第２のターナリセルに無効データが存在する場合に、前記複数のマッチラインにおける前記第２のワード線に対応するマッチラインを前記第２状態に変化させるロンゲストマッチ検出回路とを含むことを特徴とする。
【０００６】
上記発明においては、ロンゲストマッチのエントリデータを検出するために、各ターナリセルに広報機能を備える。この広報機能は、自らのターナリセルの属するエントリデータが一致データであり、しかも自らのセルの内容が有効データであるときに、同一のビット位置にある他のターナリセルに対して、自らが有効データであることを広報する。このようにして有効データの存在が広報されると、同一のビット位置にある他のターナリセルは、自らのセルの内容が無効データである場合には、自らのターナリセルの属するエントリデータが一致データであるがロンゲストマッチではないことが判明するので、データ一致を示す状態からデータ不一致を示す状態に変更する。
【０００７】
このように、あるセルの内容が無効データであり、同一ビット位置の他のセルにエントリデータが一致する有効データが存在する場合には、自らの属するエントリデータが最優先データでないことを判断して、このエントリデータを最優先データの候補からおろす。これによって、最終的に残ったエントリデータを、最優先データとして検出することが出来る。
【発明の実施の形態】
以下に、本発明の実施例を添付の図面を用いて詳細に説明する。
【０００８】
最初に、実施例の理解を容易にするために、本発明の原理を説明する。
【０００９】
ＣＡＭにおいて、エントリキー及びエントリデータは、１、０、及びｘ（マスク或いはマスクプレフィックス）の３値からなるターナリデータ（Ternary）である。図１は、ＣＡＭにおいて一般的に用いられるターナリセルを示す。
【００１０】
図１のターナリセル１０は、ＮＭＯＳトランジスタ１１乃至１８とインバータ１９乃至２２とを含む。インバータ１９及び２０で１ビットを格納するラッチを形成し、インバータ２１及び２２で１ビットを格納するラッチを形成する。ターナリセル１０が１を格納する場合には、ノードＮ１が０でノードＮ２が１になるようにデータが格納される。ターナリセル１０が０を格納する場合には、ノードＮ１が１でノードＮ２が０になるようにデータが格納される。またターナリセル１０がｘを格納する場合には、ノードＮ１及びノードＮ２が双方とも０になるようにデータが格納される。なおデータ格納は、ビット線ＢＬ（１）及び／ＢＬ（１）とビット線ＢＬ（２）及び／ＢＬ（２）にデータを供給して、ワード線ＷＬを活性化することにより行われる。
【００１１】
エントリキーは、サーチバスＳＢ及び／ＳＢから供給される。エントリキーが１の場合には、サーチバスＳＢ及び／ＳＢはそれぞれ１及び０となる。またエントリキーが０の場合には、サーチバスＳＢ及び／ＳＢはそれぞれ０及び１となる。更に、エントリキーがｘの場合には、サーチバスＳＢ及び／ＳＢは双方共に０となる。従って、エントリキーの０／１がエントリデータの０／１と一致する場合には、マッチラインＭＬはＨＩＧＨのままである。不一致の場合にはＮＭＯＳトランジスタ１３及び１４が同時に導通するか、或いはＮＭＯＳトランジスタ１７及び１８が同時に導通し、結果としてマッチラインＭＬはグランドに接続されてＬＯＷとなる。またエントリキー或いはエントリデータの何れか一方がマスクｘであるときは、マッチラインＭＬはＨＩＧＨのままである。
【００１２】
このようなターナリセル１０が、並列に接続されて、複数のデータ列からなるエントリキーに対する一致／不一致が判定される。
【００１３】
図２は、ターナリセル１０が縦横に配置されたセルマトリックスを示す。図２に示されるように、行列状に配置されたターナリセル１０のうち、行方向のターナリセル１０のマッチラインＭＬを共通とする。このような構成において、サーチバスＳＢ及び／ＳＢに供給されるエントリキーが、行方向に配置された複数のターナリセル１０のデータ列であるエントリデータと一致すると、マッチラインＭＬはＨＩＧＨである。またエントリキーとエントリデータとの間に一箇所でも不一致があると、不一致箇所のターナリセル１０においてマッチラインＭＬがグランドに接続されるために、マッチラインＭＬはＬＯＷとなる。
【００１４】
エントリキー或いはエントリデータにマスクｘが含まれる場合には、その箇所においては不一致判定が出ることは無く、データの一致／不一致には無関係なドントケアとなる。従って、例えば、“001011xx”がエントリキーであるときは、“00101xxx” や“0010110x”のエントリデータは一致判定となる。なおマスクデータ即ち非有効データは、必ずＬＳＧ側に連続して並ぶように存在し、マスクデータが有効データの間に挟まれるように存在することはない
一般的に、エントリデータの優先順位は、マスクｘの数によって決定される。即ち、エントリデータのうちでマスクｘの数が最も少ないものが最優先のエントリデータであり、マスクｘの数が最も多いものが最も優先順位の低いエントリデータである。例えば、以下の複数のエントリデータは、最初の行のものが最優先であり、下の行に行くほど順番に優先順位が低くなる。
【００１５】
“00101001”
“1011100x”
“011000xx”
“11101xxx”
“1001xxxx”
従って、エントリキーと一致するエントリデータが複数個存在する場合、一致するエントリデータのうちで、マスクｘの数が最も少ないものを最優先のエントリデータとして検出し、そのメモリアドレスをＣＡＭの出力とすればよい。
【００１６】
本発明においては、マスクｘの数が最も少ないものを最優先のエントリデータとして検出する。この目的のために、マスクデータ即ち非有効データは必ずＬＳＧ側に連続して並ぶように存在し、マスクデータが有効データの間に挟まれるように存在することはないという性質を利用する。例えば、エントリキーが“0010111x”であるとして、以下のような複数の一致エントリデータが存在するとする。
【００１７】
“0010110x”  （第１のエントリデータ）
“001011xx”  （第２のエントリデータ）
“00101xxx”  （第３のエントリデータ）
“0010xxxx”  （第４のエントリデータ）
この場合、第４のエントリデータにおいては、右から４番目のビットがマスクデータであり、第１乃至第３のエントリデータの同じ位置のビットである右から４番目のビットが有効データであることから、第４のエントリデータはマスク数が最小の一致データではない。また第３のエントリデータにおいては、右から３番目のビットがマスクデータであり、第１及び第２のエントリデータの同じ位置のビットである右から３番目のビットが有効データであることから、第３のエントリデータはマスク数が最小の一致データではない。また第２のエントリデータにおいては、右から２番目のビットがマスクデータであり、第１のエントリデータの同じ位置のビットである右から２番目のビットが有効データであることから、第２のエントリデータはマスク数が最小の一致データではない。従って、第２乃至第４のエントリデータは、マスク数が最小である一致データではないことが分かる。これによって、第２乃至第４のエントリデータを除いて唯一残った第１のエントリデータが、マスク数が最小である一致データであることになる。
【００１８】
以降、マスクデータ数が最小である一致エントリデータ即ち有効データ長が最長である一致エントリデータを、ロンゲストマッチ（longest match）のエントリデータと呼ぶ。
【００１９】
本発明においては、ロンゲストマッチ（longest match）のエントリデータを検出するために、各ターナリセル１０に広報機能を備える。この広報機能は、自らのターナリセル１０の属するエントリデータが一致データであり、しかも自らのセルの内容が有効データであるときに、同一のビット位置にある他のターナリセル１０に対して、自らが有効データであることを広報する。このようにして有効データの存在が広報されると、同一のビット位置にある他のターナリセル１０は、自らのセルの内容がマスクデータである場合には、自らのターナリセル１０の属するエントリデータが一致データであるがロンゲストマッチではないことが判明するので、データ一致を示すマッチラインＭＬをＬＯＷに引き下げる。
【００２０】
このように本発明においては、あるセルの内容がマスクデータであり、同一ビット位置の他のセルにエントリデータが一致する有効データが存在する場合には、自らの属するエントリデータが最優先データでないことを判断して、このエントリデータを最優先データの候補からおろす。これによって、最終的に残ったエントリデータを、最優先データとして検出することが出来る。
【００２１】
図３は、本発明による連想記憶装置のセルの構成を示すブロック図である。
【００２２】
本発明によるＣＡＭセル２５は、ターナリセル１０、有効データ検出回路２６、及びロンゲストマッチ検出回路２７を含む。ここで有効データ検出回路２６が、上記の広報機能を備える回路である。
【００２３】
ターナリセル１０は、例えば図１に示すような構成であり、１、０、及びｘ（マスク或いはマスクプレフィックス）の３値からなるターナリデータを格納する。データ格納は、ビット線ＢＬ及び／ＢＬ（実際には図１に示されるようにＢＬ（１）及び／ＢＬ（１）とＢＬ（２）及び／ＢＬ（２））にデータを供給して、ワード線ＷＬを活性化することにより行われる。またエントリキーは、サーチバスＳＢ及び／ＳＢから供給される。
【００２４】
有効データ検出回路２６は、ターナリセル１０の内容の有効／無効を示す信号をターナリセル１０から受け取ると共に、マッチラインＭＬ上に現れている信号を入力として受け取る。同一ワード線上のＣＡＭセル即ちエントリデータを構成するＣＡＭセルが全て一致状態の時に、有効データ検出回路２６がマッチラインＭＬから受け取る信号はＨＩＧＨである。マッチラインＭＬからＨＩＧＨ信号を受け取り、かつターナリセル１０の内容が有効データであると、有効データ検出回路２６は、プライオリティーバスＰＢに自らのセルが有効データであることを通知する信号を送出する。例えばこれを通知するために、プライオリティーバスＰＢのレベルをＬＯＷにする。
【００２５】
ロンゲストマッチ検出回路２７は、ターナリセル１０の内容の有効／無効を示す信号をターナリセル１０から受け取ると共に、プライオリティーバスＰＢ上に現れている信号を入力として受け取る。ターナリセル１０の内容が無効データ（マスクデータ）である場合、プライオリティーバスＰＢ上に有効データの存在を通知する信号がのっていれば、ロンゲストマッチ検出回路２７はマッチラインＭＬをＬＯＷにする。ターナリセル１０の内容が無効データ（マスクデータ）であっても、プライオリティーバスＰＢ上に有効データの存在を通知する信号がのっていなければ、ロンゲストマッチ検出回路２７はマッチラインＭＬに対して何ら操作をしない。マッチラインＭＬが最初からＬＯＷであれば、ロンゲストマッチ検出回路２７の動作は無関係である。またターナリセル１０の内容が有効データであれば、ロンゲストマッチ検出回路２７はマッチラインＭＬに対して何ら操作をしない。
【００２６】
このように有効データ検出回路２６が広報機能を備え、自らのターナリセル１０の属するエントリデータが一致データであり、しかも自らのセルの内容が有効データであるときに、同一のビット位置にある他のＣＡＭセル２５に対して、自らが有効データであることをプライオリティーバスＰＢを介して広報する。プライオリティーバスＰＢ上に有効データの存在が広報されると、ロンゲストマッチ検出回路２７は、自らのセルの内容がマスクデータである場合に、自らのＣＡＭセル２５の属するエントリデータがロンゲストマッチではないことが判明するので、データ一致を示すマッチラインＭＬをＬＯＷに引き下げる。
【００２７】
このようにして本発明においては、図３のＣＡＭセル２５を用いることにより、あるセルの内容がマスクデータであり、同一ビット位置の他のセルに有効データが存在する場合には、自らの属するエントリデータが最優先データでないことを判断して、このエントリデータを最優先データの候補からおろす。これによって、最終的に残ったエントリデータを、最優先データとして検出することが出来る。
【００２８】
図４は、本発明による連想記憶装置の全体構成を示すブロック図である。
【００２９】
図４の連想記憶装置３０は、ＣＡＭセル配列３１、サーチバスドライバ３２、マッチラインセンスアンプ３３、プライオリティーエンコーダ３４、アドレスデコーダ３５、ワードラインドライバ３６、及びセンスアンプ＆ライトアンプ３７を含む。
【００３０】
ＣＡＭセル配列３１には、図３に示されるＣＡＭセル２５が縦横に配置され、サーチバスドライバ３２からのサーチバスＳＢ及び／ＳＢと、ワードラインドライバ３６からのワード線ＷＬと、センスアンプ＆ライトアンプ３７からのビット線ＢＬ及び／ＢＬとが、各ＣＡＭセル２５に接続される。また同一のワード線ＷＬに接続される複数のＣＡＭセル２５は、同一のマッチラインＭＬを共有し、マッチラインＭＬはマッチラインセンスアンプ３３へと供給される。またエントリデータの同一のビット位置に対応する複数のＣＡＭセル２５は、プライオリティーバスＰＢを共有する。図３を参照して説明したように、このプライオリティーバスＰＢを介して、一致エントリデータの有効データの存在が広報される。
【００３１】
サーチバスドライバ３２は、外部から入力されるエントリキーに応じて、サーチバスＳＢを駆動する。アドレスデコーダ３５は、外部から入力される書き込みアドレスをデコードして、デコード結果をワードラインドライバ３６に供給する。ワードラインドライバ３６は、デコード結果に応じて、入力アドレスに対応するワード線ＷＬを選択活性化する。センスアンプ＆ライトアンプ３７は、外部から入力される書き込みデータを増幅してＣＡＭセル配列３１に供給すると共に、ＣＡＭセル配列３１から読み出されるデータを増幅して装置外部に出力する。マッチラインセンスアンプ３３は、マッチラインＭＬの信号を増幅して、プライオリティーエンコーダ３４に供給する。プライオリティーエンコーダ３４は、ロンゲストマッチのマッチラインＭＬに対応するアドレスをエンコードして、最優先マッチデータのアドレスとして装置外部に出力する。
【００３２】
なおプライオリティーエンコーダ３４は、仮にエントリデータ一致を示すマッチラインＭＬが複数ある場合、例えば最小アドレスに対応するマッチラインＭＬのアドレスを、最優先マッチデータのアドレスとして装置外部に出力するように構成される。
【００３３】
ここで本発明の原理によれば、前記広報機能によって、最優先でない（ロンゲストマッチでない）エントリデータは、最優先データの候補からおろされる。従って、基本的には、マッチラインＭＬは一本だけがロンゲストマッチを示すはずである。しかしながら、例えば、通常とは異なった使用方法として、エントリキーが“001011xx”であり、以下のような複数の一致エントリデータが存在するとする。
【００３４】
“0010110x”  （第１のエントリデータ）
“0010111x”  （第２のエントリデータ）
“00101xxx”  （第３のエントリデータ）
“0010xxxx”  （第４のエントリデータ）
このとき第１のエントリデータと第２のエントリデータとの双方が、ロンゲストマッチとして検出されてしまうことになる。従って、このような通常とは異なった使用をする場合に備えて、プライオリティーエンコーダ３４には、エントリデータ一致を示すマッチラインＭＬが複数ある場合に備えて、それに対応できる構成を備えておくことが望ましい。
【００３５】
図５は、本発明によるＣＡＭセル２５の構成を示す回路図である。
【００３６】
図５のＣＡＭセル２５は、図４にも示されるように、ターナリセル１０、有効データ検出回路２６、及びロンゲストマッチ検出回路２７を含む。
【００３７】
ターナリセル１０は、ＮＭＯＳトランジスタ１１乃至１８とインバータ１９乃至２２とを含む。インバータ１９及び２０で１ビットを格納するラッチを形成し、インバータ２１及び２２で１ビットを格納するラッチを形成する。ターナリセル１０が１を格納する場合には、ノードＮ１が０でノードＮ２が１になるようにデータが格納される。ターナリセル１０が０を格納する場合には、ノードＮ１が１でノードＮ２が０になるようにデータが格納される。またターナリセル１０がマスクデータｘを格納する場合には、ノードＮ１及びノードＮ２が双方とも０になるようにデータが格納される。なおデータ格納は、ビット線ＢＬ（１）及び／ＢＬ（１）とビット線ＢＬ（２）及び／ＢＬ（２）にデータを供給して、ワード線ＷＬを活性化することにより行われる。このターナリセル１０の動作は、図１を参照して詳細に説明したとおりである。
【００３８】
有効データ検出回路２６は、ＮＭＯＳトランジスタ４１乃至４４を含む。ＮＭＯＳトランジスタ４１のゲートには、制御信号線ＰＳの信号が供給される。ＮＭＯＳトランジスタ４２のゲートには、マッチラインＭＬの信号が供給される。ＮＭＯＳトランジスタ４３のゲートには、ターナリセル１０のノードＮ１の信号が供給され、ＮＭＯＳトランジスタ４４のゲートには、ターナリセル１０のノードＮ２の信号が供給される。有効データ検出回路２６は、当該エントリデータが一致でマッチラインＭＬがＨＩＧＨである状態で、かつターナリセル１０の内容が有効データである場合に、プライオリティーバスＰＢをＬＯＷに引き下げる。これによって、同一のビット位置にある他のＣＡＭセル２５に、自らのセルにある有効データの存在を広報する。
【００３９】
初期状態において、マッチラインＭＬを、ハイレベルにプリチャージするか、或いはプルアップ状態にしてハイレベルに保持する。制御信号線ＰＳは、初期状態においてＬＯＷレベルに固定しておく。これは、サーチバスＳＢ及び／ＳＢにエントリキーが伝播される前の状態で、回路が誤動作することを防ぐためである。即ち、サーチバスＳＢ及び／ＳＢにエントリキーが伝播される前は、セルの内容に対する一致／不一致の判定がまだ実行されていない状態であり、この状態では、マッチラインＭＬはセルの内容に関わらずＨＩＧＨである。この時、有効データ検出回路２６は、当該データが不一致であってもセル内容が有効データであれば、誤ってプライオリティーバスＰＢをＬＯＷに引き下げてしまうことになる。これを防ぐために、制御信号線ＰＳは、初期状態においてＬＯＷレベルに固定しておいて、その後サーチバスＳＢ及び／ＳＢが駆動された後に、ＨＩＧＨレベルに設定される。
【００４０】
有効データ検出回路２６において、当該エントリデータが一致でマッチラインＭＬがＨＩＧＨであると、ＮＭＯＳトランジスタ４２が導通する。またターナリセル１０の内容が有効データであると、ＮＭＯＳトランジスタ４３或いは４４が導通する。また制御信号線ＰＳは上述のようにＨＩＧＨとなっているので、ＮＭＯＳトランジスタ４１も導通状態である。従って有効データ検出回路２６は、当該エントリデータが一致でマッチラインＭＬがＨＩＧＨである状態で、かつターナリセル１０の内容が有効データである場合に、プライオリティーバスＰＢをＬＯＷに引き下げる。
【００４１】
ロンゲストマッチ検出回路２７は、ＮＭＯＳトランジスタ４５乃至４８、及びインバータ４９を含む。ＮＭＯＳトランジスタ４５のゲートには、プライオリティーバスＰＢの信号の反転信号がインバータ４９を介して入力される。ＮＭＯＳトランジスタ４６のゲートには、制御信号線ＰＳの信号が供給される。ＮＭＯＳトランジスタ４７のゲートには、ターナリセル１０のノードＮ１の反転信号が供給され、ＮＭＯＳトランジスタ４４のゲートには、ターナリセル１０のノードＮ２の反転信号が供給される。
【００４２】
プライオリティーバスＰＢがＬＯＷになり、有効データの存在が広報されると、ＮＭＯＳトランジスタ４５が導通する。またターナリセル１０の内容が無効データ（マスクデータｘ）である場合には、ノードＮ１及びＮ２は双方ともＬＯＷレベルであり、この反転信号をゲートに供給されるＮＭＯＳトランジスタ４７及び４８は双方とも導通する。また制御信号線ＰＳは上述のようにＨＩＧＨとなっているので、ＮＭＯＳトランジスタ４６も導通状態である。従って、有効データの存在が広報されてプライオリティーバスＰＢがＬＯＷである状態で、ターナリセル１０の内容が無効データである場合には、ＮＭＯＳトランジスタ４５乃至４８が全て導通されて、マッチラインＭＬをＬＯＷに引き下げる。
【００４３】
このように有効データ検出回路２６が広報機能を備え、自らのターナリセル１０の属するエントリデータが一致データであり、しかも自らのセルの内容が有効データであるときに、同一のビット位置にある他のＣＡＭセル２５に対して、自らが有効データであることを、プライオリティーバスＰＢをＬＯＷにすることで広報する。プライオリティーバスＰＢ上に有効データの存在が広報されると、ロンゲストマッチ検出回路２７は、自らのセルの内容がマスクデータである場合に、自らのＣＡＭセル２５の属するエントリデータがロンゲストマッチではないことが判明するので、データ一致を示すマッチラインＭＬをＬＯＷに引き下げる。
【００４４】
図６は、エントリデータが一致している状態で自らのセルの内容が有効データの場合において各信号の変化を示すタイムチャートである。
【００４５】
図６（ａ）はサーチバスＳＢ及び／ＳＢの信号、（ｂ）はマッチラインＭＬの信号、（ｃ）は制御信号線ＰＳの信号、（ｄ）はプライオリティーバスＰＢの信号、（ｄ）はマッチラインＭＬ及びプライオリティーバスＰＢをプリチャージする信号を示す。図６に示されるように、サーチバスＳＢ及び／ＳＢが駆動された後に、制御信号線ＰＳがＨＩＧＨに設定される。エントリデータが一致している状態で自らのセルの内容が有効データの場合においては、有効データの信号（図示せず）と、制御信号線ＰＳのＨＩＧＨ信号と、マッチラインＭＬのＨＩＧＨ信号とによって、プライオリティーバスＰＢの信号がＬＯＷに引き下げられる。この場合、自らのセルの内容が有効データであるので、プライオリティーバスＰＢの信号がＬＯＷになっても、マッチラインＭＬの信号レベルはＨＩＧＨのままである。サーチバスＳＢ及び／ＳＢの駆動が終了すると、プライオリティーバスＰＢ及びマッチラインＭＬはＨＩＧＨにプリチャージされる。
【００４６】
図７は、エントリデータが一致している状態で自らのセルの内容が無効データであり、同一ビット位置の他のセルに有効データが存在する場合において、各信号の変化を示すタイムチャートである。
【００４７】
図７に示されるように、サーチバスＳＢ及び／ＳＢが駆動された後に、制御信号線ＰＳがＨＩＧＨに設定される。エントリデータが一致している状態で自らのセルの内容が無効データの場合においては、自らのＣＡＭセル２５は、プライオリティーバスＰＢをＬＯＷに引き下げることはしない。しかし図７の例では、同一ビット位置にある他のＣＡＭセル２５に有効データが存在するので、プライオリティーバスＰＢの信号がＬＯＷに引き下げられる。この場合、図７に示される自らのセルの内容は無効データであるので、プライオリティーバスＰＢの信号がＬＯＷになると、これに応じて、マッチラインＭＬの信号レベルはＬＯＷに引き下げられる。サーチバスＳＢ及び／ＳＢの駆動が終了すると、プライオリティーバスＰＢ及びマッチラインＭＬはＨＩＧＨにプリチャージされる。
【００４８】
図８は、エントリデータが一致している状態で自らのセルの内容が無効データであり、同一ビット位置の他のセルに有効データが存在しない場合において、各信号の変化を示すタイムチャートである。
【００４９】
図８に示されるように、サーチバスＳＢ及び／ＳＢが駆動された後に、制御信号線ＰＳがＨＩＧＨに設定される。エントリデータが一致している状態で自らのセルの内容が無効データの場合においては、自らのＣＡＭセル２５は、プライオリティーバスＰＢをＬＯＷに引き下げることはしない。また図８の例では、同一ビット位置にある他のＣＡＭセル２５にも有効データが存在しないので、プライオリティーバスＰＢの信号はＨＩＧＨのままである。従って、マッチラインＭＬの信号レベルは、ＨＩＧＨのままであり。サーチバスＳＢ及び／ＳＢの駆動が終了すると、プライオリティーバスＰＢ及びマッチラインＭＬはＨＩＧＨレベルにプリチャージされる。
【００５０】
図９は、本発明によるＣＡＭセル２５の別の実施例の構成を示す回路図である。
【００５１】
図９のＣＡＭセル５０は、ターナリセル５１、有効データ検出回路５２、及びロンゲストマッチ検出回路５３を含む。
【００５２】
ターナリセル５１は、ＮＭＯＳトランジスタ６１乃至６９とインバータ７０乃至７３とを含む。インバータ７０及び７１で１ビットを格納するラッチを形成し、インバータ７２及び７３で１ビットを格納するラッチを形成する。ターナリセル５１が１を格納する場合には、ノードＮ１が０でノードＮ２が１になるようにデータが格納される。ターナリセル５１が０を格納する場合には、ノードＮ１が１でノードＮ２が１になるようにデータが格納される。またターナリセル５１がマスクデータｘを格納する場合には、ノードＮ１はドントケアでノードＮ２が０になるようにデータが格納される。なおデータ格納は、ビット線ＢＬ（１）及び／ＢＬ（１）とビット線ＢＬ（２）及び／ＢＬ（２）にデータを供給して、ワード線ＷＬを活性化することにより行われる。
【００５３】
有効データ検出回路５２は、ＮＭＯＳトランジスタ８４乃至８６を含む。有効データ検出回路５２において、当該エントリデータが一致でマッチラインＭＬがＨＩＧＨであると、ＮＭＯＳトランジスタ８５が導通する。またターナリセル５１の内容が有効データであると、ノードＮ２がＨＩＧＨであるので、ＮＭＯＳトランジスタ８４が導通する。また制御信号線ＰＳはＨＩＧＨとなっているので、ＮＭＯＳトランジスタ８６も導通状態である。従って有効データ検出回路５２は、当該エントリデータが一致でマッチラインＭＬがＨＩＧＨである状態で、かつターナリセル５１の内容が有効データである場合に、プライオリティーバスＰＢをＬＯＷに引き下げる。
【００５４】
ロンゲストマッチ検出回路５３は、ＮＭＯＳトランジスタ８１乃至８３、及びインバータ８７を含む。プライオリティーバスＰＢがＬＯＷになり、有効データの存在が広報されると、ＮＭＯＳトランジスタ８３が導通する。またターナリセル５１の内容が無効データ（マスクデータｘ）である場合には、ノードＮ２はＬＯＷレベルであり、この反転信号をゲートに供給されるＮＭＯＳトランジスタ８１が導通する。また制御信号線ＰＳはＨＩＧＨとなっているので、ＮＭＯＳトランジスタ８２も導通状態である。従って、有効データの存在が広報されてプライオリティーバスＰＢがＬＯＷである状態で、ターナリセル５１の内容が無効データである場合には、ＮＭＯＳトランジスタ８１乃至８３が全て導通されて、マッチラインＭＬをＬＯＷに引き下げる。
【００５５】
このように有効データ検出回路５２が広報機能を備え、自らのターナリセル５１の属するエントリデータが一致データであり、しかも自らのセルの内容が有効データであるときに、同一のビット位置にある他のＣＡＭセル５０に対して、自らが有効データであることを、プライオリティーバスＰＢをＬＯＷにすることで広報する。プライオリティーバスＰＢ上に有効データの存在が広報されると、ロンゲストマッチ検出回路５３は、自らのセルの内容がマスクデータである場合に、自らのＣＡＭセル５０の属するエントリデータがロンゲストマッチではないことが判明するので、データ一致を示すマッチラインＭＬをＬＯＷに引き下げる。
【００５６】
図９のＣＡＭセル５０の構成においては、図５のＣＡＭセル２５の構成と比較して、有効データ検出回路５２及びロンゲストマッチ検出回路５３のＮＭＯＳトランジスタの数を減らすことが出来る。ＣＡＭセルは、図４に示されるようなＣＡＭセル配列３１において多数個が縦横に配置されるので、各ＣＡＭセルにおける回路素子の数が若干であっても減ることは、ＣＡＭセル配列３１の回路規模を減少するうえで大きな効果がある。
【００５７】
図１０は、制御信号線ＰＳの制御機構を示す構成図である。
【００５８】
上記説明においては、制御信号線ＰＳは、同一のワードにおいて一律にＨＩＧＨになるものとして説明された。即ち、同一ワード上の全てのＣＡＭセル２５（或いは５０）に対して、制御信号線ＰＳがＨＩＧＨとなり、各ＣＡＭセルにおいて有効データ検出回路とロンゲストマッチ検出回路が動作する。しかしながら有効データ検出回路とロンゲストマッチ検出回路の動作は、同一ビット位置のデータが全て有効データである場合には、特に実行する必要がない動作である。従って、同一ビット位置のデータが全て有効データであるビット位置においては、制御信号線ＰＳをＨＩＧＨとしないことで、消費電力の削減を図ることが出来る。
【００５９】
図１０においては、（ａ）に示されるセルマトリクスイメージのように、セル配列に格納されるエントリデータのうちで、最長のマスクデータの数（マスクプレフィックスの数）が５であるとする。このとき図１０（ｂ）に示されるように、制御信号線ＰＳを制御するＰＳコントロールレジスタ９１を設けておき、この最長マスクデータの数に対応して、ＰＳコントロールレジスタ９１の各ビットに０及び１のデータを格納する。この例では、最長マスクデータの数に等しい数である５つの１を、ＰＳコントロールレジスタ９１に連続して並べるように格納する。それ以外のビットには、０を格納しておく。
【００６０】
更に複数のＡＮＤ回路が、ＰＳコントロールレジスタ９１の各ビットに対して設けられる。例えばＡＮＤ回路９２は、ＰＳコントロールレジスタ９１の右から６番目のビットに対応し、ＡＮＤ回路９３は、ＰＳコントロールレジスタ９１の一番右のビットに対応する。これらのＡＮＤ回路は、ＰＳタイミング信号とＰＳコントロールレジスタ９１の各ビットとのＡＮＤをとることで、各ビット位置に対する制御信号線ＰＳの信号を生成する。これによって、マスクデータの長さが最長であるエントリデータのマスクデータの位置でのみ、有効データ検出回路及びロンゲストマッチ検出回路を駆動することが出来る。従って、図１０の構成を用いれば、無駄な電力消費を無くすことが可能となる。
【００６１】
図１１は、本発明による連想記憶装置の変形例におけるＣＡＭセル及びその周辺の構成を示す回路図である。図１１において、図５と同一の構成要素は同一の参照番号で参照し、その説明は省略する。
【００６２】
図１１のＣＡＭセル２５Ａは、ターナリセル１０、有効データ検出回路２６、及びロンゲストマッチ検出回路２７Ａを含む。ここでターナリセル１０及び有効データ検出回路２６は、図５の構成と同一である。ロンゲストマッチ検出回路２７Ａにおいては、図５のロンゲストマッチ検出回路２７からインバータ４９及びＮＭＯＳトランジスタ４６が削除されている。
【００６３】
有効データ検出回路２６は、図５の構成と同様に、プライオリティーバスＰＢに接続される。これによって、当該エントリデータが一致でマッチラインＭＬがＨＩＧＨである状態で、かつターナリセル１０の内容が有効データである場合に、プライオリティーバスＰＢをＬＯＷに引き下げる。
【００６４】
プライオリティーバスＰＢは、ＰＢリピータ１０１に接続される。ＰＢリピータ１０１は、インバータ１０２及びＮＯＲ回路１０３を含む。インバータ１０２は制御信号線ＰＳの信号を受け取り、出力をＮＯＲ回路１０３に供給する。従って制御信号線ＰＳの信号がＨＩＧＨのときに、ＮＯＲ回路１０３は、プライオリティーバスＰＢ上の信号に対する反転回路として動作する。制御信号線ＰＳの信号がＬＯＷのときは、ＮＯＲ回路１０３の出力はＬＯＷに固定である。
【００６５】
ここでＮＯＲ回路１０３の出力は、リピートプライオリティーバスＲＰＢとして、同一ビット位置にある各ＣＡＭセル２５Ａに供給される。
【００６６】
プライオリティーバスＰＢがＬＯＷに引き下げられると、制御信号線ＰＳの信号がＨＩＧＨである場合に、リピートプライオリティーバスＲＰＢがＨＩＧＨとなる。このリピートプライオリティーバスＲＰＢのＨＩＧＨ信号が、ロンゲストマッチ検出回路２７ＡのＮＭＯＳトランジスタ４５のゲートに入力されて、当該セルのデータが無効である場合には、マッチラインＭＬのレベルがＬＯＷに引き下げられる。
【００６７】
このように図１１の構成では、図５におけるロンゲストマッチ検出回路２７のインバータ４９の役割とＮＡＮＤ回路４６の役割を、ＰＢリピータ１０１によって代用させる。これによって、図５の構成と同一の動作を、各ＣＡＭセルあたりの回路素子数を少なくして実現することが出来る。
【００６８】
図１２は、ＰＢリピータを図９の構成に適用した場合の構成を示す回路図である。図１２において、図９と同一の構成要素は同一の参照番号で参照し、その説明は省略する。
【００６９】
図１１のＣＡＭセル５０Ａは、ターナリセル５１、有効データ検出回路５２、及びロンゲストマッチ検出回路５３Ａを含む。ここでターナリセル５１及び有効データ検出回路５２は、図９の構成と同一である。ロンゲストマッチ検出回路５３Ａにおいては、図９のロンゲストマッチ検出回路５３からインバータ８７及びＮＭＯＳトランジスタ８２が削除されている。
【００７０】
プライオリティーバスＰＢは、ＰＢリピータ１０１に接続される。ＰＢリピータ１０１の出力は、リピートプライオリティーバスＲＰＢとして、同一ビット位置にある各ＣＡＭセル２５Ａに供給される。
【００７１】
プライオリティーバスＰＢがＬＯＷに引き下げられると、制御信号線ＰＳの信号がＨＩＧＨである場合に、リピートプライオリティーバスＲＰＢがＨＩＧＨとなる。このリピートプライオリティーバスＲＰＢのＨＩＧＨ信号が、ロンゲストマッチ検出回路５３ＡのＮＭＯＳトランジスタ８３のゲートに入力されて、当該セルのデータが無効である場合には、マッチラインＭＬのレベルがＬＯＷに引き下げられる。
【００７２】
このように図１２の構成では、図９におけるロンゲストマッチ検出回路５３のインバータ８７の役割とＮＡＮＤ回路８２の役割を、ＰＢリピータ１０１によって代用させる。これによって、図９の構成と同一の動作を、各ＣＡＭセルあたりの回路素子数を少なくして実現することが出来る。
【００７３】
図１３は、本発明による連想記憶装置の更なる変形例におけるＣＡＭセル及びその周辺の構成を示す回路図である。図１３において、図１１と同一の構成要素は同一の参照番号で参照し、その説明は省略する。
【００７４】
図１３のＣＡＭセル２５Ｂは、ターナリセル１０、有効データ検出回路２６Ａ、及びロンゲストマッチ検出回路２７Ａを含む。ここでターナリセル１０及びロンゲストマッチ検出回路２７Ａは、図１１の構成と同一である。有効データ検出回路２６Ａにおいては、図１１の有効データ検出回路２６からＮＭＯＳトランジスタ４１が削除されている。
【００７５】
図１３の構成において、マッチラインＭＬは、有効データ検出回路２６Ａにもロンゲストマッチ検出回路２７Ａにも接続されない。マッチラインＭＬは、ＭＬセンスアンプ１２１に接続される。ＭＬセンスアンプ１２１はマッチラインＭＬの信号レベルを増幅し、増幅された出力が、クロック信号Φに同期してフリップフロップ１２２にラッチされる。ラッチされたデータはＲＭＬドライバ１２３に入力され、ＲＭＬドライバ１２３がリピートマッチラインＲＭＬを駆動する。これによってリピートマッチラインＲＭＬには、マッチラインＭＬの信号が、クロック信号Φの１クロック後に現れる。
【００７６】
有効データ検出回路２６Ａは、リピートマッチラインＲＭＬの信号を入力とすると共に、プライオリティーバスＰＢに接続される。これによって、当該エントリデータが一致でリピートマッチラインＲＭＬがＨＩＧＨである状態で、かつターナリセル１０の内容が有効データである場合に、プライオリティーバスＰＢをＬＯＷに引き下げる。
【００７７】
プライオリティーバスＰＢは、ＰＢセンスアンプ１１１に接続される。ＰＢセンスアンプ１１１はプライオリティーバスＰＢの信号レベルを増幅し、増幅された出力が、クロック信号Φに同期してフリップフロップ１１２にラッチされる。ラッチされたデータは、インバータ１１３を介してＲＰＢドライバ１１４に入力され、ＲＰＢドライバ１１４がリピートプライオリティーバスＲＰＢを駆動する。これによってリピートプライオリティーバスＲＰＢには、プライオリティーバスＰＢの反転信号が、クロック信号Φの１クロック後に現れる。
【００７８】
リピートプライオリティーバスＲＰＢは、同一ビット位置にある各ＣＡＭセル２５Ｂに供給される。
【００７９】
図１４は、図１３の構成においてサーチバスＳＢ及び／ＳＢの活性化から、リピートプライオリティーバスＲＰＢの変化までのタイミングを示す図である。図１４において、（ａ）はクロック信号（図１３のΦ）、（ｂ）はサーチバスＳＢ及び／ＳＢ、（ｃ）はマッチラインＭＬ、（ｄ）はＭＬセンスアンプ１２１の出力、（ｅ）はフリップフロップ１２２の出力、（ｆ）はリピートマッチラインＲＭＬ、（ｇ）はプライオリティーバスＰＢ、（ｈ）はＰＢセンスアンプ１１１の出力、（ｉ）はフリップフロップ１１２の出力、（ｊ）はリピートプライオリティーバスＲＰＢを示す。
【００８０】
図１４に示されるように、一致判定結果がマッチラインＭＬに現れてからクロック信号Φの１クロック後に、プライオリティーバスＰＢがＬＯＷに引き下げられると、クロック信号Φの１クロック後に、リピートプライオリティーバスＲＰＢがＨＩＧＨとなる。
【００８１】
このリピートプライオリティーバスＲＰＢのＨＩＧＨ信号が、ロンゲストマッチ検出回路２７ＡのＮＭＯＳトランジスタ４５のゲートに入力されて、当該セルのデータが無効である場合には、ロンゲストマッチラインＬＭＬのレベルがＬＯＷに引き下げられる。
【００８２】
なおリピートマッチラインＲＭＬは、フリップフロップ１２４に入力され、クロック信号Φに同期してラッチされる。ラッチされたデータはＬＭＬドライバ１２５に入力され、これに応じてＬＭＬドライバ１２５がロンゲストマッチラインＬＭＬを駆動する。これによってロンゲストマッチラインＬＭＬには、リピートマッチラインＲＭＬの信号が、クロック信号Φの１クロック後に現れる。
【００８３】
このようにマッチラインＭＬの信号は、クロック信号Φの１クロック後にリピートマッチラインＲＭＬに伝播し、更にリピートマッチラインＲＭＬの信号は、クロック信号Φの１クロック後にロンゲストマッチラインＬＭＬに伝播する。有効データ検出回路２６Ａは、リピートマッチラインＲＭＬの信号に基づいて、エントリデータが一致で当該データが有効である場合に、有効データの存在をリピートプライオリティーバスＲＰＢに広報する。またロンゲストマッチ検出回路２７Ａは、有効データの存在がリピートプライオリティーバスＲＰＢに広報されかつ当該セルのデータが無効である場合に、ロンゲストマッチラインＬＭＬをＬＯＷに引き下げる。
【００８４】
このようにマッチラインＭＬ、リピートマッチラインＲＭＬ、及びロンゲストマッチラインＬＭＬの信号を、クロック信号Φのサイクル毎に分離する。そして一致判定はマッチラインＭＬの信号に基づいて、また有効データの広報はリピートマッチラインＲＭＬの信号に基づいて実行することで、ロンゲストマッチの判定結果をロンゲストマッチラインＬＭＬに送出する。これによって一致判定、有効データの広報、及びロンゲストマッチの判定を各クロックサイクルで実行することが可能になる。
【００８５】
このように各動作を各クロックサイクルで実行する場合には、一般に、各動作のパイプライン動作を実現することが出来る。即ち本発明の場合には、第１のサイクルで第１のエントリキーに対する一致判定を行い、第２のサイクルで第２のエントリキーに対する一致判定と第１のエントリキーに対する有効データの広報とを同時に実行し、第３のサイクルで、第３のエントリキーに対する一致判定と、第２のエントリキーに対する有効データの広報と、第１のエントリキーに対するロンゲストマッチの判定とを同時に実行する。以下同様に、一致判定、有効データの広報、及びロンゲストマッチの判定を、各サイクルで同時に実行することが可能になる。このパイプライン動作によって、一連のロンゲストマッチ判定に要する処理時間を、大幅に削減することが可能になる。
【００８６】
図１５は、パイプライン動作を実現する機構を図１２の構成に適用した場合の回路図である。図１５において、図１２と同一の構成要素は同一の参照番号で参照し、その説明は省略する。
【００８７】
図１５のＣＡＭセル５０Ｂは、ターナリセル５１、有効データ検出回路５２Ａ、及びロンゲストマッチ検出回路５３Ａを含む。ここでターナリセル５１及びロンゲストマッチ検出回路５３Ａは、図１２の構成と同一である。有効データ検出回路５２Ａにおいては、図１２の有効データ検出回路５２からＮＭＯＳトランジスタ８６が削除されている。
【００８８】
図１５の構成の動作は、図１３の構成の動作と実質的に同一であるので、その説明は省略する。図１５の構成においても、図１３の構成と同様に、パイプライン動作を実現することが出来る。
【００８９】
図１６は、図１３のようなパイプライン動作可能な構成のＣＡＭセル配列全体の構成を示す図である。
【００９０】
ＣＡＭセル２５Ｂ（或いは５０Ｂ）が、縦横に配置されてＣＡＭセル配列１３０を構成する。サーチバスＳＢ及び／ＳＢの延長方向の各列に対して、ＰＢセンスアンプ１１１、フリップフロップ１１２、インバータ１１３、ＲＰＢドライバ１１４のセットが設けられ、プライオリティーバスＰＢに基づいてリピートプライオリティーバスＲＰＢを駆動する。またワード線ＷＬの延長方向の各行に対して、ＭＬセンスアンプ１２１、フリップフロップ１２２、ＲＭＬドライバ１２３、フリップフロップ１２４、及びＬＭＬドライバ１２５のセットが設けられ、マッチラインＭＬの信号に基づいてリピートマッチラインＲＭＬ及びロンゲストマッチラインＬＭＬを駆動する。また各行に対して、ＬＭＬセンスアンプ１２６が設けられ、ロンゲストマッチラインＬＭＬの信号を増幅し、例えば図４のプライオリティーエンコーダ３４に供給する。
【００９１】
このようにＰＢセンスアンプ１１１、フリップフロップ１１２、インバータ１１３、ＲＰＢドライバ１１４のセットは各列に対して設ければよく、またＭＬセンスアンプ１２１、フリップフロップ１２２、ＲＭＬドライバ１２３、フリップフロップ１２４、及びＬＭＬドライバ１２５のセットは各行に対して設ければよいので、ＣＡＭセル配列１３０の回路面積が増大することはなく、また上記各セットの個数もセルの個数よりは遥かに小さいので、回路全体の規模もそれ程は大きくならない。
【００９２】
以上、本発明を実施例に基づいて説明したが、本発明は上記実施例に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【発明の効果】
本発明においては、あるセルの内容が無効データであり、同一ビット位置の他のセルにエントリデータが一致する有効データが存在する場合には、自らの属するエントリデータが最優先データでないことを判断して、このエントリデータを最優先データの候補からおろす。これによって、最終的に残ったエントリデータを、最優先データとして検出することが出来る。
【００９３】
従って、アドレスと優先順位とを関係付けることなく最優先のエントリデータを検出可能な構成となり、アドレスと優先順位とを関係付けていた従来の構成と比較して、メモリシステムの実行性能を著しく向上させることが出来る。
【図面の簡単な説明】
【図１】ＣＡＭにおいて一般的に用いられるターナリセルを示す回路図である。
【図２】ターナリセルが縦横に配置されたセルマトリックスを示す図である。
【図３】本発明による連想記憶装置のセルの構成を示すブロック図である。
【図４】本発明による連想記憶装置の全体構成を示すブロック図である。
【図５】本発明によるＣＡＭセルの構成を示す回路図である。
【図６】エントリデータが一致している状態で自らのセルの内容が有効データの場合において各信号の変化を示すタイムチャートである。
【図７】エントリデータが一致している状態で自らのセルの内容が無効データであり、同一ビット位置の他のセルに有効データが存在する場合において、各信号の変化を示すタイムチャートである。
【図８】エントリデータが一致している状態で自らのセルの内容が無効データであり、同一ビット位置の他のセルに有効データが存在しない場合において、各信号の変化を示すタイムチャートである。
【図９】本発明によるＣＡＭセルの別の実施例の構成を示す回路図である。
【図１０】制御信号線の制御機構を示す構成図である。
【図１１】本発明による連想記憶装置の変形例におけるＣＡＭセル及びその周辺の構成を示す回路図である。
【図１２】ＰＢリピータを図９の構成に適用した場合の構成を示す回路図である。
【図１３】本発明による連想記憶装置の更なる変形例におけるＣＡＭセル及びその周辺の構成を示す回路図である。
【図１４】図１３の構成においてサーチバスＳＢ及び／ＳＢの活性化から、リピートプライオリティーバスＲＰＢの変化までのタイミングを示す図である。
【図１５】パイプライン動作を実現する機構を図１２の構成に適用した場合の回路図である。
【図１６】図１３のようなパイプライン動作可能な構成のＣＡＭセル配列全体の構成を示す図である。
【符号の説明】
１０  ターナリセル
２５  ＣＡＭセル
２６  有効データ検出回路
２７  ロンゲストマッチ検出回路
３１  ＣＡＭセル配列
３２  サーチバスドライバ
３３  マッチラインセンスアンプ
３４  プライオリティーエンコーダ
３５  アドレスデコーダ
３６  ワードラインドライバ
３７  センスアンプ＆ライトアンプ
【図１】
0005072145.tif 000002
【図２】
0005072145.tif 000003
【図３】
0005072145.tif 000004
【図４】
0005072145.tif 000005
【図５】
0005072145.tif 000006
【図６】
0005072145.tif 000007
【図７】
0005072145.tif 000008
【図８】
0005072145.tif 000009
【図９】
0005072145.tif 000010
【図１０】
0005072145.tif 000011
【図１１】
0005072145.tif 000012
【図１２】
0005072145.tif 000013
【図１３】
0005072145.tif 000014
【図１４】
0005072145.tif 000015
【図１５】
0005072145.tif 000016
【図１６】
0005072145.tif 000017