王 潔，康俊杰，周寬久

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

1 引言

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

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

2 相關(guān)工作

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

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

3 演化硬件實時容錯系統(tǒng)

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

3．1 故障檢測機制

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

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

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

3．2 故障補償機制

故障檢測定位故障源電路后，需要對故障電路進行隔離，此時系統(tǒng)仍需正常運行。由于電路系統(tǒng)的結(jié)構(gòu)復(fù)雜，無法預(yù)測故障電路的修復(fù)約束期限，若不能在約束期限內(nèi)完成故障的修復(fù)，則系統(tǒng)的運行直接受到影響，甚至導(dǎo)致嚴(yán)重后果。

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

3．3 故障修復(fù)庫

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

3．4 可重構(gòu)模塊

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

3．5 演化修復(fù)機制

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

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

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

算法1 IGA

4 實驗結(jié)果與分析

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

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

Table 1 Algorithm and circuit parameters表1 算法與電路參數(shù)

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

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

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

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

5 結(jié)束語

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

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