Three-Dimensional Circuit Layouts

Recent advances in fabrication technology have rendered imminent the fabrication of multilayer (i.e., three-dimensional) chips, wafers, and packages. In this paper, we examine the savings in material (as measured by Area in a two-dimensional medium and Volume in a three-dimensional one) and in communication time (as measured by the length of the longest uninterrupted run of wire) afforded by this developing technology. We derive close upper and lower bounds on the efficiency with which circuits can be realized in a multilayer medium, based on the sizes of the smallest {\em bifurcators} of the circuit. We find that the smallest Volume of any three-dimensional layout of an $N$-device circuit is no more than (roughly) $(NA)^{1/2}$, where $A$ is the smallest Area of any two-dimensional layout of the circuit. We then refine our layout techniques so that we can deal with multilayer layouts having a fixed number of layers. We find that we can efficiently transform a two-dimensional layout of Area $A$ and Maximum Wire Run $R$ into a three-dimensional layout of Volume (roughly) $V~=~A/H$ and Maximum Wire Run $R^*~=~R/H$ for moderate numbers of layers $H$. Two noteworthy features of the study are: (1) that, within logarithmic factors, the indicated savings can be realized with layouts that use the third dimension only for interconnect; and (2) that the indicated savings can be realized algorithmically: we present polynomial-time algorithms that transform a given two-dimensional layout into a more efficient three-dimensional one.