Efficient randomized routing algorithms on the two-dimensional mesh of buses

The mesh of buses (MBUS) is a parallel computation model which consists of n x n processors, II row buses and n column buses but no local connections between two neighboring processors. As for deterministic (permutation) rout ing on MBUSs, the known 1.5n upper bound appears to be hard to improve. Als o, the information theoretic lower bound for any type of MBUS routing is 1. 0n. In this paper, we present two randomized algorithms for MBUS routing. O ne of them runs in 1.4375n + o(n) steps with high probability. The other ru ns 1.25n + o(n) steps also with high probability but needs more local compu tation. (C) 2001 Elsevier Science B.V. All rights reserved.