一种降低三维片上网络功耗的映射方法

摘要

本发明提供了一种降低三维片上网络功耗的映射方法，属于三维大规模集成电路设计与制造、网络拓扑与图论以及智能优化算法的交叉学科领域。该方法包括：S1，生成初始种群，具体包括以下步骤：A1，将数字i放到个体X的第一个位置；A2，初始化可用集P＝{1,2,3,...,N}，N为CTG的IP核个数，将i从可用集P中删去；A3，任意选取可用集P中的一个数字n，将n放入个体X的所有可用处理单元的位置，计算放入这些位置后X的适应值，从这些适应值中找到最大的适应值Fit，记下n放到使得X的适应值最大的位置m，把 存到集合F中；A4，遍历集合F，找到Fit值最大的一个元素 。

权利要求

1.一种降低三维片上网络功耗的映射方法，其特征在于：设通信轨迹图CTG(N,C)为有向图，N为顶点集，节点ni∈N表示一个IP核，C为边集，有向边cij∈C表示节点ci到节点cj的边，wij表示边cij的权重；

设拓扑结构图TAG(T,E)为有向图，T为处理单元PE集合，ti∈T表示一个处理单元PE，E为边集，有向边eij表示节点ti到节点tj的边；每个处理单元PE能够向任何一个其他处理单元PE发送数据，CTG中的一个IP核能够映射到任何一个可用处理单元PE上；

所述方法包括：

S1，生成初始种群，具体包括以下步骤：

A1，将数字i放到个体X的第一个位置；

A2，初始化可用集P＝{1,2,3,...,N}，N为CTG的IP核个数，将i从可用集P中删去；

A3，任意选取可用集P中的一个数字n，将n放入个体X的所有可用处理单元的位置，计算放入这些位置后X的适应值，从这些适应值中找到最大的适应值Fit，记下n放到使得X的适应值最大的位置m，把存到集合F中；所述A3中的适应值＝maxF-通信总量，所述通信总量为已放到PE上的IP核之间的通信总量，适应值的上界maxF为用户设定的，其大于所有个体的通信量；

A4，遍历集合F，找到Fit值最大的一个元素，把n放到个体X的第m个位置，把n从可用集P中删去；

A5，重复A3和A4，直到可用集P为空，当P为空时，表示产生了新个体X，把X加入临时种群tempPop中；

A6，重复A1到A5，生成N个个体；

A7，将个体X中的任意两个坐标数字对换，生成一个新个体Y，即X的邻居个体，重复此步骤生成20个X的邻居个体放入临时种群tempPop中；

A8，从临时种群tempPop中选取适应值最大的个体放入Pop中,得到初始种群；

S2，用遗传算法对S1生成的初始种群进行进化操作，得到最优解,该最优解的通信量相对于其他解来说是最低的；

所述方法进一步包括：

S3，根据S2得到的最优解生成仿真平台能够识别的通信模式文件；

S4，仿真平台读取S3生成的通信模式文件进行仿真，得到3D NoC低功耗映射仿真结果；

所述S3是这样实现的：

B1，将CTG(N,C)里的边集C，根据S2得到的最优解，转换成TAG的边集E，统计所有边的通信量之和wSum；

B2，生成随机数1≤r≤n，如果第r条边为e13，则在通信模式文件中写入<1 3>，如果通信量等于0，则循环查找下一条边，直到找到通信量大于0的边，在通信模式文件中写入该条边的信息，将该条边的通信量减1；

B3，重复步骤B2，直到所有边的通信量为0。

2.根据权利要求1所述的降低三维片上网络功耗的映射方法，其特征在于：所述S2的遗传算法具体如下：(1)在运行之前将解空间的数据表示成运行时用的基因数据；

(2)获取S1生成的初始种群，种群中每个个体对应一个解；

(3)根据目标函数构造适值函数，计算种群中每个个体的适应值；

(4)根据适应值的优劣不断地进行选择和繁殖操作，得到下一代种群；

(5)达到终止条件后，选择适应值最好的个体作为算法的最优解。

说明书

一种降低三维片上网络功耗的映射方法

技术领域

[0001] 本发明属于三维大规模集成电路设计与制造、网络拓扑与图论以及智能优化算法的交叉学科领域，具体涉及一种降低三维片上网络功耗的映射方法。

背景技术

[0002] 1958年世界诞生了第一个集成电路，随着集成度的提高集成电路板发展成为片上系统(System-on-Chip,SoC)，而且多核片上系统SoC的处理单元(Processing Elements,PE)规模不断增加，为高效地连接数量巨大的PE，产生了二维片上网络(two-Dimension Network-on-Chip,2D NoC)这种主流的片上互联架构。而目前2D NoC在面积、功耗、布局布线、封装密度等方面都已达到了瓶颈，三维片上网络(three-Dimension Network-on-Chip,3D NoC)应运而生，3D NoC以其更短的全局互连、更高的性能、更低的互连损耗、更高的封装密度以及更小的体积等诸多优势成为了SoC的一个重要的研究方向。降低功耗问题是3D NoC所面临的一个关键问题，从多个途径降低3DNoC的功耗非常必要。映射决定知识产权(Intellectual Property，IP)核(简称IP核)在3D NoC上的位置，好的映射能够有效降低3D NoC的功耗，因此如何实现3D NoC映射，使得功耗最小化的问题逐渐成为3D NoC领域的研究热点。NoC映射问题和任务调度问题相似，都是NP(指找不到在多项式时间内得到问题解的算法)难解问题，目前大多数的映射算法都采用启发式算法来寻找最优解。

[0003] NoC映射问题对于嵌入式系统来说是迫切需要解决的问题，对于低功耗3D NoC映射问题的研究已有许多成果，如基于C3Map和ARPSO算法解决3D NoC的节能问题；通过改进粒子群算法解决3D NoC映射问题；结合温度感知和能耗降低的3D NoC映射算法；采用遗传算法解决3D NoC映射问题；针对多目标映射问题的解决方法；针对3D-Mesh结构，充分利用硅通孔(Through Silicon Via,TSV)技术，提出能量感知的运行时增量映射算法；通过优化网络的内部通信并且把处于发热量高层上的IP核放到散热片附近以减少3D NoC的信号TSV；结合映射结果信息采用对称的拓扑结构和死锁避免的路由算法来降低3D NoC的能耗；基于整数线性规划(Integer linear programming,ILP)方法把异构处理单元放置到给定的3D NoC拓扑上以减少数据访问的开销；结合拓扑结构、路由算法、任务映射和处理单元放置提出的基于低垂直连接密度的系统优化遗传算法；针对3D NoC延迟感知提出的基于排序的多任务遗传算法；针对3D NoC提出动态蚁群算法以减少算法执行时间和提高算法的优化能力；基于ILP的静态热感知映射算法，探讨热约束在3D NoC上对温度和性能的影响。以上所有研究都各有侧重，由此可见，从不同角度研究3D NoC的映射问题是非常有必要的。

[0004] 3D NoC映射算法分为两大类，即启发式映射算法和非启发式映射算法，其中，启发式映射算法应用更为广泛。遗传算法是启发式算法，有许多研究者尝试应用遗传算法解决3D NoC的映射问题，如美国宾夕法尼亚州立大学的Addo-Quaye等人采用遗传算法解决了考虑热感知和通信感知的3D NoC映射问题；南京大学的王佳文、德国达姆施塔特工业大学的Haoyuan Ying、南京航空航天大学的Gui Feng、航空电子系统综合技术重点实验室的Ge Fen等人均用遗传算法解决映射问题，并取得了重要研究成果。但是目前的方法功耗大，运行时间长，不利于实际应用。

发明内容

[0005] 本发明的目的在于解决上述现有技术中存在的难题，提供一种降低三维片上网络功耗的映射方法，使得整个3D NoC的通信量最小，达到降低通信功耗的目的。

[0006] 本发明是通过以下技术方案实现的：

[0007] 一种降低三维片上网络功耗的映射方法，设通信轨迹图CTG(N,C)为有向图，N为顶点集，节点ni∈N表示一个IP核，C为边集，有向边cij∈C表示节点ci到节点cj的边，wij表示边；

[0008] 设拓扑结构图TAG(T,E)为有向图，T为处理单元PE集合，ti∈T表示一个处理单元PE，E为边集，有向边eij表示节点ti到节点tj的边；每个处理单元PE能够向任何一个其他处理单元PE发送数据，CTG中的一个IP核能够映射到任何一个可用处理单元PE上；

[0009] 所述方法包括：

[0010] S1，生成初始种群，具体包括以下步骤：

[0011] A1，将数字i放到个体X的第一个位置；

[0012] A2，初始化可用集P＝{1,2,3,...,N}，N为CTG的IP核个数，将i从可用集P中删去；

[0013] A3，任意选取可用集P中的一个数字n，将n放入个体X的所有可用处理单元的位置，计算放入这些位置后X的适应值，从这些适应值中找到最大的适应值Fit，记下n放到使得X的适应值最大的位置m，把存到集合F中；

[0014] A4，遍历集合F，找到Fit值最大的一个元素，把n放到个体X的第m个位置，把n从可用集P中删去；

[0015] A5，重复A3和A4，直到可用集P为空，当P为空时，表示产生了新个体X，把X加入临时种群tempPop中；

[0016] A6，重复A1到A5，生成N个个体；

[0017] A7，将个体X中的任意两个坐标数字对换，生成一个新个体Y，即X的邻居个体，重复此步骤生成20个X的邻居个体放入临时种群tempPop中；

[0018] A8，从临时种群tempPop中选取适应值最大的个体放入Pop中,得到初始种群；

[0019] S2，用遗传算法对S1生成的初始种群进行进化操作，得到最优解,该最优解的通信量相对于其他解来说是最低的。

[0020] 所述A3中的适应值＝maxF-通信总量，所述通信总量为已放到PE上的IP核之间的通信总量，适应值的上界maxF为用户设定的，其大于所有个体的通信量。

[0021] 所述S2的遗传算法具体如下：

[0022] (1)在运行之前将解空间的数据表示成运行时用的基因数据；

[0023] (2)获取S1生成的初始种群，种群中每个个体对应一个解；

[0024] (3)根据目标函数构造适值函数，计算种群中每个个体的适应值；

[0025] (4)根据适应值的优劣不断地进行选择和繁殖操作，得到下一代种群；

[0026] (5)达到终止条件后，选择适应值最好的个体作为算法的最优解。

[0027] 所述方法进一步包括：

[0028] S3，根据S2得到的最优解生成仿真平台能够识别的通信模式文件；

[0029] S4，仿真平台读取S3生成的通信模式文件进行仿真，得到3D NoC低功耗映射仿真结果。

[0030] 所述S3是这样实现的：

[0031] B1，将CTG(N,C)里的边集C，根据S2得到的最优解X，转换成TAG的边集E，统计所有边的通信量之和wSum；

[0032] B2，生成随机数1≤r≤n，如果第r条边为e13，则在通信模式文件中写入<13>，如果通信量等于0，则循环查找下一条边，直到找到通信量大于0的边，在通信模式文件中写入该条边的信息，将该条边的通信量减1；

[0033] B3，重复步骤B2，直到所有边的通信量为0。

[0034] 与现有技术相比，本发明的有益效果是：仿真结果表明，随着种群规模的增大，本发明方法在功耗继续保持降低的同时，运行时间大幅度降低。当IP核数为82、种群规模为2
600时，IG映射算法比IG映射算法运行时间降低了89.98％、平均功耗降低了16.36％。仿真实验表明，所提出的I2G映射算法行之有效。

附图说明

[0035] 图1通信轨迹图PIP

[0036] 图2a 3D NoC拓扑结构第一层

[0037] 图2b 3D NoC拓扑结构第二层

[0038] 图2c 3D NoC拓扑结构第三层

[0039] 图3a映射结果第一层

[0040] 图3b映射结果第二层

[0041] 图3c映射结果第三层

[0042] 图4针对VOPD两种算法的仿真结果对比

[0043] 图5任务通信图DVOPD

[0044] 图6针对DVOPD两种算法的仿真结果对比

[0045] 图7 I2G算法与IG算法运行时间对比

[0046] 图8两种算法最低功耗的比较

[0047] 图9两种算法最高功耗的比较

[0048] 图10两种算法平均功耗的比较

[0049] 图11种群规模为200两种算法运行时间对比

[0050] 图12种群规模为300时两种算法平均功耗比较

[0051] 图13种群规模为300时两种算法平均功耗比较

[0052] 图14 IP核为82时不同种群规模下两种算法运行时间对比

具体实施方式

[0053] 下面结合附图对本发明作进一步详细描述：

[0054] 二维片上网络(Two-dimensional Network-on-Chip,2D NoC)在面积、功耗、布局布线、封装密度等方面都已达到了瓶颈。与2D NoC相比，三维片上网络(Three-dimensional Network-on-Chip,3D NoC)有着诸多优势，因此3D NoC逐渐成为一个重要的研究方向。随着3D NoC集成度的提高，低功耗映射逐渐成为研究热点。

[0055] 3D NoC低功耗优化问题就是在给定通信轨迹图和拓扑结构图的基础上，研究如何将IP核映射到NoC的资源节点上，使得整个3D NoC的通信量最小，达到降低通信功耗的目的。为了描述3D NoC映射问题，给出如下定义。

[0056] 定义1设通信轨迹图CTG(N,C)为有向图，N为顶点集，节点ni∈N表示一个IP核。C为边集，有向边cij∈C表示节点ci到节点cj的边，wij表示边cij的权重。

[0057] 定义2设拓扑结构图TAG(T,E)为有向图，T为PE集合，ti∈T表示一个PE。E为边集，有向边eij表示节点ti到节点tj的边。

[0058] 3D NoC中的功耗主要分为两部分：路由节点上消耗的功耗和链路上消耗的功耗。路由节点的功耗主要是路由节点内部存储、交换、路由内部连线和路由选择所产生的能耗；
链路上的功耗指的是路由数据经过路由节点之间链路所产生的能耗。

[0059] 功耗模型如下：

[0060] 采用文献“基于改进粒子群的3D-Mesh CMPNoC映射算法[J]”(杨微,张振,刘怡俊..计算机应用研究,2013,05:1345-1348)给出的功耗模型，节点ti发送1个微片(flit)到节点tj消耗的的能耗表示为：

[0061]

[0062] 其中，μ表示节点ti到节点tj经过的路由器个数，μH和μV分别是ti到节点tj经过的水平方向和垂直方向的边的条数(跳步)，ERbit表示一个微片通过一个路由器时消耗的能量，ELhbit和EELVbit分别表示一个微片通过一条水平方向和垂直方向的线路上消耗的能量。文献“Tightly-Coupled Multi-Layer Topologies for 3-D NoCs[C]//ICPP.2007:75”(Matsutani H,Koibuchi M,Amano H.)给出了ELhbit和EELVbit的计算公式如下：

[0063]

[0064]

[0065] 其中，dH和dV分别表示水平方向和垂直方向的线路长度，Vdd表示供电电压，CwireH和CwireV分别表示水平方向和垂直方向线路的电容。

[0066] 3D NoC映射就是寻找IP核与PE的一个对应关系。在给定CTG和拓扑结构图TAG的条件下寻找一个映射函数M(·):N→T，使得总功耗最低(用Emin表示)，其目标函数如下：

[0067]

[0068] 且满足如下条件：

[0069]

[0070]

[0071] 对于确定的拓扑结构，ERbit、ELHbit和ELVbit是确定的，根据文献“Tightly-Coupled Multi-Layer Topologies for 3-D NoCs[C]//ICPP.2007:75”(Matsutani H,Koibuchi M,Amano H.)可知，线路上的能耗与线路的长度成正相关，所以两个通信节点之间的线路长度是影响NoC能耗的关键要素，由于TVS技术的出现，3D NoC在垂直方向的线路长度要远小于在水平方向的长度，因此，传输同样的数据量，在垂直方向的能耗要远小于在水平方向的能耗。

[0072] 遗传算法是根据问题的解构造一个适值函数，产生由多个解构成的种群，根据适应值的好坏选择种群中的个体进行遗传操作产生新的种群，当进化达到终止条件，选择适应值好的个体作为问题的解。

[0073] 算法的实现主要分为以下5个步骤：

[0074] (1)遗传算法在运行之前要将解空间的数据表示成算法运行时用的基因数据，由于每个IP核只能映射到一个PE上，因此在映射问题中采用整数编码；

[0075] (2)随机产生一个一定规模的初始种群，种群中每个个体都对应映射算法的一个解；

[0076] (3)根据问题的目标函数构造适值函数，计算种群中每个个体的适应值；

[0077] (4)根据适值的优劣不断地进行选择和繁殖操作，以得到下一代种群；

[0078] (5)达到终止条件后，选择适应值最好的个体作为算法的最优解。

[0079] 基本遗传算法的初始种群是随机生成的，这使得初始种群存在个体分布不均匀、初始种群质量偏低的问题。采用贪心算法思想生成初始种群的改进遗传算法，贪心算法思想体现在生成种群个体上。用贪心算法生成初始种群(即改进遗传算法，简称IG映射算法)主要分为以下3个步骤：

[0080] (1)随机将任务图中的一个节点(即IP核)映射到3D NoC的第一个位置(把所有IP核从1到N进行编号，N为任务图上IP核个数，n代表任意一个IP核，把所有PE从1到M进行编号，M为3D NoC上PE的个数，m代表任意一个PE)；

[0081] (2)分别计算将所有IP核集中可用数字放入所有PE集可用位置后的适应值，用表示未使用数字n放入3D NoC的第m个位置使得适应值fit最大，将放入集合F中，从F中选择fit最大的三组，随机从这三组中选择一组，将n放到3D NoC的第m个位置，把n从可用的IP核集中删去，把m从3D NoC的可用位置集中删去。

[0082] (3)重复第2步直到没有未使用的数字(IP核集为空)，即任务图中的所有节点都已映射到了3D NoC上。

[0083] 生成初始种群后，采用遗传算法进行遗传操作，得到最优个体，然后用最优个体生成仿真器能够识别的通信模式文件，仿真器读取通信模式文件进行仿真，得到映射功耗。仿真结果表明，IG映射算法可以有效地降低功耗，从总体趋势上看，随着处理单元数量的增加，功耗降低的幅度逐渐增大，在种群规模为200、处理单元为120的情况下，总功耗可降低14.42％。

[0084] 由于每个PE都可以向任何一个其他PE发送数据，CTG中的IP核可以映射到任何一个可用PE上，因此，3D NoC映射问题中种群个体采用整数编码，假设个体X＝(x1,x2,x3...,xn)，n为CTG的IP核个数，xi为IP核编号，个体X的编码为1到n的一种排列，通过对编码进行解码即可得到一种映射方案。一个简单的16节点通信轨迹图VOPD，如图1所示，以此图为例来说明种群个体的向量表示。

[0085] VOPD中的IP核用数字1到16表示，将VOPD映射到2×3×3的3D NoC上，3D NoC上的每个PE用数字t1到t18表示，t1到t6表示第1层，t7到t12表示第2层，t13到t18表示第3层，如图2a至图2c所示。个体X＝(2,3,4,1,16,5,7,6,11,15,14,12,13,10,8,9)，表示将IP核集(2,3,4,1,16,5,7,6,11,15,14,12,13,10,8,9)分别映射到处理单元t1到t16上，映射结果如图3a至图3c所示。将所有IP核映射到3D NoC上后，计算3D NoC上所有节点之间的通信总量遗传算法根据3D NoC上的通信总量计算其适应值(适应值＝maxF-通信总量，maxF为人为设定的，maxF比算法中可能出现的最大适应值还大,也就是说在实验过程中的所有个体的通信量都不会超过这个值，这个值是人为设定的，通过观察得到的值。maxF为max fitness的简写，是一个常量)，通信总量越大，适应值越小，遗传算法根据适应值大小进行遗传操作。

[0086] 基本遗传算法随机产生种群，产生的种群质量偏低，为提高初始种群的质量，本发明提出改进贪心算法生成初始种群(Pop)(二次改进遗传算法，简称I2G映射算法)的主要过程如下：

[0087] Step1将数字i放到个体X的第一个位置(i从1取到N，当选取每个i后，重复step2到step5，每次循环生都成一个个体)；

[0088] Step2初始化可用集P＝{1,2,3,...,N}，N为CTG的IP核个数，将i从可用集P中删去；

[0089] Step3遍历可用集P中的数字n，将n放入个体X的所有可用位置(即可用集中的各个PE处)，计算放入这些位置后X的适应值(适应值＝maxF-通信总量(已放到PE上的IP核之间的通信总量)，maxF为人为设定的，maxF比可能出现的最大适应值还大)，从这些适应值中找到最大的适应值Fit，记下n放到使得X适应值最大的位置m，把存到集合F中；

[0090] Step4遍历集合F，找到Fit值最大的一个元素，把n放到个体X的第m个位置，把n从可用集P中删去；

[0091] Step5重复Step3和Step4，直到可用集P为空，当P为空时，表示产生了新个体X，把X加入临时种群tempPop中；

[0092] Step6重复上述5步，生成N个个体；

[0093] Step7将个体X中的任意两个坐标数字对换(即变异操作)，生成一个新个体Y，即X的邻居个体。用此方法生成20个X的邻居个体放入临时种群tempPop；

[0094] Step8从临时种群tempPop中选取一定规模(规模采用经验值，或者根据实验对比需要自由设定)适应值最大的个体放入Pop中。

[0095] I2G耗映射算法实现

[0096] (1)3D NoC低功耗映射实现流程

[0097] Step1采用改进贪心算法生成初始种群(详见3.2.3)；

[0098] Step2用遗传算法对初始种群进行进化操作，得到算法的最优解；

[0099] Step3根据最好解生成仿真平台能够识别的通信模式(traffic pattern)文件；

[0100] Step4仿真平台读取通信模式文件进行仿真，得到3D NoC低功耗映射仿真结果。

[0101] (2)通信模式文件的生成过程

[0102] Step1将CTG(N,C)里的边集C，根据改进遗传算法得到的最优个体X，转换成TAG的边集E。例如：最优个体X＝(2,3,4,1,8,5,7,6)，边c12，w12＝100，映射到TAG上后，得到边e41，w41＝100。统计所有边的通信量之和wSum；

[0103] Step2生成随机数1≤r≤n，如果第r条边为e13，则在通信模式文件中写入<13>，如果通信量等于0，则循环查找下一条边，直到找到通信量大于0的边，在通信模式文件中写入该条边的信息，将该条边的通信量减1；

[0104] Step3重复Step2，直到所有边的通信量为0。

[0105] 下面通过仿真与分析来说明本发明方法的效果：

[0106] 仿真平台与参数设计如下：

[0107] 实验在Ubuntu13操作系统下，采用C++语言编写算法的实现程序，在codeblocks 12.11环境下进行映射算法仿真。采用Access Noxim 0.2作为仿真软件，Access Noxim对主流的2D NoC仿真软件noxim进行了改进，改进后可以用于3D NoC的仿真实验。

[0108] 拓扑结构与路由选择如下：

[0109] (1)拓扑结构的选择

[0110] 3D Mesh具有结构规则、布线简单、网络节点位置平等、且在垂直互连采用TSV技术能够减小总体布线长度等优点，实验采用3D Mesh结构进行仿真。

[0111] (2)路由选择

[0112] 由于XYZ路由算法易于理解与实现，是主流的路由算法，实验采用的路由算法为XYZ路由算法。

[0113] 参数设置如下：

[0114] (1)算法的参数设置种群规模为200、遗传迭代次数为100、交叉率为0.9、变异率为0.02。

[0115] (2)仿真软件的参数设置数据包采用无记忆泊松分布(Memory-less Poisson distribution)方式注入，数据包的注入率(Packet injection rate)设为0.02，；仿真软件统计循环5000次的总功耗；数据包的大小介于2个微片(flit)到10个微片之间；路由器每个通道的缓存大小为8个微片。

[0116] 硬件运行环境如下：

[0117] 整个仿真实验的硬件环境是：CPU为Intel(R)Core(TM)i3-2120、主频为3.30GHz、3.30GHz，内存为4GB的微型计算机。

[0118] 采用C++语言编写了基于IG算法和基于I2G算法的3D NoC低功耗映射应用程序，在以上选择的环境下进行了仿真实验，结果如下：

[0119] 1，经典任务图的功耗对比

[0120] (1)针对VOPD的功耗对比

[0121] 实验首先针对两个经典的通信轨迹图VOPD和DVOPD进行仿真实验，其中VOPD有16个节点，如图4所示，实验中将VOPD映射到2*2*4的3D NoC上，在仿真实验中，首先分别采用IG映射算法和I2G映射算法对这任务图进行映射操作，用得到的最优解生成通信模式文件，仿真器Access Noxim通过读取通信模式文件进行映射仿真，得到总功耗。通过实验结果分别对两种算法得到的最小功耗、平均功耗和最大功耗进行比较。

[0122] 从针对VOPD两种算法的仿真结果分析看，在最低功耗方面I2G映射算法低于IG映射算法，即采用I2G映射算法的功耗更低，但是低的幅度较小；而在平均功耗和最大功耗方面，I2G映射算法的功耗高于IG映射算法的功耗，如图4所示。其中min表示最低功耗、avg表示平均功耗、max表示最高功耗，I2G映射算法与IG算法的唯一区别就是生成初中种群时采用的贪心策略不同。对任务图分别进行了10次实验，其中I2G映射算法与IG映射算法相比，最低功耗降低了2.02％、平均功耗增加了2.15％、最高功耗增加了1.54％。这是由于VOPD只有16个节点(节点过少)，采用改进贪心策略得到的初始种群容易陷入局部最优，因此基于I2G映射算法的功耗高于基于IG映射算法的功耗。

[0123] (2)针对DVOPD的功耗对比

[0124] 通信轨迹图DVOPD有32个节点，如图5所示，实验中将DVOPD映射到2*4*4的3D NoC上。对通信轨迹图DVOPD用两种算法进行仿真实验。

[0125] 用两种算法进行仿真实验的仿真结果如图6所示。I2G算法得到的仿真结果要比IG算法的好。实验中对任务通信图DVOPD分别进行了10次实验，分析实验结果可知：I2G映射算法比IG映射算法，最低功耗降低了13.37％、平均功耗降低了9.18％、最高功耗降低了7.48％。

[0126] 针对DVOPD的仿真实验结果表明，功耗有明显的降低，这是由于DVOPD有32个节点，任务规模比较大，采用改进贪心策略得到的初始种群不容易陷入局部最优。由以上试验和分析可见，当任务图规模增大时，I2G映射算法的优势更大。

[0127] 2，经典任务图映射算法运行时间对比

[0128] 两种算法运行时间如图7所示，从图中可以看出，I2G映射算法的运行时间远远小于IG映射算法的运行时间，由于VOPD的规模较小，生成每个个体所用的时间较短，因此I2G算法的运行时间降低幅度较小降低了19.11％(I2G映射算法运行时间3.619秒、IG映射算法4.474秒)；对于DVOPD的算法运行时间降低了68.90％(I2G映射算法：5.444秒、IG映射算法：
17.503秒)。

[0129] 3，200种群规模下随机任务图的功耗对比

[0130] (1)仿真实验数据

[0131] 采用任务生成器TGFF[16]生成随机任务图，针对不同IP核数的CTG，种群规模为200时，分别采用IG映射算法和I2G映射算法求解10次，得到的功耗如表1和表2所示。其中，对10次仿真实验的数据从低到高进行了排序。由于原始数据过小，为更直观的显示功耗，表
1和表2中所有功耗均为原始数据乘以100(但功耗的比较分析仍采用原始数据)。

[0132]

[0133]

[0134] 表1

[0135]

[0136] 表2

[0137] (2)最低功耗的比较

[0138] 当IP核数较少时，I2G映射算法算法相对于IG映射算法的最低功耗降低幅度较小，在10％以内。其中，21个IP核时，I2G映射算法相对于IG映射算法的功耗低了17.46％，这是由于IP核数较少，可能导致两种算法都陷入了局部最优，因此出现了在21个IP核时，I2G算法的功耗降低幅度较大。从整体趋势来看，随着IP核数的增加，功耗降低幅度增加，如图8所示，当IP核数为121时，I2G映射算法相对于IG映射算法功耗降低了22.64％。

[0139] (3)最高功耗的比较

[0140] 在21个IP核时，I2G映射算法相对于IG映射算法最高功耗降低了17.4％，这是由于IP核数较少，可能导致两种算法都陷入局部最优，因此降低幅度较大。当IP核个数为82时，I2G映射算法相对于IG映射算法的最高功耗降低了19.25％，为所做实验的最大降低幅度，如图9所示；当IP核数为121时，I2G映射算法相对于IG映射算法最高功耗降低了13.95％。

[0141] (4)平均功耗的比较

[0142] 21个IP核时，I2G映射算法相对于IG映射算法平均功耗降低了14.85％；当IP核数为82时，I2G映射算法相对于IG映射算法平均功耗降低了13.61％；当IP核数为121时，I2G映射算法相对于IG映射算法平均功耗降低了17.18％，为所做实验的最大值，如图10所示。

[0143] 4，200种群规模随机任务图映射算法运行时间对比

[0144] 种群规模为200两种算法运行时间对比曲线如图11所示。从图中可以看出，I2G映射算法运行时间远远小于IG映射算法运行时间，当IP核数为59时，I2G映射算法运行效率提高幅度达到74.05％。

[0145] 5，300种群规模下随机任务图的功耗与时间对比

[0146] (1)两种算法功耗对比

[0147] 种群规模为300时，两种算法平均功耗的比较如图12所示，核数为121时，I2G映射算法比IG映射算法功耗降低了13.48％。

[0148] (2)两种算法运行时间对比

[0149] 种群规模为300时I2G映射算法与IG映射算法运行时间对比图13所示，I2G映射算法比IG映射算法时间最大降低了85.56％。

[0150] 6，随机任务图不同种群规模下运行时间对比

[0151] 两种算法在IP核数为82，种群规模不同时的运行时间对比如图14所示。当种群规模为600时，I2G映射算法比IG映射算法运行时间降低了89.98％(此时功耗降低16.36％)。随着种群规模的增大，I2G映射算法的运行时间降低比例逐渐增加；随着种群规模的增加，IG映射算法的运行时间大幅度增加，而I2G映射算法的运行时间变动幅度很小，这是由于I2G映射算法是用改进贪心策略生成初始种群，因此，种群规模对算法的运行时间影响很小。

[0152] 上述技术方案只是本发明的一种实施方式，对于本领域内的技术人员而言，在本发明公开了应用方法和原理的基础上，很容易做出各种类型的改进或变形，而不仅限于本发明上述具体实施方式所描述的方法，因此前面描述的方式只是优选的，而并不具有限制性的意义。