JPH05298893A - 連想記憶装置 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】 判定回数を減らし、高速に照合データを出力
する。 【構成】 複数のデータが記憶媒体１０１に蓄積されて
おり、このデータの中から探索キーワードに照合するデ
ータを照合部１０４にてシリアルに探索する。探索結果
は対応するビットに書込まれる。各ビットからの出力は
１層目の複数のＮ入力１出力ＯＲゲート１０６に入力さ
れる。ゲート１０６の出力は夫々１層目の高速照合用レ
ジスタの各ビットに入力される。１層目の各ビットから
の出力は２層目のＯＲゲートに入力される。２層目のＯ
Ｒゲートの出力は２層目のレジスタの各ビットに入力さ
れる。以下、順次、ＯＲゲートと高速照合用レジスタに
入力される。アドレス参照回路１１０は制御回路１１１
の制御のもと最終層のレジスタのビット判定から初め
て、順次、その前の層のビット判定に遡る。この際、第
ｋ層でビット値が１との判定に対応する第ｋ−１層のビ
ットのみがビット判定される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、記憶媒体に蓄積されて
いるデータを探索キーワードとマスクとを用いて探索す
る連想記憶装置に関し、特にビットシリアル、バイトシ
リアル、またはワードシリアルに探索することのできる
連想記憶装置に関する。

【０００２】

【従来の技術】連想記憶装置とは、データ記憶領域に蓄
積されているデータの中から探索キーワードに照合する
データを高速に探索することを目的とするものであり、
記憶内容によるアドレシング、データ記憶領域への探索
キーワードの同時分配、探索キーワードとマスクとを用
いた比較の並列処理、照合結果の検知と探索を行うもの
である。このような連想記憶装置は例えば雑誌「コンピ
ュータ（COMPUTER）」の1989年７月号の51頁から64頁に
掲載されたローレンス・チスビン（Lawrence Chisvin）
らの論文「内容アドレス連想記憶（Content-Addressabl
e and Associative Memory）」に記載されている。

【０００３】従来、連想記憶を実装するアーキテクチャ
としてはビットシリアル方式、バイトシリアル方式、ワ
ードシリアル方式、及び分散論理メモリがある。ビット
シリアル方式では、データの記憶領域への登録と探索と
をビット単位で行う。バイトシリアル方式では、データ
の記憶領域への登録と探索とをバイト単位で行う。ワー
ドシリアル方式では、データの記憶領域への登録と探索
とをワード単位で行う。ビットシリアル方式、バイトシ
リアル方式、ワードシリアル方式は分散論理メモリに比
べてロジック部分の規模を小さくでき、高密度の設計が
可能となる。従って、大規模な連想メモリにはビットシ
リアル方式、バイトシリアル方式、ワードシリアル方式
が向いているとされている。

【０００４】図７に従来の連想記憶装置の構成例を示
す。この連想記憶装置は探索対象となるデータとしてＭ
個のワードを格納するための記憶領域７０１を備えてい
る。探索キーワードはキーワードレジスタ７０２に格納
されている。また、ビット単位のマスクパターンがマス
クレジスタ７０３に格納されている。

【０００５】探索キーワードとデータの照合は記憶領域
７０１とマスクレジスタ７０３とに接続する照合部７０
４にて行われる。照合部７０４には、照合の結果として
照合フラグが書き込まれるＭビットの照合フラグ用レジ
スタ７０５が接続されている。照合フラグ用レジスタ７
０５には、照合フラグを判定する照合フラグ用判定回路
７０６が接続されている。連想記憶装置は更に記憶領域
２０１に接続する検索回路７０７と、検索回路７０７に
接続する出力レジスタ７０８とを備えている。

【０００６】ビットシリアル方式にて連想記憶探索を行
う場合のこの装置の動作を以下に説明する。まず、探索
キーワードとマスクパターンがキーワードレジスタ７０
２とマスクレジスタ７０３とから照合部７０４へ入力さ
れる。一方、探索対象となるデータが記憶領域７０１か
ら照合部７０４に入力される。ここで探索対象となるデ
ータはＭ個のワードであり、これらＭ個のワードがビッ
ト単位で並列に照合部７０４に入力される。

【０００７】照合部７０４は、各ワードに対応するＭ個
の照合回路からなり、各照合回路には探索キーワードと
探索対象となるデータとがビット単位で入力されてい
る。この照合回路は照合されるビットの全てが一致した
場合に１をを出力し、照合されるビットのうち１つでも
不一致がある場合は０を出力するものである。

【０００８】各照合回路の出力は照合フラグ用レジスタ
の各ビットに対応し、その結果、探索キーワードと一致
したワードに対応する照合フラグ用レジスタ７０５のビ
ットにのみフラグが立つ。照合フラグ用レジスタの各ビ
ットには、各ワードに一対一に対応するレジスタアドレ
スが付与されている。

【０００９】照合フラグ用判定回路７０６は照合フラグ
用レジスタ７０５の各ビットの値をビットシフトしなが
らビット単位で順次読みだしてフラグの値が１のレジス
タアドレスを出力する。検索回路２０７は照合したレジ
スタアドレスを入力し、記憶領域７０１の該アドレスで
の内容を読み出して、その内容を出力レジスタ７０８に
出力する。本例ではビットシリアル方式での照合を示し
たが、バイト単位、もしくはワード単位での照合も同様
に実現できる。

【００１０】

【発明が解決しようとする課題】上記したようにビット
シリアル方式による探索では、照合フラグを検出すると
きに検索対象の数だけビットシフトしなければならず、
検索対象の数が多い大規模な連想記憶では、照合速度が
検索対象の数のオーダで遅くなってしまう。

【００１１】従って、本発明の目的は、大規模の連想記
憶において照合結果の検出速度を短縮し、高速に探索可
能な連想記憶装置を提供することである。

【００１２】

【課題を解決するための手段】上記した本発明の目的
は、複数のデータを蓄積する記憶媒体と、該記憶媒体に
蓄積されたデータの中から探索キーワードに照合するデ
ータをシリアルに探索するための照合手段と、該照合手
段に接続し照合するデータに対応するビットに照合フラ
グが書込まれる照合フラグレジスタと、該照合フラグレ
ジスタの各ビットからの出力が並列に入力される照合フ
ラグを判定するための照合判定手段とを具備し、前記照
合判定手段が複数並列にかつ階層状に配列された多入力
論理和手段及び該論理和手段の出力を判定する判定手段
を有していることを特徴とする連想記憶装置によって達
成される。

【００１３】また、上記した本発明の目的は、複数のデ
ータを蓄積する記憶媒体と、該記憶媒体に蓄積されたデ
ータの中から探索キーワードに照合するデータをシリア
ルに探索するための照合手段と、該照合手段に接続し照
合するデータに対応するビットに照合フラグが書込まれ
る第１の照合フラグレジスタと、該第１の照合フラグレ
ジスタに接続し、照合フラグのビット位置を変更するた
めの交換手段と、該交換手段に接続し、変更されたビッ
ト位置にて照合フラグが書込まれる第２の照合フラグレ
ジスタと、該第２の照合フラグレジスタの各ビットから
の出力が並列に入力され、複数並列にかつ階層状に配列
された多入力論理和手段及び該論理和手段の出力を判定
する判定手段を有している照合フラグを判定するための
照合判定手段と、関連のあるデータを第１層目の複数の
多入力論理和手段のうち同一の多入力論理和手段に入力
するように交換手段を切り替える切り替え手段とを具備
することを特徴とする連想記憶装置によっても達成され
る。

【００１４】

【作用】上記構成にてなる連想探索装置によれば、最終
層の論理和手段の出力値の判定から初めて、順次、その
論理和手段に入力する前の層の論理和手段に遡りながら
論理和手段の出力値の判定が行われる。最終的に照合フ
ラグレジスタの必要かつ十分な一部分のビットのみの照
合フラグ値の判定が行われる。これにより、判定回数を
著しく減らすことができる。

【００１５】

【実施例】以下、本発明の連想記憶装置の一実施例を図
面に基づき詳述する。

【００１６】図１に本発明にてなる連想記憶装置の一実
施例の構成を示す。連想記憶装置は探索対象となるデー
タとしてＭ個のワードを格納するための記憶領域１０１
を備えている。ここでＭは１００もしくは１０００程度
の数であるが、これ以上であってもかまわない。各ワー
ドは、１６ビット、３２ビット又は２５６ビット等のビ
ット長を有するものである。

【００１７】探索キーワードはキーワードレジスタ１０
２に格納されている。また、ビット単位のマスクパター
ンがマスクレジスタ１０３に格納されている。

【００１８】探索キーワードとデータの照合は記憶領域
１０１とマスクレジスタ１０３とに接続する照合部１０
４にて行われる。照合部１０４は第２図に示すように各
ワードに対応するＭ個の照合回路２０１からなり、各照
合回路２０１には探索キーワードと探索対象となるデー
タとがビット単位で入力されている。この照合回路２０
１は照合されるビットの全てが一致した場合に１を出力
し、照合されるビットのうち１つでも不一致がある場合
は０を出力するものである。照合回路２０１は二つの入
力のビット単位の照合を行うための２入力のＸＯＲ回路
２０２と、ＸＯＲ回路２０２からの出力が一方の入力端
子に入力される２入力ＯＲ回路２０３と、２入力ＯＲ回
路２０３からの出力がＤ入力端子に入力され、クロック
ＣＬＫに同期してＤ入力端子に与えられた値をＱ出力端
子より出力するＤラッチ２０４と、Ｄラッチ２０４のＱ
出力端子からの出力を反転するためのインバータ２０５
とからなり、２入力ＯＲ回路２０３の他方の入力にはＤ
ラッチ２０４からの出力が入力されている。

【００１９】ここで探索対象となるデータはＭ個のワー
ドであり、これらＭ個のワードがビット単位で並列に照
合部１０４に入力される。各ワードからのビット単位の
入力は各照合回路２０１のＸＯＲ回路２０２の一方の入
力となり、各照合回路２０１のＸＯＲ回路２０２の他方
の入力には探索キーワードがビット単位で入力される。
探索対象となるワードからのビット単位の入力と探索キ
ーワードからのビット単位の入力は、まず、ＸＯＲ回路
２０２にてビット単位で照合される。ＸＯＲ回路２０２
の出力は両者が一致した場合に論理値０となり、不一致
の場合は論理値１となる。ＸＯＲ回路２０２の出力はＤ
ラッチ２０４に保持され、Ｑ出力の値は両者が一致した
場合に０となり、不一致の場合は１となる。ところで、
ＯＲ回路２０３にはＤラッチのＱ出力が一方の入力とし
て入力されており、一度でもＱ出力に１が表れた場合、
以降はすべてＸＯＲ回路２０２の出力に関係なく、Ｄラ
ッチのＱ出力は１となる。このＤラッチのＱ出力をイン
バータ２０５によって反転した信号が、照合回路２０１
の出力になっているので、従って、照合回路２０１は照
合されるビットの全てが一致した場合に１をを出力し、
照合されるビットのうち１つでも不一致がある場合は０
を出力する。

【００２０】照合部１０４には照合の結果として照合フ
ラグが書き込まれるＭビットの照合フラグ用レジスタ１
０５が接続されている。各照合回路の出力は照合フラグ
用レジスタの各ビットに対応し、また照合フラグ用レジ
スタ１０５の各ビットには、各ワードに一対一に対応す
るレジスタアドレスが付与されている。

【００２１】照合フラグ用レジスタ１０５の各ビットか
らの出力は、レジスタアドレス０からＮ−１のビットか
らの出力が第１層のＮ入力１出力ＯＲゲート１０６の第
１番目のＮ入力１出力ＯＲゲートに、レジスタアドレス
Ｎから２Ｎ−１のビットからの出力が同じく第２番目の
Ｎ入力１出力ＯＲゲートに、以下同様に、レジスタアド
レス（ｋ−１）＊Ｎからｋ＊Ｎ−１までのビットからの
出力が第１層のＮ入力１出力ＯＲゲート１０６の第ｋ番
目のゲートに入力されるように第１層の並列に設けられ
た複数のＮ入力１出力ＯＲゲート１０６に入力されてい
る。

【００２２】Ｎ入力１出力ＯＲゲートは図３に示すよう
に１つの２入力ＯＲゲート３０１の出力が次段の２入力
ＯＲゲート３０２の一方の入力になるように複数の２入
力ＯＲゲートを多段に接続したもので、Ｎ個の入力に１
を含む場合は、１を出力するものである。

【００２３】第１層のＮ入力１出力ＯＲゲートの出力線
数、即ち第１層のＮ入力１出力ＯＲゲートの数は、Ｍ／
Ｎの小数点以下を切り上げた数となる。この場合、Ｎ入
力１出力ＯＲゲートに未入力の入力端子が生じる場合
は、予めそのような入力端子には０が与えられている。

【００２４】各ゲートの出力は、第１層のＮ入力１出力
ＯＲゲート１０６と同数のビットを有する第１層の高速
照合用レジスタ１０７に入力されている。

【００２５】第１層の高速照合用レジスタ１０７の各ビ
ットからの出力は、第１層のＮ入力１出力ＯＲゲート１
０６に入力したときと同様にして、順に第２層のＮ入力
１出力ＯＲゲートの各ゲートに入力され、各ゲートの出
力は、第２層のＮ入力１出力ＯＲゲートと同数のビット
を有する第２層の高速照合用レジスタ１０７に入力され
ている。以下、複数のＮ入力１出力ＯＲゲートと高速照
合用レジスタの組合わせで３層、４層と階層状に順次接
続される。

【００２６】各層の高速照合用レジスタの各ビットには
照合フラグ用レジスタ１０５の各ビットと同様にレジス
タアドレスが付与されており、第（ｋ−１）層のレジス
タアドレス値ｉを有するビットからの出力が、第ｋ層の
レジスタアドレス値ｊを有するビットに接続するＮ入力
１出力ゲートに入力されている場合、ｊはｉ／Ｎの小数
点以下を切り上げた数から１減じた数（但し、０≦ｉ＜
Ｍ／Ｎ^k-1 ）となる。Ｎ入力１出力ＯＲゲートの未入力
の入力端子が生じる場合は、そのような入力端子には予
め０が与えられている。

【００２７】最終的には最終層である第Ｋ層の単一のＮ
入力１出力ＯＲゲート１０８と１ビットの高速照合用レ
ジスタ１０８が接続される。このとき層数はＭがＮの累
乗の場合はｌｏｇ_N Ｍとなる。但し、ＭがＮの累乗でな
い場合はｌｏｇ_N Ｍの少数点以下を切り上げた数とな
る。

【００２８】図示の連想記憶装置は更に照合フラグ用レ
ジスタ１０５及び各層の高速照合用レジスタに接続する
レジスタアドレス参照回路１１０を備えている。

【００２９】レジスタアドレス参照回路１１０は、後述
する制御回路１１２の制御に基づき照合フラグ用レジス
タ１０５及び各層の高速照合用レジスタの値を読み出
し、その値を判定するもので、特に照合フラグ用レジス
タ１０５から読み出した値に１がある場合は、制御回路
１１２の制御に基づき、この値が読み出されたビットの
レジスタアドレスを後述する検索回路に出力するように
構成されている。

【００３０】ところで、一般に第（ｋ−１）層の高速照
合用レジスタのレジスタアドレス値ｉを有するビットか
らの出力が、第ｋ層の高速照合用レジスタのレジスタア
ドレス値ｊを有するビットに入力するＮ入力１出力ＯＲ
ゲートに入力する場合、Ｎ＊ｊ≦ｉ＜Ｎ＊（ｊ＋１）
（但し、０≦ｉ＜Ｍ／Ｎ^k-1 ）となり、Ｎ入力１出力Ｏ
Ｒゲートを用いていることから当然ではあるが、一つの
ｊに対して、Ｎ個のｉが存在することになる。

【００３１】上記したレジスタアドレス参照回路１１０
は、上記の関係に基づき、第ｋ層のレジスタアドレスｉ
_k から、このレジスタアドレスｉ_k を有する第ｋ層の高
速照合用レジスタのビットに入力する第ｋ層のＮ入力１
出力ＯＲ回路の入力となっている第（ｋ−１）層の高速
照合用レジスタのビットのレジスタアドレスＡ（ｉ_k）
を算出するためのアドレスジェネレータを有している。

【００３２】レジスタアドレス参照回路１１０に接続す
る制御回路１１２は、レジスタアドレス参照回路１１０
がどの層のどのビットを読み出すかを制御するためのも
ので、第Ｋ層の高速照合用レジスタの読み出しからビッ
トの読み出しを開始するようにレジスタアドレス参照回
路１１０を制御するとともに、第ｋ層（ｋは１からＫ）
の高速照合用レジスタで値が１となっているビットがあ
る場合は、このビットに付与されているレジスタアドレ
スに基づき第（ｋ−１）層のレジスタアドレスＡ
（ｉ_k ）を算出すべくアドレスジェネレータに指示し、
レジスタアドレス参照回路１１０の第ｋ層での高速照合
用レジスタの読み出しを一時中断し、第（ｋ−１）層の
高速照合用レジスタのアドレスジェネレータで算出され
たレジスタアドレスを有するビットを読み出すようにレ
ジスタアドレス参照回路を制御する。これにより、読み
出して判定した値に１があった場合、順次読み出し及び
判定がその前の層に遡ることになり、最終的に、照合フ
ラグ用レジスタ１０５からの照合フラグの読み出し及び
判定が行われる。（ｋ−１）層以下の高速照合用レジス
タ及び第０層としての照合フラグ用レジスタ１０５から
の値の読み出しは総て、この制御回路１１２の制御のも
とで行われ、従って、各層の照合用レジスタは、アドレ
スジェネレータで算出されたレジスタアドレスを有する
ビットのみが読み出されることになる。

【００３３】また、制御回路１１１は、算出されたＮ個
のレジスタアドレスＡ（ｉ_k ）を有するビットが、レジ
スタアドレス参照回路１１０によって第（ｋ−１）層で
全て読み出されたら、レジスタアドレス参照回路１１０
の第ｋ層での読み出しを再開するようにレジスタアドレ
ス参照回路１１０を制御する。

【００３４】本実施例では、制御回路１１１は、第ｋ層
での読み出しを中断して第（ｋ−１）層の算出されたレ
ジスタアドレスを有するビットの読み出しに移行するた
めに算出されたレジスタアドレスＡ（ｉ_k ）のうち最も
小さいものを格納するためのレジスタと、各層での読み
出しの中断を再開できるように、各層での読み出しを中
断したときのレジスタアドレスを格納するための各層に
対応したスタックと、第ｋ層の一つのレジスタアドレス
に対応する第（ｋ−１）層のＮ個のレジスタアドレスの
うち、いくつのレジスタアドレスが値の判定を終わって
いるかを表すための各層に対応したカウンタを有する。

【００３５】検索回路１１２はレジスタアドレス参照回
路１１０からの照合したアドレスを入力し、記憶領域１
０１の該アドレスと同一のアドレスでの内容を読み出し
て、その内容を出力レジスタ１１３に出力する。

【００３６】以下、ビットシリアル方式にて連想記憶探
索を行う場合のこの装置の動作を説明する。

【００３７】図４は本発明の装置が実行する連想記憶探
索を一連のフローチャートとして表したものである。

【００３８】まず、探索キーワードとマスクパターンが
キーワードレジスタ１０２とマスクレジスタ１０３とか
ら照合部１０４へ入力される（Ｓ１）。一方、探索対象
となるデータが記憶領域１０１から照合部１０４に入力
され，各ワードと探索キーワードとの照合が行われ、そ
の結果が照合用フラグレジスタにセットされる（Ｓ
２）。

【００３９】次いで、照合フラグ用レジスタ１０５から
層状に接続されたＮ入力１出力ＯＲゲート及び高速照合
用レジスタによりＮ入力１出力ＯＲ演算が行われ、照合
データがある場合には第Ｋ層のレジスタ値が１となり、
ない場合は０となる（Ｓ３）。

【００４０】制御回路１１１は、初期設定として、レジ
スタアドレス参照回路１１０が、まず第Ｋ層のレジスタ
の値を読み出すように、現在の読み出しの対象となる層
番号ｋをＫとし、それと同時にレジスタアドレスｉ_k を
０とする（Ｓ４）。

【００４１】レジスタアドレス参照回路１１０は第ｋ層
の高速照合用レジスタのレジスタアドレスｉ_k で指定さ
れるビットの値を読み出し、その値が１か否かを判定す
る（Ｓ５）。

【００４２】制御回路１１１は、ステップＳ５でフラグ
値が１と判断されると、ついで層番号ｋが０でないかを
判断し（Ｓ６）、０でないならば、アドレスジェネレー
タにレジスタアドレスｉ_k でのＡ（ｉ_k ）の計算を指示
し、算出されたＮ個のアドレスのうち最も小さいものを
スタートアドレスｉ_s としてレジスタに一時格納する
（Ｓ７）。次ぎに、この層での探索を一時中断するた
め、レジスタアドレスｉ_kをｉ_kMとしてこの層に対応す
るスタックに格納し（Ｓ８）、一つ前の層の高速照合用
レジスタのステップ７で計算されたアドレスを有するビ
ットを読み出すため、（ｋ−１）を新たな層番号ｋとし
（Ｓ９）、またステップ７にてレジスタに一時格納して
あったスタートアドレスｉ_s を新たなレジスタアドレス
ｉ_k とする（Ｓ１０）。そしてこの層に対応するカウン
タＮ_k を１として、ステップＳ５に戻る。 以上のステ
ップＳ５からＳ１１までの工程で、ビットの値が１と判
定される限りは、ビット判定が１つ前の層の高速照合用
レジスタに順次遡ることになる。

【００４３】ステップＳ５にてフラグ値が０と判定され
ると、層番号ｋが最終層を表すＫでないか否かが判断さ
れ（Ｓ１２）、もしＫならば、探索対象となったデータ
の中には照合データが無かったものと判断し、探索を終
了する。

【００４４】ステップＳ１２にて層番号ｋが最終層を表
すＫでないと判断されると、ｉ_k ＋１を新たなレジスタ
アドレスｉ_k とし（Ｓ１３）、次いで、この層に対応す
るカウンタＮ_k を１だけインクリメントする（Ｓ１
４）。次ぎにカウンタＮ_k のカウント値がＮを越えたか
否かが判定され（Ｓ１５）、Ｎを越えていない場合は、
この層のレジスタでレジスタアドレスｉ_k で指定される
ビットの値を判定するため、ステップＳ５に戻る。ステ
ップＳ１５にてカウンタＮ_k のカウント値がＮを越えた
と判定されると、１つ後の層の高速照合用レジスタから
の読み出しを再開すべく、層番号ｋを１だけインクリメ
ントし（Ｓ１６）、層番号ｋが最終層を表すＫより小さ
いか否かを判定し（Ｓ１７）、小さいならば、この層に
対応するスタックに格納されているｉ_kMを新たなｉ_k と
し（Ｓ１８）、ステップＳ１３に戻る。ステップＳ１７
にて、層番号ｋが最終層を表すＫより小さくないと判断
されると、総ての層の高速照合用レジスタの参照すべき
ビットの値が判定されたと判断し、探索を終了する。

【００４５】以上のステップＳ１３からＳ１８までの工
程で、フラグ値が１のビットを読み出すまでは、順次フ
ラグ値が照合用レジスタから読み出されとともに、１つ
の層でＮ個のフラグ値が総て読み出され、判定された後
は、一つ後の層の照合用レジスタの読み出しを再開する
ことができる。

【００４６】ステップ６にて、ｋが０と判定されると、
照合用フラグレジスタからフラグ値を読み出していると
判断し、そのときのレジスタアドレスｉ₀ を検索回路１
１２に出力するようにアドレス参照回路１１０に指示
し、アドレス参照回路１１０は照合アドレスとしてその
ときのレジスタアドレスｉ₀ を出力する。

【００４７】検索回路１１２は、受けとったレジスタア
ドレスｉ₀ のもとに格納されているワードを照合データ
として出力レジスタに出力する（Ｓ２０）。

【００４８】制御回路１１１は、次ぎのレジスタアドレ
スで指定されるビットのフラグ値を読み出すべく制御を
ステップ１３に戻す。

【００４９】以上の構成及び動作によれば、照合データ
数が全データ数に比べて十分に小さいときは、たとえ
ば、照合データが一件の場合は、判定回数はＮ＊ｌｏｇ
_N Ｍ＋１となり、同じ条件の場合、従来法ではＭ回のビ
ットシフトと判定が必要になるのに対して、判定回数を
大幅に減らすことができる。

【００５０】次に、図５に基づき、より具体的な動作の
説明を行う。

【００５１】図５には、探索対象データ数が２７で、第
１層に９個の３入力１出力ＯＲ回路と９ビットの照合用
レジスタ、第２層に３個の３入力１出力ＯＲ回路と３ビ
ットの照合用レジスタ、第３層に１個の３入力１出力Ｏ
Ｒ回路と１ビットの照合用レジスタを用いた、Ｎ＝３、
“階層数３（Ｋ＝３）の連想記憶装置を示す。

【００５２】この連想記憶装置の２７ビットの照合用フ
ラグ用レジスタのうちレジスタアドレス０で指定される
ビット（図中、最も上のビット）のフラグ値が１でそれ
以外のビットは総て０であるとして、以下制御回路とア
ドレス参照回路の動作を説明する。

【００５３】まず、現在の読み出しの対象とされている
照合用レジスタが第何層のものかを表すｋは３とし、ま
たレジスタアドレス値は０とする（Ｓ４）。第３層の照
合用レジスタを読み出し、読み出したフラグ値が１か否
かを判定する。このとき第３層の照合用レジスタの値は
１なので、読み出された値は１で、ステップＳ６に進
む。ｋは０でないので、ステップＳ７でＡ（０）として
０、１、２が算出され、その最小値０がｉ_s としてレジ
スタに格納される。ステップＳ８で現在のアドレス値０
を第３層に対応するスタックに格納する。

【００５４】ｋを３から２に代えて（Ｓ９）、ｉ_s とし
てレジスタに格納されている０をレジスタアドレス値と
する（Ｓ１０）。第２層に対応するカウンタに１をセッ
トし（Ｓ１０）、第２層のレジスタアドレス値０で指定
されるビットの値を読み出し、読み出された値が１か否
かを判定する（Ｓ５）。このとき第２層の照合用レジス
タのレジスタアドレス値０で指定されるビットは１にな
っているので、読み出されたフラグ値は１で、ステップ
Ｓ６に進む。ｋは０でないので、ステップＳ７でＡ
（０）として０、１、２が算出され、その最小値０がｉ
_s としてレジスタに格納される。ステップＳ８で現在の
アドレス値０を第２層に対応するスタックに格納する。

【００５５】ｋを２から１に代えて（Ｓ９）、ｉ_s とし
てレジスタに格納されている０をレジスタアドレス値と
する（Ｓ１０）。第１層に対応するカウンタに１をセッ
トし（Ｓ１１）、第１層のレジスタアドレス値０で指定
されるビットの値を読み出し、読み出された値が１か否
かを判定する（Ｓ５）。このとき第１層の照合用レジス
タのレジスタアドレス値０で指定されるビットは１にな
っているので、読み出された値は１で、ステップＳ６に
進む。ｋは０でないので、ステップＳ７でＡ（０）とし
て０、１、２が計算され、その最小値０がｉ_s としてレ
ジスタに格納される。ステップＳ８で現在のアドレス値
０を第１層に対応するスタックに格納する。

【００５６】ｋを１から０に代えて（Ｓ９）、ｉ_s とし
てレジスタに格納されている０をレジスタアドレス値と
する。第０層に対応するカウンタに１をセットし（Ｓ１
１）、第０層のレジスタアドレス値０で指定されるビッ
トのフラグ値を読み出し、読み出されたフラグ値が１か
否かを判定する（Ｓ５）。このとき第０層の照合用レジ
スタのレジスタアドレス値０で指定されるビットは１に
なっているので、読み出されたフラグ値は１で、ステッ
プＳ６に進む。ｋは０なので、ステップＳ１９に進み、
アドレス参照回路からレジスタアドレス値０をデータ検
索回路に出力する（Ｓ１９）。

【００５７】次いでレジスタアドレス値を１だけインク
リメントすることにより１として（Ｓ１３）、第０層に
対応するカウンタのカウント値を２とする（Ｓ１４）。
カウント値２は３より大きくないので、第０層のレジス
タアドレス値１で指定されるビットのフラグ値を読み出
し、読み出されたフラグ値が１か否かを判定する（Ｓ
５）。このとき第０層の照合用レジスタのレジスタアド
レス値１で指定されるビットは０なのでレジスタアドレ
ス値を２として（Ｓ１３）、第０層に対応するカウンタ
のカウント値を３として（Ｓ１４）、カウント値３は３
より大きくないので、第０層のレジスタアドレス値２で
指定されるビットのフラグ値を読み出し、読み出された
フラグ値が１か否かを判定する（Ｓ５）。このとき第０
層の照合用レジスタのレジスタアドレス値２で指定され
るビットは０なので、レジスタアドレス値を３として
（Ｓ１３）、第０層に対応するカウンタのカウント値を
４とする（Ｓ１４）。

【００５８】カウント値４は３より大きいので、ｋを０
から１に代えて（Ｓ１６）、１は３より小さいので、第
１層に対応するスタックに格納されているレジスタアド
レス値０を新たなレジスタアドレス値とし（Ｓ１８）、
このレジスタアドレス値を１だけインクリメントし、レ
ジスタアドレス値１として（Ｓ１３）、第１層に対応す
るカウンタのカウント値を２とする（Ｓ１４）。

【００５９】カウント値２は３より大きくないので、第
１層のレジスタアドレス値１で指定されるビットのフラ
グ値を読み出し、読み出されたフラグ値が１か否かを判
定する。このとき第１層の照合用レジスタのレジスタア
ドレス値１で指定されるビットは０なのでレジスタアド
レス値を２として（Ｓ１３）、第１層に対応するカウン
タのカウント値を３とする（Ｓ１４）。

【００６０】カウント値３は３より大きくないので、第
１層のレジスタアドレス値２で指定されるビットのフラ
グ値を読み出し、読み出されたフラグ値が１か否かを判
定する。このとき第１層の照合用レジスタのレジスタア
ドレス値２で指定されるビットは０なので、レジスタア
ドレス値を３として（Ｓ１３）、第１層に対応するカウ
ンタのカウント値を４とする。

【００６１】カウント値４は３より大きいので、ｋを１
から２に代えて（Ｓ１６）、２は３より小さいので、第
２層に対応するスタックに格納されているレジスタアド
レス値０を新たなレジスタアドレス値とし（Ｓ１８）、
このレジスタアドレス値を１だけインクリメントし（Ｓ
１３）、レジスタアドレス値１として、第２層に対応す
るカウンタのカウント値を２とする（Ｓ１４）。

【００６２】カウント値２は３より大きくないので、第
２層のレジスタアドレス値１で指定されるビットのフラ
グ値を読み出し、読み出されたフラグ値が１か否かを判
定さする（Ｓ５）。このとき第２層の照合用レジスタの
レジスタアドレス値１で指定されるビットは０なのでレ
ジスタアドレス値を２として（Ｓ１３）、第１層に対応
するカウンタのカウント値を３とする（Ｓ１４）。

【００６３】カウント値３は３より大きくないので、第
１層のレジスタアドレス値２で指定されるビットのフラ
グ値を読み出し、読み出されたフラグ値が１か否かを判
定する（Ｓ５）。このとき第１層の照合用レジスタのレ
ジスタアドレス値２で指定されるビットは０なので、レ
ジスタアドレス値を３として（Ｓ１３）、第１層に対応
するカウンタのカウント値を４とする（Ｓ１４）。

【００６４】カウント値４は３より大きいので、ｋを２
から３に代えて、３は３より小さくないので、探索を終
了する。

【００６５】本例によれば、３＊ｌｏｇ₃ ２７＋１、即
ち１０回の判定回数ですみ、シリアルに照合用フラグレ
ジスタを読み出した場合の判定回数２７回に比べ約１／
３の判定回数で総ての判定が終了でき、極めて高速に照
合データを出力することが可能となる。

【００６６】探索キーワードと照合する照合データが複
数ある場合でも、例えば図６に示した構成で、記憶領域
中の上から３つのワードが探索キーワードと照合する照
合データであったとすると、照合用フラグレジスタのレ
ジスタアドレス値０、１、２で示されるビットが１とな
っており、判定回数は照合データが１つのときと変わら
ない。ところが、照合用フラグレジスタ記憶領域中でば
らばらに格納されていた場合、例えば図６に示した構成
で、照合用フラグレジスタのレジスタアドレス値０、
９、１８で示されるビットが１となっていた場合は、２
２回の判定が必要となり、高速化が十分になされない。

【００６７】図６に、照合用フラグレジスタ記憶領域中
でばらばらに格納されていた場合でも、１度用いたこと
のある探索キーワードでの２度目以降の探索を高速に実
行することを可能とする自己学習機能を備える連想記憶
装置を示す。

【００６８】図６に示した連想記憶装置は概ね図１に示
した連想記憶装置と同一の構成を有するものであり、照
合フラグ用レジスタ１０５と第１層のＮ入力１出力ＯＲ
ゲート１０６の間にＭ入力Ｍ出力の交換回路（クロス
バ）６０１とＭビットの第２の照合フラグ用レジスタ６
０２とを備え、第１層のＮ入力１出力ＯＲゲートへの入
力が第２の照合フラグ用レジスタ６０２から成されてい
る点、並びにこれに関連してメモリアクセス制御回路６
０３、メモリ回路（ＲＡＭ）６０４、及びクロスバ切り
替え回路６０５を備えている点で図１に示した連想記憶
装置と異なっている。尚、図６において、図１に示した
連想記憶装置と同一の要素は同一の参照番号が付されて
いる。

【００６９】交換回路６０１は照合フラグ用レジスタ１
０５の各ビットと第２の照合フラグ用レジスタ６０２の
各ビットとを一対一に接続するもので、照合フラグ用レ
ジスタ１０５のどのビットを第２の照合フラグ用レジス
タ６０２のどのビットに接続するかが、クロスバ切り替
え回路６０５によって変更することができるものであ
る。交換回路６０１は例えばルックアップテーブルとす
ることができるが、実際に各ビット間を結線するような
ものでもよい。

【００７０】第２の照合フラグ用レジスタ６０２の各ビ
ットにはレジスタアドレスが付与されており、第１層の
Ｎ入力１出力ＯＲゲート側から見たときは、第１図の実
施例におけるに照合フラグ用レジスタ１０５とまったく
同一にアクセス可能である。更に、第２の照合フラグ用
レジスタ６０２の各ビットは、各ビットが接続する照合
フラグ用レジスタ１０５のビットのレジスタアドレスを
も保持している。

【００７１】ＲＡＭ６０４は例えば全探索対象データ数
の１割り程度の容量をもつもので、レジスタ１１３から
出力された照合データのアドレス、即ち、照合フラグ用
レジスタ１０５において１と判定されたフラグのレジス
タアドレスを記憶するためものである。

【００７２】メモリアクセス制御回路６０３は記憶領域
から読み出された照合データのアドレスをＲＡＭ６０４
に書き込むための回路で、レジスタ１１３から出力がな
される毎に、その照合データのアドレスをＲＡＭ６０４
に格納する。但し、同一のアドレスはＲＡＭ６０４に２
度以上は書き込まないものとする。

【００７３】メモリアクセス制御回路６０３はまたＲＡ
Ｍ６０４が一杯になると、または所定の探索キーワード
での探索が総て終了すると、格納されている内容をクロ
スバ切り替え回路６０５に出力し、その後、新たな書き
込みのためＲＡＭ６０４をクリアする。

【００７４】クロスバ切り替え回路６０５はＲＡＭ６０
４から読み出されるアドレスを昇順にクロスバ６０１の
出力になるように、クロスバ６０１の結線変更又はルッ
クアップテーブルの書換えを行うものである。

【００７５】上記構成における動作を以下に説明する。

【００７６】データの探索自体は図４のフローチャート
に従って行われるが、この際、第２の照合フラグ用レジ
スタ６０２が第０層のレジスタと見做される。また、ア
ドレス参照回路１１０からは、第２の照合フラグ用レジ
スタ６０２でフラグ値が１と判定されたビットがある
と、そのビットのレジスタアドレスを出力する代わり
に、このビットが対応する照合フラグ用レジスタ１０５
のビットのレジスタアドレスが出力される。

【００７７】検索回路１１２はアドレス参照回路１１０
から出力されたレジスタアドレスに基づきこれと同一の
アドレスに格納されるデータを出力レジスタ１１３に出
力する。

【００７８】メモリアクセス制御回路６０３は記憶領域
１０１から読み出された照合データのアドレスをＲＡＭ
６０４に順次書き込む。

【００７９】ＲＡＭ６０４が一杯になると、メモリアク
セス制御回路６０３は、ＲＡＭ６０４に格納されている
アドレス値を、クロスバ切り替え回路６０５に出力す
る。

【００８０】クロスバ切り替え回路６０５はＲＡＭ６０
４から読み出されるアドレスでのフラグが昇順にクロス
バ６０１の出力になるように、クロスバ６０１の結線変
更又はルックアップテーブルの書換えを行う。尚、ＲＡ
Ｍ６０４から出力されなかったアドレスのフラグ、即
ち、探索キーワードに該当しなかったデータに関するフ
ラグは、ＲＡＭ６０４から読み出されるアドレスでのフ
ラグの判定が終わった後にアドレス参照回路にて判定さ
れるように、そのアドレス位置をシフトするものとす
る。

【００８１】以上により、所定のキーワードと照合する
データは、相互に関連するデータと見做され、照合フラ
グは第２の照合用フラグレジスタの、同一又は隣接する
第１層のＮ入力１出力ＯＲゲートに入力する隣接したビ
ットにセットされることになり、このキーワードでの２
度目以降のデータ探索で判定回数を著しく減らすことが
できる。

【００８２】一般にｋ個の照合データが第１層のＮ入力
１出力ＯＲゲートに１つずつ対応した場合、最悪の判定
回数は、 ｋ＊（Ｎ−１）＊ｌｏｇ_N Ｍ＋Ｎ＋１ であるが、本発明にて、クロスバ書替え後は、例えば、
ｋ≦Ｎならば、 Ｎ＊ｌｏｇ_N Ｍ＋１ と減少し、データ探索を極めて高速に実行することが可
能になる。

【００８３】初期状態では照合フラグ用レジスタ１０５
の各ビットのレジスタアドレスと照合フラグ用レジスタ
１０５の各ビットに対応する照合フラグ用レジスタ６０
２の各ビットのレジスタアドレスは同一であったとする
と、図６に示した構成で、照合用フラグレジスタ１０５
のレジスタアドレス値０、９、１８で示されるビットが
１となっていた場合の例では、最初の探索では２２回の
判定が必要であるが、２度目以降は照合用フラグレジス
タ６０２のレジスタアドレス値０、１、２で示されるビ
ットが１となり、１０回の判定で探索が終了することに
なる。

【００８４】第１の実施例、及び第２の実施例はとも
に、最終層Ｋにて１ビットになるまで階層状の論理和演
算を行うが、本発明はこれに限られず、最終層Ｋが実際
上、支障とならない程度に十分に小さいビット長であっ
てもよい。

【００８５】また、最終層のレジスタアドレスから順次
判定を遡るための方法も、記載された方法に限られるも
のではない。

【００８６】

【発明の効果】以上、詳述したように、本願の請求項１
に記載の発明にてなる連想記憶装置によれば、判定回数
を著しく減らすことができ、極めて高速に照合データを
出力することが可能となる。

【００８７】また、本願の請求項２に記載の発明にてな
る連想記憶装置によれば、自己学習機能を有し、同一の
探索キーワードを用いた２度目以降のデータ探索を極め
て高速に実行することが可能となる。

【図面の簡単な説明】

【図１】本発明にてなる連想記憶装置の一例の構成を示
すブロック図である。

【図２】図１に示した連想記憶装置の照合部の回路構成
を示す回路図である。

【図３】図１に示した連想記憶装置のＮ入力１出力ＯＲ
ゲートの構成を示す回路図である。

【図４】図１に示した連想記憶装置におけるデータ探索
のフローチャートである。

【図５】データ数が２７の場合の連想記憶装置の構成を
示すブロック図である。

【図６】本発明にてなる連想記憶装置の他の例の構成を
示すブロック図である。

【図７】従来の連想記憶装置の構成を示すブロック図で
ある。

【符号の説明】

１０１、７０１ 記憶領域 １０２、７０２ キーワードレジスタ １０３、７０３ マスクレジスタ １０４、７０４ 照合部 １０５、７０５ 照合フラグ用レジスタ １０６ 第１層目のＮ入力１出力ＯＲゲート １０７ 第１層目の高速照合用レジスタ １０８ 最終層のＮ入力１出力ＯＲゲート １０９ 最終層の高速照合用レジスタ １１０ アドレス参照回路 １１１ 制御回路 １１２、７０７ 検索回路 １１３、７０８ 出力レジスタ ６０１ 交換回路 ６０２ 第２の照合フラグ用レジスタ ６０３ メモリアクセス制御回路 ６０４ ＲＡＭ ６０５ クロスバ切り替え回路

Claims (2)

【特許請求の範囲】
1. 【請求項１】 複数のデータを蓄積する記憶媒体と、該
   記憶媒体に蓄積されたデータの中から探索キーワードに
   照合するデータをシリアルに探索するための照合手段
   と、該照合手段に接続し照合するデータに対応するビッ
   トに照合フラグが書込まれる照合フラグレジスタと、該
   照合フラグレジスタの各ビットからの出力が並列に入力
   される照合フラグを判定するための照合判定手段とを具
   備し、前記照合判定手段が複数並列にかつ階層状に配列
   された多入力論理和手段及び該論理和手段の出力を判定
   する判定手段を有していることを特徴とする連想記憶装
   置。
2. 【請求項２】 複数のデータを蓄積する記憶媒体と、該
   記憶媒体に蓄積されたデータの中から探索キーワードに
   照合するデータをシリアルに探索するための照合手段
   と、該照合手段に接続し照合するデータに対応するビッ
   トに照合フラグが書込まれる第１の照合フラグレジスタ
   と、該第１の照合フラグレジスタに接続し、照合フラグ
   のビット位置を変更するための交換手段と、該交換手段
   に接続し、変更されたビット位置にて照合フラグが書込
   まれる第２の照合フラグレジスタと、該第２の照合フラ
   グレジスタの各ビットからの出力が並列に入力され、複
   数並列にかつ階層状に配列された多入力論理和手段及び
   該論理和手段の出力を判定する判定手段を有している照
   合フラグを判定するための照合判定手段と、関連のある
   データを第１層目の複数の多入力論理和手段のうち同一
   の多入力論理和手段に入力するように交換手段を切り替
   える切り替え手段とを具備することを特徴とする連想記
   憶装置。