猝發模式異步控制電路設計方法
2023-05-19 21:32:26
專利名稱：猝發模式異步控制電路設計方法
技術領域：
本發明涉及大規模異步控制電路的設計方法，尤其是大規模猝發模式(burst-mode)異步控制電路的設計方法。
背景技術：
由於集成電路規模的擴大、特徵尺寸的減小、設計主頻的提高以及製造工藝的限制，同步電路中原先可以忽略的線延遲、時鐘樹負載等日益突出，設計方法上也面臨著許多難以解決的問題(特別是時鐘偏差問題)。相對而言，異步電路不需要全局時鐘，有效地避免了複雜的時鐘樹設計及其時鐘偏差問題，同時以可移植性好、模塊化程度高、抗電磁幹擾能力強、功耗低等諸多特性逐漸成為電路設計研究的熱點。
異步電路的發展可以說在很大程度上取決於異步電路設計方法與EDA工具的完善和成熟。由於異步電路與同步電路的主要差異在於電路的控制邏輯，其數據通路基本一致，因此現有的異步電路設計方法一般說來都是利用已有的同步電路的設計流程和商用EDA工具進行異步數據通路設計，而將工作重點放在異步控制電路設計上。
根據異步控制電路的類型以及描述機制的不同，異步控制電路設計方法可以大致劃分為基於CSP的方法、基於Petri網的方法以及基於有限狀態機的方法三類 A.基於CSP(Communicating Sequential Processes)的方法主要採用Balsa、Tangram、DI-Algebra、DISP(DI Sequential Processes)以及CHP(Communicating Hardware Processes)等CSP類異步描述語言對控制電路的行為進行描述，經由語法驅動的轉換(syntax-directed translation)得到延遲無關或者準延遲無關異步控制電路。這類方法可以在較高層次對電路行為進行描述，能夠較為充分地挖掘異步控制電路的並行性，其缺點是 a)無法運用全局優化技術，設計得到的電路工作效率不高； b)CSP類異步描述語言語法晦澀，相關EDA工具不完善，難以得到廣泛的接受和使用； B.基於Petri網的方法主要採用LPN(Labeled Petri Net)、STG(SignalTransition Graph)或者CD(Change Diagram)等對控制電路的行為進行描述，經由可達性分析、狀態編碼、布爾表達式生成、邏輯分解以及工藝映射得到速度無關異步控制電路。這類方法可以在較低層次描述電路行為，能夠在優化時使用時序信息，產生較為高效的電路結構，其缺點是採用無限門延遲模型，對線延遲忽略不計，導致電路存在一些不必要的開銷。同時，對於深亞微米工藝而言，線延遲佔有主導地位，電路的延遲假設可能不再適用。
C.基於有限狀態機的方法主要採用異步有限狀態機(Asynchronous FiniteState Machine)或者猝發模式狀態機(Burst Mode Machine)對控制電路的行為進行描述，經由狀態歸約、狀態賦值、邏輯綜合以及工藝映射分別得到基本模式Huffman電路和猝發模式異步控制電路。這類方法與基於有限狀態機的同步電路設計方法類似，可以充分利用或者借鑑現有的設計方法和EDA工具加以處理，不足之處在於不允許輸入和輸出並發變化，若且唯若電路完全穩定，也就是電路的狀態不再發生變化的時候，電路的外部輸入信號才允許改變，由此導致電路的運行周期加長，工作效率降低。
通過比較上述方法的優勢與不足可知，基於有限狀態機的異步控制電路設計方法更具可行性和實用性。
猝發模式狀態機是基於有限狀態機的異步控制電路設計方法所常用的描述機制，它採用類似於同步Mealy機的狀態轉換圖對電路行為進行說明。猝發模式狀態機源於異步有限狀態機，但是對異步有限狀態機的描述能力進行了擴展降低異步有限狀態機的基本假設要求(異步有限狀態機要求對前一個輸入信號的響應穩定之前，當前輸入信號不發生變化)，允許猝發輸入(非空的輸入信號集合)中的信號以任何順序發生變化。當然，猝發模式狀態機仍然要求各個猝發輸入之間必須滿足基本假設。
猝發模式狀態機M通常採用7元偶進行形式化描述，其中V是狀態節點集合，節點v∈V對應於M的狀態v，EV×V是有向邊集合，有向邊e＝∈E連接節點u和v，用於描述M中狀態u和v之間的轉換，I＝{x1，…，xm}是輸入信號集合，O＝{z1，…，zn}是輸出信號集合，節點v0∈V定義為起始狀態節點，與M的起始狀態v0相對應。有向邊標記函數transiE→{-，+}I和transoE→{-，+}O分別用於指定狀態轉換時的猝發輸入變遷和猝發輸出變遷，也就是狀態轉換過程中猝發輸入和猝發輸出的變化情況。對於任意有向邊e∈E，其對應的猝發輸入和猝發輸出採用「|」加以區分，「|」之前為猝發輸入，之後為猝發輸出，猝發輸出允許為空。
猝發模式異步控制電路經由猝發模式狀態機得到，由猝發輸入、猝發輸出、組合邏輯電路以及反饋迴路構成，組合邏輯電路採用有限延遲模型，反饋迴路採用無限反饋延遲模型。電路的當前狀態保存在反饋迴路中，電路的猝發輸出和下一狀態由猝發輸入、當前狀態以及部分輸出信號的反饋共同決定。
對基於有限狀態機的異步控制電路設計方法而言，由於在邏輯綜合階段需要進行完備的狀態空間搜索，面臨狀態空間爆炸問題，因此僅僅適用於中小規模控制電路的設計。為了有效地提高猝發模式異步控制電路的設計規模，哥倫比亞大學的異步電路與系統研究小組在文章A Cycle-BasedDecomposition Method for Burst-Mode Asynchronous Controllers中提出了一種大規模猝發模式異步控制電路的分解設計方法，該方法首先對複雜的猝發模式狀態機進行層次化分解，獲得相互獨立的猝發模式子狀態機，各子狀態機的輸入均為外部環境的輸入信號，子狀態機之間不存在輸入輸出上的制約關係；然後利用已有的異步控制電路綜合工具(加利福尼亞大學的3D和哥倫比亞大學的MINIMALIST)對各子狀態機分別進行綜合得到對應的猝發模式子控制電路模塊；接著對各子控制電路模塊進行調整，增加輸入信號鎖存模塊以解決子控制電路模塊之間的仲裁問題(由於子控制電路模塊是相互獨立的，輸入信號的變化可能導致多個子控制電路模塊同時被驅動，為此需要合理選擇允許運行的子控制電路模塊)；最後將各子控制電路模塊進行連接獲得最終的猝發模式異步控制電路。該方法存在兩點不足一是採用深度優先搜索算法進行猝發模式狀態機的層次化分解，分解效率較低；二是子控制電路模塊的仲裁機制要求各子控制電路模塊之間存在嚴格的時序約束，在電路設計過程中很難得到滿足，因此這種方法難以有效地付諸實際應用。
發明內容
本發明要解決的技術問題是改進現有猝發模式異步控制電路的設計方法，提高設計規模，使大規模猝發模式異步控制電路實用化。利用猝發模式狀態機所對應有向圖的有向迴路集合對狀態機進行分解得到相互獨立的猝發模式子狀態機；對各子狀態機進行調整，採用請求/應答信號實現相應子狀態機之間的四段握手通信；設計猝發模式接口狀態機解決相應子狀態機之間的仲裁問題。
本發明的技術方案是 本發明包括分解猝發模式狀態機、調整猝發模式子狀態機、設計猝發模式接口狀態機、再調整猝發模式子狀態機、實現子控制電路模塊和接口控制電路模塊以及合成猝發模式異步控制電路六步。具體步驟是 1.利用猝發模式狀態機M所對應有向圖的有向迴路集合對M進行層次化分解，得到K級猝發模式子狀態機，K為M分解得到的猝發模式子狀態機的總級數。
分解流程為 (1)根據M所對應有向圖G＝的有向迴路集合C確定初始子狀態機集合S任一有向迴路c(c∈C)在M中的對應結構，包括狀態節點、有向邊及相應的猝發輸入和猝發輸出，構成一個初始子狀態機s(s∈S)。
(2)確定判定節點集合DG中所有出度大於2的頂點在M中的對應狀態節點即為判定節點。
(3)M中起始狀態節點v0到最近的判定節點d1∈D之間的有向通路及相應的猝發輸入和猝發輸出構成第一級猝發模式子狀態機，第一級子狀態機的起始狀態節點為v0；所有包含判定節點d1的初始子狀態機均為第二級猝發模式子狀態機，第二級子狀態機的起始狀態節點為d1。
(4)設定子狀態機級數N＝2。
(5)從S中刪除所有第N級猝發模式子狀態機。
(6)對S進行判斷，如果S不為空，跳轉至步驟(7)；如果S為空則M分解完成。
(7)對第N級猝發模式子狀態機逐一進行判斷，如果存在除起始狀態節點之外的其他判定節點(可能不是唯一的，不失一般性記為dNi，i＝1，…，l，l為第N級猝發模式子狀態機中除起始狀態節點之外的判定節點數目)，則S中所有包含dNi的初始子狀態機均為第N+1級猝發模式子狀態機，起始狀態節點為dNi。
(8)調整子狀態機級數N＝N+1，跳轉至步驟(6)。
2.增加額外的請求/應答信號，對第1級至第K級所有的猝發模式子狀態機進行調整，實現相鄰兩級子狀態機之間的四段握手通信，去除相鄰兩級子狀態機之間的時序要求。對第1級至第K級所有的猝發模式子狀態機進行調整的方法是 (1)在第N級猝發模式子狀態機MN(1≤N≤K-1)中，增加輔助狀態節點vN與除起始狀態節點之外的判定節點dN相連接；設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為ackN+和reqN-；設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為ackN-和reqN+；以dN為終點的有向邊(除外)的猝發輸出變遷增加reqN+。(+代表信號由0到1的變遷，-代表由1到0的變遷) (2)記MN對應的第N+1級猝發模式子狀態機分別為MN+11，…，MN+1L，L為第N+1級猝發模式子狀態機的個數，在MN+1i(i＝1，…，L)中，以起始狀態節點dN為起點的有向邊的猝發輸入變遷和猝發輸出變遷分別增加reqN+1i+和ackN+1i+，以節點dN為終點的有向邊的猝發輸入變遷和猝發輸出變遷分別增加reqN+1i-和ackN+1i-。
MN與任意第N+1級猝發模式子狀態機MN+1i的通信過程為 (1)MN進入狀態dN，同時將信號reqN置為高，啟動握手操作，請求觸發第N+1級子狀態機； (2)MN+1i接收來自MN的觸發請求reqN+1i+，然後將信號ackN+1i置為高加以確認； (3)MN接收來自MN+1i的應答信號ackN+，進入狀態vN，同時將信號reqN置為低，對握手操作進行復位； (4)MN+1i接收來自MN的復位請求reqN+1i-，然後將信號ackN+1i置為低，加以確認； (5)MN接收來自MN+1i的應答信號ackN+，回到狀態dN，同時再次將信號reqN置為高，進行新的通訊。
對於MN與任意第N+1級猝發模式子狀態機MN+1i而言，由於採用延遲無關的四段握手協議進行通訊，MN+1i接收到MN所發送的觸發請求之後才能執行，MN+1i執行時MN被中斷，MN+1i執行完畢MN才能進行執行，因而可以有效地去除相鄰兩級子狀態機之間的時序要求。
由於MN+11，…，MN+1L是相互獨立的，也就是說各子狀態機之間不存在輸入輸出上的制約關係，因此某個輸入信號的變化可能導致多個子狀態機同時被觸發，從而產生子狀態機的仲裁問題。
3.在相鄰兩級子狀態機之間設計猝發模式接口狀態機，對子狀態機是否觸發進行仲裁。
對於任意第N級猝發模式子狀態機MN及其對應的第N+1級猝發模式子狀態機MN+11，…，MN+1L而言，1≤N＜K，L為第N+1級猝發模式子狀態機的總數目；子狀態機MN除起始狀態節點之外的判定節點為dN，輔助狀態節點為vN，以節點dN為起點的有向邊eN≠所對應的猝發輸入為BIN，相應的猝發輸入變遷為transi(eN)；子狀態機MN+1i(i＝1，…，L)以起始狀態節點dN為起點的有向邊eN+1i所對應的猝發輸入為BIN+1i，其相應的猝發輸入變遷為transi(eN+1i)。
接口狀態機的設計方法是 (1)確定接口狀態機的輸入輸出信號。接口狀態機與MN，MN+11，…，MN+1L相連接，輸入信號包括猝發輸入BIN，BIN+11，…，BIN+1L、子狀態機MN的請求信號reqN以及子狀態機MN+11，…，MN+1L相應的應答信號ackN+11，…，ackN+1L；輸出信號包括子狀態機MN的應答信號ackN、子狀態機MN+11，…，MN+1L相應的請求信號reqN+11，…，reqN+1L以及輔助信號pseu。
(2)確定接口狀態機狀態節點的數目。當N＝1時，接口狀態機僅需要解決MN+11，…，MN+1L之間的觸發仲裁問題，此時需要3L+1個狀態節點，記為dN，v11，…，vL1，v12，…，vL2，v13，…，vL3。當1＜N＜K時，接口狀態機不僅需要解決MN+11，…，MN+1L之間的觸發仲裁問題，而且需要解決MN與MN+11，…，MN+1L之間的觸發仲裁問題，此時需要3L+3個狀態節點，記為dN，v01，v11，…，vL1，v02，v12，…，vL2，v13，…，vL3。
(3)確定狀態節點之間的有向邊及其對應的猝發輸入/猝發輸出變遷。
a)有向邊，對應的猝發輸入變遷為reqN+，transi(eN)，猝發輸出變遷為pseu+；有向邊，對應的猝發輸入變遷為reqN-，猝發輸出變遷為pseu-；有向邊，對應的猝發輸入變遷為
對於任意信號x∈BIN，如果x+∈transi(eN)，則如果x-∈transi(eN)，則 b)對於任意i＝1，…，L，有向邊，對應的猝發輸入變遷為reqN+，transi(eN+1i>，猝發輸出變遷為reqN+1i+；有向邊，對應的猝發輸入變遷為ackN+1i+，猝發輸出變遷為ackN+；有向邊，對應的猝發輸入變遷為
猝發輸出變遷為reqN+1i-；有向邊， 對應的猝發輸入變遷為ackN+1i-，猝發輸出變遷為ackN-。
對於第一級子狀態機而言，除之外不存在其他以節點d1為起點的有向邊，連接第一級子狀態機和第二級子狀態機的接口狀態機無需輸出輔助信號pseu，因此這個接口狀態機最簡單。
在第N級猝發模式子狀態機MN及其對應的第N+1級猝發模式子狀態機MN+11，…，MN+1L之間設計接口狀態機之後，當MN進入狀態dN時，MN將啟動握手操作，請求接口狀態機進行仲裁，接口狀態機則根據外部環境輸入信號的變化情況進行判斷，對子狀態機是否觸發進行仲裁，方法為 (1)如果猝發輸入變遷reqN+，transi(eN+1i)先有效，那麼接口狀態機進入狀態vi1，選擇觸發第N+1級子狀態機MN+1i，具體過程為 a)接口狀態機接收來自MN的仲裁請求reqN+，當猝發輸入變遷transi(eN)有效時進入狀態vi1，同時將信號reqN+1i置為高，請求觸發MN+1i； b)MN+1i接收來自狀態機的觸發請求reqN+1i+，將信號ackN+1i置為高，對觸發請求加以確認； c)接口狀態機接收來自MN+1i的應答信號ackN+1i，進入狀態vi2，同時將信號ackN置為高，對仲裁請求加以確認； d)MN接收來自接口狀態機的應答信號ackN+，進入狀態vN，同時將reqN置為低，對仲裁請求進行復位； e)接口狀態機接收來自MN的仲裁復位請求reqN-，進入狀態vi3，同時將reqN+1i置為低，對觸發請求進行復位； f)MN+1i接收來自接口狀態機的觸發復位請求reqN+1i-，等待相應的猝發輸入變遷有效，然後進入狀態dN，同時將信號ackN+1i置為低，對觸發復位加以確認； g)接口狀態機接收來自MN+1i的應答信號ackN+1i-，回到狀態dN，同時將信號ackN置為低，對仲裁復位加以確認； h)MN接收來自接口狀態機的應答信號ackN+，回到狀態dN，同時再次將信號reqN置為高，進行新的仲裁。
(2)如果猝發輸入變遷reqN+，transi(eN)先有效，那麼接口狀態機進入狀態v01，選擇繼續運行MN，具體過程為 a)接口狀態機接收來自MN的仲裁請求reqN+，當猝發輸入變遷transi(eN+1i)有效時進入狀態v01，同時將信號pseu置為高； b)MN接收來自接口狀態機的輔助信號變遷pseu+，然後將reqN置為低進行復位； c)接口狀態機接收復位請求reqN-，進入狀態v02，同時將信號pseu置為低； d)MN接收來自接口狀態機的輔助信號變遷pseu-等待相應的猝發輸入變遷有效，進而繼續運行； e)接口狀態機等待相應的猝發輸入變遷有效，然後回到狀態dN，等待新的仲裁請求。
4.再次調整第2級到第K-1級的所有猝發模式子狀態機MN，2≤N＜K，實現N級猝發模式子狀態機與對應N+1級子狀態機之間的仲裁。
對於第N級猝發模式子狀態機MN及其對應的第N+1級子狀態機MN+11，…，MN+1L而言，採用接口狀態機進行仲裁時，MN將根據接口狀態機的輔助輸出信號pseu是否發生變遷來決定是繼續運行還是等待某一個N+1級子狀態機被觸發並運行完畢。為此，MN需要引入新的輸入信號pseu，進行再調整。
MN除起始狀態節點之外的判定節點為dN，除輔助狀態節點vN以外與dN通過有向邊連接的節點為vc；有向邊對應的猝發輸出變遷reqN-，有向邊eN＝所對應的猝發輸入變遷和猝發輸出變遷分別為transi(eN)和transo(eN)。
調整方法為 (1)刪除有向邊及其相應的猝發輸入變遷transi(eN)和猝發輸出變遷transo(eN)； (2)增加額外的狀態節點v，設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為pseu+和reqN-；設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為pseu-，transi(eN)和transo(eN)。
5.對所有的猝發模式子狀態機和猝發模式接口狀態機採用已有的基於有限狀態機的異步控制電路設計方法和工具進行狀態歸約、狀態賦值、邏輯綜合以及工藝映射，得到相應的子控制電路模塊和接口控制電路模塊。
6.將所有的子控制電路模塊和接口控制電路模塊按照對應信號進行連接得到最終的猝發模式異步控制電路。
採用本發明可以達到以下技術效果 1.本發明充分利用猝發模式狀態機所對應有向圖的有向迴路集合對狀態機進行層次化分解，比基於深度優先搜索的分解算法分解效率更高，處理規模更大； 2.通過額外設計的猝發模式接口狀態機有效地解決了各子狀態機之間的仲裁問題，設計方法簡單且不需要增加任何時序約束； 3.利用請求/應答信號實現相應子狀態機之間的四段握手協議進行通信，有效地去除了各子狀態機之間的時序約束要求，降低了邏輯綜合的難度。
圖1四段握手通信的時序圖； 圖2基於有限狀態機的異步控制電路設計方法流程圖； 圖3猝發模式異步控制電路結構圖； 圖4哥倫比亞大學所提出的基於層次化分解的猝發模式異步控制電路設計方法流程圖； 圖5本發明基於層次化分解的猝發模式異步控制電路設計方法流程圖； 圖6為一個典型的猝發模式狀態機M； 圖7為圖6所示猝發模式狀態機M對應的有向圖及其有向迴路集合； 圖8為採用本發明對M進行分解後的猝發模式子狀態機； 圖9為對圖8所示的猝發模式子狀態機進行調整後的猝發模式子狀態機； 圖10為對圖9所示猝發模式子狀態機再調整之後的猝發模式子狀態機； 圖11為採用本發明對M設計的猝發模式接口狀態機； 圖12為圖11所示接口狀態機與子狀態機連接方式示意圖。
具體實施例方式 圖1為兩個異步電路模塊之間進行四段握手通信時請求/應答信號的時序圖。當兩個異步電路模塊A、B之間同步傳輸數據時，通常包括四個步驟 (1)模塊A發送數據，同時將請求信號req置為高來啟動握手；(2)模塊B接收數據，然後將應答信號ack置為高進行確認，表示已經接收到數據，並開始相應的運算；(3)模塊A將請求信號req置為低進行復位；(4)模塊B將應答信號ack置為低完成握手。
圖2是基於有限狀態機的異步控制電路設計方法流程圖。基於有限狀態機模型的異步電路設計方法與同步電路的設計流程基本相同，首先將有限狀態機描述轉換為異步流表，其次進行狀態歸約與賦值得到二進位異步流表，接著進行邏輯綜合確定輸出變量的邏輯表達式，最後通過工藝映射獲得電路的門級網表。
圖3為猝發模式異步控制電路結構圖。猝發模式異步控制電路由猝發輸入、猝發輸出、組合邏輯電路以及反饋迴路構成，組合邏輯電路採用有限延遲模型，反饋迴路採用無限反饋延遲模型。電路的當前狀態保存在反饋迴路中，電路的猝發輸出和下一狀態由猝發輸入、當前狀態以及部分輸出信號的反饋共同決定。
圖4為哥倫比亞大學公布的基於層次化分解的猝發模式異步控制電路設計方法流程圖。對於給定的複雜猝發模式狀態機描述，首先採用深度優先搜索算法進行層次化分解得到相互獨立的猝發模式子狀態機；其次採用已有的猝發模式狀態機綜合工具(比如說加利福尼亞大學的3D和哥倫比亞大學的MINIMALIST)對各子狀態機分別進行邏輯綜合得到對應的猝發模式子控制電路模塊；接著對各子控制電路模塊進行調整，增加輸入信號鎖存模塊以解決子控制電路模塊之間的仲裁問題，最後將各子控制模塊按照對應的輸入輸出信號關係進行連接獲得最終的猝發模式異步控制電路。
圖5為本發明所提出的基於層次化分解的猝發模式異步控制電路設計方法流程圖，總共包括6個步驟(1)利用猝發模式狀態機所對應有向圖的有向迴路集合對狀態機進行層次化分解；(2)通過增加額外的請求/應答信號對猝發模式子狀態機進行調整，實現相應子狀態機之間的四段握手通信；(3)設計猝發模式接口狀態機解決子狀態機的仲裁問題；(4)再次調整猝發模式子狀態機，實現第N級猝發模式子狀態機與對應第N+1級子狀態機之間的仲裁；(5)對各子狀態機和接口狀態機進行邏輯綜合獲得子控制電路模塊和接口電路模塊；(6)將各子控制模塊進行連接獲得最終的猝發模式異步控制電路。
圖6為一個典型的猝發模式狀態機M，其狀態節點為v0，v1，v2，v3，v4，v5；有向邊為，，，，，，，；輸入信號為ain，bin，cin以及din，輸出信號為yout和zout起始狀態節點為v0。
圖7.1為M對應的有向圖G。圖7.2、7.3以及7.4為有向圖G的有向迴路，構成有向迴路集合C。
圖8為採用本發明對圖6所示M進行分解後得到的猝發模式子狀態機。圖8.1所示為第一級猝發模式子狀態機M1，圖8.2所示為第二級猝發模式子狀態機M21，圖8.3所示為第二級猝發模式子狀態機M22，圖8.4所示為第三級猝發模式子狀態機M31。
具體分解過程是 (1)生成M的初始子狀態機集合S。有向迴路集合C中的有向迴路在M中的對應結構，包括狀態節點、有向邊及相應的猝發輸入和猝發輸出，構成M的初始子狀態機。圖7.2、圖7.3以及圖7.4所示有向迴路分別與圖8.2、圖8.3以及圖8.4所示初始子狀態機相對應。
(2)確定M中判定節點集合D，D＝{v2，v4}。
(3)M中起始狀態節點v0到判定節點v2之間的有向路徑及相應的猝發輸入和猝發輸出構成第一級猝發模式子狀態機M1，起始狀態節點為v0。
(4)包含節點v2的初始子狀態機為第二級猝發模式子狀態機M21和M22，起始狀態節點均設定為v2。
(5)對於M22而言，除起始狀態節點v2之外還存在判定節點v4，因此包含v4的初始子狀態機為第三級猝發模式子狀態機M31，起始狀態節點設定為v4。
圖9為對圖8所示的猝發模式子狀態機進行調整，即增加額外的請求/應答信號之後的猝發模式子狀態機。圖9.1、圖9.2、圖9.3以及圖9.4所示的調整後的猝發模式子狀態機分別與圖8.1、圖8.2、圖8.3以及圖8.4所示的猝發模式子狀態機相對應。
具體的調整步驟為 (1)在如圖8.1所示的M1中，增加輔助狀態節點v1與節點v2相連接；設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為ack1+和req1-；設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為ack1-和req1+；有向邊的猝發輸出變遷增加req1+。
(2)在如圖8.2所示的M21中，有向邊的猝發輸入變遷和猝發輸出變遷分別增加req21+和ack21+，有向邊的猝發輸入變遷和猝發輸出變遷分別增加req21-和ack21-。
(3)在如圖8.3所示的M22中，有向邊的猝發輸入變遷和猝發輸出變遷分別增加req22+和ack22+，有向邊的猝發輸入變遷和猝發輸出變遷分別增加req22-和ack22-。
(4)在如圖8.3所示的M22中，增加輔助狀態節點v2與節點v4相連接；設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為ack2+和req2-；設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為ack2-和req2+；有向邊的猝發輸出變遷增加req2+。
(5)在如圖8.4所示的M31中，有向邊的猝發輸入變遷和猝發輸出變遷分別增加req31+和ack31+，有向邊的猝發輸入變遷和猝發輸出變遷分別增加req31-和ack31-。
圖10為引入接口狀態機的輸出輔助信號pseu進行再調整之後的猝發模式子狀態機。對於M的第二級猝發模式子狀態機M21和M22而言，由於M21沒有對應的第三級猝發模式子狀態機，所以僅需要調整M22。
具體的調整步驟為 (1)刪除有向邊及其相應的猝發輸入變遷ain+，bin+； (2)增加額外的狀態節點v，設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為pseu+和req2-； (3)設定有向邊對應的猝發輸入變遷為pseu-，ain+，bin+。
圖11為採用本發明設計的猝發模式接口狀態機，圖11.1所示接口狀態機A用於解決圖9.1所示第一級猝發模式子狀態機M1與圖9.2、圖10所示第二級猝發模式子狀態機M21、M22之間的仲裁問題。圖11.2所示接口狀態機B是則為了解決圖10所示第二級猝發模式子狀態機M22與圖9.4所示第三級猝發模式子狀態機M31之間的仲裁問題。
接口狀態機A的仲裁過程為M1進入狀態v2，同時將信號req1置為高，啟動握手操作，請求接口狀態機A進行仲裁；接口狀態機A根據外部環境輸入信號的變化情況進行判斷，如果猝發輸入變遷req1+，bin+，cin+先有效，則接口狀態機A進入狀態v11，選擇觸發M21；如果輸入變遷req1+，ain-先有效，則接口狀態機A進入狀態v21，選擇觸發M22。
1、當接口狀態機A進入狀態v11，選擇觸發M21時，具體執行過程為 a)接口狀態機A接收來自M1的仲裁請求req1+，當猝發輸入變遷bin+，cin+有效時進入狀態v11，同時將信號req21置為高，請求觸發M21； b)M21接收來自接口狀態機A的觸發請求req21+，進入狀態v3，同時將信號ack21置為高，對觸發請求加以確認； c)接口狀態機A接收來自M21的應答信號ack21+，進入狀態v12，同時將信號ack1置為高，對仲裁請求加以確認； d)M1接收來自接口狀態機A的應答信號ack1+，進入狀態v1，同時將req1置為低，對仲裁請求進行復位； e)接口狀態機A接收來自M1的仲裁復位請求req1-，進入狀態v13，同時將req21置為低，對觸發請求進行復位； f)M21接收來自接口狀態機A的觸發復位請求req21-，等待猝發輸入變遷bin-，cin-有效，然後回到狀態v2，同時將信號ack21置為低，對觸發復位加以確認； g)接口狀態機A接收來自M21的應答信號ack21-，回到狀態v2，同時將信號ack1置為低，對仲裁復位加以確認； h)M1接收來自接口狀態機A的應答信號ack1+，回到狀態v2，同時再次將信號req1置為高進行新的仲裁。
2、接口狀態機A進入狀態v21選擇觸發M22時的具體執行過程與其進入狀態v11選擇觸發M21時基本一致。
接口狀態機B的仲裁過程為M22進入狀態v4，同時將信號req2置為高，啟動握手操作，請求接口狀態機B進行仲裁；接口狀態機B根據外部環境輸入信號的變化情況進行判斷，如果猝發輸入變遷req2+，ain+，bin+先有效，那麼接口狀態機B進入狀態v01，選擇繼續運行M22；如果猝發輸入變遷req2+，din+先有效，那麼接口狀態機B進入狀態v11，選擇觸發M31。
1、接口狀態機B進入狀態v11選擇觸發M31時的具體執行過程與接口狀態機A進入狀態v11選擇觸發M21時基本一致。
2、接口狀態機B進入狀態v01，選擇繼續運行M22時，具體執行過程為 a)接口狀態機B接收到來自M22的仲裁請求req2+，當猝發輸入變遷din+有效時進入狀態v01，同時將信號pseu置為高； b)M22接收來自接口狀態機B的輔助信號變遷pseu+，進入狀態v並將req2置為低進行復位； c)接口狀態機B接收復位請求reqN-，進入狀態v02，同時將信號pseu置為低； d)M22接收來自接口狀態機B的輔助信號變遷pseu-，等待猝發輸入變遷ain-，bin-有效，然後進入狀態v1繼續運行； e)接口狀態機等待猝發輸入變遷ain-，bin-有效，然後回到狀態v4，等待新的仲裁請求。
圖12.1是圖11.1所示接口狀態機A與圖9.1所示第一級猝發模式子狀態機M1、圖9.2所示第二級猝發模式子狀態機M21以及圖10所示第二級猝發模式子狀態機M22的連接方式示意圖。接口狀態機A通過握手信號req1和ack1與M1相連接，通過握手信號req21和ack21與M21相連接，通過握手信號req22和ack22與M22相連接。圖12.2是圖11.2所示接口狀態機B與圖10所示第二級猝發模式子狀態機M22以及圖9.4所示第三級猝發模式子狀態機M31之間的連接方式示意圖。接口狀態機B通過握手信號req2和ack2以及輔助信號pseu與M22相連接，通過信號req31和ack31與M31相連接。
權利要求
1.一種猝發模式異步控制電路設計方法，它包括分解猝發模式狀態機、實現子控制電路模塊、合成猝發模式異步控制電路這些步驟，其特徵在於在分解猝發模式狀態機步驟和實現子控制電路模塊步驟之間還包括調整猝發模式子狀態機、設計猝發模式接口狀態機、再調整猝發模式子狀態機三個步驟，具體步驟為
第一步，利用猝發模式狀態機M所對應有向圖的有向迴路集合對M進行層次化分解，得到K級猝發模式子狀態機，K為M分解得到的猝發模式子狀態機的總級數；
第二步，增加額外的請求/應答信號，對第1級至第K級所有的猝發模式子狀態機進行調整，實現相鄰兩級子狀態機之間的四段握手通信，去除相鄰兩級子狀態機之間的時序要求；
第三步，在相鄰兩級子狀態機之間設計猝發模式接口狀態機，對子狀態機是否觸發進行仲裁；
第四步，再次調整第2級到第K-1級的所有猝發模式子狀態機MN，2≤N＜K，實現N級猝發模式子狀態機與對應N+1級子狀態機之間的仲裁；
第五步，對所有的猝發模式子狀態機和猝發模式接口狀態機進行狀態歸約、狀態賦值、邏輯綜合以及工藝映射，得到相應的子控制電路模塊和接口控制電路模塊；
第六步，將所有的子控制電路模塊和接口控制電路模塊按照對應信號進行連接得到最終的猝發模式異步控制電路。
2.如權利要求1所述的一種猝發模式異步控制電路設計方法，其特徵在於所述層次化分解的流程為
(1)根據M所對應有向圖G＝的有向迴路集合C確定初始子狀態機集合S任一有向迴路c(c∈C)在M中的對應結構，包括狀態節點、有向邊及相應的猝發輸入和猝發輸出，構成一個初始子狀態機s(s∈S)；
(2)確定判定節點集合DG中所有出度大於2的頂點在M中的對應狀態節點即為判定節點；
(3)M中起始狀態節點v0到最近的判定節點d1∈D之間的有向通路及相應的猝發輸入和猝發輸出構成第一級猝發模式子狀態機，第一級子狀態機的起始狀態節點為v0；所有包含判定節點d1的初始子狀態機均為第二級猝發模式子狀態機，第二級子狀態機的起始狀態節點為d1；
(4)設定子狀態機級數N＝2；
(5)從S中刪除所有第N級猝發模式子狀態機；
(6)對S進行判斷，如果S不為空，跳轉至步驟(7)；如果S為空則M分解完成；
(7)對第N級猝發模式子狀態機逐一進行判斷，如果存在除起始狀態節點之外的其他判定節點dNi，i＝1，…，l，l為第N級猝發模式子狀態機中除起始狀態節點之外的判定節點數目，則S中所有包含dNi的初始子狀態機均為第N+1級猝發模式子狀態機，起始狀態節點為dNi；
(8)調整子狀態機級數N＝N+1，跳轉至步驟(6)。
3.如權利要求1所述的一種猝發模式異步控制電路設計方法，其特徵在於對第1級至第K級所有的猝發模式子狀態機進行調整的方法是
(1)在第N級猝發模式子狀態機MN(1≤N≤K-1)中，增加輔助狀態節點vN與除起始狀態節點之外的判定節點dN相連接；設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為ackN+和reqN-；設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為ackN-和reqN+；以dN為終點的有向邊(除外)的猝發輸出變遷增加reqN+；+代表信號由0到1的變遷，-代表由1到0的變遷；
(2)記MN對應的第N+1級猝發模式子狀態機分別為MN+11，…，MN+1L，L為第N+1級猝發模式子狀態機的個數，在MN+1i(i＝1，…，L)中，以起始狀態節點dN為起點的有向邊的猝發輸入變遷和猝發輸出變遷分別增加reqN+1i+和ackN+1i+，以節點dN為終點的有向邊的猝發輸入變遷和猝發輸出變遷分別增加reqN+1i-和ackN+1i-。
4.如權利要求3所述的一種猝發模式異步控制電路設計方法，其特徵在於所述MN與任意N+1級猝發模式子狀態機MN+1i的通信過程為
(1)MN進入狀態dN，同時將信號reqN置為高，啟動握手操作，請求觸發第N+1級子狀態機；
(2)MN+1i接收來自MN的觸發請求reqN+1i+，然後將信號ackN+1i置為高加以確認；
(3)MN接收來自MN+1i的應答信號ackN+，進入狀態vN，同時將信號reqN置為低，對握手操作進行復位；
(4)MN+1i接收來自MN的復位請求reqN+1i-，然後將信號ackN+1i置為低，加以確認；
(5)MN接收來自MN+1i的應答信號ackN+，回到狀態dN，同時再次將信號reqN置為高，進行新的通訊。
5.如權利要求1所述的一種猝發模式異步控制電路設計方法，其特徵在於所述接口狀態機的設計方法是
(1)確定接口狀態機的輸入輸出信號接口狀態機與MN，MN+11，…MN+1L相連接，輸入信號包括猝發輸入BIN，BIN+11，…，BIN+1L、子狀態機MN的請求信號reqN以及子狀態機MN+11，…，MN+1L相應的應答信號axkN+11，…，ackN+1L；輸出信號包括子狀態機MN的應答信號ackN、子狀態機MN+11，…，MN+1L相應的請求信號reqN+11，…，reqN+1L以及輔助信號pseu；
(2)確定接口狀態機狀態節點的數目當N＝1時，接口狀態機僅需要解決MN+11，…，MN+1L之間的觸發仲裁問題，此時需要3L+1個狀態節點，記為dN，v11，…，vL1，v12，…，vL2，v13，…，vL3；當1＜N＜K時，接口狀態機不僅需要解決MN+11，…，MN+1L之間的觸發仲裁問題，而且需要解決MN與MN+11，…，MN+1L之間的觸發仲裁問題，此時需要3L+3個狀態節點，記為dN，v01，v11，…，vL1，v02，v12，…，vL2，v13，…，vL3。
(3)確定狀態節點之間的有向邊及其對應的猝發輸入/猝發輸出變遷
a)有向邊，對應的猝發輸入變遷為reqN+，transi(eN)，猝發輸出變遷為pseu+；有向邊，對應的猝發輸入變遷為reqN-，猝發輸出變遷為pseu-；有向邊，對應的猝發輸入變遷為
；對於任意信號x∈BIN，如果x+∈transi(eN)，則，如果x-∈transi(eN)，則
b)對於任意i＝1，…，L，有向邊，對應的猝發輸入變遷為reqN+，transi(eN+1i)，猝發輸出變遷為reqN+1i+；有向邊，對應的猝發輸入變遷為ackN+1i+，猝發輸出變遷為ackN+；有向邊，對應的猝發輸入變遷為reqN-，
，猝發輸出變遷為reqN+1i-；有向邊，
對應的猝發輸入變遷為ackN+1i-，猝發輸出變遷為ackN-。
6.如權利要求1或5所述的一種猝發模式異步控制電路設計方法，其特徵在於所述接口狀態機對子狀態機是否觸發進行仲裁的方法是
(1)如果猝發輸入變遷reqN+，transi(eN+1i)先有效，那麼接口狀態機進入狀態vi1，選擇觸發第N+1級子狀態機MN+1i，具體過程為
a)接口狀態機接收來自MN的仲裁請求reqN+，當猝發輸入變遷transi(eN)有效時進入狀態vi1，同時將信號reqN+1i置為高，請求觸發MN+1i；
b)MN+1i接收來自狀態機的觸發請求reqN+1i+，將信號ackN+1i置為高，對觸發請求加以確認；
c)接口狀態機接收來自MN+1i的應答信號ackN+1i+，進入狀態vi2，同時將信號ackN置為高，對仲裁請求加以確認；
d)MN接收來自接口狀態機的應答信號ackN+，進入狀態vN，同時將reqN置為低，對仲裁請求進行復位；
e)接口狀態機接收來自MN的仲裁復位請求reqN-，進入狀態vi3，同時將reqN+1i置為低，對觸發請求進行復位；
f)MN+1i接收來自接口狀態機的觸發復位請求reqN+1i-，等待相應的猝發輸入變遷有效，然後進入狀態dN，同時將信號ackN+1i置為低，對觸發復位加以確認；
g)接口狀態機接收來自MN+1i的應答信號ackN+1i-，回到狀態dN，同時將信號ackN置為低，對仲裁復位加以確認；
h)MN接收來自接口狀態機的應答信號ackN+，回到狀態dN，同時再次將信號reqN置為高，進行新的仲裁；
(2)如果猝發輸入變遷reqN+，transi(eN)先有效，那麼接口狀態機進入狀態v01，選擇繼續運行MN，具體過程為
a)接口狀態機接收來自MN的仲裁請求reqN+，當猝發輸入變遷transi(eN+1i)有效時進入狀態v01，同時將信號pseu置為高；
b)MN接收來自接口狀態機的輔助信號變遷pseu+，然後將reqN置為低進行復位；
c)接口狀態機接收復位請求reqN-，進入狀態v02，同時將信號pseu置為低；
d)MN接收來自接口狀態機的輔助信號變遷pseu-等待相應的猝發輸入變遷有效，進而繼續運行；
e)接口狀態機等待相應的猝發輸入變遷有效，然後回到狀態dN，等待新的仲裁請求。
7.如權利要求1所述的一種猝發模式異步控制電路設計方法，其特徵在於所述對第2級到第K-1級的所有猝發模式子狀態機MN再次調整的方法為
(1)刪除有向邊及其相應的猝發輸入變遷transi(eN)和猝發輸出變遷transo(eN)；dN為MN中除起始狀態節點之外的判定節點，vc為除輔助狀態節點vN以外與dN通過有向邊連接的節點；有向邊對應的猝發輸出變遷reqN-，有向邊eN＝所對應的猝發輸入變遷和猝發輸出變遷分別為transi(eN)和transo(eN)；
(2)增加額外的狀態節點v，設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為pseu+和reqN-；設定有向邊對應的猝發輸入變遷和猝發輸出變遷分別為pseu-，transi(eN)和transo(eN)。
8.如權利要求5所述的一種猝發模式異步控制電路設計方法，其特徵在於連接第一級子狀態機和第二級子狀態機的接口狀態機不輸出輔助信號pseu。
全文摘要
本發明公開了一種猝發模式異步控制電路設計方法，要解決的技術問題是提高設計規模，使大規模猝發模式異步控制電路實用化。技術方案是利用猝發模式狀態機M所對應有向圖的有向迴路集合對M進行層次化分解；增加額外的請求/應答信號，對第1級至第K級所有的猝發模式子狀態機進行調整；設計猝發模式接口狀態機，對子狀態機是否觸發進行仲裁；再次調整第2級到第K-1級的所有猝發模式子狀態機；實現子控制電路模塊和接口控制電路模塊；合成猝發模式異步控制電路。採用本發明可對狀態機進行層次化分解，分解效率高，處理規模大；可解決各子狀態機之間的仲裁問題，設計方法簡單；可有效去除各子狀態機之間的時序約束要求，降低邏輯綜合的難度。
文檔編號G06F17/50GK101149763SQ20071003605
公開日2008年3月26日 申請日期2007年11月6日 優先權日2007年11月6日
發明者王志英, 堅 阮, 蕾 王, 葵 戴, 勇 李, 銳 龔, 鋼 晉, 李雲照 申請人:中國人民解放軍國防科學技術大學