JPH0632225B2 - 連想メモリ装置 - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は内容を指定して、その内容（以下探索データと
称す）がどこに記憶されているかを探る連想動作を行う
連想メモリに係り、複数の連続するデータに対する連想
動作を高速に実行する高速連想メモリ装置に関する。

〔発明の背景〕

情報処理学会編 情報処理ハンドブツクに述べられてい
る通り、構成が簡単な連想メモリでは、探索入力と全記
憶内容との照合を行い、一致する情報があつた場合にそ
の位置を番地として読み取る連想動作と、この番地によ
り情報の読出し、書込みを行うＲＡＭ動作に分かれてい
る。前記の連想動作を行うために、番地を一つずつ変化
させて記憶内容と探索入力との比較を行う必要があり、
記憶内容がＮ個ある場合には、平均してＮ／２回の比較
ののちに一致がとれることとなる。その為連続するＫ個
のデータに対する連想動作には、ＮＫ／２回の比較が必
要である。

連想メモリ装置に関する公開公報としては、特開昭５８
−２００４９４号「連想メモリ装置」および特開昭５９
−８１９５号「連想記憶方式」が知られている。

〔発明の目的〕

本発明の目的は、連続する複数データに対する連想動作
が高速な、高速連想メモリ装置を提供することにある。

〔発明の概要〕

本発明の特徴は、連想メモリ装置として、データメモリ
と、データメモリのアドレスを歩進するカウンタと、複
数個の探索データを記憶する探索データメモリと、該探
索データメモリ中の特定の探索データを選択し出力する
選択手段と、該選択手段により選択された探索データの
うち特定の比較範囲と前記データメモリから読出された
データのうち前記探索データのうち特定の比較範囲に相
当する部分との比較を行う第１の比較手段と、一致した
場合に、該カウンタの歩進を停止する停止手段と、前記
停止手段が働いた場合に、前記データメモリから読出さ
れたデータと前記探索データメモリ中の各データとを、
前記特定の比較範囲により定まる回数まで逐次全ビット
比較する第２の比較手段と、前記第２の比較手段による
比較の結果、全ビットが一致した場合は、比較終了後
に、該カウンタの歩進を停止した次のアドレスから再開
する再開手段とを有することである。

これにより、データメモリの検索に探索データメモリの
検索を併用するため、従来のようにデータメモリのみを
検索するのに比べて、複数の連続する探索データに対す
る連想動作を高速化にすることができる。

〔発明の実施例〕

第１図は本発明の実施例を示す。１０はデータを記憶す
るデータメモリであり、ここにデイレクトリを記憶す
る。２０は探索すべきデータを記憶する探索データメモ
リ、３０は一語の探索データを一時保持するレジスタ、
３５はレジスタのラツチのタイミングを与える信号線
で、本図には省略してあるが、演算器（ＡＬＵ）９０の
出力により制御される。４０はデータメモリ１０の出力
とレジスタ３０の出力とを比較する比較器であり、５０
はデータメモリ１０のアドレスを与えるアドレスカウン
タである。６０は前記カウンタ５０に対するカウントク
ロツクを与えるか否かを制御するゲートであり、７０は
クロツク信号、８０はＡＬＵ９０の出力により制御され
る１ビツトのレジスタである。ＡＬＵ９０は全体の制御
を行うものであり、第１図には省略したメモリに格納さ
れるプログラムによつてその動作は規定される。１００
は探索データメモリ２０に対するアドレスを保持するア
ドレスレジスタであり、１０５は本レジスタのラツチを
指示する信号であり、３５と同様にＡＬＵ９０によつて
発生させられる。１１０はオアゲートであつて、カウン
タ５０の動作をストツプさせる信号を、カウンタ５０の
オーバーフロー出力と、比較器４０の一致出力をオアし
て作り出す。

第２図（Ａ）〜（Ｃ）は、本発明の動作を示すフローチ
ヤートである。第３図は、動作を説明する為の一例を示
す。探索データに対する出力アドレス、及び探索済フラ
グをセツトする領域は、探索データメモリ上に実現す
る。データは全て８ビツトとし、探索データは１０進に
して０から７までの８語の論理アドレスとし、デイレク
トリには２，０，７が夫々アドレス／１０，／１８，／
１Ａに記憶されているものとする。但し／ＸＸは１６進
の数であることを表わす。デイレクトリ中Ｘ−Ｘは探索
データと無関係なデータであることを示し、奇数アドレ
スには論理アドレスに対応する物理アドレスが記憶され
ている。

以下第２図により、第１図の動作を説明する。最初に探
索データメモリのアドレスを／０として設定し、その内
容をレジスタ３０に格納する。この内容は第３図にある
通り、１０進にして０である。該データが既に探索済か
否かを探索データメモリ中に実現した探索済フラグによ
り調べ、探索済である場合はステツプ２９０により更に
全探索データについて操作が完了したか否かを調べる。
完了していれば動作を終結し、完了していなければステ
ツプ３００により探索データメモリのアドレスを歩進し
てステツプ２００に戻る。ステツプ２１０による判定
は、探索が必ずしも探索データメモリのアドレス順に完
了するものでない為に行う。

ステツプ２２０によりアドレスカウンタ５０をクリア
し、ステツプ２３０によりレジスタ８０をセツトしてク
ロツク７０をアドレスカウンタ５０に導き、カウントを
開始させる。アドレスカウンタ５０のクリアはＡＬＵ９
０の出力によるが、本図では省略してある。

次にゲート１１０のＳＴＯＰ出力を監視し、ＳＴＯＰと
なつていればその要因がオーバーフローか否かを判定す
る。オーバーフローであれば、データメモリ中に該探索
データが存在しないことを示す。この場合ステツプ２９
０によつて探索が全て完了したか否かにより次の動作を
定める。オーバーフローであるか否かはアドレスカウン
タ５０の出力をＡＬＵ９０が判定することにより行う。
ステツプ２５０の判定でオーバーフローでなければ比較
器４０の一致出力によつてＳＴＯＰしたのであるが、こ
の場合の比較は全ビツトについて行つたのではない為、
ステツプ２６０にて全ビツトの比較を行う。本例では比
較器４０での比較は８ビツト中上位５ビツトだけ行うも
のとする。ステツプ２６０の判定の結果が一致であれ
ば、そのアドレスを読み取つて記憶し、探索済フラグを
セツトし、前述したステツプ２９０以降の動作に進む。
第３図の例ではアドレス／１０にてＳＴＯＰするが、全
ビツトの比較では一致しておらず、フローチヤートによ
るステツプ３１０へ進む。ステツプ３１０では探索デー
タ「０」とデイレクトリのアドレス／１０の内容を比較
した結果後者の方が大であるためステツプ３２０へ進
む。ステツプ３２０では繰り返し回数を計数するポイン
タをクリアし、アドレスレジスタ１００に探索データの
アドレス／１０をセツトする。ステツプ３３０以下は、
デイレクトリのデータに一致するデータが探索データメ
モリ中に存在するか否かを判定する操作である。ステツ
プ３３０にてアドレスを歩進した結果探索データは
「１」となるがステツプ３４０，３５０の比較の結果が
不一致となるためステツプ３７０へ進む。ステツプ３７
０により全て探索データについて比較したかを判定し、
本例では否の為ステツプ３８０へ進む。ステツプ３８０
では探索データを８回以上比較したかを判定する。比較
器４０にて比較する際に、無視しているビツト数は３で
ある為、８以上離れたデータ同士の比較では一致出力は
出ないため、ステツプ３８０の判定でポインタが８以上
の場合はデイレクトリ側の探索を再開するため、ステツ
プ２３０に進む。第３図の例に従うとステツプ３８０の
判定の結果ステツプ３３０へ戻り、アドレスを歩進した
結果、探索データが「２」となり、ステツプ３４０，３
５０の比較の結果一致する。そこでステツプ３６０にお
いて、この際のカウンタの値／１０を記憶し、探索済フ
ラグをセツトする。その後ステツプ２３０に進んでデイ
レクトリの／１２以降の比較を開始する。次にステツプ
２４０でＳＴＯＰするのはアドレス／１８であり、この
時にはステツプ２６０，２７０の全ビツト比較において
一致の為、ステツプ２８０によりカウンタの出力／１０
を記憶し、探索済フラグをセツトする。ステツプ２９０
の判定で、未だ全ての探索データに対して操作が完了し
ていないと判定し、探索データメモリのアドレスを１歩
進して／１とし、フローの最初の時点より動作を繰り返
す。

第４図は、本発明の他の実施例であり、マスクゲート１
２０，１３０により比較器４０の比較ビツト数を可変と
したもので、動作は第１図の実施例の場合と同一であ
る。但し、フローチヤート第２図中３８０の判定値８を
マスクしたビット数で２のべき乗を計算した結果とする
点が異なる。すなわち、第１図から第３図までに示す例
では、比較範囲を８ビットのデータ中上位５ビットとし
ているが、８ビットのデータ中上位５ビットが一致して
も下位３ビットは異なる可能性があり、全ビットが一致
した場合を含めるとその種類は２の３乗（＝８）で表さ
れる。このように、第２図のフローチャート中ステップ
３８０に示す判定値は、マスクした（即ち、比較対象と
しなかつた）ビット数により定まり、８（＝２の３乗）
となる。

第４図の実施例では、マスクゲート１２０，１３０であ
るＡＮＤゲートによつて、探索データメモリからの出力
およびデータメモリからの出力の所定範囲のビットをマ
スクする。したがつて、マスクデータを変えることによ
り、比較範囲を８ビットのデータ中上位５ビットとする
のみならず、データのビット数の範囲内で任意に設定で
きる。その場合、その比較ビットの異なる種類の数は、
２の（マスクした下位のビット数）乗を計算した値とな
る。

本発明の第１の実施例によれば、デイレクトリのデータ
数をＮ、探索データ数をＫとした場合、従来、全探索が
終了するまでに、平均してＮＫ／２回のデイレクトリの
参照が必要であつたのを、比較器で無視するビット数で
２のべきをとつた値と探索データ数が一致した場合、最
大でデイレクトリを２Ｎ回と、探索データメモリをＫ
（Ｋ＋１）／２回参照することにより全ての探索が完了
する。

一般にはＮはＫに対して大きく、一例としてＮを1000、
Ｋを８とした場合は、本発明実施前のデイレクトリ参照
が平均4000回に対し、実施後は、最大でデイレクトリ参
照2000回と、探索データメモリを３６回参照すれば良い
ことになる。

本発明の第２の実施例によれば、探索データ数に合わせ
て比較器により無視するビット数を変化させることが可
能となり第２図のステップ２４０においてムダにストッ
プする回数を減じ、全体としての動作時間を最小にでき
る。例えば、第１図から第３図までに示す例において、
探索データとして下２ビットが００から始まり４個連続
することにより特徴づけられる場合を考える。この場合
には８ビットのデータ中上位５ビットの比較を行うと２
の２乗ビットが１の場合にもデータメモリ用のアドレス
カウンタが停止し、無駄な比較を行うこととなる。この
場合には８ビットのデータ中上位６ビットの比較を行う
のが最適である。

上記のように探索データの数によりマスクするビット数
を変化させることができれば無駄な比較を行う回数を減
ずることができる。また、その結果、最終の結果を得る
までの時間を短縮できる。

〔発明の効果〕

本発明によれば、デイレクトリ参照が大幅に減り、連続
する複数データに対する連想動作が高速な高速連想メモ
リ装置を提供可能である。

【図面の簡単な説明】

第１図，第４図はそれぞれ本発明の一実施例構成を示
し、第２図は第１図の動作説明用フローチヤート、第３
図は第１図の動作説明用のデータの一例を示すものであ
る。 １０…データメモリ、２０…探索データメモリ、 ３０…レジスタ、４０…比較器、５０…アドレスカウン
タ、９０…ＡＬＵ、１００…アドレスレジスタ。

Claims (2)

【特許請求の範囲】
1. 【請求項１】データメモリと、データメモリのアドレス
   を歩進するカウンタと、 複数個の探索データを記憶する探索データメモリと、該
   探索データメモリ中の特定の探索データを選択し出力す
   る選択手段と、 該選択手段により選択された探索データのうち特定の比
   較範囲と前記データメモリから読出されたデータのうち
   前記探索データのうち特定の比較範囲に相当する部分と
   の比較を行う第１の比較手段と、一致した場合に、該カ
   ウンタの歩進を停止する停止手段と、 前記停止手段が働いた場合に、前記データメモリから読
   出されたデータと前記探索データメモリ中の各データと
   を、前記特定の比較範囲により定まる回数まで逐次全ビ
   ット比較する第２の比較手段と、 前記第２の比較手段による比較の結果、全ビットが一致
   した場合は、比較終了後に、該カウンタの歩進を停止し
   た次のアドレスから再開する再開手段とを有することを
   特徴とする連想メモリ装置。
2. 【請求項２】前記特定の比較範囲は、比較範囲設定手段
   により任意に設定できることを特徴とする特許請求の範
   囲第１項記載の連想メモリ装置。