Systolic Sorting on a Mesh-Connected Network

Author

Lang, Hans-werner ; Schimmler, Manfred ; Schmeck, Hartmut ; Schröder, Heiko

Author_Institution

Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität Kiel

Issue

7

fYear

1985

fDate

7/1/1985 12:00:00 AM

Firstpage

652

Lastpage

658

Abstract

A parallel algorithm for sorting n data items in O(n) steps is presented. Its simple structure and the fact that it needs local communication only make it suitable for an implementation in VLSI technology. The algorithm is based on a merge algorithm that merges four subfiles stored in a mesh-connected processor array. This merge algorithm is composed of the perfect shuffle and odd-even-transposition sort. For the VLSI implementation a systolic version of the algorithm is presented. The area and time complexities for a bit-serial and a bit-parallel version of this implementation are analyzed.

Keywords

Odd-even-transposition sort; VLSI algorithms; VLSI complexity; mesh-connected processor array; perfect shuffle; sorting; systolic array; Algorithm design and analysis; Computational modeling; Data flow computing; Parallel algorithms; Pipeline processing; Registers; Routing; Sorting; Systolic arrays; Very large scale integration; Odd-even-transposition sort; VLSI algorithms; VLSI complexity; mesh-connected processor array; perfect shuffle; sorting; systolic array;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/TC.1985.1676603

Filename

1676603