On the design of scalable pipelined broadcasting for mesh networks

Al-Dubai, Ahmed; Ould-Khaoua, Mohamed

Abstract

Minimising the communication latency and achieving considerable scalability are of paramount importance when designing high performance broadcast algorithms. Many 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 for the all-port mesh networks. The unique feature of the proposed algorithm is its capability of handling broadcast in only one message-passing step irrespective of the network size. Results from a comparative analysis and simulation reveal that the proposed algorithm exhibits superior performance characteristics over those of the well-known Recursive Doubling, Extending Dominating Node and Network Partitioning algorithms

• Conference Name: 16th Annual International Symposium on High Performance Computing Systems and Applications, 2002. Proceedings.
• Start Date: Jun 16, 2002
• End Date: Jun 19, 2002
• Publication Date: Aug 7, 2002
• Deposit Date: Dec 15, 2009
• Publicly Available Date: Dec 15, 2009
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Pages: 98-105
• Book Title: High Performance Computing Systems and Applications
• ISBN: 0-7695-1626-2
• DOI: https://doi.org/10.1109/HPCSA.2002.1019140
• Keywords: multiprocessor interconnection networks; parallel algorithms; pipeline processing; all-port mesh networks; broadcast algorithm; communication latency; message-passing parallel algorithms; scalability
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/3563
• Publisher URL: http://dx.doi.org/10.1109/HPCSA.2002.1019140
• Contract Date: Dec 15, 2009