(57)【要約】      （修正有）【課題】検索要素ごとに検索条件を設定可能とし、複数の検索要素を一括して検索できるようにする。【解決手段】それぞれが２個の全比較器を含む複数の比較手段と、前記複数の比較手段を選択的に連結する連結手段と、検索ごとに前記複数の比較手段に判定式を設定するとともに、前記複数の比較手段が選択的に連結されるように前記連結手段を設定する設定手段を有する。比較器２０２は、それぞれが２個の全比較器を含む複数の比較器コア部３０１乃至３０４を有する。比較器コア部３０１乃至３０４は、検索ごとに、判定式が設定されるとともに、選択的に連結される。【選択図】図１１
2010211388.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが２個の全比較器を含む複数の比較手段と、
前記複数の比較手段を選択的に連結する連結手段と、
検索ごとに、前記複数の比較手段に判定式を設定するとともに、前記複数の比較手段が選択的に連結されるように前記連結手段を設定する設定手段を有することを特徴とする検索装置。
【請求項２】
請求項１において、複数の判定式と、それぞれが連結すべき比較手段を指定する複数の指定データを対応して記憶可能な記憶手段を有し、前記設定手段は、前記複数の判定式のそれぞれに対応して記憶されている指定データにより指定された複数の比較手段が連結されるように前記連結手段を設定し、前記複数の判定式のそれぞれに対応して記憶されている指定データにより指定された比較手段は、検索データが前記複数の判定式のそれぞれに適合するか判定することを特徴とする検索装置。
【請求項３】
請求項１において、前記設定手段は、連結された比較手段ごとにドントケアを設定することを特徴とする検索装置。
【請求項４】
請求項１において、前記設定手段は、判定式に応じて、２個ある全比較器の一方の出力を無効とすることを特徴とする検索装置。
【請求項５】
請求項１において、前記設定手段は、記憶手段に保持された情報をドントケア情報として機能させるか検索データとして機能させるか、判定式によって決定することを特徴とする検索装置。
【請求項６】
請求項１において、前記設定手段は、該比較手段に与える検索順序を、検索ごとに順序を入れ替え可能であることを特徴とする検索装置。
【請求項７】
請求項６において、前記設定手段は、検索履歴を参照して、検索順序を入れ替えることを特徴とする検索装置。
【請求項８】
検索データが適合する判定式を複数の比較手段を用いて検索する検索方法であって、
検索データが複数の判定式のそれぞれに適合するか順次判定する判定処理において、前記複数の判定式のそれぞれに対応する指定データにより指定される比較手段を連結し、検索データが前記複数の判定式のそれぞれに適合するか前記連結された比較手段を用いて判定することを特徴とする検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は検索装置または検索方法に関する。
【背景技術】
【０００２】
従来、高速な検索を実現するために、ＣＡＭ（内容参照可能メモリ又は連想メモリとも呼ばれる）を利用することが知られている。例えば、ルーターなどにおいては、ＴＣＰ／ＩＰ処理に使用されるＩＰアドレス検索を高速化するために、ＣＡＭが利用されている。しかしながら、範囲指定を含む検索処理においては従来型ＣＡＭでは行なえずソフトウエアによって逐次比較検索を行っている。例えば、ＩＰｓｅｃ（ＩＰ  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌ）において用いられるセキュリティ・ポリシー・データベース（ＳＰＤ）は、複数の要素と要素ごとに異なる検索条件で検索され、更に検索条件には範囲指定も含まれる。ＳＰＤは、セキュリティ・ポリシーを管理するデータベースであり、ＩＰｓｅｃでは、セキュリティ・ポリシーに従ってパケットを処理する。
【０００３】
このような検索は、ＤｏＳ攻撃等に対処するためのフィルタリング処理においても行なわれている。このような検索が行われるのは、ネットワークプロトコル処理に限らず、画像処理の分野でも行われる。
【０００４】
ＰＣ（パーソナル・コンピュータ）等高速なＣＰＵを保有する機器では、このような検索処理を行なっても、著しいパフォーマンス低下とはならない。しかしながら、安価なコンシューマ機器のように搭載するＣＰＵがＰＣのそれに比べて非力で、当該ＣＰＵが製品の主要機能を担っている場合は重負荷である検索処理を行なわせることはできない。また、特許文献１に開示されているようにマグニチュード比較器を用いて従来型ＣＡＭを拡張し、大小比較ができるようにした提案もある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−１２９２１８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献１に開示されている提案では前述の検索処理のように検索要素を組み換えることが出来ないという問題がある。さらには、特許文献１に開示されている提案では、検索条件（一致、不一致、範囲内、範囲外）の組み替えることも、複数の要素の組み合わせを同時に検索することも出来ない。
【０００７】
また、特許文献１で開示されたマグニチュード比較器は特殊なセルで構成されており、安価なコンシューマ機器に搭載するＬＳＩを開発する上で、半導体開発ベンダの選定や開発期間及びコスト面で不向きである。一般に流通している標準的なロジック・セルで構成可能な検索装置が望まれている。
【課題を解決するための手段】
【０００８】
上記課題を解決するため、本発明においては、それぞれが２個の全比較器を含む複数の比較手段と、前記複数の比較手段を選択的に連結する連結手段と、検索ごとに、前記複数の比較手段に判定式を設定するとともに、前記複数の比較手段が選択的に連結されるように前記連結手段を設定する設定手段を有することを特徴とする。
【発明の効果】
【０００９】
上記構成により、様々な検索処理を同一検索装置で行なうことが出来る。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施例に係る構成を示す図である。
【図２】本発明の一実施例に係るディスクリプタのデータ構造、登録／参照データ・バッファの構造、及び、検索データを示す図である。
【図３】本発明の一実施例に係るインターフェース部に内蔵するレジスタ・セットの構成を示す図である。
【図４】本発明の一実施例に係る検索ブロックを詳しく説明する図である。
【図５】本発明の一実施例に係る検索テーブルの構成及び１１５２ビット・ワードの内訳を示す図である。
【図６】本発明の一実施例に係るアプリケーションの設定表である。
【図７】本発明の一実施例に係る登録データの構成を示す図である。
【図８】本発明の一実施例に係る登録データの構成を示す図である。
【図９】本発明の一実施例に係る登録データの構成を示す図である。
【図１０】本発明の一実施例に係る検索キーとマスク情報の構成を示す図である。
【図１１】本発明の一実施例に係る比較器を詳しく説明する図である。
【図１２】本発明の一実施例に係る比較器コア部を詳しく説明する図である。
【図１３】本発明の一実施例に係る４ｂｉｔ全比較器１の真理値表である。
【図１４】本発明の一実施例に係る４ｂｉｔ全比較器２の真理値表である。
【図１５】本発明の一実施例に係る一致検索モードにおけるセレクタの真理値表である。
【図１６】本発明の一実施例に係る不一致検索モードにおけるセレクタの真理値表である。
【図１７】本発明の一実施例に係る範囲内検索モードにおけるセレクタの真理値表である。
【図１８】本発明の一実施例に係る範囲外検索モードにおけるセレクタの真理値表である。
【発明を実施するための形態】
【００１１】
図１は本発明を実施した検索装置（以降ＳＥと呼称する）１０１を示した概略図である。ＳＥ１０１は、種々のデータ処理に使用される。ＳＥ１０１は、主要機能である検索、登録、参照、削除などのコマンド処理を、図２（Ａ）乃至（Ｃ）に示すディスクリプタ６０１と付属する各種データ（７０１、８０１）を、外部メモリ１０７から読み出して実行する。この読み出しはインターフェース部１０２に内蔵されたＤＭＡＣ（ダイレクト・メモリ・アクセス・コントローラ）１０９によって行われる。
【００１２】
インターフェース部１０２はレジスタ・セット１０８を含む。レジスタ・セット１０８の詳細を図３に示す。レジスタ・セット１０８はディスクリプタ・アドレス・レジスタ５０１、ビットマップ・アドレス・レジスタ５０２及び検索結果アドレス・レジスタ５０３から構成されている。ＳＥ１０１に対するコマンドの伝達は、外部メモリ１０７に置いたディスクリプタ６０１の先頭アドレスをディスクリプタ・アドレス・レジスタ５０１に書き込むことで行われる。書き込まれたディスクリプタ６０１の先頭アドレスはインターフェース部１０２に内蔵されたＦＩＦＯ（ファースト・イン・ファースト・アウト・メモリ）１１０に一時的に格納される。ＳＥ１０１は、このＦＩＦＯ１１０からディスクリプタ６０１の先頭アドレスを取り出し、この先頭アドレスを手掛かりにディスクリプタ６０１と付属する各種データ（７０１、８０１）をＤＭＡＣ１０９によって外部メモリ１０７から読み出し、コマンドを実行する。
【００１３】
レジスタ・セット１０８内のレジスタの選択はＲＥＧ＿ＡＤＤＲ信号によって行なう。該レジスタへの書き込みデータはＷＲＩＴＥ＿ＤＡＴＡ信号で伝達され、ＷＲＩＴＥ＿ＲＥＧ信号でレジスタに書き込まれる。また、該レジスタからの読み出しデータはＲＥＧ＿ＡＤＤＲ信号とＲＥＡＤ＿ＲＥＧ信号で選択され、ＲＥＡＤ＿ＤＡＴＡ信号でＳＥ１０１の外部に伝達される。
【００１４】
ＤＭＡＣ１０９は、外部メモリ１０７のアドレスを選択するＤＭＡ＿ＡＤＤＲ信号のほか、ＤＭＡ＿ＲＥＱ信号とＤＭＡ＿ＲＤＹ信号を使ってＤＭＡ動作を制御する。ＤＭＡ動作中、読み書きされるデータはＤＭＡ＿ＷＲＩＴＥ＿ＤＡＴＡ信号やＤＭＡ＿ＲＥＡＤ＿ＤＡＴＡ信号によって伝達される。
【００１５】
本実施例においてＳＥ１０１は、検索を行なう機能を有する３２個の検索ブロック１乃至３２（１０３乃至１０５）を内蔵する。検索ブロック１乃至３２（１０３乃至１０５）の内部は共通で、その概略を図４に示す。各検索ブロックが内蔵するメモリ２０１は複数個のメモリから構成されているが、トータルビット幅は１１５２ビットである。よって、これら各検索ブロックが内蔵するメモリを全てあわせると１１５２ビット・ワード×１０２４アドレスのメモリとみなせる。このメモリのイメージを図５（Ａ）に示す。本説明では前述のアドレスをエントリ・アドレス１１０２、前述のメモリを検索テーブル１１０１と呼称する。１１５２ビット・ワードの内訳を図５（Ｂ）に示す。本実施例では、任意エントリ・アドレスの１１５２ビット・ワードは４ビットごとの９６個の領域から構成されている。ここで１１５２ビット・ワードのデータ１００１をエントリ登録データと呼称する。本実施例では、３２個の検索ブロックを設けたが、本発明は、検索手段を複数の検索ブロックに分割する形態には限らない。
【００１６】
本実施例において検索モードには、一致検索（検索モード＝００）と不一致検索（検索モード＝０１）があり、更に、範囲内検索（検索モード＝１０）と範囲外検索（検索モード＝１１）がある。一致検索（検索モード＝００）と不一致検索（検索モード＝０１）では、ビット単位の比較で一致・不一致を判定する。範囲内検索と範囲外検索では、１個の領域（４ビット）又は隣接した複数の領域を結合した連結領域ごとに、あらかじめ設定した上限値と下限値の範囲内にあるか、範囲外にあるかを判定する。つまり領域又は連結領域ごとにＭＯＤＥ［０：１９１］データ１００４によって検索モードが設定される。
【００１７】
また、隣接する領域どうしの結合はＬＩＮＫ［０：９５］データ１００５によって設定される。ここで、ＬＩＮＫ［０：９５］データ１００５で９６個の領域の連結状態を指定し、その値が１の場合は後段の領域との分離を、値が０の場合は後段の領域との連結を意味する。更に、ＤＩＳＡＢＬＥ［０：９５］データ１００６によって未使用領域を設定する。
【００１８】
ＣＯＮＴＡ１００２及びＣＯＮＴＢ１００３は検索モードによって働きが異なる。一致検索は標準的なターナリＣＡＭと同様な動作で、ＣＯＮＴＡ１００２に比較対象のデータを格納し、ＣＯＮＴＢ１００３にターナリＣＡＭで使用されるＤｏｎ’ｔ  Ｃａｒｅ（ドントケア）ビットを格納する。不一致検索では、ＣＯＮＴＡ１００２に比較対象のデータを格納し、ＣＯＮＴＢ１００３にＤｏｎ’ｔ  Ｃａｒｅビットを格納する。範囲内検索と範囲外検索においては、ＣＯＮＴＡ１００２に範囲の上限値、ＣＯＮＴＢ１００３に範囲の下限値をそれぞれ格納する。
【００１９】
次に、検索、登録、参照、削除などのコマンドの動作を説明する。本コマンド処理の説明をわかりやすくするため、ネットワーク通信処理で広く行われているパケット・フィルタリングを事例とする。パケット・フィルタリングはネットワーク回線から受信したパケットを、パケットや受信環境に含まれる情報を基に、パケットの取捨選択を行なう機能である。パケットや受信環境に含まれる情報は様々なものがある。しかしながら、ここでは、本事例では受信パケットの情報として発信元ＩＰアドレス、宛先ＩＰアドレス、プロトコルタイプ、上位プロトコルの宛先ポート番号を使い、受信環境の情報として受信したインターフェース番号を使う。本フィルタリングでは検索テーブル１１０１に登録された条件に一致したパケットを破棄し、それ以外を通過させるものとする。
【００２０】
本事例の受信環境は受信インターフェースを２つ持ち、そのインターフェース番号を１と２とする。また、パケット・フィルタリングの設定アプリケーションから図６に示す設定が行なわれた状況を想定する。本パケット・フィルタリングが機能するサーバーのＩＰアドレスを１７２．１０．１．１０とする。
【００２１】
図６の設定１は接続される全てのクライアントに対してＴｅｌｎｅｔ（ポート番号２３）の要求を排除している。設定２はＩＰアドレス１７２．１０．２．１００から１７２．１０．２．２００までのクライアントに対してインターフェース番号１を経由してのＦＴＰ（ポート番号２１）の要求を排除している。設定３はＩＰアドレス１７２．１０．１．２０以外のクライアントに対してポート番号９８００から９９００のサービスを排除している。図６に記載のＡＮＹとは何でもよいという意味である。設定２の発信元ＩＰアドレス項と設定３の宛先ポート番号項はいずれも範囲指定がされている。また、設定３の発信元ＩＰアドレス項は不一致かどうかを見ている。
【００２２】
登録コマンドの動作を説明する。登録コマンドを使って図６の内容を検索テーブル１１０１に設定する。始めに、図７に示すように、外部メモリ１０７に設定１に対応する登録データ１２０１を用意する。ここで、発信元ＩＰアドレス項とインターフェース番号項がＡＮＹ指定であるため、ＣＯＮＴＢの対応部分（１２０２、１２０３）にＤｏｎ’ｔ  Ｃａｒｅビットが設定されている。また、ＣＯＮＴＡの有効ビットが２４×４ビットであるため、未使用ビット（７２×４）に対応したＤＩＳＡＢＬＥの対応部分１２０４は全て１が設定される。
【００２３】
次に、外部メモリ１０７にディスクリプタ６０１を用意する。ディスクリプタ６０１の内容は以下の通りである。
【００２４】
コマンド・フィールド６０２に登録コマンド・コード（０ｘ００００＿０００１）を設定する。エントリ・アドレス・フィールド６０３には検索テーブル１１０１の未使用エントリ・アドレスを設定する。この事例では、検索テーブル１１０１が初期化直後で、検索テーブル１１０１が全て未使用であるので、エントリ・アドレス０（０ｘ００００＿００００）を設定することにする。データ・アドレス・フィールド６０４には先ほど用意した登録データ１２０１の先頭アドレスを設定する。ビットマップ・アドレス・フィールド６０５は登録コマンドでは使用しないのでゼロを設定する。終了ステータス・フィールド６０６にはゼロを設定する。このゼロ設定の意味は、ＳＥ１０１によってコマンド終了時にゼロ以外の値が終了ステータス・フィールド６０６に書き込まれ、ポーリングシステムによってコマンド終了を知るためである。
【００２５】
次に、用意したディスクリプタ６０１の先頭アドレスをディスクリプタ・アドレス・レジスタ５０１に書き込み、ＳＥ１０１に登録コマンドを通知する。
【００２６】
通知を受けたＳＥ１０１の内部動作を説明する。ＦＩＦＯ１１０に書き込まれたディスクリプタ６０１の先頭アドレスを読み出したインターフェース部１０２は内蔵するＤＭＡＣ１０９を起動して外部メモリ１０７に記されたディスクリプタ６０１をインターフェース部１０２内部のバッファに取り込む。コマンドを解析し、登録コマンドであると認識したインターフェース部１０２は再度ＤＭＡＣ１０９を起動して登録データを外部メモリ１０７から取り込む。取り込み先はエントリ・アドレス・フィールド６０３に記載された値をＣＯＮＴＥＮＴＳ＿ＡＤＤＲ［０：１０２３］信号として各検索ブロック１０３〜１０５のメモリ２０１に出力する。該当する検索ブロックのメモリ２０１（エントリ・アドレスが０）が選択され、ＤＭＡＣ１０９によって取り込まれた登録データはＷＲＩＴＥ＿ＣＯＮＴＥＮＴＳ信号によって伝達され、ＷＲＩＴＥ＿ＥＮＡＢＬＥ信号によってメモリ２０１に書き込まれる。
【００２７】
次に、図８に示すように、図６の設定２に対応する登録データ１３０１を外部メモリ１０７に用意する。ここで、発信元ＩＰアドレス項はＩＰアドレスが１７２．１０．２．１００から１７２．１０．２．２００までの範囲指定であるため、ＣＯＮＴＡの該当部分１３０２には１７２．１０．２．２００（０ｘａｃ０ａ０２ｃ８）の値が設定される。また、ＣＯＮＴＢの該当部分１３０３には１７２．１０．２．１００（０ｘａｃ０ａ０２６４）の値が設定される。更に範囲内検索とするために該当するＭＯＤＥの該当部分１３０４に範囲内検索のコード１０が設定される。この８つの領域を連結し他と独立させるため、ＬＩＮＫの該当部分１３０５に連結の区切りを示す値１を設定する。検索テーブル１１０１に書き込まれるエントリ・アドレスが１となる以外は前述の設定１と同様な動作となる。
【００２８】
次に、図９に示すように、図６の設定３に対応する登録データ１４０１を外部メモリ１０７に用意する。ここで、宛先ポート番号項が範囲指定であるため前述と同様に１４０３、１４０４、１４０６、１４０８の設定となる。また、発信元ＩＰアドレス項が不一致指定であるためＭＯＤＥの該当部分１４０５に不一致検索のコード０１が設定される。ＬＩＮＫの該当部分１４０７に連結の区切りを示す値１を設定する。検索テーブル１１０１に書き込まれるエントリ・アドレスが３となる以外は前述の設定１と同様な動作となる。
【００２９】
削除コマンドの動作を説明する。削除コマンドは、指定したエントリ・アドレスに記載の登録データを検索テーブル１１０１から削除する動作で、具体的には指定したエントリ・アドレスのＤＩＳＡＢＬＥ［０：９５］ビットを全て１とする動作である。この操作によって後述の検索コマンド処理において、当該エントリ・アドレスは検索対象から除外される。削除コマンド・コードは０ｘ００００＿０００２である。
【００３０】
参照コマンドの動作を説明する。参照コマンドは、指定したエントリ・アドレスの検索テーブル１１０１に記載の登録データを、ディスクリプタ６０１のデータ・アドレス・フィールドに記載されたアドレスを先頭とする登録／参照データ・バッファ７０１に転送する動作である。参照コマンドは登録データの参照のほか、検索対象外の領域つまりＤＩＳＡＢＬＥビットが１となっている領域を通常メモリと同様に使用することを意図して設けられたものである。すなわち、参照コマンドは、登録データと関連するデータ構造体のアドレスを格納したり、あるいは関連する情報を直接的に格納したりするために用いられる。参照コマンド・コードは０ｘ００００＿０００３である。
【００３１】
検索コマンドの動作を説明する。検索コマンドは、図２（Ｃ）に示すＫＥＹとＧＭＡＳＫの組み合わせデータである検索データ８０１の内容が、検索テーブル１１０１に登録された各エントリ・アドレスに記載の条件に適合するか否かを判定する処理である。ここでＫＥＹは検索キー、ＧＭＡＳＫはグローバル・マスクで図１０（Ａ）乃至（Ｂ）に具体的事例を示す。
【００３２】
インターフェース部１０２は受領したディスクリプタが検索コマンドと判断するとＤＭＡＣ１０９を起動して外部メモリ１０７に置かれた検索データ８０１を読み出す。ＤＭＡＣ１０９は、この検索データ８０１をＫＥＹ［０：３８３］信号とＧＭＡＳＫ［０：３８３］信号を介して各検索ブロック１０３乃至１０５の比較器２０２に伝達する。その後、インターフェース部１０２はＳＴＡＲＴ信号によって制御部１０６に検索開始を指示する。検索開始によって、制御部１０６は各検索ブロック１０３乃至１０５のメモリ２０１へＳ＿ＡＤＤＲ信号によってアドレスを出力する。このアドレスは、各検索ブロック１０３乃至１０５に設けられた、３２エントリ・アドレス分のメモリ２０１の０番地から３１番地まで、動作クロック毎に１づつ増分し出力される。このメモリ・アクセスにより検索テーブル１１０１に登録された全データが動作クロック毎に逐次読み出され、各検索ブロック１０３乃至１０５内の比較器２０２に伝達される。
【００３３】
図１１に比較器２０２の詳細を示す。比較器２０２は９６個の比較器コア部３０１乃至３０４から構成されている。各比較器コア部にはＣＯＮＴＡ、ＣＯＮＴＢ、ＫＥＹ、ＧＭＡＳＫの各信号がそれぞれ４ビット、ＭＯＤＥ信号が２ビット、ＬＩＮＫ信号が１ビット入力される。その他、各比較器コア部には前段の比較器コア部からのキャリー信号であるＬＧ１Ｏｎ、ＥＱ１Ｏｎ、ＳＭ１Ｏｎ、ＬＧ２Ｏｎ、ＥＱ２Ｏｎ、ＳＭ２Ｏｎ、ＡＦＯｎの各信号が入力される。ｎは０から９４までの整数である。ただし、初段の比較器コア部３０１のキャリー入力については初期値としてＬＧ１Ｉ０、ＳＭ１Ｉ０、ＬＧ２Ｉ０及びＳＭ２Ｉ０は値０、ＥＱ１Ｉ０、ＥＱ２Ｉ０及びＡＦＩ０は値１を与える。図１１の信号表記でＬＧ１Ｉ０のＩは入力を表し、ＬＧ１Ｏ０のＯは出力を表す。また、ＬＧ１Ｉ０、ＬＧ１Ｏ０の０は９６個ある比較器コア部の０番目という意味である。
【００３４】
次に、ｍ番目の比較器コア部３０３を例にその内部構成を図１２に示す。ここでｍは０から９５までの整数であり、以降の本文中においても同様とする。比較手段である比較器コア部３０３は、４ｂｉｔ全比較器１（４０１）、４ｂｉｔ全比較器２（４０２）、セレクタ４０３及びいくつかのロジック・ゲートから構成されている。比較器コア部３０３は、２個の全比較器４０１、４０２を有する。図１３に４ｂｉｔ全比較器１（４０１）の入出力信号に関する真理値表を示す。また、図１４に４ｂｉｔ全比較器２（４０２）の入出力信号に関する真理値表を示す。これらの４ｂｉｔ全比較器は一般的に知られている４ｂｉｔマグニチュード・コンパレータ（大小比較器）と同等な機能を有する。
【００３５】
セレクタ４０３にはＣＯＮＴＢ、ＭＯＤＥ、ＧＭＡＳＫ、ＬＩＮＫ、ＡＦの各信号の他、４ｂｉｔ全比較器１（４０１）及び４ｂｉｔ全比較器２（４０２）からそれぞれ出力されるキャリー信号であるＬＧ１、ＥＱ１、ＳＭ１、ＬＧ２、ＥＱ２、ＳＭ２が入力される。セレクタ４０３はＭＯＤＥ［２ｍ＋０：２ｍ＋１］信号（検索モード）によって動作を変える。検索モードは前述したように一致検索（検索モード＝００）、不一致検索（検索モード＝０１）、範囲内検索（検索モード＝１０）及び範囲外検索（検索モード＝１１）の４種類である。そこで、検索モード毎にセレクタ４０３の動作を説明する。
【００３６】
一致検索（検索モード＝００）では４ｂｉｔ全比較器２（４０２）の出力ＬＧ２、ＥＱ２、ＳＭ２は使用されない。一致検索ではＣＯＮＴＢ信号で伝達されるデータはターナリＣＡＭで使用されるＤｏｎ’ｔ  Ｃａｒｅ（ドントケア）ビットと同じ意味を持たせるため、以下のように構成している。すなわち、セレクタ４０３からＤＣ信号を値１で出力し、ＣＯＮＴＢ信号が４ｂｉｔ全比較器１（４０１）の入力信号ＣＡ［０］〜ＣＡ［３］及び入力信号Ｋ［０］〜Ｋ［３］のマスク信号となるように構成している。このＤＣ信号の扱いは不一致検索（検索モード＝０１）でも同様である。すなわち、セレクタ４０３は、検索モードに応じて、２個ある全比較器の一方の出力を無効とする。
【００３７】
以上述べた、一致検索（検索モード＝００）におけるセレクタ４０３の入出力の真理値表を図１５に示す。ここで、ＧＭＡＳＫ信号はＫＥＹ信号とペアで入力されるが、ＧＭＡＳＫ信号の意味はＫＥＹ信号のビット毎のマスク機能である。つまり、ＧＭＡＳＫ信号が値１であると、対応するＫＥＹ信号の値によらずに常に４ｂｉｔ全比較器１（４０１）の入力信号であるＫ信号は１となる。同時にもう一方のＣＡ信号も１となり、当該ビットはＤｏｎ’ｔ  Ｃａｒｅとなる。判定結果はＨｍ信号に出力されて値１は検索条件（判定式）に適合していることを表し、値０は検索条件との不一致を表す。尚、本文中、検索条件に適合していることをヒットしているあるいはヒットと表現する場合もある。
【００３８】
不一致検索（検索モード＝０１）におけるセレクタ４０３の入出力の真理値表を図１６に示す。不一致検索時の４ｂｉｔ全比較器１（４０１）や４ｂｉｔ全比較器２（４０２）の役割やＧＭＡＳＫ信号の働きは次に述べる点以外は一致検索（検索モード＝００）時と同様である。
【００３９】
ＡＦ信号は連結領域の最下位の比較器コア部から伝播して来るキャリー信号で、最下位ビット以降、検索条件との適合が続く間、値１を伝播する。つまりセレクタ４０３のＡＦＩｍ信号が１で且つ、４ｂｉｔ全比較器１（４０１）のキャリー信号が検索条件との適合を示すＥＱ１信号が０（不一致検索なので）の場合又はマスク信号であるＣＯＮＴＡ又はＧＭＡＳＫが全て１の場合、ＡＦＯｍ信号は値１となる。ただし、ＬＩＮＫ［ｍ］が１の場合、連結領域の境界であるので、ＡＦＯｍ信号は無条件に初期値の値１となる。なお、上述したように、ＡＦＩ０は値１である。
【００４０】
キャリー信号ＡＦは連結領域全てがマスク信号でマスクされていた場合、検索条件に適合すると判定させるために必要である。例えば連結領域でＧＭＡＳＫが全て１の場合、最上位の比較器コア部の４ｂｉｔ全比較器１（４０１）のキャリー信号出力のＥＱ１が値１となるため、このままでは不一致検索としては検索条件に適合しないと判断される。キャリー信号ＡＦは、この誤判定を防止する役割を持つ。
【００４１】
範囲内検索（検索モード＝１０）及び範囲外検索（検索モード＝１１）ではＣＯＮＴＢ信号に範囲の下限値の意味を持たせる。そのためセレクタ４０３はＤＣ信号に値０を出力し、一致検索（検索モード＝００）などでビット毎のマスクの意味を持たせていたＣＯＮＴＢ信号とＧＭＡＳＫ信号の機能を停止する。すなわち、外部メモリ（記憶手段）に保持されたＣＯＮＴＢ信号をドントケア情報として機能させるか検索データとして機能させるかを、検索時に比較器２０２に与えるＭＯＤＥ信号によって決定する。範囲内検索及び範囲外検索では、ＣＯＮＴＢ信号を、ＭＯＤＥ信号によって、検索データとして機能させる。範囲内検索（検索モード＝１０）及び範囲外検索（検索モード＝１１）では４ｂｉｔ全比較器１（４０１）において範囲の上限値と検索キーＫ［０：３］が比較され、４ｂｉｔ全比較器２（４０２）において範囲の下限値と検索キーＫ［０：３］が比較される。これらの比較結果であるキャリー信号ＬＧ１、ＥＱ１、ＳＭ１、ＬＧ２、ＥＱ２、ＳＭ２がセレクタ４０３に入力される。
【００４２】
ここで範囲内検索（検索モード＝１０）におけるセレクタ４０３の入出力信号の真理値表を図１７に示す。また、範囲外検索（検索モード＝１１）におけるセレクタ４０３の入出力信号の真理値表を図１８に示す。
【００４３】
真理値表に示すように範囲内検索（検索モード＝１０）及び範囲外検索（検索モード＝１１）では判定結果であるＨｍ信号は、比較器コア部に入力するＬＩＮＫ信号が値１、つまり当該比較器コア部が連結領域の境界である場合に出力される。このように、比較器コア部は、ＬＩＮＫ信号により選択的に連結される。ＬＩＮＫ信号の値は、連結すべき比較器コア部を指定する指定データである。ＬＩＮＫ信号の値は、検索ごとに設定される。
【００４４】
更に、比較器コア部に入力されるＬＩＮＫ信号が値１で、且つＧＭＡＳＫ信号が０ｘＦ値の場合、検索キーＫ［０：３］によらずセレクタ４０３はＨｍ信号に値１を出力し、検索条件に適合していることを示す。つまり連結領域単位で（連結された比較器コア部ごとに）マスクし、Ｄｏｎ’ｔ  Ｃａｒｅ（ドントケア）に設定することができる。
【００４５】
以上説明したように、本実施形態では、ＣＯＮＴＡ、ＣＯＮＴＢ、ＭＯＤＥ信号は、判定式であり、制御部１０６によりメモリ２０１から読出されて比較器コア部に設定される。比較器コア部は、セレクタ４０３により選択的に連結される。制御部１０６は、ＬＩＮＫ信号をメモリ２０１から読出してセレクタ４０３に設定する。セレクタ４０３は、ＬＩＮＫ信号に従って、比較器コア部を連結する。検索を行なう場合、その検索で使用される比較器コア部がＬＩＮＫ信号で指定され、ＬＩＮＫ信号に従って連結された比較器コア部がＣＯＮＴＡ、ＣＯＮＴＢ、ＭＯＤＥ信号により指定される判定式に検索データが適合するか判定する。
【００４６】
メモリ２０１は、複数の検索条件の判定式を記憶可能である。本実施形態での検索条件は、図６に示したとおりである。メモリ２０１に記憶される検索条件には、連結すべき比較器コア部を指定する指定データであるＬＩＮＫデータが含まれる。すなわち、検索条件は、判定式、及び、検索データが判定式に適合するか連結して判定する比較器コア部を指定する指定データであるＬＩＮＫデータが含まれる。メモリ２０１は、この検索条件を複数組記憶可能である。
【００４７】
検索データが適合する判定式を複数の比較器コア部を用いて検索する判定処理において、制御部１０６は、メモリ２０１に複数組記憶されている検索式とＬＩＮＫデータを１組ずつ読出す。そして、制御部１０６は、判定式を比較器コア部に順次設定するとともに、設定した判定式に対応するＬＩＮＫデータをセレクタ４０３に設定して、検索データが判定式に適合するか判定する比較器コア部を連結する。制御部１０６は、この設定をメモリに記憶されている検索式とＬＩＮＫデータのそれぞれについて、順次行なう。このようにして、比較器２０２は、検索ごとに異なる判定式に検索データが適合するか順次判定し、検索データが適合する判定式が検索される。
【００４８】
本実施形態では、ＳＴＡＲＴ信号によって検索が開始されてから３２クロックで検索が終了する。開始から終了までの間に、各比較器コア部３０１乃至３０４から出力された検索結果Ｈ０乃至Ｈ９５は対応するＬＩＮＫ信号とＤＩＳＡＢＬＥ信号によってマスクされてＨＩＴ［ｉ］信号に集約されて制御部１０６に入力される。つまり、３２クロックのクロックごとに検索ブロック１乃至３２（１０３乃至１０５）から出力されたＨＩＴ［０：３１］信号の値は、各エントリ・アドレス１１０２に対応した１０２４ビット（ＨＩＴ［０：３１］×３２）の検索結果となる。この検索結果を、以降、検索結果アドレス・ビットマップと呼称する。
【００４９】
制御部１０６では検索結果アドレス・ビットマップから検索条件に適合していることを示す値１の数をカウントし、検索終了を示すＤＯＮＥ信号とともに、その総和をＨＩＴ＿ＣＯＵＮＴ［０：９］信号でインターフェース部１０２に伝達する。一方、検索結果アドレス・ビットマップは出力されるたびにＲ＿ＢＴＭ［０：３１］信号でインターフェース部１０２に伝達する。検索結果アドレス・ビットマップはエントリ・アドレス順に並び替えるためにインターフェース部１０２に設けられたバッファに一時保持される。
【００５０】
インターフェース部１０２は、ＤＭＡＣ１０９を使って、ディスクリプタ６０１のビットマップ・アドレス・フィールド６０５に記載されたアドレスの格納バッファに、検索結果アドレス・ビットマップを転送する。この検索結果アドレス・ビットマップは、エントリ・アドレス順に並び替えられている。検索結果アドレス・ビットマップの格納バッファは外部メモリ１０７に用意されている。
【００５１】
インターフェース部１０２は、検索結果アドレス・ビットマップの転送終了後にディスクリプタ６０１の終了ステータス・フィールド６０６に書き込む。この書き込みでは、終了ステータス［１６：３１］を値１（正常終了を表す）とし、終了ステータス［０：９］をＨＩＴ＿ＣＯＵＮＴ［０：９］信号で得たカウント値（いわゆるマルチヒット数）とする。続いて、終了通知のための割り込み信号であるＩＮＴ信号をアサートする。この後、インターフェース部１０２は、ＦＩＦＯ１１０から次のアドレスを読み出す動作に入る。
【００５２】
ところで、前述のカウント値が１以上の場合、どのエントリ・アドレスの検索条件に適合しているかを知るため、本実施例では、インターフェース部１０２にアドレス変換器１１１を備えている。アドレス変換器１１１は、検索結果アドレス・ビットマップをヒット箇所に対応するエントリ・アドレス値に変換する。外部メモリ１０７に書き出された検索結果アドレス・ビットマップの先頭アドレスをビットマップ・アドレス・レジスタ５０２に書き込むと、アドレス変換器１１１は先頭アドレスを手掛かりに検索結果アドレス・ビットマップを読み出す。更に、ヒット箇所を調べ対応するエントリ・アドレス値に変換し、検索結果アドレス・レジスタ５０３に格納、表示する。アドレス変換器１１１は次候補のヒット箇所の探索をバックグラウンドで進めており、検索結果アドレス・レジスタ５０３からアドレス値が読み出されると、次候補のアドレスを検索結果アドレス・レジスタ５０３に格納、表示する。アドレス変換器１１１は次候補がなければ検索結果アドレス・レジスタ５０３に０ｘＦＦＦＦ＿ＦＦＦＦＦ値を表示し、ヒット箇所が無いことを示す。
【００５３】
なお、このアドレス変換器１１１は、検索結果アドレス・ビットマップから３２ビットづつデータを取り出し、下位ビット・アドレスから探索し、値１の箇所を発見すると（１）式に示す変換を行なう。ここで検索結果アドレス・ビットマップから３２ビットづつデータを取り出す回数をｒ、値１を発見した３２ビット中のビット・アドレスをＡとすると、求めるエントリ・アドレスＥＡは、
ＥＡ  ＝  Ａ＋３２（ｒ−１）      （１）
となる。
【００５４】
以上の実施例では比較器コア部３０１乃至３０４に４ビット構成の全比較器を使用していたが、ＳＥ１０１の用途によっては４ビット以外の構成の全比較器を使用してもよい。またメモリ２０１のアドレスサイズを３２としているが実装規模を縮小するため検索時間は長くなるが３２より大きなサイズを採用することも、逆に３２より小さなサイズを採用し検索時間を短縮することもできる。
【００５５】
以上述べたように、複数の検索要素が混在し且つ各検索要素のサイズや検索条件（検索モード）を様々に設定可能な、いわばプログラマブルなＳＥが実現できる。標準的なロジック・ゲートを使いＳＥが実現できる。
【００５６】
さて、本実施例では検索ブロック１乃至３２（１０３乃至１０５）に与える検索アドレスＳ＿ＡＤＤＲ［０：３１］信号は制御部１０６から出力されている。このとき、検索ブロック１乃至３２（１０３乃至１０５）に与えるアドレスは共通であった。しかしながら他の実施例では、検索履歴が残る、２回目以降の検索からは前回ヒットしたエントリ・アドレスを優先して検索するように、検索ブロックごとに、Ｓ＿ＡＤＤＲ［０：３１］信号に出力するアドレス順序を組み替える。すなわち、発行済みのエントリ・アドレスについてＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）テーブルを作り、検索がヒットするごとにＬＲＵテーブル内の優先順位の変更を行なう。このようにして、比較器２０２に与える検索順序を、検索ごとに順序を入れ替える。検索順序は、検索履歴を参照して決定する。これは、同一端末どうしで連続してパケットを送受信することが多いネットワーク処理などでは、ＬＲＵテーブルを使用したエントリ・アドレスの組み換えは、検索時間の短縮につながり、パフォーマンスの向上に役立つ。
【００５７】
以上のように、検索時に複数の要素の組み合わせを同時に検索することも、検索要素の組み換えや検索条件（一致、不一致、範囲内、範囲外）の組み替えもプログラマブルに行なうことも実現できる。これによって、様々な検索処理を同一検索装置で行なうことが出来、システムの性能向上と機能向上が期待される。
【００５８】
また、標準的なロジック・セルで構成可能な検索装置であるため搭載するＬＳＩを開発する上で、半導体開発ベンダの選定に自由度を持たせることも可能で、更に設計や検証といった開発期間及び半導体プロセスの簡素化でコスト面においても有利となる。
【００５９】
以上において、本発明が特定の実施例に関して図示され、かつ、説明されたが、さらに他の修正および改善が可能である。本発明は前述の実施例に示された特定の形式に限定されるものではなく、かつ添付の特許請求の範囲において本発明の精神および範囲から離れることのない全ての修正をカバーすることを考えていることが理解されるべきである。
【符号の説明】
【００６０】
１０１  ＳＥ
１０２  インターフェース部
１０３〜１０５  検索ブロック
１０６  制御部
１０７  外部メモリ
１０８  レジスタ・セット
１０９  ＤＭＡＣ
１１０  ＦＩＦＯ
１１１  アドレス変換器
【図１】
2010211388.tif 000003
【図２】
2010211388.tif 000004
【図３】
2010211388.tif 000005
【図４】
2010211388.tif 000006
【図５】
2010211388.tif 000007
【図６】
2010211388.tif 000008
【図７】
2010211388.tif 000009
【図８】
2010211388.tif 000010
【図９】
2010211388.tif 000011
【図１０】
2010211388.tif 000012
【図１１】
2010211388.tif 000013
【図１２】
2010211388.tif 000014
【図１３】
2010211388.tif 000015
【図１４】
2010211388.tif 000016
【図１５】
2010211388.tif 000017
【図１６】
2010211388.tif 000018
【図１７】
2010211388.tif 000019
【図１８】
2010211388.tif 000020