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

doi:10.11772/j.issn.1001-9081.2017.01.0090

计算机应用 ›› 2017, Vol. 37 ›› Issue (1): 90-96.DOI: 10.11772/j.issn.1001-9081.2017.01.0090

• 2016年全国开放式分布与并行计算学术年会(DPCS2016)论文 • 上一篇下一篇

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

宋国治¹, 王铖^1,2, 涂遥¹, 张大坤¹

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

收稿日期:2016-07-30 修回日期:2016-08-07 出版日期:2017-01-10 发布日期:2017-01-09
通讯作者: 宋国治
作者简介:宋国治(1977-),男,黑龙江哈尔滨人,副教授,博士,CCF会员,主要研究方向:三维片上网络、无线传感器网络、异构网络融合;王铖(1995-),男,安徽阜阳人,主要研究方向:三维片上网络;涂遥(1992-),男,安徽淮南人,硕士研究生,主要研究方向:三维片上网络布局优化;张大坤(1960-),女,辽宁阜新人,教授,博士,主要研究方向:三维片上网络、虚拟现实、组合算法。
基金资助:
国家自然科学基金资助项目（61272006）；国家级大学生创新创业训练计划项目（201510058050）。

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

SONG Guozhi¹, WANG Cheng^1,2, TU Yao¹, ZHANG Dakun¹

1. School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300387, China;
2. School of Information Science and Engineering, Yunnan University, Kunming Yunnan 650091, China

Received:2016-07-30 Revised:2016-08-07 Online:2017-01-10 Published:2017-01-09
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61272006), National Undergraduate Training Program for Innovation and Entrepreneurship (201510058050).

摘要/Abstract

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

关键词: 三维片上网络, 低功耗, 映射算法, 遗传算法, Prim算法

Abstract: 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.

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

中图分类号:

TP393.01

宋国治, 王铖, 涂遥, 张大坤. 基于Prim初始种群选取优化遗传算法的三维片上网络低功耗映射[J]. 计算机应用, 2017, 37(1): 90-96.

SONG Guozhi, WANG Cheng, TU Yao, ZHANG Dakun. Low power mapping based on improved genetic algorithm with Prim initial population selection for 3D network-on-chip[J]. Journal of Computer Applications, 2017, 37(1): 90-96.

参考文献

[1] 张大坤,黄翠,宋国治.三维片上网络研究综述[J].软件学报,2016,27(1):155-187.(ZHANG D K, HUANG C, SONG G Z. A survey of three dimensional network on chip[J]. Journal of Software, 2016, 27(1):155-187.)
[2] MORGAN A A, ELMILIGI H, EL-KHARASHI M W, et al. Multi-objective optimization for networks-on-chip architectures using genetic algorithms[C]//ISCAS 2010:Proceedings of 2010 IEEE International Symposium on Circuits and Systems. Piscataway, NJ:IEEE, 2010:3725-3728.
[3] 刘炎华,刘静,赖宗声,等.基于遗传蚁群算法的片上网络映射研究[J].计算机工程,2010,36(22):262-264.(LIU Y H, LIU J, LAI Z S, et al. Research of network on chip mapping based on genetic and ant colony algorithm[J]. Computer Engineering, 2010, 36(22):262-264.)
[4] HU J, MARCULESCU R. Energy- and performance-aware mapping for regular NoC architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 24(4):551-562.
[5] 林桦,李险峰,佟冬,等.保证QoS的片上网络低能耗映射与路由方法[J].计算机辅助设计与图形学学报,2008,20(4):425-431.(LIN H, LI X F, TONG D, et al. A low energy mapping and routing approach for network-on-chip with QoS guarantees[J]. Journal of Computer-Aided Design & Computer Graphics, 2008, 20(4):425-431.)
[6] 王雷,凌翔,胡剑浩.异构多核协作系统的混沌离散粒子群NoC映射算法[J].计算机科学,2011,38(9):298-303.(WANG L, LING X, HU J H. NoC mapping for heterogeneous multi-core cooperative system based on chaotic discrete particle swarm optimization[J]. Computer Science, 2011, 38(9):298-303.)
[7] 常政威,谢晓娜,桑楠,等.片上网络映射问题的改进禁忌搜索算法[J].计算机辅助设计与图形学学报,2008,20(2):155-160.(CHANG Z W, XIE X N, SANG N, et al. An improved tabu search algorithm for network-on-chip mapping[J]. Journal of Computer-Aided Design and Computer Graphics, 2008, 20(2):155-160.)
[8] 杨盛光,李丽,高明伦,等.面向能耗和延时的NoC映射方法[J].电子学报,2008,36(5):937-942.(YANG S G, LI L, GAO M L, et al. An energy and delay-aware mapping method of NoC[J]. Acta Electronica Sinica, 2008, 36(5):937-942.)
[9] 王佳文,李丽,易伟,等.3D NoC映射问题的动态蚁群算法[J].计算机辅助设计与图形学学报,2011,23(9):1614-1620.(WANG J W, LI L, YI W, et al. A dynamic ant colony optimization algorithm for 3D NoC mapping[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(9):1614-1620.)
[10] 李东生,刘琪.面向通信能耗的3D NoC映射研究[J].半导体技术,2012(7):504-507.(LI D S, LIU Q. Research on mapping 3D network on chip for communication energy-aware[J]. Semiconductor Technology,2012(7):504-507.)
[11] 黄翠.基于量子粒子群的三维片上网络低功耗映射算法研究[D].天津:天津工业大学,2015.(HUANG C, Research on a low-power mapping algorithm for 3D NoC based on diversity-controlled quantum-behaved particle swarm optimization[D]. Tianjin:Tianjin Polytechnic University, 2015.)
[12] 杨微,张振,刘怡俊.基于改进粒子群的3D-Mesh CMP片上网络映射算法[J].计算机应用研究,2013,30(5):1345-1348.(YANG W, ZHANG Z, LIU Y J. Improved particle swarm optimization algorithm based mapping algorithm for 3D-Mesh CMP[J]. Application Research of Computers, 2013, 30(5):1345-1348.)
[13] LEI T, KUMAR S. A two-step genetic algorithm for mapping task graphs to a network on chip architecture[C]//DSD' 03:Proceedings of the Euromicro Symposium on Digital Systems Design. Washington, DC:IEEE Computer Society, 2003:180-187.
[14] ASCIA G, CATANIA V, PALESI M. Multi-objective mapping for mesh-based NoC architectures[C]//CODES+ISSS' 04:Proceedings of the 2nd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. New York:ACM, 2004:182-187.
[15] 张涛涛.热/流均衡的混合型3D NoC拓扑结构设计与映射算法研究[D].南京:南京航空航天大学,2014.(ZHANG T T. Exploration of topology and mapping algorithm for thermal traffic balanced 3D NoC bus hybrid architecture[D]. Nanjing:Nanjing University of Aeronautics and Astronautics, 2014.)
[16] ADDO-QUAYE C. Thermal-aware mapping and placement for 3-D NoC designs[C]//Proceedings 2005 IEEE International SOC Conference. Piscataway, NJ:IEEE, 2005:25-28.
[17] YING H, HEID K, HOLLSTEIN T, et al. A genetic algorithm based optimization method for low vertical link density 3-dimensional networks-on-chip many core systems[C]//NORCHIP 2012:Proceedings of the 30th Norchip Conference. Piscataway, NJ:IEEE, 2012:1-4.
[18] WANG J, LI L, PAN H, et al. Latency-aware mapping for 3D NoC using rank-based multi-objective genetic algorithm[C]//ASICON 2011:Proceedings of the 2011 IEEE 9th International Conference on ASIC. Piscataway, NJ:IEEE, 2011:413-416.
[19] 林华洲,张大坤,黄翠.基于Prim算法的改进遗传算法的3D NoC低功耗映射研究[J].计算机工程与应用,2016,52(1):76-80.(LIN H Z, ZHANG D K, HUANG C. Research on low-power mapping for three-dimensional network-on-chip based on improved genetic algorithm[J]. Computer Engineering and Applications, 2016, 52(1):76-80.)
[20] HOLLAND J H. Adaptation in Natural and Artificial Systems:An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence[M]. Cambridge:The MIT Press, 1992Control & Artificial Intelligence University of Michigan Press, 1975, 6(2):126-137.
[21] 马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(4):1201-1206.(MA Y J, YUN W X. Research progress of genetic algorithm[J]. Application Research of Computers, 2012, 29(4):1201-1206.)
[22] JHENG K Y, CHAO C H, WANG H Y, et al. Traffic-thermal mutual-coupling co-simulation platform for three-dimensional network-on-chip[C]//VLSI-DAT 2010:Proceedings of the 2010 International Symposium on VLSI Design Automation and Test. Piscataway, NJ:IEEE, 2010:135-138.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[2]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[3]	张玲, 邝继顺. 环形链轮询复用测试端口的高效测试结构[J]. 计算机应用, 2021, 41(7): 2156-2160.
[4]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[5]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[6]	刘世泽, 秦艳君, 王晨星, 高存远, 罗海勇, 赵方, 王宝会. 基于多尺度特征提取的交通模式识别算法[J]. 计算机应用, 2021, 41(6): 1573-1580.
[7]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[8]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[9]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[10]	马晓梅, 何非. 基于改进遗传算法的标签印刷生产调度技术[J]. 计算机应用, 2021, 41(3): 860-866.
[11]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[12]	张阳, 王小宁. 基于Word2Vec词嵌入和高维生物基因选择遗传算法的文本特征选择方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3151-3155.
[13]	陈港, 孟相如, 康巧燕, 阳勇. 基于拓扑分割与聚类分析的虚拟软件定义网络映射算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3309-3318.
[14]	黄晓祥, 胡咏梅, 吴丹, 任力杰. 基于变分自编码器的异常颈动脉早期识别和预测[J]. 计算机应用, 2021, 41(10): 3082-3088.
[15]	杨华龙, 王美玉, 辛禹辰. 横向整合战略下异质车辆库存路径优化模型[J]. 计算机应用, 2021, 41(10): 3040-3048.