Efficient VLSI layouts of hypercubic networks
Chi‐Hsiang Yeh, Emmanouel Varvarigos, Behrooz Parhami · 1999
In this paper we present efficient VLSI layouts of several hypercubic networks. We show that an N-node hypercube and an N-node cube-connected cycles (CCC) graph can be laid out in 4N/sup 2//9+o(N/sup 2/) and 4N/sup 2//(9 log/sub 2//sup 2/N)+o(N/sup 2//log/sup 2/ N) areas, respectively, both of which are optimal within a factor of 1.7~+o(1). We introduce the multilayer grid model, and present efficient layouts of hypercubes that use more than 2 layers of wires. We derive efficient layouts for butterfly networks, generalized hypercubes, hierarchical swapped networks, and indirect swapped networks, that are optimal within a factor of 1+o(1). We also present efficient layouts for folded hypercubes, reduced hypercubes, recursive hierarchical swapped networks, and enhanced-cubes, which are the best results reported for these networks thus far.