Solving Boolean satisfiability problems with resistive content addressable memories

Abstract

Solving optimization problems is a highly demanding workload requiring high-performance computing systems. Optimization solvers are usually difficult to parallelize in conventional digital architectures, particularly when stochastic decisions are involved. Recently, analog computing architectures for accelerating stochastic optimization solvers have been presented, but they were limited to academic problems in quadratic polynomial format. Here we present KLIMA, a k-Local In-Memory Accelerator with resistive Content Addressable Memories (CAMs) and Dot-Product Engines (DPEs) to accelerate the solution of high-order industry-relevant optimization problems, in particular Boolean Satisfiability. By co-designing the optimization heuristics and circuit architecture we improve the speed and energy to solution up to 182x compared to the digital state of the art.

References in corpus (7)

• Ising formulations of many NP problems
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Multiscale Co-Design Analysis of Energy, Latency, Area, and Accuracy of a ReRAM Analog Neural Training Accelerator
• Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines
• Energy landscapes of combinatorial optimization in Ising machines
• Computing High-Degree Polynomial Gradients in Memory

Cited by in corpus (3)

• Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization
• A Statistical Analysis for Per-Instance Evaluation of Stochastic Optimizers: Avoiding Unreliable Conclusions
• Accelerating Hybrid XOR$-$CNF Boolean Satisfiability Problems Natively with In-Memory Computing