English

# Item

ITEM ACTIONSEXPORT
Routing and sorting on circular arrays

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

Item is

show hide
Genre: Report

### Files

show Files
hide Files
:
MPI-I-93-138.pdf (Any fulltext), 246KB
Name:
MPI-I-93-138.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
-
-
-

show

### Creators

show
hide
Creators:
Sibeyn, Jop Frederic1, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

### Content

show
hide
Free keywords: -
Abstract: 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.

### Details

show
hide
Language(s): eng - English
Dates: 1993
Publication Status: Issued
Pages: 20 p.
Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
Rev. Type: -
Identifiers: Report Nr.: MPI-I-93-138
BibTex Citekey: Sibeyn93
Degree: -

show

show

show

### Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -