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.
|Original language||English (US)|
|Number of pages||4|
|Journal||IEEE Symposium on Parallel and Distributed Processing - Proceedings|
|State||Published - Dec 1 1995|
All Science Journal Classification (ASJC) codes