CFP last date
21 October 2024
Reseach Article

BTL - An Efficient Deadlock-Free Multicast Wormhole Algorithm to Optimize Traffic in 2D Torus Multicomputers

by Kadry Hamed, Mohamed A. El-sayed
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 111 - Number 6
Year of Publication: 2015
Authors: Kadry Hamed, Mohamed A. El-sayed
10.5120/19546-1415

Kadry Hamed, Mohamed A. El-sayed . BTL - An Efficient Deadlock-Free Multicast Wormhole Algorithm to Optimize Traffic in 2D Torus Multicomputers. International Journal of Computer Applications. 111, 6 ( February 2015), 32-37. DOI=10.5120/19546-1415

@article{ 10.5120/19546-1415,
author = { Kadry Hamed, Mohamed A. El-sayed },
title = { BTL - An Efficient Deadlock-Free Multicast Wormhole Algorithm to Optimize Traffic in 2D Torus Multicomputers },
journal = { International Journal of Computer Applications },
issue_date = { February 2015 },
volume = { 111 },
number = { 6 },
month = { February },
year = { 2015 },
issn = { 0975-8887 },
pages = { 32-37 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume111/number6/19546-1415/ },
doi = { 10.5120/19546-1415 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:47:11.817359+05:30
%A Kadry Hamed
%A Mohamed A. El-sayed
%T BTL - An Efficient Deadlock-Free Multicast Wormhole Algorithm to Optimize Traffic in 2D Torus Multicomputers
%J International Journal of Computer Applications
%@ 0975-8887
%V 111
%N 6
%P 32-37
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Multicast communication, in which the same message is sending from a source node to a set of destination nodes, is being increasingly demanded in multicomputer systems. It can be used to support several other collective communication operations. 2D torus network has many features. So, it has become increasingly important to multicomputer design. This paper presents an efficient multicast wormhole deadlock-free algorithm that Balance Traffic Load on 2D torus network; hence the name BTL algorithm. BTL algorithm handles multicast operation with a fixed number of message-passing steps irrespective of the network size. Also, it is designed such that can send messages to any number of destinations within two communication phases. Results from extensive comparative analysis show that BTL algorithm exhibit superior performance advantages over a well-known algorithm.

References
  1. Dally, W. J. , and Seitz, C. L. 1986. The torus routing chip. Journal of Distributed Computing 1 (3) 187-196.
  2. Darwish, M. G. , Radwan, A. A. A. , Abd El-Baky, M. A. , and Hamed, Kadry. 2008. TTPM-An Efficient Deadlock-Free Algorithm for Multicast communication in 2D Torus Networks. Journal of Systems Architecture, (October 2008) Volume 54, Issue 10, 919-928.
  3. Wang, Neng-Chung and Hung, Yi-Ping. 2009. Multicast communication in wormhole-routed 2D torus networks with hamiltonian cycle model. Journal of System Architecture 55, 70-78.
  4. Robinson, D. F. , McKinley, P. K. , and Cheng, B. H. C. 1995. Optimal Multicast Communication in Wormhole-Routed Torus Networks. IEEE Trans. Parallel and Distributed Systems, (Oct. 1995), vol. 6, no. 10, 1029-1042.
  5. Cray Research Inc, 2005. CRAY XT3 scalable parallel processing system. Cray Research Inc. , Website: http://www. cray. com/products/xt3/index. html
  6. Fowler, A. , Mariantoni, M. , Martinis, J. , and Cleland, A. 2012. A primer on surface codes: Developing a machine language for a quantum computer. arXiv:1208. 0928.
  7. Devitt, S. J. , Nemoto, K. , and Munro, W. J. 2013. Quantum error correction for beginners. Reports on Progress in Physics. (Aug. 2013), 76, 8.
  8. Ni, L. M. , and McKinley, P. K. 1993. A survey of routing techniques in wormhole Networks. IEEE Computer, (Feb. 1993), vol. 26, no. 2, 62-76.
  9. Darwish, M. G. , Radwan, A. A. A. , Abd El-Baky, M. A. , and Hamed, Kadry. 2010. T2W:A Multicast Routing Algorithm For 2D Torus Networks with Horizontal Main Path Model. International Journal of Intelligent Computing and Information Science, (July 2010), v. 10, no. 2.
  10. Moharam, H. , Abd El-Baky, M. A. , and Nassar, S. M. M. 2000. YOMNA-An efficient deadlock-free multicast wormhole algorithm in 2-D mesh multicomputers. Journal of Systems Architecture, (October 2000), Volume 46, Issue 12, 1073-1091.
  11. El-Obaid, Amnah and Li-Zuo, Wan. 2008. An Efficient Path-Based Multicast Algorithm for Minimum Communication Steps. Inform. Technol. J. , 7(1): 32-39.
  12. Moosavi, S. R. , Rahmani, A. -M. , Liljeberg, P. , Plosila, J. , and Tenhunen, H. 2013. An Efficient Implementation of Hamiltonian Path Based Multicast Routing for 3D Interconnection Networks. 21st Iranian Conference on Electrical Engineering, (May 2013), (ICEE), p(6).
  13. Mckinley, P. , Xu, H. , Esfahanian, A-H. , and Ni, L. 1994. Unicast-Based Multicast Communication in Wormhole-Routed Networks. IEEE Trans. on Parallel and Distributed Systems, (Dec. 1994), vol. 5, no. 12, 1252-1265.
  14. Malumbres, M. P. , Duato, J. , and Torrellas, J. 1996. An Efficient Implementation of Tree-Based Multicast Routing for Distributed Shared-Memory Multiprocessors. Proc. Of the 8th IEEE Symp. On Parallel and Distributed Processing, (Oct. 1996), 186-189.
  15. Wang, Honge and Blough, Douglas M. 1998. Tree-Based Multicast in Wormhole-Routed Torus Networks. International Conference on Parallel and Distributed Processing Techniques and Applications. 702-709.
  16. Wang, Nen-Chung and Chu, Chih-Ping. 2005. An Efficient Tree-Based Multicasting Algorithm on Wormhole-Routed Star Graph Interconnection Networks Embedded with Hamiltonian Path. The Journal of Supercomputing 34(1), 5-26.
  17. Wang, Nen-Chung. , Chen, Young-Long. , Chen, Chin-Ling. , Chen, Ying-Shiou. 2011. A Dual-Tree-Based On-Demand Multicast Routing Protocol for Mobile Ad Hoc Networks. SNPD, 128-132.
  18. Lin, X. , McKinley, P. K. , and Ni, L. M. 1994. Deadlock-free multicast wormhole routing in 2D mesh multicomputers. IEEE Transactions on Parallel and Distributed Systems, (August 1994), vol. 5, 793-804.
  19. Darwish, M. G. , Radwan, A. A. A. , Abd El-Baky, M. A. , and Hamed, Kadry. 2010. Ready Groups: A Path-Based Multicast Algorithm for 2D Torus Networks. The 7th International Conference on Informatics and Systems (March 2010), (INFOS 2010) - 28-30.
  20. Lin, X. , McKinley, P. K. , and . Ni, L. M. 1994. Deadlock-free multicast wormhole routing in 2D mesh multicomputers. IEEE Transactions on Parallel and Distributed Systems, (August 1994), vol. 5, 793-804.
  21. Darwish, M. G. , Radwan, A. A. A. , Abd El-Baky, M. A. , and Hamed, Kadry. 2005. GTTPM – An Efficient Deadlock-Free Multicast Wormhole Algorithm For Communication In 2D Torus Multicomputers. In proceeding of the 17th IASTED International Conference Parallel and Distributed Computing and Systems, Phoenix, AZ, USA, November 14-16, 2005.
  22. Oral, S. and George, A. 2003. Multicast Performance Modeling and Evaluation for High-Speed Unidirectional Torus Networks. HCS Research Lab, U. of Florida, submitted (June 2003).
Index Terms

Computer Science
Information Sciences

Keywords

Deadlock-Free Multicast communication 2D torus topology Multicomputer.