基于FPGA的故障修復(fù)演化技術(shù)研究*

王 潔，康俊杰，周寬久

(大連理工大學(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)必須具備容錯(cuò)能力。傳統(tǒng)的容錯(cuò)技術(shù)主要采用冗余資源對故障進(jìn)行修復(fù)，但只能進(jìn)行容錯(cuò)，不具備故障檢測的能力，對整個(gè)電子系統(tǒng)均使用冗余資源難以實(shí)現(xiàn)。演化硬件EHW(Evolution Hard-Ware)技術(shù)能夠有效修復(fù)故障電路，但由于演化過程耗時(shí)較長且演化效率不高的缺陷，不能對整個(gè)硬件電路完成演化操作［1，2］。系統(tǒng)容錯(cuò)應(yīng)該是一個(gè)實(shí)時(shí)的過程，在故障發(fā)生之后，故障電路被隔離出系統(tǒng)，若不能在線實(shí)時(shí)完成故障的修復(fù)，將直接影響系統(tǒng)的正常運(yùn)行，甚至導(dǎo)致系統(tǒng)癱瘓［3］。

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

2 相關(guān)工作

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

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

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

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

3．1 故障檢測機(jī)制

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

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

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

3．2 故障補(bǔ)償機(jī)制

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

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

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

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

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

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

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

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

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

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

算法1 IGA

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

5 結(jié)束語

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

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