[發明專利]一種狀態機可拼接性和拼接規則判定方法和裝置

在審

• 申請號: 201410836240.5
• 申請日: 2014-12-26
• 公開（公告）號: CN104572029A
• 公開（公告）日: 2015-04-29
• 發明（設計）人: 王磊;楊磊;謝少林
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06F9/38
• 分類號: G06F9/38;G06F9/46
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 宋焰琴

技術領域

本發明涉及數字集成電路領域，更具體地涉及一種狀態機可拼接性和拼接規則判定方法和裝置。

背景技術

動態可重配流水線技術使得硬件電路結構更加靈活可控，其本質是用程序描述流水線上各個狀態機的行為。狀態機對應于電路中各個功能單元，通過編程設計和配置狀態機可以方便的操控硬件資源。然后，電路較為復雜時，狀態機的設計和配置就變得極其復雜。

然而，當硬件需要執行較為復雜的操作或實現較為復雜的算法時，不同狀態機的行為會變得復雜而多樣，此時狀態機拼接的情況就會極為復雜，可能面臨不同類型狀態機難以拼接、甚至不能拼接的情況。此時，如何從理論上分析狀態機的可拼接性，識別出可以直接拼接、或者經過等價變換即可拼接的類型，以及提示不能拼接的狀態機類型，就變得很關鍵。

發明內容

有鑒于此，本發明的主要目的在于提出一種狀態機等價變換判定方法，從理論上系統全面地分析拼接過程中狀態塊的可拼接性，并且分析各種情況狀態塊的拼接規則和等價變換規則，以便于應對各種狀態機拼接情況。

為了實現上述目的，作為本發明的一個方面，本發明提供了一種狀態機可拼接性和拼接規則判定方法，包括以下步驟：

步驟1，進行初始化，將當前狀態置為空狀態；

步驟2，從待拼接狀態塊隊列中讀取一個狀態塊，根據該狀態塊的類型和當前狀態判斷該狀態的處理方法，修改當前狀態，并跳轉到相應規則的步驟中；

步驟3，判斷全順序塊的拼接規則，保持當前狀態為全順序狀態，跳至步驟2；

步驟4，判斷全循環塊的拼接規則，保持當前狀態為全循環狀態，且讀入的狀態塊為循環塊，調用步驟6進行長度比較：

若步驟6返回長度相同，且比較的左右循環塊循環次數相同，則保持當前狀態為全循環狀態，跳至步驟2；

若步驟6返回長度相同，且比較的左右循環塊循環次數不同，則輸出等價變換規則，方法結束；

若步驟6返回結果不同信息，則輸出不可拼接，該方法結束；

步驟5，判斷全嵌套循環塊的拼接規則，保持當前狀態為全嵌套循環狀態，且讀入的狀態塊為嵌套循環塊，調用步驟6進行長度比較：

若步驟6返回長度相同，且比較的左右嵌套循環塊循環次數相同，則保持當前狀態為全嵌套循環狀態，跳至步驟2；

若步驟6返回長度相同，且比較的左右嵌套循環塊循環次數不同，則輸出等價變換規則，方法結束；

若步驟6返回長度不同，則輸出不可拼接，該方法結束；

步驟6，確定輸入的兩個循環塊或兩個嵌套循環塊長度是否一致。

其中，步驟2中所述根據該狀態塊的類型和當前狀態判斷該狀態的處理方法，修改當前狀態，并跳轉到相應規則的步驟中的步驟包括：

若當前狀態為空狀態：

若讀取的狀態塊為順序塊，置當前狀態為全順序狀態，重新開始步驟2；

若該狀態塊為循環塊，置當前狀態為全循環狀態，記錄當前循環塊的循環長度，重新開始步驟2；

若該狀態塊為嵌套循環塊，置當前狀態為全嵌套循環狀態，記錄當前循環塊的循環長度，重新開始步驟2；

若當前狀態為全順序狀態：

若讀取的狀態塊為順序塊，則跳轉到步驟3；

若讀取的狀態塊為循環塊或嵌套循環塊，則修改當前狀態為非全順序狀態，輸出等價變換規則，該方法結束；

若當前狀態為全循環狀態：

若讀取的狀態塊為循環塊，則跳轉到步驟4；

若讀取的狀態塊為順序塊，則修改當前狀態為非全順序狀態，輸出等價變換規則，該方法結束；

若讀取的狀態塊為嵌套循環塊，則修改當前狀態為非全循環狀態，輸出等價變換規則，該方法結束；

若當前狀態為全嵌套循環狀態：

若讀取的狀態塊為嵌套循環塊，則跳轉到步驟5；

若讀取的狀態塊為順序塊，則修改當前狀態為非全順序狀態，輸出等價變換規則，該方法結束；

若讀取的狀態塊為循環塊，則修改當前狀態為非全循環狀態，輸出等價變換規則，該方法結束；

若讀取待判定狀態塊隊列為空，且當前狀態為全順序狀態、全循環狀態或全嵌套循環狀態，則輸出可拼接規則，該方法結束。

其中，步驟6中所述長度與循環體長度、總循環次數和已循環次數相關，表示為：長度＝循環體長度×(總循環次數-已循環次數)。

其中，步驟6中所述確定輸入的兩個循環塊或兩個嵌套循環塊長度是否一致的步驟包括：