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 -