針對(duì)狀態(tài)機(jī)的綜合優(yōu)化策略

有限狀態(tài)機(jī)及其設(shè)計(jì)技術(shù)是數(shù)字系統(tǒng)設(shè)計(jì)中的重要組成部分，是實(shí)現(xiàn)高效率、高可靠性邏輯控制的重要途徑。大部分?jǐn)?shù)字系統(tǒng)都可以劃分為控制單元和數(shù)據(jù)單元兩個(gè)組成部分。通常，控制單元的主體是一個(gè)狀態(tài)機(jī)，它接收外部信號(hào)以及數(shù)據(jù)單元產(chǎn)生的狀態(tài)信息，產(chǎn)生控制信號(hào)序列。狀態(tài)機(jī)性能的好壞對(duì)系統(tǒng)性能有較大的影響。良好的狀態(tài)機(jī)的實(shí)現(xiàn)不僅與狀態(tài)機(jī)的設(shè)計(jì)有關(guān)，而且與采用的綜合策略密切相關(guān)，不同的綜合策略對(duì)最終實(shí)現(xiàn)的狀態(tài)機(jī)的性能有很大的影響。

　　Synopsys公司的DC （Design Compiler，設(shè)計(jì)編譯程序）提供了針對(duì)狀態(tài)機(jī)的綜合優(yōu)化策略，這個(gè)過(guò)程既可以完全自動(dòng)進(jìn)行，也可以手工進(jìn)行。本文論述了兩種綜合策略的實(shí)現(xiàn)。

　　1　狀態(tài)機(jī)的基礎(chǔ)描述

　　從數(shù)學(xué)的角度看，有限狀態(tài)機(jī)可以表示為一個(gè)五元組M = （I， O， S，δ，λ） 。其中： I和O 分別表示輸入、輸出量; S 為狀態(tài)向量;δ為次態(tài)方程（δ： S ×I） ;λ為輸出方程（λ： S ×I） 。

　　從實(shí)際狀態(tài)機(jī)的實(shí)現(xiàn)角度出發(fā)，根據(jù)輸出方程，有限狀態(tài)機(jī)可以分為3類：

　　a） 輸出是狀態(tài)向量和輸入的函數(shù)———Mealy型狀態(tài)機(jī)（λ： S ×I →O ） ;

　　b） 輸出僅是狀態(tài)向量的函數(shù)———Moore 型狀態(tài)機(jī)（λ： S →O ） ;

　　c） 輸出等于狀態(tài)向量———狀態(tài)輸出型狀態(tài)機(jī)（λ： S = O ） 。

　　在實(shí)際中最常用的狀態(tài)機(jī)是Mealy型和Moore型狀態(tài)機(jī)。

　　從電路的角度看，有限狀態(tài)機(jī)是由觸發(fā)器、寄存器和組合邏輯組合成的系統(tǒng)，圖1展示了有限狀態(tài)機(jī)的一般結(jié)構(gòu)：一組保存狀態(tài)向量的觸發(fā)器，產(chǎn)生次狀態(tài)和輸出的組合邏輯。

圖1　有限狀態(tài)機(jī)一般結(jié)構(gòu)

　　1.1　狀態(tài)表

　　為了采用DC的有限狀態(tài)機(jī)優(yōu)化策略，必須首先把原始的狀態(tài)機(jī)轉(zhuǎn)換為用DC狀態(tài)表描述的格式，這種轉(zhuǎn)換可以自動(dòng)完成，也可以手動(dòng)完成。Synopsys的狀態(tài)表提供了一種簡(jiǎn)單的、獨(dú)立于工藝的有限狀態(tài)機(jī)描述方式。下面是一個(gè)狀態(tài)表的例子

　　# 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

　　狀態(tài)表的主體由行組成，每一行描述狀態(tài)機(jī)的一個(gè)特定的狀態(tài)轉(zhuǎn)換。每行有4列：輸入值，當(dāng)前態(tài)，次態(tài)，輸出值。有的輸入可以引發(fā)狀態(tài)轉(zhuǎn)換，有的則不會(huì)。從狀態(tài)表可以很容易看出狀態(tài)機(jī)的轉(zhuǎn)換行為。狀態(tài)表還可以包含一個(gè)可選的部分，用于給出首選的狀態(tài)編碼，這些狀態(tài)編碼可以以十進(jìn)制、二進(jìn)制或者十六進(jìn)制給出。

　　例子中的狀態(tài)表包括： 1個(gè)輸入; 2個(gè)狀態(tài)，即RESET和STATE1; 4種輸出，即RESET和STATE1分別編碼為0 和1。RESET態(tài)只在輸入為1 時(shí)轉(zhuǎn)換到STATE1態(tài)，輸出變?yōu)?1，而STATE1態(tài)只在輸入為0時(shí)轉(zhuǎn)換到RESET態(tài)，輸出變?yōu)?0。

　　例子中所有可能的輸入輸出和狀態(tài)組合都被用到了，如果狀態(tài)機(jī)用到的狀態(tài)少于可用的編碼，便可以創(chuàng)建只包含所需要使用的狀態(tài)轉(zhuǎn)換的狀態(tài)表，其他未指明的狀態(tài)則按不關(guān)心態(tài)處理。

　　1.2　狀態(tài)向量

　　狀態(tài)向量是描述狀態(tài)機(jī)的元素之一，是通過(guò)觸發(fā)器實(shí)例名稱的有序列表來(lái)指定的。指定的觸發(fā)器存儲(chǔ)了有序的位模式，這些位模式定義了有限狀態(tài)機(jī)在任何給定時(shí)刻的當(dāng)前狀態(tài)。一個(gè)特定的觸發(fā)器位模式與一個(gè)狀態(tài)相對(duì)應(yīng)。例如， ff1、ff2、ff3是觸發(fā)器的實(shí)例名稱，則列表{ ff1 ff2 ff3}定義了一個(gè)3位的狀態(tài)向量，這個(gè)狀態(tài)向量可以表示不多于8個(gè)狀態(tài)的有限狀態(tài)機(jī)。

　　1.3　狀態(tài)編碼

　　狀態(tài)編碼是描述狀態(tài)機(jī)的另一個(gè)元素。有限狀態(tài)機(jī)的狀態(tài)編碼用符號(hào)定義了狀態(tài)機(jī)的所有合法狀態(tài)的位編碼。編碼確定哪些狀態(tài)向量的位模式代表合法狀態(tài)，哪些位模式可以當(dāng)作不關(guān)心態(tài)。不關(guān)心態(tài)提高了工具達(dá)到好的優(yōu)化結(jié)果的可能性。大多數(shù)以HDL （硬件描述語(yǔ)言）或狀態(tài)表給出的設(shè)計(jì)，DC可以直接從代碼中提取出狀態(tài)編碼。在工具不能得到狀態(tài)編碼時(shí)要使用命令set_fsm_encoding來(lái)手動(dòng)建立狀態(tài)編碼。對(duì)于以其他形式給出的設(shè)計(jì)，必須使用命令set_fsm_encoding手工建立狀態(tài)編碼。

　　1.4　編碼風(fēng)格

　　DC在優(yōu)化中可以使用one2hot （單狀態(tài)） 、二進(jìn)制、格雷碼和自動(dòng)編碼4種類型中的一種來(lái)分派狀態(tài)機(jī)的狀態(tài)。不同的編碼風(fēng)格可以導(dǎo)致具有很大差異的優(yōu)化結(jié)果。

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

　　2　狀態(tài)機(jī)優(yōu)化策略及實(shí)施

　　狀態(tài)機(jī)的優(yōu)化包括兩步，首先是提取狀態(tài)機(jī)邏輯，然后是優(yōu)化基于內(nèi)部狀態(tài)表表示的狀態(tài)機(jī)。這個(gè)過(guò)程既可以完全自動(dòng)進(jìn)行，也可以手工進(jìn)行。自動(dòng)優(yōu)化策略需要DC2Ultra的許可證（license） ，手動(dòng)優(yōu)化策略需要DC2Expert的許可證。

　　2.1　基于DC Ultra的自動(dòng)優(yōu)化策略

　　自動(dòng)優(yōu)化策略由讀和編譯兩個(gè)階段組成。

　　a） 讀階段：讀進(jìn)HDL或者以狀態(tài)表描述的設(shè)計(jì);自動(dòng)偵測(cè)狀態(tài)機(jī)的觸發(fā)器;標(biāo)明狀態(tài)機(jī)的狀態(tài)向量和狀態(tài)編碼特性。

　　b） 編譯階段：重新劃分包含狀態(tài)機(jī)的設(shè)計(jì)層次;從劃分后的設(shè)計(jì)中提取狀態(tài)機(jī);確定編碼風(fēng)格;如果可能，減小轉(zhuǎn)態(tài)數(shù);分派狀態(tài);基于狀態(tài)機(jī)的邏輯網(wǎng)表產(chǎn)生DC內(nèi)部數(shù)據(jù)結(jié)構(gòu)的狀態(tài)分派;展平新創(chuàng)建的設(shè)計(jì)層次;繼續(xù)其他DC優(yōu)化步驟。

　　圖2是自動(dòng)優(yōu)化的流程，其中列出了不同的可選命令，可以根據(jù)不同的設(shè)計(jì)進(jìn)行取舍。

圖2　基于DC Ultra的有限狀態(tài)機(jī)自動(dòng)優(yōu)化流程

　　2.2　基于DC2Expert的手動(dòng)優(yōu)化策略

　　當(dāng)輸入設(shè)計(jì)文件不是以HDL描述的，或者DC不能從HDL文件中自動(dòng)識(shí)別出狀態(tài)機(jī)時(shí)，就要采用手動(dòng)優(yōu)化策略。

　　圖3為手動(dòng)優(yōu)化策略的基本流程，其中展示了使用的命令、描述狀態(tài)機(jī)的狀態(tài)表和網(wǎng)表之間的關(guān)系。

圖3　FSM 手機(jī)優(yōu)化命令算法

　　從圖3中可以看出，手動(dòng)優(yōu)化包括網(wǎng)表生成、狀態(tài)表提取、基于狀態(tài)表的優(yōu)化和網(wǎng)表映射4 個(gè)階段。Compile命令基于輸入的HDL 文件生成網(wǎng)表， Extract命令基于網(wǎng)表生成狀態(tài)表， Compile命令再基于狀態(tài)機(jī)優(yōu)化的狀態(tài)表生成映射的網(wǎng)表?？蛇x命令reduce_fsm和minimize_fsm基于狀態(tài)表操作， reduce _fsm試圖降低狀態(tài)機(jī)相關(guān)的組合邏輯的復(fù)雜度， minimize_fsm則試圖減少狀態(tài)數(shù)目。

　　手動(dòng)優(yōu)化包含如下步驟：

　　（b）將設(shè)計(jì)讀入DC。

　　如果設(shè)計(jì)不是以狀態(tài)表格式給出的，按如下步驟提取狀態(tài)表：

　　運(yùn)行comp ile2map_effort low得到一個(gè)輸入文件的網(wǎng)表;

　　根據(jù)需要使用set_fsm_state_vector指定狀態(tài)向量;

　　使用group2fsm 將狀態(tài)機(jī)邏輯劃分到一個(gè)單獨(dú)的模塊，并將該模塊設(shè)為當(dāng)前設(shè)計(jì);

　　使用set_fsm_encoding分派狀態(tài)機(jī)狀態(tài);

　　使用extract從設(shè)計(jì)中提取狀態(tài)機(jī)邏輯;

　　根據(jù)需要使用reduce_fsm降低狀態(tài)機(jī)相關(guān)的組合邏輯的復(fù)雜度;

　　根據(jù)需要使用minimize_fsm，則試圖減少狀態(tài)數(shù)目;使用minimize_fsm，則試圖減少狀態(tài)數(shù)目。

　　c） 根據(jù)需要選用適當(dāng)?shù)拿?，修改基于狀態(tài)表的狀態(tài)機(jī)的屬性，如狀態(tài)向量、狀態(tài)編碼、編碼風(fēng)格等。

　　d） 指定電路級(jí)約束條件和屬性。

　　e） 編譯整個(gè)設(shè)計(jì)。

圖4是提取狀態(tài)機(jī)的流程。

圖5是基于狀態(tài)表的優(yōu)化流程。　　

　　3　應(yīng)注意的問題

　　并非所有的有限狀態(tài)機(jī)都可以使用本文所介紹的優(yōu)化策略，原始的設(shè)計(jì)文件應(yīng)該滿足下列條件：

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

　　b） 當(dāng)一個(gè)模塊中有多個(gè)狀態(tài)機(jī)時(shí)，每次編譯時(shí)只能提取出1個(gè)狀態(tài)機(jī)，而提取哪個(gè)狀態(tài)機(jī)是隨機(jī)的，所以推薦每個(gè)模塊僅包含1個(gè)有限狀態(tài)機(jī)。

　　c） 狀態(tài)機(jī)只能包含1個(gè)時(shí)鐘。

　　4　結(jié)束語(yǔ)

　　采用本文介紹的優(yōu)化策略，在不改變?cè)创a的前提下，較之標(biāo)準(zhǔn)編譯過(guò)程可以有效地提高狀態(tài)機(jī)的性能。但因?yàn)樵趦?yōu)化過(guò)程中特別是手動(dòng)優(yōu)化過(guò)程中對(duì)狀態(tài)重新進(jìn)行了編碼，如果新的編碼與原來(lái)的編碼不一致，會(huì)導(dǎo)致邏輯錯(cuò)誤，所以在使用這一策略時(shí)還要輔以其他手段進(jìn)行邏輯驗(yàn)證。