Tile Size Selection

The foremost goal is to ensure the data accessed within a tile fits within the target cache level (e.g., L1, shared memory). This minimizes expensive accesses to slower, higher-level memory (e.g., global memory, DRAM).

• Temporal Locality: Data loaded into the cache is reused multiple times by computations within the tile before being evicted.
• Spatial Locality: The tile dimensions are chosen so that consecutive memory accesses are to adjacent addresses, enabling efficient memory coalescing.
• Objective: Select a tile size where the working set (input, output, and intermediate data) does not exceed the cache capacity, preventing capacity misses.

Tile dimensions directly map to the parallel execution resources of an NPU, such as its cores, warps, or vector units. The size must align with hardware constraints to achieve full occupancy.

• Workgroup Mapping: The tile is often assigned to a thread block or workgroup. The tile size (e.g., 128x128 elements) must be divisible by the workgroup size (e.g., 256 threads) to ensure balanced load distribution.
• Reducing Synchronization: Larger tiles can reduce the frequency of global synchronization points between parallel units, but may increase register pressure.
• Objective: Choose tile dimensions that saturate the NPU's parallel compute units without causing resource contention or thread divergence.

Tile size is a primary lever to shift a kernel from being memory-bound to compute-bound. The ideal size increases the arithmetic intensity (operations per byte of data moved) within the tile.

• Memory-Bound Scenario: Small tiles result in high overhead from frequent data movement, leaving compute units idle.
• Compute-Bound Scenario: Larger tiles increase the number of operations performed on data while it resides in fast cache, better utilizing the ALUs.
• Objective: Find the tile size that maximizes the ratio of compute operations to memory transactions, moving the workload closer to the hardware's peak compute throughput.

Effective tiling reduces the total volume of data transferred between memory hierarchy levels. This directly lowers execution time and power consumption.

• Redundant Load Elimination: By reusing data within a tile, the same memory address is not fetched multiple times from slow memory.
• Granularity Optimization: Tile dimensions are chosen to match the NPU's burst transaction size or cache line length, ensuring full utilization of each memory transfer.
• Objective: Select tile dimensions that minimize the total bytes read/written to global memory per computation, thereby reducing pressure on memory bandwidth.

Tile size parameters (e.g., TILE_M, TILE_N, TILE_K for matrix multiplication) form the core dimensions of the configuration space explored by an auto-tuner.

• Discrete Parameters: Tile sizes are typically powers of two or multiples of hardware-specific dimensions (e.g., vector width), creating a finite but large search space.
• Performance Modeling: The relationship between tile size and performance (latency, throughput) is complex and non-linear, making empirical auto-tuning or Bayesian optimization necessary.
• Objective: Establish a logical, constrained parameter space that a kernel tuner can efficiently navigate to find the globally optimal configuration for a given NPU and kernel.

Tile data must be staged in fast, but limited, on-chip memories like scratchpad SRAM or registers. Tile size selection is a direct trade-off between these resources.

• Register File Pressure: Larger tiles or more complex operations per element may require more registers per thread, potentially reducing occupancy if the register file is exhausted.
• Shared Memory Allocation: Tiles are often staged in software-managed cache (shared memory). The tile size must fit within the allocated shared memory budget per thread block.
• Objective: Choose tile dimensions that optimally partition the available on-chip memory between registers and shared memory to avoid pipeline stalls due to resource limits.

The foundational compiler transformation that introduces tile size selection. It partitions loop iterations into smaller blocks (tiles) to fit data into faster levels of the memory hierarchy.

• Goal: Improve cache locality by reusing data within a tile before it is evicted.
• Mechanism: Adds outer loops that stride by the tile size and inner loops that iterate within the tile.
• Trade-off: Larger tiles increase reuse but may exceed cache capacity, causing thrashing.

The two fundamental performance states that dictate tile size strategy. A kernel is memory-bound if its speed is limited by memory bandwidth, or compute-bound if limited by arithmetic throughput.

• Memory-Bound Kernels: Benefit from tile sizes that maximize data reuse to reduce pressure on the memory subsystem.
• Compute-Bound Kernels: May prioritize tile sizes that maximize occupancy and hide ALU latency.
• Analysis: Profiling metrics like achieved memory bandwidth vs. peak FLOPS determine the bound.

The percentage of memory requests served from cache (L1, L2) versus slower main memory. It is the primary quantitative metric influenced by tile size selection.

• Direct Impact: Well-chosen tile sizes keep working sets within cache, leading to hit rates >90%.
• Measurement: Tracked via hardware performance counters (e.g., l1_cache_hit, l2_cache_miss).
• Objective: Increase hit rate to reduce the effective latency and energy cost of memory accesses.

The multidimensional search domain defined by all tunable parameters for a kernel, with tile size dimensions being a primary axis.

• Dimensions: Includes workgroup size, loop unroll factors, vectorization factors, and memory promotion flags.
• Size: Can be vast (e.g., 10⁶+ combinations), necessitating intelligent search.
• Constraint: Parameters are often interdependent; optimizing tile size may require adjusting workgroup size.

An analytical or machine-learned function that predicts execution time based on kernel parameters and hardware specs. It guides tile size selection without exhaustive search.

• Analytical Models: Use roofline analysis, calculating operational intensity and bandwidth limits.
• ML-Based Models: Trained on profiling data to predict latency for unseen configurations.
• Use Case: Filters the configuration space, identifying promising tile size regions for empirical testing.

The automated process of searching the configuration space to find optimal parameters, including tile sizes. It replaces manual heuristic-based selection.

• Methods: Include exhaustive search, random search, genetic algorithms, and Bayesian optimization.
• Tools: Frameworks like AutoTVM, Ansor, and Triton's autotuner automate this for NPU/GPU kernels.
• Output: A set of tuned parameters (e.g., tile_x=128, tile_y=64) for a specific hardware target.