Abstract
This paper addresses the issue of multicast communication in scalable interconnection networks, using path-based scheme. Most existing multicast algorithms either assume a fixed network size, low dimensional networks or only consider the latency at the network level. As a consequence, most of these algorithms implement multicast in a sequential manner and can not scale well with the network dimensions or the number of nodes involved. Furthermore, most of these algorithms handle multicast communication with low throughput. In this paper, we propose a multicast algorithm for multidimensional interconnection networks, which is built upon our Qualified Groups QG multicast scheme for ensuring efficient communication irrespective of the network sizes/dimensions or the number of the destination nodes. Unlike the existing works, this study considers the scalability and latency at both the network and node levels so as to achieve a high degree of parallelism. Our results show that the proposed algorithm considerably improves the multicast message delivery ratio, throughput and scalability.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Wang, N.-C., Yen, C.-P., Chu, C.-P.: Multicast communication in wormhole-routed symmetric networks with hamiltonian cycle model. Journal of Systems Architecture 51(3), 165–183 (2005)
Al-Dubai, A., Ould-Khaoua, M., Mackenzie, L.: An efficient path-based multicast algorithm for mesh networks. In: Proc. the 17th Int. Parallel and Distributed Processing Symposium (IEEE/ACM-IPDPS), Nice, France, April 22 -26, pp. 283–290 (2003)
Duato, J., Yalamanchili, C., Ni, L.: Interconnection networks: an engineering approach. Elsevier Science, Amsterdam (2003)
Touzene, A.: Optimal all-ports collective communication algorithms for the k-ary n-cube interconnection networks. Journal of Systems Architecture 50(4), 169–236 (2004)
Chen, Y.-S., Chiang, C.-Y., Chen, C.-Y.: Multi-node broadcasting in all-ported 3-D wormhole-routed torus using an aggregation-then-distribution strategy. Journal of Systems Architecture 50(9), 575–589 (2004)
McKinley, P.K., Trefftz, C.: MultiSim: A simulation tool for the study of large-scale multiprocessors. In: MASCOTS 1993. Proceedings of the Int. Symp. Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 57–62 (1993)
CSIM: A C-based, process-oriented simulation language, http://www.mesquite.com/
Fleury, E., Fraigniaud, P.: Strategies for path-based multicasting in wormhole-routed meshes. J. Parallel & Distributed Computing 60, 26–62 (1998)
Tseng, Y.-C., Wang, S.-Y., Ho, C.-W.: Efficient broadcasting in wormhole-routed multicomputers: A network-partitioning approach. IEEE Transactions on Parallel and Distributed Systems 10(1), 44–61 (1999)
Lin, X., McKinley, P., Ni, L.M.: Deadlock-free multicast wormhole routing in 2D-mesh multicomputers. IEEE Transactions on Parallel and Distributed Systems 5(8), 793–804 (1994)
Bjerregaard, T., Mahadevan, S.: A survey of research and practices of Network-on-Chip. ACM Computing Surveys 38, 1–51 (2006)
Robinson, D.F., McKinley, P.K., Cheng, C.: Path based multicast communication in wormhole routed unidirectional torus networks. Journal of Parallel Distributed Computing 45, 104–121 (1997)
Malumbres, M.P., Duato, J.: An efficient implementation of tree-based multicast routing for distributed shared-memory multiprocessors. J. Systems Architecture 46, 1019–1032 (2000)
Mohapatra, P., Varavithya, V.: A hardware multicast routing algorithm for two dimensional meshes. In: The Eighth IEEE Symposium on Parallel and Distributed Processing, News Orleans, pp. 198–205 (1996)
Boppana, R.V., Chalasani, S., Raghavendra, C.S.: Resource deadlock and performance of wormhole multicast routing algorithms. IEEE Transactions on Parallel and Distributed Systems 9(6), 535–549 (1998)
Wang, S., Tseng, Y., Shiu, C., Sheu, J.: Balancing traffic load for multi-node multicast in a wormhole 2D torus/mesh. The Computer Journal 44(5), 354–367 (2001)
Kumar, D.R., Najjar, W.A., Srimani, P.K.: A new adaptive hardware tree-based multicast routing in k-ary n-cubes. IEEE Computer 50(7), 647–659 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Al-Dubai, A., Ould-Khaoua, M., Romdhani, I. (2007). Design and Analysis of Multicast Communication in Multidimensional Mesh Networks. In: Stojmenovic, I., Thulasiram, R.K., Yang, L.T., Jia, W., Guo, M., de Mello, R.F. (eds) Parallel and Distributed Processing and Applications. ISPA 2007. Lecture Notes in Computer Science, vol 4742. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74742-0_77
Download citation
DOI: https://doi.org/10.1007/978-3-540-74742-0_77
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74741-3
Online ISBN: 978-3-540-74742-0
eBook Packages: Computer ScienceComputer Science (R0)