(57)【特許請求の範囲】
【請求項１】
可変幅のコンテントアドレサブルメモリ（ＣＡＭ）デバイスであって、
可変幅の複数のデータを格納するための複数のＣＡＭブロックであって、各データは、所定幅を有する１つまたはそれ以上のデータ部分を含んでおり、各ＣＡＭブロックは、各ＣＡＭブロックが前記データのうち前記所定幅のデータ部分を格納することにより、前記各データが１つまたはそれ以上の前記ＣＡＭブロックに格納されるように構成されており、各ＣＡＭブロックは複数のエントリを備えており、各エントリはデータフィールドとタグフィールドとを含み、前記データフィールドは、前記データの前記所定幅のデータ部分を格納するように構成されており、前記タグフィールドは、前記データの全体の幅を示す１セットのタグビットを格納するように構成されており、前記ＣＡＭブロックは、各検索データ部分が前記所定幅を有する特定数の検索データ部分を含む検索データを受け取るように構成されており、各ＣＡＭブロックは、前記ＣＡＭブロック内で前記検索データを検索するために、前記検索データ内の１つの検索データ部分を受け取るように構成されており、各ＣＡＭブロック内の各エントリは、前記検索データの幅を示す１セットの入力タグビットを受け取り、各エントリは、前記入力タグビットが前記格納されたタグビットと一致し、かつ、前記所定幅のデータ部分が前記受け取られた検索データ部分と一致する場合に、一致結果を生成するように構成されている、前記複数のＣＡＭブロックと、
前記特定数の前記ＣＡＭブロックを連結させて１つまたはそれ以上の検索結果を生成するように構成されている複数のデュアルモード第１エンコーダであって、各デュアルモード第１エンコーダは、前記複数のＣＡＭブロックのうちの１つと関連付けられており、１セットの前記デュアルモード第１エンコーダは、前記検索データの幅に一致させるために前記特定数のＣＡＭブロックを連結するように構成されており、前記連結されたＣＡＭブロックのうちの一端のＣＡＭブロックに関連付けられている、前記デュアルモード第１エンコーダのうちの端のエンコーダは、前記１つまたはそれ以上の検索結果を生成するように構成されている、前記複数のデュアルモード第１エンコーダと、
を備える可変幅のＣＡＭデバイス。
【請求項２】
請求項１記載の可変幅のＣＡＭデバイスであって、
前記１つまたはそれ以上の検索結果は、前記ＣＡＭブロック内のアドレスであり、前記アドレスは、前記検索データと一致する前記データの位置を特定するものである、可変幅のＣＡＭデバイス。
【請求項３】
請求項１記載の可変幅のＣＡＭデバイスであって、さらに、
前記１つまたはそれ以上の検索結果を受け取り、所定のアルゴリズムに従って、前記１つまたはそれ以上の検索結果の中の１つを出力のために選択するように構成されている第２エンコーダを備える、可変幅のＣＡＭデバイス。
【請求項４】
請求項３記載の可変幅のＣＡＭデバイスであって、
各デュアルモード第１エンコーダは、前記ＣＡＭブロックの１つに関連付けられており、前記デュアルモード第１エンコーダは、前記デュアルモード第１エンコーダがディスエイブルにされた場合には、前記関連のＣＡＭブロックからの前記一致結果を転送し、前記デュアルモード第１エンコーダがイネーブルにされた場合には、前記検索結果を生成する、可変幅のＣＡＭデバイス。
【請求項５】
請求項４記載の可変幅のＣＡＭデバイスであって、
各エントリは、さらに、前記エントリに格納された前記所定幅のデータ部分が有効か否かを示す有効ビットを格納するための有効ビットフィールドを含んでおり、各エントリは、前記有効ビットが前記エントリに格納された前記データ部分が有効であることを示す場合にのみ、前記一致結果を生成する、可変幅のＣＡＭデバイス。
【請求項６】
請求項１記載の可変幅のＣＡＭデバイスであって、
各ＣＡＭブロック内の前記複数のエントリは、異なる行に配置されており、前記複数のデータのそれぞれのデータ内の前記所定幅のデータ部分は１つの行内に格納されており、前記１セットのデュアルモード第１エンコーダは、前記連結されたＣＡＭブロック内の同じ行に配置された前記エントリを連結するように構成されている、可変幅のＣＡＭデバイス。
【請求項７】
請求項１記載の可変幅のＣＡＭデバイスであって、
各ＣＡＭブロック内の前記複数のエントリは、１つまたはそれ以上の行にインターリーブされている、可変幅のＣＡＭデバイス。
【請求項８】
請求項１記載の可変幅のＣＡＭデバイスであって、
前記ＣＡＭブロックは、複数のクロックサイクルに渡って、前記検索データを順次検索する、可変幅のＣＡＭデバイス。
【請求項９】
請求項１記載の可変幅のＣＡＭデバイスであって、
前記各ＣＡＭブロックは、１つのクロックサイクル内で、関連する検索データ部分を並行して検索する、可変幅のＣＡＭデバイス。
【請求項１０】
可変幅のコンテントアドレサブルメモリ（ＣＡＭ）デバイスであって、
複数の幅を有する複数のデータを格納するための複数のＣＡＭブロックであって、各ＣＡＭブロックは複数のエントリを含み、各エントリは、前記複数のデータのうちの１つのデータ内の所定幅のデータ部分と、前記データの全体の幅を示す１セットのタグビットとを格納するように構成されており、前記複数のデータのそれぞれは、異なるＣＡＭブロック内に配置された１つまたはそれ以上のエントリ内に格納されており、前記ＣＡＭブロックは、各ＣＡＭブロックが前記所定幅を有する１つの検索データ部分を受け取るために、特定数の検索データ部分を含む検索データを受け取るように構成されており、前記ＣＡＭブロック内の各エントリは、前記検索データの幅を示す１セットの入力タグビットを受け取り、前記入力タグビットが前記格納されたタグビットと一致し、かつ、各エントリ内の前記所定幅のデータ部分が前記所定幅の前記検索データ部分と一致する場合に、一致結果を生成するように構成されている、前記複数のＣＡＭブロックと、
前記複数のＣＡＭブロックを順次特定数連結させて前記検索データの幅に一致させるための複数の第１エンコーダであって、各第１エンコーダは、１つのＣＡＭブロックに関連付けられ、前記関連のＣＡＭブロック内の前記エントリからの前記一致結果を受け取るように構成されており、１セットの前記第１エンコーダは、前記関連のＣＡＭブロックからの前記一致結果を、順次連結された次のＣＡＭブロックに入力として引き渡すように構成されており、前記順次連結されたＣＡＭブロックのうちの一端のＣＡＭブロックに関連付けられている、前記第１エンコーダのうちの端のエンコーダは、前記順次連結されたＣＡＭブロックが前記検索データと一致するデータを含む場合に、検索結果を生成するように構成されている、前記複数の第１エンコーダと
を備える、可変幅のＣＡＭデバイス。
【請求項１１】
請求項１０記載の可変幅のＣＡＭデバイスであって、さらに、
前記第１エンコーダのうちの前記端のエンコーダに接続されて、１つまたはそれ以上の前記検索結果を受け取るように構成されている第２エンコーダであって、所定のアルゴリズムに従って、前記受け取った検索結果の中の１つを出力のために選択するように構成されている、前記第２エンコーダを備える、可変幅のＣＡＭデバイス。
【請求項１２】
請求項１０記載の可変幅のＣＡＭデバイスであって、
前記複数の幅を有する前記複数のデータのそれぞれは、前記ＣＡＭブロック内の１つまたはそれ以上のエントリに格納されており、前記１つまたはそれ以上のエントリは、前記ＣＡＭブロックのいずれのブロックからも１つのエントリのみを含む、可変幅のＣＡＭデバイス。
【請求項１３】
請求項１０記載の可変幅のＣＡＭデバイスであって、
各第１エンコーダは、各第１エンコーダがディスエイブルにされた場合には、前記関連のＣＡＭブロックからの前記検索結果を転送し、各第１エンコーダがイネーブルにされた場合には、前記検索結果の１つを生成するように構成されている、可変幅のＣＡＭデバイス。
【請求項１４】
請求項１０記載の可変幅のＣＡＭデバイスであって、
各エントリは、前記エントリに格納された前記データ部分が有効か否かを示す有効ビットを格納するための有効ビットフィールドを含んでおり、各エントリは、前記有効ビットが前記エントリに格納された前記データ部分が有効であることを示す場合にのみ、前記一致結果を生成する、可変幅のＣＡＭデバイス。
【請求項１５】
請求項１０記載の可変幅のＣＡＭデバイスであって、
前記各ＣＡＭブロック内の前記複数のエントリは、異なる行に配置されており、前記複数のデータのそれぞれのデータ内の前記所定幅のデータ部分は１つの行内に格納されており、前記１セットの第１エンコーダの各第１エンコーダは、前記次のＣＡＭブロックの同じ行に配置された前記エントリに、前記関連のＣＡＭブロックからの前記一致結果を転送するように構成されている、可変幅のＣＡＭデバイス。
【請求項１６】
請求項１０記載の可変幅のＣＡＭデバイスであって、
各ＣＡＭブロック内の前記複数のエントリは、１つまたはそれ以上の行にインターリーブされている、可変幅のＣＡＭデバイス。
【請求項１７】
請求項１０記載の可変幅のＣＡＭデバイスであって、
前記ＣＡＭブロックは、複数のクロックサイクルに渡って、前記検索データを順次検索する、可変幅のＣＡＭデバイス。
【請求項１８】
請求項１０記載の可変幅のＣＡＭデバイスであって、
各ＣＡＭブロックは、１つのクロックサイクル内で、関連する検索データ部分を並行して検索する、可変幅のＣＡＭデバイス。
【請求項１９】
可変幅のコンテントアドレサブルメモリ（ＣＡＭ）デバイスであって、
可変幅の複数のデータを格納するための複数のＣＡＭブロックであって、各ＣＡＭブロックは複数のエントリを有し、各エントリは第１の幅のデータ部分と、前記データの全体の幅を示す１セットのタグビットとを格納するように構成されており、各ＣＡＭブロックは、各ＣＡＭブロック内の各エントリへの入力のために、検索データのうちの第１の幅の検索データ部分を受け取るように構成されており、前記ＣＡＭブロック内の各エントリは、前記検索データの幅を示す１セットの入力タグビットを受け取り、前記入力タグビットが前記格納されたタグビットと一致し、かつ、各エントリ内のデータ部分が前記第１の幅の前記検索データ部分と一致する場合に、一致結果を生成するように構成されている、前記複数のＣＡＭブロックと、
前記複数のＣＡＭブロックの前記エントリを連結させるための複数の第１エンコーダであって、各第１エンコーダは、１つのＣＡＭブロックに関連付けられ、前記関連のＣＡＭブロック内の前記エントリからの前記一致結果を受け取るように構成されており、各第１エンコーダは、前記一致結果を、順次連結された次のＣＡＭブロックに、前記次のＣＡＭブロックの前記エントリへの入力として転送するように構成されており、１セットの前記第１エンコーダは、前記一致結果を転送し、１つまたはそれ以上のＣＡＭブロック内の前記エントリを連結させることにより前記連結されたエントリの幅が前記検索データと一致するように適合されており、前記順次連結されたＣＡＭブロックのうちの一端のＣＡＭブロックに関連付けられている、前記第１エンコーダのうちの端のエンコーダは、前記連結されたエントリの一致結果に応じて検索結果を生成するように構成されている、前記複数の第１エンコーダと、
前記複数の第１エンコーダに接続されて、１つまたはそれ以上の前記検索結果を受け取るように構成されている第２エンコーダであって、前記受け取った検索結果の中の１つを出力のために選択するように構成されている、前記第２エンコーダと、
を備える可変幅のＣＡＭデバイス。
【請求項２０】
請求項１９記載の可変幅のＣＡＭデバイスであって、
各ＣＡＭブロック内の前記複数のエントリは、異なる行に配置されており、前記可変幅のデータのそれぞれのデータ内の前記第１の幅のデータ部分はそれぞれ１つの行内に格納されており、前記１セットの第１エンコーダの各第１エンコーダは、前記次のＣＡＭブロックの同じ行に配置された前記エントリに、前記関連のＣＡＭブロックからの前記一致結果を転送するように構成されている、可変幅のＣＡＭデバイス。
【請求項２１】
請求項１９記載の可変幅のＣＡＭデバイスであって、
各ＣＡＭブロック内の前記複数のエントリは、１つまたはそれ以上の行にインターリーブされている、可変幅のＣＡＭデバイス。
【請求項２２】
請求項１９記載の可変幅のＣＡＭデバイスであって、
前記ＣＡＭブロックは、複数のクロックサイクルに渡って、前記検索データを順次検索する、可変幅のＣＡＭデバイス。
【請求項２３】
請求項１９記載の可変幅のＣＡＭデバイスであって、
前記各ＣＡＭブロックは、１つのクロックサイクル内で、関連する検索データ部分を並行して検索する、可変幅のＣＡＭデバイス。
【請求項２４】
請求項２０記載の可変幅のＣＡＭデバイスであって、
前記可変幅のデータのそれぞれは、前記ＣＡＭブロック内の１つまたはそれ以上のエントリに格納されており、前記１つまたはそれ以上のエントリは、前記ＣＡＭブロックのいずれのブロックからも１つのエントリのみを含む、可変幅のＣＡＭデバイス。
【請求項２５】
請求項１９記載の可変幅のＣＡＭデバイスであって、
各エントリは、前記エントリに格納された前記データ部分が有効か否かを示す有効ビットを格納するための有効ビットフィールドを含んでおり、各エントリは、前記有効ビットが前記エントリに格納された前記データ部分が有効であることを示す場合にのみ、前記一致結果を生成するように構成されている、可変幅のＣＡＭデバイス。
【発明の詳細な説明】
【０００１】
【発明の背景】
発明の属する技術分野：
本発明は、一般に、メモリデバイスに関し、特に、可変幅のデータの検索が可能なコンテントアドレサブルメモリデバイスに関する。
【０００２】
関連技術：
メモリデバイスは、現代のコンピュータシステムおよびネットワークにとって不可欠なコンポーネントである。メモリデバイスは、ストレージデバイスとして、格納されたデータや命令に素早くアクセスするのに使用される。コンテントアドレサブルメモリ（ＣＡＭ）は、アドレス検索を実行するためによく用いられる特別なタイプのメモリである。例えば、インターネットルータは、指定されたデータのアドレスを検索するためにＣＡＭを備えていることが多い。ＣＡＭの使用によって、ルータは高速検索をすることができ、この結果、コンピュータシステム間で、ネットワークを介して互いにデータをやり取りすることが可能となる。また、ＣＡＭは、ルータの他、データベース検索、画像処理、音声認識アプリケーションなどの高速検索動作が望まれる領域でよく使用される。
【０００３】
周知のように、ＣＡＭは、通常、コアセルとなる二次元的な行および列のコンテントアドレサブルメモリアレイを備えており、各列は、アドレスや、ポインタ、ビットパターンのエントリを有している。ＣＡＭは、このようなセルの配列に基づいて、従来のランダムアクセスメモリ（ＲＡＭ）のように、特定アドレスにおいて「読み出し」および「書き込み」動作を実行することができる。また、ＣＡＭは、データのビットパターンを、ＣＡＭアレイ内に予め格納されたビットパターンのエントリ（例えば、列）の全リスト（例えば、行）と同時に比較する高速検索動作を実行することもできる。ＣＡＭは、通常、これらの比較に基づいて、入力データと一致したエントリに対応する結果を、アドレスや、ポインタ、ビットパターン形式で出力する。このように、ＣＡＭは、その全てのエントリを一度に比較することにより、ＤＲＡＭやＳＲＡＭ等のＲＡＭを介した検索時間を大幅に削減することができる。
【０００４】
現代のコンピュータシステムやネットワークでは、ＣＡＭは、必要なデータサイズが異なる種々のアプリケーションで使用されることが多い。例えば、インターネットルータやスイッチでは、ＣＡＭは、メディアアクセス制御（ＭＡＣ）レベルのスイッチングや非同期転送モード（ＡＴＭ）、インターネットプロトコル（ＩＰ）バージョン４、６などの種々のネットワークレイヤプロトコルで使用される。当業者には周知のように、ＡＴＭは３２ビットのデータフィールドを頻用するのに対し、ＭＡＣレベル２のアドレッシングは、通常、４８〜６４ビットのデータサイズを使用する。データサイズは、指定されるアプリケーションに依存して、かなり変化する。例えば、スイッチングにおいてソースアドレスおよび宛先アドレスの双方が使用される場合には、ＭＡＣレベルのアドレッシングのデータサイズは６４ビットから１２８ビットに増加する。
【０００５】
変動する必要なデータサイズに対応するために、従来のアプローチ法では、各マクロを特定の必要なデータサイズに設定可能な、複数のマクロを有するＣＡＭチップが利用されている。図１Ａは、４つのマクロ１０２，１０４，１０６，１０８を有する従来のＣＡＭチップ１００を示すブロック図である。各マクロ１０２，１０４，１０６，１０８は、ユーザによって、種々のアプリケーションに応じて特定の幅に設定される。例えば、マクロ１０２は、４Ｋｘ６４ブロック（すなわち、６４ビットのデータ幅で４Ｋのエントリ）に設定され、マクロ１０４，１０８は、８Ｋｘ３２ブロック（すなわち、３２ビットのデータ幅で８Ｋのエントリ）に設定され、マクロ１０６は、２Ｋｘ１２８ブロック（すなわち、１２８ビットのデータ幅で２Ｋのエントリ）に設定される。この構成では、１つのマクロ内のエントリは、全て同一の幅を有している。
【０００６】
図１Ｂは、種々の幅に設定可能なマクロ１２０を示すブロック図である。図示するように、マクロ１２０は、複数のブロック１２２，１２４，１２６，１２８，１３０を有し、これらは３２ビット幅、６４ビット幅、１２８ビット幅、２５６ビット幅に設定可能である。例えば、ブロック１２２，１２４，１２６，１２８が、それぞれ３２ビット幅を提供するのに使用されてもよい。また、ブロック１２２，１２４が、６４ビットのデータ幅サイズを提供するのに使用されてもよい。
【０００７】
しかしながら、従来のマクロ１０２，１０４，１０６，１０８，１２０の幅は、通常、各マクロのデータサイズを特定する関連のレジスタを使用することによってのみ、ブロックレベルでの設定が可能となる。これは、各マクロ１０２，１０４，１０６，１０８，１２０が一度に適応できるのが、１つのデータサイズのみであることを意味している。ブロックレベルでのマクロの構成は、貴重なメモリスペースを無駄にする場合が多い。例えば、１２８ビットのデータ幅に適応できるマクロ１２０を、実際に、６４ビットのデータ幅に設定すると、メモリスペースの半分が使用されないため、事実上メモリスペースの５０％が無駄となる。同様に、６４ビットのデータ幅をサポートできるマクロ１２０を３２ビットのデータ幅に設定すると、メモリスペースの半分が損なわれる。また、マクロのオーバフローを避けるためには、マクロを使用するユーザまたはカスタマが、マクロとそのデータサイズとについて熟知している必要がある。さらに、マクロが異なるデータサイズに再プログラムされる場合には、プロセス中に貴重なデータ（例えば、検索の統計量）が損なわれる恐れがある。
【０００８】
以上からわかるように、可変サイズ幅のデータを格納できるＣＡＭデバイスを提供することにより、可変幅のデータの検索を貴重なメモリスペースを無駄にすることなく行い、ＣＡＭスペースの使用量を、コストの削減を伴いつつ最大化することが必要とされている。
【０００９】
【発明の概要】
本発明は、可変幅のデータを検索するための可変幅のＣＡＭデバイスを提供することにより、上述したニーズを満たす。なお、本発明は、プロセス、装置、システム、デバイス、方法を含む種々の形態で実現できる。以下では、本発明の幾つかの実施形態を説明する。
【００１０】
一実施形態において、本発明は、可変幅のデータを検索するための可変幅のＣＡＭデバイスを提供する。ＣＡＭデバイスは、複数のＣＡＭブロックと複数の第１エンコーダとを備える。複数のＣＡＭブロックは、可変幅の複数のデータを格納するように構成されており、各データは、１つまたはそれ以上の所定幅を有する１つまたはそれ以上のデータ部分を含んでいる。各ＣＡＭブロックは、各ＣＡＭブロックがデータのうち所定幅の部分を格納することによって、各データが１つまたはそれ以上のＣＡＭブロックに格納されるように構成されている。ＣＡＭブロックは、各検索データ部分が１つまたはそれ以上の所定幅を有する特定数の検索データ部分を含む検索データを受け取る。各ＣＡＭブロックは、ＣＡＭブロック内で検索データを検索するために、その検索データ内の１つの検索データ部分を受け取る。複数のデュアルモード第１エンコーダは、特定数のＣＡＭブロックを鎖状に連結させて、１つまたはそれ以上の検索結果を生成するように構成されている。１セットのデュアルモード第１エンコーダは、特定数のＣＡＭブロックを連結させて、検索データの幅に一致させる。残りのデュアルモード第１のエンコードは、連結されたＣＡＭブロックが検索データと一致するデータを含む場合に、１つまたはそれ以上の検索結果を生成する。
【００１１】
別の実施形態において、本発明は、複数のＣＡＭブロックと複数の第１エンコーダとを備える可変幅のＣＡＭデバイスを提供する。複数のＣＡＭブロックは、複数の幅を有する複数のデータを格納するように構成されている。各ＣＡＭブロックは複数のエントリを有しており、各エントリは、複数のデータのうちの１つのデータ内の所定幅のデータ部分を格納するように構成されている。複数のデータのそれぞれは、異なるＣＡＭブロック内に配置された１つまたはそれ以上のエントリ内に格納されている。ＣＡＭブロックは、各ＣＡＭブロックが所定幅の１つの検索データ部分を受け取るために、特定数の検索データ部分を有する検索データを受け取るように構成されている。ＣＡＭブロック内の各エントリは、各エントリの所定幅のデータ部分が所定幅の検索データ部分と一致する場合に、一致結果を生成することができる。複数の第１エンコーダは、複数のＣＡＭブロックを順次特定数だけ鎖状に連結させて、検索データの幅に一致させるように構成されている。各第１エンコーダは、１つのＣＡＭブロックに関連付けられ、その関連のＣＡＭブロック内のエントリからの一致結果を受け取る。１セットの第１エンコーダは、関連のＣＡＭブロックからの一致結果を、順次連結された次のＣＡＭブロックに入力として引き渡す。残りの各第１エンコーダは、順次連結されたＣＡＭブロックが検索データと一致するデータを含む場合に、検索結果を生成する。
【００１２】
さらに別の実施形態では、可変幅のＣＡＭデバイスを開示する。可変幅のＣＡＭは、複数のＣＡＭブロックと、複数の第１エンコーダと、１つの第２エンコーダとを備えている。複数のＣＡＭブロックは、複数のエントリを有する各ＣＡＭブロックに、可変幅のデータを格納するように構成されている。各エントリは、第１の幅のデータを格納するように構成されている。各ＣＡＭブロックは、各ＣＡＭブロック内の各エントリへの入力のために、検索データのうちの第１の幅の検索データ部分を受け取るように構成されている。ＣＡＭブロック内の各エントリは、各エントリ内のデータが第１の幅の検索データ部分と一致する場合に、一致結果を生成することができる。複数の第１エンコーダは、複数のＣＡＭブロックのエントリを鎖状に連結するように構成されている。各第１エンコーダは、１つのＣＡＭブロックに関連付けられ、その関連のＣＡＭブロック内のエントリからの一致結果を受け取る。各第１エンコーダは、順次連結された次のＣＡＭブロックに、該次のブロックのエントリへの入力として、一致結果を引き渡すように構成されている。１セットの第１エンコーダは、一致結果を転送し、１つまたはそれ以上のＣＡＭブロック内のエントリを連結させることにより、連結されたエントリの幅が検索データと一致するように適応されている。残りの第１エンコーダのそれぞれは、連結されたエントリの一致結果に応じて検索結果を生成する。第２エンコーダは、複数の第１エンコーダに接続されて、１つまたはそれ以上の検索結果を受け取る。第２エンコーダは、その受け取った検索結果の中の１つを出力のために選択する。
【００１３】
本発明によるＣＡＭデバイスは、可変幅のデータを検索するために可変幅のデータを格納することによって、ＣＡＭスペースの節約および柔軟性の向上をもたらす。例えば、可変幅のデータの格納および検索は、エントリの幅を識別するタグビットを、ブロックベーシスに代えてエントリベーシスでプログラミングできるようにすることにより、ユーザに大きな柔軟性をもたらす。また、可変幅のデータを個々のエントリベーシスで格納および検索することにより、従来のＣＡＭマクロに関連して生じた未使用または使用できないＣＡＭスペースを排除して、貴重なＣＡＭスペースを節約することができる。ＣＡＭデバイスの可変幅の格納および検索の能力は、ＩＰｖ４，ＩＰｖ６，ＡＴＭ，ＭＡＣレベルのスイッチング等のマルチプロトコルアプリケーションに対して特に有益である。本発明の原理を例示した添付図面との関連のもとで行う以下の詳細な説明から、本発明の他の効果が明らかとなる。
【００１４】
【好ましい実施形態の詳細な説明】
本発明の可変幅のデータを検索するための可変幅のＣＡＭデバイスに関する以下の説明では、本発明の完全な理解を促すために多くの詳細について特定している。しかしながら、当業者には理解できるように、本発明は、これらの項目の一部または全てを特定しなくても実行することが可能である。そのほか、本発明を不必要に不明瞭にするのを避けるため、周知のプロセス動作の説明は省略した。
【００１５】
図２Ａは、可変データ幅を実現するための代表的なＣＡＭデバイス２００を、本発明の一実施形態に従って示すブロック図である。ＣＡＭデバイス２００は、複数のＣＡＭブロック２０２，２０４，２０６を備えている。ＣＡＭブロック２０２，２０４，２０６のそれぞれは、エントリ１からエントリＭまでのＭ個のエントリを有している。後で詳述するように、各エントリは、タグ値を格納するためのタグフィールドと、所定幅のデータを格納するためのデータフィールドとを備えている。各ＣＡＭブロック内では、エントリは並べて配置されて、行毎に１つのエントリが設けられる。ＣＡＭブロック２０２，２０４，２０６内のエントリに対応するデータフィールドは、例えば、３２ビット幅などの均一なサイズであることが好ましい。図中、ＣＡＭデバイス２００は、３つのＣＡＭブロック２０２，２０４，２０６を使用しているが、任意の数のＣＡＭブロックを利用して、可変データ幅を実現することが可能である。
【００１６】
可変データサイズの検索動作を実行するために、ＣＡＭブロック２０２，２０４，２０６は、タグおよび検索データを入力として受け取るように構成されている。検索データは、検索されるべきデータであり、タグは、検索データの幅を指定する。タグは、ＣＡＭブロック２０２，２０４，２０６全てに対して同一であることが好ましいが、検索データは、ＣＡＭブロック毎に異なる。例えば、ＣＡＭブロック２０２，２０４，２０６は、全て同じ値の１つのタグを受け取る一方で、検索データSearch_Data_1 ，Search_Data_2 ，Search_Data_3 をそれぞれ受け取る。
【００１７】
タグは、可変幅のデータの格納および検索を実現するために、検索されるべきデータの幅をエンコードする。以下の表１に示すように、一実施形態では、３２ビット〜２５６ビットの可変データ幅を実現するために、２ビットのタグがエンコードされる。
【００１８】
【表１】
0004927247.tif 000002
【００１９】
表１に示すように、データの幅はタグ値に従って変化する。例えば、タグ値「００」，「０１」，「１０」，「１１」は、それぞれ３２ビット，６４ビット，１２８ビット，２５６ビットのデータ幅を指す。本発明は、このようなタグ体系を用いて示されているが、任意の数のタグビットを用いて任意の適切なデータ幅をエンコードすることが可能である。
【００２０】
後で詳述するように、ＣＡＭブロック２０２，２０４，２０６内の各エントリは、タグフィールドとデータフィールドとを備える。可変幅のＣＡＭデバイス２００にデータを格納する際には、データの幅（すなわちサイズ）を示すタグ値が、データフィールド内の関連のデータ部分とともに、タグフィールド内に格納される。一実施形態では、ＣＡＭブロック２０２，２０４，２０６の各エントリは、３２ビットのデータフィールドと２ビットのタグフィールドとを備えている。例えば、ＣＡＭブロック２０２のエントリ１に３２ビットのデータを格納する際には、エントリ１のタグフィールドに、タグ値「００」が格納される。６４ビットのデータを格納するには、２つのエントリが必要である。例えば、６４ビットのデータは、ＣＡＭブロック２０２，２０４のエントリ２２２，２２４にそれぞれ格納される。この場合、第１の３２データビットはエントリ２２２に格納され、第２の３２データビットはエントリ２２４に格納される。また、タグ値「０１」がエントリ２２２，２２４の両方のタグフィールドに格納され、これらのエントリは６４ビットのデータを含むことを示す。
【００２１】
検索動作で使用するために、ＣＡＭデバイス２００は、ＣＡＭブロック２０２，２０４，２０６にそれぞれ関連付けられた複数のエンコーダ２１２，２１４，２１６を備えている。エンコーダ２１２，２１４，２１６は、エンコーダをイネーブルまたはディスエイブルにするためのイネーブル信号PE_Enable_1 ，PE_Enable_2 ，PE_Enable_N をそれぞれ受け取る。例えば、イネーブル信号PE_Enable_1 ，PE_Enable_2 ，PE_Enable_N がイネーブルにされる（例えば、断定される）場合には、エンコーダ２１２，２１４，２１６は、一致結果をエンコードして検索結果を生成し、さらに所定のアルゴリズムを使用して、その中から１つの検索結果を出力のために選択するように機能する。
【００２２】
しかしながら、イネーブル信号がディスエイブルにされる（例えば、断定されない）と、エンコーダ２１２，２１４，２１６は、従来のエンコーダとして機能する代わりに、あるＣＡＭブロックからその次のＣＡＭブロックへと一致結果を送信する。例えば、イネーブル信号PE_Enable_1 が断定されない場合には、エンコーダ２１２がディスエイブルにされる。この場合、エンコーダ２１２は、次のＣＡＭブロック２０４内の対応するエントリに、一致結果MR1_B1，MR2_B1，MRM_B1を送信したり引き渡したりする。
【００２３】
この方法では、ＣＡＭブロック２０２，２０４を鎖状に連結させることにより、３２ビット幅を超えるデータワードの検索を行う。６４ビットのワードを検索する場合には、エンコーダ２１２はディスエイブルにされて、ＣＡＭブロック２０２，２０４を連結させる一方で、エンコーダ２１４はイネーブルにされて、Search_Result_2を出力し、次のＣＡＭブロックに一致結果が送信されるのを阻止する。３２ビットのデータを検索する場合は、エンコーダ２１２，２１４，２１６は、全てイネーブルにされて、検索結果Search_Result_1，Search_Result_2，Search_Result_Nを出力する。同時に、ＣＡＭブロック２０２，２０４，２０６の連結が断たれ、一致結果の送信が阻止される。
【００２４】
この構成では、検索動作の実行時に、ＣＡＭブロック２０２，２０４，２０６のそれぞれに検索データとタグ値とが供給されて、エントリが同時に比較される。例えば、３２ビットデータの検索を実現するには、３２ビットデータとタグ「００」とが、ＣＡＭブロック２０２，２０４，２０６内の各エントリに供給される。そして、各エントリが、供給されたタグとデータビットとに応じて一致結果（ＭＲ）を生成する。例えば、エントリ２２２，２２８，２３４は、それぞれ、格納されたデータおよびタグが入力されたデータおよびタグに一致することを示す一致結果MR1_B1，MR2_B1，MRM_B1を生成する。この３２ビットデータの検索動作では、エンコーダ２１２，２１４，２１６へのイネーブル信号が断定され、ＣＡＭデバイス２００内の全エンコーダがイネーブルにされる。エンコーダのイネーブリングによって、関連のＣＡＭブロックの次のＣＡＭブロックとの連結が断たれる。これに応じて、各エンコーダ２１２，２１４，２１６は、生成された一致結果をエンコードして検索結果を生成し、所定のアルゴリズムに従って、その中から、出力のための検索結果をSearch_Result_1，Search_Result_2，Search_Result_Nとして選択する。なお、入力されたデータおよびタグに一致するエントリがＣＡＭブロック内に存在せず、このため関連のエンコーダが検索結果を生成しない場合もある。
【００２５】
一方、６４ビットデータの検索を実行する場合には、一対の連続したＣＡＭブロックに、タグ「０１」と６４ビットデータを構成する２つの３２ビットデータとが供給される。例えば、第１および第２の３２データビットが、Search_Data_1 ，Search_Data_2 として、タグ値「０１」とともにＣＡＭブロック２０２，２０４に供給される。また、エンコーダ２１２はディスエイブルにされて、ＣＡＭブロック２０２からＣＡＭブロック２０４への一致結果の送信が可能となる。反対に、エンコーダ２１４はイネーブルにされて、出力のための検索結果Search_Result_2を生成する。また、ＣＡＭデバイス内の残りのＣＡＭブロックも、同様に機能して６４ビット幅の検索を実現する。
【００２６】
イネーブルにされると、エンコーダ２１２，２１４，２１６からの検索結果はエンコーダ２１８に供給される。エンコーダ２１８は、所定のアルゴリズムに従って検索結果を１つ選択し、その選択された検索結果を出力する。したがって、選択された検索結果は、所定のアルゴリズムに従ってエンコードされた検索データのアドレスである。
【００２７】
ＣＡＭデバイス２００は、種々のデータ幅を実現するために、任意の数のＣＡＭブロックを利用してもよい。図２Ｂは、４つのＣＡＭブロック２５２，２５４，２５６，２５８を有する代表的なＣＡＭデバイスを、本発明の一実施形態に従って示す図である。ＣＡＭデバイス２５０は、図２Ａで説明したＣＡＭデバイス２００と同様に機能する。図示するように、ＣＡＭデバイス２５０内の各エントリは、タグフィールド（Ｔ）とデータフィールドとを備えている。例えば、エントリ２７０は、タグフィールド２７６ａとデータフィールド２７６ｂとを備えている。各ＣＡＭブロック２５２，２５４，２５６，２５８は、特定のデータ幅のデータフィールドを有するＣＡＭエントリを備えている。
【００２８】
例えば、各ＣＡＭブロック２５２，２５４，２５６，２５８は、３２ビットのデータ幅を有するＣＡＭブロックである。すなわち、エントリは３２ビット幅のデータフィールドを有している。なお、ブロック２５２〜２５８は、要求されるデータのサイズ粒度を提供するために、任意のデータ幅（例えば、１６ビット，３２ビット，６４ビットなど）を備えていればよく、また、データ幅はブロック毎に同じである必要はない。この構成では、４つのＣＡＭブロック２５２，２５４，２５６，２５８が使用されており、３２ビット〜１２８ビットのデータ幅に対するアクセスが可能である。例えば、行２７０の一対のエントリ２７６および２８２を、タグ値「０１」を有する６４ビットのデータを格納および検索するのに使用する一方で、エントリ２８６および２９０を、同じタグ値「０１」を有する別の６４ビットのデータを検索するのに使用してもよい。同様に、４つのエントリ２７８，２８４，２８８，２９２全てを、例えば、タグ値「１０」を有する１つの１２８ビットのデータを格納および検索するのに使用してもよい。
【００２９】
図３Ａは、代表的なＣＡＭデバイス３００のＣＡＭブロック３０２，３０４内に含まれる一対のエントリ３１０，３１２を、本発明の一実施形態に従ってより詳細に示すブロック図である。なお、必要な可変データ幅を提供するためには、ＣＡＭデバイス３００は、図３Ａに示すブロック以外に任意の数のＣＡＭブロックを備えていてもよい。ＣＡＭブロック３０２，３０４内の各エントリは、タグフィールド３１４と、有効ビットフィールド３１６と、データフィールド３１８と、センスアンプ（ＳＡ）３２０とを備えている。例えば、エントリ３１０は、タグフィールド３１４ａと、有効ビットフィールド３１６ａと、データフィールド３１８ａと、センスアンプ３２０ａとを備えている。同様に、エントリ３１２は、タグフィールド３１４ｂと、有効ビットフィールド３１６ｂと、データフィールド３１８ｂと、センスアンプ３２０ｂとを備えている。データフィールド３１８は、特定幅のデータを格納する。タグフィールド３１４は、データ全体の幅を示すタグビットを格納し、データフィールド３１８内のデータは、データ全体の一部分を構成する。
【００３０】
有効ビットフィールド３１６は、関連のエントリが有効データを含むか否かを示す有効ビットを格納するのに用いられる。例えば、有効ビットフィールド３１６ａ内の有効ビットが断定された場合には、エントリ３１０は、データフィールド３１８ａ内に有効データを含む。反対に、有効ビットが断定されなかった場合には、データフィールド３１８ａ内のデータは無効データである。センスアンプ３２０は、一致結果信号を、出力のために増幅するのに用いられる。例えば、センスアンプ３２０ａ，３２０ｂは、一対のエンコーダ３０６，３０８に出力するために、一致結果信号ＭＲ１，ＭＲ２をそれぞれ増幅する。
【００３１】
この構成では、エンコーダの機能をイネーブルまたはディスエイブルにするために、エンコーダ３０６，３０８は、それぞれ、エンコーダイネーブル信号PE_Enable_1 ，PE_Enable_2 を受け取る。例えば、エンコーダイネーブル信号が断定されると、関連のエンコーダは、従来のエンコーダモードで機能し、一致結果をエンコードして関連の検索アドレスを生成し、その中の１つの検索結果を出力として選択する。しかしながら、エンコーダイネーブル信号がディスエイブルにされると、エンコーダの従来の機能がディスエイブルにされ、代わりに、エンコーダは、受け取った一致結果信号を、次のＣＡＭブロック内の同じ行に配置されるエントリに送信する。
【００３２】
例えば、データフィールド３１８ａ，３１８ｂは、エントリ３１０，３１２が連結されて６４ビットのエントリを形成することを示すタグ値「０１」がタグフィールド３１４ａ，３１４ｂの両方に格納された状態で、それぞれ３２ビットのデータを格納する。エントリ３１０は、６４ビットデータの第１の部分を含むので、一致結果（ＭＲ０）の入力は高供給電圧Ｖ＋に繋がっている。６４ビットデータの検索を実行する際には、PE_Enable_1 がディスエイブルにされる。これによって、エンコーダ３０６は、一致結果ＭＲ１を次のエントリ３１２に引き渡すことができる。一方、PE_Enable_2 信号がイネーブルにされると、エンコーダ３０８は、一致結果ＭＲ２をエンコードして検索結果を生成する。この方法では、エントリ３１０，３１２が効果的に連結されて、１つの６４ビットのエントリを格納および検索することができる。
【００３３】
しかしながら、３２ビットの検索動作を実行するためには、データフィールド３１８ａ，３１８ｂは、それぞれ３２ビットデータを格納し、関連のタグフィールド３１４ａ，３１４ｂは、それぞれタグ値「００」を格納すればよい。この場合には、信号PE_Enable_1 ，PE_Enable_2 の双方がイネーブルにされるため、エンコーダ３０６，３０８は、一致結果ＭＲ１，ＭＲ２をそれぞれ独立にエンコードして検索アドレスを生成する。このように、ＣＡＭデバイス３００は、可変幅のデータを格納および検索する能力を提供することができる。
【００３４】
なお、３つの状態「０」，「１」，「Ｘ」のうちの任意の１つの状態を格納することにより、データ、有効ビット、タグフィールドに対し、３進法による比較を実現できる。適用および格納されたデータと有効とタグ値とが有効状態「０」および「１」を有している場合には、通常の２進法による突き合わせによって、適用されたデータと有効とタグ値とが、格納されたデータおよびタグ値と同じときに、一致結果が生成される。この場合は、入力および格納されたビットが共に「０」または「１」である場合（例えば、０＝０または１＝１）に、一致したとみなされる。また、３進法による突き合わせでは、第３の状態「Ｘ」が「０」または「１」である場合（例えば、０＝Ｘ，１＝Ｘ，Ｘ＝０，Ｘ＝１）に、適用および格納されたデータとタグ値とが一致したとみなされる。
【００３５】
好ましい一実施形態では、検索動作は、あるブロックから次のブロックへと連続してパイプラインされている。例えば、３２ビットのデータを検索する場合、ＣＡＭブロック３０２，３０４内における検索は、２つのサイクルで実行される。すなわち、各ＣＡＭブロックに１つの検索サイクルを割り当て、そして、各エンコーダ３０６，３０８が検索結果を生成するのにもう１つのサイクルを割り当てる。同様にして、６４ビットのデータの検索は、３つのサイクルで実行される。すなわち、ＣＡＭブロック３０２，３０４に２つの検索サイクルを割り当て、そして、エンコーダ３０８が検索結果を生成するのにもう１つのサイクルを割り当てる。同様に、１２８ビットのデータの検索は、５つのクロックサイクルで実行される。したがって、パイプライン化された検索動作では、各ＣＡＭブロックにおける検索に１つのサイクルを使用し、最後のエンコーダが検索結果を生成するのに１つのサイクルを使用する。あるいは、ＣＡＭブロックにおける検索動作は、マルチブロック検索モードによって１つのサイクル内で並行して実行されてもよい。この場合は、入力された検索データとタグ値とは、ＣＡＭブロックに並行して供給される。
【００３６】
図３Ｂは、ＣＡＭデバイス２００，２５０，３００において、可変幅のデータを検索するための代表的なメソッドを、本発明の一実施形態に従って示すフローチャートである。このメソッドは、データの適切な幅を示す関連のタグとともに、データが格納されていることを前提としている。このメソッドでは、工程３２２において、最左端のＣＡＭブロックでデータおよびタグを検索するとともに、エンコーダイネーブル信号を供給する。エンコーダイネーブル信号は、アクティブ（例えば、断定される）または非アクティブ（例えば、断定されない）のいずれかである。そして、工程３２４において、エンコーダイネーブル信号がアクティブか否かが決定される。アクティブである場合には、ブロックに関連付けられたエンコーダが、従来のエンコーダモードで機能する。この場合には、メソッドは工程３２６に進み、工程３２６において、一致結果があれば、それらの中から検索結果を生成する。一方、エンコーダイネーブル信号が非アクティブである場合には、工程３２８において、一致結果があれば、それらの一致結果を現行のＣＡＭブロックから次のＣＡＭブロック内にある関連のエントリに送信する。上述したように、ＣＡＭブロック内のエントリ内のタグおよびデータが、入力されたタグおよびデータに共に一致する場合には、そのエントリは、一致結果を生成して次のブロックに送信する。一貫性を維持するため、以下では、上記の現行のブロックを直前のブロックと呼び、上記の次のブロックを現行のブロックと呼ぶ。
【００３７】
一致結果を受け取ると、工程３３０において、新しい現行のＣＡＭブロックは、直前のブロックで使用されたのと同一のタグを有する入力データを検索する。同時に、現行のＣＡＭブロックのエンコーダ信号が設定され、現行のＣＡＭブロックに関連付けられたエンコーダに供給される。そして、工程３３２において、現行のブロックに関連付けられたエンコーダのエンコーダイネーブル信号がアクティブか否かが決定される。アクティブである場合には、エンコーダは、工程３３４において、一致結果があれば、それらの中から検索結果を生成する。しかしながら、エンコーダイネーブル信号が非アクティブである場合には、検索データの幅が大きいことを意味している。この場合には、メソッドは工程３２８に戻り、新しい次のブロックに一致結果が引き渡される。
【００３８】
図３Ｃは、ブロック内の２つまたはそれ以上の隣接した行を使用して、大きな幅のエントリを格納するように構成されたＣＡＭデバイスを、本発明の一実施形態に従って示す図である。図３Ｃに示すＣＡＭデバイス３５０は、図３Ａに示すＣＡＭデバイス３００と同様であるが、図３Ａのデュアルモードエンコーダ３０６，３０８に代えて、マルチモードエンコーダ３５６，３５８が使用されている。マルチモードエンコーダ３５６，３５８は、デュアルモードエンコーダ３０６，３０８と同様に、ディスエイブルモード（例えば、PE_Enable_1 およびMerge_Rows_1が共に低位）またはイネーブルモード（例えば、PE_Enable_1 が高位で、Merge_Rows_1が低位）で作動し得る。また、マルチモードエンコーダ３５６，３５８は、マルチローエンコードモード（例えば、PE_Enable_1 およびMerge_Rows_1が共に高位）およびマルチローキャプチャモード（例えば、PE_Enable_1 が低位で、Merge_Rows_1が高位）も備えている。マルチモードエンコーダのこれら４つのモードを、次の表２にまとめた。
【００３９】
【表２】
0004927247.tif 000003
【００４０】
例えば、１２８ビットの値をＣＡＭデバイス３５０に格納するには、３２ビットの各部分が各エントリ３６０，３６２，３８０，３８２に格納される。１２８ビットのエントリのデータ部分は、データフィールド３６８ａ，３６８ｂ，３６８ｃ，３６８ｄに格納され、各データ部分の有効ビット３６６ａ，３６６ｂ，３６６ｃ，３６６ｄは全て有効状態に設定され、タグ値はタグフィールド３６４ａ，３６４ｂ，３６４ｃ，３６４ｄ内に格納されている。ＣＡＭブロック３５２は第１のブロックなので、一致結果の入力ＭＲ０，ＭＲ４は高位に接続され、一致結果の出力ＭＲ１，ＭＲ４はＣＡＭブロック３５４の一致結果の入力に接続されている。この例では、３２ビットのエントリはタグ値００を使用し、６４ビットのエントリはタグ値０１を使用し、PE_Enable 制御信号および適用されたタグの適切な制御によって、ＣＡＭデバイス３００で検索を行う場合と同様に、検索が行われる。この場合、Merge_Rowsエンコーダ制御信号は低位で維持される。
【００４１】
１２８ビットのエントリは、各ブロック内で２つの隣接した行に渡って格納されるので、その検索には２つのタグ値が必要である。すなわち、タグ１０が上の行のエントリ３６０，３６２に格納され、タグ１１が下の行のエントリ３８０，３８２に格納される。この方法では、３２ビットの２つの検索データ部分を、タグ１０とともにＣＡＭブロック３５２，３５４に割り当てて、１つの検索サイクル内で検索結果ＭＲ１，ＭＲ２を生成する。エンコーダの制御は、エンコーダ３５６をディスエイブルにする（PE_Enable_1 およびMerge_Rows_1を共に低位に設定する）ことにより、一致結果ＭＲ１がＣＡＭブロック３５２からＣＡＭブロック３５４に流れるように、設定されている。一致結果ＭＲ１は、エントリ３６２からの検索結果と組み合わされ、一致結果ＭＲ２が生成され、一致結果ＭＲ２は、エンコーダ３５８でキャプチャされて格納される（PE_Enable_2 が低位でMerge_Rows_2が高位）。続く検索サイクルでは、残り２つの３２ビットの検索データ部分が、タグ１１とともにＣＡＭブロック３５２，３５４に割り当てられ、エンコーダ３５６がディスエイブルにされ、一致結果ＭＲ４がＣＡＭブロック３５４に引き渡され、一致結果ＭＲ４はエントリ３８２からの一致結果と組み合わされ、一致結果ＭＲ５が生成される。
【００４２】
エンコーダ３５８は、エンコーダ制御入力PE_Enable_2 およびMerge_Rows_2が共に高位に設定された状態では、マルチローエンコードモードで作動する。一致結果ＭＲ５は、ＡＮＤゲート３９２によって、格納された一致結果ＭＲ２と論理的にＡＮＤされて、１２８ビットエントリの１つの一致結果ＭＲ２５を生成する。そして、この一致結果ＭＲ２５がエンコーダ３５８によってエンコードされて、Search_Result_2が生成される。
【００４３】
図４Ａは、可変データ幅を実現するための代表的なエントリ４００を、本発明の一実施形態に従って示すブロック図である。エントリ４００は、一致結果インターフェース部分４０２と、タグフィールド４１６と、有効ビットフィールド４１８と、データフィールド４２０と、センスアンプ４２２とを備えている。一致結果インターフェース部分４０２は、インバータ４１２とトランジスタ４１４とを備えている。インバータ４１２は、高位または低位のいずれかである一致結果ＭＲi を受け取る。例えば、高位のＭＲi 信号は直前のブロックエントリでのヒットを示し、低位のＭＲi 信号はミスを示している。エントリ４００が、データ検索のための第１の（例えば、最左端の）ＣＡＭブロック内にある場合には、ＭＲi 信号は、ＭＲi が高位になるよう供給電圧Ｖ＋に接続される。インバータ４１２は、入力ＭＲi 信号を反転させて、反転後の入力信号をトランジスタ４１４に供給する。トランジスタ４１４は、反転後の入力信号が低位である場合（例えば、ＭＲi が高位である場合）にオフとなり、出力ノード３１０における電圧が引き下げられるのを阻止する。一方、反転後の入力信号が高位である場合（例えば、ＭＲi が低位である場合）には、トランジスタは出力ノード３１０における電圧を引き下げる。
【００４４】
出力ノード３１０は、タグフィールド４１６と、有効ビットフィールド４１８と、データフィールド４２０とに接続されている。タグフィールド４１６またはデータフィールド４２０内のビットが１つでも入力データおよびタグ値に一致しない場合、または、有効ビットフィールド４１８内の有効ビットが無効である場合には、ノード３１０の電圧が引き下げられる。これは、エントリ４００で一致が発見されなかったことを意味する。逆に、タグフィールド４１６およびデータフィールド４２０内のビットが全て入力データおよびタグ値に一致し、有効ビットフィールド４１８内の有効ビットが有効である場合には、出力ノードの電圧が引き上げられる。これは、エントリ４００で一致が発見されたことを意味する。ノード３１０における電圧は、入力としてセンスアンプ４２２に供給され、センスアンプ４２２は入力電圧を増幅して、一致結果ＭＲi+1 としての出力を生成する。ＭＲi+1 は、エンコードされてアドレスを形成してもよいし、ブロック内の次のエントリへの入力として送信されてもよい。
【００４５】
なお、当業者には理解できるように、センスアンプ４２２が検索結果３１０を増幅してＭＲi+1 を生成するには、高速動作を実現するために、かなりの量の電流を消費する必要がある。この一致の増幅に要する電力消費は、何千ものエントリが格納された大容量ＣＡＭにおける総電力消費のうちのかなり大きな部分を占める。この問題に対処するには、図４Ｂに示すように、一致センスアンプ４２２を、エントリベーシスによるエントリ上で選択的にイネーブルするとよい。
【００４６】
図４Ｂに示す代表的な実施形態では、ＭＲi 入力と、タグの比較結果４６８と、有効ビットの比較結果４６６とが、ＡＮＤゲート４６０によって論理的にＡＮＤされて、一致センスアンプ４６４を制御するためのローカルなセンスアンプイネーブル信号４６２が生成される。この技術を使用することにより、ＭＲi とタグと有効ビットとの状態が、与えられた検索入力と一致するエントリに対してのみ、一致センスアンプをイネーブルにすることが可能となる。この結果、幅が一致するタグと、有効なデータと、直前のブロックからの一致を示す一致結果とを有するエントリのみが、エントリのデータフィールド４５８内に格納されたデータの比較のために電力を消費する。多数の幅（異なるタグ値）を有するエントリや、無効なエントリを格納するＣＡＭアレイにおいて、省電力を図ることができる。
【００４７】
図４Ｂに示す省電力の技術では、ＭＲi 入力と、タグおよび有効ビットの比較結果とを組み合わせることによって、ローカルな一致センスアンプ４６４をイネーブルにしている。なお、これらの入力の１つまたはそれ以上の任意の組み合わせにより、趣旨を変更することなく、センスの電力消費を部分的に減少できることは明らかである。
【００４８】
図５は、ＣＡＭブロック２５２，２５４，２５６，２５８内で格納および検索される可変データの幅を説明するＣＡＭデバイス２５０を、本発明の一実施形態に従って示す論理ブロック図である。この論理ブロック図に示すように、ＣＡＭデバイス５００は、３２ビット幅から３２ビットずつ増加して１２８ビット幅に至るまでの種々のサイズのデータを格納している。例えば、行５０２，５１６では、エントリ５１８，５２０，５２２，５２４，５５０，５５２，５５４，５５６内に、３２ビット幅のデータが格納されている。一方、行５０４，５１２では、検索のための１２８ビットのデータが格納されている。行５０８では、エントリ５３４に６４ビットのデータが１つ格納されている。
【００４９】
同じ行内に、異なる幅の複数のデータを格納することも可能である。例えば、行５０６，５１０，５１４では、種々の幅のデータが格納されている。具体的には、行５０６では、エントリ５２８内に６４ビットデータが格納されるとともに、一対のエントリ５３０，５３２内に３２ビットデータがそれぞれ格納されている。同様に、行５１０では、一対のエントリ５３６，５３８内に３２ビットのデータがそれぞれ格納されるとともに、エントリ５４０内に６４ビットのデータが格納されている。同様に、行５１４では、エントリ５４４内に９６ビット幅のデータが格納され、エントリ５４８内に３２ビットのデータが格納されている。ＣＡＭデバイス５００内の他の行およびエントリも同様に構成され、これにより、貴重なＣＡＭスペースを無駄にせず、全てのスペースをデータの格納に使用することが可能となる。また、マルチモードのエンコーダを使用する場合には、多数の行に渡ってデータを格納するようにしてもよい。例えば、図５の行５６０，５６２は、２５６ビット幅のエントリ５６４を格納するのに使用されている。
【００５０】
このように、本発明によるＣＡＭデバイスは、検索のために可変幅のデータを格納することにより、ＣＡＭスペースの節約および柔軟性の向上をもたらすことができる。特に、可変幅のデータの格納および検索は、ブロックベーシスに代えてエントリベーシスでタグビットをプログラミングすることを許容することにより、ユーザに十分な柔軟性を提供可能である。また、可変幅のデータを個々のエントリベーシスで格納および検索することにより、従来のＣＡＭマクロに関連して生じた未使用または使用できないＣＡＭスペースを排除して、貴重なＣＡＭスペースを節約することができる。ＣＡＭデバイスの可変幅の格納および検索の能力は、ＩＰｖ４，ＩＰｖ６，ＡＴＭ，ＭＡＣレベルのスイッチング等のマルチプロトコルアプリケーションに対して特に有益である。
【００５１】
実施形態の中には、１セットの行内のエントリが、１つのインターリーブされた行内に配置されたものもある。例えば、図６Ａは、一対の行６０２，６０４と、エンコーダＰＥ１，ＰＥ２，ＰＥ３とを、本発明の一実施形態に従って示す図である。各エンコーダＰＥ１，ＰＥ２，ＰＥ３は、一対のエンコーダ部分を備えている。具体的には、エンコーダＰＥ１はエンコーダ部分ＰＥ1 ，ＰＥ4 を備え、エンコーダＰＥ２はエンコーダ部分ＰＥ2 ，ＰＥ5 を備え、エンコーダＰＥ３はエンコーダ部分ＰＥ3 ，ＰＥ6 を備えている。行６０２は、エントリＥ１，Ｅ２，Ｅ３と、それぞれに関連するエンコーダ部分ＰＥ1 ，ＰＥ2 ，ＰＥ3 とを備えている。同様に、行６０４は、エントリＥ４，Ｅ５，Ｅ６と、それぞれに関連するエンコーダ部分ＰＥ4 ，ＰＥ5 ，ＰＥ6 とを備えている。
【００５２】
行６０２，６０４内のエントリは、１つの行内でインターリーブされていてもよい。図６Ｂは、エントリＥ１〜Ｅ６を備えるインターリーブされた行６０６を、本発明の一実施形態に従って示す図である。インターリーブされた行６０６では、エントリＥ１，Ｅ４が連続する位置に設けられ、その次に、ＰＥ１の関連のエンコーダ部分ＰＥ1 ，ＰＥ4 が続く。そして、エントリＥ２，Ｅ５が設けられ、その次に、関連のエンコーダ部分ＰＥ2 ，ＰＥ5 が続く。さらに、エントリＥ３，Ｅ６が設けられ、その次に、関連のエンコーダ部分ＰＥ3 ，ＰＥ6 が続く。
【００５３】
図６Ｃは、エントリＥ１，Ｅ４および関連のエンコーダ部分ＰＥ1 ，ＰＥ4 の入力および出力信号を示す図である。センスアンプＳＡ1 ，ＳＡ2 は、それぞれエントリＥ１，Ｅ４からの出力信号を増幅するために設けられている。動作中、エントリＥ１，Ｅ４は、それぞれ入力一致結果信号ＭＲi1 ，ＭＲi4 を受け取る。センスアンプＳＡ1 ，ＳＡ4 は、それぞれエントリＥ１，Ｅ４からの出力信号を増幅し、増幅後の出力信号をエンコーダ部分ＰＥ1 ，ＰＥ4 にそれぞれ供給する。これに応じて、エンコーダ部分ＰＥ1 ，ＰＥ4 は、一致結果出力信号ＭＲO1，ＭＲO4をそれぞれ出力し、これらの信号はさらに、インターリーブされた行６０６内の次のエントリＥ１，Ｅ５に提供される。
【００５４】
例えば、適切な半導体基板、プリント回路板、パッケージ化された集積回路、ソフトウェアインプリメンテーションなどを含む任意の形態で、種々のブロック図を具現化できる。したがって、当業者にはわかるように、本明細書で取り上げた実施形態は、例示を目的としたものであって、本発明の内容を限定するものではない。このため本発明は、本明細書で特定した詳細に限定されることなく、添付した特許請求の範囲の範囲および均等物の範囲内で、種々の変更を加えることが可能である。
【図面の簡単な説明】
本発明は、添付図面と関連させた詳細な説明から容易に理解できる。同様の符号は同様の構造エレメントを示している。
【図１Ａ】４つのマクロを有する従来のＣＡＭチップを示すブロック図である。
【図１Ｂ】種々の幅に設定可能なマクロを示すブロック図である。
【図２Ａ】可変データ幅を実現するための代表的なＣＡＭデバイスを、本発明の一実施形態に従って示すブロック図である。
【図２Ｂ】４つのＣＡＭブロックを有する代表的なＣＡＭデバイスを、本発明の一実施形態に従って示すブロック図である。
【図３Ａ】代表的なＣＡＭデバイスの一対のＣＡＭブロック内に設けられた一対のエントリを、本発明の一実施形態に従って詳細に示すブロック図である。
【図３Ｂ】ＣＡＭデバイスにおいて、可変幅のデータを検索するための代表的なメソッドを、本発明の一実施形態に従って示すフローチャートである。
【図３Ｃ】ブロック内の２つまたはそれ以上の隣接した行を使用して、大きな幅のエントリを格納するように構成されたＣＡＭデバイスを、本発明の一実施形態に従って示す図である
【図４Ａ】可変データ幅を実現するための代表的なエントリを、本発明の一実施形態に従って示すブロック図である。
【図４Ｂ】省電力のための代表的なエントリを、本発明の一実施形態に従って示す図である。
【図５】ＣＡＭブロック内で格納および検索される可変データの幅を説明するＣＡＭデバイスを、本発明の一実施形態に従って示す論理ブロック図である。
【図６Ａ】一対の行と、エンコーダＰＥ１，ＰＥ２，ＰＥ３とを、本発明の一実施形態に従って示す図である。
【図６Ｂ】エントリＥ１〜Ｅ６を備えるインターリーブされた行を、本発明の一実施形態に従って示す図である。
【図６Ｃ】エントリＥ１，Ｅ４および関連のエンコーダ部分ＰＥ1 ，ＰＥ4 の入力および出力信号を示す図である。
【図１Ａ】
0004927247.tif 000004
【図１Ｂ】
0004927247.tif 000005
【図２Ａ】
0004927247.tif 000006
【図２Ｂ】
0004927247.tif 000007
【図３Ａ】
0004927247.tif 000008
【図３Ｂ】
0004927247.tif 000009
【図３Ｃ】
0004927247.tif 000010
【図４Ａ】
0004927247.tif 000011
【図４Ｂ】
0004927247.tif 000012
【図５】
0004927247.tif 000013
【図６Ａ】
0004927247.tif 000014
【図６Ｂ】
0004927247.tif 000015
【図６Ｃ】
0004927247.tif 000016