(57)【特許請求の範囲】
【請求項１】
複数の格納データを記憶しておき、検索データが入力され、入力された検索データに対応する格納データを検索する連想メモリにおいて、
複数の格納データを各格納データ毎に記憶する複数のメモリワードと、
前記複数のメモリワードそれぞれに対応して備えられた、検索の際に、入力された検索データと、前記複数のメモリワードそれぞれに格納された各格納データとの間に対応関係が存在することが検出された場合にその対応関係の存在を表わすヒットフラグを格納する複数のフラグレジスタと、
前記複数のフラグレジスタのいずれかに前記ピットフラグが格納されたか否かを、複数回の検索それぞれについて順次格納するヒット列レジスタとを備えたことを特徴とする連想メモリ。
【請求項２】
複数の格納データを記憶しておき、検索データが入力され、入力された検索データに対応する格納データを検索する連想メモリにおいて、
それぞれが複数の格納データの集合からなる複数のデータ群を構成する各格納データを、該各格納データ毎に記憶する複数のメモリワードと、
前記複数のメモリワードそれぞれに対応して備えられた、検索の際に、入力された検索データと、前記複数のメモリワードそれぞれに格納された各格納データとの間に対応関係が存在することが検出された場合にその対応関係の存在を表わすヒットフラグを格納する複数のフラグレジスタと、
所定のメモリワードに記憶された格納データと入力された検索データとの間に対応関係が存在することが検出されたときに、該所定のメモリワードに対応する前記フラグレジスタに対応関係の存在を表わすヒットフラグを格納する第１のモードと、今回の検索時に所定の第１のメモリワードにおいて対応関係が検出され、かつ、前記第１のメモリワードに記憶された格納データが属するデータ群を構成する各格納データそれぞれを記憶する複数のメモリワードからなるメモリワード群に属する、前記第１のメモリワードを除く他の任意の第２のメモリワードに対応する前記フラグレジスタに前記ヒットフラグが格納されていた場合に、前記第１のメモリワードに対応する前記フラグレジスタに前記ヒットフラグを格納するとともに前記第２のメモリワードに対応する前記フラグレジスタに格納されていた前記ヒットフラグをリセットする第２のモードとを有する一致検出回路と、前記複数のフラグレジスタのいずれかに前記ヒットフラグが格納されたか否かを、複数回の検索それぞれについて順次格納するヒット列格納レジスタとを備えたことを特徴とする連想メモリ。
【請求項３】
１つのデータ群内の複数の格納データを互いに識別するための属性と該属性が付されたデータとのペアからなる各格納データを前記複数のメモリワードそれぞれに記憶しておき、前記属性と前記データとのペアからなる検索データを用いて検索を行なうものであることを特徴とする請求項１又は２記載の連想メモリ。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、一致検索の行われるデータ幅を複数のワードに拡張する機能、すなわち、連続する複数回の検索でそれぞれ一致が検出された場合に全体としての一致が検出される機能を備えた連想メモリに関する。
【０００２】
【従来の技術】
従来より、配列された複数の各メモリワードそれぞれに各ディジタルデータを記憶しておき、検索データを入力し、入力された検索データの全部もしくは所定の一部のビットパターンと一致するビットパターンを有するディジタルデータが記憶されたメモリワードを検索する連想メモリ（Ａｓｓｏｃｉａｔｉｖｅ  Ｍｅｍｏｒｙ，内容アドレス式メモリ；Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）が提案されている。
【０００３】
図２は、連想メモリの一例を表わした回路ブロック図である。
この連想メモリ１０には、ｍビットを１ワードとする、互いに図の横方向に並ぶｍビットのメモリセルからなる多数のメモリワード１１＿１，１１＿２，…，１１＿ｎが備えられている。またこの連想メモリ１０は、１ワードの検索データが入力されラッチされる検索データレジスタ１２を備え、検索データレジスタ１２にラッチされた検索データの全部もしくは所定の一部のビットパターンと、各メモリワード１１＿１，１１＿２，…，１１＿ｎに記憶された格納データのうち上記ビットパターンと対応する部分のビットパターンとの一致不一致が比較され、各メモリワード１１＿１，１１＿２，…，１１＿ｎのそれぞれに対応して備えられた一致線１４＿１，１４＿２，…，１４＿ｎのうちビットパターンが一致したメモリワード１１＿１，１１＿２，…，１１＿ｎに対応する一致線１４＿１，１４＿２，…，１４＿ｎに論理‘１’（ここでは５Ｖとする）の一致信号が出力される。それ以外の一致線１４＿１，１４＿２，…，１４＿ｎは論理‘０’（ここでは０Ｖとする）にとどまる。
【０００４】
これらの一致線１４＿１，１４＿２，…，１４＿ｎに出力された信号は、各フラグレジスタ１５＿１，１５＿２，…，１５＿ｎに格納される。ここでは、一例として、図示のように、各フラグレジスタ１５＿１，１５＿２，…，１５＿ｎにそれぞれ‘０’，‘１’，‘１’，‘０’，…，‘０’，‘０’が格納されたものとする。これらのフラグレジスタ１５＿１，１５＿２，…，１５＿ｎに格納された信号はプライオリティエンコーダ１６に入力される。プライオリティエンコーダ１６には、エンコードパルスＥＰが入力され、エンコードパルスＥＰが入力される毎に、所定の優先順位づけに従って、論理‘１’の信号が格納されたフラグレジスタ（ここではフラグレジスタ１５＿２とフラグレジスタ１５＿３の２つ）のうちの優先度の高いフラグレジスタに対応するアドレス信号ＡＤが順次出力される。ここでは、添字が若いほど優先順位が高いものとし、従ってエンコードパルスＥＰが１つだけ入力されると、フラグレジスタ１５＿２に対応するメモリアドレスが出力される。このプライオリティエンコーダ１６から出力されたアドレス信号ＡＤは、必要に応じてアドレスデコーダ１７に入力される。アドレスデコーダ１７ではこの入力されたアドレス信号ＡＤをデコードして、各メモリワード１１＿１，１１＿２，…，１１＿ｎそれぞれに対応して備えられたワード線１８＿１，１８＿２，…，１８＿ｎのうちの入力されたアドレス信号ＡＤに対応するいずれか１本のワード線（ここではワード線１８＿２）にアクセス信号（ここでは論理‘１’の信号）を出力する。これによりアクセス信号の出力されたワード線１８＿２に対応するメモリワード１１＿２に記憶されている格納データが出力レジスタ１９に読み出される。
【０００５】
次に、エンコードパルスＥＰがもう１つ入力されると、今度はフラグレジスタ１５＿３に対応するメモリワード１１＿３のアドレスを得ることができる。
上記のように、連想メモリ１０は、検索データの全部もしくは所定の一部のデータを用いて多数のメモリワード１１＿１，１１＿２，…，１１＿ｎに記憶された格納データを検索し、一致する格納データを有するメモリワードのアドレスを得、必要に応じてそのメモリワードに記憶されたデータ全体を読み出すことができるように構成されたメモリである。
【０００６】
上記のような基本構成を有する連想メモリにおいて、一致検索の対象となるデータ幅を２ワードもしくはそれ以上の複数ワードに拡張する技術が提案されている。
図３は、データ拡張機能を備えた連想メモリの一例を示すブロック図である。図２に示した連想メモリの構成要素と対応する構成要素には、図２に付した符号と同一の符号を付して示し、その要素についての重複説明は省略する。
【０００７】
各メモリワード１１＿１，１１＿２，…から延びる各一致線１４＿１，１４＿２，…，は、各アンドゲート２０＿１，２０＿２，…の一方の入力端子に接続されている。また各アンドゲート２０＿１，２０＿２，…の他方の入力端子には各オアゲート２１＿２，２１＿３，…の出力端子が接続されており、各オアゲート２１＿２，２１＿３，…の一方の入力端子は、初回検索制御線２２に接続されている。ただし図示の一番上のアンドゲート２０＿１に対応するオアゲートは省略されており、そのアンドゲート２０＿１の入力端子に初回検索御線２２が直接接続されている。
【０００８】
各アンドゲート２０＿１，２０＿２，…の出力端子は各第１のフラグレジスタ２３＿１，２３＿２，…のデータ入力端子に接続され、各第１のフラグレジスタ２３＿１，２３＿２，…の出力端子は各第２のフラグレジスタ２４＿１，２４＿２，…の入力端子に接続されている。各第２のフラグレジスタ２４＿１，２４＿２，…の出力端子は、図２に示すプライオリティエンコーダ１６（図３では図示省略）に接続されるとともに、図３の下方に隣接するメモリワードに対応するオアゲート２１＿２，２１＿３，…の入力端子に接続されている。
【０００９】
互いに対応する第１および第２のフラグレジスタ２３＿１，２４＿１，；２３＿２，２４＿２，…の各ペアが図２に示す各フラグレジスタ１５＿１，１５＿２，…に対応する。
第１のフラグレジスタ２３＿１，２３＿２，…と第２のフラグレジスタ２４＿１，２４＿２，…には、ともに、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１が入力され、その一致結果ラッチ信号Ｓ１により各データ入力端子から入力された入力データがラッチされるが、第１のフラグレジスタ２３＿１，２３＿２，…には、一致結果ラッチ信号５１の立ち上がりａの時点における入力データがラッチされ、第２のフラグレジスタ２４＿１，２４＿２，…には、一致結果ラッチ信号Ｓ１の立ち下がりｂの時点の入力データがラッチされる。
【００１０】
以上のように構成された連想メモリにおいては、以下のようにして一致検索が行われる。尚、ここでは図示のように、各メモリワード１１＿１，１１＿２，１１＿３，１１＿４，１１＿５，１１＿６…には、各格納データＡ，Ｂ，Ｃ，Ｄ，Ｃ，Ｆ，…が格納されているものとする。
ここで、各格納データを単独に検索する際は、検索データＲＥＦ＿ＤＡＴＡを入力して検索を行う際に、初回検索制御線２２に初回検索タイミング信号Ｓ２を出力する。ここでは、検索データＲＥＦ＿ＤＡＴＡとしてデータ‘Ｂ’を入力したものとすると、データ‘Ｂ’が格納されたメモリワード１１＿２に対応する一致線１４＿２に論理‘１’の一致信号が出力されてアンドゲート２０＿２に入力され、また、これとともに初回検索タイミング信号Ｓ２がオアゲート２１＿２を経由してアンドゲート２０＿２に入力されるため、アンドゲート２０＿２から論理‘１’の信号が出力される。またこのとき、他の一致線１４＿１；１４＿３，１４＿４，…には論理‘０’の信号が出力されるため、それに対応する他のアンドゲート２０＿１；２０＿３，２０＿４，…からは論理‘０’の信号が出力される。
【００１１】
アンドゲート２０＿２から出力された論理‘１’の信号は、一致結果ラッチ制御線２５に出力された一致結果ラッチ信号Ｓ１の立ち上がりａのタイミングで第１のフラグレジスタ２３＿２にラッチされ、それに引き続く一致結果ラッチ信号Ｓ１の立ち下がりｂのタイミングで第２のフラグレジスタ２４＿２にラッチされる。
【００１２】
また第１のフラグレジスタ２３＿２および第２のフラグレジスタ２４＿２に論理‘１’の信号がラッチされる各タイミングで、他の第１フラグレジスタ２３＿１；２３＿３，２３＿４，…、および他の第２のフラグレジスタ２４＿１；２４＿３，；２４＿４，…には論理‘０’の信号がラッチされる。
このようにして各第２のフラグレジスタ２４＿１，２４＿２，２４＿３，…にラッチされた論理‘０’，‘１’，‘０’，…の信号が図２に示すプライオリティエンコーダ１６に入力され、メモリワード１１＿２のアドレス信号ＡＤが得られる。
【００１３】
次に、データ幅が拡張された検索を行う場合について説明する。ここでは、２ワードに拡張された、データ‘Ｂ’とデータ‘Ｃ’からなる２ワードデータを検索する場合について説明する。
この場合、先ず上記と同様にして、データ‘Ｂ’の検索を行う。これにより、メモリワード１１＿２に対応する第１および第２のフラグレジスタ２３＿２，２４＿２に論理‘１’の信号がラッチされる。次に検索データＲＥＦ＿ＤＡＴＡとしてデータ‘Ｃ’を入力して検索を行うが、このときは初回検索制御線２２には初回検索タイミング信号Ｓ２は出力せずに、初回検索制御線２２は論理‘０’の状態に保っておく。検索データＲＥＦ＿ＤＡＴＡとしてデータ‘Ｃ’を入力して検索を行うと、図示の２つのメモリワード１１＿３，１１＿５にそれぞれ対応する一致線１４＿３，１４＿５に論理‘１’の一致信号が出力されるが、オアゲート２１＿３には、第２のフラグレジスタ２４＿２にラッチされている論理‘１’の信号が入力されているため一致線１４＿３の一致信号はアンドゲート２０＿３を通過し、第１および第２のフラグレジスタ２３＿３，２４＿３に、一致を表わす論理‘１’の信号がラッチされる。一方オアゲート２１＿５には、第２のフラグレジスタ２４＿４にラッチされている論理‘０’の信号が入力されているため一致線１４＿５の一致信号はアンドゲート２０＿５で遮断され、第１および第２のフラグレジタ２３＿５，２４＿５には不一致を表わす論理‘０’の信号がラッチされることになる。このようにして、データ‘Ｂ’とデータ‘Ｃ’のペアからなる２ワードデータの一致検出が行われる。３ワード以上のデータの一致検出も同様にして行われる。
【００１４】
ただし、図３に示す連想メモリは、データ幅拡張機能を備えてはいるが、２ワード，３ワード等に拡張されるデータは、互いに隣接したメモリワードに所定の順序で格納されている必要があり、検索しようとする複数のデータが互いに離れたメモリワードに格納されている場合や逆の順序、例えばデータ‘Ｃ’，データ‘Ｂ’の順序に格納されている場合には複数のデータを結合した一致検出を行うことはできない。
【００１５】
このような検索が必要となる場合のデータ構造を、図４に示す。図４には、それぞれ属性Ｉ，ＩＩ，ＩＩＩ，ＩＶが付された４つのデータがセットとなって１つのデータ群を構成しているデータ構造が示されている。データ群および属性の概念を明確にするために一例を挙げると、例えば各群番号１，２，３，４，…毎の各データ群は各個人に属するデータであり、属性Ｉはその人の氏名，属性ＩＩはその人の生年月日、属性ＩＩＩは住所、……等を示している。
【００１６】
このように各属性Ｉ，ＩＩ，ＩＩＩ，ＩＶが付された複数のデータからなるデータ群を連想メモリに格納しておいて検索を行う場合に、例えば群番号１のデータ群を検索する場合を例に説明すると、データ‘Ａ’の検索とデータ‘Ｂ’の検索をこの順に行って、一致するデータ群の残りのデータ‘Ｃ’，‘Ｄ’を読み出すことだけではなく、例えばデータ‘Ａ’の検索とデータ‘Ｄ’の検索を行って残りのデータ‘Ｂ’，‘Ｃ’を読み出したい場合や、データ‘Ｂ’の検索を先に行い、次にデータ‘Ａ’の検索を行いたい場合がある。
【００１７】
しかし、上述したワード幅拡張機能を備えた連想メモリ（図３参照）では、このような検索は不可能である。また上述した連想メモリでは、データ‘Ａ’とデータ‘Ｂ’の検索を行った場合に、図４に示す群番号１の欄にある属性Ｉの付されたデータ‘Ａ’と属性ＩＩの付されたデータ‘Ｂ’とのペアと、群番号４の欄にある属性ＩＩの付されたデータ‘Ａ’と属性ＩＩＩの付されたデータ‘Ｂ’とのペアとの区別をすることはできず、例えば、‘氏名’という属性Ｉと‘生年月日’という属性ＩＩの情報を基にそれらが一致する特定の個人の属性ＩＩＩ，ＩＶの情報を知ろうとしても、属性ＩＩと属性ＩＩＩのペアでも一致が検出される等必要な情報以外のノイズが混入してしまうことになる。
【００１８】
このような問題を解決した連想メモリが、本願出願人により提案されている（特願平５−２４８１２１号参照）。以下この提案に係る連想メモリについて説明する。
図５は、上記提案に係る連想メモリの一例を示すブロック図である。図３に示す連想メモリの各構成要素と同一の構成要素には、図３に付した符号と同一の符号を付して示し、相違点についてのみ説明する。
【００１９】
各メモリワード１１＿１，１１＿２，…は、属性を格納する属性格納部１１＿１＿１，１１＿２＿１，…とデータを格納するデータ格納部１１＿１＿２，１１＿２＿２，…とで構成されており、各メモリワード１１＿１，１１＿２，…には、互いに対応する属性とデータとのペアからなる格納データがそれぞれ格納されている。ここでは、図示のように、各メモリワード１１＿１，１１＿２，１１＿３，１１＿４には、それぞれ、図４に示す群番号１に属する、属性Ｉ，データ‘Ａ’、属性ＩＩ，データ‘Ｂ’、属性ＩＩＩ，データ‘Ｃ’、属性ＩＶ，データ‘Ｄ’が格納されている。また各メモリワード１１＿５，１１＿６，…には、それぞれ、図４に示す群番号２に属する、属性Ｉ，データ‘Ｃ’、属性ＩＩ，データ‘Ｆ’、……が格納されている。また検索にあたっては、属性とデータとのペアからなる検索データＲＥＦ＿ＤＡＴＡが入力される。
【００２０】
各メモリワード１１＿１，１１＿２には、そこに記憶された格納データ（属性及びデータの双方）が、入力された検索データ（属性及びデータの双方）と一致しているときに一致信号が出力される一致線１４＿１，１４＿２，…のほか、属性のみの一致不一致の信号が出力される属性一致線３０＿１，３０＿２，…が備えられている。尚、属性のみの一致も、属性及びデータの双方の一致も、従来の一致検出回路と同様に構成され、従来の一致検出回路は連想メモリの分野において極めて一般的な技術であるため、ここでの図示および説明は省略する。
【００２１】
各メモリワード１１＿１，１１＿２に対応して第３のフラグレジスタ３１＿１，３１＿２，…が備えられており、各属性一致線３０＿１，３０＿２，…は対応する第３のフラグレジスタ３１＿１，３１＿２，…のデータ入力端子に延びている。また、この連想メモリには、図４に示す各データ群に属するデータが格納された複数のメモリワードからなるメモリワード群それぞれについて１本ずつデータ線３２＿１，３２＿２，…が備えられており、またデータ線３２＿１，３２＿２，…と各第２のフラグレジスタ２４＿１，２４＿２，…の出力端子との間には各第１のスイッチ３３＿１，３３＿２，…が備えられている。これらの第１のスイッチ３３＿１，３３＿２，…は具体的にはトランジスタ等を用いて構成される。後述する他のスイッチについても同様である。各第１のスイッチ３３＿１，３３＿２，…は、対応する各第３のフラグレジスタ３１＿１，３１＿２，…に論理‘１’の信号がラッチされているときに導通され、論理‘０’の信号がラッチされているときには遮断される。各第３のフラグレジスタ３１＿１，３１＿２，…は、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１の立ち下がりｂのタイミングで、対応する属性一致線３０＿１，３０＿２，…の信号をラッチする。
【００２２】
またデータ線３２＿１，３２＿２，…と各オアゲート２１＿１，２１＿２，…の入力端子との間に各第２のスイッチ３４＿１，３４＿２，…が備えられており、これら各第２のスイッチ３４＿１，３４＿２，…は、対応する属性一致線３０＿１，３０＿２，…の信号により、その信号が一致を表わす論理‘１’のときに導通状態、不一致を表わす論理‘０’の時に遮断状態となるように制御される。尚、この図５に示す連想メモリには、図３に示す連想メモリと異なり、図示の最上段のメモリワード１１＿１に対応するアンドゲート２０＿１の前段にもオアゲート２１＿１が備えられている。
【００２３】
以上のように構成された連想メモリにおいて、一致検索は以下のようにして行われる。
１ワード分の単独のデータ検索、および連続した複数ワードの検索のうち第１回目の検索は、図３に示した従来のワード拡張機能付連想メモリの場合と同じであるためここでは説明は省略し、ここでは第１回目の検索において属性ＩＩとデータ‘Ｂ’とからなる検索データＲＥＦ＿ＤＡＴＡによってメモリワード１１＿２に対応する第１および第２のメモリワード２３＿２，２４＿２に論理‘１’がラッチされたものとする。このとき、属性の一致を受けてメモリワード１１＿２に対応する属性一致線３０＿２に論理‘１’の信号が出力され、これにより、対応する第３のフラグレジスタ３１＿２にも論理‘１’の信号がラッチされ、対応する第１のスイッチ３３＿２がオンし、対応する第２のフラグレジスタ２４＿２に格納された、属性及びデータ双方の一致を表わす論理‘１’の信号がデータ線３２＿１に出力される。またこれとともに、対応する第２のスイッチ３４＿２もオンするが、第１回目の検索においてはこれは無用の動作である。
【００２４】
次に、属性ＩＶとデータ‘Ｄ’からなる検索データＲＥＦ＿ＤＡＴＡを入力して検索を行うものとする。このときは、図３の連想メモリの場合と同様、初回検索制御線２２は論理‘０’に保持されている。このとき、属性の一致を受けてメモリワード１１＿４に対応する属性一致線３０＿４に論理‘１’の信号が出力され、これにより対応する第２のスイッチ３４＿４がオンし、データ線３２＿１に出力されていた、メモリワード１１＿２に対応する第２のフラグレジスタ２４＿２の論理‘１’の信号がオアゲート２１＿４を経由してアンドゲート２０＿４に入力される。このため、メモリワード１１＿４で属性ＩＶとデータ‘Ｄ’の双方の一致が検出されて一致線１４＿４に論理‘１’の一致信号が出力され、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１により、対応する第１および第２のフラグレジスタ２３＿４，２４＿４に論理‘１’の信号がラッチされる。またこのとき、属性一致線３０＿４に出力された論理‘１’の信号が、対応する第３のフラグレジスタ３１＿４にラッチされ、対応する第１のスイッチ３３＿４がオンし、第２のフラグレジスタ２４＿４の論理‘１’の信号がデータ線３２＿１に出力される。またこの２回目の検索では、メモリワード１１＿２に対応する属性一致線３０＿２には属性の不一致を表わす論理‘０が出力されるため、対応する第３のフラグレジスタ３１＿２には‘０’が格納され、メモリワード１１＿２に対応する第１のスイッチ３３＿２はオフする。
【００２５】
これにより、メモリワード１１＿４に対応する第２のフラグレジスタ２４＿４の論理‘１’の信号がプライオリティエンコーダ１６（図２参照）に入力され、メモリワード１１＿４のアドレスが得られることになるが、メモリワード１１＿４には属性ＩＶが格納されていることは予め分かっており、同一群内の例えば属性ＩＩＩのデータを読み出したいときは、得られたアドレスから１を引いてメモリワード１１＿３のアドレスを求め、そのアドレスをアドレスデコーダ１７に入力してメモリワード１１＿３の内容を読み出せばよい。
【００２６】
一方、２回目の検索時に、属性ＩＶとデータ‘Ｄ’とからなる検索データに代わり、例えば属性ＩＶとデータ‘Ｂ’とからなる検索データで検索が行われた場合、メモリワード１１＿４については、属性は一致するため第２のスイッチ３４＿４がオンし、データ線３２＿１に出力されている論理‘１’の信号が取り込まれるが、データが異なるため一致線１４＿４には不一致を表わす論理‘０’が出力され、第１及び第２のフラグレジスタ２３＿４，２４＿４には一致が検出されなかったことを示す論理‘０’がラッチされる。また、データ‘Ｂ’が一致するメモリワード１１＿２については属性が一致せず、したがって属性及びデータの双方も一致しない。
【００２７】
以上のようにして、図５に示す連想メモリでは、同一の群内においては、互いに離れたメモリワードに記憶されたデータであっても、もしくはデータの順序を逆にして検索した場合であっても、検索を行うことができる。
ここで、図５に示す連想メモリにおけるデータ線３２＿１，３２＿２，…，は、１つの群に属するデータの数が予め定まっているものとしてその長さが固定されたものであるが、このように固定長のデータ線を備えると、１つの群に属するデータの数の最大を見積もり、最大のデータ数に対応した長さのデータ線を備える必要がある。これではその最大よりも少ない数のデータによりデータ群が構成される場合に無駄なメモリワードが発生することになる。そこで、１つの群に属するデータの数に合せてデータ線を可変長とすることが好ましい。
【００２８】
図６は、可変長のデータ線を実現する一つの方式を示した模式図である。
データ線３２が複数のメモリワード１１＿１，１１＿２，１１＿３，…に亘って延び、そのデータ線３２には、最上端のメモリワード１１＿１を除く他のメモリワード１１＿２，１１＿３，…それぞれに対応する各スイッチ４０＿１，４０＿２，４０＿３，…が互いにシリーズに配置されている。これらの各スイッチ４０＿２，４０＿３，４０＿４，…は、対応するメモリワード１１＿２，１１＿３，１１＿４，…と、その直ぐ上段に隣接するメモリワード１１＿１，１１＿２，１１＿３，…との間に配置されている。それらのスイッチ４０＿２，４０＿３，４０＿４，…のうちの１つおきのスイッチ４０＿２，４０＿４，４０＿６，…は第１制御線４１に出力される第１のスイッチ制御信号によりオンし、３つおきのスイッチ４０＿３，４０＿７，…は第２制御線４２に出力される第２のスイッチ制御信号によりオンし、残りのスイッチのうち８つおきのスイッチ４０＿５，…は第３制御線４３に出力される第３のスイッチ制御信号によりオンされる。
【００２９】
１つのデータ群を構成するデータの数が２の場合は、第１制御線４１に第１のスイッチ制御信号を出力することにより１つおきのスイッチ４０＿２，４０＿４，４０＿６，…をオンさせる。これにより各２つのメモリワード１１＿１，１１＿２；１１＿３，１１＿４；１１＿５，１１＿６；…毎に切断されたデータ線が形成される。また、１つのデータ群を構成するデータの数が４の場合は、第１制御線４１に第１のスイッチ制御信号を出力するとともに第２制御線４２に第２のスイッチ制御信号を出力する。すると、各４つのメモリワード１１＿１，１１＿２，１１＿３，１１＿４；１１＿５，１１＿６，…毎に切断されたデータ線が形成される。同様にして、１つのデータ群を構成するデータの数が８の場合は、第１制御線４１、第２制御線４２にそれぞれ第１および第２のスイッチ制御信号を出力するとともに、第３制御線４３に第３のスイッチ制御信号を出力する。これにより各８つのメモリワード１１＿１，…，１１＿８；１１＿９…毎に切断されたデータ線が形成される。
【００３０】
この方式によれば、１つのデータ群を構成するデータの数が２の倍数の場合はメモリワードに空きは生じないが、２の倍数以外の、例えば３，５，９等の場合空きのメモリワードが生じてしまうことになる。この空きのメモリワードが生じないように多数のスイッチ４０＿２，４０＿３，…を任意にオン，オフできるように構成すると、制御線の本数が多数本となり、またそれらの制御線にスイッチ制御信号を出力する制御回路が複雑となる。したがって、図６に示す方式は、データ線の長さを完全に任意に制御するには不向きである。
【００３１】
図７は、可変のデータ線を実現するもう一つの方式を示した模式図である。
多数のメモリワードに亘ってデータ線３２が延び、そのデータ線３２に互いにシリーズに接続された、最上端のメモリワードを除く他のメモリワードそれぞれに対応する各スイッチ４０＿２，４０＿３，４０＿４，…が備えられている点は図６の場合と同じである。各メモリワードには、各属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…が備えられており、それら属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…には、図示の各属性Ｉ，ＩＩ，ＩＩＩ，ＩＶがそれぞれ格納されている。この例は、属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…に格納された属性が属性Ｉかそれ以外の属性ＩＩ，ＩＩＩ，ＩＶかに応じて、属性Ｉの場合は対応するスイッチをオフのままとし、それ以外の属性ＩＩ，ＩＩＩ，ＩＶの場合は対応するスイッチをオンするように構成したものである。このように構成すると、１つのデータ群を構成するデータの数がいくつであっても、また、データ数の異なるデータ群が混在していても、各データ群の先頭に属性Ｉのデータを配置することにより、自動的に過不足ない数のメモリワード毎に切断されたデータ線が形成されることになる。
【００３２】
図８は、属性がＩかそれ以外かを判定する属性判定回路の一例を示す回路図である。
ここでは属性Ｉに‘０００’が割り当てられており、属性格納部１１＿ｉ＿１に格納された属性が属性Ｉ（‘０００’）の場合オアゲートから‘０’が出力され、したがってトランジスタ４０で構成されたスイッチはオフ状態となり、そのトランジスタ４０の両側のデータ線が電気的に切断される。属性格納部１１＿ｉ＿１に格納された属性が属性Ｉ以外の属性の場合はオアゲートから‘１’が出力され、トランジスタ４０はオン状態となり、そのトランジスタの両側のデータ線が接続される。
【００３３】
このように、図５に示す連想メモリにおいて、１つのデータ群を構成するデータの数に応じてデータ線３２＿１，３２＿２，…の長さを調整することもできる。もちろん、属性データを利用するのではなく、専用の制御線によってスイッチを制御することによりデータ線の長さを調整してもよい。
【００３４】
【発明が解決しようとする課題】
上記提案に係る連想メモリは、上述したように、１つのデータ群が格納されたメモリワード群内の互いに離れたアドレスの複数のメモリワードに跨る検索や、順序が逆の検索を許容する点では従来の連想メモリと比べ極立って優れているが、図５に示す構成では、例えば
（ＡおよびＢ）又は（ＸおよびＹ）  ………  （１）
に合致するデータ群が存在するか否かといった、アンド（および）とオア（又は）とが入り混った検索を行なうことはできない。例えば図５に示すようなデータが格納されていた場合に、先ず、初回検索タイミング信号Ｓ２を入力して、属性ＩとデータＡで検索すると、第２のメモリワード２４ １が論理‘１’となる。次に初回検索タイミング信号Ｓ２は入力せずに、属性ＩＩとデータＢで検索すると、第２のメモリワード２４ ２が論理‘１’となるとともに、第２のメモリワード２４ ２は論理‘０’にリセットされる。ここまではよいが、次に、属性ＩＩＩ  とデータＸで検索すると、初回検索タイミング信号Ｓ２を入力しても入力しなくても、図５に図示のいずれの第２のメモリワード２４ １，２４ ２，……も論理‘０’となり、上記（１）式の検索に失敗する結果となる。これを回避するために、外部の、例えばマイクロコンピュータ等で、一連の検索（例えば上記（１）式の最初から最後まで）の途中で中間的な検索結果を調べる必要があり、極めて複雑なシステム構成となってしまい、検索速度の低下も招くという問題がある。
【００３５】
本発明は、上記事情に鑑み、例えば上記（１）式のような複雑な論理の検索を、その一連の検索の途中で、その途中までの検索結果を外部からアクセスすることなく、可能とする連想メモリを提供することを目的とする。
【００３６】
【課題を解決するための手段】
上記目的を解決する本発明の連想メモリは、複数の格納データを記憶しておき、検索データが入力され、入力された検索データに対応する格納データを検索する連想メモリにおいて、
（１）複数の格納データを各格納データ毎に記憶する複数のメモリワード
（２）上記複数のメモリワードそれぞれに対応して備えられた、検索の際に、入力された検索データと、上記複数のメモリワードそれぞれに格納された各格納データとの間に対応関係が存在することが検出された場合にその対応関係の存在を表わすヒットフラグを格納する複数のフラグレジスタ
（３）上記の複数のフラグレジスタのいずれかにヒットフラグが格納されたか否かを、複数回の検索それぞれについて順次格納するヒット列レジスタ
を備えたことを特徴とする。
【００３７】
ここで、上記本発明の連想メモリは、上記（１）〜（３）に加え、
（４）上記メモリワードが、それぞれが複数の格納データの集合からなる複数のデータ群を構成する各格納データを、各格納データ毎に記憶するものであり、
（５）所定のメモリワードに記憶された格納データと入力された検索データとの間に対応関係が存在することが検出されたときに、その所定のメモリワードに対応するフラグレジスタにその対応関係の存在を表わすヒットフラグを格納する第１のモードと、今回の検索時に所定の第１のメモリワードにおいて対応関係が検出され、かつ、その第１のメモリワードに記憶された格納データが属するデータ群を構成する各格納データそれぞれを記憶する複数のメモリワードからなるメモリワード群に属する、その第１のメモリワードを除く他の任意の第２のメモリワードに対応するフラグレジスタにヒットフラグが格納されていた場合に、上記第１のメモリワードに対応するフラグレジスタにヒットフラグを格納するとともに上記第２のメモリワードに対応するフラグレジスタに格納されていたヒットフラグをリセットする第２のモードとを有する一致検出回路
を備えることが好ましい。
【００３８】
また、上記本発明の連想メモリは、１つのデータ群内の複数の格納データを互いに識別するための属性と属性が付されたデータとのペアからなる各格納データを上記複数のメモリワードそれぞれに記憶しておき、属性とデータとのペアからなる検索データを用いて検索を行なうものであってもよい。
【００３９】
【作用】
本発明の連想メモリは、上記（３）のヒット列レジスタを備えたものであるため、そのヒット列レジスタに一連の検索の間の中間の検索結果が格納されることになり、種々の論理検索に対応できる連想メモリが実現する。
【００４０】
【実施例】
以下、本発明の実施例について説明する。
図１は、本発明の連想メモリの一実施例の、本発明に特徴的な部分を示した回路ブロック図である。この回路ブロックには、図５に示す連想メモリをベースにして、その図５に示す連想メモリの一部と、図５に示す連想メモリに追加された部分が示されている。
【００４１】
ここでは、図示のように、各メモリワード１１ １，１１ ２，…，１１ ｍ，…，１１ ｎ，…に、それぞれ、各属性Ｉ〜ＩＶと各データＧ，Ｈ，Ｉ，Ｊ，Ａ，Ｂ，Ｅ，Ｅ，…，Ａ，Ｂ，Ｃ，Ｃ，…，Ａ，Ａ，Ｃ，Ｆが格納されているものとする。この実施例では、属性レジスタ１２ １に格納された属性データと、外部から入力され、入力データレジスタ１２ ２に格納された入力データとのペアを検索データとして各メモリワード１１ １，１１ ２，…，１１ ｍ，…，１１ ｎ，…に入力して検索を行なう。
【００４２】
この連想メモリには、検索モードレジスタ５１が備えられており、この検索モードレジスタ５１には、一連の検索（ここでは４回の検索とする）のうちの各検索において、初回検索タイミング信号Ｓ２を入力するか否かを定めるフラグが格納される。ここでは、後述する検索を行なうために、検索モードレジスタ５１には、‘１，０，１，０’が格納されており、一連の４回の検索のうち、最初の検索では初回検索タイミング信号Ｓ２が入力され、２回目の検索では初回検索タイミング信号Ｓ２は入力されず、３回目の検索では、初回検索と見なされて、初回検索タイミング信号Ｓ２が入力され、４回目の検索では初回検索タイミング信号Ｓ２は入力されない。
【００４３】
また、各メモリワード１１ １，１１ ２，…，１１ ｍ，…，１１ ｎ，…に対応して、検索の際に各メモリワード１１ １，１１ ２，…，１１ ｍ，…，１１ ｎ，…で一致が検出されたか否かを示すヒットフラグが格納されるフラグレジスタ２４ １，２４ ２，…，２４ ｍ，…，２４ ｎ，…が備えられている。このフラグレジスタ２４ １，２４ ２，…，２４ ｍ，…，２４ ｎ，…は、図５に示す連想メモリの第２のフラグレジスタ２４ １，２４ ２，…に相当する。
【００４４】
またこの連想メモリには、全てのメモリワード１１ １，１１ ２，…，１１
ｍ，…，１１ ｎ…に跨って延びる検索線５２が備えられている。
検索線５２とグラウンドとの間には、各メモリワード１１ １，１１ ２，…，１１ ｍ，…，１１ ｎ，…それぞれに対応して備えられた、互いに直列に接続された各２つのトランジスタ５３ １，５４ １；５３ ２，５４ ２；…；５３ ｍ，５４ ｍ；…；５３ ｎ，５４ ｎ；…が配置されている。各２つのトランジスタ５３ １，５４ １；５３ ２，５４ ２；…；５３ ｍ，５４ ｍ；…；５３ ｎ，５４ ｎ；…のうちの一方のトランジスタ５３ １，５３ ２，…，５３ ｍ，…，５３ ｎ，…のゲートは、対応するフラグレジスタ２４ １，２４ ２，…，２４ ｍ，…，２４ ｎ，…に接続されており、もう一方のトランジスタ５４ １，５４ ２，…，５４ ｍ，…，５４ ｎ，…のゲートは、共通の一本の制御線５５に接続されている。
【００４５】
また、検索線５１の、図１の下側の一端は、その検索線５１の電荷のチャージの状態を検出して論理‘０’又は論理‘１’を検出するセンスアンプ５６を構成するセンスアンプインバータ５７の入力に接続されている。またこのセンスアンプ５６には、センスアンプインバータ５７の入力と電源ＶＤＤとの間に配置されゲートがセンスアンプインバータ５７の出力と接続されたフィードバック用Ｐチャンネルトランジスタ５８と、センスアンプインバータ５７の入力と電源ＶＤＤとの間に配置されゲートが制御線５５に接続されたプリチャージ用Ｐチャンネルトランジスタ５９が備えられている。
【００４６】
また、センスアンプインバータ５７の出力は、ヒット列レジスタ６０を構成する、この実施例では４つのフリップフロップ６０ １，６０ ２，６０ ３，６０ ４に接続されている。各フリップフロップ６０ １，６０ ２，６０ ３，６０ ４には、一連の検索を構成する各検索毎に、それぞれ、セットパルスＳ３，Ｓ４，Ｓ５，Ｓ６が入力され、センスアンプ５６から出力された論理‘０’又は論理‘１’の信号がそれぞれ格納される。
【００４７】
以上のような構成を備えた連想メモリを用いて、ここでは、
｛（属性ＩＩＩ  にデータＣが存在し）かつ（属性ＩＶにデータＤが存在する）｝
もしくは
｛（属性ＩにデータＡが存在し）かつ（属性ＩＩにデータＢが存在する）｝……（２）
の検索を行なうものとする。
先ず、属性レジスタ１２ １に属性ＩＩＩ  がセットされ、入力レジスタ１２ ２にデータＣがセットされ、属性ＩＩＩ  とデータＣにより１回目の検索が行なわれる。このときには、初回検索タイミング信号Ｓ２が入力される。
【００４８】
すると、メモリワード１１ ｍ＋２とメモリワード１１ ｎ＋２で一致が検出され、フラグレジスタ２４ ｍ＋２とフラグレジスタ２４ ｎ＋２に一致が検出されたことを示す論理‘１’がセットされる。他の全てのフラグレジスタは、もし論理‘１’が格納されていたとしても全て論理‘０’にリセットされる。
このとき、制御線５５に論理‘０’の信号が印加されトランジスタ５９を介して検索線５２がプリチャージされており、フラグレジスタ２４ １，２４ ２，…，２４ ｍ，…，２４ ｎ，…の論理が定まると制御線５５が論理‘１’に変化し、プリチャージが終了するとともにトランジスタ５４ １，５４ ２，５４ ｍ，…，５４ ｎ，…が‘オン’となり、フラグレジスタ２４ １，２４ ２，…，２４ ｍ，…，２４ ｍ，…のいずれかに論理‘１’がセットされていると、トランジスタ５３ １，５３ ２，…，５３ ｍ，…，５３ ｎ，…のうちの、論理‘１’のセットされたフラグレジスタ（上記の場合フラグレジスタ２４ ｍ＋２とフラグレジスタ２４ ｎ＋２）に対応するトランジスタ（上記の場合トランジスタ５３ ｍ＋２とトランジスタ５３ ｎ＋２）が‘オン’となり、検索線５２の電荷がディスチャージされ、センスアンプインバータ５７の出力が論理‘１’となる。このセンスアンプインバータ５７の出力が確定した時点でセットパルスＳ３が入力され、これにより、ヒット列レジスタ６０を構成する、図１の左端のフリップフロップ６０ １に、１回目の検索で一致が検出されたことを示す論理‘１’がセットされる。
【００４９】
次に、属性レジスタ１２ １に属性ＩＶがセットされ、入力レジスタ１２ ２にデータＤがセットされ、属性ＩＶとデータＤにより２回目の検索が行なわれる。このときには、初回検索タイミング信号Ｓ２は入力されない。
この検索では一致は検出されず、全てのフラグレジスタ２４ １，２４ ２，…，２４ ｍ，…，２４ ｎ，…が論理‘０’にリセットされる。すなわち、（２）式の前半の部分、
（属性ＩＩＩ  にデータＣが存在し）かつ（属性ＩＶにデータＤが存在する）…（３）
というデータ群は検出されなかったことになる。
【００５０】
全てのフラグレジスタ２４ １，２４ ２，…，２４ ｍ，…，２４ ｎ，…が論理‘０’にリセットされているため、今度は検査線５２はプリチャージされたままの状態にとどまり、センスアンプインバータ５７からは論理‘０’が出力され、セットパルスＳ４が入力され、ヒット列レジスタ６０の、図示の左から２番目のフリップフロップ６０ ２に論理‘０’が格納される。
【００５１】
次に、属性ＩとデータＡで検索が行なわれ、かつ初回検索タイミング信号Ｓ２が入力され、３つのメモリワード１１ ５，１１ ｍ，１１ ｎで一致が検出されて、それぞれに対応するフラグレジスタ２４ ５，２４ ｍ，２４ ｎが論理‘１’にセットされ、センスアンプインバータ５７から論理‘１’が出力され、セットパルスＳ５の入力を受けて、ヒット列レジスタ６０の、図示の左側から３番目のフリップフロップ６０ ３に論理‘１’がセットされる。
【００５２】
次に属性ＩＩとデータＢで検索が行なわれ、アンド検索であるため、初回検索タイミング信号Ｓ２は入力されない。このとき、２つのメモリワード１１ ｍ＋１，１１ ｎ＋１で一致が検出され、対応するフラグレジスタ２４ ６，２４ ｍ＋１に論理‘１’がセットされる。またこれとともに、フラグレジスタ２４ ５，２４ ｍ，２４ ｎは論理‘０’にリセットされる。また、一致が検出されたことを受けてセンスアンプインバータ５７から論理‘１’が出力され、セットパルスＳ６の入力を受けて、ヒット列レジスタ６０の、図示の右端のフリップフロップ６０ ４に論理‘１’が格納される。
【００５３】
ヒット列レジスタ６０が備えられていない図５に示す連想メモリの場合、フラグレジスタ２４ １，２４ ２，…，２４ ｍ，…，２４ ｎ，…には最終の検索結果しか残らないために、上記の（２）式のような検索では中間の結果を知ることはできない。（２）式の例では、（３）式の後に、
（属性ＩにデータＡが存在し）かつ（属性ＩＩにデータＢが存在する）…（４）
を満足するデータ群が存在するために、図５に示す構成の連想メモリでも最終的に（４）式を満足したことが検出されるが、（４）式が先に来て次に（３）式が来る場合には、図５に示す構成の連想メモリでは、後半の（３）式の検索結果のミスヒットしか検出されないことになる。
【００５４】
これに対し、図１に示す実施例ではヒット例レジスタ６０を備えたため、一連の検索を構成する各回毎の検索の結果が保持され、したがって種々の検索条件に対応することができる。しかも、図１に示すように、連想メモリを構成する全てのメモリワードに跨って１系統だけヒット列レジスタ６０およびそれに付属する回路を備えるだけで済み、連想メモリ全体としては極くわずかな要素の追加にとどめることができる。
【００５５】
尚、上記実施例は、一連の検索として４回の検索を行なうことを例にして図示および説明を行なったが、本発明では、４回の検索を一連の検索とするものに限られないことはもちろん、ヒット列レジスタ６０を構成するフリップフロップとして一連の検索を構成する検索の最大回数以上の数のフリップフロップに備えておき、一連の検索としての検索回数を可変に構成してもよい。
【００５６】
【発明の効果】
以上説明したように、本発明の連想メモリは、複数のフラグレジスタのいずれかにヒットフラグが格納されたか否かを、複数回の検索をそれぞれについて順次格納するヒット列レジスタを備えたため、一連の検索を構成する複数回の各検索毎の中間的な検索結果を、その一連の検索が終了した後にまとめて知ることができ、システムの簡単化、検索連度の向上に寄与する。また、これに伴う回路要素の付加は連想メモリ全体として極くわずかで済む。
【図面の簡単な説明】
【図１】本発明の連想メモリの一実施例の、本発明に特徴的な部分を示した回路図である。
【図２】連想メモリの一例を表わした回路ブロック図である。
【図３】データ拡張機能を備えた連想メモリの一例を示すブロック図である。
【図４】群構造のデータの一例を示す図である。
【図５】連想メモリの一例を示すブロック図である。
【図６】可変長のデータ線を実現する一つの方式を示した模式図である。
【図７】可変のデータ線を実現するもう一つの方式を示した模式図である。
【図８】属性判定回路の一例を示す回路図である。
【符号の説明】
１１＿１，１１＿２，…  メモリワード
１１＿１＿１，１１＿２＿１，…  属性格納部
１１＿１＿２，１１＿２＿２，…  データ格納部
１４＿１，１４＿２，…  一致線
１６  プライオリティエンコーダ
１７  アドレスデコータ
１８＿１，１８＿２，…  ワード線
２０＿１，２０＿２，…  アンドゲート
２１＿１，２１＿２，…  オアゲート
２３＿１，２３＿２，…  第１のフラグレジスタ
２４＿１，２４＿２，…  第２のフラグレジスタ
２５  一致結果ラッチ制御線
３０＿１，３０＿２，…  属性一致線
３１＿１，３１＿２，…  第３のフラグレジスタ
３２＿１，３２＿２，…  データ線
３３＿１，３３＿２，…  第１スイッチ
３４＿１，３４＿２，…  第２スイッチ
５２    検索線
５６    センスアンプ
６０    ビット列レジスタ
【図１】
0003597882.tif 000002
【図２】
0003597882.tif 000003
【図３】
0003597882.tif 000004
【図４】
0003597882.tif 000005
【図５】
0003597882.tif 000006
【図６】
0003597882.tif 000007
【図７】
0003597882.tif 000008
【図８】
0003597882.tif 000009