JP3645293B2

JP3645293B2 - Associative memory

Info

Publication number: JP3645293B2
Application number: JP25836894A
Authority: JP
Inventors: 洋笹間; 正人米田
Original assignee: Kawasaki Microelectronics Inc
Current assignee: Kawasaki Microelectronics Inc
Priority date: 1994-10-24
Filing date: 1994-10-24
Publication date: 2005-05-11
Anticipated expiration: 2020-05-11
Also published as: JPH08124388A

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. 11 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, the data stored in the memory word 11b corresponding to the word line 17b to which the access signal is output is read to the 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. 12 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. 12 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. 12, 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]
Note that the memory structure of the associative memory shown in FIG. 12 is merely an example, and various structures have been proposed (see, for example, Japanese Patent Application No. 5-216424).
[0017]
[Problems to be solved by the invention]
When associative memory is applied to various applications that require searching, it searches with the contents of a part of the data stored in one memory word and outputs the data of another part of the matched memory word I often want to do it. At this time, if there is no memory word for storing data that matches the search data, there is a case where it is desired to newly register the search data and accompanying data corresponding to the portion to be output. However, in the conventional associative memory, the search operation and the registration, that is, the write operation are performed completely separately. For this reason, after a mismatch is detected as a result of the search, the search data and the accompanying data must be combined and then written to the associative memory. The search data once given for the search is given again as part of the registration data. Inefficiency that must be generated.
[0018]
In view of the above circumstances, an object of the present invention is to provide an associative memory capable of efficiently and rapidly realizing new registration of data that has been found to be unregistered as a result of a search as a result of a search. .
[0019]
[Means for Solving the Problems]
The first associative memory of the present invention that achieves the above-described object provides:
Corresponding to the bit pattern of the memory word for storing each data, the bit pattern of all or part of the input search data provided corresponding to the memory word, and the data stored in the memory word In an associative memory including a coincidence detection circuit that detects coincidence / non-coincidence with all or part of the bit pattern
If none of the coincidence detection circuits outputs a coincidence signal indicating that a coincidence has been detected, the valid data to be searched for in the memory word is not stored, and therefore overwriting is allowed. A search data write circuit that selects one of the empty memory words to be stored and stores the search data in the selected memory word;
An accompanying data writing area designating circuit for designating an unmasked bit position as an accompanying data writing area for writing accompanying data related to the search data by masking a part of bits of the selected memory word When,
The accompanying data writing area comprises an accompanying data writing circuit for storing the accompanying data.
[0020]
Here, the first associative memory of the present invention is
A flag is stored corresponding to the memory word and indicating whether the memory word is a memory word in a storage state in which the valid data is stored or a memory word in the free state. Flag register
A flag changing circuit for storing a flag indicating the storage state in the flag register corresponding to the selected memory word when the match signal is not output from any of the match detection circuits;
It may be provided.
[0021]
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 comparison is made 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 of the data stored in the memory word, and from one or more times All of the search data input in all the matching searches or a match with all or a part of the data stored in the same memory word group as each predetermined part of the bit pattern corresponds to the bit pattern. An associative memory that detects the presence of a data group corresponding to the search data input a predetermined number of times when detected Oite,
The 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 to be searched is stored, or the valid data group is A flag register in which a flag indicating whether the memory word group is in an empty state that is not stored and thus overwritten is allowed to be stored;
During the predetermined number of matching searches, each time a search is performed, the input search data is written to any memory word in the memory word group selected from the free memory word group. A data writing circuit;
A memory word designating circuit for designating any memory word in the empty memory word group in which the search data is written;
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, the memory word specified by the memory word specifying circuit is associated with the search data. An accompanying data writing circuit for writing data;
As a result of the predetermined number of matching searches, when the data group corresponding to the search data input the predetermined number of times is not detected, the flag register corresponding to the selected memory word group indicates the storage state. A flag change circuit for storing a flag;
It is characterized by comprising.
[0022]
Here, the second associative memory of the present invention is
By masking some bits of the memory word designated by the memory word designating circuit, an unmasked bit position is designated as an accompanying data write area for writing accompanying data related to the search data. A data write area specification circuit is provided.
The accompanying data writing circuit may store the accompanying data in the accompanying data writing area.
[0023]
Alternatively, in the second associative memory of the present invention, the memory word designating circuit includes:
A memory word group designating circuit for designating the empty memory word group in which the search data is written;
And a memory word position specifying circuit in the memory word group for relatively specifying the position of the memory word in the memory word group specified by the memory word group specifying circuit.
[0024]
The third associative memory of the present invention is
All or part of the input search data group comprising 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 In an associative memory for detecting coincidence / non-coincidence between all or a part of bit patterns corresponding to the bit pattern in the group stored in the memory word group
A memory word group designating circuit for designating one of the memory word groups;
A memory word position specifying circuit in the memory word group for relatively specifying the position of the memory word in the memory word group specified by the memory word group specifying circuit;
And a memory word writing / reading circuit for writing / reading data to / from the memory word corresponding to the designated memory word position.
[0025]
[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, a match was not detected as in the prior art. When registering data, it is only necessary to write the remaining accompanying data portion, and the processing efficiency is improved.
[0026]
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.
[0027]
The technique proposed there is for eliminating the need to manage a memory word in an empty state externally. In the registration of unregistered data, the search data is again stored in the memory after the search operation. Need to give to the word. In this respect, the present invention is significantly different from the proposed technique described above.
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.
[0028]
In such an associative memory, for example, a group of 100 data including 90 search target data and 10 output target data (accompanying data) is stored, and the search data is input. Consider a case where the search operation is repeated 90 times to detect the presence of a desired data group and the accompanying data of the desired data group is output 10 times. At this time, since a desired data group does not exist, when a new data group is registered, when a conventional associative memory is used, a new effective data group is registered only after data is written 100 times after searching. It will be.
[0029]
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 90 searches. If the group does not exist, the search data has already been written, so the data group can be registered by writing only the accompanying data ten times. For this reason, the trouble of writing data is greatly reduced and the processing speed is increased.
[0030]
The third associative memory according to the present invention designates a specific memory word by dividing it into a memory word group address and a relative address in the memory word group, and therefore handles data having a group structure. In this case, the complicated process of managing the absolute address of each memory word and designating the absolute address is avoided.
[0031]
【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.
[0032]
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 set to “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 overwritten is stored (this is referred to as the corresponding memory word 11 being “free”), the empty flag of “1” is stored. Is memorized. 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.
[0033]
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.
[0034]
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.
[0035]
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.
[0036]
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.
[0037]
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. 11 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.
[0038]
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. Further, the match line 140 extends to the priority encoder 15 shown in FIG. 11 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.
[0039]
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.
[0040]
FIG. 3 is a diagram showing a circuit example of one bit of the bit line drive circuit 70. The partial circuit 70_1 shown here includes two OR gates 93_1 and 94_1 arranged corresponding to a pair of bits and bit bars. The two OR gates 93_1 and 94_1 include search mask data lines. 98_1 and the write mask data line 99_1 are connected in common. Further, the bit data line 97_1 is directly connected to the OR gate 93_1, and the data applied to the bit data line 97_1 is input to the OR gate 93_1 as it is. On the other hand, the data applied to the bit data line 97_1 is inverted and input to the OR gate 94_1 through the inverter 95_1. The outputs of the two OR gates 93_1 and 94_1 are respectively input to the bit line drivers 91_1 and 92_1. When a logic “1” pulse is applied to the bit line driver signal line 96, the outputs of the OR gates 93_1 and 94_1 The signal is applied to the bit line 23_1 and the bit bar line 26_1 through the line drivers 91_1 and 92_1.
[0041]
When a search is performed, a signal of logic “1” is applied to the search mask data line 98_1 for a bit not to be searched, that is, a bit to be masked, and then a logic “1” is applied to the bit line drive signal line 96. When a pulse is applied, both the bit line 23 and the bit bar line 26 become logic “1”, and a mask search for the corresponding bit is realized. At this time, writing is not performed on the mask-searched bits of the memory word 11 at the bottom of FIG.
[0042]
By the operation of the bit line drive circuit 70 as described above, the search data is written into the memory word 11 at the bottom of FIG. 1 simultaneously with the search.
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.
[0043]
On the other hand, for a bit to be searched, that is, a bit that is not masked, a signal of logic “0” is given to the search mask data line 98_1, the search data is put on the bit data line 97_1, and then the bit line drive signal line. A pulse of logic “1” is given to 96. By doing so, search data is given to the bit line, and data obtained by inverting the search data is given to the bit bar line, and search without masking is performed, and writing to the relevant bit of the memory word 11 at the bottom of FIG. 1 is performed. Is called.
[0044]
On the other hand, when all the memory words 11 are not matched in the entire match detection circuit 71, that is, when unregistered data is detected and data is registered, the following operation is performed.
Similarly to the search, the word line 24 corresponding to the memory word 11 at the bottom in FIG. 1 is activated and data is written. At this time, in the bit line drive circuit 70, a logic “1” signal is applied to the write mask data line 99_1 shown in FIG. For the bit, a signal of logic “0” is applied to the write mask data line 99_1. Further, by adding the accompanying data to the bit data line 97_1 and applying a logic “1” pulse to the bit line drive signal line 96, only the accompanying data is written while retaining the search data written at the time of the search. Can do.
[0045]
At this time, the write-once control circuit 72 gives a logic “0” signal to the empty flag data line 66 connected to the flag register 51, and gives a clock pulse of “1” to the empty flag clock signal line 65 in this state. . Then, the word line 24 of the lowermost memory word 11 in FIG. 1 is “1”, and the signal “1” is input to the bottom AND gate 61 via the signal line 60. Therefore, 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.
[0046]
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.
In the above description, the accompanying data is written only to bits other than the bit in which the search data is written. However, the signals of the search mask data line 98_1 and the write mask data line 99_1 are appropriately controlled. It goes without saying that various data registration methods can be realized.
[0047]
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. 4 is a diagram illustrating an example of data forming a group structure.
FIG. 4 shows a data structure in which four data with attributes I, II, III, and IV are set 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. 5 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 shown in FIG. 11 (not shown in FIG. 5), 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 illustrated, each of the memory words 11_1, 11_2, 11_3, and 11_4 has an attribute I, data 'A', attribute II, data 'B', and 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.
[0055]
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.
[0056]
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. .
[0057]
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.
[0058]
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.
[0059]
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.
[0060]
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.
[0061]
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.
[0062]
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. 11), 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.
[0063]
As described above, in the embodiment shown in FIG. 5, 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.
[0064]
FIG. 6 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 the 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.
[0065]
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;
[0066]
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. 6 is not suitable for arbitrarily controlling the length of the data line.
[0067]
FIG. 7 is a schematic diagram showing another method for realizing a variable data line.
A data line 32 extends over a number of memory words, and switches 40_2, 40_3, 40_4,... Corresponding to the other memory words other than the uppermost memory word connected to the data line 32 in series. This is the same as in the case of FIG. Each memory word includes an attribute storage unit 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.
[0068]
FIG. 8 is a circuit diagram showing an example of an attribute determination circuit that determines whether the 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.
[0069]
As described above, in the associative memory shown in FIG. 5, the length of the data lines 32_1, 32_2,... Can be adjusted 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. 5 will be described.
[0070]
FIG. 9 is a circuit diagram showing the characterizing portion 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. 9 shows the memory word group storing the data group of group number n among the data groups shown in FIG. Yes.
[0071]
In the associative memory shown in FIG. 9, 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. These flag registers ..., 51 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.
[0072]
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. 9, 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.
[0073]
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.
[0074]
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,...
[0075]
As shown in FIG. 4, when a valid data group is stored in the memory word group corresponding to the group numbers 1, 2,..., N−1, the memory word group corresponding to the 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.
[0076]
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.
[0077]
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.
[0078]
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.
[0079]
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. 9 each 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.
[0080]
On the other hand, when the desired data group does not exist in all the memory word groups in the entire match detection circuit 71, that is, when the unregistered data group is detected and the data group is registered, the following operation is performed.
As described above, search data is written simultaneously with the search in the memory word corresponding to the attribute to be searched. Therefore, only the accompanying data needs to be written for registering the data group.
[0081]
Here, it is assumed that accompanying data is written in a memory word corresponding to attribute III. At this time, as in the search, the attribute III and the accompanying data are input as a pair. Each attribute storage unit 11 1 1 n, 11 2 1 n, ..., 11 1 1 For n + 1,..., the memory word 11 in FIG. 3 Attribute match line 30 corresponding to n 3 A logic “1” signal is output to n. At this time, a signal of logic “1” is output from the additional write control circuit 72 (see FIG. 1) to the word activation timing signal line 68, and the third memory word 11 from the top in FIG. 3 AND gate 67 corresponding to n 3 word line 24 via n 3 n becomes “1”, and the accompanying data to be stored at this time is the data storage unit... 11 1 2 n, 11 2 2 n, ..., 11 1 2 is applied to the bit lines corresponding to n + 1,... and the inverted signal of the accompanying data is applied to the bit bar lines. 3 The accompanying data is written to n.
[0082]
The above-mentioned accompanying data is written by a plurality of separation circuits... 1 n, 52 2 n, ..., 52 1 Among the memory word groups corresponding to the group number n in an empty state designated by n + 1,. 3 2 for n. Similarly, accompanying data can be written in a memory word in which other attribute data is stored.
[0083]
As described above, the search data and the accompanying data are written in the memory word group corresponding to the group number n. Thereafter, the write-once control circuit 72 (see FIG. 1) sends 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 is represented by 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.
[0084]
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.
[0085]
In the above description, the memory word in which the search data is stored and the memory word in which the accompanying data are stored are described as separate ones. However, the second associative memory according to the present invention also includes Similar to the first associative memory, both search data and accompanying data can be stored in the same memory word by performing mask control at the time of searching and at the time of writing.
[0086]
In the embodiment shown in FIG. 9, the memory word to which the search data is to be written is determined using the output of the multiple separation circuit and the attribute match line, but the present invention is not limited to the embodiment of FIG. For example, the priority decoder is configured by inputting the output of the multi-separation circuit 52 to the encoder, and the output is obtained by adding the relative address in the memory word group corresponding to the attribute to the output as an address. The memory word to be written may be determined by inputting into (see FIG. 11), and includes various methods.
[0087]
In the second associative memory embodiment of the present invention, there is provided a method of selectively activating one memory word in a memory word group by selecting a memory word group by a multiple selection separation circuit and further detecting attribute matching. Although shown, it is very effective to apply this concept when storing data having a group structure as shown in FIG.
FIG. 10 is a diagram showing each data having the data structure shown in FIG. 4 and the absolute address of a memory word storing each data. Here, as described above, in response to the fact that no match was detected as a result of the search, the associated data corresponding to attribute III is registered in the memory word group corresponding to the group number n in the highest priority free state. In this case, in order to specify that data corresponding to the attribute III is to be written, it is only necessary to perform a match comparison by the attribute III, and there is no need for the outside to know the group number of the memory word group that is currently in the highest priority empty state. .
[0088]
On the other hand, in order to perform the same writing of the accompanying data by designating the memory word by the absolute address, it is necessary to know that the group number of the memory word group in the empty state having the highest priority at present is n. Yes, it is necessary to specify the absolute address 4n-2 which is obtained after knowing this, and the processing becomes complicated.
As described above, when a data group having a data structure as shown in FIG. 4 or FIG. 10 is handled, the address number is managed by the group number of the memory word group and the position of the memory word in the memory word group, rather than the absolute address management. It is preferable to do relative.
[0089]
The address management of data having a group structure as described above is not limited to the second associative memory embodiment of the present invention, and is widely effective for an associative memory having data having a group structure.
[0090]
【The invention's effect】
As described above, the content addressable memory of the present invention stores search data at the same time as search. Therefore, it is only necessary to write only accompanying data for additional writing of unregistered data. Done at high speed.
[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 a circuit example of one bit of a bit line drive circuit.
FIG. 4 is a diagram illustrating an example of group structure data.
FIG. 5 is a block diagram showing an example of an associative memory suitable for handling group structure data.
FIG. 6 is a schematic diagram showing one method for realizing a variable-length data line.
FIG. 7 is a schematic diagram showing another method for realizing a variable data line.
FIG. 8 is a circuit diagram of an example of an attribute determination circuit that determines whether an attribute is I or other.
FIG. 9 is a circuit diagram showing a characteristic part of an embodiment of a second associative memory according to the present invention;
FIG. 10 is a diagram illustrating a correspondence between group structure data and absolute addresses;
FIG. 11 is a circuit block diagram showing an example of a conventional associative memory.
FIG. 12 is a detailed circuit diagram showing one memory word in the associative memory.
[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 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 comparison is made 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 of the data stored in the memory word, and from one or more times All of the search data input in all the matching searches or a match with all or a part of the data stored in the same memory word group as each predetermined part of the bit pattern corresponds to the bit pattern. An associative memory that detects the presence of a data group corresponding to the search data input a predetermined number of times when detected Oite,
The 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 to be searched is stored, or the valid data group is A flag register in which a flag indicating whether the memory word group is in an empty state that is not stored and thus overwritten is allowed, and
During the predetermined number of matching searches, each time a search is performed, the input search data is written to any memory word in the memory word group selected from the empty memory word group. A data writing circuit;
A memory word designating circuit for designating any memory word in the empty memory word group in which the search data is written;
As a result of the predetermined number of coincidence searches, if no data group corresponding to the search data input the predetermined number of times is detected, the memory word specified by the memory word specifying circuit is associated with the search data. An accompanying data writing circuit for writing data;
As a result of the predetermined number of coincidence searches, when the data group corresponding to the search data input the predetermined number of times is not detected, the flag register corresponding to the selected memory word group indicates the storage state. An associative memory comprising a flag changing circuit for storing a flag .

By masking a part of bits of the memory word designated by the memory word designating circuit, an unmasked bit position is designated as an accompanying data write area for writing accompanying data related to the search data. A data write area specification circuit is provided.
2. The associative memory according to claim 1, wherein the accompanying data writing circuit stores the accompanying data in the accompanying data writing area .

The memory word designating circuit is
A memory word group designating circuit for designating the empty memory word group in which the search data is written;
Claim 1, characterized in that with a memory word groups within a memory word location specified circuit relatively specifying the position of the memory words in the memory word groups designated by the memory word groups specifying circuit Or the associative memory of 2 .

All or part of the input search data group comprising 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 In an associative memory for detecting coincidence / non-coincidence between all or a part of bit patterns corresponding to the bit pattern in the group stored in the memory word group
A memory word group designating circuit for designating one of the memory word groups;
A memory word position specifying circuit in a memory word group for relatively specifying a position of a memory word in a memory word group specified by the memory word group specifying circuit;
The memory word corresponding to the specified memory word location, associative memory you characterized by comprising the data writing, and a memory word write read circuit for reading.