基于云进化算法的NoC测试规划

侯绪彬

(桂林电子科技大学 电子工程与自动化学院，广西 桂林541004)

随着片上系统(System－on－Chip，SoC)集成度越来越高，如何保证IP核之间快速高效的通信已经成为阻碍SoC发展的新瓶颈［1］。于是一种以通信为核心的复杂SoC的IP核的集成方法，即片上网络(Networkon－Chip，NoC)被提出。NoC采用基于包交换的方法和分层传输方法来替代原先的传统总线［2］，从体系结构上有效解决了多核通信问题。

在NoC测试过程中，往往用多条TAM(Test Access Mechanism，测试访问机制)进行并行测试。但为了防止功耗过大损坏芯片，必须限制并行测试的TAM的条数，控制测试功耗［3］。如何在一定功耗限制下，将IP核合理地分配到各条TAM上，优化测试时间，是NoC测试中的一个重要课题。

文中利用基于云模型的进化算法对NoC调度规划问题进行了研究，使得在功耗限制下优化NoC的测试时间。

1 NoC测试调度问题

1.1 基于NoC重用的测试访问机制

在SoC测试中，测试向量通过TAM进行传输［4］。而在NoC系统中，重用NoC系统中的路由(Router)和通道(Channel)等资源作为TAM，不仅能够避免增加额外的硬件开销，还能有效提高测试效率［5］。

1.2 NoC并行测试

在文中，采用XY路由方式，在测试过程中采用非抢占式测试机制。具体的测试流程为［6］:外部测试设备ATE通过I/O端口连接到NoC，测试向量通过input端口输入到网络中，通过路由输送到待测IP核中;测试响应同样通过路由输送到output端口，被外部测试响应分析机制接收:这样就完成了一个IP核的测试。图2给出了d695中对8号和6号IP核进行并行测试时的测试路径。

1.3 NOC测试规划问题描述

在NoC测试中，如何在众多IP核的分配方案中寻找最优方案，是NoC调度规划的关键。如图2所示，将10个待测IP核，按照A、B两种规划调度方式分别分配到3条TAM上进行测试，B种调度方式的测试时间T2＜A种调度方式的测试时间T1。任务是在众多调度方案中找到最优方案，使测试时间最短。

图1 d695上两条TAM并行测试

图2 NoC测试规划

2 功耗约束下NoC测试规划数学模型

假设在一个NoC中，有a条TAM，TAMj上有k个待测IP核，第i号待测IP核测试时间为Ti，则TAMj的测试时间为

则NoC总的测试时间为测试时间最长的那条TAM的测试时间

NoC的测试功耗为当前所有TAM上功耗的总和

3 基于云进化算法的测试规划

基于云模型的进化算法利用云模型C(Ex，En，He)描述进化过程［7－8］，其中Ex成为优良种子个体;En成为进化熵;He成为进化超熵。Ex正态云发生器产生下一代云滴。

3.1 算法编码

根据IP核在TAM上的分配编码，如图1(b)所示，可以得到此个体的编码为010202101，表示编号为3、9、5、1的IP核在0号的TAM上;编号为2、7、8、10的IP核在1号TAM上;编号为6、4的IP核在2号的TAM上。

3.2 算法实现

算法包括以下步骤:初始化种群、适应度值计算、个体更新和终止判断。

(1)初始化种群。对于一个有N个待测IP核的NoC系统。随机生成一个N位的整数代码串，表示各待测IP核在TAM上的分配方式。

(2)适应值计算。分析种群中每个个体的染色体信息，通过式(2)计算方案的测试时间作为此个体的适应值。选取当代个体中适应度值最优的n_s个个体作为种子，利用种子进化生成新一代个体。

(3)个体更新。分为进化和变异两部分。

图3 算法流程图

种群进化采用云进化策略和自然进化策略相结合的方法。

云进化策略指利用n_s个种子，运用一维正向云发生器产生新一代个体。将种子个体的代码串如0102021021作为一个整数，此整数即为正态云期望Ex;Ex的取值范围ε≥(a－1)×109(a为TAM个数)，令En=ε/6;He=En/c2，c2一般取5～15之间的整数［9］，根据实验数据比较分析，取c2=10时算法具有较好的收敛性。

当连续φ1代出现跨代精英时，算法可能找到了新的极值领域或更加逼近原有极值领域，这时令减小En和He的值降低算法搜索范围，并提高搜索精度。输入数字特征值Ex、En、He，产生nc个云滴。

自然进化策略是指采用轮盘赌的方式，随机选择种子个体进行交叉变异，生成新个体。

假设算法的连续平凡带数为λ，阈值为λ1、λ2和λ3(λ1＜λ2＜λ3)。当λ＜λ1时，只采用云进化策略更新个体;当λ＞λ1时，云进化策略和自然进化策略联合更新个体，其中云进化策略更新nc个新个体，自然进化策略更新ne个新个体，k=ne/nc。当λ＞λ2时，增大k以提高自然进化算法生成新个体的数目;同时提高En、He，增大搜索范围。当λ＞λ3时，对部分种子个体进行变异操作。若最大迭代次数为λmax，本文取λ1=λmax/10，λ2=2λ1，λ3=5λ1时，算法的效率较高。

变异操作针对种子个体进行。针对适应度值最好的前h个种子个体的编码串，逐位求平均数然后4舍5入取整，作为新的种子。

(4)终止判断。如果进化代数达到最大的迭代次数，或达到进化最大平凡代数，则终止迭代输出结果;否则转到步骤(2)。

4 结果及分析

文中采用ITC'02 SoC标准电路中的d695电路作为实验对象，其作为3×4网格结构的NoC系统，有10个待测IP核。测试的基准时钟为fT=1 GHz，限制功耗设置为测试总功耗的50%。实验环境为:Intel(R)(CoreTM)－2410M i5 2.3 GHz CPU，4 GB内存;程序源代码通过C++语言编写，并在VC 6.0上编译运行，其中正向云发生器用Matlab 7.0的MCC方式与VC混编实现，程序在Windows XP操作系统下运行。

表1 d695单时钟最佳测试规划方案

实验分别对NoC系统上有2条、3条和4条TAM进行测试，且有功耗限制和无功耗限制两种情况。并将得到的测试数据和文献［10］中基准测试数据作比较。文献［10］将待测IP核按照测试时间进行排序后，根据资源空闲和功耗约束，将IP核依次分配到各TAM上，属于传统的测试规划方案。二者对d695电路的测试数据比较如表1所示。

通过表中数据可以看出，当TAM的数量增多时，由于并行测试IP核的数量增加，相应的总测试时间是逐渐降低的;相比于无功耗限制和50%功耗限制两种情况，无功耗限制时的测试时间更小。

对比本文中的测试方法和文献［10］的基准测试数据可以发现，应用云进化算法的应用明显提高了测试效率，其中最大的优化幅度达到了28.8%。

由以上测试数据可得，由于云进化算法拥有搜索范围大且收敛快的特点，将其运用到测试规划中，相对比与传统的测试规划方案能够有效地降低测试时间，提高了测试的效率。

5 结束语

文中在功耗限制下对NoC中待测IP核的测试进行规划。在2D网格结构下，重用NoC的路由和通道作TAM进行测试，并用XY路由方式选择测试路径，运用云进化算法对待测IP核在TAM上分配方式进行寻优。实验结果表明，通过本文设计的方法所得到的测试方案能有效降低测试时间，提高NoC系统待测IP核并行测试的效率。

［1］DALLY W，TOWLES B.Router packets，not wires:on－chip interconnection networks［C］.Las Vegas，NV:Proc.The Design Automation Conference，2001:684－689.

［2］ 谭耀东，刘有耀.NoC系统研究综述［J］.西安邮电学院学报，2008，13(1):5－9.

［3］ 许川佩，姚芬，胡聪.基于云进化算法的NoC资源节点优化测试研究［J］.电子测量与仪器学报，2012，26(3):192－196.

［4］ 许川佩，胡红波.基于量子粒子群算法的SoC测试调度研究［J］.仪器仪表学报，2011，32(1):113－119.

［5］LIU Chunsheng，LINK Z，PRADHAN D K.Reuse－based test access and integrated test scheduling for network－onchip［J］.Computer Science，2006(2):90－95.

［6］ 欧阳一鸣，张岚，梁华国.一种时间优化的NoC低功耗测试调度方法［J］.中国科学技术大学学报，2010，40(5):540－545.

［7］ 叶琼，李绍稳，张友华，等.云模型及应用综述［J］.计算基础工程与设计，2011，32(12):4198－4201.

［8］ 张光卫，何锐，刘禹，等.基于云模型的进化算法［J］.计算机学报，2008，31(7):1082－1091.

［9］ 许川佩，覃上洲.基于云子粒子群算法的SoC测试规划研究［J］.桂林电子科技大学学报，2010，30(5):463－468.

［10］COTA E，LIU CH SH.Constraint－driven test scheduling for noc－based systems［J］.IEEE Transactions on Computer－Aided Design of Integrated Circuits and Systems，2006，25(11):2465－2478.