AN EXACT ALGORITHM FOR SELECTING PARTIAL SCAN FLIP-FLOPS

We develop an exact algorithm for selecting partial scan Aip-flops to break all feedback cycles. We also permit the option of not breaking s elf-loops. The key ideas that allow us to solve this complex problem e xactly for large, practical instances are-an MFVS-preserving graph tra nsformation, a partitioning scheme used in the branch and bound proced ure, and pruning techniques based on an integer linear programming for mulation of the MFVS problem. We have obtained optimum solutions for a ll ISCAS'89 benchmark circuits and several production VLSI circuits wi thin reasonable computation time, For example, the optimal number of s can flip-flops required to eliminate all cycles except self-loops in t he circuit s38417 is 374. An optimal solution was obtained in 32 CPU s econds on a SUN Sparc 2 workstation.