秦李青顏學(xué)龍

（1.桂林電子科技大學(xué)電子工程與自動化學(xué)院，廣西 桂林 541004；2.桂林電子科技大學(xué)，廣西 桂林 541004）

組合電路的故障測試生成并行ATPG算法研究

秦李青1顏學(xué)龍2

（1.桂林電子科技大學(xué)電子工程與自動化學(xué)院，廣西 桂林 541004；2.桂林電子科技大學(xué)，廣西 桂林 541004）

自動測試向量生成（ATPG）是借助計算機或者其他工具根據(jù)一定的測試生成算法自動的為被測電路生成測試向量的過程。文章給出了一種位級并行（split-into-W-clones）自動測試向量生成算法，該算法的判決按照位邏輯操作運算進行。通過將該算法與 SCOAP可測性測度結(jié)合起來，為該算法前后向蘊涵選擇最優(yōu)路徑，提高每次回溯成功的概率，達(dá)到減少回溯次數(shù)、加速測試向量的生成和提高故障覆蓋率的目的。通過實驗看出改進后的算法具有良好的性能。

位并行自動測試向量生成算法；可測性測度；前后向蘊涵；故障覆蓋率

早期的電路規(guī)模小，開發(fā)者用功能測試的方法就可以完成測試。但隨著集成電路技術(shù)的發(fā)展，被測電路變得越來越龐大復(fù)雜，因此功能測試的方法已不再適用。為了解決測試向量生成的問題，隨后致力于解決該問題的學(xué)者提出了一些算法，根據(jù)這些算法生成測試向量過程的特征，將其分為基于電路結(jié)構(gòu)的 ATPG 算法和基于代數(shù)運算的ATPG算法[1]。另外為了能夠提高ATPG算法的效率，人們將現(xiàn)在正在探索的ATPG問題映射到并行處理機上的方法，并行ATPG技術(shù)可分為故障并行、啟發(fā)式并行、搜索空間并行、功能并行和拓?fù)洳⑿械榷喾N并行測試生成技術(shù)。其思想就是把復(fù)雜的ATPG任務(wù)分解成若干獨立的子任務(wù)，然后把各個子任務(wù)分配給不同的處理機并行執(zhí)行，以提高ATPG總的運行效率[2]。

組合數(shù)字集成電路測試生成方法各式各樣，其中代數(shù)法中典型的是布爾差分法和異或法等。最早提出的測試生成算法是 D算法，后來在此基礎(chǔ)上又逐漸發(fā)展出了 PODEM算法、FAN算法和 SOCRATES算法等多種算法。文獻(xiàn)[3]提出了對搜索空間進行靜態(tài)劃分 ATPG算法（SPPTC），文獻(xiàn)[4]對布爾可滿足性的組合電路ATPG算法進行改進，在采用當(dāng)前最新布爾可滿足性求解程序加速策略的基礎(chǔ)上，引入電路結(jié)構(gòu)信息來實現(xiàn)基于結(jié)構(gòu)的分支決策，文獻(xiàn)[5]提出了無回溯并行多路徑搜索測試向量生成算法（NBMP）。

文中的SWK算法[6]利用的是模擬并行和搜索空間并行，它是一個基于面向通路判決為導(dǎo)向的 ATPG算法。由于在蘊含過程中，SWK算法的判決是以并行信號位進行位邏輯操作，因此可以同時在搜索過程中做出多個決策。

1 SWK算法概述

在SWK算法中，每個信號線用W（cpu word size）的7個位來表示，假設(shè)該信號線標(biāo)號為A，則用和來表示該信號，每一位都是信號A一個獨立位，即在前后向蘊含過程中他們基于決策樹進行獨立的前后向蘊涵，以下介紹各個字母所標(biāo)示的含義：

表1　各個字母的含義

SWK算法類似于傳統(tǒng)的事件驅(qū)動邏輯模擬，SWK算法零延遲事件驅(qū)動并行向量邏輯模擬過程中進行 d-生成、d-傳播、p-生成、p-傳播的操作，每個信號的標(biāo)志位（OBJ）更新。

回溯分為p-回溯和o-回溯兩類，OBJ在回溯過程中會隨時更新。下面是以輸入為A，B和輸出為C的‘與’門為例的p-回溯和o-回溯。

式（1）（4）中S是一個W位的隨機分裂向量 ，式（2）（6）中是S的補。

SWK算法中，在遇到不止一個可能的選擇路徑（p-分裂和o-分裂）即‘或’選擇時，該算法采用的是使用一個W位的隨機分裂矢量器盲目的隨機的選擇一條路徑進行蘊涵，而并不對電路拓?fù)溥壿嫿Y(jié)構(gòu)進行分析，這樣很容易導(dǎo)致該次模擬不成功，必然增加回溯的次數(shù)，從而增加測試向量生成的時間。鑒于此引入了電路設(shè)計中的可測性分析理論應(yīng)用于該測試生成算法中，用于評定每個節(jié)點測試生成的難易，還可以指導(dǎo)確定性測試生成的路徑選擇，為測試生成過程提供更有效的啟發(fā)性信息，實現(xiàn)對原型算法的加速。

2 SWK算法改進

目前國內(nèi)外一些作者已提出了好幾種數(shù)字電路可測性測度的算法，其中影響較大的是 L.H.Goldsteia所提出的稱為SCOAP的可測性測度[7]。SCOAP算法中的可控性度量和可觀察性度量的計算分為組合的和時序的。因此，電路中每個節(jié)點的可測性度量采用6個函數(shù)分別描述，其中4個用于描述它的可控性，2個用于描述它的可觀察性。SCOAP的主要意圖不是分析電路狀態(tài)和初始序列，僅由電路的拓?fù)浣Y(jié)構(gòu)來評定電路的可測試性性能。除此之外SCOAP算法計算簡單，且便于編程，故選擇SCOAP可測性測度。SCOAP可測性測度中，電路每個節(jié)點的可控性表明該節(jié)點取邏輯值0或1的難易程度的重要度量。因此在原型算法的基礎(chǔ)上計算出每個節(jié)點的可控性0值，可控性1值和可觀測性值，當(dāng)遇到處理p-分裂時，比較兩個節(jié)點可觀測性值的大小，取可觀測性值小的節(jié)點作為p蘊涵的路徑；當(dāng)遇到o-分裂時，由于按照其可控制性的度量值從小到大的順序進行排序，因此可以保證能夠按照可控制性由低到高的順序來對各個扇出節(jié)點進行搜索。這樣就使得搜索成功可能性大的路徑所在的節(jié)點排在比較靠前，因而能先從取出進行搜索嘗試；搜索成功可能性小的路徑比較靠后，因而后取出進行搜索嘗試。通過這種排序機制的處理，不但能夠大幅減少成功地搜索到一條路徑所需的平均嘗試次數(shù)，而且也能夠降低單次搜索嘗試所需的平均時間，因而能夠提高路徑搜索效率，實現(xiàn)對算法的加速。

3 結(jié)論

下面是將該算法與SCOAP可測性測度結(jié)合后在VC++6.0中對組合電路ISCAS85運行后所得的實驗數(shù)據(jù)。

表2　實驗數(shù)據(jù)

從表 2數(shù)據(jù)中可以看出，改進后的算法的故障覆蓋率有提高，但在測試向量生成的時間上，測試向量生成的時間明顯減小，因為將該算法與SCOAP可測性測度結(jié)合后，在遇到多路徑‘或’選擇時，SCOAP可測性測度會首先評估各個節(jié)點的可控性和可觀測性，選擇可控性值和可觀測性值小的節(jié)點進行蘊涵，充分利用電路的拓?fù)浣Y(jié)構(gòu)信息來進行最優(yōu)路徑的選擇，從而能加快測試向量的生成。但對于一些對稱電路來說，將可測性測度與該算法結(jié)合起來并不能有效的加速測試向量的生成，因為通過節(jié)點的可控性、可觀測性作路徑選擇時，會遇到節(jié)點可控性值、可觀測性值一樣的情形，而無法做出決策的情形。

[1] 張必超,于鵬.組合數(shù)字集成電路測試生成技術(shù)研究[J].中國測試技術(shù),2007,33(3):105-107.

[2] 許小方,陳光衤禹.自動測試圖形生成的并行處理技術(shù)綜述[J].微電子測試,1994,(1):11-19.

[3] 曾芷德,劉蓬俠.一個基于故障敏化模式分解的并行ATPG算法SPPTG[J].計算機應(yīng)用,2000,(20):177.

[4] 鄧雨春,楊士元,邢建輝.基于布爾可滿足性的組合電路ATPG 算法[J].計算機工程與應(yīng)用,2003(7):78-80.

[5] 黃越,于宗光,萬書芹.無回溯并行多路徑搜索測試向量生成算法[J].計算機應(yīng)用,2010,30(5):1390-1391.

[6] Kuan-Yu Liao, Chia-Yuan Chang, and James Chien-Mo Li.A Parallel Test Pattern Generation Algorithm to Meet Multiple Quality Objectives[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011,30(11):1767-1772.

[7] 徐新河,陳光衤禹,謝永樂.數(shù)字電路可控性算法和 C++程序?qū)崿F(xiàn)[J].電子測量與儀器學(xué)報,2004,(z1):47-50.

The research of test generation parallel ATPG algorithm of fault of combinational circuit

Automatic test pattern generation (ATPG) is the automatic process of generating test vector for the circuit under test according to the test generation algorithm by computer or other tools. This paper presents a bit-level parallel (split-into-W-clones) automatic test vector generation algorithm, which decisions convert into bit-wise logic operation. It selects the optimal path for the forward and backward implication, increases the probability of per backtrace successfully in order to reduce the number of backtrace , accelerate test vector generation and improve the fault coverage by combining the algorithm with the SCOAP testability measure . The improved algorithm has a good performance by the experiment.

A bit-level parallel automatic test vector generation algorithm;the testability measure;the forward and backward implication;the fault coverage

TP206

A

1008-1151(2015)04-0017-02

2015-02-13

秦李青（1987-），女，桂林電子科技大學(xué)工程與自動化學(xué)院碩士研究生，研究方向為可測性設(shè)計與故障診斷；顏學(xué)龍( 1962-)，男，桂林電子科技大學(xué)教授，碩士生導(dǎo)師，研究方向為可測性設(shè)計與故障診斷、測試信號處理等。