An optimal transistor-chaining algorithm for CMOS cell layout

A fast algorithm is produced for the optimal transistor chaining problem in CMOS functional cell layout based on T. Uehara and W.M. van Cleemput´s layout style (IEEE Trans. Comput., vol. C-30, p.305-12, May 1981). The algorithm takes a transistor-level circuit schematic and outputs a minimum set of chains. Possible diffusion abutments between the transistor pairs are modeled as a bipartite graph. A depth-first search algorithm is used to search for the optimal chaining. Theorems on the number of branches needed to be explored at each node of the search tree are derived. A theoretical lower bound on the size of the chain set is derived. This bound enables pruning the search tree efficiently. The algorithm has been implemented and tested. It is able to find optimal solutions almost instantly for all the cases available to use from the literature.<>