Al-Dubai, Ahmed and Ould-Khaoua, Mohamed (2001) Coded path routing: a new approach to broadcasting in 3-D meshes, Technical Report. In: 20th IEEE International Performance, Computing, and Communications Conference, April 4, 2001 - April 6, 2001, Phoenix, AZ, United states.

PDF Restricted to Registered users only Available under License Creative Commons Attribution Non-commercial. Download (731kB) | Request a copy

Abstract/Description

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.

Actions (login required)