Canonical parallel form improves speed of auto-parallelizing compilers on cpu and gpu
The Canonical Parallel Form as a Substrate for Parallelizing Compilers and Agentic Optimizers
Performance
Summary
Programs often say things must happen in a certain order, but sometimes they don't actually need to. The authors present a way to rewrite programs into a 'canonical parallel form' that removes unnecessary order, making it easier for compilers to run parts at the same time. This new form uses a step-by-step process to find safe parallelism and works on different devices without changes. Their tests show it can run much faster than several existing tools on real hardware, and it also helps code-writing assistants work more efficiently.
What this means in practice
- •For compiler developers: Integrate canonical parallel form normalization to improve auto-parallelization performance across CPUs and GPUs without device-specific tuning.
- •For machine learning system engineers: Use canonical parallel form as a starting point to reduce code generation cost and maintain speed-ups when employing AI code-writing agents for parallel kernels.
Authors
Yakup Koray Budanaz, Pratyai Mazumder, Alexandru Calotoiu, Torsten Hoefler
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.