Packet routing on square meshes with row and column buses
Joseph Y.‐T. Leung, Sunil M. Shende · 2002
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 Theta (2n/3) time steps. Further, they demonstrate a simple algorithm which, for any chosen 2/n>