Kernel Auto-Tuning

This defines the parallel execution hierarchy on an accelerator. The thread block size (e.g., 128, 256, 512 threads) and the grid size (number of blocks) determine how work is mapped to hardware cores (SMs/CUs).

• Optimization Goal: Maximize occupancy—the number of active warps/wavefronts per core—to hide memory latency. The optimal size balances register usage, shared memory limits, and hardware warp schedulers.
• Hardware Constraints: Limited by maximum threads per block (e.g., 1024 on modern GPUs) and available shared memory per block.

Tiling partitions loops to fit working data sets into faster, on-chip memory (e.g., shared memory on GPUs, scratchpad memory on NPUs).

• Key Parameters: Tile dimensions for input matrices, filter weights, and output channels.
• Optimization Goal: Maximize data reuse within a tile to reduce accesses to slower global memory (HBM). Larger tiles improve reuse but must fit within limited on-chip memory capacity.
• Example: In a matrix multiplication C = A x B, tuning the TILE_M, TILE_N, and TILE_K parameters for the blocking of the three matrices.

This optimizes how data is loaded from memory into registers. Coalesced memory accesses are critical for performance.

• Parameters: Stride of memory loads, use of vectorized loads/stores (e.g., loading 4 or 8 floats at once), and explicit prefetching.
• Optimization Goal: Achieve peak memory bandwidth by ensuring consecutive threads access consecutive memory addresses. Auto-tuners test different loop unrolling factors and data layout transformations (e.g., NHWC vs. NCHW) to find the most efficient pattern.

These compiler transformations increase instruction-level parallelism (ILP) and overlap memory operations with computation.

• Loop Unrolling Factor: Controls how many loop iterations are explicitly written out, reducing branch overhead and enabling more scheduling flexibility for the compiler.
• Software Pipelining Depth: Determines the schedule for overlapping loads, computations, and stores within a single loop iteration.
• Optimization Goal: Keep the arithmetic logic units (ALUs) saturated by hiding the latency of memory operations and dependent instructions.

On architectures like GPUs, shared memory is divided into banks. Simultaneous accesses to the same bank cause serialization, or bank conflicts.

• Parameter: The memory layout stride or padding applied to data structures in shared memory.
• Optimization Goal: Reorganize data (e.g., adding padding columns to a matrix in shared memory) so that concurrently accessing threads target different memory banks, enabling full parallel bandwidth.
• Impact: Eliminating bank conflicts can improve kernel performance by 2x or more for memory-bound operations.

For some operations, multiple algorithmic variants exist. Auto-tuning selects the best algorithm for the given problem size and hardware.

• Common Examples:
  • Convolution: Choosing between direct, im2col+GEMM, Winograd, or FFT-based algorithms.
  • Matrix Multiplication: Selecting a tiling strategy optimized for specific matrix shapes (e.g., tall-skinny vs. square).
  • Reduction: Choosing a tree-reduction algorithm optimized for the number of elements and block size.
• Optimization Goal: The tuner evaluates each variant's performance empirically, as the theoretical best choice can vary with hardware microarchitecture.

An analytical performance model used to guide and validate auto-tuning efforts. It visualizes the attainable performance of a kernel as a function of its operational intensity.

• Purpose: Provides theoretical upper bounds (rooflines) based on hardware limits: peak compute (FLOPS) and peak memory bandwidth.
• Use in Tuning: Helps diagnose whether a kernel is compute-bound or memory-bound, directing the auto-tuner to focus on optimizing the limiting factor (e.g., improving data reuse for memory-bound kernels).
• Key Metric: Operational Intensity (Ops/Byte) determines a kernel's position on the roofline chart.

A compiler-level optimization that combines multiple sequential operations into a single, fused kernel. This is a primary target for auto-tuning, as fusion changes the fundamental structure of the computation.

• Goal: Minimize intermediate memory writes and reads between operations (e.g., fuse Conv + Bias + ReLU).
• Auto-Tuning Challenge: The optimal fusion pattern and the parameters for the resulting fused kernel are highly hardware-dependent.
• Benefit: Reduces kernel launch overhead and improves data locality, directly impacting the memory-bound roofline.

A fundamental transformation explored during auto-tuning that partitions loop iterations into smaller blocks or 'tiles' to fit within fast cache memory.

• Objective: Maximize data reuse from cache (SRAM) and minimize accesses to slower global memory (HBM/DRAM).
• Tunable Parameters: Tile sizes for each loop dimension are critical optimization knobs. The optimal sizes depend on cache hierarchy sizes, data types, and hardware thread scheduling.
• Impact: Directly influences the operational intensity of a kernel, potentially moving it from memory-bound toward compute-bound.

Neural Architecture Search that incorporates hardware metrics as direct objectives. While NAS searches over model architectures, kernel auto-tuning searches over implementation parameters for a fixed operation.

• Synergy: A model discovered by Hardware-Aware NAS still requires highly tuned kernels for each of its operations to achieve the predicted latency/energy benefits.
• Two-Stage Optimization: NAS finds the optimal model macro-architecture; auto-tuning finds the optimal micro-architecture (kernel implementation) for that model on target hardware.
• Joint Optimization: Some advanced systems perform lightweight tuning during the NAS search to make hardware cost estimates more accurate.

A compilation strategy where kernel code is generated and optimized at runtime. This is the natural execution environment for online kernel auto-tuning.

• Advantage for Tuning: Allows optimizations (like tile sizes) to be specialized for exact runtime parameters (e.g., input tensor shapes, batch size) which may be unknown at traditional compile time.
• Process: The JIT compiler can invoke an auto-tuner to search for the best kernel configuration for the specific runtime context, caching the result for future reuse.
• Trade-off: Accepts a one-time tuning overhead for long-running or frequently executed kernels to achieve optimal performance.