Optimal layout for butterfly networks in multilayer VLSI
Chi‐Hsiang Yeh · 2003
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/sup 2///spl lfloor/L/sup 2//2/spl rfloor/log/sub 2//sup 2/N+ o(N/sup 2//L/sup 2/log/sup 2/N), volume LN/sup 2///spl lfloor/L/sup 2//2/spl rfloor/log/sub 2//sup 2/N+ o(N/sup 2//Llog/sup 2/N), and maximum wire length N//spl radic//spl lfloor/L/sup 2//4/spl rfloor/log/sub 2/N+o(N/LlogN) under 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 /spl les/ L /spl les/ o(/spl I.nroot/N). We also show that the proposed multilayer butterfly layouts are optimal within a factor of 1+o(1) 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 far for L /spl gsim/ 3, and match the best previous layout for L=2. We propose to use AT/sup 2/L2 or 2AT/sup 2/ /spl lfloor/L/sup 2//2/spl rfloor/ as a new parameter for characterizing the space-time complexity for multilayer VLSI, and show that AT/sup 2/L/sup 2//spl ap/ 2R/sup 2/for RxR butterfly networks, where R=N/log/sub 2/N+o(N/logN).