Parallel Satisfiability Test with Synchronous Simulated Annealing on Distributed-Memory Multiprocessor
✍ Scribed by Andrew Sohn
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 440 KB
- Volume
- 36
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
Solving the hard Satisfiability Problem is time consuming even for modest-sized problem instances. Solving the Random L-SAT Problem is especially difficult due to the ratio of clauses to variables. This report presents a practical approach to solving the Random L-SAT Problem on a large-scale distributed-memory multiprocessor. In particular, we use a parallel synchronous simulated annealing procedure, called Generalized Speculative Computation, which guarantees the same decision sequence as sequential simulated annealing. We have selected problem instances varying in size from 100-variable/425-clause to 5000variable/21,250-clause. Experimental results on the AP1000 distributed-memory multiprocessor indicate that Generalized Speculative Computation of synchronous simulated annealing can satisfy 99.9% of the clauses while giving almost a 70-fold speedup on 500 processors.