parSAT: Parallel Solving of Floating-Point Satisfiability

Markus Krahl, Matthias Güdemann, Stefan Wallentowitz · 2025

Read parSAT: Parallel Solving of Floating-Point Satisfiability by Markus Krahl, Matthias Güdemann, Stefan Wallentowitz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-16237.txt.

Introduction

Checking that computer programs behave safely often means solving hard math claims about decimal numbers. Markus Krahl, Matthias Güdemann, and Stefan Wallentowitz recast such claims so many parts can be solved in parallel on modern multi-core chips. Their tool mixes global search methods with parallel runs in a portfolio style, where several tries race and the first success wins.

Benchmark tests show the approach can support standard solvers on tough decimal problems. The method is a semi-decision procedure, tuned for the kind of exact math that safety-critical code demands. It points to a practical way to use spare cores in verification work.

Catalog record

CREATORMarkus Krahl, Matthias Güdemann, Stefan Wallentowitz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-16237

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

parSAT: Parallel Solving of Floating-Point Satisfiability Markus Krahl, Matthias Güdemann, Stefan Wallentowitz Abstract Satisfiability-based verification techniques, leveraging modern Boolean satisfiability (SAT) and Satisfiability Modulo Theories (SMT) solvers, have demonstrated efficacy in addressing practical problem instances within program analysis. However, current SMT solver implementations often encounter limitations when addressing non-linear arithmetic problems, particularly those involving floating point (FP) operations. This poses a significant challenge for safety critical applications, where accurate and reliable calculations based on FP numbers and elementary mathematical functions are essential. This paper shows how an alternative formulation of the satisfiability problem for FP calculations allows for exploiting parallelism for FP constraint solving. By combining global optimization approaches with parallel execution on modern multi-core CPUs, we construct a portfolio-based semi-decision procedure specifically tailored to handle FP arithmetic. We demonstrate the potential of this approach to complement conventional methods through the evaluation of various benchmarks. 1 Introduction Various software-intensive systems utilize Floating Point (FP) computations, as FP allows for the approximation of real numbers that are essential in numerous applications modeling physical behavior. When these systems operate within safety or security critical domains, their correctness must be guaranteed. The challenge lies in testing and verifying FP computations due to the vast domain and specific behaviors inherent to FP arithmetic. However, taking into account recent advancements such as incorporating IEEE754 compliant FP theory into the SMT-LIB2 standard, current state-of-the-art automatic theorem provers offer a viable approach for modeling and verifying these complex calculations. For solving FP constraints, contemporary state-of-the-art SMT solvers, e.g., bitwuzla [ 17 ] , cvc5 [ 2 ] , or Z3 [ 7 ] , employ bit-blasting [ 5 ] , a technique that transforms the FP constraints into propositional logic problems. These problems are then solved by Boolean satisfiability (SAT) solvers, thereby enabling rigorous, automatic verification of FP computations. While significant advancements have been made in SMT solver capabilities for solving equations in FP theory, their capacity for reasoning about FP constraints, particularly those involving non-linear arithmetic, remains limited for practical applications. This limitation stems from inherent overhead associated with converting these computations from FP arithmetic to propositional logic, often requiring word- [ 17 ] or bit-blasting operations specific to the FP-focused solver frameworks. Furthermore, this encoding process fails to exploit advancements in hardware such as dedicated FP units within multicore CPUs or GPUs that could significantly accelerate computation. In this paper, we present parSAT, an integrated tool that performs a portfolio-based semi-decision procedure for SMT equations in FP theory. It extends the formulation of solving FP constraints based on global optimization (GO), originally introduced and refined in [ 9 , 3 ] . We specifically address limitations by incorporating a more comprehensive support for SMT-LIB2 constraints and enabling a portfolio-based minimization of the objective function using a multicore implementation to decide satisfiability. Furthermore, we demonstrate the potential of combining parSAT with an SMT solver to systematically leverage the advantages of both approaches. The paper is structured as follows. Section 2 discusses related work, and section 3 provides the theoretical foundations for converting SMT equations in FP theory. The core principles and implementation details of parSAT are described in section 4 . In section 5 , we evaluate parSAT in comparison with other SMT solvers. Section 6 concludes the paper and discusses the outlook and potential further work. 2 Related Work The approach to formulate FP constraints in the form of a GO problem was first introduced in XSat [ 9 ] . It solves SMT equations in pure FP theory by converting the given constraints into an equisatisfiable mathematical optimization problem which has a global minimum of value 0 if and only if the original problem is satisfiable. In detail, it transforms a quantifier-free SMT equation F(\overrightarrow{x}) , where \overrightarrow{x}\in FP^{n} corresponds to an arbitrary assignment of the variables in the equation, into an objective function G(\overrightarrow{x}) . G(\overrightarrow{x}) is minimized by applying GO to find an input vector \overrightarrow{z} for which G(\overrightarrow{z})=0 . In case a \overrightarrow{z} was found, \overrightarrow{z} would correspond to a valid assignment \alpha for which F(\alpha)=\textit{SAT} , therefore F(\overrightarrow{x}) would be satisfiable. In case only a non-zero global minimum is found, the SMT equation F(\overrightarrow{x}) is considered to be unsatisfiable. XSat takes an SMT equation in the SMT-LIB2 format as input and generates the optimization function as C-code which is compiled and loaded as Python-Module that applies the GO algorithm Basin Hopping [ 23 ] ( BH ) from the SciPy-Package [ 22 ] to find its global minimum. goSAT [ 3 ] is based on the ideas of XSat as it similarly transforms an SMT equation in pure FP theory from a given input file in SMT-LIB2 format to an optimization function and attempts to find its global minimum. It also supports a code generation mode similar to XSat where the optimization function is emitted as C-code. However, the main aspect of goSAT is the Just-in-Time (JIT) compilation of the generated objective function and the immediate search for its global minimum. Additionally, it offers the possibility to choose from several different GO routines provided through the NLopt [ 11 ] library whereas XSat only involves the BH algorithm. Our parSAT approach builds on top of XSat and goSAT. We included the three best performing GO algorithms based on average runtime and found SAT solutions used in goSAT and XSat, namely BH with the Powell method [ 18 ] as local minimizer, Controlled Random Search 2 with local mutation [ 20 , 12 ] ( CRS2 ) and Improved Stochastic Ranking Evolution Strategy [ 21 ] ( ISRES ) for use in minimization by reimplementing each approach in C ++ . parSAT supports a freely configurable parallel execution of these algorithms in a portfolio-based approach. Similar to XSat and goSAT, parSAT first converts the given SMT equation into an optimization function, but it natively compiles this optimization function into a shared library that is directly loaded into parSAT. Additionally, parSAT provides a more complete support of the SMT-LIB2 standard, e.g., the ite function for arguments with FP type. Most other SMT solvers apply the DPLL(T) [ 15 , p. 66] framework which is used to decide combinations of different theories based on structural SAT solving. In that case, an SMT solver consists of multiple theory solvers and an orchestrating SAT solver. The SMT solvers bitwuzla [ 17 ] and cvc5 [ 2 ] use an implementation of FP constraints based on the SymFPU [ 6 ] library. This allows them to apply word-blasting, i.e., an eager conversion of FP into the bitvector theory and then using bit-blasting to generate a purely propositional bit-level problem for a SAT solver. It can be beneficial to not only have conjunctions for the theory solver, but to use more abstract reasoning on the mathematical level in order to avoid searching through large state spaces that are impossible according to the theory. This is for example realized in the natural domain solving procedure implemented in MathSAT [ 10 ] or based on incremental approximations and logic programming as in Colibri [ 26 ] . These approaches to solving FP constraints are powerful and guaranteed to be complete. The downside is that due to the complexity of

Read the complete text