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.

Cite this paper

@article{feng1976parallel,
  title = {{Parallel Multitonic Sorting Networks.}},
  author = {Feng, Tse-Yun and Lee, Chung-chang},
  journal = {Defense Technical Information Center (DTIC)},
  year = {1976}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

Related papers