Packet routing on square meshes with row and column buses

General point-to-point communication among processors in the classical two-dimensional n×n square mesh architecture necessarily takes at least 2n-2 time steps. The authors investigate the problem of routing arbitrary permutations on an enhanced square mesh with separate broadcast buses along each of its rows and columns. They prove that any packet routing algorithm on this mesh takes Θ(2n/3) time steps. Further, they demonstrate a simple algorithm which, for any chosen 2/n⩽∈⩽1/2, routes packets in (7n/6+O (∈n)) time steps with local queue-size at most (3/∈+5)