(57)【特許請求の範囲】
【請求項１】
予め指定されたキーワードを入力データ列から検索する半導体装置であって、
前記キーワードの先頭から予め定められたデータ数の部分に相当する部分キーワードを格納する第１の連想メモリと、
前記キーワードの全体を格納する第２の連想メモリと、
前記第１の連想メモリおよび前記第２の連想メモリに接続された制御回路と、
前記入力データ列を予め定められたデータ数ずつシフトして、前記第１の連想メモリでの検索対象となるデータとして出力するデータシフト部とを備え、
前記制御回路は、前記第１の連想メモリでの検索によって前記入力データ列内に前記部分キーワードと一致する部分が検出されると、当該検出された前記部分キーワードと一致する部分の位置情報に基づいて前記入力データ列から検索データを抽出し、前記第２の連想メモリへ入力し、
前記第１の連想メモリは、前記データシフト部がシフトするデータ数に応じて、互いに異なるオフセットを前記部分キーワードにそれぞれ付与した複数のエントリを格納する、半導体装置。
【請求項２】
前記第１の連想メモリは、そのメモリ容量が前記第２の連想メモリのメモリ容量より小さくなるように構成される、請求項１に記載の半導体装置。
【請求項３】
前記第２の連想メモリは、前記第１の連想メモリが前記部分キーワードと一致する部分を検出した場合に検索動作を実行する、請求項１に記載の半導体装置。
【請求項４】
前記部分キーワードと一致する部分の位置情報は、前記第１の連想メモリにおいて一致したエントリに対応するオフセットの情報を含む、請求項１に記載の半導体装置。
【請求項５】
前記第１の連想メモリは、複数のキーワードの各々について複数のエントリを格納しており、
前記部分キーワードと一致する部分の位置情報は、前記第１の連想メモリにおいて一致したエントリに対応するキーワードを特定する情報を含む、請求項１に記載の半導体装置。
【請求項６】
前記第２の連想メモリは、前記複数のキーワードの各々に加えて、各キーワードに付けて当該キーワードを特定する情報を格納しており、
前記第２の連想メモリは、前記部分キーワードと一致する部分の位置情報に含まれるキーワードを特定する情報に基づいて、格納している複数のキーワードのうち、検索に用いるキーワードを選択する、請求項５に記載の半導体装置。
【請求項７】
前記半導体装置は、複数の前記第１の連想メモリを備えており、
前記複数の第１の連想メモリは、同一の部分キーワードを共通に含んでおり、
前記データシフト部は、シフトごとに、当該シフトされた位置を基準として、互いに異なるオフセット位置が開始位置に設定された複数のデータを前記複数の第１の連想メモリへそれぞれ与える、請求項１に記載の半導体装置。
【請求項８】
前記第２の連想メモリは、前記第２の連想メモリに格納されているキーワードを、前記部分キーワードと一致する部分の位置情報に基づいてずらした上で、前記検索データと比較する、請求項１に記載の半導体装置。
【請求項９】
前記キーワードは、文字列であり、
前記データシフト部は、１つの文字を定義するのに必要なデータ数の整数倍に相当するデータ数ずつ、前記入力データ列をシフトする、請求項１に記載の半導体装置。
【請求項１０】
前記第１の連想メモリは、
前記入力データ列内の検索対象となるデータの第１の部分と、前記部分キーワードの前記第１の部分に対応する部分との一致を判定するとともに、
前記第１の部分が一致していると判定された場合に、前記検索対象となるデータの前記第１の部分とは異なる第２の部分と、前記部分キーワードの前記第２の部分に対応する部分との一致を判定する、請求項１に記載の半導体装置。
【請求項１１】
前記半導体装置は、複数の前記第１の連想メモリを備えており、
前記複数の第１の連想メモリには、同一の部分キーワードに異なるオフセットをそれぞれ付与した複数のエントリが分散して格納されており、
前記制御回路は、前記複数の第１の連想メモリの各々から出力される前記部分キーワードと一致する部分の位置情報に基づいて、前記検索データを前記入力データ列から抽出する、請求項１に記載の半導体装置。
【請求項１２】
前記半導体装置は、複数の前記第１の連想メモリを備えており、
前記複数の第１の連想メモリは、同一の部分キーワードを共通に含んでおり、
前記複数の第１の連想メモリには、前記入力データ列の互い異なる位置から開始するそれぞれのデータが検索対象として入力される、請求項１に記載の半導体装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予め指定されたキーワードを入力データ列から検索する半導体装置およびそれを含む情報処理システムに関する。
【背景技術】
【０００２】
情報通信技術の急速な進歩に伴って、データ内に含まれる特定のキーワードを高速に検索したいというニーズがますます増加している。例えば、セキュリティ分野では、ネットワークのワイヤスピードでの文字列抽出などが要求される。
【０００３】
ツリー検索またはバイトシフト検索といったアルゴリズムを用いるアプローチでは、このようなキーワード検索の高速化のニーズに対して、複数のチップを搭載する、あるいは、ＣＰＵ（Central Processing Unit）の高速化といった手法を用いて、要求されるニーズを実現するという方法が採用される。このようなソフトウェアによる実装形態に代えて、連想メモリ（Content Addressable Memory：以下「ＣＡＭ」とも称する。）を含む半導体装置による実装形態も提案されている。
【０００４】
例えば、特開２００５−０１８９４２号公報（特許文献１）は、制御部に与える負荷を低減することが可能な連想メモリ機能付き集積回路を開示する。このような集積回路を用いることで、より高速なキーワード検索を実現できる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−０１８９４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特開２００５−０１８９４２号公報（特許文献１）に開示される連想メモリ機能付き集積回路では、１バイトずつシフトさせて検索動作を実行する。このような構成において、検索スループットを向上させるための一つの手法として、シフトするバイト数を増加させるというアプローチがある。しかしながら、シフトするバイト数を増加させると、その増加させたバイト数に応じた連想メモリのメモリ容量が必要となる。連想メモリのメモリ容量増加に伴って、製作コストの増加に加えて、集積回路上の実装面積の増加および消費電力の増加といった課題も生じ得る。
【０００７】
すなわち、検索スループットと、製作コスト、実装面積、消費電力とはトレードオフの関係にある。そのため、連想メモリのメモリ容量の増加を抑制しつつ、より高速なキーワード検索が可能な回路構成が要望されている。
【０００８】
その他の課題と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【０００９】
ある実施の形態に従う半導体装置は、予め指定されたキーワードを入力データ列から検索するものであって、キーワードの先頭から予め定められたデータ数の部分に相当する部分キーワードを格納する第１の連想メモリと、キーワードの全体を格納する第２の連想メモリと、第１の連想メモリおよび第２の連想メモリに接続された制御回路とを含む。第１の連想メモリでの検索によって入力データ列内に部分キーワードと一致する部分が検出されると、入力データ列から抽出された検索データを第２の連想メモリが検索する。
【発明の効果】
【００１０】
ある実施の形態によれば、連想メモリのメモリ容量の増加を抑制しつつ、より高速なキーワード検索が可能な回路構成を実現できる。
【図面の簡単な説明】
【００１１】
【図１】本発明の関連技術に従う連想メモリ機能付き集積回路であるＣＡＭ内蔵集積回路の構成を示すブロック図である。
【図２】図１に示すＣＡＭ内蔵集積回路を用いたペイロードデータに対する検索動作を説明する模式図である。
【図３】図１に示すＣＡＭ内蔵集積回路を用いたペイロードデータに対する検索スループットを８倍にした場合の検索動作を説明する模式図である。
【図４】本実施の形態に従う半導体装置を含む情報処理システムの要部を機能的に示す模式図である。
【図５】実施の形態１に従う半導体装置の要部構成を示す模式図である。
【図６】図５に示す半導体装置を用いたペイロードデータに対する検索動作を説明する模式図である。
【図７】実施の形態２に従う半導体装置の要部構成を示す模式図である。
【図８】図７に示す半導体装置を用いたペイロードデータに対する検索動作を説明する模式図である。
【図９】実施の形態３に従う半導体装置の要部構成を示す模式図である。
【図１０】図９に示す半導体装置を用いたペイロードデータに対する検索動作を説明する模式図である。
【図１１】実施の形態４に従う半導体装置の要部構成を示す模式図である。
【図１２】図１１に示す半導体装置を用いたペイロードデータに対する検索動作を説明する模式図である。
【図１３】実施の形態５に従う半導体装置の要部構成を示す模式図である。
【図１４】図１３に示す半導体装置を用いたペイロードデータに対する検索動作を説明する模式図である。
【図１５】図１３に示す半導体装置を用いたペイロードデータに対する検索動作を説明するタイムチャートである。
【図１６】実施の形態６に従う半導体装置を用いたペイロードデータに対する検索動作を説明する模式図である。
【図１７】１バイトシフト検索が可能なオリジナルサーチＣＡＭを用いて４バイトシフト検索を実現するための構成例を示す模式図である。
【図１８】実施の形態７に従う半導体装置の構成を示す模式図である。
【図１９】実施の形態８に従う半導体装置の要部構成および検索動作を説明する模式図である。
【図２０】図５に示す実施の形態１に従う半導体装置において生じ得るマルチマッチを説明するための図である。
【図２１】実施の形態９に従う半導体装置の要部構成および検索動作を説明する模式図である。
【図２２】実施の形態１０に従う半導体装置の要部構成および検索動作を説明する模式図である。
【発明を実施するための形態】
【００１２】
本発明の実施の形態について、図面を参照しながら詳細に説明する。なお、図中の同一または相当部分については、同一符号を付してその説明は繰り返さない。
【００１３】
［Ａ．関連技術］
まず、本実施の形態に従う半導体装置の技術的意義をより明りょう化するために、特開２００５−０１８９４２号公報（特許文献１）に記載の連想メモリ機能付き集積回路での検索動作について説明する。
【００１４】
図１は、本発明の関連技術に従う連想メモリ機能付き集積回路であるＣＡＭ内蔵集積回路の構成を示すブロック図である。図１を参照して、ＣＡＭ内蔵集積回路９００は、ペイロードデータから指定された文字列を検索するシグネチャマッチング検索を実行する。具体的には、ＣＡＭ内蔵集積回路９００は、主たるコンポーネントとして、検索用ペイロードデータシフト部９０９と、オフセット情報出力部９２０と、検索用データ組合せ部９１５と、ＣＡＭアレイ９１１とを含む。
【００１５】
検索用ペイロードデータシフト部９０９は、各々が１バイトのラッチデータが格納可能なｎ個のラッチ部ＬＴ１〜ＬＴｎ（ｎ≧２）を有している。オフセット情報出力部９２０は、ペイロードデータ内の検索すべき文字列の開始位置の情報を格納する。ＣＡＭアレイ９１１は、ペイロードデータおよびヘッダ部から検索すべき文字列を格納する。
【００１６】
検索用ペイロードデータシフト部９０９は、ペイロードデータＤ１２を１バイト（１文字に相当）ずつシフトして、検索用ペイロードデータＰＤを出力する。検索用データ組合せ部９１５は、ヘッダデータＨＤと、シフトにより順次更新される検索用ペイロードデータＰＤとを結合して検索用データＤ１５を生成する。検索用データＤ１５は、ＣＡＭアレイ９１１の検索テーブルに予め格納されている検索すべき文字列であるエントリ値と比較される。検索用データＤ１５の検索用ペイロードデータＰＤがエントリ値と一致していると判定された場合には、オフセット情報出力部９２０は、検索用ペイロードデータＰＤの開始位置を示すオフセット（以下、「ｏｆｆｓｅｔ」とも記す。）情報を出力する。また、検索用データＤ１５の全体（ヘッダデータＨＤおよび検索用ペイロードデータＰＤ）がＣＡＭアレイ９１１に予め格納されているエントリ値と一致している場合には、一致（Ｈｉｔ）およびその一致したエントリのアドレス情報が出力される。
【００１７】
図２は、図１に示すＣＡＭ内蔵集積回路を用いたペイロードデータに対する検索動作を説明する模式図である。図２を参照して、ペイロードデータＤ１２「ＡＢｃｄＥｆＷａ…」は、検索用ペイロードデータシフト部９０９にて、最初の８文字「ＡＢｃｄＥｆＷａ」から１バイト（１文字に相当）（以下、「Ｂｙｔｅ」とも記す。）ずつシフトされる。各シフトされたペイロードデータＤ１２は、ＣＡＭアレイ９１１に予め格納されている検索すべき文字列であるエントリ値と比較される。図２には、ＣＡＭアレイ９１１のエントリＤＥｘのペイロード部に「Ｗａｒｎｉｎｇ！」という文字列が格納されている。すなわち、図２においては、文字列「Ｗａｒｎｉｎｇ！」が、ペイロードデータＤ１２のいずれの位置（オフセット情報）から開始されるかを検索する例を示す。
【００１８】
時間経過に伴って、ペイロードデータＤ１２から検索用ペイロードデータＰＤ０〜ＰＤ７が順次抽出される。すなわち、検索用ペイロードデータＰＤ０「ＡＢｃｄＥｆＷａ」（ｏｆｆｓｅｔ＝０の場合）、ＰＤ１「ＢｃｄＥｆＷａｒ」（ｏｆｆｓｅｔ＝１の場合）、ＰＤ２「ｃｄＥｆＷａｒｎ」（ｏｆｆｓｅｔ＝２の場合）…のように変化する。
【００１９】
このとき、ＣＡＭアレイ９１１のエントリＤＥｘに「ＸＸＸＸＸＸＸＸＷａｒｎｉｎｇ！」という文字列が格納されているとすると、ｏｆｆｓｅｔ＝６の場合、すなわち、検索用ペイロードデータＰＤ６＝「Ｗａｒｎｉｎｇ！」が検索用データ組合せ部９１５において結合され検索用データＤ１５「ＸＸＸＸＸＸＸＸＷａｒｎｉｎｇ！」と一致する。なお、ＣＡＭアレイ９１１のエントリＤＥｘのヘッダ部「ＸＸＸＸＸＸＸＸ」は、ヘッダデータＨＤと一致していると仮定している。
【００２０】
すると、ＣＡＭアレイ９１１は、結果（ｒｅｓｕｌｔ）として、一致（Ｈｉｔ）をプライオリティエンコーダ９１２へ出力する。プライオリティエンコーダ９１２は、一致（Ｈｉｔ）との結果を受けて、「Ｗａｒｎｉｎｇ！」が格納されているＣＡＭアレイ９１１のアドレス情報を出力する。併せて、プライオリティエンコーダ９１２は、「Ｗａｒｎｉｎｇ！」がペイロードデータＤ１２のいずれの位置から開始されるかを示すシフト値である、オフセット情報「ｏｆｆｓｅｔ＝６」を出力する。
【００２１】
図２に示す検索動作では、検索用ペイロードデータシフト部９０９がペイロードデータＤ１２を１バイトずつシフトすることで、検索用ペイロードデータＰＤを順次出力する構成について例示した。これに対して、検索スループットを向上させるために、ペイロードデータＤ１２をシフトするバイト数を増加させた場合について検討する。
【００２２】
図３は、図１に示すＣＡＭ内蔵集積回路を用いたペイロードデータに対する検索スループットを８倍にした場合の検索動作を説明する模式図である。図３に示す検索動作においては、ペイロードデータＤ１２のシフトバイト数を８バイトに増加させることで、検索スループットを８倍にしている。
【００２３】
図３を参照して、検索用ペイロードデータシフト部９０９は、ペイロードデータＤ１２を１６バイト分取り込み、８バイトずつシフトして、検索用ペイロードデータＰＤを出力する。検索用ペイロードデータＰＤから「Ｗａｒｎｉｎｇ！」という文字列を検索する場合、ＣＡＭアレイ９１１は、シフトされるバイトに応じた数のエントリを予め格納している。図３に示すＣＡＭアレイ９１１のエントリ内の「＊（アスタリスク）」は、検索動作において、比較対象のペイロードデータの値にかかわらず一致しているとみなす設定値（Ｄｏｎ’ｔ  ｃａｒｅ）を意味する。
【００２４】
図３に示す例では、検索用ペイロードデータＰＤ０「ＡＢｃｄＥｆＷａｒｎｉｎｇ！Ｏｐ」とＣＡＭアレイ９１１のエントリＤＥ０〜ＤＥ７の各々とが比較される。検索用ペイロードデータＰＤ０は、ＣＡＭアレイ９１１のエントリＤＥ６「＊＊＊＊＊＊Ｗａｒｎｉｎｇ！＊＊」と一致していると判定される。このように、１つの文字列を検索するために、８エントリが必要となる。
【００２５】
すなわち、図２に示す１バイトずつシフトする検索では、検索テーブルとしては、１エントリで済んでいたものが、図３に示す８バイトずつシフトする検索では、検索テーブルとして、８エントリが必要となる。すなわち、検索スループットを向上させるために、８バイトシフトに変更することで、１バイトシフトの場合に比較して、８倍のエントリすなわち、８倍のメモリ容量が必要となる。
【００２６】
以上検討したように、特開２００５−０１８９４２号公報（特許文献１）に記載の連想メモリ機能付き集積回路では、ペイロードデータを１バイトずつシフトしながら検索するため、システム全体の検索スループットの向上が難しい。一方で、検索スループットを向上させるために、ペイロードデータをシフトするバイト数を増加させると、シフトするバイト数に比例して検索すべき文字列を格納するメモリ容量が増加するため、実装面積および消費電力が増加するという課題が生じ得る。
【００２７】
そこで、本実施の形態に従う半導体装置および半導体装置を含む情報処理システムでは、検索スループットの向上と、製作コスト、実装面積、消費電力とのトレードオフの問題を解決し、メモリ容量の増加を抑制しつつ、検索スループットを向上できる回路構成を提供する。
【００２８】
［Ｂ．システム構成］
まず、本実施の形態に従う半導体装置を含む情報処理システムの全体構成について概略する。図４は、本実施の形態に従う半導体装置を含む情報処理システム２の要部を機能的に示す模式図である。
【００２９】
本実施の形態に従う情報処理システム２は、入力データ列からキーワードを検索する。入力データ列としては、情報処理システム２の応用先に応じて、任意のデータ列を対象とすることができる。情報処理システム２の応用先としては、ネットワーク検索エンジン、ネットワークセキュリティシステム、パケットデータ中のペイロードデータ内の特定パターン（例えば、ウイルスパターンまたはユーザ指定パターン）を検出するシステム、ビッグデータ内でいずれの位置にあるのか不明な特定パターンに合致するデータを検索するシステムなどが想定される。情報処理システム２がネットワーク上に配置される場合には、入力データ列としては、ネットワーク上を伝搬するパケットデータなどが想定される。
【００３０】
本明細書において、「キーワード」は、入力データ列から抽出されるべきデータを特定するための検索ルールを包含する。キーワードとしては、１または複数の特定データの集合（例えば、文字列またはデータパターン）であってもよいし、正規表現のようなマッチすべきデータの種類を特定するようなものであってもよい。典型的には、キーワードは、ユーザによって指定される文字列である。以下では、一般的な応用例として、入力データ列およびキーワードがいずれも文字列である場合について説明する。
【００３１】
図４には、情報処理システム２をネットワーク上に配置した構成を例示する。ユーザが、パーソナルコンピュータ５００を操作して所望のキーワードを入力すると、当該入力されたキーワードは情報処理システム２に登録される。そして、情報処理システム２は、ＬＡＮ（Local Area Network）などを介して接続されるインターネット６００から流入するパケットデータに対して、登録したキーワードを用いたキーワード検索を実行する。情報処理システム２は、キーワード検索によって得られた結果（例えば、キーワードとの一致の有無、キーワードと一致したパケットデータの情報、パケットデータ内の一致したキーワードの開始位置など）をパーソナルコンピュータ５００へ出力する。
【００３２】
図４を参照して、情報処理システム２は、主たるコンポーネントとして、半導体装置１と、上位コントローラ４とを含む。
【００３３】
半導体装置１は、上位コントローラ４からパケットデータおよびコマンドを受けて、上述したようなキーワード検索を実行し、その結果を上位コントローラ４へ出力する。より具体的には、半導体装置１は、コントローラ８と、ポジション検索エンジン１０と、ポジションサーチＣＡＭ２０と、オリジナルサーチＣＡＭ３０とを含む。
【００３４】
コントローラ８は、上位コントローラ４から受けたパケットデータおよびコマンドをポジション検索エンジン１０へ出力するとともに、ポジション検索エンジン１０から結果（キーワード情報、抽出キーワード、比較結果など）を受け付ける。コントローラ８は、ポジション検索エンジン１０からの結果を上位コントローラ４へ出力する。
【００３５】
本実施の形態に従う半導体装置１では、ポジションサーチＣＡＭ２０が、入力データ列に対して指定されたキーワードの一部を用いてポジションサーチ（部分検索）を実行するとともに、オリジナルサーチＣＡＭ３０が、ポジションサーチＣＡＭ２０でのポジションサーチの結果に基づいて、指定されたキーワード全体との一致を判定するオリジナルサーチ（全文検索）を実行する。ポジションサーチＣＡＭ２０は、入力されたキーワードの先頭から予め定められたデータ数の部分に相当する部分キーワードを格納する連想メモリである。オリジナルサーチＣＡＭ３０は、入力されたキーワードの全体を格納する連想メモリである。
【００３６】
このように、半導体装置１では、入力データ列に対して、部分検索であるポジションサーチと、全文検索であるオリジナルサーチとを組み合わせて実行することで、回路全体としてのメモリ容量を低減しつつ、より効率的な検索を実現する。
【００３７】
ポジション検索エンジン１０は、制御回路の一例であり、ポジションサーチＣＡＭ２０およびオリジナルサーチＣＡＭ３０に接続される。ポジション検索エンジン１０は、ポジションサーチに用いられるポジションサーチ検索データをポジションサーチＣＡＭ２０へ入力し、ポジションサーチＣＡＭ２０から比較結果（入力データ列内で部分キーワードが開始する位置など）を受け取る。そして、ポジション検索エンジン１０は、ポジションサーチＣＡＭ２０からの比較結果に基づいて、オリジナルサーチに用いられる検索データを抽出し、オリジナルサーチＣＡＭ３０へ入力する。最終的に、ポジション検索エンジン１０は、オリジナルサーチＣＡＭ３０から比較結果（入力データ列内でキーワードが開始する位置など）を受け取る。
【００３８】
このように、制御回路の一例であるポジション検索エンジン１０は、ポジションサーチＣＡＭ２０での検索によって入力データ列内に部分キーワードと一致する部分が検出されると、当該検出された部分キーワードと一致する部分の位置情報に基づいて入力データ列から検索データを抽出し、オリジナルサーチＣＡＭ３０へ入力する。
【００３９】
ポジションサーチＣＡＭ２０およびオリジナルサーチＣＡＭ３０には、「＊（アスタリスク）」（Ｄｏｎ’ｔ  ｃａｒｅ）を含むキーワードが登録されることもある。「＊」については、比較対象の値にかかわらず常に一致（Ｈｉｔ／マッチ）と判定される。そのため、ポジションサーチＣＡＭ２０およびオリジナルサーチＣＡＭ３０は、２値連想メモリ（Binary CAM）ではなく、３値連想メモリ（Ternary CAM）を採用することが好ましい。但し、「＊」をキーワードとして登録できさえすれば、どのようなタイプの連想メモリを採用してもよい。また、後述の実施の形態１０に従う半導体装置１については、キーワードに「＊」を含める必要はないので、２値連想メモリを用いて構成してもよい。
【００４０】
ポジション検索エンジン１０は、キーワードシフト・制御部１２と、ポジション検索部１４と、キーワード抽出・生成・制御部１６とを含む。キーワードシフト・制御部１２は、入力データ列を予め定められたデータ数ずつシフトして、ポジションサーチＣＡＭ２０での検索対象となるデータ（ポジション検索データ）として出力する。キーワードシフト・制御部１２は、ポジションサーチＣＡＭ２０に対するポジション検索データの入力、および、ポジションサーチＣＡＭ２０からの比較結果の受け取りなどを司る。
【００４１】
ポジション検索部１４は、ポジションサーチＣＡＭ２０からの比較結果に基づいて、入力データ列内のキーワードが現れる開始位置などを特定する。
【００４２】
キーワード抽出・生成・制御部１６は、ポジション検索部１４にて特定されたキーワードが現れる開始位置の情報などに基づいて、オリジナルサーチＣＡＭ３０へ入力する検索データを生成するとともに、オリジナルサーチＣＡＭ３０から比較結果を受け取る。
【００４３】
上位コントローラ４は、半導体装置１を含む情報処理システム２の全体を制御する。典型的には、上位コントローラ４は、外部からのキーワードの入力を受け付けるとともに、オリジナルサーチＣＡＭ３０での検索結果を外部へ出力する。
【００４４】
図４では、本実施の形態に従う情報処理システム２の主要なコンポーネントを機能的に示すものであり、実装形態について何ら限定するものではない。すなわち、ポジションサーチＣＡＭ２０およびオリジナルサーチＣＡＭ３０が連想メモリを用いて実現されている点を除いて、本発明を具現化する時代の技術に応じて、任意の実装技術を採用すればよい。また、いずれの部分を単一の集積回路（チップ）内に実装するのかといった点についても、任意に設計できる。
【００４５】
例えば、図４には、単一の半導体装置１上に、コントローラ８、ポジション検索エンジン１０、ポジションサーチＣＡＭ２０、およびオリジナルサーチＣＡＭ３０が実装されている例を模式的に示すが、これに限られず、一部のコンポーネントを別の集積回路上に形成してもよいし、逆に、さらに図示しない機能を盛り込むようにしてもよい。
【００４６】
また、上位コントローラ４およびコントローラ８などについては、集積回路ではなく、プロセッサがプログラムを実行することで、必要な機能を実現するようにしてもよい。例えば、上位コントローラ４としては、ＮＰＵ（Network Processing Unit）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field-Programmable Gate Array）などを用いて実装してもよい。
【００４７】
［Ｃ．実施の形態１］
次に、本発明の実施の形態１に従う半導体装置１について説明する。図５は、実施の形態１に従う半導体装置１の要部構成を示す模式図である。図６は、図５に示す半導体装置１を用いたペイロードデータに対する検索動作を説明する模式図である。
【００４８】
実施の形態１および他の実施の形態においては、入力データ列の一例としてペイロードデータを想定する。実施の形態１に従う半導体装置１は、ペイロードデータから、予め指定されたキーワードの一例として、指定された文字列（以下、「検索文字列」とも略称する。）を検索する。半導体装置１では、ペイロードデータに対して、部分検索であるポジションサーチと、全文検索であるオリジナルサーチとを実行することで、より少ないメモリ容量で、より効率的な検索を実現する。
【００４９】
より具体的には、図５を参照して、半導体装置１は、ポジションサーチ（部分検索）を実行するためのポジションサーチ部１００と、オリジナルサーチ（全文検索）を実行するためのオリジナルサーチ部２００とを含む。
【００５０】
ポジションサーチ部１００は、主たるコンポーネントとして、ペイロードデータシフト部１０２と、制御回路１０４と、ポジションサーチＣＡＭ２０とを含む。制御回路１０４は、検索データ情報抽出回路１０６と、検索データ生成回路１０８とを含む。オリジナルサーチ部２００は、主たるコンポーネントとして、オリジナルサーチＣＡＭ３０を含む。ポジションサーチＣＡＭ２０およびオリジナルサーチＣＡＭ３０は、汎用的なＣＡＭアレイ（検索メモリ）を用いて実現できる。
【００５１】
ポジションサーチ部１００は、入力されたペイロードデータから検索すべき文字列（検索文字列）の開始位置情報を検出し、検出した開始位置情報に基づいて、オリジナルサーチ部２００での全文検索の対象となる検索データを生成する。ポジションサーチＣＡＭ２０は、ポジションサーチ（部分検索）に必要な検索文字列の一部をエントリとして格納する。具体的には、ポジションサーチＣＡＭ２０は、検索文字列の先頭から予め定められたデータ数の部分に相当する検索文字列の一部を格納する。これに対して、オリジナルサーチＣＡＭ３０は、検索文字列の全体を格納する。
【００５２】
ペイロードデータシフト部１０２は、ペイロードデータを予め定められたデータ数（典型的には、所定バイト）ずつシフトして、ポジションサーチＣＡＭ２０での検索対象となるデータ（検索用ペイロードデータＰＤ）として出力する。すなわち、ペイロードデータシフト部１０２は、ペイロードデータの先頭から所定バイト数以降のデータを検索用ペイロードデータＰＤとして出力する。
【００５３】
なお、実施の形態１においては、キーワードとして検索文字列が用いられており、これに対応して、ペイロードデータシフト部１０２は、１つの文字を定義するのに必要なデータ数（１バイト＝８ｂｉｔ）の整数倍に相当するデータ数（例えば、４バイト）ずつ、ペイロードデータをシフトする。ペイロードデータをこのように決定することで、文字列に適合した形で、キーワードとの一致を判定できる。
【００５４】
ポジションサーチＣＡＭ２０は、ペイロードデータシフト部１０２で生成された検索用ペイロードデータＰＤと予め格納している検索文字列とを比較し、ペイロードデータ内の一致した検索文字列を出力する。併せて、ポジションサーチＣＡＭ２０は、検出された検索文字列の情報（ルール番号およびシフト値など）を出力する。制御回路１０４は、ポジションサーチＣＡＭ２０およびオリジナルサーチＣＡＭ３０に接続され、オリジナルサーチ部２００へ入力する検索データを生成する。制御回路１０４は、ポジションサーチＣＡＭ２０に格納されているいずれかのエントリが検索用ペイロードデータＰＤと一致した場合に動作する。検索データ情報抽出回路１０６は、ポジションサーチＣＡＭ２０にていずれかの検索文字列（エントリ値）が検出されたのか（ルール番号）、および、検索文字列が検出された検索用ペイロードデータＰＤが何バイトシフトされたものであるか（位置情報）といった情報を含む検索データ情報（キーワード情報）を抽出する。検索データ生成回路１０８は、検索データ情報およびペイロードデータから、オリジナルサーチ部２００へ与える検索データを生成する。
【００５５】
図６を参照して、図５に示す半導体装置１での検索動作について詳述する。図６に示す検索動作においては、ペイロードデータシフト部１０２でのペイロードデータのシフト量は４バイトとする。これに合わせて、ポジションサーチＣＡＭ２０に予め格納される検索ルール（ポジションルール）は、８バイトの文字列（エントリ値）から構成される。また、オリジナルサーチＣＡＭ３０に予め格納される検索ルール（オリジナルルール）は、６４バイトの文字列（エントリ値）から構成される。すなわち、図６に示す半導体装置１では、最大６４バイト長までの文字列検索が可能になっている。また、検索文字列が「Ｗａｒｎｉｎｇ！」である場合の検索動作の一例を示す。
【００５６】
ペイロードデータシフト部１０２は、ペイロードデータを所定バイト（図６の例では、４バイト）ずつシフトして、８バイトの検索用ペイロードデータＰＤを順次、ポジションサーチＣＡＭ２０へ出力する。図６に示す例では、検索用ペイロードデータＰＤ０「ＡＢｃｄＥｆＷａ」（シフト回数＝０の場合）、検索用ペイロードデータＰＤ１「ＥｆＷａｒｎｉｎ」（シフト回数＝１の場合）、検索用ペイロードデータＰＤ２「ｒｎｉｎｇ！Ｏｐ」（シフト回数＝２の場合）、…のように出力される。
【００５７】
ポジションサーチＣＡＭ２０は、複数の検索文字列の各々について複数のエントリを格納する。すなわち、ポジションサーチＣＡＭ２０は、ペイロードデータシフト部１０２がシフトするデータ数（シフトバイト数）に応じて、互いに異なるオフセットを検索文字列の一部にそれぞれ付与した複数のエントリを格納する。
【００５８】
図６に示す例では、ポジションサーチＣＡＭ２０は、ペイロードデータシフト部１０２での４バイトシフトに対応して、８バイト（すなわち、４バイトの２倍）の文字列（エントリ値）からなる検索ルール（ポジションルール）を格納する。より具体的には、ポジションサーチＣＡＭ２０は、エントリＰＤＥ０「Ｗａｒｎｉｎｇ！」、エントリＰＤＥ１「＊Ｗａｒｎｉｎｇ」、エントリＰＤＥ２「＊＊Ｗａｒｎｉｎ」、エントリＰＤＥ３「＊＊＊Ｗａｒｎｉ」のように、１バイトずつシフトした文字列を予め格納している。
【００５９】
すなわち、オリジナルサーチＣＡＭ３０の１エントリに対して、ペイロードデータシフト部１０２がペイロードデータをシフトするバイト数と同じ数のエントリが、ポジションサーチＣＡＭ２０に格納される検索ルールとして必要となる。例えば、ペイロードデータシフト部１０２が４バイトシフトを行なう場合には、ポジションサーチＣＡＭ２０には４エントリが必要となり、ペイロードデータシフト部１０２が８バイトシフトを行なう場合には、ポジションサーチＣＡＭ２０には８エントリが必要となる。
【００６０】
ポジションサーチＣＡＭ２０に格納されている検索ルールごとに、各エントリの位置と検索文字列の先頭位置とが対応付けて格納されている。すなわち、ポジションサーチＣＡＭ２０においてエントリが格納されているアドレスから、検索用ペイロードデータ内の検索文字列が存在する位置（シフト値）を容易に計算できるように、検索ルールは順序付けて格納されている。
【００６１】
図６に示すように、検索文字列の一部（予め定められた文字数以上）が一致すれば、Ｈｉｔと判定するようなあいまい検索を採用することが好ましい。図６に示すように、「Ｗａｒｎｉｎｇ！」という文字列を検索する場合には、５バイトの文字列「Ｗａｒｎｉ」から８バイトの文字列「Ｗａｒｎｉｎｇ！」のいずれであっても、一致（Ｈｉｔ）と判定されるようになっている。すなわち、図６に示す例では、検索文字列のうち５文字以上が一致すると、一致（Ｈｉｔ）と判定される。このようなあいまい検索を採用することで、連想メモリの使用率を抑制することができる。ペイロードデータシフト部１０２がＮバイトシフトを行ない、ポジションサーチＣＡＭ２０に格納される検索ルールの文字列の長さがＭバイトであるとすると、（Ｍ−Ｎ＋１）〜Ｍバイトのあいまい検索となる。
【００６２】
図６に示す例では、最初の検索用ペイロードデータＰＤ０「ＡＢｃｄＥｆＷａ」（シフト回数＝０の場合）に対しては、ポジションサーチＣＡＭ２０に格納されているいずれのエントリとも不一致（Ｍｉｓｓ）となる。次の検索用ペイロードデータＰＤ１「ＥｆＷａｒｎｉｎ」（シフト回数＝１の場合）に対しては、ポジションサーチＣＡＭ２０に格納されているエントリＰＤＥ２「＊＊Ｗａｒｎｉｎ」と一致する。ポジションサーチＣＡＭ２０は、エントリＰＤＥ２を示す一致アドレス（ＨｉｔＡｄｄ）として、「４ｎ＋２」を出力する。ここで、「ｎ」は１以上の整数である（以下同様）。
【００６３】
制御回路１０４は、ポジションサーチＣＡＭ２０での検索によってペイロードデータ内に検索文字列と一致する部分が検出されると、当該検出された検索文字列と一致する部分の位置情報に基づいてペイロードデータから検索データを抽出し、オリジナルサーチＣＡＭ３０へ入力する。より具体的には、制御回路１０４（検索データ情報抽出回路１０６）は、検索用ペイロードデータＰＤ１「ＥｆＷａｒｎｉｎ」に対応する検索用ペイロードデータＰＤ「ＥｆＷａｒｎｉｎ…」と一致アドレス「４ｎ＋２」とから、検索データ情報を抽出する。検索データ情報としては、ポジションサーチＣＡＭ２０において一致した検索ルールを示すルール番号「４ｎ」、ポジションサーチＣＡＭ２０において検索ルールが一致したときのオフセット情報であるシフト値「２」、および、ペイロード内の検索文字列の開始位置情報であるシフト回数「１」などを含む。検索データ情報抽出回路１０６は、一致アドレス「４ｎ＋２」を、ルール番号「４ｎ」と、シフト値（オフセット情報）「２」とに分離する。このように、検索文字列と一致する部分の位置情報である検索データ情報は、ポジションサーチＣＡＭ２０において一致したエントリに対応する検索文字列を特定する情報（ルール番号）およびそのオフセットの情報（シフト値）を含む。
【００６４】
制御回路１０４（検索データ生成回路１０８）は、検索データ情報に基づいて検索データを生成し、オリジナルサーチＣＡＭ３０へ与える。より具体的には、制御回路１０４は、ペイロードデータシフト部１０２が４バイトシフトを実行した回数「１」と、ポジションサーチＣＡＭ２０からのシフト値「２」とを抽出し、組み合わせることで、ペイロードデータ内の検索すべき文字列である「Ｗａｒｎｉｎｇ！」の開始位置情報を取得する。
【００６５】
検索データ生成回路１０８は、シフト回数「１」である場合のペイロードデータ＃１「ＥｆＷａｒｎｉｎｇ！ＯｐＱＣａｕｔｉｏｎ！ＶｗＸＹＺ…」を、検索データ情報抽出回路１０６にて計算されたシフト値「２」に応じて、２バイト左にシフトさせることで、シフト後検索データ（ＳＰＤ）を生成する。図６に示す例では、シフト後の検索データは、「Ｗａｒｎｉｎｇ！ＯｐＱＣａｕｔｉｏｎ！ＶｗＸＹＺ……」となる。
【００６６】
オリジナルサーチＣＡＭ３０は、各検索文字列について、その先頭から必要なバイト数分のデータを格納する。例えば、検索文字列が「Ｗａｒｎｉｎｇ！」である場合には、「Ｗａｒｎｉｎｇ！＊＊＊＊＊＊＊＊」がオリジナルサーチＣＡＭ３０のエントリＤＥ０として格納される。ここで、先頭から８バイト以降の文字列は任意の文字列でよいため、「＊（アスタリスク）」（Ｄｏｎ’ｔ  ｃａｒｅ）が指定される。「＊」が指定されている場所に対応する文字については、比較対象の値にかかわらず常に一致（Ｈｉｔ）と判定される。
【００６７】
図６に示す例では、オリジナルサーチＣＡＭ３０は、６４バイトの文字列（エントリ値）を格納できるように構成されているので、最大で６４バイトの文字（１文字が１バイトである場合）を指定できる。
【００６８】
オリジナルサーチＣＡＭ３０は、制御回路１０４（検索データ生成回路１０８）が生成したシフト後検索データ（ＳＰＤ）「Ｗａｒｎｉｎｇ！ＯｐＱＣａｕｔｉｏｎ！ＶｗＸＹＺ…」と、格納されている各検索ルールとの一致を判定する。図６に示す例では、シフト後検索データ（ＳＰＤ）「Ｗａｒｎｉｎｇ！ＯｐＱＣａｕｔｉｏｎ！ＶｗＸＹＺ…」がオリジナルサーチＣＡＭ３０のエントリＤＥ０「Ｗａｒｎｉｎｇ！＊＊＊＊＊＊＊＊」と一致するため、オリジナルサーチ部２００は、比較結果（ＨｉｔＩｎｄｅｘ）として、エントリＤＥ０「Ｗａｒｎｉｎｇ！＊＊＊＊＊＊＊＊」が格納されているアドレスおよび一致信号などを上位コントローラなどへ出力する。
【００６９】
以上説明したように、検索スループットを向上させるために、ペイロードデータシフト部１０２でのペイロードデータのシフトバイト数を増加させた場合であっても、ポジションサーチＣＡＭ２０では、ペイロードデータの先頭から所定バイト（例えば、８バイト）の文字列についてのみ部分検索すればよいので、メモリ容量の増加を抑制できる。さらに、ポジションサーチＣＡＭ２０でのポジションサーチ（部分検索）の結果を利用することで、ペイロードデータ内の検索文字列の開始位置を高速に取得できる。
【００７０】
また、オリジナルサーチＣＡＭ３０に格納される複数の検索ルール（オリジナルルール）の間で、ポジションサーチＣＡＭ２０に格納される対応する検索ルール（ポジションルール）が互いに同一であれば、ポジションサーチＣＡＭ２０に格納される検索テーブルのサイズをさらに低減できる。すなわち、オリジナルサーチＣＡＭ３０に新たな検索ルールを登録する場合に、対応するポジションルールと同一のポジションルールがポジションサーチＣＡＭ２０に既に登録されていれば、新たなポジションルールを追加する必要はない。これによって、検索エンジンに搭載するＣＡＭのメモリ容量を低減できるとともに、検索フローを低減できる。
【００７１】
実施の形態１に従う半導体装置１においては、ペイロードデータシフト部１０２がペイロードデータを４バイトずつシフトして検索動作を実行する。このような４バイトシフト検索を採用することで生じるメモリ容量の増加を抑制できる効果を、図１に示す関連技術に従うＣＡＭ内蔵集積回路と比較して説明する。
【００７２】
実施の形態１に従う半導体装置１において、ポジションサーチＣＡＭ２０を用いた４バイトシフト検索を採用することで、１バイトシフト検索に比較して、４倍の検索スループットを実現できる。検索スループットの向上に加えて、メモリ容量の削減も削減できる。
【００７３】
例えば、図１に示す関連技術に従うＣＡＭ内蔵集積回路において、１バイトシフト検索に必要なＣＡＭアレイのメモリ容量を２５６ｋｂｉｔ（＝６４バイト（検索文字列の最大長）×８×５１２エントリ）と仮定すると、４倍の検索スループットを実現するためには、この４倍のＣＡＭアレイが必要となるので、要求されるメモリ容量は１０２４ｋｂｉｔ（２５６ｋｂｉｔ×４）となる。
【００７４】
これに対して、実施の形態１に従う半導体装置１では、ポジションサーチＣＡＭ２０に必要なメモリ容量は、１２８ｋｂｉｔ（＝８バイト（部分検索に必要な検索文字列の長さ）×８×４バイトシフト×５１２エントリ）であり、オリジナルサーチＣＡＭ３０に必要なメモリ容量は、図１に示す関連技術に従うＣＡＭ内蔵集積回路のＣＡＭアレイのメモリ容量と同じく、２５６ｋｂｉｔである。よって、実施の形態１に従う半導体装置１の全体として必要なメモリ容量は、３８４ｋｂｉｔ（＝１２８ｋｂｉｔ＋２５６ｋｂｉｔ）となり、関連技術に従うＣＡＭ内蔵集積回路において４バイトシフトを実現する場合に比較して、３７．５％（＝３８４ｋｂｉｔ／１０２４ｋｂｉｔ）で済む。つまり、約６０％のメモリ容量の削減を実現できる。
【００７５】
すなわち、ポジションサーチＣＡＭ２０のメモリ容量は、オリジナルサーチＣＡＭ３０のメモリ容量より小さくなるように構成されれば、図１に示す関連技術に従うＣＡＭ内蔵集積回路において、複数バイトシフト検索を実行する場合に比較して、回路全体としてのメモリ容量を低減できる。
【００７６】
このメモリ容量の削減効果を一般化すると、以下のようになる。ペイロードデータのシフトバイト数をＳ、ポジションサーチＣＡＭ２０に格納される１エントリあたりのバイト数をＰ、オリジナルサーチＣＡＭ３０に格納される１エントリあたりのバイト数をＫ、オリジナルサーチＣＡＭ３０に格納されるエントリ数をＲとすると、メモリ容量は以下の数式で表わすことができる。
【００７７】
実施の形態１に従う半導体装置１のメモリ容量（ポジションサーチＣＡＭ２０＋オリジナルサーチＣＡＭ３０）＝（Ｐ×Ｒ×Ｓ）＋（Ｋ×Ｒ）…（１）
関連技術に従うＣＡＭ内蔵集積回路のメモリ容量（ＣＡＭアレイのメモリ容量）＝Ｋ×Ｒ×Ｓ…（２）
なお、検索スループットを同一にするため、関連技術に従うＣＡＭ内蔵集積回路のメモリ容量をＳ倍にして比較している。実施の形態１に従う半導体装置１のメモリ容量を関連技術に比較して削減するためには、以下の関係式が成立すればよい。
【００７８】
Ｐ＜（Ｓ−１）×Ｋ／Ｓ…（３）
例えば、シフトバイト数Ｓ＝４、オリジナルサーチＣＡＭ３０に格納される１エントリあたりのバイト数をＫ＝６４バイトとすると、ポジションサーチＣＡＭ２０に格納される１エントリあたりのバイト数Ｐは４８バイト未満であれば、面積および消費電流の低減効果がある。
【００７９】
また、シフトバイト数Ｓ＝１６、オリジナルサーチＣＡＭ３０に格納される１エントリあたりのバイト数をＫ＝６４バイトとすると、ポジションサーチＣＡＭ２０に格納される１エントリあたりのバイト数Ｐは６０バイト未満であれば、面積および消費電流の低減効果がある。
【００８０】
但し、関連技術に従うＣＡＭ内蔵集積回路では、シフトバイト数の数だけエントリが必要になるが、実施の形態１に従う半導体装置１では、同一のルール番号が付与されている検索ルールについては、ポジションサーチＣＡＭ２０に別のエントリとして登録する必要はないので、面積および消費電流をより低減できる効果がある。
【００８１】
実施の形態１に従う半導体装置１において、ポジションサーチＣＡＭ２０は完全に一致しているか否かを判定するのではなく、所定バイト数のあいまい検索（上述の説明では、５バイト〜８バイト：すなわち５バイト以上）を実行する。このようなあいまい検索を採用することで、一致検出率（ポジションサーチＣＡＭ２０において一致していると判定された文字列がオリジナルサーチＣＡＭ３０においても一致していると判定される確率）を高めつつ、ポジションサーチＣＡＭ２０に検索ルールとして格納される文字列（エントリ値）を短くすることができる。すなわち、検索文字列と一致する文字列を容易かつ高速に検索できるとともに、必要なメモリ容量を削減できる。
【００８２】
また、図１に示す関連技術に従うＣＡＭ内蔵集積回路では、動作サイクルごとに大容量のＣＡＭアレイ９１１を用いた検索動作が実行されるが、実施の形態１に従う半導体装置１では、大容量のオリジナルサーチＣＡＭ３０を用いたオリジナルサーチ（全文検索）は、小容量のポジションサーチＣＡＭ２０が一致を出力した場合のみ動作する。すなわち、オリジナルサーチＣＡＭ３０は、ポジションサーチＣＡＭ２０が検索文字列と一致する部分を検出した場合に検索動作を実行する。そのため、キーワード検索に要する消費電流を低減できる。
【００８３】
実施の形態１に従う半導体装置１は、長い検索文字列を用いた検索が要求される場合にも有効である。例えば、図３に示すような手法で検索スループットを向上させる場合、８バイトシフト検索を採用すると、１エントリが６４バイトの検索システムでは、エントリの文字列の長さにシフトバイト数を加えた７２バイト幅のＣＡＭアレイが必要となる。さらにシフトバイト数を増加させてキーワード検索を高速化する場合には、シフトバイト数に対応したビット幅のＣＡＭアレイが必要となる。
【００８４】
つまり、長い検索文字列を用いた検索を高速に実行する必要がある場合、図３に示すようなシフトバイト数を増加させるというアプローチでは、ハードウェア上の制約（典型的には、大きなビット幅のＣＡＭアレイを実現できない）により実装が難しい場合が想定される。これに対して、実施の形態１に従う半導体装置１においては、シフトバイト数の増加に伴って増加させなければならないのは、オリジナルサーチＣＡＭ３０のビット幅ではなく、ポジションサーチＣＡＭ２０のビット幅である。すなわち、オリジナルサーチＣＡＭ３０のビット幅は、要求される検索文字列の最大長さのみに依存して決定される。そのため、関連技術に従うＣＡＭ内蔵集積回路において生じ得るハードウェア上の制約を受ける可能性は低く、より容易に実装できる。
【００８５】
以上のとおり、実施の形態１に従う半導体装置１では、オリジナルサーチＣＡＭ３０と、オリジナルサーチＣＡＭ３０に比較してメモリ容量の小さいポジションサーチＣＡＭ２０とを組み合わせて採用することで、入力されるペイロードデータに対するシフトバイト数を増加させた場合であっても、必要なメモリ容量の増加を抑制することができる。これによって、関連技術に従うＣＡＭ内蔵集積回路と比較して、小容量および低消費電力を維持しつつ、高い検索スループットを実現できる。
【００８６】
高い検索スループットで検索文字列に対応する文字列の開始位置を取得できるため、例えば、ＨＴＴＰ（HyperText Transfer Protocol）ヘッダ内から特定のキーワード（検索文字列）を抽出するような検索エンジンなどに応用することで、ネットワークのワイヤスピードでの文字列抽出などを実現できる。
【００８７】
［Ｄ．実施の形態２］
上述の実施の形態１に従う半導体装置１では、ポジションサーチＣＡＭ２０を用いてポジションサーチ（部分検索）を実行するが、このポジションサーチ（部分検索）をより効率的に実現する構成について例示する。
【００８８】
図７は、実施の形態２に従う半導体装置１Ａの要部構成を示す模式図である。図８は、図７に示す半導体装置１Ａを用いたペイロードデータに対する検索動作を説明する模式図である。
【００８９】
実施の形態２に従う半導体装置１Ａは、図５に示す実施の形態１に従う半導体装置１において、ポジションサーチ部１００のポジションサーチＣＡＭ２０を、プリサーチ機能を有するポジションサーチＣＡＭ２０Ａに置換した構成に相当する。その他の構成については、図５に示す半導体装置１の対応する構成と同様であるので、詳細な説明は繰り返さない。
【００９０】
ポジションサーチＣＡＭ２０Ａは、入力された検索用ペイロードデータに対して複数段階で検索を実行するプリサーチ機能を有している。図７および図８に示す例では、ポジションサーチＣＡＭ２０Ａは、８バイトの検索用ペイロードデータを前半４バイトおよび後半４バイトに分割し、前半部分に対する検索（以下、「プリサーチ」または「ｐｒｅサーチ」とも称す。）と、後半部分に対する検索（以下、「ポストサーチ」または「ｐｏｓｔサーチ」とも称す。）とを実行する。ポストサーチについては、プリサーチの結果が一致（Ｈｉｔ）を示している場合のみ実行される。このような複数段階で検索を実行することで、回路全体としての低消費電力化を実現できる。
【００９１】
ポジションサーチＣＡＭ２０Ａは、ペイロードデータ内の検索対象となるデータの第１の部分と、検索文字列（の一部）の第１の部分に対応する部分（プリサーチ部）との一致を判定するとともに、第１の部分が一致していると判定された場合に、検索対象となるデータの第１の部分とは異なる第２の部分と、検索文字列（の一部）の第２の部分に対応する部分（ポストサーチ部）との一致を判定する。
【００９２】
図８を参照して、図７に示す半導体装置１Ａでの検索動作について詳述する。ポジションサーチＣＡＭ２０Ａの動作以外は、図６に示す実施の形態１に従う半導体装置１での検索動作と同様であるので、詳細な説明は繰り返さない。図６には、検索文字列が「Ｗａｒｎｉｎｇ！」である場合の検索動作の一例を示す。
【００９３】
ペイロードデータシフト部１０２は、ペイロードデータを所定バイト（図８の例では、４バイト）ずつシフトして、８バイトの検索用ペイロードデータＰＤを順次、ポジションサーチＣＡＭ２０Ａへ出力する。図８には、説明の便宜上、検索用ペイロードデータＰＤ０〜ＰＤ３を４バイトずつ前半部分と後半部分とに２分割しているが、ペイロードデータシフト部１０２の動作は実施の形態１に従う半導体装置１と同様である。
【００９４】
ポジションサーチＣＡＭ２０Ａは、ペイロードデータシフト部１０２から出力される８バイトの検索用ペイロードデータＰＤ０「ＡＢｃｄＥｆＷａ」（シフト回数＝０の場合）を、前半部分＃０「ＡＢｃｄ」と後半部分＃１「ＥｆＷａ」との４バイトずつに分割して検索を実行する。ポジションサーチＣＡＭ２０Ａには、上述の実施の形態１に従う半導体装置１と同様の検索ルール（ポジションルール）が格納される。但し、文字列（エントリ値）の各々は、プリサーチ部とポストサーチ部とに分割されている。
【００９５】
ポジションサーチＣＡＭ２０Ａは、まず、プリサーチとして、検索用ペイロードデータＰＤ０の前半部分＃０「ＡＢｃｄ」と、格納している各検索ルールのプリサーチ部とを比較する。図８に示す例では、最初の検索用ペイロードデータＰＤ０の前半部分＃０「ＡＢｃｄ」は、ポジションサーチＣＡＭ２０Ａに格納されているいずれのエントリ値のプリサーチ部とも不一致（Ｍｉｓｓ）となる。そのため、検索用ペイロードデータＰＤ０に対するポストサーチは実行されない。
【００９６】
ポジションサーチＣＡＭ２０Ａは、次に、４バイトシフトされた検索用ペイロードデータＰＤ１「ＥｆＷａｒｎｉｎ」に対する検索を実行する。検索用ペイロードデータＰＤ１の前半部分＃１「ＥｆＷａ」は、ポジションサーチＣＡＭ２０Ａに格納されているエントリＰＤＥ２のプリサーチ部「＊＊Ｗａ」と一致（Ｈｉｔ）するので、ポストサーチが実行される。すなわち、ポジションサーチＣＡＭ２０Ａは、ポストサーチとして、検索用ペイロードデータＰＤ１の後半部分＃２「ｒｎｉｎ」と、そのプリサーチ部が一致したエントリＰＤＥ２のポストサーチ部「ｒｎｉｎ」とを比較する。図８に示す例では、検索用ペイロードデータＰＤ１の後半部分＃２「ｒｎｉｎ」は、エントリＰＤＥ２のポストサーチ部「ｒｎｉｎ」と一致する。
【００９７】
プリサーチおよびポストサーチの両方が一致（Ｈｉｔ）と判定されると、ポジションサーチＣＡＭ２０Ａは、エントリＰＤＥ２を示す一致アドレス（ＨｉｔＡｄｄ）として、「４ｎ＋２」を出力する。実施の形態１に従う半導体装置１と同様に、検索データ情報抽出回路１０６は、一致アドレス「４ｎ＋２」を、ルール番号「４ｎ」と、シフト値（オフセット情報）「２」とに分離する。制御回路１０４（検索データ生成回路１０８）は、検索データ情報に基づいて検索データを生成し、オリジナルサーチＣＡＭ３０へ与える。
【００９８】
上述のように、実施の形態２に従う半導体装置１ＡのポジションサーチＣＡＭ２０Ａでは、プリサーチが不一致（Ｍｉｓｓ）と判定されると、ポストサーチは実行されない。すなわち、プリサーチにおいて一致（Ｈｉｔ）と判定されるまで、ポストサーチの実行が省略され、プリサーチが繰り返される。このように、不要なポストサーチの実行が抑制されるので、実施の形態１に従う半導体装置１に比較して、さらなる低消費電力化を実現できる。
【００９９】
［Ｅ．実施の形態３］
上述の実施の形態１に従う半導体装置１では、オリジナルサーチＣＡＭ３０を用いてオリジナルサーチ（全文検索）を実行するが、このオリジナルサーチ（全文検索）をより効率的に実現する構成について例示する。
【０１００】
図９は、実施の形態３に従う半導体装置１Ｂの要部構成を示す模式図である。図１０は、図９に示す半導体装置１Ｂを用いたペイロードデータに対する検索動作を説明する模式図である。
【０１０１】
実施の形態３に従う半導体装置１Ｂは、図５に示す実施の形態１に従う半導体装置１において、オリジナルサーチ部２００のオリジナルサーチＣＡＭ３０を、プリサーチ機能を有するオリジナルサーチＣＡＭ３０Ａに置換した構成に相当する。その他の構成については、図５に示す半導体装置１の対応する構成と同様であるので、詳細な説明は繰り返さない。
【０１０２】
オリジナルサーチＣＡＭ３０Ａは、入力された検索データに対して複数段階で検索を実行するプリサーチ機能を有している。図７および図８に示す例では、オリジナルサーチＣＡＭ３０Ａは、ポジションサーチ部１００（検索データ情報抽出回路１０６）から出力されるルール番号に対する検索（以下、「プリサーチ」または「ｐｒｅサーチ」とも称す。）と、ルール番号に対応する検索ルール（オリジナルルール）を用いた検索データに対する検索（以下、「ポストサーチ」または「ｐｏｓｔサーチ」とも称す。）とを実行する。すなわち、実施の形態２に従う半導体装置１Ｂのオリジナルサーチ部２００Ａにおいては、ポジションサーチＣＡＭ２０Ａにおいて一致したエントリＰＤＥ２を示す一致アドレス情報から抽出されルール番号を用いてプリサーチが実行される。ポストサーチでは、プリサーチにおいて一致したエントリについてのみ、オリジナルサーチ（全文検索）が実行される。
【０１０３】
図１０を参照して、図９に示す半導体装置１Ｂでの検索動作について詳述する。オリジナルサーチＣＡＭ３０Ａの動作以外は、図６に示す実施の形態１に従う半導体装置１での検索動作と同様であるので、詳細な説明は繰り返さない。図１０には、検索文字列が「Ｗａｒｎｉｎｇ！」である場合の検索動作の一例を示す。
【０１０４】
実施の形態３に従う半導体装置１Ｂでは、最大６４バイト長までの文字列検索が可能になっているとする。オリジナルサーチＣＡＭ３０Ａは、前記複数の検索文字列（検索ルール）の各々に加えて、各検索文字列に付けて当該検索文字列を特定する情報（ルール番号を示す情報）を格納している。より具体的には、オリジナルサーチＣＡＭ３０Ａは、各エントリあたり、検索文字列に対応する５１２ｂｉｔ（＝６４バイト）と、検索文字列のルール番号を示す９ｂｉｔとが格納されている。検索文字列を示す検索ルール（オリジナルルール）は、実施の形態１に従う半導体装置１と同様である。９ｂｉｔのデータは、オリジナルサーチＣＡＭ３０Ａでのプリサーチに用いられる検索ルールに相当する。以下の説明においては、各エントリのルール番号を示す９ｂｉｔのデータを「プリサーチ部」と称し、各エントリの検索文字列を示す検索ルール（オリジナルルール）を「ポストサーチ部」と称す。
【０１０５】
オリジナルサーチＣＡＭ３０Ａに格納されるエントリの数を５１２とすれば、オリジナルサーチＣＡＭ３０Ａは、（５１２＋９）ｂｉｔ×５１２エントリのアレイ構成を用いて実現できる。
【０１０６】
オリジナルサーチＣＡＭ３０Ａは、プリサーチにおいて、ポジションサーチＣＡＭ２０からの位置情報に含まれる検索文字列を特定する情報（ルール番号）に基づいて、格納している複数の検索文字列のうち、検索に用いる検索文字列を抽出する。より具体的には、オリジナルサーチＣＡＭ３０Ａは、ポジションサーチ部１００（検索データ情報抽出回路１０６）にて分離されたルール番号と、プリサーチ部に格納されている検索ルールとを比較する。図６に示す例では、検索データ情報抽出回路１０６にて分離されたルール番号「４ｎ」は、オリジナルサーチＣＡＭ３０ＡのエントリＤＥ０およびＤＥ１に対応付けられる検索ルール「４ｎ」と一致する。原則として、ポジションサーチ部１００でのポジションサーチ（部分検索）は、オリジナルサーチ（全文検索）に用いられる検索文字列の一部を用いて実行されるので、オリジナルサーチＣＡＭ３０Ａのプリサーチでは、何らかのエントリが一致することになる。
【０１０７】
続いて、オリジナルサーチＣＡＭ３０Ａは、ポストサーチとして、プリサーチで一致したエントリに対応するエントリを用いて、検索データに対するオリジナルサーチ（全文検索）を実行する。図６に示す例では、プリサーチにおいて検索ルール「４ｎ」と一致したエントリＤＥ０およびＤＥ１が、オリジナルサーチ（全文サーチ）の検索ルール（オリジナルルール）として用いられる。
【０１０８】
ポストサーチにおいて、オリジナルサーチＣＡＭ３０Ａは、制御回路１０４（検索データ生成回路１０８）が生成したシフト後検索データ（ＳＰＤ）「Ｗａｒｎｉｎｇ！ＯｐＱＣａｕｔｉｏｎ！ＶｗＸＹＺ…」と、エントリＤＥ０およびＤＥ１として格納されているそれぞれの検索ルールとの一致を判定する。図６に示す例では、シフト後検索データ（ＳＰＤ）「Ｗａｒｎｉｎｇ！ＯｐＱＣａｕｔｉｏｎ！ＶｗＸＹＺ…」がオリジナルサーチＣＡＭ３０ＡのエントリＤＥ０「Ｗａｒｎｉｎｇ！＊＊＊＊＊＊＊＊」と一致するため、オリジナルサーチ部２００Ａは、比較結果（ＨｉｔＩｎｄｅｘ）として、エントリＤＥ０「Ｗａｒｎｉｎｇ！＊＊＊＊＊＊＊＊」が格納されているアドレスおよび一致などを上位コントローラなどへ出力する。
【０１０９】
上述のように、実施の形態３に従う半導体装置１ＢのオリジナルサーチＣＡＭ３０Ａでは、ポジションサーチ部１００から出力される検索データ情報を用いてプリサーチを実行し、オリジナルサーチ（全文検索）の対象とする検索ルール（オリジナルルール）を絞り込む。そのため、不要なオリジナルサーチ（全文検索）の実行が抑制されるので、実施の形態１に従う半導体装置１に比較して、さらなる低消費電力化を実現できる。
【０１１０】
［Ｆ．実施の形態４］
上述の実施の形態２では、プリサーチ機能を有するポジションサーチＣＡＭ２０Ａを有する半導体装置１Ａについて説明し、実施の形態３においては、プリサーチ機能を有するオリジナルサーチＣＡＭ３０Ａを有する半導体装置１Ｂについて説明した。ポジションサーチＣＡＭ２０ＡおよびオリジナルサーチＣＡＭ３０Ａを組み合わせることで、さらに効率的な検索を実現できる。
【０１１１】
図１１は、実施の形態４に従う半導体装置１Ｃの要部構成を示す模式図である。図１２は、図１１に示す半導体装置１Ｃを用いたペイロードデータに対する検索動作を説明する模式図である。
【０１１２】
実施の形態４に従う半導体装置１Ｃは、図７に示す実施の形態２に従う半導体装置１Ａのポジションサーチ部１００Ａと、図９に示す実施の形態３に従う半導体装置１Ｂのオリジナルサーチ部２００Ａとを組み合わせた構成に相当する。ポジションサーチ部１００Ａおよびオリジナルサーチ部２００Ａの構成および動作については、それぞれ実施の形態２および実施の形態３において説明したので、ここでは詳細な説明は繰り返さない。また、その他の構成については、図５に示す半導体装置１の対応する構成と同様であるので、詳細な説明は繰り返さない。
【０１１３】
図１２には、実施の形態４に従う半導体装置１Ｃでの検索動作を示す。半導体装置１Ｃにおいて、ポジションサーチ部１００Ａでは、図８に示すようなプリサーチおよびポストサーチが実行され、オリジナルサーチ部２００Ａでは、図１０に示すようなプリサーチおよびポストサーチが実行される。
【０１１４】
ポジションサーチ部１００Ａ（ポジションサーチＣＡＭ２０Ａ）およびオリジナルサーチ部２００Ａ（オリジナルサーチＣＡＭ３０Ａ）がそれぞれプリサーチ機能を有することで、生じる、低消費電力の効果の一例について説明する。
【０１１５】
例えば、メモリ容量が２５６ｋｂｉｔ（＝６４バイト（検索文字列の最大長）×５１２エントリ）のオリジナルサーチＣＡＭ３０での検索動作に要する消費電流を１００ｍＡと仮定する。この場合、４バイトシフトに対応したポジションサーチＣＡＭ２０Ａでの検索動作に要する消費電流は５０ｍＡ（＝１００ｍＡ×（１２８ｋｂｉｔ／２５６ｋｂｉｔ）×１．０）と算出され、メモリ容量が２６０．５ｋｂｉｔ（＝（６４バイト＋９ｂｉｔ）×５１２エントリ）であるオリジナルサーチＣＡＭ３０Ａでの検索動作に要する消費電流は１０２ｍＡ（＝（２６０．５ｋｂｉｔ／２５６ｋｂｉｔ）×１００ｍＡ）と算出される。なお、ポジションサーチＣＡＭ２０Ａでの一致率（Ｈｉｔ率）を１００％としている。
【０１１６】
４バイトシフト検索を実行した場合、ポジションサーチＣＡＭ２０Ａでの一致率（Ｈｉｔ率）を１００％（ワースト条件）とすると、実施の形態１に従う半導体装置１においては、検索動作に４００ｍＡ（＝１００ｍＡ×４回）の消費電流を要するが、実施の形態４に従う半導体装置１Ｃにおいては、ポジションサーチＣＡＭ２０ＡおよびオリジナルサーチＣＡＭ３０Ａでの消費電流の合計は、１５２ｍＡ（＝５０ｍＡ＋１０２ｍＡ）となり、ワースト条件でも約６２％の消費電流を低減できることになる。
【０１１７】
このように、プリサーチ機能を有するポジションサーチＣＡＭ２０Ａおよび／またはプリサーチ機能を有するオリジナルサーチＣＡＭ３０Ａを採用することで、実施の形態１に従う半導体装置１に比較しても、さらなる低消費電力化を実現できる。
【０１１８】
実施の形態２〜４において説明したように、プリサーチ機能を有するポジションサーチＣＡＭ２０Ａおよび／またはオリジナルサーチＣＡＭ３０Ａを採用することで、プリサーチで不一致（Ｍｉｓｓ）と判定された場合には、後続のポストサーチを省略するため、低消費電力化を実現できる。
【０１１９】
［Ｇ．実施の形態５］
上述の実施の形態２および実施の形態４においては、プリサーチ機能を有するポジションサーチＣＡＭ２０Ａを採用した検索システムについて説明したが、実施の形態５では、ポジションサーチＣＡＭ２０Ａを複数搭載することで、検索スループットを向上させる構成について説明する。
【０１２０】
図１３は、実施の形態５に従う半導体装置１Ｄの要部構成を示す模式図である。図１４は、図１３に示す半導体装置１Ｄを用いたペイロードデータに対する検索動作を説明する模式図である。図１５は、図１３に示す半導体装置１Ｄを用いたペイロードデータに対する検索動作を説明するタイムチャートである。
【０１２１】
図１３を参照して、半導体装置１Ｄは、ポジションサーチ（部分検索）を実行するためのポジションサーチ部１００Ｂと、オリジナルサーチ（全文検索）を実行するためのオリジナルサーチ部２００Ａとを含む。
【０１２２】
オリジナルサーチ部２００Ａの構成および動作については、実施の形態４などにおいて説明したので、ここでは詳細な説明は繰り返さない。なお、オリジナルサーチ部２００Ａに代えて、上述の実施の形態１において説明したオリジナルサーチＣＡＭ３０を含むオリジナルサーチ部２００を採用してもよい。
【０１２３】
図１３には、４バイトシフト検索に対応する、プリサーチ機能を有する４個のポジションサーチＣＡＭ２０Ａ（＃０〜＃３）を用いて、１バイトシフト検索の場合に比較して１６倍（４×４＝１６バイトシフト検索に相当）まで検索スループットを向上させた構成例を示す。
【０１２４】
４個のポジションサーチＣＡＭ２０Ａ（＃０〜＃３）の各々は、互いに同一の検索ルール（検索文字列の一部／ポジションルール）を格納している。ペイロードデータシフト部１０２Ａは、ペイロードデータを所定バイト（図１３の例では、４バイト）ずつシフトして、検索用ペイロードデータＰＤとして４個のポジションサーチＣＡＭ２０Ａにそれぞれ出力する。４個のポジションサーチＣＡＭ２０Ａが検索文字列の開始位置情報の検索を並列して実行することで、ポジションサーチＣＡＭ２０Ａの並列数に応じた倍数まで、ポジションサーチ（部分検索）を高速化する。
【０１２５】
ペイロードデータシフト部１０２Ａは、シフトごとに、当該シフトされた位置を基準として、互いに異なるオフセット位置が開始位置に設定された複数の検索用ペイロードデータをポジションサーチＣＡＭ２０Ａ（＃０〜＃３）へそれぞれ与える。すなわち、ペイロードデータシフト部１０２Ａは、ペイロードデータから検索用ペイロードデータＰＤの抽出を開始する位置（位相／オフセット）をそれぞれのポジションサーチＣＡＭ２０Ａに応じて異ならせる。
【０１２６】
制御回路１０４Ａは、４個のポジションサーチＣＡＭ２０Ａからそれぞれ出力される一致アドレス（ＨｉｔＡｄｄ）を処理して、オリジナルサーチ部２００Ａでの全文検索の対象となる検索データを生成する。より具体的には、制御回路１０４Ａは、検索データ情報抽出回路１０６Ａと、検索データ生成回路１０８Ａとを含む。
【０１２７】
検索データ情報抽出回路１０６Ａの基本的な動作は、上述の実施の形態１に従う半導体装置１の検索データ情報抽出回路１０６と同様であるが、検索データ情報抽出回路１０６Ａは、一致アドレス（ＨｉｔＡｄｄ）の出力先のポジションサーチＣＡＭ２０Ａに応じて、シフト回数を算出する。
【０１２８】
検索データ生成回路１０８Ａの基本的な動作は、上述の実施の形態１に従う半導体装置１の検索データ生成回路１０８と同様であるが、２つ以上のポジションサーチＣＡＭ２０Ａから同時に一致アドレス（ＨｉｔＡｄｄ）が出力された場合には、検索データ（シフト後検索データ（ＳＰＤ））の生成および出力タイミングを調整する。
【０１２９】
図１４を参照して、図１３に示す半導体装置１Ｄでの検索動作について詳述する。図１４には、検索文字列が「Ｗａｒｎｉｎｇ！」である場合の検索動作の一例を示す。
【０１３０】
ペイロードデータシフト部１０２Ａは、ペイロードデータを所定バイト（図１４の例では、４バイト）ずつシフトして、８バイトの検索用ペイロードデータＰＤをそれぞれのポジションサーチＣＡＭ２０Ａへ出力する。図１４に示す例では、ペイロードデータシフト部１０２Ａは、４バイトずつシフトした各８バイトの検索用ペイロードデータＰＤ＃０「ＡＢｃｄＥｆＷａ」〜＃３「ｇ！ＯｐＱＣａｕ」をポジションサーチＣＡＭ＃０〜＃３へそれぞれ入力する。ポジションサーチＣＡＭ＃０〜＃３は、入力されたそれぞれの検索用ペイロードデータＰＤ＃０〜＃３に対して、予め格納しているエントリＰＤＥ０〜ＰＤＥ３（検索ルール）との一致を判定する。ポジションサーチＣＡＭ＃０〜＃３には、それぞれの検索用ペイロードデータＰＤが並列的に入力されるので、ポジションサーチＣＡＭ＃０〜＃３でのプリサーチは、同一サイクル内で実行される。
【０１３１】
ポジションサーチＣＡＭ＃０〜＃３の各々において、プリサーチおよびポストサーチは、同一周期内で並列的に実行可能である。そのため、ポジションサーチのプリサーチは、毎サイクル実行される。例えば、第２サイクルでは、ポジションサーチ１のポストサーチと同時に、ポジションサーチ２のプリサーチが実行され、第３サイクルでは、ポジションサーチ２のポストサーチと同時に、ポジションサーチ３のプリサーチが実行される。
【０１３２】
ポジションサーチ１では、ポジションサーチＣＡＭ＃０〜＃３がそれぞれプリサーチを実行した結果、ポジションサーチＣＡＭ＃１の検索用ペイロードデータＰＤ＃１「ＥｆＷａ」がポジションサーチＣＡＭ＃１に格納されているエントリＰＤＥ２のプリサーチ部「＊＊Ｗａ」と一致する。プリサーチの実行結果が一致（Ｈｉｔ）と判定されると、ポジションサーチＣＡＭ＃１は、ポジションサーチ１のポストサーチを実行する。プリサーチが不一致（Ｍｉｓｓ）と判定されたポジションサーチＣＡＭ＃０，＃２，＃３は、ポジションサーチ１のポストサーチを実行しない。
【０１３３】
ポジションサーチ１のポストサーチにおいて、検索用ペイロードデータＰＤ＃２「ｒｎｉｎ」は、ポジションサーチＣＡＭ＃１に格納されているエントリＰＤＥ２のポストサーチ部「ｒｎｉｎ」と一致する。そのため、ポジションサーチＣＡＭ＃１は、エントリＰＤＥ２を示す一致アドレス（ＨｉｔＡｄｄ）を出力する。すると、オリジナルサーチ部２００Ａにてオリジナルサーチ（全文検索）が実行される。
【０１３４】
次に、図１５を参照して、図１３に示す半導体装置１Ｄを用いたペイロードデータに対する検索動作について説明する。図１５には、プリサーチ機能を有する４個のポジションサーチＣＡＭ＃０〜＃３と、プリサーチ機能を有するオリジナルサーチＣＡＭ３０とを用いて、１６バイトシフト検索する場合のタイムチャートを示す。
【０１３５】
まず、時刻ｔ１において、ポジションサーチＣＡＭ＃０〜＃３は、それぞれプリサーチを実行する。続く時刻ｔ２において、ポジションサーチＣＡＭ＃０〜＃３は、時刻ｔ１で実行したプリサーチの判定結果を出力するとともに、時刻ｔ１でプリサーチの対象とした検索用ペイロードデータからそれぞれ４バイトシフトさせた新たな検索用ペイロードデータに対して、プリサーチを実行する。ポジションサーチＣＡＭ＃０〜＃３でのプリサーチは、毎時刻において実行される。
【０１３６】
時刻ｔ１〜ｔ２において実行されたプリサーチでは、ポジションサーチＣＡＭ＃０〜＃３のすべてにおいてプリサーチが不一致（Ｍｉｓｓ）となっている。すなわち、時刻ｔ１において実行されたプリサーチの結果が時刻ｔ２で出力され、図１５に示す例では、すべて不一致（Ｍｉｓｓ）であるため、ポジションサーチＣＡＭ＃０〜＃３でのポストサーチは実行されない。
【０１３７】
時刻ｔ２〜ｔ３において実行されたプリサーチでは、ポジションサーチＣＡＭ＃０のプリサーチが一致（Ｈｉｔ）となっており、ポジションサーチＣＡＭ＃０では、続いてポストサーチが実行される。時刻ｔ４〜ｔ５において実行されたポジションサーチＣＡＭ＃０のポストサーチは不一致（Ｍｉｓｓ）となっており、オリジナルサーチＣＡＭ３０でのオリジナルサーチ（全文検索）は実行されない。
【０１３８】
時刻ｔ３〜ｔ８には、ポジションサーチＣＡＭ＃１のプリサーチおよびポストサーチがいずれも一致（Ｈｉｔ）であるが、オリジナルサーチＣＡＭ３０のプリサーチが不一致（Ｍｉｓｓ）である例を示している。すなわち、時刻ｔ３〜ｔ４において実行されたプリサーチでは、ポジションサーチＣＡＭ＃１のプリサーチが一致（Ｈｉｔ）となっており、ポジションサーチＣＡＭ＃１では、続いてポストサーチが実行される。時刻ｔ５〜ｔ６において実行されたポジションサーチＣＡＭ＃１のポストサーチは一致（Ｈｉｔ）となっており、オリジナルサーチＣＡＭ３０にて検索データに対するオリジナルサーチ（全文検索）が実行される。時刻ｔ７〜ｔ８において実行されたオリジナルサーチのプリサーチは不一致（Ｍｉｓｓ）となっており、オリジナルサーチはこの時点で終了する。
【０１３９】
このように、ポジションサーチＣＡＭ＃０〜＃３のいずれかにおいて、プリサーチおよびポストサーチが一致（Ｈｉｔ）した場合のみ、オリジナルサーチ（全文検索）が実行される。
【０１４０】
時刻ｔ５〜ｔ１２には、ポジションサーチＣＡＭ＃３でのポジションサーチ（部分検索）、および、オリジナルサーチＣＡＭ３０のオリジナルサーチ（全文検索）がいずれも一致（Ｈｉｔ）である例を示している。すなわち、時刻ｔ５〜ｔ６において実行されたプリサーチでは、ポジションサーチＣＡＭ＃３のプリサーチが一致（Ｈｉｔ）となっており、ポジションサーチＣＡＭ＃３では、続いてポストサーチが実行される。時刻ｔ７〜ｔ８において実行されたポジションサーチＣＡＭ＃３のポストサーチは一致（Ｈｉｔ）となっており、オリジナルサーチＣＡＭ３０にて検索データに対するオリジナルサーチ（全文検索）が実行される。時刻ｔ９〜ｔ１０において実行されたオリジナルサーチのプリサーチは一致（Ｈｉｔ）となっており、続く時刻ｔ１１〜ｔ１２において実行されたオリジナルサーチのポストサーチについても一致（Ｈｉｔ）となっている。その結果、オリジナルサーチＣＡＭ３０は、比較結果（ＨｉｔＩｎｄｅｘ）として、一致したエントリが格納されているアドレスおよび一致（Ｈｉｔ）などを出力する。
【０１４１】
以上のように、入力されたペイロードデータから検索文字列と一致する文字列が検索されるまで、または、入力されたペイロードデータに対するすべての検索が完了するまで、図１５に示す検索動作が繰り返される。
【０１４２】
プリサーチ機能を有するポジションサーチＣＡＭ２０Ａを採用することで、ポジションサーチのプリサーチを毎時刻において実行することが可能になる。これによって、ネットワークのワイヤスピードでの文字列抽出などを実現できる。また、各時刻でのサーチ結果が一致（Ｈｉｔ）した場合のみ、次の検索を実行するため、無駄な電力を消費することを抑制でき、低消費電力化を実現できる。
【０１４３】
このように、オリジナルサーチＣＡＭ３０よりメモリ容量が少ない、４バイトシフト検索に対応したポジションサーチＣＡＭ２０Ａを４個用いることで、１バイトシフト検索に比較して、１６倍の検索スループットを実現できる。検索スループットの向上に加えて、メモリ容量も削減できる。
【０１４４】
例えば、図１に示す関連技術に従うＣＡＭ内蔵集積回路において、１バイトシフト検索に必要なＣＡＭアレイのメモリ容量を２５６ｋｂｉｔ（＝６４バイト（検索文字列の最大長）×８×５１２エントリ）と仮定すると、１６倍の検索スループットを実現するためには、この１６倍のＣＡＭアレイが必要となるので、要求されるメモリ容量は４０９６ｋｂｉｔ（２５６ｋｂｉｔ×４）となる。
【０１４５】
これに対して、実施の形態５に従う半導体装置１Ｄでは、４個のポジションサーチＣＡＭ２０と１個のオリジナルサーチＣＡＭ３０とが必要になる。４個のポジションサーチＣＡＭ２０に必要なメモリ容量は、５１２ｋｂｉｔ（＝１２８ｋｂｉｔ×４）であり、オリジナルサーチＣＡＭ３０に必要なメモリ容量は、実施の形態４に従う半導体装置１Ｃで説明したように、２６０．５ｋｂｉｔ（＝（６４バイト＋９ｂｉｔ）×５１２エントリ）である。すなわち、実施の形態５に従う半導体装置１Ｄを実現するのに必要なメモリ容量は、全体で７７２．５ｋｂｉｔ（＝５１２ｋｂｉｔ＋２６０．５ｋｂｉｔ）となり、関連技術に従うＣＡＭ内蔵集積回路において１６バイトシフトを実現する場合に比較して、１８．９％（＝７７２．５ｋｂｉｔ／４０９６ｋｂｉｔ）で済む。つまり、約８０％のメモリ容量の削減を実現できる。
【０１４６】
併せて、低消費電力化も実現できる。例えば、上述の実施の形態４と同様に、メモリ容量が２５６ｋｂｉｔのオリジナルサーチＣＡＭ３０での検索動作に要する消費電流を１００ｍＡと仮定する。ポジションサーチＣＡＭ２０Ａでの一致率（Ｈｉｔ率）を１００％（ワースト条件）とするとともに、オリジナルサーチＣＡＭ３０Ａでの一致率（Ｈｉｔ率）を１００％（ワースト条件）とすると、１６バイトシフト検索に要する消費電流は２４２ｍＡ（＝３５ｍＡ×４＋１０２ｍＡ）と算出される。図１に示す関連技術に従うＣＡＭ内蔵集積回路において、オリジナルサーチＣＡＭを１６個用いて１６バイトシフト検索を実現する場合の消費電流が１６００ｍＡ（１００ｍＡ×１６）であるので、実施の形態５に従う半導体装置１Ｄでは、ワースト条件でも約８５％の消費電流を低減できることになる。
【０１４７】
［Ｈ．実施の形態６］
上述の実施の形態１に従う半導体装置１は、ポジションサーチＣＡＭ２０にて検出された検索文字列の情報に基づいて、オリジナルサーチＣＡＭ３０での検索に用いられるシフト後検索データ（ＳＰＤ）を生成する。これに対して、実施の形態６においては、オリジナルサーチＣＡＭ３０に格納される検索ルールを適合させる構成について説明する。
【０１４８】
図１６は、実施の形態６に従う半導体装置１Ｅを用いたペイロードデータに対する検索動作を説明する模式図である。図１６に示す半導体装置１Ｅは、制御回路１０４Ｂ（検索データ生成回路１０８Ｂ）およびオリジナルサーチＣＡＭ３０Ｂでの処理が図６に示す実施の形態１に従う半導体装置１とは異なっている。その他の構成および動作については、実施の形態１と同様であるので、詳細な説明は繰り返さない。
【０１４９】
制御回路１０４Ｂの検索データ生成回路１０８Ｂは、ペイロードデータシフト部１０２からのシフト回数の情報に基づいて、ペイロードデータから検索データを生成する。このとき、検索データ生成回路１０８Ｂは、生成した検索データをさらにシフトすることなく、そのままオリジナルサーチＣＡＭ３０Ｂへ入力する。
【０１５０】
オリジナルサーチＣＡＭ３０Ｂは、制御回路１０４にて算出されたシフト値に基づいて、予め格納している検索ルール（オリジナルルール）をシフトさせてシフト後検索ルールを生成する。そして、オリジナルサーチＣＡＭ３０Ｂは、検索データとシフト後検索ルールとを比較することで、一致を判定する。このような構成を採用することで、制御回路１０４での検索データの抽出処理を簡素化できる。
【０１５１】
以上のように、検索文字列の開始位置に合わせて、検索データとオリジナルサーチＣＡＭ３０に格納されている検索ルールとを比較できれば、どのような形で実装してもよい。
【０１５２】
［Ｉ．実施の形態７］
次に、本発明の実施の形態に従う検索システムの実装について説明する。
【０１５３】
図１７は、１バイトシフト検索が可能なオリジナルサーチＣＡＭを用いて４バイトシフト検索を実現するための構成例を示す模式図である。図１７を参照して、関連技術に従う検索システム９５０は、典型的には、ネットワーク検索エンジン、または、ネットワークセキュリティシステムに応用可能である。より具体的には、検索システム９５０は、上位コントローラであるＮＰＵ９２０と、４個のオリジナルサーチＣＡＭ９６０−１〜９６０−４とを含む。オリジナルサーチＣＡＭ９６０−１〜９６０−４の各々のメモリ容量は、１０Ｍｂｉｔであるとする。オリジナルサーチＣＡＭ９６０−１〜９６０−４の各々は、１バイトシフト検索が可能に構成されており、ＮＰＵ９２０が検索対象のペイロードデータ（典型的には、パケットデータ）を１バイトずつシフトさせて、オリジナルサーチＣＡＭ９６０−１〜９６０−４のそれぞれへ入力することで、４バイトシフト検索を実現する。
【０１５４】
図１７に示すように、関連技術に従う検索システム９５０では、４倍の検索スループットを実現するために、大容量（例えば、１０Ｍｂｉｔ）のオリジナルサーチＣＡＭ９６０を４個必要とする。そのため、検索システム９５０を実現するための実装面積が大きくなり過ぎて、実現することが難しい場合がある。
【０１５５】
図１８は、実施の形態７に従う半導体装置１Ｆの構成を示す模式図である。図１８に示す半導体装置１Ｆでは、上位コントローラであるＮＰＵ４０と、ポジションサーチ部１００Ｅと、オリジナルサーチＣＡＭ３０とを含む。これらのコンポーネントは、単一基板上に実装することが可能である。
【０１５６】
ＮＰＵ４０は、図示しないネットワーク上を流れるパケットデータを取得し、その中に含まれるペイロードデータおよびＨＴＴＰヘッダデータを抽出し、検索対象データとしてポジションサーチ部１００Ｅへ出力する。ポジションサーチ部１００Ｅは、入力されたペイロードデータ内から予め格納されている検索文字列（エントリ値）と一致する文字列の開始位置を検索する。ポジションサーチ部１００Ｅは、検索により取得された検索データ情報（ルール番号およびシフト値など）および生成された検索データをオリジナルサーチＣＡＭ３０へ出力する。オリジナルサーチＣＡＭ３０は、ポジションサーチ部１００Ｅから入力された検索データに対して、オリジナルサーチ（全文検索）を実行し、その比較結果をＮＰＵ４０へ出力する。
【０１５７】
ポジションサーチ部１００Ｅは、ペイロードデータシフト部１０２Ｅと、４個のポジションサーチＣＡＭ２０と、制御回路１０４Ｅとを含む。ペイロードデータシフト部１０２Ｅは、入力されたペイロードデータを４バイトずつシフトさせて検索用ペイロードデータＰＤを順次出力する。ペイロードデータシフト部１０２Ｅは、ＨＴＴＰヘッダデータに含まれる識別子に対応するペイロードデータのみを処理するようにしてもよい。
【０１５８】
ポジションサーチ部１００Ｅでは、４個のポジションサーチＣＡＭ２０を採用することで、４バイトシフト検索を実現する。制御回路１０４Ｅは、それぞれのポジションサーチＣＡＭ２０から出力される検索結果に基づいて、検索データ情報（ルール番号およびシフト値など）を取得するとともに、検索データを生成する。
【０１５９】
図１８に示すように、オリジナルサーチＣＡＭ３０に比較してメモリ容量が少なく、かつ、検索文字列の開始位置を高速に検索できる、ポジションサーチＣＡＭ２０を採用することで、４バイトシフト検索を実現するために必要なメモリ容量を低減しつつ、低消費電力化も実現できる。これにより、従来の構成と同等またはそれ以上の検索スループットを実現するネットワーク検索エンジンおよびネットワークセキュリティシステムを提供できる。すなわち、要求されるネットワークのワイヤスピードでの文字列抽出などを実現できる。
【０１６０】
また、図１７に示す構成例においては、４個のオリジナルサーチＣＡＭ９６０−１〜９６０−４を実装するが、実施の形態７に従う半導体装置１Ｆでは、オリジナルサーチＣＡＭ９６０に比較して実装面積の小さなポジションサーチＣＡＭ２０を４個搭載する。そのため、半導体装置１Ｆのコンポーネントとしては、ＮＰＵ４０に加えて、ポジションサーチ部１００ＥとオリジナルサーチＣＡＭ３０との２個で済み、半導体装置１Ｆの実装面積を削減できる。
【０１６１】
［Ｊ．実施の形態８］
実施の形態７においては、ネットワーク検索エンジンまたはネットワークセキュリティシステムを実現可能な半導体装置１Ｆについて説明した。実施の形態８においては、ＨＴＴＰヘッダデータ内から予め指定された検索文字列の開始位置を再帰的な検索手法により検索し、検索により取得された検索データ情報（ルール番号およびシフト値など）および生成された検索データをオリジナルサーチＣＡＭ３０へ出力する構成について説明する。
【０１６２】
図１９は、実施の形態８に従う半導体装置１Ｇの要部構成および検索動作を説明する模式図である。図１９を参照して、実施の形態８に従う半導体装置１Ｇは、主たるコンポーネントとして、ポジションサーチＣＡＭ２０およびポジション検索エンジン１０を含む。ポジション検索エンジン１０は、典型的には、ロジック回路として実装されてもよい。ポジションサーチＣＡＭ２０は、比較対象の値にかかわらず一致しているとみなす設定（Ｄｏｎ’ｔ  ｃａｒｅ）が可能なＴＣＡＭ（Ternary CAM）アレイを用いることが好ましい。
【０１６３】
実施の形態８に従う半導体装置１Ｇにおいては、ＨＴＴＰヘッダデータ内に含まれ得る特定のヘッダ部およびフッタ部がそれぞれ抽出すべきキーワード（検索文字列）として指定される。例えば、特定のヘッダ部として、アドレスルールの第１番目にある「ＧＥＴ  ／」（ルール０）が登録され、特定のフッタ部として、アドレスルールの第１番目にある「￥ｒ￥ｎ」（ルール１）が登録される。抽出対象の文字列の開始部分と終了部分とが対応付けて検索ルールとして登録される。
【０１６４】
半導体装置１Ｇにおいては、バイトシフト検索を実行するため、ポジションサーチＣＡＭ２０には、各アドレスルールについて、１バイトずつシフトした４エントリ分が格納されている。
【０１６５】
ポジション検索エンジン１０は、上述のペイロードデータシフト部１０２と同様に、ＨＴＴＰヘッダデータを４バイトずつシフトさせてポジションサーチＣＡＭ２０へそれぞれ入力する。ポジションサーチＣＡＭ２０は、入力されたＨＴＴＰヘッダデータに対してポジションサーチ（部分検索）を実行し、その結果をポジション検索エンジン１０へ出力する。ポジション検索エンジン１０は、ポジションサーチＣＡＭ２０からの検索結果に基づいて、ＨＴＴＰヘッダデータからキーワード（検索文字列）を抽出する。ポジション検索エンジン１０は、ＨＴＴＰヘッダデータ内の検索文字列の開始位置情報（シフト回数）、および、ポジションサーチＣＡＭ２０において検出された検索文字列の検索データ情報（ルール番号およびシフト値など）２０２を出力する。また、ポジション検索エンジン１０は、一致した検索文字列を含む検索データ２０４を生成し、図示しないオリジナルサーチＣＡＭへ出力する。
【０１６６】
以下、ポジション検索エンジン１０での検索動作について詳述する。まず、ポジション検索エンジン１０は、ＨＴＴＰヘッダデータを、検索用ヘッダデータ＃Ｎ−１「＊＊＊＊ＧＥＴ  ／ｃ」，検索用ヘッダデータ＃Ｎ「ＧＥＴ  ／ｃｎｎ／ｃ」，…のように４バイトずつシフトさせて１０バイトのデータをポジションサーチＣＡＭ２０へ入力する。ポジションサーチＣＡＭ２０は、入力される検索用ヘッダデータの各々を、予め格納している検索ルール（アドレスルール）と比較する。
【０１６７】
図１９に示すＨＴＴＰヘッダデータでは、検索用ヘッダデータ＃Ｎ「ＧＥＴ  ／ｃｎｎ／ｃ」とアドレスルール０の０番地「ＧＥＴ  ／＊＊＊＊＊」とが一致し、検索用ヘッダデータ＃Ｍ「１￥ｒ￥ｎＡｃｃｅｐ」とアドレスルール１の１番地「＊￥ｒ￥ｎ＊＊＊＊＊」とが一致する。ポジションサーチＣＡＭ２０は、入力されたＨＴＴＰヘッダデータといずれかのエントリとが一致すると、当該一致した検索文字列の検索データ情報（開始位置情報（シフト回数）およびルール番号など）をポジション検索エンジン１０へ出力する。
【０１６８】
ポジション検索エンジン１０は、一致した検索用ヘッダデータに対応する検索用フッダデータを用いて、再帰的な検索を実行する。図１９に示す例では、Ｈｉｔ（Ｎ，０）のように、一致した検索文字列の開始位置情報「＃Ｎ」とルール番号「０」とがアドレスとして出力される。
【０１６９】
ポジション検索エンジン１０は、ポジションサーチＣＡＭ２０からの検索データ情報などに基づいて、ＨＴＴＰヘッダデータから抽出するキーワード（検索データ）の先頭および最後尾の文字の位置を特定する。図１９に示す例では、ＨＴＴＰヘッダデータ内の＃Ｎ「ＧＥＴ  ／」から＃Ｍ「￥ｒ￥ｎ」までをキーワード「ＧＥＴ  ／ｃｎｎ／ｃｎｉｎｔｌ＿ａｄｓｐａｃｅｓ／……ＨＴＴＰ／１．１￥ｒ￥ｎ」として抽出する。
【０１７０】
図示しないオリジナルサーチＣＡＭは、抽出されキーワードに対してオリジナルサーチ（全文検索）を実行する。
【０１７１】
実施の形態８に従う半導体装置１Ｇにおいては、ポジションサーチＣＡＭ２０を用いることで、検索システム全体として搭載されるメモリ容量の増加を抑制しつつ、ＨＴＴＰヘッダデータ内のキーワードを高速に検索することができる。そのため、ネットワークのワイヤスピードでのキーワード抽出（文字列抽出）を実現できる。なお、ポジションサーチＣＡＭ２０としては、上述したプリサーチ機能を有するポジションサーチＣＡＭ２０Ａを用いてもよい。
【０１７２】
ポジションサーチＣＡＭ２０を用いたテーブル検索方式と、ポジション検索エンジン１０を用いた再帰的な検索手法とを組み合わせることで、ＨＴＴＰヘッダデータ内から高速なキーワード抽出（文字列抽出）を実現できる。実施の形態８に従う半導体装置１Ｇにおいては、特定の検索文字列の開始位置を取得できるので、検索文字列の頭出しが可能となり、通常のテーブル検索方式を用いて、入力された文字列内から検索文字列を特定することが可能となる。
【０１７３】
［Ｋ．実施の形態９］
次に、部分検索であるポジションサーチを採用することで生じ得るマルチマッチによる不具合を解消するための構成例について説明する。
【０１７４】
本明細書にて説明する「マルチマッチ」は、同一の検索用ペイロードデータに対して、ポジションサーチＣＡＭ２０に予め格納される２つ以上の検索ルール（ポジションルール）について同時に一致（Ｈｉｔ）と判定される現象である。このマルチマッチは、適切な検索文字列を登録することで回避できるが、以下では、どのような検索文字列であってもロバストな検索動作を実行できる構成について説明する。
【０１７５】
図２０は、図５に示す実施の形態１に従う半導体装置１において生じ得るマルチマッチを説明するための図である。図２０を参照して、例えば、検索文字列として、先頭に同じ文字が連続する「ａａａａａａａａＷａｒｎｉｎｇ！」（８個の連続する「ａ」の後に「Ｗａｒｎｉｎｇ！」が続く）を想定する。このような先頭に同じ文字が連続する検索文字列を登録した場合には、ポジションサーチＣＡＭ２０でのポジションサーチにおいて、マルチマッチが生じ得る。
【０１７６】
一般的には、ポジションサーチＣＡＭ２０には、図示しないプライオリティエンコーダ（ＰＥ：Priority Encoder）が実装されている。プライオリティエンコーダは、マルチマッチ、すなわち複数の一致アドレス（ＨｉｔＡｄｄ）が同時に出力された場合には、優先度が最も高い一致アドレスを選択して出力する。但し、優先度が最も高い一致アドレスが本来の一致アドレスとは限らず、オリジナルサーチＣＡＭ３０でのオリジナルサーチ（全文検索）で一致すべき文字列を見逃してしまう可能性がある。この課題について詳述する。
【０１７７】
図２０に示す例では、ペイロードデータシフト部１０２は、４バイトずつシフトした各８バイトの検索用ペイロードデータＰＤ１「ａａａａａａＷａ」、検索用ペイロードデータＰＤ２「ａａＷａｒｎｉｎ」…をポジションサーチＣＡＭ２０へそれぞれ入力する。
【０１７８】
ポジションサーチＣＡＭ２０は、８バイトの検索ルール（ポジションルール）をエントリＰＤＥ０「ａａａａａａａａ」、エントリＰＤＥ１「＊ａａａａａａａ」、エントリＰＤＥ２「＊＊ａａａａａａ」、エントリＰＤＥ３「＊＊＊ａａａａａ」、…のように１バイトずつシフトさせて予め格納している。
【０１７９】
ポジションサーチＣＡＭ２０では、最初の検索用ペイロードデータＰＤ０「ａａａａａａａａ」に対して、エントリＰＤＥ０「ａａａａａａａａ」、ＰＤＥ１「＊ａａａａａａａ」、ＰＤＥ２「＊＊ａａａａａａ」、および、ＰＤＥ３「＊＊＊ａａａａａ」のすべてのエントリが一致（Ｈｉｔ）と判定される。すなわち、４つのエントリについてマルチマッチする。
【０１８０】
このマルチマッチに対して、プライオリティエンコーダは、優先度が最も高い一致アドレスのみを選択して出力する。図２０に示す例では、格納されている番地が最も小さい、エントリＰＤＥ０についての一致アドレス（ＨｉｔＡｄｄ）「４ｎ＋０」のみが出力される。制御回路１０４は、一致アドレス「４ｎ＋０」を、ルール番号「４ｎ」と、シフト値（オフセット情報）「０」とに分離する。制御回路１０４は、ペイロードデータシフト部１０２でペイロードデータをシフトした回数「０」とシフト値「０」とから、ペイロードデータ内の文字列の開始位置情報「０」（＝４×０＋０）を算出し、その開始位置情報から、オリジナルサーチ部２００での全文検索の対象となるシフト後検索データ（ＳＰＤ）を生成する。この場合には、シフト後検索データ（ＳＰＤ）は、「ａａａａａａａａａａＷａｒｎｉｎｇ！……」（１０個の連続する「ａ」の後に「Ｗａｒｎｉｎｇ！」が続く）となる。
【０１８１】
オリジナルサーチＣＡＭ３０には、検索文字列が先頭から必要なバイト数分だけ格納される。図２０に示す例では、オリジナルサーチＣＡＭ３０には、１エントリあたり、最大６４文字の文字列（１文字１バイト）を格納できる。例えば、検索文字列が「ａａａａａａａａＷａｒｎｉｎｇ！」（８個の連続する「ａ」）の場合には、オリジナルサーチＣＡＭ３０のエントリＤＥ０として、「ａａａａａａａａＷａｒｎｉｎｇ！＊＊＊＊＊＊＊＊」（８個の連続する「ａ」）が登録される。ここで、先頭から１６バイト以外の文字列は任意の文字列でよいため、「＊（アスタリスク）」（Ｄｏｎ’ｔ  ｃａｒｅ）が指定される。
【０１８２】
オリジナルサーチＣＡＭ３０は、制御回路１０４で生成されたシフト後検索データＳＰＤ「ａａａａａａａａａａＷａｒｎｉｎｇ！……」（１０個の連続する「ａ」）と格納している検索ルールとを比較する。図２０に示す例では、シフト後検索データＳＰＤ「ａａａａａａａａａａＷａｒｎｉｎｇ！……」（１０個の連続する「ａ」）と、エントリＤＥ０「ａａａａａａａａＷａｒｎｉｎｇ！＊＊＊＊＊＊＊＊」（８個の連続する「ａ」）とは一致しないので、不一致（Ｍｉｓｓ）と判定される。
【０１８３】
すなわち、図２０に示す検索動作では、プライオリティエンコーダが一致アドレスとして「４ｎ＋０」を出力したために、オリジナルサーチＣＡＭ３０では不一致（Ｍｉｓｓ）と判定されている。一方で、プライオリティエンコーダが一致アドレスとして「４ｎ＋２」を出力していれば、制御回路１０４は、シフト値「２」を用いて、シフト後検索データ（ＳＰＤ）を生成するので、「ａａａａａａａａＷａｒｎｉｎｇ！＊＊＊＊＊＊＊＊」（８個の連続する「ａ」）がポジションサーチＣＡＭ２０へ入力され、ポジションサーチＣＡＭ２０の比較結果は一致（Ｈｉｔ）になっていたはずである。
【０１８４】
すなわち、図２０に示す例では、制御回路１０４がシフト値＝０に基づいて、シフト後検索データＳＰＤを生成したため、不一致（Ｍｉｓｓ）と判定されたが、シフト値＝２として、シフト後検索データＳＰＤを生成すれば、一致（Ｈｉｔ）と判定できる。
【０１８５】
上述のように、マルチマッチが生じると、プライオリティエンコーダによって、本来の一致アドレスではなく、異なる一致アドレスが出力されるため、本来は一致（Ｈｉｔ）と判定されるべき検索用ペイロードデータに対して、不一致（Ｍｉｓｓ）と誤判定する可能性がある。
【０１８６】
そこで、実施の形態９においては、上述のようなマルチマッチが生じた場合であっても、誤判定することなく、比較結果を出力できる構成例について説明する。
【０１８７】
図２１は、実施の形態９に従う半導体装置１Ｈの要部構成および検索動作を説明する模式図である。図２１を参照して、半導体装置１Ｈは、同一の検索用ペイロードデータが並列に入力される４個のポジションサーチＣＡＭ２０＿０〜２０＿３を有している。マルチマッチ対策として、４個のポジションサーチＣＡＭ２０＿０〜２０＿３にそれぞれ対応付けてプライオリティエンコーダ（ＰＥ）２２＿０〜２２＿３が設けられている。
【０１８８】
実施の形態９に従う半導体装置１Ｈでは、ポジションサーチＣＡＭ２０＿０〜２０＿３には、同一の検索文字列（の一部）に異なるオフセットをそれぞれ付与した複数のエントリが分散して格納されている。具体的には、ポジションサーチＣＡＭ２０＿０〜２０＿３には、同一の検索ルール（ポジションルール）を１バイトずつシフトさせたそれぞれのエントリが格納される。すなわち、実施の形態１に従う半導体装置１においては、１個のポジションサーチＣＡＭ２０に４エントリの検索ルールを格納していた。これに対して、実施の形態９に従う半導体装置１Ｈにおいては、同一の検索ルールを１バイトずつシフトさせたそれぞれのエントリについて、１つのポジションサーチＣＡＭ２０に１つのエントリが格納される。例えば、８バイトの検索ルール（ポジションルール）を１バイトずつシフトさせて得られる、エントリＰＤＥ０「ａａａａａａａａ」はポジションサーチＣＡＭ２０＿０に格納され、エントリＰＤＥ１「＊ａａａａａａａ」はポジションサーチＣＡＭ２０＿１に格納され、エントリＰＤＥ２「＊＊ａａａａａａ」はポジションサーチＣＡＭ２０＿２に格納され、エントリＰＤＥ３「＊＊＊ａａａａａ」はポジションサーチＣＡＭ２０＿３に格納される。
【０１８９】
同一の検索用ペイロードデータ（図２１には、アドレス＜８７：２４＞に相当）を４個のポジションサーチＣＡＭ２０＿０〜２０＿３へ同時に入力する。ポジションサーチＣＡＭ２０＿０〜２０＿３の各々は、入力された検索用ペイロードデータと格納している各エントリとを比較し、一致（Ｈｉｔ）場合には、その一致アドレス（ＨｉｔＡｄｄ）を対応するプライオリティエンコーダ２２へ出力する。
【０１９０】
図２１に示す例では、図２０と同様に、「ａａａａａａａａＷａｒｎｉｎｇ！」（８個の連続する「ａ」の後に「Ｗａｒｎｉｎｇ！」が続く）が検索文字列として指定されているとする。この状態において、検索用ペイロードデータとして、「ａａａａａａａａ」が入力された場合を示す。
【０１９１】
ポジションサーチＣＡＭ２０＿０〜２０＿３のすべてにおいて、予め格納されているエントリと一致（Ｈｉｔ）するので、ポジションサーチＣＡＭ２０＿０〜２０＿３は、一致アドレス（ＨｉｔＡｄｄ０〜ＨｉｔＡｄｄ３）として、「４ｎ＋０」，「４ｎ＋１」，「４ｎ＋２」，「４ｎ＋３」をそれぞれ出力する。
【０１９２】
実施の形態９に従う半導体装置１Ｈにおいて、図示しない制御回路１０４は、ポジションサーチＣＡＭ２０＿０〜２０＿３の各々から出力される検索文字列（の一部）と一致する部分の位置情報に基づいて、検索データを入力データ列から抽出する。すなわち、制御回路１０４は、出力されたそれぞれの一致アドレスに基づいて、それぞれ検索用データを生成する。そして、オリジナルサーチＣＡＭ３０は、生成されたそれぞれの検索用データに対して、オリジナルサーチ（全文検索）を実行する。この結果、ポジションサーチＣＡＭ２０＿２から出力された一致アドレス（ＨｉｔＡｄｄ２）である「４ｎ＋２」に基づいて生成された検索用データが、オリジナルサーチＣＡＭ３０に予め格納される検索文字列と一致することになる。
【０１９３】
実施の形態９に従う半導体装置１Ｈにおいて、プライオリティエンコーダ２２＿０〜２２＿３の各々は、同一の検索ルールから生成された複数のエントリを用いた一致アドレスの間で優先度を評価するのではなく、異なる検索ルールからそれぞれ生成された単一のエントリの間で優先度を評価することになり、図２０に示すような、本来出力すべき一致アドレスを見落とすといった事態を回避できる。
【０１９４】
このように、同一の検索用ペイロードデータと検索ルールとの比較を異なるポジションサーチＣＡＭ２０を用いて並列的に実行することで、単一のポジションサーチＣＡＭ２０を用いた場合に生じ得る、一致アドレスの出力見落としといった事態を回避できる。
【０１９５】
［Ｌ．実施の形態１０］
上述の実施の形態９に従う半導体装置１Ｈにおいては、マルチマッチが生じたとしても検索文字列の見落としは生じないが、ポジションサーチＣＡＭ２０でのポジションサーチ（あいまい検索）の偽陽性率（最終的なオリジナルサーチでは不一致であるが、ポジションサーチでは一致と判定される確率）がいくらか高くなる。このような偽陽性率の増加に伴なるオーバヘッドが問題となる場合には、以下に説明するような、実施の形態１０に従う半導体装置１Ｈのような構成を採用することが好ましい。
【０１９６】
図２２は、実施の形態１０に従う半導体装置１Ｉの要部構成および検索動作を説明する模式図である。図２２（Ａ）には、比較対象として、実施の形態９に従う半導体装置１Ｈの要部構成および検索動作を示し、図２２（Ｂ）には、実施の形態１０に従う半導体装置１Ｉの要部構成および検索動作を示す。
【０１９７】
図２２（Ａ）と図２２（Ｂ）とを比較して、実施の形態１０に従う半導体装置１Ｈの要部構成は、図２１に示す実施の形態９に従う半導体装置１Ｈの要部構成と類似している。但し、ポジションサーチＣＡＭ２０＿０〜２０＿３に格納されるエントリ、および、ポジションサーチＣＡＭ２０＿０〜２０＿３への検索用ペイロードデータの入力方式が実施の形態９の構成とは異なっている。
【０１９８】
まず、図２２（Ａ）を参照して、実施の形態９に従う半導体装置１Ｈにおいて生じ得る偽陽性率の増加について説明する。図２２には、検索文字列として「Ｗａｒｎｉｎｇ！」を想定した検索動作を示す。
【０１９９】
図２２（Ａ）に示す半導体装置１Ｈにおいて、ポジションサーチＣＡＭ２０＿０〜２０＿３には、検索文字列「Ｗａｒｎｉｎｇ！」を１バイトずつシフトさせた、エントリＰＤＥ０「Ｗａｒｎｉｎｇ！」、エントリＰＤＥ１「＊Ｗａｒｎｉｎｇ」、エントリＰＤＥ２「＊＊Ｗａｒｎｉｎ」、エントリＰＤＥ３「＊＊＊Ｗａｒｎｉ」がそれぞれ格納されている。
【０２００】
このような検索ルールが格納されたポジションサーチＣＡＭ２０＿０〜２０＿３に対して、同一の検索用ペイロードデータ「ａａａＷａｒｎｉ」が入力されるとする。ポジションサーチＣＡＭ２０＿０〜２０＿３では、あいまい検索が実行される。このあいまい検索では、入力された検索用ペイロードデータと、ポジションサーチＣＡＭ２０＿３に格納されているエントリＰＤＥ３「＊＊＊Ｗａｒｎｉ」とが一致する。但し、このあいまい検索において、ポジションサーチＣＡＭ２０に格納されているエントリのうち、検索用ペイロードデータと完全に一致している文字列は、「Ｗａｒｎｉ」の５文字（５バイト）である。「Ｗａｒｎｉ」以降の文字は確定していないため、例えば、制御回路にて生成される検索データが「ＷａｒｎｉＮＧ！…」であるような場合には、オリジナルサーチＣＡＭ３０では、検索データが検索文字列「Ｗａｒｎｉｎｇ！」とは一致しない。このように、実施の形態９に示すようなあいまい検索では、ポジションサーチＣＡＭ２０において一致（Ｈｉｔ）と判定された場合であっても、オリジナルサーチＣＡＭ３０において一致（Ｈｉｔ）とは判定されない場合が生じる。
【０２０１】
図２２（Ｂ）を参照して、実施の形態１０に従う半導体装置１Ｉでは、ポジションサーチＣＡＭ２０＿０〜２０＿３には、同一の検索文字列「Ｗａｒｎｉｎｇ！」が格納される。その上で、検索用ペイロードデータを１バイトずつシフトして、ポジションサーチＣＡＭ２０＿０〜２０＿３へ入力する。なお、図２２中の「＜８７：２４＞」といった標記は、入力されたペイロードデータのうち、検索用ペイロードデータとして抽出される文字列の開始および終了位置（バイト位置）を示す。
【０２０２】
ポジションサーチＣＡＭ２０＿０〜２０＿３は、同一の検索文字列（の一部）を共通に含んでおり、ポジションサーチＣＡＭ２０＿０〜２０＿３には、ペイロードデータの互いに異なる位置から開始するそれぞれのデータが検索対象として入力される。より具体的には、実施の形態１０に従う半導体装置１Ｉでは、図２２（Ａ）に示す実施の形態９に従う半導体装置１ＨのポジションサーチＣＡＭ２０＿０〜２０＿３に格納されていた「＊（アスタリスク）」（Ｄｏｎ’ｔ  ｃａｒｅ）のメモリ領域を利用して、ポジションサーチＣＡＭ２０＿０〜２０＿３のすべてに８バイト分の検索文字列「Ｗａｒｎｉｎｇ！」を格納する。
【０２０３】
ポジションサーチＣＡＭ２０＿０〜２０＿３へそれぞれ入力される検索用ペイロードデータは、それぞれ１バイトずつシフトされている。より具体的には、ポジションサーチＣＡＭ２０＿０には「ａａａＷａｒｎｉ」が入力され、ＣＡＭ２０＿１には「ａａＷａｒｎｉｎ」が入力され、ＣＡＭ２０＿２には「ａＷａｒｎｉｎｇ」が入力され、ＣＡＭ２０＿３には「Ｗａｒｎｉｎｇ！」が入力される。ポジションサーチＣＡＭ２０＿０〜２０＿３の各々は、入力された検索用ペイロードデータと格納している各エントリとを比較し、一致（Ｈｉｔ）場合には、その一致アドレス（ＨｉｔＡｄｄ）を出力する。
【０２０４】
図２２（Ｂ）に示す例では、ポジションサーチＣＡＭ２０＿３において、入力された検索用ペイロードデータと格納されているエントリＰＤＥ１３とが一致する。図２２（Ａ）に示すあいまい検索とは異なり、登録されているエントリ「Ｗａｒｎｉｎｇ！」のすべてと検索用ペイロードデータとが一致するので、偽陽性率を低減することができる。上述したように、複数のポジションサーチＣＡＭ２０に登録される検索ルール（ポジションルール）から「＊（アスタリスク）」（Ｄｏｎ’ｔ  ｃａｒｅ）を排除し、登録されているエントリのすべての文字列が入力された検索用ペイロードデータと一致している場合に限って、一致（Ｈｉｔ）を出力するように構成することで、偽陽性率を低減できる。また、偽陽性率を低減することで、オリジナルサーチＣＡＭ３０での無駄なオリジナルサーチ（全文検索）の実行頻度も低減できるので、回路全体としての低消費電力化を実現できる。
【０２０５】
［Ｌ．利点］
以上のとおり、本発明の各実施の形態によれば、連想メモリのメモリ容量の増加を抑制しつつ、より高速なキーワード検索が可能な回路構成を実現できる。
【０２０６】
以上、本発明者らによってなされた発明を実施の形態に基づき具体的に説明したが、本発明は上記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。
【符号の説明】
【０２０７】
１，１Ａ，１Ｂ，１Ｃ，１Ｄ，１Ｅ，１Ｆ，１Ｇ，１Ｈ，１Ｉ  半導体装置、２  情報処理システム、４  上位コントローラ、８  コントローラ、１０  ポジション検索エンジン、１２  キーワードシフト・制御部、１４  ポジション検索部、１６  キーワード抽出・生成・制御部、２０，２０Ａ  ポジションサーチＣＡＭ、２２，９１２  プライオリティエンコーダ、３０，３０Ａ，３０Ｂ，９６０  オリジナルサーチＣＡＭ、１００，１００Ａ，１００Ｂ，１００Ｅ  ポジションサーチ部、１０２，１０２Ａ，１０２Ｅ  ペイロードデータシフト部、１０４，１０４Ａ，１０４Ｂ，１０４Ｅ  制御回路、１０６，１０６Ａ  検索データ情報抽出回路、１０８，１０８Ａ，１０８Ｂ  検索データ生成回路、２００，２００Ａ  オリジナルサーチ部、２０４  検索データ、５００  パーソナルコンピュータ、６００  インターネット、９００  ＣＡＭ内蔵集積回路、９０９  検索用ペイロードデータシフト部、９１１  ＣＡＭアレイ、９１５  検索用データ組合せ部、９２０  オフセット情報出力部、９５０  検索システム、ＨＤ  ヘッダデータ、ＬＴ  ラッチ部、ＰＤ  検索用ペイロードデータ。
【図１】
0006592310.tif 000002
【図２】
0006592310.tif 000003
【図３】
0006592310.tif 000004
【図４】
0006592310.tif 000005
【図５】
0006592310.tif 000006
【図６】
0006592310.tif 000007
【図７】
0006592310.tif 000008
【図８】
0006592310.tif 000009
【図９】
0006592310.tif 000010
【図１０】
0006592310.tif 000011
【図１１】
0006592310.tif 000012
【図１２】
0006592310.tif 000013
【図１３】
0006592310.tif 000014
【図１４】
0006592310.tif 000015
【図１５】
0006592310.tif 000016
【図１６】
0006592310.tif 000017
【図１７】
0006592310.tif 000018
【図１８】
0006592310.tif 000019
【図１９】
0006592310.tif 000020
【図２０】
0006592310.tif 000021
【図２１】
0006592310.tif 000022
【図２２】
0006592310.tif 000023