摘要：針對(duì)重構(gòu)文件的大小,、動(dòng)態(tài)容錯(cuò)時(shí)隙的長(zhǎng)短,、實(shí)現(xiàn)的復(fù)雜性、模塊間通信方式,、冗余資源的比例與布局等關(guān)鍵問題進(jìn)行了分析,。并對(duì)一些突出問題,，提出了基于算法和資源多級(jí)分塊的解決方法，闡述了新方法的性能,，及其具有的高靈活性高,、粒度等參數(shù)可選擇、重構(gòu)布線可靠性高,、系統(tǒng)工作頻率有保障的優(yōu)點(diǎn),。
關(guān)鍵詞：容錯(cuò)；動(dòng)態(tài)重構(gòu),；Retiming,；STARs

    太空中存在大量的宇宙射線和高能帶電粒子，它們對(duì)星載電子系統(tǒng)的照射會(huì)導(dǎo)致系統(tǒng)出錯(cuò),，甚至永久損壞,。其所造成的輻射效應(yīng)主要有位移損傷效應(yīng)、電離輻射總劑量效應(yīng),、瞬時(shí)電離輻射效應(yīng),、單粒子效應(yīng)等。而且由于器件集成度高,，每個(gè)記憶單元的尺寸小,，引起翻轉(zhuǎn)所需的臨界電荷也小，所以SEU的問題在空間器件上越來越嚴(yán)重,。
    現(xiàn)場(chǎng)可編程門陣列(FPGA,，F(xiàn)ield Programmable Gate Array)靈活、可重構(gòu)的特性,，對(duì)于克服器件設(shè)計(jì)錯(cuò)誤和后天所導(dǎo)致的故障有效,。基于可動(dòng)態(tài)可重構(gòu)FPGA,，動(dòng)態(tài)容錯(cuò)技術(shù)在理論上已得到發(fā)展,，并出現(xiàn)了多種方法，其基本原理都是將備用的配置文件重新裝載到FPGA上,，以消除原有的暫態(tài)錯(cuò)誤或者繞過故障區(qū),。
    但在實(shí)際應(yīng)用過程中涉及到許多問題。容錯(cuò)粒度的大小選擇,，是其中較突出的一個(gè),，這會(huì)影響到重構(gòu)文件的大小、動(dòng)態(tài)容錯(cuò)時(shí)隙的長(zhǎng)短,、資源利用率,、實(shí)現(xiàn)的復(fù)雜度等方面。另外模塊間通信方式,、檢錯(cuò)與定位的實(shí)現(xiàn),、冗余資源的比例與布局、暫態(tài)與永久錯(cuò)誤的處理與分析都是有待深入研究的問題,，很多方法過于復(fù)雜不容易實(shí)現(xiàn)或者過于簡(jiǎn)單而容錯(cuò)性能得不到保障,，并且對(duì)以上這些問題分析不充分。
    本文基于多種具體的實(shí)現(xiàn)方法,，對(duì)這些問題進(jìn)行了全面的分析與研究,，并權(quán)衡各個(gè)方面，提出了基于算法和資源多級(jí)分塊的方法,，對(duì)其性能進(jìn)行了分析,。
    這種方法中粒度、冗余資源比例等多項(xiàng)參數(shù)可以選擇,，重構(gòu)時(shí)沒有模塊間布線的要求,，能有效保障系統(tǒng)工作頻率。

1 基于動(dòng)態(tài)可重構(gòu)FPGA的幾種容錯(cuò)技術(shù)
1．1 基于Retiming理論的方法及分析
    重定時(shí)(Retimg)技術(shù)的應(yīng)用是建立在容錯(cuò)粒度較小的基礎(chǔ)上的一種容錯(cuò)方法,。它最初是針對(duì)靜態(tài)電路以優(yōu)化系統(tǒng)時(shí)鐘為目的,，且在整個(gè)電路設(shè)計(jì)過程中只使用一次。現(xiàn)在通過在FPGA中多次使用,，改變觸發(fā)器的位置以及增減觸發(fā)器的數(shù)量可以達(dá)到重構(gòu)的目的,，并保證整個(gè)系統(tǒng)的功能穩(wěn)定以及工作時(shí)序的協(xié)調(diào)。使用這種方法時(shí),，先根據(jù)約束條件生成一個(gè)Retiming矩陣,，這個(gè)矩陣決定了觸發(fā)器(FF)可能的各種布局。當(dāng)電路出現(xiàn)故障時(shí),，通過調(diào)用矩陣的信息重新定位不同的FF以使電路恢復(fù)正常,。
    這種方法主要的特點(diǎn)就是不改變系統(tǒng)的功能而改變系統(tǒng)的結(jié)構(gòu)特性，重構(gòu)策略簡(jiǎn)單,。如果結(jié)合可進(jìn)化算法,，處理器可以實(shí)時(shí)地計(jì)算得到有效的FF的重新布局?；赗etiming的實(shí)時(shí)重構(gòu)可以有效地降低暫態(tài)故障的影響,，尤其是SEU。同時(shí)這種方法配置文件量比較小,，粒度水平高,，重構(gòu)過程系統(tǒng)開銷小。
    但是由于這種方法對(duì)電路的重構(gòu)能力有限,，所以容錯(cuò)能力得到一定的限制,，尤其對(duì)于永久故障則容錯(cuò)率較低。其次,，當(dāng)完成FF的重新配置后,，電路需要一個(gè)初始化時(shí)間,，這個(gè)時(shí)間隨著電路規(guī)模的增大而增大，當(dāng)電路的規(guī)模和復(fù)雜度增大時(shí)這種方式的重構(gòu)將導(dǎo)致較大的系統(tǒng)開銷,，這樣電路規(guī)模受到限制并且對(duì)接口布線要求較高,。圖1所示給出了以相關(guān)器為例的兩種可能的重構(gòu)結(jié)構(gòu)，其中小方塊為FF,。

1．2 基于STARs的方法及分析
    基于移動(dòng)自檢測(cè)區(qū)域(STARs)的動(dòng)態(tài)容錯(cuò)技術(shù),，是一種基于FPGA的具有多種容錯(cuò)級(jí)別的在線容錯(cuò)技術(shù)。它不僅可以進(jìn)行邏輯工作區(qū)域的容錯(cuò),，也可以進(jìn)行布線區(qū)域的容錯(cuò),。
    基于STARs的方法，F(xiàn)PGA被劃分為系統(tǒng)工作區(qū)和檢測(cè)區(qū),，在檢測(cè)區(qū)中進(jìn)行內(nèi)建自測(cè)試,。若當(dāng)前的被檢測(cè)區(qū)完成被檢測(cè)后STAR和相鄰工作區(qū)的Slice交換位置，這樣依次進(jìn)行,，最終STAR可以覆蓋整個(gè)FPGA,。其優(yōu)勢(shì)是，檢測(cè)診斷總是在STAR中進(jìn)行,，不影響系統(tǒng)的工作,，可以有充足的時(shí)間來進(jìn)行精確的診斷和生成針對(duì)故障區(qū)的配置文件，并實(shí)現(xiàn)冗余,。

    這種方法采用了動(dòng)態(tài)系統(tǒng)時(shí)鐘的概念,。系統(tǒng)初始工作在最大時(shí)鐘頻率下，當(dāng)部分重構(gòu)使得某些部分的延時(shí)增加,，那么根據(jù)布線的時(shí)序分析結(jié)果,，通過周期可編程的時(shí)鐘產(chǎn)生器降低時(shí)鐘頻率，以滿足系統(tǒng)工作要求,。這克服了一般容錯(cuò)方法中系統(tǒng)在整個(gè)壽命期工作在較低時(shí)鐘頻率下的缺點(diǎn),。
    基于STARs的方法主要是針對(duì)永久性錯(cuò)誤，包括配置存儲(chǔ)器中的錯(cuò)誤,。STARs提供了一個(gè)相對(duì)于持續(xù)運(yùn)行的工作區(qū)的離線區(qū)域,。通過FPGA的邊界檢測(cè)接口可以使STAR中測(cè)試文件的配置動(dòng)態(tài)進(jìn)行而不影響系統(tǒng)工作。由于STARs的存在,，工作區(qū)或者是連續(xù)的,，或者是被STARs分割成不相連的區(qū)域，系統(tǒng)可以分別使用水平布線和垂直布線穿過V-STAR和H-STAR以實(shí)現(xiàn)通信,。
    這種方法采用了可編程邏輯塊(PLB)重用技術(shù),。PLB重用是指以一種沒有出錯(cuò)的模式來使用出錯(cuò)的PLB，即對(duì)在出故障的PLB中實(shí)現(xiàn)的功能來說這個(gè)PLB是沒有出故障的。這有兩種情況,，一是故障PLB中的損壞部分并沒有參與實(shí)現(xiàn)這個(gè)PLB內(nèi)的功能單元,，此時(shí)無需進(jìn)行重新配置。第二種情況的一個(gè)簡(jiǎn)單例子是,，當(dāng)一個(gè)LUT的某個(gè)存儲(chǔ)單元由于出錯(cuò)而固定置為0,，且這個(gè)LUT用來實(shí)現(xiàn)一個(gè)組合邏輯,，而此組合邏輯的這個(gè)存儲(chǔ)單元恰要求被設(shè)置為0,，那么這個(gè)錯(cuò)誤就不需要進(jìn)行冗余。由于PLBs的重用,，冗余資源的利用率得到提高,，容錯(cuò)量增大，系統(tǒng)壽命得到延長(zhǎng),。另外這還使得損壞的PLB利用較遠(yuǎn)距離的冗余資源來重構(gòu)而避開故障區(qū)的情況減少,，所以，隨著故障區(qū)增多,，系統(tǒng)的時(shí)鐘頻率不會(huì)明顯降低,。
    當(dāng)STAR位置改變時(shí)，系統(tǒng)時(shí)鐘必須停止以使STAR完成移動(dòng),。系統(tǒng)時(shí)鐘停止時(shí),，系統(tǒng)的工作狀態(tài)必須被存儲(chǔ)，并在系統(tǒng)時(shí)鐘重新啟動(dòng)前被復(fù)制到新的工作區(qū)域,。從STAR離開當(dāng)前這個(gè)區(qū)域到下一次再檢測(cè)這個(gè)區(qū)域的時(shí)間內(nèi),，工作區(qū)電路可能出錯(cuò)，這個(gè)時(shí)間稱為最壞的錯(cuò)誤駐留時(shí)間,。雖然基于STARs的方法,，檢測(cè)、診斷以及重構(gòu)過程在理論上可以不影響系統(tǒng)工作,，然而這也是它的缺點(diǎn),，不能對(duì)隨時(shí)出現(xiàn)的錯(cuò)誤進(jìn)行容錯(cuò)。因此,，必須考慮最壞的錯(cuò)誤駐留時(shí)間,，應(yīng)該提高檢測(cè)速度，而檢測(cè)速度的提高會(huì)使STARs的移動(dòng)速度提高,。這導(dǎo)致檢測(cè)區(qū)和工作區(qū)的交換頻率增加,，進(jìn)而影響系統(tǒng)工作的連續(xù)性。
1．3 基于遺傳算法及設(shè)計(jì)空間搜索的容錯(cuò)方法與分析
    在重構(gòu)容錯(cuò)的過程中,，由于技術(shù)的多樣性,，同時(shí)會(huì)有多種可行的方案，而這很難通過人工來分析比較得到最優(yōu)的解決方法。同時(shí)設(shè)計(jì)好的系統(tǒng)中必須有足夠的存儲(chǔ)量來存儲(chǔ)針對(duì)不同故障的重構(gòu)文件,。因此文獻(xiàn)提出了基于遺傳算法的空間搜索技術(shù),。
    首先用硬件設(shè)計(jì)語(yǔ)言描述系統(tǒng)功能，當(dāng)設(shè)計(jì)完成后,，對(duì)其實(shí)現(xiàn)功能進(jìn)行分析并產(chǎn)生一個(gè)向量圖,，節(jié)點(diǎn)表示功能單元，有向線段代表他們之間的鏈接,。同時(shí),，對(duì)源文件進(jìn)行綜合來識(shí)別其資源使用量(包括Slice數(shù)量，塊RAN數(shù)量等)和各個(gè)功能單元的特征,，最終形成一個(gè)功能單元庫(kù),。這個(gè)庫(kù)里面也包含一些標(biāo)準(zhǔn)器件和一些基本單元。另外在設(shè)計(jì)過程中還需要生成以下3個(gè)庫(kù)：
    器件特征庫(kù)：存儲(chǔ)對(duì)FPGA特征的描述,，包括可用資源容量,，基本重構(gòu)單元大小，重構(gòu)區(qū)域形狀約束,。
    技術(shù)庫(kù)：包含了部分重構(gòu)技術(shù)的模型,。
    參數(shù)庫(kù)：包含一些指導(dǎo)重構(gòu)過程并衡量重構(gòu)效果的參數(shù)。
    系統(tǒng)工作時(shí),，先將原功能模塊分成不同的組,。然后根據(jù)參數(shù)要求在每一組內(nèi)使用在技術(shù)庫(kù)里選擇的方法。遺傳算法用來產(chǎn)生不同的可行的染色體,，而染色體代表不同的處理方法,。這種算法與TMR結(jié)合的例子如圖4所示。

    基于遺傳算法的設(shè)計(jì)空間搜索方法需要設(shè)計(jì)者在前期作出大量工作,，例如,，遺傳算法的設(shè)計(jì)，約束條件以及各庫(kù)的形成,。其中遺傳算法的設(shè)計(jì)和參數(shù)設(shè)定是關(guān)鍵,，同時(shí)系統(tǒng)需要較強(qiáng)的計(jì)算能力，系統(tǒng)開銷較大,。不過其所需配置文件存儲(chǔ)量較小,，解決方法多樣，能產(chǎn)生出最優(yōu)的解決方案,。而且基于硬件遺傳算法具有廣闊的應(yīng)用前景,。

2 基于算法和資源多級(jí)分塊的容錯(cuò)結(jié)構(gòu)
2．1 方法的提出
    動(dòng)態(tài)容錯(cuò)粒度的選取是一個(gè)關(guān)鍵問題，如果粒度過小,，則對(duì)錯(cuò)誤的檢測(cè)定位能力要求較高,，而且配置文件復(fù)雜,，如果在線生成配置文件，則需要較強(qiáng)的系統(tǒng)計(jì)算能力,，這顯然會(huì)增大系統(tǒng)的開銷,，破壞系統(tǒng)的連續(xù)性，而且布線復(fù)雜,。如果粒度過大,，那么冗余資源的利用率降低，配置文件增大,，這削弱了系統(tǒng)的容錯(cuò)能力,，且需要較大的存儲(chǔ)資源。另外,，對(duì)冗余資源比例的選擇必須要考慮到系統(tǒng)布線難度,，而布線所造成的延遲是不可預(yù)知的，所以系統(tǒng)工作頻率也難以保證,。上面這幾種方法粒度水平不易改變，布線難度大,，系統(tǒng)時(shí)鐘性能不高,，而且后兩種實(shí)現(xiàn)難度較大。
    現(xiàn)在采取算法和資源多級(jí)分塊的方法進(jìn)行系統(tǒng)的容錯(cuò),?？梢栽诓桓姆椒ǖ那闆r下，通過對(duì)算法和資源不同次數(shù),、不同大小的劃分達(dá)到不同的粒度水平,，進(jìn)而滿足容錯(cuò)需要。因?yàn)橐运惴K為單位進(jìn)行重構(gòu),，且保證重構(gòu)前后模塊之間接口不變,，那么模塊外部無需重新布線，這樣就削減了容錯(cuò)時(shí)系統(tǒng)開銷,，不會(huì)降低時(shí)鐘頻率,。
    先將整個(gè)系統(tǒng)在減少模塊間布線難度的情況下按照算法分塊。然后將每個(gè)模塊所使用的資源在有2／9以9等分為例,，冗余資源的情況下進(jìn)行9等分,，這為第二級(jí)劃分。如圖5所示?，F(xiàn)在需要解決的是配置文件的設(shè)計(jì)以及布局的問題,。設(shè)計(jì)時(shí)，對(duì)實(shí)現(xiàn)相同功能的每—個(gè)算法模塊進(jìn)行多種不同的布局,，每—個(gè)布局都留出其中2／9的冗余資源,。當(dāng)然其算秸結(jié)構(gòu)可以不同，而實(shí)現(xiàn)相同功能的不同算法也可能會(huì)達(dá)到容錯(cuò)的效果，這將提高系統(tǒng)的容錯(cuò)能力,。相同功能算法的不同布局結(jié)構(gòu)如圖6所示,。

    基于算法和資源兩級(jí)分塊的容錯(cuò)結(jié)構(gòu)，在系統(tǒng)出現(xiàn)異常的情況下,，首先采用相同的配置文件對(duì)電路進(jìn)行重構(gòu),。重構(gòu)后如果異常消除，那么容錯(cuò)過程完成,，而且出現(xiàn)的錯(cuò)誤屬于暫態(tài)錯(cuò)誤,。在系統(tǒng)工作的過程中，需要周期性地記錄電路的狀態(tài),，當(dāng)出現(xiàn)故障然并進(jìn)行重構(gòu)后應(yīng)該將記錄的狀態(tài)進(jìn)行裝載,，以保持系統(tǒng)連續(xù)性及電路工作的正確性。如果這樣的重構(gòu)仍然沒有解決問題,，那么改變配置文件,，利用布局不同的配置文件進(jìn)行部分動(dòng)態(tài)重構(gòu)，用以解決永久性的故障,。重構(gòu)前后算法的功能應(yīng)該保持不變,，通過不同布局的重構(gòu)使電路可以繞開硬件故障區(qū)，達(dá)到容錯(cuò)的目的,。
    為解決重構(gòu)前后的通信問題,，采取類似總線宏(Bus Macro)的通信結(jié)構(gòu)，保持模塊間重構(gòu)前后通信布線不變,。而且每一次重構(gòu),，必須保證4個(gè)方向的通信端口和內(nèi)部模塊連接也不變，重構(gòu)后的電路都接在原有對(duì)外接口上,?？偩€宏只能用于相鄰的兩個(gè)模塊間的通信，對(duì)于不相鄰的模塊間的通信,，采用稱作可重構(gòu)多路總線(Recongigurable Multiple Bus)的動(dòng)態(tài)開關(guān)信號(hào)的通信結(jié)構(gòu),。以一維結(jié)構(gòu)為例，即現(xiàn)有模塊分布在一條線上,。當(dāng)一個(gè)模塊Mk需要和另一個(gè)不與自己相鄰的模塊通信時(shí),，它向與自己相鄰的且與要通信的模塊在相同方向上的模塊Mk+1發(fā)出請(qǐng)求，Mk+1再向Mk+2發(fā)出請(qǐng)求,，如是依次下去直到需要通信的模塊Mk+i收到信號(hào),，接著它以相反的路徑返回一個(gè)應(yīng)答信號(hào)，當(dāng)Mk收到應(yīng)答信號(hào)后,，兩者開始通信,。
2．2 方法分析
    假設(shè)在第二級(jí)劃分時(shí)將每一個(gè)模塊所占用的資源分成N2等分,，稱N為等分?jǐn)?shù)，冗余資源為N-1,，每一個(gè)資源單位出錯(cuò)概率為P(N),，則系統(tǒng)正常工作的概率為
   
    由仿真結(jié)果可知，隨著每一個(gè)模塊所占資源等分?jǐn)?shù)的增加,，系統(tǒng)容錯(cuò)能力提高,，而同時(shí)冗余資源所占的比例卻下降?？梢钥吹?，基于算法和資源的兩級(jí)分塊容錯(cuò)結(jié)構(gòu)，相對(duì)于以往基于模塊的重構(gòu)方法,，進(jìn)一步降低了系統(tǒng)的容錯(cuò)粒度,，提高了系統(tǒng)的容錯(cuò)率和冗余資源的使用效率，而且在容錯(cuò)的同時(shí)起到了檢錯(cuò)和定位的作用,。省去了實(shí)際用于檢錯(cuò)和定位的硬件或軟件開銷,，而且系統(tǒng)也不需要在線計(jì)算配置文件等，提高了系統(tǒng)的連續(xù)性和可靠性,。
    由于重構(gòu)前后模塊對(duì)外功能接口都不變,，相當(dāng)于一個(gè)電路黑盒子，節(jié)省了外部布局布線的時(shí)間和計(jì)算時(shí)間,，系統(tǒng)容錯(cuò)時(shí)開銷降低。其他的一些冗余方法,，例如以CLB為最小單元,，每次利用冗余資源繞過故障區(qū)需要復(fù)雜的布局布線，而這樣的布局布線所造成的延遲是難以避免的,，只有通過降低芯片工作頻率來保證系統(tǒng)時(shí)序的穩(wěn)定,。而現(xiàn)在所采取的結(jié)構(gòu)雖然在布局上進(jìn)行了兩次劃分，但是對(duì)于每一個(gè)模塊的外部仍然是基于功能模塊的容錯(cuò),，每次都是以經(jīng)過測(cè)試的成熟的功能算法為單元的,，不存在算法內(nèi)部重新布線后造成延遲的問題，保證了系統(tǒng)的高速運(yùn)行,，這也是本方法的主要特點(diǎn),。

    采用逐級(jí)劃分的方法可以合理的選擇所需的容錯(cuò)粒度，以及容錯(cuò)能力,?？墒请S著級(jí)數(shù)和對(duì)每一個(gè)模塊等分?jǐn)?shù)目的增加，預(yù)編譯的配置文件數(shù)量將增大,，這樣系統(tǒng)需要較多的存儲(chǔ)資源來存儲(chǔ)這些文件,。如果采用遺傳算法,，根據(jù)硬件資源與工作模塊的分級(jí)分塊結(jié)構(gòu)進(jìn)行在線計(jì)算，那么這個(gè)問題將得到解決,。

3 結(jié)束語(yǔ)
    文章對(duì)基于FPGA的動(dòng)態(tài)可重構(gòu)技術(shù)在容錯(cuò)領(lǐng)域的應(yīng)用進(jìn)行了研究,。針對(duì)重構(gòu)文件的大小，動(dòng)態(tài)容錯(cuò)時(shí)隙的長(zhǎng)短,、資源利用率,、實(shí)現(xiàn)的復(fù)雜性、模塊間通信方式,、冗余資源的比例與布局等方面的問題分析了一些方法的優(yōu)缺點(diǎn),，針對(duì)突出的問題，提出了一種基于算法和資源多級(jí)分塊的容錯(cuò)方法,，可以在不影響系統(tǒng)工作的情況下完成基于動(dòng)態(tài)重構(gòu)的容錯(cuò),。這種方法結(jié)構(gòu)簡(jiǎn)單，多項(xiàng)參數(shù)可以選擇,，尤其是粒度的可變性,。冗余資源比例較低，重構(gòu)時(shí)沒有對(duì)模塊外進(jìn)行布線的要求,，不會(huì)因重構(gòu)造成延遲而降低系統(tǒng)的工作頻率,。