Auto-Tuning

The core of auto-tuning is the systematic search across a configuration space, which is the set of all possible combinations of tunable parameters. Key parameters include:

• Workgroup/Thread Block Size: The number of threads grouped for cooperative execution.
• Tile Size: Dimensions of data blocks for optimizing cache locality.
• Loop Unrolling Factor: The number of times a loop body is replicated.
• Vectorization Factor: The number of data elements processed per SIMD instruction. The search aims to find the single point in this multi-dimensional space that minimizes execution time or maximizes compute throughput for a given workload and hardware target.

Auto-tuning employs intelligent search strategies to navigate the configuration space efficiently, avoiding exhaustive searches which can be prohibitively expensive.

• Bayesian Optimization: A model-based technique that uses a probabilistic surrogate model (like a Gaussian Process) to predict performance and guide the search, expertly balancing exploration of new regions and exploitation of known good areas.
• Performance Models: Analytical or machine-learned models that estimate execution time based on parameters and hardware specs (e.g., memory bandwidth, compute throughput). These models can prune the search space or provide a warm start for iterative searches.
• Evolutionary Algorithms: Techniques like genetic algorithms that evolve populations of configurations over generations based on fitness (performance).

Auto-tuning is inherently hardware-aware. The optimal configuration is highly dependent on the target NPU's microarchitecture.

• Memory Hierarchy: Tuning must account for cache sizes (L1, L2, shared memory) and memory coalescing patterns to avoid being memory bound.
• Parallel Resources: Parameters are tuned to maximize occupancy—the utilization of available cores, ALUs, and thread slots—while minimizing thread divergence.
• Vendor Intrinsics: The search may include parameters that map to vendor-specific instructions or hardware intrinsics exposed via an SDK for optimal low-level control. A configuration tuned for one NPU (e.g., from NVIDIA) will likely be suboptimal for another (e.g., from Google or Intel).

Auto-tuning is not a standalone tool but is deeply integrated into the AI compilation pipeline.

• Kernel Tuners: Tools like AutoTVM (for TVM), Triton's autotuner, or vendor-specific tuners operate at the kernel level, generating and benchmarking many code variants.
• Graph-Level Tuning: In frameworks like TensorFlow or PyTorch with XLA, tuning can occur at the level of the computational graph, deciding operator fusion strategies and data layout transformations.
• Just-In-Time (JIT) vs. Ahead-of-Time (AOT): Tuning can be performed offline (AOT), caching optimal configurations for deployment, or online (JIT) at runtime, adapting to dynamic input shapes or hardware states, though with an upfront cost.

Auto-tuning relies on continuous, precise measurement to evaluate candidate configurations.

• Kernel Profilers: Tools that measure actual execution time, hardware performance counters (cache misses, pipeline stalls), and resource usage for each tested configuration.
• Bottleneck Analysis: Profiling data identifies if a kernel is compute bound, memory bound, or latency-bound, guiding the tuner on which parameters to prioritize.
• Low-Overhead Measurement: Techniques like sampling profilers or repeated execution with high-resolution timers are used to gather accurate data without excessive slowdown during the search process.

Auto-tuning is applied across the AI stack to solve real performance problems.

• Deep Learning Frameworks: Auto-tuning is used to find optimal convolution or matrix multiplication (GEMM) kernels, which are foundational to neural networks.
• Domain-Specific Libraries: Libraries for image processing, scientific computing, or cryptography use auto-tuning to adapt to different CPU/GPU/NPU architectures.
• Example Tools:
  • TVM AutoTVM / Ansor: For deep learning model compilation.
  • CLBlast / CLTune: For OpenCL-based linear algebra.
  • CUDA cuBLASLt: Uses internal heuristics and tuning for GEMM operations.
  • Triton: Its compiler includes an autotuner for GPU/NPU kernels written in its Python-like language.

An analytical or machine-learned model that predicts the execution time or resource usage of a computational kernel based on its parameters, hardware characteristics, and input data. Performance models are central to efficient auto-tuning, as they can guide the search process without requiring exhaustive, time-consuming execution of every configuration.

• Analytical models use first-principles equations based on hardware specs (e.g., peak FLOPS, memory bandwidth) and kernel characteristics.
• Machine-learned models (e.g., regression, neural networks) are trained on profiling data from a subset of configurations to predict performance for unseen ones.
• A high-quality model allows an auto-tuner to prune the search space and focus evaluation on the most promising regions.

The set of all possible combinations of tunable parameters that define the search domain for an auto-tuning process. For an NPU kernel, this space is defined by discrete and continuous variables that control its execution.

• Key parameters include workgroup size, tile size, loop unrolling factor, vectorization factor, and memory padding.
• The size of the space grows exponentially with the number of parameters, making brute-force search infeasible.
• Auto-tuning strategies involve intelligently sampling or traversing this high-dimensional space to find the optimal point (e.g., shortest runtime, lowest power).

A sequential, model-based optimization technique that uses a probabilistic surrogate model to guide the search for optimal parameters. It is particularly effective for auto-tuning expensive-to-evaluate functions, like kernel execution.

• The process balances exploration (testing uncertain regions) and exploitation (refining known good regions).
• A Gaussian Process is a common surrogate model that provides a mean prediction and uncertainty estimate for untested configurations.
• An acquisition function (e.g., Expected Improvement) uses the model's predictions to select the next most promising configuration to evaluate.
• This method typically finds near-optimal configurations with far fewer evaluations than random or grid search.

The process of identifying the primary limiting factor that restricts the overall performance of a system or application. In auto-tuning, this analysis determines which resource constraint (e.g., compute, memory bandwidth, latency) the tuning process should target.

• A compute-bound kernel's execution time is limited by ALU speed; tuning may focus on increasing occupancy or improving instruction-level parallelism.
• A memory-bound kernel is limited by memory bandwidth; tuning focuses on optimizing memory coalescing, cache hit rates, and tile sizes to reduce data movement.
• Resource contention from concurrent kernels can create a shared-resource bottleneck, requiring system-level tuning.

The systematic exploration of a configuration space to optimize the performance of an NPU kernel. This is the core algorithmic component of any auto-tuner.

• Exhaustive/Grid Search: Evaluates every combination in a discretized space. Guarantees finding the optimum but is computationally prohibitive for large spaces.
• Random Search: Samples configurations randomly. Often more efficient than grid search in high-dimensional spaces.
• Evolutionary Algorithms (e.g., Genetic Algorithms): Use principles of selection, crossover, and mutation to evolve a population of configurations toward better performance.
• Gradient-Based Search: Used when the performance landscape is differentiable with respect to parameters, though this is rare for discrete hardware parameters.