JPS635839B2 - - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 本発明は内容によりサーチを行う連想メモリに
関し、特に連想メモリのメモリ幅拡張装置に関す
る。

背景技術とその問題点 連想メモリ（associative memory）は、物理
ロケーシヨン（physical location）によつてで
はなく、内容によつてサーチされる。連想メモリ
を構成する個々のセルは、他のメモリと同様に
各々、情報の１ビツトを含む。所定数のビツトに
より、１ワードが構成される。連想サーチでは、
メモリ内の複数のワードは、一連のデータビツト
から成る既知のサーチ・パターンと、同時に（並
列に）比較される。一致が検出されると、その一
致したデータを含むセルの物理ロケーシヨンが決
定される。連想メモリの主な利点は、全メモリの
サーチが実質的に１ワードのサーチを行うに要す
る時間で迅速に行われることである。

或る連想メモリは、その設計により特定のメモ
リ幅（width）に限定され、メモリをカスケード
接続（cascading）して拡張することができな
い。よつてこのようなメモリは、所定のワードに
対するビツト数が或る最大値例えば16ビツトに制
限され、このメモリに対する16ビツトより大きい
サーチ・パターンは確実にはサーチされない。こ
れは大きな欠点であり、従つてこのようなメモリ
は、その用途も限定されることになる。

他の連想メモリには、固定長のサーチ・パター
ンでのみサーチ可能に設計されたものもある。こ
れは、可変長のサーチ・パターンでサーチを行い
たいときに問題となる。

発明の目的 本発明の目的は、連想メモリのメモリ幅より大
きいサーチ・パターンによつてもサーチが行われ
るよう、連想メモリのメモリ幅を実質的に拡張す
る連想メモリのメモリ幅拡張装置を提供すること
である。

発明の概要 本発明は連想メモリに用いられるものであり、
メモリデバイス内の所定のワード・ロケーシヨン
に関連し、一致信号を出力する回路手段を含む。
一致信号は、そのワード・ロケーシヨンのデータ
がメモリの現在の連想サーチ中に用いられる選択
されたサーチ・パターンの一部と一致し、且つメ
モリデバイス内のその前のワード・ロケーシヨン
のデータが、メモリの連想サーチ中に直前に用い
られた選択されたサーチ・パターンの一部と一致
していたとき発生される。

実施例 数個の論理素子を含む本発明は、連想メモリ・
デバイスの現存のチツプ設計に都合よく組込むこ
とができる。本発明を適用して有益な連想メモリ
デバイスの一例として、本出願人に譲渡されたト
ーマス・エイ・アルミー（Thomas A.Almy）等
による米国特許出願第502047号、発明の名称「大
記憶容量連想メモリ（High Storage Capacity
Associative Memory）」が挙げられる。先ずこ
の米国特許出願を第２図を参照しながら説明す
る。

この米国特許出願は第２図に示すように、連想
メモリアレイ３１、マスク／データ駆駆ブロツク
３３、アドレスデコーダ３５、一致検出ブロツク
３７及びアドレスエンコーダ３９を含む連想メモ
リデバイスを開示している。これらの構成要素は
１つのチツプ内に組込まれ得る。連想メモリデバ
イスは従来のランダムアクセスメモリ（RAM）
と同様の働きをするRAMモードまたは連想サー
チを行う連想モードで動作する。RAMモードで
は、アドレスデコーダ３５により連想メモリ内の
任意のロケーシヨンが指定され、そのロケーシヨ
ンの内容の読出し、または書込みがマスク／デー
タ駆動ブロツク３３を介して行われる。このと
き、アドレスデコーダ３５はANDゲート３５ａ
によりイネーブルされ、一致検出ブロツク３７及
びアドレスエンコーダ３９は夫々インバータ３７
ａ及びANDゲート３９ａによりデイスエーブル
される。連想モードでは逆にアドレスデコーダ３
５がデイスエーブルされ、一致検出ブロツク３７
及びアドレスエンコーダ３９がイネーブルされ
る。連想モードではマスク／データ駆動ブロツク
３３から、サーチの対象となるビツト位置を指定
するマスク信号及びサーチ・パターンのデータが
入力される。サーチ・パターンは、同時に連想メ
モリ３１の各ロケーシヨンの内容と比較される。
連想メモリ３１は各ワード・ロケーシヨンに対し
て１本の出力線を有する。この出力線の信号状態
（「高」または「低」）はそのロケーシヨンの内容
に対してサーチパターンの一致が生じたかどうか
を示す。一致検出ブロツク３７は、夫々これらの
出力線を受ける複数の一致検出回路を含み、一致
の生じたロケーシヨンのうち最下位のロケーシヨ
ンに対応する信号を出力する。この信号はアドレ
スエンコーダ３９に入力され、一致の生じた最下
位のロケーシヨンが決定される。

本発明に係る回路は、上述したメモリアレイと
一致検出ブロツクとの間に用い得る。他の連想メ
モリにおいても同様である。第１図は本発明の一
実施例のブロツク図を示す。連想メモリアレイの
各ワード・ロケーシヨンは破線１３及び１５間に
示した回路１１を有する。この回路は図示の如く
カスケード接続される。連想メモリアレイ内の前
のワードに対する回路１４は、破線１３の上方に
示され、その出力信号を回路１１の入力線２５に
供給する。回路１１の出力線１９は連想メモリア
レイ内の後続ワード・ロケーシヨンに対応する回
路１１と同様の回路の入力線に接続される。

回路１１は、ANDゲート２１及びラツチ２３
から成る。ANDゲート２１は２本の入力線２５
及び２７を有する。入力線２５は上述の如く、前
段の回路の出力線に接続される。入力線２７へ
は、連想メモリからのワード選択線（上述のメモ
リアレイの出力線）が接続される。ワード選択線
は、メモリ内の所定のワード・ロケーシヨンから
導かれる。メモリからのこのワード選択線の信号
状態は、そのワードがサーチ・パターンに一致し
たかどうかを示す。連想サーチは、メモリ内で実
行され、その結果を表す信号はANDゲート２１
を通過する。

ANDゲート２１の出力はラツチ２３の一方の
端子すなわち入力端子Ｄ２２へ入力される。他方
の端子すなわち出力端子Ｑ２４の信号はこの回路
の出力であり、上述の米国特許出願に開示された
一致検出回路の如き後続の回路へ供給される。他
方の端子Ｑ２４から更に出力線１９が伸び、後続
回路のANDゲートの一入力線へ接続される。ラ
ツチ２３はまた、ラツチ用のクロツクが供給され
るクロツク入力端子２６を有する。なお、連想メ
モリアレイ３１の第２ワード・ロケーシヨン以降
の各ワード・ロケーシヨン用回路は、回路１１と
同じ構成であるが、第１（最初の）ワード・ロケ
ーシヨン用回路１４のみ、アンド・ゲート２１を
具えておらず、他の回路からの一致信号を受けな
い点に留意されたい。

次に動作を説明する。まず複数の回路の各々の
ラツチは初期化信号によつてセツトされる。こう
してラツチ２３は最初セツト状態におかれ、端子
２４には「高」信号が出力される。これは全回路
に対して一致を示す。よつてANDゲート２１へ
の信号線２５上の一入力も「高」となる。そこ
で、サーチ・パターンの第１部分に対する連想サ
ーチがメモリアレイ内で行われる。例えば、連想
メモリ・デバイスが16ビツト幅であるとすると、
サーチ・パターンの最初の16ビツトが連想サーチ
に用いられる。

サーチ・パターンの第１部分に内容の一致した
連想メモリ内のワードに対して、信号線２７が
「高」となり、一致の生じたメモリ内の各ワー
ド・ロケーシヨンで第１サーチ・パターン部分に
対してANDゲート２１の両入力が「高」となる。
このときANDゲート２１の出力は「高」となる。
しかし、ワード選択線２７の状態が「低」なら
ば、即ちメモリから不一致信号が送られると、
ANDゲート２１の出力は「低」になる。ラツチ
２３は入力端子２６はクロツクを受け、出力端子
２４の信号状態はANDゲート２１の出力に応じ
て決まる。出力端子２４の出力はメモリから一致
信号が送られているとき「高」（セツト）となり、
不一致信号が送られているときは「低」となる。

次にサーチ・パターンの次の部分がメモリの連
想サーチに用いられる。よつて、16ビツトの連想
メモリ、32ビツトのサーチ・パターンの場合、ビ
ツト17乃至32は次のサーチのサーチ・パターンを
構成する。連想メモリはサーチを実行し、一致が
検出されると、連続した回路に対して信号線２７
上に新しい信号パターンを発生する。信号線２５
上の入力は、サーチ・パターンの第１部分のサー
チにおいてメモリ内の前のワード・ロケーシヨン
で一致が起きたときのみ「高」になり、信号線２
７上の信号は、サーチ・パターンの今回の部分に
ついてこの回路に対応してメモリ内で一致が起き
たときのみ「高」になる。ラツチ２３が次に再び
クロツクを受けると、出力端子２４の出力は、サ
ーチ・パターンの２つの部分がメモリ内の２つの
連続したワードに一致したときのみ「高」（セツ
ト）となる。サーチ・パターン部分の順次サーチ
（sequential search）は、パターンの全部分がサ
ーチされるまで続く。ラツチ２３は各サーチ間に
クロツクを受ける。このように、Ｎビツト幅のメ
モリにおけるＭ×Ｎビツトのサーチ・パターン
は、Ｍ個のクロツク周期内で達成される。連想メ
モリの性能は、このような順次サーチを行うこと
によつてそれだけ低下するが、性能の若干の低下
は通常、サーチの融通性が生まれることによつて
充分に補われる。

以上の如く、連想メモリ自身の幅より大きいサ
ーチ・パターンを可変長サーチ・パターンと同様
に使用できる。説明のため好適実施例についての
み記載したが、本発明の要旨を逸脱することなく
種々の変化・変更・置換ができることは明らかで
あろう。

発明の効果 上述の如く本発明によれば、従来行うことがで
きなかつた連想メモリのメモリ幅より大きいサー
チ・パターンによるサーチが行えるようになるの
で、任意の大きさのサーチ・パターンを確実にサ
ーチすることができ、またその用途が拡大され汎
用性をもたせることができる。しかも、本発明に
よる装置は簡単な論理素子のみから成るので、従
来の連想メモリのチツプに容易に組込むことがで
きる。

また、連想メモリの第２ワード・ロケーシヨン
以降の各々に設けられた回路手段は、単に選択信
号及び直前の回路手段の出力信号が共に一致状態
ならば、一致状態の出力信号を発生する。よつ
て、連想メモリのメモリ幅より大きいサーチ・パ
ターンによつてサーチを行なう際、サーチ・パタ
ーンのサーチ対象部分に対応しない連想メモリの
ワード・ロケーシヨンをマスクする必要がないの
で、サーチの際の制御が容易となる。

また、サーチ・パターンの長さ（幅）が変化し
ても、何ら回路構成を変更する必要がなく、単に
初期化信号を供給するタイミングを変更するのみ
でよい。（初期化信号は、サーチ・パターンの最
初の部分をサーチする直前に供給する。）よつて
適用範囲が広がる。

更に連想メモリの各ワード・ロケーシヨンがサ
ーチ・パターンのどの部分に対応するかを予め割
当てる必要がない。よつて、データを書込む際、
ワード・ロケーシヨンが連続していればよいの
で、制御が容易となる。

【図面の簡単な説明】

第１図は本発明の一実施例を示す回路図、第２
図は本発明の関連技術を示す説明図である。 図中、１１は回路手段、２１はANDゲート、
２３はラツチである。

Claims (1)

1. 【特許請求の範囲】 １ 各ワード・ロケーシヨンに記憶されたデータ
   がサーチ・パターンと一致したか否かを示す選択
   信号を上記ワード・ロケーシヨン毎に出力する連
   想メモリにおいて、 該連想メモリの第１ワード・ロケーシヨン用回
   路手段は、上記選択信号をラツチするラツチ回路
   を有し、 上記連想メモリの第２ワード・ロケーシヨン以
   降のワード・ロケーシヨン用回路手段の各々は、
   上記選択信号及び直前の上記ワード・ロケーシヨ
   ン用回路手段の出力信号が共に一致状態のとき一
   致状態の信号を出力するゲート手段と、該ゲート
   手段の出力信号をラツチするラツチ回路とを有
   し、 連想モードの開始において、上記第１ワード・
   ロケーシヨン以降の総ての上記回路手段の上記ラ
   ツチ回路が一致状態の信号を出力するように初期
   化されることを特徴とする連想メモリのメモリ幅
   拡張装置。