The two-dimensional (2D) mesh architecture with wormhole routing is an attractive interconnection architecture for distributed-memory multicomputers. A mesh can be scaled to arbitrarily large configurations while retaining high link bandwidth. Moreover, the number of nodes in a mesh does not inherently need to be a power of two, in contrast with the hypercube. However, the advent of the mesh architecture has required the rethinking of some algorithms. Although the programming model for both hypercubes and meshes with wormhole routing allow the user to assume total connectivity, many communication algorithms that do not incur network conflicts on hypercubes do incur such conflicts on meshes.
In this paper, we are concerned with the efficient implementation of broadcast algorithms on two-dimensional meshes, concentrating on the long vector case, since this is when network conflict is most noticeable. With regard to this subject, the paper makes the following contributions:
β’ It introduces techniques for avoiding network conflicts in a minimum spanning tree based broadcast. While this broadcast is clearly inferior for long vector lengths on which we focus, the results are applicable to the short vector case as well as scatter and gather operations, for which minimum spanning tree algorithms are optimal.
It must be noted that essentially these techniques were independently discovered prior to our work . Our work differentiates itself from methods based on dominating sets found in by the assumptions made about the underlying architecture. In particular, we assume that nodes are single-ported-that is, a node cannot send to or receive from more than one other node simultaneously without a performance penalty.
β’ We give an introduction to pipelined broadcast algorithms for two-dimensional meshes. We use a simple implementation to illustrate why pipelined broadcasts are not as appropriate for general purpose libraries on meshes as they are on hypercubes.
β’ We propose a new algorithm, the scatter/collect algorithm for meshes, which is a natural choice for libraries due to both its simplicity and performance.
We must emphasize that we purposely focus on the techniques more than pushing the technology to the limit. It