Donald Bren School of Information and Computer Sciences

This paper defines a new sliced layout architecture for compilation of arbitrary schematics (netlists) into layout for CMOS technology. This sliced architecture uses over-the-cell routing on the second metal layer. We define three different architectures with simple folding, interleaved folding and unrestricted folding. We present a linear time algorithm for placement of components in architectures with simple folding. We prove interleaved folding is NP-hard and give an algorithm of complexity O(nbH/6) for approximating an optimal module, where n is the number of components, b is the width of the least-area module, H is the total height of the components, and 6 > 0 is arbitrarily chosen. The error of this algorithm (i.e. the difference between the area of the resulting module and the optimal one) is O (nb6). We conclude the paper with a proof that the architecture with interleaved folding is as good as the architecture with unrestricted folding with respect to area minimization of the total layout.