Effective Partitioning Method With Predictable Hardness for CircuitSAT

Abstract

Many industrial verification problems are solved via reduction to CircuitSAT (curcuit satisfibiliaty). It is often the case that the resulting SAT instances are very hard and require the use of parallel computing to be solved in reasonable time. The particularly relevant problem in this context is how to best plan the use of the computing resources, because SAT solvers’ runtime is well known to be hard to predict. In the present paper we propose two methods that employ the knowledge about a circuit’s structure to partition a CircuitSAT instance into a specific number of simpler subproblems. A distinctive feature of the proposed partitioning methods is that they make it possible to estimate the hardness (e.g. the total runtime of a SAT solver on all subproblems) of a partitioning via the Monte Carlo method. In the experimental evaluation we apply these methods to hard CircuitSAT instances and compare their performance with the well known Cube and Conquer approach. The proposed partitioning methods not only often outperform Cube and Conquer, but also show remarkably small variance in the runtime of a SAT solver on subproblems from a partitioning, thus making it possible to construct accurate estimations of time required to process all subproblems, using random samples of small size. As a consequence, we have the efficient stochastic estimation procedure which provides an additional opportunity to employ hyperparameter tuning methods to further increase the SAT solver performance on (partitioned) hard SAT instances. We demonstrate the effectiveness of the proposed constructions by applying them to some problems associated with CircuitSAT, in particular, Logical Equivalence Checking benchmarks, Automated Test Pattern Generation benchmarks and the inversion problems of some cryptographic functions.

Keywords

• SAT
• CircuitSAT
• partitioning
• hardness estimation
• logical equivalence checking
• automated test pattern generation