Login
- Title:
Optimal Deterministic Sorting and Routing on Grids and Tori with Diagonals
- Document type:
- Technical Report
- Author(s):
- Manfred Kunde; Rolf Niedermeier; Klaus Reinhardt; Peter Rossmanith
- Abstract:
- 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.
- Keywords:
- mesh-connected array; parallel algorithm; sorting; routing
- Year:
- 1996
- Year / month:
- 1996-07-01 00:00:00
- Pages:
- 33
BibTeX