Conference
Version
E. Avior, T. Calamoneri, S. Even, A. Litman and A.L. Rosenberg
Abstract
We establish upper and lower bounds on the layout area of the butterfly network, which differ only in low-order terms. Specifically, the N-input, N-output butterfly network can be laid out in area (1 + o(1)) N^2, while no layout of the network can have area smaller than (1 - o(1)) N^2. These results improve both the known upper bound and the known lower bound on the area of butterfly network layouts.
PS Files