(57)【要約】      （修正有）【課題】低消費電力化が可能な半導体装置を提供する。【解決手段】半導体装置は、Ｎ個のサブブロックと、サブブロックにそれぞれ対応して分割された１〜Ｎ番目のエントリデータのうちプリサーチ用のエントリーデータの番号を指定するための設定レジスタ１６と、設定レジスタの値に基づいて入力されるサーチデータのデータ配列順序を変更するサーチデータ変更部１８とを備える。Ｎ個のサブブロックのうちのプリサーチ用のサブブロックは、サーチデータ変更部により変更されたデータ配列順序に従うプリサーチ用データに一致するものを検索し、行毎に一致または不一致という検索結果を出力し、プリサーチ用のサブブロックの検索結果に基づいて、メモリセルアレイの行毎に格納されたエントリデータのうち、サーチデータのうちのポストサーチ用データに一致するものを検索し、行毎に一致または不一致という検索結果を出力する。【選択図】図９
2019008845.tif 000002
【特許請求の範囲】
【請求項１】
各々がメモリセルアレイを含む、Ｎ個のサブブロックと、
前記Ｎ個のサブブロックにそれぞれ対応して分割された１〜Ｎ番目のエントリデータのうちプリサーチ用のエントリデータの番号を指定するための設定レジスタと、
前記設定レジスタの値に基づいて入力されるサーチデータのデータ配列順序を変更するサーチデータ変更部とを備え、
前記Ｎ個のサブブロックのうちのプリサーチ用のサブブロックは、検索指示に従って、前記メモリセルアレイの行毎に格納されたエントリデータのうち、前記サーチデータ変更部により変更されたデータ配列順序に従うプリサーチ用データに一致するものを検索し、前記行毎に一致または不一致という検索結果を出力し、
前記Ｎ個のサブブロックのうちのポストサーチ用のサブブロックは、前記プリサーチ用のサブブロックの検索結果に基づいて、前記メモリセルアレイの行毎に格納されたエントリデータのうち、前記サーチデータのうちの前記プリサーチ用データ以外のポストサーチ用データに一致するものを検索し、前記行毎に一致または不一致という検索結果を出力する、半導体装置。
【請求項２】
前記設定レジスタの値に基づいて各前記Ｎ個のサブブロックから読み出された１〜Ｎ番目のエントリデータの配列順序を変更する読出エントリデータ変更部をさらに備える、請求項１記載の半導体装置。
【請求項３】
前記読出エントリデータ変更部から、前記Ｎ個のサブブロックに格納された行毎に格納された１〜Ｎ番目のエントリデータの全てを所得し、データ解析に基づいて前記プリサーチ用のエントリデータの番号を再指定する解析部をさらに備える、請求項２記載の半導体装置。
【請求項４】
前記設定レジスタの値に基づいて１〜Ｎ番目の書込用のエントリデータのデータ配列順序を変更する書込エントリデータ変更部をさらに備え、
各前記Ｎ個のサブブロックは、変更された順番に従うエントリデータを前記メモリアレイに書込む書込回路をさらに含む、請求項１記載の半導体装置。
【請求項５】
前記サーチデータ変更部は、前記入力されるサーチデータのうちプリサーチ用データを前記プリサーチ用のサブブロックに出力するとともに、前記プリサーチ用データ以外のポストサーチ用データを保持する保持回路を含む、請求項１記載の半導体装置。
【請求項６】
前記プリサーチ用のサブブロックのメモリセルアレイは、２値を保持して、前記プリサーチ用データとの間での一致または不一致の比較が可能なメモリセルを有し、前記ポストサーチ用のサブブロックのメモリセルアレイは、３値を保持して、前記ポストサーチ用データとの間での一致または不一致の比較が可能なメモリセルを有する、請求項１記載の半導体装置。
【請求項７】
複数の検索ブロックを備え、
各前記検索ブロックは、
各々がメモリセルアレイを含む、Ｎ個のサブブロックと、
前記Ｎ個のサブブロックにそれぞれ対応して分割された１〜Ｎ番目のエントリデータのうちプリサーチ用のエントリデータの番号を指定するための設定レジスタと、
前記設定レジスタの値に基づいて前記複数の検索ブロックに対して共通に入力されるサーチデータのデータ配列順序を変更するサーチデータ変更部とを含み、
前記Ｎ個のサブブロックのうちのプリサーチ用のサブブロックは、検索指示に従って、前記メモリセルアレイの行毎に格納されたエントリデータのうち、前記サーチデータ変更部により変更されたデータ配列順序に従うプリサーチ用データに一致するものを検索し、前記行毎に一致または不一致という検索結果を出力し、
前記Ｎ個のサブブロックのうちのポストサーチ用のサブブロックは、前記プリサーチ用のサブブロックの検索結果に基づいて、前記メモリセルアレイの行毎に格納されたエントリデータのうち、前記サーチデータのうちの前記プリサーチ用データ以外のポストサーチ用データに一致するものを検索し、前記行毎に一致または不一致という検索結果を出力する、半導体装置。
【請求項８】
各々が行列状に配置された連想メモリセルを含む第１および第２のサブブロックと、
書込データを構成する第１および第２の書込データがそれぞれ格納された前記第１および第２のサブブロックとの対応関係を指定した設定レジスタと、
前記設定レジスタの値に基づいて、入力された検索データのデータ配列順序を変更し、前記検索データを構成する前記第１および第２の検索キーをそれぞれ対応する前記第１および第２のサブブロックに出力するデータ配列順序変更部とを備え、
前記第１のサブブロックは、前記第１のサブブロックに入力された前記第１および第２の検索キーの一方による検索動作を行い、
前記第２のサブブロックは、前記第１のサブブロックの検索動作の結果に基づいて、前記第１および第２の検索キーの他方による検索動作を行う、半導体装置。
【請求項９】
前記設定レジスタの値に応じて、前記第１および第２のサブブロックにそれぞれ格納されている前記第１および第２の書込データの配列順序を変更して読出データとして出力する読出データ配列順序変更部をさらに備える、請求項８に記載の半導体装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、半導体装置に関し、たとえば、連想メモリに関する。
【背景技術】
【０００２】
連想メモリまたはＣＡＭ（内容参照メモリ：Content Addressable Memory）と呼ばれる記憶装置は、記憶しているデータワードの中から検索ワードに一致しているものを検索し、一致しているデータワードが見つかった場合は、そのアドレスを出力するものである。
【０００３】
ＣＡＭにはＢＣＡＭ（Binary CAM）とＴＣＡＭ（Ternary CAM）とがある。ＢＣＡＭの各メモリセルは“０”か“１”かのいずれかの情報を記憶する。一方、ＴＣＡＭの場合には、各メモリセルは、“０”および“１”の他に“ドントケア（Don't Care）”（本例においては、“＊”の記号を用いる）の情報を記憶可能である。“＊”は“０”および“１”のどちらでも良いことを示す。
【０００４】
ＴＣＡＭ装置は、インターネットなどのネットワーク用のルータにおいてアドレス検索およびアクセス制御のために幅広く利用されている。大容量化に対応するために、ＴＣＡＭ装置は、通常、複数のアレイを有し、各アレイに対して同時にサーチ動作が実行される構成となっている。
【０００５】
ＴＣＡＭ装置は、入力サーチデータ（入力パケット）とＴＣＡＭセルデータとを一斉に比較することができるので、全ての検索用途においてＲＡＭ（Random Access Memory）よりも高速である。しかしながら、検索時にサーチ電流が発生するために消費電力の増大が問題となっている。
【０００６】
この点で、時分割検索により初段セグメントの検索（プリサーチ）が不一致（ＭＩＳＳ）である場合には、後段セグメントの検索（ポストサーチ）を実行しないことにより検索の低消費電力化を図ることが可能である（特許文献１）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開昭６２−２９３５９６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、時分割検索はなるべくプリサーチで不一致となることが消費電力化の観点から望ましいが、例えば、ＡＣＬ（Access Control List）等のテーブルを構成するフィールドに対して時分割検索を実行する場合には、不一致となりやすいものとなり難いものあり、同じテーブルでもＴＣＡＭ装置への書き込み方次第で時分割検索による省電力効果は変化する。
【０００９】
本開示は、上記の課題を解決するためになされたものであって、低消費電力化が可能な半導体装置を提供することを目的とする。
【００１０】
その他の課題と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１１】
一実施例によれば、半導体装置は、各々がメモリセルアレイを含む、Ｎ個のサブブロックと、Ｎ個のサブブロックにそれぞれ対応して分割された１〜Ｎ番目のエントリデータのうちプリサーチ用のエントリデータの番号を指定するための設定レジスタと、設定レジスタの値に基づいて入力されるサーチデータのデータ配列順序を変更するサーチデータ変更部とを備える。Ｎ個のサブブロックのうちのプリサーチ用のサブブロックは、検索指示に従って、メモリセルアレイの行毎に格納されたエントリデータのうち、サーチデータ変更部により変更されたデータ配列順序に従うプリサーチ用データに一致するものを検索し、行毎に一致または不一致という検索結果を出力し、Ｎ個のサブブロックのうちのポストサーチ用のサブブロックは、プリサーチ用のサブブロックの検索結果に基づいて、メモリセルアレイの行毎に格納されたエントリデータのうち、サーチデータのうちのプリサーチ用データ以外のポストサーチ用データに一致するものを検索し、行毎に一致または不一致という検索結果を出力する。
【発明の効果】
【００１２】
一実施例によれば、本開示の半導体装置は、低消費電力化を図ることが可能である。
【図面の簡単な説明】
【００１３】
【図１】実施形態１に基づく通信機器１の構成を説明する図である。
【図２】実施形態１に基づく検索メモリ８の構成を説明する図である。
【図３】実施形態１に基づくＴＣＡＭ装置１２の構成を説明する図である。
【図４】ＴＣＡＭセルの構成の一例を示す回路図である。
【図５】図４のＸセルおよびＹセルの記憶内容とＴＣＡＭデータとの対応関係を表形式で示す図である。
【図６】実施形態に基づくセグメント（サブブロック）１２Ａの構成を説明する図である。
【図７】サーチ線ドライバ２２の構成の一例を示す回路図である。
【図８】マッチアンプの構成の一例を示す回路図である。
【図９】実施形態１に基づく検索ブロック１０の検索方式を説明する図である。
【図１０】検索ブロック１０の検索のタイミングを説明する図である。
【図１１】検索メモリ８のメンテナンス動作について説明する図である。
【図１２】実施形態２に基づく検索ブロック１０＃の検索方式を説明する図である。
【図１３】ＢＣＡＭ装置１２ＰのＢＣＡＭセルＭＣ＃の構成の一例を示す回路図である。
【図１４】実施形態２の変形例に基づく検索ブロック１０Ａの検索方式を説明する図である。
【図１５】検索ブロック１０Ａの検索のタイミングを説明する図である。
【発明を実施するための形態】
【００１４】
実施形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付し、その説明は繰り返さない。
【００１５】
（実施形態１）
＜通信機器１の全体構成＞
図１は、実施形態１に基づく通信機器１の構成を説明する図である。
【００１６】
図１に示されるように、通信機器１は、スイッチあるいはルータ等の通信装置である。
通信機器１は、ＣＰＵ（Central Processing Unit）２と、転送制御回路４と、汎用メモリ６と、検索メモリ８とを含む。
【００１７】
ＣＰＵ２は、機器全体を制御する。
ＣＰＵ２は、汎用メモリ６に格納されたプログラムと協働して種々の機能を実現する。たとえば、汎用メモリ６は、ＤＲＡＭ（Dynamic Random Access Memory）で構成することが可能であり、ＣＰＵ２と協働することによりオペレーティングシステム（ＯＳ）を構築する。ＣＰＵ２は、隣接する通信機器等と情報交換し、転送処理に必要な情報を維持管理する。
【００１８】
転送制御回路４は、通信パケットの転送処理を実行する。転送制御回路４は、転送処理に特化したＡＳＩＣ（Application Specific Integrated Circuit）回路あるいはＮＰＵ(Network Processing Unit)といった専用ハードウェアが設けられている。転送制御回路４は、検索メモリ８にアクセスして、転送処理に必要な情報を取得する。
【００１９】
検索メモリ８は、本例においては、ＴＣＡＭ装置を用いる場合について説明する。
＜検索メモリ８の構成＞
図２は、実施形態１に基づく検索メモリ８の構成を説明する図である。
【００２０】
図２に示されるように、検索メモリ８は、入力データから検索キーを生成する検索キー生成部２９と、プロファイルレジスタ２６と、複数の検索ブロック１０と、検索結果生成部２８とを含む。
【００２１】
検索メモリ８全体は一定の粒度を持つ検索ブロック１０という単位で管理される。本例においては、複数の検索ブロック１０−１〜１０−ｎが設けられた構成が示されている。
【００２２】
各検索ブロック１０の構成についての詳細は、後述するが、ＴＣＡＭセルを有するＴＣＡＭ装置１２と、プリサーチ用のエントリデータの番号を指定するための設定レジスタ１６と、設定レジスタ１６の値に基づいてデータ配列順序を変更するデータ変更部２７とを含む。
【００２３】
プロファイルレジスタ２６には検索に必要な様々な設定が保持されている。
プロファイルレジスタ２６の情報に基づき検索キー生成部２９は入力データから検索キーの生成を行う。
【００２４】
検索ブロック１０−１〜１０−ｎは、並列に設けられており並列検索機能を有する。
検索結果生成部２８は、各検索ブロック１０からの検索結果に対して優先順位をつけ最終的な検索結果を生成する。
【００２５】
検索コマンドが発行されると、検索キー生成部２９は、受け取ったデータとプロファイルレジスタ２６を始めとする各種情報に基づき検索キーを生成する。
【００２６】
検索キー生成部２９は、各検索ブロック１０に検索キーを分配する。各検索ブロック１０では、設定レジスタ１６に予め設定されたレジスタ値に基づいてデータ変更部２７が、検索キーのデータ配列順序を変更して出力する。これによって変更された検索キーは各検索ブロック１０毎にユニークな値となる。
【００２７】
＜ＴＣＡＭ装置１２の構成＞
図３は、実施形態１に基づくＴＣＡＭ装置１２の構成を説明する図である。
【００２８】
図３に示されるように、ＴＣＡＭ装置１２は、時分割検索機能を有する。
ＴＣＡＭ装置１２は、複数のセグメント（サブブロック）に分割されている。本例においては、４つのセグメント（サブブロック）に分割されている場合が示されている。
【００２９】
一例として、セグメント１２Ａ〜１２Ｄに分割されている場合が示されている。
セグメント１２Ａ〜１２Ｄは、前段から後段に連結されている。
【００３０】
各セグメント１２Ａ〜１２Ｄは、基本的に同様の構成であり、メモリセルアレイと、マッチアンプが設けられているが最終段のセグメント１２Ｄには、メモリセルアレイと、マッチアンプと、プライオリティエンコーダとが設けられている。
【００３１】
マッチアンプは少なくともセグメント毎に存在し、各マッチ線の一致、不一致の判定結果を増幅して出力する。
【００３２】
プライオリティエンコーダは、マッチアンプからの入力をアドレスに変換し最終的な出力を生成する。
【００３３】
また、メモリセルアレイは、複数のｓｅ(Search Enable)端子が設けられており、ｓｅ端子がアサートされた領域のみマッチ線のプリチャージを行うことにより検索範囲を限定することが可能である。
【００３４】
また、本例においては、一例としてマッチアンプを活性化させる信号を保持するためのフリップフロップＦＦ１が設けられている。具体的には、フリップフロップＦＦ１に検索コマンドが入力された場合にマッチアンプを活性化させる信号が保持されて各セグメントのマッチアンプに出力される。
【００３５】
また、セグメント１２Ｂ〜１２Ｄには、フリップフロップＦＦ２〜ＦＦ４が設けられており、前段のセグメントにおける検索処理が終了するまで検索キーを保持することが可能な構成となっている。本例においては、セグメント１２Ａには、検索キーＳＢが入力され、セグメント１２Ｂには、検索キーＳＡが入力され、セグメント１２Ｃ，１２Ｄには、検索キーＳＣ，ＳＤが入力される場合が示されている。
【００３６】
前段のセグメントのマッチアンプ出力を後段のセグメントのｓｅ端子と接続することにより、前段のセグメントで一致したエントリのみを検索対象とすることが可能である。
【００３７】
具体的には、まず初段のセグメント１２Ａのみを活性させて第１の検索を実行する。第１の検索で一致した領域のみセグメント１２Ｂにおいて第２の検索を実行する。同様にして第３、第４の検索を実行する。前段のセグメントの検索で不一致となった領域の分だけ後段のセグメントの消費電力を抑えることが可能である。
【００３８】
＜セグメント（サブブロック）の構成＞
［ＴＣＡＭセルの構成］
図４は、ＴＣＡＭセルの構成の一例を示す回路図である。
【００３９】
図４を参照して、ＴＣＡＭセル（メモリセルＭＣとも称する）は、２個のＳＲＡＭセル（Static Random Access Memory Cell）１１，１２と、データ比較部１３とを含む。ＳＲＡＭセル１１をＸセルとも称し、ＳＲＡＭセル１４をＹセルとも称する。Ｘセル１１は、内部の記憶ノード対ＮＤ１，ＮＤ１＿ｎに互いに相補となる（一方が“１”のとき他方が“０”となる）１ビット（ｂｉｔ）のデータを記憶する。Ｙセル１４は、内部の記憶ノード対ＮＤ２，ＮＤ２＿ｎに互いに相補となる１ビットのデータを記憶する。ＴＣＡＭセルは、連想メモリセルとも称する。
【００４０】
ＴＣＡＭセルは、ビット線対ＢＬ，ＢＬ＿ｎ、サーチ線対ＳＬ，ＳＬ＿ｎ、マッチ線ＭＬ、およびワード線ＷＬＸ，ＷＬＹと接続される。ビット線対ＢＬ，ＢＬ＿ｎは、図６のＴＣＡＭセルアレイ２０の列方向（Ｙ方向）に延在し、列方向に配列された複数のＴＣＡＭセルによって共有される。サーチ線対ＳＬ，ＳＬ＿ｎは、ＴＣＡＭセルアレイ２０の列方向（Ｙ方向）に延在し、列方向に配列された複数のＴＣＡＭセルによって共有される。
【００４１】
マッチ線ＭＬは、ＴＣＡＭセルアレイ２０の行方向（Ｘ方向）に延在し、行方向に配列された複数のＴＣＡＭセルによって共有される。ワード線ＷＬＸ，ＷＬＹは、ＴＣＡＭセルアレイ２０の行方向（Ｘ方向）に延在し、行方向に配列された複数のＴＣＡＭセルによって共有される。
【００４２】
Ｘセル１１は、インバータＩＮＶ１，ＩＮＶ２と、ＮチャネルＭＯＳ（Metal Oxide Semiconductor）トランジスタＱ１，Ｑ２とを含む。インバータＩＮＶ１は、記憶ノードＮＤ１＿ｎから記憶ノードＮＤ１へ向かう方向が順方向となるように、記憶ノードＮＤ１と記憶ノードＮＤ１＿ｎの間に接続される。インバータＩＮＶ２は、ＩＮＶ１と並列かつ逆方向に接続される。ＭＯＳトランジスタＱ１は、記憶ノードＮＤ１とビット線ＢＬとの間に接続される。ＭＯＳトランジスタＱ２は、記憶ノードＮＤ１＿ｎとビット線ＢＬ＿ｎとの間に接続される。ＭＯＳトランジスタＱ１，Ｑ２のゲートは、ワード線ＷＬＸと接続される。
【００４３】
Ｙセル１４は、インバータＩＮＶ３，ＩＮＶ４と、ＭＯＳ（Metal Oxide Semiconductor）トランジスタＱ３，Ｑ４とを含む。インバータＩＮＶ３は、記憶ノードＮＤ２＿ｎから記憶ノードＮＤ２に向かう方向が順方向となるように、記憶ノードＮＤ２と記憶ノードＮＤ２＿ｎの間に接続される。インバータＩＮＶ４は、ＩＮＶ３と並列かつ逆方向に接続される。ＭＯＳトランジスタＱ３は、記憶ノードＮＤ２とビット線ＢＬとの間に接続される。ＭＯＳトランジスタＱ４は、記憶ノードＮＤ２＿ｎとビット線ＢＬ＿ｎとの間に接続される。ＭＯＳトランジスタＱ３，Ｑ４のゲートは、ワード線ＷＬＹと接続される。
【００４４】
データ比較部１３は、ＮチャネルＭＯＳトランジスタＱ６〜Ｑ９を含む。ＭＯＳトランジスタＱ６，Ｑ７はマッチ線ＭＬとの接続点であるノードＮＤ３と接地ノードＧＮＤとの間に直列に接続される。ＭＯＳトランジスタＱ８，Ｑ９は、ノードＮＤ３と接地ノードＧＮＤとの間に直列に、かつ、直列接続されたＭＯＳトランジスタＱ６，Ｑ７の全体と並列に接続される。ＭＯＳトランジスタＱ６，Ｑ８のゲートは、記憶ノードＮＤ１，ＮＤ２とそれぞれ接続される。ＭＯＳトランジスタＱ７，Ｑ９のゲートは、サーチ線ＳＬ，ＳＬ＿ｎとそれぞれ接続される。
【００４５】
図５は、図４のＸセルおよびＹセルの記憶内容とＴＣＡＭデータとの対応関係を表形式で示す図である。
【００４６】
図４および図５を参照して、ＴＣＡＭセルは、２ビットのＳＲＡＭセルを用いて、“０”、“１”、“＊”（ドントケア：don't care）の３値を格納することができる。具体的に、Ｘセル１１の記憶ノードＮＤ１に“１”が格納され、Ｙセル１４の記憶ノードＮＤ２に“０”が格納されているとき、ＴＣＡＭセルには“０”が格納されているとする。Ｘセル１１の記憶ノードＮＤ１に“０”が格納され、Ｙセル１４の記憶ノードＮＤ２に“１”が格納されているとき、ＴＣＡＭセルには“１”が格納されているとする。Ｘセル１１の記憶ノードＮＤ１に“０”が格納され、Ｙセル１４の記憶ノードＮＤ２に“０”が格納されているとき、ＴＣＡＭセルには“＊”（ドントケア）が格納されているとする。Ｘセル１１の記憶ノードＮＤ１に“１”が格納され、Ｙセル１４の記憶ノードＮＤ２に“１”が格納されている場合は使用しない。
【００４７】
上記のＴＣＡＭセルの構成によれば、サーチデータが“１”（すなわち、サーチ線ＳＬが“１”、かつ、サーチ線ＳＬ＿ｎが“０”）であり、ＴＣＡＭデータが“０”（記憶ノードＮＤ１が“１”、かつ、記憶ノードＮＤ２が“０”）である場合には、ＭＯＳトランジスタＱ６，Ｑ７がオン状態となるために、プリチャージされたマッチ線ＭＬの電位が接地電位まで引き抜かれる。サーチデータが“０”（すなわち、サーチ線ＳＬが“０”、かつ、サーチ線ＳＬ＿ｎが“１”）であり、ＴＣＡＭデータが“１”（記憶ノードＮＤ１が“０”、かつ、記憶ノードＮＤ２が“１”）である場合には、ＭＯＳトランジスタＱ８，Ｑ９がオン状態となるために、プリチャージされたマッチ線ＭＬの電位が接地電位まで引き抜かれる。すなわち、サーチデータとＴＣＡＭデータとが不一致の場合には、マッチ線ＭＬの電位は接地電位まで引き抜かれる。
【００４８】
逆に、入力されたサーチデータが“１”であり、かつ、ＴＣＡＭデータが“１”または“＊”の場合、もしくは、サーチデータが“０”であり、かつ、ＴＣＡＭデータが“０”または“＊”の場合（すなわち、両者が一致する場合）、プリチャージされたマッチ線ＭＬの電位（電源電位ＶＤＤレベル）は維持される。
【００４９】
上記のように、ＴＣＡＭでは、１つのエントリ（行）に対応するマッチ線ＭＬに接続された全てのＴＣＡＭセルのデータが入力サーチデータと一致しない限り、マッチ線ＭＬに蓄えられた電荷が引き抜かれる。このため、ＴＣＡＭでの検索は高速であるが、消費電流が大きいという問題がある。
【００５０】
図６は、実施形態に基づくセグメント（サブブロック）１２Ａの構成を説明する図である。
【００５１】
図６に示されるように、セグメント１２Ａは、ＴＣＡＭセルアレイ２０（単にセルアレイとも称する）と、書込ドライバ２１と、サーチ線ドライバ２２と、マッチアンプ部２３と、制御論理回路２４と、読出回路２５とを含む。
【００５２】
セグメント１２Ａは、図示していないがワード線ＷＬＸ，ＷＬＹを駆動するためのワード線ドライバ（不図示）と、制御信号やアドレス信号等の入力を受ける入出力回路（不図示）とを含む。
【００５３】
ＴＣＡＭセルアレイ２０は、行列状（ｍ行；ｋ列）に配列されたＴＣＡＭセルを含む。本例においては、セルアレイ２０は、行数（エントリ数）ｍがＮであり、列数（ビット数）ｋが４０の場合が示されている。
【００５４】
セルアレイ２０の各列に対応して、ｋ個（ｋ＝４０）のビット線対（ＢＬ［０］，ＢＬ＿ｎ［０］からＢＬ［ｋ−１］，ＢＬ＿ｎ［ｋ−１］まで）と、ｋ個（ｋ＝４０）のサーチ線対（ＳＬ［０］，ＳＬ＿ｎ［０］からＳＬ［ｋ−１］，ＳＬ＿ｎ［ｋ−１］まで）とが設けられる。
【００５５】
セルアレイ２０の各行に対応して、ｍ本（ｍ＝Ｎ）のマッチ線（ＭＬ［０］からＭＬ［Ｎ］まで）と、図示しないｍ本のＸセル用のワード線（ＷＬＸ［０］からＷＬＸ［ｍ−１］まで）と、図示しないｍ本のＹセル用のワード線（ＷＬＹ［０］からＷＬＹ［ｍ−１］まで）とが設けられている。
【００５６】
書込ドライバ２１は、書込時に、ビット線対ＢＬ，ＢＬ＿ｎを介して各ＴＣＡＭセルに書込データを供給する。サーチ線ドライバ２２は、検索時に、サーチ線対ＳＬ，ＳＬ＿ｎを介して各ＴＣＡＭセルにサーチデータを供給する。
【００５７】
制御論理回路２４は、セグメント１２Ａ全体の動作を制御する。たとえば、制御論理回路２４は、検索時には、サーチコマンドを受け取り、サーチ線ドライバ２２と、マッチアンプ部２３に制御信号を出力することによって、サーチ線ドライバ２２、マッチアンプ部２３、およびプリチャージ回路の動作を制御する。制御論理回路２４は、読出時には読出コマンドを受け取り、読出回路２５を制御する制御信号を出力する。これによりセルアレイ２０に格納されているエントリデータを読み出して出力することが可能である。
【００５８】
マッチアンプ部２３は、セルアレイの行にそれぞれ対応する複数のマッチアンプＭＡを含む。マッチアンプＭＡは、検索時に、対応するマッチ線ＭＬの電位に基づいて、対応するＴＣＡＭセルデータと入力サーチデータの対応部分とが一致するか否かを検出する。この実施形態では、マッチアンプＭＡは、検索時に対応するマッチ線ＭＬをプリチャージするためのプリチャージ回路を含む。
【００５９】
図７は、サーチ線ドライバ２２の構成の一例を示す回路図である。
図７に示されるように、サーチ線ドライバ２２は、サーチ線イネーブル信号ｓｅｎａが「Ｈ」レベルに活性化されたときに、入力サーチデータｓｋｅｙ［ｉ］（ｉ＝０，１，…，ｋ）をサーチ線ＳＬ［ｉ］に出力する。また、入力サーチデータｓｋｅｙ［ｉ］の論理レベルを反転した信号を相補のサーチ線ＳＬ＿ｎ［ｉ］に出力する。
【００６０】
本例においては、一例として、検索キーＳＢは、入力サーチデータｓｋｅｙ［ｉ］（ｉ＝０，１，…，ｋ）として構成されている場合について説明する。
【００６１】
具体的に、サーチ線ドライバ２２は、サーチ線ＳＬ［０］〜ＳＬ［ｋ］にそれぞれ対応するＡＮＤゲート６０［０］〜６０［ｋ］と、サーチ線ＳＬ＿ｎ［０］〜ＳＬ＿ｎ［ｋ］にそれぞれ対応するＡＮＤゲート６１［０］〜６１［ｋ］と、インバータ６２［０］〜６２［ｋ］とを含む。
【００６２】
サーチ線イネーブル信号ｓｅｎａは、ＡＮＤゲート６０［０］〜６０［ｋ］およびＡＮＤゲート６１［０］〜６１［ｋ］に共通に入力される。さらに、ＡＮＤゲート６０［ｉ］（ｉ＝０，１，…，ｋ）には、対応する入力サーチデータｓｋｅｙ［ｉ］が入力される。
【００６３】
ＡＮＤゲート６０［ｉ］（ｉ＝０，１，…，ｋ）の出力信号はサーチ線ＳＬ［ｉ］に送信される。ＡＮＤゲート６１［ｉ］（ｉ＝０，１，…，ｋ）には、対応する入力サーチデータｓｋｅｙ［ｉ］を反転した信号が入力される。
【００６４】
上記構成によれば、たとえば、サーチ線イネーブル信号ｓｅｎａが「Ｈ」レベルに活性化され、かつ、入力サーチデータｓｋｅｙ［ｉ］が「Ｈ」レベル（“１”）である場合には、サーチ線ＳＬ［ｉ］の電圧が「Ｈ」レベルとなり、サーチ線ＳＬ＿ｎ［ｉ］の電圧が「Ｌ」レベルとなる。サーチ線イネーブル信号ｓｅｎａが「Ｈ」レベルに活性化され、かつ、入力サーチデータｓｋｅｙ［ｉ］が「Ｌ」レベル（“０”）である場合には、サーチ線ＳＬ［ｉ］の電圧が「Ｌ」レベルとなり、サーチ線ＳＬ＿ｎ［ｉ］の電圧が「Ｈ」レベルとなる。
【００６５】
図８は、マッチアンプの構成の一例を示す回路図である。
図８を参照して、マッチアンプＭＡは、プリチャージ回路としてのＰチャネルＭＯＳトランジスタ７０と、インバータ７１〜７４とを含む。
【００６６】
プリチャージ回路としてのＭＯＳトランジスタ７０がマッチアンプＭＡの内部にあるように図示しているが、ＭＯＳトランジスタ７０はマッチアンプＭＡの外部に設けられていても構わない。制御論理回路２４は、マッチアンプイネーブル信号ｍａｅを出力する。
【００６７】
また、上記したように、本例においては、ｓｅ端子がマッチ線のプリチャージを行なうプリチャージ信号として用いられる。ここでは、ｓｅ端子からの入力をインバータにより反転し、当該反転信号をプリチャージ信号としてＭＯＳトランジスタ７０に入力する場合が示されている。
【００６８】
したがって、図３で説明したように初段のセグメントにおいては、ｓｅ端子は検索コマンドとして「Ｈ」レベル（“１”）が入力された場合に、全てのマッチ線はプリチャージされることになる。
【００６９】
一方、２段目以降のセグメントにおいては、前段のセグメントにおけるマッチアンプＭＡからの出力がｓｅ端子と接続されているため前段のマッチアンプＭＡからの出力が「Ｌ」レベルの場合には、次段のセグメントにおける同一行のマッチ線は、プリチャージされない。一方、前段のマッチアンプＭＡからの出力が「Ｈ」レベルの場合には、次段のセグメントにおける同一行のマッチ線は、プリチャージされる。したがって、前段のセグメントのマッチアンプ出力を後段セグメントのｓｅ端子と接続することにより、前段のセグメントで一致したエントリのみを検索対象とすることが可能である。前段のセグメントの検索で不一致となった領域の分だけ後段セグメントの消費電力を抑えることが可能である。
【００７０】
以下、上記の構成要素の接続について説明する。ＭＯＳトランジスタ７０は、対応するマッチ線ＭＬと電源電位ＶＤＤを与える電源ノードとの間に接続される。ＭＯＳトランジスタ７０のゲートには、ｓｅ端子の反転信号であるマッチ線プリチャージ信号が入力される。マッチ線ＭＬは、さらに、インバータ７１の入力ノードに接続される。インバータ７１の出力ノードは、インバータ７４の入力ノードに接続される。インバータ７４の出力ノードは、インバータ７２を介してインバータ７２の入力ノードに接続される。
【００７１】
マッチアンプイネーブル信号ｍａｅおよびその論理レベルをインバータ７３によって反転させた信号は、インバータ７１，７２の駆動電源ノードに接続される。マッチアンプイネーブル信号ｍａｅが非活性状態（「Ｌ」レベル）のとき、インバータ７１は非動作状態となり、インバータ７２は動作状態となる。マッチアンプイネーブル信号ｍａｅが活性状態（「Ｈ」レベル）のとき、インバータ７１は動作状態となり、インバータ７２は非動作状態となる。
【００７２】
次に、マッチアンプＭＡの回路動作について説明する。マッチ線プリチャージ信号が活性化される（「Ｌ」レベルになる）ことによって、ＭＯＳトランジスタ７０が導通する。これによって、マッチ線ＭＬが電源電位ＶＤＤまで充電される（プリチャージされる）。
【００７３】
マッチ線プリチャージ信号が非活性化された後に、サーチ線イネーブル信号ｓｅｎａが活性化される（「Ｈ」レベルになる）ことによって、サーチ線対ＳＬ，ＳＬ＿ｎにサーチデータが入力される。これによって、マッチ線ＭＬの電位がサーチ結果（入力サーチデータの対応部分とＴＣＡＭセルデータとの比較結果）に依存して変化する。すなわち、一致（ヒット：hit）の場合、マッチ線ＭＬの電位は電源電位ＶＤＤ（「Ｈ」レベル）のまま維持され、不一致（ミス：miss）の場合、マッチ線ＭＬの電荷が接地ノードに放電されるのでマッチ線のＭＬ電位は接地電位（「Ｌ」レベル）に変化する。
【００７４】
次に、マッチアンプイネーブル信号が活性化される（「Ｈ」レベルになる）。これによって、サーチ結果に基づくマッチ線ＭＬの電位が、インバータ７１およびインバータ７４を介してマッチアンプ出力信号ｍｏとして出力される。マッチアンプイネーブル信号ｍａｅが非活性化される（「Ｌ」レベルになる）と、インバータ７４とインバータ７２とによって構成されるラッチ回路により、サーチ結果に基づくマッチ線ＭＬの電位が保持される。
【００７５】
＜検索ブロック１０の検索方式＞
図９は、実施形態１に基づく検索ブロック１０の検索方式を説明する図である。
【００７６】
図９に示されるように、検索ブロック１０は、設定レジスタ１６と、再配置制御信号生成部１５と、再配置回路１７，１８と、ＴＣＡＭ装置１２とを含む。
【００７７】
再配置制御信号生成部１５と、再配置回路１７，１８とはデータ変更部２７を構成する。
【００７８】
ＴＣＡＭ装置１２は、時分割検索機能を有する。
再配置回路１７，１８は、クロスバースイッチである。
【００７９】
再配置制御信号生成部１５は、設定レジスタ１６のレジスタ値に基づいて再配置回路１７，１８に対して再配置を指示する制御信号を出力する。
【００８０】
本例においては、再配置回路１７，１８としてクロスバースイッチを用いているが、時分割検索に有効な領域を特定の場所に再配置できるような回路であればどのようなものでも良い。たとえば、データの上位と下位のビットを入れ替えるような構成、あるいはローテーション回路等を用いてもよい。
【００８１】
本例においては、検索ブロック１０の構成として、ＴＣＡＭ装置を挙げて説明するが、特にこれに限られず時分割検索が可能なデータ構造であれば何であっても構わない。
【００８２】
検索ブロック１０は、入力ピンとして、書込および検索時に使用するデータバスと制御系のピンを有する。また、検索ブロック１０は、出力ピンとして、検索結果出力ピンおよび読出結果出力データバスを有する。
【００８３】
再配置回路１７，１８は、これら入力および出力データバスの信号に対する再配置を実行する。具体的には、データ配列順序を変更する。
【００８４】
再配置回路１７，１８は、再配置制御信号生成部１５で生成された制御信号に従ってデータ配列順序を変更する。
【００８５】
本例においては、ＴＣＡＭ装置１２は、上記したように４つのセグメント（サブブロック）に分割する場合について説明する。当該４つのセグメント（サブブロック）のうち１番目のセグメント（サブブロック）をプリサーチ対象とし、２〜４番目のセグメント（サブブロック）をポストサーチ対象とする。
【００８６】
本例においては、設定レジスタ１６は、４つのセグメント（サブブロック）にそれぞれ対応して分割された１〜４番目のエントリデータのうちプリサーチ用のエントリデータの番号を指定する。設定レジスタ１６には、一例として２ビットのデータが格納される。
【００８７】
再配置制御信号生成部１５は、設定レジスタ１６のデータに基づいて制御信号Ｓ１〜Ｓ４を生成する。
【００８８】
例えば、設定レジスタ１６に「００」が格納されている場合には、再配置制御信号生成部１５は、制御信号Ｓ１を再配置回路１７，１８に出力する。
【００８９】
再配置回路１７，１８は、制御信号Ｓ１が入力された場合には、データ配列順序を変更せず、そのままの形式で出力する。
【００９０】
設定レジスタ１６に「０１」が格納されている場合には、再配置制御信号生成部１５は、制御信号Ｓ２を再配置回路１７，１８に出力する。
【００９１】
再配置回路１７，１８は、制御信号Ｓ２が入力された場合には、データ配列順序を変更して、出力する。ＴＣＡＭ装置１２は、４つのセグメント（サブブロック）に分割されているため書込データあるいは検索キーについてもそれぞれのセグメントに対応させるため４つのフィールドに分割される。再配置回路１７は、制御信号Ｓ２の入力に従って書込データあるいは検索キーの２番目のフィールドと１番目のフィールドとを入れ替えるデータ配列順序に変更する。
【００９２】
再配置回路１８は、制御信号Ｓ２の入力に従って読出データの２番目のフィールドと１番目のフィールドとを入れ替えるデータ配列順序に変更する。
【００９３】
設定レジスタ１６に「１０」が格納されている場合には、再配置制御信号生成部１５は、制御信号Ｓ３を再配置回路１７，１８に出力する。
【００９４】
再配置回路１７，１８は、制御信号Ｓ３が入力された場合には、データ配列順序を変更して、出力する。書込データあるいは検索キーは４つのフィールドに分割される。再配置回路１７は、制御信号Ｓ３の入力に従って書込データあるいは検索キーの３番目のフィールドと１番目のフィールドとを入れ替えるデータ配列順序に変更する。
【００９５】
再配置回路１８は、制御信号Ｓ３の入力に従って読出データの３番目のフィールドと１番目のフィールドとを入れ替えるデータ配列順序に変更する。
【００９６】
設定レジスタ１６に「１１」が格納されている場合には、再配置制御信号生成部１５は、制御信号Ｓ４を再配置回路１７，１８に出力する。
【００９７】
再配置回路１７，１８は、制御信号Ｓ４が入力された場合には、データ配列順序を変更して、出力する。書込データあるいは検索キーは４つのフィールドに分割される。再配置回路１７は、制御信号Ｓ４の入力に従って書込データあるいは検索キーの４番目のフィールドと１番目のフィールドとを入れ替えるデータ配列順序に変更する。
【００９８】
再配置回路１８は、制御信号Ｓ４の入力に従って読出データの４番目のフィールドと１番目のフィールドとを入れ替えるデータ配列順序に変更する。
【００９９】
（検索メモリ８の初期化（設定）について）
図１で説明した通信機器１には、ＡＣＬやＦＩＢ（Forwarding Information Base）など、転送処理を行う上で必要なルールセットを有する。
【０１００】
これらはユーザーによって手動で設定される場合もあれば、特定の通信プロトコルによって自動生成される場合もある。
【０１０１】
各ルールセットは、それぞれＩＰアドレスやポート番号といったパケット転送処理に必要な情報が含まれるフィールド群で構成される。
【０１０２】
各ルールセットは、すべてのフィールドに情報が完全に設定されたルールも存在するが、中にはフィールドに部分的にしか情報が設定されていないルールも存在する。
【０１０３】
一例として、例えばＩＰｖ４アドレスは３２ビットのデータであるが、ネットワーク部・ホスト部という概念があり、しばしばネットワーク部の上位Ｎビットだけを検索対象とし下位（３２−Ｎ）ビットは検索対象に含めないといった運用がなされている。
【０１０４】
この検索対象に含めない部分は、検索メモリ８上では“ドントケア（Don't Care）”のデータが書き込まれることになる。
【０１０５】
この“ドントケア（Don't Care）”のビットを大量に含むフィールドを、時分割検索の初段セグメント（サブブロック）に割り当てた場合、エントリの絞り込みとして機能しないため、時分割検索による低消費電力化が得られ難くなる。
【０１０６】
また、ポート番号に関しては１０２４〜６５３３５といったように特定の範囲をまとめて扱う場合ある。このようは範囲情報を含むルールセットに関してはレンジ展開アルゴリズムを用いて複数のエントリで一つのルールを表現する手法が用いられる。
【０１０７】
このときポート番号以外のすべてのフィールドには同じデータがコピーされた状態となっている。
【０１０８】
したがって、検索メモリ８に、ルールセットを格納した場合にはエントリの絞り込みが有効に働かないフィールド領域が局所的に存在することになる。
【０１０９】
実施形態においては、時分割検索において、当該エントリの絞り込みが有効に働く可能性の高いフィールド領域を初段セグメント（サブブロック）に割り当てる。
【０１１０】
検索メモリ８の初期化（設定）を行うに際し、ＣＰＵ２は、検索メモリ８に格納する各ルールセットの解析処理を実行する。
【０１１１】
通常、各ルールセットはテーブル形式で保持されているが、各ルールテーブルは人間が管理しやすい形式で表現されている。したがって、各ルールテーブルを検索用のハードウェアに適した形式に変換する必要がある。
【０１１２】
変換された各テーブルは、検索メモリ８の各ブロックに割り付けられ、設定レジスタ１６のデータ幅やマスク設定、プロファイルレジスタ２６の設定が行われる。
【０１１３】
ＣＰＵ２は、各ルールテーブルを検索ブロック１０の単位に分割したサブテーブルに対してデータ解析を行う。
【０１１４】
ＣＰＵ２は、サブテーブルに対するデータ解析により各検索ブロック１０において時分割検索に有効なフィールドを特定する。
【０１１５】
本例においては、検索ブロック１０に含まれるＴＣＡＭ装置１２が、４つのサブブロックを有する場合について説明する。
【０１１６】
一例として、サブテーブルのエントリデータの長さが１６０ビットである場合、４０ビットずつの４つのフィールドに分割する。
【０１１７】
ＣＰＵ２は、各検索ブロック１０に格納するサブテーブルのうち４つのサブブロックにそれぞれ対応する４つのフィールドの中からいずれのフィールドが時分割検索に有効なフィールドかを特定する。
【０１１８】
この点で、“ドントケア（Don't Care）”のビットが無いあるいは少ないフィールドを有効なフィールドとして特定する。
【０１１９】
一例として、１番目〜４番目のフィールドのうち２番目のフィールドが有効なフィールドとして特定されるものとする。
【０１２０】
この場合、ＣＰＵ２は、当該解析結果に基づき検索ブロック１０の設定レジスタ１６に「０１」を設定する。
【０１２１】
これにより、設定レジスタ１６に「０１」が格納されている場合には、再配置制御信号生成部１５は、制御信号Ｓ２を再配置回路１７，１８に出力する。
【０１２２】
再配置回路１７，１８は、制御信号Ｓ２が入力された場合には、データ配列順序を変更する。
【０１２３】
この場合、再配置回路１７は、サブテーブルのエントリデータの２番目のフィールドと、１番目のフィールドとを入れ替えるデータ配列順序に変更する。
【０１２４】
そして、当該変更されたデータ配列順序に従うサブテーブルが４つのサブブロックにそれぞれ格納される。すなわち、データ配列順序が変更されなかった場合には、１番目のサブブロックにサブテーブルの１番目のフィールドのデータが格納され、２番目のサブブロックにサブテーブルの２番目のフィールドが格納されるところ、データ配列順序を変更することで、１番目のサブブロックにサブテーブルの２番目のフィールドが格納され、２番目のサブブロックにサブテーブルの１番目のフィールドが格納されることになる。
【０１２５】
上記設定が、各検索ブロック１０毎に行なわれる。
したがって、図２に示される検索ブロック１０−１〜１０−ｎにおいて、それぞれ格納されるサブテーブルの解析結果に基づいて設定レジスタ１６に格納される値はそれぞれ異なる場合がある。
【０１２６】
これにより、検索メモリ８の初期化（設定）が完了し、実際の転送処理、すなわちデータ書込処理が開始される。
【０１２７】
（検索メモリ８の検索について）
検索時においては、検索キー生成部２９により検索キーが生成される。
【０１２８】
当該検索キーが各検索ブロック１０に出力される。
各検索ブロック１０においては、上記したように設定レジスタ１６の値に基づいて、制御信号が生成される。
【０１２９】
一例として、設定レジスタ１６の値が「０１」の場合には、再配置制御信号生成部１５は、制御信号Ｓ２を再配置回路１７，１８に出力する。
【０１３０】
再配置回路１７，１８は、制御信号Ｓ２が入力された場合には、データ配列順序を変更して、検索キーを出力する。
【０１３１】
この場合、再配置回路１７は、入力された検索キーを４つの検索キーＳＡ〜ＳＤに分割し、２番目の検索キーＳＢと１番目の検索キーＳＡとのデータ配列順序を変更する。
【０１３２】
そして、再配置回路１７は、データ配列順序を変更した検索キーをそれぞれのセグメント１２Ａ〜１２Ｄに出力する。すなわち、２番目の検索キーＳＢはセグメント１２Ａに出力され、１番目の検索キーＳＡはセグメント１２Ｂに出力される。
【０１３３】
これにより、本来であるならば第２の検索として実行されるサブテーブルの２番目のフィールドと、検索キーＳＢとの比較処理とが第１の検索として実行される。サブテーブルの２番目のフィールドは、“ドントケア（Don't Care）”のビットが無いあるいは少ない有効なフィールドとして特定されたものであり、不一致となり易い。
【０１３４】
したがって、不一致となった場合には、後段セグメントの不一致のエントリは検索対象とはならないため後段セグメントの消費電力を抑えることが可能である。
【０１３５】
なお、本例においては、サブテーブルの２番目のフィールドが有効なフィールドとして特定された場合について説明したが、特にこれに限られず、３番目、４番目のフィールドが有効なフィールドとして特定された場合についても同様に適用可能で有る。
【０１３６】
図１０は、検索ブロック１０の検索のタイミングを説明する図である。
図１０に示されるように、検索ブロック１０は、クロックＣＬＫに同期して動作する。
【０１３７】
クロックＣＬＫに同期して再配置回路１８は、時刻Ｔ１において検索キー（ｋｅｙＡ）を取得する。そして、時刻Ｔ２において、設定レジスタ１６から出力される制御信号に基づいて変更されたデータ配列順序に従う検索キー（ｋｅｙＢ）をＴＣＡＭ装置１２に出力する。時刻Ｔ３において、ＴＣＡＭ装置１２は、再配置回路１８から出力された検索キー（ｋｅｙＢ）の入力を受け付けて検索動作を実行する。
【０１３８】
次のクロックＣＬＫの同期タイミングにおける時刻Ｔ４において、初段のセグメント１２Ａから結果が出力された場合が示されている。
【０１３９】
また、次のクロックＣＬＫの同期タイミングにおける時刻Ｔ５において、次段のセグメント１２Ｂから結果が出力された場合が示されている。
【０１４０】
当該処理繰り返されて最終段のセグメント１２Ｄからの検索結果が出力される。
（検索メモリ８の読出について）
検索メモリ８に格納されたエントリデータの読出時について説明する。
【０１４１】
設定レジスタ１６の値が「０１」の場合には、再配置制御信号生成部１５は、制御信号Ｓ２を再配置回路１８に出力する。
【０１４２】
再配置回路１８は、制御信号Ｓ２が入力された場合には、データ配列順序を変更して、出力する。
【０１４３】
この場合、再配置回路１８は、セグメント１２Ａ〜１２Ｄからそれぞれ読み出されたエントリデータのデータ配列順序を変更する。
【０１４４】
具体的には、セグメント１２Ａから読み出されたデータと、セグメント１２Ｂから読み出されたデータとのデータ配列順序を変更する。セグメント１２Ｂから読み出されたデータを１番目、セグメント１２Ｂから読み出されたデータを２番目、セグメント１２Ｃ，セグメント１２Ｄから読み出されたデータを３番目、４番目として出力する。
【０１４５】
当該方式により、検索ブロック１０に格納する前のデータ配列順序変更前のデータに簡易に復元することが可能である。
【０１４６】
したがって、実施形態においては、このため不一致となりやすいと思われるフィールドを初段セグメントに書き込まれるように設定レジスタ１６を設定する事で、このような時分割検索の効果を最大化することが可能になる。
【０１４７】
（検索メモリ８のメンテナンスについて）
検索メモリ８のメンテナンス動作について説明する。
【０１４８】
ネットワーク制御プロトコルによる自動更新やネットワーク管理者によるポリシーの変更など、ルールテーブルは様々な理由により実動作中に更新が行われる。具体的には、エントリの上書きや、新規追加が行われる。
【０１４９】
動作中に設定レジスタ１６を書き換えることはできないため、ルールテーブルの更新によって最初のルールテーブルの解析内容と、最新のルールテーブルの情報の解析内容とに乖離が生じ、時分割検索による低消費電力効果が低下する可能性がある。
【０１５０】
実施形態においては、ＣＰＵ２が検索メモリ８のメンテナンス処理を実行する場合について説明するが、特にＣＰＵ２に限られず、ＮＰＵ等の転送制御回路４が実行するようにしても良いし、検索メモリ８にメンテナンス処理を実行するチップを内蔵する構成としても良い。
【０１５１】
図１１は、検索メモリ８のメンテナンス動作について説明する図である。
図１１に示されるように、メンテナンス処理は、所定の時間経過あるいは、検索メモリ８に対する書込コマンドの発行回数等をトリガーとして実行する。ここでは、タイマー等により所定の時間経過により割り込みとしてトリガーが生成された場合が示されている。
【０１５２】
次に、ＣＰＵ２は、検索メモリ８の対象となる検索ブロック１０、例えば検索ブロック１０−１に格納されている最新のルールテーブルを読み出す（全エントリ読み出し）（１）。上記したように、検索ブロック１０−１から読み出す際には、設定レジスタ１６のレジスタ値に基づいて再配置回路１８によりデータ配列順序を変更する。これにより、初期のデータ配列に復元され、後述する空きの検索ブロック１０、例えば検索ブロック１０−ｎへの書込データとしてそのまま利用することが可能である。
【０１５３】
次に、ＣＰＵ２は、対象となる検索ブロック１０−１から読み出した最新のルールテーブルを解析する処理を実行し、解析結果により設定レジスタ１６に格納するレジスタ値に関する情報を生成する（２）。
【０１５４】
そして、次に、ＣＰＵ２は、現在の設定レジスタ１６、すなわち、検索ブロック１０−１の設定レジスタ１６に格納されているレジスタ値と、生成したレジスタ値に関する情報とが同じか否かを確認する。
【０１５５】
すなわち、検索ブロック１０−１の設定レジスタ１６のレジスタ値がエントリの絞り込みを有効に働かせることが可能なフィールド領域を指定しているか否かを判断する。時分割検索に有効なフィールドか否かを判断する。
【０１５６】
ＣＰＵ２は、生成したレジスタ値に関する情報が、検索ブロック１０−１の設定レジスタ１６に格納されているレジスタ値と異なると判断した場合には、当該生成したレジスタ値に関する情報を空きの検索ブロック１０、すなわち検索ブロック１０−ｎの設定レジスタ１６に格納する（３）。
【０１５７】
そして、当該空きの検索ブロック１０−ｎのＴＣＡＭ装置１２に元の検索ブロック１０−１から取得した最新のルールテーブルの情報をコピーする（４）。
【０１５８】
その際、検索ブロック１０−ｎの再配置回路１７，１８は、格納した設定レジスタ１６のレジスタ値に基づいて、データ配列順序を変更する。そして、上記したように空きの検索ブロック１０−ｎの初段のセグメントに検索に有効なフィールドのデータを格納する。
【０１５９】
ＣＰＵ２は、コピーが完了した場合に、プロファイルレジスタ２６を設定し直し、検索となる元の対象となる検索ブロック１０−１からコピー先となる検索ブロック１０−ｎに差し替える（５）。
【０１６０】
新しい検索ブロック１０は時分割検索の低消費電力効果が最大化されているため、システム全体の低消費電力化に貢献する。
【０１６１】
当該メンテナンス方式により、システム全体の動作を止めることなく消費電力を下げることが可能である。
【０１６２】
また、検索メモリにはNetFlow/FIB/QoS/ACL等の性質の異なる様々なルールテーブルが書き込まれ、また前述の通りレンジ展開アルゴリズム等の処理が行われる。したがって、実際に検索ブロックに書き込まれるデータには偏りが生じやすい。このようなデータ構造に対して一様に時分割検索を実行すると、あるブロックに対しては時分割検索が極めて有効となり、別のあるブロックに対しては全く有効ではないという状況が発生する。
【０１６３】
特に、ＩＰｖ６アドレスを用いたテーブルでは大きなドントケアの塊が生じやすく、この部分は検索対象のエントリの絞り込みには不適切であるため、時分割検索の初段セグメントに割り当てられた場合、時分割検索は全く効果がなくなる。
【０１６４】
実施形態に基づく方式を採用することにより、このようなブロック毎の偏りを無くすことが可能であり、結果として時分割検索による省電力効果を最大化することが可能となる。
【０１６５】
また、実施形態１に従う方式により、１つの検索キーから各検索ブロック毎に時分割検索に最適な検索キーを生成することが可能となるため、複数の検索命令を１回でまとめることが可能になり、スループットを向上させることが可能となる。
【０１６６】
また、ＴＣＡＭ装置のように消費電力の大きなデバイスでは、システムの熱設計、電源設計の観点から検索対象の検索ブロックを限定して検索操作を複数回に分割実行することがある。このようなケースにおいて消費電力を削減することは分割操作を無くすないしは減らすことにつながり、検索操作のスループット向上にも寄与する。
【０１６７】
（実施形態２）
実施形態２においても、エンドユーザーが作成したルールセットを検索メモリ８に適したテーブル形式に変換し、それをさらに細かい領域に分割して解析を行い、設定レジスタ１６を設定する。
【０１６８】
上記の実施形態１においては、ＴＣＡＭ装置１２の初段セグメントに検索に有効なフィールドの情報を格納する場合について説明した。
【０１６９】
実施形態２においては、検索に有効なフィールドの情報として、ドントケアビットを含まない領域をＢＣＡＭ（Binary Content Addressable Memory）装置に格納する。そして、残りの領域をＴＣＡＭ装置に格納する。なお、本例においては、ＢＣＡＭ装置を用いる場合について説明するが、ＡＳＥ(Algorithmic Search Engine :SRAMやFFのような記憶素子とツリー・ハッシュといった検索アルゴリズムを実現する論理回路とを組合せて検索を実現するもの)を用いる構成としても良い。
【０１７０】
図１２は、実施形態２に基づく検索ブロック１０＃の検索方式を説明する図である。
図１２に示されるように、検索ブロック１０＃は、検索ブロック１０と比較して、ＴＣＡＭ装置１２の代わりに、ＢＣＡＭ装置１２Ｐと、ＴＣＡＭ装置１２Ｑとが設けられた点が異なる。その他の構成については、図９で説明したのと同様であるのでその詳細な説明については繰り返さない。
【０１７１】
図１３は、ＢＣＡＭ装置１２ＰのＢＣＡＭセルＭＣ＃の構成の一例を示す回路図である。
【０１７２】
図１３を参照して、ＢＣＡＭセルＭＣ＃は、１個のＳＲＡＭセル１１と、データ比較部１３＃とを含む。ＳＲＡＭセル１１は、内部の記憶ノード対ＮＤ１，ＮＤ１＿ｎに互いに相補となる（一方が“１”のとき他方が“０”となる）１ビット（ｂｉｔ）のデータを記憶する。
【０１７３】
ＢＣＡＭセルは、ビット線対ＢＬ，ＢＬ＿ｎ、サーチ線対ＳＬ，ＳＬ＿ｎ、マッチ線ＭＬ、およびワード線ＷＬＸと接続される。ビット線対ＢＬ，ＢＬ＿ｎは、列方向（Ｙ方向）に延在し、列方向に配列された複数のＢＣＡＭセルによって共有される。サーチ線対ＳＬ，ＳＬ＿ｎは、列方向（Ｙ方向）に延在し、列方向に配列された複数のＢＣＡＭセルによって共有される。
【０１７４】
マッチ線ＭＬは、行方向（Ｘ方向）に延在し、行方向に配列された複数のＢＣＡＭセルによって共有される。ワード線ＷＬＸは、行方向（Ｘ方向）に延在し、行方向に配列された複数のＢＣＡＭセルによって共有される。
【０１７５】
データ比較部１３＃は、データ比較部１３と比較して、ＭＯＳトランジスタＱ８，Ｑ９を削除した点が異なる。その他の構成については、データ比較部１３と同様であるのでその詳細な説明については繰り返さない。
【０１７６】
実施形態２の検索ブロック１０＃において、第一の検索をＢＣＡＭ装置で行い、第二の検索以降をＴＣＡＭ装置で実行する。そして、検索結果を生成するという時分割動作を実行する。なお、ＢＣＡＭ装置には、ルールセットにおけるドントケアを含まないフィールドが格納される。
【０１７７】
設定レジスタ１６の値としては、Binaryセグメントが時分割検索のＢＣＡＭ装置による初段セグメントに割り当てられるように設定する。
【０１７８】
再配置制御信号生成部１５は、設定レジスタ１６の値に基づいて制御信号を生成する。
再配置回路１７，１８は、再配置制御信号生成部１５で生成された制御信号に基づいて検索キーのデータ配列順序を変更する。
【０１７９】
なお、設定レジスタ１６の値は、各セグメントをＢＣＡＭ装置あるいはＴＣＡＭ装置のどちらに割り当てるかの判断につながるものであるならばどのようなものでも良い。なお、ツリー検索のＡＳＥを用いる場合はＬＰＭ（Longest Prefix Match)も有効な情報として使えるし、具体的な検索順序を記述するようなものであっても良い。
【０１８０】
この場合、ＡＳＩＣ回路あるいはＮＰＵから見て、検索メモリ８の内部構造を意識する必要はなく、各検索ブロックの設定レジスタのレジスタ値を適切に設定することにより自動的に検索テーブルの分割と再配置を実行することが可能である。
【０１８１】
（検索メモリ８の検索について）
検索時においては、検索キー生成部２９により検索キーが生成される。
【０１８２】
当該検索キーが各検索ブロック１０＃に出力される。
各検索ブロック１０＃に分配された検索キーは、設定レジスタ１６の値に基づいて再配置回路１７により検索キーのデータ配列順序が変更される。
【０１８３】
そして、再配置回路１７によって再配置された後、ＢＣＡＭ装置１２ＰとＴＣＡＭ装置１２Ｑとにそれぞれ分割されて出力される。
【０１８４】
そして、ＢＣＡＭ装置１２Ｐにおいて、受け取った検索キーとＢＣＡＭ装置１２Ｐに格納された各エントリデータとの比較動作が実行される。そして、ＢＣＡＭ装置１２Ｐからその全ての比較結果が制御信号ＭＬＯＵＴとして出力される。
【０１８５】
ＴＣＡＭ装置１２Ｑは、受け取った検索キーと、各エントリデータとの比較動作を制御信号ＭＬＯＵＴによって制御する。具体的には、実施形態１で説明したのと同様に、制御信号ＭＬＯＵＴをｓｅ端子と接続する。当該構成により、ＢＣＡＭ装置１２Ｐでヒットしたエントリデータに対応するエントリデータのみ検索キーとの比較動作を実行することにより、ＴＣＡＭ装置１２Ｑの消費電力を抑えることが可能となる。
【０１８６】
ＴＣＡＭ装置１２Ｑにおいて、検索結果はプライオリティエンコーダに渡され、最終的な検索結果アドレスが生成される。
【０１８７】
当該構成により、ルールテーブルの一部をＢＣＡＭ装置１２Ｐに格納することにより、ＴＣＡＭ装置に全てのルールテーブルを格納する場合に比べて面積を縮小することが可能となる。
【０１８８】
上記の実施形態１では、設定レジスタを設定する際にルールテーブルを解析し、時分割検索におけるエントリの絞り込みに有効であると思われるフィールドを特定する必要があった。これにはドントケアのビットの数や一定範囲に含まれるデータのばらつきなどを解析する必要があるが、実施形態２においては、バイナリあるいはターナリの判定だけで解析することができるためメンテナンスにかかるＣＰＵ２の処理も削減することが可能である。
【０１８９】
（変形例）
上記の実施形態２においては、複数の異なる検索モジュールを接続し時分割検索を実施する場合について説明した。
【０１９０】
一方で、第１の検索が出力されるまでの遅延に合わせて第２の検索に対する信号入力を遅延させる必要がある。
【０１９１】
図１４は、実施形態２の変形例に基づく検索ブロック１０Ａの検索方式を説明する図である。
【０１９２】
図１４に示されるように検索ブロック１０Ａは、検索ブロック１０＃と比較して、タイミング調整回路１９を設ける。
【０１９３】
タイミング調整回路１９は、再配置回路１８と、データ保持に用いられるデータフリップフロップ回路ＤＦＦ１〜ＤＦＦ４と、セレクタＳＥＬ１〜ＳＥＬ４とを含む。
【０１９４】
データフリップフロップ回路ＤＦＦ１〜ＤＦＦ４は、再配置回路１８から出力された信号を保持する。
【０１９５】
セレクタＳＥＬ１〜ＳＥＬ４は、再配置回路１８から出力される信号と、データフリップフロップ回路ＤＦＦ１〜ＤＦＦ４とのいずれを選択して出力するかを切り替える。
【０１９６】
セレクタＳＥＬ１〜ＳＥＬ４の選択を切り替える切替信号は、再配置制御信号生成部１５＃から出力される。
【０１９７】
例えば、本例の場合には、セレクタＳＥＬ１〜ＳＥＬ３は、ＴＣＡＭ装置１２Ｑに検索キーを出力する構成であるためデータフリップフロップ回路ＤＦＦ１〜ＤＦＦ３からのデータを出力する。
【０１９８】
一方、セレクタＳＥＬ４は、ＢＣＡＭ装置１２Ｐに検索キーを出力する構成であるためデータフリップフロップ回路ＤＦＦ４からのデータではなく、再配置回路１８からのデータをそのまま出力する。
【０１９９】
図１５は、検索ブロック１０Ａの検索のタイミングを説明する図である。
図１５に示されるように、検索ブロック１０Ａは、クロックＣＬＫに同期して動作する。
【０２００】
クロックＣＬＫに同期して再配置回路１８は、時刻Ｔ１０において検索キー（ｋｅｙＡ）を取得する。そして、時刻Ｔ１１において、設定レジスタ１６から出力される制御信号に基づいて変更されたデータ配列順序に従う検索キー（ｋｅｙＢ）をＢＣＡＭ装置１２Ｐに出力する。ここでは一例として、１６０ビット幅の検索キーが入力されて、４０ビットの検索キーをＢＣＡＭ装置１２Ｐに出力し、残りの１２０ビットの検索キーをＴＣＡＭ装置１２Ｑに分割して出力する場合について説明する。
【０２０１】
時刻Ｔ１２において、ＢＣＡＭ装置１２Ｐにおいて、再配置回路１８から出力された検索キー（ｋｅｙＢ）の入力を受け付けて検索動作を実行する。
【０２０２】
そして、次のクロックＣＬＫの同期タイミングにおける時刻Ｔ１３において、ＢＣＡＭ装置１２Ｐから結果が出力された場合が示されている。
【０２０３】
そして、同様のタイミングにおける時刻Ｔ１３において、データフリップフロップ回路ＤＦＦ１〜３に保持されていた検索キー（ｋｅｙＣ）をＴＣＡＭ装置１２Ｑに出力する。
【０２０４】
本例においては、後段のセグメントであるＴＣＡＭ装置１２Ｑで使用する残りの１２０ビットの検索キーに関してはデータフリップフロップ回路ＤＦＦに一旦取り込まれるため１サイクル遅れてＴＣＡＭ装置１２Ｑに入力される。このためＴＣＡＭ装置１２Ｑは、検索キーの入力とＢＣＡＭ装置１２Ｐの検索結果の出力をほぼ同じタイミングで受け取ることが可能である。
【０２０５】
そして、時刻Ｔ１４において、ＢＣＡＭ装置１２Ｐからの結果に基づいて、検索キー（ｋｅｙＣ）におけるＴＣＡＭ装置１２Ｑの検索動作を実行する。
【０２０６】
次のクロックＣＬＫの同期タイミングにおける時刻Ｔ１５において、ＴＣＡＭ装置１２Ｑから結果が出力された場合が示されている。
【０２０７】
以上、本開示を実施形態に基づき具体的に説明したが、本開示は、実施形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【符号の説明】
【０２０８】
１  通信機器、４  転送制御回路、６  汎用メモリ、８  検索メモリ、１０，１０Ａ  検索ブロック、１２  ＴＣＡＭ装置、１３  データ比較部、１５  再配置制御信号生成部、１６  設定レジスタ、１７，１８  再配置回路、１９  タイミング調整回路、２０  ＴＣＡＭセルアレイ、２１  書込ドライバ、２２  サーチ線ドライバ、２３  マッチアンプ部、２４  制御論理回路、２５  読出回路、２６  プロファイルレジスタ、２７  データ変更部、２８  検索結果生成部、２９  検索キー生成部。
【図１】
2019008845.tif 000003
【図２】
2019008845.tif 000004
【図３】
2019008845.tif 000005
【図４】
2019008845.tif 000006
【図５】
2019008845.tif 000007
【図６】
2019008845.tif 000008
【図７】
2019008845.tif 000009
【図８】
2019008845.tif 000010
【図９】
2019008845.tif 000011
【図１０】
2019008845.tif 000012
【図１１】
2019008845.tif 000013
【図１２】
2019008845.tif 000014
【図１３】
2019008845.tif 000015
【図１４】
2019008845.tif 000016
【図１５】
2019008845.tif 000017