基于FPGA的故障修復演化技術研究*

王 潔，康俊杰，周寬久

(大連理工大學軟件學院，遼寧大連116620)

1 引言

隨著集成電路的規模和復雜度不斷提高，電子系統在復雜多變的應用環境中發生故障的可能性大大增加，尤其是航空航天和深海探測等領域，系統一旦發生故障，將導致嚴重的后果。因此，電子系統必須具備容錯能力。傳統的容錯技術主要采用冗余資源對故障進行修復，但只能進行容錯，不具備故障檢測的能力，對整個電子系統均使用冗余資源難以實現。演化硬件EHW(Evolution Hard-Ware)技術能夠有效修復故障電路，但由于演化過程耗時較長且演化效率不高的缺陷，不能對整個硬件電路完成演化操作［1，2］。系統容錯應該是一個實時的過程，在故障發生之后，故障電路被隔離出系統，若不能在線實時完成故障的修復，將直接影響系統的正常運行，甚至導致系統癱瘓［3］。

針對以上問題，本文提出了基于演化硬件的實時系統容錯架構，通過故障分析樹實時檢測電路故障，并將故障定位至故障源電路;在發生故障后，采用故障補償機制，隔離故障源電路，維持系統正常運行;采用高效的演化算法，快速演化得到修復電路，實現故障的在線實時修復，提高系統的穩定性和可靠性。

2 相關工作

容錯是指系統在運行過程中發生故障時，能夠通過調節自身電路結構，保持系統正常運行的能力。傳統的容錯方案主要采用冗余技術。冗余技術通過利用系統冗余資源來完成故障修復，能夠有效應對器件損壞等硬件故障，其中最經典的是三模冗余技術，但過多的冗余資源將導致系統的復雜度及設計成本大大增加［4，5］。Yang 等人［6］提出一種基于演化機制的三模冗余架構，通過交互式兩階段變異演化策略將系統的電路演化為具有不同結構的冗余模塊，能夠有效解決共模故障問題，但耗費的硬件資源更多。Zhang等人［7，8］提出了一種基于演化硬件和補償平衡技術的新型自修復技術，可通過動態配置實現各種電路和設備的故障自修復。但是，只通過對故障輸出進行補償修復，若在不同時間段發生多次相同問題，將重復演化修復，耗費時間。針對這個問題，Wang等人［9，10］提出了一種基于演化硬件的實時系統容錯策略，相同電路發生多次故障時訪問配置庫，結合配置庫和相似性演化算法，縮短了故障修復時間。但是，存在的問題是，系統電路的修復約束期限無法準確預測，并且維持配置庫也增加了額外時間和資源消耗。

上述容錯方案經實驗驗證都具有良好的容錯性，但由于都不能得到故障電路的修復約束期限，只能在理論上以短時間得到修復電路，因此實時性是相對的。系統容錯必須考慮實時性約束，如果不能在約束期限內獲得修復電路，即使最終生成修復電路，容錯也是失敗的，因此必須設計出具有高效實時性、容錯性的容錯方案。

3 演化硬件實時容錯系統

電路系統的結構復雜多變，同種電路在不同系統結構中的修復約束期限也各不相同，因此以約束期限作為實時性約束難以操作。本文在Zynq平臺上設計了演化硬件實時容錯系統。如圖1所示，通過故障檢測機制實時監控系統電路，發生故障后快速定位、隔離故障源電路，采用故障補償機制維持系統正常運行，同時運行演化修復機制快速生成修復電路，實現系統的在線實時修復，提高系統的可靠性。

3．1 故障檢測機制

在線實時修復故障的前提是在故障發生后，能夠準確快速地檢測并定位故障源電路。本文采用故障樹分析FTA(Fault Tree Analysis)的檢測機制，從某個可能的故障點開始通過樹的形式，從上至下，逐層查找發生故障的直接原因和間接原因，最終找到故障源，完成故障的準確定位。

如圖2所示，在進行大規模電路系統設計時，對系統各級電路進行分層模塊劃分，同時存儲對應電路的真值表信息。在系統運行時，利用故障樹實時檢測系統各個模塊的實際輸出和應有輸出，若輸出值不一致，則發生了故障。以自頂向下的方式分析各模塊的輸出值能夠快速定位故障源電路，實現故障的實時檢測。

基于冗余的電路容錯方案，不具備故障檢測的能力，需要對電路整體采用多個冗余資源維持電路功能，硬件資源消耗過大，增加了系統復雜度。演化硬件實時容錯方案能夠檢測故障源，將發生故障的區域最小化，只對故障的電路進行修復，提高了資源利用率。

3．2 故障補償機制

故障檢測定位故障源電路后，需要對故障電路進行隔離，此時系統仍需正常運行。由于電路系統的結構復雜，無法預測故障電路的修復約束期限，若不能在約束期限內完成故障的修復，則系統的運行直接受到影響，甚至導致嚴重后果。

基于上述原因，本文提出一種故障補償機制，當故障電路被隔離之后，采用故障補償機制維持系統的正常運行，為故障修復提供安全保障。如圖3所示，由于故障檢測是通過真值表對電路的各模塊進行監測，在故障發生之后，故障檢測機制發送信號C1給多路模擬開關MUX，隔離故障電路，信號C0觸發故障補償機制運行，并從真值表中獲取故障電路輸入端的對應輸出值，再通過MUX輸出數據，保證系統的正常運行。在演化修復機制運行的同時，系統能夠執行正常的功能，不必預測電路的修復約束期限，快速演化得到修復電路后重新配置故障電路，即可實現故障的在線實時修復。由于集成電路中發生的很多故障不可預測，為了防止長時間使用真值表導致真值表數值出錯或者傳輸過程中數據出錯，未發生故障時不需要從真值表中讀出對應輸出值。

3．3 故障修復庫

在系統運行時，電路可能發生各種類型的故障，通過預測電路發生的部分故障，利用演化硬件的方式提前生成該類故障的修復電路，并存儲于故障修復庫中。當該類故障發生時，直接查詢故障修復庫，利用庫中的修復配置信息恢復電路正常功能，提高修復速度。若發生的故障類型與修復庫中的修復電路不匹配，由于修復電路的結構位與故障電路一致，將其作為演化硬件的初始種群進行演化操作，加快演化速度，可更快得到對應的修復電路。

3．4 可重構模塊

由于在故障檢測時，不能夠準確分析故障類型，若故障為永久性故障，則需繞過故障位置，重新配置電路。如圖4所示，FPGA器件由多個可配置邏輯塊CLB(Configurable Logic Block)組成，當某個CLB發生故障后，隔離該CLB，由故障修復庫或者演化硬件技術得到的故障電路的配置信息直接下載到未使用的可配置區域，完成故障恢復。

3．5 演化修復機制

系統容錯是一個實時的過程，若演化機制不能夠在滿足實時性的約束條件下得到修復電路，系統功能將受到直接影響。對于演化硬件容錯技術而言，需要在滿足系統的故障修復時間之內得到故障電路的演化修復電路。在發生未知問題的情況下，采用演化算法演化電路占據了大部分的修復時間，因此一個好的演化算法對于提高演化硬件容錯技術的實時性有著關鍵性的作用。

傳統的遺傳算法通過選擇群體中優良個體，進行多次交叉、變異得到最優個體，但演化前期速度慢，后期容易破壞個體的優良模式，大大降低了演化效率［11，12］。粒子群算法則通過群體內部信息交流，逐步向歷史最優個體迭代，最終得到最優解，但在迭代后期，粒子群體不斷進化，逐漸向群體中最優個體聚集，導致后期種群多樣性差，全局優化能力減弱［13］。本文提出一種基于粒子群算法的改進遺傳算法IGA(Improved Genetic Algorithm)，交叉部分采用自適應交叉算子提高算法前期演化速度，演化后期通過考慮個體自身歷史最優適應度和群體內其他個體的歷史最優適應度，個體之間相互交流，向目標函數最優解移動，提高算法局部搜索能力。交叉和變異的公式如式(1)～式(4)所示:

其中，Pc、Mi分別為染色體的交叉算子和變異位數，favg、fmax為種群的平均適應度、最大適應度，fi、fimax、w分別為第i個染色體的適應度、i的歷史最優適應度及權重，t為染色體的演化代數，k1、c1、c2為常數值。在演化前期，采用較大的Pc和w，增強對新領域的探索能力，加快收斂速度;演化后期，隨著適應度的不斷增加，自適應減小Pc和w，避免破壞個體的優良模式，提高對局部位置的探索能力，突破局部最優解的限制。改進遺傳算法的流程如下所示:

算法1 IGA

4 實驗結果與分析

采用演化算法生成修復電路需要將電路結構映射為對應的染色體編碼串。為了綜合考慮染色體串的重配置時間開銷以及適應度計算開銷，實現更加有效的染色體編碼操作，本實驗采用了笛卡爾遺傳編碼和虛擬可重構電路技術VRC(Virtual Reconfigurable Circuit)［14］。虛擬可重構電路能夠簡化演化目標電路的復雜程度，進一步降低計算成本。

實驗采用Xilinx公司的Zynq UltraScale zcu102開發板，以2位乘法器及8位奇偶校驗器作為容錯演化的實驗對象。在zcu102開發板上搭建實時容錯系統，通過預測電路中可能發生的故障問題，利用演化算法預先生成對應的故障修復配置信息，并將其存入修復庫中。多次隨機注入故障，即通過使虛擬可重構電路中的某些功能矩陣的輸入端恒為0或1，使電路出現故障，盡可能地模擬自然環境下導致的電路故障，提高實驗可信度。實驗中比較重要的算法與電路結構參數如表1所示。

Table 1 Algorithm and circuit parameters表1 算法與電路參數

為了提高容錯方案的實時性，采用傳統的遺傳算法 SGA(Standard Genetic Algorithm)、自適應遺傳算法AGA(Adaptive Genetic Algorithm)、粒子群優化PSO(Particle Swarm Optimization)算法以及本文提出的改進遺傳算法IGA分別對容錯系統進行故障修復，對比實驗，驗證方案的實時性。實驗結果如圖5和圖6所示。

遺傳算法和粒子群算法都是從初始化隨機數開始，通過評價粒子或者染色體的適應值來決定群體對解空間的全局搜索方向，但粒子群算法不必對染色體進行復雜的選擇、交叉和變異操作。傳統遺傳算法中的交叉算子和變異算子對算法的全局搜索及局部微調能力影響很大，自適應遺傳算法雖然對交叉和變異作了一定改進，但當種群中群體平均適應度值接近種群最大適應度時，整體交叉率以及變異率都很低，導致演化的收斂速度變慢。相較于前兩種算法，粒子群算法通過共享粒子之間的信息優化種群染色體，收斂效率更高，但在演化后期，種群的多樣性較差，全局優化能力減弱。改進的遺傳算法隨著演化代數的增加，能夠根據染色體個體的適應度改變交叉算子和變異算子，演化前期使種群的平均適應度快速達到一個較高水平，后期由于個體的染色體適應度很接近最大適應度值，因此變異的位數也相應減少。通過這種方式在解空間中搜索最優解，每次變異只保留優質個體，能夠使算法突破局部最優解的限制。

由于8位奇偶校驗器結構較為簡單，4種算法在4 000代以內都能取得較好的結果，但改進的遺傳算法能夠在1 000代以內完成60%的電路修復，修復效果最為明顯。對于結構較為復雜的2位乘法器，改進的遺傳算法在1 000代以內能夠完成50%的故障修復，2 000代以內修復率達到80%，4 000代以內能夠完成90%的故障修復，對比其他算法，改進的遺傳算法對容錯方案的實時性提高最為明顯。由于演化硬件修復技術存在一定的隨機性，最終不一定能得到最優染色體，但迭代的局部最優染色體的適應值與最優染色體相差很小，能夠滿足絕大部分的電路功能，因此仍然可以將局部最優染色體用于配置修復電路，若再次運行檢測到故障，則再次進行演化修復。

表2為4種算法進行修復實驗的綜合對比表，改進遺傳算法和粒子群算法的修復成功率明顯優于其他兩種算法，但改進遺傳算法能夠更快地演化生成修復電路，更好地滿足容錯系統的實時性約束。對比Liu和Zhang的故障修復方案，二者均強調在線實時修復，卻無法保證修復過程中系統是否能夠正常運行，本文提出的容錯方案通過故障補償機制能夠有效保障修復過程中系統的正常功能，并通過高效的改進遺傳算法快速生成所需修復電路，進一步保障容錯的實時性，提高系統的可靠性和穩定性。

5 結束語

針對傳統演化容錯方案存在的修復能力有限、難以滿足實時性等問題，本文提出了基于演化硬件的實時系統容錯架構，當電子系統發生故障時通過故障分析樹快速定位故障源，利用故障補償機制維持系統正常功能，同時采用高效的演化修復機制快速演化得到修復電路，實現故障的在線實時修復。該容錯方案克服了故障電路修復約束期限無法預測、無法保證容錯方案實時性的問題，提高了系統的穩定性和可靠性。

Table 2 Comprehensive algorithm comparison表2 算法綜合對比