Search WWW Search
»Journal Description
»Call for Papers and Reviewers
»Author Guidelines
»Contents & Papers
»Call for Special Issues

Routing for Center Concentrated Mesh


Akash Punhani1*,Pardeep Kumar1,N Nitin2


1 Department of CSE& IT, Jaypee University of Information Technology, Waknaghat, Solan, H.P. India
2 Department of CSE& IT, Jaypee Institute of Information Technology, Sector 62, Noida, U.P. India


As the number of cores increases this affects the performance of the mesh and leads to investigation of new topological concept that is center concentrated Mesh. The topology designed seems to be efficient but the routing algorithm seems to contradict the objectives. In this paper we propose a new routing algorithm which is more time efficient in comparison to the center concentrated mesh (CCM) routing in terms of QoS Parameters and space efficient in comparison of table based routing algorithm. The main idea behind designing the new routing algorithm is due to the identification of hot spot effect at the center nodes created by CCM routing algorithm. Proposed routing algorithm is a hybrid of XY routing and CMM routing. Main objective of the proposed routing algorithm is to reduced hop count and improve the performance in quality of service parameters. It has been observed that the proposed routing algorithm has shown improvement in all the quality of service parameters. This improvement ranges from 10% - 30% as shown by the simulation results. The hop count analysis also provides the improvement of 7%. All the results prove that the proposed routing algorithm is a better substitute to CMM routing algorithm. The routing has also been compared to odd-even algorithm and was found to be slightly better.


Mesh interconnection network, Routing algorithm, Latency, Throughput.

Full Text:

  1. M. Mejia, J. Palesi, S. Flich, P. Kumar, R. Lopez, R. Holsmark, and J. Duato, Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs, Vol. 17, No. 3, pp. 356–369, IEEE Trans. Very Large Scale Integr. VLSI Syst, Mar. 2009.
  2. J. Flich, A. Mejia, J. Duato, and D. Valencia, “Region-Based Routing : An Efficient Routing Mechanism to Tackle Unreliable Hardware in Network on Chips”, In: Proc. of First International Symposium on Networks-on-Chip (NOCS'07), IEEE , pp. 183–194, 2007.
  3. P. Guerrier and A. Greiner, “A generic architecture for on-chip packet-switched interconnections”, In: Proc. of the conference on Design, automation and test, Europe, pp. 250–256, 2000.
  4. S. Kumar, A. Jantsch, J.-P. Soininen, M. Forsell, M. Millberg, J. Öberg, K. Tiensyrjä, and A. Hemani, “A network on chip architecture and design methodology”, In: Proc IEEE Computer Society Annual Symposium on VLSI, pp. 105–112, 2002.
  5. J. Balfour and W. J. Dally, “Design trade-offs for tiled CMP on-chip networks”, In: Proc. of the 20th annual international conference on Supercomputing, pp. 187–198, 2006.
  6. E. Bolotin, A. Morgenshtein, I. Cidon, R. Ginosar, and A. Kolodny, “Automatic hardware-efficient SoC integration by QoS network on chip”, In: Proc. 11th IEEE International Conference on Electronics, Circuits and Systems, ICECS 2004, pp. 479–482, 2004.
  7. W. J. Dally and B. Towles, “Route packets, not wires: on-chip interconnection networks”, In Proc. of Design Automation Conference, pp. 684–689, 2001.
  8. W. J. Dally and B. P. Towles, Principles and practices of interconnection networks. Elsevier, 2004.
  9. L. Yu-hang, Z. Ming-fa, W. Jue, Li-min Xiao, and G. Tao, “Xtorus: An Extended Torus Topology for On-Chip Massive Data Communication”, In Proc. 2012 IEEE 26th International of Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), pp. 2061–2068, 2012.
  10. W.H. Hu, S. E. Lee, N. Bagherzadeh, Z. Xiao-jing, H. Wei-wu, M. Ke, and Z. Long-bing, Xmesh: a mesh-like topology for network on chip, Netw. Chip Archit., p. 14, 2008
  11. Y. Wang, H. Du, and X. Shen, Topological properties and routing algorithm for semi-diagonal torus networks, J. China Univ. Posts Telecommun., vol. 18, no. 5, pp. 64–70, 2011.
  12. L. K. Arora and Rajkumar, “C2Mesh”, In: Proc of IEEE 3rd International Advance Computing Conference (IACC), 2013, pp. 282–286, 2013.
  13. S. Yadav and C. R. Krishna, “CCTorus: A New Torus Topology for Interconnection Networks”, In: Proc Int’l Conference on Advanced Computational Technologies & Creative Media (ICACTCM2014), pp. 14–15, Aug, 2014.
  14. M. Bhardwaj, C2 Torus New Interconnection Network Topology Based on 2D Torus, Am. J. Netw. Commun., vol. 4, no. 3, pp. 1–4, 2015.
  15. A. Punhani, Nitin, and P. Kumar, “A modified diagonal mesh interconnection network,” In: Proc. 2014 Annual IEEE India Conference (INDICON), pp. 1–6, 2014.
  16. R. Vaish, U. Shrivastava, and Nitin, On a deadlock and performance analysis of ALBR and DAR algorithm on X-Torus topology by optimal utilization of Cross Links and minimal lookups, J. Supercomput., vol. 59, no. 3, pp. 1252–1288, 2012.
  17. A. Chauhan, A. Punhani, and Nitin, “EMC2Mesh”, In: Proc. of 2015 Annual IEEE India Conference (INDICON), pp. 1–5, 2015.
  18. A. Chauhan, A. Punhani, and Nitin, “Comparative analysis of traffic patterns on centre connected topologies based on burton normal form”, In: Proc. of TENCON 2015-2015 IEEE Region 10 Conference, pp. 1–6, 2015.
  19. A. Varga and others, “The OMNeT++ discrete event simulation system,” In: Proc. of the European simulation multi conference (ESM2001), vol. 9, p. 65, 2001.
  20. A. Varga, OMNeT++, In Modelling and Tools for Network Simulation, Springer, pp. 35–59, 2010.
  21. Y. Ben-Itzhak, E. Zahavi, I. Cidon, and A. Kolodny, “HNOCS: Modular open-source simulator for Heterogeneous NoCs”, In: Proc. of 2012 Intl. Conf. on Embedded Computer Systems: Architectures, Modelling and Simulation, IC-SAMOS 2012, pp. 51–57, 2012.
  22. N. Nitin and D. S. Chauhan, Comparative analysis of Traffic Patterns on k-ary n-tree using adaptive algorithms based on Burton Normal Form, J. Supercomput., vol. 59, no. 2, pp. 569–588, 2012.
  23. P. P. Pande, C. Grecu, M. Jones, A. Ivanov, and R. Saleh, Performance evaluation and design trade-offs for network-on-chip interconnect architectures, IEEE Trans. Comput., vol. 54, no. 8, pp. 1025–1040, Aug. 2005.
  24. P. P. Pande, C. Grecu, A. Ivanov, and R. Saleh, “Design of a switch for network on chip applications”, In: Proc of 2003 Intl. symp. on Circuits and Systems, 2003. ISCAS’03., vol. 5, pp. V–217, 2003
  25. J. Duato, S. Yalamanchili, and L. M. Ni, Interconnection networks: an engineering approach, Morgan Kaufmann, 2003
  26. S. Skiena, Dijkstra’s algorithm, Implement. Discrete Math. Comb. Graph Theory Math. Read. MA Addison-Wesley, pp. 225–227, 1990.

INASS Home | Copyright@2008 The Intelligent Networks and Systems Society