(57)【要約】【課題】主にＲＡＭセルを用いて分類ＣＡＭ機能を実装する方法を開示する。この方法は、所定の領域により多くのテーブルエントリを、または従来の３進ＣＡＭよりも所定のテーブルに対してより小さな領域を提供する。この方法は、より電力効率が良く、低価格で、従来のＣＡＭよりもより優れたレンジの特徴を提示する。【選択図】図６
2007508653.tif 000002
【特許請求の範囲】
【請求項１】
連想メモリを実装する方法であって、
ａ）連想メモリのエントリを異なる複数のグループに分割し、前記何れのグル−プのエントリも２つ以上が所定の入力と一致することなく、かつ前記異なるグループの１つが、比較するビットのスペックが前記２つのグループ全体で共通であるようにグループ分けされる、分割するステップと、
ｂ）前記グループのそれぞれに対する複数のビット位置を識別ビット位置として選択し、前記選択した識別ビット位置のエントリは、前記グループのそれぞれの中でユニークにエントリを識別するのに十分な値を有し、かつ前記グループのそれぞれの中で、前記選択した識別ビット位置で前記エントリの値はｘ（don't care）ではない、選択するステップと、
ｃ）前記選択した識別ビット位置でビット選択器回路を構成するステップと、
ｄ）前記選択した識別ビット位置において、前記エントリからの値でエントリ選択器回路を構成し、そのエントリ選択回路は２値連想メモリであり、マッチング機能を実行する多段回路を備える、構成するステップと、
ｅ）前記エントリ選択器回路の識別ビットに対応する位置で、前記エントリをスペックメモリにロードするステップと、
ｆ）前記エントリビット選択器回路を構成した位置の入力からビットを選択するステップと、
ｇ）前記選択したインプットビットの値と、前記エントリ選択回路を構成する値のうちの１以下の値とを一致させるステップと、
ｈ）前記エントリ選択回路の一致した位置に対応する位置において、前記スペックメモリからエントリを読み出すステップと、
ｉ）前記スペックメモリから読み出した前記エントリを修正するスペックと、
ｊ）前記修正したエントリと、インプットワードとを比較するスペックと、
ｋ）比較した結果を出力するスペックと、
を含む連想メモリを実装する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）
本出願は、Madian Somasundaram氏によって２００３年１０月１１日に出願された「Memory And Power Efficient Content Addressable Memory for General
Classification」という発明の名称の米国特許仮出願番号６０／５１０，７６１に関して、その優先権を主張し、その参照によって援用される。
本発明は、一般に連想メモリ（Content Addressable
Memories（ＣＡＭ）またはassociative memories）に関する。
【背景技術】
【０００２】
連想メモリ（ＣＡＭ）は複数の記憶位置にデータを格納することができる。データをある位置に格納すると、その位置のコンテンツ（データ値）を用いて格納位置をアドレス指定することができる。入力したワードは、許容値のテーブルと比較される。これらが一致した場合は、一致したワードの位置が返送される。その位置は、通常関連したテーブルをアドレル指定するために用いられ、対応するワードが返送される。ＣＡＭはインターネットプロトコル（ＩＰ）パケットの分類に応用され、ＩＰアドレスおよび他のフィールドのインターネットパケットがネットワークスイッチおよびルータ内で比較される。サブネットアドレスまたはアドレスプレフックスと呼ばれるＩＰアドレスの通常の形態は、確定値が一定の数のビットで指定され、アドレスビット以外の残りは「ｘ」（don't care）ビットで指定される。ＩＰｖ４アドレスの１例を以下に示す。
0110
1100 0111 xxxx xxxx xxxx xxxx xxxx
【０００３】
ｘ（don't
care）でないビットがアドレスのプレフィックスを形成し、プレフィックスビットの数をプレフィックス長と呼ぶ。サブセットを分類する用途は、最も長いプレフィクスビットを有するマッチングプレフィクスを識別することである。より一般的な分類用途では、複数のフィールドが同時に一致しなくてはならない。分類における例示のスペックを図１９のテーブルに示す。
【０００４】
分類に他のフィールドを使用してもよい。例えば、１４４ビットのスペックをインターネットプロトコル４バージョン（ＩＰｖ４）に使用することができる。インターネットプロトコル６バージョン（ＩＰｖ６）において、各アドレルフィールドの長さが１２８ビットとなり、分類スペックが５７６ビットを超えることがある。分類スペックのキーキャラクタは、それぞれのフィールドがｘ（don't care）を有することである。それゆえ、分類用のＣＡＭは、必ずしも隣接していないｘ（don't care）ビットを許容しなくてはならない。３進ＣＡＭと呼ばれるＣＡＭの類は、この必要性を満たすために導入され、すべてのデータと関連するエキストラビット（マスクビットと呼ばれる）が存在する。
【０００５】
しかしながら、従来の３進ＣＡＭ構造には多くの不都合がある。各セルは２つのメモリセルと、マスクおよび比較回路とを含むため、ｗ×２ｎサイズのテーブルを実装するには、ｗ×２ｎ＋１個のメモリ素子とｗ×２ｎ個のマスクおよび比較回路が必要である。テーブルをルックアップするためにすべてのセルを起動することが必要なため、電力消費はｗ×２ｎに比例する。ｎは大きな値であるためコストが増大し、莫大な電力消費量となる。更に、すべてのセルで比較ロジックが繰り返されるため、異なる種類の比較を行うには高価となり、かつ困難である。そのため、通常のＣＡＭはビット毎（bit-for-bit）の比較のみを提供している。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
連想メモリシステムにおいて以下が必要である。
１）必要な比較器の数を減らす。
２）純メモリのアレイを使用する。
３）比較器とメモリ素子を分離させる。
４）すべてのビットを比較する前に、潜在的な一致として特定のエントリを選択する。
これらを変更により、メモリ素子と比較器の数が減って実装サイズが縮小し、データエントリのより効率的な比較を行うことによって消費電力が低減する。
【課題を解決するための手段】
【０００７】
コストを低減させるためのインターネットパケット識別に適した連想メモリを、１ビット当たり１つをやや上回るメモリ素子で実装する方法を提供する。本発明によって、より大きなＣＡＭテーブルを備えても著しい省電力化が可能となる。好適な実施形態では、単一の構造体内に多様なルックアップ機能が提供されている。オプションの範囲を、設計段階中（アーキテクチャのスケーリング）、チップの製造中（マスクのプログラミング性）、ＣＡＭを特定の用途に具現する前（フィールドプログラミング性）、ＣＡＭプログラミングのサイクルの間（再プログラミング性）、あるいはＣＡＭの使用サイクルの間（再構築可能度）に活用することができる。本発明の１実施形態によって、ビット毎およびレンジ比較を含む種々の比較が可能となる。他の実施形態において、様々な種類の比較を同一のワード内で併用するか、あるいは様々なＣＡＭエントリを多様に比較することができる。
【発明を実施するための最良の形態】
【０００８】
ここで本発明の実施形態を、図面を参照して説明する。図において、同一または機能的に類似の構成要素には同一番号を付す。また、各参照番号の１番左の数字は、参照番号が最初に使用された図面に相当する。
【０００９】
図１は、ＣＡＭを有する典型的なシステムを示している。幅ｗを有する入力ワード（１０１）は許容値のテーブル（１０２）と比較される。一致があると、一致したワードの位置（１０３）が返される。その位置は通常関連したテーブル（１０４）をアドレス指定するために用いられ、対応するワード（１０５）が返される。
【００１０】
図２は、従来の３進ＣＡＭアレイを示している。データはデータレジスタＤ（２０１）に格納され、マスクはマスクレジスタＭ（２０２）に格納される。値は、比較時にコラムラインＣｏｌ（２０３）に置かれる。比較回路（２０４）はデータ値とＣｏｌラインの値とを比較し、マスクレジスタの値がデータビットの比較が有効と示す場合には比較結果をＭａｔｃｈライン（２０５）に転送する。セル２０６は、ｗ個並び、幅ｗの列（２０７）を形成し、列は２ｎ個並んでテーブルを形成する。複数の列が所定の入力に一致する可能性があるため、優先回路（Priority Circuit）（２０８）を用いてＭａｔｃｈラインの１つを選択する。
【００１１】
図３Ａのブロック図は、本発明の１実施形態に係る、Ｎ×ｎエントリの能力を有するＣＡＭ（３００）を示している。ブロック１（３２０）〜Ｎ（３２１）のＮ個のブロックが存在する。各ブロック内にｎエントリまで格納可能なスペックメモリ（Specification Memory）３０１が存在する。エントリビット選択（Entry
Bit Select）回路３０２は幅ｗの入力ワード３０３から任意のビットを選択する。エントリ選択（Entry
Select）回路３０５は幅ｓｗの選択したビット３０４を用いてスペックメモリからｎエントリのうちの１つを選択する。３０６で出力される選択したエントリは、オプションで翻訳（Interpretation）回路３０７によって修正され、３０８で出力される。入力３０３はオプションで比較ゲートおよび修正（Compare Gate and Modify）回路３１６で修正され、３１０で出力される。比較（Compare）回路３０９は、３０８と３１０とを比較し、Ｍａｔｃｈライン３１１で入力と選択したエントリとが一致しているかどうかを示す。ブロック内の選択したエントリのアドレスはＡｄｄｒ３１２として出力される。ブロックごとに１つ、すなわちＮ個の一致インジケータがあり、１つのブロックが優先回路３１３によって選択され、ブロックの少なくとも１つが一致を示した場合には、優先回路３１３の出力Ｍａｔｃｈ３１５が設定される。出力する選択されたアドレス３１４は、優先回路によって選択されたグループの識別と、ブロック内の一致したエントリのアドレスとを兼ね備えている。
【００１２】
ＣＡＭ３００は、図３Ｂで示すようなシステムで使用される。１実施形態において、ＣＡＭ３００を使用する２つの段階（phase）が存在する。ＣＡＭ３００がエントリをロードする制御段階（Control
Phase）と、ＣＡＭ３００が入力値と格納したエントリとを比較してその結果を返すデータ段階（Data
Phase）とである。監視プロセッサ（Supervisory Processor）３３１は、ＣＡＭ３００の構成レジスタとメモリとにエントリをロードする。ロードすると、ＣＡＭ３００はデータ段階で独立して動作する。このデータ段階では、ＣＡＭ３００は入力３０３を受け入れ、その入力をエントリと比較し、結果として一致インジケータ３１５と選択アドレス３１４とを返す。
【００１３】
制御段階の目的は、ＣＡＭ３００の各ブロック内のエントリの１つのみが所定の入力に一致するようにＣＡＭ３００をロードすることである。その目的を達成するための方法を図３Ｃに一連のステップで示す。開始点３５０は、最大Ｎ×ｎエントリまでを有するテーブルである。第１のステップ３５１において、エントリはそれぞれがｎエントリ以下のＮグループまでに分けられ、各グループ内で１以下のエントリが所定の入力と一致する。以下の３ステップが、ステップ３５１で形成された各グループに対して一回ずつ繰り返される。ステップ３５２で、グループのエントリは、ＣＡＭ３００内の新しいブロックのスペックメモリ３０１内にロードされる。ステップ３５３で、あるビット位置がグループに対して選択され、選択されたビット位置の値により、グループ内の１つのエントリと残りエントリとが区別される。次のステップ３５４で、エントリビット選択３０２はステップ３５３で選択されたビット位置で構成される。次いで、ステップ３５５で、エントリ選択３０５が、スペックメモリ３０１内のエントリの位置に相当する位置のエントリの識別ビットを有するように構成される。
【００１４】
データ段階の目標はＣＡＭ３００で達成される。ＣＡＭ３００の各ブロックは、図３Ｄのフローチャートのように機能する。ステップ３６１において、エントリビット選択で構成されるビット位置が入力３０３から読み出される。ステップ３６２において、エントリ選択３０５が、ステップ３６１で読み出されたビット値を基に、最大１つのエントリを選択する。次のステップ３６３において、選択されたエントリがスペックメモリ３０１から読み出される。オプションのステップ３６４において、スペックメモリからの値が翻訳回路３０７によって修正され、かつ／または、入力が比較ビット選択および解釈回路３１６によって修正される。ステップ３６５において、比較回路３０９は、ステップ３６４からオプションで修正された値を相互に比較し、その結果を出力する。ステップ３６６において、優先回路３１３がすべてのブロックから１つを選択して、選択結果を出力する。
【００１５】
ＣＡＭ３００の動作を、図４に示したＣＡＭエントリの例示のテーブルで示す。例示のテーブルは、それぞれが１３ビットの２０エントリを備え、各ビットは０、１、ｘの３つの可能な状態を有する。テーブルは、図５に示す５エントリ以下を有するグループに分けられ、各グループから１つのみのエントリが所定の入力と一致する。各グループ内で、エントリの間で複数のビットが一意的かつ十分に異なる。これらのビットに陰影をつける（強調する）。エントリをグループ分けする２つ以上の方法があり、２つ以上の識別ビットのセットがある。本発明の様々な実施形態があるため、グループまたはビットの特定の選択については言及しない。エントリビット選択回路３０２は、各グループで強調されたビットが自動的にエントリ選択回路３０５への入力として選択されるようにする。エントリビット選択３０２の潜在的な出力を図５のテーブルにＳＢ０、ＳＢ１、ＳＢ２、ＳＢ３として示す。グループに対するＳＢ０〜３の許容可能な値がエントリ選択３０５にロードされる。グループエントリは、エントリがエントリ選択３０５で見つかった位置と同じ所でスペックメモリ３０１にロードされる。ＳＢ０〜３の入力値が許容値の１つと一致した場合には、スペックメモリ内の対応するエントリが選択され、ライン３０６上の潜在的な一致として出力される。この例では、翻訳回路３０７は出力を修正しないよう構成され、比較ゲートおよび修正回路３１６は、すべての入力ビットを出力するよう構成される。そのため、選択されたエントリは、直接入力ワードと比較される。図６は、第１のグループに対する構成および値と、例示の入力の結果とを示す。エントリビット選択３０２はビット０、５、６、１２をエントリ選択回路３０５への入力として選択する。選択されたビットは、エントリセレクタ３０５の第２のエントリと一致する。スペックメモリ３０１の第２のエントリは読み出され、入力３０３のすべてのビットと比較され、一致する。
【００１６】
スペックメモリブロックは（従来の３進ＣＡＭセルではない）純ＲＡＭセルから構成されるメモリアレイのため、本発明の実施形態は従来のＣＡＭより改善されている。ＲＡＭセルのサイズはＣＡＭセルより小さい。静的ＲＡＭ技術の場合、純ＲＡＭセルの大きさは３進ＣＡＭセルの１／３〜１／５となる。ＤＲＡＭまたは１−Ｔ  ＳＲＡＭ技術を用いてもサイズを縮小することができる。そのため、本発明の実施形態で用いられるメモリセルをＣＡＭセルの１／１０より小さくすることができる。それゆえ、ＣＡＭの実装サイズは従来のＣＡＭの等価サイズよりも相当に小さく（１／３〜１／１０）なる。それゆえ、所定のサイズのシリコンにおいて、本発明に係るＣＡＭは、従来のＣＡＭと比較して、３〜１０倍大きいテーブルを有することができる。本発明の１ビット当たりのコストは１０倍以上下がる。
【００１７】
従来のＣＡＭにおいて、比較回路はアレイの各セルに組み込まれる。そのため、各入力は、ＣＡＭ内のビットと同じ数の比較回路を起動させる。本発明の実施形態において、エントリ選択回路で用いられるいくつかの狭い比較器を除いて、各クループに存在するエントリ幅の比較器の数は１つのみである。それゆえ、一致の計算に要する消費電力もグループのサイズを決めるファクタによって小さくなる。
【００１８】
従来のＣＡＭデバイスと異なる本発明の１実施形態の態様は、メモリ素子を演算／比較素子と分離していることである。この分離により、２つの素子を個別に電力およびコストに対して最適化することができる。例えば、すべてのブロック内の多数の素子に対して複雑性を償却できるため、本発明の実施形態で用いられる比較器はより高度な電力管理技術を使用することができる。別の例としては、比較器の要求による制約を受けずに、低電力なスイングを利用することができる。
【００１９】
実装サイズおよび消費電力は従来のＣＡＭよりもずっと小さくなるため、本発明の実施形態は集積化により適している。より大きいＣＡＭテーブルを１つのダイスに集積可能なだけでなく、ネットワークプロセッサ、トラフィックマネージャ、セキュリティチップなどの複雑なロジックを備えたダイスに、非常に大きなＣＡＭテーブルを集積することができる。比較機能をＣＡＭのメモリと分離することにより、それほどコストをそれほど上げずに、より複雑な比較機能（例えばレンジ比較）を実装することができる。
【００２０】
制御段階において、エントリのグループ化を達成する様々な方法がある。エントリをグループ化する最も効率的な方法は、エントリのテーブルの特徴に依存することである。例えば、エントリがｘ値（don't care）を有しない場合、グループに属するのに最適なエントリを探すタスクは簡単である。なぜならば、すべてのエントリはユニークに定義されていて、エントリがどのようにグループ化されたかに関らず、所与のインプットが１つのエントリとだけ一致する。これは、いわゆるネットワーク業界用語におけるフローテーブルを含む、ネットワークで共通な複数のテーブルに対する一例である。ネットワークアプリケーションで使用される典型的な転送テーブルにおいて、テーブルエントリはプレフィックスの形態を有し、それゆえ連続するｘビット（don't care)を有する。この場合は、複数の方法、例えば、ｘ（don't care）ビットの数によってエントリをグループ化する方法で取り扱うことができる。より一般的な分類の場合、より複雑な方法を採用する必要が生ずる可能性がある。例えば、エントリは、２つのパスアプローチ（pass approach）を用いて予測可能にグループ化してよい。最初のパスで、データは各ノードから３つの潜在的なブランチを有するツリーに編成され、次のパスで、ツリーは様々な方法で考察され、グループが形成される。ツリーの考察を良好に行う考えは、０ブランチおよび１ブランチを有する各ノードで、０ブランチから１つのエントリを、そして１ブランチから１つのエントリを抽出することである。このように選択された２つのエントリは、それらのビット位置が異なるので、同時に一致しないことが保証される。他のオプションとしては、例えばＩＰアドレスに関るような統計情報を用いて、各グループでデータを区別するために用いるビット位置を識別することである。この技術は、区別するビット位置が最初に選ばれ、次いでグループが形成される点で、図３Ｃのフローとは異なる。この技術では、ビット位置の同一のセットをＣＡＭのすべてのグループに使用する必要がない。一方のセットが残りのエントリ間の区別が困難になるまで使用し、次いで他方のセットを使用する。この技術の変形例では、ランダムでビット位置を識別するセットを選択することである。これにより、テーブル内に良好に分布する値を用いて大きなテープルを処理する場合に良好に作用する。
【００２１】
グループに対してエントリの選択は、そのグループに対する識別ビット位置、それゆえ、エントリセレクタ３０５に対して選択されたビット位置の数に関連する。エントリセレクタは任意の数のビット位置を取り扱うことできるようになっているが、制御段階が各グループに対して最少の識別ビット位置を選択した場合には、ロジックを簡単することができる。識別ビット位置の最少の数は、グループ内のエントリの数のｌｏｇ２値であり、必要な最も大きな値は、グループ内のエントリの数より小さい値である。ツリー考察技術、並びにグループを選択前に（ランダムで、またはアプリオリ統計知識を用いて）ビット位置を選択する技術により、ビット位置を識別する最少の数を選択することが支援される。
【００２２】
エントリをグループ化およびビット位置の選択の別の考察は、ｘ値（don't
care）が任意のグループに対する識別ビット位置で許容されるかどうかである。エントリ選択回路の実装は、識別位置でｘ値（don't care）を許容しないことで簡単にすることができる。この場合、制御段階タスクは各グループのエントリ間の識別を、グループ内にｘ値（don't care）が無いビット位置のみを考慮することでエントリをグループ化する。この方法の例を図８に示す。この図では、ｘ値（don't care）がエントリ選択で必要ないように図４のテーブルのエントリがグループ化されている。
【００２３】
ＣＡＭビットに基づくエントリ選択回路３０５の実装を図７に示す。ここでは、選択したビットを保持するのに十分な幅を有するＣＡＭ７０１を用いている。このテーブルの深さは、グループ内のエントリの数と同じである。選択したビット７０２はエントリの最大１つを選択し、ＣＡＭはポインタ７０３を一致した選択ビットベースのエントリに返す。グループのすべてのエントリが（図５のグループ４のように）定義されていないため、有効ビット７０４は各選択判定基準に追加される。その位置にエントリが存在しない場合は、有効ビットは無効にセットされる。図５のようにｘ値（don't care）が識別ビットで許容される場合は、この実装で用いられるＣＡＭセルは３進である必要があり、図８のように許容されない場合は２進となる。
【００２４】
エントリ選択回路３０５のサイズを、複数段階の技術をさらにも用いることで小さくすることができる。図１１は８個の選択したビットを用いて１６エントリの中から選択するエントリ選択情報の例を示す。図１２において、情報はビットで形成された数の大きさによって４つのセグメントに分割されている。灰色で網掛けした複数のビットは、エントリを識別するために使用される。エントリの選択は２つの段階で行われる。第１の段階では、選択したビットＳＢ０〜７のすべてを用いてどのセグメントが当てはまるかを決定し、第２の段階では、ビットＳＢ０〜７のうちのいくつかを用いてセグメント内のエントリを選択する。図１３は２段階のエントリ選択３０５のロジカル動作を示している。図１４は実装例を示している。第２の段階で識別ビットの情報（１４０２）と、アドレスオフセット１４０３とを第２に段階のビット値のＣＡＭ１４０４に含ませる１列のメモリを選択するために、選択したビットＳｅｌ１はマグニチュード比較アレイ１４０１によって使用される。第２の段階で必要なビットの情報は、第２のビット選択回路１４０５に適合しており、この回路はＣＡＭへの入力として提供するのに適切なビットを選定する。単一の段階による選択は、図１１の例示のテーブルに適した１６×８のＣＡＭを要する。図１２の２段階のセレクタの実装は、３つの８ビットマグニチュード比較器と１６×３のＣＡＭが必要である。場合によっては、ＣＡＭをデコーダで代用することができる。複数の段階の回路は、特にグループが大きく、エントリセレクタに多数のビットが存在し、トランジスタ効率のレイテンシのトレードオフを生ずる場合には実装コストを低減する。
【００２５】
制御段階により、選択したビットの数がグループサイズのｌｏｇ２値と正確に同じになる場合には、エントリ選択回路として簡単なデコーダを使用することができる。
【００２６】
図１５はビット選択回路の実装例を示す。選択される入力１５０１のビットは、選択レジスタＳＥＬ１５０２内で「１」値として表される。ロードが指示されると、選択したビットはシフトレジスタ１５０３へロードされる。この例では、各シフトレジステセルで２ビットが存在する。すなわち、シフトレジスタビットがフルか空きがを示すＦ／Ｅ１５０５と、フルの場合のその値を示すＶＡＬ１５０６とが存在する。それゆえ、ビットがロードされた場合、対応するＦ／Ｅビットが「ＦＵＬＬ」と設定され、他のすべてのＦ／Ｅビットが「ＥＭＰＴＹ」と設定される。ロードが完了すると、シフトレジスタはシフティングのために起動される。シフティングは一連のステップで行われる。各ステップにおいて、シフトレジスタは「ＥＭＰＴＹ」の場合には値を「ＦＵＬＬ」位置から左横へ移動させる。このような移動が完了すると、元来の位置を「ＥＭＰＴＹ」と設定し、新しい位置を「ＦＵＬＬ」と設定する。シフティングはシフトが可能な値がなくなるまで続けられる。シフト制御回路１５０７は、現在の位置と過去の位置からＦ／Ｅビットの値を用いて、移動が可能かどうかを判断し、現在と過去の位置でＦ／Ｅの設定および再設定を行う。例示のビット選択の一連のステップを図１６に示す。最後のステップ（ステップ５）までにすべてに選択したビットを一番左のビットに配置し、アウトシグナルによって出力ラインＳＢｉｔ１５０４に向けられる。シフトレジスタが非同期式の場合、すべてのステップをＣＡＭの１サイクルで完了させてよい。
【００２７】
関連するビットを最も重要なビットにシフトさせるのに必要なステップの最悪な数を、図１７の方式を用いて減少させることができる。図１７Ｂに示すように、シフトレジスタの長さは２つ以上のセグメントに分割され、それぞれの長さはｓｗビットである。各シフトレジスタの最も左のビットの出力１７０１は、１番右のビット入力１７０２と接続され、円形のシフトレジスタを形成する。別のビットＰＯＳ１７０３を用いて各セグメントのシフトしたビットの最終位置を示す。シフト処理中には、ＰＯＳ＝１のビットからＰＯＳ＝０のビットへのシフトは許可されない。如何なる位置に対するシフト制御でも、現在位置のＰＯＳ値、並びに過去の位置のＦ／Ｅ位置が考慮される。各セグメント１７０４の最初のビットからの出力が、ビットセレクタ出力Ｓ−Ｂｉｔ１  １７０５の最初のビットと接続されるようにセグメントは重なる。同様に、すべてのセグメントから出力される２番目のビット出力はＳＢｉｔ−２に接続される。単一のセグメントに対するＰＯＳビットは所与のＳＢｉｔ位置に対する１に設定され、何れの所与のセグメントでもすべてのＰＯＳビットが連続するようにＰＯＳビットは構成される。セグメントのシフトレジスタが入力からロードされると、円形のシフトが始まり、最後のステップまでにすべての選択したビットが一番左のＳＢｉｔから正しく並ぶように配置される。円形のシフトレジスタを用いるため、選択したビットの順序は、本来の入力の順序とは異なる可能性がある。図１８はステップの順序を示す。ステップ２に示すようにシフトが完了したら、２つの円形のレジスタは重ならないように並んだフルビットを有し、それらの値は出力ラインにロードされる。ＰＯＳビットはその位置で設定された場合のみ、値が出力される。重ねることにより、この例では５ステップから２ステップへ、ビット選択手続きを完了する時間が短縮される。セグメントの長さが選択したビットの数より短い場合、各セグメントのシフトした値を適切な出力ラインに導くために別の構成ビットが必要である。
【００２８】
従来のＣＡＭでは、ＣＡＭのメモリセルの値の翻訳は、ＣＡＭセルのロジックによって強制的に行われる。それゆえ、典型的な３進ＣＡＭセルにおいて、１つのメモリセルは常に値がｘ（don't care）であるかどうかを示すマスクとして翻訳され、他のメモリセルはｘ値ではないとして翻訳される。本発明の実施形態は、ＣＡＭ内で翻訳機能とメモリを分離している。それゆえ、スペックメモリ３０１に格納された値の種類に対する多くの選択が可能である。これらの選択には、２進、３進、レンジスペック、圧縮スペックなどが挙げられるが、それに限定されるものではない。２進スペックの場合、メモリのｗビットはｗビットサイズの入力のために使用される。３進スペックの場合、メモリの２ｗビットはｗビットサイズの入力のために使用される。レンジスペックの場合、レンジの開始と終わり定義するように２つのフィールドを定義することができる。あるいは、開始とカウントはレンジを定義する別の方法と定義することができる。より大きいまたは小さいフォームを有するレンジフィールドも定義することができる。
【００２９】
圧縮したフィールドは多くの表現が可能である。一例として、幅ｗビットのサブネットアドレスフィールド（プレフィクスアドレスとも呼ばれる）は、標準３進ＣＳＭで２ｗのメモリセルが必要である。本発明の実施形態において、図９に示す符号方式を用いて、単にｗ＋１ビットでｗビットのプレフィックスアドレスを表現することができる。別のビットをｗビットの終わりに付加し、前のビットが比較されるべきかどうかを示すことができる。ビットを比較するべきではない場合、ビットの値は次のビットが比較されるべきかどうかを示す。この処理は、ビットが次のビットは比較されるべきと示すまで続けられる。すべてのビットを比較した後は、（どのビットを比較するかを特定する）マスクビットのスペックがグループ全体と共通になるように、グループエントリによってメモリ要求を減らすことができる。１例として図８の第３のグループを用いた双方の技術は、図１０で使用されている。スペックメモリ１００１はｘ値を有していないが、それぞれプレフィックスビット０〜４および５〜９に関連する２つの新規ビットＸ１およびＸ２を有している。翻訳回路１００２はプレフィックス値としてこれらのフィールドを識別するようになっている。更に、ビット１２はグループ全体に対して「ｘ」であるため、翻訳回路はｘ（don't care）としてビット１２を取り扱うように構成されている。スペックメモリはビット１２に任意の値を有することができる。翻訳回路は符号化形態から元来のエントリを再作成し、再作成されたエントリは比較回路１００３によって入力と比較される。
【００３０】
本発明の翻訳技術について、本発明の潜在的な実施形態として多くの利用可能なオプションが存在する。翻訳オプションはスペックメモリの符号化オプションと相補の関係にある。前述のオプションに加え、この回路に実行時のエラーチェックおよびエラー補正を含ませることができる。これらの機能は、典型的な３進ＣＡＭにおいては提供することが非常に困難である。エントリがどのように翻訳されるかを示すためにスペックメモリ内で別のコードビットが提供される場合、同一のグループ内でエントリからエントリへエントリの実装を変えることができる。これは、入力のあるビットの意味（meaning）が他のあるビットの値と共に変わる場合に有益である。
【００３１】
様々な比較オプション（または他の動作）が回路３０９での比較の実装に利用可能である。比較オプションとしては、ビット毎（bit-for-bit）比較、レンジ比較、様々な軟比較が挙げられるが、これらの限定されるものではない。ビット毎比較は標準ＣＡＭ手法である。レンジ比較はグループ毎に行われるため、安価で実装することができる。比較の特別な形態によって、値の許容またはベクトル距離の演算の許容が可能となる。これは声紋および画像などの「軟」比較には有意になり得る。一般に、ビットをどのように翻訳するかのオプションと比較ブロックのオプションとを組み合わせることにより、本発明の実施形態における複雑なＡＬＵ機能が可能となる。これらのより複雑な動作を行うために使用されるロジックはメモリセル毎ではなく、グループ毎で繰り返されるため、本発明はより複雑なロジックを控えめなコストでサポートする。
【００３２】
いままで示した例は、比較回路の入力ワード全体を使用しており、そのため比較ゲートおよび修正回路がオプションである。しかし、本発明のある実施形態において、この回路は別の有益な機能を備えることができる。例えば、エントリ選択回路で用いられるビットは再び比較される必要が無い場合、比較回路への入力よりもビットを小さくすることができる。これにより、スペックメモリ内のメモリビットの数を減らすことができる。また、任意の動作をブロックで処理する前に、回路内である条件が入力によって満たされるかどうかをチェックすることができる。これは、制御段階において、グループ内のすべてのエントリがある条件を満足するように、グループ内のすべてのエントリが選ばれる場合に、特に有益である。次いで、これらの基準は比較回路および修正回路によって実施されるゲート基準となる。この場合、すべての比較時に、ＣＡＭ３００のすべてのブロックが起動されるわけではないので、より消費電力を節約できる。
【００３３】
本発明の趣旨および本質的な特徴から逸脱しない範囲で、本発明を他の特定の形態で実施することができることは、本技術分野に精通した者ならば理解できるであろう。同様に、モジュール、マネージャ、特徴、属性、他の態様の特定の名称および区分は絶対的なものではなく、重要なものでもない。本発明またはその特徴を実施する機構は種々の名称、区分および／またはフォーマットを有することが可能である。更に、当業者ならば明らかなことではあるが、本発明のモジュール、マネージャ、特徴、属性、方法、他の態様は、ソフトウェア、ハードウェア、ファームウェア、これらの組み合わせとして実装することができる。更に、本発明は、如何なる特定のプログラム言語、動作システム、環境による実装に必ずしも限定されるものではない。それゆえ、本発明の開示は、添付の請求項に記載の本発明の範囲を例示しているに過ぎない。
【図面の簡単な説明】
【００３４】
【図１】従来のＣＡＭシステムを示す図である。
【図２】従来の３進ＣＡＭアレイを示す図である。
【図３Ａ】本発明の１実施形態に係るＣＡＭのブロック図である。
【図３Ｂ】本発明の１実施形態に係るＣＡＭを用いたシステムのブロック図である。
【図３Ｃ】本発明の１実施形態に係る制御段階の技術のフロー図である。
【図３Ｄ】本発明の１実施形態に係るデータ段階の技術のフロー図である。
【図４】ＣＡＭエントリのテーブルの例を示す図である。
【図５】本発明の１実施形態に係る、ＣＡＭを複数のグループに分ける方法の例を示す図である。
【図６】本発明の１実施形態に係る、図５に記載の例で示された第１のグループに対する構成値を示す図である。
【図７】本発明の１実施形態に係る、３進ＣＡＭビットに基づくエントリ選択回路を示す図である。
【図８】本発明の１実施形態に係る、ｘ（don't care）値がエントリ選択器で必要としないようにエントリをグループ化する方法を示す図である。
【図９】本発明の１実施形態に係る、プレフィックススペックを示すコード化方式を示す図である。
【図１０】本発明の１実施形態に係る、図８の第３のグループに対する圧縮されたスペックを示す図である。
【図１１】本発明の１実施形態に係るエントリ選択テーブルの例を示す図である。
【図１２】本発明の１実施形態に係る、４つのセグメントに分割されたエントリ選択テーブルの例を示す図である。
【図１３】本発明の１実施形態に係る２段階エントリ選択器のロジック動作を示す図である。
【図１４】本発明の１実施形態に係る２段階エントリ選択器の実装の例を示す図である。
【図１５】本発明の１実施形態に係るビット選択器の回路を示す図である。
【図１６】本発明の１実施形態に係る、入力からビットを選択する一連のステップを示す図である。
【図１７Ａ】本発明の１実施形態に係る、重なったビット選択回路を示す図である。
【図１７Ｂ】本発明の１実施形態に係る、重なったビット選択回路のセグメントが接続する方法を示す図である。
【図１８】本発明の１実施形態に係る、重なったビット選択回路でビットを選択する一連のステップを示す図である。
【図１９】本発明の１実施形態に係る、分類スペックの例のフォーマットを示す図である。
【図１】
2007508653.tif 000003
【図２】
2007508653.tif 000004
【図３Ａ】
2007508653.tif 000005
【図３Ｂ】
2007508653.tif 000006
【図３Ｃ】
2007508653.tif 000007
【図３Ｄ】
2007508653.tif 000008
【図４】
2007508653.tif 000009
【図５】
2007508653.tif 000010
【図６】
2007508653.tif 000011
【図７】
2007508653.tif 000012
【図８】
2007508653.tif 000013
【図９】
2007508653.tif 000014
【図１０】
2007508653.tif 000015
【図１１】
2007508653.tif 000016
【図１２】
2007508653.tif 000017
【図１３】
2007508653.tif 000018
【図１４】
2007508653.tif 000019
【図１５】
2007508653.tif 000020
【図１６】
2007508653.tif 000021
【図１７Ａ】
2007508653.tif 000022
【図１７Ｂ】
2007508653.tif 000023
【図１８】
2007508653.tif 000024
【図１９】
2007508653.tif 000025
【国際調査報告】
2007508653.tif 000026