Skip to main content
Top
Published in: The Journal of Supercomputing 10/2019

06-06-2019

S2DIO: an extended scalable 2D mesh network-on-chip routing reconfiguration for efficient bypass of link failures

Authors: Anugrah Jain, Vijay Laxmi, Meenakshi Tripathi, Manoj Singh Gaur, Rimpy Bishnoi

Published in: The Journal of Supercomputing | Issue 10/2019

Log in

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

search-config
loading …

Abstract

The paradigm of computing has shifted from computation-centric to communication-centric designs. Network-on-chip has emerged as an alternative interconnect mechanism for future multi-core designs. Transistor integration is approaching its limit, and this increases the susceptibility of the interconnects toward failures. Research efforts are directed toward improving the fault tolerance of these interconnects. Fault-tolerant routing such as segment-based and up*/down* are static by nature and require reconfiguration to circumvent failures. Failures may disrupt the connectivity of the network, and new routing instance needs to be configured in case old routing instance is unable to offer full connectivity. In this paper, we identify nodes affected by the failures and propose an extended scalable routing reconfiguration, called S2DIO. It performs reconfiguration of affected nodes by taking \(N^2\) cycles for \(N \times N\) mesh network, whereas state-of-the-art (ARIADNE) consumes \(N^4\) cycles. Instead of routing tables, we employ logic-based routing and achieve significant improvements, i.e., \(30.7\%\) in terms of area and \(29\%\) in terms of power overhead for a \(16\times 16\) mesh router. A novel algorithm for computation of new logic-based routing bits is also proposed in this paper. Our reconfiguration (S2DIO) improves average flit latency up to \(32\%\) and throughput up to 19% for single-link failure in \(8\times 8\) 2D mesh network-on-chip.

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
Any failure resulting in partitioning of interconnect network shall result in disruption of routing functions.
 
2
We assume a detection algorithm such as [30, 31] is working in the background. Detection is not part of the proposed work.
 
Literature
1.
go back to reference Dally W, Towles B (2003) Principles and practices of interconnection networks. Morgan Kaufmann, San Francisco Dally W, Towles B (2003) Principles and practices of interconnection networks. Morgan Kaufmann, San Francisco
2.
go back to reference Aisopos K (2012) Fault tolerant architectures for on-chip networks, Ph.D. dissertation. Princeton University, Princeton Aisopos K (2012) Fault tolerant architectures for on-chip networks, Ph.D. dissertation. Princeton University, Princeton
3.
go back to reference Mejia A, Flich J, Duato J, Reinemo S-A, Skeie T (2006) Segment-based routing: an efficient fault-tolerant routing algorithm for meshes and tori. In: Proceedings of the 20th International Conference on Parallel and Distributed Processing, IPDPS’06. IEEE Computer Society, Washington, pp 105–105 Mejia A, Flich J, Duato J, Reinemo S-A, Skeie T (2006) Segment-based routing: an efficient fault-tolerant routing algorithm for meshes and tori. In: Proceedings of the 20th International Conference on Parallel and Distributed Processing, IPDPS’06. IEEE Computer Society, Washington, pp 105–105
4.
go back to reference Schroeder MD, Birrell AD, Burrows M, Murray H, Needham RM, Rodeheffer TL, Satterthwaite EH, Thacker CP (2006) Autonet: a high-speed, self-configuring local area network using point-to-point links. IEEE J Sel A Commun 9(8):1318–1335CrossRef Schroeder MD, Birrell AD, Burrows M, Murray H, Needham RM, Rodeheffer TL, Satterthwaite EH, Thacker CP (2006) Autonet: a high-speed, self-configuring local area network using point-to-point links. IEEE J Sel A Commun 9(8):1318–1335CrossRef
5.
go back to reference Pinkston TM, Pang R, Duato J (2003) Deadlock-free dynamic reconfiguration schemes for increased network dependability. IEEE Trans Parallel Distrib Syst 14(8):780–794CrossRef Pinkston TM, Pang R, Duato J (2003) Deadlock-free dynamic reconfiguration schemes for increased network dependability. IEEE Trans Parallel Distrib Syst 14(8):780–794CrossRef
6.
go back to reference Puente V, Gregorio JA, Vallejo F, Beivide R (2004) Immunet: a cheap and robust fault-tolerant packet routing mechanism. In: Proceedings of the 31st Annual International Symposium on Computer Architecture, June 2004, pp 198–209 Puente V, Gregorio JA, Vallejo F, Beivide R (2004) Immunet: a cheap and robust fault-tolerant packet routing mechanism. In: Proceedings of the 31st Annual International Symposium on Computer Architecture, June 2004, pp 198–209
7.
go back to reference Fick D, DeOrio A, Hu J, Bertacco V, Blaauw D, Sylvester D (2009) Vicis: a reliable network for unreliable silicon. In: Proceedings of the 46th Annual Design Automation Conference. ACM, pp 812–817 Fick D, DeOrio A, Hu J, Bertacco V, Blaauw D, Sylvester D (2009) Vicis: a reliable network for unreliable silicon. In: Proceedings of the 46th Annual Design Automation Conference. ACM, pp 812–817
8.
go back to reference Strano A, Bertozzi D, Trivino F, Sánchez JL, Alfaro FJ, Flich J (2012) OSR-Lite: fast and deadlock-free NoC reconfiguration framework. In: Embedded Computer Systems (SAMOS), 2012 International Conference on, pp 86–95. IEEE Strano A, Bertozzi D, Trivino F, Sánchez JL, Alfaro FJ, Flich J (2012) OSR-Lite: fast and deadlock-free NoC reconfiguration framework. In: Embedded Computer Systems (SAMOS), 2012 International Conference on, pp 86–95. IEEE
9.
go back to reference Aisopos K, DeOrio A, Peh L-S, Bertacco V (2011) Ariadne: agnostic reconfiguration in a disconnected network environment. In: Parallel Architectures and Compilation Techniques (PACT), 2011 International Conference on. IEEE, pp 298–309 Aisopos K, DeOrio A, Peh L-S, Bertacco V (2011) Ariadne: agnostic reconfiguration in a disconnected network environment. In: Parallel Architectures and Compilation Techniques (PACT), 2011 International Conference on. IEEE, pp 298–309
10.
go back to reference Lee D, Parikh R, Bertacco V (2014) Brisk and limited-impact NoC routing reconfiguration. In: 2014 Design, Automation Test in Europe Conference Exhibition (DATE), pp 1–6 Lee D, Parikh R, Bertacco V (2014) Brisk and limited-impact NoC routing reconfiguration. In: 2014 Design, Automation Test in Europe Conference Exhibition (DATE), pp 1–6
11.
go back to reference Parikh R, Bertacco V (2013) uDIREC: unified diagnosis and reconfiguration for frugal bypass of NoC faults. In: 2013 46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pp 148–159 Parikh R, Bertacco V (2013) uDIREC: unified diagnosis and reconfiguration for frugal bypass of NoC faults. In: 2013 46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pp 148–159
12.
go back to reference Parikh R, Bertacco V (2016) Resource conscious diagnosis and reconfiguration for NoC permanent faults. IEEE Trans Comput 65(7):2241–2256MathSciNetCrossRef Parikh R, Bertacco V (2016) Resource conscious diagnosis and reconfiguration for NoC permanent faults. IEEE Trans Comput 65(7):2241–2256MathSciNetCrossRef
13.
go back to reference Ghiribaldi A, Ludovici D, Triviño F, Strano A, Flich J, Sánchez JL, Alfaro F, Favalli M, Bertozzi D (2013) A complete self-testing and self-configuring NoC infrastructure for cost-effective MPSoCs. ACM Trans Embed Comput Syst (TECS) 12(4):106 Ghiribaldi A, Ludovici D, Triviño F, Strano A, Flich J, Sánchez JL, Alfaro F, Favalli M, Bertozzi D (2013) A complete self-testing and self-configuring NoC infrastructure for cost-effective MPSoCs. ACM Trans Embed Comput Syst (TECS) 12(4):106
14.
go back to reference Rodrigo S, Medardoni S, Flich J, Bertozzi D, Duato J (2009) Efficient implementation of distributed routing algorithms for NoCs. Comput Digit Techn IET 3(5):460–475CrossRef Rodrigo S, Medardoni S, Flich J, Bertozzi D, Duato J (2009) Efficient implementation of distributed routing algorithms for NoCs. Comput Digit Techn IET 3(5):460–475CrossRef
15.
go back to reference Rodrigo S, Flich J, Roca A, Medardoni S, Bertozzi D, Camacho J, Silla F, Duato J (2011) Cost-efficient on-chip routing implementations for CMP and MPSoC systems. IEEE Trans Comput-Aided Des Integr Circuits Syst 30(4):534–547CrossRef Rodrigo S, Flich J, Roca A, Medardoni S, Bertozzi D, Camacho J, Silla F, Duato J (2011) Cost-efficient on-chip routing implementations for CMP and MPSoC systems. IEEE Trans Comput-Aided Des Integr Circuits Syst 30(4):534–547CrossRef
16.
go back to reference Bishnoi R, Laxmi V, Gaur MS, Flich J (2015) \(d^2\)-LBDR: distance-driven routing to handle permanent failures in 2D mesh NoCs. In: Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition. EDA Consortium, pp 800–805 Bishnoi R, Laxmi V, Gaur MS, Flich J (2015) \(d^2\)-LBDR: distance-driven routing to handle permanent failures in 2D mesh NoCs. In: Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition. EDA Consortium, pp 800–805
17.
go back to reference Jain A, Laxmi V, Tripathi M, Gaur MS, Bishnoi R (2017) Performance-enhanced \(d^2\)-LBDR for 2D mesh network-on-chip. In: Kaushik B, Dasgupta S, Singh V (eds) VLSI design and test. VDAT 2017. Communications in computer and information science, vol 711. Springer, Singapore, pp 313–323 Jain A, Laxmi V, Tripathi M, Gaur MS, Bishnoi R (2017) Performance-enhanced \(d^2\)-LBDR for 2D mesh network-on-chip. In: Kaushik B, Dasgupta S, Singh V (eds) VLSI design and test. VDAT 2017. Communications in computer and information science, vol 711. Springer, Singapore, pp 313–323
18.
go back to reference Gomez ME, Duato J, Flich J, Lopez P, Robles A, Nordbotten NA, Lysne O, Skeie T (2004) An efficient fault-tolerant routing methodology for meshes and tori. IEEE Comput Archit Lett 3(1):3–3CrossRef Gomez ME, Duato J, Flich J, Lopez P, Robles A, Nordbotten NA, Lysne O, Skeie T (2004) An efficient fault-tolerant routing methodology for meshes and tori. IEEE Comput Archit Lett 3(1):3–3CrossRef
19.
go back to reference Valinataj M, Mohammadi S (2010) A fault-aware, reconfigurable and adaptive routing algorithm for NoC applications. In: 2010 18th IEEE/IFIP International Conference on VLSI and System-on-Chip, pp 13–18 Valinataj M, Mohammadi S (2010) A fault-aware, reconfigurable and adaptive routing algorithm for NoC applications. In: 2010 18th IEEE/IFIP International Conference on VLSI and System-on-Chip, pp 13–18
20.
go back to reference Ebrahimi M, Daneshtalab M, Plosila J, Tenhunen H (2012) MAFA: adaptive fault-tolerant routing algorithm for networks-on-chip. In: 2012 15th Euromicro Conference on Digital System Design, pp 201–207 Ebrahimi M, Daneshtalab M, Plosila J, Tenhunen H (2012) MAFA: adaptive fault-tolerant routing algorithm for networks-on-chip. In: 2012 15th Euromicro Conference on Digital System Design, pp 201–207
21.
go back to reference Ebrahimi M, Daneshtalab M (2015) A light-weight fault-tolerant routing algorithm tolerating faulty links and routers. Computing 97(6):631–648MathSciNetCrossRef Ebrahimi M, Daneshtalab M (2015) A light-weight fault-tolerant routing algorithm tolerating faulty links and routers. Computing 97(6):631–648MathSciNetCrossRef
22.
go back to reference Osterloh B, Michalik H, Fiethe B (2009) SoCWire: a robust and fault tolerant network-on-chip approach for a dynamic reconfigurable system-on-chip in FPGAs. In: Berekovic M, Müller-Schloer C, Hochberger C, Wong S (eds) Architecture of computing systems—ARCS 2009. Springer, Berlin, pp 50–59CrossRef Osterloh B, Michalik H, Fiethe B (2009) SoCWire: a robust and fault tolerant network-on-chip approach for a dynamic reconfigurable system-on-chip in FPGAs. In: Berekovic M, Müller-Schloer C, Hochberger C, Wong S (eds) Architecture of computing systems—ARCS 2009. Springer, Berlin, pp 50–59CrossRef
23.
go back to reference Nunez-Yanez A, Luis J, Beldachi F (2013) Configurable router design for dynamically reconfigurable systems based on the SOCWire NoC. Inst Adv Eng Sci 2(1):27 Nunez-Yanez A, Luis J, Beldachi F (2013) Configurable router design for dynamically reconfigurable systems based on the SOCWire NoC. Inst Adv Eng Sci 2(1):27
24.
go back to reference Gupta P, Akoglu A, Melde K, Roveda J (2013) FPGA based single cycle, reconfigurable router for NoC applications. In: 2013 IEEE International Symposium on Circuits and Systems (ISCAS2013), pp 2428–2431 Gupta P, Akoglu A, Melde K, Roveda J (2013) FPGA based single cycle, reconfigurable router for NoC applications. In: 2013 IEEE International Symposium on Circuits and Systems (ISCAS2013), pp 2428–2431
25.
go back to reference Bhanwala A, Kumar M, Kumar Y (2015) FPGA based design of low power reconfigurable router for network on chip (NoC). In: International Conference on Computing, Communication Automation, pp 1320–1326 Bhanwala A, Kumar M, Kumar Y (2015) FPGA based design of low power reconfigurable router for network on chip (NoC). In: International Conference on Computing, Communication Automation, pp 1320–1326
26.
go back to reference Gade SH, Garg S, Deb S (2017) OFDM based high data rate, fading resilient transceiver for wireless networks-on-chip. In: 2017 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). IEEE, pp 483–488 Gade SH, Garg S, Deb S (2017) OFDM based high data rate, fading resilient transceiver for wireless networks-on-chip. In: 2017 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). IEEE, pp 483–488
27.
go back to reference Wang S, Jin T (2014) Wireless network-on-chip: a survey. J Eng 2014(3):98–104 Wang S, Jin T (2014) Wireless network-on-chip: a survey. J Eng 2014(3):98–104
28.
go back to reference Xu L, Wang J, Zhang H, Gulliver TA (2017) Performance analysis of IAF relaying mobile D2D cooperative networks. J Frankl Inst 354(2):902–916CrossRef Xu L, Wang J, Zhang H, Gulliver TA (2017) Performance analysis of IAF relaying mobile D2D cooperative networks. J Frankl Inst 354(2):902–916CrossRef
29.
go back to reference Xu L, Wang J, Liu Y, Shi W, Gulliver TA (2018) Outage performance for IDF relaying mobile cooperative networks. Mobile Netw Appl 23(6):1496–1501CrossRef Xu L, Wang J, Liu Y, Shi W, Gulliver TA (2018) Outage performance for IDF relaying mobile cooperative networks. Mobile Netw Appl 23(6):1496–1501CrossRef
30.
go back to reference Raik J, Ubar R, Govind V (2007) Test configurations for diagnosing faulty links in NoC switches. In: 12th IEEE European Test Symposium (ETS’07), pp 29–34 Raik J, Ubar R, Govind V (2007) Test configurations for diagnosing faulty links in NoC switches. In: 12th IEEE European Test Symposium (ETS’07), pp 29–34
31.
go back to reference Ghofrani A, Parikh R, Shamshiri S, DeOrio A, Cheng K, Bertacco V (2012) Comprehensive online defect diagnosis in on-chip networks. In: 2012 IEEE 30th VLSI Test Symposium (VTS), pp 44–49 Ghofrani A, Parikh R, Shamshiri S, DeOrio A, Cheng K, Bertacco V (2012) Comprehensive online defect diagnosis in on-chip networks. In: 2012 IEEE 30th VLSI Test Symposium (VTS), pp 44–49
32.
go back to reference Duato J, Lysne O, Pang R, Pinkston TM (2005) A theory for deadlock-free dynamic network reconfiguration. Part I. IEEE Trans Parallel Distrib Syst 16(5):412–427CrossRef Duato J, Lysne O, Pang R, Pinkston TM (2005) A theory for deadlock-free dynamic network reconfiguration. Part I. IEEE Trans Parallel Distrib Syst 16(5):412–427CrossRef
33.
go back to reference Lysne O, Pinkston TM, Duato J (2005) A methodology for developing deadlock-free dynamic network reconfiguration processes. Part II. IEEE Trans Parallel Distrib Syst 16(5):428–443CrossRef Lysne O, Pinkston TM, Duato J (2005) A methodology for developing deadlock-free dynamic network reconfiguration processes. Part II. IEEE Trans Parallel Distrib Syst 16(5):428–443CrossRef
34.
go back to reference Agarwal N, Krishna T, Peh L-S, Jha NK (2009) GARNET: a detailed on-chip network model inside a full-system simulator. In: 2009 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). IEEE, pp 33–42 Agarwal N, Krishna T, Peh L-S, Jha NK (2009) GARNET: a detailed on-chip network model inside a full-system simulator. In: 2009 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). IEEE, pp 33–42
Metadata
Title
S2DIO: an extended scalable 2D mesh network-on-chip routing reconfiguration for efficient bypass of link failures
Authors
Anugrah Jain
Vijay Laxmi
Meenakshi Tripathi
Manoj Singh Gaur
Rimpy Bishnoi
Publication date
06-06-2019
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 10/2019
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-019-02915-5

Other articles of this Issue 10/2019

The Journal of Supercomputing 10/2019 Go to the issue

Premium Partner