利用專用元件實施有限狀態的製造方法

2023-09-22 13:49:30 2

利用專用元件實施有限狀態的製造方法
【專利摘要】本發明描述用於編譯程序的設備、系統和方法。一種此類編譯程序產生對應於包含通用元件和專用元件的一組元件的機器碼。所述編譯程序識別有關係連接的運算符的布置中的對應於專用元件的一部分。所述編譯程序還確定所述部分是否滿足將被映射到所述專用元件的條件。所述編譯程序還將所述布置轉換成包括多個狀態的自動機，其中如果所述部分滿足所述條件，那麼使用對應於所述專用元件的專用狀態來轉換所述部分。所述編譯程序還將所述自動機轉換成機器碼。本發明揭示額外設備、系統和方法。
【專利說明】利用專用元件實施有限狀態機
[0001]優先權主張
[0002]本專利申請案主張2011年I月25日申請的標題為「利用專用元件實施有限狀態機(UTILIZING SPECIAL PURPOSE ELEMENTS TO IMPLEMENT A FSM) 」的第 61/436，022 號美國臨時專利申請案的優先權權益，所述美國臨時專利申請案的全文特此以引用方式併入本文中。
【技術領域】【背景技術】
[0003]有限狀態機(FSM)(也被稱作有限狀態自動機、自動機或簡稱為狀態機)為狀態、狀態之間的轉變和動作的表示。有限狀態機可用以設計數字邏輯、電腦程式或平行機的映像。有限狀態機為由有限數目個狀態、那些狀態之間的轉變和輸出組成的行為模型。有限狀態機可表示為一圖，其中所述圖的頂點對應於FSM的狀態，且所述圖的邊對應於歸因於到所述有限狀態機的一個或一個以上輸入而發生的狀態之間的轉變。有限狀態機還可具有概率轉變、模糊狀態或其它異事。有限狀態機可充當具有輸入特徵和任選的輸出特徵的有限內部存儲器。具有輸出的有限狀態機可被稱作有限狀態轉換器。
[0004]有限狀態機的應用包含電子設計自動化、通信協議設計、生物學和人工智慧研究，以及用以描述自然語言的文法的語言學。

【發明內容】
【專利附圖】

【附圖說明】
[0005]圖1說明根據本發明的各種實施例的確定性有限狀態機的實例。
[0006]圖2說明根據本發明的各種實施例的非確定性有限狀態機的實例。
[0007]圖3說明根據本發明的各種實施例的供編譯程序用以將源碼轉換成機器碼的方法的實例。
[0008]圖4說明根據本發明的各種實施例的用於將語法樹轉換成自動機的方法。
[0009]圖5說明根據本發明的各種實施例的平行機的實例。
[0010]圖6說明根據本發明的各種實施例的實施為有限狀態機引擎的圖5的平行機的實例。
[0011]圖7說明根據本發明的各種實施例的圖6的有限狀態機引擎的方框的實例。
[0012]圖8說明根據本發明的各種實施例的圖7的方框的行的實例。
[0013]圖9說明根據本發明的各種實施例的圖8的行的成對群組的實例。
[0014]圖10說明根據本發明的各種實施例的供編譯程序用以將源碼轉換成經配置以對圖5的平行機編程的映像的方法的實例。
[0015]圖11說明根據本發明的各種實施例的具有專用計數器狀態的實例自動機。[0016]圖12說明根據本發明的各種實施例的具有專用計數器狀態的另一實例自動機。
[0017]圖13A和13B說明根據本發明的各種實施例的實例自動機。
[0018]圖14說明根據本發明的各種實施例的具有不滿足無前綴條件的量化的正規表達式的實例自動機。
[0019]圖15說明根據本發明的各種實施例的具有馮諾依曼(Von Nuemann)架構的計算機的實例。
【具體實施方式】
[0020]以下描述和圖式充分地說明特定實施例以使所屬領域的技術人員能夠實踐所述實施例。其它實施例可並有結構、邏輯、電、過程和其它改變。一些實施例的部分和特徵可包含在其它實施例的部分和特徵中或可替代其它實施例的部分和特徵。權利要求書中所陳述的實施例涵蓋那些權利要求的所有可用等效物。
[0021]本文獻尤其描述將源碼轉換成有限狀態機的機器碼實施方案的編譯程序。機器碼可對應於目標裝置，因為所述機器碼經配置以在所述目標裝置上實施通過源碼描述的功能。在一實例中，所述目標裝置為平行機，且機器碼包括用於所述平行機的映像。在另一實例中，所述目標裝置包括具有馮諾依曼架構的計算機，且機器碼包括供所述計算機中的處理器執行的指令。
[0022]在任何情況下，編譯程序均可將源碼編譯成機器碼，所述機器碼實施體現通過所述源碼描述的功能的有限狀態機。在編譯源碼的過程中，所述編譯程序將源碼轉換成自動機。使用所述自動機，所述編譯程序可識別並組合源碼中的冗餘，以便優化通過機器碼實施的所得有限狀態機。另外，所述編譯程序可識別所述自動機的部分並將所述部分映射到對應於目標裝置的元件。當目標裝置為平行機時，所述元件可包括所述平行機的硬體元件。當目標裝置為具有馮諾依曼架構的計算機時，所述元件可包括供處理器執行的指令。在映射期間，可將有限狀態機的某些部分映射到特定(例如，專用)元件以便(例如)改進所得機器碼的性能。
[0023]圖1說明實例有限狀態機(FSM) 100。有限狀態機100對應於用於將容器中的水位維持在1/4與3/4滿之間的方法。在狀態102處，激活泵以減少容器中的水位。當水位掉落到1/4滿以下時，FSM100轉變到狀態104，在狀態104下，對泵去活。在處於狀態104時，當水位超過3/4滿時，FSM100轉變回到狀態104，在狀態104下，重新激活泵。到FSM100的輸入為容器中的水位，且輸出為泵開/關信號。
[0024]FSM可分成兩類:確定性和非確定性的。確定性FSM在給定時間具有單一執行路徑，而非確定性FSM具有多個同時的執行路徑。具有N個狀態的非確定性FSM通常可轉換成具有最壞情況2到N個狀態的確定性FSM。然而，從非確定性到確定性FSM的此指數狀態展開通常使非確定性FSM成為具有有限機器資源和時間的最實際的實施方案。
[0025]FSM100為確定性FSM的實例，且此確定性FSM100可為較大非確定性FSM的一部分。舉例來說，圖2說明有一部分是由確定性FSM100組成的非確定性FSM200。FSM200將管壓力的監視添加到水位維持FSM100。在FSM200中，在泵運作時監視管壓力，且如果管壓力在固定時間周期內過負荷，那麼停止泵。在FSM200中，當管在狀態102下激活時管壓力過負荷時，FSM200轉變到狀態106，在狀態106下開啟計時器。另外，當管過負荷時，狀態102轉變到自身以使泵維持於「開」狀態。因此，在FSM200中的此位置處，狀態102( 「泵開」狀態)和狀態106 ( 「計時器開」狀態)兩者同時在作用中。由於狀態102和106可同時在作用中，因此存在多個執行路徑，且FSM200因此為非確定性的。當管中的壓力不再過負荷時，FSM200從狀態106轉變到狀態102。而且，當計時器期滿時，FSM200從狀態102和狀態106兩者轉變到狀態104以將泵設定為「關」狀態。
[0026]圖3說明實例編譯程序的流程圖300。所述編譯程序採用源碼作為輸入且產生機器碼以在目標裝置上實施通過源碼描述的功能。在一個實例中，所述目標裝置包括如下文關於圖5到9中所描述的平行機。所述平行機包含可設定為多個狀態中的一者的多個可編程元件。用於平行機的機器碼包括用於設定所述可編程元件中的一者或一者以上的狀態的映像。在另一實例中，所述目標裝置為具有馮諾依曼架構的計算機。所述計算機包含耦合到一個或一個以上存儲器裝置的一個或一個以上處理器，所述一個或一個以上存儲器裝置上具有供所述一個或一個以上處理器執行的軟體。用於馮諾依曼架構的機器碼包括供所述一個或一個以上處理器執行的指令。在下文關於圖15來描述具有馮諾依曼架構的實例計算機。在任何情況下，所述編譯程序通過將自動機用作中間轉換來產生機器碼。所述編譯程序使用自動機以便尤其優化所得FSM且又優化所述機器碼。
[0027]在實例中，源碼描述用於識別一群符號內的符號的樣式的搜索字符串。為了描述所述搜索字符串，所述源碼可包含多個正規表達式(regex)。正規表達式可為用於描述符號搜索樣式的字符串。正規表達式廣泛用在各種計算機領域中，例如程式語言、文字編輯器、網絡安全和其它領域。在實例中，由編譯程序支持的正規表達式包含用於無結構數據的搜索的搜索準則。無結構數據可包含以下數據，其為自由形式的且無索引施加於數據內的字。字可包含數據內的任何字節組合，可列印和不可列印的。在實例中，編譯程序可支持用於實施正規表達式的多種不同的源碼語言，包含Perl (例如，Perl兼容正規表達式(PCRE))、PHP、Java 和.NET 語言。
[0028]返回參看圖3，在方框302處，編譯程序可剖析源碼以形成有關係連接的運算符的布置。剖析源碼可產生所述源碼的一股表示。在實例中，所述一股表示包括所述源碼中的呈被稱為語法樹的樹形圖形式的正規表達式的經編碼表示。本文中所描述的實例將所述布置稱為語法樹(也被稱為「抽象語法樹」)，然而，在其它實例中，可使用具體語法樹或其它布置。
[0029]由於如上文所提及，編譯程序可支持多種語言的源碼，因此，不管是何種語言，剖析將所述源碼轉換成非語言特定表示，例如語法樹。因此，通過編譯程序進行的進一步處理(方框304、306、308、310)可從共同輸入結構來起作用，而不管源碼的語言。
[0030]所述語法樹包含有關係連接的多個運算符。所述語法樹可包含多個不同類型的運算符，其中不同類型的運算符對應於通過源碼實施的不同功能。即，不同運算符可對應於通過源碼中的正規表達式實施的不同功能。
[0031]在方框304處，將所述語法樹轉換成自動機。自動機包括FSM的軟體模型，且可因此分為確定性或非確定性。確定性自動機在給定時間具有單一執行路徑，而非確定性自動機具有多個同時的執行路徑。所述自動機包括多個狀態。為了將語法樹轉換成自動機，將語法樹中的運算符和運算符之間的關係轉換成狀態和狀態之間的轉變。
[0032]在實例中，自動機包括通用狀態和專用狀態。所述通用狀態和專用狀態對應於通過目標裝置支持的通用元件和專用元件，編譯程序為所述目標裝置產生機器碼。不同類型的目標裝置可支持不同類型的通用元件以及一個或一個以上不同類型的專用元件。通用元件通常可用以實施廣泛範圍的功能，而專用元件通常可用以實施更窄範圍的功能。然而，在實例中，專用元件可在其窄範圍的適用性內實現(例如)較大效率。因此，專用元件可用以(例如)減少在目標裝置中實施某些功能所需的機器循環或機器資源。在一些實例中，目標裝置僅支持專用元件，其中支持多個不同類型的專用元件。
[0033]目標裝置的類型可很大程度上控制所述目標裝置所支持的元件的類型。在一個實例中，所述目標裝置為具有馮諾依曼架構的計算機，且所支持的元件包含對應於所述計算機的處理器的指令集。指令集可包含例如加法、減法、讀取和寫入等通用指令以及例如存儲器的較大塊的多重存儲和移動等專門指令。在另一實例中，目標裝置為如下文關於圖5到9中所描述的平行機。由平行機支持的元件包含所述平行機的硬體元件。硬體組件可包含例如狀態機元件等通用元件以及例如計數器等專用元件。在一些實例中，尤其是平行機實例，目標裝置可支持與相對較少數目個專用元件相比數目較大的通用元件。因此，在一些實例中，將用通用元件來實施大多數功能，而用專用元件來實施較少的選定功能。
[0034]為了有效地利用目標裝置的元件，所述編譯程序使用自動機中的對應於目標裝置支持的專用元件的專用狀態來轉換語法樹的適當部分。所述語法樹的不使用專用狀態轉換的部分可轉換成對應於目標裝置支持的通用元件的通用狀態。所述編譯程序可分析所述語法樹以確定哪些部分可使用專用狀態來轉換且哪些部分應轉換成通用狀態。在一些實例中，自動機的大部分轉換成一個或一個以上通用狀態，而使用一個或一個以上專用狀態來轉換較小百分比。
[0035]舉例來說，使用專用狀態轉換自動機的一些部分可減少狀態的數目和/或簡化自動機，且因此簡化通過所述機器碼實施的FSM。舉例來說，所述語法樹的某些部分在使用通用狀態而不用任何專用狀態來轉換時可導致大數目的狀態。為了減少狀態的數目，可使用一個或一個以上專用狀態可能結合一個或一個以上通用狀態來轉換這些相同部分。小數目的專用狀態可能夠代替大數目的通用狀態。由於通用狀態的數目通常對應於所得機器碼所使用的通用元件的數目，因此減少通用狀態的數目可歸因於使用較少的通用元件而減少複雜性並增加所得機器碼的效率。
[0036]在任何情況下，所述編譯程序將語法樹中的某些部分轉換成某些類型的狀態，且將所述語法樹中的其它部分轉換成其它類型的狀態。由於狀態的類型對應於目標裝置支持的元件的類型，因此所述轉換可具有將由所述源碼實施的某些功能映射到由所述平行機支持的特定類型的元件的作用。在目標裝置為具有馮諾依曼架構的計算機的實例中，源碼中的某些功能可映射到由馮諾依曼計算機支持的指令集的特定類型的指令。在目標裝置為平行機的實例中，源碼的某些功能可映射到通用元件，例如狀態機元件，且其它功能可映射到專用元件，例如計數器。下文關於圖4提供關於將語法樹轉換成自動機的額外細節。
[0037]一旦已形成自動機，在方框306處，可將所述自動機優化以尤其減少其複雜性和大小。可尤其通過組合等效狀態來優化所述自動機。
[0038]在方框308處，將所述自動機轉換成用於目標裝置的機器碼。在方框304處，將所述自動機的每一部分轉換成如所映射的對應於所述目標裝置的元件的機器碼。在一個實例中，所述機器碼包括用於馮諾依曼架構中的處理器的可執行指令。在此，機器碼可包括可執行程序。在另一實例中，機器碼可包括用於平行機中的硬體元件的編程的位。在此，所述機器碼可包括供加載到平行機上的映像。
[0039]在方框310處，所述機器碼可通過編譯程序發布。在實例中，可通過將機器碼保存到計算機可讀媒體來發布所述機器碼。在另一實例中，可通過將機器碼發送到另一裝置(例如，用於將機器碼加載到平行機上的編程裝置)來發布所述機器碼。在再一實例中，可通過將機器碼加載到平行機上來發布所述機器碼。在又一實例中，可通過在顯示裝置上顯示機器碼來發布所述機器碼。
[0040]在實例中，所述編譯程序可由用於具有馮諾依曼架構的計算機的指令來實施。這些指令可致使所述計算機上的處理器實施所述編譯程序的功能。舉例來說，所述指令在由所述處理器執行時可致使所述處理器對可由所述處理器存取的源碼執行如方框302、304、306、308和310中所描述的動作。具有馮諾依曼架構的實例計算機展示於圖15中且在下文描述。
[0041]圖4說明用於將布置(例如，語法樹)轉換成自動機的方法400，其中使用專用狀態來轉換所述語法樹的某些部分。為了利用自動機內的專用狀態，在方框402處，編譯程序首先識別所述語法樹的對應於目標裝置支持的專用元件的部分。舉例來說，在平行機中，通常可能在需要時藉助通用狀態來實施整個語法樹。這是因為通用狀態可以某些方式組合以實施所述平行機支持的所有功能。然而，如上文所提及，專用元件希望僅實施某些功能。因此，編譯程序識別所述語法樹中的可由專用元件實施或可由專用元件有效實施的運算符。如下文所描述，可接著使用專用狀態來轉換語法樹的這些運算符和周圍部分。
[0042]在實例中，基於所述語法樹中的運算符的功能來識別所述語法樹的對應於專用狀態的部分。事實上，通過編譯程序識別的運算符的功能性可對應於所述目標裝置的專用元件希望實施的特定功能性。在實例中，當所述目標裝置支持作為專用元件的計數器時，所述編譯程序可將所述語法樹中的量化識別為對應於專用元件。關於圖5到14提供關於量化和計數器的更多細節。
[0043]在方框404處，一旦已將一部分識別為對應於專用元件，便可進一步分析所識別的部分以確定其是否滿足某些條件以便被映射到專用元件。在實例中，所述條件包含對應於所識別部分的自動機是否為確定性的。即，所述條件對應於，不管有一部分為所識別部分的較大自動機(例如，基於整個語法樹形成的自動機)是否為確定性的，所識別部分在轉換成通用狀態的自動機時是否為確定性的。如果對應於所識別部分的自動機為確定性的，那麼在方框406處，使用一個或一個以上專用狀態來轉換所述所識別部分。如果所述自動機並非確定性的，那麼在方框408處，使用一個或一個以上通用狀態而不用任何專用狀態來轉換所識別部分。在其它實例中，所述自動機可在所識別能力為確定性時使用第一類型的專用狀態來轉換所識別部分且在所識別部分並非確定性時使用另一類型的專用狀態來轉換所識別部分。在又其它實例中，可使用其它條件來確定在轉換所述語法樹的所識別部分時將使用哪類型的狀態。
[0044]在實例中，為了在方框404處確定語法樹的所識別部分是否為確定性的，編譯程序可確定所識別部分在轉換成自動機時是否在給定時間僅具有一個作用中狀態。此可通過(例如)找出是否存在幹擾到所識別部分的任何條件來確定。舉例來說，在所識別部分為量化時，編譯程序可分析所述自動機以確定所述自動機是否滿足「無重入」條件或「無前綴」條件。在下文關於圖10到14提供關於無重入和無前綴幹擾條件的額外細節。
[0045]使用這些確定性，可將語法樹中的每一運算符轉換成自動機的一個或一個以上狀態。一些運算符可通過識別由所述運算符所實施的特定功能和在適當時使用所述自動機中的一個或一個以上專用狀態來轉換那些功能來如上文所描述進行轉換。不使用一個或一個以上專用狀態轉換的運算符可默認地轉換為一個或一個以上通用狀態。舉例來說，可分析所述語法樹以識別所有適用運算符並將所述運算符映射到平行機中的計數器。一旦所有適用運算符已映射到一個或一個以上計數器，便可將剩餘運算符映射到一個或一個以上狀態機元件。在其它實例中，通過識別對應於特定部分的一個或一個以上特定元件來映射所述語法樹的所有部分。
[0046]實例實施例
[0047]下文關於圖5到15所作的描述與使用平行機中的專用元件實施FSM的實例實施例有關。在實例中，所述平行機的專用元件包含計數器。所述計數器希望實施源碼中的量化。參看圖5到9所作的描述與實例平行機有關，且關於圖10到14所作的描述描述了用以產生機器碼以對所述平行機編程的編譯程序。
[0048]圖5說明可用以實施用於分析數據的階層式結構的實例平行機500。平行機500可接收輸入數據並基於所述輸入數據提供輸出。平行機500可包含用於接收輸入數據的數據輸入埠 510和用於將輸出提供到另一裝置的輸出埠 514。數據輸入埠 510提供用於將輸入到所述平行機500的數據的接口。
[0049]平行機500包含多個可編程元件，包含通用元件502和專用元件512。通用元件502可包含一個或一個以上輸入504和一個或一個以上輸出506。可將通用元件502編程到多個狀態中的一者中。通用元件502的狀態確定所述通用元件502將基於給定輸入提供哪一(些)輸出。即，通用元件502的狀態確定可編程元件將基於給定輸入如何起反應。輸入到數據輸入埠 510的數據可提供到所述多個通用元件502以致使所述通用元件502對其採取行動。通用元件502的實例可包含下文詳細論述的狀態機元件(SME)和可配置邏輯塊。在實例中，SME可設定為給定狀態以當在數據輸入埠 510處接收到給定輸入時提供某一輸出(例如，高或「I」信號)。當在數據輸入埠 510處接收到不同於給定輸入的輸入時，SME可提供不同輸出(例如，低或「O」信號)。在實例中，可配置邏輯塊可經設定以基於在數據輸入埠 510處接收到的輸入來執行布林邏輯函數(例如，「和」(AND)、「或」(0R)、「或非」 (NOR)等)。
[0050]平行機500還可包含用於將程序(例如，映像)加載到平行機500上的編程接口511。所述映像可編程(例如，設定)通用元件502的狀態。即，所述映像可配置通用元件502以按某一方式來對給定輸入起反應。舉例來說，通用元件502可經設定，以當在數據輸入埠 510處接收到字符『a』時輸出高信號。在一些實例中，平行機500可使用時鐘信號來控制通用元件502的操作的時序。在某些實例中，平行機500可包含用於與通用元件502交互和用於執行專用功能的專用元件512(例如，RAM、邏輯門、計數器、查找表等)。在一些實施例中，在數據輸入埠 510處接收到的數據可包含隨時間過去或一齊接收到的一組固定的數據或隨時間過去而接收到的數據流。可從耦合到平行機500的任何源接收數據或通過耦合到平行機500的任何源產生數據，所述任何源例如資料庫、傳感器、網絡等。
[0051]平行機500還包含用於將平行機500的不同元件(例如，通用元件502、數據輸入埠 510、輸出埠 514、編程接口 511和專用元件512)選擇性地耦合在一起的多個可編程開關508。因此，平行機500包括在所述元件間形成的可編程矩陣。在實例中，可編程開關508可將兩個或兩個以上元件選擇性地耦合到彼此，使得通用元件502的輸入504、數據輸入埠 510、編程接口 511或專用元件512可經由一個或一個以上可編程開關508而耦合到通用元件502的輸出506、輸出埠 514、編程接口 511或專用元件512。因此，所述元件之間的信號的投送可通過設定可編程開關508來控制。儘管圖5說明給定元件與可編程開關508之間的某一數目的導體(例如，電線)，但應理解，在其它實例中，可使用不同數目的導體。而且，儘管圖5說明每一通用元件502個別地耦合到可編程開關508，但在其它實例中，多個通用元件502可作為群組(例如，塊802，如圖8中所說明)而耦合到可編程開關508。在實例中，數據輸入埠 510、數據輸出埠 514和/或編程接口 511可實施為寄存器，以使得到寄存器的寫入將數據提供到相應元件或從相應元件提供數據。
[0052]在實例中，單一平行機500實施於物理裝置上，然而，在其它實例中，兩個或兩個以上平行機500可實施於單一物理裝置(例如，物理晶片)上。在實例中，多個平行機500中的每一者可包含不同的數據輸入埠 510、不同的輸出埠 514、不同的編程接口 511，和一組不同的通用元件502。此外，每一組通用元件502可對其對應輸入數據埠 510處的數據起反應(例如，輸出高或低信號)。舉例來說，對應於第一平行機500的第一組通用元件502可對對應於第一平行機500的第一數據輸入埠 510處的數據起反應。對應於第二平行機500的第二組通用元件502可對對應於第二平行機500的第二數據輸入埠 510起反應。因此，每一平行機500包含一組通用元件502，其中不同組的通用元件502可對不同輸入數據起反應。類似地，每一平行機500和每一組對應的通用元件502可提供不同輸出。在一些實例中，來自第一平行機500的輸出埠 514可耦合到第二平行機500的輸入埠510，使得用於第二平行機500的輸入數據可包含來自第一平行機500的輸出數據。
[0053]在實例中，用於加載到平行機100上的映像包括用於在平行機100內設定可編程元件102的狀態、編程可編程開關108和配置專用元件112的多個信息位。在實例中，所述映像可加載到平行機100上以編程所述平行機100以基於某些輸入而提供所要輸出。輸出埠 114可基於可編程元件102對在數據輸入埠 110處的數據所起的反應來提供來自平行機100的輸出。來自輸出埠 114的輸出可包含指示給定樣式的匹配的單一位、包括指示與多個樣式的匹配和不匹配的多個位的字、包括指示多個作用中和非作用中狀態的多個位的字，和對應於在給定時刻所有或某些可編程元件102的狀態的狀態向量。
[0054]平行機500的實例用途包含樣式辨識(例如，語音辨識、圖像辨識等)、信號處理、成像、計算機視覺、密碼學和其它。在某些實例中，平行機500可包括有限狀態機(FSM)引擎、現場可編程門陣列(FPGA)和其變體。此外，平行機500可為較大裝置中的組件，所述較大裝置例如計算機、尋呼機、蜂窩式電話、個人記事本、可攜式音頻播放器、網絡裝置(例如，路由器、防火牆、交換機或其任何組合)、控制電路、相機等。
[0055]圖6到9說明在本文中被稱作「FSM引擎600」的平行機的實例。在實例中，FSM引擎600包括有限狀態機的硬體實施方案。因此，FSM引擎600實施對應於FSM中的多個狀態的多個可選擇性地耦合的硬體元件(例如，可編程元件)。類似於FSM中的狀態，硬體元件可分析輸入流且基於所述輸入流來激活下遊硬體元件。
[0056]FSM引擎600包含多個可編程元件，包含通用元件和專用元件。通用元件可經編程以實施許多不同功能。這些通用元件包含SME604、605 (展示於圖9中)，所述SME604、605階層式組織成行606 (展示於圖7和8中)和塊602 (展示於圖6和7中)。為了在經階層式組織的SME604、605之間投送信號，使用可編程開關的階層，所述階層包含塊間開關603 (展示於圖6和7中)、塊內開關608 (展示於圖7和8中)和行內開關612 (展示於圖8中)。SME604、605可對應於由FSM引擎600實施的FSM的狀態。如下文所描述，可通過使用可編程開關將SME604、605耦合在一起。因此，可通過編程SME604、605以對應於狀態的功能和通過將SME604、605選擇性地耦合在一起以對應於FSM中的狀態之間的轉變來在FSM引擎600上實施FSM。
[0057]圖6說明實例FSM引擎600的全圖。FSM引擎600包含多個塊602，所述塊可與可編程塊間開關603選擇性地耦合在一起。另外，塊602可選擇性地耦合到用於接收信號(例如，數據)和將數據提供到塊602的輸入塊609(例如，數據輸入埠)。塊602還可選擇性地耦合到用於將來自塊602的信號提供到外部裝置(例如，另一 FSM引擎600)的輸出塊613 (例如，輸出埠)。FSM引擎600還可包含用於將程序(例如，映像)加載到FSM引擎600上的編程接口 611。所述映像可編程(例如，設定)SME604、605的狀態。S卩，所述映像可配置SME604、605以按某一方式來對輸入塊609處的給定輸入起反應。舉例來說，SME604可經設定，以當在輸入塊609處接收到字符『a』時輸出高信號。
[0058]在實例中，輸入塊609、輸出塊613和/或編程接口 611可實施為寄存器，以使得到寄存器的寫入將數據提供到相應元件或從相應元件提供數據。因此，來自存儲於對應於編程接口 611的寄存器中的映像的位可加載於SME604、605上。儘管圖6說明塊602、輸入塊609、輸出塊613和塊間開關603之間的某一數目的導體(例如，電線、跡線)，但應理解，在其它實例中，可使用更少或更多的導體。
[0059]圖7說明塊602的實例。塊602可包含多個行606，所述行可與可編程塊內開關608選擇性地耦合在一起。另外，行606可通過塊間開關603而選擇性地耦合到另一塊602內的另一行606。在實例中，包含緩衝器601以控制去往/來自塊間開關603的信號的時序。行606包含多個SME604、605，所述多個SME604、605組織成本文中被稱作成對群組(GOT) 610的元件對。在實例中，塊602包括十六(16)行606。
[0060]圖8說明行606的實例。G0T610可通過可編程行內開關612而選擇性地耦合到其它G0T610和行606內的任何其它元件624。G0T610還可藉助塊內開關608而耦合到其它行606中的其它G0T610，或藉助塊間開關603而耦合到其它塊602中的其它G0T610。在實例中，G0T610具有第一輸入614和第二輸入616以及輸出618。第一輸入614耦合到G0T610的第一 SME604，且第二輸入614耦合到G0T610的第二 SME604。
[0061]在實例中，行606包含第一多個行互連導體620和第二多個行互連導體622。在實例中，G0T610的輸入614、616可耦合到一個或一個以上行互連導體620、622，且輸出618可耦合到一個行互連導體620、622。在實例中，第一多個行互連導體620可耦合到行606內的每一 G0T610的每一 SME604。第二多個行互連導體622可耦合到行606內的每一 G0T610的一個SME604，但不可耦合到G0T610的另一 SME604。在實例中，所述第二多個行互連導體622的前一半可耦合到行606內的SME604的前一半(來自每一 G0T610的一個SME604)，且所述第二多個行互連導體622的後一半可稱合到行606內的SME604的後一半(來自每一G0T610的另一 SME604)。所述第二多個行互連導體622與SME604、605之間的有限連接性在本文中被稱作「對等性」。
[0062]在實例中，行606還可包含專用元件624，例如計數器、可編程布林邏輯元件、現場可編程門陣列(FPGA)、專用集成電路(ASIC)、可編程處理器(例如，微處理器)和其它元件。另外，在實例中，所述專用元件624在不同行606中為不同的。舉例來說，塊602中的行606中的四個可包含布林邏輯作為專用元件624，且塊602中的其它八個行606可包含計數器作為專用元件624。
[0063]在實例中，專用元件624包含計數器(本文中也被稱作計數器624)。在實例中，計數器624包括12位可編程遞減計數器。所述12位可編程計數器624具有計數輸入、復位輸入，和零計數輸出。所述計數輸入在被斷言時使計數器624的值遞減一。所述復位輸入在被斷言時致使計數器624加載來自相關聯的寄存器的初始值。對於所述12位計數器624，可加載高達12位的數作為初始值。當計數器624的值遞減到零(O)時，斷言所述零計數輸出。計數器624還具有至少兩種模式，脈衝和保持。當將計數器624設定為脈衝模式時，在計數器624遞減到零時的第一時鐘循環期間斷言零計數輸出，且在接下來的時鐘循環處，即使斷言了計數輸入，仍不再斷言零計數輸出。此狀態繼續，直到通過復位輸入被斷言而復位計數器624為止。當將計數器624設定為保持模式時，在計數器624遞減到零時的第一時鐘循環期間斷言零計數輸出，且在斷言了計數輸入時保持為經斷言的，直到通過復位輸入被斷言而復位計數器624為止。
[0064]圖9說明G0T610的實例。G0T610包含第一 SME604和第二 SME605，其具有輸入614,616且具有其耦合到OR門630的輸出626、628。用OR門630對輸出626、628 —起進行邏輯OR運算以形成G0T610的共同輸出618。在實例中，第一 SME604和第二 SME605展現對等性，其中第一 SME604的輸入614可耦合到行互連導體622中的一些，且第二 SME605的輸入616可耦合到其它行互連導體622。在實例中，可通過設定開關640以將第一 SME604的輸出626耦合到第二 SME605的輸入616來將G0T610內的兩個SME604、605級聯。
[0065]在實例中，狀態機元件604、605包括與檢測線634並聯耦合的多個存儲器單元632，例如動態隨機存取存儲器(DRAM)中所常用的那些存儲器單元。一種此類存儲器單元632包括可設定為數據狀態的存儲器單元，所述數據狀態例如對應於高或低值(例如，I或O)的狀態。存儲器單元632的輸出耦合到檢測線634，且存儲器單元632的輸入基於數據流線636上的數據而接收信號。在實例中，解碼數據流線636上的輸入以選擇所述存儲器單元632中的一者。選定的存儲器單元632將其所存儲的數據狀態作為輸出提供到檢測線634上。舉例來說，在數據輸入埠 609處接收到的數據可提供到解碼器(未圖示)，且所述解碼器可選擇所述數據流線636中的一者。在實例中，所述解碼器可將ACSII字符轉換成256位的I。
[0066]因此，當存儲器單元632設定為高值且數據流線636上的數據對應於存儲器單元632時，所述存儲器單元632輸出高信號到檢測線634。當數據流線636上的數據對應於存儲器單元632且存儲器單元632設定為低值時，存儲器單元632輸出低信號到檢測線634。在檢測線634上的來自存儲器單元632的輸出通過檢測電路638來感測。在實例中，輸入線614、616上的信號將相應檢測電路638設定為作用中或非作用中狀態。當設定為非作用中狀態時，檢測電路638在相應輸出626、628上輸出低信號，而不管相應檢測線634上的信號。當設定為作用中狀態時，當檢測到來自相應SME604、605的存儲器單元634中的一者的高信號時，檢測電路638在相應輸出線626、628上輸出高信號。當在作用中狀態時，當來自相應SME604、605的所有存儲器單元634的信號為低時，檢測電路638在相應輸出線626、628上輸出低信號。
[0067]在實例中，SME604、605包含256個存儲器單元632，且每一存儲器單元632耦合到不同的數據流線636。因此，SME604、605可經編程以當數據流線636中的選定的一者或一者以上上面具有高信號時輸出高信號。舉例來說，SME604可使第一存儲器單元632(例如，位O)設定為高且使所有其它存儲器單元632 (例如，位I到255)設定為低。當相應檢測電路638處於作用中狀態時，當對應於位O的數據流線636上面具有高信號時，SME604在輸出626上輸出高信號。在其它實例中，SME604可經設定，以當通過將適當的存儲器單元632設定為高值而使多個數據流線636中的一者上面具有高信號時輸出高信號。
[0068]在實例中，可通過從相關聯的寄存器讀取位來將存儲器單元632設定為高值或低值。因此，可通過將由編譯程序產生的映像存儲到寄存器中且將寄存器中的位加載到相關聯的存儲器單元632中來編程SME604。在實例中，由所述編譯程序產生的映像包含高和低(例如，I和O)位的二進位映像。所述映像可通過將SME604、605級聯而編程FSM引擎600以作為FSM而操作。舉例來說，可通過將檢測電路638設定為作用中狀態而將第一 SME604設定為作用中狀態。第一 SME604可經設定，以當對應於位O的數據流線636上面具有高信號時輸出高信號。第二 SME605最初可設定為非作用中狀態，但可經設定以在作用中時當對應於位I的數據流線636上面具有高信號時輸出高信號。可通過設定第一 SME604的輸出626以耦合到第二 SME605的輸入616來將第一 SME604與第二 SME605級聯。因此，當在對應於位O的數據流線636上感測到高信號時，第一 SME604在輸出626上輸出高信號且將第二 SME605的檢測電路638設定為作用中狀態。當在對應於位I的數據流線636上感測到高信號時，第二 SME605在輸出628上輸出高信號以激活另一 SME605或用於來自FSM引擎600的輸出。
[0069]圖10說明供編譯程序用以將源碼轉換成經配置以編程平行機的映像的方法1000的實例。方法1000包含:將所述源碼剖析成語法樹(方框1002);將所述語法樹轉換成自動機(方框1004);優化所述自動機(方框1006);將所述自動機轉換成連線表(方框1008)；將所述連線表放置於硬體上(方框1010);對所述連線表進行路由(方框1012);和發布所得映像(方框1014)。
[0070]在實例中，所述編譯程序包含應用編程接口(API)，所述API允許軟體開發者產生用於在FSM引擎600上實施FSM的映像。所述編譯程序提供用以將所述源碼中的一組輸入的正規表達式轉換成經配置以編程FSM引擎600的映像的方法。所述編譯程序可通過用於具有馮諾依曼架構的計算機的指令來實施。這些指令可致使所述計算機上的處理器實施所述編譯程序的功能。舉例來說，所述指令在由所述處理器執行時可致使所述處理器對可由所述處理器存取的源碼執行如方框1002、1004、1006、1008、1010、1012和1014中所描述的動作。具有馮諾依曼架構的實例計算機展示於圖15中且在下文描述。
[0071]在方框1002處，剖析正規表達式以形成語法樹。如上文關於圖3所解釋，剖析產生所述源碼的一股表示。另外，剖析可考量由FSM引擎600支持和不支持的正規表達式。所支持的正規表達式可轉換成適當機器碼實施方案；然而，不受支持的正規表達式可(例如)產生錯誤，或轉換成在功能性上接近於不受支持的正規表達式的受支持的機器碼。[0072]在方框1004處，將所述語法樹轉換成自動機。如上文關於圖3所提及，轉換所述語法樹將所述語法樹轉換成包括多個狀態的自動機。在實例中，可部分基於FSM引擎600的硬體來轉換所述自動機。
[0073]在實例中，用於自動機的輸入符號包含字母、數字O到9和其它可列印字符的符號。在實例中，所述輸入符號通過字節值O到255 (包含在內)來表示。在實例中，自動機可表示為有向圖，其中所述圖的節點對應於狀態集合。在實例中，被自動機接受(例如，匹配)的數據為在按順序地輸入到所述自動機中時將達到最終狀態的所有可能數據的集合。被所述自動機接受的數據中的每一符號沿從開始狀態到一個或一個以上最終狀態的路徑而行。被正規表達式接受的數據為匹配所述正規表達式的所有可能字符串的集合。給定正規表達式「R」，將「R」被接受的數據表示為￡ (R)。
[0074]在實例中，所述自動機包括通用狀態以及專用狀態。在編譯程序產生用於FSM引擎600的機器碼的實例中，通用狀態可對應於SME604、605，且通用狀態因此在本文中被稱作「SME狀態」。此外，當編譯程序產生用於FSM引擎600的機器碼時，專用狀態可對應於計數器624且因此在本文中被稱作「計數器狀態」。在實例中，自動機中的SME狀態1:1映射到FSM引擎600中的SME(例如，SME604、605)，不映射到SME的自動機的開始狀態除外。計數器624可能或可能不1:1映射到計數器狀態。
[0075]在實例中，在所述自動機中可使用輸入符號範圍外的特殊轉變符號。這些特殊轉變符號可用以(例如)使得能夠使用專用元件224。此外，特殊轉變符號可用以提供在不同於輸入符號的一些事物上發生的轉變。舉例來說，特殊轉變符號可指示當啟用第二狀態和第三狀態時將啟用(例如，轉變到)第一狀態。因此，當激活第二狀態和第三狀態時激活第一狀態，且到所述第一狀態的轉變並非直接取決於輸入符號。顯著地，指示在啟用第二狀態和第三狀態時將啟用第一狀態的特殊轉變符 號可用以將(例如)通過布林邏輯執行的布林AND函數表示為專用元件224。在實例中，可使用特殊轉變符號來指示計數器狀態已達到零，且因此轉變到下遊狀態。
[0076]在實例中，可使用例如葛魯許柯夫(Glushkov)的方法等標準技術中的一者來構造自動機。在實例中，所述自動機可為無ε的同構自動機(homogeneous automaton)。下文關於圖4、11、12、13A、13B和14提供關於將語法樹轉換成自動機的額外細節。
[0077]在方框1006處，一旦已將所述語法樹轉換成自動機，便優化所述自動機。所述自動機可經優化以尤其減少其複雜性和大小。可通過組合冗餘狀態來優化所述自動機。
[0078]在方框1008處，將所述經優化的自動機轉換成連線表。將所述自動機轉換成連線表將所述自動機的每一狀態映射到FSM引擎600上的硬體元件(例如，SME604、605、專用元件624)的個例。而且，確定所述個例之間的連接以產生所述連線表。
[0079]在方框1010處，放置所述連線表以針對所述連線表的每一個例選擇所述目標裝置的特定硬體元件(例如，SME604、605、專用元件624)。在實例中，放置基於所述FSM引擎600的一股輸入和輸出約束而選擇每一特定硬體元件。
[0080]在方框1012處，對經放置的連線表進行路由以確定可編程開關(例如，塊間開關603、塊內開關608和行內開關612)的設定以便將選定硬體元件耦合在一起以實現連線表所描述的連接。在實例中，通過確定FSM引擎600的將用以連接選定的硬體元件的特定導體和所述可編程開關的設定來確定所述可編程開關的設定。路由可能要考量比方框1010處的放置多的在硬體元件之間的連接的特定限制。因此，路由可調整如由全局放置確定的硬體元件中的一些的位置，以便在給出對FSM引擎600的導體的實際限制的情況下進行適當連接。
[0081]一旦對連線表進行放置和路由，便可將所放置和經路由的連線錶轉換成用於編程FSM引擎200的多個位。所述多個位在本文中被稱作映像。
[0082]在方框1014處，通過編譯程序發布映像。所述映像包括用於編程FSM引擎600的特定硬體元件和/或可編程開關的多個位。在所述映像包括多個位(例如，O和I)的實施例中，所述映像可被稱作二進位映像。所述位可加載到FSM引擎600上以編程SME604、605、專用元件624和可編程開關的狀態，以使得經編程的FSM引擎600實施具有由源碼描述的功能性的FSM。放置(方框1010)和路由(方框1012)可將在FSM引擎600中的特定位置處的特定硬體元件映射到自動機中的特定狀態。因此，所述映像中的位可編程所述特定硬體元件和/或可編程開關以實施所要功能。在實例中，可通過將機器碼保存到計算機可讀媒體來發布所述映像。在另一實例中，可通過在顯示裝置上顯示所述映像來發布映像。在又一實例中，可通過將所述映像發送到另一裝置(例如，用於將所述映像加載到FSM引擎600上的編程裝置)來發布映像。在再一實例中，可通過將所述映像加載到平行機(例如，FSM引擎600)上來發布映像。
[0083]在實例中，可通過將來自映像的位值直接加載到SME604、605和其它硬體元件624或通過將映像加載到一個或一個以上寄存器中且接著將來自寄存器的位值寫入到SME604、605和其它硬體元件624來將映像加載到FSM引擎600上。在實例中，FSM引擎600的硬體元件(例如，SME604、605、其它元件624、可編程開關603、608、612)經存儲器映射，以使得計算機(例如，耦合到所述計算機或與所述計算機成一體的編程裝置)可通過將映像寫入到一個或一個以上存儲器地址而將映像加載到FSM引擎600上。
[0084]如上文所論述， 圖 4詳述用於將語法樹轉換成自動機的方法400。以下描述提供用於在目標裝置為平行機(例如，FSM引擎600)時將語法樹轉換成自動機的額外細節。
[0085]可以源碼描述的一類正規表達式包含量化。量化在此項技術中為眾所周知的，且用以描述重複樣式。作為實例，「A(B) {nl, n2}C」為一股正規表達式,其中A、B和C為子表達式，且「(B) {nl, n2}」包括量化。如本文中所描述，使用大寫字母來表示正規表達式或正規表達式的一部分(例如，子表達式)。可將雙引號添加到正規表達式或子表達式周圍以避免混淆。因此，描述表達式的大寫字母可對應於用於多個輸入符號的搜索字符串。舉例來說，表達式「A」可對應於輸入字符串『abbc』。
[0086]此外，應理解，術語表達式和子表達式在本文中僅用於關係描述(例如，子表達式為表達式的一部分)，且術語表達式和子表達式不應限於任何特定長度、語法或字符數目。明確地說，源碼可包含大量字符(包含元字符和搜索字符)，其中整組字符或其任何個別部分可被視為「表達式」。舉例來說，以下各者中的每一者可被視為表達式:「a(bb|d? ){5，20} C」、「 (b) {0，10} 」、「 (b I d)，，和 「b」。
[0087]將量化以正規表達式表達為「(B) {nl，n2} 」，其中B為子表達式，且nl和n2為指定允許前述子表達式出現多少次的整數。B在本文中被稱作重複子表達式，因為B為重複了由nl和n2指定的次數的子表達式。為了匹配量化「(B) {nl，n2} 」，必須匹配重複子表達式B nl到n2次。舉例來說，正規表達式「(B) {5，7) 」將要求子表達式B匹配5、6或7次。在正規表達式「A(B) {nl，n2}C」中，子表達式A在本文中被稱作驅動表達式，因為子表達式A在匹配時轉變為量化。另外，為了繼續重複和遞增針對所述量化的計數，必須連續地匹配所述量化的重複子表達式。即，當重複子表達式在所述量化的給定循環期間不匹配時，所述量化結束。在實例中，符號「？」也對應於量化，其中在「？ 」之前的符號可識別一次或零次。
[0088]當目標裝置為FSM引擎600時，方法400可識別某些量化並將所述量化映射到FSM引擎600上的計數器624。用計數器624實施某些量化可導致優於用狀態機元件604、605實施量化的效率。因此，可簡化針對FSM引擎600的自動機和所得映像。舉例來說，實施量化的語法樹的部分可需要大量SME604、605來實施。然而，在實例中，這些量化中的一些可使用計數器624來實施，計數器624具有比SME604、605將需要的狀態少的狀態。
[0089]在方框402處，編譯程序識別語法樹的對應於用FSM引擎600中的計數器624的可能的實施方案的量化的部分 。如果所述語法樹的部分不對應於量化，那麼方法400前進到方框408，在方框408處，將所述部分轉換成用於用SME604、605的實施方案的通用狀態。如果所述語法樹的部分確實對應於量化，那麼進一步分析所述量化以確定是否可用計數器624來實施所識別的部分。
[0090]在做出是否可能用計數器624來實施量化的確定之前，如果￡ (B)包含空字符串，那麼「B{nl，n2}」的量化重寫為「B' {0，n2}」，其中B'為B的非空字符串版本，￡ (B')=￡ (B) -Φ。舉例來說，「 (bcl) {10，20} 」可重寫為「 (be) {O, 20} 」，因為這些正規表達式接受正好相同的數據。接著，對於給定的量化B{nl，n2}，根據以下條件，所述量化可能用計數器來實施(方法前進到方框404)或者用SME來實施且無計數器(方法前進到方框408):
[0091].I)當(nl = O, n2 = -1)時，將藉助SME604、605來實施所述量化且無計數器624 (方框408)。在此，不需要計數器624。
[0092].2)當(nl = 1，n2 = -1)時，將藉助SME604、605來實施所述量化且無計數器624 (方框408)。在此，不需要計數器624。
[0093].3)當(nl > 1，η2 = -1)時，所述量化將分裂成兩個正規表達式B {nl_l}和B+，因為B{n，-1}等於B{nl-1}B+。可接著可能用計數器來實施量化B {nl_l}(方框404)，而將藉助SME604、605來實施B+且無計數器624 (方框408)。對於B+，不需要計數器624。
[0094].4)當(ηI = 0，η2 > O)時，將所述量化修改成(Β{1, η2}) ?，因為(Β{1, η2}) ?等於Β{0，η2}。可接著可能用計數器624來實施不可空Β{1，η2}(方框404)。
[0095].5)當(nl > 0，η2 > O)時，可能用計數器624將所述量化實施為B {ηI，η2}(方框404)。
[0096]總之，在不修改的情況下可能可用計數器624實施(方框404)的量化可被寫成B{nl，η2}，其中B為不可空的，nl > O、η2 > O且nl≤n2。
[0097]在方框404處，一旦編譯程序已識別了可能可用計數器624實施的量化，所述編譯程序便確定語法樹的對應於經識別部分的一部分是否為確定性的。當所述經識別部分為確定性時，可用一個或一個以上計數器624來實施所述經識別部分，且方法400前進到方框406，在方框406處，將所述經識別部分轉換成一個或一個以上計數器狀態以及一個或一個以上SME狀態。當所述經識別部分為非確定性時，不使用計數器624來實施所述經識別部分，且方法400前進到方框408，在方框408處，將所述經識別部分轉換成一個或一個以上SME狀態。[0098]大體上,方框406和方框408對應於用以將量化轉換成自動機的兩種方式。在方框406處，使用一個或一個以上計數器狀態來轉換所述量化，可能結合一個或一個以上SME狀態以將所述量化實施為循環。在方框408處，通過「展開」所述量化來轉換所述量化，其包含使用SME狀態且無計數器狀態。展開包括用非量化語法來重寫所述量化。舉例來說，正規表達式「(b|c) {1，2}」可展開為「(b|c) (b|c) ? 」。展開的優點包含(I)所得自動機為有向非循環圖(DAG)且可易於分析和實施，和(2)所得自動機可用通用元件(尤其是狀態機元件)而非專用元件來實施。然而，用以實施展開量化的通用狀態且因此狀態機元件的數目與nl和n2成線性關係。因此，當nl或n2為大數目時，狀態的數目可為大的。明確地說，真實資源為有限的，因此，在一些實例中，此展開技術僅用於有限類別的量化。
[0099]然而，當目標裝置具有經設計以實施計數功能的專用元件(例如，計數器624)時，在某些情況下可避免展開。此方法的優點為在自動機中需要重複表達式的較少副本，且副本的數目獨立於nl和n2。因此，可節省顯著資源。舉例來說，可使用一個或一個以上計數器624以通過用重複表達式和一個或一個以上計數器624產生循環來實施量化。每當重複表達式匹配時，計數器624便可遞增(或遞減)。可接著重新激活所述重複表達式以搜索另一匹配。當計數器624已遞增(或遞減)了等於所述量化所規定的次數時，計數器624可在所述量化之後激活所述狀態。因此，可用較少SME604、605來實施所述量化，因為再用了用以實施重複表達式的SME。然而，歸因於整個自動機(例如，對應於整個語法樹)的平行性(即，可同時處於作用中的多個狀態)，在一些實例中，計數器624可僅用於對應於整個自動機的確定性部分的量化。
[0100] 圖11說明轉換成自動機1100的正規表達式的實例，所述自動機1100使用專用計數器狀態1102來實施量化。自動機1100對應於正規表達式「A⑶{nl，nl}C」，其中所述量化的兩個計數值(例如，nl、n2)相等。由於所述計數值中的兩者相等，因此使用單一計數器624來實施所述量化。如圖11中所展示，自動機1100可表示為有向圖，其中所述圖的節點對應於一組狀態。
[0101]正規表達式「A(B) {nl, nl}C」轉換成若干SME狀態1104、1106、1110、1108和計數器狀態1102。SME狀態1104、1106、1108、1110對應於子表達式和「C」。SME狀態1104、1106、1110、1108可用SME604、605來實施，而計數器狀態1102可用計數器624來實施。當在FSM引擎600上實施自動機1110時，對應於計數器狀態1102的計數器624最初加載有值nl且經設定以在計數器624中的值達到零時斷言零計數輸出。當nl等於n2時，計數器624可經設定為停止O和脈衝輸出模式，其意味一旦計數器624的值達到零，計數器624便將斷言其輸出，且計數器624將維持於零且不發出任何信號直到復位計數器624為止。
[0102]自動機1100在狀態1104處開始且在匹配子表達式「A」後即刻轉變到狀態1106。當處於狀態1106處，每當子表達式「B」匹配時，便激活計數器狀態1102的IN埠，且計數器狀態1102遞減一。另外，每當子表達式「B」匹配時，狀態1106便激活其自身以及激活狀態1110。當計數器狀態1102達到零時，激活輸出，且自動機1100將接著搜索子表達式「C」。在接下來的循環中，將出現兩種情形:第一種情形在「~B」匹配時出現。當「~B」匹配時，復位計數器狀態1102且將其值設定回到nl。因此，下次子表達式「A」匹配時，過程便從狀態1104開始。在第二種情形中，狀態1106的自循環仍在作用中，且在子表達式「B」匹配時繼續觸發計數器1102的IN埠。由於計數器狀態1102是在脈衝模式下配置，因此儘管狀態1106的自循環仍處於作用中，但計數器狀態1102將不會再次激活其輸出。
[0103]子表達式「B」的否定版本在本文中也被稱作「?B」。在實例中，子表達式「B」的否定版本用以激活計數器狀態1102的復位埠。這是因為，由於「B」是量化「⑶{nl，nl} 」的重複表達式，因此當在輸入處接收到不同於B的任一者(例如，「B」的否定版本)時(一旦已激活了狀態1106)，那麼所述量化結束且因此復位計數器。因此，一旦激活了狀態1110，便復位計數器狀態1102，且當子表達式「B」的否定版本匹配時，所述量化不匹配。在實例中，使用標準自動機理論來否定重複表達式。
[0104]儘管當nl等於n2時，說明並描述單一計數器狀態624實施量化，但應認識到，多個計數器624可級聯以考量比單一計數器624支持的數目大的數目。
[0105]圖12說明轉換成自動機1200的正規表達式的另一實例，所述自動機1200使用多個專用計數器狀態1202、1204來實施具有量化的正規表達式。自動機1200對應於正規表達式「A(B) {nl，n2}C」，其中nl小於n2。使用兩個計數器狀態1202、1204，因為在量化「(B){nl, n2}」中nl小於n2。計數器狀態1202、1204經配置到停止O和保持模式，其意味，當計數器狀態1202、1204達到零時，計數器狀態1202、1204激活其輸出，且在復位計數器狀態1202、1204之前，計數器狀態1202、1204維持於零且每當激活IN埠時便保持激活其輸出。在此實例中，從計數器狀態1202到計數器狀態1204的延時佔用兩個循環。
[0106]計數器狀態1202最初設定為nl，且計數器狀態1204最初設定為n2。當子表達式「A」匹配時，所述自動機從狀態1206轉變到狀態1208。一旦激活了狀態1208，每當子表達式「B」匹配時，便激活計數器狀態1202和計數器狀態1204兩者的IN埠。因此，計數器狀態1202和計數器狀態1204兩者遞減一。當計數器狀態1202達到零時，激活其輸出，且自動機1200接著搜索子表達式「C」的匹配且激活狀態1210。一旦子表達式「B」已匹配了nl次，計數器狀態1204的值便為n2-nl。稍後，每當子表達式「B」匹配時，便激活計數器狀態1202的IN埠，且計數器狀態1202的值維持於零，且仍激活其輸出。同時，計數器狀態1204繼續遞減。當子表達式「B」匹配了 n2次時，計數器狀態1204也達到零，且激活其輸出，此驅動計數器狀態1202的復位埠。由於計數器狀態1204到計數器狀態1202的延時為兩個循環，因此計數器狀態1202繼續激活其輸出到狀態1210。在下一個循環中，從計數器狀態1204的輸出復位計數器狀態1202，且不從計數器狀態1202斷言輸出。在接下來的循環中，將出現兩種情形。在第一種情形中，「?B」匹配。計數器狀態1202和計數器狀態1204兩者均通過狀態1212復位，且其值分別設定為nl和n2。因此，下次狀態1206為作用中且下次子表達式「A」匹配時，激活狀態1208，且計數器狀態1202、1204再次遞減。在第二種情形中，狀態1208的自循環維持激活，且激活計數器狀態1202、1204兩者的IN埠。由於計數器狀態1204繼續激活其輸出，因此計數器狀態1202繼續復位，且只要狀態1208的自循環處於作用中便不激活其輸出。
[0107]另外，在狀態1208處於作用中時子表達式「B」的匹配激活了狀態1212。一旦狀態1212激活且「?B」匹配，便復位計數器狀態1202、1204，且不匹配所述量化。使用子表達式「B」的否定版本，因為「B」為量化「⑶{nl，n2}」的重複表達式。因此，可重複地匹配在狀態1208下的表達式『B』從nl到n2次。儘管說明並描述了單一計數器分別實施下(例如，nl)和上(例如，n2)閾值，但應認識到，如所屬領域的技術人員所知，多個計數器可級聯以考量比單一計數器支持的數目大的數目。
[0108]在使用計數器狀態轉換量化之前，在方框404處，編譯程序確定對應於所述量化的自動機是否為確定性的。在實例中，當表達式滿足下文所論述的無前綴、無重入條件兩者時，所述自動機為確定性的。即，為了使量化映射到計數器624，所述量化應滿足如下文所論述的無前綴和無重入條件。
[0109]參考圖12的自動機1200，無重入條件要求從狀態1206到狀態1208的邊不可激活，而計數器狀態1202處於作用中(例如，當計數器狀態1202正在計數時)。即，確定在已處理所述量化時是否可匹配所述量化的驅動表達式。匹配驅動表達式意味，緊跟在所述量化之前的狀態將轉變到對應於所述量化的狀態。因此，將「重入」所述量化，而計數器狀態仍處理重複表達式。由於在FSM引擎600的此實例中，計數器624在任何給定時間時可僅實施單一循環，因此在循環已經處理時轉變到量化可致使計數器624在給定循環期間不正確地計數。
[0110]圖13A和13B說明自動機1500和1314，可用以進一步解釋無重入條件。圖13A說明對應於語法樹中的量化的實例自動機1500，其中編譯程序可進行分析以確定對應於所述量化的自動機是否為確定性的。
[0111]自動機1500對應於正規表達式「abb ? (b | c) {1，2} 」且包含開始狀態1502和最終狀態1312、1504。所述最終狀態在圖13A中識別為雙圓。最初激活開始狀態1502並在輸入符號『a』後即刻使其轉變到狀態1506。在輸入符號『b』時，狀態1506轉變到狀態1308和狀態1310兩者。在輸入符號『b』時狀態1308轉變到狀態1310，且在輸入符號『b』或『C，時，狀態1310轉變到狀態1312。在輸入符號『b』或『C，時，自動機1300從狀態1312轉變到狀態1304。
[0112]自動機1300包括正規表達式「abb ? (b | c) {1，2} 」的自動機，將檢查所述正規表達式是否符合無重入條件。 自動機1314包括從自動機1300的正規表達式「abb ? (b | c){1，2}」導出的正規表達式55( 「abb ? 」、「(b|c)⑵」)的自動機。SS (M, N)被定義為從M、N導出的正規表達式。導出步驟包含:1)串接M和N，結果表示為「麗」。2)構造「麗」的自動機，表示為A(MN)。3)如下地修改A (MN):a)使A (MN)的開始狀態驅動所有其它狀態，和b)使對應於「N」的所有狀態為最終狀態。最後，4)將經修改的自動機的正規表達式表示為SS (M，N)。SS (M，N)的被接受數據由從「MN」的任何狀態開始且在N的任何狀態處結束的子字符串組成。
[0113]無重入條件可定義如下。給出具有量化「八8{111，112}(:」的正規表達式，無重入條件需要￡(SS(A.Β{η!.η2}) Π ￡(Α)=0。換句話說，一旦子表達式「Α」匹配且計數器狀態1202開始計數，那麼為了滿足無重入條件，將不再次激活從狀態1206到狀態1208的邊，直到進行「B{nl，n2}」(匹配或失敗)為止。舉例來說，用計數器624將不會正確地實施「abb」 e￡ ( 「abb ?，，) Π ￡ (SS( 「abb ? 」，「(blc) {2} 」)，和因此 「abb ? (b | c) {1,2} 」。
[0114]現在參看圖14，將參考自動機1400來解釋無前綴條件。無前綴條件規定￡ (B)的任何字符串不應為￡ (B)的另一字符串的前綴，此將保證B不會致使計數器計數多於一次。換句話說，當量化的第一重複子表達式為所述量化的第二重複子表達式的前綴時，所述量化不實施為(且因此轉換為)計數器624。正式的陳述為:對於所有Ii, Ij e ￡ (B)，Ii關Ij,要求(丨,1叩」夕}=0。[0115]舉例來說，正規表達式「a (b I be) {3}」不滿足無前綴條件。因此，將不使用計數器狀態來轉換正規表達式「a (b I be) {3}」，且因此將不用計數器624來實施。實情為，將不用任何計數器狀態來將正規表達式「a (b I be) {3} 」轉換成通用狀態。
[0116]如果用計數器624來實施正規表達式「a(b |bc) {3} 」，那麼將錯誤地匹配輸入「abbc」。舉例來說，自動機1400為使用計數器狀態1412對正規表達式「a(b | be) {3} 」的假設轉換的結果。如下文所描述，此轉換導致計數器狀態1412的不正確執行。最初激活狀態1402，且在輸入「a」處，狀態1402激活狀態1404。在狀態1404激活的情況下，在輸入「b」處，狀態1404激活狀態1406、1408且再激活自身，即狀態1404。而且，在輸入「b」處，狀態1404激活計數器1412的IN埠，其中計數器狀態1412的初始值處於3且接著減少到2。在狀態1404、1406和1408激活的情況下，在另一輸入「b」處通過狀態1404再次激活計數器狀態1412的IN埠，且計數器狀態1412中的值減少到I。此時，激活狀態1404、1406和1408。接著，輸入值「c」致使計數器狀態1412的IN埠通過狀態1408激活以將計數器1412中的值減少到O。在計數器1412中的值處於零的情況下，激活輸出，且激活狀態1414，此指示匹配。然而，此匹配為錯誤肯定，因為在序列「abbc」不滿足正規表達式「a(b|bc){3}」時，輸入「abbc」已造成匹配。因此，正規表達式「a (b I be) {3} 」不滿足無前綴條件，且不應使用計數器狀態來轉換且不應用計數器624來實施。
[0117]如果在方框404處，所述量化滿足無前綴條件和無重入條件兩者，那麼在方框406處使用專用計數器狀態來轉換所述量化。可如上文關於圖12和13所描述股轉換所述量化。然而，如果所述量化不滿足無前綴或無重入條件，那麼在方框408處通過展開所述量化且將所述量化轉換成通用狀態且無計數器狀態624來轉換所述量化。因此，用SME604、605而不是計數器624來實施所述量化。
[0118]本文中所描述的方法實例可至少部分為機器或計算機實施的。一些實例可包含編碼有指令的計算機可讀媒體或機器可讀媒體，所述指令可操作以配置電子裝置以執行如上述實例中所描述的方法。這些方法的實施方案可包含碼，例如微碼、組合語言碼、高級語言碼等。此類碼可包含用於執行各種方法的計算機可讀指令。碼可形成電腦程式產品的部分。另外，碼在執行期間或在其它時間時可有形地存儲於一個或一個以上易失性或非易失性計算機可讀媒體上。這些計算機可讀媒體可包含(但不限於)硬碟、可裝卸式磁碟、可裝卸式光碟(例如，壓縮光碟和數字視頻光碟)、磁帶盒、存儲卡或存儲條、隨機存取存儲器(RAM)、只讀存儲器(ROM)等。
[0119]圖15大體上說明具有馮諾依曼架構的計算機1500的實例。在閱讀和理解了本發明的內容之後，所屬領域的技術人員將理解在基於計算機的系統中可從計算機可讀媒體啟動軟體程序以使其執行以軟體程序定義的功能的方式。所屬領域的技術人員將進一步理解，可使用各種程式語言來產生經設計以實施並執行本文所揭示的方法的一個或一個以上軟體程序。可使用對象導向語言(例如，Java、C++或一種或一種以上其它語言)以對象導向格式來結構化所述程序。或者，可使用程序語言(例如，組合語言、C等)以程序導向格式來結構化所述程序。軟體組件可使用所屬領域的技術人員所眾所周知的許多方案中的任一者來通信，例如應用編程接口或過程間通信技術，包含遠程程序呼叫或其它。各個實施例的教示不限於任何特定程式語言或環境。
[0120]因此，可實現其它實施例。舉例來說，製造物件(例如，計算機、存儲器系統、磁碟或光碟、某一其它存儲裝置，或任何類型的電子裝置或系統)可包含一個或一個以上處理器1502，所述一個或一個以上處理器1502耦合到上面存儲有指令1524(例如，電腦程式指令)的計算機可讀媒體1522，例如存儲器(例如，可裝卸式存儲媒體，以及包含電、光或電磁導體的任何存儲器)，所述指令在由所述一個或一個以上處理器1502執行時導致執行相對於上述方法所描述的動作中的任一者。
[0121]計算機1500可採取具有處理器1502的計算機系統的形式，所述處理器1502直接和/或使用總線1508而耦合到許多組件。這些組件可包含主存儲器1504、靜態或非易失性存儲器1506和大容量存儲裝置1516。耦合到處理器1502的其它組件可包含輸出裝置1510(例如，視頻顯示器)、輸入裝置1512(例如，鍵盤)和光標控制裝置1514(例如，滑鼠)。用以將處理器1502和其它組件耦合到網絡1526的網絡接口裝置1520還可耦合到總線1508。指令1524可利用許多眾所周知的傳送協議(例如，HTTP)中的任一者經由網絡接口裝置1520跨越網絡1526來進一步發射或接收。耦合到總線1508的這些元件中的任一者可不存在，單獨地存在，或以複數形式存在，這取決於待實現的特定實施例。
[0122]在實例中，處理器1502、存儲器1504、1506或存儲裝置1516中的一者或一者以上可各自包含指令1524，所述指令1524在執行時可致使計算機1500執行本文所描述的方法中的任何一者或一者以上。在替代實施例中，計算機1500操作為單獨裝置或可連接(例如，聯網)到其它裝置。在聯網環境中，計算機1500可以伺服器一客戶端網絡環境中的伺服器或客戶端裝置的能力來操作，或操作為對等(或分散式)網絡環境中的對等裝置。計算機1500可包含個人計算機(PC)、平板PC、機頂盒(STB)、個人數字助理(PDA)、蜂窩式電話、web器具、網絡路由器、交換機或橋接器，或能夠執行指令集(順序的或其它)的任何裝置，所述指令集指定將由所述裝置採取的行動。另外，雖然僅說明了單一計算機1500，但術語「計算機」還應被視為包含個別地或共同地執行一(或多個)指令集以執行本文中所論述的方法中的任何一者或一者以上的裝置的任何集合。
[0123]計算機1500還可包含用於使用一個或一個以上通信協議(例如，通用串行總線(USB)、IEEE1394等)與外圍裝置通信的輸出控制器1528。輸出控制器1528可(例如)將映像提供到通信地耦合到計算機1500的編程裝置1530。編程裝置1530可經配置以編程平行機(例如，平行機500、FSM引擎600)。在其它實例中，編程裝置1530可與計算機1500集成且耦合到總線1508或可經由網絡接口裝置1520或另一裝置與計算機1500通信。
[0124]雖然計算機可讀媒體1524展示為單一媒體，但術語「計算機可讀媒體」應被視為包含存儲所述一個或一個以上指令集1524的單一媒體或多個媒體(例如，集中式或分散式資料庫，或相關聯的高速緩衝存儲器和伺服器，和或各種存儲媒體，例如處理器1502寄存器、存儲器1504、1506和存儲裝置1516)。術語「計算機可讀媒體」還應被視為包含以下任何媒體，其能夠存儲、編碼或載運供計算機執行的指令集且致使所述計算機執行本發明的方法中的任何一者或一者以上，或能夠存儲、編碼或載運供此指令集利用或與此指令集相關聯的數據結構。術語「計算機可讀媒體」因此應被視為包含(但不限於)有形媒體，例如固態存儲器、光媒體和磁性媒體。
[0125]提供摘要以遵照需要摘要的37C.F.R.章節1.72 (b)，此將允許讀者確定技術揭示內容的性質和要旨。在理解到摘要將不用以限制或解釋權利要求書的範圍或涵義的情況下提交摘要。所附權利要求書特此併入詳細描述中，其中每一權利要求依賴於其自身而作為單獨實施例。
[0126]實例實施例
[0127]實例I包含一種計算機實施方法，所述方法用於產生對應於包含通用元件和專用元件的一組元件的機器碼，所述方法包括:確定有關係連接的運算符的布置中的一部分是否滿足將被映射到專用元件的條件；如果所述部分滿足所述條件，那麼將所述部分映射到專用元件；和將有關係連接的運算符的所述布置轉換成機器碼。
[0128]實例2包含一種計算機可讀媒體，其包含指令，所述指令在由計算機執行時致使所述計算機執行包括以下各者的操作:識別有關係連接的運算符的布置中的對應於目標裝置的專用元件的一部分，其中所述目標裝置還包含通用元件；確定所述部分是否滿足將被映射到所述專用元件的條件；將所述布置轉換成包括多個狀態的自動機，其中如果所述部分滿足所述條件，那麼使用對應於所述專用元件的專用狀態來轉換所述部分；和將所述自動機轉換成機器碼。
[0129]實例3包含一種計算機，其包括:存儲器，其上面存儲有軟體；和處理器，其通信地耦合到所述存儲器，其中所述軟體在通過所述處理器執行時致使所述處理器將正規表達式編譯成用於目標裝置的碼，其中所述目標裝置支持第一類型的元件和至少一種其它類型的元件；其中編譯包含將對應於所述第一類型的元件的第一正規表達式映射到所述第一類型的元件；且其中編譯包含將不對應於所述第一類型的元件的第二正規表達式映射到所述至少一種其它類型的元件。
[0130]實例4包含一種系統，其包括計算機，所述計算機經配置以識別有關係連接的運算符的布置中的對應於目標裝置的專用元件的一部分，其中所述目標裝置還包含通用元件；確定所述部分是否滿足將被映射到所述專用元件的條件；將所述布置轉換成包括多個互連狀態的自動機，其中如果第一部分滿足所述條件，那麼將所述部分轉換成對應於所述專用元件的專用狀態；和將所述自動機轉換成機器碼；和所述系統包括用於編程平行機的裝置，所述裝置經配置以將所述機器碼加載到所述平行機上。
[0131]在實例5中，實例I到4中任一者的標的可任選地包含，其中所述機器碼包括用於平行機的映像。
[0132]在實例6中，實例I到5中任一者的標的可任選地包含，其中所述組元件包含供在處理器上執行的指令集，且其中所述專用元件包含專用指令。
[0133]在實例7中，實例I到6中任一者的標的可任選地包含識別有關係連接的運算符的所述布置中的對應於專用元件的一部分，其中確定一部分是否滿足條件，確定經識別的所述部分是否滿足條件；其中映射包含將所述布置轉換成包括多個狀態的自動機，其中如果所述部分滿足所述條件，那麼使用對應於所述專用元件的專用狀態來轉換所述部分；且其中轉換所述布置包含將所述自動機轉換成機器碼。
[0134]在實例8中，實例I到7中任一者的標的可任選地包含，其中識別所述布置中的對應於專用元件的一部分包括識別所述有關係連接的運算符中的可使用所述專用元件實施的運算符。
[0135]在實例9中，實例I到8中任一者的標的可任選地包含，其中將所述布置轉換成自動機包括將所述布置中的運算符中的每一者轉換成所述多個狀態中的一者或一者以上。
[0136]在實例10中，實例I到9中任一者的標的可任選地包含，其中如果所述部分不滿足所述條件，那麼使用通用狀態且不使用對應於專用元件的專用狀態來轉換所述部分，其中所述通用狀態對應於所述通用元件。
[0137]在實例11中，實例I到10中任一者的標的可任選地包含，其中所述部分包括第一部分，且其中如果所述布置的第二部分並未被識別為對應於專用元件，那麼使用通用狀態且不使用對應於專用元件的專用狀態來轉換所述第二部分，其中所述通用狀態對應於通用元件。
[0138]在實例12中，實例I到11中任一者的標的可任選地包含，其中所述組元件包含平行機的一組硬體元件，其中所述通用元件包括可編程元件且其中所述專用元件包含計數器。
[0139]在實例13中，實例I到12中任一者的標的可任選地包含，其中所述可編程元件包括狀態機元件。
[0140]在實例14中，實例I到13中任一者的標的可任選地包含，其中所述狀態機元件包含存儲器單元。
[0141]在實例15中，實例I到13中任一者的標的可任選地包含，其中所述存儲器單元包括易失性存儲器單元。
[0142]在實例16中，實例I到15中任一者的標的可任選地包含進一步包括發布所述機器碼。
[0143]在實例17中，實例I到16中任一者的標的可任選地包含，其中發布所述機器碼包含將所述機器碼加載到平行機上。
[0144]在實例18中，實例I到17中任一者的標的可任選地包含，其中發布所述機器碼包含將所述機器碼存儲於計算機可讀媒體上。
[0145]在實例19中，實例I到18中任一者的標的可任選地包含，其中所述指令致使所述計算機執行包括以下各者的操作:將源碼轉換成所述布置；和發布所述機器碼。
[0146]在實例20中，實例I到19中任一者的標的可任選地包含，其中確定所述部分是否滿足將被映射到專用元件的條件包括確定所述部分是否為確定性的。
[0147]在實例21中，實例I到20中任一者的標的可任選地包含，其中識別所述布置的一部分包含識別量化；且其中確定所述部分是否為確定性的包含確定在處理所述量化時是否可匹配所述量化的驅動表達式。
[0148]在實例22中，實例I到21中任一者的標的可任選地包含，其中識別所述布置的一部分包含識別量化；且其中確定所述部分是否為確定性的包含確定所述量化的重複表達式是否為所述量化的另一重複表達式的前綴。
[0149]在實例23中，實例I到22中任一者的標的可任選地包含，其中識別所述布置中的一部分包含識別量化。
[0150]在實例24中，實例I到23中任一者的標的可任選地包含，其中確定所述部分是否為確定性的包含確定在處理所述量化時是否可匹配所述量化的驅動表達式，且確定所述量化的重複表達式是否為所述量化的另一重複表達式的前綴。
[0151]在實例25中，實例I到24中任一者的標的可任選地包含，其中所述專用元件包含在所述自動機中具有對應計數器狀態的計數器，且所述通用元件包含在所述自動機中具有對應狀態機元件狀態的狀態機元件。[0152]在實例26中，實例I到25中任一者的標的可任選地包含，其中當所述部分對應於量化且所述部分為確定性時，將所述部分實施為循環，所述循環包括所述量化的重複表達式和計數器狀態，其中所述計數器狀態經配置以對所述重複表達式匹配的次數計數，且其中在所述重複表達式匹配了通過所述量化指定的次數時所述計數器狀態激活下遊狀態。
[0153]在實例27中，實例I到26中任一者的標的可任選地包含，其中所述循環通過與所述重複表達式的否定版本的匹配而退出。
[0154]在實例28中，實例I到27中任一者的標的可任選地包含，其中當所述量化可與單一數目個循環匹配時，配置所述重複表達式以斷言所述計數器狀態的計數輸入；配置所述重複表達式的否定版本以復位所述計數器狀態；和配置所述計數器狀態以在所述計數輸入已斷言了等於循環的數目的次數但未復位所述計數器狀態時斷言輸出。
[0155]在實例29中，實例I到28中任一者的標的可任選地包含，其中當所述量化可與多個數目個循環匹配時，配置所述重複表達式以斷言第一計數器狀態的計數輸入和第二計數器狀態的計數輸入；配置所述重複表達式以斷言所述第一計數器狀態的復位輸入和所述第二計數器狀態的復位輸入；配置所述第一計數器狀態以在所述第一計數器狀態的所述計數輸入已斷言了等於所述多個數目個循環的低閾值的次數但未復位所述第一計數器狀態時斷言輸出；和配置所述第二計數器狀態以在所述第二計數器狀態的計數輸入已斷言了等於所述多個數目個循環的高閾值的次數但未復位所述第二計數器狀態時斷言所述第二計數器狀態的輸出，其中所述第二計數器狀態的輸出經配置以斷言所述第一計數器狀態的復位輸入。
[0156]在實例30中，實例I到29中任一者的標的可任選地包含，其中所述目標裝置包括平行機，且所述第一類型的元件為第一類型的硬體元件，且所述至少一個其它類型的元件包含第二類型的硬體元件。
[0157]在實例31中，實例I到30中任一者的標的可任選地包含，其中所述第二類型的硬體元件可接收輸入流且根據所述輸入流而提供輸出；且其中所述第一類型的硬體元件不接收所述輸入流且根據來自所述目標裝置的其它元件的輸入而提供輸出。
[0158]在實例32中，實例I到31中任一者的標的可任選地包含，其中所述第一類型的元件為計數器且所述第二類型的元件為狀態機元件。
[0159]在實例33中，實例I到32中任一者的標的可任選地包含確定正規表達式是否為對應於所述第一類型的元件的類型；且當所述正規表達式並非對應於所述第一類型的元件的類型時，將所述正規表達式映射到所述至少一種其它類型的元件。
[0160]在實例34中，實例I到33中任一者的標的可任選地包含，其中確定正規表達式是否為對應於所述第一類型的元件的類型包含確定所述正規表達式是否為量化；且當所述正規表達式並非量化時，將所述正規表達式映射到所述至少一種其它類型的元件。
[0161]在實例35中，實例I到34中任一者的標的可任選地包含確定所述量化是否為確定性的；當所述量化為確定性時，將所述正規表達式映射到所述第一類型的元件；和當所述量化並非確定性時，將所述正規表達式映射到所述至少一種其它類型的元件。
[0162]在實例36中，實例I到35中任一者的標的可任選地包含，其中確定所述量化是否為確定性的包含確定在處理所述量化時是否可匹配所述量化的驅動表達式，且所述量化的重複表達式是否為所述量化的另一重複表達式的前綴。[0163]在實例37中，實例I到36中任一者的標的可任選地包含，其中編譯包含剖析所述正規表達式以形成語法樹；將所述語法樹轉換成自動機；將所述自動機轉換成連線表；放置所述連線表的個例；和對所述連線表的個例之間的連接進行路由。
[0164]在實例38中，實例I到37中任一者的標的可任選地包含，其中所述正規表達式包括用於搜索無結構數據的準則。
[0165]在實例39中，實例I到38中任一者的標的可任選地包含，其中確定所述部分是否滿足將被映射到專用元件的條件包括確定所述部分是否為確定性的。
[0166]在實例40中，實例I到39中任一者的標的可任選地包含，其中識別所述布置的一部分包含識別量化；且其中確定所述部分是否為確定性的包含確定在處理所述量化時是否可匹配所述量化的驅動表達式，和所述量化的重複表達式是否為所述量化的另一重複表達式的前綴。
[0167]實例41包含通過使用權利要求1到40中任一者的標的產生的映像來編程的平行機。
【權利要求】
1.一種計算機實施方法，所述方法用於產生對應於包含通用元件和專用元件的一組元件的機器碼，所述方法包括: 確定有關係連接的運算符的布置中的一部分是否滿足將被映射到專用元件的條件； 如果所述部分滿足所述條件，那麼將所述部分映射到專用元件；和 將有關係連接的運算符的所述布置轉換成機器碼。
2.根據權利要求1所述的計算機實施方法，其中所述機器碼包括用於平行機的映像。
3.根據權利要求1所述的計算機實施方法，其中所述組元件包含供在處理器上執行的指令集，且其中所述專用元件包含專用指令。
4.根據權利要求1所述的計算機實施方法，其包括: 識別有關係連接的運算符的所述布置中的對應於專用元件的一部分，其中確定一部分是否滿足條件，確定經識別的所述部分是否滿足條件； 其中映射包含將所述布置轉換成包括多個狀態的自動機，其中如果所述部分滿足所述條件，那麼使用對應於所述專用元件的專用狀態來轉換所述部分；且 其中轉換所述布置包含將所述自動機轉換成機器碼。
5.根據權利要求4所述的計算機實施方法，其中識別所述布置中的對應於專用元件的一部分包括:識別所述有關係連接的運算符中的可使用所述專用元件來實施的運算符。
6.根據權利要求4所述的計算機實施方法，其中將所述布置轉換成自動機包括:將所述布置中的所述運算符中的每一者轉換成所述多個狀態中的一者或一者以上。
7.根據權利要求4所述的計算機實施方法，其中如果所述部分不滿足所述條件，那麼使用通用狀態且不使用對應於專用元件的專用狀態來轉換所述部分，其中所述通用狀態對應於所述通用元件。
8.根據權利要求4所述的計算機實施方法，其中所述部分包括第一部分，且其中如果所述布置的第二部分並未被識別為對應於專用元件，那麼使用通用狀態且不使用對應於專用元件的專用狀態來轉換所述第二部分，其中所述通用狀態對應於通用元件。
9.根據權利要求1所述的計算機實施方法，其中所述組元件包含平行機的一組硬體元件，其中所述通用元件包括可編程元件且其中所述專用元件包含計數器。
10.根據權利要求9所述的計算機實施方法，其中所述可編程元件包括狀態機元件。
11.根據權利要求10所述的計算機實施方法，其中所述狀態機元件包含存儲器單元。
12.根據權利要求11所述的計算機實施方法，其中所述存儲器單元包括易失性存儲器單元。
13.根據權利要求1所述的計算機實施方法，其進一步包括: 發布所述機器碼。
14.根據權利要求13所述的計算機實施方法，其中發布所述機器碼包含:將所述機器碼加載到平行機上。
15.根據權利要求13所述的計算機實施方法，其中發布所述機器碼包含:將所述機器碼存儲於計算機可讀媒體上。
16.一種計算機可讀媒體，其包含指令，所述指令在由計算機執行時致使所述計算機執行包括以下各者的操作: 識別有關係連接的運算符的布置中的對應於目標裝置的專用元件的一部分，其中所述目標裝置還包含通用元件； 確定所述部分是否滿足將被映射到所述專用元件的條件； 將所述布置轉換成包括多個狀態的自動機，其中如果所述部分滿足所述條件，那麼使用對應於所述專用元件的專用狀態來轉換所述部分；和 將所述自動機轉換成機器碼。
17.根據權利要求16所述的計算機可讀媒體，其中所述指令致使所述計算機執行包括以下各者的操作: 將源碼轉換成所述布置；和 發布所述機器碼。
18.根據權利要求16所述的計算機可讀媒體，其中確定所述部分是否滿足將被映射到專用元件的條件包括:確定所述部分是否為確定性的。
19.根據權利要求18所述的計算機可讀媒體，其中識別所述布置的一部分包含: 識別量化；且 其中確定所述部分是否為確定性的包含確定在處理所述量化時是否可匹配所述量化的驅動表達式。
20.根據權利要求18所述的計算機可讀媒體，其中識別所述布置的一部分包含: 識別量化；且· 其中確定所述部分是否為確定性的包含確定所述量化的重複表達式是否為所述量化的另一重複表達式的前綴。
21.根據權利要求18所述的計算機可讀媒體，其中識別所述布置中的一部分包含識別量化。
22.根據權利要求21所述的計算機可讀媒體，其中確定所述部分是否為確定性的包含:確定在處理所述量化時是否可匹配所述量化的驅動表達式；和確定所述量化的重複表達式是否為所述量化的另一重複表達式的前綴。
23.根據權利要求22所述的計算機可讀媒體，其中所述專用元件包含在所述自動機中具有對應計數器狀態的計數器，且所述通用元件包含在所述自動機中具有對應狀態機元件狀態的狀態機元件。
24.根據權利要求23所述的計算機可讀媒體，其中當所述部分對應於量化且所述部分為確定性時，將所述部分實施為循環，所述循環包括所述量化的重複表達式和計數器狀態，其中所述計數器狀態經配置以對所述重複表達式匹配的次數計數，且其中在所述重複表達式匹配了通過所述量化指定的次數時所述計數器狀態激活下遊狀態。
25.根據權利要求24所述的計算機可讀媒體，其中所述循環通過與所述重複表達式的否定版本的匹配而退出。
26.根據權利要求24所述的計算機可讀媒體，其中當所述量化可與單一數目個循環匹配時， 配置所述重複表達式以斷言所述計數器狀態的計數輸入； 配置所述重複表達式的否定版本以復位所述計數器狀態；和 配置所述計數器狀態以在所述計數輸入已斷言了等於循環的所述數目的次數但未復位所述計數器狀態時斷言輸出。
27.根據權利要求24所述的計算機可讀媒體，其中當所述量化可與多個數目個循環匹配時， 配置所述重複表達式以斷言第一計數器狀態的計數輸入和第二計數器狀態的計數輸A ； 配置所述重複表達式以斷言所述第一計數器狀態的復位輸入和所述第二計數器狀態的復位輸入； 配置所述第一計數器狀態以在所述第一計數器狀態的所述計數輸入已斷言了等於所述多個數目個循環的低閾值的次數但未復位所述第一計數器狀態時斷言輸出；和 配置所述第二計數器狀態以在所述第二計數器狀態的所述計數輸入已斷言了等於所述多個數目個循環的高閾值的次數但未復位所述第二計數器狀態時斷言所述第二計數器狀態的輸出，其中所述第二計數器狀態的所述輸出經配置以斷言所述第一計數器狀態的所述復位輸入。
28.一種計算機，其包括: 存儲器，其上面存儲有 軟體；和 處理器，其通信地耦合到所述存儲器，其中所述軟體在由所述處理器執行時致使所述處理器: 將正規表達式編譯成用於目標裝置的碼，其中所述目標裝置支持第一類型的元件和至少一種其它類型的元件； 其中編譯包含將對應於所述第一類型的元件的第一正規表達式映射到所述第一類型的元件；且 其中編譯包含將不對應於所述第一類型的元件的第二正規表達式映射到所述至少一種其它類型的元件。
29.根據權利要求28所述的計算機，其中所述目標裝置包括平行機，且所述第一類型的元件為第一類型的硬體元件，且所述至少一種其它類型的元件包含第二類型的硬體元件。
30.根據權利要求29所述的計算機，其中所述第二類型的硬體元件可接收輸入流並根據所述輸入流提供輸出；且 其中所述第一類型的硬體元件不接收所述輸入流且根據來自所述目標裝置的其它元件的輸入而提供輸出。
31.根據權利要求30所述的計算機，其中所述第一類型的元件為計數器且所述第二類型的元件為狀態機元件。
32.根據權利要求28所述的計算機，其中所述軟體致使所述處理器: 確定正規表達式是否為對應於所述第一類型的元件的類型；和 當所述正規表達式並非對應於所述第一類型的元件的類型時，將所述正規表達式映射到所述至少一種其它類型的元件。
33.根據權利要求32所述的計算機，其中確定正規表達式是否為對應於所述第一類型的元件的類型包含: 確定所述正規表達式是否為量化；和 當所述正規表達式並非量化時，將所述正規表達式映射到所述至少一種其它類型的元件。
34.根據權利要求33所述的計算機，其中所述軟體致使所述處理器: 確定所述量化是否為確定性的； 當所述量化為確定性的時，將所述正規表達式映射到所述第一類型的元件；和 當所述量化並非確定性的時，將所述正規表達式映射到所述至少一種其它類型的元件。
35.根據權利要求34所述的計算機，其中確定所述量化是否為確定性的包含確定在處理所述量化時是否可匹配所述量化的驅動表達式，和所述量化的重複表達式是否為所述量化的另一重複表達式的前綴。
36.根據權利要求28所述的計算機，其中編譯包含: 剖析所述正規表達式以形成語法樹； 將所述語法樹轉換成自動機； 將所述自動機轉換成連線表； 放置所述連線表的個例；和 對所述連線表的所述個例之間的連接進行路由。
37.根據權利要求36所述的計算機，其中所述正規表達式包括用於搜索無結構數據的準則。
38.一種系統,其包括: 計算機，其經配置以: 識別有關係連接的運算符的布置中的對應於目標裝置的專用元件的一部分，其中所述目標裝置還包含通用元件； 確定所述部分是否滿足將被映射到所述專用元件的條件； 將所述布置轉換成包括多個互連狀態的自動機，其中如果第一部分滿足所述條件，那麼將所述部分轉換成對應於所述專用元件的專用狀態；和將所述自動機轉換成機器碼；和 用於編程平行機的裝置，所述裝置經配置以將所述機器碼加載到所述平行機上。
39.根據權利要求38所述的系統，其中確定所述部分是否滿足將被映射到專用元件的條件包括:確定所述部分是否為確定性的。
40.根據權利要求38所述的系統，其中識別所述布置的一部分包含: 識別量化；且 其中確定所述部分是否為確定性的包含確定在處理所述量化時是否可匹配所述量化的驅動表達式，和所述量化的重複表達式是否為所述量化的另一重複表達式的前綴。
41.一種通過使用根據權利要求1所述的過程產生的映像編程的平行機。
【文檔編號】G06F9/45GK103547999SQ201280013886
【公開日】2014年1月29日 申請日期:2012年1月24日 優先權日:2011年1月25日
【發明者】許郡娟, 保羅·格倫迪寧 申請人:美光科技公司