Strategies for Solving SAT in Grids by Randomized Search

摘要: Grid computing offers a promising approach to solving challenging computational problems in an environment consisting of large number easily accessible resources. In this paper we develop strategies for collections hard instances the propositional satisfiability problem (SAT) with randomized SAT solver run Grid. We study alternative by using simulation framework which is composed (i) grid model capturing communication and management delays, (ii) run-time distributions solver, obtained running state-of-the-art on collection instances. The results are experimentally validated production level When single instance, show that practice only relatively small amount parallelism can be efficiently used; speedup increasing thereafter negligible. This observation leads novel strategy solve Instead one-by-one, aims at decreasing overall solution time applying alternating distribution schedule.