(57)【特許請求の範囲】
【請求項１】
それぞれのアレイが、符号器と、その符号器に関連したｗワード×ｂビットのコア・セル（２３０）のアレイとを含み、その際、各セルはデータ記憶手段を有し、さらに各アレイがクロック信号に応じた探索操作の結果のヒット信号および一致アドレス信号を生成する手段を備えた、複数の内容アドレスメモリ(ＣＡＭ)アレイ（１１０）を有するシステムにおいて、
前記システムの結果のヒット信号および一致アドレス信号を供給する複数の論理回路（１２０）を備え、その論理回路（１２０）のそれぞれは、ＣＡＭアレイ（１１０）からヒット信号を受け取るようにそれぞれのＣＡＭアレイ（１１０）に関連づけられており、前記論理回路（１２０）のそれぞれは、前記クロック信号に応じて自己タイミングをとった信号を生成するタイミング信号生成手段を有し、前記論理回路（１２０）のそれぞれは、前記自己タイミングをとった信号に応じて、伝搬出力ヒット信号が下流の論理回路（１２０）に供給されるように、上流の論理回路から供給される伝搬入力ヒット信号および関連するＣＡＭアレイから供給されるヒット信号を論理的に結合する論理手段（３３６）を有し、前記論理回路のそれぞれが、探索操作の間、前記タイミング信号生成手段によって有効にされるのを妨げられるアドレス・イネーブル信号を含むことを特徴とするシステム。
【請求項２】
前記タイミング信号生成手段は、前記クロック信号から時間遅延される前記自己タイミングを取った信号を生成するための遅延手段（３５４）を有することを特徴とする請求項１記載のシステム。
【請求項３】
前記論理手段は、下流の論理回路へ前記伝搬出力ヒット信号を供給するように、前記自己タイミングを取った信号と、上流の論理回路からの前記伝搬入力ヒット信号と、関連するＣＡＭアレイから供給される前記ヒット信号とのＯＲ論理信号を得るためのＯＲ手段（３３６）からなることを特徴とする請求項１記載のシステム。
【請求項４】
前記ＯＲ手段は、前記自己タイミングを取った信号の反転信号と、前記伝搬入力ヒット信号と、前記ヒット信号とを入力とするＯＲゲートであることを特徴とする請求項３記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、複数のＣＡＭアレイがカスケード接続された内容アドレスメモリ(ＣＡＭ)システムに関する。
【０００２】
【従来の技術】
公知の内容アドレスメモリ(ＣＡＭ)において、データは、物理的位置ではなく内容に基づいて選択される。この機能は、多くのアプリケーションにとって、特に、長い識別ワードから一層短いワードにマッピングする目的でルックアップを実施するときに有用である。この操作は、非同期転送モード(ＡＴＭ)のアドレス変換を含む多くの電気通信(telecom)機能に必要とされる。
【０００３】
多くの場合、システム記憶要求は、１つのＣＡＭアレイ上に格納されるエントリの数を越える。従って、複数のチップ上にありうる複数のＣＡＭアレイが必要とされ、複数のＣＡＭアレイを１つのものとして探索(サーチ)できるようにカスケード接続する必要がある。適当な「ユーザ・フレンドリ」なカスケード機能によって、同じＣＡＭアレイを異なる容量を必要とするシステム内で使用することができるようにし、さらに拡張および拡大縮小を容易にする。
【０００４】
米国特許第5,568,416号明細書は、連想記憶装置を開示しており、その中で複数のＣＡＭチップがカスケード接続され、カスケード内の全てのチップを通して、結果のアドレスおよび状態が伝搬する。それぞれのチップは、それ自身のための状態レジスタ、および全ての上流チップのための状態レジスタを含む。前記米国特許はさらに、カスケード内の最後の装置を識別する手段並びに共通のおよび特異なデータ・エントリのための個々の記憶エリアを開示している。
【０００５】
【発明が解決しようとする課題】
この発明の目的は、改善された内容アドレスメモリ(ＣＡＭ)システムを提供することである。
【０００６】
【課題を解決するための手段】
この発明は、上記の課題を解決するため、それぞれが、データ記憶手段を含むコア・セルのwワードxbビットのアレイを含み、探索操作から生じるヒット信号および一致アドレス信号を供給することができる複数のＣＡＭアレイと、上記ＣＡＭアレイから受信する探索結果を伝搬し、システムのヒット結果および一致アドレス結果を供給するカスケード接続手段とを備えるという構成をとる。
【０００７】
この発明によると、１つのＣＡＭと同じ探索結果出力の種類(例えばヒット、一致アドレス)をもつ複数のＣＡＭアレイを実現することができる。それぞれがwエントリの容量をもつn個のＣＡＭアレイは、nxwワードをもつ１つのマルチチップＣＡＭシステムに統合される。
【０００８】
カスケード接続手段は、それぞれが個々のＣＡＭアレイに関連する複数の伝搬手段を含むことができる。システムの中で、ヒット結果は、アレイからアレイに伝搬される。
【０００９】
【発明の実施の形態】
この発明の実施例を、添付の図面を参照して説明する。
【００１０】
この発明の実施例によるシステムを示す図１を参照すると、システムは、n個の論理回路120を通してカスケード接続されるn個のＣＡＭアレイ110を含む。それぞれの論理回路120は、それぞれのＣＡＭアレイ110に関連し、ＣＡＭアレイ110からヒット信号ht、一致アドレス信号saおよび多重一致信号mtを受信する。これら３つの信号のタイミングは、既知であるが、必ずしも制御可能ではない。論理回路120は、上流の論理回路120からヒット信号および多重一致信号をそれぞれ受信するための入力端子HTIおよびMTIを有する。最も上流の論理回路120の入力端子MTIおよびHTIは共に、論理0端子に接続する。それぞれの論理回路120はさらに、下流の論理回路120にヒット信号および多重一致信号を供給するための出力端子HTおよびMTを有する。それぞれの論理回路120のアドレス出力端子SAは、共通に共有されるバス(以下共有バスという)122に接続する。システムは、反転および非反転入力端子を有するn個のＡＮＤゲート124を含む。それぞれの論理回路120のヒット入力端子HTIおよびヒット出力端子HTは、個々のＡＮＤゲート124の反転および非反転入力端子に接続する。クロック発生器126は、ＣＡＭアレイ110および論理回路120にクロック信号ckを供給する。バス122、および最も下流の論理回路120のヒット出力端子HTおよび多重一致出力端子MTは、探索結果観察回路128に接続する。ＡＮＤゲート124の出力端子は、nからlog2nへの符号器130に接続する。
【００１１】
w(=4)ワード(行)×b(=4)ビット(列)で実現されるＣＡＭアレイ110の例を示す図２を参照すると、ＣＡＭアレイ110は、w行xb列のコア・セル230を含む。コア・セル230の各々は、データ記憶手段(図示せず)を含み、一致線232と１対のビット線234の交わるところにある。１対のビット線234は、２ビットのデータではなく１ビットを表す差分のデータを運ぶ。それぞれのコア・セル230は、データの１ビットを格納するように動作し、そのビット記憶能力に加えて、１ビット比較(論理の排他的ＮＯＲ(ＸＮＯＲ))操作を実施することができる。差分のデータのためのビット線234は、ＣＡＭアレイの内容をロードするためおよび探索参照ワードのための入力データDを受信する参照ワード記憶装置およびビット線ドライバ236に接続する。ＣＡＭアレイ110は、一致線234に接続される符号器238を含む。ＣＡＭアレイの構造は、既に知られている。K.J.Schultz他の「Architectures for Large-Capacity CAMs」(INTEGRATION:the VLSI Journal,Vol.18,pp.151-171,1995年)を参照されたい。
【００１２】
ＣＡＭアレイは、図２に示されるものに限定されず、多くの変形が可能である。例えば、ＣＡＭアレイのデータ比較機能は、コア・セルによって実施されるのではなく、コア・セルに隣接して配置される個々の比較器によって実施される。そのようなＣＡＭアレイは、K.J.Schultz他の米国特許出願第08/748,928号「Large-Capacity Content Addressable Memory」(1996年11月14日出願)の明細書に記述されている。さらに、ＣＡＭアレイのコア・セル・アレイは、K.J.Schultz他の米国特許出願第60/037,834号「Content Addressable Memory」(1997年2月6日出願)の明細書に記述されるようにチェーン結合することができる。
【００１３】
図１および図２を参照すると、探索操作において、差分のデータが、クロック信号ckに応じて１対のビット線234上にアサートされるとき、コア・セル230は、その格納されたデータ・ビットを、この差分のデータ(参照データまたはコンパランドの１ビットとしても知られる)と比較する。格納されたデータが、参照データと等しくないとき、コア・セル230は、(高い論理状態にプリチャージされた)一致線232を低い状態に下げる。格納されたデータが参照データと等しいとき、セル230は、それが接続される一致線232に影響を与えない。所与のワードの中の全てのb個のコア・セル230が、同じ方法で一致線232に接続されているので、そのワードの中のいずれかのビットが、対応する参照ビットに等しくない(すなわち不一致である)場合、一致線232は、低レベルに下げられる。そのワードの全てのビットが、対応する参照ビットに一致する場合のみ、一致線232は、高い論理状態のままでなる。
【００１４】
それぞれのＣＡＭアレイ110は、探索結果(すなわちヒット信号ht、一致アドレス信号saおよび多重一致信号mt)を符号器238へ供給することができる。探索結果は、個々の論理回路120に供給される。それぞれの論理回路120は、ヒット結果および多重一致結果をアレイからアレイに伝搬し、一致アドレス結果を共有バス122に転送する。システムのヒット結果SHTおよび多重一致結果SMTは、はるか右方(最も下流)で得られる。状態情報の追加の有用な一部分は、その結果をバス122上に送ったアレイ(つまり一致する最も高い優先順位のアレイ)の順序位置(ordinal location)であり、この情報は、ＡＮＤゲート124および符号器130によって生成される。
【００１５】
１つのアレイ110に関して、一致するワードの２進アドレスが、「sa」出力へ符号化される。複数のワードが参照データに一致するとき、多重一致信号mtが高い論理状態にアサートされる。このとき、符号器238の一致アドレス出力は、(a)無効な結果、(b)多重一致のうちの１つの一致の位置を表すアドレス、または(c)一致したワードのそれぞれの位置を表す出力のシーケンス、を生成することができる。あるアプリケーションは、多重一致結果を必要とせず、多重一致の機能についての言及は、この明細書から削除しても支障がないことに注意されたい。
【００１６】
図３は、論理回路120の一例の回路図である。図１に示すシステムのＣＡＭアレイ110は、ヒット結果および多重一致の探索結果を供給するので、論理回路120は、それらを同じ方法で伝搬する。１つの論理回路120は、それぞれのＣＡＭアレイ110から、探索結果のヒット信号ht、一致アドレス信号saおよび多重一致信号mtを受け取る。ヒット信号htは、ＡＮＤゲート332および342、並びにＯＲゲート336に供給される。一致アドレス信号saは、転送ゲート334の入力端子に供給され、転送ゲート334の出力端子は、論理回路120の一致アドレス出力端子SAに接続する。多重一致信号mtは、ＯＲゲート344に供給される。伝搬入力ヒット信号htiは、ＡＮＤゲート342、ＯＲゲート336、およびＡＮＤゲート332の反転入力端子に供給され、ＡＮＤゲート332の出力(一致アドレス・イネーブル信号sae)は、転送ゲート334に供給される。多重一致入力端子MTIは、ＯＲゲート344に接続する。ＡＮＤゲート342の出力は、ＯＲゲート344に供給される。ＯＲゲート344の出力は、バッファ346に供給され、バッファ346の出力端子は、論理回路120の多重一致出力端子MTに接続する。
【００１７】
自己タイミングをとった信号stが、自己タイミングをとった信号の発生器で生成される。自己タイミングをとった信号の発生器の多くの実現しうる実施例がある。結果として生じる自己タイミングをとった信号stが上述したように使用され、競合のない結果バスの共有を可能にする限り、この発明は、そのようなすべての回路を包含する。
【００１８】
図３を参照すると、自己信号発生器の考えられる１つの実施例で、クロック信号ckは、フリップフロップ352のリセット入力端子Ｒに供給される。さらにクロック信号ckは、バッファ354を通してフリップフロップ352のセット入力端子Sに供給される。自己タイミングをとった信号stは、フリップフロップ352のQ出力端子から、ＡＮＤゲート332およびＯＲゲート336の反転入力端子に供給される。自己タイミングをとった信号stの立ち下がり端は、クロック信号ckの立ち上がり端によって生成され、自己タイミングをとった信号stの立ち上がり端は、クロック信号ckの立ち上がり端の遅延した形によって生成される。クロック信号ckの立ち上がり端に基づいて自己タイミングをとった信号stの両端のタイミングをとることにより、デューティサイクルに依存しなくなる。遅延チェーンの遅延は、クロック信号ckとヒット信号htの立ち上がり端の間の遅延に等しくなるように設定することができる。あるいは、クロック信号ckのデューティサイクルが既に分かっていて、良好に制御される場合、自己タイミングをとった信号stの立ち上がり端のタイミングは、クロック信号ckの立ち下がり端によって制御することができる。ヒット・タイミングは、実施例を使用して最大限の操作速度を達成するために予測可能であるべきことに注意されたい。ヒット・タイミングが予測可能でない実施例では、stの低レベルのパルス幅は、起こりうるどんなht遅延よりも長くなるよう十分な長さでなければならない。
【００１９】
図４は、自己タイミングをとった信号および探索結果を示すタイミング・チャートである。ＣＡＭアレイ110からのアドレス信号saは、転送ゲート334に供給される。イネーブル信号saeが低レベルであるとき、転送ゲート334は、アドレス信号がゲートを通過しないようにする。転送ゲート334からの出力信号は、アドレス出力端子SAに供給される。ＯＲゲート336からの伝搬出力ヒット信号htoは、バッファ338に供給される。
【００２０】
システム内の全ての論理回路120上でst=0である間、どのアレイも、バス122を駆動することができない。
【００２１】
同じ時間、カスケード内の全てのヒット信号HTは、論理１であり、st=0(図5Aないし図５Dを参照)のために、伝搬入力ヒット信号htiによってSA出力ドライバを二重にディスエーブルする。この部分的な冗長は、再び信号のタイミングをとり、ゲートへの入力の数を低減することによって、この発明の理念から逸脱することなく除去することができる。そのような方法は、丈夫さの劣る設計に結び付くことに注意されたい。
【００２２】
１つのアレイ上の関連する全ての信号の波形が、伝搬入力ヒット信号htiの4つの異なるケース(0から0、1から0、0から1、および1から１への遷移)について、図5Aないし図5Dに示される。
【００２３】
分かるように、非選択(deselection)が、回路120に属する論理に基づいて生じ、上流の信号によって選択だけがゲート制御されるので、正しい操作は、(a)アレイ間の速度の違い、および(b)ルーティング遅延、に依存しない。システムに加えられる追加のアレイが、異なる処理条件または完全に異なる製作技術に従うときであっても、この特徴は拡張性を支援する。
【００２４】
最悪の場合のタイミングが特徴づけられるとき、SAドライブまでの最も遅いパスは、伝搬入力ヒット信号HTI入力からのものである。伝搬入力ヒット信号HTIの下方向への遷移は、さらに伝搬出力ヒット信号HT(ht=0を仮定)に伝搬することができ、最悪の場合のシステム性能は、独立型の１つのアレイのシステム性能に、伝搬入力ヒット信号のHTIからHTまでの遅延の(n-2)倍および伝搬入力HTI信号のhtiからSAまでの遅延を加えたものに等しい。システム性能は、以下の式によって特徴付けられる。
【００２５】
【数１】
tCH-SAV = tCH-HTV + (n-2)xtHTIL-HTL + tHTIL-SAV
tCH-SHTV = tCH-HTV + (n-1)xtHTIL-tHTL
【００２６】
上の式で、tCH-SAV は、クロックckの上方向の遷移から有効な一致アドレスSAまでの時間を意味し、tCH-HTV は、分離された１つのチップについて、クロックckの上方向の遷移から有効なHTまでの時間を意味する。また、tHTIL-HTL は、チップ入力でのHTIの下方向の遷移から同じチップの出力におけるHTの下方向の遷移までの時間であり、tHTIL-SAV は、チップの入力でのHTIの下方向の遷移から同じチップから出される有効なSAまでの時間である。さらに、tCH-SHTV は、クロックckの上方向の遷移から有効なSHTまでの時間である。
【００２７】
自己タイミングをとった信号stを用いない場合、SAドライブのディスエーブルおよびイネーブルは、HTIタイミングに依存することに注意されたい。バスの競合を防ぐことが困難になり、ディスエーブルのタイミングは、カスケード内のアレイの位置に依存する。
【００２８】
別の代替の実施例で、または単に追加の機能として、探索アドレス結果をレジスタ(図示せず)に格納することができる。
【００２９】
符号器130の出力は、どのアレイ結果レジスタが読み出されるか判断するために使用することができる。
【００３０】
この発明の開示によって論理上包含される実施例には、異なる信号極性、同等のブールのゲート・レベル実現、小さいタイミング変化、その他を含む多くの変形がありうることを理解されたい。
【００３１】
【発明の効果】
本発明によれば、複数のＣＡＭアレイおよびカスケード接続手段を含む内容アドレスメモリシステムで、複数のＣＡＭアレイを１つものとして探索し、システム全体としての結果を得ることを可能にするカスケード接続を実現することができる。また、論理回路で生成される自己タイミングをとった信号により、共有バスの競合を防ぐことができる。
【図面の簡単な説明】
【図１】この発明の実施例による、カスケード接続された複数のＣＡＭアレイを含むシステムのブロック図。
【図２】図１に示されるＣＡＭアレイの一例の回路図。
【図３】図１に示される論理回路の一例の回路図。
【図４】１つのＣＡＭアレイ内の自己タイミングをとった信号および探索結果を示すタイミング・チャート。
【図５】伝搬入力ヒット信号に応答する探索信号の相対的なタイミングを示すタイミング・チャート。
【符号の説明】
110    ＣＡＭアレイ
120    論理回路
122    共有バス
230    コア・セル
232    一致線
234    ビット線
238    符号器
【図１】
0004347439.tif 000002
【図２】
0004347439.tif 000003
【図３】
0004347439.tif 000004
【図４】
0004347439.tif 000005
【図５】
0004347439.tif 000006