JP6181074B2 - ステートマシンにおける検出方法とシステム - Google Patents

Description

本発明の実施形態は、一般に、電子デバイスに関し、より詳細には、いくつかの実施形態において、パターン認識のためのパラレルな有限ステートマシン (parallel finite state machine)を有する電子デバイスに関する。

従来のフォンノイマン型コンピュータで複雑なパターン認識を行うことは、非効率なことがある。しかしながら、生命体の脳、特に人間の脳は、パターン認識を行うことが得意である。最近の研究は、人間の脳が、新皮質内にある階層的に系統だった一連のニューロン層を用いてパターン認識を行うことを示唆している。この階層の下位層におけるニューロンは、例えば、感覚器官からの「未加工の信号(raw signal)」を分析し、一方、上位層におけるニューロンは、より低いレベルにあるニューロンからの信号出力を分析する。この新皮質内にある階層システムは、おそらくは、脳のその他の領域と相まって、人間が、空間認識や、意識的思考、複雑な言語等の高いレベルの機能を発揮できる複雑なパターン認識を実現していると考えられる。

コンピューティングの分野において、パターン認識という課題は、ますます挑戦しがいのある問題となっている。従来よりも膨大なデータ量がコンピュータ間で伝送され、ユーザが識別を希望するパターンの数が増加している。例えば、スパムやマルウェアは、例えば、特定のフレーズまたはコードの一部等のデータストリーム内のパターンを検索することによって、頻繁に検出される。新しいパターンが、新しい変種(variant)を検索するために実装されるため、パターンの数は、スパム及びマルウェアの多様性とともに増加する。データストリームでこれらの各パターンを検索することは、コンピューティングのボトルネックを形成する場合がある。多くの場合において、データストリームが受信されると、各パターンが１度に１つずつ検索される。システムがデータストリームの次の部分を検索できるようになるまでに起きる遅延は、パターンの数とともに増加する。従って、パターン認識は、データの受信を遅らせる場合がある。

データストリームでパターンを検索するためのハードウェアが設計されているが、このようなハードウェアは、一定の時間内に適切なデータ量を処理することができない場合が多い。データストリームで検索するように構成されたデバイスでは、複数の回路間にデータストリームを分散させることによって、かかるデータストリームで検索を行うものもある。回路は、データストリームがパターンの一部と一致するか否かをそれぞれ判定する。多くの場合、大量の回路が、そのそれぞれがほぼ同時にデータストリームで検索を行い、並行して動作する。しかしながら、生命体の脳以上に効率的にパターン認識を行うことができるシステムはこれまでなかった。そこで、このようなシステムの開発が望まれている。

図１は、本発明の様々な実施形態による、ステートマシンエンジンを有するシステムの１つの実施例を示す。 図２は、本発明の様々な実施形態による、図１のステートマシンエンジンの有限ステートマシン（ＦＳＭ）ラティス(lattice)の１つの実施例を示す。 図３は、本発明の様々な実施形態による、図２のＦＳＭラティスのブロックの１つの実施例を示す。 図４は、本発明の様々な実施形態による、図３のブロック 行の１つの実施例を示す。 図５は、本発明の様々な実施形態による、図４の行のグループオブツー(group of two)の１つの実施例を示す。 図６は、本発明の様々な実施形態による、有限ステートマシングラフの１つの実施例を示す。 図７は、本発明の様々な実施形態による、ＦＳＭラティスによって実装される２段階の階層の１つの実施例を示す。 図８は、本発明の様々な実施形態による、コンパイラがソースコードを図２のＦＳＭラティスのプログラミング用のバイナリファイルに変換する方法の１つの実施例を示す。 図９は、本発明の様々な実施形態による、ステートマシンエンジンを示す。 図１０は、本発明の様々な実施形態による、図４の検出セルの１つの実施例を示す。 図１１は、本発明の様々な実施形態による、図１０の検出セルに結合したルーティングの１つの実施例を示す。 図１２は、本発明の様々な実施形態による、図１１のイントラグループ（グループ内）回路を示す。 図１３は、本発明の様々な実施形態による、図１２のマルチプレクサの真偽表を示す。

図面に戻ると、図１は、参照符号１０によって一般に示される、プロセッサベースのシステムの実施形態を示す。システム１０は、デスクトップコンピュータ、ラップトップコンピュータ、ページャ、携帯電話機、電子手帳、携帯オーディオプレーヤー、制御回路、カメラ等の様々な種類のうちの任意のものであってよい。また、システム１０は、ルータ、サーバ、またはクライアント（例えば、先に記載した種類のコンピュータの１つ）等のネットワークノードであってもよい。システム１０は、コピー機、スキャナ、プリンタ、ゲーム機、テレビ、セットトップビデオ配信または記録システム、ケーブルボックス、パーソナルデジタルメディアプレーヤ、工場オートメーションシステム、自動車用コンピュータシステム、医療デバイス等のその他の種類の電子デバイスであってもよい（これらのシステムの実施例について記載するために使用した用語は、本明細書において使用するその他の多くの用語と同様に、単なる例示としているものであり、それゆえに、列挙されたその他の項目があるからという理由で狭い意味に解釈されてはならない）。

システム１０のような典型的なプロセッサベースのデバイスにおいて、マイクロプロセッサ等のプロセッサ１２は、システム１０におけるシステム機能やリクエストの処理を制御する。プロセッサ１２は、システム制御を共有する複数のプロセッサを更に備えることができる。プロセッサ１２は、プロセッサ１２が、システム１０の内部またはシステム１０の外部に保存された命令を実行することによってシステム１０を制御するように、システム１０における各素子と直接的又は間接的に結合することができる。

本明細書に記載する実施形態によれば、システム１０は、プロセッサ１２の制御下で動作することができるステートマシンエンジン１４を含む。ステートマシンエンジン１４は、ミーリ・アーキテクチャ、ムーア・アーキテクチャ、フィニットステートマシン（ＦＳＭ）、ディターミニスティックＦＳＭ、ビットパラレルステートマシン（ＢＰＳＭ）等を含むがこれらに限定されない複数のステートマシンアーキテクチャの任意の１つを採用することができる。様々な種類のアーキテクチャが使用できるが、議論の目的上、ここでの応用として、ＦＳＭを指す。しかしながら、当業者は、本明細書に記載する技術が、種々のステートマシンアーキテクチャのうちの任意の１つを使用することによってなされる旨を理解するであろう。

更に以下で論じるように、ステートマシンエンジン１４は、いくつかの（例えば１つ以上の）有限ステートマシン（ＦＳＭ）ラティスを備えることができる。ＦＳＭラティスのそれぞれは、その各々が同じデータを並行して受信し分析する複数のＦＳＭを備えていてもよい。更に、ＦＳＭラティスは、ＦＳＭラティスのクラスターが同じ入力データを並行して分析できるように、グループ（例えばクラスター）で配置することができる。更に、ステートマシンエンジン１４のＦＳＭラティスのクラスターは、階層構造の下位レベルのステートマシンラティスからの出力が、上位レベルのステートマシンラティスへの入力として使用できる階層構造に配置することができる。この階層構造を通ってステートマシンエンジン１４のパラレルＦＳＭラティスを連続してカスケード接続することにより、複雑さの増したパターンを分析（例えば評価、検索等）することができる。

更に、ステートマシンエンジン１４の階層的並行構造に基づいて、高い処理速度を利用するシステムにおいて、パターン認識のためのステートマシンエンジン１４を採用することができる。例えば、本明細書に記載する実施形態は、１ギガバイト／秒の処理速度を有するシステムに組み入れることができる。従って、このステートマシンエンジン１４を利用して、様々なパターンに対する高速メモリデバイスまたはその他の外部デバイスからのデータが迅速に分析できる。ステートマシンエンジン１４は、いくつかの基準とそれぞれの検索語に基づいて、ほぼ同時に、例えばシングルデバイスサイクルの間に、データストリームを分析することができる。ステートマシンエンジン１４のレベルのＦＳＭクラスター内にあるＦＳＭラティスのそれぞれが、データストリームからほぼ同時にそれぞれ同じ検索語を受信することができ、パラレルＦＳＭラティスの各々が、処理基準においてその用語によってステートマシンエンジン１４が次の状態に進むか否かを判定することができる。ステートマシンエンジン１４は、例えば、１００を超える、１１０を超える、或いは１０，０００を超える相対的に多くの基準に基づいて検索語を分析することができる。並行に動作するため、データストリームの速度を落とすことなく、例えば、ほぼ１ギガバイト／秒以上の相対的に高い帯域幅を有するデータストリームにその基準を適用することができる。

１つの実施形態において、ステートマシンエンジン１４は、データストリームにおける多数のパターンを認識（例えば、検出）するように構成することができる。例えば、ステートマシンエンジン１４は、ユーザまたはその他のエンティティが分析を希望する１つまたは複数の各種データストリームにおけるパターンを検出するために利用することができる。例えば、ステートマシンエンジン１４は、インターネットで受信されるパケットや、携帯電話ネットワークで受信される、音声やデータ等のネットワークで受信されるデータのストリームを分析するように構成することができる。１つの実施例において、ステートマシンエンジン１４は、スパムやマルウェアに対するデータストリームを分析するように構成することができる。データストリームは、データが、時間的、語彙的、または意味的に重要な順番等、なんらかの意義を有する順に受信される連続した（シリアル）データストリームとして受信することができる。或いは、データストリームは、並行して、または順不同に受信の後、例えばインターネットで受信したパケットの順番を変えることによって連続したデータストリームに変換することもできる。いくつかの実施形態において、データストリームは、用語を連続して提供できるが、各用語を示すビットを並行に受信することができる。データストリームは、システム１０の外部にあるソースから受信したり、メモリ１６等のメモリデバイスに問い合わせたり、メモリ１６に保存したデータからデータストリームを形成することによって形成することもできる。その他の実施例において、ステートマシンエンジン１４は、特定の語を綴る一連の文字、遺伝子を特定する一連の遺伝子塩基対、画像の一部を形成する画像ファイルや映像ファイル内の一連のビット、プログラムの一部を形成する実行ファイル内の一連のビット、歌や話し言葉の一部を形成する音声ファイル内の一連のビットを認識するよう構成することができる。分析されるデータのストリームは、バイナリフォーマットまたは、例えば、ベーステン、ＡＳＣＩＩ等の複数ビットのデータを含んでもよい。ストリームは、１つのデジットまたは、例えば、いくつかのバイナリデジット等の複数のデジットのデータをコード化することができる。

当業者が理解するように、システム１０は、メモリ１６を含むことができる。メモリ１６は、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、ダブルデータレートＤＲＡＭ（ＤＤＲ ＳＤＲＡＭ）、ＤＤＲ２ ＳＤＲＡＭ、ＤＤＲ３ ＳＤＲＡＭ等の揮発性メモリを含むことができる。メモリ１６はまた、揮発性メモリと合わせて使用するために、読み出し専用メモリ（ＲＯＭ）、ＰＣ−ＲＡＭ、シリコン・オキシド・ナイトリド・オキシド・シリコン（ＳＯＮＯＳ）メモリ、メタル・オキシド・ナイトリド・オキシド・シリコン（ＭＯＮＯＳ）メモリ、ポリシリコン・フローティング・ゲート・ベース・メモリ及び／または様々なアーキテクチャのその他の種類のフラッシュメモリ（例えば、ＮＡＮＤメモリ、ＮＯＲメモリ等）等の不揮発性メモリを含むことができる。メモリ１６は、ステートマシンエンジン１４によって分析されるデータを提供することができるＤＲＡＭデバイス等の１つまたは複数のメモリデバイスを含んでいてもよい。こうしたデバイスは、半導体ドライブ（ＳＳＤ）、マルチメディア・メディア・カード（ＭＭＣ）、セキュア・デジタル（ＳＤ）カード、コンパクト・フラッシュ（ＣＦ）カード、またはその他任意の適切なデバイスで称され、またはこれらを含むことができる。更に、これらのデバイスは、ユニバーサル・シリアル・バス（ＵＳＢ）、ペリフェラル・コンポーネント・インターコネクト（ＰＣＩ）、ＰＣＩ−エキスプレス（ＰＣＩ−Ｅ）、スモール・コンピュータ・システム・インターフェース（ＳＣＳＩ）、ＩＥＥＥ１３９４（ファイヤーワイヤー）またはその他の任意の適切なインターフェースを介してシステム１０に結合できることが理解されるべきである。フラッシュ・メモリ・デバイス等のメモリ１６の動作を容易にするために、システム１０は、メモリ・コントローラ（図示しない）を備えることができる。当業者が理解するように、メモリ・コントローラは、独立したデバイスであっても、プロセッサ１２と一体化したものであってもよい。また、システム１０は、磁気記憶装置等の外部記憶装置１８を含むことができる。外部記憶装置は、入力されたデータをステートマシンエンジン１４に提供することもできる。

システム１０は、複数の追加的素子を含むことができる。例えば、図８に関してより詳細に記載するように、ステートマシンエンジン１４をプログラミングするために、コンパイラ２０を使用することができる。ユーザがシステム１０にデータを入力できるように、入力デバイス２２がプロセッサ１２に結合していてもよい。例えば、入力デバイス２２は、ステートマシンエンジン１４が後に分析するために、データをメモリ１６に入力するために使用することができる。入力デバイス２２は、例えば、ボタン、スイッチング素子、キーボード、ライトペン、タッチペン、マウス及び／または音声認識システムを備えることができる。ディスプレイ等の出力デバイス２４も、プロセッサ１２に結合することができる。ディスプレイ２４は、例えば、ＬＣＤ、ＣＲＴ、ＬＥＤ及び／または聴覚ディスプレイを備えることができる。また、このシステムは、インターネット等のネットワークとインターフェースで接続するために、ネットワークインターフェースカード（ＮＩＣ）等のネットワークインターフェースデバイス２６を備えることもできる。当業者が理解するように、システム１０は、システム１０の用途に応じてその他の多くの構成要素を含むことができる。

図２〜図５は、ＦＳＭラティス３０の１つの実施例を示す。１つの実施例において、ＦＳＭラティス３０は、ブロック３２のアレイ(array)を備える。後に記載するが、各ブロック３２は、ＦＳＭの複数の状態に対応する選択的に結合可能な複数のハードウェア素子（例えば、プログラマブル素子及び／または専用素子）を含むことができる。ＦＳＭ内の状態と同様に、ハードウェア素子は、入力ストリームを分析することができ、この入力ストリームに基づいてダウンストリーム・ハードウェア素子をアクティブ化することができる。

プログラマブル素子は、多くの異なる機能を実装するためにプログラミングすることができる。例えば、プログラマブル素子は、階層的に系統立てられて、行３８（図３及び図４に示す）及びブロック３２（図２及び図３に示す）を有するステートマシンエンジン（ＳＭＥ）３４、３６（図５に示す）を含むことができる。階層的に系統立ったＳＭＥ３４とＳＭＥ３６との間の信号をルーティングするために、インターブロックスイッチング素子４０（図２及び図３に示す）、イントラブロックスイッチング素子４２（図３及び図４に示す）、イントラロースイッチング素子４４（図４に示す）等のプログラマブルスイッチング素子の階層を使用することができる。

以下に記載するように、スイッチング素子は、ルーティング構造とバッファとを備えることができる。ＳＭＥ３４とＳＭＥ３６は、ＦＳＭラティス３０によって実装されるＦＳＭの状態に対応することができる。ＳＭＥ３４とＳＭＥ３６は、以下に記載するプログラマブルスイッチング素子を使用することによって結合できる。従って、ＦＳＭは、状態の機能に対応するようにＳＭＥ３４とＳＭＥ３６とをプログラミングし、ＦＳＭ内の状態間の遷移に対応するように選択的にＳＭＥ３４とＳＭＥ３６とを結合することによって、ＦＳＭラティス３０に実装することができる。

図２は、ＦＳＭラティス３０の１つの例の全体図を示す。ＦＳＭラティス３０は、プログラマブルインターブロックスイッチング素子４０と選択的に結合することができる複数のブロック３２を備える。インターブロックスイッチング素子４０は、導体４６（例えば、電線、配線）や、バッファ４８、５０を備えてもよい。１つの実施例において、バッファ４８、５０は、インターブロックスイッチング素子４０への信号とインターブロックスイッチング素子４０からの信号の接続とタイミングを制御するために備えられる。以下で更に記載するが、バッファ４８がブロック３２間で送信されるデータをバッファリングするために提供され、バッファ５０がインターブロックスイッチング素子４０間で送信されるデータをバッファリングするために提供されてもよい。また、ブロック３２は、信号（例えばデータ）を受信し、そのデータをブロック３２に提供するために、入力ブロック５２（例えばデータ入力ポート）と選択的に結合することができる。ブロック３２は、信号をブロック３２から外部デバイス（例えば、別のＦＳＭラティス３０）に提供するために、出力ブロック５４（例えばデータ出力ポート）と選択的に結合することもできる。ＦＳＭラティス３０は、ＦＳＭラティス３０にプログラム（例えば、画像）をロードするためのプログラミングインターフェース５６を備えることもできる。画像は、ＳＭＥ３４とＳＭＥ３６の状態をプログラミング（設定）することができる。即ち、画像は、入力ブロック５２での所定の入力に対して何らかの形で反応するようにＳＭＥ３４、３６を構成することができる。例えば、入力ブロック５２で「ａ」という文字が受信されるとハイ信号を出力するようにＳＭＥ３４、３６を設定することができる。

１つの実施例において、入力ブロック５２、出力ブロック５４及び／またはプログラミングインターフェース５６は、レジスタへの書き込みまたはレジスタからの読み出しがそれぞれの素子へ、またはそれぞれの素子からデータを提供するようなレジスタとして実装することができる。従って、プログラミングインターフェース５６に対応するレジスタに保存した画像からのビットを、ＳＭＥ３４、３６にロードすることができる。図２は、ブロック３２、入力ブロック５２、出力ブロック５４、インターブロックスイッチング素子４０間の所定数の導体（例えば電線、配線）を示しているが、他の実施例において、より少ない数の、またはより多い数の導体が使用できことを理解すべきである。

図３は、ブロック３２の１つの実施例を示す。ブロック３２は、プログラマブルイントラブロックスイッチング素子４２とともに選択的に結合できる複数の行３８を含むことができる。また、行３８は、別のブロック３２内で別の行３８とプログラマブルインターブロックスイッチング素子４０とともに選択的に結合することができる。行３８は、本明細書でグループオブツー（ＧＯＴ）６０と呼ばれる素子の対に編成される複数のＳＭＥ３４、３６を備える。１つの実施例において、ブロック３２は、１６の行３８を備える。

図４は、行３８の１つの実施例を示す。ＧＯＴ６０は、プログラマブルイントラロースイッチング素子４４によって、その他のＧＯＴ６０と行３８内のその他任意の素子（例えば専用素子５８）と選択的に結合することができる。ＧＯＴ６０は、別の行３８内で、イントラブロックスイッチング素子４２とともにその他のＧＯＴ６０と結合することができ、または、別のブロック３２内で、インターブロックスイッチング素子４０とともにその他のＧＯＴ６０と結合することができる。１つの実施例において、ＧＯＴ６０は、第一及び第二入力６２、６４と、出力６６を有する。後に図５を参照して更に示すが、第一入力６２は、ＧＯＴ６０の第一ＳＭＥ３４と結合し、第二入力６４は、ＧＯＴ６０の第二ＳＭＥ３４と結合する。

１つの実施例において、行３８は、複数の第一及び第二行相互接続導体６８、７０を備える。１つの実施例において、ＧＯＴ６０の入力６２、６４は、１つまたは複数の行相互接続導体６８、７０に結合することができ、出力６６は、１つの行相互接続導体６８、７０に結合することができる。１つの実施例において、複数の第一行相互接続導体６８は、行３８の中で、各ＧＯＴ６０のそれぞれのＳＭＥ３４、３６に結合することができる。複数の第二行相互接続導体７０は、行３８の中で、各ＧＯＴ６０のＳＭＥ３４、３６の１つとのみ結合することができるが、ＧＯＴ６０の別のＳＭＥ３４、３６とは結合することができない。後に図５に関してより詳しく示すが、１つの実施例において、複数の第二行相互接続導体７０の前半(first half)は、行３８の中で、ＳＭＥ３４、３６の前半と結合することができ（各ＧＯＴ６０からの１つのＳＭＥ３４）、複数の第二行相互接続導体７０の後半は、行３８の中で、ＳＭＥ３４、３６の後半(second half)と結合することができる（各ＧＯＴ６０からの別のＳＭＥ３４、３６）。複数の第二行相互接続導体７０とＳＭＥ３４、３６との間の限定された接続は、本明細書において「パリティ」と呼ばれる。１つの実施例において、行３８は、カウンタ、プログラマブルブーリアンロジック素子、ルックアップテーブル、ＲＡＭ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、アプリケーションスペシフィックインテグレーテッドサーキット（ＡＳＩＣ）、プログラマブルプロセッサ（例えば、マイクロプロセッサ）または専用機能を実行するその他の素子等の専用素子５８を備えることもできる。

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

別の実施例において、専用素子５８は、ブーリアンロジックを備える。いくつかの実施例において、このブーリアンロジックは、ＦＳＭラティス３０内の終端状態ＳＭＥ（本明細書で後に論じるようにＦＳＭの終端ノードに対応）からの情報を抽出するために使用することができる。抽出した情報は、状態情報をその他のＦＳＭラティス３０に伝送するため、及び／またはＦＳＭラティス３０を再度プログラミングするために使用されるプログラミング情報を伝送するため、またはその他のＦＳＭラティス３０を再度プログラミングするために使用することができる。

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

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

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

１つの実施例において、入力ライン６２、６４の信号は、それぞれの検出セル８６をアクティブまたは非アクティブのいずれかの状態に設定する。非アクティブな状態に設定されている場合、検出セル８６は、ハイ信号が各ＳＭＥ３４、３６のメモリセル８２の１つから検出されると、各出力ライン７２、７４にハイ信号を出力する。アクティブな状態にある場合、検出セル８６は、各ＳＭＥ３４、３６の全てのメモリセル８２からの信号がロウであるとき、各出力ライン７２、７４にロウ信号を出力する。

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

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

１つの実施例において、単一のＦＳＭラティス３０は、単一の物理デバイスに実装されるが、別の実施例においては、２つ以上のＦＳＭラティス３０を単一の物理デバイスに（例えば物理チップ）に実装することができる。１つの実施例において、ＦＳＭラティス３０の各々は、別個のデータ入力ブロック５２、別個のデータ出力ブロック５４、別個のプログラミングインターフェース５６、別個のプログラマブル素子の１セットを備えることができる。更にプログラマブル素子の各セットは、その対応するデータ入力ブロック５２にて、データに反応する（例えばハイ信号やロウ信号を出力する）ことができる。例えば、第一ＦＳＭラティス３０に対応するプログラマブル素子の第一セットは、第一ＦＳＭラティス３０に対応する第一データ入力ブロック５２で、データに反応することができる。第二ＦＳＭラティス３０に対応するプログラマブル素子の第二セットは、第二ＦＳＭラティス３０に対応する第二データ入力ブロック５２で、第二データに反応することができる。従って、各ＦＳＭラティス３０は、異なるセットのプログラマブル素子が異なる入力データに反応することができるプログラマブル素子の１セットを備える。同様に、各ＦＳＭラティス３０と対応するプログラマブル素子の各セットは、別個の出力を提供することができる。いくつかの実施形態において、第一ＦＳＭラティス３０からの出力ブロック５４は、第二ＦＳＭラティス３０の入力データが、一連のＦＳＭラティス３０の階層的な配置において第一ＦＳＭラティス３０からの出力データを含むことができるように第二ＦＳＭラティス３０の入力ブロック５２と結合することができる。

１つの実施例において、ＦＳＭラティス３０にロードするための画像は、ＦＳＭラティス内のプログラマブル素子、プログラマブルスイッチング素子、及び専用素子を構成するための複数ビットの情報を含んでいる。１つの実施例において、画像は、特定の入力に基づいて望ましい出力を提供するため、ＦＳＭラティス３０をプログラミングするために、ＦＳＭラティス３０にロードすることができる。出力ブロック５４は、プログラマブル素子の反応に基づいて、ＦＳＭラティス３０から、データ入力ブロック５２におけるデータへと出力を提供することができる。出力ブロック５４からの出力は、所定パターンとの一致を示す単一ビット、複数のパターンとの一致、不一致を示す複数ビットを含むワード、及び、所定の時間における全てまたは特定のプログラマブル素子の状態に対応する状態ベクトルを含むことができる。既に記載したように、パターン認識（例えば、音声認識、画像認識等）、信号処理、画像化、コンピュータビジョン、暗号文等のデータ分析を行うため、複数のＦＳＭラティス３０がステートマシンエンジン１４等のステートマシンエンジンに備えられていてもよい。

図６は、ＦＳＭラティス３０によって実装できる有限ステートマシン（ＦＳＭ）の実施例モデルを示す。ＦＳＭラティス３０は、ＦＳＭの物理的実装として構成する（例えばプログラミングする）ことができる。ＦＳＭは、１つ以上のルートノード９２を含む図形９０（例えば、有向グラフ、無向グラフ、シュードグラフ(pseudograph)）として表すこともできる。ルートノード９２に加えて、ＦＳＭは、１つまたは複数のエッジ９８を介してルートノード９２と別の標準ノード９４に結合したいくつかの標準ノード９４、終端ノード９６から構成することができる。ノード９２、９４、９６は、ＦＳＭにおける状態に対応する。エッジ９８は、状態間の遷移に対応する。

ノード９２、９４、９６のそれぞれは、アクティブまたは非アクティブのいずれかの状態とすることができる。非アクティブな状態の場合、ノード９２、９４、９６は、入力データに対して反応（例えば応答）しない。アクティブな状態の場合、ノード９２、９４、９６は、入力データに対して反応することができる。入力データが、アップストリームノード９２、９４と、ダウンストリームノード９４、９６との間のエッジ９８によって特定される基準に一致すると、アップストリームノード９２、９４は、ノードからダウンストリームにあるノード９４、９６をアクティブ化することによって入力データに反応することができる。例えば、文字「ｂ」を特定する第一ノード９４は、第一ノード９４がアクティブで、文字「ｂ」が入力データとして受信されると、エッジ９８によって第一ノード９４と結合した第二ノード９４をアクティブ化する。本明細書に記載するように、「アップストリーム」とは、１つまたは複数の別のノードのアップストリーム（または、ループ構成やフィードバック構成の場合はそれ自体のアップストリーム）にある第一ノードが、第一ノードが１つまたは複数の別のノードをアクティブ化することができる（または、ループの場合は、それ自体をアクティブ化することができる）状況を指すときの１つまたは複数のノード間の関係を指す。同様に、「ダウンストリーム」とは、１つまたは複数の別のノードのダウンストリーム（または、ループの場合はそれ自体のダウンストリーム）にある第一ノードが、第一ノードが１つまたは複数の別のノードによってアクティブ化される（または、ループの場合は、それ自体によってアクティブ化される）状況を指すときの関係を指す。従って、本明細書では、「アップストリーム」と「ダウンストリーム」という用語は、１つまたは複数のノード間の関係を指すが、これらの用語は、ノード間のループまたは他の非線形パスの使用を排除するものではない。

図形９０において、ルートノード９２は、最初にアクティブ化され、入力データがルートノード９２からのエッジ９８と一致すると、ダウンストリームノード９４をアクティブ化することができる。ノード９４は、入力データがノード９４からのエッジ９８と一致すると、ノード９６をアクティブ化することができる。入力データが受信されると、図形９０にある全てのノード９４、９６は、このようにしてアクティブ化される。終端ノード９６は、入力データによって対象となるシーケンスの一致に対応する。従って、終端ノード９６のアクティブ化は、対象となるシーケンスが入力データとして受信されたことを示す。パターン認識機能を実装するＦＳＭラティス３０の意味合いにおいて、終端ノード９６に到達することは、入力データの中で対象となる特定のパターンが検出された旨、示すことができる。

１つの実施例において、ルートノード９２、標準ノード９４、終端ノード９６のそれぞれは、ＦＳＭラティス３０におけるプログラマブル素子に対応することができる。エッジ９８のそれぞれは、プログラマブル素子間の接続に対応することができる。こうして、別の標準ノード９４または終端ノード９６に遷移する（例えば、別の標準ノード９４または終端ノード９６に接続するエッジ９８を有する）標準ノード９４は、別のプログラマブル素子に遷移する（例えば、別のプログラマブル素子に出力を提供する）プログラマブル素子に対応する。いくつかの実施例において、ルートノード９２は、対応するプログラマブル素子を有していない。

ＦＳＭラティス３０がプログラミングされると、各プログラマブル素子は、アクティブか非アクティブのいずれかの状態となることもできる。非アクティブなとき、所定のプログラマブル素子は、対応するデータ入力ブロック５２で、入力データに対して反応しない。アクティブなプログラマブル素子は、データ入力ブロック５２で、入力データに対して反応することができ、入力データがプログラマブル素子の設定と一致すると、ダウンストリームプログラマブル素子をアクティブ化することができる。プログラマブル素子が、終端ノード９６に対応すると、プログラマブル素子は出力５４と結合し、外部装置に対して一致している旨を表示することができる。

プログラミングインターフェース５６を介してＦＳＭラティス３０にロードされた画像は、データブロック入力５２で、データに対する反応に基づきノードの連続したアクティブ化を介して望ましいＦＳＭが実装されるように、プログラマブル素子及び専用素子のみならず、プログラマブル素子と専用素子との間の接続をも構成することができる。１つの実施例において、プログラマブル素子は、単一データサイクル（例えば、単一文字、文字一式、単一クロックサイクル）の間、アクティブなままであり、その後、アップストリームプログラマブル素子によって再度アクティブ化されない限りは非アクティブとなる。

終端ノード９６は、過去のイベントの圧縮履歴を保存するものと考えることができる。例えば、終端ノード９６に到達するために必要な入力データの１つまたは複数のパターンは、その終端ノード９６のアクティブ化によって表すことができる。１つの実施例において、終端ノード９６によって提供される出力はバイナリであり、即ち、出力は、対象となるパターンが一致したか否かを示す。図形９０における終端ノード９６の標準ノード９４に対する比率はかなり小さくすることができる。言い換えれば、ＦＳＭの複雑さが高くても、ＦＳＭの出力は比較的小さくすることができる。

１つの実施例において、ＦＳＭラティス３０の出力は、状態ベクトルを含むことができる。状態ベクトルは、ＦＳＭラティス３０のプログラマブル素子の状態（例えば、アクティブ化されているか否か）を含む。１つの実施例において、状態ベクトルは、終端ノード９６に対応するプログラマブル素子の状態を含む。従って、出力は、図形９０の終端ノード９６全てによって提供される指示の集合体を含むことができる。状態ベクトルは、ワードとして表され、各終端ノード９６によって提供されるバイナリ表示は、１ビットのワードを含む。この終端ノード９６のコード化は、ＦＳＭラティス３０の検出状態（例えば、対象とするシーケンスが検出されたか否か、また、どのような対象シーケンスが検出されたか）の効果的な表示を提供することができる。別の実施例において、状態ベクトルは、プログラマブル素子が終端ノード９６に対応するか否かに関わらず、プログラマブル素子全ての、またはサブセットの状態を含むことができる。

上記の通り、ＦＳＭラティス３０は、パターン認識機能を実装するためにプログラミングすることができる。例えば、ＦＳＭラティス３０は、入力データにおける１つまたは複数のデータシーケンス（例えば、シグナチャ、パターン）を認識するよう、構成することができる。対象となるデータシーケンスがＦＳＭラティス３０によって認識されると、その認識の表示が出力ブロック５４においてなされる。１つの実施例において、パターン認識は、例えば、ネットワークデータにおけるマルウェアやその他の情報を識別するために、記号の文字列（例えば、ＡＳＣＩＩ文字）を認識することができる。

図７は、階層構造１００の１つの実施例を示し、この中で２つの段階のＦＳＭラティス３０が直列に結合され、データ分析のために使用される。具体的には、図示した実施形態において、階層構造１００は、直列に配置された第一ＦＳＭラティス３０Ａと第二ＦＳＭラティス３０Ｂとを含む。各ＦＳＭラティス３０は、それぞれ、データ入力を受信するデータ入力ブロック５２とプログラミング信号を受信するプログラミングインターフェースブロック５６と、出力ブロック５４とを含む。

第一ＦＳＭラティス３０Ａは、データ入力ブロックにおいて、例えば、未加工データ等の入力データを受信するよう構成される。第一ＦＳＭラティス３０Ａは、入力データに対して上記のように反応し、出力ブロックにおいて、出力を提供する。第一ＦＳＭラティス３０Ａからの出力は、第二ＦＳＭラティス３０Ｂのデータ入力ブロックに送信される。その後、第二ＦＳＭラティス３０Ｂは、第一ＦＳＭラティス３０Ａによって提供される出力に基づいて反応し、階層構造１００の対応する出力信号１０２を提供する。この直列の２つのＦＳＭラティス３０Ａ、３０Ｂの階層的結合は、第一ＦＳＭラティス３０Ａから第二ＦＳＭラティス３０Ｂへの圧縮ワードにおける過去のイベントに関する情報を伝送する手段を提供する。伝送された情報は、効率的に、第一ＦＳＭラティス３０Ａによって記録された複雑なイベント（例えば、対象となるシーケンス）のサマリとなることができる。

図７に示すＦＳＭラティス３０Ａ、３０Ｂの二段階の階層１００により、２つの独立したプログラムが同じデータストリームに基づいて動作できる。二段階の階層は、異なる領域としてモデル化されている生命体の脳と視認上類似とすることができる。このようなモデルにおいて、領域は、その各々が類似したコンピュータ機能（パターン一致）を実行するが、異なるプログラム（シグナチャ）を使用する、効率的に異なるパターン認識エンジンである。複数のＦＳＭラティス３０Ａ、３０Ｂを接続することにより、データストリーム入力についてのより多くの知識を得ることができる。

（第一ＦＳＭラティス３０Ａによって実装された）階層の第一段階は、例えば、未加工データストリームに対して直接的に処理を行うことができる。即ち、未加工データストリームは、第一ＦＳＭラティス３０Ａの入力ブロック５２において受信され、第一ＦＳＭラティス３０Ａのプログラマブル素子は、未加工データストリームに対して反応することができる。（第二ＦＳＭラティス３０Ｂによって実装された）階層の第二段階は、第一段階からの出力を処理することができる。即ち、第二ＦＳＭラティス３０Ｂは、第二ＦＳＭラティス３０Ｂの入力ブロック５２において、第一ＦＳＭラティス３０Ａの出力ブロック５４からの出力を受信し、第二ＦＳＭラティス３０Ｂのプログラマブル素子は、第一ＦＳＭラティス３０Ａの出力に対して反応することができる。従って、この実施例において、第二ＦＳＭラティス３０Ｂは入力として、未加工データストリームを受信せず、第一ＦＳＭラティス３０Ａによって決定されたように未加工データストリームによって一致した対象となるパターンの表示を受信する。第二ＦＳＭラティス３０Ｂは、第一ＦＳＭラティス３０Ａから出力データストリームにおけるパターンを認識するＦＳＭを実装することができる。

図８は、コンパイラ２０が、ＦＳＭを実装するために、ラティス３０等のＦＳＭラティスをプログラミングするよう構成された画像にソースコードを変換する方法１１０の１つの実施例を示す。方法１１０は、ソースコードをシンタックスツリーに解析する(parse)こと（ブロック１１２）、シンタックスツリーを自動化装置に変換すること（ブロック１１４）、自動化装置を最適化すること（ブロック１１６）、自動化装置をネットリストに変換すること（ブロック１１８）、ネットリストをハードウェア上に設置すること（ブロック１２０）、ネットリストをルーティングすること（ブロック１２２）、及び結果生じた画像を掲載(publish)すること（ブロック１２４）を含む。

１つの実施例において、コンパイラ２０は、ソフト開発者がＦＳＭラティス３０でＦＳＭを実装するための画像を作成できるａｐｐｌｉｃａｔｉｏｎ ｐｒｏｇｒａｍｍｉｎｇ ｉｎｔｅｒｆａｃｅ（ＡＰＩ）を含む。コンパイラ２０は、ソースコード内の正規表現の入力一式を、ＦＳＭラティス３０をプログラミングするよう構成される画像へ変換する方法を提供する。コンパイラ２０は、フォンノイマン型アーキテクチャを有するコンピュータに対する命令によって実装することができる。これらの命令は、コンピュータのプロセッサ１２に対してコンパイラ２０の機能を実装させることができる。例えば、プロセッサ１２による実行が行われると、命令は、プロセッサ１２にアクセス可能なソースコード上のブロック１１２、１１４、１１６、１１８、１２０、１２２、１２４に記載される動作をプロセッサ１２に実行させることができる。

１つの実施例において、ソースコードは、一群の記号の中で記号のパターンを識別するためのサーチ文字列を記載する。サーチ文字列を記載するために、ソースコードは複数の正規表現（ｒｅｇｅｘ）を含むことができる。正規表現は、記号サーチパターンを記載するための文字列とすることができる。正規表現は、プログラミング言語、テキストエディタ、ネットワークセキュリティ等、様々なコンピュータ領域で広範囲に使用されている。１つの実施例において、コンパイラによってサポートされる正規表現は、非構造化データを分析するための基準を含む。非構造化データは、自由な形式であり、そのデータ内でワードに適用する指標が無いデータを含むことができる。ワードは、データ内で、バイト、印刷可能、印刷不可能の任意の組み合わせを含むことができる。１つの実施例において、コンパイラは、Ｐｅｒｌ（例えばＰｅｒｌ Ｃｏｍｐａｔｉｂｌｅ ｒｅｇｕｌａｒ ｅｘｐｒｅｓｓｉｏｎｓ（ＰＣＲＥ））、ＰＨＰ、Ｊａｖａ（登録商標）及び．ＮＥＴ言語等のｒｅｇｅｘを実装するため、複数の異なるソースコード言語をサポートすることができる。

ブロック１１２において、コンパイラ２０は、関連接続した演算子の配置を構成すべくソースコードを解析することができ、ここでは、異なる種類の演算子が、ソースコードによって実装された異なる機能（例えば、ソースコードにおいて正規表現によって実装された異なる機能）に対応する。ソースコードを解析することにより、ソースコードの一般的表現を作り出すことができる。１つの実施例において、一般的表現は、シンタックスツリーとして知られるツリーグラフ形態におけるソースコードにおける正規表現のコード化表現を含む。本明細書に記載されている実施例は、シンタックスツリー（「抽象シンタックスツリー」としても知られる）としての配置を指すが、別の実施例においては、具象シンタックスツリーやその他の配置も使用できる。

上記のように、コンパイラ２０は、多言語のソースコードをサポートすることができるため、解析は、ソースコードを、その言語に関わらず、例えばシンタックスツリー等の非言語固有の表現へ変換する。従って、コンパイラ２０による更なる処理（ブロック１１４、１１６、１１８、１２０）は、ソースコードの言語に関わらず、共通の入力構造から行うことができる。

上記のように、シンタックスツリーは、関連接続した複数の演算子を含む。シンタックスツリーは、複数の異なる種類の演算子を含むことができる。即ち、異なる演算子は、ソースコードにおける正規表現によって実装される異なる機能に対応することができる。

ブロック１１４において、シンタックスツリーは、自動装置へ変換される。自動装置は、ＦＳＭのソフトウェアモデルを備え、これによって決定性と非決定性とに分類することができる。決定性の自動装置は、所定の時間において単一実行経路を有するのに対し、非決定性の自動装置は、所定の時間において複数の同時実行経路を有する。自動装置は、複数の状態を含む。シンタックスツリーを自動装置に変換するために、シンタックスツリー内の演算子と演算子間の関係は、状態間の遷移を伴う状態に変換される。１つの実施例において、自動装置は、ＦＳＭラティス３０のハードウェアに部分的に基づいて変換される。

１つの実施例において、自動装置の入力記号は、アルファベット、数字０〜９、及びその他の印刷可能な文字の記号を含む。１つの実施例において、入力記号は、０〜２５５で表されるバイト値によって示される。１つの実施例において、自動装置は、グラフのノードが状態一式に対応する有向グラフとして表すことができる。１つの実施例において、入力記号αにおける状態ｐから状態ｑへの遷移即ちδ（ｐ，α）は、ノードｐからノードｑへの有向接続によって示される。１つの実施例において、自動装置の反転により、幾つかの記号αにおける遷移ｐ→ｑのそれぞれが同じ記号においてｑ→ｐと反転する新たな自動装置が作り出される。反転において、開始状態は最終状態となり、最終状態は開始状態となる。１つの実施例において、自動装置によって認識される（一致する）言語は、自動装置に連続して入力されると最終状態に到達する可能性のある全ての文字列一式である。自動装置によって認識される各文字列は、開始状態から１つまたは複数の最終状態へのパスをトレースする。

ブロック１１６において、自動装置が構築された後、特に、自動装置がその複雑さと大きさを減じるように最適化される。自動装置は、重複した状態を組み合わせることによって最適化することができる。

ブロック１１８において、最適化された自動装置がネットリストに変換される。自動装置のネットリストへの変換は、ＦＳＭラティス３０のハードウェア素子（例えば、ＳＭＥ３４、３６、その他の素子）に自動装置の各状態をマッピングし、ハードウェア素子間の接続を決定する。

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

ブロック１２２において、設置されたネットリストは、ネットリストに記載された接続を実現するために、選択したハードウェア素子を結合するため、プログラマブルスイッチング素子（例えば、インターブロックスイッチング素子４０、イントラブロックスイッチング素子４２、イントラロースイッチング素子４４）の設定を決定すべくルーティングされる。１つの実施例において、プログラマブルスイッチング素子の設定は、選択したハードウェア素子を接続するために使用されるＦＳＭラティス３０の特定の導体を決定することによって、また、プログラマブルスイッチング素子の設定によって決定される。ルーティングは、ブロック１２０におけるハードウェア素子間の接続のより具体的な限定を考慮することができる。従って、ルーティングは、ＦＳＭラティス３０の導体に実際に限界がある場合でも、適切な接続を行うために、グローバルな設置によって決定されるいくつかのハードウェア素子の位置を調節することができる。

ひとたびネットリストが設置され、ルーティングされると、設置され、ルーティングされたネットリストは、ＦＳＭラティス３０のプログラミングのための複数ビットに変換される。本明細書において、この複数ビットは画像と呼ばれる。

ブロック１２４において、画像はコンパイラ２０によって掲載される。画像は、ＦＳＭラティス３０の特定のハードウェア素子をプログラミングするための複数ビットを含む。画像が複数のビット（例えば０及び１）を含む実施形態において、その画像をバイナリ画像と呼ぶことができる。プログラミングしたＦＳＭラティス３０がソースコードによって記載された機能を有するＦＳＭを実装するよう、ＳＭＥ３４、３６、専用素子５８及びプログラマブルスイッチング素子の状態をプログラミングするために、ＦＳＭラティス３０にビットをロードすることができる。設置（ブロック１２０）とルーティング（ブロック１２２）は、ＦＳＭラティス３０内の特定位置にある特定のハードウェア素子を自動装置内の特定の状態にマッピングすることができる。従って、画像におけるビットは、（複数の）望ましい機能を実装するために、特定のハードウェア素子をプログラミングすることができる。１つの実施例において、マシンコードをコンピュータ可読媒体に保存することによって、画像を掲載することができる。別の実施例において、表示デバイスに画像を表示することによって、画像を掲載することができる。更に別の実施例において、画像をＦＳＭラティス３０にロードするプログラミングデバイス等、別のデバイスに画像を送信することによって、画像を掲載することができる。更に別の実施例において、ＦＳＭラティス（例えばＦＳＭラティス３０）に画像をロードすることによって、画像を掲載することができる。

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

本明細書に記載する方法は、少なくとも部分的に機械またはコンピュータにより実装されるものとすることができる。いくつかの実施例は、上記の実施例に記載された方法を実行するための電子デバイスを構成するように動作可能な命令によってコード化されたコンピュータ可読媒体または機械可読媒体を含むことができる。このような方法の実装は、マイクロコード、アセンブリ言語コード、高水準言語コード等のコードを含むことができる。このようなコードは、様々な方法を実行するためのコンピュータ可読命令を含むことができる。コードは、コンピュータプログラム製品の一部分を形成することができる。更に、コードは、実行中またはその他のときに１つまたは複数の揮発性または不揮発性コンピュータ可読媒体に有体物として保存することができる。これらのコンピュータ可読媒体は、ハードディスク、リムーバブル磁気ディスク、リムーバブル光ディスク（例えば、コンパクトディスクやデジタルビデオディスク）、磁気カセット、メモリカードまたはスティック、ランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）等を含むことができるが、これらに限定されない。

ここで図９を参照すると、ステートマシンエンジン１４の実施形態が示されている。既に記載したように、ステートマシンエンジン１４は、データバスを介してメモリ１６等のソースからデータを受信するよう構成される。図示した実施形態において、データはＤＤＲ３バスインターフェース１３０等のバスインターフェースを介してステートマシンエンジン１４に送信することができる。ＤＤＲ３バスインターフェース１３０は、１ギガバイト／秒以上の速度でデータを送受信することができる。当業者が理解するように、分析されるデータのソースによって、バスインターフェース１３０は、ＮＡＮＤフラッシュインターフェース、ＰＣＩインターフェース等、データソースとステートマシンエンジン１４との間でデータを送受信するのに適した任意のバスインターフェースとなることができる。既に記載したように、ステートマシンエンジン１４は、データを分析するよう構成される１つ以上のＦＳＭラティス３０を備える。ＦＳＭラティス３０のそれぞれは、２つの半分のラティスに分割することができる。図示した実施形態において、半分のラティスのそれぞれは、ラティス３０が４８ＫのＳＭＥを含むように、２４ＫのＳＭＥ（例えば、ＳＭＥ３４、３６）を備えていてもよい。ラティス３０は、図２〜５に関して既に記載したように配置された望ましい数のＳＭＥを備えることができる。更に、ＦＳＭラティス３０を１つだけ示しているが、既に記載したように、ステートマシンエンジン１４は、複数のＦＳＭラティス３０を備えることもできる。

分析対象のデータは、バスインターフェース１３０で受信され、複数のバッファとバッファインターフェースを介してＦＳＭラティス３０に送信される。図示した実施形態において、データパスは、データバッファ１３２、プロセスバッファ１３４、インターランク（ＩＲ）バス、及びプロセスバッファインターフェース１３６を備える。データバッファ１３２は、分析対象のデータを受信し、一時的に保存するように構成される。１つの実施形態において、データバッファ１３２は２つある（データバッファＡとデータバッファＢ）。データは、２つあるデータバッファ１３２のうち１つに保存され、一方で、ＦＳＭラティス３０による分析に供するため、残りの１つのデータバッファ１３２から削除されてもよい。図示した実施形態において、データバッファ１３２はそれぞれ３２キロバイトとすることができる。ＩＲバスとプロセスバッファインターフェース１３６は、プロセスバッファ１３４へのデータ送信を容易にする。ＩＲバスとプロセスバッファ１３４は、データが順番にＦＳＭラティス３０によって処理されることを確実にする。ＩＲバスとプロセスバッファ１３４、データが正しい順番で受信され分析されるように、データ送受信、時間情報、パッキング指示等を調整することができる。一般的にＩＲバスとプロセスバッファ１３４、ＦＳＭラティス３０の論理ランクによって複数のデータセットを並行して分析することができる。

図示した実施形態において、ステートマシンエンジン１４は、ステートマシンエンジン１４による膨大な量のデータの伝送を補助するために、解凍装置１３８と圧縮装置１４０とを備えることができる。圧縮装置１４０と解凍装置１３８は協働して、データ伝送時間を最小限にするため、データを圧縮できるようにする。分析対象のデータを圧縮することにより、バス利用時間を最小化することができる。コンパイラ２０によって提供される情報に基づいて、ステートマシンエンジンが使用される可能性が低い情報を提供するため、ステートマシンエンジン１４に対してマスクが提供されてもよい。圧縮装置１４０と解凍装置１３８は、様々なバースト長のデータを取り扱うように構成することもできる。圧縮データを膨らませて、それぞれの圧縮領域が終端する時期についてのインジケータを備えることによって、圧縮装置１４０は、ステートマシンエンジン１４による全体的な処理速度を改善することができる。圧縮装置１４０と解凍装置１３８は、ＦＳＭラティス３０による分析の後、一致結果データを圧縮したり解凍したりするために使用することもできる。

既に記載したように、ＦＳＭラティス３０の出力は、状態ベクトルを含むことができる。状態ベクトルは、ＦＳＭラティス３０のプログラマブル素子の状態（例えば、アクティブ化されているか否か）を含む。状態ベクトルの各々は、更なる階層的処理と分析に供するため、状態ベクトルキャッシュメモリ１４２に一時的に保存することができる。即ち、新たなデータセットに再度プログラミングし、及び／または更なる分析に供するためにステートマシンを解放しつつ、更なる分析に供するために最終の状態が使用可能となるよう、ステートマシンそれぞれの状態を保存することができる。典型的なキャッシュと同様に、例えば、ここではＦＳＭラティス３０による迅速な取り出しと使用のために、状態ベクトルキャッシュメモリによって、ここでは状態ベクトルである情報の保存が可能になる。状態ベクトルメモリバッファ、状態ベクトル中間入力バッファ１４６、及び状態ベクトル中間出力バッファ１４８等の追加的なバッファを状態ベクトルキャッシュメモリ１４２とともに利用して、ステートマシンエンジン１４のパケット送信プロトコルを順守しつつ、状態ベクトルの迅速な分析と保存を行うことができる。

ひとたび、対象となる結果がＦＳＭラティス３０によって作成されると、一致結果は、一致結果メモリ１５０に保存することができる。即ち、一致（例えば、対象となっているパターンの検出）を示す「一致ベクトル」を一致結果メモリ１５０に保存することができる。一致結果は、その後、例えば、バスインターフェース１３０を通ってプロセッサ１２へ送信するため、一致バッファ１５２に送信することができる。既に記載したように、一致結果は圧縮することができる。

ステートマシンエンジン１４において、追加的なレジスタとバッファを備えることもできる。例えば、ステートマシンエンジン１４は、コントロールステータスレジスタ(control and status register)１５４を備えることができる。また、当初のＦＳＭラティス３０のプログラミングに使用し、分析期間中のＦＳＭラティス３０におけるマシンの状態を回復するためのリストアプログラムバッファ(restore and program buffer)１５６を備えることができる。同様に、設定と使用のために、マップを保存し回復するためのセーブリペアマップバッファ(save and repair map buffer)１５８も備えることができる。

図１０は、図５の検出セル８６をより詳細に示している。既に記載したように、この検出セル８６は、第一入力６２と第二入力８２とを受信することができる。１つの実施形態において、第一入力６２は、検出セル８６のイネーブル信号として動作するための統合イネーブル入力(unified enable input)とすることができる。既に論じたように、この入力６２は、行３８におけるＧＯＴ６０のＳＭＥ３４のそれぞれに結合した、ルーティングから受信した信号を含むことができる。また、行３８におけるＧＯＴ６０のＳＭＥ３６における同一の検出セル８６は、検出セル８６のイネーブル信号として動作するために、統合イネーブル入力として入力６２をミラーリングする入力６４を受信することもできることに留意すべきである。そのため、入力６４は、行３８におけるＧＯＴ６０のＳＭＥ３６のそれぞれに結合したルーティングから受信される信号を含むことができる。従って、ＳＭＥ３４の検出セル８６については以下により詳細に論じるが、ＳＭＥ３６の検出セル８６も実質的に同様に動作することに留意すべきである。

図１０に示すように、検出セルは、Ｄ‐フリップフロップ１６０を備えることができる。このＤ‐フリップフロップは、入力１６２のクロック信号とともに、統合イネーブル入力６２を受信するように作動することができる。従って、Ｄ‐フリップフロップ１６０は、入力１６２（クロック入力）におけるポジティブエッジ(positive edge)が受信されると、結果を統合イネーブル入力６２（Ｄ入力）の状態であり得るＱ出力１６４に駆動する。このようにして、Ｄ‐フリップフロップ１６０によって、以下に記載するように、検出セル８６が所定時間ＳＭＥのメモリセル８０を使用して行われる分析の結果のみを出力するクロックイネーブル回路となることができる。検出セル８６は、統合イネーブル入力６２の数値や入力１６２のクロック信号の数値とは無関係に、Ｑ出力１６４をアクティブなハイ信号に設定するために使用できるセット入力１６６と、Ｑ出力１６４をアクティブなロウ信号に設定するために使用できるリセット入力１６８とを含むことができることにも留意すべきである。

図１０の検出セル８６は、第二入力８２を受信することもできる。既に論じたように、この入力８２は、検出ライン８２と対応するものであってよい。この検出ライン８２は、検出セル８６に対応するＳＭＥ３４の１つまたは複数のメモリセル８０から分析結果（例えば一致結果）を運ぶことができる。従って、選択したメモリセル８０は、その保存したデータ状態を出力として検出ライン８２に提供し、これがその後、検出セル８６に分析結果として送信される。検出ライン８２のこの結果は、検出セル８６内のＡＮＤゲート１７０に送信することができる。また、Ｑ出力１６４は、ＡＮＤゲート１０７に送信することができる。例えば、検出ライン８２の正しい一致(qualified match)が起き、かつ検出セル８６が統合イネーブル入力６２を介してアクティブ化される（例えば、アクティブな状態になる）と、一致結果出力が、検出セル８６から出力７２（ＳＭＥ３６の検出セル８６については出力７４）に対して出力される。この正しい一致とは、例えば、単一のＳＭＥ３４からの分析されたデータストリームにおける一致を示し、これは、例えば、データストリーム内のパターンを検索するために、その他のＳＭＥ３４、３６におけるその他の一致とともに利用することができる。検出セル８６におけるＤ‐フリップフロップ１６０を使用することによって、ここから生成した検索や結果をクロック信号に基づいて所定期間実行することができる。また、（例えば、統合イネーブル入力６２を選択的に使用することによって、）ＳＭＥ３４、３６から（例えば出力７２、７４について）いつ、どの結果を出力するかについての制御も実現することができる。更に、統合イネーブル入力６２（及び統合イネーブル入力６４）を介したＳＭＥ３４、３６のこの選択的アクティブ化によって、データストリームの全体的なより広い分析の一部として、ＳＭＥ３４、３６のそれぞれにおいて見出される結果を実現することができる。

図１１は、行３８のＧＯＴ６０に結合することができるローカルルーティングマトリックス１７２の１つの例を示す。図に示すように、ＳＭＥ３４は、データ分析素子１７１とともにＳＭＥ３４のメモリセル８０を備えることができる検出セル８６も備えている。データ分析素子１７１は、ＳＭＥ３４の検出ライン８２と結合することができる。同様に、ＳＭＥ３６は、データ分析素子１７３とともにメモリセル８０を備えることができる検出セル８６も備えている。また、データ分析素子１７３は、ＳＭＥ３６の検出ライン８２と結合することができる。更に、図１１に示すＳＭＥ３４、３６と結合することに加えて、ローカルルーティングマトリックス１７２は、特定の行３８のＧＯＴ６０のＳＭＥ３４、３６の全ての対と結合することができる。従って、ローカルルーティングマトリックス１７２は、プログラマブルイントラロースイッチング素子４４と、行相互接続導体６８、７０（以下で記載するように「ロー（行）ルーティングライン」とも呼ばれる）を備えることができる。

１つの実施形態において、ローカルルーティングマトリックス１７２は、複数のロールーティングライン１７４、１７６、１７８、１８０、１８２、１８４、１８６、１８８、１９０、１９２、１９４、１９６、１９８、２００、２０２、２０４（以後、まとめて「ロールーティングライン１７４〜２０４」と呼ぶ）を備えることができる。このようにして、ロールーティングライン１７４‐２０４の数は、所定の行におけるＧＯＴの数に対応することができる。このように、示した実施形態において、１７４〜２０４の１６本のロールーティングラインが存在する。しかしながら、ローカルルーティングマトリックス１７２において、より数の少ないまたは数の多いロールーティングラインが利用できる点について理解されるべきである。

ロールーティングライン１７４〜２０４のそれぞれは、１つまたは複数のＧＯＴ６０の任意のＳＭＥ３４、３６に対するイネーブル信号を提供するために利用することができる。従って、これらのロールーティングライン１７４〜２０４を使用することにより、特定のＳＭＥ（例えばＳＭＥ３４）に対する特定の検出セル８６をアクティブ化することができる。これは、（例えばプログラミングを介して）選択的にロールーティングライン１７４〜２０４をＳＭＥ３４、３６の統合イネーブル入力６２、６４と結合することによって実現することができる。また、イネーブル信号をＳＭＥ３４、３６に提供する上で更なる柔軟性を提供するために、ロールーティングライン１７４〜２０４は、２つのＳＭＥ３４、３６の間で分割することができる。例えば、行３８におけるＳＭＥ３４、３６のそれぞれをアクティブ化するためにロールーティングライン１７４、１７６、１７８、１８０、１８２、１８４、１８６及び１８８を利用することができる。また、行３８におけるＳＭＥ３４に統合イネーブル入力６２を送信するためにロールーティングライン１９０、１９４、１９８及び２０２を利用することができる一方、行３８におけるＳＭＥ３６に統合イネーブル入力６４を送信するためにロールーティングライン１９２、１９６、２００及び２０４を利用することができる。このように、例えば行におけるＳＭＥ３４の合計１６の検出セル８６のうちＳＭＥ３４の最大１２の検出セル８６が直接アドレス指定され、一方、残りの検出セル８６は、例えば図５に関して既に記載したスイッチング素子７９の使用を介してアドレス指定される。このようにして、全体的な柔軟性と、行３８における任意のＳＭＥ３４、３６の任意の検出セル８６をアクティブ化する能力を維持しつつ、ロールーティングライン１７４〜２０４の全体数を減少させることができる。

また、図１１はイントラグループ回路２０６を備える点に留意すべきである。このイントラグループ回路２０６の出力は、出力６６とすることができ、これは、それぞれのＧＯＴ６０に対する出力を送信することができる。１つの実施形態において、この出力６６は、アクティブなＳＭＥ３４、３６において発生した結果を反映して、ＧＯＴ６０の出力６６を送信するために、ロールーティングライン１７４、１７６、１７８、１８０、１８２、１８４、１８６、及び１８８のいずれかに結合することができる。ＧＯＴの出力６６を送信するためにロールーティングライン１７４、１７６、１７８、１８０、１８２、１８４、１８６、及び１８８を使用することにより（ＳＭＥ３４、３６の統合イネーブル入力６２、６４を有するローカルルーティングマトリックス１７２に共通している）、システム全体の柔軟性を維持しつつ、ロールーティングライン１７４‐２０４の全体数を減少させることができる。

図１１のイントラグループ回路２０６は、図５に関して既に論じたＧＯＴ６０の素子を備えていてもよい点に留意すべきである。イントラグループ回路２０６におけるこれらの素子の特別な機能と相互接続については、図１２との関連で、後ほど、より詳細に論じる。

図１２のイントラグループ回路２０６は、ＳＭＥ３４、３６に結合することを示した入力６２、６４、出力７２、７４を備える。入力６２、６４、出力７２、７４は、ＳＭＥ３４、３６に対するそれぞれの関係性に関して言及されているのであり、必ずしもイントラグループ回路２０６におけるそれらの機能について言及したものではないことに留意すべきである。また、イントラグループ回路２０６は、それぞれ出力７２、７４と結合するＯＲゲート７６、３−１マルチプレクサ７８、及びスイッチング素子７９を備える。図に示したように、出力７２と結合するスイッチング素子７９は、例えば、カスケード検索ができるように、ＳＭＥ３４の出力７２が、ＳＭＥ３６の統合イネーブル入力６４に送信されるようにすることができる。これとともに、またはこれに替えて、出力７２と結合するスイッチング素子７９は、ＳＭＥ３４の統合イネーブル入力６２が、ＳＭＥ３６の統合イネーブル入力６４に送信され、及び／またはＳＭＥ３４の出力７２が、ＯＲゲート７６に送信されるようにすることができる。既に論じたように、ＳＭＥ３４の統合イネーブル入力６２がＳＭＥ３６の統合イネーブル入力６４に送信されるようにできれば、ロールーティングライン１７４〜２０４の共有を介して所定の行３８のＳＭＥ３６における全ての検出セル素子８６の全面的なアドレス指定が可能になる。

同様に、出力７４と結合するスイッチング素子７９は、例えば、カスケード検索ができるように、ＳＭＥ３６の出力７４が、ＳＭＥ３４の統合イネーブル入力６２に送信されるようにすることができる。これとともに、またはこれに替えて、出力７４と結合するスイッチング素子７９は、ＳＭＥ３６の統合イネーブル入力６４が、ＳＭＥ３４の統合イネーブル入力６２に送信され、及び／またはＳＭＥ３６の出力７４が、ＯＲゲート７６に送信されるようにすることができる。再び、ＳＭＥ３６の統合イネーブル入力６４がＳＭＥ３４の統合イネーブル入力６２に送信されるようにできれば、ロールーティングライン１７４〜２０４の共有を介して所定の行３８のＳＭＥ３４における全ての検出セル素子８６の全面的なアドレス指定が可能になる。なお、図示していないが、出力７２、７４は、１つのスイッチング素子７９を介して出力７２を入力６２と結合することによって、また、別のスイッチング素子７９を介して出力７７を入力６４と結合することによって、出力７２、７４を生成したＳＭＥ３４、３６にループバックできることに留意すべきである。

イントラグループ回路２０６の３−１マルチプレクサ７８は、ＧＯＴ６０の共通の出力６６を形成するためにＳＭＥ３４、３６の両方の出力７２、７４とともに結合するために使用することができる第一ＳＭＥ３４、第二ＳＭＥ３６、またはＯＲゲート７６のいずれかとＧＯＴ６０の出力６６を結合するように設定することができる。従って、３−１マルチプレクサ７８は、第一出力選択入力２０８と第二出力選択入力２１０とを備えることができる。これにより、これらの出力選択入力２０８、２１０は、出力６６に送信された出力をプログラム可能に選択することができる。このプログラミングは、例えば、ＦＳＭラティス３０の初期プログラミング段階で行われるロードされた画像に基づいて達成することができる。図１３は、どのようにして出力選択入力２０８、２１０がＧＯＴ６０の出力６６をプログラム可能に選択するかについてその１つの例を記載した真偽表２１２を示す。

図１３に示すように、出力選択入力２０８、２１０の両方がロウ（即ち０）である場合、ＧＯＴ６０の出力６６は、高インピーダンス信号となり、その結果、値が出力６６に送信されるのを効果的に防ぐことになる。出力選択入力２０８がハイ（即ち１）であり、出力選択入力２１０がロウである場合は、ＧＯＴ６０の出力６６は、第一ＳＭＥ３４の出力、即ち出力７２となる。出力選択入力２０８がロウであり、出力選択入力２１０がハイである場合は、ＧＯＴ６０の出力６６は、第二ＳＭＥ３６の出力、即ち出力７４となる。最後に、出力選択入力２０８、２１０の両方がハイである場合は、ＧＯＴ６０の出力６６は、ＯＲゲート７６の出力、即ち出力７４との論理和をとった出力７２となる。このようにして、３−１マルチプレクサ７８は、ＧＯＴ６０の出力６６として、プログラム可能に出力無し、出力７２、出力７４、または出力７４との論理和をとった出力７２を選択する。また、３−１マルチプレクサは、図１２に示した具体的な実施形態に限らず、その他のプログラム可能な構成において動作できることに留意すべきである。

本発明に対して、様々な変形や代替的な形態を加えてもよいが、具体的な実施形態として、図面による例示によって、また本明細書の記載において詳細に示した。しかしながら、本発明は、ここで開示した特定の内容に限定することを意図していない旨を理解すべきである。そうではなく、本発明は、以下に示す添付の請求項によって定義される発明の趣旨と範囲内にある全ての変形、均等物、代替物を網羅するものである。

Claims (11)

1. 複数の第一メモリセルを備える第一データ分析素子であって、前記第一データ分析素子がデータストリームの少なくとも一部分を分析した第一分析結果を出力するように構成された第一データ分析素子と、
   第一入力として前記第一分析結果を受信するように構成された第一ＡＮＤゲートと、前記第一ＡＮＤゲートの第二入力と結合する出力を備える第一Ｄフリップフロップと、を備える第一検出セルと、
   複数の第二メモリセルを備える第二データ分析素子であって、前記第二データ分析素子が前記データストリームの少なくとも一部分を分析した第二分析結果を出力するように構成された第二データ分析素子と、
   第一入力として前記第二分析結果を受信するように構成された第二ＡＮＤゲートと、前記第二ＡＮＤゲートの第二入力と結合する出力を備える第二Ｄフリップフロップと、を備える第二検出セルと、
   前記第一ＡＮＤゲート及び前記第二ＡＮＤゲートからの出力をそれぞれ第１入力及び第２入力として受けるＯＲゲートと、
   前記第一ＡＮＤゲート、前記第二ＡＮＤゲート及び前記ＯＲゲートからの出力のうち、いずれか一つを出力するマルチプレクサと、
   を備えることを特徴とするデバイス。
2. 前記第一Ｄフリップフロップは、第一イネーブル信号を受信するように構成されたデータ入力を備え、
   前記第二Ｄフリップフロップは、第二イネーブル信号を受信するように構成されたデータ入力を備えることを特徴とする、請求項１に記載のデバイス。
3. 前記第一Ｄフリップフロップ及び前記第二Ｄフリップフロップはクロック信号に応じて前記第一イネーブル信号及び前記第二イネーブル信号をそれぞれの前記出力から出力する請求項２に記載のデバイス。
4. 複数のプログラマブル素子と、
   前記複数のプログラマブル素子に対して共通に設けられるイントラブロックスイッチング素子と、を備え、前記複数のプログラマブル素子は、各々が、
   複数の第一メモリセルを備える第一データ分析素子であって、前記第一データ分析素子がデータストリームの少なくとも一部分を分析した第一分析結果を出力するように構成された第一データ分析素子と、
   第一Ｄフリップフロップと、前記第一Ｄフリップフロップの出力及び前記第一データ分析素子の出力を受ける第一ＡＮＤゲートを備える第一検出セルと、
   複数の第二メモリセルを備える第二データ分析素子であって、前記第二データ分析素子が前記データストリームの少なくとも一部分を分析した第二分析結果を出力するように構成された第二データ分析素子と、
   第二Ｄフリップフロップと、前記第二Ｄフリップフロップの出力及び前記第二データ分析素子の出力を受ける第二ＡＮＤゲートを備える第二検出セルと、
   前記第一ＡＮＤゲートの出力及び前記第二ＡＮＤゲートの出力を受けるＯＲゲートと、
   前記第一ＡＮＤゲートの出力、前記第二ＡＮＤゲートの出力及び前記ＯＲゲートの出力のうち、いずれか一つを出力するマルチプレクサと、
   を含むデバイス。
5. 前記第一Ｄフリップフロップは、第一イネーブル信号を受信するように構成されたデータ入力を備え、
   前記第二Ｄフリップフロップは、第二イネーブル信号を受信するように構成されたデータ入力を備えることを特徴とする、請求項４に記載のデバイス。
6. 前記第一Ｄフリップフロップ及び前記第二Ｄフリップフロップはクロック信号に応じて前記第一イネーブル信号及び前記第二イネーブル信号をそれぞれの前記出力から出力する請求項５に記載のデバイス。
7. 前記複数のプログラマブル素子において受信される前記第一イネーブル信号及び前記第二イネーブル信号を共通の信号として前記イントラブロックスイッチング素子から伝送する第一相互接続導体と、
   前記複数のプログラマブル素子において受信される前記第一イネーブル信号のみを前記イントラブロックスイッチング素子から伝送する第二相互接続導体と、
   前記複数のプログラマブル素子において受信される前記第二イネーブル信号のみを前記イントラブロックスイッチング素子から伝送する第三相互接続導体と、
   を更に備える請求項５または６に記載のデバイス。
8. 入力ブロックと、
   出力ブロックと、
   複数のブロックと、
   前記入力ブロック、前記出力ブロック及び複数のブロック間にそれぞれ設けられ、前記入力ブロック、前記出力ブロック及び前記複数のブロック相互間の信号の送受信を制御する複数のインターブロックスイッチング素子と、を備え、前記複数のブロックは各々が、
   複数のプログラマブル素子と、
   前記複数のプログラマブル素子に対して共通に設けられ、前記複数のインターブロックスイッチング素子のうち少なくとも一つの対応するインターブロックスイッチング素子と信号の送受信を行うイントラブロックスイッチング素子と、を備え、前記複数のプログラマブル素子は各々が、
   複数の第一メモリセルを備える第一データ分析素子であって、前記第一データ分析素子がデータストリームの少なくとも一部分を分析した第一分析結果を出力するように構成された第一データ分析素子と、
   第一Ｄフリップフロップと、前記第一Ｄフリップフロップの出力及び前記第一データ分析素子の出力を受ける第一ＡＮＤゲートを備える第一検出セルと、
   複数の第二メモリセルを備える第二データ分析素子であって、前記第二データ分析素子が前記データストリームの少なくとも一部分を分析した第二分析結果を出力するように構成された第二データ分析素子と、
   第二Ｄフリップフロップと、前記第二Ｄフリップフロップの出力及び前記第二データ分析素子の出力を受ける第二ＡＮＤゲートを備える第二検出セルと、
   前記第一ＡＮＤゲートの出力及び前記第二ＡＮＤゲートの出力を受けるＯＲゲートと、
   前記第一ＡＮＤゲートの出力、前記第二ＡＮＤゲートの出力及び前記ＯＲゲートの出力のうち、いずれか一つを出力するマルチプレクサと、
   を含むデバイス。
9. 前記第一Ｄフリップフロップは、第一イネーブル信号を受信するように構成されたデータ入力を備え、
   前記第二Ｄフリップフロップは、第二イネーブル信号を受信するように構成されたデータ入力を備えることを特徴とする、請求項８に記載のデバイス。
10. 前記第一Ｄフリップフロップ及び前記第二Ｄフリップフロップはクロック信号に応じて前記第一イネーブル信号及び前記第二イネーブル信号をそれぞれの前記出力から出力する請求項９に記載のデバイス。
11. 前記複数のプログラマブル素子において受信される前記第一イネーブル信号及び前記第二イネーブル信号を共通の信号として前記イントラブロックスイッチング素子から伝送する第一相互接続導体と、
    前記複数のプログラマブル素子において受信される前記第一イネーブル信号のみを前記イントラブロックスイッチング素子から伝送する第二相互接続導体と、
    前記複数のプログラマブル素子において受信される前記第二イネーブル信号のみを前記イントラブロックスイッチング素子から伝送する第三相互接続導体と、
    を更に備える請求項９または１０に記載のデバイス。

Images