SEMICONDUCTOR INTEGRATED CIRCUITS

A low overhead load balancing router for network-on-chip

Xiaofeng Zhou, Lu Liu, Zhangming Zhu and Duan Zhou

+ Author Affiliations

 Corresponding author: Zhu Zhangming,zhangmingzhu@xidian.edu.cn

PDF

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: NoClow overheadload balancingrouter



[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
Fig. 1.  Architecture for baseline router.

Fig. 2.  Routing paths for three schemes.

Fig. 3.  Architecture for LOLBR.

Fig. 4.  Packet injection of LOLBR.

Fig. 5.  Priority policy of heavier-first for LOLBR.

Fig. 6.  (Color online) Average packet latency in 4 × 4 mesh. (a) Uniform pattern. (b) Transpose pattern. (c) Bit-reversal pattern. (d) Bit-complement pattern.

Fig. 7.  (Color online) Average packet latency in 8 × 8 mesh. (a) Uniform pattern. (b) Transpose pattern. (c) Bit-reversal pattern. (d) Bit-complement pattern.

Fig. 8.  (Color online) Saturation throughput in two networks. (a) Saturation throughput in 4 × 4 mesh. (b) Saturation throughput in 8 × 8 mesh.

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
  • Search

    Advanced Search >>

    GET CITATION

    shu

    Export: BibTex EndNote

    Article Metrics

    Article views: 2655 Times PDF downloads: 18 Times Cited by: 0 Times

    History

    Received: 27 March 2016 Revised: 08 May 2016 Online: Published: 01 November 2016

    Catalog

      Email This Article

      User name:
      Email:*请输入正确邮箱
      Code:*验证码错误
      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.Export: BibTex EndNote
      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.
      Export: BibTex EndNote

      A low overhead load balancing router for network-on-chip

      doi: 10.1088/1674-4926/37/11/115003
      Funds:

      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)

      More Information
      • Corresponding author: Zhu Zhangming,zhangmingzhu@xidian.edu.cn
      • Received Date: 2016-03-27
      • Revised Date: 2016-05-08
      • Published Date: 2016-11-01

      Catalog

        /

        DownLoad:  Full-Size Img  PowerPoint
        Return
        Return