Kernel Auto-Tuning

The tile size (or block size) determines how the input data is partitioned for processing. This is the most critical parameter for optimizing data locality and cache utilization.

• Impact: Directly affects the balance between computation and memory access (operational intensity). An optimal tile size maximizes data reuse within fast cache memory, minimizing expensive trips to main RAM.
• Example: For a matrix multiplication kernel, tuning the M, N, and K tile dimensions for the inner loops to match the sizes of the CPU's L1/L2 cache or a GPU's shared memory.
• Trade-off: Too small a tile increases loop overhead; too large a tile evicts useful data from cache.

This defines the parallelism granularity, specifying how many concurrent threads (CPU) or work-items (GPU) are launched and how they are organized.

• Thread Count: The total number of parallel execution units. On CPUs, this often aligns with core count and hyper-threading. On GPUs, it must saturate the massively parallel hardware.
• Work-Group/Block Size: On GPUs and other accelerators, threads are grouped into cooperative units (CUDA thread blocks, OpenCL work-groups). The size of these groups must align with hardware limits (e.g., warp/wavefront size) and shared memory capacity.
• Grid/NDRange Size: The total number of work-groups launched, which partitions the overall problem.

These parameters control instruction-level parallelism (ILP) by determining how many loop iterations are processed per instruction or are explicitly unrolled.

• Vector Width: The number of data elements processed by a Single Instruction, Multiple Data (SIMD) operation. The tuner must match the hardware's SIMD register width (e.g., 256-bit AVX2, 512-bit AVX-512).
• Loop Unroll Factor: The number of times a loop body is duplicated. This reduces branch overhead and increases opportunities for instruction scheduling and register reuse.
• Constraint: Excessive unrolling can increase register pressure and cause spilling to slower memory, degrading performance.

Tuning how data is arranged in memory and accessed by threads to ensure coalesced, stride-1 accesses that maximize memory bandwidth.

• Data Layout Transformation: Choosing between formats like NCHW (common in frameworks) and NHWC (often faster on GPUs) for convolutional networks.
• Coalescing: On GPUs, ensuring that consecutive threads access consecutive memory addresses to enable a single, wide memory transaction.
• Padding: Adding padding to tensor dimensions to avoid cache line thrashing or to meet alignment requirements for vectorized loads.

Parameters that orchestrate the overlap of memory operations with computation to hide latency.

• Software Prefetch Distance: How many loop iterations ahead to issue a prefetch instruction for data, allowing it to be loaded into cache before it is needed.
• Pipeline Stages: For deeply pipelined functional units (e.g., on CPUs), scheduling instructions to keep the pipeline full and avoid stalls.
• Double Buffering: A technique where two buffers are used: one is being processed while the other is being loaded, fully overlapping memory transfer with computation.

Selecting the optimal low-level instructions and execution schedules for a specific microarchitecture.

• Intrinsic Functions: Choosing which vendor-specific intrinsics (e.g., Intel AVX-512, ARM NEON/SVE) to use for critical operations.
• Scheduling for Latency vs. Throughput: Prioritizing instruction mixes that minimize dependency chain latency or maximize overall throughput, depending on the kernel's bottleneck.
• Tensor Core/Matrix Engine Usage: On modern GPUs and NPUs, tuning parameters to efficiently utilize dedicated matrix multiplication units, such as NVIDIA's Tensor Cores or AMD's Matrix Cores, which have specific data type and alignment requirements.

A compiler optimization that combines multiple sequential operations (e.g., convolution, bias add, activation) into a single, fused kernel. This reduces kernel launch overhead and intermediate memory traffic by keeping data in registers or cache between operations. It is a prerequisite for effective auto-tuning, as the fused kernel's parameters become the search space.

• Example: Fusing a 2D convolution, bias addition, and ReLU activation into one conv_bias_relu kernel.
• Benefit: Eliminates the need to write temporary tensors back to main memory between layers.

A critical loop transformation and a primary target for auto-tuning. It partitions loop iterations into smaller blocks or tiles to fit data into fast, on-chip memory (caches or shared memory). The choice of tile size is hardware-specific and has a dramatic impact on performance.

• Auto-Tuning Target: The search algorithm experiments with different tile dimensions (e.g., 32x32, 64x64, 128x16).
• Objective: Maximize data locality and minimize costly accesses to slower main memory (DRAM).

An analytical or machine-learned function that predicts the execution cost (latency, throughput) of a kernel implementation given its parameters and hardware characteristics. It guides the auto-tuning search process.

• Heuristic Models: Use rules-of-thumb based on hardware specs (peak FLOPS, bandwidth).
• Learned Models: Neural networks trained on profiling data from previous kernel runs.
• Role in Auto-Tuning: Prunes the vast search space by quickly estimating performance without running every candidate, making the search feasible.

A complementary technique where the compiler uses data from actual program execution (profiles) to inform optimizations. For kernel auto-tuning, runtime profiling is the core mechanism.

• Process:
  1. The auto-tuner generates multiple kernel variants.
  2. Each variant is executed with representative input data on the target hardware.
  3. Precise performance metrics (e.g., cycles, cache misses) are collected.
  4. The fastest variant is selected for deployment.
• Difference from Static Analysis: PGO/Auto-tuning makes decisions based on empirical measurement, not just static code analysis.

A visual performance model used to analyze the performance upper bounds of a kernel. It plots attainable GFLOPs/sec against operational intensity (operations per byte of DRAM traffic).

• How it Relates to Auto-Tuning:
  • Identifies if a kernel is compute-bound or memory-bound.
  • Guides the tuning objective: for memory-bound kernels, optimize for data reuse (tiling); for compute-bound kernels, optimize for instruction-level parallelism (unrolling, vectorization).
  • Provides a sanity check for auto-tuning results—the optimal kernel should sit near the 'roof' of the model.

A powerful mathematical framework for the analysis and transformation of loop nests. It provides a systematic way to reason about complex loop optimizations that are often the subject of auto-tuning.

• Represents Loops as sets of integer points within polyhedra, enabling precise dependency analysis.
• Enables Transformations like loop tiling, fusion, skewing, and interchange in a unified, semantics-preserving way.
• Connection to Auto-Tuning: The polyhedral model can generate a large, legal space of loop transformations. Auto-tuning can then be used to empirically search this space for the transformation parameters that yield the best performance on specific hardware.