The algorithms described in Sections 2.1
through 2.3 can be improved in several
ways. For example, by considering the expansion obtained across two
or more levels of splitters, it is possible to obtain much larger
expansion factors for randomly-wired splitter networks. In fact, it
is possible to show that even a splitter network with multiplicity *2*
can route any permutation in steps. This is not possible
to prove using the previous analysis for splitters with *d=2*, since
they do not have expansion.

One of the nice properties of a *d*-multibutterfly is that it requires
about the same VLSI layout area [28] as a *d*-dilated
butterfly. In particular, the layout area of an *N*-input
*d*-butterfly or *d*-dilated butterfly is . In
Section 2.1 we proposed appending a set of levels
numbered to the multibutterfly, each isomorphic
to the first. Unfortunately, each such level requires
area to lay out (as much as the entire
multibutterfly), so the total area becomes . For , however, it can be shown that a more area-efficient
network will suffice: the *multi-Benes* network. The
multi-Benes network consists of back-to-back multibutterflies and
requires twice the area of the multibutterfly.

Mon Jul 22 18:45:42 EDT 1996