Min-area retiming on flexible circuit structures

In this paper, we present two techniques for improving min-area retiming that combine the actual register minimization with combinational optimization. First, we discuss an on-the-fly retiming approach based on a sequential AND/inverter/register graph. With this method, the circuit structure is sequentially compacted using a combination of register "dragging" and AND vertex hashing. Second, we present an extension of the classical retiming formulation that allows an optimal sharing of fan-in registers of AND clusters, similar to traditional fan-out register sharing. The combination of both techniques is capable of minimizing the circuit size beyond that possible with a standard Leiserson and Saxe retiming approach on a static netlist structure. Our work is primarily aimed at optimizing the performance of reachability-based verification methods. However, the presented techniques are equally applicable to sequential redundancy removal in technology-independent logic synthesis. A large set of experiments using benchmark and industrial circuits demonstrate the effectiveness of the described techniques.