Optimal Broadcasting in Mesh-Connected Architectures
Michael D. Barnett, David G. Payne, Robert A. Geijn · 1991
In this paper, we disprove the common assumption that the time for broadcasting in a mesh is at best proportional to the square root of the number of processors, at least in the presence of worm-hole routing. We present an optimal algorithm for broadcasting in mesh-connected distributed-memory architectures with worm-hole routing. By organizing the processing nodes in a logical spanning tree, the algorithm executes in time proportional to the logarithm of the number of nodes without inducing contention in the communication network. We restrict the number of nodes in each dimension of the processor mesh to be a power of two. Our method provides insight into how to avoid and/or reduce network contention on meshes for other communication operations. Experimental results on the Intel Touchstone Delta system are included. Keywords: distributed-memory, mesh-connected, broadcast, parallel processing, worm-hole routing 1 Introduction We investigate broadcast algorithms for mesh-co...