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

AbstractThe mesh of buses (MBUS) is a parallel computation model which consists of n×n processors, n row buses and n column buses but no local connections between two neighboring processors. As for deterministic (permutation) routing on MBUSs, the known 1.5n upper bound appears to be hard to improve. Also, 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. One of them runs in 1.4375n+o(n) steps with high probability. The other runs 1.25n+o(n) steps also with high probability but needs more local computation