A COMPARISON OF MESHES WITH STATIC BUSES AND HALF-DUPLEX WRAP-AROUNDS
Danny Kriz̧anc, Sanguthevar Rajasekaran, Sunil M. Shende · Parallel Processing Letters · 1993
We investigate the relative computational powers of a mesh with static buses and a mesh with half-duplex wrap-arounds. The latter model is like a torus, except that any wrap-around link of the architecture can only transmit data in one of the two directions at any clock tick. We show that the permutation routing problem can be solved as efficiently on a linear array augmented with a half-duplex wrap-around link, as on a linear array with an augmented broadcast bus. We also present a routing algorithm for a two-dimensional (2D) mesh with half-duplex wrap-around links whose run time is close to that of the best known algorithm for routing on a 2D mesh with broadcast buses in each dimension. In addition, we show that on an n×n 2D mesh with broadcast buses, randomized sorting of n2 elements can be accomplished in time that is only o(n) more, with high probability, than the time needed for permutation routing.