TY - GEN
T1 - Generalized class of g-chain periodic sorting networks
AU - Nassimi, David
AU - Perl, Yehoshua
AU - Becker, Ronald I.
PY - 1994
Y1 - 1994
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
AN - SCOPUS:0027929278
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 -