JP2015507255A - ステートマシンにおけるデータ解析用の方法およびシステム - Google Patents

Abstract

デバイスは、第一の結果を受信するように構成された第一のデータ入力を含むマッチ素子（１６０）を含み、第一の結果は、ステートマシンの素子によってデータストリームの少なくとも一部に実施された解析の結果である。マッチ素子（１６０）は、第二の結果を受信するように構成された第二のデータ入力も含み、第二の結果は、ステートマシンの別の素子によってデータストリームの少なくとも一部に実施された解析の結果である。マッチ素子（１６０）は、第一の結果もしくは第二の結果を選択的に提供するように構成された出力をさらに含む。【選択図】図１１

Description

本発明の実施形態は、概して電子デバイスに関し、より詳細には、ある実施形態においては、パターン認識用のパラレル有限ステートマシンを有する電子デバイスに関する。

複雑なパターン認識は、従来のフォンノイマンベースコンピュータ上で実施するために非効率的である可能性がある。しかしながら、生物学的脳、特に人の脳は、パターン認識の実施に熟達している。現在の研究は、人の脳は、新皮質においてヒエラルキー的に組織化された一連のニューロン（神経細胞）層を利用して、パターン認識を実施することを示唆している。ヒエラルキーのより下層におけるニューロンは、例えば、感覚器官からの“生信号”を解析し、より上層におけるニューロンは、より低いレベルのニューロンからの信号出力を解析する。新皮質におけるこのヒエラルキーシステムは、ことによると脳の他の領域と組み合わせて、空間推論、意識的思考、複雑な言語などの高レベル機能を人が実施することを可能にする複雑なパターン認識を達成する。

コンピューティングの分野においては、パターン認識タスクはますますやりがいのあるものになっている。コンピュータ間でますます大量のデータが伝送され、ユーザが検出を望むパターン数は増加している。例えば、スパムもしくはマルウェアはしばしば、データストリーム内でパターン（例えば、特定の句もしくはコードの一部）を検索することによって検出される。新規パターンが新規変形を検索するために実装されるにつれて、パターン数は、スパムおよびマルウェアの多様性とともに増加する。これらのパターンの各々に対してデータストリームを検索することは、コンピューティングボトルネックを形成する可能性がある。しばしば、データストリームが受信されると、一度に一つずつ各パターンに対してそれが検索される。システムがデータストリームの次の部分を検索するために準備するまでの遅延は、パターン数とともに増加する。したがって、パターン認識は、データの受信を遅延させる可能性がある。

ハードウェアは、パターン用のデータストリームを検索するために設計されてきたが、このハードウェアは、しばしば、与えられた期間において十分なデータ量を処理することができない。データストリームを検索するように構成された幾つかのデバイスは、複数の回路間でデータを分散することによって、十分なデータ量を処理する。回路は、データストリームがパターンの一部にマッチするか否かを各々判定する。しばしば、多数の回路がパラレルに動作して、各々がほぼ同時にデータストリームを検索する。しかしながら、生物学的脳以上に効率的にパターン認識を実施することが可能なシステムは存在しなかった。そのようなシステムの開発が望ましい。

本発明の種々の実施形態に従うステートマシンエンジンを有するシステムの一実施例を示す。 本発明の種々の実施形態に従う、図１のステートマシンエンジンのＦＳＭラチスの一実施例を示す。 本発明の種々の実施形態に従う、図２のＦＳＭラチスのブロックの一実施例を示す。 本発明の種々の実施形態に従う、図３のブロックの行の一実施例を示す。 本発明の種々の実施形態に従う、図４の行のうちの２のグループの一実施例を示す。 本発明の種々の実施形態に従う、有限ステートマシングラフの一実施例を示す。 本発明の種々の実施形態に従う、ＦＳＭラチスで実現された２レベルヒエラルキーの一実施例を示す。 本発明の種々の実施形態に従う、コンパイラが図２のＦＳＭラチスのプログラミング用のバイナリファイルへとソースコードを変換するための方法の一実施例を示す。 本発明の種々の実施形態に従う、ステートマシンエンジンを示す。 本発明の種々の実施形態に従う、図３のブロックの行の第二の実施例を示す。 本発明の種々の実施形態に従う、図１０のマッチ素子の一実施例を示す。 本発明の種々の実施形態に従う、図１１のマルチプレクサに対応する真理値表を示す。

続いて図面に関連して、図１は、参照番号１０によって概して示されるプロセッサベースシステムの一実施形態を示す。システム１０は、デスクトップコンピュータ、ラップトップコンピュータ、ページャ、携帯電話、パーソナルオーガナイザ、ポータブル音声プレイヤー、制御回路、カメラなどの種々のタイプのうちの任意のものであってもよい。システム１０は、ルータ、サーバ、クライアントなどのネットワークノード（例えば、前述されたタイプのコンピュータのうちの一つ）であってもよい。システム１０は、コピー機、スキャナ、プリンタ、ゲーム機、テレビ、セットトップビデオ配信もしくは録画システム、ケーブルボックス、パーソナルデジタルメディアプレイヤー、工場オートメーションシステム、乗用車コンピュータシステム、医療デバイスなどの、幾つかの他の種類の電子デバイスであってもよい。（本明細書で使用される他の用語のうちの多くと同様に、これらの種々のシステムの実施例を記述するために使用される用語は、幾つかの指示物を共有し、それゆえ、記載された他の品目があるからという理由で狭小に解釈されるべきではない。）

システム１０などの典型的なプロセッサベースデバイスにおいては、マイクロプロセッサなどのプロセッサ１２は、システム１０におけるシステム機能および要求の処理を制御する。さらには、プロセッサ１２は、システム制御を共有する複数のプロセッサを含んでもよい。プロセッサ１２がシステム１０内に格納されうるか、システム１０の外部に格納されうる命令を実行することによってシステム１０を制御するように、プロセッサ１２は、システム１０における構成要素のうちの各々に直接もしくは間接的に結合されてもよい。

本明細書で記述された実施形態に従い、システム１０は、ステートマシンエンジン１４を含み、ステートマシンエンジン１４はプロセッサ１２の制御下で動作してもよい。ステートマシンエンジン１４は、Ｍｅａｌｙアーキテクチャ、Ｍｏｏｒｅアーキテクチャ、有限ステートマシン（ＦＳＭ）、決定論的ＦＳＭ（ＤＦＳＭ）、ビット・パラレルステートマシン（ＢＰＳＭ）などを含むがそのいずれにも限定はされない多数のステートマシンアーキテクチャのうちの任意のアーキテクチャを使用してもよい。議論する目的用に種々のアーキテクチャが使用されてもよいが、アプリケーションはＦＳＭに言及する。しかしながら、記述された技術は、種々のステートマシンアーキテクチャのうちの任意のアーキテクチャを利用して使用されうることが当業者には理解されるであろう。

以下にさらに議論されるように、ステートマシンエンジン１４は、多数（例えば一つ以上）の有限ステートマシン（ＦＳＭ）ラチスを含んでもよい。各ＦＳＭラチスは、各々が同一のデータをパラレルに受信して解析する複数のＦＳＭを含んでもよい。さらには、ＦＳＭラチスのクラスタが同一の入力データをパラレルに解析しうるようにＦＳＭラチスは、グループ（例えばクラスタ）で配列されてもよい。さらには、ステートマシンエンジン１４のＦＳＭラチスのクラスタはヒエラルキー構造に配列され、ヒエラルキー構造のより低レベルにおけるステートマシンラチスからの出力は、より高レベルにおけるステートマシンラチスに対する入力として使用されてもよい。ヒエラルキー構造を通して直列にステートマシンエンジン１４のパラレルＦＳＭラチスのクラスタをカスケード接続することによって、より多くの複雑なパターンが解析される（例えば、評価され、検索されるなど）可能性がある。

さらには、ステートマシンエンジン１４のヒエラルキーパラレル構造に基づいて、ステートマシンエンジン１４は、高い処理速度を利用するシステムにおいてパターン認識用に使用することができる。例えば、本明細書で記述される実施形態は、１Ｇバイト／秒の処理速度を有するシステムで組み込まれてもよい。したがって、ステートマシンエンジン１４を利用して、高速メモリデバイスもしくは他の外部デバイスからのデータは、種々のパターンに対して迅速に解析される可能性がある。ステートマシンエンジン１４は、幾つかの基準および其々の検索語に従ってデータストリームを、ほぼ同時に（例えば、単一のデバイスサイクル間に）解析してもよい。ステートマシンエンジン１４のレベル上のＦＳＭのクラスタ内の各ＦＳＭラチスは、ほぼ同時にデータストリームから同一の検索語を各々受信して、各パラレルＦＳＭラチスは、当該用語が処理基準における次の状態へとステートマシンエンジン１４を進めるか否かを判定してもよい。ステートマシンエンジン１４は、比較的多数の基準（例えば、１００以上、１１０以上もしくは１００００以上）に従って用語を解析してもよい。それらはパラレルに動作するため、データストリームを遅くすることなく、比較的高いバンド幅を有するデータストリーム（例えば、１Ｇバイト／秒以上のデータストリーム）に対して基準を適用してもよい。

一実施形態においては、ステートマシンエンジン１４は、データストリームにおける多数のパターンを認識する（例えば検出する）ように構成されてもよい。例えば、ステートマシンエンジン１４は、ユーザもしくは他のエンティティが解析を望む種々のタイプのデータストリームのうちの一つ以上におけるパターンを検出するために使用されてもよい。例えば、ステートマシンエンジン１４は、インターネット上で受信されたパケット、携帯電話ネットワーク上で受信された音声もしくはデータなどのネットワーク上で受信されたデータストリームを解析するように構成されてもよい。一実施例においては、ステートマシンエンジン１４は、スパムもしくはマルウェア用のデータストリームを解析するように構成されてもよい。データストリームは、シリアルデータストリームとして受信され、データは、時間的、単語的、意味的に重要な順序など、意味のある順序で受信される。あるいは、データストリームは、パラレルもしくは順序に関係なく受信され、その後、例えば、インターネット上で受信されたパケットを再配列することによってシリアルデータストリームに変換されてもよい。幾つかの実施形態においては、データストリームはシリアルに用語を提示するが、各用語を表すビットはパラレルに受信されてもよい。データストリームはシステム１０へと外部ソースから受信されるか、メモリ１６などのメモリデバイスからデータを得て、メモリ１６内に格納されたデータからデータストリームを形成することによって形成されてもよい。他の実施例においては、ステートマシンエンジン１４は、ある単語を綴る文字シーケンス、遺伝子を特定する遺伝子塩基対のシーケンス、画像の一部を形成する画像もしくはビデオファイルにおけるビットのシーケンス、プログラムの一部を形成する実行可能なファイルにおけるビットのシーケンス、または、歌もしくは発話フレーズの一部を形成する音声ファイルにおけるビットのシーケンスを認識するように構成されてもよい。解析されるべきデータストリームは、例えば、ベーステン、ＡＳＣＩＩなどのバイナリフォーマットもしくは他のフォーマットにおける複数ビットのデータを含んでもよい。ストリームは、例えば幾つかのバイナリデジットなどの単一デジットもしくは複数デジットを有するデータをエンコードしてもよい。

理解されるように、システム１０はメモリ１６を含んでもよい。メモリ１６は、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、同期式ＤＲＡＭ（ＳＤＲＡＭ）、ダブルデータレートＤＲＡＭ（ＤＤＲ ＤＲＡＭ）、ＤＤＲ２ ＳＤＲＡＭ、ＤＤＲ３ ＳＤＲＡＭなどの揮発性メモリを含んでもよい。メモリ１６は、揮発性メモリと組み合わせて使用するための、リードオンリーメモリ（ＲＯＭ）、ＰＣ−ＲＡＭ、シリコン・酸化物・窒化物・酸化物・シリコン（ＳＯＮＯＳ）メモリ、金属・酸化物・窒化物・酸化物・シリコン（ＭＯＮＯＳ）メモリ、ポリシリコン浮遊ゲートベースメモリおよび／もしくは種々のアーキテクチャの他のタイプのフラッシュメモリ（例えば、ＮＡＮＤメモリ、ＮＯＲメモリなど）などの不揮発性メモリをも含んでもよい。メモリ１６は、ステートマシンエンジン１４によって解析されるデータを提供しうるＤＲＡＭデバイスなどの一つ以上のメモリデバイスを含んでもよい。当該デバイスは、ソリッドステートドライブ（ＳＳＤ’ｓ）、マルチメディアメディアカード（ＭＭＣ’ｓ）、セキュアデジタル（ＳＤ）カード、コンパクトフラッシュ（登録商標）（ＣＦ）カード、もしくは任意の他の適切なデバイスと称されるか、またはそれらを含んでもよい。さらには、当該デバイスはユニバーサルシリアルバス（ＵＳＢ）、ペリフェラルコンポーネントインターコネクト（ＰＣＩ）、ＰＣＩエクスプレス（ＰＣＩ−Ｅ）、スモールコンピュータシステムインターフェイス（ＳＣＳＩ）、ＩＥＥＥ１３９４（ファイアワイヤ）もしくは任意の他の適切なインターフェイスなどの任意の適切なインターフェイスを介してシステム１０へと結合しうることを理解されるべきである。フラッシュメモリデバイスなどのメモリ１６の動作を容易にするために、システム１０は、（図示されていない）メモリコントローラを含んでもよい。理解されるように、メモリコントローラは、独立したデバイスであるか、プロセッサ１２と一体であってもよい。さらには、システム１０は、磁気記憶デバイスなどの外部ストレージ１８を含んでもよい。外部ストレージもまた、ステートマシンエンジン１４に入力データを提供してもよい。

システム１０は、多数のさらなる構成要素を含んでもよい。例えば、コンパイラ２０は、図８に関連してより詳細に記述されるように、ステートマシンエンジン１４をプログラムするために使用されてもよい。入力デバイス２２は、ユーザがシステム１０にデータを入力することを可能にするために、プロセッサ１２に結合されてもよい。例えば、入力デバイス２２は、ステートマシンエンジン１４によるその後の解析用にメモリ１６へとデータを入力するために使用されてもよい。入力デバイス２２は、ボタン、スイッチング素子、キーボード、ライトペン、スタイラス、マウスおよび／もしくは音声認識システムを例えば含んでもよい。ディスプレイなどの出力デバイス２４も、プロセッサ１２に結合されてもよい。ディスプレイ２４は、例えば、ＬＣＤ、ＣＲＴ、ＬＥＤおよび／もしくは音声ディスプレイを含んでもよい。システムは、インターネットなどのネットワークとインターフェイスを介して接続するために、ネットワークインターフェイスカード（ＮＩＣ）などのネットワークインターフェイスデバイス２６を含んでもよい。理解されるように、システム１０は、システム１０の用途に依存して、多くの他のコンポーネントを含んでもよい。

図２−図５は、ＦＳＭラチス３０の一実施例を示す。一実施例においては、ＦＳＭラチス３０は、ブロック３２のアレイを含む。記述されるように、各ブロック３２は、ＦＳＭにおける複数の状態に対応する複数の選択的に結合可能なハードウェア素子（例えば、プログラマブル素子および／もしくは専用素子）を含んでもよい。ＦＳＭにおける状態に類似して、ハードウェア素子は、入力ストリームを解析して、入力ストリームに基づいて下流（ダウンストリーム）ハードウェア素子をアクティブ化することができる。

プログラマブル素子は、多くの異なる機能を実施するためにプログラムすることができる。例えば、プログラマブル素子は、行３８（図３および図４に示される）とブロック３２（図２および図３に示される）へとヒエラルキー的に組織化されたステートマシン素子（ＳＭＥ）３４、３６（図５に示される）を含んでもよい。ヒエラルキー的に組織化されたＳＭＥ３４、３６の間で信号をルーティングするために、ブロック間スイッチング素子４０（図２および図３に示される）、ブロック内スイッチング素子４２（図３および図４に示される）、行内スイッチング素子４４（図４に示される）を含むプログラマブルスイッチング素子のヒエラルキーが使用される可能性がある。

以下に記述されるように、スイッチング素子は、ルーティング構造およびバッファを含んでもよい。ＳＭＥ３４、３６は、ＦＳＭラチス３０によって実現されるＦＳＭの状態に対応する可能性がある。ＳＭＥ３４、３６は、以下に記述されるようなプログラマブルスイッチング素子を利用することによってともに結合することができる。したがって、ＦＳＭは、状態の機能に対応するために、ＳＭＥ３４、３６をプログラムすることによって、かつ、ＦＳＭにおける状態間の遷移に対応するためにＳＭＥ３４、３６をともに選択的に結合することによって、ＦＳＭラチス３０上で実現することができる。

図２は、ＦＳＭラチス３０の一実施例の全体図を示す。ＦＳＭラチス３０は、プログラマブルブロック間スイッチング素子４０とともに選択的に結合することができる複数のブロック３２を含む。ブロック間スイッチング素子４０は、導体４６（例えば、ワイヤ、トレースなど）およびバッファ４８、５０を含んでもよい。一実施例においては、バッファ４８および５０は、ブロック間スイッチング素子４０とやり取りする信号の接続およびタイミングを制御するために含まれる。以下にさらに記述されるように、バッファ４８は、ブロック３２間で送信されるデータをバッファするために提供され、バッファ５０は、ブロック間スイッチング素子４０間で送信されるデータをバッファするために提供されてもよい。さらには、ブロック３２は、信号（例えばデータ）を受信し、ブロック３２へとデータを提供するために入力ブロック５２（例えばデータ入力ポート）へと選択的に結合することができる。ブロック３２は、外部デバイス（例えば、別のＦＳＭラチス３０）へとブロック３２からの信号を提供するために、出力ブロック５４（例えば、出力ポート）へも選択的に結合することができる。ＦＳＭラチス３０は、ＦＳＭラチス３０上のプログラム（例えば、画像）をロードするためにプログラミングインターフェイス５６を含んでもよい。画像は、ＳＭＥ３４、３６の状態をプログラム（例えば設定）することができる。即ち、画像は、入力ブロック５２において与えられた入力にある方法で反応するようにＳＭＥ３４、３６を構成することができる。例えば、ＳＭＥ３４、３６は、文字‘ａ’が入力ブロック５２で受信されるとき、ハイ信号を出力するように設定することができる。

一実施例においては、入力ブロック５２、出力ブロック５４および／もしくはプログラミングインターフェイス５６は、レジスタとして実現され、レジスタへの書き込みもしくはレジスタからの読み出しは、其々の素子へのデータもしくは其々の素子からのデータを提供する。したがって、プログラミングインターフェイス５６に対応するレジスタに格納された画像からのビットは、ＳＭＥ３４、３６上でロードすることができる。図２は、ブロック３２、入力ブロック５２、出力ブロック５４、ブロック間スイッチング素子４０間で、ある数の導体（例えば、ワイヤ、トレース）を示しているが、他の実施例においては、より少ないかより多い数の導体が使用されてもよいことを理解されたい。

図３は、ブロック３２の一実施例を示す。ブロック３２は、プログラマブルブロック内スイッチング素子４２と選択的に結合することができる複数の行３８を含む可能性がある。さらには、行３８は、ブロック間スイッチング素子４０で、別のブロック３２内の別の行３８へと選択的に結合することができる。行３８は、本明細書においては、２のグループ（ＧＯＴ）６０と称される素子の対へと組織化された複数のＳＭＥ３４、３６を含む。一実施例においては、ブロック３２は、１６個の行３８を含む。

図４は、行３８の一実施例を示す。ＧＯＴ６０は、プログラマブル行内スイッチング素子４４によって、行３８内の任意の他の素子（例えば、専用素子５８）および他のＧＯＴ６０へと選択的に結合することができる。ＧＯＴ６０は、ブロック内スイッチング素子４２で他の行３８における他のＧＯＴ６０へと、または、ブロック間スイッチング素子４０によって他のブロック３２における他のＧＯＴ６０へと結合することができる。一実施例においては、ＧＯＴ６０は、第一の入力６２、第二の入力６４、出力６６を有する。図５に関連してさらに示されるように、第一の入力６２は、ＧＯＴ６０の第一のＳＭＥ３４へと結合され、第二の入力６２は、ＧＯＴ６０の第二のＳＭＥ３４へと結合される。

一実施例においては、行３８は、第一および第二の複数の行相互接続導体６８、７０を含む。一実施例においては、ＧＯＴ６０の入力６２、６４は、一つ以上の行相互接続導体６８、７０へと結合され、出力６６は、一つの行相互接続導体６８、７０へと結合される可能性がある。一実施例においては、第一の複数の行相互接続導体６８は、行３８内の各ＧＯＴ６０の各ＳＭＥ３４、３６へと結合することができる。第二の複数の行相互接続導体７０は、行３８内の各ＧＯＴ６０のうちの唯一つのＳＭＥ３４、３６へと結合することができるが、ＧＯＴ６０の他方のＳＭＥ３４、３６へは結合することができない。一実施例においては、図５に関連してより明瞭に示されるように、第二の複数の行相互接続導体７０のうちの前半（第一の半分）は、行３８内のＳＭＥ３４、３６のうちの前半（各ＧＯＴ６０からの一つのＳＭＥ３４）に結合することができ、第二の複数の行相互接続導体７０のうちの後半（第二の半分）は、行３８内のＳＭＥ３４、３６のうちの後半（各ＧＯＴ６０の他のＳＭＥ３４、３６）に結合することができる。第二の複数の行相互接続導体７０とＳＭＥ３４、３６との間の限定された接続は、本明細書においては、“パリティ”と称される。一実施例においては、行３８は、カウンタ、プログラマブルブール型論理素子、ルックアップテーブル、ＲＡＭ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、プログラマブルプロセッサ（例えば、マイクロプロセッサ）もしくは専用機能を実施するための他の素子などの専用素子５８を含む可能性がある。

一実施例においては、専用素子５８は、カウンタ（本明細書においては、カウンタ５８とも称される）を含む。一実施例においては、カウンタ５８は１２ビットプログラマブルダウンカウンタを含む。１２ビットプログラマブルカウンタ５８は、カウンティング入力、リセット入力、ゼロカウント出力を有する。カウンティング入力は、アサートされると、１ずつカウンタ５８の値をデクリメントする。リセット入力は、アサートされると、関連するレジスタからの初期値をカウンタ５８にロードさせる。１２ビットカウンタ５８に対して、１２ビットの数までが初期値としてロードすることができる。カウンタ５８の値がゼロ（０）までデクリメントされると、ゼロカウント出力がアサートされる。カウンタ５８は、少なくとも二つのモードであるパルスおよびホールドをも有する。カウンタ５８がパルスモードに設定されると、カウンタ５８がゼロへデクリメントするとき、クロックサイクル中にゼロカウント出力がアサートされ、次のクロックサイクルにおいて、ゼロカウント出力はもはやアサートされない。カウンタ５８がホールドモードに設定されると、カウンタ５８がゼロへデクリメントするとき、クロックサイクル中にゼロカウント出力がアサートされ、アサートされたリセット入力によってカウンタ５８がリセットされるまでアサートされたままである。

別の実施例においては、専用素子５８は、ブール型論理を含む。幾つかの実施例においては、このブール型論理は、ＦＳＭラチス３０における（本明細書でこの後議論されるようなＦＳＭの端末ノードに対応する）端末状態ＳＭＥからの情報を抽出するために使用することができる。抽出された情報は、他のＦＳＭラチス３０に状態情報を伝送するために、および／もしくはＦＳＭラチス３０を再プログラムするか別のＦＳＭラチス３０を再プログラムするために使用されるプログラミング情報を伝送するために、使用することができる。

図５は、ＧＯＴ６０の一実施例を示す。ＧＯＴ６０は、入力６２、６４を有し、ＯＲゲート７６および３：１マルチプレクサ７８に結合された出力７２、７４を有する第一のＳＭＥ３４、第二のＳＭＥ３６を含む。３：１マルチプレクサ７８は、第一のＳＭＥ３４、第二のＳＭＥ３６、もしくはＯＲゲート７６のいずれかへとＧＯＴ６０の出力６６を結合するように設定することができる。ＯＲゲート７６は、ＧＯＴ６０の共通出力６６を形成するために双方の出力７２、７４を結合するために使用することができる。一実施例においては、第一および第二のＳＭＥ３４、３６は、上述されたようなパリティを示し、第一のＳＭＥ３４の入力６２は行相互接続導体６８の幾つかに結合され、第二のＳＭＥ３６の入力６４は、他の行相互接続導体７０へと結合される可能性がある。一実施例においては、ＧＯＴ６０内の二つのＳＭＥ３４、３６はカスケード接続されるか、および／もしくはスイッチング素子７９のいずれかもしくは双方を設定することによってそれ自身にループバックされる可能性がある。ＳＭＥ３４、３６は、ＳＭＥ３４、３６の出力７２、７４を他のＳＭＥ３４、３６の入力６２、６４へと結合することによってカスケード接続することができる。ＳＭＥ３４、３６は、出力７２、７４をそれら自身の入力６２、６４へと接続することによって、自身へとループバックすることができる。したがって、第一のＳＭＥ３４の出力７２は、第一のＳＭＥ３４の入力６２および第二のＳＭＥ３６の入力６４のうちの一つもしくはその双方に結合されるか、何れにも結合されない可能性がある。

一実施例においては、ステートマシン素子３４、３６は、検出ライン８２へとパラレルに結合されたダイナミックランダムアクセスメモリ（ＤＲＡＭ）でしばしば利用されるような複数のメモリセル８０を含む。当該メモリセル８０のうちの一つは、ハイもしくはロウの値（例えば、１もしくは０）のいずれかに対応するような、データ状態に設定することのできるメモリセルを含む。メモリセル８０の出力は、検出ライン８２に結合され、メモリセル８０の入力は、データストリームライン８４上のデータに基づいて信号を受信する。一実施例においては、データストリームライン８４上の入力は、メモリセル８０のうちの選択された一つへとデコードされる。選択されたメモリセル８０は、検出ライン８２上の出力としてその格納されたデータ状態を提供する。例えば、入力ブロック５２で受信されたデータは、（図示されていない）デコーダへと提供され、デコーダは、データストリームライン８４のうちの一つを選択することができる。一実施例においては、デコーダは、２５６本のデータストリームライン８４のうちの対応する１本へと、８ビットＡＣＳＩＩ文字を変換することができる。

メモリセル８０は、したがって、メモリセル８０がハイ値に設定されると検出ライン８２へとハイ信号を出力して、データストリームライン８４上のデータはメモリセル８０に対応する。データストリームライン８４上のデータがメモリセル８０に対応し、メモリセル８０がロウ値へと設定されるとき、メモリセル８０は検出ライン８２へとロウ信号を出力する。検出ライン８２上のメモリセル８０からの出力は、検出セル８６によって検知される。

一実施例においては、入力ライン６２、６４上の信号は、アクティブもしくは非アクティブ状態のいずれかに其々の検出セル８６を設定する。非アクティブ状態に設定されると、検出セル８６は、其々の検出ライン８２上の信号に関わらず、其々の出力７２、７４上にロウ信号を出力する。アクティブ状態に設定されると、検出セル８６は、ハイ信号が其々のＳＭＥ３４、３６のメモリセル８２のうちの一つから検出されると、其々の出力ライン７２、７４上にハイ信号を出力する。アクティブ状態においては、其々のＳＭＥ３４、３６のメモリセル８２の全てからの信号がロウであるとき、検出セル８６は、其々の出力ライン７２、７４上にロウ信号を出力する。

一実施例においては、ＳＭＥ３４、３６は、２５６個のメモリセル８０を含み、各メモリセル８０は、異なるデータストリームライン８４に結合される。したがって、ＳＭＥ３４、３６は、データストリームライン８４の選択された一つ以上がその上にハイ信号を有するときにハイ信号を出力するようにプログラムすることができる。例えば、ＳＭＥ３４は、ハイに設定された第一のメモリセル８０（例えばビット０）と、ロウに設定された他の全てのメモリセル８０（例えば、ビット１−２５５）を有する可能性がある。其々の検出セル８６がアクティブ状態にあるとき、ビット０に対応するデータストリームライン８４がその上にハイ信号を有すると、ＳＭＥ３４は出力７２上にハイ信号を出力する。他の実施例においては、複数のデータストリームライン８４のうちの一つが、適切なメモリセル８０をハイ値に設定することによってハイ信号をその上に有すると、ＳＭＥ３４は、ハイ信号を出力するように設定することができる。

一実施例においては、メモリセル８０は関連するレジスタからのビットを読み出すことによって、ハイもしくはロウ値へと設定することができる。したがって、ＳＭＥ３４は、レジスタへとコンパイラ２０によって生成された画像を格納して、関連するメモリセル８０へとレジスタ内のビットをロードすることによってプログラムすることができる。一実施例においては、コンパイラ２０によって生成された画像は、ハイおよびロウ（例えば、１および０）ビットのバイナリ画像を含む。画像は、ＳＭＥ３４、３６をカスケード接続することによって、ＦＳＭとして動作させるために、ＦＳＭラチス３０をプログラムすることができる。例えば、第一のＳＭＥ３４は、検出セル８６をアクティブ状態に設定することによって、アクティブ状態に設定することができる。第一のＳＭＥ３４は、ビット０に対応するデータストリームライン８４がその上にハイ信号を有するとき、ハイ信号を出力するように設定することができる。第二のＳＭＥ３６は、最初に非アクティブ状態に設定されるが、ビット１に対応するデータストリームライン８４がその上にハイ信号を有するとき、アクティブになり、ハイ信号を出力するように設定することができる。第一のＳＭＥ３４および第二のＳＭＥ３６は、第一のＳＭＥ３４の出力７２を第二のＳＭＥ３６の入力６４へと結合するように設定することによって、カスケード接続することができる。したがって、ハイ信号が、ビット０に対応するデータストリームライン８４上に検知されると、第一のＳＭＥ３４は、出力７２上にハイ信号を出力して、第二のＳＭＥ３６の検出セル８６をアクティブ状態に設定する。ビット１に対応するデータストリームライン８４上にハイ信号が検知されると、第二のＳＭＥ３６は、別のＳＭＥ３６をアクティブ化するため、もしくはＦＳＭラチス３０からの出力用に出力７４上にハイ信号を出力する。

一実施例においては、単一のＦＳＭラチス３０は、単一の物理デバイス上に実現されるが、他の実施例においては、二つ以上のＦＳＭラチス３０が単一の物理デバイス（例えば物理チップ）上に実現される可能性がある。一実施例においては、各ＦＳＭラチス３０は、別個のデータ入力ブロック５２、別個の出力ブロック５４、別個のプログラミングインターフェイス５６、別個のプログラミング素子の組を含む可能性がある。さらには、プログラマブル素子の各組は、その対応するデータ入力ブロック５２におけるデータに対して反応する（例えば、ハイもしくはロウ信号を出力する）ことができる。例えば、第一のＦＳＭラチス３０に対応する第一組のプログラマブル素子は、第一のＦＳＭラチス３０に対応する第一のデータ入力ブロック５２におけるデータに対して反応することができる。第二のＦＳＭラチス３０に対応する第二組のプログラマブル素子は、第二のＦＳＭラチス３０に対応する第二のデータ入力ブロック５２に対して反応することができる。したがって、各ＦＳＭラチス３０は、一組のプログラマブル素子を含み、異なる組のプログラマブル素子は、異なる入力データに反応することができる。同様に、各ＦＳＭラチス３０および各対応する組のプログラマブル素子は、個別出力を提供することができる。幾つかの実施例においては、第一のＦＳＭラチス３０からの出力ブロック５４は、第二のＦＳＭラチス３０の入力ブロック５２に結合することができ、第二のＦＳＭラチス３０用の入力データは、一連のＦＳＭラチス３０のヒエラルキー配列における第一のＦＳＭラチス３０からの出力データを含むことができる。

一実施例においては、ＦＳＭラチス３０にロードするための画像は、ＦＳＭラチス３０内のプログラマブル素子、プログラマブルスイッチング素子、専用素子を構成するための複数ビットの情報を含む。一実施例においては、画像は、ある入力に基づいて、所望の出力を提供するために、ＦＳＭラチス３０をプログラムするために、ＦＳＭラチス３０上にロードすることができる。出力ブロック５４は、データ入力ブロック５２におけるデータ対して、プログラマブル素子の反応に基づいて、ＦＳＭラチス３０からの出力を提供することができる。出力ブロック５４からの出力は、任意のパターンのマッチを示す単一ビット、複数のパターンのマッチ（一致）および不一致を示す複数ビットを含む語、任意の瞬間における全てもしくはあるプログラマブル素子の状態に対応する状態ベクトルを含む可能性がある。記述されるように、多数のＦＳＭラチス３０は、ステートマシンエンジン１４などのステートマシンエンジンに含まれ、パターン認識（例えば、音声認識、画像認識など）、信号処理、画像処理、コンピュータビジョン、クリプトグラフィーなどのデータ解析を実施する。

図６は、ＦＳＭラチス３０によって実現できる有限ステートマシン（ＦＳＭ）の例示的な一モデルを示す。ＦＳＭラチス３０は、ＦＳＭの物理的実装として構成される（例えばプログラムされる）可能性がある。ＦＳＭは、一つ以上のルートノード９２を含む図形９０（例えば、有向グラフ、無向グラフ、擬グラフ）として表すことができる。ルートノード９２に加えて、ＦＳＭは、幾つかの標準ノード９４と、一つ以上の辺９８を通してルートノード９２および他の標準ノード９４に接続される端末ノード９６とで形成される可能性がある。ノード９２、９４、９６はＦＳＭにおける状態に対応する。辺９８は、状態間の遷移に対応する。

各ノード９２、９４、９６は、アクティブもしくは非アクティブ状態のいずれかにある可能性がある。非アクティブ状態にあるとき、ノード９２、９４、９６は入力データに対して反応（例えば応答）しない。アクティブ状態にあるとき、ノード９２、９４、９６は入力データに対して反応できる。上流ノード９２、９４は、上流ノード９２、９４と下流ノード９４、９６の間の辺９８によって特定される基準に入力データがマッチするときに、ノードから下流にあるノード９４、９６をアクティブ化することによって入力データに対して反応できる。例えば、第一のノード９４がアクティブであり、かつ文字‘ｂ’が入力データとして受信されるとき、文字‘ｂ’を特定する第一のノード９４は、辺９８によって第一のノード９４へと接続された第二のノード９４をアクティブ化する。本明細書で使用されるような“上流”は、一つ以上のノード間の関係を称し、一つ以上の他のノードの上流（ループもしくはフィードバック構成の場合にはそれ自身の上流）である第一のノードとは、第一のノードが他の一つ以上のノードをアクティブ化できる（もしくはループの場合にはそれ自身をアクティブ化できる）状況のことを称する。同様に、“下流”とは、他の一つ以上のノードの下流（ループの場合にはそれ自身の下流）にある第一のノードが一つ以上の他のノードによってアクティブ化されうる（ループの場合にはそれ自身によってアクティブ化されうる）関係を称する。したがって、“上流”および“下流”という用語は、本明細書においては、一つ以上のノード間の関係を称するために使用されるが、これらの用語は、ノード間のループもしくは他の非線形経路の利用を排除することはない。

図形９０においては、ルートノード９２は最初にアクティブ化され、入力データがルートノード９２からの辺９８とマッチするとき、下流ノード９４をアクティブ化することができる。ノード９４は、ノード９４からの辺９８に入力データがマッチするとき、ノード９６をアクティブ化することができる。図形９０中のノード９４、９６は、入力データが受信されると、この方法でアクティブ化することができる。端末ノード９６は、入力データによる興味あるシーケンスのマッチに対応する。したがって、端末ノード９６のアクティブ化は、入力データとして、興味あるシーケンスが受信されたことを示す。パターン認識機能を実現するＦＳＭラチス３０の状況においては、端末ノード９６への到着は興味ある特定のパターンが入力データにおいて検出されたことを示す可能性がある。

一実施例においては、各ルートノード９２、標準ノード９４、端末ノード９６は、ＦＳＭラチス３０におけるプログラマブル素子に対応する可能性がある。各辺９８は、プログラマブル素子間の接続に対応する可能性がある。したがって、別の標準ノード９４もしくは端末ノード９６に遷移する（例えば、別の標準ノード９４もしくは端末ノード９６に接続する辺９８を有する）標準ノード９４は、別のプログラマブル素子へと遷移する（例えば、別のプログラマブル素子へと出力を提供する）プログラマブル素子に対応する。幾つかの実施例においては、ルートノード９２は、対応するプログラマブル素子を有しない。

ＦＳＭラチス３０がプログラムされると、各プログラマブル素子は、アクティブか非アクティブ状態のいずれかにある可能性がある。任意のプログラマブル素子は、非アクティブなとき、対応するデータ入力ブロック５２において入力データに反応しない。アクティブなプログラマブル素子は、データ入力ブロック５２において入力データに反応し、入力データがプログラマブル素子の設定にマッチするとき、下流プログラマブル素子をアクティブ化することができる。プログラマブル素子が端末ノード９６に対応するとき、プログラマブル素子は、外部デバイスへマッチの指示を提供するために、出力ブロック５４に結合される可能性がある。

プログラミングインターフェイス５６を介してＦＳＭラチス３０上にロードされた画像は、プログラマブル素子と専用素子との間の接続と同様、プログラマブル素子と専用素子を構成し、所望のＦＳＭはデータ入力ブロック５２におけるデータに対する反応に基づいて、連続的なノードのアクティブ化を通して実現される。一実施例においては、プログラマブル素子は、単一のデータサイクル（例えば、単一の文字、一組の文字、単一のクロックサイクル）中にアクティブなままであり、その後、上流プログラマブル素子によって再アクティブ化されるまでは非アクティブとなる。

端末ノード９６は、過去のイベントの圧縮されたヒストリを格納すると考えられる可能性がある。例えば、端末ノード９６に到達することを必要とされる一つ以上のパターンの入力データは、端末ノード９６のアクティブ化によって表すことができる。一実施例においては、端末ノード９６によって提供される出力はバイナリであって、即ち、出力は、興味あるパターンがマッチしたか否かを示す。図形９０における標準ノード９４に対する端末ノード９６の割合は、非常に小さい可能性がある。換言すると、ＦＳＭには高い複雑性が存在することがあるが、ＦＳＭの出力は、比較的小さくなりうる。

一実施例においては、ＦＳＭラチス３０の出力は、状態ベクトルを含む可能性がある。状態ベクトルは、ＦＳＭラチス３０のプログラマブル素子の状態（例えば、アクティブ化されているか否か）を含む。一実施例においては、状態ベクトルは、端末ノード９６に対応するプログラマブル素子の状態を含む。したがって、出力は、図形９０の全端末ノード９６によって提供される指示の集合を含む可能性がある。状態ベクトルは、単語として表され、各端末ノード９６によって提供されるバイナリ指示は１ビットの単語を含む。端末ノード９６のこのエンコードは、ＦＳＭラチス３０に対する検出状態の有効な指示（例えば、興味あるシーケンスが検出されたか否か、興味あるシーケンスは何か）を提供することができる。別の実施例においては、プログラマブル素子が端末ノード９６に対応するか否かに関わらず、状態ベクトルは、プログラマブル素子の全てもしくはサブセットの状態を含むことができる。

上述されたように、ＦＳＭラチス３０は、パターン認識機能を実現するためにプログラムすることができる。例えば、ＦＳＭラチス３０は入力データにおける一つ以上のデータシーケンス（例えば、署名、パターン）を認識するように構成することができる。興味あるデータシーケンスがＦＳＭラチス３０によって認識されると、当該認識の指示を出力ブロック５４において提供することができる。一実施例においては、パターン認識は、シンボルのストリング（例えば、ＡＳＣＩＩ文字）を、例えば、ネットワークデータにおけるマルウェアもしくは他の情報を識別するために認識することができる。

図７は、ヒエラルキー構造１００の一実施例を示し、ここでは、ＦＳＭラチス３０の二レベルが直列に結合され、データを解析するために使用される。つまり、示された実施形態においては、ヒエラルキー構造１００は、直列に配列された第一のＦＳＭラチス３０Ａと第二のＦＳＭラチス３０Ｂを含む。各ＦＳＭラチス３０は、データ入力を受信するための其々のデータ入力ブロック５２と、プログラミング信号を受信するためのプログラミングインターフェイスブロック５６と、出力ブロック５４とを含む。

第一のＦＳＭラチス３０Ａは、データ入力ブロックにおいて、入力データ（例えば、生データ）を受信するように構成される。第一のＦＳＭラチス３０Ａは、上述されたように入力データに対して反応して、出力ブロックにおいて出力を提供する。第一のＦＳＭラチス３０Ａからの出力は、第二のＦＳＭラチス３０Ｂのデータ入力ブロックへと送信される。第二のＦＳＭラチス３０Ｂは、その後、第一のＦＳＭラチス３０Ａによって提供された出力に基づいて反応して、ヒエラルキー構造１００の対応する出力信号１０２を提供することができる。直列の二つのＦＳＭラチス３０Ａおよび３０Ｂのこのヒエラルキー結合は、第一のＦＳＭラチス３０Ａから第二のＦＳＭラチス３０Ｂへの圧縮された単語における過去のイベントに関する情報を伝送するための手段を提供する。伝送された情報は、事実上、第一のＦＳＭラチス３０Ａによって記録された複雑なイベント（例えば、興味あるシーケンス）の要約である可能性がある。

図７に示されたＦＳＭラチス３０Ａ、３０Ｂの２レベルヒエラルキー１００は、二つの独立したプログラムが同一のデータストリームに基づいて動作することを可能にする。二段階ヒエラルキーは、異なる領域としてモデル化された生物学的脳における視認に類似する可能性がある。このモデルの下で、領域は、有効に異なるパターン認識エンジンであり、各々が類似する計算機能（パターンマッチング）を実施するが、異なるプログラム（署名）を利用する。複数のＦＳＭラチス３０Ａ、３０Ｂを接続することによって、データストリーム入力についてのより多い知識が得られることがある。

ヒエラルキーの第一レベル（第一のＦＳＭラチス３０Ａによって実現される）は、例えば、生データストリームにおいて直接的に処理を実施することができる。即ち、生データストリームは、第一のＦＳＭラチス３０Ａの入力ブロック５２で受信されて、第一のＦＳＭラチス３０Ａのプログラマブル素子は、生データストリームに反応することができる。ヒエラルキーの第二レベル（第二のＦＳＭラチス３０Ｂによって実現される）は、第一レベルからの出力を処理することができる。即ち、第二のＦＳＭラチス３０Ｂは、第二のＦＳＭラチス３０Ｂの入力ブロック５２において、第一のＦＳＭラチス３０Ａの出力ブロック５４からの出力を受信して、第二のＦＳＭラチス３０Ｂのプログラマブル素子は、第一のＦＳＭラチス３０Ａの出力に対して反応することができる。したがって、この実施例においては、第二のＦＳＭラチス３０Ｂは、入力として生データストリームは受信しないが、その代わりに、第一のＦＳＭラチス３０Ａによって判定された、生データストリームとマッチする興味あるパターンの指示を受信する。第二のＦＳＭラチス３０Ｂは、第一のＦＳＭラチス３０Ａからの出力データストリームにおけるパターンを認識するＦＳＭを実現することができる。

図８は、コンパイラがＦＳＭを実現するためのラチス３０などのＦＳＭラチスをプログラムするように構成された画像へとソースコードを変換するための方法１１０の一実施例を示す。方法１１０は、ソースコードをシンタックスツリーへと解析すること（ブロック１１２）と、シンタックスツリーをオートメーションに変換すること（ブロック１１４）と、オートメーションを最適化すること（ブロック１１６）と、オートメーションをネットリストへ変換すること（ブロック１１８）と、ハードウェア上にネットリストを配置すること（ブロック１２０）と、ネットリストをルーティングすること（ブロック１２２）と、結果として生じる画像を発行すること（ブロック１２４）と、を含む。

一実施例においては、コンパイラ２０は、ＦＳＭラチス３０上のＦＳＭを実現するための画像をソフトウェア開発者が生成することを可能にするアプリケーションプログラミングインターフェイス（ＡＰＩ）を含む。コンパイラ２０は、ＦＳＭラチス３０をプログラムするように構成された画像へとソースコードにおける正規表現の入力セットを変換するための方法を提供する。コンパイラ２０は、フォンノイマンアーキテクチャを有するコンピュータ用の命令によって実現することができる。これらの命令は、コンパイラ２０の機能をコンピュータ上のプロセッサ１２に実現させることができる。例えば、命令は、プロセッサ１２によって実行されると、プロセッサ１２に対してアクセス可能なソースコード上のブロック１１２、１１４、１１６、１１８、１２０、１２２、１２４に記述された動作をプロセッサ１２に実施させることができる。

一実施例においては、ソースコードは、シンボルのグループ内のシンボルのパターンを識別するための検索ストリングを記述する。検索ストリングを記述するために、ソースコードは複数の正規表現（ｒｅｇｅｘ）を含む可能性がある。Ｒｅｇｅｘは、シンボル検索パターンを記述するためのストリングである可能性がある。Ｒｅｇｅｘは、プログラミング言語、テキストエディタ、ネットワークセキュリティなど、種々のコンピュータドメインで広く使用されている。一実施例においては、コンパイラによってサポートされる正規表現は、非構造化データの解析用の基準を含む。非構造化データは、フリーフォームであるデータを含み、データ内の単語に対して適用される索引付けを有さない。単語は、データ内の印刷可能および印刷不能な任意の組み合わせのバイトを含む可能性がある。一実施例においては、コンパイラは、Ｐｅｒｌ、（例えば、Ｐｅｒｌ互換正規表現（ＰＣＲＥ））、ＰＨＰ、Ｊａｖａ（登録商標）、．ＮＥＴ言語を含むｒｅｇｅｘを実現するための異なる複数のソースコード言語をサポートすることができる。

ブロック１１２において、コンパイラ２０は、相関的に接続されたオペレータ（演算子）の配列を形成するためにソースコードを解析することができ、異なるタイプのオペレータはソースコードによって実現される異なる機能（例えば、ソースコード内のｒｅｇｅｘによって実現される異なる機能）に対応する。ソースコードを解析することは、ソースコードのジェネリック表現を生成できる。一実施例においては、ジェネリック表現は、シンタックスツリーとして知られるツリーグラフの形式のソースコードにおけるｒｅｇｅｘのエンコードされた表現を含む。本明細書で記述される実施例は、シンタックスツリー（“抽象シンタックスツリー”としても知られる）として配列を称するが、他の実施例においては、具象シンタックスツリーもしくは他の配列を使用することができる。

上述されたように、コンパイラ２０は複数のソースコード言語をサポートできるため、言語に関わらず、解析することは、非言語の特定の表現（例えば、シンタックスツリー）へとソースコードを変換する。したがって、コンパイラ２０によるさらなる処理（ブロック１１４、１１６、１１８、１２０）は、ソースコードの言語に関わらず、共通の入力構造から動作することができる。

上述されたように、シンタックスツリーは、相関的に接続された複数のオペレータを含む。シンタックスツリーは、複数の異なるタイプのオペレータを含むことができる。即ち、異なるオペレータは、ソースコードにおけるｒｅｇｅｘによって実現される異なる機能に対応する可能性がある。

ブロック１１４においては、シンタックスツリーはオートメーションへと変換される。オートメーションは、ＦＳＭのソフトウェアモデルを含み、したがって、決定論的もしくは非決定論的として分類することができる。決定論的オートメーションは、任意の時間における単一の実行経路を有し、非決定論的オートメーションは、複数の同時実行経路を有する。オートメーションは複数の状態を含む。シンタックスツリーをオートメーションに変換するために、シンタックスツリーにおけるオペレータおよびオペレータ間の関係は、状態間の遷移を伴う状態へと変換される。一実施例においては、オートメーションは、ＦＳＭラチス３０のハードウェアに部分的に基づいて変換することができる。

一実施例においては、オートメーション用の入力シンボルは、アルファベット、０−９の数字、および他の印刷可能な文字のシンボルを含む。一実施例においては、入力シンボルは、０から２５５を含むバイト値によって表される。一実施例においては、オートメーションは、グラフのノードが状態の組に対応する、有向グラフとして表すことができる。一実施例においては、入力シンボルα上の状態ｐから状態ｑへの遷移、即ち、δ（ｐ，α）は、ノードｐからノードｑへの有向接続によって示される。一実施例においては、オートメーションの反転は、幾つかのシンボルαにおける各遷移ｐ→ｑが、同一シンボルにおけるｑ→ｐに反転される新規オートメーションを生成する。反転においては、開始状態は最終状態になり、最終状態は開始状態になる。一実施例においては、オートメーションによって認識される（例えば、マッチする）言語は、オートメーションへ順次入力されるとき最終状態に到達する全ての可能性のある文字ストリングの組である。オートメーションによって認識される言語における各ストリングは、開始状態から一つ以上の最終状態への経路を追跡する。

ブロック１１６においては、オートメーションが構成された後、オートメーションがとりわけ、その複雑性およびサイズを減少させるために最適化される。オートメーションは、余分な状態を組み合わせることによって最適化することができる。

ブロック１１８においては、最適化されたオートメーションはネットリストへ変換される。オートメーションをネットリストへ変換することは、ＦＳＭラチス３０上のハードウェア素子（例えば、ＳＭＥ３４、３６、他の素子）へのオートメーションの各状態をマップして、ハードウェア素子間の接続を判定する。

ブロック１２０においては、ネットリストは、ネットリストの各ノードに対応するターゲットデバイス（例えば、ＳＭＥ３４、３６、専用素子５８）の特定のハードウェア素子を選択するために配置される。一実施例においては、配置することは、ＦＳＭラチス３０の一般的入力および出力制約に基づいて、各特定のハードウェア素子を選択する。

ブロック１２２においては、配置されたネットリストは、ネットリストによる接続の記述を達成するために、選択されたハードウェア素子を結合するために、プログラマブルスイッチング素子（例えば、ブロック間スイッチング素子４０、ブロック内スイッチング素子４２、行内スイッチング素子４４）用の設定を判定するためにルーティングされる。一実施例においては、プログラマブルスイッチング素子の設定は、選択されたハードウェア素子を接続するために使用されるＦＳＭラチス３０の特定の導体、ならびに、プログラマブルスイッチング素子用の設定を判定することによって判定される。ルーティングは、ブロック１２０において配置されたハードウェア素子間の接続のより特定な制限を考慮することができる。したがって、ルーティングはＦＳＭラチス３０上の導体の実際の制限がある場合でも適切な接続をするために、グローバル配置によって判定されたように、ハードウェア素子の幾つかの位置を調整してもよい。

いったんネットリストが配置されルーティングされると、配置されてルーティングされたネットリストは、ＦＳＭラチス３０のプログラミング用の複数のビットへと変換することができる。複数ビットは、本明細書においては画像とも称される。

ブロック１２４においては、画像は、コンパイラ２０によって発行される。画像は、ＦＳＭラチス３０の特定のハードウェア素子のプログラミング用の複数ビットを含む。画像が複数ビット（例えば、０と１）を含む実施形態においては、画像はバイナリ画像と称される。プログラムされたＦＳＭラチス３０がソースコードによって記述された機能を有するＦＳＭを実現するように、ビットは、ＳＭＥ３４、３６、専用素子５８、プログラミングスイッチング素子の状態をプログラムするために、ＦＳＭラチス３０上にロードすることができる。配置（ブロック１２０）およびルーティング（ブロック１２２）は、オートメーションにおける特定の状態へとＦＳＭラチス３０における特定の位置における特定のハードウェア素子をマップすることができる。したがって、画像におけるビットは、所望の（複数の）機能を実現するために、特定のハードウェア素子をプログラムすることができる。一実施例においては、画像は、コンピュータ可読媒体へとマシンコードを保存することによって発行することができる。別の実施例においては、画像は、ディスプレイデバイス上に画像を表示することによって発行することができる。さらに別の実施例においては、画像は、ＦＳＭラチス３０上に画像をロードするためのプログラミングデバイスなどの別のデバイスへと画像を送信することによって発行することができる。さらに別の実施例においては、画像はＦＳＭラチス（例えば、ＦＳＭラチス３０）上に画像をロードすることによって発行することができる。

一実施例においては、画像は、ＳＭＥ３４、３６および他のハードウェア素子へと画像からのビット値を直接ロードするか、一つ以上のレジスタに画像をロードして、その後ＳＭＥ３４、３６および他のハードウェア素子へとレジスタからのビット値を書き込むことのいずれかによってＦＳＭラチス３０上にロードすることができる。一実施例においては、プログラミングデバイスおよび／もしくはコンピュータが一つ以上のメモリアドレスへと画像を書き込むことによって、ＦＳＭラチス３０上に画像をロードすることができるように、ＦＳＭラチス３０のハードウェア素子（例えば、ＳＭＥ３４、３６、専用素子５８、プログラマブルスイッチング素子４０、４２、４４）は、マップされたメモリである。

本明細書で記述される方法の実施例は、少なくとも部分的にマシンもしくはコンピュータで実現することができる。幾つかの実施例は、上記の実施例に記述された方法を実施するために電子デバイスを構成するように動作可能な命令をエンコードされたコンピュータ可読媒体もしくはマシン可読媒体を含む可能性がある。当該方法の実現は、マイクロコード、アセンブリ言語コード、より高いレベルの言語コードなどのコードを含む可能性がある。当該コードは、種々の方法を実施するためのコンピュータ可読命令を含む可能性がある。コードはコンピュータプログラム製品の一部を形成してもよい。さらには、実行中もしくは他の時間に、コードは、一つ以上の揮発性もしくは不揮発性コンピュータ可読媒体に具体的に格納されてもよい。これらのコンピュータ可読媒体は、ハードディスク、リムーバブル磁気ディスク、リムーバブル光ディスク（例えば、コンパクトディスクおよびデジタルビデオディスク）、磁気カセット、メモリカードもしくはスティック、ランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）などを含むがそのいずれにも限定はされない。

ここで、図９に関連して、ステートマシンエンジン１４の一実施形態が示される。前述されたように、ステートマシンエンジン１４は、データバスを介して、メモリ１６などのソースからデータを受信するように構成される。示された実施形態においては、データは、ＤＤＲ３バスインターフェイス１３０などのバスインターフェイスを通して、ステートマシンエンジン１４に送信されてもよい。ＤＤＲ３バスインターフェイス１３０は、１Ｇバイト／秒以上のレートでデータを交換可能であってもよい。理解されるように、解析されるべきデータのソースに依存して、バスインターフェイス１３０は、ＮＡＮＤフラッシュインターフェイス、ＰＣＩインターフェイスなどの、ステートマシンエンジン１４とデータソースとでデータをやり取りするための任意の適切なバスインターフェイスであってもよい。前述されたように、ステートマシンエンジン１４は、データを解析するように構成された一つ以上のＦＳＭラチス３０を含む。各ＦＳＭラチス３０は、二つのハーフラチスへと分割されてもよい。示された実施形態においては、ラチス３０が４８Ｋ ＳＭＥを含むように、各ハーフラチスは、２４Ｋ ＳＭＥ（例えば、ＳＭＥ３４、３６）を含んでもよい。ラチス３０は、図２−図５に関連して前述されたように配列された任意の所望の数のＳＭＥを含んでもよい。さらには、唯一つのＦＳＭラチス３０が示されているが、前述されたように、ステートマシンエンジン１４は複数のＦＳＭラチス３０を含んでもよい。

解析されるべきデータがバスインターフェイス１３０で受信され、多数のバッファおよびバッファインターフェイスを通してＦＳＭラチス３０へと伝送される。示された実施形態においては、データ経路は、データバッファ１３２、プロセスバッファ１３４、インターランク（ＩＲ）バスおよびプロセスバッファインターフェイス１３６を含む。データバッファ１３２は、解析されるべきデータを受信して一時的に格納するように構成される。一実施形態においては、二つのデータバッファ１３２（データバッファＡおよびデータバッファＢ）が存在する。データは、二つのデータバッファ１３２のうちの一つに格納され、データは、ＦＳＭラチス３０による解析用に他のデータバッファ１３２から除かれる。示された実施形態においては、データバッファ１３２は、各々３２Ｋバイトであってもよい。ＩＲバスおよびプロセスバッファインターフェイス１３６は、プロセスバッファ１３４へのデータ伝送を容易にしてもよい。ＩＲバスおよびプロセスバッファ１３６は、データがＦＳＭラチス３０によって順番に処理されることを保証する。ＩＲバスおよびプロセスバッファ１３６は、データが正確な順序で受信されて解析されるように、データの交換、タイミング情報、パッキング命令などを調整してもよい。概して、ＩＲバスおよびプロセスバッファ１３６は、ＦＳＭラチス３０の論理ランクを通したパラレルな複数データセットの解析を可能にする。

示された実施形態においては、ステートマシンエンジン１４は、ステートマシンエンジン１４を通した大量のデータの伝送を援助するために、デコンプレッサ（圧縮解除プログラム）１３８およびコンプレッサ（圧縮プログラム）１４０をも含む。コンプレッサ１４０およびデコンプレッサ１３８は、データ伝送時間を最小限化するためにデータが圧縮されるように、組み合わせて動作する。解析されるべきデータを圧縮することによって、バス使用時間は最小限化される可能性がある。コンパイラ２０によって提供される情報に基づいて、マスクは、ステートマシンエンジン１４に提供され、どのステートマシンが使用されないかの情報を提供する。コンプレッサ１４０およびデコンプレッサ１３８は、バースト長の変化するデータを処理するように構成することもできる。圧縮されたデータを詰めて、各圧縮された領域がいつ終わるかについての指示を含むことによって、コンプレッサ１４０は、ステートマシンエンジン１４を通した全体の処理速度を改善してもよい。コンプレッサ１４０およびデコンプレッサ１３８は、ＦＳＭラチス３０による解析後のマッチ結果データを圧縮して、復元するために使用されてもよい。

前述されたように、ＦＳＭラチス３０の出力は、状態ベクトルを含む可能性がある。状態ベクトルは、ＦＳＭラチス３０のプログラマブル素子の状態（例えば、アクティブ化されているか否か）を含む。各状態ベクトルは、さらなるヒエラルキー処理および解析用に状態ベクトルキャッシュメモリ１４２に一時的に格納されてもよい。即ち、最終状態がさらなる解析において使用されるように、各ステートマシンの状態が格納され、新規データセットの再プログラミングおよび／もしくはさらなる解析用にステートマシンを解放してもよい。典型的なキャッシュと同様に、状態ベクトルキャッシュメモリは、例えば、ここではＦＳＭラチス３０による迅速な回復および使用のために、情報（ここでは状態ベクトル）の格納を可能にする。状態ベクトルメモリバッファ、状態ベクトル中間入力バッファ１４６、状態ベクトル中間出力バッファ１４８などのさらなるバッファが状態ベクトルキャッシュメモリ１４２と組み合わせて使用され、ステートマシンエンジン１４を通したパケット伝送プロトコルを順守しながら状態ベクトルの迅速な解析および格納を適応させる。

いったん興味の結果がＦＳＭラチス３０によって生成されると、マッチ結果は、マッチ結果メモリ１５０に格納されてもよい。即ち、マッチを示す“マッチベクトル”（例えば、興味あるパターンの検出）はマッチ結果メモリ１５０に格納されてもよい。マッチ結果は、その後、例えば、プロセッサ１２にバスインターフェイス１３０を介した伝送用にマッチバッファ１５２へと送信される可能性がある。前述されたように、マッチ結果は圧縮されてもよい。

さらなるレジスタおよびバッファが、同様にステートマシンエンジン１４に提供されてもよい。例えば、ステートマシンエンジン１４は、制御およびステータスレジスタ１５４を含んでもよい。さらには、復元およびプログラムバッファ１５６は、最初にＦＳＭラチス３０をプログラミングするうえで使用するため、もしくは解析中にＦＳＭラチス３０におけるマシンの状態を復元するために提供されてもよい。同様に、保存および修復マップバッファ１５８は、セットアップおよび使用のためにマップを保存および修復するためのストレージとして提供されてもよい。

図１０は、図４に関連して上述されたものと類似する行３８の第二の実施例を示す。行３８は、プログラマブル行内スイッチング素子４４と、行相互接続導体６８、７０（以下に記述されるように“行ルーティングライン”とも称される）を含んでもよい。

図１０の行３８は、８個のＧＯＴ６０、専用素子５８、入力６２、入力６４、出力６６、マッチ素子１６０、複数の行ルーティングライン１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６、１７８、１８０、１８２、１８４、１８６、１８８、１９０、１９２（以降、“行ルーティングライン１６２−１９２”と集合的に称される）、専用素子ルーティングライン１９４、複数の接合点１９６を含んでもよい。

さらには、図１１に示されたＳＭＥ３４、３６に結合されるのに加えて、ローカルルーティングマトリクス１７２は、特定の行３８におけるＧＯＴ６０に対するＳＭＥ３４、３６の全ての対に結合されてもよい。したがって、ローカルルーティングマトリクス１７２は、プログラマブル行内スイッチング素子４４と行相互接続導体６８、７０（以下に記述されるように“行ルーティングライン”とも称される）を含んでもよい。

図１０に示されたＧＯＴ６０および専用素子５８は、図４に関連して前述されたＧＯＴ６０と専用素子５８に実質的に類似する。従って、各ＧＯＴ６０は、ＳＭＥ３４の検出セル８６に対してイネーブル信号として動作するための統一型イネーブル入力でありうる入力６２を受信する。同様に、各ＧＯＴ６０は、ＳＭＥ３６の検出セル８６に対するイネーブル信号として動作するための統一型イネーブル入力でもある入力６４を受信もする。これらの統一型イネーブル入力６２、６４は、例えば、データストリーム内のパターンを検索するために、他のＳＭＥ３４、３６からの結果と組み合わせて利用されうる、其々のＳＭＥによって実施された解析の其々の結果（例えば、単一のＳＭＥ３４からの解析されたデータストリームにおけるマッチ）を出力するために、ＳＭＥ３４、３６の検出セル８６をアクティブ化してもよい。例えば、統一型イネーブル入力６２と統一型イネーブル入力６４は、アクティブなＳＭＥ３４、３６の各々によって生成された結果がデータストリームの全体のより広い解析の一部として利用されうるように、ＳＭＥ３４、３６の選択的アクティブ化を可能にする。

ＧＯＴ６０のＳＭＥ３４、３６によって生成された結果は、出力６６上にＧＯＴから選択的に提供されてもよい。一実施形態においては、ＧＯＴ６０の可能性のある出力は、出力を含まないか、第一のＳＭＥ３４の出力（即ち、出力７２）と第二のＳＭＥ３６の出力（即ち出力７４）を含むか、第一のＳＭＥ３４の出力もしくは第二のＳＭＥ３６の出力（即ち、出力７２もしくは出力７４）を含む。したがって、ＧＯＴ６０は、ＧＯＴ６０から選択された結果を出力するようにプログラムされてもよい。このプログラミングは、例えば、ＦＳＭラチス３０の最初のプログラミングステージ間に実施されるロードされた画像に基づいて達成されてもよい。ＧＯＴ６０からの結果は、任意のデータストリーム検索もしくはデータストリーム検索の一部用に行３８から生成された選択された結果を出力するように動作しうる、マッチ素子１６０へと提供されてもよい。

さらに、行３８は、行ルーティングライン１６２−１９２（行相互接続導体とも称されうる）を含んでもよい。本実施形態においては、８個のＧＯＴ６０と専用素子５８に選択的に結合可能な１６本の行ライン１６２−１９２が存在する。しかしながら、より少ないかより多い行ルーティングラインが行３８と組み合わせて利用されてもよいことを理解されたい。

行ルーティングライン１６２−１９２の各々は、入力６２、６４に沿って、一つ以上のＧＯＴ６０のＳＭＥ３４、３６の任意のＳＭＥに対してイネーブル信号を提供するために使用されてもよい。したがって、これらの行ルーティングライン１６２−１９２の使用を介して、任意の特定のＳＭＥ（例えばＳＭＥ３４）に対する任意の特定の検出セル８６はアクティブ化されてもよい。これは、ＳＭＥ３４、３６の統一型イネーブル入力６２、６４に対して、行ルーティングライン１６２−１９２を（例えば、ロードされた画像に従って）選択的に結合することによって達成されてもよい。さらには、ＳＭＥ３４、３６にイネーブル信号を提供するうえでのさらなる柔軟性を提供するために、行ルーティングライン１６２−１９２は、任意のＧＯＴ６０の二つのＳＭＥ３４、３６の間で分割されてもよい。例えば、行ルーティングライン１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６は行３８におけるＳＭＥ３４、３６のうちの任意のＳＭＥをアクティブ化するために使用されてもよい。例えば、ＧＯＴ６０は、そこに結合された行ルーティングライン（例えば、行ルーティングライン１６２）へと出力６６を伝送してもよい。この信号は、例えば、行３８におけるさらなるＧＯＴ６０へと行ルーティングライン１６４上でルーティングされうる、ブロック内スイッチへと伝送されてもよい。さらには、行ルーティングライン１７８、１８２、１８６、１９０は、例えば、ブロック内スイッチ４２からの信号を受信することによって、行３８におけるＳＭＥ３４をアクティブ化し、行ルーティングライン１８０、１８４、１８８、１９２は、例えば、ブロック内スイッチ４２から受信された信号を介して行３８におけるＳＭＥ３６をアクティブ化してもよい。この方法においては、行ルーティングライン１６２−１９２の全体の数が減少するが、行３８におけるＳＭＥ３４、３６のうちの任意のＳＭＥの任意の検出セル８６をアクティブ化するための性能および全体の柔軟性を可能とする。

図１０に示されるように、各行ルーティングライン１６２−１９２は、複数の接合点１９６を含む。これらの接合点１９６は、例えば、図３の行内スイッチング素子４４を含んでもよい。なぜなら、任意のＧＯＴ６０を任意の他のＧＯＴ６０へと選択的に結合するためか、行３８（もしくはその点において、別の行および／もしくは別のブロック）内の任意の他の素子（例えば、専用素子５８）へと任意のＧＯＴ６０を選択的に結合するために接合点１９６が使用されることがあるためである。しかしながら、これらの接続は、利用可能な接合点１９６によって制限されてもよい。例えば、各行ルーティングライン１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６は、行３８におけるＳＭＥ３４、３６のうちの任意のＳＭＥをアクティブ化するために使用されてもよい。しかしながら、各行ルーティングライン１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６は、ＧＯＴ６０のうちの其々異なる一つの出力へと選択的に結合可能でもある。例えば、ＧＯＴ６０のうちの任意の一つからの出力は、そこに結合可能な行ルーティングライン１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６のうちのそれぞれ一つの上のＧＯＴ６０から提供されるだけでもよい。したがって、一実施形態においては、行ルーティングライン１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６は、ＧＯＴ６０の出力６６へと結合可能であるため、行ルーティングライン１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６は、ブロック内スイッチ４２へと（例えば、駆動）信号を提供してもよい。対照的に、一実施形態においては、行ルーティングライン１７８、１８０、１８２、１８４、１８６、１８８、１９０、１９２は、例えば、他の行３８もしくはブロック３２から受信されることがあるブロック内スイッチ４２からの信号を受信して（例えば、それによって駆動されて）もよい。

行ルーティングライン１６２−１９２に加えて、行３８は、専用素子５８に結合された専用素子ルーティングライン１９４を含んでもよい。行ルーティングライン１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６と類似して、専用ルーティングライン１９４は、ブロック内スイッチ４２へと（例えば、駆動）信号を提供してもよい。一実施形態においては、専用素子ルーティングライン１９４は、マッチ素子１６０へと結合可能であってもよい。例えば、専用素子５８がカウンタを含む場合、カウンタの出力は、専用ルーティングライン１９４に沿って提供されてもよい。同様に、専用素子５８がブール型セルなどのブール論理素子を含む場合、ブール論理素子の出力は、専用ルーティングライン１９４に沿って提供されてもよい。これらの専用素子の利用を通して、繰り返し型検索（例えば、１０回ある要素を見つける）もしくはカスケード型検索（例えば、要素ｘ、ｙ、ｚを見つける）は、ブロック内スイッチ４２およびマッチ素子１６０のうちのいずれかまたはその双方へと、専用ルーティングライン１９４に沿って提供されうる単一の出力へと簡略化されてもよい。

マッチ素子１６０のより詳細な図が図１１に表示される。示されるように、マッチ素子１６０は、４つのデータ入力１９８、２００、２０２、２０４と２つの出力と、６つの制御入力２１０、２１２、２１４、２１６、２１８、２２０を含んでもよい。さらには、マッチ素子は、二つの２：１マルチプレクサ２２２、２２４を含んでもよい。２：１マルチプレクサ２２２、２２４が示されているが、例えば、ルーティング／出力構成における柔軟性を可能とするため、もしくはシリコンスペースが許すときに、３：１マルチプレクサ、４：１マルチプレクサもしくは他の素子が所望の場合には、２：１マルチプレクサ２２２、２２４の位置で使用されてもよいことに留意されたい。

一実施形態においては、マッチ素子１６０のデータ入力１９８は、行ルーティングライン１７６に結合され、データ入力２００は行ルーティングライン１７４に結合され、データ入力２０２は、専用ルーティングライン１９４に結合され、データ入力２０４は行ルーティングライン１６８に結合される。これらの特定のラインの選択は例示的なためだけのものであって、行３８からの出力信号を受信するうえで柔軟性を説明するために選択される。マッチ素子１６０に接続するものとして、行ルーティングライン１６８および行ルーティングライン１７６を選択することによって、ＧＯＴ６０間のパリティを確立することができる。例えば、全てのＧＯＴ６０のうちの前半（ＧＯＴ６０の０から３）における一つのＧＯＴ６０によって、データストリームの少なくとも一部で実施される第一の解析の結果は、マッチ素子１６０へのルーティングライン１６８上で提供され、全てのＧＯＴ６０のうちの後半（ＧＯＴ６０の４から７）における別のＧＯＴ６０によって、データストリームの少なくとも一部で実施される第二の解析の結果は、マッチ素子１６０へのルーティングライン１７６上で提供される可能性がある。入力２００、２０４をこの方法で分割することによって、マッチ素子１６０へと結果を提供するための経路を減少させることを可能とすることができる。さらには、マッチ素子１６０において、専用ルーティングライン１９４に沿って専用素子５８からの結果を受信することによって、カスケード型検索の結果は、マッチ素子１６０へと一度に提供されてもよい。最後に、行ルーティングライン１７４の選択は、行３８の全体システムに対して柔軟性を追加する。しかしながら、記述されたように、これらの選択は単に例示的なものにすぎない。

示されるように、マッチ素子１６０のデータ入力１９８、２００は、２：１マルチプレクサ２２２に提供され、マッチ素子１６０のデータ入力２０２、２０４は、２：１マルチプレクサ２２４に提供されてもよい。２：１マルチプレクサ２２２、２２４は、例えば、ＦＳＭラチス３０の最初のプログラミングステージ間に実施されるロードされた画像に基づいてプログラムされうる、制御入力２１０、２１２、２１４、２１６、２１８、２２０から制御信号を各々受信してもよい。一実施形態においては、２：１マルチプレクサ２２２は、制御入力２１０から選択信号Ｓ０を、制御入力２１２から選択信号Ｓ１を、制御入力２１４から出力イネーブル信号を受信してもよい。同様に、２：１マルチプレクサ２２４は、制御入力２１６から選択信号Ｓ０を、制御入力２１８から選択信号Ｓ１を、制御入力２２０から出力イネーブル信号を受信してもよい。選択信号Ｓ０、Ｓ１は、其々、例えば出力ブロック５４へとデータ検索の結果を伝送するために、どのデータ入力が出力２０６、２０８へと提供されるべきかを選択するために使用されてもよい。さらには、選択信号Ｓ０、Ｓ１を搬送する複数の選択ラインの利用は、インバータなしで各２：１マルチプレクサ２２２、２２４を構築することを可能とし、それによって、２：１マルチプレクサ２２２、２２４を実装するために必要とされる面積を縮小する。しかしながら、一実施形態においては、単一の選択信号、例えばＳ０を搬送する単一の選択ラインが使用されてもよい。

さらには、制御入力２１４からの出力イネーブル信号は、データ入力１９８、２００、２０２、２０４上の信号がステーブルであるときにのみ、出力２０６、２０８を提供することを可能とするクロック信号もしくは他のイネーブル信号であってもよい。図１３は、制御入力２１０からの選択信号Ｓ０、制御入力２１２からの選択信号Ｓ１が２：１マルチプレクサ２２４の出力２０８を如何にしてプログラマブルに選択するかの一実施例を説明する真理値表２２６を示す。

図１３に示されるように、マッチ素子１６０の出力２０８に対応する真理値表２２６が示される。真理値表２２６に表された出力２０８は、制御入力２２２０からの出力イネーブル信号が２：１マルチプレクサ２２４で受信されたことを仮定することに留意されたい。真理値表２２６に示されたように、制御入力２１６からの選択信号Ｓ０と制御入力２１８からの選択信号Ｓ１の双方がロウ（即ち０）であるとき、２：１マルチプレクサ２２４の出力２０８はロウである。例えば、マッチ素子１６０から提供される行３８からの結果はない。制御入力２１６からの選択信号Ｓ０がハイ（即ち１）であって、制御入力２１８からの選択信号Ｓ１がロウであるとき、２：１マルチプレクサ２２４の出力２０８は、行ルーティングライン１６８上の結果である。逆に、制御入力２１６からの選択信号Ｓ０がロウであって、制御入力２１８からの選択信号Ｓ１がハイであるとき、２：１マルチプレクサ２２４の出力２０８は、専用ルーティングライン１９４上の結果である。最後に、制御入力２１６からの選択信号Ｓ０と制御入力２１８からの選択信号Ｓ１の双方がハイになることによる状態は禁じられる。したがって、当該状態は、マッチ素子１６０のプログラミング中に回避される。この方法においては、マッチ素子１６０は、出力を選択しないか、第一のデータ入力２０４からの出力（行ルーティングライン１６８上の結果）をプログラマブルに選択するか、第二のデータ入力２０２からの出力（専用ルーティングライン１９４上の結果）をプログラマブルに選択してもよい。さらには、マッチ素子は、図１２に示された特定の実施形態に限定されることなく、他のプログラマブル構成で動作してもよいことに留意されたい。

本明細書においては、図面で例示する目的のために特定の実施形態が示され、詳細に記述されてきたが、本発明は種々の改変および置換形態が可能であってもよい。しかしながら、本発明は開示された特定の形態に限定されることを意図するものではないことを理解されるべきである。それよりもむしろ、本発明は、以下に添付された請求項によって定義される本発明の趣旨および範囲内にある全ての改変物、均等物、代替物を包含するものである。

図４は、行３８の一実施例を示す。ＧＯＴ６０は、プログラマブル行内スイッチング素子４４によって、行３８内の任意の他の素子（例えば、専用素子５８）および他のＧＯＴ６０へと選択的に結合することができる。ＧＯＴ６０は、ブロック内スイッチング素子４２で他の行３８における他のＧＯＴ６０へと、または、ブロック間スイッチング素子４０によって他のブロック３２における他のＧＯＴ６０へと結合することができる。一実施例においては、ＧＯＴ６０は、第一の入力６２、第二の入力６４、出力６６を有する。図５に関連してさらに示されるように、第一の入力６２は、ＧＯＴ６０の第一のＳＭＥ３４へと結合され、第二の入力６４は、ＧＯＴ６０の第二のＳＭＥ３４へと結合される。

一実施例においては、ステートマシン素子３４、３６は、検出ライン８２へとパラレルに結合されたダイナミックランダムアクセスメモリ（ＤＲＡＭ）でしばしば利用されるような複数のメモリセル８０を含む。当該メモリセル８０のうちの一つは、ハイもしくはロウの値（例えば、１もしくは０）のいずれかに対応するような、データ状態に設定することのできるメモリセルを含む。メモリセル８０の出力は、検出ライン８２に結合され、メモリセル８０の入力は、データストリームライン８４上のデータに基づいて信号を受信する。一実施例においては、データストリームライン８４上の入力は、メモリセル８０のうちの選択された一つへとデコードされる。選択されたメモリセル８０は、検出ライン８２上の出力としてその格納されたデータ状態を提供する。例えば、入力ブロック５２で受信されたデータは、（図示されていない）デコーダへと提供され、デコーダは、データストリームライン８４のうちの一つを選択することができる。一実施例においては、デコーダは、２５６本のデータストリームライン８４のうちの対応する１本へと、８ビットＡＳＣＩＩ文字を変換することができる。

解析されるべきデータがバスインターフェイス１３０で受信され、多数のバッファおよびバッファインターフェイスを通してＦＳＭラチス３０へと伝送される。示された実施形態においては、データ経路は、データバッファ１３２、プロセスバッファ１３４、インターランク（ＩＲ）バスおよびプロセスバッファインターフェイス１３６を含む。データバッファ１３２は、解析されるべきデータを受信して一時的に格納するように構成される。一実施形態においては、二つのデータバッファ１３２（データバッファＡおよびデータバッファＢ）が存在する。データは、二つのデータバッファ１３２のうちの一つに格納され、データは、ＦＳＭラチス３０による解析用に他のデータバッファ１３２から除かれる。示された実施形態においては、データバッファ１３２は、各々３２Ｋバイトであってもよい。ＩＲバスおよびプロセスバッファインターフェイス１３６は、プロセスバッファ１３４へのデータ伝送を容易にしてもよい。ＩＲバスおよびプロセスバッファ１３４は、データがＦＳＭラチス３０によって順番に処理されることを保証する。ＩＲバスおよびプロセスバッファ１３４は、データが正確な順序で受信されて解析されるように、データの交換、タイミング情報、パッキング命令などを調整してもよい。概して、ＩＲバスおよびプロセスバッファ１３４は、ＦＳＭラチス３０の論理ランクを通したパラレルな複数データセットの解析を可能にする。

さらには、図５に示されたＳＭＥ３４、３６に結合されるのに加えて、ローカルルーティングマトリクス１７２は、特定の行３８におけるＧＯＴ６０に対するＳＭＥ３４、３６の全ての対に結合されてもよい。したがって、ローカルルーティングマトリクス１７２は、プログラマブル行内スイッチング素子４４と行相互接続導体６８、７０（以下に記述されるように“行ルーティングライン”とも称される）を含んでもよい。

行ルーティングライン１６２−１９２に加えて、行３８は、専用素子５８に結合された専用素子ルーティングライン１９４を含んでもよい。行ルーティングライン１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６と類似して、専用素子ルーティングライン１９４は、ブロック内スイッチ４２へと（例えば、駆動）信号を提供してもよい。一実施形態においては、専用素子ルーティングライン１９４は、マッチ素子１６０へと結合可能であってもよい。例えば、専用素子５８がカウンタを含む場合、カウンタの出力は、専用素子ルーティングライン１９４に沿って提供されてもよい。同様に、専用素子５８がブール型セルなどのブール論理素子を含む場合、ブール論理素子の出力は、専用素子ルーティングライン１９４に沿って提供されてもよい。これらの専用素子の利用を通して、繰り返し型検索（例えば、１０回ある要素を見つける）もしくはカスケード型検索（例えば、要素ｘ、ｙ、ｚを見つける）は、ブロック内スイッチ４２およびマッチ素子１６０のうちのいずれかまたはその双方へと、専用素子ルーティングライン１９４に沿って提供されうる単一の出力へと簡略化されてもよい。

一実施形態においては、マッチ素子１６０のデータ入力１９８は、行ルーティングライン１７６に結合され、データ入力２００は行ルーティングライン１７４に結合され、データ入力２０２は、専用素子ルーティングライン１９４に結合され、データ入力２０４は行ルーティングライン１６８に結合される。これらの特定のラインの選択は例示的なためだけのものであって、行３８からの出力信号を受信するうえで柔軟性を説明するために選択される。マッチ素子１６０に接続するものとして、行ルーティングライン１６８および行ルーティングライン１７６を選択することによって、ＧＯＴ６０間のパリティを確立することができる。例えば、全てのＧＯＴ６０のうちの前半（ＧＯＴ６０の０から３）における一つのＧＯＴ６０によって、データストリームの少なくとも一部で実施される第一の解析の結果は、マッチ素子１６０へのルーティングライン１６８上で提供され、全てのＧＯＴ６０のうちの後半（ＧＯＴ６０の４から７）における別のＧＯＴ６０によって、データストリームの少なくとも一部で実施される第二の解析の結果は、マッチ素子１６０へのルーティングライン１７６上で提供される可能性がある。入力２００、２０４をこの方法で分割することによって、マッチ素子１６０へと結果を提供するための経路を減少させることを可能とすることができる。さらには、マッチ素子１６０において、専用素子ルーティングライン１９４に沿って専用素子５８からの結果を受信することによって、カスケード型検索の結果は、マッチ素子１６０へと一度に提供されてもよい。最後に、行ルーティングライン１７４の選択は、行３８の全体システムに対して柔軟性を追加する。しかしながら、記述されたように、これらの選択は単に例示的なものにすぎない。

さらには、制御入力２１４からの出力イネーブル信号は、データ入力１９８、２００、２０２、２０４上の信号がステーブルであるときにのみ、出力２０６、２０８を提供することを可能とするクロック信号もしくは他のイネーブル信号であってもよい。図１２は、制御入力２１０からの選択信号Ｓ０、制御入力２１２からの選択信号Ｓ１が２：１マルチプレクサ２２４の出力２０８を如何にしてプログラマブルに選択するかの一実施例を説明する真理値表２２６を示す。

図１２に示されるように、マッチ素子１６０の出力２０８に対応する真理値表２２６が示される。真理値表２２６に表された出力２０８は、制御入力２２２０からの出力イネーブル信号が２：１マルチプレクサ２２４で受信されたことを仮定することに留意されたい。真理値表２２６に示されたように、制御入力２１６からの選択信号Ｓ０と制御入力２１８からの選択信号Ｓ１の双方がロウ（即ち０）であるとき、２：１マルチプレクサ２２４の出力２０８はロウである。例えば、マッチ素子１６０から提供される行３８からの結果はない。制御入力２１６からの選択信号Ｓ０がハイ（即ち１）であって、制御入力２１８からの選択信号Ｓ１がロウであるとき、２：１マルチプレクサ２２４の出力２０８は、行ルーティングライン１６８上の結果である。逆に、制御入力２１６からの選択信号Ｓ０がロウであって、制御入力２１８からの選択信号Ｓ１がハイであるとき、２：１マルチプレクサ２２４の出力２０８は、専用素子ルーティングライン１９４上の結果である。最後に、制御入力２１６からの選択信号Ｓ０と制御入力２１８からの選択信号Ｓ１の双方がハイになることによる状態は禁じられる。したがって、当該状態は、マッチ素子１６０のプログラミング中に回避される。この方法においては、マッチ素子１６０は、出力を選択しないか、第一のデータ入力２０４からの出力（行ルーティングライン１６８上の結果）をプログラマブルに選択するか、第二のデータ入力２０２からの出力（専用素子ルーティングライン１９４上の結果）をプログラマブルに選択してもよい。さらには、マッチ素子は、図１２に示された特定の実施形態に限定されることなく、他のプログラマブル構成で動作してもよいことに留意されたい。

Claims (29)

1. 第一の結果を受信するように構成された第一のデータ入力であって、前記第一の結果は、ステートマシンの素子によってデータストリームの少なくとも一部上で実施される解析の結果である、第一のデータ入力と、
   第二の結果を受信するように構成された第二のデータ入力であって、前記第二の結果は、前記ステートマシンの別の素子によって前記データストリームの少なくとも一部上で実施される解析の結果である、第二のデータ入力と、
   前記第一の結果もしくは前記第二の結果を選択的に提供するように構成された出力と、
   を含むマッチ素子を含む、
   ことを特徴とするデバイス。
2. 前記マッチ素子は、
   第一の制御信号を受信するように構成された第一の制御入力と、
   第二の制御信号を受信するように構成された第二の制御入力と、
   を含む、
   ことを特徴とする請求項１に記載のデバイス。
3. 前記第一の結果もしくは前記第二の結果を選択的に提供するように構成された前記出力は、前記第一および第二の制御信号に基づいて、前記第一の結果もしくは前記第二の結果を選択的に提供するように構成された前記出力を含む、
   ことを特徴とする請求項２に記載のデバイス。
4. 前記マッチ素子は、出力イネーブル信号を受信するように構成された第三の制御入力を含む、
   ことを特徴とする請求項３に記載のデバイス。
5. 前記第一および第二の制御信号に基づいて、前記第一の結果もしくは前記第二の結果を提供するように構成された前記出力は、前記第一および第二の制御信号と前記出力イネーブル信号とに基づいて、前記第一の結果もしくは前記第二の結果を提供するように構成された前記マッチ素子を含む、
   ことを特徴とする請求項４に記載のデバイス。
6. 前記マッチ素子は、前記第一のデータ入力、前記第二のデータ入力、前記第一の制御入力、前記第二の制御入力、前記第三の制御入力、前記出力に結合された２：１マルチプレクサを含む、
   ことを特徴とする請求項４に記載のデバイス。
7. 前記第一の結果もしくは前記第二の結果を選択的に提供するように構成された前記出力は、出力を提供しないか、前記第一の結果もしくは前記第二の結果を選択的に提供するように構成された前記出力を含む、
   ことを特徴とする請求項１に記載のデバイス。
8. 前記マッチ素子は、
   第三の結果を受信するように構成された第三のデータ入力であって、前記第三の結果は、前記ステートマシンの第三の素子によって前記データストリームの少なくとも一部上で実施された解析の結果である、第三のデータ入力と、
   第四の結果を受信するように構成された第四のデータ入力であって、前記第四の結果は、前記ステートマシンの専用素子によって検出された複数の結果の組み合わせを含む、第四のデータ入力と、
   前記第三の結果もしくは前記第四の結果を選択的に提供するように構成された第二の出力と、
   を含む、
   ことを特徴とする請求項２に記載のデバイス。
9. 前記マッチ素子は、
   第三の制御信号を受信するように構成された第三の制御入力と、
   第四の制御信号を受信するように構成された第四の制御入力と、
   を含む、
   ことを特徴とする請求項８に記載のデバイス。
10. 前記第三の結果もしくは前記第四の結果を選択的に提供するように構成された前記第二の出力は、前記第三および第四の制御信号に基づいて、前記第三の結果もしくは前記第四の結果を選択的に提供するように構成された前記第二の出力を含む、
    ことを特徴とする請求項９に記載のデバイス。
11. 前記マッチ素子は、出力イネーブル信号を受信するように構成された第五の制御入力を含む、
    ことを特徴とする請求項１０に記載のデバイス。
12. 前記第三および第四の制御信号に基づいて、前記第三の結果もしくは前記第四の結果を提供するように構成された前記マッチ素子は、前記第三および第四の制御信号ならびに前記出力イネーブル信号に基づいて、前記第三の結果もしくは前記第四の結果を提供するように構成された前記マッチ素子を含む、
    ことを特徴とする請求項１１に記載のデバイス。
13. 前記マッチ素子は、前記第三のデータ入力、前記第四のデータ入力、前記第三の制御入力、前記第四の制御入力、前記第五の制御入力、前記第二の出力に結合された２：１マルチプレクサを含む、
    ことを特徴とする請求項１１に記載のデバイス。
14. データストリームの少なくとも一部上で実施される解析の第一の結果を提供するように構成された第一の素子と、
    前記データストリームの少なくとも一部上で実施される解析の第二の結果を提供するように構成された第二の素子と、
    マッチ素子であって、
    前記第一の結果を受信するように構成された第一の入力と、
    前記第二の結果を受信するように構成された第二の入力と、
    前記第一の結果もしくは前記第二の結果を選択的に提供するように構成された出力と、
    を含むマッチ素子と、
    を各々含む複数の行、
    を各々含む複数のブロック、
    を含むステートマシン、
    を含む、
    ことを特徴とするデバイス。
15. 前記第一の結果もしくは前記第二の結果を選択的に提供するように構成された前記出力は、出力を提供しないか、前記第一の結果もしくは前記第二の結果を選択的に提供するように構成された前記出力を含む、
    ことを特徴とする請求項１に記載のデバイス。
16. 前記複数の行の各々は、前記第一の素子および前記第二の素子に選択的に結合されるように構成された複数の行ルーティングラインを含む、
    ことを特徴とする請求項１４に記載のデバイス。
17. 前記複数の行の各々は、前記第一の素子および前記第二の素子の各々に、選択された複数の行ルーティングラインを選択的に結合するように構成された複数の接合点を含む、
    ことを特徴とする請求項１６に記載のデバイス。
18. 前記複数の接合点のうちの少なくとも一つは、前記マッチ素子へ、前記行ルーティングラインのうちの少なくとも一つを選択的に結合するように構成される、
    ことを特徴とする請求項１７に記載のデバイス。
19. 前記複数の行の各々は、専用結果を提供するように構成された専用素子を含み、前記専用結果は、前記データストリームの少なくとも一部上で実施された解析からの複数の結果の組み合わせに基づく、
    ことを特徴とする請求項１４に記載のデバイス。
20. 前記複数の行の各々は、前記データストリームの少なくとも一部上で実施された解析の第三の結果を提供するように構成された第三の素子を含む、
    ことを特徴とする請求項１９に記載のデバイス。
21. 前記マッチ素子は、
    前記第三の結果を受信するように構成された第三の入力と、
    前記専用結果を受信するように構成された第四の入力と、
    前記第三の結果もしくは前記専用結果を選択的に提供するように構成された第二の出力と、
    をさらに含む、
    ことを特徴とする請求項２０に記載のデバイス。
22. ステートマシンの第一の素子によって、データストリームの少なくとも一部上で実施された解析の第一の結果を、マッチ素子の第一のデータ入力で受信することと、
    前記ステートマシンの第二の素子によって、前記データストリームの少なくとも一部上で実施された解析の第二の結果を、前記マッチ素子の第二のデータ入力で受信することと、
    前記第一の結果もしくは前記第二の結果を前記マッチ素子から選択的に出力することと、
    を含む、
    ことを特徴とする方法。
23. 前記マッチ素子で第一の制御信号を受信することと、
    前記マッチ素子で第二の制御信号を受信することと、
    を含む、
    ことを特徴とする請求項２２に記載の方法。
24. 前記第一の結果もしくは前記第二の結果を前記マッチ素子から選択的に出力することは、前記第一および第二の制御信号に基づいて、前記マッチ素子から出力を出力しないか、前記第一の結果もしくは前記第二の結果を前記マッチ素子から選択的に出力することを含む、
    ことを特徴とする請求項２３に記載の方法。
25. 前記マッチ素子で出力イネーブル信号を受信することをさらに含み、前記第一および第二の制御信号に基づいて、前記マッチ素子から出力を出力しないか、前記第一の結果もしくは前記第二の結果を前記マッチ素子から選択的に出力することは、前記第一および第二の制御信号と前記出力イネーブル信号とに基づいて、前記マッチ素子から出力を出力しないか、前記第一の結果もしくは前記第二の結果を前記マッチ素子から選択的に出力することを含む、
    ことを特徴とする請求項２４に記載の方法。
26. 前記ステートマシンの第三の素子によって前記データストリームの少なくとも一部上で実施された解析の第三の結果を前記マッチ素子で受信することと、
    前記マッチ素子で第四の結果を受信することであって、前記第四の結果は前記ステートマシンの専用素子によって検出された複数の結果の組み合わせを含む、ことと、
    前記第三の結果もしくは前記第四の結果を、前記マッチ素子から選択的に出力することと、
    を含む、
    ことを特徴とする請求項２６に記載の方法。
27. 前記マッチ素子で第三の制御信号を受信することと、
    前記マッチ素子で第四の制御信号を受信することと、
    を含み、
    前記第三の結果もしくは前記第四の結果を前記マッチ素子から選択的に出力することは、前記第三および第四の制御信号に基づいて、前記第三の結果もしくは前記第四の結果を前記マッチ素子から選択的に出力することを含む、
    ことを特徴とする請求項２７に記載の方法。
28. 前記マッチ素子において出力イネーブル信号を受信することをさらに含み、前記第三および第四の制御信号に基づいて、前記第三の結果もしくは前記第四の結果を前記マッチ素子から選択的に出力することは、前記第三および第四の制御信号と、前記出力イネーブル信号とに基づいて、前記第三の結果もしくは前記第四の結果を前記マッチ素子から選択的に出力することを含む、
    ことを特徴とする請求項２８に記載の方法。
29. データストリームの解析の複数の結果が一つ以上の複数のステートマシン素子で検出された複数の指示を受信するように構成された複数のデータ入力を含むマッチ素子を含む、
    ことを特徴とするデバイス。

Images