FPGA設(shè)計(jì)中狀態(tài)機(jī)安全性研究

楊宏亮，金炎勝，王剛毅

（1.穆棱卷煙廠，黑龍江穆棱157500; 2.哈爾濱工業(yè)大學(xué)電子與信息工程學(xué)院，黑龍江哈爾濱150001）

隨著EDA技術(shù)的不斷發(fā)展，F(xiàn)PGA在各個(gè)領(lǐng)域都得到了廣泛的應(yīng)用，而在這些FPGA應(yīng)用中，絕大部分都使用到狀態(tài)機(jī)的方法，狀態(tài)機(jī)對(duì)于每個(gè)各自的設(shè)計(jì)都起著至關(guān)重要的作用，一旦狀態(tài)機(jī)出現(xiàn)卡死，也就是出現(xiàn)了通常說(shuō)的“狀態(tài)機(jī)跑飛”現(xiàn)象，整個(gè)設(shè)計(jì)將無(wú)法繼續(xù)工作。鑒于狀態(tài)機(jī)的設(shè)計(jì)的重要性，有必要對(duì)狀態(tài)機(jī)的安全性進(jìn)行深入的研究。

本文的研究?jī)?nèi)容如下：首先，從狀態(tài)機(jī)編碼討論狀態(tài)機(jī)出現(xiàn)卡死的可能性；然后，詳細(xì)分析狀態(tài)機(jī)“跑飛”現(xiàn)象的原因，并提供幾種解決狀態(tài)機(jī)“跑飛”問(wèn)題的方法；最后，深入研究了EDA工具軟件Quartus II中“Safe State Machine”選項(xiàng)選中后對(duì)狀態(tài)機(jī)電路帶來(lái)的影響。

1 導(dǎo)致?tīng)顟B(tài)機(jī)“跑飛”現(xiàn)象的原因分析

1.1 狀態(tài)機(jī)編碼問(wèn)題

在對(duì)狀態(tài)機(jī)進(jìn)行編碼的時(shí)候，總是不可避免地會(huì)出現(xiàn)大量的剩余狀態(tài)[1]，即未被定義的編碼組合，這些編碼組合由于在狀態(tài)機(jī)正常運(yùn)行時(shí)是不需要出現(xiàn)的，所以通常被稱為非法狀態(tài)。

正是由于非法狀態(tài)的存在，為狀態(tài)機(jī)跑飛現(xiàn)象提供了可能性。

1.2 惡劣工作環(huán)境的影響

這個(gè)原因比較容易理解，如果最后的產(chǎn)品工作環(huán)境比較惡劣，比如工作在太空中，眾所周知，太空中存在著各種粒子，受輻射程度很高，F(xiàn)PGA中的存儲(chǔ)單元就有可能因?yàn)槭艿礁鞣N粒子的撞擊而改變其中存儲(chǔ)的值[1]。如果狀態(tài)機(jī)中的狀態(tài)存儲(chǔ)器中的一位突然改變了，那么狀態(tài)機(jī)就有可能進(jìn)入到非法狀態(tài)。例如：一個(gè)3個(gè)工作狀態(tài)采用One-hot編碼的狀態(tài)機(jī)，其合法編碼組合為“001”，“010”，“100”。如果在狀態(tài)“001”時(shí)，突然其中一位受到影響而翻轉(zhuǎn)了，變成了“101”，現(xiàn)在顯然就進(jìn)入了非法狀態(tài)，如果沒(méi)有相應(yīng)的補(bǔ)救措施，這個(gè)狀態(tài)機(jī)就會(huì)卡死。

1.3 狀態(tài)機(jī)中有異步輸入

也就是說(shuō)狀態(tài)機(jī)如何跳轉(zhuǎn)不僅僅受當(dāng)前狀態(tài)的影響，還受異步輸入的控制。為方便分析，舉一個(gè)帶異步輸入實(shí)例，其狀態(tài)轉(zhuǎn)換圖如圖1所示。

圖1 一個(gè)簡(jiǎn)單的狀態(tài)轉(zhuǎn)換圖Fig.1 A simple state transition diagram

根據(jù)這個(gè)轉(zhuǎn)換圖，很容易用狀態(tài)機(jī)來(lái)實(shí)現(xiàn)，下面是一個(gè)簡(jiǎn)單的VHDL程序狀態(tài)機(jī)實(shí)現(xiàn)部分：

在上述代碼中，sidle，srun，send表示 ST1，ST2，ST3三個(gè)工作狀態(tài)，‘a(chǎn)’為異步輸入。用Quartus II對(duì)上面代碼進(jìn)行綜合，可以得到狀態(tài)機(jī)部分電路如圖2所示。

圖2 綜合的狀態(tài)機(jī)電路圖Fig.2 Quartus II integrated circuit of state machine

從狀態(tài)轉(zhuǎn)換方程中可以看出有兩個(gè)觸發(fā)器次態(tài)跟異步輸入‘a(chǎn)’有關(guān)，分別為D1和D3。當(dāng)a發(fā)生變化時(shí)，D1和D3的值也會(huì)隨之發(fā)生相應(yīng)的改變。在時(shí)鐘clk上升沿到來(lái)時(shí)，如果輸入a穩(wěn)定保持不變，則D1，D2，D3這三個(gè)觸發(fā)器輸出也會(huì)穩(wěn)定，狀態(tài)機(jī)保持正常運(yùn)行；但是如果a的值也剛好正在變化，情況就變得不可預(yù)測(cè)了。因?yàn)楦鱾€(gè)觸發(fā)器D端組合邏輯不盡相同，所以各個(gè)組合邏輯產(chǎn)生的延遲也不同。這樣，如果在同一時(shí)刻，a正在變化，由于延遲不同的緣故，各個(gè)觸發(fā)器所采集到的a的值也會(huì)有所不同，可能有的是‘1’，有的是‘0’，還有可能因觸發(fā)器建立保持時(shí)間不夠出現(xiàn)亞穩(wěn)態(tài)。假設(shè)D1觸發(fā)器采集到的a為1，而D3觸發(fā)器采集到的a為‘0’，那么D1和D3這兩個(gè)觸發(fā)器的輸出就肯定有一個(gè)是錯(cuò)誤的，從而就有可能導(dǎo)致?tīng)顟B(tài)機(jī)出現(xiàn)非法狀態(tài)而卡死。

2 解決的辦法

分析完導(dǎo)致?tīng)顟B(tài)機(jī)跑飛現(xiàn)象的幾種原因，針對(duì)不同的原因我們可以提出不同的解決方案。問(wèn)題的解決方案，總是有兩種類型：事先預(yù)防和事后補(bǔ)救。同樣，解決狀態(tài)機(jī)跑飛問(wèn)題也是如此。

2.1 預(yù)防措施

事故的最好解決辦法一定是“防患于未然”，事故一旦發(fā)生，無(wú)論補(bǔ)救措施多么的及時(shí)，或多或少都會(huì)造成一些損失。狀態(tài)機(jī)跑飛現(xiàn)象也是如此，如果能預(yù)防狀態(tài)機(jī)進(jìn)入非法狀態(tài)，或者減少狀態(tài)機(jī)進(jìn)入非法狀態(tài)的可能性，無(wú)疑是一個(gè)好辦法。

2.1.1 選用合適的編碼方式

既然由于大量非法狀態(tài)的存在，為狀態(tài)機(jī)跑飛提供了可能性，那么減少這種可能性就是一個(gè)好的努力方向。對(duì)同一個(gè)狀態(tài)機(jī)來(lái)說(shuō)，不用的編碼方式，其剩余狀態(tài)可能會(huì)不同。Binary編碼和One-hot編碼是最常用的兩種編碼方式。

對(duì)于Binary編碼來(lái)說(shuō)，如果狀態(tài)數(shù)N正好是2的冪次，則不會(huì)出現(xiàn)非法狀態(tài)。然而剛好符合這種情況的時(shí)候很少。更一般的情形，如果用到的合法狀態(tài)數(shù)量為N，觸發(fā)器的數(shù)量n=[log2N]，由此非法狀態(tài)的數(shù)量M=2n-N。對(duì)于One-hot編碼來(lái)說(shuō)，出現(xiàn)非法狀態(tài)是必然的結(jié)果。如果使用到的合法狀態(tài)數(shù)量為N，則設(shè)計(jì)狀態(tài)機(jī)所需的觸發(fā)器數(shù)量也為N，由此非法狀態(tài)的數(shù)量M=2n-N。假設(shè)同樣是6個(gè)狀態(tài)，用Binary編碼只有兩個(gè)非法狀態(tài)，而用One-hot進(jìn)行編碼卻有58個(gè)非法狀態(tài)。正因?yàn)榉欠顟B(tài)的存在，為狀態(tài)機(jī)跑飛提供了可能，而非法狀態(tài)越多，可能性就越大，單就這一點(diǎn)可以得出：One-hot編碼的狀態(tài)機(jī)比Binary編碼的狀態(tài)機(jī)更容易跑飛，而且狀態(tài)機(jī)狀態(tài)數(shù)越多，這種趨勢(shì)越明顯。

然而，選用什么樣的編碼方式對(duì)狀態(tài)機(jī)進(jìn)行編碼是一個(gè)綜合考慮的問(wèn)題，而并不是說(shuō)Binary編碼剩余狀態(tài)少就一定要用它對(duì)狀態(tài)機(jī)進(jìn)行編碼。事實(shí)上，Quartus II的默認(rèn)編碼方式是One-hot編碼。

2.1.2 異步輸入同步化

這是針對(duì)狀態(tài)機(jī)有異步輸入的情況。異步輸入同步化是一個(gè)跨時(shí)鐘域的問(wèn)題。對(duì)于1.3節(jié)中的狀態(tài)機(jī)，因?yàn)橹皇菃伪忍氐漠惒叫盘?hào)，可以通過(guò)“雙跳”技術(shù)來(lái)對(duì)其進(jìn)行同步。

圖3 雙跳以及雙跳重新同步Fig.3 Double jump and double jump to re-sync

在圖3中b是第一個(gè)觸發(fā)器的輸出，a是第二個(gè)觸發(fā)器的輸出。理論上說(shuō)，可以輸出準(zhǔn)穩(wěn)態(tài)信號(hào)，但是實(shí)際上準(zhǔn)穩(wěn)態(tài)信號(hào)會(huì)很快穩(wěn)定下來(lái)，不能一直維持其準(zhǔn)穩(wěn)態(tài)的狀態(tài)。所以第二個(gè)觸發(fā)器可用來(lái)防止其他電路發(fā)現(xiàn)這個(gè)準(zhǔn)穩(wěn)態(tài)信號(hào)?？梢钥吹揭肓穗p跳技術(shù)會(huì)對(duì)輸入a延遲1～2個(gè)時(shí)鐘周期，但是一般情況下一個(gè)外部事件觸發(fā)引起FPGA內(nèi)部一個(gè)動(dòng)作的一個(gè)比特位可能發(fā)生的頻率很小，通常附加幾個(gè)納秒對(duì)邏輯將不構(gòu)成影響[2]。

2.2 事后容錯(cuò)機(jī)制

有時(shí)候，雖然做了足夠的預(yù)防措施，但是也無(wú)法做到能消除一切隱患。事故發(fā)生了，就需要及時(shí)地采取行動(dòng)進(jìn)行補(bǔ)救以減少損失。比如由于惡劣的環(huán)境影響，狀態(tài)機(jī)已經(jīng)進(jìn)入了非法狀態(tài)，這件事已經(jīng)發(fā)生了，要能在出現(xiàn)更大損失之前糾正狀態(tài)機(jī)的狀態(tài)，使其能夠自動(dòng)地回到正常工作狀態(tài)。所謂“事后”是指狀態(tài)機(jī)進(jìn)入了非法狀態(tài)后，而不是出現(xiàn)跑飛之后。

2.2.1 非法狀態(tài)的處理

正是由于大量非法狀態(tài)的存在，為狀態(tài)機(jī)跑飛現(xiàn)象提供了可能性，所以理論上如果對(duì)所有的非法狀態(tài)都進(jìn)行邏輯控制，使能回來(lái)正常工作狀態(tài)上來(lái)，就能杜絕狀態(tài)機(jī)跑飛現(xiàn)象。

（1）方法一

假設(shè)一個(gè)狀態(tài)機(jī)正常用到的狀態(tài)為“st0”、“st1”、“st2”等3個(gè)，用的編碼方式是Binary,那么還剩余1個(gè)編碼組合，也就是說(shuō)還剩下1個(gè)非法狀態(tài)。這1個(gè)非法狀態(tài)在正常狀態(tài)機(jī)運(yùn)轉(zhuǎn)的時(shí)候用不到，但是現(xiàn)在在枚舉狀態(tài)時(shí)，也把這些列上：“undefined”。用VHDL語(yǔ)言表示如下：

定義部分：

實(shí)現(xiàn)部分：

這樣，即使?fàn)顟B(tài)機(jī)進(jìn)入了非法狀態(tài)“undefined”，由于加入對(duì)這個(gè)狀態(tài)的處理，狀態(tài)機(jī)也會(huì)重新回到正常工作狀態(tài)。

這種方法對(duì)Binary編碼方式來(lái)說(shuō)還可能有效，但是對(duì)于One-hot編碼來(lái)說(shuō)，因?yàn)镺ne-hot編碼的非法狀態(tài)太多了，編寫起來(lái)過(guò)于繁瑣，同樣是上面的例子，用One-hot來(lái)進(jìn)行編碼，就會(huì)出現(xiàn)5個(gè)非法狀態(tài)。

（2）方法二

VHDL語(yǔ)法提供了另一種簡(jiǎn)便的方法，如2.2節(jié)所述，利用others語(yǔ)句對(duì)未提到的狀態(tài)進(jìn)行統(tǒng)一處理。參照2.2節(jié)中有關(guān)部分重新改寫如下：

在others時(shí)，state不一定必須指到st0，也可以指到別的狀態(tài)或者是特定的處理模塊。語(yǔ)法上這種方法很有效果，但是實(shí)際上會(huì)有所不同，例如Quartus、Synplify等EDA工具在綜合以上的代碼時(shí)，會(huì)自動(dòng)忽視others這一行，并不生成相應(yīng)的電路。這種忽視是有意的，是對(duì)狀態(tài)機(jī)進(jìn)行優(yōu)化的結(jié)果。在絕大多數(shù)情況下，狀態(tài)機(jī)不會(huì)進(jìn)入到非法狀態(tài)，即使在極少數(shù)情況下?tīng)顟B(tài)機(jī)進(jìn)到非法狀態(tài)了，用以上的采用冗余方法綜合出來(lái)的電路所費(fèi)得資源太多，所以許多EDA工具采取忽視這條語(yǔ)句的做法，而提供了另一條更有效的方法：“安全狀態(tài)機(jī)”。

如果想others這一句不被綜合掉，可以選擇自己手動(dòng)對(duì)狀態(tài)機(jī)進(jìn)行編碼而不采用聲明為狀態(tài)機(jī)的語(yǔ)法。這種編寫方法Quartus II無(wú)法識(shí)別出狀態(tài)機(jī)，自然也就無(wú)法對(duì)其進(jìn)行優(yōu)化，others這一行就能綜合處正常的電路來(lái)。

圖4 一種自動(dòng)恢復(fù)電路模式Fig.4 An automatic recovery circuit mode

一般情況下，這種恢復(fù)電路是通過(guò)加入組合邏輯來(lái)實(shí)現(xiàn)的。如圖4所示，為了能使?fàn)顟B(tài)機(jī)恢復(fù)正常，在觸發(fā)器的D端原組合邏輯的基礎(chǔ)上，增加了一些新的組合邏輯。這種電路雖然實(shí)現(xiàn)了自動(dòng)恢復(fù)的功能，但是也增加了延遲。可能帶來(lái)一些負(fù)面的影響，如可允許的最大時(shí)鐘頻率減小或者達(dá)不到觸發(fā)器建立保持時(shí)間等?？梢钥紤]另一種方法：利用D觸發(fā)器的異步清零端來(lái)恢復(fù)。當(dāng)狀態(tài)機(jī)出現(xiàn)異常時(shí)，將每個(gè)觸發(fā)器的狀態(tài)清零。這種方式克服了前一種方法的增加延遲的缺點(diǎn)，但對(duì)狀態(tài)機(jī)的編碼有一定的要求。對(duì)所有的觸發(fā)器進(jìn)行清零后，狀態(tài)機(jī)回到了全零狀態(tài)，所以全零狀態(tài)必須是一個(gè)合法的工作狀態(tài)。這就要求在對(duì)狀態(tài)機(jī)編碼時(shí)，注意必須要有一個(gè)狀態(tài)是全零。D觸發(fā)器除了有一個(gè)清零端外，還有一個(gè)置位端，為什么這里用清零而不用置位呢？這是因?yàn)樵S多FPGA中D觸發(fā)器沒(méi)有置位端，只有清零端，要實(shí)現(xiàn)置位，必須要加入其他邏輯，所以使用清零端是最高效的方法。

2.2.2 加入檢測(cè)模塊

采用檢測(cè)模塊來(lái)檢測(cè)狀態(tài)機(jī)是否進(jìn)入非法狀態(tài)，如果檢測(cè)到了，就進(jìn)行一個(gè)特殊操作使?fàn)顟B(tài)機(jī)轉(zhuǎn)入一個(gè)特定的狀態(tài)。以O(shè)ne-hot編碼為例：One-hot編碼方式有自己的特點(diǎn),正常狀態(tài)只可能有一個(gè)觸發(fā)器的狀態(tài)為“1”,其余觸發(fā)器的狀態(tài)皆為“0”,即任何多于1個(gè)觸發(fā)器為“1”的狀態(tài)均為非法狀態(tài)。因此,可通過(guò)判斷是否在同一時(shí)刻有多個(gè)寄存器為“1”,若有,則啟動(dòng)相關(guān)操作來(lái)恢復(fù)狀態(tài)機(jī)。

2.2.3 選用安全狀態(tài)機(jī)

采用EDA工具中安全狀態(tài)機(jī)。現(xiàn)在EDA工具都提供這一功能。以Quartus II 8.1為例，進(jìn)入界面后，選擇“Assignments-＞settings-＞Analysis&Synthesis settings-＞more settings”，找到“Safe State Machine”，將其設(shè)置為“ON”即可。

3 結(jié)論

（1）有剩余狀態(tài)的存在，為狀態(tài)機(jī)跑飛想象的出現(xiàn)提供了可能。剩余狀態(tài)的多少與編碼方式有關(guān)系，所以可以通過(guò)選擇合適的編碼方式來(lái)盡量減少這種可能性；

（2）在編寫程序階段，設(shè)計(jì)者對(duì)惡劣環(huán)境因素的影響是無(wú)能為力的。幸好經(jīng)常遇到的狀態(tài)機(jī)跑飛問(wèn)題都是由異步輸入引起的，利用雙跳技術(shù)將異步輸入同步化即可消除這個(gè)因素；

（3）因?yàn)椴豢赡軓氐紫隣顟B(tài)機(jī)跑飛的可能性，所以事后容錯(cuò)機(jī)制是必不可少的。本文列出了一些容錯(cuò)方法，其中最簡(jiǎn)單有效的就是選用安全狀態(tài)機(jī)；

（4）要想設(shè)計(jì)安全健壯，就必須努力減少狀態(tài)機(jī)進(jìn)入非法狀態(tài)的可能。安全狀態(tài)機(jī)所謂的“安全”，并不是真正的安全，實(shí)際上只是容錯(cuò)機(jī)制的一種。

[1]潘松,黃繼業(yè).EDA技術(shù)實(shí)用教程:VHDL版(第4版)[M].北京：科學(xué)出版社,2010.

[2]ALTERA CORPORATION.Quartus II Handbook,Version 1:Design and Synthesis[M].2009.

[3]克里茲,孟憲元.高級(jí)FPGA設(shè)計(jì):結(jié)構(gòu)、實(shí)現(xiàn)也優(yōu)化[M].北京：機(jī)械工業(yè)出版社,2009.