More Web Proxy on the site http://driver.im/

Article

PASSAT: Efficient SAT-Based Test Pattern Generation for Industrial Circuits

Authors:

Rolf Drechsler,

Andreas Glowatz,

Friedrich Hapke,

Jurgen SchloffelAuthors Info & Claims

ISVLSI '05: Proceedings of the IEEE Computer Society Annual Symposium on VLSI: New Frontiers in VLSI Design

Pages 212 - 217

https://doi.org/10.1109/ISVLSI.2005.55

Published: 11 May 2005 Publication History

Abstract

Automatic Test Pattern Generation (ATPG) based on Boolean Satisfiability (SAT) has been proposed as an alternative to classical search algorithms. SAT-based ATPG turned out to be more robust and more effective by formulating the problem as a set of equations. In this paper we present an efficient ATPG algorithm that makes use of powerful SAT-solving techniques. Problem specific heuristics are applied to guide the search. In contrast to previous SAT-based algorithms, the new approach can also cope with tri-states. The algorithm has been implemented as the tool PASSAT. Experimental results on large industrial circuits are given to demonstrate the quality and efficiency of the algorithm.

References

[1]

S. Cook. The complexity of theorem proving procedures. In 3rd ACM Symposium on Theory of Computing, pages 151-158, 1971.

Digital Library

[2]

R. Drechsler. Advanced Formal Verification. Kluwer Academic Publishers, 2004.

Digital Library

[3]

H. Fujiwara and T. Shimono. On the acceleration of test generation algorithms. IEEE Trans. on Comp., 32:1137-1144, 1983.

Digital Library

[4]

P. Goel. An implicit enumeration algorithm to generate test for combinational logic. IEEE Trans. on Comp., 30:215-222, 1981.

Digital Library

[5]

E. Goldberg and Y. Novikov. BerkMin: a fast and robust SAT-solver. In Design, Automation and Test in Europe, pages 142-149, 2002.

Digital Library

[6]

A. Kuehlmann, M. Ganai, and V. Paruthi. Circuit-based Boolean reasoning. In Design Automation Conf., pages 232-237, 2001.

Digital Library

[7]

T. Larrabee. Test pattern generation using Boolean satisfiability. IEEE Trans. on CAD, 11:4-15, 1992.

Digital Library

[8]

H. Lee and D. Ha. Atalanta: An efficient ATPG for combinational circuits. Technical Report 12, Dep't of Electrical Eng., Virginia Polytechnic Institute and State University, 1993.

[9]

J. Marques-Silva. The impact of branching heuristics in propositional satisfiability algorithms. In 9th Portuguese Conference on Artificial Intelligence (EPIA), 1999.

Digital Library

[10]

J. Marques-Silva and K. Sakallah. GRASP - a new search algorithm for satisfiability. In Int'l Conf. on CAD, pages 220-227, 1996.

Digital Library

[11]

J. Marques-Silva and K. Sakallah. GRASP: A search algorithm for propositional satisfiability. IEEE Trans. on Comp., 48(5):506-521, 1999.

Digital Library

[12]

M. Moskewicz, C. Madigan, Y. Zhao, L. Zhang, and S. Malik. Chaff: Engineering an efficient SAT solver. In Design Automation Conf., pages 530-535, 2001.

Digital Library

[13]

J. Roth. Diagnosis of automata failures: A calculus and a method. IBM J. Res. Dev., 10:278-281, 1966.

Digital Library

[14]

E. Sentovich, K. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. Brayton, and A. Sangiovanni-Vincentelli. SIS: A system for sequential circuit synthesis. Technical report, University of Berkeley, 1992.

[15]

J. M. Silva and K. Sakallah. Robust search algorithms for test pattern generation. In Int'l Symp. on Fault-Tolerant Comp., pages 152-, 1997.

Digital Library

[16]

P. Stephan, R. Brayton, and A. Sangiovanni-Vincentelli. Combinational test generation using satisfiability. IEEE Trans. on CAD, 15:1167-1176, 1996.

Digital Library

[17]

P. Tafertshofer and A. Ganz. SAT based ATPG using fast justification and propagation in the implication graph. In Int'l Conf. on CAD, pages 139-146, 1999.

Digital Library

[18]

P. Tafertshofer, A. Ganz, and M. Henftling. A SAT-based implication engine for efficient ATPG, equivalence checking, and optimization of netlists. In Int'l Conf. on CAD, pages 648-655, 1997.

Digital Library

Cited By

Osama MGaber LHussein AMahmoud H(2018)An Efficient SAT-Based Test Generation Algorithm with GPU AcceleratorJournal of Electronic Testing: Theory and Applications10.1007/s10836-018-5747-434:5(511-527)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10836-018-5747-4
Eggersglüß SWille RDrechsler RHenkel J(2013)Improved SAT-based ATPGProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561847(85-90)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561847
Saluja NGulati KKhatri S(2008)SAT-based ATPG using multilevel compatible don't-caresACM Transactions on Design Automation of Electronic Systems10.1145/1344418.134442013:2(1-18)Online publication date: 23-Apr-2008
https://dl.acm.org/doi/10.1145/1344418.1344420
Show More Cited By

Index Terms

PASSAT: Efficient SAT-Based Test Pattern Generation for Industrial Circuits
1. Hardware

Recommendations

On stateless multihead automata: Hierarchies and the emptiness problem

We look at stateless multihead finite automata in their two-way and one-way, deterministic and nondeterministic variations. The transition of a k-head automaton depends solely on the symbols currently scanned by its k heads, and every such transition ...
Pebble alternating tree-walking automata and their recognizing power

Pebble tree-walking automata with alternation were first investigated by Milo, Suciu and Vianu (2003), who showed that tree languages recognized by these devices are exactly the regular tree languages. We strengthen this by proving the same result for ...
Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata
Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures - Volume 5504

The nonemptiness problem for nondeterministic automata on infinite words can be reduced to a sequence of reachability queries. The length of a shortest witness to the nonemptiness is then polynomial in the automaton. Nonemptiness algorithms for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ISVLSI '05: Proceedings of the IEEE Computer Society Annual Symposium on VLSI: New Frontiers in VLSI Design

May 2005

301 pages

ISBN:076952365X

Publisher

IEEE Computer Society

United States

Publication History

Published: 11 May 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Osama MGaber LHussein AMahmoud H(2018)An Efficient SAT-Based Test Generation Algorithm with GPU AcceleratorJournal of Electronic Testing: Theory and Applications10.1007/s10836-018-5747-434:5(511-527)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10836-018-5747-4
Eggersglüß SWille RDrechsler RHenkel J(2013)Improved SAT-based ATPGProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561847(85-90)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561847
Saluja NGulati KKhatri S(2008)SAT-based ATPG using multilevel compatible don't-caresACM Transactions on Design Automation of Electronic Systems10.1145/1344418.134442013:2(1-18)Online publication date: 23-Apr-2008
https://dl.acm.org/doi/10.1145/1344418.1344420
Drechsler RFey G(2006)Automatic test pattern generationProceedings of the 6th international conference on Formal Methods for the Design of Computer, Communication, and Software Systems10.1007/11757283_2(30-55)Online publication date: 22-May-2006
https://dl.acm.org/doi/10.1007/11757283_2

View Options

View options

Media

Figures

Other

Tables

View Table of Contents