Friedrich-Alexander-Universität DruckenUnivisEnglish FAU-Logo
Techn. Fakultät Willkommen am Department Informatik FAU-Logo
Lehrstuhl für Informatik 12
Department Informatik  >  Informatik 12  >  Personal  >  Rolf Wanka  >  Veröffentlichungen  >  MW10

Improving Bitonic Sorting by Wire Elimination

Moritz Mühlenthaler and Rolf Wanka

Department of Computer Science
University of Erlangen-Nuremberg, Germany

Abstract. We introduce a technique called wire elimination by which it is possible to remove wires and comparators from (n,m)-merging and n-sorting circuits such that the resulting circuits are (n',m')-merging and n'-sorting circuits, resp., with n' < n, m' < m. By neatly choosing the wires to be removed, it is possible to obtain for n' and m' new circuits that have size less than circuits previously designed for n' and m'. We demonstrate this approach by eliminating from the classical Bitonic (2n,2n)-merging circuit 2n wires such that an (n,n)-merging circuit is obtained which has 1/2 n comparators less than the classical Bitonic (n,n)-merge circuit, but still the same depth. Using the usual sorting by merging technique, we get a variant of Bitonic sort which saves 1/4 n(log n-1) comparators compared to the classical variant.

Full article in PDF (204 KB) or PDF at IEEE

Copyright Notice: © 2010 VDE Verlag, Berlin, Offenbach.

Published in: Proc. 23rd PARS-Workshop on Parallel Systems and Architectures of the 23rd Int. Conf. on Architecture of Computing Systems (ARCS); pp. 15--22, 2010.

BibTex entry

  Impressum Stand: 18 January 2012.   R.W.