ISSN:
1432-0541
Keywords:
Key words. Parallel computation, Algorithms, Packet routing, Meshes, Buses, Lower bounds, Randomization, Coloring.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. We consider the problem of routing packets on an $n\times\cdots\times n$ MIMD mesh-connected array of processors augmented with row and column buses. We give lower bounds and randomized algorithms for the problem of routing k-permutations (where each processor is the source and destination of exactly k packets) on a d-dimensional mesh with buses, which we call the (k,d)-routing problem. We give a general class of ``hard'' permutations which we use to prove lower bounds for the (k,d)-routing problem, for all k,d≥ 1. For the (1,1)- and (1,2)-routing problems the worst-case permutations from this class are identical to ones published by other authors, as are the resulting lower bounds. However, we further show that the (1,d)-routing problem requires 0.72 ... n steps for d=3, 0.76 ... n steps for d=4, and slightly more than $(1-1/d)\cdot n$ steps for all d≥ 5. We also obtain new lower bounds for the (k,d)-routing problem for k,d 〉 1, which improve on the bisection lower bound in some cases. These lower bounds hold for off-line routing as well. We develop efficient algorithms for the (k,1)-routing problem and for the problem of routing k-randomizations (where each processor has k packets initially and each packet is routed to a random destination) on the one-dimensional mesh and use them in a general (k,d)-routing algorithm which improves considerably on previous results. In particular, the routing time for the (1,d)-routing problem is bounded by $(2-1/d) \cdot n + o(n)$ steps with high probability (whp), whenever $d\leq n^{1/2-\epsilon}$ for some constant ε 〉 0, and the routing time for the (k,d)-routing problem is $k\cdot n/3+o(k\cdot n)$ steps whp whenever $d=(k\cdot n)^{1/2-\epsilon}$ for some constant ε 〉 0 and k≥ 3.6 ... d, matching the bisection lower bound. We then present a simple algorithm for the (2,2)-routing problem running in 1.39 ... n+o(n) steps whp. Finally, for the important special case of routing permutations on two-dimensional meshes with buses, the (1,2)-routing problem, we give a more sophisticated algorithm that runs in 0.78 ... n+o(n) steps whp.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009164
