JPS61283096A - 連想メモリ - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は連想処理等に用いられるデータ内容により検
索を行なう連想メモリに関するものである。

〔従来の技術〕

第３図は従来の連想メモリを示すものであシ。

Ｇυはデータの特性を数ビツト程度のデータ量で表現さ
れた参照タグが入力される入力バス、　Ｇ３はこの入力
バスに接続された８個のタグ比較回路（Ｓ２ａ）〜（３
２ｇ）からなるタグ比較回路群で、それぞれのタグ比較
回路はデータの特性を数ビツト程度のデータ量で表現さ
れたタグを記憶しているタグメモリと、このタグメモリ
のタグと上記人力バス０υからの参照タグとをビット単
位で比較して両者一致した場合一致信号を出力する比較
器とを有しているものである。（至）はこのタグ比較回
路群０３のタグ比較回路（３２ａ）〜（３２ｓ）と対応
して接続され、それぞれ個々のデータを記憶している８
個のデータメモリ（３３ａ）〜（３３ａ）からなるデー
タメモリ群で上記タグ比較回路（３２ａ）〜（３２ｓ）
からの一致信号を受けたデータメモＩＪ　（３２ａ）〜
（５３Ｂ）のデータが出力バス（ロ）に出力されるもの
である。

次にこの様に構成された連想メモリの動作について説明
する。入力バス０１１にアクセスしたいデータの特性を
示す数ビットの参照タグが入力されてこの参照タグがタ
グ比較回路群Ｃ（３の各タグ比較回路（３２ａ）〜（３
２８）　Ｋ入力される。各タグ比較回路較して全ビット
で一致した場合に一致信号が出力される。この一致信号
はタグ比較回路（３２ａ）〜（３２ａ）のうちの１つの
タグ比較回路から出力されるものであシ、残りのタグ比
較回路からは出力されない。

この一致信号を受けたデータメモリ群（至）の一致信号
を出力したタグ比較回路に対応したデータメモリのデー
タが出力バスＩ３４に出力されることＫなる。

〔発明が解決しようとする問題点〕

しかるに、この様に構成された連想メモリにあっては、
出力バス（ロ）にデータメモリ群（至）の全てのデータ
メモリ（３３ａ）〜（３３θ）が接続されているため、
２つ以上のデータメモリからデータが出力されるとデー
タの競合が起るので、１つのデータメモリからしか出力
されないようにしである。

従って入力バス０ηに入力される参照タグ及びタグ比較
回路（３２ａ）〜（ＳＺａ）のタグメモリのタグとデー
タメモリ（３２ａ）〜（３２ａ）のデータとが１対１に
対応させる必要があシ、用途が限定されてしまうもので
あった。さらに、入力バスＧυに入力される参照タグが
タグ比較回路群Ｇ３で比較されてデータメモリ群（至）
からデータが出力バス［有］に出力されるまで２次の参
照タグを入力できないことから。

読み出しスルーレートが遅いという問題を有するもので
あった。しかも入力バスＩ３υ及び出力バス（２）の線
長け、データ容量の増大に伴なって長くなるため、デー
タ量の増大に伴ないバスのドライブに時間がかかるとい
う問題を有するものであった。

この発明は上記した点に鑑みてなされたものであシ、１
つの参照タグに対して複数のデータをアクセスすること
ができ、読み出しスルーレートが向上するパイプライン
形連想メモリを得ることを目的とするものである。

〔問題点を解決するための手段〕

この発明に係る連想メモリは、データメモリに記憶され
たデータの属性を示すタグが記憶されたタグメモリと、
このタグメモリのタグと参照タグラッチにラッチされた
参照タグとを比較して一致信号を出力するタグ比較回路
と、この比較回路からの一致信号に応じてデータメモリ
のデータを選択出力するセレクタと、セレクタからの選
択出力をラッチするデータ出力ラッチとを有しているも
のである。

〔作用〕

この発明においては、各レジスタの段間において；　タ
グ比較回路が参照タグラッチにラッチされた参照タグと
タグメモリに記憶されたタグとを比較し、このタグ比較
回路からの一致信号に基づきセレクタがデータメモリに
記憶されたデータをデータ出力ラッチに選択出力するも
のである。

〔実施例〕

以下にこの発明の一実施例を第１図及び第２図に基づい
て説明する。図において（１ａ）〜（１ｄ）はデータの
特性を８ビツトのデータ量で表現されたアクセスデータ
となる参照タグをラッチする参照タグラッチで、入力さ
れる非同期信号の立上がシによシ次段の８照タグラツチ
ヘラツチしている参照タグを転送するものである。（２
ａ）〜（２ｄ）は出力するための１６ピツトのデータが
ラッチされるデータ出力ラッチで、入力される非同期信
号の立上がりにより次段ヘラッチしているデータを転送
するものである。（３ａ）〜（３ｄ）は１ビツトの一致
信号をラッチする一致信号ラッチで、入力される非同期
信号の立上がシによシ次段ヘラッチしている一致信号を
転送するものである。（４ａ）〜（４ｄ）はデータの特
性を８ビツトのデータ量で表現されたタグが記憶された
タグメモリ、　　（５１）〜（５ｄ）は１６ピツトのデ
ータが記憶されたデータメモリで上記タグメモリのタグ
と対応したデータとなっている。（６ｂ）〜（６ｄ）は
前段の参照タグラッチ（１ａ）（１ｄ）　　にラッチさ
れた参照タグと前段のタグメモリ（４ａ）〜（４ｄ）に
記憶されたタグとをビット単位毎に比較して８ビツトの
比較結果信号、一致の時は’Ｈ”、不一致の時は“Ｌ″
、を出力するビット比較器ｓ　　（７ａ）〜（７ｄ）は
それぞれこれらビット比較器（６ａ）〜（６ｄ）からの
８ビツトの比較結果信号をラッチする比較結果ラッチで
、入力される非同期信号の立上がシによシ井碇１ラッチ
している比較結果信号を次段へ転送するものである。（
８ａ）〜（８ｄ）は前段の比較結果ラッチ（７ａ）〜（
７ｄ）にラッチされた比較結果信号が入力されるＡＮＤ
ゲートで。

比較結果信号の８ビツト全てが“Ｈ”の時“Ｈ″からな
る一致信号を出力するものである。（９ｂ）〜（９ｄ）
は複数データアクセス制御器で、詳細は第２図を用いて
後記する。（１０ａ）〜（１ｏｄ）は１ビツトの既一致
信号をラッチする既一致信号ラッチで。

前段の一致信号ラッチ（３ａ）〜（３ｄ）からの一致信
号あるいは前段の既一致信号ラッチからの既一致信号を
上記複数データアクセス制御器（９ｂ）〜（９ｄ）を介
して受けた場合に既一致信号をラッチするものであシ、
入力される非同期信号の立上がりによ如次段へ既一致信
号を転送するものである。

（１１ａ）〜（１１ｄ）は１ビツトのタグ先頭信号をラ
ッチするタグ先頭信号ラッチで、入力される非同期信号
の立上がシによシ次段へタグ先頭信号を転送するもので
ある。（１２ａ１Ｘ１２ａ２）　〜（１２ｄ１）　％　
（１２ｄ２）　’は上記参照タグラッチ（１ａ）〜（１
ｄ）　、データ出力ラッチ（２ａ）　〜（２ｄ）　？一
致倍信号ラッチ３ａ）　〜（３ｄ）　＊比較結果ラッチ
（７ａ）〜（７ｄ）、既一致信号ラッチ（１０ａ）〜（
１ｏｄ）及びタグ先頭信号ラッチ（１１ａ）〜（１１ｄ
）に非同期信号を出力する１対の自己同期要素で、前段
からの出力信号“■”と次段からの空きを示すｒｅａｄ
ｙ信号“Ｈ″を受けると出力信号“Ｈ″を次段へ出力す
るものであシ、前段からの出力信号と次段のｒｅａｄｙ
信号のどちらか一方が“Ｌ″の時は出力信号が“Ｌ”と
なるものである。（１！＋１））〜（１３１１１）は前
段のデータ出力ラッチ（ｚａ）　〜（２ｄ）　Ｋ　：１
７ｙチされたデータと３段前のデータメモリ（５ａ）〜
（５ｄ）に記憶されたデータとが入力され、上記複数デ
ータアクセス制御器（９ａ）（９ｄ）からの１ビツトの
選択信号によシ上記入力されたデータを選択出力するセ
レクタである。

そして、上記参照タグラッチ（１ａ）〜（ｉｄ）ｔデー
タ出力ラッチ（２ａ）〜（２ｄ）　、一致信号ランチＣ
３ｅｔ）　〜（３（Ｌ）　、比較結果ラッチ（７ａ）　
〜（７ｄ）　、既（１２（ＬＩＸ１２ｄ２）　　によシ
非同期シフトレジスタａ〜ｄを構成しておシ、一対の自
己同期要素（１２ａ１）〜（１２＆２）〜（１２ｄ１）
（１２ｄ２）からの非同期信号に基づき各ラッチにラッ
チされたデータがシフトされるものである。また、非同
期シフトレジスタａ〜ｄの股間にはビット比較器（６ｂ
）〜（Ｓｄ）　、比較結果ラッチ（７ｂ）〜（７ｄ）及
びＡＮＤゲート（８ｂ）〜（８ｄ）からなるビット比較
回路ｂ　％　ｄが設けられるとともに複数データアクセ
ス制御器（９ｂ）〜（９ｄ）が設けられているものであ
る。さらに、タグの一致判定から転送データの選定まで
の処理を。

（Ｉ）ビット比較器（６ｂ）〜（６ｄ）によるタグのビ
ット毎の比較、（１１）ＡＮＤゲート（８ｂ）〜（８ｄ
）による比較結果からの一致信号生成、（■）複数デー
タアクセス制御器（９ｂ）〜（９ｄ）及びセレクタ（１
３ｂ）〜（１３ｄ）による転送データの判断及び選定と
いう３つのパイプラインステージを有しておシ、これら
３つのパイプラインステージは同時並列実行されるもの
である。

次にこの様に構成された連想メモリの動作について説明
する。まず、動作の理解を助けるために参照タグラッチ
（１ａ）　　Ｋラッチされた参照タグとデータメモリ（
ＳＬ）　　に記憶されたデータの特性を現わすタグラッ
チ（４ａ）にラッチされたタグとが一致した場合につい
て説明する。参照タグラッチ（１ａ）にラッチされた参
照タグとタグラッチ（４ａ）にラッチされたタグとがビ
ット比較器（６１））　　Ｋてビット単位毎に比較され
て８ビツトの比較結果信号として比較結果ラッチ（７ｂ
）にラッチされる。

この時弁解タグとタグとが一致したものとしているので
全てのビットが■”である。そして、自己同期要素（１
２１）２）からの非同期信号がこの比較結果ラッチ（７
ｂ）に入力されると、ラッチされた比較結果信号はＡＮ
Ｄゲート（８Ｃ）に入力され。

１ビツトの“Ｈ”からなる一致信号を複数データアクセ
ス制御器（９Ｃ）を介して一致信号ラッチ（３Ｃ）にラ
ッチされる。次に自己同期要素（１２Ｃ２）からの非同
期信号がこの一致信号ラッチ（３Ｃ）に入力されると、
ラッチされた一致信号は複数データアクセス制御器（９
ａ）　　Ｋ入力され、この複数データアクセス制御器（
９ｄ）から既一致信号として既一致信号ラッチ（１ｏｄ
）　ＫラッチさせるとともＫ。

選択信号をセレクタ（１３ｄ）に出力し、データメモリ
（５ａ）からのデータをセレクタ（１３ｃＬ）　Ｋて選
択させてデータ出力ラッチ（２ｄ）　　Ｋラッチさせる
。

この様にしてデータ出力ラッチ（２ｄ）　　Ｋラッチさ
れ゛たデータは非同期に順次転送され、最終段のデータ
出力ラッチからデータとして出力されるものである。

従って２通常動作においては初段の参照タグラッチに複
数の参照タグが順次入力され、各段の一対の自己同期要
素（１２ｂ１）（１２ｂ２）〜（１２”１）　（１２ｄ
２）からの非同期信号によシ参照タグラッチ（１ａ）〜
（１ｄ）にラッチされた参照タグ、データ出力ラッチ（
２ａ）〜（２ｄ）にラッチされたデータ、一致信号ラッ
チ（３ａ）〜（３ｄ）　Ｋラッチされた一致信号、比較
結果ラッチ（７ａ）〜（７ｄ）にラッチされた比較結果
信号、既一致信号ラッチ（１０ａ）〜（１０ｄ）及びタ
グ先頭信号ラッチ（１１ａ）〜（１１ｄ）Ｋラッチされ
たタグ先頭信号が順次次段へ転送され、参照タグにより
アクセスされたデータは最終段のデータ出力ラッチから
順次出力されるものである。そして。

送される間に、　（１）ビット比較器（６ｂ）〜（６ｄ
）による参照タグラッチ（１ａ）〜（１Ｃ）にラッチさ
れたタグとタグラッチ（４ａ）〜（４Ｃ）にラッチされ
たタグの とｔビット毎の比較、（１）ＡＮＤゲート（８ａ）〜（
８ｅＬ）　　Ｋよる比較結果ラッチ（７ａ）　〜（７０
）にラッチされた比較結果信号に基づく一致信号の生成
。

（１）複数データアクセス制御器（９ｂ）〜（９ｄ）及
びセレクタ（１３ｂ）　〜（１３ｄ）によるデータラッ
チ（５ａ）にラッチされたデータとデータ出力ラッチ（
２Ｃ）にラッチされた出力データの選定をパイプライン
的に実行されているものである。

また、この様に構成された連想メモリにおいては、タグ
ラッチ（４ａ）〜（４ｄ）のタグ内容が重複してもデー
タの競合が起ることがないため、参照タグとタグとが既
に一致していても、その参照タグについて再度一致した
タグを選定できるものである。この時、再度一致するタ
グを持つデータが存在すると、それまで転送されていた
データを複数データアクセス制御器によシ一旦停止し、
再度一致したタグを持つデータを先に次段のデータ出力
ラッチに転送させ、停止していたデータの転送を再び開
始するようにしているものである。従って１つの参照タ
グに対し、複数のデータをアクセスして最終段のデータ
出力ラッチから出力できるもして説明する。一致信号ラ
ッチ（３Ｃ）、既一致信号ラッチ（１０ｃ）及びタグ先
頭信号ラッチ（１１Ｃ）に“Ｈ″信号ラッチされていな
い場合には、ゲー）　（１８ｄ）の出力信号が“Ｌ”に
なりこの“Ｌ”信号がセレクタ（１３ｄ）に入力される
ことによりデータ出力ラッチ（２Ｃ）にラッチされたデ
ータが選択されてデータ出力ラッチ（２ｄ）に転送され
るものである。一致信号ラッチ（３Ｃ）に■”信号がラ
ッチされており、既一致信号ラッチ（１ｏｅ）及びタグ
先頭信号ラッチ（１１０）　Ｋ″Ｈ″Ｈ″信号チされて
いない場合には、ゲー）　（１８ｄ）の出力信号が“Ｈ
″になシ、この“Ｈ″信号セレクタ（１３ｄ）に入力さ
れることによシデータメモリ（５ａ）に記憶されたデー
タが選択されてデータ出力ラッチ（２ｄ）に転送される
ものであシ、シかも、一致信号ラッチ（３Ｃ）からの“
■”信号によυゲート（１６ｄ）から“■”つまわタグ
先頭信号が出力されてタグ先頭信号ラッチ（１１ｄ）Ｉ
ｃラッチされるとともにゲー）　（１５ｄ）から“ＨＮ
つまシ既一致信号が出力されて既一致信号ラッチ（１０
ｄ）にラッチされるものである。

一致信号ラッチ（３Ｃ）　　ｌ既一致信号ラッチ（１０
ｄ）及びタグ先頭信号ラッチ（１１ｄ）全てに“■”信
号がラッチされている場合には、ゲー）　（１８（１）
の出力信号が“Ｈ”になり、この“Ｈ”信号がセレクタ
（１３（Ｌ）　Ｋ入力されることによシャデータメモリ
（５ａ）に記憶されたデータが選択されてデータ出力ラ
ッチ（２ｄ）に転送され、しかも、一致信号ラッチ（３
Ｃ）からの“Ｈ”信号によシゲート（１６ｄ）からタグ
先頭信号が出力されてタグ先頭信号ラッチ（１１ｄ）に
ラッチされるとともにゲート（１Ｓａ）から既一致信号
が出力されて既一致信号ラッチ（１０ａ）にラッチされ
るものである。これと同時に、フリップフロップ（１４
ｄ）がリセットされてゲート（１７ｄ）の出力を“Ｈ”
にして、データ出力ラッチ（２ｄ）　を一致信号ラッチ
（３ｄ）　ｔ　タグ先頭信号ラッチ（１１ｄ）、既一致
信号ラッチ（１ｏｄ）等のデータを次段へ転送するとと
もに自己同期要素（１２ｄ２）の出力が“Ｌ”となって
前段からの転送を遮断する。そして９次段への転送が終
了するとゲート（２Ｏａ）の出力が“Ｌ″になシッフリ
ップフロップ（１４（１）をセットし、自己同期要素（
１２（１２）　　の出力が“Ｈ”となって前段からの転
送が許可状態となるため、ゲート（１８ｄ）の出力が“
Ｌ”になシアセレクタ（１３（１）によシデータ出力ラ
ッチ（２Ｃ）にラッチされたデータがデータ出力ラッチ
（２ｄ）に転送される。この時、ゲー）　（ｉ５ｄ）か
ら既一致信号が出力されるものの、ゲート（１６（１）
からはタグ先頭信号は解除されるものである。

〔発明の効果〕

この発明は以上に述べたように、データメモリタグメモ
リ、参照タグラッチ及びデータ出力ラッチのレジスタの
股間においてタグ比較回路が参照タグラッチにラッチさ
れた参照タグとタグメモリに記憶されたタグとを比較し
、このタグ比較回路からの一致信号に基づきセレクタが
上記参照タグと一致したタグに対応するデータメモリに
記憶されたデータをデータ出力ラッチに選択出力するよ
５にしたので、データのアクセス時間が短縮できるとい
う効果な有するものである。

また、一つの参照タグに対して一致するタグを複数もた
せることも可能なものである。

【図面の簡単な説明】 第１図はこの発明の一実施例を示す要部ブロック図、第
２図は複数データアクセス制御器と自己同期要素を示す
論理図、第３図は従来の連想メモリを示すブロック図で
ある。 図において（１ａ）　−＝　（ｔａ）は参照タグラッチ
。 （２ａ）　〜（２ｄ）はデータ出力ラッチ、（４ａ）〜
（４ｄ）はタグメモリ、　　（５ａ）〜（５ｄ）はデー
タメモリ。 （６ｂ）〜（６ｄ）はビット比較器、　　（７ｂ）〜（
７ｄ）は比較結果ラッチ、（８ｂ）〜（８ｄ）はＡＮＩ
）ゲート。 （１３／ｂ）〜（１３４）はセレクタである。

Claims (1)

【特許請求の範囲】
1. 　データが記憶されたデータメモリを複数段有するデー
   タメモリ群、上記各データメモリ対応し、各データメモ
   リに記憶されたデータの属性を示すタグが記憶されたタ
   グメモリを複数段有するタグメモリ群、参照タグをラッ
   チする参照タグラッチを複数段有する参照タグラッチ群
   、同一段に存在する上記タグメモリのタグと上記参照タ
   グラッチの参照タグとを比較して一致信号を出力するタ
   グ比較回路を複数有するタグ比較回路群、上記タグ比較
   回路からの一致信号に応じて上記データメモリのデータ
   を選択出力するセレクタを複数有するセレクタ群、上記
   セレクタからの選択出力をラッチするデータ出力ラッチ
   を複数段有するデータ出力ラッチ群を備えた連想メモリ
   。