Nearly optimal algorithms for broadcast on d-dimensional all-port and wormhole-routed torus

摘要

We present nearly optimal algorithms for broadcast on a d-dimensional n/spl times x...x n torus that supports all-port communication and wormhole routing. Let T(n) denote the number of communication steps performed to broadcast a message. We present algorithms that achieve the following performance: (i) T(n)=d[log/sub 2d+1]+1 when n is odd, and (ii) T(n)=d[log/sub 2d+1/(n-1)]+[d/2]+1 when n is even. The lower bound is [dlog/sub 2d+1]. Our algorithm is the first one that works for arbitrary n, and is optimal up to the constant term. Previous algorithms with comparable performance only work for the case that either d is 2 or 3, or n is a power of 2d+1. For special cases such as d=2 or 3, we can improve the algorithm so that T(n)=d[log/sub 2d+1] for any n.