Coded path routing: a new approach to broadcasting in 3-D meshes, Technical Report

Al-Dubai, Ahmed; Ould-Khaoua, Mohamed

Abstract

Broadcast is an important collective communication operation required by many real-world parallel applications. This paper proposes the Coded Path Routing (or CPR for short) as a new approach for designing efficient broadcast algorithms for wormhole-switched multicomputer networks. A unique feature of the CPR is that a message can be delivered to an arbitrary number of destination nodes with single start-up latency. The CPR is then used to devise a new broadcast algorithm for the all-port 3-dimensional mesh. The algorithm requires a fixed number of message-passing steps to implement a broadcast operation irrespective of the network size. Results from an extensive comparative analysis reveal that the proposed algorithm exhibits superior performance characteristics over those of the well-known Recursive Doubling and Extending Dominating Node algorithms.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: 20th IEEE International Performance, Computing, and Communications Conference
• Start Date: Apr 4, 2001
• End Date: Apr 6, 2001
• Online Publication Date: Aug 7, 2002
• Publication Date: Aug 7, 2002
• Deposit Date: Dec 1, 2009
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Pages: 155-162
• Book Title: Conference Proceedings of the 2001 IEEE International Performance, Computing, and Communications Conference (Cat. No.01CH37210)
• ISBN: 0780370015
• DOI: https://doi.org/10.1109/IPCCC.2001.918648
• Keywords: Broadcasting; 3-d meshes; interconnection networks; wormhole switching; performance analysis; coded path routing
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/3572