loopblocking

Loop blocking, also known as tiling, is a loop transformation used to improve data locality in nested loops by operating on sub-blocks of data that fit into fast cache memory. By restricting the working set to a small, repeated region, loop blocking aims to increase cache hits and reduce memory bandwidth pressure, thereby speeding up compute-intensive kernels.

The technique reorganizes the iteration space of a multi-dimensional loop nest. Instead of processing entire arrays in a single pass, the outer loops iterate over blocks of indices, while inner loops process the elements within each block. For example, a matrix-matrix multiplication or stencil computation can be rewritten to loop over blocks of rows, columns, and, if needed, the k dimension, with block sizes chosen to match the target cache sizes. This promotes temporal locality by reusing loaded data across multiple computations within a block.

Applications of loop blocking are common in high-performance computing, numerical linear algebra, and image processing. It is frequently used to optimize matrix multiplication, convolution-like operations, and stencil codes, where data reuse patterns are predictable. Blocking can be combined with other optimizations such as loop interchange, vectorization, and parallelization to further improve performance on multi-core CPUs and GPUs. Some compilers or domain-specific languages also offer automatic blocking or user-guided blocking via annotations or pragmas.

Choosing appropriate block sizes is crucial and depends on hardware characteristics such as cache size, associativity, and memory hierarchy. Poorly chosen blocks can degrade performance or increase overhead. Blocking can complicate code and dependency analysis, so it requires careful consideration of correctness, data layout, and portability across architectures.