Skip to main content
Top
Published in: The Journal of Supercomputing 2/2014

01-05-2014

A novel distributed congestion control for bufferless network-on-chip

Authors: Jili Yan, Guoming Lai, Xiaola Lin

Published in: The Journal of Supercomputing | Issue 2/2014

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Bufferless Network-on-Chip (NoC) emerges as an interesting option for NoC design in recent years, which can save considerable router power and area. However, bufferless NoC only works well under low-to-medium load because it becomes more easily congested as message injection rate increases. In this paper, we propose a novel distributed source-throttling congestion control mechanism that relieves the effect of congestion in bufferless NoC under high load, called Cbufferless. The proposed strategy uses a novel congestion detection and control mechanism, computing average deflection rate of routing flit and distributed throttling message injection. Utilizing the new mechanism, the congestion information can be directly obtained inside node, which allows the mechanism to be fully distributed without requiring any transmission of global congestion information among neighbor routers and within a router. Simulation results show that the proposed mechanism improves system throughput by up to \(\sim \)30 and \(\sim \)15.5 %, saves energy consumption by up to \(\sim \)40 and \(\sim \)19 % than that of baseline and injection rate throttling bufferless NoCs, respectively, and keeps lower message latency under congested load when compared.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Footnotes
1
pri \(_{i}\) is the priority of packet \(i\).
 
Literature
1.
go back to reference Dally WJ, Towles B (2001) Route packets, not wires: on-chip interconnection networks. In: Proceedings of design automation conference, pp 684–689 Dally WJ, Towles B (2001) Route packets, not wires: on-chip interconnection networks. In: Proceedings of design automation conference, pp 684–689
2.
go back to reference Ho R, Mai KW, Horowitz MA (2001) The future of wires. Proc IEEE 89(4):490–504CrossRef Ho R, Mai KW, Horowitz MA (2001) The future of wires. Proc IEEE 89(4):490–504CrossRef
3.
go back to reference Kim J, Balfour J, Dally WJ (2007) Flattened butterfly topology for on-chip networks. In: Proceedings of the 40th annual IEEE/ACM international symposium on microarchitecture, pp 172–182 Kim J, Balfour J, Dally WJ (2007) Flattened butterfly topology for on-chip networks. In: Proceedings of the 40th annual IEEE/ACM international symposium on microarchitecture, pp 172–182
4.
go back to reference Kao YH, Alfaraj N, Yang M et al (2010) Design of high-radix clos network-on-chip. In: 2010 fourth ACM/IEEE international symposium on networks-on-chip, pp 181–188 Kao YH, Alfaraj N, Yang M et al (2010) Design of high-radix clos network-on-chip. In: 2010 fourth ACM/IEEE international symposium on networks-on-chip, pp 181–188
5.
go back to reference Jing L, Xiaola L (2012) Power and latency efficient mechanism: a seamless bridge between buffered and bufferless routing in on-chip network. J Supercomput 61(3):1048–1067CrossRef Jing L, Xiaola L (2012) Power and latency efficient mechanism: a seamless bridge between buffered and bufferless routing in on-chip network. J Supercomput 61(3):1048–1067CrossRef
6.
go back to reference Hoskote Y, Vangal S, Singh A et al (2007) A 5-ghz mesh interconnect for a teraflops processor. IEEE J MICRO 27(5):51–61CrossRef Hoskote Y, Vangal S, Singh A et al (2007) A 5-ghz mesh interconnect for a teraflops processor. IEEE J MICRO 27(5):51–61CrossRef
7.
go back to reference Taylor MB, Lee W, Miller J et al (2004) Evaluation of the raw microprocessor: an exposed-wire-delay architecture for ILP and atreams. In: Proceedings of international symposium on computer architecture, pp 2–13 Taylor MB, Lee W, Miller J et al (2004) Evaluation of the raw microprocessor: an exposed-wire-delay architecture for ILP and atreams. In: Proceedings of international symposium on computer architecture, pp 2–13
8.
go back to reference Gratz P, Kim C, McDonald R et al (2006) Implementation and evaluation of on-chip network architectures. In: International conference on computer design, pp 477–484 Gratz P, Kim C, McDonald R et al (2006) Implementation and evaluation of on-chip network architectures. In: International conference on computer design, pp 477–484
9.
go back to reference Vangal SR, Howard J et al (2008) An 80-tile sub-100-w teraflops processor in 65-nm CMOS. IEEE J Solid State Circuits 43:29–41CrossRef Vangal SR, Howard J et al (2008) An 80-tile sub-100-w teraflops processor in 65-nm CMOS. IEEE J Solid State Circuits 43:29–41CrossRef
10.
go back to reference Moscibroda T, Mutlu O (2009) A case for bufferless routing in on-chip networks. In: Proceedings of international symposium on computer architecture, pp 196–207 Moscibroda T, Mutlu O (2009) A case for bufferless routing in on-chip networks. In: Proceedings of international symposium on computer architecture, pp 196–207
11.
go back to reference Fallin C, Craik C, Mutlu O (2011) Chipper: a low-complexity bufferless deflection router. In: Proceedings of international symposium on high performance computer architecture, pp 144–155 Fallin C, Craik C, Mutlu O (2011) Chipper: a low-complexity bufferless deflection router. In: Proceedings of international symposium on high performance computer architecture, pp 144–155
12.
go back to reference Baran P (1964) On distributed communications networks. IEEE J Commun Syst 12(1):1–9CrossRef Baran P (1964) On distributed communications networks. IEEE J Commun Syst 12(1):1–9CrossRef
13.
go back to reference Nychis GP, Fallin C, Moscibroda T et al (2012) On-chip networks from a networking perspective: congestion and scalability in many-core interconnects. ACM SIGCOMM Comput Commun Rev 42(4):407–418CrossRef Nychis GP, Fallin C, Moscibroda T et al (2012) On-chip networks from a networking perspective: congestion and scalability in many-core interconnects. ACM SIGCOMM Comput Commun Rev 42(4):407–418CrossRef
14.
go back to reference Hennessy JL, Patterson DA (2012) Computer architecture: a quantitative approach. Elsevier, Amsterdam Hennessy JL, Patterson DA (2012) Computer architecture: a quantitative approach. Elsevier, Amsterdam
15.
go back to reference Yan J, Lin X, Lai G (2013) Cbufferless: a novel congestion control for bufferless networks on-chip. In: 2nd international conference on advances in computer science and engineering, pp 153–156 Yan J, Lin X, Lai G (2013) Cbufferless: a novel congestion control for bufferless networks on-chip. In: 2nd international conference on advances in computer science and engineering, pp 153–156
16.
go back to reference Guan Y, Adi CAD, Miyoshi T et al (2012) Throttling control for bufferless routing in on-chip networks. In: IEEE 6th international symposium on embedded multicore SoCs (MCSoC), 2012 IEEE, pp 37–44 Guan Y, Adi CAD, Miyoshi T et al (2012) Throttling control for bufferless routing in on-chip networks. In: IEEE 6th international symposium on embedded multicore SoCs (MCSoC), 2012 IEEE, pp 37–44
17.
go back to reference Hu W-H, Lee SE, Bagherzadeh N (2008) DMesh: a diagonally-linked mesh network-on-chip architecture. In: First international workshop on network on chip architectures workshop Hu W-H, Lee SE, Bagherzadeh N (2008) DMesh: a diagonally-linked mesh network-on-chip architecture. In: First international workshop on network on chip architectures workshop
19.
go back to reference Ye TT, Benini L, De Micheli G (2002) Analysis of power consumption on switch fabrics in network routers. In: Design automation conference proceedings, pp 524–529 Ye TT, Benini L, De Micheli G (2002) Analysis of power consumption on switch fabrics in network routers. In: Design automation conference proceedings, pp 524–529
20.
go back to reference Feng W, Shin KG (1997) Impact of selection functions on routing algorithm performance in multicomputer networks. In: Proceedings of the 11th international conference on supercomputing, pp 132–139 Feng W, Shin KG (1997) Impact of selection functions on routing algorithm performance in multicomputer networks. In: Proceedings of the 11th international conference on supercomputing, pp 132–139
21.
go back to reference Ogras UY, Marculescu R (2006) Prediction-based flow control for network on-chip traffic. In: Proceedings of the 43rd annual design automation conference, pp 839–844 Ogras UY, Marculescu R (2006) Prediction-based flow control for network on-chip traffic. In: Proceedings of the 43rd annual design automation conference, pp 839–844
22.
go back to reference Jiang N, Becker DU, Miche logiannakis G, Dally WJ (2012) Network congestion avoidance through speculative reservation. In: Proceedings of international symposium on high performance computer architecture, pp 1–12 Jiang N, Becker DU, Miche logiannakis G, Dally WJ (2012) Network congestion avoidance through speculative reservation. In: Proceedings of international symposium on high performance computer architecture, pp 1–12
23.
go back to reference Gratz P, Grot B, Keckler SW (2008) Regional congestion awareness for load balance in networks-on-chip. In: Proceedings of international symposium on high performance computer architecture, pp 203–214 Gratz P, Grot B, Keckler SW (2008) Regional congestion awareness for load balance in networks-on-chip. In: Proceedings of international symposium on high performance computer architecture, pp 203–214
24.
go back to reference Hu J, Marculescu R (2004) Dyad: smart routing for networks-on-chip. In: Proceedings of the 41st annual design automation conference, pp 260–263 Hu J, Marculescu R (2004) Dyad: smart routing for networks-on-chip. In: Proceedings of the 41st annual design automation conference, pp 260–263
25.
go back to reference Baydal E, Lopez P, Duato J (2005) A family of mechanisms for congestion control in wormhole networks. IEEE J Parallel Distrib Syst 16(9):772–784CrossRef Baydal E, Lopez P, Duato J (2005) A family of mechanisms for congestion control in wormhole networks. IEEE J Parallel Distrib Syst 16(9):772–784CrossRef
26.
go back to reference van den Brand JW, Ciordas C, Goossens K, Basten T (2007) Congestion-controlled best-effort communication for networks-on-chip. In: design, automation and test in Europe conference and exhibition, pp 1–6 van den Brand JW, Ciordas C, Goossens K, Basten T (2007) Congestion-controlled best-effort communication for networks-on-chip. In: design, automation and test in Europe conference and exhibition, pp 1–6
27.
go back to reference Thottethodi M, Lebeck AR, Mukherjee SS (2001) Self-tuned congestion control for multiprocessor networks. In: Proceedings of international symposium on high performance computer architecture, pp 107–118 Thottethodi M, Lebeck AR, Mukherjee SS (2001) Self-tuned congestion control for multiprocessor networks. In: Proceedings of international symposium on high performance computer architecture, pp 107–118
28.
go back to reference Tedesco LP, Rosa T, Clermidy F, Calazans N et al (2010) Implementation and evaluation of a congestion aware routing algorithm for networks-on-chip. In: Proceedings of the 23rd symposium on integrated circuits and system design, pp 91–96 Tedesco LP, Rosa T, Clermidy F, Calazans N et al (2010) Implementation and evaluation of a congestion aware routing algorithm for networks-on-chip. In: Proceedings of the 23rd symposium on integrated circuits and system design, pp 91–96
29.
go back to reference Nilsson E, Millberg M, Oberg J, Jantsch A (2003) Load distribution with the proximity congestion awareness in a network on chip. In: Design, automation and test in Europe conference and exhibition, pp 1126–1127 Nilsson E, Millberg M, Oberg J, Jantsch A (2003) Load distribution with the proximity congestion awareness in a network on chip. In: Design, automation and test in Europe conference and exhibition, pp 1126–1127
30.
go back to reference Johnson KL (1992) The impact of communication locality on large-scale multiprocessor performance. In: Proceedings of international symposium on computer architecture, pp 392–402 Johnson KL (1992) The impact of communication locality on large-scale multiprocessor performance. In: Proceedings of international symposium on computer architecture, pp 392–402
Metadata
Title
A novel distributed congestion control for bufferless network-on-chip
Authors
Jili Yan
Guoming Lai
Xiaola Lin
Publication date
01-05-2014
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 2/2014
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-013-1069-6

Other articles of this Issue 2/2014

The Journal of Supercomputing 2/2014 Go to the issue

Premium Partner