A linear time algorithm for optimal CMOS functional cell layouts

To obtain a minimum width cell layout of a static CMOS circuit in the Uehara-vanCleemput (1981) style the circuit is often modeled as a pair of dual series-parallel multigraphs. The problem then reduces to finding a minimal number of edge-disjoint dual paths that cover the pair of graphs. Presented is an O(l) time heuristic algorithm for this problem, where l is the number of literals in an input prefix logic expression. It utilises the decomposition tree structure of the dual multigraphs. The algorithm produces optimal solutions to all the examples available in the literature. The algorithm is able to process very complicated logic expressions and almost always produces cell layouts of minimum width in less than a second