Continuous technology scaling in semiconductor industry makes the system reliability as a serious concern in the area of nanoscale computing. In this paper, a fully adaptive routing algorithm is proposed to overcome faults in NoCs (Network-on-Chip). This algorithm called DINRA-NoC (DIstiributed and New Routing Algorithm for NoC) is distributed, fault tolerant and congestion-aware. First, each node selects the appropriate output to route packets to neighbor routers according to the state of each link and router. Secondly, the proposed routing algorithm takes in account the status of adjacent routers traffic to update the congestion metric. DINRA-NoC does not use any VCs (Virtual Channels) and is deadlock-free. A simulation of the proposed routing algorithm has been carried out using Noxim simulator. The results show that DINRA ensures a good reliability rate despite of the presence of many faulty routers/links. In other hand, the simulation results indicate that the performance of the proposed routing algorithm surpasses the performance of existing algorithms in terms of lowering the congestion, improving average latency and increasing throughput.
G.Angelo, M.Laracca and S.Rampone, Automated eddy current non-destructive testing through low definition lissajous figures, in: IEEE Metrology for Aerospace (MetroAeroSpace), 2016, pp. 280–285.
2.
R.J.Behrouz, M.Modarressi and H.Sarbazi-Azad, Fault-tolerant routing algorithms in networks on-chip, in: Routing Algorithms in Networks-on-Chip, Springer, 2014, pp. 193–210. doi:10.1007/978-1-4614-8274-1_8.
3.
F.Chaix, D.Avresky, N.E.Zergainoh and M.Nicolaidis, Fault-tolerant deadlock-free adaptive routing for any set of link and node failures in multi-cores systems, in: Proceedings 9th IEEE International Symposium on Network Computing and Applications, NCA 2010, 2010, pp. 52–59.
4.
A.Charif, N.E.Zergainoh and M.Nicolaidis, MUGEN: A high-performance fault-tolerant routing algorithm for unreliable Networks-on-Chip, in: IOLTS, 2015, pp. 71–76.
5.
S.C.N.Chatterjee and K.Manna, Pare router based reliable Network-on-Chip design, in: Proc. of IEEE Intl. Symposium on Circuits and Systems, 2014, pp. 1957–1960.
6.
C.Chen and S.D.Cotofana, An Effective Routing Algorithm to Avoid Unnecessary Link Abandon in 2D Mesh NoCs, IEEE, 2013, pp. 311–318.
7.
Y.Y.Chen, E.J.Chang and H.K.Hsin, Path-diversity-aware fault-tolerant routing algorithm for Network-on-Chip, Systems IEEE Transactions on parallel and distributed systems28(3) (2017), 838–849. doi:10.1109/TPDS.2016.2588482.
8.
W.J.Dally and H.Aoki, Deadlock-free adaptive routing in multicomputer networks using virtual channels, IEEE Transactions on Parallel and Distributed Systems4(4) (1993), 466–475.
9.
R.Das, S.Narayanasamy, S.K.Satpathy and R.Dreslinski, Catnap: Energy proportional multiple Network-on-Chip, in: Proceedings of the 40th International Symposium on Computer Architecture, Tel Aviv, Israel ISCA, 2013.
10.
A.DeOrio, L.-S.Peh and V.Bertacco, ARIADNE: Agnostic reconfiguration in a disconnected network environment, in: International Conference on Parallel Architectures and Compilation Techniques (PACT), 2011, pp. 298–309.
11.
M.Dimopoulos, Y.Gang, L.Anghel, M.Benabdenbi, N.Zergainoh and M.Nicolaidis, Fault-tolerant adaptive routing under an unconstrained set of node and link failures for manycore systems-on-chip, Microprocessors Microsystems, v.38(6) (2014), 620–635. doi:10.1016/j.micpro.2014.04.003.
12.
M.Ebrahimi, Reliable and adaptive routing algorithms for 2d and 3d networks-on-chip, in: Routing Algorithms in Networks-on-Chip, Springer, New York, NY, USA, 2014, pp. 211–237. doi:10.1007/978-1-4614-8274-1_9.
13.
M.Ebrahimi, M.Daneshtalab and J.Plosila, High Performance Fault-Tolerant Routing Algorithm for NoC-Based Many-Core Systems, IEEE, 2013, pp. 462–469.
14.
M.Ebrahimi, M.Daneshtalab, J.Plosila and F.Mehdipour, MD: Minimal path-based fault-tolerant routing in on-chip networks, in: Proc. of the 18th Asia and South Pacific Design Automation Conference, 2013, pp. 35–40.
15.
M.Ebrahimi, M.Daneshtalab, J.Plosila and H.Tenhunen, MAFA: Adaptive fault-tolerant routing algorithm for networks-on-chip, in: Proc. of 15th Euromicro Conference on Digital System Design, 2013, pp. 201–207.
16.
C.Feng, Z.Lu, A.Jantsch, J.Li and M.Zhang, A reconfigurable fault-tolerant deflection routing algorithm based on reinforcement learning for networks-on-chip, in: Proceedings of the International Workshop on Network on Chip Architectures (NoCArc), Atlanta, Georgia, 2010.
17.
D.Fick, A.DeOrio, J.Hu, V.Bertacco, D.Blaauw and D.Sylvester, Vicis: A reliable network for unreliable silicon, in: ACM/IEEE Design Automation Conference (DAC), 2009, pp. 812–817.
18.
V.Fochi, E.Wachter, A.Erichsen, A.M.Amory and F.G.Moraes, An integrated method for implementing online fault detection in NoCBased MPSoCs, in: ISCAS, 2015, pp. 1562–1565.
19.
B.Fu, Y.Han, H.Li and X.Li, Zone defense: A fault-tolerant routing for 2-D meshes without virtual channels, IEEE Trans. Very Large Scale Integration (VLSI) Syst.22(1) (2014), 113–126. doi:10.1109/TVLSI.2012.2235188.
20.
C.Glass and L.Ni, The turn model for adaptive routing, in: Proceedings of the 19th Annual International Symposium on Computer Architecture (ISCA – 92), New York, NY, USA, 1992, pp. 278–287.
21.
T.Lehtonen, P.Liljeberg and J.Plosila, Online reconfigurable self-timed links for fault tolerant NoC, VLSI Design2007 (2007), 94676.
22.
C.-A.Lin, H.-K.Hsin, E.-J.Chang and A.-Y.Wu, ACO-based fault-aware routing algorithm for Network-on-Chip systems, in: Signal Processing Systems (SiPS), Workshop on, IEEE, 2014, pp. 342–347.
23.
P.Poluri and A.Louri, Shield: A reliable network-onchip router architecture for chip multiprocessors, IEEE Trans. on Parallel and Distributed Systems27(10) (2016), 3058–3070. doi:10.1109/TPDS.2016.2521641.
24.
I.Pratomo and S.Pillement, Gradient: An adaptive fault-tolerant routing algorithm for 2D mesh network-on-chips, in: Proc. Des. Archit. Signal Image Process, 2012, pp. 1–8.
25.
M.Radetzki, C.Feng, X.Zhao and A.Jantsch, Methods for fault tolerance in networks-on-chip, ACM Computing Surveys46(1) (2013), 8. doi:10.1145/2522968.2522976.
26.
Y.Ren, L.Liu, S.Yin, J.Han and S.Wei, Efficient fault-tolerant topology reconfiguration using a maximum flow algorithm, ACM Trans. Reconfig. Technol. Syst.8(3) (2015), 19. doi:10.1145/2700417.
A.Vitkovskiy, V.Soteriou and C.Nicopoulos, Dynamic fault-tolerant routing algorithm for networks-on-chip based on localised detouring paths, Computers & Digital Techniques IET7(2) (2013), 93–103. doi:10.1049/iet-cdt.2012.0054.
29.
E.Wachter, A.Erichsen, A.Amory and F.G.Moraes, Topology agnostic fault-tolerant NoC routing method, in: DATE, 2013, pp. 1595–1600.
30.
S.Werner, J.Navaridas and M.Lujan, A survey on design approaches to circumvent permanent faults in networks-on-chip, ACM Computing Surveys48(4) (2016), 59. doi:10.1145/2886781.
31.
S.Xiangming, Configurable Redundant Routing for Network on Chip, IEEE, 2012, pp. 477–479.
32.
Z.Zhang, A.Greiner and S.Taktak, A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh Network-on-Chip, Design Automation Conference (2008), 441–446, DAC 2008. 45th ACM/IEEE on, 2008.
