A GPU sampler finds valid circuit inputs in parallel
SAT Sampling at Scale via GPU-based Boolean Constraint Propagation · arXiv:2610.28805
In plain words
Circuit testers need legal input patterns that make a circuit produce chosen outputs, including outputs that ordinary random inputs rarely reach.
This paper introduces Gpap-S, a GPU sampler that tries many randomized assignments at once and keeps only completed assignments that satisfy the circuit's rules.
In tests on circuit collections, Gpap-S produced samples faster than the compared GPU gradient samplers on rare targets; Demotic produced none on five of its seven tested rare-target instances.
A separate statistical test accepted Gpap-S on 65 retained instances, which is evidence from that test rather than a guarantee of perfect uniformity.
The research
Circuit verification needs legal inputs that drive a design to chosen outputs, including rare patterns that random inputs seldom reach. Can a GPU generate many such valid inputs without the loss of useful samples that can occur when gradient-based methods round their results to Boolean assignments?
Gpap-S samples valid circuit inputs by running many randomized propagation attempts in parallel on a GPU and keeping completed assignments.
Gpap-S runs many randomized decide-and-propagate attempts on a GPU, discarding contradictions and keeping completed satisfying assignments as samples. This makes its outputs valid without rounding or repair.
Across the reported circuit-set, target and depth rows, Gpap-S had higher steady-state sampling rates than CPU sampler CMSGen.
Its rates also exceeded the compared GPU gradient samplers' rates at rare targets, though those comparisons covered each gradient sampler's own circuit set and counted only instances where both tools emitted samples.
The results come from a bounded set of circuit tests and compare tools under the reported hardware, settings and timing rules. Barbarik accepted Gpap-S on 65 retained instances, but this statistical result does not provide a formal guarantee that its samples are uniform.
What the evidence shows
- The rare-input problem
The paper introduces Gpap-S, a GPU method for sampling valid inputs to circuits. The question is how to generate many satisfying inputs, including inputs that reach rare output patterns.
CPU SAT samplers can find valid assignments, while GPU gradient samplers can lose useful output when few rounded assignments satisfy a rare target.
- A different GPU sampler
Gpap-S uses Gpap, an engine that propagates many independent partial assignments against one shared formula. For each attempt, it assigns variables and follows the consequences of those choices.
Completed assignments satisfy the formula and become samples; attempts that reach a contradiction are discarded. This keeps every emitted sample valid without rounding or repairing an assignment.
- Higher rates than CMSGen
In comparisons with the CPU sampler CMSGen, Gpap-S had higher steady-state samples-per-second rates across the reported circuit-set, target and depth rows. Both received the same circuit and depth and had a 60-second sampling budget, but Gpap-S's encoder repeated the circuit simplification and added a dc2 pass afterward.
Gpap-S ran on a GPU and CMSGen on one CPU core. The row means include only instances where both tools emitted samples.
- Rare targets and sample quality
Comparisons with GPU gradient samplers used each tool's own circuit collection. At original targets, Gpap-S had higher reported rates; at rare targets, its advantage over Recurrent was larger, while Demotic produced no samples on five of seven rare-target instances.
A statistical test also accepted both Gpap-S and CMSGen on all 65 retained instances. That test is evidence about sample quality under its criteria, not a proof of uniformity.
- Discarded work limits gains
The rate advantage has a cost on rare sequential targets. Gpap-S discards conflicting attempts without learning from them, so it can spend much more propagation work for each emitted sample than CMSGen, which learns from conflicts and backtracks.
The authors measured 6.41 and 6.59 times CMSGen's work per sample at 25 and 50 cycles, respectively. These were also the rows with Gpap-S's smallest measured speedups over CMSGen.
Deep
- Original paper authors
- Alexander Nadel, Yogev Shalmon, Ofer Strichman
- Submitted to arXiv
- License
- CC BY 4.0