A Pipelined Broadcast for Multidimensional Meshes

We address the problem of performing a pipelined broadcast on a mesh architecture. Meshes require a different approach than other topologies, and their very nature puts a tighter bound on the performance that one can hope to achieve. By using the appropriate techniques, however, one can obtain excellent performance for sufficiently long messages. The resulting algorithm will work on meshes of any dimension with any number of nodes. Our model assumes that the mesh is a torus and/or that it has bidirectional links and uses wormhole routing. Performance data from the Cray T3D are included. Keywords: broadcast, pipelining, communication, mesh, torus 1. Introduction The broadcast is a fundamental routine in any communication library. As a result, its implementation should be as efficient as possible. To that end, no single algorithm will suffice: A routine which minimizes the number of message operations will perform well for short messages, when start-up latencies are the primary time c..