Loop Tiling

Loop tiling, also known as loop blocking, transforms a loop's iteration space by introducing new, outer loops that step through the space in fixed-size blocks (tiles). The original inner loops then iterate within each tile. This restructuring is defined by a tile size parameter. For a 2D loop nest, it changes access from a row-major traversal to a block-major traversal, fundamentally altering the memory access pattern to exploit temporal and spatial locality.

The principal objective of tiling is to maximize data reuse within the CPU's cache hierarchy. By working on a small tile of data, the computation can keep that tile resident in fast L1/L2 cache for the duration of its processing. This drastically reduces expensive accesses to slower main memory (DRAM). The effectiveness hinges on selecting a tile size that matches the capacity of the target cache level, ensuring the working set of a tile fits entirely within it.

Tiling transforms strided, often non-unit stride, memory accesses into localized, sequential accesses within a tile. For example, in matrix multiplication, accessing a column of a large matrix in the inner loop causes poor cache use due to cache line underutilization and capacity misses. Tiling ensures that both the row of matrix A and the column of matrix B are accessed in small, contiguous chunks, leading to efficient cache line fills and prefetching behavior.

Choosing the optimal tile size is a critical and non-trivial optimization problem. Key trade-offs include:

• Cache Capacity: Tile data must fit within the target cache (L1, L2, or TLB).
• Register Pressure: Smaller tiles may increase overhead; larger tiles may spill registers.
• Parallelism Granularity: Tile size affects load balancing in parallel execution.
• Hardware-Specific Factors: Cache line size, associativity, and prefetcher behavior. Kernel auto-tuning is often used to empirically search for the best tile size for a given hardware target.

Loop tiling is frequently combined with other transformations to form a powerful optimization pipeline:

• Loop Fusion: Often performed after tiling to merge operations on the same tiled data.
• Loop Unrolling: Applied to the innermost loop within a tile to reduce branch overhead and enable instruction-level parallelism (ILP).
• Loop Vectorization: The contiguous, predictable accesses within a tile are ideal for SIMD vectorization.
• Loop Interchange: Can be used in conjunction with tiling to place the loop with the most reuse potential as the innermost loop within the tile.

In neural network compilation for NPUs and GPUs, tiling is essential for managing specialized memory hierarchies (e.g., global memory, shared memory, registers). Compilers like TVM or MLIR apply tiling to map convolutional and matrix multiplication loops onto hardware resources. The tile sizes are chosen to maximize data reuse in fast scratchpad memory (SRAM) and minimize transfers to/from slow High-Bandwidth Memory (HBM). This is a cornerstone of hardware-aware model optimization.

Within the MLIR compiler infrastructure, loop tiling is expressed as a transformation on the affine or scf (Structured Control Flow) dialects. A typical lowering pipeline involves:

• Applying the tile transformation with specific tile size parameters.
• Generating tiled loops with explicit bounds for the outer (tile) and inner (intra-tile) loops.
• Subsequent passes like promotion move tiled data into fast memory (e.g., NPU scratchpad).
• The tiled representation is then lowered through vector and gpu or vendor-specific dialects for final code generation.

Google's XLA compiler integrates tiling with its fusion optimizer. The process is:

1. Loop analysis identifies multi-dimensional loops in HLO (High-Level Optimizer) operations like convolutions and matmuls.
2. Tile size selection is often heuristic-driven or based on hardware parameters (e.g., tensor core dimensions for NVIDIA GPUs, systolic array dimensions for NPUs).
3. Fusion decisions are made post-tiling; smaller, tiled loops are more amenable to being fused with adjacent operations, reducing global memory traffic. This creates compound operations optimized for a single hardware kernel launch.

Advanced polyhedral model compilers use affine transformation frameworks to derive optimal tiling hyper-planes mathematically. For NPU compilation:

• The iteration space of nested loops is modeled as a polyhedron.
• Transformations for locality (tiling) and parallelism are computed simultaneously.
• Dependence analysis ensures tiling is legal (does not violate data flow).
• This approach can find complex, non-rectangular tiles that maximize data reuse in multi-level memory hierarchies, which is essential for NPU efficiency.

Vendor NPU SDKs (e.g., NVIDIA TensorRT, Intel OpenVINO, ARM Compute Library) often expose low-level intrinsics or APIs that assume or require tiled data layouts.

• Kernels are pre-optimized for specific tile sizes (e.g., 4x4, 8x8, 16x16).
• The compiler's job is to transform the model's data layout to match this expected tiled format, often through layout transformation passes.
• Manual tiling hints can be provided via SDK APIs to override compiler heuristics for performance-critical sections.

Loop tiling is rarely applied in isolation; it enables and interacts with other critical graph compilation strategies:

• Loop Fusion: Tiling creates smaller, uniform loops that are more easily fused with neighboring operations.
• Vectorization: The inner, intra-tile loop is a prime candidate for SIMD vectorization as it often operates on contiguous, aligned data.
• Memory Planning: Tiling directly informs scratchpad memory allocation and double buffering schemes to overlap computation and data movement.
• Parallelism: The outer tile loops often become targets for parallelization across NPU cores.

A compiler transformation that merges two or more adjacent loops with the same iteration space into a single loop. This optimization improves data locality by keeping intermediate results in faster cache levels and reduces loop overhead from separate kernel launches or loop control instructions. It is often applied before or in conjunction with loop tiling to maximize the benefit of each tile.

• Example: Fusing a convolution operation with its subsequent ReLU activation into a single loop.
• Key Benefit: Reduces the number of memory loads/stores for data shared between the fused operations.

A compiler optimization that transforms scalar operations within a loop to use Single Instruction, Multiple Data (SIMD) instructions. This enables parallel execution on multiple data elements within a single CPU or NPU core. While tiling optimizes for cache hierarchy, vectorization exploits data-level parallelism within a core's execution units.

• Relationship to Tiling: The inner loops created by tiling are prime candidates for vectorization.
• Hardware Target: Essential for utilizing the wide vector units in modern NPUs and CPUs.

A compiler optimization pass that allocates memory buffers for tensors in a computational graph, aiming to minimize peak memory usage. It works closely with transformations like tiling by determining the lifetime of data buffers. Effective memory planning enables in-place operations and buffer reuse across tiles and operators.

• Critical for Tiling: Determines if tile-sized buffers can fit in target cache or shared memory.
• Goal: Reduce expensive transfers to and from global DRAM, which is a primary objective of tiling.

An automated process that searches a space of possible kernel implementation parameters to find the configuration that delivers optimal performance for a specific hardware target. For tiled loops, this involves empirically testing different tile sizes, unroll factors, and scheduling strategies to find the best combination.

• Direct Application: Used to find the optimal tile dimensions (Tx, Ty) for a given loop nest on specific hardware.
• Methodology: Often employs search algorithms like grid search, random search, or machine learning-based predictors.

A compiler technique that groups sets of operators within a computational graph into clusters, typically to be executed together on a specific hardware unit. This high-level grouping creates boundaries for lower-level optimizations. Loop tiling is then applied within these clusters to optimize the execution of the fused operation sequence.

• Compilation Flow: Clustering → Fusion → Tiling & Vectorization.
• Purpose: Isolates sections of the graph for targeted optimization and potential offloading to an NPU.

A compiler optimization that changes the in-memory data layout of tensors to align with the access patterns preferred by specific hardware or computational kernels. This transformation is highly synergistic with tiling. Choosing the correct memory layout (e.g., NHWC vs NCHW) can make the access patterns within a tile unit-stride, maximizing cache line utilization and prefetcher effectiveness.

• Performance Impact: A poor layout can negate the benefits of tiling by causing cache thrashing.
• Hardware-Specific: NPUs often have a strongly preferred layout for their matrix multiplication units.