Kernel Tiling

The core objective of tiling is to exploit temporal locality and spatial locality within a faster memory hierarchy. By partitioning a large iteration space into smaller tiles, the working set of data (the tile) is designed to fit entirely into a limited, fast memory like shared memory (on GPUs) or scratchpad memory/L1 cache (on NPUs). This drastically reduces the number of accesses to slower global memory (DRAM). For example, in a matrix multiplication, tiling allows a sub-block of matrices A and B to be loaded once into shared memory and reused for many computations.

Effective tiling is explicitly designed for a target accelerator's memory hierarchy. A multi-level tiling strategy is often employed:

• Register Tiling: The innermost tile size is chosen to keep operands in thread-private registers for the lowest latency access.
• Shared Memory/Scratchpad Tiling: An intermediate tile is sized to fit the software-managed cache shared by a thread block or workgroup.
• Cache Tiling: Outer tiles may be sized for the hardware-managed L2/L3 cache. This hierarchical blocking minimizes data movement at every level of the memory pyramid.

The tile dimensions (e.g., TILE_M, TILE_N, TILE_K for GEMM) are not arbitrary. They are pivotal optimization parameters that must balance multiple, often conflicting, hardware constraints:

• Shared Memory Capacity: Total tile data must not exceed available shared memory per thread block.
• Register Count: Per-thregister usage, determined by the innermost tile, must avoid register spilling.
• Thread Block Size: Tile dimensions often map directly to the number of threads, affecting kernel occupancy.
• Memory Coalescing: Tile dimensions should be chosen to enable aligned, contiguous memory accesses by threads. Finding the optimal tile size is a classic target for auto-tuning.

Tiling decomposes a large problem into independent or partially independent sub-problems (tiles). This creates natural units of work that can be:

• Distributed across multiple thread blocks or workgroups for coarse-grained parallelism.
• Assigned to threads within a block for fine-grained parallelism. The tile becomes the fundamental unit of data parallelism. Furthermore, tiling can expose pipeline parallelism; while one thread block processes its tile, others can be loading their data, hiding memory latency.

Tiling is rarely applied in isolation. It is a prerequisite or synergistic with several other critical compiler passes:

• Loop Unrolling: Applied to the innermost loops within a tile to reduce loop overhead and increase instruction-level parallelism (ILP).
• Vectorization: The regular, predictable access patterns within a tile are ideal for SIMD or SIMT vectorization.
• Memory Coalescing: Tiling, when combined with proper thread mapping, transforms scattered memory accesses into contiguous, coalesced transactions.
• Kernel Fusion: Tiling can be applied across fused operation boundaries, keeping intermediate results within fast memory across multiple operations.

Tiling is essential for accelerating the compute-bound kernels that dominate deep learning:

• General Matrix Multiply (GEMM): The canonical example. Tiling is applied across all three loops (M, N, K) to block matrices for register and shared memory.
• Convolutions: The input image and filter are tiled to maximize reuse of input pixels across multiple output positions and filters.
• Reductions: Tiling is used to perform partial reductions within a thread block using shared memory, followed by a final reduction across blocks. The performance of frameworks like cuBLAS, oneDNN, and MLIR-based compilers hinges on sophisticated tiling strategies.

A compiler optimization that combines two or more adjacent loops with the same iteration space into a single loop. This reduces loop overhead and improves data locality by keeping intermediate results in faster memory hierarchies like registers or caches, which can complement tiling by creating larger, more efficient tiles.

• Primary Benefit: Reduces kernel launch and memory access overhead.
• Interaction with Tiling: Often performed before tiling to create a larger, fused iteration space that is then partitioned into tiles.

A class of compiler transformations applied to nested loops to maximize data locality, parallelism, and hardware utilization. Kernel tiling is a core LNO technique. Others include:

• Loop interchange: Swaps loop order to improve access patterns.
• Loop unrolling: Replicates loop body to reduce control overhead.
• Loop fission: Splits a loop to reduce register pressure.

LNO uses a polyhedral model to mathematically analyze and legally apply these transformations in combination for accelerators like NPUs.

An optimization on parallel architectures where concurrent memory accesses from multiple threads (within a warp or wavefront) are combined into a single, wider transaction. This maximizes effective memory bandwidth.

• Critical for Tiling: The tile size and thread mapping must be chosen to ensure threads within a block access contiguous, aligned memory addresses.
• Performance Impact: Poor coalescing can reduce effective bandwidth by 10x or more, negating the benefits of tiling.

A key performance metric defined as the number of arithmetic operations performed per byte of data transferred between the processor and main memory (DRAM). It classifies kernels as:

• Compute-Bound: High arithmetic intensity. Performance limited by peak FLOPS.
• Memory-Bound: Low arithmetic intensity. Performance limited by memory bandwidth.

Tiling's Goal: To transform memory-bound kernels into compute-bound ones by reusing data within a tile (in registers/shared memory), thereby increasing the effective arithmetic intensity for the data fetched from global memory.

Occurs when a compiler's register allocator is forced to move values from fast, on-chip registers to slower memory (like the stack or local memory) because the live variables exceed the available physical registers.

• Tiling Trade-off: Larger tile sizes increase data reuse but also raise register pressure. Excessive spilling can destroy performance gains from tiling.
• Compiler Role: The compiler must balance tile size against the fixed register file size of the target hardware (e.g., NPU streaming processor).

An automated process that empirically searches a parameter space—such as tile sizes, loop unroll factors, or thread block dimensions—to find the configuration yielding the best performance for a specific kernel on target hardware.

• Why it's needed: The optimal tile size is a complex function of problem shape, memory hierarchy sizes, and hardware quirks.
• Methodology: Uses techniques like grid search, genetic algorithms, or machine learning to evaluate thousands of configurations, often leveraging a Roofline Model to guide the search.