A plane-based broadcast algorithm for multicomputer networks

Al-Dubai, Ahmed; Ould-Khaoua, Mohamed; Mackenzie, Lewis

Abstract

Maximising the performance of parallel systems requires matching message-passing algorithms and application characteristics with a suitable underling interconnection network. 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 techniques. Motivated by these observations, this paper presents a new efficient broadcast algorithm for the mesh, called the Plane-Based (PB) algorithm. The main feature of this approach is its ability to perform broadcast operation with a high degree of scalability and parallelism. Furthermore, performance is insensitive to the network size, i.e., only three message-passing steps are required to implement a broadcast operation irrespective of the network size. Results from a comparative analysis demonstrate that the PB algorithm exhibits superior performance characteristics over those of the well-known Recursive Doubling and Extending Dominating Node algorithms.

• Journal Article Type: Article
• Publication Date: 2005-10
• Deposit Date: Apr 8, 2008
• Print ISSN: 1383-7621
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 51
• Issue: 10-11
• Pages: 617-632
• DOI: https://doi.org/10.1016/j.sysarc.2005.01.003
• Keywords: Computing; Parallel systems; Performance enhancement; Broadcast algorithms; Worm-hole switching; Plane based algorithm; Evaluation
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/1817
• Publisher URL: http://dx.doi.org/10.1016/j.sysarc.2005.01.003