Cube-and-Conquer approach for SAT solving on grids

Our goal is to develop techniques for using distributed computing resources to efficiently solve instances of the propositional satisfiability problem (SAT). We claim that computational grids provide a distributed computing environment suitable for SAT solving. In this paper we apply the Cube and Conquer approach to SAT solving on grids and present our parallel SAT solver CCGrid (Cube and Conquer on Grid) on computational grid infrastructure. Our solver consists of two major components. The master application runs march_cc, which applies a lookahead SAT solver, in order to partition the input SAT instance into work units distributed on the grid. The client application executes an iLingeling instance, which is a multi-threaded CDCL SAT solver. We use BOINC middleware, which is part of the SZTAKI Desktop Grid package and supports the Distributed Computing Application Programming Interface (DC-API). Our preliminary results suggest that our approach can gain significant speedup and shows a potential for future investigation and development.