A VLSI Scan-Chain Optimization Algorithm for Multiple Scan-Paths

Susumu KOBAYASHI  Masato EDAHIRO  Mikio KUBO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.11   pp.2499-2504
Publication Date: 1999/11/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
VLSI CAD,  scan-chain,  layout design,  design for testability,  

Full Text: PDF>>
Buy this Article

This paper presents an algorithm for the scan-chain 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 flip-flops 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 scan-paths, 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.