算法a

收稿日期:20190326;修回日期:20190603基金项目:国家科技重大专项核高基资助项目作者简介:张保岗(1986),男,河南周口人,硕士研究生,主要研究方向为片上网络、可重构计算、智能算法(zhangbaogang2017@126.
com);韩国栋(1964),男,山东莱西人,副教授,硕导,博士,主要研究方向为宽带信息处理、芯片设计技术;刘冬培(1985),男,湖南祁阳人,博士,主要研究方向为SoC芯片设计与验证;燕籨昊(1994),男,山西吕梁人,硕士研究生,主要研究方向为机器学习、入侵检测、网络安全.
TSGA:新型的片上网络低功耗映射算法张保岗,韩国栋,刘冬培,燕籨昊(信息工程大学,郑州450002)摘要:针对如何将越来越复杂的应用任务有效地映射到片上网络处理单元上,达到以更少的能耗完成任务的目的,提出了一种遗传算法和禁忌搜索算法相融合的新型片上网路低功耗映射算法.
该方法充分利用遗传算法强大的全局搜索能力,融合禁忌搜索的局部搜索能力和突出的翻山特性来弥补遗传算法的局部搜索能力弱和早熟的缺陷,取得了更好的片上网络低功耗效果.
实验结果表明,在同样的实验平台和功耗模型下,禁忌搜索遗传算法相比于早期的遗传算法能耗降低显著,相比于后来改进的MGA、AGA算法也有能效优势.
关键词:片上网络;映射算法;遗传算法;禁忌搜索算法中图分类号:TP393文献标志码:A文章编号:10013695(2020)09032272604doi:10.
19734/j.
issn.
10013695.
2019.
03.
0138TSGA:novelnetworkonchiplowpowermappingalgorithmZhangBaogang,HanGuodong,LiuDongpei,YanBinghao(InformationEngineeringUniversity,Zhengzhou450002,China)Abstract:Inordertoeffectivelymapcomplexapplicationtaskstothenetworkonchipprocessingunitandachievethetaskwithlessenergyconsumption,thispaperproposedanovelnetworkonchipmappingalgorithmthatcombinedgeneticalgorithmandtabusearchalgorithm.
Themethodmadefulluseofthepowerfulglobalsearchabilityofthegeneticalgorithm,andcombinedthelocalsearchabilityofthetabusearchandtheprominentmountainfeaturestocompensatefortheweaklocalsearchabilityandprematuredefectsofthegeneticalgorithm,thenachievedabetternetworkonchiplowpowereffect.
Underthesameexperimentalplatformandpowerconsumptionmodel,comparedwiththeearlygeneticalgorithm,thetabusearchgeneticalgorithmhassignificantenergyefficiencyimprovement,andithasenergyefficiencyadvantagescomparedwiththelaterimprovedMGAandAGAalgorithms.
Keywords:networkonchip;mappingalgorithm;geneticalgorithm;tabusearchalgorithm0引言随着超大规模集成电路的持续发展和生产工艺的不断改进,电子产品零器件越来越向小型化发展,单位芯片上集成的元器件日益增多,片上系统(systemonchip,SoC)这些年也得到突飞猛进的发展;作为总线结构替代技术的内部通信系统片上网络(networkonchip,NoC)已经成为实现芯片上各个处理单元(processingelements,PE)之间通信的主流设计[1].
随着单位芯片上集成度越来越高,能耗逐渐成为限制芯片发展的重要因素甚至是首要因素.
NoC自2001年提出以来[2],其发展相当迅速,极大地推进了芯片的发展,其能耗方面的研究设计也成为SoC能耗设计最重要的一环[3].
片上网络映射作为NoC设计的重要一维,其低功耗的优化设计对整个片上网络能耗表现影响很大[4].
如何在系统条件约束下,在现有NoC拓扑结构和路由的基础上,将任务节点按照一定规则有效地映射到片上网络各个处理单元上,以尽可能减少总的信息交互功耗是NoC技术研究的一个热点.
随着芯片PE数量的增加,需要处理的应用越来越多也越来越复杂,传统穷举求最优解的方法早已经不适合.
目前,基于智能启发式算法在该领域逐步展现其优越性和实用性[5],也是近年来NoC映射技术研究的热点.
1相关工作基于启发式算法的NoC低功耗映射技术研究成果有很多,如任向隆等人[6]提出了基于遗传和蚂蚁算法融合的映射算法,利用蚂蚁算法的正反馈特性,融合遗产算法的交叉变异操作,使得低功耗映射问题搜出更优解.
戴启华等人[7]提出了改进遗传算法的NoC低功耗映射方法MGA,根据任务节点的通信权重优先排序并获取较优初始解,每次迭代中以一定概率选择初始解,防止早熟.
文献[8]结合了禁忌搜索,主要优化离散粒子群,用禁忌列表防止群粒子重复搜索,使得NoC的总体通信延迟和能耗最小化.
文献[9]提出一种优化快速最近邻启发算法ONMAP,最小化NoC通信消耗并可以映射实时嵌入式应用程序,某种程度上实现了动态映射效果.
文献[10]提出了一种新的基于遗传的超启发式算法作为核心算法,由于该算法可以在映射过程中自动选择合适的算子,可以显著提高收敛速度并表现出优异的稳定性,用于共同优化片上网络的能耗和通信延迟.
上述有关研究成果对NoC低功耗映射方面有很大的推进作用,但依然有可优化的研究空间.
本文在充分理解经典遗传算法(geneticalgorithm,GA)优缺点的基础上[11],结合禁忌搜索(tabusearch,TS)算法的优势[12],考虑到2Dmesh拓扑结构的NoC特点,设计了一种混合的禁忌遗传算法(tabusearchge第37卷第9期2020年9月计算机应用研究ApplicationResearchofComputersVol37No9Sep.
2020neticalgorithm,TSGA)来实现NoC低功耗映射.
2问题定义和模型描述结合文献[3,7,13]中对片上网络映射问题定义和模型构建,本文对问题定义和模型描述如图1所示.
!
!
""#$"$"%"&'()*")"#")"+,--.
/0!
('#*%$)&)'(!
#&,1图1映射流程图Fig.
1Flowofmapping21问题定义定义1应用任务图(applicationtaskgraph,ATG)如图1(a)所示,是一个带通信权重的有向图.
含有数字的圆圈代表相应的任务节点ti,从任务节点ti到tj的通信量记为Vti,tj,如图Vt1,t2=40.
定义2结构特征图(architecturecharacteristicgraph,ARCG)如图1(b)所示,由各个带处理单元的交换节点相互连接可以实现双向通信的有向图.
图1(b)为典型的3*3的mesh拓扑结构,含有数字的圆圈代表相关交换节点si,每个交换节点都有一个处理单元pi与之对应.
两个处理单元pi、pj之间的曼哈顿距离为Mpi,pj,对于mesh结构一般为两个资源节点所经历最少交换节点数减1.
22NoC映射片上网络映射就是将给定的ATG按一定顺序分配到ARCG中,使任务节点与处理单元一一对应,为处理单元通过NoC完成相应的处理任务作准备.
要使映射结果正确执行,需要保证结构特征图的处理节点数量大于任务图中的任务节点数[7],即size(ATG)≤size(ARCG)(1)任务节点数量为m的ATG要映射到n*n的2Dmesh上,需要满足m≤n2.
m个任务节点参与映射就有n2!
/(n2-m)!
个映射结果,合理的映射结果可以更好地利用现有处理资源来完成相应的应用任务,如实现快速、低功耗等.
如何找到一个较好的低功耗映射结果是本文所要解决的主要问题.
23功耗模型常用的片上网络功耗模型如文献[4,7],单位比特数据在两个相邻处理单元之间传递消耗的能量Ebit为Ebit=ESbit+EBbit+EWbit+ELbit(2)其中:ESbit为单位比特在交换节点的能量消耗;EBbit、EWbit为单位比特在缓存区和处理单元与相应交换节点之间链路消耗的能量;ELbit是单位比特在两个处理单元之间链路传输消耗的能量.
由于EBbit、EWbit远远小于ESbit和ELbit,所以式(2)可以简化为Ebit=ESbit+ELbit(3)因此,单位比特从处理单元pi到pj所消耗的能量为Epi,pjbit=Mpi,pj*ELbit+(Mpi,pj+1)*ESbit(4)对于规则2Dmesh结构来说,可以将式(4)简化为Epi,pjbit=Mpi,pj*(ELbit+ESbit)(5)以便于评估计算算法的功耗.
对于n*n规则2Dmesh拓扑结构的NoC,令M=n*n,则任务节点数为m的任务图映射到结构特征图后所消耗的总能耗ENoC为ENoC=∑Mi=1∑Mj=1Vti,tj*Epi,pjbit(6)由功耗模型可知,任务节点映射到的处理节点不同,最终完成任务需要消耗的能耗也不尽相同.
从式(5)(6)可知,要减少片上网络的总功耗,关键在于降低映射结果全部信息的曼哈顿距离之和.
如何在众多映射结果中找到能量消耗最少的结果,就是本文主要解决的问题.
3基于禁忌搜索遗传算法的低功耗映射针对遗传算法的全局搜索能力强、局部搜索欠佳和禁忌搜索算法的局部搜索能力强而全局搜索能力欠佳的特点,本文融合两种算法的长处,提出禁忌搜索遗传算法来实现NoC低功耗映射,以解决遗传算法存在的问题并可以获得更好的映射方案.
31解结构图1中的ARCG结构是一个典型的3*3mesh的NoC,本文只考虑2Dmesh结构的NoC,2D的mesh结构有n2个处理单元,每个处理单元在NoC中位置不同,分别有2、3、4条物理链路将各个处理单元连接起来,以实现相互之间的通信.
对于禁忌搜索遗传算法,每个种群个体和禁忌解都代表一个映射结果.
将2Dmesh中的处理单元从左到右、从上至下进行升序排序,如图2所示,从P1到P9,每个处理单元都有一个唯一的数字编号,对于图中3*3mesh结构的最大编号为9.
将图1中的任务节点映射到该NoC中,由于任务节点数量为6,则有9!
/(9-6)!
=60480个映射结果,其中两个如图2所示.
映射结果a、b对应映射位置信息Pa={1,4,5,2,3,7},Pb={1,5,9,2,3,7}为两个有效的映射结果即有效解,只要对应位置信息为六个不大于9的不相同整数,都是一个有效解.
!
"#$%&'()*)$#+%*",$%&'()*)$"%*,-.
图2映射结果Fig.
2Mappingresults32禁忌搜索遗传算法设计实现经过常规遗传算法得到的解或许不是最优解,但一定是个较优解,非常适合作为禁忌搜索的初始解.
经过禁忌算法的藐视准则判定,符合的再进入遗传算法的选择操作,从而增加种群多样性,避免遗传算法早熟现象.
321TSGA:禁忌搜索遗传算法算法1禁忌搜索遗传算法输入:种群规模numpop;种群进化代数numgen;任务节点数量numtask;处理单元数量numpe;变异概率Pmut;交叉概率Pcro;禁忌长度Ltaboo;邻域移动速度MVnear;通信权重矩阵matcom.
输出:遗传产出的较优解betsol;最优解optsol.
1initializetheparameters2randomlygeneratetheinitialpopulation·7272·第9期张保岗,等:TSGA:新型的片上网络低功耗映射算法3fori=1numgenbegin4selectoperationoftheinitialpopulation5forj=1numpopbegin6crossoveroperationandmutationoperation7calculatethefitnessoftheobtainedindividual8compareandfindthebetsol//找到较优解9endfor10form=1numtaskbegin11ifbetsol>Tstop12outputoptsol13else14movethebetsoltogetneibsols//构建邻域解集15tabuoperation//禁忌准则和藐视准则的使用16endfor17updatetheinitialpopution//满足藐视准则18endfor322算法适应度选定根据任务图的任务节点数m,对任务节点赋值,赋予1~m的整数值,不得重复.
提取各个节点之间的通信权重,生成m*m的通信权重矩阵matcom.
如图3所示,依据图中的ATG六个任务节点之间的通信权重生成一个6*6的通信矩阵,有通信权重的任务节点之间才会产生数据流量,再由NoC映射结果计算出任务节点间的Mpi,pj,代入式(5)得出映射结果总功耗ENoC,作为算法的适应度.
最终得出的最优解为optsol=min{ENoC}(7)!
!
""#$%&'#"'"("(")"*"+#"'"("(")"*",!
""图3通信矩阵生成过程Fig.
3Communicationmatrixgeneration323构建邻域解集依据NoC的结构特点构建邻域解集neibsols,如图4所示,以图2中映射结果a为例,按MVnear为1产生邻域解集,由于Pa的映射结果在NoC中只有六个直接互连的任务节点,那么邻域解集只有六个有效解,如图4(b)所示.
任务节点1和4在NoC中曼哈顿距离为1,则两个任务节点可以互换位置,得到一个邻域解Pa1={2,4,5,1,3,7},将NoC中相邻任务节点互换得到图中其他五个邻域解.
!
"#$%&'()*+,-,'&%(-#.
/%0(0-0&0'0)1234图4邻域解集构造Fig.
4Neighborhoodsolutionsetstructuremap324遗传禁忌操作先进行GA操作,随机生成初始种群,通过选择、交叉、变异等遗传操作产生优势种群,通过最后适应度计算比较获得一个较优解.
该算法中将映射结果的ENoC定为适应度,功耗越大适应度越小,反之功耗越小适应度越大.
利用轮盘转赌选择适应度大的种群进入交叉变异,个别优势个体会繁衍较快,进而破坏种群多样性,使得陷入早熟获得一个局域较优解betsol.
该映射结果的功耗相对较低但不是很理想.
然后将betsol作为TS初始解进行禁忌操作,按一定运动速率构建邻域候选解neibsol,利用TS的禁忌准则优化较优解,用藐视准则反馈到遗传操作的选择阶段,增加种群多样性,使得遗传操作跳出早熟陷阱.
停止准则的目标参数设定为NoC想要达到的理想功耗,藐视准则的渴望水平设为历史最优.
4实验与分析41实验环境搭建1)仿真平台实验在Linux环境下用C++完成映射算法程序等相关源代码的编写,采用2DNoC仿真软件Noxim,在Ubuntu16.
04操作系统下实现.
硬件环境的CPU为第八代英特尔酷睿i78550U4.
0GHz,内存为16GBDDR4双通道.
2)ARCG拓扑结构和路由选择2Dmesh拓扑结构具有结构规则、实现容易、布线简单、便于拓展的特点,是常用的NoC拓扑结构,非常适合研究映射算法.
该实验选用2Dmesh拓扑结构,根据实验需要有4*4、5*5、6*6三种规模的mesh拓扑.
路由算法采用容易理解和实现的XY路由算法,也是NoC主流路由算法.
3)任务图的选择为了体现TSGA对各种实际应用的有效性,以及便于和同类算法作对比分析,实验采用典型的实际应用任务图VOPD、MPEG4、263Enc、263Dec[13].
四种应用任务图结构不同,任务节点数和通信总量也不尽相同,详细特征属性如表1所示.
表1应用任务属性Tab.
1Applicationtaskproperties应用通信边数任务节点数通信总量/MBpsVOPD21163471MPEG413123466263Dec151419.
627263Enc1212239.
2144)参数设定参数设置对禁忌搜索遗传算法的影响很大,例如初始种群规模的大小直接关系到计算速度和最终解的优劣,初始规模太大,计算量大,会降低计算速度;初始规模太小,不能覆盖种群全部,最终生成局部最优解.
结合图1中任务数量特征和NoC结构特点进行参数设置和调整,基本参数设置定义如表2所示.
表2参数定义设置表Tab.
2Parameterdefinitionsettingtable参数定义设置参数定义设置numinipop初始种群规模200Pmutation变异概率0.
05numgen种群进化代数300Pcross交叉概率0.
7numtask任务几点数量6Ltaboo禁忌长度10numpe处理单元数量9MVnear移动速度142实验结果对比分析由于芯片生产工艺的不同,不同芯片的mesh结构相邻处理单元之间传递信息的消耗也不相同,但这并不影响评估算法的功耗降低强度大小.
为了便于评估映射结果的功耗,考虑到mesh结构的规则对称性,实验计算时将相邻两个处理单元之间的距离视为一个曼哈顿距离M,每M通信传递消耗1个能·8272·计算机应用研究第37卷量单元.
由于智能算法有一定的随机性,为确保实验结果的准确性,每种应用任务图在同一规模的mesh结构特征图下分别运行10次,然后取10次结果的平均能耗.
各个算法在不同规模的mesh拓扑NoC上消耗能量如表3所示,为了检验TSGA的低功耗性能,实验结果与GA[11]、AGA[13]、MGA[7]三种算法作对比.
表3能量消耗表Tab.
3EnergyconsumptiontableNoC规模应用任务算法GAAGAMGAGATS4*4VOPD5354.
64226.
34139.
64034.
8MPEG44866.
13789.
33663.
23546.
7263Dec57.
534.
831.
631.
4263Enc340.
9297.
3276.
8268.
35*5VOPD5311.
44198.
64155.
83995.
6MPEG44758.
63724.
83648.
33368.
5263Dec55.
832.
130.
329.
2263Enc320.
1288.
6267.
3255.
46*6VOPD5266.
84156.
94113.
73988MPEG4473436783613.
93346.
4263Dec54.
231.
529.
629.
1263Enc311.
2274.
7262.
8253.
6从表3可以看出,相比于早期的GA,后期的改进遗传基因算法在降低功耗上都有很大的提升,TSGA相对于AGA、GA也有不小的提升.
如图5所示,四种应用任务通过TSGA在三种NoC规模下的能耗走势可以看出,在NoC规模满足任务节点数早期功耗降低明显,当然这是在占用更多芯片资源的情况下,但是后期随着规模再扩大,能耗降低水平减弱甚至没有变化.
在4*4mesh拓扑的NoC上,以VOPD应用为例,在能耗上TSGA相比于GA提升了24.
6%,相比于较新的MGA也提升了2.
6%.
在其他三种应用中不论和GA比较还是和后来改进的AGA、MGA对比,TSGA都有不少优势,随着片上网络规模的增大,优势依然存在,形象比较如图6所示.
!
"!
"!
"#"!
"""$%&"$%'"!
!
((''$'""$(""$!
""$$""$)""!
!
((''$)$*$+)%)&),!
!
((''),")'()'")(()(")!
(!
!
((''-.
/0123-456278!
9:5)'$3;:-A能耗趋势图Fig.
5TSGAenergyconsumptiontrendchart!
"#$"#%"#&"#'"#("#"#)*+,-+.
/%'!
&,01'!
&.
213/3-/345/3%%)*+,-+.
/%'!
&,01'!
&.
21)*+,-+.
/%'!
&,01'!
&.
21$$!
!
图6相比GA各算法能耗降低比例Fig.
6EnergyreductionratiocomparedwhitGA算法执行时间上,TSGA耗时相对于其他三种算法有些长,是GA的近两倍,但随着计算机计算能力的提升,执行时间越来越短,这点执行时间的增长并不明显,并且对后面的片上网络静态映射没有影响.
耗费一点算法执行时间来获取片上网络映射功耗的降低是值得的.
5结束语本文结合GA和TS算法的长处,形成一种优势互补的TSGA来解决片上网络低功耗映射的问题,以禁忌搜索的翻山特性解决遗传基因算法的早熟问题,又通过禁忌搜索的强大局部搜索能力优化GA的成果.
实验结果表明,TSGA的映射结果明显优于GA,相对于其他改进后的AGA、MGA也有很大的优势.
在下一步的研究中,应该优化算法的融合强度,考虑执行时间和算法复杂度,以便在片上网络映射上有更突出的表现.
参考文献:[1]BeniniL,DeMicheliG.
Networksonchips:anewSoCparadigm[J].
Computer,2002,35(1):7078.
[2]DallyWJ,TowlesB.
Routepackets,notwires:onchipinterconnectionnetworks[C]//Procofthe38thAnnualDesignAutomationConference.
2001:684689.
[3]HanJianjun,LinMan,ZhuDakai,etal.
ContentionawareenergymanagementschemeforNoCbasedmulticorerealtimesystems[J].
IEEETransonParallelandDistributedSystems,2015,26(3):691701.
[4]马悦.
面向片上网络映射的关键技术研究[D].
天津:天津工业大学,2018.
(MaYue.
Researchonkeytechnologiesforonchipnetworkmapping[D].
Tianjin:TianjinPolytechnicUniversity,2018.
)[5]NesrineT,DjamelB,AliM.
AclassificationandevaluationframeworkforNoCmappingstrategies[J].
JournalofCircuits,SystemsandComputers,2017,26(2):1730001.
11730001.
44.
[6]任向隆,安建峰,高德远,等.
低功耗片上网络映射的遗传及蚂蚁融合算法[J].
西安交通大学学报,2012,46(8):6570.
(RenXianglong,AnJianfeng,GaoDeyuan,etal.
FusionstrategywithgeneticandantalgorithmsforlowpowerNoCmapping[J].
JournalofXi'anJiaotongUniversity,2012,46(8):6570.
)[7]戴启华,刘勤让,沈剑良,等.
基于改进遗传算法的片上网络低功耗映射方法[J].
计算机应用研究,2016,33(6):18621866.
(DaiQihua,LiuQinrang,ShenJianliang,etal.
Modifiedgeneticalgorithmbasedmethodonlowpowermappinginnetworkonchip[J].
ApplicationResearchofComputers,2016,33(6):18621866.
)[8]ObaidullahM,KhanGN.
Optimalapplicationmappingto2DmeshNoCsbyusingatabubasedparticleswarmmethodology[C]//Procofthe2ndInternationalWorkshoponAdvancedInterconnectSolutionsandTechnologiesforEmergingComputingSystems.
2017:1722.
[9]KhanS,AnjumS,GulzariUA,etal.
Anoptimizedhybridalgorithmintermofenergyandperformanceformappingrealtimeworkloadson2Dbasedonchipnetworks[J].
AppliedIntelligence,2018,48:47924804.
[10]XuChangqing,LiuYi,LiPeng,etal.
Unifiedmultiobjectivemappingfornetworkonchipusinggeneticbasedhyperheuristicalgorithms[J].
IETComputers&DigitalTechniques,2018,12(4):158166.
[11]TangLei,KumarS.
Atwostepgeneticalgorithmformappingtaskgraphstoanetworkonchiparchitecture[C]//ProcofEuromicroSymposiumonDigitalSystemDesign.
Piscataway,NJ:IEEEPress,2003:180187.
[12]GloverF,LagunaM.
Tabusearch[M].
Boston,MA:Springer,1997:20932229.
[13]WangYizhuo,ZhangZhibiao.
AnadaptivegeneticalgorithmformeshbasedNoCapplicationmapping[J].
TELKOMNIKAIndonesianJournalofElectricalEngineering,2014,12(11):78697875.
[14]SahuPK,ChattopadhyayS.
Asurveyonapplicationmappingstrategiesfornetworkonchipdesign[J].
JournalofSystemsArchitecture,2013,59(1):6076.
·9272·第9期张保岗,等:TSGA:新型的片上网络低功耗映射算法