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 (2
n,2
n)-merging circuit
2
n 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.