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