JP3636382B2

JP3636382B2 - Associative memory

Info

Publication number: JP3636382B2
Application number: JP23734794A
Authority: JP
Inventors: 洋笹間
Original assignee: Kawasaki Microelectronics Inc
Current assignee: Kawasaki Microelectronics Inc
Priority date: 1993-10-04
Filing date: 1994-09-30
Publication date: 2005-04-06
Anticipated expiration: 2020-04-06
Also published as: JPH07153281A

Description

【０００１】
【産業上の利用分野】
本発明は、各データをそれぞれ記憶する複数のメモリワードを備えるとともに、各メモリワードの記憶されたデータと入力された検索データとの一致不一致を検索する機能を備えた連想メモリ（ＡｓｓｏｃｉａｔｉｖｅＭｅｍｏｒｙ，内容アドレス式メモリ；ＣｏｎｔｅｎｔＡｄｄｒｅｓｓａｂｌｅＭｅｍｏｒｙ）に関する。
【０００２】
【従来の技術】
近年、上記のような検索機能を備えた連想メモリが提案されている。ここでは、先ず最初に、連想メモリの構造、機能について説明し、次いで連想メモリの適用分野の例について説明する。
図９は従来の連想メモリの一例を表わした回路ブロック図である。
【０００３】
この連想メモリ１０には、互いに図の横方向に並ぶ複数のメモリセルからなるメモリワード１１ａ，１１ｂ，…，１１ｎが多数備えられている。またこの連想メモリ１０は、検索データが入力されラッチされる検索レジスタ１２を備え、検索レジスタ１２にラッチされた検索データの全部もしくは所定の一部のビットパターンと、各メモリワード１１ａ，１１ｂ，…，１１ｎに記憶されたデータのうち、上記ビットパターンと対応する部分のビットパターンとの一致不一致が比較され、各メモリワード１１ａ，１１ｂ，…，１１ｎのそれぞれに対応して備えられた一致線１４ａ，１４ｂ，…，１４ｎのうちビットパターンが一致したメモリワード１１ａ，１１ｂ，…，１１ｎに対応する一致線１４ａ，１４ｂ，…，１４ｎに論理‘１’の一致信号が出力され、それ以外の一致線１４ａ，１４ｂ，…，１４ｎに論理‘０’の不一致信号が出力される。
【０００４】
ここでは各フラグ線１４ａ，１４ｂ，…，１４ｎにそれぞれ‘０’，‘１’，‘０’，‘０’，‘１’，…，‘０’の信号が出力されたものとする。この信号はプライオリティエンコーダ１５に入力され、このプライオリティエンコーダ１５からは論理‘１’の一致信号が出力された一致線（ここでは一致線１４ｂと一致線１４ｅの２本）のうちの優先度の最も高い最優先一致線に対応するアドレス信号ＡＤが出力される。ここでは、添字のアルファベットが若いほど優先順位が高いものとし、従ってここでは一致線１４ｂが最優先一致線となる。このプライオリティエンコーダ１５から出力された、最優先一致線１４ｂに対応するアドレス信号ＡＤは、必要に応じて、アドレスデコーダ１６に入力される。アドレスデコーダ１６ではこの入力されたアドレス信号ＡＤをデコードして各メモリワード１１ａ，１１ｂ，…，１１ｎのそれぞれに対応して備えられたワード線１７ａ，１７ｂ，…，１７ｎのうちの入力されたアドレス信号ＡＤに対応するいずれか１本のワード線（ここではワード線１７ｂ）にアクセス信号（ここでは論理‘１’の信号）を出力する。これによりアクセス信号の出力されたワード線１７ｂに対応するメモリワード１１ｂに記憶されているデータが出力レジスタ１８に読出される。
【０００５】
上記のように連想メモリ１０は、検索データを用いて多数のメモリワード１１ａ，１１ｂ，…，１１ｎに記憶された内容（データ）を検索し、一致するデータが記憶されたメモリワードのアドレスを得てそのメモリワードに記憶されたデータ全体を読出すことができるメモリである。
図１０は、連想メモリ中の１つのメモリワードを表わした詳細回路図である。
【０００６】
このメモリワード１１は、同一構成のｎ個のメモリセル１１−１，１１−２，…，１１−ｎから構成されている。各メモリセル１１−１，１１−２，…，１１−ｎには、互いの出力が互いの入力に接続された、第１インバータ２０−１，２０−２，…，２０−ｎと第２のインバータ２１−１，２１−２，…，２１−ｎが備えられており、これらのインバータ２０−１，２１−１；２０−２，２１−２；…；２０−ｎ，２１−ｎにより各メモリセル１１−１，１１−２，…，１１−ｎに論理‘１’もしくは論理‘０’の１ビットの情報が記憶される。
【０００７】
また各メモリセル１１−１，１１−２，…，１１−ｎにおいて、第１インバータ２０−１，２０−２，…，２０−ｎの出力はＮチャンネルトランジスタ２２−１，２２−２，…，２２−ｎを介してビット線２３−１，２３−２，…，２３−ｎと接続されており、このトランジスタ２２−１，２２−２，…，２２−ｎのゲートはワード線２４に接続されている。また第２のインバータ２１−１，２１−２，…，２１−ｎの出力はＮチャンネルトランジスタ２５−１，２５−２，…，２５−ｎを介してビットバー線２６−１，２６−２，…，２６−ｎと接続されており、このトランジスタ２５−１，２５−２，…，２５−ｎのゲートもワード線２４に接続されている。さらに各メモリセル１１−１，１１−２，…，１１−ｎは、ビット線２３−１，２３−２，…，２３−ｎとビットバー線２６−１，２６−２，…，２６−ｎとの間をつなぐように互いにシリーズに接続された２つのＮチャンネルトランジスタ２７−１，２８−１；２７−２，２８−２；…；２７−ｎ，２８−ｎが配置されており、これら各２つのトランジスタ２７−１，２８−１；２７−２，２８−２；…；２７−ｎ，２８−ｎのうちの一方のトランジスタ２７−１，２７−２，…，２７−ｎのゲートは第１のインバータ２０−１，２０−２，…，２０−ｎの出力、他方のトランジスタ２８−１，２８−２，…，２８−ｎのゲートは第２のインバータ２１−１，２１−２，…，２１−ｎの出力と接続されている。
【０００８】
また一致線１４には、各メモリセル１１−１，１１−２，…，１１−ｎに対応して１つずつトランジスタ３６−１，３６−２，…，３６−ｎが備えられており、それらのトランジスタ３６−１，３６−２，…，３６−ｎは互いにシリーズに接続され、それらのトランジスタ３６−１，３６−２，…，３６−ｎの各ゲートは、各２つのトランジスタ２７−１，２８−１；２７−２，２８−２；…；２７−ｎ，２８−ｎの中点と接続されている。
【０００９】
またこの一致線１４にはもう１つのトランジスタ３６−０がシリーズに接続されており、一致線１４の図１０の左端はこのトランジスタ３６−０を介して接地されている。またこのトランジスタ３６−０のゲートは制御線３０に接続されている。
一致線１４の、図１０の右端にはセンス用インバータ３１が配置され、このインバータ３１の出力からは一致線１４がさらに延び、図９に示すプライオリティエンコーダ１５に接続されている。
【００１０】
またこのインバータ３１の入力と電源Ｖ_DDとの間には２つのＰチャンネルトランジスタ３２，３３が配置されており、これら２つのトランジスタ３２，３３のうちの一方のトランジスタ３２のゲートは制御線３０と接続され、他方のトランジスタ３３のゲートはインバータ３１の出力と接続されている。
このような構造のメモリワード及びその周辺回路を備えた連想メモリにおいて、一致検索は以下のようにして行なわれる。
【００１１】
メモリセル１１−１には、論理‘１’の情報が記憶されているものとする。即ちこの場合第１のインバータ２０−１の出力側が論理‘１’、第２のインバータ２１−１の出力側が論理‘０’の状態にある。
このメモリセル１１−１に対して論理‘１’の検索が行なわれるものとする。即ち、ビット線２３−１が論理‘１’、ビットバー線２６−１が論理‘０’とされる。ワード線２４は論理‘０’のままの状態に保持されている。この場合トランジスタ２７−１のゲートには論理‘１’の電圧が印加され、ビット線２３−１の論理‘１’の信号がトランジスタ３６−１のゲートに印加され、これによりトランジスタ３６−１が‘オン’状態となる。即ちメモリセル１１−１に記憶されたビット情報とビット線２３−１、ビットバー線２６−１を経由して入力された検索データ中のビット情報が一致する場合に、対応するトランジスタ３６−１が‘オン’状態となる。
【００１２】
また、メモリセル１１−２には論理‘０’の情報が記憶されているものとする。この場合第１のインバータ２０−２の出力側が論理‘０’、第２のインバータ２１−２の出力側が論理‘１’の状態にある。
このメモリセル１１−２に対してやはり論理‘１’の検索が行なわれるものとする。即ち、ビット線２３−２が論理‘１’、ビットバー線２６−２が論理‘０’とされる。この場合、トランジスタ２８−２を経由して論理‘０’の状態にあるビットバー線２６−２の信号がトランジスタ３６−２のゲートに印加され、したがってこのトランジスタ３６−２は‘オフ’状態にととどまることになる。即ち不一致の場合、一致線１４にプリチャージされていた電荷はディスチャージされない。
【００１３】
また、マスクをかけたビットについては、メモリセル１１−ｎに示すように、ビット線２３−ｎ、ビットバー線２６−ｎの双方とも論理‘１’とされる。この場合このメモリセル１１−ｎに論理‘１’の情報が記憶されているか論理‘０’の情報が記憶されているかに応じてトランジスタ２７−ｎもしくはトランジスタ２８−５のいずれかが‘オン’状態となり、これによりいずれの場合もトランジスタ３６−５が‘オン’状態になる。すなわちそのメモリセルについては、記憶された情報と検索の情報とが一致しているものとみなされる。
【００１４】
検索にあたっては制御線３０が先ず論理‘０’となり、トランジスタ３２が‘オン’状態となってインバータ３１の入力側の一致線１４がプリチャージされ、その後制御線３０が論理‘１’となり、トランジスタ３２が‘オフ’状態となってプリチャージが停止するとともにトランジスタ３６−０が‘オン’状態となる。
【００１５】
このとき、メモリセルに記憶された情報と入力された検索の情報がこのメモリワード１１を構成する全てのメモリセルにわたって一致している（上述したようにマスクされたビットは一致とみなす）場合、トランジスタ３６−１，３６−２，…，３６−ｎの全てが‘オン’状態となり一致線１４にプリチャージされた電荷がディスチャージされ、インバータ３１から論理‘１’の信号が出力される。
【００１６】
尚、図１０に示す連想メモリのメモリ構造は一例に過ぎず、種々の構造のものが提案されている（例えば特願平５−２１６４２４号参照）。
次に、連想メモリの適用の一例として、ＬＡＮ（ＬｏｃａｌＡｒｅａＮｅｔｗｏｒｋ）への適用例について説明する。
図１１は、ＬＡＮの一例を示した図である。
【００１７】
図１１（Ａ）に示すように２つの通信回線ＬＡＮ１，ＬＡＮ２に、それぞれ複数の端末Ａ〜Ｇ，Ｔ〜Ｚが接続され、これにより２つの通信綱が構成されているものとする。通信回線ＬＡＮ１，ＬＡＮ２のトラフィック量（その通信回線を流れるデータの量；その通信回線の混雑度）は、それぞれ’１０’であるとする。これら２つの通信回線を互いに接続する必要が生じた場合に、図１１（Ｂ）に示すように図１１（Ｂ）に示すように単純に接続すると、通信回線ＬＡＮ１，ＬＡＮ２のトラフィック量は２０となり、極めて混雑し、各端末間がなかなか接続されず、待ち時間、空き時間が増大してしまうという結果を招く。
【００１８】
そこで通常は、図１１（Ｃ）に示すように２つの通信回線ＬＡＮ１，ＬＡＮ２の中間に、これらの通信回線ＬＡＮ１，ＬＡＮ２のうちの一方から発信されたデータを他方に伝送するか否かのフィルタリングを行なうブリッジを接続する。このブリッジを接続した場合、このブリッジを通過するデータのトラフィック量、すなわち２つの通信綱に跨るデータの授受についてのトラフィック量を１とすると、各通信回線ＬＡＮ１，ＬＡＮ２内部でのトラフィック量１０とを合わせ、各通信回線ＬＡＮ１，ＬＡＮ２のトラフィック量はそれぞれ１１となり、２つの通信回線ＬＡＮ１，ＬＡＮ２を単純に接続した図１１（Ｂ）の場合と比べトラフィック量は大きく低下する。ここでは２つの通信回線ＬＡＮ１，ＬＡＮ２の接続について説明したが、１つのブリッジに多数の通信回線を接続すると、この差はさらに顕著となる。
【００１９】
図１２は、ブリッジの機能説明図である。
ブリッジは内部にメモリを持ち、最初は全て空白の状態から出発し、例えば通信回線ＬＡＮ１の端末Ａからデータが送信されると、ＬＡＮ１側からそのデータが送信されてきたことを受けて、端末Ａが通信回線ＬＡＮ１に接続されていることを学習する。この学習は、概念的には、ブリッジ内部のメモリに、通信回線ＬＡＮ１，ＬＡＮ２それぞれについてテーブル１，テーブル２を持ち、通信回線ＬＡＮ１に対応するテーブル１に端末Ａを書込むことによって行われる。端末Ａから送信されたデータの受信先が、端末Ａと同じＬＡＮ１側の通信網内にあるか否かは端末Ａについてのみ学習した時点では判らずしたがってこの時点は無条件にブリッジを通過させる。
【００２０】
このような学習を繰り返すことにより、ブリッジ中に図１２に示すようなテーブル１，テーブル２が作成され、これらが作成された後は、例えば図示のように、発信先が端末Ｂ（ＬＡＮ１側）、受信先が端末Ｘ（ＬＡＮ２側）のデータは、ブリッジで、それら端末Ｂ，Ｘがブリッジを跨っていることを認識してブリッジを通過させ、発信先，受信先がいずれもＬＡＮ１側の端末Ａ，Ｅの場合は、それらの端末Ａ，Ｅがブリッジから見て同じ側の通信網にあることを認識してブリッジでデータの通過を遮断する。これにより、前述したように、トラフィック量の低減化が図られる。
【００２１】
このブリッジに備えられるメモリとして連想メモリを採用すると、処理の高速化が図られる。例えば各端末Ａ〜Ｇ，Ｔ〜Ｚの情報と、それらの各端末がテーブル１に属するか（ＬＡＮ１側に接続されているか）、あるいはテーブル２に属するか（ＬＡＮ２側に属するか）という情報を連想メモリに記憶し、データを通過させるか否かの判断にあたっては、例えば受信先が端末Ｘであった場合、そのＸを検索データとして検索してそのＸがテーブル２（ＬＡＮ２）に属する端末であることを認識し、これに基づいてデータを通過させるか否かを定めることができる。
【００２２】
これに対し、ブリッジに通常のＲＡＭメモリ等を備えた場合は、メモリされたデータを１つずつ読み出してはそのデータが端末Ｘのデータであるか否かを逐次比較により検索する必要があり、ブリッジを通過させるか遮断するかを定めるために多大な時間を要することとなる。
【００２３】
【発明が解決しようとする課題】
上記のように、連想メモリは、例えばＬＡＮネットワーク等に好適に用いられるが、例えば端末Ａからデータが送信されてきたとき、それを受けて端末Ａがブリッジ内のメモリに既に登録されているかどうか確認し、未登録の場合は登録を行なう必要がある。このように、従来は、既に登録されているかどうかの確認と、未登録の場合の登録との２つのステップを必要としており、このことが、ブリッジの動作をさらに高速化する際の妨げの１つとなっている。
【００２４】
本発明は、上記事情に鑑み、未登録データの登録を高速に行なうことのできる連想メモリを提供することを目的とする。
【００２５】
【課題を解決するための手段】
上記目的を達成する本発明の第１の連想メモリは、
各データをそれぞれ記憶するメモリワードと、そのメモリワードに対応して備えられた、入力された検索データの全部もしくは所定の一部のビットパターンとそのメモリワードに記憶されたデータのうち上記ビットパターンと対応する全部又は一部分のビットパターンとの一致不一致を検出する一致検出回路とを備えた連想メモリにおいて、
前記一致検出回路のいずれからも、一致が検出されたことを示す一致信号が出力されなかった場合に、前記検索データを、上記メモリワードのうち検索の対象とされる有効データが記憶されておらずしたがって上書きが許容される空き状態にあるメモリワードの１つに記憶させるデータ追記回路を備えたことを特徴とするものである。
【００２６】
ここで、上記本発明の第１の連想メモリにおいて、上記データ追記回路は、
（１）上記のメモリワードに対応して備えられた、そのメモリワードが、有効データが記憶された記憶状態にあるメモリワードであるか、あるいは空き状態にあるメモリワードであるかを示すフラグが記憶されるフラグレジスタ
（２）空き状態にあるメモリワードの中から１つのメモリワードを選択してその１つのメモリワードに検索データを書き込む検索データ書込回路
（３）上記一致検出回路のいずれからも一致信号が出力されなかった場合に、上記１つのメモリワードに対応するフラグレジスタに、記憶状態を示すフラグを記憶させるフラグ変更回路
を備えたものであってもよい。
【００２７】
また、上記目的を達成する本発明の第２の連想メモリは、
複数の格納データの集合からなる１つのデータ群を構成する複数のデータを、各データ毎に記憶する複数のメモリワードからなるメモリワード群を複数備え、検索データが入力される毎に、入力された検索データの全部もしくは所定の一部のビットパターンと上記メモリワードに記憶されたデータのうち上記ビットパターンと対応する全部又は一部分のビットパターンとの一致検索を行ない、１回もしくは連続する複数回からなる所定回数の一致検索全てにおいて、入力された検索データの全部もしくは各所定の一部のビットパターンと、同一のメモリワード群内に記憶されたデータのうち上記ビットパターンと対応する全部又は一部分との一致が検出されたことをもって、上記所定回数入力された検索データに対応するデータ群の存在を検出する連想メモリにおいて、
上記所定回数の一致検索の間、１回の検索毎に、入力された検索データを、検索の対象とされる有効データ群が記憶されておらず、したがって上書きが許容される空き状態にあるメモリワード群の中から選択された１つのメモリワード群内のいずれかのメモリワードに書き込むデータ書込回路を備えたことを特徴とするものである。
【００２８】
ここで、上記本発明の第２の連想メモリにおいて、
（４）上記メモリワード群それぞれに対応して備えられた、対応するメモリワード群が、有効データ群が記憶された記憶状態にあるメモリワード群であるか、あるいは空き状態にあるメモリワード群であるかを示すフラグが記憶されるフラグレジスタ
（５）上記所定回数の一致検索の結果、所定回数入力された検索データに対応するデータ群が検出されなかった場合に、上記１つのメモリワード群に対応するフラグレジスタに、記憶状態を示すフラグを記憶させるフラグ変更回路
を備えることが好ましい。
【００２９】
あるいは、上記本発明の第２の連想メモリにおいて、
（６）上記メモリワード群それぞれに対応して備えられた、対応するメモリワード群が、前記有効データ群が記憶された記憶状態にあるメモリワード群であるか、あるいは前記空き状態にあるメモリワード群であるかを示すフラグが記憶されるフラグレジスタ
（７）外部から入力された所定の指示信号を受けて、上記１つのメモリワード群に対応するフラグレジスタに、記憶状態を示すフラグを記憶させるフラグ変更回路
を備えてもよい。
【００３０】
【作用】
上記本発明の第１の連想メモリは、検索によって一致検出が行なわれなかったことを受けて検索データをそのまま格納してしまうものであるため、従来のように、検索動作と、その検索により一致が検出されなかった場合にデータを書き込む動作との２回のステップは不要となり、処理の高速化が図られることになる。
【００３１】
ここで、特公昭６１−３１５５８号公報に、本発明と関連した技術が提案されているため、そこに提案された技術と本発明との相違を説明する。
連想メモリを構成する多数のメモリワードは、常に全てのメモリワードに検索の対象となるデータが記憶されている訳ではなく、それらのメモリワードの一部は有効なデータが記憶されていない空きの状態にあったり、その空きの状態にあるメモリワードに新たに有効データを書き込んだりすることがある。この場合、このメモリワードが空きの状態にあるか否かを外部で管理しておくのは煩雑であることから、上記の文献には、各メモリワードに対応してそのメモリワードに有効なデータが記憶されているかそれともそのメモリワードが空きの状態にあるかを示すフラグを各メモリワードに対応させて記憶しておき、新たな有効データを書き込む場合に連想メモリ自体で空きの状態にあるメモリワードを見つけてそのメモリワードに有効データを書き込むという技術が提案されている。
【００３２】
そこに提案された技術は、空き状態にあるメモリワードを外部で管理する必要をなくすためのものであって、未登録のデータの登録においては、やはり、そのデータが既登録が未登録かの検索と、未登録の場合の登録との２つのステップを要するものである。
本発明の第２の連想メモリは、データ群を記憶しておくメモリワード群を有し、検索データを入力して検索を行なうという動作を所定回数行なって対応するデータ群の存在を検出する連想メモリに関するものである。
【００３３】
このような連想メモリにおいて、例えば１００個のデータからなるデータ群を格納しておいて、検索データを入力して検索を行なうという動作を１００回繰り返して所望のデータ群を検出する場合、従来考えられているデータ群の存在を検出するタイプの連想メモリを用いると、１００回の検索を行なった結果所望のデータ群が見つからなかった場合、次に検索データを１００回書き込んではじめて新たな有効なデータ群が登録されることになる。
【００３４】
これに比較し、本発明の第２の連想メモリでは、１回の検索毎に、検索データが、空き状態にあるメモリワード群に書き込まれるため、１００回の検索を行なった結果、所望のデータ群が見つからなかった場合、既に１回の検索毎に検索データが書き込まれているため、この検索データが書き込まれたメモリワード群を次回以降の検索に用いるか否かを定めるだけで済み、データ書き込みの手間が大幅に低減され、処理の高速化が図られることになる。
【００３５】
検索データが書き込まれたメモリワード群を次回以降の検索に用いるか否かは、例えば上記（４）、上記（６）のフラグレジスタを備えておき、そのフラグレジスタに記憶されたフラグを書き換えることによって定めることができる。
このフラグの書き換えは、上記（５）のフラグ変更回路を備えることにより、所定回数の検索で所望のデータ群が検出されなかったことを受けて自動的に書き換えを行うように構成することがより好ましいが、上記（７）のフラグ変更回路を備え、外部からフラグ書換えの指示を入力するように構成してもよく、この場合であっても、従来と比べ処理の大幅な高速化を図ることができる。
【００３６】
【実施例】
以下、本発明の実施例について説明する。
図１は、本発明の第１の連想メモリの一実施例の特徴部分を示す回路図である。前述した従来例で参照した図面における構成要素に対応する構成要素には、それらの図面に付した番号と同一の番号を付して示す。
【００３７】
この図１では、メモリワード１１や一致線１４の構成は略示されている。この各メモリワード１１に対応して各フラグレジスタ５１が備えられており、このフラグレジスタ５１には、対応するメモリワード１１に、検索の対象となる有効ワードが記憶されている場合に’０’、検索の対象から除外され、したがって上書きを許容する無効のデータが記憶されている場合（ここではこれを、対応するメモリワード１１が「空き状態」に有る、と称する）に’１’の空きフラグが記憶される。ここでは、各フラグレジスタ５１には、図示のように、’０’，’０’，…，’１’が格納されているものとする。各フラグレジスタ５１のＱ出力は、対応して備えられた各複数選択分離回路５２に入力される。この選択分離回路５２は互いに直列的に接続されており、その接続により、この図の上方ほど優先度が高くなっており、’１’が格納されたフラグレジスタ５１のうち、優先度の最も高いフラグレジスタ５１に対応する複数選択分離回路５２のみから信号’１’が出力される。ここでは、図１の一番下に図示されたフラグレジスタ５１が最も優先度が高く、したがってそれに対応する一番下に図示された複数選択分離回路５２から’１’が出力されているものとする。
【００３８】
図２は、複数選択分離回路５２の回路例を示した図である。
図２（Ａ）に示す複数選択分離回路５２は、図示のように接続された、一方の入力が反転されるアンドゲート５２１と、オアゲート５２２から構成されている。また、図示の一番上の複数選択分離回路５２を構成するオアゲート５２２の一方の入力はグラウンドＧＮＤに接地されている。
【００３９】
この構成の複数選択分離回路５２では図示の上方ほど高い優先度を有しており、複数のフラグレジスタ５１に空きフラグ‘１’が格納されている場合に、それら複数のフラグレジスタ５１のうち最も高い優先度を有するフラグレジスタ５１に対応する複数選択分離回路５２のアンドゲート５２１から‘１’が出力される。
【００４０】
また、図２（Ｂ）に示す複数選択分離回路５２’は、図示のようにインバータ５２３、Ｎチャンネルトランジスタ５２４，Ｐチャンネルトランジスタ５２６、排他論理和（エクスクルーシブオア）ゲート５２５から構成されている。また各複数選択分離回路５２’を構成するＰチャンネルトランジスタ５２６の一端は電源Ｖ_DDに接続され、図示の一番上の複数選択分離回路５２’を構成する排他論理和ゲート５２５の一方の入力はグラウンドＧＮＤに接地されている。
【００４１】
この図２（Ｂ）に示す複数選択分離回路５２’も、図２（Ａ）に示す複数選択分離回路５２と同様に、図示の上方ほど高い優先度を有しており、複数のフラグレジスタ５１に空きフラグ‘１’が格納されている場合に、それら複数のフラグレジスタ５１のうち最も高い優先度を有するフラグレジスタ５１に対応する複数選択分離回路５２’の排他論理和ゲート５２５から‘１’が出力される。
【００４２】
尚、この図２（Ａ）もしくは図２（Ｂ）に示す複数選択分離回路の後段にエンコーダを接続すれば、図９に示すプライオリティエンコーダ１５が構成される。
上記のようにして、図１の１番下に図示されたフラグレジスタ５１が、空きフラグ‘１’が格納された第２のフラグレジスタ５１の中の最優先のものであった場合、それに対応する複数選択分離回路５２から‘１’が出力され、対応するアンドゲート６７に入力される。またこのアンドゲート６７の入力にはワード線活性化タイミング信号線６８も接続されている。
【００４３】
ここで、ビット線ドライブ回路７０によりビット線２３−１，…，２３−ｎ、およびビットバー線２６−１，…，２６−ｎに検索データをのせて検索を行なう。その結果、その検索データと図示の最上段のメモリワード１１に記憶されたデータとが一致したものとすると、最上段の一致線１４が’１’となり、フラグレジスタ５１の出力は’０’であるためアンドゲート５３の出力が’１’となる。ここではアンドゲート５３の出力から延びる線も一致線１４０と称する。全てのメモリワード１１に対応する一致線１４０は全体一致検出回路７１に延び、さらに、従来の場合の一致線１４に代わり、図９に示すプライオリティエンコーダ１５に延びている。フラグレジスタ５１に空きフラグ’１’が格納されている場合は、そのフラグレジスタ５１に対応するメモリワード１１で一致が生じても、一致線１４の’１’信号はアンドゲート５３でストップされ、そのアンドゲート５３の出力側の一致線１４０は’０’のままにとどまる。すなわち、そのメモリワード１１は検索には寄与しないことになる。
【００４４】
全体一致検出回路７１では、各一致線１４０から入力された信号のオア演算を行い、これにより、１つでも一致があったか、もしくは全てのメモリワード１１にわたって不一致であったかが検出され、追記制御回路７２に入力される。
追記制御回路７２では、先ず、いずれかのメモリワード１１で一致が生じたか否かにはかかわりなく、ビット線２３−１，…，２３−ｎ、ビットバー線２６−１，…，２６−ｎに検索データをのせて検索しているときに、ワード線活性化タイミング信号線６８に信号’１’をのせる。すると、’１’の信号を出力している、図示の１番下の複数選択分離回路５２に対応するアンドゲート６７の出力が’１’となり、対応するワード線２４が’１’となって、図示の１番下のメモリワード１１に検索データが書き込まれる。この検索データが書き込まれるタイミングは、検索と同時であり、したがってその検索において一致が生じたか否かとは無関係である。
【００４５】
その後、上述のように、全体一致検出回路７１においていずれかのメモリワード１１で一致が生じたか、あるいは全てのメモリワード１１にわたって不一致であったかが検出されて追記制御回路７２に入力される。追記制御回路７２ではいずれかのメモリワード１１で一致が生じていたときはその後は何も行なわない。すなわち、図示の一番下のメモリワード１１には検索データが上書きされたものの、それに対応するフラグレジスタ５１には依然として空きフラグ’１’が格納されており、一番下のメモリワード１１は依然として検索に寄与しない空き状態にとどまることになる。
【００４６】
一方、全体一致検出回路７１で全てのメモリワード１１にわたって不一致が検出された場合、追記制御回路７２は以下のように動作する。すなわち、フラグレジスタ５１に接続された空きフラグデータ線６６に論理’０’の信号を与え、その状態で空きフラグクロック信号線６５に’１’のクロックパルスを与える。すると図示の１番下のメモリワード１１のワード線２４は’１’となっており、その’１’の信号が信号線６０を経由して一番下のアンドゲート６１に入力されているため、空きフラグクロック信号線６５に与えられたクロックパルスはそのアンドゲート６１を通過し、一番下のフラグレジスタ５１に入力される。これにより、一番下のフラグレジスタ５１に対応するメモリワード１１に検索の対象となる有効なデータが格納されていることを表す’０’が格納される。
【００４７】
複数選択分離回路５２では、図示の１番下のフラグレジスタ５１に’０’が格納されたことに伴い、そのフラグレジスタ５１以外の、空きフラグ’１’が格納されているフラグレジスタ５１中から最も優先度の高いものが検出されることになる。
次に、本発明の第２の連想メモリの実施例について説明するが、本発明の第２の連想メモリの思想が好適に適用される、データ群を格納しておいてデータ群の検索を行なう連想メモリ自体が未だ公知ではないため（特願平５−２４８１２１号参照）、ここでは先ずそのベースとなる連想メモリ自体について説明し、次いで、本発明の第２の連想メモリの実施例について説明する。
【００４８】
図３は、群構造を成すデータの一例を示した図である。
この図３には、それぞれ属性Ｉ，ＩＩ，ＩＩＩ，ＩＶが付された４つのデータがセットとなって１つのデータ群を構成しているデータ構造が示されている。データ群および属性の概念を明確にするために一例を挙げると、例えば各群番号１，２，３，４，…毎の各データ群は各個人に属するデータであり、属性Ｉはその人の氏名，属性ＩＩはその人の生年月日、属性ＩＩＩは住所、……等を示している。
【００４９】
このように各属性Ｉ，ＩＩ，ＩＩＩ，ＩＶが付された複数のデータからなるデータ群を連想メモリに格納しておいて検索を行う場合に、例えば群番号１のデータを検索する場合を例に説明すると、データ‘Ａ’の検索とデータ‘Ｂ’の検索をこの順に行って一致するデータ群の残りのデータ‘Ｃ’，‘Ｄ’を読み出すことだけではなく、例えばデータ‘Ａ’の検索とデータ‘Ｄ’の検索を行って残りのデータ‘Ｂ’，‘Ｃ’を読み出したい場合や、データ‘Ｂ’の検索を先に行い、次にデータ‘Ａ’の検索を行いたい場合があり、それら多様な検索を行なうことのできる連想メモリが考えられている。
【００５０】
尚、ここでは、後の説明の都合上、群番号ｎとｎ＋１は、有効なデータ群が記録されていない空き状態にあるものとする。
図４は、図３に示すような群構造のデータを取り扱うのに好適な連想メモリの一例を示すブロック図である。
各メモリワード１１＿１，１１＿２，…から延びる各一致線１４＿１，１４＿２，…，は、各アンドゲート２０＿１，２０＿２，…の一方の入力端子に接続されている。また各アンドゲート２０＿１，２０＿２，…の他方の入力端子には各オアゲート２１＿２，２１＿３，…の出力端子が接続されており、各オアゲート２１＿２，２１＿３，…の一方の入力端子は、初回検索制御線２２に接続されている。
【００５１】
各アンドゲート２０＿１，２０＿２，…の出力端子は各第１のフラグレジスタ２３＿１，２３＿２，…のデータ入力端子に接続され、各第１のフラグレジスタ２３＿１，２３＿２，…の出力端子は各第２のフラグレジスタ２４＿１，２４＿２，…の入力端子に接続されている。各第２のフラグレジスタ２４＿１，２４＿２，…の出力端子は、図９に示すプライオリティエンコーダ１５（図４では図示省略）に接続されるとともに、各第１のスイッチ３３＿１，３３＿２，…を介して、図３に示す各データ群を格納する各メモリワード群毎に備えられたデータ線３２＿１，３２＿２，…に接続されている。
【００５２】
第１のフラグレジスタ２３＿１，２３＿２，…と第２のフラグレジスタ２４＿１，２４＿２，…には、ともに、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１が入力され、その一致結果ラッチ信号Ｓ１により、各データ入力端子から入力された入力データがラッチされるが、第１のフラグレジスタ２３＿１，２３＿２，…には、一致結果ラッチ信号Ｓ１の立ち上がりａの時点における入力データがラッチされ、第２のフラグレジスタ２４＿１，２４＿２，…には、一致結果ラッチ信号Ｓ１の立ち下がりｂの時点−の入力データがラッチされる。
【００５３】
各メモリワード１１＿１，１１＿２，…は、属性を格納する属性格納部１１＿１＿１，１１＿２＿１，…とデータを格納するデータ格納部１１＿１＿２，１１＿２＿２，…とで構成されており、各メモリワード１１＿１，１１＿２，…には、互いに対応する属性とデータとのペアからなる格納データがそれぞれ格納されている。ここでは、図示のように、各メモリワード１１＿１，１１＿２，１１＿３，１１＿４には、それぞれ、図３に示す群番号１に属する、属性Ｉ，データ‘Ａ’、属性ＩＩ，データ‘Ｂ’、属性ＩＩＩ，データ‘Ｃ’、属性ＩＶ，データ‘Ｄ’が格納されている。また各メモリワード１１＿５，１１＿６，…には、それぞれ、図３に示す群番号２に属する、属性Ｉ，データ‘Ｃ’、属性ＩＩ，データ‘Ｆ’、……が格納されている。また検索にあたっては、属性とデータとのペアからなる参照データＲＥＦ＿ＤＡＴＡが入力される。
【００５４】
各メモリワード１１＿１，１１＿２には、そこに記憶された格納データ（属性及びデータの双方）が、入力された参照データ（属性及びデータの双方）と一致しているときに一致信号が出力される従来の一致線１４＿１，１４＿２，…のほか、属性のみの一致不一致の信号が出力される属性一致線３０＿１，３０＿２，…が備えられている。尚、属性のみの一致も、属性及びデータの双方の一致も、従来の一致検出回路と同様に構成され、従来の一致検出回路は連想メモリの分野において極めて一般的な技術であるため、ここでの図示および説明は省略する。各メモリワード１１＿１，１１＿２に対応して第３のフラグレジスタ３１＿１，３１＿２，…が備えられており、各属性一致線３０＿１，３０＿２，…は対応する第３のフラグレジスタ３１＿１，３１＿２，…のデータ入力端子に延びている。また、この実施例の連想メモリには、前述したように図３に示す各データ群に属する各データが格納されたメモリワードからなるメモリワード群それぞれについて１本ずつデータ線３２＿１，３２＿２，…が備えられており、またデータ線３２＿１，３２＿２，…と各第２のフラグレジスタ３１＿１，３１＿２，…の出力端子との間には各第１のスイッチ３３＿１，３３＿２，…が備えられている。これらの第１のスイッチ３３＿１，３３＿２，…は具体的にはトランジスタ等を用いて構成される。後述する他のスイッチについても同様である。各第１のスイッチ３３＿１，３３＿２，…は、対応する各第３のフラグレジスタ３１＿１，３１＿２，…に論理‘１’の信号がラッチされているときに導通され、論理‘０’の信号がラッチされているときには遮断される。各第３のフラグレジスタ３１＿１，３１＿２，…は、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１の立ち下がりｂのタイミングで、対応する属性一致線３０＿１，３０＿２，…の信号をラッチする。
【００５５】
またデータ線３２＿１，３２＿２，…と各オアゲート２１＿１，２１＿２，…の入力端子との間に各第２のスイッチ３４＿１，３４＿２，…が備えられており、これら各第２のスイッチ３４＿１，３４＿２，…は、対応する属性一致線３０＿１，３０＿２，…の信号により、その信号が一致を表わす論理‘１’のときに導通状態、不一致を表わす論理‘０’の時に遮断状態となるように制御される。
【００５６】
以上のように構成された連想メモリにおいて、一致検索は以下のようにして行われる。
各検索データを単独で検索する際は、参照データＲＥＦ＿ＤＡＴＡを入力して検索を行う際に、初回検索制御線２２に初回検索タイミング信号Ｓ２を出力する。ここでは、参照データＲＥＦ＿ＤＡＴＡとして属性ＩＩおよびデータ‘Ｂ’を入力したものとすると、属性ＩＩおよびデータ‘Ｂ’が格納されたワードメモリ１１＿２に対応する一致線１４＿２に論理‘１’の一致信号が出力されてアンドゲート２０＿２に入力され、また、これとともに初回検索タイミング信号Ｓ２がオアゲート２１＿２を経由してアンドゲート２０＿２に入力されるため、アンドゲート２０＿２から論理‘１’の信号が出力される。またこのとき、他の一致線１４＿１；１４＿３，１４＿４，…には論理‘０’の信号が出力されるため、それに対応する他のアンドゲート２０＿１；２０＿３，２０＿４，…からは論理‘０’の信号が出力される。
【００５７】
アンドゲート２０＿２から出力された論理‘１’の信号は、一致結果ラッチ制御線２５に出力された一致結果ラッチ信号Ｓ１の立ち上がりａのタイミングで第１のフラグレジスタ２３＿２にラッチされ、それに引き続くの一致結果ラッチ信号Ｓ１の立ち下がりｂのタイミングで第２のフラグレジスタ２４＿２にラッチされる。
【００５８】
また第１のフラグレジスタ２３＿２および第２のフラグレジスタ２４＿２に論理‘１’の信号がラッチされる各タイミングで、他の第１フラグレジスタ２３＿１；２３＿３，２３＿４，…、および他の第２のフラグレジスタ２４＿１；２４＿３，；２４＿４，…には論理‘０’の信号がラッチされる。
このようにして各第２のフラグレジスタ２４＿１，２４＿２，２４＿３，…にラッチされた論理‘０’，‘１’，‘０’，…の信号が図９に示すプライオリティエンコーダ１５に入力され、ワードメモリ１１＿２のアドレス信号ＡＤが得られる。
【００５９】
次に複数回の連続したデータ検索を行なう場合について説明する。複数回の連続した検索を行う場合における第１回目の検索については、上述の単独のデータ検索の動作と同じであるが、この第１回目のデータ検索では、上記の動作に加えて、第２回目のデータ検索の準備として、以下の動作が行なわれる。
上記の第１回目のデータ検索の際、属性の一致を受けてメモリワード１１＿２に対応する属性一致線３０＿２に論理‘１’の信号が出力され、これにより、対応する第３のフラグレジスタ３１＿２にも論理‘１’の信号がラッチされ、対応する第１のスイッチ３３＿２がオンし、対応する第２のフラグレジスタ２４＿２に格納された、属性及びデータ双方の一致を表わす論理‘１’の信号がデータ線３２＿１に出力される。またこれとともに、対応する第２のスイッチ３４＿２もオンするが、第１回目の検索においてはこれは無用の動作である。
【００６０】
次に、属性ＩＶとデータ‘Ｄ’からなる参照データＲＥＦ＿ＤＡＴＡを入力して検索を行うものとする。このときは、初回検索制御線２２は論理‘０’に保持されている。このとき、属性の一致を受けてメモリワード１１＿４に対応する属性一致線３０＿４に論理‘１’の信号が出力され、これにより対応する第２のスイッチ３４＿４がオンし、データ線３２＿１に出力されていた、メモリワード１１＿２に対応する第２のフラグレジスタ２４＿２の論理‘１’の信号がオアゲート２１＿４を経由してアンドゲート２０＿４に入力される。このため、メモリワード１１＿４で属性ＩＶとデータ‘Ｄ’の双方の一致が検出されて一致線１４＿４に論理‘１’の一致信号が出力されると、一致結果ラッチ制御線２５に出力される一致結果ラッチ信号Ｓ１により、対応する第１および第２のフラグレジスタ２３＿４，２４＿４に論理‘１’の信号がラッチされる。またこのとき、属性一致線３０＿４に出力された論理‘１’の信号が、対応する第３のフラグレジスタ３１＿４にラッチされ、対応する第１のスイッチ３３＿４がオンし、第２のフラグレジスタ２４＿４の論理‘１’の信号がデータ線３２＿１に出力される。またこの２回目の検索では、メモリワード１１＿２に対応する属性一致線３０＿２には属性の不一致を表わす論理‘０が出力されるため、対応する第３のフラグレジスタ３１＿２には‘０’が格納され、メモリワード１１＿２に対応する第１のスイッチ３３＿２はオフする。
【００６１】
これにより、メモリワード１１＿４に対応する第２のフラグレジスタ２４＿４の論理‘１’の信号がプライオリティエンコーダ１５（図９参照）に入力され、メモリワード１１＿４のアドレスが得られることになるが、メモリワード１１＿４には属性ＩＶが格納されていることは予め分かっており、同一群内の、例えば属性ＩＩＩのデータを読み出したいときは、得られたアドレスから１を引いてメモリワード１１＿３のアドレスを求め、そのアドレスをアドレスデコーダ１６に入力してメモリワード１１＿３の内容を読み出せばよい。尚、２回目の検索時に、属性ＩＶとデータ‘Ｄ’とからなる参照データに代わり、例えば属性ＩＶとデータ‘Ｂ’とからなる参照データで検索が行われた場合、メモリワード１１＿４については、属性は一致するため第２のスイッチ３４＿４がオンし、データ線３２＿１に出力されている論理‘１’の信号が取り込まれるが、データが異なるため一致線１４＿４には不一致を表わす論理‘０’が出力され、第１及び第２のフラグレジスタ２３＿４，２４＿４には一致が検出されなかったことを示す論理‘０’がラッチされる。また、データ‘Ｂ’が一致するメモリワード１１＿２については属性が一致せず、したがって属性及びデータの双方も一致しない。
【００６２】
以上のようにして、図４に示す実施例では、同一の群内においては、互いに離れたメモリワードに記憶されたデータであっても、もしくはデータの順序を逆にして検索した場合であっても、検索を行うことができる。
ここで、上記実施例におけるデータ線３２＿１，３２＿２，…，は、１つの群に属するデータの数が予め定まっているものとしてその長さが固定されたものであるが、このように固定長のデータ線を備えると、１つの群に属するデータの数の最大を見積もり、最大のデータ数に対応した長さのデータ線を備える必要がある。これではその最大よりも少ない数のデータによりデータ群が構成される場合に無駄なメモリワードが発生することになる。そこで、１つの群に属するデータの数に合せてデータ線を可変長とすることが好ましい。
【００６３】
図５は、可変長のデータ線を実現する一つの方式を示した模式図である。
データ線３２が複数のメモリワード１１＿１，１１＿２，１１＿３，…に亘って延び、そのデータ線３２には、最上端のメモリワード１１＿１を除く他のメモリワード１１＿２，１１＿３，…それぞれに対応する各スイッチ４０＿２，４０＿３，４０＿４，…が互いにシリーズに配置されている。これらの各スイッチ４０＿２，４０＿３，４０＿４，…は、対応するメモリワード１１＿２，１１＿３，１１＿４，…と、その直ぐ上段に隣接するメモリワード１１＿１，１１＿２，１１＿３，…との間に配置されている。それらのスイッチ４０＿２，４０＿３，４０＿４，…のうちの１つおきのスイッチ４０＿２，４０＿４，４０＿６，…は第１制御線４１に出力される第１のスイッチ制御信号によりオンし、３つおきのスイッチ４０＿３，４０＿７，…は第２制御線４２に出力される第２のスイッチ制御信号によりオンし、残りのスイッチのうち７つおきのスイッチ４０＿５，…は第３制御線４３に出力される第３のスイッチ制御信号によりオンされる。
【００６４】
１つのデータ群を構成するデータの数が２の場合は、第１制御線４１に第１のスイッチ制御信号を出力することにより１つおきのスイッチ４０＿２，４０＿４，４０＿６，…をオンさせる。これにより各２つのメモリワード１１＿１；１１＿２；１１＿３，１１＿４；１１＿５，１１＿６；…毎に切断されたデータ線が形成される。また、１つのデータ群を構成するデータの数が４の場合は、第１制御線４１に第１のスイッチ制御信号を出力するとともに第２制御線４２に第２のスイッチ制御信号を出力する。すると、各４つのメモリワード１１＿１，１１＿２；１１＿３，１１＿４；１１＿５，１１＿６，…毎に切断されたデータ線が形成される。同様にして、１つのデータ群を構成するデータの数が８の場合は、第１制御線４１、第２制御線４２にそれぞれ第１および第２のスイッチ制御信号を出力するとともに、第３制御線４３に第３のスイッチ制御信号を出力する。これにより各８つのメモリワード１１＿１，…，１１＿８；１１＿９…毎に切断されたデータ線が形成される。
【００６５】
この方式によれば、１つのデータ群を構成するデータの数が２の倍数の場合はメモリワードに空きは生じないが、２の倍数以外の、例えば３，５，９等の場合空きのメモリワードが生じてしまうことになる。この空きのメモリワードが生じないように多数のスイッチ４０＿２，４０＿３，…を任意にオン，オフできるように構成すると、制御線の本数が多数本となり、またそれらの制御線にスイッチ制御信号を出力する制御回路が複雑となる。したがって、図５に示す方式は、データ線の長さを任意に制御するには不向きである。
【００６６】
図６は、可変のデータ線を実現するもう一つの方式を示した模式図である。
多数のメモリワードに亘ってデータ線３２が延び、そのデータ線３２に互いにシリーズに接続された、最上端のメモリワードを除く他のメモリワードそれぞれに対応する各スイッチ４０＿２，４０＿３，４０＿４，…が備えられている点は図５の場合と同じである。各メモリワードには、各属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…が備えられており、それら属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…には、図示の各属性Ｉ，ＩＩ，ＩＩＩ，ＩＶがそれぞれ格納されている。この例は、属性格納部１１＿１＿１，１１＿２＿１，１１＿３＿１，…に格納された属性が属性Ｉかそれ以外の属性ＩＩ，ＩＩＩ，ＩＶかに応じて、属性Ｉの場合は対応するスイッチをオフのままとし、それ以外の属性ＩＩ，ＩＩＩ，ＩＶの場合は対応するスイッチをオンするように構成したものである。このように構成すると、１つのデータ群を構成するデータの数がいくつであっても、また、データ数の異なるデータ群が混在していても、各データ群の先頭に属性Ｉのデータを配置することにより、自動的に過不足ない数のメモリワード毎に切断されたデータ線が形成されることになる。
【００６７】
図７は、属性がＩかそれ以外かを判定する属性判定回路の一例を示す回路図である。
ここでは属性Ｉに‘０００’が割り当てられており、属性格納部１１＿ｉ＿１に格納された属性が属性Ｉ（‘０００’）の場合オアゲートから‘０’が出力され、したがってトランジスタ４０で構成されたスイッチ４０’はオフ状態となり、そのトランジスタ４０’の両側のデータ線が電気的に切断される。属性格納部１１＿ｉ＿１に格納された属性が属性Ｉ以外の属性の場合はオアゲートから‘１’が出力され、トランジスタ４０はオン状態となり、そのトランジスタの両側のデータ線が接続される。
【００６８】
このように、図４に示す連想メモリにおいて、１つのデータ群を構成するデータの数に応じてデータ線３２＿１，３２＿２，…の長さを調整することもできる。もちろん、属性データを利用するのではなく、専用の制御線によってスイッチを制御することによりデータ線の長さを調整してもよい。
次に、図４に示す連想メモリに本発明の技術思想を適用した、本発明の第２の連想メモリの一実施例について説明する。
【００６９】
図８は、本発明の第２の連想メモリの一実施例の特徴部分を示す回路図である。図１に示す本発明の第１の連想メモリの各構成要素に対応する構成要素には、図１に付した番号と対応する番号を付して示し、相違点を中心に説明する。
この図８には、図３に示すデータ群のうち、群番号ｎのデータ群を格納するメモリワード群、すなわち、空き状態にあるメモリワード群のうち、最優先のメモリワード群が示されている。
【００７０】
この図８に示す連想メモリには、図１に示す連想メモリと同様に、各メモリワード…，１１１ｎ，１１２ｎ，…，１１１ｎ＋１，…に対応してフラグレジスタ…，５１１ｎ，５１２ｎ，…，５１１ｎ＋１，…が備えられているが、これらのフラグレジスタ…，５１１ｎ，５１２ｎ，…，５１１ｎ＋１，…は、後述するようにして、各メモリワード群毎に一括して制御されるが、有効なフラグレジスタは、各メモリワード群毎の先頭のフラグレジスタである。
【００７１】
また、各メモリワード…，１１１ｎ，１１２ｎ，…，１１１ｎ＋１，…は、属性を格納する属性格納部…，１１１１ｎ，１１２１ｎ，…，１１１１ｎ＋１，…と、データを格納するデータ格納部…，１１１２ｎ，１１２２ｎ，…，１１１２ｎ＋１，…とで構成されている。ただし、図８では、図示の都合上、属性格納部１１１１ｎ，１１２１ｎ，…，１１１１ｎ＋１，…とデータ格納部１１１２ｎ，１１２２ｎ，…，１１１２ｎ＋１，…は互いに離れた位置に図示されている。
【００７２】
ここでは、群番号ｎ、群番号ｎ＋１に対応する各メモリワード群は空き状態にあり、したがってそれらのメモリワード群に対応するフラグレジスタ５１１ｎ，５１２ｎ，５１３ｎ，５１４ｎ，５１１ｎ＋１，…には、空き状態を示す論理‘１’のフラグが格納されている。
第１のトランジスタ…，８１１ｎ，８１２ｎ，…，８１１ｎ＋１，…は対応する属性格納部…，１１１１ｎ，１１２１ｎ，…，１１１１ｎ＋１，…から延びる制御線によりそのオン／オフが制御されるトランジスタであり、属性Ｉが格納された属性格納部…，１１１１ｎ，１１１１ｎ＋１，…のみがオン状態となる。したがって群番号ｎに対応する第１の可変長データ線８３ｎには、フラグレジスタ５１１ｎに格納された、空き状態を表わす論理‘１’（‘Ｈ’レベル）の信号が出力され、その信号がその群番号ｎに対応するメモリワード群内の４つの複数選択分離回路５２１ｎ，５２２ｎ，５２３ｎ，５２４ｎに入力される。またその第１の可変長データ線８３−ｎの信号は、その論理が反転されて、その群番号ｎに対応するメモリワード群内の４つのアンドゲート５３１ｎ，５３２ｎ，５３３ｎ，５３４ｎに入力される。
【００７３】
群番号ｎ＋１に対応するメモリワード群についても同様であり、フラグレジスタ５１１ｎ＋１に格納された論理‘１’の信号が第１のトランジスタ８１１ｎ＋１、第１の可変長データ線８３ｎ＋１を経由して、４つの複数分離選択回路５２１ｎ＋１，…および論理が反転されて、４つのアンドゲート５３１ｎ＋１，…に入力される。
【００７４】
図３に示すように、１，２，…，群番号ｎ−１に対応するメモリワード群には有効なデータ群が格納されている場合、群番号ｎに対応するメモリワード群に備えられた４つの複数分離選択回路５２１ｎ，５２２ｎ，５２３ｎ，５２４ｎのうち最上段の複数分離選択回路５２１ｎから最優先であることを示す論理‘１’（‘Ｈ’レベル）の信号が出力される。複数分離選択回路…，５２１ｎ，５２２ｎ，５２１ｎ＋１，…の出力側には、第２のトランジスタ…，８２１ｎ，８２２ｎ，８２１ｎ＋１，…が備えられている。この第２のトランジスタ…，８２１ｎ，８２２ｎ，８２１ｎ＋１，…は、第１のトランジスタ…，８１１ｎ，８１２ｎ，…，８１１ｎ＋１，…と同様に、属性格納部…，１１１１ｎ，１１２１ｎ，…，１１１１ｎ＋１，…に属性Ｉが格納されている場合のみオン状態となるトランジスタであり、複数分離選択回路５２１ｎから出力された論理‘１’の信号は、第２のトランジスタ８２１ｎを通って第２の可変長データ線８４ｎに出力される。ここでは群番号ｎに対応するメモリワード群が最優先のメモリワード群であり、したがって群番号ｎ＋１に対応するメモリワード群の複数分離選択回路５２１ｎ＋１の出力は論理‘０’であって、群番号ｎ＋１に対応するメモリワード群の第２の可変長データ線８４ｎ＋１には複数分離選択回路５２１ｎ＋１の出力である論理‘０’の信号が供給される。
【００７５】
また各属性格納部…，１１１１ｎ，１１２１ｎ，…，１１１１ｎ＋１，…からは、検索時に属性の一致を受けて論理‘１’（‘Ｈ’レベル）の信号が出力される属性一致線…，３０１ｎ，３０２ｎ，３０１ｎ＋１，…が延び、対応するアンドゲート…，５３１ｎ，５３２ｎ，５３１ｎ＋１，…の入力端子に接続されている。また、各データ格納部…，１１１２ｎ，１１２２ｎ，…，１１１２ｎ＋１，…からは、検索時にデータの一致を受けて論理‘１’（‘Ｈ’レベル）の信号が出力されるデータ一致線…，１４１ｎ，１４２ｎ，１４１ｎ＋１，…が延び、属性一致線…，３０１ｎ，３０２ｎ，３０１ｎ＋１，…と同様に、対応するアンドゲート…，５３１ｎ，５３２ｎ，５３１ｎ＋１，…の入力端子に接続されている。
【００７６】
ここで、属性ＩＩ，データ‘Ｂ’の検索データを入力してデータ検索を行なったとし、属性格納部１１２１ｎに属性ＩＩが格納されているメモリワード１１２ｎのデータ格納部１１２２ｎにたまたまデータ‘Ｂ’が格納されていたとすると、属性の一致を受けて属性一致線３０２ｎが‘Ｈ’レベルとなり、またデータの一致を受けてデータ一致線１４２ｎも‘Ｈ’レベルとなるが、第１の可変長データ線８３ｎが、空き状態を表わす‘Ｈ’レベルにあるため、アンドゲート５３２ｎからは一致を表わす‘Ｈ’レベルの信号は出力されない。すなわち、空き状態にあるメモリワード群は、検索には参加しない。
【００７７】
この検索を行なっているときに、いずれかのメモリワード群で一致が検出されたか否かとは無関係に、追記制御回路７２（図１参照）から、ワード線活性化タイミング信号線６８に‘１’の信号が出力される。すると、図８の上から２番目のメモリワード１１２ｎに対応するアンドゲート６７２ｎの入力が全て‘１’となりアンドゲート６７２ｎの出力側に延びるワード線２４２ｎが‘１’となり、メモリワード１１２ｎに検索データが書き込まれる。この検索データが書き込まれたタイミングは、検索と同時であり、したがってその検索において一致が生じたか否かとは無関係である。
【００７８】
以上のような検索と検索データの書き込みが所定回数行なわれた後、最終的に所望のデータ群が検出されたか否かの情報が追記制御回路７２（図１参照）に入力される。追記制御回路７２では、いずれかのメモリワード群において所望のデータ群が検出された場合はその後は何も行なわない。すなわち、図８に示す群番号ｎに対応するメモリワード群には検索の都度検索データが書き込まれたものの、そのメモリワード群に対応するフラグレジスタ５１１ｎ，５１２ｎ，，５１３ｎ，５１４ｎには依然として空きフラグ‘１’が格納されており、群番号ｎに対応するメモリワード群は、依然として検索には寄与しない空き状態にとどまることになる。
【００７９】
一方、全体一致検出回路７１で、全てのメモリワード群にわたって所望のデータ群が検出されなかったときは、追記制御回路７２（図１参照）は、以下のように動作する。すなわち、フラグレジスタ…，５１１ｎ，５１２ｎ，…，５１１ｎ＋１，…に接続された空きフラグデータ線６６に論理‘０’の信号を与え、その状態で空きフラグクロック信号線６５に‘１’のクロックパルスを与える。すると、図示の群番号ｎに対応するメモリワード群に延びる第２の可変長データ線８４ｎに論理‘１’の信号が出力されていることから空きフラグクロック信号線６５に与えられた‘１’のクロックパルスは、４つのアンドゲート６１１ｎ，６１２ｎ，６１３ｎ，６１４ｎをそれぞれ通過して４つのフラグレジスタ５１１ｎ，５１２ｎ，５１３ｎ，５１４ｎに入力され、それら４つのフラグレジスタ５１１ｎ，５１２ｎ，５１３ｎ，５１４ｎに、有効なデータ群が記録されていることを示す論理‘０’のフラグが格納される。
【００８０】
複数選択分離回路…，５２１ｎ，５２２ｎ，…，５２１ｎ＋１，…では、群番号ｎに対応するフラグレジスタ５１１ｎ，５１２ｎ，５１３ｎ，５１４ｎに‘０’が格納されたことに伴い、その群番号ｎに対応するメモリワード群以外の、空きフラグ‘１’が格納されているフラグレジスタに対応するメモリワード群の中から最も優先度の高いメモリワード群（ここに示す例では群番号ｎ＋１に対応するメモリワード群）が検出されることになる。
【００８１】
尚、図８に示す実施例では、いずれのメモリワード群にも所望のデータ群が格納されていなかったことを受けて、追記制御回路７２が、自動的に、最優先のメモリワード群（図８の例では群番号ｎに対応するメモリワード群）に対応するフラグレジスタに空き状態を解除する論理‘０’のフラグを書き込んだが、追記制御回路７２に外部から所定の制御信号を入力できるように構成しておき、追記制御回路７２では、外部からその制御信号が入力されるのを待って、最優先のメモリワード群の空き状態を解除してもよい。
【００８２】
【発明の効果】
以上説明したように、本発明の連想メモリは、検索と同時に検索データをそのまま格納してしまうものであるため、未登録データの追記が高速に行なわれる。したがって本発明の連想メモリは、例えばＬＡＮシステム等に好適である。
【図面の簡単な説明】
【図１】本発明の第１の連想メモリの一実施例の特徴部分を示す回路図である。
【図２】複数選択分離回路の回路図である。
【図３】群構造のデータの一例を示す図である。
【図４】群構造のデータを取り扱うのに適した連想メモリの一例を示すブロック図である。
【図５】可変長のデータ線を実現する一つの方式を示した模式図である。
【図６】可変のデータ線を実現するもう一つの方式を示した模式図である。
【図７】属性がＩかそれ以外かを判定する属性判定回路の一例の回路図である。
【図８】本発明の第２の連想メモリの一実施例の特徴部分を示す回路図である。
【図９】従来の連想メモリの一例を表わした回路ブロック図である。
【図１０】連想メモリ中の１つのメモリワードを表わした詳細回路図である。
【図１１】ＬＡＮの一例を示した図である。
【図１２】ブリッジの機能説明図である。
【符号の説明】
１１，１１＿１ｎ，１１＿２ｎ，…，１１＿１ｎ＋１メモリワード
１１＿１＿１ｎ，１１＿２＿１ｎ，…，１１＿１１ｎ＋１
属性格納部
１１＿１＿２ｎ，１１＿２＿２ｎ，…，１１＿１２ｎ＋１
データ格納部
１４一致線
１４＿１ｎ，１４＿２ｎ，…，１４＿１ｎ＋１データ一致線
３０＿１ｎ，３０＿２ｎ，…，３０＿１ｎ＋１属性一致線
５１，５１＿１ｎ，５１＿２ｎ，…，５１＿１ｎ＋１フラグレジスタ
５２，５２＿１ｎ，５２＿２ｎ，…，５２＿１ｎ＋１
複数選択分離回路[0001]
[Industrial application fields]
The present invention includes a plurality of memory words for storing each data, and an associative memory having a function of searching for a match / mismatch between the stored data of each memory word and input search data. Addressable memory).
[0002]
[Prior art]
In recent years, an associative memory having a search function as described above has been proposed. Here, first, the structure and function of the associative memory will be described, and then examples of application fields of the associative memory will be described.
FIG. 9 is a circuit block diagram showing an example of a conventional associative memory.
[0003]
The associative memory 10 is provided with a large number of memory words 11a, 11b,..., 11n composed of a plurality of memory cells arranged in the horizontal direction in the figure. The associative memory 10 also includes a search register 12 into which search data is input and latched. The search data latched in the search register 12 is entirely or a predetermined bit pattern, and each of the memory words 11a, 11b,. , 11n are compared for coincidence / non-coincidence between the bit pattern and the corresponding bit pattern, and a match line 14a provided for each of the memory words 11a, 11b,. , 14b,..., 14n, a match signal of logic '1' is output to the match lines 14a, 14b,..., 14n corresponding to the memory words 11a, 11b,. A mismatch signal of logic “0” is output to the lines 14a, 14b,.
[0004]
Here, it is assumed that signals of “0”, “1”, “0”, “0”, “1”,..., “0” are output to the flag lines 14a, 14b,. This signal is input to the priority encoder 15, and the priority encoder 15 has the highest priority among the match lines (here, the match line 14b and the match line 14e) from which a match signal of logic '1' is output. An address signal AD corresponding to the highest highest priority match line is output. Here, it is assumed that the lower the alphabet of the subscript is, the higher the priority is. Therefore, here, the match line 14b is the highest priority match line. The address signal AD corresponding to the highest priority match line 14b output from the priority encoder 15 is input to the address decoder 16 as necessary. The address decoder 16 decodes the input address signal AD and inputs the address of the word lines 17a, 17b,..., 17n provided corresponding to the memory words 11a, 11b,. An access signal (here, a signal of logic “1”) is output to any one word line (here, the word line 17b) corresponding to the signal AD. As a result, data stored in memory word 11b corresponding to word line 17b to which the access signal is output is read to output register 18.
[0005]
As described above, the associative memory 10 searches the contents (data) stored in the many memory words 11a, 11b,..., 11n using the search data, and obtains the address of the memory word in which the matching data is stored. The memory is capable of reading the entire data stored in the memory word.
FIG. 10 is a detailed circuit diagram showing one memory word in the associative memory.
[0006]
This memory word 11 is composed of n memory cells 11-1, 11-2,..., 11-n having the same configuration. Each of the memory cells 11-1, 11-2,..., 11-n has a first inverter 20-1, 20-2,. Inverters 21-1, 21-2,..., 21-n, and these inverters 20-1, 21-1; 20-2, 21-2; 1-bit information of logic '1' or logic '0' is stored in each of the memory cells 11-1, 11-2, ..., 11-n.
[0007]
In each of the memory cells 11-1, 11-2,..., 11-n, the outputs of the first inverters 20-1, 20-2,. , 22-n are connected to bit lines 23-1, 23-2,..., 23-n, and the gates of the transistors 22-1, 22-2,. It is connected. Also, the outputs of the second inverters 21-1, 21-2,..., 21-n are sent to bit bar lines 26-1, 26-2 via N-channel transistors 25-1, 25-2,. ,..., 26-n, and the gates of the transistors 25-1, 25-2,. Further, each of the memory cells 11-1, 11-2,..., 11-n includes bit lines 23-1, 23-2,..., 23-n and bit bar lines 26-1, 26-2,. n-channel transistors 27-1, 28-1; 27-2, 28-2;...; 27-n, 28-n connected to each other in series so as to connect to n, Each of these two transistors 27-1, 28-1; 27-2, 28-2;..., 27-n, 28-n, one of the transistors 27-1, 27-2,. The gates are the outputs of the first inverters 20-1, 20-2,..., 20-n, and the gates of the other transistors 28-1, 28-2,. ,..., 21-n are connected to the outputs.
[0008]
The coincidence line 14 includes transistors 36-1, 36-2,..., 36-n corresponding to the memory cells 11-1, 11-2,. The transistors 36-1, 36-2,..., 36-n are connected in series with each other, and the gates of the transistors 36-1, 36-2,. 1, 28-1; 27-2, 28-2;...; Connected to the midpoint of 27-n, 28-n.
[0009]
Further, another transistor 36-0 is connected to the match line 14 in series, and the left end of the match line 14 in FIG. 10 is grounded via the transistor 36-0. The gate of the transistor 36-0 is connected to the control line 30.
A sense inverter 31 is arranged at the right end of the coincidence line 14 in FIG. 10, and the coincidence line 14 further extends from the output of the inverter 31 and is connected to the priority encoder 15 shown in FIG.
[0010]
The input of this inverter 31 and the power source V_DDBetween the two transistors, two P-channel transistors 32 and 33 are arranged. The gate of one of the two transistors 32 and 33 is connected to the control line 30 and the gate of the other transistor 33 is The output of the inverter 31 is connected.
In an associative memory including a memory word having such a structure and its peripheral circuits, a match search is performed as follows.
[0011]
It is assumed that information of logic “1” is stored in the memory cell 11-1. That is, in this case, the output side of the first inverter 20-1 is in the logic "1" state, and the output side of the second inverter 21-1 is in the logic "0" state.
It is assumed that a logic “1” search is performed on the memory cell 11-1. That is, the bit line 23-1 is set to logic “1” and the bit bar line 26-1 is set to logic “0”. The word line 24 is held in the state of logic “0”. In this case, a logic '1' voltage is applied to the gate of the transistor 27-1, and a logic '1' signal on the bit line 23-1 is applied to the gate of the transistor 36-1, which causes the transistor 36-1 to 'On' state. That is, when the bit information stored in the memory cell 11-1 matches the bit information in the search data input via the bit line 23-1 and the bit bar line 26-1, the corresponding transistor 36-1 Enters the 'on' state.
[0012]
In addition, it is assumed that logic “0” information is stored in the memory cell 11-2. In this case, the output side of the first inverter 20-2 is in a logic '0' state, and the output side of the second inverter 21-2 is in a logic '1' state.
It is assumed that the logic “1” is searched for the memory cell 11-2. That is, the bit line 23-2 is set to logic "1", and the bit bar line 26-2 is set to logic "0". In this case, the signal of the bit bar line 26-2 in the logic “0” state is applied to the gate of the transistor 36-2 via the transistor 28-2, so that the transistor 36-2 is in the “off” state. Will stay. That is, in the case of mismatch, the charge precharged on the match line 14 is not discharged.
[0013]
For the masked bit, as shown in the memory cell 11-n, both the bit line 23-n and the bit bar line 26-n are set to logic '1'. In this case, either the transistor 27-n or the transistor 28-5 is 'ON' depending on whether logic '1' information or memory '0' information is stored in the memory cell 11-n. This causes the transistor 36-5 to be 'on' in either case. That is, for the memory cell, the stored information and the search information are regarded as matching.
[0014]
In the search, the control line 30 is first set to logic “0”, the transistor 32 is turned “ON”, and the coincidence line 14 on the input side of the inverter 31 is precharged, and then the control line 30 is set to logic “1”. 32 is in an “off” state, precharging is stopped, and the transistor 36-0 is in an “on” state.
[0015]
At this time, when the information stored in the memory cell and the input search information are consistent across all the memory cells constituting the memory word 11 (the masked bits are regarded as coincident as described above), All of the transistors 36-1, 36-2,..., 36-n are in the “ON” state, and the precharged charges on the coincidence line 14 are discharged, and a logic “1” signal is output from the inverter 31.
[0016]
The memory structure of the associative memory shown in FIG. 10 is merely an example, and various structures have been proposed (see, for example, Japanese Patent Application No. 5-216424).
Next, an application example to a LAN (Local Area Network) will be described as an example of application of the associative memory.
FIG. 11 is a diagram illustrating an example of a LAN.
[0017]
As shown in FIG. 11A, it is assumed that a plurality of terminals A to G and TZ are connected to two communication lines LAN1 and LAN2, respectively, thereby forming two communication lines. It is assumed that the traffic amount of the communication lines LAN1 and LAN2 (the amount of data flowing through the communication line; the degree of congestion of the communication line) is “10”. When it is necessary to connect these two communication lines to each other, if they are simply connected as shown in FIG. 11B as shown in FIG. 11B, the traffic volume of the communication lines LAN1 and LAN2 becomes 20. The result is that the terminals are extremely congested, the terminals are not easily connected, and waiting time and idle time increase.
[0018]
Therefore, normally, as shown in FIG. 11C, filtering whether or not data transmitted from one of the communication lines LAN1 and LAN2 is transmitted to the other between the two communication lines LAN1 and LAN2. Connect the bridge to perform. When this bridge is connected, if the traffic volume of data passing through this bridge, that is, the traffic volume for data exchange across two communication lines is 1, the traffic volume 10 inside each communication line LAN1, LAN2 is In addition, the traffic volume of each of the communication lines LAN1 and LAN2 is 11, and the traffic volume is greatly reduced as compared with the case of FIG. 11B in which the two communication lines LAN1 and LAN2 are simply connected. Although the connection between the two communication lines LAN1 and LAN2 has been described here, this difference becomes more prominent when a large number of communication lines are connected to one bridge.
[0019]
FIG. 12 is a functional explanatory diagram of the bridge.
The bridge has a memory inside and initially starts from a blank state. For example, when data is transmitted from the terminal A of the communication line LAN1, the terminal A receives the data transmitted from the LAN1 side. Learns that is connected to the communication line LAN1. This learning is conceptually performed by having tables 1 and 2 for the communication lines LAN1 and LAN2 in the memory inside the bridge, and writing the terminal A into the table 1 corresponding to the communication line LAN1. Whether or not the destination of the data transmitted from the terminal A is in the same LAN 1 side communication network as that of the terminal A is not known at the time of learning only about the terminal A. Therefore, the bridge is passed unconditionally at this time.
[0020]
By repeating such learning, tables 1 and 2 as shown in FIG. 12 are created in the bridge, and after these are created, the destination is the terminal B (LAN1 side) as shown in the figure, for example. The data of the destination X (LAN2 side) is a bridge, the terminals B and X recognize that the bridge crosses the bridge, pass through the bridge, and the destination and destination are both terminals on the LAN1 side. In the case of A and E, the terminals A and E recognize that they are on the same communication network as seen from the bridge, and block the data from passing through the bridge. Thereby, as described above, the traffic amount can be reduced.
[0021]
If an associative memory is employed as the memory provided in the bridge, the processing speed can be increased. For example, information on each of the terminals A to G and T to Z and information on whether each of these terminals belongs to the table 1 (connected to the LAN 1 side) or to the table 2 (whether it belongs to the LAN 2 side) In determining whether to store data in the associative memory and pass the data, for example, if the receiving destination is the terminal X, the X is searched as search data, and the X belongs to the table 2 (LAN2). Recognizing that there is, it is possible to determine whether or not to allow data to pass based on this.
[0022]
On the other hand, when a normal RAM memory or the like is provided in the bridge, it is necessary to read out the stored data one by one and search whether the data is the data of the terminal X by sequential comparison. It takes a lot of time to determine whether to pass or block the bridge.
[0023]
[Problems to be solved by the invention]
As described above, the associative memory is preferably used in, for example, a LAN network. For example, when data is transmitted from the terminal A, whether or not the terminal A is already registered in the memory in the bridge in response to the data. Check and register if unregistered. As described above, conventionally, it is necessary to check two steps, i.e., confirmation of whether or not the registration has already been performed, and registration in the case of non-registration. This is one of the obstacles to further speeding up the operation of the bridge. It has become one.
[0024]
In view of the above circumstances, an object of the present invention is to provide an associative memory capable of registering unregistered data at high speed.
[0025]
[Means for Solving the Problems]
The first associative memory of the present invention that achieves the above-described object provides:
A memory word for storing each data, a bit pattern of all or a part of the input search data provided corresponding to the memory word, and the bit pattern among the data stored in the memory word And an associative memory including a coincidence detection circuit for detecting coincidence / non-coincidence with all or a part of the corresponding bit pattern,
If no match signal indicating that a match is detected is output from any of the match detection circuits, the search data is stored as valid data to be searched among the memory words. Therefore, a data appending circuit is provided which is stored in one of the memory words in an empty state where overwriting is allowed.
[0026]
Here, in the first associative memory of the present invention, the data appending circuit is
(1) A flag provided corresponding to the above-described memory word, indicating whether the memory word is a memory word in a storage state in which valid data is stored or a memory word in a free state Stored flag register
(2) Search data write circuit for selecting one memory word from memory words in an empty state and writing search data to the one memory word
(3) A flag change circuit for storing a flag indicating a storage state in a flag register corresponding to the one memory word when no coincidence signal is output from any of the coincidence detection circuits.
It may be provided.
[0027]
The second associative memory of the present invention that achieves the above object is
A plurality of data constituting a data group consisting of a set of a plurality of stored data is provided with a plurality of memory word groups consisting of a plurality of memory words for storing each data, and is input each time search data is input. A match search between all or a part of a predetermined bit pattern of the search data and all or a part of the bit pattern corresponding to the bit pattern in the data stored in the memory word is performed once or a plurality of consecutive times In all of the predetermined number of coincidence searches consisting of, all or part of the input search data or each predetermined part of the bit pattern and all or part of the data stored in the same memory word group corresponding to the bit pattern Is detected, the presence of a data group corresponding to the search data input a predetermined number of times is detected. In the associative memory,
During the predetermined number of matching searches, each time the search is performed, the input search data is not stored as a valid data group to be searched, and is therefore in a free state in which overwriting is allowed. A data write circuit for writing to any one of the memory words in one memory word group selected from the word group is provided.
[0028]
Here, in the second associative memory of the present invention,
(4) A corresponding memory word group provided corresponding to each of the memory word groups is a memory word group in a storage state in which a valid data group is stored, or a memory word group in an empty state. Flag register that stores a flag indicating whether or not there is
(5) If a data group corresponding to the search data input a predetermined number of times is not detected as a result of the predetermined number of matching searches, a flag indicating a storage state is stored in the flag register corresponding to the one memory word group. Flag change circuit for storing
It is preferable to provide.
[0029]
Alternatively, in the second associative memory of the present invention,
(6) A corresponding memory word group provided corresponding to each of the memory word groups is a memory word group in a storage state in which the valid data group is stored, or a memory word in the empty state Flag register that stores a flag indicating whether or not a group
(7) A flag change circuit that receives a predetermined instruction signal input from the outside and stores a flag indicating a storage state in a flag register corresponding to the one memory word group
May be provided.
[0030]
[Action]
Since the first associative memory of the present invention stores the search data as it is in response to the fact that no match was detected by the search, the search operation and the search are matched as in the conventional case. If no data is detected, the two steps of the data writing operation are not necessary, and the processing speed is increased.
[0031]
Here, since a technique related to the present invention is proposed in Japanese Patent Publication No. 61-31558, a difference between the technique proposed there and the present invention will be described.
Many memory words that make up an associative memory do not always store data to be searched in all memory words, and some of these memory words are empty in which no valid data is stored. In some cases, valid data may be written to a memory word that is in a state of being empty. In this case, since it is cumbersome to manage externally whether or not this memory word is in an empty state, the above document describes data valid for the memory word corresponding to each memory word. Is stored in association with each memory word, and when writing new valid data, the associative memory itself is in an empty state. Techniques have been proposed for finding a word and writing valid data to the memory word.
[0032]
The technology proposed there is for eliminating the need to manage memory words that are in an empty state. When registering unregistered data, the data is still registered or unregistered. It requires two steps: search and registration when not registered.
The second associative memory of the present invention has a memory word group for storing a data group, and performs an operation of inputting search data and performing a search a predetermined number of times to detect the presence of the corresponding data group. It is about memory.
[0033]
In such an associative memory, for example, when a desired data group is detected by repeating the operation of storing a data group of 100 data and inputting the search data and performing the search 100 times, a conventional idea is considered. When the associative memory of the type that detects the existence of the data group that has been stored is used, if the desired data group is not found as a result of 100 searches, the search data is written 100 times and a new effective A data group will be registered.
[0034]
In contrast, in the second associative memory of the present invention, search data is written into a memory word group in an empty state for each search, so that the desired data is obtained as a result of 100 searches. If no group is found, search data has already been written for each search, so it is only necessary to determine whether or not to use the memory word group to which this search data is written for the next and subsequent searches. The time for writing is greatly reduced, and the processing speed is increased.
[0035]
Whether or not to use the memory word group in which the search data is written for the next and subsequent searches includes, for example, the flag registers (4) and (6) above, and rewrites the flag stored in the flag register. Can be determined by.
This flag rewriting may be configured to automatically rewrite in response to the fact that a desired data group has not been detected by a predetermined number of searches by providing the flag changing circuit of (5) above. Although it is preferable, the flag change circuit of (7) may be provided so that an instruction to rewrite the flag may be input from the outside. Even in this case, the processing speed can be significantly increased compared to the conventional case. Can do.
[0036]
【Example】
Examples of the present invention will be described below.
FIG. 1 is a circuit diagram showing the characterizing portion of one embodiment of the first associative memory of the present invention. Constituent elements corresponding to the constituent elements in the drawings referred to in the above-described conventional example are denoted by the same reference numerals as those in the drawings.
[0037]
In FIG. 1, the configuration of the memory word 11 and the coincidence line 14 is schematically shown. Each flag register 51 is provided corresponding to each memory word 11, and this flag register 51 is “0” when a valid word to be searched is stored in the corresponding memory word 11. , When invalid data that is excluded from the search target and thus allows overwriting is stored (here, this is referred to as the corresponding memory word 11 being “free”), A flag is stored. Here, it is assumed that “0”, “0”,..., “1” are stored in each flag register 51 as illustrated. The Q output of each flag register 51 is input to each of the multiple selection separation circuits 52 provided correspondingly. The selection / separation circuits 52 are connected in series with each other, and as a result of this connection, the priority is higher in the upper part of the figure. Among the flag registers 51 in which “1” is stored, the priority is the highest. The signal “1” is output only from the multiple selection separation circuit 52 corresponding to the flag register 51. Here, the flag register 51 shown at the bottom of FIG. 1 has the highest priority. Therefore, “1” is output from the multi-selection separation circuit 52 shown at the bottom corresponding thereto. To do.
[0038]
FIG. 2 is a diagram showing a circuit example of the multiple selection separation circuit 52.
The multi-selection / separation circuit 52 shown in FIG. 2A includes an AND gate 521 that is connected as shown in the figure and in which one input is inverted, and an OR gate 522. Also, one input of an OR gate 522 constituting the uppermost multiple selection separation circuit 52 shown in the figure is grounded to the ground GND.
[0039]
The multi-selection / separation circuit 52 having this configuration has a higher priority in the upper part of the figure, and when the empty flag “1” is stored in the plurality of flag registers 51, the highest among the plurality of flag registers 51 '1' is output from the AND gate 521 of the multiple selection separation circuit 52 corresponding to the flag register 51 having a high priority.
[0040]
2B includes an inverter 523, an N channel transistor 524, a P channel transistor 526, and an exclusive OR gate 525, as shown. One end of the P-channel transistor 526 constituting each of the multiple selection / separation circuits 52 'is connected to the power source V._DDAnd one input of an exclusive OR gate 525 constituting the top multiple selection separation circuit 52 'shown in the figure is grounded to the ground GND.
[0041]
Similarly to the multiple selection separation circuit 52 shown in FIG. 2A, the multiple selection separation circuit 52 ′ shown in FIG. When the empty flag “1” is stored in the exclusive OR gate 525 of the multiple selection separation circuit 52 ′ corresponding to the flag register 51 having the highest priority among the plurality of flag registers 51 to “1”. Is output.
[0042]
If an encoder is connected to the subsequent stage of the multiple selection separation circuit shown in FIG. 2A or 2B, the priority encoder 15 shown in FIG. 9 is configured.
As described above, when the flag register 51 shown at the bottom of FIG. 1 has the highest priority in the second flag register 51 in which the empty flag “1” is stored, it corresponds to that. '1' is output from the multiple selection / separation circuit 52 to be input to the corresponding AND gate 67. A word line activation timing signal line 68 is also connected to the input of the AND gate 67.
[0043]
Here, the bit line drive circuit 70 puts search data on the bit lines 23-1,..., 23-n and the bit bar lines 26-1,. As a result, if the search data matches the data stored in the uppermost memory word 11 shown in the figure, the uppermost match line 14 becomes “1”, and the output of the flag register 51 is “0”. Therefore, the output of the AND gate 53 becomes “1”. Here, a line extending from the output of the AND gate 53 is also referred to as a coincidence line 140. Match lines 140 corresponding to all the memory words 11 extend to the entire match detection circuit 71, and further extend to the priority encoder 15 shown in FIG. 9 instead of the match line 14 in the conventional case. When the empty flag “1” is stored in the flag register 51, even if a match occurs in the memory word 11 corresponding to the flag register 51, the “1” signal on the match line 14 is stopped by the AND gate 53, The coincidence line 140 on the output side of the AND gate 53 remains “0”. That is, the memory word 11 does not contribute to the search.
[0044]
The whole coincidence detection circuit 71 performs an OR operation on the signals input from the coincidence lines 140, thereby detecting whether there is any coincidence or disagreement over all the memory words 11. Is input.
In the write-once control circuit 72, first, the bit lines 23-1,..., 23-n, the bit bar lines 26-1,. When the search data is put in the search, the signal “1” is put on the word line activation timing signal line 68. Then, the output of the AND gate 67 corresponding to the bottom multiple selection / separation circuit 52 shown in the figure, which outputs the signal “1”, becomes “1”, and the corresponding word line 24 becomes “1”. The search data is written in the lowest memory word 11 shown in the figure. The timing at which this search data is written is at the same time as the search, and is therefore independent of whether or not a match has occurred in the search.
[0045]
Thereafter, as described above, whether or not a match has occurred in any of the memory words 11 in the overall match detection circuit 71 or a mismatch in all the memory words 11 is detected and input to the additional write control circuit 72. In the write-once control circuit 72, if there is a match in any one of the memory words 11, nothing is performed thereafter. That is, although the search data is overwritten in the bottom memory word 11 shown in the figure, the empty flag '1' is still stored in the corresponding flag register 51, and the bottom memory word 11 is still It will remain in a free state that does not contribute to the search.
[0046]
On the other hand, when a mismatch is detected across all the memory words 11 by the overall match detection circuit 71, the additional write control circuit 72 operates as follows. That is, a logic "0" signal is applied to the empty flag data line 66 connected to the flag register 51, and a clock pulse of "1" is applied to the empty flag clock signal line 65 in that state. Then, the word line 24 of the lowermost memory word 11 shown in the figure is “1”, and the signal “1” is input to the bottom AND gate 61 via the signal line 60. The clock pulse applied to the empty flag clock signal line 65 passes through the AND gate 61 and is input to the lowermost flag register 51. As a result, “0” indicating that valid data to be searched is stored in the memory word 11 corresponding to the lowermost flag register 51.
[0047]
In the multi-selection / separation circuit 52, when “0” is stored in the lowest flag register 51 in the figure, the flag register 51 other than the flag register 51 stores the empty flag “1”. The one with the highest priority is detected.
Next, an embodiment of the second associative memory according to the present invention will be described. The idea of the second associative memory according to the present invention is preferably applied, and the data group is stored and searched. Since the associative memory itself is not yet publicly known (see Japanese Patent Application No. 5-248121), here, the associative memory itself as a base will be described first, and then a second example of the associative memory of the present invention will be described. .
[0048]
FIG. 3 is a diagram illustrating an example of data forming a group structure.
FIG. 3 shows a data structure in which four data with attributes I, II, III, and IV are combined to form one data group. To clarify the concept of data groups and attributes, for example, each data group for each group number 1, 2, 3, 4,... Is data belonging to each individual, and attribute I is the person's The name and attribute II indicate the person's date of birth, the attribute III indicates the address, and so on.
[0049]
As described above, for example, in the case where a search is performed by storing a data group composed of a plurality of data to which attributes I, II, III, and IV are attached in an associative memory, for example, the data of group number 1 is searched. In other words, the search for the data 'A' and the search for the data 'B' are performed in this order to read out the remaining data 'C' and 'D' in the matching data group. When searching for the remaining data 'B' and 'C' by searching and searching for data 'D', or when searching for data 'B' first and then for data 'A' There is an associative memory that can perform such various searches.
[0050]
Here, for convenience of explanation, it is assumed that group numbers n and n + 1 are in an empty state in which no valid data group is recorded.
FIG. 4 is a block diagram showing an example of an associative memory suitable for handling data having a group structure as shown in FIG.
.. Extending from each memory word 11_1, 11_2,... Are connected to one input terminal of each AND gate 20_1, 20_2,. The other input terminals of the AND gates 20_1, 20_2,... Are connected to the output terminals of the OR gates 21_2, 21_3,..., And one input terminal of each of the OR gates 21_2, 21_3,. 22 is connected.
[0051]
The output terminals of the AND gates 20_1, 20_2,... Are connected to the data input terminals of the first flag registers 23_1, 23_2,..., And the output terminals of the first flag registers 23_1, 23_2,. Are connected to the input terminals of the flag registers 24_1, 24_2,. The output terminals of the second flag registers 24_1, 24_2,... Are connected to the priority encoder 15 (not shown in FIG. 4) shown in FIG. 9, and through the first switches 33_1, 33_2,. .. Are connected to data lines 32_1, 32_2,... Provided for each memory word group storing each data group shown in FIG.
[0052]
The first flag registers 23_1, 23_2,... And the second flag registers 24_1, 24_2,... Receive the match result latch signal S1 output to the match result latch control line 25, and the match result latch signal. The input data input from each data input terminal is latched by S1, but the input data at the time of the rising edge a of the coincidence result latch signal S1 is latched in the first flag registers 23_1, 23_2,. In the second flag register 24_1, 24_2,..., The input data at the time “b” of the coincidence result latch signal S1 is latched.
[0053]
Each of the memory words 11_1, 11_2,... Includes an attribute storage unit 11_1_1, 11_2_1,... That stores an attribute, and a data storage unit 11_1_2, 11_2_2,. Each stores storage data consisting of pairs of attributes and data corresponding to each other. Here, as shown in the figure, each of the memory words 11_1, 11_2, 11_3, and 11_4 has an attribute I, data 'A', attribute II, data 'B', attribute belonging to the group number 1 shown in FIG. III, data 'C', attribute IV, and data 'D' are stored. Further, in each of the memory words 11_5, 11_6,..., Attribute I, data “C”, attribute II, data “F”,... Belonging to the group number 2 shown in FIG. In the search, reference data REF_DATA consisting of a pair of attribute and data is input.
[0054]
A match signal is output to each memory word 11_1 and 11_2 when the stored data (both attribute and data) stored therein match the input reference data (both attribute and data). In addition to the conventional match lines 14_1, 14_2,..., Attribute match lines 30_1, 30_2,. It should be noted that both the attribute only match and the attribute and data match are configured in the same way as the conventional match detection circuit, and the conventional match detection circuit is a very general technique in the field of associative memory. The illustration and explanation are omitted. The third flag registers 31_1, 31_2, ... are provided corresponding to the memory words 11_1, 11_2, and the attribute match lines 30_1, 30_2, ... are data of the corresponding third flag registers 31_1, 31_2, .... Extends to the input terminal. Further, in the associative memory of this embodiment, as described above, one data line 32_1, 32_2,... Is provided for each memory word group composed of memory words storing each data belonging to each data group shown in FIG. Are provided, and the first switches 33_1, 33_2,... Are provided between the data lines 32_1, 32_2,... And the output terminals of the second flag registers 31_1, 31_2,. Specifically, these first switches 33_1, 33_2,... Are configured using transistors or the like. The same applies to other switches described later. Each of the first switches 33_1, 33_2,... Is turned on when a logic “1” signal is latched in the corresponding third flag register 31_1, 31_2,. It is cut off when it is done. Each of the third flag registers 31_1, 31_2,... Latches the signal of the corresponding attribute match line 30_1, 30_2, ... at the timing of the falling b of the match result latch signal S1 output to the match result latch control line 25. To do.
[0055]
Further, second switches 34_1, 34_2, ... are provided between the data lines 32_1, 32_2, ... and the input terminals of the OR gates 21_1, 21_2, ..., and these second switches 34_1, 34_2, ... are provided. Are controlled by the signals of the corresponding attribute match lines 30_1, 30_2,... To be in a conductive state when the signal is logic “1” indicating coincidence, and to be cut off when the signal is logic “0” indicating mismatch. .
[0056]
In the associative memory configured as described above, the matching search is performed as follows.
When searching each search data independently, the first search timing signal S2 is output to the first search control line 22 when the reference data REF_DATA is input and the search is performed. Here, assuming that attribute II and data 'B' are input as reference data REF_DATA, a match signal of logic '1' is sent to match line 14_2 corresponding to word memory 11_2 storing attribute II and data 'B'. Since the first search timing signal S2 is input to the AND gate 20_2 via the OR gate 21_2, the logic '1' signal is output from the AND gate 20_2. At this time, since the logic '0' signal is output to the other coincidence lines 14_1; 14_3, 14_4,..., The other AND gates 20_1; 20_3, 20_4,. A signal is output.
[0057]
The logic '1' signal output from the AND gate 20_2 is latched in the first flag register 23_2 at the timing of the rising edge a of the match result latch signal S1 output to the match result latch control line 25, and the subsequent match. The result latch signal S1 is latched in the second flag register 24_2 at the timing of falling b.
[0058]
Further, at each timing when a signal of logic “1” is latched in the first flag register 23_2 and the second flag register 24_2, the other first flag registers 23_1; 23_3, 23_4,. A signal of logic “0” is latched in the registers 24_1; 24_3; 24_4,.
The signals of logic '0', '1', '0',... Latched in the second flag registers 24_1, 24_2, 24_3, ... in this way are input to the priority encoder 15 shown in FIG. An address signal AD of the memory 11_2 is obtained.
[0059]
Next, a case where a plurality of continuous data searches are performed will be described. The first search in the case of performing a plurality of consecutive searches is the same as the above-described single data search operation. However, in this first data search, in addition to the above operation, the second search In preparation for the second data search, the following operation is performed.
At the time of the first data search, a signal of logic '1' is output to the attribute match line 30_2 corresponding to the memory word 11_2 in response to the attribute match, whereby the corresponding third flag register 31_2 is output. Also, the logic '1' signal is latched, the corresponding first switch 33_2 is turned on, and the logic '1' signal representing the match of both the attribute and the data stored in the corresponding second flag register 24_2 is The data is output to the data line 32_1. At the same time, the corresponding second switch 34_2 is also turned on, but this is an unnecessary operation in the first search.
[0060]
Next, search is performed by inputting reference data REF_DATA including attribute IV and data ‘D’. At this time, the initial search control line 22 is held at logic “0”. At this time, in response to the attribute match, a logic '1' signal is output to the attribute match line 30_4 corresponding to the memory word 11_4, thereby turning on the corresponding second switch 34_4 and outputting to the data line 32_1. In addition, a logic “1” signal of the second flag register 24_2 corresponding to the memory word 11_2 is input to the AND gate 20_4 via the OR gate 21_4. Therefore, when a match between the attribute IV and the data 'D' is detected in the memory word 11_4 and a match signal of logic '1' is output to the match line 14_4, the match output to the match result latch control line 25 In response to the result latch signal S1, a signal of logic “1” is latched in the corresponding first and second flag registers 23_4 and 24_4. At this time, the logic '1' signal output to the attribute match line 30_4 is latched in the corresponding third flag register 31_4, the corresponding first switch 33_4 is turned on, and the second flag register 24_4 A signal of logic “1” is output to the data line 32_1. Further, in this second search, since the logic “0” indicating the attribute mismatch is output to the attribute match line 30_2 corresponding to the memory word 11_2, “0” is stored in the corresponding third flag register 31_2. The first switch 33_2 corresponding to the memory word 11_2 is turned off.
[0061]
As a result, the logic '1' signal of the second flag register 24_4 corresponding to the memory word 11_4 is input to the priority encoder 15 (see FIG. 9), and the address of the memory word 11_4 is obtained. It is known in advance that attribute IV is stored in 11_4, and for example, when it is desired to read data of attribute III in the same group, 1 is subtracted from the obtained address to obtain the address of memory word 11_3, The address may be input to the address decoder 16 to read the contents of the memory word 11_3. In the second search, when a search is performed using reference data consisting of attribute IV and data 'B' instead of reference data consisting of attribute IV and data 'D', for memory word 11_4, Since the attributes match, the second switch 34_4 is turned on and the logic '1' signal output to the data line 32_1 is taken in. However, since the data is different, the match line 14_4 has a logic '0' indicating a mismatch. The logic '0' indicating that no match has been detected is latched in the first and second flag registers 23_4 and 24_4. Also, the attribute does not match for the memory word 11_2 that matches the data 'B', and therefore neither the attribute nor the data match.
[0062]
As described above, in the embodiment shown in FIG. 4, even in the same group, even if the data is stored in memory words that are separated from each other, or the data is searched in the reverse order. You can also search.
Here, the data lines 32_1, 32_2,... In the above embodiment are fixed in length assuming that the number of data belonging to one group is determined in advance. When the data line is provided, it is necessary to estimate the maximum number of data belonging to one group and to provide a data line having a length corresponding to the maximum number of data. In this case, when a data group is constituted by a smaller number of data than the maximum, a useless memory word is generated. Therefore, it is preferable that the data line has a variable length according to the number of data belonging to one group.
[0063]
FIG. 5 is a schematic diagram showing one method for realizing a variable-length data line.
A data line 32 extends over a plurality of memory words 11_1, 11_2, 11_3,..., And each switch corresponding to each of the other memory words 11_2, 11_3,. 40_2, 40_3, 40_4,... Are arranged in series with each other. Each of these switches 40_2, 40_3, 40_4,... Is arranged between the corresponding memory word 11_2, 11_3, 11_4,... And the memory word 11_1, 11_2, 11_3,. Of the switches 40_2, 40_3, 40_4,..., Every other switch 40_2, 40_4, 40_6,... Is turned on by the first switch control signal output to the first control line 41. 40_3, 40_7,... Are turned on by the second switch control signal output to the second control line 42, and every seventh switch 40_5,... Among the remaining switches is output to the third control line 43. It is turned on by the switch control signal.
[0064]
When the number of data constituting one data group is 2, every other switch 40_2, 40_4, 40_6,... Is turned on by outputting a first switch control signal to the first control line 41. As a result, a disconnected data line is formed for each of the two memory words 11_1; 11_2; 11_3, 11_4; 11_5, 11_6; When the number of data constituting one data group is 4, the first switch control signal is output to the first control line 41 and the second switch control signal is output to the second control line 42. Then, a data line cut for each of the four memory words 11_1, 11_2; 11_3, 11_4; 11_5, 11_6,. Similarly, when the number of data constituting one data group is 8, the first and second switch control signals are output to the first control line 41 and the second control line 42, respectively, and the third control is performed. A third switch control signal is output to the line 43. As a result, a disconnected data line is formed for each of the eight memory words 11_1,..., 11_8;
[0065]
According to this method, when the number of data constituting one data group is a multiple of 2, no vacancy occurs in the memory word, but when the number of data other than a multiple of 2, for example, 3, 5, 9, etc., the vacant memory A word will be generated. If a large number of switches 40_2, 40_3,... Can be arbitrarily turned on / off so that this empty memory word does not occur, the number of control lines becomes large, and switch control signals are output to these control lines. The control circuit to perform becomes complicated. Therefore, the method shown in FIG. 5 is not suitable for arbitrarily controlling the length of the data line.
[0066]
FIG. 6 is a schematic diagram showing another method for realizing a variable data line.
A data line 32 extends over a large number of memory words, and switches 40_2, 40_3, 40_4,... Corresponding to the other memory words other than the uppermost memory word are connected to the data line 32 in series. This is the same as in the case of FIG. Each memory word is provided with attribute storage units 11_1_1, 11_2_1, 11_3_1,..., And the attribute storage units 11_1_1, 11_2_1, 11_3_1,. Stored. In this example, depending on whether the attribute stored in the attribute storage unit 11_1_1, 11_2_1, 11_3_1,... Is the attribute I or the other attributes II, III, IV, the corresponding switch is left off. In the case of other attributes II, III, and IV, the corresponding switches are turned on. With this configuration, the data of the attribute I is arranged at the head of each data group regardless of the number of data constituting one data group or the mixed data groups having different data numbers. As a result, a data line that is automatically cut for each of a sufficient number of memory words is formed.
[0067]
FIG. 7 is a circuit diagram illustrating an example of an attribute determination circuit that determines whether an attribute is I or other.
Here, “000” is assigned to the attribute I, and when the attribute stored in the attribute storage unit 11 — i — 1 is the attribute I (“000”), “0” is output from the OR gate, and thus the switch configured by the transistor 40 40 'is turned off, and the data lines on both sides of the transistor 40' are electrically disconnected. When the attribute stored in the attribute storage unit 11 — i — 1 is an attribute other than the attribute I, “1” is output from the OR gate, the transistor 40 is turned on, and the data lines on both sides of the transistor are connected.
[0068]
4 can adjust the lengths of the data lines 32_1, 32_2,... According to the number of data constituting one data group. Of course, instead of using attribute data, the length of the data line may be adjusted by controlling the switch with a dedicated control line.
Next, an embodiment of the second associative memory of the present invention in which the technical idea of the present invention is applied to the associative memory shown in FIG. 4 will be described.
[0069]
FIG. 8 is a circuit diagram showing the characteristic part of one embodiment of the second associative memory of the present invention. The components corresponding to the respective components of the first associative memory of the present invention shown in FIG. 1 are indicated by the numbers corresponding to the numbers given in FIG. 1, and the differences will be mainly described.
FIG. 8 shows the memory word group storing the data group with the group number n among the data groups shown in FIG. 3, that is, the memory word group having the highest priority among the memory word groups in the empty state. Yes.
[0070]
In the associative memory shown in FIG. 8, each memory word..., 11 is similar to the associative memory shown in FIG. 1 n, 11 2 n, ..., 11 1 Flag registers ..., 51 corresponding to n + 1, ... 1 n, 51 2 n, ..., 51 1 n + 1,... are provided, but these flag registers... 1 n, 51 2 n, ..., 51 1 As described later, n + 1,... are controlled collectively for each memory word group, but the effective flag register is the head flag register for each memory word group.
[0071]
Each memory word ..., 11 1 n, 11 2 n, ..., 11 1 n + 1,... are attribute storage units for storing attributes,. 1 1 n, 11 2 1 n, ..., 11 1 1 n + 1,..., a data storage unit for storing data, 11 1 2 n, 11 2 2 n, ..., 11 1 2 n + 1,... However, in FIG. 8, for convenience of illustration, the attribute storage unit 11 1 1 n, 11 2 1 n, ..., 11 1 1 n + 1,... and data storage unit 11 1 2 n, 11 2 2 n, ..., 11 1 2 n + 1,... are illustrated at positions separated from each other.
[0072]
Here, each memory word group corresponding to the group number n and the group number n + 1 is in an empty state, and therefore the flag register 51 corresponding to those memory word groups. 1 n, 51 2 n, 51 3 n, 51 4 n, 51 1 In n + 1,..., a logic “1” flag indicating an empty state is stored.
First transistor ... 81 1 n, 81 2 n, ..., 81 1 n + 1,... are corresponding attribute storage units ..., 11 1 1 n, 11 2 1 n, ..., 11 1 1 .., 11 is a transistor whose ON / OFF is controlled by a control line extending from n + 1,. 1 1 n, 11 1 1 Only n + 1,... are turned on. Therefore, the first variable length data line 83 corresponding to the group number n. n is a flag register 51 1 A signal of logic ‘1’ (‘H’ level) stored in n indicating a free state is output, and the signal is output from the four multiple selection separation circuits 52 in the memory word group corresponding to the group number n. 1 n, 52 2 n, 52 3 n, 52 4 n. Further, the logic of the signal of the first variable length data line 83-n is inverted, and four AND gates 53 in the memory word group corresponding to the group number n are obtained. 1 n, 53 2 n, 53 3 n, 53 4 n.
[0073]
The same applies to the memory word group corresponding to the group number n + 1. 1 The logic ‘1’ signal stored in n + 1 is the first transistor 81. 1 n + 1, first variable length data line 83 Four multi-separation selection circuits 52 via n + 1 1 n + 1,... and logic are inverted, and four AND gates 53 1 n + 1,...
[0074]
As shown in FIG. 3, when a valid data group is stored in the memory word group corresponding to 1, 2,..., Group number n-1, the memory word group corresponding to group number n is provided. Four multiple separation selection circuits 52 1 n, 52 2 n, 52 3 n, 52 4 n is the uppermost multiple separation selection circuit 52 1 A logic “1” (“H” level) signal indicating the highest priority is output from n. Multiple separation selection circuit 52 1 n, 52 2 n, 52 1 On the output side of n + 1,..., second transistors. 1 n, 82 2 n, 82 1 n + 1,... are provided. This second transistor ..., 82 1 n, 82 2 n, 82 1 n + 1,... are first transistors,. 1 n, 81 2 n, ..., 81 1 Similarly to n + 1,..., attribute storage units. 1 1 n, 11 2 1 n, ..., 11 1 1 .. are transistors that are turned on only when attribute I is stored in n + 1,. 1 The signal of logic ‘1’ output from n is the second transistor 82. 1 n through the second variable length data line 84 output to n. Here, the memory word group corresponding to the group number n is the highest priority memory word group, and therefore the multiple separation selection circuit 52 for the memory word group corresponding to the group number n + 1. 1 The output of n + 1 is logic ‘0’, and the second variable length data line 84 of the memory word group corresponding to the group number n + 1. In n + 1, the multiple separation selection circuit 52 1 A logic “0” signal, which is an output of n + 1, is supplied.
[0075]
Each attribute storage unit 11 1 1 n, 11 2 1 n, ..., 11 1 1 From n + 1,..., an attribute match line for which a logic '1' ('H' level) signal is output upon receiving a match of attributes at the time of retrieval ..., 30 1 n, 30 2 n, 30 1 n + 1,... extend and corresponding AND gates. 1 n, 53 2 n, 53 1 are connected to n + 1,... input terminals. Also, each data storage unit ..., 11 1 2 n, 11 2 2 n, ..., 11 1 2 From n + 1,..., a data match line that receives a data match at the time of retrieval and outputs a logic '1' ('H' level) signal. 1 n, 14 2 n, 14 1 n + 1,... extend, and the attribute match line ..., 30 1 n, 30 2 n, 30 1 In the same manner as n + 1,. 1 n, 53 2 n, 53 1 are connected to n + 1,... input terminals.
[0076]
Here, it is assumed that the data retrieval is performed by inputting the retrieval data of the attribute II and the data 'B', and the attribute storage unit 11 2 1 Memory word 11 in which attribute II is stored in n 2 n data storage unit 11 2 2 If data “B” happens to be stored in n, the attribute match line 30 is received in response to the attribute match. 2 n becomes 'H' level, and the data match line 14 is received in response to the data match. 2 n also becomes the “H” level, but the first variable length data line 83 Since n is at the “H” level indicating an empty state, the AND gate 53 2 No signal of “H” level indicating coincidence is output from n. That is, the memory word group in the empty state does not participate in the search.
[0077]
Regardless of whether or not a match is detected in any of the memory word groups during this search, the additional write control circuit 72 (see FIG. 1) sends “1” to the word line activation timing signal line 68. Is output. Then, the second memory word 11 from the top in FIG. 2 AND gate 67 corresponding to n 2 n input is all '1' and AND gate 67 2 Word line 24 extending to the output side of n 2 n becomes ‘1’ and the memory word 11 2 Search data is written to n. The timing at which this search data is written is at the same time as the search, and is therefore independent of whether or not a match has occurred in the search.
[0078]
After the above search and the writing of the search data are performed a predetermined number of times, information indicating whether or not a desired data group has been finally detected is input to the additional write control circuit 72 (see FIG. 1). In the write-once control circuit 72, if a desired data group is detected in any of the memory word groups, nothing is performed thereafter. That is, although the search data is written in the memory word group corresponding to the group number n shown in FIG. 8 every time the search is performed, the flag register 51 corresponding to the memory word group is written. 1 n, 51 2 n, 51 3 n, 51 4 The empty flag “1” is still stored in n, and the memory word group corresponding to the group number n still remains in an empty state that does not contribute to the search.
[0079]
On the other hand, when the entire coincidence detection circuit 71 does not detect a desired data group across all memory word groups, the additional write control circuit 72 (see FIG. 1) operates as follows. That is, flag registers... 51 1 n, 51 2 n, ..., 51 1 A logic “0” signal is applied to the empty flag data line 66 connected to n + 1,..., and a clock pulse of “1” is applied to the empty flag clock signal line 65 in this state. Then, the second variable length data line 84 extending to the memory word group corresponding to the group number n shown in the figure. Since a logic ‘1’ signal is output to n, the ‘1’ clock pulse applied to the empty flag clock signal line 65 has four AND gates 61. 1 n, 61 2 n, 61 3 n, 61 4 n through each of the four flag registers 51 1 n, 51 2 n, 51 3 n, 51 4 n, and these four flag registers 51 1 n, 51 2 n, 51 3 n, 51 4 A flag of logic “0” indicating that a valid data group is recorded is stored in n.
[0080]
Multiple selection separation circuit ... 52 1 n, 52 2 n, ..., 52 1 In n + 1,..., the flag register 51 corresponding to the group number n 1 n, 51 2 n, 51 3 n, 51 4 As '0' is stored in n, the highest priority is selected from among the memory word groups corresponding to the flag register storing the empty flag '1' other than the memory word group corresponding to the group number n. Memory word group (memory word group corresponding to the group number n + 1 in the example shown here) is detected.
[0081]
In the embodiment shown in FIG. 8, in response to the fact that no desired data group is stored in any of the memory word groups, the write-once control circuit 72 automatically selects the highest priority memory word group (FIG. In the example of FIG. 8, a flag of logic '0' for releasing the empty state is written in the flag register corresponding to the memory word group corresponding to the group number n), but a predetermined control signal can be input to the additional write control circuit 72 from the outside. In this case, the write-once control circuit 72 may release the empty state of the top-priority memory word group after waiting for the control signal to be input from the outside.
[0082]
【The invention's effect】
As described above, the associative memory of the present invention stores the search data as it is at the same time as the search, so that the unregistered data is additionally written at a high speed. Therefore, the associative memory of the present invention is suitable for a LAN system, for example.
[Brief description of the drawings]
FIG. 1 is a circuit diagram showing a characteristic part of an embodiment of a first content addressable memory according to the present invention;
FIG. 2 is a circuit diagram of a multiple selection separation circuit.
FIG. 3 is a diagram illustrating an example of group structure data.
FIG. 4 is a block diagram showing an example of an associative memory suitable for handling group structure data.
FIG. 5 is a schematic diagram showing one method for realizing a variable-length data line.
FIG. 6 is a schematic diagram showing another method for realizing a variable data line.
FIG. 7 is a circuit diagram of an example of an attribute determination circuit that determines whether an attribute is I or other.
FIG. 8 is a circuit diagram showing a characteristic part of an embodiment of a second associative memory according to the present invention;
FIG. 9 is a circuit block diagram showing an example of a conventional associative memory.
FIG. 10 is a detailed circuit diagram showing one memory word in the content addressable memory.
FIG. 11 is a diagram illustrating an example of a LAN.
FIG. 12 is a functional explanatory diagram of a bridge.
[Explanation of symbols]
11, 11_1 n, 11_2 n, ..., 11_1 n + 1 memory word
11_1_1 n, 11_2_1 n, ..., 11_1 1 n + 1
Attribute storage
11_1_2 n, 11_2_2 n, ..., 11_1 2 n + 1
Data storage
14 Matching line
14_1 n, 14_2 n, ..., 14_1 n + 1 data match line
30_1 n, 30_2 n, ..., 30_1 n + 1 attribute match line
51, 51_1 n, 51_2 n, ..., 51_1 n + 1 flag register
52, 52_1 n, 52_2 n, ..., 52_1 n + 1
Multiple selection separation circuit

Claims

A plurality of memory word groups each including a plurality of memory words for storing a plurality of data constituting one data group consisting of a set of a plurality of stored data for each data are input each time search data is input. A search for matching between all or a part of the bit pattern of the search data and all or a part of the bit pattern corresponding to the bit pattern in the data stored in the memory word is performed once or a plurality of consecutive times. In all the predetermined number of coincidence searches, all or a part of the input search data or each predetermined part of the bit pattern and all or a part of the data stored in the same memory word group corresponding to the bit pattern The presence of a data group corresponding to the search data input a predetermined number of times. In out to the associative memory,
During the predetermined number of matching searches, the input search data is not stored in the valid data group to be searched for each search, and is therefore in a free state in which overwriting is allowed. An associative memory comprising a data write circuit for writing to any memory word in one memory word group selected from the word group .

A corresponding memory word group provided corresponding to each of the memory word groups is a memory word group in a storage state in which the valid data group is stored, or a memory word group in the empty state. A flag register storing a flag indicating
As a result of the predetermined number of matching searches, when a data group corresponding to the search data input the predetermined number of times is not detected, a flag indicating the storage state is stored in the flag register corresponding to the one memory word group 2. An associative memory according to claim 1, further comprising a flag changing circuit for storing

A corresponding memory word group provided corresponding to each of the memory word groups is a memory word group in a storage state in which the valid data group is stored, or a memory word group in the empty state. A flag register storing a flag indicating
Receiving a predetermined instruction signal inputted from outside, the claims in the flag register corresponding to said one memory word groups, characterized by comprising a flag change circuit for storing a flag indicating the storage state 1. The associative memory according to 1 .