Improved routing and sorting on multibutterflies
Bruce MacDowell Maggs, Berthold Vöcking · 1997
IntroductionThis paper shows that an N-node AKS network (as described by Paterson) can be embedded in a ~-node degree-8 multibutterfly network with load 1, congestion 1, and dilation 2. The result has several implications, including the first deterministic algorithms for sorting and finding the median of n logn keys on an n-input multibuttertly in O(log n) time, a work-efficient deterministic algorithm for finding the median of n logz n log log n keys on an n-input multibutterfly in O(log n log log n) time, and a three-dimensional VLSI layout for the n-input AKS network with volume 0(n3/2).While these algorithms are not practical, they provide further evidence of the robustness of multibutterfly networks.We also present a separate, and more practical, deterministic algorithm for routing h relations on an n-input multibutterfly in O(h + log n) time.Previously, only algorithms for solving h one-to-one routing problems were known.Finally, we show that a 2-folded butterfly, whose individual splitters do not exhibit expansion, can emulate a bounded-degree multibutterfly with (CS, ,@-expansion, for any a ./3 < 1/4.