Generalized class of g-chain periodic sorting networks

David Nassimi, Yehoshua Perl, Ronald I. Becker

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

4 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 i of the next block. Previously, Dowd-Perl-Rudolph-Saks [5, 6] introduced by balanced merging network, with N =2k inputs/ outputs and logN stages of comparators. Using an intricate proof, they showed that a cascade of logN such blocks constitutes a sorting network. Recently (SPAA'93), we introduced a class of merging networks with N = 2k inputs/outputs and with periodic property [3]. In this paper, we extend our class of merging networks to arbitrary size N. For each N, the class contains an exponentially large number of merging networks (about 2N/2-1) with [log N] stages.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Parallel Processing
PublisherPubl by IEEE
Pages424-432
Number of pages9
ISBN (Print)0818656026
StatePublished - Jan 1 1994
EventProceedings of the 8th International Parallel Processing Symposium - Cancun, Mex
Duration: Apr 26 1994Apr 29 1994

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

OtherProceedings of the 8th International Parallel Processing Symposium
CityCancun, Mex
Period4/26/944/29/94

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Generalized class of g-chain periodic sorting networks'. Together they form a unique fingerprint.

Cite this