Optimal layout for butterfly networks in multilayer VLSI

In this paper we propose optimal VLSI layouts for butterfly networks under the multilayer 2-D grid model, the Thompson model, and the extended grid model. We show that an N-node butterfly network can be laid out with area (N-2) under bar /[L-2/2] log(2)(2)N + o (N-2/L(2)log(2)N) , volume (LN2) under bar/[L-2/L]log(2)(2)N + o ((N-2) under bar /Llog(2)N) T and maximum wire length (N) under bar/root[L-2/4]log(2)N + o ((N) under bar LlogN) under T J 1-92 N the multilayer 2-D grid model, where only one active layer (for network nodes) is required and L wiring layers (for network links) are available, 2 less than or equal to L less than or equal to o((3)rootN). We also show layouts are optimal that the proposed multilayer butterfly within a factor of I + o(l) when adjacent wiring layers have orthogonal wires (to be referred to as X-Y layouts) and the area is calculated by a slanted encompassing rectangle. The proposed layouts are the first and only optimal butterfly layouts reported in the literature thus farfor L greater than or equal to 3, and match the best previous layout for L = 2. We propose to use AT(2)L(2) or 2AT(2) [L-2/2] as a new parameter for charac terizing the space-time complexity for multilayer VLSI, and show that AT(2)L(2) approximate to 2R(2) for R x R butterfly networks, where R= (n) under bar log(2)N +o (N) under bar /logN.