基于相關(guān)性分離的邏輯電路敏感門定位算法

蔡 爍 何輝煌 余 飛 尹來容 劉 洋

①(長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院 長(zhǎng)沙 410114)

②(長(zhǎng)沙理工大學(xué)汽車與機(jī)械工程學(xué)院 長(zhǎng)沙 410114)

③(中通服咨詢?cè)O(shè)計(jì)研究院有限公司 南京 210019)

1 引言

隨著互補(bǔ)金屬氧化半導(dǎo)體(Complementary Metal Oxide Semiconductor, CMOS)器件特征尺寸持續(xù)縮小，電路規(guī)模不斷增大，芯片的速度、功耗等性能得到穩(wěn)步提升。但與此同時(shí)，工藝擾動(dòng)、環(huán)境噪聲和粒子輻射等造成的芯片失效率問題日益嚴(yán)重，給電路可靠性帶來嚴(yán)峻挑戰(zhàn)[1-3]，尤其是因空間高能粒子輻射引發(fā)的軟錯(cuò)誤所帶來的影響最為嚴(yán)重。依據(jù)國(guó)際半導(dǎo)體技術(shù)發(fā)展藍(lán)圖(International Technology Roadmap for Semiconductors,ITRS)對(duì)集成電路的預(yù)測(cè)，電路制造工藝由45 ns縮減至12 ns時(shí)，電路軟錯(cuò)誤率可增加10個(gè)以上數(shù)量級(jí)。因此，在設(shè)計(jì)階段對(duì)電路失效率進(jìn)行有效評(píng)估并采取合理容錯(cuò)與加固設(shè)計(jì)以提高產(chǎn)品可靠性變得刻不容緩[4]。

電路可靠程度可用電路失效率衡量。準(zhǔn)確、高效地評(píng)估電路失效率是指導(dǎo)高效容錯(cuò)設(shè)計(jì)的前提[5]。邏輯電路失效率評(píng)估方法一般可分兩類：基于模擬的方法與基于信號(hào)概率分析的方法。蒙特卡羅(Monte Carlo, MC)方法是典型的基于模擬的方法，其準(zhǔn)確性與模擬次數(shù)密切相關(guān)[6]。由于要模擬多次才能保證準(zhǔn)確性，MC方法往往耗時(shí)較長(zhǎng)。概率轉(zhuǎn)移矩陣(Probability Transition Matrix, PTM)與概率門模型(Probabilistic Gate Models, PGM)方法都可通過準(zhǔn)確分析電路的輸入輸出關(guān)系評(píng)估電路整體失效率。PTM方法通過建立基本門電路的輸入與輸出關(guān)系評(píng)估電路可靠性，是一種能準(zhǔn)確計(jì)算電路整體失效率的概率分析方法，其缺點(diǎn)是算法的空間復(fù)雜度太大[7,8]。PGM方法利用條件概率計(jì)算不同類型扇出重匯聚結(jié)構(gòu)的節(jié)點(diǎn)信號(hào)概率，具有線性的空間復(fù)雜度，但在扇出重匯聚處的指數(shù)級(jí)時(shí)間復(fù)雜度未能得到有效解決。基于PGM的估算方法則假設(shè)所有邏輯門的輸入信號(hào)相互獨(dú)立，通過逐個(gè)門迭代計(jì)算輸出節(jié)點(diǎn)概率，雖然計(jì)算過程簡(jiǎn)單，但因忽視了信號(hào)相關(guān)性影響，僅能得到近似結(jié)果[9-11]。文獻(xiàn)[12]表明三模冗余技術(shù)是目前使用最廣泛的緩解FPGA軟錯(cuò)誤的電路加固技術(shù)，可以有效提高電路可靠性。文獻(xiàn)[13]提出的關(guān)鍵信號(hào)算法(Critical Score Algorithm, CSA)可快速計(jì)算特定輸入下的電路失效率，其復(fù)雜度與電路規(guī)模呈線性關(guān)系，但也因其沒有考慮信號(hào)相關(guān)性而導(dǎo)致準(zhǔn)確性不高。當(dāng)前關(guān)于電路信號(hào)相關(guān)性的研究仍無法做到在保證計(jì)算精度的情況下解決耗時(shí)問題，難以應(yīng)用于超大規(guī)模電路的評(píng)估與計(jì)算。

精準(zhǔn)定位敏感目標(biāo)且針對(duì)性地容錯(cuò)加固能以最小代價(jià)降低電路失效率[14,15]。在容錯(cuò)設(shè)計(jì)中，人們關(guān)注的是那些對(duì)電路輸出端有直接影響的門，即敏感門。敏感門與輸入激勵(lì)向量及電路拓?fù)浣Y(jié)構(gòu)有關(guān)[16]。文獻(xiàn)[17]結(jié)合信號(hào)傳播特點(diǎn)，通過深度優(yōu)先搜索遞歸算法對(duì)敏感單元進(jìn)行標(biāo)識(shí)，但因其重復(fù)計(jì)算扇出節(jié)點(diǎn)而影響了準(zhǔn)確性。文獻(xiàn)[18]考慮了扇出源節(jié)點(diǎn)與敏感門的關(guān)系，并通過從電路原始輸出端向前迭代獲取潛在敏感門集合，再逐一驗(yàn)證集合中的門單元。然而，潛在敏感門集獲取方法是基于關(guān)鍵信號(hào)的，沒有準(zhǔn)確考慮信號(hào)相關(guān)性影響的情況下，潛在敏感門集本身存在誤差。綜上，由于電路規(guī)模增大和信號(hào)相關(guān)性影響，目前的方法很難既準(zhǔn)又快地評(píng)估超大規(guī)模電路失效率[19]；也很難精準(zhǔn)、高效地定位對(duì)電路失效率影響較大的敏感單元。

本文提出一種相關(guān)性分離方法用于準(zhǔn)確、快速地計(jì)算特定向量激勵(lì)下的電路失效率；在此基礎(chǔ)上，利用相關(guān)性分離后的電路模塊和反向搜索算法精準(zhǔn)定位電路敏感單元；再綜合考慮多輸入激勵(lì)的情況，確定最優(yōu)容錯(cuò)目標(biāo)，實(shí)現(xiàn)以低容錯(cuò)成本提高電路可靠性的目的。

本文第2節(jié)詳細(xì)介紹相關(guān)性分離方法(COrrelation SEparation Approach, COSEA)；第3節(jié)提出基于相關(guān)性分離的邏輯電路敏感門定位算法；第4節(jié)對(duì)一系列電路的實(shí)驗(yàn)結(jié)果進(jìn)行分析；最后是結(jié)論。

2 相關(guān)性分離方法

本文提出一種充分考慮信號(hào)相關(guān)性的邏輯電路失效率計(jì)算方法，該方法將電路劃分為多個(gè)獨(dú)立電路結(jié)構(gòu)(Independent Circuit Structure, ICS)，并以這些獨(dú)立電路結(jié)構(gòu)為基本計(jì)算單元，分析它們的出錯(cuò)率及故障在電路中的傳播情況，以此計(jì)算電路失效率。下面介紹此方法的原理與計(jì)算過程。

2.1 ICS分類與計(jì)算

邏輯電路中普遍存在大量扇出重匯聚結(jié)構(gòu)。上游電路的故障信息會(huì)在扇出節(jié)點(diǎn)處沿扇出分支傳播，若扇出支路重匯聚，則匯聚路徑包含相關(guān)的故障信息，導(dǎo)致信號(hào)具有相關(guān)性?？稍谏瘸鲋飞蠘?biāo)記故障來源，根據(jù)分支標(biāo)記溯源故障信息。以扇出節(jié)點(diǎn)為間隔將電路劃分為不同電路模塊。每個(gè)模塊包含多個(gè)輸入節(jié)點(diǎn)和一個(gè)輸出節(jié)點(diǎn)，其中，輸入為電路扇出節(jié)點(diǎn)或原始輸入信號(hào)，輸出為扇出節(jié)點(diǎn)或原始輸出。每個(gè)電路模塊代表的電路結(jié)構(gòu)都不同，模塊失效率相互獨(dú)立，將這些模塊稱為獨(dú)立電路結(jié)構(gòu)。根據(jù)ICS輸出節(jié)點(diǎn)的不同，將其分為兩類：輸出節(jié)點(diǎn)為扇出節(jié)點(diǎn)的ICS稱為扇出相關(guān)電路CFR，其對(duì)應(yīng)的失效率PFR通過扇出源傳播；輸出為非扇出節(jié)點(diǎn)的ICS稱為扇出無關(guān)電路CFI，其失效率PFI表示以該節(jié)點(diǎn)為輸出的ICS失效率。

對(duì)于非扇出節(jié)點(diǎn)j，以該節(jié)點(diǎn)為輸出的ICS類型為CFI，其對(duì)應(yīng)失效率PFI計(jì)算如式(1)所示：

其中，t為其關(guān)鍵信號(hào)個(gè)數(shù)，PFIi為第i個(gè)關(guān)鍵輸入信號(hào)的PFI。

實(shí)際上，CFI可轉(zhuǎn)化為CFR。轉(zhuǎn)化后CFR的失效率PFR等于轉(zhuǎn)化前PFI的失效率，與此同時(shí)，CFI(b)的PFI變?yōu)?，計(jì)算過程如式(2)所示：

式(2)表明，在檢測(cè)到b點(diǎn)為扇出節(jié)點(diǎn)后，以b點(diǎn)為輸出的CFI(b)即轉(zhuǎn)化為CFR(b)。

2.2 節(jié)點(diǎn)信息定義與計(jì)算

電路節(jié)點(diǎn)的出錯(cuò)率受該節(jié)點(diǎn)輸入錐中邏輯門的影響。將電路劃分為不同的CFR和CFI，節(jié)點(diǎn)j的出錯(cuò)率可表示為EPNj= function(CFR1, CFR2, ···,CFRm, CFIj)。其中，m為節(jié)點(diǎn)j的輸入錐中CFR的個(gè)數(shù)，CFIj為以節(jié)點(diǎn)j為輸出的CFI。CFIj對(duì)節(jié)點(diǎn)j的影響是必然的；而對(duì)于CFR，其故障可能被屏蔽，也可能被傳播至目標(biāo)節(jié)點(diǎn)j，對(duì)該節(jié)點(diǎn)的出錯(cuò)率產(chǎn)生影響。因此，節(jié)點(diǎn)j的出錯(cuò)率EPNj可表示為

其中，nc為對(duì)節(jié)點(diǎn)j出錯(cuò)率有影響的CFR的數(shù)目，PFRj為CFRj的失效率，PFIj為CFIj的失效率。

影響目標(biāo)節(jié)點(diǎn)出錯(cuò)率的CFR可能有多個(gè)，用U表示影響該節(jié)點(diǎn)的CFR集合；影響目標(biāo)節(jié)點(diǎn)的CFI只有一個(gè)。通過以下節(jié)點(diǎn)信息可計(jì)算整個(gè)電路失效率：節(jié)點(diǎn)邏輯值LV、節(jié)點(diǎn)PFI、影響節(jié)點(diǎn)出錯(cuò)率的CFR集合U。T表示此3類信息集合，即T={LV, PFI,U}。節(jié)點(diǎn)邏輯值LV由門輸入信號(hào)和門類型決定；PFI可利用CSA方法計(jì)算，隨著目標(biāo)節(jié)點(diǎn)的變化，CFI可轉(zhuǎn)化為CFR。

接下來介紹如何計(jì)算集合U。CFR的故障信息通過其輸出節(jié)點(diǎn)(扇出源)傳播，當(dāng)扇出分支在同一節(jié)點(diǎn)匯聚，由于故障信息已保存，在計(jì)算該節(jié)點(diǎn)出錯(cuò)率時(shí)可充分考慮到CFR間的相關(guān)性。目標(biāo)節(jié)點(diǎn)前驅(qū)邏輯門的輸入信號(hào)中，若多個(gè)輸入信號(hào)中存在相同的CFR，則說明它們?cè)从谕粋€(gè)CFR。

圖1描述了n輸入與門輸出節(jié)點(diǎn)的CFR集合U的計(jì)算過程。設(shè)與門輸入信號(hào)中‘1’的個(gè)數(shù)為n1，‘0’的個(gè)數(shù)為n0，n1+n0= n。輸入為‘1’的信號(hào)記為P1，P2, ···,Pn1，對(duì)應(yīng)節(jié)點(diǎn)信息為{TP1,TP2, ···,TPn1}，其中TPi={LVPi, PFIPi,UPi}；輸入為‘0’的信號(hào)記為Q1, Q2, ···,Qn0，對(duì)應(yīng)節(jié)點(diǎn)信息為{TQ1,TQ2, ···,TQn0}，其中，TQi={LVQi, PFIQi,UQi}。第Pi個(gè)‘1’信號(hào)節(jié)點(diǎn)信息的CFR集合UPi= {CFRPi(1),CFRPi(2), ···, CFRPi(kPi)}，第Qi個(gè)‘0’信號(hào)節(jié)點(diǎn)信息的CFR集合UQi= {CFRQi(1), CFRQi(2), ···, CFRQi(kQi)}，圖1中各信號(hào)線上所列即為輸入信號(hào)所對(duì)應(yīng)的U。輸出端的節(jié)點(diǎn)信息Tout= {LVout, PFIout, Uout}。

圖1 與門輸出節(jié)點(diǎn)的集合U計(jì)算過程

針對(duì)不同輸入，分情況討論輸出節(jié)點(diǎn)的CFR集合U的計(jì)算方法，表1列出了與門輸出節(jié)點(diǎn)信息。同理，或門及非門的輸出節(jié)點(diǎn)信息的計(jì)算方法與門類似，不再贅述。

表1 與門輸出節(jié)點(diǎn)信息

(1) n1= n, n0= 0。如圖1(a)所示，與門的所有輸入都為1，其正常輸出為1。此時(shí)，任意輸入信號(hào)的CFR出錯(cuò)，都將導(dǎo)致與門輸出出錯(cuò)。因此，輸出節(jié)點(diǎn)的U即為輸入節(jié)點(diǎn)的U之并集，即Uout=；

(2) n1= n-1, n0= 1。如圖1(b)所示，與門輸入中存在一個(gè)0信號(hào)，其正常輸出為0。輸入信號(hào)Qi上的CFRQi(kQi)出錯(cuò)，將導(dǎo)致與門輸出出錯(cuò)；但若CFRQi(kQi)也存在于其他輸入1信號(hào)中，則CFRQi(kQi)出錯(cuò)將使輸入1信號(hào)變?yōu)?，導(dǎo)致與門輸出仍為0。因此，只有存在于輸入0且不存在于任意輸入1上的CFR出錯(cuò)，才會(huì)導(dǎo)致與門輸出出錯(cuò)。此時(shí)，輸出節(jié)點(diǎn)的U為輸入0信號(hào)的U減去所有輸入1信號(hào)的U之并集，即

(3) 1＜n0＜n, n1=n-n0。如圖1(c)所示，與門輸入中存在多個(gè)0 信號(hào)，其正常輸出為0。與圖1(b)情形類似，只有存在于所有輸入0信號(hào)且不存在于任意輸入1信號(hào)上的CFR出錯(cuò)，才能導(dǎo)致門輸出出錯(cuò)。所以輸出節(jié)點(diǎn)的U為所有輸入0信號(hào)的U 之交集減去所有輸入1 信號(hào)的U 之并集，即

3 敏感門定位算法

敏感門(Critical Gates, CG)指那些若發(fā)生故障便將直接導(dǎo)致電路失效的邏輯門。CG的故障不會(huì)被下游電路邏輯屏蔽，而是被傳至電路原始輸出端，或被下游存儲(chǔ)單元捕獲，從而導(dǎo)致電路失效。本節(jié)提出基于COSEA的敏感門定位算法，包括單個(gè)輸入向量激勵(lì)下電路的敏感門定位方法和多輸入向量激勵(lì)的敏感門定位方法(Vector Critical Gate Location Algorithm, VCGLA)。

3.1 向量敏感門定位算法

在單個(gè)特定向量激勵(lì)下，若邏輯門故障導(dǎo)致電路失效，則稱此邏輯門為向量敏感門(Vector Critical Gate, VCG)。對(duì)特定電路而言，不同輸入向量對(duì)應(yīng)不同的VCG集合。本節(jié)介紹如何計(jì)算電路的VCG集合。

類似地，將那些若發(fā)生故障便會(huì)導(dǎo)致電路失效的ICS稱為敏感ICS，否則為非敏感ICS。顯然，所有以電路原始輸出節(jié)點(diǎn)為輸出的CFI都是敏感ICS。電路中的CFR是否為敏感ICS則取決于電路的拓?fù)浣Y(jié)構(gòu)和當(dāng)前輸入向量。由于非敏感ICS的故障不會(huì)導(dǎo)致電路失效，所以該結(jié)構(gòu)內(nèi)部的邏輯門都不是向量敏感門；而敏感ICS結(jié)構(gòu)內(nèi)部的邏輯門也并非都是向量敏感門，可使用關(guān)鍵信號(hào)定位敏感ICS內(nèi)部的向量敏感門。

VCGLA首先對(duì)輸入的電路網(wǎng)表進(jìn)行解析，針對(duì)每個(gè)單獨(dú)的輸入向量調(diào)用COSEA計(jì)算電路所有原始輸出的節(jié)點(diǎn)信息T；其次，對(duì)所有輸出節(jié)點(diǎn)的集合U進(jìn)行分類，得到對(duì)電路輸出有影響的敏感ICS集合；最后，對(duì)得到的ICS進(jìn)行敏感門定位，使用反向搜索算法從ICS的輸出向上游迭代，通過關(guān)鍵信號(hào)定位每個(gè)能影響到此ICS輸出的邏輯門，將它們加入至敏感門集合。具體過程如算法1所示。

3.2 示例說明

本文以圖2電路為例說明VCGLA具體計(jì)算過程。

圖2 示例電路

步驟1 根據(jù)COSEA方法計(jì)算示例電路原始輸出Out1和Out2的節(jié)點(diǎn)信息分別為Tout1={1, FPG,{CFR(S1), CFR(S4)}}和Tout2={1, 4FPG, {CFR(S1),CFR(S4), CFR(S5)}}，則輸出節(jié)點(diǎn)的UCFR= Uout1∪Uout2= {CFR(S1), CFR(S4), CFR(S5)}, UCFI= {CFI(out1),CFI(out2)}。電路節(jié)點(diǎn)信息的具體計(jì)算過程如表2所示，其中No表示該節(jié)點(diǎn)處不需要進(jìn)行CFI和CFR之間的轉(zhuǎn)化。

算法1 VCGLA算法

表2 示例電路節(jié)點(diǎn)信息計(jì)算過程

步驟2：定位每個(gè)敏感ICS內(nèi)的向量敏感門，在此以CFR(S4)為例。CFR(S4)為UCFR中的敏感ICS，首先找到輸出節(jié)點(diǎn)G6，將G6加入向量敏感門集合；然后，向前追溯G6的輸入信號(hào)“10”，由于G6是或門，所以輸入‘1’為G6的關(guān)鍵信號(hào)，該信號(hào)的前驅(qū)邏輯門為G4，故將G4添加至向量敏感門集合；最后，G4的前驅(qū)為扇出節(jié)點(diǎn)S2，停止此次迭代。因此，CFR(S4)的向量敏感門為G4和G6。分析所有敏感ICS可知，在輸入向量為“1 110”時(shí)，電路的向量敏感門集合為{G1, G4, G6, G7, G8, G9}。

3.3 電路敏感門定位算法

電路中被多數(shù)向量甚至所有向量都定位為向量敏感門的邏輯門，被稱為電路敏感門(Circuit Critical Gate, CCG)，它們是容錯(cuò)設(shè)計(jì)的重點(diǎn)，對(duì)該部分邏輯門進(jìn)行容錯(cuò)，能夠大幅度提高電路可靠性。本節(jié)我們提出一種電路敏感門定位算法(Circuit Critical Gate Location Algorithm, CCGLA)，如算法2所示。

若邏輯門G為輸入向量V的向量敏感門，則向量V為邏輯門G的敏感向量。定義邏輯門的敏感向量數(shù)占總輸入向量空間的比值為該邏輯門的敏感度GS。設(shè)定敏感度閾值Th，認(rèn)為電路敏感門即電路中敏感度超過閾值Th的邏輯門。例如，某電路的原始輸入數(shù)為w，其輸入向量空間大小為2w。計(jì)算所有輸入向量空間的敏感門集合分別為VCG1,VCG2, ···, VCG2w，若邏輯門Gi出現(xiàn)在其中ki個(gè)向量敏感門集合中，則Gi的敏感度為ki/2w。隨著輸入數(shù)和電路規(guī)模的增大，計(jì)算所有輸入向量的敏感門集合變得非常困難，因此，通常只選取部分向量計(jì)算對(duì)應(yīng)敏感門。設(shè)N為選取的向量個(gè)數(shù)，ki為第i個(gè)邏輯門Gi的敏感向量數(shù)，則Gi的敏感度為

算法2為CCGLA算法總體框架，包含3步：(1)選取N個(gè)向量，計(jì)算這些向量對(duì)應(yīng)的向量敏感門集合：VCG1, VCG2, ···, VCGN；(2)計(jì)算電路中每一個(gè)邏輯門的敏感度；(3)設(shè)定閾值參數(shù)Th，比較邏輯門的敏感度與閾值Th的大小，超過閾值的門添加至電路敏感門集合。

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

4.1 VCGLA效果驗(yàn)證

模擬實(shí)驗(yàn)在配備3.0 GHz微處理器和8 GB內(nèi)存的計(jì)算機(jī)上進(jìn)行。VCGLA, CCGLA和CGC方法都是基于MATLAB 2014a平臺(tái)。ISCAS-85,89系列電路應(yīng)用于文獻(xiàn)[16-18,20]進(jìn)一步驗(yàn)證提出的方法的準(zhǔn)確性，其中文獻(xiàn)[17,18]提出的CGC方法被廣泛應(yīng)用于電路敏感門定位，通過與其對(duì)比驗(yàn)證VCGLA的準(zhǔn)確性與高效性。其中，CGC的變體方法共有6種，選取實(shí)驗(yàn)條件相似(單線程)的CGC-V1, V3,V4和V6方法進(jìn)行對(duì)比。V1方法通過逐個(gè)檢測(cè)電路每個(gè)單元的敏感性獲取向量敏感門，準(zhǔn)確率為100%，但因?yàn)閷?duì)每個(gè)邏輯門進(jìn)行檢測(cè)耗時(shí)太高，無法用于大規(guī)模和超大規(guī)模電路的敏感門定位；相比之下，V3方法是一種快速的VCG定位方法，但準(zhǔn)確性不高。V4和V6方法的準(zhǔn)確性與定位速度介于以上兩種方法之間。

算法2 CCGLA算法

考慮到CGC-V1, V4和V6方法所需時(shí)間較長(zhǎng)，針對(duì)實(shí)驗(yàn)電路的每種方法各選擇100個(gè)向量，用于定位電路的VCG集合。本實(shí)驗(yàn)中，由于CGC-V1方法能精準(zhǔn)定位VCG集合，故以其為標(biāo)準(zhǔn)驗(yàn)證其他方法的準(zhǔn)確性。針對(duì)ISCAS’85系列4個(gè)規(guī)模較小的電路，表3列舉了VCGLA與CGC-V1, V3, V4和V6方法的比較結(jié)果。其中，avg.CG為100個(gè)相同隨機(jī)向量激勵(lì)下對(duì)應(yīng)的敏感門數(shù)目的平均值，avg.err是它們與CGC-V1方法相比的誤差平均值(即每個(gè)向量對(duì)應(yīng)VCG誤差的平均值)，如式(5)所示，max.err表示單個(gè)隨機(jī)向量激勵(lì)下敏感門集合誤差的最大值，如式(6)所示，表3還列出了單個(gè)向量激勵(lì)下定位對(duì)應(yīng)VCG的平均計(jì)算時(shí)間。

表3 VCGLA與CGC-V1, V3, V4和V6方法的比較

其中，m1是是激勵(lì)向量數(shù)，VCGCGC-V1(i)是由CGC-V1方法定位出的第i個(gè)輸入向量的VCG,VCGOther(i)表示其他幾類方法計(jì)算出的第i個(gè)輸入向量的VCG，在此統(tǒng)一表示。公式中的VCG差值實(shí)際是兩個(gè)集合中不同的敏感門總數(shù)：相比CGCV1方法定位的VCG集合，用其他方法定位的VCG集合中漏檢與誤檢的敏感門。

表3中VCGLA的max.err列都為0表明VCGLA與CGC-V1方法找到的所有敏感門集合完全相同，表明本方法在定位向量敏感門時(shí)具有100%的準(zhǔn)確性；而在定位速度上，VCGLA平均耗時(shí)0.2 s，相比CGC-V1的537.3 s快了3個(gè)數(shù)量級(jí)以上。CGCV3是唯一一個(gè)在定位速度上稍快于VCGLA的方法，但由它定位的敏感門集合的最大誤差平均值為69.5，且平均誤差為22.8，是所列方法中準(zhǔn)確性最低的。CGC-V4和V6的速度和準(zhǔn)確性介于CGCV1和V3之間，但都不及VCGLA。相關(guān)性分離方法通過將電路劃分為多個(gè)ICS，再以ICS為基本單元分析故障傳播及信號(hào)相關(guān)性影響，在保證準(zhǔn)確性的前提下，大大簡(jiǎn)化了敏感門定位算法的迭代過程。

接下來使用VCGLA計(jì)算更大規(guī)模電路，衡量其計(jì)算大規(guī)模和超大規(guī)模電路時(shí)的有效性，結(jié)果如表4所示?？紤]到CGC-V1, V4和V6方法的計(jì)算時(shí)間太長(zhǎng)，已很難在合適的時(shí)間內(nèi)定位這些大規(guī)模電路的敏感門，后續(xù)實(shí)驗(yàn)中我們僅使用VCGLA與CGC-V3方法定位敏感門。在表3和表4中，avg.err和max.err的含義相同，都是以CGC-V1方法結(jié)果為參考。只是表4中計(jì)算avg.err和max.err時(shí)，使用VCGLA方法的計(jì)算結(jié)果代替了CGC-V1方法結(jié)果，因?yàn)橹耙炎C明，VCGLA方法與CGC-V1方法結(jié)果一致，且速度遠(yuǎn)快于后者。所選實(shí)驗(yàn)電路包括ISCAS’85, 89系列和ITC’99的10個(gè)電路。對(duì)于其中規(guī)模相對(duì)較小的電路，各選取10 000個(gè)測(cè)試向量，隨著電路規(guī)模的不斷增大，考慮到定位時(shí)間的快速增長(zhǎng)，所選取向量的數(shù)目逐漸減小。

表4 VCGLA與CGC-V3方法定位大規(guī)模電路的敏感門

從表4可知，電路規(guī)模達(dá)到萬門以上，VCGLA的計(jì)算耗時(shí)仍與CGC-V3方法相差不大，二者計(jì)算超大規(guī)模電路的向量敏感門速度都比較快。在實(shí)驗(yàn)中，隨著電路規(guī)模的增長(zhǎng)，VCGLA方法的計(jì)算耗時(shí)基本隨邏輯門的數(shù)量呈線性增長(zhǎng)，充分證明所提算法的可拓展性。因此，VCGLA可應(yīng)用于更大規(guī)模電路的敏感門精準(zhǔn)定位。

4.2 CCGLA效果驗(yàn)證

影響電路敏感門(CCG)定位性能的參數(shù)包括選取的向量數(shù)N和敏感度閾值Th。先考慮N的變化對(duì)CCGLA的影響。實(shí)驗(yàn)電路選取C7552的一個(gè)單輸出子電路，輸出節(jié)點(diǎn)編號(hào)為65。實(shí)驗(yàn)使用CCGLA計(jì)算當(dāng)N為不同值時(shí)該子電路的敏感門集合，且對(duì)設(shè)定的每個(gè)N值，取Th的范圍為0～1，步長(zhǎng)為0.05。以N=50 000時(shí)的計(jì)算結(jié)果為參考標(biāo)準(zhǔn)，比較N取其它值時(shí)對(duì)應(yīng)21個(gè)不同Th的電路敏感門集合，并將此21組差值求和表示為該N值與最大N值(N=50 000)的敏感門集合差，實(shí)驗(yàn)結(jié)果如圖3所示。由圖可知，當(dāng)N＜5 000時(shí)，對(duì)應(yīng)電路敏感門集合與參考標(biāo)準(zhǔn)差別逐漸減??；當(dāng)N＞5 000時(shí)，隨著N繼續(xù)增大，敏感門集合差異已可忽略。實(shí)驗(yàn)說明，當(dāng)N增大到一定程度即可用于準(zhǔn)確定位CCG集合，無需遍歷所有輸入激勵(lì)。實(shí)際上，對(duì)多數(shù)電路都有此結(jié)論。

圖3 N的變化對(duì)敏感門差異的影響

Th是電路敏感度閾值，其值可影響CCG集的大小和質(zhì)量：Th值若增大，則CCG集合中的元素減少，但CCG的敏感度更高；反之，則CCG數(shù)增加，但門的敏感度降低。定位CCG的目的是更高效地對(duì)電路進(jìn)行容錯(cuò)加固。在此，假設(shè)改進(jìn)后的CCG無錯(cuò)，對(duì)比容錯(cuò)前后的電路失效率，即可得到對(duì)該CCG集合容錯(cuò)后電路失效率的改善情況，以此評(píng)估Th對(duì)CCG定位及容錯(cuò)效果的影響。為保證失效率計(jì)算結(jié)果的準(zhǔn)確性，使用MC模擬方法計(jì)算容錯(cuò)前后電路的失效率，模擬次數(shù)為5×106。實(shí)驗(yàn)電路為ISCAS’89系列電路。

本實(shí)驗(yàn)分5步：(1)選定實(shí)驗(yàn)電路，使用MC方法計(jì)算實(shí)驗(yàn)電路失效率，將邏輯門的出錯(cuò)概率設(shè)為10-4[15,20]；(2)設(shè)N=10 000，針對(duì)Th值定位CCG集合；(3)計(jì)算容錯(cuò)后電路失效率，并對(duì)比容錯(cuò)前電路失效率；(4)改變Th大小，其范圍為0～1，間隔步長(zhǎng)為0.05；(5)重復(fù)步驟(3)和步驟(4)，分析Th對(duì)容錯(cuò)效果的影響。

實(shí)驗(yàn)結(jié)果如圖4所示，圖4(a)-4(f)分別描述不同電路下Th變化對(duì)電路失效率的影響。藍(lán)色折線為針對(duì)不同Th值定位CCG集合并容錯(cuò)后得到的電路失效率；綠色直線為不進(jìn)行容錯(cuò)的電路失效率。在圖中，當(dāng)Th為0時(shí)，所有輸入激勵(lì)對(duì)應(yīng)的CCG都是容錯(cuò)對(duì)象，容錯(cuò)后電路失效率最低(可認(rèn)為是0)；隨著Th增大，容錯(cuò)對(duì)象減少，容錯(cuò)后電路失效率也逐漸增大；當(dāng)Th為1時(shí)，只有極少數(shù)CCG為容錯(cuò)對(duì)象，容錯(cuò)后電路失效率最高。

圖4 敏感門容錯(cuò)前后電路失效率對(duì)比

容錯(cuò)效果與容錯(cuò)代價(jià)是需綜合考慮的兩個(gè)重要指標(biāo)。設(shè)FPCa和FPCb分別為容錯(cuò)后和容錯(cuò)前電路失效率，兩者之間的改善比率定義為電路失效率改善率(Improvement Rate of Failure, IRF)，如式(7)所示；NCCG為CCG集合的元素個(gè)數(shù)，NCCG與電路總門數(shù)Num的比值稱為電路敏感度比值(Circuit Critical Gate Rate, CCGR)，如式(8)所示。容錯(cuò)效果可用IRF衡量，IRF越大，說明容錯(cuò)效果越好；容錯(cuò)代價(jià)則用CCGR衡量，CCGR越小，則表明容錯(cuò)代價(jià)越小。定義容錯(cuò)效率(Fault Tolerance Efficiency, FTE)為IRF和CCGR的比值，如式(9)所示。FTE越大，表示對(duì)CCG集合容錯(cuò)的效率越高。

圖5中兩條曲線分別描述了所選擇的6個(gè)實(shí)驗(yàn)電路的IRF和CCGR隨Th的變化情況，其中藍(lán)色折線代表IRF，綠色折線代表CCGR。由圖可知，IRF與CCGR都隨Th的增大而減小。當(dāng)電路設(shè)計(jì)人員以特定的IRF為電路設(shè)計(jì)目標(biāo)時(shí)，可根據(jù)IRF選擇Th值，從而得到對(duì)應(yīng)的CCG集合，再對(duì)集合中的邏輯門進(jìn)行容錯(cuò)；當(dāng)以特定的CCGR為電路容錯(cuò)限制條件時(shí)，同樣可選擇對(duì)應(yīng)Th值以得到CCG集合，再進(jìn)行容錯(cuò)處理。

圖6為實(shí)驗(yàn)電路的FTE隨Th的變化情況。當(dāng)Th為0時(shí)，F(xiàn)TE最小，隨著Th增大，F(xiàn)TE也逐漸增大；當(dāng)Th增大到一定程度時(shí)，F(xiàn)TE的增大開始變緩，甚至有減小趨勢(shì)。從本文實(shí)驗(yàn)電路的結(jié)果可知：當(dāng)Th為0.6～1的范圍時(shí)，電路容錯(cuò)效率較高，但不同電路最佳容錯(cuò)點(diǎn)對(duì)應(yīng)的Th會(huì)有差別。

圖6 FTE隨Th的變化

5 結(jié)論

本文提出了一種基于相關(guān)性分離的邏輯電路敏感門定位算法。首先將整個(gè)電路分離成多個(gè)獨(dú)立電路結(jié)構(gòu)；再針對(duì)獨(dú)立電路結(jié)構(gòu)反向搜索定位特定輸入向量的向量敏感門；最后進(jìn)一步定位面向向量空間的電路敏感門。使用本文提出的敏感門定位算法，能精準(zhǔn)定位對(duì)多數(shù)輸入激勵(lì)都敏感的邏輯門集合；而針對(duì)這些敏感門進(jìn)行容錯(cuò)加固將有助于提升整個(gè)電路可靠性，同時(shí)能保證較低的容錯(cuò)開銷。相比于其他敏感門定位算法，本文提出的算法既準(zhǔn)確又高效，適用于定位大規(guī)模及超大規(guī)模電路的敏感門單元，以輔助高效容錯(cuò)設(shè)計(jì)。