ROUTING ON MESHES WITH BUSES

We consider the problem of routing packets on an n x...x n MIMD mesh-c onnected array of processors augmented with row and column buses. We g ive 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 busts, which we call t he (k, n)-routing problem. We give a general class of ''hard'' permuta tions which we use to prove lower bounds for the (k, d)-routing proble m, for all k, d greater than or equal to 1. For the (1, 1)- and (1,2)- routing problems the worst-case permutations from this class are ident ical to ones published by other authors, as are the resulting lower bo unds. However, we further show that the (1, d)-routing problem require s 0.72.n steps for d = 3, 0.76.n steps for d = 4, and slightly more th an (1 - 1/d).n steps for all d greater than or equal to 5. We also obt ain new lower bounds for the (k, d)-routing problem for k, d > 1, whic h improve on the bisection lower bound in some cases. These lower boun ds hold for off-line routing as well. We develop efficient algorithms for the (k, l)-routing problem and for the problem of routing k-random izations (where each processor has k packets initially and each packet is routed to a random destination) on the one-dimensional mesh and us e them in a general (k. d)-routing algorithm which improves considerab ly on previous results. In particular, the routing time for the (1, d) -routing problem is bounded by (2 - 1/d).n + o(n) steps with high prob ability (whp), whenever d less than or equal to n(1/2-epsilon) for som e constant epsilon > 0, and the routing time for the (k, d)-routing pr oblem is k.n/3 + o(k.n) steps whp whenever d = (k.n)(1/2-epsilon) for some constant epsilon > 0 and k greater than or equal to 3.6.d, matchi ng the bisection lower bound. We then present a simple algorithm for t he (2, 2)-routing problem running in 1.39.n + o(n) steps whp. Finally, for the important special case of routing permutations on two-dimensi onal meshes with buses, the (1,2)-routing problem, we give a more soph isticated algorithm that runs in 0.78.n + o(n) steps whp.