(57)【特許請求の範囲】
【請求項１】
配列された複数のメモリワードそれぞれに各ディジタルデータを書込み自在に記憶しておき、検索データを入力し、入力された検索データの全部もしくは所定の一部のビットパターンと一致するビットパターンを有するディジタルデータが記憶されたメモリワードを検索する連想メモリの使用方法において、
前記複数のメモリワードのうち、検索に使用される第１のメモリワードに、該第１のメモリワードがそれぞれ二分された一方の第１の領域にディジタルデータを格納すると共に、該第１のメモリワードの、該第１の領域を除く第２の領域に、該第１の領域に格納されたディジタルデータの属性を表わす属性データを記憶させ、かつ
前記複数のメモリワードのうち、検索に使用されない第２のメモリワードの前記第２の領域に、前記第１のメモリワードに記憶される属性データのいずれとも値の異なる属性データを記憶させ、
前記連想メモリに所定の属性データと所定のディジタルデータとの組を前記検索データとして入力することにより、該連想メモリに、入力された所定のディジタルデータに対応すると共に入力された所定の属性データが表わす属性を有するディジタルデータが記憶されたメモリワードの検索を行わせることを特徴とする連想メモリの使用方法。
【請求項２】
配列された複数のメモリワードそれぞれに各ディジタルデータを記憶しておき、検索データを入力し、入力された検索データの全部もしくは所定の一部のビットパターンと一致するビットパターンを有するディジタルデータが記憶されたメモリワードを検索する連想メモリにおいて、
前記複数のメモリワードのうち検索に使用される第１のメモリワードが、各ディジタルデータが書込み自在に記憶された第１の領域と、該第１の領域に記憶されたディジタルデータの属性を表わす属性データが書込み自在にもしくは固定的に記憶された第２の領域とを有するとともに、
前記複数の各メモリワードのうち検索に使用されない第２のメモリワードが前記第１のメモリワードに記憶された属性データのいずれとも値の異なる属性データが書込み自在にもしくは固定的に記憶された前記第２の領域を有するものであることを特徴とする連想メモリ。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、従来の一般的な連想メモリの使用方法、およびその使用方法に適合したハードウェア構成を備えた連想メモリに関する。
【０００２】
【従来の技術】
従来より、配列された複数の各メモリワードそれぞれに各ディジタルデータを記憶しておき、検索データを入力し、入力された検索データの全部もしくは所定の一部のビットパターンと一致するビットパターンを有するディジタルデータが記憶されたメモリワードを検索する連想メモリ（Ａｓｓｏｃｉａｔｉｖｅ  Ｍｅｍｏｒｙ，内容アドレス式メモリ；Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）が提案されている。
【０００３】
図２は、連想メモリの一例を表わした回路ブロック図である。
この連想メモリ１０には、ｍビットを１ワードとする、互いに図の横方向に並ぶｍビットのメモリセルからなるメモリワード１１＿１，１１＿２，…，１１＿ｎが多数備えられている。またこの連想メモリ１０は、１ワードの検索データが入力されラッチされる検索レジスタ１２を備え、検索レジスタ１２にラッチされた検索データの全部もしくは所定の一部のビットパターンと、各メモリワード１１＿１，１１＿２，…，１１＿ｎに記憶されたデータのうち上記ビットパターンと対応する部分のビットパターンとの一致不一致が比較され、各メモリワード１１＿１，１１＿２，…，１１＿ｎのそれぞれに対応して備えられた一致線１４＿１，１４＿２，…，１４＿ｎのうちビットパターンが一致したメモリワード１１＿１，１１＿２，…，１１＿ｎに対する一致線１４＿１，１４＿２，…，１４＿ｎに論理‘１’（ここでは５Ｖとする）の一致信号が出力される。それ以外の一致線１４＿１，１４＿２，…，１４＿ｎは論理‘０’（ここでは０Ｖとする）にとどまる。
【０００４】
これらの一致線１４＿１，１４＿２，…，１４＿ｎに出力された信号は、各一致フラグレジスタ１５＿１，１５＿２，…，１５＿ｎに格納される。ここでは、一例として、図示のように、各一致フラグレジスタ１５＿１，１５＿２，…，１５＿ｎにそれぞれ‘０’，‘１’，‘１’，‘０’，…，‘０’，‘０’が格納されたものとする。これらの一致フラグレジスタ１５＿１，１５＿２，…，１５＿ｎに格納された信号はアドレスエンコーダ１６に入力され、このアドレスエンコーダ１６からは論理‘１’の信号が格納された一致フラグレジスタ（ここでは一致フラグレジスタ１５＿２と一致フラグレジスタ１５＿３の２つ）のうちの優先度の高い一致フラグレジスタに対応するアドレス信号が出力される。ここでは、添字が若いほど優先順位が高いものとし、従ってここでは一致フラグレジスタ１５＿２に対応するメモリアドレスが出力される。このアドレスエンコーダ１６から出力されたアドレス信号ＡＤは、必要に応じてデコーダ１７に入力される。デコーダ１７ではこの入力されたアドレス信号ＡＤをデコードして各メモリワード１１＿１，１１＿２，…，１１＿ｎのそれぞれに対応して備えられたワード線１８＿１，１８＿２，…，１８＿ｎのうちの入力されたアドレス信号ＡＤに対応するいずれか１本のワード線（ここではワード線１８＿２）にアクセス信号（ここでは論理‘１’の信号）を出力する。これによりアクセス信号の出力されたワード線１８＿２に対応するメモリワード１１＿２に記憶されているデータが出力レジスタ１９に読出される。
【０００５】
次に、一致フラグレジスタ１５＿２に格納された信号を‘０’に変更することにより、今度は一致フラグレジスタ１５＿３に対応するメモリワード１１＿３のアドレスを得ることができる。
上記のように、連想メモリ１０は、検索データの全部もしくは所定の一部のデータを用いて多数のメモリワード１１＿１，１１＿２，…，１１＿ｎに記憶された内容（データ）を検索し、一致するデータを有するメモリワードのアドレスを得、必要に応じてそのメモリワードに記憶されたデータ全体を読出すことができるように構成されたメモリである。
【０００６】
上記のような連想メモリに記憶されるデータが、複数の属性の付されたデータである場合に、検索の不都合を生じることがある。
図３は、連想メモリに記憶された、属性の付されたデータの配列を示した図である。
連想メモリを構成する多数のメモリワードが４つずつ組にされ、各組内の先頭のメモリワードには、例えば‘氏名’という「属性０」の付されたデータが格納され、各組内の２番目のメモリワードには例えば‘生年月日’という「属性１」の付されたデータが格納され、以下同様にして各組内の３番目、４番目のメモリワードにはそれぞれ「属性２」，「属性３」が付されたデータが格納されるものとする。ここでは、各メモリワードに格納された各データを図示のアルファベットＡ，Ｂ，…で表示している。尚、以下上記のように各属性が付された１組のデータ群を「データセット」と称する。
【０００７】
ここで、図３の最上段に記された属性０のデータが‘Ａ’であり、次段に記された属性１のデータも‘Ａ’であるというように、属性が異なっても同一のビットパターンのデータが格納されることが生じる場合がある。
この場合において、属性０に属するデータ‘Ａ’（例えば氏名‘Ａ’である人）のみを検索したい場合に、データ‘Ａ’を検索データとして入力すると、属性０に属するデータ‘Ａ’のみでなく、他の属性１，２，３に属するデータ‘Ａ’も同時に検索されてしまい、検索後において検索されたデータの中から属性０に属するデータを再度検索し直す等の操作を行う必要があり、その操作が極めて煩雑であり検索にも時間がかかるという問題がある。
【０００８】
このような問題の解決手法が本願出願人より提案されている（特願平５−１８１４４７号参照）。以下、この提案について説明する。
図４は、上記提案に係るメモリ構造図である。
連想メモリを構成する、それぞれがｍビット（例えば１６ビット）からなるメモリワードの上位ｋビット（例えば２ビット）を属性を表わす属性データを格納する領域と定め、また残りのｍ−ｋビット（例えば１６−２＝１４ビット）を、それらの属性の付された本来のデータを格納しておくべき領域と定め、各メモリワードに属性とデータとの双方を格納する。そして検索にあたっては、属性とデータとの双方で検索を行う。例えば「属性０」とデータ‘Ａ’との双方で検索を行えば、図４の最上段に示されたデータが検索されることになる。
【０００９】
図５は、上記の考え方をさらに説明するための、連想メモリのブロック図である。尚、この連想メモリは、説明の都合上描き方がやや異なるのみであって本質的には図２に示す連想メモリと同一のものであるが、説明に不必要なブロックの図示は一部省略されている。また図２に示す連想メモリの各ブロックと同一のブロックには図２に付した番号と同一の番号が付されている。
【００１０】
ｍビットからなる各メモリワード１１＿１，１１＿２，…，１１＿ｎの上位２ビットには属性データを格納し、残りのｍ−２ビットに、各属性の付されたデータを格納する。そして検索にあたっては、検索レジスタ１２の上位２ビットを検索用の属性データが格納される属性検索レジスタ１２＿１とし、検索レジスタ１２の残りの部分（検索データレジスタ１２＿２を、図２を参照して説明した際の、本来の意味における検索レジスタとし、この検索レジスタ１２に属性データと本来の意味における検索データとを格納して検索を行う。これによりその検索に用いられた属性データが表わす属性が付された所望の格納データの検索が行われる。即ち、属性の異なる同一の格納データの検索は排除される。
【００１１】
次に属性データを固定的に記憶しておくように構成された連想メモリの一例について説明する。
図５は、属性データを固定的に記憶しておくように構成された連想メモリの説明にもそのまま用いることができるが、各メモリワード１１＿１，１１＿２，…，１１＿ｎの構成が従来の汎用の連想メモリのメモリワードと異なっている。
【００１２】
図６は、連想メモリを構成する多数のメモリワードのうち、１つのメモリワードの構成を示す回路図である。この回路は、ＳＲＡＭを基本とし、かつ検索データとの一致をＮＡＮＤ型一致検出回路で検出する回路構成の一例である。
図示のメモリワードには、第１の属性ビットセル２０＿１と第２の属性ビットセル２０＿２からなるビットセル群２０と、ｍビット（例えば１６ビット）のＳＲＡＭ構造のメモリセル２１＿１，…，２１＿ｍからなるメモリセル群２１が形成されている。
【００１３】
第１の属性ビットセル２０＿１には、ビット線Ｚｂ１とビットバー線Ｚｂ１＿  の間に互いにシリアルに接続された２つのトランジスタＴ１，Ｔ２が形成されており、これら２つのトランジスタＴ１，Ｔ２の接続点にトランジスタＴＣ１＿１のゲート電極が接続されている。トランジスタＴ１のゲートは論理‘１’に設定されており、トランジスタＴ２のゲートは論理‘０’に設定されている。このとき、図５に示す属性検索レジスタ１２＿１に接続された、ビット線Ｚｂ１に‘１’、ビットバー線Ｚｂ１＿  にその反転信号である‘０’が印加されると、トランジスタＴ１がオンし、ビット線Ｚｂ１の‘１’がトランジスタＴＣ１＿１のゲートに印加されこのトランジスタＴＣ１＿１もオンとなる。この状態が、第１の属性ビットセル２０＿１に関し、この第１の属性ビットセル２０＿１に固定的に記憶された内容と入力された検索用の属性データとが一致した状態である。これとは逆に、ビット線Ｚｂ１に‘０’，ビットバー線Ｚｂ１＿  に‘１’が印加されると、トランジスタＴＣ１＿１のゲートは‘０’となりこのトランジスタＴＣ１＿１はオフとなる。これが、この第１の属性ビットセル２０＿１に関し、不一致の状態である。
【００１４】
同様にして、図６に示す例では、第２の属性ビットセル２０＿２は、そこに格納されたデータが第１の属性ビットセル２０＿１に格納されたデータと逆であり、属性検索レジスタ２０＿１からの信号が‘０’（ビット線Ｚｂ２が‘０’、ビットバー線Ｚｂ２＿  が‘１’）のとき一致の状態となる。
即ち、図６に示す例では属性ビットの２ビットが（１，０）のとき、‘一致’の状態となる。
【００１５】
またメモリセル２１＿１，……２１＿ｍは、トランジスタＴ１，Ｔ２のゲートに印加される値がデコーダ１７によってアクセスされるＳＲＡＭのＱノード，Ｑ＿  ノードによって設定されるものであり、一致検出動作は、属性メモリセル２０＿１，２０＿２の場合と同じである。
互いにシリアルに接続されたトランジスタＴＣ１＿１，ＴＣ１＿２，ＴＣ２＿１，…，ＴＣ２＿ｍ等からなるＮＡＮＤ型一致検出回路３０には、図の左端に制御トランジスタＴＣ０が構成され、図の右端には一致検出アンプ３１が構成されたものであり、制御クロックφで制御される。先ず制御クロックφが‘０’となり、一致検出アンプ３１の入力ノードがプリチャージトランジスタ３１ａでプリチャージされ、これによりインバータ３１ｂの出力は‘０’となる。このとき、制御トランジスタＴＣ０はオフ状態に保たれる。
【００１６】
各ビット線，各ビットバー線Ｚｂ１，Ｚｂ１＿  ；Ｚｂ２，Ｚｂ２＿  ：Ｄｂ１，Ｄｂ１＿  …；Ｄｂｍ，Ｄｂｍ＿  を介して属性検索レジスタ１２＿１と検索データレジスタ１２＿２から検索データがあらかじめ入力されており、前述の各属性ビットセル２０＿１，２０＿２および各メモリセル２１＿１，…，２１＿ｍのそれぞれについて一致不一致が決定され、一致するセルについては、ＮＡＮＤ型一致検出回路を構成する、対応する各トランジスタＴＣ１＿１，ＴＣ１＿２，ＴＣ２＿１，…，ＴＣ２＿ｍのゲート電圧が‘１’となり、そのトランジスタがオンする。
【００１７】
この状態で制御クロックφが‘１’になると、全てのセルが一致したメモリワードのみに対応するＮＡＮＤ型一致検出回路３１のインバータ３１ｂの入力ノードがディスチャージされ、このインバータ３１ｂから‘１’の一致信号が出力され、対応する一致フラグレジスタ１５に‘１’が格納されることになる。
このとき、メモリセル２１＿１，…，２１＿ｍに格納された格納データだけでなく属性データの一致がなければ一致信号は得られないことになる。したがってこの属性データを各データセットを構成する各データの属性に合わせて定義しておくことにより、各データセットの各属性毎の検索が可能となる。このように属性データをあらかじめハードウェア的に作り込んだ連想メモリにおいては、図５に示す属性検索レジスタ１２＿１には制御データの１つとして属性データをセットすればよく、したがってこの連想メモリを用いることにより連想メモリの１ワード分のビット長を減らすことなく外部とのアクセスを行うことのできるシステムを構成することができる。
【００１８】
【発明が解決しようとする課題】
上記のように、各メモリワードに属性とデータの双方を格納しておいてそれら属性とデータとの双方で検索を行なう場合において、使用されないメモリワードの処理が問題となる。例えばメモリワードが１２８個作り込まれた連想メモリに用いて、属性Ｉ〜属性Ｖの５つのデータをデータセットとしてその連想メモリに格納すると、１２８のメモリワードのうち５で割り切れない余りの３つのメモリワードは使用されない状態となる。
【００１９】
この余りの３つのメモリワードをそのままにしておくと、そのメモリワードにたまたま格納されていたデータと検索データとが一致してしまうという事態が懸念される。またこの余りの３つのメモリワードが検索の対象となる有効なデータが格納されていない空き状態にあると定義する（実際は各メモリワード毎にフラグレジスタを持ち、対応するメモリワードに有効なデータが格納されているかそのメモリワードが空き状態にあるかを識別するフラグが格納される）と、新たなデータをメモリワードに書き込む際に、その余りのメモリワードが指定され、しかも１つのデータセットを構成するデータ全部が書き込まれないという事態が生じ得ることになる。
【００２０】
本発明は、上記事情に鑑み、余りのメモリワードを有効に処理する連想メモリの使用方法、および、余りのメモリワードが有効に処理された連想メモリを提供することを目的とする。
【００２１】
【課題を解決するための手段】
上記目的を達成する本発明の連想メモリの使用方法は、配列された複数のメモリワードそれぞれに各ディジタルデータを書込み自在に記憶しておき、検索データを入力し、入力された検索データの全部もしくは所定の一部のビットパターンと一致するビットパターンを有するディジタルデータが記憶されたメモリワードを検索する連想メモリの使用方法において、
上記複数のメモリワードのうち、検索に使用される第１のメモリワードに、その第１のメモリワードがそれぞれ二分された一方の第１の領域にディジタルデータを格納すると共に、その第１のメモリワードの、上記第１の領域を除く第２の領域に、その第１の領域に格納されたディジタルデータの属性を表わす属性データを記憶させ、かつ
上記複数の各メモリワードのうち、検索に使用されない第２のメモリワードの上記第２の領域に、上記第１のメモリワードに記憶される属性データのいずれとも値の異なる属性データを記憶させ、
この連想メモリに所定の属性データと所定のディジタルデータとの組を検索データとして入力することにより、その連想メモリに、入力された所定のディジタルデータに対応すると共に入力された所定の属性データが表わす属性を有するディジタルデータが記憶されたメモリワードの検索を行わせることを特徴とする。
【００２２】
また、上記目的を達成する本発明の連想メモリは、配列された複数のメモリワードそれぞれに各ディジタルデータを記憶しておき、検索データを入力し、入力された検索データの全部もしくは所定の一部のビットパターンと一致するビットパターンを有するディジタルデータが記憶されたメモリワードを検索する連想メモリにおいて、
上記複数のメモリワードのうち検索に使用される第１のメモリワードが、各ディジタルデータが書込み自在に記憶された第１の領域と、その第１の領域に記憶されたディジタルデータの属性を表わす属性データが書込み自在にもしくは固定的に記憶された第２の領域とを有するとともに、
上記複数の各メモリワードのうち検索に使用されない第２のメモリワードが上記第１のメモリワードに記憶された属性データのいずれとも値の異なる属性データが書込み自在にもしくは固定的に記憶された上記第２の領域を有するものであることを特徴とする。
【００２３】
【作用】
本発明の連想メモリの使用方法は、余りのメモリワードに、検索に使用される属性データのいずれとも異なる値の異なる属性データを書き込んでおいて検索を行なうものであり、また本発明の連想メモリは、余りのメモリワードに、検索に使用される属性データのいずれとも値の異なる属性データが書き込まれたものであるため、その余りのメモリワードで一致が検出されることが防止される。
【００２４】
【実施例】
以下、本発明の実施例について説明する。
図１は本発明における、メモリワードのメモリマップの一例を示した図である。
この実施例の連想メモリには、１２８個のメモリワード１１＿１，１１＿２，…，１１＿１２８が備えられており、各メモリワード１１＿１，１１＿２，…，１１＿１２８には、本来のデータを格納する第１の領域１１＿１＿１，１１＿２＿１，…，１１＿１２８＿１と属性データを格納する第２の領域１１＿１＿２，１１＿２＿２，…，１１＿１２８＿２が備えられている。この連想メモリに、それぞれ属性Ｉ〜Ｖが付された５つのデータからなるデータセットが格納されるものとする。
【００２５】
その場合、５で割り切れない３つの余りのメモリワード１１＿１２６，…，１１＿１２８が生じるが、それらのメモリワード１１＿１２６，…，１１＿１２８の第２の領域１１＿１２６＿２，…，１１＿１２８＿２には、検索に使用される属性Ｉ〜Ｖのいずれとも異なる値、例えば属性ＶＩＩが格納される。この場合、属性とデータのうち属性が一致することはなく、従って属性とデータの全体としても一致することはなく、不用意な誤った検索が防止される。
【００２６】
【発明の効果】
以上説明したように、本発明によれば、メモリワードに余りが生じても不用意な誤った検索が防止される。
【図面の簡単な説明】
【図１】本発明における、メモリワードのメモリマップの一例を示した図である。
【図２】連想メモリの一例を表わした回路ブロック図である。
【図３】連想メモリに記憶された、属性の付されたデータの配列を示した図である。
【図４】メモリ構造図である。
【図５】連想メモリのブロック図である。
【図６】連想メモリを構成する多数のメモリワードのうち、１つのメモリワードの構成を示す回路図である。
【符号の説明】
１０  連想メモリ
１１＿１，１１＿２，…，１１＿１２８  メモリワード
１１＿１＿１，１１＿２＿１，…，１１＿１２８＿１  第１の領域
１１＿１＿２，１１＿２＿２，…，１１＿１２８＿２  第２の領域
【図１】
0003583799.tif 000002
【図２】
0003583799.tif 000003
【図３】
0003583799.tif 000004
【図４】
0003583799.tif 000005
【図５】
0003583799.tif 000006
【図６】
0003583799.tif 000007