GPU-Accelerated Synthesis of Mixed-Boolean Arithmetic: Beyond Caching

• URL: http://arxiv.org/abs/2605.08243v1
• Date: Thu, 07 May 2026 09:10:17 GMT
• Title: GPU-Accelerated Synthesis of Mixed-Boolean Arithmetic: Beyond Caching
• Abstract summary: We present SIMBA, a GPU-accelerated MBA synthesizer built around cache-free bottom-up enumeration.<n>In experiments, SIMBA is substantially faster than prior MBA synthesis tools, handles larger specifications, and reaches expression sizes that existing methods fail to solve.
• Score: 3.921125675673334
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Synthesizing Mixed-Boolean Arithmetic (MBA) expressions from input-output examples is central to program deobfuscation and also useful for compiler optimization, reverse engineering, and cryptanalysis. Existing MBA synthesizers are typically CPU-based and scale poorly on large specifications or complex targets. Recent GPU-accelerated synthesis methods achieve large speedups in qualitative settings, but they depend on caching observationally equivalent candidates; this strategy breaks down for MBA because candidate outputs are quantitative bitvectors and the behavioral space is enormous. We present SIMBA (Synthesis of Mixed-Boolean Arithmetic), a GPU-accelerated MBA synthesizer built around cache-free bottom-up enumeration. SIMBA avoids language caches entirely and uses a GPU-oriented enumeration design that keeps work local and highly parallel. In experiments, SIMBA is substantially faster than prior MBA synthesis tools, handles larger specifications, and reaches expression sizes that existing methods fail to solve. These results establish cache-free GPU synthesis as a practical and scalable approach for quantitative domains, and identify it as a strong alternative to cache-centric designs.

Related papers

• UniLab: A Heterogeneous Architecture for Robot RL Beyond GPU-Dominant Paradigms [68.40808444348735]
  In simulation-dominated robot control, the essential question is not which processor runs physics, but whether simulation throughput, policy learning, and runtime synchronization form an efficient end-to-end loop.<n>We present UniLab, a heterogeneous CPU-resident / GPU-learning architecture that decouples CPU-parallel simulation from GPU policy updates through a unified runtime for data movement, buffering, and synchronization.
  arXiv  Detail & Related papers  (2026-05-28T17:53:50Z)
• From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$-Sparse GLMs [6.381561491422844]
  We propose a generic, modular framework for processing heterogeneous nodes in branch and bound (BnB)<n>The framework is built around a small set of GPU-efficient routines and uses padding together with lightweight custom kernels to handle irregular node data structures.<n>Experiments show one to two orders of magnitude speedups and zero optimality gap on challenging instances.
  arXiv  Detail & Related papers  (2026-05-21T08:56:15Z)
• A Few GPUs, A Whole Lotta Scale: Faithful LLM Training Emulation with PrismLLM [47.09947710347623]
  PrismLLM decouples large-scale execution from the need to access large clusters.<n>Experiments on large-scale LLM training workloads show that PrismLLM accurately reproduces performance and memory behavior.
  arXiv  Detail & Related papers  (2026-05-15T04:58:20Z)
• ARGUS: Agentic GPU Optimization Guided by Data-Flow Invariants [12.49256588033198]
  LLM-based coding agents can generate functionally correct GPU kernels, yet their performance remains far below hand-optimized libraries on critical computations.<n>We present Argus, an agentic framework that addresses this through data-flow invariants.<n>We evaluate Argus on the AMD MI300X GPU across GEMM, flash attention, and MoE kernels.
  arXiv  Detail & Related papers  (2026-04-16T15:49:31Z)
• GPU Acceleration of Sparse Fully Homomorphic Encrypted DNNs [1.8933299988942567]
  homomorphic encryption (FHE) has attracted significant attention as both a cryptographic primitive and a systems challenge.<n>We propose a new optimized method that improves the runtime and complexity of ciphertext matmul by using FIDESlib, a recent open-source FHE library designed specifically for GPUs.
  arXiv  Detail & Related papers  (2026-04-13T16:09:26Z)
• NGPU-LM: GPU-Accelerated N-Gram Language Model for Context-Biasing in Greedy ASR Decoding [54.88765757043535]
  This work rethinks data structures for statistical n-gram language models to enable fast and parallel operations for GPU-optimized inference.<n>Our approach, named NGPU-LM, introduces customizable greedy decoding for all major ASR model types with less than 7% computational overhead.<n>The proposed approach can eliminate more than 50% of the accuracy gap between greedy and beam search for out-of-domain scenarios while avoiding significant slowdown caused by beam search.
  arXiv  Detail & Related papers  (2025-05-28T20:43:10Z)
• GPU accelerated program synthesis: Enumerate semantics, not syntax! [1.3422713954544112]
  We build a synthesiser running on GPUs which takes as input positive and negative example traces and returns a logical formula accepting the positive and rejecting the negative traces.<n>With GPU-friendly programming techniques, our synthesiser scales to significantly larger synthesis problems, and operates much faster than the previous CPU-based state-of-the-art.
  arXiv  Detail & Related papers  (2025-04-26T15:06:37Z)
• Hardware-Aware Parallel Prompt Decoding for Memory-Efficient Acceleration of LLM Inference [23.633481089469836]
  Auto-regressive decoding of Large Language Models (LLMs) results in significant overheads in their hardware performance.<n>We propose a novel parallel prompt decoding that requires only $0.0002$% trainable parameters, enabling efficient training on a single A100-40GB GPU in just 16 hours.<n>Our approach demonstrates up to 2.49$times$ speedup and maintains a minimal memory overhead of just $0.0004$%.
  arXiv  Detail & Related papers  (2024-05-28T22:19:30Z)
• ParaGraph: Weighted Graph Representation for Performance Optimization of HPC Kernels [1.304892050913381]
  We introduce a new graph-based program representation for parallel applications that extends the Abstract Syntax Tree. We evaluate our proposed representation by training a Graph Neural Network (GNN) to predict the runtime of an OpenMP code region. Results show that our approach is indeed effective and has normalized RMSE as low as 0.004 to at most 0.01 in its runtime predictions.
  arXiv  Detail & Related papers  (2023-04-07T05:52:59Z)
• Providing Meaningful Data Summarizations Using Examplar-based Clustering in Industry 4.0 [67.80123919697971]
  We show, that our GPU implementation provides speedups of up to 72x using single-precision and up to 452x using half-precision compared to conventional CPU algorithms. We apply our algorithm to real-world data from injection molding manufacturing processes and discuss how found summaries help with steering this specific process to cut costs and reduce the manufacturing of bad parts.
  arXiv  Detail & Related papers  (2021-05-25T15:55:14Z)
• High-performance symbolic-numerics via multiple dispatch [52.77024349608834]
  Symbolics.jl is an extendable symbolic system which uses dynamic multiple dispatch to change behavior depending on the domain needs. We show that by formalizing a generic API on actions independent of implementation, we can retroactively add optimized data structures to our system. We demonstrate the ability to swap between classical term-rewriting simplifiers and e-graph-based term-rewriting simplifiers.
  arXiv  Detail & Related papers  (2021-05-09T14:22:43Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)
• Heterogeneous CPU+GPU Stochastic Gradient Descent Algorithms [1.3249453757295084]
  We study training algorithms for deep learning on heterogeneous CPU+GPU architectures. Our two-fold objective -- maximize convergence rate and resource utilization simultaneously -- makes the problem challenging. We show that the implementation of these algorithms achieves both faster convergence and higher resource utilization than on several real datasets.
  arXiv  Detail & Related papers  (2020-04-19T05:21:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.