Parallel Multitonic Sorting Networks

This report is a study of the characteristics of multitonic sequences applied to parallel sorting networks. The main concern is the interconnections among the comparison levels of the sorting networks. A sorting network depends on various sorting algorithms and basic comparison element (BCE) impleme...

Full description

Saved in:
Bibliographic Details
Main Authors: Feng,Tse-yun, Lee,Chung-chang
Format: Report
Language:English
Subjects:
ALGORITHMS
Computer Systems
NETWORK FLOWS
PARALLEL PROCESSING
SORTING
THEOREMS
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This report is a study of the characteristics of multitonic sequences applied to parallel sorting networks. The main concern is the interconnections among the comparison levels of the sorting networks. A sorting network depends on various sorting algorithms and basic comparison element (BCE) implementation. A BCE is a device which can compare inputs and yields ordered outputs either in ascending order or in descending order. In order to facilitate analysis, the investigation is first confined to each BCE accepting two inputs only. With this restriction, sorting algorithms for parallel processing are described. Next, a new technique of graphic method is introduced, which helps the analysis of characteristics of multitonic sequences with respect to 2-sorters, and leads to the construction of perfect shuffle networks with '0' and '1' operations. Finally, the same technique of graphic method is also applied to construct perfect shuffle networks with BCE's that can accept three inputs.