内容参照メモリ
【課題】未使用の記憶領域の発生を低減することができる内容参照メモリを提供する。
【解決手段】メモリアレイ２は、複数のバンク１〜Ｎを含み、検索対象のＩＰアドレスを格納する。メモリアレイ２は、可変数のバンクからなる複数のブロックを含む。同一のブロックのバンクにはプリフィックスが同一のＩＰアドレスが格納される。プリサーチ回路５は、ＩＰアドレスを検索データとして受けて、検索データと同一のＩＰアドレスがいずれのブロックに格納されているかをプリサーチする。検索判定部１４は、プリサーチによって特定されたブロックから読み出されたＩＰアドレスと検索データとを比較する。
【解決手段】メモリアレイ２は、複数のバンク１〜Ｎを含み、検索対象のＩＰアドレスを格納する。メモリアレイ２は、可変数のバンクからなる複数のブロックを含む。同一のブロックのバンクにはプリフィックスが同一のＩＰアドレスが格納される。プリサーチ回路５は、ＩＰアドレスを検索データとして受けて、検索データと同一のＩＰアドレスがいずれのブロックに格納されているかをプリサーチする。検索判定部１４は、プリサーチによって特定されたブロックから読み出されたＩＰアドレスと検索データとを比較する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、内容参照メモリに関する。
【背景技術】
【０００２】
近年ルータやスイッチなどのネットワーク機器において、ＩＰアドレスの経路検索用途またはフィルタリングのアクセスコントロールリスト（ＡＣＬ）制御用途として、内容参照メモリ（ＣＡＭ：Content Addressable Memory）が広く用いられるようになってきている。たとえば一例として、ＩＰアドレスのルーティングにおいては、以下の処理が実行される。インターネット環境に設置されたルータまたはスイッチにパケットが到着すると、このルータ／スイッチ内に設けられた内部のネットワークパケットプロセシングユニット（ＮＰＵ）は、到着したパケットのヘッダを解析し、次のホップ先（経路）を見つけるために、アドレス検索を開始する。アドレス検索において、ＣＡＭは、ハードウェアベースでアドレス検索を提供するＬＳＩ（大規模集積回路装置）である。パケットのヘッダに記述される宛先ＩＰアドレスを、次ホップ先アドレス検索のためのサーチ要求データとしてＣＡＭに入力する。ＣＡＭは、内部に予め書込まれて記憶されたＩＰアドレスのデータ列一覧と、この入力されたサーチ要求データとの一斉並列比較を行なう。一致したアドレスが存在する場合、ＣＡＭは、その一致したアドレスのインデックスを出力する。ＮＰＵは、ＣＡＭからの一致アドレスインデックスから、次ホップ先アドレスを参照する。具体的なホップ先アドレスは、ＣＡＭ自身ではなく、別のメモリＬＳＩ、たとえばＳＲＡＭ（スタティック・ランダム・アクセス・メモリ）に書込まれていることが多い。
【０００３】
一方、ＣＡＭ内部に記憶されているデータ列との一致がなかった場合には、到着パケットの次のホップ先アドレスは、ＣＡＭハードウェア検索ではない別の方法、たとえばＣＡＭには記憶されていないが、別の大容量メモリに書込まれている場合には、この大容量メモリへアクセスしてソフトウェアベースでの検索を行なうか、またはそのままパケット廃棄として処理される。ＣＡＭ内部に一致するアドレスが存在せず、ソフトウェアベースの長い検索時間が必要な場合においても、この宛先アドレス（次ホップ先アドレス）は、次回以降同じヘッダを持つパケットが来たときのための学習として、ＣＡＭへの書込および記憶内容の更新が実行されるのが一般的である。この操作により、ソフトウェアによる処理時間の長い検索は１度だけであり、次回からは、再びＣＡＭハードウェアベースでの高速検索が可能となり、アプリケーション上ＣＡＭの長所が拡大される。
【０００４】
上述のように、ＣＡＭのハードウェアベースによるアドレス検索の長所は、その実効サーチ性能の高さである。また、このサーチ性能は、保持するデータ列の大きさ（ビット幅）に拘らず一定である。一般的なメモリを用いたソフトウェアベースでの検索の場合には、これまでツリーを始めさまざまな研究報告がなされている。しかしながら、このようなソフトウェアベースでの検索の場合、一般的には、保持データ量が大きくなるにつれて外部へすべてのデータを読出す時間が長くかかってしまう。すなわち、一般的なメモリを用いる場合、アドレス検索に要する時間は、データベースの容量に比例して大きくなるという特徴があり、これが、近年のインターネット人口の増加を考慮すると、大きな問題となる。したがって、ＣＡＭハードウェアベースのアドレス検索は、そのサーチ性能がデータベースの大きさに依存しないという点においても、このようなパケット転送制御用途向けに高く評価されている。
【０００５】
このようなＣＡＭの構成の一例が、特許文献１（特開２００３−１２３４８２号公報）に示されている。この特許文献１においては、ＳＲＡＭセルが、ＣＡＭセルおよびＴＣＡＭ（３値ＣＡＭ：Ternary CAM）セルに適用される。この特許文献１に示される構成においては、各メモリセルに、一致検出回路（ＸＯＲ回路）が設けられ、記憶データビットと検索データビットとの一致／不一致の判定が各ビット単位で実行される。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−１２３４８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで、ＣＡＭは、ＩＰアドレスのプリフィックスごとにブロック化されることがある。プリフィックスが８ビットの場合、ＣＡＭは、２５６個のブロックに分割される。各ブロックには、同一のメモリ容量が与えられる。
【０００８】
しかしながら、インターネット内を伝送するＩＰアドレスのプリフィックスは等しく平均化されるものではない。あるプリフィックスのＩＰアドレスについては、多種類が伝送されるが、別のプリフィックスのＩＰアドレスについては、少ない種類しか伝送されない場合がある。
【０００９】
図１４（ａ）は、ＩＰアドレスの有効ビット長が２４ビットの場合に、各プリフィックス（上位８ビット）ごとに、インターネット上に伝送されるＩＰアドレスのビットパターンの種類を表わす図である。
【００１０】
図１４（ｂ）は、ＩＰアドレスの有効ビット長が２３ビットの場合に、各プリフィックス（上位８ビット）ごとに、インターネット上に伝送されるＩＰアドレスのビットパターンの種類を表わす図である。
【００１１】
図１４（ｃ）は、ＩＰアドレスの有効ビット長が１８ビットの場合に、各プリフィックス（上位８ビット）ごとに、インターネット上に伝送されるＩＰアドレスのビットパターンの種類を表わす図である。
【００１２】
図１４（ａ）〜（ｃ）に示すように、伝送されるＩＰアドレスのビットパターンの種類が多いプリフィックスもあれば、伝送されるＩＰアドレスのビットパターンの種類が少ないプリフィックスもあることがわかる。
【００１３】
上述のような場合には、ブロックのメモリ容量が同一であるにもかかわらず、あるプリフィックスに対応するブロックには、多量のＩＰアドレスが書込まれるが、別のプリフィックスに対応するブロックには、少量のＩＰアドレスしか書込まれない状態となり、メモリの使用効率が低くなる。その結果、無駄に電力が消費されることになる。
【００１４】
それゆえに、本発明の一実施形態の目的は、未使用の記憶領域の発生を低減することができる内容参照メモリを提供することである。
【課題を解決するための手段】
【００１５】
本発明の一実施形態の内容参照メモリは、複数のバンクを含み、検索対象のＩＰアドレスを格納するメモリアレイを備え、メモリアレイは、可変数のバンクからなる複数のブロックを含み、同一のブロックのバンクにはプリフィックスが同一のＩＰアドレスが格納される。内容参照メモリは、ＩＰアドレスを検索データとして受けて、検索データと同一のＩＰアドレスがいずれのブロックに格納されているかをプリサーチするプリ検索部と、プリサーチによって特定されたブロックから読み出されたＩＰアドレスと検索データとを比較する検索判定部とをさらに備える。
【発明の効果】
【００１６】
本発明の一実施形態によれば、未使用の記憶領域の発生を低減することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施の形態の半導体装置を表わす図である。
【図２】（ａ）は、バンク内のエントリを表わす図である。（ｂ）は、エントリに格納されるデータを表わす図である。
【図３】ブロック１〜２５６に属するバンクを表わす図である。
【図４】図３に示すように複数のバンクがブロック化されている場合に、ブロックｉ用制御回路ごとのブロック化支援回路１３のバンクアドレスレジスタ群に記憶されるデータの例を表わす図である。
【図５】図３に示すように複数のバンクがブロック化されている場合に、ブロックｉ用制御回路のアドレスカウンタ１０１に記憶されるデータの例を表わす図である。
【図６】（ａ）〜（ｃ）は、ＦＩＦＯメモリ９１に格納されるデータの例を表わす図である。
【図７】検索判定部１４の概略構成を説明するための図である。
【図８】検索判定部１４の詳細を表わす図である。
【図９】ブロック化支援回路１３の構成を表わす図である。
【図１０】エントリ消去回路１２の構成を表わす図である。
【図１１】エントリ消去動作を説明するための図である。
【図１２】エントリ消去動作を説明するための図である。
【図１３】第２の実施形態の検索判定部１４の例を表わす図である。
【図１４】（ａ）〜（ｃ）は、各プリフィックス（上位８ビット）ごとに、インターネット上に伝送されるＩＰアドレスのビットパターンの種類を表わす図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施形態について、図面を用いて説明する。
［第１の実施形態］
図１は、本発明の実施の形態の半導体装置１を表わす図である。
【００１９】
図１を参照して、この半導体装置１は、メモリアレイ２と、制御回路３とを備える。
メモリアレイ２は、内部参照メモリセル（ＣＡＭセル）であるユニットセルＵＣが行列状に配列される。
【００２０】
メモリアレイ２は、行を単位として複数のエントリに分割される。各エントリに対しては、対応のエントリ内のユニットセルＵＣが並列に結合されるマッチラインが設けられる。また、メモリアレイ２の列方向に、検索データを伝達するサーチライン対が設けられる。このサーチライン対とマッチラインの交差部に対応してユニットセルが設けられる。
【００２１】
メモリアレイ２は、バンク１〜バンクＮのＮ個のバンクに分割される。各バンクは、図２（ａ）に示すように、エントリ１〜エントリＫのＫ個のエントリを有する。各エントリには、図２（ｂ）に示すように、サーチ対象である３２ビットのＩＰアドレス（情報データ）と、３２ビットのホップ先アドレスとが記憶される。
【００２２】
各ブロックのバンクの数は可変であり、最大Ｌ個である。同一のブロックのバンクにはプリフィックス（先頭の８ビットのネットワークアドレス部分）が同一のネットワークアドレスが格納される。
【００２３】
制御回路３は、ブロックｉ用制御回路１０−ｉ（ｉ＝１〜２５６）と、バンク管理部４と、プリサーチ回路５と、検索判定部１４と、ブロック管理部９３、書込部９５と、消去部９４とを備える。
【００２４】
各ブロックｉ用制御回路１０−ｉは、ブロック化支援回路１３と、アドレスカウンタ１０１とを備える。
【００２５】
ブロック化支援回路１３は、対応するブロックに属するバンクのアドレスを記憶するバンクアドレスレジスタ群を含む。
【００２６】
アドレスカウンタ１０１は、対応のブロックに属する書込対象のバンクのエントリの位置を指示する。
【００２７】
プリサーチ回路５は、外部から与えられる検索データ（３２ビットのＩＰアドレス）のプリフィックス部分である先頭の８ビットに基づいて、検索データがブロック１〜ブロック２５６のいずれに属するかを判定する。
【００２８】
検索判定部１４は、プリサーチによって特定されたブロックの各エントリからデータを読み出して、読み出したデータに含まれるＩＰアドレスと検索データとを比較して、一致した場合に、そのＩＰアドレスとともに読み出されたホップ先アドレスを出力する。
【００２９】
バンク管理部４は、未使用バンクを表わす情報を保持するバンクＦＩＦＯ（First In First Out）メモリ９１を含む。バンク管理部４は、初期状態では、メモリアレイ２に含まれるすべてのバンクのアドレスをＦＩＦＯメモリ９１に格納する。バンク管理部４は、ＩＰアドレスをメモリアレイ２の未使用のバンクに書込み必要が生じた際には、ＦＩＦＯメモリ９１から未使用バンクのアドレスを読み出して、読み出した情報に基づいて、未使用バンクをＩＰアドレスを書込むバンクとして割り当てる。ここで、ＩＰアドレスをメモリアレイ２の未使用のバンクに書込み必要が生じる場合とは、ＩＰアドレスの書込みを指示された場合において、書込み中（使用中）のバンクの未使用領域がなくなった場合（すなわち、全エントリが使用されているとき）である。また、バンク管理部４は、バンク内のすべてのエントリが消去された際に、消去されたバンクのアドレスをＦＩＦＯメモリ９１に格納する。
【００３０】
ブロック管理部９３は、バンク管理部４によって新たに割り当てられたバンクをＩＰアドレスのプリフィックスに基づいて、いずれのブロックに属するかを特定する。ブロック管理部９３は、特定されたブロックに対応するブロック化支援回路１３に含まれるバンクアドレスレジスタ群に新たに割り当てられたバンクのアドレスを格納する。
【００３１】
書込部９５は、書込み時に、書込対象のバンクが属するブロックのアドレスカウンタ１０１で示されるエントリの位置にＩＰアドレスを書込み、その後、そのアドレスカウンタ１０１の値を１だけ増加させる。
【００３２】
消去部９４は、バンク内のエントリを消去する際に、バンクの使用領域の末尾のエントリに格納されているデータで、消去するエントリを上書きし、その後、バンクが属するブロックのアドレスカウンタ１０１の値を１だけ減少させる。
【００３３】
図３〜図６は、ブロック化の例を説明するための図である。
図３は、ブロック１〜２５６に属するバンクを表わす図である。
【００３４】
図３に示すように、バンク１、７はブロック１に属する。バンク２、５、６、８、１０は、ブロック２に属する。バンク３は、ブロック３に属する。バンク４は、ブロック４に属する。バンク９は、ブロック５に属する。バンク６８７、７４３は、ブロック２５６に属する。
【００３５】
図４は、図３に示すように複数のバンクがブロック化されている場合に、ブロックｉ用制御回路ごとのブロック化支援回路１３のバンクアドレスレジスタ群に記憶されるデータの例を表わす図である。
【００３６】
ブロック１用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク１のアドレスと、バンク７のアドレスを記憶する。ブロック２用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク２のアドレスと、バンク５のアドレスと、バンク６のアドレスと、バンク８のアドレスと、バンク１０のアドレスとを記憶する。ブロック３用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク３のアドレスを記憶する。ブロック４用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク４のアドレスを記憶する。ブロック５用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク９のアドレスを記憶する。ブロック２５６用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク６８７のアドレスと、バンク７４３のアドレスとを記憶する。
【００３７】
図５は、図３に示すように複数のバンクがブロック化されている場合に、ブロックｉ用制御回路のアドレスカウンタ１０１に記憶されるデータの例を表わす図である。
【００３８】
図５に示すように、ブロック１用制御回路のアドレスカウンタ１０１は、エントリ５のアドレスを記憶する。したがって、図４と図５によって、バンク７のエントリ５が現在又は次の書込対象のエントリとなる。ブロック２用制御回路のアドレスカウンタ１０１は、エントリ７のアドレスを記憶する。したがって、図４と図５によって、バンク１０のエントリ７が現在又は次の書込対象のエントリとなる。ブロック３用制御回路のアドレスカウンタ１０１は、エントリ５のアドレスを記憶する。したがって、図４と図５によって、バンク３のエントリ５が現在又は次の書込対象のエントリとなる。ブロック４用制御回路のアドレスカウンタ１０１は、エントリ１のアドレスを記憶する。したがって、図４と図５によって、バンク４のエントリ１が現在又は次の書込対象のエントリとなる。ブロック５用制御回路のアドレスカウンタ１０１は、エントリ１２のアドレスを記憶する。したがって、図４と図５によって、バンク９のエントリ１２が現在又は次の書込対象のエントリとなる。ブロック２５６用制御回路のアドレスカウンタ１０１は、エントリ４３のアドレスを記憶する。したがって、図４と図５によって、バンク７４３のエントリ４３が現在又は次の書込対象のエントリとなる。
【００３９】
図６（ａ）は、ＦＩＦＯメモリ９１に初期状態（ブロック化前）に格納されるデータの例を表わす図である。
【００４０】
初期状態では、ＦＩＦＯには、バンク１〜バンクＮのアドレスが格納される。エントリへの書込み時に、新たなバンクを割当る時には、バンク１のアドレスから順次取り出される。取り出されたアドレスで指定されるバンクのエントリに図２（ｂ）に示すようなデータが書込まれる。
【００４１】
図６（ｂ）は、バンク１〜バンク７が利用されて、データが書込まれた状態を表わす図である。
【００４２】
バンクに含まれる全エントリのデータが消去された場合には、バンクは解放され、再割当可能となる。たとえば、バンク５が解放された場合に、図６（ｃ）に示すように、消去部９４によって解放されたバンクのアドレスがＦＩＦＯメモリ９１の末尾に格納される。
【００４３】
（検索判定部１４）
図７は、検索判定部１４の概略構成を説明するための図である。
【００４４】
プリサーチによって、検索データがブロック１に属することがわかった場合に、バンク１の各エントリの情報データ（ＩＰアドレス）が順次比較器６０＿１に出力される。比較器６０＿１は、検索データと、各エントリの情報データとが一致するか否かを比較して、比較結果を出力する。同時に、バンク７の各エントリのデータ各エントリの情報データ（ＩＰアドレス）が順次比較器６０＿２に出力される。比較器６０＿２は、検索データと、各エントリの情報データとが一致するか否かを比較して、比較結果を出力する。論理回路Ｒは、比較器６０＿１の出力と比較器６０＿２の出力とを論理演算して、演算結果を出力する。
【００４５】
図８は、検索判定部１４の詳細を表わす図である。
図８を参照してプリサーチ回路５で特定されたブロックに属するバンクからエントリのデータ（ＩＰアドレスとホップ先アドレス）が出力される。
【００４６】
各バンクと接続する比較器６０は、外部から与えられる検索データとＩＰアドレスとを比較して、比較結果を論理回路Ｒ１、および論理回路ＲＲ１〜ＲＲＮのうち、特定されたブロックに属するバンクと接続される論理回路へ出力する。論理回路ＲＲ１〜ＲＲＮのうち、特定されたブロックに属するバンクと接続される論理回路には、接続されるバンクのエントリのホップ先アドレスが入力される。
【００４７】
論理回路Ｒ１は、比較器６０＿１〜６０＿Ｎでの比較のうち一致したものがある場合には、Ｈｉｔを示す信号を出力する。
【００４８】
論理回路ＲＲ１〜ＲＲＮのうち、特定されたブロックに属するバンクと接続する論理回路は、そのバンクでＨｉｔしたとき（つまり、接続される比較器が一致を示す信号を出力したとき）には、入力されたホップ先アドレスを出力し、そのバンクでＭｉｓｓしたときには、全ビットが０の信号を出力する。
【００４９】
論理回路Ｒ３は、Ｈｉｔしたバンクのエントリのホップ先アドレスを出力する。論理回路Ｒ２およびラッチ回路ＲＡ１によって、ＨｉｔまたはＭｉｓｓの結果を更新されるまで維持し、出力する。論理回路Ｒ３、セレクタＳＬ１およびラッチ回路ＲＡ２によって、ホップ先アドレスを更新されるまで維持し、出力する。
【００５０】
（ブロック化支援回路１３）
図９は、ブロック化支援回路１３の構成を表わす図である。
【００５１】
図９を参照して、カウンタ１３４は、バンクアドレスレジスタ３６＿１〜３６＿Ｎのうちバンクアドレスが格納されているレジスタの個数をカウントする。
【００５２】
セレクタ３２は、バンクアドレスレジスタ３６＿１〜３６＿Ｎのいずれかを指定するアドレス、またはカウンタ１３４のカウンタ値を受けて、どちらかを出力する。バンクアドレスレジスタ３６＿１〜３６＿Ｎのいずれかを指定するアドレスは、メモリアレイ２への書込み時に、このグループ支援回路が対応するブロックへのバンクの割当があった場合に、入力される。
【００５３】
デコーダ３０は、セレクタ３２の出力信号をデコードする。デコーダ３０の出力によって、論理回路ＲＬ１〜ＲＬ＿Ｌのいずれかが選択される。またＡＬＬ＿ｓｅｌｅｃｔ信号が入力されるときには、論理回路ＲＬ＿１〜ＲＬ＿Ｌのすべてが選択される。
【００５４】
メモリアレイ２への書込み時には、選択された論理回路ＲＬ＿ｉと接続されているバンクアドレスレジスタ３６＿ｉに、ライトデータ（バンクアドレス）が書込まれる。
【００５５】
また、メンテナンス時には、選択された論理回路ＲＬ＿ｉと接続されているバンクアドレスレジスタ３６＿ｉからリードデータ（バンクアドレス）が読み出される。
【００５６】
（エントリ消去）
消去部９４は、ブロックごとにエントリ消去回路１２を含む。
【００５７】
図１０は、エントリ消去回路１２の構成を表わす図である。
メモリＡ１０２は、メモリアレイ２内のバンクを表わす。
【００５８】
メモリＢ１０４は、検索のために使用するデータを格納するものである。
アドレスカウンタ１０１は、メモリＡ（バンク内）で使用されている末尾のエントリの番号をセレクタ１０３へ出力する。
【００５９】
セレクタ１０３は、命令が入力されて、この命令をメモリＡへの命令（Ａ＿命令）またはメモリＢへの命令（Ｂ＿命令）として出力する。
【００６０】
セレクタ１０３は、アドレスが入力されて、このアドレスをメモリＡへのアドレス（Ａ＿アドレス）、メモリＢへのアドレス（Ｂ＿アドレス）として出力する。
【００６１】
セレクタ１０３は、ライトデータ、メモリＡからのリードデータ（Ａ＿リードデータ）、メモリＢからのリードデータ（Ｂ＿リードデータ）とが入力されて、これらをメモリＡへのライトデータ（Ａ＿ライトデータ）、メモリＢへのライトデータ（Ｂ＿ライトデータ）として出力する。
【００６２】
図１１は、エントリ消去動作を説明するための図である。
１つのバンクに０〜ｎ番目のエントリが使用され、アドレス順に０〜ｎ番目のエントリが存在する場合に、エントリ消去回路は、ｋ番目のエントリを消去する場合に、末尾に存在するｎ番目のエントリのデータを読み出して、ｋ番目のエントリに上書きする。そして、ｎ番目のエントリを未使用領域として解放し、使用領域を０〜（ｎ−１）番目のエントリとする。これによって、消去したエントリを再利用することができる。
【００６３】
図１２は、エントリ消去動作を説明するための図である。
ｎ番目のエントリ（アドレスがｎとする）から読み出したデータをＫｅｙ１＋メモリＢのｉアドレスとする。Ｋｅｙ１は、ＩＰアドレスで、メモリＢのｉアドレスは、ホップ先アドレスである。
【００６４】
一方、ｋ番目のエントリ（アドレスがｋとする）に格納されているデータがＫｅｙ２＋メモリＢのｊアドレスであるとする。Ｋｅｙ２は、ＩＰアドレスで、メモリＢのｊアドレスは、ホップ先アドレスである。ｋ番目のエントリは、ｎ番目のエントリのデータで上書きされるので、ｋ番目のエントリのデータは、Ｋｅｙ１＋メモリＢのｉアドレスとなる。
【００６５】
一方、メモリＢのｉアドレスには、メモリＡのｎアドレスが格納され、メモリＢのｊアドレスには、メモリＡのｋアドレスが格納されている。
【００６６】
以上のように、本実施の形態によれば、プリフィックス毎の使用状況に偏りが発生した場合にも状況に応じてメモリを使用するため、未使用領域を発生させることなく効率よくメモリを使い切ることができる。
【００６７】
［第２の実施形態］
図１３は、第２の実施形態の検索判定部１４の例を表わす図である。
【００６８】
この検索判定部１４は、ブロック１〜ブロック２５６において、同時に並行して検索処理が実行できる。
【００６９】
セレクタ５０−ｉは、バンク１〜バンクＮのうち、ブロックｉに属するバンクのエントリと検索データとを比較する比較器と接続する。
【００７０】
ブロック１に属するバンク１の各エントリの情報データ（ＩＰアドレス）と検索データとを比較する比較器６０＿１の比較結果と、ブロック１に属するバンク７の各エントリの情報データ（ＩＰアドレス）を比較する比較器６０＿７の比較結果がセレクタ５０−１に送られる。セレクタ５０−１は、これらの２つの比較器６０＿１，６０＿７からの信号を論理回路５２−１に出力する。論理回路５２−１で２つの比較器６０＿１，６０＿７からの出力される信号を論理演算して、演算結果を出力する。
【００７１】
同時に、ブロック２に属するバンク２，５，６，８，１０の各エントリの情報データ（ＩＰアドレス）と検索データとを比較する比較器６０＿２，６０＿５，６０＿６，６０＿８，６０＿１０の比較結果がセレクタ５０−２に送られる。セレクタ５０−２は、これらの比較器６０＿２，６０＿５，６０＿６，６０＿８，６０＿１０からの信号を論理回路５２−２に出力する。論理回路５２−２で４つの比較器６０＿２，６０＿５，６０＿６，６０＿８，６０＿１０からの出力される信号を論理演算して、演算結果を出力する。
【００７２】
同様に、同時にブロック３〜ブロック２５６についても、上述と同様にして検索データとの一致／不一致が判定される。
【００７３】
並列処理方法の場合は、同時に各プリフィックスで使用されるブロックを動作させ検索を行い、検索結果をプライオリティエンコーダによって選別する。
【００７４】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【００７５】
１ 半導体装置、２ メモリアレイ、３ 制御回路、４ バンク管理部、５ プリサーチ回路、１４ 検索判定部、１０−１〜１０−２５６ ブロック制御回路、１３ ブロック化支援回路、３０ デコーダ、３６＿１〜３６＿Ｎ バンクアドレスレジスタ、６０＿１〜６０＿Ｎ 比較器、９１ ＦＩＦＯメモリ、９３ ブロック管理部、９４ 消去部、９５ 書込部、１０１ アドレスカウンタ、１０２ メモリＡ、１０４ メモリＢ、１３４ カウンタ、Ｒ，Ｒ１，Ｒ２，ＲＲ１〜ＲＲＮ，Ｒ３ 論理回路、３２，ＳＬ１，１０３ セレクタ回路、ＲＬ＿１〜ＲＬ＿Ｎ，ＲＡ１，ＲＡ２ ラッチ回路。
【技術分野】
【０００１】
本発明は、内容参照メモリに関する。
【背景技術】
【０００２】
近年ルータやスイッチなどのネットワーク機器において、ＩＰアドレスの経路検索用途またはフィルタリングのアクセスコントロールリスト（ＡＣＬ）制御用途として、内容参照メモリ（ＣＡＭ：Content Addressable Memory）が広く用いられるようになってきている。たとえば一例として、ＩＰアドレスのルーティングにおいては、以下の処理が実行される。インターネット環境に設置されたルータまたはスイッチにパケットが到着すると、このルータ／スイッチ内に設けられた内部のネットワークパケットプロセシングユニット（ＮＰＵ）は、到着したパケットのヘッダを解析し、次のホップ先（経路）を見つけるために、アドレス検索を開始する。アドレス検索において、ＣＡＭは、ハードウェアベースでアドレス検索を提供するＬＳＩ（大規模集積回路装置）である。パケットのヘッダに記述される宛先ＩＰアドレスを、次ホップ先アドレス検索のためのサーチ要求データとしてＣＡＭに入力する。ＣＡＭは、内部に予め書込まれて記憶されたＩＰアドレスのデータ列一覧と、この入力されたサーチ要求データとの一斉並列比較を行なう。一致したアドレスが存在する場合、ＣＡＭは、その一致したアドレスのインデックスを出力する。ＮＰＵは、ＣＡＭからの一致アドレスインデックスから、次ホップ先アドレスを参照する。具体的なホップ先アドレスは、ＣＡＭ自身ではなく、別のメモリＬＳＩ、たとえばＳＲＡＭ（スタティック・ランダム・アクセス・メモリ）に書込まれていることが多い。
【０００３】
一方、ＣＡＭ内部に記憶されているデータ列との一致がなかった場合には、到着パケットの次のホップ先アドレスは、ＣＡＭハードウェア検索ではない別の方法、たとえばＣＡＭには記憶されていないが、別の大容量メモリに書込まれている場合には、この大容量メモリへアクセスしてソフトウェアベースでの検索を行なうか、またはそのままパケット廃棄として処理される。ＣＡＭ内部に一致するアドレスが存在せず、ソフトウェアベースの長い検索時間が必要な場合においても、この宛先アドレス（次ホップ先アドレス）は、次回以降同じヘッダを持つパケットが来たときのための学習として、ＣＡＭへの書込および記憶内容の更新が実行されるのが一般的である。この操作により、ソフトウェアによる処理時間の長い検索は１度だけであり、次回からは、再びＣＡＭハードウェアベースでの高速検索が可能となり、アプリケーション上ＣＡＭの長所が拡大される。
【０００４】
上述のように、ＣＡＭのハードウェアベースによるアドレス検索の長所は、その実効サーチ性能の高さである。また、このサーチ性能は、保持するデータ列の大きさ（ビット幅）に拘らず一定である。一般的なメモリを用いたソフトウェアベースでの検索の場合には、これまでツリーを始めさまざまな研究報告がなされている。しかしながら、このようなソフトウェアベースでの検索の場合、一般的には、保持データ量が大きくなるにつれて外部へすべてのデータを読出す時間が長くかかってしまう。すなわち、一般的なメモリを用いる場合、アドレス検索に要する時間は、データベースの容量に比例して大きくなるという特徴があり、これが、近年のインターネット人口の増加を考慮すると、大きな問題となる。したがって、ＣＡＭハードウェアベースのアドレス検索は、そのサーチ性能がデータベースの大きさに依存しないという点においても、このようなパケット転送制御用途向けに高く評価されている。
【０００５】
このようなＣＡＭの構成の一例が、特許文献１（特開２００３−１２３４８２号公報）に示されている。この特許文献１においては、ＳＲＡＭセルが、ＣＡＭセルおよびＴＣＡＭ（３値ＣＡＭ：Ternary CAM）セルに適用される。この特許文献１に示される構成においては、各メモリセルに、一致検出回路（ＸＯＲ回路）が設けられ、記憶データビットと検索データビットとの一致／不一致の判定が各ビット単位で実行される。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−１２３４８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで、ＣＡＭは、ＩＰアドレスのプリフィックスごとにブロック化されることがある。プリフィックスが８ビットの場合、ＣＡＭは、２５６個のブロックに分割される。各ブロックには、同一のメモリ容量が与えられる。
【０００８】
しかしながら、インターネット内を伝送するＩＰアドレスのプリフィックスは等しく平均化されるものではない。あるプリフィックスのＩＰアドレスについては、多種類が伝送されるが、別のプリフィックスのＩＰアドレスについては、少ない種類しか伝送されない場合がある。
【０００９】
図１４（ａ）は、ＩＰアドレスの有効ビット長が２４ビットの場合に、各プリフィックス（上位８ビット）ごとに、インターネット上に伝送されるＩＰアドレスのビットパターンの種類を表わす図である。
【００１０】
図１４（ｂ）は、ＩＰアドレスの有効ビット長が２３ビットの場合に、各プリフィックス（上位８ビット）ごとに、インターネット上に伝送されるＩＰアドレスのビットパターンの種類を表わす図である。
【００１１】
図１４（ｃ）は、ＩＰアドレスの有効ビット長が１８ビットの場合に、各プリフィックス（上位８ビット）ごとに、インターネット上に伝送されるＩＰアドレスのビットパターンの種類を表わす図である。
【００１２】
図１４（ａ）〜（ｃ）に示すように、伝送されるＩＰアドレスのビットパターンの種類が多いプリフィックスもあれば、伝送されるＩＰアドレスのビットパターンの種類が少ないプリフィックスもあることがわかる。
【００１３】
上述のような場合には、ブロックのメモリ容量が同一であるにもかかわらず、あるプリフィックスに対応するブロックには、多量のＩＰアドレスが書込まれるが、別のプリフィックスに対応するブロックには、少量のＩＰアドレスしか書込まれない状態となり、メモリの使用効率が低くなる。その結果、無駄に電力が消費されることになる。
【００１４】
それゆえに、本発明の一実施形態の目的は、未使用の記憶領域の発生を低減することができる内容参照メモリを提供することである。
【課題を解決するための手段】
【００１５】
本発明の一実施形態の内容参照メモリは、複数のバンクを含み、検索対象のＩＰアドレスを格納するメモリアレイを備え、メモリアレイは、可変数のバンクからなる複数のブロックを含み、同一のブロックのバンクにはプリフィックスが同一のＩＰアドレスが格納される。内容参照メモリは、ＩＰアドレスを検索データとして受けて、検索データと同一のＩＰアドレスがいずれのブロックに格納されているかをプリサーチするプリ検索部と、プリサーチによって特定されたブロックから読み出されたＩＰアドレスと検索データとを比較する検索判定部とをさらに備える。
【発明の効果】
【００１６】
本発明の一実施形態によれば、未使用の記憶領域の発生を低減することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施の形態の半導体装置を表わす図である。
【図２】（ａ）は、バンク内のエントリを表わす図である。（ｂ）は、エントリに格納されるデータを表わす図である。
【図３】ブロック１〜２５６に属するバンクを表わす図である。
【図４】図３に示すように複数のバンクがブロック化されている場合に、ブロックｉ用制御回路ごとのブロック化支援回路１３のバンクアドレスレジスタ群に記憶されるデータの例を表わす図である。
【図５】図３に示すように複数のバンクがブロック化されている場合に、ブロックｉ用制御回路のアドレスカウンタ１０１に記憶されるデータの例を表わす図である。
【図６】（ａ）〜（ｃ）は、ＦＩＦＯメモリ９１に格納されるデータの例を表わす図である。
【図７】検索判定部１４の概略構成を説明するための図である。
【図８】検索判定部１４の詳細を表わす図である。
【図９】ブロック化支援回路１３の構成を表わす図である。
【図１０】エントリ消去回路１２の構成を表わす図である。
【図１１】エントリ消去動作を説明するための図である。
【図１２】エントリ消去動作を説明するための図である。
【図１３】第２の実施形態の検索判定部１４の例を表わす図である。
【図１４】（ａ）〜（ｃ）は、各プリフィックス（上位８ビット）ごとに、インターネット上に伝送されるＩＰアドレスのビットパターンの種類を表わす図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施形態について、図面を用いて説明する。
［第１の実施形態］
図１は、本発明の実施の形態の半導体装置１を表わす図である。
【００１９】
図１を参照して、この半導体装置１は、メモリアレイ２と、制御回路３とを備える。
メモリアレイ２は、内部参照メモリセル（ＣＡＭセル）であるユニットセルＵＣが行列状に配列される。
【００２０】
メモリアレイ２は、行を単位として複数のエントリに分割される。各エントリに対しては、対応のエントリ内のユニットセルＵＣが並列に結合されるマッチラインが設けられる。また、メモリアレイ２の列方向に、検索データを伝達するサーチライン対が設けられる。このサーチライン対とマッチラインの交差部に対応してユニットセルが設けられる。
【００２１】
メモリアレイ２は、バンク１〜バンクＮのＮ個のバンクに分割される。各バンクは、図２（ａ）に示すように、エントリ１〜エントリＫのＫ個のエントリを有する。各エントリには、図２（ｂ）に示すように、サーチ対象である３２ビットのＩＰアドレス（情報データ）と、３２ビットのホップ先アドレスとが記憶される。
【００２２】
各ブロックのバンクの数は可変であり、最大Ｌ個である。同一のブロックのバンクにはプリフィックス（先頭の８ビットのネットワークアドレス部分）が同一のネットワークアドレスが格納される。
【００２３】
制御回路３は、ブロックｉ用制御回路１０−ｉ（ｉ＝１〜２５６）と、バンク管理部４と、プリサーチ回路５と、検索判定部１４と、ブロック管理部９３、書込部９５と、消去部９４とを備える。
【００２４】
各ブロックｉ用制御回路１０−ｉは、ブロック化支援回路１３と、アドレスカウンタ１０１とを備える。
【００２５】
ブロック化支援回路１３は、対応するブロックに属するバンクのアドレスを記憶するバンクアドレスレジスタ群を含む。
【００２６】
アドレスカウンタ１０１は、対応のブロックに属する書込対象のバンクのエントリの位置を指示する。
【００２７】
プリサーチ回路５は、外部から与えられる検索データ（３２ビットのＩＰアドレス）のプリフィックス部分である先頭の８ビットに基づいて、検索データがブロック１〜ブロック２５６のいずれに属するかを判定する。
【００２８】
検索判定部１４は、プリサーチによって特定されたブロックの各エントリからデータを読み出して、読み出したデータに含まれるＩＰアドレスと検索データとを比較して、一致した場合に、そのＩＰアドレスとともに読み出されたホップ先アドレスを出力する。
【００２９】
バンク管理部４は、未使用バンクを表わす情報を保持するバンクＦＩＦＯ（First In First Out）メモリ９１を含む。バンク管理部４は、初期状態では、メモリアレイ２に含まれるすべてのバンクのアドレスをＦＩＦＯメモリ９１に格納する。バンク管理部４は、ＩＰアドレスをメモリアレイ２の未使用のバンクに書込み必要が生じた際には、ＦＩＦＯメモリ９１から未使用バンクのアドレスを読み出して、読み出した情報に基づいて、未使用バンクをＩＰアドレスを書込むバンクとして割り当てる。ここで、ＩＰアドレスをメモリアレイ２の未使用のバンクに書込み必要が生じる場合とは、ＩＰアドレスの書込みを指示された場合において、書込み中（使用中）のバンクの未使用領域がなくなった場合（すなわち、全エントリが使用されているとき）である。また、バンク管理部４は、バンク内のすべてのエントリが消去された際に、消去されたバンクのアドレスをＦＩＦＯメモリ９１に格納する。
【００３０】
ブロック管理部９３は、バンク管理部４によって新たに割り当てられたバンクをＩＰアドレスのプリフィックスに基づいて、いずれのブロックに属するかを特定する。ブロック管理部９３は、特定されたブロックに対応するブロック化支援回路１３に含まれるバンクアドレスレジスタ群に新たに割り当てられたバンクのアドレスを格納する。
【００３１】
書込部９５は、書込み時に、書込対象のバンクが属するブロックのアドレスカウンタ１０１で示されるエントリの位置にＩＰアドレスを書込み、その後、そのアドレスカウンタ１０１の値を１だけ増加させる。
【００３２】
消去部９４は、バンク内のエントリを消去する際に、バンクの使用領域の末尾のエントリに格納されているデータで、消去するエントリを上書きし、その後、バンクが属するブロックのアドレスカウンタ１０１の値を１だけ減少させる。
【００３３】
図３〜図６は、ブロック化の例を説明するための図である。
図３は、ブロック１〜２５６に属するバンクを表わす図である。
【００３４】
図３に示すように、バンク１、７はブロック１に属する。バンク２、５、６、８、１０は、ブロック２に属する。バンク３は、ブロック３に属する。バンク４は、ブロック４に属する。バンク９は、ブロック５に属する。バンク６８７、７４３は、ブロック２５６に属する。
【００３５】
図４は、図３に示すように複数のバンクがブロック化されている場合に、ブロックｉ用制御回路ごとのブロック化支援回路１３のバンクアドレスレジスタ群に記憶されるデータの例を表わす図である。
【００３６】
ブロック１用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク１のアドレスと、バンク７のアドレスを記憶する。ブロック２用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク２のアドレスと、バンク５のアドレスと、バンク６のアドレスと、バンク８のアドレスと、バンク１０のアドレスとを記憶する。ブロック３用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク３のアドレスを記憶する。ブロック４用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク４のアドレスを記憶する。ブロック５用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク９のアドレスを記憶する。ブロック２５６用制御回路のブロック化支援回路１３に含まれるバンクアドレスレジスタ群は、バンク６８７のアドレスと、バンク７４３のアドレスとを記憶する。
【００３７】
図５は、図３に示すように複数のバンクがブロック化されている場合に、ブロックｉ用制御回路のアドレスカウンタ１０１に記憶されるデータの例を表わす図である。
【００３８】
図５に示すように、ブロック１用制御回路のアドレスカウンタ１０１は、エントリ５のアドレスを記憶する。したがって、図４と図５によって、バンク７のエントリ５が現在又は次の書込対象のエントリとなる。ブロック２用制御回路のアドレスカウンタ１０１は、エントリ７のアドレスを記憶する。したがって、図４と図５によって、バンク１０のエントリ７が現在又は次の書込対象のエントリとなる。ブロック３用制御回路のアドレスカウンタ１０１は、エントリ５のアドレスを記憶する。したがって、図４と図５によって、バンク３のエントリ５が現在又は次の書込対象のエントリとなる。ブロック４用制御回路のアドレスカウンタ１０１は、エントリ１のアドレスを記憶する。したがって、図４と図５によって、バンク４のエントリ１が現在又は次の書込対象のエントリとなる。ブロック５用制御回路のアドレスカウンタ１０１は、エントリ１２のアドレスを記憶する。したがって、図４と図５によって、バンク９のエントリ１２が現在又は次の書込対象のエントリとなる。ブロック２５６用制御回路のアドレスカウンタ１０１は、エントリ４３のアドレスを記憶する。したがって、図４と図５によって、バンク７４３のエントリ４３が現在又は次の書込対象のエントリとなる。
【００３９】
図６（ａ）は、ＦＩＦＯメモリ９１に初期状態（ブロック化前）に格納されるデータの例を表わす図である。
【００４０】
初期状態では、ＦＩＦＯには、バンク１〜バンクＮのアドレスが格納される。エントリへの書込み時に、新たなバンクを割当る時には、バンク１のアドレスから順次取り出される。取り出されたアドレスで指定されるバンクのエントリに図２（ｂ）に示すようなデータが書込まれる。
【００４１】
図６（ｂ）は、バンク１〜バンク７が利用されて、データが書込まれた状態を表わす図である。
【００４２】
バンクに含まれる全エントリのデータが消去された場合には、バンクは解放され、再割当可能となる。たとえば、バンク５が解放された場合に、図６（ｃ）に示すように、消去部９４によって解放されたバンクのアドレスがＦＩＦＯメモリ９１の末尾に格納される。
【００４３】
（検索判定部１４）
図７は、検索判定部１４の概略構成を説明するための図である。
【００４４】
プリサーチによって、検索データがブロック１に属することがわかった場合に、バンク１の各エントリの情報データ（ＩＰアドレス）が順次比較器６０＿１に出力される。比較器６０＿１は、検索データと、各エントリの情報データとが一致するか否かを比較して、比較結果を出力する。同時に、バンク７の各エントリのデータ各エントリの情報データ（ＩＰアドレス）が順次比較器６０＿２に出力される。比較器６０＿２は、検索データと、各エントリの情報データとが一致するか否かを比較して、比較結果を出力する。論理回路Ｒは、比較器６０＿１の出力と比較器６０＿２の出力とを論理演算して、演算結果を出力する。
【００４５】
図８は、検索判定部１４の詳細を表わす図である。
図８を参照してプリサーチ回路５で特定されたブロックに属するバンクからエントリのデータ（ＩＰアドレスとホップ先アドレス）が出力される。
【００４６】
各バンクと接続する比較器６０は、外部から与えられる検索データとＩＰアドレスとを比較して、比較結果を論理回路Ｒ１、および論理回路ＲＲ１〜ＲＲＮのうち、特定されたブロックに属するバンクと接続される論理回路へ出力する。論理回路ＲＲ１〜ＲＲＮのうち、特定されたブロックに属するバンクと接続される論理回路には、接続されるバンクのエントリのホップ先アドレスが入力される。
【００４７】
論理回路Ｒ１は、比較器６０＿１〜６０＿Ｎでの比較のうち一致したものがある場合には、Ｈｉｔを示す信号を出力する。
【００４８】
論理回路ＲＲ１〜ＲＲＮのうち、特定されたブロックに属するバンクと接続する論理回路は、そのバンクでＨｉｔしたとき（つまり、接続される比較器が一致を示す信号を出力したとき）には、入力されたホップ先アドレスを出力し、そのバンクでＭｉｓｓしたときには、全ビットが０の信号を出力する。
【００４９】
論理回路Ｒ３は、Ｈｉｔしたバンクのエントリのホップ先アドレスを出力する。論理回路Ｒ２およびラッチ回路ＲＡ１によって、ＨｉｔまたはＭｉｓｓの結果を更新されるまで維持し、出力する。論理回路Ｒ３、セレクタＳＬ１およびラッチ回路ＲＡ２によって、ホップ先アドレスを更新されるまで維持し、出力する。
【００５０】
（ブロック化支援回路１３）
図９は、ブロック化支援回路１３の構成を表わす図である。
【００５１】
図９を参照して、カウンタ１３４は、バンクアドレスレジスタ３６＿１〜３６＿Ｎのうちバンクアドレスが格納されているレジスタの個数をカウントする。
【００５２】
セレクタ３２は、バンクアドレスレジスタ３６＿１〜３６＿Ｎのいずれかを指定するアドレス、またはカウンタ１３４のカウンタ値を受けて、どちらかを出力する。バンクアドレスレジスタ３６＿１〜３６＿Ｎのいずれかを指定するアドレスは、メモリアレイ２への書込み時に、このグループ支援回路が対応するブロックへのバンクの割当があった場合に、入力される。
【００５３】
デコーダ３０は、セレクタ３２の出力信号をデコードする。デコーダ３０の出力によって、論理回路ＲＬ１〜ＲＬ＿Ｌのいずれかが選択される。またＡＬＬ＿ｓｅｌｅｃｔ信号が入力されるときには、論理回路ＲＬ＿１〜ＲＬ＿Ｌのすべてが選択される。
【００５４】
メモリアレイ２への書込み時には、選択された論理回路ＲＬ＿ｉと接続されているバンクアドレスレジスタ３６＿ｉに、ライトデータ（バンクアドレス）が書込まれる。
【００５５】
また、メンテナンス時には、選択された論理回路ＲＬ＿ｉと接続されているバンクアドレスレジスタ３６＿ｉからリードデータ（バンクアドレス）が読み出される。
【００５６】
（エントリ消去）
消去部９４は、ブロックごとにエントリ消去回路１２を含む。
【００５７】
図１０は、エントリ消去回路１２の構成を表わす図である。
メモリＡ１０２は、メモリアレイ２内のバンクを表わす。
【００５８】
メモリＢ１０４は、検索のために使用するデータを格納するものである。
アドレスカウンタ１０１は、メモリＡ（バンク内）で使用されている末尾のエントリの番号をセレクタ１０３へ出力する。
【００５９】
セレクタ１０３は、命令が入力されて、この命令をメモリＡへの命令（Ａ＿命令）またはメモリＢへの命令（Ｂ＿命令）として出力する。
【００６０】
セレクタ１０３は、アドレスが入力されて、このアドレスをメモリＡへのアドレス（Ａ＿アドレス）、メモリＢへのアドレス（Ｂ＿アドレス）として出力する。
【００６１】
セレクタ１０３は、ライトデータ、メモリＡからのリードデータ（Ａ＿リードデータ）、メモリＢからのリードデータ（Ｂ＿リードデータ）とが入力されて、これらをメモリＡへのライトデータ（Ａ＿ライトデータ）、メモリＢへのライトデータ（Ｂ＿ライトデータ）として出力する。
【００６２】
図１１は、エントリ消去動作を説明するための図である。
１つのバンクに０〜ｎ番目のエントリが使用され、アドレス順に０〜ｎ番目のエントリが存在する場合に、エントリ消去回路は、ｋ番目のエントリを消去する場合に、末尾に存在するｎ番目のエントリのデータを読み出して、ｋ番目のエントリに上書きする。そして、ｎ番目のエントリを未使用領域として解放し、使用領域を０〜（ｎ−１）番目のエントリとする。これによって、消去したエントリを再利用することができる。
【００６３】
図１２は、エントリ消去動作を説明するための図である。
ｎ番目のエントリ（アドレスがｎとする）から読み出したデータをＫｅｙ１＋メモリＢのｉアドレスとする。Ｋｅｙ１は、ＩＰアドレスで、メモリＢのｉアドレスは、ホップ先アドレスである。
【００６４】
一方、ｋ番目のエントリ（アドレスがｋとする）に格納されているデータがＫｅｙ２＋メモリＢのｊアドレスであるとする。Ｋｅｙ２は、ＩＰアドレスで、メモリＢのｊアドレスは、ホップ先アドレスである。ｋ番目のエントリは、ｎ番目のエントリのデータで上書きされるので、ｋ番目のエントリのデータは、Ｋｅｙ１＋メモリＢのｉアドレスとなる。
【００６５】
一方、メモリＢのｉアドレスには、メモリＡのｎアドレスが格納され、メモリＢのｊアドレスには、メモリＡのｋアドレスが格納されている。
【００６６】
以上のように、本実施の形態によれば、プリフィックス毎の使用状況に偏りが発生した場合にも状況に応じてメモリを使用するため、未使用領域を発生させることなく効率よくメモリを使い切ることができる。
【００６７】
［第２の実施形態］
図１３は、第２の実施形態の検索判定部１４の例を表わす図である。
【００６８】
この検索判定部１４は、ブロック１〜ブロック２５６において、同時に並行して検索処理が実行できる。
【００６９】
セレクタ５０−ｉは、バンク１〜バンクＮのうち、ブロックｉに属するバンクのエントリと検索データとを比較する比較器と接続する。
【００７０】
ブロック１に属するバンク１の各エントリの情報データ（ＩＰアドレス）と検索データとを比較する比較器６０＿１の比較結果と、ブロック１に属するバンク７の各エントリの情報データ（ＩＰアドレス）を比較する比較器６０＿７の比較結果がセレクタ５０−１に送られる。セレクタ５０−１は、これらの２つの比較器６０＿１，６０＿７からの信号を論理回路５２−１に出力する。論理回路５２−１で２つの比較器６０＿１，６０＿７からの出力される信号を論理演算して、演算結果を出力する。
【００７１】
同時に、ブロック２に属するバンク２，５，６，８，１０の各エントリの情報データ（ＩＰアドレス）と検索データとを比較する比較器６０＿２，６０＿５，６０＿６，６０＿８，６０＿１０の比較結果がセレクタ５０−２に送られる。セレクタ５０−２は、これらの比較器６０＿２，６０＿５，６０＿６，６０＿８，６０＿１０からの信号を論理回路５２−２に出力する。論理回路５２−２で４つの比較器６０＿２，６０＿５，６０＿６，６０＿８，６０＿１０からの出力される信号を論理演算して、演算結果を出力する。
【００７２】
同様に、同時にブロック３〜ブロック２５６についても、上述と同様にして検索データとの一致／不一致が判定される。
【００７３】
並列処理方法の場合は、同時に各プリフィックスで使用されるブロックを動作させ検索を行い、検索結果をプライオリティエンコーダによって選別する。
【００７４】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【００７５】
１ 半導体装置、２ メモリアレイ、３ 制御回路、４ バンク管理部、５ プリサーチ回路、１４ 検索判定部、１０−１〜１０−２５６ ブロック制御回路、１３ ブロック化支援回路、３０ デコーダ、３６＿１〜３６＿Ｎ バンクアドレスレジスタ、６０＿１〜６０＿Ｎ 比較器、９１ ＦＩＦＯメモリ、９３ ブロック管理部、９４ 消去部、９５ 書込部、１０１ アドレスカウンタ、１０２ メモリＡ、１０４ メモリＢ、１３４ カウンタ、Ｒ，Ｒ１，Ｒ２，ＲＲ１〜ＲＲＮ，Ｒ３ 論理回路、３２，ＳＬ１，１０３ セレクタ回路、ＲＬ＿１〜ＲＬ＿Ｎ，ＲＡ１，ＲＡ２ ラッチ回路。
【特許請求の範囲】
【請求項１】
複数のバンクを含み、検索対象のＩＰアドレスを格納するメモリアレイを備え、前記メモリアレイは、可変数のバンクからなる複数のブロックを含み、同一のブロックのバンクにはプリフィックスが同一のＩＰアドレスが格納され、
ＩＰアドレスを検索データとして受けて、前記検索データと同一のＩＰアドレスがいずれのブロックに格納されているかをプリサーチするプリ検索部と、
前記プリサーチによって特定されたブロックから読み出されたＩＰアドレスと前記検索データとを比較する検索判定部とをさらに備えた、内容参照メモリ。
【請求項２】
未使用バンクを表わす情報を保持するＦＩＦＯメモリを含みバンク管理部をさらに備え、
前記バンク管理部は、初期状態では、前記メモリアレイに含まれるすべてのバンクを表わす情報を前記ＦＩＦＯメモリに格納し、前記ＩＰアドレスをメモリアレイの未使用のバンクに書込み必要が生じた際には、前記ＦＩＦＯメモリから未使用バンクを表わす情報を読み出して、読み出した情報に基づいて、前記未使用バンクを前記ＩＰアドレスを書込むバンクとして割り当てる、請求項１記載の内容参照メモリ。
【請求項３】
ブロックに対応して、属するバンクを表わす情報を記憶するレジスタ群と、
前記バンク管理部によって新たに割り当てられたバンクを前記ＩＰアドレスのプリフィックスに基づいて、いずれのブロックに属するかを特定して、特定されたブロックに対応する前記レジスタ群に前記新たに割り当てられたバンクを表わす情報を格納するブロック管理部とをさらに備えた、請求項２記載の内容参照メモリ。
【請求項４】
各バンクは、複数のエントリを含み、
ブロックごとに、前記ブロックに属する書込対象のバンクのエントリの位置を示すアドレスカウンタと、
書込み時に、前記書込対象のバンクが属するブロックの前記アドレスカウンタで示されるエントリの位置に前記ＩＰアドレスを書込み、その後前記アドレスカウンタの値を１だけ増加させる書込部とをさらに備えた、請求項３記載の内容参照メモリ。
【請求項５】
前記バンク内のエントリを消去する際に、前記バンクの使用領域の末尾のエントリに格納されているデータで、前記消去するエントリを上書きし、その後、前記バンクが属するブロックの前記アドレスカウンタの値を１だけ減少させる消去部をさらに備え、
前記バンク管理部は、バンク内のすべてのエントリが消去された際に、前記消去されたバンクを表わす情報を前記ＦＩＦＯメモリに格納する、請求項４記載の内容参照メモリ。
【請求項１】
複数のバンクを含み、検索対象のＩＰアドレスを格納するメモリアレイを備え、前記メモリアレイは、可変数のバンクからなる複数のブロックを含み、同一のブロックのバンクにはプリフィックスが同一のＩＰアドレスが格納され、
ＩＰアドレスを検索データとして受けて、前記検索データと同一のＩＰアドレスがいずれのブロックに格納されているかをプリサーチするプリ検索部と、
前記プリサーチによって特定されたブロックから読み出されたＩＰアドレスと前記検索データとを比較する検索判定部とをさらに備えた、内容参照メモリ。
【請求項２】
未使用バンクを表わす情報を保持するＦＩＦＯメモリを含みバンク管理部をさらに備え、
前記バンク管理部は、初期状態では、前記メモリアレイに含まれるすべてのバンクを表わす情報を前記ＦＩＦＯメモリに格納し、前記ＩＰアドレスをメモリアレイの未使用のバンクに書込み必要が生じた際には、前記ＦＩＦＯメモリから未使用バンクを表わす情報を読み出して、読み出した情報に基づいて、前記未使用バンクを前記ＩＰアドレスを書込むバンクとして割り当てる、請求項１記載の内容参照メモリ。
【請求項３】
ブロックに対応して、属するバンクを表わす情報を記憶するレジスタ群と、
前記バンク管理部によって新たに割り当てられたバンクを前記ＩＰアドレスのプリフィックスに基づいて、いずれのブロックに属するかを特定して、特定されたブロックに対応する前記レジスタ群に前記新たに割り当てられたバンクを表わす情報を格納するブロック管理部とをさらに備えた、請求項２記載の内容参照メモリ。
【請求項４】
各バンクは、複数のエントリを含み、
ブロックごとに、前記ブロックに属する書込対象のバンクのエントリの位置を示すアドレスカウンタと、
書込み時に、前記書込対象のバンクが属するブロックの前記アドレスカウンタで示されるエントリの位置に前記ＩＰアドレスを書込み、その後前記アドレスカウンタの値を１だけ増加させる書込部とをさらに備えた、請求項３記載の内容参照メモリ。
【請求項５】
前記バンク内のエントリを消去する際に、前記バンクの使用領域の末尾のエントリに格納されているデータで、前記消去するエントリを上書きし、その後、前記バンクが属するブロックの前記アドレスカウンタの値を１だけ減少させる消去部をさらに備え、
前記バンク管理部は、バンク内のすべてのエントリが消去された際に、前記消去されたバンクを表わす情報を前記ＦＩＦＯメモリに格納する、請求項４記載の内容参照メモリ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１３−３７７５０（Ｐ２０１３−３７７５０Ａ）
【公開日】平成２５年２月２１日（２０１３．２．２１）
【国際特許分類】
【出願番号】特願２０１１−１７４８７３（Ｐ２０１１−１７４８７３）
【出願日】平成２３年８月１０日（２０１１．８．１０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、独立行政法人情報通信研究機構「高度通信・放送研究開発委託研究／光統合ネットワークの管理制御およびノード構成技術に関する研究開発、副題：光統合ネットワークの制御技術と光パケット安定性処理技術の研究開発」、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【公開日】平成２５年２月２１日（２０１３．２．２１）
【国際特許分類】
【出願日】平成２３年８月１０日（２０１１．８．１０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、独立行政法人情報通信研究機構「高度通信・放送研究開発委託研究／光統合ネットワークの管理制御およびノード構成技術に関する研究開発、副題：光統合ネットワークの制御技術と光パケット安定性処理技術の研究開発」、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
[ Back to top ]