MPI-INF/SWS Research Reports 1991-2021

# MPI-I-93-138

## Routing and sorting on circular arrays

### Sibeyn, Jop F.

#### September 1993, 20 pages.

.
##### Status: available - back from printing

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.

• MPI-I-93-138.pdf
• Attachement: MPI-I-93-138.ps (263 KBytes); MPI-I-93-138.pdf (246 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-138

BibTeX
@TECHREPORT{Sibeyn93,
AUTHOR = {Sibeyn, Jop F.},
TITLE = {Routing and sorting on circular arrays},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},