language: en

*Broadcasting on Meshes with Worm-Hole Routing

Michael Barnett
Department of Computer Science University of Idaho
Moscow, Idaho 83844-1010
mbarnett@cs.uidaho.edu
David G. Payne
Supercomputer Systems Division Intel Corporation
15201 N.W. Greenbrier Pkwy Beaverton, Oregon 97006
payne@ssd.intel.com
Robert A. van de Geijn
Department of Computer Sciences The University of Texas at Austin
Austin, Texas 78712-1188
rvdg@cs.utexas.edu
Jerrell Watts
Scalable Concurrent Programming Laboratory California Institute of Technology
Pasadena, California 91125
jwatts@scp.caltech.edu

[Original Version: November 2, 1993 Revised Version: September 21, 1994]

Abstract We address the problem of broadcasting on mesh architectures with arbitrary (non-power-two) dimensions. It is assumed that such mesh architectures employ cut-through or worm-hole 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.

1 Introduction