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

Susumu Kobayashi*, Masato Edahiro, Mikio Kubo

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)2499-2504
Number of pages6
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number11
Publication statusPublished - 1999
Externally publishedYes


  • Design for testability
  • Layout design
  • Scan-chain

ASJC Scopus subject areas

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'A VLSI scan-chain optimization algorithm for multiple scan-paths'. Together they form a unique fingerprint.

Cite this