万方数据万方数据万方数据万方数据2期常政威等:片上网络映射问题的改进禁忌搜索算法159的能力.对每个IP核通信任务图,用TSNM,RoTS,ITS(iterativeTS和分支限界(branchandbound,BB算法一J分别运行相同的CPU时间求解,以比较它们的优化结果.其中,ITS算法是指不包含精英重组步骤的简化TSNM算法,每次局部搜索迭代都使用随机产生的初始解.由于前3种算法是随机优化算法,因此对每个问题各独立运行10次,NoC通信能耗值取10次优化结果的最优值.在求解规模为咒的问题时,TSNM的参数设置为:局部搜索内部迭代次数z=0.1x,12,EQ长度s=咒.衡麟缣掣ASIC:l,5,8,13,21,25Mem:7,14,19,24CPU:6。12,18DSP:2,3,4,9,10,11,15,16,17,20,22,23图4多媒体系统MMS以RoTS算法的优化结果为标准,图5所示为各种算法的求解性能比较.从图中可以看出:1当IP核通信任务图中的节点数较少(25~36时,TSNM,RoTS和ITS算法得到了基本相同的优化结果.但随着节点数的增加,TSNM获得了较RoTS更优的结果.ITS在这3种算法中的性能最差,这是因为其缺乏有效的分散搜索机制,从而弱化了集中搜索的效果.而TSNM采用COHX交叉操作,构造出新的可行解,保留了已有的搜索状态信息,取得了良好的优化结果.节点,在较短的时间内获得最优解.随着节点数的增加,TSNM的性能明显优于BB,最高可节省能耗28.5%,平均节能16.1%.第2组实验评估TSNM算法的搜索效率.用RoTS和TSNM分别求解多媒体系统MMS,当算法首次搜索到最优解130.06mJ时,便终止其运行,得到的NoC映射结果如图6所示.图6MMS的映射结果图7所示为RoTS和TSNM求解MMS的映射问题时,NoC通信能耗值随搜索过程的变化情况.从图中可以看出,TSNM大大地缩小了对状态空问的搜索范围,而且具有较快的收敛速度,经过0.35s获得了最优解,比RoTS提高了约50%。由此可知,通过集中和分散机制,TSNM实现了对映射空间的高效搜索.-g300\薹250逛200罨-50Z童\耀拦逛赠譬3002502001500.10.20.30.40.50.6时间/saRoTS搜索过程4结论图5各种算法的求解性能比较通信时延受约束的低能耗N。c映射是一个NP2对于节点数为25的IP核通信任务图,因为难问题,精确求最优解是非常困难的.针对RoTS算问题规模较小,BB算法可以遍历其搜索树中的所有法求解NoC“”映射的停滞现象,本文将禁忌搜索和万方数据１６０计算机辅助设计与图形学学报２００８年遗传算法融合起来，提出了一种改进禁忌搜索算法ＴＳＮＭ．ＴＳＮＭ基于集中和分散机制，用简化后的ＲＯＴＳ实现对优良区域的集中搜索，并对局部优化结果中的精英个体采用ＣＯＨＸ交叉操作，以扩展全局搜索范围．实验结果表明，ＴＳＮＭ实现了对状态空间的高效搜索，获得了更好的优化结果，适合于大规模ＮｏＣ映射问题的求解．［９】ＲｈｅｅＣｈａｅ．Ｅｕｎ，Ｊｅｏｎｇｃｏｒｅ．ｓｗｉｔｃ——ｈｌ－ｌａｎＹｏｕ，Ｈａ２－ＤＳｏｏｎｈｏｉ．Ｍａｎｙｔｏ－ｍａｎｙａｒｃｈｉｔｅｃｔｕｒｅｓ［Ｃ】／／ｏＤｍａｐｐｉｎｇＩＥＥＥｉｎｍｅｓｈＮｏＣＰｒｏｃｅｅｄｉｎｇｓｏｆＤｅｓｉｇｎ，ＳａｎＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅＣｏｍｐｕｔｅｒＪｏｓｅ，ＣＡ，２００４：４３８—４４３ｏｆｏｎ［１０］ＷｕＣｈｉａ———Ｍｉｎｇ，ＣｈｉＨｓｉｎＣｂｏｕ，ＬｅｅＭｉｎｇＣｈａｏ．ＭａｐｐｉｎｇＩＰｃｏｒｅｓｔｏｎｅｔｗｏｒｋ－ｏｎ－ｃｈｉｐａｒｃｈｉｔｅｃｔｕｒｅｓｂａｓｅｄｏｆｔｈｅｃｏｍｍｕｎｉｃａｔｉｏｎｔａｓｋｇｒａｐｈｓ［Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓｏｎ６ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅＡＳＩＣ，Ｓｈａｎｇｈａｉ，２００５：９５３—９５６Ｙｏｎｇｈｕａ，ｅｔａ１．ＮｏＣ［１１］ＺｈｏｕＧａｎｍｉｎ，ＹｉｎｂａｓｅｄｏｎＹｏｎｇｓｈｅｎｇ，Ｈｕａｎｔｍａｐｐｉｎｇｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ参考ａｌｇｏｒｉｔｈｍ［Ｊ］．文献ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００５。４１（１８）：７一１１（ｉｎＣｈｉｎｅｓｅ）［１】ＢｊｅｒｒｅｇａａｒｄＴ，ＭａｈｅｄｅｖａｎｏｆＳ．ＡｓｕｒｖｅｙｏｆｒｅｓｅａｒｃｈａｎｄｐｒａｃｔｉｃｅｓＳｕｒｖｅｙｓ...