Loop Tiling

The primary goal of loop tiling is to increase data reuse within fast cache memory. By partitioning loop iterations into smaller blocks (tiles), the working data set for each tile fits within the L1 or L2 cache. This transforms memory-bound loops, where performance is limited by slow DRAM access, into compute-bound loops that can saturate the processor's arithmetic units. For example, in a matrix multiplication, tiling ensures that a sub-block of each matrix is loaded once and used for multiple computations before being evicted, dramatically reducing the total bytes transferred from main memory.

Choosing the optimal tile dimensions is critical and hardware-dependent. The size is constrained by:

• Cache Capacity: The combined data footprint of all arrays accessed within a tile must not exceed the target cache's size.
• Cache Associativity: To avoid conflict misses, tile dimensions should be chosen so that accessed memory lines map to different cache sets.
• Register File Limits: For innermost loops, further tiling for register-level locality (register blocking) is used, constrained by the number of available hardware registers. Poor tile sizing can lead to capacity misses (tile too large) or inefficient reuse (tile too small). Auto-tuners like TVM Ansor empirically search for the optimal tile size.

Modern memory hierarchies (e.g., DRAM → L3 → L2 → L1 → Registers) necessitate hierarchical tiling. A single tile size is insufficient. Instead, nested tiles are used:

• Outer Tiles target the last-level cache (LLC) or DRAM bandwidth.
• Inner Tiles target the L1 cache.
• Innermost Loops are optimized for register blocking. This creates a cascading effect where data is staged through progressively faster, smaller memories. The transformation results in loops with multiple new tiling loops surrounding the original computation loop nest.

Tiling inherently exposes new forms of parallelism:

• Inter-Tile Parallelism: Independent tiles can be distributed across multiple processor cores or threads, enabling efficient coarse-grained data parallelism. This is crucial for scaling on multi-core CPUs and NPUs.
• Intra-Tile Vectorization: The small, regular loops within a tile are ideal candidates for Single Instruction, Multiple Data (SIMD) vectorization, as the data is likely resident in L1 cache. However, tiling can complicate synchronization if tiles have dependencies. For perfectly nested loops with no cross-iteration dependencies, tiles are embarrassingly parallel.

Tiling changes the fundamental order in which data is accessed. The compiler must also choose an optimal loop permutation (the order of the tiled loops). The goals are:

• Unit Stride Access: Ensure the innermost loop iterates over contiguous memory addresses for efficient prefetching and cache line utilization.
• Reuse Distance Minimization: Order loops so that the data reused by the inner loops is produced or loaded by the immediately surrounding outer loops. A classic example is optimizing a stencil computation (e.g., a 3D convolution) where tiling in the spatial dimensions must be combined with loop skewing to maintain correctness and enable pipelining.

Loop tiling is rarely applied in isolation; it is a foundational step that enables other critical optimizations:

• Operator Fusion: After tiling, the computation within a tile for fused operators (e.g., Conv + Bias + ReLU) can be performed entirely on-chip, eliminating intermediate global memory writes.
• Array Padding: To prevent cache thrashing caused by conflict misses, arrays are often padded in memory so that different tiles map to distinct cache sets.
• Software Pipelining: The regular structure of tiled loops allows for better instruction scheduling to hide memory latency by overlapping loads, computations, and stores. Thus, tiling is a core component of the polyhedral model and modern ML compilers like Apache TVM, MLIR, and XLA.

A compiler-level optimization that merges multiple sequential neural network operations (e.g., Convolution → BatchNorm → ReLU) into a single, fused kernel. This eliminates intermediate memory writes and reads between operations, reducing latency and off-chip bandwidth pressure. It is a complementary technique to loop tiling, as fused operators often become the primary unit for tiling and scheduling.

The end-to-end process of transforming a high-level neural network computational graph into an optimized, hardware-specific executable. This pipeline applies a series of transformations, including:

• Operator Lowering: Decomposing framework-specific layers into primitive operations.
• Loop Transformations: Applying tiling, unrolling, and vectorization.
• Memory Layout Optimization: Rearranging data for efficient access patterns. Loop tiling is a critical intermediate step within this compilation flow.

An automated empirical search process that finds the optimal configuration parameters for a computational kernel on specific hardware. For tiled loops, this involves searching over a vast space of possible tile sizes, loop orders, and unroll factors to maximize performance. Auto-tuners like TVM's Ansor use machine learning or genetic algorithms to navigate this parameter space, as the optimal tile dimensions depend on cache sizes, register counts, and memory bandwidth.

A key performance metric defined as the number of arithmetic operations performed per byte of data transferred from main memory (FLOPs/byte). It determines if a kernel is compute-bound or memory-bound. Loop tiling is the primary technique for increasing operational intensity by promoting data reuse from fast cache memory. The Roofline Model uses this metric to visualize the attainable performance of a kernel, bounded by hardware peaks.

A specific memory transformation technique for convolutional layers. It rearranges local image patches into columns of a matrix, converting convolution into a General Matrix Multiply (GEMM). This transformation creates large, regular data accesses ideal for high-performance libraries but increases memory footprint. Loop tiling is then applied to the resulting GEMM operation to manage this expanded working set within the processor's cache hierarchy.

The overarching discipline of orchestrating data movement across a processor's layered memory subsystems (e.g., DRAM → L3 Cache → L2 Cache → L1 Cache → Registers). Loop tiling is its most fundamental algorithm. Effective management requires understanding:

• Cache Blocking: Tiling for CPU/GPU caches.
• Register Tiling: The innermost loop tile, sized to fit in processor registers.
• Software-Managed Scratchpad: Explicitly moving tiles to/from fast SRAM on NPUs/GPUs.