Arbitrary size bitonic (ASB) sorters and their applications in broadband ATM switching

Author

Agrawal, Jagan P.

Author_Institution

Missouri Univ., Kansas City, MO, USA

fYear

1996

fDate

27-29 Mar 1996

Firstpage

454

Lastpage

458

Abstract

Bitonic sorters require that the number of inputs to the sorter N be a power of two. If N is not a power of two, the sorter size must be increased to make it a power of two nearest to N which in turn increases the sorter complexity. In this paper we propose a scheme which does not require N to be a power of two. We call it an arbitrary size bitonic (ASB) sorter. It is shown that the number of sorting elements in an ASB sorter increases slowly as the number of inputs increases from N to 2N. It has also been shown that the proposed ASB sorters can be used to significantly reduce complexity of the ATM switches which employ sorters with recirculation

Keywords

asynchronous transfer mode; broadband networks; communication complexity; electronic switching systems; multiprocessor interconnection networks; sorting; arbitrary size bitonic sorters; banyan networks; broadband ATM switching; input numbers; recirculation; sorter complexity; sorter size; sorting elements; Asynchronous transfer mode; Cities and towns; Sorting; Switches;

fLanguage

English

Publisher

ieee

Conference_Titel

Computers and Communications, 1996., Conference Proceedings of the 1996 IEEE Fifteenth Annual International Phoenix Conference on

Conference_Location

Scottsdale, AZ

Print_ISBN

0-7803-3255-5

Type

conf

DOI

10.1109/PCCC.1996.493671

Filename

493671