A novel mapping algorithm for three-dimensional network on chip based on quantum-behaved particle swarm optimization

doi:10.1007/s11704-016-5196-0

Front. Comput. Sci.

2017, Vol. 11

Issue (4) : 622-631 https://doi.org/10.1007/s11704-016-5196-0

RESEARCH ARTICLE

A novel mapping algorithm for three-dimensional network on chip based on quantum-behaved particle swarm optimization

Cui HUANG, Dakun ZHANG(

), Guozhi SONG

School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300387, China

Download: PDF(542 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Mapping of three-dimensional network on chip is a key problem in the research of three-dimensional network on chip. The quality of the mapping algorithm used directly affects the communication efficiency between IP cores and plays an important role in the optimization of power consumption and throughput of the whole chip. In this paper, basic concepts and related work of three-dimensional network on chip are introduced. Quantum-behaved particle swarm optimization algorithm is applied to the mapping problem of three-dimensional network on chip for the first time. Simulation results show that the mapping algorithm based on quantum-behaved particle swarm algorithm has faster convergence speed with much better optimization performance compared with the mapping algorithm based on particle swarm algorithm. It also can effectively reduce the power consumption of mapping of three-dimensional network on chip.

Keywords three-dimensional network on chip mapping algorithm quantum-behaved particle swarm optimization algorithm particle swarm optimization algorithm low power consumption

Corresponding Author(s): Dakun ZHANG

Just Accepted Date: 17 June 2016 Online First Date: 23 March 2017 Issue Date: 26 July 2017

Cite this article:

Cui HUANG,Dakun ZHANG,Guozhi SONG. A novel mapping algorithm for three-dimensional network on chip based on quantum-behaved particle swarm optimization[J]. Front. Comput. Sci., 2017, 11(4): 622-631.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-5196-0
https://academic.hep.com.cn/fcs/EN/Y2017/V11/I4/622

1	ChenY, HuJ, LingX. Study on three-dimensional network on chip. Telecommunications Science, 2009, 25(4): 39–44
2	MagarshackP, PaulinP G. System-on-chip beyond the nanometer wall. In: Proceedings of the 40th Annual Design Automation Conference. 2003, 419–424 https://doi.org/10.1145/775832.775943
3	DallyW J, TowlesB. Route packets, not wires: on-chip interconnection networks. In: Proceedings of the 38th Design Automation Conference. 2001, 684–689 https://doi.org/10.1109/dac.2001.935594
4	BeniniL, De Micheli G. Networks on chips: a new SoC paradigm. IEEE Computer, 2002, 35(1): 70–78 https://doi.org/10.1109/2.976921
5	KangA B. The ITRS design technology and system drivers roadmap: process and status. In: Proceedings of the 50th Design Automation Conference. 2013, 1–6 https://doi.org/10.1145/2463209.2488776
6	PalesiM, Daneshtalab M. Routing Algorithms in Network-on-Chip. New York: Springer, 2014 https://doi.org/10.1007/978-1-4614-8274-1
7	XiangD, LiuG, ChakrabartyK , FujiwareH. Thermal-aware test scheduling for NOC-based 3D integrated circuits. In: Proceedings of the 21st IFIP/IEEE International Conference on Very Large Scale Integration. 2013, 96–101 https://doi.org/10.1109/vlsi-soc.2013.6673257
8	RahmaniA M, Vaddina K R, LatifK , LiljebergP, Plosila J, TenhunenH . Design and management of hign-performance, reliable and thermalaware 3D network-on-chip. IET Circuits, Devices & Systems, 2012, 6(5): 308–321 https://doi.org/10.1049/iet-cds.2011.0349
9	HassanpournN, Hessabi S, HamedaniP K . Temperature control in three-network on chips using task migration. IET Computers & Digital Techniques, 2013, 7(6): 274–281 https://doi.org/10.1049/iet-cdt.2013.0016
10	ChengY, ZhangL, HanY, Li X. Thermal-constrained task allocation for interconnect energy reduction in 3-D homogeneous MPSoCs. IEEE Transactions on Very Large Scale Integration Systems, 2013, 21(2): 239–249 https://doi.org/10.1109/TVLSI.2011.2182067
11	WangJ, LiL, YiW. A dynamic ant colony optimization algorithm for 3D NoC mapping. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(9): 1614–1620
12	WangJ, LiL, PanH, He S, ZhangR . Latency-aware mapping for 3D NoC using rank-based multi-objective genetic algorithm. In: Proceedings of the 9th IEEE International Conference on ASIC. 2011, 413–416
13	SahniS, Gonzales T. P-complete approximation problems. Journal of the ACM, 1976, 23(3): 555–565 https://doi.org/10.1145/321958.321975
14	YangW. Study on low-power mapping of network on chip. Modern Computer, 2015, 3(3): 10–13
15	SahuP, Chattopadhyay S. A survey on application mapping strategies for network-on-chip design. Journal of Systems Architecture, 2013, 59(2013): 60–76 https://doi.org/10.1016/j.sysarc.2012.10.004
16	YangW, ZhangZ, LiuY. Improved particle swarm optimization algorithm based mapping algorithm for 3D-Mesh CMP. Application Research of Computers, 2013, 30(5): 1345–1348
17	MatsutaniH, Koibuchi M, AmanoH . Tightly-coupled multi-layer topologies for 3-D NoCs. In: Proceedings of International Conference on Parallel Processing. 2007 https://doi.org/10.1109/icpp.2007.79
18	KennedyJ, Eberhart R C. Particle Swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks. 1995, 1942–1948 https://doi.org/10.1109/ICNN.1995.488968
19	HeppnerF, Grenander U. A stochastic nonlinear model for coordinated bird rocks. The Ubiquity of Chaos, 1990
20	WangD W, WangJ W, WangH F, Zheng R, GuoZ . Intelligent Optimization Methods. Beijing:Higher Education Press, 2007
21	SunJ. Study on Quantum-Behaved Particle Swarm Optimization Algorithm.Jiangnan University, 2009
22	Van Den BerghF. An analysis of particle swarm optimizers. Particle Swarm Optimization, 2002
23	WangF. Analysis of key characteristics of through-silicon-via (TSV)- based three-dimensional integrated circuits (3D ICs). Dissertation for the Doctoral Degree. Xi’an: Xidian University, 2014
24	KimJ, PakJ S, ChoJ, Song E, ChoJ , KimH, SongT, LeeJ, Lee H, ParkK , YangS, SuhM, ByunK, Kim J. High-frequency scalable electrical model and analysis of a through silicon via (TSV). IEEE Transactions On Components, Packaging and Manufacturing Technology, 2011, 1(2): 181–195 https://doi.org/10.1109/TCPMT.2010.2101890
25	JhengK Y, ChaoC H, WangH Y, Wu A Y. Traffic-thermal mutualcoupling co-simulation platform for three-dimensional Network-on- Chip. In: Proceedings of International Symposium on VLSI Design Automation and Test. 2010, 135–138
26	DickR P, RhodesD L, WolfW. TGFF: task graphs for free. In: Proceedings of the 6th International Workshop on Hardware/Software Code Sign. 1998, 97–101 https://doi.org/10.1145/278241.278309

[1]

FCS-0622-15196-DKZ_suppl_1

Download

[1]	Wei ZHAO, Ye SAN. RBF neural network based on q-Gaussian function in function approximation[J]. Front Comput Sci Chin, 2011, 5(4): 381-386.
[2]	Xuejun YANG, Xiangke LIAO, Weixia XU, Junqiang SONG, Qingfeng HU, Jinshu SU, Liquan XIAO, Kai LU, Qiang DOU, Juping JIANG, Canqun YANG, . TH-1: China’s first petaflop supercomputer[J]. Front. Comput. Sci., 2010, 4(4): 445-455.

Viewed

Full text

Abstract

Cited

Shared

Discussed