針對狀態機的綜合優化策略

有限狀態機及其設計技術是數字系統設計中的重要組成部分，是實現高效率、高可靠性邏輯控制的重要途徑。大部分數字系統都可以劃分為控制單元和數據單元兩個組成部分。通常，控制單元的主體是一個狀態機，它接收外部信號以及數據單元產生的狀態信息，產生控制信號序列。狀態機性能的好壞對系統性能有較大的影響。良好的狀態機的實現不僅與狀態機的設計有關，而且與采用的綜合策略密切相關，不同的綜合策略對最終實現的狀態機的性能有很大的影響。

　　Synopsys公司的DC （Design Compiler，設計編譯程序）提供了針對狀態機的綜合優化策略，這個過程既可以完全自動進行，也可以手工進行。本文論述了兩種綜合策略的實現。

　　1　狀態機的基礎描述

　　從數學的角度看，有限狀態機可以表示為一個五元組M = （I， O， S，δ，λ） 。其中： I和O 分別表示輸入、輸出量; S 為狀態向量;δ為次態方程（δ： S ×I） ;λ為輸出方程（λ： S ×I） 。

　　從實際狀態機的實現角度出發，根據輸出方程，有限狀態機可以分為3類：

　　a） 輸出是狀態向量和輸入的函數———Mealy型狀態機（λ： S ×I →O ） ;

　　b） 輸出僅是狀態向量的函數———Moore 型狀態機（λ： S →O ） ;

　　c） 輸出等于狀態向量———狀態輸出型狀態機（λ： S = O ） 。

　　在實際中最常用的狀態機是Mealy型和Moore型狀態機。

　　從電路的角度看，有限狀態機是由觸發器、寄存器和組合邏輯組合成的系統，圖1展示了有限狀態機的一般結構：一組保存狀態向量的觸發器，產生次狀態和輸出的組合邏輯。

圖1　有限狀態機一般結構

　　1.1　狀態表

　　為了采用DC的有限狀態機優化策略，必須首先把原始的狀態機轉換為用DC狀態表描述的格式，這種轉換可以自動完成，也可以手動完成。Synopsys的狀態表提供了一種簡單的、獨立于工藝的有限狀態機描述方式。下面是一個狀態表的例子

　　# State table body

　　Input PresentNextOutput

　　Value State State Values

　　0 RESET RESET 00

　　1 RESET STATE1 01

　　0 STATE1 RESET 10

　　1 STATE1 STATE1 11

　　# Preferred state encoding

　　.encoding

　　RESET 2#00

　　STATE1 2#01

　　狀態表的主體由行組成，每一行描述狀態機的一個特定的狀態轉換。每行有4列：輸入值，當前態，次態，輸出值。有的輸入可以引發狀態轉換，有的則不會。從狀態表可以很容易看出狀態機的轉換行為。狀態表還可以包含一個可選的部分，用于給出首選的狀態編碼，這些狀態編碼可以以十進制、二進制或者十六進制給出。

　　例子中的狀態表包括： 1個輸入; 2個狀態，即RESET和STATE1; 4種輸出，即RESET和STATE1分別編碼為0 和1。RESET態只在輸入為1 時轉換到STATE1態，輸出變為01，而STATE1態只在輸入為0時轉換到RESET態，輸出變為10。

　　例子中所有可能的輸入輸出和狀態組合都被用到了，如果狀態機用到的狀態少于可用的編碼，便可以創建只包含所需要使用的狀態轉換的狀態表，其他未指明的狀態則按不關心態處理。

　　1.2　狀態向量

　　狀態向量是描述狀態機的元素之一，是通過觸發器實例名稱的有序列表來指定的。指定的觸發器存儲了有序的位模式，這些位模式定義了有限狀態機在任何給定時刻的當前狀態。一個特定的觸發器位模式與一個狀態相對應。例如， ff1、ff2、ff3是觸發器的實例名稱，則列表{ ff1 ff2 ff3}定義了一個3位的狀態向量，這個狀態向量可以表示不多于8個狀態的有限狀態機。

　　1.3　狀態編碼

　　狀態編碼是描述狀態機的另一個元素。有限狀態機的狀態編碼用符號定義了狀態機的所有合法狀態的位編碼。編碼確定哪些狀態向量的位模式代表合法狀態，哪些位模式可以當作不關心態。不關心態提高了工具達到好的優化結果的可能性。大多數以HDL （硬件描述語言）或狀態表給出的設計，DC可以直接從代碼中提取出狀態編碼。在工具不能得到狀態編碼時要使用命令set_fsm_encoding來手動建立狀態編碼。對于以其他形式給出的設計，必須使用命令set_fsm_encoding手工建立狀態編碼。

　　1.4　編碼風格

　　DC在優化中可以使用one2hot （單狀態） 、二進制、格雷碼和自動編碼4種類型中的一種來分派狀態機的狀態。不同的編碼風格可以導致具有很大差異的優化結果。

　　One2hot風格編碼使用與狀態機狀態數相等的位來編碼狀態，每一個狀態的編碼只有1位是1，其余各位都是0，所以這種編碼方式需要與狀態數相等數目的觸發器。這種編碼方式簡化了組合邏輯，可以獲得最快的速度，但同時會大大增加設計的面積。二進制和格雷碼編碼方式按照一定的順序用二進制序列或者格雷碼序列來表示狀態機的狀態，這兩種編碼方式可以降低所需的觸發器的數目，但速度不及one2hot編碼方式。自動編碼方式使用一種隨機的風格產生狀態編碼，這種編碼能在使用最短編碼長度的情況下最大限度地降低組合邏輯的復雜度。采用什么樣的編碼風格，要根據設計需要進行選擇。

　　2　狀態機優化策略及實施

　　狀態機的優化包括兩步，首先是提取狀態機邏輯，然后是優化基于內部狀態表表示的狀態機。這個過程既可以完全自動進行，也可以手工進行。自動優化策略需要DC2Ultra的許可證（license） ，手動優化策略需要DC2Expert的許可證。

　　2.1　基于DC Ultra的自動優化策略

　　自動優化策略由讀和編譯兩個階段組成。

　　a） 讀階段：讀進HDL或者以狀態表描述的設計;自動偵測狀態機的觸發器;標明狀態機的狀態向量和狀態編碼特性。

　　b） 編譯階段：重新劃分包含狀態機的設計層次;從劃分后的設計中提取狀態機;確定編碼風格;如果可能，減小轉態數;分派狀態;基于狀態機的邏輯網表產生DC內部數據結構的狀態分派;展平新創建的設計層次;繼續其他DC優化步驟。

　　圖2是自動優化的流程，其中列出了不同的可選命令，可以根據不同的設計進行取舍。

圖2　基于DC Ultra的有限狀態機自動優化流程

　　2.2　基于DC2Expert的手動優化策略

　　當輸入設計文件不是以HDL描述的，或者DC不能從HDL文件中自動識別出狀態機時，就要采用手動優化策略。

　　圖3為手動優化策略的基本流程，其中展示了使用的命令、描述狀態機的狀態表和網表之間的關系。

圖3　FSM 手機優化命令算法

　　從圖3中可以看出，手動優化包括網表生成、狀態表提取、基于狀態表的優化和網表映射4 個階段。Compile命令基于輸入的HDL 文件生成網表， Extract命令基于網表生成狀態表， Compile命令再基于狀態機優化的狀態表生成映射的網表?？蛇x命令reduce_fsm和minimize_fsm基于狀態表操作， reduce _fsm試圖降低狀態機相關的組合邏輯的復雜度， minimize_fsm則試圖減少狀態數目。

　　手動優化包含如下步驟：

　?。╞）將設計讀入DC。

　　如果設計不是以狀態表格式給出的，按如下步驟提取狀態表：

　　運行comp ile2map_effort low得到一個輸入文件的網表;

　　根據需要使用set_fsm_state_vector指定狀態向量;

　　使用group2fsm 將狀態機邏輯劃分到一個單獨的模塊，并將該模塊設為當前設計;

　　使用set_fsm_encoding分派狀態機狀態;

　　使用extract從設計中提取狀態機邏輯;

　　根據需要使用reduce_fsm降低狀態機相關的組合邏輯的復雜度;

　　根據需要使用minimize_fsm，則試圖減少狀態數目;使用minimize_fsm，則試圖減少狀態數目。

　　c） 根據需要選用適當的命令，修改基于狀態表的狀態機的屬性，如狀態向量、狀態編碼、編碼風格等。

　　d） 指定電路級約束條件和屬性。

　　e） 編譯整個設計。

圖4是提取狀態機的流程。

圖5是基于狀態表的優化流程?！　?/p>

　　3　應注意的問題

　　并非所有的有限狀態機都可以使用本文所介紹的優化策略，原始的設計文件應該滿足下列條件：

　　a） 所有的端口應該僅為輸入或者輸出端口，不支持輸入輸出端口。

　　b） 當一個模塊中有多個狀態機時，每次編譯時只能提取出1個狀態機，而提取哪個狀態機是隨機的，所以推薦每個模塊僅包含1個有限狀態機。

　　c） 狀態機只能包含1個時鐘。

　　4　結束語

　　采用本文介紹的優化策略，在不改變源代碼的前提下，較之標準編譯過程可以有效地提高狀態機的性能。但因為在優化過程中特別是手動優化過程中對狀態重新進行了編碼，如果新的編碼與原來的編碼不一致，會導致邏輯錯誤，所以在使用這一策略時還要輔以其他手段進行邏輯驗證。