TY  - JOUR
AU  - CHU, GG
AU  - HARWOOD, A
AU  - STUCKEY, P
Y2  - 2014/05/21
Y1  - 2010
SN  - 1574-0617
UR  - http://hdl.handle.net/11343/26737
AB  - Current SAT solvers are well engineered and highly efficient, and significant research effort has been put into creating data structures that can produce maximal efficiency for the core propagation engine within SAT solvers. However, there is still substantial room for improvement. As the disparity between CPU speeds and cache sizes have increased, cache conscious data structures and algorithms have become very important. They are even more important in the context of parallel SAT solving, as issues like cache contention and main memory contention can dramatically slow down a parallel SAT solver. We present a series of data structure and algorithmic modifications that are able to increase the core propagation speed of MiniSat 2.0 by an average of 80% on a set of medium sized industrial instances, and increase the speed of a parallelized version of MiniSat running with 8 threads by 140% on those same instances.
N1  - application/pdf
PB  - IOS Press
KW  - Computer Software not elsewhere classified; Computer Software and Services not elsewhere classified
T1  - Cache Conscious Data Structures for Boolean Satisfiability Solvers
DO  - 10.3233/sat190064
IS  - Journal of Satisfiability, Boolean Modeling and Computation
VL  - 6
IS  - 1-3
SP  - 99-120
L1  - /bitstream/handle/11343/26737/117714_5682.pdf?sequence=1&isAllowed=n
ER  -