Depth-First-Search and Dynamic Programming Algorithms for Efficient CMOS Cell Generation

Abstract

We describe a new algorithmic framework for mapping CMOS circuit diagrams into area-efficient, high-performance layouts in the style of one-dimensional transistor arrays. Using efficient search techniques and accurate evaluation methods, the huge solution space that is typical to such problems is traversed extremely fast, yielding designs of hand-layout quality. In addition to generating circuits.that meet prespecified layout constraints in the context of a fixed target image, on-the-fly optimizations are performed to meet secondary optimization criteria. A practical dynamic programming routing algorithm is employed to accommodate the special conditions that arise in this context. This algorithm has been implemented and is currently used at IBM for cell library generation. © 1989 IEEE