Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Routing and sorting on circular arrays


Sibeyn,  Jop Frederic
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Any fulltext), 246KB

Supplementary Material (public)
There is no public supplementary material available

Sibeyn, J. F.(1993). Routing and sorting on circular arrays (MPI-I-93-138). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B428-E
We analyze routing and sorting problems on circular processor arrays with bidirectional connections. We assume that initially and finally each PU holds $k \geq 1$ packets. On linear processor arrays the routing and sorting problem can easily be solved for any $k$, but for the circular array it is not obvious how to exploit the wrap-around connection. We show that on an array with $n$ PUs $k$-$k$ routing, $k \geq 4$, can be performed optimally in $k \cdot n / 4 + \sqrt{n}$ steps by a deterministical algorithm. For $k = 1$, the routing problem is trivial. For $k = 2$ and $k = 3$, we prove lower-bounds and show that these (almost) can be matched. A very simple algorithm has good performance for dynamic routing problems. For the $k$-$k$ sorting problem we use a powerful algorithm which also can be used for sorting on higher-dimensional tori and meshes. For the ring the routing time is $\max\{n, k \cdot n / 4\} + {\cal O}((k \cdot n)^{2/3})$ steps. For large $k$ we take the computation time into account and show that for $n = o(\log k)$ optimal speed-up can be achieved. For $k < 4$, we give specific results, which come close to the routing times.