基于NSGA-II算法的IP核测试优化研究

黄俊

（湖南铁道职业技术学院 湖南 株洲 412001）

基于NSGA-II算法的IP核测试优化研究

黄俊

（湖南铁道职业技术学院 湖南 株洲 412001）

IP核集成化的SoC测试，测试时间与测试功耗是两个相互影响的因素。多目标进化算法能够处理相互制约的多目标优化问题。在无约束条件下，对IP核的测试时间与测试功耗建立联合优化模型，并采用多目标进化算法中的改进型非劣分类遗传算法（Non-dominated Sorting Genetic Algorithm II，NSGA-II）对模型进行求解。通过应用ITC'02标准电路中的h953做应用验证，结果表明该方法能够给出模型的均衡解，证明了模型的实用性和有效性。

NSGA-II算法；IP核；测试时间；测试功耗

当今，复杂的SoC芯片由大量结构功能复杂的IP核构成，而且其设计采用了新的工艺技术。在整个芯片产品的开发设计过程中，为了提高芯片系统的优良率及可靠性，SoC的测试技术成为了必要的研究课题[1-3]。在基于IP核的SoC测试调度的研究中，为了整个芯片的安全性，功耗问题必须要考虑。对于SoC测试时间与测试功耗的协同优化研究，也是在将测试功耗作为约束条件下，考察测试时间的优化问题[4-7]。

文中在无测试时间及测试功耗的约束限制条件下，建立IP核测试时间与测试功耗的联合优化模型，研究NSGA-II算法实现过程，将NSGA-II算法应用到SoC的测试优化模型中，最后采用ITC’02 Benchmark中的h953电路来进行算法验证，并给出优化结果[8-13]。

1 IP核测试的多目标优化问题的描述

对基于IP核的SoC总测试时间及总测试功耗的优化问题可以转化为：对于给定的SoC，包含N个IP核，在SoC的测试过程中，每个IP核有测试和空闲两个状态，那么总共有2N个测试方案，这是典型的NP 问题[14-15]。

1）最小化SoC的整体测试时间，其表达式为：

Tj（1≤j≤N）表示每个 IP 核的测试时间，xij（1≤j≤N）表示每个IP核的状态，IP核j为测试状态时，xij=1；或者IP核j为空闲状态时，xij=0。在2N个测试方案中，至少存在一种方案使式（1）中的目标函数值F1取得最小值，即获得SoC最短的测试时间。

2）在IP核的并串测试方式内，瞬时的SoC总测试功耗表示为：

其中Pj为测试IP核j所需功耗；xij同上。Pi为SoC测试时的总功耗。在2N个测试方案中，至少存在一种方案使式（2）中的F2取得最小值，即获得SoC最小的测试功耗。

3）此外，还需要满足以下约束条件：

即所有的IP核分k组测试完，并且各组之间测试的IP核不会重复测试。式中i、j、k和xij取值相同于式（1）。

2 基于NSGA-II算法的IP核的测试时间与测试功耗的优化

文中综合考虑测试时间和测试功耗，从中找到IP核测试的最优解。NSGA-II算法是多目标进化算法的一种，多目标进化算法主要解决多目标联合优化问题，可以不受决策者的预先偏好信息的影响，对于建立的多目标值数学模型，给出结果是一组均衡解，即Pareto最优解。

2.1 算法主要流程

图1所示内容为非支配排序进化算法 （NSGAII）的主要运算流程。

图1 NSGA-II算法的流程图

2.2 IP核测试分配问题的算法实现过程

通过MATLAB编程实现NSGA-II算法及求解本文建立的数学模型，程序实现NSGA-II算法的代码文件调用流程如图2所示，包含以下10项：

1）父代种群初始化：initialize_variables.m

主要对初始父代种群Po的个体随机初始化。根据算法初始设置种群个体数N，随机初始化每个个体。对于单个染色体的编码初始化，设定染色体长度L，限定染色体编码值的范围，并生成染色体的编码值。

用MATLAB编程，随机生成一个N×L阶的矩阵P，其中，矩阵的每一行为一条染色体编码。此外，本文建立的模型所要求解的目标函数有2个，将矩阵P扩展为N×（L+2）阶的矩阵P'，后2列存储各染色体对应的2个目标函数值。

2）确定目标函数值：evaluate_objective.m

该文件根据建立的数学模型，确定目标函数的个数及各目标函数的具体表达式。对于给定的每条染色体，计算出其目标函数值。应用到本文模型求解中，就是计算出每条染色体的2个目标函数值，存储在矩阵P'的后两列中。

图2 NSGA-II算法的代码文件调用流程图

3）输入初始数据：input_data.m

该文件代码用于对优化对象原始数据的输入。包括IP核的个数，特定TAM总线宽度下各个IP核的测试时间数据矩阵，及测试功耗数据矩阵。

4）目标函数值非支配排序：non_domination_sort_mod.m

非支配排序文件是NSGA-II算法的核心部分。其对当前种群所有个体的目标函数值进行非支配排序，设定相应个体非支配的等级。调整矩阵P'中每个个体的排列顺序，将个体及其相应的目标函数值按等级从高到低进行排序，同时将矩阵P'扩展成P″，增加第L+3列存储所有个体的非支配等级值。

5）目标函数值拥挤度计算：crowding_distance.m

该文件完成对当前种群的各排序前端的个体设定拥挤度值。并将矩阵P″扩展，增加第L+4列存储各个体的拥挤度值。拥挤度值为种群个体选择做准备。

6）锦标赛选择：tournament_selection.m

该文件用来完成对当前种群个体的选择，其中的竞赛规模设置为2，选择操作进行遵循锦标赛选择规则。

7）交叉操作：crossover_operator.m

对进行选择后的种群个体染色体交叉，并且设置交叉概率Pc的参数值。

8）变异操作：mutation_operator.m

对进行选择和交叉操作后的种群个体染色体变异，并且设置变异概率Pm的参数值。

9）种群更新：replace_chromosome.m

种群更新的作用即为精英保留策略。对父代种群Pt和子代种群Qt合并后得新种群Rt，参照非支配排序等级及拥挤度值，选择N个优良个体作为新种群。对于矩阵P″来说，种群更新参考其第L+3列非支配等级值和第L+4列拥挤度值。

10）NSGA-II算法主函数：nsga2_main.m

完成对其他子程序文件（1）-（9）的调用，设置种群个体数N和算法进化代数gen。此外，精英保留策略中的父代与子代种群合并的操作在主文件中完成。

3 IP核测试分配问题的应用实例及结果分析

文中采用的NSGA-II算法对IP核测试分配，以期获得IP核测试时间与测试功耗的联合优化。为了对算法做出验证并且使算法具有普遍应用性，采用国际标准SoC电路ITC’02 SoC Test Benchmark[4]来进行分析，在ITC’02各个SoC中，h953具有测试功耗的信息，可以作为应用实例来进行研究。h953的相关信息如表1所示。

表1 h953的测试数据

表1中第一列是h953中各个IP模块的名字。第二列是各模块的原始输入输出端口总数，第三列是各个模块的测试矢量数，第四列是各个模块的内部扫描链数量。其中，符号“-”表示没有扫描链，即组合逻辑模块。第五和第六列分别表示各模块中最短和最长扫描链长度。第七列是各模块在测试状态下的功耗值。

本文的验证条件为，对于给定的测试电路h953有8个IP模块，为了计算方便，将各个IP模块的测试功耗值取整表示：h953_test_time=[119357，3279，1319，2194，14094，34585，1373，120869]；h953_test_power=[56586，575380，590，332，1788，204252，14208，302520]；设测试时间的单位为 μs，测试功耗的单位为mW。对于NSGA-II算法的参数，考虑h953基准电路中包含8个IP核，文章设定初始种群个体数为80；遗传操作中的交叉概率Pc=0.9，变异概率Pm=0.1；锦标赛选择规模参数设置为2；设算法运行代数为50代。经过运算后得到一组最佳测试方案解。Pareto最优解，F1和F2分别为h953测试方案优化后测试时间与测试功耗的目标函数值。对于h953内部所有IP模块，编码1表示分4组进行测试：

表2 Pareto编码集及目标函数值

第1组：{Module1、Module4、Module5、Module6、Module8}；

第2组：{Module2}；

第3组：{Module3}；

第4组：{Module7}；

此方案的测试时间与测试功耗分别为575 386 μs，126 788 mW。

编码2表示分2组进行测试：

第1组：{Module1、Module5、Module6、Module8}；

第2组：{Module2、Module3、Module4、Module7}；

此方案的测试时间与测试功耗分别为590 498 μs，124 150 mW。

编码3表示分3组进行测试：

第1组：{Module1、Module2、Module4、Module5、Module6、Module8}；

第2组：{Module3}；

第3组：{Module7}；

此方案的测试时间与测试功耗分别为1140912μs，123 573 mW。

编码4表示对于分4组进行测试：

第1组：{Module1、Module5、Module6、Module8}；

第2组：{Module2、Module4}；

第3组：{Module3}；

第4组：{Module7}；

此方案的测试时间与测试功耗分别为575 680 μs，125 503 mW。

表2中我们可以看到，经过优化后获得的目标函数值具有多样性，而在实际测试应用中，可以根据测试功耗或测试时间的限制来选择不同测试方案。同样的，根据表2所示数据，我们可以考虑在功耗约束下，测试时间的最优解。将表2中F2作为约束条件，功耗约束强时，测试时间相应长，功耗约束弱时，测试时间相应短，这验证了测试时间及测试功耗的相互制约性。

4 结 论

文中介绍了一种基于NSGA-II算法的IP核测试优化方案，对于不同的功耗及时间要求，均可采用本文提出的方法获得一组Pareto解集，根据实际需求选择不同的解方案，验证了此方案的实用性和可行性。

[1]汪滢，许东宁.SoC测试时间与测试功耗协同优化[J].微计算机信息，2009（32）:27-29.

[2]张建胜.变长重复播种BIST和SoC测试[D].上海:复旦大学，2007:36-54.

[3]王小平，曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社，2002.

[4]E.J.Marinissen,V.Iyengar,K.Chakrabarty.ITC’02 SOC Test Benchmarks[EB/OL].http://itc02socbenchm.pratt.duke.edu/.2008.

[5]解光军，肖晗.基于遗传算法的运算放大器建模与自动设计 [J].电子测量与仪器学报，2009，23（1）：91-95.

[6]林峰.SoC测试功耗优化技术研究 [D].上海:上海大学，2009.

[7]孔民秀，陈琳，杜志江，等.基于NSGA_II算法的平面并联机构动态性能多目标优化 [J].机器人，2010，32（2）:271-275.

[8]朱国俊.基于NSGA_II算法的轴流式叶片优化设计[D].西安:西安理工大学，2009.

[9]冷冰，谈恩民.基于IEEE1500标准的IP核内建自测试设计[J].国外电子测量技术，2015，34（9）:75-79.

[10]贺显龙，雷加．层次型IP核测试环单元的设计[J].国外电子测量技术，2010，29（5）:56-59.

[11]朱敏，杨春玲，孔德晶．模拟电路内建自测试故障特征提取与优化[J]．仪器仪表学报，2013，34（1）:200-207.

[12]赵丽丽，谈恩民，王海超 ．优化SOC测试时间的扫描链平衡 及NSGA-ll设 计 [J].国外电子测量技术，2014，33（7）:32-35.

[13]乔立岩，向刚，俞洋，等．基于IEEE 1500标准的IP核测试壳设计[J]．电子测量技术，2010，33（7）:88-91.

[14]许川佩.带分复用的三维片上网络测试规划研究[J]．仪器仪表学报，2015，36（9）:2120-2127.

[15]欧阳一鸣，贺超，梁华国，等．NoC架构下异构 IP核的并行测试方法 [J]．电子学报，2013，41（12）:2391-2396.

Optimization of IP cores test based on NSGA-II algorithm

HUANG Jun
（Hunan Railway Professional Technology College，Zhuzhou 412001，China）

In the test of SoC integrated IP cores，test time and test power were in the restrict condition to each other.The multi-objective evolutionary algorithm can achieve the simultaneous optimization.The paper constructed the combined optimization model for IP cores'test time and test power under no constraining，applied NSGA-II to deal with the combined optimization model，and adopted ITC'02 Benchmark circuit h953 to verify the algorithm.The results show that the NSGA-II algorithm can generate balance solutions，and the test model is practical and effective.

NSGA-II； IP cores； test time； test power

TN108

A

1674－6236（2017）17-0058-04

2016-07-30稿件编号：201607218

黄 俊（1969—），男，湖南株洲人，硕士，讲师。研究方向：控制系统与控制理论、电气工程。