An optimization based approach to the partial scan design problem

The problem of selecting flip-flops for inclusion into a partial scan path is formulated as an optimization problem. Scan flip-flops result in layout and delay overheads. Hence, scan flip-flops have to be chosen such that the net cost associated with these overheads is bounded by some user-specified limit. The problem then reduces to choosing a set of flip-flops which gives the best improvement in testability, while keeping the cost bounded. Cost functions are proposed for a standard cell design approach to model the effects of the overheads. Profit functions for three different testability criteria are proposed, and the optimization methodology for each is discussed. The optimization process is modeled on the lines of the 0/1 knapsack problem. Results for some medium-sized sequential circuits which show a very large improvement in fault coverage obtained by optimally selecting a small fraction of the flip-flops in the circuit are presented