TY - JOUR
T1 - Solving hard satisfiability problems with synchronous simulated annealing on the AP1000 multiprocessor
AU - Sohn, Andrew
PY - 1995/12/1
Y1 - 1995/12/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0029513343&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0029513343&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:0029513343
SN - 1063-6374
SP - 719
EP - 722
JO - IEEE Symposium on Parallel and Distributed Processing - Proceedings
JF - IEEE Symposium on Parallel and Distributed Processing - Proceedings
ER -