用於元件利用的狀態分組的製作方法

2023-09-22 13:41:05 2

用於元件利用的狀態分組的製作方法
【專利摘要】揭示一種系統及方法的實施例，所述系統及方法用於從原始碼產生經配置以編程並行機的映像。一種此類並行機包括分組成對的多個狀態機元件SME，使得一對中的SME具有共同輸出。一種此類方法包括：將原始碼轉換成包含多個互連狀態的自動機；及將所述自動機轉換成包含實例的網表，所述實例對應於所述自動機中的狀態，其中轉換包括基於一對中的SME具有共同輸出的事實而使對應於SME對的狀態成對。可將所述網錶轉換成所述映像並加以發布。
【專利說明】用於元件利用的狀態分組
[0001]優先權主張
[0002]本專利申請案主張2011年I月25日申請的題為「用於元件利用的狀態分組(STATE GROUPING FOR ELEMENT UTILIZATION) 」的第 61/436，075 號美國臨時專利申請案的優先權的利益，所述美國臨時專利申請案的全文以引用方式特此併入本文中。
【技術領域】【背景技術】
[0003]用於並行機的編譯程序將原始碼轉換成用於配置(例如，編程)所述並行機的機器代碼(例如，映像)。所述機器代碼可在所述並行機上實施有限狀態機。將原始碼轉換成機器代碼的過程的一個階段包括形成網表。網表描述所述並行機的硬體元件的實例之間的連接性。所述網表可描述所述硬體元件之間的連接，使得所述硬體元件實施所述原始碼的功能性。

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

【附圖說明】
[0004]圖1說明根據本發明的各種實施例的並行機的實例。
[0005]圖2說明根據本發明的各種實施例的實施為有限狀態機引擎的圖1的並行機的實例。
[0006]圖3說明根據本發明的各種實施例的圖2的有限狀態機引擎的塊的實例。
[0007]圖4說明根據本發明的各種實施例的圖3的塊的行的實例。
[0008]圖5說明根據本發明的各種實施例的圖4的行的成對群組的實例。
[0009]圖6說明根據本發明的各種實施例的供編譯程序用以將原始碼轉換成經配置以編程圖1的並行機的映像的方法的實例。
[0010]圖7A及圖7B說明根據本發明的各種實施例的實例自動機。
[0011]圖8A及圖8B說明根據本發明的各種實施例的實例網表。
[0012]圖9說明根據本發明的各種實施例的用於執行圖6的編譯程序的實例計算機。
【具體實施方式】
[0013]以下描述及圖式充分地說明使所屬領域的技術人員能夠實踐的特定實施例。其它實施例可併入有結構、邏輯、電、過程及其它改變。一些實施例的部分及特徵可包括於其它實施例中或可替代其它實施例的部分及特徵。權利要求書中所陳述的實施例涵蓋那些權利要求的所有可用等效物。
[0014]本文件尤其描述基於並行機的物理設計產生網表的編譯程序。在一實例中，所述並行機的物理設計可包括所述並行機的狀態機元件之間的連接性限制。舉例來說，所述並行機中的狀態機元件可分組成共享一共同輸出的對。因此，所述編譯程序可基於一物理設計產生網表，在所述物理設計中，SME對共享一共同輸出。
[0015]圖1說明實例並行機100。並行機100可接收輸入數據並基於所述輸入數據提供一輸出。並行機100可包括用於接收輸入數據的數據輸入埠 110及用於將輸出提供到另一裝置的輸出埠 114。數據輸入埠 110提供用於將輸入到所述並行機100的數據的接□。
[0016]並行機100包括多個可編程元件，包括通用元件102及專用元件112。通用元件102可包括一個或一個以上輸入104及一個或一個以上輸出106。可將通用元件102編程為多個狀態中的一者。通用元件102的狀態確定所述通用元件102將基於給定輸入提供哪一(些)輸出。也就是說，通用元件102的狀態確定可編程元件將基於給定輸入如何起反應。輸入到數據輸入埠 110的數據可提供到所述多個通用元件102以使所述通用元件102對其採取行動。通用元件102的實例可包括下文詳細論述的狀態機元件(SME)及一可配置邏輯塊。在一實例中，SME可設定為給定狀態以當在數據輸入埠 110處接收到給定輸入時提供某一輸出(例如，高或「I」信號)。當在數據輸入埠 110處接收到不同於所述給定輸入的輸入時，所述SME可提供不同輸出(例如，低或「O」信號)。在一實例中，一可配置邏輯塊可經設定以基於在數據輸入埠 110處接收到的輸入來執行布爾邏輯函數(例如，「與(AND) 」、「或(OR) 」、「或非(NOR) 」等)。
[0017]並行機100還可包括編程接口 111以將程序(例如，映像)加載到並行機100上。所述映像可編程(例如，設定)通用元件102的狀態。也就是說，所述映像可配置通用元件102以按某一方式對給定輸入起反應。舉例來說，一通用元件102可經設定，以當在數據輸入埠 Iio處接收到字符「a」時輸出高信號。在一些實例中，並行機100可使用時鐘信號來控制通用元件102的操作的時序。在某些實例中，並行機100可包括用於與通用元件102互動及用於執行專用功能的專用元件112(例如，RAM、邏輯門、計數器、查找表等)。在一些實施例中，在數據輸入埠 110處接收到的數據可包括隨時間過去或一齊接收到的一組固定的數據或隨時間過去而接收到的數據串流。數據可從耦合到並行機100的任何來源接收或通過耦合到並行機100的任何來源產生，所述任何來源例如資料庫、傳感器、網絡等。
[0018]並行機100還包括用於將並行機100的不同元件(例如，通用元件102、數據輸入埠 110、輸出埠 114、編程接口 111及專用元件112)選擇性地耦合在一起的多個可編程開關108。因此，並行機100包含在所述元件間形成的可編程矩陣。在一實例中，可編程開關108可將兩個或兩個以上元件選擇性地耦合到彼此，使得通用元件102的輸入104、數據輸入埠 110、編程接口 111或專用元件112可經由一個或一個以上可編程開關108而耦合到通用元件102的輸出106、輸出埠 114、編程接口 111或專用元件112。因此，所述元件之間的信號的路由可通過設定可編程開關108來控制。儘管圖1說明給定元件與可編程開關108之間的某一數目的導體(例如，電線)，但應理解，在其它實例中，可使用不同數目的導體。而且，儘管圖1說明每一通用元件102個別地耦合到一可編程開關108，但在其它實例中，多個通用元件102可作為一群組(例如，塊802，如圖8中所說明)而耦合到一可編程開關108。在一實例中，數據輸入埠 110、數據輸出埠 114及/或編程接口 111可實施為寄存器，以使得到寄存器的寫入將數據提供到相應元件或從相應元件提供數據。
[0019]在一實例中，單一併行機100實施於物理裝置上，然而，在其它實例中，兩個或兩個以上並行機100可實施於單一物理裝置(例如，物理晶片)上。在一實例中，多個並行機100中的每一者可包括一不同的數據輸入埠 110、一不同的輸出埠 114、一不同的編程接口 111，及一組不同的通用元件102。此外，每一組通用元件102可對其對應輸入數據埠 110處的數據起反應(例如，輸出高或低信號)。舉例來說，對應於第一併行機100的第一組通用元件102可對對應於第一併行機100的第一數據輸入埠 110處的數據起反應。對應於第二並行機100的第二組通用元件102可對對應於第二並行機100的第二數據輸入埠 110起反應。因此，每一併行機100包括一組通用元件102，其中通用元件102的不同集合可對不同輸入數據起反應。類似地，每一併行機100及每一組對應的通用元件102可提供一不同輸出。在一些實例中，來自第一併行機100的輸出埠 114可耦合到第二並行機100的輸入埠 110，使得用於第二並行機100的輸入數據可包括來自第一併行機100的輸出數據。
[0020]在一實例中，用於加載到並行機100上的映像包含用於在並行機100內設定通用元件102的狀態、編程可編程開關108及配置專用元件112的多個信息位。在一實例中，所述映像可加載到並行機100上以編程所述並行機100以基於某些輸入而提供所要輸出。輸出埠 114可基於通用元件102對數據輸入埠 110處的數據所起的反應來提供來自並行機100的輸出。來自輸出埠 114的輸出可包括指示給定模式的匹配的單一位、包含指示與多個模式的匹配及不匹配的多個位的字，及對應於在給定時刻所有或某些通用元件102的狀態的狀態向量。
[0021]並行機100的實例用途包括模式識別(例如，語音識別、圖像識別等)、信號處理、成像、計算機視覺、密碼學及其它。在某些實例中，並行機100可包含有限狀態機(FSM)引擎、現場可編程門陣列(FPGA)及其變體。此外，並行機100可為較大裝置中的一組件，所述較大裝置例如計算機、尋呼機、蜂窩式電話、個人管理器、便攜型音頻播放器、網絡裝置(例如，路由器、防火牆、交換機或其任何組合)、控制電路、照相機等。
[0022]圖2至5說明實施為有限狀態機(FSM)引擎200的另一併行機。在一實例中，FSM引擎200包含有限狀態機的硬體實施方案。因此，FSM引擎200實施對應於FSM中的多個狀態的多個可選擇性地耦合的硬體元件(例如，可編程元件)。類似於FSM中的狀態，硬體元件可分析輸入串流且基於所述輸入串流來激活下遊硬體元件。
[0023]FSM引擎200包括多個可編程元件，包括通用元件及專用元件。通用元件可經編程以實施許多不同功能。這些通用元件包括SME204、205(展示於圖5中)，所述SME204、205階層式組織成行206 (展示於圖3及4中)及塊202 (展示於圖2及3中)。為了在經階層式組織的SME204、205之間路由信號，使用可編程開關的階層，所述階層包括塊間開關203 (展示於圖2及3中)、塊內開關208 (展示於圖3及4中)及行內開關212 (展示於圖4中)。SME204、205可對應於通過FSM引擎200實施的FSM的狀態。如下文所描述，可通過使用可編程開關將SME204、205耦合在一起。因此，可通過編程SME204、205以對應於狀態的功能及通過將SME204、205選擇性地耦合在一起以對應於FSM中的狀態之間的轉變來在FSM引擎200上實施FSM。
[0024]圖2說明實例FSM引擎200的全圖。FSM引擎200包括多個塊202，所述塊可與可編程塊間開關203選擇性地耦合在一起。另外，塊202可選擇性地耦合到用於接收信號(例如，數據)及將數據提供到塊202的輸入塊209 (例如，數據輸入埠)。塊202還可選擇性地耦合到用於將來自塊202的信號提供到外部裝置(例如，另一 FSM引擎200)的輸出塊213 (例如，輸出埠)。FSM引擎200還可包括用於將程序(例如，映像)加載到FSM引擎200上的編程接口 211。所述映像可編程(例如，設定)SME204、205的狀態。也就是說，所述映像可配置SME204、205以按某一方式來對輸入塊209處的給定輸入起反應。舉例來說，SME204可經設定，以當在輸入塊209處接收到字符「a」時輸出高信號。
[0025]在一實例中，輸入塊209、輸出塊213及/或編程接口 211可實施為寄存器，以使得到寄存器的寫入將數據提供到相應元件或從相應元件提供數據。因此，來自存儲於對應於編程接口 211的寄存器中的映像的位可加載於SME204、205上。儘管圖2說明塊202、輸入塊209、輸出塊213及塊間開關203之間的某一數目的導體(例如，電線、跡線)，但應理解，在其它實例中，可使用更少或更多的導體。
[0026]圖3說明塊202的實例。塊202可包括多個行206，所述行可與可編程塊內開關208選擇性地耦合在一起。另外，行206可通過塊間開關203而選擇性地耦合到另一塊202內的另一行206。在一實例中，包括緩衝器201以控制去往/來自塊間開關203的信號的時序。行206包括多個SME204、205，所述多個SME204、205組織成本文中被稱作成對群組(group of two ;G0T)210的元件對。在一實例中，塊202包含十六(16)個行206。
[0027]圖4說明行206的實例。G0T210可通過可編程行內開關212而選擇性地耦合到其它G0T210及行206內的任何其它元件224。G0T210也可通過塊內開關208而耦合到其它行206中的其它G0T210，或通過塊間開關203而耦合到其它塊202中的其它G0T210。在一實例中，G0T210具有第一輸入214及第二輸入216以及一輸出218。第一輸入214 I禹合到G0T210的第一 SME204，且第二輸入214耦合到G0T210的第二 SME204。
[0028]在一實例中，行206包括第一多個行互連導體220及第二多個行互連導體222。在一實例中，G0T210的輸入214、216可耦合到一個或一個以上行互連導體220、222，且輸出218可耦合到一個行互連導體220、222。在一實例中，第一多個行互連導體220可耦合到行206內的每一 G0T210的每一 SME204。第二多個行互連導體222可耦合到行206內的每
一G0T210的一 SME204，但不可耦合到G0T210的另一 SME204。在一實例中，所述第二多個行互連導體222的前一半可耦合到一行206內的SME204的前一半(來自每一 G0T210的一SME204)，且所述第二多個行互連導體222的後一半可耦合到一行206內的SME204的後一半(來自每一 G0T210的另一 SME204)。所述第二多個行互連導體222與SME204、205之間的有限連接性在本文中被稱作「對等性」。
[0029]在一實例中，行206還可包括專用元件224，例如計數器、可編程布爾邏輯元件、現場可編程門陣列(FPGA)、專用集成電路(ASIC)、可編程處理器(例如，微處理器)及其它元件。另外，在一實例中，所述專用元件224在不同行206中為不同的。舉例來說，一塊202中的行206中的四個可包括布爾邏輯作為專用元件224，且一塊202中的其它八個行206可包括計數器作為專用元件224。
[0030]在一實例中，專用元件224包括計數器(本文中也被稱作計數器224)。在一實例中，計數器224包含12位可編程遞減計數器。所述12位可編程計數器224具有計數輸入、復位輸入，及零計數輸出。所述計數輸入在被斷言時使計數器224的值遞減一。所述復位輸入在被斷言時使計數器224加載來自相關聯的寄存器的初始值。對於所述12位計數器224，可加載高達12位的數目作為初始值。當計數器224的值遞減到零(O)時，斷言所述零計數輸出。計數器224還具有至少兩種模式，脈衝及保持。當將計數器224設定為脈衝模式時，在計數器224遞減到零時的第一頻率循環期間斷言零計數輸出，且在接下來的頻率循環處，即使斷言了計數輸入，仍不再斷言零計數輸出。此狀態繼續，直到通過復位輸入被斷言而復位計數器224為止。當將計數器224設定為保持模式時，在計數器224遞減到零時的第一頻率循環期間斷言零計數輸出，且在斷言了計數輸入時保持為經斷言的，直到通過復位輸入被斷言而復位計數器224為止。
[0031]圖5說明G0T210的實例。G0T210包括第一 SME204及第二SME205，其具有輸入214、216且具有其耦合到OR門230及3比I多路復用器242的輸出226、228。所述3比I多路復用器242可經設定以將G0T210的輸出218耦合到第一 SME204、第二 SME205或OR門230。可使用OR門230將輸出226、228耦合在一起以形成G0T210的共同輸出218。在一實例中，如上文所論述，第一 SME204及第二 SME205展現對等性，其中第一 SME204的輸入214可耦合到行互連導體222中的一些，且第二 SME205的輸入216可耦合到其它行互連導體222。在一實例中，可通過設定開關240中的任一者或兩者來使G0T210內的兩個SME204、205級聯及/或循環回到其自身。可通過將SME204、205的輸出226、228耦合到另一 SME204、205的輸入214、216而使SME204、205級聯。可通過將輸出226、228耦合到其自身的輸入214、216而使SME204、205循環回到其自身。因此，第一 SME204的輸出226可不耦合到第一 SME204的輸入214及第二 SME205的輸入216中的任一者，或可耦合到所述輸入中的一者或兩者。
[0032]在一實例中，一狀態機元件204、205包含與檢測線234並聯耦合的多個存儲器單元232，例如動態隨機存取存儲器(DRAM)中所常用的那些存儲器單元。一種此類存儲器單元232包含可設定為一數據狀態的存儲器單元，所述數據狀態例如對應於高或低值(例如，I或O)的狀態。存儲器單元232的輸出耦合到檢測線234，且存儲器單元232的輸入基於數據串流線236上的數據而接收信號。在一實例中，解碼數據串流線236上的輸入以選擇所述存儲器單元232中的一者。選定的存儲器單元232將其所存儲的數據狀態作為輸出提供到檢測線234上。舉例來說，在數據輸入埠 209處接收到的數據可提供到解碼器(未圖示)，且所述解碼器可選擇所述數據串流線236中的一者。在一實例中，所述解碼器可將ACSII字符轉換成256位的I。
[0033]因此，當存儲器單元232設定成高值且數據串流線236上的數據對應於存儲器單元232時，存儲器單元232輸出高信號到檢測線234。當數據串流線236上的數據對應於存儲器單元232且存儲器單元232設定成低值時，存儲器單元232輸出低信號到檢測線234。在檢測線234上的來自存儲器單元232的輸出通過檢測電路238來感測。在一實例中，輸入線214、216上的信號將相應檢測電路238設定成作用中或非作用中狀態。當設定成非作用中狀態時，檢測電路238在相應輸出226、228上輸出低信號，而不管相應檢測線234上的信號。當設定成作用中狀態時，當檢測到來自相應SME204、205的存儲器單元234中的一者的高信號時，檢測電路238在相應輸出線226、228上輸出高信號。當在作用中狀態時，當來自相應SME204、205的所有存儲器單元234的信號為低時，檢測電路238在相應輸出線226、228上輸出低信號。
[0034]在一實例中，SME204、205包括256個存儲器單元232，且每一存儲器單元232耦合到一不同的數據串流線236。因此，SME204、205可經編程以當數據串流線236中的選定的一者或一者以上上面具有高信號時輸出高信號。舉例來說，SME204可使第一存儲器單兀232(例如，位O)設定為高且使所有其它存儲器單元232 (例如，位1-255)設定為低。當相應檢測電路238處於作用中狀態時，當對應於位O的數據串流線236上面具有高信號時，SME204在輸出226上輸出高信號。在其它實例中，SME204可經設定，以當通過將適當的存儲器單元232設定成高值而使多個數據串流線236中的一者上面具有高信號時輸出高信號。
[0035]在一實例中，可通過從相關聯的寄存器讀取位來將存儲器單元232設定成高值或低值。因此，可通過將由編譯程序產生的映像存儲到寄存器中且將寄存器中的位加載到相關聯的存儲器單元232中來編程SME204。在一實例中，由所述編譯程序產生的映像包括高及低(例如，I及O)位的二進位映像。所述映像可通過將SME204、205級聯而編程FSM引擎200以作為FSM操作。舉例來說，可通過將檢測電路238設定成作用中狀態而將第一 SME204設定成作用中狀態。第一 SME204可經設定，以當對應於位O的數據串流線236上面具有高信號時輸出高信號。第二 SME205最初可設定成非作用中狀態，但可經設定以在作用中時當對應於位I的數據串流線236上面具有高信號時輸出高信號。可通過設定第一 SME204的輸出226以耦合到第二 SME205的輸入216來將第一 SME204與第二 SME205級聯。因此，當在對應於位O的數據串流線236上感測到高信號時，第一 SME204在輸出226上輸出高信號且將第二 SME205的檢測電路238設定成作用中狀態。當在對應於位I的數據串流線236上感測到高信號時，第二 SME205在輸出228上輸出高信號以激活另一 SME205或用於來自FSM引擎200的輸出。
[0036]圖6說明供編譯程序用以將原始碼轉換成經配置以編程並行機的映像的方法600的實例。方法600包括:將所述原始碼剖析成語法樹(框602);將所述語法樹轉換成自動機(框604);最佳化所述自動機(框606);將所述自動機轉換成網表(框608);將所述網表放置於硬體上(框610);對所述網表進行布線(框612);及發布所得映像(框614)。
[0037]在一實例中，所述編譯程序包括應用編程接口(API)，所述API允許軟體開發者產生用於在FSM引擎600上實施FSM的映像。所述編譯程序提供用以將所述原始碼中的一組輸入的正規表達式轉換成經配置以編程FSM引擎600的映像的方法。所述編譯程序可通過用於具有馮諾依曼架構的計算機的指令來實施。這些指令可使所述計算機上的處理器實施所述編譯程序的功能。舉例來說，所述指令在通過所述處理器執行時可使所述處理器對可由所述處理器存取的原始碼執行如框602、604、606、608、610、612及614中所描述的動作。具有馮諾依曼架構的實例計算機展示於圖9中且在下文描述。
[0038]在一實例中，原始碼描述用於識別一群符號內的符號的模式的搜索字符串。為了描述所述搜索字符串，所述原始碼可包括多個正規表達式(regex)。正規表達式可為用於描述符號搜索模式的字符串。正規表達式廣泛用在各種計算機領域中，例如程式語言、文字編輯器、網絡安全及其它領域。在一實例中，由編譯程序支持的正規表達式包括用於無結構數據的搜索的搜索準則。無結構數據可包括以下數據，其為自由形式的且無索引施加於數據內的字。字可包括數據內的任何字節組合，可列印及不可列印的。在一實例中，編譯程序可支持用於實施正規表達式的多種不同的原始碼語言，包括Perl(例如，Perl兼容正規表達式(PCRE))、PHP、Java 及.NET 語言。
[0039]返回參看圖6，在框602處，編譯程序可剖析原始碼以形成有關係連接的運算符的布置，其中不同類型的運算符對應於通過原始碼實施的不同功能(例如，通過原始碼中的正規表達式實施的不同功能)。剖析原始碼可產生所述原始碼的一般表示。在一實例中，所述一般表示包含所述原始碼中的呈被稱為語法樹的樹形圖形式的正規表達式的經編碼表示。本文中所描述的實例將所述布置稱為語法樹(也被稱為「抽象語法樹」)。然而，在其它實例中，可使用具體語法樹或其它布置。
[0040]由於如上文所提及，編譯程序可支持多種語言的原始碼，因此，不管是何種語言，剖析將所述原始碼轉換成非語言特定表示，例如語法樹。因此，通過編譯程序進行的其它處理(框604、606、608、610)可從共同輸入結構來起作用，而不管原始碼的語言。
[0041]如上所述，所述語法樹包括有關係連接的多個運算符。語法樹可包括多種不同類型的運算符。也就是說，不同運算符可對應於通過原始碼中的正規表達式實施的不同功能。
[0042]在框604處，將所述語法樹轉換成自動機。自動機(也被稱作有限狀態自動機、有限狀態機(FSM)或簡稱為狀態機)為狀態、狀態之間的轉變及動作的表示，且可分為確定性或非確定性的。確定性自動機在給定時間具有單一執行路徑，而非確定性自動機具有多個同時的執行路徑。所述自動機包含多個狀態。為了將語法樹轉換成自動機，將語法樹中的運算符及運算符之間的關係轉換成狀態及狀態之間的轉變。在一實例中，可部分基於FSM引擎200的硬體來轉換所述自動機。
[0043]在一實例中，用於自動機的輸入符號包括字母、數字0-9及其它可列印字符的符號。在一實例中，所述輸入符號通過字節值O至255(包括在內)來表示。在一實例中，自動機可表示為有向圖，其中所述圖的節點對應於狀態集合。在一實例中，在輸入符號α時從狀態P到狀態q的轉變(即，S (ρ，α))通過從節點P到節點q的有向連接展示。在一實例中，被自動機接受(例如，匹配)的語言為在按順序地輸入到所述自動機中時將達到最終狀態的所有可能字符字符串的集合。被所述自動機接受的語言中的每一字符串沿從開始狀態到一個或一個以上最終狀態的路徑而行。
[0044]在一實例中，在所述自動機中可使用輸入符號範圍外的特殊轉變符號。這些特殊轉變符號可用以(例如)使得能夠使用專用元件224。此外，特殊轉變符號可用以提供在不同於輸入符號的其它者上發生的轉變。舉例來說，一特殊轉變符號可指示當啟用第二狀態及第三狀態時將啟用(例如，轉變到)第一狀態。因此，當激活第二狀態及第三狀態時激活第一狀態，且到所述第一狀態的轉變並非直接取決於輸入符號。顯著地，指示在啟用第二狀態及第三狀態時將啟用第一狀態的特殊轉變符號可用以將(例如)通過布爾邏輯執行的布爾AND函數表示為專用元件224。在一實例中，可使用特殊轉變符號來指示計數器狀態已達到零，且因此轉變成下遊狀態。
[0045]在一實例中，所述自動機包含通用狀態以及專用狀態。所述通用狀態及專用狀態對應於通過目標裝置支持的通用元件及專用元件，編譯程序為所述目標裝置產生機器代碼。不同類型的目標裝置可支持不同類型的通用元件以及一種或一種以上不同類型的專用元件。通用元件通常可用以實施廣泛範圍的功能，而專用元件通常可用以實施更窄範圍的功能。然而，在一實例中，專用元件可在其窄範圍的功能內實現(例如)較大效率。因此，專用元件可用以(例如)減少在目標裝置中實施某些功能所需的機器循環或機器資源。在一些實例中，所述目標裝置僅支持專用元件，其中支持多種不同類型的專用元件。
[0046]在編譯程序產生用於FSM引擎200的機器代碼的實例中，通用狀態可對應於SME204、205，且通用狀態因此在本文中被稱作「SME狀態」。此外，當編譯程序產生用於FSM引擎200的機器代碼時，專用狀態的實例可對應於計數器224且因此在本文中被稱作「計數器狀態」。專用狀態的另一實例可對應於一邏輯元件(例如，可編程邏輯、布爾邏輯)且因此在本文中被稱作「邏輯狀態」。在一實例中，自動機中的SME狀態1:1映射到FSM引擎200中的SME(例如，SME204、205)，不映射到SME的自動機的開始狀態除外。專用元件224可或可不1:1映射到專用狀態。
[0047]在一實例中，可使用例如Glushkov的方法的標準技術中的一者來建構自動機。在一實例中，所述自動機可為無ε的均齊自動機(homogeneous automaton)。均齊自動機為對一般自動機定義的限制。所述限制要求進入一狀態的所有轉變必須發生在同一(些)輸入符號上。均齊自動機滿足以下條件:對於任何兩個狀態，1及％，如果
r e δ (q) Π δ (q2)，則表示 S1 = {a | a e Σ , r e δ (q1； a)} > S2 = {a | a e Σ , r e δ (q2,
a)}。S1為允許qi轉變成r的符號的集合；且S2為允許q2轉變成r的符號的集合。在此，S1=S2,即，如果狀態Q1及狀態q2均轉變成狀態r，則均齊限制為轉變必須發生在同一(些)符號上。
[0048]圖7A及7B說明從語法樹產生的實例自動機。圖7A說明均齊自動機700，且圖7B說明非均齊自動機702。
[0049]均齊自動機700在開始狀態704處開始，開始狀態704在輸入符號「a」時轉變成狀態706。在輸入符號「b」時狀態706轉變成狀態708，且在輸入符號「b」時，狀態708轉變成狀態710。在輸入符號「c」時，狀態710轉變成狀態712。狀態712在輸入符號「b」時轉變成狀態710，且在輸入符號「d」時轉變成狀態714。狀態714為最終狀態且通過雙圓來識別為最終狀態。在一實例中，最終狀態可為重要的，因為最終狀態的激活指示對應於所述自動機的正規表達式的匹配。自動機700為均齊自動機，因為給定狀態的所有內轉變(例如，到狀態的轉變)發生在同一(些)符號上。顯著地，狀態710具有兩個內轉變(從狀態708及狀態712)，且所述兩個內轉變均發生在同一符號「b」上。
[0050]非均齊自動機702包括與均齊自動機700相同的狀態704、706、708、710、712及714，然而，狀態712在輸入符號「e」時轉變成狀態710。因此，自動機702為非均齊的，因為狀態710在兩個不同符號時具有內轉變；符號「b」時從狀態708且符號「e」時從狀態712。
[0051]在框606處，在建構了自動機之後，最佳化所述自動機以尤其減少其複雜性及大小。可通過組合冗餘狀態來最佳化所述自動機。
[0052]在框608處，將所述自動機轉換成網表。將所述自動機轉換成網表將所述自動機的狀態映射到FSM引擎200的硬體元件(例如，SME204、205、G0T210、專用元件224)的實例，且確定所述實例之間的連接。在一實例中，所述網表包含多個實例，每一實例對應於(例如，表示)FSM引擎200的一硬體元件。每一實例可具有用於連接到另一實例的一個或一個以上連接點(本文中也被稱作「埠」)。所述網表還包含所述實例的埠之間的多個連接，所述多個連接對應於(例如，表示)用以耦合對應於所述實例的硬體元件的導體。在一實例中，所述網表包含對應於不同類型的硬體元件的不同類型的實例。舉例來說，所述網表可包括對應於通用硬體元件的通用實例及對應於專用硬體元件的專用實例。作為一實例，通用狀態可轉換成通用實例，且專用狀態可轉換成專用實例。在一實例中，所述通用實例可包括用於一 SME204、205的一 SME實例及用於包含一群SME的硬體元件的一 SME群組實例。在一實例中，所述SME群組實例包括對應於G0T210的GOT實例；然而，在其它實例中，所述SME群組實例可對應於包含一群三個或三個以上SME的硬體元件。專用實例可包括用於計數器224的計數器實例及用於邏輯元件224的邏輯實例。由於G0T210包括兩個SME204、205，因此GOT實例含有兩個SME實例。
[0053]為產生網表，將自動機中的狀態轉換成網表中的實例，除了開始狀態不具有對應實例之外。將SME狀態轉換成GOT實例，且將計數器狀態轉換成計數器實例。另外，針對從對應於第一實例的狀態到對應於第二實例的狀態的轉變產生從第一實例到第二實例的對應連接。由於FSM引擎200中的SME204、205分組到被稱作G0T210的對中，因此編譯程序可將SME狀態分組到GOT實例中的對中。歸因於G0T210的物理設計，並非所有SME實例可一起成對以形成G0T210。因此，編譯程序確定可將哪些SME狀態一起映射在G0T210中，且接著基於所述確定將SME狀態成對到GOT實例中。
[0054]如圖5中所示，G0T210具有對SME204、205的輸出限制。確切地說，G0T210具有由兩個SME204、205共享的單一輸出218。因此，G0T210中的每一 SME204、205不可獨立地驅動輸出218。此輸出限制限制了在GOT實例中哪些SME狀態可一起成對。顯著地，驅動(例如，轉變到、激活)外部SME狀態(例如，對應於GOT實例外的SME的SME狀態)的不同集合的兩個SME狀態在一 GOT實例中不可一起成對。然而，此限制不限制所述兩個SME狀態是否驅動彼此或自循環，因為G0T210可在內部通過開關240提供此功能性。儘管將FSM引擎200描述為具有對應於SME204、205的某一物理設計，但在其它實例中，SME204、205可具有其它物理設計。舉例來說，SME204、205可一起分組到SME204、205的三個或三個以上集合中。另外，在一些實例中，可存在對到SME204、205的輸入214、216的限制，對來自SME204、205的輸出226、228可具有或不具有限制。
[0055]然而，在任一種情況下，編譯程序基於FSM引擎200的物理設計來確定哪些SME狀態可一起分組。因此，對於GOT實例，編譯程序基於G0T210中的SME204、205的輸出限制來確定哪些SME狀態可一起成對。在一實例中，存在五種情形，其中兩個SME狀態可基於G0T210的物理設計而一起成對以形成G0T210。
[0056]在第一 SME狀態及第二 SME狀態可在G0T210中一起成對時的第一種情形出現在第一 SME狀態或第二 SME狀態均非最終狀態時，及出現在第一 SME狀態及第二 SME狀態中的一者不驅動不同於第一 SME狀態或第二 SME狀態的任何狀態時。作為一實例，當第一狀態轉變成第二狀態時，認為所述第一狀態驅動所述第二狀態。當此第一種情形出現時，至多第一SME狀態及第二 SME狀態中的一者驅動一(些)外部狀態。因此，第一 SME狀態及第二 SME狀態可一起成對，而不受G0T210的輸出限制影響。然而，歸因於G0T210在內部將SME204、205耦合到彼此的能力，允許第一 SME狀態及第二 SME狀態驅動彼此及自循環以驅動自身。在自動機項中，當Q1或均非最終狀態，且δ (q^-1q^qal為空時，或當δ (q^-jq^qj為空時，第一 SME狀態(對應於狀態qi)及第二 SME狀態(對應於狀態q2)可一起成對。
[0057]在第一 SME狀態及第二 SME狀態可在G0T210中一起成對時的第二種情形出現在第一或第二 SME狀態均非自動機中的最終狀態時，及出現在第一 SME狀態及第二 SME狀態驅動相同的外部狀態時。如本文中所使用，外部狀態對應於GOT實例外部的狀態，例如，不管GOT實例中的第一 SME狀態及第二 SME狀態是否驅動彼此或自循環。再次，G0T210的輸出限制不影響第一 SME狀態及第二 SME狀態，因為第一 SME狀態及第二 SME狀態驅動相同的外部狀態。而且，歸因於G0T210在內部將SME204、205耦合到彼此的能力，對驅動相同狀態的限制不包括第一狀態及第二狀態是否驅動彼此或自循環。使用自動機項，當Q1或q2均非最終狀態，且S (qi)-{qi，q2} = δ (q2)-{qi，q2}時，第一 SME狀態(對應於狀態qj及第
二SME狀態(對應於狀態q2)可一起成對。
[0058]第一 SME狀態及第二 SME狀態可在G0T210中一起成對的第三及第四種情形出現在第一 SME狀態及第二 SME狀態中的一者為最終狀態且第一 SME狀態及第二 SME狀態中的另一者並不驅動任一外部狀態時。也就是說，當Q1為最終狀態且δ (q2)-{qi, q2}為空時，或當q2對應於最終狀態且S (Q1)-1q1, q2}為空時，第一 SME狀態(對應於狀態qj及第二SME狀態(對應於狀態q2)可一起成對。由於最終狀態輸出與正規表達式匹配的指示，因此對應於最終狀態的SME狀態應能夠獨立使用G0T210的輸出218以便指示所述匹配。因此，不允許G0T210中的另一 SME狀態使用輸出218。
[0059]在第一 SME狀態及第二 SME狀態可在G0T210中一起成對時的第五種情形出現在第一 SME狀態及第二 SME狀態均對應於一自動機中的最終狀態且第一 SME狀態及第二 SME狀態均驅動相同的外部狀態時。使用自動機項，當Q1及92均為最終狀態，且δ (q^-tq^qj=δ (q2)-{qi，q2}時，第一狀態(對應於狀態qj及第二 SME狀態(對應於狀態q2)可一起成對。
[0060]一旦編譯程序確定一個或一個以上SME狀態是否可一起成對，編譯程序便將所述SME狀態成對為GOT實例。在一實例中，編譯程序按SME狀態被確定為能夠成對以形成GOT實例的次序來將SME狀態成對為GOT實例。也就是說，一旦兩個特定SME狀態被確定為能夠一起成對，此兩個SME狀態便可成對為一 GOT實例。一旦兩個SME狀態已成對以形成GOT實例，這些成對的SME狀態不可用於與其它SME狀態成對。此過程可繼續，直到不再有任何SME狀態留待成對為止。
[0061]在一實例中，編譯程序使用圖論來確定哪些SME—起成對為GOT實例。由於僅某些SME可一起成對，因此一些SME成對可導致其它SME必須在其自身的GOT實例中實施，以致GOT實例中的其它SME位置 未用且因此被浪費。可使用圖論來通過減少網表的GOT實例中的未用SME實例的數目來最佳化G0T210中的SME利用(例如，減少未用SME的數目)。為了使用圖論，編譯程序首先根據上文所論述的FSM引擎200的物理設計來確定SME狀態之間的所有可能成對。編譯程序接著產生一圖，其中所述圖的頂點對應於SME狀態，且所述圖的邊對應於SME狀態的可能成對。也就是說，如果確定兩個SME狀態能夠在GOT實例中一起成對，則用一條邊連接兩個對應的頂點。因此，所述圖含有SME狀態的所有可能成對。
[0062]編譯程序可接著找出所述圖的匹配頂點以識別哪些SME狀態在G0T210中一起成對。也就是說，編譯程序識別邊(且因此識別頂點對)，使得所述圖的匹配頂點之間的兩條邊不會共享一個共同頂點。在一實例中，編譯程序可找出所述圖的最大匹配。在另一實例中，編譯程序可找出所述圖的最大匹配。最大匹配為含有最大的可能數目的邊的匹配。可存在許多最大匹配。可以多項式時間來解決找出一般圖的最大匹配的問題。
[0063]一旦已識別了所有匹配頂點(例如，作為最大匹配)，則將對應於匹配頂點的每一對SME狀態映射到一 GOT實例。將對應於未匹配頂點的SME狀態映射到其自身的GOT實例。也就是說，將對應於未匹配頂點的SME狀態映射到GOT實例中的SME位置中的一者中，且GOT實例中的其它SME位置未用。因此，假定網表N及其匹配頂點M的對應集合，所使用的N的GOT實例的數目等於I Q1-1-1MI，其中Q為自動機的狀態集合，且「-1 」是因為在此實例中自動機的開始狀態並不對應於SME狀態。[0064]在一實例中，網表N是使用最少數目的GOT實例由G的最大匹配M來建構。此可通過以下事例證明:如果存在使用更少數目的GOT實例的另一網表N'，則將所述對應匹配表示為M'。由於N'的got實例的數目等於Iq1-1-1m' I，因此我們得到|m| < |m' I。此與M為最大匹配的事實衝突。因此，網表N使用最少數目的GOT實例。
[0065]一旦SME狀態成對為GOT實例，便根據自動機中的狀態之間的轉變來連接GOT實例、計數器實例及邏輯實例。由於每一 G0T210具有單一輸出，因此網表中的每一 GOT實例具有單一輸出埠以供連接到其它實例。因此，如果第一 GOT實例中的任一 SME狀態驅動第二 GOT實例中的一 SME狀態，則第一 GOT實例的輸出埠耦合到第二 GOT實例的輸入。
[0066]圖8A及8B說明從圖7A的均齊自動機700產生的實例網表800、802。SME實例806、808、810、812及814對應於自動機700中的狀態706、708、710、712及714。如上文所論述，所述自動機的開始狀態704不對應於一實例。
[0067]網表800為非最佳網表的一實例。網表800使用四個GOT實例816，同時留下三個SME實例818未用。然而，網表802為使用圖論識別最大匹配而產生的最佳網表的實例。網表802使用三個GOT實例816且具有單一未用SME實例818。在網表802中，可通過GOT實例內部的連接(例如，經由開關240)將實例810連接到實例812。
[0068]在框610處,一旦已產生網表,便放置所述網表以針對所述網表的每一實例選擇所述目標裝置的特定硬體元件(例如，SME204、205、其它元件224)。根據本發明的一實施例，放置基於針對硬體元件的一般輸入及輸出約束來選擇硬體元件。
[0069]在框612處，對經全局放置的網表進行布線以確定可編程開關(例如，塊間開關203、塊內開關208及行內開關212)的設定以便將選定硬體元件耦合在一起以實現網表所描述的連接。在一實例中，所述可編程開關的設定通過確定FSM引擎200的將用以連接選定的硬體元件的特定導體及所述可編程開關的設定來確定。布線可調整在放置期間針對網表實例中的一些選擇的特定硬體元件，例如以便耦合硬體元件，給定FSM引擎200上的導體及/或開關的物理設計。
[0070]一旦對網表進行放置及布線，便可將所放置及經布線的網錶轉換成用於編程FSM引擎200的多個位。所述多個位在本文中被稱作映像。
[0071]在框614處，通過編譯程序發布映像。所述映像包含用於編程FSM引擎200的特定硬體元件及/或可編程開關的多個位。在所述映像包含多個位(例如，O及I)的實施例中，所述映像可被稱作二進位映像。所述位可加載到FSM引擎200上以編程SME204、205、專用元件224及可編程開關的狀態，以使得經編程的FSM引擎200實施具有通過原始碼描述的功能性的FSM。放置(框610)及布線(框612)可將在FSM引擎200中的特定位置處的特定硬體元件映像到自動機中的特定狀態。因此，所述映像中的位可編程所述特定硬體元件及/或可編程開關以實施所要功能。在一實例中，可通過將機器代碼存儲到計算機可讀媒體來發布所述映像。在另一實例中，可通過在顯示裝置上顯示所述映像來發布映像。在又一實例中，可通過將所述映像發送到另一裝置(例如，用於將所述映像加載到FSM引擎200上的編程裝置)來發布映像。在再一實例中，可通過將所述映像加載到並行機(例如，FSM引擎200)上來發布映像。
[0072]在一實例中，可通過將來自映像的位值直接加載到SME204、205及其它硬體元件224或通過將映像加載到一個或一個以上寄存器中且接著將來自寄存器的位值寫入到SME204、205及其它硬體元件224來將映像加載到FSM引擎200上。在一實例中，可編程開關(例如，塊間開關203、塊內開關208及行內開關212)的狀態。在一實例中，FSM引擎200的硬體元件(例如，SME204、205、其它元件224、可編程開關203、208、212)經存儲器映射，以使得編程裝置及/或計算機可通過將映像寫入到一個或一個以上存儲器地址而將映像加載到FSM引擎200上。
[0073]本文中所描述的方法實例可至少部分為機器或計算機實施的。一些實例可包括編碼有指令的計算機可讀媒體或機器可讀媒體，所述指令可操作以配置電子裝置以執行如上述實例中所描述的方法。這些方法的實施方案可包括代碼，例如微碼、彙編語言代碼、高級語言代碼或其類似者。此類代碼可包括用於執行各種方法的計算機可讀指令。代碼可形成電腦程式產品的部分。另外，代碼在執行期間或在其它時間時可有形地存儲於一個或一個以上易失性或非易失性計算機可讀媒體上。這些計算機可讀媒體可包括(但不限於)硬碟、可裝卸磁碟、可裝卸光碟(例如，壓縮光碟及數字視頻光碟)、磁帶、存儲器卡或存儲器棒、隨機存取存儲器(RAM)、只讀存儲器(ROM)及其類似者。
[0074]圖9大體上說明具有馮諾依曼架構的計算機900的實例。在閱讀及理解了本發明的內容之後，一般所屬領域的技術人員將理解，在基於計算機的系統中可從計算機可讀媒體加載軟體程序以使其執行以軟體程序定義的功能的方式。一般所屬領域的技術人員將進一步理解，可使用各種程式語言來產生經設計以實施並執行本文所揭示的方法的一個或一個以上軟體程序。可使用面向對象的語言(例如，Java、C++或一種或一種以上其它語言)以面向對象的格式來結構化所述程序。或者，可使用程序語言(例如，彙編語言、C等)以面向程序的格式來結構化所述程序。軟體組件可使用一般所屬領域的技術人員所眾所周知的許多方案中的任一者來通信，例如應用編程接口或過程間通信技術，包括遠程過程調用或其它。各個實施例的教示不限於任何特定程式語言或環境。
[0075]因此，可實現其它實施例。舉例來說，一製造對象(例如，計算機、存儲器系統、磁碟或光碟、某其它存儲裝置，或任何類型的電子裝置或系統)可包括一個或一個以上處理器902，所述一個或一個以上處理器902耦合到上面存儲有指令924 (例如，電腦程式指令)的計算機可讀媒體922，例如存儲器(例如，可裝卸存儲媒體，以及包括電、光或電磁導體的任何存儲器)，所述指令在通過所述一個或一個以上處理器902執行時導致執行相對於上述方法所描述的動作中的任一者。
[0076]計算機900可採取具有處理器902的計算機系統的形式，所述處理器908直接及/或使用總線908來耦合到許多元件。這些元件可包括主存儲器904、靜態或非易失性存儲器906及大容量存儲裝置916。耦合到處理器902的其它元件可包括輸出裝置910 (例如，視頻顯示器)、輸入裝置912 (例如，鍵盤)及光標控制裝置914 (例如，滑鼠)。用以將處理器902及其它元件耦合到網絡926的網絡接口裝置920還可耦合到總線908。指令924可利用許多眾所周知的傳送協議(例如，HTTP)中的任一者經由網絡接口裝置920跨越網絡926來進一步傳輸或接收。耦合到總線908的這些元件中的任一者可不存在，單獨地存在，或以複數形式存在，此取決於待實現的特定實施例。
[0077]在一實例中，處理器902、存儲器904、906或存儲裝置916中的一者或一者以上可各自包括指令924，所述指令924在執行時可使計算機900執行本文所描述的方法中的任何一者或一者以上。在替代實施例中，計算機900作為單獨裝置操作或可連接(例如，網絡連接)到其它裝置。在網絡環境中，計算機900可以伺服器-客戶端網絡環境中的伺服器或客戶端裝置的能力來操作，或操作為對等(或分布式)網絡環境中的對等裝置。計算機900可包括個人計算機(PC)、平板PC、機頂盒(STB)、個人數字助理(PDA)、蜂窩式電話、web器具、網絡路由器、交換機或橋接器，或能夠執行一組指令(順序的或其它)的任何裝置，所述組指令指定將由所述裝置採取的行動。另外，雖然僅說明了單一計算機900，但術語「計算機」還應被視為包括個別地或共同地執行一組(或多組)指令以執行本文中所論述的方法中的任何一者或一者以上的裝置的任何集合。
[0078]計算機900還可包括用於使用一個或一個以上通信協議(例如，通用串行總線(USB)、IEEE1394等)與外圍裝置通信的輸出控制器928。輸出控制器928可(例如)將映像提供到通信地耦合到計算機900的編程裝置930。編程裝置930可經配置以編程並行機(例如，並行機100、FSM引擎200)。在其它實例中，編程裝置930可與計算機900集成且耦合到總線908或可經由網絡接口裝置920或另一裝置與計算機900通信。
[0079]雖然計算機可讀媒體924展示為單一媒體，但術語「計算機可讀媒體」應被視為包括存儲所述一組或一組以上指令924的單一媒體或多個媒體(例如，集中式或分布式資料庫，或相關聯的高速緩存及伺服器，及或各種存儲媒體，例如處理器902寄存器、存儲器904,906及存儲裝置916)。術語「計算機可讀媒體」還應被視為包括以下任何媒體，其能夠存儲、編碼或載運供計算機執行的一組指令且使所述計算機執行本發明的方法中的任何一者或一者以上，或能夠存儲、編碼或載運供此組指令利用或與此組指令相關聯的數據結構。術語「計算機可讀媒體」因此應被視為包括(但不限於)有形媒體，例如固態存儲器、光媒體及磁性媒體。
[0080]提供摘要以遵照需要摘要的37C.F.R.章節1.72 (b)，此將允許讀者確定技術揭示內容的性質及要旨。在理解到摘要將不用以限制或解釋權利要求書的範疇或涵義的情況下提交摘要。以下權利要求書藉此併入詳細描述中，其中每一權利要求依賴於其自身而作為一單獨實施例。
[0081]實例實施例
[0082]實例I包括一種計算機實施方法，其用於從原始碼產生經配置以編程並行機的映像。所述方法包括:將原始碼轉換成包含多個互連狀態的自動機；將所述自動機轉換成網表，所述網表包含對應於所述自動機的狀態的實例，其中所述實例對應於所述並行機的硬體元件，其中將所述自動機轉換成網表包括基於所述並行機的物理設計來對狀態一起分組；及將所述網錶轉換成所述映像。
[0083]實例2包括一種計算機可讀媒體，其包括指令，所述指令在由所述計算機執行時使所述計算機執行操作。所述操作包括:將原始碼轉換成包含多個互連狀態的自動機；將所述自動機轉換成網表，所述網表包含對應於所述自動機的狀態的實例，其中所述實例對應於所述並行機的硬體元件，其中將所述自動機轉換成網表包括基於所述並行機的物理設計來對狀態一起分組；及將所述網錶轉換成所述映像。
[0084]實例3包括一種計算機，其包括:存儲器，其上面存儲有軟體；及處理器，其通信地耦合到所述存儲器。其中所述軟體在由所述處理器執行時使所述處理器:將原始碼轉換成包含多個互連狀態的自動機；將所述自動機轉換成網表，所述網表包含對應於所述自動機的狀態的實例，其中所述實例對應於所述並行機的硬體元件，其中所述實例包括多個第一實例及含有兩個或兩個以上第一實例的一群組實例，其中將所述自動機轉換成網表包括基於許多未用的第一實例來將狀態一起分組在一群組實例中；及將所述網錶轉換成所述映像。
[0085]實例4包括一種系統，其包括計算機，所述計算機經配置以:將原始碼轉換成包含多個互連狀態的自動機；將所述自動機轉換成網表，所述網表包含對應於所述自動機的狀態的實例，其中所述實例對應於所述並行機的硬體元件，其中所述實例包括多個第一實例及含有兩個或兩個以上第一實例的一群組實例，其中將所述自動機轉換成網表包括基於許多未用的第一實例來將狀態一起分組在一群組實例中；及將所述網錶轉換成所述映像。所述系統還包括經配置以將所述映像加載到並行機上的裝置。
[0086]在實例5中，實例I至4中任一者的主題可任選地包括，其中所述實例包括對應於狀態機元件(SME)硬體元件的SME實例及對應於包含一群SME的硬體元件的SME群組實例，且其中分組包括將狀態分組到SME群組實例中。
[0087]在實例6中，實例I至5中任一者的主題可任選地包括，其中所述物理設計包括包含一群SME的所述硬體元件的物理設計。
[0088]在實例7中，實例I至6中任一者的主題可任選地包括，其中所述物理設計包括對包含一群SME的所述硬體元件中的所述SME的輸入或輸出限制中的一者。
[0089]在實例8中，實例I至7中任一者的主題可任選地包括,其中所述物理設計包括包含一群SME的所述硬體元件中的所述SME共享輸出的限制。
[0090]在實例9中，實例I至8中任一者的主題可任選地包括，其中SME群組實例包括含有兩個SME實例的成對群組(GOT)實例，且其中所述物理設計包括每一 GOT中的所述SME耦合到共同輸出。
[0091]在實例10中，實例I至9中任一者的主題可任選地包括，其中將所述自動機轉換成網表包含:確定所述狀態中的哪些可一起分組在GOT實例中；及基於所述確定來使所述狀態成對。
[0092]在實例11中，實例I至10中任一者的主題可任選地包括，其中當第一狀態或第二狀態均非所述自動機的最終狀態，且所述第一狀態及所述第二狀態中的一者不驅動不同於所述第一狀態或所述第二狀態的任何狀態時，所述第一狀態及所述第二狀態可在GOT實例中一起成對。
[0093]在實例12中，實例I至11中任一者的主題可任選地包括，其中當第一狀態或第二狀態均非所述自動機的最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態時，所述第一狀態及所述第二狀態可在GOT實例中一起成對。
[0094]在實例13中，實例I至12中任一者的主題可任選地包括，其中當第一狀態及第二狀態中的一者為所述自動機的最終狀態，且所述第一狀態及所述第二狀態中的另一者不驅動任何外部狀態時，所述第一狀態及所述第二狀態可在GOT實例中一起成對。
[0095]在實例14中，實例I至13中任一者的主題可任選地包括，其中當第一狀態及第二狀態均為所述自動機的最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態時，所述第一狀態及所述第二狀態可在GOT實例中一起成對。
[0096]在實例15中，實例I至14中任一者的主題可任選地包括，其中確定所述狀態中的哪些可一起分組在GOT實例中包含使用圖論來確定所述狀態中的哪些可一起分組在GOT實例中。
[0097]在實例16中，實例I至15中任一者的主題可任選地包括，其中使用圖論來確定所述狀態中的哪些可一起分組在GOT實例中包含使用圖論識別最大匹配來確定所述狀態中的哪些可一起分組在GOT實例中。
[0098]在實例17中，實例I至16中任一者的主題可任選地包括發布所述映像。
[0099]在實例18中，實例I至17中任一者的主題可任選地包括，其中所述實例包含通用實例及專用實例，其中所述通用實例對應於所述自動機的通用狀態，且所述專用實例對應於所述自動機的專用狀態。
[0100]在實例19中，實例I至18中任一者的主題可任選地包括，其中對應於所述通用實例的所述硬體元件包括狀態機元件(SME)及成對群組(G0T)，且其中對應於所述專用實例的所述硬體元件包括計數器及邏輯元件。
[0101]在實例20中，實例I至19中任一者的主題可任選地包括，其中所述自動機為均齊自動機。
[0102]在實例21中，實例I至20中任一者的主題可任選地包括，其中將所述自動機轉換成網表包含將所述自動機的所述狀態中的每一者映像到對應於所述硬體元件的實例及確定所述實例之間的連接性。
[0103]在實例22中，實例I至21中任一者的主題可任選地包括，其中所述網表進一步包含表示所述硬體元件之間的導體的所述實例之間的多個連接。
[0104]在實例23中，實例I至22中任一者的主題可任選地包括，其中將所述自動機轉換成網表包含將所述自動機轉換成包含實例的網表，所述實例對應於所述自動機的除了開始狀態之外的狀態。
[0105]在實例24中，實例I至23中任一者的主題可任選地包括確定對應於所述網表的實例的所述硬體元件在所述並行機中的位置。
[0106]在實例25中，實例I至24中任一者的主題可任選地包括，其中對狀態一起分組包括基於包含一群通用元件的硬體元件的物理設計來對狀態一起分組。
[0107]在實例26中，實例I至25中任一者的主題可任選地包括確定將使用所述並行機的哪些導體來連接所述硬體元件；及確定所述並行機的可編程開關的設定，其中所述可編程開關經配置以選擇性地將所述硬體元件耦合在一起。
[0108]在實例27中，實例I至26中任一者的主題可任選地包括，其中所述群組實例包括成對群組(GOT)實例，且其中分組狀態包括根據成對的狀態驅動哪些狀態來使狀態成對。
[0109]在實例28中，實例I至27中任一者的主題可任選地包括，其中基於許多未用的第一實例將狀態分組在群組實例中包括:基於以下條件確定第一狀態與第二狀態是否可成對:所述第一狀態或所述第二狀態均非所述自動機中的最終狀態，且所述第一狀態及所述第二狀態中的一者不驅動不同於所述第一狀態或所述第二狀態的任何狀態；所述第一狀態或所述第二狀態均非所述自動機中的最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態；所述第一狀態或所述第二狀態中的任一者為最終狀態，且並非最終狀態的所述第一狀態或所述第二狀態不驅動除了所述第一狀態或所述第二狀態的外的任何狀態；及所述第一狀態及所述第二狀態均為最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態。[0110]在實例29中，實例I至28中任一者的主題可任選地包括，其中將所述自動機轉換成網表包括:將所述狀態模型化為一圖，其中所述圖的頂點對應於狀態，且所述圖的邊對應於所述狀態的可能成對；確定所述圖的匹配頂點；及使對應於所述匹配頂點的狀態成對。
[0111]在實例30中，實例I至29中任一者的主題可任選地包括，其中將所述自動機轉換成網表包括:確定所述圖的最大匹配。
[0112]在實例31中，實例I至30中任一者的主題可任選地包括，其中將所述自動機轉換成網表包括:使對應於匹配頂點的每一組狀態成對；及將對應於未匹配頂點的每一狀態映像到GOT實例，其中所述GOT實例中的SME實例將為未用的。
[0113]在實例32中，實例I至31中任一者的主題可任選地包括，其中對狀態一起分組包括:根據成對的狀態驅動哪些狀態來使狀態成對。
[0114]在實例33中，實例I至32中任一者的主題可任選地包括，其中基於許多未用的第一實例將狀態一起分組在群組實例中包括:基於以下條件確定第一狀態與第二狀態是否可成對:所述第一狀態或所述第二狀態均非所述自動機中的最終狀態，且所述第一狀態及所述第二狀態中的一者不驅動不同於所述第一狀態或所述第二狀態的任何狀態；所述第一狀態或所述第二狀態均非所述自動機中的最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態；所述第一狀態或所述第二狀態中的任一者為最終狀態，且並非最終狀態的所述第一狀態或所述第二狀態不驅動除了所述第一狀態或所述第二狀態之外的任何狀態；及所述第一狀態及所述第二狀態均為最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態。
[0115]在實例34中，實例I至33中任一者的主題可任選地包括，其中基於許多未用的第一實例將狀態一起分組在群組實例中包括:將所述狀態模型化為一圖，其中所述圖的頂點對應於狀態，且所述圖的邊對應於所述狀態的可能成對；確定所述圖的匹配頂點；及使對應於所述匹配頂點的狀態成對。
[0116]在實例35中，實例I至34中任一者的主題可任選地包括，其中基於許多未用的第一實例將狀態一起分組在群組實例中:確定所述圖的最大匹配。
[0117]在實例36中，實例I至35中任一者的主題可任選地包括，其中基於許多未用的第一實例將狀態一起分組在群組實例中包括:使對應於匹配頂點的每一組狀態成對；及將對應於未匹配頂點的每一狀態映射到一 GOT實例，其中所述GOT實例中的SME實例將為未用的。
[0118]在實例37中，實例I至36中任一者的主題可任選地包括，其中裝置經配置以將每一對狀態實施為所述並行機中的兩個硬體元件的一群組。
[0119]實例38包括通過用實例I至37中任一者的過程產生的映像來編程的並行機。
【權利要求】
1.一種計算機實施的方法，其用於從原始碼產生經配置以編程並行機的映像，所述方法包含: 將原始碼轉換成包含多個互連狀態的自動機； 將所述自動機轉換成網表，所述網表包含對應於所述自動機的狀態的實例，其中所述實例對應於所述並行機的硬體元件，其中將所述自動機轉換成網表包括基於所述並行機的物理設計來對狀態一起分組；及 將所述網錶轉換成所述映像。
2.根據權利要求1所述的方法，其中所述實例包括對應於狀態機元件SME硬體元件的SME實例及對應於包含一群SME的硬體元件的SME群組實例，且其中分組包括將狀態分組到SME群組實例中。
3.根據權利要求2所述的方法，其中所述物理設計包括包含一群SME的所述硬體元件的物理設計。
4.根據權利要求3所述的方法，其中所述物理設計包括對包含一群SME的所述硬體元件中的所述SME的輸入或輸出限制中的一者。
5.根據權利要求4所述的方法，其中所述物理設計包括包含一群SME的所述硬體元件中的所述SME共享輸出的限制。
6.根據權利要求2所述的方法，其中SME群組實例包括含有兩個SME實例的成對群組GOT實例，且其中所述物理設計包括每一 GOT中的所述SME耦合到共同輸出。
7.根據權利要求6所述的方法，其中將所述自動機轉換成網表包含:` 確定所述狀態中的哪些可一起分組在GOT實例中；及 基於所述確定使所述狀態成對。
8.根據權利要求7所述的方法，其中當第一狀態或第二狀態均非所述自動機的最終狀態，且所述第一狀態及所述第二狀態中的一者不驅動不同於所述第一狀態或所述第二狀態的任何狀態時，所述第一狀態及所述第二狀態可在GOT實例中一起成對。
9.根據權利要求7所述的方法，其中當第一狀態或第二狀態均非所述自動機的最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態時，所述第一狀態及所述第二狀態可在GOT實例中一起成對。
10.根據權利要求7所述的方法，其中當第一狀態及第二狀態中的一者為所述自動機的最終狀態，且所述第一狀態及所述第二狀態中的另一者不驅動任何外部狀態時，所述第一狀態及所述第二狀態可在GOT實例中一起成對。
11.根據權利要求7所述的方法，其中當第一狀態及第二狀態均為所述自動機的最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態時，所述第一狀態及所述第二狀態可在GOT實例中一起成對。
12.根據權利要求7所述的方法，其中確定所述狀態中的哪些可一起分組在GOT實例中包含:使用圖論來確定所述狀態中的哪些可一起分組在GOT實例中。
13.根據權利要求12所述的方法，其中使用圖論來確定所述狀態中的哪些可一起分組在GOT實例中包含:使用圖論識別最大匹配來確定所述狀態中的哪些可一起分組在GOT實例中。
14.根據權利要求1所述的方法，其進一步包含:發布所述映像。
15.根據權利要求1所述的方法，其中所述實例包含通用實例及專用實例，其中所述通用實例對應於所述自動機的通用狀態，且所述專用實例對應於所述自動機的專用狀態。
16.根據權利要求15所述的方法，其中對應於所述通用實例的所述硬體元件包括狀態機元件SME及成對群組GOT，且其中對應於所述專用實例的所述硬體元件包括計數器及邏輯元件。
17.一種計算機可讀媒體，其包括指令，所述指令在由所述計算機執行時使所述計算機執行包含以下各者的操作: 將原始碼轉換成包含多個互連狀態的自動機； 將所述自動機轉換成網表，所述網表包含對應於所述自動機的狀態的實例，其中所述實例對應於並行機的硬體元件，其中將所述自動機轉換成網表包括基於所述並行機的物理設計來對狀態一起分組 '及 將所述網錶轉換成所述映像。
18.根據權利要求17所述的計算機可讀媒體，其中所述自動機為均齊自動機。
19.根據權利要求17所述的計算機可讀媒體，其中將所述自動機轉換成網表包含:將所述自動機的所述狀態中的每一者映射到對應於所述硬體元件的實例及確定所述實例之間的連接性。
20.根據權利要求17所述的計算機可讀媒體，其中所述網表進一步包含所述實例之間的表示所述硬體元件之間的導體的多個連接。
21.根據權利要求17 所述的計算機可讀媒體，其中將所述自動機轉換成網表包含:將所述自動機轉換成包含實例的網表，所述實例對應於所述自動機的除了開始狀態之外的狀態。
22.根據權利要求17所述的計算機可讀媒體，其中所述指令使所述計算機執行包含以下各者的操作: 確定對應於所述網表的所述實例的所述硬體元件在所述並行機中的位置。
23.根據權利要求22所述的計算機可讀媒體，其中對狀態一起分組包括:基於包含一群通用元件的硬體元件的物理設計來對狀態一起分組。
24.根據權利要求22所述的計算機可讀媒體，其中所述指令使所述計算機執行包含以下各者的操作: 確定將使用所述並行機的哪些導體來連接所述硬體元件；及 確定所述並行機的可編程開關的設定，其中所述可編程開關經配置以選擇性地將所述硬體元件稱合在一起。
25.一種計算機，其包含: 存儲器，其上面存儲有軟體 '及 處理器，其通信地耦合到所述存儲器，其中所述軟體在由所述處理器執行時使所述處理器: 將原始碼轉換成包含多個互連狀態的自動機； 將所述自動機轉換成網表，所述網表包含對應於所述自動機的狀態的實例，其中所述實例對應於所述並行機的硬體元件，其中所述實例包括多個第一實例及含有兩個或兩個以上第一實例的群組實例，其中將所述自動機轉換成網表包括基於許多未用的第一實例來將狀態一起分組在群組實例中；及將所述網錶轉換成所述映像。
26.根據權利要求25所述的計算機，其中所述群組實例包括成對群組GOT實例，且其中分組狀態包括根據成對的狀態驅動哪些狀態來使狀態成對。
27.根據權利要求26所述的計算機，其中基於許多未用的第一實例將狀態分組在群組實例中包括: 基於以下條件確定第一狀態與第二狀態是否可成對: 所述第一狀態或所述第二狀態均非所述自動機中的最終狀態，且所述第一狀態及所述第二狀態中的一者不驅動不同於所述第一狀態或所述第二狀態的任何狀態； 所述第一狀態或所述第二狀態均非所述自動機中的最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態； 所述第一狀態或所述第二狀態中的任一者為最終狀態，且並非最終狀態的所述第一狀態或所述第二狀態不驅動除了所述第一狀態或所述第二狀態之外的任何狀態；及 所述第一狀態及所述第二狀態均為最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態。·
28.根據權利要求25所述的計算機，其中將所述自動機轉換成網表包括: 將所述狀態模型化為圖，其中所述圖的頂點對應於狀態，且所述圖的邊對應於所述狀態的可能成對； 確定所述圖的匹配頂點；及 使對應於所述匹配頂點的狀態成對。
29.根據權利要求28所述的計算機，其中將所述自動機轉換成網表包括: 確定所述圖的最大匹配。
30.根據權利要求29所述的計算機，其中將所述自動機轉換成網表包括: 使對應於匹配頂點的每一組狀態成對；及 將對應於未匹配頂點的每一狀態映射到一 GOT實例，其中所述GOT實例中的一個SME實例將為未用的。
31.一種系統，其包含: 計算機，其經配置以: 將原始碼轉換成包含多個互連狀態的自動機； 將所述自動機轉換成網表，所述網表包含對應於所述自動機的狀態的實例，其中所述實例對應於所述並行機的硬體元件，其中所述實例包括多個第一實例及含有兩個或兩個以上第一實例的群組實例，其中將所述自動機轉換成網表包括基於許多未用的第一實例來將狀態一起分組在群組實例中；及將所述網錶轉換成映像；及裝置，其經配置以將所述映像加載到並行機上。
32.根據權利要求31所述的系統，其中對狀態一起分組包括: 根據成對的狀態驅動哪些狀態來使狀態成對。
33.根據權利要求31所述的系統，其中基於許多未用的第一實例將狀態一起分組在群組實例中包括: 基於以下條件確定第一狀態與第二狀態是否可成對: 所述第一狀態或所述第二狀態均非所述自動機中的最終狀態，且所述第一狀態及所述第二狀態中的一者不驅動不同於所述第一狀態或所述第二狀態的任何狀態； 所述第一狀態或所述第二狀態均非所述自動機中的最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態； 所述第一狀態或所述第二狀態中的任一者為最終狀態，且並非最終狀態的所述第一狀態或所述第二狀態不驅動除了所述第一狀態或所述第二狀態之外的任何狀態；及 所述第一狀態及所述第二狀態均為最終狀態，且所述第一狀態及所述第二狀態均驅動相同的外部狀態。
34.根據權利要求31所述的系統，其中基於許多未用的第一實例將狀態一起分組在群組實例中包括: 將所述狀態模型化為圖，其中所述圖的頂點對應於狀態，且所述圖的邊對應於所述狀態的可能成對； 確定所述圖的匹配頂點；及 使對應於所述匹配頂點的狀態成對。
35.根據權利要求34所述的系統,其中基於許多未用的第一實例將狀態一起分組在群組實例中: 確定所述圖的最大匹 配。
36.根據權利要求35所述的系統,其中基於許多未用的第一實例將狀態一起分組在群組實例中包括: 使對應於匹配頂點的每一組狀態成對；及 將對應於未匹配頂點的每一狀態映射到一 GOT實例，其中所述GOT實例中的一個SME頭例將為未用的。
37.根據權利要求31所述的系統，其中所述裝置經配置以將每一對狀態實施為所述並行機中的兩個硬體元件的群組。
38.一種通過用根據權利要求1所述的過程產生的映像編程的並行機。
【文檔編號】G06F9/45GK103430148SQ201280013903
【公開日】2013年12月4日 申請日期:2012年1月24日 優先權日:2011年1月25日
【發明者】許郡君, 保羅·格倫迪寧 申請人:美光科技公司