Implementation of Algorithms for Synthesis of Digital Circuits

This thesis describes some techniques to be used in EDA synthesis tools to increase the quality of results of digital circuits. We present circuit transformations able to improve the delay by pushing critical signals forward in the logic. The algorithms are applied to netlists of mapped or generic non-sized gates, without electrical optimization. The elaborations we present are graph-based and can be used in conjunction with generic algebraic methods. The first two algorithms rely on the associative and distributive property which are used to restructure a cluster of few gates to reduce the logic levels for critical paths. The last algorithm presents an extension of the Global Flow algorithm. Global Flow is a rewiring algorithm that minimizes a circuit by changing its set of connections to an equivalent one. The new algorithm introduces the possibility of using global flow analysis on generic and mapped gates. Moreover, we present a heuristic to optimize for delay rather than for area. The algorithms have been implemented as part of the EDA tool Fusion Compiler by Synopsys. We describe the results of some experiments showing the potential improvement over the QoR.