When compiling a computational kernel—such as a matrix multiplication, a convolution, or a stencil operation—the mathematical definition of the algorithm is only half the battle. The other half is determining the execution schedule: how the computation is broken into blocks, how loops are reordered and unrolled, and how data is mapped to hardware threads.
On modern hardware like GPUs, TPUs, and multicore CPUs, the execution schedule dictates performance. If a schedule is poorly tuned, the processor spends most of its time stalled, waiting for data to arrive from main memory. If it is well-tuned, data remains trapped in fast, on-chip caches, and the execution units run at near-theoretical peak capacity.
Historically, finding the optimal schedule required human experts to spend weeks hand-writing assembly code. Today, a major research direction focuses on automated schedule optimization (or hardware-aware autotuning). This paradigm decouples the mathematical logic of an operation from its physical execution strategy, using automated systems to search for the most efficient schedule on any given chip architecture.
The Tiling Problem and the Search Space
To understand why automated tuning is necessary, consider the concept of tiling (or blocking). A large matrix multiplication cannot fit entirely within a processor's fast on-chip registers or shared memory. To compute it efficiently, the operation must be sliced into smaller sub-matrices—tiles—that fit perfectly within the cache hierarchy.
Choosing the right tile size involves a delicate balancing act:
- Too large: The tile spills out of the cache into slow main memory, causing a catastrophic drop in throughput.
- Too small: The processor does not reuse data effectively, and the overhead of managing loops and synchronizing threads overwhelms the actual computation.
The "sweet spot" changes completely with every hardware generation, input data shape, and architectural quirk. As Mingzhen Li et al. note in The Deep Learning Compiler: A Comprehensive Survey, execution parameters like loop orders and tiling sizes form a massive, high-dimensional search space. Manually navigating this space for every new chip is unsustainable. As a result, frameworks often rely on manual heuristics that fail to achieve peak performance, a limitation highlighted by Yuwei Hu et al. in the context of graph neural networks in FeatGraph: A Flexible and Efficient Backend for Graph Neural Network Systems.
Empirical Autotuning: Learning by Doing
The most straightforward way to find the best schedule is to try many variations and measure which one runs the fastest. This is known as empirical autotuning.
Instead of compiling a single static binary, an empirical autotuner uses runtime code generation to compile dozens or hundreds of kernel variants on the fly. In PyCUDA and PyOpenCL: A scripting-based approach to GPU run-time code generation, Andreas Klöckner et al. demonstrated the power of deferring optimization decisions until execution. By running micro-benchmarks of different kernel variants directly on the target hardware, the software automatically adapts to the underlying architecture without manual intervention.
This feedback-driven approach works well across different scales of computation. For instance, Daniele G. Spampinato showed in A Basic Linear Algebra Compiler that feedback-driven search can be applied effectively to small, fixed-size linear algebra operations, outperforming general-purpose libraries by discovering highly specific tiling strategies. Similarly, for specialized deep learning operations, Jintao Meng et al. utilized an empirical search strategy in Automatic Generation of High-Performance Convolution Kernels on ARM CPUs for Deep Learning to automatically discover optimal tile sizes and scheduling parameters for Winograd convolutions across diverse ARM architectures.
Analytical Models: Math Over Muscle
While empirical tuning guarantees accuracy, evaluating hundreds of configurations on physical hardware is time-consuming. To accelerate this process, researchers build analytical cost models—mathematical abstractions of the hardware that predict how fast a given schedule will run without actually executing it.
A foundational tool for this is the Roofline model, adapted to GPUs by Haipeng Jia et al. in GPURoofline: A Model for Guiding Performance Optimizations on GPUs. By plotting a kernel's arithmetic intensity against the hardware's theoretical memory and compute bounds, the model reveals whether a kernel is bottlenecked by memory bandwidth or math. Compilers can use these models to instantly discard sub-optimal schedules. For example, Kazuaki Matsumura et al. demonstrated in AN5D: automated stencil framework for high-degree temporal blocking on GPUs that roofline-based performance models can effectively prune the massive parameter space required for complex temporal stencil blocking.
More granular analytical models incorporate specific hardware constraints like register files and shared memory capacities. In A Performance Model for GPU Architectures that Considers On-Chip Resources: Application to Medical Image Registration, Junhao Wu et al. developed an analytical cost function that mathematically identifies the optimal thread block size by minimizing predicted execution time. By encoding hardware limits directly into the equation, the system avoids exhaustive empirical testing while maximizing hardware utilization.
Other approaches combine heuristics with mathematical optimization algorithms. In TSM2X: High-performance tall-and-skinny matrix-matrix multiplication on GPUs, Cody Rivera et al. used a heuristic performance model that tracks streaming multiprocessor occupancy and bandwidth utilization, applying gradient descent to automatically converge on the ideal tile sizes for irregular matrix shapes.
Algorithmic and Machine Learning-Driven Search
As hardware architectures become more heterogeneous, pure analytical models can become too rigid, while pure empirical search remains too slow. Modern optimization frameworks increasingly bridge this gap using advanced search algorithms and machine learning.
Instead of guessing schedules, these systems treat schedule optimization as a guided search problem. In A Unified Optimization Approach for CNN Model Inference on Integrated GPUs, Leyuan Wang et al. introduced a machine-learning-based search strategy that optimizes execution parameters (such as tile sizes and loop unrolling factors) at both the individual tensor level and the overall computational graph level. This automated approach generates schedules that frequently outperform hand-written vendor libraries.
When navigating highly constrained environments, such as edge devices, compilers deploy sophisticated search heuristics. Mohammadali Shakerdargah et al., in MAS-Attention: Memory-Aware Stream Processing for Attention Acceleration on Resource-Constrained Edge Devices, leveraged Monte Carlo Tree Search (MCTS) and Genetic Algorithms to automatically discover optimal tiling parameters that balance the specific compute-to-memory ratios of edge hardware.
To bypass the overhead of exhaustive search entirely, researchers are also exploring hybrid approaches. Adrián Castelló 0001 et al. demonstrated in Experience-guided, mixed-precision matrix multiplication with apache TVM for ARM processors that combining expert-defined algorithmic templates with analytical modeling can reduce the optimization search time by 48x while matching the performance of state-of-the-art auto-schedulers.
Finally, as the field moves toward autonomous optimization agents, benchmarks like the one proposed by Arya Tschand et al. in JAXBench: Benchmarking Autonomous TPU Kernel Optimization show that providing language-model agents with structured search tools and hardware documentation allows them to iteratively refine block sizes and schedules, ultimately outperforming standard compiler heuristics.
Why It Works: The Core Intuition
Automated schedule optimization works because it separates intent from implementation.
A programmer or a high-level framework defines what needs to be computed (e.g., $C = A \times B$). The automated tuning framework is responsible for figuring out how to compute it on a specific piece of silicon. By transforming the "how" into a mathematical or empirical optimization problem, the system can evaluate non-intuitive configurations—such as asymmetrical tile sizes or complex loop unrolling factors—that a human engineer would rarely think to try, unlocking the true performance potential of modern hardware.
Key Foundational Work
Hierarchical N-body Simulations with Autotuning for Heterogeneous Systems (2012) — contributed 2 concept elements to this direction.
A model-driven partitioning and auto-tuning integrated framework for sparse matrix-vector multiplication on GPUs (2011) — contributed 1 concept elements to this direction.
PyCUDA and PyOpenCL: A scripting-based approach to GPU run-time code generation (2011) — contributed 1 concept elements to this direction.