VLSI layout and packaging of butterfly networks
Chi‐Hsiang Yeh, Behrooz Parhami, Emmanouel Varvarigos, H. Lee · 2000
We present a scheme for optimal VLSI layout and packaging of butterfly networks under the Thompson model, the multilayer grid model, and the hierarchical layout model. We show that when L layers of wires are available, an N-node butterfly network can be laid out with area 4N2/L2 log22 N + o (N2/L2 log2 N), maximum wire length 2N/L log2 N + o (N/L log N), and volume 4N2/L log22 N + o (N2/L log2 N) , under the multilayer 2-D grid model, where only one active layer (for network nodes) is required and L layers of wires are available.