Efficient Data Structures and Methodologies for SAT-based ATPG providing High Fault Coverage in Industrial Application

Stephan Eggersglüß, Rolf Drechsler

In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) 30 9 Seiten 1411-1415 IEEE Press 2011.


ATPG based on Boolean satisfiability (SAT) turned out to be a robust alternative to classical structural automatic test pattern generation (ATPG) algorithms performing very well especially for hard-to-detect faults but suffer from the overhead for easy-to-detect faults. In this letter, we propose new efficient data structures and methodologies for SAT-based ATPG. The novel incremental SAT solving technique dynamic clause activation which makes use of structural information using dedicated data structures forms the core of a new flexible SAT-based ATPG approach. Experimental results on large industrial circuits show a significant performance gain and a removal of the limitations. At the same time, the robustness of SAT-based ATPG can even be strengthened resulting in very high fault efficiency and increased fault coverage for transition faults.

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence