(57)【要約】      （修正有）【課題】ＣＡＭ制御デバイスのメモリ監視動作を容易にし、大容量ＣＡＭの可用性向上を図る。【解決手段】記憶情報（エントリ）および入力情報（比較情報または検索キー）の構成要素である領域に応じて、最小値と差を対とする４値情報、もしくはデータとマスクを対とする３値情報を入出力信号とする。また、前記二種類の情報に応じて二種類の符号化回路および復号回路を配置し、エントリおよび検索キーの各領域における情報の形式を指定するために複数配置されたレジスタに設定された値に応じて、いずれか一方の符号化回路および復号回路を活性化する。外部コマンド信号とアドレス信号により前記複数のレジスタから所望のレジスタを選択することにより、処理する情報に応じた符号化および復号を行う。【選択図】図１
2005353107.tif 000002
【特許請求の範囲】
【請求項１】
第１の複数の信号線と第２の複数の信号線との間に配置された入出力回路と、
前記第２の複数の信号線が入力端子に接続された符号化回路と、
前記第２の複数の信号線が出力端子に接続された復号回路と、
複数のメモリアレイとを有する半導体装置において、
前記入出力回路は、第１のマッピングに基づく第１の情報または第２のマッピングに基づく第２の情報の送受信を行い、
前記符号化回路は、前記第１または第２の情報から符号化した第３の情報を前記複数のメモリアレイに出力し、
前記復号回路は、前記複数の該メモリアレイから受信した前記第３の情報を復号して発生した前記第１または第２の情報を前記入出力回路に出力し、
前記メモリアレイは、前記第３の情報を記憶すると共に、新たに入力された前記第３の情報との比較動作を行うことを特徴とする半導体装置。
【請求項２】
請求項１において、
前記符号化回路は、前記第１の情報に応じた第１符号化回路ユニットと前記第２の情報に応じた第２符号化回路ユニットとを具備し、前記第１又は第２符号化回路ユニットは、処理すべき情報に応じて選択的に活性化され、
前記復号回路は、前記第１の情報に応じた第１復号回路ユニットと前記第２情報に応じた第２復号回路ユニットを具備し、前記第１又は第２復号回路ユニットは、処理すべき情報に応じて選択的に活性化されることを特徴とする半導体装置。
【請求項３】
請求項２において、
前記半導体装置は、さらに、処理すべき情報の形式が前記第１のマッピングに基づくものであるか、あるいは前記第２のマッピングに基づくものであるかを識別するための第１レジスタを具備し、
前記第１レジスタに設定された値に応じて、前記第１又は第２符号化回路ユニットが選択され、前記第１又は第２復号回路ユニットが選択されることを特徴とする半導体装置。
【請求項４】
請求項３において、
前記第１レジスタは、複数のレジスタ・ユニットで構成され、
前記半導体装置は、外部から入力されたコマンドとレジスタ・アドレスを用いて、前記複数のレジスタ・ユニットの中から所望のレジスタ・ユニットを選択することにより、処理すべき情報の形式に応じた複合化および復号を行うことを特徴とする半導体装置。
【請求項５】
請求項４において、
前記符号化回路は、書き込み動作と検索動作とで使用されることを特徴とする半導体装置。
【請求項６】
第１の複数の信号線と第２の複数の信号線との間に配置された入出力回路と、
前記第２の複数の信号線が入力端子に接続された符号化回路と、
前記第２の複数の信号線が出力端子に接続された復号回路と、
複数のメモリアレイとを有する半導体装置において、
前記入出力回路は、第１のマッピングに基づく第１の情報と第２のマッピングに基づく第２の情報からなる情報の送受信を行い、
前記符号化回路は、前記第１または第２の情報から符号化した第３の情報を前記複数のメモリアレイに出力し、
前記復号回路は、前記複数のメモリアレイから受信した前記第３の情報を復号して生成した前記第１または第２の情報を前記入出力回路に出力し、
前記メモリアレイは、前記第３の情報を記憶すると共に、新たに入力された前記第３の情報との比較動作を行うことを特徴とする半導体装置。
【請求項７】
請求項６において、
前記符号化回路は、前記第１の情報に応じた第１符号化回路ユニットと前記第２の情報に応じた第２符号化回路ユニットを具備し、前記第２の複数の信号線が多分割された単位で、処理すべき情報に応じて前記第１又は第２符号化回路ユニットが選択的に活性化され、
前記復号回路は、前記第１の情報に応じた第１復号回路ユニットと前記第２の情報に応じた第２復号回路ユニットを具備し、前記第２の複数の信号線が多分割された単位で、処理すべき情報に応じて前記第１又は第２復号回路ユニットが選択的に活性化されることを特徴とする半導体装置。
【請求項８】
請求項７において、
前記半導体装置は、さらに、処理すべき情報の形式が前記第１のマッピングに基づくものであるか、あるいは前記第２のマッピングに基づくものであるかを識別するための第１レジスタを具備し、
前記第１レジスタに設定された値に応じて、前記第１又は第２符号化回路ユニットが選択され、前記第１又は第２復号回路ユニットが選択されることを特徴とする半導体装置。
【請求項９】
第１の複数の信号線と第２の複数の信号線との間に配置された入出力回路と、
前記第２の複数の信号線が入力端子に接続された符号化回路と、
前記第２の複数の信号線が出力端子に接続された復号回路と、
複数のメモリアレイとを有する半導体装置において、
前記入出力回路は、第１のマッピングに基づく第１の情報または第２のマッピングに基づく第２の情報の送受信を行い、
前記符号化回路は、前記第１または第２の情報から符号化した第３の情報を前記複数のメモリアレイに出力し、
前記復号回路は、前記複数のメモリアレイから受信した前記第３の情報を復号して発生した前記第１または第２の情報を前記入出力回路に出力し、
前記メモリアレイは、前記第３の情報を記憶すると共に、新たに入力された前記第３の情報との比較動作を行い、
前記第１のマッピングに基づく情報に対する入出力信号は最小値と差の組み合せであり、
前記第２のマッピングに基づく情報に対する入出力信号はデータとマスクの組み合せであることを特徴とする半導体装置。
【請求項１０】
請求項９において、
前記半導体装置は、前記最小値及び差、又は、前記データ及びマスクの組み合せを２回に分けて送受信することを特徴とする半導体装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は半導体装置に関し、特に、蓄積ノードに記憶された情報と入力された情報との比較を行うコンテント・アドレッサブル・メモリセル（ＣＡＭセル）を含む半導体装置において、装置内部で符号化した情報を記憶または比較するＣＡＭアレイを含む半導体装置に関する。
【背景技術】
【０００２】
インターネットの爆発的な普及に伴い、ネットワークにおけるルータやスイッチに要するテーブル規模が急増しており、テーブル検索の高速化が課題となっている。この課題をハードウェア的に解決する手段として、ターナリ・コンテント・アドレッサブル・メモリ（ＴＣＡＭ）が注目されている。
【０００３】
図１９は、ルータの構成を模式的に示したものである。同図では、一例として、ネットワーク・インターフェイスNIF、ネットワーク・プロセッサNP、検索エンジンSE、検索テーブルLUT、コンテント・メモリCMで構成された例を示している。ネットワーク・インタータフェイスNIFとネットワーク・プロセッサNPは、システム・バスSBSで接続されている。ネットワーク・プロセッサNPと検索エンジンSEは、内部バスIBSで接続されている。検索エンジンSEと検索テーブルLUTは、データ・バスDQで接続されている。ここで、検索テーブルLUTはＴＣＡＭ、コンテント・メモリCMはスタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）やダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）である。
【０００４】
ルータは、インターネット網IPNからネットワーク・インタフェイスNIFを介してパケットを送受信する。ネットワーク・プロセッサNPは、受信したパケットの内容を解読および再構成する。例えば、パケットのヘッダから読み出された宛先インターネット・プロトコル・アドレス（ＩＰアドレス）は、検索エンジンSEを介して検索テーブルLUTに転送される。検索テーブルLPTは、複数の宛先ＩＰアドレスを記憶しており、入力された宛先ＩＰアドレスが記憶されている場合に、その宛先ＩＰアドレスに関する情報をコンテント・メモリCMから読み出すためのアドレスを発生する。コンテント・メモリCMは、パケット転送に必要な経路情報やルータのポート番号などを記憶しており、コンテント・メモリ・アドレス・バスCADDを介して入力されたアドレスに応じた情報を、コンテント・バスCBSおよび検索エンジンSEを介してネットワーク・プロセッサNPに出力する。ネットワーク・プロセッサNPは、これらの情報に基づいてヘッダの内容を再構成し、指定されたポートから次の中継点へパケットを転送する。
【０００５】
非特許文献１は、ＴＣＡＭにおけるＴＣＡＭセル構成を記載する。図２０に非特許文献１のFig.1のセル構成を示す。このセルは、次の３つの回路ブロックで構成される。第一の回路ブロックは、所謂ＳＲＡＭセルと同じように、NMOSトランジスタN311、N312、N313、N314とPMOSトランジスタP311、P312で構成されるメモリセルSMC31である。第二の回路ブロックは、メモリセルSMC31同様に、NMOSトランジスタN321、N322、N323、N324とPMOSトランジスタP321、P322で構成されるメモリセルSMC32である。第三の回路ブロックは、NMOSトランジスタN331、N332、N333、N334、M335で構成される比較回路MUCである。メモリセルSMC31は‘0’または‘1’の二値情報、メモリセルSMC32は所謂『Don't care』状態と呼ばれる第三の情報‘X’をそれぞれ記憶する。これらの情報は、選択的にワード線WL31またはWL32を活性化することにより、公知のＳＲＡＭと同様に書き込んだり読み出したりすることができる。また、比較回路MUC は、記憶情報と入力情報とを比較するためのXNOR演算を行う。
【０００６】
一例として、記憶情報が‘1’の場合の検索動作を以下に説明する。この場合、メモリセルSMC311内の記憶ノードNTが電源電圧VDD、記憶ノードNBが接地電圧VSSに駆動されているものとする。今、ＴＣＡＭセルはDon't care状態におらず、メモリセルSMC32内の記憶ノードDCが電源電圧VDDに駆動されているものとすると、比較回路MUC内のトランジスタN331、N335はそれぞれ導通し、トランジスタN332はカットオフ状態にある。このような状態において、マッチ線MLを接地電圧VSSよりも高い電圧にプリチャージしてから情報‘1’を入力すると、接地電圧VSSにあったビット線BLTとBLBのうち、ビット線BLBが電源電圧VDDに駆動されることにより比較回路MUC内のトランジスタN334が導通状態となる。しかし、トランジスタN332がカットオフ状態にあるので、マッチ線MLと接地電極の間は開放された状態に保たれる。したがって、プリチャージ電圧に保持されたマッチ線MLの電圧を、図示されていないマッチ線センスアンプで弁別することにより、比較した情報が一致していたと判定される。
【０００７】
反対に、情報‘0’を入力すると、接地電圧VSSにあったビット線BLTとBLBのうち、ビット線BLTが電源電圧VDDに駆動されることにより比較回路MUC内のトランジスタN333が導通状態となる。したがって、トランジスタN335、N331、N333を介してマッチ線MLと接地電極とが短絡されるので、マッチ線MLが放電される。すなわち、マッチ線MLの電圧低下をマッチ線センスアンプで弁別することにより、比較した情報が不一致であったと判定される。なお、同図のTCAMセルがDon't care状態にある場合、メモリセルSMC32内の記憶ノードDCが接地電圧VSSに駆動されているので、比較回路MUC内のトランジスタN335はカットオフされる。したがって、如何なる情報が入力されようとも、マッチ線MLと接地電極との間に電流経路が形成されないので、マッチ線MLはプリチャージ電圧に保持され、強制的に一致と判定される。
【０００８】
また、入力情報が所謂『マスク』状態を示す第三の情報‘Ｘ’の場合においても、ビット線BLTおよびBLBは共に接地電位VSSに保持されるので、比較回路MUC内のトランジスタN333およびN334はカットオフされる。したがって、メモリセルSMC31が如何なる情報を記憶していようとも、この場合もマッチ線MLと接地電極との間に電流経路が形成されないので、マッチ線MLはプリチャージ電圧に保持され、強制的に一致と判定される。
【０００９】
【非特許文献１】アイ・イー・イー・イー、ジャーナル・オブ・ソリッド・ステート・サーキッツ、第３１巻、第１１号、第1601頁から第1609頁（IEEE Journal of Solid-state circuits, vol. 31, No. 11, November 1996, p.1601-1609）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本願発明者等は、本願に先立ち、ＴＣＡＭにおける容量不足と消費電力増大を解消するＣＡＭを実現するための、エントリあるいは検索キーの符号化方式とメモリアレイ構成を検討した。ここで、ＴＣＡＭでは、ＤＲＡＭやＳＲＡＭで広く使われているワードに対応する言葉として、“エントリ”を用いるのが普通である。エントリは、各ワードに記憶された情報を指す言葉であるので、以下では慣例に従って記憶情報をエントリ、比較情報を検索キーと呼ぶことにする。以後、本願発明をするにあたって検討した内容を図２１〜図２４を用いて説明するが、図２１〜図２４は、検討内容を説明するために本願発明者等が作成したものであり、既に公開されている図面ではない。
【００１１】
図２１にＴＣＡＭの大容量化・低消費電力化に適したOne-hot-spotブロック符号のデータ・パターンの例を示す。ここでは、情報０〜３（１０進数）の組み合せ（ベキ集合）に対して、ターナリ表記とOne-hot-spotブロック符号表記によるデータ・パターンの例が示されている。One-hot-spotブロック符号は、情報に応じたビットを論理値‘1’に活性化した符合であり、複数の情報を一つのデータ・パターンで表記することができる。このため、ターナリ表記では不可能であった１〜２や０〜２、１〜３といった連続する１０進数の情報を一纏めに記憶することが可能となるので、ＴＣＡＭで問題であった容量不足を緩和することができる。なお、エントリや検索キーとして入力される情報は２ビットに限らず複数のビットで構成されるが、それらは図２１に従って全て２ビット単位で符号化される。
【００１２】
図２２に本願発明に先立ってのメモリアレイ構成を示す。このメモリアレイは、マッチ線が、メインマッチ線MMLm（m=0,1,…）とサブマッチ線SMLmj（m=0,1,…,j=0,1,…）からなる階層構造を形成する。メモリセルは、複数のワード線WLm（m=0,1,…）と複数のビット線BLni（n=0,1,…,i=0,1,2,3）との交点にそれぞれ配置される。複数のワード線の各々はワード・ドライバ群WDB、複数のビット線は読み書き回路群RWBによりそれぞれ駆動される。ビット線BLni（n=0,1,…,i=0,1,2,3）には、対応する複数のサーチ線SLni（n=0,1,…,i=0,1,2,3）がそれぞれ平行に配置される。複数のサーチ線の各々は、サーチ・ドライバ群SDBにより駆動される。また、ワード線WLm（m=0,1,…）には、対応する複数のメインマッチ線MMLm（m=0,1,…）がそれぞれ平行に配置される。
【００１３】
さらに、複数のサブマッチ線SMLmj（m=0,1,…,j=0,1,…）が、対応するメインマッチ線MMLm（m=0,1,…）にそれぞれ平行に配置され、対応するサブマッチ判定回路SMDmj（m=0,1,…,j=0,1,…）を介してそれぞれ接続される。サブマッチ線には、例えばサブマッチ線SML01のように、四つのメモリセルDMCi（i=0,1,2,3）がそれぞれ接続される。ここで、これら四つのメモリセルDMCi（i=0,1,2,3）からなるグループを、メモリブロックMBmj（m=0,1,…,j=0,1,…）とそれぞれ呼ぶ。メモリセルの各々は、図２３に示すように、３つのNMOSトランジスタT311、T312、T313とキャパシタCで構成される。
【００１４】
また、サブマッチ判定回路は、対応するサブマッチ線をプリチャージするためのNMOSトランジスタT421と、サブマッチ線に発生された微小な信号の弁別するためのNMOSトランジスタT422で構成される。さらに、図２２のメインマッチ判定回路群MMDBは、図２３に示すように複数のメインマッチ判定回路MMDm（m=0,1,…）で構成され、それぞれ対応するメインマッチ線を駆動するためのNMOSトランジスタT431と、対応するメインマッチ線上のエントリにおける比較結果を分別するためのセンスアンプSAで構成され、比較結果に応じた電圧のヒット信号（ここではHIT0）を出力する。
【００１５】
本願発明者等は、本願に先立ち、上記記載のＣＡＭにおけるエントリおよび検索キーの入力方式について更に検討した。特に、エントリおよび検索キーの構成を詳細に検討したところ、後述する三つの問題があることに気がついた。これらの問題を述べる前に、理解を助けるために、エントリおよび検索キーの構成について説明する。
【００１６】
図２４は、エントリおよび検索キーが１４４ビットの信号で構成される場合の例を示している。以下では、エントリおよび検索キーの構成要素を領域と呼ぶが、これらは、主に国際標準化機構ＩＳＯ（International Organization for Standardization）により標準かされたＯＳＩ（Open Systems Interconnection）参照モデルで規定されているものである。50は、第３層（ネットワーク層）における送信元ＩＰアドレスSIP（Source IP address）領域であり、３２ビットの情報である。51は、第３層（ネットワーク層）における宛先ＩＰアドレスDIP（Destination IP address）領域であり、同じく３２ビットの情報である。52は、第４層（トランスポート層）のプロトコルIPPRT領域であり、８ビットの情報である。
【００１７】
領域53は、インターネット・プロトコルのサービス品質を示すTOS（Type of service）領域であり、同じく８ビットの情報である。54は、第４層における送信元ポート番号（Source port）SPORT領域であり、１６ビットの情報である。55は、第４層における宛先ポート番号（Destination port）DPORT領域であり、同じく１６ビットの情報である。56は、ユーザーが定義し、付加した情報を示すUDT領域であり、同図では２３ビットの例が示されている。57は、ユーザーが付加した情報のうち、特に複数のフラグを示すUFLG領域であり、同図では９つのフラグに応じて９ビットの情報の例が示されている。なお、１４４ビットもの長大なビット幅の情報をＣＡＭに入力するには、実装コストを抑制するためにデータ・バスのピン数を例えば７２個として、同図に示したように二つに分割して入力する手法が広く採られている。
【００１８】
さて、このようなエントリおよび検索キーを扱うＣＡＭに上記記載のOne-hot-spotブロック符号を適用すると、次の三つの問題が発生することに気がついた。第一の問題は、ＣＡＭを制御する例えばネットワーク・プロセッサと称されるデバイスが、ＣＡＭ内部のメモリ使用状況を監視するのが困難になるという点にある。すなわち、ＣＡＭ内部で符号化と圧縮を行ってからエントリを記憶しているが、ＣＡＭ外部からは入力したエントリがＣＡＭ内部で勝手に書き換わったように見えてしまう。このため、ＣＡＭ制御デバイスは、情報が書き込まれていないエントリ（以下では、空エントリ）を把握することができず、エントリの更新や追加動作に支障をきたす。また、エントリ・カウント信号群を追加し、チップ内部で圧縮および展開されたエントリに関する情報を出力することにより監視機能を補助することが考えられるが、データ・バスのピン数が増えることにより実装コストが嵩んでしまう。したがって、圧縮および展開動作をＣＡＭ制御デバイスに任せ、ＣＡＭは圧縮された情報に応じた信号の符号化および復号だけを行うことが望ましい。
【００１９】
第二の問題は、１ビットの情報を効率よく記憶することが困難であるという点にある。前述のOne-hot-spotブロック符号は、図２４の50、51のようなＩＰアドレス領域における複数のＩＰアドレスや同図の54、55のようなポート番号領域もおける複数のポート番号を一纏めに記憶するのに好適である。しかし、特に領域57のようなフラグを、図２１に示したような情報０〜３（１０進数）のベキ集合とOne-hot-spotブロック符号との対応に従って符号化を行おうとすると、ＣＡＭは図２２に示したようにメモリセルが２ビット単位でブロック化されているために、一つのメモリブロックに一つのフラグしか記憶することができない。すなわち、一つのメモリブロックに、フラグが記憶されているか（例えば情報が１か）否か（例えば情報が０か）、その何れかでも良いか（例えば情報が０または１のいずれでも良いか）という情報しか記憶することができない。このために、１ワードあたり１４４ビット以上のメモリブロックが必要となり、メモリ使用効率が低下する。したがって、一つのメモリブロックに二つのフラグを記憶するには、ＣＡＭはターナリ表記に応じた情報を入力して、符号化することが望ましい。
【００２０】
第三の問題は、図２４で説明したように長大なエントリおよび検索キーが多分割されて入力されるので、様々な領域の情報を処理できる符号化回路および復号回路が必要となる点にある。すなわち、同図で二分割された検索キーのそれぞれの下位ビットに注目すると、一方では宛先ＩＰアドレスの一部を処理し、他方ではフラグ情報を処理するようなビットが存在するので、両方に対応できる符号化回路および復号回路が必要となる。そこで、回路規模を抑制しながら、前述の相反する要求を満たすには、動作サイクル毎に処理する情報に応じて符号化回路および復号回路を切り替えられるような回路構成とすることが望ましい。
【００２１】
以上の説明から、本発明の課題は、エントリおよび検索キーの領域に応じた情報をＣＡＭとＣＡＭ制御デバイスとの間で送受信することにある。また、動作サイクル毎に異なる情報に応じて符号化および復号を行うことにより、One-hot-spotブロック符号を適用したＣＡＭの可用性を向上することにある。
【課題を解決するための手段】
【００２２】
本発明の代表的な手段の一つを示せば以下の通りである。即ち、記憶情報（エントリ）および入力情報（比較情報または検索キー）の領域に応じて、最小値と差を対とする４値情報、もしくはデータとマスクを対とする３値情報を入出力信号とする。また、前記二種類の情報に応じて二種類の符号化回路および復号回路を配置し、エントリおよび検索キーの各領域における情報の形式を指定するために複数配置するレジスタに設定された値に応じて、いずれか一方の符号化回路および復号回路を活性化する。外部コマンド信号とアドレス信号により前記複数のレジスタから所望のレジスタを選択することにより、処理する情報に応じた符号化および復号を行う。
【発明の効果】
【００２３】
圧縮をかけながらエントリを記憶するＣＡＭにおいて、従来のＴＣＡＭと同様に、メモリ使用状況の監視を容易に行うことができる。また、様々な構成のエントリおよび検索キーに対応することが可能となる。したがって、エントリを効率良く記憶するＣＡＭの可用性を向上することができる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の実施例について、図面を用いて詳細に説明する。実施例の各ブロックを構成する回路素子は、特に制限されないが、典型的には公知のＣＭＯＳ（相補型ＭＯＳトランジスタ）等の半導体集積回路技術によって、単結晶シリコンのような１個の半導体基板上に形成される。
【実施例１】
【００２５】
《入出力信号のマッピング》
図２は、本発明におけるエントリに対するＣＡＭ入出力信号とOne-hot-block符号とのマッピングの例をＩＰアドレス領域とフラグ領域のそれぞれについて示している。詳細は後述するが、本入出力信号の特徴は２つある。第一の特徴は、複数の情報を一纏めに記憶するようなＩＰアドレス領域において、各エントリの最小値と差に関するバイナリ情報を入出力信号とする点にある。第二の特徴は、フラグ領域に代表されるようにＩＰアドレスのように範囲指定されることが無い領域において、従来のＴＣＡＭと同様にデータとマスクに関するバイナリ情報を入出力信号とする点にある。
【００２６】
まず、ＩＰアドレス領域の入出力信号について説明する。同図では、簡単のために０〜３（１０進数）の組み合せの場合について、２ビットの入出力信号のマッピングが示されている。より具体的には、単独値（０、１、２、３）と連続値（０〜１、０〜２、０〜３など）に対して最小値とその差を２ビットのバイナリ値で割り当てる。残りの組み合せは、記憶情報が書き込まれていない状態すなわち初期状態や、範囲指定されたＩＰアドレスの記憶には使われない離散値の集合であるが、これらの組み合せには、残りのバイナリ値の組み合せを適宜割り当てている。これらの残りの組み合せに対して、最小値や差という言葉は意味をなさないので、同図では、入出力信号のパターンが括弧で括られている。
【００２７】
なお、０〜３（１０進数）のそれぞれを小さい方から順に‘01’、‘02’ ‘10’、‘20’で表記すると、初期状態を除いた組み合せは、これらの足し算で表現することができる。すなわち、０〜３（１０進数）の組み合せは、二桁の０〜３を組み合せた二桁のシンボルで表記することができる。そこで、図２に示すようなＩＰアドレス領域に対する入出力信号とOne-hot-spotブロック符号との関係を、以下の実施例では便宜上、『４値情報の符号化マッピング』を呼ぶことにする。
【００２８】
次に、フラグ領域の入出力信号について説明する。この場合、前述したように、従来のＴＣＡＭに準じた情報の符号化を行う。そこで、図２に示すようなフラグ領域などに対する入出力信号とOne-hot-spotブロック符号との関係を、以下では便宜上、『３値情報の符号化マッピング』と呼ぶことにする。同図では、“Don't care”またはローカル・マスクとなるビットのマスクを論理値‘0’とする例が示されている。ここで、データにおける論理記号‘Z’は不定値であることを示し、論理値が‘1’か‘0’の何れでも良いことを示している。
【００２９】
図３は、さらに本発明による検索キー用のＣＡＭ入力信号とOne-hot-block符号とのマッピングの例をＩＰアドレス領域とフラグ領域のそれぞれについて示している。図２と比べての相違点は、二つある。第一の相違点は、初期状態に対するマッピングを削除している点にある。その理由は、検索動作において、情報の組み合せが無いことは検索キーを入力しないことに他ならないからである。第二の相違点は、ＩＰアドレス領域において、２連続値および３連続値のマッピングを削除している点にある。その理由は、パケット毎に指定されたＩＰアドレスは唯一つであり、これを検索するかしないかのいずれかしか有り得ないからである。その他は、図２と同じマッピングである。
【００３０】
以上のマッピングにより、次の二つの効果が得られる。第一の効果は、ＣＡＭの入出力信号とＣＡＭ内部で符号化された信号との間に、１対１の関係を築ける点にある。この結果、ＣＡＭ制御デバイスはエントリ数を正確に把握することができるので、メモリ使用状況などの監視が容易になる。第二の効果は、エントリと検索キーとに対して、共通の入出力信号を用いることが可能となる点にある。この結果、後述する符号化回路および復号回路の共通化が図られ、ＣＡＭのチップ面積を抑制することが可能となる。
【００３１】
なお、ＩＰアドレス領域の境界がメモリブロックの境目に一致するようにエントリおよび検索キーを構成することによって、メモリブロックに効率良くエントリを記憶することができるようになることは、これまでの説明から容易に理解することができる。また、これまでは、４値情報の符号化マッピングはＩＰアドレス領域に用いられるものとして説明してきたが、これに限定されず、他の領域にも適用可能である。例えば、複数のポート番号を記憶する場合がある、ポート領域に適用することも可能であり、ＩＰアドレス領域の場合と同様の効果が得られる。
【００３２】
最後に、本実施例によるマッピングについて補足する。インターネット・プロトコル・バージョン４（ＩＰｖ４）におけるＩＰアドレス領域は、図２４に示したように３２ビット幅である。よって、ＩＰアドレス領域の入出力信号は３２ビット全体で見た最小値と差であり、これらを２ビット単位にブロック符号化することは、次の説明から容易に理解することができる。簡単な例として情報１２〜１４（１０進数）の場合、最小値は１２（バイナリ値で‘1100’）、差は２（バイナリ表記で‘0010’）である。図２に従い上位２ビットを符号化すると1000、下位２ビットを符号化すると0111であるので、One-hot-spotブロック符号‘1000_0111’を得る。
【００３３】
《ＣＡＭ全体構成》
次に、図１と図４に従って、前述の入出力信号マッピングに基づいたＣＡＭの全体構成を説明する。図１は、ＣＡＭの要部ブロックの基本構成を示す図である。本構成は、メモリアレイMAA、MAB、データ入出力回路DIO、各種レジスタ群REGB、ＣＡＭ制御回路CAMCTL、リフレッシュ・カウンタRFCNT、ロウ・デコーダXDEC、符号化回路ENCDR、復号回路DCDR、プライオリティ・エンコーダPENC、ＲＡＭ制御回路RAMCTLを有する。メモリアレイMAA、MABは図２２および図２３に示した構成である。データ入出力回路DIOは、データ・バスDQとチップ内部データ・バスDBSとの間に配置され、アドレス信号やデータ、さらにチップの各種設定を定義する制御信号の授受を行う。
【００３４】
各種レジスタは、データ・バスDQの信号線数（ここではk+1）に応じた複数ビットのレジスタでそれぞれ構成される。同図では、内部データ・バスDBSを介してアドレス信号の授受を行うレジスタとして、バースト・ライト・レジスタWREG、ネクスト・フリーアドレス・レジスタNREG、バースト・リード・レジスタRREGの三つが示されている。第一のバースト・ライト・レジスタWREGは、バースト・ライト動作における１サイクル目のロウ・アドレスとバースト長とを記憶し、バースト・ライト動作が始まるとカウントアップしながら２サイクル目以降のアドレスを発生する。
【００３５】
第二のネクスト・フリーアドレス・レジスタNREGは、空エントリのロウ・アドレスを記憶する。第三のバースト・リード・レジスタRREGは、バースト・リード動作における１サイクル目のロウ・アドレスとバースト長を記憶し、バースト・リード動作が始まるとカウントアップしながら２サイクル目以降のアドレスを発生する。これらのレジスタが発生したアドレス信号は、ロウ・アドレス・バスXBSを介してロウ・デコーダXDECに入力され、デコードされた結果がメイン・ワード線群MWLBA、MWLBBを介してメモリアレイMAA、MABにそれぞれ入力される。また、内部データ・バスDBSおよびデータ入出力回路DIOを介して、チップ外部に出力される。
【００３６】
同図では、また、内部データ・バスDBSを介して制御信号を受信するレジスタとして、インストラクション・レジスタISREG、インフォメーション・レジスタIFREG、コンフィガレーション・レジスタCFREG、情報識別レジスタDIREGの四つが示されている。第一のインストラクション・レジスタISREGは、内部データ・バスDBSを介して入力された制御信号を記憶して、チップの初期化方法、縦続接続されたＣＡＭのチップ数、チップ内部のテーブル構成を定義する。ここで、テーブル構成とは、エントリの数およびその情報量に応じた論理的なメモリアレイ構成のことである。例えば、メモリアレイMAAおよびMABのデータ幅がそれぞれ７２ビット、かつエントリの情報量が７２ビット（＝ｋ＋１ビット、ｋ＝７１。（ｋ＋１）はデータ・バス幅を示す。）の場合、エントリはメモリアレイMAAまたはMABに入力される。
【００３７】
この際、第一のインストラクション・レジスタISREGは、二つのメモリアレイを通して連続したロウ・アドレスが割り振られるような値に設定される。したがって、二つのメモリアレイMAAおよびMABにより、７２ビット幅かつワード数が２倍のメモリアレイとなるように内部回路が設定され、異なるデコード信号が前述のメイン・ワード線群MWLBA、MWLBBを介して入力される。さらに別の例では、メモリアレイMAAおよびMABのデータ幅がそれぞれ７２ビット、かつ図２４に示したようにエントリの情報量が１４４ビット（＝２×（ｋ＋１）ビット、ｋ＝７１。（ｋ＋１）はデータ・バス幅を示す。）の場合、エントリは７２ビット（＝（ｋ＋１）ビット、ｋ＝７１。）に分割された後で符号化されて、メモリアレイMAAおよびMABにそれぞれ入力される。この際、第一のインストラクション・レジスタISREGは、双方のメモリアレイに共通のロウ・アドレスが割り振られるような値に設定される。
【００３８】
したがって、二つのメモリアレイMAAおよびMABで１４４ビット幅のメモリアレイとなるように内部回路が設定され、同じデコード信号が前述のメイン・ワード線群MWLBA、MWLBBを介して入力される。第二のインフォメーション・レジスタIFREGは、ルータなどのシステム上に割り当てられたチップ固有のデバイス番号を記憶する。第三のコンフィガレーション・レジスタCFREGは、例えば、前述したように論理的に分割されたメモリアレイMAA、MABの活性化を制御するための信号などを記憶する。第四の情報識別レジスタDIREGは、本実施例によるＣＡＭが処理する情報の形式を区別する識別情報を格納する。すなわち、当該ビットで処理する領域の情報に応じて、図２や図３に示した４値情報のマッピングに従った符号化および復号を行うか、３値情報のマッピングに従った符号化および復号を行うかを示す情報を記憶する。
【００３９】
このレジスタ設定値は、符号化ブロック単位で識別情報バスDIBSを介して後述する符号化回路および復号回路に入力される。なお、符号化回路および復号回路は、符号化ブロックの２ビット単位で切り換えるので、識別情報バスDIBSのバス幅は（ｋ＋１）／２ビットである。また、これまで述べた四つのレジスタの値は、チップの電源投入時や動作モードの切り替わりに応じて所望の値に設定される。
【００４０】
さらに、図１では、内部データ・バスDBSを介してデータを受信するためのレジスタとして、コンパランド・レジスタCPREGと第一サイクル・データ・レジスタFDREG、第二サイクル・データ・レジスタSDREGの三つが示されている。第一のコンパランド・レジスタCPREGは、検索動作で入力された検索キー（または比較情報）を記憶する。ここで記憶された検索キーは、検索動作で一致するエントリがなかった場合に、後述の符号化回路を介してメモリアレイMAAおよびMABへ書き込まれる。第二の第一サイクル・データ・レジスタFDREGは、図２や図３に示した差やマスクを一時的に格納し、第一サイクル・データ・バスFDBSを介して後述の符号化回路に転送する。
【００４１】
第三の第二サイクル・データ・レジスタSDREGは、メモリアレイMAA、MABから読み出したエントリから後述の復号回路および第二サイクル・データ・バスSDBS[k:0]を介して得られた情報のうち、図２や図３に示した差およびマスクを一時的に格納し、内部データ・バスDBSを介してデータ入出力回路DIOに転送する。
図１では、これらの他に、後述するマッチ・アドレス・バスMABSと内部データ・バスDBSとの間に挿入されたマッチ・アドレス・レジスタMAREGがそれぞれ示されている。なお、以上で述べた各種レジスタは、適宜同じ構成と仕様の複数のレジスタ群でそれぞれ構成されており、後述のコマンド信号群やアドレス信号によって所望のレジスタが選択される。
【００４２】
ＣＡＭ制御回路CAMCTLは、チップ外部から入力されたクロック・モード信号CLK_MODE、マスタ・クロックMCLK、位相信号PHS_L、コマンド・バリッド信号CMDV、複数（ここでは（ｎ＋1）本）の信号からなる外部コマンド信号群CMDなどに応じて発生した内部制御信号を内部コマンド・バスCBSなどに出力し、かつリード・アクノーリッジ信号ACKなどをチップ外部に出力する。クロック・モード信号CLK_MODEは、マスタ・クロックMCLKの周波数を選択するための信号である。マスタ・クロックMCLKは２種類の周波数を採ることが可能であり、例えばクロック・モード信号CLK_MODEがハイ・レベルの時、位相信号PHS_Lの倍の周期のクロックを受信する。
【００４３】
これとは逆に、クロック・モード信号CLK_MODEがロウ・レベルの時、位相信号PHS_Lと同じ周期のクロックを受信する。コマンド・バリッド信号CMDVは、外部コマンド信号群CMDの有効性を示す。外部コマンド信号群CMDは前述したＣＡＭ制御デバイスで発生された信号であり、ＣＡＭ制御回路CAMCTLを介して発生された内部コマンド・バスCBS上の信号に応じて、ＣＡＭの動作状態が規定されたり、前述の各種レジスタの中から動作に応じたレジスタが選択されたりする。例えば、CMD[1:0]=00（ｎ≧１）の時は読み出し動作、CMD[1:0]=01の時は書き込み動作、CMD[1:0]=10の時は検索動作、CMD[1:0]=11の時はエントリ更新動作のようにＣＡＭの動作が規定される。リード・アクノーリッジ信号ACKは、読み出し動作中に読み出しデータに同期して出力されるストローブ信号である。
リフレッシュ・カウンタRFCNTは、リフレッシュ動作に応じてロウ・アドレスを発生する。このアドレスは、ロウ・アドレス・バスXBSを介してロウ・デコーダXDECに入力される。
【００４４】
符号化回路ENCDRは、前述したように第一サイクル・データ・レジスタFDREGから第一サイクル・データ・バスFDBSを介して得た情報（ここでは差およびマスク）と、内部データ・バスDBSを介して入力された情報（ここでは最小値およびデータ）を受信して、エントリまたは検索キーをOne-hot-spotブロック符号化する。ここで、２ビット単位で符号化を行う場合、２×（ｋ＋１）ビットの符号化信号が、符号化データ・バスENBSを介してメモリアレイMAA、MABにそれぞれ入力される。
【００４５】
復号回路DCDRは、メモリアレイMAA、MABから読み出されたエントリを符号化データ・バスENBSを介して受信し、図２に示したように最小値と差の対やデータとマスクの対に変換する。そして、一方の最小値およびデータを内部データ・バスDBSを介してデータ入出力回路DIO、他方の差およびマスクを復号データ・バスDCBS[k:0]を介して前述の第二サイクル・データ・レジスタSDREGにそれぞれ転送する。
【００４６】
プライオリティ・エンコーダPENCは検索動作において、図２３の一致信号HIT0などで構成される一致信号バスHBSA、HBSBから入力された信号に応じて、検索キーと一致したエントリに対応するアドレス信号を発生する。なお、一致したエントリが複数あった場合、最上位（例えば、対応するロウ・アドレスが最も小さい番号の行）のエントリに応じたアドレス信号から順に出力する機能を有する。発生されたアドレス信号は、マッチ・アドレス・バスMABSを介して前述のマッチ・アドレス・レジスタMAREGに入力される。
【００４７】
ＲＡＭ制御回路RAMCTLは、マッチ・アドレス・バスMABSを介して受信したコンテント・アドレスなどを、ＤＲＡＭ（ダイナミック・ランダム・アクセス・メモリ）やＳＲＡＭ（スタティック・ランダム・アクセス・メモリ）に出力する。同図では、一例として、コンテント・アドレスがコンテント・アドレス信号群CADD[S:0]を介してチップ外部に出力される構成が示されている。ここで、sは、本実施例によるＣＡＭのメモリアレイ構成に応じて決まる整数である。
【００４８】
なお、本実施例によるＣＡＭを形成する構成要素は、図１に記載の回路ブロックや信号に限らず、様々な要素ブロックや信号が含まれる。例えば、内部クロックの位相調整用のフェーズ・ロックド・ループＰＬＬやディレイ・ロックド・ループＤＬＬ、テスト回路、カスケード接続したチップを制御するコントローラ、外付けのコンテント・メモリを制御するＲＡＭ用クロック、ＲＡＭ制御信号群などが図１では簡単のために省略されている。
【００４９】
図４は、図１におけるデータの送受信に関係する構成要素について、説明を簡単にするために、代表として符号化ブロック単位である２ビット分の回路ブロック構成を示している。以下に示す記号の添え字‘j’は、０、１、…、(ｋ―１)／２のいずれかである（‘ｋ’は奇数）。同図では、各種レジスタ群REGBの構成要素として、情報識別レジスタ要素ブロックDIREGEj、第一サイクル・データ・レジスタ要素ブロックFDREGEj、第二サイクル・データ・レジスタ要素ブロックSDREGEjが示されている。これらのレジスタの設定は、内部データ・バスの構成要素である内部データ線DL2j、DL(2j+1)を介して行われる。なお、情報識別レジスタ要素ブロックDIREGEjは複数のレジスタ群で構成され、レジスタの値は所望の値に設定可能である。また、図４では省略されている内部コマンド・バスCBSの信号に応じたレジスタが選択されることは、図１で説明した通りである。
【００５０】
符号化回路ENCDRは、４値符号化回路要素ブロックQENCEj、３値符号化回路要素ブロックTENCEj、第一スイッチ群FTSWBj、第二スイッチ群SSWBjで構成される。４値符号化回路要素ブロックQENCEjは、図２および図３に示したＩＰアドレス領域などの符号化に用いられる。また、３値符号化回路要素ブロックTENCEjは、フラグ領域などの符号化に用いられる。第一スイッチ群FTSWBjは４つの二股スイッチで構成され、情報識別レジスタ要素ブロックDIREGEjの出力信号、すなわち識別情報バスDIBS[(k-1)/2:0]の構成要素である情報識別線DILjの電圧レベルに応じて、内部データ線DL2jおよびDL(2j+1)と第一サイクル・データ・レジスタ要素ブロックFDREGEjの出力信号線すなわち、第一サイクル・データ・バスFDBS[k:0]の構成要素である第一サイクル・データ線FDL2j、FDL(2j+1)を、４値符号化回路要素ブロックQENCEjまたは３値符号化回路要素ブロックTENCEjのいずれかに接続する。
【００５１】
例えば、当該要素ブロックにおいてＩＰアドレス領域の中の２ビットを符号化する場合、情報識別レジスタ要素ブロックDIREGEjの値を‘11’に設定して情報識別線DILjをハイ・レベルとすることにより、内部データ線DL2j、DL(2j+1)と第一サイクル・データ・レジスタ要素ブロックFDREGEjの出力信号線である第一サイクル・データ線FDL2j、FDL(2j+1)を４値符号化回路要素ブロックQENCEjにそれぞれ接続する。あるいは、当該要素ブロックにおいてフラグ領域の２ビットの符号化を行う場合、情報識別レジスタ要素ブロックDIREGEjの値を‘00’に設定して情報識別線DILjをロウ・レベルとすることにより、内部データ線DL2j、DL(2j+1)と第一サイクル・データ・レジスタ要素ブロックFDREGEjの出力信号線である第一サイクル・データ線FDL2j、FDL(2j+1)を３値符号化回路要素ブロックTENCEjにそれぞれ接続する。第二スイッチ群SSWjも同様に４つの二股スイッチで構成され、情報識別レジスタ要素ブロックDIREGEjの出力信号である情報識別線DILjに応じて、符号化データ・バスENBSの構成要素である符号化データ線ENLj0〜ENLj3を、４値符号化回路要素ブロックQENCEjまたは３値符号化回路要素ブロックTENCEjにそれぞれ接続する。
【００５２】
復号回路DCDRは、４値復号回路要素ブロックQDCEj、３値復号回路要素ブロックTDCEj、第三スイッチ群TSWBj、第四スイッチ群FRSWBjで構成される。４値復号回路要素ブロックQDCEjは、図２に示したＩＰアドレス領域の復号に用いられる。また、３値復号回路要素ブロックTDCEjは、フラグ領域などの復号に用いられる。第三スイッチ・ブロックTSWjは４つの二股スイッチで構成され、情報識別レジスタ要素ブロックDIREGEjの出力信号である情報識別線DILｊに応じて、符号化データ線ENLj0〜ENLj3を４値復号回路要素ブロックQDCEjまたは３値復号回路要素ブロックTDCEjにそれぞれ接続する。
【００５３】
例えば、当該要素ブロックにおいてＩＰアドレス領域の中の２ビットの復号を行う場合、情報識別レジスタ要素ブロックDIREGEjの値を‘11’に設定して情報識別線DILjをハイ・レベルとすることにより、符号化データ・バスENBSの構成要素である符号化データ線ENLj0〜ENLj3を、４値復号回路要素ブロックQDCEjにそれぞれ接続する。あるいは、当該要素ブロックにおいてフラグ領域の２ビットの復号を行う場合、情報識別レジスタ要素ブロックDIREGEjの値を‘00’に設定して情報識別線DILjをロウ・レベルとすることにより、符号化データ・バスENBSの構成要素である符号化データ線ENLj0〜ENLj3を、３値復号回路要素ブロックTDCEjにそれぞれ接続する。第四スイッチ群FRSWjも同様に４つの二股スイッチで構成され、情報識別レジスタ要素ブロックDIREGEjの出力信号である情報識別線DILjに応じて、内部データ線DL2j、DL(2j+1)と第二サイクル・データ・レジスタ要素ブロックSDREGEjの入力信号線、すなわち第二サイクル・データ・バスSDBS[k:0]の構成要素である第二サイクル・データ線SDL2j、SDL(2j+1)を４値復号回路要素ブロックQDCEjまたは３値復号回路要素ブロックTDCEjにそれぞれ接続する。
【００５４】
なお、同図では、上記の第一スイッチ群から第四スイッチ群は、簡単のために二股スイッチで構成される例が示されているが、実際には公知のMOSトランジスタで同様の機能を実現するように形成されている。
【００５５】
次に、以上で説明したＣＡＭのフロア・プランを説明する。図５は、エントリおよび検索キーの送受信経路に注目したフロア・プランの例を示している。同図で、メモリアレイ群ARY0〜ARY3はメモリアレイ群ARY0に示しているように、図１のメモリアレイMAA、MABでそれぞれ構成される。メモリアレイMAA、MABはメモリアレイ群ARY1に示しているように、図２２あるいは図２３で示したワード線WLと複数のビット線（ここでは四本のビット線BL0〜BL3）の交点に配置されたメモリブロックMB、ワード線WLを駆動するワード・ドライバWD、対応するビット線BL0〜BL3をそれぞれ駆動する読み書き回路RW0〜RW3、対応するビット線BL0〜BL3にそれぞれ平行に配置されたサーチ線SL0〜SL3、対応するサーチ線SL0〜SL3を駆動するサーチ・ドライバSD0〜SD3、メモリブロックにおける比較動作に応じた信号が発生されるサブマッチ線SML、ワード線WLに平行に配置されたメインマッチ線MML、サブマッチ線に発生された信号を分別して、その結果に応じてメインマッチ線を駆動するサブマッチ判定回路SMD、メインマッチ線MMLに発生された信号を弁別するメインマッチ判定回路MMDなどで構成される。
【００５６】
また、DIOは入出力回路であり、チップ外部との情報の授受を行う。各種レジスタ群REGBの値は、内部データ・バスDBSを介して設定されたり読み出されたりする。なお、図５では、説明を簡単にするために、各種レジスタ群とＣＡＭ内部ブロックとの結線を省略しているが、これまでの説明から関連する回路ブロック通しが接続されていることは容易に理解することができる。チップ内部に入力された情報（ここではエントリおよび検索キー）は、前述のように内部データ・バスDBSから符号化回路ENCDRを介してOne-hot-block符号に変換され、符号化データ・バスENBSを介して各メモリアレイ群ARY0〜ARY3に転送される。これとは反対に、各メモリアレイ群ARY0〜ARY3から読み出された情報（ここではエントリ）は、符号化データ・バスENBSから復号回路DCDRを介して最小値およびデータと差およびマスクに変換されて、内部データ・バスDBSから入出力回路を介してチップ外部に出力される。
【００５７】
また、メモリアレイARY0,1の間及びメモリアレイARY2,3の間には、内部電圧発生回路VGERやPLL回路PLL等の周辺回路PERIが配置され、メモリアレイARY0,2の間及びARY1,3の間には符号化データ・バスENBSや入出力回路DIOが配置される。このようにメモリアレイ群ARY0〜ARY3の夫々は、夫々の間に周辺回路PERIや入出力回路DIOが配置される十字型領域により分けられる。ここで、各種レジスタ群REGBや符号化回路ENCDR、複合回路DCDRを十字型領域の交差領域に設けている。
【００５８】
以上のように、本フロア・プランによるＣＡＭは、各種レジスタ群REGBや符号化回路ENCDR、復号回路DCDRを複数のメモリアレイ群で共有することにより、チップ面積を抑制することができる。また、メモリアレイ群を十字型領域により分け、その交差領域に複数のメモリアレイ群で共有している回路を設けることにより、信号線の遅延時間等がほぼ等しくすることが可能となる。次に、以上のような構成によるＣＡＭの動作について説明する。
【００５９】
《書き込み動作》
図６は、本実施例におけるＣＡＭの書き込み動作のタイミングチャートを示している。同図では、マスタ・クロックMCLKの周波数が位相信号PHS_Lの倍の例が示されているが、以下の動作説明においては、位相信号PHS_Lに合わせてサイクル数を数えることにする。同図の動作は、２（ｋ＋１）ビットのエントリをＣＡＭに登録すると仮定した場合、このエントリの半分の領域を図１に示したメモリアレイMAA、MABのいずれか一方に書き込む動作に相当する。この動作の特徴は、差およびマスクを第一サイクル・データ・レジスタに書き込む動作と、最小値およびデータを先に入力した差およびマスクに応じて符号化してメモリアレイに書き込む動作をそれぞれ３サイクルかけて行う点にある。なお、図１に示した情報識別レジスタは、これから処理する情報の形式に応じた値に予め設定されているものとする。
【００６０】
まず、以下の手順に従い、差およびマスクを第一サイクル・データ・レジスタに入力する。
１サイクル目の前半（１Ａサイクル）：ロウ・レベルとなっているコマンド・バリッド信号CMDVをハイ・レベルに駆動すると同時に、コマンド信号群CMD[1:0]を用いてライト・コマンドを入力する。また、コマンド信号群CMD[n:2]を所望の値に設定して、図１に示した各種レジスタ群REGBの中から第一サイクル・データ・レジスタFDREGを選択したり、本実施例のＣＡＭと共に使用される外付けのコンテント・メモリのアドレスの一部を入力したりする。さらに、データ・バスDQ[k:0]を介して、第一サイクル・データ・レジスタFDREGの中から所望のレジスタを選択するためのアドレスREG-ADDを入力する。
【００６１】
１サイクル目の後半（１Ｂサイクル）：１Ａサイクルから引き続いてライト・コマンドの入力と、第一サイクル・データ・レジスタFDREGの選択を行う。
２サイクル目：ハイ・レベルとなっているコマンド・バリッド信号CMDVをロウ・レベルに駆動すると同時に、データ・バスDQ[k:0]を介して差およびマスクを入力する。これらの情報は、１サイクル目に選択した第一サイクル・データ・レジスタFDREGに書き込まれる。
３サイクル目：待機状態である。ＣＡＭ内部では、このサイクルの終わりまでに、第一サイクル・データ・レジスタFDREGへの書き込み動作を終了する。
【００６２】
次に、以下の手順に従い、最小値およびデータを入力する。
４サイクル目の前半（４Ａサイクル）：ロウ・レベルとなっているコマンド・バリッド信号CMDVをハイ・レベルに駆動すると同時に、コマンド信号群CMD[1:0]を用いてライト・コマンドを入力する。また、コマンド信号群CMD[n:2]を所望の値に設定して、２サイクル目に差およびマスクを書き込んだ第一サイクル・データ・レジスタや、これから入力する情報の形式に応じた値に設定された情報識別レジスタDIREGを選択したり、本実施例のＣＡＭと共に使用される外付けのコンテント・メモリのアドレスの一部を入力したりする。さらに、データ・バスDQ[k:0]を介して、エントリを書き込むワードを選択するためのロウ・アドレスX-ADDを入力する。このロウ・アドレスは、図１に示すロウ・デコーダXDECでデコードされて、以降、書き込み先のワード線が活性化される。
【００６３】
４サイクル目の後半（４Ｂサイクル）：４Ａサイクルから引き続いてライト・コマンドを入力する。
５サイクル目：データ・バスDQ[k:0]を介して最小値およびデータを入力する。これらの情報は、２サイクル目に入力した差およびマスクと共に情報識別レジスタDIREGで選択された符号化回路により対応するOne-hot-spotブロック符号に変換され、メモリアレイに転送される。
６サイクル目：待機状態である。このサイクルの終わりまでに、メモリアレイへの書き込み動作を終了する。
なお、図１の各種レジスタの設定は、図６の１サイクル〜３サイクルの動作に準じた手順で行われる。また、メモリセルの初期化は、図２の４値情報における最小値：‘11’、差：‘11’を入力することにより行われる。
【００６４】
《読み出し動作》
図７は、本実施例におけるＣＡＭの読み出し動作のタイミングチャートを示している。便宜上、図面を（Ａ）と（Ｂ）に分けているが、（Ａ）と（Ｂ）は、連続するサイクルである。同図では、マスタ・クロックMCLKの周波数が位相信号PHS_Lの倍の例が示されているが、以下の動作説明においては、位相信号PHS_Lに合わせてサイクル数を数えることにする。同図の動作は、２（ｋ＋１）ビットのエントリがＣＡＭに登録されていると仮定した場合、このエントリの半分の領域を図１に示したメモリアレイMAA、MABのいずれか一方から読み出す動作に相当する。この特徴は、メモリアレイから読み出したエントリを復号してから、一旦、差およびマスクを第二サイクル・データ・レジスタに格納しつつ最小値およびデータを出力し、その後にアドレスを入れ直して、差およびマスクを出力する点にある。なお、図１に示した情報識別レジスタは、これから処理する情報の形式に応じた値に予め設定されているものとする。
【００６５】
１サイクル目の前半（１Ａサイクル）：ロウ・レベルとなっているコマンド・バリッド信号CMDVをハイ・レベルに駆動すると同時に、コマンド信号群CMD[1:0]を用いてリード・コマンドを入力する。また、コマンド信号群CMD[n:2]を所望の値に設定して、図１に示した各種レジスタ群REGBの中から第二サイクル・データ・レジスタSDREGや、これから読み出す情報の形式に応じた値に設定された情報識別レジスタDIREGを選択したり、本実施例と共に使用される外付けのコンテント・メモリのアドレスの一部を入力したりする。さらに、データ・バスDQ[k:0]を介して、エントリを読み出すワードを選択するためのロウ・アドレスX-ADDを入力する。このロウ・アドレスは、図１に示すロウ・デコーダXDECでデコードされる。以降、ワード線が活性化されて、メモリセルからOne-hot-spotブロック符号化されたエントリが読み出され、復号回路で最小値およびデータと差およびマスクに変換される。
【００６６】
１サイクル目の後半（１Ｂサイクル）：１Ａサイクルから引き続いてリード・コマンドの入力や、第二サイクル・データ・レジスタSDREGの選択を続ける。
２サイクル目：ハイ・レベルとなっているコマンド・バリッド信号CMDVをロウ・レベルに駆動すると同時に、データ・バスDQ[k:0]を介して、第二サイクル・データ・レジスタの中から所望のレジスタを選択するためのレジスタ・アドレスREG-ADDを入力する。この結果、復号回路で発生された差およびマスクを、第二サイクル・データ・レジスタに書き込むことが可能となる。
【００６７】
３サイクル目：待機状態である。ＣＡＭ内部では、上述の読み出し動作および復号動作が引き続き行われている。
４サイクル目：ハイ・インピーダンス状態となっているリード・アクノーリッジ信号ACKをロウ・レベルに駆動して、データ・バスDQをバリッド状態とする。この後、データ・バスDQ[k:0]に最小値およびデータが出力し始める。
５サイクル目：ロウ・レベルとなっているリード・アクノーリッジ信号ACKをハイ・レベルに駆動する。この時、データ・バスDQには、読み出し情報が出力されている。
【００６８】
６サイクル目：ハイ・レベルとなっているリード・アクノーリッジ信号ACKをロウ・レベルに駆動する。
７サイクル目の前半（７Ａサイクル）：ロウ・レベルとなっているリード・アクノーリッジ信号ACKをハイ・インピーダンス状態にする。続いて、１Ａサイクルと同様に、ロウ・レベルとなっているコマンド・バリッド信号CMDVをハイ・レベルに駆動すると同時に、コマンド信号群CMD[1:0]を用いてリード・コマンドを入力する。また、コマンド信号群CMD[n:2]を所望の値に設定して、図１に示した各種レジスタ群REGBの中から第二サイクル・データ・レジスタSDREGや、これから読み出す情報の形式に応じた値に設定された情報識別レジスタDIREGを選択したり、本実施例と共に使用される外付けのコンテント・メモリのアドレスの一部を入力したりする。さらに、データ・バスDQ[k:0]を介して、第二サイクル・データ・レジスタの中から所望のレジスタを選択するためのレジスタ・アドレスREG-ADDを入力する。
【００６９】
７サイクル目の後半（７Ｂサイクル）：７Ａサイクルから引き続いてリード・コマンドの入力や、第二サイクル・データ・レジスタSDREGの選択を続ける。
８〜９サイクル目：ハイ・レベルとなっているコマンド・バリッド信号CMDVをロウ・レベルに駆動する。ＣＡＭ内部では、第二サイクル・データ・レジスタSDREGからの読み出し動作が行われている。
【００７０】
１０サイクル目：ハイ・インピーダンス状態となっているリード・アクノーリッジ信号ACKをロウ・レベルに駆動して、データ・バスDQをバリッド状態とする。この後、データ・バスDQ[k:0]に差およびマスクが出力し始める。
１１サイクル目：ロウ・レベルとなっているリード・アクノーリッジ信号ACKをハイ・レベルに駆動する。この時、データ・バスDQには、差およびマスクが出力されている。
１２サイクル目：ハイ・レベルとなっているリード・アクノーリッジ信号ACKをロウ・レベルに駆動する。
１３サイクル目：ロウ・レベルとなっているリード・アクノーリッジ信号ACKをハイ・インピーダンス状態にして、待機状態に復帰する。
【００７１】
以上の動作では、符号化されたエントリをメモリアレイから１２サイクルかけて読み出す動作を説明してきた。しかし、図１の各種レジスタ群REGBに設定された値を読み出す際は、第二サイクル・データ・レジスタSDREGからの差およびマスクを読み出しと同じように、動作が行われることは容易に理解できる。このような動作により、メモリアレイからもレジスタからも６サイクル数で読み出し動作を行うことができ、本実施例によるＣＡＭの制御が容易となる。
【００７２】
なお、メモリアレイからエントリの読み出しは、図７のタイミングチャートに示した動作に限らず、種々の変形が可能である。例えば、図８に示すように、最小値およびデータを読み出した後に６サイクル目で差およびマスクを読み出す動作も可能である。この場合、読み出しサイクルを１２サイクルから６サイクルに半減することができ、検索動作禁止期間を短縮することができる。また、図１の各種レジスタ群REGBに設定された値を読み出す際は、１サイクル目にロウ・アドレスX‐ADDとしてメモリセルへのアクセスを行わないような値に設定されたデフォルト値を入力する。これに応じて、図１に記載のＣＡＭは、５サイクル目に最小値およびデータとして、記憶情報を意味しない別のデフォルト値を出力し、さらに６サイクル目に差およびマスクに変わるレジスタの値を出力する。このような動作により、図７と同じように、各種レジスタ群REGBからも６サイクル数で読み出し動作を行うことができる。
【００７３】
《検索動作》
図９は、本実施例におけるＣＡＭの検索動作のタイミングチャートを示している。同図では、マスタ・クロックMCLKの周波数が位相信号PHS_Lの倍の例が示されているが、以下の動作説明においては、位相信号PHS_Lに合わせてサイクル数を数えることにする。同図の動作は、２（ｋ＋１）ビットのエントリがＣＡＭに登録されていると仮定した場合、四つの検索キーを連続して比較する動作に相当する。この特徴は、書き込み動作と異なり最小値およびデータのみを入力し、予め図１の第一サイクル・データ・レジスタFDREGに設定していた差およびマスクをコマンド信号群により選択して符号化を行い、メモリアレイに入力する点にある。なお、図１に示した情報識別レジスタは、これから処理する情報の形式に応じた値に予め設定されているものとする。
【００７４】
１サイクル目の前半（１Ａサイクル）：ロウ・レベルとなっているコマンド・バリッド信号CMDVをハイ・レベルに駆動すると同時に、コマンド信号群CMD[1:0]を用いてサーチ・コマンドを入力する。また、コマンド信号群CMD[n:2]を所望の値に設定して、図１に示した各種レジスタ群REGBの中から所望の第一サイクル・データ・レジスタFDREGや、これから検索する情報の形式に応じた値に設定された情報識別レジスタDIREGを選択したり、検索キーおよびエントリのデータ長を示すフラグ信号を入力したりする。さらに、データ・バスDQ[k:0]を介して、２（ｋ＋１）ビットの第一の検索キーの前半ビットＤ１を入力する。この検索キーは符号化された後、例えば図１のメモリアレイMAAに入力されて比較動作が行われる。
【００７５】
１サイクル目の後半（１Ｂサイクル）：１Ａサイクルから引き続いてサーチ・コマンドを入力したり、図１のコンパランド・レジスタCPREGやマッチ・アドレス・レジスタMAREGを選択するようなデータ・パターンを外部コマンド群CMD[n:2]を介して入力したりする。また、データ・バスDQ[k:0]を介して、２（ｋ＋１）ビットの第一の検索キーの後半ビットＤ２を入力する。この検索キーは符号化された後、例えば図１のメモリアレイMABに入力されて比較動作が行われる。
２サイクルから４サイクル：１サイクル目と同じ動作を繰り返し、第二から第四の検索キーを１サイクルおきに二つに分けてそれぞれ入力する。以降、これらの検索キーは、前述のコンパランド・レジスタ、マッチ・アドレスがマッチ・アドレス・レジスタにそれぞれ適宜格納されつつ、パイプライン動作により順次比較動作が行われ、一致アドレスが検出される。
【００７６】
５サイクル目：ハイ・レベルとなっているコマンド・バリッド信号CMDVをロウ・レベルに駆動して、検索キーの受信を終える。また、第一の検索キーによる比較結果に応じたコンテント・メモリ用アドレスＡ１が出力される。
６サイクルから８サイクル：第二から第四の検索キーによる比較結果に応じたコンテント・メモリ用アドレスＡ２からＡ４が、コンテント・アドレス・バスCADR[s:0]から１サイクルおきに順次出力される。
【００７７】
以上の構成と動作により、図１および図４に示したＣＡＭは、次の二つの効果を得る。第一に、内部データ・バスDBSにおいて、符号化ブロック数単位（ここでは２ビット単位）に二種類の符号化回路（ここでは４値情報の符号化回路と３値情報の符号化回路）を備えることにより、回路面積を抑制しながら、様々な構成のエントリもしくは検索キー応じた符号化を行うことが可能となる。すなわち、ＩＰアドレス領域においては、４値情報の符号化回路を用いることにより、少ないエントリ数で範囲指定されたＩＰアドレスを記憶することが可能となる。
【００７８】
また、フラグ領域においては、３値情報の符号化回路を用いることにより、一つのメモリブロックに二つのフラグ信号を記憶することが可能となる。すなわち、効率良くエントリを記憶することが可能となる。第二に、エントリおよび検索キー内の領域の割り付けを覚える情報識別レジスタDIREGを複数備え、外部コマンド信号群CMDを用いて動作に応じて所望のレジスタを選択することにより、様々な構成のエントリおよび検索キーに対応することが可能となる。すなわち、ＣＡＭが処理する情報の汎用性とユーザーの可用性を同時に向上することが可能となる。
以下では、これまで述べたＣＡＭの使われ方をネットワーク・ルータへの適用を例に説明する。
【００７９】
《ネットワーク・ルータへの適用》
図１０は、本発明によるＣＡＭを適用したネットワーク・ルータNRの構成例を示している。同図では、説明を簡単にするために、要部ブロックとしてルータ・マネージャ群RMB、クロスバ・スイッチ群CBSWB、パケット・プロセッサ・ユニットPPU0〜PPUyが示されている。ルータ・マネージャ群RMBは複数の中央演算処理装置（ＣＰＵ）で構成され、ネットワーク・ルータ全体の設定、制御を行う。クロスバ・スイッチ群CBSWBは、処理するパケットの転送経路に応じて所望のパケット・プロセッサ・ユニット同士を接続する。パケット・プロセッサ・ユニットPPU0〜PPUyは、対応するネットワークIPN0〜IPNyとの間でパケットの授受をそれぞれ行うブロックである。
【００８０】
なお、130は、本ネットワーク・ルータが処理するパケットPCTを模式的に示している。パケットPCTは、二つの領域に大別される。一方の140はヘッダ領域HDR、他方の131はペイロード領域PYLDである。ヘッダ領域HDRは、さらに、図１１に示すような複数（ここでは三つ）の領域で構成される。141は第２層のヘッダL2HDRであり、送信元ＭＡＣアドレス（Source address Media Access Control）や宛先ＭＡＣアドレス（Destination address Media Access Control）などを有する。142は第３層のヘッダL3HDRであり、送信元ＩＰアドレス（Source IP address）や宛先ＩＰアドレス（Destination IP address）などを有する。143は、第４層のヘッダL4HDRであり、プロトコルすなわち上位アプリケーションを表す送信元ポート（Source port）や宛先ポート（Destination port）などを有する。ペイロード領域PYLDは、電子メールの本文やテキスト・ファイルなどの送信者が指定した情報などを有する。なお、同図に示された矢印132はパケットPCTの転送経路、矢印133はヘッダ領域の転送経路である。以下では、これらの経路に注目しながら、パケット・プロセッサ・ユニットPPU0〜PPUyの詳細な構成を説明する。
【００８１】
パケット・プロセッサ・ユニットPPU0〜PPUyの各々は、ネットワーク・インタフェイスNIF、パケット・フォワーディング・プロセッサPFP、検索エンジンSE、本実施例によるコンテント・アドレッサブル・メモリCAM、ＤＲＡＭなどが用いられるコンテント・メモリCM、パケット・プロセッサ・ユニット用中央演算処理装置PPUPなどで構成される。ネットワーク・インタフェイスNIFとパケット・フォワーディング・プロセッサPFPは、システム・バスSBSで接続されている。パケット・フォワーディング・プロセッサPFPと検索エンジンSEは、内部バスIBSで接続されている。検索エンジンSEとコンテント・アドレッサブル・メモリCAMはデータ・バスDQ、検索エンジンSEとコンテント・メモリCMはコンテント・データ・バスCBSでそれぞれ接続されている。コンテント・アドレッサブル・メモリCAMとコンテント・メモリCMは、コンテント・アドレス・バスCADDでそれぞれ接続されている。
【００８２】
ルータNRは、例えばインターネット網IPN0とパケット・プロセッシング・ユニットPPU0との間で、ネットワーク・インタフェイスNIFを介してパケットPCTの送受信を行う。パケット・フォワーディング・プロセッサPFPは、受信したパケットの内容を解読し、そのペイロード領域PYLDを保持しつつ、ヘッダ領域HDRを検索エンジンSEに転送する。検索エンジンSEは、パケット・プロセッシング・ユニット用中央演算処理装置PPUPを用いてヘッダ領域から所望の情報を抽出して図２４に示すような形式に組み合せ、さらに領域毎に図３に応じた入力情報を発生して検索キーとしてコンテント・アドレッサブル・メモリCAMに転送する。コンテント・アドレッサブル・メモリCAMには、検索キーと同じ形式の情報で構成されたエントリが多数格納されており、検索動作によって一致したエントリに対応するアドレスを発生する。
【００８３】
このアドレスがコンテント・アドレス・バスCADDを介してコンテント・メモリCMに入力されることにより、該当するエントリに関する情報がコンテント・メモリCMから読み出され、検索エンジンSEを介してパケット・フォワーディング・プロセッサPFPに転送される。ここで読み出された情報は、例えば、宛先までの最適な経路情報などが含まれる転送制御情報である。パケット・フォワーディング・プロセッサPFPは、この転送制御情報に基づいてヘッダ領域HDRの内容を書き換え、前述したペイロード領域PYLDと共にパケットPCTを再構築する。そして、このパケットPCTをクロスバ・スイッチ群CBSWBから指定されたパケット・プロセッシング・ユニットを介して、次の中継点であるネットワーク・ルータに接続されたネットワークへ転送する。図１２は、以上で述べた一連のパケット転送処理のフローを示すチャートである。
【００８４】
このようなルータNRの構成において、検索キーは、検索エンジンSEおよびパケット・プロセッサ・ユニット用中央演算処理装置PPUPを用いて発生される。一方、コンテント・アドレッサブル・メモリCAMに記憶さるエントリは、ルータNRの管理者が設定した情報ETRをルータ・マネージャ群RMBもしくはパケット・プロセッサ・ユニット用中央演算処理装置PPUPで解析しながら発生、登録する。以下では、図１３と図１４に従い、範囲指定されたＩＰアドレス領域におけるエントリの発生方法について説明する。
【００８５】
まず、図１３は、エントリ発生方法の概念を示すフロー・チャート示している。このフロー・チャートでは、次の五つの段階を踏む。
第一ステップ：ルータ・マネージャ群RMB（もしくは各パケット・プロセッシング用中央演算処理装置PPUP）が、エントリ定義ファイルを読み込む。
第二ステップ：ルータ・マネージャ群RMB（もしくは各パケット・プロセッシング用中央演算処理装置PPUP）は、定義ファイルに範囲指定されたＩＰアドレスを解析し、ターナリ表記に分解する。そして、全ての領域がターナリ表記されたエントリを一時的に発生する。
第三ステップ：ルータ・マネージャ群RMB（もしくは各パケット・プロセッシング用中央演算処理装置PPUP）は、ターナリ表記のエントリを図２１のマッピングに従ってブロック符号化する。
第四ステップ：ルータ・マネージャ群RMB（もしくは各パケット・プロセッシング用中央演算処理装置PPUP）は、符号化したエントリを圧縮する。
第五ステップ：ルータ・マネージャ群RMB（もしくは各パケット・プロセッシング用中央演算処理装置PPUP）は、圧縮した結果に基づいて、ＩＰアドレス領域については最小値と差（４値情報）、フラグなど他の領域についてはデータとマスク（３値情報）を検索エンジンＳＥからコンテント・アドレッサブル・メモリCAMにそれぞれ送信する。
【００８６】
次に、図１４は、範囲指定されたＩＰアドレスをターナリ表記に分解したことにより複数生成されたエントリの符号化とその圧縮方法についてのフロー・チャートを示している。このアルゴリズムは、図１３のステップ３〜ステップ５に対応している。このアルゴリズムの特徴は、次のように三つある。第一の特徴は、ＣＡＭ内部でハードウェア的に実行するのと比較して、レジスタ・ファイルを多用して、ルータ・マネージャ群RMB（もしくは各パケット・プロセッシング用中央演算処理装置PPUP）上でソフトウェア的に実行する点にある。第二の特徴は、ターナリ表記されたエントリを逐次符号化しながらデータ・パターンを比較し、適宜圧縮する点にある。
【００８７】
第三の特徴は、圧縮した結果発生されたエントリに応じて、ＩＰアドレス領域については最小値と差（４値情報）、フラグなど圧縮をかけない他の領域についてはデータとマスク（３値情報）をＣＡＭへ出力する点にある。ルータ・マネージャ群RMB（もしくは各パケット・プロセッシング用中央演算処理装置PPUP）は、このようなアルゴリズムを実行することにより、ＣＡＭ入力信号を発生しながらエントリ数をカウントすることができる。すなわち、ルータ・マネージャ・ブロックRMBや各パケット・プロセッシング用中央演算処理装置PPUP、検索エンジンSEなどのＣＡＭ制御デバイスは、前述したようにエントリと１対１の関係にある入力情報を発生することにより、ＣＡＭ内のメモリアレイ使用状況を容易に把握することが可能となる。
【００８８】
《本実施例の効果》
最後に、以上で述べたマッピングと、ＣＡＭの構成および動作による効果を、以下にまとめる。
まず、図２および図３のマッピングによる第一の効果は、ＣＡＭの入出力信号とＣＡＭ内部で符号化された信号との間に、１対１の関係を築ける点にある。この結果、ＣＡＭ制御デバイスはエントリ数を正確に把握することができるので、メモリ使用状況などの監視が容易になる。ＩＰアドレス領域に用いられる４値情報の発生方法は、図１３および図１４で説明した通りである。第二の効果は、エントリと検索キーとに対して、共通の入出力信号を用いることが可能となる点にある。この結果、符号化回路および復号回路の共通化が図られ、ＣＡＭのチップ面積を抑制することが可能となる。
【００８９】
次に、図１、図４、図５のＣＡＭの構成と、図６〜図９の動作による第一の効果は、内部データ・バスDBSにおいて、符号化ブロック数単位（ここでは２ビット単位）に二種類の符号化および復号回路（ここでは４値情報の符号化および復号回路と３値情報の符号化および復号回路）を備えることにより、回路面積を抑制しながら、様々な構成のエントリもしくは検索キー応じた符号化および復号を行うことが可能となる点にある。すなわち、フラグ領域のように範囲指定されない１ビットの情報について３値情報の符号化および復号回路を用いることにより、一つのメモリブロックに二つのフラグ信号を効率よく記憶することが可能となる。第二に、エントリおよび検索キー内の領域の割り付けを覚える情報識別レジスタDIREGを複数備え、外部コマンド信号群CMDを用いて動作に応じて所望のレジスタを選択することにより、様々な構成のエントリおよび検索キーに対応することが可能となる。すなわち、ＣＡＭが処理する情報の汎用性とユーザーの可用性を同時に向上することが可能となる。
【００９０】
なお、本実施例は、これまで説明してきた形態に限らず、種々変形が可能である。例えば図２や図３では、ＩＰアドレス領域に用いられる４値情報を最小値と差の組み合せとしてきたが、最大値と差の組み合せとしたマッピングでも同様の効果が得られることは、容易に理解できる。また、フラグ領域に用いられる３値情報において、ロウ・レベルのビットを“Don't care”としてきたが、ハイ・レベルのビットを“Don't care”としたマッピングでも同様の効果が得られることは、容易に理解できる。さらに、２ビット単位で符号化する場合のマッピングを説明したが、符号化単位はこれに限らず、例えば３ビット単位の符号化も可能であることは容易に理解することができる。
【００９１】
図３では、検索キーのＩＰアドレス領域に、図２に基づいた４値情報の符号化マッピングを用いる例を示した。しかし、単独のＩＰアドレスを検索キーとして入力したり、ＩＰアドレス領域にマスクをかけて検索したりするのであれば、符号化された検索キーのデータ・パターンが同じなために、３値情報の符号化マッピングを適用することも可能であり、所望の検索動作を行うことができる。また、詳細は後述するが、パケットのヘッダを解析して検索キーを発生する際に、図１３や図１４で述べた４値情報の符号化アルゴリズムを使わなくて済むので、ＣＡＭ制御デバイスの計算量を減らして電力を抑制するとともに、検索キー発生に要する時間を抑制することも可能となる。
【００９２】
図５では、四つのメモリアレイ群で構成されるＣＡＭを示したが、メモリアレイ群の数はこれに限らず、さらに多くとも良い。この場合、様々な構成のエントリからなる検索テーブルを格納できて、ＣＡＭの可用性および仕様効率を向上することができる。また、同一構成のエントリを複数のメモリアレイ群に跨って記憶することにより、大きな規模の検索テーブルを一つのＣＡＭに格納することができる。
【００９３】
図６では、前半の３サイクルに差およびマスク、後半の３サイクルに最小値およびデータを入力する書き込み動作を説明した。しかし、順番を入れ替えて、前半の３サイクルに最小値およびデータを第一サイクル・データ・レジスタに書き込み、後半の３サイクルに差およびマスクを入力することによりＣＡＭ内部で符号化する動作も可能である。また、書き込み動作は６サイクルに限らず、ＣＡＭ内部回路の動作速度に応じて待機状態（IDLE）が追加されることもあり得る。
【００９４】
同様に、図７では、始めの６サイクルに最小値およびデータ、後の６サイクルに差およびマスクを出力する読み出し動作を説明した。しかし、順番を入れ替えて、始めの６サイクルに最小値およびデータを第二サイクル・データ・レジスタに書き込みながら差およびマスクを直接出力し、後の６サイクルに最小値およびデータを第二サイクル・データ・レジスタから読み出す動作も可能である。また、読み出し動作は１２サイクルに限らず、ＣＡＭ内部回路の動作速度に応じてレイテンシが増減されることもあり得る。図９に関して、検索キーを入力してからコンテント・アドレスが出力されるまでの時間についても同様である。
【００９５】
図１０では、コンテント・アドレッサブル・メモリCAMから出力される一致エントリに応じたアドレスをコンテント・アドレス・バスCADDを介してコンテント・メモリCMに直接入力する構成を示した。しかし、コンテント・アドレス・バスCADDを検索エンジンSEに接続して、検索エンジンSEから新たなバスを介してコンテント・メモリCMに入力することも可能である。このような構成とすることにより、検索エンジンSEの動作を基準にしたタイミング設計が容易になる。
【実施例２】
【００９６】
次に、実施例１で説明したOne-hot-spotブロック符号を適用したＣＡＭの動作の別な例を説明する。この動作の特徴は、ＣＡＭのデータ・バスDQのバス幅が広いことを利用して、ロウ・アドレスX-ADDとレジスタ・アドレスREG-ADDを同時に入力するアドレス信号非多重化方式を適用して、動作時間を短縮している点にある。以下に、書き込み動作と読み出し動作をそれぞれ説明する。
【００９７】
《書き込み動作》
図１５は、本実施例におけるＣＡＭの書き込み動作のタイミングチャートを示している。同図は、図６と同様の仮定に基づいており、共通の記号を用いた波形が示されている。
１サイクル目の前半（１Ａサイクル）：ロウ・レベルとなっているコマンド・バリッド信号CMDVをハイ・レベルに駆動すると同時に、コマンド信号群CMD[1:0]を用いてライト・コマンドを入力する。また、コマンド信号群CMD[n:2]を所望の値に設定して、図１に示した各種レジスタ群REGBの中から第一サイクル・データ・レジスタFDREGや、これから入力する情報の形式に応じた値に設定された情報識別レジスタDIREGを選択したり、本実施例と共に使用されるコンテント・メモリのアドレスの一部を入力したりする。さらに、データ・バスDQ[k:0]を介して、エントリを書き込むワードを選択するためのロウ・アドレスX-ADDと、第一サイクル・データ・レジスタFDREGの中から所望のレジスタを選択するためのアドレスREG-ADDを入力する。ロウ・アドレスは、図１に示すロウ・デコーダXDECでデコードされて、以降、書き込み先のワード線が活性化される。
【００９８】
１サイクル目の後半（１Ｂサイクル）：１Ａサイクルから引き続いてライト・コマンドの入力、第一サイクル・データ・レジスタFDREGや情報識別レジスタDIREGの選択を行う。
２サイクル目：ハイ・レベルとなっているコマンド・バリッド信号CMDVをロウ・レベルに駆動すると同時に、データ・バスDQ[k:0]を介して差およびマスクを入力する。これらの情報は、１サイクル目に選択した第一サイクル・データ・レジスタFDREGに書き込まれる。
３サイクル目：データ・バスDQ[k:0]を介して最小値およびデータを入力する。これらの情報は、２サイクル目に入力した差およびマスクと共に情報識別レジスタDIREGで選択された符号化回路により対応するOne-hot-spotブロック符号に変換され、メモリアレイに転送される。
４サイクル目：待機状態である。このサイクルの終わりまでに、メモリアレイへの書き込み動作を終了する。
このように、アドレス信号非多重方式を適用することにより、書き込み時間を６サイクルから４サイクルに短縮することが可能となる。
【００９９】
《読み出し動作》
図１６は、本実施例におけるＣＡＭの読み出し動作のタイミングチャートを示している。同図は、図６と同様の仮定に基づいており、共通の記号を用いた波形が示されている。
１サイクル目の前半（１Ａサイクル）：ロウ・レベルとなっているコマンド・バリッド信号CMDVをハイ・レベルに駆動すると同時に、コマンド信号群CMD[1:0]を用いてリード・コマンドを入力する。また、コマンド信号群CMD[n:2]を所望の値に設定して、図１に示した各種レジスタ群REGBの中から第二サイクル・データ・レジスタSDREGや、これから読み出す情報の形式に応じた値に設定された情報識別レジスタDIREGを選択したり、本実施例と共に使用されるコンテント・メモリのアドレスの一部を入力したりする。
【０１００】
さらに、データ・バスDQ[k:0]を介して、エントリを読み出すワードを選択するためのロウ・アドレスX-ADDと、第二サイクル・データ・レジスタの中から所望のレジスタを選択するためのレジスタ・アドレスREG-ADDを入力する。ロウ・アドレスは、図１に示すロウ・デコーダXDECでデコードされる。以降、ワード線が活性化されて、メモリセルからエントリが読み出され、復号回路で最小値およびデータと差およびマスクに変換される。
【０１０１】
１サイクル目の後半（１Ｂサイクル）：１Ａサイクルから引き続いてリード・コマンドを入力したり、第二サイクル・データ・レジスタSDREGを選択したりし続ける。
２サイクル目：ハイ・レベルとなっているコマンド・バリッド信号CMDVをロウ・レベルに駆動する。
３サイクル目：コマンド入力禁止の状態である。ＣＡＭ内部では、上述の読み出し動作および復号動作が引き続き行われている。
４サイクル目：ハイ・インピーダンス状態となっているリード・アクノーリッジ信号ACKをロウ・レベルに駆動して、データ・バスDQをバリッド状態とする。この後、データ・バスDQ[k:0]に最小値およびデータが出力し始める。
５サイクル目：ロウ・レベルとなっているリード・アクノーリッジ信号ACKをハイ・レベルに駆動する。この時、データ・バスDQには、最小値およびデータが確実に出力されている。
６サイクル目：ハイ・レベルとなっているリード・アクノーリッジ信号ACKをロウ・レベルに駆動する。データ・バスDQには、第二サイクル・データ・レジスタから差およびマスクが出力される。
７サイクル目：ロウ・レベルとなっているリード・アクノーリッジ信号ACKをハイ・インピーダンス状態に駆動して、待機状態に復帰する。
【０１０２】
このように、アドレス信号非多重方式を適用することにより、読み出し時間を１２サイクルから６サイクルに短縮することが可能となる。
なお、最小値およびデータと差およびマスクを入出力する順番が逆であっても、同様の効果が得られることは容易に理解することができる。また、ＣＡＭ内部回路の動作時間に応じて、レイテンシが調整されるもともあり得るが、総じて実施例１よりも動作時間を短縮できることは容易に理解することができる。
【実施例３】
【０１０３】
次に、実施例１で説明したOne-hot-spotブロック符号を適用したＣＡＭのフロア・プランの別な例を図１７を用いて説明する。この構成の特徴は、メモリアレイ群ARY0〜ARY3毎にインタフェイス回路群IFB0〜IFB3を配して、対応する符号化データ・バスENBS0〜ENBS3を介してメモリアレイ群ARY0〜ARY3との間でエントリや検索キーの送受信を行う点にある。ここで、インタフェイス回路群IFB0〜IFB3は、図５に示したインタフェイス回路群IFBと同様に、符号化回路ENCDR、復号回路DCDR、各種レジスタ群REGBでそれぞれ構成される。従って、図５に示されるフロアプランでは、インタフェイス回路群IFBは、十字型領域の交差領域に配置されたが、本実施例では、周辺回路PERIが配置されない横方向の領域に配置される。このような配置とすることにより、次の二つの効果が得られる。第一の効果は、消費電力を抑制することが可能となる点にある。
【０１０４】
すなわち、本実施例のＣＡＭ内部におけるエントリおよび検索キーのビット長は、符号化したことにより増加する。また、図２や図３のマッピングに示したように複数のビットが活性化されるので、符号化データ・バスの駆動電力が増加する。しかし、符号化データ・バスENBS0〜ENBS3を対応するメモリアレイ群ARY0〜ARY3の近辺に配置することにより、バスの負荷容量が低減されて、駆動電力を抑制することができる。第二の効果は、検索動作速度を向上させることが可能となる点にある。すなわち、図９で説明したように、ＣＡＭ内部はパイプライン処理により検索動作が行われるが、同一の検索キーの異なる領域にマスクをかけることにより、複数のメモリアレイ群毎に様々な検索キーを発生することができる。したがって、これらの検索を並列に行うことにより、検索速度の向上が可能となる。ここで、実施例１による符号化は、同じ規模の検索テーブルを記憶する際に必要なエントリ数を低減するので、複数の検索テーブルを同一チップ内に形成するのに好適である。
【実施例４】
【０１０５】
次に、実施例１で説明したメモリブロックにおけるメモリセルの別な例を説明する。本実施例の目的は、リフレッシュ動作が不要なメモリセル構造とすることにより検索動作禁止時間を排し、ＣＡＭの検索回数を増加することにある。また、キャパシタ形成など特殊な加工工程を排し、ビット単価を低減することにある。
【０１０６】
図１８は、図２３に対応させて、本実施例によるメモリブロックMB00を示している。メモリブロックMB00は、図２３と同様に四つのメモリセルSMC0〜SMC3で構成される。メモリセルにおける構成上の相違点は、メモリセルSMC0に代表されるように、NMOSトランジスタN４１１とキャパシタCが、二つのPMOSトランジスタP211、P212と四つのNMOSトランジスタN211、N212、N213、N214とで構成される公知のＳＲＡＭセルに置き換わっている点にある。クロスカップル接続されたトランジスタP211、P212とNMOSトランジスタN211、N212により正帰還がかかるので、記憶ノードN00TとN00Bは、エントリに応じて電源電圧VCCか接地電圧VSSの何れか一方の電圧レベルに保持される。したがって、図２３のメモリセルのように、エントリのリフレッシュ動作を必要としない。したがって、常時、検索動作が可能となる。
【０１０７】
なお、図１８では、六つのトランジスタで構成されたＳＲＡＭセルに応じて、ビット線BL00T、BL00Bのようにビット線を相補の信号線対としている。しかし、セル構成はこれに限らず、種々の変形が可能である。例えば、PMOSトランジスタとポリシリコン抵抗に置き換えた構成や、クロスカップル接続された四つのMOSトランジスタから何れか一方の極性のMOSトランジスタ対を排した構成が可能である。この場合、トランジスタ数が削減されるので、セル面積を低減することができる。また、トランジスタN214を排して五つのトランジスタで構成したＳＲＡＭセルを適用することも可能である。この場合、負極性のビット線（ここでBL00B〜BL03B）を排除することができるので、配線本数を削減することによりメモリセルのレイアウトを容易にして、セル面積を低減することができる。
【０１０８】
以上、本発明者によってなされた発明を発明の実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。例えば、本発明によるＣＡＭは、オフチップすなわち単体デバイスに限らず、所謂システム・オン・チップ（ＳｏＣ）と呼ばれるシステムＬＳＩに搭載されるＣＡＭブロックにも適用することが可能であり、これまで述べた実施例と同様の効果が得られる。また、メモリセルは、図２３のＤＲＡＭセルや図１８のＳＲＡＭセルをベースとした構成以外にも、フラッシュ・メモリや強誘電体ＲＡＭ（フェロエレクトリック・ランダム・アクセス・メモリ）、ＭＲＡＭ（マグネトレジスティブ・ランダム・アクセス・メモリ）などのメモリセルを適用することも可能である。この場合、いずれも不揮発性のメモリセル構造であるので、電源遮断事故が起こっても、短時間に動作を復帰することができる。さらに、図２３や図１８では、サブマッチ線と接地電極との間に、NMOSトランジスタをT412、T413の順に直列接続するメモリセル構成を示したが、順番を逆にしても同様の検索動作が可能である。
【産業上の利用可能性】
【０１０９】
以上のように、本発明にかかる半導体装置は、ＩＰアドレスに限らず、様々な情報に関して１エントリあたりの情報量を増加しつつ、ソフトウェアの僅かな変更により、従来のＴＣＡＭと同様にシステムに実装することが可能であり、情報量の大きなテーブルを用いた検索動作を行う技術に適している。
【図面の簡単な説明】
【０１１０】
【図１】One-hot-spotブロック符号を適用したコンテント・アドレッサブル・メモリにおける要部ブロックの基本構成の例を示した説明図である。
【図２】図１のコンテント・アドレッサブル・メモリで用いられる書き込み動作における入出力信号と符号とのマッピングの例を示した説明図である。
【図３】図１のコンテント・アドレッサブル・メモリで用いられる読み出し動作における入出力信号と符号とのマッピングの例を示した説明図である。
【図４】図１のコンテント・アドレッサブル・メモリにおける符号化回路と復号回路、各種レジスタ群の詳細な構成の例を示した説明図である。
【図５】図１のコンテント・アドレッサブル・メモリにおける基本構成に基づくフロア・プランの例を示した説明図である。
【図６】図１のコンテント・アドレッサブル・メモリにおいてエントリを書き込む場合の動作タイミングの例を示した説明図である。
【図７】図１のコンテント・アドレッサブル・メモリにおいてエントリを読み出す場合の動作タイミングの例の前半サイクルを示した説明図である。
【図８】図１のコンテント・アドレッサブル・メモリにおいてエントリを読み出す場合の動作タイミングの別の例を示した説明図である。
【図９】図１のコンテント・アドレッサブル・メモリにおいて検索動作のタイミングの例を示した説明図である。
【図１０】ルータの構成例を模式的に示す説明図である。
【図１１】図１０のルータで転送処理するパケットの構成例を模式的に示す説明図である。
【図１２】図１０のルータにおけるパケット転送処理方法の例を説明図である。
【図１３】図１０のルータにおけるエントリ入力方法における概念の例を説明図である。
【図１４】図１０のルータにおけるエントリ入力におけるアルゴリズムの具体例を説明図である。
【図１５】図１のコンテント・アドレッサブル・メモリにおいてエントリを書き込む場合の動作タイミングの別の例を示した説明図である。
【図１６】図１のコンテント・アドレッサブル・メモリにおいてエントリを読み出す場合の動作タイミングの別の例を示した説明図である。
【図１７】図１のコンテント・アドレッサブル・メモリにおける基本構成に基づくフロア・プランの別の例を示した説明図である。
【図１８】図２２のメモリアレイにおけるメモリブロック構成の別の例を示した説明図である。
【図１９】ルータの構成例を模式的に示す説明図である。
【図２０】１７個のトランジスタで構成される従来のターナリ・コンテント・アドレッサブル・メモリセルの構成を示した説明図である。
【図２１】本発明をするにあたって検討したOne-hot-spotブロック符号を適用したコンテント・アドレッサブル・メモリにおいて処理される情報のマッピングを示した説明図である。
【図２２】本発明をするにあたって検討したOne-hot-spotブロック符号を適用したコンテント・アドレッサブル・メモリにおける階層マッチ線構造を用いたメモリアレイの構成例を示した説明図である。
【図２３】図２２のメモリアレイにおける回路ブロックの具体的な構成の例を示した説明図である。
【図２４】本発明をするにあたって検討したエントリおよび検索キーの構成例を模式的に示す説明図である。
【符号の説明】
【０１１１】
N211, N212, N213, N214, N411, N412, N413, N421, N422, N431…NMOSトランジスタ、P211, P222…PMOSトランジスタ、C…キャパシタ、
SMC0, SMC3, DMC0, DMC1, DMC2, DMC3…メモリセル、MMLm（m=0、1、…）…メインマッチ線、SMLmj（m=0、1、…、j=0、1、…）…メインマッチ線、WL, WLm（m=0、1、…）…ワード線、BL00T, BL03T, BL00B, BL03B, BL0, BL1, BL2, BL3, BLni（n=0、1、…、i=0、1、…、7）…ビット線、SL0, SL1, SL2, SL3, SLni（n=0、1、…、i=0、１、…、7）…サーチ線、PC…プリチャージ起動信号線、SEB…検索イネーブル信号線、N0i（i=0、1、…、7）, N00T, N03T…記憶ノード、MBmj（m=0、1、…、j=0、1、…）…メモリブロック、SMD、SMDmj（m=0、1、…、j=0、1、…）…サブマッチ判定回路、WDB…ワード・ドライバ群、WD…ワード・ドライバ、XDEC…ロウ・デコーダ、MMDB…メインマッチ判定回路群、SDB…サーチ線駆動回路群、RWB…読み書き回路群、MMD、MMD0…メインマッチ判定回路、SD0、SD1、SD2、SD3…サーチ線駆動回路、RW0、RW1、RW2、RW3…読み書き回路、VDD…電源電圧、VSS…接地電圧、VDL…アレイ電圧、VPC…プリチャージ電圧、NR…ネットワーク・ルータ、NIF…ネットワーク・インタフェイス、PFP…パケット・フォワーディング・プロセッサ、SE…検索エンジン、CAM…コンテント・アドレッサブル・メモリ、CM…コンテント・メモリ、PPU…パケット・プロセッシング・ユニット、PPUP…パケット・プロセッシング・ユニット用中央演算処理装置、RMB…ルーティング・マネージャ群、CBSWB…クロスバ・スイッチ群、CADD…コンテント・アドレス・バス、CBS…コンテント・バス、IPNx（x=0、1、…、y）…ネットワーク、SBS…システム・バス、IBS…内部バス、ETR…ルータNRの管理者が設定した情報、MAA、MAB…メモリアレイ、DIO…データ入出力回路、CAMCTL…ＣＡＭ制御回路、RFCNT…リフレッシュ・カウンタ、ENCDR…符号化回路、DCDR…復号回路、PENC…プライオリティ・エンコーダ、RAMCTL…ＲＡＭ制御回路、CPREG…コンパランド・レジスタ、WREG…バースト・ライト・レジスタ、NREG…ネクスト・フリーアドレス・レジスタ、RREG…バースト・リード・レジスタ、ISREG…インストラクション・レジスタ、IFREG…インフォメーション・レジスタ、
CFREG…コンフィガレーション・レジスタ、MAREG…マッチ・アドレス・レジスタ、REGB…各種レジスタ群、FDREG…第一サイクル・データ・レジスタ、SDREG…第二サイクル・データ・レジスタ、DIREG…情報識別レジスタ、DQ…データ・バス、CLK…外部クロック、CMD…外部コマンド信号群、ACK…リード・アクノーリッジ信号、DBS…内部データ・バス、SDBS…第一サイクル・データ・バス、SDBS…第二サイクル・データ・バス、XBS…ロウ・アドレス・バス、HBSA、HBSB…一致信号バス、MABS…マッチ・アドレス・バス、DIBS…認識情報バス、ENBS…符号化データ・バス、CBS…内部コマンド・バス、MWLBA、MWLBB…メイン・ワード線群、ARY0、ARY1、ARY2、ARY3…メモリアレイ群、IFB、IFB0、IFB1、IFB2、IFB3…インタフェイス回路群、DIREGEj…情報識別レジスタ要素ブロック、FDREGEj…第一サイクル・データ・レジスタ要素ブロック、SDREGEj…第二サイクル・データ・レジスタ要素ブロック、DL2j、DL(2j+1) …内部データ・バスの構成要素である内部データ線、QENCEj…４値符号化回路要素ブロック、TENCEj…３値符号化回路要素ブロック、QDCEj…４値復号回路要素ブロック、TDCEj…３値復号回路要素ブロック、FTSWBj…第一スイッチ群、SSWBj…第二スイッチ群、TSWBj…第三スイッチ群、FRSWBj…第四スイッチ群、DILj…識別情報バスDIBSの構成要素である情報識別線、FDL2j、FDL(2j+1)…第一サイクル・データ・バスFDBSの構成要素である第一サイクル・データ線、SDL2j、SDL(2j+1) …第二サイクル・データ・バスSDBSの構成要素である第二サイクル・データ線、ENLj0〜ENLj3…符号化データ・バスENBSの構成要素である符号化データ線、50…送信元ＩＰアドレスSIP（Source IP address）領域、51…宛先ＩＰアドレスDIP（Destination IP address）領域、52…第４層（トランスポート層）のプロトコル領域、53…TOS（Type of service）領域、54…第４層における送信元ポート番号（Source port）SPORT領域、55…第４層における宛先ポート番号（Destination port）DPORT領域、56…ユーザーが定義し、付加した情報を示すUDT領域、57…複数のフラグを示すUFLG領域、130…パケット、131…ペイロード領域、140…ヘッダ領域、141…第２層ヘッダ領域、142…第３層ヘッダ領域、143…第４層ヘッダ領域。
【図１】
2005353107.tif 000003
【図２】
2005353107.tif 000004
【図３】
2005353107.tif 000005
【図４】
2005353107.tif 000006
【図５】
2005353107.tif 000007
【図６】
2005353107.tif 000008
【図７】
2005353107.tif 000009
【図８】
2005353107.tif 000010
【図９】
2005353107.tif 000011
【図１０】
2005353107.tif 000012
【図１１】
2005353107.tif 000013
【図１２】
2005353107.tif 000014
【図１３】
2005353107.tif 000015
【図１４】
2005353107.tif 000016
【図１５】
2005353107.tif 000017
【図１６】
2005353107.tif 000018
【図１７】
2005353107.tif 000019
【図１８】
2005353107.tif 000020
【図１９】
2005353107.tif 000021
【図２０】
2005353107.tif 000022
【図２１】
2005353107.tif 000023
【図２２】
2005353107.tif 000024
【図２３】
2005353107.tif 000025
【図２４】
2005353107.tif 000026