一種基于FPGA的低功耗\\容錯狀態機設計方法

摘要:針對FPGA在航空航天領域應用面臨的可靠性和功耗問題，提出了一種適于FPGA實現的低功耗、容錯有限狀態機設計方法。該方法與傳統FPGA中實現狀態機占用布線資源、查找表、寄存器等資源的思想不同，它將狀態機映射到FPGA內嵌塊RAM，同時采用兩塊RAM構成雙模冗余結構，通過比較兩塊RAM輸出數據的一致性確定RAM中數據出錯的情況，并結合奇偶校驗進行檢錯與糾錯。實驗結果表明與經典的三模冗余方法相比該方法有更低的功耗和更高的可靠性，并能對一位錯誤實現在線糾錯。

關鍵詞:低功耗;有限狀態機;容錯;現場可編程門陣列

中圖分類號: TP368;TN873文獻標識碼:A文章編號:1004-731X (2006) xx-xxxx-x

A FPGA-Based Design Method of Low Power fault-tolerance

finite state machine

LI Lie-wen ，GUI Wei-hua ， HU Xiao-long

( School of Information Science and Engineering，Central South University，Changsha 410075，China)

Abstract: Considering the reliability and power consumption problems of FPGA in aviation and spaceflight application field， a new design method of low power and fault-tolerance finite state machine suitable for FPGA was presented. Different from traditional occupying routing resources， looking up tables and registers， the method was realized by mapping finite-state machines into embedded blocks RAM of FPGA and employing two RAM blocks to compose the duple-redundancy structure to confirm data errors in RAM through comparing consistency of two blocks RAM output data and combining with parity check for error detection and correction. The experimental results show that the method has the advantages of lower power， higher reliability， and achieving an error on-line error correction compared with the traditional triple-redundancy method.

Key words:low power;finite state machine;fault-tolerance;Field Programmable Gate Array(FPGA)

現場可編程門陣列(FPGA) 以其高性能、可重構、設計周期短等優勢，被認為是在航空航天領域的重要器件。由于空間輻射，基于SRAM 的FPGA 在空間環境工作時，極易受到單粒子翻轉 (Single Event Upset，SEU)的影響。SEU是由于帶電重粒子轟擊集成電路時造成瞬時充放電而導致存儲單元的邏輯狀態翻轉[1]，它能改變FPGA內部寄存器、塊RAM、查找表(Look-Up-Table，LUT)、配制存儲塊的內容，可能引起計算結果錯誤、程序執行序列錯誤， 甚至使系統崩潰。此外，在宇宙空間的高真空環境，由于沒有空氣來散發電子系統產生的熱量，整個環境對系統的散熱非常不利，電子系統散熱只能用其它方式來解決，這就勢必對系統功耗指標提出嚴格的要求。因此，可靠性和功耗問題已經成為FPGA在航空航天領域應用首要考慮和解決問題。

有限狀態機(finite state machine ，FSM)是數字系統設計中的重要組成部分、是FPGA中實現高效率高可靠性邏輯控制的重要途徑，有限狀態機可靠性直接關系到整個系統的穩定，國內外許多研究機構針對FPGA中有限狀態機的容錯能力展開了研究。目前，FPGA中實現有限狀態機主要有兩種方法。第一種是傳統方法，該方法用寄存器存儲狀態信息，用組合邏輯產生下一狀態和輸出值，實現時主要占用FPGA的布線資源、查找表、寄存器等資源。基于這種實現方法， 國內外提出了許多容錯方法。如系統級N模冗余、選擇性冗余結構等。在眾多容錯方法中三模冗余(triple module redundancy， TMR)是最典型方法之一，該方法在增加系統可靠性的同時， 大大增加系統的資源開銷，使系統功耗也隨之增大，此外三模冗余結構不具備在線糾錯能力[2]。

第二種方法是利用FPGA中存儲資源，將有限狀態機映射到FPGA內嵌的塊RAM[3][5]。新一代的FPGA器件中除了有觸發器、查找表、布線資源等可編程邏輯資源外，還有一些存儲資源，如Xilinx公司的Virtex系列FPGA內部有成塊的RAM資源。Altera 公司的Stratix系列FPGA包含TriMatrix存儲器[4]。該方法充分利用了新一代的FPGA器件存儲資源，大大減少了FPGA的布線壓力和功耗，此外，還可以通過修改塊RAM的內容的方式來改變有限狀態機的功能而不必重新綜合、布局、布線。在此方法基礎上，文獻[5] 提出一種容錯狀態機實現方法，該方法用塊RAM執行狀態機，采用漢明碼用于檢錯與糾錯。該方法特點是能對一位錯誤能在線檢測并糾正，缺點是實現較復雜，容易產生誤校驗(在發生二位錯誤時，編碼以一位錯誤來處理并加以“糾正”，結果將引起更大的錯誤)。

本文針對三模冗余容錯方法具有占用資源多、功耗大等缺點，結合高性能FPGA結構特點，充分利用FPGA內嵌塊RAM資源，提出了一種新的低功耗、容錯狀態機設計方法。首先，文章分析了FSM映射到塊RAM思想并給出了相映算法，在此基礎上，提出了基于塊RAM的雙模冗余結構狀態機設計方法，該方法通過比較兩塊RAM的輸出值，結合奇偶校驗進行檢錯與糾錯，幾乎能檢驗出所有錯誤，并能對一位錯誤實現在線糾錯。

1容錯狀態機設計

基于雙RAM冗余結構容錯狀態機設計主要思想: 整個設計采用兩塊塊RAM構成雙模比較冗余結構，同時將狀態機映射到塊RAM，映射到塊RAM的狀態機每個字增加一位用于奇偶校驗，系統工作時通過比較兩個模塊的輸出，并結合奇偶校驗結果對系統進行查錯和糾錯。實現過程主要包括兩步:(1)FSM映射到塊RAM。(2)雙模冗余結構設計。

1.1 FSM映射到塊RAM

使用FPGA中塊RAM執行狀態機時，存儲器每個存儲單元內容包括狀態編碼(由它和狀態機的輸入位一起形成下一狀態的存儲位置的地址)和狀態機的輸出位。一個有限狀態機映射到FPGA塊RAM的實例如圖1所示，其中圖1(a)為有限狀態機的狀態轉換圖(state transition graph ，STG)，圖1(b)為狀態機在存儲塊中執行示意圖。

圖中RAM的數據寬度為4比特，高3位是狀態機當前狀態的編碼，低1位是狀態機向下一狀態轉換時的輸出值。例如，“0000“存儲單元中高3位存放S1的狀態編碼 “001”，低1位則存放態轉換時的輸出值“0“。狀態機轉換時下一狀態的地址由當前狀態編碼和當前輸入決定。例如，從狀態S1到狀態S2跳轉時由于當前狀態S1的編碼為“001”，而且狀態S1到狀態S2跳轉時輸入為“1”因此由S1的狀態編碼“001”和“1”組合在一起構成S2狀態編碼的存儲單元地址“0011”該存儲單元高三位存放S2的狀態編碼“010”，第四位存放輸出值“0”。同樣，狀態轉換圖的其它狀態也按這種方式存儲。如果用I表示狀態機輸入的位數，O表示狀態機輸出位數。S 是狀態編碼的位數，則執行該狀態機所需存儲器的大小可表示如下:(1)

I+s 表示所需的地址線數目， o+s是每個存儲單元的位數.地址線和所需存儲單元的數目隨狀態機輸入數增加而增加。實現FSM映射到塊RAM的映射算法如表1所示。

算法中的第一行對狀態轉換圖中所有狀態進行編碼。第二行到第四行比較每片RAM的地址線數目與狀態機編碼位數和輸入位數之和。如果單片RAM的地址線數目大于狀態機編碼位數和輸入位數之和，則進一步確定此片RAM的每個存儲單元位數是否小于編碼位數與輸出位數之和。第五行到第十行用于處理單片存儲單元位數不能滿足存儲編碼位數與輸出位數情況，此時多片RAM串行連接，進行位擴展。第十三行到第十六行則處理單片RAM地址線不能滿足要求的情況。第十八行到第二十行完成多片RAM并行連接，進行字擴展，在保證有足夠的地址線后，跳轉到第三行確保每個存儲單元有足夠的存儲位。在完成所有FSM映射后算法終止。

1.2基于塊RAM的雙模冗余結構

(1)雙模冗余結構

基于塊RAM的雙模冗余結構如圖2所示。圖中兩塊RAM構成雙冗余結構，每塊RAM具有兩個端口，分別稱為端口A 端口B，每個端口都有獨立地址線、數據線、時鐘信號線、復位信號線和使能端。圖中兩塊RAM接受相同的輸入，運行相同的任務，比較器用于比較兩塊RAM輸出的數據。此外，存儲在兩塊RAM的數據每個字增加一位奇偶校驗位，奇偶校驗器用于對輸出數據進行奇偶校驗，可以檢測出RAM中每個存儲單元出現的寄數個錯誤。

圖中多路選擇器可用FPGA自帶的多路選擇器單元實現，這樣可以避免SEU的影響。奇偶校驗器和比較器采用三模冗余結構，它們的輸出通過一個表決器，表決器符合下列等式。

(2)

其中a，b，c是表決器的輸入。表決器也可能受到SEU影響，因而表決器也采用三模冗余結構。

(2)雙模冗余結構工作分析

基于塊RAM的雙模冗余結構運行狀態機時，兩塊RAM接受相同的輸入，運行相同的任務，每個時鐘周期，兩塊RAM輸出的數據通過比較器進行比較，根據輸出數據是否一致來判斷兩塊RAM中是否出現錯誤，同時結合寄偶校驗碼進行查錯與糾錯。

雙模冗余結構工作時可能出現的錯誤可分為三類。第一類指兩塊RAM輸出相同字的對應位只有一處錯誤。第二類指兩塊RAM輸出相同字的對應位有兩處以上錯誤，包括一個字中有多個錯誤，或兩個字中分別有錯誤，不包括兩塊RAM輸出相同字的對應位置發生偶數個的錯誤。第三類指兩塊RAM輸出相同字的對應位置發生偶數個錯誤。

第一類錯誤發生時，比較器顯示結果是兩塊RAM輸出相同字的對應位不一致的數目為一位，對于種情況，由奇偶校驗位確定出錯的塊RAM，并通過多路選擇器從沒有出錯的塊RAM中選取正確的數據輸出，同時用正確RAM數據對出錯RAM的內容進行修正，從而實現了對一位錯誤在線糾正。實現系統一位錯誤在線糾正的結構如圖3所示。

對于第二類錯誤，即圖2中的比較器比較兩塊RAM輸出數據時，比較結果是兩塊RAM輸出的兩個字中不同的位數超過一位，此時可以確定系統出現了錯誤，但不能確定錯誤來源于那一塊RAM，因此必須調用外部正確的數據對兩RAM內部數據擦洗校正。

當第三種錯誤發生時，由于兩塊RAM輸出相同字的對應位置發生偶數個錯誤。此時比較器和奇偶校驗都將失去作用，但實驗證明，出現這種錯誤的概率極小，在系統可靠性分析時將對這種錯誤出現的概率進行分析。

2 系統可靠性分析

2.1 雙模冗余結構的可靠性建模

要驗證雙模冗余結構的可靠性，首先建立瞬時錯誤估計模型。當前，已有不少文獻對存儲器的可靠性進行了研究 [6] [7] [8]。本文對雙模冗余結構可靠性是在這些研究的基礎進行。

2.1.1雙模冗余結構的可靠性

基于雙模冗余結構系統工作時，當系統出現一位錯誤時，系統能在線檢測并在線糾正，當出現兩個或兩個以上錯誤時，則中斷現行操作，啟用外部擦洗，因此雙模冗余結構的可靠性是指能檢測出多個錯誤情況下的可靠性。下面推斷計算雙模冗余結構可靠性計算公式，依照泊松分布，有N個字且每個字為W位的存儲器可靠性滿足下面公式[9]。

(3)

其中入是瞬時出錯的概率。W是每個字的位數，N代表存儲器的總字數。

在基于雙模冗余結構系統中，兩塊RAM輸出的兩個字中必須包含一個正確的字用于糾正出錯的輸出字，同時一個字中最多不超過一位錯誤，有一位錯誤出現并能在線糾錯情況下的穩定性計算公式如下:

(4)

上式中第一項代表兩塊RAM輸出字都是正確的情況。第二項表示一個SEU錯誤能使用冗余塊RAM在線修正的情況。

2.1.2 兩塊RAM輸出相同字的對應位置發生偶數個錯誤概率

對于前面提到的第三類錯誤，即雙模冗余結構中來自兩塊不同RAM的兩個輸出字相同的位上出現偶數個錯誤的概率推導過程如下:

1.假設兩塊RAM各自的一個輸出字都發生兩個錯誤，則錯誤出現在兩個輸出字相同位上的概率:

(5)

2.兩個錯誤在一個字上發生的概率是:

(6)

3.用上面兩公式可計算RAM冗余結構兩塊RAM的輸出字相同的位上同時出現兩個錯誤的概率:

(7)

4.同理，可計出一個字上發生的所有偶數個錯誤的概率，從而可以出自兩塊不同RAM的兩個輸出字相同的位上出現偶數個錯誤的概率:

(8)

本文在計算兩塊不同RAM的兩個輸出字相同的位上出現偶數個錯誤的概率時一些實驗用數據來源于文獻[10]，其中t=10天、入=48*10-6次翻轉/每位/每天。根據公式(8)得出P偶數=10-9，從這個數值可看出兩塊不同RAM的兩個輸出字相同的位上出現偶數個錯誤的概率極小，在系統實際工作時可不加以考慮。

2.2 三模冗余結構的可靠性建模

為了進行比較，對三模冗余結構的可靠性建模。對于傳統的基于查找表和觸發器的狀態機的實現方式采用和雙模冗余結構相同的錯誤評估模型，Xilinx Virtex-II中每個查找表包含16個存儲單元。因此設計存儲單元可以表示成L*16，其中L是設計中使用的查找表數目，狀態機組合部分的可靠性可用下面公式計算:

(9)

RLUT是所有查找表組合的可靠性，L是設計中查找表數目[11]，整個三模冗余結構的可靠性計算公式如下。

(10)

上式計算有兩個假設:

①三模冗余系統中應有兩個或兩個以模塊正常工作。

②實現狀態機使用的觸發器也采用三模冗余結構，不會受SEU影響而發生錯誤。

3.實驗及結果分析

實驗采用6個MCNC基準電路對基于塊RAM雙模冗余結構和三模冗余結構進行可靠性、功耗兩個方面比較。

3.1可靠性實驗

在計算有限狀態在基于三模冗余結構上執行的可靠性時，假設四輸入的查找表中的16位任意一位有錯誤將導致設計失敗。在計算三模冗余結構穩定時，設計了出錯位占查找表總位數不同百分比情況，分別對一個查找表中出錯位占25%， 50%， 75% 和 100%四種情況進行了可靠性計算，基于三模冗余、基于雙模冗余的可靠性實驗結果如表2所示。

從表2中可以看出雙模冗余結構的可靠性要高于傳統三模冗余結構，其主要原因是雙模冗余結構能對系統出現的一位錯誤實現在線糾正。而三模冗余結構只能在系統的三個模塊比較后才能發現系統錯誤，而且不具有在線糾錯能力，構成三模冗余結構的三個模塊中只有兩個或兩個以上模塊無錯時系統才能正常工作。因此，當系統有充足的塊RAM資源時，雙模冗余結構是一種實現穩定性高并具有自我糾錯能力有限狀態機很好的方法。

3.2功耗實驗

為了對兩種設計方法的功耗進行分析比較，設計了仿真實驗。整個實驗上在Xilinx公司的FPGA Virtex-II系列器件XC2V1500上進行，仿真工具采用Modelsim6.1，綜合工具采用Xilinx公司的ISE8.1[12]，最后用XPower進行功耗分析。XPower進行功耗分析流程如圖4所示。

XPower是Xilinx公司開發的專門用來進行功耗分析的工具。XPower直接集成在ISE軟件中，XPower從布局和布線 (.ncd)文檔獲得FPGA設計信息，從vcd文檔中獲得網絡設計中所需的時鐘頻率、開關活動等信息，該文件可在布局和布線時由Xilinx工具產生，功耗報告在pwr文檔中結出。三模冗余結構、雙模冗余結功耗比較如表3所示，實驗時鐘頻率為100MHZ，功耗單位是毫瓦。

表3三模冗余結構、雙模冗余結功耗比較

測試

電路三模

冗余功耗()雙模

冗余功耗()節約功耗(%)

Keyb190.85144.2732.28

planet324.35232.9239.46

Dk16191.24144.0232.79

Exl244.87225.418.63

styr270.61184.9646.30

sand274.27181.4851.13

Tab.3 th power comparison between TMR and duple-redundancy structure

從表3中看出雙模冗余結構的功耗要明顯低于傳統三模冗余結構，其主要原因是采用查找表和觸發器資源實現的三模冗余結構時，除了查找表和觸發器要消耗大量的能量之外，負責聯通查找表和觸發器等FPGA內部單元的布線資源也要消耗較多的能量[13]，而用雙模冗余結構實現有限狀態機時，主要占用塊RAM資源幾乎不需要消耗布線資源，因而具有較低的功耗。

4 結論

a、本文提出了一種適于FPGA實現的低功耗、容錯有限狀態機設計方法，該方法在基于將FSM映射到RAM的基礎上，充分利用FPGA所帶存儲資源，采用雙RAM冗余結構， 并結合奇偶校驗進行檢錯與糾錯。實驗結果表明，較傳統的TMR方法，該方法具有低功耗、高穩定性等優勢，非常適合于提高FPGA在高空工作環境下的容錯能力。

b、提出了冗余方法和編碼容錯相結合的思想。

在傳統冗余容錯思想的基礎上結合編碼容錯不但能提高系統的可靠性，還能提高系統在線糾錯能力，今后將編碼壓縮、編碼容錯、冗余容錯相結合可以節約存儲資源、降低功耗是一個值得研究的方向。

c、提出了同時考FPGA功耗和容錯的思路。在以往有關FPGA的研究中，往往只注重FPGA功耗或系統容錯能力單個方面，但隨著FPGA在航空航天、軍工鄰域廣泛應用，基于FPGA的系統功耗和容錯能力同時考慮將成為一個新的研究方向。

參考文獻:

[1]Bolchini C， Quarta D. SEU mitigation for sram-based fpgas through dynamic partial reconfiguration[C]//Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI， Stresa-Lago Maggiore， Italy .2007， 55-60.

[2]Sterpone L. Analysis of the Robustness of the TMR Architecture in SRAM-Based FPGAs [J]. IEEE Transaction on Nuclear Science， 2005，52(5):1545-1549.

[3]Tessier R， Betz V.Power-Efficient RAM mapping algorithms for FPGA Embedded memory blocks[J].IEEE Trans. of Computer- Aided Design， 2007，26(2):278-289.

[4]Gyouml;rfi T， Cre O . High performance true random number generator based on FPGA block RAMs[C] //Proceedings of the 2009 IEEE International Symposium on Parallel and Distributed Processing Rome， Italy，2009， 1-8 .

[5]Frigerio L， Salice F.Ram-based fault tolerant state machines for FPGA[C]//Proceedings of IEEE Design and Fault Tolerant Symposium， Rome， Italy， 2007， 312-320 .

[6]Maestro J A，Reviriego P. Study of the effects of MBUs on the reliability of a 150 nm SRAM device[C]//Proceedings of the 45th annual Design Automation Conference， ACMNew York， NY， USA ， 2008，930-935.

[7] Maestro J A， Reviriego P. Reliability of Single-Error Correction ProtectedMemories[J].IEEE Transactions on Reliability ， 2009，58(1):193-201.

[8]Argyrides C， Vargas F. Embedding Current Monitoring in H-Tree RAM Architecture for Multiple SEU Tolerance and Reliability Improvement[C] // Proceedings of the 2008 14th IEEE International On-Line Testing Symposium， Washington， DC， USA2008， 155-160 .

[9]Reviriego P， Maestro J A. Reliability Analysis of Memories Suffering Multiple Bit Upsets[J].IEEE Trans. on Device and Materials Reliability， 2007，7(4):592-601.

[10]Asadi G， Tahoori M B. Soft Error Rate Estimation and Mitigation for SRAM-Based FPGAs[C]//International Symposium on Field Programmable Gate Arrays， ACM New York， NY， USA 2005，149-160.

[11] 徐拾義.可信計算系統設計和分析[M].北京:清華大學出版社，2006.

XU S Y. analysis and design of trusted computer system [M].Beijing: Tsinghua University Press，2006.(In Chinese)

[12] 張紅南，劉曉巍. IC 卡的優化設計及FPGA仿真[J].湖南大學學報:自然科學版，2006，33(2):66-69.

ZHANG H N ，LIU X W. OptimizedDesignand

Simulation Based on FPGA of IC Card [J] .Journal of

Hunan University:Natural Sciences 2006，33(2):66-69.

(In Chinese)

[13]TUAN T， RAHMAN A. A90-nm low-power FPGA for battery-powered applications[J].IEEE Trans. on Computer-Aided Design ，2007，26(2):296-300.