A Novel Approach to Optimize Fault-Tolerant Hybrid Wireless Network-on-Chip Architectures

Abstract

Wireless Network-on-Chip (WNoC) architectures have emerged as a promising interconnection infrastructure to address the performance limitations of traditional wire-based multihop NOCs. Nevertheless, the WNoC systems encounter high failure rates due to problems pertaining to integration and manufacturing of wireless interconnection in nano-domain technology. As a result, the permanent failures may lead to the formation of any shape of faulty regions in the interconnection network, which can break down the whole system. This issue is not investigated in previous studies on WNoC architectures. Our solution advocates the adoption of communication structures with both node and link on disjoint paths. On the other hand, the imposed costs of WNoC design must be reasonable. Hence, a novel approach to design an optimized fault-tolerant hybrid hierarchical WNoC architecture for enhancing performance as well as minimizing system costs is proposed. The experimental results indicate that the robustness of this newly proposed design is significantly enhanced in comparison with its the fault-tolerant wire-based counterparts in the presence of various faulty regions under both synthetic and application-specific traffic patterns.

References

1. N. Banerjee, P. Vellanki, and K. S. Chatha. 2004. A power and performance model for network-on-chip architectures. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, IEEE Computing Society, 1250--1255. DOI:http://dx.doi.org/10.1109/DATE.2004.1269067
2. L. Benini and G. De Micheli. 2002. Networks on chip: A new paradigm for systems on chip design. In Proceedings of the Design, Automation and Test in Europe (DATE), IEEE Computing Society, 418--419. DOI:http://dx.doi.org/10.1109/DATE.2002.998307
3. P. Bogdan, T. Dumitraş, and R. Marculescu. 2007. Stochastic communication: A new paradigm for fault-tolerant networks-on-chip. VLSI Design 2007. DOI:http://dx.doi.org/10.1155/2007/95348
4. P. Bogdan and R. Marculescu. 2009. Statistical physics approaches for network-on-chip traffic characterization. In Proceedings of the 7th IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS’09). New York: ACM Press, 461. DOI:http://dx.doi.org/10.1145/1629435.1629498
5. P. Bogdan and R. Marculescu. 2011. Hitting time analysis for fault-tolerant communication at nanoscale in future multiprocessor platforms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 30, 8, 1197--1210. DOI:http://dx.doi.org/10.1109/TCAD.2011.2138430
6. J. Cervantes and C. R. Stephens. 2006. Optimal mutation rates for genetic search. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO’06), New York: ACM Press, 1313. DOI:http://dx.doi.org/10.1145/1143997.1144201
7. K. Chang, S. Deb, and A. Ganguly, et al. 2012. Performance evaluation and design trade-offs for wireless network-on-chip architectures. ACM Journal of Emerging Technology and Computer Systems 8, 3, 1--25. DOI:http://dx.doi.org/10.1145/2287696.2287706
8. C.-W. Chen and C.-P. Chung. 2005. Designing a disjoint paths interconnection network with fault tolerance and collision solving. Journal of Supercomputing 34, 1, 63--80. DOI:http://dx.doi.org/10.1007/s11227-005-0327-7
9. H. Chung, C. Teuscher, and P. Pande. 2014. Design and evaluation of technology-agnostic heterogeneous networks-on-chip. ACM Journal of Emerging Technology and Computer Systems 10, 3, 1--27. DOI:http://dx.doi.org/10.1145/2567666
10. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computing 6, 2, 182--197. DOI:http://dx.doi.org/10.1109/4235.996017
11. S. Deb, K. Chang, and X. Yu, et al. 2013. Design of an energy-efficient CMOS-compatible NoC architecture with millimeter-wave wireless interconnects. IEEE Transactions on Computing 62, 12, 2382--2396. DOI:http://dx.doi.org/10.1109/TC.2012.224
12. S. Deb, A. Ganguly, P. P. Pande, B. Belzer, and D. Heo. 2012. Wireless NoC as interconnection backbone for multicore chips: Promises and challenges. IEEE Journal on Emerging Selected Topics in Circuits and Systems 2, 2, 228--239. DOI:http://dx.doi.org/10.1109/JETCAS.2012.2193835
13. K. Dejong. 2002. Evolutionary Computation (1st. Ed.). MIT Press.
14. A. DeOrio, D. Fick, and V. Bertacco, et al. 2012. A reliable routing architecture and algorithm for NoCs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 31, 5, 726--739. DOI:http://dx.doi.org/10.1109/TCAD.2011.2181509
15. J. Duato, S. Yalamanchili, and L. M. Ni. 2003. Interconnection Networks: An Engineering Approach. Morgan Kaufmann.
16. B. S. Feero and P. P. Pande. 2009. Networks-on-chip in a three-dimensional environment: A performance evaluation. IEEE Trans. Comput. 58, 1 (Jan. 2009), 32--45. DOI:http://dx.doi.org/10.1109/TC.2008.142
17. C. Feng, Z. Lu, A. Jantsch, M. Zhang, and Z. Xing. 2013. Addressing transient and permanent faults in NoC with efficient fault-tolerant deflection router. IEEE Transactions on Very Large Scale Integrated Systems 21, 6, 1053--1066. DOI:http://dx.doi.org/10.1109/TVLSI.2012.2204909
18. R. W. Floyd. 1962. Algorithm 97: Shortest path. Communications of the ACM 5, 6, 345. DOI:http://dx.doi.org/10.1145/367766.368168
19. R. M. Francis. 2009. Exploring Networks-On-Chip for FPGAs. Ph.D. Dissertation. University of Cambridge.
20. B. Fu, Y. Han, H. Li, and X. Li. 2014. ZoneDefense: A fault-tolerant routing for 2-D meshes without virtual channels. IEEE Transactions on Very Large Scale Integrated Systems 22, 1, 113--126. DOI:http://dx.doi.org/10.1109/TVLSI.2012.2235188
21. A. Ganguly, K. Chang, S. Deb, P. P. Pande, B. Belzer, and C. Teuscher. 2011a. Scalable hybrid wireless network-on-chip architectures for multicore systems. IEEE Transactions on Computing 60, 10, 1485--1502. DOI:http://dx.doi.org/10.1109/TC.2010.176
22. A. Ganguly, P. Pande, B. Belzer, and A. Nojeh. 2011b. A unified error control coding scheme to enhance the reliability of a hybrid wireless network-on-chip. In Proceedings of the 2011 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, IEEE, 277--285. DOI:http://dx.doi.org/10.1109/DFT.2011.24
23. A. Ganguly, P. Wettin, K. Chang, and P. Pande. 2011c. Complex network inspired fault-tolerant NoC architectures with wireless links. In Proceedings of the 5th ACM/IEEE International Symposium on Networks-on-Chip (NOCS’11), New York: ACM Press, 169. DOI:http://dx.doi.org/10.1145/1999946.1999974
24. M. Hayenga, D. R. Johnson, and M. Lipasti. 2010. Pitfalls of orion-based simulation. ORION 35, 0--40.
25. ITRS Edition. 2009. Retrieved November 2, 2014 from http://www.itrs.net/Links/2009itrs/home2009.htm.
26. A. B. Kahng, B. Li, L.-S. Peh, and K. Samadi. 2009. ORION 2.0: A fast and accurate NoC power and area model for early-stage design space exploration. In Proceedings of the 2009 Design, Automation and Test in Europe Conference and Exhibition, 423--428. DOI:http://dx.doi.org/10.1109/DATE.2009.5090700
27. A. B. Kaplan. 2008. Architectural Integration of RF-Interconnect to Enhance On-Chip Communication for Many-Core Chip Multiprocessors. Ph.D. Dissertation. University of California, Los Angeles.
28. K. Kempa, J. Rybczynski, and Z. Huang, et al. 2007. Carbon nanotubes as optical antennae. Advanced Materials 19, 3, 421--426. DOI:http://dx.doi.org/10.1002/adma.200601187
29. S. Khuller and B. Raghavachari. 2010. Basic graph algorithms. In Algorithms and Theory of Computation Handbook. Chapman & Hall/CRC, 7--7.
30. S. Khuller and U. Vishkin. 1994. Biconnectivity approximations and graph carvings. Journal of the ACM 41, 2, 214--235. DOI:http://dx.doi.org/10.1145/174652.174654
31. S.-B. Lee, L. Zhang, and J. Cong, et al. 2009. A scalable micro wireless interconnect structure for CMPs. In Proceedings of the 15th Annual International Conference on Mobile Computing and Networking (MobiCom’09), New York: ACM Press, 217. DOI:http://dx.doi.org/10.1145/1614320.1614345
32. W. Liu, J. Xu, and X. Wu, et al. 2011. A NoC traffic suite based on real applications. In 2011 IEEE Computer Society Annual Symposium on VLSI, IEEE, 66--71. DOI:http://dx.doi.org/10.1109/ISVLSI.2011.49
33. E. L. Lloyd. 2010. Fault-tolerant relay node placement in heterogeneous wireless sensor networks. IEEE IEEE Transactions on Mobile Computing 9, 5, 643--656. DOI:http://dx.doi.org/10.1109/TMC.2009.161
34. I. Loi, F. Angiolini, and L. Benini. 2009. Synthesis of low-overhead configurable source routing tables for network interfaces. In Proceedings of the 2009 Design, Automation and Test in Europe Conference and Exhibition, 262--267. DOI:http://dx.doi.org/10.1109/DATE.2009.5090668
35. O. Lysne, T. Skeie, S.-A. Reinemo, and I. Theiss. 2006. Layered routing in irregular networks. IEEE Transactions on Parallel Distributed Systmes 17, 1, 51--65. DOI:http://dx.doi.org/10.1109/TPDS.2006.12
36. T. Majumder, P. P. Pande, and A. Kalyanaraman. 2013. Network-on-chip with long-range wireless links for high-throughput scientific computation. In Proceedings of the 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and PhD Forum. IEEE, 781--790. DOI:http://dx.doi.org/10.1109/IPDPSW.2013.72
37. R. Manevich, L. Polishuk, I. Cidon, and A. Kolodny. 2014. Designing single-cycle long links in hierarchical NoCs. Microprocessors and Microsystems 38, 8, 814--825. DOI:http://dx.doi.org/10.1016/j.micpro.2014.05.005
38. R. Marculescu and P. Bogdan. 2007. The chip is the network: Toward a science of network-on-chip design. Foundations and Trends® in Electronic Design Automation 2, 4, 371--461. DOI:http://dx.doi.org/10.1561/1000000011
39. D. Matolak, A. Kodi, S. Kaya, D. Ditomaso, S. Laha, and W. Rayess. 2012. Wireless networks-on-chips: Architecture, wireless channel, and devices. IEEE Wireless Communications 19, 5, 58--65. DOI:http://dx.doi.org/10.1109/MWC.2012.6339473
40. H. Matsutani, P. Bogdan, and R. Marculescu, et al. 2013. A case for wireless 3D NoCs for CMPs. In Proceedings of the 2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC). IEEE, 23--28. DOI:http://dx.doi.org/10.1109/ASPDAC.2013.6509553
41. A. Mejia, M. Palesi, and J. Flich, et al. 2009. Region-based routing: A mechanism to support efficient routing algorithms in NoCs. IEEE Transactions on Very Large Scale Integrated Systems 17, 3, 356--369. DOI:http://dx.doi.org/10.1109/TVLSI.2008.2012010
42. A. More and B. Taskin. 2012. A unified design methodology for a hybrid wireless 2-D NoC. In Proceedings of the 2012 IEEE International Symposium on Circuits and Systems. IEEE, 640--643. DOI:http://dx.doi.org/10.1109/ISCAS.2012.6272113
43. J. Murray, T. Lu, P. Wettin, P. P. Pande, and B. Shirazi. 2014. Dual-level DVFS-enabled millimeter-wave wireless NoC architectures. ACM Journal of Emerging Technologies and Computer Systems 10, 4, 1--27. DOI:http://dx.doi.org/10.1145/2600074
44. A. Nojeh, P. Pande, A. Ganguly, S. Sheikhaei, B. Belzer, and A. Ivanov. 2008. Reliability of wireless on-chip interconnects based on carbon nanotube antennas. In Proceedings of the 2008 IEEE 14th International Mixed-Signals, Sensors, and Systems Test Workshop. IEEE, 1--6. DOI:http://dx.doi.org/10.1109/IMS3TW.2008.4581628
45. K. K. O, K. Kim, and B. A. Floyd, et al. 2005. On-chip antennas in silicon ICs and their application. IEEE Transactions on Electronic Devices 52, 7, 1312--1323. DOI:http://dx.doi.org/10.1109/TED.2005.850668
46. U. Y. Ogras and R. Marculescu. 2006. “It's a small world after all”: NoC performance optimization via long-range link insertion. IEEE Transactions on Very Large Scale Integrated Systems 14, 7, 693--706. DOI:http://dx.doi.org/10.1109/TVLSI.2006.878263
47. M. Palesi, S. Kumar, and V. Catania. 2010. Leveraging partially faulty links usage for enhancing yield and performance in networks-on-chip. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 29, 3, 426--440. DOI:http://dx.doi.org/10.1109/TCAD.2010.2041851
48. P. P. Pande, C. Grecu, M. Jones, A. Ivanov, and R. Saleh. 2005. Performance evaluation and design trade-offs for network-on-chip interconnect architectures. IEEE Transactions on Computing 54, 8, 1025--1040. DOI:http://dx.doi.org/10.1109/TC.2005.134
49. PTM - Latest models. Retrieved Novamber 2, 2014 from http://ptm.asu.edu/latest.html.
50. Z. Qian, P. Bogdan, C. Y. Tsui, and R. Marculescu. 2013. Performance evaluation of multicore systems: From traffic analysis to latency predictions (Embedded tutorial). In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers (ICCAD), IEEE, 82--84. DOI:http://dx.doi.org/10.1109/ICCAD.2013.6691101
51. M. Radetzki, C. Feng, X. Zhao, and A. Jantsch. 2013. Methods for fault tolerance in networks-on-chip. ACM Computing Surveys 46, 1, 1--38. DOI:http://dx.doi.org/10.1145/2522968.2522976
52. P. Salihundam, S. Jain, and T. Jacob, et al. 2011. A 2 tb/s 6 4 mesh network for a single-chip cloud computer with dvfs in 45 nm cmos. IEEE Journal on Solid-State Circuits 46, 4, 757--766. DOI:http://dx.doi.org/10.1109/JSSC.2011.2108121
53. A. Shacham, K. Bergman, and L. P. Carloni. 2008. Photonic networks-on-chip for future generations of chip multiprocessors. IEEE Transactions on Computing 57, 9, 1246--1260. DOI:http://dx.doi.org/10.1109/TC.2008.78
54. N. Srinivas and K. Deb. 1994. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computing 2, 3, 221--248. DOI:http://dx.doi.org/10.1162/evco.1994.2.3.221
55. C. Sun, C.-H. O. Chen, and G. Kurian, et al. 2012. DSENT - A tool connecting emerging photonics with electronics for opto-electronic networks-on-chip modeling. In Proceedings of the 2012 IEEE/ACM 6th International Symposium on Networks-on-Chip. IEEE, 201--210. DOI:http://dx.doi.org/10.1109/NOCS.2012.31
56. M. Sun, Y. P. Zhang, G. X. Zheng, and Yin, W.-Y. 2009. Performance of intra-chip wireless interconnect using on-chip antennas and UWB radios. IEEE Transactions on Antennas and Propagation 57, 9, 2756--2762. DOI:http://dx.doi.org/10.1109/TAP.2009.2024458
57. A. Varga. 2001. The OMNeT++ discrete event simulation system. In Proceedings of the European Simulation Multiconference (ESM’01). 185.
58. V. Vijayakumaran. 2012. Adaptive Code Division Multiple Access Protocol for Wireless Network-on-Chip Architectures. Ph.D. Dissertation. Rochester Institute of Technology.
59. V. Vijayakumaran, M. P. Yuvaraj, N. Mansoor, N. Nerurkar, A. Ganguly, and A. Kwasinski. 2014. CDMA enabled wireless network-on-chip. ACM Journal on Emerging Technology and Computer Systems 10, 4, 1--20. DOI:http://dx.doi.org/10.1145/2536778
60. S. Waharte and R. Boutaba. 2006. Totally disjoint multipath routing in multihop wireless networks. In 2006 IEEE International Conference on Communications. IEEE, 5576--5581. DOI:http://dx.doi.org/10.1109/ICC.2006.255550
61. C. Wang, W.-H. Hu, and N. Bagherzadeh. 2012. A load-balanced congestion-aware wireless network-on-chip design for multi-core platforms. Microprocessors and Microsystems 36, 7, 555--570. DOI:http://dx.doi.org/10.1016/j.micpro.2011.10.002
62. P. Wettin, P. P. Pande, D. Heo, B. Belzer, S. Deb, and A. Ganguly. 2013a. Design space exploration for reliable mm-wave wireless NoC architectures. In Proceedings of the 2013 IEEE 24th International Conference on Application-Specific Systems, Architectures and Processors. IEEE, 79--82. DOI:http://dx.doi.org/10.1109/ASAP.2013.6567554
63. P. Wettin, A. Vidapalapati, A. Gangul, and P. P. Pande. 2013b. Complex network-enabled robust wireless network-on-chip architectures. ACM Journal on Emerging Technology and Computer Systems 9, 3, 1--19. DOI:http://dx.doi.org/10.1145/2491676
64. R.-Y. Wu, G.-H. Chen, Y.-L. Kuo, and G. J. Chang. 2007. Node-disjoint paths in hierarchical hypercube networks. Information Sciences (NY) 177, 19, 4200--4207. DOI:http://dx.doi.org/10.1016/j.ins.2007.02.035
65. D. Zhao and Y. Wang. 2008a. MTNet: Design of a wireless test framework for heterogeneous nanometer systems-on-chip. IEEE Transactions on Very Large Scale Integrated Systems 16, 8, 1046--1057. DOI:http://dx.doi.org/10.1109/TVLSI.2008.2000820
66. D. Zhao and Y. Wang. 2008b. SD-MAC: Design and synthesis of a hardware-efficient collision-free QoS-aware MAC protocol for wireless network-on-chip. IEEE Transactions on Computing 57, 9, 1230--1245. DOI:http://dx.doi.org/10.1109/TC.2008.86
67. D. Zhao, Y. Wang, J. Li, and T. Kikkawa. 2011. Design of multi-channel wireless NoC to improve on-chip communication capacity. In Proceedings of the 5th ACM/IEEE International Symposium on Networks-on-Chip. ACM, 177--184. DOI:http://dx.doi.org/10.1145/1999946.1999975
68. H. Zhu, P. P. Pande, and C. Grecu. 2007. Performance evaluation of adaptive routing algorithms for achieving fault tolerance in NoC fabrics. In Proceedings of the 2007 IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP‘07). IEEE, 42--47. DOI:http://dx.doi.org/10.1109/ASAP.2007.4429956

Index Terms

• Networks

  • Network architectures