An Exact Algorithm for Selecting Partial Scan Flip-Flops

We develop an exact algorithm for selecting flip-flops in partial scan designs to break all feedback cycles. The main ideas that allowus to solve this hard problemexactly for large, practical instances are - graph transformations, a partitioning scheme used in the branch and bound procedure, and pruning techniques based on an integer linear programming formulation of the minimum feedback vertex set (MFVS) problem.We have obtained optimum solutions for the ISCAS ´89 benchmark circuits and several production VLSI circuits within reasonable computation time. For example, the optimal number of scan flip-flops required to eliminate all cycles except self-loops in the circuit s38417 is 374. This optimal solution was obtained in 32 CPU seconds on a SUN Sparc 2 workstation.