Halide paper

The claim

The claim is narrow and load-bearing: the definition of a pipeline and the order in which it is computed are independent, and a compiler can be given both. A Halide algorithm is a set of stages, each a pure function over an index domain. A schedule says how to walk those domains: reorder, split, fuse, tile, vectorise, parallelise, and where to compute and store each intermediate. Change the schedule and the output is bit-identical. Change the algorithm and it is a different program.

Why it is the ancestor

Tiling and fusion are schedule decisions, and this is where they were first given a vocabulary separate from the loop nest. compute_at(consumer, level) is fusion: the producer is evaluated inside the consumer’s loop and its buffer shrinks to a tile. store_at is the storage decision that follows. A fusion pass in a modern compiler answers the same two questions, and the paper’s locality analysis is the argument for why those answers move performance by multiples on one piece of hardware.

What it does not claim

It is not a general-purpose language, not an autotuner, and not a claim that one schedule ports everywhere. The embedded C++ DSL is the vehicle; the split is the contribution, and the schedules in the paper are written by hand for image pipelines.

What to read

The split itself, then the discussion of locality, recomputation and bounds inference. Skim the stencil benchmarks if imaging is not your problem.

What you should be able to do

Given a fused pointwise chain in your own compiler, name the Halide decisions it encodes: the fusion level, the tile size, the storage scope, and what is recomputed. linalg tiling and bufferisation expose the same decision space, and naming it in these terms makes the compiler’s choices legible.

Things that break

Taking the separation to mean the schedule is free. Every schedule is checked against bounds inference and storage limits, and an illegal one fails to compile. The other failure is adopting the vocabulary without the legality analysis, then splitting a reduction into tiles that do not reassociate. The tell is a schedule that compiles, runs fast, and disagrees with the reference at the tile edges.