Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


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.
References to related material:

MPI-I-93-138.pdfMPI-I-93-138.pdfMPI-I-93-138.ps263 KBytes; 246 KBytes
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Sibeyn, Jop F.},
  TITLE = {Routing and sorting on circular arrays},
  TYPE = {Research Report},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-93-138},
  MONTH = {September},
  YEAR = {1993},
  ISSN = {0946-011X},