Heron: Automatically Constrained High-Performance Library Generation for Deep Learning Accelerators

Tensor compilers that beat hand-tuned libraries on CPUs and GPUs fall apart on deep-learning accelerators, because accelerator constraints make ~95% of their candidate programs invalid and the constraints are too numerous to hand-write (a single GEMM needs 372 of them over 173 variables) — so Heron generates the constraints automatically by static analysis alongside the schedule itself, turning the search space into a formal constraint satisfaction problem, and then explores it with a genetic algorithm that evolves the PROBLEMS rather than the solutions — crossover adds constraints pinning model-identified key variables to parent values, mutation removes one, and a solver samples offspring that are valid by construction — beating four state-of-the-art auto-compilers by 2.71× and vendor hand-tuned libraries by 2.00× on TensorCore, Intel DL Boost, and VTA, at no extra compilation time.

Why this problem is worth solving

The economics of accelerators run through software: silicon that only specialists can program is silicon that ships late and underperforms in the field. The compiler community’s answer,

The paper’s framing insight is that this is really two coupled problems. First, describing the valid region requires machine-generated precision — the constraints number in the hundreds per operator, vary with tensor shapes, and connect architectural limits to tunable parameters only through chains of intermediate quantities (a scratchpad bound constrains a product of loop lengths, which constrains tile factors). Second, searching the resulting region requires constraint-aware machinery, because the region is not a box: it is a jagged archipelago where a mutation that nudges one tile size strands you outside validity. Heron’s two halves — constraint generation and constraint-preserving evolution — answer the two halves exactly, and the payoff lands not just against other compilers but against the vendors’ own hand-tuned crown jewels.

What people did before, and where it broke

• Vendor libraries (cuDNN, cuBLAS, oneDNN, PopLIBS). Peak-tuned by teams over months-to-years; inflexible against new operators and shapes, and — the evaluation shows — beatable: Heron averages 2.00× over them, because hand-tuning cannot exhaustively cover every shape.
• Manual-template compilers (AutoTVM, UNIT). Experts write templates per operator per backend; the template bakes in a few simple constraints, excluding much of the valid space (and often the optimum) — visualized in the paper as a tidy box missing the best programs.
• Auto-template compilers (Ansor, FlexTensor, AMOS). Rules generate bigger spaces without manual templates — but the rules were designed for general-purpose targets, blind to DLA constraints: spaces balloon with invalid programs, and search wastes its budget discovering invalidity by compilation failure.
• Polyhedral compilers (AKG). Wider legal transformations via dependence analysis, TensorCore support included — but still not constraint-complete for DLA resource limits, and outperformed by 1.52–2.85× here.
• Constraint-handling GAs from the optimization literature. Penalty functions and multi-objective tricks do not guarantee valid offspring; repair and SAT-decoder methods guarantee validity but scramble inherited structure (the decoder maps mangled genotypes to legal phenotypes, losing the parents’ good genes). Heron’s evaluation shows all four trailing CGA, worse as problems grow.

How Heron works

The idea

Constraints are not obstacles to the search — they are the map. Prior compilers treated DLA validity as something to discover the hard way, one failed compilation at a time; Heron treats it as derivable knowledge. The derivation is the elegant part: every constraint is born from a schedule primitive — the split that created two sub-loops also creates PROD(parent, [sub1, sub2]); the cache stage that touched shared memory also creates the capacity inequality; the tensorize that claimed the matrix unit also creates the shape menu. Because schedule and constraints emerge from the same static analysis, they cannot drift apart, and the hundreds-per-operator scale that defeated hand-writing becomes free. The reification rhymes with moves this site has seen — a safety poset, a Steiner grid — but here the formal object is a CSP, chosen precisely because industrial-strength solvers exist to sample it.

Evolve the problems, not the solutions. The deep fix to genetic search is a change of representation. Classic crossover splices two concrete parameter vectors — and in a jagged valid region, the splice almost always lands outside (hence GA’s degeneration to random restarts). CGA never touches concrete vectors: crossover narrows the CSP by pinning key variables to parental values, mutation re-widens it by dropping one pin, and the solver — which understands every constraint — produces the offspring. Validity is not checked, repaired, or penalized; it is inherited, because adding constraints to a satisfiable problem can only shrink the solution set within the valid region. Meanwhile the cost-model-driven choice of key variables makes the pins meaningful: pinning what predicts performance is how parental “good genes” survive — exactly what SAT-decoder approaches lose (their evaluation shows it: GA-2 fades as problems grow).

Better spaces are harder spaces — plan for both. The paper’s search-space visualization makes an easily-missed point: pruning invalid programs does not smooth the landscape, it sharpens it — neighboring valid programs differ wildly in performance, because the buffer zones of mediocre-but-valid candidates are gone. A high-quality space without constraint-aware search is nearly useless (SA and GA both flounder in it); constraint-aware search without the high-quality space has nothing to find. The two contributions are a matched pair, and the ablations price each: CGA beats SA/GA/random in half the exploration steps, and beats all four classic constraint-handling GA techniques, with the gap widening on larger problems.

A GEMM’s journey to TensorCore

the same rules, re-pointed, target DL Boost or VTA — porting is rule editing
convolutions tensorize via im2col before the mapping

Why it works

• Every constraint originates in a schedule primitive → generating them together by static analysis makes hundreds-per-operator scale free, shape-adaptive, and drift-proof → the search space contains all valid programs and only valid programs.
• The space is a formal CSP → industrial constraint solvers can sample it uniformly (RandSAT) → initial populations and all offspring are valid, so the entire measurement budget goes to real programs.
• Adding constraints to a satisfiable CSP only shrinks its solution set → crossover-by-pinning and mutation-by-unpinning keep every offspring inside the original valid region → the validity guarantee costs nothing and needs no repair machinery.
• Key variables come from cost-model feature importance → the pins preserve exactly the choices that predict performance → parental good genes survive evolution, which SAT-decoder and penalty methods structurally lose.
• Pruning mediocre-invalid buffer zones concentrates performance but sharpens the landscape → constraint-preserving search is the necessary complement to the constrained space → the two halves of Heron are a matched pair, each ablated separately.

What it costs

• Rules are still human artifacts. The schedule rules (S1–S3) and constraint rules (C1–C6) encode expert abstractions of DLA families; a genuinely novel accelerator paradigm (or an intrinsic the pattern-matcher cannot recognize) needs new rules — automation moved up a level, not away.
• Per-shape search remains. Heron searches per operator and shape configuration (~90 minutes per operator at 2,000 trials) — a library-building workflow, not a JIT; dynamic shapes inherit the classic tensor-compiler weakness.
• Solver in the loop. CGA spends 23% of compile time in constraint solving; the approach leans on modern CSP solver efficiency, and pathological constraint systems could bite.
• Cost model dependence. Key-variable extraction and candidate ranking both trust XGBoost feature importances; the CGA-1 ablation shows random key variables erode gains, and model accuracy decays on the largest problems.
• Hardware-measurement dominance. 76% of compile time is timing programs on the device — Heron reduces wasted measurements but cannot escape needing the accelerator in hand, unlike forecast-only approaches.

The evaluation

Three commercial-grade accelerators with different constraint regimes (TensorCore’s shape menus, DL Boost’s fixed VNNI shapes, VTA’s buffer/order limits), operator- and network-level benchmarks, four auto-compiler baselines plus vendor libraries, search-space visualizations, algorithm ablations against classic constraint handling, and compile-time accounting.

Check yourself

Sources

• ACM DL: Heron: Automatically Constrained High-Performance Library Generation for Deep Learning Accelerators — ASPLOS 2023 (open access)