Skip to content

The Canonical Parallel Form as a Substrate for Parallelizing Compilers and Agentic Optimizers

Sep 2026 · arXiv.org · Vol abs/2609.28724 · 1 citation · 77 references
Computer Science

TL;DR

The Canonical Parallel Form (CPF), a device-neutral program state from which every ordering constraint the authors' analyses prove unnecessary has been removed, is introduced, a device-neutral program state from which every ordering constraint their analyses prove unnecessary has been removed.

Abstract

Imperative code fixes an execution order the computation does not require, and a parallelizing compiler must prove which parts of that order it can remove. We introduce the Canonical Parallel Form (CPF), a device-neutral program state from which every ordering constraint our analyses prove unnecessary has been removed. CPF is reached by output-preserving normalization, by lifting semantic operations such as tensor contractions, and by deriving parallelism in three levels ordered by decidability: syntactic subscript tests, exact affine dependence tests over integer sets, and SMT queries over non-linear integer arithmetic, which also admit parallelism guarded behind a runtime check. Heuristics can then specialize the canonical form for each architecture. Across 248 loop-level reasoning kernels on an AMD MI300A, CPF reaches 4.4x over Numba on its 24 Zen 4 cores and 25.4x on its CDNA 3 GPU. Against the other auto-parallelizing optimizers, CPF is 2.9x faster on the CPU and 8.7x on the GPU than DaCe's own auto-parallelizer, 1.9x faster than Pluto, and 1.5x faster than PPCG on the affine subset of the kernels. Because the pipeline is deterministic, CPF also serves as an agent's starting source, cutting the token cost per kernel by up to a factor of 2.72x while leaving the achieved speed-up unchanged, since the coding agents reason less about parallelism.

View source

Similar papers

Sep 2026

Exo-GPU: Safe, Imperative, User-schedulable Programming for Tensor Cores

Exo-GPU, an imperative, low-level language that creates minimal abstraction over CUDA, is proposed, to treat parallelism and synchronization as mere annotations on sequential code rather than as fundamental control flow primitives, enabling verification that these constructs do not alter the program semantics.

David Akeley, Yuka Ikarashi, Jonathan Ragan-Kelley · 2 citations

Accelerating the Mitigation of LLM Inference Nondeterminism Across GPU Architectures

This work presents a solution employing a set of fixed-configuration fused-upcast GEMM kernels that load 16-bit weights from memory, upcast them to FP32 in registers, and accumulate with IEEE-754 arithmetic in a reduction order that is a pure function of the problem shape and is therefore independent of the device, its...

Liam Cooper, Shinnung Jeong, Hyeran Jeon et al. · 1 citation
#artificial intelligence Preprint Oct 2026

Racer: Hunting GPU Kernel Bugs with Symbolic Equivalence Checking

GPU kernels are critical to the performance of today's AI services, yet the same operators are rewritten repeatedly: for each GPU generation, numeric format, serving regime, and kernel language. Every rewrite must preserve the function computed by the implementation it replaces. Today, this obligation depends almost en...

Tuan Truong Vu, Cheng Tan · 0 citations
Preprint Oct 2026

Cyclotron: A Recurrence Language for Expressing Interprocessor Communication

Cyclotron is a compiler that expresses streaming dataflow algorithms using recurrence equations, which are then compiled to distributed topologies of interlinked processors, and is competitive with and often outperforms these hand-optimized libraries.

Shiv Sundram, Akhilesh Balasingam, Nathan Zhang et al. · 0 citations
Sep 2026

Compiling with the Sequent Calculus

This work is a continuation, and generalization, of Andrew Appel's landmark work on “Compiling with Continuations”, but instead of natural-deduction-based languages like the lambda calculus, it uses sequent-calculus-inspired languages throughout all intermediate stages.

Marius Müller, David Binder, Marco Tzschentke et al. · 0 citations
Preprint Oct 2026

Proving LLM-Generated GPU Kernels Correct and Safe: Floating-Point Verification in Lean and VerCors

Modern statistical model development begins with a high-level specification in an automatic differentiation framework such as PyTorch, JAX, or TensorFlow, which is then lowered to a target backend by a compiler or implemented manually by a research engineer. In this paper, we study whether frontier language models can...

A. Browne, Eugene Lee, Cristopher Salvi · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.