Integer-programming-based layout synthesis of two-dimensional CMOS cells.

With the growing complexity and size of integrated circuits, automatic techniques for generating the layout of CMOS cells are becoming increasingly necessary for both full-custom and cell-based, semi-custom designs. In this thesis, we address the problem of minimizing the area of CMOS cells that employ the widely applicable, but little studied, two-dimensional (2-D) layout style. We present the first practical cell synthesis methodology CLIP (Cell Layout via Integer Programming) aimed at producing optimal or near-optimal 2-D layouts under various design objectives and constraints. CLIP uses integer-linear programming (ILP) as its core optimization method. Each 2-D cell layout problem is modeled as a 0-1 integer-linear program. An off-the-shelf ILP solver program then solves the model and generates a solution that is optimal under the modeled assumptions. CLIP exactly solves both the width and height minimization problems for 2-D cells. For width minimization, we formulate the problem in a precise form that combines all factors influencing the 2-D width in a common problem space; this space is then searched in a systematic manner by branch-and-bound algorithms used by ILP solvers. For height minimization, we show that cell height can be modeled accurately in terms of the horizontal wire routing density. The solution to this model specifies a minimum-height layout from among all layouts of minimum width. To handle larger circuits, we propose two different heuristic clustering techniques--grouping series-connected transistors (and-stacking) and hierarchical circuit partitioning (HCLIP)--that produce probably near-optimal layouts. Finally, we demonstrate the versatility of the CLIP approach by presenting a new performance-directed synthesis method that folds large transistors and generates layouts that are optimal for a given folding. We have experimented with two different branch-and-bound solution strategies for our ILP problems, one based on linear programming and the other on boolean satisfiability; the latter proved to have significantly shorter run times. Through extensive experimentation on a wide range of practical CMOS circuits, we demonstrate that exact CLIP is computationally feasible for optimal 2-D layout generation of circuits with about 20 transistors. With and-stacking and partitioning, CLIP is shown to be practical for circuits with 50 or more transistors. We also compare our layouts to those of prior heuristic methods, and demonstrate that CLIP produces significantly smaller cells.PhDApplied SciencesComputer scienceElectrical engineeringOperations researchUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/130480/2/9732086.pd