Call for Paper - January 2023 Edition
IJCA solicits original research papers for the January 2023 Edition. Last date of manuscript submission is December 20, 2022. Read More

NoCGIN: A Gamma Interconnection Network as NoC Interconnect

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2016
Authors:
Meenal A. Borkar, Nitin Nitin, Atul Kumar
10.5120/ijca2016909552

Nitin Nitin Meenal A. Borkar and Atul Kumar. NoCGIN: A Gamma Interconnection Network as NoC Interconnect. International Journal of Computer Applications 141(2):17-25, May 2016. BibTeX

@article{10.5120/ijca2016909552,
	author = {Meenal A. Borkar, Nitin Nitin and Atul Kumar},
	title = {NoCGIN: A Gamma Interconnection Network as NoC Interconnect},
	journal = {International Journal of Computer Applications},
	issue_date = {May 2016},
	volume = {141},
	number = {2},
	month = {May},
	year = {2016},
	issn = {0975-8887},
	pages = {17-25},
	numpages = {9},
	url = {http://www.ijcaonline.org/archives/volume141/number2/24756-2016909552},
	doi = {10.5120/ijca2016909552},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

As billions of transistors can easily getting manufactured on small chips, multiple processing elements are also getting fabricated on these chips. This type of chip manufacturing caught attention of researchers from the domains like Parallel and Distributed Computing, Computer Aided Chip Manufacturing, Computer Design etc. Many researchers tried to utilize the boosted capacity of multiprocessor chips to implement time consuming, bulky, parallel algorithms. A strong communication network, which is reliable, robust and reusable is very much needed to achieve expected performance. This paper proposes a new Gamma Interconnection Network variant, namely NoCGIN, which act as interconnection network for Networks-on-Chip. The paper further gives information about the topology of NoCGIN and a simple routing algorithm for routing packets.

References

  1. Hwang, K., and Briggs, F.A., 1984, Computer Architecture and Parallel Processing, McGraw– Hill, New York.
  2. Dally, W., and Towles, B., 2004, Principles and Practices of Interconnection Networks, Morgan Kaufmann, San Francisco, CA.
  3. Duato, J., Yalamanchili, S., and Ni, L.M., 2003, Interconnection Networks: An Engineering Approach, Morgan Kaufmann, and San Francisco, CA.
  4. Feng, T. Y., 1981, “A Survey of Interconnection Networks”, IEEE Transactions on Computers.
  5. Adams III, G. B., Agrawal, D. P., and Siegel, H. J., 1987, “A Survey and Comparison of Fault–Tolerant Multistage Interconnection Networks”, IEEE Transactions on Computers.
  6. Special Issue on Interconnection Networks, 1987, IEEE Computer 20 (6).
  7. Siegel, H.J., 1990, Interconnection Network for Large Scale Parallel Processing: Theory and Case Studies, McGraw Hill.
  8. Nitin, 2002, On a fault–tolerant hybrid ZETA MIN, Master’s Thesis, Computer Science and Engineering Department, Thapar Institute of Engineering and Technology, Patiala, Punjab.
  9. Nitin, 2006, “Component Level Reliability Analysis of Fault–tolerant Hybrid MINs”, WSEAS Transactions on Computers.
  10. Kruskal, C. P., and Snir, M., 1983, “The Performance of Multistage Interconnection Networks for Multiprocessors”, IEEE Transactions on Computers, Vol. C-32, Issue 12.
  11. Raghavendra, C. S., and Varma, A., 1986, “Fault Tolerant Multiprocessors with Redundant-Path Interconnection Networks”, IEEE Transactions on Computers, Vol. C-35, Issue 4.
  12. Varma, A., and Raghavendra, C. S., 1989, “Fault-Tolerant routing in Multistage Interconnection Networks”, IEEE Transactions on Computers, Vol. 38, Issue 3.
  13. Fan, C. C., and Bruck, J., 2000, “Tolerating multiple faults in Multistage Interconnection Networks with minimal extra stages”, IEEE Transactions on Computers, Vol. 49, Issue 9.
  14. Parker, D. S., and Raghavendra, C. S., 1982, “The Gamma Network: A Multiprocessor Interconnection Network With Redundant Paths”, IEEE Transactions on Computers.
  15. Parker, D. S., and Raghavendra, C. S., 1984, “The Gamma Network”, IEEE Transactions on Computers, Vol. c–33, No. 4.
  16. Kothari, S. C., Prabhu G. M., and Roberts, R., 1988, “The Kappa Network with Fault–Tolerant Destination Tag Algorithm”, IEEE Transactions On Computers, Vol.37 No 5.
  17. Lee, K.Y., and Hegazy, W., 1988, “The Extra Stage Gamma Network”, IEEE Transactions on Computer, Vol. 37, No. 11.
  18. Lee, K. Y., and Yoon, H., 1990, “The B–Network: A Multistage Interconnection Network With Backward Links”, IEEE Transactions on Computer, Vol. 39, No. 7.
  19. Venkatesan, R., and Mouftah, H. T., 1992, “Balanced Gamma Network–A New Candidate For Broadband Packet Switch Architectures”, IEEE Transactions on Computer.
  20. Chen, C. W., Lu, N. P., Chen, T. F., and Chung, C. P., 2000, “Fault Tolerant Gamma Interconnection Networks By Chaining”, IEE Proceedings – Comput. Digit. Tech, Vol. 147, No. 2.
  21. Chuang, P. J., 1998, “Creating a Highly Reliable Modified Gamma Interconnection Network Using a Balance Approach”, IEE Proceedings – Comput. Digit. Tech, Vol. 145, No. 1.
  22. Tzeng, N. F., Chuang, P. J., and Wu, C. H., 1993, “Creating Disjoint Paths In Gamma Interconnection Networks”, IEEE Transactions on Computer, Vol. 42, No. 10.
  23. Chuang, P. J., 1994, “CGIN: A Modified Gamma Interconnection Network with Multiple Disjoint Paths”, IEEE Transactions on Computer.
  24. Chen, C. W., Lu, N. P., and Chung, C. P., 2003, “3–Disjoint Gamma Interconnection Network”, The Journal of Systems and Software.
  25. Chen, Z., “A Class of Incomplete Gamma Interconnection Network”, Available at: www.researchgate.com
  26. Borkar, M.A., 2010, “A Survey of Fault Tolerance Techniques Used in GIN”, in National Conference EEC, 2010
  27. Borkar, M.A., and Nitin, 2011, “3D–CGIN: A 3 Disjoint Paths CGIN with Alternate Source”, in Proceedings of ACC.
  28. Barlik, P. K., 2011, “FIR Filter IC Design Using Redundant Binary Number Systems”, M.Tech Thesis, NIT Rourkela, India.
  29. Borkar, M.A., 2011, “3D–CGIN: A 3Disjoint Paths CGIN with Alternate Source”, M.Tech Dissertation, UTU Dehradun, India.
  30. Borkar, M.A., and Nitin, 2012, “Network Status Aware Routing in 3D–CGIN”, in Proceedings of ICCCS.
  31. Wu, Y., Liu, L., and Wang, Z., 1993, “Modified gamma network and its optical implementation”, Journal of Applied Optics, Vol. 32, Issue 35.
  32. Chaoyang, C. Q., “A minimal cost dynamic rerouting gamma network”, Available At: http://wr.cyut.edu.tw
  33. Rajkumar, S., and Goyal, N.K., 2014, “Design of 4–disjoint gamma interconnection layouts and reliability analysis of gamma interconnection networks”, Journal of Supercomputing.
  34. Chen, C. W., and Chung, C. P., 2001, “Fault Tolerant Gamma Interconnection Networks without backtracking”, Journal of Systems and Software.
  35. Borkar, M.A., Nitin, and Kumar, A., 2015, “A Survey on the Family of Gamma Interconnection Network”, International Journal of Applied Engineering Research, Vol. 10, No. 24.
  36. Bell, S., Edwards, B., Amann, J., Conlin, R., et al., 2008, “TILE64 processor: A 64-core SoC with Mesh interconnect”, In Proceedings of the IEEE International Solid-State Circuits Conference (ISSCC'08).
  37. Vangal, S., Howard, J., Ruhl, G., Dighe, S., Wilson, H., et al., 2007, “An 80-tile 1.28 tflops network-on-chip in 65nm cmos”, In Digest of Technical Papers of the IEEE International Solid-State Circuits Conference (ISSCC'07).
  38. Hoskote, Y., Vangal, S., Singh, A., Borkar, N., et al., 2007, “A 5-ghz mesh interconnect for a tera flops processor”, IEEE Micro.
  39. Radetzki, M., Feng, C. C., Zhao, X. Q., and Jantsch, A., 2013, “Methods for Fault Tolerance in Network-on-Chip”, ACM Computing Surveys.
  40. Tilera Announces the world’s first 100-core processor with the new tile-gx family, Available At: http://goo.gl/K9c85
  41. Nychis, G., Fallin, C., Moscibroda, T., Mutlu, O., and Seshan, S., 2012, “On-chip Networks from a Networking Perspective: Congestion and Scalability in Multi-Core Interconnects”, In SIGCOMM.
  42. University of Glasgow, “Scientists squeeze more than 1,000 cores on to computer chip.”, Available At: http://goo.gl/KdBbW
  43. Nitin, 2012, “On Asymptotic Analysis of Packet and Wormhole Switched Routing Algorithm for Application-specific Network-on-Chip”, Journal of Electrical and Computer Engineering.
  44. Nitin, and Chauhan, D.S., 2010, “Stochastic Communication for Application Specific Networks-on-Chip”, Journal of Supercomputing, Springer, Volume 59, Number 2.
  45. Agarwal, A., Iskander, C., and Shankar, R., 2009, “Survey on Network on Chip (NoC) Architectures & Contributions”, Journal of Engineering, Computing and Architecture, Vol. 3, Issue 1.
  46. Constantinescu, C., 2003, “Trends and challenges in vlsi circuit reliability”, IEEE Micro.
  47. Chae-Eun, R., Han-You, J., and Soonhoi, H., 2004, “Many-to-many core-switch mapping in 2-D mesh NoC architectures”, Proc. IEEE International Conference on Computer Design: VLSI in Computers and Processors.
  48. Nitin, 2006, “Component Level reliability analysis of fault-tolerant hybrid MINs,” WSEAS Transactions on Computers, vol. 5, no. 9.
  49. Nitin, and Subramanian, A., 2008, “Efficient algorithms and methods to solve dynamic MINs stability problem using stable matching with complete ties,” Journal of Discrete Algorithms, vol. 6, no. 3.
  50. Bjerregaard, T., and Mahadevan, S., 2006, “A survey of research and practices of network-on-chip,” ACM Computing Surveys, vol. 38, no. 1.
  51. Pirretti, M., Link, G. M., Brooks, R. R., Vijaykrishnan, N., et al, 2004, “Fault Tolerant algorithms for network-on-chip interconnect”, Proceedings of IEEE Computer Society Annual Symposium on VLSI.
  52. Holsmark, R., and Kumar, S., 2005, “Design issues and performance evaluation of mesh NoC with regions”, Proceedings of 23rd NORCHIP conference.
  53. Rehan, F., Alemzadeh, H., Safari, S., Prinetto, P., et al, 2008, “Relaibility in Application Specific Mesh-based NoC Architectures”, Proceedings of 14th IEEE International Online Testing Symposium.
  54. Holsmark, R., Palesi, M., and Kumar, S., 2008, “Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions”, Journal of System Architecture, Vol. 54, Issue 3-4.
  55. Samuelsson, H., and Kumar, S., 2004, “Ring road NoC architecture”, Proceedings of NORCHIP conference.
  56. Bononi, L., and Concer, N., 2006, “Simulation and analysis of network on chip architectures: ring, spidergon and 2D mesh”, Proceedings of the Conference on Design, Automation and Test in Europe.
  57. Bononi, L., Concer, N., Grammatikakis, M., Coppola M., et al, 2007, “NoC Topologies Exploration based on Mapping and Simulation Models”, Proceedings of 10th Euromicro conference on Digital System Design Architectures, Methods and Tools.
  58. Manevich, R., Walter, I., Cidon, I., and Kolodny, A., 2009, “Best of both worlds: A bus enhanced NoC (BENoC)”, 3rd ACM/IEEE Symposium on Networks-on-Chip.
  59. Thid, R., Sander, I., and Jantsch, A., 2006, “Flexible Bus and NoC Performance Analysis with Configurable Synthetic Workloads”, Proceedings of 9th Euromicro conference on Digital System Design Architectures, Methods and Tools.
  60. Lee, H. G., Chang, N., Ogras, U. Y., and Marculescu, R., 2007, “On-chip communication architecture exploration: A quantitative evaluation of point-to-point, bus, and network-on-chip approaches”, ACM Transactions on Design Automation of Electronic Systems, Vol 12, Issue 3.
  61. Tsai, K. L., Lai, F., Pan, C. Y., Xiao, D. S., et al, 2010, “Design of low latency on-chip communication based on hybrid NoC architecture”, Proceedings of 8th IEEE conference on NEWCAS.
  62. Mirza-Aghatabar, M., Koohi, S., Hessabi, S., and Pedram, M., 2007, “An Empirical Investigation of Mesh and Torus NoC Topologies Under Different Routing Algorithms and Traffic Models”, Proceedings of 10th Euromicro conference on Digital System Design Architectures, Methods and Tools.
  63. Concatto, C., Almeida, P., Kastensmidt, M., Cota, E., et al, 2009, “Improving yield of torus nocs through fault-diagnosis-and-repair of interconnect faults”, Proceedings of 15th IEEE International Online Testing Symposium.
  64. Kao, Y. H., Alfaraj, N., Yang, M., and Chao, H. J., 2010, “Design of High-Radix Clos Network-on-Chip”, 4th ACM/IEEE International Symposium on Networks-on-Chip.
  65. Kao, Y. H., Yang, M., Artan, N.S., and Chao, H. J., 2011, “CNoC: High-Radix Clos Network-on-Chip”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 30, Issue 12.
  66. Pande, P. P., Grecu, C., Jones, M., Ivanov, A., et al, 2005, “Performance evaluation and design trade-offs for network-on-chip interconnect architectures”, IEEE Transactions on Computers, Vol. 54, Issue 8.
  67. Zeferino, C. A., and Susin, A. A., 2003, “SoCIN: a parametric and scalable network-on-chip”, Proceeding of 16th Symposium of Integrated Circuits and Systems Design.
  68. Ogras, U. Y., Hu, J., and Marculescu, R., 2005, “Key research problems in NoC design: a holistic perspective”, Proceedings of 3rd IEEE/ACM/IFIP International Conference on Hardware/Software codesign and System synthesis.

Keywords

Networks-on-chip, Gamma Interconnection Network, Systems-on-chip, Parallel Computing