Solving hard satisfiability problems with synchronous simulated annealing on the AP1000 multiprocessor

Solving the hard Satisfiability Problem is difficult and time-consuming for even modest sized problem instances. This report presents a parallel synchronous simulated annealing method for solving the Random L-Sat problem on a large scale distributed-memory multiprocessor. In particular, we use a parallel synchronous simulated annealing method, called Generalized Speculative Computation, which guarantees the convergence property and same decision sequence of sequential simulated annealing. To demonstrate the performance, we have selected the Random L-SAT instances of 100-variable/425-clause to 5,000-variable/21,250-clause. Experimental results on the AP1000 distributed-memory multiprocessor indicate that the method can satisfy 99.9% of the clauses of the hard Random L-Sat instances while giving nearly 70-fold speedup on 500 processors.