Memory Tiling

The primary goal of tiling is to maximize data reuse from fast, on-chip memory (caches). By partitioning large tensors into smaller tiles that fit within cache, the same data elements are accessed multiple times while "hot" in the cache before being evicted. This transforms memory access patterns from streaming (high bandwidth demand) to reusable, dramatically reducing pressure on the main memory bus and lowering effective latency.

Effective tiling is often multi-level, mirroring the hardware's memory hierarchy. A compiler might create:

• Register tiles: Tiny blocks that fit in CPU/GPU registers for single-instruction multiple-data (SIMD) operations.
• L1 Cache tiles: Larger blocks that stay in the L1 data cache.
• Shared Memory/ L2 Cache tiles: Even larger blocks for GPU shared memory or CPU L2/L3 cache. Each level is sized to match the capacity and associativity of its corresponding hardware structure to minimize cache conflicts and thrashing.

Tiling fundamentally restructures loop nests. For a matrix multiplication C[i][j] += A[i][k] * B[k][j], a tiled version adds two new outer loops over tile indices (Ti, Tj, Tk) and partitions the inner loops to iterate within a tile. This changes the loop order from, e.g., i,k,j to Ti,Tj,Tk,i,k,j, creating a blocked algorithm. The compiler must choose a tiling schedule that balances parallelism, locality, and hardware prefetching behavior.

Choosing the optimal tile dimensions is critical and non-trivial. Factors include:

• Cache capacity and line size.
• Translation lookaside buffer (TLB) coverage to avoid page faults.
• Arithmetic intensity (FLOPs per byte) of the kernel.
• Hardware prefetcher characteristics. Compilers often use auto-tuning to empirically search the parameter space (tile height, width, depth) or employ polyhedral model analysis to derive optimal sizes analytically for regular loops.

Tiling introduces a tension between locality and parallelism. Large tiles improve locality but reduce the number of parallel tiles available for distribution across cores or threads, potentially underutilizing the machine. Conversely, very small tiles maximize parallelism but hurt cache reuse. Compilers must perform a trade-off analysis, often using parallel tiling strategies that tile for shared caches (L3) while allowing inner tiles to be distributed across cores for private caches (L1/L2).

Tiling is most famously applied in General Matrix Multiply (GEMM) kernels, which are the backbone of deep learning and scientific computing. It is equally crucial for convolutional neural network (CNN) layers. Here, tiling must handle multi-dimensional data (e.g., NCHW format) and sometimes involves implicit GEMM transformations where convolution is converted to a matrix multiplication before tiling. Libraries like BLAS, cuDNN, and compilers like TVM or MLIR heavily rely on advanced tiling schemes for these operations.

A compiler optimization that replicates the body of a loop multiple times, reducing the overhead of loop control instructions (e.g., increment and branch). This increases the basic block size, enabling more aggressive instruction scheduling and vectorization by exposing more independent operations to the compiler. For example, unrolling an inner loop in a matrix multiplication can allow the compiler to schedule multiple fused multiply-add (FMA) operations in parallel.

A compiler optimization that transforms scalar operations to execute simultaneously on multiple data points using Single Instruction, Multiple Data (SIMD) instructions. It is a critical follow-on optimization to tiling, as the smaller, regular blocks created by tiling are ideal candidates for SIMD lanes. For instance, a tiled 8x8 block of a matrix can be efficiently processed using 256-bit SIMD registers that operate on 8 single-precision floating-point numbers at once.

A compiler optimization that merges multiple sequential neural network operations into a single, compound kernel. This reduces intermediate tensor writes to slow main memory, complementing tiling's goal of improving data locality. A classic example is fusing a Convolution, Batch Normalization, and ReLU activation into one kernel, which allows the fused computation to occur entirely within fast cache registers after the initial data is tiled into the cache.

A compiler optimization that pre-allocates and reuses memory buffers for all tensors at compile time. It works in concert with tiling by allowing the compiler to precisely plan the lifetime of each tile's buffer. This eliminates the runtime overhead of dynamic memory allocation (malloc/free) and can minimize the total peak memory footprint, which is critical for memory-constrained edge devices.

A high-level compiler pass that transforms a neural network's computational graph before low-level optimizations like tiling. It applies transformations such as constant folding, dead code elimination, and algebraic simplifications. These optimizations reduce the overall operation count and simplify the graph structure, making subsequent loop-based optimizations like tiling more effective and straightforward to apply.

An automated compiler process that searches a space of possible configurations (like tile sizes, unroll factors, and vector widths) to find the optimal version for a specific workload and hardware target. Since the optimal tile size depends on cache hierarchy specifics, auto-tuning empirically tests different configurations to maximize performance, often using techniques like profile-guided optimization (PGO).