基于Petri网与混沌差分萤火虫算法的3D NoC测试规划方法

摘要

本发明公开一种基于Petri网与混沌差分萤火虫算法的3D NoC测试规划方法，首先通过在原型Petri网的基础之上增加时延与带抑止弧的概念，能有效描述测试规划中的IP核调度问题、简化模型；模型建立后，为了在Petri网的变迁发生序列集合中实施高效寻优，对基本萤火虫算法进行了两处改进，即分别采用单维结合多维的混沌优化方法，使基本萤火虫算法具备精细的局部寻优能力，采用与差分进化算法之间的信息共享机制，增强基本萤火虫算法的全局寻优能力。将实验结果与其他测试方法的实验结果进行比较，结果显示本发明测试方法在测试时间与程序运行时间方面都展现出较明显的优势。

说明书

技术领域

本发明涉及三维片上网络(three Dimensional Network-on-Chip，3D NoC) 技术领域，具体涉及一种基于Petri网与混沌差分萤火虫算法的3D NoC测试规划方法。

背景技术

三维片上网络通过硅通孔(Through Silicon Via，TSV)技术，将二维片上网络(Network-on-Chip，NoC)结构进行层间衔接，有效缓解了制造工艺水平与设计能力之间的“剪刀差”。虽然3D NoC具备互连线短、集成度高、功耗及延迟低、可拓展性及电路抗噪声能力强等种种优势，但与此同时，单位芯片面积上包含资源内核数目的增长、芯片系统结构复杂度的攀升，将对芯片的并行测试效率带来新一轮的考验。因此，以缩减测试成本为目标，考虑软硬件等多种约束条件的限制，如何实施高效的并行传输与测试，成为一个NP难题，同时也具有较大研究价值。

由于Petri网能够便捷地对分布式系统中的顺序、同步、并发及冲突等现象进行描述，因此通过Petri网对3D NoC测试规划问题建立模型，不仅可以通过图形刻画调度过程，同时易于观察这一过程的动态变化。然而当系统规模不断扩大时，通过可达标识图求解Petri网将使得状态空间矩阵的大小以指数规律急剧上升。

发明内容

本发明针对现有的测试规划Petri网模型的状态空间过大，测试规划算法对测试时间寻优效果不佳的问题，提供一种基于Petri网与混沌差分萤火虫算法的3D NoC测试规划方法。

为解决上述问题，本发明是通过以下技术方案实现的：

基于Petri网与混沌差分萤火虫算法的3D NoC测试规划方法，具体包括步骤如下：

步骤1、根据3D NoC中每个资源内核的测试资源需求建立增广时延变迁 Petri网模型，并计算增广时延变迁Petri网模型的输入矩阵、输出矩阵以及状态空间矩阵，确定初始标识与终止标识；

步骤2、初始化两个不同规模的萤火虫种群，分别为TAM分配种群与顺序分配种群，即在(0,M)开区间内，按照TAM分配个体编码方式，随机生成 NP1个D维的TAM分配个体形成TAM分配种群；在此基础上，针对每一个 TAM分配个体，都在(0,1)开区间内，按顺序分配个体编码方式，随机生成 NP2个顺序分配个体形成顺序分配种群；其中M、NP1、NP2、D均为设定值， M为TAM条数，D为IP核数量，NP1≥NP2；

步骤3、根据TAM分配种群的TAM分配个体与顺序分配种群的顺序分配个体生成相应的变迁发生序列个体，并计算每一个变迁发生序列个体的适应度值即总变迁时延及功耗；

步骤4、采用混沌差分萤火虫算法对变迁发生序列个体进行寻优和更新，寻找出最优变迁发生序列个体，即最优TAM分配个体与最优顺序分配个体的组合；即：

步骤4.1、采用萤火虫算法，更新变迁发生序列个体位置，得到萤火虫算法在本次迭代中适应度值最小的变迁发生序列个体，即萤火虫优选变迁发生序列个体；

步骤4.2、采用差分进化算法，更新变迁发生序列个体的位置，得到差分进化算法在本次迭代中适应度值最小的变迁发生序列个体，即差分优选变迁发生序列个体；

步骤4.3、比较步骤4.1所选出的萤火虫优选变迁发生序列个体和步骤4.2 所选出的差分优选变迁发生序列个体的适应度值，并将两者中适应度值较小的个体作为最优变迁发生序列个体进入步骤4.4；

步骤4.4、采用混沌优化方法，对步骤4.3所选出的最优变迁发生序列个体进行单维结合多维的混沌扰动更新，得到本次迭代的最优TAM分配个体与最优顺序分配个体的组合；

步骤5、判断当前迭代是否达到混沌差分萤火虫算法的最大迭代次数：没达到则返回步骤3，进入下一次迭代寻优；若达到，则输出当前迭代所得到的最优变迁发生序列个体，作为最佳TAM分配与顺序分配方案。

上述步骤1中，所建立的增广时延变迁Petri网模型在原型Petri网的基础之上，为每个变迁赋予时延与功耗，并增添一种从库所引向变迁有控制作用的抑止弧。

上述步骤2中，TAM分配个体编码方式采用实数编码方式，即：在随机初始化TAM分配个体时舍去小数部分，并确保不存在未被分配IP核的空闲 TAM，或者将IP核分配至系统中不存在的TAM编号，否则重新初始化。

上述步骤2中，顺序分配个体编码方式采用二维矩阵编码方式，即：

首先，通过TAM分配个体确定各个IP核被划分至哪条TAM；

接着，在固定TAM分配的情况下，对每条TAM上IP核的测试先后顺序，用(0,1)区间内的小数进行随机初始化；

最后，根据升序重新排列IP核的顺序，从而针对每个TAM分配个体产生一定数量的顺序分配个体。

上述步骤3中变迁发生序列个体的适应度值计算过程如下：

步骤3.1、调度测试分配至第一条TAM上的第一个变迁，并标志该条TAM 为正在测试的忙状态，标志该变迁为正处于激发状态的变迁；

步骤3.2、查找处于空闲状态的TAM，并通过输入、输出矩阵以及变迁发生准则判断该条TAM上的未激发变迁是否具备激发条件：

若该变迁满足激发条件，则计算增广时延变迁Petri网模型的状态标识、变迁时延即测试时间、以及测试功耗，并标志该变迁为正处于激发状态变迁、标志该TAM为正在测试的忙状态，并返回步骤3.2开始查找下一条空闲状态的TAM；

若该变迁不满足激发条件，则继续查找同一条TAM上的下一个未激发变迁，并判断该未激发变迁是否具备激发条件，若该条TAM上所有的未激发变迁均不具备激发条件，则返回步骤3.2开始查找下一条空闲状态的TAM；

步骤3.3、遍历查找完所有TAM之后，等待某个变迁完成激发即某个IP 核完成测试，更新状态标志、变迁时延以及测试功耗，将完成激发的变迁标志为已激发变迁，并标志刚被释放的TAM，判断该变迁所处的TAM上的所有变迁是否都为已激发状态：若是，则标志该TAM为完成测试状态；否则，标志该TAM为空闲状态；

步骤3.4、判断是否到达终止标识，即判断变迁发生序列中的所有变迁是否都为已激发变迁：若是，则输出变迁发生序列个体的总变迁时延及功耗；否则，转至步骤3.2。

上述未激发变迁具备激发条件是指：测试数据包的传输路径没有冲突，且传输功耗同时满足层功耗与总功耗约束。

上述步骤4.4的具体过程如下：

步骤4.4.1、设置最大混沌局部搜索次数M_s，初始时混沌局部搜索次数>

步骤4.4.2、判断混沌局部搜索次数k的奇偶：

若混沌局部搜索次数k为奇数，则对最优变迁发生序列个体的某一维进行混沌扰动，得到1个混沌个体，并将该混沌个体保存至混沌种群中；

若混沌局部搜索次数k为偶数，则对最优变迁发生序列个体的每一维进行混沌扰动，得到1个混沌个体，并将该混沌个体保存至混沌种群中；

步骤4.4.3、判断混沌局部搜索次数k是否达到最大混沌局部搜索次数M_s，若是，则转至步骤4.4.4；否则，令k加1，转至步骤4.4.2；

步骤4.4.4、选出当前混沌种群中适应度值最小的混沌个体作为优选混沌个体；

步骤4.4.5、若优选混沌个体的适应度值小于最优变迁发生序列个体的适应度值，则用该优选混沌个体位置替换原最优变迁发生序列个体；否则保留原最优变迁发生序列个体不变；

步骤4.4.6、将当前最优变迁发生序列个体作为本次迭代的最优TAM分配个体与最优顺序分配个体的组合。

与现有技术相比，本发明具有如下特点：

1、本发明采用增广时延变迁Petri网(Extended Time Transition Petri Net，ETTPN)为3D NoC测试建立规划模型，该模型在原型Petri网的基础之上，为每个变迁赋予时延与功耗，并增添一种从库所引向变迁有控制作用的抑止弧，能有效描述测试规划中的IP核调度问题，增强Petri网的模拟能力，同时通过引入抑止弧降低了输入、输出矩阵中行的维度和状态空间中列的维度，从而简化模型、提高测试效率。

2、采用混沌差分萤火虫算法，即将差分进化算法以辅助型的方式，与萤火虫算法进行最优信息的共享，增强了基本萤火虫算法的全局寻优能力，同时针对每次迭代的最优个体位置，对其进行单维结合多维的混沌扰动寻优，增强了基本萤火虫的局部搜索能力，提高了寻优精度，，从而利用改进后的混沌差分萤火虫算法在Petri网的变迁发生序列集合中实施高效寻优，最终求得 3D NoC的最佳测试规划方案。

附图说明

图1为3D Mesh NoC并行测试示意图。

图2为ETTPN子模型示意图。

图3为变迁发生序列适应度值计算流程图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实例，并参照附图，对本发明进一步详细说明。

本发明采用新兴元启发式优化方法——萤火虫算法(Firefly Algorithm， FA)在Petri网的变迁发生序列集合中进行搜索，FA具备概念简单易理解、收敛速度快及寻优精度较高等优势，被越来越多地运用于求解NP难题，但 FA仍旧无法摆脱群智能优化算法容易陷入局部最优值而无法跳出的通病。因此本发明针对以上问题提出混沌差分萤火虫算法(Firefly Algorithm Combined with Differential Evolution and Chaotic LocalSearch，CDEFA)，同时增强基本萤火虫算法的全局寻优能力与局部精细搜索能力。最终通过将增广时延变迁 Petri网与混沌差分萤火虫算法相结合的方式，实现3D NoC测试规划问题的优化求解。

本发明优选实施例所涉及的3D NoC为3D Mesh拓扑结构，如图1所示，主要由资源节点也即资源内核(Intellectual Property，IP)、路由节点、资源网络接口、水平层面(xy方向)的互连线和垂直层面(z方向)的TSV构成。

1、测试策略

为降低测试的硬件开销、减少网络拥塞以及测试模型的复杂度，采用的测试策略如下：复用NoC作为测试访问机制(test access mechanism，TAM)，即将NoC中的路由节点、互连线、TSV等作为资源内核测试矢量传输的路径资源。而传输路径的选择通过确定性维序XYZ路由算法确定，如图1中第三层的核8被分配至TAM2进行测试时，测试矢量由自动测试设备(Automatic Test Equipment，ATE)从Input2端口输入给第一层的核4，然后依次沿x、y、z坐标方向路由至第三层的核8，该核的测试响应按照同样的方式最后经由第一层的核3，通过Output2端口输出至ATE。测试过程中采用非抢占式传输方式，即对IP核进行连续测试，测试中途不会因被其他IP核抢占资源而导致中断，且规定每个核只能测试一次。

2、问题描述

因此本发明涉及的3D NoC测试规划问题可简要概述为：对于一个3D NoC，已知N个资源内核的相关参数如：扫描链长度及数量、测试矢量个数等。给定M条固定带宽的TAM(即M对I/O测试端口)，拓扑结构、调度方式、路由算法等，研究如何为每个IP核的测试过程建立准确的Petri网模型，通过Petri网内部的元素描述IP核的TAM分配与该核的测试时间及测试功耗，在测试资源无冲突、功耗满足限制的条件下，如何通过群智能优化算法求解 Petri网模型，最终求得最优变迁发生序列，即系统最佳测试方案。

3、Petri网建模

针对以上的测试规划问题，采用面向IP核的思想结合子任务划分的方式，针对每个核的测试数据包在不同TAM上传输所需的资源，建立增广时延变迁 Petri网模型。通过Visual Object Net++仿真软件建立模型并观察Petri网系统的运行状态，以14个待测核3条TAM为例，针对其中的IP核3与IP核5 建立的ETTPN模型如图2所示，表1与表2分别列出了图2中各变迁与各库所的含义。

表1图2中各变迁的含义

表2图2中各库所的含义

以变迁t_0,3为例，分别从两方面简要说明ETTPN模型运行规则，从3D>0,3的发生条件为，库所s_0,1、s_0,3、s_1,1、s_1,2、s_1,3中有标识，测试功耗满足约束条件，同时库所S_b3中无标识，此时变迁t_0,3才能被激发。变迁t_0,3被激发后，库所S_b3得到标识，意味着变迁t_1,3与t_2,3将无法满足激发条件，从而保证了三个变迁t_0,3、t_1,3、>2,3当中只有一个能发生，即保证了核3只被分配至一条TAM(一对I/O口)>

模型中的变迁发生序列与测试规划方案之间存在一一对应的关系，当14 个IP核被分配至3条TAM进行测试时存在3¹⁴种测试规划方案，即从初始标识M₀＝{00000000000000111111111111111111}抵达终止标识>f＝{11111111111111111111111111111111}时有3¹⁴个变迁发生序列通过算法在大量的变迁发生序列σ集合中寻找最优序列，等同于在测试规划方案中寻找最优测试路径选择方案，而最优规划方案的测试时间即为变迁发生序列σ中所有变迁时延DI与等待时间W的总和，通过ETTPN模型最终实现了3D NoC测试规划问题向Petri网求解问题的转变。

模型建立后，根据模型的软件仿真图计算输入、输出矩阵A^-与A⁺以及状态空间矩阵即所有的可达标识，确定初始与终止标识，为后续判断变迁是否具备激发条件建立基础。

4、算法求解Petri网模型

为了求解以上针对3D NoC测试规划问题建立的ETTPN模型，采用萤火虫算法在模型的变迁发生序列集合中进行寻优。

萤火虫算法通过个体之间的亮度差异引导来搜索最优值，对于最大化寻优问题，绝对亮度小的萤火虫个体总是会被绝对亮度比它大的个体吸引，而不断更新自身的位置向量，由于每个个体的亮度感应范围一定且各个个体之间相互独立，所以通过迭代寻优能够同时获得解空间当中的局部和全局最优解。但基本萤火虫在解决规模较大的NP完全问题时，仍然存在一些局限性：

1)由于萤火虫算法自身缺少变异规则，在迭代寻优的过程当中无法保证种群多样性，所以易早熟收敛；

2)迭代后期随着萤火虫个体之间距离的缩小，由于吸引力过大使得个体在极值点附近来回震荡，导致收敛速度慢、寻优精度低。

针对以上两大缺陷，基于混沌序列随机、遍历、初值敏感等优良特性，与差分进化算法(Differential Evolution Algorithm，DE)良好的全局搜索能力，提出混沌差分萤火虫算法。

4.1算法编码

建立ETTPN模型，并选取寻优算法后，需要对算法进行编码，即将测试规划方案用合适的编码方式表达为萤火虫算法中的个体，才能将萤火虫算法运用于模型求解问题，因此设定以下编码方式：

假定IP核总数为N，TAM数量为M。协同考虑IP核被划分至不同TAM 与同一条TAM上IP核测试的先后顺序对测试时间的影响，所以需要对TAM 分配个体与测试顺序个体分别编码。

1)TAM分配个体编码

采用实数编码方式，随机初始化TAM分配个体时舍去小数部分，并确保不存在未被分配IP核的空闲TAM，或者将IP核分配至系统中不存在的TAM 编号，否则重新初始化。

TAM分配个体编码如下：

X_TAM＝{B₁>2 ···>N}

式中，B_i表示第i个被测IP核被划分至标号为B_i的TAM进行测试，N为>i≤M。

2)顺序分配个体编码

采用二维矩阵编码方式，首先确定各个IP核被划分至哪条TAM，划分方案确定后再对每条TAM上IP核的先后顺序，用(0,1)区间内的小数进行随机初始化，最后再根据升序重新排列核的顺序。

顺序分配个体编码如下：

式中，A_bj表示对应标号的IP核在TAMb上的测试顺序为j。1≤A_bj≤N，>

3)变迁发生序列编码

由于需将求解3D NoC测试规划问题转换为求解ETTPN模型，所以有必要将IP核TAM分配个体编码与测试顺序分配个体编码，转换为与两者的组合相对应的变迁发生序列编码：

式中：t_b,j∈T表示标号为b的TAM上包含了第j个IP核的测试矢量，>

以IP核总数为10、TAM数量为3举例，对编码方式进行详细阐述，TAM 分配个体X_TAM＝{1>表示被划分至TAM0上测试的3 个IP核的先后顺序为：3→2→5，被划分至TAM1上测试的4个核的先后顺序为：6→9→8→1，被划分至TAM2上测试的3个核的先后顺序为： 4→10→7。

该TAM分配个体与测试顺序分配个体的组合对应的变迁发生序列为：

4.2混沌差分萤火虫算法位置更新准则

建立ETTPN模型，并确定算法编码方案后，根据上述编码方案初始化萤火虫种群，以10个IP核3条TAM为例，在(0,3)开区间内，随机生成规模为100、维数为10的TAM分配萤火虫种群，在(0,1)开区间内生成规模为30的顺序分配萤火虫种群。初始化完成后，根据初始化生成的TAM分配个体与顺序分配个体，生成对应的变迁发生序列个体。例如通过 X_TAM＝{10>生成对于该变迁发生序列，按照以下步骤计算其适应度值(参见图3)：

(注：该计算过程中的TAM状态有三种：处于正在测试的忙状态，处于非测试阶段的空闲状态以及完成测试状态；变迁也有三种状态：未激发态，完成激发态以及刚被激发但未结束的激发状态。)

步骤1：调度测试分配至第一条TAM上的第一个变迁，如t_0,3，并标志该条TAM为正在测试的忙状态，标志该变迁为正处于激发状态的变迁。

步骤2：查找处于空闲状态的TAM，并通过输入、输出矩阵以及变迁发生准则判断该条TAM上的未激发变迁是否具备激发条件，(即判断测试数据包的传输路径是否冲突以及传输功耗是否同时满足层功耗与总功耗约束)，若该变迁满足发生条件，则进入步骤3；若该变迁不满足发生条件，则继续查找同一条TAM上的下一个未激发变迁，重复以上判断，若该条TAM上的所有变迁均不具备发生条件，则重复步骤2开始查找下一条空闲TAM。

步骤3：计算ETTPN模型的状态标识、变迁时延(即测试时间)以及测试功耗，并标志该变迁为正处于激发状态变迁、标志该TAM为正在测试的忙状态，然后转至步骤2开始查找下一条空闲TAM。

步骤4：遍历查找完所有TAM之后，等待某个变迁完成激发(即某个IP 核完成测试)，将完成激发的变迁标志为已激发变迁，标志刚被释放的TAM，判断该变迁所处的TAM上的所有变迁是否都为已激发状态，若是，则标志该 TAM为完成测试状态，否则，标志为空闲状态，更新状态标识、变迁时延及功耗。

步骤5：判断是否到达终止标识，即判断所有变迁是否都为已激发变迁，若是，则输出变迁发生序列的总变迁时延及功耗；否则，转至步骤2。

通过以上步骤计算得出所有变迁发生序列的适应度值后，分别按照以下的萤火虫算法与差分进化算法，对变迁发生序列个体进行寻优更新。最后通过比较两种算法的寻优结果，得出本次迭代中适应度值最好的个体位置。差分进化算法通过这种单独寻优的辅助方式，能够与萤火虫种群进行最优信息的共享，间接增强了基本萤火虫算法的种群多样性与全局寻优能力。

1)基本萤火虫算法位置更新准则

在萤火虫算法中，将目标函数在个体位置向量处的适应度值作为萤火虫i的绝对亮度I_i，即若萤火虫i的绝对亮度相比萤火虫j较大，则通过下式计算i对j的吸引力：

式中，β₀代表最大吸引力，γ是光吸收系数，r_ij表示两只萤火虫之间的距离，计算公式如下式所示：

式中，x_i,k与x_j,k分别表示萤火虫个体i与个体j位置向量中的第k维。

萤火虫个体j由于个体i对它的吸引，依据以下公式对位置进行更新从而向i靠近。

式中，t表示迭代次数，α是[0,1]区间内的常数，表示随机数向量。

2)差分进化算法位置更新准则

差分进化算法，主要由以下三大操作构成：

a、变异操作

通过以下公式的变异操作，产生与解空间中的任意一个目标向量(G为进化代数，NP为种群规模)对应的施予向量

式中，r1、r2、r3是在[1,NP]区间内不等于i同时相互独立的整数，F∈[0.4,1] 表示变异算子。

b、交叉操作

通过将目标向量中的某些维用施予向量的对应维进行替换，可提高多样性，交叉过程产生的试验向量如以下公式：

式中，D为向量维数，randb(j)代表[0,1]范围之间的随机数，CR∈[0,1]是交叉算子，rnbr(i)∈(1,2,···,D)为向量中某一维。

c、选择操作

按照贪婪准则，选取目标向量与试验向量当中适应度值更好的个体进行后续的迭代：

式中，与分别为试验向量与目标向量对应的目标函数值。

2)混沌优化算法更新准则

采用萤火虫算法结合差分进化算法，对变迁发生序列进行一次迭代寻优之后，会得到本次迭代的最优变迁发生序列个体，对应着最优的TAM分配与顺序分配方案，也即最优萤火虫个体的位置，针对该最优萤火虫个体应用混沌序列，通过改变某一维与改变所有维交替进行的方式，在该最优萤火虫个体位置的一定邻域内生成一系列的混沌个体，并从中择优选取，具体步骤如下：

步骤1：随机选定混沌序列的初始迭代数值y₀，设置混沌局部搜索共进行M_s次，混沌局部搜索次数通过k进行累加，且初始时k＝1。

步骤2：根据以下立方映射函数公式由y_k-1计算y_k。

y(n+1)＝4y(n)³-3y(n)

式中y(n)∈[-1,1]，且y(n)≠0,n＝0,1,2,···。

步骤3：判断混沌局部搜索次数k的奇偶：

①若k为奇数，则进行单维的混沌局部搜索。即：

在[1,D]范围内产生随机整数d，其中D是解空间维数。设tp＝p_g，p_g为通过萤火虫算法结合差分进化算法，得到的本次迭代的全局最优萤火虫个体位置。根据下式对p_g进行某一维的混沌扰动：

tp_d＝p_gd+(-1)^k(1-(t-1)/T_max)y_k

式中，tp_d表示tp的第d维，p_gd表示p_g的第d维，t是萤火虫算法当下的迭代次数，T_max表示萤火虫算法迭代次数的上限。

②若k为偶数，则进行多维的混沌局部搜索。即：

依次取d＝1,2,···,D，并对p_g的每一维都按照以上公式实施混沌扰动。

步骤4：将第k次通过混沌搜索得到的新个体位置保存至混沌种群个体 cx_k，即cx_k＝tp。

步骤5：若k＜M_s，则令k加1，转至步骤2。

步骤6：计算得出混沌种群cx_k,(k＝1,2,···,M_s)中适应度值最好的混沌个体位置，若比本次迭代中的最优萤火虫个体位置p_g的适应度值好，则进行替换，否则不替换。

现有的大部分混沌优化方法都是多维的方式，即每次循环都会改变目标向量的每一维，而本发明中的混沌扰动采用单维结合多维的方式，这样的方式在目标向量距离最优解只有微小的差距时，可以提高寻优效率与精度。

按照以上混沌差分萤火虫算法对变迁发生序列个体，即TAM分配与顺序分配个体，进行一次寻优迭代得到最优变迁发生序列个体位置后，重新计算位置更新后的各个变迁发生序列个体适应度值，然后再根据混沌差分萤火虫算法进行第二次迭代寻优，如此循环往复直至达到预设的最大种群迭代次数，最后输出最优变迁发生序列对应的TAM分配与顺序分配方案。

基于以上分析，本发明公开一种基于Petri网与混沌差分萤火虫算法的3D NoC测试规划方法，具体包括步骤如下：

步骤1、根据3D NoC中每个资源内核的测试资源需求建立ETTPN模型，并计算模型的输入、输出矩阵以及状态空间矩阵，确定初始与终止标识。

步骤2、初始化两个规模分别为NP1、NP2的萤火虫种群，分别为TAM 分配种群与顺序分配种群，即在(0,M)开区间内，按照TAM分配个体编码方式，随机生成NP1个D维的TAM分配个体形成TAM分配种群；在此基础上，针对每一个TAM分配个体，都在(0,1)开区间内，按顺序分配个体编码方式，随机生成NP2个顺序分配个体形成顺序分配种群。其中M、NP1、 NP2、D均为设定值，M为TAM条数，D为IP核数量，NP1≥NP2。

以10个IP核3条TAM为例，在(0,3)开区间内随机初始化，生成100 个10维的TAM分配个体，由于针对同一个TAM分配个体，同一条TAM上核的测试顺序会对测试时间产生影响，所以对每一个TAM分配个体，在(0,1) 区间内随机生成30个顺序分配个体，即每一个TAM分配个体都将对应30 个顺序分配个体，这30个顺序分配个体中每条TAM上分配的IP核编号一样，但测试顺序不同，后续可通过算法先找出同一种TAM分配方式下的最优测试顺序，然后再通过算法找出最优TAM分配方式。

上述用于将萤火虫算法与实际问题相结合的编码方式如下：

TAM分配个体用于确定IP核被分配至哪条TAM进行测试，其采用实数编码方式，随机初始化TAM分配个体时舍去小数部分，并确保不存在未被分配IP核的空闲TAM，或者将IP核分配至系统中不存在的TAM编号，否则重新初始化。

顺序分配个体用于在确定IP核的TAM分配后，进一步确定分配至同一条TAM的IP核的测试顺序，其采用二维矩阵编码方式，且以TAM分配个体编码为基础，即只有先确定各个IP核被划分至哪条TAM，划分方案确定后，才能对分配至同一条TAM的IP核的测试先后顺序，用(0,1)区间内的小数进行随机初始化，最后再根据升序重新排列核的测试顺序。

步骤3、根据初始化生成的TAM分配个体与顺序分配个体生成相应的变迁发生序列个体。

步骤4、计算每一个变迁发生序列个体的适应度值即总变迁时延及功耗。

1)调度测试分配至第一条TAM上的第一个变迁，并标志该条TAM为正在测试的忙状态，标志该变迁为正处于激发状态的变迁。

2)查找处于空闲状态的TAM，并通过输入、输出矩阵以及变迁发生准则判断该条TAM上的未激发变迁是否具备激发条件，(即判断测试数据包的传输路径是否冲突以及传输功耗是否同时满足层功耗与总功耗约束)，若该变迁满足发生条件，则进入3)；若该变迁不满足发生条件，则继续查找同一条 TAM上的下一个未激发变迁，重复以上判断，若该条TAM上的所有变迁均不具备发生条件，则转至2)的开头，开始查找下一条空闲TAM。

3)计算ETTPN模型的状态标识、变迁时延(即测试时间)以及测试功耗，并标志该变迁为正处于激发状态变迁、标志该TAM为正在测试的忙状态，然后转至2)开始查找下一条空闲TAM。

4)遍历查找完所有TAM之后，等待某个变迁完成激发(即某个IP核完成测试)，将完成激发的变迁标志为已激发变迁，标志刚被释放的TAM，判断该变迁所处的TAM上的所有变迁是否都为已激发状态，若是，则标志该 TAM为完成测试状态，否则，标志为空闲状态，更新状态标识、变迁时延及功耗。

5)判断是否到达终止标识，即判断所有变迁是否都为已激发变迁，若是，则输出变迁发生序列个体的总变迁时延及功耗；否则，转至2)。

变迁发生准则为：对于变迁t∈T，若该变迁所有一般性输入库所当中的标志均大于或等于1，同时带抑止弧的输入库所当中无标识，即且则称变迁t有发生权，记为M[t＞。变迁t在标识M下被激发之后获得新标识M'，计算公式如下：

变迁时延计算公式为：

式中：M代表TAM条数，N代表IP核个数，W_i,j代表当不满足并行测试约束条件时，在该节点处的等待时长，DI_i,j代表IP核i的测试矢量被安排至>corei及测试数据包的路由时长T_transi，即DI_i,j＝T_{core>+Ttrans>。测试数据包的路由时长由下式计算：}

T_{trans>＝nbxy>·Txy+nbz>·Tz+nbr>·Tr＝Tr+nbxy>·(Txy+Tr)+nbz>·(Tz+Tr)}

式中：T_xy、T_z、T_r分别表示测试矢量在xy坐标方向的互连线、TSV以及路由节点上的单位传输时间，nb_xyi、nb_{z>、nbr>分别表示测试矢量通过xy坐标方向的互连线、TSV以及路由节点的数量。}

层功耗约束与总功耗约束分别为：

1)在任意的时间槽t，第l层在测核的功耗总和P_l^t需要满足：

式中：P_{max_l(l)}代表第l层的功耗上限，TS_i和TE_i分别是IP核i测试时的起始及结束时刻。P_{test>代表分布在第l层核i的总功耗，由对该核测试产生的功耗Pcore>和对测试矢量进行路由传输产生的功耗Ptrans>组成，即}

P_{test>＝Pcore>+Ptrans>}

式中：P_{core>由制造商提供，Ptrans>计算公式如下：}

P_{trans>＝nbxy>·Pxy+nbz>·Pz+nbr>·Pr＝Pr+nbxy>·(Pxy+Pr)+nbz>·(Pz+Pr)}

式中：P_xy、P_z、P_r分别代表测试矢量经由xy坐标方向互连线、TSV以及路由节点的路由传输功耗。

2)在任意时间槽t，要求拓扑结构中所有正在进行测试的IP核的功耗之和必须低于总功耗的上限P_max：

步骤5、采用混沌差分萤火虫算法对变迁发生序列个体进行寻优、更新，寻找出最优变迁发生序列个体，即最优TAM分配个体与最优顺序分配个体的组合，也即最佳测试规划方案。

1)采用萤火虫算法，更新变迁发生序列个体的绝对亮度、吸引力、以及位置，得到本次迭代中适应度值最好的变迁发生序列个体。

2)采用差分进化算法，通过变异、交叉、选择操作更新变迁发生序列个体的位置，进而得到本次迭代中适应度值最好的变迁发生序列个体。

3)比较1)和2)中两个最优变迁发生序列个体的适应度值，选择更好的个体进入4)。

4)采用混沌优化方法，在混沌迭代次数为奇数时，改变最优变迁发生序列个体位置的某一维，为偶数时，改变最优变迁发生序列个体位置的所有维，通过这样的方式在最优变迁发生序列的一定邻域内生成M_s个混沌个体。

5)计算M_s个混沌个体的适应度值，并选出适应度值最好(测试时间最短)的变迁发生序列个体，作为本次迭代的最优变迁发生序列个体。

6)判断是否达到算法最大迭代次数，否则返回步骤4重新计算变迁发生序列的适应度值，然后进行混沌差分萤火虫算法的下一次迭代寻优，若达到则输出最优变迁发生序列个体对应的TAM分配与顺序分配方案。

为验证本发明测试方法的有效性，选取国际基准电路ITC’02 test benchmarks的2个系统：2*d695和p93791进行仿真实验。本发明的ETTPN 模型相比其他模型，程序运行时间优化率在38.18％～55.74％之间；本发明的算法改进方案即混沌差分萤火虫算法，相比改进前的基本萤火虫算法，测试时间优化率为3.14％～8.78％。

本发明公开了一种用于解决3D NoC测试规划的方法——基于增广时延变迁Petri网与混沌差分萤火虫算法的测试方法。该方法首先通过在原型Petri 网的基础之上增加时延与带抑止弧的概念，能有效描述测试规划中的IP核调度问题、简化模型；模型建立后，为了在Petri网的变迁发生序列集合中实施高效寻优，对基本萤火虫算法进行了两处改进，即分别采用单维结合多维的混沌优化方法，使基本萤火虫算法具备精细的局部寻优能力，采用与差分进化算法之间的信息共享机制，增强基本萤火虫算法的全局寻优能力。将实验结果与其他测试方法的实验结果进行比较，结果显示本发明测试方法在测试时间与程序运行时间方面都展现出较明显的优势。

需要说明的是，尽管以上本发明所述的实施例是说明性的，但这并非是对本发明的限制，因此本发明并不局限于上述具体实施方式中。在不脱离本发明原理的情况下，凡是本领域技术人员在本发明的启示下获得的其它实施方式，均视为在本发明的保护之内。