Computer Science ›› 2019, Vol. 46 ›› Issue (8): 100-105.doi: 10.11896/j.issn.1002-137X.2019.08.016

• HPC China 2018 • Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] WU Wei-nan, LIU Jian-ming. Dynamic Retransmission Algorithm inLow-power Wireless Sensor Networks [J]. Computer Science, 2018, 45(6): 96-99.
[2] WANG Yao-xing and LIU Jian-jun. Design of Low-power Node and Interface Protocol in WSN [J]. Computer Science, 2014, 41(Z11): 228-231.
[3] TIAN Ze,ZHANG Jun,XU Hong-jie,GUO Liang and LI Xiao-yu. Low-power Design Techniques for GPU [J]. Computer Science, 2013, 40(Z6): 210-216.
[4] FANG Juan,GUO Mei and DU Wen-juan. WPP-L2:A Way-predicting Algorithm for Shared L2Cache of Multi-core Processors [J]. Computer Science, 2013, 40(8): 34-37.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!