Multilayer VLSI layout for interconnection networks

Current VLSI technology allows more than two wiring layers and the number is expected to rise in future. In this paper we show that, by designing VLSI layouts directly for an L-layer model, the layout area for a variety of networks can be reduced by a factor of about (L/2)/sup 2/ compared to the layout area required under a 2-layer model, and the volume and maximum wire length can be reduced by a factor of about L/2, leading to considerably lower cost and/or higher performance. The proposed layouts for k-ary n-cubes, hypercubes, butterfly networks, cube-connected cycles (CCC), folded hypercubes, generalized hypercubes, k-ary n-cube cluster-c, hierarchical hypercube networks, reduced hypercubes, hierarchical swap networks, and indirect swap networks, are the best layouts reported for these networks thus far and are optimal within a small constant factor under both the Thompson model and the multilayer grid model. All of our layouts are optimally scalable in that we can allow each network node to occupy the largest possible area (e.g., o(N/L/sup 2/) for hypercubes) without increasing the leading constant of the layout area, volume, or maximum wire length.