Three-dimensional VLSI: a case study.

*(English)*Zbl 0624.94019The advantages of three-dimensional circuits are studied by comparing sample three-dimensional realizations of certain common families of circuits, namely, permutation networks, FFT circuits, and complete binary trees, with the families’ optimal two-dimensional realizations. These circuits are then used as building blocks to obtain three-dimensional realizations of arbitrary circuits. The results obtained indicate (roughly) that bounds on area (both upper and lower) in the neighborhood of order \(n^ 2\) in the two-dimensional case translate to bounds on volume in the neighborhood of order \(n^{3/2}\) in the three-dimensional case. Moreover, several of the upper bounds are attainable (idealized) realizations that have active devices on only one level that use the third dimension only for wire-routing; such realizations place fewer demands on the fabrication technology. However, it is also shown that unrestricted use of the third dimension can yield realizations that are more conservative of volume (by the factor \(\log^{1/2}n)\) than any “one-active-level” realization can be. Finally, examples are presented wherein two-dimensional realizations require device-to-device wire lengths as large as n/log n, while equivalent three-dimensional realizations can get by with wire lengths not exceeding \(n^{1/2}\). Thus, at least in the worst case, there are substantive savings from three-dimensional circuit realizations, in both material (area versus volume) and time (wire length).

##### MSC:

94C15 | Applications of graph theory to circuits and networks |

68R10 | Graph theory (including graph drawing) in computer science |