PCIM-SAT: A 55nm Probabilistic K-SAT Solver with p-Bit-Based Parallel-Variable Update on a Mixed-Signal Compute-in-Memory Architecture

📋 论文概要

本文提出一款55nm混合信号K-SAT求解器，采用基于概率比特(p-bit)的并行变量更新算法和存算一体架构，无需预处理即可映射任意阶K-SAT问题。在50变量3-SAT问题上实现5.5ms求解、265nJ能耗和100%可解性，较现有ASIC实现4-13倍加速。

💡 主要创新点

• 提出并行变量更新算法，利用概率比特实现高效并行采样，加速收敛。
• 采用混合信号存算一体架构，使用11T-SRAM交叉阵列实现一次模拟梯度计算，并省去ADC实现无转换梯度采样。
• 无需预处理即可直接映射任意阶K-SAT问题，降低硬件开销。

🏷 关键词

📄 原文摘要

Abstract We present a 55nm mixed-signal K-SAT solver with parallel-variable update algorithm for improved convergence and a compute-in-memory fabric that maps arbitrary-order K-SAT instances without preprocessing. It solves 50-variable 3-SAT (satisfiable) problems in 5.5ms with 100% solvability at 265nJ. A custom 11T-SRAM crossbar for one-shot analog gradient computation and ADC-less gradient-based sampling with probabilistic-bit circuits enable 4to-13× speedup over prior ASICs. Boolean Satisfiability (K-SAT, K)3) is an NP-complete problem that arises across nearly all domains of science and engineering like cryptography, computational biology, AI planning and EDA [1]. A K-SAT instance with N variables and M clauses is expressed as a conjunction (AND) of clauses, each being a disjunction (OR) of up to K literals (Boolean variables or their complements, Fig. 10.10.1, top). Solving SAT, i.e., finding satisfying assignment for

👥 作者与机构

Tinish Bhattacharya, George Higgins Hutchinson, Dongseok Kwon, Dmitri Strukov

University of California, Santa Barbara, CA