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