Manfred Kunde; Rolf Niedermeier; Klaus Reinhardt; Peter Rossmanith
Optimal Deterministic Sorting and Routing on Grids and Tori with Diagonals
We present deterministic sorting and routing algorithms for grids and tori with additional diagonal connections. For large loads (h>=12), where each processor has at most h data packets in the beginning and in the end, the sorting problem can be solved in optimal hn/6+o(n) and hn/12+o(n) steps for grids and tori with diagonals, respectively. For smaller loads we present a new concentration technique that yields very fast algorithms for h<12. For a load of 1, the theoretically most interesting case, sorting takes only 1.2n+o(n) steps and routing only 1.1n+o(n) steps. For tori we can present optimal algorithms for all loads h>=1. The above algorithms all use a constant size memory for all processors and never copy or split packets. For tori all algorithms are optimal. If packets may be copied, 1--1 sorting can be done in only in 2/3 n + o(n) on a torus with diagonals. Gaining in general a speedup of 3 by only doubling the number of communication links compared to a grid without diagonals, our work suggests to build grids and tori with diagonals.