On Acceleration of SAT-Based ATPG for Industrial Designs

Due to the rapidly growing size of integrated circuits, there is a need for new algorithms for automatic test pattern generation (ATPG). While classical algorithms reach their limit, there have been recent advances in algorithms to solve Boolean Satisfiability (SAT). Because Boolean SAT solvers are...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 2008-07, Vol.27 (7), p.1329-1333
Main Authors: Drechsler, R., Eggersgluss, S., Fey, G., Glowatz, A., Hapke, F., Schloeffel, J., Tille, D.
Format: Article
Language:English
Subjects:
Acceleration
Algorithm design and analysis
Algorithms
Automatic test pattern generation
Automatic test pattern generation (ATPG)
Boolean algebra
Boolean functions
Boolean satisfiability (SAT)
Circuit testing
Design engineering
Engines
formal methods
Integrated circuits
Life estimation
Logic circuits
Pattern generation
Robustness
Semiconductors
Studies
Test pattern generators
testing
Transformations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Due to the rapidly growing size of integrated circuits, there is a need for new algorithms for automatic test pattern generation (ATPG). While classical algorithms reach their limit, there have been recent advances in algorithms to solve Boolean Satisfiability (SAT). Because Boolean SAT solvers are working on conjunctive normal forms (CNFs), the problem has to be transformed. During transformation, relevant information about the problem might get lost and, therefore, is not available in the solving process. In this paper, we present a technique that applies structural knowledge about the circuit during the transformation. As a result, the size of the problem instances decreases, as well as the run time of the ATPG process. The technique was implemented, and experimental results are presented. The approach was combined with the ATPG framework of NXP Semiconductors. It is shown that the overall performance of an industrial framework can significantly be improved. Further experiments show the benefits with regard to the efficiency and robustness of the combined approach.
ISSN:0278-0070
1937-4151
DOI:10.1109/TCAD.2008.923107