Abstract | ||
---|---|---|
The Propositional Satisfiability Problem (SAT) is one of the most fundamental NP-complete problems, and is central to many domains of computer science. Utilizing a massively parallel architecture on a Graphics Processing Unit (GPU) together with a conventional CPU on NVIDIA's Compute Unified Device Architecture (CUDA) platform, this work proposes an efficient scheme to implement one parallel Stochastic Local Search (SLS) algorithms for SAT: CUDA-WSat-PcL. The implementation leads up to 5x speedup over the latest implementation of CUDA-WSat-PcL on CUDA. Additionally, our profiling results show that the CUDA portion of the new implementation is now at least 6x faster. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1109/CANDAR.2016.0087 | 2016 Fourth International Symposium on Computing and Networking (CANDAR) |
Keywords | Field | DocType |
CUDA,SAT Solving,Stochastic Local Search,CUDA-WSat-PcL | CUDA,Instruction set,Computer science,Parallel computing,Boolean satisfiability problem,General-purpose computing on graphics processing units,Local search (optimization),Graphics processing unit,Speedup,CUDA Pinned memory | Conference |
ISSN | ISBN | Citations |
2379-1888 | 978-1-5090-2656-2 | 0 |
PageRank | References | Authors |
0.34 | 6 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Heng Liu | 1 | 153 | 27.10 |
Arrvindh Shriraman | 2 | 15 | 1.57 |
Evgenia Ternovska | 3 | 0 | 0.34 |