Resynthesis and Retiming for Optimum Partial Scan

An effective partial scan approach selects flip-flops (FFs) to break all feedback loops. These FFs correspond to the minimum feedback vertex set (MFVS) of the FF dependency graph. The MFVS of the circuit (the minimum number of gates whose removal makes the circuit, acyclic) is a lower bound and in many cases significantly smaller than the MFVS of the FF dependency graph. Since only FFs are scannable, this paper investigates repositioning of FFs so that every circuit MFVS gate drives one or more FFs in the modified circuit. We show that resynthesis and retiming can always transform any circuit into an equivalent circuit whose FF dependency graph MFVS is equal to the MFVS of the original circuit. Experimental results for several large sequential benchmarks show that the number of scan FFs required for the resynthesized and retimed circuit is significantly smaller than that required for the original circuit.