Research Output

Towards a scalable broadcast in wormhole-routed mesh networks

  Broadcast algorithms for wormhole--switched meshes have been widely reported in the literature. However, most of these
algorithms handle broadcast in a sequential manner and do not scale well with the network size. As a consequence, many parallel applications cannot be efficiently supported using existing algorithms. Motivated by these observations, this paper presents a new broadcast algorithm based on our previously proposed Coded Path Routing (or CPR for short) [I]. The main feature of the proposed algorithm lies in its ability to perform broadcast operations with a high degree of parallelism. Furthermore, its performance is insensitive to the network size, i.e., only two message-passing steps are required to implement a broadcast operation irrespective of the network size. Results from a comparative analysis reveal that the new algorithm exhibits superior performance characteristics over those of the well-known Recursive Doubling, Extending Dominating Node and Network
Partitioning algorithms.

  • Type:

    Book Chapter

  • Date:

    30 November 2001

  • Publication Status:

    Published

  • Publisher

    ACM

  • DOI:

    10.1145/508791.508955

  • Library of Congress:

    QA75 Electronic computers. Computer science

Citation

Al-Dubai, A., Ould-Khaoua, M. & Mackenzie, L. (2001). Towards a scalable broadcast in wormhole-routed mesh networks. In Proceedings of the 2002 ACM symposium on Applied computing, 840-844. ACM. doi:10.1145/508791.508955. ISBN 1-58113-445-2

Authors

Keywords

Interconnection networks; routing; wormhole switching; collective communication; communication latency

Available Documents