Layout optimization of static CMOS functional cells

A general theory for designing minimum-area layouts of static series-parallel CMOS functional cells (also called complex gates) in a standard cell layout style is presented. T. Uehara and W.M. vanCleemput. (1981) originally formulated this as the graph optimization problem of finding the minimum number of dual trails that cover a multigraph model of M of a cell. The present theory provides a formalism for the analysis of series-parallel graphs and identifies the mathematical structures that underlie the layout problem. It also leads to two efficient algorithms for designing minimum area functional cell layouts. The first algorithm, TrailTrace, accepts an ordering of M that is fixed, typically for performance reasons, and produces the minimum area layout for that ordering. Its time complexity is linear in the number of transistors in the cell. The second algorithm, R-TrailTrace, reorders M and produces the best layout area that can be achieved for any reordering that preserves the cell´s functionality