A TIGHT LAYOUT OF THE BUTTERFLY NETWORK

We establish upper and lower bounds on the layout area of the butterfl y network (without wraparound), which differ only in low-ol:der 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 s maller 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 layou ts.