TY - GEN

T1 - Generalized class of g-chain periodic sorting networks

AU - Nassimi, David

AU - Perl, Yehoshua

AU - Becker, Ronald I.

PY - 1994/1/1

Y1 - 1994/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027929278&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027929278&partnerID=8YFLogxK

M3 - Conference contribution

SN - 0818656026

T3 - Proceedings of the International Conference on Parallel Processing

SP - 424

EP - 432

BT - Proceedings of the International Conference on Parallel Processing

PB - Publ by IEEE

T2 - Proceedings of the 8th International Parallel Processing Symposium

Y2 - 26 April 1994 through 29 April 1994

ER -