SAT Sampling at Scale via GPU-based Boolean Constraint Propagation
En palabras de los autores
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.
En palabras simples Resumen con IA
Los autores crearon Gpap-S, el primer muestreador de GPU que utiliza propagación de restricciones booleanas. Gpap-S explora miles de caminos de decisión simultáneamente, combinando confiabilidad en objetivos raros con la velocidad de GPU. En las pruebas anteriores, Gpap-S es de 2.2 a 18.7 veces más rápido que los muestreadores de GPU anteriores en objetivos de alta probabilidad. Gpap-S también es de 83.4 a 1,571 veces más rápido que el CMSGen basado en CPU, con igual calidad de muestras.
Escrito por Kimi K2.5 usando solo el abstract de arriba. Jev verificó que cada oración esté respaldada por las oraciones del abstract que cita y eliminó las que no. Pasá el cursor por una oración para ver de dónde sale. Se eliminó 1 oración por no estar respaldada por el abstract.
Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 22 pages, 3 figures, 3 tables