基于最小集合覆盖求解方法的测试向量集约简

欧阳丹彤，郭江姗，张立明†

（1.吉林大学计算机科学与技术学院，吉林长春 130012；2.符号计算与知识工程教育部重点实验室（吉林大学），吉林长春 130012）

随着集成电路设计（Integrated Circuit，IC）及工艺技术的发展，人们对设计精度的要求不断提高，IC设计复杂度近乎呈指数增长，芯片故障的测试愈发困难[1].在数字电路测试中，自动测试向量生成（Automatic Test Pattern Generation，ATPG）是对被测电路生成测试向量的过程.首先向被测电路中插入故障列表，将ATPG 产生的测试向量作为数字电路的输入序列，根据实际输出信号与无故障电路预期值的差异，区分正常的电路行为和由故障引起的故障电路行为，以此来检测相应的故障[2].由ATPG 产生的高质量的测试向量集将进一步被应用到全扫描IC设计或规整的部分扫描设计.因此，ATPG 作为IC 设计流程的重要组成部分之一[3]，工业界和学术界许多学者对其进行了研究.

工业上，ATPG 方法逐渐被集成在电子设计自动化（Electronic Design Automation，EDA）工具中以实现工业IC 的设计，其中较为著名的ATPG 工具有Synopsys 研发的Tetra MAX ATPG 和Cadence 研发的Encounter®Test 等.其中Tetra MAX ATPG 以其简洁的图形用户界面和强大的命令行被广泛应用，本文中将其简称为TMAX.TMAX 支持多种设计风格和测试方法，可以在较短的时间内生成具有高故障覆盖率的测试向量集，以满足后续IC 设计要求.

在学术界，国内外许多研究人员都对ATPG 方法进行了研究和改进.1966 年Roth 提出了第一个关于非冗余组合逻辑电路的ATPG 方法D 方法[4]，D 方法基于多维敏化思路，对可测故障生成测试向量，理论上解决了非冗余组合电路的测试问题，但不能对冗余电路和有重聚扇出电路进行测试向量生成.Geol 提出了D 方法的改进方法PODEM 方法[5]，主旨是对激活的故障回溯其原始输入，搜索所有可能的原始输入值，只要选取一个满足要求的原始输入即可作为测试向量，循环搜索，直到完成所有故障回溯.PODEM 方法减少了D 方法中回溯与判决的测试，有效提高了计算效率，但仍存在回溯的问题.1983 年，Fujiwara 等提出了PODEM 的改进方法FAN 方法[6]，引入了唯一蕴涵、唯一敏化、多路回退和头线等概念，采用头线和扇出的回溯方式，有效降低了回溯次数和执行时间，并在扇出点方面做了改进.此后，许多学者相继地提出了ATPG 的改进方法，如Schulz等人提出的基于FAN 算法的改进算法SOCRATES方法[7]，Bryant 提出的简化排序二元决策图ROBDD方法[8]，Larrabee 和Stephan 等人提出的基于SAT 的ATPG 方法[9-10]，等等.

随着ATPG 方法的发展，由ATPG 生成的测试向量集也被应用于更多的研究测试中，但由于生成的测试向量集规模庞大，其中可能包含大量的冗余测试向量，对测试电路成本有较大影响[11-12].因此，对测试向量集进行优化，剔除冗余测试向量，对降低测试成本和测试时间是十分必要的.故障测试向量集的优化常见有动态优化[13]和静态优化[14].动态优化是在测试向量集生成过程中，通过将ATPG 方法与测试集压缩方法同时进行，在生成测试向量的同时压缩测试向量集，完成测试向量集优化；静态优化则是在ATPG 得到测试向量集后，在保证故障覆盖率不变的基础上缩减测试集规模.

静态测试集优化问题已被证明NP 完全问题[15]，王小港[16]提出基于遗传算法的测试集约简方法，该方法将测试向量作为染色体，通过编码方式和评估函数的设计，实现测试集约简并取得较好的效果，但由于遗传算法参数设置较多，如种群大小、变异概率、交叉概率等的变化，使得优化效果可能不同；康波等学者[17]提出了基于混沌遗传算法的测试集约简方法，利用混沌序列的随机性、遍历性及规律性等特点来控制遗传算法中的交叉与变异操作，并通过实验验证该方法明显优于标准遗传算法，但是由于混沌序列的随机性，该算法运行时间变动较大；乔家庆等学者[18]采用遗传算法对测试向量排列顺序进行优化，同时采用行列消去法作为适应度评估方法，能有效减少测试向量的数目且优于传统遗传算法，但遗传算法收敛速度慢，容易产生局部最优的情况；侯艳丽等学者[19]将粒子群算法应用于测试集约简，通过构造粒子的表达方式和编码规则，建立粒子群速度-位置模型，利用混沌优化算法来初始化粒子群，使得初始个体本身为一个完备测试集，具有较好的约简效果，但是使用的参数往往依据经验设置，不便于操作；姜伟等学者[20]提出的基于粒子群的多目标测试集优化方法（DPSO），以最大故障检测率、最少测试数目和最小测试代价为优化目标，对测试集进行约简，取得了较好的约简效果，在实际应用中具备一定的局限性.因此，本文提出基于最小集合覆盖求解方法的完备测试向量集求解方法（Complete Test Pattern Set Solution，CTPSS），该方法将故障集与测试向量集中每个测试向量建立对应关系，通过重新建模，将测试集约简问题转化为最小集合覆盖问题求解，将复杂的实际问题通过简单的模型加以解决.

最小集合覆盖问题作为经典NP 完全问题，已被应用于各个领域[21]，相较精确求解方法，启发式求解方法更适用于大规模问题的求解.在文献[22]中提出一种行加权局部搜索方法（Row Weighting Local Search，RWLS），该方法提出预处理步骤，在局部搜索前有效减少搜索空间，且采用多个禁忌策略有效避免搜索的重复和循环，实验证明该方法针对大规模问题仍可在有限时间内获得更佳解.因此，本文提出的CTPSS 方法结合RWLS 方法实现测试向量集约简，其优点为：1）模型适配，最小集合覆盖问题可以有效求解测试向量集约简问题，且不会降低测试向量集的覆盖率；2）模型简洁，参数设置仅需终止条件，即最大的迭代次数；3）预处理阶段可有效缩减部分数据规模，提高计算效率.

1 预备知识

本节将给出集合覆盖的相关概念，并示例说明.

定义1 最小集合覆盖[21].给定非空元素集合R和一个R 上的子集族S，最小集合覆盖问题（the Minimum Set Covering Problem，MSCP） 是求解一个S 的一个子集族C⊆S，满足C 可以覆盖R 中所有元素且C 的规模最小.一个最小集合覆盖实例表示为MSCP（R，S），其中称R 为元素集合，S 为初始子集族.

下面通过给出的实例对上述概念进行说明.

例1 对于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规模最小，故MSCP（R，S）的解C=Sa={{a，e}，{b，c，d}}.

根据整数规划的定义形式，一个集合覆盖实例可以用0-1 矩阵表示.RWLS 方法即在MSCP（R，S）的0-1 矩阵基础上，通过行加权的方式，获取最小集合覆盖最优解，下节将给出具体介绍.

2 RWLS 方法

本节将给出RWLS 方法的伪代码描述及其分值计算方式相关定义.

2.1 RWLS 方法

本小节将给出RWLS 方法具体介绍，其伪代码如算法1 所示，可分为三个部分：前期准备、预处理和局部搜索求解.

在前期准备阶段，完成MSCP（R，S）问题读入，并设置算法停止条件，以获取限定条件内的最优解，此为RWLS 方法的唯一参数.

预处理阶段作为RWLS 方法的一个重要部分，其目的是保证禁忌策略的有效性.在此阶段，对R 中每一个元素，检查能够覆盖该元素的集合的个数，若其值为1，即代表该集合一定会被放入候选解集中，则可以将该集合及此集合可覆盖的所有元素从原问题中移除.

局部搜索求解阶段作为RWLS 方法的关键部分，它实现了一个扰动搜索的框架，假设初始候选解集C 的大小为k，若存在更优的解，则其规模一定小于k.故首先破坏C 的可行性，后通过Add 和Remove操作[22]不断扰动C 并试图使C 重新变成可行，以获取更优解.同时，RWLS 方法采用了多个禁忌策略[23]避免搜索的重复和循环，包括有禁忌列表tabu_list，时间戳timestamp 以及布尔状态检查canAddToSolution，并采用一个权重增长策略以帮助算法跳出局部最优.其算法流程图如图1 所示，其中，L 为R 中未被候选解集C 覆盖的元素的集合.

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

由此可知，每个集合的分值为LocalSearch 方法集合选取的一个重要因素，下小节将给出RWLS 方法的分值计算方法.

2.2 RWLS 方法分值计算

本小节将给出RWLS 方法的分值的计算方式.

定义2 分值score（Sj）.若weight（xi）表示元素xi的权重，则对于集合族S 中任意元素Sj，score（Sj）的值为：

其中，σ（C，xi）=，Xi为集合族S 中所有可以覆盖元素xi的集合构成的子集族，即σ（C，xi）表示当前候选解集C 中能够覆盖元素xi的集合的个数.RWLS 方法仅考虑σ（C，xi）=0 和σ（C，xi）=1 两种情况：当集合Sj∉C 时，score（Sj）为当前所有能被集合Sj覆盖且未被C 覆盖的元素xi的权重之和；当集合Sj∈C 时，score（Sj）为一个负数，即当前所有能且仅能被集合Sj覆盖的元素xi的权重之和的相反数.由此可以看出，当从C 中添加或删除一个集合Sj时，与其具有相同可覆盖元素的集合的分值均有可能发生变化，需重新计算.

3 CTPSS 方法

本节将给出测试集约简问题的建模过程，并给出CTPSS 方法的相关定义以及其伪代码描述.

3.1 问题建模

本小节将给出测试集约简建模的相关概念及定义，并给出建模过程.

定义3 故障列表.由电路中所有可能发生的故障组成，记为F={ f0，f1，…，fm}，其中m 为F 中元素的个数.

定义4 故障族FS.若对于测试向量集T={t0，t1，t2，…，tn}中任意一测试向量tj（0≤j≤n），Fj={fa，fb，fc，…}为tj能够覆盖的故障列表F 的故障子集，其中0≤a，b，c≤m，则称{F0，F1，F2，…，Fn}为这个测试向量集T 对应的故障族，记作FS.

定义5 候选测试向量集TC.称TC={ta，tb，tc，…}，其中0≤a，b，c≤n 为故障列表F 的一个候选测试向量集，当且仅当TC⊆T 且

候选测试向量集也可称为完备测试向量集，称候选测试向量集TC是最小完备测试集，当且仅当TC的任意一个真子集都不是候选测试向量集.

定义6 故障-测试矩阵FT.对于故障列表F={f0，f1，…，fm}和测试向量集T={t0，t1，t2，…，tn}，故障-测试矩阵可以记作：

其中，对于矩阵中任意元素ftij（0≤i≤m，0≤j≤n），ftij=1 表示测试向量tj可以观测到故障fi，反之，若测试向量tj不能观测到故障fi，则ftij=0.

测试向量集约简可以描述为，从测试向量T={t0，t1，t2，…，tn}中选取子集TC⊆T，使之能够覆盖故障列表F={ f0，f1，K，fm}中所有元素.根据上述相关定义，测试向量集约简问题可进一步描述为，从测试向量集T 对应的故障族FS={ F0，F1，F2，…，Fn}中选取一个集合族FC={ Fa，Fb，Fc，…}，0≤a，b，c≤n，使之能够覆盖故障列表F={f0，f1，…，fm}中所有元素.根据上述描述，测试向量集约简可以被转化为可由RWLS 方法求解的最小集合覆盖实例MSCP（F，FS），其中，故障-测试矩阵FT 等同于集合覆盖实例所转化0-1 矩阵.此外，本文给出必然测试向量定义如下.

定义7 必然测试向量.若存在故障fk∈F，能且仅能被一个测试向量tj∈T 覆盖，则称测试向量tj为必然测试向量.

在预处理阶段，必然测试向量tj及其可覆盖的故障集Fj将暂时从原问题中移除，从而缩小局部搜索求解方法的矩阵规模，提高运行效率.下小节将给出CTPSS 方法的具体过程.

3.2 CTPSS 算法描述

本小节给出了CTPSS 算法的伪代码，并给予相关说明.

古建筑是传统“虽由人造，宛如天开”理念的集中体现，加强仿古建筑结构施工技术的研究，能够有效避免建设中对人力、物力、材料资源的浪费和损耗，并且有利于中国优秀的传统文化弘扬，让人民群众在闲适、自然、轻松环境中，体验“天人合一”“道法自然”的人文精神。

第2～8 行获取TMAX 生成的测试向量及其对应故障列表：readNetlist（）用于读取电路文件，若当前电路为时序逻辑电路，则需要进一步读入与其相关的时钟信息文件；初始化故障族FS，候选解集C 和最优解bestSol；通过运行TMAX 得到初始测试向量集T 以及故障列表F；第5～8 行为获取集合簇FS，通过pat_get（）函数将测试向量集T 分割为多个独立可执行测试向量tj，使之可以被TMAX 识别，从而得到tj可覆盖的故障集合Fj，最终获得故障族FS.

第9～17 行调用RWLS 方法：读入最小集合覆盖实例MSCP（F，FS）；设置终止条件，本文中将其设定为一个预期最大迭代次数，同时若当前候选解集规模小于等于必然测试向量数目加1，则算法可提前终止，当前候选解集即为最优解；在预处理阶段添加函数check（）来检测每个故障的被覆盖次数，若故障的被覆盖次数为1，则存在必然测试向量fi，通过函数GetMust（）获取tj并予以标记后加入到候选解集C 中，将其可覆盖故障集合Fj中所有元素从未覆盖列表L 中移除，以保证后续禁忌策略成功进行；局部搜索求解阶段，以预处理得到的部分候选解集C 为输入，贪婪算法初始化得到完整的初始候选解集C，最后调用LocalSearch（）方法得到最优解.

第18～19 行为验证过程，使用change（）函数获取bestSol 中的测试向量，组合后得到新的测试向量集TC，并通过Get_fc（）调用TMAX 对新测试向量集TC与基础测试向量T 的故障覆盖率进行对比，若两者相同则证明此次约简成功.

4 实验与结果

本节给出了CTPSS 方法的实验分析，实验环境如下：Ubuntu 14.04，CPU Intel Core i5 -8250U 1.80GHz，8GB RAM，python 和C++，使用TetraMAX生成初始测试向量集并完成后续覆盖率检验.本文使用的测试电路为基准电路ISCAS85[24]，全扫描版本的ISCAS89[25]电路和ITC99[26]电路.

同时在实验对比中，本文选取了文献[20]中的DPSO 方法，DPSO 方法以最大故障覆盖率、最少测试向量数量和最小代价为优化目标，取得了较好的测试向量集约简效果.因此，在实际所需代价相同的情况下，本文以TMAX 提供的初始测试向量集故障覆盖率为最大故障覆盖率，即保证测试向量集覆盖率不变，以约简后的测试向量集规模为统一衡量指标，对CTPSS 方法与DPSO 方法进行了实验结果对比.同时，DPSO 方法终止条件与CTPSS 方法终止条件均为预期最大迭代次数，但DPSO 方法无预处理步骤，因此，可通过对比实验验证CTPSS 方法的预处理步骤在测试向量集约简问题中的重要性.

4.1 故障模型

在使用TMAX 生成故障列表时，使用故障模型为固定型故障（Stuck-at Fault，SAF）.SAF 故障模型是ATPG 工具中常用的故障类型，很多故障模型也可以用不同的SAF 组合表示而成.一个能够对SAF故障具有较高覆盖率的测试向量集对其它故障类型也会具有较高的故障覆盖率[27]，该测试向量集的实用性较高.

同时，为验证CTPSS 算法对于多种故障类型同样适用，选取TMAX 支持的静态电路故障（Integrated Circuit Quiescent Current Fault，IDDQ）中的the pseudo-stuck-at model 故障模型[28]进行了实验，此类故障类型也较容易获得较高的故障覆盖率.

4.2 CTPSS 实验结果

表1 中给出了CTPSS 方法与DPSO 方法实验结果对比，其中，约简后测试向量集故障覆盖率均与初始测试向量集故障覆盖率相同，故障类型为SAF.

其中，第1 列（Cir Name）为电路名称，以S 开头的电路为ISCAS89 电路，以B 开头的电路为ITC99电路；第2 列（Flt Num）为该电路中插入的SAF 故障类型的故障列表F 的规模；第3 列（TMAX）为TMAX生成的具有高故障覆盖率的初始测试向量集T 的规模；第4～7 列为CTPSS 方法与DPSO 方法得到的故障覆盖率不变的缩减后的测试向量集规模（Pat Num）及其对应的缩减率（Re Rate），其中缩减率为减少的测试向量在初始测试向量集中所占的比例.实验过程中，将CTPSS 方法和DPSO 方法的终止条件最高迭代次数均设置为5 × 103次.由于部分电路规模较大，DPSO 算法在可接受范围内不能产生解，表示为“—”.

从表1 可以看出，CTPSS 方法对测试集的缩减效果明显优于DPSO 方法，且对于大规模电路，CTPSS 方法同样可以得到良好的缩减效果.对于表1中所有电路，85%的电路测试集在CTPSS 方法中缩减率高达20%，其中缩减率高于30%的占23%左右.因此，可以看出CTPSS 方法对测试向量集的缩减有着良好的效果，可以有效缩减测试向量集，从而降低电路测试成本.

表2 给出了预处理阶段必然测试向量数目（Num of tj）与约简后的测试向量集数目（Num of TC）的对比，实验数据表明，在测试向量集约简这一实际问题中，预处理阶段在缩减算法数据规模上有着明显效果.

同时，表2 给出了CTPSS 方法的实际平均迭代次数（iterations），而DPSO 方法因无预处理步骤不能提前终止算法，其实际平均迭代次数均为5×103.迭代次数作为DPSO 方法与CTPSS 方法的算法终止条件，同时也是影响算法时间复杂度的重要因素.假设算法最大迭代次数为m，测试向量集规模为N，则DPSO 方法的时间复杂度可表示为O（N×m）[20-29].同时，对于CTPSS 方法，其最好时间复杂度为O（N），即在预处理产生的必然测试向量基础上，仅需少数迭代就可以满足算法终止条件，如表2 中电路s27、s208_1 等；其最坏时间复杂度为O（d×m），在已标记必然测试向量的大规模电路中，d 的值往往小于N.因此，由以上分析可知，CTPSS 方法的时间复杂度一般优于DPSO 方法.

表1 CTPSS 与DPSO 结果对比Tab.1 Comparison of CTPSS and DPSO results

表2 tj 数目与TC 数目对比Tab.2 Comparison of the number of tj and TC

为验证CTPSS 方法对于其他故障类型同样适用，表3 给出了CTPSS 方法在ISCAS85 电路上分别采用SAF 故障类型与IDDQ 故障类型下的实验结果.左侧为故障类型为SAF 时的实验数据，右侧为故障类型为IDDQ 时的实验数据.实验证明对于不同故障类型，CTPSS 方法都能获得良好的测试集约简效果.

表3 ISCAS85 在SAF 和IDDQ 下的实验结果比较Tab.3 Comparison of ISCAS85 under SAF and IDDQ fault model

5 结束语

本文通过对测试向量集约简问题的合理建模，通过建立测试向量集与故障列表之间的关系，将其转化为最小集合覆盖问题，并结合最小集合覆盖问题的求解方法行加权局部搜索方法RWLS 提出了CTPSS 方法，实现对TMAX 产生的初始测试向量集的约简.CTPSS 方法简洁容易操作，提供高效的预处理过程，确保不降低测试向量覆盖率的同时，实现测试向量集的约简.实验证明其对于约简不同故障类型生成的测试向量集均具有良好效果，对降低后续电路测试成本具有重要的现实意义.但是，当问题规模过大时，CTPSS 方法存在建模占用空间较大的不足，有待后续解决.