Fig. 1.
Architecture for baseline router.
SEMICONDUCTOR INTEGRATED CIRCUITS
Xiaofeng Zhou, Lu Liu, Zhangming Zhu and Duan Zhou
Corresponding author: Zhu Zhangming,zhangmingzhu@xidian.edu.cn
Abstract: The design of a router in a network-on-chip (NoC) system has an important impact on some performance criteria. In this paper, we propose a low overhead load balancing router (LOLBR) for 2D mesh NoC to enhance routing performance criteria with low hardware overhead. The proposed LOLBR employs a balance toggle identifier to control the initial routing direction of X or Y for flit injection. The simplified demultiplexers and multiplexers are used to handle output ports allocation and contention, which provide a guarantee of deadlock avoidance. Simulation results show that the proposed LOLBR yields an improvement of routing performance over the reported routing schemes in average packet latency by 26.5%. The layout area and power consumption of the network compared with the reported routing schemes are 15.3% and 11.6% less respectively.
Key words: NoC, low overhead, load balancing, router
| [1] |
Yang Yintang, Guan Xuguang, Zhou Duan, et al. A full asynchronous serial transmission converter for network-on-chips. Journal of Semiconductors, 2010, 31(4):045007 doi: 10.1088/1674-4926/31/4/045007
|
| [2] |
Zhou X, Liu L, Zhu Z, et al. A routing aggregation for load balancing network-on-chip. Journal of Circuits, Systems and Computers, 2015, 24(09):1550137 doi: 10.1142/S0218126615501376
|
| [3] |
Lee J, Nicopoulos C, Lee H G, et al. Sharded router:a novel onchip router architecture employing bandwidth sharding and stealing. Journal of Parallel Computing, 2013, 39(9):372 doi: 10.1016/j.parco.2013.04.004
|
| [4] |
Bahrebar P, Stroobandt D. The Hamiltonian-based odd-even turn model for maximally adaptive routing in 2D mesh networks-onchip. Journal of Computers & Electrical Engineering, 2015, 45:386
|
| [5] |
Chang E J, Chao C H, Jheng K Y, et al. ACO-based cascaded adaptive routing for traffic balancing in NoC systems. Proc Int Conf Green Circuits and Systems (ICGCS), 2010:317
|
| [6] |
Ma S, Wang Z, Jerger N E, et al. Novel flow control for fully adaptive routing in cache-coherent NoCs. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(9):2397 doi: 10.1109/TPDS.2013.166
|
| [7] |
Samman F A, Hollstein T, Glesner M. Runtime contention and bandwidth-aware adaptive routing selection strategies for networks-on-chip. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(7):1411 doi: 10.1109/TPDS.2012.200
|
| [8] |
Peh L S, Dally W J. A delay model and speculative architecture for pipelined routers. IEEE International Symposium on High Performance Computer Architecture, 2001:255
|
| [9] |
Ebrahimi M. Fully adaptive routing algorithms and regionbased approaches for two-dimensional and three-dimensional networks-on-chip. IET Computers & Digital Techniques, 2013, 7(6):264
|
| [10] |
Ramakrishna M, Gratz P V, Sprintson A. GCA:global congestion awareness for load balance in networks-on-chip. Proc 2013 IEEE Int Symp Networks on Chip (NoCs), 2013:1
|
| [11] |
Wang C, Hu W H, Bagherzadeh N. Scalable load balancing congestion-aware network-on-chip router architecture. Journal of Computer and System Sciences, 2013, 79(4):421 doi: 10.1016/j.jcss.2012.09.007
|
| [12] |
Ma S, Jerger N E, Wang Z, et al. Holistic routing algorithm design to support workload consolidation in NoCs. IEEE Trans Comput, 2014, 63(3):529 doi: 10.1109/TC.2012.201
|
| [13] |
Wang J, Gu H, Yang Y, et al. An energy-and buffer-aware fully adaptive routing algorithm for network-on-chip. Journal of Microelectronics, 2013, 44(2):137 doi: 10.1016/j.mejo.2012.12.008
|
| [14] |
Chen C H O, Agarwal N, Krishna T, et al. Physical vs. virtual express topologies with low-swing links for future many-core NoCs. Proceedings of the 2010 Fourth ACM/IEEE International Symposium on Networks-on-Chip, 2010:173
|
| [15] |
Peh L S, Dally W J. A delay model and speculative architecture for pipelined routers. Seventh IEEE International Symposium on High-Performance Computer Architecture(HPCA), 2001:255
|
| [16] |
Mullins R, West A, Moore S. Low-latency virtual-channel routers for on-chip networks. Proc ACM SIGARCH Computer Architecture News, 2004, 32(2):188 doi: 10.1145/1028176
|
| [17] |
Ni L M, McKinley P K. A survey of wormhole routing techniques in direct networks. Journal of Computer, 1993, 26(2):62 doi: 10.1109/2.191995
|
| [18] |
Tang M, Lin X, Palesi M. An offline method for designing adaptive routing based on pressure model. IEEE Trans Comput-Aided Des Integ Circuits Syst, 2015, 34(2):307 doi: 10.1109/TCAD.2014.2379649
|
| [19] |
Hu S, Xu W, Lin J, et al. Probabilistic odd-even:an adaptive wormhole routing algorithm for 2D mesh network-on-chip. Journal of Supercomputing, 2014, 70(1):385 doi: 10.1007/s11227-014-1250-6
|
| [20] |
Singh A, Dally W J, Gupta A K, and Towles B. GOAL:a loadbalanced adaptive routing algorithm for torus networks. ACM SIGARCH Computer Architecture News, 2003, 31(2):194-205 doi: 10.1145/871656
|
| [21] |
Chang E J, Hsin H K, Chao C H, et al. Regional ACO-based cascaded adaptive routing for traffic balancing in mesh-based network-on-chip systems. IEEE Trans Comput, 2015, 64(3):868 doi: 10.1109/TC.2013.2296032
|
| [22] |
nirgam.ecs.soton.ac.uk. NIRGAM:Networkon-Chip Simulator.[Online]. Available:http://nirgam.ecs.soton.ac.uk/Download.php
|
| [23] |
Shang L, Peh L S, Jha N K. PowerHerd:a distributed scheme for dynamically satisfying peak-power constraints in interconnection networks. IEEE Trans Comput-Aided Des Integ Circuits Syst, 2006, 25(1):92 doi: 10.1109/TCAD.2005.852438
|
Table 1. Simulation parameter.
|
Table 2. Layout area and power consumption.
|
| [1] |
Yang Yintang, Guan Xuguang, Zhou Duan, et al. A full asynchronous serial transmission converter for network-on-chips. Journal of Semiconductors, 2010, 31(4):045007 doi: 10.1088/1674-4926/31/4/045007
|
| [2] |
Zhou X, Liu L, Zhu Z, et al. A routing aggregation for load balancing network-on-chip. Journal of Circuits, Systems and Computers, 2015, 24(09):1550137 doi: 10.1142/S0218126615501376
|
| [3] |
Lee J, Nicopoulos C, Lee H G, et al. Sharded router:a novel onchip router architecture employing bandwidth sharding and stealing. Journal of Parallel Computing, 2013, 39(9):372 doi: 10.1016/j.parco.2013.04.004
|
| [4] |
Bahrebar P, Stroobandt D. The Hamiltonian-based odd-even turn model for maximally adaptive routing in 2D mesh networks-onchip. Journal of Computers & Electrical Engineering, 2015, 45:386
|
| [5] |
Chang E J, Chao C H, Jheng K Y, et al. ACO-based cascaded adaptive routing for traffic balancing in NoC systems. Proc Int Conf Green Circuits and Systems (ICGCS), 2010:317
|
| [6] |
Ma S, Wang Z, Jerger N E, et al. Novel flow control for fully adaptive routing in cache-coherent NoCs. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(9):2397 doi: 10.1109/TPDS.2013.166
|
| [7] |
Samman F A, Hollstein T, Glesner M. Runtime contention and bandwidth-aware adaptive routing selection strategies for networks-on-chip. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(7):1411 doi: 10.1109/TPDS.2012.200
|
| [8] |
Peh L S, Dally W J. A delay model and speculative architecture for pipelined routers. IEEE International Symposium on High Performance Computer Architecture, 2001:255
|
| [9] |
Ebrahimi M. Fully adaptive routing algorithms and regionbased approaches for two-dimensional and three-dimensional networks-on-chip. IET Computers & Digital Techniques, 2013, 7(6):264
|
| [10] |
Ramakrishna M, Gratz P V, Sprintson A. GCA:global congestion awareness for load balance in networks-on-chip. Proc 2013 IEEE Int Symp Networks on Chip (NoCs), 2013:1
|
| [11] |
Wang C, Hu W H, Bagherzadeh N. Scalable load balancing congestion-aware network-on-chip router architecture. Journal of Computer and System Sciences, 2013, 79(4):421 doi: 10.1016/j.jcss.2012.09.007
|
| [12] |
Ma S, Jerger N E, Wang Z, et al. Holistic routing algorithm design to support workload consolidation in NoCs. IEEE Trans Comput, 2014, 63(3):529 doi: 10.1109/TC.2012.201
|
| [13] |
Wang J, Gu H, Yang Y, et al. An energy-and buffer-aware fully adaptive routing algorithm for network-on-chip. Journal of Microelectronics, 2013, 44(2):137 doi: 10.1016/j.mejo.2012.12.008
|
| [14] |
Chen C H O, Agarwal N, Krishna T, et al. Physical vs. virtual express topologies with low-swing links for future many-core NoCs. Proceedings of the 2010 Fourth ACM/IEEE International Symposium on Networks-on-Chip, 2010:173
|
| [15] |
Peh L S, Dally W J. A delay model and speculative architecture for pipelined routers. Seventh IEEE International Symposium on High-Performance Computer Architecture(HPCA), 2001:255
|
| [16] |
Mullins R, West A, Moore S. Low-latency virtual-channel routers for on-chip networks. Proc ACM SIGARCH Computer Architecture News, 2004, 32(2):188 doi: 10.1145/1028176
|
| [17] |
Ni L M, McKinley P K. A survey of wormhole routing techniques in direct networks. Journal of Computer, 1993, 26(2):62 doi: 10.1109/2.191995
|
| [18] |
Tang M, Lin X, Palesi M. An offline method for designing adaptive routing based on pressure model. IEEE Trans Comput-Aided Des Integ Circuits Syst, 2015, 34(2):307 doi: 10.1109/TCAD.2014.2379649
|
| [19] |
Hu S, Xu W, Lin J, et al. Probabilistic odd-even:an adaptive wormhole routing algorithm for 2D mesh network-on-chip. Journal of Supercomputing, 2014, 70(1):385 doi: 10.1007/s11227-014-1250-6
|
| [20] |
Singh A, Dally W J, Gupta A K, and Towles B. GOAL:a loadbalanced adaptive routing algorithm for torus networks. ACM SIGARCH Computer Architecture News, 2003, 31(2):194-205 doi: 10.1145/871656
|
| [21] |
Chang E J, Hsin H K, Chao C H, et al. Regional ACO-based cascaded adaptive routing for traffic balancing in mesh-based network-on-chip systems. IEEE Trans Comput, 2015, 64(3):868 doi: 10.1109/TC.2013.2296032
|
| [22] |
nirgam.ecs.soton.ac.uk. NIRGAM:Networkon-Chip Simulator.[Online]. Available:http://nirgam.ecs.soton.ac.uk/Download.php
|
| [23] |
Shang L, Peh L S, Jha N K. PowerHerd:a distributed scheme for dynamically satisfying peak-power constraints in interconnection networks. IEEE Trans Comput-Aided Des Integ Circuits Syst, 2006, 25(1):92 doi: 10.1109/TCAD.2005.852438
|
Article views: 3131 Times PDF downloads: 22 Times Cited by: 0 Times
Received: 27 March 2016 Revised: 08 May 2016 Online: Published: 01 November 2016
| Citation: |
Xiaofeng Zhou, Lu Liu, Zhangming Zhu, Duan Zhou. A low overhead load balancing router for network-on-chip[J]. Journal of Semiconductors, 2016, 37(11): 115003. doi: 10.1088/1674-4926/37/11/115003
****
X F Zhou, L Liu, Z M Zhu, D Zhou. A low overhead load balancing router for network-on-chip[J]. J. Semicond., 2016, 37(11): 115003. doi: 10.1088/1674-4926/37/11/115003.
|
Project supported by the National Natural Science Foundation of China Nos. 61474087, 61322405, 61376039
Project supported by the National Natural Science Foundation of China (Nos. 61474087, 61322405, 61376039)
| [1] |
Yang Yintang, Guan Xuguang, Zhou Duan, et al. A full asynchronous serial transmission converter for network-on-chips. Journal of Semiconductors, 2010, 31(4):045007 doi: 10.1088/1674-4926/31/4/045007
|
| [2] |
Zhou X, Liu L, Zhu Z, et al. A routing aggregation for load balancing network-on-chip. Journal of Circuits, Systems and Computers, 2015, 24(09):1550137 doi: 10.1142/S0218126615501376
|
| [3] |
Lee J, Nicopoulos C, Lee H G, et al. Sharded router:a novel onchip router architecture employing bandwidth sharding and stealing. Journal of Parallel Computing, 2013, 39(9):372 doi: 10.1016/j.parco.2013.04.004
|
| [4] |
Bahrebar P, Stroobandt D. The Hamiltonian-based odd-even turn model for maximally adaptive routing in 2D mesh networks-onchip. Journal of Computers & Electrical Engineering, 2015, 45:386
|
| [5] |
Chang E J, Chao C H, Jheng K Y, et al. ACO-based cascaded adaptive routing for traffic balancing in NoC systems. Proc Int Conf Green Circuits and Systems (ICGCS), 2010:317
|
| [6] |
Ma S, Wang Z, Jerger N E, et al. Novel flow control for fully adaptive routing in cache-coherent NoCs. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(9):2397 doi: 10.1109/TPDS.2013.166
|
| [7] |
Samman F A, Hollstein T, Glesner M. Runtime contention and bandwidth-aware adaptive routing selection strategies for networks-on-chip. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(7):1411 doi: 10.1109/TPDS.2012.200
|
| [8] |
Peh L S, Dally W J. A delay model and speculative architecture for pipelined routers. IEEE International Symposium on High Performance Computer Architecture, 2001:255
|
| [9] |
Ebrahimi M. Fully adaptive routing algorithms and regionbased approaches for two-dimensional and three-dimensional networks-on-chip. IET Computers & Digital Techniques, 2013, 7(6):264
|
| [10] |
Ramakrishna M, Gratz P V, Sprintson A. GCA:global congestion awareness for load balance in networks-on-chip. Proc 2013 IEEE Int Symp Networks on Chip (NoCs), 2013:1
|
| [11] |
Wang C, Hu W H, Bagherzadeh N. Scalable load balancing congestion-aware network-on-chip router architecture. Journal of Computer and System Sciences, 2013, 79(4):421 doi: 10.1016/j.jcss.2012.09.007
|
| [12] |
Ma S, Jerger N E, Wang Z, et al. Holistic routing algorithm design to support workload consolidation in NoCs. IEEE Trans Comput, 2014, 63(3):529 doi: 10.1109/TC.2012.201
|
| [13] |
Wang J, Gu H, Yang Y, et al. An energy-and buffer-aware fully adaptive routing algorithm for network-on-chip. Journal of Microelectronics, 2013, 44(2):137 doi: 10.1016/j.mejo.2012.12.008
|
| [14] |
Chen C H O, Agarwal N, Krishna T, et al. Physical vs. virtual express topologies with low-swing links for future many-core NoCs. Proceedings of the 2010 Fourth ACM/IEEE International Symposium on Networks-on-Chip, 2010:173
|
| [15] |
Peh L S, Dally W J. A delay model and speculative architecture for pipelined routers. Seventh IEEE International Symposium on High-Performance Computer Architecture(HPCA), 2001:255
|
| [16] |
Mullins R, West A, Moore S. Low-latency virtual-channel routers for on-chip networks. Proc ACM SIGARCH Computer Architecture News, 2004, 32(2):188 doi: 10.1145/1028176
|
| [17] |
Ni L M, McKinley P K. A survey of wormhole routing techniques in direct networks. Journal of Computer, 1993, 26(2):62 doi: 10.1109/2.191995
|
| [18] |
Tang M, Lin X, Palesi M. An offline method for designing adaptive routing based on pressure model. IEEE Trans Comput-Aided Des Integ Circuits Syst, 2015, 34(2):307 doi: 10.1109/TCAD.2014.2379649
|
| [19] |
Hu S, Xu W, Lin J, et al. Probabilistic odd-even:an adaptive wormhole routing algorithm for 2D mesh network-on-chip. Journal of Supercomputing, 2014, 70(1):385 doi: 10.1007/s11227-014-1250-6
|
| [20] |
Singh A, Dally W J, Gupta A K, and Towles B. GOAL:a loadbalanced adaptive routing algorithm for torus networks. ACM SIGARCH Computer Architecture News, 2003, 31(2):194-205 doi: 10.1145/871656
|
| [21] |
Chang E J, Hsin H K, Chao C H, et al. Regional ACO-based cascaded adaptive routing for traffic balancing in mesh-based network-on-chip systems. IEEE Trans Comput, 2015, 64(3):868 doi: 10.1109/TC.2013.2296032
|
| [22] |
nirgam.ecs.soton.ac.uk. NIRGAM:Networkon-Chip Simulator.[Online]. Available:http://nirgam.ecs.soton.ac.uk/Download.php
|
| [23] |
Shang L, Peh L S, Jha N K. PowerHerd:a distributed scheme for dynamically satisfying peak-power constraints in interconnection networks. IEEE Trans Comput-Aided Des Integ Circuits Syst, 2006, 25(1):92 doi: 10.1109/TCAD.2005.852438
|
WeChat ID
Journal of Semiconductors © 2017 All Rights Reserved 京ICP備05085259號-2
DownLoad:
