Parallel Multitonic Sorting Networks.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1976
- Accession Number
- ADA024392
Entities
People
- Chung-chang Lee
- Tse-yun Feng
Organizations
- Syracuse University