Cache Locality

Temporal locality refers to the principle that data accessed recently is likely to be accessed again in the near future. Optimizing for this involves reusing data while it remains in cache.

• Example: Reusing the same weight tensor across multiple input vectors in a batched matrix multiplication.
• Impact: Reduces repeated, costly fetches from main memory (DRAM).
• Implementation: Loop ordering that keeps frequently accessed data in inner loops.

Spatial locality refers to the principle that data elements stored close to each other in memory are likely to be accessed together. Optimizing for this ensures that fetching one piece of data brings adjacent, needed data into cache.

• Example: Accessing consecutive elements of an array or a contiguous block of a feature map in a convolutional neural network.
• Impact: Maximizes the utility of each cache line fetch (typically 64 bytes).
• Implementation: Using contiguous memory layouts (e.g., NCHW/NHWC formats) and avoiding strided or random access patterns.

Data layout transformation involves rearranging how multidimensional data (like tensors) is stored in linear memory to create contiguous access patterns aligned with compute loops.

• Common Formats: Converting from NCHW to NHWC format can provide better spatial locality for convolution operations on certain hardware.
• Operation: Often performed by inference runtimes (e.g., TensorRT, ONNX Runtime) during graph optimization.
• Goal: Minimize cache line waste and ensure sequential memory accesses during the innermost computation loops.

Neural network model architecture choices have a profound impact on inherent cache locality. Efficient architectures are designed for predictable, sequential data flow.

• Favorable Patterns: Convolutions with small kernels and dense linear layers exhibit strong spatial locality.
• Challenging Patterns: Attention mechanisms with large, dynamic key-value caches can strain locality.
• Co-Design: Hardware-aware Neural Architecture Search (NAS) often uses latency estimators that model cache behavior to find optimal architectures for a target device.

Loop tiling (or loop blocking) is a compiler optimization that partitions loop iterations into smaller blocks (tiles) to fit the working data set into the processor's cache. This is a direct implementation of cache locality principles.

• Mechanism: It transforms nested loops to process data in cache-sized chunks, minimizing expensive transfers to and from main memory (RAM).
• Application: Critical for optimizing GEMM (General Matrix Multiply) operations in neural networks, where large matrices are broken into tiles that fit in L1/L2 cache.
• Impact: Can lead to order-of-magnitude speedups in convolutional and fully connected layers by ensuring data reused within a tile is served from fast cache.

Operator fusion is a compiler optimization that combines multiple sequential neural network operations into a single, fused kernel. It directly improves cache locality by keeping intermediate tensor data in registers or cache.

• How it works: Instead of writing the output of a convolution to memory and then reading it back for batch normalization and ReLU, a fused kernel performs all three operations in one pass.
• Benefits: Dramatically reduces memory footprint and bandwidth pressure by eliminating intermediate storage. This is a key optimization in runtimes like TensorRT and ONNX Runtime.
• Example: Fusing Conv2D -> BatchNorm -> ReLU is a standard pattern for CNN acceleration.

Memory footprint is the total amount of system memory (RAM) required to load and execute a machine learning model, including its parameters, activations, and intermediate buffers. Minimizing it is essential for cache locality.

• Components: Includes model weights (persistent), activation maps (transient), and workspace memory for operations like convolution.
• Relationship to Cache: A smaller memory footprint increases the likelihood that working data will reside in CPU cache. Techniques like quantization and pruning reduce the weight footprint, while operator fusion reduces activation memory.
• Constraint: On edge devices with limited RAM (e.g., 512MB), footprint dictates model feasibility. On-Device Model Compression techniques directly target this metric.

A compute graph is a directed acyclic graph (DAG) representation of a neural network where nodes represent operations (ops) and edges represent the tensors flowing between them. It is the data structure optimized for execution.

• Role in Optimization: Frameworks and compilers (e.g., TensorRT, TVM) perform graph-level optimizations—like constant folding, dead code elimination, and scheduling for cache locality—on this intermediate representation.
• Lowering: The graph is progressively "lowered" from a high-level framework representation to hardware-specific kernels, with optimizations applied at each stage.
• Static vs. Dynamic: A static graph (used in AOT compilation) allows for aggressive optimization, while a dynamic graph offers flexibility at the cost of runtime overhead.

Kernel optimization involves hand-tuning or auto-generating low-level code for fundamental operations (like GEMM or convolution) to maximize performance on specific hardware by leveraging features like vectorization and memory hierarchy.

• Goal: To create the most cache-efficient and compute-saturated implementation of a single operation. This is the final, hardware-aware step after operator fusion.
• Techniques: Includes explicit prefetching, loop unrolling, register blocking, and the use of SIMD (Single Instruction, Multiple Data) instructions.
• Hardware-Specific: Optimal kernels differ vastly between a mobile CPU, a desktop GPU with Tensor Cores, and a dedicated NPU. Hardware-Aware Model Design co-designs algorithms with these kernels in mind.

GEMM (General Matrix Multiply) optimization is the specialized focus on maximizing the performance of matrix multiplication, the core computational primitive in deep learning. It is fundamentally an exercise in cache locality.

• The Problem: Naive matrix multiplication has poor cache usage, repeatedly accessing data from slow RAM.
• The Solution: Advanced implementations use loop tiling to block matrices for L1/L2/L3 cache, vectorization for SIMD units, and assembly-level tuning.
• Libraries: Highly optimized BLAS libraries like OpenBLAS, Intel oneDNN (formerly MKL-DNN), and NVIDIA's cuBLAS provide these kernels. Tensor Cores in NVIDIA GPUs are hardware units dedicated to mixed-precision GEMM.