Broadcasting on meshes with wormhole routing

We address the problem of broadcasting on two-dimensional mesh architectures with an arbitrary (non-power-of-two) number of nodes in each dimension, It is assumed that such mesh architectures employ cut-through or wormhole routing, The primary focus is on avoiding network conflicts in the various proposed algorithms, We give algorithms for performing a conflict-free minimum-spanning tree broadcast, a pipelined algorithm that is similar to Ho and Johnsson's EDST algorithm for hypercubes, and a novel scatter-collect approach that is a natural choice for communication libraries due to its simplicity. Results obtained on the Intel Paragon system are included. (C) 1996 Academic Press, Inc.