SKADI: A 28-nm Complete K-SAT Solver Featuring Bidirectional In-Memory Deduction and Incremental Updating
IEEE Journal of Solid-State Circuits · 2026-05 · 61 (5) · 2295-2308
DOI: 10.1109/jssc.2025.3598289 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Journal of Solid-State Circuits, 2026-05. Verfasst von Zihan Wu und 10 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 29 Literaturangaben. Gefördert von: National Key Research and Development Program of China.
Abstract (Originalsprache)
Boolean satisfiability (K-SAT) is a canonical problem at the core of many electronic design automation (EDA) and artificial intelligence (AI) tasks. Due to its NP-complete characteristic, solving K-SAT ( $K \geq 3$ ) problems on von Neumann architectures incurs substantial energy and latency overhead. Recent ASIC K-SAT solvers have significantly improved energy efficiency, but these implementations are inherently incomplete. While these solvers have demonstrated the capability to solve satisfiable (SAT) problems, no evidence has been provided for proving unsatisfiability. This limitation severely restricts their applicability, as real-life scenarios mostly demand definitive SAT/unsatisfiable (UNSAT) outcomes. To address this gap, this work presents a complete K-SAT solver based on the DPLL framework that can determine whether the given formula is SAT or UNSAT. The proposed architecture incorporates a dual-path SRAM-based macro and a position-encoded counter (PEC) to perform highly parallel, bidirectional clause-variable deduction. Additionally, an incremental updating technique is employed for conflict-aware backtracking and search space pruning. Fabricated in 28-nm CMOS, the proposed solver achieves 100% solvability across all SAT and UNSAT benchmarks, with average solution times of $17.1~\mu $ s (uf50-218) and $42.1 ~\mu $ s (uuf50-218) at 0.9-V supply voltage. Corresponding energy consumptions are 58.0 and 142.8 nJ, respectively. As the first ASIC complete K-SAT solver, it enables deployment in applications where deterministically asserting SAT/UNSAT is essential.
Förderung
- National Key Research and Development Program of China
Zitieren
APA
Wu, Z., Tang, X., Zhang, T., Lin, L., Luo, H., Xu, B., Wu, Z., Song, J., Liang, Y., Bo, X., & Wang, Y. (2026). SKADI: A 28-nm Complete K-SAT Solver Featuring Bidirectional In-Memory Deduction and Incremental Updating. IEEE Journal of Solid-State Circuits, 61(5), 2295-2308. https://doi.org/10.1109/jssc.2025.3598289
Vancouver
Wu Z, Tang X, Zhang T, Lin L, Luo H, Xu B, et al. SKADI: A 28-nm Complete K-SAT Solver Featuring Bidirectional In-Memory Deduction and Incremental Updating. IEEE Journal of Solid-State Circuits. 2026;61(5):2295-2308. doi:10.1109/jssc.2025.3598289
BibTeX
@article{Wu2026,
author = {Wu, Zihan and Tang, Xiyuan and Zhang, Tao and Lin, Lishan and Luo, Haoyang and Xu, Bocheng and Wu, Zhongyi and Song, Jiahao and Liang, Yitao and Bo, Xiaochen and Wang, Yuan},
title = {SKADI: A 28-nm Complete K-SAT Solver Featuring Bidirectional In-Memory Deduction and Incremental Updating},
journal = {IEEE Journal of Solid-State Circuits},
year = {2026},
volume = {61},
number = {5},
pages = {2295--2308},
doi = {10.1109/jssc.2025.3598289}
}
EUVIMED