(57)【特許請求の範囲】
【請求項１】
データとそのマスクデータとの対から成るワードを格納する連想メモリセルを有し、検索データと一致するワードのうち、最短のマスクをワイアード論理によって得る最短マスク線を有し、前記最短のマスクを出力する機能を具備した最短マスク出力機能付連想メモリ装置において、
前記最短マスク線の値を保持するラッチを備え、
データ・セルに対応する比較器へ、検索データの各ビットである、比較対象ビット情報を入力する信号線と、マスク・セルに対応するマスク比較器への比較対象ビットを入力する信号線が、分離されて配設されており、
前記ラッチの出力線は、前記マスク比較器への比較対象ビットを入力する信号線に接続されており、
検索はデータセルに対する比較と、マスクセルに対する比較という２つの比較動作から成り、
連続した検索を行う際、先行する検索のマスクセルに対する比較動作と、次の検索のデータセルに対する比較動作を同時に実行する構成としてなることを特徴とする最短マスク出力付連想メモリ装置。
【請求項２】
データとそのマスクデータとの対から成るワード構成をもち、データ・セルと、マスク・セルと、前記データ・セルに対応する比較器と、前記マスク・セルに対する比較器と、を備えた連想メモリ・セルを複数有し、検索データと一致するワードのうち、最短のマスクをワイアード論理によって得る最短マスク線とを有し、前記最短のマスクを出力する機能を具備した最短マスク出力機能付連想メモリにおいて、
前記データ・セルに対応する前記比較器へ検索データの各ビットである比較対象ビット情報を入力する第１のビット線と、
前記マスク・セルに対応するマスク比較器へ前記最短マスクの各ビットである比較対象ビット情報を入力する第２のビット線と、
前記最短マスク線の値を保持するラッチと、
を備え、
前記第１のビット線には、検索データの対応するビット情報を入力し、
前記第２のビット線には、前記ラッチの出力線が接続され、前記最短マスク線の対応するビット位置のビット情報が入力される、ことを特徴とする最短マスク出力機能付き連想メモリ装置。
【請求項３】
ｎビットｍ語の連想メモリ・ワードを構成する各連想メモリ・セルが、データ・セルと、マスク・セルと、前記データ・セルに対応する比較器と、前記マスク・セルに対応する比較器と、前記データ・セルの比較器の出力に接続された一致線の状態と前記マスク・セルのマスク情報との論理演算を行う論理ゲート回路とを備え、
前記論理ゲート回路の出力がｍ語の前記連想メモリ・ワードに対して共通に設けられた最短マスク線にワイアード論理接続し、
前記データ・セルに対応する比較器へ比較対象ビット情報を入力する第１のビット線と、前記マスク・セルに対応するマスク比較器へ比較対象ビット情報を入力する第２のビット線とを互いに分離して備え、
前記データ・セルに対応する比較器へ比較対象ビット情報を入力する前記第１のビット線には、検索データの対応するビット情報が供給されて第１の比較を行い、
前記マスク・セルに対応するマスク比較器へ比較対象情報を入力する前記第２のビット線には前記最短マスク線の状態をラッチする回路から対応するビット位置のビット情報が供給されて第２の比較を行う構成とされ、
連続した検索を行う際、先行した検索の前記第２の比較と、次の検索の第１の比較を同時に実行可能とした、ことを特徴とする最短マスク出力機能付き連想メモリ装置。
【請求項４】
ｎビットｍ語の連想メモリ・ワードと、
ｍ語の前記連想メモリ・ワードに対して共通に設けられた計ｎ本の最短マスク線をそれぞれラッチするｎビットラッチと、を備え、
前記各連想メモリ・ワードは、それぞれ、
ｎ個の連想メモリ・セルと、
前記ｎ個の連想メモリ・セルに対して共通に設けられた一致線の状態をラッチし、出力がマスク一致線に接続されるラッチと、を備え、
前記連想メモリ・セルは、外部からビット線を介して入力される記憶データの対応するビット情報を格納するデータ・セルと、
前記データ・セルに記憶されたビット情報と外部から入力される検索データの対応するビット情報とを比較し出力が前記一致線にワイアード接続されるデータ比較器と、
外部からビット線を介して入力されるマスク情報の対応するビット情報を格納するマスク・セルと、
前記マスク・セルに記憶されたビット情報と前記ｎビットラッチからラッチ出力線を介して出力された最短マスク情報の対応するビット情報とを比較し出力がｎ個の連想メモリ・セルに対して共通に設けられたマスク一致線にワイアード接続されるマスク比較器と、
前記一致線と前記マスク・セルに格納されたマスク情報の値を入力し出力が前記最短マスク線に接続され、前記一致線が有効状態であり、かつ前記マスク・セルに格納されたマスク情報が無効状態のときに無効状態を出力し、それ以外の場合には開放状態とする論理ゲート回路と、を備え、
１回目の検索動作では、検索データがビット線から前記各連想メモリ・ワードへ同時に入力され、前記各連想メモリ・ワードに含まれる前記データ・セルの値が前記データ比較器にて前記マスク・セルの情報をマスクとして前記ビット線の値と比較され、一致した連想メモリ・ワードでは対応する一致線が有効化され、前記最短マスク線に前記マスク・セルの値が出力され、一致しないエントリでは一致線は有効化されず前記最短マスク線には非有効状態が出力され前記最短マスク線上でワイアード論理積をとった結果が前記ｎビット・ラッチに格納されるとともに、前記ｍ語の連想メモリ・ワードの一致線の状態も対応するラッチに格納され、
２回目の検索動作では、前記ｎビットラッチの出力データが前記ラッチ出力線から前記各連想メモリ・ワードのマスク比較器へと入力され、
前記各連想メモリ・ワードでは前記ラッチ出力線の値と、前記マスク・セルの値を比較し、一致した連想メモリ・ワードではマスク一致線が有効化され検索結果を得る構成とされ、連続した検索を行う際、先行した検索の２回目の検索動作と、次の検索の１回目の検索動作を同時に実行することができるようにしたことを特徴とする最短マスク出力機能付連想メモリ装置。
【請求項５】
ＩＰ（Internet  Protocol）パケットのフォワーディング処理を行なうルータに用いられる連想メモリ装置であって、宛先フィールドとこれに対応する出力インタフェース情報フィールドの組よりなるＩＰフォワーディングテーブルを請求項４に記載の最短マスク出力機能付連想メモリ装置で構成し、
１段目の検索で、ＩＰアドレスの最上位ビットから任意長さのビット分だけ指定したプレフィクスデータが、検索データと一致する連想メモリセル・ワード（「エントリ」という）を決定するとともに、一致するエントリ中で最長のプレフィクスを持つエントリの最短マスクの決定を行ない、
２段目で、前記１段目で決定された最短マスク情報を連想メモリセルのマスク比較器に供給し、最短マスク情報をもつ連想メモリセル・ワードのマスク一致線が有効状態とされる、こと特徴とする連想メモリ装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、連想メモリに関し、特に、マスク機能を具備した連想メモリに関する。
【０００２】
【従来の技術】
記憶データ１語ごと、または複数語ごとにマスク情報を有する連想メモリとして、例えば特開平１−２２０２９３号公報等に記載されているように、通常の記憶回路と同様にアドレスを指定して記憶データの書き込み、読み出しを行う機能のほかに、入力した検索データと同一の記憶データが格納されているアドレスを出力する検索、またはマスク情報により記憶データの一部を比較対照から除外した検索を行い、検索の結果一致する記憶データが格納されているアドレスを出力する機能を具備している。
【０００３】
また例えば本願出願人による特開平１１−０７３７８２号公報には、複数の記憶データが検索データと一致したときに、その中で最短のマスクをもつものを選択する機能を具備した最短マスク出力機能付連想メモリが開示されている。
【０００４】
従来の最短マスク出力機能付連想メモリとして、上記特開平１１−０７３７８２号公報に記載されている最短マスク出力機能付連想メモリについて以下に説明する。
【０００５】
図８は、上記特開平１１−０７３７８２号公報に記載されている最短マスク出力機能付連想メモリの構成の一例を示すブロック図である。
【０００６】
図８を参照すると、この連想メモリ１０は、ｎビット２入力１出力セレクタ１７と、ｎビットｍ語の連想メモリ・ワード８−１〜８−ｍと、ｎビットラッチ２１とを有している。
【０００７】
各連想メモリ・ワード８−ｊ（但し、１≦ｊ≦ｍ）は、それぞれ、ｎ個の連想メモリ・セル１２−ｊ−１〜１２−ｊ−ｎと、１個のラッチ２０−ｊを備えている。
【０００８】
各連想メモリ・セル１２−ｊ−ｋ（但し、１≦ｋ≦ｎ、１≦ｊ≦ｍ）は、外部からビット線６−ｋ（但し、１≦ｋ≦ｎ）を介して入力される記憶データの対応するビット情報を格納するデータ・セル９−ｊ−ｋ（但し、１≦ｋ≦ｎ、１≦ｊ≦ｍ）と、データ・セル９−ｊ−ｋに記憶されたビット情報と外部から入力される検索データの対応するビット情報１０５−ｋとを比較する比較器１１−ｊ−ｋと、外部からビット線６−ｋを介して入力されるマスク情報の対応するビット情報を格納するマスク・セル１０−ｊ−ｋと、マスク・セル１０−ｊ−ｋに記憶されたビット情報とｎビットラッチ２１から出力された最短マスク情報の対応するビット情報２２−ｋとを比較するマスク比較器１８−ｊ−ｋと、論理ゲート１３−ｊ−ｋと、を備えている。
【０００９】
図９は、図８に示した連想メモリ・セルの構成の一例を示す図である。図９において、２本のビット線６ａ、６ｂは、図８に示されている各ビット線に対応するものであるが、図８では、６−ｉ（但し、１≦ｉ≦ｎ）で表わしている。
【００１０】
この２本のビット線６ａ、６ｂを介して連想メモリ・セルへのデータの読み書きや、検索データ１０５の入力を行う。
【００１１】
データを書き込む場合、および検索データの入力を行う場合には、ビット線６ｂには、ビット線６ａの値を反転した値を入力する。
【００１２】
データ・セル９は、入力端と出力端が相互に接続されフリップフロップを構成する反転論理ゲート（Ｇ１）２０１及び反転論理ゲート（Ｇ２）２０２と、反転論理ゲート（Ｇ２）２０２の出力端とビット線６ａとの間に挿入されゲートがデータ・ワード線１４が接続されデータ・ワード線１４がハイ・レベル／ロウ・レベルのときに導通状態／非導通状態となりトランスファゲートとして機能するＭＯＳトランジスタ（Ｔ１）２０３と、反転論理ゲート（Ｇ１）２０１の出力端とビット線６ｂとの間に挿入されゲートがデータ・ワード線１４に接続されデータ・ワード線１４がハイ・レベル／ロウ・レベルのときに導通状態／非導通状態となりトランスファゲートとして機能するＭＯＳトランジスタ（Ｔ２）２０４と、を備えて構成されており、このデータ・セル９の構成は、一般的なスタティックＳＲＡＭ（スタティックランダムアクセスメモリ）素子と等価の構成とされる。
【００１３】
また、マスク・セル１０も、入力端と出力端とが相互に接続されフリップフロップを構成する反転論理ゲート（Ｇ３）２０９及び反転論理ゲート（Ｇ４）２１０と、反転論理ゲート（Ｇ４）２１０の出力端とビット線６ａとの間に挿入され、ゲートがマスク・ワード線１５に接続されマスク・ワード線１５がハイ・レベル／ロウ・レベルのときに導通状態／非導通状態となりトランスファゲートとして機能するＭＯＳトランジスタ（Ｔ７）２１１と、反転論理ゲート（Ｇ３）２０９の出力端とビット線６ｂとの間に挿入され、ゲートがマスク・ワード線１５に接続され、マスク・ワード線１５がハイ・レベル／ロウ・レベルのときに導通状態／非導通状態となりトランスファゲートとして機能するＭＯＳトランジスタ（Ｔ８）２１２と、を備えて構成されており、このマスク・セルも一般的なスタティックＳＲＡＭ素子である。
【００１４】
比較器１１は、ＭＯＳトランジスタ（Ｔ３）２０５、ＭＯＳトランジスタ（Ｔ４）２０６、ＭＯＳトランジスタ（Ｔ５）２０７、ＭＯＳトランジスタ（Ｔ６）２０８により構成されている。
【００１５】
ＭＯＳトランジスタ（Ｔ３）２０５とＭＯＳトランジスタ（Ｔ４）２０６は、ビット線６ａ、６ｂの間に直列に挿入されており、ＭＯＳトランジスタ（Ｔ３）２０５は、そのゲートが、データ・セ９内の反転論理ゲート（Ｇ１）２０１の出力端に接続され、反転論理ゲート（Ｇ１）２０１の出力端がハイ・レベルのときに導通状態となり、ＭＯＳトランジスタ（Ｔ４）２０６は、そのゲートが、データ・セル９内の反転論理ゲート（Ｇ２）２０１の出力端に接続され、反転論理ゲート（Ｇ２）２０１の出力端がハイ・レベルのときに導通状態となる。
【００１６】
ＭＯＳトランジスタ（Ｔ５）２０７とＭＯＳトランジスタ（Ｔ６）２０８は、低電位電源と、一致線７との間に直列に挿入され、ＭＯＳトランジスタ（Ｔ５）２０７は、そのゲートがＭＯＳトランジスタ（Ｔ３）２０５とＭＯＳトランジスタ（Ｔ４）２０６との接続点に接続され、該接続点の電位がハイ・レベルの時に導通状態となる。
【００１７】
ＭＯＳトランジスタ（Ｔ６）２０８は、そのゲートが、マスク・セル１０内の反転論理ゲート（Ｇ３）２０９の出力端に接続され、反転論理ゲート（Ｇ３）２０９の出力端がハイ・レベルの時に導通状態となる。
【００１８】
ビット線６ａと反転論理ゲート（Ｇ１）２０１の出力端がともにハイ・レベル、またはビット線６ｂと反転論理ゲート（Ｇ２）２０２の出力端がともにハイ・レベルのときに、ＭＯＳトランジスタ（Ｔ３）２０５とＭＯＳトランジスタ（Ｔ４）２０６の接続点はハイ・レベルとなり、ＭＯＳトランジスタ（Ｔ５）２０７が導通状態となる。
【００１９】
従って、データ・セル９に格納されている記憶データと、ビット線６ａ、６ｂ上の検索データ１０５が異なる場合には、ＭＯＳトランジスタ（Ｔ５）２０７は導通状態となる。
【００２０】
またＭＯＳトランジスタ（Ｔ６）２０８はマスク・セル１０内に格納されているマスク情報が“１”のときには非導通状態（開放状態）であり、“０”のときに導通状態となる。
【００２１】
一致線７は、不図示の抵抗により高電位にプル・アップされているか、もしくは、検索動作を開始する前に、高電位にプリチャージされる。
【００２２】
これにより、複数の連想メモリ・セル１２が一致線７にそれぞれＭＯＳトランジスタ（Ｔ６）２０８を介して接続されているとき、一つの連想メモリ・セル１２でもロウ・レベルを出力していると、一致線７の電位がロウ・レベルとなるようなワイアードＡＮＤ接続となる。
【００２３】
ＭＯＳトランジスタ（Ｔ５）２０７、及びＭＯＳトランジスタ（Ｔ６）２０８がともに導通状態のときに一致線７は低電位電源電位となり、連想メモリ・セル１２は、一致線７に無効状態“０”を出力し、それ以外の時には、一致線７を開放状態とする。
【００２４】
すなわち、マスク情報が“０”の場合には、一致線７を必ず開放状態とし、マスク情報が“１”の場合にはビット線６ａ、６ｂ上の検索データ１０５とデータ・セル９に格納されている記憶データとが互いに一致するときに開放状態とし、ビット線６ａ、６ｂ上の検索データ１０５とデータ・セル９に格納されている記憶データとが異なる場合には無効状態“０”を出力する。
【００２５】
最短マスク線４は、図８に示すように、抵抗１６により高電位電源Ｖｄｄにプル・アップされ、検索動作前には、有効状態“１”になっている。
【００２６】
論理ゲート１３は、最短マスク線４と低電位電源との間に直列に挿入されたＭＯＳトランジスタ（Ｔ９）２１３と、ＭＯＳトランジスタ（Ｔ１０）２１４で構成されている。
【００２７】
ＭＯＳトランジスタ（Ｔ９）２１３は、ゲートが一致線７に接続されており、一致線７が有効状態“１”のときに導通状態となり、無効状態“０”のときには非導通状態（開放状態）となる。またＭＯＳトランジスタ（Ｔ１０）２１４は、そのゲートがマスク・セル１０内部の反転論理ゲートＧ３（２０９）の出力端に接続されており、反転論理ゲートＧ３（２０９）の出力端がハイ・レベルの場合に導通状態となり、ロウ・レベルの場合には非導通状態（開放状態）となる。つまり、マスク・セル１０に格納されているマスク情報が無効状態“０”のときに導通状態となり、有効状態“１”のときには開放状態となる。
【００２８】
これにより論理ゲート１３は、一致線７が有効状態“１”であり、かつ、マスク・セル１０に格納されたマスク情報が無効状態“０”のときに、最短マスク線４の電位を低電位電源電位とし、最短マスク線４を無効状態“０”を出力し、それ以外の場合には開放状態にする。
【００２９】
次に、図９を参照して、マスク比較器１８とマスク一致線１９について説明する。
【００３０】
マスク一致線１９は、不図示の抵抗により高電位にプル・アップされているか、または、検索動作を開始する前に高電位にプリチャージされる。
【００３１】
マスク比較器１８は、ＭＯＳトランジスタ（Ｔ１１）２１５、ＭＯＳトランジスタ（Ｔ１２）２１６、ＭＯＳトランジスタ（Ｔ１３）２１７により構成される。
【００３２】
ＭＯＳトランジスタ（Ｔ１１）２１５とＭＯＳトランジスタ（Ｔ１２）２１６はビット線６ａ、６ｂの間に直列に挿入され、ＭＯＳトランジスタ（Ｔ１１）２１５は、そのゲートがマスク・セル１０内の反転論理ゲート（Ｇ３）２０９の出力端に接続され、反転論理ゲート（Ｇ３）２０９の出力端がハイ・レベルのときに導通状態となり、ＭＯＳトランジスタ（Ｔ１２）２１６は、そのゲートがマスク・セル１０内の反転論理ゲート（Ｇ４）２１０の出力端に接続されており、反転論理ゲート（Ｇ４）２１０の出力端がハイ・レベルのときに導通状態となる。
【００３３】
ＭＯＳトランジスタ（Ｔ１３）２１７は、低電位電源と、マスク一致線１２との間に挿入されており、そのゲートがＭＯＳトランジスタ（Ｔ１１）２１５とＭＯＳトランジスタ（Ｔ１２）２１６の接続点に接続され、ＭＯＳトランジスタ（Ｔ１３）２１７は、該接続点の電位がハイ・レベルの時に導通状態となる。
【００３４】
ビット線６ａと反転論理ゲート（Ｇ３）２０９の出力端がともにハイ・レベル、またはビット線６ｂと反転論理ゲート（Ｇ４）２１０の出力端がともにハイ・レベルのときに、ＭＯＳトランジスタ（Ｔ１１）２１５とＭＯＳトランジスタ（Ｔ１２）２１６の接続点はハイ・レベルとなり、ＭＯＳトランジスタ（Ｔ１３）２１７は導通状態になり、その他の場合は非導通状態（開放状態）となる。
【００３５】
従って、マスク・セル１０に格納されているマスク情報と、ビット線６ａ、６ｂ上の検索データ１０５が異なる場合には、ＭＯＳトランジスタ（Ｔ５）２０７は導通状態になり、マスク一致線１９に無効状態“０”を出力し、一致する場合には一致線１０９を開放状態（高電位）にする。
【００３６】
これにより、複数の連想メモリ・セル１２がマスク一致線１９にＭＯＳトランジスタ（Ｔ１３）２１７を介して接続されているとき、一つの連想メモリ・セルでもロウ・レベルを出力していると、マスク一致線１９はロウ・レベルとなり、これ以外の場合はハイ・レベルとなる、ワイアードＡＮＤ接続を構成している。
【００３７】
上記の構成により、図８に示した連想メモリ・セル１２の機能は上記構成により実現される。
【００３８】
再び図８を参照して、連想メモリ１０全体の動作についてその概略を説明する。
【００３９】
ｎビット２入力１出力セレクタ１７は、ビット線６−１〜６−ｎに出力するデータを、制御信号２３の状態により、検索データ１０５−１〜１０５−ｎとラッチ出力線２２−１〜２２−ｎの一方から選択する。各の連想メモリ・ワード８は、該連想メモリワードに対応するマスク一致線１９をそれぞれ出力する。例えば一番目の連想メモリ・ワード８−１はマスク一致線１９−１を出力する。
【００４０】
ここで、各連想メモリ・ワード８の中のｎ個の連想メモリ・セル１２はすべて、対応する１本のマスク一致線１９とワイアード論理（ＡＮＤ）接続されている。
【００４１】
ｎビット・ラッチ２１は、ラッチ制御信号２４が有効状態の時に、最短マスク線４−１〜４−ｎの状態を内部に格納し、格納した状態をラッチ出力線２２−１〜２２−ｎに出力する。
【００４２】
ラッチ２０−１〜２０−ｍは、同一の連想メモリ・ワード８−１〜８−ｍの中の一致線７−１〜７−ｍの状態を、ラッチ制御信号が有効状態の時に内部に格納すし、格納した状態を出力する。ラッチ２０−１〜２０−ｍの出力は同一の連想メモリ・ワード８−１〜８−ｍのマスク一致線１９とワイアード論理接続されている。
【００４３】
マスク一致線１９−１〜１９−ｍは、検索動作の終了時に、検索データ１０５と一致した記憶データの中で、マスク情報により検索対象から除外されたビット数が最も少ない記憶データに対応するものだけが有効状態となり、それ以外は無効状態となる。
【００４４】
なお、ここでは、マスク情報の有効状態を“１”、無効状態を“０”とし、最短マスク線４−１〜４−８の有効状態を“１”、無効状態を“０”とする。また一致線７−１〜７−５の有効状態を“１”、無効状態を“０”とする。そして、マスク一致線１９−１〜１９−ｍの有効状態を“１”、無効状態を“０”とする。
【００４５】
マスク一致線１９−１〜１９−ｍは検索動作開始前に、不図示の抵抗により高電位電源Ｖｄｄ側にプル・アップされているか、もしくはハイ・レベルにプリ・チャージされ、有効状態“１”になっているものとする。
【００４６】
ラッチ２０−１〜２０−ｍは対応するマスク一致線１９−１〜１９−ｍに対して、格納されたデータが無効状態“０”の場合には“０”を出力し、格納されたデータが有効状態“１”の場合には対応するマスク一致線１９−１〜１９−ｍを開放状態とする。
【００４７】
また、各連想メモリ・セルの中のマスク比較器１８−１−１〜１８−ｍ−ｎは、同一の連想メモリ・セル１８−１−１〜１８−ｍ−ｎの中にあるマスク・セル１０−１−１〜１０−ｍ−ｎと、ビット線６−１〜６−ｎおよびマスク一致線１９−１〜１９−ｍに対応する。
【００４８】
マスク比較器１８は、対応するマスク・セル１０が格納するマスク情報の状態と、対応するビット線６上の最短マスク情報とを比較し、両者が一致している場合、対応するマスク一致線１９を開放状態にし、不一致の場合、対応するマスク一致線１９に無効状態“０”を出力する。
【００４９】
従って、連想メモリ・ワード８の中において、ｎ個の連想メモリ・セル１２のマスク比較器１８のＭＯＳトランジスタ（Ｔ１３）２１７が非導通状態とされており、ラッチ２０がすべてマスク一致線１９を開放状態にしているときに、マスク一致線は有効状態“１”となり、それ以外の場合には無効状態“０”となるワイアードＡＮＤ論理接続を構成している。
【００５０】
すなわち、連想メモリ・ワード８が格納しているマスク情報と、ビット線６−１〜６−ｎの値が完全に一致し、かつ、ラッチ２０に格納されている一致線７の状態が有効状態“１”の場合に限り、マスク一致線１９は有効状態“１”となり、それ以外の場合は無効状態“０”となる。
【００５１】
もちろん、このような動作をするように、通常の論理ゲートを用いて構成してもよい。
【００５２】
図１０は、図８に示した従来の連想メモリの動作を説明するための図である。図１０を参照して、連想メモリ１０の動作を説明する。マスク情報の有効状態を“１”、無効状態を“０”とする。また、最短マスク線４−１〜４−８の有効状態を“１”、無効状態を“０”とし、一致線７−１〜７−５、マスク一致線１９−１〜１９−５の有効状態を“１”、無効状態を“０”とする。また連想メモリ１０を８ビット５語の構成とする。
【００５３】
連想メモリ・ワード８−１には、（１．＊．＊．＊）を実現するため２進数で、記憶データには（０１．００．００．００）を、マスク情報として（００．１１．１１．１１）が格納されている。
【００５４】
同様に、連想メモリ・ワード８−２には（２．＊．＊．＊）を、連想メモリ・ワード８−３には（１．２．２．＊）を、連想メモリ・ワード８−４には（１．２．＊．＊）を、連想メモリ・ワード８−５には（２．３．３．＊）が格納されている。
【００５５】
以降、検索データ１０５として（１．２．２．３）を入力して検索動作を行った場合の動作説明をする。
【００５６】
まず、選択信号２３により８ビット２入力１出力セレクタ１７は、検索データ１０５を選択し、ビット線６−１〜６−８に出力する。
【００５７】
これにより、連想メモリ１０の連想メモリ・ワード８−３に格納されている４進表現の（１．２．２．＊）と、連想メモリ・ワード８−４に格納されている４進表現の（１．２．＊．＊）がビット線上のデータと一致する。
【００５８】
従って、一致線７−３と７−４の２本が有効状態“１”となり、残りの一致線７−１、７−２、および７−５は無効状態“０”となる。
【００５９】
ここで、最短マスク線４−１からは、メモリ・ワード７−３内の最短マスク線４−１に対応するマスク情報“０”と、メモリ・ワード７−４内の最短マスク線４−１に対応するマスク情報“０”の論理積“０”が出力される。
【００６０】
最短マスク線４−２からは、メモリ・ワード７−３内の最短マスク線４−２に対応するマスク情報“０”と、メモリ・ワード７−４内の最短マスク線４−２に対応するマスク情報“０”の論理積“０”が出力される。
【００６１】
以降、同様に、最短マスク線４−３からは“０”と“０”の論理積“０”が、最短マスク線４−４からは“０”と“０”の論理積“０”が、最短マスク線４−５からは“０”と“１”の論理積“０”が、最短マスク線４−６からは“０”と“１”の論理積“０”が、最短マスク線４−７からは“１”と“１”の論理積“１”が、最短マスク線４−８からは“１”と“１”の論理積“１”が、それぞれ出力される。
【００６２】
従って、最短マスク線４−１〜４−８には、２進表現で“００００００１１”が出力される。
【００６３】
この状態でラッチ制御信号２４が有効状態になり、ラッチ２０−１〜２０−５は、対応する一致線７−１〜７−５の状態を内部に格納し、ｎビット・ラッチ２１は最短マスク線４−１〜４−８の状態を内部に格納する。従って、ラッチ２０−１には“０”が、ラッチ２０−２には“０”が、ラッチ２０−３には“１”が、ラッチ２０−４には“１”が、ラッチ２０−５には“０”が、それぞれ格納され、ｎビット・ラッチ２１には２進表現で“００００００１１”が格納され、ｎビット・ラッチ２１は、格納した状態“００００００１１”をラッチ出力線２２に出力する。
【００６４】
次に、選択信号２３により、８ビット２入力１出力セレクタ１７は、ラッチ出力線２２を選択し、その情報“００００００１１”を対応するビット線６−１〜６−８に出力した後、連想メモリ１０は、２回目の検索動作を開始する。
【００６５】
２回目の検索動作では、マスク一致線１９−１〜１９−８の状態を利用し、一致線７−１〜７−８の状態は無視される。
【００６６】
マスク一致線１９−１〜１９−８は、２回目の検索動作開始前に、ハイ・レベルにプリ・チャージされるか、図示されない抵抗によりハイ・レベルにプル・アップされて、有効状態“１”になっている。
【００６７】
ビット線６−１〜６−８の状態が“００００００１１”に対して、連想メモリ・ワード８−３と８−５が格納するマスク情報が完全に一致し、対応するマスク一致線１９−３、１９−５を開放状態にする。
【００６８】
他の連想メモリ・ワード８−１、８−２および８−４が格納するマスク情報は一致しないので、対応するマスク一致線１９−１、１９−２、および１９−４に無効状態“０”を出力する。
【００６９】
また、ラッチ２０−１は格納した状態“０”を対応するマスク一致線１９−１に出力し、ラッチ２０−２は格納した状態“０”を対応するマスク一致線１９−２に出力し、ラッチ２０−３は格納した状態が“１”であるため対応するマスク一致線１９−３を開放状態にし、ラッチ２０−４は格納した状態が“１”であるため対応するマスク一致線１９−４を開放状態にし、ラッチ２０−５は格納した状態“０”を対応するマスク一致線１９−５に出力する。
【００７０】
従って、マスク一致線１９−１は、連想メモリ・ワード８−１の一致線７−１が“０”を出力し、ラッチ２０−１も“０”を出力しているので無効状態“０”となる。
【００７１】
マスク一致線１９−２は、連想メモリ・ワード８−２の一致線７−２が“０”を出力しラッチ２０−２も“０”を出力しているので無効状態“０”となる。
【００７２】
マスク一致線１９−３は、連想メモリ・ワード８−３の一致線７−３が開放状態でありラッチ２０−３も開放状態であるので、有効状態“１”を保持する。
【００７３】
マスク一致線１９−４は、ラッチ２０−４が開放状態にしているが、連想メモリ・ワード８−４の一致線７−４が“０”を出力しているので、無効状態“０”となる。
【００７４】
マスク一致線１９−５は、連想メモリ・ワード８−５が開放状態にしているが、ラッチ２０−５が“０”を出力しているので、マスク一致線１９−５は無効状態“０”となる。
【００７５】
これにより、１回目の検索動作で、予め格納されている記憶データがマスク情報を考慮して、検索データ１０５と一致し、かつ２回目の検索動作で、予め格納されているマスク情報が１回目の検索動作の結果得られた最短マスク線４−１〜４−８の状態と一致するような連想メモリ・ワード８−１〜８−５に対応するマスク一致線１９−１〜１９−５のみが、２回目の検索動作終了時に有効状態“１”になることがわかる。
【００７６】
この２回目の検索動作終了時に有効状態となるマスク一致線に対応するワードは、検索データとマスク情報を考慮して一致するワード（複数あり得る）の中で、最もマスクの無効状態のビット数が短い、即ち、検索データと最も長い部分で一致するワードである。
【００７７】
図１１は、上述した１回目の検索動作と２回目の検索動作を示すタイミングチャートであり、［１］〜［４］はクロックサイクルを示している。
【００７８】
［１］  全てのビット線６、一致線７およびマスク一致線１９をハイ（“１”）にプリチャージする。
【００７９】
［２］  クロックの立ち上がりで各ビット線に検索データの対応するビット情報が出力される。このビット情報と各連想メモリ・ワード内の対応する記憶データのビット情報が一致するか、または対応するビットのマスク情報が“１”ならばそのメモリ・ワードの一致線は有効状態“１”になり、それ以外の連想メモリ・ワードの一致線は無効状態“０”になる。また、各最短マスク線には有効状態にある連想メモリ・ワードの対応するマスクビット情報の論理積が出力される。ここで、ラッチ制御信号２４が活性化されて各連想メモリ・ワードの一致線の値がラッチ２０に格納される。また、各最短マスク線のビット情報がｎビット・ラッチ２１に格納されるとともに対応するラッチ出力線２２に出力される。
【００８０】
［３］  次に、全てのビット線、一致線７およびマスク一致線１９をハイにプリチャージする。なお、マスク一致線１９に関しては、ラッチ２０に“１”を格納している連想メモリ・ワードのマスク一致線のみハイにプリチャージしてもよい。
【００８１】
［４］  クロックの立ち上がりで選択信号２３により、各ラッチ出力線２２上のビット情報が対応するビット線６に出力される。このビット情報と連想メモリ・ワード中のマスク情報が一致し、且つラッチ２０が“１”を記憶している連想メモリ・ワードのマスク一致線１９のみが有効状態“１”を出力する。
【００８２】
上述のように、従来の最短マスク出力機能付連想メモリを使用すれば、２クロックで、検索データとマスク情報を考慮して一致するワード（複数あり得る）の中で、最もマスクの無効状態のビット数が短い、即ち、検索データと最も長い部分で一致するワードのマスク一致線が有効状態“１”になり、このワードを選択するこができる。
【００８３】
【発明が解決しようとする課題】
しかしながら、上述した最短マスク出力機能付き連想メモリにおいては、上述の１回目の検索動作と２回目の検索動作において、検索データを連想メモリセル・ワードのデータセルに対応する比較器と、マスクセルに対応するマスク比較器として、ビット線を供給するビット線６−１〜６−ｎを共有しているため、連続した検索を行った際、パイプライン検索ができない。すなわち、先の検索がその２回目の検索動作を終えた後にしか、次の検索を開始することができない。
【００８４】
このため、検索性能において、一定時間内に検索が出来る回数が少ないという問題があった。
【００８５】
したがって本発明は、上記問題点に鑑みてなされたものであって、その目的は、連続した検索を行う際に、先の検索の２回目の検索動作を実行するのと同時に、次の検索の１回目の検索動作を実行することが出来るようにし、一定時間に検索が出来る回数を向上させる連想メモリ装置を提供することにある。
【００８６】
【課題を解決するための手段】
前記目的を達成する本発明は、データ・セルと、マスク・セルと、前記データ・セルに対応する比較器と、前記マスク・セルに対応する比較器と、を備えた最短マスク出力機能付連想メモリにおいて、前記データ・セルに対応する前記比較器へ比較対象ビットを入力する第１のビット線と、前記マスク・セルに対応するマスク比較器へ比較対象ビットを入力する第２のビット線と、を備え、前記第１のビット線には、検索データの対応するビットを入力し、前記第２のビット線には、最短マスク線の対応するビット位置のビットを入力する。
【００８７】
【発明の実施の形態】
本発明の実施の形態について説明する。本発明の最短マスク出力機能付連想メモリは、データ・セルに対応する比較器へ比較対象ビットを入力するビット線と、マスク・セルに対応するマスク比較器へ比較対象ビットを入力するビット線を分離し、データ・セルに対応する比較器へ比較対象ビットを入力するビット線には、検索データの対応するビットを入力する手段を有し、データ・セルに対応する比較器へ比較対象ビットを入力するビット線には、最短マスク線の対応するビット位置のビットを入力する手段を有する。
【００８８】
本発明の最短マスク出力機能付連想メモリにおいては、検索データに関する検索を２回の検索動作によって実行する。
【００８９】
上記したように従来の最短マスク出力機能は連想メモリでは、１回目の検索動作に用いる、データ・セルに対応する比較器へ比較対象ビットを入力するビット線と、２回目の検索動作に用いる、マスク・セルに対応するマスク比較器へ比較対象ビットを入力するビット線を同一のビット線を用いていたので、連続して検索データを検索する際に、先行している検索の２回目の検索動作が終了するまで、次の検索データの１回目の検索を開始することができなかった。
【００９０】
本発明によれば、データ・セルに対応する比較器へ比較対象ビットを入力するビット線と、マスク・セルに対応するマスク比較器へ比較対象ビットを入力するビット線が分離されているため、先行して検索が行われている検索データの、２回目の検索動作時に、同時に、次の検索データの１回目の検索動作が可能になる。そのため、検索がパイプライン的に行われ、一定の時間内に検索出来る回数を増加させることができる。
【００９１】
本発明の連想メモリは、その好ましい一実施の形態において、図１及び図２を参照すると、ｎビットｍ語の連想メモリ・ワード（８）と、ｎビットラッチ（２１）とを有し、各連想メモリ・ワード（８）は、ｎ個の連想メモリ・セル（１２）と、一致線の値をラッチする１個のラッチ（２０）とを備えている。各連想メモリ・セル（１２）は、外部からビット線（６）を介して入力される記憶データの対応するビット情報を格納するデータ・セル（９）と、データ・セルに記憶されたビット情報と外部から入力される検索データの対応するビット情報（１０５）とを比較する比較器（１１）と、外部からビット線（６）を介して入力されるマスク情報の対応するビット情報を格納するマスク・セル（１０）と、マスク・セルに記憶されたビット情報とｎビットラッチ（２１）から出力された最短マスク情報の対応するビット情報（２２）とを比較するマスク比較器（１８）と、論理ゲート（１３）とを備えている。ラッチ（２０）の出力は、各連想メモリ・セル（１２）のマスク比較器（１８）の出力とともにマスク一致線（１９）にワイアード論理接続されている。
【００９２】
１つの検索データに対する検索は２回の検索動作で行われる。１回目の検索動作では、検索データ（１０５）は、ビット線を使って各連想メモリワードへ同時に入力され、各連想メモリ・ワードでは、たとえば、連想メモリ・ワードに含まれるデータ・セルは、同一の連想メモリ・ワードに含まれるマスク・セルの値をマスクとして、ビット線の値と比較される。一致した連想メモリ・ワードでは、対応する一致線が有効化され、最短マスク線（４）にマスク・セルの値が出力される。
【００９３】
一致しないエントリでは、一致線は有効化されず、最短マスク線には“０”が出力され、最短マスク線（４）上でワイアードＡＮＤがとられて、結果がｎビット・ラッチ（２１）に格納される。また、各一致線（７）の状態も対応するラッチ（２０）に格納される。
【００９４】
２回目の検索動作では、ｎビットラッチ（２１）のデータがラッチ出力線（２１）を使って、各連想メモリワードのマスク比較器へと入力され、各連想メモリ・ワードではラッチ出力線（２２）の値と、マスク・セル（１０）の値を比較し、一致したワードでは、マスク一致線（１９）が有効化され、検索結果を得る。
【００９５】
この２回の検索動作は、データ・セル（９）に対応する比較器（１１）へ比較対象ビットを入力する線と、マスク・セル（１０）に対応するマスク比較器（１８）へ比較対象ビットを入力する線が、それぞれ、ビット線（６）とラッチ出力線（２２）とに分離されているため、連続した検索を行う際、先行した検索の２回目の検索動作と、次の検索の１回目の検索動作を同時に実行することができ、一定時間に検索が出来る回数を２倍に向上させることができる。
【００９６】
【実施例】
上記した本発明の実施の形態について更に詳細に説明すべく、本発明の実施例について図面を参照して説明する。
【００９７】
図１は、本発明の一実施例の構成を示すブロック図である。図１を参照すると、連想メモリ１は、ｎビットｍ語の連想メモリ・ワード８−１〜８−ｍと、ｎビットラッチ２１とを備え、各連想メモリ・ワード８−ｊ（但し、１≦ｊ≦ｍ）はｎ個の連想メモリ・セル１２−ｊ−１〜１２−ｊ−ｎと１個のラッチ２０−ｊとを備えている。
【００９８】
各連想メモリ・セル１２−ｊ−ｋ（但し、１≦ｋ≦ｎ、１≦ｊ≦ｍ）は、外部からビット線６−ｋ（但し、１≦ｋ≦ｎ）を介して入力される記憶データの対応するビット情報を格納するデータ・セル９−ｊ−ｋと、データ・セル９−ｊ−ｋに記憶されたビット情報と外部から入力される検索データの対応するビット情報１０５−ｋとを比較する比較器１１−ｊ−ｋと、外部からビット線６−ｋを介して入力されるマスク情報の対応するビット情報を格納するマスク・セル１０−ｊ−ｋと、マスク・セルに記憶されたビット情報とｎビットラッチ２１から出力された最短マスク情報の対応するビット情報（ラッチ出力）２２−ｋとを比較するマスク比較器１８−ｊ−ｋと、論理ゲート１３−ｊ−ｋとを備えている。
【００９９】
図２は、本発明の一実施例における連想メモリ・セルの構成を示す図である。図２において、２本のラッチ出力線２２ａ、２２ｂは、図１に示されている各ラッチ線に対応するものであるが、図１においては２２−ｉで代表して表している。
【０１００】
図８に示した従来の連想メモリ・セルと、図２とを比較すれば分かるように、本発明の一実施例の連想メモリ・セルは、マスク比較器１８のＭＯＳトランジスタ（Ｔ１１）２１５と、ＭＯＳトランジスタ（Ｔ１２）２１６が、それぞれビット線６ａ、６ｂではなく、それぞれラッチ出力線２１ａ、  ２１ｂに接続されている点が、図８に示した従来の連想メモリ・セルと相違している。以下では、本発明の一実施例のの連想メモリ・セルについて、従来の連想メモリ・セルと相違点について説明し、データセル９、比較器１１等の同一部分の説明は適宜省略する。
【０１０１】
マスク比較器１８は、ＭＯＳトランジスタ（Ｔ１１）２１５、ＭＯＳトランジスタ（Ｔ１２）２１６、ＭＯＳトランジスタ（Ｔ１３）２１７から構成されている。ＭＯＳトランジスタ（Ｔ１１）２１５とＭＯＳトランジスタ（Ｔ１２）２１６はラッチ出力線２１ａ、２１ｂの間に直列に挿入されており、ＭＯＳトランジスタ（Ｔ１１）２１５は、そのゲートがマスク・セル１０内の反転論理ゲート（Ｇ３）２０９の出力端に接続されており、反転論理ゲート（Ｇ３）２０９の出力端がハイ・レベルのときに導通状態となる。ＭＯＳトランジスタ（Ｔ１２）２１６は、そのゲートがマスク・セル１０内の反転論理ゲート（Ｇ４）２１０の出力端に接続されており、反転論理ゲート（Ｇ４）２１０の出力端がハイ・レベルのときに導通状態となる。
【０１０２】
ＭＯＳトランジスタ（Ｔ１３）２１７は、低電位電源と、マスク一致線１２との間に挿入され、ゲートが、ＭＯＳトランジスタ（Ｔ１１）２１５とＭＯＳトランジスタ（Ｔ１２）２１６の接続点に接続され、該接続点の電位がハイ・レベルの時に導通状態となる。
【０１０３】
ラッチ出力線２１ａと反転論理ゲート（Ｇ３）２０９の出力端がともにハイ・レベル、またはビット線２１ｂと反転論理ゲート（Ｇ４）２１０の出力端がともにハイ・レベルのときに、ＭＯＳトランジスタ（Ｔ１１）２１５とＭＯＳトランジスタ（Ｔ１２）２１６の接続点はハイ・レベルとなり、ＭＯＳトランジスタ（Ｔ１３）２１７が導通状態になり、その他の場合は開放状態となる。
【０１０４】
従って、マスク・セル１０に格納されているマスク情報と、ラッチ出力線２１ａ、２１ｂ上の最短マスク情報が互いに異なる場合に、ＭＯＳトランジスタ（Ｔ５）２０７は導通状態になり、マスク一致線１９に無効状態“０”を出力し、一致する場合には、一致線１０９を開放状態にする。
【０１０５】
これにより、複数の連想メモリ・セル１２がマスク一致線１９にＭＯＳトランジスタ（Ｔ１３）２１７を介して接続されているとき、一つの連想メモリ・セルでもロウ・レベルを出力していると、マスク一致線１９はロウ・レベルとなり、それ以外の場合にはハイ・レベルにするワイアードＡＮＤ接続を構成している。
【０１０６】
以上が、本発明の一実施例における連想メモリ・セル１２の構成である。
【０１０７】
再び図１を参照して、連想メモリ１の全体の動作について説明する。
【０１０８】
ビット線６−１〜６−ｎには、検索データ１０５−１〜１０５−ｎの対応するビットの値が出力される。それぞれの連想メモリ・ワード８は、対応する１本のマスク一致線１９を出力する。たとえば一番目の連想メモリ・ワード８−１はマスク一致線１９−１を出力する。ここで、各連想メモリ・ワード８の中のｎ個の連想メモリ・セル１２はすべて、対応する１本のマスク一致線１９とワイアード論理接続されている。
【０１０９】
ｎビット・ラッチ２１は、ラッチ制御信号２４が有効状態の時に、最短マスク線４−１〜４−ｎの状態を内部に格納する。また、格納した状態をラッチ出力線２２−１〜２２−ｎに出力する。
【０１１０】
ラッチ２０−１〜２０−ｍは、同一の連想メモリ・ワード８−１〜８−ｍの中の一致線７−１〜７−ｍの状態を、ラッチ制御信号２４線が有効状態の時に内部に格納して出力する。また、ラッチ２０−１〜２０−ｍの出力は、同一の連想メモリ・ワードの中にあるマスク一致線１９とワイアード論理接続されている。
【０１１１】
マスク一致線１９−１〜１９−ｍは、検索動作の終了時に、検索データ１０５と一致した記憶データの中で、マスク情報により検索対象から除外されたビット数が最も少ない記憶データに対応するものだけが有効状態となり、それ以外は無効状態となる。
【０１１２】
なお、本実施例では、マスク情報の有効状態を“１”、無効状態を“０”とし、最短マスク線４−１〜４−８の有効状態を“１”、無効状態を“０”とする。一致線７−１〜７−５の有効状態を“１”、無効状態を“０”とする。また、マスク一致線１９−１〜１９−ｍの有効状態を“１”、無効状態を“０”とする。
【０１１３】
マスク一致線１９−１〜１９−ｍは検索動作開始前に、不図示の抵抗によりプル・アップされているか、ハイ・レベルにプリ・チャージされることにより、有効状態“１”になっているものとする。
【０１１４】
ラッチ２０−１〜２０−ｍは対応するマスク一致線１９−１〜１９−ｍに対して、格納されたデータが無効状態“０”の場合には“０”を出力し、格納されたデータが有効状態“１”の場合には対応するマスク一致線１９−１〜１９−ｍを開放状態とする。
【０１１５】
また、各連想メモリ・セルの中のマスク比較器１８−１−１〜１８−ｍ−ｎは、同一の連想メモリ・セル１８−１−１〜１８−ｍ−ｎの中にあるマスク・セル１０−１−１〜１０−ｍ−ｎと、ラッチ出力線２１−１〜２１−ｎおよびマスク一致線１９−１〜１９−ｍに対応する。
【０１１６】
マスク比較器１８は、対応するマスク・セル１０が格納するマスク情報の状態と対応するラッチ出力線２１上の最短マスク情報を比較し、これらが一致している場合、対応するマスク一致線１９を開放状態にし、不一致の場合、対応するマスク一致線１９に無効状態“０”を出力する。
【０１１７】
従って、連想メモリ・ワード８の中のｎ個の連想メモリ・セル１２と、１個のラッチ２０がすべてマスク一致線を開放状態にしているときに、マスク一致線１９は有効状態“１”となり、それ以外の場合には無効状態“０”となるワイアードＡＮＤ論理接続を構成している。
【０１１８】
すなわち、連想メモリ・ワード８が格納しているマスク情報とビット線６−１〜６−ｎが完全に一致し、かつ、ラッチ２０に格納されている一致線７の状態が有効状態“１”の場合に限り、マスク一致線１９は有効状態“１”となり、それ以外の場合は無効状態“０”となる。もちろん、このような動作をするように通常の論理ゲートを用いて構成してもよい。
【０１１９】
図３乃至図５は、本発明の一実施例の動作を説明するための図である。
【０１２０】
マスク情報の有効状態を“１”、無効状態を“０”とする。また、最短マスク線４−１〜４−８の有効状態を“１”、無効状態を“０”とし、一致線７−１〜７−５、マスク一致線１９−１〜１９−５の有効状態を“１”、無効状態を“０”とする。連想メモリ１を８ビット５語の構成と仮定する。
【０１２１】
図３乃至図５に示すように、連想メモリ・ワード８−１には（１．＊．＊．＊）を実現するため２進数で、記憶データには（０１．００．００．００）を、マスク情報として（００．１１．１１．１１）が格納されている。同様に連想メモリ・ワード８−２には（２．＊．＊．＊）が、連想メモリ・ワード８−３には（１．２．２．＊）が、連想メモリ・ワード８−４には（１．２．＊．＊）が、連想メモリ・ワード８−５には（２．３．３．＊）が格納されている。
【０１２２】
以降、検索データ１０５として（１．２．２．３）と、 （１．０．２．３）を連続して入力し検索動作を行った場合の動作について説明する。図３乃至図５は、連想メモリ１の状態を順に示したものである。
【０１２３】
まず、図３に示すように、検索データ１０５を（１．２．２．３）とし、検索データ１０５の対応する各ビットが、ビット線６−１〜６−８に出力される。これにより、連想メモリ１の連想メモリ・ワード８−１に格納されている４進表現の（１．＊．＊．＊）と、連想メモリ・ワード８−３に格納されている４進表現の（１．２．２．＊）と、連想メモリ・ワード８−４に格納されている４進表現の（１．２．＊．＊）がビット線上のデータと一致する。従って、一致線７−１、７−３と７−４の３本が有効状態“１”となり、残りの一致線７−２および７−５は無効状態“０”となる。
【０１２４】
ここで、最短マスク線４−１からは、メモリ・ワード７−１内の最短マスク線４−１に対応するマスク情報”０”と、メモリ・ワード７−３内の最短マスク線４−１に対応するマスク情報”０”と、メモリワード７−４内の最短マスク線４−１に対応するマスク情報”０”の論理積”０”が出力される。
【０１２５】
最短マスク線４−２からは、メモリ・ワード７−１内の最短マスク線４−２に対応するマスク情報”０”と、メモリ・ワード７−３内の最短マスク線４−２に対応するマスク情報”０”と、メモリワード７−４内の最短マスク線４−２に対応するマスク情報”０”の論理積”０”が出力される。
【０１２６】
以下同様にして、最短マスク線４−３からは“０”と“０”の論理積“０”が、最短マスク線４−４からは“０”と“０”の論理積“０”が、最短マスク線４−５からは“０”と“１”の論理積“０”が、最短マスク線４−６からは“０”と“１”の論理積“０”が、最短マスク線４−７からは“１”と“１”の論理積“１”が、最短マスク線４−８からは“１”と“１”の論理積“１”が、それぞれ出力される。
【０１２７】
従って、最短マスク線４−１〜４−８には、２進表現で“００００００１１”が出力される。
【０１２８】
この状態で、ラッチ制御信号２４が有効状態になり、ラッチ２０−１〜２０−５は対応する一致線７−１〜７−５の状態を内部に格納し、ｎビット・ラッチ２１は最短マスク線４−１〜４−８の状態を内部に格納する。従って、ラッチ２０−１には“１”が、ラッチ２０−２には“０”が、ラッチ２０−３には“１”が、ラッチ２０−４には“１”が、ラッチ２０−５には“０”が、それぞれ格納され、ｎビット・ラッチ２１には２進表現で“００００００１１”が格納される。また、ｎビット・ラッチ２１は、格納した状態“００００００１１”をラッチ出力線２２に出力する。
【０１２９】
次に検索データ（１．２．２．３）に関する２回目の検索動作と、連続して次に検索する検索データ（１．０．２．３）に関する１回目の検索動作が開始される（図４参照）。
【０１３０】
検索データ（１．５．３．３）に関する１回目の検索動作については、上述した（１．２．２．３）に関する１回目の検索動作と同様の処理が行われ、処理の終了時には、ラッチ２０−１には“１”が、ラッチ２０−２には“０”が、ラッチ２０−３には“０”が、ラッチ２０−４には“０”が、ラッチ２０−５には“０”がそれぞれ格納され、ｎビット・ラッチ２１には、ラッチ制御信号２４に基づき、２進表現で“００１１１１１１”が格納される。また、ｎビット・ラッチ２１は、格納した状態“００１１１１１１”をラッチ出力線２２に出力する。
【０１３１】
上記の（１．０．２．３）に関する１回目の検索動作と同時に実行される、(１．２．２．３）に関する２回目の検索動作について説明する。
【０１３２】
２回目の検索動作では、マスク一致線１９−１〜１９−８の状態を利用し、一致線７−１〜７−８の状態は無視される。
【０１３３】
マスク一致線１９−１〜１９−８は（１．２．２．３）に関する２回目の検索動作開始前に、ハイ・レベルにプリ・チャージされるか、不図示の抵抗によりハイ・レベルにプル・アップされて有効状態“１”になっている。
【０１３４】
動作開始時には、ラッチ出力線２２−１〜２２−８の状態は、（１．０．２．３）に関する１回目の検索動作の結果を反映していず、（１．２．２．３）に関する１回目の検索動作の結果である値“００００００１１”を保持している。
【０１３５】
このラッチ出力線２２−１〜２２−８の値に対して、連想メモリ・ワード８−３と８−５が格納するマスク情報が完全に一致し、対応するマスク一致線１９−３、１９−５を開放状態にする。
【０１３６】
他の連想メモリ・ワード８−１、８−２および８−４が格納するマスク情報は一致しないので、対応するマスク一致線１９−１、１９−２、および１９−４に無効状態“０”を出力する。
【０１３７】
また、ラッチ２０−１〜２０−５は、（１．２．２．３）に関する１回目の検索動作の結果を保持しており、ラッチ２０−１は格納した状態“０”を対応するマスク一致線１９−１に出力し、ラッチ２０−２は格納した状態“０”を対応するマスク一致線１９−２に出力し、ラッチ２０−３は格納した状態が“１”であるため対応するマスク一致線１９−３を開放状態にし、ラッチ２０−４は格納した状態が“１”であるため、対応するマスク一致線１９−４を開放状態にし、ラッチ２０−５は格納した状態“０”を対応するマスク一致線１９−５に出力する。
【０１３８】
従って、マスク一致線１９−１は、連想メモリ・ワード８−１の一致線７−１が“０”を出力しラッチ２０−１も“０”を出力しているため、無効状態“０”になる。
【０１３９】
マスク一致線１９−２は、連想メモリ・ワード８−２の一致線７−２が“０”を出力し、ラッチ２０−２も“０”を出力しているため、無効状態“０”となる。
【０１４０】
マスク一致線１９−３は、連想メモリ・ワード８−３の一致線７−３が開放状態でありラッチ２０−３も開放状態であることから、有効状態“１”を保持する。
【０１４１】
マスク一致線１９−４は、ラッチ２０−４が開放状態にしているが、連想メモリ・ワード８−４の一致線７−４が“０”を出力しているので、無効状態“０”となる。
【０１４２】
マスク一致線１９−５は、連想メモリ・ワード８−５が開放状態にしているが、ラッチ２０−５が“０”を出力していることから、マスク一致線１９−５は無効状態“０”となる。
【０１４３】
これにより、１回目の検索動作で、予め格納されている記憶データがマスク情報を考慮して検索データ１０５と一致し、かつ２回目の検索動作で、予め格納されているマスク情報が１回目の検索動作の結果得られた最短マスク線４−１〜４−８の状態と一致するような連想メモリ・ワード８−１〜８−５に対応するマスク一致線１９−１〜１９−５のみが、２回目の検索動作終了時に有効状態“１”になることがわかる。
【０１４４】
以上で、（１．２．２．３）に関する１、２回目の検索動作が終了し、連想メモリワード３が検索結果として選択されることになる。
【０１４５】
次に、検索データ（１．０．２．３）に関する２回目の検索動作が開始される（図５参照）。
【０１４６】
この動作も、（１．２．２．３）に関する上記した２回目の検索動作と同様で、最終的には、マスク一致線１９−１〜１９−５の中で、連想メモリワード１のマスク一致線１９−１のみが、有効状態”１”となり、連想メモリワード１が検索結果として選択されることになる。
【０１４７】
図６は、本発明の一実施例において、上記した連続した検索におけるそれぞれの１回目の検索動作の一例と２回目の検索動作を示すタイミングチャートであり、［１］〜［６］はクロックサイクルを表している。
【０１４８】
［１］  このサイクル後半で、全てのビット線、一致線およびマスク一致線をハイ（“１”）にプリチャージする。
【０１４９】
［２］  クロック立ち上がりで各ビット線に１番目の検索データの対応するビット情報が出力される。このビット情報と各連想メモリ・ワード内の対応する記憶データのビット情報が一致するか、または対応するビットのマスク情報が“１”ならばその連想メモリ・ワードの一致線７は有効状態“１”になり、それ以外の連想メモリ・ワードの一致線は無効状態“０”になる。また、各最短マスク線には有効状態にある連想メモリ・ワードの対応するマスクビット情報の論理積が出力される。ここで、ラッチ制御信号２４が活性化されて各メモリ・ワードの一致線７の値がラッチ２０に格納される。また、各最短マスク線のビット情報がｎビット・ラッチ２１に格納されるとともに対応するラッチ出力線２２に出力される。
【０１５０】
［３］  次に、全てのビット線、一致線７およびマスク一致線１９をハイにプリチャージする。なお、マスク一致１９線については、ラッチ２０に“１”を格納しているメモリ・ワードのマスク一致線１９のみハイにプリチャージしてもよい。
【０１５１】
［４］  クロックの立ち上がりでラッチ出力線２１上のビット情報と連想メモリ・ワード中のマスク情報が一致し、且つラッチ２０が“１”を記憶している連想メモリ・ワードのマスク一致線のみが有効状態“１”を出力する。
【０１５２】
また、［４］のクロックの立ち上がりで、２番目の検索データの対応するビット情報が出力される。このビット情報と各連想メモリ・ワード内の対応する記憶データのビット情報が一致するか、または対応するビットのマスク情報が“１”ならば、その連想メモリ・ワードの一致線７は有効状態“１”になり、それ以外の連想メモリ・ワードの一致線は無効状態“０”になる。
【０１５３】
また、各最短マスク線には有効状態にある連想メモリ・ワードの対応するマスクビット情報の論理積が出力される。ここで、ラッチ制御信号が活性化されて各連想メモリ・ワードの一致線の値がラッチ２０に格納される。また、各最短マスク線のビット情報がｎビット・ラッチ２１に格納されるとともに対応するラッチ出力線２２に出力される。
【０１５４】
［５］  次に、全てのビット線６、一致線７およびマスク一致線１７をハイレベルにプリチャージする。なお、マスク一致線に関しては、ラッチ２０に“１”を格納しているメモリ・ワードのマスク一致線のみハイにプリチャージしてもよい。
【０１５５】
［６］  クロックの立ち上がりでラッチ出力線２１上のビット情報とメモリ・ワード中のマスク情報が一致し、且つラッチ２０が“１”を記憶しているメモリ・ワードのマスク一致線のみが有効状態“１”を出力する。
【０１５６】
次に本発明の別の実施例について説明する。図７は、本発明に係る最短マスク出力機能付連想メモリを備えたＬＳＩの回路構成を示すブロック図である。この実施例において、最短マスク出力機能付連想メモリの構成は、図１及び図２を参照して説明した前記実施例のものと基本的に同一とされる。この最短マスク出力機能付連想メモリは、ＩＰパケットのフォワーディング処理を行なうルータに用いられ、より詳細には、宛先フィールドとこれに対応する出力インタフェース情報フィールドの組からなるＩＰフォワーディングテーブルの検索におけるＬＰＭ（Ｌｏｎｇｅｓｔ  Ｐｒｅｆｉｘ  Ｍａｔｃｈ）に適用して好適とされる。被検索対象となるのは、宛先フィールドでプレフィクスと呼ばれるＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）アドレスの最上位ビットから任意長さのビット分だけ指定したビット列からなる。
【０１５７】
１回（段）目の検索では、検索データＦ／Ｆ（フリップフロップ）が検索データをラッチし、検索データがビット線６から各エントリ（図１の連想メモリ・ワード８に対応）に伝達され、各エントリでは、前述した通り、検索データとプレフィクスデータ（データビット列）をマスクビット列が“１”のビットに着目して比較が行なわれ、検索データと一致する連想メモリセル・ワードを決定するとともに、一致するエントリ中で最長のプレフィクス（Ｌｏｎｇｅｓｔ  Ｐｒｅｆｉｘ）を持つエントリの最短マスクの決定を行なう。すなわち、検索データとプレフィクスデータの比較結果に従い、プレフィクス一致線（図１の一致線７に対応する）、マスクビット列出力線に値を出力し、最短マスク（Ｓｈｏｒｔｅｓｔ  Ｍａｓｋ）線では、各エントリのマスクビット出力線のエントリに対応するワイアード論理がとられ、ｎ本の最短マスク（Ｓｈｏｒｔｅｓｔ  Ｍａｓｋ）線には、プレフィクス比較結果が一致するエントリのうち、プレフィクス長（マスクビット列の中でＭＳＢから“１”が連続しているビット数）が最大のマスクビット列を持つエントリのマスクビットである、最短マスク（Ｓｈｏｒｔｅｓｔ  Ｍａｓｋ）が現れ、これをｎビットラッチ（図１の２１）でラッチする。
【０１５８】
２回目の検索では、前記一段目で決定された最短マスク（Ｓｈｏｒｔｅｓｔ  Ｍａｓｋ）情報をラッチ出力線２２から連想メモリセルのマスク比較器に供給し、マスクビット列と、最短マスクの値の比較が行われ、最短マスク情報をもつ連想メモリセル・ワードを決定し、マスク一致線（Ｓｈｏｒｔｅｓｔ  Ｍａｓｋ一致線）に出力し、エンコーダ（Ｅｎｃｏｄｅｒ）を介してＬＰＭしたエントリが決定される。マスクビット列と最短マスクビット情報が一致したエントリで、１段目のプレフィクス比較結果が一致しているエントリは、エンコーダに“１”を出力し、それ以外のエントリは該エンコーダに“０”を出力し、エンコーダには、ＬＰＭしたエントリのみが、“１”を出力し、エンコーダから検索結果であるＬＰＭしたエントリのアドレスが出力される。図７に示す構成においても、検索データＦ／Ｆ（フリップフロップ）から各エントリへの検索データを入力するｎビットのビット線６と、各エントリでのマスクビット列との比較のために入力される最短マスク情報を入力する線２２とが分離されているため、連続した検索を行う際、先行した検索の２回目の検索動作と、次の検索の１回目の検索動作を同時に実行することができ、一定時間に検索が出来る回数を２倍に向上させることができる。
【０１５９】
【発明の効果】
以上説明したように、本発明によれば、従来の最短マスク出力機能付き連想メモリと同様に、２クロックで最適なメモリ・ワードがどれであるかをマスク一致線の値により選択することができることに加え、クロックの立ち上がりで検索データを入力して連続した検索を行うことができ高速検索を実現する、という顕著な効果を奏する。
【０１６０】
上記したように従来の最短マスク出力機能付き連想メモリが、１クロックおきにしか検索データを入力出来なかったが、本発明においては、単位時間あたり２倍の回数の検索を可能としている。
【図面の簡単な説明】
【図１】本発明の一実施例の連想メモリの構成を示すブロック図である。
【図２】本発明の一実施例の連想メモリ・セルを説明する図である。
【図３】本発明の一実施例の連想メモリの動作を示す図（その１）である。
【図４】本発明の一実施例の連想メモリの動作を示す図（その２）である。
【図５】本発明の一実施例の連想メモリの動作を示す図（その３）である。
【図６】本発明の一実施例の連想メモリの動作を説明するためのタイミングチャートである。
【図７】本発明の第２の実施例の構成を示す図である。
【図８】従来の最短マスク出力機能付き連想メモリの構成を示すブロック図である。
【図９】従来の最短マスク出力機能付き連想メモリのメモリ・セルを説明する図である。
【図１０】従来の最短マスク出力機能付き連想メモリの動作を説明する図である。
【図１１】従来の最短マスク出力機能付き連想メモリの動作タイミングチャートである。
【符号の説明】
１  連想メモリ
４  最短マスク線
６  ビット線
７  一致線
８  連想メモリ・ワード
９  データ・セル
１０  連想メモリ
１１  比較器
１２  連想メモリ・セル
１３  論理ゲート
１４  データ・ワード線
１５  マスク・ワード線
１６抵抗
１８  マスク比較器
１９  マスクイッチ線
２０  ラッチ
２１  ｎビットラッチ
２２  ラッチ出力線
２３  選択信号
２４  ラッチ制御信号
１０５  ビット情報
１０  マスク・セル
２０１、２０２  反転論理ゲート
２０３、２０４  ＭＯＳトランジスタＭＯＳトランジスタ
２０９、２１０  反転論理ゲート
１５  マスク・ワード線
２１１、２１２  ＭＯＳトランジスタ
２０５〜２０８  ＭＯＳトランジスタ
【図１】
0003593920.tif 000002
【図２】
0003593920.tif 000003
【図３】
0003593920.tif 000004
【図４】
0003593920.tif 000005
【図５】
0003593920.tif 000006
【図６】
0003593920.tif 000007
【図７】
0003593920.tif 000008
【図８】
0003593920.tif 000009
【図９】
0003593920.tif 000010
【図１０】
0003593920.tif 000011
【図１１】
0003593920.tif 000012