CLIP: Integer-programming-based optimal layout synthesis of 2D CMOS cells

A novel technique, CLIP, is presented for the automatic generation of optim al layouts of CMOS cells in the two-dimensional (2D) style. CLIP is based o n integer-linear programming (ILP) and solves both the width and height min imization problems for 2D cells. Width minimization is formulated in a prec ise form that combines all factors influencing the 2D cell width-transistor placement, diffusion sharing, and vertical interrow connections-in a commo n problem space; this space is then searched in a systematic manner by the branch-and-bound algorithms used by ILP solvers. For height minimization, c ell height is modeled accurately in terms of the horizontal wire routing de nsity, and a minimum-height layout is found from among all layouts of minim um width. For exact width minimization alone, CLIP's run times are in secon ds for large circuits with 30 or more transistors. For both height and widt h optimization, CLIP is practical for circuits with up to 20 transistors. T o extend CLIP to larger circuits, hierarchical methods are necessary. Since CLIP is optimum under the modeling assumptions, its layouts are significan tly better than those generated by other, heuristic, layout tools.