A Simulation Study of Scalable Broadcast in High-Performance Regular Networks

Abstract

Broadcast is an important communication operation required by many real-world applications encountered in parallel, cluster, and grid computing environments. Broadcasting on regular networks has been widely investigated in the past. However, most of the existing algorithms handle broadcast in a sequential manner and do not scale well; as a consequence, many applications cannot be efficiently supported using existing algorithms. In an effort to avoid this limitation, this article presents a new broadcast algorithm based on coded path routing. In addition to its simplicity, the proposed algorithm has shown to be capable of performing the broadcast operation in a fixed number of message-passing steps, irrespective of the network size. An extensive simulation study has been conducted to evaluate the performance of the proposed algorithm under different traffic working conditions. The analysis reveals that the new algorithm exhibits superior performance characteristics over those of the well-known recursive-doubling and extended-dominating node algorithms.

Keywords

Collective communication regular networks simulation grid and cluster computing performance analysis multicast latency

Get full access to this article

View all access options for this article.

References

[1] Al-Dubai, A. Y. , and M. Ould-Khaoua . 2001. Coded path routing: A new approach to broadcasting in 3-D meshes . In Proceedings of the 20th IEEE International Performance, Computing & Communications Conference (ICPPP’2001), April, pp. 155-162 .

[2] Barnett, M. , G. David , R. A. van de Geijn , and J. Watts . 1996. Broad-casting on meshes with wormhole routing . Journal of Parallel & Distributed Computing 35: 111-122 .

[3] Duato, J. , S.Yalamanchili , and L. Ni . 1997. Interconnection networks: An engineering approach. New York: IEEE Computer Society Press .

[4] McKinley, P. K. , H. Xu , A. Esfahanian , and L. M. Ni . 1994. Unicast-based multicast communication in wormhole-routed direct net-works . IEEE Transactions on Parallel and Distributed Systems 5 (12): 1254-1265 .

[5] Chin, T.-S. , C.-Y. Chang , and J.-P. Sheu . 2000. Efficient path-based multicast in wormhole-routed mesh networks . Journal of Systems Architecture 46: 919-930 .

[6] Ni, L. , and P. McKinley . 1993. A survey of wormhole routing techniques in direct networks . IEEE Computer 26 (2): 62-76 .

[7] Panda, D. K. , S. Singal , and R. Kesavan . 1999. Multidestination message-passing in wormhole k-ary n-cube networks with base routing conformed paths . IEEE Transactions on Parallel and Distributed Systems 10 (1): 76-96 .

[8] Schwetman, H. D. 1985. CSIM: A C-based, process-oriented simulation language. Technical report, Microelectronics and Computer Technology Corp .

[9] McKinley, P. K. , and C. Trefftz . 1993. MultiSim: A simulation tool for the study of large-scale multiprocessors . In Proceedings of MASCOTS’1993, pp. 57-62 .

10.

[10] Tseng, Y.-C. , S.-Y. Wang , and C.-W. Ho . 1999. Efficient broadcasting in wormhole-routed multicomputers: A network-partitioning approach . IEEE Transactions on Parallel and Distributed Systems 10 (1): 44-61 .

11.

[11] Tsai, Y.-J. , and P. K. McKinley . 1997. An extended dominating node approach to broadcast and global combine in multiport worm-hole routed mesh networks . IEEE Transactions on Parallel & Distributed Systems 8 (1): 41-58 .

12.

[12] McKinley, P. K. , and C. Trefftz . 1993. Efficient broadcast in all-port wormhole-routed hypercubes . In Proceedings of the International Conference on Parallel Processing, pp. 288-291 .

13.

[13] Cang, S. , and J. Wu . 2000. Time-step optimal broadcasting in 3-D meshes with minimal total communication distance . Journal of Parallel & Distributed Computing 60: 966-997 .

14.

[14] Watts, J. 1994. Efficient collective communication on multidimensional meshes with wormhole routing. Technical Report TR-94-19, Department of Computer Science, University of Texas at Austin .

15.

[15] Robinson, D. F. , P. K. McKinley , and C. Cheng . 1997. Path based multicast communication in wormhole routed unidirectional torus networks . Journal of Parallel & Distributed Computing 45: 104-121 .

16.

[16] Panda, D. K. 1995. Issues in designing efficient and practical algorithms for collective communication on wormhole routed systems . In Proceedings of the 1995 Challenges in Parallel Processing Workshop, pp. 8-15 .

17.

[17] McKinley, P. K. , Y.-J. Tsai , and D. Robinson . 1995. Collective communication in wormhole-routed massively parallel computers . IEEE Computer 28 (12): 39-50 .

18.

[18] Lin, X. , and L. M. Ni . 1991. Deadlock-free multicast wormhole routing multicomputer networks . In Proceedings of the International Symposium on Computer Architecture, pp. 116-124 .

19.

[19] Malumbres, M. P. , and J. Duato . 2000. An efficient implementation of tree-based multicast routing for distributed shared-memory multiprocessors . Journal of Systems Architecture 46: 1019-1032 .

20.

[20] Tseng, Y. , D. K. Panda , and T. Lai . 1996. A trip-based multicasting model in wormhole-routed networks with virtual channels . IEEE Transactions on Parallel & Distributed Systems 7 (2): 138-150 .

21.

[21] Obaidat, M. S. , Z. Al-Awwami , and M. Al-Mulhem . 2002. An efficient injection limitation scheme for fully adaptive routing in wormhole networks . Computer Communication 25 (11-12): 997-1008 .

22.

[22] Chien, A. A. 1998. A cost and speed model for k-ary n-cube worm-hole routers . IEEE Transactions on Parallel & Distributed Systems 9 (2): 150-162 .