Abstract

Three-dimensional Network-On-Chips (3D NOC) are the most efficient communication structures for complex multi-processor System-On-Chips (SOC). Such structures utilize short vertical interconnects in 3D ICs together with scalability of NOC to improve performance of communications in SOCs. By scaling trends in 3D integration, probability of fault occurrence increases that leads to low yield of links, especially TSV-based vertical links in 3D NOCs. In this paper, FT-Z-OE (Fault Tolerant Z Odd-Even) routing, a distributed routing to tolerate permanent faults on vertical links of 3D NOCs is proposed. FT-Z-OE is designed to have low overhead because of no need to any routing table or global information of faults in the network. The proposed routing is evaluated using a cycle-accurate network simulator and compared to planar-adaptive routing for a 3D mesh-based network. It is shown that FT-Z-OE significantly outperforms planar-adaptive in the terms of latency and throughput under synthetic traffic patterns.

References

• Dally, W. J. and Towles, B. , 2001, Route packets, not wires: on-chip interconnection networks, In Proceeding of the Design Automation Conference, pp. 684-689.
• Benini, L. and De Micheli, L. , 2002, Networks on chips: a new SoC paradigm, Computer 35 (1), pp. 70-78.
• A. W. Topol, et al. , Three-dimensional integrated circuits, IBM J. RES. & DEV 50(4. 5) (2006) 491-506.
• Loi, I. , et al. , 2008, A Low-overhead Fault Tolerance Scheme for TSV-based 3D Network on Chip Links, In Proceeding of ICCAD, pp. 598-602.
• Dumitras, T. and Marculescu, R. , 2003, On-chip stochastic communication, In Proceeding of DATE, pp. 790-795.
• Pirretti, M. , Link, G. M. , Brooks, R. R. , Vijaykrishnan, N. , Kandemir, M. , Irwin, M. J. , 2004, Fault tolerant algorithms for network-on-chip interconnect, In Proceedings of IEEE Computer society Annual Symposium on VLSI, pp. 46 – 51.
• Zhu, H. , Pande, P. P. and Grecu, C. , 2007, Performance evaluation of adaptive routing algorithms for achieving fault tolerance in NOC fabrics, In Proceeding of ASAP, pp. 42-47.
• Young Bok, K. and Yong-Bini, K. , 2007, Fault Tolerant Source Routing for Network-on-chip, In Proceeding of 22nd IEEE International Symposium on Defect and Fault-Tolerance in VLSI systems, pp. 12-20.
• Schonwald, T. , et al. , 2007, Fully adaptive fault tolerant routing algorithm for network on chip architecture, In Proceeding of DSD, pp. 527-534.
• Glass, M. J. , Ni, L. M. , 1994, The turn model for Adaptive Routing, Journal of ACM 41(5), pp. 874-902.
• Chiu, G. , 2000, The odd-even turn model for Adaptive Routing, IEEE Transactions on Parallel and Distributed Systems 11 (7) , pp. 729-738.
• Pasrecha, S. , et al. , 2010, OE+IOE: A Novel Turn Model Based Fault Tolerant Routing Scheme for Networks-on-Chip, In Proceeding of ISSS, pp. 24-29.
• Andres, M. , et al. , 2009, Region based: a mechanism to support efficient routing algorithms in NOCs, In Proceeding of IEEE TVLSI, pp. 356-369.
• Hu, J. and Marculescu, R. , 2004, Dyad- smart routing for networks on chip, in: Proceeding of DAC, pp. 260-263.
• Jovanovic, S. , Tanougast, C. , Weber, S. , Bobda, C. , 2009, A new deadlock-free fault-tolerant routing algorithm for NoC interconnections, In Proceeding of FPLA, pp. 326 – 331.
• Rezazadeh, A. , Fathy, M. , Hassanzadeh, A. , 2009, If-cube3: An improved fault-tolerant routing algorithm to achieve less latency in NoCs, In Proceeding of IACC, pp. 278-283.
• Wu, J. , 2003, A fault-tolerant and deadlock-free routing protocol in 2D meshes based on odd-even turn model," IEEE Transactions on Computers 52 (9), pp. 1154-1169.
• Boppana , R. V. and Chalasani, S. , 1995, Fault-tolerant wormhole routing algorithms for mesh networks, IEEE Transactions on Computers 44 (7), pp. 848–864.
• Chien, A. A. and Kim, J. H. , 1992, Planar-adaptive routing: low-cost adaptive networks for multiprocessors, In Proceeding of the 19th Annual International symposium on computer architecture, pp. 268-277.
• Nordbotten, N. A. , et al. , 2004, A fully adaptive fault-tolerant routing methodology based on intermediate nodes, In Proceeding of IFIP International Conference on Network and Parallel Computing, vol. 3222, pp. 341-356.
• Wu, J. , 2003, A simple fault-tolerant adaptive and minimal routing approach in 3-D meshes, Journal of Computer Science and Technology, 18, pp. 1-13.
• Ebrahimi, M. , Daneshtalab, M. , Plosila, J. , 2013, Fault-tolerant routing algorithm for 3D NoC using hamiltonian path strategy, Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 1601-1604.
• Akbari, S. , Shafiee, A. , Fathy, M. , Berangi, R. , 2012, AFRA: A low cost high performance reliable routing for 3D mesh NOCs, In Proceeding of DATE, pp. 332-337.
• Li, M. , Zeng, Q. A. and Jone, W. B. , 2006, DyXY - A proximity congestion aware deadlock-free dynamic routing method for Network on Chip, In Proceeding of Design Automation Conference, pp. 849-852.
• https://nocs. stanford. edu/
• Kahng, A. B. , Li, B. , Peh. L. S. , and Samadi, K. , 2009, ORION2: A Fast and Accurate NOC Power and Area Model for Early-Stage Design Space Exploration, In Proceeding of DATE, pp. 423-428.
• Dally, W. J. and Towels, B. , 2004, Principles and Practices of Interconnection Networks, Morgan Kaufmann.