COMPLEXITIES OF LAYOUTS IN 3-DIMENSIONAL VLSI CIRCUITS

Recent advances in very large scale integration (VLSI) fabrication technologies have demonstrated the feasibility of three-dimensional (3-D) circuits in a single chip. Owing to the ability, with flexibility, to connect nonadjacent circuits by using the third dimension, the cost of mapping nonplanar circuits to two-dimensional (2-D) systems can be reduced. In this paper, we examine the complexities in volume and maximum wire length of mapping circuits represented as undirected graphs to 3-D systems. Tighter bounds than those previously known are shown for various families of graphs, in both the one-active-layer and the unrestricted layouts. Finally, we develop a cost model to reflect the cost of implementation in the third dimension and present an optimization model on the number of layers to minimize the overall cost. © 1991.