More Web Proxy on the site http://driver.im/

research-article

FL-RuNS: A High-Performance and Runtime Reconfigurable Fault-Tolerant Routing Scheme for Partially Connected Three-Dimensional Networks on Chip

Authors:

Alexandre Coelho,

Nacer-Eddine Zergainoh,

Raoul VelazcoAuthors Info & Claims

IEEE Transactions on Nanotechnology, Volume 18

Pages 806 - 818

https://doi.org/10.1109/TNANO.2019.2931271

Published: 01 January 2019 Publication History

Abstract

Three-dimensional networks on chip (3D-NoCs) have been proposed as an enormously scalable solution to address communication problems in modern systems on chip. Through-silicon via (TSV) is usually adopted as a viable technology enabling vertical connection among NoC layers. However, TSV-based architectures typically exhibit high vulnerability to transient and permanent faults caused by aging effects, thermal violations, manufacturing issues, or even transient fault sources. Therefore, TSV-based architectures call for robust routing schemes capable of sustaining operation under unpredictable failure patterns. In this paper, we introduce FL-RuNS, a fault-tolerant routing scheme for achieving 100% packet delivery under an unconstrained set of runtime and permanent vertical link failures. The proposed scheme uses the concept of vertical link announcement to inform nodes in the network of the health condition of vertical links. This mechanism is able to dynamically and progressively reconfigure the entire network without any packet loss. FL-RuNS requires a very low number of asymmetric virtual channels to achieve both deadlock freedom and reachability. Also, FL-RuNS introduces one-flit-dedicated virtual channels, which are used as an escape buffer in case of TSVs failures. The experimental results have confirmed that FL-RuNS shows better reliability when compared to the recently proposed fault-tolerant routing algorithm. Furthermore, the hardware synthesis performed using a commercial 28-nm technology library shows a reasonable area and power overhead with respect to the non-fault-tolerant baseline.

References

[1]

W. Dally and B. Towles, “Route packets, not wires: On-chip interconnection networks,” in Proc. 38th Des. Autom. Conf., 2001, pp. 684–689.

[2]

E. Rijpkema et al., “Trade offs in the design of a router with both guaranteed and best-effort services for networks on chip,” in Proc. Des., Autom. Test Eur. Conf. Exhib., Mar. 2003, pp. 350–355.

[3]

B. S. Feero and P. P. Pande, “Networks-on-chip in a three-dimensional environment: A performance evaluation,” IEEE Trans. Comput., vol. 58, no. , pp. 32–45, Jan. 2009.

Digital Library

[4]

S. Murali, C. Seiculescu, L. Benini, and G. D. Micheli, “Synthesis of networks on chips for 3d systems on chips,” in Proc. Asia South Pac. Des. Autom. Conf., Jan. 2009, pp. 242–247.

[5]

W. R. Davis et al., “Demystifying 3D ICs: The pros and cons of going vertical,” IEEE Des. Test Comput., vol. 22, no. 6, pp. 498–510, Nov. 2005.

Digital Library

[6]

J. Burns et al., “Three-dimensional integrated circuits for low-power, high-bandwidth systems on a chip,” in Proc. IEEE Int. Solid-State Circuits Conf., Feb. 2001, pp. 268–269.

[7]

R. S. Patti, “Three-dimensional integrated circuits and the future of system-on-chip designs,” Proc. IEEE, vol. 94, no. 6, pp. 1214–1224, Jun. 2006.

[8]

I. Loi, S. Mitra, T. H. Lee, S. Fujita, and L. Benini, “A low-overhead fault tolerance scheme for TSV-based 3D network on chip links,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Des., Nov. 2008, pp. 598–602.

[9]

T. Zhang, Y. Zhan, and S. S. Sapatnekar, “Temperature-aware routing in 3D ICs,” in Proc. Asia South Pac. Conf. Des. Autom., Jan. 2006, pp. 6–11.

[10]

A. Eghbal, P. M. Yaghini, N. Bagherzadeh, and M. Khayambashi, “Analytical fault tolerance assessment and metrics for TSV-based 3D network-on-chip,” IEEE Trans. Comput., vol. 64, no. 12, pp. 3591–3604, Dec. 2015.

Digital Library

[11]

T. Frank et al., “Resistance increase due to electromigration induced depletion under TSV,” in Proc. Int. Rel. Phys. Symp., Apr. 2011, pp. 3F.4.1–3F.4.6.

[12]

C. Serafy and A. Srivastava, “Online TSV health monitoring and built-in self-repair to overcome aging,” in Proc. IEEE Int. Symp. Defect Fault Tolerance VLSI Nanotechnol. Syst., Oct. 2013, pp. 224–229.

[13]

A. Charif, A. Coelho, M. Ebrahimi, N. Bagherzadeh, and N. Zergainoh, “First-last: A cost-effective adaptive routing solution for TSV-based three-dimensional networks-on-chip,” IEEE Trans. Comput., vol. 67, no. 10, pp. 1430–1444, Oct. 2018.

[14]

A. Charif, N. E. Zergainoh, A. Coelho, and M. Nicolaidis, “Rout3D: A lightweight adaptive routing algorithm for tolerating faulty vertical links in 3D-NOCs,” in Proc. 22nd IEEE Eur. Test Symp., May 2017, pp. 1–6.

[15]

A. Coelho, A. Charif, N. Zergainoh, and R. Velazco, “A runtime fault-tolerant routing scheme for partially connected 3d networks-on-chip,” in Proc. IEEE Int. Symp. Defect Fault Tolerance VLSI Nanotechnol. Syst., Oct. 2018, pp. 1–6.

[16]

M. Ebrahimi, M. Daneshtalab, and J. Plosila, “Fault-tolerant routing algorithm for 3D NoC using hamiltonian path strategy,” in Proc. Des., Autom. Test Eur. Conf. Exhib., Mar. 2013, pp. 1601–1604.

[17]

S. Pasricha and Y. Zou, “A low overhead fault tolerant routing scheme for 3D networks-on-chip,” in Proc. 12th Int. Symp. Qual. Electron. Des., 2011, pp. 204–211.

[18]

S. Akbari, A. Shafiee, M. Fathy, and R. Berangi, “AFRA: A low cost high performance reliable routing for 3D mesh NoCs,” in Proc. Des., Autom. Test Eur. Conf. Exhib., Mar. 2012, pp. 332–337.

[19]

A. B. Ahmed and A. B. Abdallah, “Graceful deadlock-free fault-tolerant routing algorithm for 3D network-on-chip architectures,” J. Parallel Distrib. Comput., vol. 74, no. 4, pp. 2229–2240, 2014.

Digital Library

[20]

E. Taheri, M. Isakov, A. Patooghy, and M. A. Kinsy, “Advertiser elevator: A fault tolerant routing algorithm for partially connected 3D network-on-chips,” in Proc. IEEE 60th Int. Midwest Symp. Circuits Syst., Aug. 2017, pp. 136–139.

[21]

B. Niazmand, S. P. Azad, J. Flich, J. Raik, G. Jervan, and T. Hollstein, “Logic-based implementation of fault-tolerant routing in 3D network-on-chips,” in Proc. 10th IEEE/ACM Int. Symp. Netw. Chip, Sep. 2016, pp. 1–8.

[22]

R. Salamat, M. Khayambashi, M. Ebrahimi, and N. Bagherzadeh, “A resilient routing algorithm with formal reliability analysis for partially connected 3D-NoCs,” IEEE Trans. Comput., vol. 65, no. 11, pp. 3265–3279, Nov. 2016.

Digital Library

[23]

R. Salamat, M. Khayambashi, M. Ebrahimi, and N. Bagerzadeh, “Lead: An adaptive 3D-NoC routing algorithm with queuing-theory based analytical verification,” IEEE Trans. Comput., vol. 67, no. 8, pp. 1153–1166, Aug. 2018.

Digital Library

[24]

F. Dubois, A. Sheibanyrad, F. Petrot, and M. Bahmani, “Elevator-First: A deadlock-free distributed routing algorithm for vertically partially connected 3D-NoCs,” IEEE Trans. Comput., vol. 62, no. 3, pp. 609–615, Mar. 2013.

Digital Library

[25]

R. Salamat, M. Ebrahimi, N. Bagherzadeh, and F. Verbeek, “CoBRA: Low cost compensation of TSV failures in 3D-NoC,” in Proc. IEEE Int. Symp. Defect Fault Tolerance VLSI Nanotechnol. Syst., Sep. 2016, pp. 115–120.

[26]

A. Charif, A. Coelho, N.-E. Zergainoh, and M. Nicolaidis, “A framework for scalable TSV assignment and selection in three-dimensional networks-on-chips,” VLSI Des., vol. 2017, 2017, Art. no.

[27]

A. Charif, A. Coelho, N. E. Zergainoh, and M. Nicolaidis, “A dynamic sufficient condition of deadlock-freedom for high-performance fault-tolerant routing in networks-on-chips,” IEEE Trans. Emerg. Topics Comput., vol. PP, no. 99, pp. 1–1, Nov. 2017.

[28]

M. Ebrahimi and M. Daneshtalab, “EbDa: A new theory on design and verification of deadlock-free interconnection networks,” in Proc. ACM/IEEE 44th Annu. Int. Symp. Comput. Archit., Jun. 2017, pp. 703–715.

[29]

A. Coelho, A. Charif, N. E. Zergainoh, J. Fraire, and R. Velazco, “A soft-error resilient route computation unit for 3D networks-on-chips,” in Proc. Des., Autom. Test Eur. Conf. Exhib., Mar. 2018, pp. 1357–1362.

[30]

R. Mullins, “Netmaker,” 2009. [Online]. Available: http://www-dyn.cl.cam.ac.uk/rdm34/wiki

Cited By

Almeida da Silva ANogueira LCoelho ASilveira JMarcon C(2025)Securet3d: An Adaptive, Secure, and Fault-Tolerant Aware Routing Algorithm for Vertically–Partially Connected 3D-NoCIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2024.350057533:1(275-287)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TVLSI.2024.3500575
Ramesh SManna KGogineni VChattopadhyay SMahapatra S(2024)Congestion-Aware Vertical Link Placement and Application Mapping Onto 3-D Network-on-Chip ArchitecturesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337125543:8(2249-2262)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3371255
Taheri EKim RNikdast M(2023)AdEle+: An Adaptive Congestion-and-Energy-Aware Elevator Selection for Partially Connected 3D Networks-on-ChipIEEE Transactions on Computers10.1109/TC.2023.324826072:8(2278-2292)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TC.2023.3248260
Show More Cited By

Index Terms

FL-RuNS: A High-Performance and Runtime Reconfigurable Fault-Tolerant Routing Scheme for Partially Connected Three-Dimensional Networks on Chip

Index terms have been assigned to the content through auto-classification.

Recommendations

Fault-Tolerant Network Interfaces for Networks-on-Chip

As the complexity of designs increases and technology scales down into the deep-submicron domain, the probability of malfunctions and failures in the networks-on-chip (NoCs) components increases. In this work, we focus on the study and evaluation of ...
Fault tolerant architectures for on-chip networks
Fault tolerant routing in toroidal networks
PAS '95: Proceedings of the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis

We give an O(r/sup 2/) time algorithm for constructing a fault-free routing path of optimal length between any true non-fault nodes of an r-dimensional torus with 2r-1 faulty nodes. We show that the Rabin diameter of a r-dimensional torus is its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Nanotechnology

IEEE Transactions on Nanotechnology Volume 18, Issue

May 2019

625 pages

ISSN:1536-125X

Issue’s Table of Contents

1536-125X © 2019 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

Publisher

IEEE Press

Publication History

Published: 01 January 2019

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Almeida da Silva ANogueira LCoelho ASilveira JMarcon C(2025)Securet3d: An Adaptive, Secure, and Fault-Tolerant Aware Routing Algorithm for Vertically–Partially Connected 3D-NoCIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2024.350057533:1(275-287)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TVLSI.2024.3500575
Ramesh SManna KGogineni VChattopadhyay SMahapatra S(2024)Congestion-Aware Vertical Link Placement and Application Mapping Onto 3-D Network-on-Chip ArchitecturesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337125543:8(2249-2262)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3371255
Taheri EKim RNikdast M(2023)AdEle+: An Adaptive Congestion-and-Energy-Aware Elevator Selection for Partially Connected 3D Networks-on-ChipIEEE Transactions on Computers10.1109/TC.2023.324826072:8(2278-2292)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TC.2023.3248260
Taheri EKim RNikdast M(2021)AdEle: An Adaptive Congestion-and-Energy-Aware Elevator Selection for Partially Connected 3D NoCs2021 58th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18074.2021.9586174(67-72)Online publication date: 5-Dec-2021
https://dl.acm.org/doi/10.1109/DAC18074.2021.9586174
Zhang YHong XChen ZPeng ZJiang J(2020)A Deterministic-Path Routing Algorithm for Tolerating Many Faults on Very-Large-Scale Network-on-ChipACM Transactions on Design Automation of Electronic Systems10.1145/341406026:1(1-26)Online publication date: 27-Oct-2020
https://dl.acm.org/doi/10.1145/3414060

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents