基于最小集合覆蓋求解方法的測(cè)試向量集約簡(jiǎn)

歐陽丹彤，郭江姍，張立明?

（1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林長(zhǎng)春 130012；2.符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室（吉林大學(xué)），吉林長(zhǎng)春 130012）

隨著集成電路設(shè)計(jì)（Integrated Circuit，IC）及工藝技術(shù)的發(fā)展，人們對(duì)設(shè)計(jì)精度的要求不斷提高，IC設(shè)計(jì)復(fù)雜度近乎呈指數(shù)增長(zhǎng)，芯片故障的測(cè)試愈發(fā)困難[1].在數(shù)字電路測(cè)試中，自動(dòng)測(cè)試向量生成（Automatic Test Pattern Generation，ATPG）是對(duì)被測(cè)電路生成測(cè)試向量的過程.首先向被測(cè)電路中插入故障列表，將ATPG 產(chǎn)生的測(cè)試向量作為數(shù)字電路的輸入序列，根據(jù)實(shí)際輸出信號(hào)與無故障電路預(yù)期值的差異，區(qū)分正常的電路行為和由故障引起的故障電路行為，以此來檢測(cè)相應(yīng)的故障[2].由ATPG 產(chǎn)生的高質(zhì)量的測(cè)試向量集將進(jìn)一步被應(yīng)用到全掃描IC設(shè)計(jì)或規(guī)整的部分掃描設(shè)計(jì).因此，ATPG 作為IC 設(shè)計(jì)流程的重要組成部分之一[3]，工業(yè)界和學(xué)術(shù)界許多學(xué)者對(duì)其進(jìn)行了研究.

工業(yè)上，ATPG 方法逐漸被集成在電子設(shè)計(jì)自動(dòng)化（Electronic Design Automation，EDA）工具中以實(shí)現(xiàn)工業(yè)IC 的設(shè)計(jì)，其中較為著名的ATPG 工具有Synopsys 研發(fā)的Tetra MAX ATPG 和Cadence 研發(fā)的Encounter?Test 等.其中Tetra MAX ATPG 以其簡(jiǎn)潔的圖形用戶界面和強(qiáng)大的命令行被廣泛應(yīng)用，本文中將其簡(jiǎn)稱為TMAX.TMAX 支持多種設(shè)計(jì)風(fēng)格和測(cè)試方法，可以在較短的時(shí)間內(nèi)生成具有高故障覆蓋率的測(cè)試向量集，以滿足后續(xù)IC 設(shè)計(jì)要求.

在學(xué)術(shù)界，國內(nèi)外許多研究人員都對(duì)ATPG 方法進(jìn)行了研究和改進(jìn).1966 年Roth 提出了第一個(gè)關(guān)于非冗余組合邏輯電路的ATPG 方法D 方法[4]，D 方法基于多維敏化思路，對(duì)可測(cè)故障生成測(cè)試向量，理論上解決了非冗余組合電路的測(cè)試問題，但不能對(duì)冗余電路和有重聚扇出電路進(jìn)行測(cè)試向量生成.Geol 提出了D 方法的改進(jìn)方法PODEM 方法[5]，主旨是對(duì)激活的故障回溯其原始輸入，搜索所有可能的原始輸入值，只要選取一個(gè)滿足要求的原始輸入即可作為測(cè)試向量，循環(huán)搜索，直到完成所有故障回溯.PODEM 方法減少了D 方法中回溯與判決的測(cè)試，有效提高了計(jì)算效率，但仍存在回溯的問題.1983 年，F(xiàn)ujiwara 等提出了PODEM 的改進(jìn)方法FAN 方法[6]，引入了唯一蘊(yùn)涵、唯一敏化、多路回退和頭線等概念，采用頭線和扇出的回溯方式，有效降低了回溯次數(shù)和執(zhí)行時(shí)間，并在扇出點(diǎn)方面做了改進(jìn).此后，許多學(xué)者相繼地提出了ATPG 的改進(jìn)方法，如Schulz等人提出的基于FAN 算法的改進(jìn)算法SOCRATES方法[7]，Bryant 提出的簡(jiǎn)化排序二元決策圖ROBDD方法[8]，Larrabee 和Stephan 等人提出的基于SAT 的ATPG 方法[9-10]，等等.

隨著ATPG 方法的發(fā)展，由ATPG 生成的測(cè)試向量集也被應(yīng)用于更多的研究測(cè)試中，但由于生成的測(cè)試向量集規(guī)模龐大，其中可能包含大量的冗余測(cè)試向量，對(duì)測(cè)試電路成本有較大影響[11-12].因此，對(duì)測(cè)試向量集進(jìn)行優(yōu)化，剔除冗余測(cè)試向量，對(duì)降低測(cè)試成本和測(cè)試時(shí)間是十分必要的.故障測(cè)試向量集的優(yōu)化常見有動(dòng)態(tài)優(yōu)化[13]和靜態(tài)優(yōu)化[14].動(dòng)態(tài)優(yōu)化是在測(cè)試向量集生成過程中，通過將ATPG 方法與測(cè)試集壓縮方法同時(shí)進(jìn)行，在生成測(cè)試向量的同時(shí)壓縮測(cè)試向量集，完成測(cè)試向量集優(yōu)化；靜態(tài)優(yōu)化則是在ATPG 得到測(cè)試向量集后，在保證故障覆蓋率不變的基礎(chǔ)上縮減測(cè)試集規(guī)模.

靜態(tài)測(cè)試集優(yōu)化問題已被證明NP 完全問題[15]，王小港[16]提出基于遺傳算法的測(cè)試集約簡(jiǎn)方法，該方法將測(cè)試向量作為染色體，通過編碼方式和評(píng)估函數(shù)的設(shè)計(jì)，實(shí)現(xiàn)測(cè)試集約簡(jiǎn)并取得較好的效果，但由于遺傳算法參數(shù)設(shè)置較多，如種群大小、變異概率、交叉概率等的變化，使得優(yōu)化效果可能不同；康波等學(xué)者[17]提出了基于混沌遺傳算法的測(cè)試集約簡(jiǎn)方法，利用混沌序列的隨機(jī)性、遍歷性及規(guī)律性等特點(diǎn)來控制遺傳算法中的交叉與變異操作，并通過實(shí)驗(yàn)驗(yàn)證該方法明顯優(yōu)于標(biāo)準(zhǔn)遺傳算法，但是由于混沌序列的隨機(jī)性，該算法運(yùn)行時(shí)間變動(dòng)較大；喬家慶等學(xué)者[18]采用遺傳算法對(duì)測(cè)試向量排列順序進(jìn)行優(yōu)化，同時(shí)采用行列消去法作為適應(yīng)度評(píng)估方法，能有效減少測(cè)試向量的數(shù)目且優(yōu)于傳統(tǒng)遺傳算法，但遺傳算法收斂速度慢，容易產(chǎn)生局部最優(yōu)的情況；侯艷麗等學(xué)者[19]將粒子群算法應(yīng)用于測(cè)試集約簡(jiǎn)，通過構(gòu)造粒子的表達(dá)方式和編碼規(guī)則，建立粒子群速度-位置模型，利用混沌優(yōu)化算法來初始化粒子群，使得初始個(gè)體本身為一個(gè)完備測(cè)試集，具有較好的約簡(jiǎn)效果，但是使用的參數(shù)往往依據(jù)經(jīng)驗(yàn)設(shè)置，不便于操作；姜偉等學(xué)者[20]提出的基于粒子群的多目標(biāo)測(cè)試集優(yōu)化方法（DPSO），以最大故障檢測(cè)率、最少測(cè)試數(shù)目和最小測(cè)試代價(jià)為優(yōu)化目標(biāo)，對(duì)測(cè)試集進(jìn)行約簡(jiǎn)，取得了較好的約簡(jiǎn)效果，在實(shí)際應(yīng)用中具備一定的局限性.因此，本文提出基于最小集合覆蓋求解方法的完備測(cè)試向量集求解方法（Complete Test Pattern Set Solution，CTPSS），該方法將故障集與測(cè)試向量集中每個(gè)測(cè)試向量建立對(duì)應(yīng)關(guān)系，通過重新建模，將測(cè)試集約簡(jiǎn)問題轉(zhuǎn)化為最小集合覆蓋問題求解，將復(fù)雜的實(shí)際問題通過簡(jiǎn)單的模型加以解決.

最小集合覆蓋問題作為經(jīng)典NP 完全問題，已被應(yīng)用于各個(gè)領(lǐng)域[21]，相較精確求解方法，啟發(fā)式求解方法更適用于大規(guī)模問題的求解.在文獻(xiàn)[22]中提出一種行加權(quán)局部搜索方法（Row Weighting Local Search，RWLS），該方法提出預(yù)處理步驟，在局部搜索前有效減少搜索空間，且采用多個(gè)禁忌策略有效避免搜索的重復(fù)和循環(huán)，實(shí)驗(yàn)證明該方法針對(duì)大規(guī)模問題仍可在有限時(shí)間內(nèi)獲得更佳解.因此，本文提出的CTPSS 方法結(jié)合RWLS 方法實(shí)現(xiàn)測(cè)試向量集約簡(jiǎn)，其優(yōu)點(diǎn)為：1）模型適配，最小集合覆蓋問題可以有效求解測(cè)試向量集約簡(jiǎn)問題，且不會(huì)降低測(cè)試向量集的覆蓋率；2）模型簡(jiǎn)潔，參數(shù)設(shè)置僅需終止條件，即最大的迭代次數(shù)；3）預(yù)處理階段可有效縮減部分?jǐn)?shù)據(jù)規(guī)模，提高計(jì)算效率.

1 預(yù)備知識(shí)

本節(jié)將給出集合覆蓋的相關(guān)概念，并示例說明.

定義1 最小集合覆蓋[21].給定非空元素集合R和一個(gè)R 上的子集族S，最小集合覆蓋問題（the Minimum Set Covering Problem，MSCP） 是求解一個(gè)S 的一個(gè)子集族C?S，滿足C 可以覆蓋R 中所有元素且C 的規(guī)模最小.一個(gè)最小集合覆蓋實(shí)例表示為MSCP（R，S），其中稱R 為元素集合，S 為初始子集族.

下面通過給出的實(shí)例對(duì)上述概念進(jìn)行說明.

例1 對(duì)于MSCP（R，S），其中R={a，b，c，d，e}，S={{a，e}，{b，c}，{b，c，d}，{b，d}，{a，d}}，可知Sa={{a，e}，{b，c，d}}，Sb={{a，e}，{b，c}，{b，c，d}}，Sc={{a，e}，{b，c}，{b，d}}，Sd={{a，e}，{b，c}，{a，d}} 均可覆蓋R 中所有元素，但Sa規(guī)模最小，故MSCP（R，S）的解C=Sa={{a，e}，{b，c，d}}.

根據(jù)整數(shù)規(guī)劃的定義形式，一個(gè)集合覆蓋實(shí)例可以用0-1 矩陣表示.RWLS 方法即在MSCP（R，S）的0-1 矩陣基礎(chǔ)上，通過行加權(quán)的方式，獲取最小集合覆蓋最優(yōu)解，下節(jié)將給出具體介紹.

2 RWLS 方法

本節(jié)將給出RWLS 方法的偽代碼描述及其分值計(jì)算方式相關(guān)定義.

2.1 RWLS 方法

本小節(jié)將給出RWLS 方法具體介紹，其偽代碼如算法1 所示，可分為三個(gè)部分：前期準(zhǔn)備、預(yù)處理和局部搜索求解.

在前期準(zhǔn)備階段，完成MSCP（R，S）問題讀入，并設(shè)置算法停止條件，以獲取限定條件內(nèi)的最優(yōu)解，此為RWLS 方法的唯一參數(shù).

預(yù)處理階段作為RWLS 方法的一個(gè)重要部分，其目的是保證禁忌策略的有效性.在此階段，對(duì)R 中每一個(gè)元素，檢查能夠覆蓋該元素的集合的個(gè)數(shù)，若其值為1，即代表該集合一定會(huì)被放入候選解集中，則可以將該集合及此集合可覆蓋的所有元素從原問題中移除.

局部搜索求解階段作為RWLS 方法的關(guān)鍵部分，它實(shí)現(xiàn)了一個(gè)擾動(dòng)搜索的框架，假設(shè)初始候選解集C 的大小為k，若存在更優(yōu)的解，則其規(guī)模一定小于k.故首先破壞C 的可行性，后通過Add 和Remove操作[22]不斷擾動(dòng)C 并試圖使C 重新變成可行，以獲取更優(yōu)解.同時(shí)，RWLS 方法采用了多個(gè)禁忌策略[23]避免搜索的重復(fù)和循環(huán)，包括有禁忌列表tabu_list，時(shí)間戳timestamp 以及布爾狀態(tài)檢查canAddToSolution，并采用一個(gè)權(quán)重增長(zhǎng)策略以幫助算法跳出局部最優(yōu).其算法流程圖如圖1 所示，其中，L 為R 中未被候選解集C 覆蓋的元素的集合.

圖1 LocalSearch 方法流程圖Fig.1 The flowchart of LocalSearch

由此可知，每個(gè)集合的分值為L(zhǎng)ocalSearch 方法集合選取的一個(gè)重要因素，下小節(jié)將給出RWLS 方法的分值計(jì)算方法.

2.2 RWLS 方法分值計(jì)算

本小節(jié)將給出RWLS 方法的分值的計(jì)算方式.

定義2 分值score（Sj）.若weight（xi）表示元素xi的權(quán)重，則對(duì)于集合族S 中任意元素Sj，score（Sj）的值為：

其中，σ（C，xi）=，Xi為集合族S 中所有可以覆蓋元素xi的集合構(gòu)成的子集族，即σ（C，xi）表示當(dāng)前候選解集C 中能夠覆蓋元素xi的集合的個(gè)數(shù).RWLS 方法僅考慮σ（C，xi）=0 和σ（C，xi）=1 兩種情況：當(dāng)集合Sj?C 時(shí)，score（Sj）為當(dāng)前所有能被集合Sj覆蓋且未被C 覆蓋的元素xi的權(quán)重之和；當(dāng)集合Sj∈C 時(shí)，score（Sj）為一個(gè)負(fù)數(shù)，即當(dāng)前所有能且僅能被集合Sj覆蓋的元素xi的權(quán)重之和的相反數(shù).由此可以看出，當(dāng)從C 中添加或刪除一個(gè)集合Sj時(shí)，與其具有相同可覆蓋元素的集合的分值均有可能發(fā)生變化，需重新計(jì)算.

3 CTPSS 方法

本節(jié)將給出測(cè)試集約簡(jiǎn)問題的建模過程，并給出CTPSS 方法的相關(guān)定義以及其偽代碼描述.

3.1 問題建模

本小節(jié)將給出測(cè)試集約簡(jiǎn)建模的相關(guān)概念及定義，并給出建模過程.

定義3 故障列表.由電路中所有可能發(fā)生的故障組成，記為F={ f0，f1，…，fm}，其中m 為F 中元素的個(gè)數(shù).

定義4 故障族FS.若對(duì)于測(cè)試向量集T={t0，t1，t2，…，tn}中任意一測(cè)試向量tj（0≤j≤n），F(xiàn)j={fa，fb，fc，…}為tj能夠覆蓋的故障列表F 的故障子集，其中0≤a，b，c≤m，則稱{F0，F(xiàn)1，F(xiàn)2，…，F(xiàn)n}為這個(gè)測(cè)試向量集T 對(duì)應(yīng)的故障族，記作FS.

定義5 候選測(cè)試向量集TC.稱TC={ta，tb，tc，…}，其中0≤a，b，c≤n 為故障列表F 的一個(gè)候選測(cè)試向量集，當(dāng)且僅當(dāng)TC?T 且

候選測(cè)試向量集也可稱為完備測(cè)試向量集，稱候選測(cè)試向量集TC是最小完備測(cè)試集，當(dāng)且僅當(dāng)TC的任意一個(gè)真子集都不是候選測(cè)試向量集.

定義6 故障-測(cè)試矩陣FT.對(duì)于故障列表F={f0，f1，…，fm}和測(cè)試向量集T={t0，t1，t2，…，tn}，故障-測(cè)試矩陣可以記作：

其中，對(duì)于矩陣中任意元素ftij（0≤i≤m，0≤j≤n），ftij=1 表示測(cè)試向量tj可以觀測(cè)到故障fi，反之，若測(cè)試向量tj不能觀測(cè)到故障fi，則ftij=0.

測(cè)試向量集約簡(jiǎn)可以描述為，從測(cè)試向量T={t0，t1，t2，…，tn}中選取子集TC?T，使之能夠覆蓋故障列表F={ f0，f1，K，fm}中所有元素.根據(jù)上述相關(guān)定義，測(cè)試向量集約簡(jiǎn)問題可進(jìn)一步描述為，從測(cè)試向量集T 對(duì)應(yīng)的故障族FS={ F0，F(xiàn)1，F(xiàn)2，…，F(xiàn)n}中選取一個(gè)集合族FC={ Fa，F(xiàn)b，F(xiàn)c，…}，0≤a，b，c≤n，使之能夠覆蓋故障列表F={f0，f1，…，fm}中所有元素.根據(jù)上述描述，測(cè)試向量集約簡(jiǎn)可以被轉(zhuǎn)化為可由RWLS 方法求解的最小集合覆蓋實(shí)例MSCP（F，F(xiàn)S），其中，故障-測(cè)試矩陣FT 等同于集合覆蓋實(shí)例所轉(zhuǎn)化0-1 矩陣.此外，本文給出必然測(cè)試向量定義如下.

定義7 必然測(cè)試向量.若存在故障fk∈F，能且僅能被一個(gè)測(cè)試向量tj∈T 覆蓋，則稱測(cè)試向量tj為必然測(cè)試向量.

在預(yù)處理階段，必然測(cè)試向量tj及其可覆蓋的故障集Fj將暫時(shí)從原問題中移除，從而縮小局部搜索求解方法的矩陣規(guī)模，提高運(yùn)行效率.下小節(jié)將給出CTPSS 方法的具體過程.

3.2 CTPSS 算法描述

本小節(jié)給出了CTPSS 算法的偽代碼，并給予相關(guān)說明.

古建筑是傳統(tǒng)“雖由人造，宛如天開”理念的集中體現(xiàn)，加強(qiáng)仿古建筑結(jié)構(gòu)施工技術(shù)的研究，能夠有效避免建設(shè)中對(duì)人力、物力、材料資源的浪費(fèi)和損耗，并且有利于中國優(yōu)秀的傳統(tǒng)文化弘揚(yáng)，讓人民群眾在閑適、自然、輕松環(huán)境中，體驗(yàn)“天人合一”“道法自然”的人文精神。

第2～8 行獲取TMAX 生成的測(cè)試向量及其對(duì)應(yīng)故障列表：readNetlist（）用于讀取電路文件，若當(dāng)前電路為時(shí)序邏輯電路，則需要進(jìn)一步讀入與其相關(guān)的時(shí)鐘信息文件；初始化故障族FS，候選解集C 和最優(yōu)解bestSol；通過運(yùn)行TMAX 得到初始測(cè)試向量集T 以及故障列表F；第5～8 行為獲取集合簇FS，通過pat_get（）函數(shù)將測(cè)試向量集T 分割為多個(gè)獨(dú)立可執(zhí)行測(cè)試向量tj，使之可以被TMAX 識(shí)別，從而得到tj可覆蓋的故障集合Fj，最終獲得故障族FS.

第9～17 行調(diào)用RWLS 方法：讀入最小集合覆蓋實(shí)例MSCP（F，F(xiàn)S）；設(shè)置終止條件，本文中將其設(shè)定為一個(gè)預(yù)期最大迭代次數(shù)，同時(shí)若當(dāng)前候選解集規(guī)模小于等于必然測(cè)試向量數(shù)目加1，則算法可提前終止，當(dāng)前候選解集即為最優(yōu)解；在預(yù)處理階段添加函數(shù)check（）來檢測(cè)每個(gè)故障的被覆蓋次數(shù)，若故障的被覆蓋次數(shù)為1，則存在必然測(cè)試向量fi，通過函數(shù)GetMust（）獲取tj并予以標(biāo)記后加入到候選解集C 中，將其可覆蓋故障集合Fj中所有元素從未覆蓋列表L 中移除，以保證后續(xù)禁忌策略成功進(jìn)行；局部搜索求解階段，以預(yù)處理得到的部分候選解集C 為輸入，貪婪算法初始化得到完整的初始候選解集C，最后調(diào)用LocalSearch（）方法得到最優(yōu)解.

第18～19 行為驗(yàn)證過程，使用change（）函數(shù)獲取bestSol 中的測(cè)試向量，組合后得到新的測(cè)試向量集TC，并通過Get_fc（）調(diào)用TMAX 對(duì)新測(cè)試向量集TC與基礎(chǔ)測(cè)試向量T 的故障覆蓋率進(jìn)行對(duì)比，若兩者相同則證明此次約簡(jiǎn)成功.

4 實(shí)驗(yàn)與結(jié)果

本節(jié)給出了CTPSS 方法的實(shí)驗(yàn)分析，實(shí)驗(yàn)環(huán)境如下：Ubuntu 14.04，CPU Intel Core i5 -8250U 1.80GHz，8GB RAM，python 和C++，使用TetraMAX生成初始測(cè)試向量集并完成后續(xù)覆蓋率檢驗(yàn).本文使用的測(cè)試電路為基準(zhǔn)電路ISCAS85[24]，全掃描版本的ISCAS89[25]電路和ITC99[26]電路.

同時(shí)在實(shí)驗(yàn)對(duì)比中，本文選取了文獻(xiàn)[20]中的DPSO 方法，DPSO 方法以最大故障覆蓋率、最少測(cè)試向量數(shù)量和最小代價(jià)為優(yōu)化目標(biāo)，取得了較好的測(cè)試向量集約簡(jiǎn)效果.因此，在實(shí)際所需代價(jià)相同的情況下，本文以TMAX 提供的初始測(cè)試向量集故障覆蓋率為最大故障覆蓋率，即保證測(cè)試向量集覆蓋率不變，以約簡(jiǎn)后的測(cè)試向量集規(guī)模為統(tǒng)一衡量指標(biāo)，對(duì)CTPSS 方法與DPSO 方法進(jìn)行了實(shí)驗(yàn)結(jié)果對(duì)比.同時(shí)，DPSO 方法終止條件與CTPSS 方法終止條件均為預(yù)期最大迭代次數(shù)，但DPSO 方法無預(yù)處理步驟，因此，可通過對(duì)比實(shí)驗(yàn)驗(yàn)證CTPSS 方法的預(yù)處理步驟在測(cè)試向量集約簡(jiǎn)問題中的重要性.

4.1 故障模型

在使用TMAX 生成故障列表時(shí)，使用故障模型為固定型故障（Stuck-at Fault，SAF）.SAF 故障模型是ATPG 工具中常用的故障類型，很多故障模型也可以用不同的SAF 組合表示而成.一個(gè)能夠?qū)AF故障具有較高覆蓋率的測(cè)試向量集對(duì)其它故障類型也會(huì)具有較高的故障覆蓋率[27]，該測(cè)試向量集的實(shí)用性較高.

同時(shí)，為驗(yàn)證CTPSS 算法對(duì)于多種故障類型同樣適用，選取TMAX 支持的靜態(tài)電路故障（Integrated Circuit Quiescent Current Fault，IDDQ）中的the pseudo-stuck-at model 故障模型[28]進(jìn)行了實(shí)驗(yàn)，此類故障類型也較容易獲得較高的故障覆蓋率.

4.2 CTPSS 實(shí)驗(yàn)結(jié)果

表1 中給出了CTPSS 方法與DPSO 方法實(shí)驗(yàn)結(jié)果對(duì)比，其中，約簡(jiǎn)后測(cè)試向量集故障覆蓋率均與初始測(cè)試向量集故障覆蓋率相同，故障類型為SAF.

其中，第1 列（Cir Name）為電路名稱，以S 開頭的電路為ISCAS89 電路，以B 開頭的電路為ITC99電路；第2 列（Flt Num）為該電路中插入的SAF 故障類型的故障列表F 的規(guī)模；第3 列（TMAX）為TMAX生成的具有高故障覆蓋率的初始測(cè)試向量集T 的規(guī)模；第4～7 列為CTPSS 方法與DPSO 方法得到的故障覆蓋率不變的縮減后的測(cè)試向量集規(guī)模（Pat Num）及其對(duì)應(yīng)的縮減率（Re Rate），其中縮減率為減少的測(cè)試向量在初始測(cè)試向量集中所占的比例.實(shí)驗(yàn)過程中，將CTPSS 方法和DPSO 方法的終止條件最高迭代次數(shù)均設(shè)置為5 × 103次.由于部分電路規(guī)模較大，DPSO 算法在可接受范圍內(nèi)不能產(chǎn)生解，表示為“—”.

從表1 可以看出，CTPSS 方法對(duì)測(cè)試集的縮減效果明顯優(yōu)于DPSO 方法，且對(duì)于大規(guī)模電路，CTPSS 方法同樣可以得到良好的縮減效果.對(duì)于表1中所有電路，85%的電路測(cè)試集在CTPSS 方法中縮減率高達(dá)20%，其中縮減率高于30%的占23%左右.因此，可以看出CTPSS 方法對(duì)測(cè)試向量集的縮減有著良好的效果，可以有效縮減測(cè)試向量集，從而降低電路測(cè)試成本.

表2 給出了預(yù)處理階段必然測(cè)試向量數(shù)目（Num of tj）與約簡(jiǎn)后的測(cè)試向量集數(shù)目（Num of TC）的對(duì)比，實(shí)驗(yàn)數(shù)據(jù)表明，在測(cè)試向量集約簡(jiǎn)這一實(shí)際問題中，預(yù)處理階段在縮減算法數(shù)據(jù)規(guī)模上有著明顯效果.

同時(shí)，表2 給出了CTPSS 方法的實(shí)際平均迭代次數(shù)（iterations），而DPSO 方法因無預(yù)處理步驟不能提前終止算法，其實(shí)際平均迭代次數(shù)均為5×103.迭代次數(shù)作為DPSO 方法與CTPSS 方法的算法終止條件，同時(shí)也是影響算法時(shí)間復(fù)雜度的重要因素.假設(shè)算法最大迭代次數(shù)為m，測(cè)試向量集規(guī)模為N，則DPSO 方法的時(shí)間復(fù)雜度可表示為O（N×m）[20-29].同時(shí)，對(duì)于CTPSS 方法，其最好時(shí)間復(fù)雜度為O（N），即在預(yù)處理產(chǎn)生的必然測(cè)試向量基礎(chǔ)上，僅需少數(shù)迭代就可以滿足算法終止條件，如表2 中電路s27、s208_1 等；其最壞時(shí)間復(fù)雜度為O（d×m），在已標(biāo)記必然測(cè)試向量的大規(guī)模電路中，d 的值往往小于N.因此，由以上分析可知，CTPSS 方法的時(shí)間復(fù)雜度一般優(yōu)于DPSO 方法.

表1 CTPSS 與DPSO 結(jié)果對(duì)比Tab.1 Comparison of CTPSS and DPSO results

表2 tj 數(shù)目與TC 數(shù)目對(duì)比Tab.2 Comparison of the number of tj and TC

為驗(yàn)證CTPSS 方法對(duì)于其他故障類型同樣適用，表3 給出了CTPSS 方法在ISCAS85 電路上分別采用SAF 故障類型與IDDQ 故障類型下的實(shí)驗(yàn)結(jié)果.左側(cè)為故障類型為SAF 時(shí)的實(shí)驗(yàn)數(shù)據(jù)，右側(cè)為故障類型為IDDQ 時(shí)的實(shí)驗(yàn)數(shù)據(jù).實(shí)驗(yàn)證明對(duì)于不同故障類型，CTPSS 方法都能獲得良好的測(cè)試集約簡(jiǎn)效果.

表3 ISCAS85 在SAF 和IDDQ 下的實(shí)驗(yàn)結(jié)果比較Tab.3 Comparison of ISCAS85 under SAF and IDDQ fault model

5 結(jié)束語

本文通過對(duì)測(cè)試向量集約簡(jiǎn)問題的合理建模，通過建立測(cè)試向量集與故障列表之間的關(guān)系，將其轉(zhuǎn)化為最小集合覆蓋問題，并結(jié)合最小集合覆蓋問題的求解方法行加權(quán)局部搜索方法RWLS 提出了CTPSS 方法，實(shí)現(xiàn)對(duì)TMAX 產(chǎn)生的初始測(cè)試向量集的約簡(jiǎn).CTPSS 方法簡(jiǎn)潔容易操作，提供高效的預(yù)處理過程，確保不降低測(cè)試向量覆蓋率的同時(shí)，實(shí)現(xiàn)測(cè)試向量集的約簡(jiǎn).實(shí)驗(yàn)證明其對(duì)于約簡(jiǎn)不同故障類型生成的測(cè)試向量集均具有良好效果，對(duì)降低后續(xù)電路測(cè)試成本具有重要的現(xiàn)實(shí)意義.但是，當(dāng)問題規(guī)模過大時(shí)，CTPSS 方法存在建模占用空間較大的不足，有待后續(xù)解決.