An Arboriculture Approach for Parallel SMT and Symbolic Model Checking

by M. Marescotti, A.E.J. Hyvärinen, N. Sharygina
Formal Verification and Security Lab
Università della Svizzera Italiana


Abstract: The inherent complexity of parallel computing makes development, resource monitoring, and debugging for parallel constraint-solving-based applications difficult. This paper presents SMTS, a framework for parallelizing sequential constraint solving algorithms and running them in distributed computing environments. The design (i) is based on a general parallelization technique that supports recursively combining algorithm portfolios and divide-and-conquer with the exchange of learned information, (ii) provides monitoring by visually inspecting the parallel execution steps, and (iii) supports interactive guidance of the algorithm through a web interface. We report positive experiences on instantiating the framework for one SMT solver and one model checker based on IC3, debugging parallel executions, and visualizing solving, structure, and learned clauses of SMT instances. A more detailed presentation of this work is published in LPAR 2018.