一種引導(dǎo)測試向量自動生成廣義折疊集的方法

詹文法　程一飛　吳海峰　江健生

(安慶師范大學(xué)計算機與信息學(xué)院, 安慶 246133)

隨著集成電路技術(shù)的發(fā)展,測試成本已成為影響集成電路成本的主要問題之一,最有效的解決方法是通過壓縮測試數(shù)據(jù)量達到減少測試成本的目的．按是否同時壓縮原始測試數(shù)據(jù)的長度或?qū)挾?可以將測試數(shù)據(jù)壓縮方法分為一維壓縮和二維壓縮．一維壓縮僅單一壓縮測試數(shù)據(jù)的長度或?qū)挾龋畨嚎s測試數(shù)據(jù)長度的代表性方法包括基于LFSR的壓縮技術(shù)[1-2]和基于編碼的壓縮技術(shù)[4-11]等．基于LFSR的壓縮技術(shù)優(yōu)點是可以采用種子編碼整個測試向量,但LFSR種子長度與單個測試向量中最多確定位有關(guān),即受最壞環(huán)境影響;基于編碼的壓縮技術(shù)優(yōu)點是不需要提供被測電路的內(nèi)部結(jié)構(gòu),能夠保護知識產(chǎn)權(quán),缺點是無法解決測試數(shù)據(jù)與自動測試設(shè)備之間的同步問題．壓縮測試集寬度的代表性方法有測試緊縮技術(shù)[12],該技術(shù)的優(yōu)點是不增加任何硬件成本,缺點是難以覆蓋被測電路中的非固定性故障．二維壓縮同時壓縮測試集的長度和寬度,代表性的有基于折疊集和廣義折疊集的測試數(shù)據(jù)壓縮技術(shù)[13-14]．

從壓縮效果上看,二維測試壓縮能有效地組合折疊計數(shù)器、扭環(huán)計數(shù)器以及LFSR編碼技術(shù),其壓縮效果為所有同類技術(shù)中最優(yōu)．然而,傳統(tǒng)的二維壓縮技術(shù)未探討測試集內(nèi)部測試向量之間的相關(guān)性,其壓縮效果不好．本文提出了一種引導(dǎo)自動測試向量生成的廣義折疊技術(shù),即根據(jù)信號線的確定值計算對應(yīng)的原始輸入,在測試生成時嵌入廣義折疊技術(shù),以確保按照廣義折疊規(guī)律生成廣義折疊集．

1　廣義折疊技術(shù)

廣義折疊集的基本思想是將整個測試集的直接存儲轉(zhuǎn)換成廣義折疊種子和對應(yīng)折疊距離的間接存儲．不失一般性,設(shè)由t個不同向量組成原始測試數(shù)據(jù),將這t個向量嵌入到n個廣義折疊集中,這樣對原始測試集的存儲就轉(zhuǎn)換成對n個廣義折疊集的存儲．進一步可將整個原始測試集的存儲轉(zhuǎn)換成對n個廣義折疊種子和對應(yīng)折疊距離的存儲,其中t?n[15]．

構(gòu)成廣義折疊集的向量之間無相關(guān)性,限制了廣義折疊集的壓縮效果,中間產(chǎn)生了很多對測試覆蓋率無關(guān)的測試向量,增加了測試時間和測試功耗．

2　測試向量生成策略

2.1　準(zhǔn)確影響范圍技術(shù)

傳統(tǒng)的自動測試向量生成工具是基于故障點產(chǎn)生測試向量的,測試向量之間無相關(guān)性,難以將其嵌入到折疊集等固定翻轉(zhuǎn)規(guī)律的單一序列中,因而很難達到最優(yōu)壓縮效果．傳統(tǒng)算法中通過輸入核來判斷一個信號線的影響區(qū)域,無法準(zhǔn)確識別一個有確定值的信號線影響的輸入范圍．一個觸發(fā)器的輸入核可能有很多輸入,在測試向量的產(chǎn)生過程中,只有一部分會被置為確定值．因此,準(zhǔn)確識別能夠被該觸發(fā)器影響的輸入對后面的壓縮工作具有很大的指導(dǎo)意義．

SCOAP是ATPG過程中廣泛應(yīng)用的一種可測性度量方法．但是它只單獨分析各個門電路,不能在全局上進行測量．本文提出了一種新的測度,將每一個信號線取確定值可能影響的基本輸入(PI)或偽基本輸入(PPI)的集合記錄下來,在回溯的過程中進行選擇．

信號線l的可控性Ti(l)是使l賦值為i(i∈{0,1})時從l到PPI所有門電路的可控性之和,如果存在多條通路,則取最小值．令Ci(l)表示使l賦值為i時從l到PPI最小通路的距離,記為Ci(l)=|Ti(l)|．

如果l的輸入為PI或者PPI,用l(0)和l(1)分別代表信號線l被賦值為0和1,則

T1(l)={l(1)},T0(l)={l(0)}

(1)

C1(l)=C0(l)=1

(2)

對于一個與門來說,假設(shè)其輸入值為A和B,則

T1(l)=T1(A)∪T1(B)

(3)

C1(l)=C1(A)+C1B+ΔC

(4)

式中,ΔC為門的級數(shù),默認值為1．

區(qū)分PI和PPI是為了向盡量少的PPI方向回溯．如果對于輸入端都是PI的情況,C取值為10,作為一個懲罰值．

類似地，與門之間存在如下關(guān)系：

(5)

(6)

使一個與門的輸出值為0,只需要任一個輸入值為0．如果存在多種選擇,則優(yōu)先選擇最小代價進行回溯．

對于一個輸入值為A或B的或門,有

T0(l)=T0(A)∪T0(B)

(7)

C0(l)=C0(A)+C0(B)+ΔC

(8)

(9)

(10)

對于一個輸入值為A的非門,有

T1(B)=T0(A),C1(B)=|T(B)|

(11)

T0(B)=T1(A),C0(B)=|T0(B)|

(12)

對于一個多扇出信號線s,其扇出端值分別為B1,B2,…,Bk,則

Ci(Bj)=Ci(s)

(13)

與非門和或非門的計算情況與上面類似,可以按照與門、非門和或門直接復(fù)合．

對于一個確定的故障,檢測時不僅需要將其激活,還需要把故障效應(yīng)傳遞到原始輸出．因此,需要定義每個信號線的可觀測性．

與可控制性類似,可觀測性Qi(l)定義為使l賦值為i(i∈{0,1})時從PPO到l所有門電路的可控制性之和,如果存在多條通路,則取最小值．令Oi(l) 表示使l賦值為i時從PPO到l最小通路的距離,記為Oi(l)=|Qi(l)|．

對于電路的原始輸入端M,有

Q(M)=?,O(M)=0

(14)

對于非門,令輸入值為A,輸出值為B,則

Q(A)=Q(B)

(15)

O(A)=|Q(A)|

(16)

對于二輸入與門,輸入值為A和B,輸出值為p,則

Q(A)=Q(p)∪T1(B)

(17)

O(A)=|Q(A)|

(18)

對于二輸入或門,輸入值為A和B,輸出值為p,則

Q(A)=Q(p)∪T0(B)

(19)

O(A)=|Q(A)|

(20)

對于扇出s,設(shè)B1,B2,…,Bk為多扇出分支值,則

O(s)=min(O(B1),O(B2),…,O(Bk))

(21)

由此可得一個故障的原始輸入．在ATPG產(chǎn)生測試向量的過程中,選擇性地調(diào)整確定位位置,使產(chǎn)生的測試向量符合廣義折疊規(guī)律．

2.2　故障合并策略

在2個故障生成測試向量過程中,可以按照如下3個原則來執(zhí)行:

① 如果2個故障沒有相同的結(jié)構(gòu)輸入核,那么它們肯定是可以合并的,基于這2個故障產(chǎn)生一個測試向量;

② 如果2個故障的結(jié)構(gòu)輸入核有交叉,其影響范圍沒有交叉,可以基于這2個向量產(chǎn)生一個測試向量;

③ 在其他情況下,理論上不能判斷這2個故障是否可以直接合并成一個測試向量,需要通過量化影響范圍指標(biāo)來判斷其交叉程度,優(yōu)先選取影響范圍交叉程度小的故障進行測試．

2.3　向量生成順序

首先按照測試向量的合并策略,將基于同一個測試向量測試的難測故障個數(shù)分組,選擇可以合并的難測故障數(shù)最多的2組故障,產(chǎn)生2個測試向量.與折疊集類似,由這2個測試向量計算對應(yīng)的廣義折疊集,根據(jù)得到的廣義折疊集中的測試向量進行故障模擬,檢查該廣義折疊集所能測試的所有故障．對剩下的難測故障再次分組,得到另一完整廣義折疊集．以此類推,直到故障覆蓋率達到100%,最終得到若干個確定的廣義折疊集．

3　綜合過程

通過隨機測試將故障分成易測故障和難測故障．難測故障采用2.2節(jié)的故障合并策略,按照同一個測試向量測試的難測故障個數(shù)分組,選擇可以合并故障數(shù)最多的2組故障,采用較為準(zhǔn)確的影響范圍技術(shù)來判斷每個信號線在回退過程中產(chǎn)生影響的原始輸入,指導(dǎo)測試向量的生成過程,產(chǎn)生對應(yīng)的2個測試向量．與折疊集類似,由這2個測試向量來計算廣義折疊集,根據(jù)得到的廣義折疊集中的測試向量進行故障模擬,檢查該廣義折疊集所能測試的所有故障．對剩下的故障再次分組,得到另一完整廣義折疊集．以此類推,直到故障覆蓋率達到100%,最終得到若干個確定的廣義折疊集．總體過程見圖1．

圖1　按照廣義折疊規(guī)律生成的自動測試向量生成算法 　 　 技術(shù)路線

廣義折疊集不同的翻轉(zhuǎn)規(guī)律需要配置不同的解壓電路,即翻轉(zhuǎn)規(guī)律的個數(shù)直接決定著硬件的開銷．因此,在實際應(yīng)用時,需要在硬件開銷和壓縮效果之間權(quán)衡,而不僅僅只考慮壓縮效果．

4　實驗結(jié)果

下面通過實驗結(jié)果來驗證ATPG引導(dǎo)后廣義折疊技術(shù)的壓縮效果．選用ISCAS 89標(biāo)準(zhǔn)電路中規(guī)模較大的6個時序電路,在隨機模式下運行1×104個時鐘周期以剔除易測故障．對于剩下的難測故障,運用atalanta等ATPG工具生成確定位最少的硬故障測試集． 在同等情況下,對比本文方法與傳統(tǒng)廣義折疊技術(shù)的壓縮效果,結(jié)果見表1．

表1　采用ISCAS 89標(biāo)準(zhǔn)電路和硬故障測試集時2種方法的壓縮效果比較

由表1可知,對每個標(biāo)準(zhǔn)電路,本文方法的壓縮效果明顯優(yōu)于傳統(tǒng)廣義折疊技術(shù)．針對6個標(biāo)準(zhǔn)電路,本文方法的壓縮率較傳統(tǒng)廣義折疊技術(shù)平均提高1.17%．這一結(jié)果是在未增加硬件開銷的情況下得到的,如果增加硬件開銷,壓縮率提高值還可以進一步增大．隨著電路規(guī)模的增加,本文方法的壓縮率逐漸增大．究其原因在于,電路規(guī)模越大,測試向量數(shù)越多,嵌入到廣義折疊集的概率越大,因而壓縮效果也越好．當(dāng)前實際中的集成電路規(guī)模遠遠高于ISCAS89標(biāo)準(zhǔn)電路,因此,本文方法的優(yōu)勢更為明顯．

為了進一步驗證本文方法的效果,將其與國內(nèi)外其他成熟方案在同等實驗環(huán)境下進行比較．實驗中采用ISCAS 89標(biāo)準(zhǔn)電路和Mintest測試集．采用本文方法時,選用難測故障數(shù)最多的2個測試向量,使用準(zhǔn)確影響范圍技術(shù)調(diào)整測試向量的無關(guān)位,并構(gòu)建ATPG引導(dǎo)的廣義折疊集,分析其所測故障數(shù)．對剩下的難測故障循環(huán)使用該方法,直到故障覆蓋率達到100%,從而得到若干個廣義折疊集的存儲位數(shù)．

表2給出了9種方法的壓縮率.由圖可知本文方法的壓縮效果最優(yōu)．對于ISCAS 89標(biāo)準(zhǔn)電路的6個時序電路,本文方法的壓縮率較Golomb碼、FDR碼、VIHC碼、交替連續(xù)碼、EFDR碼、IRIN碼、LODP碼分別提高22.45%,17.01%,14.40%, 13.92%,11.91%,8.73%,11.33%．6個時序電路中,4個電路采用本文方法時壓縮效果最好,壓縮率為61%～77%,從而證明了本文方法的穩(wěn)定性．

表2　采用ISCAS 89標(biāo)準(zhǔn)電路和Mintest測試集時9種方法的壓縮率結(jié)果比較 　%

5　結(jié)論

1) 提出了一種引導(dǎo)自動測試向量生成的廣義折疊技術(shù)．該技術(shù)根據(jù)信號線的確定值計算對應(yīng)的原始輸入,在測試生成時嵌入廣義折疊技術(shù),確保按廣義折疊規(guī)律生成廣義折疊集．將原始測試數(shù)據(jù)的直接存儲轉(zhuǎn)換成對廣義折疊集的種子和折疊距離的間接存儲．

2) 相對于傳統(tǒng)的二維壓縮方法,本文方法可以嵌入更多的測試向量,減少了無用測試向量的產(chǎn)生．實驗結(jié)果顯示,本文方法具有較少的存儲位數(shù),被測電路規(guī)模越大,優(yōu)勢越明顯．

3) 將本文方法與LFSR編碼、輸入精減、掃描鏈重排序技術(shù)結(jié)合使用可進一步提高壓縮效果．

參考文獻(References)

[1] 梁華國, 劉軍, 蔣翠云, 等. 約束輸入精簡的多掃描鏈BIST方案[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2007, 19(3): 371-375 DOI:10.3321/j.issn:1003-9775.2007.03.018.

Liang Huaguo, Liu Jun, Jiang Cuiyun, et al. Constraint input reduction BIST scheme for multiple scan chains[J].JournalofComputerAidedDesign&ComputerGraphics, 2007,19(3): 371-375. DOI:10.3321/j.issn:1003-9775.2007.03.018.(in Chinese)

[2] Xiang D, Chen M J, Fujiwara H. Using weighted scan enable signals to improve test effectiveness of scan-based BIST[J].IEEETransactionsonComputers, 2007,56(12): 1619-1628.

[3] Chandra A, Chakrabarty K. System-on-a-chip test-data compression and decompression architectures based on Golomb codes[J].IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems, 2001,20(3): 355-368.

[4] Chandra A, Chakrabarty K. Test data compression and test resource partitioning for system-on-a-chip using frequency-directed run-length (FDR) codes[J].IEEETransactionsonComputers, 2003,52(8): 1076-1088. DOI:10.1109/tc.2003.1223641.

[5] Gonciari P T, Al-Hashimi B M, Nicolici N. Variable-length input huffman coding for system-on-a-chip test[J].IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems, 2003,22(6): 783-796. DOI:10.1109/tcad.2003.811451.

[6] 梁華國, 蔣翠云. 基于交替與連續(xù)長度碼的有效測試數(shù)據(jù)壓縮和解壓[J]. 計算機學(xué)報, 2004, 27(4): 548-554. DOI:10.3321/j.issn:0254-4164.2004.04.015.

Liang Huaguo, Jiang Cuiyun. Efficient test data compression and decompression based on alternation and run length codes[J].ChineseJournalofComputers, 2004,27(4): 548-554. DOI:10.3321/j.issn:0254-4164.2004.04.015.(in Chinese)

[7] El-Maleh A H. Test data compression for system-on-a-chip using extended frequency-directed run-length code[J].IETComputers&DigitalTechniques, 2008,2(3): 155-163. DOI:10.1049/iet-cdt:20070028.

[8] 詹文法, 梁華國, 時峰, 等.混合定變長碼的測試數(shù)據(jù)壓縮方案[J]. 計算機學(xué)報, 2008, 31(10): 1826-1834. DOI:10.3321/j.issn:0254-4164.2008.10.017.

Zhan Wenfa, Liang Huaguo, Shi Feng, et al. A test data compression scheme based on mixed fixed and variable length coding[J].ChineseJournalofComputers, 2008,31(10): 1826-1834. DOI:10.3321/j.issn:0254-4164.2008.10.017.(in Chinese)

[9] 鄺繼順, 周穎波, 蔡爍. 一種用于測試數(shù)據(jù)壓縮的自適應(yīng)EFDR編碼方法[J]. 電子與信息學(xué)報, 2015, 37(10): 2529-2535. DOI:10.11999/JEIT150177.

Kuang Jishun, Zhou Yingbo, Cai Shuo. Adaptive EFDR coding method for test data compression[J].JournalofElectronics&InformationTechnology, 2015,37(10): 2529-2535. DOI:10.11999/JEIT150177.(in Chinese)

[10] 詹文法, 梁華國, 程一飛, 等. 利用整數(shù)存儲無理數(shù)的測試數(shù)據(jù)編碼壓縮方法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2016, 28(9): 1605-1612. DOI:10.3969/j.issn.1003-9775.2016.09.025.

Zhan Wenfa, Liang Huaguo, Cheng Yifei, et al. Test data compression coding-based scheme storing integers represented for irrational numbers[J].JournalofComputer-AidedDesign&ComputerGraphics, 2016,28(9): 1605-1612. DOI:10.3969/j.issn.1003-9775.2016.09.025.(in Chinese)

[11] 吳瓊, 黃麗. 基于邏輯運算的折半劃分測試數(shù)據(jù)壓縮方法[J]. 系統(tǒng)仿真學(xué)報, 2015, 27(6): 1324-1328.

Wu Qiong, Huang Li. Test data compression based on logical operational dimidiate partition[J].JournalofSystemSimulation. 2015,27(6): 1324-1328.

[12] El-Maleh A H, Khursheed S S, Sait S M. Efficient static compaction techniques for sequential circuits based on reverse-order restoration and test relaxation[J].IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems, 2006,25(11): 2556-2564. DOI:10.1109/ats.2005.53.

[13] Liang H G,Hellebrand S,Wunderlich H J. Twodimensional test data compression for scan-based deterministic BIST [J].JournalofElectronicTesting:TheoryandApplications, 2002,18(2): 159-170.

[14] 周彬, 葉以正, 李兆麟. 基于二維測試數(shù)據(jù)壓縮的BIST方案[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2009, 21(4):481-486,492.

Zhou Bin, Ye Yizheng, Li Zhaolin. BIST scheme based on two-dimensional test data compression[J].JournalofComputer-AidedDesign&ComputerGraphics, 2009,21(4): 481-486,492. (in Chinese)

[15] 詹文法, 吳瓊, 程一飛, 等. 嵌入廣義折疊技術(shù)的集成電路測試數(shù)據(jù)壓縮方案[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報， 2017, 29(8):1542-1548.

Zhan Wenfa, Wu Qiong, Cheng Yifei, et al. Integrated circuit test data compression scheme built-in generalized folding technology [J].JournalofComputer-AidedDesign&ComputerGraphics, 2017,29(8):1542-1548.(in Chinese)