內進化容錯模型設計及其可靠性分析

摘 要： 仿照自然界的碳基生物進化過程，在FPGA內部實現了可控的硅基進化。針對電子系統常見的SA故障，提出了基于演化硬件技術的內進化容錯模型，通過在FPGA內部裝載Microblaze CPU和構建可重配置陣列，實現了演化硬件的片內進化。利用該模型進行了故障容錯實驗，檢驗了其有效的故障容錯能力，證明該容錯方法能夠有效提高數字電路的可靠性。

關鍵詞： FPGA； 內進化； 容錯； 可靠性分析

中圖分類號： TN911?34； TP301.6 文獻標識碼： A 文章編號： 1004?373X（2013）20?0001?03

進化硬件（Evolution Hardware，EHW）指的是仿照自然界中以碳為基的生物進化過程，在現有的FPGA芯片基礎上實現可控的“硅基進化”。進化硬件實際上是一種特殊硬件，它可以像生物一樣具有自適應、自組織、自修復特性[1]，從而可以根據使用環境的變化而改變自身的結構以適應其生存環境。進化硬件除了能夠生成具有新功能的電路以外，還可用于減少故障的發生，獲得容錯的功能，從而提高電路可靠性[2]。

1 內進化容錯模型

通過在FPGA內部構建運算進化算法的Microblaze CPU，把決定電路結構和功能的二進制配置位串作為染色體，通過對實際硬件的配置和測試來加速適應度評估過程。將其進化結果直接用于可重配置電路，以便獲得具備預期功能的實際硬件。內進化設計的方式更充分地利用了可編程器件的芯片資源和可重構特性。由于將進化硬件特有的快速進化和硬件可重配置結構與FPGA內部算法運行和下載的內進化模式相結合，即可獲得具有實時、自適應、容錯能力的理想硬件特性[3?4]。如圖1所示。

從圖1可以發現在FPGA內部主要分為兩個區域：Microblaze CPU[5]和可重配置陣列[6]。圖中的Microblaze CPU是基于XILINX公司FPGA的微處理器IP核，和其他外設IP核一起，可以完成可編程系統芯片（SoPC）的設計。Microblaze是一個高度靈活可以配置的軟核，可以根據設計的需要，對Microblaze進行裁減，用最少的資源完成設計的需要。可重配置陣列由可編程單元組成，其規模根據電路的復雜程度和功能需求設定。其中最基本單元是可編程單元（Programmable Element，PE），由配置寄存器、多路選擇器和基本邏輯運算單元組成。在系統工作時， Microblaze CPU通過數據控制通道配置可重配置陣列，配置完成后可重配置陣列單獨工作。

如果嵌入該模型的FPGA工作環境或功能要求發生了變化，只需重新啟動上述進化過程，針對新的設計目標和內、外部條件重新進行搜索，便可獲得新的配置位串和預期電路功能，即實現硬件自適應。同樣，如果硬件電路本身出現了局部故障但存在預留的資源冗余，重新執行上述進化過程后也有望避開故障區域，重新獲得預期的電路功能。

2 具體實現

2.1 算法流程

由于遺傳算法模擬了自然選擇和自然遺傳過程中發生的繁殖、雜交和突變現象。因此將遺傳算法作為演化算法。在求解問題時，問題的每個可能的解都被編碼成一個“染色體”，即個體，若干個個體構成了群體。在遺傳算法開始時，隨機地產生初始個體群，根據預定的目標函數對每個個體進行評價，給出了一個適應度值。基于此適應度值，選擇個體用來復制下一代。選擇操作體現了“適者生存”原理，“好”的個體被選擇用來復制，而“壞”的個體則被淘汰。然后選擇出來的個體經過交叉和變異算子進行再組合生成新的一代。這一群新個體由于繼承了上一代的一些優良性狀，因而在性能上要優于上一代，這樣逐步朝著更優解的方向進化。演化算法的基本流程如圖2所示。

2.2 遺傳算子設計

（1）轉盤賭選擇，即個體的選擇概率pi等于其適應度值在所有個體的適應度值之和中占的比例。首先先計算個體的相對適應值記為pi，然后根據選擇概率{pi ，i=1，2，…，N}把一個圓盤分成N份，其中第i扇形的中心角為2πpi。在進行選擇時，先生成一個[0，1]內的隨機數r，若p0+p1+…+pi?1

（2）交叉運算，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區別于其他進化算法的重要特征，它在遺傳算法中起著關鍵作用，是產生新個體的主要方法。本設計采取單點式交叉方法，即隨機的在兩個父串上選擇一個雜交點，然后交換這兩個串的對應的子串。

（3）變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。

2.3 適應度評估

內部演化將遺傳算法每一代產生的每一條染色體都實際下載到器件中，并對每一種電路結構的輸出直接進行評判。內部演化評估速度快，并可利用器件的實際特性實現系統動態重構。適應度的計算方式為給一個輸入矩陣，讀取輸出矩陣，如果和希望的標準矩陣一致則“適應度”加1。其數學表達式為：

[fitness=i=1mj=1nCi，j，C=X⊕M] （1）

式中：X為該個體對應的輸出矩陣；M為標準輸出矩陣。

3 故障容錯實驗與冗余可靠性分析

3.1 實驗條件

采用Schwefel的（1+λ）?ES演化策略[7]。程序參數為：最大適應度值12，種群規模10，變異率0.02，交叉率0.3，最大演化代數100 000。根據第一列PE單元的損傷數目設計7種不同的故障模式，每種故障采用100個不同的隨機數種子。應用數理統計的方法，每種故障模式采用100個樣本。在規模為8×4個PE單元的可重配置陣列中，進行了第一列PE單元邏輯門損壞和容錯實驗。模擬文獻[6]中提到數字電路中常見的SA故障，SA故障指的是無論對于何種輸入，節點的輸出固定為某一邏輯值。

3.2 實驗結論

記PEi為第一列PE損傷數為i（i<7）的故障模式，試驗結果如表1所示。

表1 不同故障模式修復代數統計

針對SA?0錯誤，通過Microblaze CPU對可重配置陣列進行演化在十萬代內均能找到正確的解（PEi（i<6）），成功證明了該算法良好的容錯特性，在電路設計方面有效改善了傳統電路設計中一次設計終身定型的弊端，使電路在遇到故障時可以避開故障單元，實現功能自修復。

3.3 冗余可靠性分析

圖3所示為演化電機的3輸入2輸出換向電路，分別計算兩種不同電路的可靠性[8]。

由于設計只使用了基本的邏輯單元如與門、或門、與非門和或非門，得到演化方法設計電路可靠性概率pe為：

相比傳統電路設計方法得到的可靠性概率pn為：

pe和pn概率如圖4所示，虛線表示傳統電路設計方法生成的電路的故障率，實線表示冗余電路利用演化算法生成電路的故障率。可以看出，當p∈（0，0.5）時pe>pn，即動態可重構冗余電路具有更高的可靠性。

4 結 語

本文通過在FPGA內部集成Microblaze CPU和可重配置陣列的方式，實現了基于內進化方式容錯模型。針對SA故障進行了容錯實驗，證明該模型具有良好的故障容錯能力，為獲得具有實時、自適應、容錯能力的理想硬件特性提供了新的技術途徑。建立了電路可靠性的概率分析模型，并且針對本試驗中的具體電路分析了冗余方法結合演化算法設計電路和傳統方法設計電路的出錯概率，證明了前者具有更高的可靠性。

參考文獻

[1] YAO X， HIGUICHI T. Promises and challenges of evolvable hardware [J]. IEEE Transaction on Systems Man and Cybernetics， 1999， 29（1）： 87?97.

[2] PAULINE C， ANDY M. Challenges of evolvable hardware： past， present and the plan to a promising future [J]. Genet Program Evolvable， 2011，12： 183?215.

[3] FUKUNAGE A， HAYWORTH K， STOICA A. Evolvable hardware for spacecraft autonomy [C]// 1998 IEEE Aerospace Conference. Snowmass at Aspen， CO： IEEE， 1998， 3： 135?143.

[4] KEYMEULEN D， ZEBULUM R S. Fault?tolerant evolvable hardware using field programmable transistor arrays [J]. IEEE Trans. on Reliability， 2000， 49（3）： 221?227.

[5] OBEIDAT F， KLENKE R. Microblaze： an application?independent fpga?based profiler [C]// Proceeding of the 19th ACM/SIGDA international symposium on Field programmable gate arrays. New York， NY， USA： ACM， 2011： 283?285.

[6] LOU J A， ZHANG Z W， CUI X F. Design and implementation of digital ciecuit evolution based on Virtual reconfigurable platform [J]. Computer Measurement Control， 2011， 19（11）： 2781?2784.

[7] 高瑋，尹志喜.現代智能仿生算法及其應用[M].北京：科學出版社，2011.

[8] 王同權.高能質子輻射效應研究[D].長沙：國防科技大學， 2003.

[9] JAHANIRAD H， MOHAMMADI K， ATTARSHARGHI P. Single fault reliability analysis in FPGA implemented circuits [C]// 2012 13th International Symposium on Quality Electronic Design （ISQED）. [S.l.]： IEEE， 2012： 49?56.