三维片上网络离散量子粒子群布图算法研究*

万逸君，张大坤，郑亚振

天津工业大学 计算机科学与软件学院，天津 300387

三维片上网络离散量子粒子群布图算法研究*

万逸君，张大坤+，郑亚振

天津工业大学 计算机科学与软件学院，天津 300387

三维片上网络在多种性能上均优于二维片上网络，已成为研究热点。布图算法直接影响芯片的面积和布线长度，成为三维片上网络优化设计的重要方向。提出一种基于离散粒子群算法的三维片上网络布图优化算法，与之前常使用的模拟退火算法相比，不再使用单一解局部扰动的方式得到整个解空间，该算法采用初始化随机种群并不断迭代的进化方式，具有更优的搜索能力和更快的收敛速度。仿真结果表明，采用该算法选择布图方案可以显著降低微片延迟，节省CPU计算时间，尤其是在IP核数量众多的测试用例和高注入率情况下效果更为明显，如对于ami49测试用例当注入率为100%时，基于离散量子粒子群算法的结果和基于模拟退火算法的结果相比，平均微片延迟减少了20.63%，CPU平均时间减少了69.40%。

三维片上网络；布图算法；B*-tree；离散量子粒子群算法；模拟退火算法；粒子群算法

1 引言

随着大规模集成电路技术的发展，片上系统（system-on-chip，SoC）、二维片上网络（two dimensional network-on-chip，2D NoC）相继产生。随着2D NoC规模的增大，2D NoC在面积、功耗、布局布线以及封装密度等方面都已达到了瓶颈[1]。因而三维片上网络（three dimensional network-on-chip，3D NoC）应运而生，并成为研究热点[2-4]。3D NoC通过三维集成电路堆叠技术（die stacking）将多层硅晶互相堆叠，然后通过矽晶穿孔（through silicon via，TSV）技术实现了层次芯片设计，它拥有更好的适应性和扩展性，同时减小了芯片面积。

衡量3D NoC性能的指标有很多，如微片延迟、功耗和发热等，这些性能指标均与三维芯片中IP核的布图方式密切相关。3D NoC布图方式可分为两大类，即二分结构（slicing structure）[5]和非二分结构（none slicing structure）[6]。二分结构是指通过横向或纵向迭代切割布图区域，从而得到布图方案，如图1所示。其中（a）是二分结构布图方案，（b）是相应的切割树，这种结构在实际中有许多应用[7-8]。非二分结构不能通过迭代切割获得，而只能通过总体布局设计而获得，如图2所示，有许多二分结构的应用实例[9-10]。一般来说，二分结构实现起来更加简单，但对布图图形以及布图方式要求较高；而非二分结构更具普遍性，应用更为广泛，针对非二分结构研究三维片上网络布图优化算法更具有普遍意义。

Fig.1 Slicing structure and its cutting tree图1 二分结构及其对应的切割树

Fig.2 None slicing structure图2 非二分结构

在计算机中，需要使用表示布图的编码方法，即使用一个数字或者字母的序列来表示一种布图方案。二分结构常使用的表示法有二叉树[11]及正则波兰表达式[12]；非二分常使用的表示法有SP（sequence pair）[13]、BSG（bounded-sliceline grid）[14]、TCG（transitive closure graph）[15]、ACG（adjacent constraint graph）[16]、O-tree[17]和 B*-tree[18]。

目前，3D NoC布图优化算法主要有基于模拟退火算法（simulated annealing，SA）的布图优化算法[19]、基于粒子群算法的布图优化算法（particle swarm optimization，PSO）[20]以及基于模拟退火改进的粒子群算法的布图算法。分析现有的这些算法可知，它们都通过单一解扰动方式获得下一个可行解，收敛速度较慢。当三维片上网络规模增大、结构复杂度增加时，布图可行方案数会急剧增加，解的扰动次数也随之增加，求解时间将大幅度增加，因而导致求解效率显著下降。为了提高求解效率等，本文提出一种基于离散粒子群算法的三维片上网络布图优化算法，该算法采用初始化随机种群并不断迭代的进化方式，具有更优的搜索能力和更快的收敛速度。

2 基本设计

2.1 3D NoC架构和设计流程

本文采用3层的片上网络，如图3所示。该结构是美国North Dakota State大学Cristinel Ababei教授等提出的[21]，并开发了基于该结构的仿真平台vnoc3。其中，第1层、第3层片上放置任意尺寸大小的异构IP核；第2层是标准mesh结构，放置路由器。

Fig.3 Atask graph mapping 3 layer structure图3 一个任务图映射3层结构

这种3层结构保持了网络层的规则性，使3D NoC的整体设计更加简单，设计流程如图4所示。

Fig.4 3D NoC design process图4 3D NoC设计流程

（1）将不同的任务映射到IP核上，并根据任务图，使用hMetis图划分器，按照最小割边的标准，将IP核分为两层。

（2）分层使用布图算法，先用布图算法将一部分IP核分配到第1层中，再分配剩下的IP核到第3层；使用布图算法时加上了垂直方向的约束条件，以减少链路的长度。将布图算法在每一层应用10次，保存其中最优的3个布图方案。

（3）在3个布图方案中，为每层IP核分配路由器。首先将第2层设置为R×R标准mesh结构，保证至少每一个IP核都能分配到一个路由器（称之为直接拓扑），并不是每一个IP核都能连接上垂直方向的路由器，因此有的IP核需要使用额外的链路来连接路由器，这些额外链路也会影响微片的延迟，vnoc3中将此问题看作一个线性分配问题，应用Kuhn-Munkres算法来解决。

（4）实现周期内的精准模拟，模拟出微片的平均延迟和运行时间等。

对ami33测试用例使用这种设计结构，其中的一种布图方案如图5所示，mesh中的红色路由器表示没有连接IP核，路由器上的斜线表示额外链路。

2.2 B*-tree编码表示及更新算法

2.2.1 B*-tree编码表示法

B*-tree布图表示法由Chang等人首次提出[22]，它用有序二叉树B*-tree表示布图方案，是一种自左下角向右上角直至全局的紧凑布图表示法，即在布图方案中没有任何一个模块可以向其左下方移动，优点是每一个可行的布图方案只对应唯一的一个B*-tree，反之亦然。

布图中模块Mi与B*-tree中的节点Ni一一对应，定义B*-tree的节点和B*-tree结构为：

节点中的id、parent、left、right分别记录此节点、父节点、左孩子、右孩子的id号；rotate是模块能否旋转角度的标志；B*-tree中nodes_list记录所有Node节点的集合；nodes_root记录根节点的id号，可以构造一棵B*-tree。

Fig.5 Layout and topology scheme of ami33 using 3 layer structure图5 使用3层结构的ami33的一种布图和拓扑方案

设(x,y)为模块M的左下点坐标，w、h分别为模块M宽和高，如果B*-tree有Ni、Nj两节点，对应的模块Mi、Mj几何关系如图6所示，规则如下。

Fig.6 Feasible floorplanning and its corresponding B*-tree图6 可行布图方案及其对应的B*-tree

（1）根节点对应整个布图最左下角模块，其坐标(xroot,yroot)=(0,0)。

（2）如果节点Nj是节点Ni的左孩子，那么在布图方案中Mj紧邻着Mi，并且是Mi右侧最下方尚未在布局方案中的模块，且xj=xi+wi。

（3）如果Nj是Ni的右孩子，那么模块Mj紧挨着模块Mi在其上侧，而且两个模块在X轴的坐标相等，即xi=xj。

2.2.2 基于B＊-tree的布图位置更新算法

对于已有的一棵B*-tree，将其转换成一个布图方案就需要按照树深度优先遍历的顺序，将每一个节点对应的模块加入布图方案中，更新其坐标以及布图方案的轮廓边界。在放置一个模块且更新边界的算法中，定义轮廓界限的结构为：

其中，front记录本轮廓界限的前一段轮廓对应的模块序号；back记录本轮廓界限的后一段轮廓对应的模块序号。如图7（a）所示，每一个模块都用(x,y)以及(rx,ry)两组坐标来表示它的位置以及范围，IP0对应的轮廓Contour0是最小的点组成的虚线，Contour0.front=1,Contour0.back=2，最开始已知IP0的坐标(x0,y0)=(xroot,yroot)=(0,0)。

Fig.7 B*-tree and update coordinates and contours图7 B＊-tree及更新坐标和轮廓界限

当前布图方案中已有IP0、IP1以及IP2这3个模块，并已知它们的左下角坐标分别为(x0,y0)、(x1,y1)以及 (x2,y2)，右上角坐标分别为 (rx0，ry0)、(rx1，ry1)以及(rx2,ry2)，此时布图的轮廓界限由Contour0、Contour1、Contour2组成，将要加入的模块为IP3，根据布图方案对应的B*-tree来更新布图方案。

（1）判断要插入的节点，节点3在B*-tree中是节点1的右孩子，如图7（b）所示。

（2）IP3应该放置在IP1的上方，且IP3的x3与其父节点对应的模块IP1的x1相等，更新x3=x1,y3与父节点模块的ry1相等，更新y3=ry1，而且IP3的rx3=x3+w（w为IP3模块的宽度），ry3=y3+h（h为IP3模块的高度）。

（3）由于加入了新的节点要更新布图轮廓，更新IP0对应的轮廓Contour0以及IP3对应的轮廓Contour3，Contour0.front=3,Contour3.back=0。

（4）比较rx3与rx1，如果rx3＜rx1，则更新IP3所对应的轮廓Contour3以及IP1所对应的轮廓Contour1，Contour3.front=1,Contour1.back=3；否则IP3所对应的轮廓Contour3将代替IP1所对应的轮廓Contour1，Contour3.front=Contour1.front，如果IP1轮廓的front不为空的话，(Contour1.front).back=3，如此迭代更新，直至形成整个布图方案。

3 3D NoC离散量子粒子群布图优化算法研究

3.1 目标函数选取

3D NoC布图优化，就是对于给定的测试用例（由N个面积、宽高方向数值不等的IP核组成）使用B*-Tree表示方法编码，按照优化布图算法，把N个模块分配到3D NoC结构的不同层上，即依据目标函数求出布图方案的编码序列，并且按照布图规则分配模块的摆放位置，并且它们互不重叠。它实际上是一个 NP（non-deterministic polynomial）问题[23]，由于布图方案直接影响芯片的面积、布线的长度，微片延迟、CPU时间等衡量3D NoC芯片性能的指标会随着芯片面积、布线长度的增加而增加，因此它的目标函数可以定义如下：

其中，A、W分别表示芯片的面积和布线长度。A、W都由布图方案得到的模块信息计算，使用最外层轮廓对应的模块坐标计算整个芯片的面积，使用模块的坐标计算曼哈顿长度表示布线长度。α是由用户设置的权值系数，在0,1之间随机取值，用来调整面积和线长的比重，本算法选取α=0.25（多次实验表明α=0.25效果最好）。

3.2 标准量子粒子群优化算法

量子粒子群优化（quantum-behaved particle swarm optimization，QPSO）算法是Sun等人提出的[24]，他们对人类学习模式和群体智能的基本特征进行了深入研究[25]，建立了基于量子势阱的粒子群模型，并且提出了量子行为的粒子群优化算法。本文选用QPSO算法是因为它同PSO一样，具有总结自身和向群体或领域内优秀粒子学习的能力，整个种群不断进化迭代，其收敛速度快，能更好地适用于解空间较大的问题，如大型架构的优化布局问题；粒子群算法（particle swarm optimization，PSO）存在着参数较多且要调整相应的取值范围等缺点，而在QPSO算法中，控制参数较少，除基本参数如种群规模和迭代次数之外，唯一需要设定的参数就是算法的收缩-扩张因子（contraction-expansion coefficient，CE因子）[26]。

一般量子粒子群算法的进化方程如式（2）～（4）所示：

其中，N表示粒子种群的规模，即解方案的数量；M表示解的维度；mbest(t)表示第t次迭代平均最好的位置；pbesti,j(t)表示粒子i在第t次迭代的历史最佳位置在j维的坐标值；gbestj(t)表示第t次迭代的全局最佳粒子位置在第j维的坐标值；φ是0,1之间的随机分布数；Xi,j(t)表示粒子i第t次迭代在j维的坐标值；u是0,1之间的随机分布数；α是收缩-扩张系数，一般处于1.0到0.5之间，并且呈线性递减，如式（5）所示：

其中，T为总迭代次数；count为当前迭代次数；αmax=1.0,αmin=0.5。

3.3 基于离散量子粒子群算法的布图优化算法设计

一般的QPSO算法大多都是针对连续的解空间，而对于3D NoC的布局问题，它的解空间是离散的，且需要与B*-tree编码相对应，因此需要重新定义离散量子粒子群优化算法（discrete quantum-behaved particle swarm optimization，DQPSO）、粒子所代表的意义和DQPSO算法中的一些操作。

3.3.1 粒子结构的定义

为了结合量子粒子群算法的特点，方便粒子进化操作，本文定义的粒子结构为：

Quantum与B*-tree中的节点相对，id代表它的序号，left、right取值为1或0，1代表有左孩子或右孩子，0代表没有。每一个Quantum序列设为{Q1,Q2,…,QM}，如果它可以生成一棵B*-tree，其中Quantum的id出现顺序代表一棵树的广度优先遍历顺序，Quantum的left、right代表节点排列的疏密程度，left、right中1越多代表生成的B*-tree节点排列越稠密，同时序列也对应一种布图方案；如果Quantum序列不能生成一棵B*-tree就需要对解进行修正，重新随机选择Quantum序列中left、right的0、1值直到能构成B*-tree为止。

3.3.2 初始种群的生成

应用DQPSO算法实现布图，首先可以通过对B*-tree的局部扰动方法生成初始种群。局部扰动同时可以完成局部搜索，以及增加解空间的多样性，扰动方法有：

（1）旋转节点。随机选取节点，如果节点有可旋转标志，此时交换模块的宽和高。

（2）交换节点。随机选取两个节点，并交换它们的位置，对应的模块布图位置也相应交换。

（3）删除和插入节点。随机选取一个节点删除它，将它的左、右子树，添加到其父节点之下，同时随机选取另一个节点并把它作为父节点，在它下面插入已经删除的节点。

同时为了增大局部搜索，以及保存部分模块已有的位置优势，本文增加了两种扰动方式。

（4）交换子树。任意选择两个节点，其中一个节点不能是另一个节点的祖先，找到两棵以这两个节点为根的子树，并交换这两个子树。

（5）删除和插入树。任意选择两个节点a和b,a代表要删除的子树的根节点，b代表要插入位置的父节点，其中a不能是b的祖先，将子树从a删除，插入b位置。

3.3.3 粒子进化操作说明

已有QPSO算法的进化公式不适用于本文定义的与B*-tree相对应的离散解的结构，需要对一系列的进化操作重新解释说明，说明如下。

说明1式（2）中，初始有N个Quantum序列，每个序列M维，把它们设为初始的pbesti，0≤i≤N-1。在第t次迭代中，求解种群平均最优位置mbest={mbest1,mbest2,…,mbestM}，N个pbest，也就是N个Quantum序列 {Q1,Q2,…,QM}，pbesti={Q1,Q2,…,QM}，Qj中的id可能为M个模块中的任意一个，即0≤Qj.id≤M-1。对于mbest第j个维度的值mbestj，求解N个pbest在维度j中的不同id号出现的次数，即如果Qj.id=k,0≤k≤M-1，计算N个pbest第j维Qj.id中k出现的次数，记录下出现最多的id号k以及k出现的次数n，计算n/N，如果大于1/N，证明k出现的几率大于随机选择，则mbestj.id=k，否则随机生成0到M-1的任意数L，则mbestj.id=L。同样记录下N个pbest第j维Qj.left和n，计算n/N，如果大于1/2，表明1出现的次数大于0出现的次数，则mbestj.left=1，如果小于1/2，mbestj.left=0，如果等于1/2，则随机生成0或1。同理right也是如此。

说明2式（3）中，在第t次迭代中，求解第i个粒子的Pi,j,0≤i≤N-1,1≤j≤M。φ×pbest可以理解为以φ的概率收敛到自身历史最佳位置pbest，同时以1-φ的概率收敛到全局最佳位置gbest，需要随机产生一个0到1之间的随机数r，如果r＜φ,Pi,j=pbesti,j，否则Pi,j=gbestj，并且为了增加收敛速度，取φ=fpbest/(fpbest+fgbest),fpbest、fgbest分别代表每个粒子历史最优解以及全局最优解的适应值。

说明3式（4）中，表示迭代次数从第t次到t+1次粒子位置的更新。先定义mbest-Xi可以理解为平均最优位置与第i个解的位置之差，{mbest1,mbest2,…,mbestM}与{Xi,1,Xi,2,…,Xi,M}之差Vi，如果mbestj=Xi,j，则Vi,j取0，表示位置不变，否则取1，表示位置变化，如果Vi,j=0，说明在第t+1次位置不更新，保持Pi,j的值不变，如果Vij=1，生成0到1的随机数k。从概率角度，当k≥α时，产生随机数u，如果u≤0.5,Xi,j(t+1)的结果取值为(Pi,j(t)+10×k)mod(M)，否则结果取值为|Pi,j(t)-10×k|mod(M)，当k＜α时，保持Pi,j的值不变。

3.3.4 离散量子粒子群布图优化算法的实现过程

DQPSO布图优化算法的流程图如图8所示。

（1）初始化一棵二叉树，并通过扰动方式生成初始种群，种群规模为N；然后求出这N个个体的适应值，记录每一个适应值fpbesti,i取值在0到N-1之间，也就是初始化这N个个体的历史最优值；同时记录它们的历史最优位置pbesti，选取fpbesti中最优的值记为全局最优值fgbest，全局最优位置为gbest，设置初始迭代次数记录值count为1。

（2）由这N个个体的历史最优位置，计算出平均最佳位置mbest。

（3）根据fpbesti和fgbest计算出φ和相应的位置Pij。

（4）计算收缩-扩张系数α，开启每一个粒子的进化过程，随机生成0到1之间的随机数u，更新每一个粒子位置，验证每一个位置是否合法，即能否生成一个新的B*-tree，如果不能，就要修正这个新位置，使之能构成B*-tree。

（5）根据N个新解生成的二叉树布图方案，计算出适应值，如果小于这个解的历史最优值，随即更新历史最优值和其相应位置，如果这个新值同时小于已有的全局最优值，那么全局最优值和其位置也相应更新，否则保持原值不变。

（6）查看是否达到最大的迭代次数，以及是否达到设定的收敛条件，如果达到则执行（8），否则执行（7）。

（7）迭代次数记录值count加1，执行（2）。

Fig.8 DQPSO floorplanning process图8 离散量子粒子群布图优化流程

（8）迭代结束，输出保存的全局最优值以及全局最优位置也就是最优解序列。

4 仿真实验及分析

4.1 仿真器与仿真环境

为了验证本文提出的3D NoC离散量子粒子群布图优化算法，采用VNOC3仿真器进行仿真。它是在Linux系统下，使用C++语言开发的。仿真实验的硬件环境：CPU为Intel®CoreTMi5-4590，主频为3.30 GHz，内存为8 GB的微型计算机；采用了VMware虚拟机以及Centos操作系统。

4.2 实验用例与仿真过程

实验中使用了常用的MCNC（Microelectronics Centre of North-Carolina）典型测试用例，其属性值如表1所示。

Table 1 Attribute value of experimental use case表1 实验用例的属性值

vnoc3采用Elmore[27]延迟公式来估算物理链路以及IP核与路由间额外链路的延迟。为了测试本文算法的优势，将基于离散量子粒子群算法的实验数据与基于传统的模拟退火算法[21,28]、改进的基于模拟退火的粒子群算法[29]的实验数据进行对比，SA算法初始温度为1，停止温度为0.1；PSO与本文使用的DQPSO算法初始种群为100，迭代总次数为500。

4.3 仿真结果与分析

4.3.1 微片延迟对比

3种算法在6种不同的测试用例中，随着注入率从20%到100%的变化，平均微片延迟的变化如图9所示。

由图9的6张图可以看出，微片延迟整体随着注入率增加而增加。6个测试用例可以分成3组：（1）IP核数量较少，如图（a）、（b）所示的apte、xerox；（2）IP核横纵相差较大，如图（c）所示的hp；（3）IP核数量较多，如图（d）、（e）、（f）所示的ami25、ami33、ami49。由图9可见在组（1）中，采用3种算法的微片延迟相差不大，算法优势不明显。在组（2）的hp中，在注入率小时，3种算法的微片延迟基本相同，当注入率增大到80%时，虽然延迟仍然上升，但是DQPSO算法的微片延迟明显小于其他两种算法的延迟，在注入率为100%时，DQPSO算法的微片延迟比传统SA算法减少了21.85%，比PSO算法减少了53.17%。在组（3）中，都是IP核较多的用例，其中IP核之间通讯较为复杂，选择ami49进行比较，当注入率小于60%时，3种算法的微片延迟基本相同，当注入率大于60%时，微片延迟明显上升，但是DQPSO算法的上升速度低于其他两种算法的上升速度，SA算法与PSO算法的微片延迟基本相同；当注入率达到100%时，DQPSO算法的微片延迟比SA算法减少了20.63%，比PSO算法减少了23.69%。由以上数据分析，组（2）用例和组（3）用例这种网络规模大的情况下，解空间急剧增加，DQPSO算法不是依靠随机扰动的方法，能快速寻找到较优解，减少陷入局部极值，使链路长度和面积更小，使链路延迟更短，路由分配更合理。

4.3.2 平均CPU时间的对比

3种算法所消耗的CPU平均计算时间对比如图10所示。可以看出SA、PSO和DQPSO算法所消耗的CPU平均计算时间在apte、xerox两个测试用例中相差不大，从hp开始DQPSO算法的优势比较明显，尤其在ami49中，DQPSO算法所消耗的CPU平均计算时间比SA算法减少了69.40%，比PSO算法减少了46.55%，是因为hp用例中核纵横比平均值和标准差大。后面3个用例中，IP核较多，都导致解空间较大，因为DQPSO采用种群迭代、粒子聚集的方式，所以收敛速度更快。

4.3.3 算法的稳定性分析

同时随机对3种算法选取了10次实验结果，通过每次实验结果的变化趋势分析算法的稳定性。由于组（1）用例IP核较少，微片延迟较低，每次实验结果相差不大，效果不明显。因此，实验中选用布图方案多，结果性能相差大的用例，如组（2）的hp与组（3）的ami49用例来分析。

为了更直观地观察实验结果，本文计算出每种算法在固定注入率下10次实验结果的标准差，标准差越接近0，证明结果的一致性越高。

Fig.9 Latency changes with injection of 3 algorithms in 6 testcases图9 6种测试用例中3种算法随注入率变化的延迟变化

Fig.10 CPU time changes with injection of 3 algorithms in 6 testcases图10 6种测试用例中3种算法随注入率变化的CPU平均时间变化

hp用例标准差如图11所示，在开始注入率由20%增加到70%的过程中，10次实验的结果一致性较强；但在注入率到达80%之后，DQPSO算法的标准差明显低于另外两种算法；在到达100%时，DQPSO算法的标准差比SA算法减少了约95.32%，比PSO算法减少了约74.50%。说明当测试用例中IP核长宽相差较大时，提高注入率，SA及PSO算法得到的结果差距大，算法不稳定；DQPSO算法更加稳定，能得到更准确的解。

ami49用例标准差如图12所示，在开始注入率由20%增加到50%的过程中，10次实验的结果一致性较强；但在注入率到达60%之后，DQPSO算法的标准差明显低于另外两种算法；在到达100%时，DQPSO算法的标准差比SA算法减少了约50.94%，比PSO算法减少了约29.63%。说明当测试用例中IP核数量较多时，提高注入率DQPSO布图算法得到的结果更准确，更具一般性。

Fig.11 Standard deviation of 3 kinds of algorithms in hp图11 hp用例中3种算法微片延迟的标准差

Fig.12 Standard deviation of 3 kinds of algorithms in ami49图12 ami49用例中3种算法微片延迟的标准差

4.3.4 芯片面积对比

3种算法在MCNC的6种测试用例下的芯片面积对比如图13所示。

如图13所示，使用DQPSO算法，面积略有下降，但是效果不明显，apte中DQPSO选择的芯片面积是SA的89.21%；ami49中DQPSO选择的芯片面积是SA的94.63%。DQPSO算法对芯片面积优化方面的优势不大。

5 结束语

本文提出了一种基于离散量子粒子群算法并与B*-tree编码方式相结合的布图优化算法，用以解决异构3D NoC芯片的布图问题；根据布图问题解空间离散化的特点，重新定义了量子粒子群算法的实现过程；初始化一个随机可行解的种群，通过进化迭代来慢慢收敛于全局最优解，避免容易陷入局部极值，这样大大地提高了解的收敛速度，减少了计算时间，更快地得到了更优的布图方案。

仿真实验结果表明，本文提出的基于DQPSO的布图算法在IP核较多，IP核形状长宽比较大的情况下，微片延迟明显减少，CPU平均运行时间也大幅减少，同时算法标准差最小，说明DQPSO算法更稳定。

在未来的研究中，可以适当增加DQPSO算法中解的多样性，以便更好地寻找更优解；同时可以把布图算法引入到3D NoC的功耗、发热等性能指标验证中，进一步提高3D NoC的性能。

[1]Zhang Dakun,Song Guozhi,Lin Huazhou,et al.Double improved genetic algorithm and low power task mapping in 3D networks-on-chip[J].Journal of Computer Research and Development,2016,53(4):921-931.

[2]Yadav S,Laxmi V,Gaur M S.A power efficient dual link mesh NoC architecture to support nonuniform traffic arbitration at routing logic[C]//Proceedings of the 29th International Conference on VLSI Design and 15th International Conference on Embedded Systems,Kolkata,India,Jan 4-8,2016.Washington:IEEE Computer Society,2016:69-74.

[3]Jafri A,Baghdadi A,Najam-Ul-Islam M,et al.Heterogeneous multi-ASIP and NoC-based architecture for adaptive parallel TBICM-ID-SSD[J].IEEE Transactions on Circuits&Systems II Express Briefs,2017,64(3):259-263.

[4]Rezaei S H S,Modarressi M,Daneshtalab M,et al.A threedimensional networks-on-chip architecture with dynamic buffer sharing[C]//Proceedings of the 24th Euromicro Inter-national Conference on Parallel,Distributed,and Network-Based Processing,Heraklion,Greece,Feb 17-19,2016.Washington:IEEE Computer Society,2016:771-776.

[5]Zhou Hongxia,Sham C W,Yao Hailong.Slicing floorplans with handling symmetry and general placement constraints[C]//Proceedings of the 2016 IEEE Computer Society Annual Symposium on VLSI,Tampa,USA,Jul 9-11,2016.Washington:IEEE Computer Society,2014:112-117.

[6]Alpert C J,Mehta D P,Sapatnekar S S.Handbook of algorithms for physical design automation[M].Boston,USA:Auerbach Publications,2008:139-142.

[7]Young F Y,Wong D F,Yang H H.Slicing floorplans with range constraint[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2000,19(2):272-278.

[8]Yuen W S,Young F Y.Slicing floorplan with clustering constraints[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2003,22(5):652-658.

[9]Ma Qiang,Xiao Linfu,Tam Y C,et al.Simultaneous handling of symmetry,common centroid,and general placement constraints[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2011,30(1):85-95.

[10]Chou P Y,Ou H C,Chang Yaowen.Heterogeneous B*-trees for analog placement with symmetry and regularity considerations[C]//Proceedings of the 2011 International Conference on Computer-Aided Design,San Jose,USA,Nov 7-11,2011.Washington:IEEE Computer Society,2011:512-516.

[11]Otten R H J M.Automatic floorplan design[C]//Proceedings of the 19th Design Automation Conference,Las Vegas,USA,Jun 14-16,1982.Piscataway,USA:IEEE,1982:261-267.

[12]Wong D F,Liu C L.A new algorithm for floorplan design[C]//Proceedings of the 23rd ACM/IEEE Design Automation Conference,Las Vegas,USA,Jun 29-Jul 2,1986.Piscataway,USA:IEEE,1986:101-107.

[13]Murata H,Fujiyoshi K,Nakatake S,et al.Rectangle-packingbased module placement[C]//Proceedings of the 1995 International Conference on Computer-Aided Design,San Jose,USA,Nov 5-9,1995.Washington:IEEE Computer Society,1995:535-548.

[14]Nakatake S,Fujiyoshi K,Murata H,et al.Module placement on BSG-structure and IC layout applications[C]//Proceedings of the 1996 International Conference on Computer-Aided Design,San Jose,USA,Nov 10-14,1996.Washington:IEEE Computer Society,1996:484-491.

[15]Lin Jaiming,Chang Yaowen.TCG:a transitive closure graphbased representation for non-slicing floorplans[C]//Proceedings of the 38th Annual Design Automation Conference,Las Vegas,USA,Jun 18-22,2001.New York:ACM,2001:764-769.

[16]Zhou Hai,Wang Jia.ACG-adjacent constraint graph for general floorplans[C]//Proceedings of the 30th International Conference on Computer Design,San Jose,USA,Oct 11-13,2004.Washington:IEEE Computer Society,2004:572-575.

[17]Guo Peining,Takahashi T,Cheng C K,et al.Floorplanning using a tree representation[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2001,20(2):281-289.

[18]Chen T C,Chang Yaowen.Modern floorplanning based on B*-tree and fast simulated annealing[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2006,25(4):637-650.

[19]Vorwerk K,Kennings A,Greene J W.Improving simulated annealing-based FPGA placement with directed moves[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2009,28(2):179-192.

[20]Chen Guolong,Guo Wenzhong,Cheng Hongju,et al.VLSI floorplanning based on particle swarm optimization[C]//Proceedings of the 3rd International Conference on Intelligent System and Knowledge Engineering,Xiamen,China,Nov 17-19,2008.Piscataway,USA:IEEE,2008:1020-1025.

[21]Paulo V D,Cristinel A.3D network-on-chip architectures using homogeneous meshes and heterogeneous floorplans[J].International Journal of Reconfigurable Computing,2010:603059.

[22]Chang Y C,Chang YW,Wu G M,et al.B*-trees:a new representation for non-slicing floorplans[C]//Proceedings of the 37th Annual Design Automation Conference,Los Angeles,USA,Jun 5-9,2000.New York:ACM,2000:458-463.

[23]Garey M R,Johnson D S.Computers and intractability:a guide to the theory of NP-completeness[M].New York:W H Freeman&Company,1979:8-10.

[24]Sun Jun,Feng Bin,Xu Wenbo.Particle swarm optimization with particles having quantum behavior[C]//Proceedings of the Congress on Evolutionary Computation,Portland,USA,Jun 19-23,2004.Piscataway,USA:IEEE,2004:1571-1580.

[25]Sun Jun.Research on quantum behaved particle swarm optimization algorithm[D].Wuxi:Jiangnan University,2009.

[26]Yang Chuanjiang,Liu Qing,Huang Zhen.One method of improving quantum-behaved particle swarm optimization[J].Computing Technology andAutomation,2009,28(1):100-103.

[27]Rabaey J M.Digital integrated circuits:a design perspective[M].Upper Saddle River,USA:Prentice Hall,1996:274-278.

[28]Wang Lianlian.Research on the routing algorithm of the network routing algorithm based on the heterogeneous layout[D].Tianjin:Tianjin Polytechnic University,2013.

[29]Song Guozhi,Zhang Dakun,Tu Yao,et al.Improved algorithm for 3D NoC floorplan based on particle swarm optimization[J].Computer Science,2015,42(7):114-117.

附中文参考文献：

[1]张大坤,宋国治,林华洲,等.二次改进遗传算法与3D NoC低功耗映射[J].计算机研究与发展,2016,53(4):921-931.

[25]孙俊.量子行为粒子群优化算法研究[D].无锡:江南大学,2009.

[26]杨传将,刘清,黄珍.一种量子粒子群算法的改进方法[J].计算技术与自动化,2009,28(1):100-103.

[28]王莲莲.基于异构布局的三维片上网络路由算法的研究[D].天津:天津工业大学,2013.

[29]宋国治,张大坤,涂遥,等.一种改进的基于粒子群的三维片上网络优化布局算法[J].计算机科学,2015,42(7):114-117.

Research on Floorplanning Algorithm Based on Discrete Quantum Particle Swarm Optimization in Three Dimensional Network-on-Chip*

WAN Yijun,ZHANG Dakun+,ZHENG Yazhen

School of Computer Science&Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China

2016-10,Accepted 2016-12.

The performance of three dimensional network-on-chip is much better than that of two dimensional networkon-chip in many aspects,so that it has become a hot research topic.The floorplanning algorithm directly affects the chip size,wiring length,and becomes the significant direction of the optimization design in three dimensional networkon-chip.This paper proposes a floorplanning optimization algorithm based on discrete quantum-behaved particle swarm algorithm.Compared with the simulated annealing algorithm commonly used in the previous research,this algorithm initializes the random population and uses the evolutionary way,instead of using a local single solution perturbation method to get solution space,so it has better search ability and faster convergence speed.Simulation results show that using this algorithm can select floorplanning scheme which can reduce flit latency and save CPU computing time.It has significant effect especially in test cases which has more IP cores and high injection rate.In ami49 experiment with 100%of the injection rate,compared with the simulated annealing algorithm,the average flit latency of this algorithm reduces 20.63%;while the average CPU time of this algorithm reduces 69.40%.

three dimensional network-on-chip;floorplanning algorithm;B*-tree;discrete quantum-behaved particle swarm optimization;simulated annealing;particle swarm optimization

+Corresponding author:E-mail:zhangdakun2002@163.com

10.3778/j.issn.1673-9418.1610016

*The National Natural Science Foundation of China under Grant No.61272006(国家自然科学基金).

CNKI网络优先出版:2016-12-07,http://www.cnki.net/kcms/detail/11.5602.TP.20161207.0922.012.html

WAN Yijun,ZHANG Dakun,ZHENG Yazhen.Research on floorplanning algorithm based on discrete quantum particle swarm optimization in three dimensional network-on-chip.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1953-1964.

A

TP393

WAN Yijun was born in 1988.She is an M.S.candidate at Tianjin Polytechnic University.Her research interests include 3D network on chip and its floorplanning algorithm.

万逸君（1988—），女，天津工业大学硕士研究生，主要研究领域为三维片上网络和片上网络布图算法。

ZHANG Dakun was born in 1960.She received the Ph.D.degree in computer application technology from Northeastern University in 2004.Now she is a professor and Ph.D.supervisor at Tianjin Polytechnic University.Her research interests include network on chip,combinational algorithm and virtual reality technology.

张大坤（1960—），女，辽宁阜新人，2004年于东北大学获得博士学位，现为天津工业大学教授、博士生导师，主要研究领域为片上网络，组合算法，虚拟现实技术。

ZHENG Yazhen was born in 1989.He is an M.S.candidate at Tianjin Polytechnic University.His research interests include 3D network on chip and topology.

郑亚振（1989—），男，天津工业大学硕士研究生，主要研究领域为三维片上网络和片上网络拓扑结构。