IEICE TRANSACTIONS on Fundamentals
A VLSI Scan-Chain Optimization Algorithm for Multiple Scan-Paths
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.11 pp.2499-2504
- Publication Date
- 1999/11/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Susumu KOBAYASHI, Masato EDAHIRO, Mikio KUBO, "A VLSI Scan-Chain Optimization Algorithm for Multiple Scan-Paths" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 11, pp. 2499-2504, November 1999, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_11_2499/_p
Copy
@ARTICLE{e82-a_11_2499,
author={Susumu KOBAYASHI, Masato EDAHIRO, Mikio KUBO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A VLSI Scan-Chain Optimization Algorithm for Multiple Scan-Paths},
year={1999},
volume={E82-A},
number={11},
pages={2499-2504},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={November},}
Copy
TY - JOUR
TI - A VLSI Scan-Chain Optimization Algorithm for Multiple Scan-Paths
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2499
EP - 2504
AU - Susumu KOBAYASHI
AU - Masato EDAHIRO
AU - Mikio KUBO
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 1999
AB - 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.
ER -
English
