计算机工程
COMPUTER ENGINEERING
1999年 第25卷 第10期 Vol.25 No.10 1999



同时故障模拟方法改进策略
王仲　康葳
摘要：影响同时故障模拟方法效率的原因：一是对扇出重汇聚和过多判定，二是故障表占用窨大，对表的处理时间长。针对上述两点，提出了基于电路结构重组以及两级模拟的策略，以提高故障模拟的效率。针对ISCAS89电路的实验结果也表明了其有效性。
关键词：时序电路；故障模拟；故障表
A Method for Improving the Efficiency of Concurrent Fault Simulation
Wang Zhong Kang Wei
(Electronic Department,Armored Foreed Engineering Instiute,Beijing 100072)
【Abstract】There are two reasons affect the efficiency of concurrent fault simulation,one is overfull computation for the reconvergence gate to identify the testability of the fault,the other is that the fault list take up memory space highly.This paper presents the methods of reconstruction of the circuit and two level simulation of the circuit and two level simulation for improving the efficiency of concurrent fault simulation.Experimental for ISCAS89 benchmark circuits verifies its effecting.
【Key words】Sequential circuit;Fault simulation;Fault list
　　在时序电路测试产生系统中，无论是采用确定性测试产生方法还是基于模拟的测试产生方法，故障模拟器是必不可缺的。故障模拟器效率的高低也直接影响到整个测试产生系统效率的高低。在基于模拟的时序电路测试产生系统中这一点尤为重要。
　　故障模拟器是利用电路的初级输出，对一给定的测试矢量序列，在初级输入施加测试矢量之后用来识别故障对电路初级输出的影响。对每一测试矢量，无故障电路和故障电路分别被模拟，如果故障电路的初级输出值异于无故障电路，那么这个故障是可测的。同时这个故障应从故障表中丢弃，只让故障表中未被检测到故障继续被模拟，这样可以减少故障表对内存的需求，提高故障模拟速度。常用的数字电路故障模拟方法有3种 , 即平行故障模拟、演绎故障模拟和同时故障模拟[1]。
　　平行故障模拟方法容易实现，但平行模拟方法在模拟一个故障所产生的测试矢量序列过程当中，对已检测到的故障不能丢弃，因此其所占用的存储空间也不能被释放，这就要影响到模拟器的效率。所以在时序电路测试产生中一般不单独使用该方法。演绎故障模拟方法可以从电路的正常状态演绎出电路中每条引线上的可测故障。演绎故障模拟方法使用了故障表的概念，但由于演绎故障模拟的故障表是建立在引线上，当电路规模很大时，所需存储量十分巨大，而且集合运算对较大故障表的运算也是十分复杂的。所以单独采用演绎故障模拟策略对时序电路进行模拟，其效率也是不高的。
　　同时故障模拟方法与演绎故障模拟有很多相似之处，它也采用了故障表的概念，但它的故障表是建立在门上的。同时故障模拟在完成真值模拟的同时也完成故障模拟。在同时故障模拟中，由于可以对故障表中的每个故障分别处理，因此还可以通过查表的方法来进一步加快计算速度，这在演绎故障模拟中是不可能实现的，所以它较适合时序电路的故障模拟。但其故障表占用内存较大和故障效应通过扇出重汇聚而造成的判定时间过多影响了其计算速度。本文针对其不足之处做了较为深入的研究，提出了一些改进的策略。
1　故障表压缩策略
　　同时故障模拟所消耗的时间可以分为两部分。一是真值模拟，其次是故障模拟。在故障模拟部分又可细分为对无扇出区域的计算和扇出重汇聚区域的计算。真值计算和无扇出区域计算的复杂性基本上是线性的，但由于扇出重汇聚中的各传播路径奇偶性不一致，使通过该区域的故障效应在汇聚点上的可观性往往是不定的，需要进行判定，这是比较耗时的。其次由于同时模拟方法对每个功能块都建立一个故障表，故障表所占用的空间越大，对故障表的处理也越长。
　　
(a) 门级的电路拓扑结构图　　　　　(b) 新功能块所构成的电路
图1 电路无扇出重构示意
　　通过上述分析，我们首先设想如果电路中的功能块越少，故障表所占用的空间越小，对故障表的计算时间越快。其次如果电路中的扇出重汇聚区域越少，判定扇出源的可观性时间就越少。因此我们提出了电路重构的解决策略。
　　电路重构的原则包括以下几个方面。1)尽量将扇出重汇聚区域划分到一个功能块中；2)为了便于故障模拟计算，新功能块的输入个数不宜过多，以利于模拟过程中的查表计算；3)触发器只能单独做功能块使用。
　　图1为一未重构的电路，在图1(a)中扇出重汇聚的区域有B和C两部分(在图1(a)用虚线圈)。所构造的新电路应由A,B,C3个新功能块组成。新电路的拓扑结构如图1(b)所示，其中A,B,C3个功能块分别对应于图1(a)中的虚线包围3块。
　　
(a) 重组后功能块内部结构　　　　(b) 功能块内部故障表链表结构
图2 功能块内部故障表示意
　　按照上述法则对ISCAS89电路进行重构后的结果表明，重构后的电路所含功能块数目大大减少，只有重构前电路功能块总数的20%-30%[2]。利用新的电路进行故障模拟 , 可以减少同时故障模拟对内存的过多需求。
2　故障模拟策略
　　对重构后的电路，在故障模拟过程中，采取对功能块节点外部引线和功能块内部引线分别处理的两级模拟策略。即对外部电路采用同时故障模拟的策略，对功能块内部采用单路径模拟策略。功能块外部电路的故障表同文献[1]。但故障表中信息按照电路引线编号顺序排列，便于故障信息的查询和故障快速丢弃，同时可以对故障表使用归并计算技术，使表的计算速度进一步提高。
　　对功能块内部的电路故障采用单路径回退策略。如果功能块内部是一扇出重汇聚电路，则只回退到扇出分支，而不对扇出源进行可观性判定。对扇出源的可观性判定留到外部模拟进行处理。对功能块内部故障处理过程中不是对每一个门都建立一故障表，而只在功能块输出端建立一故障表。该表在真值模拟过程中以链表的形式建立。这个过程如图2所示。图2(a) 为一功能块内部结构。当X7X8X9X10={0111}时，其故障表的链表结构形式如图2(b)所示。如果输出端X14=0在初级输出可测，则查功能块输出X14为1的链表即可得出{14/1,12/1,13/1,7/1,9/0,10/0}故障可测。其中i/v表示i引线固定为v类型故障可测，其中v∈{0,1}。这样做与传统的同时故障模拟的故障表相比有如下的优点。传统同时模拟过程中，图2(a)所示电路共有3个故障表。在相同的输入值下故障表如下所示：
　　fg1={[7/1];11;1,8/0;00; 0,[12/1];01;1}
　　fg2={[9/0];01;1,[10/0];10;1,[13/1];11;1}
　　fg3={[7/1];01;1,[12/1];01;1,[9/0];10;1,[10/0];10;1,[13/1];10;1,[14/1];00;1}
　　从上述表中可以看出fg3含有fg2和fg1的很多信息，如果功能块中门的个数较多的话，这种重复的信息在故障表占有的空间还是很大的，因此链表的使用可以有效地节省故障表所占用的空间。在上述表达式中符号[a/b]表示a引线上的s_a_b故障(b∈{0,1})可以在功能块输出端观察到。
3　实验结果
　　上述思想用C语言在Sun4工作站上进行了实现。表1为针对文献[3]的测试产生系统所产生测试码的实验结果。从实验结果可以看出，由于电路重构和两级模拟策略的采用使同时模拟的空间占用太大以至不足以改善，同时由于故障表的压缩，模拟速度也得到了提高，基本上可以满足对大电路测试产生系统所得到测试码进行故障模拟的要求。
表1 针对ISCAS89电路的实验结果
电路名称矢量长度故障覆盖率模拟时间
S27161000.013
S20810162.313.9
S29811685.0621.2
S3449795.629.15
S3499795.1429.16
S38611974.8713.51
S42010740.943.6
S52627974.5972.4
S64116786.5054.7
S71313681.958.3
S82013464.9449
S83215763.3357.9
S953708.3410.7
4　结   论
　　影响同时故障模拟方法效率的原因主要有两个：一是对电路中扇出重汇聚点的过多判定；二是故障表占用计算机内存空间大，对进行处理的时间也因此增加。针对同时故障模拟这两个方面的不足之处，本文提出了基于电路结构重组和两级故障模拟的策略以提高故障模拟的效率。针对ISCAS89电路的实验结果也表明了其有效性。
基金项目：国家自然科学基金（69773006）
作者简介：王仲（1965～），男，讲师，主研大规模集成电路测试
作者单位：装甲兵工程学院电子工程系，北京100072）
参考文献
1 Ulrich E G,Baker T.The Concurrent Simulation of Nearly Identical Digital Network、Proc.10th Design Automation Workshop,1973,6
2 陈思成.同步时序电路故障模拟系统的设计与实现[硕士学位论文].北京：中国科学院计算技术研究所 ,1998
3 王仲.一种基于模拟的时序电路测试产生方法.98大连-香港国际计算机会议论文集,1998-10
收稿日期：1999-01-04
