User: Guest  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