基于Prim初始种群选取优化遗传算法的三维片上网络低功耗映射

宋国治，王 铖，涂 遥，张大坤

(1.天津工业大学 计算机科学与软件学院，天津 300387； 2.云南大学 信息学院，昆明 650091)

(*通信作者电子邮箱guozhi.song@googlemail.com)

基于Prim初始种群选取优化遗传算法的三维片上网络低功耗映射

宋国治1*，王 铖1,2，涂 遥1，张大坤1

(1.天津工业大学 计算机科学与软件学院，天津 300387； 2.云南大学 信息学院，昆明 650091)

(*通信作者电子邮箱guozhi.song@googlemail.com)

针对将计算任务合理地映射到三维片上网络(NoC)的问题，提出了一种基于遗传算法(GA)的改进算法。GA具有快速随机的搜索能力，Prim算法可在加权连通图内得到最小生成树，改进算法结合了两种算法的优势，将计算任务合理地分配到各个网络节点，对于优化三维片上网络功耗和散热等问题具有很高的效率。通过仿真实验，对所提出的基于Prim算法的改进GA与基本GA的3D NoC映射算法进行了对比，仿真结果显示，基于Prim算法的改进GA平均功耗更低，从总体趋势来看，处理单元数量的增加与功耗降低幅度成正相关，在101个处理单元情况下，平均功耗比基本GA降低32%。

三维片上网络；低功耗；映射算法；遗传算法；Prim算法

0 引言

近年来，随着集成电路工艺和多核体系的飞速发展，芯片上集成的IP(Intellectual Property)核数目愈来愈多，用户对嵌入式产品功能与性能的要求也愈来愈高，总线型结构已经不能完全满足众多的刚性需求。在这个背景下，二维片上网络(Network-on-Chip, NoC)解决了SoC(System-on-Chip)面临的一系列问题，但是从根本上依然避免不了由于芯片上IP核数的增加，芯片的面积有限、功耗不断增大、芯片中全局导线的长度增加、工作频率提升空间的限制所导致的关键部件路径无法最短、功耗开销增大和连线延迟等相关问题[1]。因此，三维片上网络的概念被提出。与2D NoC相比，3D NoC的优势表现在全局互连更短、延时更低，系统性能更优秀、功耗更低、封装密度更高、芯片面积更小等方面，并且为混合芯片提供了连接方式。

在3D NoC领域中的关键性问题被美国卡内基梅隆大学(Carnegie Mellon University)的Morgan等[2]归纳为三大类：3D NoC架构、3D NoC通信和3D NoC映射。其中映射是研究如何将计算任务合理地映射到各个IP核上，这也是在片网设计阶段需要解决一个重要的研究问题，3D NoC映射算法性能的提升对最终系统的执行时间、通信时延、通信能耗等性能均有很大影响[3]。NoC映射是在已知NoC体系结构和IP核间通信量的基础上，按特定的算法将各IP核分配到NoC中各资源节点上，其中对应关系需要满足一定的条件限制，属于非确定多项式(Non-Deterministic Polynomial, NP)问题中受约束的二次分配问题。

本文在应用于三维片上网络映射的基本遗传算法基础上，在初始种群选取阶段结合Prim算法，形成一种基于Prim算法的改进遗传算法，并应用到3D NoC低功耗映射问题中，提高了搜索性能并大幅降低了功耗。本文首先介绍了遗传算法的原理，然后给出改进遗传的具体步骤，最后通过仿真实验验证算法的有效性。

1 3D NoC低功耗映射问题描述

1.1 基本概念

3D NoC映射的任务是探寻任务图上每个任务与3D NoC上资源节点之间的一种对应关系。在已知通信轨迹图和映射结构的条件下，降低网络延迟和功耗，寻找一种优秀的映射方案。

为了详细地说明映射和路由问题，本文用数学方式给出必要的定义表示NoC映射过程。

定义1 有一个任务图G∈V，应用特征图的每一个顶点vi∈V代表一个任务，并且每一条边ei, j∈E代表两个任务vi和vj间的通信，vi和vj间的数据传输量作为通信的权重。

定义2 有一个任务图M(T,P),拓扑结构中的每一个点ti∈T代表一条边，pi, j∈P代表ti到tj的一条通信路径。gi, j代表ti到tj发送一位数据的平均功耗。

1.2 能耗模型

本文的研究目标是在NoC体系结构的网络资源中最大限度地减少所消耗的能量。网络结构中的功耗与网络中的通信量有直接关系。为了估计NoC体系结构的功耗，应该使用一个基于总传输量的功耗模型，其定义如下：

ETbit=ESbit+EBbit+EWbit+ELbit

(1)

式中:ESbit、EBbit、EWbit、ELbit分别代表交换机、缓冲器、结构中的内部线和链接所消耗的能量，则1 bit数据在NoC传输一个基本长度的能耗可以表示为：

ETbit=ESbit+EBbit+EWbit

(2)

同时来自缓冲和内部线的能源消耗可以忽略不计，所以可将式(2)修改为：

ETbit=ESbit+ELbit

(3)

然后，从核心i到核心j发送1 bit数据的平均能量消耗的计算公式为：

(4)

(ni, j+1)代表数据在传送过程中数据经过的路由器的数量，如果1 bit数据通过(ni, j+1)个路由器，显然，它还通过(ni, j+1)条链接，这是所谓的核心i到核心j之间的距离跳数。式(4)表明，最小化通信核心的距离跳数可以最小化核心i到核心j之间发送1 bit数据的功耗。

1.3 种群个体向量表示

经典应用特征图PIP(Picture-In-Picture)包含8个节点，如图1所示，图中的IP核用数字1到8表示，将PIP中的节点映射到2×2×2的3D Mesh结构上。假设个体Y=(y0，y1，y2，…，yM-1)，M为任务图的IP核个数，yi为IP核编号。

将PIP映射到2×2×2的3DNoC上，3DNoC上的每个处理单元(ProcessingElement,PE)用数字t1到t8表示。

t1到t4表示第1层(图2(a))，t5到t8表示第2层(图2(b))。个体y=(6,1,2,4,8,5,7,3)，表示将IP核集(2,3,4,1,8,9,5,10,11,7,6,12)分别映射到PE集(1,2,3,4,5,6,7,8)上，映射结果如图3所示。

图1 任务通信图PIP

图2 NoC拓扑结构

图3 映射结果

2 映射算法基础

优秀的映射算法可以让系统在能耗[4-5]、延时[6]等方面的性能大为改善。近年来国内外研究学者已提出多种算法并应用于NoC映射中。目前，3DNoC的映射算法有许多种分类方法，近年来在学术界比较公认的有以下四种。

2.1 基于禁忌搜索算法

禁忌搜索(TabuSearch或TabooSearch，TS)是扩展局部领域搜索之后的一种全局逐步寻优算法。它的主体思想是对已搜索的局部最优解的对象进行标记，并在以后的迭代搜索中尽量地不出现这些对象，从而尽量做到探索不同的有效搜索途径。

常政威等[7]提出了一种有效的改进禁忌搜索(TabuSearchforNoCMapping,TSNM)算法。采用禁忌搜索和遗传算法混合优化策略，先对RoTS(RobustTabuSearch)进行简化，再实现对求解空间局部区域的集中搜索，并用COHX(COHesivecrossover)交叉操作完成分散搜索。

2.2 基于蚁群算法

蚁群优化(AntColonyOptimization,ACO)算法是通过模拟自然界中的蚂蚁的寻找路径的方式而得出的一种优化算法。

南京大学微电子设计研究所的杨盛光等基于二维网格结构NoC平台[8]，建立了统一的目标函数，降低了系统通信功耗和执行的时间，提出了一种通过优化链路负载分布进而间接降低延时的方法，并且通过蚁群算法实现了前面提到的面向能耗和延时的NoC映射。

南京大学物理系微电子设计研究所的王佳文等[9]基于基本蚁群算法(AntColonyAlgorithm,ACA)，总结出一种动态蚁群算法(DynamicAntColonyAlgorithm,DACA)。

李东生等[10]基于2DNoC的映射规则，总结出了针对3D网格NoC的通信能耗模型，并运用蚁群算法实现了面向通信能耗的NoC映射。

2.3 基于粒子群算法

粒子群算法是通过模拟自然界中的鸟类觅食行为而得出的一种优化算法，Eberhart和Kennedy从这种生物种群行为特性中得到启发并用于求解优化问题。

黄翠[11]利用量子粒子群算法具有全局收敛性、收敛速度快、寻优能力强、控制参数少以及鲁棒性等诸多优点，首次将量子粒子群算法应用到三维片上网络低功耗映射问题中，但当应用特征图规模较大时，功耗优化效率降低。针对这一问题，她又提出一种基于多样性控制量子粒子群的三维片上网络低功耗映射算法。

杨微等[12]提出一种改进的粒子群算法以及相应的算法评估模型。该算法通过引入非支配解(Pareto解)的概念对粒子群算法进行改进，使得算法能对多个评估模型参数同时优化，并且还能根据特定的应用对单个评估模型参数进行优化。

2.4 基于遗传算法

遗传算法(GeneticAlgorithm,GA)是通过模拟自然界中生物进化的自然选择和遗传中发生的繁殖、交叉和基因突变现象而得到的优化算法。

Lei等[13]采用分步式遗传算法进行映射处理，并且先后从粗、细2种粒度上进行，通过参数化的任务图的描述，算法找到一个映射的任务图的顶点的映射，使任务图的整体执行时间被最小化。

Ascia等[14]用遗传算法求解多目标优化的NoC映射，它提出了一种多目标探索映射空间网状网络基础上的芯片架构。该方法可以高效、准确地来获得帕累托映射优化性能和功耗。

张涛涛[15]提出的映射算法的设计主要依据混合型3DNoC-Bus拓扑结构中垂直总线的相关特征，创造优化算法的计算模型，通过遗传算法和回溯算法来寻找最优解。

Addo-Quaye[16]把遗传算法应用到三维片上网络映射问题，并进行求解，提出了一种基于3DMesh,降低芯片温度与网络通信开销的映射算法。

Ying等[17]提出了一种基于遗传算法的映射优化方案，这个方案主要研究了硅穿孔(ThroughSiliconVia,TSV)数目和系统性能的关系。

Wang等[18]针对3DNoC延迟感知提出基于排序的多任务遗传算法。

林华洲等[19]指出：随着3DNoC集成度的提高，低功耗映射逐渐受到了关注。他将遗传算法和贪心算法结合为一种改进的遗传算法，用以解决3DNoC低功耗映射问题。与基本遗传算法相比，基于贪心算法的改进遗传算法的搜索能力更加优秀。

3 遗传算法及改进

3.1 基本遗传算法

1975年，美国的Holland教授[20]提出了遗传算法(GA)的概念，遗传算法是通过模拟自然界中生物进化的自然选择和遗传中发生的繁殖、交叉和基因突变现象而得到的优化算法。随机初始化群体，利用此群体进行迭代，每次迭代后保留一组最优候选解，利用选择、交叉、变异对解空间中的解集进行组合，产生新的解空间，直到满足停止准则[21]。

3.2 Prim算法

基本思想 假设G=(V,E)是连通的，TE是G上最小生成树中边的集合。算法从U={u0}(u0∈V)、TE={}开始。重复执行下列操作：

在所有u∈U，v∈V-U的边(u,v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V=U为止。

此时，TE中必有n-1条边，T=(V,TE)为G的最小生成树。

3.3 改进遗传算法

3.3.1 改进遗传算法的提出

类似于其他寻找最优组合的问题，寻找从G(V,E)到P(U,F)的映射最优解，是一类NP难问题。本文的目的是要寻找一个或者一些能够在性能和寻优计算时间上获得平衡的方案。遗传算法在这两方面表现出它的优势。遗传算法适合解决3DNoC映射问题，其他优化算法在解决3DNoC映射问题上也有各自的优点，但本文主要是针对初始种群的优化，并不涉及采用何种优化算法对实验结果的影响，因此本文采用遗传算法解决3DNoC映射问题。

基本遗传算法的初始种群是随机生成的，这使得初始种群存在个体分布不均匀、初始种群质量偏低的问题。本文针对随机生成初始种群的缺陷，提出了一种采用Prim算法思想生成初始种群的改进遗传算法，Prim算法思想体现在生成种群个体上。算法的流程如图4所示。

图4 基于Prim算法的改进遗传算法流程

3.3.2 生成初始种群

基本遗传算法随机产生初始种群，产生的初始种群质量偏低，基于Prim算法的改进遗传算法体现在生成初始种群个体上，算法核心思想描述如下：假设有一个由N个IP核组成的任务图，将这些IP核从1到N进行编号，这N个正整数构成了IP核集合，首先将i放入3D NoC的第一个位置(i表示正在生成的第i个个体)，然后将i从IP核集合中删去，对此任务图运行以i为第一个节点的Prim算法产生最小生成树，按顺序记录选择节点的数组。之后在3D NoC的其他可用位置(未被占用的位置)按数组遍历放入未使用的IP核的编号并计算适应值，选择一个使得适应值最大的IP核的编号放入3D NoC的相应位置，然后将该IP核的编号从IP核集合中删去，用同种方法确定其他未被占用位置放入的IP核的编号，依此类推，最终得到一个采用Prim算法得到的个体。用同样的方法生成N个个体，然后对这N个个体进行变异操作，使之生成一定数量的邻居个体，最后对所有已生成的个体根据适应值进行排序，选择适应值最大的一定数量的个体作为初始种群。

本文提出基于Prim算法思想的初始化方法产生种群pop，主要过程如图5所示。

图5 初始化种群流程

步骤1 随机生成一个数r(1≤r≤N)，然后将这个随机数r映射个体X的第1个位置，用Prim算法产生以r为第1个节点的最小生成树的数组；

步骤2 初始化可用集P={1，2，…，N}，将r从P集合中删去；

步骤3 按数组顺序遍历可用集P中的数字n，将n放入个体X的所有可用位置，计算放入这些位置后X的适应值，从这些适应值中找到最大的适应值fit，记下n放到使得X适应值最大的位置m，把〈n,m,fit〉存到集合F；

步骤4 遍历集合F，找到fit值最大的一组元素〈n,m,fit〉，把n放到个体X的第m个位置，把n从可用集P中删去，把m从可用位置中删去；

步骤5 重复步骤3和步骤4，直到可用集P为空，当P为空时，表示产生了一个个体X，把X加入临时种群tempPop；

步骤6 将个体X的任意两个坐标数字对换，即生成一个X的邻居个体。对上述步骤生成的个体X用此方法生成20个邻居个体，将这些邻居个体都放入临时种群tempPop中；

步骤7 重复上述所有步骤N次，即生成了N个由Prim算法得到的个体和这些个体的20个邻居个体；

步骤8 从tempPop中选取适应值最大的多个个体放入pop中作为初始种群。

下面用一个任务图规模为7，往一个拓扑架构为2×2×2的片上网络做映射为例详细说明映射过程。

1)给任务图每个节点编号：0，1，2，3，4，5，6。

2)给片上网络每个处理单元编号：0，1，2，3，4，5，6，7对应(0，0，0)、(0，0，1)、(0，1，0)、(0，1，1)、(1，0，0)、(1，0，1)、(1，1，0)、(1，1，1)。

3)将任务图节点0，放到片上网络的第0号处理单元上，剩下的任务图节点有(1，2，3，4，5，6)，剩下的片上网络可用位置有(1，2，3，4，5，6，7)，利用Prim算法得出遍历数组(0，1，2，5，3，4，6，7)。

4)把任务图节点1，放到片上网络的所有可用位置：

(0，1，，，，，，)对应适应值13

(0，，1，，，，，)对应适应值12

(0，，，1，，，，)对应适应值14

(0，，，，1，，，)对应适应值17

(0，，，，，1，，)对应适应值18

(0，，，，，，1，)对应适应值19

(0，，，，，，，1)对应适应值12

选取适应值最大的一组(0，，，，，，1，)对应适应值19，剩下的任务图节点有(2，3，4，5，6)，剩下的片上网络可用位置有(1，2，3，4，5，7)。

5)把任务图节点2，放到片上网络的所有可用位置：

(0，2，，，，，1，)对应适应值16

(0，，2，，，，1，)对应适应值18

(0，，，2，，，1，)对应适应值24

(0，，，，2，，1，)对应适应值27

(0，，，，，2，1，)对应适应值21

(0，，，，，，1，2)对应适应值29

选取适应值最大的一组(0，，，，，，1，2)对应适应值29。

6)重复上述步骤，就可以得到一个体，例如(0，3，4，6，5，7，1，2)。

7)把第一次放入片上网络第0号位置的数字0换成1，重复上述步骤就可以得到(1，2,…)开头的Prim个体。

8)重复上述步骤7次，就可以得到7个Prim算法得到的个体，分别以0,1,2,3,4,5,6开头的Prim个体。

9)因为初始种群规模肯定比7大，所以，每个用Prim算法得到的个体都要进行变异操作，得到更多的个体。

10)一般是这7个个体都变异M次，解空间>种群规模F，然后从解空间中选取适应值最大的F个作为初始种群。

4 仿真实验与结果分析

本文提出的基于遗传算法的三维片上网络映射算法，运行环境是Ubuntu13操作系统，编程语言采用C++语言，编程工具是codeblocks12.11，最后采用AccessNoxim进行仿真实验得出数据。

AccessNoxim是一个由Jheng等[22]开发的将网络模型(networkmodel)、功率模型(powermodel)和热模型(thermalmodel)相结合的3DNoC系统协同仿真平台。在仿真实验的运行过程中，流量活动被网络模型聚集起来并输入到功率模型，功率模型会产生整个片上网络系统的空间和时间功耗，然后进行能量跟踪，根据给定的能量跟踪所得出的温度计算出热模型。他们基于Intel的80-core处理器的功率模型对Noxim和Hotspot进行功能上的整合，Hotspot的作用是提供架构级热模型。由于合并条件的限制，NoC仿真器需要用芯片级物理布局和功率追踪来对其架构级布局和功率跟踪进行替换。第一步加入基础三维路由器模型和垂直交叉的路由器，扩大Noxim生成三维基于用户定义的参数尺寸的NoC架构，然后插入一个模块插入结构自动转换成物理布局，这样才能很好地与HotSpot进行结合。

4.1 参数设计

拓扑结构采用3Dmesh结构，路由算法采用经典算法，最后采用AccessNoxim进行仿真实验得出数据。仿真器参数如表1所示。

表1 仿真器参数

4.2 实验结果对比与分析

本次实验对2种算法进行功耗对比，分别是基于Prim算法的改进遗传算法的映射算法和基于遗传算法的映射算法。

4.2.1 两种映射算法针对经典APCG仿真功耗对比

本次仿真实验使用了3种经典任务图(VOPD(VideoObjectPlaneDecoder)、DVOPD(DoubleVideoObjectPlaneDecoder)和MWD(Multi-WindowDisplayer))，如图6所示。

图6 经典任务图

针对不同的APCG(ApplicationCharacteristicGraph)，采用两种算法分别求解10次。

4.2.2 改进算法与基本遗传算法数据对比

仿真实验中，分别采用基于Prim算法的改进遗传算法与基本遗传算法对该任务图进行映射操作，用得到的最优解生成通信模式文件，仿真器AccessNoxim通过读取通信模式文件进行映射仿真，得到映射功耗。用实验数据分别对3种映射算法得到的最小功耗、平均功耗和最大功耗进行了比较，如图7～9所示。

图7 针对经典APCG的平均功耗比较

图8 针对经典APCG的最小功耗比较

图9 针对经典APCG的最大功耗比较

分析针对VOPD的2种映射算法仿真结果可见，在最小功耗和平均功耗方面基于Prim算法的改进遗传算法低于基本遗传算法，即采用基于Prim算法的改进遗传算法的功耗更低，但是降低的幅度较小；而在最大功耗方面基于Prim算法的改进遗传算法的功耗高于基本遗传算法的功耗，基于Prim算法的改进遗传算法与基本遗传算法的唯一区别就是生成初始种群时采用的Prim算法的改进。对任务图分别进行实验，由实验结果可知：基于Prim算法的改进遗传算法相对于基本遗传算法最小功耗减少了10.58%，平均功耗减少4.05%。其中，基于Prim算法的改进遗传算法的最大功耗高于基本遗传算法的功耗，这是由于VOPD只有16个节点(节点过少)，采用改进策略得到的初始种群容易陷入局部最优。

分析针对DVOPD的2种映射算法仿真结果可见，采用基于Prim算法的改进遗传算法的功耗更低，并且降低的幅度较大；这是由于DVOPD有32个节点，任务规模较大，采用改进策略得到的初始种群不容易陷入局部最优。由以上实验和分析可见，当任务图规模增大时，基于Prim算法的改进遗传算法的优势更为明显。由实验结果可知:基于Prim算法的改进遗传算法相对于基本遗传算法最小功耗减少了12.46%，平均功耗减少16.13%，最大功耗减少了17.4%。

分析针对MWD的2种映射算法仿真结果可见，基于Prim算法的改进遗传算法相对于基本遗传算法最小功耗减少了5.71%，平均功耗减少13.04%，最大功耗减少了12.24%。

Prim算法思想体现在生成种群个体上，提高其初始种群的质量，使得IP核布局更合理，核之间的远距离通信减少而芯片功耗降低。

4.2.3 基于随机任务图的功耗对比

采用任务生成器TGFF生成IP核数分别为13，21，41，82和101的随机APCG，针对不同IP核数的随机APCG，采用两种算法分别求解10次。采用基于Prim算法的改进遗传算法和基于遗传的映射算法对比结果如图10～12所示。

图10 针对随机APCG的平均功耗比较

图11 针对随机APCG的最小功耗比较

图12 针对随机APCG的最大功耗比较

4.2.4 平均功耗对比

当IP核数较少时，基于Prim算法的改进遗传算法相对于基本遗传算法的最小功耗降低幅度较小，在10%以内。其中，82个IP核时，基于Prim算法的改进遗传算法比基本遗传算法的功耗低了41.5%，这是由于IP核数目较少，容易导致两种算法均陷入局部最优，因此出现了在82个IP核时基于Prim算法的改进遗传算法的功耗降低幅度较大。从整体趋势来看，随着IP核数的增加，功耗降低幅度增加。

4.2.5 最小功耗比较

13个IP核时，基于Prim算法的改进遗传算法比基本遗传算法的功耗低了30%；41个核时，基于Prim算法的改进遗传算法与基本遗传算法的功耗基本相等；101个核时，基于Prim算法的改进遗传算法比基本遗传算法的功耗低了32%。

4.2.6 最大功耗比较

13个IP核时，基于Prim算法的改进遗传算法与基本遗传算法的功耗基本相等；41个核时，基于Prim算法的改进遗传算法比基本遗传算法的功耗低了25%；101个核时，基于Prim算法的改进遗传算法比基本遗传算法的功耗低了33%。

5 结语

本文介绍的改进的遗传算法在保留原始遗传算法具有的快速随机搜索特性基础上针对其随机生成初始种群过程中的缺陷，提出了一种采用Prim算法生成初始种群的方法，Prim算法思想体现在生成种群个体上，提高其初始种群的质量，使得IP核布局更合理，核之间的远距离通信减少而降低芯片功耗。通过仿真实验验证，本文提出的基于Prim算法的改进遗传算法与基本的遗传算法的3DNoC映射算法相比，仿真结果显示基于Prim算法的改进遗传算法平均功耗更低。从总体趋势来看随着处理单元数量的增加与功耗降低幅度成正相关，在101个处理单元情况下，平均功耗比基本遗传算法降低32%。

在今后的研究中发热是需要考虑的问题，随着研究的深入，将进行3DNoC发热方面的优化问题研究；并且目前实际面向应用的芯片往往都是针对于异构的拓扑结构，但是大部分3DNoC映射算法都是为解决三维规则拓扑结构上的映射提出的，因此，对于异构3D拓扑结构下低功耗映射算法的研究也将是国内外研究学者在3DNoC映射问题的一个研究重点。

)

[1] 张大坤,黄翠,宋国治.三维片上网络研究综述[J].软件学报,2016,27(1):155-187.(ZHANGDK,HUANGC,SONGGZ.Asurveyofthreedimensionalnetworkonchip[J].JournalofSoftware, 2016, 27(1): 155-187.)

[2]MORGANAA,ELMILIGIH,EL-KHARASHIMW,etal.Multi-objectiveoptimizationfornetworks-on-chiparchitecturesusinggeneticalgorithms[C]//ISCAS2010:Proceedingsof2010IEEEInternationalSymposiumonCircuitsandSystems.Piscataway,NJ:IEEE, 2010: 3725-3728.

[3] 刘炎华,刘静,赖宗声,等.基于遗传蚁群算法的片上网络映射研究[J].计算机工程，2010,36(22):262-264.(LIUYH,LIUJ,LAIZS,etal.Researchofnetworkonchipmappingbasedongeneticandantcolonyalgorithm[J].ComputerEngineering, 2010, 36(22): 262-264.)

[4]HUJ,MARCULESCUR.Energy-andperformance-awaremappingforregularNoCarchitectures[J].IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems, 2006, 24(4): 551-562.

[5] 林桦,李险峰,佟冬,等.保证QoS的片上网络低能耗映射与路由方法[J].计算机辅助设计与图形学学报,2008,20(4):425-431.(LINH,LIXF,TONGD,etal.Alowenergymappingandroutingapproachfornetwork-on-chipwithQoSguarantees[J].JournalofComputer-AidedDesign&ComputerGraphics, 2008, 20(4): 425-431.)

[6] 王雷,凌翔,胡剑浩.异构多核协作系统的混沌离散粒子群NoC映射算法[J].计算机科学,2011,38(9):298-303.(WANGL,LINGX,HUJH.NoCmappingforheterogeneousmulti-corecooperativesystembasedonchaoticdiscreteparticleswarmoptimization[J].ComputerScience, 2011, 38(9): 298-303.)

[7] 常政威,谢晓娜,桑楠,等.片上网络映射问题的改进禁忌搜索算法[J].计算机辅助设计与图形学学报,2008,20(2):155-160.(CHANGZW,XIEXN,SANGN,etal.Animprovedtabusearchalgorithmfornetwork-on-chipmapping[J].JournalofComputer-AidedDesignandComputerGraphics, 2008, 20(2): 155-160.)

[8] 杨盛光,李丽,高明伦,等.面向能耗和延时的NoC映射方法[J].电子学报,2008,36(5):937-942.(YANGSG,LIL,GAOML,etal.Anenergyanddelay-awaremappingmethodofNoC[J].ActaElectronicaSinica, 2008, 36(5): 937-942.)

[9] 王佳文,李丽,易伟,等.3DNoC映射问题的动态蚁群算法[J].计算机辅助设计与图形学学报,2011,23(9):1614-1620.(WANGJW,LIL,YIW,etal.Adynamicantcolonyoptimizationalgorithmfor3DNoCmapping[J].JournalofComputer-AidedDesign&ComputerGraphics, 2011, 23(9): 1614-1620.)

[10] 李东生,刘琪.面向通信能耗的3DNoC映射研究[J].半导体技术,2012(7)：504-507.(LIDS,LIUQ.Researchonmapping3Dnetworkonchipforcommunicationenergy-aware[J].SemiconductorTechnology,2012(7)： 504-507.)

[11] 黄翠.基于量子粒子群的三维片上网络低功耗映射算法研究[D].天津:天津工业大学,2015.(HUANGC,Researchonalow-powermappingalgorithmfor3DNoCbasedondiversity-controlledquantum-behavedparticleswarmoptimization[D].Tianjin:TianjinPolytechnicUniversity, 2015.)

[12] 杨微,张振,刘怡俊.基于改进粒子群的3D-MeshCMP片上网络映射算法[J].计算机应用研究,2013,30(5):1345-1348.(YANGW,ZHANGZ,LIUYJ.Improvedparticleswarmoptimizationalgorithmbasedmappingalgorithmfor3D-MeshCMP[J].ApplicationResearchofComputers, 2013, 30(5): 1345-1348.)

[13]LEIT,KUMARS.Atwo-stepgeneticalgorithmformappingtaskgraphstoanetworkonchiparchitecture[C]//DSD’ 03:ProceedingsoftheEuromicroSymposiumonDigitalSystemsDesign.Washington,DC:IEEEComputerSociety, 2003: 180-187.

[14]ASCIAG,CATANIAV,PALESIM.Multi-objectivemappingformesh-basedNoCarchitectures[C]//CODES+ISSS’ 04:Proceedingsofthe2ndIEEE/ACM/IFIPInternationalConferenceonHardware/SoftwareCodesignandSystemSynthesis.NewYork:ACM, 2004: 182-187.

[15] 张涛涛.热/流均衡的混合型3DNoC拓扑结构设计与映射算法研究[D].南京:南京航空航天大学,2014.(ZHANGTT.Explorationoftopologyandmappingalgorithmforthermaltrafficbalanced3DNoCbushybridarchitecture[D].Nanjing:NanjingUniversityofAeronauticsandAstronautics, 2014.)

[16]ADDO-QUAYEC.Thermal-awaremappingandplacementfor3-DNoCdesigns[C]//Proceedings2005IEEEInternationalSOCConference.Piscataway,NJ:IEEE, 2005: 25-28.

[17]YINGH,HEIDK,HOLLSTEINT,etal.Ageneticalgorithmbasedoptimizationmethodforlowverticallinkdensity3-dimensionalnetworks-on-chipmanycoresystems[C]//NORCHIP2012:Proceedingsofthe30thNorchipConference.Piscataway,NJ:IEEE, 2012: 1-4.

[18]WANGJ,LIL,PANH,etal.Latency-awaremappingfor3DNoCusingrank-basedmulti-objectivegeneticalgorithm[C]//ASICON2011:Proceedingsofthe2011IEEE9thInternationalConferenceonASIC.Piscataway,NJ:IEEE, 2011: 413-416.

[19] 林华洲,张大坤,黄翠.基于Prim算法的改进遗传算法的3DNoC低功耗映射研究[J].计算机工程与应用,2016,52(1):76-80.(LINHZ,ZHANGDK,HUANGC.Researchonlow-powermappingforthree-dimensionalnetwork-on-chipbasedonimprovedgeneticalgorithm[J].ComputerEngineeringandApplications, 2016, 52(1): 76-80.)

[20]HOLLANDJH.AdaptationinNaturalandArtificialSystems:AnIntroductoryAnalysiswithApplicationstoBiology,Control,andArtificialIntelligence[M].Cambridge:TheMITPress, 1992.

[21] 马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(4):1201-1206.(MAYJ,YUNWX.Researchprogressofgeneticalgorithm[J].ApplicationResearchofComputers, 2012, 29(4): 1201-1206.)

[22]JHENGKY,CHAOCH,WANGHY,etal.Traffic-thermalmutual-couplingco-simulationplatformforthree-dimensionalnetwork-on-chip[C]//VLSI-DAT2010:Proceedingsofthe2010InternationalSymposiumonVLSIDesignAutomationandTest.Piscataway,NJ:IEEE, 2010: 135-138.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61272006),NationalUndergraduateTrainingProgramforInnovationandEntrepreneurship(201510058050).

SONG Guozhi, born in 1977, Ph.D., associate professor.His research interests include 3D network-on-chip, heterogeneous wireless network integration.

WANG Cheng, born in 1995.His research interests include 3D network-on-chip.

TU Yao, born in 1992, M.S.candidate.His research interests include 3D network-on-chip floorplanning.

ZHANG Dakun, born in 1960, Ph.D., professor.Her research interests include 3D network-on-chip, virtual reality, combinational algorithm.

Low power mapping based on improved genetic algorithm with Prim initial population selection for 3D network-on-chip

SONG Guozhi1*, WANG Cheng1,2, TU Yao1, ZHANG Dakun1

(1.SchoolofComputerScienceandSoftwareEngineering,TianjinPolytechnicUniversity,Tianjin300387,China;2.SchoolofInformationScienceandEngineering,YunnanUniversity,KunmingYunnan650091,China)

To solve the problem of properly mapping the computational task onto a three-dimensional Network-on-Chip (NoC), an improved algorithm based on Genetic Algorithm (GA) was proposed.GA has the fast random searching ability and Prim algorithm can get the minimal spanning tree of a weighted connected graph.By combining the two algorithms’ advantages, the improved algorithm could properly assign computational tasks onto each network node, achieving a high efficiency on solving network power consumption and heat problems.The simulation experiments were carried out to compare the proposed improved GA based on Prim algorithm with GA based 3D NoC mapping algorithm.The simulation results indicate that the average power consumption of the improved GA based on Prim algorithm is lower: from the overall trend, the reduction on power consumption is positive correlated to the increase of the number of processing units, and when there are 101 processing units, the average power consumption is 32% lower than that of the traditional GA.

three-dimensional Network-on-Chip (3D NoC); low power consumption; mapping algorithm; Genetic Algorithm (GA); Prim algorithm

2016-07-30;

2016-08-07。

国家自然科学基金资助项目(61272006)；国家级大学生创新创业训练计划项目(201510058050)。

宋国治(1977—)，男，黑龙江哈尔滨人，副教授，博士，CCF会员，主要研究方向：三维片上网络、无线传感器网络、异构网络融合；王铖(1995—)，男，安徽阜阳人，主要研究方向：三维片上网络； 涂遥(1992—)，男，安徽淮南人，硕士研究生，主要研究方向：三维片上网络布局优化； 张大坤(1960—)，女，辽宁阜新人，教授，博士，主要研究方向：三维片上网络、虚拟现实、组合算法。

1001-9081(2017)01-0090-07

10.11772/j.issn.1001-9081.2017.01.0090

TP393.01

A