计算机科学 ›› 2019, Vol. 46 ›› Issue (8): 100-105.doi: 10.11896/j.issn.1002-137X.2019.08.016

• 2018 全国高性能计算学术年会 • 上一篇    下一篇

基于混合混沌大爆炸算法的三维片上网络低功耗映射

范星冉1, 宋国治1, 李加正2   

  1. (天津工业大学计算机科学与技术学院 天津300387)1
    (伊利诺伊大学香槟分校信息科学学院 尚佩恩 IL61820)2
  • 收稿日期:2018-10-15 出版日期:2019-08-15 发布日期:2019-08-15
  • 通讯作者: 宋国治(1977-),男,博士,副教授,硕士生导师,CCF会员,主要研究方向为下一代网络技术、异构无线网络,E-mail:songguozhi@tjpu.edu.cn
  • 作者简介:范星冉(1993-),女,硕士生,主要研究方向为三维片上网络;李加正(1995-),男,硕士生,主要研究方向为三维片上网络

Low-power Mapping Method for Three-dimensional Network on Chip Based on Hybrid Chaotic Big Bang-big Crunch

FAN Xing-ran1, SONG Guo-zhi1, LI Jia-zheng2   

  1. (School of Computer Science and Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China)1
    (School of Information Sciences,University of Illinois at Urbana-Champaign,Champaign IL61820,USA)2
  • Received:2018-10-15 Online:2019-08-15 Published:2019-08-15

摘要: 三维片上网络(3D NoC)被认为是提高多核处理系统性能的一种方式。对于3D NoC的设计,如何将给定应用特征图(APCG)上的IP核适当地分配到3D NoC架构中是IP核映射的关键问题。一种优秀的映射算法及一次合理的映射可以大幅改善片上网络的通信功耗、发热、延时等指标。大爆炸算法(BB-BC)是一种新型的元启发式群体智能优化算法;混合混沌大爆炸(HCBB-BC)算法是在大爆炸算法基础上进行改进的一种算法,它具有参数简单、收敛速度快等优点。文中提出将混合混沌大爆炸算法用于解决三维片上网络映射问题,这是首次用大爆炸算法的相关算法来解决3D NoC映射问题。仿真实验结果证明,与现有的3D NoC映射算法相比,所提方法可以用更少的迭代次数和时间来找到更好的解决方案,同时有效地降低3D NoC的映射功耗。在经典任务图映射条件下,混合混沌大爆炸算法与遗传算法(GA)相比,收敛速度提高了36.73%,与粒子群算法(PSO)相比,收敛速度提高了22.45%;同时,混合混沌大爆炸算法的平均功耗比遗传算法的平均功耗的最大值低5.75%,并且比粒子群算法的平均功耗的最大值低3.90%。在随机任务图映射条件下,混合混沌大爆炸算法仍然能够保持稳定的功耗优化效率和更快的收敛速度。

关键词: 三维片上网络, 映射算法, 低功耗, 大爆炸算法, 混合混沌大爆炸算法

Abstract: Three-dimensional network on chip (3D NoC) is envisioned as a way to achieve high performance of multi-processor systems.For the design of 3D NoC,how to properly allocate IP cores on a given application feature map (APCG) to the 3D NoC architecture is the key problem of IP core mapping.An excellent mapping algorithm and a reasonable mapping can greatly improve the power consumption,heating,delay and other indicators of network-on-chip.The big bang-big crunch (BB-BC) algorithm is a new type of meta-heuristic swarm intelligence optimization algorithm.The hybrid chaotic big bang-big crunch (HCBB-BC) is a modified algorithm based on the big bang-big crunch (BB-BC) algorithm,which has simple parameters and fast convergence speed.In this paper,the hybrid chaotic big bang-big crunch (HCBB-BC) was proposed to solve the problem of 3D NoC mapping.This is the first time that big bang-big crunch (BB-BC) algorithm is used to solve the 3D NoC mapping problem.Simulations are conducted to prove that the proposed method requirs less number of iterations and time to find a better solution and can reduce energy consumed compared with existing NoC mapping algorithms.Under the condition of the classical task graphs,compared with the genetic algorithm (GA) algorithm,the convergence speed of the hybrid chaotic big bang-big crunch (HCBB-BC) is increased by 36.73%,and the 22.45% improvement is witnessed compared with the particle swarm optimization (PSO) algorithm.The average power consumption of the hybrid chaotic big bang-big crunch (HCBB-BC) mapping is lower than that of GA with the maximum as 5.75%,and lower than that of PSO with the maximum as 3.90%.Under the condition of the random tasks,the hybrid chaotic big bang-big crunch (HCBB-BC) algorithm can still maintain stable optimization efficiency and higher convergence speed

Key words: Three-dimensional network on chip, Mapping algorithm, Low-power, Big bang-big crunch, Hybrid chaotic big bang-big crunch

中图分类号: 

  • TP393
[1] DALLY W J,TOWLES B.Route packets,not wires:On-Chip interconnection networks[C]∥Proceedings of the 38th Design Automation Conference (DAC 2001).New York:ACM Press,2001:684-689.
[2] WANG C P.Design of NoC High Performance Interconnect Structure Based on TSV[D].Xi’an:Xidian University,2014.(in Chinese) 王昌鹏.基于TSV的NoC高性能互连结构设计[D].西安:西安电子科技大学,2014.
[3] SAHNI S.P-Complete Approximation Problems[J].Journal of the Acm,1976,23(3):555-565.
[4] PALANIVELOO V A,AMBROSE J A,SOWMYA A.Impro- ving GA-Based NoC Mapping Algorithms Using a Formal Mo-del[C]∥2014 IEEE Computer Society Annual Symposium on VLSI.IEEE,2014:344-349.
[5] ZHONG L,SHENG J,JING M,et al.An optimized mapping algorithm based on Simulated Annealing for regular NoC architecture[C]∥IEEE International Conference on Asic.IEEE,2011:389-392.
[6] SAHU P K,SHAH T,MANNA K,et al.Application Mapping Onto Mesh-Based Network-on-Chip Using Discrete Particle Swarm Optimization[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2014,22(2):300-312.
[7] LI J,SONG G,MA Y,et al.Bat Algorithm Based Low Power Mapping Methods for 3D Network-on-Chips[M]∥Theoretical Computer Science.Singapore:Springer,2017:277-295.
[8] XIE Y,LIU Y.A research on NoC mapping with Quantum Ant Colony Algorithm[C]∥International Conference on Wireless Communications,Signal Processing and Networking.IEEE,2017:874-877.
[9] TENG L,LI H.A new frog leaping algorithm based on simulated annealing and immunization algorithm for low-power mapping in network-on-chip[J].Journal of Information Hiding and Multimedia Signal Processing 2018,9(3):716-722.
[10] OBAIDULLAH M,KHAN G N.Hybrid multi-swarm optimization based NoC synthesis[C]∥IEEE International System-On-Chip Conference.IEEE,2017:62-67.
[11] JIN X,GUAN N,DENG Q,et al.Memory Access Aware Mapping for Networks-on-Chip[C]∥IEEE International Conference on Embedded and Real-Time Computing Systems and Applications.IEEE,2011:339-348.
[12] WANG X H,LIU P,YANG M,et al.Energy Efficient Run-Time Incremental Mapping for 3-D Networks-on-Chip[J].Journal of Computer Science and Technology,2013,28(1):54-71.
[13] EROL O K,EKSIN I.A new optimization method:Big Bang-Big Crunch.Advances in Engineering Software,2006,37(2):106-111.
[14] LI S Y.Research and Improvement of Big Bang Algorithm [D].Guangzhou:Guangdong University of Technology,2014.(in Chinese) 李少勇.大爆炸算法的研究与改进[D].广州:广东工业大学,2014.
[15] KIM J,PAK J S,CHO J.High-frequency scalable electrical model and analysis of a through silicon via (TSV)[J].IEEE transactions on components packaging and manufacturing technology,2011,1(2):181-195.
[16] 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]∥International Symposium on Vlsi Design Automation and Test.IEEE,2010:135-138.
[17] YUAN L Y.Research of Communication Strategy for Multi Cores on NoC [D].Dalian:Dalian University of Technology,2009.(in Chinese) 袁立业.NoC上的多核间通信策略研究[D].大连:大连理工大学,2009.
[18] DICK R P,RHODES D L,WOLF W.TGFF:task graphs for free[C]∥Proceedings of Sixth IEEE International Workshop on Hardware/Software Codesign (CODES/CASHE’98).IEEE,1998:97-101.
[1] 王华华, 周远文, 刘江兵. LLN中基于混合式的网络拥塞控制路由算法[J]. 计算机科学, 2019, 46(6): 107-111.
[2] 朱艳娜,王党辉. 基于多级磁自旋存储器的Cache调度策略的设计[J]. 计算机科学, 2018, 45(6A): 513-517.
[3] 吴伟男, 刘建明. 面向低功耗无线传感器网络的动态重传算法[J]. 计算机科学, 2018, 45(6): 96-99,123.
[4] 谈恩民,范玉祥. 一种基于海明排序进行无关位填充的低功耗测试向量优化方法[J]. 计算机科学, 2018, 45(2): 249-253.
[5] 宋国治 张大坤 涂 遥 黄 翠 王莲莲. 一种改进的基于粒子群的三维片上网络优化布局算法[J]. 计算机科学, 2015, 42(7): 114-117, 124.
[6] 王耀兴,刘建军. 低功耗WSN节点及其接口协议的设计[J]. 计算机科学, 2014, 41(Z11): 228-231.
[7] 方娟,王帅,于璐. 面向低功耗共享Cache路适应划分算法研究[J]. 计算机科学, 2014, 41(7): 36-39,73.
[8] 冯永,姚龙海,张亮. 基于M/M/1/K排队模型的低功耗无线通信网络TDMA协议延迟评估及仿真[J]. 计算机科学, 2013, 40(Z6): 262-264,286.
[9] 田泽,张骏,许宏杰,郭亮,黎小玉. 图形处理器低功耗设计技术研究[J]. 计算机科学, 2013, 40(Z6): 210-216.
[10] 方娟,郭媚,杜文娟. WPP-L2:多核处理器中共享Cache低功耗路预测算法[J]. 计算机科学, 2013, 40(8): 34-37,42.
[11] 王剑锋,陈灿峰,刘嘉,郗闽军. 一种基于IPv6和低功耗蓝牙的物联网体系结构[J]. 计算机科学, 2013, 40(5): 97-102.
[12] 葛红美,徐超,陈念,廖希密. 一种面向嵌入式系统总线的低功耗优化方法[J]. 计算机科学, 2013, 40(12): 31-36.
[13] 曹洪新,李光顺,吴俊华. 基于一种新网络拓扑结构的低功耗研究[J]. 计算机科学, 2012, 39(Z11): 327-330.
[14] 张立,韩银和,袁小龙. 一种基于Android系统网络模块功耗的评估和分析[J]. 计算机科学, 2012, 39(6): 289-292.
[15] 史莉雯,樊晓桠,陈杰,黄小平,郑乔石. 程序行为分析指导TLB低功耗设计[J]. 计算机科学, 2011, 38(5): 301-305.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105, 130 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111, 142 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121, 136 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .