Satometer: how much have we searched?

We introduce Satometer, a tool that can be used to estimate the percentage of the search space actually explored by a backtrack SAT solver. Satometer calculates a normalized minterm count for those portions of the search space identified by conflicts. The computation is carried out using a zero-supp...

Full description

Saved in:
Bibliographic Details
Main Authors: Aloul, Fadi A., Sierawski, Brian D., Sakallah, Karem A.
Format: Conference Proceeding
Language:English
Subjects:
Applied sciences
Computing methodologies > Symbolic and algebraic manipulation
Electronics
Exact sciences and technology
Integrated circuits
Integrated circuits by function (including memories and processors)
Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce Satometer, a tool that can be used to estimate the percentage of the search space actually explored by a backtrack SAT solver. Satometer calculates a normalized minterm count for those portions of the search space identified by conflicts. The computation is carried out using a zero-suppressed BDD data structure and can have adjustable accuracy. The data provided by Satometer can help diagnose the performance of SAT solvers and can shed light on the nature of a SAT instance.
ISSN:0738-100X
DOI:10.1145/513918.514103