基于改進(jìn)二分查找的VRC快速故障定位技術(shù)

蔡金燕， 張峻賓,2， 孟亞峰

(1. 軍械工程學(xué)院 電子與光學(xué)工程系， 石家莊 050003;2. 中國(guó)空氣動(dòng)力研究與發(fā)展中心 超高速空氣動(dòng)力研究所, 四川 綿陽(yáng) 621000)

基于改進(jìn)二分查找的VRC快速故障定位技術(shù)

蔡金燕1， 張峻賓1,2， 孟亞峰1

(1. 軍械工程學(xué)院 電子與光學(xué)工程系， 石家莊 050003;2. 中國(guó)空氣動(dòng)力研究與發(fā)展中心 超高速空氣動(dòng)力研究所, 四川 綿陽(yáng) 621000)

針對(duì)虛擬可重構(gòu)電路(virtual reconfigurable circuits, VRC)故障定位難、傳統(tǒng)故障定位方法測(cè)試次數(shù)大等問(wèn)題，提出一種基于改進(jìn)二分查找的VRC快速故障定位技術(shù). 當(dāng)VRC規(guī)模不大于兩行(或兩列)時(shí)，直接逐行(逐列)定位故障. 當(dāng)VRC規(guī)模大于兩行和兩列時(shí)，首先執(zhí)行一次行測(cè)試和一次列測(cè)試，以確定可編程單元(programmable elements, PE)的故障可疑區(qū)域；然后比較故障可疑區(qū)域的行/列數(shù)量，以數(shù)量較少的作為故障測(cè)試方向；最后在測(cè)試方向上二分故障可疑區(qū)域，根據(jù)行/列測(cè)試原理配置電路并執(zhí)行“與”操作，根據(jù)輸出結(jié)果定位故障. 當(dāng)故障可疑區(qū)域無(wú)法二分時(shí)，可定位所有故障PE. 故障定位性能分析表明：和常規(guī)的VRC故障定位技術(shù)相比，本文提出的VRC快速故障定位技術(shù)能夠快速檢測(cè)并隔離連續(xù)分布的無(wú)故障PE，快速縮小測(cè)試區(qū)域，大幅度降低故障定位測(cè)試次數(shù)，且出現(xiàn)最大測(cè)試次數(shù)的概率遠(yuǎn)小于前者，單故障和雙故障定位的平均測(cè)試次數(shù)縮減量超過(guò)50%. 基于改進(jìn)二分查找的VRC快速故障定位技術(shù)的可行性和有效性得到驗(yàn)證，具有一定的通用性和工程應(yīng)用價(jià)值.

硬件演化；故障定位；虛擬可重構(gòu)電路；可編程單元；二分查找

硬件演化(evolvable hardware, EHW)技術(shù)在上世紀(jì)90年代已被提出，其具有的自組織、自適應(yīng)和自修復(fù)能力在電路故障修復(fù)領(lǐng)域發(fā)揮了重要作用[1-4]. 目前常將現(xiàn)場(chǎng)可編程門陣列(field programming gate array, FPGA)作為實(shí)現(xiàn)EHW的硬件基礎(chǔ)，但由于FPGA生產(chǎn)商均為外企，對(duì)外實(shí)行技術(shù)封鎖，除Xilinx的Virtex2系列芯片外，學(xué)者不能夠自由的訪問(wèn)/控制FPGA內(nèi)部邏輯單元和開(kāi)關(guān)盒[5-8]，對(duì)EHW技術(shù)的發(fā)展造成一定影響. 因此虛擬可重構(gòu)電路(virtual reconfigurable circuits, VRC)應(yīng)運(yùn)而生[9-11]，其能夠克服以上問(wèn)題.

VRC與故障自修復(fù)領(lǐng)域中的胚胎電子細(xì)胞都是可編程陣列[12-14]，因而具有相似性；由于可編程單元(programmable elements, PE)內(nèi)部結(jié)構(gòu)和PE間互聯(lián)不同，又具有差異性. 雖然現(xiàn)有偽窮舉測(cè)試法、布爾差分法、D算法等故障定位方法[15-17]，但都針對(duì)具體電路，需輸入測(cè)試序列. 而VRC結(jié)構(gòu)具有特殊性，使得數(shù)字電路常用測(cè)試方法不適用. 常規(guī)的VRC故障定位方法主要進(jìn)行逐行(列)測(cè)試，且需對(duì)PE的所有邏輯功能進(jìn)行測(cè)試，因此VRC的行(列)數(shù)決定了測(cè)試的次數(shù)，容易造成測(cè)試次數(shù)大等問(wèn)題. 一些文獻(xiàn)提出將可能存在故障的行(列)所有PE單獨(dú)連接至無(wú)故障的行(列)進(jìn)行測(cè)試，在故障可能存在的行(列)較少時(shí)，且無(wú)故障行(列)較多和每行(列)的PE數(shù)量較少時(shí)才使用，否則將無(wú)足夠無(wú)故障行(列)供使用[18]. 另有很多文獻(xiàn)只研究VRC的使用，而回避VRC故障定位[9-10, 19].

本文提出一種基于改進(jìn)二分查找的VRC快速故障定位技術(shù). 首先采用一次行測(cè)試和一次列測(cè)試確定故障可疑區(qū)域，然后根據(jù)故障可疑區(qū)域的規(guī)模確定測(cè)試方向，最后采用二分查找技術(shù)對(duì)故障可疑區(qū)域進(jìn)行故障定位. 通過(guò)對(duì)本文提出的故障定位方法進(jìn)行性能分析，所提方法的可行性和有效性得到驗(yàn)證.

1 VRC平臺(tái)基本原理

EHW技術(shù)主要有內(nèi)部演化(intrinsic EHW)和外部演化(extrinsic EHW) 兩種方式. 而基于VRC的電路演化平臺(tái)，也包含內(nèi)部演化和外部演化兩種演化方式[1, 2, 4, 20].

VRC是一種基于FPGA中可編程邏輯單元重新封裝后的可重構(gòu)平臺(tái)[9-11, 19]，是由多個(gè)PE構(gòu)成陣列，也稱PE為function elements(FE)[9]. 每個(gè)PE可實(shí)現(xiàn)任意二輸入邏輯功能，其中包括與、或、非、異或、與或、同或、與非、或非、D觸發(fā)器共8種邏輯. 有些文獻(xiàn)設(shè)計(jì)的PE只包含8種邏輯中的部分邏輯. VRC構(gòu)成示意見(jiàn)圖1.

圖1 VRC構(gòu)成示意

圖1中的a和b為輸入信號(hào)，c為輸出信號(hào)，fFD為PE功能表達(dá)配置數(shù)據(jù)，clk為時(shí)鐘. VRC平臺(tái)中的PE還可具有圖2所示結(jié)構(gòu)[19]，同圖1(a)中的PE結(jié)構(gòu)具備相同功能. PE互聯(lián)網(wǎng)絡(luò)示意見(jiàn)圖3.

圖2 另一種PE內(nèi)部結(jié)構(gòu)示意

圖3 VRC互聯(lián)網(wǎng)絡(luò)示意

從圖3可看出，針對(duì)規(guī)模為M行N列的VRC，每個(gè)PE的輸出端均互聯(lián)至整個(gè)VRC，每個(gè)PE的每個(gè)輸入端均有一個(gè)M×N到一的多路選擇器(multiplexer, MUX)，將所有PE輸出端連接至具有M×N個(gè)輸入一個(gè)輸出的MUX，使得VRC中每個(gè)PE輸出端能夠接入任意PE的輸入端.

對(duì)MUX的M×N個(gè)輸入端進(jìn)行二進(jìn)制計(jì)算，對(duì)應(yīng)的位數(shù)為所有MUX控制信號(hào)的編碼長(zhǎng)度. 假如M×N=60，其二進(jìn)制編碼為111 100，控制MUX的信號(hào)編碼長(zhǎng)度為6位.

2 基于改進(jìn)二分查找的VRC快速故障定位技術(shù)

本文提出的基于改進(jìn)二分查找的VRC快速故障定位技術(shù)的主要原理如下：首先實(shí)施一次行測(cè)試和一次列測(cè)試確定故障可疑區(qū)域，再采用二分查找技術(shù)對(duì)故障可疑區(qū)域進(jìn)行故障定位.

對(duì)VRC實(shí)施行/列測(cè)試的PE連接/配置方法分別見(jiàn)圖4和圖5.

圖4 VRC行測(cè)試配置方法

圖5 VRC列測(cè)試配置方法

圖4和圖5中的yr1～yr5和yc1～yc6分別對(duì)應(yīng)行測(cè)試和列測(cè)試的每路輸出信號(hào). 行/列測(cè)試時(shí)通過(guò)改變輸入端a和b的值，保證每個(gè)PE能將邏輯1順利輸出到端口. 比如在測(cè)試PE的邏輯“與”功能時(shí)，輸入信號(hào)a和b需同時(shí)輸入1，或同時(shí)輸入0. 如果輸入1時(shí)輸出為1，且輸入0時(shí)輸出為0，代表無(wú)故障，反之則有故障. 將經(jīng)過(guò)行測(cè)試和列測(cè)試后的交叉區(qū)域記為故障PE可疑區(qū)域見(jiàn)圖6.

圖6 VRC故障PE可疑區(qū)域

經(jīng)過(guò)行測(cè)試后，確定第2～4行存在故障；經(jīng)過(guò)列測(cè)試后，確定第2～5列存在故障. 此時(shí)的故障可疑區(qū)域不只一行和一列.

在基于行測(cè)試、列測(cè)試和故障可疑區(qū)域基礎(chǔ)之上，基于改進(jìn)二分查找的VRC快速故障定位技術(shù)實(shí)現(xiàn)流程如下：

Step1首先進(jìn)行行測(cè)試和列測(cè)試，確定故障可疑區(qū)域.

Step2判斷VRC故障可疑區(qū)域的大小，假設(shè)可疑區(qū)域規(guī)模為m行n列，且m≤n. 判斷VRC不在可疑區(qū)域內(nèi)的PE(即無(wú)故障PE)數(shù)量k，如果k≥n，轉(zhuǎn)入Step3；反之，則轉(zhuǎn)入Step6.

Step3采用二分查找法，將可疑區(qū)域每一列平分(偶數(shù)直接平分，奇數(shù)平分時(shí)一邊可多一個(gè)PE)，分別按圖5方式縱向連接，并將兩路信號(hào)送入此列無(wú)故障PE進(jìn)行“與”操作. 如果此列沒(méi)有無(wú)故障PE，則選擇其它列多余的無(wú)故障PE進(jìn)行“與”操作. 如果輸出值為1，判定上/下兩部分均存在故障，并轉(zhuǎn)入Step4；如果輸出值為0，判斷上/下部分中有一部分存在故障，并轉(zhuǎn)入Step5.

Step4當(dāng)平分后的上/下兩部分均存在故障時(shí)，對(duì)上部分進(jìn)行再次平分，按照Step3的步驟進(jìn)行故障定位. 在上部分故障定位完畢后，再對(duì)下部分故障定位. 依此進(jìn)行，直到可疑區(qū)域的故障完全定位為止.

Step5當(dāng)平分后的上/下兩部分只有一部分存在故障時(shí)，首先測(cè)試上/下部分的任意部分. 如果測(cè)試出上部分(下部分)無(wú)故障，則下部分(上部分)必存在故障，此時(shí)測(cè)試次數(shù)將大大縮減.

Step6在Step2中確定可疑區(qū)域后，當(dāng)k

在上述測(cè)試流程中，如果VRC中故障PE只存在某一行或某一列，只需一次行測(cè)試和一次列測(cè)試即可定位故障. 詳細(xì)的二分法查找過(guò)程見(jiàn)圖7.

圖7 極端情形下二分查找故障定位過(guò)程

Fig.7 Binary search process of fault localization under extreme circumstances

圖7所示測(cè)試步驟包含極端情形下的測(cè)試次數(shù)，將可疑區(qū)域中的某一行分離出來(lái)單獨(dú)演示，包含7個(gè)PE，分別用字母D1～D7表示，測(cè)試點(diǎn)用f1～f10表示. 在非極端情形下，圖7中一些測(cè)試步驟可省略. 此時(shí)的極端情形主要指：在二分過(guò)程中且還未最小二分時(shí)，兩側(cè)測(cè)試始終顯示有故障；在最小二分時(shí)，兩側(cè)測(cè)試顯示無(wú)故障.

圖7中f1、f2屬于中間過(guò)程的二分，而f3、f5、f7和f8屬于最小二分，且以上均屬于節(jié)點(diǎn)測(cè)試，f4、f6、f9和f10屬于邏輯塊功能測(cè)試. 圖7中只要D7無(wú)故障，且D1和D2、D3和D4、D5和D6每對(duì)中只要有一個(gè)故障，將造成最大測(cè)試次數(shù). 即至少存在4個(gè)故障PE，相當(dāng)于至少4/7的PE出現(xiàn)故障，而4/7的PE出現(xiàn)故障的概率極小.

3 故障定位性能分析

故障定位性能分析，主要關(guān)注故障全部定位情況下的測(cè)試次數(shù)，通常情況下，測(cè)試次數(shù)越少越好. 常規(guī)測(cè)試方法需進(jìn)行逐行(或逐列)測(cè)試. 在對(duì)比分析中，設(shè)定測(cè)試順序從上至下(從左至右). 針對(duì)VRC規(guī)模為M行N列，且M≤N，常規(guī)的故障定位方法最大測(cè)試次數(shù)為M次. 本文提出的基于改進(jìn)二分查找的VRC快速定位技術(shù)，在極端情形下的最大測(cè)試次數(shù)為G(x)，其中x代表圖6中故障可疑區(qū)域的行數(shù)和列數(shù)的最小值，不是VRC中故障PE的數(shù)量(用h表示，h∈N+).

在故障定位過(guò)程中，確定故障可疑區(qū)域需要測(cè)試兩次. 當(dāng)PE數(shù)量取2的對(duì)數(shù)為整數(shù)時(shí)(即PE數(shù)量等于2x，x∈N+)，極端情形下需測(cè)試分界點(diǎn)，x個(gè)PE有x-1個(gè)分界點(diǎn)，需測(cè)試x-1次. 當(dāng)兩個(gè)PE為一組時(shí)，x個(gè)PE最后細(xì)分為0.5x等分. 對(duì)每個(gè)等分進(jìn)行故障確認(rèn)需測(cè)試1次，測(cè)試次數(shù)合計(jì)為1.5x+1. 在x個(gè)PE基礎(chǔ)上，每增加1個(gè)PE，測(cè)試次數(shù)將增加兩次(1次分界點(diǎn)測(cè)試，1次確認(rèn)測(cè)試)；在x個(gè)PE基礎(chǔ)上增加的PE數(shù)量多余0.5x時(shí)，每增加1個(gè)PE將增加1次測(cè)試(分界點(diǎn)測(cè)試). 因此，G(x)為

G(x)=

(1)

相比傳統(tǒng)的故障定位方法，雖然本文提出的故障定位技術(shù)在極端情形下的測(cè)試次數(shù)最大增加約一半，但只存在于極端情況下，即整個(gè)VRC陣列均存在故障. 在當(dāng)VRC出現(xiàn)故障PE數(shù)量占VRC總PE數(shù)量≤50%時(shí)，本文提出的VRC快速故障定位技術(shù)將具有明顯的優(yōu)勢(shì).

由于VRC陣列PE的結(jié)構(gòu)一樣，因此出現(xiàn)故障概率也一樣. 假設(shè)一個(gè)PE出現(xiàn)故障的概率為p，則k個(gè)PE出現(xiàn)故障的概率服從二項(xiàng)分布，且為

(2)

式中:X為PE總數(shù)，λ為失效率，t為工作時(shí)間，p=1-e-λt. 當(dāng)λ=1×10-5、t=24×365、λ分別為3個(gè)不同失效率值、故障PE概率累積量大于99%時(shí)，h與X的比值為phX見(jiàn)圖8.

圖8 概率累積量大于99%時(shí)故障PE數(shù)量占總數(shù)量百分比

Fig.8 Ratio of the number of fault PE of total number when probability cumulant is larger than 99%

圖8中，隨著VRC規(guī)模的增大，無(wú)論λ是0.8×10-5、1.0×10-5還是1.2×10-5，phX始終呈下降趨勢(shì)，且慢慢趨于穩(wěn)定. 當(dāng)X≤4時(shí)，故障PE數(shù)量占總PE數(shù)量的百分比才會(huì)超過(guò)50%.

當(dāng)X<4時(shí)，PE只能排成一行或一列，采用本文提出的故障定位技術(shù)，只需兩次測(cè)試. 當(dāng)X=4時(shí)，如果4個(gè)PE排成一行或一列，只需兩次測(cè)試. 但如果4個(gè)PE呈兩行兩列的陣列排列時(shí)，取消可疑區(qū)域測(cè)試，只進(jìn)行二分查找測(cè)試，需測(cè)試兩次. 當(dāng)X>4時(shí)，X越大，不到50%的PE存在故障的概率為0.99，當(dāng)VRC規(guī)模大于200個(gè)時(shí)，少于20%的PE存在故障的概率為0.99. 此時(shí)，本文提出的故障快速定位技術(shù)將具有明顯優(yōu)勢(shì).

對(duì)于規(guī)模為10×10的VRC，只有當(dāng)h>14時(shí)，且在特定故障布局下，才可能造成最大測(cè)試次數(shù)，見(jiàn)圖9.

(a) 示例一 (b) 示例二

圖9中只給出了兩種故障PE分布示意圖. 其中，深色方塊代表故障PE，白色方塊代表無(wú)故障PE. 造成最大測(cè)試次數(shù)的必要條件如下：一是有一列或一行中每隔一個(gè)PE必須存在故障，而間隔中的PE可有故障也可無(wú)故障. 二是除開(kāi)當(dāng)前列(行)，剩余的故障PE不能出現(xiàn)在同一行或同一列. 圖10 展示了不同h值造成相同故障可疑區(qū)域的示例.

(a) 故障頒布一 (b) 故障頒布二 (c) 故障頒布三

Fig.10 Instances of the same fault PE shadiness area under different value ofh

造成最大測(cè)試次數(shù)單獨(dú)列出現(xiàn)的最少故障數(shù)量為H(x)

(3)

造成最大測(cè)試次數(shù)的可疑區(qū)域最小h值用為H1(x)

H1(x)=H(x)+x-1x∈N+.

(4)

深入研究規(guī)模為10×10的VRC，采用常規(guī)方法進(jìn)行故障定位，當(dāng)從上至下定位時(shí)，只要最后一行出現(xiàn)故障，將造成最大測(cè)試次數(shù). 對(duì)應(yīng)不同h值造成最大測(cè)試次數(shù)的概率用P1(x)為

(5)

在采用本文提出的方法時(shí)，按照式(3)和式(4)的計(jì)算規(guī)則，故障PE可疑區(qū)域?yàn)?0×10的最小h=13. 其不同h值造成最大測(cè)試次數(shù)的概率為P2(x)

(6)

式(6)中的P3(x)可表示為

(7)

從式(6)、(7)可看出，當(dāng)x∈[1,13],x∈N+時(shí)，式(6)屬于精確計(jì)算，當(dāng)x≥14,x∈N+時(shí)，式(6)屬于近似范圍計(jì)算. 當(dāng)計(jì)算的近似值比真值大時(shí)，造成最大測(cè)試次數(shù)概率遠(yuǎn)遠(yuǎn)低于常規(guī)方法造成最大測(cè)試次數(shù)的概率.

令每個(gè)PE的失效率λ=1.0×10-5，t=24×365，VRC不同數(shù)量PE出現(xiàn)故障的概率和對(duì)應(yīng)的概率累積量見(jiàn)圖11.

圖11 VRC不同數(shù)量故障PE故障出現(xiàn)概率及概率累積量

Fig.11 Fault probability and fault probability cumulant of VRC in different number of PEs

從圖11中可看出，當(dāng)VRC的故障PE概率累積量達(dá)到99.9%時(shí)，對(duì)應(yīng)有min(h)=18. 因此只計(jì)算最多18個(gè)PE出現(xiàn)故障，故障定位相關(guān)參數(shù)見(jiàn)表1，表1中造成最大測(cè)試次數(shù)的故障分布和故障隨機(jī)分布的比率用S表.

表1 VRC陣列(規(guī)模為10×10)故障定位相關(guān)參數(shù)

從表1可看出，常規(guī)故障定位方法最大測(cè)試次數(shù)始終為10次. 本文提出的故障定位方法最大測(cè)試次數(shù)，在h<7時(shí)明顯低于前者. 當(dāng)h≥7時(shí)大于前者，最大增加量約為一半. 但本文提出的方法造成最大測(cè)試次數(shù)的故障PE需特殊布局，且相同數(shù)量故障PE特殊布局所出現(xiàn)的概率. 在h=7時(shí)，常規(guī)方法是本文提出方法的118倍；h=10時(shí)是3.19×106倍；h=13是2.34×107倍；即使在近似計(jì)算h=18時(shí)，前者也為后者的5.03×103倍.

當(dāng)h值確定時(shí)，常規(guī)故障定位方法始終有S=0.1. 采用本文提出的方法，當(dāng)h≤6時(shí)，雖然S>0.1，但是此時(shí)的最大測(cè)試次數(shù)小于常規(guī)方法的測(cè)試次數(shù). 當(dāng)h>6時(shí)，雖然最大測(cè)試次數(shù)大于常規(guī)測(cè)試方法，但此時(shí)S遠(yuǎn)小于0.1，之間差距從40倍到3.06×106倍不等.

排除極端情形下造成最大測(cè)試次數(shù)，當(dāng)實(shí)例中h≤6時(shí)，只要VRC最后一行存在故障PE，常規(guī)方法的測(cè)試次數(shù)大于本文提出的方法. 如果7個(gè)故障PE全在第一行，本文提出的故障定位方法將需兩次測(cè)試，而常規(guī)方法只需一次測(cè)試，但是7個(gè)故障全在第一行的概率只有7.50×10-8. 當(dāng)h>6時(shí)，需根據(jù)具體的故障PE分布分析故障測(cè)試次數(shù). 常規(guī)方法存在10%造成最大次數(shù)的概率，雖然本文提出的方法存在最大測(cè)試次數(shù)大于常規(guī)方法的可能性，但其概率低于1.94×10-4，甚至更小.

例如，當(dāng)VRC陣列只有1個(gè)故障時(shí)，常規(guī)方法檢測(cè)次數(shù)少于兩次的概率為20%，即80%的檢測(cè)次數(shù)都大于2次. 而采用本文提出的方法，測(cè)試次數(shù)只使用兩次. 對(duì)于雙故障，常規(guī)方法93.03%的檢測(cè)次數(shù)大于4次. 而采用本文提出方法的最大測(cè)試次數(shù)為4次(2次測(cè)試占3.64%，4次測(cè)試占96.36%).

當(dāng)h=7時(shí)，如圖12所示的故障分布. 由于每個(gè)故障分布在不同的行和列，常規(guī)測(cè)試方法需進(jìn)行10次測(cè)試，才能將7個(gè)故障PE完全定位. 而采用本文方法只需進(jìn)行8次測(cè)試，中間3行連續(xù)分布的無(wú)故障PE得到快速隔離.

圖12 VRC中7個(gè)故障PE分布

綜上所述，故障定位的測(cè)試次數(shù)和故障PE的分布密切相關(guān). 常規(guī)故障定位方法，無(wú)論某行/列是否存在故障PE，均需要測(cè)試一次. 本文提出的故障定位方法能夠?qū)o(wú)故障的行/列排除，只對(duì)故障可疑區(qū)域進(jìn)行二分查找測(cè)試，從而降低故障測(cè)試次數(shù).

4 結(jié) 論

針對(duì)目前VRC陣列故障定位方法單一、故障定位難及定位測(cè)試次數(shù)大等問(wèn)題，本文提出一種基于改進(jìn)二分查找的VRC快速故障定位技術(shù).

和常規(guī)故障定位技術(shù)相比，本文提出的故障快速定位技術(shù)能夠避免對(duì)連續(xù)分布的無(wú)故障PE進(jìn)行測(cè)試，縮小測(cè)試區(qū)域，且造成最大測(cè)試次數(shù)的概率遠(yuǎn)小于前者，對(duì)單故障和雙故障定位時(shí)的測(cè)試次數(shù)縮減量超過(guò)50%.

通過(guò)故障定位性能分析，本文提出的基于改進(jìn)二分查找的VRC快速故障定位技術(shù)的可行性和有效性得到驗(yàn)證，具有一定通用性和工程應(yīng)用價(jià)值.

[1] PAULINE C H, ANDY M T. Challenges of evolvable hardware: past, present and the path to a promising future[J]. Genetic Programming and Evolvable Machines, 2011, 12(3): 183-215.

[2] HORNBY G S, LOHN J D, LINDEN D S. Computer- automated evolution of an x-band antenna for NASA's space technology 5 mission[J]. Evolutionary Computation, 2011, 19(1): 1-23.

[3] HIHUCHI T, IWATA M, KAJITANI I, et al. Evolvable hardware and its applications to pattern recognition and fault tolerant systems[J]. Lecture Notes in Computer Science, 1996, 1062:118-135.

[4] ZHANG Junbin, CAI Jinyan, MENG Yafeng, et al. Fault self-repair strategy based on evolvable hardware and reparation balance technology[J]. Chinese Journal of Aeronautics, 2014, 27(5): 1211-1222.

[5] YAN S L, CHEN Y, PU Q M. A new evolutionary hardware system using FPGAS[C]//Proceeding of International Colloquium on Computing, Communication, Control, and Management. Piscataway, NJ: IEEE Press, 2009: 82-85.

[6] LOPEZ-BUEDO S, GARRIDO J, BOEMO E I. Dynamically inserting, operating, and eliminating thermal sensors of FPGA-based systems[J]. IEEE Transactions on Components and Packing Technologies, 2002, 25(4): 561-566.

[7] DAS N, ROY P, RAHAMAN H. Runtime congestion and crosstalk aware router for FPGA using jbits3.0 for partial reconfigurable[C]//Proceeding of International Symposium on Electronic System Design. Piscataway, NJ: IEEE Press, 2011: 146-151.

[8] 任小西, 李仁發(fā), 金聲震, 等. 基于JBits的一種可重構(gòu)數(shù)據(jù)處理系統(tǒng)可靠性研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(4): 722-728.

REN Xiaoxi, LI Renfa, JIN Shengzhen, et al. Research on reliability of a reconfigurable data processing system based on jbits[J]. Journal of Computer Research and Development, 2007, 44(4): 722-728.

[9] WANG Jin, LEE C H. Virtual reconfigurable architecture for evolving combinational logic circuits[J]. Journal of Central South University, 2014, 21(5): 1862-1870.

[10]OMAR E, IMBABY I M, MOHAMED K R, et al. Hardware implementation of virtual reconfigurable circuit for fault tolerant evolvable hardware system on FPGA[J]. American Journal of Engineering and Technology Research, 2015, 15(1): 2015.

[11]樸昌浩, 王進(jìn), 孫志華, 等. 自適應(yīng)變異比率控制在虛擬可重構(gòu)結(jié)構(gòu)中的應(yīng)用[J]. 高技術(shù)通訊, 2010, 20(4): 398-402.

PIAO Changhao, WANG Jin, SUN Zhihua, et al. Applying self-adaptive mutation rate control to virtual reconfigurable architecture[J]. Chinese High Technology Letters, 2010, 20(4): 398-402.

[12]蔡金燕, 朱賽, 孟亞峰. 一種新型的仿生電子細(xì)胞基因存儲(chǔ)結(jié)構(gòu)[J]. 電子學(xué)報(bào), 2016, 44(8): 1915-1924.

CAI Jinyan, ZHU Sai, MENG Yafeng.A novel gene memory structure for bio-inspired electronic cell[J]. Acta Electronica Sinica, 2016, 44(8): 1915-1924.

[13]王南天, 錢彥嶺, 李岳, 等. 胚胎型在線自修復(fù)FIR濾波器研究[J]. 儀器儀表學(xué)報(bào), 2012, 33(6): 1385-1391.

WANG Nantian, QIAN Yanling, LI Yue, et al. Study of embryonic type on-line self-healing FIR filters[J]. Chinese Journal of Scientific Instrument, 2012, 33(6): 1385-1391.

[14]XU Guili, XIA Zhenghao, WANG Haibin, et al. Design of embryo-electronic systems capable of self-diagnosing and self-healing and configuration control[J]. Chinese Journal of Aeronautics, 2009, 22(6): 637-643.

[15]朱敏, 王石記, 楊春玲. 改進(jìn)Tent混沌序列的數(shù)字電路BIST技術(shù)[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 2010, 42(4): 607-611.

ZHU Min, WANG Shiji, YANG Chunling. BIST technique of digital circuits based on improved tent chaotic sequence[J]. Journal of Harbin Institute of Technology, 2010, 42(4): 607-611. DOI: 10.11918/j.issn. 0367-6234.2010.04.022.

[16]楊德才,陳光礻禹, 謝永樂(lè). 進(jìn)位保留陣列乘法器的一種內(nèi)建自測(cè)試[J]. 電子科技大學(xué)學(xué)報(bào), 2007,36(4):751-754.

YANG Decai, CHEN Guangju, XIE Yongle. A built-in self-test scheme for carry save array multiplier[J]. Journal of University of Electronic Science and Technology of China, 2007, 36(4): 751-754.

[17]潘張?chǎng)? 陳偕雄. 或-符合型通用邏輯門組合電路的故障檢測(cè)[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版), 2007, 41(8): 1260-1264.

PAN Zhangxin, CHEN Xiexiong. Faults detection in combinational circuits of OR-coincidence type universal logic gates[J]. Journal of Zhejiang University (Engineering Science), 2007, 41(8): 1260-1264.

[18]婁建安, 崔新風(fēng), 褚杰. 基于類神經(jīng)網(wǎng)絡(luò)模型的電路自主修復(fù)方法[J]. 軍械工程學(xué)院學(xué)報(bào), 2010,22(6):46-49.

LOU Jian'an, CUI Xinfeng, CHU Jie. Self-repairing method of the electronic circuit based on neural network model[J]. Journal of Ordnance Engineering College, 2010, 22(6): 46-49.

[19]張峻賓, 蔡金燕, 孟亞峰. 面向復(fù)雜電磁環(huán)境的容錯(cuò)電路系統(tǒng)設(shè)計(jì)技術(shù)[J]. 西安交通大學(xué)學(xué)報(bào), 2017, 51(2): 53-59.

ZHANG Junbin, CAI Jinyan, MENG Yafeng. A design technology of fault tolerance circuit systems facing complex electromagnetic environments[J]. Journal of Xi′an Jiaotong University, 2017, 51(2): 53-59.

[20]李杰,黃士坦. 可進(jìn)化硬件的動(dòng)態(tài)進(jìn)化[J]. 武漢大學(xué)學(xué)報(bào), 2008, 41(6): 103-107.

LI Jie, HUANG Shitan. Dynamic evolution for evolvable hardware[J]. Engineering Journal of Wuhan University, 2008, 41(6): 103-107.

RapidfaultlocalizationtechnologyofVRCbasedonimprovedbinarysearch

CAI Jinyan1, ZHANG Junbin1,2, MENG Yafeng1

(1. Department of Electronic and Optical Engineering, Ordnance Engineering College, Shijiazhuang 050003, China;2. China Aerodynamics Research & Development Center, Hypervelocity Aerodynamics Institute, Mianyang 621000, China)

According to difficult fault localization of virtual reconfigurable circuits (VRC) and large test times of traditional fault localization technology, a novel rapid fault localization technology of VRC based on improved binary search is proposed. When the scales of VRC are no more than two rows (or two columns), fault PE can be located line by line (or column by column). When the scales of VRC are larger than two rows and two columns, the fault dubitable area of programmable elements (PE) can be confirmed by one row-test and one column-test, and then the test direction can be confirmed through the number of rows and columns of fault dubitable area. Eventually, fault dubitable area can be divided equally in the test direction, and two parts can be configured based on the theory of row-test and column-test. Faults can be located by “AND” operation of two parts. All faults PE can be located until fault dubitable area can not divided two parts. Compared with traditional VRC fault localization technology, the test performance analysis of fault localization proves that continuous distribution trouble-free PE can be detected and isolated by proposed VRC fault localization technology, and test area can be narrowed quickly. The test number of faults localization can be reduced, and the maximum test numbers are smaller than former. The average decrement of single and dual fault localization test number is more than 50%. The feasibility and validity of proposed improved rapid fault localization technology are proved, and it has definite generality and engineering application value.

evolvable hardware (EHW); fault localization; virtual reconfigurable circuits(VRC); programmable elements(PE); binary search

10.11918/j.issn.0367-6234.201612042

TP302.8

A

0367-6234(2017)11-0151-07

2016-12-9.

國(guó)家自然科學(xué)基金(61372039, 61601495)

蔡金燕(1961—)，女，教授，博士生導(dǎo)師

蔡金燕，cjyrad@163.com

(編輯苗秀芝)