CN104486222A - 基于蚁群优化算法的小时延缺陷测试关键路径选择方法 - Google Patents

Abstract

基于蚁群优化算法的小时延缺陷测试关键路径选择方法，涉及一种小时延缺陷的测试路径选择方法。它为了解决现有基于贪婪算法对小时延缺陷的测试通路选择方法时间长、速度慢的问题。本发明所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法，首先对测试电路读入分析电路节点连接信息时的算法及存储数据的格式；然后对所要测试电路在读取连接信息的基础上转换为有向无环路图的形式；最后使用蚁群优化算法求解电路网络中的最长通路作为小时延缺陷的关键路径。在保证较高的正确率的前提下，加快了运行速度，以提高路径选择方法在实际应用的实用性。适用于小时延缺陷的测试路径的选择。

Description

基于蚁群优化算法的小时延缺陷测试关键路径选择方法

技术领域

本发明涉及一种小时延缺陷的测试路径选择方法。

背景技术

集成电路制造工艺的进步导致芯片上集成晶体管数目急剧上升，芯片日益趋向高功能密度和高工作频率。这不仅为设计同样也为测试带来了巨大的挑战，因为特征尺寸降低致使芯片中出现了更多的缺陷。制造中的缺陷包括阻性开路短路、边缘毛刺、工艺参数偏差、长互连线带来的耦合电容增加、电源噪声等因素，这些都会给电路带来小时延缺陷，从而给电路带来额外的时序错误而导致芯片失效。随着芯片设计进入45nm时代，小时延缺陷检测是保证电路高性能和高可靠性必不可少的步骤，因此如何选择针对小时延缺陷的测试路径是检测小时延缺陷的关键。

因为无法预测哪条长通路上的小时延缺陷累积后会导致电路输出端时序失效，这些小时延缺陷的存在时刻威胁着芯片的稳定性和可靠性，会导致芯片早期失效。经研究表明当下最新工艺水平下很大部分的时延失效是由小时延缺陷引起的。在高频电路对时序要求如此严格的今天，只有有效检测小时延缺陷才能够保证高集成度电路的可靠性和质量。然而小时延缺陷在普通的针对时延缺陷的测试路径上存在测试逃脱的现象，因而选择能够针对小时延缺陷的测试路径，是能够高效快速检测的关键。

因而小时延测试其本质就是测试路径的选择问题，不同的测试路径对小时延缺陷的检测能力是有差异的。由上文论述可知，要提高测试路径对小时延缺陷的检测能力，就要降低测试时钟周期与通路敏化时延值之差，也就是时延余量(Slack)。因为时延余量的大小决定了能够检测到时延缺陷大小的最大值。而当前学术界和工业界的也是从降低测试时钟周期和增大通路敏化时延这两个方面进行研究。

而当下的EDA工具中对小时延缺陷的测试通路选择大多是基于贪婪算法下对电路选择长通路作为小时延缺陷的测试通路，贪婪算法虽然基于全局搜索能够获得最优解，但是时间复杂度和空间复杂度过高是其缺点。

发明内容

本发明是为了解决现有基于贪婪算法对小时延缺陷的测试通路选择方法时间长、速度慢的问题，现提供基于蚁群优化算法的小时延缺陷测试关键路径选择方法。

基于蚁群优化算法的小时延缺陷测试关键路径选择方法，它包括以下步骤：

步骤一：读取测试电路的节点在连接信息时的算法、数据存储方法和数据存储格式；

步骤二：将测试电路转换成有向无环拓扑图的形式，并将该有向无环拓扑图存储为邻接矩阵，然后将该邻接矩阵作为目标电路网络；

步骤三：利用蚁群优化算法将所有蚂蚁均放置在目标电路网络的输入节点处；

步骤四：每只蚂蚁独立的根据概率公式选择下一步要到达的节点；

步骤五：分别判断每只蚂蚁在步骤四获得的下一步要到达的节点是否为指定输出节点，是则执行步骤六，否则返回步骤四；

步骤六：将完成路径选择的蚂蚁走过的路径作为待选择的路径；

步骤七：比较所有待选择的路径的节点数量，将节点数目最多的路径作为关键路径。

在上述步骤七之后还包括以下步骤：令迭代次数k的初始值为1，

步骤A：按照信息素更新规则更新信息素，将更新后的信息素分配到精英蚂蚁走过的路径上，重复步骤三至步骤七，并将获得的关键路径作为第r次迭代结果；

步骤B：将步骤A获得的第r次迭代结果中蚂蚁走过的节点数目与步骤七获得的关键路径中蚂蚁走过的节点数目进行比较，将节点数目多的路径作为当前备选结果；

步骤C：令r＝r+1，重复执行步骤A，将第r次迭代结果中蚂蚁走过的节点数目与当前备选结果中蚂蚁走过的节点数目进行比较，并将节点数目多的通路作为更新后的当前备选结果，并记录该结果；

步骤D：判断i的值是否大于2；是则执行步骤E；否则返回执行步骤C；

步骤E：判断相邻三次更新后的当前备选结果是否相同，是则将该更新后的当前备选结果作为最优关键路径，否则返回执行步骤C。

本发明所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法，首先对测试电路读入分析电路节点连接信息时的算法及存储数据的格式；然后对所要测试电路在读取连接信息的基础上转换为有向无环路图的形式；最后使用蚁群优化算法求解电路网络中的最长通路作为小时延缺陷的关键路径。在保证较高的正确率的前提下，加快了运行速度，以提高路径选择方法在实际应用的实用性。

附图说明

图1为基于蚁群优化算法的小时延缺陷测试关键路径选择方法的流程图。

具体实施方式

具体实施方式一：参照图1具体说明本实施方式，本实施方式所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法，它包括以下步骤：

步骤一：读取测试电路的节点在连接信息时的算法、数据存储方法和数据存储格式；

步骤二：将测试电路转换成有向无环拓扑图的形式，并将该有向无环拓扑图存储为邻接矩阵，然后将该邻接矩阵作为目标电路网络；

步骤三：利用蚁群优化算法将所有蚂蚁均放置在目标电路网络的输入节点处；

步骤四：每只蚂蚁独立的根据概率公式选择下一步要到达的节点；

步骤五：分别判断每只蚂蚁在步骤四获得的下一步要到达的节点是否为指定输出节点，是则执行步骤六，否则返回步骤四；

步骤六：将完成路径选择的蚂蚁走过的路径作为待选择的路径；

步骤七：比较所有待选择的路径的节点数量，将节点数目最多的路径作为关键路径。

本实施方式步骤一中，大规模电路在设计时常以verilog(一种硬件描述语言)形式进行表述。从测试电路，即电路网表中可以读取电路中逻辑门之间的相互连接关系。

步骤二中，有向无环路图以电路基本单元为图的顶点，以电路基本单元延时值为各边的权重，组合电路主要就是由各个逻辑门通过互联线连接组成，具有明显的点线结构特点，并且信号在电路中传递具有方向性，且输入到输出不存在环路，因而是典型的无回路有向图。图中的每条边则表示电路中逻辑门的互联关系，而边的方向则代表电路中信号的传输方向，图中每条边的权值代表逻辑门端口到端口时延和互连线的延时之和。

拓扑图是一种复杂的结构，具体表现在点与点之间复杂的逻辑关系。因此要选择合适的形式表示拓扑图，图的基本存储结构包括邻接矩阵、关联矩阵、边节点表(数组)、邻接表、十字链表等多种数据结构。这里我们选择邻接矩阵的结构，其优点是：分析过程清晰，容易实现，结构简单，适应性强，节点间关系明显。使用邻接矩阵对拓扑图进行存储时，邻接矩阵代表拓扑图中各个节点之间的连接关系。设G(V,E)是一个具有n个顶点的图，则图G的邻接矩阵是一个n×n的二维数组。设邻接矩阵用C表示，C＝[C_ij]_n×n，其中：

其中，i和j分别表示电路网络的节点。

以一个例子作为说明：

如下是一个C17门级描述电路的示例：

将C17转换成数值描述后，数值描述为每个逻辑门的数值描述，而将电路转换成有向无环拓扑图的形式时，每个逻辑门恰好代表拓扑网络中的节点，如{5,8,1,3}代表电路拓扑图中的节点1，{5,6,8,12}代表电路拓扑图中的节点5，则因为节点1的输出8与节点5的输入8相同，则节点1连入节点5，则电路拓扑图的邻接矩阵上第一行第5列为1。

在这个例子中，C17电路由逻辑门组成，通过对关键词的识别，读取逻辑门之间的连接关系。读取整个电路的骨架，并通过关键字input、output以及wire可以获取电路的输入引线数目、输出引线数目以及电路总的引线数目。通过改写可以将电路中的门级描述语句用向量表示出来。自定义的门级数值表述为如下表：

表1：自定义门级数值表

通过对表自定义门级表，并去掉多余部分，可以得到如阵列所示的数值表述形式，第一位表示门的类型，第二位表示电路的输出，后面的位数表示电路的输入，输入为几位即为几位。通过读入每一句数值就可以读出电路的门级结构了，如{5,8,1,3}表示G1和G3与非输出为G8和上面给出的第一句描述电路结构的语句是一致的。

使用蚁群优化算法时，实际上我们选择的是时延最大的通路。因为电路中时延主要产生在电子元器件中，为了建模方便，互联线中的时延可以被忽略，所以当以逻辑门作为蚁群优化算法中的节点时，两点之间没有具体的期望值。在电路中关键路径搜索问题中，蚂蚁不一定要走完所有的节点，每只蚂蚁所经过的点的数量是不确定的。蚂蚁从同一起点出发，通过不同的路径走到任意输出点。关键路径是指电路中特定输入输出间的最长路径，具体表现为包含最多逻辑门的路径。因此，选择关键路径，只需比较最后蚂蚁所走过点的数量。在每一步的选择时，不必考虑点和点之间的距离。

具体实施方式二：本实施方式是对具体实施方式一所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法作进一步限定，本实施方式中，步骤二所记载的将测试电路转换成有向无环拓扑图的形式的具体方法为：将测试电路在连接信息时的算法转换为有向无环路图的算法，将测试电路在连接信息时的数据存储方法转换为有向无环路图的数据存储方法，将测试电路在连接信息时的数据存储格式转换为有向无环路图的数据存储格式。

本实施方式中，将测试电路转换成有向无环拓扑图的形式进行存储，主要是通过对电路网表的数值描述后，确定逻辑门之间的相互连接关系，以邻接矩阵的数据结构进行存储。

具体实施方式三：本实施方式是对具体实施方式一所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法作进一步限定，本实施方式中，步骤四所述概率公式为：

$P_{\mathrm{ij}}^k\left(t\right)=\left\{\begin{array}{cc}\frac{{\left[{\mathrm{\τ}}_{\mathrm{ij}}\left(t\right)\right]}^{\mathrm{\α}}}{{\mathrm{\Σ}}_{u\∈J_K\left(i\right)}{\left[{\mathrm{\τ}}_{\mathrm{iu}}\left(t\right)\right]}^{\mathrm{\α}}}& j\∈J_k\left(i\right)\\ 0& j\∉J_k\left(i\right)\end{array}\right.$

其中，为t时刻蚂蚁k从点i转移到点j的概率，τ_ij(t)为t时刻点i和点j之间路径上的信息素强度，τ_iu(t)t时刻点i和所有能够与点i相连的点之间路径上的信息素强度，u为包含所有能够与点i相连的点的集合，J_k为蚂蚁k在i点处能够通向的点的集合，α为信息素强度的重要程度。

具体实施方式四：本实施方式是对具体实施方式一所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法作进一步限定，本实施方式中，步骤五中判断下一步要到达的节点是否为指定输出节点的方法为：

对目标电路网络中所有节点进行编号，设定输出节点的编号为A，判断蚂蚁当前所在节点的编号是否为A，是则该节点为输出节点。

具体实施方式五：本实施方式是对具体实施方式一所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法作进一步限定，本实施方式中，在步骤七之后还包括以下步骤：令迭代次数k的初始值为1，

步骤A：按照信息素更新规则更新信息素，将更新后的信息素分配到精英蚂蚁走过的路径上，重复步骤三至步骤七，并将获得的关键路径作为第r次迭代结果；

步骤B：将步骤A获得的第r次迭代结果中蚂蚁走过的节点数目与步骤七获得的关键路径中蚂蚁走过的节点数目进行比较，将节点数目多的路径作为当前备选结果；

步骤C：令r＝r+1，重复执行步骤A，将第r次迭代结果中蚂蚁走过的节点数目与当前备选结果中蚂蚁走过的节点数目进行比较，并将节点数目多的通路作为更新后的当前备选结果，并记录该结果；

步骤D：判断i的值是否大于2；是则执行步骤E；否则返回执行步骤C；

步骤E：判断相邻三次更新后的当前备选结果是否相同，是则将该更新后的当前备选结果作为最优关键路径，否则返回执行步骤C。

在蚁群优化算法中既要保证其搜索空间足够大，以尽可能大的寻找最优解的解区间，又要保证蚁群间信息的充分交流以较大概率通过信息正反馈机制获得最优解。因而蚁群算法中的参数设置对算法的收敛性、性能和效率均具有很大影响。蚁群算法中有6个重要的参数，分别是：最大迭代次数、重复跳出次数、蚂蚁数目、启发因子、挥发度和信息素量，其中最大迭代次数和重复跳出次数是一对组合参数，需要同时考虑。通过对蚁群算法进行实验调整，确定各个参数的量。实际实验时，每次运行蚁群算法30次，实验对象是中大规模组合电路c1355转换后的邻接矩阵，该邻接矩阵为一个546×546的矩阵，定义问题规模vexnum＝546。每运行一次得到一组路径长度l_x和运行时间t_x，其中x为运行次数。对比在DFS算法(深度优先算法)中得到的最长路径长度l，得到在该参数下蚁群算法的偏差值d、平均运行时间t和效率值p：

$d=\frac{{(l_1-1)}^2+{(l_2-1)}^2+...+{(l_{30}-1)}^2}{30}$

$t=\frac{t_1+t_2+...+t_{30}}{30}$

$p=\frac{e^{-d}}{t^2}$

其中，效率值p被定义成与平均运行时间t的负2次相关，设置的最佳参数配置为：最大迭代次数NC_Max＝10，重复跳出次数NC_Flag＝4，启发因子α＝1，蚂蚁数目M＝vexnum/2，挥发度ρ＝0.6，信息素总量Q＝vexnum/100，e为即常用指数函数计算中的自然对数，取值为2.7182818245。

具体实施方式六：本实施方式是对具体实施方式五所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法作进一步限定，本实施方式中，步骤A所述的信息素更新规则为带精英策略的信息素更新规则，表达方式如下：

其中，为t时刻蚂蚁k点i和点j之间路径上的信息素增量，Q为蚂蚁k在完成旅行时，经过路径上释放的信息素总量，L_k为蚂蚁k在这次旅程中所走路径长度。

信息素更新规则是根据问题的目标规定的，因为那决定了算法的正反馈作用的强弱和优化速度的快慢。在关键路径搜索问题中，新增信息素应该分配到长路径上。而需要寻找的关键路径是从输入到输出的最长路径，也就是全局最优解。本实施方式从每次迭代的所有符合输出点要求的蚂蚁中，选择一只结果最好的蚂蚁，作为这一代的精英蚂蚁，这有些类似于遗传算法中的精英策略。所有新增信息素按照如上公式只分配到这只精英蚂蚁所走的路上，同时所有路径上的信息素浓度都按照信息素挥发系数而减少。

具体实施方式七：本实施方式是对具体实施方式五所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法作进一步限定，本实施方式中，步骤A中，在更新信息素的同时，按信息素挥发系数减少每次迭代的信息素浓度。

本实施方式中所述的信息素挥发系数取值为0.2。

Claims (7)

1.基于蚁群优化算法的小时延缺陷测试关键路径选择方法，其特征在于，它包括以下步骤：

步骤一：读取测试电路的节点在连接信息时的算法、数据存储方法和数据存储格式；

步骤二：将测试电路转换成有向无环拓扑图的形式，并将该有向无环拓扑图存储为邻接矩阵，然后将该邻接矩阵作为目标电路网络；

步骤三：利用蚁群优化算法将所有蚂蚁均放置在目标电路网络的输入节点处；

步骤四：每只蚂蚁独立的根据概率公式选择下一步要到达的节点；

步骤五：分别判断每只蚂蚁在步骤四获得的下一步要到达的节点是否为指定输出节点，是则执行步骤六，否则返回步骤四；

步骤六：将完成路径选择的蚂蚁走过的路径作为待选择的路径；

步骤七：比较所有待选择的路径的节点数量，将节点数目最多的路径作为关键路径。

2.根据权利要求1所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法，其特征在于，步骤二所记载的将测试电路转换成有向无环拓扑图的形式的具体方法为：将测试电路在连接信息时的算法转换为有向无环路图的算法，将测试电路在连接信息时的数据存储方法转换为有向无环路图的数据存储方法，将测试电路在连接信息时的数据存储格式转换为有向无环路图的数据存储格式。

3.根据权利要求1所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法，其特征在于，步骤四所述概率公式为：

$P_{\mathrm{ij}}^k\left(t\right)=\left\{\begin{array}{cc}\frac{{\left[{\mathrm{\τ}}_{\mathrm{ij}}\left(t\right)\right]}^{\mathrm{\α}}}{{\mathrm{\Σ}}_{u\∈J_k\left(i\right)}{\left[{\mathrm{\τ}}_{\mathrm{iu}}\left(t\right)\right]}^{\mathrm{\α}}}& j\∈J_k\left(i\right)\\ 0& j\∉J_k\left(i\right)\end{array}\right.$

其中，为t时刻蚂蚁k从点i转移到点j的概率，τ_ij(t)为t时刻点i和点j之间路径上的信息素强度，τ_iu(t)t时刻点i和所有能够与点i相连的点之间路径上的信息素强度，u为包含所有能够与点i相连的点的集合，J_k为蚂蚁k在i点处能够通向的点的集合，α为信息素强度的重要程度。

4.根据权利要求1所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法，其特征在于，步骤五中判断下一步要到达的节点是否为指定输出节点的方法为：

对目标电路网络中所有节点进行编号，设定输出节点的编号为A，判断蚂蚁当前所在节点的编号是否为A，是则该节点为输出节点。

5.根据权利要求1所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法，其特征在于，在步骤七之后还包括以下步骤：令迭代次数k的初始值为1，

步骤A：按照信息素更新规则更新信息素，将更新后的信息素分配到精英蚂蚁走过的路径上，重复步骤三至步骤七，并将获得的关键路径作为第r次迭代结果；

步骤B：将步骤A获得的第r次迭代结果中蚂蚁走过的节点数目与步骤七获得的关键路径中蚂蚁走过的节点数目进行比较，将节点数目多的路径作为当前备选结果；

步骤C：令r＝r+1，重复执行步骤A，将第r次迭代结果中蚂蚁走过的节点数目与当前备选结果中蚂蚁走过的节点数目进行比较，并将节点数目多的通路作为更新后的当前备选结果，并记录该结果；

步骤D：判断i的值是否大于2；是则执行步骤E；否则返回执行步骤C；

步骤E：判断相邻三次更新后的当前备选结果是否相同，是则将该更新后的当前备选结果作为最优关键路径，否则返回执行步骤C。

6.根据权利要求5所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法，其特征在于，步骤A所述的信息素更新规则为带精英策略的信息素更新规则，表达方式如下：

其中，为t时刻蚂蚁k点i和点j之间路径上的信息素增量，Q为蚂蚁k在完成旅行时，经过路径上释放的信息素总量，L_k表示蚂蚁k在这次旅程中所走路径长度。

7.根据权利要求5所述的基于蚁群优化算法的小时延缺陷测试关键路径选择方法，其特征在于，步骤A中，在更新信息素的同时，按信息素挥发系数减少每次迭代的信息素浓度。