基于改进遗传算法的3D NoC测试优化

凌景 唐静

（巢湖学院，安徽 巢湖 238000）

1 引言

随着半导体集成技术和制造工艺的不断发展，片上网络（Network-On-Chip，NoC）技术作为一种新型体系结构解决了SoC总线通信的局限性[1]，而三维片上网络（three dimensional network-on-chip，3DNoC）的出现解决了2D NoC全局连线过长、连线延迟和功耗开销等问题，逐渐成为NoC发展的主流[2]。3D NoC的测试随着IP核集成时不断增加的种类和数量变得愈来愈重要，随着芯片集成复杂度的提高同时也愈来愈困难，因此，3D NoC发展的瓶颈之一是怎样实现高效的测试调度。

目前对3D NoC测试调度的研究主要集中在优化算法和优化策略上，文献[3]利用遗传算法将系统中的待测核分配到各个测试端口，实验结果表明，该方法可减小测试时间，但在测试过程中未考虑到测试端口的位置。文献[4]采用Kernighan-Lin算法实现对TSV位置的合理选择，该方法有助于3D设计实现，但没有权衡对系统性能的影响。文献[5]采用粒子群算法对3D NoC TSV数量和位置进行协同优化，实验结果表明，该方法可提高TSV的利用率，完成TSV位置的寻优。

本文结合3D NoC通过路由传输数据的特点，重用NoC作为TAM，并将TAM动态划分的带分复用和并行测试的策略。将遗传算法和云模型相结合，以测试时间为目标函数，对分配到测试端口上的IP核进行调度，寻优最佳调度方案。

2 3D NoC测试调度

2.1 测试策略

本文进行测试调度研究的NoC为规则的3D Mesh结构，图1所示为其体系结构，资源结点、路由结点和通信链路是主要组成部分[6]，其中水平方向的互连线和垂直方向的硅通孔组成了通信链路。资源结点主要用来完成系统计算任务，又称为资源内核或IP核；NoC核与核之间的数据传输主要是通过路由节点进行数据的存储和转发，这是与SoC通过总线来实现数据传输本质上的区别；IP核和路由节点之间的数据传输通过资源网络接口实现[7]。3D NoC片上丰富的资源为并行测试提供了硬件支持，为减小并行测试时的硬件开销，本文重用NoC作为TAM，即重复使用路由节点、互连线和TSV完成测试。

图1 3D Mesh NoC结构图

2.2 测试调度模型

在测试过程中，采用xyz路由算法，即一旦给核分配了TAM带宽和I/O端口，便确定了核的测试路径，以图1为例，核的测试过程如下：若核8的测试矢量从源节点核1开始出发，根据设定的路由算法，先沿X方向传输，到达与Core8 X坐标相同的Core2路由节点后，由于Core2和Core8两路由节点Y坐标相同，测试矢量不需沿Y方向传输，直接沿Z方向传输到达待测核，测试完成后，测试矢量按照同样的传输算法到达目的节点Core6，此时对Core8的测试结束。Core8总的测试时间包括传输测试矢量的时间和测试Core8所用的时间。

本文采用带分复用的方法对3D NoC测试规划，使同一时刻IP核的多个测试数据共享同一TAM并行传输[8]，若core的测试顺序调度不合理，则有可能产生路径冲突，影响系统总调度时间和功耗。如图2所示，图2（a）是未使用带分复用的规划结果，最后的测试时间为Ta；图2（b）是使用带分复用的规划结果，最后的测试时间为Tb，Ta要远远大于Tb，可见方案（b）要优于方案（a）。相比以往一条TAM被单个IP核测试数据独占进行传输，资源利用率和并行测试的效率因带分复用提高了[9]。描述文中的测试调度问题为：如何无冲突地调度个待测核core，在带宽允许的条件下，使系统整体测试时间最小。

图2 3D NoC测试调度结果

2.3 目标函数以及TAM约束函数

2.3.1 测试时间

在图2中的每个测试节点更新待测核时，测试结束时间最大的核决定了系统总测试时间，即T ＝ max（Tend（corei）），i≤1≤N。其中，核的总数为 N，corei测试结束时间 Tend（corei）包括 corei开始测试的时间与测试corei的总时间。corei前一个核的结束测试时间决定了该核开始测试时间，核传输测试矢量的时间 Ttr和测试核的时间 Ttc为 corei测试总时间 Ttest（corei），即 Ttest（corei） =Ttr+Ttc。

文中对核进行测试的测试矢量是通过测试数据包在各个路由节点间传输，当第一个测试数据包传输到被测核时开始对核进行测试，余下的测试数据包相继传入网络，此时对核进行测试的时间包括了测试数据包的传输时间。因此，第一个测试数据包从源节点传输到被测核的时间Tpacket（first）和最后一个测试数据包从被测核传输到目的节点的时间Tpacket（last）为测试数据包传输总时间，即Ttr=nhopi·Tpacket（first）＋nhop0·Tpacket（last）。其中，nhopi是第一个测试数据包传输到被测核所经过的路由跳数，nhop0是最后一个测试数据包从被测核传输到目的节点所经过的路由跳数。文中各路由节点用三维坐标表示，设待测核的坐标为（xc，yc，zc），源节点的坐标为（xi，yi，zi），目的节点的坐标为（xo，yo，zo）。则：

2.3.2 TAM约束函数

当TAMj上核i开始测试时，该核测试数据传输带宽Wcoreij的分配必须满足：其中，每条TAM总带宽为WTAM，文中TAM的测试方法采用重用NoC，因此每条TAM总带宽固定且相等。为TAMj上所有在测核占用的带宽之和。

3 改进遗传算法的3D NoC测试优化研究

3.1 3D NoC测试调度编码设计

文中将核分配到实施带分复用的TAM上，不同的分配方案使得最后调度的结果不同，即核的测试数据包在TAM上传输顺序决定了最终的测试时间。本文以规模为M×N×L、TAM的条数为B的3D NoC为例，为了体现每个核的特征，本文采用的编码方法如下：

3.2 个体、基因

上文中的S即是完成所有核测试的一种调度方案被称为个体，基因则是组成个体的各元素，基因的特征用S中的子矩阵Gbj中的元素表示。不同的基因在不同的测试节点表现出的特征不同，进而使得个体特征不同。本文中基因表示核的标号，利用云模型更新所选个体非0基因即有效基因。若新生成的子代中最优个体的适应度比父代差，则当代的种子仍然取父代个体。

3.3 算法流程

遗传算法借用了仿真生物遗传学和自然选择机理，通过遗传、变异等机制寻找最优个体，但仅仅通过交叉变异实现个体的更新，寻优精度不高，容易陷入局部最优。本文优化测试调度采用结合了云模型的改进遗传算法，利用云模型在进化初期更新个体，当调节云模型参数时无法寻优到更优秀的个体，实施遗传算法的交叉变异、个体之间竞争等策略继续寻优，直至达到最大迭次数。云模型特征如图3，其数字特征用期望Ex、熵En和超熵He三个参数表示。将优秀个体作为云模型更新时的Ex，进化过程中物种变异的范围可用En表示，进化过程中的稳定性可用He表示[9-10]。

图3 云模型特征图

将云模型与进化算法相结合，算法主要流程如图4，包括：种群初始化、适应度值计算、云模型更新个体、云进化算法自适应调整、遗传算法更新策略、种群间个体竞争。

图4 算法流程图

3.3.1 云模型更新个体 从初始种群中选取适应度值最优的个体，将该个体的基因作为云模型的期望值，初始的熵取值为 e／c1，超熵取值为 En／c2，c1、c2为控制系数，C1初始值取 1，C2初始值取 10，e 为待测核编号范围。生成云滴的过程如下。

输入：Ex、En和 He，n% 数字特征和云滴数

若云模型更新过程中连续多代都出现了适应性最强的个体，此时的进化过程有可能逼近了原极值领域或者找到了新极值领域，此时需减小搜索半径和增大搜索稳定度[11]，可通过减小En和He来实现，达到局部求精的目的。若经过多代更新都没有更优的个体出现时，进化过程此时有可能陷入局部最优，可通过提高En和He扩大搜索半径和减小搜索稳定度以达到局部求变和寻找全局最优的目的[12-13]。

3.3.2 遗传算法更新策略 当经过若干代都没有更优秀的个体出现时，此时对种群引入遗传算法进行更新。文中采用轮盘赌产生0～1的随机概率p，根据实际情况设定p1、p2的值。当0≤p≤p1时进行自交，当p1≤p≤p2时进行杂交，当p2≤p＜1时进行变异。

3.3.3 种群间个体竞争 为加强种群间的个体交流进而有效避免算法陷入局部最优，本文设计如下的竞争机制，主要过程为：两两比较从每个种群中挑选出的d个优秀个体，以适应度值为评判标准，适应度值高者在比较中获得胜利，种群i中的优秀个体j的胜负次数分别用uij、vij（1≤i≤2，1≤j≤d）表示。经 d2次比较后，计算每个个体的胜、负次数差值△ij=uij-vij，1≤i≤2，1≤j≤d，若△ij＜ 0，则淘汰种群i中的个体j，淘汰的个体j用随机生成新个体代替。图5中以每个种群选出3个个体为例进行说明u11=2，v11=1，△11=1，u12=0，v12=3，△12=-3，u13=3，v13=0，△13=3，u21=1，v21=2，△21=-1，u22=1，v22=2，△22=-1，u23=2，v23=1，△23=1 则种群 1 中的个体 3，种群 2 中的个体 1、2 被淘汰。经过多次比较、淘汰、替换操作后，剔除了适应度差的个体，其位置被加入的新个体代替，增加了多样性，实现了种群间个体交流。

图5 个体竞争示意图

4 实验结果分析

本文在不同的TAM条数下采用ITC′02基准电路d695和2*d695实验，在的3D NoC Mesh结构中映射d695电路，在3×3×3的3D NoC Mesh结构中映射2*d695电路。核的分布如表1所示，依据的原则为每层IP核的测试时间、测试功耗总和大致相同。其中第1个d695电路中的第5个核用1-5表示；第2个d695电路中的第5个核用2—5表示。

实验中设定不同的TAM条数，对每条TAM上IP核分配方案利用本文的方法进行分析，为验证本文结合云模型的遗传算法（CGA）的性能，将没有结合云模型遗传算法（GA）与本文的实验结果进行对比，比较结果如下图所示。以2条TAM为例，采用CGA的测试时间为14386个时钟周期，而采用GA的测试时间为28467个时钟周期，采用GA的测试时间明显多于采用CGA的测试时间，因此本文所采用的方法总是优于仅使用遗传算法的优化结果，且在TAM条数较少时，优化的效果更明显。

图6 d695电路的测试结果

图7 2*d695电路的测试结果

5 结论

本文采用带分复用的测试策略，重用NoC作为TAM，在TAM带宽约束下对3D NoC测试调度进行研究，将遗传算法与云模型相结合，进化初期使用云模型更新个体，并根据实验结果实时调节云模型参数。当云模型已无法更新更优秀的个体时，加入遗传算法的交叉变异以及个体间竞争机制继续更新，直至得出最佳测试时间，完成3D NoC资源内核测试规划。实验结果表明，本文的方法可明显减少测试时间，提高测试效率。