《Test_Set_Compaction_Algorithms_for_Combinational_Circuits》中文翻译.doc

计算机辅助设计国际会议记录，1998年11月组合电路的测试集压缩算法Ilker Hamzaoglu 和Janak H.Patel乌尔班纳市伊利诺伊州大学可靠和高性能计算中心摘要：文章提出两种新算法，冗余矢量消除算法（RVE）和基本故障减少算法（EFR），为组合电路在故障模型单卡下产生压缩测试集，在故障测试集下启发式估算最小单固定故障。结合动态压缩算法，这些算法被合并成组合电路的ATPG系统，称为MinTest。MinTest找到更低跳变数，相比先前为ISCAS85公布的记过，其能产生更小的测试集，同时能完整扫描ISCAS89基准电路。1 介绍压缩测试集对降低超大规模集成电路的测试成本非常重要，通过降低测试应用时间可实现。这对基于扫描链电路尤为重要，因为这些电路的测试时间与测试集大小的产生和扫描链中存储设备数量有直接关系。少的测试集也降低测试存储设备的需求。因为在故障测试集中为给定的不可缩短的组合电路估算最小单固定故障已经被证明是NP完全问题，所以在文献中提出了一些基于不同试探法的测试集压缩算法，例如，静态压缩算法6,动态压缩算法6，基于测试产生的独立和兼容故障集1,9,12,14，倒序故障仿真13，最大压缩12，旋转回溯12，双重检测8,9，二选一9，三选二9，强迫对合并4，基本故障修剪4。虽然这些算法能成功产生小测试集，但是作为结果的测试集仍然比已知的低跳变数要大。这是因为如下两个原因：以前公开发表的测试压缩集算法不能更进一层和测试集结合，已知低跳变数不是严格的。为了进一步结束这个缺口，本文解决这两个问题。我们提出两个新的测试集压缩算法，冗余矢量消除算法和基本故障减少算法，以及在故障测试集中一个新的估算最小单固定故障启发法。这些算法和动态压缩算法为组合电路包含到先进的ATPG系统中，称为MinTest. MinTest找到更低跳变数，相比先前为ISCAS85公布的记过，其能产生更小的测试集，同时能完整扫描ISCAS89基准电路2,3.文章余下部分的结构如下。第二部分叙述文章中将要用到的定义。第三部分叙述冗余矢量消除算法。基本故障消除减少算法在第四部分出现。最小测试集估算启发法在第五部分描述。第六部分给出实验结果。最后第七部分进行总结。2 预备知识 在这部分中，我们将介绍文章将会使用的定义。如果一个测试矢量能发现至少一个在这个测试集中其他矢量不能发现的故障，那么在这个给定测试集中，该测试矢量称为基本矢量。如果一个故障只能被给定测试集中的这个测试矢量发现，那么这个故障被定义为测试矢量的基本故障4,9.换句话说，一个基本矢量至少发现一个基本故障。如果测试矢量不能发现任何基本故障，那么在给定测试集中该测试矢量被认为是冗余的，也就是说，被它发现的所有的故障也被这个测试集中其他测试矢量发现9. 如果测试集中测试矢量，测试矢量被新测试矢量替代，能发现测试矢量的基本故障，同时故障只能被和发现，那么测试矢量的基本故障据说会被删除4。 如果两个故障能被一个单一测试向量检测出来，那么称它们是兼容的。类似地，如果两个故障不能被一个单一测试向量检测出来，那么称它们是不相容的。给定故障集的不相容图表，定义为,其中1,4,9,14.如果在一个集合中所有的故障都是成对的不相容，那么这个故障集就称为独立故障集1.对于一个给定的组合电路，最大尺寸的独立故障集称为最大独立故障集。因为寻找最大独立故障集是NP完全问题10,因此在实践中经常使用的是最全面的独立故障集。 在故障模型的单一故障下，给定组合电路的最小测试集大小是指在这个电路中，检测故障中所有可检测的单一故障的最少的测试向量的数量。3 冗余矢量消除 在动态测试模式产生的过程中，被早期测试向量检测到的一些故障也能偶然地被后来产生的测试向量检测到。因此，随着在ATPG算法中产生更多的向量，早期产生的测试向量有可能变成冗余向量。冗余矢量消除算法（RVE）在测试向量产生的过程中识别冗余矢量同时将他们从测试集中动态删除。如图1所示，RVE模拟故障列表中所有故障，除了那些被证明不具有可测性的故障，算法同时记录被每个矢量检测到的故障，基本故障数，和故障检测时间。例如，在测试矢量产生过程中，如果一个测试矢量的基本故障数减少到0，那么这个测试矢量就成为冗余矢量并且将被从测试集中删除。 下面举例说明，RVE算法比翻转顺序故障模拟（ROFS）算法更能降低测试集大小13.这是因为如果被检测的一些故障只能被早期产生的测试矢量检测，那么ROFS算法不能识别冗余测试矢量。如果被检测的所有故障也能被早期产生的测试矢量检测，那么ROFS算法才能识别出冗余矢量。 举例：考虑故障集。假设针对这个故障集，ATPG系统产生给定序列的测试集，其中检测故障，检测故障，检测故障。在这个例子中，在产生以后，RVE算法检测到是冗余的同时将其从测试集中删除。因此算法将测试集减少到。然后ROFS不能减小这个测试集的大小。 RVE算法性能和文献8,9所介绍的双检测（DD）算法相似，即使因为删除冗余矢量的顺序不同导致产生的结果稍有不同。然而，我们不提议将RVE作为一个独立测试集压缩算法，宁愿将其当作包括RVE和基本故障减少算法（EFR）这两步压缩框架种的第一步。除了通过DD也能获得每个测试矢量的基本故障数以外，EFR需要由RVE产生的额外的信息；由每个测试矢量检测的故障和由当前测试集检测每个故障所用的精确时间数。如果用DD代替RVE，那么EFR本身将获得这个信息。因为RVE花费了大多数的执行时间去产生这些信息，RVE和EFR算法合并一起的执行时间比DD和EFR算法合并一起的执行时间要短。冗余矢量消除算法伪代码（t:测试矢量）每个故障的故障模拟测试矢量没有被证明是冗余的因为测试矢量t检测每个故障检测计数+;If(检测计数=1)基本故障数t+;Else if (检测计数=2)识别测试矢量基本故障数-;If (基本故障数=0)将从测试集中删除由检测的每个故障检测计数-;If (检测计数=1)识别测试矢量基本故障数+4 基本故障减少 因为修剪测试矢量的基本故障会减少它的基本故障数目，如果测试矢量的所有基本故障都被修剪，那该矢量就成为冗余矢量，同时它会被从测试集中删除。如图2所示，在最初的测试集产生后，基本故障减少算法（EFR）通过尽可能多地修剪每个测试矢量的基本故障，反复使用去进一步压缩测试集。EFR使用多重目标测试产生程序（MTTG）4,9来产生能检测给定故障集的测试矢量。EFR算法改进了一个代替两个算法（TBO）9和基本故障修剪算法（EFP）4. 在给定的初始测试集中，TBO通过用一个新的测试矢量来代替两个测试矢量的方法尝试减少测试集大小。通过找出一个能检测出两个测试矢量都能检测出的基本故障的测试矢量，同时这些故障智能被这两个测试矢量检测出来，这样可以实现TBO目标。然而，即使不可能寻找这样的一个测试矢量，仍然有可能从测试集中消除这样的两个测试矢量。这可能借助两个代替三个算法(TBT)实现，TBT算法用两个新的测试矢量代替原来的三个测试矢量。总体来说，算法可以延展带一个N-by-M(M2，导致N-by-M算法计算太大难以实现。 另一方面，EFR降低测试集大小的方法是通过修剪每个测试矢量的基本故障。如果一个测试矢量的所有基本故障都被修剪，那么这个测试矢量是冗余的，可以将其从测试集中删除。TBO可以看成是EFP的特例，TBO中测试矢量仅用一个测试矢量替代允许修剪的基本故障。通过缓和这种限制同时允许测试矢量用测试集中不止一个的测试矢量代替修剪其基本故障，EFP比TBO达到更好的性能。在最坏情况下，EFP将试着为故障集产生一个测试矢量，其中E是基本故障数，V是原始测试集中测试矢量数。由于大多情况下E是远大于V的，因此EFP比TBO计算复杂性更高。然而，在N-by-M算法的大多数情况下N2时计算复杂性更高。 压缩给定测试集问题可看作把这个测试集的基本故障分类到给定冗余矢量数最大的测试矢量。因此，应该被开发的探索空间就是为给定测试矢量所有可能的基本故障分类。由于TBO算法和EFP算法都没有这个探索空间的全局观，通过修剪测试矢量的基本故障，两种算法只集中每次从测试集中移动一个测试矢量完成局部的贪婪搜索。只要这让一个测试矢量成为冗余矢量，他们就会修剪这个测试矢量的基本故障，否则，他们就不会修剪基本故障。因为这个限制，使它们只能探索这个搜索空间的一部分。 另一方面，EFR算法有搜索空间的全局观。它克服了TBO算法和EFP算法的限制，通过试着把基本故障分配到给定冗余测试矢量数最大的测试集中，完成非贪婪全局搜索。因此，即使一个矢量没有成为冗余矢量，通过尽可能多地修剪其基本故障，EFR会尽可能多地减少它的基本故障数。即使一个测试矢量的其中一个基本故障修剪失败，算法也会试着修剪该矢量的其他基本故障。这样，EFR就探索出比TBO和EFP都要大的搜索空间。下面通过例子说明使用这个新搜索技术EFR能产生比TBO算法、TBT算法和EFP算法任何一个产生的测试集都要小的测试集。举例：考虑测试集。假设检测故障，检测故障，检测故障，检测故障，在图3中给出了不相容图标的邻近列表。EFR通过第一次迭代可降低这个测试集的大小。正如图3说明的那样，可检测，用代替测试矢量，可检测，用于代替，可检测，用代替。经过这些替代后变成冗余矢量，因此它可以从测试集中删除。TBO算法、TBT算法和EFP算法没有一个可以减小这个原始测试集的大小。 正如下面举例说明一样，通过新搜索技术方法，反复地使用EFR能进一步压缩给定测试集。这是TBO算法和TBT算法无法完成的。虽然反复地使用EFR可以进一步压缩给定测试集，但是这是不太可能的。如果新测试矢量其中一个“偶然地”检测出其他测试矢量不打算检测的一个或更多基本故障，那么这才会发生。这使它在第二次迭代时可能去修剪一个测试矢量的基本故障，虽然这在第一次迭代中不可能不修剪。 举例：考虑测试集。假设检测故障，检测故障，检测故障，检测故障，检测故障，图4给出代表不相容图标的邻近列表。正如图4举例说明那样，在EFR算法的第一次迭代中，代替将修剪掉，代替将修剪掉。因此，EFR算法的第一次迭代不能减小测试集大小。然而，因为在第一次迭代后，不再是的基本故障，也不再是的基本故障，在第二次迭代中，代替将修剪掉，代替将修剪掉。这样将变成冗余矢量就会从测试集中删除。另一方面，TBO算法、TBT算法和EFP算法没有一个可以减小这个原始测试集的大小。 EFR算法和EFP算法有相同的最坏情况下计算复杂性，例如，EFR算法将试着为故障集产生一个测试矢量，其中E是基本故障数，V是原始测试集中测试矢量数。如果算法被反复迭代，那么最坏情况下的计算复杂性将达到，其中I是迭代次数。 TBO算法和EFP算法中不相容图表用来降低平均事件执行次数4,9.然而，在文献1,4,9,14定义使用的不相容图表不能代表接下来的故障中单一故障的不相容关系。一个故障成对地与给定故障集所有故障相容，虽然这是可能的，但是当它们一起作为目标时它可能与这些故障不相容。因此，通过允许图表结点代替故障集，我们扩展不相容图表的定义。在压缩过程中以需求驱动方式构建这个新不相容图表。通过观察得出使用这种不相容图表能降低EFR算法的执行时间。基本故障减少(T:测试集，执行次数：int,MFL:int，MEFL:int)执行次数T中每一个测试矢量有少于MEFL的基本故障all-ef-pruned=trun;failure-limit=0; 的每个基本故障pruned=false;pruned=Multiple-Target-Test-Generation;if(pruned=true) break;If(pruned=ture)用新测试矢量代替更新T；故障模拟新测试矢量；Elsefailure-limit+;aii-ef-pruned=false;if(failure-limit=MFL)break;If(all-ef-pruned=true)将从T中删除；5 最小测试集大小估计 为了评估测试集压缩算法在组合电路中的有效性，有必要了解这种电路的最小测试集大小（MTSS）。此外，如果了解了MTSS，那么不论什么时候达到最小测试集而不是迭代预定的时间值就停止EFR算法执行可降低测试集压缩时间，由于在为给定不可缩短组合电路的故障测试集中计算最小单一故障数被证明是NP完全问题10,MTSS使用启发式技术去找更低范围。 寻找更低范围的最普遍使用启发式方法中的一种是寻找最大独立故障集。最大独立故障集大小少于或等于最小测试集大小。在故障集给定的单一故障的不相容图表中寻找最大圈来计算得到最大独立故障集1,4,8,9,11,14. 由于在给定图表中找到最大圈问题被证明是NP完全问题5,一些启发法被提出为了在给定图表中找到最大圈。由于在给定测试中测试矢量的基本故障高度不相容，文献4提出计算最大圈的方法是首先只考虑基本故障，然后再考虑其他故障来扩大这个圈。文献9提出对于一些电路来说，在只考虑使用基本故障的不相容图表中计算最大圈比在考虑全部故障的不相容图表中计算最大圈要更大。基于下面的定理和推论，首先只考虑基本故障计算最大圈，然后再考虑给定故障列表中其他故障来扩展这个圈。定理1：组合电路中，在大小为N的故障集TS给定完整单一故障，如果这个电路存在大小为K的最大独立故障集MIFS，那么MIFS包含来自不同测试矢量至少2K-N个基本故障。证明：如果存在大小为K的最大独立故障集MIFS，那么定义MIFS中存在K个对不相容故障。由于MIFS中的故障是成对不相容的，那么没有测试矢量能检测到MIFS中多于一个故障。因此，MIFS中每个故障应该被TS中不同测试矢量检测。由于测试集是完整的，那么至少TS中K个测试矢量检测K个故障。如果这些K个故障没有一个被TS中剩下的（N-K）个测试矢量检测到，那么它们中的每一个都是TS中不同测试矢量的基本故障。最坏情况下，剩下的（N-K）个测试矢量中的每一个检测到MIFS中不同的故障。因为这些(N-K)个故障被两个测试矢量检测，所以它们不是基本故障。因此，最坏情况下，MIFS中K-(N-K)=2K-N个故障是TS不同测试矢量的基本故障。换句话说，MIFS包含来自不同测试矢量至少2K-N个基本故障。推论：组合电路中，在大小为N的故障集TS给定完整单一故障，如果该电路存在大小为N最大独立故障集MIFS，那么MIFS包含来自TS中每个测试矢量的一个基本故障。证明：根据定理1，在TS至少2k-N个测试矢量中MIFS应该包含一个基本故障，其中K是最大独立故障集的大小。因为K=N，所以表达式2K-N=N.又因为TS有N个测试矢量，这就意味着MIFS应该包含TS中每个测试矢量的基本故障。 定理1表示在一个小测试集不相容图表中的最大圈很可能包含许多基本故障，而推论则说明如果在不相容图表中存在最小测试集，那么这个圈中只包含基本故障。由于EFR算法基于这个理论产生测试集，可能是最小的，也可能非常接近最小，通过搜索包含来着由EFR算法产生的测试集中尽可能多的测试向量的基本故障的最大圈，我们为MTSS计算降低的范围，然后通过考虑给定故障列表中的其他故障使这个圈扩大。从尽可能多的测试矢量中选择基本故障来计算最大圈，这个搜索空间是非常大的，计算代价太高不能用尽一切方法去搜索。若测试集中有n个测试矢量，他们基本故障集的大小分别是，则搜索空间的大小是。因此，我们提出下面新的启发法导出分枝，限制搜索算法。当试着从每个测试矢量中选择一个基本故障时，考虑他们所拥有基本故障数递增顺序的测试矢量，同时为原始测试矢量探测更多分枝。 这种启发法增加了在短时间内计算最大圈的可能性，原因如下。一旦一个基本故障被包含到圈中，将减少能被包含到圈中余下测试矢量的基本故障数。若测试矢量有大小的基本故障，同时假设这些基本故障中的每一个都有相同的可能性成为最大圈，那么当试着选择这个测试矢量的基本故障时，选择这个在最大圈的基本故障的可能性为。若能被加入最大圈的的基本故障数减少，那么选择在最大圈的基本故障的可能性就增加。因为对于有较少基本故障数的测试矢量来说，选择在最大圈的基本故障的可能性已经很高了，而在选择这些基本故障以后，对于有较多基本故障数的测试矢量来说，选择在最大圈的基本故障的可能性增加，所以在短时间内考虑有较少基本故障数的测试矢量首先增加计算最大圈的总体可能性。6 实验结果 最小测试集大小的估值，上文提出来的RVE算法和EFR算法以及文献6提出的动态压缩算法，我们将这些合并到组合电路7中先进的ATPG系统中去，称为MinTest. MinTest以面向对象的方式设计由C+实现。在ISCAS85基准电路和全扫描版ISCAS89基准电路2,3测试MinTest.在200M赫兹，128MBRAM运行Linux2.0.0 使用GNU CC2.8.0版本的奔腾个人电脑上获得MinTest性能结果。 在最小测试集估计方面，将MinTes的结果和先前公布的结果相比较，在表1中显示性能比较结果。表中符号-表示这个电路中未公布的最低范围。结果显示我们算法计算出比以前公布的范围更低的范围。在40个电路中超过38个电路，算法计算得到的较低范围比公布的最好的最低范围要更大或相等。在这38个电路中的14个电路，相比以前公布的结果，算法计算较低范围差不多要大33%。例如，c7552超过25%，s1423超过33%，s9234超过11%。表中*显示的是这14个新较低范围结果。 最小测试集大小估算算法适用于大型电路，其执行时间和文献8,9提出的算法执行时间相似。文献11提出的算法智能适用于小型电路，对于这些电路，我们的算法可计算出同样的较低范围。文献4提出的算法是一个计算代价高的算法，其在ISCAS85基准电路的执行时间和ISCAS89基准电路的性能均未公布。 在测试集压缩方面MinTest的性能和文献CT8,9,12和文献TSC4发表的两个最好测试集压缩算法性能相比较。比较结果在表2中显示。表中，每个电路的最小已知测试大小用*标注出来。每个电路最小测试集中最大已知低范围在LB栏中显示出来。这些较低范围中的一些是用最小测试集估计算法计算的得到，剩下的是来自文献9.在所有的实验中，MinTest使用6个限制反馈。MinTest的执行时间包括故障模拟和原始测试集产生，所有有MinTest产生的测试集故障覆盖率为100%.CT和TSC的结果分别来自文献9和4。TSC没有ISCAS89基准电路上的实验结果。 从实验