The new class of g-chain periodic sorters

Ronald I. Becker, David Nassimi, Yehoshua Perl

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

A periodic sorter is a sorting network which is a cascade of a number of identical blocks, where output i of each block is input t of the next block. Previously, Dowd-Perl-Rudolph-Saks [4, 5] introduced the balanced merging network, with N = 2inputs/outputs and log N stages of comparators. Using an intricate proof, they showed that a cascade of log N such blocks constitutes a sorting network. In this paper, we introduce a large class of merging networks with the same periodic property. This class contains 22 1 networks, where N = 2is the number of inputs. The balanced merger is one network in this class. Other networks use fewer comparators. We provide a Yery simple and elegant proof of periodicity, based on the recursive structure of the networks. Our construction can also be extended to arbitrary-sized networks (not necessarily a power of 2).

Original languageEnglish (US)
Title of host publicationProceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
PublisherAssociation for Computing Machinery, Inc
Pages356-364
Number of pages9
ISBN (Electronic)0897915992, 9780897915991
DOIs
StatePublished - Aug 1 1993
Event5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993 - Velen, Germany
Duration: Jun 30 1993Jul 2 1993

Publication series

NameProceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993

Other

Other5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
CountryGermany
CityVelen
Period6/30/937/2/93

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'The new class of g-chain periodic sorters'. Together they form a unique fingerprint.

Cite this