Temporal Locality

Temporal locality describes the tendency for a processor to access the same memory location multiple times within a short temporal window. This is the primary justification for cache memory. When data exhibits high temporal locality, caching it after the first access provides a high probability of a cache hit on subsequent accesses, dramatically reducing effective memory latency. Examples include loop counters, frequently used variables, and instructions within a tight loop.

Cache management policies are explicitly designed to exploit temporal locality. The Least Recently Used (LRU) eviction algorithm is a direct embodiment of this principle, operating on the assumption that data not used recently is less likely to be used soon. Similarly, write-back caching policies rely on temporal locality; modified data is kept in the cache, assuming it will be accessed again before being written to main memory, thereby reducing bandwidth consumption.

Software can be structured to enhance temporal locality, a key optimization for NPU kernels. Techniques include:

• Loop blocking/tiling: Reorganizing loops to keep working data sets small enough to fit in cache.
• Common subexpression elimination: Reusing computed values instead of recalculating them.
• Register allocation: Compilers aggressively assign temporaries with high reuse to CPU/NPU registers, the fastest level of the memory hierarchy. Poor locality leads to thrashing, where the cache constantly evicts and reloads data.

Temporal locality often works in concert with spatial locality (access to nearby addresses). When a cache line is fetched due to temporal locality for one address, the entire line—containing spatially local data—is loaded. Subsequent accesses to adjacent addresses within that line then benefit from both principles. Effective prefetching algorithms predict future accesses based on patterns combining temporal and spatial locality.

Temporal locality is quantified by a program's working set—the set of memory addresses it actively references during a time interval. If the working set size is less than or equal to the available cache capacity, the program exhibits good temporal locality and runs efficiently. Performance collapses when the working set exceeds cache size, causing continuous capacity misses. Profiling tools measure cache hit rates and reuse distance to analyze temporal locality.

In Neural Processing Units, temporal locality is critical for weight and activation reuse across layers and inference steps. NPU compilers perform operator fusion to keep intermediate tensor data in on-chip scratchpad memory or caches across consecutive operations. For recurrent neural networks (RNNs) or processing sequential data, the same weights are accessed repeatedly over time, making temporal locality a primary optimization focus to minimize costly accesses to external DRAM like HBM.

In a convolutional neural network (CNN), the output activations from one layer become the input to the next. During the forward pass of a batch, the same activation tensor is read multiple times by different filters in the subsequent layer. This creates strong temporal locality. Optimization: The NPU's L1 or shared memory (scratchpad) can hold these activations, preventing repeated fetches from slower global memory (e.g., HBM).

During the processing of a mini-batch, the same set of model weights (parameters) is used for every example in the batch. For a batch size of N, each weight is accessed N times in quick succession. Key Impact: This is a primary driver for designing large, fast caches on NPUs. If weights fit in an on-chip cache, access latency drops dramatically for the entire batch. Techniques like weight stationary dataflow in systolic arrays are hardware designs explicitly built to exploit this locality.

During the backward pass of training, gradients are computed for each layer's weights. In gradient accumulation, gradients from multiple micro-batches are summed before a weight update. The gradient accumulator variable for each weight is read, updated, and written back repeatedly over these micro-batches. System Benefit: This creates temporal locality for the accumulator in on-chip memory, reducing traffic to DRAM. It's a fundamental optimization for training large models that cannot fit a full batch in device memory.

In autoregressive inference with Transformer-based Large Language Models (LLMs), the Key (K) and Value (V) matrices for previous tokens in a sequence are reused when generating the next token. Instead of recomputing them, they are cached. Each new token generation involves reading this entire growing cache. Performance Critical: This exhibits extreme temporal locality for the K/V cache of earlier tokens. Optimizing its placement in fast, high-bandwidth memory (like SRAM or HBM) is essential for low-latency token generation. NPU memory hierarchies are tuned for this access pattern.

Loop tiling (or block matrix multiplication) is a compiler optimization that decomposes a large matrix operation into smaller sub-blocks. A tile of data from matrices A and B is loaded into fast on-chip memory (scratchpad/cache). All computations for that tile are performed before moving to the next. Locality Creation: This transformation explicitly creates temporal locality—the elements within a tile are accessed many times for the dot product calculations—before being evicted. This is the software technique that enables hardware caches to be effective for linear algebra kernels like GEMM.

In Replay Buffers used by deep reinforcement learning algorithms (e.g., DQN, DDPG), past experiences (state, action, reward, next state) are stored. During training, a mini-batch is sampled randomly from this buffer. Temporal Locality in Sampling: The sampling process often has locality—certain experiences may be sampled multiple times within a short period, especially with prioritized replay where high-error experiences are re-sampled more frequently. While the buffer itself is large, caching frequently sampled experiences can improve data loading efficiency.

Spatial locality is the principle that if a particular memory location is accessed, nearby memory locations are also likely to be accessed in the near future. This pattern is exploited by memory systems through:

• Cache line design: Data is transferred in contiguous blocks (lines) from main memory to cache.
• Prefetching algorithms: Hardware or software predicts and loads adjacent data ahead of time.
• Memory access patterns: Sequential or strided access (e.g., iterating through an array) exhibits high spatial locality, while random access does not.

For NPU workloads, optimizing data layout (e.g., using NHWC vs. NCHW tensor formats) can dramatically improve spatial locality and cache line utilization.

A cache miss occurs when a processor requests data that is not present in the cache, forcing a slower access to a lower level of the memory hierarchy (e.g., DRAM). Cache misses are a primary source of performance stalls. Types include:

• Compulsory (cold) miss: First access to a block; unavoidable.
• Capacity miss: The working set exceeds the cache size.
• Conflict miss: Occurs in set-associative or direct-mapped caches when multiple blocks map to the same set.

In NPU acceleration, minimizing cache misses for weight tensors and activation maps is critical. Techniques like tiling and loop reordering are used to increase data reuse within the cache before eviction.

The working set of a process is the collection of memory pages or cache lines that it actively references during a specific time window. It is a dynamic measure of a program's immediate memory requirements.

Key implications for NPU performance:

• If the working set fits within the NPU's on-chip SRAM or cache, performance is optimal.
• If it exceeds on-chip memory, thrashing occurs, with constant data movement to/off-chip DRAM (e.g., HBM).
• Kernel fusion and operator scheduling in graph compilers aim to minimize the peak working set of consecutive operations to keep data on-chip.

Scratchpad memory (SPM) is a small, high-speed, software-managed on-chip memory in accelerators like NPUs. Unlike hardware-managed caches, the programmer or compiler explicitly controls data movement in and out of the SPM.

Contrast with Caches (which exploit temporal locality implicitly):

• Cache: Hardware automatically retains recently used data based on locality.
• Scratchpad: Software explicitly places data with known reuse (high temporal locality) into fast memory.

For NPUs, using SPM for weights, partial sums, or small feature map tiles with high temporal locality provides deterministic, low-latency access and avoids cache coherence overhead.

Prefetching is a hardware or software technique that predicts future memory accesses and proactively loads data into a cache or buffer before the processor explicitly requests it. The goal is to hide memory latency by overlapping computation with data transfer.

Types relevant to NPUs:

• Hardware stride prefetcher: Detects regular access patterns (common in matrix multiplication).
• Software prefetching: Compiler inserts special prefetch instructions based on static analysis of loops.
• Agent-based prefetching: A separate thread or micro-engine predicts and fetches data for the main compute cores.

Effective prefetching relies on predictable access patterns with strong spatial and temporal locality.

A memory access pattern describes the sequence, stride, and regularity with which a program reads from or writes to memory addresses. It is the primary determinant of cache performance and bandwidth utilization.

Patterns and their impact on locality:

• Sequential/Streaming: High spatial locality, ideal for prefetching.
• Strided (e.g., column-major access): Can cause poor cache utilization if stride != 1.
• Random: Very low spatial and temporal locality, causing frequent cache misses.
• Gather-Scatter: Common in sparse tensor operations; challenging for caches.

NPU compilers perform loop transformations and data layout optimizations to convert irregular patterns into regular, cache-friendly ones to exploit temporal locality.