Performance-oriented decomposition of sequential circuits

A synthesis procedure which partitions a given finite state machine (FSM) into an interconnection of submachines in order to improve the timing performance of the circuit is presented. A decomposition via factorization which decomposes a given machine of any size by extracting and merging groups of states having similar I/O transition edges and representing them in separate submachines is discussed. These submachines are interconnected in a parallel, but interactive, fashion to realize the original terminal behavior. Timing improvements are achieved by optimally identifying and sharing common logic blocks in the eventual realization of a given FSM. The complete procedure operates solely at the state transition graph level, thus constituting a high-level, or global timing optimization step in the synthesis of FSMs. Results which illustrate the efficacy of this procedure are presented. Based on a set of benchmark examples, the factorization procedure, on the average, decreases the critical-path delays of the original FSMs by 26% while keeping the area increase in the decomposed FSMs within 33% under both two-level and multilevel logic implementations.