A memristor-based in-memory computing accelerator natively embeds and solves hybrid XOR-CNF SAT problems, with simulations showing roughly 10x gains in speed, energy, and area over CNF translation methods and 1000x energy efficiency over CPU solvers.
XORSAT: An Efficient Algorithm for the DIMACS 32-bit Parity Problem
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The DIMACS 32-bit parity problem is a satisfiability (SAT) problem hard to solve. So far, EqSatz by Li is the only solver which can solve this problem. However, This solver is very slow. It is reported that it spent 11855 seconds to solve a par32-5 instance on a Maxintosh G3 300 MHz. The paper introduces a new solver, XORSAT, which splits the original problem into two parts: structured part and random part, and then solves separately them with WalkSAT and an XOR equation solver. Based our empirical observation, XORSAT is surprisingly fast, which is approximately 1000 times faster than EqSatz. For a par32-5 instance, XORSAT took 2.9 seconds, while EqSatz took 2844 seconds on Intel Pentium IV 2.66GHz CPU. We believe that this method significantly different from traditional methods is also useful beyond this domain.
fields
cs.ET 1years
2025 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Accelerating Hybrid XOR$-$CNF Boolean Satisfiability Problems Natively with In-Memory Computing
A memristor-based in-memory computing accelerator natively embeds and solves hybrid XOR-CNF SAT problems, with simulations showing roughly 10x gains in speed, energy, and area over CNF translation methods and 1000x energy efficiency over CPU solvers.