The Synthesis of Cyclic Dependencies with Boolean Satisfiability

The accepted wisdom is that combinational circuits must have acyclic (i.e., feed-forward) topologies. Yet simple examples suggest that this is incorrect. In fact, introducing cycles (i.e., feedback) into combinational designs can lead to significant savings in area and in delay. Prior work described methodologies for syn- thesizing cyclic circuits with sum-of-product (SOP) and binary-decision diagram (BDD)-based formulations. Recently, techniques for analyzing and mapping cyclic circuits based on Boolean satisfiability (SAT) were proposed. This paper presents a SAT-based methodology for synthesizing cyclic dependencies. The strat- egy is to generate cyclic functional dependencies through a technique called Craig interpolation. Given a choice of different functional dependencies, a branch-and-bound search is performed to pick the best one. Experiments on benchmark circuits demonstrate the effectiveness of the approach.