A VLSI scan-chain optimization algorithm for multiple scan-paths

This paper presents an algorithm for the scanchain optimization problem in multiple-scan design methodology. The proposed algorithm which consists of four phases first determines pairs of scan-in and scan-out pins (Phase 1) and then assigns flip-flops to scan-paths by using a graph theoretical method (Phase 2). Next the algorithm decides connection-order of flipflops in each scan-path by using TSP (Traveling Salesman Problem) heuristics (Phase 3) and finally exchanges flip-flops among scan-paths in order to reduce total scan-path length (Phase 4). Experiments using actual design data show that for ten scanpaths our algorithm achieved a 90% reduction in scan-test time at the expense of a 7% total scan-path length increase as compared with the length of a single optimized scan-path. Also our algorithm produced less total scan-path length than other three possible algorithms in a reasonable computing time.