並列パターン検索エンジンのパターンマッチング結果を通信するための装置、システム、および方法
開示されているのは次のような方法およびシステムである。その中には、データストリーム（１２）を検索するための一つ以上のパターン認識プロセッサ（１４，９３）を含む装置を含むシステムがある。パターン認識プロセッサ（１４，９３）のクラスタは、様々な検索機能を実行するために使用されてよい、さまざまなパターンマッチングマトリクス（４０、４２、４４、４６、４８、５０）およびマスクモジュール（９４、９６、９８、１００）を含んでよい。さらに、バッファ（２５）は、情報検索に対する、パターンマッチングマトリクス（４０、４２、４４、４６、４８、５０）およびマスクモジュール（９４、９６、９８、１００）からの続いて起こる様々な結果を個別に記憶するために使用されてよい。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、概して、パターン認識プロセッサおよび、より具体的には、実施形態において、パターン認識プロセッサの多重動作からの結果として生じるデータの通信に関する。
【背景技術】
【０００２】
コンピューティングの分野においては、パターン認識タスクは、ますます性能が試される。大量のデータさえコンピュータ間で伝送され、ユーザが識別を望むパターンの数は増加している。例えば、スパムもしくはマルウェアは、しばしば、データストリームにおけるパターン（例えば、特定の句もしくはコードの一部）を検索することによって検出される。新規の変異形を検索するために新規のパターンが実施される可能性があるため、パターンの数は、スパムおよびマルウェアの多様性によって増加する。これらのパターンの各々に対してデータストリームを検索することは、コンピューティングボトルネック（障害）を形成する可能性がある。しばしば、データストリームが受信されると、一つずつ、各パターンを検索される。システムより前の遅延は、パターン数に伴うデータストリームの増加の次の部分を検索する状態にある。したがって、パターン認識は、データの受信を遅延させる可能性がある。
【０００３】
パターン認識タスクは、実行されることになるさまざまなタイプの照合（一致、マッチ）によってしばしば複雑化される。データストリームは、短く連続する間にいくつかのパターンを照合し、これらの様々な照合は分類され得る。これらの照合による検索は、システムの相対的な性能を遅くし、これにより新しい照合が発生したときにシステムに対して迅速に応答することをできなくさせる。他の例においては、、照合が発生する前の比較的長期間にわたってデータストリームが受信される可能性がある。これにより照合を処理するための他の構成部分の能力は使用されずに残ることとなる。パターン認識中のリザルトデータの不規則な流れは、パターン認識ハードウェアとインタフェース接続するシステムの設計を難しくする。
【図面の簡単な説明】
【０００４】
【図１】データストリームを検索するシステムの一実施例を示す。
【図２】図１のシステムにおけるパターン認識プロセッサの一実施例を示す。
【図３】図２のパターン認識プロセッサにおける検索タームセルの一実施例を示す。
【図４】単一の文字に対してデータストリームを検索する、図３の検索タームセルを示す。
【図５】単一の文字に対してデータストリームを検索する、図３の検索タームセルを示す。
【図６】一語に対してデータストリームを検索する幾つかの検索タームセルを含む認識モジュールを示す。
【図７】一語に対してデータストリームを検索する幾つかの検索タームセルを含む認識モジュールを示す。
【図８】一語に対してデータストリームを検索する幾つかの検索タームセルを含む認識モジュールを示す。
【図９】二語に対してパラレルにデータストリームを検索するように構成された認識モジュールを示す。
【図１０】同一の接頭辞を有する複数語を特定する検索基準に従って検索する認識モジュールを示す。
【図１１】同一の接頭辞を有する複数語を特定する検索基準に従って検索する認識モジュールを示す。
【図１２】同一の接頭辞を有する複数語を特定する検索基準に従って検索する認識モジュールを示す。
【図１３】図１のシステムにおけるパターン認識プロセッサの第２の例を示す。
【図１４】図１３のパターン認識プロセッサにおけるリザルトバッファの例を示す。
【図１５】図１４のリザルトバッファと接続して使用されるレジスタバンクの直列接続を示す。
【発明を実施するための最良の形態】
【０００５】
図１は、データストリーム１２を検索するシステム１０の一実施例を示す。システム１０は、検索基準１６に従ってデータストリーム１２を検索するパターン認識プロセッサ１４を含んでもよい。
【０００６】
各検索基準は、一つ以上の対象表現、すなわちパターンを特定してもよい。“対象表現”という用語は、パターン認識プロセッサ１４が検索するためのデータ配列（シーケンス）のことを称する。対象表現の例は、ある単語を綴る文字配列、遺伝子を特定する遺伝子塩基対配列、画像の一部を形成する画像ファイルもしくはビデオファイルにおけるビット配列、プログラムの一部を形成する実行可能ファイルにおけるビット配列、または、歌もしくは口語表現の一部を形成するオーディオファイルにおけるビット配列を含む。
【０００７】
検索基準は、一つ以上の対象表現を特定してもよい。例えば、検索基準は、文字列“ｃｌ”で始まる全５文字の単語、文字列“ｃｌ”で始まるあらゆる単語、３回以上“ｃｌｏｕｄ”という単語を含む段落などを特定してもよい。対照表現のうちで生じうる組の数は、任意の大きさであり、例えば、データストリームが存在することが可能であるデータの順列が存在するのと同一数の対象表現が存在する可能性がある。検索基準は、種々のフォーマットで表現されてもよく、そのフォーマットは、正規表現として、各対象表現を必ずしも記載することなく、対象表現の組を簡潔に特定するプログラミング言語を含む。
【０００８】
各検索基準は、一つ以上の検索タームから構成されてもよい。したがって、検索基準の各対象表現は一つ以上の検索タームを含み、幾つかの対象表現は、共通の検索タームを使用してもよい。本明細書で使用されるように、“検索ターム”という用語は、単一の検索周期の間に検索されるデータの配列のことを称する。データの配列は、バイナリフォーマットもしくは、例えば、１０進法、ＡＳＣＩＩなどの他のフォーマットにおける複数ビットのデータを含んでもよい。配列は、単一のディジットもしくは複数のディジット（例えば幾つかのバイナリディジット）でデータをエンコードしてもよい。例えば、パターン認識プロセッサ１４は、一度に一文字をテキストデータストリーム１２から検索し、検索タームは、例えば、文字“ａ”、文字“ａ”か“ｅ”のいずれか、または、全ての単一文字の組を特定するワイルドカード検索タームなど、単一文字の組を特定してもよい。
【０００９】
検索タームは、文字（もしくは、データストリームによって表現される情報の他の書記素、すなわち基本単位、例えば、音符、遺伝子塩基対、１０進法のディジット、サブピクセル）を特定するビット数よりも小さいか、または大きくてもよい。例えば、検索タームは８ビットであり、単一文字は１６ビットであり、この場合には、二つの連続した検索タームは単一文字を特定してもよい。
【００１０】
検索基準１６は、コンパイラ１８によってパターン認識プロセッサ１４のためにフォーマットされてもよい。フォーマットするステップは、検索基準から検索タームを分解するステップを含んでもよい。例えば、データストリーム１２によって表現された書記素が検索タームよりも大きい場合、コンパイラは単一の書記素を検索するために、複数の検索タームへと検索基準を分解してもよい。同様に、データストリーム１２によって表現された書記素が検索タームよりも小さい場合、コンパイラ１８は、各個別の書記素に対して、使用されていないビットを伴う単一の検索タームを提供してもよい。コンパイラ１８は、パターン認識プロセッサ１４によって本来サポートされていない種々の正規表現演算子をサポートするために、検索基準１６をフォーマットしてもよい。
【００１１】
パターン認識プロセッサ１４は、データストリーム１２から各新規タームを評価することによって、データストリーム１２を検索してもよい。本明細書における“ターム”という用語は、検索タームに一致しうるデータ量のことを称する。検索周期の間、パターン認識プロセッサ１４は、現在提示されているタームが検索基準において現在の検索タームに一致するかどうかを決定してもよい。タームが検索タームと一致する場合には、評価は“進行”し、すなわち、次のタームが検索基準における次の検索タームと比較される。そのタームが一致しない場合には、次のタームは、検索基準における第一のタームと比較され、それによって検索をリセットする。
【００１２】
各検索基準は、パターン認識プロセッサ１４における異なる有限ステートマシンへとコンパイルされてもよい。有限ステートマシンは、パラレルに（並行して）実行してもよく、検索基準１６に従ってデータストリーム１２を検索する。有限ステートマシンは、先行する検索タームがデータストリーム１２によって一致する場合に検索基準における連続する各検索タームへと進んでもよい。または、検索タームが一致しない場合には、有限ステートマシンは検索基準における第一の検索タームの検索を開始してもよい。
【００１３】
パターン認識プロセッサ１４は、幾つかの検索基準に従って各新規タームを評価し、ほぼ同時に、例えば、単一のデバイス周期の間に其々の検索タームを評価してもよい。パラレルな有限ステートマシンは、ほぼ同時にデータストリーム１２からタームを各々受信し、パラレルな有限ステートマシンの各々は、そのタームが、パラレルな有限ステートマシンを検索基準における次の検索タームへと進めるかどうかを決定してもよい。パラレルな有限ステートマシンは、比較的多数の検索基準（例えば、１００以上、１０００以上、もしくは１００００以上）に従って、タームを評価してもよい。それらはパラレルに動作するため、データストリームを遅延させることなく、比較的高いバンド幅を有するデータストリーム１２（例えば、６４ＭＢ毎秒もしくは１２８ＭＢ毎秒より大きいかほぼ同一のデータストリーム１２）に対して検索基準を適用してもよい。幾つかの実施形態においては、検索周期の継続期間は、検索基準の数によって増減しないため、検索基準の数はパターン認識プロセッサ１４の性能にあまり影響を与えることはない。
【００１４】
検索基準が満足されるとき（すなわち、最後の検索タームに進行してそれが一致した後）、パターン認識プロセッサ１４は、中央処理装置（ＣＰＵ）２０などの処理装置に対して基準を満足したことを報告してもよい。中央処理装置２０は、パターン認識プロセッサ１４およびシステム１０の他の部分を制御してもよい。
【００１５】
システム１０は、データのストリームを検索する種々のシステムもしくはデバイスのうちのいずれであってもよい。例えば、システム１０は、データストリーム１２を監視するデスクトップ、ラップトップ、ハンドヘルドもしくは他のタイプのコンピュータであってもよい。システム１０は、ルータ、サーバ、もしくはクライアント（例えば、前述されたタイプのコンピュータのうちの一つ）などのネットワークノードであってもよい。システム１０は、コピー機、スキャナ、プリンタ、ゲーム機、テレビ、セットトップビデオ分配もしくは録画システム、ケーブルボックス、パーソナルデジタルメディアプレイヤー、工場自動化システム、自動車用コンピュータシステムもしくは医療デバイスなどの他の種類の何らかの電子デバイスであってもよい。（これらの種々のシステムの実施例を記述するために使用される用語は、本明細書で使用される他の多くの用語と同様に、幾つかの指示対象を共有し、それ自体は、列挙された他の項目によって、範囲を狭めて構成されるべきではない。）
【００１６】
データストリーム１２は、ユーザもしくは他の存在が検索を望む可能性のある、種々のタイプの一つ以上のデータストリームであってもよい。例えば、データストリーム１２は、インターネットを介して受信されたパケット、または、携帯電話ネットワークを介して受信された音声もしくはデータなど、ネットワークを介して受信されたデータのストリームであってもよい。データストリーム１２は、画像センサ、温度センサ、加速度計などもしくはその組み合わせなど、システム１０と連通するセンサから受信されたデータであってもよい。データストリーム１２は、シリアルデータストリームとしてシステム１０によって受信され、データは、時間的、語彙的、もしくは意味的に意義のある順序など、意味のある順序で受信される。または、データストリーム１２は、パラレルにもしくはバラバラの順序で受信され、その後、例えば、インターネットを介して受信されたパケットを順序づけることによって、シリアルデータストリームへと変換される。幾つかの実施形態においては、データストリーム１２は、タームをシリアルに提示してもよいが、各タームを表すビットはパラレルに受信されてもよい。データストリーム１２は、システム１０に対して外部ソースから受信されてもよいか、または、メモリデバイスにインテロゲート（伝送）し、格納されたデータからデータストリーム１２を形成することによって形成されてもよい。
【００１７】
データストリーム１２におけるデータのタイプに依存して、異なるタイプの検索基準が設計者によって選択されてもよい。例えば、検索基準１６は、ウイルス定義ファイルであってもよい。ウイルスもしくは他のマルウェアは特徴づけられ、マルウェアの態様は、データストリーム１２がマルウェアを伝送しうるかどうかを示す検索基準を形成するために使用されてもよい。結果として生じる検索基準はサーバに格納され、クライアントシステムのオペレータはシステム１０へと検索基準をダウンロードするサービスに登録してもよい。検索基準１６は、異なるタイプのマルウェアが現れたとき、サーバから定期的にアップデートされてもよい。検索基準は、ネットワークを介して受信される可能性のある望ましくないコンテンツ（例えば、（スパムとしてよく知られている）迷惑電子メールもしくはユーザが望まない他のコンテンツ）を特定するために使用されてもよい。
【００１８】
データストリーム１２はシステム１０によって受信されたデータに対して関心を持った第三者によって検索されてもよい。例えば、データストリーム１２は、著作物として生じる文字列、音声配列、ビデオ配列に対して監視されてもよい。データストリーム１２は、刑事捜査もしくは民事手続きに関係する発話、もしくは使用者にとって関心のある発話に対して監視されてもよい。
【００１９】
検索基準１６は、例えば、ＣＰＵ２０もしくはパターン認識プロセッサ１４によってアドレス可能なメモリにおいて、翻訳が入手可能であるデータストリーム１２におけるパターンを含んでもよい。例えば、検索基準１６は、対応するスペイン語がメモリに格納された英単語を各々特定してもよい。別の実施例においては、検索基準１６は、例えば、デコードされたバージョンのデータストリーム１２が使用可能であるＭＰ３、ＭＰＥＧ４、ＦＬＡＣ、Ｏｇｇ Ｖｏｒｂｉｓなど、エンコードされたバージョンのデータストリーム１２を特定してもよいし、その逆を特定してもよい。
【００２０】
パターン認識プロセッサ１４は、ＣＰＵ２０と共に（単一のデバイスなどの）単一の構成部分に統合されたハードウェアであってもよいし、別個の構成部分として形成されてもよい。例えば、パターン認識プロセッサ１４は別個の集積回路であってもよい。パターン認識プロセッサ１４は、“コプロセッサ”もしくは“パターン認識コプロセッサ”と称されてもよい。
【００２１】
図２は、パターン認識プロセッサ１４の一実施例を示す。パターン認識プロセッサ１４は、認識モジュール２２および出力バッファ５１を有する集約モジュール２４を含んでもよい。出力バッファ５１は、リザルトバッファ２５を含んでもよい。認識モジュール２２は、受信されたタームを検索タームと比較するように構成され、認識モジュール２２および集約モジュール２４の双方は、検索タームとタームが一致することが検索基準を満足するかどうかを決定するように協力してもよい。リザルトバッファ２５はパターン認識プロセッサ１４の他の部分からのリザルトデータをバッファリングしてもよく、これは図１３に関連して以下に説明される。
【００２２】
認識モジュール２２は、行デコーダ２８および複数のフィーチャセル３０を含んでもよい。各フィーチャセル３０は検索タームを特定し、フィーチャセル３０のグループは、検索基準を形成するパラレルな有限ステートマシンを形成してもよい。フィーチャセル３０のコンポーネントは、検索タームアレイ３２、検出アレイ３４およびアクティブ化ルーティングマトリクス３６を形成してもよい。検索タームアレイ３２は複数の入力導体３７を含み、入力導体３７の各々は、行デコーダ２８と連通する各フィーチャセル３０を配置してもよい。
【００２３】
行デコーダ２８は、データストリーム１２のコンテンツに基づいて、複数の入力導体３７中の特定の導体を選択してもよい。例えば、行デコーダ２８は、１タームを表現する可能性がある受信されたバイトの値に基づいて、２５６行のうちの１つをアクティブ化する１バイトから２５６への行デコーダであってもよい。００００００００の１バイトタームは、複数の入力導体３７のうち最も上の行に対応し、１１１１１１１１の１バイトタームは、複数の入力導体３７のうちの最も下の行に対応してもよい。したがって、異なる入力導体３７は、どのタームがデータストリーム１２から受信されるかに依存して選択されてもよい。異なるタームが受信されると、行デコーダ２８は、前のタームに対応する行を非アクティブ化し、新規タームに対応する行をアクティブ化してもよい。
【００２４】
検出アレイ３４は、検索基準を完全にもしくは部分的に満足することを示す信号を集約モジュール２４に対して出力する検出バス３８に結合してもよい。アクティブ化ルーティングマトリクス３６は、一致した検索基準における検索ターム数に基づいて、フィーチャセル３０を選択的にアクティブ化する、ならびに非アクティブ化してもよい。
【００２５】
集約モジュール２４は、ラッチマトリクス４０、集約ルーティングマトリクス４２、閾値論理マトリクス４４、論理積マトリクス４６、論理和マトリクス４８および初期化ルーティングマトリクス５０を含んでもよい。
【００２６】
ラッチマトリクス４０は、ある検索基準の一部を実施してもよい。例えば、幾つかの正規表現などの幾つかの検索基準は、最初に一致（もしくは複数の一致）が発生したときのみ考慮する。ラッチマトリクス４０は、一致が生じたかどうかを記録するラッチを含んでもよい。検索基準が満足されたとき、もしくはそれ以上満足されないと判定された、すなわち、その検索基準が満足されるより前に前の検索タームを再度マッチングさせる必要があるとき、ラッチは初期化の間にクリアされ、動作中に定期的に再初期化されてもよい。
【００２７】
集約ルーティングマトリクス４２は、アクティブ化ルーティングマトリクス３６と類似した機能を果たしてもよい。集約ルーティングマトリクス４２は、検出バス３８における一致を示す信号を受信し、閾値論理マトリクス４４に接続する異なるグループ論理ライン５３へと信号を送信してもよい。集約ルーティングマトリクス４２は、検索基準が満足された、もしくはこれ以上満足されないと判定されたとき、検出アレイ３４の一部をリセットするために、検出アレイ３４へと初期化ルーティングマトリクス５０の出力を送信してもよい。
【００２８】
閾値論理マトリクス４４は、例えば、数を数える（カウントアップする）、または数を逆に数える（カウントダウンする）ように構成された３２ビットカウンタなどの、複数のカウンタを含んでもよい。閾値論理マトリクス４４は、初期カウントでロードされ、認識モジュールによって信号通知された一致時のカウント値から、カウントアップもしくはカウントダウンしてもよい。例えば、閾値論理マトリクス４４は、ある長さの文字列の単語が現れた数を数えてもよい。
【００２９】
閾値論理マトリクス４４の出力は、論理積マトリクス４６に対する入力であってもよい。論理積マトリクス４６は、“積”の結果（例えば、ブール論理における“ＡＮＤ”関数）を選択的に生成してもよい。論理積マトリクス４６は、正方行列として実施され、出力積の数は、閾値論理マトリクス４４からの入力ラインの数と同一であるか、または、論理積マトリクス４６は、出力とは異なる数の入力を有してもよい。結果として生じる積の値は、論理和マトリクス４８に対する出力であってもよい。
【００３０】
論理和マトリクス４８は、和（例えば、ブール論理における“ＯＲ”関数）を選択的に生成してもよい。論理和マトリクス４８もまた、正方行列として実施されるか、または、論理和マトリクス４８は、出力とは異なる数の入力を有してもよい。入力は論理積であるため、論理和マトリクス４８の出力は、論理積和（例えば、ブール論理での積和（ＳＯＰ）形）であってもよい。論理和マトリクス４８の出力は、初期化ルーティングマトリクス５０によって受信されてもよい。
【００３１】
初期化ルーティングマトリクス５０は、集約ルーティングマトリクス４２を介して、検出アレイ３４および集約モジュール２４の一部をリセットしてもよい。初期化ルーティングマトリクス５０は、正方行列として実行されるか、または、初期化ルーティングマトリクス５０は、出力とは異なる数の入力を有してもよい。初期化ルーティングマトリクス５０は、論理和マトリクス４８からの信号に応じて、例えば、検索基準が満足されたとき、または、検索基準がこれ以上満足されないと判定されたとき、パターン認識プロセッサ１４の他の部分を再初期化してもよい。
【００３２】
集約モジュール２４は、閾値論理マトリクス４４、集約ルーティングマトリクス４２、および論理和マトリクス４８の出力を受信する出力バッファ５１を含んでもよい。集約モジュール２４の出力は、出力バッファ５１から出力バス２６上のＣＰＵ２０（図１）へと伝送されてもよい。幾つかの実施形態においては、出力マルチプレクサは、これらのコンポーネント４２、４４および４８からの信号を多重化し、基準を満足したことを示す信号、もしくは検索タームの一致を示す信号をＣＰＵ２０（図１）へと出力してもよい。他の実施形態においては、パターン認識プロセッサ１４からのリザルトは、出力マルチプレクサを介して信号を伝送することなく報告されてもよいが、このことは、本明細書で記述されたあらゆる他の特性が省略される可能性がないことを示唆するものではない。例えば、閾値論理マトリクス４４、論理積マトリクス４６、論理和マトリクス４８もしくは初期化ルーティングマトリクス５０からの信号は、出力バス２６上をパラレルにＣＰＵへと伝送されてもよい。
【００３３】
図３は、検索タームセル５４として本明細書で称されるコンポーネントである、検索タームアレイ３２（図２）における単一のフィーチャセル３０の一部を示す。検索タームセル５４は、出力導体５６および複数のメモリセル５８を含んでもよい。各メモリセル５８は、出力導体５６および複数の入力導体３７の中の導体の一つの両方へと結合されてもよい。入力導体３７が選択されるのに応じて、各メモリセル５８は、格納された値を示す値を出力し、出力導体５６を介してデータを出力する。幾つかの実施形態においては、複数の入力導体３７は“ワード線”と称され、出力導体５６は“データ線”と称されてもよい。
【００３４】
メモリセル５８は、種々のタイプのメモリセルのうちのいずれを含んでもよい。例えば、メモリセル５８は、トランジスタとキャパシタを有するダイナミックランダムアクセスメモリ（ＤＲＡＭ）セルなどの揮発性メモリであってもよい。トランジスタのソースおよびドレインは、其々、キャパシタのプレートおよび出力導体５６へと接続され、トランジスタのゲートは入力導体３７のうちの一つへと接続されてもよい。揮発性メモリの別の実施例においては、各メモリセル５８は、スタティックランダムアクセスメモリ（ＳＲＡＭ）セルを含んでもよい。ＳＲＡＭセルは、入力導体３７の一つによって制御されるアクセストランジスタによって、出力導体５６へと選択的に結合された出力を有してもよい。メモリセル５８は、相変化メモリ（例えば、オボニックデバイス）、フラッシュメモリ、シリコン・酸化物・窒化物・酸化物・シリコン（ＳＯＮＯＳ）メモリ、磁気抵抗メモリもしくは他のタイプの不揮発性メモリなどの不揮発性メモリをも含んでもよい。メモリセル５８は、フリップフロップ、例えば、論理ゲートによって形成されたメモリセルをも含んでもよい。
【００３５】
図４および図５は、動作における検索タームセル５４の一実施例を示す。図４は、セルの検索タームに一致しないタームを受信する検索タームセル５４を示し、図５は、セルの検索タームに一致するタームを受信する検索タームセル５４を示す。
【００３６】
図４によって示されるように、検索タームセル５４は、メモリセル５８にデータを格納することによって、一つ以上のタームを検索するように構成されてもよい。メモリセル５８は、例えば図３において、データストリーム１２が提示する可能性のあるタームを各々表し、各メモリセル５８は文字“ａ”で開始し、数字“９”で終了する単一の文字もしくは数字を表す。検索タームを満足するタームを表すメモリセル５８は、第一の値を格納するようにプログラムされ、検索タームを満足するタームを表していないメモリセル５８は、異なる値を格納するようにプログラムされてもよい。示された実施例においては、検索タームセル５４は、文字“ｂ”を検索するように構成される。“ｂ”を表すメモリセル５８は、１もしくは論理的なハイを格納し、“ｂ”を表していないメモリセル５８は、０、もしくは論理的なロウを格納するようにプログラムされてもよい。
【００３７】
データストリーム１２からのタームを検索タームと比較するために、行デコーダ２８は、受信されたタームを表すメモリセル５８に結合された入力導体３７を選択してもよい。図４においては、データストリーム１２は、小文字の“ｅ”を示す。このタームは、８ビットＡＳＣＩＩコード形式でデータストリーム１２によって示され、行デコーダ２８は、行アドレスとしてこのバイトを解釈し、導体６０に電圧を印加することによって、導体６０上に信号を出力する。
【００３８】
それに応じて、導体６０によって制御されるメモリセル５８は、メモリセル５８が格納するデータを示す信号を出力し、その信号は出力導体５６によって伝送されてもよい。この場合には、文字“ｅ”は、検索タームセル５４によって特定されたタームのうちの一つではないため、検索タームとは一致せず、検索タームセル５４は０値を出力し、それは一致が見つからなかったことを示している。
【００３９】
図５においては、データストリーム１２は、文字“ｂ”を示す。再度、行デコーダ２８はこのタームをアドレスとして解釈し、行デコーダ２８は導体６２を選択してもよい。それに応じて、文字“ｂ”を表すメモリセル５８は、格納された値を出力し、この場合には、それは１であり、一致を示している。
【００４０】
検索タームセル５４は一度に一つ以上のタームを検索するように構成されてもよい。複数のメモリセル５８は、１を格納するようにプログラムされ、一つ以上のタームと一致する検索タームを特定する。例えば、小文字“ａ”および大文字“Ａ”を表すメモリセル５８は、１を格納するようにプログラムされ、検索タームセル５４は、いずれかのタームを検索してもよい。別の実施例においては、検索タームセル５４は、いかなる文字が受信された場合にも一致を出力するように構成されてもよい。全メモリセル５８は、１を格納するようにプログラムされてもよく、検索タームセル５４は、検索基準におけるワイルドカードタームとして機能してもよい。
【００４１】
図６−図８は、例えば一単語など複数ターム検索基準に従って検索する認識モジュール２２を示す。具体的には、図６は一単語の最初の文字を検出する認識モジュール２２を示し、図７は、第二の文字の検出を示し、図８は、最後の文字の検出を示す。
【００４２】
図６によって示されるように、認識モジュール２２は、単語“ｂｉｇ”を検索するように構成されてもよい。３個の隣接するフィーチャセル６３、６４および６６が示される。フィーチャセル６３は、文字“ｂ”を検出するように構成される。フィーチャセル６４は、文字“ｉ”を検出するように構成される。フィーチャセル６６は、文字“ｇ”を検出し、検索基準が満足されたことを示すように構成される。
【００４３】
図６は、検出アレイ３４のさらなる詳細をも示す。検出アレイ３４は、各フィーチャセル６３、６４および６６における検出セル６８を含んでもよい。各検出セル６８は、上述されたタイプのメモリセルのうちの一つ（例えば、フリップフロップ）のような、メモリセル７０を含んでもよく、メモリセル７０は、フィーチャセル６３、６４もしくは６６がアクティブか非アクティブかを示す。検出セル６８は、両方の検出セルがアクティブであり、一致を示す関連付けられた検索タームセル５４から信号を受信したかどうかを示す信号を、アクティブ化ルーティングマトリクス３６へと出力するように構成されてもよい。非アクティブなフィーチャセル６３、６４および６６は、一致を無視してもよい。各検出セル６８は、メモリセル７０および出力導体５６からの入力を有する、ＡＮＤゲートを含んでもよい。ＡＮＤゲートの出力は、検出バス３８およびアクティブ化ルーティングマトリクス３６の両方へ、またはそのどちらか一方へと送信されてもよい。
【００４４】
今度は、アクティブ化ルーティングマトリクス３６は、検出アレイ３４におけるメモリセル７０へと書き込むことによって、フィーチャセル６３、６４および６６を選択的にアクティブ化してもよい。アクティブ化ルーティングマトリクス３６は、検索基準ならびに次にどの検索タームがデータストリーム１２において検索されるかに従って、フィーチャセル６３、６４もしくは６６をアクティブ化してもよい。
【００４５】
図６においては、データストリーム１２は文字“ｂ”を示す。それに応じて、各フィーチャセル６３、６４および６６は、その出力導体５６上に信号を出力し、文字“ｂ”を表す導体６２に接続されたメモリセル５８に格納された値を示す。検出セル５６は、その後、一致を示す信号を受信したかどうか、ならびに検出セル５６がアクティブかどうかを各々決定してもよい。フィーチャセル６３は文字“ｂ”を検出するように構成され、そのメモリセル７０によって示されるようにアクティブであるため、フィーチャセル６３における検出セル６８は、アクティブ化ルーティングマトリクス３６へと信号を出力して、検索基準のうちの第一の検索タームが一致したことを示す。
【００４６】
図７によって示されるように、第一の検索タームが一致した後、アクティブ化ルーティングマトリクス３６は、検出セル６８におけるメモリセル７０へと１を書き込むことによって、次のフィーチャセル６４をアクティブ化してもよい。次のタームが第一の検索タームを満足する場合（例えば、タームの配列“ｂｂｉｇ”が受信された場合）アクティブ化ルーティングマトリクス３６はフィーチャセル６３のアクティブ状態を維持してもよい。検索基準のうちの第一の検索タームは、データストリーム１２が検索される時間のうちの一部もしくは実質的に全期間の間、アクティブ状態に維持されてもよい。
【００４７】
図７においては、データストリーム１２は認識モジュール２２へ文字“ｉ”を出力する。それに応じて、各フィーチャセル６３、６４および６６は、その出力導体５６上に信号を出力し、文字“ｉ”を表す導体７２へと接続されたメモリセル５８に格納された値を示す。検出セル５６は、その後、一致を示す信号を受信したかどうか、ならびに検出セル５６がアクティブかどうかを各々決定してもよい。フィーチャセル６４は文字“ｉ”を検出するように構成され、メモリセル７０によって示されるようにアクティブであるため、フィーチャセル６４における検出セル６８は、アクティブ化ルーティングマトリクス３６へと信号を出力し、検索基準の次の検索タームが一致したことを示す。
【００４８】
続いて、図８に示されるように、アクティブ化ルーティングマトリクス３６はフィーチャセル６６をアクティブ化してもよい。次のタームを評価する前に、フィーチャセル６４は非アクティブ化されてもよい。フィーチャセル６４は、その検出セル６８によって非アクティブ化され、検出周期の間そのメモリセル７０をリセットするか、または、例えば、アクティブ化ルーティングマトリクス３６はフィーチャセル６４を非アクティブ化してもよい。
【００４９】
図８においては、データストリーム１２は行デコーダ２８へと、ターム“ｇ”を出力し、行デコーダ２８はターム“ｇ”を表す導体７４を選択する。それに応じて、各フィーチャセル６３、６４および６６は、その出力導体５６上に信号を出力し、文字“ｇ”を表す導体７４へと接続されたメモリセル５８に格納された値を示す。検出セル５６は、その後、一致を示す信号を受信したかどうか、ならびに検出セル５６がアクティブかどうかを各々決定してもよい。フィーチャセル６６は文字“ｇ”を検出するように構成され、そのメモリセル７０によって示されるようにアクティブであるため、フィーチャセル６６における検出セル６８は、アクティブ化ルーティングマトリクス３６へと信号を出力し、検索基準の最後の検索タームが一致したことを示す。
【００５０】
検索基準の終わりもしくは検索基準の一部は、アクティブ化ルーティングマトリクス３６もしくは検出セル６８によって識別されてもよい。これらのコンポーネント３６もしくは６８は、そのフィーチャセル６３、６４もしくは６６が検索基準の最終検索タームか検索基準のコンポーネントかを識別するかを示すメモリを含んでもよい。例えば、検索基準は、“ｃａｔｔｌｅ”という単語が二度現れる全ての文を特定し、認識モジュールは、“ｃａｔｔｌｅ”の出現回数を数える集約モジュールへと、文内の各々の“ｃａｔｔｌｅ”の出現を示す信号を出力し、検索基準が満足されたかどうかを判定する。
【００５１】
フィーチャセル６３、６４もしくは６６は幾つかの条件下でアクティブ化されてもよい。フィーチャセル６３、６４もしくは６６は、“常にアクティブ”であってもよく、それは、全検索の間、もしくは実質的に全ての検索の間アクティブ状態のままであることを意味する。常にアクティブなフィーチャセル６３、６４もしくは６６の一実施例は、検索基準の第一のフィーチャセル、例えば、フィーチャセル６３である。
【００５２】
フィーチャセル６３、６３もしくは６６は、“要求されたときアクティブ”であってもよく、それは、幾つかの先行する条件が一致したとき、例えば、検索基準における先行する検索タームが一致したときに、フィーチャセル６３、６４もしくは６６がアクティブであることを意味する。一実施例は、図６−図８におけるフィーチャセル６３によって要求されたときにアクティブであるフィーチャセル６４と、フィーチャセル６４によって要求されたときにアクティブであるフィーチャセル６６である。
【００５３】
フィーチャセル６３、６４もしくは６６は、“自己アクティブ化”されてもよく、それは、一度アクティブ化されればその検索タームが一致している限り、それ自身をアクティブ化することを意味する。例えば、いかなる数のディジットにでも一致した検索タームを有する自己アクティブ化されたフィーチャセルは、文字“ｘ”に到達するまで、文章“１２３４５６ｘｙ”をアクティブ化したままであってもよい。自己アクティブ化されたフィーチャセルの検索タームが一致するたび、自己アクティブ化されたフィーチャセルは検索基準における次のフィーチャセルをアクティブ化してもよい。したがって、常にアクティブなフィーチャセルは、自己アクティブ化するフィーチャセルおよび要求されたときにアクティブなフィーチャセルから形成されてもよい。自己アクティブ化フィーチャセルは、１を格納するメモリセル５８の全てにプログラムされてもよく、各ターム後に要求されたときアクティブなフィーチャセルを繰り返しアクティブ化してもよい。幾つかの実施形態においては、各フィーチャセル６３、６４および６６は、フィーチャセルが常にアクティブかどうかを識別する検出セル６８もしくはアクティブ化ルーティングマトリクス３６におけるメモリセルを含んでもよく、それによって、単一のフィーチャセルから常にアクティブなフィーチャセルを形成する。
【００５４】
図９は、第一の検索基準７５および第二の検索基準７６に従ってパラレルに検索するように構成された認識モジュール２２の一実施例を示す。本実施例においては、第一の検索基準７５は、単語“ｂｉｇ”を識別し、第二の検索基準７６は、単語“ｃａｂ”を識別する。データストリーム１２からの現在のタームを示す信号は、ほぼ同時に各検索基準７５および７６におけるフィーチャセルへと通信されてもよい。各入力導体３７は、検索基準７５および７６の双方へと及ぶ。結果として、幾つかの実施形態においては、検索基準７５および７６の双方は、ほぼ同時に現在のタームを評価してもよい。このことによって、検索基準の評価が加速すると考えられる。他の実施形態は、より多くの検索基準をパラレルに評価するように構成されたより多くのフィーチャセルを含んでもよい。例えば、幾つかの実施形態は、パラレルに動作する１００、５００、１０００、５０００もしくは１００００以上のフィーチャセルを含んでもよい。これらのフィーチャセルは、ほぼ同時に何百、もしくは何千もの検索基準を評価してもよい。
【００５５】
異なる数の検索タームを有する検索基準は、より多くのもしくはより少ないフィーチャセルを検索基準へと割り当てることによって形成されてもよい。単純な検索基準は、フィーチャセルの形式で、複雑な検索基準よりも、より少ないリソースを消費してもよい。このことによって、ほぼ同一の多数のコアを有し、複雑な検索基準を評価するように全て構成されたプロセッサと比較して、パターン認識プロセッサ１４（図２）のコストを低減すると考えられる。
【００５６】
図１０−図１２は、アクティブ化ルーティングマトリクス３６のより複雑な検索基準とフィーチャの一実施例の双方を示す。アクティブ化ルーティングマトリクス３６は、複数のアクティブ化ルーティングセル７８を含んでもよく、アクティブ化ルーティングセル７８のグループは、各フィーチャセル６３、６４、６６、８０、８２、８４および８６に関連付けられてもよい。例えば、各フィーチャセルは、５、１０、２０、５０もしくはそれ以上のアクティブ化ルーティングセル７８を含んでもよい。アクティブ化ルーティングセル７８は、先行する検索タームが一致するとき、検索基準における次の検索タームへとアクティブ化信号を送信するように構成されてもよい。アクティブ化ルーティングセル７８は、同一のフィーチャセル内の隣接するフィーチャセルもしくは他のアクティブ化ルーティングセル７８へとアクティブ化信号を送信するように構成されてもよい。アクティブ化ルーティングセル７８は、どのフィーチャセルが検索基準における次の検索タームに対応するかを示すメモリを含んでもよい。
【００５７】
図１０−図１２に示されるように、認識モジュール２２は、単一の単語を特定する基準よりも複雑な検索基準に従って検索するように構成されてもよい。例えば、認識モジュール２２は、接頭辞８８で開始し、２つの接尾辞９０もしくは９２のうちの一つで終了する単語を検索するように構成されてもよい。示された検索基準は、文字“ｃ”および“ｌ”の配列で開始し、文字配列“ａｐ”もしくは文字配列“ｏｕｄ”のいずれかで終了する単語を特定する。これは、複数の対象表現、例えば、単語“ｃｌａｐ”もしくは単語“ｃｌｏｕｄ”を特定する検索基準の一実施例である。
【００５８】
図１０においては、データストリーム１２は、認識モジュール２２に対して文字“ｃ”を示し、フィーチャセル６３は両方アクティブであり、一致を検出する。それに応じて、アクティブ化ルーティングマトリクス３６は、次のフィーチャセル６４をアクティブ化してもよい。アクティブ化ルーティングマトリクス３６は、フィーチャセル６３が検索基準における第一の検索タームであるとき、フィーチャセル６３のアクティブ状態を維持してもよい。
【００５９】
図１１においては、データストリーム１２は、文字“ｌ”を示し、フィーチャセル６４は、一ｘ致を認識してアクティブである。それに応じて、アクティブ化ルーティングマトリクス３６は、第一の接尾辞９０の第一のフィーチャセル６６および第二の接尾辞９２の第一のフィーチャセル８２の双方へとアクティブ化信号を伝送してもよい。他の実施例においては、より多くの接尾辞がアクティブ化されてもよく、または、複数の接頭辞は一つ以上の接尾辞をアクティブ化してもよい。
【００６０】
続いて、図１２においては、データストリーム１２は、認識モジュール２２に対して文字“ｏ”を示し、第二の接尾辞９２のフィーチャセル８２は、一致を認識してアクティブである。それに応じて、アクティブ化ルーティングマトリクス３６は、第二の接尾辞９２の次のフィーチャセル８４をアクティブ化してもよい。フィーチャセル６６が非アクティブになると認められると、第一の接尾辞９０の検索は終了してもよい。図１０−図１２に示されたステップは、文字“ｕ”および“ｄ”へと継続してもよいし、または、接頭辞８８が一致する次の機会まで、検索は終了してもよい。
【００６１】
図１３は、他のパターン認識プロセッサ９３の例を示す。パターン認識プロセッサ９３は、図２のパターン認識プロセッサ１４に関して上述したのと実質的に同様の方法で動作してよい。しかしながら、パターン認識プロセッサ９３は、図２のパターン認識プロセッサ１４と共通の構成部分に加えて、閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および初期化出力マスク１００をさらに含んでよい。
【００６２】
閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および初期化出力マスク１００は一般に、入力として受信される一つ以上の結果を、“マスク”し、換言すればフィルタ処理する。例えば、閾値論理マトリクス４４は、データストリーム１２における例えばセキュリティの脅威などの全ての既知の出現事象に対して検索をするように設定されてよい。しかしながら、特定のハイリスク脅威のような一つ以上の特定のセキュリティ脅威に対しては、これらの結果をフィルタ処理することが有益であろう。従って、閾値出力マスク９４は、特定のハイリスクセキュリティ脅威を除いては、閾値論理４４によって発見される全てのセキュリティ脅威をブロックするように設定されてよい。もしこのハイリスクセキュリティ脅威が発見されたならば、ＣＰＵによって取り出されるようにするために、脅威に対する通知が閾値出力マスク９４から出力バッファ５１に伝送されてよい。このようにして、閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および初期化出力マスク１００は、それぞれがパターンマッチングマトリクス４４−５０の全体の結果出力から一つ以上の特定の結果を分けるために、それぞれのマトリクス４４−５０の出力をフィルタ処理できるマスクモジュールを形成してよい。幾つかの実施形態において、出力マスクモジュール９４−１００は、そのようなフィルタリングを容易にするために、パターンマッチングマトリクス４４−５０の出力に関連するマスクレジスタを用いてよい。
【００６３】
従って、閾値出力マスク９４は、閾値論理マトリクス４４の結果に基づいて検索結果照合（一致、マッチ）を生成するように動作してよい。上述したように、閾値論理マトリクス４４は、認識モジュールにより通知された照合に基づいてカウントアップまたはダウンするように構成される例えば３２ビットカウンタである複数のカウンタを含んでよい。閾値論理マトリクス４４は、データ列中で発見された３つの“Ａ”シンボルのようないくらかの長さのテキストにおける単語の発生数を計数してよい。閾値論理マトリクス４４からの結果は、閾値出力マスク９４、出力バッファ５１、および論理積マトリクス４６に送られてよい。閾値出力マスク９４は、閾値論理マトリクス４４によって決定される閾値結果を使用して追加の照合検索を実行してよい。この追加の照合検索は、例えば閾値出力マスク９４中のビット配置を使って閾値論理マトリクス４４によって決定される閾値結果に対する“アンド演算（ＡＮＤ−ｉｎｇ）”を含んでよい。
【００６４】
例えば、閾値結果は、各ラインが特定の結果に対応してよい例えば３２ラインの閾値出力マスク９４に送られてよい。これらのラインの各々はまた、１または０のいずれかにセットされてよい、閾値出力マスク９４内の対応するビット配置を有してよい。そのセットされる値は、そのビット配置に対応するライン上で受信された結果が閾値出力マスク９４によって選択されるものであるか否かに依存する。このようにして、１にセットされた閾値出力マスク９４内の任意のビット配置に対して、閾値論理マトリクス４４からの対応する結果ラインに沿って受信された任意の情報が、閾値出力マスク９４から出力バッファ５１に伝送されてよい。同様にして、０にセットされた閾値出力マスク９４内の任意のビット配置に対して、閾値論理マトリクス４４からの対応するラインに沿って受信された任意の情報が、マスクされ、換言すればフィルタ処理され、従って、閾値出力マスク９４から出力バッファ５１に伝送されないようにしてよい。このようにして、閾値出力マスク９４は、どの閾値論理マトリクス４４の結果（例えば閾値出力マスク９４中の有効にされたビット配置に対応するもの）を出力バッファ５１に流し、どの閾値論理マトリクス４４の結果（例えば閾値出力マスク９４中の有効にされたビット配置に対応するもの）を無視するかを、効果的に選択してよい。上述の考察は、閾値出力マスク９４を介したハードウェア照合について説明することを示してきたが、上述のものと同様に機能的に動作する閾値マスクプログラムを用いたソフトウェア照合が使用されてもよいことに留意されたい。
【００６５】
積出力マスク９６は、論理積マトリクス４６の結果に基づいて検索結果照合を生成するように動作してよい。論理積マトリクス４６は、２つ以上の閾値論理マトリクス４４結果に基づいて、“積”の結果（例えば、ブール論理における“ＡＮＤ”関数）を選択的に生成してよい。例えば、論理積マトリクス４６は３つの“Ａ’ｓ”とターム“ｃａｔ”の両方を検索してよい。論理積マトリクス４６からの結果は、積出力マスク９６、出力バッファ５１、および論理和マトリクス４８に流されてよい。積出力マスク９６は、論理積マトリクス４６により決定された積の結果を使用して追加の照合検索を実行してよい。この追加の照合検索は、例えば閾値出力マスク９４内のビット配置を用いて論理積マトリクス４６によって決定される結果に対する“アンド演算（ＡＮＤ−ｉｎｇ）”を含んでよい。
【００６６】
例えば、論理積マトリクス４６の積の結果は、各ラインが特定の結果に対応してよい例えば３２ラインに沿って積出力マスク９６に流されてよい。これらのラインの各々はまた、１または０のいずれかがセットされてよい積出力マスク９６内の対応するビット配置を有してよい。そのセットされる値は、そのビット配置に対応するライン上で受信された結果が積出力マスク９６によって選択されるべきものであるか否かに依存する。このようにして、１にセットされた積出力マスク９６内の任意のビット配置に対して、論理積マトリクス４６からの対応する結果ラインに沿って受信された任意の情報が、積出力マスク９６から出力バッファ５１に伝送されてよい。同様にして、０にセットされた積出力マスク９６内の任意のビット配置に対して、論理積マトリクス４６からの対応するラインに沿って受信された任意の情報が、マスクされ、換言すればフィルタ処理され、従って、積出力マスク９６から出力バッファ５１に伝送されないようにしてよい。このようにして、積出力マスク９６は、どの論理積マトリクス４６の結果（例えば積出力マスク９６中の有効にされたビット配置に対応するもの）を出力バッファ５１に流し、どの論理積マトリクス４６の結果（例えば積出力マスク９６中の有効にされたビット配置に対応するもの）を無視するかを、効果的に選択してよい。上述の考察は、積出力マスク９６を介したハードウェア照合について説明することを示してきたが、上述のものと同様に機能的に動作する閾値マスクプログラムを用いたソフトウェア照合が使用されてもよいことに留意されたい。
【００６７】
和出力マスク９８は、閾値出力マスク９４および積出力マスク９６を用いて上述したのと類似の方法で、論理和マトリクス４８の結果に基づいて検索結果照合を生成するように動作してよい。論理和マトリクス４８は、“和”の結果（例えば、ブール論理における“ＯＲ”関数）を選択的に生成してよく、あるいは、論理積入力結果に基づいて、論理積和（例えば、ブール論理での積和（ＳＯＰ）形）を創り出してもよい。例えば、論理和マトリクス４８は、３つの“Ａ’ｓ”とターム“ｃａｔ”の両方または３つの“Ｎ’ｓ”とターム“ｄｏｇ”、を検索してよい。論理和マトリクス４８からの結果は、和出力マスク９８、出力バッファ５１、および初期化ルーティングマトリクス５０に送られてよい。
【００６８】
そのような和の結果は、和出力マスク９８によって一組の出力結果ラインに沿って受信されてよい。これらのラインの各々はまた、１または０のいずれかがセットされてよい和出力マスク９８内の対応するビット配置を有してよい。そのセットされる値は、そのビット配置に対応するライン上で受信された結果が和出力マスク９８によって選択されるべきものであるか否かに依存する。従って、１にセットされた和出力マスク９８内の任意のビット配置に対して、論理和マトリクス４８からの対応する結果ラインに沿って受信された任意の情報が、和出力マスク９８から出力バッファ５１に伝送されてよい。同様にして、０にセットされた和出力マスク９８内の任意のビット配置に対して、論理和マトリクス４８からの対応する結果ラインに沿って受信された任意の情報が、マスクされ、換言すればフィルタ処理され、従って、和出力マスク９８から出力バッファ５１に伝送されないようにしてよい。このようにして、和出力マスク９８は、どの論理和マトリクス４８の結果（例えば和出力マスク９８中の有効にされたビット配置に対応するもの）を出力バッファ５１に流し、どの論理和マトリクス４８の結果（例えば和出力マスク９８中の有効にされたビット配置に対応するもの）を無視するかを、効果的に選択してよい。上述の考察は、和出力マスク９８を介したハードウェア照合について説明することを示してきたが、上述のものと同様に機能的に動作する閾値マスクプログラムを用いたソフトウェア照合が使用されてもよいことに留意されたい。
【００６９】
初期化出力マスク１００は、初期化ルーティングマトリクス５０の初期化結果に基づく結果を生成するように動作してよい。初期化ルーティングマトリクス５０は、論理和マトリクス４８からの結果に基づいて、検出アレイ３４および／または集約ルーティングマトリクス４２を介して集約モジュール２４の一部を選択的にリセットしてよい。初期化ルーティングマトリクス５０はまた、検索基準が満足されまたはそれ以上満足されないと決定されたときのような場合に、パターン認識プロセッサ１４の他の部分を再初期化してもよい。これらの初期化結果は、出力バッファ５１および初期化出力マスク１００に流される。
【００７０】
初期化出力マスク１００は、初期化ルーティングマトリクス５０によって決定される初期化結果を利用して追加の照合検索を実行してよく、それによって第２の条件付きのリセットが生成されてもよい。この追加的なリセットは、例えば検出アレイ３４または集約ルーティングマトリクス４２を介した集約モジュール２４の初期化出力マスク１００によるリセットのための第２の条件を用いて、初期化ルーティングマトリクス５０によって決定される初期化結果に対する“アンド演算（ＡＮＤ−ｉｎｇ）”によって生成されてもよい。この第２の条件は初期化出力マスク１００内の一つ以上のアクティブ化されたビット配置であってよく、それによりそのビット配置は初期化ルーティングマトリクス５０からの一つ以上の結果ラインに対応する。初期化出力マスク１００内の与えられたビット配置は１または０のいずれかにセットされてよい。そのセットされる値は、そのビット配置に対応するライン上で受信された結果が初期化出力マスク１００によって選択されるべきものであるか否かに依存する。この結果、どの初期化ルーティングマトリクス５０の結果を出力バッファ５１に流し、どの初期化ルーティングマトリクス５０の結果を無視するかを効果的に選択できる。さらに、初期化出力マスク１００は、ハードウェアを介して、または、例えば上述のハードウェア実装と同様に機能的に動作する初期化マスクプログラムを用いたソフトウェアを介して、実装されてよい。
【００７１】
従って、出力バッファ５１は、閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および初期化出力マスク１００の出力と同様に、閾値論理マトリクス４４、論理積マトリクス４６、論理和マトリクス４８、および初期化ルーティングマトリクス５０の出力を受信してよい。出力バッファ５１は、結果バッファ２５とともに、出力バス２６を介した出力の伝送に先立って、その出力のためのバッファとして動作してよい。さらに、これらの結果の出力バッファ５１への書込みは、同時に、換言すれば並列に実行されてよい。
【００７２】
図１４は、パターン認識プロセッサ１４またはパターン認識プロセッサ９３に結合されるリザルト（結果）バッファ２５の例を示す。図２および図１３に関連して上述したように、リザルトバッファ２５は、出力バッファ５１に含まれてよい。結果バッファ２５は、ファースト−インファースト−アウト（ＦＩＦＯ）バッファ１０２、バッファ書込み制御モジュール１０４、バッファ読出し制御モジュール１０６、およびバッファ設定モジュール１０８を含んでよい。リザルトバッファ２５は、パターン認識プロセッサ１４の一部として（例えばシリコンの同一ボディー上に）完全に形成されてよく、あるいはそれは別々の構成部品または別々の構成部品の一部であってもよい。リザルトバッファ２５は、上りリザルトバス１１０を通してパターン認識プロセッサ１４からリザルトデータを受信してよく、また、リザルトバッファ２５は、下りリザルトバス１１２を通してＣＰＵ２０（図１）にリザルトデータを出力してよい。設定バス１１４は、ＣＰＵ２０を、リザルトバッファ２５内のバッファ設定モジュール１０８およびパターン認識プロセッサ１４を設定するのに使用してよいパターン認識プロセッサ設定モジュール１１６と通信する状態に置いてよい。
【００７３】
ＦＩＦＯバッファ１０２は、複数のレコード１１８を記憶するように構成されてよい。各レコード１１８は例えば基準の充足に関連するデータであるリザルトデータを記憶してよい。各レコード１１８は一つの基準を満足させる一つのインスタンスと一致してよく、あるいは、基準を満足させることに関連するデータは例えば幾つかの隣接する、さもなくば連続的なレコード１１８である幾つかのレコード１１８に記憶されてよい。
【００７４】
各レコード１１８はリザルトステータス情報１２０，ハウスキーピング情報１２２，およびリザルトデータ１２４を記憶するためのフィールドを含んでよい。他の実施形態は、追加的なフィールドまたはより少ないフィールドを含んでよい。リザルトステータスフィールド１２０はデータストリーム１２を識別しデータストリーム１２をパターン認識プロセッサ１４が受信するかもしれない他のデータストリームから区別するデータを記憶してよい。
【００７５】
ハウスキーピングフィールド１２２は基準が満足されたときにパターン認識プロセッサ１４のステータスを表示するデータを記憶してよい。例えば、ハウスキーピングフィールド１２２は、エラー状態が発生したか否かを指し示すデータを記憶してよい。エラー状態の例は、入力データオーバーフローまたはＦＩＦＯバッファフル状態を含む。ＦＩＦＯバッファ１０２は、例えば、約３２レコード以上、約６４レコード以上、約１２８レコード以上、約２５６レコード以上、または約５１２レコード以上を含んでよい。
【００７６】
リザルトデータ１２４は、どの基準が満足されたのか、基準を満足させたデータストリーム１２からのタームのシーケンス、基準を満足させたデータストリーム１２の部分を示すタームカウント（例えばビットカウント）、またはその間基準を満足させたデータストリームの部分が受信された時間間隔のようなデータを含んでよい。各レコード１１８に記憶されたリザルトデータ１２４は、バンクとして分類される。このバンクは、閾値論理マトリクス４４、論理積マトリクス４６、論理和マトリクス４８、初期化ルーティングマトリクス５０、閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および／または初期化出力マスク１００の各々からの照合結果出力の各々の記憶装置のための個々のレジスタを含んでよい。さらに、照合結果出力は、並列にレジスタバンクに書き込まれてよい。この方法において、各レコード１１８のためのリザルトデータ１２４、換言すれば照合データは、受信されてレジスタバンクに同時に記憶されてよい。そこによって、各々個別のレジスタは、特にそのマトリクスまたはマスクからの明示された結果を個別に記憶してよい。
【００７７】
バッファ書込み制御モジュール１０８は、上りリザルトバス１１０からのどのデータがＦＩＦＯバッファ１０２中のどのレコード１１８に書き込まれるかを制御するように構成されてよい。バッファ書込み制御モジュール１０２は、基準が満足されるごとにまたはリザルトデータが新しいレコード１１８に書き込まれるごとにインクリメントまたはデクリメントするカウンタを含んでよい。バッファ書込み制御モジュールはまた、どのレコード１１８が最も最近にＣＰＵ２０に出力されたかを示すメモリを含んでよく、バッファ書込み制御モジュール１０４は、上りリザルトバス１１０からのデータを、すでにＣＰＵ２０に伝えられたデータを含むレコード１１８に書き込むように構成されてよい。
【００７８】
同様に、バッファ読出し制御モジュール１０６は、どのレコード１１８がＦＩＦＯバッファ１０２から読み出されていない最も古いレコードであるかを指し示すように構成されてよい。例えば、バッファ読出し制御モジュール１０６はレコードがＦＩＦＯバッファから読み出されるごとにインクリメントまたはデクリメントするカウンタを含んでよく、そのカウンタのカウントは最も古く読まれていないレコード１１８を識別してよい。バッファ読出し制御モジュール１０６は、ＣＰＵ２０からの読出し命令信号１２６を受信し、ＦＩＦＯバッファ１０２に対して最も古く読まれていないレコード１１８により記憶されたデータを出力させることによりその読出し命令に応答するように構成されてよい。
【００７９】
リザルトバス１１２は、下りリザルトバス１１２がデータを出力しているのと同時にデータストリーム１２がデータを入力するように、データストリーム１２を伝搬するバスとは異なる導体を含んでよい。リザルトバッファ２５がパターン認識プロセッサ１４と完全に一体に形成される実施形態では、パターン認識プロセッサ１４はデータストリーム１２入力と結果出力を伝搬するための個別のピンを含んでよい。従って、リザルトデータはデータストリームが入力されるのと同時に出力されてよい。
【００８０】
代わりに、リザルトバス１１２は、同じ導体またはピンを使用して、要するに共有バスを使用して、データストリーム１２を受信しリザルトデータを出力してよい。例えば、その共有バスは、その共有バスが同じ導体によって使用されてデータストリーム１２を受信しリザルトデータを出力できるように、多重化されまたはタイムスライス化されてよい。しかしながら、その共有バスが入力データを伝送するように使用される時間は、その共有バスが出力データを伝送するのに使用される時間を超えており、そのようにして出力サイクルよりも多くの入力サイクルが生み出されている。そのようにして、入力サイクルはその共有バスの多重化の間、最高の優先度が与えられてよい。出力サイクルは、時間の許す限り、入力サイクルとして使用されていないタイムスロットに続いてはめ込まれてよい。
【００８１】
動作については、パターン認識プロセッサ１４は、図２−図１３を参照して上述した方法で、データストリーム１２を検索してよく、その検索からの結果はＣＰＵ２０に伝搬される前にリザルトバッファ２５にバッファリングされてよい。基準が満たされたとき、どの基準が満たされたのかを示すデータ、データストリーム１２中のどのタームがその基準を満たしたのかを示すデータ、およびどのデータストリームが検索されたのかを示すデータのような、その基準の充足に関連するデータが、上りリザルトバス１１０を通してリザルトバッファ２５に伝送されてよい。
【００８２】
このデータの受信において、バッファ書込み制御モジュール１０４は、例えば、記憶データをすでにＣＰＵ２０に伝搬されているレコード１１８またはどのデータも記憶していないレコード１１８である幾つかのフリーレコードがＦＩＦＯバッファ１０２内にあるか否かを決定してよい。もしフリーレコードが利用可能でなければ、バッファ書込み制御モジュール１０４は、パターン認識プロセッサ１４に通知してデータストリーム１２を検索することを停止させ、ＣＰＵ２０はＦＩＦＯバッファ１０２中のレコードを通じて動作するので空き時間を創り出してしまうが、ＣＰＵ２０に通知してデータストリーム１２の伝送を休止させてよい。バッファ書込み制御モジュール１０４はまた、現在のまたはその次のレコードのハウスキーピング情報フィールド１２２に、パターン認識プロセッサ１４がリザルトバッファオーバーフロー状態に入ったことを示すデータを記憶させてよい。
【００８３】
バッファ書込み制御モジュール１０４が少なくとも一つのフリーレコード１１８が利用可能であると決定したならば、バッファ書込み制御モジュール１０４は、上りリザルトデータバス１１０からのリザルトデータをそのフリーレコード１１８に書き込んでよい。バッファ書込み制御モジュール１０４は、そのレコード１１８が書き込みが行われたがまだ読出しは行われていないことを示してよく、バッファ書込み制御モジュール１０４は、そのレコード１１８が他の書き込まれたレコードと比較して最新のレコードであることを示してよい。
【００８４】
実質的に同じ時間または他の時間において、ＣＰＵ２０は読出し制御信号１２６をバッファ読出し制御モジュール１０６に送信し、それによってバッファ読出し制御モジュール１０６に対してまだ未読の最も古いレコード１１８内のデータを出力するように通知してよい。このようにして、ＣＰＵ２０は重要なステータスレジスタに対して“ポーリング”して、例えばＣＰＵ２０への伝送のために新しいレコード１１８が利用可能であるか否かを決定してよい。ＣＰＵ２０によるポーリングは、リザルトバッファ２５の内部または外部のいずれかの一つ以上のステータスビットがセットされたか否かの、ＣＰＵ２０を介した決定を生ずる。一つ以上のステータスビットのセッティングは、新たなパターンマッチリザルトデータがＣＰＵ２０による読出しのために利用可能であることを指し示してよい。
【００８５】
バッファ読出し制御モジュール１０６はまた、いくつかの未読のレコード１１８が存在するか否かを決定してよい。未読レコードが存在しないならば、バッファ読出し制御モジュール１０６はＣＰＵ２０に対して目下のところ未読レコードは無いことを通知する。もし未読のレコード１１８が存在するならば、バッファ読出し制御モジュール１０６は、最も古い未読レコードを識別し、その最も古い未読のレコード１１８によって記憶されたデータをＣＰＵ２０に伝搬してよい。これは、ＣＰＵ２０が新たな結果が利用可能であるか否かを“質問”する“ポーリング”方法を構成する。
【００８６】
他の方法として、“割込み処理”が、ＣＰＵ２０が与えられた照合を通知するアクティブ通知方法を構成してよい。この方法において、バッファ読出し制御モジュール１０６は、下りリザルトバス１１２を通じてＣＰＵ２０に、ＣＰＵ２０に通知をしおよび／または割込みを行う通知信号をアクティブに伝送し、これによりＣＰＵ２０に対して一つ以上の利用可能レコード１１８が利用できることを認識させてよい。割込み線（図示していないが、下りリザルトバス１１２の一部とみなされる）が、その通知信号をＣＰＵ２０に伝送するために使用されてよい。
【００８７】
他の実施形態において、バッファ読出し制御モジュール１０６は、最も古い未読のレコード１１８によって記憶されているデータの一部を伝搬してよい。それは例えば、基準が満たされたというデータである。そして、ＣＰＵ２０はそのレコード１１８によって記憶されているデータをより多く要求するか否かを決定してよい。それは例えば、データストリーム１２からのどのタームがその基準を満たしたかというデータである。ＣＰＵ２０は、レコード１１８を終了したとき、バッファ読出し制御モジュール１０６に、そのレコードがもはや必要ないことを通知する。バッファ読出し制御モジュール１０６は、それで、そのレコードが読出しが行われてバッファ書込み制御モジュール１０４によって上書きされても安全であることを示してよい。
【００８８】
リザルトバッファはまた、検索結果処理によって生ずる遅延を減少させる。ＣＰＵ２０が検索結果を受信しまたは処理できるよりも速くデータストリーム１２が検索基準を満たすとき、リザルトバッファ２５は、ＣＰＵ２０が追いつくまでの間、未処理のリザルトデータを記憶してよい。リザルトバッファ２５は、たとえ幾つかの検索基準がほぼ同時に満たされたとしても、ＣＰＵ２０へのリザルトデータの流れをスムーズ化することができ、その結果、ＣＰＵ２０がリザルトバッファ２５によって記憶された検索結果のバックログ（処理残）を処理している間、パターン認識プロセッサ１４はデータストリーム１２を検索することを継続してよい。
【００８９】
それに応じて、リザルトバッファ２５は、データストリーム検索からの結果がリザルトバッファ２５に入力されるのと同時に、リザルトデータをＣＰＵ２０に出力してよい。すなわち、リザルトバッファ２５は、“最も古い”未読レコード１１８からＣＰＵ２０に前もって受信されている結果を伝送している間に、“空の”レコード１１８にデータストリーム検索の結果を受信してよい。これは、バッファ書込み制御モジュール１０４によって制御されながら受信された検索の結果を“空の”レコード１１８に記憶すること、およびバッファ読出し制御モジュール１０６によって制御されながら“最も古い”レコード１１８を読み出すこと、によって成し遂げられる。これは、検索結果処理によって引き起こされる遅延を減少できる。
【００９０】
図１５は、例えばＦＩＦＯ記憶位置０に対するリザルトデータ１２４である、最も古いレコード１１８に対するリザルトデータ１２４に対応してよいリザルトバンク１２８を示す。リザルトバンク１２８は、最も古いレコード１１８がいつでもＣＰＵ２０に対して見える唯一のレコードであるように、リザルトバンク１２８を介して読むことができるＦＩＦＯレコード１１８中への“ウインドウ”であってよい。リザルトバンク１２８のアクセスがひとたび完了すれば、ＣＰＵ２０は、例えば、ＣＰＵ２０がリザルトバンク１２８のレコード１１８（すなわち最も古く記憶されたリザルトデータ１２４）を終了したことを、バッファ読出し制御モジュール１０６に通知してよい。それに応答して、バッファ読出し制御モジュール１０６は、次のレコード１１８すなわちＦＩＦＯ記憶位置１をリザルトバンク１２８に対応する新たな最も古いレコード１１８として見えるようにして、ＦＩＦＯキューを前に進めてよい。このようにして、ＣＰＵ２０はリザルトバンク１２８に対応する現在のレコード１１８を処理することのみができてよい。残りのレコード１１８はＦＩＦＯキューにおいてＣＰＵ２０から隠されたままにされてよい。
【００９１】
リザルトバンク１２８は、レジスタ１３０のグループを含んでよい。このレジスタ１３０のグループは、リザルトデータ１２４を記憶するのに使用されてよい。例えば、レジスタ１３０のグループは、閾値論理マトリクス４４、論理積マトリクス４６、論理和マトリクス４８、初期化ルーティングマトリクス５０、閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および初期化出力マスク１００からの照合結果出力の各々の記憶のための個別のレジスタ１３２−１４６を含んでよい。さらに、レジスタ１３０のグループ中の各レジスタ１３２−１４６は、並列に書き込まれてよい。この方法において、与えられたＦＩＦＯ記憶位置に対応するレコード１１８に対するリザルトデータ１２４は、同時に受信されてレジスタ１３０のグループに記憶されてよく、それによって各個別のレジスタ１３２−１４６は、特にそのマトリクス４４−５０またはマスク９４−１００からの明示された結果を個別に記憶してよい。
【００９２】
本発明は、種々の変形および代替形を受け入れる余地があるが、本明細書では、具体的な実施形態が図面において例として示され、詳細に説明されてきた。しかしながら、本発明は、開示された特定の形式に限定されることを意図されるものではないことを理解されたい。それよりもむしろ、本発明は、以下に添付された請求項によって定義される本発明の精神および範囲内にある全ての変形、均等物および代替物を包含するものである。
【技術分野】
【０００１】
本発明の実施形態は、概して、パターン認識プロセッサおよび、より具体的には、実施形態において、パターン認識プロセッサの多重動作からの結果として生じるデータの通信に関する。
【背景技術】
【０００２】
コンピューティングの分野においては、パターン認識タスクは、ますます性能が試される。大量のデータさえコンピュータ間で伝送され、ユーザが識別を望むパターンの数は増加している。例えば、スパムもしくはマルウェアは、しばしば、データストリームにおけるパターン（例えば、特定の句もしくはコードの一部）を検索することによって検出される。新規の変異形を検索するために新規のパターンが実施される可能性があるため、パターンの数は、スパムおよびマルウェアの多様性によって増加する。これらのパターンの各々に対してデータストリームを検索することは、コンピューティングボトルネック（障害）を形成する可能性がある。しばしば、データストリームが受信されると、一つずつ、各パターンを検索される。システムより前の遅延は、パターン数に伴うデータストリームの増加の次の部分を検索する状態にある。したがって、パターン認識は、データの受信を遅延させる可能性がある。
【０００３】
パターン認識タスクは、実行されることになるさまざまなタイプの照合（一致、マッチ）によってしばしば複雑化される。データストリームは、短く連続する間にいくつかのパターンを照合し、これらの様々な照合は分類され得る。これらの照合による検索は、システムの相対的な性能を遅くし、これにより新しい照合が発生したときにシステムに対して迅速に応答することをできなくさせる。他の例においては、、照合が発生する前の比較的長期間にわたってデータストリームが受信される可能性がある。これにより照合を処理するための他の構成部分の能力は使用されずに残ることとなる。パターン認識中のリザルトデータの不規則な流れは、パターン認識ハードウェアとインタフェース接続するシステムの設計を難しくする。
【図面の簡単な説明】
【０００４】
【図１】データストリームを検索するシステムの一実施例を示す。
【図２】図１のシステムにおけるパターン認識プロセッサの一実施例を示す。
【図３】図２のパターン認識プロセッサにおける検索タームセルの一実施例を示す。
【図４】単一の文字に対してデータストリームを検索する、図３の検索タームセルを示す。
【図５】単一の文字に対してデータストリームを検索する、図３の検索タームセルを示す。
【図６】一語に対してデータストリームを検索する幾つかの検索タームセルを含む認識モジュールを示す。
【図７】一語に対してデータストリームを検索する幾つかの検索タームセルを含む認識モジュールを示す。
【図８】一語に対してデータストリームを検索する幾つかの検索タームセルを含む認識モジュールを示す。
【図９】二語に対してパラレルにデータストリームを検索するように構成された認識モジュールを示す。
【図１０】同一の接頭辞を有する複数語を特定する検索基準に従って検索する認識モジュールを示す。
【図１１】同一の接頭辞を有する複数語を特定する検索基準に従って検索する認識モジュールを示す。
【図１２】同一の接頭辞を有する複数語を特定する検索基準に従って検索する認識モジュールを示す。
【図１３】図１のシステムにおけるパターン認識プロセッサの第２の例を示す。
【図１４】図１３のパターン認識プロセッサにおけるリザルトバッファの例を示す。
【図１５】図１４のリザルトバッファと接続して使用されるレジスタバンクの直列接続を示す。
【発明を実施するための最良の形態】
【０００５】
図１は、データストリーム１２を検索するシステム１０の一実施例を示す。システム１０は、検索基準１６に従ってデータストリーム１２を検索するパターン認識プロセッサ１４を含んでもよい。
【０００６】
各検索基準は、一つ以上の対象表現、すなわちパターンを特定してもよい。“対象表現”という用語は、パターン認識プロセッサ１４が検索するためのデータ配列（シーケンス）のことを称する。対象表現の例は、ある単語を綴る文字配列、遺伝子を特定する遺伝子塩基対配列、画像の一部を形成する画像ファイルもしくはビデオファイルにおけるビット配列、プログラムの一部を形成する実行可能ファイルにおけるビット配列、または、歌もしくは口語表現の一部を形成するオーディオファイルにおけるビット配列を含む。
【０００７】
検索基準は、一つ以上の対象表現を特定してもよい。例えば、検索基準は、文字列“ｃｌ”で始まる全５文字の単語、文字列“ｃｌ”で始まるあらゆる単語、３回以上“ｃｌｏｕｄ”という単語を含む段落などを特定してもよい。対照表現のうちで生じうる組の数は、任意の大きさであり、例えば、データストリームが存在することが可能であるデータの順列が存在するのと同一数の対象表現が存在する可能性がある。検索基準は、種々のフォーマットで表現されてもよく、そのフォーマットは、正規表現として、各対象表現を必ずしも記載することなく、対象表現の組を簡潔に特定するプログラミング言語を含む。
【０００８】
各検索基準は、一つ以上の検索タームから構成されてもよい。したがって、検索基準の各対象表現は一つ以上の検索タームを含み、幾つかの対象表現は、共通の検索タームを使用してもよい。本明細書で使用されるように、“検索ターム”という用語は、単一の検索周期の間に検索されるデータの配列のことを称する。データの配列は、バイナリフォーマットもしくは、例えば、１０進法、ＡＳＣＩＩなどの他のフォーマットにおける複数ビットのデータを含んでもよい。配列は、単一のディジットもしくは複数のディジット（例えば幾つかのバイナリディジット）でデータをエンコードしてもよい。例えば、パターン認識プロセッサ１４は、一度に一文字をテキストデータストリーム１２から検索し、検索タームは、例えば、文字“ａ”、文字“ａ”か“ｅ”のいずれか、または、全ての単一文字の組を特定するワイルドカード検索タームなど、単一文字の組を特定してもよい。
【０００９】
検索タームは、文字（もしくは、データストリームによって表現される情報の他の書記素、すなわち基本単位、例えば、音符、遺伝子塩基対、１０進法のディジット、サブピクセル）を特定するビット数よりも小さいか、または大きくてもよい。例えば、検索タームは８ビットであり、単一文字は１６ビットであり、この場合には、二つの連続した検索タームは単一文字を特定してもよい。
【００１０】
検索基準１６は、コンパイラ１８によってパターン認識プロセッサ１４のためにフォーマットされてもよい。フォーマットするステップは、検索基準から検索タームを分解するステップを含んでもよい。例えば、データストリーム１２によって表現された書記素が検索タームよりも大きい場合、コンパイラは単一の書記素を検索するために、複数の検索タームへと検索基準を分解してもよい。同様に、データストリーム１２によって表現された書記素が検索タームよりも小さい場合、コンパイラ１８は、各個別の書記素に対して、使用されていないビットを伴う単一の検索タームを提供してもよい。コンパイラ１８は、パターン認識プロセッサ１４によって本来サポートされていない種々の正規表現演算子をサポートするために、検索基準１６をフォーマットしてもよい。
【００１１】
パターン認識プロセッサ１４は、データストリーム１２から各新規タームを評価することによって、データストリーム１２を検索してもよい。本明細書における“ターム”という用語は、検索タームに一致しうるデータ量のことを称する。検索周期の間、パターン認識プロセッサ１４は、現在提示されているタームが検索基準において現在の検索タームに一致するかどうかを決定してもよい。タームが検索タームと一致する場合には、評価は“進行”し、すなわち、次のタームが検索基準における次の検索タームと比較される。そのタームが一致しない場合には、次のタームは、検索基準における第一のタームと比較され、それによって検索をリセットする。
【００１２】
各検索基準は、パターン認識プロセッサ１４における異なる有限ステートマシンへとコンパイルされてもよい。有限ステートマシンは、パラレルに（並行して）実行してもよく、検索基準１６に従ってデータストリーム１２を検索する。有限ステートマシンは、先行する検索タームがデータストリーム１２によって一致する場合に検索基準における連続する各検索タームへと進んでもよい。または、検索タームが一致しない場合には、有限ステートマシンは検索基準における第一の検索タームの検索を開始してもよい。
【００１３】
パターン認識プロセッサ１４は、幾つかの検索基準に従って各新規タームを評価し、ほぼ同時に、例えば、単一のデバイス周期の間に其々の検索タームを評価してもよい。パラレルな有限ステートマシンは、ほぼ同時にデータストリーム１２からタームを各々受信し、パラレルな有限ステートマシンの各々は、そのタームが、パラレルな有限ステートマシンを検索基準における次の検索タームへと進めるかどうかを決定してもよい。パラレルな有限ステートマシンは、比較的多数の検索基準（例えば、１００以上、１０００以上、もしくは１００００以上）に従って、タームを評価してもよい。それらはパラレルに動作するため、データストリームを遅延させることなく、比較的高いバンド幅を有するデータストリーム１２（例えば、６４ＭＢ毎秒もしくは１２８ＭＢ毎秒より大きいかほぼ同一のデータストリーム１２）に対して検索基準を適用してもよい。幾つかの実施形態においては、検索周期の継続期間は、検索基準の数によって増減しないため、検索基準の数はパターン認識プロセッサ１４の性能にあまり影響を与えることはない。
【００１４】
検索基準が満足されるとき（すなわち、最後の検索タームに進行してそれが一致した後）、パターン認識プロセッサ１４は、中央処理装置（ＣＰＵ）２０などの処理装置に対して基準を満足したことを報告してもよい。中央処理装置２０は、パターン認識プロセッサ１４およびシステム１０の他の部分を制御してもよい。
【００１５】
システム１０は、データのストリームを検索する種々のシステムもしくはデバイスのうちのいずれであってもよい。例えば、システム１０は、データストリーム１２を監視するデスクトップ、ラップトップ、ハンドヘルドもしくは他のタイプのコンピュータであってもよい。システム１０は、ルータ、サーバ、もしくはクライアント（例えば、前述されたタイプのコンピュータのうちの一つ）などのネットワークノードであってもよい。システム１０は、コピー機、スキャナ、プリンタ、ゲーム機、テレビ、セットトップビデオ分配もしくは録画システム、ケーブルボックス、パーソナルデジタルメディアプレイヤー、工場自動化システム、自動車用コンピュータシステムもしくは医療デバイスなどの他の種類の何らかの電子デバイスであってもよい。（これらの種々のシステムの実施例を記述するために使用される用語は、本明細書で使用される他の多くの用語と同様に、幾つかの指示対象を共有し、それ自体は、列挙された他の項目によって、範囲を狭めて構成されるべきではない。）
【００１６】
データストリーム１２は、ユーザもしくは他の存在が検索を望む可能性のある、種々のタイプの一つ以上のデータストリームであってもよい。例えば、データストリーム１２は、インターネットを介して受信されたパケット、または、携帯電話ネットワークを介して受信された音声もしくはデータなど、ネットワークを介して受信されたデータのストリームであってもよい。データストリーム１２は、画像センサ、温度センサ、加速度計などもしくはその組み合わせなど、システム１０と連通するセンサから受信されたデータであってもよい。データストリーム１２は、シリアルデータストリームとしてシステム１０によって受信され、データは、時間的、語彙的、もしくは意味的に意義のある順序など、意味のある順序で受信される。または、データストリーム１２は、パラレルにもしくはバラバラの順序で受信され、その後、例えば、インターネットを介して受信されたパケットを順序づけることによって、シリアルデータストリームへと変換される。幾つかの実施形態においては、データストリーム１２は、タームをシリアルに提示してもよいが、各タームを表すビットはパラレルに受信されてもよい。データストリーム１２は、システム１０に対して外部ソースから受信されてもよいか、または、メモリデバイスにインテロゲート（伝送）し、格納されたデータからデータストリーム１２を形成することによって形成されてもよい。
【００１７】
データストリーム１２におけるデータのタイプに依存して、異なるタイプの検索基準が設計者によって選択されてもよい。例えば、検索基準１６は、ウイルス定義ファイルであってもよい。ウイルスもしくは他のマルウェアは特徴づけられ、マルウェアの態様は、データストリーム１２がマルウェアを伝送しうるかどうかを示す検索基準を形成するために使用されてもよい。結果として生じる検索基準はサーバに格納され、クライアントシステムのオペレータはシステム１０へと検索基準をダウンロードするサービスに登録してもよい。検索基準１６は、異なるタイプのマルウェアが現れたとき、サーバから定期的にアップデートされてもよい。検索基準は、ネットワークを介して受信される可能性のある望ましくないコンテンツ（例えば、（スパムとしてよく知られている）迷惑電子メールもしくはユーザが望まない他のコンテンツ）を特定するために使用されてもよい。
【００１８】
データストリーム１２はシステム１０によって受信されたデータに対して関心を持った第三者によって検索されてもよい。例えば、データストリーム１２は、著作物として生じる文字列、音声配列、ビデオ配列に対して監視されてもよい。データストリーム１２は、刑事捜査もしくは民事手続きに関係する発話、もしくは使用者にとって関心のある発話に対して監視されてもよい。
【００１９】
検索基準１６は、例えば、ＣＰＵ２０もしくはパターン認識プロセッサ１４によってアドレス可能なメモリにおいて、翻訳が入手可能であるデータストリーム１２におけるパターンを含んでもよい。例えば、検索基準１６は、対応するスペイン語がメモリに格納された英単語を各々特定してもよい。別の実施例においては、検索基準１６は、例えば、デコードされたバージョンのデータストリーム１２が使用可能であるＭＰ３、ＭＰＥＧ４、ＦＬＡＣ、Ｏｇｇ Ｖｏｒｂｉｓなど、エンコードされたバージョンのデータストリーム１２を特定してもよいし、その逆を特定してもよい。
【００２０】
パターン認識プロセッサ１４は、ＣＰＵ２０と共に（単一のデバイスなどの）単一の構成部分に統合されたハードウェアであってもよいし、別個の構成部分として形成されてもよい。例えば、パターン認識プロセッサ１４は別個の集積回路であってもよい。パターン認識プロセッサ１４は、“コプロセッサ”もしくは“パターン認識コプロセッサ”と称されてもよい。
【００２１】
図２は、パターン認識プロセッサ１４の一実施例を示す。パターン認識プロセッサ１４は、認識モジュール２２および出力バッファ５１を有する集約モジュール２４を含んでもよい。出力バッファ５１は、リザルトバッファ２５を含んでもよい。認識モジュール２２は、受信されたタームを検索タームと比較するように構成され、認識モジュール２２および集約モジュール２４の双方は、検索タームとタームが一致することが検索基準を満足するかどうかを決定するように協力してもよい。リザルトバッファ２５はパターン認識プロセッサ１４の他の部分からのリザルトデータをバッファリングしてもよく、これは図１３に関連して以下に説明される。
【００２２】
認識モジュール２２は、行デコーダ２８および複数のフィーチャセル３０を含んでもよい。各フィーチャセル３０は検索タームを特定し、フィーチャセル３０のグループは、検索基準を形成するパラレルな有限ステートマシンを形成してもよい。フィーチャセル３０のコンポーネントは、検索タームアレイ３２、検出アレイ３４およびアクティブ化ルーティングマトリクス３６を形成してもよい。検索タームアレイ３２は複数の入力導体３７を含み、入力導体３７の各々は、行デコーダ２８と連通する各フィーチャセル３０を配置してもよい。
【００２３】
行デコーダ２８は、データストリーム１２のコンテンツに基づいて、複数の入力導体３７中の特定の導体を選択してもよい。例えば、行デコーダ２８は、１タームを表現する可能性がある受信されたバイトの値に基づいて、２５６行のうちの１つをアクティブ化する１バイトから２５６への行デコーダであってもよい。００００００００の１バイトタームは、複数の入力導体３７のうち最も上の行に対応し、１１１１１１１１の１バイトタームは、複数の入力導体３７のうちの最も下の行に対応してもよい。したがって、異なる入力導体３７は、どのタームがデータストリーム１２から受信されるかに依存して選択されてもよい。異なるタームが受信されると、行デコーダ２８は、前のタームに対応する行を非アクティブ化し、新規タームに対応する行をアクティブ化してもよい。
【００２４】
検出アレイ３４は、検索基準を完全にもしくは部分的に満足することを示す信号を集約モジュール２４に対して出力する検出バス３８に結合してもよい。アクティブ化ルーティングマトリクス３６は、一致した検索基準における検索ターム数に基づいて、フィーチャセル３０を選択的にアクティブ化する、ならびに非アクティブ化してもよい。
【００２５】
集約モジュール２４は、ラッチマトリクス４０、集約ルーティングマトリクス４２、閾値論理マトリクス４４、論理積マトリクス４６、論理和マトリクス４８および初期化ルーティングマトリクス５０を含んでもよい。
【００２６】
ラッチマトリクス４０は、ある検索基準の一部を実施してもよい。例えば、幾つかの正規表現などの幾つかの検索基準は、最初に一致（もしくは複数の一致）が発生したときのみ考慮する。ラッチマトリクス４０は、一致が生じたかどうかを記録するラッチを含んでもよい。検索基準が満足されたとき、もしくはそれ以上満足されないと判定された、すなわち、その検索基準が満足されるより前に前の検索タームを再度マッチングさせる必要があるとき、ラッチは初期化の間にクリアされ、動作中に定期的に再初期化されてもよい。
【００２７】
集約ルーティングマトリクス４２は、アクティブ化ルーティングマトリクス３６と類似した機能を果たしてもよい。集約ルーティングマトリクス４２は、検出バス３８における一致を示す信号を受信し、閾値論理マトリクス４４に接続する異なるグループ論理ライン５３へと信号を送信してもよい。集約ルーティングマトリクス４２は、検索基準が満足された、もしくはこれ以上満足されないと判定されたとき、検出アレイ３４の一部をリセットするために、検出アレイ３４へと初期化ルーティングマトリクス５０の出力を送信してもよい。
【００２８】
閾値論理マトリクス４４は、例えば、数を数える（カウントアップする）、または数を逆に数える（カウントダウンする）ように構成された３２ビットカウンタなどの、複数のカウンタを含んでもよい。閾値論理マトリクス４４は、初期カウントでロードされ、認識モジュールによって信号通知された一致時のカウント値から、カウントアップもしくはカウントダウンしてもよい。例えば、閾値論理マトリクス４４は、ある長さの文字列の単語が現れた数を数えてもよい。
【００２９】
閾値論理マトリクス４４の出力は、論理積マトリクス４６に対する入力であってもよい。論理積マトリクス４６は、“積”の結果（例えば、ブール論理における“ＡＮＤ”関数）を選択的に生成してもよい。論理積マトリクス４６は、正方行列として実施され、出力積の数は、閾値論理マトリクス４４からの入力ラインの数と同一であるか、または、論理積マトリクス４６は、出力とは異なる数の入力を有してもよい。結果として生じる積の値は、論理和マトリクス４８に対する出力であってもよい。
【００３０】
論理和マトリクス４８は、和（例えば、ブール論理における“ＯＲ”関数）を選択的に生成してもよい。論理和マトリクス４８もまた、正方行列として実施されるか、または、論理和マトリクス４８は、出力とは異なる数の入力を有してもよい。入力は論理積であるため、論理和マトリクス４８の出力は、論理積和（例えば、ブール論理での積和（ＳＯＰ）形）であってもよい。論理和マトリクス４８の出力は、初期化ルーティングマトリクス５０によって受信されてもよい。
【００３１】
初期化ルーティングマトリクス５０は、集約ルーティングマトリクス４２を介して、検出アレイ３４および集約モジュール２４の一部をリセットしてもよい。初期化ルーティングマトリクス５０は、正方行列として実行されるか、または、初期化ルーティングマトリクス５０は、出力とは異なる数の入力を有してもよい。初期化ルーティングマトリクス５０は、論理和マトリクス４８からの信号に応じて、例えば、検索基準が満足されたとき、または、検索基準がこれ以上満足されないと判定されたとき、パターン認識プロセッサ１４の他の部分を再初期化してもよい。
【００３２】
集約モジュール２４は、閾値論理マトリクス４４、集約ルーティングマトリクス４２、および論理和マトリクス４８の出力を受信する出力バッファ５１を含んでもよい。集約モジュール２４の出力は、出力バッファ５１から出力バス２６上のＣＰＵ２０（図１）へと伝送されてもよい。幾つかの実施形態においては、出力マルチプレクサは、これらのコンポーネント４２、４４および４８からの信号を多重化し、基準を満足したことを示す信号、もしくは検索タームの一致を示す信号をＣＰＵ２０（図１）へと出力してもよい。他の実施形態においては、パターン認識プロセッサ１４からのリザルトは、出力マルチプレクサを介して信号を伝送することなく報告されてもよいが、このことは、本明細書で記述されたあらゆる他の特性が省略される可能性がないことを示唆するものではない。例えば、閾値論理マトリクス４４、論理積マトリクス４６、論理和マトリクス４８もしくは初期化ルーティングマトリクス５０からの信号は、出力バス２６上をパラレルにＣＰＵへと伝送されてもよい。
【００３３】
図３は、検索タームセル５４として本明細書で称されるコンポーネントである、検索タームアレイ３２（図２）における単一のフィーチャセル３０の一部を示す。検索タームセル５４は、出力導体５６および複数のメモリセル５８を含んでもよい。各メモリセル５８は、出力導体５６および複数の入力導体３７の中の導体の一つの両方へと結合されてもよい。入力導体３７が選択されるのに応じて、各メモリセル５８は、格納された値を示す値を出力し、出力導体５６を介してデータを出力する。幾つかの実施形態においては、複数の入力導体３７は“ワード線”と称され、出力導体５６は“データ線”と称されてもよい。
【００３４】
メモリセル５８は、種々のタイプのメモリセルのうちのいずれを含んでもよい。例えば、メモリセル５８は、トランジスタとキャパシタを有するダイナミックランダムアクセスメモリ（ＤＲＡＭ）セルなどの揮発性メモリであってもよい。トランジスタのソースおよびドレインは、其々、キャパシタのプレートおよび出力導体５６へと接続され、トランジスタのゲートは入力導体３７のうちの一つへと接続されてもよい。揮発性メモリの別の実施例においては、各メモリセル５８は、スタティックランダムアクセスメモリ（ＳＲＡＭ）セルを含んでもよい。ＳＲＡＭセルは、入力導体３７の一つによって制御されるアクセストランジスタによって、出力導体５６へと選択的に結合された出力を有してもよい。メモリセル５８は、相変化メモリ（例えば、オボニックデバイス）、フラッシュメモリ、シリコン・酸化物・窒化物・酸化物・シリコン（ＳＯＮＯＳ）メモリ、磁気抵抗メモリもしくは他のタイプの不揮発性メモリなどの不揮発性メモリをも含んでもよい。メモリセル５８は、フリップフロップ、例えば、論理ゲートによって形成されたメモリセルをも含んでもよい。
【００３５】
図４および図５は、動作における検索タームセル５４の一実施例を示す。図４は、セルの検索タームに一致しないタームを受信する検索タームセル５４を示し、図５は、セルの検索タームに一致するタームを受信する検索タームセル５４を示す。
【００３６】
図４によって示されるように、検索タームセル５４は、メモリセル５８にデータを格納することによって、一つ以上のタームを検索するように構成されてもよい。メモリセル５８は、例えば図３において、データストリーム１２が提示する可能性のあるタームを各々表し、各メモリセル５８は文字“ａ”で開始し、数字“９”で終了する単一の文字もしくは数字を表す。検索タームを満足するタームを表すメモリセル５８は、第一の値を格納するようにプログラムされ、検索タームを満足するタームを表していないメモリセル５８は、異なる値を格納するようにプログラムされてもよい。示された実施例においては、検索タームセル５４は、文字“ｂ”を検索するように構成される。“ｂ”を表すメモリセル５８は、１もしくは論理的なハイを格納し、“ｂ”を表していないメモリセル５８は、０、もしくは論理的なロウを格納するようにプログラムされてもよい。
【００３７】
データストリーム１２からのタームを検索タームと比較するために、行デコーダ２８は、受信されたタームを表すメモリセル５８に結合された入力導体３７を選択してもよい。図４においては、データストリーム１２は、小文字の“ｅ”を示す。このタームは、８ビットＡＳＣＩＩコード形式でデータストリーム１２によって示され、行デコーダ２８は、行アドレスとしてこのバイトを解釈し、導体６０に電圧を印加することによって、導体６０上に信号を出力する。
【００３８】
それに応じて、導体６０によって制御されるメモリセル５８は、メモリセル５８が格納するデータを示す信号を出力し、その信号は出力導体５６によって伝送されてもよい。この場合には、文字“ｅ”は、検索タームセル５４によって特定されたタームのうちの一つではないため、検索タームとは一致せず、検索タームセル５４は０値を出力し、それは一致が見つからなかったことを示している。
【００３９】
図５においては、データストリーム１２は、文字“ｂ”を示す。再度、行デコーダ２８はこのタームをアドレスとして解釈し、行デコーダ２８は導体６２を選択してもよい。それに応じて、文字“ｂ”を表すメモリセル５８は、格納された値を出力し、この場合には、それは１であり、一致を示している。
【００４０】
検索タームセル５４は一度に一つ以上のタームを検索するように構成されてもよい。複数のメモリセル５８は、１を格納するようにプログラムされ、一つ以上のタームと一致する検索タームを特定する。例えば、小文字“ａ”および大文字“Ａ”を表すメモリセル５８は、１を格納するようにプログラムされ、検索タームセル５４は、いずれかのタームを検索してもよい。別の実施例においては、検索タームセル５４は、いかなる文字が受信された場合にも一致を出力するように構成されてもよい。全メモリセル５８は、１を格納するようにプログラムされてもよく、検索タームセル５４は、検索基準におけるワイルドカードタームとして機能してもよい。
【００４１】
図６−図８は、例えば一単語など複数ターム検索基準に従って検索する認識モジュール２２を示す。具体的には、図６は一単語の最初の文字を検出する認識モジュール２２を示し、図７は、第二の文字の検出を示し、図８は、最後の文字の検出を示す。
【００４２】
図６によって示されるように、認識モジュール２２は、単語“ｂｉｇ”を検索するように構成されてもよい。３個の隣接するフィーチャセル６３、６４および６６が示される。フィーチャセル６３は、文字“ｂ”を検出するように構成される。フィーチャセル６４は、文字“ｉ”を検出するように構成される。フィーチャセル６６は、文字“ｇ”を検出し、検索基準が満足されたことを示すように構成される。
【００４３】
図６は、検出アレイ３４のさらなる詳細をも示す。検出アレイ３４は、各フィーチャセル６３、６４および６６における検出セル６８を含んでもよい。各検出セル６８は、上述されたタイプのメモリセルのうちの一つ（例えば、フリップフロップ）のような、メモリセル７０を含んでもよく、メモリセル７０は、フィーチャセル６３、６４もしくは６６がアクティブか非アクティブかを示す。検出セル６８は、両方の検出セルがアクティブであり、一致を示す関連付けられた検索タームセル５４から信号を受信したかどうかを示す信号を、アクティブ化ルーティングマトリクス３６へと出力するように構成されてもよい。非アクティブなフィーチャセル６３、６４および６６は、一致を無視してもよい。各検出セル６８は、メモリセル７０および出力導体５６からの入力を有する、ＡＮＤゲートを含んでもよい。ＡＮＤゲートの出力は、検出バス３８およびアクティブ化ルーティングマトリクス３６の両方へ、またはそのどちらか一方へと送信されてもよい。
【００４４】
今度は、アクティブ化ルーティングマトリクス３６は、検出アレイ３４におけるメモリセル７０へと書き込むことによって、フィーチャセル６３、６４および６６を選択的にアクティブ化してもよい。アクティブ化ルーティングマトリクス３６は、検索基準ならびに次にどの検索タームがデータストリーム１２において検索されるかに従って、フィーチャセル６３、６４もしくは６６をアクティブ化してもよい。
【００４５】
図６においては、データストリーム１２は文字“ｂ”を示す。それに応じて、各フィーチャセル６３、６４および６６は、その出力導体５６上に信号を出力し、文字“ｂ”を表す導体６２に接続されたメモリセル５８に格納された値を示す。検出セル５６は、その後、一致を示す信号を受信したかどうか、ならびに検出セル５６がアクティブかどうかを各々決定してもよい。フィーチャセル６３は文字“ｂ”を検出するように構成され、そのメモリセル７０によって示されるようにアクティブであるため、フィーチャセル６３における検出セル６８は、アクティブ化ルーティングマトリクス３６へと信号を出力して、検索基準のうちの第一の検索タームが一致したことを示す。
【００４６】
図７によって示されるように、第一の検索タームが一致した後、アクティブ化ルーティングマトリクス３６は、検出セル６８におけるメモリセル７０へと１を書き込むことによって、次のフィーチャセル６４をアクティブ化してもよい。次のタームが第一の検索タームを満足する場合（例えば、タームの配列“ｂｂｉｇ”が受信された場合）アクティブ化ルーティングマトリクス３６はフィーチャセル６３のアクティブ状態を維持してもよい。検索基準のうちの第一の検索タームは、データストリーム１２が検索される時間のうちの一部もしくは実質的に全期間の間、アクティブ状態に維持されてもよい。
【００４７】
図７においては、データストリーム１２は認識モジュール２２へ文字“ｉ”を出力する。それに応じて、各フィーチャセル６３、６４および６６は、その出力導体５６上に信号を出力し、文字“ｉ”を表す導体７２へと接続されたメモリセル５８に格納された値を示す。検出セル５６は、その後、一致を示す信号を受信したかどうか、ならびに検出セル５６がアクティブかどうかを各々決定してもよい。フィーチャセル６４は文字“ｉ”を検出するように構成され、メモリセル７０によって示されるようにアクティブであるため、フィーチャセル６４における検出セル６８は、アクティブ化ルーティングマトリクス３６へと信号を出力し、検索基準の次の検索タームが一致したことを示す。
【００４８】
続いて、図８に示されるように、アクティブ化ルーティングマトリクス３６はフィーチャセル６６をアクティブ化してもよい。次のタームを評価する前に、フィーチャセル６４は非アクティブ化されてもよい。フィーチャセル６４は、その検出セル６８によって非アクティブ化され、検出周期の間そのメモリセル７０をリセットするか、または、例えば、アクティブ化ルーティングマトリクス３６はフィーチャセル６４を非アクティブ化してもよい。
【００４９】
図８においては、データストリーム１２は行デコーダ２８へと、ターム“ｇ”を出力し、行デコーダ２８はターム“ｇ”を表す導体７４を選択する。それに応じて、各フィーチャセル６３、６４および６６は、その出力導体５６上に信号を出力し、文字“ｇ”を表す導体７４へと接続されたメモリセル５８に格納された値を示す。検出セル５６は、その後、一致を示す信号を受信したかどうか、ならびに検出セル５６がアクティブかどうかを各々決定してもよい。フィーチャセル６６は文字“ｇ”を検出するように構成され、そのメモリセル７０によって示されるようにアクティブであるため、フィーチャセル６６における検出セル６８は、アクティブ化ルーティングマトリクス３６へと信号を出力し、検索基準の最後の検索タームが一致したことを示す。
【００５０】
検索基準の終わりもしくは検索基準の一部は、アクティブ化ルーティングマトリクス３６もしくは検出セル６８によって識別されてもよい。これらのコンポーネント３６もしくは６８は、そのフィーチャセル６３、６４もしくは６６が検索基準の最終検索タームか検索基準のコンポーネントかを識別するかを示すメモリを含んでもよい。例えば、検索基準は、“ｃａｔｔｌｅ”という単語が二度現れる全ての文を特定し、認識モジュールは、“ｃａｔｔｌｅ”の出現回数を数える集約モジュールへと、文内の各々の“ｃａｔｔｌｅ”の出現を示す信号を出力し、検索基準が満足されたかどうかを判定する。
【００５１】
フィーチャセル６３、６４もしくは６６は幾つかの条件下でアクティブ化されてもよい。フィーチャセル６３、６４もしくは６６は、“常にアクティブ”であってもよく、それは、全検索の間、もしくは実質的に全ての検索の間アクティブ状態のままであることを意味する。常にアクティブなフィーチャセル６３、６４もしくは６６の一実施例は、検索基準の第一のフィーチャセル、例えば、フィーチャセル６３である。
【００５２】
フィーチャセル６３、６３もしくは６６は、“要求されたときアクティブ”であってもよく、それは、幾つかの先行する条件が一致したとき、例えば、検索基準における先行する検索タームが一致したときに、フィーチャセル６３、６４もしくは６６がアクティブであることを意味する。一実施例は、図６−図８におけるフィーチャセル６３によって要求されたときにアクティブであるフィーチャセル６４と、フィーチャセル６４によって要求されたときにアクティブであるフィーチャセル６６である。
【００５３】
フィーチャセル６３、６４もしくは６６は、“自己アクティブ化”されてもよく、それは、一度アクティブ化されればその検索タームが一致している限り、それ自身をアクティブ化することを意味する。例えば、いかなる数のディジットにでも一致した検索タームを有する自己アクティブ化されたフィーチャセルは、文字“ｘ”に到達するまで、文章“１２３４５６ｘｙ”をアクティブ化したままであってもよい。自己アクティブ化されたフィーチャセルの検索タームが一致するたび、自己アクティブ化されたフィーチャセルは検索基準における次のフィーチャセルをアクティブ化してもよい。したがって、常にアクティブなフィーチャセルは、自己アクティブ化するフィーチャセルおよび要求されたときにアクティブなフィーチャセルから形成されてもよい。自己アクティブ化フィーチャセルは、１を格納するメモリセル５８の全てにプログラムされてもよく、各ターム後に要求されたときアクティブなフィーチャセルを繰り返しアクティブ化してもよい。幾つかの実施形態においては、各フィーチャセル６３、６４および６６は、フィーチャセルが常にアクティブかどうかを識別する検出セル６８もしくはアクティブ化ルーティングマトリクス３６におけるメモリセルを含んでもよく、それによって、単一のフィーチャセルから常にアクティブなフィーチャセルを形成する。
【００５４】
図９は、第一の検索基準７５および第二の検索基準７６に従ってパラレルに検索するように構成された認識モジュール２２の一実施例を示す。本実施例においては、第一の検索基準７５は、単語“ｂｉｇ”を識別し、第二の検索基準７６は、単語“ｃａｂ”を識別する。データストリーム１２からの現在のタームを示す信号は、ほぼ同時に各検索基準７５および７６におけるフィーチャセルへと通信されてもよい。各入力導体３７は、検索基準７５および７６の双方へと及ぶ。結果として、幾つかの実施形態においては、検索基準７５および７６の双方は、ほぼ同時に現在のタームを評価してもよい。このことによって、検索基準の評価が加速すると考えられる。他の実施形態は、より多くの検索基準をパラレルに評価するように構成されたより多くのフィーチャセルを含んでもよい。例えば、幾つかの実施形態は、パラレルに動作する１００、５００、１０００、５０００もしくは１００００以上のフィーチャセルを含んでもよい。これらのフィーチャセルは、ほぼ同時に何百、もしくは何千もの検索基準を評価してもよい。
【００５５】
異なる数の検索タームを有する検索基準は、より多くのもしくはより少ないフィーチャセルを検索基準へと割り当てることによって形成されてもよい。単純な検索基準は、フィーチャセルの形式で、複雑な検索基準よりも、より少ないリソースを消費してもよい。このことによって、ほぼ同一の多数のコアを有し、複雑な検索基準を評価するように全て構成されたプロセッサと比較して、パターン認識プロセッサ１４（図２）のコストを低減すると考えられる。
【００５６】
図１０−図１２は、アクティブ化ルーティングマトリクス３６のより複雑な検索基準とフィーチャの一実施例の双方を示す。アクティブ化ルーティングマトリクス３６は、複数のアクティブ化ルーティングセル７８を含んでもよく、アクティブ化ルーティングセル７８のグループは、各フィーチャセル６３、６４、６６、８０、８２、８４および８６に関連付けられてもよい。例えば、各フィーチャセルは、５、１０、２０、５０もしくはそれ以上のアクティブ化ルーティングセル７８を含んでもよい。アクティブ化ルーティングセル７８は、先行する検索タームが一致するとき、検索基準における次の検索タームへとアクティブ化信号を送信するように構成されてもよい。アクティブ化ルーティングセル７８は、同一のフィーチャセル内の隣接するフィーチャセルもしくは他のアクティブ化ルーティングセル７８へとアクティブ化信号を送信するように構成されてもよい。アクティブ化ルーティングセル７８は、どのフィーチャセルが検索基準における次の検索タームに対応するかを示すメモリを含んでもよい。
【００５７】
図１０−図１２に示されるように、認識モジュール２２は、単一の単語を特定する基準よりも複雑な検索基準に従って検索するように構成されてもよい。例えば、認識モジュール２２は、接頭辞８８で開始し、２つの接尾辞９０もしくは９２のうちの一つで終了する単語を検索するように構成されてもよい。示された検索基準は、文字“ｃ”および“ｌ”の配列で開始し、文字配列“ａｐ”もしくは文字配列“ｏｕｄ”のいずれかで終了する単語を特定する。これは、複数の対象表現、例えば、単語“ｃｌａｐ”もしくは単語“ｃｌｏｕｄ”を特定する検索基準の一実施例である。
【００５８】
図１０においては、データストリーム１２は、認識モジュール２２に対して文字“ｃ”を示し、フィーチャセル６３は両方アクティブであり、一致を検出する。それに応じて、アクティブ化ルーティングマトリクス３６は、次のフィーチャセル６４をアクティブ化してもよい。アクティブ化ルーティングマトリクス３６は、フィーチャセル６３が検索基準における第一の検索タームであるとき、フィーチャセル６３のアクティブ状態を維持してもよい。
【００５９】
図１１においては、データストリーム１２は、文字“ｌ”を示し、フィーチャセル６４は、一ｘ致を認識してアクティブである。それに応じて、アクティブ化ルーティングマトリクス３６は、第一の接尾辞９０の第一のフィーチャセル６６および第二の接尾辞９２の第一のフィーチャセル８２の双方へとアクティブ化信号を伝送してもよい。他の実施例においては、より多くの接尾辞がアクティブ化されてもよく、または、複数の接頭辞は一つ以上の接尾辞をアクティブ化してもよい。
【００６０】
続いて、図１２においては、データストリーム１２は、認識モジュール２２に対して文字“ｏ”を示し、第二の接尾辞９２のフィーチャセル８２は、一致を認識してアクティブである。それに応じて、アクティブ化ルーティングマトリクス３６は、第二の接尾辞９２の次のフィーチャセル８４をアクティブ化してもよい。フィーチャセル６６が非アクティブになると認められると、第一の接尾辞９０の検索は終了してもよい。図１０−図１２に示されたステップは、文字“ｕ”および“ｄ”へと継続してもよいし、または、接頭辞８８が一致する次の機会まで、検索は終了してもよい。
【００６１】
図１３は、他のパターン認識プロセッサ９３の例を示す。パターン認識プロセッサ９３は、図２のパターン認識プロセッサ１４に関して上述したのと実質的に同様の方法で動作してよい。しかしながら、パターン認識プロセッサ９３は、図２のパターン認識プロセッサ１４と共通の構成部分に加えて、閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および初期化出力マスク１００をさらに含んでよい。
【００６２】
閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および初期化出力マスク１００は一般に、入力として受信される一つ以上の結果を、“マスク”し、換言すればフィルタ処理する。例えば、閾値論理マトリクス４４は、データストリーム１２における例えばセキュリティの脅威などの全ての既知の出現事象に対して検索をするように設定されてよい。しかしながら、特定のハイリスク脅威のような一つ以上の特定のセキュリティ脅威に対しては、これらの結果をフィルタ処理することが有益であろう。従って、閾値出力マスク９４は、特定のハイリスクセキュリティ脅威を除いては、閾値論理４４によって発見される全てのセキュリティ脅威をブロックするように設定されてよい。もしこのハイリスクセキュリティ脅威が発見されたならば、ＣＰＵによって取り出されるようにするために、脅威に対する通知が閾値出力マスク９４から出力バッファ５１に伝送されてよい。このようにして、閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および初期化出力マスク１００は、それぞれがパターンマッチングマトリクス４４−５０の全体の結果出力から一つ以上の特定の結果を分けるために、それぞれのマトリクス４４−５０の出力をフィルタ処理できるマスクモジュールを形成してよい。幾つかの実施形態において、出力マスクモジュール９４−１００は、そのようなフィルタリングを容易にするために、パターンマッチングマトリクス４４−５０の出力に関連するマスクレジスタを用いてよい。
【００６３】
従って、閾値出力マスク９４は、閾値論理マトリクス４４の結果に基づいて検索結果照合（一致、マッチ）を生成するように動作してよい。上述したように、閾値論理マトリクス４４は、認識モジュールにより通知された照合に基づいてカウントアップまたはダウンするように構成される例えば３２ビットカウンタである複数のカウンタを含んでよい。閾値論理マトリクス４４は、データ列中で発見された３つの“Ａ”シンボルのようないくらかの長さのテキストにおける単語の発生数を計数してよい。閾値論理マトリクス４４からの結果は、閾値出力マスク９４、出力バッファ５１、および論理積マトリクス４６に送られてよい。閾値出力マスク９４は、閾値論理マトリクス４４によって決定される閾値結果を使用して追加の照合検索を実行してよい。この追加の照合検索は、例えば閾値出力マスク９４中のビット配置を使って閾値論理マトリクス４４によって決定される閾値結果に対する“アンド演算（ＡＮＤ−ｉｎｇ）”を含んでよい。
【００６４】
例えば、閾値結果は、各ラインが特定の結果に対応してよい例えば３２ラインの閾値出力マスク９４に送られてよい。これらのラインの各々はまた、１または０のいずれかにセットされてよい、閾値出力マスク９４内の対応するビット配置を有してよい。そのセットされる値は、そのビット配置に対応するライン上で受信された結果が閾値出力マスク９４によって選択されるものであるか否かに依存する。このようにして、１にセットされた閾値出力マスク９４内の任意のビット配置に対して、閾値論理マトリクス４４からの対応する結果ラインに沿って受信された任意の情報が、閾値出力マスク９４から出力バッファ５１に伝送されてよい。同様にして、０にセットされた閾値出力マスク９４内の任意のビット配置に対して、閾値論理マトリクス４４からの対応するラインに沿って受信された任意の情報が、マスクされ、換言すればフィルタ処理され、従って、閾値出力マスク９４から出力バッファ５１に伝送されないようにしてよい。このようにして、閾値出力マスク９４は、どの閾値論理マトリクス４４の結果（例えば閾値出力マスク９４中の有効にされたビット配置に対応するもの）を出力バッファ５１に流し、どの閾値論理マトリクス４４の結果（例えば閾値出力マスク９４中の有効にされたビット配置に対応するもの）を無視するかを、効果的に選択してよい。上述の考察は、閾値出力マスク９４を介したハードウェア照合について説明することを示してきたが、上述のものと同様に機能的に動作する閾値マスクプログラムを用いたソフトウェア照合が使用されてもよいことに留意されたい。
【００６５】
積出力マスク９６は、論理積マトリクス４６の結果に基づいて検索結果照合を生成するように動作してよい。論理積マトリクス４６は、２つ以上の閾値論理マトリクス４４結果に基づいて、“積”の結果（例えば、ブール論理における“ＡＮＤ”関数）を選択的に生成してよい。例えば、論理積マトリクス４６は３つの“Ａ’ｓ”とターム“ｃａｔ”の両方を検索してよい。論理積マトリクス４６からの結果は、積出力マスク９６、出力バッファ５１、および論理和マトリクス４８に流されてよい。積出力マスク９６は、論理積マトリクス４６により決定された積の結果を使用して追加の照合検索を実行してよい。この追加の照合検索は、例えば閾値出力マスク９４内のビット配置を用いて論理積マトリクス４６によって決定される結果に対する“アンド演算（ＡＮＤ−ｉｎｇ）”を含んでよい。
【００６６】
例えば、論理積マトリクス４６の積の結果は、各ラインが特定の結果に対応してよい例えば３２ラインに沿って積出力マスク９６に流されてよい。これらのラインの各々はまた、１または０のいずれかがセットされてよい積出力マスク９６内の対応するビット配置を有してよい。そのセットされる値は、そのビット配置に対応するライン上で受信された結果が積出力マスク９６によって選択されるべきものであるか否かに依存する。このようにして、１にセットされた積出力マスク９６内の任意のビット配置に対して、論理積マトリクス４６からの対応する結果ラインに沿って受信された任意の情報が、積出力マスク９６から出力バッファ５１に伝送されてよい。同様にして、０にセットされた積出力マスク９６内の任意のビット配置に対して、論理積マトリクス４６からの対応するラインに沿って受信された任意の情報が、マスクされ、換言すればフィルタ処理され、従って、積出力マスク９６から出力バッファ５１に伝送されないようにしてよい。このようにして、積出力マスク９６は、どの論理積マトリクス４６の結果（例えば積出力マスク９６中の有効にされたビット配置に対応するもの）を出力バッファ５１に流し、どの論理積マトリクス４６の結果（例えば積出力マスク９６中の有効にされたビット配置に対応するもの）を無視するかを、効果的に選択してよい。上述の考察は、積出力マスク９６を介したハードウェア照合について説明することを示してきたが、上述のものと同様に機能的に動作する閾値マスクプログラムを用いたソフトウェア照合が使用されてもよいことに留意されたい。
【００６７】
和出力マスク９８は、閾値出力マスク９４および積出力マスク９６を用いて上述したのと類似の方法で、論理和マトリクス４８の結果に基づいて検索結果照合を生成するように動作してよい。論理和マトリクス４８は、“和”の結果（例えば、ブール論理における“ＯＲ”関数）を選択的に生成してよく、あるいは、論理積入力結果に基づいて、論理積和（例えば、ブール論理での積和（ＳＯＰ）形）を創り出してもよい。例えば、論理和マトリクス４８は、３つの“Ａ’ｓ”とターム“ｃａｔ”の両方または３つの“Ｎ’ｓ”とターム“ｄｏｇ”、を検索してよい。論理和マトリクス４８からの結果は、和出力マスク９８、出力バッファ５１、および初期化ルーティングマトリクス５０に送られてよい。
【００６８】
そのような和の結果は、和出力マスク９８によって一組の出力結果ラインに沿って受信されてよい。これらのラインの各々はまた、１または０のいずれかがセットされてよい和出力マスク９８内の対応するビット配置を有してよい。そのセットされる値は、そのビット配置に対応するライン上で受信された結果が和出力マスク９８によって選択されるべきものであるか否かに依存する。従って、１にセットされた和出力マスク９８内の任意のビット配置に対して、論理和マトリクス４８からの対応する結果ラインに沿って受信された任意の情報が、和出力マスク９８から出力バッファ５１に伝送されてよい。同様にして、０にセットされた和出力マスク９８内の任意のビット配置に対して、論理和マトリクス４８からの対応する結果ラインに沿って受信された任意の情報が、マスクされ、換言すればフィルタ処理され、従って、和出力マスク９８から出力バッファ５１に伝送されないようにしてよい。このようにして、和出力マスク９８は、どの論理和マトリクス４８の結果（例えば和出力マスク９８中の有効にされたビット配置に対応するもの）を出力バッファ５１に流し、どの論理和マトリクス４８の結果（例えば和出力マスク９８中の有効にされたビット配置に対応するもの）を無視するかを、効果的に選択してよい。上述の考察は、和出力マスク９８を介したハードウェア照合について説明することを示してきたが、上述のものと同様に機能的に動作する閾値マスクプログラムを用いたソフトウェア照合が使用されてもよいことに留意されたい。
【００６９】
初期化出力マスク１００は、初期化ルーティングマトリクス５０の初期化結果に基づく結果を生成するように動作してよい。初期化ルーティングマトリクス５０は、論理和マトリクス４８からの結果に基づいて、検出アレイ３４および／または集約ルーティングマトリクス４２を介して集約モジュール２４の一部を選択的にリセットしてよい。初期化ルーティングマトリクス５０はまた、検索基準が満足されまたはそれ以上満足されないと決定されたときのような場合に、パターン認識プロセッサ１４の他の部分を再初期化してもよい。これらの初期化結果は、出力バッファ５１および初期化出力マスク１００に流される。
【００７０】
初期化出力マスク１００は、初期化ルーティングマトリクス５０によって決定される初期化結果を利用して追加の照合検索を実行してよく、それによって第２の条件付きのリセットが生成されてもよい。この追加的なリセットは、例えば検出アレイ３４または集約ルーティングマトリクス４２を介した集約モジュール２４の初期化出力マスク１００によるリセットのための第２の条件を用いて、初期化ルーティングマトリクス５０によって決定される初期化結果に対する“アンド演算（ＡＮＤ−ｉｎｇ）”によって生成されてもよい。この第２の条件は初期化出力マスク１００内の一つ以上のアクティブ化されたビット配置であってよく、それによりそのビット配置は初期化ルーティングマトリクス５０からの一つ以上の結果ラインに対応する。初期化出力マスク１００内の与えられたビット配置は１または０のいずれかにセットされてよい。そのセットされる値は、そのビット配置に対応するライン上で受信された結果が初期化出力マスク１００によって選択されるべきものであるか否かに依存する。この結果、どの初期化ルーティングマトリクス５０の結果を出力バッファ５１に流し、どの初期化ルーティングマトリクス５０の結果を無視するかを効果的に選択できる。さらに、初期化出力マスク１００は、ハードウェアを介して、または、例えば上述のハードウェア実装と同様に機能的に動作する初期化マスクプログラムを用いたソフトウェアを介して、実装されてよい。
【００７１】
従って、出力バッファ５１は、閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および初期化出力マスク１００の出力と同様に、閾値論理マトリクス４４、論理積マトリクス４６、論理和マトリクス４８、および初期化ルーティングマトリクス５０の出力を受信してよい。出力バッファ５１は、結果バッファ２５とともに、出力バス２６を介した出力の伝送に先立って、その出力のためのバッファとして動作してよい。さらに、これらの結果の出力バッファ５１への書込みは、同時に、換言すれば並列に実行されてよい。
【００７２】
図１４は、パターン認識プロセッサ１４またはパターン認識プロセッサ９３に結合されるリザルト（結果）バッファ２５の例を示す。図２および図１３に関連して上述したように、リザルトバッファ２５は、出力バッファ５１に含まれてよい。結果バッファ２５は、ファースト−インファースト−アウト（ＦＩＦＯ）バッファ１０２、バッファ書込み制御モジュール１０４、バッファ読出し制御モジュール１０６、およびバッファ設定モジュール１０８を含んでよい。リザルトバッファ２５は、パターン認識プロセッサ１４の一部として（例えばシリコンの同一ボディー上に）完全に形成されてよく、あるいはそれは別々の構成部品または別々の構成部品の一部であってもよい。リザルトバッファ２５は、上りリザルトバス１１０を通してパターン認識プロセッサ１４からリザルトデータを受信してよく、また、リザルトバッファ２５は、下りリザルトバス１１２を通してＣＰＵ２０（図１）にリザルトデータを出力してよい。設定バス１１４は、ＣＰＵ２０を、リザルトバッファ２５内のバッファ設定モジュール１０８およびパターン認識プロセッサ１４を設定するのに使用してよいパターン認識プロセッサ設定モジュール１１６と通信する状態に置いてよい。
【００７３】
ＦＩＦＯバッファ１０２は、複数のレコード１１８を記憶するように構成されてよい。各レコード１１８は例えば基準の充足に関連するデータであるリザルトデータを記憶してよい。各レコード１１８は一つの基準を満足させる一つのインスタンスと一致してよく、あるいは、基準を満足させることに関連するデータは例えば幾つかの隣接する、さもなくば連続的なレコード１１８である幾つかのレコード１１８に記憶されてよい。
【００７４】
各レコード１１８はリザルトステータス情報１２０，ハウスキーピング情報１２２，およびリザルトデータ１２４を記憶するためのフィールドを含んでよい。他の実施形態は、追加的なフィールドまたはより少ないフィールドを含んでよい。リザルトステータスフィールド１２０はデータストリーム１２を識別しデータストリーム１２をパターン認識プロセッサ１４が受信するかもしれない他のデータストリームから区別するデータを記憶してよい。
【００７５】
ハウスキーピングフィールド１２２は基準が満足されたときにパターン認識プロセッサ１４のステータスを表示するデータを記憶してよい。例えば、ハウスキーピングフィールド１２２は、エラー状態が発生したか否かを指し示すデータを記憶してよい。エラー状態の例は、入力データオーバーフローまたはＦＩＦＯバッファフル状態を含む。ＦＩＦＯバッファ１０２は、例えば、約３２レコード以上、約６４レコード以上、約１２８レコード以上、約２５６レコード以上、または約５１２レコード以上を含んでよい。
【００７６】
リザルトデータ１２４は、どの基準が満足されたのか、基準を満足させたデータストリーム１２からのタームのシーケンス、基準を満足させたデータストリーム１２の部分を示すタームカウント（例えばビットカウント）、またはその間基準を満足させたデータストリームの部分が受信された時間間隔のようなデータを含んでよい。各レコード１１８に記憶されたリザルトデータ１２４は、バンクとして分類される。このバンクは、閾値論理マトリクス４４、論理積マトリクス４６、論理和マトリクス４８、初期化ルーティングマトリクス５０、閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および／または初期化出力マスク１００の各々からの照合結果出力の各々の記憶装置のための個々のレジスタを含んでよい。さらに、照合結果出力は、並列にレジスタバンクに書き込まれてよい。この方法において、各レコード１１８のためのリザルトデータ１２４、換言すれば照合データは、受信されてレジスタバンクに同時に記憶されてよい。そこによって、各々個別のレジスタは、特にそのマトリクスまたはマスクからの明示された結果を個別に記憶してよい。
【００７７】
バッファ書込み制御モジュール１０８は、上りリザルトバス１１０からのどのデータがＦＩＦＯバッファ１０２中のどのレコード１１８に書き込まれるかを制御するように構成されてよい。バッファ書込み制御モジュール１０２は、基準が満足されるごとにまたはリザルトデータが新しいレコード１１８に書き込まれるごとにインクリメントまたはデクリメントするカウンタを含んでよい。バッファ書込み制御モジュールはまた、どのレコード１１８が最も最近にＣＰＵ２０に出力されたかを示すメモリを含んでよく、バッファ書込み制御モジュール１０４は、上りリザルトバス１１０からのデータを、すでにＣＰＵ２０に伝えられたデータを含むレコード１１８に書き込むように構成されてよい。
【００７８】
同様に、バッファ読出し制御モジュール１０６は、どのレコード１１８がＦＩＦＯバッファ１０２から読み出されていない最も古いレコードであるかを指し示すように構成されてよい。例えば、バッファ読出し制御モジュール１０６はレコードがＦＩＦＯバッファから読み出されるごとにインクリメントまたはデクリメントするカウンタを含んでよく、そのカウンタのカウントは最も古く読まれていないレコード１１８を識別してよい。バッファ読出し制御モジュール１０６は、ＣＰＵ２０からの読出し命令信号１２６を受信し、ＦＩＦＯバッファ１０２に対して最も古く読まれていないレコード１１８により記憶されたデータを出力させることによりその読出し命令に応答するように構成されてよい。
【００７９】
リザルトバス１１２は、下りリザルトバス１１２がデータを出力しているのと同時にデータストリーム１２がデータを入力するように、データストリーム１２を伝搬するバスとは異なる導体を含んでよい。リザルトバッファ２５がパターン認識プロセッサ１４と完全に一体に形成される実施形態では、パターン認識プロセッサ１４はデータストリーム１２入力と結果出力を伝搬するための個別のピンを含んでよい。従って、リザルトデータはデータストリームが入力されるのと同時に出力されてよい。
【００８０】
代わりに、リザルトバス１１２は、同じ導体またはピンを使用して、要するに共有バスを使用して、データストリーム１２を受信しリザルトデータを出力してよい。例えば、その共有バスは、その共有バスが同じ導体によって使用されてデータストリーム１２を受信しリザルトデータを出力できるように、多重化されまたはタイムスライス化されてよい。しかしながら、その共有バスが入力データを伝送するように使用される時間は、その共有バスが出力データを伝送するのに使用される時間を超えており、そのようにして出力サイクルよりも多くの入力サイクルが生み出されている。そのようにして、入力サイクルはその共有バスの多重化の間、最高の優先度が与えられてよい。出力サイクルは、時間の許す限り、入力サイクルとして使用されていないタイムスロットに続いてはめ込まれてよい。
【００８１】
動作については、パターン認識プロセッサ１４は、図２−図１３を参照して上述した方法で、データストリーム１２を検索してよく、その検索からの結果はＣＰＵ２０に伝搬される前にリザルトバッファ２５にバッファリングされてよい。基準が満たされたとき、どの基準が満たされたのかを示すデータ、データストリーム１２中のどのタームがその基準を満たしたのかを示すデータ、およびどのデータストリームが検索されたのかを示すデータのような、その基準の充足に関連するデータが、上りリザルトバス１１０を通してリザルトバッファ２５に伝送されてよい。
【００８２】
このデータの受信において、バッファ書込み制御モジュール１０４は、例えば、記憶データをすでにＣＰＵ２０に伝搬されているレコード１１８またはどのデータも記憶していないレコード１１８である幾つかのフリーレコードがＦＩＦＯバッファ１０２内にあるか否かを決定してよい。もしフリーレコードが利用可能でなければ、バッファ書込み制御モジュール１０４は、パターン認識プロセッサ１４に通知してデータストリーム１２を検索することを停止させ、ＣＰＵ２０はＦＩＦＯバッファ１０２中のレコードを通じて動作するので空き時間を創り出してしまうが、ＣＰＵ２０に通知してデータストリーム１２の伝送を休止させてよい。バッファ書込み制御モジュール１０４はまた、現在のまたはその次のレコードのハウスキーピング情報フィールド１２２に、パターン認識プロセッサ１４がリザルトバッファオーバーフロー状態に入ったことを示すデータを記憶させてよい。
【００８３】
バッファ書込み制御モジュール１０４が少なくとも一つのフリーレコード１１８が利用可能であると決定したならば、バッファ書込み制御モジュール１０４は、上りリザルトデータバス１１０からのリザルトデータをそのフリーレコード１１８に書き込んでよい。バッファ書込み制御モジュール１０４は、そのレコード１１８が書き込みが行われたがまだ読出しは行われていないことを示してよく、バッファ書込み制御モジュール１０４は、そのレコード１１８が他の書き込まれたレコードと比較して最新のレコードであることを示してよい。
【００８４】
実質的に同じ時間または他の時間において、ＣＰＵ２０は読出し制御信号１２６をバッファ読出し制御モジュール１０６に送信し、それによってバッファ読出し制御モジュール１０６に対してまだ未読の最も古いレコード１１８内のデータを出力するように通知してよい。このようにして、ＣＰＵ２０は重要なステータスレジスタに対して“ポーリング”して、例えばＣＰＵ２０への伝送のために新しいレコード１１８が利用可能であるか否かを決定してよい。ＣＰＵ２０によるポーリングは、リザルトバッファ２５の内部または外部のいずれかの一つ以上のステータスビットがセットされたか否かの、ＣＰＵ２０を介した決定を生ずる。一つ以上のステータスビットのセッティングは、新たなパターンマッチリザルトデータがＣＰＵ２０による読出しのために利用可能であることを指し示してよい。
【００８５】
バッファ読出し制御モジュール１０６はまた、いくつかの未読のレコード１１８が存在するか否かを決定してよい。未読レコードが存在しないならば、バッファ読出し制御モジュール１０６はＣＰＵ２０に対して目下のところ未読レコードは無いことを通知する。もし未読のレコード１１８が存在するならば、バッファ読出し制御モジュール１０６は、最も古い未読レコードを識別し、その最も古い未読のレコード１１８によって記憶されたデータをＣＰＵ２０に伝搬してよい。これは、ＣＰＵ２０が新たな結果が利用可能であるか否かを“質問”する“ポーリング”方法を構成する。
【００８６】
他の方法として、“割込み処理”が、ＣＰＵ２０が与えられた照合を通知するアクティブ通知方法を構成してよい。この方法において、バッファ読出し制御モジュール１０６は、下りリザルトバス１１２を通じてＣＰＵ２０に、ＣＰＵ２０に通知をしおよび／または割込みを行う通知信号をアクティブに伝送し、これによりＣＰＵ２０に対して一つ以上の利用可能レコード１１８が利用できることを認識させてよい。割込み線（図示していないが、下りリザルトバス１１２の一部とみなされる）が、その通知信号をＣＰＵ２０に伝送するために使用されてよい。
【００８７】
他の実施形態において、バッファ読出し制御モジュール１０６は、最も古い未読のレコード１１８によって記憶されているデータの一部を伝搬してよい。それは例えば、基準が満たされたというデータである。そして、ＣＰＵ２０はそのレコード１１８によって記憶されているデータをより多く要求するか否かを決定してよい。それは例えば、データストリーム１２からのどのタームがその基準を満たしたかというデータである。ＣＰＵ２０は、レコード１１８を終了したとき、バッファ読出し制御モジュール１０６に、そのレコードがもはや必要ないことを通知する。バッファ読出し制御モジュール１０６は、それで、そのレコードが読出しが行われてバッファ書込み制御モジュール１０４によって上書きされても安全であることを示してよい。
【００８８】
リザルトバッファはまた、検索結果処理によって生ずる遅延を減少させる。ＣＰＵ２０が検索結果を受信しまたは処理できるよりも速くデータストリーム１２が検索基準を満たすとき、リザルトバッファ２５は、ＣＰＵ２０が追いつくまでの間、未処理のリザルトデータを記憶してよい。リザルトバッファ２５は、たとえ幾つかの検索基準がほぼ同時に満たされたとしても、ＣＰＵ２０へのリザルトデータの流れをスムーズ化することができ、その結果、ＣＰＵ２０がリザルトバッファ２５によって記憶された検索結果のバックログ（処理残）を処理している間、パターン認識プロセッサ１４はデータストリーム１２を検索することを継続してよい。
【００８９】
それに応じて、リザルトバッファ２５は、データストリーム検索からの結果がリザルトバッファ２５に入力されるのと同時に、リザルトデータをＣＰＵ２０に出力してよい。すなわち、リザルトバッファ２５は、“最も古い”未読レコード１１８からＣＰＵ２０に前もって受信されている結果を伝送している間に、“空の”レコード１１８にデータストリーム検索の結果を受信してよい。これは、バッファ書込み制御モジュール１０４によって制御されながら受信された検索の結果を“空の”レコード１１８に記憶すること、およびバッファ読出し制御モジュール１０６によって制御されながら“最も古い”レコード１１８を読み出すこと、によって成し遂げられる。これは、検索結果処理によって引き起こされる遅延を減少できる。
【００９０】
図１５は、例えばＦＩＦＯ記憶位置０に対するリザルトデータ１２４である、最も古いレコード１１８に対するリザルトデータ１２４に対応してよいリザルトバンク１２８を示す。リザルトバンク１２８は、最も古いレコード１１８がいつでもＣＰＵ２０に対して見える唯一のレコードであるように、リザルトバンク１２８を介して読むことができるＦＩＦＯレコード１１８中への“ウインドウ”であってよい。リザルトバンク１２８のアクセスがひとたび完了すれば、ＣＰＵ２０は、例えば、ＣＰＵ２０がリザルトバンク１２８のレコード１１８（すなわち最も古く記憶されたリザルトデータ１２４）を終了したことを、バッファ読出し制御モジュール１０６に通知してよい。それに応答して、バッファ読出し制御モジュール１０６は、次のレコード１１８すなわちＦＩＦＯ記憶位置１をリザルトバンク１２８に対応する新たな最も古いレコード１１８として見えるようにして、ＦＩＦＯキューを前に進めてよい。このようにして、ＣＰＵ２０はリザルトバンク１２８に対応する現在のレコード１１８を処理することのみができてよい。残りのレコード１１８はＦＩＦＯキューにおいてＣＰＵ２０から隠されたままにされてよい。
【００９１】
リザルトバンク１２８は、レジスタ１３０のグループを含んでよい。このレジスタ１３０のグループは、リザルトデータ１２４を記憶するのに使用されてよい。例えば、レジスタ１３０のグループは、閾値論理マトリクス４４、論理積マトリクス４６、論理和マトリクス４８、初期化ルーティングマトリクス５０、閾値出力マスク９４、積出力マスク９６、和出力マスク９８、および初期化出力マスク１００からの照合結果出力の各々の記憶のための個別のレジスタ１３２−１４６を含んでよい。さらに、レジスタ１３０のグループ中の各レジスタ１３２−１４６は、並列に書き込まれてよい。この方法において、与えられたＦＩＦＯ記憶位置に対応するレコード１１８に対するリザルトデータ１２４は、同時に受信されてレジスタ１３０のグループに記憶されてよく、それによって各個別のレジスタ１３２−１４６は、特にそのマトリクス４４−５０またはマスク９４−１００からの明示された結果を個別に記憶してよい。
【００９２】
本発明は、種々の変形および代替形を受け入れる余地があるが、本明細書では、具体的な実施形態が図面において例として示され、詳細に説明されてきた。しかしながら、本発明は、開示された特定の形式に限定されることを意図されるものではないことを理解されたい。それよりもむしろ、本発明は、以下に添付された請求項によって定義される本発明の精神および範囲内にある全ての変形、均等物および代替物を包含するものである。
【特許請求の範囲】
【請求項１】
少なくとも一部がデータストリーム中の一つ以上の値に対する検索に基づく第１の結果を生成するように適合させられるパターンマッチングマトリクスと、
少なくとも一部が前記第１の結果をフィルタリングすることに基づく第２の結果を生成するように適合させられるマスクモジュールと、
を備えるパターン認識プロセッサと、
前記パターン認識プロセッサによって生成される第１および第２の結果を記憶するように適合させられる複数のファースト−インファースト−アウト（ＦＩＦＯ）記憶位置を含むリザルトバッファと、
を備えることを特徴とするシステム。
【請求項２】
請求項１に記載のシステムであって、前記複数のＦＩＦＯ記憶位置の各々に記憶される前記第１および第２の結果は、各ＦＩＦＯ記憶位置に対応するレジスタバンクに記憶されることを特徴とするシステム。
【請求項３】
請求項２に記載のシステムであって、前記レジスタバンクは、各々が前記第１の結果のうちの一つに対応する照合リザルトデータまたは前記第２の結果のうちの一つに対応するマスクリザルトデータを記憶するように適合させられる複数のレジスタを備えることを特徴とするシステム。
【請求項４】
請求項３に記載のシステムであって、前記パターンマッチングマトリクスは、前記データストリーム中の値の発生を閾値結果として登録し、前記閾値結果を前記第１の結果のサブセットとして前記複数のレジスタのうちの一つのレジスタに出力するように構成される閾値論理マトリクスを含むことを特徴とするシステム。
【請求項５】
請求項４に記載のシステムであって、閾値出力マスクを含む前記マスクモジュールは、
前記閾値論理マトリクスから前記閾値結果を受信し、
前記閾値結果をフィルタ処理し、
前記フィルタ処理された閾値結果を前記第２の結果のサブセットとして前記複数のレジスタのうちの追加のレジスタに出力する、
ように構成されることを特徴とするシステム。
【請求項６】
請求項３に記載のシステムであって、前記パターンマッチングマトリクスは、少なくとも一部が二つ以上の閾値論理マトリクス結果に基づく積結果を生成し、前記積結果を前記第１の結果のサブセットとして前記複数のレジスタのうちの一つのレジスタに出力するように構成される論理積マトリクスを含むことを特徴とするシステム。
【請求項７】
請求項６に記載のシステムであって、積出力マスクを含む前記マスクモジュールは、
前記論理積マトリクスから前記積結果を受信し、
前記受信された積結果をフィルタ処理し、
前記フィルタ処理された積結果を前記第２の結果のサブセットとして前記複数のレジスタのうちの追加のレジスタに出力する、
ように構成されることを特徴とするシステム。
【請求項８】
請求項３に記載のシステムであって、前記パターンマッチングマトリクスは、少なくとも一部が二つ以上の論理積マトリクス結果に基づく和結果を生成し、前記和結果を前記第１の結果のサブセットとして前記複数のレジスタのうちの一つのレジスタに出力するように構成される論理和マトリクスを含むことを特徴とするシステム。
【請求項９】
請求項８に記載のシステムであって、和出力マスクを含む前記マスクモジュールは、
前記論理和マトリクスから前記和結果を受信し、
前記受信された和結果をフィルタ処理し、
前記フィルタ処理された照合を前記第２の結果のサブセットとして前記複数のレジスタのうちの追加のレジスタに出力する、
ように構成されることを特徴とするシステム。
【請求項１０】
請求項３に記載のシステムであって、前記パターンマッチングマトリクスは、検索基準が満たされたと決定したときに初期化結果を登録し、前記初期化結果を前記第１の結果のサブセットとして前記複数のレジスタのうちの一つのレジスタに出力するように構成される初期化ルーティングマトリクスを含むことを特徴とするシステム。
【請求項１１】
請求項１０に記載のシステムであって、初期化出力マスクを含む前記マスクモジュールは、
前記初期化ルーティングマトリクスから前記初期化結果を受信し、
前記受信された初期化結果をフィルタ処理し、
前記フィルタ処理された初期化結果を前記第２の結果のサブセットとして前記複数のレジスタのうちの追加のレジスタに出力する、
ように構成されることを特徴とするシステム。
【請求項１２】
請求項３に記載のシステムであって、前記複数のレジスタの各々は同時に書き込まれてよいことを特徴とするシステム。
【請求項１３】
データストリームを受信し、
パターン認識プロセッサの一つ以上のパターンマッチングマトリクスを介して前記データストリームを検索し、前記一つ以上のパターンマッチングマトリクスは少なくとも一部がデータのストリーム中の一つ以上の値に対応する検索に基づく第１の結果を生成するように適合させられ、
一つ以上のマスクモジュールを介して前記第１の結果をフィルタ処理して第２の結果を生成し、
前記第１および第２の結果をレジスタのグループを備える一つ以上のＦＩＦＯ記憶位置を備えるバッファ中に記憶する、
ことを備えることを特徴とする方法。
【請求項１４】
請求項１３に記載の方法であって、前記一つ以上のマスクモジュールを介して前記第１の結果をフィルタ処理することは、前記第１の結果を前記一つ以上のマスクモジュールのマスクレジスタに記憶された値とアンド演算して前記第２の結果を生成することを備えることを特徴とする方法。
【請求項１５】
請求項１３に記載の方法であって、前記一つ以上のパターンマッチングマトリクスを介して前記データストリームを検索することは、閾値論理マトリクス、論理積マトリクス、論理和マトリクス、および初期化ルーティングマトリクスのうちの一つ以上を介して前記データストリームを検索することを含むことを特徴とする方法。
【請求項１６】
請求項１３に記載の方法であって、前記一つ以上のマスクモジュールを介して前記第１の結果をフィルタ処理することは、閾値出力マスク、積出力マスク、和出力マスク９８、および初期化出力マスクのうちの一つ以上を介して前記第１の結果をフィルタ処理することを含むことを特徴とする方法。
【請求項１７】
請求項１３に記載の方法であって、前記レジスタのグループ中の各レジスタは同時に書き込まれてよいことを特徴とする方法。
【請求項１８】
請求項１３に記載の方法であって、ステータスビットがアクティブ化されたことを決定するとき一つ以上のＦＩＦＯ記憶位置の少なくとも一つにアクセスすることを備え、前記ステータスビットはパターンマッチデータが前記レジスタのグループに記憶されたときにアクティブ化されることを特徴とする方法。
【請求項１９】
請求項１３に記載の方法であって、割込み信号を受信するとき一つ以上のＦＩＦＯ記憶位置の少なくとも一つにアクセスすることを備え、前記割込み信号はパターンマッチデータが前記レジスタのグループに記憶されたことを示すことを特徴とする方法。
【請求項２０】
複数のレジスタを備え、前記複数のレジスタはデータのストリーム中の一つ以上の値に対する検索を介してマッチングマトリクスによって生成される結果データと、前記結果データをフィルタ処理することを介してマスクモジュールによって生成されるマスク結果データを記憶するように適合させられることを特徴とするシステム。
【請求項２１】
請求項２０に記載のシステムであって、前記複数のレジスタは、ファースト−インァースト−アウト順で、レジスタバンクにグループ化されるシステム。
【請求項２２】
請求項２１に記載の方法であって、ステータスビットがアクティブ化されているか否かを決定するとき少なくとも一つの前記レジスタバンクにアクセスするように適合させられるプロセッサを備え、前記ステータスビットは結果データに対応し少なくとも一つのレジスタバンク中の前記複数のレジスタに書き込まれることを特徴とする方法。
【請求項２３】
請求項２１に記載の方法であって、割込み信号を受信し前記割込み信号を受信するとき少なくとも一つの前記レジスタバンクにアクセスするように適合させられるプロセッサを備え、前記割込み信号は結果データに対応し少なくとも一つのレジスタバンク中の前記複数のレジスタに書き込まれることを特徴とする方法。
【請求項１】
少なくとも一部がデータストリーム中の一つ以上の値に対する検索に基づく第１の結果を生成するように適合させられるパターンマッチングマトリクスと、
少なくとも一部が前記第１の結果をフィルタリングすることに基づく第２の結果を生成するように適合させられるマスクモジュールと、
を備えるパターン認識プロセッサと、
前記パターン認識プロセッサによって生成される第１および第２の結果を記憶するように適合させられる複数のファースト−インファースト−アウト（ＦＩＦＯ）記憶位置を含むリザルトバッファと、
を備えることを特徴とするシステム。
【請求項２】
請求項１に記載のシステムであって、前記複数のＦＩＦＯ記憶位置の各々に記憶される前記第１および第２の結果は、各ＦＩＦＯ記憶位置に対応するレジスタバンクに記憶されることを特徴とするシステム。
【請求項３】
請求項２に記載のシステムであって、前記レジスタバンクは、各々が前記第１の結果のうちの一つに対応する照合リザルトデータまたは前記第２の結果のうちの一つに対応するマスクリザルトデータを記憶するように適合させられる複数のレジスタを備えることを特徴とするシステム。
【請求項４】
請求項３に記載のシステムであって、前記パターンマッチングマトリクスは、前記データストリーム中の値の発生を閾値結果として登録し、前記閾値結果を前記第１の結果のサブセットとして前記複数のレジスタのうちの一つのレジスタに出力するように構成される閾値論理マトリクスを含むことを特徴とするシステム。
【請求項５】
請求項４に記載のシステムであって、閾値出力マスクを含む前記マスクモジュールは、
前記閾値論理マトリクスから前記閾値結果を受信し、
前記閾値結果をフィルタ処理し、
前記フィルタ処理された閾値結果を前記第２の結果のサブセットとして前記複数のレジスタのうちの追加のレジスタに出力する、
ように構成されることを特徴とするシステム。
【請求項６】
請求項３に記載のシステムであって、前記パターンマッチングマトリクスは、少なくとも一部が二つ以上の閾値論理マトリクス結果に基づく積結果を生成し、前記積結果を前記第１の結果のサブセットとして前記複数のレジスタのうちの一つのレジスタに出力するように構成される論理積マトリクスを含むことを特徴とするシステム。
【請求項７】
請求項６に記載のシステムであって、積出力マスクを含む前記マスクモジュールは、
前記論理積マトリクスから前記積結果を受信し、
前記受信された積結果をフィルタ処理し、
前記フィルタ処理された積結果を前記第２の結果のサブセットとして前記複数のレジスタのうちの追加のレジスタに出力する、
ように構成されることを特徴とするシステム。
【請求項８】
請求項３に記載のシステムであって、前記パターンマッチングマトリクスは、少なくとも一部が二つ以上の論理積マトリクス結果に基づく和結果を生成し、前記和結果を前記第１の結果のサブセットとして前記複数のレジスタのうちの一つのレジスタに出力するように構成される論理和マトリクスを含むことを特徴とするシステム。
【請求項９】
請求項８に記載のシステムであって、和出力マスクを含む前記マスクモジュールは、
前記論理和マトリクスから前記和結果を受信し、
前記受信された和結果をフィルタ処理し、
前記フィルタ処理された照合を前記第２の結果のサブセットとして前記複数のレジスタのうちの追加のレジスタに出力する、
ように構成されることを特徴とするシステム。
【請求項１０】
請求項３に記載のシステムであって、前記パターンマッチングマトリクスは、検索基準が満たされたと決定したときに初期化結果を登録し、前記初期化結果を前記第１の結果のサブセットとして前記複数のレジスタのうちの一つのレジスタに出力するように構成される初期化ルーティングマトリクスを含むことを特徴とするシステム。
【請求項１１】
請求項１０に記載のシステムであって、初期化出力マスクを含む前記マスクモジュールは、
前記初期化ルーティングマトリクスから前記初期化結果を受信し、
前記受信された初期化結果をフィルタ処理し、
前記フィルタ処理された初期化結果を前記第２の結果のサブセットとして前記複数のレジスタのうちの追加のレジスタに出力する、
ように構成されることを特徴とするシステム。
【請求項１２】
請求項３に記載のシステムであって、前記複数のレジスタの各々は同時に書き込まれてよいことを特徴とするシステム。
【請求項１３】
データストリームを受信し、
パターン認識プロセッサの一つ以上のパターンマッチングマトリクスを介して前記データストリームを検索し、前記一つ以上のパターンマッチングマトリクスは少なくとも一部がデータのストリーム中の一つ以上の値に対応する検索に基づく第１の結果を生成するように適合させられ、
一つ以上のマスクモジュールを介して前記第１の結果をフィルタ処理して第２の結果を生成し、
前記第１および第２の結果をレジスタのグループを備える一つ以上のＦＩＦＯ記憶位置を備えるバッファ中に記憶する、
ことを備えることを特徴とする方法。
【請求項１４】
請求項１３に記載の方法であって、前記一つ以上のマスクモジュールを介して前記第１の結果をフィルタ処理することは、前記第１の結果を前記一つ以上のマスクモジュールのマスクレジスタに記憶された値とアンド演算して前記第２の結果を生成することを備えることを特徴とする方法。
【請求項１５】
請求項１３に記載の方法であって、前記一つ以上のパターンマッチングマトリクスを介して前記データストリームを検索することは、閾値論理マトリクス、論理積マトリクス、論理和マトリクス、および初期化ルーティングマトリクスのうちの一つ以上を介して前記データストリームを検索することを含むことを特徴とする方法。
【請求項１６】
請求項１３に記載の方法であって、前記一つ以上のマスクモジュールを介して前記第１の結果をフィルタ処理することは、閾値出力マスク、積出力マスク、和出力マスク９８、および初期化出力マスクのうちの一つ以上を介して前記第１の結果をフィルタ処理することを含むことを特徴とする方法。
【請求項１７】
請求項１３に記載の方法であって、前記レジスタのグループ中の各レジスタは同時に書き込まれてよいことを特徴とする方法。
【請求項１８】
請求項１３に記載の方法であって、ステータスビットがアクティブ化されたことを決定するとき一つ以上のＦＩＦＯ記憶位置の少なくとも一つにアクセスすることを備え、前記ステータスビットはパターンマッチデータが前記レジスタのグループに記憶されたときにアクティブ化されることを特徴とする方法。
【請求項１９】
請求項１３に記載の方法であって、割込み信号を受信するとき一つ以上のＦＩＦＯ記憶位置の少なくとも一つにアクセスすることを備え、前記割込み信号はパターンマッチデータが前記レジスタのグループに記憶されたことを示すことを特徴とする方法。
【請求項２０】
複数のレジスタを備え、前記複数のレジスタはデータのストリーム中の一つ以上の値に対する検索を介してマッチングマトリクスによって生成される結果データと、前記結果データをフィルタ処理することを介してマスクモジュールによって生成されるマスク結果データを記憶するように適合させられることを特徴とするシステム。
【請求項２１】
請求項２０に記載のシステムであって、前記複数のレジスタは、ファースト−インァースト−アウト順で、レジスタバンクにグループ化されるシステム。
【請求項２２】
請求項２１に記載の方法であって、ステータスビットがアクティブ化されているか否かを決定するとき少なくとも一つの前記レジスタバンクにアクセスするように適合させられるプロセッサを備え、前記ステータスビットは結果データに対応し少なくとも一つのレジスタバンク中の前記複数のレジスタに書き込まれることを特徴とする方法。
【請求項２３】
請求項２１に記載の方法であって、割込み信号を受信し前記割込み信号を受信するとき少なくとも一つの前記レジスタバンクにアクセスするように適合させられるプロセッサを備え、前記割込み信号は結果データに対応し少なくとも一つのレジスタバンク中の前記複数のレジスタに書き込まれることを特徴とする方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公表番号】特表２０１２−５１５３７８（Ｐ２０１２−５１５３７８Ａ）
【公表日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願番号】特願２０１１−５４５３６０（Ｐ２０１１−５４５３６０）
【出願日】平成２１年１２月１６日（２００９．１２．１６）
【国際出願番号】ＰＣＴ／ＵＳ２００９／０６８２８０
【国際公開番号】ＷＯ２０１０／０８０４４５
【国際公開日】平成２２年７月１５日（２０１０．７．１５）
【出願人】（５９５１６８５４３）マイクロン テクノロジー， インク． (444)
【Ｆターム（参考）】
【公表日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願日】平成２１年１２月１６日（２００９．１２．１６）
【国際出願番号】ＰＣＴ／ＵＳ２００９／０６８２８０
【国際公開番号】ＷＯ２０１０／０８０４４５
【国際公開日】平成２２年７月１５日（２０１０．７．１５）
【出願人】（５９５１６８５４３）マイクロン テクノロジー， インク． (444)
【Ｆターム（参考）】
[ Back to top ]