Fault-Tolerant Network-on-Chip Design with Flexible Spare Core Placement

Abstract

Network-on-Chip (NoC) has been proposed as a promising solution to overcome the communication challenges of System-on-Chip (SoC) design in nanoscale technologies. With the advancement in the nanoscale technology, the integration density of Intellectual Property (IP) cores in a single chip have increased, leading to heat dissipation, which in turn makes the system unreliable. Therefore, efficient fault-tolerant methods are necessary at different levels to improve overall system performance and make the system to operate normally. This article presents a flexible spare core placement technique for mesh-based NoC by taking several benchmark applications into consideration. An Integer Linear Programming (ILP)-based solution has been proposed for the spare core placement problem. Also, Particle Swarm Optimisation (PSO)-based meta-heuristic has been proposed for the same. Experiments have been performed by taking several application benchmarks reported in the literature and the applications generated using the TGFF tool. Comparisons have been carried out using our approach and the approach followed in the literature (i) by varying the network size with fixed fault percentage in the network, and (ii) by fixing the network size while varying the percentage of faults in the network. We have also compared the overall communication cost and CPU runtime between ILP and PSO approaches. The results show significant reductions in the overall communication cost, average network latency, and network power consumption across all the cases using our approach over the approaches reported in the literature.

References

1. A. Karkar, T. Mak, K. F. Tong, and A. Yakovlev. 2016. A survey of emerging interconnects for on-chip efficient multicast and broadcast in many-cores. IEEE Circuits and Systems Magazine 16, 1 (2016), 58--72.
2. L. Benini and G. De Micheli. 2002. Networks on chips: A new SoC paradigm. IEEE Computer 35, 1 (2002), 70--78.
3. W. J. Dally and B. Towles. 2001. Route packets, not wires: On-chip interconnection networks. In 38th Design Automation Conference (IEEE Cat. No.01CH37232). 684--689.
4. M. Radetzki, C. Feng, X. Zhao, and A. Jantsch. 2013. Methods for fault tolerance in Networks-on-Chip. ACM Computing Surveys (CSUR) 46, 1 (2013), 8.
5. C. L. Chou and R. Marculescu. 2011. FARM: Fault-Aware Resource Management in NoC-based multiprocessor platforms. In 2011 Design, Automation 8 Test in Europe. 1--6.
6. W. Donath. 1980. Complexity theory and design automation. In 17th Design Automation Conference. 412--419.
7. F. Khalili and H. R. Zarandi. 2012. A fault-tolerant low-energy multi-application mapping onto NoC-based multiprocessors. In 2012 IEEE 15th International Conference on Computational Science and Engineering. 421--428.
8. B. N. K. Reddy, M. H. Vasantha, and Y. B. N. Kumar. 2016. A gracefully degrading and energy-efficient fault tolerant NoC using spare core. In 2016 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). 146--151.
9. D. Xiang, K. Chakrabarty, and H. Fujiwara. 2016. A unified test and fault-tolerant multicast solution for Network-on-Chip designs. In 2016 IEEE International Test Conference (ITC). 1--9.
10. S. D. Mediratta and J. Draper. 2007. Performance evaluation of probe-send fault-tolerant network-on-chip router. In 2007 IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP). 69--75.
11. Z. Qian, Y. F. Teh, and C. Tsui. 2011. A fault-tolerant Network-on-Chip design using dynamic reconfiguration of partial-faulty routing resources. In 2011 IEEE/IFIP 19th International Conference on VLSI and System-on-Chip. 192--195.
12. J. Liu, J. Harkin, Y. Li, and L. P. Maguire. 2016. Fault-tolerant Networks-on-Chip routing with coarse and fine-grained look-ahead. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 35, 2 (2016), 260--273.
13. J. Xu, Y. Hang, P. Guo, and Q. Dai. 2016. A unified online fault-tolerant mechanism for FIFO faults in Network-on-Chip router. In 2016 13th IEEE International Conference on Solid-State and Integrated Circuit Technology (ICSICT). 1419--1421.
14. Y. Jojima and M. Fukushi. 2016. A fault-tolerant routing method for 2D-mesh Network-on-Chips based on components of a router. In 2016 IEEE 5th Global Conference on Consumer Electronics. 1--2.
15. A. Runge and R. Kolla. 2016. Using Benes networks at fault-tolerant and deflection routing-based Network-on-Chips. In 2016 10th IEEE/ACM International Symposium on Networks-on-Chip (NOCS). 1--8.
16. A. Charif, N. E. Zergainoh, and M. Nicolaidis. 2016. Addressing transient routing errors in fault-tolerant Networks-on-Chips. In 2016 21th IEEE European Test Symposium (ETS). 1--6.
17. K. Latif, A. M. Rahmani, T. Seceleanu, and H. Tenhunen. 2011. A low-cost processing element recovery mechanism for fault tolerant Networks-on-Chip. In 2011 NORCHIP. 1--4.
18. S. Khoroush and M. Reshadi. 2013. A fault-tolerant approach for application-specific Network-on-Chip. In 2013 NORCHIP. 1--6.
19. Y. Y. Chen, E. J. Chang, H. K. Hsin, K. C. Chen, and A. Y. Wu. 2017. Path-diversity-aware fault-tolerant routing algorithm for Network-on-Chip systems. IEEE Transactions on Parallel and Distributed Systems 28, 3 (2017), 838--849.
20. D. DiTomaso, A. Kodi, and A. Louri. 2014. QORE: A fault-tolerant Network-on-Chip architecture with power-efficient quad-function channel (QFC) buffers. In 2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA). 320--331.
21. R. Xie, J. Cai, and P. Wang. 2016. RFRA: Reconfigurable and fault-tolerant routing algorithm without virtual channels for 2D Network-on-Chip. In 2016 13th IEEE International Conference on Solid-State and Integrated Circuit Technology (ICSICT). 1615--1617.
22. S. Moriam and G. P. Fettweis. 2016. Fault-tolerant deadlock-free adaptive routing algorithms for hexagonal Networks-on-Chip. In 2016 Euromicro Conference on Digital System Design (DSD). 131--137.
23. B. Niazmand, S. P. Azad, J. Flich, J. Raik, G. Jervan, and T. Hollstein. 2016. Logic-based implementation of fault-tolerant routing in 3D Network-on-Chips. In 2016 10th IEEE/ACM International Symposium on Networks-on-Chip (NOCS). 1--8.
24. V. Rantala, T. Lehtonen, P. Liljeberg, and J. Plosila. 2009. Multi-network interface architectures for fault-tolerant Network-on-Chip. In 2009 International Symposium on Signals, Circuits and Systems. 1--4.
25. S. H. S. Rezaei, M. Modarressi, R. Y. Aminabadi, and M. Daneshtalab. 2016. Fault-tolerant 3-D Network-on-Chip design using dynamic link sharing. In 2016 Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE). 1195--1200.
26. A. Kohler, G. Schley, and M. Radetzki. 2010. Fault-tolerant Network-on-Chip switching with graceful performance degradation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 29, 6 (2010), 883--896.
27. H. Kariniemi and J. Nurmi. 2006. Fault-tolerant 2-D mesh Network-on-Chip for multiprocessor Systems-on-Chip. In 2006 IEEE Design and Diagnostics of Electronic Circuits and systems. 184--189.
28. M. Valinataj, P. Liljeberg, and J. Plosila. 2013. Enhanced fault-tolerant Network-on-Chip architecture using hierarchical agents. In 2013 IEEE 16th International Symposium on Design and Diagnostics of Electronic Circuits 8 Systems (DDECS). 141--146.
29. D. Park, C. Nicopoulos, J. Kim, N. Vijaykrishnan, and C. R. Das. 2006. Exploring fault-tolerant Network-on-Chip architectures. In International Conference on Dependable Systems and Networks (DSN'06). 93--104.
30. O. Derin, D. Kabakci, and L. Fiorin. 2011. Online task remapping strategies for fault-tolerant Network-on-Chip multiprocessors. In 5th ACM/IEEE International Symposium. 129--136.
31. G. Luo, H. Zhao, and C. Song. 2008. Convergence analysis of a dynamic discrete PSO algorithm. In 2008 1st International Conference on Intelligent Networks and Intelligent Systems. 89--92.
32. Andrew B. Kahng, Bin Li, Li-Shiuan Peh, and Kambiz Samadi. 2009. ORION 2.0: A fast and accurate NoC power and area model for early-stage design space exploration. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'09). European Design and Automation Association, Belgium, 423--428.
33. J. Kennedy and R. Eberhart. 1995. Particle swarm optimization. IEEE International Conference on Neural Networks 4 (1995), 1942--1948.
34. S. Kundu and S. Chattopadhyay. 2008. Network-on-chip architecture design based on Mesh-of-Tree deterministic routing topology. International Journal of High Performance Systems Architecture 1, 3 (2008), 163--182.
35. S. Kundu, J. Soumya, and S. Chattopadhyay. 2012. Design and evaluation of Mesh-of-Tree based network-on-chip using virtual channel router. Microprocessors and Microsystems 36, 6 (2012), 471--488.
36. www.ibm.com/in-en/products/ilog-cplex-optimization-studio. Accessed 23 December 2018.
37. P. K. Sahu and S. Chattopadhyay. 2013. A survey on application mapping strategies for Network-on-Chip design. Journal of Systems Architecture 59, 1 (2013), 60--76.
38. F. Khalili and H. R. Zarandi. 2013. A fault-tolerant core mapping technique in Networks-on-Chip. IET Computers 8 Digital Techniques 7, 6 (2013), 238--245.
39. Soumya J, Ashish Sharma, and Santanu Chattopadhyay. 2014. Multi-application Network-on-Chip design using global mapping and local reconfiguration. ACM Trans. Reconfigurable Technol. Syst 7, 2, Article 7 (2014).
40. Priyajit Mukherjee and Santanu Chattopadhyay. 2017. Low-power low-latency floorplan aware path synthesis in application-specific Network-on-Chip design. Integration, the VLSI Journal 58 (2017), 167--188.
41. Pradip Kumar Sahu, Kanchan Manna, Tapan Shah, and Santanu Chattopadhyay. 2014. Thermal uniformity-aware application mapping for Network-on-Chip design. International Journal of Computer Applications 99, 2 (2014), 0975--8887.
42. C. A. Quaye. 2005. Thermal-aware mapping and placement for 3-D NoC design. In IEEE International Conference on SoC. 25--28.
43. R. P. Dick, D. L. Rhodes, and W. Wolf. 1998. TGFF: Task graphs for free. In 6th International Workshop on Hardware/Software Codesign. 97--101.
44. Y. Raparti, N. Kapadia, and S. Pasricha. 2017. ARTEMIS: An aging-aware runtime application mapping framework for 3D NoC-based chip multiprocessors. IEEE Transactions on Multi-Scale Computing Systems (TMSCS) 3, 2 (2017), 72--85.
45. V. Y. Raparti and S. Pasricha. 2016. CHARM: A checkpoint-based resource management framework for reliable multicore computing in the dark silicon era. In IEEE International Conference on Computer Design (ICCD).

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

    • Fault-tolerant network topologies