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

凌 景 杨汉生 王 静

(巢湖学院，合肥 238000)

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

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

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

1 测试规划

1.1 测试策略

3D NoC主要由资源结点、路由结点和通信链路组成[6]，其系统结构如图1所示。其中，通信链路包括水平方向的互连线和垂直方向的硅通孔。资源结点又称为资源内核或IP核，其主要用来完成系统计算任务；NoC核与核之间的数据主要通过路由节点进行存储和转发，这一点是与SoC通过总线来实现数据传输的本质区别；IP核和路由节点之间的数据传输通过资源网络接口实现。

对NoC IP核进行测试，测试矢量通过网络从输入端口传输到目的核，测试完成后从目的核通过网络传输到输出端口。测试矢量所经过的路径称为测试访问机制TAM，本次研究采用重用NoC作为TAM的测试策略。与SoC测试时所加专用硬件作为TAM不同，重用NoC作为TAM测试过程中，测试矢量的数据包可重复使用路由节点、通信链路等系统本身所有的硬件资源，进而减小硬件开销[7]。NoC通过网络进行数据传输，支持分组交换和全局同步局部异步的通信技术。3D NoC片上丰富的资源也为并行测试提供了硬件支持。数据传输过程采用常用的非抢占式静态路由算法——XYZ路由算法，基于IP核优先权的调度方式进行测试规划。

图1 3D NoC系统结构图

1.2 测试问题描述

当给核分配了测试端口后，按照XYZ路由算法便能确定核所占用的路径资源，依次判断其他测试端口上核占用的路径资源与在测核的路径资源是否冲突。调度顺序不同，则测试矢量在传输过程中冲突的测试资源不同，影响测试时间，以图2为例。图2表示核2、8、7、1测试矢量被分配到测试端口1上，核3、4、10测试矢量被分配到测试端口2上，核9、6、5测试矢量被分配到测试端口3上。图2a中第1个测试的核是IO1端口上的核8，依次判断IO2端口上的核3和IO3端口上的核6的测试资源是否与核8的测试资源冲突，如果有冲突则判断下一个核，直至测试完成；但图2b中第1个测试的核是IO1端口上的核2，这时依次判断IO2端口上的核4和IO3端口上的核5的测试资源是否与核2的测试资源冲突，如果有冲突则判断下一个核。因此核的测试顺序不同会直接影响总的测试时间，图2中调度方案1总的测试时间ta大于调度方案2总的测试时间tb。如何对IP核进行调度，优化待测核的测试顺序，减小测试时间是一个NP(Non-deterministic Polynomial)难问题[8]。

1.3 目标函数

系统总测试时间由测试结束时间最大的核决定，即

T=max(Tend(i)),i≤1≤N

(1)

其中，Tend(i)为核i的测试结束时刻，是核i测试开始时刻加上核i测试的总时间。核i测试开始时刻由上一个核的测试结束时刻决定，而核i测试总时间Ttest(i)包括核测试数据传输时间Ttr和核的测试时间Ttc，即

Ttest(i)=Ttr+Ttc

(2)

图2 不同调度方案的测试结果

对核进行测试的测试矢量是通过测试数据包在各个路由节点间传输，当第1个测试数据包传输到被测核时开始对核进行测试，余下的测试数据包相继传入网络，此时对核进行测试的时间包括了测试数据包的传输时间。因此，测试数据包传输时间主要包括第1个测试数据包从源节点传输到被测核的时间Tfirst和最后一个测试数据包从被测核传输到目的节点的时间Tlast，即

Ttr=Ji·Tfirst+(nhop)o·Tlast

(3)

其中，(nhop)i是第1个测试数据包传输到被测核i所经过的路由跳数，(nhop)o是最后一个测试数据包从被测核传输到目的节点所经过的路由跳数。用三维坐标表示路由节点，设源节点的坐标为(xi,yi,zi)，待测核的坐标为(xc,yc,zc)，目的节点的坐标为(xo,yo,zo)。则：

(nhop)i=|xc-xi|+|yc-yi|+|zc-zi|

(4)

(nhop)o=|xo-xc|+|yo-yc|+|zo-zc|

(5)

2 测试端口优化

2.1 编码

2.2 个体、基因和染色体

个体表示一种调度方案，即用于表示编码的矩阵；染色体表示调度方案中核的标号，即矩阵中的每个元素；基因即为每个染色体的特征，将核测试开始时间和测试结束时间作为染色体的特征。如个体S1中，核8的测试数据第1个传输，则该核测试开始时间tstart是0，若测试结束时间tend是698.5。则核8的2个染色体为[0,698.5]。在测试过程中，每条染色体在不同的个体中表现出不同的基因，进而使得个体表现出的特征不同，即对应调度方案的结果不同。

2.3 算法流程

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

图3 云模型特征图

将云模型与遗传算法相结合，其算法主要流程包括种群初始化、适应度值计算、云模型更新个体、遗传算法的自交、杂交、变异，其算法流程如图4所示。

(1) 种群初始化。随机为每层中的核分配一对IO端口，形成规模为n的端口分配矩阵。由随机函数生成的端口分配矩阵中非0元素个数一定与待测核的数目相等且包括所有端口对数标号。

图4 算法流程图

(2) 适应度值计算。个体的适应度值即为每个个体完成测试的时间，根据式(1)计算。

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

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

输出：{(x1,m1)…(xn,mn)}%n个云滴

For i=1 to n

{

%生成期望值为En,方差为He的正态随机数

drop(xi,ui);

%生成第i个云滴xi,ui为第i个云滴的不确定度

}

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

杂交后的S1和S2不符合个体的要求，对S1、S2进行确定基因位的自交策略，则自交后

由于个体基因特征明显，任何轻微染色体的改变都会使得个体特征有大的变化，如此杂交确定基因位自交策略能够很大程度上实现个体的变异，寻找到最优秀的调度方案。

3 实验结果分析

以ITC′02标准电路作为实验对象，将d695、g1023、p93791电路分别映射到4×3×3 Mesh结构的3D NoC上。以每层IP核的测试时间、测试功耗总和大致相同为原则进行核的分布，如表1所示。

表1 核的分布

实验设定不同的端口对数，利用本次提出的方法对每对IO端口IP核分配方案进行分析，为验证将云模型和遗传算法相结合算法(CGA)的性能，将实验结果与没有结合云模型遗传算法(EA)以及文献[12]端口位置进行优化的研究结果进行对比，比较结果如表2—表4所示。表2、表3、表4分别是电路d695、g1023、p93791采用不同算法测试的对比结果，OCG表示CGA优于GA算法的优化率，OC12表示CGA优于文献[12]的优化率。

表2 d695电路的对比结果

表3 g1023电路的对比结果

表4 p93791电路的对比结果

由测试结果可知，本次采用的方法能够减少测试时间，没有采用任何优化方法调度的结果表明不管端口位置如何变化，测试结果几乎相同。本次采用的方法与文献[12]的区别在于：文献[12]仅对端口位置进行优化，未考虑核的调度顺序，本次选择和文献[12]同样的端口，规划结果却明显优于文献[12]。

4 结 语

基于重用NoC作为测试存取机制，将遗传算法与云模型相结合，进化初期使用云模型更新个体，并根据实验结果实时调节云模型参数。当云模型已无法更新更优秀的个体时，采用遗传算法继续更新，直至得出最佳测试时间，完成3D NoC资源内核测试规划。实验结果表明，该方法可明显减少测试时间，相比于仅对测试端口位置的优化，本次的调度结果明显更优。