SEMICONDUCTOR INTEGRATED CIRCUITS

A congestion-aware OE router employing fair arbitration for network-on-chip

Lu Liu, Yadong Sun, Zhangming Zhu and Yintang Yang

+ Author Affiliations

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

PDF

Turn off MathJax

Abstract: To meet the demand for high on-chip network performance, flexible routing algorithms supplying path diversity and congestion alleviation are required. We propose a CAOE-FA router as a combination of congestion-awareness and fair arbitration. Buffer occupancies from downstream neighbors are collected to indicate the congestion levels, among the candidate outputs permitted by the odd-even (OE) turn model, the lightest loaded direction is selected; fair arbitration is employed for the condition of the same congestion level to replace random selection. Experimental results show that the CAOE-FA can reduce the average packet latency by up to 22.18% and improve the network throughput by up to 68.58%, with ignorable price of hardware cost.

Key words: network-on-chipodd-even turn modelcongestion-aware routerfair arbitration



[1]
Zhu J, Qian Z, Tsui C Y. Bilink: A high performance NoC router architecture using bi-directional link with double data rate. Integration, the VLSI Journal, 2016(55): 30
[2]
Wachter E, Caunu L L, Fochi V, et al. BrNoC: A broadcast NoC for control messages in many-core systems. Microelectron J, 2017(68): 69
[3]
Liu J, Harkin J, Li Y, et al. Fault-tolerant network-on-chip routing with coarse and fine-grained look-ahead. IEEE Trans Comput-Aided Des Integr Circuit Syst, 2016, 35(2): 260 doi: 10.1109/TCAD.2015.2459050
[4]
Vassos S, Theocharis T, Kakoulli E. A holistic approach towards intelligent hotspot prevention in network-on-chip-based multicores. IEEE Trans Comput, 2016, 65(3): 819 doi: 10.1109/TC.2015.2435748
[5]
Zhou X, Liu L, Zhu Z, et al. A routing aggregation for load balancing network-on-chip. J Circuits, Syst Comput, 2015, 24(9): 1550137 doi: 10.1142/S0218126615501376
[6]
Bahrebar P, Stroobandt D. The Hamiltonian-based odd–even turn model for maximally adaptive routing in 2D mesh networks-on-chip. Comput Electron Eng, 2015, 45(7): 386
[7]
Y, Jili. Enhanced global congestion awareness(EGCA) for load balance in networks-on-chip. J Supercomput, 2016, 72(2): 567 doi: 10.1007/s11227-015-1583-9
[8]
Yin C Y, Jui C E, Kai H H, et al. Path-diversity-aware fault-tolerant routing algorithm for network-on-chip systems. IEEE Transn Parall Distrib Syst, 2017, 28(3): 838 doi: 10.1109/TPDS.2016.2588482
[9]
Tang M, Lin X, Palesi M. An offline method for designing adaptive routing based on pressure model. IEEE Trans Comput-Aided Des Integr Circuit Syst, 2015, 34(2): 307 doi: 10.1109/TCAD.2014.2379649
[10]
Wang C, Hu W H, Bagherzadeh N. Scalable load balancing congestion-aware network-on-chip router architecture. J Comput Syst Sci, 2013, 79(4): 421 doi: 10.1016/j.jcss.2012.09.007
[11]
Liu S, Chen T, Li L. FreeRider: non-local adaptive network-on-chip routing with packet-carried propagation of congestion information. IEEE Trans Parall Distribd Syst, 2015, 26(8): 2272 doi: 10.1109/TPDS.2014.2345065
[12]
Ramakrishna M, Kodati V K, Gratz P V, et al. GCA: global congestion awareness for load balance in network-on-chip. IEEE Trans Parall Distrib Syst, 2016, 27(7): 2022 doi: 10.1109/TPDS.2015.2477840
[13]
Eldin R E, Moursy M E, Hamed H. process variation delay and congestion aware routing algorithm for asynchronous NoC design. IEEE Trans Very Large Scale Integr (VLSI) Syst, 2016, 24(3): 909 doi: 10.1109/TVLSI.2015.2434853
[14]
Chang E J, Hsin H K, Lin S Y, et al. Path-congestion-aware adaptive routing with a contention prediction scheme for network-on-chip systems. IEEE Trans Comput-Aided Des Integr Circuits Syst, 2014, 22(1): 113
[15]
Liu L, Zhu Z, Zhou D, et al. A fair arbitration for network-on-chip routing with odd-even turn model. Microelectron J, 2017(64): 1
[16]
Verbeek F, Schmaltz J. A decision procedure for deadlock-free routing in wormhole networks. IEEE Trans Parall Distrib Syst, 2014, 25(8): 1935 doi: 10.1109/TPDS.2013.121
[17]
Zhou X, Liu L, Zhu Z, et al. A low overhead load balancing router for network-on-chip. J Semicond, 2016, 37(11): 115003 doi: 10.1088/1674-4926/37/11/115003
[18]
Ma S, Wang Z, Jerger N, et al. Novel flow control for fully adaptive routing in cache-coherent NoCs. IEEE Trans Parall Distrib Syst, 2014, 25(9): 2397 doi: 10.1109/TPDS.2013.166
[19]
Bashizade R, Sarbazi Azad H. P2R2: parallel pseudo-round-robin arbiter for high performance NoCs. Integration, the VLSI Journal, 2015(50): 173
[20]
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
[21]
Catania V, Mineo A, Monteleone S, et al. Cycle-accurate network on chip simulation with Noxim. ACM Trans Model Comput Simul, 2016, 27(1): 4
[22]
Kim G, Lee M M J, Kim J, et al. Low-overhead network-on-chip support for location-oblivious task placement. IEEE Trans Computers, 2014, 63(6): 1487 doi: 10.1109/TC.2012.241
Fig. 1.  (Color online) CAOE-FA router architecture.

Fig. 2.  The flowchart of CAOE-FA.

Fig. 3.  (Color online) Average packet latency without hotspot. (a) Random. (b) Transpose1. (c) Transpose2. (d) Bit reversal.

Fig. 4.  (Color online) Saturation throughput without hotspot.

Fig. 5.  (Color online) Average packet latency with hotspot. (a) Random-hotspot. (b) Transpose1-hotspot. (c) Transpose2-hotspot. (d) Bit reversal-hotspot.

Fig. 6.  (Color online) Saturation throughput with hotspot.

Table 1.   Configuration parameters for simulation.

Parameter Value
Network size and topology 4 × 4 mesh
Routing algorithms OE, CAOE-random, CAOE-FA
Flit width 32 bits
Packet size 3 flits
Buffer sizeTraffic pattern 9 flitsrandom, bit reversal, transpose 1, transpose 2, hotspot
DownLoad: CSV

Table 2.   Implementation overhead.

Routing algorithm OE CAOE-FA Increasing percentage
Power consumption 0.2959 mW 0.2996 mW 1.25%
Area cost 587.473 μm2 686.868 μm2 17.92%
DownLoad: CSV
[1]
Zhu J, Qian Z, Tsui C Y. Bilink: A high performance NoC router architecture using bi-directional link with double data rate. Integration, the VLSI Journal, 2016(55): 30
[2]
Wachter E, Caunu L L, Fochi V, et al. BrNoC: A broadcast NoC for control messages in many-core systems. Microelectron J, 2017(68): 69
[3]
Liu J, Harkin J, Li Y, et al. Fault-tolerant network-on-chip routing with coarse and fine-grained look-ahead. IEEE Trans Comput-Aided Des Integr Circuit Syst, 2016, 35(2): 260 doi: 10.1109/TCAD.2015.2459050
[4]
Vassos S, Theocharis T, Kakoulli E. A holistic approach towards intelligent hotspot prevention in network-on-chip-based multicores. IEEE Trans Comput, 2016, 65(3): 819 doi: 10.1109/TC.2015.2435748
[5]
Zhou X, Liu L, Zhu Z, et al. A routing aggregation for load balancing network-on-chip. J Circuits, Syst Comput, 2015, 24(9): 1550137 doi: 10.1142/S0218126615501376
[6]
Bahrebar P, Stroobandt D. The Hamiltonian-based odd–even turn model for maximally adaptive routing in 2D mesh networks-on-chip. Comput Electron Eng, 2015, 45(7): 386
[7]
Y, Jili. Enhanced global congestion awareness(EGCA) for load balance in networks-on-chip. J Supercomput, 2016, 72(2): 567 doi: 10.1007/s11227-015-1583-9
[8]
Yin C Y, Jui C E, Kai H H, et al. Path-diversity-aware fault-tolerant routing algorithm for network-on-chip systems. IEEE Transn Parall Distrib Syst, 2017, 28(3): 838 doi: 10.1109/TPDS.2016.2588482
[9]
Tang M, Lin X, Palesi M. An offline method for designing adaptive routing based on pressure model. IEEE Trans Comput-Aided Des Integr Circuit Syst, 2015, 34(2): 307 doi: 10.1109/TCAD.2014.2379649
[10]
Wang C, Hu W H, Bagherzadeh N. Scalable load balancing congestion-aware network-on-chip router architecture. J Comput Syst Sci, 2013, 79(4): 421 doi: 10.1016/j.jcss.2012.09.007
[11]
Liu S, Chen T, Li L. FreeRider: non-local adaptive network-on-chip routing with packet-carried propagation of congestion information. IEEE Trans Parall Distribd Syst, 2015, 26(8): 2272 doi: 10.1109/TPDS.2014.2345065
[12]
Ramakrishna M, Kodati V K, Gratz P V, et al. GCA: global congestion awareness for load balance in network-on-chip. IEEE Trans Parall Distrib Syst, 2016, 27(7): 2022 doi: 10.1109/TPDS.2015.2477840
[13]
Eldin R E, Moursy M E, Hamed H. process variation delay and congestion aware routing algorithm for asynchronous NoC design. IEEE Trans Very Large Scale Integr (VLSI) Syst, 2016, 24(3): 909 doi: 10.1109/TVLSI.2015.2434853
[14]
Chang E J, Hsin H K, Lin S Y, et al. Path-congestion-aware adaptive routing with a contention prediction scheme for network-on-chip systems. IEEE Trans Comput-Aided Des Integr Circuits Syst, 2014, 22(1): 113
[15]
Liu L, Zhu Z, Zhou D, et al. A fair arbitration for network-on-chip routing with odd-even turn model. Microelectron J, 2017(64): 1
[16]
Verbeek F, Schmaltz J. A decision procedure for deadlock-free routing in wormhole networks. IEEE Trans Parall Distrib Syst, 2014, 25(8): 1935 doi: 10.1109/TPDS.2013.121
[17]
Zhou X, Liu L, Zhu Z, et al. A low overhead load balancing router for network-on-chip. J Semicond, 2016, 37(11): 115003 doi: 10.1088/1674-4926/37/11/115003
[18]
Ma S, Wang Z, Jerger N, et al. Novel flow control for fully adaptive routing in cache-coherent NoCs. IEEE Trans Parall Distrib Syst, 2014, 25(9): 2397 doi: 10.1109/TPDS.2013.166
[19]
Bashizade R, Sarbazi Azad H. P2R2: parallel pseudo-round-robin arbiter for high performance NoCs. Integration, the VLSI Journal, 2015(50): 173
[20]
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
[21]
Catania V, Mineo A, Monteleone S, et al. Cycle-accurate network on chip simulation with Noxim. ACM Trans Model Comput Simul, 2016, 27(1): 4
[22]
Kim G, Lee M M J, Kim J, et al. Low-overhead network-on-chip support for location-oblivious task placement. IEEE Trans Computers, 2014, 63(6): 1487 doi: 10.1109/TC.2012.241
  • Search

    Advanced Search >>

    GET CITATION

    shu

    Export: BibTex EndNote

    Article Metrics

    Article views: 3044 Times PDF downloads: 21 Times Cited by: 0 Times

    History

    Received: 04 May 2018 Revised: 09 July 2018 Online: Uncorrected proof: 09 October 2018Published: 13 December 2018

    Catalog

      Email This Article

      User name:
      Email:*请输入正确邮箱
      Code:*验证码错误
      Lu Liu, Yadong Sun, Zhangming Zhu, Yintang Yang. A congestion-aware OE router employing fair arbitration for network-on-chip[J]. Journal of Semiconductors, 2018, 39(12): 125006. doi: 10.1088/1674-4926/39/12/125006 L Liu, Y D Sun, Z M Zhu, Y T Yang, A congestion-aware OE router employing fair arbitration for network-on-chip[J]. J. Semicond., 2018, 39(12): 125006. doi: 10.1088/1674-4926/39/12/125006.Export: BibTex EndNote
      Citation:
      Lu Liu, Yadong Sun, Zhangming Zhu, Yintang Yang. A congestion-aware OE router employing fair arbitration for network-on-chip[J]. Journal of Semiconductors, 2018, 39(12): 125006. doi: 10.1088/1674-4926/39/12/125006

      L Liu, Y D Sun, Z M Zhu, Y T Yang, A congestion-aware OE router employing fair arbitration for network-on-chip[J]. J. Semicond., 2018, 39(12): 125006. doi: 10.1088/1674-4926/39/12/125006.
      Export: BibTex EndNote

      A congestion-aware OE router employing fair arbitration for network-on-chip

      doi: 10.1088/1674-4926/39/12/125006
      Funds:

      Project supported by the National Natural Science Foundation of China (No. 61625403).

      More Information
      • Corresponding author: Email: zhangmingzhu@xidian.edu.cn
      • Received Date: 2018-05-04
      • Revised Date: 2018-07-09
      • Published Date: 2018-12-01

      Catalog

        /

        DownLoad:  Full-Size Img  PowerPoint
        Return
        Return