TY - GEN
T1 - The new class of g-chain periodic sorters
AU - Becker, Ronald I.
AU - Nassimi, David
AU - Perl, Yehoshua
N1 - Publisher Copyright:
© 1993 ACM.
PY - 1993/8/1
Y1 - 1993/8/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 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).
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 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).
UR - http://www.scopus.com/inward/record.url?scp=84990189286&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84990189286&partnerID=8YFLogxK
U2 - 10.1145/165231.157378
DO - 10.1145/165231.157378
M3 - Conference contribution
AN - SCOPUS:84990189286
T3 - Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
SP - 356
EP - 364
BT - Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
PB - Association for Computing Machinery, Inc
T2 - 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
Y2 - 30 June 1993 through 2 July 1993
ER -