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

doi:10.11896/j.issn.1002-137X.2019.08.016

摘要/Abstract

摘要： 三维片上网络(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: Big bang-big crunch, Hybrid chaotic big bang-big crunch, Low-power, Mapping algorithm, Three-dimensional network on chip

中图分类号:

TP393

范星冉, 宋国治, 李加正. 基于混合混沌大爆炸算法的三维片上网络低功耗映射[J]. 计算机科学, 2019, 46(8): 100-105. https://doi.org/10.11896/j.issn.1002-137X.2019.08.016

FAN Xing-ran, SONG Guo-zhi, LI Jia-zheng. Low-power Mapping Method for Three-dimensional Network on Chip Based on Hybrid Chaotic Big Bang-big Crunch[J]. Computer Science, 2019, 46(8): 100-105. https://doi.org/10.11896/j.issn.1002-137X.2019.08.016

参考文献

[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.

相关文章 15

[1]	何权奇, 余飞鸿. 面向无线网络相机的低功耗架构研究综述 Review of Low Power Architecture for Wireless Network Cameras 计算机科学, 2021, 48(6A): 369-373. https://doi.org/10.11896/jsjkx.201100099
[2]	张英, 陶磊岩, 曹健, 王世会, 赵茜, 张兴. 实时低功耗飞行器神经网络 Real-time Low Power Consumption Aircraft Neural Network 计算机科学, 2021, 48(3): 196-200. https://doi.org/10.11896/jsjkx.191200142
[3]	王华华, 周远文, 刘江兵. LLN中基于混合式的网络拥塞控制路由算法 Hybrid-based Network Congestion Control Routing Algorithm for LLN 计算机科学, 2019, 46(6): 107-111. https://doi.org/10.11896/j.issn.1002-137X.2019.06.015
[4]	朱艳娜,王党辉. 基于多级磁自旋存储器的Cache调度策略的设计 Design of Cache Scheduling Policies Based on MLC STT-RAM 计算机科学, 2018, 45(6A): 513-517.
[5]	吴伟男, 刘建明. 面向低功耗无线传感器网络的动态重传算法 Dynamic Retransmission Algorithm inLow-power Wireless Sensor Networks 计算机科学, 2018, 45(6): 96-99. https://doi.org/10.11896/j.issn.1002-137X.2018.06.016
[6]	谈恩民,范玉祥. 一种基于海明排序进行无关位填充的低功耗测试向量优化方法 Optimization Method of Low Power Test Vectors Based on Hamming Sorting for X Bits Padding 计算机科学, 2018, 45(2): 249-253. https://doi.org/10.11896/j.issn.1002-137X.2018.02.043
[7]	宋国治张大坤涂遥黄翠王莲莲. 一种改进的基于粒子群的三维片上网络优化布局算法 Improved Algorithm for 3D NoC Floorplan Based on Particle Swarm Optimization 计算机科学, 2015, 42(7): 114-117. https://doi.org/10.11896/j.issn.1002-137X.2015.07.024
[8]	王耀兴,刘建军. 低功耗WSN节点及其接口协议的设计 Design of Low-power Node and Interface Protocol in WSN 计算机科学, 2014, 41(Z11): 228-231.
[9]	方娟,王帅,于璐. 面向低功耗共享Cache路适应划分算法研究 Research of Lower Power Oriented Way-adaptive Partition Algorithm in Shared Cache of CMP 计算机科学, 2014, 41(7): 36-39. https://doi.org/10.11896/j.issn.1002-137X.2014.07.006
[10]	田泽,张骏,许宏杰,郭亮,黎小玉. 图形处理器低功耗设计技术研究 Low-power Design Techniques for GPU 计算机科学, 2013, 40(Z6): 210-216.
[11]	冯永,姚龙海,张亮. 基于M/M/1/K排队模型的低功耗无线通信网络TDMA协议延迟评估及仿真 Delay Evaluation and Simulation of TDMA Through M/M/1/K Queue Model in Low-energy Wireless Communication Environment 计算机科学, 2013, 40(Z6): 262-264.
[12]	方娟,郭媚,杜文娟. WPP-L2:多核处理器中共享Cache低功耗路预测算法 WPP-L2:A Way-predicting Algorithm for Shared L2Cache of Multi-core Processors 计算机科学, 2013, 40(8): 34-37.
[13]	王剑锋,陈灿峰,刘嘉,郗闽军. 一种基于IPv6和低功耗蓝牙的物联网体系结构 Internet of Things Architecture Based on IPv6and Bluetooth Low Energy 计算机科学, 2013, 40(5): 97-102.
[14]	葛红美,徐超,陈念,廖希密. 一种面向嵌入式系统总线的低功耗优化方法 Low Power Optimization Method Oriented to Embedded System’s Bus 计算机科学, 2013, 40(12): 31-36.
[15]	曹洪新，李光顺，吴俊华. 基于一种新网络拓扑结构的低功耗研究 Low Power Research Based on a New NoC Topology Architecture 计算机科学, 2012, 39(Z11): 327-330.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed