基于布谷鸟算法的3D NoC测试优化研究

许川佩 杜雨桐

(桂林电子科技大学电子工程与自动化学院 广西 桂林 541004)(广西自动检测技术与仪器重点实验室 广西 桂林 541004)

0 引 言

由于片上网络(Network-on-Chip，NoC)具有可重用和易扩展的特性，已被证明可更好地用于芯片的多处理器系统，以解决多核集成的问题。芯片性能的增加提高了通信效率，与此同时IP核集成数量的增加引起了测试功耗的加大，过大的功耗导致了热效应现象出现，降低了芯片测试的可靠性以及数据传输的稳定性。由于在NoC测试中多采用并行测试以减少测试时间，但是，多核并行测试造成了单位时间内的功耗堆叠，因此，本文针对如何降低3D NoC测试功耗展开研究。通过对IP核分配带宽、规划待测核的测试时序，在保证测试效率的前提下，解决片上网络测试中因功耗过大而导致的芯片发热问题。

许多学者针对3D NoC测试的优化研究做了大量的工作。Coaté等[1]对重用NoC展开研究，通过抢占式与非抢占式方法处理待测核的调度方法，采用专用路由路径对测试进行优化，减少了测试总体时间，但未对测试功耗进行优化以减少对芯片性能的影响；文献[2]采用双变换在线技术管理电源布局，并优化芯片层的堆叠结构，最大限度地降低性能损失，即通过改善热量分布减轻热点，从片上网络结构方面优化测试功耗；文献[3]通过多种群操作和算法结合得到3D NoC测试总功耗最少的测试规划方案。

1 3D NoC测试规划与目标函数

3D NoC由资源节点C、路由器R、资源网络接口和互联线等组成，针对3D Mesh结构的NoC，采用XYZ路由算法，IP核测试调度方式采用非抢占式调度方式。本文设置的测试系统参数如下：待测IP核的数目为N，设定带宽为32的TAM，TAM条数为B条，固定时钟频率以及设置芯片的功耗约束[5]。本文中测试时间和测试功耗均为标准单位，以重用NoC为测试访问机制，采用带分复用的测试策略[4]，使用虚通道技术与虫孔交换技术相结合的数据交换技术[5]，对布谷鸟算法进行改进并合理调度测试矢量的传输时序，得到算法的最优解，以最佳的测试规划方案实施低功耗并行测试。

在片上网络的测试规划中，有两个重要的性能指标，即测试功耗和测试时间[7]，本文由测试功耗和测试时间建立评估3D NoC测试的目标函数：

minf(t,p)=ω×T+(1-ω)×P

(1)

式中：ω∈[0,1]为调节因子，在测试过程中根据需求调整测试功耗和测试时间在目标函数中的占比，即当ω=0时只做测试功耗部分的优化；ω=1时只做时间部分的优化；0≤ω≤1时，折中优化两个部分。本文ω设置为0.55。

测试矢量经过的路由器数量、路径信息，路径计算函数表示为：

(2)

式中：dCiCi+1为测试过程中数据包由待测核i至核i+1需要经过的路由器的数量；N为总的待测核数目；Q为NoC测试经过的路由器总数量，由XYZ路由算法以及TAM中的测试时序得到测试经过的路径[7]。在测试过程中，将数据包通过的路由器标号按顺序记录在数组DB={R0,R1,…,Rm-1,Rm}中，其中Rm为第m步经过的路由器标号，DB表示测试矢量在第B条TAM上的测试路径。

本文中片上网络测试时间由最长的TAM测试时序计算总测试时间，测试时间函数表示为：

(3)

(4)

式中：N为IP核的总数；B为TAM数量；Tti,j为TAMj上第i个IP核的测试时间；Twi,j为核i遇到冲突所需等待的时间。

测试功耗函数表示为：

(5)

Ppassi=nxyi×Pxy+nzi×Pz+zi×Pr

(6)

式中：Pmax表示NoC测试允许的最大功耗；nxyi、nzi分别表示第i个核在xy平面方向、z轴方向上所通过的通信链路数目；zi表示第i个核经过的路由器总数。Pxy、Pz和Pr分别表示测试数据通过xy平面方向路径、z轴方向路径以及路由器的传输功耗，这些值由NoC系统标准得出，本文设定Pxy=0.1、Pz=2、Pr=10[9]。

2 基于布谷鸟算法的3D NoC测试

2.1 模型编码方案

本文针对3D NoC测试，通过改进布谷鸟算法以迅速准确地寻找到测试功耗最低的解，并以X作为测试数据的TAM分配矩阵，X的编码如下：

(7)

对IP核的测试时序的编码如下：

(8)

式中：SBv是第B条TAM传输中的第v个测试数据为标号是SBv的IP核；N为待测IP核的总数，起始核的标号为1。SBv为0表示该核不存在。

2.2 鸟巢的更新

(9)

(10)

(12)

α0的计算公式如下：

(11)

σu的计算公式及σv的定义为：

(13)

σv(β)=1

式中：u和v分别是标准偏差σu和σv的两个标准正态分布随机变量；β是满足0<β≤2的分布因子，本文设置β为1.5；Γ是伽马分布函数。

为了在执行算法过程中以更快的速度得到全局最优解并且避免出现早熟现象，在算法的初期要保证α在足够大的范围内变化。为了加快在此过程中的收敛速度，α降低的速度也要随之增大，在迭代后期α的值降速趋缓，以此保证算法的寻优方向是趋于稳定的，从而加速得到局部最优解。本文设置αmax=2、αmin=1，α(gen)的计算式表示为：

(14)

算法初期α(gen)的值下降速度迅速，算法后期α(gen)的值下降速度比较缓慢。当迭代次数gen=1时，α(gen)≈0.003 3，而当gen=300时，α(gen)≈0.761 6。

本文通过余弦递减策略改进发现概率，设定发现概率为Pag，最优解的搜索速度取决于Pag的取值，Pag过大则较难收敛到最优解，Pag过小则会导致收敛速度过慢。为提高算法寻找劣质解的概率，采用余弦函数的特点动态改变发现概率。其中，Pmin=0.2，Pmax=0.5，Pag的取值范围是(0.2,0.8)，P′为调整参数，本文设置P′为0.5。发现概率公式表示为：

(15)

图1 改进的发现概率变化情况

(16)

算法具体步骤如下：

步骤1初始化鸟巢群体，即对测试数据分配TAM，将随机生成的F个分配方案记录于X矩阵中，并设定算法系数。

步骤2比较每个鸟巢的适应度值，即测试规划结果，找到当前的全局最佳鸟巢gbestg。

步骤4对劣质鸟巢通过交叉变异操作替换部分鸟巢以生成新的鸟巢。

步骤5通过比较操作将飞行操作之前和之后的鸟巢的适应度值进行对比，将更好的鸟巢放入鸟巢群体。

步骤6得到全局鸟巢群体中的最佳解以及鸟巢信息。

步骤7检查是否达到最大迭代次数，若达到则结束算法，得到测试时间、测试功耗最少的测试规划方案，否则转至步骤2。

算法流程图如图2所示。

图2 基于布谷鸟算法的3D NoC测试流程图

3 实验结果分析

本文仿真环境为Windows 7 64位操作系统，CPU运行速度为3.20 GHz，4 GB内存，通过 Microsoft Visual Studio 2013编写程序。采用ITC'02 SoC Test Benchmarks中的d695、g1023和p93791电路作为实验对象，并记录实验数据。其中，适应度值优化率的公式为：

(17)

本文对3D NoC进行测试规划的基准电路信息如表1所示。

表1 基准电路信息

基于基准电路g1023进行测试，在TAM 条数不同的情况下测试功耗和时间的适应度值结果如表2所示。

表2 g1023电路下不同TAM的测试结果

由于测试资源的限制，TAM条数由2增至3时，测试总功耗和时间减少幅度明显，能达到9.4%的优化率。因此，若在g1023电路下设置2条TAM，会导致资源不足，使传输冲突增加，测试时间和功耗加大。而TAM条数设置过多则会出现资源浪费，因此，在优化测试时要尽可能多地利用资源，以得到更好的优化效果。

本文以3条TAM作为g1023、d695和2×d695电路的测试条件，p93791、3×d695电路设置4条TAM进行测试。由表3可知,在得到最佳适应度值的条件下，TAM的分配情况以及核的测试时序。

表3 g1023电路核的测试规划

3D NoC测试电路规模不同时，布谷鸟算法优化前以及优化后的适应度值如图3所示。

图3 不同电路规模下的测试结果

针对3D NoC测试的协同优化结果如下，对于d695电路，优化率约为10.5%；g1023电路，优化率约为10.8%；2×d695电路，优化率约为8.5%；p93791电路，优化率约为4.5%；3×d695电路，优化率约为6.0%。

验证条件设定如下：测试传输TAM的带宽为32，改进的布谷鸟算法的种群大小在不同规模下设置不同大小的种群。在3×3×3的规模下的种群设置为100，由上文知F=100，在4×3×3的规模下设置为150个，即F=150，迭代次数设置为300次，即gen=300。为了更进一步地说明改进后的布谷鸟算法能够稳定的寻优，得到更好的全局最优解。分别将优化前的布谷鸟算法与优化后的布谷鸟算法加入3D NoC测试规划，得到测试时间、测试功耗以及适应度值的结果，并进行对比，3D NoC测试实验结果如表4和表5所示。

表4 CS优化前实验结果

表5 CS优化后实验结果及分析

由CS优化前和优化后实验结果可知，经改进后的布谷鸟算法能够有效控制NoC测试功耗的涨幅，同时减少整体测试时间。在约束条件下，可以更好地利用片上网络资源，增强芯片可靠性，加快了收敛速度的同时也加强了寻优效果。当芯片规模为3×3×3，同时芯片上映射的IP核数量小于等于20个时，测试功耗与测试时间的优化率由表4、表5可见，改进的布谷鸟算法优化程度好于优化前，优化率能达到10.7%。在规模4×3×3下进行测试，待测核数量小于等于32个时，改进的布谷鸟算法也优于改进前的算法，但优化率不如小规模下的测试优化程度高。因此，采用改进的布谷鸟算法在3D NoC测试功耗与时间的协同优化方面更为有效。

4 结 语

本文针对3D NoC的测试功耗过大的问题，协同优化测试功耗和时间，通过改进布谷鸟算法，采用基于logistic函数模型动态控制步长，通过余弦递减函数改进发现概率，找到最优的测试规划方案，得到最小的测试功耗和时间。在保证不会降低芯片性能的前提下，通过改进布谷鸟算法提高 NoC测试效率的同时，合理利用片上网络资源有效地降低测试成本。实验结果表明，本文得到的测试规划方案，在优化3D NoC测试时间与功耗方面有明显效果。