组合电路的故障测试生成并行ATPG算法研究

秦李青颜学龙

（1.桂林电子科技大学电子工程与自动化学院，广西 桂林 541004；2.桂林电子科技大学，广西 桂林 541004）

组合电路的故障测试生成并行ATPG算法研究

秦李青1颜学龙2

（1.桂林电子科技大学电子工程与自动化学院，广西 桂林 541004；2.桂林电子科技大学，广西 桂林 541004）

自动测试向量生成（ATPG）是借助计算机或者其他工具根据一定的测试生成算法自动的为被测电路生成测试向量的过程。文章给出了一种位级并行（split-into-W-clones）自动测试向量生成算法，该算法的判决按照位逻辑操作运算进行。通过将该算法与 SCOAP可测性测度结合起来，为该算法前后向蕴涵选择最优路径，提高每次回溯成功的概率，达到减少回溯次数、加速测试向量的生成和提高故障覆盖率的目的。通过实验看出改进后的算法具有良好的性能。

位并行自动测试向量生成算法；可测性测度；前后向蕴涵；故障覆盖率

早期的电路规模小，开发者用功能测试的方法就可以完成测试。但随着集成电路技术的发展，被测电路变得越来越庞大复杂，因此功能测试的方法已不再适用。为了解决测试向量生成的问题，随后致力于解决该问题的学者提出了一些算法，根据这些算法生成测试向量过程的特征，将其分为基于电路结构的 ATPG 算法和基于代数运算的ATPG算法[1]。另外为了能够提高ATPG算法的效率，人们将现在正在探索的ATPG问题映射到并行处理机上的方法，并行ATPG技术可分为故障并行、启发式并行、搜索空间并行、功能并行和拓扑并行等多种并行测试生成技术。其思想就是把复杂的ATPG任务分解成若干独立的子任务，然后把各个子任务分配给不同的处理机并行执行，以提高ATPG总的运行效率[2]。

组合数字集成电路测试生成方法各式各样，其中代数法中典型的是布尔差分法和异或法等。最早提出的测试生成算法是 D算法，后来在此基础上又逐渐发展出了 PODEM算法、FAN算法和 SOCRATES算法等多种算法。文献[3]提出了对搜索空间进行静态划分 ATPG算法（SPPTC），文献[4]对布尔可满足性的组合电路ATPG算法进行改进，在采用当前最新布尔可满足性求解程序加速策略的基础上，引入电路结构信息来实现基于结构的分支决策，文献[5]提出了无回溯并行多路径搜索测试向量生成算法（NBMP）。

文中的SWK算法[6]利用的是模拟并行和搜索空间并行，它是一个基于面向通路判决为导向的 ATPG算法。由于在蕴含过程中，SWK算法的判决是以并行信号位进行位逻辑操作，因此可以同时在搜索过程中做出多个决策。

1 SWK算法概述

在SWK算法中，每个信号线用W（cpu word size）的7个位来表示，假设该信号线标号为A，则用和来表示该信号，每一位都是信号A一个独立位，即在前后向蕴含过程中他们基于决策树进行独立的前后向蕴涵，以下介绍各个字母所标示的含义：

表1　各个字母的含义

SWK算法类似于传统的事件驱动逻辑模拟，SWK算法零延迟事件驱动并行向量逻辑模拟过程中进行 d-生成、d-传播、p-生成、p-传播的操作，每个信号的标志位（OBJ）更新。

回溯分为p-回溯和o-回溯两类，OBJ在回溯过程中会随时更新。下面是以输入为A，B和输出为C的‘与’门为例的p-回溯和o-回溯。

式（1）（4）中S是一个W位的随机分裂向量 ，式（2）（6）中是S的补。

SWK算法中，在遇到不止一个可能的选择路径（p-分裂和o-分裂）即‘或’选择时，该算法采用的是使用一个W位的随机分裂矢量器盲目的随机的选择一条路径进行蕴涵，而并不对电路拓扑逻辑结构进行分析，这样很容易导致该次模拟不成功，必然增加回溯的次数，从而增加测试向量生成的时间。鉴于此引入了电路设计中的可测性分析理论应用于该测试生成算法中，用于评定每个节点测试生成的难易，还可以指导确定性测试生成的路径选择，为测试生成过程提供更有效的启发性信息，实现对原型算法的加速。

2 SWK算法改进

目前国内外一些作者已提出了好几种数字电路可测性测度的算法，其中影响较大的是 L.H.Goldsteia所提出的称为SCOAP的可测性测度[7]。SCOAP算法中的可控性度量和可观察性度量的计算分为组合的和时序的。因此，电路中每个节点的可测性度量采用6个函数分别描述，其中4个用于描述它的可控性，2个用于描述它的可观察性。SCOAP的主要意图不是分析电路状态和初始序列，仅由电路的拓扑结构来评定电路的可测试性性能。除此之外SCOAP算法计算简单，且便于编程，故选择SCOAP可测性测度。SCOAP可测性测度中，电路每个节点的可控性表明该节点取逻辑值0或1的难易程度的重要度量。因此在原型算法的基础上计算出每个节点的可控性0值，可控性1值和可观测性值，当遇到处理p-分裂时，比较两个节点可观测性值的大小，取可观测性值小的节点作为p蕴涵的路径；当遇到o-分裂时，由于按照其可控制性的度量值从小到大的顺序进行排序，因此可以保证能够按照可控制性由低到高的顺序来对各个扇出节点进行搜索。这样就使得搜索成功可能性大的路径所在的节点排在比较靠前，因而能先从取出进行搜索尝试；搜索成功可能性小的路径比较靠后，因而后取出进行搜索尝试。通过这种排序机制的处理，不但能够大幅减少成功地搜索到一条路径所需的平均尝试次数，而且也能够降低单次搜索尝试所需的平均时间，因而能够提高路径搜索效率，实现对算法的加速。

3 结论

下面是将该算法与SCOAP可测性测度结合后在VC++6.0中对组合电路ISCAS85运行后所得的实验数据。

表2　实验数据

从表 2数据中可以看出，改进后的算法的故障覆盖率有提高，但在测试向量生成的时间上，测试向量生成的时间明显减小，因为将该算法与SCOAP可测性测度结合后，在遇到多路径‘或’选择时，SCOAP可测性测度会首先评估各个节点的可控性和可观测性，选择可控性值和可观测性值小的节点进行蕴涵，充分利用电路的拓扑结构信息来进行最优路径的选择，从而能加快测试向量的生成。但对于一些对称电路来说，将可测性测度与该算法结合起来并不能有效的加速测试向量的生成，因为通过节点的可控性、可观测性作路径选择时，会遇到节点可控性值、可观测性值一样的情形，而无法做出决策的情形。

[1] 张必超,于鹏.组合数字集成电路测试生成技术研究[J].中国测试技术,2007,33(3):105-107.

[2] 许小方,陈光衤禹.自动测试图形生成的并行处理技术综述[J].微电子测试,1994,(1):11-19.

[3] 曾芷德,刘蓬侠.一个基于故障敏化模式分解的并行ATPG算法SPPTG[J].计算机应用,2000,(20):177.

[4] 邓雨春,杨士元,邢建辉.基于布尔可满足性的组合电路ATPG 算法[J].计算机工程与应用,2003(7):78-80.

[5] 黄越,于宗光,万书芹.无回溯并行多路径搜索测试向量生成算法[J].计算机应用,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] 徐新河,陈光衤禹,谢永乐.数字电路可控性算法和 C++程序实现[J].电子测量与仪器学报,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-），女，桂林电子科技大学工程与自动化学院硕士研究生，研究方向为可测性设计与故障诊断；颜学龙( 1962-)，男，桂林电子科技大学教授，硕士生导师，研究方向为可测性设计与故障诊断、测试信号处理等。