Loop Tiling

Loop tiling, also called loop blocking, partitions the iteration space of a loop nest into smaller blocks or tiles. The primary goal is to ensure that all data within a tile fits into a processor's cache hierarchy (L1, L2). This transforms a computation with poor temporal locality into one with high locality, drastically reducing costly accesses to main memory (DRAM).

• Key Transformation: It changes the loop order from, for example, (i, j) to (ti, tj, ii, jj), where ti/tj iterate over tiles and ii/jj iterate within a tile.
• Target: Memory-bound operations like dense matrix multiplication, convolutions, and stencil computations.

Choosing the optimal tile size is non-trivial and balances multiple constraints. The ideal tile maximizes data reuse without exceeding cache capacity or introducing excessive overhead.

• Cache Capacity Bound: The working set of a tile (input + output data) must fit within the target cache (e.g., L1).
• Translation Lookaside Buffer (TLB) Coverage: Tile dimensions should be chosen to minimize TLB misses for virtual-to-physical address translation.
• Hardware-Specific Tuning: Optimal sizes depend on the specific cache line size, associativity, and bandwidth of the target CPU or accelerator. This often requires auto-tuning or analytical modeling.

Loop tiling is rarely applied in isolation; it enables and synergizes with other critical compiler passes.

• Enables Vectorization: By creating contiguous, predictable inner-loop access patterns within a tile, tiling provides ideal conditions for SIMD vectorization.
• Facilitates Parallelization: Tiling creates independent units of work (tiles) that can be distributed across multiple CPU cores or GPU threads for parallel execution.
• Foundation for the Polyhedral Model: Tiling is a canonical transformation within the polyhedral model, a mathematical framework for loop nest optimization that ensures correctness across complex transformations like fusion and skewing.

Effective tiling must account for the memory hierarchy and compute architecture of the target hardware.

• Multi-Level Tiling: For deep cache hierarchies, nested tiling is used—a small tile for L1 cache, a larger tile for L2/L3 cache. This is essential for operations like general matrix multiply (GEMM).
• Register Tiling: The innermost loop levels can be tiled to hold operands directly in CPU registers, minimizing even L1 cache accesses.
• Accelerator-Specific Tiling: On GPUs and NPUs, tiling dimensions are chosen to optimize for shared memory/SRAM capacity and thread block/wavefront execution models.

The effectiveness of loop tiling is perfectly illustrated by the Roofline performance model. This model plots attainable performance (FLOPS/sec) against operational intensity (FLOPS/byte).

• Memory-Bound Region: Kernels with low operational intensity are limited by memory bandwidth. Tiling increases operational intensity by reusing cached data, moving the kernel's point to the right on the Roofline chart.
• Compute-Bound Region: Once operational intensity is high enough, performance hits the processor's peak compute ceiling. Tiling ensures the kernel can saturate this compute capacity by keeping the functional units fed with data.

Consider naive matrix multiplication C[i][j] += A[i][k] * B[k][j]. The inner loop has poor cache locality as it strides through entire rows/columns.

A tiled version introduces block indices (ib, jb, kb) and inner indices (ii, jj, kk):

codeCopy
for ib in range(0, N, TILE):
  for jb in range(0, N, TILE):
    for kb in range(0, N, TILE):
      # Compute on tile C[ib:ib+TILE][jb:jb+TILE]
      # using A[ib:ib+TILE][kb:kb+TILE] and B[kb:kb+TILE][jb:jb+TILE]

• Result: The sub-matrices A_tile and B_tile are loaded into cache once and reused extensively for all computations within the (ib, jb) tile, reducing memory accesses from O(N³) to roughly O(N³/√TILE).

A loop transformation that reduces loop control overhead by duplicating the body of a loop multiple times. This decreases the total number of iterations and branch instructions, increasing opportunities for instruction-level parallelism and enabling other compiler optimizations like constant propagation.

• Key Benefit: Reduces branch prediction misses and increases instruction cache efficiency.
• Trade-off: Increases code size, which can negatively impact instruction cache performance if over-applied.
• Relation to Tiling: Often applied within a tile after tiling has been performed, to further optimize the innermost computation.

A compiler optimization that converts scalar operations into Single Instruction, Multiple Data (SIMD) instructions. Instead of processing one data element per instruction, vectorized loops process a small vector (e.g., 4 or 8) of elements simultaneously.

• Hardware Dependency: Requires CPU support for SIMD instruction sets (e.g., AVX-512, ARM NEON).
• Prerequisite: Often requires loop unrolling and data alignment to be most effective.
• Synergy with Tiling: Tiling improves data locality, bringing contiguous blocks of data into cache, which is ideal for the wide, contiguous memory accesses required by vectorized loads and stores.

A powerful mathematical framework for the compile-time analysis and transformation of loop nests. It represents loop iterations as points in a geometric space (a polyhedron) and transformations (like tiling, fusion, skewing) as affine mappings.

• Key Strength: Enables complex, multi-loop optimizations while guaranteeing semantic correctness (no change to program output).
• Application: Used in advanced compilers (e.g., LLVM Polly, Tiramisu) to automatically derive optimal tiling and fusion strategies for dense linear algebra and stencil computations.
• Relation: Provides the formal foundation for systematically applying and reasoning about loop tiling transformations.

The transformation of a tensor's in-memory arrangement to better match the access patterns of computational kernels. Common transformations include changing from NHWC (batch, height, width, channels) to NCHW format or to a blocked layout like NCHW[x]c.

• Goal: Maximize spatial locality and enable efficient vectorization by ensuring the data being accessed sequentially in the loop is also contiguous in memory.
• Hardware-Specific: Optimal layout depends on the memory hierarchy and SIMD width of the target CPU, GPU, or NPU.
• Co-optimization with Tiling: The choice of tile size and shape is intimately tied to the data layout. An optimal tiling strategy for one layout may be inefficient for another.

An automated empirical process that searches for the optimal implementation parameters for a computational kernel on specific hardware. For matrix multiplication or convolution kernels, this involves searching a space of parameters like:

• Tile sizes for different levels of cache (L1, L2, L3).
• Loop ordering within a tile.
• Unroll factors and vectorization width.
• Number of software threads to use.

A cost model or direct benchmarking is used to evaluate each configuration. Libraries like OpenBLAS, Intel oneDNN, and TVM use auto-tuning to deliver portable high performance.

An intuitive visual performance model used to analyze the performance limits of a kernel or loop nest. It plots Attainable GFLOPs/sec against Operational Intensity (FLOPs/byte).

• Roofline: The model shows two hard ceilings: a compute-bound roof (peak FLOPs of the hardware) and a memory-bound roof (peak bandwidth * operational intensity).
• Diagnostic Tool: Determines if a kernel is compute-bound or memory-bound.
• Guiding Tiling: The primary goal of loop tiling is to shift a kernel's operational intensity to the right on the Roofline chart, moving it from the memory-bound slope towards the compute-bound plateau. The model helps answer how much tiling is needed.