仮想化超並列プログラマブルハードウェアによる正規表現の検索
プログラマブルハードウェアデバイスでの実行に適切な論理および状態情報は、コーパスに対して正規表現を評価するように、タスクから生成することができる。プログラマブルハードウェアデバイスでの論理および状態情報のハードウェア容量の要件を推定することができる。推定されると、複数のタスクから生成された複数の論理および状態情報は、各セットの論理および状態情報がプログラマブルハードウェアデバイスのハードウェア容量内に収まるように、セットに配分することができる。各セット内のタスクは、プログラマブルハードウェアデバイスで並列に実行するように構成することができる。次いで、セットは順次に実行されてもよく、リソースの仮想化が可能になる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想化超並列プログラマブルハードウェアによる正規表現の検索に関する。
【背景技術】
【０００２】
正規表現検索は、電子メールスパムフィルタリングおよびネットワーク侵入検出から一般的な調査に至るまで、多種多様なアプリケーションに共通する操作である。正規表現（「ｒｅｇ ｅｘ」または「ＲＥ」）は、特定の文字、単語、または文字のパターンのような、関心対象のストリングを識別するための簡潔で柔軟な手段をもたらす。たとえば、テキストファイルを解析する場合の「＊ｃａｒ＊」の正規表現は、「ｃａｒ」、「ｃａｒｔｏｏｎ」、「ｖｉｃａｒ」などを識別することができる。
【０００３】
従来より、ｒｅｇ ｅｘｓは、ソフトウェアベースまたはハードウェアベースの検索ソリューションを使用して実行されてきた。残念なことに、それらのソリューションは、膨大な数の複合検索を実行する場合には問題に遭遇する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ソフトウェアベースの検索では、スループットに関連する根本的な問題が生じる。プロセッサベースのシステムは、原則的に任意の複合検索を大量に実行できるその柔軟性ゆえに普及しているが、その速度は、検索の数および複雑さが増大するにつれて低下し一貫性を失う。言い換えれば、膨大量のデータ（「コーパス」）でのｒｅｇ ｅｘ検索は、実際的ではない。
【０００５】
一方、既存のハードウェアベースの検索ソリューションは、適応能力に根本的な問題がある。これらのシステムは、システム自体にマップすることができる検索に対しては高速で一貫性のあるパフォーマンスを備えることができるが、既存のデバイスには、詳細な専門知識と手操作による介入なしでサポート可能な検索の数および複雑さに関して厳しい制限がある。言い換えれば、ハードウェア検索は高速であるが、制限されている。
【０００６】
したがって、正規表現検索のようなアルゴリズムのハードウェアベースの処理に、ソフトウェアと同様の柔軟性をもたらすことを求める切迫した需要がある。
【課題を解決するための手段】
【０００７】
この課題を解決するための手段は、後段の発明を実施するための形態においてさらに説明される一連の概念を簡略化された形態で示すために提供される。この課題を解決するための手段は、請求項に係る主題の重要な特徴または基本的特徴を特定することを意図するものではなく、また請求項に係る主題の範囲を限定するために使用されることを意図するものでもない。
【０００８】
正規表現を含む（ただし、これに限定されることはない）計算タスクは、対応する論理および状態方程式に変換することができる。論理および状態方程式を実行するためにどのくらいのプログラマブルハードウェアデバイスが必要であるかなど、物理リソース要件は、コンピュータ支援設計（ＣＡＤ）ツールを通じて反復の試行錯誤を行なうことなく推定されてもよい。推定された後、計算タスクはセットに配分されてもよく、そこで各セットは個々の使用可能な物理リソース内に収まる。たとえば、計算タスクのセットは、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）のような、プログラマブルハードウェアデバイスに収まることができる。制御および通信論理が各セットに追加されてもよく、ハードウェア定義言語（ＨＤＬ）ファイルは、各セットに対して生成される。複数のＨＤＬファイルにわたる計算タスクの分割方法、ＨＤＬファイルの実行シーケンスなどを詳述する構成仕様も生成されてもよい。各ＨＤＬファイルから、構成バイナリが生成されてもよい。次いで、プログラマブルハードウェアデバイスは、構成バイナリを実行する。
【０００９】
ユーザインターフェイスは、ユーザを、タスク管理の複雑さ、構成バイナリの作成、構成バイナリにわたる計算タスクの配分などから隔離する。プログラマブルハードウェアの速度および再構成可能性を併せ持つ簡単なユーザインターフェイスは、正規表現検索の実際の実施および実行をユーザに意識させないようにする。プログラマブルハードウェアの面倒な手操作による構成に代わって、自動化システムは、ユーザのために構成バイナリを生成し、それらを実行して、結果の整理統合を管理する。
【００１０】
信頼性を向上させるためのフォールトトレランスのサポートは、再配分、スペアリングなどを含む。パフォーマンスの向上は、フラグメンテーションの緩和および優先順位付けを通じて可能となる。
【図面の簡単な説明】
【００１１】
詳細な説明は、添付の図面を参照して示される。図面において、参照番号の左端の数字（複数可）は、参照番号が最初に出現する図面を識別する。異なる図面において同じ参照番号が使用される場合、それは類似または同一の項目を指示する。
【００１２】
【図１】正規表現処理システムの保持に適したアーキテクチャの選択されたコンポーネントを示すブロック図である。
【図２】図１から選択されたコンパイルモジュールのコンポーネント、およびコンパイルモジュールにより生成されうる構成情報を示すブロック図である。
【図３】図１のアーキテクチャにより生成される構成バイナリの選択されたコンポーネントを示すブロック図である。
【図４】図１のアーキテクチャにより生成される構成仕様の選択されたコンポーネントを示すブロック図である。
【図５】図１のアーキテクチャから選択されたプログラマブルハードウェアシステムコントローラ（ＰＨＳＣ）のコンポーネントを示すブロック図である。
【図６】ＰＨＳＣによる構成バイナリの実行を示す流れ図である。
【図７】構成バイナリからの状態情報の格納を含む、ＰＨＳＣによる構成バイナリの実行を示す流れ図である。
【図８】正規表現処理システムとのユーザ対話を示す流れ図である。
【図９】正規表現に基づく構成情報の生成を示す流れ図である。
【図１０】正規表現のセットに対する物理リソース要件の推定を示す流れ図である。
【図１１】プログラマブルハードウェアにおける生成された構成の実行を示す流れ図である。
【図１２】正規表現の動的な変更を示す流れ図である。
【図１３】残りの機能可能なプログラマブルハードウェアデバイスに構成バイナリを再配分することによるフォールトトレランスのサポートを示す流れ図である。
【図１４】残りの機能可能なプログラマブルハードウェアデバイスに構成バイナリを再配分することによるフォールトトレランスのサポートを示す流れ図である。
【図１５】残りの機能可能なプログラマブルハードウェアデバイスに構成バイナリを再配分することによるフォールトトレランスのサポートを示す流れ図である。
【図１６】予備の機能可能なプログラマブルハードウェアデバイスの使用を介するフォールトトレランスのサポートを示す流れ図である。
【図１７】予備の機能可能なプログラマブルハードウェアデバイスの使用を介するフォールトトレランスのサポートを示す流れ図である。
【図１８】予備の機能可能なプログラマブルハードウェアデバイスの使用を介するフォールトトレランスのサポートを示す流れ図である。
【図１９】構成バイナリにわたる正規表現のフラグメンテーション緩和を示す概略図である。
【図２０】コンパイルリソースが制限されている場合のような、正規表現の一部および対応する構成バイナリの選択的な再コンパイルによるフラグメンテーション緩和を示す概略図である。
【図２１】正規表現の優先度を認識するハードウェア割り当て、ならびにそれらの正規表現の構成バイナリへのパッキングおよびスケジューリングを示す概略図である。
【図２２】構成バイナリの実行を再配分することによるアイドルプログラマブルハードウェアリソースの再利用を示す流れ図である。
【図２３】構成バイナリおよびその内部の正規表現の優先順位付けを示す流れ図である。
【図２４】構成バイナリおよびその内部の正規表現の優先順位付けを示す流れ図である。
【図２５】コンパイルおよび実行における複数のユーザ／アプリケーションによる正規表現のマージを示す流れ図である。
【図２６】構成バイナリの遅延構成ページングを示す流れ図である。
【図２７】後に完全な構成バイナリを作成するよう結合されうる構成バイナリサブエレメントのコンパイルを示す流れ図である。
【図２８】正規表現を結合する計算を示す概略図である。
【図２９】重複するかまたは類似する部分を有する正規表現のスーパーセットを示す概略図である。
【発明を実施するための形態】
【００１３】
正規表現（「ｒｅｇ ｅｘ」または「ＲＥ」）は、特定の文字、単語、または文字のパターンのような、関心対象のストリングを識別するための簡潔で柔軟な手段をもたらす。たとえば、テキストファイルを解析する場合の「＊ｃａｒ＊」の正規表現は、「ｃａｒ」、「ｃａｒｔｏｏｎ」、「ｖｉｃａｒ」などの単語を識別することができる。
【００１４】
正規表現検索は、要求していない広告電子メール（「スパム」）フィルタリングから一般的な調査に至るまで、多種多様な分野において幅広く使用される。たとえば、電子メールサーバは、所与の電子メールがスパムであるかどうかを決定するために、「ｍｏｒｔｇａｇｅ」または「ｃｒｅｄｉｔ ｃａｒｄ」または「ｅｎｈａｎｃｅｍｅｎｔ」の出現をすべて検索することができる。もう１つの例において、医師は、癌の素因を指示する「ＧＧＣＣＣＡＧＣＡＴＡＧＡＴＴＡＣＡ」という配列を見つけるために患者のＤＮＡを調べることができる。したがって、ｒｅｇ ｅｘは、多くの用途において有用なツールである。残念なことに、前述のように、ｒｅｇ ｅｘを実施する従来の方法には、ソフトウェアにおいては遅い速度、またはハードウェアにおいては処理されるｒｅｇ ｅｘの変化に対して適応能力が限られているという深刻な欠点があった。
【００１５】
本開示において、正規表現は、プログラマブルハードウェアデバイスで実行するための対応する論理および状態方程式に自動的に変換される。この自動変換のプロセスの一環として、各正規表現を実行するために必要なプログラマブルハードウェアのサイズは、厄介な試行錯誤を行なうことなく推定されてもよい。一部の実施形態において、コンパイルレポートから派生したフィードバックを使用する、および実際のリソース利用率を使用して構成を変更するなどのような、自動制御の下で試行錯誤が使用されてもよい。推定された後、正規表現はセットに配分されてもよく、そこで各セットは個々のプログラマブルハードウェアデバイスの物理リソースの制約の範囲内に収まる。たとえば、５００の正規表現のセットは、特定のＦＰＧＡ内に収めることができる。
【００１６】
通信および制御（ＣＣ）論理は各セットに追加されてもよく、それによりプログラマブルハードウェアがコントローラと通信して、プログラマブルハードウェアでの実行を管理することができるようになる。プログラマブルハードウェアは、イーサネット（登録商標）のようなデータネットワーク、ＰＣＩ（ｐｅｒｉｐｈｅｒａｌ ｃｏｍｐｏｎｅｎｔ ｉｎｔｅｒｃｏｎｎｅｃｔ）のような入出力バスインターフェイス、またはＨｙｐｅｒＴｒａｎｓｐｏｒｔコンソーシアムにより記述されているＨｙｐｅｒＴｒａｎｓｐｏｒｔ（商標）のような中央演算処理装置バスベースのインターフェイスを介してコントローラと通信することができる。コンパイラは、各セットに対して、正規表現およびＣＣ論理を含むハードウェア定義言語（ＨＤＬ）ファイルを生成する。コンパイラはまた、複数のＨＤＬファイルにわたる正規表現の配分、実行シーケンスなどを詳述する構成仕様も生成することができる。ＣＡＤツールは、各ＨＤＬファイルから構成バイナリを生成することができる。次いで、プログラマブルハードウェアデバイスは、構成バイナリを実行することができる。
【００１７】
実行中、各プログラマブルハードウェアデバイス内の正規表現は並列で実行するので、大幅な速度の増大をもたらす。たとえば、特定のＦＰＧＡ内に収まる前述の５００の正規表現のセットは、ＦＰＧＡ内で並列に実行される。
【００１８】
（構成バイナリの形態の）異なるセットは、プログラマブルハードウェアデバイスで順次にロードされて実行される。それにより、使用可能なプログラマブルハードウェアの容量を通常であれば超えるであろう正規表現検索を行なうことが可能になる。たとえば、前述の第１のセットは５００の正規表現を有するが、第２のセットは３００の正規表現を有する。合わせると、それらの８００の正規表現は、単一のプログラマブルハードウェアデバイスにとっては大量過ぎる。しかし、２つの構成バイナリに分割して、順次に実行される場合、単一のプログラマブルハードウェアデバイスは、８００の正規表現全体を実行することができる。
【００１９】
ユーザインターフェイスは、ユーザが、タスク管理の複雑さ、構成バイナリの作成、構成バイナリにわたる配分などを見なくてすむようにする。この簡単なユーザインターフェイスにより、プログラマブルハードウェアの速度および再構成可能性を活用して、正規表現をデータのコーパスと比較するような計算タスクの実行の大幅な増大をもたらすことができる。
【００２０】
プログラマブルハードウェアを使用してｒｅｇ ｅｘを実行することは、２つの利点をもたらす。第１は、プログラマブルハードウェアによって提供される並列操作により、システムの容量が、プログラマブルハードウェアデバイス自体の容量と相関することである。したがって、プログラマブルハードウェアベースのソリューションが、別の構成バイナリを実行シーケンスに追加する必要が生じるまで、一定のスループットを備えることが可能である。たとえば、ＦＰＧＡ内に収まりうる３００の表現によるセットは、同じＦＰＧＡに収まる上記の５００の表現と同時に実行する。これは、３００の表現の場合よりも５００の表現のほうが評価に多くの時間を要するように、パフォーマンスが所望の検索の数に関して線形に低下（または悪化）するソフトウェアのソリューションとは対照的である。
【００２１】
プログラマブルハードウェアベースの正規表現検索がもたらす第２の利点は、プログラマブルハードウェアで構成される回路が確定的パフォーマンスを提供することである。前述のように、プログラマブルハードウェアデバイス内に収まるように構成された正規表現のセットは、既知の時間で実行する。これとは対照的に、プロセッサで稼働しているソフトウェアのスループットは、所望される検索の特性（多少複雑な検索）および入力データの特性（低いヒット率の入力ストリームに対する高いヒット率の入力ストリーム）によって異なる可能性がある。加えて、キャッシュミスのような、その他の予測不能なイベントがパフォーマンスに変化をもたらすことがある。
【００２２】
再配分、スペアリングなどが、フォールトトレランスを可能にする。パフォーマンスは、選択的または完全な再コンパイルを通じた取り消しまたは変更から正規表現のフラグメンテーションを緩和することにより保持される。正規表現はまた、パッキング、スケジューリング、および実行順序付けを通じてさまざまに変化する優先度レベルを割り当てられてもよい。
【００２３】
例示のアーキテクチャ
図１は、正規表現処理システム１０２の実施に適したアーキテクチャの選択されたコンポーネントを示すブロック図１００である。限定の目的ではなく説明のために、会社が、一般に「スパム」として知られる要求していない広告電子メールをその電子メールサーバからフィルタリングしようとしていると仮定する。スパムに関連付けられていたストリングを組み入れる正規表現のセットが保持される。たとえば、「ｍｏｒｔｇａｇｅ ｒａｔｅ」および「ｃｒｅｄｉｔ ｃａｒｄ」といった語句は、スパム電子メールを指示すると決定されている。システムアドミニストレータまたはスパムユーティリティアプリケーションは、それらの語句に対する正規表現を生成する。
【００２４】
会社のサーバでの電子メールの収集は、潜在的なスパムを除去するために正規表現（ｒｅｇ ｅｘ）のこのリストを使用してフィルタされるデータのコーパスを形成する。実際には、そのようなｒｅｇ ｅｘのリストは、数千から数百万にさえも及ぶことがある。現在のソフトウェアのみの正規表現検索に必要とされる計算要件を考えれば、これは重大なサーバの負荷をもたらし、それに応じてタスク、出力、冷却などに割り振られるサーバのようなリソース要件の増大もまねく。
【００２５】
正規表現処理システム１０２内には、メモリ１０６に格納されているモジュールを実行するように構成されたプロセッサ１０４があってもよい。一部の実施形態において、プロセッサ１０４は、多重コアプロセッサ、または複数プロセッサの集合であってもよい。正規表現処理システム内にはまた、メモリ１０６があってもよい。メモリ１０６は、正規表現１０８（１）、１０８（２）、．．．、１０８（Ｒ）を格納することができる。本出願の図１から図２９において使用される、「（Ｒ）」または「（Ｐ）」のような括弧で囲まれた文字は、ゼロよりも大きい任意の整数を示す。これらの正規表現は、それらを表すブロックの可変サイズによって指示されるように、さまざまなサイズおよび／または複雑さであってもよい。
【００２６】
また、メモリ１０６内には、正規表現を受け入れて、同様にメモリ１０６にあるコンパイルモジュール１１２により処理するためにそれらの正規表現を搬送するように構成されたユーザインターフェイス１１０もある。コンパイルモジュール１１２は、プログラマブルハードウェアでのロードおよび実行に適した構成情報を生成するように構成され、後段で図２に関してさらに詳細に説明される。
【００２７】
コンパイルモジュール１１２は、プログラマブルハードウェアシステムコントローラ（ＰＨＳＣ）１１４と通信し、メモリ１０６に格納されてもよい。ＰＨＳＣ１１４は、プログラマブルハードウェアの操作を管理するように構成され、後段で図５に関してさらに詳細に説明される。ＰＨＳＣ１１４は、ソフトウェアモジュールとして（示されるように）、ハードウェアデバイスとして、または組み合わせとして実行されてもよい。
【００２８】
ＰＨＳＣ１１４はまた、処理のためにメモリ１０６内のコーパスデータ１１６またはその他の外部データを受け入れるように構成される。一部の実施態様において、このコーパスデータは、正規表現が実行されるべき情報を含むことができる。たとえば、正規表現として表されるスパム語句が検索される電子メールメッセージの集合。
【００２９】
ＰＨＳＣ１１４は、プログラマブルハードウェア１１８（１）、１１８（２）、．．．、１１８（Ｐ）と通信する。プログラマブルハードウェア１１８は、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、複合プログラマブル論理デバイス（ＣＰＬＤ：ｃｏｍｐｌｅｘ ｐｒｏｇｒａｍｍａｂｌｅ ｌｏｇｉｃ ｄｅｖｉｃｅ）、またはその他の再構成可能なハードウェアデバイスであってもよい。プログラマブルハードウェア１１８は、（同じ製造業者による同じモデルのＦＰＧＡのように）類似していても、（異なる製造業者によるＦＰＧＡのように）異なっていてもよい。各プログラマブルハードウェア１１８内には、正規表現１０８（１）〜（Ｒ）のプログラマブルハードウェア内の物理的な具現ならびに任意の必須の通信および制御（ＣＣ）論理である１つまたは複数の計算論理ブロック１２０（１）、１２０（２）、．．．、１２０（Ｌ）があってもよい。
【００３０】
ＰＨＳＣ１１４は、計算論理１２０を作成するプログラマブルハードウェア１１８に構成をロードする。計算論理１２０が実行した後、プログラマブルハードウェア１１８内のＣＣ論理は、その結果をＰＨＳＣ１１４に転送することができ、次いでＰＨＳＣ１１４は結果１２２をメモリ１０６またはその他の外部データ宛先に出力することができる。プログラマブルハードウェアデバイス１１８で実行するための構成に含まれてはいない正規表現１０８は、補助の正規表現処理モジュール１２４において実行されてもよい。たとえば、新しく追加されたスパム語句「ｒｏｏｆｉｎｇ ｒｅｐａｉｒ」は、正規表現のリストに追加されてもよいが、ハードウェア実行のために構成バイナリにコンパイルされなくてもよい。コンパイルされるまで、この新しく追加されたスパム語句の正規表現は、補助の正規表現処理モジュール１２４を使用して処理されてもよい。補助の正規表現処理モジュール１２４は、メモリ１０６に格納されてもよく、コンパイルモジュール１１２およびＰＨＳＣ１１４と通信してもよい。
【００３１】
並列に正規表現を実行するように構成されたプログラマブルハードウェア１１８のパフォーマンスの利点を考えれば、プログラマブルハードウェア１１８は、課せられた要求をゆうに超えることができる。その結果、プログラマブルハードウェア１１８が十分に活用されない場合もある。プログラマブルハードウェア１１８を動的に再構成することにより、過剰なパフォーマンスと交換に仮想容量を提供することが可能になる。その結果、より小さいプログラマブルハードウェアデバイスが使用されてもよい。または、単一のプログラマブルハードウェアがもはやｒｅｇ ｅｘ１０８（１）〜１０８（Ｒ）のすべてを含むことができなくなるところまで要求が高まる場合、ｒｅｇ ｅｘは複数の計算論路１２０（１）〜１２０（Ｌ）を作成するように分割され、逐次ロードされて実行されてもよい。計算論理の逐次実行は若干遅いが、プログラマブルハードウェア１１８の容量を超える計算論理をロードする場合に生じるであろう完全故障をはるかにしのぐ。
【００３２】
正規表現処理システム１０２はまた、サーバ、ワークステーション、ネットワーク接続ＦＰＧＡデバイスなどのような他のデバイスと通信するように構成可能なネットワークインターフェイス１２６を組み入れることもできる。
【００３３】
図２は、図１から選択されたコンパイルモジュール１１２のコンポーネントを示すブロック図２００である。正規表現１０８（１）〜１８０（Ｒ）は、ユーザインターフェイス１１０などを介して、コンパイルモジュール１１２に提供される。コンパイルモジュール１１２は、正規表現を、プログラマブルハードウェア１１８により実行可能な形態にコンパイルするように構成される。正規表現−ハードウェア定義言語（ＨＤＬ）コンパイラ２０２は、正規表現１０８のＨＤＬ表現を生成する。
【００３４】
ハードウェア定義言語（ハードウェア記述言語としても知られる）は、計算を実行するように構成されたデジタル論理および電子回路の記述を表す。コンピュータコードがアルゴリズムを表す場合、ＨＤＬステートメントは実際の回路素子を表す。
【００３５】
米国電気電子学会（ＩＥＥＥ）規格ＩＥＥＥ１０７６によって説明されるように、１つのＨＤＬは、超高速集積回路ハードウェア記述言語（ＶＨＤＬ）である。もう１つのＨＤＬは、ＩＥＥＥ規格１３６４−２００１に説明されているＶｅｒｉｌｏｇである。その他のＨＤＬも使用可能であり、同様に使用されてもよい。
【００３６】
正規表現−ＨＤＬコンパイラ２０２がｒｅｇ ｅｘ１０８をコンパイルしてＨＤＬファイルを生成すると、構成仕様２０４（１）、２０４（２）、．．．、２０４（Ｓ）は、コンパイルの結果得られた情報に基づいて生成されてもよい。構成仕様は、構成バイナリにわたり配分されるｒｅｇ ｅｘ１０８の数などのような詳細を含み、後段で図４に関してさらに詳細に説明される。
【００３７】
コンパイラ２０２は、ＨＤＬファイル２０６を、プログラマブルハードウェアのコンピュータ支援設計（ＣＡＤ）ツール２０８に提供する。このＣＡＤツール２０８は、ＨＤＬファイル２０６を受け入れ、プログラマブルハードウェアデバイス１１８による実行に適した構成バイナリ２１０（１）、２１０（２）、．．．、２１０（Ｂ）を生成する。参照を簡単にするために、構成仕様２０４および構成バイナリ２１０は、構成情報２１２とみなされてもよい。１つの実施態様において、複数の構成バイナリ２１０（１）〜２１０（Ｂ）に関連する単一の構成仕様２０４が生成されてもよい。もう１つの実施態様において、複数の構成仕様２０４（１）〜２０４（Ｓ）は、複数の構成バイナリ２１０（１）〜２１０（Ｂ）に対応して生成されてもよい。一部の実施態様において、構成情報２１２（１）、２１２（２）、．．．、２１２（Ｆ）があってもよい。
【００３８】
図３は、図１のアーキテクチャにより生成される例示の構成バイナリの選択されたコンポーネントを示すブロック図３００である。この図において、破線３０２は、プログラマブルハードウェア１１８の容量の輪郭を描いている。構成バイナリ２１０内、およびこの容量３０２内には、コンパイルモジュール１１２によって生成されたバイナリ構成命令のような、バイナリ構成命令３０４として表現されるｒｅｇ ｅｘがあってもよい。さらに、構成バイナリ２１０に含まれるのは、ＰＨＳＣ１１４とプログラマブルハードウェアデバイス１１８との結合を可能にするように構成された通信および制御（ＣＣ）論理３０６であってもよい。一部の実施態様において、ローカル状態ストレージ３０８もまた、構成バイナリ２１０内に提供されてもよい。
【００３９】
この図において、構成バイナリ２１０（１）は、ｒｅｇ ｅｘ１０８（１）、１０８（２）、１０８（６）、およびＣＣ３０６（１）を含む。構成バイナリ２１０（２）は、ｒｅｇ ｅｘ１０８（３）、１０８（４）、およびＣＣ３０６（２）を含む。構成バイナリ２１０（３）は、ｒｅｇ ｅｘ１０８（５）、ローカル状態ストレージ３０８（１）、およびＣＣ３０６（３）を含む。ｒｅｇ ｅｘは、内部の正規表現のサイズ／複雑さの相違を示すように、異なる幅で表されていることに留意されたい。したがって、ｒｅｇ ｅｘ１０８（５）は、使用可能な計算論理容量のほとんどを必要とするので、構成バイナリ２１０（３）内の唯一のｒｅｇ ｅｘである。
【００４０】
各構成バイナリ２１０は、内部のｒｅｇ ｅｘが並列実行のために設計されるように構成されてもよい３１０。たとえば、構成バイナリ２１０（１）がプログラマブルハードウェア１１８において実行されると、ｒｅｇ ｅｘ１０８１０８（１）、１０８（２）、および１０８（６）が並列に実行される。ハードウェアにおいて複数のｒｅｇ ｅｘを並列に実行できるこの機能は、結果として単一プロセッサ上で順次に実行するソフトウェアにまさる重大な速度の増加をもたらす。図１の例に戻ると、プログラマブルハードウェア１１８による構成バイナリ２１０（１）の実行は、ソフトウェアで行なわれる逐次処理とは対照的に、３つのｒｅｇ ｅｘの検索を一度に行なう。
【００４１】
図４は、図１のアーキテクチャにより生成される構成仕様２０４の選択されたコンポーネントを示すブロック図４００である。構成仕様２０４は、複数の情報を含むことができる。生成される構成バイナリ４０２（１）のカウントは、格納されてもよい。たとえば、コンパイルされた正規表現は、３つの構成バイナリを生成する。構成バイナリ間の正規表現の配分の記述４０２（２）もまた、格納されてもよい。たとえば、これは、ｒｅｇ ｅｘ１０８（１）、１０８（２）、および１０８（６）が構成バイナリ２１０（１）内にあることを指示することができる。構成バイナリ４０２（３）の実行のシーケンスが含まれてもよい。たとえば、構成バイナリ２１０（１）を最初に実行し、続いて２１０（３）、次いで２１０（２）が実行して、特定の正規表現の優先順位付けを説明する。以下の図２１では、優先順位付けをさらに詳細に説明する。構成仕様２０４（１）はまた、どの許可または「正当な」プログラマブルハードウェアデバイス１１８が正規表現処理システム１０２内にあるのかを含むこともできる。たとえば、現在システム内で使用可能なプログラマブルハードウェアデバイスは、製造業者ＸによるＦＰＧＡタイプＡおよびＢ、ならびに製造業者ＹによるＦＰＧＡタイプＣを含む。コンパイル日付／時間、アプリケーション識別および／またはユーザ識別などのような、その他の情報４０２（Ｙ）もまた、構成仕様２０４（１）に含まれてもよい。
【００４２】
図５は、図１のアーキテクチャから選択されたプログラマブルハードウェアシステムコントローラ（ＰＨＳＣ）のコンポーネントを示すブロック図５００である。この図において、ＰＨＳＣ１１４は、構成仕様２０４（１）および対応する構成バイナリ２１０（１）〜２１０（３）を、コーパスデータ１１６と共に受け入れる。たとえば、構成仕様は、スパム検索のために正規表現１０８（１）〜１０８（Ｒ）に対応する表現を含むことができるが、コーパスは、スパムがないかどうか確認される電子メールストアを含むことができる。
【００４３】
ＰＨＳＣ１１４は、入力を受信して、結果１２２を提供することを含む、ＰＨＳＣ１１４のアクションを協調するように構成された制御モジュール５０２を含むことができる。プログラマブルハードウェアデバイス１１８と通信して、構成バイナリのロードおよびアンロード、結果１２２の転送などのようなタスクを管理するように構成されたプログラマブルハードウェアインターフェイスモジュール５０４もまた、ＰＨＳＣ１１４に含まれてもよい。構成バイナリ順序付けモジュール５０６もまた存在してもよい。構成バイナリ順序付けモジュール５０６は、プログラマブルハードウェア１１８内の構成バイナリ２１０の処理のための実行シーケンス５０８（この説明図において破線で示される）を決定することができる。たとえば、実行シーケンス５０８は、構成バイナリ２１０（１）、構成バイナリ２１０（２）、次いで構成バイナリ２１０（３）が続いてもよい。実行シーケンス５０８は、構成仕様２０４からの構成バイナリ４０２（３）の実行のシーケンスに基づいてもよい。一部の実施態様において、実行シーケンス５０８は、優先度の変更、ハードウェアが使用できないこと、処理ロード、およびＰＨＳＣ１１４に使用可能なその他の因子により、実行のシーケンス４０２（３）とは異なっていてもよい。
【００４４】
例示の実行
図６は、プログラマブルハードウェア１１８でのＰＨＳＣ１１４による構成バイナリの実行を示す流れ図６００である。この例の場合、単一のプログラマブルハードウェアデバイス１１８（１）があり、矢印６０２により指示されるようにページを下方に進むと時間が増大すると仮定する。ｒｅｇ ｅｘ１０８（１）〜１０８（Ｒ）はコンパイルされて構成バイナリ２１０（１）〜２１０（Ｂ）を形成し、構成バイナリ２１０（１）〜２１０（Ｂ）のロードおよび構成が行なわれるとプログラマブルハードウェアデバイス１１８は計算論理１２０となる。プログラマブルハードウェア１１８（１）にロードされると、計算論理１２０は、６０４内部で符号化された正規表現検索を並列に実行する。構成バイナリのシーケンスは、１つずつ構成バイナリが次々と６０６で順次にロードされ処理される。
【００４５】
たとえば、６０８において、ＰＨＳＣ１１４のプログラマブルハードウェアインターフェイスモジュール（ＰＨＩＭ）５０４は、構成バイナリ２１０（１）をプログラマブルハードウェア１１８（１）にロードする。ロードされると、プログラマブルハードウェア１１８（１）内で結果として得られる回路の物理的配列は、計算論理１２０（１）である。計算論理１２０（１）は実行し、その結果はＰＨＩＭ５０４に渡される。
【００４６】
６１０において、ＰＨＩＭ５０４は、ＰＨＳＣ１１４の実行シーケンス５０８で次の順位にあった構成バイナリ２１０（２）を、計算論理１２０（２）を形成するプログラマブルハードウェア１１８（１）にロードする。計算論理１２０（２）は実行し、その結果はＰＨＩＭ５０４に返される。
【００４７】
６１２において、ＰＨＩＭ５０４は、ＰＨＳＣ１１４の実行シーケンス５０８で次の順位にあった構成バイナリ２１０（３）を、計算論理１２０（３）を形成するプログラマブルハードウェア１１８（１）にロードする。計算論理１２０（３）は実行し、その結果はＰＨＩＭ５０４に返される。
【００４８】
このように連続的に構成バイナリをロードして結果の計算論理を実行することにより、プログラマブルハードウェアの仮想化が可能になり、仮想化計算ファブリックを作成することができる。たとえば、処理されるべきすべての正規表現を実行するのに十分な大きさのプログラマブルハードウェア１１８を個々に必要とするのではなく、ｒｅｇ ｅｘは１つまたは複数のプログラマブルハードウェアデバイス１１８にわたり実行するように分割されてもよい。使用可能なプログラマブルハードウェアデバイスが十分ではなく、同時操作ができない場合（たとえば、ｒｅｇ ｅｘの要求がプログラマブルハードウェアデバイスの使用可能容量を超える場合）、ｒｅｇ ｅｘは複数の構成バイナリにわたり配分されてもよく、次いで限られた数のプログラマブルハードウェア１１８にわたり配分されてもよい、および／または同じプログラマブルハードウェア１１８で順次に実行されてもよい。スパム検索のための８００の正規表現に関する前述の例に戻ると、８００すべてが単一のＦＰＧＡに収まるわけではないが、５００は収まる。したがって、第１の構成バイナリは５００の正規表現で作成されるが、第２の構成バイナリは残りの３００の正規表現で作成される。１つのプログラマブルハードウェア１１８デバイスが使用可能であるので、第１の構成バイナリがロードされて実行され、次いで第２の構成バイナリがロードされて実行される。
【００４９】
パフォーマンスを向上させるため、および／または一連の構成バイナリが先行のステップの結果に基づいて反復して実行できる（すなわち、パイプライン制御される）ようにするため、状態情報が格納されてもよい。図７は、構成バイナリからの状態情報の格納を伴う、ＰＨＳＣ１１４による構成バイナリの実行を示す流れ図７００である。上記で図６に関して説明されたとおり、矢印７０２により指示されるようにページを下方に進むと時間が増大する。また上記のように、この例において、構成バイナリから結果として得られた計算論理に表される正規表現は並列に実行され７０４、複数の構成バイナリは、単一のプログラマブルハードウェア１１８（１）で逐次ロードされ実行される７０６。計算論理に接続されたローカルメモリは、７０８において、または計算論理内で具現されるもう１つの実施態様において、状態情報を格納する。たとえば、計算論理に接続されたローカルメモリの１つの実施態様において、メモリは、接続されたフラッシュメモリのような、プログラマブルハードウェアデバイスに外部のメモリであってもよい。プログラマブルハードウェア１１８（１）に直接アクセス可能なメモリ７０８を使用することで、速度を増大させ、ＰＨＳＣ１１４を通じて状態を転送して格納する必要をなくす。
【００５０】
７１０において、ＰＨＩＭ５０４は構成バイナリ２１０（１）をロードし、その結果計算論理１２０（１）が得られ、これが実行して、ローカル状態情報３０８（１）をローカルメモリ７０８に格納することができる。７１２において、ＰＨＩＭ５０４は構成バイナリ２１０（２）をロードし、その結果計算論理１２０（２）が得られ、これがローカル状態情報３０８（１）にアクセスして、メモリ７０８との間で情報を読み取りおよび／または書き込みすることができる。７１４において、ＰＨＩＭ５０４は構成バイナリ２１０（３）をロードし、その結果計算論理１２０（３）が得られ、これもまたローカル状態情報３０８（１）にアクセスして、メモリ７０８との間で情報を読み取りおよび／または書き込みすることができる。したがって、情報は、構成バイナリの実行の間で持続することができる。
【００５１】
たとえば、構成バイナリ２１０（１）内のｒｅｇ ｅｘ１０８（１）はストリング「ｃａｒ」のｒｅｇ ｅｘであるが、構成バイナリ２１０（２）内のｒｅｇ ｅｘ１０８（３）はストリング「ｃａｒ ｌｏａｎ」のｒｅｇ ｅｘであり、構成バイナリ２１０（３）内のｒｅｇ ｅｘ１０８（５）はストリング「ｃａｒ ｌｏａｎ ｒｅｆｉｎａｎｃｉｎｇ」のｒｅｇ ｅｘであると仮定する。構成バイナリの実行中、状態情報３０８（１）は、構成バイナリ２１０（３）が、次に構成バイナリ２１０（１）からの結果を使用する構成バイナリ２１０（２）からの結果を使用するように、メモリ７０８に格納されてもよい。したがって、プログラマブルハードウェア１１８によって直接アクセス可能なメモリに格納されている状態情報にアクセスすることにより、処理速度が加速される。さらに、ストレージは、大きすぎて単一のプログラマブルハードウェアデバイスの容量を超えるｒｅｇ ｅｘの分割を容易にすることができる。
【００５２】
プロセスの例示
図８は、図１〜図７に示されるアーキテクチャを使用して実施されうる（ただし、必須ではない）正規表現処理システム１０２とのユーザ対話を説明する流れ図を示す。フロー８００（および図９〜図１２のフロー）は、論理フローグラフにおいてブロックの集合として示され、ブロックはハードウェア、ソフトウェア、またはその組み合わせにおいて実施されうる操作のシーケンスを表す。ソフトウェアのコンテキストにおいて、ブロックは、１つまたは複数のプロセッサによって実行される場合、列挙された操作を実行するコンピュータ実行可能命令を表す。一般に、コンピュータ実行可能命令は、特定の機能を実行するか、または特定の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造体などを含む。操作が説明される順序は、限定として解釈されることを意図されておらず、任意の数の説明されるブロックは、任意の順序および／または並列に組み合わされてプロセスを実施することができる。説明のために、プロセスは、図１〜図７のアーキテクチャのコンテキストで説明される。
【００５３】
ブロック８０２は、正規表現のリストを受信する。たとえば、正規表現として表されるスパム検索基準のリスト。ブロック８０４は、正規表現に基づいて構成情報を生成する。これは、図９に関して後段でさらに詳細に説明される。
【００５４】
ユーザには、ブロック８０６において明示または暗黙のいずれのユーザインターフェイスが選択されているかに応じて異なるインターフェイスが表示される。ブロック８０６において暗黙ユーザインターフェイスが選択されると、ブロック８０８は、生成された構成情報をプログラマブルハードウェアで実行する。ブロック８１０は、プログラマブルハードウェアからの結果を提供する。
【００５５】
ブロック８０６において暗黙ユーザインターフェイスが選択されると、ブロック８１２は、構成情報（構成仕様２０４および構成バイナリ２１０（１）〜２１０（Ｒ））を検査および／または変更のためにユーザに提示する。たとえば、自動的に生成された構成バイナリを手操作で調整したいと考えるユーザは、明示インターフェイスを選択することができる。この提示が完了すると、フローはブロック８０８において再開し、前述のように、生成された構成情報をプログラマブルハードウェアで実行することができる。
【００５６】
選択されたインターフェイスには関わりなく、このユーザインターフェイスは、ｒｅｇ ｅｘの複雑さとは無関係にプログラマブルハードウェアとの単純な対話をもたらす。そうすることで、ユーザは、プログラマブルハードウェアの詳細を認識する必要、または気に掛ける必要からも解放される。さらにこれは、異なるプログラマブルハードウェア１１８にわたる検索ポータビリティをもたらす。たとえば、ｒｅｇ ｅｘ１０８（１）〜１０８（Ｒ）は、異なるプログラマブルハードウェアデバイス１１８（１）〜１１８（Ｐ）にわたり実行するようにコンパイルされて、処理に使用可能になるとそれらのプログラマブルハードウェアデバイスにわたり配分されてもよい。このインターフェイスを使用することで、この複雑さをユーザの目から隠す。
【００５７】
図９は、図８に関して上記で述べた、正規表現８０４に基づく構成情報の生成を表す流れ図を示す。ブロック９０２は、正規表現のリストを解析し、それらを対応する論理および状態方程式に変換する。この変換は、前述のように、コンパイルモジュール１１２内で行ってもよい。ブロック９０４は、各正規表現の物理リソース要件を推定する。たとえば、ｒｅｇ ｅｘ１０８（１）が、プログラマブルハードウェアデバイス１１８（１）で２，０００の計算素子を必要とすると推定されることもあり、ｒｅｇ ｅｘ１０８（５）は、７，０００の計算素子を必要とすると推定されることもある。
【００５８】
ブロック９０６は正規表現をセットに配分し、ここで各セットはプログラマブルハードウェア１１８において使用可能な物理リソース内に収まる。この推定はまた、通信および制御（ＣＣ）論理、ならびにローカルストレージ要件を含むことができる。たとえば、上記の図３において、使用可能な物理リソースはプログラマブルハードウェアの計算論理容量３０２であり、セットのうちの１つはｒｅｇ ｅｘ１０８（１）、１０８（２）、１０８（６）、およびＣＣ３０６（１）を含む。
【００５９】
ブロック９０８は、各セットにカスタマイズされた制御および通信論理を追加し、ブロック９１０は、各セットに対してＨＤＬファイルを生成する。ブロック９１２は、構成仕様２０４（１）のような構成仕様を生成する。ブロック９１４は、各ＨＤＬファイルから構成バイナリを生成する。たとえば、ＨＤＬファイルは、結果として構成バイナリ２０１（１）をもたらすことができる。
【００６０】
図１０は、図９に関して前述された正規表現９０４による物理リソース要件の推定を表す流れ図を示す。ブロック１００２は、正規表現を特定の計算論理配列に関連付ける。たとえば、ストリング「ｈｏｍｅ」の正規表現は、２００の回路素子の特定の配列を伴うことがある。この関連付けは、正規表現を生成するブロック１００２（１）、ハードウェアＣＡＤツールがｒｅｇ ｅｘ内の項目を論理方程式に変換する方法を決定するブロック１００２（２）、ｒｅｇ ｅｘの回路要件を決定するブロック１００２（３）により作成されてもよい。たとえば、サンプルの正規表現は、ＣＡＤツールによる論理方程式に変換されてもよく、結果の要件が監視される。したがって、正規表現入力に基づいて回路要件の予測を可能にするモデルが構築されてもよい。
【００６１】
関連付けが行なわれると、ブロック１００４は、冗長論理を識別し、それらの冗長を除去するように統合して、統合された論理を形成する。たとえば、複数の正規表現は、共通のルートストリングを伴うか、または回路で表現される場合に冗長回路をもたらすこともあるその他の共通性を有することができる。これらの冗長性は除去することができ、効率を高めることができる。その１つの実施態様は、図２９に関して後段で、スーパーセットのコンテキストでさらに詳細に説明される。
【００６２】
ブロック１００６は、ローカル状態ストレージ３０８が呼び出されるかどうか、および呼び出される場合に必要とされるメモリリソースなどのような、ローカルストレージ要件を推定する。ブロック１００８は、ＣＡＤツール固有の修正率を統合された論理およびローカルストレージ要件に適用する。たとえば、特定のＣＡＤツールは、特定のｒｅｇ ｅｘによって呼び出された論理方程式を例外的な方法で計算ブロックに変換することができ、したがって物理リソースの推定がさらに正確になるように修正率が入力されてもよい。
【００６３】
ブロック１０１０は、推定される物理リソース要件を生成する。たとえば、「ｃｒｅｄｉｔ ｃａｒｄ」を検索するためのｒｅｇ ｅｘは、製造業者ＸによるＦＰＧＡタイプＡで推定一千の回路素子を必要とすることがある。この推定は、ｒｅｇ ｅｘがプログラマブルハードウェア１１８の物理リソース内に収まるかどうかを決定するために使用されるブルートフォースの試行錯誤と比較すると、大幅に高速で、リソース集約的ではなく、人間の対話をほとんどまたは全く必要としない。さらに、このプロセスは、さまざまな容量を備えるプログラマブルハードウェアの複数のタイプに容易に適用することができ、新しいハードウェアへのｒｅｇ ｅｘの迅速な再配置が可能になる。
【００６４】
図１１は、図８に関して前述されたプログラマブルハードウェア８０８での生成された構成情報の実行を表す流れ図である。１つの実施態様において、後続のブロックは、ＰＨＳＣ１１４によって実行されてもよい。
【００６５】
ブロック１１０２は、構成情報２１２およびコーパスデータ１１６を受信する。たとえば、構成ファイルは、スパム検索のために正規表現１０８を具現する構成バイナリ２１０を含むことができ、コーパスデータは、スパムを検索される未加工の電子メールであってもよい。
【００６６】
ブロック１１０４は、実行シーケンス５０８からの実行されていない構成バイナリをプログラマブルハードウェア１１８にロードする。ブロック１１０６は、コーパス１１６の全部または一部を処理のためにプログラマブルハードウェア１１８にロードする。ブロック１１０８は、ロードされたコーパスデータ１１６に対してプログラマブルハードウェア１１８で計算論理１２０を実行する。ブロック１１１０は、計算論理のプログラマブルハードウェアの実行からの結果を提供する。コーパスの追加の部分が残っている場合、ブロック１１１２は、フローをブロック１１０６に戻し、コーパスの別の部分を処理のためにプログラマブルハードウェア１１８にロードする。それ以外の場合で、ブロック１１１２においてコーパスの追加の部分が残っていなければブロック１１１４は、追加の構成バイナリが実行シーケンス５０８に存在するかどうかを決定する。追加の構成バイナリが実行シーケンス５０８に残っている場合、ブロック１１１６は、実行シーケンスを次の構成バイナリに増分して、フローを１１０４に戻す。追加の構成バイナリが実行シーケンス５０８に残っていない場合、ブロック１１１８は、１つまたは複数の構成バイナリの実行により得られた結果を統合する。
【００６７】
図１２は、正規表現の動的な変更を示す流れ図１２００である。ｒｅｇ ｅｘは、時間の経過に伴って変化してもよい。たとえば、インコの売れ行きの新たな一時的流行により、「ｐａｒａｋｅｅｔ」がスパム検索リストに追加されるという結果をもたらすこともある。あるいは、新種のクレジットカードビジネスが加わって、「ｃｒｅｄｉｔ ｃａｒｄ」がスパム検索リストから削除されるという結果をもたらすこともある。
【００６８】
限定の目的ではなく説明を簡単にするため、正規表現のリストへの変更は一般に、新しい正規表現の追加、または既存の正規表現の削除という２つのカテゴリに分類されると考えられてもよい。新しい正規表現が追加されるべきであるとブロック１２０２が決定する場合、ブロック１２０４は、新しい正規表現の構成バイナリを生成する。次いで、ブロック１２０６は、この構成バイナリを実行のシーケンス５０８に追加する。
【００６９】
変更は既存の正規表現の削除であるとブロック１２０２が決定する場合、ブロック１２０８は正規表現を廃棄リストに追加する。プログラマブルハードウェア１１８で計算論理１２０を実行した後、ブロック１２１０は、ｒｅｇ ｅｘからの結果を廃棄する。一部の実施態様において、この廃棄はアクティブな削除であってもよく、また他の実施態様において、廃棄されたｒｅｇ ｅｘからの結果はＰＨＳＣ１１４によってレポートされていなくてもよい。廃棄リストでｒｅｇ ｅｘの処理を続行することは無駄が多いと思われることもあるが、各構成バイナリ内のｒｅｇ ｅｘの並列処理を考えると、実際には非常に効率的である。図６に関して前述されているように、構成バイナリ内のｒｅｇ ｅｘは並列に実行される。したがって、構成バイナリが大量にフラグメント化した状態になるまでは、構成バイナリ全体を再コンパイルするよりも、多数のｒｅｇ ｅｘを並列に実行して、それらの結果のうちの１つを廃棄するほうが安価である。さらに、ユーザは、廃棄リストからｒｅｇ ｅｘを単に除去してそれを再イネーブルすることにより、以前廃棄されたｒｅｇ ｅｘを容易に復元することができる。未使用の／取り消されたｒｅｇ ｅｘにより生じたフラグメンテーションに対処するための再コンパイルをどのように、いつ行なうかについての決定は、後段で図１９〜図２０関してさらに詳細に説明される。
【００７０】
ブロック１２１２は、プログラマブルハードウェア１１８からの結果を、現在の構成に含まれていない追加の正規表現の結果でパッチする。これは、最近システムに追加されたが、まだプログラマブルハードウェア１１８での実行のために構成バイナリ２１０にはコンパイルされていないｒｅｇ ｅｘの場合のように、一部のｒｅｇ ｅｘが補助の正規表現処理モジュール１２４で実行される場合に有用となることがある。
【００７１】
ブロック１２１４は、補助の正規表現処理モジュール１２４で実行されている正規表現のような、現在の構成には含まれていない正規表現を、現在の構成に追加することができる。これらの正規表現は、実行シーケンス５０８の一部である構成バイナリ２１０に組み入れるためにコンパイルモジュール１１２によってコンパイルされてもよい。ブロック１２１６は、新しい構成バイナリの生成中に、廃棄リストに存在する正規表現を除去して、廃棄を一掃する。
【００７２】
再配分を介するフォールトトレランス
プログラマブルハードウェアデバイス１１８を含む機器は、故障することもある。図１３〜図１５は、残りの機能可能なプログラマブルハードウェアデバイスに構成バイナリを再配分することによるフォールトトレランスのサポートを示す流れ図１３００である。これらの図において、矢印１３０２により指示されるようにページを下方に進むと時間が増大する。図１３を始めとして、ＰＨＩＭ５０４は、２つのプログラマブルハードウェアデバイス１１８（１）および１１８（２）に結合されることが示される。この例の場合、プログラマブルハードウェア１１８（１）および１１８（２）がバイナリ互換である１３０４、すなわち、いずれのプログラマブルハードウェアでも再コンパイルすることなく同一の構成バイナリ２１０が実行されてもよいと仮定する。また、実行シーケンス５０８が、構成バイナリ２１０（１）、２１０（２）、２１０（３）、２１０（４）、２１０（１）、２１０（２）、２１０（３）、２１０（４）のためのものであるというように仮定する。図１３は、通常の操作１３０６を示す。通常の操作１３６０中に、１３０８において、ＰＨＩＭ５０４は、構成バイナリ２１０（１）および２１０（２）をそれぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードする。その結果得られた計算論理１２０（１）および１２０（２）は実行し、その結果はＰＨＩＭ５０４に返される。同様に、１３１０において、構成バイナリ２１０（３）および２１０（４）はロードされて実行される。１３１２において、シーケンスは繰り返し、処理のために構成バイナリ２１０（１）および２１０（２）をロードする。これは、プログラマブルハードウェアを仮想化することの汎用性を示す。４つの構成バイナリ２１０（１）〜２１０（４）は、２つのプログラマブルハードウェア１１８（１）および１１８（２）だけで実行される。
【００７３】
図１４は、この流れ図を継続して、故障の発生および移行１４０２を説明する。１３１４において、構成バイナリ２１０（３）はプログラマブルハードウェア１１８（１）に正常にロードされ、一方構成バイナリ２１０（４）のプログラマブルハードウェア１１８（２）へのロードは試みられたが、使用不可能であったために失敗した。１３１６において、構成バイナリ２１０（３）に基づいて計算論理１２（３）からＰＨＩＭ５０４に結果が返された後、ＰＨＩＭ５０４は、構成バイナリ２１０（４）を処理のためにプログラマブルハードウェア１１８（１）にロードする。
【００７４】
フローを図１５に継続して、フェイルセーフ操作１５０２が示される。プログラマブルハードウェア１１８（２）は引き続き使用不可能であり、プログラマブルハードウェア１１８（１）は、実行シーケンス５０８にリストされている構成バイナリの実行を処理する。１３１８において、プログラマブルハードウェア１１８（１）は、実行シーケンス５０８で次の順番の構成バイナリ２１０（１）をロードして実行する。１３２０において、プログラマブルハードウェア１１８（１）は構成バイナリ２１０（２）をロードして実行し、１３２２において、構成バイナリ（３）がロードされて実行され、さらに１３２４において、構成バイナリ２１０（４）がロードされて実行される。このように、実行シーケンス５０８内に存在するリストは完全に実行されており、実行シーケンス５０８によって呼び出されると続行することができる。プログラマブルハードウェア１１８（２）の損失により実行パフォーマンスは低下しているが、ｒｅｇ ｅｘ１０８（１）〜１０８（Ｒ）の処理は引き続き継続することができた。構成が仮想であるため、この動的な再配分が可能になる。スパムフィルタリングの例に戻ると、プログラマブルハードウェア１１８（２）の故障は、システムが完全に使用不可となる結果をまねくのではなく、単にスパムフィルタリングのパフォーマンスを低下させる。
【００７５】
複数のプログラマブルハードウェア１１８を有する一部の実施態様において、構成バイナリは故障に備えるために過小に割り振られてもよい。たとえば、各プログラマブルハードウェアデバイスの実行シーケンスは、後に故障中に消費されうるアイドル状態のプレースホルダを含むことができる。
【００７６】
スペアリングを介するフォールトトレランス
図１６〜図１８は、予備の機能可能なプログラマブルハードウェアデバイスの使用を介するフォールトトレランスのサポートを示す流れ図１６００を備える。上記と同様に、これらの図において、矢印１６０２により指示されるようにページを下方に進むと時間が増大する。
【００７７】
図１６を始めとして、ＰＨＩＭ５０４は、２つのプログラマブルハードウェアデバイス１１８（１）および１１８（２）に結合されることが示される。上記のように、この例の場合、プログラマブルハードウェア１１８（１）および１１８（２）がバイナリ互換である１６０４、すなわち、いずれのプログラマブルハードウェアでも再コンパイルすることなく同一の構成バイナリ２１０が実行されてもよいと仮定する。また、実行シーケンス５０８が、構成バイナリ２１０（１）、２１０（２）、２１０（３）、２１０（４）、２１０（１）、２１０（２）、２１０（３）、２１０（４）のためのものであるというように仮定する。
【００７８】
図１６は、通常の操作１６０６を示す。通常の操作１６０６中に、１６０８において、ＰＨＩＭ５０４は、構成バイナリ２１０（１）および２１０（２）をそれぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードする。その結果得られた計算論理１２０（１）および１２０（２）は実行し、その結果はＰＨＩＭ５０４に返される。同様に、１６１０において、構成バイナリ２１０（３）および２１０（４）はロードされて実行される。１６１２において、シーケンスは繰り返し、処理のために構成バイナリ２１０（１）および２１０（２）をロードする。
【００７９】
図１７は、フロー１６００を継続して、故障の発生およびスペアリング１７０２を説明する。この図において、１６１４において、プログラマブルハードウェア１１８（１）は構成バイナリ２１０（３）を正常にロードし、一方プログラマブルハードウェア１１８（２）は構成バイナリ２１０（４）をロードすることができなくなった。プログラマブルハードウェア１１８（２）が失敗したと決定すると、ＰＨＩＭ５０４は、構成バイナリ２１０（４）を備えてあった予備のプログラマブルハードウェアデバイス１１８（３）にリダイレクトすることができる。
【００８０】
図１８は、予備のプログラマブルハードウェアに構成バイナリをリダイレクトすることによる通常の操作の再開１８０２を示す図である。１６１６において、プログラマブルハードウェア１１８（１）は構成バイナリ２１０（１）をロードし、一方予備のプログラマブルハードウェア１１８（３）は構成バイナリ２１０（４）をロードした。
【００８１】
１６１８において、ＰＨＩＭ５０４は、実行シーケンス５０８に指定されているように構成バイナリをロードして実行する。したがって、構成バイナリ２１０（２）および２１０（３）は、それぞれプログラマブルハードウェア１１８（１）および１１８（３）にロードされる。１６２０において、構成バイナリ２１０（４）および２１０（１）は、それぞれプログラマブルハードウェア１１８（１）および１１８（３）にロードされ、実行シーケンス５０８を再度開始する。
【００８２】
プログラマブルハードウェア１１８のコンテキストにおけるスペアリングは、いくつかの利点をもたらす。構成バイナリが完全構成をカプセル化するので、構成バイナリはプログラマブルハードウェアに迅速にロードおよびアンロードされる。これは、サーバインスタンスを導入するために必要な操作の複雑さおよび時間とは対照的である。したがって、予備のプログラマブルハードウェアデバイスは、非常に迅速にアクセスしてサービスに参加させることができる。
【００８３】
フラグメンテーションの緩和
前述のように、時間の経過に伴って、処理されるべき正規表現のリストは変化する。スパムフィルタリングの例において、新しいｒｅｇ ｅｘは、他のｒｅｇ ｅｘが除去される間に追加される。図１９は、構成バイナリにわたる正規表現のフラグメンテーション緩和を示す概略図１９００である。１つの実施態様において、フラグメンテーション緩和は、ＰＨＳＣ１１４内で実行されてもよい。
【００８４】
この追加および除去は、時間の経過に伴って、「ライブ（生き）の」すなわち廃棄されたｒｅｇ ｅｘの中で引き続き必要なｒｅｇ ｅｘのフラグメンテーションをまねくことになる。１９０２において、複数のフラグメント化された構成バイナリが、フラグメンテーション緩和の前に示される。この図において、網掛けは、未使用の／取り消されたｒｅｇ ｅｘを示す１９０４。この例において、ｒｅｇ ｅｘ１０８（１）、１０８（３）、１０８（５）、１０８（７）、および１０８（９）は、取り消されている。たとえば、これらは、会社の新種のクレジットカードビジネスにより現在はスパムリストから削除されている「ｃｒｅｄｉｔ ｃａｒｄ」および変種のスパムフィルタに関連する可能性もある。ｒｅｇ ｅｘ１０８（２）、１０８（４）、１０８（６）、および１０８（８）は、引き続き使用されている。そのため、それらのｒｅｇ ｅｘを含む４つの構成バイナリ２１０（２０）〜２１０（２３）がフラグメント化された状態になり、わずかな望ましいｒｅｇ ｅｘの間にいくつかの未使用のｒｅｇ ｅｘが散在している。これらのフラグメント化された構成バイナリを実行することで、使用可能なプログラマブルハードウェアのリソースを浪費する。したがって、このフラグメンテーションを緩和することが望ましい。
【００８５】
１９０６において、新しく追加されたｒｅｇ ｅｘ１０８（１０）は、補助のｒｅｇ ｅｘ処理モジュール１２４で実行する。次回の構成バイナリのコンパイル中に、構成バイナリ内にスペースが使用可能である場合、ｒｅｇ ｅｘ１０８（１０）は、プログラマブルハードウェア１１８で実行するために、処理モジュール１２４での実行から構成バイナリ２１０へ転送されてもよい。
【００８６】
１９０８において、フラグメンテーション緩和後の構成バイナリが示される。未使用のｒｅｇ ｅｘは廃棄されており、１９１０において、引き続き使用されたそれらのｒｅｇ ｅｘおよびｒｅｇ ｅｘ１０８（１０）は、２つの新しい構成バイナリにコンパイルされた。４つの構成バイナリがソフトウェアにおいて１つのｒｅｇ ｅｘで実行されていたが、ここで２つの構成バイナリが実行する。
【００８７】
図１９は、すべてのアクティブなｒｅｇ ｅｘ１０８の完全な再コンパイルを示す。しかし、コンパイルは、時間およびシステムリソースの点から高価である。一部の実施態様において、完全再コンパイルをあまり頻繁には実行しない間、システムコストを最小化するために選択的に再コンパイルを行なうことが望ましいこともある。
【００８８】
図２０は、選択的な再コンパイルによるフラグメンテーション緩和を示す概略図２０００である。選択的または完全に再コンパイルするかどうかに関する決定は、コンパイル時間に対してハードウェアおよびソフトウェアの潜在的な実行効率を重み付けすることを伴う。
【００８９】
２００２において、フラグメンテーション緩和前の構成バイナリ２１０（３０）〜２１０（３３）が示される。上記のように、未使用のまたは取り消されたｒｅｇ ｅｘは網掛けで示される２００４。この例において、ｒｅｇ ｅｘ１０８（１）、１０８（３）、１０８（５）、１０８（７）、および１０８（９）は、取り消されている。ｒｅｇ ｅｘ１０８（２）、１０８（４）、１０８（６）、および１０８（８）は、引き続き使用されている。２００６において、新しく追加されたｒｅｇ ｅｘ１０８（１０）は、次の構成バイナリのコンパイルを待つ間、補助のｒｅｇ ｅｘ処理モジュール１２４で実行する。
【００９０】
この図において、コンパイル時間に対してハードウェアおよびソフトウェアの潜在的な実行効率を重み付けすることは、結果として１つの再コンパイルのリソースが使用可能になると仮定する。初期コンパイル中に生成されたリソース推定情報は取り出され、構成バイナリは最大の未使用のスペースから最小の未使用のスペースにソートされる。構成バイナリ２１０（３０）は１００％の未使用スペースを有し、構成バイナリ２１０（３１）は約６６％の未使用スペースを有し、構成バイナリ２１０（３２）は約５５％の未使用スペースを有し、構成バイナリ２１０（３３）は約３３％の未使用スペースを有する、
【００９１】
１つの実施態様において、選択的再コンパイルは、補助のｒｅｇ ｅｘ処理モジュール１２４によって実行されているｒｅｇ ｅｘ１０８（１）をハードウェアに移動し、次いでｒｅｇ ｅｘを最大の未使用スペースを持つ構成バイナリに移動することを伴うことができる。この図において、構成バイナリ２１０（３０）および２１０（３１）は、破線によって指示されるように２００８、選択的再コンパイルのために選択される。
【００９２】
アクティブなｒｅｇ ｅｘは、Ｎ個の構成（１つのコンパイルが使用可能なので、この場合はＮ＝１）が満たされるまで結合される。この図において、構成バイナリ２１０（３０）は空になると廃棄され、構成バイナリ２１０（３１）のｒｅｇ ｅｘ１０８（２）は、２０１０においてｒｅｇ ｅｘ１０８（２）と結合されて構成バイナリ２１０（３４）を生成する。２０１２において、新しくコンパイルされた構成バイナリ２１０（３４）および変更なしの構成バイナリ２１０（３２）および２１０（３３）を示す、選択的フラグメンテーション移行後の結果が表される。これは、ソフトウェアベースのｒｅｇ ｅｘの数を０に減少させ、合計ハードウェア構成の数を４から３に減少させる。したがって、最小のコンパイルリソースが使用され、しかも全体的なフラグメンテーションを軽減している。
【００９３】
タスクの優先順位付け、およびリソースの再利用
一部の実施態様において、タスクを優先順位付けすることが有益である場合がある。たとえば、今日のスパムが主に「クレジットカード」広告を扱うこともあり、したがってこの語句を見つけるように設計されるｒｅｇ ｅｘは、これらの広く行き渡る出現を素早く除去するために、より高い優先度を与えられてもよい。
【００９４】
図２１は、正規表現の優先度を認識するハードウェア割り当て、ならびにそれらの正規表現の構成バイナリへのパッキングおよびスケジューリングを示す概略図２１００である。この図において、通常の優先度のｒｅｇ ｅｘは白で指定され、中程度の優先度のｒｅｇ ｅｘは斜線で指定され、最高の優先度のｒｅｇ ｅｘは影付きである。２１０２において、実行のための正規表現が示される。それらの中で、ｒｅｇ ｅｘ１０８（１）、１０８（６）、および１０８（８）は、最高の優先度である。ｒｅｇ ｅｘ１０８（５）は中程度の優先度として設計され、残りの１０８（２）、１０８（３）、１０８（４）、１０８（７）、１０８（９）、および１０８（１０）は通常の優先度である。
【００９５】
２１０４において、パックされ、コンパイルされて、実行のために順序付けられたｒｅｇ ｅｘが示される。より高い優先度を有するｒｅｇ ｅｘは共にパックされ、一部の実施態様において、より高速なプログラマブルハードウェアデバイス１１８で実行するよう設計されるか、実行シーケンス５０８の優先度を受信するか、またはさらに頻繁な実行のために実行シーケンス５０８の複数ポイントに配置されてもよい。示されているように、構成バイナリ２１０（４１）は、すべての高い優先度のｒｅｇ ｅｘに対して十分な容量を有する。構成バイナリ２１０（４２）は、中程度の優先度のｒｅｇ ｅｘ１０８（５）を含み、使用できる残りの追加の容量があったので通常の優先度の１０８（４）も含む。構成バイナリ２１０（４１）および２１０（４２）は共に、そのより高い優先度の内容を考慮してより高速なプログラマブルハードウェアデバイスで実行するために２１０６により示されるように指定されてもよい。通常の優先度のｒｅｇ ｅｘを含む構成バイナリ２１０（４３）および２１０（４４）は、より遅いプログラマブルハードウェアデバイスで実行するように２１０８指定されてもよい。
【００９６】
構成バイナリのパッキングおよび／または構成バイナリの実行シーケンスの優先度割り当ては、特定のタスクが先に実行されて、それらの結果が後の処理に影響を及ぼすようにするか、または後の処理全体を除去するように行なわれてもよい。たとえば、「ｚｅｒｏ ｄｏｗｎ ｈｏｍｅ ｍｏｒｔｇａｇｅ ｆｉｎａｎｃｉｎｇ ｂｏｎａｎｚａ」を探すｒｅｇ ｅｘは、この項目の組み合わせがスパムメッセージのさらに容易な識別に役立つ可能性があることを前提に、「ｈｏｍｅ ｍｏｒｔｇａｇｅ」のｒｅｇ ｅｘよりも高い優先度を与えられてもよい。
【００９７】
図２２は、構成バイナリの実行を再配分することによるアイドルプログラマブルハードウェアリソースの再利用を示す流れ図２２００である。上記と同様に、この図において、矢印２２０２により指示されるようにページを下方に進むと時間が増大する。
【００９８】
この例の場合、プログラマブルハードウェア１１８（１）および１１８（２）がバイナリ互換である２２０４、すなわち、いずれのプログラマブルハードウェアでも再コンパイルすることなく同一の構成バイナリ２１０が実行されてもよいと仮定する。また、初期実行シーケンス５０８が、構成バイナリ２１０（１）、２１０（２）、２１０（３）、２１０（４）、２１０（１）、２１０（２）、２１０（３）、２１０（４）のためのものであるというように仮定する。
【００９９】
図２２０６において、通常の操作が示される。２２０８において、ＰＨＩＭ５０４は、構成バイナリ２１０（１）および２１０（２）をそれぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードする。結果が返され、２２１０において、ＰＨＩＭ５０４は、構成バイナリ２１０（３）および２１０（４）をそれぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードする。このプロセスは、初期実行シーケンス５０８全体を通過するように続行することができる。
【０１００】
しかし、それぞれ構成バイナリ２１０（２）および２１０（４）に基づく計算論理１２０（２）および１２０（４）がアイドルであると仮定する。おそらくは、それらの計算論理は中断されていたか、または計算論理１２０（１）および１２０（３）の前に完了していた。初期実行シーケンスが連続して続行していた場合、プログラマブルハードウェアリソースは、これらのアイドル構成バイナリを待つか、または中断された構成バイナリを実行して浪費されていたであろう。したがって、この例において、初期実行シーケンスは、リソースを再利用するように変更される。
【０１０１】
２２１２において、このアイドル時間の再利用は、引き続きアクティブな構成バイナリの再配分を通じて示される。したがって、２２１４において、ＰＨＩＭ５０４は、構成バイナリ２１０（１）および２１０（３）をそれぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードする。２２１６において、プログラマブルハードウェア１１８（１）および１１８（２）は、再度、構成バイナリ２１０（１）および２１０（３）に基づく計算論理１２０（１）および１２０（３）を実行する。計算論理１２０（２）および１２０（４）はアイドルであるので、これらはロードされて実行されることはない。したがって、１２０（２）および１２０（３）のような引き続き実行するよう指定されている計算論理は、アイドルまたは中断した計算論理によって妨げられることなく実行し続ける。
【０１０２】
前述のように、特定のｒｅｇ ｅｘが他のｒｅｇ ｅｘよりもさらに重要である場合、これらはさらに多くのリソースを与えられてもよい。図２３および図２４は、構成バイナリおよびその内部の正規表現の優先順位付けを示す流れ図２３００である。この図において、矢印２３０２により指示されるようにページを下方に進むと時間が増大する。プログラマブルハードウェア１１８（１）および１１８（２）は、バイナリ互換であると仮定する２３０４。
【０１０３】
図２３を参照すると、２３０６において、等しい優先度の操作が示される。任意の計算論理内のタスクには優先度が与えられない。実行シーケンス５０８は、構成バイナリ２１０（１）、２１０（２）、２１０（３）、２１０（４）、２１０（１）、２１０（２）、２１０（３）、２１０（４）などのためのものである。２３０８において、構成バイナリ２１０（１）および２１０（２）は、実行のために、それぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードされる。２３１０において、構成バイナリ２１０（３）および２１０（４）は、実行のために、それぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードされる。
【０１０４】
図２４にフローを続行すると、２４０２において、構成バイナリ２１０（１）内のｒｅｇ ｅｘは高い優先度を与えられており、そのほんのわずかなタイムスライスが増大されている。したがって、実行シーケンス５０８は、構成バイナリ２１０（１）、２１０（１）、２１０（１）、２１０（１）、２１０（１）、２１０（２）、２１０（１）、２１０（３）、２１０（１）、２１０（４）を実行するように変更される。したがって、２３１２において、構成バイナリ２１０（１）は、プログラマブルハードウェア１１８（１）および１１８（２）の両方にロードされる。２３１４において、両プログラマブルハードウェア上に計算論理１２０（１）がすでに存在するので、構成バイナリはロードされず、計算論理が再度実行される。
【０１０５】
２３１６において、計算論理１２０（１）は再度プログラマブルハードウェア１１８（１）で実行し、構成バイナリ２１０（２）はプログラマブルハードウェア１１８（２）にロードされて実行される。２３１８において、計算論理１２０（１）は再度実行し、構成バイナリ２１０（３）はロードされてプログラマブルハードウェア１１８（２）で実行される。２３２０において、計算論理１２０（１）は再度実行し、構成バイナリ２１０（４）はＰＨＩＭ５０４によってプログラマブルハードウェア１１８（２）にロードされる。したがって、この例において、構成バイナリ２１０（１）内に含まれる高い優先度のｒｅｇ ｅｘは、時間の７０％で実行された。
【０１０６】
タスクのマージ
正規表現処理システム１０２の操作中、複数のユーザおよび／またはアプリケーションからのｒｅｇ ｅｘが受信されてもよい。たとえば、スパムフィルタリングシステムは、ユーザまたは分析ソフトウェアによりフラグ設定されたスパムのようなスパムを指示する複数のストリングのストリームを受信することができる。図２５は、コンパイルおよび／または実行における複数のユーザ／アプリケーションによる正規表現のマージャーを示す流れ図２５００である。そのようなマージは、時間およびシステムリソースの点から比較的高価であるプログラマブルハードウェアの再構成を最小化することにより速度を増大させる。
【０１０７】
コンパイルマージ中、２５０２において、ｒｅｇ ｅｘ１０８（１）はユーザＡから受信され、ｒｅｇ ｅｘ１０８（２）はユーザＢから受信される。２５０４において、コンパイルモジュール１１２はこれらのｒｅｇ ｅｘを処理し、これらがいずれも同じ構成バイナリで実行できることを決定し、２５０６において、ｒｅｇ ｅｘ１０８（１）および１０８（２）を含む構成バイナリ２１０（５１）を生成する。２５０８において、ユーザＡおよびＢからの入力がＰＨＳＣ１１４において受信される。２５１０において、ＰＨＩＭ５０４は、実行のために構成バイナリ２１０（５１）をロードし、２５１２においてプログラマブルハードウェアは構成バイナリを実行して、結果をＰＨＩＭ５０４に返す。次いで、ＰＨＳＣ１１４は、結果をそれぞれのユーザに返す。利点の中でも特に、マージは、コンテキスト切り替えの必要性をなくす。たとえば、マージしなければ、ユーザＡとユーザＢとの間でコンテキストを切り替えることが必要になる。したがって、ユーザＡのｒｅｇ ｅｘ１０８（１）は、ｒｅｇ ｅｘ１０８（２）が待機している間に実行していることになる。ｒｅｇ ｅｘ１０８（１）が完了すると、ｒｅｇ ｅｘ１０８（２）は実行する。マージにより、両方が同時に実行することができる。
【０１０８】
このプロセスのセキュリティは、単に基礎をなすコンパイルモジュール１１２およびＰＨＳＣ１１４はそれらの２つの異なるｒｅｇ ｅｘが同時に実行されたことを認識しているので、マージ中に保持される。ユーザＡおよびユーザＢは、マージャーに気付いてはおらず、それぞれの結果は別々のままである。
【０１０９】
遅延構成ページング
マージに加えて、複数のアプリケーションまたはユーザは、正規表現処理システム１０２の操作中にリソースを共有することができる。図２６は、この共有を容易にするための構成バイナリの遅延構成ページングを示す流れ図２６００である。遅延ページングは、タスクの遅延を考慮に入れて、それらのタスクの統合を可能にし、プログラマブルハードウェアの再構成を最小化することができる。
【０１１０】
この図において、矢印２６０２により指示されるようにページを下方に進むと時間が増大する。２６０４において、ＰＨＳＣ１１４は、コーパスの第１の部分のような、入力Ａを持つｒｅｇ ｅｘ１０８（８０）を受信する。ＰＨＳＣ１１４は、プログラマブルハードウェアでの実行のためにｒｅｇ ｅｘをＰＨＩＭ５０４に渡し、結果をユーザに返す。
【０１１１】
２６０６において、ＰＨＳＣ１１４は、処理のためにｒｅｇ ｅｘ１０８（８１）を受信する。しかし、ｒｅｇ ｅｘ１０８（８０）の追加の処理が発生することが予想されていた。その結果、ｒｅｇ ｅｘ１０８（８１）の処理が遅延する。
【０１１２】
２６０８において、コーパスの第２の部分のような、今回は入力Ｂを持つｒｅｇ ｅｘ１０８（８０）が再度要求される。プログラマブルハードウェア１１８（２）はすでに、ロードされたｒｅｇ ｅｘ１０８（８０）を組み入れる構成２１０（８０）を有しているので、再構成のための遅延はなく、処理は開始することができる。次いで、これらの結果はユーザに返される。
【０１１３】
２６１０において、ｒｅｇ ｅｘ１０８（８０）は完了し、遅延したｒｅｇ ｅｘ１０８（８１）はここでロードされてプログラマブルハードウェア１１８（２）によって実行されてもよい。次いで、これらの結果はユーザに返されてもよい。
【０１１４】
したがって、一部の実施態様において、作業は、現在ロードされておらず、受信された順序と比較して順不同に実行される構成バイナリ２１０について格納されてもよい。それにより、プログラマブルハードウェア１１８への構成バイナリ２１０のロードの回数と頻度を最小化することによって、さらに大幅に効率を高めることができる。
【０１１５】
サブバイナリコンパイル
コンパイルは、プログラマブルハードウェア１１８を使用するように設計された構成バイナリ全体の細分性を下回る細分性のレベルにおいて生じることがある。一部の再構成可能なハードウェアデバイスは、部分的な動的再構成、すなわち、デバイス全体よりも少ない細分性における再構成を考慮に入れる。図２７は、後に完全な構成バイナリを作成するよう結合されうる構成バイナリサブエレメントのコンパイルを示す流れ図２７００である。
【０１１６】
プログラマブルハードウェア２０８のＣＡＤツールによって必要とされる実行時間は、計算論理１２０のサイズに対して超線形に増大する。そのため、パフォーマンスの利点は、より大きい構成バイナリまたはＨＤＬファイルをより小さいファイルに分割して、それらのより小さいファイルを別個にコンパイルすることによって認識することができる。次いで、結果として得られるサブエレメントは、完全な計算論理を形成するように結合されてもよい。より高速なＣＡＤツール２０８のコンパイル時間に加えて、バイナリは、多大なリソースおよび時間を要する全構成バイナリの再コンパイルを必要とするのではなく、それらの事前構成されたサブエレメントを操作することができるので、デフラグおよび再構成を行ないやすい。それらのサブエレメントのパッキングは、（構成全体に対し静的に１回ではなく）動的に行なわれてもよい。
【０１１７】
この図において、正規表現１０８（１）および１０８（２）、ならびに通信および制御論理（ＣＣ）３０６は、サブエレメントのコンパイルのために構成されたコンパイルモジュール１１２によって受信される。ＨＤＬコンパイラ２０２は、各々に対してＨＤＬファイルを作成する。したがって、ＲＥ１０８（１）に対してＨＤＬファイル２７０２（１）、ＲＥ１０８（２）に対してＨＤＬファイル２７０２（２）、ＲＥ１０８（３）に対してＨＤＬファイル２７０２（３）がコンパイルされる。ＣＡＤツール２０８は、サブエレメントの作成のためにそれらのＨＤＬファイル２７０２（１）〜２７０２（３）を受け入れる。結果としてｒｅｇ ｅｘ１０８（１）は構成バイナリサブエレメント２７０４（１）をもたらし、ｒｅｇ ｅｘ１０８（２）は構成バイナリサブエレメント２７０４（２）をもたらし、ＣＣ３０６は構成バイナリサブエレメント２７０４（３）をもたらす。
【０１１８】
バイナリサブエレメントは実行のために選択されてもよいので、バイナリマージモジュール２７０６は、これらのサブエレメントをまとめて結合構成バイナリ２７０８を生成することができる。次いで、この結合構成バイナリ２７０８は、ロードされてプログラマブルハードウェア１１８によって実行されてもよい。
【０１１９】
計算の結合およびスーパーセット
追加のパフォーマンスの利点は、計算およびスーパーセットの組み合わせを通じて達成されうる。図２８は、正規表現を結合する計算を示す概略図２８００である。類似または重複するｒｅｇ ｅｘのような計算は、結合されてもよい。たとえば、いくつかのスパムフィルタリングアプリケーションおよびユーザが、処理のためにｒｅｇ ｅｘのグループをサブミットすると仮定する。それらのグループ内に、共通の実行のために見出されてパックされうる重複があってもよい。
【０１２０】
２８０２において、実行のための正規表現が示される。これらは、２８０４において、ｒｅｇ ｅｘ１０８（１）〜１０８（６）を含むタスクＡを含む。さらに実行のためにｒｅｇ ｅｘに含まれるのは、２８０６において、ｒｅｇ ｅｘ１０８（１）、１０８（４）、１０８（６）、１０８（７）、１０８（８）、および１０８（９）を含むタスクＢである。重複するｒｅｇ ｅｘは、影付きで示される。ｒｅｇ ｅｘ１０８（１）、１０８（４）、および１０８（６）は、２つのタスク間で共通である。計算の結合を行なわない場合、１２のｒｅｇ ｅｘすべてを包含するために４つの構成バイナリが必要であったことになる。
【０１２１】
しかし、計算の結合を通じて、この数は３つの構成バイナリに減少されうる。２８０８において、結合されてコンパイルされたｒｅｇ ｅｘが示される。構成バイナリ２１０（６１）は、ｒｅｇ ｅｘ１０８（１）、１０８（４）、および１０８（６）を含み、構成バイナリ２１０（６２）および２１０（６３）は、重複することなく、残りの正規表現を組み入れる。追加の利点は、タスクＡ２８０４とタスクＢ２８０６間を切り替える場合に、４つではなく、１つの再構成しか必要ないということである。
【０１２２】
図２９は、重複するかまたは類似する部分を有する正規表現のスーパーセットを示す概略図２９００である。上記のように、ｒｅｇ ｅｘの重複または類似する部分は網掛けで示される。２９０２において、実行のための正規表現が示される。ｒｅｇ ｅｘ１０８（１）、１０８（２）、および１０８（３）は、実行を待っている。ここで示されるように、ｒｅｇ ｅｘ１０８（２）の一部は、ｒｅｇ ｅｘ１０８（１）と類似している。たとえば、ｒｅｇ ｅｘ１０８（１）がストリング「ｈｏｍｅ ｍｏｒｔｇａｇｅ」用であり、ｒｅｇ ｅｘ１０８（２）がストリング「ｒｅｆｉｎａｎｃｉｎｇ およびｅｑｕｉｔｙ ｆｒｏｍ ｙｏｕｒ ｈｏｍｅ ｍｏｒｔａｇｅ」用であると仮定する。したがって、１０８（２）は、ストリング「ｈｏｍｅ ｍｏｒｔｇａｇｅ」の一部の、１０８（１）と類似する部分を含み、それは影付きで示される。
【０１２３】
コンパイルモジュール１１２によるコンパイル中に、類似または同一の部分は結合される。２９０４において、パックされてコンパイルされた正規表現のスーパーセットが示される。構成バイナリ２１０（７１）内に、ｒｅｇ ｅｘ１０８（２）が、１０８（１）に共通な部分、１０８（３）、およびＣＣ３０６（１）と共に示される。同じ作業がｒｅｇ ｅｘ１０８（２）の共通部分によって行なわれるので、ｒｅｇ ｅｘ１０８（１）は構成バイナリ２１０（７１）に含まれていない。実行後、ＰＨＳＣ１１４は、結果を分離して、それらを１０８（１）がプログラマブルハードウェアで別々に実行されたかのように返す。
【０１２４】
スーパーセットにより、実行に必要な計算リソースの低減が可能になる。スーパーセットはまた、より多くの等価の正規表現を、より少ない構成バイナリで実行できるようにすることで、再構成の必要性を減少させる。
【０１２５】
異種のＦＰＧＡの処理
システム１０２内のプログラマブルハードウェア１１８は、同一である必要はないか、またはビットストリーム互換でさえなくてもよい。システム１０２は、さまざまなサイズ、速度、グレード、製造業者、オンボードメモリ容量などのデバイスを含むことができる。異種ハードウェアが存在する場合、プログラマブルハードウェアデバイス１１８は、既存のｒｅｇ ｅｘ配分、およびデバイスのワークロード（他のデバイスよりも使用されることが少ないデバイスもある）、およびｒｅｇ ｅｘ優先度に応じて使用の対象とされてもよい。
【０１２６】
対象となるプログラマブルハードウェア１１８の選択は、複数の因子に影響を及ぼす。それらの因子は、異なるハードウェアに基づくリソース要件の推定の変動を含む。たとえば、ある製造業者が他の製造業者とは異なる基本論理素子を使用し、その結果ｒｅｇ ｅｘがプログラマブルハードウェア１１８で実施される方法に差異が生じることもある。
【０１２７】
対象となるプログラマブルハードウェア１１８の選択により影響を受けるもう１つの因子は、パッキング能力である。パッキング能力は、プログラマブルハードウェア１１８の容量を反映する。たとえば、より大きいデバイスは、小さいデバイスよりも多くのｒｅｇ ｅｘを保持することができる。これは、複数の構成にわたりｒｅｇ ｅｘが分割されうる場所および方法に影響を及ぼす。
【０１２８】
部分的なｒｅｇ ｅｘをマップするための実現可能性もまた、対象プログラマブルハードウェアの決定中に影響を受けることがある。たとえば、時として、中間データのサイズが入力コーパスデータとほぼ同じ規模である場合、オンボードメモリはパフォーマンスにとって有益となりうる。そのような状況において、対象プログラマブルハードウェアの決定は、ハードウェアがそれを処理する実現可能性を考慮に入れることができる。
【０１２９】
システムコントローラの操作は、さまざまなデバイスがさまざまなコマンドで制御されうることを考えると、対象プログラマブルハードウェアによっても影響を受ける。最終的に、仮想化の「ポータビリティ」は、対象となるプログラマブルハードウェアの差異により影響を受ける。たとえば、スペアリングまたは再配分のような、フォールトトレランスを迅速に調整することに関して、本来故障したデバイスに割り振られるｒｅｇ ｅｘは、再コンパイルを行なうことなく他のビットストリーム互換のプログラマブルハードウェアに移行することができる。
【０１３０】
構成の事前取り出し／ページング
複数のアプリケーションまたはユーザが同じ物理プラットフォームを共有する場合、固有の構成バイナリ２１０またはサブエレメントの呼び出しが予測されることもある。したがって、構成バイナリは、メモリ事前取り出しおよび投機的実行と類似する方法でプリロードされてもよい。
【０１３１】
ＦＰＧＡとの直接通信
前述のように、一部の実施態様において、ＰＨＳＣ１１４は、ユーザとの間のスケジューリングおよびデータフローを処理することができる。次いで、プログラマブルハードウェア１１８は、入力データの再生、出力データの再配列、再構成の順序付けなどを処理する機能を含むことができる。この実施態様におけるプログラマブルハードウェア１１８は、状態情報を格納するための追加の外部メモリを必要とすることがある。
【０１３２】
もう１つの実施態様において、プログラマブルハードウェア１１８は、自ら、最初に入力データの受信を最初に処理することができる。この実施態様において、プログラマブルハードウェア１１８は、入力データを受信し、現在ロードされている計算論理１２０による検索の実行を開始する。プログラマブルハードウェア１１８は、入力データを、ソフトウェアで実行しているＰＨＳＣ１１４の一部に中継して返す。ＰＨＳＣ１１４のこのソフトウェアベースの部分は、データの再生、出力データの再配列、およびプログラマブルハードウェア１１８の再構成に責任を負う。
【０１３３】
結論
例示の方法の特定の詳細は、本明細書において提示される図面およびその他の流れ図に関して説明されるが、図面に示される特定の動作が説明されている順序で実行される必要はなく、変更されてもよく、および／または状況に応じて全体が省略されてもよいことを理解されたい。本出願において説明されるように、モジュールおよびエンジンは、ソフトウェア、ハードウェア、ファームウェア、またはそれらの組み合わせとして実施されてもよい。さらに、説明される動作および方法は、コンピュータ、プロセッサ、またはメモリに格納された命令に基づくその他のコンピューティングデバイスにより実施されてもよく、メモリは１つまたは複数のコンピュータ可読ストレージ媒体（ＣＲＳＭ）を備える。
【０１３４】
ＣＲＳＭは、格納されている命令を実施するためにコンピューティングデバイスによってアクセス可能な任意の使用可能な物理媒体であってもよい。ＣＲＳＭは、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、電気的消去再書き込み可能読み出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュメモリその他のソリッドステートメモリ技術、コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）またはその他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたはその他の磁気記憶装置、もしくは望ましい情報を格納するために使用することができ、コンピューティングデバイスによってアクセスすることができる任意の他の媒体を含むことができるが、これらに限定されることはない。
【技術分野】
【０００１】
本発明は、仮想化超並列プログラマブルハードウェアによる正規表現の検索に関する。
【背景技術】
【０００２】
正規表現検索は、電子メールスパムフィルタリングおよびネットワーク侵入検出から一般的な調査に至るまで、多種多様なアプリケーションに共通する操作である。正規表現（「ｒｅｇ ｅｘ」または「ＲＥ」）は、特定の文字、単語、または文字のパターンのような、関心対象のストリングを識別するための簡潔で柔軟な手段をもたらす。たとえば、テキストファイルを解析する場合の「＊ｃａｒ＊」の正規表現は、「ｃａｒ」、「ｃａｒｔｏｏｎ」、「ｖｉｃａｒ」などを識別することができる。
【０００３】
従来より、ｒｅｇ ｅｘｓは、ソフトウェアベースまたはハードウェアベースの検索ソリューションを使用して実行されてきた。残念なことに、それらのソリューションは、膨大な数の複合検索を実行する場合には問題に遭遇する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ソフトウェアベースの検索では、スループットに関連する根本的な問題が生じる。プロセッサベースのシステムは、原則的に任意の複合検索を大量に実行できるその柔軟性ゆえに普及しているが、その速度は、検索の数および複雑さが増大するにつれて低下し一貫性を失う。言い換えれば、膨大量のデータ（「コーパス」）でのｒｅｇ ｅｘ検索は、実際的ではない。
【０００５】
一方、既存のハードウェアベースの検索ソリューションは、適応能力に根本的な問題がある。これらのシステムは、システム自体にマップすることができる検索に対しては高速で一貫性のあるパフォーマンスを備えることができるが、既存のデバイスには、詳細な専門知識と手操作による介入なしでサポート可能な検索の数および複雑さに関して厳しい制限がある。言い換えれば、ハードウェア検索は高速であるが、制限されている。
【０００６】
したがって、正規表現検索のようなアルゴリズムのハードウェアベースの処理に、ソフトウェアと同様の柔軟性をもたらすことを求める切迫した需要がある。
【課題を解決するための手段】
【０００７】
この課題を解決するための手段は、後段の発明を実施するための形態においてさらに説明される一連の概念を簡略化された形態で示すために提供される。この課題を解決するための手段は、請求項に係る主題の重要な特徴または基本的特徴を特定することを意図するものではなく、また請求項に係る主題の範囲を限定するために使用されることを意図するものでもない。
【０００８】
正規表現を含む（ただし、これに限定されることはない）計算タスクは、対応する論理および状態方程式に変換することができる。論理および状態方程式を実行するためにどのくらいのプログラマブルハードウェアデバイスが必要であるかなど、物理リソース要件は、コンピュータ支援設計（ＣＡＤ）ツールを通じて反復の試行錯誤を行なうことなく推定されてもよい。推定された後、計算タスクはセットに配分されてもよく、そこで各セットは個々の使用可能な物理リソース内に収まる。たとえば、計算タスクのセットは、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）のような、プログラマブルハードウェアデバイスに収まることができる。制御および通信論理が各セットに追加されてもよく、ハードウェア定義言語（ＨＤＬ）ファイルは、各セットに対して生成される。複数のＨＤＬファイルにわたる計算タスクの分割方法、ＨＤＬファイルの実行シーケンスなどを詳述する構成仕様も生成されてもよい。各ＨＤＬファイルから、構成バイナリが生成されてもよい。次いで、プログラマブルハードウェアデバイスは、構成バイナリを実行する。
【０００９】
ユーザインターフェイスは、ユーザを、タスク管理の複雑さ、構成バイナリの作成、構成バイナリにわたる計算タスクの配分などから隔離する。プログラマブルハードウェアの速度および再構成可能性を併せ持つ簡単なユーザインターフェイスは、正規表現検索の実際の実施および実行をユーザに意識させないようにする。プログラマブルハードウェアの面倒な手操作による構成に代わって、自動化システムは、ユーザのために構成バイナリを生成し、それらを実行して、結果の整理統合を管理する。
【００１０】
信頼性を向上させるためのフォールトトレランスのサポートは、再配分、スペアリングなどを含む。パフォーマンスの向上は、フラグメンテーションの緩和および優先順位付けを通じて可能となる。
【図面の簡単な説明】
【００１１】
詳細な説明は、添付の図面を参照して示される。図面において、参照番号の左端の数字（複数可）は、参照番号が最初に出現する図面を識別する。異なる図面において同じ参照番号が使用される場合、それは類似または同一の項目を指示する。
【００１２】
【図１】正規表現処理システムの保持に適したアーキテクチャの選択されたコンポーネントを示すブロック図である。
【図２】図１から選択されたコンパイルモジュールのコンポーネント、およびコンパイルモジュールにより生成されうる構成情報を示すブロック図である。
【図３】図１のアーキテクチャにより生成される構成バイナリの選択されたコンポーネントを示すブロック図である。
【図４】図１のアーキテクチャにより生成される構成仕様の選択されたコンポーネントを示すブロック図である。
【図５】図１のアーキテクチャから選択されたプログラマブルハードウェアシステムコントローラ（ＰＨＳＣ）のコンポーネントを示すブロック図である。
【図６】ＰＨＳＣによる構成バイナリの実行を示す流れ図である。
【図７】構成バイナリからの状態情報の格納を含む、ＰＨＳＣによる構成バイナリの実行を示す流れ図である。
【図８】正規表現処理システムとのユーザ対話を示す流れ図である。
【図９】正規表現に基づく構成情報の生成を示す流れ図である。
【図１０】正規表現のセットに対する物理リソース要件の推定を示す流れ図である。
【図１１】プログラマブルハードウェアにおける生成された構成の実行を示す流れ図である。
【図１２】正規表現の動的な変更を示す流れ図である。
【図１３】残りの機能可能なプログラマブルハードウェアデバイスに構成バイナリを再配分することによるフォールトトレランスのサポートを示す流れ図である。
【図１４】残りの機能可能なプログラマブルハードウェアデバイスに構成バイナリを再配分することによるフォールトトレランスのサポートを示す流れ図である。
【図１５】残りの機能可能なプログラマブルハードウェアデバイスに構成バイナリを再配分することによるフォールトトレランスのサポートを示す流れ図である。
【図１６】予備の機能可能なプログラマブルハードウェアデバイスの使用を介するフォールトトレランスのサポートを示す流れ図である。
【図１７】予備の機能可能なプログラマブルハードウェアデバイスの使用を介するフォールトトレランスのサポートを示す流れ図である。
【図１８】予備の機能可能なプログラマブルハードウェアデバイスの使用を介するフォールトトレランスのサポートを示す流れ図である。
【図１９】構成バイナリにわたる正規表現のフラグメンテーション緩和を示す概略図である。
【図２０】コンパイルリソースが制限されている場合のような、正規表現の一部および対応する構成バイナリの選択的な再コンパイルによるフラグメンテーション緩和を示す概略図である。
【図２１】正規表現の優先度を認識するハードウェア割り当て、ならびにそれらの正規表現の構成バイナリへのパッキングおよびスケジューリングを示す概略図である。
【図２２】構成バイナリの実行を再配分することによるアイドルプログラマブルハードウェアリソースの再利用を示す流れ図である。
【図２３】構成バイナリおよびその内部の正規表現の優先順位付けを示す流れ図である。
【図２４】構成バイナリおよびその内部の正規表現の優先順位付けを示す流れ図である。
【図２５】コンパイルおよび実行における複数のユーザ／アプリケーションによる正規表現のマージを示す流れ図である。
【図２６】構成バイナリの遅延構成ページングを示す流れ図である。
【図２７】後に完全な構成バイナリを作成するよう結合されうる構成バイナリサブエレメントのコンパイルを示す流れ図である。
【図２８】正規表現を結合する計算を示す概略図である。
【図２９】重複するかまたは類似する部分を有する正規表現のスーパーセットを示す概略図である。
【発明を実施するための形態】
【００１３】
正規表現（「ｒｅｇ ｅｘ」または「ＲＥ」）は、特定の文字、単語、または文字のパターンのような、関心対象のストリングを識別するための簡潔で柔軟な手段をもたらす。たとえば、テキストファイルを解析する場合の「＊ｃａｒ＊」の正規表現は、「ｃａｒ」、「ｃａｒｔｏｏｎ」、「ｖｉｃａｒ」などの単語を識別することができる。
【００１４】
正規表現検索は、要求していない広告電子メール（「スパム」）フィルタリングから一般的な調査に至るまで、多種多様な分野において幅広く使用される。たとえば、電子メールサーバは、所与の電子メールがスパムであるかどうかを決定するために、「ｍｏｒｔｇａｇｅ」または「ｃｒｅｄｉｔ ｃａｒｄ」または「ｅｎｈａｎｃｅｍｅｎｔ」の出現をすべて検索することができる。もう１つの例において、医師は、癌の素因を指示する「ＧＧＣＣＣＡＧＣＡＴＡＧＡＴＴＡＣＡ」という配列を見つけるために患者のＤＮＡを調べることができる。したがって、ｒｅｇ ｅｘは、多くの用途において有用なツールである。残念なことに、前述のように、ｒｅｇ ｅｘを実施する従来の方法には、ソフトウェアにおいては遅い速度、またはハードウェアにおいては処理されるｒｅｇ ｅｘの変化に対して適応能力が限られているという深刻な欠点があった。
【００１５】
本開示において、正規表現は、プログラマブルハードウェアデバイスで実行するための対応する論理および状態方程式に自動的に変換される。この自動変換のプロセスの一環として、各正規表現を実行するために必要なプログラマブルハードウェアのサイズは、厄介な試行錯誤を行なうことなく推定されてもよい。一部の実施形態において、コンパイルレポートから派生したフィードバックを使用する、および実際のリソース利用率を使用して構成を変更するなどのような、自動制御の下で試行錯誤が使用されてもよい。推定された後、正規表現はセットに配分されてもよく、そこで各セットは個々のプログラマブルハードウェアデバイスの物理リソースの制約の範囲内に収まる。たとえば、５００の正規表現のセットは、特定のＦＰＧＡ内に収めることができる。
【００１６】
通信および制御（ＣＣ）論理は各セットに追加されてもよく、それによりプログラマブルハードウェアがコントローラと通信して、プログラマブルハードウェアでの実行を管理することができるようになる。プログラマブルハードウェアは、イーサネット（登録商標）のようなデータネットワーク、ＰＣＩ（ｐｅｒｉｐｈｅｒａｌ ｃｏｍｐｏｎｅｎｔ ｉｎｔｅｒｃｏｎｎｅｃｔ）のような入出力バスインターフェイス、またはＨｙｐｅｒＴｒａｎｓｐｏｒｔコンソーシアムにより記述されているＨｙｐｅｒＴｒａｎｓｐｏｒｔ（商標）のような中央演算処理装置バスベースのインターフェイスを介してコントローラと通信することができる。コンパイラは、各セットに対して、正規表現およびＣＣ論理を含むハードウェア定義言語（ＨＤＬ）ファイルを生成する。コンパイラはまた、複数のＨＤＬファイルにわたる正規表現の配分、実行シーケンスなどを詳述する構成仕様も生成することができる。ＣＡＤツールは、各ＨＤＬファイルから構成バイナリを生成することができる。次いで、プログラマブルハードウェアデバイスは、構成バイナリを実行することができる。
【００１７】
実行中、各プログラマブルハードウェアデバイス内の正規表現は並列で実行するので、大幅な速度の増大をもたらす。たとえば、特定のＦＰＧＡ内に収まる前述の５００の正規表現のセットは、ＦＰＧＡ内で並列に実行される。
【００１８】
（構成バイナリの形態の）異なるセットは、プログラマブルハードウェアデバイスで順次にロードされて実行される。それにより、使用可能なプログラマブルハードウェアの容量を通常であれば超えるであろう正規表現検索を行なうことが可能になる。たとえば、前述の第１のセットは５００の正規表現を有するが、第２のセットは３００の正規表現を有する。合わせると、それらの８００の正規表現は、単一のプログラマブルハードウェアデバイスにとっては大量過ぎる。しかし、２つの構成バイナリに分割して、順次に実行される場合、単一のプログラマブルハードウェアデバイスは、８００の正規表現全体を実行することができる。
【００１９】
ユーザインターフェイスは、ユーザが、タスク管理の複雑さ、構成バイナリの作成、構成バイナリにわたる配分などを見なくてすむようにする。この簡単なユーザインターフェイスにより、プログラマブルハードウェアの速度および再構成可能性を活用して、正規表現をデータのコーパスと比較するような計算タスクの実行の大幅な増大をもたらすことができる。
【００２０】
プログラマブルハードウェアを使用してｒｅｇ ｅｘを実行することは、２つの利点をもたらす。第１は、プログラマブルハードウェアによって提供される並列操作により、システムの容量が、プログラマブルハードウェアデバイス自体の容量と相関することである。したがって、プログラマブルハードウェアベースのソリューションが、別の構成バイナリを実行シーケンスに追加する必要が生じるまで、一定のスループットを備えることが可能である。たとえば、ＦＰＧＡ内に収まりうる３００の表現によるセットは、同じＦＰＧＡに収まる上記の５００の表現と同時に実行する。これは、３００の表現の場合よりも５００の表現のほうが評価に多くの時間を要するように、パフォーマンスが所望の検索の数に関して線形に低下（または悪化）するソフトウェアのソリューションとは対照的である。
【００２１】
プログラマブルハードウェアベースの正規表現検索がもたらす第２の利点は、プログラマブルハードウェアで構成される回路が確定的パフォーマンスを提供することである。前述のように、プログラマブルハードウェアデバイス内に収まるように構成された正規表現のセットは、既知の時間で実行する。これとは対照的に、プロセッサで稼働しているソフトウェアのスループットは、所望される検索の特性（多少複雑な検索）および入力データの特性（低いヒット率の入力ストリームに対する高いヒット率の入力ストリーム）によって異なる可能性がある。加えて、キャッシュミスのような、その他の予測不能なイベントがパフォーマンスに変化をもたらすことがある。
【００２２】
再配分、スペアリングなどが、フォールトトレランスを可能にする。パフォーマンスは、選択的または完全な再コンパイルを通じた取り消しまたは変更から正規表現のフラグメンテーションを緩和することにより保持される。正規表現はまた、パッキング、スケジューリング、および実行順序付けを通じてさまざまに変化する優先度レベルを割り当てられてもよい。
【００２３】
例示のアーキテクチャ
図１は、正規表現処理システム１０２の実施に適したアーキテクチャの選択されたコンポーネントを示すブロック図１００である。限定の目的ではなく説明のために、会社が、一般に「スパム」として知られる要求していない広告電子メールをその電子メールサーバからフィルタリングしようとしていると仮定する。スパムに関連付けられていたストリングを組み入れる正規表現のセットが保持される。たとえば、「ｍｏｒｔｇａｇｅ ｒａｔｅ」および「ｃｒｅｄｉｔ ｃａｒｄ」といった語句は、スパム電子メールを指示すると決定されている。システムアドミニストレータまたはスパムユーティリティアプリケーションは、それらの語句に対する正規表現を生成する。
【００２４】
会社のサーバでの電子メールの収集は、潜在的なスパムを除去するために正規表現（ｒｅｇ ｅｘ）のこのリストを使用してフィルタされるデータのコーパスを形成する。実際には、そのようなｒｅｇ ｅｘのリストは、数千から数百万にさえも及ぶことがある。現在のソフトウェアのみの正規表現検索に必要とされる計算要件を考えれば、これは重大なサーバの負荷をもたらし、それに応じてタスク、出力、冷却などに割り振られるサーバのようなリソース要件の増大もまねく。
【００２５】
正規表現処理システム１０２内には、メモリ１０６に格納されているモジュールを実行するように構成されたプロセッサ１０４があってもよい。一部の実施形態において、プロセッサ１０４は、多重コアプロセッサ、または複数プロセッサの集合であってもよい。正規表現処理システム内にはまた、メモリ１０６があってもよい。メモリ１０６は、正規表現１０８（１）、１０８（２）、．．．、１０８（Ｒ）を格納することができる。本出願の図１から図２９において使用される、「（Ｒ）」または「（Ｐ）」のような括弧で囲まれた文字は、ゼロよりも大きい任意の整数を示す。これらの正規表現は、それらを表すブロックの可変サイズによって指示されるように、さまざまなサイズおよび／または複雑さであってもよい。
【００２６】
また、メモリ１０６内には、正規表現を受け入れて、同様にメモリ１０６にあるコンパイルモジュール１１２により処理するためにそれらの正規表現を搬送するように構成されたユーザインターフェイス１１０もある。コンパイルモジュール１１２は、プログラマブルハードウェアでのロードおよび実行に適した構成情報を生成するように構成され、後段で図２に関してさらに詳細に説明される。
【００２７】
コンパイルモジュール１１２は、プログラマブルハードウェアシステムコントローラ（ＰＨＳＣ）１１４と通信し、メモリ１０６に格納されてもよい。ＰＨＳＣ１１４は、プログラマブルハードウェアの操作を管理するように構成され、後段で図５に関してさらに詳細に説明される。ＰＨＳＣ１１４は、ソフトウェアモジュールとして（示されるように）、ハードウェアデバイスとして、または組み合わせとして実行されてもよい。
【００２８】
ＰＨＳＣ１１４はまた、処理のためにメモリ１０６内のコーパスデータ１１６またはその他の外部データを受け入れるように構成される。一部の実施態様において、このコーパスデータは、正規表現が実行されるべき情報を含むことができる。たとえば、正規表現として表されるスパム語句が検索される電子メールメッセージの集合。
【００２９】
ＰＨＳＣ１１４は、プログラマブルハードウェア１１８（１）、１１８（２）、．．．、１１８（Ｐ）と通信する。プログラマブルハードウェア１１８は、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、複合プログラマブル論理デバイス（ＣＰＬＤ：ｃｏｍｐｌｅｘ ｐｒｏｇｒａｍｍａｂｌｅ ｌｏｇｉｃ ｄｅｖｉｃｅ）、またはその他の再構成可能なハードウェアデバイスであってもよい。プログラマブルハードウェア１１８は、（同じ製造業者による同じモデルのＦＰＧＡのように）類似していても、（異なる製造業者によるＦＰＧＡのように）異なっていてもよい。各プログラマブルハードウェア１１８内には、正規表現１０８（１）〜（Ｒ）のプログラマブルハードウェア内の物理的な具現ならびに任意の必須の通信および制御（ＣＣ）論理である１つまたは複数の計算論理ブロック１２０（１）、１２０（２）、．．．、１２０（Ｌ）があってもよい。
【００３０】
ＰＨＳＣ１１４は、計算論理１２０を作成するプログラマブルハードウェア１１８に構成をロードする。計算論理１２０が実行した後、プログラマブルハードウェア１１８内のＣＣ論理は、その結果をＰＨＳＣ１１４に転送することができ、次いでＰＨＳＣ１１４は結果１２２をメモリ１０６またはその他の外部データ宛先に出力することができる。プログラマブルハードウェアデバイス１１８で実行するための構成に含まれてはいない正規表現１０８は、補助の正規表現処理モジュール１２４において実行されてもよい。たとえば、新しく追加されたスパム語句「ｒｏｏｆｉｎｇ ｒｅｐａｉｒ」は、正規表現のリストに追加されてもよいが、ハードウェア実行のために構成バイナリにコンパイルされなくてもよい。コンパイルされるまで、この新しく追加されたスパム語句の正規表現は、補助の正規表現処理モジュール１２４を使用して処理されてもよい。補助の正規表現処理モジュール１２４は、メモリ１０６に格納されてもよく、コンパイルモジュール１１２およびＰＨＳＣ１１４と通信してもよい。
【００３１】
並列に正規表現を実行するように構成されたプログラマブルハードウェア１１８のパフォーマンスの利点を考えれば、プログラマブルハードウェア１１８は、課せられた要求をゆうに超えることができる。その結果、プログラマブルハードウェア１１８が十分に活用されない場合もある。プログラマブルハードウェア１１８を動的に再構成することにより、過剰なパフォーマンスと交換に仮想容量を提供することが可能になる。その結果、より小さいプログラマブルハードウェアデバイスが使用されてもよい。または、単一のプログラマブルハードウェアがもはやｒｅｇ ｅｘ１０８（１）〜１０８（Ｒ）のすべてを含むことができなくなるところまで要求が高まる場合、ｒｅｇ ｅｘは複数の計算論路１２０（１）〜１２０（Ｌ）を作成するように分割され、逐次ロードされて実行されてもよい。計算論理の逐次実行は若干遅いが、プログラマブルハードウェア１１８の容量を超える計算論理をロードする場合に生じるであろう完全故障をはるかにしのぐ。
【００３２】
正規表現処理システム１０２はまた、サーバ、ワークステーション、ネットワーク接続ＦＰＧＡデバイスなどのような他のデバイスと通信するように構成可能なネットワークインターフェイス１２６を組み入れることもできる。
【００３３】
図２は、図１から選択されたコンパイルモジュール１１２のコンポーネントを示すブロック図２００である。正規表現１０８（１）〜１８０（Ｒ）は、ユーザインターフェイス１１０などを介して、コンパイルモジュール１１２に提供される。コンパイルモジュール１１２は、正規表現を、プログラマブルハードウェア１１８により実行可能な形態にコンパイルするように構成される。正規表現−ハードウェア定義言語（ＨＤＬ）コンパイラ２０２は、正規表現１０８のＨＤＬ表現を生成する。
【００３４】
ハードウェア定義言語（ハードウェア記述言語としても知られる）は、計算を実行するように構成されたデジタル論理および電子回路の記述を表す。コンピュータコードがアルゴリズムを表す場合、ＨＤＬステートメントは実際の回路素子を表す。
【００３５】
米国電気電子学会（ＩＥＥＥ）規格ＩＥＥＥ１０７６によって説明されるように、１つのＨＤＬは、超高速集積回路ハードウェア記述言語（ＶＨＤＬ）である。もう１つのＨＤＬは、ＩＥＥＥ規格１３６４−２００１に説明されているＶｅｒｉｌｏｇである。その他のＨＤＬも使用可能であり、同様に使用されてもよい。
【００３６】
正規表現−ＨＤＬコンパイラ２０２がｒｅｇ ｅｘ１０８をコンパイルしてＨＤＬファイルを生成すると、構成仕様２０４（１）、２０４（２）、．．．、２０４（Ｓ）は、コンパイルの結果得られた情報に基づいて生成されてもよい。構成仕様は、構成バイナリにわたり配分されるｒｅｇ ｅｘ１０８の数などのような詳細を含み、後段で図４に関してさらに詳細に説明される。
【００３７】
コンパイラ２０２は、ＨＤＬファイル２０６を、プログラマブルハードウェアのコンピュータ支援設計（ＣＡＤ）ツール２０８に提供する。このＣＡＤツール２０８は、ＨＤＬファイル２０６を受け入れ、プログラマブルハードウェアデバイス１１８による実行に適した構成バイナリ２１０（１）、２１０（２）、．．．、２１０（Ｂ）を生成する。参照を簡単にするために、構成仕様２０４および構成バイナリ２１０は、構成情報２１２とみなされてもよい。１つの実施態様において、複数の構成バイナリ２１０（１）〜２１０（Ｂ）に関連する単一の構成仕様２０４が生成されてもよい。もう１つの実施態様において、複数の構成仕様２０４（１）〜２０４（Ｓ）は、複数の構成バイナリ２１０（１）〜２１０（Ｂ）に対応して生成されてもよい。一部の実施態様において、構成情報２１２（１）、２１２（２）、．．．、２１２（Ｆ）があってもよい。
【００３８】
図３は、図１のアーキテクチャにより生成される例示の構成バイナリの選択されたコンポーネントを示すブロック図３００である。この図において、破線３０２は、プログラマブルハードウェア１１８の容量の輪郭を描いている。構成バイナリ２１０内、およびこの容量３０２内には、コンパイルモジュール１１２によって生成されたバイナリ構成命令のような、バイナリ構成命令３０４として表現されるｒｅｇ ｅｘがあってもよい。さらに、構成バイナリ２１０に含まれるのは、ＰＨＳＣ１１４とプログラマブルハードウェアデバイス１１８との結合を可能にするように構成された通信および制御（ＣＣ）論理３０６であってもよい。一部の実施態様において、ローカル状態ストレージ３０８もまた、構成バイナリ２１０内に提供されてもよい。
【００３９】
この図において、構成バイナリ２１０（１）は、ｒｅｇ ｅｘ１０８（１）、１０８（２）、１０８（６）、およびＣＣ３０６（１）を含む。構成バイナリ２１０（２）は、ｒｅｇ ｅｘ１０８（３）、１０８（４）、およびＣＣ３０６（２）を含む。構成バイナリ２１０（３）は、ｒｅｇ ｅｘ１０８（５）、ローカル状態ストレージ３０８（１）、およびＣＣ３０６（３）を含む。ｒｅｇ ｅｘは、内部の正規表現のサイズ／複雑さの相違を示すように、異なる幅で表されていることに留意されたい。したがって、ｒｅｇ ｅｘ１０８（５）は、使用可能な計算論理容量のほとんどを必要とするので、構成バイナリ２１０（３）内の唯一のｒｅｇ ｅｘである。
【００４０】
各構成バイナリ２１０は、内部のｒｅｇ ｅｘが並列実行のために設計されるように構成されてもよい３１０。たとえば、構成バイナリ２１０（１）がプログラマブルハードウェア１１８において実行されると、ｒｅｇ ｅｘ１０８１０８（１）、１０８（２）、および１０８（６）が並列に実行される。ハードウェアにおいて複数のｒｅｇ ｅｘを並列に実行できるこの機能は、結果として単一プロセッサ上で順次に実行するソフトウェアにまさる重大な速度の増加をもたらす。図１の例に戻ると、プログラマブルハードウェア１１８による構成バイナリ２１０（１）の実行は、ソフトウェアで行なわれる逐次処理とは対照的に、３つのｒｅｇ ｅｘの検索を一度に行なう。
【００４１】
図４は、図１のアーキテクチャにより生成される構成仕様２０４の選択されたコンポーネントを示すブロック図４００である。構成仕様２０４は、複数の情報を含むことができる。生成される構成バイナリ４０２（１）のカウントは、格納されてもよい。たとえば、コンパイルされた正規表現は、３つの構成バイナリを生成する。構成バイナリ間の正規表現の配分の記述４０２（２）もまた、格納されてもよい。たとえば、これは、ｒｅｇ ｅｘ１０８（１）、１０８（２）、および１０８（６）が構成バイナリ２１０（１）内にあることを指示することができる。構成バイナリ４０２（３）の実行のシーケンスが含まれてもよい。たとえば、構成バイナリ２１０（１）を最初に実行し、続いて２１０（３）、次いで２１０（２）が実行して、特定の正規表現の優先順位付けを説明する。以下の図２１では、優先順位付けをさらに詳細に説明する。構成仕様２０４（１）はまた、どの許可または「正当な」プログラマブルハードウェアデバイス１１８が正規表現処理システム１０２内にあるのかを含むこともできる。たとえば、現在システム内で使用可能なプログラマブルハードウェアデバイスは、製造業者ＸによるＦＰＧＡタイプＡおよびＢ、ならびに製造業者ＹによるＦＰＧＡタイプＣを含む。コンパイル日付／時間、アプリケーション識別および／またはユーザ識別などのような、その他の情報４０２（Ｙ）もまた、構成仕様２０４（１）に含まれてもよい。
【００４２】
図５は、図１のアーキテクチャから選択されたプログラマブルハードウェアシステムコントローラ（ＰＨＳＣ）のコンポーネントを示すブロック図５００である。この図において、ＰＨＳＣ１１４は、構成仕様２０４（１）および対応する構成バイナリ２１０（１）〜２１０（３）を、コーパスデータ１１６と共に受け入れる。たとえば、構成仕様は、スパム検索のために正規表現１０８（１）〜１０８（Ｒ）に対応する表現を含むことができるが、コーパスは、スパムがないかどうか確認される電子メールストアを含むことができる。
【００４３】
ＰＨＳＣ１１４は、入力を受信して、結果１２２を提供することを含む、ＰＨＳＣ１１４のアクションを協調するように構成された制御モジュール５０２を含むことができる。プログラマブルハードウェアデバイス１１８と通信して、構成バイナリのロードおよびアンロード、結果１２２の転送などのようなタスクを管理するように構成されたプログラマブルハードウェアインターフェイスモジュール５０４もまた、ＰＨＳＣ１１４に含まれてもよい。構成バイナリ順序付けモジュール５０６もまた存在してもよい。構成バイナリ順序付けモジュール５０６は、プログラマブルハードウェア１１８内の構成バイナリ２１０の処理のための実行シーケンス５０８（この説明図において破線で示される）を決定することができる。たとえば、実行シーケンス５０８は、構成バイナリ２１０（１）、構成バイナリ２１０（２）、次いで構成バイナリ２１０（３）が続いてもよい。実行シーケンス５０８は、構成仕様２０４からの構成バイナリ４０２（３）の実行のシーケンスに基づいてもよい。一部の実施態様において、実行シーケンス５０８は、優先度の変更、ハードウェアが使用できないこと、処理ロード、およびＰＨＳＣ１１４に使用可能なその他の因子により、実行のシーケンス４０２（３）とは異なっていてもよい。
【００４４】
例示の実行
図６は、プログラマブルハードウェア１１８でのＰＨＳＣ１１４による構成バイナリの実行を示す流れ図６００である。この例の場合、単一のプログラマブルハードウェアデバイス１１８（１）があり、矢印６０２により指示されるようにページを下方に進むと時間が増大すると仮定する。ｒｅｇ ｅｘ１０８（１）〜１０８（Ｒ）はコンパイルされて構成バイナリ２１０（１）〜２１０（Ｂ）を形成し、構成バイナリ２１０（１）〜２１０（Ｂ）のロードおよび構成が行なわれるとプログラマブルハードウェアデバイス１１８は計算論理１２０となる。プログラマブルハードウェア１１８（１）にロードされると、計算論理１２０は、６０４内部で符号化された正規表現検索を並列に実行する。構成バイナリのシーケンスは、１つずつ構成バイナリが次々と６０６で順次にロードされ処理される。
【００４５】
たとえば、６０８において、ＰＨＳＣ１１４のプログラマブルハードウェアインターフェイスモジュール（ＰＨＩＭ）５０４は、構成バイナリ２１０（１）をプログラマブルハードウェア１１８（１）にロードする。ロードされると、プログラマブルハードウェア１１８（１）内で結果として得られる回路の物理的配列は、計算論理１２０（１）である。計算論理１２０（１）は実行し、その結果はＰＨＩＭ５０４に渡される。
【００４６】
６１０において、ＰＨＩＭ５０４は、ＰＨＳＣ１１４の実行シーケンス５０８で次の順位にあった構成バイナリ２１０（２）を、計算論理１２０（２）を形成するプログラマブルハードウェア１１８（１）にロードする。計算論理１２０（２）は実行し、その結果はＰＨＩＭ５０４に返される。
【００４７】
６１２において、ＰＨＩＭ５０４は、ＰＨＳＣ１１４の実行シーケンス５０８で次の順位にあった構成バイナリ２１０（３）を、計算論理１２０（３）を形成するプログラマブルハードウェア１１８（１）にロードする。計算論理１２０（３）は実行し、その結果はＰＨＩＭ５０４に返される。
【００４８】
このように連続的に構成バイナリをロードして結果の計算論理を実行することにより、プログラマブルハードウェアの仮想化が可能になり、仮想化計算ファブリックを作成することができる。たとえば、処理されるべきすべての正規表現を実行するのに十分な大きさのプログラマブルハードウェア１１８を個々に必要とするのではなく、ｒｅｇ ｅｘは１つまたは複数のプログラマブルハードウェアデバイス１１８にわたり実行するように分割されてもよい。使用可能なプログラマブルハードウェアデバイスが十分ではなく、同時操作ができない場合（たとえば、ｒｅｇ ｅｘの要求がプログラマブルハードウェアデバイスの使用可能容量を超える場合）、ｒｅｇ ｅｘは複数の構成バイナリにわたり配分されてもよく、次いで限られた数のプログラマブルハードウェア１１８にわたり配分されてもよい、および／または同じプログラマブルハードウェア１１８で順次に実行されてもよい。スパム検索のための８００の正規表現に関する前述の例に戻ると、８００すべてが単一のＦＰＧＡに収まるわけではないが、５００は収まる。したがって、第１の構成バイナリは５００の正規表現で作成されるが、第２の構成バイナリは残りの３００の正規表現で作成される。１つのプログラマブルハードウェア１１８デバイスが使用可能であるので、第１の構成バイナリがロードされて実行され、次いで第２の構成バイナリがロードされて実行される。
【００４９】
パフォーマンスを向上させるため、および／または一連の構成バイナリが先行のステップの結果に基づいて反復して実行できる（すなわち、パイプライン制御される）ようにするため、状態情報が格納されてもよい。図７は、構成バイナリからの状態情報の格納を伴う、ＰＨＳＣ１１４による構成バイナリの実行を示す流れ図７００である。上記で図６に関して説明されたとおり、矢印７０２により指示されるようにページを下方に進むと時間が増大する。また上記のように、この例において、構成バイナリから結果として得られた計算論理に表される正規表現は並列に実行され７０４、複数の構成バイナリは、単一のプログラマブルハードウェア１１８（１）で逐次ロードされ実行される７０６。計算論理に接続されたローカルメモリは、７０８において、または計算論理内で具現されるもう１つの実施態様において、状態情報を格納する。たとえば、計算論理に接続されたローカルメモリの１つの実施態様において、メモリは、接続されたフラッシュメモリのような、プログラマブルハードウェアデバイスに外部のメモリであってもよい。プログラマブルハードウェア１１８（１）に直接アクセス可能なメモリ７０８を使用することで、速度を増大させ、ＰＨＳＣ１１４を通じて状態を転送して格納する必要をなくす。
【００５０】
７１０において、ＰＨＩＭ５０４は構成バイナリ２１０（１）をロードし、その結果計算論理１２０（１）が得られ、これが実行して、ローカル状態情報３０８（１）をローカルメモリ７０８に格納することができる。７１２において、ＰＨＩＭ５０４は構成バイナリ２１０（２）をロードし、その結果計算論理１２０（２）が得られ、これがローカル状態情報３０８（１）にアクセスして、メモリ７０８との間で情報を読み取りおよび／または書き込みすることができる。７１４において、ＰＨＩＭ５０４は構成バイナリ２１０（３）をロードし、その結果計算論理１２０（３）が得られ、これもまたローカル状態情報３０８（１）にアクセスして、メモリ７０８との間で情報を読み取りおよび／または書き込みすることができる。したがって、情報は、構成バイナリの実行の間で持続することができる。
【００５１】
たとえば、構成バイナリ２１０（１）内のｒｅｇ ｅｘ１０８（１）はストリング「ｃａｒ」のｒｅｇ ｅｘであるが、構成バイナリ２１０（２）内のｒｅｇ ｅｘ１０８（３）はストリング「ｃａｒ ｌｏａｎ」のｒｅｇ ｅｘであり、構成バイナリ２１０（３）内のｒｅｇ ｅｘ１０８（５）はストリング「ｃａｒ ｌｏａｎ ｒｅｆｉｎａｎｃｉｎｇ」のｒｅｇ ｅｘであると仮定する。構成バイナリの実行中、状態情報３０８（１）は、構成バイナリ２１０（３）が、次に構成バイナリ２１０（１）からの結果を使用する構成バイナリ２１０（２）からの結果を使用するように、メモリ７０８に格納されてもよい。したがって、プログラマブルハードウェア１１８によって直接アクセス可能なメモリに格納されている状態情報にアクセスすることにより、処理速度が加速される。さらに、ストレージは、大きすぎて単一のプログラマブルハードウェアデバイスの容量を超えるｒｅｇ ｅｘの分割を容易にすることができる。
【００５２】
プロセスの例示
図８は、図１〜図７に示されるアーキテクチャを使用して実施されうる（ただし、必須ではない）正規表現処理システム１０２とのユーザ対話を説明する流れ図を示す。フロー８００（および図９〜図１２のフロー）は、論理フローグラフにおいてブロックの集合として示され、ブロックはハードウェア、ソフトウェア、またはその組み合わせにおいて実施されうる操作のシーケンスを表す。ソフトウェアのコンテキストにおいて、ブロックは、１つまたは複数のプロセッサによって実行される場合、列挙された操作を実行するコンピュータ実行可能命令を表す。一般に、コンピュータ実行可能命令は、特定の機能を実行するか、または特定の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造体などを含む。操作が説明される順序は、限定として解釈されることを意図されておらず、任意の数の説明されるブロックは、任意の順序および／または並列に組み合わされてプロセスを実施することができる。説明のために、プロセスは、図１〜図７のアーキテクチャのコンテキストで説明される。
【００５３】
ブロック８０２は、正規表現のリストを受信する。たとえば、正規表現として表されるスパム検索基準のリスト。ブロック８０４は、正規表現に基づいて構成情報を生成する。これは、図９に関して後段でさらに詳細に説明される。
【００５４】
ユーザには、ブロック８０６において明示または暗黙のいずれのユーザインターフェイスが選択されているかに応じて異なるインターフェイスが表示される。ブロック８０６において暗黙ユーザインターフェイスが選択されると、ブロック８０８は、生成された構成情報をプログラマブルハードウェアで実行する。ブロック８１０は、プログラマブルハードウェアからの結果を提供する。
【００５５】
ブロック８０６において暗黙ユーザインターフェイスが選択されると、ブロック８１２は、構成情報（構成仕様２０４および構成バイナリ２１０（１）〜２１０（Ｒ））を検査および／または変更のためにユーザに提示する。たとえば、自動的に生成された構成バイナリを手操作で調整したいと考えるユーザは、明示インターフェイスを選択することができる。この提示が完了すると、フローはブロック８０８において再開し、前述のように、生成された構成情報をプログラマブルハードウェアで実行することができる。
【００５６】
選択されたインターフェイスには関わりなく、このユーザインターフェイスは、ｒｅｇ ｅｘの複雑さとは無関係にプログラマブルハードウェアとの単純な対話をもたらす。そうすることで、ユーザは、プログラマブルハードウェアの詳細を認識する必要、または気に掛ける必要からも解放される。さらにこれは、異なるプログラマブルハードウェア１１８にわたる検索ポータビリティをもたらす。たとえば、ｒｅｇ ｅｘ１０８（１）〜１０８（Ｒ）は、異なるプログラマブルハードウェアデバイス１１８（１）〜１１８（Ｐ）にわたり実行するようにコンパイルされて、処理に使用可能になるとそれらのプログラマブルハードウェアデバイスにわたり配分されてもよい。このインターフェイスを使用することで、この複雑さをユーザの目から隠す。
【００５７】
図９は、図８に関して上記で述べた、正規表現８０４に基づく構成情報の生成を表す流れ図を示す。ブロック９０２は、正規表現のリストを解析し、それらを対応する論理および状態方程式に変換する。この変換は、前述のように、コンパイルモジュール１１２内で行ってもよい。ブロック９０４は、各正規表現の物理リソース要件を推定する。たとえば、ｒｅｇ ｅｘ１０８（１）が、プログラマブルハードウェアデバイス１１８（１）で２，０００の計算素子を必要とすると推定されることもあり、ｒｅｇ ｅｘ１０８（５）は、７，０００の計算素子を必要とすると推定されることもある。
【００５８】
ブロック９０６は正規表現をセットに配分し、ここで各セットはプログラマブルハードウェア１１８において使用可能な物理リソース内に収まる。この推定はまた、通信および制御（ＣＣ）論理、ならびにローカルストレージ要件を含むことができる。たとえば、上記の図３において、使用可能な物理リソースはプログラマブルハードウェアの計算論理容量３０２であり、セットのうちの１つはｒｅｇ ｅｘ１０８（１）、１０８（２）、１０８（６）、およびＣＣ３０６（１）を含む。
【００５９】
ブロック９０８は、各セットにカスタマイズされた制御および通信論理を追加し、ブロック９１０は、各セットに対してＨＤＬファイルを生成する。ブロック９１２は、構成仕様２０４（１）のような構成仕様を生成する。ブロック９１４は、各ＨＤＬファイルから構成バイナリを生成する。たとえば、ＨＤＬファイルは、結果として構成バイナリ２０１（１）をもたらすことができる。
【００６０】
図１０は、図９に関して前述された正規表現９０４による物理リソース要件の推定を表す流れ図を示す。ブロック１００２は、正規表現を特定の計算論理配列に関連付ける。たとえば、ストリング「ｈｏｍｅ」の正規表現は、２００の回路素子の特定の配列を伴うことがある。この関連付けは、正規表現を生成するブロック１００２（１）、ハードウェアＣＡＤツールがｒｅｇ ｅｘ内の項目を論理方程式に変換する方法を決定するブロック１００２（２）、ｒｅｇ ｅｘの回路要件を決定するブロック１００２（３）により作成されてもよい。たとえば、サンプルの正規表現は、ＣＡＤツールによる論理方程式に変換されてもよく、結果の要件が監視される。したがって、正規表現入力に基づいて回路要件の予測を可能にするモデルが構築されてもよい。
【００６１】
関連付けが行なわれると、ブロック１００４は、冗長論理を識別し、それらの冗長を除去するように統合して、統合された論理を形成する。たとえば、複数の正規表現は、共通のルートストリングを伴うか、または回路で表現される場合に冗長回路をもたらすこともあるその他の共通性を有することができる。これらの冗長性は除去することができ、効率を高めることができる。その１つの実施態様は、図２９に関して後段で、スーパーセットのコンテキストでさらに詳細に説明される。
【００６２】
ブロック１００６は、ローカル状態ストレージ３０８が呼び出されるかどうか、および呼び出される場合に必要とされるメモリリソースなどのような、ローカルストレージ要件を推定する。ブロック１００８は、ＣＡＤツール固有の修正率を統合された論理およびローカルストレージ要件に適用する。たとえば、特定のＣＡＤツールは、特定のｒｅｇ ｅｘによって呼び出された論理方程式を例外的な方法で計算ブロックに変換することができ、したがって物理リソースの推定がさらに正確になるように修正率が入力されてもよい。
【００６３】
ブロック１０１０は、推定される物理リソース要件を生成する。たとえば、「ｃｒｅｄｉｔ ｃａｒｄ」を検索するためのｒｅｇ ｅｘは、製造業者ＸによるＦＰＧＡタイプＡで推定一千の回路素子を必要とすることがある。この推定は、ｒｅｇ ｅｘがプログラマブルハードウェア１１８の物理リソース内に収まるかどうかを決定するために使用されるブルートフォースの試行錯誤と比較すると、大幅に高速で、リソース集約的ではなく、人間の対話をほとんどまたは全く必要としない。さらに、このプロセスは、さまざまな容量を備えるプログラマブルハードウェアの複数のタイプに容易に適用することができ、新しいハードウェアへのｒｅｇ ｅｘの迅速な再配置が可能になる。
【００６４】
図１１は、図８に関して前述されたプログラマブルハードウェア８０８での生成された構成情報の実行を表す流れ図である。１つの実施態様において、後続のブロックは、ＰＨＳＣ１１４によって実行されてもよい。
【００６５】
ブロック１１０２は、構成情報２１２およびコーパスデータ１１６を受信する。たとえば、構成ファイルは、スパム検索のために正規表現１０８を具現する構成バイナリ２１０を含むことができ、コーパスデータは、スパムを検索される未加工の電子メールであってもよい。
【００６６】
ブロック１１０４は、実行シーケンス５０８からの実行されていない構成バイナリをプログラマブルハードウェア１１８にロードする。ブロック１１０６は、コーパス１１６の全部または一部を処理のためにプログラマブルハードウェア１１８にロードする。ブロック１１０８は、ロードされたコーパスデータ１１６に対してプログラマブルハードウェア１１８で計算論理１２０を実行する。ブロック１１１０は、計算論理のプログラマブルハードウェアの実行からの結果を提供する。コーパスの追加の部分が残っている場合、ブロック１１１２は、フローをブロック１１０６に戻し、コーパスの別の部分を処理のためにプログラマブルハードウェア１１８にロードする。それ以外の場合で、ブロック１１１２においてコーパスの追加の部分が残っていなければブロック１１１４は、追加の構成バイナリが実行シーケンス５０８に存在するかどうかを決定する。追加の構成バイナリが実行シーケンス５０８に残っている場合、ブロック１１１６は、実行シーケンスを次の構成バイナリに増分して、フローを１１０４に戻す。追加の構成バイナリが実行シーケンス５０８に残っていない場合、ブロック１１１８は、１つまたは複数の構成バイナリの実行により得られた結果を統合する。
【００６７】
図１２は、正規表現の動的な変更を示す流れ図１２００である。ｒｅｇ ｅｘは、時間の経過に伴って変化してもよい。たとえば、インコの売れ行きの新たな一時的流行により、「ｐａｒａｋｅｅｔ」がスパム検索リストに追加されるという結果をもたらすこともある。あるいは、新種のクレジットカードビジネスが加わって、「ｃｒｅｄｉｔ ｃａｒｄ」がスパム検索リストから削除されるという結果をもたらすこともある。
【００６８】
限定の目的ではなく説明を簡単にするため、正規表現のリストへの変更は一般に、新しい正規表現の追加、または既存の正規表現の削除という２つのカテゴリに分類されると考えられてもよい。新しい正規表現が追加されるべきであるとブロック１２０２が決定する場合、ブロック１２０４は、新しい正規表現の構成バイナリを生成する。次いで、ブロック１２０６は、この構成バイナリを実行のシーケンス５０８に追加する。
【００６９】
変更は既存の正規表現の削除であるとブロック１２０２が決定する場合、ブロック１２０８は正規表現を廃棄リストに追加する。プログラマブルハードウェア１１８で計算論理１２０を実行した後、ブロック１２１０は、ｒｅｇ ｅｘからの結果を廃棄する。一部の実施態様において、この廃棄はアクティブな削除であってもよく、また他の実施態様において、廃棄されたｒｅｇ ｅｘからの結果はＰＨＳＣ１１４によってレポートされていなくてもよい。廃棄リストでｒｅｇ ｅｘの処理を続行することは無駄が多いと思われることもあるが、各構成バイナリ内のｒｅｇ ｅｘの並列処理を考えると、実際には非常に効率的である。図６に関して前述されているように、構成バイナリ内のｒｅｇ ｅｘは並列に実行される。したがって、構成バイナリが大量にフラグメント化した状態になるまでは、構成バイナリ全体を再コンパイルするよりも、多数のｒｅｇ ｅｘを並列に実行して、それらの結果のうちの１つを廃棄するほうが安価である。さらに、ユーザは、廃棄リストからｒｅｇ ｅｘを単に除去してそれを再イネーブルすることにより、以前廃棄されたｒｅｇ ｅｘを容易に復元することができる。未使用の／取り消されたｒｅｇ ｅｘにより生じたフラグメンテーションに対処するための再コンパイルをどのように、いつ行なうかについての決定は、後段で図１９〜図２０関してさらに詳細に説明される。
【００７０】
ブロック１２１２は、プログラマブルハードウェア１１８からの結果を、現在の構成に含まれていない追加の正規表現の結果でパッチする。これは、最近システムに追加されたが、まだプログラマブルハードウェア１１８での実行のために構成バイナリ２１０にはコンパイルされていないｒｅｇ ｅｘの場合のように、一部のｒｅｇ ｅｘが補助の正規表現処理モジュール１２４で実行される場合に有用となることがある。
【００７１】
ブロック１２１４は、補助の正規表現処理モジュール１２４で実行されている正規表現のような、現在の構成には含まれていない正規表現を、現在の構成に追加することができる。これらの正規表現は、実行シーケンス５０８の一部である構成バイナリ２１０に組み入れるためにコンパイルモジュール１１２によってコンパイルされてもよい。ブロック１２１６は、新しい構成バイナリの生成中に、廃棄リストに存在する正規表現を除去して、廃棄を一掃する。
【００７２】
再配分を介するフォールトトレランス
プログラマブルハードウェアデバイス１１８を含む機器は、故障することもある。図１３〜図１５は、残りの機能可能なプログラマブルハードウェアデバイスに構成バイナリを再配分することによるフォールトトレランスのサポートを示す流れ図１３００である。これらの図において、矢印１３０２により指示されるようにページを下方に進むと時間が増大する。図１３を始めとして、ＰＨＩＭ５０４は、２つのプログラマブルハードウェアデバイス１１８（１）および１１８（２）に結合されることが示される。この例の場合、プログラマブルハードウェア１１８（１）および１１８（２）がバイナリ互換である１３０４、すなわち、いずれのプログラマブルハードウェアでも再コンパイルすることなく同一の構成バイナリ２１０が実行されてもよいと仮定する。また、実行シーケンス５０８が、構成バイナリ２１０（１）、２１０（２）、２１０（３）、２１０（４）、２１０（１）、２１０（２）、２１０（３）、２１０（４）のためのものであるというように仮定する。図１３は、通常の操作１３０６を示す。通常の操作１３６０中に、１３０８において、ＰＨＩＭ５０４は、構成バイナリ２１０（１）および２１０（２）をそれぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードする。その結果得られた計算論理１２０（１）および１２０（２）は実行し、その結果はＰＨＩＭ５０４に返される。同様に、１３１０において、構成バイナリ２１０（３）および２１０（４）はロードされて実行される。１３１２において、シーケンスは繰り返し、処理のために構成バイナリ２１０（１）および２１０（２）をロードする。これは、プログラマブルハードウェアを仮想化することの汎用性を示す。４つの構成バイナリ２１０（１）〜２１０（４）は、２つのプログラマブルハードウェア１１８（１）および１１８（２）だけで実行される。
【００７３】
図１４は、この流れ図を継続して、故障の発生および移行１４０２を説明する。１３１４において、構成バイナリ２１０（３）はプログラマブルハードウェア１１８（１）に正常にロードされ、一方構成バイナリ２１０（４）のプログラマブルハードウェア１１８（２）へのロードは試みられたが、使用不可能であったために失敗した。１３１６において、構成バイナリ２１０（３）に基づいて計算論理１２（３）からＰＨＩＭ５０４に結果が返された後、ＰＨＩＭ５０４は、構成バイナリ２１０（４）を処理のためにプログラマブルハードウェア１１８（１）にロードする。
【００７４】
フローを図１５に継続して、フェイルセーフ操作１５０２が示される。プログラマブルハードウェア１１８（２）は引き続き使用不可能であり、プログラマブルハードウェア１１８（１）は、実行シーケンス５０８にリストされている構成バイナリの実行を処理する。１３１８において、プログラマブルハードウェア１１８（１）は、実行シーケンス５０８で次の順番の構成バイナリ２１０（１）をロードして実行する。１３２０において、プログラマブルハードウェア１１８（１）は構成バイナリ２１０（２）をロードして実行し、１３２２において、構成バイナリ（３）がロードされて実行され、さらに１３２４において、構成バイナリ２１０（４）がロードされて実行される。このように、実行シーケンス５０８内に存在するリストは完全に実行されており、実行シーケンス５０８によって呼び出されると続行することができる。プログラマブルハードウェア１１８（２）の損失により実行パフォーマンスは低下しているが、ｒｅｇ ｅｘ１０８（１）〜１０８（Ｒ）の処理は引き続き継続することができた。構成が仮想であるため、この動的な再配分が可能になる。スパムフィルタリングの例に戻ると、プログラマブルハードウェア１１８（２）の故障は、システムが完全に使用不可となる結果をまねくのではなく、単にスパムフィルタリングのパフォーマンスを低下させる。
【００７５】
複数のプログラマブルハードウェア１１８を有する一部の実施態様において、構成バイナリは故障に備えるために過小に割り振られてもよい。たとえば、各プログラマブルハードウェアデバイスの実行シーケンスは、後に故障中に消費されうるアイドル状態のプレースホルダを含むことができる。
【００７６】
スペアリングを介するフォールトトレランス
図１６〜図１８は、予備の機能可能なプログラマブルハードウェアデバイスの使用を介するフォールトトレランスのサポートを示す流れ図１６００を備える。上記と同様に、これらの図において、矢印１６０２により指示されるようにページを下方に進むと時間が増大する。
【００７７】
図１６を始めとして、ＰＨＩＭ５０４は、２つのプログラマブルハードウェアデバイス１１８（１）および１１８（２）に結合されることが示される。上記のように、この例の場合、プログラマブルハードウェア１１８（１）および１１８（２）がバイナリ互換である１６０４、すなわち、いずれのプログラマブルハードウェアでも再コンパイルすることなく同一の構成バイナリ２１０が実行されてもよいと仮定する。また、実行シーケンス５０８が、構成バイナリ２１０（１）、２１０（２）、２１０（３）、２１０（４）、２１０（１）、２１０（２）、２１０（３）、２１０（４）のためのものであるというように仮定する。
【００７８】
図１６は、通常の操作１６０６を示す。通常の操作１６０６中に、１６０８において、ＰＨＩＭ５０４は、構成バイナリ２１０（１）および２１０（２）をそれぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードする。その結果得られた計算論理１２０（１）および１２０（２）は実行し、その結果はＰＨＩＭ５０４に返される。同様に、１６１０において、構成バイナリ２１０（３）および２１０（４）はロードされて実行される。１６１２において、シーケンスは繰り返し、処理のために構成バイナリ２１０（１）および２１０（２）をロードする。
【００７９】
図１７は、フロー１６００を継続して、故障の発生およびスペアリング１７０２を説明する。この図において、１６１４において、プログラマブルハードウェア１１８（１）は構成バイナリ２１０（３）を正常にロードし、一方プログラマブルハードウェア１１８（２）は構成バイナリ２１０（４）をロードすることができなくなった。プログラマブルハードウェア１１８（２）が失敗したと決定すると、ＰＨＩＭ５０４は、構成バイナリ２１０（４）を備えてあった予備のプログラマブルハードウェアデバイス１１８（３）にリダイレクトすることができる。
【００８０】
図１８は、予備のプログラマブルハードウェアに構成バイナリをリダイレクトすることによる通常の操作の再開１８０２を示す図である。１６１６において、プログラマブルハードウェア１１８（１）は構成バイナリ２１０（１）をロードし、一方予備のプログラマブルハードウェア１１８（３）は構成バイナリ２１０（４）をロードした。
【００８１】
１６１８において、ＰＨＩＭ５０４は、実行シーケンス５０８に指定されているように構成バイナリをロードして実行する。したがって、構成バイナリ２１０（２）および２１０（３）は、それぞれプログラマブルハードウェア１１８（１）および１１８（３）にロードされる。１６２０において、構成バイナリ２１０（４）および２１０（１）は、それぞれプログラマブルハードウェア１１８（１）および１１８（３）にロードされ、実行シーケンス５０８を再度開始する。
【００８２】
プログラマブルハードウェア１１８のコンテキストにおけるスペアリングは、いくつかの利点をもたらす。構成バイナリが完全構成をカプセル化するので、構成バイナリはプログラマブルハードウェアに迅速にロードおよびアンロードされる。これは、サーバインスタンスを導入するために必要な操作の複雑さおよび時間とは対照的である。したがって、予備のプログラマブルハードウェアデバイスは、非常に迅速にアクセスしてサービスに参加させることができる。
【００８３】
フラグメンテーションの緩和
前述のように、時間の経過に伴って、処理されるべき正規表現のリストは変化する。スパムフィルタリングの例において、新しいｒｅｇ ｅｘは、他のｒｅｇ ｅｘが除去される間に追加される。図１９は、構成バイナリにわたる正規表現のフラグメンテーション緩和を示す概略図１９００である。１つの実施態様において、フラグメンテーション緩和は、ＰＨＳＣ１１４内で実行されてもよい。
【００８４】
この追加および除去は、時間の経過に伴って、「ライブ（生き）の」すなわち廃棄されたｒｅｇ ｅｘの中で引き続き必要なｒｅｇ ｅｘのフラグメンテーションをまねくことになる。１９０２において、複数のフラグメント化された構成バイナリが、フラグメンテーション緩和の前に示される。この図において、網掛けは、未使用の／取り消されたｒｅｇ ｅｘを示す１９０４。この例において、ｒｅｇ ｅｘ１０８（１）、１０８（３）、１０８（５）、１０８（７）、および１０８（９）は、取り消されている。たとえば、これらは、会社の新種のクレジットカードビジネスにより現在はスパムリストから削除されている「ｃｒｅｄｉｔ ｃａｒｄ」および変種のスパムフィルタに関連する可能性もある。ｒｅｇ ｅｘ１０８（２）、１０８（４）、１０８（６）、および１０８（８）は、引き続き使用されている。そのため、それらのｒｅｇ ｅｘを含む４つの構成バイナリ２１０（２０）〜２１０（２３）がフラグメント化された状態になり、わずかな望ましいｒｅｇ ｅｘの間にいくつかの未使用のｒｅｇ ｅｘが散在している。これらのフラグメント化された構成バイナリを実行することで、使用可能なプログラマブルハードウェアのリソースを浪費する。したがって、このフラグメンテーションを緩和することが望ましい。
【００８５】
１９０６において、新しく追加されたｒｅｇ ｅｘ１０８（１０）は、補助のｒｅｇ ｅｘ処理モジュール１２４で実行する。次回の構成バイナリのコンパイル中に、構成バイナリ内にスペースが使用可能である場合、ｒｅｇ ｅｘ１０８（１０）は、プログラマブルハードウェア１１８で実行するために、処理モジュール１２４での実行から構成バイナリ２１０へ転送されてもよい。
【００８６】
１９０８において、フラグメンテーション緩和後の構成バイナリが示される。未使用のｒｅｇ ｅｘは廃棄されており、１９１０において、引き続き使用されたそれらのｒｅｇ ｅｘおよびｒｅｇ ｅｘ１０８（１０）は、２つの新しい構成バイナリにコンパイルされた。４つの構成バイナリがソフトウェアにおいて１つのｒｅｇ ｅｘで実行されていたが、ここで２つの構成バイナリが実行する。
【００８７】
図１９は、すべてのアクティブなｒｅｇ ｅｘ１０８の完全な再コンパイルを示す。しかし、コンパイルは、時間およびシステムリソースの点から高価である。一部の実施態様において、完全再コンパイルをあまり頻繁には実行しない間、システムコストを最小化するために選択的に再コンパイルを行なうことが望ましいこともある。
【００８８】
図２０は、選択的な再コンパイルによるフラグメンテーション緩和を示す概略図２０００である。選択的または完全に再コンパイルするかどうかに関する決定は、コンパイル時間に対してハードウェアおよびソフトウェアの潜在的な実行効率を重み付けすることを伴う。
【００８９】
２００２において、フラグメンテーション緩和前の構成バイナリ２１０（３０）〜２１０（３３）が示される。上記のように、未使用のまたは取り消されたｒｅｇ ｅｘは網掛けで示される２００４。この例において、ｒｅｇ ｅｘ１０８（１）、１０８（３）、１０８（５）、１０８（７）、および１０８（９）は、取り消されている。ｒｅｇ ｅｘ１０８（２）、１０８（４）、１０８（６）、および１０８（８）は、引き続き使用されている。２００６において、新しく追加されたｒｅｇ ｅｘ１０８（１０）は、次の構成バイナリのコンパイルを待つ間、補助のｒｅｇ ｅｘ処理モジュール１２４で実行する。
【００９０】
この図において、コンパイル時間に対してハードウェアおよびソフトウェアの潜在的な実行効率を重み付けすることは、結果として１つの再コンパイルのリソースが使用可能になると仮定する。初期コンパイル中に生成されたリソース推定情報は取り出され、構成バイナリは最大の未使用のスペースから最小の未使用のスペースにソートされる。構成バイナリ２１０（３０）は１００％の未使用スペースを有し、構成バイナリ２１０（３１）は約６６％の未使用スペースを有し、構成バイナリ２１０（３２）は約５５％の未使用スペースを有し、構成バイナリ２１０（３３）は約３３％の未使用スペースを有する、
【００９１】
１つの実施態様において、選択的再コンパイルは、補助のｒｅｇ ｅｘ処理モジュール１２４によって実行されているｒｅｇ ｅｘ１０８（１）をハードウェアに移動し、次いでｒｅｇ ｅｘを最大の未使用スペースを持つ構成バイナリに移動することを伴うことができる。この図において、構成バイナリ２１０（３０）および２１０（３１）は、破線によって指示されるように２００８、選択的再コンパイルのために選択される。
【００９２】
アクティブなｒｅｇ ｅｘは、Ｎ個の構成（１つのコンパイルが使用可能なので、この場合はＮ＝１）が満たされるまで結合される。この図において、構成バイナリ２１０（３０）は空になると廃棄され、構成バイナリ２１０（３１）のｒｅｇ ｅｘ１０８（２）は、２０１０においてｒｅｇ ｅｘ１０８（２）と結合されて構成バイナリ２１０（３４）を生成する。２０１２において、新しくコンパイルされた構成バイナリ２１０（３４）および変更なしの構成バイナリ２１０（３２）および２１０（３３）を示す、選択的フラグメンテーション移行後の結果が表される。これは、ソフトウェアベースのｒｅｇ ｅｘの数を０に減少させ、合計ハードウェア構成の数を４から３に減少させる。したがって、最小のコンパイルリソースが使用され、しかも全体的なフラグメンテーションを軽減している。
【００９３】
タスクの優先順位付け、およびリソースの再利用
一部の実施態様において、タスクを優先順位付けすることが有益である場合がある。たとえば、今日のスパムが主に「クレジットカード」広告を扱うこともあり、したがってこの語句を見つけるように設計されるｒｅｇ ｅｘは、これらの広く行き渡る出現を素早く除去するために、より高い優先度を与えられてもよい。
【００９４】
図２１は、正規表現の優先度を認識するハードウェア割り当て、ならびにそれらの正規表現の構成バイナリへのパッキングおよびスケジューリングを示す概略図２１００である。この図において、通常の優先度のｒｅｇ ｅｘは白で指定され、中程度の優先度のｒｅｇ ｅｘは斜線で指定され、最高の優先度のｒｅｇ ｅｘは影付きである。２１０２において、実行のための正規表現が示される。それらの中で、ｒｅｇ ｅｘ１０８（１）、１０８（６）、および１０８（８）は、最高の優先度である。ｒｅｇ ｅｘ１０８（５）は中程度の優先度として設計され、残りの１０８（２）、１０８（３）、１０８（４）、１０８（７）、１０８（９）、および１０８（１０）は通常の優先度である。
【００９５】
２１０４において、パックされ、コンパイルされて、実行のために順序付けられたｒｅｇ ｅｘが示される。より高い優先度を有するｒｅｇ ｅｘは共にパックされ、一部の実施態様において、より高速なプログラマブルハードウェアデバイス１１８で実行するよう設計されるか、実行シーケンス５０８の優先度を受信するか、またはさらに頻繁な実行のために実行シーケンス５０８の複数ポイントに配置されてもよい。示されているように、構成バイナリ２１０（４１）は、すべての高い優先度のｒｅｇ ｅｘに対して十分な容量を有する。構成バイナリ２１０（４２）は、中程度の優先度のｒｅｇ ｅｘ１０８（５）を含み、使用できる残りの追加の容量があったので通常の優先度の１０８（４）も含む。構成バイナリ２１０（４１）および２１０（４２）は共に、そのより高い優先度の内容を考慮してより高速なプログラマブルハードウェアデバイスで実行するために２１０６により示されるように指定されてもよい。通常の優先度のｒｅｇ ｅｘを含む構成バイナリ２１０（４３）および２１０（４４）は、より遅いプログラマブルハードウェアデバイスで実行するように２１０８指定されてもよい。
【００９６】
構成バイナリのパッキングおよび／または構成バイナリの実行シーケンスの優先度割り当ては、特定のタスクが先に実行されて、それらの結果が後の処理に影響を及ぼすようにするか、または後の処理全体を除去するように行なわれてもよい。たとえば、「ｚｅｒｏ ｄｏｗｎ ｈｏｍｅ ｍｏｒｔｇａｇｅ ｆｉｎａｎｃｉｎｇ ｂｏｎａｎｚａ」を探すｒｅｇ ｅｘは、この項目の組み合わせがスパムメッセージのさらに容易な識別に役立つ可能性があることを前提に、「ｈｏｍｅ ｍｏｒｔｇａｇｅ」のｒｅｇ ｅｘよりも高い優先度を与えられてもよい。
【００９７】
図２２は、構成バイナリの実行を再配分することによるアイドルプログラマブルハードウェアリソースの再利用を示す流れ図２２００である。上記と同様に、この図において、矢印２２０２により指示されるようにページを下方に進むと時間が増大する。
【００９８】
この例の場合、プログラマブルハードウェア１１８（１）および１１８（２）がバイナリ互換である２２０４、すなわち、いずれのプログラマブルハードウェアでも再コンパイルすることなく同一の構成バイナリ２１０が実行されてもよいと仮定する。また、初期実行シーケンス５０８が、構成バイナリ２１０（１）、２１０（２）、２１０（３）、２１０（４）、２１０（１）、２１０（２）、２１０（３）、２１０（４）のためのものであるというように仮定する。
【００９９】
図２２０６において、通常の操作が示される。２２０８において、ＰＨＩＭ５０４は、構成バイナリ２１０（１）および２１０（２）をそれぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードする。結果が返され、２２１０において、ＰＨＩＭ５０４は、構成バイナリ２１０（３）および２１０（４）をそれぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードする。このプロセスは、初期実行シーケンス５０８全体を通過するように続行することができる。
【０１００】
しかし、それぞれ構成バイナリ２１０（２）および２１０（４）に基づく計算論理１２０（２）および１２０（４）がアイドルであると仮定する。おそらくは、それらの計算論理は中断されていたか、または計算論理１２０（１）および１２０（３）の前に完了していた。初期実行シーケンスが連続して続行していた場合、プログラマブルハードウェアリソースは、これらのアイドル構成バイナリを待つか、または中断された構成バイナリを実行して浪費されていたであろう。したがって、この例において、初期実行シーケンスは、リソースを再利用するように変更される。
【０１０１】
２２１２において、このアイドル時間の再利用は、引き続きアクティブな構成バイナリの再配分を通じて示される。したがって、２２１４において、ＰＨＩＭ５０４は、構成バイナリ２１０（１）および２１０（３）をそれぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードする。２２１６において、プログラマブルハードウェア１１８（１）および１１８（２）は、再度、構成バイナリ２１０（１）および２１０（３）に基づく計算論理１２０（１）および１２０（３）を実行する。計算論理１２０（２）および１２０（４）はアイドルであるので、これらはロードされて実行されることはない。したがって、１２０（２）および１２０（３）のような引き続き実行するよう指定されている計算論理は、アイドルまたは中断した計算論理によって妨げられることなく実行し続ける。
【０１０２】
前述のように、特定のｒｅｇ ｅｘが他のｒｅｇ ｅｘよりもさらに重要である場合、これらはさらに多くのリソースを与えられてもよい。図２３および図２４は、構成バイナリおよびその内部の正規表現の優先順位付けを示す流れ図２３００である。この図において、矢印２３０２により指示されるようにページを下方に進むと時間が増大する。プログラマブルハードウェア１１８（１）および１１８（２）は、バイナリ互換であると仮定する２３０４。
【０１０３】
図２３を参照すると、２３０６において、等しい優先度の操作が示される。任意の計算論理内のタスクには優先度が与えられない。実行シーケンス５０８は、構成バイナリ２１０（１）、２１０（２）、２１０（３）、２１０（４）、２１０（１）、２１０（２）、２１０（３）、２１０（４）などのためのものである。２３０８において、構成バイナリ２１０（１）および２１０（２）は、実行のために、それぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードされる。２３１０において、構成バイナリ２１０（３）および２１０（４）は、実行のために、それぞれプログラマブルハードウェア１１８（１）および１１８（２）にロードされる。
【０１０４】
図２４にフローを続行すると、２４０２において、構成バイナリ２１０（１）内のｒｅｇ ｅｘは高い優先度を与えられており、そのほんのわずかなタイムスライスが増大されている。したがって、実行シーケンス５０８は、構成バイナリ２１０（１）、２１０（１）、２１０（１）、２１０（１）、２１０（１）、２１０（２）、２１０（１）、２１０（３）、２１０（１）、２１０（４）を実行するように変更される。したがって、２３１２において、構成バイナリ２１０（１）は、プログラマブルハードウェア１１８（１）および１１８（２）の両方にロードされる。２３１４において、両プログラマブルハードウェア上に計算論理１２０（１）がすでに存在するので、構成バイナリはロードされず、計算論理が再度実行される。
【０１０５】
２３１６において、計算論理１２０（１）は再度プログラマブルハードウェア１１８（１）で実行し、構成バイナリ２１０（２）はプログラマブルハードウェア１１８（２）にロードされて実行される。２３１８において、計算論理１２０（１）は再度実行し、構成バイナリ２１０（３）はロードされてプログラマブルハードウェア１１８（２）で実行される。２３２０において、計算論理１２０（１）は再度実行し、構成バイナリ２１０（４）はＰＨＩＭ５０４によってプログラマブルハードウェア１１８（２）にロードされる。したがって、この例において、構成バイナリ２１０（１）内に含まれる高い優先度のｒｅｇ ｅｘは、時間の７０％で実行された。
【０１０６】
タスクのマージ
正規表現処理システム１０２の操作中、複数のユーザおよび／またはアプリケーションからのｒｅｇ ｅｘが受信されてもよい。たとえば、スパムフィルタリングシステムは、ユーザまたは分析ソフトウェアによりフラグ設定されたスパムのようなスパムを指示する複数のストリングのストリームを受信することができる。図２５は、コンパイルおよび／または実行における複数のユーザ／アプリケーションによる正規表現のマージャーを示す流れ図２５００である。そのようなマージは、時間およびシステムリソースの点から比較的高価であるプログラマブルハードウェアの再構成を最小化することにより速度を増大させる。
【０１０７】
コンパイルマージ中、２５０２において、ｒｅｇ ｅｘ１０８（１）はユーザＡから受信され、ｒｅｇ ｅｘ１０８（２）はユーザＢから受信される。２５０４において、コンパイルモジュール１１２はこれらのｒｅｇ ｅｘを処理し、これらがいずれも同じ構成バイナリで実行できることを決定し、２５０６において、ｒｅｇ ｅｘ１０８（１）および１０８（２）を含む構成バイナリ２１０（５１）を生成する。２５０８において、ユーザＡおよびＢからの入力がＰＨＳＣ１１４において受信される。２５１０において、ＰＨＩＭ５０４は、実行のために構成バイナリ２１０（５１）をロードし、２５１２においてプログラマブルハードウェアは構成バイナリを実行して、結果をＰＨＩＭ５０４に返す。次いで、ＰＨＳＣ１１４は、結果をそれぞれのユーザに返す。利点の中でも特に、マージは、コンテキスト切り替えの必要性をなくす。たとえば、マージしなければ、ユーザＡとユーザＢとの間でコンテキストを切り替えることが必要になる。したがって、ユーザＡのｒｅｇ ｅｘ１０８（１）は、ｒｅｇ ｅｘ１０８（２）が待機している間に実行していることになる。ｒｅｇ ｅｘ１０８（１）が完了すると、ｒｅｇ ｅｘ１０８（２）は実行する。マージにより、両方が同時に実行することができる。
【０１０８】
このプロセスのセキュリティは、単に基礎をなすコンパイルモジュール１１２およびＰＨＳＣ１１４はそれらの２つの異なるｒｅｇ ｅｘが同時に実行されたことを認識しているので、マージ中に保持される。ユーザＡおよびユーザＢは、マージャーに気付いてはおらず、それぞれの結果は別々のままである。
【０１０９】
遅延構成ページング
マージに加えて、複数のアプリケーションまたはユーザは、正規表現処理システム１０２の操作中にリソースを共有することができる。図２６は、この共有を容易にするための構成バイナリの遅延構成ページングを示す流れ図２６００である。遅延ページングは、タスクの遅延を考慮に入れて、それらのタスクの統合を可能にし、プログラマブルハードウェアの再構成を最小化することができる。
【０１１０】
この図において、矢印２６０２により指示されるようにページを下方に進むと時間が増大する。２６０４において、ＰＨＳＣ１１４は、コーパスの第１の部分のような、入力Ａを持つｒｅｇ ｅｘ１０８（８０）を受信する。ＰＨＳＣ１１４は、プログラマブルハードウェアでの実行のためにｒｅｇ ｅｘをＰＨＩＭ５０４に渡し、結果をユーザに返す。
【０１１１】
２６０６において、ＰＨＳＣ１１４は、処理のためにｒｅｇ ｅｘ１０８（８１）を受信する。しかし、ｒｅｇ ｅｘ１０８（８０）の追加の処理が発生することが予想されていた。その結果、ｒｅｇ ｅｘ１０８（８１）の処理が遅延する。
【０１１２】
２６０８において、コーパスの第２の部分のような、今回は入力Ｂを持つｒｅｇ ｅｘ１０８（８０）が再度要求される。プログラマブルハードウェア１１８（２）はすでに、ロードされたｒｅｇ ｅｘ１０８（８０）を組み入れる構成２１０（８０）を有しているので、再構成のための遅延はなく、処理は開始することができる。次いで、これらの結果はユーザに返される。
【０１１３】
２６１０において、ｒｅｇ ｅｘ１０８（８０）は完了し、遅延したｒｅｇ ｅｘ１０８（８１）はここでロードされてプログラマブルハードウェア１１８（２）によって実行されてもよい。次いで、これらの結果はユーザに返されてもよい。
【０１１４】
したがって、一部の実施態様において、作業は、現在ロードされておらず、受信された順序と比較して順不同に実行される構成バイナリ２１０について格納されてもよい。それにより、プログラマブルハードウェア１１８への構成バイナリ２１０のロードの回数と頻度を最小化することによって、さらに大幅に効率を高めることができる。
【０１１５】
サブバイナリコンパイル
コンパイルは、プログラマブルハードウェア１１８を使用するように設計された構成バイナリ全体の細分性を下回る細分性のレベルにおいて生じることがある。一部の再構成可能なハードウェアデバイスは、部分的な動的再構成、すなわち、デバイス全体よりも少ない細分性における再構成を考慮に入れる。図２７は、後に完全な構成バイナリを作成するよう結合されうる構成バイナリサブエレメントのコンパイルを示す流れ図２７００である。
【０１１６】
プログラマブルハードウェア２０８のＣＡＤツールによって必要とされる実行時間は、計算論理１２０のサイズに対して超線形に増大する。そのため、パフォーマンスの利点は、より大きい構成バイナリまたはＨＤＬファイルをより小さいファイルに分割して、それらのより小さいファイルを別個にコンパイルすることによって認識することができる。次いで、結果として得られるサブエレメントは、完全な計算論理を形成するように結合されてもよい。より高速なＣＡＤツール２０８のコンパイル時間に加えて、バイナリは、多大なリソースおよび時間を要する全構成バイナリの再コンパイルを必要とするのではなく、それらの事前構成されたサブエレメントを操作することができるので、デフラグおよび再構成を行ないやすい。それらのサブエレメントのパッキングは、（構成全体に対し静的に１回ではなく）動的に行なわれてもよい。
【０１１７】
この図において、正規表現１０８（１）および１０８（２）、ならびに通信および制御論理（ＣＣ）３０６は、サブエレメントのコンパイルのために構成されたコンパイルモジュール１１２によって受信される。ＨＤＬコンパイラ２０２は、各々に対してＨＤＬファイルを作成する。したがって、ＲＥ１０８（１）に対してＨＤＬファイル２７０２（１）、ＲＥ１０８（２）に対してＨＤＬファイル２７０２（２）、ＲＥ１０８（３）に対してＨＤＬファイル２７０２（３）がコンパイルされる。ＣＡＤツール２０８は、サブエレメントの作成のためにそれらのＨＤＬファイル２７０２（１）〜２７０２（３）を受け入れる。結果としてｒｅｇ ｅｘ１０８（１）は構成バイナリサブエレメント２７０４（１）をもたらし、ｒｅｇ ｅｘ１０８（２）は構成バイナリサブエレメント２７０４（２）をもたらし、ＣＣ３０６は構成バイナリサブエレメント２７０４（３）をもたらす。
【０１１８】
バイナリサブエレメントは実行のために選択されてもよいので、バイナリマージモジュール２７０６は、これらのサブエレメントをまとめて結合構成バイナリ２７０８を生成することができる。次いで、この結合構成バイナリ２７０８は、ロードされてプログラマブルハードウェア１１８によって実行されてもよい。
【０１１９】
計算の結合およびスーパーセット
追加のパフォーマンスの利点は、計算およびスーパーセットの組み合わせを通じて達成されうる。図２８は、正規表現を結合する計算を示す概略図２８００である。類似または重複するｒｅｇ ｅｘのような計算は、結合されてもよい。たとえば、いくつかのスパムフィルタリングアプリケーションおよびユーザが、処理のためにｒｅｇ ｅｘのグループをサブミットすると仮定する。それらのグループ内に、共通の実行のために見出されてパックされうる重複があってもよい。
【０１２０】
２８０２において、実行のための正規表現が示される。これらは、２８０４において、ｒｅｇ ｅｘ１０８（１）〜１０８（６）を含むタスクＡを含む。さらに実行のためにｒｅｇ ｅｘに含まれるのは、２８０６において、ｒｅｇ ｅｘ１０８（１）、１０８（４）、１０８（６）、１０８（７）、１０８（８）、および１０８（９）を含むタスクＢである。重複するｒｅｇ ｅｘは、影付きで示される。ｒｅｇ ｅｘ１０８（１）、１０８（４）、および１０８（６）は、２つのタスク間で共通である。計算の結合を行なわない場合、１２のｒｅｇ ｅｘすべてを包含するために４つの構成バイナリが必要であったことになる。
【０１２１】
しかし、計算の結合を通じて、この数は３つの構成バイナリに減少されうる。２８０８において、結合されてコンパイルされたｒｅｇ ｅｘが示される。構成バイナリ２１０（６１）は、ｒｅｇ ｅｘ１０８（１）、１０８（４）、および１０８（６）を含み、構成バイナリ２１０（６２）および２１０（６３）は、重複することなく、残りの正規表現を組み入れる。追加の利点は、タスクＡ２８０４とタスクＢ２８０６間を切り替える場合に、４つではなく、１つの再構成しか必要ないということである。
【０１２２】
図２９は、重複するかまたは類似する部分を有する正規表現のスーパーセットを示す概略図２９００である。上記のように、ｒｅｇ ｅｘの重複または類似する部分は網掛けで示される。２９０２において、実行のための正規表現が示される。ｒｅｇ ｅｘ１０８（１）、１０８（２）、および１０８（３）は、実行を待っている。ここで示されるように、ｒｅｇ ｅｘ１０８（２）の一部は、ｒｅｇ ｅｘ１０８（１）と類似している。たとえば、ｒｅｇ ｅｘ１０８（１）がストリング「ｈｏｍｅ ｍｏｒｔｇａｇｅ」用であり、ｒｅｇ ｅｘ１０８（２）がストリング「ｒｅｆｉｎａｎｃｉｎｇ およびｅｑｕｉｔｙ ｆｒｏｍ ｙｏｕｒ ｈｏｍｅ ｍｏｒｔａｇｅ」用であると仮定する。したがって、１０８（２）は、ストリング「ｈｏｍｅ ｍｏｒｔｇａｇｅ」の一部の、１０８（１）と類似する部分を含み、それは影付きで示される。
【０１２３】
コンパイルモジュール１１２によるコンパイル中に、類似または同一の部分は結合される。２９０４において、パックされてコンパイルされた正規表現のスーパーセットが示される。構成バイナリ２１０（７１）内に、ｒｅｇ ｅｘ１０８（２）が、１０８（１）に共通な部分、１０８（３）、およびＣＣ３０６（１）と共に示される。同じ作業がｒｅｇ ｅｘ１０８（２）の共通部分によって行なわれるので、ｒｅｇ ｅｘ１０８（１）は構成バイナリ２１０（７１）に含まれていない。実行後、ＰＨＳＣ１１４は、結果を分離して、それらを１０８（１）がプログラマブルハードウェアで別々に実行されたかのように返す。
【０１２４】
スーパーセットにより、実行に必要な計算リソースの低減が可能になる。スーパーセットはまた、より多くの等価の正規表現を、より少ない構成バイナリで実行できるようにすることで、再構成の必要性を減少させる。
【０１２５】
異種のＦＰＧＡの処理
システム１０２内のプログラマブルハードウェア１１８は、同一である必要はないか、またはビットストリーム互換でさえなくてもよい。システム１０２は、さまざまなサイズ、速度、グレード、製造業者、オンボードメモリ容量などのデバイスを含むことができる。異種ハードウェアが存在する場合、プログラマブルハードウェアデバイス１１８は、既存のｒｅｇ ｅｘ配分、およびデバイスのワークロード（他のデバイスよりも使用されることが少ないデバイスもある）、およびｒｅｇ ｅｘ優先度に応じて使用の対象とされてもよい。
【０１２６】
対象となるプログラマブルハードウェア１１８の選択は、複数の因子に影響を及ぼす。それらの因子は、異なるハードウェアに基づくリソース要件の推定の変動を含む。たとえば、ある製造業者が他の製造業者とは異なる基本論理素子を使用し、その結果ｒｅｇ ｅｘがプログラマブルハードウェア１１８で実施される方法に差異が生じることもある。
【０１２７】
対象となるプログラマブルハードウェア１１８の選択により影響を受けるもう１つの因子は、パッキング能力である。パッキング能力は、プログラマブルハードウェア１１８の容量を反映する。たとえば、より大きいデバイスは、小さいデバイスよりも多くのｒｅｇ ｅｘを保持することができる。これは、複数の構成にわたりｒｅｇ ｅｘが分割されうる場所および方法に影響を及ぼす。
【０１２８】
部分的なｒｅｇ ｅｘをマップするための実現可能性もまた、対象プログラマブルハードウェアの決定中に影響を受けることがある。たとえば、時として、中間データのサイズが入力コーパスデータとほぼ同じ規模である場合、オンボードメモリはパフォーマンスにとって有益となりうる。そのような状況において、対象プログラマブルハードウェアの決定は、ハードウェアがそれを処理する実現可能性を考慮に入れることができる。
【０１２９】
システムコントローラの操作は、さまざまなデバイスがさまざまなコマンドで制御されうることを考えると、対象プログラマブルハードウェアによっても影響を受ける。最終的に、仮想化の「ポータビリティ」は、対象となるプログラマブルハードウェアの差異により影響を受ける。たとえば、スペアリングまたは再配分のような、フォールトトレランスを迅速に調整することに関して、本来故障したデバイスに割り振られるｒｅｇ ｅｘは、再コンパイルを行なうことなく他のビットストリーム互換のプログラマブルハードウェアに移行することができる。
【０１３０】
構成の事前取り出し／ページング
複数のアプリケーションまたはユーザが同じ物理プラットフォームを共有する場合、固有の構成バイナリ２１０またはサブエレメントの呼び出しが予測されることもある。したがって、構成バイナリは、メモリ事前取り出しおよび投機的実行と類似する方法でプリロードされてもよい。
【０１３１】
ＦＰＧＡとの直接通信
前述のように、一部の実施態様において、ＰＨＳＣ１１４は、ユーザとの間のスケジューリングおよびデータフローを処理することができる。次いで、プログラマブルハードウェア１１８は、入力データの再生、出力データの再配列、再構成の順序付けなどを処理する機能を含むことができる。この実施態様におけるプログラマブルハードウェア１１８は、状態情報を格納するための追加の外部メモリを必要とすることがある。
【０１３２】
もう１つの実施態様において、プログラマブルハードウェア１１８は、自ら、最初に入力データの受信を最初に処理することができる。この実施態様において、プログラマブルハードウェア１１８は、入力データを受信し、現在ロードされている計算論理１２０による検索の実行を開始する。プログラマブルハードウェア１１８は、入力データを、ソフトウェアで実行しているＰＨＳＣ１１４の一部に中継して返す。ＰＨＳＣ１１４のこのソフトウェアベースの部分は、データの再生、出力データの再配列、およびプログラマブルハードウェア１１８の再構成に責任を負う。
【０１３３】
結論
例示の方法の特定の詳細は、本明細書において提示される図面およびその他の流れ図に関して説明されるが、図面に示される特定の動作が説明されている順序で実行される必要はなく、変更されてもよく、および／または状況に応じて全体が省略されてもよいことを理解されたい。本出願において説明されるように、モジュールおよびエンジンは、ソフトウェア、ハードウェア、ファームウェア、またはそれらの組み合わせとして実施されてもよい。さらに、説明される動作および方法は、コンピュータ、プロセッサ、またはメモリに格納された命令に基づくその他のコンピューティングデバイスにより実施されてもよく、メモリは１つまたは複数のコンピュータ可読ストレージ媒体（ＣＲＳＭ）を備える。
【０１３４】
ＣＲＳＭは、格納されている命令を実施するためにコンピューティングデバイスによってアクセス可能な任意の使用可能な物理媒体であってもよい。ＣＲＳＭは、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、電気的消去再書き込み可能読み出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュメモリその他のソリッドステートメモリ技術、コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）またはその他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたはその他の磁気記憶装置、もしくは望ましい情報を格納するために使用することができ、コンピューティングデバイスによってアクセスすることができる任意の他の媒体を含むことができるが、これらに限定されることはない。
【特許請求の範囲】
【請求項１】
１つまたは複数のコンピュータ可読ストレージ媒体であって、プロセッサによって実行される場合、前記プロセッサに、
正規表現のリストを解析し、正規表現の前記リストを対応する論理および状態方程式に変換するステップ（９０２）と、
プログラマブルハードウェアデバイスで前記論理および状態方程式を実施するための物理リソース要件を推定するステップ（９０４）と、
前記論理および状態方程式をセットに配分するステップであって、前記推定される物理リソース要件に基づき、各セットは、制御および通信論理と結合される場合、前記プログラマブルハードウェアデバイス内に収まるようにサイズ調整されるステップ（９０６）と、
前記制御および通信論理を各セットに追加するステップ（９０８）と、
各セットに対してハードウェア定義言語（ＨＤＬ）ファイルを生成するステップ（９１０）と、
各ＨＤＬファイルから構成バイナリを生成するステップ（９１４）であって、各構成バイナリは前記プログラマブルハードウェアデバイスで実行するように構成されるステップと
を備える動作を実行させる命令を格納することを特徴とするコンピュータ可読ストレージ媒体。
【請求項２】
前記セットのうちの１つまたは複数の構成仕様を生成するステップ（９１２）をさらに備えることを特徴とする請求項１に記載のコンピュータ可読ストレージ媒体。
【請求項３】
計算論理を生成するために、前記構成バイナリを前記プログラマブルハードウェアデバイスにロードするステップ（１１０４）と、
コーパスの少なくとも一部を前記プログラマブルハードウェアデバイスにロードするステップ（１１０６）と、
前記ロードされたコーパスに対して前記プログラマブルハードウェアデバイスで前記計算論理を実行するステップ（１１０８）と
をさらに備えることを特徴とする請求項１または２のいずれか一項に記載のコンピュータ可読ストレージ媒体。
【請求項４】
前記物理リソース要件を推定するステップは、
特定の正規表現を前記プログラマブルハードウェアデバイスの計算論理に関連付けるステップ（１００２）と、
統合された論理を形成するために、前記計算論理内から冗長な論理を識別して除去するステップ（１００４）と、
前記プログラマブルハードウェアデバイスでの前記統合された論理のローカルストレージ要件を推定するステップ（１００６）と、
コンピュータ支援設計ツール固有の修正率を前記統合された論理およびローカルストレージ要件に適用するステップ（１００８）と、
前記推定された統合された論理およびローカルストレージ要件に基づいて推定された物理リソース要件を生成するステップと
を備えることを特徴とする請求項１から３のいずれか一項に記載のコンピュータ可読ストレージ媒体。
【請求項５】
前記リストの正規表現を廃棄リストに追加するステップ（１２１０）と、
前記廃棄リストの前記正規表現に関連付けられている実行結果を廃棄するステップ（１２１２）と
をさらに備えることを特徴とする請求項１から４のいずれか一項に記載のコンピュータ可読ストレージ媒体。
【請求項６】
実行結果を、対応する論理および状態方程式によって表される正規表現の前記リストに含まれていない追加の正規表現でパッチするステップ（１２１４）をさらに備えることを特徴とする請求項３に記載のコンピュータ可読ストレージ媒体。
【請求項７】
使用不可能なプログラマブルハードウェアデバイスから使用可能なプログラマブルハードウェアデバイスに構成バイナリの前記ロードを動的にリダイレクトするステップ（１４０２）をさらに備えることを特徴とする請求項３に記載のコンピュータ可読ストレージ媒体。
【請求項８】
廃棄された正規表現に関連付けられている計算論理を前記セットから除去するステップ（１９０２）と、
残りの計算論理と制御および通信論理を新しい１つまたは複数のセットに再配分するステップ（１９０８）と
をさらに備えることを特徴とする請求項１から７のいずれか一項に記載のコンピュータ可読ストレージ媒体。
【請求項９】
前記構成バイナリは、複数の構成バイナリサブエレメントを備える（２７００）ことを特徴とする請求項１から８のいずれか一項に記載のコンピュータ可読ストレージ媒体。
【請求項１０】
プログラマブルハードウェアデバイスでの実行に適切なプロセッサ論理および状態情報を生成するステップであって、前記実行は結果として複数のタスクの処理をもたらすステップと、
前記論理および状態情報を処理するために前記プログラマブルハードウェアデバイスによって必要とされるハードウェア容量を推定するステップと、
前記推定されたハードウェア容量の要件に基づいて、各セットの前記論理および状態情報が前記プログラマブルハードウェアデバイスのハードウェア容量内に収まるように、前記論理および状態情報をセットに配分するステップと
を備えることを特徴とする方法。
【請求項１１】
前記プログラマブルハードウェアデバイスで実行するように構成される構成バイナリを各セットに対して生成するステップと、
前記構成バイナリに基づいて構成仕様を生成するステップと
をさらに備えることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記プログラマブルハードウェアデバイスでの前記セットの実行優先度を決定するステップであって、前記実行優先度は高い優先度のタスクおよび低い優先度のタスクを含むステップと、
低い優先度のタスクを実行するプログラマブルハードウェアよりも速いプログラマブルハードウェアで高い優先度のタスクを含む前記セットを実行するように順序付けるステップと
をさらに備えることを特徴とする請求項１０または１１のいずれか一項に記載の方法。
【請求項１３】
前記プログラマブルハードウェアデバイスでの実行のためにタスクを優先度レベルにより順序付けるステップと、
高い優先度のタスクが、最初に実行されるかまたは低い優先度のセットよりも頻繁に実行されるセットに配分されるように、セット内で前記タスクを配分するステップと
をさらに備えることを特徴とする請求項１０から１２のいずれか一項に記載の方法。
【請求項１４】
プロセッサと、
前記プロセッサに結合されたメモリと、
前記メモリに格納され、前記プロセッサで実行するように構成されたユーザインターフェイスと、
前記ユーザインターフェイスを通じて取得され、前記メモリに格納された複数のタスクと、
メモリに格納されたコンパイルモジュールであって、
前記複数のタスクの少なくとも一部を対応する論理および状態方程式に変換し、
プログラマブルハードウェアデバイスで前記論理および状態方程式を実施するための物理リソース要件を推定し、
前記推定される物理リソース要件に基づいて前記論理および状態方程式をセットに配分し、各セットは、制御および通信論理と結合される場合、前記プログラマブルハードウェアデバイス内に収まるようにサイズ調整され、
各セットの構成バイナリを生成するように構成されたコンパイルモジュールと、
前記プログラマブルハードウェアデバイスに対する前記構成および入出力データのマーシャリングを管理するために前記プロセッサで実行するように構成されたプログラマブルハードウェアシステムコントローラと
を備えることを特徴とするシステム。
【請求項１５】
前記ユーザインターフェイスにより取得され、メモリに格納された前記複数のタスクは、データのコーパスに対して実行されるように構成された正規表現であることを特徴とする請求項１４に記載のシステム。
【請求項１】
１つまたは複数のコンピュータ可読ストレージ媒体であって、プロセッサによって実行される場合、前記プロセッサに、
正規表現のリストを解析し、正規表現の前記リストを対応する論理および状態方程式に変換するステップ（９０２）と、
プログラマブルハードウェアデバイスで前記論理および状態方程式を実施するための物理リソース要件を推定するステップ（９０４）と、
前記論理および状態方程式をセットに配分するステップであって、前記推定される物理リソース要件に基づき、各セットは、制御および通信論理と結合される場合、前記プログラマブルハードウェアデバイス内に収まるようにサイズ調整されるステップ（９０６）と、
前記制御および通信論理を各セットに追加するステップ（９０８）と、
各セットに対してハードウェア定義言語（ＨＤＬ）ファイルを生成するステップ（９１０）と、
各ＨＤＬファイルから構成バイナリを生成するステップ（９１４）であって、各構成バイナリは前記プログラマブルハードウェアデバイスで実行するように構成されるステップと
を備える動作を実行させる命令を格納することを特徴とするコンピュータ可読ストレージ媒体。
【請求項２】
前記セットのうちの１つまたは複数の構成仕様を生成するステップ（９１２）をさらに備えることを特徴とする請求項１に記載のコンピュータ可読ストレージ媒体。
【請求項３】
計算論理を生成するために、前記構成バイナリを前記プログラマブルハードウェアデバイスにロードするステップ（１１０４）と、
コーパスの少なくとも一部を前記プログラマブルハードウェアデバイスにロードするステップ（１１０６）と、
前記ロードされたコーパスに対して前記プログラマブルハードウェアデバイスで前記計算論理を実行するステップ（１１０８）と
をさらに備えることを特徴とする請求項１または２のいずれか一項に記載のコンピュータ可読ストレージ媒体。
【請求項４】
前記物理リソース要件を推定するステップは、
特定の正規表現を前記プログラマブルハードウェアデバイスの計算論理に関連付けるステップ（１００２）と、
統合された論理を形成するために、前記計算論理内から冗長な論理を識別して除去するステップ（１００４）と、
前記プログラマブルハードウェアデバイスでの前記統合された論理のローカルストレージ要件を推定するステップ（１００６）と、
コンピュータ支援設計ツール固有の修正率を前記統合された論理およびローカルストレージ要件に適用するステップ（１００８）と、
前記推定された統合された論理およびローカルストレージ要件に基づいて推定された物理リソース要件を生成するステップと
を備えることを特徴とする請求項１から３のいずれか一項に記載のコンピュータ可読ストレージ媒体。
【請求項５】
前記リストの正規表現を廃棄リストに追加するステップ（１２１０）と、
前記廃棄リストの前記正規表現に関連付けられている実行結果を廃棄するステップ（１２１２）と
をさらに備えることを特徴とする請求項１から４のいずれか一項に記載のコンピュータ可読ストレージ媒体。
【請求項６】
実行結果を、対応する論理および状態方程式によって表される正規表現の前記リストに含まれていない追加の正規表現でパッチするステップ（１２１４）をさらに備えることを特徴とする請求項３に記載のコンピュータ可読ストレージ媒体。
【請求項７】
使用不可能なプログラマブルハードウェアデバイスから使用可能なプログラマブルハードウェアデバイスに構成バイナリの前記ロードを動的にリダイレクトするステップ（１４０２）をさらに備えることを特徴とする請求項３に記載のコンピュータ可読ストレージ媒体。
【請求項８】
廃棄された正規表現に関連付けられている計算論理を前記セットから除去するステップ（１９０２）と、
残りの計算論理と制御および通信論理を新しい１つまたは複数のセットに再配分するステップ（１９０８）と
をさらに備えることを特徴とする請求項１から７のいずれか一項に記載のコンピュータ可読ストレージ媒体。
【請求項９】
前記構成バイナリは、複数の構成バイナリサブエレメントを備える（２７００）ことを特徴とする請求項１から８のいずれか一項に記載のコンピュータ可読ストレージ媒体。
【請求項１０】
プログラマブルハードウェアデバイスでの実行に適切なプロセッサ論理および状態情報を生成するステップであって、前記実行は結果として複数のタスクの処理をもたらすステップと、
前記論理および状態情報を処理するために前記プログラマブルハードウェアデバイスによって必要とされるハードウェア容量を推定するステップと、
前記推定されたハードウェア容量の要件に基づいて、各セットの前記論理および状態情報が前記プログラマブルハードウェアデバイスのハードウェア容量内に収まるように、前記論理および状態情報をセットに配分するステップと
を備えることを特徴とする方法。
【請求項１１】
前記プログラマブルハードウェアデバイスで実行するように構成される構成バイナリを各セットに対して生成するステップと、
前記構成バイナリに基づいて構成仕様を生成するステップと
をさらに備えることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記プログラマブルハードウェアデバイスでの前記セットの実行優先度を決定するステップであって、前記実行優先度は高い優先度のタスクおよび低い優先度のタスクを含むステップと、
低い優先度のタスクを実行するプログラマブルハードウェアよりも速いプログラマブルハードウェアで高い優先度のタスクを含む前記セットを実行するように順序付けるステップと
をさらに備えることを特徴とする請求項１０または１１のいずれか一項に記載の方法。
【請求項１３】
前記プログラマブルハードウェアデバイスでの実行のためにタスクを優先度レベルにより順序付けるステップと、
高い優先度のタスクが、最初に実行されるかまたは低い優先度のセットよりも頻繁に実行されるセットに配分されるように、セット内で前記タスクを配分するステップと
をさらに備えることを特徴とする請求項１０から１２のいずれか一項に記載の方法。
【請求項１４】
プロセッサと、
前記プロセッサに結合されたメモリと、
前記メモリに格納され、前記プロセッサで実行するように構成されたユーザインターフェイスと、
前記ユーザインターフェイスを通じて取得され、前記メモリに格納された複数のタスクと、
メモリに格納されたコンパイルモジュールであって、
前記複数のタスクの少なくとも一部を対応する論理および状態方程式に変換し、
プログラマブルハードウェアデバイスで前記論理および状態方程式を実施するための物理リソース要件を推定し、
前記推定される物理リソース要件に基づいて前記論理および状態方程式をセットに配分し、各セットは、制御および通信論理と結合される場合、前記プログラマブルハードウェアデバイス内に収まるようにサイズ調整され、
各セットの構成バイナリを生成するように構成されたコンパイルモジュールと、
前記プログラマブルハードウェアデバイスに対する前記構成および入出力データのマーシャリングを管理するために前記プロセッサで実行するように構成されたプログラマブルハードウェアシステムコントローラと
を備えることを特徴とするシステム。
【請求項１５】
前記ユーザインターフェイスにより取得され、メモリに格納された前記複数のタスクは、データのコーパスに対して実行されるように構成された正規表現であることを特徴とする請求項１４に記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【公表番号】特表２０１２−５３０９７６（Ｐ２０１２−５３０９７６Ａ）
【公表日】平成２４年１２月６日（２０１２．１２．６）
【国際特許分類】
【出願番号】特願２０１２−５１６３６０（Ｐ２０１２−５１６３６０）
【出願日】平成２２年６月１８日（２０１０．６．１８）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０３９２７１
【国際公開番号】ＷＯ２０１０／１４８３６７
【国際公開日】平成２２年１２月２３日（２０１０．１２．２３）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
【公表日】平成２４年１２月６日（２０１２．１２．６）
【国際特許分類】
【出願日】平成２２年６月１８日（２０１０．６．１８）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０３９２７１
【国際公開番号】ＷＯ２０１０／１４８３６７
【国際公開日】平成２２年１２月２３日（２０１０．１２．２３）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
[ Back to top ]