An Exact Optimization of Two-Level Acyclic Sequential Circuits

Authors:
Sentovich, Ellen M.
Brayton, Robert K.
Technical Report Identifier: ERL-94-048
July 1994

Abstract: Several algorithms for gate-level sequential circuit optimization have been reported in the literature. They perform operations similar to those in the more mature multilevel combinational domain while taking relationships across several time periods into account. These techniques are heuristic and their application ad hoc: there is no guarantee of optimality by say definition beyond "no further improvement". In this paper, we present a technique for producing an optimum two-level acyclic sequential circuit. While the circuit restrictions (e.g. two- level, acyclic) and cost function are limiting, the guarantee of optimality is novel and illuminating. The technique presented herein is useful for optimizing sub-circuits of a multilevel sequential circuit just as two-level combinational techniques have been in the combinational domain. Furthermore, the algorithm can be used to detect precisely circuits in which logic sharing across latch boundaries is actually possible - a hitherto unsolved problem.