(57)【要約】装置は、プロセッサ（１２）からデータストリーム（１７０）の第一の部分を受信するように構成された第一のステートマシンエンジン（１４）、及びプロセッサ（１２）からデータストリーム（１７０）の第二の部分を受信するように構成された第二のステートマシンエンジン（１４）を含むことができる。装置は、第一のステートマシンエンジン（１４）と第二のステートマシンエンジン（１４）との間でデータ転送を可能にするように構成されたバッファインターフェイス（１３６）を含む。バッファインターフェイス（１３６）は、第一及び第二のステートマシンエンジン（１４）に結合されたインターフェイスデータバス（３７６）を含む。バッファインターフェイス（１３６）は、第一のステートマシンエンジン（１４）と第二のステートマシンエンジン（１４）との間でデータを提供するように構成される。【選択図】図１０
2016515266.tif 000002
【特許請求の範囲】
【請求項１】
第一の複数のデータ線及び第二の複数のデータ線を備えており、前記第一の複数のデータ線が、前記第二の複数のデータ線とパラレルにデータを提供するように構成された、データバスと、
前記第一の複数のデータ線に結合された第一のステートマシンエンジンと、
前記第二の複数のデータ線に結合された第二のステートマシンエンジンと、を備えており、前記第二のステートマシンエンジンが前記第二の複数のデータ線から前記データストリームの第二の部分を受信するのとパラレルに、前記第一のステートマシンエンジンが前記第一の複数のデータ線からデータストリームの第一の部分を受信するように構成されており、
前記第二のステートマシンエンジンが、前記データストリームの前記第二の部分を前記第一のステートマシンエンジンに提供するように構成されており、前記第一のステートマシンエンジンが、前記データストリームの前記第一の部分及び前記データストリームの前記第二の部分を解析するように構成された、装置。
【請求項２】
前記第一及び第二のステートマシンエンジンの各々が、複数のコンフィギュラブル素子を有するそれぞれのステートマシンラチスを備えており、前記複数のコンフィギュラブル素子の各々が、前記データストリームの少なくとも一部を解析し、前記解析の結果を出力するように構成された複数のセルを備えた、請求項１の装置。
【請求項３】
前記第一のステートマシンエンジン及び前記第二のステートマシンエンジンに結合されたアドレスバスを備えた、請求項１の装置。
【請求項４】
前記第一及び第二のステートマシンエンジンが、前記アドレスバスから信号をパラレルに受信するように構成された、請求項３の装置。
【請求項５】
前記第一のステートマシンエンジンに結合された第一の制御線、及び前記第二のステートマシンエンジンに結合された第二の制御線を備えており、前記第二のステートマシンエンジンが前記第二の制御線から第二の組の信号を受信するのとパラレルに、前記第一のステートマシンエンジンが、前記第一の制御線から第一の組の信号を受信するように構成された、請求項１の装置。
【請求項６】
前記データバスが、第三の複数のデータ線、第四の複数のデータ線、第五の複数のデータ線、第六の複数のデータ線、第七の複数のデータ線、及び第八の複数のデータ線を備えており、前記第一の複数のデータ線が、前記第二の複数のデータ線、前記第三の複数のデータ線、前記第四の複数のデータ線、前記第五の複数のデータ線、前記第六の複数のデータ線、前記第七の複数のデータ線、及び前記第八の複数のデータ線とパラレルにデータを提供するように構成された、請求項１の装置。
【請求項７】
前記第三の複数のデータ線に結合された第三のステートマシンエンジンと、
前記第四の複数のデータ線に結合された第四のステートマシンエンジンと、
前記第五の複数のデータ線に結合された第五のステートマシンエンジンと、
前記第六の複数のデータ線に結合された第六のステートマシンエンジンと、
前記第七の複数のデータ線に結合された第七のステートマシンエンジンと、
前記第八の複数のデータ線に結合された第八のステートマシンエンジンと、を備えた、請求項６の装置。
【請求項８】
前記第二のステートマシンエンジンが前記第二の複数のデータ線から前記データストリームの前記第二の部分を受信するのとパラレルに、前記第一のステートマシンエンジンが前記第一の複数のデータ線から前記データストリームの前記第一の部分を受信するように構成されており、前記第三のステートマシンエンジンが、前記第三の複数のデータ線から前記データストリームの第三の部分を受信し、前記第四のステートマシンエンジンが、前記第四の複数のデータ線から前記データストリームの第四の部分を受信し、前記第五のステートマシンエンジンが、前記第五の複数のデータ線から前記データストリームの第五の部分を受信し、前記第六のステートマシンエンジンが、前記第六の複数のデータ線から前記データストリームの第六の部分を受信し、前記第七のステートマシンエンジンが、前記第七の複数のデータ線から前記データストリームの第七の部分を受信し、そして前記第八のステートマシンエンジンが、前記第八の複数のデータ線から前記データストリームの第八の部分を受信する、請求項７の装置。
【請求項９】
前記第三のステートマシンエンジンが、前記データストリームの前記第三の部分を前記第一のステートマシンエンジンに提供するように構成されており、前記第四のステートマシンエンジンが、前記データストリームの前記第四の部分を前記第一のステートマシンエンジンに提供するように構成されており、前記第五のステートマシンエンジンが、前記データストリームの前記第五の部分を前記第一のステートマシンエンジンに提供するように構成されており、前記第六のステートマシンエンジンが、前記データストリームの前記第六の部分を前記第一のステートマシンエンジンに提供するように構成されており、前記第七のステートマシンエンジンが、前記データストリームの前記第七の部分を前記第一のステートマシンエンジンに提供するように構成されており、前記第八のステートマシンエンジンが、前記データストリームの前記第八の部分を前記第一のステートマシンエンジンに提供するように構成されており、そして前記第一のステートマシンエンジンが、前記データストリームの前記第三の部分、前記データストリームの前記第四の部分、前記データストリームの前記第五の部分、前記データストリームの前記第六の部分、前記データストリームの前記第七の部分、及び前記データストリームの前記第八の部分を解析するように構成された、請求項８の装置。
【請求項１０】
前記第一のステートマシンエンジンが、前記データストリームの前記第一の部分を格納するように構成された第一のバッファを備えており、前記第二のステートマシンエンジンが、前記データストリームの前記第二の部分を格納するように構成された第二のバッファを備えた、請求項１の装置。
【請求項１１】
前記第一のステートマシンエンジンが、前記データストリームの前記第一の部分及び前記データストリームの前記第二の部分を格納するように構成された第三のバッファを備えた、請求項１０の装置。
【請求項１２】
前記第二のステートマシンエンジンから前記データストリームの前記第二の部分を受信し、前記データストリームの前記第二の部分を前記第一のステートマシンエンジンに提供するように構成されたバッファインターフェイスを備えた、請求項１の装置。
【請求項１３】
前記バッファインターフェイスが、前記第一のステートマシンエンジン及び前記第二のステートマシンエンジンの少なくともいずれかに命令を提供するように構成された、請求項１２の装置。
【請求項１４】
前記第一のステートマシンエンジンが、前記バッファインターフェイスに提供された第一の組のデータをラッチするように構成された第一のバッファを備えており、前記第二のステートマシンエンジンが、前記バッファインターフェイスに提供された第二の組のデータをラッチするように構成された第二のバッファを備えた、請求項１２の装置。
【請求項１５】
前記第一のバッファが、第一の所定間隔において前記第一の組のデータをラッチするように構成されており、前記第二のバッファが、第二の所定間隔において前記第二の組のデータをラッチするように構成された、請求項１４の装置。
【請求項１６】
モジュールを備えた、請求項１の装置。
【請求項１７】
データ解析システムを備えた、請求項１の装置。
【請求項１８】
前記第一及び第二のステートマシンエンジンの各々が別個のチップを備えた、請求項１の装置。
【請求項１９】
第一のステートマシンエンジンにおいて、データバスのうちの第一の複数のデータ線からデータストリームの第一の部分を受信することと、
第二のステートマシンエンジンにおいて、前記データバスのうちの第二の複数のデータ線から前記データストリームの第二の部分を受信することと、ここでは、前記第一のステートマシンエンジンが前記データストリームの前記第一の部分を受信するのとパラレルに、前記データストリームの前記第二の部分が前記第二のステートマシンエンジンにおいて受信され、
前記第二のステートマシンエンジンから前記データストリームの前記第二の部分を前記第一のステートマシンエンジンに提供することと、を含む、データ解析方法。
【請求項２０】
前記第一のステートマシンエンジンを使用して、前記データストリームの前記第一の部分及び前記データストリームの前記第二の部分を解析することを含む、請求項１９の方法。
【請求項２１】
前記第一のステートマシンエンジンの第一のメモリアドレス、及び前記第二のステートマシンエンジンの第二のメモリアドレスをパラレルに選択するためのアドレス信号を、前記第一及び第二のステートマシンエンジンにおいて受信することを含む、請求項１９の方法。
【請求項２２】
前記第一のメモリアドレスが前記第二のメモリアドレスと等しい、請求項２１の方法。
【請求項２３】
データストリームの第一の部分を受信するように構成された第一のステートマシンエンジンと、
前記データストリームの第二の部分を受信するように構成された第二のステートマシンエンジンと、
前記第一のステートマシンエンジンと前記第二のステートマシンエンジンとの間でデータ転送を可能にするように構成されたバッファインターフェイスと、を備えており、前記バッファインターフェイスが、前記第一のステートマシンエンジン及び前記第二のステートマシンエンジンに結合されており、前記第一のステートマシンエンジンと前記第二のステートマシンエンジンとの間でデータを提供するように構成されたインターフェイスデータバスを備えている、装置。
【請求項２４】
前記インターフェイスデータバスが双方向バスである、請求項２３の装置。
【請求項２５】
前記インターフェイスデータバスが８ビットインターランクデータバスを備えた、請求項２３の装置。
【請求項２６】
前記バッファインターフェイスが、前記第一のステートマシンエンジン及び前記第二のステートマシンエンジンに結合されており、前記第一のステートマシンエンジンと前記第二のステートマシンエンジンとの間のデータ転送を調整するように構成されたインストラクションバスをさらに備えた、請求項２３の装置。
【請求項２７】
前記第一のステートマシンエンジンが、前記第一のステートマシンエンジンと前記第二のステートマシンエンジンとの間のデータ転送を調整するための命令を前記インストラクションバスに提供するように構成されたマスタデバイスである、請求項２６の装置。
【請求項２８】
前記第二のステートマシンエンジンが、マスタデバイスによって前記インストラクションバスに提供された命令を受信するように構成されたスレーブデバイスであり、前記命令が、前記第二のステートマシンエンジが前記データストリームの前記第二の部分を前記インターフェイスデータバスに提供する時点を制御するように設定された、請求項２６の装置。
【請求項２９】
前記第一のステートマシンエンジン及び前記第二のステートマシンエンジンの少なくともいずれかが、データを前記インターフェイスデータバスに提供すること、前記インターフェイスデータバスへのデータの提供を停止すること、またはそれらの幾つかの組み合わせを可能にするように構成された出力を備えた、請求項２３の装置。
【請求項３０】
前記第一のステートマシンエンジン及び前記第二のステートマシンエンジンの少なくともいずれかが、前記インターフェイスデータバスに提供されたデータを同期するように構成された出力を備えた、請求項２３の装置。
【請求項３１】
前記第一及び第二のステートマシンエンジンが論理グループの一部であり、前記第一のステートマシンエンジンが、前記データストリームの、前記第二のステートマシンエンジンと同じ部分を解析するように構成された、請求項２３の装置。
【請求項３２】
前記第一のステートマシンエンジンが第一の論理グループの一部であり、前記第二のステートマシンエンジンが第二の論理グループの一部であり、前記第一及び第二の論理グループが、前記データストリームの異なる部分を解析するように構成された、請求項２３の装置。
【請求項３３】
前記第一のステートマシンエンジンが第一の論理グループの一部であり、前記第二のステートマシンエンジンが第二の論理グループの一部であり、前記第一の論理グループ及び前記第二の論理グループの少なくともいずれかが、複数のステートマシンエンジンを備えた、請求項２３の装置。
【請求項３４】
前記第一の論理グループが、前記第二の論理グループよりも多い数のステートマシンエンジンを備えた、請求項３３の装置。
【請求項３５】
前記第一のステートマシンエンジンが、第一のバス位置、及び前記第一のバス位置に対応するデータを格納するように構成された第一のストレージを備えており、前記第二のステートマシンエンジンが、第二のバス位置、及び前記第二のバス位置に対応するデータを格納するように構成された第二のストレージを備えた、請求項２３の装置。
【請求項３６】
前記第一のステートマシンエンジンが、前記インターフェイスデータバスのバス幅に対応するデータを格納するように構成された、請求項２３の装置。
【請求項３７】
前記第一のステートマシンエンジンが、同期信号が前記第一及び第二のステートマシンエンジンによって受信された後に前記インターフェイスデータバスに提供された第一のデータセットを格納するように構成されており、前記第二のステートマシンエンジンが、前記同期信号が前記第一及び第二のステートマシンエンジンによって受信された後に前記インターフェイスデータバスに提供された第二のデータセットを格納するように構成された、請求項２３の装置。
【請求項３８】
前記第一及び第二のデータセットの各々が１バイトを含む、請求項３７の装置。
【請求項３９】
前記第一及び第二のステートマシンエンジンの各々が、ランクにおけるステートマシンエンジンの一部である、請求項２３の装置。
【請求項４０】
前記ランクにおけるステートマシンエンジンの各ステートマシンエンジンが、それぞれのバイトを前記バッファインターフェイスに連続的に提供するように構成された、請求項３９の装置。
【請求項４１】
前記ランクにおけるステートマシンエンジンの各ステートマシンエンジンが、前記バッファインターフェイスに提供された前記それぞれのバイトの全てを受信するように構成された、請求項４０の装置。
【請求項４２】
前記ランクにおけるステートマシンエンジンの各ステートマシンエンジンが、前記バッファインターフェイスに提供された前記それぞれのバイトの一部を受信するように構成された、請求項４０の装置。
【請求項４３】
マスタチップにおいてデータストリームの第一の部分を受信することと、
スレーブチップにおいて前記データストリームの第二の部分を受信することと、
バッファインターフェイスを使用して前記マスタチップから前記スレーブチップに第一の信号を提供することによって、前記マスタチップと前記スレーブチップとの間のデータ転送を起動することと、
前記マスタチップから前記第一の信号を提供した後の第一の時点に、前記データストリームの前記第一の部分を前記バッファインターフェイスに提供することと、
前記第一の時点後の第二の時点に、前記データストリームの前記第二の部分を前記バッファインターフェイスに提供することと、を含む、バッファインターフェイスの動作方法。
【請求項４４】
前記バッファインターフェイスを使用して前記マスタチップから前記スレーブチップに第二の信号を提供することによって、前記マスタチップと前記スレーブチップとの間のデータ転送を停止することを含む、請求項４３の方法。
【請求項４５】
前記バッファインターフェイスを使用して前記スレーブチップから前記マスタチップに第二の信号を提供することによって、前記マスタチップと前記スレーブチップとの間のデータ転送を停止することを含む、請求項４３の方法。
【請求項４６】
前記マスタチップ及び前記スレーブチップの少なくともいずれかに、一定期間中データを解析させる命令を提供することを含む、請求項４３の方法。
【請求項４７】
命令を実行する前に前記マスタチップ及び前記スレーブチップを同期させる命令を、前記マスタチップ及び前記スレーブチップに提供することを含む、請求項４３の方法。
【請求項４８】
前記命令がデータバッファ処理命令を含む、請求項４７の方法。
【請求項４９】
プロセッサから第一のアドレスを受信することと、
第一のステートマシンエンジンにおいて、前記プロセッサから第一のデータブロックの第一の部分を受信することと、
第二のステートマシンエンジンにおいて、前記プロセッサから前記第一のデータブロックの第二の部分を受信することと、ここでは、前記第一のステートマシンエンジンが前記第一のデータブロックの前記第一の部分を受信するのとパラレルに、前記第一のデータブロックの前記第二の部分が前記第二のステートマシンエンジンにおいて受信され、
前記第一のアドレスに対応する前記第一のステートマシンエンジンの第一のメモリロケーションに前記第一のデータブロックの前記第一の部分を格納することと、
前記第一のアドレスに対応する前記第二のステートマシンエンジンの第二のメモリロケーションに前記第一のデータブロックの前記第二の部分を格納することと、
前記プロセッサから第二のアドレスを受信することと、
前記第一のステートマシンエンジンにおいて、前記プロセッサから前記第一のデータブロックの第三の部分を受信することと、
前記第二のステートマシンエンジンにおいて、前記プロセッサから前記第一のデータブロックの第四の部分を受信することと、ここでは、前記第一のステートマシンエンジンが前記第一のデータブロックの前記第三の部分を受信するのとパラレルに、前記第一のデータブロックの前記第四の部分が前記第二のステートマシンエンジンにおいて受信され、
前記第二のアドレスに対応する前記第一のステートマシンエンジンの第三のメモリロケーションに前記第一のデータブロックの前記第三の部分を格納することと、
前記第二のアドレスに対応する前記第二のステートマシンエンジンの第四のメモリロケーションに前記第一のデータブロックの前記第四の部分を格納することと、を含み、
前記第一のステートマシンエンジンが、前記第一のデータブロックの前記第一の部分を受信した直後に前記第一のデータブロックの前記第三の部分を受信し、前記第二のステートマシンエンジンが、前記第一のデータブロックの前記第二の部分を受信した直後に前記第一のデータブロックの前記第四の部分を受信し、前記第三のメモリロケーションが所定のオフセットだけ前記第一のメモリロケーションからオフセットされ、前記第四のメモリロケーションが前記所定のオフセットだけ前記第二のメモリロケーションからオフセットされた、データ格納方法。
【請求項５０】
前記第一のステートマシンエンジンのラチスを用いて前記第一のデータブロックを解析することを含む、請求項４９の方法。
【請求項５１】
前記第一のデータブロックの前記第一の部分及び前記第一のデータブロックの前記第三の部分を、前記第一のステートマシンエンジンからバッファインターフェイスに提供することと、
前記第一のデータブロックの前記第二の部分及び前記第一のデータブロックの前記第四の部分を、前記第二のステートマシンエンジンから前記バッファインターフェイスに提供することと、
前記第一のステートマシンエンジンにおいて、前記バッファインターフェイスから前記第一のデータブロックの前記第一、第二、第三及び第四の部分を受信することと、を含む、請求項４９の方法。
【請求項５２】
前記バッファインターフェイスから受信したデータのタイミングに少なくとも部分的に基づいて、前記第一のステートマシンエンジンによって、前記バッファインターフェイスから受信したデータを格納することを含む、請求項５１の方法。
【請求項５３】
前記第一のデータブロックの前記第一、第二、第三及び第四の部分が前記プロセッサから提供されたのと同じ順序で、前記第一のステートマシンエンジンにおいて、前記第一のデータブロックの前記第一、第二、第三及び第四の部分を受信することを含む、請求項５１の方法。
【請求項５４】
前記プロセッサから第三のアドレスを受信することと、
前記第一のステートマシンエンジンにおいて、前記プロセッサから第二のデータブロックの第一の部分を受信することと、
前記第二のステートマシンエンジンにおいて、前記プロセッサから前記第二のデータブロックの第二の部分を受信することと、ここでは、前記第一のステートマシンエンジンが前記第二のデータブロックの前記第一の部分を受信するのとパラレルに、前記第二のデータブロックの前記第二の部分が前記第二のステートマシンエンジンにおいて受信され、
前記第三のアドレスに対応する前記第一のステートマシンエンジンの第五のメモリロケーションに前記第二のデータブロックの前記第一の部分を格納することと、
前記第三のアドレスに対応する前記第二のステートマシンエンジンの第六のメモリロケーションに前記第二のデータブロックの前記第二の部分を格納することと、
前記プロセッサから第四のアドレスを受信することと、
前記第一のステートマシンエンジンにおいて、前記プロセッサから前記第二のデータブロックの第三の部分を受信することと、
前記第二のステートマシンエンジンにおいて、前記プロセッサから前記第二のデータブロックの第四の部分を受信することと、ここでは、前記第一のステートマシンエンジンが前記第二のデータブロックの前記第三の部分を受信するのとパラレルに、前記第二のデータブロックの前記第四の部分が前記第二のステートマシンエンジンにおいて受信され、
前記第四のアドレスに対応する前記第一のステートマシンエンジンの第七のメモリロケーションに前記第二のデータブロックの前記第三の部分を格納することと、
前記第四のアドレスに対応する前記第二のステートマシンエンジンの第八のメモリロケーションに前記第二のデータブロックの前記第四の部分を格納することと、を含み、
前記第一のステートマシンエンジンが、前記第二のデータブロックの前記第一の部分を受信した直後に前記第二のデータブロックの前記第三の部分を受信し、前記第二のステートマシンエンジンが、前記第二のデータブロックの前記第二の部分を受信した直後に前記第二のデータブロックの前記第四の部分を受信し、前記第五のメモリロケーションが前記第一のメモリロケーションから１だけオフセットされ、前記第七のメモリロケーションが前記第五のメモリロケーションから前記所定のオフセットだけオフセットされ、前記第六のメモリロケーションが前記第二のメモリロケーションから１だけオフセットされ、前記第八のメモリロケーションが前記第六のメモリロケーションから前記所定のオフセットだけオフセットされた、請求項４９の方法。
【請求項５５】
前記第二のステートマシンエンジンのラチスを用いて前記第二のデータブロックを解析することを含む、請求項５４の方法。
【請求項５６】
複数のステートマシンエンジンにおいて、前記複数のステートマシンエンジンのうちの第一のステートマシンエンジンによって解析されるべき第一のデータブロックをプロセッサから受信することと、
前記複数のステートマシンエンジンにおいて、前記複数のステートマシンエンジンのうちの第二のステートマシンエンジンによって解析されるべき第二のデータブロックを前記プロセッサから受信することと、を含み、
前記第一のデータブロックにおける有効データの長さが、前記第二のデータブロックにおける有効データの長さとは異なる、データ処理方法。
【請求項５７】
前記第一のステートマシンエンジンにおいて、前記第一のデータブロックに対応する第一の命令を前記プロセッサから受信することと、
前記第二のステートマシンエンジンにおいて、前記第二のデータブロックに対応する第二の命令を前記プロセッサから受信することと、を含む、請求項５６の方法。
【請求項５８】
前記プロセッサからの前記第一のデータブロックの受信が、前記第一のステートマシンエンジンにおいて前記第一のデータブロックの第一の部分を受信することと、前記第二のステートマシンエンジンにおいて前記第一のデータブロックの第二の部分を受信することと、を含む、請求項５７の方法。
【請求項５９】
前記プロセッサからの前記第二のデータブロックの受信が、前記第一のステートマシンエンジンにおいて前記第二のデータブロックの第一の部分を受信することと、前記第二のステートマシンエンジンにおいて前記第二のデータブロックの第二の部分を受信することと、を含む、請求項５８の方法。
【請求項６０】
前記第一のデータブロックの前記第一の部分及び前記第一のデータブロックの前記第二の部分をバッファインターフェイスに提供することと、前記第二のデータブロックの前記第一の部分及び前記第二のデータブロックの前記第二の部分を前記バッファインターフェイスに提供することと、を含む、請求項５９の方法。
【請求項６１】
前記第一の命令が前記第一のデータブロックのためのデータバイトの総数を含む、請求項６０の方法。
【請求項６２】
前記第一の命令が前記第一のデータブロックのための有効バイト数を含む、請求項６１の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の参照］
本願は、２０１３年３月１５日に出願された米国特許出願第６１／７８８，３６４号の非仮出願である。
［技術分野］
【０００２】
本発明の実施形態は、概して電子デバイスに関し、より詳細には、ある実施形態においては、データ解析のための並列デバイスを有する電子デバイスに関する。
【背景技術】
【０００３】
複雑なデータ解析（例えば、パターン認識）は、従来のフォンノイマンベースコンピュータ上で実施するために非効率的である場合がある。しかしながら、生物学的脳、特に人の脳は、複雑なデータ解析の実施に熟練している。最新の研究では、人の脳が新皮質においてヒエラルキー的に組織化された一連のニューロン層を利用してデータ解析を実施することが示唆されている。ヒエラルキーのより下層にあるニューロンが、例えば、感覚器官からの「生信号」を解析し、一方で、より上層にあるニューロンが、より低いレベルのニューロンからの信号出力を解析する。新皮質におけるこのヒエラルキーシステムは、ことによると脳の他の区域と組み合わさって、空間推論、意識的思考及び複雑な言語などの高レベル機能を人が実施することを可能にする複雑なデータ解析を達成する。
【０００４】
コンピューティングの分野においては、例えば、パターン認識タスクはますます困難なものになっている。コンピュータ間でますます大量のデータが伝送され、ユーザが検出を望むパターン数は増加している。例えば、スパムまたはマルウェアはしばしば、データストリーム内でパターン、例えば、特定の句またはコードの一部を検索することによって検出される。新規パターンが新規変形を検索するために実装され得るにつれて、パターン数は、スパム及びマルウェアの多様性とともに増加する。これらのパターンの各々に対してデータストリームを検索することは、コンピューティングボトルネックを形成する場合がある。しばしば、データストリームが受信されると、それは一度に１つずつ各パターンに対して検索される。システムがデータストリームの次の部分を検索するために準備するまでの遅延は、パターン数とともに増大する。したがって、パターン認識は、データの受領を遅延させる場合がある。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ハードウェアは、パターン用のデータストリームを検索するために設計されてきたが、このハードウェアは、しばしば、任意の期間において十分なデータ量を処理することができない。データストリームを検索するように構成された幾つかのデバイスは、複数の回路間でデータストリームを分配することによって、十分なデータ量を処理する。回路は、データストリームがパターンの一部にマッチするか否かを各々判定する。しばしば、多数の回路がパラレルに動作して、各々がほぼ同時にデータストリームを検索する。しかしながら、生物学的脳以上に効率的に複雑なデータ解析を実施することが可能なシステムは存在しなかった。そのようなシステムの開発が望ましい。
【図面の簡単な説明】
【０００６】
【図１】本発明の種々の実施形態に従う、ステートマシンエンジンを有するシステムの一実施例を図示する。
【図２】本発明の種々の実施形態に従う、図１のステートマシンエンジンの有限ステートマシン（ＦＳＭ）ラチスの一実施例を図示する。
【図３】本発明の種々の実施形態に従う、図２のＦＳＭラチスのブロックの一実施例を図示する。
【図４】本発明の種々の実施形態に従う、図３のブロックの行の一実施例を図示する。
【図５】本発明の種々の実施形態に従う、図４の行のうちの２のグループの一実施例を図示する。
【図６】本発明の種々の実施形態に従う、有限ステートマシングラフの一実施例を図示する。
【図７】本発明の種々の実施形態に従う、ＦＳＭラチスで実現された２レベルヒエラルキーの一実施例を図示する。
【図８】本発明の種々の実施形態に従う、コンパイラが図２のＦＳＭラチスのプログラミング用のバイナリファイルへとソースコードを変換するための方法の一実施例を図示する。
【図９】本発明の種々の実施形態に従う、ステートマシンエンジンを図示する。
【図１０】本発明の種々の実施形態に従う、デバイスがランクにおいて配列された複数の物理的なステートマシンエンジンの一実施例を図示する。
【図１１】本発明の種々の実施形態に従う、ステートマシンエンジンに提供されるデータブロックにグループ化されたデータセグメントの一実施例を図示する。
【図１２】本発明の種々の実施形態に従う、図１１のデータブロックのデータセグメント間に挿入されるデータパディングの一実施例を図示する。
【図１３】本発明の種々の実施形態に従う、図１２のデータブロックのデータセグメントの後ろに挿入されるデータパディングの一実施例を図示する。
【図１４】本発明の種々の実施形態に従う、ステートマシンエンジンのデータバッファシステムに伝送するように組織化された図１３のデータブロックの一実施例を図示する。
【図１５】本発明の種々の実施形態に従う、デバイスがランクにおいて配列されており、インターランク（ＩＲ）バス及びプロセスバッファインターフェイスによってともに結合された複数の物理的なステートマシンエンジンの一実施例を図示する。
【図１６】本発明の種々の実施形態に従う、複数の物理的なステートマシンエンジンに結合されたＩＲバス及びプロセスバッファインターフェイスにおける信号の一実施例を図示する。
【図１７】本発明の種々の実施形態に従う、ＩＲバス及びプロセスバッファインターフェイスにおける信号のタイミング図の一実施例を図示する
【図１８】本発明の種々の実施形態に従う、複数の論理グループに組織化された複数の物理的なステートマシンエンジンのデータバッファに格納されたデータの一実施例を図示する。
【図１９】本発明の種々の実施形態に従う、複数の論理グループに組織化された複数の物理的なステートマシンエンジンのプロセスバッファに格納されたデータの一実施例を図示する。
【図２０】本発明の種々の実施形態に従う、１つの論理グループに組織化された複数の物理的なステートマシンエンジンのデータバッファに格納されたデータの一実施例を図示する。
【図２１】本発明の種々の実施形態に従う、１つの論理グループに組織化された複数の物理的なステートマシンエンジンのプロセスバッファに格納されたデータの一実施例を図示する。
【発明を実施するための形態】
【０００７】
ここで図面を参照する。図１は、参照数字１０で概して示されるプロセッサベースシステムの実施形態を図示する。システム１０（例えば、データ解析システム）は、例えば、デスクトップコンピュータ、ラップトップコンピュータ、ページャ、携帯電話、パーソナルオーガナイザ、ポータブル音声プレイヤ、制御回路、カメラなどの様々なタイプのうちの任意のものであってもよい。システム１０は、さらに、ルータ、サーバまたは（例えば、前述のタイプのコンピュータのいずれかの）クライアントなどのネットワークノードであってもよい。システム１０は、コピー機、スキャナ、プリンタ、ゲーム機、テレビ、セットトップビデオ配信もしくは録画システム、ケーブルボックス、パーソナルデジタルメディアプレイヤ、工場オートメーションシステム、乗用車コンピュータシステム、または医療デバイスなどの、幾つかの他の種類の電子デバイスであってもよい。（本明細書中に使用される多くの他の用語と同様に、これらの種々のシステムの実施例を記述するために使用される用語は、幾つかの指示物を共有し、それゆえ、記載された他の品目があるからという理由で狭義に解釈されるべきではない。）
【０００８】
システム１０などの典型的なプロセッサベースデバイスにおいては、マイクロプロセッサなどのプロセッサ１２が、システム１０におけるシステム機能及び要求の処理を制御する。さらに、プロセッサ１２は、システム制御を共有する複数のプロセッサを備えてもよい。プロセッサ１２がシステム１０内部または外部に格納され得る命令を実行することによってシステム１０を制御するように、プロセッサ１２は、システム１０内の各々の構成要素に直接的に結合されてもよいし、間接的に結合されてもよい。
【０００９】
本明細書に記述する実施形態に従い、システム１０は、ステートマシンエンジン１４を含み、ステートマシンエンジン１４はプロセッサ１２の制御下で動作してもよい。本明細書中に使用されるようなステートマシンエンジン１４は、単一デバイス（例えば、単一チップ）を指す。ステートマシンエンジン１４は、任意のオートマトン理論を利用することができる。例えば、ステートマシンエンジン１４は、これらに限定されないが、Ｍｅａｌｙアーキテクチャ、Ｍｏｏｒｅアーキテクチャ、有限ステートマシン（ＦＳＭ）、決定論的ＦＳＭ（ＤＦＳＭ）、ビット・パラレルステートマシン（ＢＰＳＭ）などを含む多くのステートマシンアーキテクチャのうちの１つを利用することができる。様々なアーキテクチャを使用できるが、論述する目的のため、本願ではＦＳＭに言及する。しかしながら、様々なステートマシンアーキテクチャのうちの任意の１つを使用しても記述した技術を利用できることが当業者には認識されるであろう。
【００１０】
さらに下記するように、ステートマシンエンジン１４は、多数（例えば、１つ以上）の有限ステートマシン（ＦＳＭ）ラチス（例えば、ステートマシンエンジン１４のコア）を含んでもよい。この適用目的のため、「ラチス」という用語は、素子（例えば、ブールセル、カウンタセル、ステートマシン素子、状態遷移素子）の組織化されたフレームワーク（例えば、ルーティングマトリクス、ルーティングネットワーク、フレーム）を指す。さらにまた、「ラチス」は、任意の適切な形状、構造またはヒエラルキー的組織（例えば、グリッド、立方形、球状、カスケーディング接続）を有してもよい。各ＦＳＭラチスは、各々が同一のデータをパラレルに受信して解析する複数のＦＳＭを実現してもよい。さらに、ＦＳＭラチスのクラスタが同一の入力データをパラレルに解析できるように、ＦＳＭラチスは、グループ（例えば、クラスタ）で配列されてもよい。さらに、ステートマシンエンジン１４のＦＳＭラチスのクラスタをヒエラルキー構造に配列することによって、ヒエラルキー構造のより低レベルにおけるステートマシンラチスからの出力を、より高レベルにおけるステートマシンラチスに対する入力として使用してもよい。ヒエラルキー構造を通して直列にステートマシンエンジン１４のパラレルＦＳＭラチスのクラスタをカスケード接続することによって、より多くの複雑なパターンを解析（例えば、評価、検索など）できる。
【００１１】
さらに、ステートマシンエンジン１４のヒエラルキーパラレル構造に基づいて、ステートマシンエンジン１４は、高い処理速度を利用するシステムにおいて複雑なデータ解析（例えば、パターン認識）に使用することができる。例えば、本明細書に記述する実施形態は、１Ｇバイト／秒の処理速度を持つシステムに組み込むことができる。したがって、ステートマシンエンジン１４を利用することによって、高速メモリデバイスもしくは他の外部デバイスからのデータを迅速に解析することができる。ステートマシンエンジン１４は、幾つかの基準（例えば、検索語）に従ってデータストリームを、ほぼ同時に、例えば、単一のデバイスサイクル期間に解析することができる。ステートマシンエンジン１４のレベル上のＦＳＭのクラスタ内の各ＦＳＭは、ほぼ同時にデータストリームから同一の検索語を各々受信して、各パラレルＦＳＭラチスが、当該用語が処理基準における次の状態へとステートマシンエンジン１４を進めるか否かを判定してもよい。ステートマシンエンジン１４は、比較的多数の基準、例えば、１００超、１０００超または１００００超の基準に従い用語を解析してもよい。これらはパラレルに動作するため、データストリームを遅くすることなく、比較的高いバンド幅を有するデータストリーム、例えば、１Ｇバイト／秒と同等以上のデータストリームに対して基準を適用してもよい。
【００１２】
一実施形態においては、ステートマシンエンジン１４は、データストリームにおける多数のパターンを認識（例えば、検出）するように構成されてもよい。例えば、ステートマシンエンジン１４は、ユーザまたは他のエンティティが解析を望み得る様々なタイプのデータストリームのうちの１つ以上におけるパターンを検出するのに利用することができる。例えば、ステートマシンエンジン１４は、インターネット上で受信されたパケット、または携帯電話ネットワーク上で受信された音声もしくはデータなどの、ネットワーク上で受信されたデータストリームを解析するように構成できる。一実施例においては、ステートマシンエンジン１４は、スパムまたはマルウェア用のデータストリームを解析するように構成できる。データストリームは、シリアルデータストリームとして受信されてもよく、データが、時間的、単語的または意味的に重要な順序などの、意味のある順序で受信される。あるいは、データストリームは、パラレルまたは順序に関係なく受信され、その後、例えば、インターネット上で受信されたパケットを再配列することによってシリアルデータストリームに変換されてもよい。幾つかの実施形態においては、データストリームはシリアルに用語を提示することができるが、各用語を表すビットはパラレルに受信されてもよい。データストリームはシステム１０へと外部ソースから受信されてもよいし、メモリ１６などのメモリデバイスに問い合わせ、メモリ１６内に格納されたデータからデータストリームを形成することによって形成されてもよい。他の実施例においては、ステートマシンエンジン１４は、あるワードを綴る文字シーケンス、遺伝子を特定する遺伝的塩基対のシーケンス、画像の一部を形成する画像もしくはビデオファイルにおけるビットのシーケンス、プログラムの一部を形成する実行可能なファイルにおけるビットのシーケンス、または歌もしくは発話フレーズの一部を形成する音声ファイルにおけるビットのシーケンスを認識するように構成できる。解析されるべきデータストリームは、例えば、ベーステン、ＡＳＣＩＩなどのバイナリフォーマットまたは他のフォーマットにおける複数のビットのデータを含んでもよい。ストリームは、例えば、幾つかのバイナリデジットなどの単一デジットまたは複数デジットを有するデータをエンコードしてもよい。
【００１３】
認識されるように、システム１０はメモリ１６を含むことができる。メモリ１６は、例えば、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、同期式ＤＲＡＭ（ＳＤＲＡＭ）、ダブルデータレートＤＲＡＭ（ＤＤＲ  ＳＤＲＡＭ）、ＤＤＲ２  ＳＤＲＡＭ、ＤＤＲ３  ＳＤＲＡＭなどの揮発性メモリを含むことができる。メモリ１６は、揮発性メモリと組み合わせて使用するための、リードオンリーメモリ（ＲＯＭ）、ＰＣ−ＲＡＭ、シリコン・酸化物・窒化物・酸化物・シリコン（ＳＯＮＯＳ）メモリ、金属・酸化物・窒化物・酸化物・シリコン（ＭＯＮＯＳ）メモリ、ポリシリコン浮遊ゲートベースメモリ、及び／または種々のアーキテクチャの他のタイプのフラッシュメモリ（例えば、ＮＡＮＤメモリ、ＮＯＲメモリなど）などの不揮発性メモリも含むことができる。メモリ１６は、ステートマシンエンジン１４によって解析されるデータを提供できる、ＤＲＡＭデバイスなどの１つ以上のメモリデバイスを含むことができる。本明細書中に使用されるような「提供」という用語は、総称的に、導き、入力、挿入、送信、転送、伝送、生成、付与、出力、配置、書き込みなどを指す。当該デバイスは、ソリッドステートドライブ（ＳＳＤ）、マルチメディアメディアカード（ＭＭＣ）、セキュアデジタル（ＳＤ）カード、コンパクトフラッシュ（ＣＦ）カード、または任意の他の適切なデバイスと称されるか、またはそれらを含んでもよい。さらに、当該デバイスはユニバーサルシリアルバス（ＵＳＢ）、ペリフェラルコンポーネントインターコネクト（ＰＣＩ）、ＰＣＩエクスプレス（ＰＣＩ−Ｅ）、スモールコンピュータシステムインターフェイス（ＳＣＳＩ）、ＩＥＥＥ１３９４（ファイアワイヤ）、または任意の他の適切なインターフェイスなどの任意の適切なインターフェイスを通してシステム１０に結合できることが認識されるはずである。フラッシュメモリデバイスなどのメモリ１６の動作を容易にするために、システム１０は、メモリコントローラ（図示せず）を含むことができる。認識されるように、メモリコントローラは、独立したデバイスであってもよいし、プロセッサ１２と一体であってもよい。さらに、システム１０は、磁気記憶デバイスなどの外部ストレージ１８を含むことができる。外部ストレージは、ステートマシンエンジン１４に入力データを提供することもできる。
【００１４】
システム１０は、多数のさらなる構成要素を含んでもよい。例えば、コンパイラ２０を、図８に関してより詳細に記述するように、ステートマシンエンジン１４を構成（例えば、プログラム）するのに使用してもよい。ユーザがデータをシステム１０に入力できる入力デバイス２２も、プロセッサ１２に結合することができる。例えば、入力デバイス２２を使用して、ステートマシンエンジン１４によるその後の解析のためにメモリ１６にデータを入力することができる。入力デバイス２２は、例えば、ボタン、スイッチング素子、キーボード、ライトペン、スタイラス、マウス及び／または音声認識システムを含むことができる。ディスプレイなどの出力デバイス２４も、プロセッサ１２に結合することができる。ディスプレイ２４は、例えば、ＬＣＤ、ＣＲＴ、ＬＥＤ及び／または音声ディスプレイを含むことができる。システムは、インターネットなどのネットワークとインターフェイスを介して接続するために、ネットワークインターフェイスカード（ＮＩＣ）などのネットワークインターフェイスデバイス２６も含むことができる。認識されるように、システム１０は、システム１０の用途に応じて、多数の他のコンポーネントを含むことができる。
【００１５】
図２〜図５は、ＦＳＭラチス３０の一実施例を図示する。一実施例においては、ＦＳＭラチス３０は、ブロック３２のアレイを備える。記述するように、各ブロック３２は、ＦＳＭにおける複数の状態に対応する複数の選択的に結合可能なハードウェア素子（例えば、コンフィギュラブル素子及び／または専用素子）を含むことができる。ＦＳＭにおける状態に類似して、ハードウェア素子は、入力ストリームを解析して、入力ストリームに基づいて下流ハードウェア素子をアクティブ化することができる。
【００１６】
コンフィギュラブル素子は、多くの異なる機能を実施するように構成（例えば、プログラム）することができる。例えば、コンフィギュラブル素子は、（図３及び図４に示すような）行３８及び（図２及び図３に示すような）ブロック３２にヒエラルキー的に組織化された（図５に示す）ステートマシン素子（ＳＭＥ）３４、３６を含むことができる。ＳＭＥも、状態遷移素子（ＳＴＥ）とみなすことができる。ヒエラルキー的に組織化されたＳＭＥ３４、３６の間で信号をルーティングするために、ブロック間スイッチング素子４０（図２及び図３に示す）、ブロック内スイッチング素子４２（図３及び図４に示す）、及び行内スイッチング素子４４（図４に示す）を含むプログラマブルスイッチング素子のヒエラルキーを使用することができる。
【００１７】
下記するように、スイッチング素子は、ルーティング構造及びバッファを含むことができる。ＳＭＥ３４、３６は、ＦＳＭラチス３０によって実現されるＦＳＭの状態に対応することができる。ＳＭＥ３４、３６は、下記するようなプログラマブルスイッチング素子を使用することによってともに結合することができる。したがって、状態の機能に対応するようにＳＭＥ３４、３６を構成し、かつＦＳＭにおける状態間の遷移に対応するようにＳＭＥ３４、３６をともに選択的に結合することによって、ＦＳＭをＦＳＭラチス３０において実現することができる。
【００１８】
図２は、ＦＳＭラチス３０の一実施例の全体図を図示する。ＦＳＭラチス３０は、プログラマブルブロック間スイッチング素子４０とともに選択的に結合することができる複数のブロック３２を含む。ブロック間スイッチング素子４０は、導体４６（例えば、ワイヤ、トレースなど）並びにバッファ４８及び５０を含むことができる。一実施例においては、バッファ４８及び５０は、ブロック間スイッチング素子４０とやり取りする信号の接続及びタイミングを制御するために含まれる。さらに下記するように、バッファ４８は、ブロック３２間で送信されるデータをバッファするために提供され、一方で、バッファ５０は、ブロック間スイッチング素子４０間で送信されるデータをバッファするために提供することができる。さらに、ブロック３２は、信号（例えば、データ）を受信し、ブロック３２にデータを提供するための入力ブロック５２（例えば、データ入力ポート）に選択的に結合することができる。ブロック３２は、ブロック３２からの信号を外部デバイス（例えば、別のＦＳＭラチス３０）に提供するための出力ブロック５４（例えば、出力ポート）にも選択的に結合することができる。ＦＳＭラチス３０は、ＦＳＭラチス３０を構成（例えば、画像を通じたプログラム）するためのプログラミングインターフェイス５６も含むことができる。画像は、ＳＭＥ３４、３６の状態を構成（例えば、設定）することができる。すなわち、画像は、入力ブロック５２において与えられた入力に、ある方法で反応するようにＳＭＥ３４、３６を構成することができる。例えば、ＳＭＥ３４、３６は、文字「ａ」が入力ブロック５２で受信されたときに、ハイ信号を出力するように設定できる。
【００１９】
一実施例においては、入力ブロック５２、出力ブロック５４及び／またはプログラミングインターフェイス５６は、レジスタとして実現することができ、レジスタへの書き込みまたはレジスタからの読み出しによってそれぞれの素子にまたはそれらからデータを提供する。したがって、プログラミングインターフェイス５６に対応するレジスタに格納された画像からのビットは、ＳＭＥ３４、３６上でロードすることができる。図２は、ブロック３２、入力ブロック５２、出力ブロック５４及びブロック間スイッチング素子４０間にある数の導体（例えば、ワイヤ、トレース）を図示しているが、他の実施例においては、より少ないまたは多い数の導体を使用できることが理解されるはずである。
【００２０】
図３は、ブロック３２の一実施例を図示する。ブロック３２は、プログラマブルブロック内スイッチング素子４２にともに選択的に結合することができる複数の行３８を含むことができる。さらに、行３８は、ブロック間スイッチング素子４０によって、別のブロック３２内の別の行３８に選択的に結合することができる。行３８は、２のグループ（ＧＯＴ）６０として本明細書に参照される素子の対に組織化された複数のＳＭＥ３４、３６を含む。一実施例においては、ブロック３２は、１６個（１６）の行３８を含む。
【００２１】
図４は、行３８の一実施例を図示する。ＧＯＴ６０は、プログラマブル行内スイッチング素子４４によって、行３８内の他のＧＯＴ６０及び任意の他の素子（例えば、専用素子５８）に選択的に結合することができる。ＧＯＴ６０は、ブロック内スイッチング素子４２によって他の行３８における他のＧＯＴ６０、またはブロック間スイッチング素子４０によって他のブロック３２における他のＧＯＴ６０にも結合することができる。一実施例においては、ＧＯＴ６０は、第一の入力６２、第二の入力６４及び出力６６を有する。図５を参照してさらに図示するように、第一の入力６２は、ＧＯＴ６０の第一のＳＭＥ３４に結合され、第二の入力６４は、ＧＯＴ６０の第二のＳＭＥ３６に結合される。
【００２２】
一実施例においては、行３８は、第一及び第二の複数の行相互接続導体６８、７０を含む。一実施例においては、ＧＯＴ６０の入力６２、６４は、１つ以上の行相互接続導体６８、７０に結合し、出力６６も、１つ以上の行相互接続導体６８、７０に結合することができる。一実施例においては、第一の複数の行相互接続導体６８は、行３８内の各ＧＯＴ６０の各ＳＭＥ３４、３６に結合することができる。第二の複数の行相互接続導体７０は、行３８内の各ＧＯＴ６０のうちの唯一つのＳＭＥ３４、３６に結合することができるが、ＧＯＴ６０の他のＳＭＥ３４、３６には結合することができない。一実施例においては、図５によりよく図示するように、第二の複数の行相互接続導体７０のうちの第一の半分が、行３８内のＳＭＥ３４、３６のうちの第一の半分（各ＧＯＴ６０からの一方のＳＭＥ３４）に結合することができ、第二の複数の行相互接続導体７０のうちの第二の半分が、行３８内のＳＭＥ３４、３６のうちの第二の半分（各ＧＯＴ６０からの他方のＳＭＥ３４、３６）に結合することができる。第二の複数の行相互接続導体７０とＳＭＥ３４、３６との間の限定された接続は、本明細書においては、「パリティ」と称される。一実施例においては、行３８は、カウンタ、プログラマブルブール型論理素子、ルックアップテーブル、ＲＡＭ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、プログラマブルプロセッサ（例えば、マイクロプロセッサ）、または専用機能を実施するための他の素子などの専用素子５８も含むことができる。
【００２３】
一実施例においては、専用素子５８は、（本明細書においては、カウンタ５８とも称される）カウンタを含む。一実施例においては、カウンタ５８は１２ビットプログラマブルダウンカウンタを含む。１２ビットプログラマブルカウンタ５８は、カウンティング入力、リセット入力及びゼロカウント出力を有する。カウンティング入力は、アサートされると、１ずつカウンタ５８の値をデクリメントする。リセット入力は、アサートされると、関連するレジスタからの初期値をカウンタ５８にロードさせる。１２ビットカウンタ５８に対して、１２ビットの数までを初期値としてロードすることができる。カウンタ５８の値がゼロ（０）までデクリメントされると、ゼロカウント出力がアサートされる。カウンタ５８は、また、少なくとも２つのモードであるパルス及びホールドも有する。カウンタ５８がパルスモードに設定されると、カウンタ５８がゼロ及びクロックサイクルに達したときにゼロカウント出力がアサートされる。カウンタ５８の次のクロックサイクル中に、ゼロカウント出力がアサートされる。その結果、カウンタ５８は、時間内にクロックサイクルからオフセットされる。次のクロックサイクルにおいて、ゼロカウント出力はもはやアサートされない。カウンタ５８がホールドモードに設定されると、カウンタ５８がゼロにデクリメントするとき、クロックサイクル中にゼロカウント出力がアサートされ、アサートされたリセット入力によってカウンタ５８がリセットされるまでアサートされたままである。
【００２４】
別の実施例においては、専用素子５８は、ブール論理を含む。例えば、このブール論理は、ＡＮＤ、ＯＲ、ＮＡＮＤ、ＮＯＲ、積和（ＳｏＰ）、積和の否定出力（ＮＳｏＰ）、和積の否定出力（ＮＰｏＳ）、及び和積（ＰｏＳ）関数などの論理関数を実行するのに使用してもよい。このブール論理を使用して、ＦＳＭラチス３０における（本明細書中に後に論じるような、ＦＳＭの端末ノードに対応する）端末状態ＳＭＥからのデータを抽出できる。抽出されたデータを使用して、状態データを他のＦＳＭラチス３０に提供する、及び／またはＦＳＭラチス３０の再構成もしくは別のＦＳＭラチス３０の再構成に使用される構成データを提供することができる。
【００２５】
図５は、ＧＯＴ６０の一実施例を図示する。ＧＯＴ６０は、入力６２、６４並びにＯＲゲート７６及び３：１マルチプレクサ７８に結合されたそれらの出力７２、７４を有する第一のＳＭＥ３４及び第二のＳＭＥ３６を含む。３：１マルチプレクサ７８は、第一のＳＭＥ３４、第二のＳＭＥ３６、またはＯＲゲート７６のいずれかにＧＯＴ６０の出力６６を結合するように設定することができる。ＯＲゲート７６を使用して、ＧＯＴ６０の共通出力６６を形成するために双方の出力７２、７４をともに結合することができる。一実施例においては、第一及び第二のＳＭＥ３４、３６が前述のようにパリティを示し、第一のＳＭＥ３４の入力６２は行相互接続導体６８の幾つかに結合することができ、第二のＳＭＥ３６の入力６４が他の行相互接続導体７０に結合できるによって、パリティ問題を克服できる共通出力６６を生成することができる。一実施例においては、ＧＯＴ６０内の２つのＳＭＥ３４、３６は、カスケード接続されるか、かつ／またはスイッチング素子７９のいずれかもしくは双方を設定することによってそれ自身にループバックさせることができる。ＳＭＥ３４、３６の出力７２、７４を他のＳＭＥ３４、３６の入力６２、６４に結合することによって、ＳＭＥ３４、３６をカスケード接続することができる。出力７２、７４をそれら自身の入力６２、６４に結合することによって、ＳＭＥ３４、３６をそれ自身にループバックさせることができる。したがって、第一のＳＭＥ３４の出力７２は、第一のＳＭＥ３４の入力６２及び第二のＳＭＥ３６の入力６４のいずれにも結合しないか、またはいずれかもしくは双方に結合させることができる。
【００２６】
一実施例においては、ステートマシン素子３４、３６は、検出ライン８２にパラレルに結合された、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）でしばしば使用されるような複数のメモリセル８０を備える。当該メモリセル８０のうちの１つは、ハイまたはロウの値（例えば、１または０）のいずれかに対応するようなデータ状態に設定することができるメモリセルを含む。メモリセル８０の出力は、検出ライン８２に結合し、メモリセル８０の入力は、データストリームライン８４上のデータに基づいて信号を受信する。一実施例においては、入力ブロック５２における入力は、メモリセル８０のうちの１つ以上を選択するようにデコードされる。選択されたメモリセル８０は、検出ライン８２上の出力としてその格納されたデータ状態を提供する。例えば、入力ブロック５２で受信されたデータは、デコーダ（図示せず）に提供でき、デコーダは、データストリームライン８４のうちの１つ以上を選択できる。一実施例においては、デコーダは、２５６本のデータストリームライン８４のうちの対応する１本へと、８ビットＡＣＳＩＩ文字を変換することができる。
【００２７】
メモリセル８０は、したがって、メモリセル８０がハイ値に設定されると検出ライン８２にハイ信号を出力し、そしてデータストリームライン８４上のデータがメモリセル８０を選択する。データストリームライン８４上のデータがメモリセル８０を選択し、メモリセル８０がロウ値へと設定されるとき、メモリセル８０は、検出ライン８２にロウ信号を出力する。検出ライン８２上のメモリセル８０からの出力は、検出セル８６によって検知される。
【００２８】
一実施例においては、入力ライン６２、６４上の信号は、アクティブまたは非アクティブ状態のいずれかにそれぞれの検出セル８６を設定する。非アクティブ状態に設定されると、検出セル８６は、それぞれの検出ライン８２上の信号にかかわらず、それぞれの出力７２、７４にロウ信号を出力する。アクティブ状態に設定されると、検出セル８６は、ハイ信号がそれぞれのＳＭＥ３４、３６のメモリセル８２のうちの１つから検出されたときに、それぞれの出力ライン７２、７４にハイ信号を出力する。アクティブ状態においては、それぞれのＳＭＥ３４、３６のメモリセル８２の全てからの信号がロウであるとき、検出セル８６は、それぞれの出力ライン７２、７４上にロウ信号を出力する。
【００２９】
一実施例においては、ＳＭＥ３４、３６は、２５６個のメモリセル８０を含み、各メモリセル８０は、異なるデータストリームライン８４に結合される。したがって、ＳＭＥ３４、３６は、データストリームライン８４の選択された１つ以上がその上にハイ信号を有するときにハイ信号を出力するようにプログラムすることができる。例えば、ＳＭＥ３４は、一番目のメモリセル８０（例えば、ビット０）をハイに設定し、全ての他のメモリセル８０（例えば、ビット１〜２５５）をロウに設定することができる。それぞれの検出セル８６がアクティブ状態にあるとき、ビット０に対応するデータストリームライン８４がその上にハイ信号を有すると、ＳＭＥ３４は、出力７２上にハイ信号を出力する。他の実施例においては、複数のデータストリームライン８４のうちの１つが、適切なメモリセル８０をハイ値に設定することによってその上にハイ信号を有すると、ＳＭＥ３４は、ハイ信号を出力するように設定することができる。
【００３０】
一実施例においては、メモリセル８０は、関連するレジスタからのビットを読み出すことによって、ハイ値またはロウ値に設定することができる。したがって、ＳＭＥ３４は、コンパイラ２０によって生成された画像をレジスタに格納して、レジスタ内のビットを関連するメモリセル８０にロードすることによって構成することができる。一実施例においては、コンパイラ２０によって生成された画像は、ハイ及びロウ（例えば、１及び０）ビットのバイナリ画像を含む。画像は、ＳＭＥ３４、３６をカスケード接続することによって、ＦＳＭとして動作させるようにＦＳＭラチス３０を構成することができる。例えば、検出セル８６をアクティブ状態に設定することによって、第一のＳＭＥ３４をアクティブ状態に設定することができる。第一のＳＭＥ３４は、ビット０に対応するデータストリームライン８４がその上にハイ信号を有するとき、ハイ信号を出力するように設定することができる。第二のＳＭＥ３６は、最初に非アクティブ状態に設定することができるが、アクティブ状態時に、ビット１に対応するデータストリームライン８４がその上にハイ信号を有するときにハイ信号を出力するように設定することができる。第一のＳＭＥ３４及び第二のＳＭＥ３６は、第一のＳＭＥ３４の出力７２を第二のＳＭＥ３６の入力６４に結合するように設定することによって、カスケード接続することができる。したがって、ビット０に対応するデータストリームライン８４上にハイ信号が検知されると、第一のＳＭＥ３４は、出力７２上にハイ信号を出力して、第二のＳＭＥ３６の検出セル８６をアクティブ状態に設定する。ビット１に対応するデータストリームライン８４上にハイ信号が検知されると、第二のＳＭＥ３６は、別のＳＭＥ３６をアクティブ化するために、またはＦＳＭラチス３０からの出力用に、出力７４上にハイ信号を出力する。
【００３１】
一実施例においては、単一のＦＳＭラチス３０は、単一の物理デバイス上に実現されるが、他の実施例においては、２つ以上のＦＳＭラチス３０を単一の物理デバイス（例えば、物理チップ）上に実現してもよい。一実施例においては、各ＦＳＭラチス３０は、別個のデータ入力ブロック５２、別個の出力ブロック５４、別個のプログラミングインターフェイス５６、及び別個のコンフィギュラブル素子の組を含むことができる。さらに、コンフィギュラブル素子の各組は、それらの対応するデータ入力ブロック５２におけるデータに対して反応（例えば、ハイまたはロウ信号を出力）することができる。例えば、第一のＦＳＭラチス３０に対応する第一の組のコンフィギュラブル素子は、第一のＦＳＭラチス３０に対応する第一のデータ入力ブロック５２におけるデータに対して反応することができる。第二のＦＳＭラチス３０に対応する第二の組のコンフィギュラブル素子は、第二のＦＳＭラチス３０に対応する第二のデータ入力ブロック５２に対して反応することができる。したがって、各ＦＳＭラチス３０は、一組のコンフィギュラブル素子を含み、異なる組のコンフィギュラブル素子は、異なる入力データに対して反応することができる。同様に、各ＦＳＭラチス３０及び各対応する組のコンフィギュラブル素子は、個別出力を提供することができる。幾つかの実施例においては、第一のＦＳＭラチス３０からの出力ブロック５４は、第二のＦＳＭラチス３０の入力ブロック５２に結合することができ、この構成により第二のＦＳＭラチス３０用の入力データが、一連のＦＳＭラチス３０のヒエラルキー配列における第一のＦＳＭラチス３０からの出力データを含むことができる。
【００３２】
一実施例においては、ＦＳＭラチス３０上にロードするための画像は、ＦＳＭラチス３０におけるコンフィギュラブル素子、プログラマブルスイッチング素子及び専用素子の構成用の複数ビットのデータを含む。一実施例においては、画像は、ある入力に基づいて所望の出力を提供するＦＳＭラチス３０を構成するように、ＦＳＭラチス３０上にロードすることができる。出力ブロック５４は、データ入力ブロック５２におけるデータに対して、コンフィギュラブル素子の反応に基づいて、ＦＳＭラチス３０からの出力を提供することができる。出力ブロック５４からの出力は、任意のパターンとのマッチを示す単一ビット、複数のパターンとのマッチ及び不一致を示す複数ビットを含む語、並びに任意の瞬間における全てまたはあるコンフィギュラブル素子の状態に対応する状態ベクトルを含むことができる。記述するように、パターン認識（例えば、音声認識、画像認識など）、信号処理、画像処理、コンピュータビジョン、クリプトグラフィーなどのデータ解析を実施するために、多数のＦＳＭラチス３０をステートマシンエンジン１４などのステートマシンエンジン内に含ませてもよい。
【００３３】
図６は、ＦＳＭラチス３０によって実現できる有限ステートマシン（ＦＳＭ）の一実施例のモデルを図示する。ＦＳＭラチス３０は、ＦＳＭの物理的実装として構成（例えば、プログラム）することができる。ＦＳＭは、１つ以上のルートノード９２を含有する図形９０（例えば、有向グラフ、無向グラフ、擬グラフ）として表すことができる。ルートノード９２に加えて、ＦＳＭは、幾つかの標準ノード９４と、１つ以上の辺９８を通してルートノード９２及び他の標準ノード９４に接続される端末ノード９６からなることができる。ノード９２、９４、９６は、ＦＳＭにおける状態に対応する。辺９８は、状態間の遷移に対応する。
【００３４】
各ノード９２、９４、９６は、アクティブ状態であってもよいし、非アクティブ状態であってもよい。非アクティブ状態にあるとき、ノード９２、９４、９６は入力データに対して反応（例えば、応答）しない。アクティブ状態にあるとき、ノード９２、９４、９６は入力データに対して反応することができる。上流ノード９２、９４は、上流ノード９２、９４と下流ノード９４、９６との間の辺９８によって特定される基準に入力データがマッチするときに、そのノードから下流にあるノード９４、９６をアクティブ化することによって入力データに対して反応することができる。例えば、第一のノード９４がアクティブであり、かつ文字「ｂ」が入力データとして受信されるとき、文字「ｂ」を特定する第一のノード９４は、辺９８によって第一のノード９４に接続された第二のノード９４をアクティブ化する。本明細書中に使用される「上流」は、１つ以上のノード間の関係を指し、他の１つ以上のノードの上流（または、ループもしくはフィードバック構成の場合には、それ自身の上流）である第一のノードとは、その第一のノードが他の１つ以上のノードをアクティブ化できる（または、ループの場合にはそれ自身をアクティブ化できる）状況を指す。同様に、「下流」とは、他の１つ以上のノードの下流（または、ループの場合にはそれ自身の下流）にある第一のノードが他の１つ以上のノードによってアクティブ化できる（または、ループの場合にはそれ自身によってアクティブ化できる）関係を指す。したがって、「上流」及び「下流」という用語は、本明細書中においては、１つ以上のノード間の関係を指すために使用されるが、これらの用語は、ループまたはノード間の他の非線形経路の使用を排除することはない。
【００３５】
図形９０においては、ルートノード９２は、最初にアクティブ化することができ、入力データがルートノード９２からの辺９８とマッチするとき、下流ノード９４をアクティブ化することができる。ノード９４は、ノード９４からの辺９８に入力データがマッチするとき、ノード９６をアクティブ化することができる。図形９０中のノード９４、９６は、入力データが受信されると、この方法でアクティブ化することができる。端末ノード９６は、入力データ内の興味あるシーケンスのマッチに対応する。したがって、端末ノード９６のアクティブ化は、入力データとして、興味あるシーケンスが受信されたことを示す。パターン認識機能を実現するＦＳＭラチス３０の状況においては、端末ノード９６への到着が、興味ある特定のパターンが入力データにおいて検出されたことを示すことができる。
【００３６】
一実施例においては、各ルートノード９２、標準ノード９４及び端末ノード９６は、ＦＳＭラチス３０におけるコンフィギュラブル素子に対応することができる。各辺９８は、コンフィギュラブル素子間の接続に対応することができる。したがって、別の標準ノード９４または端末ノード９６に遷移する（例えば、それらに接続する辺９８を有する）標準ノード９４は、別のコンフィギュラブル素子に遷移する（例えば、それに出力を提供する）コンフィギュラブル素子に対応する。幾つかの実施例においては、ルートノード９２は、対応するコンフィギュラブル素子を有さない。
【００３７】
認識されるように、ノード９２をルートノードとして記述し、ノード９６を端末ノードとして記述したが、必ずしも特定の「開始」またはルートノードが存在しなくてもよく、必ずしも特定の「終了」または出力ノードが存在しなくてもよい。換言すると、任意のノードを開始点にし、任意のノードが出力を提供してもよい。
【００３８】
ＦＳＭラチス３０がプログラムされると、各コンフィギュラブル素子は、アクティブ状態であってもよいし、非アクティブ状態であってもよい。任意のコンフィギュラブル素子は、非アクティブなとき、対応するデータ入力ブロック５２において入力データに対して反応しない。アクティブなコンフィギュラブル素子は、データ入力ブロック５２において入力データに対して反応することができ、入力データがコンフィギュラブル素子の設定にマッチするとき、下流コンフィギュラブル素子をアクティブ化することができる。コンフィギュラブル素子が端末ノード９６に対応するとき、コンフィギュラブル素子は、外部デバイスにマッチの指示を提供するために、出力ブロック５４に結合することができる。
【００３９】
プログラミングインターフェイス５６を介してＦＳＭラチス３０上にロードされた画像は、コンフィギュラブル素子と専用素子との間の接続と同様、コンフィギュラブル素子及び専用素子を構成することができ、データ入力ブロック５２におけるデータに対する反応に基づいて、連続的なノードのアクティブ化を通して所望のＦＳＭが実現される。一実施例においては、コンフィギュラブル素子は、単一のデータサイクル（例えば、単一の文字、一組の文字、単一のクロックサイクル）中にアクティブなままであり、その後、上流コンフィギュラブル素子によって再アクティブ化されるまでは非アクティブとなる。
【００４０】
端末ノード９６は、過去のイベントの圧縮されたヒストリを格納すると考慮できる。例えば、端末ノード９６に到達することを必要とされる１つ以上のパターンの入力データを、その端末ノード９６のアクティブ化によって表すことができる。一実施例においては、端末ノード９６によって提供される出力はバイナリであって、つまり、その出力は、興味あるパターンがマッチしたか否かを示す。図形９０における標準ノード９４に対する端末ノード９６の割合は、非常に小さくてもよい。換言すると、ＦＳＭには高い複雑性が存在することがあるが、ＦＳＭの出力は、比較的に小さく成り得る。
【００４１】
一実施例においては、ＦＳＭラチス３０の出力は、状態ベクトルを含むことができる。状態ベクトルは、ＦＳＭラチス３０のコンフィギュラブル素子の状態（例えば、アクティブ化されているか否か）を含む。別の実施例においては、コンフィギュラブル素子が端末ノード９６に対応するか否かにかかわらず、状態ベクトルは、コンフィギュラブル素子の全てまたはサブセットの状態を含むことができる。一実施例においては、状態ベクトルは、端末ノード９６に対応するコンフィギュラブル素子の状態を含む。したがって、出力は、図形９０の全端末ノード９６によって提供される指示の集合を含むことができる。状態ベクトルは、単語として表すことができ、各端末ノード９６によって提供されるバイナリ指示は一ビットの単語を含む。端末ノード９６のこのエンコードは、ＦＳＭラチス３０に対する検出状態の有効な指示（例えば、興味あるシーケンスが検出されたか否か、検出された興味あるシーケンスは何か）を提供することができる。
【００４２】
前述のように、ＦＳＭラチス３０は、パターン認識機能を実現するようにプログラムすることができる。例えば、ＦＳＭラチス３０は入力データにおける１つ以上のデータシーケンス（例えば、署名、パターン）を認識するように構成できる。興味あるデータシーケンスがＦＳＭラチス３０によって認識されると、当該認識の指示を出力ブロック５４において提供することができる。一実施例においては、パターン認識は、シンボルのストリング（例えば、ＡＳＣＩＩ文字）を、例えば、ネットワークデータにおけるマルウェアまたは他のデータを識別するために認識することができる。
【００４３】
図７は、ヒエラルキー構造１００の一実施例を図示し、ここでは、ＦＳＭラチス３０の二レベルが直列に結合され、データを解析するために使用される。つまり、図示する実施形態においては、ヒエラルキー構造１００は、直列に配列された第一のＦＳＭラチス３０Ａ及び第二のＦＳＭラチス３０Ｂを含む。各ＦＳＭラチス３０は、データ入力を受信するためのそれぞれのデータ入力ブロック５２、構成信号を受信するためのプログラミングインターフェイスブロック５６、及び出力ブロック５４を含む。
【００４４】
第一のＦＳＭラチス３０Ａは、データ入力ブロックにおいて、生データなどの入力データを受信するように構成される。第一のＦＳＭラチス３０Ａは、前述のように入力データに対して反応して、出力ブロックにおいて出力を提供する。第一のＦＳＭラチス３０Ａからの出力は、第二のＦＳＭラチス３０Ｂのデータ入力ブロックに送信される。第二のＦＳＭラチス３０Ｂは、その後、第一のＦＳＭラチス３０Ａによって提供された出力に基づいて反応して、ヒエラルキー構造１００の対応する出力信号１０２を提供することができる。直列の２つのＦＳＭラチス３０Ａ及び３０Ｂのこのヒエラルキー結合は、第一のＦＳＭラチス３０Ａから第二のＦＳＭラチス３０Ｂに圧縮された単語における過去のイベントに関するデータを提供するための手段を提供する。提供されたデータは、事実上、第一のＦＳＭラチス３０Ａによって記録された複雑なイベント（例えば、興味あるシーケンス）の要約であり得る。
【００４５】
図７に示すＦＳＭラチス３０Ａ、３０Ｂの２レベルヒエラルキー１００は、２つの独立したプログラムを同一のデータストリームに基づいて動作させることができる。二段階ヒエラルキーは、異なる領域としてモデル化された生物学的脳における視認と同様であり得る。このモデルの下で、領域は、有効に異なるパターン認識エンジンであり、各々が類似する計算機能（パターンマッチング）を実施するが、異なるプログラム（署名）を利用する。複数のＦＳＭラチス３０Ａ、３０Ｂをともに接続することによって、データストリーム入力についてのより多い知識が得られることがある。
【００４６】
（第一のＦＳＭラチス３０Ａによって実現される）ヒエラルキーの第一のレベルは、例えば、生データストリームにおいて直接的に処理を実施することができる。すなわち、生データストリームを第一のＦＳＭラチス３０Ａの入力ブロック５２で受信することができ、第一のＦＳＭラチス３０Ａのコンフィギュラブル素子が、生データストリームに反応することができる。（第二のＦＳＭラチス３０Ｂによって実現される）ヒエラルキーの第二のレベルは、第一のレベルからの出力を処理することができる。すなわち、第二のＦＳＭラチス３０Ｂは、第一のＦＳＭラチス３０Ａの出力ブロック５４からの出力を、第二のＦＳＭラチス３０Ｂの入力ブロック５２で受信し、第二のＦＳＭラチス３０Ｂのコンフィギュラブル素子が、第一のＦＳＭラチス３０Ａの出力に対して反応することができる。したがって、この実施例においては、第二のＦＳＭラチス３０Ｂは、入力として生データストリームは受信しないが、その代りに、第一のＦＳＭラチス３０Ａによって判定された、生データストリームとマッチする興味あるパターンの指示を受信する。第二のＦＳＭラチス３０Ｂは、第一のＦＳＭラチス３０Ａからの出力データストリームにおけるパターンを認識するＦＳＭを実現することができる。第二のＦＳＭラチス３０Ｂが、ＦＳＭラチス３０Ａからの出力を受信することに加えて、複数の他のＦＳＭラチスからの入力も受信できることが認識されるはずである。同じように、第二のＦＳＭラチス３０Ｂは、他のデバイスからの入力を受信できる。第二のＦＳＭラチス３０Ｂは、これらの複数の入力を組み合わせて出力を生成することができる。
【００４７】
図８は、コンパイラがＦＳＭを実現するためのラチス３０などのＦＳＭラチスを構成するために使用される画像にソースコードを変換するための方法１１０の一実施例を図示する。方法１１０は、ソースコードをシンタックスツリーに解析すること（ブロック１１２）と、シンタックスツリーをオートマトンに変換すること（ブロック１１４）と、オートマトンを最適化すること（ブロック１１６）と、オートマトンをネットリストに変換すること（ブロック１１８）と、ハードウェア上にネットリストを配置すること（ブロック１２０）と、ネットリストをルーティングすること（ブロック１２２）と、結果生じた画像を発行すること（ブロック１２４）と、を含む。
【００４８】
一実施例においては、コンパイラ２０は、ＦＳＭラチス３０上のＦＳＭを実現するための、ソフトウェア開発者が画像を生成することを可能にするアプリケーションプログラミングインターフェス（ＡＰＩ）を含む。コンパイラ２０は、ＦＳＭラチス３０を構成するように構成された画像にソースコードにおける正規表現の入力セットを変換するための方法を提供する。コンパイラ２０は、フォンノイマンアーキテクチャを有するコンピュータ用の命令によって実現することができる。これらの命令は、コンパイラ２０の機能をコンピュータ上のプロセッサ１２に実現させることができる。例えば、命令は、プロセッサ１２によって実行されると、プロセッサ１２に対してアクセス可能なソースコード上のブロック１１２、１１４、１１６、１１８、１２０、１２２及び１２４に記述された動作をプロセッサ１２に実施させることができる。
【００４９】
一実施例においては、ソースコードは、シンボルのグループ内のシンボルのパターンを識別するための検索ストリングを記述する。検索ストリングを記述するために、ソースコードは複数の正規表現（ｒｅｇｅｘ）を含むことができる。Ｒｅｇｅｘは、シンボル検索パターンを記述するためのストリングであってもよい。Ｒｅｇｅｘは、プログラミング言語、テキストエディタ、ネットワークセキュリティなど、種々のコンピュータドメインで広く使用されている。一実施例においては、コンパイラによってサポートされる正規表現は、非構造化データの解析用の基準を含む。非構造化データは、フリーフォームであるデータを含むことができ、データ内の単語に対して適用される索引付けを有さない。単語は、データ内の印刷可能及び印字不能な任意の組み合わせのバイトを含むことができる。一実施例においては、コンパイラは、Ｐｅｒｌ（例えば、Ｐｅｒｌ互換正規表現（ＰＣＲＥ））、ＰＨＰ、Ｊａｖａ、及びＮＥＴ言語を含むｒｅｇｅｘを実現するための複数の異なるソースコード言語をサポートすることができる。
【００５０】
ブロック１１２において、コンパイラ２０は、相関的に接続されたオペレータの配列を形成するためにソースコードを解析することができ、異なるタイプのオペレータはソースコードによって実現される異なる機能（例えば、ソースコード内のｒｅｇｅｘによって実現される異なる機能）に対応する。ソースコードの解析によって、ソースコードのジェネリック表現を生成できる。一実施例においては、ジェネリック表現は、シンタックスツリーとして知られるツリーグラフの形式のソースコードにおけるｒｅｇｅｘのエンコードされた表現を含む。本明細書に記述する実施例は、（「抽象シンタックスツリー」としても知られる）シンタックスツリーとしての配列を参照する。しかしながら、他の実施例においては、具象シンタックスツリーまたは他の配列を使用することができる。
【００５１】
前述のように、コンパイラ２０は複数のソースコード言語をサポートできるため、言語にかかわらず、解析によって、非言語の特定の表現、例えば、シンタックスツリーへとソースコードを変換する。したがって、コンパイラ２０によるさらなる処理（ブロック１１４、１１６、１１８、１２０）は、ソースコードの言語にかかわらず、共通の入力構造から動作することができる。
【００５２】
前述のように、シンタックスツリーは、相関的に接続された複数のオペレータを含む。シンタックスツリーは、複数の異なるタイプのオペレータを含むことができる。すなわち、異なるオペレータが、ソースコードにおけるｒｅｇｅｘによって実現される異なる機能に対応することができる。
【００５３】
ブロック１１４において、シンタックスツリーはオートマトンに変換される。オートマトンは、ＦＳＭのソフトウェアモデルを含み、したがって、決定論的または非決定論的として分類することができる。決定論的オートマトンは、所定の時間における単一の実行経路を有し、一方で、非決定論的オートマトンは、複数の同時実行経路を有する。オートマトンは複数の状態を含む。シンタックスツリーをオートマトンに変換するために、シンタックスツリーにおけるオペレータ及びオペレータ間の関係は、状態間の遷移を伴う状態に変換される。一実施例においては、オートマトンは、ＦＳＭラチス３０のハードウェアに部分的に基づいて変換することができる。
【００５４】
一実施例においては、オートマトン用の入力シンボルは、アルファベット、０〜９の数字及び他の印刷可能な文字のシンボルを含む。一実施例においては、入力シンボルは、０〜２５５（その数値も含む）バイト値によって表される。一実施例においては、オートマトンは、グラフのノードが状態の組に対応する有向グラフとして表すことができる。一実施例においては、入力シンボルα上の状態ｐから状態ｑへの遷移、すなわち、δ（ｐ、α）は、ノードｐからノードｑへの有向接続によって示される。一実施例においては、オートマトンの反転によって、幾つかのシンボルαにおける各遷移ｐ→ｑが、同一シンボルにおいてｑ→ｐに反転される新規オートマトンが生成される。反転においては、開始状態が最終状態になり、そして最終状態が開始状態になる。一実施例においては、オートマトンによって認識される（例えば、マッチする）言語は、オートマトンに順次入力されるとき最終状態に到達する全ての可能性のある文字ストリングの組である。オートマトンによって認識される言語における各ストリングは、開始状態から１つ以上の最終状態への経路を追跡する。
【００５５】
ブロック１１６においては、オートマトンが構成された後、オートマトンは、とりわけ、その複雑性及びサイズを減少させるために最適化される。オートマトンは、余分な状態を組み合わせることによって最適化することができる。
【００５６】
ブロック１１８においては、最適化されたオートマトンがネットリストに変換される。オートマトンのネットリストへの変換においては、ＦＳＭラチス３０上のハードウェア素子（例えば、ＳＭＥ３４、３６、他の素子）へのオートマトンの各状態をマップして、ハードウェア素子間の接続を判定する。
【００５７】
ブロック１２０においては、ネットリストが、ネットリストの各ノードに対応するターゲットデバイス（例えば、ＳＭＥ３４、３６、専用素子５８）の特定のハードウェア素子を選択するために配置される。一実施例においては、この配置によって、ＦＳＭラチス３０の一般的入力及び出力制約に基づいて、各特定のハードウェア素子が選択される。
【００５８】
ブロック１２２においては、配置されたネットリストが、ネットリストによる接続の記述を達成するように選択されたハードウェア素子をともに結合するために、プログラマブルスイッチング素子（例えば、ブロック間スイッチング素子４０、ブロック内スイッチング素子４２及び行内スイッチング素子４４）用の設定を判定するためにルーティングされる。一実施例においては、プログラマブルスイッチング素子の設定は、選択されたハードウェア素子を接続するのに使用されるＦＳＭラチス３０の特定の導体、及びプログラマブルスイッチング素子用の設定を判定することによって判定される。ルーティングにおいては、ブロック１２０において配置されたハードウェア素子間の接続のより特定な制限を考慮することができる。したがって、ルーティングにおいては、ＦＳＭラチス３０上の導体の実際の制限がある場合でも適切な接続をするために、グローバル配置によって判定されたように、ハードウェア素子の幾つかの位置を調整してもよい。
【００５９】
一旦ネットリストが配置されルーティングされると、配置されてルーティングされたネットリストを、ＦＳＭラチス３０の構成用の複数ビットに変換することができる。複数ビットは、本明細書においては画像（例えば、バイナリ画像）とも称される。
【００６０】
ブロック１２４においては、画像がコンパイラ２０によって発行される。画像は、ＦＳＭラチス３０の特定のハードウェア素子の構成用の複数ビットを含む。プログラムされたＦＳＭラチス３０がソースコードによって記述された機能を有するＦＳＭを実現するように、ビットは、ＦＳＭラチス３０上にロードし、ＳＭＥ３４、３６、専用素子５８、及びプログラマブルスイッチング素子の状態を構成することができる。配置（ブロック１２０）及びルーティング（ブロック１２２）では、オートマトンにおける特定の状態へとＦＳＭラチス３０における特定の位置の特定のハードウェア素子をマップすることができる。したがって、画像におけるビットは、所望の機能（複数可）を実現するために、特定のハードウェア素子を構成することができる。一実施例においては、画像は、コンピュータ可読媒体にマシンコードを保存することによって発行することができる。別の実施例においては、画像は、ディスプレイデバイス上に画像を表示することによって発行することができる。さらに別の実施例においては、画像は、ＦＳＭラチス３０上に画像をロードするための構成デバイスなどの別のデバイスに画像を送信することによって発行することができる。さらに別の実施例においては、画像はＦＳＭラチス（例えば、ＦＳＭラチス３０）上に画像をロードすることによって発行することができる。
【００６１】
一実施例においては、画像は、ＳＭＥ３４、３６及び他のハードウェア素子に画像からのビット値を直接ロードするか、または１つ以上のレジスタに画像をロードして、その後、ＳＭＥ３４、３６及び他のハードウェア素子にレジスタからのビット値を書き込むことのいずれかによって、ＦＳＭラチス３０上にロードすることができる。一実施例においては、構成デバイス及び／またはコンピュータが１つ以上のメモリアドレスに画像を書き込むことによって、ＦＳＭラチス３０上に画像をロードできるように、ＦＳＭラチス３０のハードウェア素子（例えば、ＳＭＥ３４、３６、専用素子５８、プログラマブルスイッチング素子４０、４２、４４）は、マップされたメモリである。
【００６２】
本明細書に記述する方法の実施例は、少なくとも部分的にマシンまたはコンピュータで実現することができる。幾つかの実施例は、前述の実施例に記述したような方法を実施するように電子デバイスを構成するように動作可能な命令がエンコードされたコンピュータ可読媒体またはマシン可読媒体を含むことができる。当該方法の実現では、マイクロコード、アセンブリ言語コード、より高いレベルの言語コードなどのコードを含むことができる。当該コードは、種々の方法を実施するためのコンピュータ可読命令を含むことができる。コードは、コンピュータプログラム製品の一部を形成してもよい。さらに、コードは、実行中または他の時間中に、１つ以上の揮発性または不揮発性コンピュータ可読媒体に具体的に格納されてもよい。これらのコンピュータ可読媒体は、これらに限定されないが、ハードディスク、リムーバブル磁気ディスク、リムーバブル光ディスク（例えば、コンパクトディスク及びデジタルビデオディスク）、磁気カセット、メモリカードまたはスティック、ランダムアクセスメモリ（ＲＡＭ）、リードオンリメモリ（ＲＯＭ）などを含むことができる。
【００６３】
ここで図９を参照し、ステートマシンエンジン１４（例えば、単一チップ上の単一デバイス）の実施形態を図示する。前述のように、ステートマシンエンジン１４は、データバスを介して、メモリ１６などのソースからデータを受信するように構成される。図示する実施形態においては、データを、ダブルデータレートスリー（ＤＤＲ３）バスインターフェイス１３０などのバスインターフェイスを通して、ステートマシンエンジン１４に送信できる。ＤＤＲ３バスインターフェイス１３０は、１Ｇバイト／秒以上の速度でデータを交換（例えば、提供及び受信）可能であってもよい。そのようなデータ交換速度は、ステートマシンエンジン１４によってデータが解析される速度よりも大きくてもよい。認識されるように、解析されるべきデータのソースに応じて、バスインターフェイス１３０は、ＮＡＮＤフラッシュインターフェイス、ペリフェラルコンポーネントインターコネクト（ＰＣＩ）インターフェイス、ギガビットメディア独立型インターフェイス（ＧＭＩＩ）などの、ステートマシンエンジン１４とデータソースとでデータをやり取りするための任意の適切なバスインターフェイスであってもよい。前述のように、ステートマシンエンジン１４は、データを解析するように構成された１つ以上のＦＳＭラチス３０を含む。各ＦＳＭラチス３０は、２つのハーフラチスに分割されてもよい。図示する実施形態においては、ラチス３０が４８Ｋ  ＳＭＥを含むように、各ハーフラチスは、２４Ｋ  ＳＭＥ（例えば、ＳＭＥ３４、３６）を含んでもよい。ラチス３０は、図２〜図５に関して前述したように配列された任意の所望の数のＳＭＥを含んでもよい。さらに、唯一のＦＳＭラチス３０を図示したが、前述のように、ステートマシンエンジン１４は複数のＦＳＭラチス３０を含んでもよい。
【００６４】
解析されるべきデータは、バスインターフェイス１３０で受信され、多数のバッファ及びバッファインターフェイスを通してＦＳＭラチス３０へと提供することができる。図示する実施形態においては、データ経路は、データバッファ１３２、命令バッファ１３３、プロセスバッファ１３４、並びにインターランク（ＩＲ）バス及びプロセスバッファインターフェイス１３６を含む。データバッファ１３２は、解析されるべきデータを受信して一時的に格納するように構成される。一実施形態においては、２つのデータバッファ１３２（データバッファＡ及びデータバッファＢ）が存在する。データは、２つのデータバッファ１３２のうちのいずれかに格納することができ、一方で、ＦＳＭラチス３０による解析のために、他方のデータバッファ１３２からデータは除かれている。バスインターフェイス１３０は、データバッファ１３２が満たされるまで、解析されるべきデータをデータバッファ１３２に提供するように構成できる。バスインターフェイス１３０は、データバッファ１３２が満たされた後、他の目的（例えば、データバッファ１３２が解析されるべきさらなるデータの受信に利用可能になるまで、データストリームから他のデータを提供するため）に自由に使用できるように構成することができる。図示する実施形態においては、データバッファ１３２は、それぞれ、３２Ｋバイトであってもよいが、他の実施形態においては、データバッファ１３２は、任意の適切なサイズ（例えば、４Ｋバイト、８Ｋバイト、１６Ｋバイト、６４Ｋバイトなど）であってもよい。命令バッファ１３３は、バスインターフェイス１３０を通じてプロセッサ１２からの命令、例えば、解析されるべきデータに対応する命令、及びステートマシンエンジン１４の構成に対応する命令を受信するように構成される。ＩＲバス及びプロセスバッファインターフェイス１３６は、プロセスバッファ１３４へのデータ提供を容易にすることができる。ＩＲバス及びプロセスバッファインターフェイス１３６を使用することによって、データがＦＳＭラチス３０によって順番に処理されることを保証できる。ＩＲバス及びプロセスバッファインターフェイス１３６は、データが正確な順序で受信されて解析されるように、データの交換、タイミングデータ、パッキング命令などを調整することができる。概して、ＩＲバス及びプロセスバッファインターフェイス１３６は、複数のデバイスをランクにおけるデバイスとして使用することができる。ランクにおけるデバイスである複数のデバイスは、複数のデバイスの全てが全ての共有データを正しい順序で受信するようにデータを共有する。例えば、複数の物理デバイス（例えば、ステートマシンエンジン１４、チップ、個々のデバイス）は、ランクに配列され、ＩＲバス及びプロセスバッファインターフェイス１３６を通じて互いにデータを提供することができる。この用途のための「ランク」という用語は、同一のチップセレクトに接続されたステートマシンエンジン１４の組を指す。図示する実施形態においては、ＩＲバス及びプロセスバッファインターフェイス１３６は、８ビットデータバスを含むことができる。
【００６５】
図示する実施形態においては、ステートマシンエンジン１４は、ステートマシンエンジン１４を通したデータの提供を援助するためのデコンプレッサ１３８及びコンプレッサ１４０も含む。認識できるように、コンプレッサ１４０及びデコンプレッサ１３８は、ソフトウェア及び／またはハードウェア設計を単純化するための同一の圧縮アルゴリズムを使用することができる。しかしながら、コンプレッサ１４０及びデコンプレッサ１３８は、異なるアルゴリズムを使用することもできる。データを圧縮することによって、バスインターフェイス１３０（例えば、ＤＤＲ３バスインターフェイス）の利用時間を最小限化することができる。本実施形態においては、コンプレッサ１４０を使用して、状態ベクトルデータ、コンフィギュレーションデータ（例えば、プログラミングデータ）、及びＦＳＭラチス３０による解析後に得られるマッチ結果データを圧縮できる。一実施形態においては、コンプレッサ１４０及びデコンプレッサ１３８へとかつ／またはそこから移動するデータが（例えば、圧縮でも解凍でも）変更されないように、コンプレッサ１４０及びデコンプレッサ１３８を無効にする（例えば、停止させる）ことができる。
【００６６】
コンプレッサ１４０及びデコンプレッサ１３８は、複数の組のデータであって、各組のデータの長さが変化し得る、複数組のデータを処理するようにも構成することができる。圧縮データを「パディング」し、各々の圧縮領域が終了する時に関するインジケータを含ませることによって、コンプレッサ１４０は、ステートマシンエンジン１４を通じた全体的な処理速度を改善することができる。
【００６７】
ステートマシンエンジン１４は状態ベクトルシステム１４１を含み、これは、状態ベクトルキャッシュメモリ１４２、状態ベクトルメモリバッファ１４４、状態ベクトル中間入力バッファ１４６、及び状態ベクトル中間出力バッファ１４８を有する。状態ベクトルシステム１４１を使用して、ＦＳＭラチス３０の複数の状態ベクトルを格納し、状態ベクトルをステートマシンエンジン１４にまたはそこから離すように移動し、そして状態ベクトルをＦＳＭラチス３０に提供して、提供された状態ベクトルに対応する状態にＦＳＭラチス３０を復元することができる。例えば、各状態ベクトルは、状態ベクトルキャッシュメモリ１４２に一時的に格納することができる。すなわち、状態を復元して後にさらなる解析に使用することができるように、各ＳＭＥ３４、３６の状態を格納し、その一方で、新規のデータセット（例えば、検索語）の解析のために、ＳＭＥ３４、３６を使用されていない状態にすることができる。典型的なキャッシュメモリと同様に、状態ベクトルキャッシュメモリ１４２は、例えば、ここではＦＳＭラチス３０によって迅速検索及び使用されるように状態ベクトルを格納することができる。図示する実施形態においては、状態ベクトルキャッシュメモリ１４２は、最大５１２個の状態ベクトルを格納することができる。各状態ベクトルは、ＦＳＭラチス３０のＳＭＥ３４、３６の状態（例えば、アクティブ化されているか否か）、及びカウンタ５８の動的（例えば、最新の）カウントを含む。
【００６８】
認識されるように、状態ベクトルデータは、ランク内の異なるステートマシンエンジン１４（例えば、チップ）間でやり取りすることができる。状態ベクトルデータは、種々の目的のために異なるステートマシンエンジン１４間でやり取りすることができる。この目的は、例えば、ＦＳＭラチス３０のＳＭＥ３４、３６の状態とカウンタ５８の動的カウントとの同期、複数のステートマシンエンジン１４にわたる同一の機能の実行、複数のステートマシンエンジン１４にわたる結果の再生成、複数のステートマシンエンジン１４にわたる結果のカスケード接続、ＳＭＥ３４、３６の状態のヒストリ及び複数のステートマシンエンジン１４を通じてカスケードされたデータを解析するために使用されるカウンタ５８の動的カウントの格納などを含む。さらにまた、ステートマシンエンジン１４内において状態ベクトルデータを使用して状態ベクトルを迅速に復元できることが留意されるべきである。例えば、状態ベクトルデータを使用して、ＳＭＥ３４、３６の状態及びカウンタ５８の動的カウントを、（例えば、新規の検索語を検索するための）初期化状態に復元し、ＳＭＥ３４、３６の状態及びカウンタ５８の動的カウントを、（例えば、以前に検索した検索語を検索するために）以前の状態に復元し、かつＳＭＥ３４、３６の状態及びカウンタ５８の動的カウントを、（例えば、カスケード検索において検索語を検索するための）カスケード構成を構成するように変化させることができる。ある実施形態においては、（例えば、状態ベクトルデータの解析、状態ベクトルデータを修正するための再構成、状態ベクトルデータの効率を改善するための再構成などのために）状態ベクトルデータをプロセッサ１２に提供することができるように、状態ベクトルデータをバスインターフェイス１３０に提供することができる。
【００６９】
例えば、ある実施形態においては、ステートマシンエンジン１４は、ＦＳＭラチス３０から外部デバイスにキャッシュされた状態ベクトルデータ（例えば、状態ベクトルシステム１４１によって格納されたデータ）を提供することができる。外部デバイスは、状態ベクトルデータを受信し、状態ベクトルデータを修正し、修正した状態ベクトルデータを、ＦＳＭラチス３０を復元（例えば、リセッティング、初期化）するためにステートマシンエンジン１４に提供することができる。したがって、外部デバイスは、所望のようにステートマシンエンジン１４が状態をスキップ（例えば、ジャンプ）できるように、状態ベクトルデータを修正できる。
【００７０】
状態ベクトルキャッシュメモリ１４２は、任意の適切なデバイスから状態ベクトルデータを受信できる。例えば、状態ベクトルキャッシュメモリ１４２は、ＦＳＭラチス３０、（例えば、ＩＲバス及びプロセスバッファインターフェイス１３６を通じて）別のＦＳＭラチス３０、デコンプレッサ１３８などから状態ベクトルを受信することができる。図示する実施形態においては、状態ベクトルキャッシュメモリ１４２は、状態ベクトルメモリバッファ１４４を通じて他のデバイスから状態ベクトルを受信できる。さらにまた、状態ベクトルキャッシュメモリ１４２は、状態ベクトルデータを任意の適切なデバイスに提供することができる。例えば、状態ベクトルキャッシュメモリ１４２は、状態ベクトルデータを、状態ベクトルメモリバッファ１４４、状態ベクトル中間入力バッファ１４６、及び状態ベクトル中間出力バッファ１４８に提供することができる。
【００７１】
状態ベクトルメモリバッファ１４４、状態ベクトル中間入力バッファ１４６、及び状態ベクトル中間出力バッファ１４８などのさらなるバッファを、高速検索及び状態ベクトルの格納に適応させ、その一方で、ステートマシンエンジン１４を通じてインターリーブされたパケットを有する個々のデータセットを処理するように、状態ベクトルキャッシュメモリ１４２と併せて使用することができる。図示する実施形態においては、状態ベクトルメモリバッファ１４４、状態ベクトル中間入力バッファ１４６、及び状態ベクトル中間出力バッファ１４８の各々は、１つの状態ベクトルを一時的に格納するように構成されてもよい。状態ベクトルメモリバッファ１４４を使用して、任意の適切なデバイスから状態ベクトルデータを受信し、状態ベクトルデータを任意の適切なデバイスに提供することができる。例えば、状態ベクトルメモリバッファ１４４を使用して、ＦＳＭラチス３０、（例えば、ＩＲバス及びプロセスバッファインターフェイス１３６を通じて）別のＦＳＭラチス３０、デコンプレッサ１３８、及び状態ベクトルキャッシュメモリ１４２から状態ベクトルを受信することができる。別の実施例として、状態ベクトルメモリバッファ１４４を使用して、状態ベクトルデータを、（例えば、他のＦＳＭラチス３０に向けて）ＩＲバス及びプロセスバッファインターフェイス１３６、コンプレッサ１４０、及び状態ベクトルキャッシュメモリ１４２に提供することができる。
【００７２】
同じように、状態ベクトル中間入力バッファ１４６を使用して、任意の適切なデバイスから状態ベクトルデータを受信し、状態ベクトルデータを任意の適切なデバイスに提供することができる。例えば、状態ベクトル中間入力バッファ１４６を使用して、（例えば、ＩＲバス及びプロセスバッファインターフェイス１３６を通じて）ＦＳＭラチス３０、デコンプレッサ１３８、及び状態ベクトルキャッシュメモリ１４２から状態ベクトルを受信することができる。別の実施例として、状態ベクトル中間入力バッファ１４６を使用して、状態ベクトルをＦＳＭラチス３０に提供することができる。さらにまた、状態ベクトル中間出力バッファ１４８を使用して、任意の適切なデバイスから状態ベクトルを受信し、状態ベクトルを任意の適切なデバイスに提供することができる。例えば、状態ベクトル中間出力バッファ１４８を使用して、ＦＳＭラチス３０、及び状態ベクトルキャッシュメモリ１４２から状態ベクトルを受信することができる。別の実施例として、状態ベクトル中間出力バッファ１４８を使用して、状態ベクトルを、（例えば、ＩＲバス及びプロセスバッファインターフェイス１３６を通じて）ＦＳＭラチス３０、及びコンプレッサ１４０に提供することができる。
【００７３】
一旦興味ある結果がＦＳＭラチス３０によって生成されると、マッチ結果をマッチ結果メモリ１５０に格納することができる。例えば、マッチ（例えば、興味あるパターンの検出）を示す「マッチベクトル」を、マッチ結果メモリ１５０に格納することができる。マッチ結果を、その後、例えば、バスインターフェイス１３０を通じてプロセッサ１２に伝送するためにマッチバッファ１５２に送信することができる。前述のように、マッチ結果は圧縮されてもよい。
【００７４】
さらなるレジスタ及びバッファを、同様にステートマシンエンジン１４に提供してもよい。例えば、ステートマシンエンジン１４は、制御及びステータスレジスタ１５４を含んでもよい。さらに、復元及びプログラムバッファ１５６を、最初にＦＳＭラチス３０のＳＭＥ３４、３６を構成し、または解析中にＦＳＭラチス３０におけるＳＭＥ３４、３６の状態を復元するのに使用するために提供してもよい。同様に、保存及び修復マップバッファ１５８も、セットアップ及び使用のために保存及び修復マップを格納するために提供してもよい。
【００７５】
図１０は、デバイスがランクにおいて配列された複数の物理的なステートマシンエンジン１４の一実施例を図示する。認識できるように、ステートマシンエンジン１４とプロセッサ１２との間のインターフェイス（例えば、ＤＤＲ３バスインターフェイス１３０）によって、ステートマシンエンジン１４は、プロセッサ１２からの全てのデータ線を使用してプロセッサ１２からデータを受信できる。例えば、プロセッサ１２が６４本のデータ線を有し、各ステートマシンエンジン１４が８本のデータ線を有する場合には、プロセッサ１２の全てのデータ線からデータを受信するように、８つのステートマシンエンジン１４を６４本のデータ線に結合することができる。したがって、プロセッサ１２は、迅速にかつ標準インターフェイスを使用して、ステートマシンエンジン１４にデータを提供することができる。さらに、ステートマシンエンジン１４は、ステートマシンエンジン１４によって集合的に受信される全てのデータが全てのステートマシンエンジン１４に正しい手順で提供されるように、ともに調整するように構成できる。
【００７６】
前述のように、解析されるべきデータは、バスインターフェイス１３０で受信される。バスインターフェイス１３０は、データバッファ１３２及び命令バッファ１３３を含む、各ステートマシンエンジン１４（例えば、Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６、Ｆ７）のデータバッファシステム１５９にデータを導く。データバッファ１３２は、解析されるべきデータを受信して一時的に格納するように構成される。図示する実施形態においては、各ステートマシンエンジン１４に２つのデータバッファ１３２（例えば、データバッファＡ及びデータバッファＢ）が存在する。データは、２つのデータバッファ１３２のうちのいずれかに格納することができ、一方で、ＦＳＭラチス３０による解析のために、他方のデータバッファ１３２からデータは除かれている。前述のように、命令バッファ１３３は、バスインターフェイス１３０を通じてプロセッサ１２からの命令、例えば、解析されるべきデータに対応する命令を受信するように構成される。解析されるべきデータ及びデータに対応する命令が、データバッファシステム１５９からＩＲバス及びプロセスバッファインターフェイス１３６を通じて、ＦＳＭラチス３０の１つ以上に提供される。本実施形態においては、物理的なＦＳＭラチス３０は、論理グループにおいて配列される。つまり、ステートマシンエンジン１４Ｆ０及びＦ１のＦＳＭラチス３０は、論理グループＡ１６２に配列され、ステートマシンエンジン１４Ｆ２及びＦ３のＦＳＭラチス３０は、論理グループＢ１６４に配列され、ステートマシンエンジン１４Ｆ４及びＦ５のＦＳＭラチス３０は、論理グループＣ１６６に配列され、そしてステートマシンエンジン１４Ｆ６及びＦ７のＦＳＭラチス３０は、論理グループＤ１６８に配列される。他の実施形態においては、物理的なＦＳＭラチス３０は、任意の適切な数（例えば、１、２、３、４、５、６、７、８）の論理グループに配列されてもよい。さらにまた、認識されるように、ＩＲバス及びプロセスバッファインターフェイス１３６を通じてステートマシンエンジン１４間でデータをやり取りすることができる。例えば、ＩＲバス及びプロセスバッファインターフェイス１３６を使用して、任意のステートマシンエンジン１４（例えば、Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６、Ｆ７）間でデータをやり取りすることができる。８つのステートマシンエンジン１４を図示したが、ランクにおけるデバイスは、任意の適切な数のステートマシンエンジン１４（例えば、１、２、４、８など）を有することができる。認識されるように、各ステートマシンエンジン１４のＩＲバス及びプロセスバッファインターフェイス１３６は、（例えば、それ自身のデータバッファシステム１５９、及び他のステートマシンエンジン１４のＩＲバス及びプロセスバッファインターフェイス１３６からの）データを受信するための入力を含むことができる。同じように、各ステートマシンエンジン１４のＩＲバス及びプロセスバッファインターフェイス１３６は、（例えば、ＦＳＭラチス３０、及び他のステートマシンエンジン１４のＩＲバス及びプロセスバッファインターフェイス１３６に）データを送信するための出力を含むことができる。
【００７７】
バスインターフェイス１３０は、データを効率的に使用するように調整されたフォーマットにおいて解析されるべきデータを受信することができる。具体的には、図１１〜図１４は、バスインターフェイス１３０を通じてステートマシンエンジン１４に提供されたデータブロックに、プロセッサ１２によってデータを割り当てる（例えば、グループ化する）ことができる方法の実施例を図示する。
【００７８】
ここで図１１を参照し、ステートマシンエンジン１４に提供されるデータブロックに、プロセッサ１２によって割り当てられたデータセグメント（例えば、データセット、検索語）の一実施例を図示する。本実施形態においては、複数のデータセグメントが単一のデータブロックに割り当てられる。各データブロックは、ＦＳＭラチス３０の単一の論理グループ（例えば、１６２、１６４、１６６、１６８）（例えば、ランクにおけるステートマシンエンジン１４のうちの１つ以上のステートマシンエンジン１４）によって解析されるように割り当てられる。例えば、データストリーム１７０（例えば、プロセッサ１２によってステートマシンエンジン１４に送信される大量のデータ）は、プロセッサ１２によって、論理グループＡ１６２用に意図されたデータに対応する第一のデータブロック１７２、論理グループＢ１６４用に意図されたデータに対応する第二のデータブロック１７４、論理グループＣ１６６用に意図されたデータに対応する第三のデータブロック１７６、及び論理グループＤ１６８用に意図されたデータに対応する第四のデータブロック１７８に割り当てられる。つまり、データストリーム１７０は、プロセッサ１２によって、データセグメント１８０、１８２、１８４、１８６、１８８、１９０、１９２、１９４、１９６、１９８及び２００から組み立てられる。認識されるように、データセグメント１８０、１８２、１８４、１８６、１８８、１９０、１９２、１９４、１９６、１９８及び２００の各々は、ＦＳＭラチス３０によって解析されるデータセットを表し得る。認識されるように、プロセッサ１２は、データセグメント１８０、１８２、１８４、１８６、１８８、１９０、１９２、１９４、１９６、１９８及び２００を、任意の適切な根拠に従いデータブロック１７２、１７４、１７６及び１７８に割り当てることができる。例えば、プロセッサ１２は、データセグメントを、各データセットの長さ及び／またはデータセットを効率的に処理するための、解析されるデータセットの順序に基づいて、特定のデータブロックに割り当てることができる。
【００７９】
データセグメント１８０、１８２、１８４、１８６、１８８、１９０、１９２、１９４、１９６、１９８及び２００は、任意の適切な様式でデータブロック１７２、１７４、１７６及び１７８に割り当てることができる。例えば、データセグメント１８０、１８２、１８４、１８６、１８８、１９０、１９２、１９４、１９６、１９８及び２００は、データブロック１７２、１７４、１７６及び１７８におけるバイト数を最小限化するように、データブロック１７２、１７４、１７６及び１７８に割り当てることができる。別の実施例として、データセグメント１８０、１８２、１８４、１８６、１８８、１９０、１９２、１９４、１９６、１９８及び２００は、特定のデータセグメントがともにグループ化されるように、データブロック１７２、１７４、１７６及び１７８に割り当てることができる。
【００８０】
図示するように、第一のデータブロック１７２は、データセグメントＡ１８０、データセグメントＦ１９０、及びデータセグメントＩ１９６を含む。第二のデータブロック１７４は、データセグメントＢ１８２及びデータセグメントＫ２００を含む。さらにまた、第三のデータブロック１７６は、データセグメントＣ１８４、データセグメントＥ１８８、及びデータセグメントＧ１９２を含む。第四のデータブロック１７８は、データセグメントＤ１８６、データセグメントＨ１９４、及びデータセグメントＪ１９８を含む。
【００８１】
認識されるように、データブロックを効率的に処理するように全てのデータブロックが等しい量のデータを有してもよい。さらにまた、データブロック内のデータセグメントは、データセグメントが開始及び終了する時を処理デバイスが判定できるように、データブロック内において所定の間隔（例えば、バイト、単語）で開始及び／または終了してもよい。しかしながら、データセグメントは、所定の間隔で開始及び／または終了するための正確な量のデータを有さないことがある。したがって、データが所定の間隔でデータブロック内において開始及び／または終了するように、データパディングを特定のデータセグメント間に挿入してもよい。さらに、全てのデータブロックが等しい量のデータを有するように、データブロックの終端にデータパディングを追加してもよい。
【００８２】
ここで図１２を参照し、図１１のデータブロック１７２、１７４、１７６及び１７８のデータセグメント間に挿入されるデータパディングの一実施例を図示する。例えば、第一のデータブロック１７２では、データパディング２０２を、データセグメントＡ１８０とデータセグメントＦ１９０との間に挿入できる。さらに、データパディング２０４を、データセグメントＦ１９０とデータセグメントＩ１９６との間に挿入できる。別の実施例として、第二のデータブロック１７４では、データパディング２０６を、データセグメントＢ１８２とデータセグメントＫ２００との間に挿入できる。第三のデータブロック１７６では、データパディング２０８を、データセグメントＣ１８４とデータセグメントＥ１８８との間に挿入できる。同じように、データパディング２１０を、データセグメントＥ１８８とデータセグメントＧ１９２との間に挿入できる。別の実施例として、第四のデータブロック１７８では、データパディング２１２を、データセグメントＤ１８６とデータセグメントＨ１９４との間に挿入できる。さらに、データパディング２１４を、データセグメントＨ１９４とデータセグメントＪ１９８との間に挿入できる。
【００８３】
データパディング２０２、２０４、２０６、２０８、２１０、２１２及び２１４は、解析されない任意の適切なバイト数のデータ（例えば、無効データ、ジャンクデータ、フィラーデータ、ガベージデータなど）を含んでもよい。一実施形態においては、データパディングとして使用されるバイト数は、先のデータセグメントのバイト数に加えられた場合に完全なワード境界に達するバイト数であってもよい（すなわち、先のデータセグメントのバイト数とデータパディングとして使用されるバイト数との和は、完全なワード境界によって割り切れる。例えば、データパディング２０２のバイト数は、データパディング２０２とデータセグメントＡ１８０（すなわち、先のデータセグメント）とのバイトの合計数が、完全なワード境界によって割り切れる（例えば、余りがない）数にできる。図示する実施形態においては、完全なワード境界は、８バイトであってもよい。他の実施形態においては、完全なワード境界は、任意の適切な数のバイトまたはビットであってもよい。それゆえ、図示する実施形態においては、仮にデータセグメントＡ１８０が６３バイトのデータを含む場合には、データパディング２０２は、１バイトのデータを含むであろう（例えば、データセグメントＡ１８０とデータパディング２０２とのデータの合計バイトを６４にすると、この６４は、８バイトで割り切れる）。別の実施例として、データセグメントＡ１８０が（例えば、８によって割り切れない）６０バイトのデータを含む場合には、データパディング２０２は、４バイトのデータを含むであろう。さらなる実施例として、データセグメントＡ１８０が６４バイトのデータを含む場合には、データパディング２０２は、ゼロバイトのデータを含むであろう。換言すると、データセグメントＡ１８０とデータセグメントＦ１９０との間にデータパディング２０２を必要としないであろう。認識されるように、各データパディング２０２、２０４、２０６、２０８、２１０、２１２及び２１４も、同様の様式で作用することができる。
【００８４】
ここで図１３を参照し、図１２のデータブロック１７２、１７４、１７６及び１７８のデータセグメントの後に挿入されるデータパディングの一実施例を図示する。具体的には、各データブロック１７２、１７４、１７６及び１７８におけるバイト数を等しくするために、必要に応じて、各データブロック１７２、１７４、１７６及び１７８の終端にデータパディングを挿入してもよい。さらにまた、各データブロック１７２、１７４、１７６及び１７８の終端に位置するデータパディングを使用できることによって、各データブロック１７２、１７４、１７６及び１７８は前述のような完全なワード境界に達する。図示する実施形態においては、データセグメントＩ１９６の後ろにデータパディング２１６が挿入され、データセグメントＧ１９２の後ろにデータパディング２１８が挿入され、そしてデータセグメントＪ１９８の後ろにデータパディング２２０が挿入される。したがって、データブロック１７２、１７４、１７６及び１７８の各々が、等しいバイト数を含み、かつ完全なワード境界に達する。
【００８５】
ＦＳＭラチス３０にとって、データパディングを有効データと区別することが困難である場合がある。したがって、有効データの解析中にＦＳＭラチス３０がデータパディングを識別して無視できるように、命令をデータブロック１７２、１７４、１７６及び１７８に付随させることができる。そのような命令は、プロセッサ１２によってバスインターフェイス１３０を通じてステートマシンエンジン１４に送信され、そしてステートマシンエンジン１４の命令バッファ１６０によって受信、格納及び提供することができる。命令を生成するために、プロセッサ１２は、データストリーム１７０を、領域２２２、２２４、２２６、２２８、２３０、２３２、２３４及び２３６に論理的に分けることができる。領域２２２、２２４、２２６、２２８、２３０、２３２、２３４及び２３６の端部境界は、各領域が任意のデータパディング端部を終端とするように形成できる。例えば、第一の領域２２２は、データパディング２０８端部を終端とする。別の実施例として、第五の領域２３０は、データパディング２０４端部を終端とする。
【００８６】
データブロック１７２、１７４、１７６及び１７８に付随する命令は、各領域２２２、２２４、２２６、２２８、２３０、２３２、２３４及び２３６のバイトの合計数、並びに各領域内の各データブロック１７２、１７４、１７６及び１７８における有効バイト数（例えば、パディングのバイトを除くバイト数）を含むことができる。例えば、命令は、第一の領域２２２に対応するバイト数２３８、第一の領域２２２内の第一のデータブロック１７２における有効バイトに対応するバイト数２４０、第一の領域２２２内の第二のデータブロック１７４における有効バイトに対応するバイト数２４２、第一の領域２２２内の第三のデータブロック１７６における有効バイトに対応するバイト数２４４、及び第一の領域２２２内の第四のデータブロック１７８における有効バイトに対応するバイト数２４６を含むことができる。この実施例においては、データセグメントＡ１、Ｂ１及びＤ１に続くパディングが存在しないため、２３８、２４０、２４２及び２４６に示すバイト数が等しいことに留意されたい。
【００８７】
同じように、命令は、第二の領域２２４に対応するバイト数２４８、２５０、２５２、２５４及び２５６、第三の領域２２６に対応するバイト数２５８、２６０、２６２、２６４及び２６６、第四の領域２２８に対応するバイト数２６８、２７０、２７２、２７４及び２７６、第五の領域２３０に対応するバイト数２７８、２８０、２８２、２８４及び２８６、第六の領域２３２に対応するバイト数２８８、２９０、２９２、２９４及び２９６、第七の領域２３４に対応するバイト数２９８、３００、３０２、３０４及び３０６、並びに、第八の領域２３６に対応するバイト数３０８、３１０、３１２、３１４及び３１６を含むことができる。命令が各領域２２２、２２４、２２６、２２８、２３０、２３２、２３４、２３６内の各データセグメントにおける有効バイト数を含むことができることが留意されるべきである。したがって、第七の領域２３４では、論理グループＡ１６２は、有効バイト数３００がゼロであってもよい。さらにまた、第八の領域２３６では、論理グループＡ１６２は、有効バイト数３１０がゼロであってもよい。したがって、ＦＳＭラチス３０は、命令を使用して、データセグメントに挿入されるデータパディングを識別することができる。１つの特定のタイプの命令を本明細書に提示したが、データブロック１７２、１７４、１７６及び１７８のグループに含まれる命令が、ＦＳＭラチス３０がデータパディング（すなわち、無効データ）から有効データを区別できる任意の適切なグループの命令であってもよいことが留意されるべきである。
【００８８】
ここで図１４を参照し、ステートマシンエンジン１４のデータバッファシステム１５９に伝送するために、プロセッサ１２によって組織化された図１３のデータブロック１７２、１７４、１７６及び１７８の一実施例を図示する。データブロック１７２、１７４、１７６及び１７８の各々は、全体のワード長と等しいバイト数３１８を有するデータの行で配列される。図示する実施形態においては、全体のワード長は、各ステートマシンエンジン１４（例えば、Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）が１バイトを示すため、８バイトである。データセグメントの各々からの第一のバイトは各データブロック１７２、１７４、１７６及び１７８の右側から始まり、データセグメントＡ１８０における第一のバイトが列Ｆ０に位置し、データセグメントＡ１８０における第八のバイトが列Ｆ７に位置するように、各データブロックの左側に向かうほど増大する。認識されるように、列Ｆ０は、Ｆ０ステートマシンエンジン１４のデータバッファ１３２に最初に格納されるデータを表し、列Ｆ１は、Ｆ１ステートマシンエンジン１４のデータバッファ１３２に最初に格納されるデータを表し、それ以降も同様である。さらにまた、データセグメントは、行内において上部から底部まで配置される。図示するように、データセグメントとデータパディングとの各々の組み合わせは、列Ｆ７を終端とする（すなわち、それらの各々が全体のワード長に広がる）。さらにまた、各データブロック１７２、１７４、１７６及び１７８のサイズは等しい。認識されるように、動作中、データブロック１７２、１７４、１７６及び１７８は、プロセッサ１２からステートマシンエンジン１４に連続的に提供することができる。
【００８９】
任意のブロック（１７２、１７４、１７６及び１７８）のデータは、対応する論理グループ（１６２、１６４、１６６または１６８のそれぞれ）用に意図されたデータが、ランクにおけるステートマシンエンジン１４のデータバッファシステム１５９の全体にわたって散布されるように、ランクにおけるデバイス内の全てのステートマシンエンジン１４のデータバッファシステム１５９にわたって提供され、格納される。データは、バスインターフェイス１３０を通じてデータバッファシステム１５９に迅速に提供できるような方法で受信及び格納することができる。ある実施形態においては、データバッファシステム１５９のデータバッファ１３２は、バスインターフェイス１３０からのデータを（例えば、所定の間隔で）ラッチするように構成できる。他の実施形態においては、データバッファシステム１５９のデータバッファ１３２は、データバッファ１３２とバスインターフェイス１３０との間の接続に基づいて、データの限られた部分だけを受信することができる。以下に詳細に説明するように、データバッファシステム１５９に格納されたデータは、データがデータバッファシステム１５９からＩＲバス及びプロセスバッファインターフェイス１３６を通じてプロセスバッファ１３４に提供されるときに選別される。
【００９０】
図１５は、デバイスがランクにおいて配列されており、ＩＲバス及びプロセスバッファインターフェイス１３６によってともに結合された複数の物理的なステートマシンエンジン１４の一実施例を図示する。具体的には、図示する実施形態においては、８つのステートマシンエンジン１４（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）が、単一プリント基板に配列されて、モジュール３４０を形成する。ある実施形態においては、モジュール３４０は、デュアルインラインメモリモジュール（ＤＩＭＭ）と同様に配列されてもよい。例えば、単一チップは、ステートマシンエンジン１４を１つだけ含んでもよい。さらにまた、１つのステートマシンエンジン１４を各々が有する複数のチップを、モジュール３４０のプリント基板に結合（例えば、電気的に、光学的に、別なように動作可能に結合）してもよい。例えば、プリント基板は、１つのステートマシンエンジン１４を各々が含む１個、２個、４個、８個、１６個またはそれ以上のチップを含んでもよい。さらに、ある実施形態においては、モジュール３４０は、モジュール３４０とコンピュータ、ワークステーションまたはサーバなどのシステムとを結合するための、７２個、１００個、１４４個、１６８個、１８４個、２００個、２４０個またはより少ないもしくは多いピンまたは接続素子を含むことができる。例えば、モジュール３４０は、２４０個のピンを含み、サーバにおけるスロット内に挿入されるように構成することができる。
【００９１】
モジュール３４０のピンは、ＤＤＲ３バスインターフェイス１３０に結合し、プロセッサ１２とモジュール３４０との間のデータ転送を容易にする。さらに、モジュール３４０のピンは、プリント基板のルーティングラインを使用して、ステートマシンエンジン１４（例えば、Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）を有するチップのピンに結合される。ＤＤＲ３バスインターフェイス１３０は、プロセッサ１２に、各ステートマシンエンジン１４のデータバッファシステム１５９のメモリアドレスを選択させることができるＤＤＲ３アドレスバス３４２を含む。図示するように、ＤＤＲ３アドレスバス３４２は、１６個のアドレス線を含む。しかしながら、他の実施形態においては、ＤＤＲ３アドレスバス３４２は、１６個よりも少ないまたは多いアドレス線を含んでもよい。ＤＤＲ３アドレスバス３４２の各アドレス線は、各ステートマシンエンジン１４のデータバッファシステム１５９に結合される。したがって、プロセッサ１２は、各ステートマシンエンジン１４のデータバッファシステム１５９のアドレスをともに選択することができる。
【００９２】
認識できるように、ステートマシンエンジン１４とプロセッサ１２との間のＤＤＲ３バスインターフェイス１３０によって、ステートマシンエンジン１４が、プロセッサ１２からの全てのデータ線を使用して、プロセッサ１２からデータを受信することができてもよい。例えば、プロセッサ１２が６４本のデータ線を有し、各ステートマシンエンジン１４が８本のデータ線を有する場合には、プロセッサ１２の全てのデータ線からデータを受信するように、８つのステートマシンエンジン１４が６４本のデータ線に結合することができる。したがって、プロセッサ１２は、迅速にかつ標準インターフェイスを使用して、ステートマシンエンジン１４にデータを提供することができる。さらに、ステートマシンエンジン１４は、ステートマシンエンジン１４によって集合的に受信される全てのデータが全てのステートマシンエンジン１４に正しい手順で提供されるように、ともに調整するように構成できる。図示する実施形態においては、ＤＤＲ３バスインターフェイス１３０は、各ステートマシンエンジン１４に結合されたデータ線３４４、３４６、３４８、３５０、３５２、３５４、３５６及び３５８の組を有するデータバス３４３を含む。図示するように、個々のデータ線が各ステートマシンエンジン１４に結合される。例えば、ある実施形態においては、データバス３４３は、６４本のデータ線を含み、モジュール３４０は、８つのステートマシンエンジン１４を含む。そのような実施形態においては、８本のデータ線が、８つのステートマシンエンジン１４の各々に結合され、かつ／またはそれぞれに専用であってもよい。したがって、データバス３４３及びＤＤＲ３アドレスバス３４２を使用して、それぞれのデータバイトを、各ステートマシンエンジン１４のデータバッファシステム１５９の選択されたアドレスに同期して提供することができる。ある実施形態においては、８本よりも少ないまたは多いデータ線が、ステートマシンエンジン１４とデータバス３４３とを結合してもよい。さらにまた、ＤＤＲ３バスインターフェイス１３０は、６４本よりも少ないまたは多いデータ線を含んでもよい。以下の表、表１は、規定の数のデータ線を有するＤＤＲ３バスインターフェイス１３０の構成、及びステートマシンエンジン１４に結合されたＤＤＲ３バスインターフェイス１３０におけるデータ線の数の種々の実施例を図示する。
【表１】
2016515266.tif 000003
【００９３】
表１に図示するように、データバス３４３が８本のデータ線を含む場合には、その８本のデータ線が、８本の線の入力データバス幅を有する１つのステートマシンエンジン１４に結合することができる。別の実施例として、データバス３４３が１６本のデータ線を含む場合には、その１６本のデータ線が、８本の線の入力データバス幅を有する２つのステートマシンエンジン１４、または１６本の線の入力データバス幅を有する１つのステートマシンエンジン１４に結合することができる。さらなる実施例として、データバス３４３が３２本のデータ線を含む場合には、その３２本のデータ線が、８本の線の入力データバス幅を有する４つのステートマシンエンジン１４、または１６本の線の入力データバス幅を有する２つのステートマシンエンジン１４に結合することができる。さらに、データバス３４３が６４本のデータ線を含む場合には、その６４本のデータ線が、８本の線の入力データバス幅を有する８つのステートマシンエンジン１４、または１６本の線の入力データバス幅を有する４つのステートマシンエンジン１４に結合することができる。
【００９４】
ＤＤＲ３バスインターフェイス１３０は、プロセッサ１２とモジュール３４０との間のデータ転送を容易にするための他の制御線３６０、３６２、３６４、３６６、３６８、３７０、３７２及び３７４を含む。他の制御線３６０、３６２、３６４、３６６、３６８、３７０、３７２及び３７４によって、プロセッサ１２と選択されたステートマシンエンジン１４との間の個別の通信、及び／またはプロセッサ１２と集合的なステートマシンエンジン１４との間の通信が可能になる。
【００９５】
動作中、プロセッサ１２は、ＤＤＲ３バスインターフェイス１３０にデータを提供できる。例えば、プロセッサ１２は、６４本のデータ線を有するデータバスを使用して、一度に６４ビットのデータを提供することができる。さらにまた、ステートマシンエンジン１４は、その各々が、各ステートマシンエンジン１４に結合された８本のデータ線から８ビットのデータを受信することができる。したがって、プロセッサ１２は、一度に６４ビットのデータをモジュール３４０に提供することができる。前述のように、ステートマシンエンジン１４は、他の異なるステートマシンエンジン１４によって解析されるべきデータを受信するように構成できる。それゆえ、プロセッサ１２は、モジュール３４０のステートマシンエンジン１４の１つ以上によって処理されるように各データブロックが意図されたデータブロックにおいて、モジュール３４０にデータを提供することができる。換言すると、プロセッサ１２は、それが提供するデータブロックをソート及び／またはパックしなくてもよい。例えば、プロセッサ１２は、連続的なバイト数のデータの一部がステートマシンエンジン１４の各々（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）によって受信及び格納される場合でさえも、ステートマシンエンジン１４Ｆ０によって解析されるように意図された連続的なバイト数のデータを提供することができる。したがって、プロセッサ１２は、単純かつ効率的な様式でデータをモジュール３４０に提供し、ステートマシンエンジン１４に、選択されたステートマシンエンジン１４によって処理されるデータをソートさせることができる。
【００９６】
プロセッサ１２は、ステートマシンエンジン１４に、プロセッサ１２から提供される各データブロックを解析するようステートマシンエンジン１４に命令するための命令、ステートマシンエンジン１４に、一定期間（例えば、所定の期間）中データを解析させるための命令、及びステートマシンエンジン１４に、プロセッサ１２から提供される各データブロックの長さに関する命令も提供することができる。ある実施形態においては、データバッファシステム１５９は、プロセッサ１２から受信した命令を格納するための特定のメモリロケーションを含むことができる。したがって、プロセッサ１２は、ＤＤＲ３アドレスバス３４２を使用して、命令の受信に専用のデータバッファシステム１５９の所定のアドレスを選択することができる。次に、プロセッサ１２は、データバス３４３及びＤＤＲ３アドレスバス３４２を使用して、ステートマシンエンジン１４の各々に命令を提供することができる。
【００９７】
ＩＲバス及びプロセスバッファインターフェイス１３６は、モジュール３４０の一部であり、ステートマシンエンジン１４を相互接続する接続（例えば、電気的、光学的または別の動作可能な接続）を含む。図示するように、ＩＲバス及びプロセスバッファインターフェイス１３６は、インストラクションバスの一部であってもよいＩＲデータバス３７６及び他の制御線３７８を含む。図示する実施形態においては、ＩＲデータバス３７６は、ステートマシンエンジン１４の各々を互いに結合する８本のデータ線を含む。具体的には、ＩＲデータバス３７６は、各ステートマシンエンジン１４のデータバッファシステム１５９と、各ステートマシンエンジン１４のプロセスバッファ１３４とを結合する。さらに、ＩＲデータバス３７６を使用して、プロセッサ１２から受信したデータをデータの解析のための他のステートマシンエンジン１４に提供することができる。他の制御線３７８を使用して、ステートマシンエンジン１４間のデータ転送を同期及び／または制御することができる。
【００９８】
ステートマシンエンジン１４を有する各チップは、プロセッサ１２から受信したデータを処理するために論理グループにグループ化してもよい。認識できるように、モジュール３４０のステートマシンエンジン１４は、１つ以上の論理グループを含むことができる。モジュール３４０では、全てのステートマシンエンジン１４（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）を含む１つの論理グループが存在してもよい。さらにまた、２つ、３つ、４つ、５つ、６つ、７つまたは８つの論理グループが存在してもよい。論理グループは、任意の数のステートマシンエンジン１４を有することができ、同一サイズでなくてもよい。例えば、一実施形態においては、第一の論理グループは、ステートマシンエンジン１４Ｆ０及びＦ１を含んでもよく、第二の論理グループは、ステートマシンエンジン１４Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７を含んでもよい。２つ以上のステートマシンエンジン１４を含むことができる論理グループを使用することによって、単一のステートマシンエンジン１４にプログラムするには大き過ぎる単一のオートマトンプロセッサブロックを、論理グループによって解析することができる。さらにまた、論理グループは、複数のデータブロックを、別個の論理グループによって同時に解析できるようにする。さらに、論理グループは、例えば、同一サイズを有する論理グループを使用して、かつ／またはパラレルプロセッシングによって、ハイスループット速度においてデータを解析できるようにする。したがって、モジュール３４０のアーキテクチャは、フレキシビリティをもたらし、モジュール３４０の単一のステートマシンエンジン１４に、最大１．０Ｇｂｐｓ以上のレートでデータを処理させることができる。さらにまた、モジュール３４０のアーキテクチャは、モジュール３４０に、例えば８つのステートマシンエンジン１４を使用したパラレルの８つの論理グループにおいてデータを処理させることができる。それによって、単一のステートマシンエンジン１４の最大８倍のレート（例えば、８．０Ｇｂｐｓ以上）のデータ処理レートを達成することができる。
【００９９】
各ステートマシンエンジン１４が論理グループの一部である場合でさえも、ステートマシンエンジン１４は、それらが特定の論理グループの一部であることの何らかの指示、及び／またはその論理グループの一部であるステートマシンエンジン１４の数についての何らかの指示を受信しなくてもよい。しかしながら、特定の情報を、命令として及び／または他の制御線３６０、３６２、３６４、３６６、３６８、３７０、３７２及び３７４を使用して、ステートマシンエンジン１４に提供してもよい。例えば、ステートマシンエンジン１４は、ＤＤＲ３バスインターフェイス１３０の合計のバス幅、ＤＤＲ３バスインターフェイス１３０に結合されたデータ線の数、ＩＲデータバス３７６のデータ線の数、ＤＤＲ３バスインターフェイス１３０におけるデバイス位置、ＩＲデータバス３７６におけるデバイス位置、ステートマシンエンジン１４がマスタデバイスであるか否か、ステートマシンエンジン１４がスレーブデバイスであるか否か、実行されるＩＲデータバス３７６サイクルの数、受信されるバイト数、及び／または解析される（例えば、有効データの）バイト数についての指示を受信及び／または格納することができる。
【０１００】
例えば、モジュール３４０の初期化中、プロセッサ１２は、各ステートマシンエンジン１４（例えば、０、１、２、３、４、５、６、７）に数を割り当てるように、各ステートマシンエンジン１４にデータを提供することができる。ある実施形態においては、「０」を受信するステートマシンエンジン１４が、ステートマシンエンジン１４Ｆ０かつ「マスタ」デバイスであってもよく、全ての他のデバイスが「スレーブ」デバイスであってもよい。他の実施形態においては、「マスタ」デバイスに、任意の適切な値を割り当てることができる。ある実施形態においては、「マスタ」デバイスは、ステートマシンエンジン１４の同期を調整するように構成できる。プロセッサ１２は、モジュール３４０の一部であるステートマシンエンジン１４の総数、ステートマシンエンジン１４が属する論理グループ、及び／またはモジュール３４０の一部である論理グループの数を表すデータも各ステートマシンエンジン１４に提供することができる。
【０１０１】
論理グループが１つである一実施形態においては、ＩＲバス及びプロセスバッファインターフェイス１３６によって、ランクにおける各ステートマシンエンジン１４（例えば、Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）が、プロセッサ１２によって提供された全てのデータバイトを解析できる。したがって、そのような実施形態においては、全データストリームを、ステートマシンエンジン１４の各々において処理することができる。複数の論理グループを有する別の実施形態においては、ＩＲバス及びプロセスバッファインターフェイス１３６によって、ランクにおける各ステートマシンエンジン１４が、データスライシングのスキームを実施することによって、データストリームのうちの割り当てられた一部をタイムリーに受信することができる。例えば、プロセッサ１２は各論理グループ用に意図されたデータを連続的に提供することができるが、ステートマシンエンジン１４は、意図されたステートマシンエンジン１４にデータを効率的に提供するようＩＲデータバス３７６にデータを提供できるように、オフセット様式において、データを各ステートマシンエンジン１４のデータバッファシステム１５９に格納することができる。
【０１０２】
図１６は、複数の物理的なステートマシンエンジン１４に結合されたＩＲバス及びプロセスバッファインターフェイス１３６の一実施例を図示する。具体的には、図示する実施形態は、２つの論理グループ（すなわち、論理グループ０及び論理グループ１）に分けられた４つのステートマシンエンジン１４を含む。さらにまた、４つのステートマシンエンジン１４は、３２本のデータ線を有するＤＤＲ３バスインターフェイス１３０に結合することができる。前述のように、ＩＲデータバス３７６がステートマシンエンジン１４の各々に結合される。さらにまた、他の制御線３７８は、ステートマシンエンジン１４の各々に結合されたランク同期化線（ＲＳＹＮＣ）３８０、ＩＲバスデータ有効線（ＩＲＤＶ）３８２、第一のＩＲバスデータストローブ線（ＩＲＤＱＳ）３８４、及び第二のＩＲバスデータストローブ線（ＩＲＤＱＳ＃）３８６を含む。ステートマシンエンジン１４の各々は、ＲＳＹＮＣ３８０からの入力を受信し、かつ／またはＲＳＹＮＣ３８０の信号を制御するように構成される。例えば、一実施形態においては、「スレーブ」デバイス及び／または「マスタ」デバイスは、ＲＳＹＮＣ３８０を論理０に引き込むことによって、ＲＳＹＮＣ３８０の信号を論理１から論理０に制御するように構成できる。一方で、「マスタ」デバイスは、ＲＳＹＮＣ３８０から受信した入力に基づいて、ＩＲＤＶ３８２の信号を制御するように構成できる。図示する実施形態においては、ステートマシンエンジン１４Ｆ０が「マスタ」デバイスとして構成され、一方で、ステートマシンエンジン１４Ｆ１、Ｆ２及びＦ３が「スレーブ」デバイスとして構成されている。さらにまた、ステートマシンエンジン１４Ｆ１、Ｆ２及びＦ３は、ＲＳＹＮＣ３８０の信号を制御するように構成され、一方で、ステートマシンエンジン１４Ｆ０は、ＲＳＹＮＣ３８０から受信した入力に基づいて、ＩＲＤＶ３８２の信号を制御するように構成される。ステートマシンエンジン１４Ｆ０は、ステートマシンエンジン１４Ｆ１、Ｆ２及びＦ３の全てがデータの受信に利用可能であることを示す第一の指示（例えば、論理ハイ）を受信するように構成できる。さらに、ステートマシンエンジン１４Ｆ０は、ステートマシンエンジン１４Ｆ１、Ｆ２及びＦ３の少なくとも１つがデータの受信に利用できないことを示す第二の指示（例えば、論理ロウ）を受信するように構成できる。例えば、ステートマシンエンジン１４Ｆ１、Ｆ２及びＦ３の任意の１つは、ステートマシンエンジン１４Ｆ１、Ｆ２及びＦ３の少なくとも１つがデータの受信に利用できないことを、ステートマシンエンジン１４Ｆ０に通知するために、ＲＳＹＮＣ３８０の信号を論理ロウに制御（例えば、論理ロウを出力）することができる。
【０１０３】
さらに、ステートマシンエンジン１４の各々は、ＩＲＤＶ３８２からの入力を受信し、かつ／またはＩＲＤＶ３８２の信号を制御するように構成される。例えば、一実施形態においては、「マスタ」デバイスは、ＩＲＤＶ３８２の信号を制御するように構成でき、一方で、「スレーブ」デバイスは、ＩＲＤＶ３８２からの入力を受信するように構成できる。図示する実施形態においては、ステートマシンエンジン１４Ｆ０は、ＩＲＤＶ３８２の信号を制御するように構成され、一方で、ステートマシンエンジン１４Ｆ１、Ｆ２及びＦ３は、ＩＲＤＶ３８２からの入力を受信するように構成される。ステートマシンエンジン１４Ｆ０は、ステートマシンエンジン１４Ｆ１、Ｆ２及びＦ３に提供されるデータが有効であることを示す第一の指示（例えば、論理ハイ）に信号を制御するように構成できる。さらに、ステートマシンエンジン１４Ｆ０は、ステートマシンエンジン１４Ｆ１、Ｆ２及びＦ３に提供されるデータが無効であることを示す第二の指示（例えば、論理ロウ）に信号を制御するように構成できる。ステートマシンエンジン１４の各々は、ＩＲＤＱＳ３８４及びＩＲＤＱＳ＃３８６からの入力を受信し、かつそれらに出力を提供するように構成される。さらに、ステートマシンエンジン１４の各々は、ＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６にデータを出力し、その一方で、ＩＲデータバス３７６にもデータを提供するように構成される。
【０１０４】
図１７は、ＩＲバス及びプロセスバッファインターフェイス１３６の信号のタイミング図の一実施例を図示する。特定の構成では、ＲＳＹＮＣ３８０を使用して、ステートマシンエンジン１４を同期することができる。例えば、ステートマシンエンジン１４の各々は、ステートマシンエンジン１４がＲＳＹＮＣ３８０の信号を論理ロウに駆動する（例えば、ＲＳＹＮＣ３８０を論理ロウに「引き込む」）デフォルト状態を含むことができる。プロセッサ１２は、ステートマシンエンジン１４の同期を起動するための種々の命令をステートマシンエンジン１４に提供することができる。例えば、同期を起動するための命令は、Ｍ＿ＢＡＲ、Ｉ＿ＤＡ．ＰＲＯＣＥＳＳ、Ｉ＿ＤＡ．ＰＲＯＣＥＳＳ＿ＥｏＰ、Ｉ＿ＤＡ．ＰＲＯＣＥＳＳ＿ＥｏＤ、Ｉ＿ＤＢ．ＰＲＯＣＥＳＳ、Ｉ＿ＤＢ．ＰＲＯＣＥＳＳ＿ＥｏＰ、及びＩ＿ＤＢ．ＰＲＯＣＥＳＳ＿ＥｏＤを含んでもよい。ステートマシンエンジン１４は、これらの命令のうちの１つに遭遇すると、ＲＳＹＮＣ３８０の信号の論理ロウへの駆動を停止し（例えば、ＲＳＹＮＣ３８０を「手放し」）、動作を中断する（例えば、命令の実行を継続しない）。ステートマシンエンジン１４は、ＲＳＹＮＣ３８０が論理ハイに遷移する（これは、全てのステートマシンエンジン１４がＲＳＹＮＣ３８０の信号の論理ロウへの駆動を停止した後、またはＲＳＹＮＣ３８０の「手放し」の後に起こる）、かつ／またはＩＲＤＶ３８２が論理ハイに遷移するまで、動作を中断する。ステートマシンエンジン１４は、ＲＳＹＮＣ３８０及び／またはＩＲＤＶ３８２が論理ハイであることを検出すると、同期を起動するための命令の動作を再開する。同期を起動するための命令の終了時に、ステートマシンエンジンは、ステートマシンエンジン１４がＲＳＹＮＣ３８０の信号を論理ロウに駆動する（例えば、ＲＳＹＮＣ３８０を論理ロウに「引き込む」）そのデフォルト状態に戻ることができる。
【０１０５】
そのような動作中に交換される信号の一実施形態を図１７に図示する。例えば、時点３８８に、ＲＳＹＮＣ３８０は、論理ロウから論理ハイに遷移する。そのような遷移は、全てのステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３がステートマシンエンジン１４の同期を起動するための命令を（例えば、プロセッサ１２から）受信し、全てのステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３が動作を中断し、そして全てのステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３がＲＳＹＮＣ３８０の信号の論理ロウへの駆動を停止したことを示す。この実施例においては、ステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３は、データバッファ処理命令（例えば、Ｉ＿ＤＡ．ＰＲＯＣＥＳＳ、Ｉ＿ＤＡ．ＰＲＯＣＥＳＳ＿ＥｏＰ、Ｉ＿ＤＡ．ＰＲＯＣＥＳＳ＿ＥｏＤ、Ｉ＿ＤＢ．ＰＲＯＣＥＳＳ、Ｉ＿ＤＢ．ＰＲＯＣＥＳＳ＿ＥｏＰ、及びＩ＿ＤＢ．ＰＲＯＣＥＳＳ＿ＥｏＤ）に遭遇した。時点３９０に、ＲＳＹＮＣ３８０は、論理ハイから論理ロウに遷移する。そのような遷移は、ステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３の少なくとも１つがデータバッファ処理命令を完了し、ステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３の少なくとも１つがＲＳＹＮＣ３８０を論理ロウに引き込んだことを示す。
【０１０６】
時点３９２に、ＩＲＤＶ３８２は、論理ロウから論理ハイに遷移する。そのような遷移は、「マスタ」ステートマシンエンジン１４Ｆ０から全てのステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３への有効データが、ＩＲデータバス３７６に提供され始め、その提供が「マスタ」デバイスから始まり、ランクにおける各ステートマシンエンジン１４を通して順番に（例えば、Ｆ０、Ｆ１、Ｆ２、Ｆ３）継続していることを示すものである。時点３９４に、ＩＲＤＶ３８２は、論理ハイから論理ロウに遷移する。そのような遷移は、「マスタ」ステートマシンエンジン１４Ｆ０から全てのステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３への有効データがもはやＩＲデータバス３７６に提供されていないことを示すものである。
【０１０７】
時点３９６に、「マスタ」ステートマシンエンジン１４Ｆ０が、データ（例えば、論理グループ０用に意図された第一のデータバイト）をＩＲデータバス３７６に提供し、論理ハイをＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６に出力する。その後、時点３９７に、「マスタ」ステートマシンエンジン１４Ｆ０は、データ（例えば、論理グループ１用に意図された第二のデータバイト）をＩＲデータバス３７６に提供し、論理ハイをＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６に出力する。さらに、時点３９８に、ステートマシンエンジン１４Ｆ１が、データ（例えば、論理グループ０用に意図された第一のデータバイト）をＩＲデータバス３７６に提供し、論理ハイをＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６に出力する。その後、時点３９９に、ステートマシンエンジン１４Ｆ１は、データ（例えば、論理グループ１用に意図された第二のデータバイト）をＩＲデータバス３７６に提供し、論理ハイをＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６に出力する。
【０１０８】
さらにまた、時点４００に、ステートマシンエンジン１４Ｆ２が、データ（例えば、論理グループ０用に意図された第一のデータバイト）をＩＲデータバス３７６に提供し、論理ハイをＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６に出力する。その後、時点４０１に、ステートマシンエンジン１４Ｆ２は、データ（例えば、論理グループ１用に意図された第二のデータバイト）をＩＲデータバス３７６に提供し、論理ハイをＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６に出力する。さらに、時点４０２に、ステートマシンエンジン１４Ｆ３が、データ（例えば、論理グループ０用に意図された第一のデータバイト）をＩＲデータバス３７６に提供し、論理ハイをＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６に出力する。その後、時点４０３に、ステートマシンエンジン１４Ｆ３は、データ（例えば、論理グループ１用に意図された第二のデータバイト）をＩＲデータバス３７６に提供し、論理ハイをＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６に出力する。
【０１０９】
したがって、ステートマシンエンジン１４の各々は、２バイトのデータの「バースト長」を有するデータを提供する（例えば、各ステートマシンエンジン１４は、ランクにおける次のステートマシンエンジン１４がデータを提供する前に２バイトのデータを出力する）。図示する実施形態においては、第一のデータバイトは、第一の論理グループ（論理グループ０）用に意図されたデータであり、第二のデータバイトは、第二の論理グループ（論理グループ１）用に意図されたデータである。認識できるように、「バースト長」は、他の実施形態においては異なってもよい。例えば、「バースト長」は、論理グループの数に基づいてもよいし、論理グループの数と等しくてもよいし、その他であってもよい。データがＩＲデータバス３７６に提供されたときに、ステートマシンエンジン１４は、データを受信し、ステートマシンエンジン１４用に意図されたデータを格納する。例えば、ステートマシンエンジン１４Ｆ０及びＦ１は、論理グループ０の一部であるため、ステートマシンエンジン１４のＦ０及びＦ１各々によって提供されたあらゆる第一のバイトを格納する。さらにまた、ステートマシンエンジン１４Ｆ２及びＦ３は、論理グループ１の一部であるため、ステートマシンエンジン１４のＦ２及びＦ３各々によって提供されたあらゆる第二のバイトを格納する。ある実施形態においては、ステートマシンエンジン１４の各々は、ＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６の立ち下がりエッジに基づいてデータを格納するように構成される。
【０１１０】
図示する実施形態においては、ステートマシンエンジン１４の各々は、唯一つのデータバーストを提供した。しかしながら、認識できるように、時点３９０にＲＳＹＮＣ３８０が論理ハイから論理ロウに遷移する前に、データバーストを提供する各ステートマシンエンジン１４の回転サイクルを任意の回数繰り返してもよい。ある実施形態においては、データバーストを提供する各ステートマシンエンジン１４のサイクルは、プロセッサ１２からステートマシンエンジン１４に提供される命令に基づいて繰り返すことができる。例えば、プロセッサ１２は、それぞれのステートマシンエンジン１４がＩＲデータバス３７６から格納可能なバイト数（ＣＮＴＣ）を示す指示を、ステートマシンエンジン１４の各々に提供できる。したがって、データバーストを提供する各ステートマシンエンジン１４のサイクルを、ＣＮＴＣ数と等しい回数繰り返すことができる。ある実施形態においては、ＣＮＴＣ数は、論理グループに提供される最長データグループの全長と等しくてもよい。その結果、その意図されたデータを受信するための十分なサイクルを各論理グループに与えることができる。さらに、プロセッサ１２は、それぞれのステートマシンエンジン１４が解析可能なバイト数（ＣＮＴＶ）を示す指示を、ステートマシンエンジン１４の各々に提供できる。ある実施形態においては、ＣＮＴＣ数がＣＮＴＶ数よりも大きい場合には、ステートマシンエンジン１４は、ＣＮＴＶ数を超えてＣＮＴＣ数に至るまでの受信したバイトを、無効データ（例えば、ジャンクデータ、ガベージデータなど）とみなすことができる。
【０１１１】
時点４０４に、ＲＳＹＮＣ３８０は、論理ロウから論理ハイに遷移する。そのような遷移は、全てのステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３がステートマシンエンジン１４の同期を起動するための命令を（例えば、プロセッサ１２から）受信し、全てのステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３が動作を中断し、そして全てのステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３がＲＳＹＮＣ３８０の信号の論理ロウへの駆動を停止したことを示す。この実施例においては、ステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３は、Ｍ＿ＢＡＲ命令に遭遇した。Ｍ＿ＢＡＲ命令は、さらなる命令がステートマシンエンジン１４によって実行される前に、ステートマシンエンジン１４を同期するのに使用される。時点４０５に、ＲＳＹＮＣ３８０は、論理ハイから論理ロウに遷移する。そのような遷移は、ステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３の少なくとも１つがＲＳＹＮＣ３８０を論理ロウに引き込み、ステートマシンエンジン１４が、同期され、さらなる命令の実行に進むことができることを示す。
【０１１２】
時点４０６に、ＲＳＹＮＣ３８０は、論理ロウから論理ハイに遷移する。この実施例においては、ステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３は、別のデータバッファ処理命令（例えば、Ｉ＿ＤＡ．ＰＲＯＣＥＳＳ、Ｉ＿ＤＡ．ＰＲＯＣＥＳＳ＿ＥｏＰ、Ｉ＿ＤＡ．ＰＲＯＣＥＳＳ＿ＥｏＤ、Ｉ＿ＤＢ．ＰＲＯＣＥＳＳ、Ｉ＿ＤＢ．ＰＲＯＣＥＳＳ＿ＥｏＰ、及びＩ＿ＤＢ．ＰＲＯＣＥＳＳ＿ＥｏＤ）に遭遇した。したがって、時点４０７に、ＩＲＤＶ３８２は、論理ロウから論理ハイに遷移する。そのような遷移は、「マスタ」ステートマシンエンジン１４Ｆ０から全てのステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２及びＦ３への有効データが、ＩＲデータバス３７６に提供され始め、その提供が「マスタ」デバイスから始まり、ランクにおける各ステートマシンエンジン１４を通して順番に（例えば、Ｆ０、Ｆ１、Ｆ２、Ｆ３）継続していることを示すものである。時点４０８に、「マスタ」ステートマシンエンジン１４Ｆ０は、データ（例えば、論理グループ０用に意図された第一のデータバイト）をＩＲデータバス３７６に提供し、論理ハイをＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６に出力する。その後、時点４０９に、「マスタ」ステートマシンエンジン１４Ｆ０は、データ（例えば、論理グループ１用に意図された第二のデータバイト）をＩＲデータバス３７６に提供し、論理ハイをＩＲＤＱＳ３８４及び／またはＩＲＤＱＳ＃３８６に出力する。他のステートマシンエンジン１４は、その後、時点３８８〜時点３９４に関して前述したようにＩＲデータバス３７６にデータを提供することができる。
【０１１３】
ステートマシンエンジン１４の動作中、ＲＳＹＮＣ３８０及びＩＲＤＶ３８２を使用して全てのステートマシンエンジン１４がともに同期された同期様式で、データをＩＲデータバス３７６に提供してもよい。さらに、ステートマシンエンジン１４の各々は、モジュール３４０を構成するランクにおけるデバイス内のそれ自身の位置を示す命令を格納する。それゆえ、ステートマシンエンジン１４の各々は、データ格納及びデータ出力のタイミングをとって、ＩＲデータバス３７６を使用する順序の正しいデータ転送を容易にすることができることによって、データを適切な時に提供及び格納する。認識できるように、データ転送処理中にはエラーが発生することがある。したがって、「マスタ」ステートマシンエンジン１４Ｆ０は、任意の時にＩＲＤＶ３８２を論理ロウに遷移することによって、エラーが解決するまで、ＩＲデータバス３７６へのデータ転送を停止（例えば、ブロック、ストール、遅延など）してもよい。さらにまた、ステートマシンエンジン１４Ｆ１、Ｆ２及びＦ３の任意の１つは、ＲＳＹＮＣ３８０を論理ロウに導くことによって、ＩＲデータバス３７６へのデータ転送を停止すべきであるという指示を、「マスタ」ステートマシンエンジン１４Ｆ０に提供することができる。
【０１１４】
図１８は、複数の論理グループに組織化された複数の物理的なステートマシンエンジン１４のデータバッファ１３２に格納されたデータの一実施例を図示する。具体的には、図１８は、８つの論理グループに組織化された８つのステートマシンエンジン１４（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）を有するモジュール３４０におけるＤＤＲ３インターフェイスビューの表４１０を図示する。８つの論理グループを持つそのような構成は、８つのステートマシンエンジン１４を有するモジュール３４０において最大データスループットを提供することができる。図示する実施形態においては、ステートマシンエンジン１４は、６４本のデータ線を有するＤＤＲ３バスインターフェイス１３０に結合される。したがって、８本のデータ線が各ステートマシンエンジン１４に結合される。しかしながら、本明細書に記述するのと同じ概念を、各ステートマシンエンジン１４に結合された任意の適切な数のデータ線を持つ任意の適切なＤＤＲ３バスインターフェイス１３０に適用することができる。さらにまた、本明細書に記述するのと同じ概念を、任意の適切な数のステートマシンエンジン１４を有するモジュール３４０に適用することができる。表４１０は、モジュール３４０がプロセッサ１２から受信し、ステートマシンエンジン１４の間でオフセット様式において格納するデータを図示する。モジュール３４０にデータを格納するのに、プロセッサ１２を使用してデータを再配列するのではなく、オフセット様式においてモジュール３４０を使用することによって、プロセッサ１２を他の機能の実行に自由に使用することができる。
【０１１５】
表４１０は、プロセッサ１２から６４本のデータ線に書き込む数を示す書き込みカウント列４１２、及びプロセッサ１２からバイトを受信した時に基づく、番号順における個々のバイト数を示すバイト数列４１４を含む。バイト数列４１４は、それぞれのステートマシンエンジン１４（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）のデータバッファシステム１５９に格納された具体的なバイトを示す列Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７を含む。表４１０は、バイト数列４１４に示されるバイトが格納される、データバッファシステム１５９のデータバッファＡ及びＢ１３２の各々内のアドレスを示すデータバッファアドレス列４１６、及びステートマシンエンジン１４の特定の論理グループによって処理されるデータを示すターゲット列４１８も含む。例えば、プロセッサ１２から６４本のデータ線への第一の書き込み期間（例えば、書き込みカウント列４１２における０）に、プロセッサ１２は、ＤＤＲ３アドレスバス３４２に、データバッファシステム１５９の第一のアドレスのアドレス選択（例えば、プロセッサ書き込みアドレス０）、及び対応する８バイトのデータを提供する。この結果、第一のデータバイト（例えば、０）を、第一のステートマシンエンジン１４（例えば、Ｆ０）の第一のデータバッファアドレス４１６（例えば、０）において第一のステートマシンエンジン１４（例えば、Ｆ０）に格納し、第二のデータバイト（例えば、１）を、第二のステートマシンエンジン１４（例えば、Ｆ１）の同一の第一のデータバッファアドレス４１６（例えば、０）において第二のステートマシンエンジン１４（例えば、Ｆ１）に格納し、第三のデータバイト（例えば、２）を、第三のステートマシンエンジン１４（例えば、Ｆ２）の同一の第一のデータバッファアドレス４１６（例えば、０）において第三のステートマシンエンジン１４（例えば、Ｆ２）に格納し、第四のデータバイト（例えば、３）を、第四のステートマシンエンジン１４（例えば、Ｆ３）の同一の第一のデータバッファアドレス４１６（例えば、０）において第四のステートマシンエンジン１４（例えば、Ｆ３）に格納し、第五のデータバイト（例えば、４）を、第五のステートマシンエンジン１４（例えば、Ｆ４）の同一の第一のデータバッファアドレス４１６（例えば、０）において第五のステートマシンエンジン１４（例えば、Ｆ４）に格納し、第六のデータバイト（例えば、５）を、第六のステートマシンエンジン１４（例えば、Ｆ５）の同一の第一のデータバッファアドレス４１６（例えば、０）において第六のステートマシンエンジン１４（例えば、Ｆ５）に格納し、第七のデータバイト（例えば、６）を、第七のステートマシンエンジン１４（例えば、Ｆ６）の同一の第一のデータバッファアドレス４１６（例えば、０）において第七のステートマシンエンジン１４（例えば、Ｆ６）に格納し、そして第八のデータバイト（例えば、７）を、第八のステートマシンエンジン１４（例えば、Ｆ７）の同一の第一のデータバッファアドレス４１６（例えば、０）において第八のステートマシンエンジン１４（例えば、Ｆ７）に格納することができる。
【０１１６】
別の実施例として、プロセッサ１２から６４本のデータ線への第二の書き込み期間（例えば、書き込みカウント列４１２における１）に、プロセッサ１２は、ＤＤＲ３アドレスバス３４２に、データバッファシステム１５９の第二のアドレスのアドレス選択（例えば、プロセッサ書き込みアドレス１）、及び対応する８バイトのデータを提供する。この結果、第一のデータバイト（例えば、８）を、第一のステートマシンエンジン１４（例えば、Ｆ０）の第二のデータバッファアドレス４１６（例えば、８）において第一のステートマシンエンジン１４（例えば、Ｆ０）に格納し、第二のデータバイト（例えば、９）を、第二のステートマシンエンジン１４Ｆ１の同一の第二のデータバッファアドレス４１６（例えば、８）において第二のステートマシンエンジン１４（例えば、Ｆ１）に格納し、第三のデータバイト（例えば、１０）を、第三のステートマシンエンジン１４（例えば、Ｆ２）の同一の第二のデータバッファアドレス４１６（例えば、８）において第三のステートマシンエンジン１４（例えば、Ｆ２）に格納し、第四のデータバイト（例えば、１１）を、第四のステートマシンエンジン１４（例えば、Ｆ３）の同一の第二のデータバッファアドレス４１６（例えば、８）において第四のステートマシンエンジン１４（例えば、Ｆ３）に格納し、第五のデータバイト（例えば、１２）を、第五のステートマシンエンジン１４（例えば、Ｆ４）の同一の第二のデータバッファアドレス４１６（例えば、８）において第五のステートマシンエンジン１４（例えば、Ｆ４）に格納し、第六のデータバイト（例えば、１３）を、第六のステートマシンエンジン１４（例えば、Ｆ５）の同一の第二のデータバッファアドレス４１６（例えば、８）において第六のステートマシンエンジン１４（例えば、Ｆ５）に格納し、第七のデータバイト（例えば、１４）を、第七のステートマシンエンジン１４（例えば、Ｆ６）の同一の第二のデータバッファアドレス４１６（例えば、８）において第七のステートマシンエンジン１４（例えば、Ｆ６）に格納し、そして第八のデータバイト（例えば、１５）を、第八のステートマシンエンジン１４（例えば、Ｆ７）の同一の第二のデータバッファアドレス４１６（例えば、８）において第八のステートマシンエンジン１４（例えば、Ｆ７）に格納することができる。２つの実施例に図示するように、データバッファアドレス４１６は、プロセッサ１２からの第一の書き込みとプロセッサ１２からの第二の書き込みとの間で、８（例えば、モジュール３４０のランクにおける論理グループの数と等しい数）だけ変化した。プロセッサ１２は、一連のプロセッサ１２がデータバッファシステム１５９に書き込むものとして、線形アドレスブロックへの書き込みを継続するが、データバッファアドレス４１６は、第一の論理グループ（論理グループ０）用に意図された全てのデータがモジュール３４０に提供されるまで、８ずつ自動的に増加するように継続する。図示するように、データは、同様の様式で他の論理グループにも提供される。
【０１１７】
例えば、プロセッサ１２から６４本のデータ線への５１３番目の書き込み期間（例えば、書き込みカウント列４１２における５１２）に、プロセッサ１２は、ＤＤＲ３アドレスバス３４２に、データバッファシステム１５９の第三のアドレスのアドレス選択（例えば、プロセッサ書き込みアドレス５１２）、及び対応する８バイトのデータを提供する。この結果、第一のデータバイト（例えば、４０９６）を、第一のステートマシンエンジン１４（例えば、Ｆ０）の第三のデータバッファアドレス４１６（例えば、１）において第一のステートマシンエンジン１４（例えば、Ｆ０）に格納し、第二のデータバイト（例えば、４０９７）を、第二のステートマシンエンジン１４（例えば、Ｆ１）の同一の第三のデータバッファアドレス４１６（例えば、１）において第二のステートマシンエンジン１４（例えば、Ｆ１）に格納し、第三のデータバイト（例えば、４０９８）を、第三のステートマシンエンジン１４（例えば、Ｆ２）の同一の第三のデータバッファアドレス４１６（例えば、１）において第三のステートマシンエンジン１４（例えば、Ｆ２）に格納し、第四のデータバイト（例えば、４０９９）を、第四のステートマシンエンジン１４（例えば、Ｆ３）の同一の第三のデータバッファアドレス４１６（例えば、１）において第四のステートマシンエンジン１４（例えば、Ｆ３）に格納し、第五のデータバイト（例えば、４１００）を、第五のステートマシンエンジン１４（例えば、Ｆ４）の同一の第三のデータバッファアドレス４１６（例えば、１）において第五のステートマシンエンジン１４（例えば、Ｆ４）に格納し、第六のデータバイト（例えば、４１０１）を、第六のステートマシンエンジン１４（例えば、Ｆ５）の同一の第三のデータバッファアドレス４１６（例えば、１）において第六のステートマシンエンジン１４（例えば、Ｆ５）に格納し、第七のデータバイト（例えば、４１０２）を、第七のステートマシンエンジン１４（例えば、Ｆ６）の同一の第三のデータバッファアドレス４１６（例えば、１）において第七のステートマシンエンジン１４（例えば、Ｆ６）に格納し、そして第八のデータバイト（例えば、４１０３）を、第八のステートマシンエンジン１４（例えば、Ｆ７）の同一の第三のデータバッファアドレス４１６（例えば、１）において第八のステートマシンエンジン１４（例えば、Ｆ７）に格納することができる。
【０１１８】
表４１０が、書き込みカウント列４１２からの書き込み０〜５１１の全てが第一のステートマシンエンジン１４（例えば、Ｆ０）を含む論理グループ０用に意図されたデータを含むことを示すことが留意されるべきである。さらにまた、表４１０が、書き込みカウント列４１２からの書き込み５１２〜１０２３の全てが第二のステートマシンエンジン１４（例えば、Ｆ１）を含む論理グループ１用に意図されたデータを含み、それ以降も同様であることを示すことが留意されるべきである。
【０１１９】
図１９は、複数の論理グループに組織化された複数の物理的なステートマシンエンジン１４のプロセスバッファ１３４に格納されたデータの一実施例を図示する。具体的には、図１９は、８つの論理グループに組織化された８つのステートマシンエンジン１４（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）を有するモジュール３４０におけるＩＲデータバス３７６ビューの表４２１を図示する。表４２１は、プロセッサ１２から受信した個々のバイト数を示すバイト数列４１４を含む。バイト数列４１４は、それぞれのステートマシンエンジン１４（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）のデータバッファシステム１５９に格納された具体的なバイトを示す列Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７を含む。表４２１は、バイト数列４１４に示されるバイトが格納される、データバッファシステム１５９のデータバッファＡ及びＢ１３２のいずれか内のアドレスを示すデータバッファアドレス列４１６も含む。さらにまた、表４２１は、プロセスバッファ１３４に格納された個々のバイト数を示すバイト数列４２６を含む。バイト数列４２６は、それぞれのステートマシンエンジン１４（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）のプロセスバッファ１３４に格納された具体的なバイトを示す列Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７を含む。例えば、プロセスバッファＡ行４２８は、ステートマシンエンジン１４の第一のプロセスバッファに格納された具体的なバイトを示し、プロセスバッファＢ行４３０は、ステートマシンエンジン１４の第二のプロセスバッファに格納された具体的なバイトを示す。
【０１２０】
したがって、表４２１は、データが、オフセット様式でデータバッファシステム１５９に格納され、連続した様式でプロセスバッファ１３４に提供されることを示している。例えば、ＩＲデータバス３７６における第一のデータバースト期間に、ステートマシンエンジン１４Ｆ０は、プロセッサ１２から受信したバイト０、４０９６、８１９２、１２２８８、１６３８４、２０４８０、２４５７６及び２８６７２（例えば、論理グループの各々における第一のバイト）を提供することができる。ＩＲデータバス３７６における第二のバースト期間に、ステートマシンエンジン１４Ｆ１は、プロセッサ１２から受信したバイト１、４０９７、８１９３、１２２８９、１６３８５、２０４８１、２４５７７及び２８６７３（例えば、論理グループの各々における第二のバイト）を提供することができ、それ以降も同様である。ステートマシンエンジン１４の各々は、そのステートマシンエンジンの論理グループに対応するデータバーストからのバイトを格納するように構成される。例えば、ステートマシンエンジン１４Ｆ０は、ＩＲデータバス３７６に提供される各データバーストの第一のバイトを格納するように構成され、ステートマシンエンジン１４Ｆ１は、ＩＲデータバス３７６に提供される各データバーストの第二のバイトを格納するように構成され、それ以降も同様である。したがって、データバッファシステム１５９に格納されるときにオフセット様式で格納されたデータは、各ステートマシンエンジン１４がその意図されたデータを解析のための正しい順序で受信できるように、ＩＲデータバス３７６を通じてステートマシンエンジン１４に提供される。
【０１２１】
図２０は、１つの論理グループに組織化された複数の物理的なステートマシンエンジン１４のデータバッファ１３２に格納されたデータの一実施例を図示する。具体的には、図２０は、１つの論理グループに組織化された８つのステートマシンエンジン１４（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）を有するモジュール３４０におけるＤＤＲ３インターフェイスビューの表４３２を図示する。図示するように、データは、プロセッサ１２によって提供され、ステートマシンエンジン１４（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）に格納される。全てのステートマシンエンジン１４は、単一の論理グループ（例えば、論理グループ０）の一部である。図示する実施形態においては、モジュール３４０によって受信されたデータは、データバッファシステム１５９に連続して格納される。
【０１２２】
図２１は、１つの論理グループに組織化された複数の物理的なステートマシンエンジン１４のプロセスバッファ１３４に格納されたデータの一実施例を図示する。具体的には、図２１は、１つの論理グループに組織化された８つのステートマシンエンジン１４（Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７）を有するモジュール３４０におけるＩＲデータバス３７６ビューの表４３４を図示する。ＩＲデータバス３７６における第一のデータバースト期間において、データバースト期間に８バイトが提供されるように、ステートマシンエンジン１４Ｆ０は、プロセッサ１２から受信したバイト０（例えば、論理グループにおける第一のバイト）を提供でき、ステートマシンエンジン１４Ｆ１は、プロセッサ１２から受信したバイト１（例えば、論理グループにおける第二のバイト）を提供でき、それ以降も同様である。ステートマシンエンジン１４の各々は、そのステートマシンエンジンの論理グループに対応するデータバーストからのバイトを格納するように構成される。例えば、全てのステートマシンエンジン１４Ｆ０、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６及びＦ７が、ＩＲデータバス３７６に提供される各データバーストの全てのバイトを格納するように構成される。したがって、各ステートマシンエンジン１４がパラレル解析用の全てのデータを受信できるように、データバッファシステム１５９に格納される全てのデータが、ＩＲデータバス３７６を通じてステートマシンエンジン１４に提供される。認識できるように、図１８〜図２１は、４Ｋバイトを有するバッファを図示するが、他の実施形態では、任意の適切なサイズ（例えば、８Ｋバイト、１６Ｋバイト、３２Ｋバイト、６４Ｋバイトなど）を有するバッファを含んでもよい。
【０１２３】
本明細書中に使用されるような、装置という用語は、単一モジュールであってもよいし、１つ以上のモジュールを含むシステムであってもよい。本発明は、種々の変更及び代替形態を受け入れることができるが、特定の実施形態を、図面に例証として示し、本明細書に詳細に記述した。しかしながら、本発明が、開示した特定の形態に限定されないことを意図することが理解されるはずである。むしろ、本発明は、以下の添付の特許請求の範囲によって定義されるような本発明の精神及び範囲内に収まる全ての変更、均等物及び代替手段を包含することができる。
【図６】
2016515266.tif 000004
【図１】
2016515266.tif 000005
【図２】
2016515266.tif 000006
【図３】
2016515266.tif 000007
【図４】
2016515266.tif 000008
【図５】
2016515266.tif 000009
【図７】
2016515266.tif 000010
【図８】
2016515266.tif 000011
【図９】
2016515266.tif 000012
【図１０】
2016515266.tif 000013
【図１１】
2016515266.tif 000014
【図１２】
2016515266.tif 000015
【図１３】
2016515266.tif 000016
【図１４】
2016515266.tif 000017
【図１５】
2016515266.tif 000018
【図１６】
2016515266.tif 000019
【図１７】
2016515266.tif 000020
【図１８】
2016515266.tif 000021
【図１９】
2016515266.tif 000022
【図２０】
2016515266.tif 000023
【図２１】
2016515266.tif 000024
【国際調査報告】
2016515266.tif 000025
2016515266.tif 000026