next up previous
Next: 3 Routing around faults Up: 2 Routing without faults Previous: 2.3 Improving the constant

2.4 Other improvements


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 tex2html_wrap_inline1911 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 tex2html_wrap_inline1925 . In Section 2.1 we proposed appending a set of levels numbered tex2html_wrap_inline1927 to the multibutterfly, each isomorphic to the first. Unfortunately, each such level requires tex2html_wrap_inline1929 area to lay out (as much as the entire multibutterfly), so the total area becomes tex2html_wrap_inline1931 . For tex2html_wrap_inline1933 , 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.

Bruce Maggs
Mon Jul 22 18:45:42 EDT 1996