基于極小碰集求解算法的測試向量集約簡

歐陽丹彤 陳曉艷 葉 靖 鄧召勇 張立明

1(吉林大學計算機科學與技術學院 長春 130012) 2(計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190) 3(符號計算與知識工程教育部重點實驗室(吉林大學) 長春 130012) 4(中國科學院計算技術研究所 北京 100190)

隨著信息產品需求的增長，集成電路市場也在其帶領下迅速發展，電路的復雜度不斷增加，使得電路的測試成本不斷提高.為了解決這一問題，人們在設計階段就開始考慮可測試性問題，以保證自動測試向量生成(automatic test pattern generation， ATPG)過程得以有效進行.ATPG的任務是針對特定的故障模型確定1個高質量測試向量集(test pattern set, TPS)，使得設計的故障覆蓋率達到期望值[1].在工業界，以Synopsys,Mentor Graphic，Cadence這3家公司為代表的芯片設計公司都提供了商用的ATPG工具.由Synopsys公司開發的TetraMAX ATPG 2018是現階段工業界功能最強和最容易使用的ATPG工具，針對不同的電路設計，TMAX 2018可以在很短的時間內生成具有高故障覆蓋率的TPS.本文中將TetraMAX ATPG 2018簡記為TMAX 2018.

TPS的規模對電路的測試成本，如測試時間、測試功耗以及被測電路的壽命等問題有較大影響[2].為了縮短測試時間、降低測試成本，國內外學者在TPS優化、TPS壓縮等領域進行了大量研究.TPS優化問題根據不同的優化目標可以大致分為2類：1)以故障覆蓋率與故障隔離率為可測試性指標，以測試代價最小為目標對TPS進行優化，在優化的過程中，可測試性指標要求故障覆蓋率與故障隔離率均不低于某個值，是兼顧測試成本、檢測與診斷效果的優化方式[3-4].2)TPS優化問題的目的是對TPS進一步約簡，求出其沒有冗余的最小TPS，使其向量個數最少，同時盡可能保證故障覆蓋率保持不變[5-9].在約簡的過程中，并沒有考慮TPS的診斷效果與測試所需的代價.優化之后的TPS將提供給自動測試儀(automatic test equipment， ATE)的測試程序使用.TPS壓縮問題是指，在ATE測試的過程中，測試數據被存儲在ATE的存儲器中，由于ATE有限的存儲資源和測試帶寬往往難以滿足片上系統高速測試的實際需求，通常要對測試數據進行壓縮，減少測試過程中需要存儲的數據空間，把數據轉換成比原格式更緊湊的形式.測試數據壓縮作用于待測電路對應的TPS，并對其進行壓縮存儲[10-11].

在TPS優化問題研究領域，國內外許多學者對保證TPS覆蓋率不變的同時減少TPS數目的TPS約簡問題進行了研究.俞龍江等人[5]提出基于蟻群算法的TPS約簡算法，對最初的蟻群算法模型進行修正，設置參數較少，多次運行可以獲得相同解，具有較強的魯棒性，但是不能保證最終解中沒有冗余的測試向量；喬家慶等人[6]提出利用遺傳排序算法對TPS中的測試向量順序進行優化，并采用行列消去法作為適應度評估算法，有效地減少了測試向量的數目，優于傳統的遺傳算法，但是遺傳算法本身收斂速度慢、尋優效率低，容易陷入局部最優的算法仍然不可避免；侯艷麗等人[7]將粒子群算法應用于TPS約簡問題，該算法重新定義粒子的位置和速度，利用具有全局優化能力的混沌算法將初始化粒子群，并且粒子針對故障編碼，使得初始個體本身就是1個完備TPS，取得了較好的效果，但使用的參數往往依據經驗設置，以最優解的適應性沒有變化作為結束條件，在實際的應用中有一定的局限性；曹義親等人[8]提出基于粗糙集的TPS優化算法中，利用粗糙集的知識約簡理論構造電路對應知識系統，生成區分函數，對該函數進行求解得到最小TPS，該算法可以有效平衡約簡效果與約簡所用時間，但是不能保證約簡后TPS的覆蓋率與原TPS相同；王宏力等人[9]提出的基于粒子群的多目標TPS優化算法(以下簡記為PSO-Td)，以最大故障覆蓋率和最少測試向量數目為優化目標，對TPS進行約簡，取得了較好的約簡效果.

以上TPS約簡算法在盡可能保證約簡后的TPS故障覆蓋率保持不變的情況下，最大程度減少TPS中的測試向量數目，隨機算法得到的TPS約簡結果具有一定的隨機性.在對以上工作的深入研究基礎上，本文提出基于極小碰集求解算法[12-13]的極小完全測試集求解算法(minimal complete test pattern set reduction, MCTPSR).

該算法只需要針對TPS建立測試向量與需要檢測的故障列表之間的對應關系，生成對應的向量覆蓋集合簇，將TPS的約簡問題轉化為極小碰集的計算問題，即可使復雜的約簡問題通過簡單的模型得到解決.該算法的主要優點有5方面：

1) 可以得到所有的極小解，是完備性算法，同時保證所有解中都沒有冗余的測試向量；

2) 可以很好地適應TPS約簡問題，且其計算效率比較高，約簡產生的開銷遠遠小于因冗余測試所產生的開銷；

3) 模型簡單，僅需要結合測試向量與故障之間的對應關系重新建模即可求解，且求解過程不需要其他參數和多次迭代；

4) 具有選擇的多樣性，對于1個TPS，往往可以得到多個極小解，可以根據實際的測試開銷選擇合適的解；

5) TPS的約簡不會降低故障覆蓋率，同時由MCTPSR算法產生的所有解都可以保證有效性.

1 預備知識

本節介紹TPS約簡問題、基于模型診斷和碰集的相關概念，以及MHS-DMECV算法中使用的相關概念與定義，并通過實例進行說明.

1.1 TPS約簡

例1.設某電路中的故障集F={f0,f1,f2,f3}，TPST={t0,t1,t2}，其中t0對應的故障集為F0={f0,f1}，t1對應的故障集為F1={f2}，t2對應的故障集為F2={f2,f3}.顯然在T中，t1是1個冗余的測試向量，因此會被刪除，最終保留測試向量t1和t3，T′={t1,t3}，使F1∪F3=F，TPST被約簡為T′.

1.2 碰 集

定義1[14].1個系統可定義為1個三元組(SD,COMPS,OBS),其中：

1)SD為系統描述，是一階謂詞公式集;

2)COMPS是系統組成部件的集合，是1個有限常量集；

3)OBS為觀測集，是一階謂詞公式的有限集.

定義2[14].沖突集CS是1個部件集{c1,c2,…,cn}?COMPS，當且僅當SD∪OBS∪{AB(c1),AB(c2),…,AB(cn)}是不一致的.其中AB為一元謂詞，表示“abnormal”.AB(c)為真，當且僅當c異常，且c∈COMPS.

定義3[14].碰集.設CS={Si|i=1,2,…,n}是集合簇，稱HS為CS的1個碰集，如果HS滿足：

1)HS?∪S；

2) 對于任意1個S∈CS都有HS∩S≠?.

集合簇CS的1個碰集是極小碰集(minimal hitting set, MHS)當且僅當它的任意真子集都不是CS的碰集.

例2.對于集合簇CS={{1,2}，{2,3}，{2,4}}，根據碰集的定義，通過計算得到CS的碰集HS有{2}，{1,2}，{2,3}，{2,4}，{1,2,3}，{1,2,4}，{2,3,4}，{1,2,3,4}.其中，集合簇CS的MHS為{2}和{1,3,4}.

1.3 MHS-DMECV算法

本節介紹極小碰集算法MHS-DMECV中的相關定義與概念，并給出實例進行說明.

定義4[12].容量.若集合簇CS中包含元素的個數為n，則稱n為集合簇CS的容量，記為CAP(CS)=n.

設U是集合簇CS中所有元素的并集構成的集合，即U=∪Si={e1，e2，…,em},用Car(U)表示集合U的勢，即集合U中元素的個數.

定義5[12].頻數.若e∈S，則稱集合S含有元素e，記Freq(CS,e)表示集合簇CS中含有元素e的元素的個數，稱為元素e在集合簇CS中的頻數.

定義6[12].元素覆蓋值.若元素e在集合簇CS的某個元素Si(i=1,2,…,n)中出現，且在當前狀態下Si中沒有其他元素出現，則稱元素e覆蓋Si；若對于集合簇CS中的所有元素，元素e能覆蓋的元素個數為C，則稱C為元素e的元素覆蓋值，記為Cover(e).顯然0≤Cover(e)≤Freq(CS,e).

例3.對于集合簇CS={{1，3}，{2，4}，{1，2，3}}，CS的容量Cap(CS)=3，CS中所有元素的并集U={1，2，3，4}，集合U的勢為Car(U)=4，元素1在CS中的頻數Freq(CS，1)=2，因為元素1在CS的元素中出現了2次.對于集合簇CS，若首先選擇元素1，由于它能覆蓋集合{1，2}和{1，2，3}，所以元素1的元素覆蓋值Cover(1)=2，若接著選擇元素2，此時集合{1，2}和{1，2，3}已被覆蓋，所以它能覆蓋的集合只有{2，4}，因此Cover(2)=1，接下來若選擇元素3或4，此時所有集合都被覆蓋，所以Cover(3)和Cover(4)的值在該時刻都為0，因此不需要選擇元素3或4，只需要元素1和2就可以完成對集合簇CS中所有集合的覆蓋.不難看出CS的1個碰集是{1，2}，由于其非空真子集{1}，{2}都不能覆蓋CS中的所有元素，因此{1，2}為CS的1個極小碰集.

2 MHS-DMECV算法

本節通過偽代碼描述MHS-DMECV算法，并通過實例介紹其流程.

算法1.MHS-DMECV算法[12].

輸入：待處理序列Seq、(與Seq對應的)Head鄰接鏈表數組和元素覆蓋值Cover數組、碰集保存容器HittingSet、集合簇CS的元素覆蓋標志數組SetFlag、已覆蓋數AlreadyCover；

輸出：集合簇CS對應的所有MHS.

① 初始化：

AlreadyCover=0，HittingSet=?，

SetFlag=[0×CAP(CS)]，

根據CS初始化Seq序列、Head數組、Cover數組；

② Begin

③ While (Seq≠[])

④e←Seq第1項；

⑤ Ife是最后1項and

Cover(e)+AlreadyCover=Cap(CS)

⑥container←{e}∪HittingSet；

⑦ EndIf

⑧ Ifcontainer是極小碰集

⑨SetMHS=SetMHS∪container；

⑩ Return；

Seq表示對U中元素的Cover值從大到小排列得到的序列；Head是用來存儲U中每個元素對應于CS中的集合索引的鄰接鏈表；update()，update(Seq′)表示更新相關變量信息；un_update()表示撤銷對相關參數的更新；create(Seq)表示構建新的Seq′和與其對應的Head′,Cover′.

例4.對于集合簇CS={{1，3}，{2，3}}，初始時，Cover(1)=1，Cover(2)=1，Cover(3)=2.根據元素的Cover值，得到的Seq序列為[3，1，2]，其對應的Head如圖1所示，此時還沒有元素被選中，因此此時沒有集合被覆蓋，AlreadyCover=0，SetFlag=[0,0].首先處理Seq序列中的第1項“3”，更新相關參數值，AlreadyCover=2，SetFlag=[1,1]，Seq′=[]，CanCover=0，AlreadyCover+CanCover=CAP(CS),因此得到CS的1個碰集{3}，將其加入HittingSet，根據極小碰集的定義判斷出{3}是集合簇CS的1個極小碰集，將其加入SetMHS；接著處理元素1，此時新的待處理序列Seq″=[2],對應的Head如圖2所示，此時AlreadyCover=1，因為集合{1,3}已經被Seq序列中的第2項“1”覆蓋，而集合{2,3}沒有被Seq序列中的第2項“1”覆蓋，因此元素覆蓋標志數組SetFlag=[1,0],可以覆蓋的元素數CanCover=1,由于AlreadyCover+CanCover=CAP(CS),可以得到CS的1個碰集{1,2}，通過判斷得出它是1個極小碰集，將其加入SetMHS；然后處理Seq序列中的第3項“2”，此時Seq中沒有其他元素，AlreadyCover=1,且AlreadyCover+Cover(2)

算法的完備性已在文獻[12]中進行證明.

Fig. 1 The adjacency list Head corresponding to pending sequence Seq′圖1 待處理序列Seq′對應的鄰接鏈表Head

Fig. 2 The adjacency list Head corresponding topending sequence Seq″圖2 待處理序列Seq″對應的鄰接鏈表Head

3 MCTPSR算法

本節對TPS約簡問題進行建模，介紹其與極小碰集求解問題中相關聯的概念，并通過偽代碼描述基于MHS-DMECV的TPS約簡算法MCTPSR.

3.1 問題建模

本節介紹TPS約簡問題的相關概念與定義，并通過實例進行說明，同時對TPS約簡問題進行建模，將其轉化為適合極小碰集求解算法處理的模型.

定義7.故障序列.電路中可能發生的所有故障組成的擁有確定順序的集合，記為F={f0,f1,…,fn}，F的容量為n.

在文獻[6]中描述了完全測試集的概念，下面我們給出標準定義.

稱CTPST是極小完全測試集(minimal complete test pattern set, MCTPS).當且僅當T的任意1個真子集都不是CTPS.

定義9.覆蓋值.如果測試向量ti(ti∈T)可以檢測到電路中的故障fj(fj∈F)，則稱該測試向量ti覆蓋了故障fj，(ti，fj)的覆蓋值為1，記為Cij=1，否則Cij=0.

定義10.故障覆蓋集.若t∈T可以檢測到電路中的故障{fi,fj,…,fk}(0≤i,j,k≤n)，則t對應的故障覆蓋集為{fi,fj,…,fk}(0≤i,j,k≤n)，記為Ft={fi,fj,…,fk}(0≤i,j,k≤n).

定義11.向量-故障矩陣.設T={t0,t1…,tm}是電路的1個TPS，F={f0,f1,…,fn}是電路中的故障序列，由T，F中的元素ti與fj的覆蓋關系Cij組成的矩陣，稱為該電路的向量-故障矩陣，記為PFM.

例5.設TPST={t0,t1,t2,t3}，故障集合F={f0,f1,f2,f3,f4}，其中，t0的故障覆蓋集為F0={f0,f3,f4}，因此可以得到覆蓋值C00=1，C01=0，C02=0，C03=1，C04=1，同理可以得到T中其他測試向量與故障fj∈F的覆蓋值，這些覆蓋值構成PFM，如表1所示.其中，PFM(0,0)=0表示測試向量t0不能覆蓋到故障f0，PFM(1,3)=1表示測試向量t1可以覆蓋到故障f3.從表1可以看出，T={t0,t1,t2,t3}是1個TPS，但由于其子集{t0,t1,t2}依然可以覆蓋F中的全部故障，它顯然不是1個MCTPS.實際上，由F0={f0,f3,f4}，F2={f1,f2,f3}，可以得出F0∪F2=F，因此{t0,t2}構成1個MCTPS，同理，由于F0∪F1∪F3=F，且{t0,t1,t3}的任意1個真子集都不是TPS，因此{t0,t1,t3}也是1個MCTPS.

Table 1 An Example of PFM表1 PFM實例

定義12.向量覆蓋集.若fj∈F，則稱集合Tj是故障fj的向量覆蓋集，如果對于所有的ti∈Tj,都有Cij=1.記為PCS(fj)={ti|Cij=1}.

例6.如表1所示，在故障f0對應的1列數據中，C0j=1的測試向量為t0，0≤j≤3，因此PCS(f0)={0}.同理可得，故障f1對應的PCS(f1)={1,2}，故障f2對應的PCS(f2)={2,3}，故障f3對應的PCS(f3)={0,2,3}，故障f3對應的PCS(f4)={1,2}.

3.2 算法描述

本節給出基于極小碰集算法MHS-DMECV的MCTPS求解算法MCTPSR的偽代碼并對其進行說明.

算法2.MCTPSR算法.

輸入：電路網表文件;

輸出：電路對應的MCTPS.

①mkdir()；

②source_gen()；

③ If需要添加掃描鏈

④run_dc()；

⑤ EndIf

⑥T,F=run_tmax()；

⑦pats=pat_split(T)；

⑧ Fori,pat∈pats

⑨F′=run_tmax_single(pats)；

⑩v=vector_gen(F′,F,T)；

行①mkdir()用于生成電路目錄及子目錄，行②中source_gen()用于生成電路所需的腳本文件；如果當前電路是時序邏輯電路文件，則需要添加掃描鏈以生成綜合網表文件與協議文件(其中規定了掃描鏈與時鐘等約束信息)(行③～⑤)；行⑥～⑦首先通過運行TMAX 2018生成TPST以及故障序列F，并且將T中的測試向量分離為單獨的測試向量pat；之后，每一個測試向量pat作為外部測試向量讀入TMAX 2018可以得到單個測試向量pat對應的故障列表F′并與F，T一起作為vector_gen()的輸入，從而得到PFM中的1行向量v，同時更新PFM(行⑧～)；行表示根據PFM生成向量覆蓋集PCS組成的集合PCSs，作為極小碰集求解算法的輸入；行調用MHS-DMECV算法，產生對應的極小碰集，即電路的MCTPSresults；行～中get_coverage()實際上是結果檢驗的過程，對results中的所有結果，形成新的TPS，載入TMAX 2018檢測TPS的故障覆蓋率是否保持不變.

4 實 驗

本節對MCTPSR算法的性能進行實驗分析，在實驗對比部分，選取TMAX 2018產生的TPS作為比較對象.同時在初始潛在解的覆蓋率最高的情況下對PSO-Td算法進行了重現，并與其實驗結果進行對比.實驗環境為：Ubuntu 14.04，CPU Intel Core i7-4700HQ 2.40 GHz，8 GB RAM，python.使用Design Compiler完成添加掃描鏈的工作，TMAX 2018生成TPS以及新的MCTPS的覆蓋率檢驗.

4.1 故障模型

利用TMAX 2018產生測試集時，所使用的故障模型是固定型故障(stuck-at fault， SAF)，SAF的優點有：

1) 易于生成故障列表，且故障總數隨著電路中的邏輯門的個數線性增長，故障列表的規模可以控制；

2) 可以覆蓋所有SAF的測試集，對于芯片中的其他類型的故障也有很高的覆蓋率；

3) 很多故障模型都可以用不同的SAF的組合表示.

SAF針對芯片中的單個故障，而實際芯片一般包含多個故障，已有實驗表明，可以覆蓋所有單故障的測試集在檢測多故障時同樣擁有很高的覆蓋率[15].因此，本文實驗選擇SAF作為ATPG過程的故障模型.

4.2 實驗結果

本文使用了國際測試界ATPG研發經常使用的基準電路ISCAS85[16]、全掃描版本的ISCAS89[17]電路和ITC99[18]電路，其電路規模如表2所示.

表3～5分別描述了對ISCAS85，ISCAS89，ITC99中的部分電路對應的TPS的約簡效果.表格中的列1(Circuit)是各電路的名字；列2(TMAX)表示電路對應的TMAX 2018生成的TPS中的測試向量數量；列3(MCTPSR)表示通過MCTPSR算法得到的MCTPS中極小TPS中包含的測試向量的數量;列4(Reduce)表示MCTPSR算法約簡掉的測試向量的個數；列5(Reduced Ratio)表示約簡的部分在TPS中所占的比例.

Table 2 Basic Information of Test Circuits表2 測試電路基本信息

Table 3 Comparison in TPS of ISCAS85表3 ISCAS85電路TPS對比

Table 4 Comparison in TPS of ISCAS89表4 ISCAS89電路TPS對比

Table 5 Comparison in TPS of ITC99表5 ITC99電路TPS對比

由表3～5可以看出，針對規模不同、類型不同(ISCAS85是組合邏輯電路，ISCAS89和ITC99是時序邏輯電路)的電路對應的TPS，MCTPSR算法都起到了很好的約簡效果.對所有電路的TPS約簡比例都在10%以上，針對電路c3540和c5315甚至產生了高于50%的約簡效果.

表6中對本文提出的MCTPSR算法與PSO-Td算法結果進行對比，表6中Circuit列表示電路名稱，MCTPSR列表示本文所提算法的約簡結果中的最小解，PSO-Td列表示PSO-Td中提出算法的約簡結果(由于PSO-Td算法的實驗結果具有隨機性，實驗中取近5次實驗結果中的最小值進行比較).PSO-Td算法應用于規模較大的電路時，不能在可接受的范圍內求出解，表6中用空白表示.可以看出MCTPSR算法明顯優于PSO-Td算法.

Table 6 Compare Reduced Results Produced by MCTPSRwith Results of PSO-Td

Table 7 Circuit Number with Different Reduced Ratio Range

Table 8 Number of MCTPS Generated by MCTPSR表8 MCTPSR算法的MCTPS個數

表8中給出由MCTPSR算法得出的MCTPS的個數.可以看出，對于不同的電路，往往有多個MCTPS，MCTPSR算法可以得到所有MCTPS，這為實際的芯片測試過程提供了很強的可選擇性，可以通過計算不同測試集的測試開銷，選擇成本合適的測試集，可以很大程度地降低芯片的測試成本.

實驗結果表明：MCTPSR算法對TMAX 2018產生的TPS有很好的約簡效果，而且可以得到不止1個MCTPS，為芯片測試提供了多種選擇.在實際應用中，可以極大地降低芯片測試成本，加快芯片的生產過程.

5 總 結

本文通過對MCTPS約簡問題進行重新建模，將復雜的約簡問題轉化為極小碰集的求解問題，結合基于動態極大元素覆蓋值求取所有極小碰集的MHS-DMECV算法提出MCTPSR算法，對商用工具TMAX 2018產生的TPS進行約簡，縮減了工具生成的TPS規模，計算效率較高，約簡產生的開銷比較小；其次，該算法的模型簡單，只需要測試向量與故障的對應關系矩陣就可以進行求解，且過程中不需要其他參數，不需要進行多次迭代就可以得到解；該算法對于1個TPS，往往可以得到不止1個極小解，可以根據實際的測試開銷選擇合適的解；同時，TPS的約簡不會降低故障覆蓋率.MCTPSR可以在保證故障覆蓋率的前提下提供更小的TPS，對降低芯片生產過程中的測試開銷有著重要的現實意義.