pipette
ESEspañol

SAT Sampling at Scale via GPU-based Boolean Constraint Propagation

Alexander Nadel, Yogev Shalmon, Ofer Strichman

PreprintClaims a big step

In the authors' words

Constrained-random verification tests hardware designs by sampling solutions of Boolean formulas. Existing samplers largely follow one of two approaches: CPU-based SAT samplers (e.g., CMSGen), which remain effective even at rare targets but offer limited throughput, and GPU-based gradient samplers, which achieve high throughput at high-probability targets but collapse at rare ones. We introduce Gpap-S, the first GPU sampler built on Boolean constraint propagation (BCP). At its core is Gpap, a new GPU engine for BCP that efficiently propagates many independent partial assignments concurrently on a shared Boolean formula. This capability allows Gpap-S to combine the rare-target robustness of SAT-based sampling with the throughput of GPU parallelism by exploring thousands of decide-and-propagate trajectories simultaneously. On the benchmark families used to evaluate prior GPU gradient samplers, Gpap-S is 2.2-18.7x faster at the high-probability targets considered in those evaluations. At rare targets, where those samplers often fail to generate any samples, Gpap-S achieves a geometric-mean speedup of roughly two orders of magnitude. Across all benchmarks, Gpap-S is also 83.4-1,571x faster than the CPU-based CMSGen. This throughput does not come at the expense of sample quality: under Barbarik, the statistical tester used to evaluate CMSGen, Gpap-S is accepted on every instance we test, as is CMSGen. We release Gpap as a reusable GPU library for high-throughput BCP.

Main resultThe abstract does not state a limitation.

In plain words AI summary

The authors created Gpap-S, the first GPU sampler that uses Boolean constraint propagation. Gpap-S explores thousands of decision paths at once, combining rare-target reliability with GPU speed. On prior benchmarks, Gpap-S is 2.2-18.7 times faster than earlier GPU samplers at high-probability targets. Gpap-S is also 83.4-1,571 times faster than the CPU-based CMSGen, with equal sample quality.

Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source. 1 sentence was removed for not being supported by the abstract.

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 22 pages, 3 figures, 3 tables