Cache Miss

Cache misses are formally categorized by their underlying cause, which dictates the optimization strategy.

• Compulsory Miss (Cold Miss): The first access to a block of data that has never been in the cache. This is unavoidable without infinite cache size or perfect prefetching.
• Capacity Miss: Occurs when the working set of the program is larger than the cache capacity, forcing eviction of blocks that will be needed again.
• Conflict Miss: Happens in set-associative or direct-mapped caches when multiple memory blocks map to the same cache set, causing thrashing even if the cache has sufficient total capacity.

The miss penalty is the critical metric quantifying a cache miss's cost. It is the additional time required to service the miss versus a hit.

• Measured in Cycles: The penalty is the number of processor clock cycles stalled waiting for data from the next memory level (e.g., L2 cache, DRAM).
• Hierarchical: Penalties escalate dramatically down the memory hierarchy (e.g., L1 miss to L2: ~10 cycles; L3 miss to DRAM: ~200+ cycles).
• Bandwidth Saturation: A high miss rate can saturate the memory bus, increasing the effective penalty for all subsequent misses.

The miss rate is the primary statistic for cache performance analysis, calculated as Misses / Total Accesses.

• Absolute vs. Relative: A low absolute rate (e.g., 1%) can still cause severe slowdowns if the program executes billions of memory accesses.
• MPKI: Misses Per Kilo-Instruction is often a more stable metric than a percentage rate, as it is independent of the total number of cache accesses.
• Profiling Tools: Hardware performance counters (e.g., via perf on Linux or VTune) are used to precisely measure cache misses during execution.

Cache misses directly result from poor exploitation of the two core locality principles.

• Temporal Locality Miss: Data was accessed, evicted, and then accessed again before it could be reused. This indicates a working set larger than cache or poor replacement policy.
• Spatial Locality Miss: Data is accessed with a large, unpredictable stride (e.g., random access), wasting the fetched cache line where only a single byte is used. Optimizing data structures for unit stride access is key.

In systems with multiple processors or NPU cores sharing memory, coherence misses add a fourth category.

• Invalidation Miss: Occurs when a cache line is invalidated because another core wrote to it (a write to a shared line). The core must then fetch the updated data.
• False Sharing: A major cause of artificial coherence misses. Threads on different cores modify different variables that happen to reside on the same cache line, triggering unnecessary invalidations and reloads.

Addressing cache misses involves hardware and software techniques.

• Hardware: Larger caches, higher associativity, smarter prefetchers, and victim caches.
• Software (Most Critical):
  • Data Structure Optimization: Align and pack data to fit cache lines.
  • Loop Transformations: Tiling/blocking to fit working sets into cache.
  • Prefetching Intrinsics: Software-initiated prefetch instructions.
  • Memory Access Pattern: Designing algorithms for sequential, predictable access. For NPUs, compiler-driven kernel fusion and scratchpad memory management are essential software mitigations.

A cache miss is a failed attempt by a processor to read or write data in a cache, requiring a fetch from a lower, slower level of the memory hierarchy. This event incurs a performance penalty measured in hundreds of processor cycles. In AI workloads, frequent cache misses can stall the massive parallel compute units in an NPU, drastically reducing throughput and increasing energy consumption per operation. The goal of memory hierarchy optimization is to minimize the miss rate.

Cache misses are categorized by their cause, guiding optimization strategies:

• Compulsory Miss (Cold Miss): The first access to a memory block. Unavoidable but can be mitigated via prefetching.
• Capacity Miss: Occurs because the working set is larger than the cache size. Solved by algorithmic tiling or using larger caches.
• Conflict Miss: Happens in set-associative caches when multiple memory blocks map to the same cache set, evicting each other. Addressed by improving data layout or increasing associativity.
• Coherence Miss (Invalidation Miss): In multi-core systems, a cache line is invalidated due to a write by another processor. Critical in NUMA systems and for cache coherence protocols.

NPUs often employ a multi-tiered, software-managed memory hierarchy distinct from CPU caches. A typical structure includes:

• Global Memory (HBM/DRAM): High-capacity, high-bandwidth, but high-latency. Source of data on a miss.
• Shared Memory / Local SRAM: A fast, on-chip, software-managed scratchpad memory. Programmers explicitly control data movement here to avoid hardware cache misses.
• Register Files: The fastest storage, directly feeding the compute units. Optimization involves data staging: proactively moving data from global to shared memory before computation, mimicking perfect cache behavior.

Neural network execution exhibits specific patterns that challenge caches:

• Large Parameter Tensors: Model weights often exceed cache capacity, leading to capacity misses during layer execution.
• Strided Access Patterns: Convolution operations access input data with large, non-unit strides, harming spatial locality and causing misses.
• Activation Recomputation: Training frameworks may recompute activations to save memory, causing repeated compulsory misses.
• Small Batch Sizes: Inference with batch size 1 provides less data reuse per weight load, increasing miss rates compared to large-batch training.

Reducing cache misses is a key systems optimization:

• Loop Tiling/Blocking: Restructures computation to operate on sub-blocks of data that fit in cache, exploiting temporal locality.
• Data Layout Transformation: Changing the order of tensor dimensions (e.g., NHWC to NCHW) to create contiguous, cache-friendly access patterns.
• Software Prefetching: Inserting explicit instructions to fetch data into cache or shared memory well before it is needed, hiding latency.
• Kernel Fusion: Fusing multiple neural network layers into a single kernel avoids writing intermediate results to memory and reading them back, eliminating those cache accesses entirely.

Understanding cache misses requires knowledge of adjacent concepts:

• Miss Penalty: The extra time taken to service a miss.
• Miss Rate: The fraction of memory accesses that result in a miss.
• Average Memory Access Time (AMAT): Calculated as: Hit Time + (Miss Rate × Miss Penalty). The key formula for quantifying cache performance.
• Working Set: The set of memory addresses a program actively uses in a time window. If it exceeds cache size, capacity misses soar.
• Memory Wall: The growing gap between processor speed and memory latency, making cache miss reduction increasingly critical.

A memory hierarchy organizes different memory types (registers, caches, main memory, storage) into a multi-level structure to balance access speed, capacity, and cost. The principle is that smaller, faster memory sits closer to the processor, while larger, slower memory provides bulk storage. A cache miss forces a data request to traverse this hierarchy downward, incurring a significant latency penalty. The hierarchy's effectiveness relies on the principles of temporal and spatial locality in program data access.

Temporal locality is the principle that if a memory location is accessed, it is likely to be accessed again in the near future. This is the foundational behavior that makes caches effective. Programs exhibiting strong temporal locality have a low cache miss rate because recently used data remains in the fast cache. Examples include loop counters or frequently called function variables. A cache miss often indicates a breach of expected temporal locality.

Spatial locality is the principle that if a memory location is accessed, nearby memory locations are also likely to be accessed soon. This justifies cache designs that fetch data in blocks (cache lines), not just single bytes. When a cache miss occurs due to a lack of spatial locality (e.g., random memory access), the fetched cache line may contain mostly unused data, wasting bandwidth and cache capacity. Optimizing data structures for contiguous access improves spatial locality and reduces miss rates.

The working set is the set of memory pages or cache lines a process actively uses within a specific time interval. If the working set size exceeds the available cache capacity, capacity misses occur as the cache cannot hold all required data, leading to constant eviction and reloading. Profiling the working set is critical for sizing on-chip memory (like an NPU's scratchpad or cache) and for optimizing algorithms to have a smaller, more cache-friendly memory footprint.

Prefetching is a hardware or software technique that predicts future memory accesses and proactively loads data into a cache before the processor explicitly requests it. Its goal is to hide memory latency by ensuring data is already present, thereby converting what would be a cache miss into a cache hit. Effective prefetching relies on predictable access patterns (like sequential strides). Incorrect prefetches waste bandwidth and can evict useful data, potentially increasing miss rates.

A memory access pattern describes the sequence and stride of a program's reads and writes to memory. It is the primary determinant of cache performance. Key patterns include:

• Sequential/Strided: Excellent for prefetching and spatial locality.
• Random: Causes poor cache utilization and high miss rates.
• Gather/Scatter: Common in sparse computations, challenging for caches. Analyzing and optimizing the memory access pattern is a fundamental step in reducing cache misses for NPU kernels and high-performance computing workloads.