# MPI-I-93-138

## Routing and sorting on circular arrays

### Sibeyn, Jop F.

**MPI-I-93-138**. September** **1993, 20 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-93-138.pdf | 263 KBytes; 246 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://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},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-93-138},`

` MONTH = {September},`

` YEAR = {1993},`

` ISSN = {0946-011X},`

`}`