NTRS - NASA Technical Reports Server

Back to Results
Satisfiability Test with Synchronous Simulated Annealing on the Fujitsu AP1000 Massively-Parallel MultiprocessorSolving 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 percent of the clauses while giving almost a 70-fold speedup on 500 processors.
Document ID
Document Type
Conference Paper
Sohn, Andrew (New Jersey Inst. of Tech. Newark, NJ United States)
Biswas, Rupak (Research Inst. for Advanced Computer Science Moffett Field, CA United States)
Date Acquired
September 6, 2013
Publication Date
March 1, 1996
Subject Category
Computer Systems
Report/Patent Number
NAS 1.26:200964
Meeting Information
10th ACM International Conference on Supercomputing(Philadelphia, PA)
Funding Number(s)
Distribution Limits
Work of the US Gov. Public Use Permitted.

Available Downloads

NameType 19960022790.pdf STI