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

Citation
S. Kobayashi et al., A VLSI scan-chain optimization algorithm for multiple scan-paths, IEICE T FUN, E82A(11), 1999, pp. 2499-2504
Citations number
7
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Eletrical & Eletronics Engineeing
Journal title
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
ISSN journal
0916-8508 → ACNP
Volume
E82A
Issue
11
Year of publication
1999
Pages
2499 - 2504
Database
ISI
SICI code
0916-8508(199911)E82A:11<2499:AVSOAF>2.0.ZU;2-J
Abstract
This paper presents an algorithm for the scan-chain optimization problem in multiple-scan design methodology. The proposed algorithm, which consists o f four phases, first determines pairs of scan-in and scan-out pins (Phase 1 ), and then assigns flip-hops to scan-paths by using a graph theoretical me thod (Phase 2). Next the algorithm decides connection-order of flip-flops i n each scan-path by using TSP (Traveling Salesman Problem) heuristics (Phas e 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-t est 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 produ ced less total scan-path length than other three possible algorithms in a r easonable computing time.