回退路径的选择方法和装置与流程

1.本技术涉及电路测试领域，具体而言，涉及一种回退路径的选择方法和装置。


背景技术：

2.自动测试向量生成(automatic test pattern generation，简称atpg）算法（测试向量是用于测试电路正确性的一组数据，既包括电路的输入数据，也包括用于和电路输出值进行比较的正确输出数据，该测试向量使得故障电路和正确电路的输出不同，该过程解决两个主要问题：故障激活，即在故障点处使得该故障出现；传播故障，即使电路的输出能够体现出该错误）通过搜索有效的测试向量来对电路中所有可能发生的故障进行尽可能完备的检测。为了缩短生产测试的测试时间、降低测试成本，需要快速、高效地完成故障检测，这其中，如何获得精简且具有高故障覆盖率（若一个测试将被测电路中的一个故障激活，同时将该故障产生的错误输出到电路的某一输出线路，则称该测试覆盖了此故障，测试向量的故障覆盖率是指该测试向量能够检测出的故障数与该电路中可能出现的所有该类型故障总数的比值，它是衡量一个测试向量的优劣的重要指标）的测试向量集显得至关重要。然而atpg是一组np-complete问题，也就是说，不存在一个算法能够使得该问题在线性时间内得到有效解决。
3.对一个有n位输入的组合逻辑电路来说，进行穷尽的测试需要用个输入向量。尽管使用穷举法进行测试能够实现高故障率，但是在实际生产应用中并不现实。目前已有一些完备的搜索算法来实现atpg。路径敏化法是在电路中通过故障敏化、故障传播以及线值确认来完成故障检测。经典的路径敏化法包括d算法（拓扑结构测试中最经典的方法，采用多维敏化的思想，同时敏化从故障位置到电路的所有输出端的全部通路，从而检测非冗余电路中所有可以检测的故障）、podem算法（全称为path oriented decision making，该算法对激活的故障向后追踪到原始输入，搜索所有可能的原始输入赋值，只要找到一个符合要求的即可作为测试图形，算法即结束。对于确定的故障，首先是确定目标，然后对连接到门的输入线选择原始输入赋值）和fan算法（全称为fan-out-oriented，主要思路是向后追踪不仅仅止于原始输入，也可以止于中间节点；生成过程中不仅仅是满足一个目标，而是采用多路径向后追踪步骤尽可能同时满足多个目标）。近年来，机器学习在电子设计自动化领域扮演着重要的角色，就测试技术而言，已在晶圆诊断、扫描链诊断、电路缺陷识别、测试压缩等方向取得了重要突破，而基于机器学习的自动测试向量生成技术的研究尚处于起步阶段。
4.传统的自动测试生成算法，在完成电路中的单固定型故障检测时会引起大量的回溯操作，这会影响测试生成的效率。podem是比较成熟的路径敏化算法，它对d算法作了有益的改进，不在电路内部节点做决策，只对所有可能的输入模式空间进行有效的隐式查找，进而大幅度地缩小了搜索空间。podem在回退时，可以随机选择回退路径，也可以结合相关启发式信息进行回退。常用的启发式信息包括线路的逻辑层级和可测试性度量方法，结合启发式信息进行回退时能够有效减少回溯次数，从而提高测试生成的效率，然而podem无论是
结合线路的逻辑层级还是可测试性度量方法，在完成单固定型故障检测时仍会引起较大数量的回溯操作。基于人工神经网络的自动向量测试生成方法，利用人工神经网络模型来指导podem的路径回退能够减少回溯次数，在部分电路中的表现明显优于传统启发式策略，但是前期需要消耗大量的显存资源来训练有效的模型，并且需要使用较多的训练集样本才能得到有效的预测模型。
5.针对上述的问题，目前尚未提出有效的解决方案。


技术实现要素：

6.本技术实施例提供了一种回退路径的选择方法和装置，以至少解决相关技术中利用人工神经网络模型来指导podem的路径回退时，前期需要消耗大量的显存资源的技术问题。
7.根据本技术实施例的一个方面，提供了一种回退路径的选择方法，包括：利用训练样本对原始knn算法模型进行训练，得到目标knn算法模型，其中，所述训练样本包括正样本和负样本，所述正样本表示与故障匹配的有效回退路径，所述负样本表示因与故障不匹配而引起回溯的无效回退路径；在利用poedm测试生成方法生成测试向量的过程中，利用所述目标knn算法模型选择回退路径，其中，所述测试向量用于用电路进行故障测试，所述目标knn算法模型用于利用从所述训练样本中学习到的线路节点的特征选择回退路径。
8.根据本技术实施例的另一方面，还提供了一种回退路径的选择装置，包括：训练模块，用于利用训练样本对原始knn算法模型进行训练，得到目标knn算法模型，其中，所述训练样本包括正样本和负样本，所述正样本表示与故障匹配的有效回退路径，所述负样本表示因与故障不匹配而引起回溯的无效回退路径；选择模块，用于在利用poedm测试生成方法生成测试向量的过程中，利用所述目标knn算法模型选择回退路径，其中，所述测试向量用于用电路进行故障测试，所述目标knn算法模型用于利用从所述训练样本中学习到的线路节点的特征选择回退路径。
9.根据本技术实施例的另一方面，还提供了一种存储介质，该存储介质包括存储的程序，程序运行时执行上述的方法。
10.根据本技术实施例的另一方面，还提供了一种电子装置，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，处理器通过计算机程序执行上述的方法。
11.根据本技术的一个方面，提供了一种计算机程序产品或计算机程序，该计算机程序产品或计算机程序包括计算机指令，该计算机指令存储在计算机可读存储介质中。计算机设备的处理器从计算机可读存储介质读取该计算机指令，处理器执行该计算机指令，使得该计算机设备执行上述方法中任一实施例的步骤。
12.在本技术实施例中，利用训练样本（包括正负样本，正样本表示与故障匹配的有效回退路径，负样本表示因与故障不匹配而引起回溯的无效回退路径）对原始knn算法模型进行训练，得到目标knn算法模型；在利用poedm测试生成方法生成测试向量的过程中，目标knn算法模型用于利用从训练样本中学习到的线路节点的特征选择回退路径。由于knn算法模型所需的样本数量相较于人工神经网络模型所需的样本数量，呈数量级级别的下降，可以解决相关技术中利用人工神经网络模型来指导podem的路径回退时，前期需要消耗大量
的显存资源的技术问题。
附图说明
13.此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本发明的实施例，并与说明书一起用于解释本发明的原理。
14.为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，对于本领域普通技术人员而言，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。
15.一个或多个实施例通过与之对应的附图中的图片进行示例性说明，这些示例性说明并不构成对实施例的限定，附图中具有相同参考数字标号的元件表示为类似的元件，除非有特别申明，附图中的图不构成比例限制。
16.图1是根据本技术实施例的一种可选的回退路径的选择方法的流程图；图2是根据本技术实施例的基于k近邻的自动测试向量生成方案的框架图；图3是根据本技术实施例的一种可选的电路处理方案的示意图；图4是根据本技术实施例的一种可选的不同启发式策略下回溯次数的示意图；图5是根据本技术实施例的一种可选的不同启发式策略下回溯次数的示意图；图6是根据本技术实施例的一种可选的不同启发式策略下回溯次数的示意图；图7是根据本技术实施例的一种可选的不同启发式策略下回溯次数的示意图；图8是根据本技术实施例的一种可选的回退路径的选择装置的示意图；以及，图9是根据本技术实施例的一种终端的结构框图。
具体实施方式
17.为了使本技术领域的人员更好地理解本技术方案，下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本技术一部分的实施例，而不是全部的实施例。基于本技术中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都应当属于本技术保护的范围。
18.需要说明的是，本技术的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本技术的实施例能够以除了在这里图示或描述的那些以外的顺序实施。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法、系统、产品或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它步骤或单元。
19.为了减少数字电路自动测试向量生成(atpg)的回溯次数，提高其性能表现。根据本技术实施例的一方面，提供了一种回退路径的选择方法的方法实施例。图1是根据本技术实施例的一种可选的回退路径的选择方法的流程图，如图1所示，该方法可以包括以下步骤：步骤s11，利用训练样本对原始knn算法模型进行训练，得到目标knn算法模型，训
练样本包括正样本和负样本，正样本表示与故障匹配的有效回退路径，负样本表示因与故障不匹配而引起回溯的无效回退路径。
20.1）先获取训练样本关联的电路结构数据和可测试性度量信息。
21.1.1)将测试回退路径输入训练电路，得到测试结果，如得到单固定型故障的测试结果。
22.1.2)在测试结果表明测试回退路径为与故障匹配的有效回退路径的情况下，将测试回退路径作为正样本，并将训练电路中测试回退路径关联的电路结构数据和可测试性度量信息作为正样本的电路结构数据和可测试性度量信息。
23.1.3)在测试结果表明测试回退路径为因与故障不匹配而引起回溯的无效回退路径的情况下，将测试回退路径作为负样本，并将训练电路中测试回退路径关联的电路结构数据和可测试性度量信息作为负样本的电路结构数据和可测试性度量信息。
24.1.4)为收集到的训练样本打标，以便于在训练时区别正样本和负样本。
25.2）将训练样本关联的电路结构数据和可测试性度量信息输入原始knn算法模型，以便于对原始knn算法模型进行训练，得到目标knn算法模型。
26.2.1）将门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数、scoap的0可控制性、1可控制性以及可观测性输入原始knn算法模型。
27.scoap全称为sandia controllability / observability analysis program，是一种可测试性度量工具，其复杂度随电路规模呈线性增长，scoap基于电路拓扑学，是一种静态分析，容易计算，为电路的可控和可观提供一个不错的估计值，也为test point的插入提供依据。
28.上述控制性指将电路中节点置为预定逻辑值的难易程度，可观测性指电路中任意节点的值的可观察的难易程度。
29.2.2）在训练过程中，原始knn算法模型利用门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数、scoap的0可控制性、1可控制性以及可观测性学习到特征空间中与正样本对应的部分空间、与负样本对应的部分空间，将完成训练后的原始knn算法模型作为目标knn算法模型。
30.步骤s12，在利用poedm测试生成方法生成测试向量的过程中，利用目标knn算法模型选择回退路径，测试向量用于用电路进行故障测试，目标knn算法模型用于利用从训练样本中学习到的线路节点的特征选择回退路径。
31.1）将候选回退路径的门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数、scoap的0可控制性、1可控制性以及可观测性输入目标knn算法模型，目标knn算法模型根据以上信息确定候选回退路径在特征空间中的所在位置，根据所在位置确定候选回退路径为有效回退路径的概率。
32.2）将所有候选回退路径中为有效回退路径的概率最高的作为实际选择的回退路径。
33.发明人在研究的过程中发现，电路中每个线路节点都包含了各自的特性(如电路结构数据和可测试性度量信息)，而在atpg过程中可以将产生测试向量的线路节点记为“成功”(success)，引起回溯的线路节点记为“失败”(failure)，因此可以把这个过程视为二分类。使用机器学习方法进行探索的思路是：让模型学习正负样本数据，进而指导atpg选择回
退路径，以尽快到达有效决策点，减少回溯次数。
34.在研究的过程中还发现，在基于人工神经网络的自动测试向量生成方法中，搭建模型阶段需要消耗较多的gpu显存资源，并且需要使用较多的训练集样本才能得到有效的预测模型。k近邻算法是一种简单、经典的机器学习算法，它没有显示的训练过程，在搭建模型阶段就能够节省一定的显存资源开销。在完成单固定型故障测试生成的过程中，可能会遇到“成功”的线路节点与“失败”的线路节点轨迹重合，对于机器学习算法，存在“冲突”的样本数据会影响模型的准确性。由于knn算法的特殊性，它是根据周围有限的临近样本来判定所属类别，因此对于不同类别之间交叉或重叠较多的样本集，knn算法更为适用。也正是由于knn对异常值不敏感，针对atpg的样本数据，knn能够尽可能消除“冲突”数据对算法本身的影响。这就使得该发明只需要少量的训练集样本就能得到有效的预测模型。
35.通过上述步骤，利用训练样本（包括正负样本，正样本表示与故障匹配的有效回退路径，负样本表示因与故障不匹配而引起回溯的无效回退路径）对原始knn算法模型进行训练，得到目标knn算法模型；在利用poedm测试生成方法生成测试向量的过程中，目标knn算法模型用于利用从训练样本中学习到的线路节点的特征选择回退路径。由于knn算法模型所需的样本数量相较于人工神经网络模型所需的样本数量，呈数量级级别的下降，可以解决相关技术中利用人工神经网络模型来指导podem的路径回退时，前期需要消耗大量的显存资源的技术问题。
36.本发明提出将机器学习中的k近邻算法引入至podem测试生成算法，knn结合电路结构数据（门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数）和可测试性度量信息（scoap的0可控制性、1可控制性和可观测性)来指导podem算法中回退路径的选择，替代传统的启发式策略，以尽快到达有效决策点，减少回溯次数。作为一种可选的实施例，下文结合具体实施方式进一步详述本技术的技术方案：本发明提出一种基于k近邻的数字电路自动测试向量生成方法，将机器学习中的k近邻算法应用至自动测试向量生成。基于atpg中经典的podem算法，使用knn结合电路结构数据和可测试性度量信息来指导podem的回退路径选择，旨在选择更合适的回退路径以尽快到达有效决策点，减少atpg的回溯次数和运行时间。
37.以下用图2中的例子描述该发明的总体框架，主要分为样本采集、样本输入、模型搭建和模型应用等几个主要步骤。
38.步骤1，样本采集。
39.为了检测图2“训练电路”在“o”线路的stuck-at-1（简称sa1）故障，假设m-h-c和n-k-j-f是atpg算法的两次回退路径，m-h-c为“有效”回退路径，产生了有效输入赋值；n-k-j-f为“无效”回退路径，发生了冲突需要回溯。测试生成过程中对每次回退路径进行记录，“有效”回退路径记为“成功”(success)，即正样本，相应的特征为正样本特征positive feature；“无效”回退路径记为“失败”(failure)，即负样本，相应的特征为负样本特征negative feature。
40.每条路径上的所有线路节点都包含各自的电路结构数据和可测试性度量信息，本发明采用的电路结构数据包括逻辑门的类型(gate-type)、当前线路节点距输入端的最短距离(dpi，用节点距离输入的线路数量表示)、逻辑门的扇出个数(fanout-size)；使用的可测试性度量方法是基于电路拓扑结构的scoap，可测试性度量信息包括scoap的0可控制性
(cc0)、1可控制性(cc1)和可观测性(co)。
41.当atpg程序启动时，正负样本数据开始被采集；当检测完电路中的所有故障，正负样本数据也被采集完成。表1是图2中针对“训练电路”完成单固定型故障测试生成过程的回退路径追踪记录。
42.表1步骤2，样本输入及模型搭建。
43.在步骤1中收集的这些正负样本数据会输入到knn中，knn利用它们对特征向量空间进行划分，并将其划分的结果作为最终的算法模型。
44.由表1可知，线路节点包含了各自的“特性”，这些“特性”可以作为样本的输入特征，而其中“成功”的线路节点(正样本)输出标签记为“1”，“失败”的线路节点(负样本)输出标签记为“0”，因此可以把这个过程视为二分类。使用机器学习方法进行探索的思路是：让模型学习正负样本数据，进而指导atpg选择回退路径，以尽快到达有效决策点，减少回溯次数。
45.步骤3，模型应用。
46.模型会被用于“测试电路”进行验证，atpg在回退时，当经过含有多输入的逻辑门，knn将会结合线路特征评估从每个输入回退成功的可能性，并选择具有最大可能性的输入进行回退。
47.在完成单固定型故障测试生成的过程中，可能会遇到“成功”的线路节点与“失败”的线路节点轨迹重合，如表中的n、k、j同时存在正样本和负样本。对于机器学习算法，存在“冲突”的样本数据会影响模型的准确性。由于knn算法的特殊性，它是根据周围有限的临近样本来判定所属类别，因此对于不同类别之间交叉或重叠较多的样本集，knn算法更为适用。也正是由于knn对异常值不敏感，针对atpg的样本数据，knn能够尽可能消除“冲突”数据对算法本身的影响。
48.本发明的技术方案可在iscas85、iscas89和itc99基准电路上进行验证，综合评估
自动测试向量生成的回溯次数、回退次数、运行时间和故障覆盖率，结果表明了本发明相对于传统启发式策略以及基于人工神经网络(ann)的回退路径选择策略的有效性。相比于基于ann的方法，knn没有显示的训练过程，在搭建模型阶段能够节省一定的显存资源开销，并且可以使用更少的训练集样本得到有效的预测模型（实验中knn训练集样本数据量为7万，ann训练集样本数据量为80万，ann的模型训练消耗的训练集样本数据量超过knn方法的10倍）。
49.为了贴近工业级芯片设计流程，本发明所使用到的benchmark电路采用商业eda工具和标准工艺库综合生成网表，处理流程如图3所示：首先，读取寄存器传输级(register transfer leve，rtl)的verilog文件和smic180工艺库，经过synopsys公司的dc(design compile)工具综合得到门级网表(gate level netlist)；再通过一款国产测试综合工具ictest读取门级网表建立内部数据结构，并在此基础上使用ictest-atpg执行测试生成。
50.接下来介绍本发明中所使用到的数据集，训练集样本数据来自跟踪“训练电路”的atpg过程中的有效和无效回退路径，测试集样本数据是从待测电路的网表结构中静态分析获得。在iscas85、iscas89、itc99系列中各选取一个电路作为“训练电路”，选取“训练电路”需要考察atpg算法在“随机”(random)搜素策略下的故障覆盖率、电路逻辑深度、逻辑门的扇出个数，故障覆盖率越低、电路逻辑深度越深、逻辑门的扇出个数越多意味该电路越“复杂”，使用复杂电路作为“训练电路”能够生成更有价值的样本数据，从而提高机器学习算法的学习效率。在“训练电路”的atpg结果中，产生了有效输入赋值的路径被记为正样本，引起回溯的路径被记为负样本，这会导致负样本的数量远小于正样本，也就是正负样本严重不均衡。考虑到高度失衡的样本数据可能会影响模型的性能表现，本发明通过在全部数据集中采样正负样本数量相等的子集进行处理。
51.基于atpg的podem算法，分别在待测电路中使用传统的启发式策略(distance、scoap)和机器学习启发式策略(knn、ann)引导podem进行回退，从而验证本发明的knn启发式策略的有效性。两种机器学习启发式策略使用相同的“训练电路”。
52.图4至图7是在benchmark电路上分别使用distance、scoap、ann和knn启发式策略下的回溯次数、回退次数、运行时间、故障覆盖率。结果是对比其他启发式策略，knn启发式策略的提升/降低倍数，正向柱状图表明knn启发式策略优于当前启发式策略，负向柱状图表明knn启发式策略劣于当前启发式策略。
53.正确的回退路径会减少atpg的回溯次数，从图4中可以看出，所提方法在大多数电路上都大大优于传统启发式策略和ann启发式策略。ann启发式策略在部分电路中优于传统启发式策略，但劣于knn启发式策略，如在c499、s13207的backtrack表现。观察c2670、s15850、b05等电路，ann启发式策略在部分电路上也会优于传统启发式策略及knn启发式策略。从图5中“回退次数”的表现中可以看出，在多数电路上knn启发式策略都占优势，但是结合图4可知“回退次数”与“回溯次数”指标并没有直接关联性。回溯次数减少能够降低atpg的运行时间，在绝大多数电路中“运行时间”与“回溯次数”可以直接对应，然而也有部分电路的“运行时间”与“回溯次数”没有直接关联，这部分电路可能与回退次数以及启发式策略在电路中部分线路的决策有关，比如过多的回退次数会影响到atpg的运行时间。故障覆盖率是atpg的重要指标，由于当前benchmark电路规模并不算大，在电路中运行atpg均能达到较好的故障覆盖率，因此每种启发式策略下的故障覆盖率差别并不明显。从图7中“故障覆
盖率”指标可以看出，所提方法在部分电路上仍然会优于其他启发式策略，如果将其应用在工业级的大电路中会有更好的表现。
54.综上，本发明提出了一种基于k近邻的数字电路自动测试向量生成方法，将机器学习中的经典算法knn应用至atpg。基于atpg的podem算法，在回退中使用knn启发式策略替代传统启发式策略，由于knn启发式策略包含了电路结构数据和可测试性度量信息，这可以尽可能的指导podem选择正确的回退路径，从而提高atpg的性能。综合对比了传统启发式策略和使用ann的启发式策略，在iscas85、iscas89和itc99的基准电路上进行了验证，结果验证了该发明的有效性。
55.需要说明的是，对于前述的各方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本技术并不受所描述的动作顺序的限制，因为依据本技术，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定是本技术所必须的。
56.通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到根据上述实施例的方法可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于这样的理解，本技术的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质（如rom/ram、磁碟、光盘）中，包括若干指令用以使得一台终端设备（可以是手机，计算机，服务器，或者网络设备等）执行本技术各个实施例所述的方法。
57.根据本技术实施例的另一个方面，还提供了一种用于实施上述回退路径的选择方法的回退路径的选择装置。图8是根据本技术实施例的一种可选的回退路径的选择装置的示意图，如图8所示，该装置可以包括：训练模块81，用于利用训练样本对原始knn算法模型进行训练，得到目标knn算法模型，其中，所述训练样本包括正样本和负样本，所述正样本表示与故障匹配的有效回退路径，所述负样本表示因与故障不匹配而引起回溯的无效回退路径；选择模块82，用于在利用poedm测试生成方法生成测试向量的过程中，利用所述目标knn算法模型选择回退路径，其中，所述测试向量用于用电路进行故障测试，所述目标knn算法模型用于利用从所述训练样本中学习到的线路节点的特征选择回退路径。
58.通过上述模块，利用训练样本（包括正负样本，正样本表示与故障匹配的有效回退路径，负样本表示因与故障不匹配而引起回溯的无效回退路径）对原始knn算法模型进行训练，得到目标knn算法模型；在利用poedm测试生成方法生成测试向量的过程中，目标knn算法模型用于利用从训练样本中学习到的线路节点的特征选择回退路径。由于knn算法模型所需的样本数量相较于人工神经网络模型所需的样本数量，呈数量级级别的下降，可以解决相关技术中利用人工神经网络模型来指导podem的路径回退时，前期需要消耗大量的显存资源的技术问题。
59.可选地，训练模块还用于：获取所述训练样本关联的电路结构数据和可测试性度量信息；将所述训练样本关联的电路结构数据和可测试性度量信息输入所述原始knn算法模型，以便于对所述原始knn算法模型进行训练，得到所述目标knn算法模型。
60.可选地，训练模块还用于：将门的类型、当前线路节点距输入端的最短距离、逻辑
门的扇出个数、scoap的0可控制性、1可控制性以及可观测性输入所述原始knn算法模型，其中，所述训练样本关联的电路结构数据包括门的类型、当前线路节点距输入端的最短距离以及逻辑门的扇出个数，所述训练样本关联的可测试性度量信息包括scoap的0可控制性、1可控制性以及可观测性；将完成训练后的所述原始knn算法模型作为所述目标knn算法模型，其中，所述原始knn算法模型用于在训练过程中，利用门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数、scoap的0可控制性、1可控制性以及可观测性学习到特征空间中与所述正样本对应的部分空间、与所述负样本对应的部分空间。
61.可选地，训练模块还用于：将测试回退路径输入训练电路，得到测试结果；在所述测试结果表明所述测试回退路径为与故障匹配的有效回退路径的情况下，将所述测试回退路径作为正样本，并将所述训练电路中所述测试回退路径关联的电路结构数据和可测试性度量信息作为所述正样本的电路结构数据和可测试性度量信息；在所述测试结果表明所述测试回退路径为因与故障不匹配而引起回溯的无效回退路径的情况下，将所述测试回退路径作为负样本，并将所述训练电路中所述测试回退路径关联的电路结构数据和可测试性度量信息作为所述负样本的电路结构数据和可测试性度量信息。
62.可选地，训练模块还用于：将所述测试回退路径输入所述训练电路，得到所述训练电路的单固定型故障的测试结果。
63.可选地，训练模块还用于：在获取所述训练样本关联的电路结构数据和可测试性度量信息之后，为收集到的所述训练样本打标，以区别所述正样本和所述负样本。
64.可选地，选择模块还用于：将候选回退路径的门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数、scoap的0可控制性、1可控制性以及可观测性输入所述目标knn算法模型，得到所述候选回退路径为有效回退路径的概率，其中，所述目标knn算法模型用于根据所述候选回退路径的门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数、scoap的0可控制性、1可控制性以及可观测性确定所述候选回退路径在特征空间中的所在位置，根据所在位置确定所述候选回退路径为有效回退路径的概率；将所有候选回退路径中为有效回退路径的概率最高的作为实际选择的回退路径。
65.此处需要说明的是，上述模块与对应的步骤所实现的示例和应用场景相同，但不限于上述实施例所公开的内容。需要说明的是，上述模块作为装置的一部分可以运行在相应的硬件环境中，可以通过软件实现，也可以通过硬件实现，其中，硬件环境包括网络环境。
66.根据本技术实施例的另一个方面，还提供了一种用于实施上述回退路径的选择方法的服务器或终端。
67.图9是根据本技术实施例的一种终端的结构框图，如图9所示，该终端可以包括：一个或多个（图9中仅示出一个）处理器901、存储器903、以及传输装置905，如图9所示，该终端还可以包括输入输出设备907。
68.其中，存储器903可用于存储软件程序以及模块，如本技术实施例中的回退路径的选择方法和装置对应的程序指令/模块，处理器901通过运行存储在存储器903内的软件程序以及模块，从而执行各种功能应用以及数据处理，即实现上述的回退路径的选择方法。存储器903可包括高速随机存储器，还可以包括非易失性存储器，如一个或者多个磁性存储装置、闪存、或者其他非易失性固态存储器。在一些实例中，存储器903可进一步包括相对于处理器901远程设置的存储器，这些远程存储器可以通过网络连接至终端。上述网络的实例包
括但不限于互联网、企业内部网、局域网、移动通信网及其组合。
69.上述的传输装置905用于经由一个网络接收或者发送数据，还可以用于处理器与存储器之间的数据传输。上述的网络具体实例可包括有线网络及无线网络。在一个实例中，传输装置905包括一个网络适配器（network interface controller，nic），其可通过网线与其他网络设备与路由器相连从而可与互联网或局域网进行通讯。在一个实例中，传输装置905为射频（radio frequency，rf）模块，其用于通过无线方式与互联网进行通讯。
70.其中，具体地，存储器903用于存储应用程序。
71.处理器901可以通过传输装置905调用存储器903存储的应用程序，以执行下述步骤：利用训练样本对原始knn算法模型进行训练，得到目标knn算法模型，其中，所述训练样本包括正样本和负样本，所述正样本表示与故障匹配的有效回退路径，所述负样本表示因与故障不匹配而引起回溯的无效回退路径；在利用poedm测试生成方法生成测试向量的过程中，利用所述目标knn算法模型选择回退路径，其中，所述测试向量用于用电路进行故障测试，所述目标knn算法模型用于利用从所述训练样本中学习到的线路节点的特征选择回退路径。
72.可选地，本实施例中的具体示例可以参考上述实施例中所描述的示例，本实施例在此不再赘述。
73.本领域普通技术人员可以理解，图9所示的结构仅为示意，终端可以是智能手机（如android手机、ios手机等）、平板电脑、掌上电脑以及移动互联网设备（mobile internet devices，mid）、pad等终端设备。图9其并不对上述电子装置的结构造成限定。例如，终端还可包括比图9中所示更多或者更少的组件（如网络接口、显示装置等），或者具有与图9所示不同的配置。
74.本领域普通技术人员可以理解上述实施例的各种方法中的全部或部分步骤是可以通过程序来指令终端设备相关的硬件来完成，该程序可以存储于一计算机可读存储介质中，存储介质可以包括：闪存盘、只读存储器（read-only memory，rom）、随机存取器（random access memory，ram）、磁盘或光盘等。
75.本技术的实施例还提供了一种存储介质。可选地，在本实施例中，上述存储介质可以用于执行回退路径的选择方法的程序代码。
76.可选地，在本实施例中，上述存储介质可以位于上述实施例所示的网络中的多个网络设备中的至少一个网络设备上。
77.可选地，在本实施例中，存储介质被设置为存储用于执行以下步骤的程序代码：利用训练样本对原始knn算法模型进行训练，得到目标knn算法模型，其中，所述训练样本包括正样本和负样本，所述正样本表示与故障匹配的有效回退路径，所述负样本表示因与故障不匹配而引起回溯的无效回退路径；在利用poedm测试生成方法生成测试向量的过程中，利用所述目标knn算法模型选择回退路径，其中，所述测试向量用于用电路进行故障测试，所述目标knn算法模型用于利用从所述训练样本中学习到的线路节点的特征选择回退路径。
78.可选地，本实施例中的具体示例可以参考上述实施例中所描述的示例，本实施例在此不再赘述。
79.可选地，在本实施例中，上述存储介质可以包括但不限于：u盘、只读存储器（rom，read-only memory）、随机存取存储器（ram，random access memory）、移动硬盘、磁碟或者光盘等各种可以存储程序代码的介质。
80.上述本技术实施例序号仅仅为了描述，不代表实施例的优劣。
81.上述实施例中的集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在上述计算机可读取的存储介质中。基于这样的理解，本技术的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在存储介质中，包括若干指令用以使得一台或多台计算机设备（可为个人计算机、服务器或者网络设备等）执行本技术各个实施例所述方法的全部或部分步骤。
82.在本技术的上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。
83.在本技术所提供的几个实施例中，应该理解到，所揭露的客户端，可通过其它的方式实现。其中，以上所描述的装置实施例仅仅是示意性的，例如所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，单元或模块的间接耦合或通信连接，可以是电性或其它的形式。
84.所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。
85.另外，在本技术各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。
86.以上所述仅是本技术的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本技术原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本技术的保护范围。

技术特征：
1.一种回退路径的选择方法，其特征在于，包括：利用训练样本对原始knn算法模型进行训练，得到目标knn算法模型，其中，所述训练样本包括正样本和负样本，所述正样本表示与故障匹配的有效回退路径，所述负样本表示因与故障不匹配而引起回溯的无效回退路径；在利用poedm测试生成方法生成测试向量的过程中，利用所述目标knn算法模型选择回退路径，其中，所述测试向量用于用电路进行故障测试，所述目标knn算法模型用于利用从所述训练样本中学习到的线路节点的特征选择回退路径。2.根据权利要求1所述的方法，其特征在于，利用训练样本对原始knn算法模型进行训练，得到目标knn算法模型，包括：获取所述训练样本关联的电路结构数据和可测试性度量信息；将所述训练样本关联的电路结构数据和可测试性度量信息输入所述原始knn算法模型，以便于对所述原始knn算法模型进行训练，得到所述目标knn算法模型。3.根据权利要求2所述的方法，其特征在于，将所述训练样本关联的电路结构数据和可测试性度量信息输入所述原始knn算法模型，以便于对所述原始knn算法模型进行训练，得到所述目标knn算法模型，包括：将门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数、scoap的0可控制性、1可控制性以及可观测性输入所述原始knn算法模型，其中，所述训练样本关联的电路结构数据包括门的类型、当前线路节点距输入端的最短距离以及逻辑门的扇出个数，所述训练样本关联的可测试性度量信息包括scoap的0可控制性、1可控制性以及可观测性；将完成训练后的所述原始knn算法模型作为所述目标knn算法模型，其中，所述原始knn算法模型用于在训练过程中，利用门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数、scoap的0可控制性、1可控制性以及可观测性学习到特征空间中与所述正样本对应的部分空间、与所述负样本对应的部分空间。4.根据权利要求2所述的方法，其特征在于，获取所述训练样本关联的电路结构数据和可测试性度量信息，包括：将测试回退路径输入训练电路，得到测试结果；在所述测试结果表明所述测试回退路径为与故障匹配的有效回退路径的情况下，将所述测试回退路径作为正样本，并将所述训练电路中所述测试回退路径关联的电路结构数据和可测试性度量信息作为所述正样本的电路结构数据和可测试性度量信息；在所述测试结果表明所述测试回退路径为因与故障不匹配而引起回溯的无效回退路径的情况下，将所述测试回退路径作为负样本，并将所述训练电路中所述测试回退路径关联的电路结构数据和可测试性度量信息作为所述负样本的电路结构数据和可测试性度量信息。5.根据权利要求4所述的方法，其特征在于，将测试回退路径输入训练电路，得到测试结果，包括：将所述测试回退路径输入所述训练电路，得到所述训练电路的单固定型故障的测试结果。6.根据权利要求2所述的方法，其特征在于，在获取所述训练样本关联的电路结构数据和可测试性度量信息之后，所述方法还包括：
为收集到的所述训练样本打标，以区别所述正样本和所述负样本。7.根据权利要求1至6中任意一项所述的方法，其特征在于，利用所述目标knn算法模型选择回退路径，包括：将候选回退路径的门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数、scoap的0可控制性、1可控制性以及可观测性输入所述目标knn算法模型，得到所述候选回退路径为有效回退路径的概率，其中，所述目标knn算法模型用于根据所述候选回退路径的门的类型、当前线路节点距输入端的最短距离、逻辑门的扇出个数、scoap的0可控制性、1可控制性以及可观测性确定所述候选回退路径在特征空间中的所在位置，根据所在位置确定所述候选回退路径为有效回退路径的概率；将所有候选回退路径中为有效回退路径的概率最高的作为实际选择的回退路径。8.一种回退路径的选择装置，其特征在于，包括：训练模块，用于利用训练样本对原始knn算法模型进行训练，得到目标knn算法模型，其中，所述训练样本包括正样本和负样本，所述正样本表示与故障匹配的有效回退路径，所述负样本表示因与故障不匹配而引起回溯的无效回退路径；选择模块，用于在利用poedm测试生成方法生成测试向量的过程中，利用所述目标knn算法模型选择回退路径，其中，所述测试向量用于用电路进行故障测试，所述目标knn算法模型用于利用从所述训练样本中学习到的线路节点的特征选择回退路径。9.一种存储介质，其特征在于，所述存储介质包括存储的程序，其中，所述程序运行时执行上述权利要求1至7任一项中所述的方法。10.一种电子装置，包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，其特征在于，所述处理器通过所述计算机程序执行上述权利要求1至7任一项中所述的方法。

技术总结
本申请公开了一种回退路径的选择方法和装置。其中，该方法包括：利用训练样本对原始KNN算法模型进行训练，得到目标KNN算法模型，训练样本包括正样本和负样本，正样本表示与故障匹配的有效回退路径，负样本表示因与故障不匹配而引起回溯的无效回退路径；在利用POEDM测试生成方法生成测试向量的过程中，利用目标KNN算法模型选择回退路径，测试向量用于用电路进行故障测试，目标KNN算法模型用于利用从训练样本中学习到的线路节点的特征选择回退路径。本申请解决了相关技术中利用人工神经网络模型来指导PODEM的路径回退时，前期需要消耗大量的显存资源的技术问题。耗大量的显存资源的技术问题。耗大量的显存资源的技术问题。


技术研发人员：李文星 王天成 李华伟
受保护的技术使用者：中科鉴芯（北京）科技有限责任公司
技术研发日：2023.06.06
技术公布日：2023/7/12