SPFDs: A new approach to flexibility in logic synthesis

Logic synthesis algorithms convert one representation of a Boolean network into another one that is more desirable from the point of view of area, delay, power, testability, wireability or other criteria. The main requirement on such transformations is that it preserves functionality across all required operating conditions. The quality of the final implementation is strongly influenced by the ability of a transformation to suitably express and utilize the flexibility inherent in the original implementation of a Boolean network. Depending on the particular transformation, several formalisms have been developed over the past decade for suitably expressing flexibility. In this dissertation, a new formalism for expressing flexibility called Sets of Pairs of Functions to be Distinguished (SPFDs) is presented. SPFDs provide a powerful mechanism for expressing flexibility during certain logic synthesis transformations. The expressive power of SPFDs is compared with previous formalisms for expressing flexibility. It is proved that the flexibility expressed by them completely contains some previous formalisms (like Incompletely Specified Functions) and extends (but does not completely contain) other formalisms (such as Boolean Relations).; An in-depth exposition is provided for various applications of SPFDs. It is argued that SPFDs provide a more powerful and intuitive mechanism for expressing flexibility in logic and for rewiring of a network. Any such improved formalism usually comes at the cost of increased computational expense in using that flexibility. Efficient algorithms are provided for harnessing this extra flexibility without incurring too much additional overhead. Other interesting applications of SPFDs to some classical logic synthesis problems like functional decomposition and sequential synthesis are also presented.