Authors

null Jaehyung Park, null Hyun Gon Kim, null Seungtaek Hwang, null Jinsoo Kim, null Ikhyeon Jang, null Hyunsoo Yoon, null Jung Wan Cho

Abstract

In this paper, we study multiport wormhole routed multicomputers where nodes are able to send multiple messages into the network at a time. Moreover, we discuss the Hamiltonian-path routing in wormhole-routed mesh/torus networks. We propose efficient unicast-based multicast algorithms in multiport wormhole-routed multicomputers which are characterized by 2D mesh/torus topology and Hamiltonian path routing. The proposed multiport multicast algorithms exploit the distance-insensitive properly of wormhole routing technology. The two-port multicast algorithm can deliver a multicast message to m destinations in at most [log/sub 3/(m+1)]+1 message-passing steps, avoiding contention among the constituent unicast messages. This paper analyzes the performance of the proposed multicast algorithm in wormhole-routed mesh networks with two-port communication architecture. It also shows that its performance is enhanced by log/sub 2/ 3 over one-port multicast algorithm in terms of multicast latency. The proposed multicast algorithms are easily applicable to wormhole-routed torus networks.

Citation

  • Journal: Proceedings of 1996 IEEE Second International Conference on Algorithms and Architectures for Parallel Processing, ICA/sup 3/PP ‘96
  • Year: 2002
  • Volume:
  • Issue:
  • Pages: 326–331
  • Publisher: IEEE
  • DOI: 10.1109/icapp.1996.562892

BibTeX

@inproceedings{Jaehyung_Park,
  series={ICAPP-96},
  title={{An efficient unicast-based multicast algorithm in two-port wormhole-routed 2D mesh networks}},
  DOI={10.1109/icapp.1996.562892},
  booktitle={{Proceedings of 1996 IEEE Second International Conference on Algorithms and Architectures for Parallel Processing, ICA/sup 3/PP ’96}},
  publisher={IEEE},
  author={Jaehyung Park and Hyun Gon Kim and Seungtaek Hwang and Jinsoo Kim and Ikhyeon Jang and Hyunsoo Yoon and Jung Wan Cho},
  pages={326--331},
  collection={ICAPP-96}
}

Download the bib file

References

  • park, Ah Efficient Software Multicast Algorithm in Two-Port Wormhole-Routed MultiComputers. ICPADS (1996)
  • Robinson, D. F., Judd, D., McKinley, P. K. & Cheng, B. H. C. Efficient collective data distribution in all-port wormhole-routed hypercubes. Proceedings of the 1993 ACM/IEEE conference on Supercomputing - Supercomputing ’93 792–801 (1993) doi:10.1145/169627.169837 – 10.1145/169627.169837
  • Robinson, D., McKinley, P. & Cheng, B. Optimal Multicast Communication in Wormhole-Routed Torus Networks. 1994 International Conference on Parallel Processing (ICPP’94) 134–141 (1994) doi:10.1109/icpp.1994.142 – 10.1109/icpp.1994.142
  • xu, Efficient implementation of barrier synchronization in wormhole-routed hypercube multicomputers (1991)
  • kumar, Scalability of Parallel Algorithms for the All-Pairs Shortest Path Problem (1991)
  • Dally, W. J. & Seitz, C. L. The torus routing chip. Distrib Comput 1, 187–196 (1986) – 10.1007/bf01660031
  • Xiaola Lin, McKinley, P. K. & Ni, L. M. Deadlock-free multicast wormhole routing in 2-D mesh multicomputers. IEEE Trans. Parallel Distrib. Syst. 5, 793–804 (1994) – 10.1109/71.298203
  • li, A Hypercube Shared Virtual Memory. ICPP (1989)
  • mckinley, A Survey of Collective Communication in Wormhole-Routed Massively Parallel Computers (1994)
  • McKinley, P. K., Xu, H., Esfahanian, A.-H. & Ni, L. M. Unicast-based multicast communication in wormhole-routed networks. IEEE Trans. Parallel Distrib. Syst. 5, 1252–1265 (1994) – 10.1109/71.334899
  • Bar-Noy, A., Bruck, J., Ho, C.-T., Kipnis, S. & Schieber, B. Computing global combine operations in the multi-port postal model. Proceedings of 1993 5th IEEE Symposium on Parallel and Distributed Processing 336–343 doi:10.1109/spdp.1993.395514 – 10.1109/spdp.1993.395514
  • Athas, W. C. & Seitz, C. L. Multicomputers: message-passing concurrent computers. Computer 21, 9–24 (1988) – 10.1109/2.73
  • Ni, L. M. & McKinley, P. K. A survey of wormhole routing techniques in direct networks. Computer 26, 62–76 (1993) – 10.1109/2.191995