Butterfly Fat-Tree, Hierarchical Network and Compact Layout
|Shown here is a compact layout for the Butterfly Fat-Tree
network. As we go to larger numbers of interconnected processing elements
(gates, FPGA-LUTs, CPUs, etc.) on a chip, we have to be very cognizant of
providing adequate interconnect while minimizing the cost of interconnect
wiring. Hierarchical structures with carefully scaled bandwidth can have
superior scaling properties to flat networks (crossbars, multistage
networks). Flat networks have a 2D area growth that goes as
O(n2). In a strictly 2D VLSI model, these tree-structures can
be designed to have area growth of only O(n log2(n)) growth.
Using this layout and O(log(n)) wiring layers, we can construct networks
using only O(n) active substrate area. In addition to showing us how to
organize interconnect efficiently on modern, multilayer VLSI processes,
this result may help provide a theoretical basis for the rate of VLSI
layer growth we've seen and a model for its continued growth as we go to
larger capacity devices.
Multilayer Layout for Butterfly Fat-Tree for more details. This is an
example of the kind of interconnect work done in our group, trying to
understand the fundamental requirements for interconnect, their
relationship to substrate costs and capabilities, how we map to
interconnect, and the design space for programmable interconnect.