(57)【要約】【課題】小規模かつ簡単な回路構成で、エンプティ状態の最もプライオリティの高いワードのアドレスを求めることができる連想メモリを提供する。【解決手段】本発明の連想メモリは、検索の対象となるデータビットを保持するＣＡＭセルと、データビットの有効無効を表すエンプティビットを保持し、かつ検索の対象となるＣＡＭセルとを含むワードを複数備える。それぞれのワードは、データビットとこのデータビットを検索しようとするデータとの検索結果と、エンプティビットとこのエンプティビットを検索しようとするデータとの検索結果とが共通の一致線上に出力される。【選択図】図１
2004253023.tif 000002
【特許請求の範囲】
【請求項１】
データビットを保持するＣＡＭセルと、前記データビットの有効無効を表すエンプティビットを保持するＣＡＭセルとを含むワードを複数備え、
それぞれの前記ワードは、前記データビットとこのデータビットを検索しようとするデータとの検索結果と、前記エンプティビットとこのエンプティビットを検索しようとするデータとの検索結果とが共通の一致線上に出力されることを特徴とする連想メモリ。
【請求項２】
前記データビットにデータが書き込まれる時に、前記エンプティビットを、前記データビットが有効であることを表す状態に設定し、前記データビットが消去される時に、前記エンプティビットを、前記データビットが無効であることを表す状態に設定する手段を備える請求項１に記載の連想メモリ。
【請求項３】
全ての前記ワードのエンプティビットを一括で同一値に設定する手段を備える請求項１または２に記載の連想メモリ。
【請求項４】
複数のワードを連結して１つのエントリを構成する機能を持つ連想メモリであって、
それぞれの前記ワードは、データビットを保持するＣＡＭセルと、前記データビットの有効無効を表すエンプティビットを保持するＣＡＭセルとを含み、
それぞれの前記ワードは、前記データビットとこのデータビットを検索しようとするデータとの検索結果と、前記エンプティビットとこのエンプティビットを検索しようとするデータとの検索結果とが共通の一致線上に出力されることを特徴とする連想メモリ。
【請求項５】
複数のワードを連結して１つのエントリを構成した場合に、前記エントリを構成するそれぞれのワードのエンプティビットがそれぞれのワードの有効無効を表し、前記エントリを構成する全てのワードのエンプティビットの状態に基づいて当該エントリの有効無効を決定する手段を備える請求項４に記載の連想メモリ。
【請求項６】
複数のワードを連結して１つのエントリを構成した場合に、前記エントリの代表となるエントリ代表ワードが設定され、このエントリ代表ワードのエンプティビットが当該エントリの有効無効を表すことを特徴とする請求項４に記載の連想メモリ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、メモリワードに保持されているデータビットが、検索対象となる有効なものなのか、検索対象とはならない無効なものなのかを表すエンプティビットを備える連想メモリに関するものである。
【０００２】
【従来の技術】
連想メモリ（Ａｓｓｏｃｉａｔｉｖｅ  Ｍｅｍｏｒｙ）は、内容アドレス式メモリ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）とも呼ばれているように、あらかじめ連想メモリ（以下、ＣＡＭという）のそれぞれのメモリワード（以下、単にワードという）にデータを保持しておき、検索しようとするデータ（以下、検索データという）と一致するデータが保持されているワードのアドレスを出力することが可能なものである。
【０００３】
特許文献１〜３に一例を示すように、ＣＡＭにおいて、検索の対象となるデータの他に、このデータが検索の対象となる有効なものなのか、あるいは検索の対象とはならない無効なものなのかを表すエンプティビット（または、バリッドビット）を設けることが知られている。また、このエンプティビットを利用して、エンプティ状態（空き状態）のワードを特定する手段を備えている。
【０００４】
これにより、あらかじめ設定されているアドレスのプライオリティに従って、エンプティ状態のワードの中で最もプライオリティの高いアドレス（Ｈｉｇｈｅｓｔ  ｐｒｉｏｒｉｔｙ  Ｅｍｐｔｙ  Ａｄｄｒｅｓｓ）（以下、ＨＥＡという）を検出することができる。例えば、アドレスが‘０’に近いほどワードのプライオリティが高く設定されている場合、アドレス‘０’に最も近いエンプティ状態のアドレス、すなわちＨＥＡを求めることができる。
【０００５】
前述の特許文献１の図３、特許文献２の図１、特許文献３の図８等には、検索結果とエンプティビットとの論理をとり、その論理演算結果を最終的な検索結果として出力する回路が示されている。
【０００６】
これらの回路では、例えば特許文献３の図７に示されているように、また、特許文献１，２においても明らかなように、エンプティビットとしてＳＲＡＭ等の通常のメモリセルが使用されている。そして、検索結果とエンプティビットとの論理をとって、その論理演算結果が最終的な検索結果として出力されている。また、この最終的な検索結果とは別にエンプティビットをエンコードしてＨＥＡが求められている。
【０００７】
また、特許文献２の図２には、データビットを保持するＣＡＭセルとバリッドビット（エンプティビット）を保持するバリッドセルとを一致線に並列に接続し、バリッドビットの状態に応じて一致線の状態を制御する回路が示されている。
【０００８】
しかし、この回路では、バリッドビットの“真”値をワード内の他のビットの“一致”に対応させ、バリッドビットの“偽”値をワード内の他のビットの“不一致”に対応させるとあり、バリッドビットに対して検索は行われることはなく、バリッドビットが“偽”であるワードについて、常に不一致を示すように一致線を固定するために用いられている。
【０００９】
このようなバリッドビットを用いて、最もプライオリティの高いエンプティワードのアドレスを出力することは可能ではあるが、バリッドビットの出力と一致線の出力のＡＮＤを取る場合と同様に検索用とは別のプライオリティエンコーダが必要になる。
【００１０】
この発明では、これらのバリッドビットの構成において、バリッドビットを用いたプリチャージのコントロールについて示されているのみであり、バリッドビットをＣＡＭセルで構成すること、検索時にバリッドビットを含んで検索すること等は示されていない。
【００１１】
従って、特許文献１，２の場合、ＨＥＡを求めるためには、例えば検索結果用のプライオリティエンコーダとは別にエンプティビット用のプライオリティエンコーダが必要になる。または、特許文献３のように、検索結果用のプライオリティエンコーダをエンプティビット用のプライオリティエンコーダとして時分割で使用するための切替手段等が必要になる。このため、回路が増大したり、複雑化するという問題があった。
【００１２】
【特許文献１】
特開平２−６４９９４号公報
【特許文献２】
特開２０００−２２８０９０号公報
【特許文献３】
特開２０００−２２２８８４号公報
【００１３】
【発明が解決しようとする課題】
本発明の目的は、前記従来技術に基づく問題点を解消し、小規模かつ簡単な回路構成で、エンプティ状態の最もプライオリティの高いワードのアドレスを求めることができる連想メモリを提供することにある。
【００１４】
【課題を解決するための手段】
上記目的を達成するために、本発明は、データビットを保持するＣＡＭセルと、前記データビットの有効無効を表すエンプティビットを保持するＣＡＭセルとを含むワードを複数備え、
それぞれの前記ワードは、前記データビットとこのデータビットを検索しようとするデータとの検索結果と、前記エンプティビットとこのエンプティビットを検索しようとするデータとの検索結果とが共通の一致線上に出力されることを特徴とする連想メモリを提供するものである。
【００１５】
ここで、前記データビットにデータが書き込まれる時に、前記エンプティビットを、前記データビットが有効であることを表す状態に設定し、前記データビットが消去される時に、前記エンプティビットを、前記データビットが無効であることを表す状態に設定する手段を備えるのが好ましい。
【００１６】
また、全ての前記ワードのエンプティビットを一括で同一値に設定する手段を備えるのが好ましい。
【００１７】
また、本発明は、複数のワードを連結して１つのエントリを構成する機能を持つ連想メモリであって、
それぞれの前記ワードは、データビットを保持するＣＡＭセルと、前記データビットの有効無効を表すエンプティビットを保持するＣＡＭセルとを含み、
それぞれの前記ワードは、前記データビットとこのデータビットを検索しようとするデータとの検索結果と、前記エンプティビットとこのエンプティビットを検索しようとするデータとの検索結果とが共通の一致線上に出力されることを特徴とする連想メモリを提供する。
【００１８】
ここで、複数のワードを連結して１つのエントリを構成した場合に、前記エントリを構成するそれぞれのワードのエンプティビットがそれぞれのワードの有効無効を表し、前記エントリを構成する全てのワードのエンプティビットの状態に基づいて当該エントリの有効無効を決定する手段を備えるのが好ましい。
【００１９】
また、複数のワードを連結して１つのエントリを構成した場合に、前記エントリの代表となるエントリ代表ワードが設定され、このエントリ代表ワードのエンプティビットが当該エントリの有効無効を表すのが好ましい。
【００２０】
【発明の実施の形態】
以下に、添付の図面に示す好適実施形態に基づいて、本発明の連想メモリを詳細に説明する。
【００２１】
図１（Ａ）は、本発明の連想メモリの一実施形態の構成概略図である。同図に示す連想メモリ１０は、外部からワードのアドレスデータ、各種コマンド、ＣＡＭセルに記憶するデータや検索キーデータを入力し、コマンドに基づいて入力されたデータを出力するＣＡＭ制御回路１２、アドレスデータに基づいてワード線（ＷＬ１〜ｎ−１）を選択するアドレスデコーダ１４、複数のワードの一致線を入力し、所定の優先順位に基づいて検索キーデータと一致したワードのアドレスを出力するプライオリティエンコーダ１６を有する。
【００２２】
また、連想メモリ１０は、複数のワードを有し、各１ワードは複数のＣＡＭセルを含んでいる。これら複数のＣＡＭセルのうち、図中左端の１ビットのＣＡＭセル１８は、このワードの有効無効を表すエンプティビットを保持するためのＣＡＭセルであり、残りのＣＡＭセル２０は外部から入力される検索データと一致するか否かの検索対象となるデータビットを保持するＣＡＭセルである。
【００２３】
ＣＡＭセル１８は、エンプティビットが記憶される記憶部２２と、比較部２６を有している。比較部２６には、エンプティビットの検索データを供給するための検索線Ｋとその反転検索線Ｋ￣が接続され、エンプティビットの検索データと記憶部２２に記憶するエンプティビットとの検索結果を一致線ＭＬに出力する。また、記憶部２２には、エンプティビットの書き込み／読み出しのためのデータ線Ｄとその反転データ線Ｄ￣が接続されている。
【００２４】
ＣＡＭセル２０は、データビット記憶部２４、比較部２８を有し、検索線Ｋとその反転検索線Ｋ￣、データ線Ｄとその反転データ線Ｄ￣が接続され、比較部２８の出力は一致線ＭＬに接続されている。
【００２５】
本図においては、エンプティビットを保持するＣＡＭセル１８とデータビットを保持するＣＡＭセル２０は同じ回路構成のものとしているが、異なる形式のＣＡＭセルであっても良い。例えば、ＣＡＭセル２０は３値ＣＡＭセルとし、ＣＡＭセル１８は２値ＣＡＭセルとするような構成が可能である。
【００２６】
本実施形態では、同図（Ｂ）に示すように、エンプティビットが‘１’の場合がエンプティ状態を表し、データビットが無効データであることを意味する。また、エンプティビットが‘０’の場合はエンプティではない状態を表し、データビットが有効データであることを意味する。なお、エンプティビットの‘１’および‘０’とエンプティ状態およびエンプティではない状態との対応は逆であってもよいし、エンプティビットの位置も１ワード中のどのビットでもよい。
【００２７】
図２の概念図に示すように、例えばアドレス‘１２３’のワードに対してデータＡがライトされると、そのエンプティビットが‘０’に設定される。これに対し、アドレス‘１２３’のワードに保持されているデータを消去するコマンドが与えられると、そのエンプティビットは‘１’に設定される。エンプティビットの設定は、エンプティビットの制御回路により、ワードへのデータのライト、消去コマンド等を検出して自動的に行われる。
【００２８】
また、エンプティビットの制御回路によって、全てのワードのエンプティビットを一括で同一値に設定することも可能である。例えば、図３の概念図に示すように、アドレス０，１，２，…，ｎ−１のワードのエンプティビットの状態が、それぞれ０，１，０，…，１である場合に、セット信号Ｓｅｔを与えることによって、メモリワードのエンプティビットを一括で同一値の‘１’、すなわちエンプティ状態（無効データ）に設定することができる。
【００２９】
この機能は、例えばイニシャライズ時に、全てのワードをエンプティ状態に設定したい場合等に用いられる。この機能を実現する具体的な回路構成は何ら限定されないが、エンプティビット用のＣＡＭセルのデータビット線だけをドライブして、全てのワード線を同時に活性化する方法や、１ワード毎に順番に活性化する方法等を例示することができる。
【００３０】
本実施形態のワードを用いたＣＡＭにおいて、データビットの検索を行う場合、エンプティビットに対する検索データとして‘０’が与えられ、データビットに対する検索データが与えられて検索が行われる。これにより、エンプティビットが‘０’のワード、すなわちエンプティではない状態のワードで、なおかつ検索データに一致するデータビットが保持されているワードで一致が検出される。
【００３１】
例えば、図４の概念図に示す例の場合、エンプティビットに対する検索データとして‘０’が、また、データビットに対する検索データとしてデータＢが与えられると、エンプティビットとして‘０’、かつデータビットとしてデータＢが保持されているアドレス１のワードで一致が検出される。この一致検索結果は一致線（図示省略）上に出力され、プライオリティエンコーダ（図示省略）により、そのアドレス１がエンコード出力される。
【００３２】
なお、データビットとしてデータＢが保持されていても、エンプティビットとして‘１’が保持されているワードは、そのデータビット自体が無効データであり、エンプティビット用のＣＡＭセルで不一致が検出されるため、メモリワード全体として不一致が検出される。また、複数のワードで一致が検出された場合、そのアドレスは、プライオリティエンコーダにより、あらかじめ設定されているプライオリティに従って、例えばプライオリティの高い順に順次エンコード出力される。
【００３３】
また、本実施形態のワードを用いたＣＡＭにおいて、エンプティ状態のワードを検索する場合、エンプティビットに対する検索データとして‘１’、すなわちエンプティ状態が与えられ、なおかつ全てのデータビットがマスクされて一致検索が行われる。これにより、データビットに関係なく、エンプティビットとして‘１’が保持されているワード、すなわちエンプティ状態のワードで一致が検出される。
【００３４】
例えば、図５の概念図に示す例の場合、エンプティビットに対する検索データとして‘１’が与えられ、また、全てのデータビットがマスクされて検索が行われると、データビットに関係なく、エンプティビットとして‘１’が保持されているアドレス２のワードにおいて一致が検出される。この検索結果は、同様に一致線上に出力され、プライオリティエンコーダにより、そのアドレス２がエンコード出力される。
【００３５】
同様に、複数のワードで一致が検出された場合、そのアドレスは、プライオリティエンコーダにより、あらかじめ設定されているプライオリティに従って、例えばプライオリティの高い順に順次エンコード出力される。
【００３６】
以上のように、本実施形態のワードを用いたＣＡＭでは、データビットに加えて、エンプティビットを検索対象のデータとして扱うことができる。このため、検索データとして、エンプティビットに対する検索データを追加するだけで、従来公知のＣＡＭと同様にデータビットの検索を行うことができるのはもちろん、エンプティビットそのものの検索を行うこともできるので、エンプティ状態のメモリワードを簡単に検索することができる。
【００３７】
また、ワードにエンプティビット用のＣＡＭセルを追加しただけという非常に小規模かつ簡単な構造で、しかもデータビットとその検索データとの検索結果と、エンプティビットとその検索データとの検索結果とが共通の一致線上に出力されるため、一致が検出されたワードのアドレスも、エンプティ状態のワードのアドレス（ＨＥＡ）も同じ１つのプライオリティエンコーダでエンコード出力することができる。
【００３８】
次に、本発明を、複数のワードを連結して１つのエントリを構成する機能（ワード連結機能）を持つＣＡＭに適用する場合を説明する。
【００３９】
上記のように、ワード連結機能を持つ各種構成のＣＡＭが知られている。本発明を、ワード連結機能を持つＣＡＭに適用する場合も同様に、それぞれのワードを、図１に示すワードと同様の構成とするだけでよい。すなわち、ワードを構成する複数のＣＡＭセルのうち、１ビットはエンプティビット用のＣＡＭセルとし、残りのＣＡＭセルはデータビット用のＣＡＭセルとする。
【００４０】
複数のワードを連結して１つのエントリを構成した場合も、エントリを構成するそれぞれのワードに対してデータがライトされると、エンプティビットの制御回路により、そのワードのエンプティビットが‘０’、すなわちエンプティではない状態に設定される。また、ワードに保持されているデータを消去するコマンドが与えられると、そのワードのエンプティビットは‘１’、すなわちエンプティ状態に設定される。
【００４１】
したがって、複数のワードを連結して１つのエントリを構成した場合、エントリを構成する複数のワードのエンプティビットが全て‘０’である、すなわちエンプティではない状態の場合に限り、そのエントリは有効となる。言い換えると、エントリを構成する複数のメモリワードのエンプティビットのうちの１つでも‘１’である、すなわちエンプティ状態である場合には、そのエントリは無効となる。
【００４２】
図６の概念図は、連続する４つのワードを連結して１つのエントリを構成した場合の例である。図中、１行が１つのエントリを表す。ここで、１行目のエントリの左端のワードのアドレスは‘０’であり、以後右側へ向かうにしたがってアドレスが１つずつ上昇し、右端のワードのアドレスは‘３’である。また、２行目のエントリの左端のワードのアドレスが‘４’であり、以後同様にアドレスが割り当てられている。
【００４３】
この概念図において、１行目および４行目のエントリは、１エントリを構成する全てのワードのエンプティビットが‘０’であるから、これらのエントリは有効なエントリである。これに対し、２行目のエントリは、左端のワードのエンプティビットが‘１’であり、３行目のエントリは、全てのワードのエンプティビットが‘１’であるから、これらのエントリは無効なエントリである。
【００４４】
データビットの検索を行う場合も同様に、それぞれのワードにおいて、エンプティビットに対する検索データとして‘０’が与えられ、データビットに対する検索データが与えられて検索が行われる。その結果、エントリを構成する全てのワードのエンプティビットが‘０’、すなわちエンプティ状態ではなく、なおかつ全てのワードのデータビットにおいて検索データとの一致が検出された場合にだけ、エントリとしての一致が検出される。
【００４５】
例えば、図７の概念図に示すように、図６の概念図に示す状態を持つＣＡＭにおいて、４つのワードのエンプティビットに対する検索データとして全て‘０’を与え、それぞれのワードのデータビットに対する検索データとして、それぞれデータＢ０，Ｂ１，Ｂ２，Ｂ３を与えて検索を行った場合を例に挙げて説明する。
【００４６】
この場合、例えば２行目のエントリにおいて、図中右側の３つのワードは、そのエンプティビットもデータビットもそれぞれ対応する検索データと一致するので、ワードとして一致が検出される。しかし、左端のワードにおいて、データビットは一致するが、エンプティビットが不一致となるため、ワードとして不一致が検出される。したがって、このエントリは不一致となる。
【００４７】
これに対し、図８の概念図に示すように、図６の概念図に示す状態のＣＡＭにおいて、２行目のエントリの左端のワードのエンプティビットが‘０’、すなわちエンプティではない状態のワードである場合には、このワードは、エンプティビットもデータビットも一致するため、ワードとして一致が検出される。従って、エントリを構成する４つ全てのワードにおいて一致が検出されるため、このエントリは一致となる。
【００４８】
また、エンプティ状態のワードを検索する場合の動作は、１つのワードで１つのエントリを構成した場合も、複数のワードを連結して１つのエントリを構成した場合も、ワード連結機能を持っていないＣＡＭの場合の動作と同じである。すなわち、エントリを構成する全てのワードのエンプティビットに対する検索データとして‘１’、すなわちエンプティ状態を与え、かつ全てのデータビットをマスクして一致検索が行われる。
【００４９】
以上のように、ワード連結機能を持つＣＡＭにおいても、ワード連結機能を持っていないＣＡＭの場合と全く同じようにして、データビットの一致検索およびエンプティ状態のワードの検索を行うことができる。
【００５０】
なお、ワード連結機能は、４ワードの連結に限定されるわけではなく、２ワード以上の何ワードを連結して１つのエントリを構成するようにしてもよい。また、ワード連結機能を持つＣＡＭにおいても、ワード連結を行うことなく、１ワードで１エントリを構成することが可能である。また、ワード連結の方式も何ら限定されず、本発明は、ワード連結機能を持つ従来公知のあらゆるＣＡＭに適用可能である。
【００５１】
次に、ワード連結機能を持つＣＡＭにおいて、複数のワードを連結して１つのエントリを構成した場合に、エントリを構成する複数のワードの中でエントリを代表するエントリ代表ワードを設定する機能を持つＣＡＭに本発明を適用する場合を説明する。
【００５２】
本出願人は、特開２００２−１９７８７３号公報において、ワードの連結機能を持つＣＡＭを既に提案している。同公報に開示のＣＡＭは、ワード連結を行った場合に、エントリ代表ワードを設定する機能を備えている。エントリ代表ワードはエントリを代表するワードであり、エントリ代表ワードのエンプティビットには、一致検索結果と同じように、エントリを構成する全てのワードのエンプティビットの状態が反映される。
【００５３】
すなわち、エントリ代表ワードのエンプティビットは、本実施形態の場合、エントリを構成する複数のワードのエンプティビットが全て‘０’、すなわちエンプティではない状態の場合に‘０’に設定され、１つでも‘１’が存在する場合には‘１’に設定される。このように、エントリ代表ワードを設定することによって、エントリ代表ワードのエンプティビットを確認するだけで、エントリの有効無効を判断できるという利点がある。
【００５４】
ここで、有効なエントリとは、エントリを構成する全てのワードに有効データが書き込まれているエントリである。従って、有効なエントリのエントリ代表ワードのエンプティビットは必然的に‘０’に設定される。これに対し、エントリを構成するワードに対してデータビットを消去するコマンドが与えられた場合、消去コマンドが与えられたワードのエンプティビット‘１’がエントリ代表ワードのエンプティビットに反映される。
【００５５】
なお、特開２００２−１９７８７３号公報には、エンプティビットの概念が存在しないが、ワードにエンプティビット用のＣＡＭセルを追加することによって、本発明を、この特開２００２−１９７８７３号公報に開示のＣＡＭに適用することが可能である。また、これ以外の構成は、基本的に特開２００２−１９７８７３号公報に開示のＣＡＭと同じであるので、ここではその構成の詳細な説明は省略する。
【００５６】
エントリ代表ワードが設定されたＣＡＭにおいて、エンプティ状態のエントリを検索する場合、エントリ代表ワードのエンプティビットに対する検索データとして‘１’、すなわちエンプティ状態を与え、なおかつ他の全てのワードのエンプティビットおよびデータビットをマスクして検索が行われる。その結果、エントリ代表ワードのエンプティビットが‘１’、すなわちエンプティ状態であるエントリ代表ワードでのみ一致が検出される。
【００５７】
例えば、図９の概念図に示す状態のＣＡＭにおいて、エントリ代表ワードのエンプティビットに対する検索データとして‘１’を与え、なおかつ他の全てのワードのエンプティビットおよびデータビットをマスクして検索を行うと、アドレス４，８のエントリ代表ワードにおいて一致が検出される。すなわち、２行目および３行目のエントリが無効（エンプティ状態）のエントリであることが検出される。
【００５８】
本実施形態の場合、エンプティ状態のエントリの先頭アドレス（エンプティアドレス）として、エントリを構成するメモリワードのアドレスうち、最も小さいアドレス４，８が、プライオリティエンコーダにより順次エンコード出力される。なお、これとは逆に、最も大きいアドレス７，１１を出力するようにしてもよい。また、エントリ代表ワードは、エントリを構成する複数のワードのうちのどのワードに設定してもよい。
【００５９】
例えば、図１０の概念図に示すように、図中右端のワードをエントリ代表ワードに設定した場合も、エントリ代表ワードのエンプティビットに対する検索データとして‘１’が与えられ、これ以外は全てマスクされて検索が行われる。この場合、エントリ代表ワードとエントリ内の最小アドレスとの差分である‘３’がセグメントレジスタに保持され、プライオリティエンコーダによって、一致が検出されたエントリ代表ワードのアドレス７，１１からそれぞれセグメントレジスタに保持されている‘３’を減算したアドレス４，８が、エンプティアドレスとして順次エンコード出力される。
【００６０】
以上のように、エントリ代表ワードを設定する機能を持つＣＡＭにおいても、エンプティ状態のワードの検索を行うことができる。なお、エントリ代表ワードを設定する機能を持つＣＡＭにおいて、データビットの検索を行う場合の動作は、全てのワードのエンプティビットに対する検索データとして‘０’、すなわちエンプティではない状態を与えて検索を行うこと以外、特開２００２−１９７８７３号公報に開示のＣＡＭと同じであるので、ここではその説明は省略する。
【００６１】
本発明は、基本的に以上のようなものである。
以上、本発明の連想メモリについて詳細に説明したが、本発明は上記実施形態に限定されず、本発明の主旨を逸脱しない範囲において、種々の改良や変更をしてもよいのはもちろんである。
【００６２】
【発明の効果】
以上詳細に説明した様に、本発明の連想メモリは、ワードを構成するＣＡＭセルを、データビットを保持するＣＡＭセルと、エンプティビットを保持するＣＡＭセルとによって構成し、データビットとその検索データとの検索結果と、エンプティビットとその検索データとの検索結果とが共通の一致線上に出力されるようにしたものである。
これにより、本発明によれば、ワード連結機能を持っていない連想メモリにおいても、ワード連結機能を持つ連想メモリにおいても、さらにはエントリ代表ワードを設定する機能を持つ連想メモリにおいても同様に、小規模かつ簡単な回路構成で、最もプライオリティの高いエンプティ状態のメモリワードのアドレスを求めることができる。
【図面の簡単な説明】
【図１】（Ａ）は本発明の連想メモリの一実施形態の構成概略図であり、（Ｂ）は１ワードの構成概念図である。
【図２】本発明の連想メモリにおいて、データビットの書き込み時および消去時の動作を説明する一実施形態の概略図である。
【図３】本発明の連想メモリにおいて、エンプティビットを一括で同一値に設定する場合の動作を説明する一実施形態の概略図である。
【図４】本発明の連想メモリにおいて、データビットの検索を行う場合の動作を説明する一実施形態の概略図である。
【図５】本発明の連想メモリにおいて、エンプティ状態のワードを検索する場合の動作を説明する一実施形態の概略図である。
【図６】複数のワードを連結して１つのエントリを構成した一実施形態の概略図である。
【図７】ワード連結を行ったエントリに対して検索を行う場合の動作を説明する一実施形態の概略図である。
【図８】ワード連結を行ったエントリに対して検索を行う場合の動作を説明する別の実施形態の概略図である。
【図９】エントリ代表ワードが設定されたメモリアレイに対して、エンプティ状態のエントリを検索する場合の動作を説明する一実施形態の概略図である。
【図１０】エントリ代表ワードが設定されたメモリアレイに対して、エンプティ状態のエントリを検索する場合の動作を説明する別の実施形態の概略図である。
【符号の説明】
１０  連想メモリ
１２  ＣＡＭ制御回路
１４  アドレスデコーダ
１６  プライオリティエンコーダ
１８  エンプティビットＣＡＭセル
２０  データビットＣＡＭセル
２２，２４  記憶部
２６，２８  比較部
【図１】
2004253023.tif 000003
【図２】
2004253023.tif 000004
【図３】
2004253023.tif 000005
【図４】
2004253023.tif 000006
【図５】
2004253023.tif 000007
【図６】
2004253023.tif 000008
【図７】
2004253023.tif 000009
【図８】
2004253023.tif 000010
【図９】
2004253023.tif 000011
【図１０】
2004253023.tif 000012