Skip to main content
Log in

Routing on Meshes with Buses

  • Published:
Algorithmica Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

Authors

Additional information

Received May 18, 1994; revised June 23, 1995.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kaufmann, M., Raman, R. & Sibeyn, J. Routing on Meshes with Buses. Algorithmica 18, 417–444 (1997). https://doi.org/10.1007/PL00009164

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/PL00009164

Navigation