Memory Hierarchy Optimization

Loop tiling is a fundamental code transformation that partitions large iteration spaces into smaller blocks (tiles) to fit the working set of data into a faster level of the memory hierarchy (e.g., L1/L2 cache). This exploits temporal locality by reusing data within a tile and spatial locality by accessing contiguous memory addresses.

• Mechanism: A large matrix multiplication is broken into sub-matrix blocks. The tiles of matrices A and B are loaded into cache once and used for multiple computations.
• Impact: Can reduce DRAM accesses by orders of magnitude, transforming memory-bound operations into compute-bound ones.

This technique reorganizes how data is stored in memory to align with the access patterns of the computation, minimizing cache misses and enabling efficient vectorized (SIMD) loads.

• Key Strategies:
  • Structure of Arrays (SoA) to Array of Structures (AoS): Converting from AoS (struct {float x,y,z;}) to SoA (struct {float x[]; float y[]; float z[];}) enables contiguous, aligned loads of a single attribute across many data points, ideal for vectorized operations.
  • Memory Alignment: Ensuring data arrays start at addresses aligned to cache line boundaries (e.g., 64-byte) prevents split loads across lines.
• Example: Computer vision pipelines often transform image data from interleaved channels (HWC) to planar format (CHW) for efficient convolutional filter application.

Kernel fusion is a compiler optimization that merges multiple consecutive computational operations (kernels) into a single, compound kernel. This eliminates intermediate writes and reads of large tensors to and from DRAM, keeping data in registers or cache.

• Classic Pattern: Fusing a convolution, batch normalization, and ReLU activation into one kernel. The output of the convolution is normalized and activated before being written back to memory.
• Benefits:
  • Drastically reduces memory bandwidth pressure.
  • Increases arithmetic intensity (operations per byte fetched).
  • Reduces kernel launch overhead in frameworks like CUDA.
• Tools: Compilers like TVM and XLA perform automatic kernel fusion during graph lowering.

This involves intelligently scheduling the execution order of operations in a computational graph to maximize data reuse and minimize peak memory footprint.

• Principle: Schedule operations so that the output of one can be consumed immediately by the next while still in a fast cache, rather than spilling to DRAM.
• Use Case: In a transformer block, carefully scheduling the order of attention heads and feed-forward network computations can keep key intermediate tensors resident.
• Relation to Gradient Checkpointing: A trade-off technique where some activations are not saved during the forward pass to reduce memory, then recomputed during the backward pass. Optimal checkpointing selects which tensors to recompute to minimize total compute time under a memory budget.

Instead of relying solely on hardware-controlled caches, this technique uses scratchpad memory (SPM)—a small, fast, software-managed SRAM on-chip. The programmer or compiler explicitly controls data movement between DRAM and the scratchpad.

• How it Works: Critical data blocks (e.g., a tile of a matrix) are DMAed into the SPM, processed completely, and results are written back. This provides predictable, low-latency access.
• Hardware Context: Common in many NPUs, DSPs, and GPUs (e.g., CUDA shared memory, AMD local data share).
• Advantage: Eliminates unpredictable cache thrashing and provides guaranteed bandwidth for real-time systems.

Optimizes memory access and computation for neural networks with pruned weights (structured/unstructured sparsity) by skipping operations on zero values and using efficient storage formats.

• Key Techniques:
  • Compressed Sparse Formats: Using CSR or CSC to store only non-zero values and their indices, dramatically reducing memory footprint and bandwidth needs.
  • Sparse Kernel Design: Specialized GPU/TPU kernels that load compressed data and use predicate masks to avoid multiplications with zeros.
  • Amortized Index Lookup: Grouping non-zero computations to reuse index loads.
• Challenge: Exploiting fine-grained unstructured sparsity requires specialized hardware support (e.g., NVIDIA's Sparse Tensor Cores) to realize performance gains beyond just memory savings.

Loop tiling is a fundamental compiler optimization that restructures nested loops to operate on small blocks (tiles) of data that fit entirely within the CPU cache. This transforms a memory-bound operation into a compute-bound one.

• Standard Convolution: Accesses large input and weight tensors from DRAM repeatedly, causing high latency.
• Tiled Convolution: Partitions tensors into smaller tiles. A tile of input activations and corresponding weights are loaded into cache once and used for multiple computations, drastically reducing DRAM traffic.
• Impact: Can improve inference throughput by 3-5x for convolutional layers by exploiting temporal and spatial locality.

Operator fusion is a graph-level optimization performed by compilers like Apache TVM and NVIDIA TensorRT. It merges multiple sequential layers (e.g., Convolution → BatchNorm → ReLU) into a single, fused kernel.

• Mechanism: The compiler generates a custom kernel that performs the combined operations without writing intermediate tensors back to DRAM.
• Benefit: Eliminates the read/write overhead for intermediate activations, reducing memory bandwidth pressure and kernel launch latency.
• Example: Fusing a common ResNet block sequence can reduce memory accesses by ~40% and improve latency by 20-30% on GPU hardware.

Neural Processing Units (NPUs) employ specialized dataflow architectures that orchestrate data movement to keep the most frequently accessed parameters in on-chip buffers. Weight Stationary is a common strategy.

• Process: The weights for a layer are loaded into a high-bandwidth SRAM buffer (weight buffer) once. The input activations are then streamed through the compute array, performing all necessary multiplications against the stationary weights.
• Advantage: Minimizes power-hungry accesses to external DRAM for weights, which are typically reused across many input pixels or tokens.
• Hardware Example: Google's TPU and many edge NPUs use systolic arrays with weight-stationary or output-stationary dataflows to achieve extreme energy efficiency (TOPS/W).

Gradient checkpointing is a memory-for-compute trade-off that enables the training of extremely deep models (e.g., 1000+ layers) on memory-constrained hardware.

• Problem: Training requires storing all intermediate activations for the backward pass, leading to O(n) memory complexity with network depth.
• Solution: Only a subset of activations (checkpoints) are stored during the forward pass. During the backward pass, missing activations are recomputed from the nearest checkpoint.
• Result: Reduces memory consumption from O(n) to O(√n), allowing for 4-8x larger models on the same GPU memory at the cost of ~30% increased compute time for the recomputation.

Optimizing the Attention mechanism for cache hierarchy is crucial for efficient LLM inference. The key is to minimize data movement for the Key (K) and Value (V) caches during autoregressive decoding.

• Standard Attention: For each new token, the entire K/V cache (growing with sequence length) is read from DRAM, creating a memory bandwidth bottleneck.
• Optimized Attention:
  • Blocked Processing: Sequences are processed in blocks. K/V vectors for a block are prefetched into cache and reused for all queries in that block.
  • FlashAttention: A seminal algorithm that uses tiling to keep slices of Q, K, V in SRAM, performing the entire softmax and attention operation on-chip, reducing HBM accesses by orders of magnitude.
• Impact: FlashAttention can achieve 2-4x speedup in training and reduce inference latency for long sequences.

After pruning a model to induce sparsity (many zero weights), efficient inference requires encoding the sparse weight matrix to skip computations and minimize memory footprint.

• Compressed Sparse Row (CSR): Stores only non-zero values and their column indices, plus row pointers. Enables efficient SpMM (Sparse Matrix-Matrix Multiplication) kernels.
• Blocked Sparsity (e.g., 2:4): A structured pattern where 2 out of every 4 contiguous weights are non-zero. This pattern can be leveraged by hardware like NVIDIA Ampere GPUs with Sparse Tensor Cores, which skip zero blocks, effectively doubling theoretical throughput for matrix operations.
• Memory/Compute Benefit: A model with 90% unstructured sparsity can reduce weight memory by 10x. With 2:4 structured sparsity, inference can see a 1.5-2x speedup on supported hardware.

An analytical performance model that visualizes the attainable performance of a computational kernel as a function of its operational intensity (operations per byte of data moved). It plots performance ceilings set by:

• Peak Compute Throughput (FLOPS)
• Peak Memory Bandwidth (Bytes/sec)

Kernels are characterized as compute-bound (limited by FLOPS) or memory-bound (limited by bandwidth). This model is foundational for identifying optimization targets in memory hierarchy design.

A compiler optimization that combines multiple consecutive neural network operations into a single, fused kernel. This reduces intermediate tensor writes to slow memory (DRAM) and minimizes kernel launch overhead.

Common Fusions:

• Convolution + Batch Normalization + Activation (e.g., ReLU)
• Matrix Multiply + Bias Add + GELU

Fusion is a primary method for increasing operational intensity, moving a kernel from being memory-bound to compute-bound on the roofline model.

Specialized hardware units in modern NVIDIA GPUs (e.g., Volta, Ampere, Hopper architectures) designed to perform mixed-precision matrix multiply-accumulate operations at extremely high throughput. They execute operations like D = A * B + C where A, B are low-precision matrices (FP16, BF16, INT8, INT4) and C, D are higher precision (FP16, FP32).

Optimizing for Tensor Cores requires:

• Data layout transformations (e.g., to NHWC format).
• Tile sizes that match the hardware's 16x16x16 or larger matrix dimensions.
• Ensuring computational kernels have sufficient arithmetic intensity to saturate the units.

A hardware feature that allows peripherals (like NPUs, GPUs, or custom accelerators) to transfer large blocks of data to/from system memory without continuous CPU intervention. This is critical for overlapping computation with data movement (hiding latency).

In memory hierarchy optimization, DMA engines are used to:

• Prefetch weights and input tiles from DRAM into on-chip SRAM/cache.
• Stream output results back to main memory while the next computation begins.
• Enable efficient double-buffering techniques where one buffer is computed on while the other is being filled via DMA.

The use of specialized data structures to store and compute with sparse tensors (where most values are zero). This reduces memory footprint and enables skipping computations involving zeros.

Common Formats:

• Compressed Sparse Row (CSR): For 2D weight matrices.
• Blocked Sparsity: Groups weights into small blocks (e.g., 4x4), requiring only a single bit to indicate if the block is all-zero.
• 2:4 Structured Sparsity: A pattern where 2 out of every 4 consecutive values are zero, natively supported by NVIDIA Ampere+ GPUs for 2x speedup.

Effective use requires co-designing pruning algorithms to induce hardware-friendly sparsity patterns.

An automated optimization process that searches for the best-performing implementation parameters for a computational kernel (like a convolution or matrix multiplication) on specific target hardware. It empirically benchmarks thousands of variants to find the optimal configuration.

Parameters Tuned:

• Tile sizes for blocking data into cache.
• Loop unrolling factors.
• Vectorization width.
• Thread block dimensions (for GPUs).

This process is essential because the optimal memory access pattern for a kernel is highly dependent on the exact cache hierarchy, memory bandwidth, and register file size of the target CPU, GPU, or NPU.