simple molecular arch pix

Compact, Multilayer Layout for Butterfly Fat-Tree

Article by André DeHon published in Twelfth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2000, July 9-12, 2000), p. 206--215.

Modern VLSI processing supports a two-dimensional surface for active devices along with multiple stacked layers of interconnect. With the advent of planarization, the number of layers can be large (6 or 7 in modern designs) and more layers are feasible if the cost is justified. Using a multilayer-wiring VLSI area model, we show how a butterfly fat-tree (or fat-pyramid) with N processors can be laid out in Theta(N) active device area using Theta(log(N)) wiring layers. This result may have practical value in laying out efficient, single-chip multiprocessors and FPGAs. It may also provide a theoretical basis for the rate of layer scaling empirically seen in VLSI designs.

Copyright 2000 ACM, Inc.


In more recent work, we show that we can achieve compact layouts for the more general case (p>0.5).