Lecture 18: Domain-Specific Languages and Autotuning

What this lecture covers

Guest lecturer Saman Amarasinghe asks how you get near-hand-optimized performance without forcing every programmer to hand-tune code for every machine and dataset. His answer is domain-specific languages that separate the algorithm (what to compute) from the schedule (how to compute it), illustrated with GraphIt for graph processing and Halide for image processing, plus autotuning frameworks like OpenTuner that search the schedule space automatically.

This is a guest lecture within MIT's performance engineering course, connecting to the course's ongoing project that uses OpenTuner. After watching, you can explain why separating algorithm from schedule helps performance portability, describe the parallelism/locality/redundant-work trade-off that both GraphIt and Halide schedules navigate, and understand why autotuning beats hand-built models or hard-coded heuristics for large search spaces.

Key ideas

• Domain-specific language (DSL): a language restricted to one problem domain, which makes domain knowledge explicit so both programmers and compilers can exploit it, unlike general-purpose languages or libraries where such structure is hidden.
• Algorithm vs. schedule: GraphIt and Halide both separate the algorithm (what result to compute) from the schedule (execution order, parallelization, data layout), so changing performance strategy doesn't require rewriting the algorithm.
• Push vs. pull graph traversal: pushing updates to neighbors gives parallelism but needs atomic updates to avoid races; pulling updates from neighbors avoids races (each node only writes itself) but may do wasted work checking neighbors with nothing new.
• Graph partitioning trade-off: partitioning a graph improves locality and can add parallelism, but introduces extra bookkeeping and possibly replicated nodes, illustrating that optimizations exist on a trade-off surface rather than being universally best.
• Parallelism, locality, redundant work: the three axes performance engineers balance across both DSLs; too much parallelism is wasted, poor locality stalls on memory, and extra recomputation can trade one for the other.
• Decoupled compute in Halide: describing an image-processing pipeline as pure functions (the algorithm) separately from tiling, fusion, vectorization and storage granularity choices (the schedule) let Halide match or beat hand-tuned C++ and GPU code with far less code.
• Model-based, heuristic, and exhaustive search limitations: analytic performance models omit details that turn out to matter, hard-coded heuristics (like a sort's magic size-16 cutoff) go stale as hardware changes, and exhaustive search is often computationally infeasible.
• Autotuning (OpenTuner): an ensemble search strategy that samples the schedule space, measures real performance, and adaptively favors techniques (such as hill climbing or random search) that are currently working, finding good schedules far faster than exhaustive search and sometimes better than hand-tuned ones.

Walkthrough

Why domain-specific languages help performance (2:05)

The lecture opens by contrasting general-purpose languages, which must support everything and so can't exploit domain structure, with DSLs that make a domain's properties explicit. This gives engineering benefits like clarity and testability, and lets compilers apply domain-specific algebraic simplifications and idioms that would be too narrow to build into C++. It also lets a compiler own performance decisions that would otherwise become brittle hand-tuned code that ages badly as architectures change.

GraphIt and the shape of graph algorithms (6:08)

Using PageRank as a running example, the lecture surveys where large-scale graph processing shows up (search, maps, recommendations, fraud detection) and distinguishes topology-driven algorithms, which touch the whole graph, from data-driven algorithms, which only traverse a local region. It walks through push versus pull update strategies and their different race conditions and inefficiencies, then discusses how graph shape (power-law social networks versus bounded-degree road networks) changes which optimization performs best, motivating a search over a large optimization trade-off space rather than a single fixed strategy.

Writing GraphIt: algorithm and schedule (24:18)

The lecture shows GraphIt's algorithm language, where operations like edge-set apply and vertex-set apply express PageRank concisely, and then its separate schedule language, where annotations select push versus pull traversal, parallelization, and partitioning without touching the algorithm code. Benchmark results show GraphIt's flexibility lets it stay competitive across many different graphs and algorithms, where other frameworks with fixed built-in strategies are fast on some inputs and much slower on others.

Halide: decoupling algorithm from schedule for images (33:30)

Turning to image processing, the lecture introduces Halide with a 3x3 blur example: a straightforward C implementation is far slower than a hand-tuned version using tiling, loop fusion, and vectorization, but Halide's schedule language lets a programmer reach that hand-tuned performance from a much simpler pipeline description. A case study describes an Adobe engineer needing months to hand-optimize a local Laplacian filter, while a Halide reimplementation beat that performance in one day and, once ported to GPU, ran nine times faster still.

Balancing parallelism, locality, and redundant work in Halide schedules (38:39)

The lecture works through concrete scheduling choices: how much parallelism is useful given the number of cores, how loop traversal order affects whether data stays in cache, and how recomputing values redundantly at boundaries can sometimes be cheaper than synchronizing between parallel workers. It frames storage granularity and computation granularity as a spectrum between fully redundant recomputation and fully cached storage, with real pipelines landing at different points depending on the stage.

Real-world adoption and comparison across domains (48:47)

The lecture notes Halide's adoption in Google's YouTube video pipeline, Android camera processing, Adobe Photoshop, and Qualcomm's Snapdragon image processor, framing these as evidence that schedule-based DSLs solve a real industrial problem. A discussion with students draws out the shared pattern between GraphIt and Halide and considers where similar approaches might help, such as scientific computing domains with similarly code-heavy but understaffed performance needs.

From heuristics to autotuning (59:59)

The lecture contrasts three ways to pick tuning parameters: analytic models that omit important effects, hard-coded heuristics that go stale (illustrated by a sort routine's fixed size-16 cutoff dating to 1995), and exhaustive search that's often too slow. It introduces autotuning, as implemented in OpenTuner, which samples the search space, measures real runtime, and adaptively shifts effort toward techniques currently finding improvements, closing with a case where OpenTuner found GraphIt schedules faster than exhaustive search and occasionally better than hand-picked ones.

Before you watch

• Familiarity with parallel loops, races, and locks helps, since push/pull graph updates and Halide scheduling both hinge on these ideas.
• Having used or read about OpenTuner from earlier assignments in this course gives useful context for the autotuning section.
• No prior graph algorithms or image processing background is assumed; the lecture introduces both.

Check your understanding

1. Why does separating "algorithm" from "schedule" make performance tuning easier in both GraphIt and Halide?
2. What is the trade-off between push-style and pull-style graph updates, and why does pull avoid needing atomic operations?
3. Why can graph partitioning improve locality while also adding overhead or reducing parallelism?
4. In Halide's parallelism/locality/redundant-work trade-off, give an example where doing extra (redundant) computation can improve overall performance.
5. Why did a hard-coded heuristic like a sort algorithm's size-16 cutoff stop being a good choice over time, and how does autotuning avoid this problem?