Cache Hit Rate

Cache Hit Rate (CHR) is the percentage of total memory access requests that are successfully served from a cache, avoiding a slower access to main memory (DRAM). It is calculated as:

Cache Hit Rate = (Number of Cache Hits / Total Memory Accesses) * 100%

• A Cache Hit occurs when requested data is found in the cache.
• A Cache Miss occurs when the data must be fetched from a lower level of the memory hierarchy.
• The complementary metric is Cache Miss Rate, where Miss Rate = 1 - Hit Rate.

CHR directly dictates the Average Memory Access Time (AMAT), a key determinant of system performance. The formula is:

AMAT = Hit Time + (Miss Rate * Miss Penalty)

• Hit Time: The latency of accessing the cache (typically 1-10 cycles).
• Miss Penalty: The much higher latency of fetching data from main memory (often 100-300 cycles).
• A high CHR minimizes the frequency of costly misses, keeping the compute units fed with data and maximizing compute throughput. A low CHR can cause the NPU to become memory-bound, stalling pipelines and wasting computational resources.

CHR is not a single value but is analyzed per cache level (L1, L2, L3, etc.). Effective memory hierarchy design aims for:

• High L1 Hit Rate: Critical for keeping the core's execution units busy. L1 caches are small and fast.
• Reasonable L2/L3 Hit Rate: These larger caches capture accesses that miss in L1, preventing them from going to main memory.
• The global hit rate experienced by the processor is the cumulative effect of all levels. A miss in L1 that hits in L2 is still a hit from the system's perspective, avoiding DRAM access.

CHR is fundamentally determined by the locality of reference in the workload:

• Temporal Locality: Recently accessed data is likely to be accessed again soon. Good temporal locality leads to high hit rates.
• Spatial Locality: Accessing a memory location makes it likely that nearby locations will be accessed. Exploited by cache line fetches.
• NPU workloads (e.g., matrix multiplications, convolutions) can achieve very high CHR (>95%) when kernels are optimized for memory coalescing and efficient tiling to fit working sets into cache.

CHR is a first-order diagnostic in performance profiling and bottleneck analysis. Profilers use hardware performance counters to measure cache hits and misses.

• Low CHR signals a memory-bound kernel. Optimization efforts should focus on improving data locality, increasing cache reuse, or applying compression.
• High CHR with low performance suggests the kernel is compute-bound. Optimization should then focus on increasing compute throughput via vectorization or improving instruction mix.

A cache hit consumes significantly less energy than a cache miss. Fetching data from DRAM involves driving high-capacitance off-chip buses and activating large memory arrays.

• High CHR reduces dynamic power consumption by keeping data access on-chip.
• It also reduces memory bandwidth pressure, allowing other system components to use the shared bus and potentially enabling lower power states. For battery-powered edge devices with NPUs, optimizing CHR is a primary method for extending operational life.

Loop tiling is a compiler transformation that partitions loop iterations into smaller blocks or tiles that fit within the cache. By reusing data within a tile before it is evicted, this technique exploits temporal locality and significantly reduces capacity and conflict cache misses. For NPU matrix multiplication, tiling ensures sub-matrices stay in shared memory or L1 cache.

• Key Benefit: Transforms memory-bound operations into compute-bound ones.
• Tunable Parameter: Tile size selection is critical and is often auto-tuned for the specific NPU cache hierarchy.

Memory coalescing optimizes memory transactions by ensuring that consecutive threads in a warp or wavefront access consecutive memory addresses. This allows the NPU's memory controller to combine multiple scattered requests into a single, wider transaction, maximizing effective memory bandwidth and improving cache line utilization.

• Mechanism: A non-coalesced access pattern can serialize transactions, causing pipeline stalls.
• Application: Essential for optimizing global memory reads/writes in data-parallel NPU kernels.

Prefetching is a proactive technique where data is loaded into the cache before it is explicitly requested by the processor. This hides memory access latency by overlapping computation with data movement. NPUs may use software-directed prefetching (explicit instructions) or hardware prefetchers that detect sequential access patterns.

• Goal: Move data from slower global memory to faster shared or L1 cache during idle memory cycles.
• Challenge: Requires accurate prediction of future access patterns to avoid cache pollution.

Array padding involves adding unused elements (padding) to the end of rows in a multi-dimensional array. This prevents conflict misses that occur when multiple, frequently accessed data elements map to the same cache line or set due to unfortunate alignment with cache geometry (e.g., power-of-two strides).

• Use Case: Critical for optimizing access to 2D/3D arrays in convolution or stencil computations on NPUs.
• Result: Transforms irregular, high-miss access patterns into predictable, cache-friendly ones.

This involves designing or selecting algorithms with inherent cache-oblivious or cache-aware properties. These algorithms are recursively decomposed to work on sub-problems that naturally fit into cache levels, regardless of the specific cache size. Examples include blocked matrix algorithms and certain sorting methods (e.g., cache-oblivious sorting).

• Advantage: Delivers portable performance across different NPU architectures with varying cache sizes.
• Principle: Minimizes the working set size of computational phases.

Transforming data structures from an Array of Structures (AoS) to a Structure of Arrays (SoA) layout. In AoS, attributes of a single object are contiguous, which is cache-inefficient when a kernel accesses only one attribute across many objects. SoA stores each attribute in a separate, contiguous array, enabling unit-stride access and perfect coalescing.

• Performance Impact: Can dramatically improve spatial locality and vectorization potential.
• Example: Changing struct Particle {float x, y, z;} to struct Particles {float x[N], y[N], z[N];} for NPU physics simulation.

A cache miss occurs when a requested data item is not found in the cache memory, forcing the processor to access the slower main memory (DRAM). This event directly opposes a cache hit and is the primary cause of performance degradation in memory-bound workloads.

• Types of Misses:
  • Compulsory Miss (Cold Miss): First access to a block of data.
  • Capacity Miss: Cache cannot contain all blocks needed due to size limits.
  • Conflict Miss: Occurs in set-associative caches when multiple blocks map to the same set.
• Miss Penalty: The additional time (often hundreds of cycles) required to service a miss, which includes memory fetch and cache line allocation.

Memory bandwidth is the maximum rate at which data can be read from or written to a memory subsystem by a processor, measured in gigabytes per second (GB/s). It is a critical, finite resource that determines the upper limit of data throughput for an NPU.

• A low cache hit rate increases demand on memory bandwidth, as more data must be fetched from main memory.
• If the data demand exceeds the available bandwidth, the workload becomes memory-bound, causing compute units to idle.
• Optimizing data access patterns (e.g., via memory coalescing) is essential to use bandwidth efficiently and mitigate the impact of cache misses.

Memory coalescing is a critical optimization for parallel architectures where consecutive threads in a warp or wavefront access consecutive memory addresses. This pattern allows the memory controller to combine multiple accesses into a single, wider transaction.

• Effect on Cache Hit Rate: Coalesced accesses maximize the utilization of each cache line fetched, improving effective bandwidth and reducing the number of required cache lines, which can indirectly improve hit rates in capacity-limited caches.
• Non-coalesced access scatters memory requests, wasting bandwidth and potentially thrashing the cache, leading to more misses and severely degraded performance.

Locality of reference is a principle stating that memory accesses tend to cluster in time and space. It is the foundational concept that makes caching effective. There are two primary types:

• Temporal Locality: Recently accessed data is likely to be accessed again soon. High temporal locality leads to high cache hit rates after initial warm-up.
• Spatial Locality: Accessing a data item makes it likely that nearby data items will be accessed soon. This justifies fetching cache lines (blocks of contiguous data) rather than single words.
• Kernel optimizations like loop tiling are designed explicitly to improve both types of locality for NPU workloads.

A cache line (or cache block) is the fundamental unit of data transfer between the main memory and the cache. When a cache miss occurs, an entire cache line (e.g., 64 or 128 bytes) is fetched, not just the requested byte.

• Implication for Hit Rate: The size of the cache line influences spatial locality. If subsequent accesses fall within the same fetched line, they become cache hits, amortizing the miss penalty.
• False Sharing: A performance issue in multi-core systems where different processors write to different variables that reside on the same cache line, causing unnecessary invalidation and coherence traffic, effectively reducing hit rates.

A workload is described as memory-bound when its execution time is primarily limited by the speed or bandwidth of the memory subsystem, not by the computational capability of the processor (ALU).

• Direct Relationship to Cache Hit Rate: A low cache hit rate is a primary indicator and cause of a memory-bound condition. The processor spends most of its time stalled, waiting for data from main memory.
• Roofline Model: This performance analysis model visually depicts if a kernel is compute-bound or memory-bound. A kernel plotting below the memory bandwidth roof is memory-bound; optimizing memory access (improving hit rate) is the key to moving it toward the compute roof.