Satisfiability test with synchronous simulated annealing on the Fujitsu AP1000 massively-parallel multiprocessor

Andrew Sohn, Rupak Biswas

Research output: Contribution to conferencePaperpeer-review

1 Scopus citations

Abstract

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 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 procedure, called Generalized Speculative Computation, which guarantees the same decision sequence as sequential simulated annealing. To demonstrate the performance of the parallel method, we have selected problem instances varying in size from 100-variables/425-clauses to 5000-variables/21.250-clauses. Experimental results on the AP1000 multiprocessor indicate that our approach can satisfy 99.9% of the clauses while giving almost a 70-fold speedup on 500 processors.

Original languageEnglish (US)
Pages213-220
Number of pages8
DOIs
StatePublished - 1996
EventProceedings of the 1996 International Conference on Supercomputing - Philadelphia, PA, USA
Duration: May 25 1996May 28 1996

Other

OtherProceedings of the 1996 International Conference on Supercomputing
CityPhiladelphia, PA, USA
Period5/25/965/28/96

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Satisfiability test with synchronous simulated annealing on the Fujitsu AP1000 massively-parallel multiprocessor'. Together they form a unique fingerprint.

Cite this