Spatial Locality

Spatial locality describes the tendency of a processor to access data elements that are stored at addresses close to recently referenced addresses. This predictable pattern arises from common programming constructs:

• Sequential array traversal: Iterating through contiguous elements.
• Structured data access: Accessing fields within a struct or class.
• Instruction fetch: Executing sequential lines of code.

Hardware exploits this by transferring data in fixed-size blocks called cache lines (e.g., 64 bytes), not as individual bytes, anticipating that nearby data will soon be needed.

The effectiveness of spatial locality is directly tied to cache line size. When a cache miss occurs, the entire line is fetched from main memory. Performance is maximized when the program's access pattern fully utilizes the fetched data.

Key implications:

• Inefficient access: A stride-1 access pattern (e.g., array[i]) perfectly utilizes a cache line.
• Inefficient access: A large-stride or random pattern wastes bandwidth, as most of the fetched cache line goes unused before eviction. This is a primary cause of poor cache utilization and effective bandwidth loss.

Prefetchers are dedicated hardware units that detect sequential memory access patterns and proactively issue read requests for subsequent cache lines before the processor explicitly demands them. This hides memory latency by having data ready in the cache.

Common prefetcher types:

• Stream prefetcher: Detects a constant-stride access and prefetches ahead.
• Adjacent-line prefetcher: On any miss, fetches the next consecutive cache line.

Prefetching effectiveness depends entirely on the strength of the program's spatial locality. Erratic patterns can cause harmful prefetches, polluting the cache with useless data.

Programmer-controlled data organization is critical for inducing spatial locality. The goal is to place data that is accessed together, close together in memory.

Optimization techniques:

• Array of Structures (AoS) vs. Structure of Arrays (SoA): SoA (e.g., positions_x[], positions_y[]) often provides better locality when processing a single field across many objects, as in SIMD or NPU kernels.
• Data packing: Removing padding and aligning data to cache line boundaries.
• Blocking/tiling: Decomposing large datasets (e.g., matrices) into smaller blocks that fit in cache, reusing each block fully before moving to the next.

Poor layout leads to cache thrashing and wasted memory bandwidth.

Spatial locality is a first-order design constraint for Neural Processing Units (NPUs) and AI accelerators. These chips feature complex, hierarchical memory subsystems (e.g., HBM, SRAM scratchpads) with high bandwidth but significant latency.

Design consequences:

• Wide memory interfaces: To amortize latency, NPUs use very wide buses (e.g., 1024-bit or wider) to transfer entire blocks of data corresponding to a spatially local working set.
• Software-managed scratchpads: Instead of hardware caches, many NPUs use scratchpad memory (SPM). The compiler must explicitly orchestrate data movement into the SPM, requiring perfect knowledge of the kernel's spatial access pattern to be efficient.
• Coalesced memory accesses: NPU programming models require memory access patterns where concurrent threads (or processing elements) access contiguous, aligned memory blocks to enable a single, efficient wide transaction.

Spatial locality is one of the Two Forms of Locality, the other being temporal locality (the reuse of specific data items over short time periods).

Interaction in caching:

• Optimal case: A program exhibits both strong temporal and spatial locality (e.g., repeatedly scanning a small array). Data stays hot in cache.
• Spatial-only: Data is used once but sequentially (e.g., streaming a large array). Prefetching is critical, but cache hit rates may be low.
• Temporal-only: Reuse of non-adjacent data items (e.g., random access to a hash table). This is challenging for caches and prefetchers.

Effective memory hierarchy management requires analyzing and optimizing for both locality types. Techniques like loop fusion increase temporal locality, while data layout transformations improve spatial locality.

Spatial locality is the observation that programs tend to access data in contiguous or nearby memory addresses. This predictable behavior is exploited by cache systems and memory controllers to improve performance.

• Cache Lines: Memory is transferred between hierarchy levels in fixed-size blocks called cache lines (e.g., 64 or 128 bytes). When a single byte is requested, the entire line containing it is fetched, anticipating that neighboring data will be needed soon.
• Hardware Prefetching: Memory controllers detect sequential access patterns and automatically issue read-ahead requests for subsequent cache lines before the processor explicitly asks for them, effectively hiding memory latency.

For NPUs processing large tensors, optimizing data layout to maximize spatial locality is critical to keep computational units fed with data.

AI workloads are dominated by tensor operations, where data access patterns are highly structured. Spatial locality directly dictates memory subsystem efficiency.

• Convolutional Layers: When processing an image, a filter (kernel) slides across spatially adjacent pixels. Accessing pixel values and their neighbors exhibits excellent spatial locality if the tensor is stored in a memory-aligned, contiguous format (e.g., NCHW or NHWC).
• Matrix Multiplication: The inner loop of a GEMM (General Matrix Multiply) operation involves streaming elements from rows of one matrix and columns of another. Memory access patterns with large, regular strides can degrade locality if not managed correctly by tiling and blocking strategies.

Poor spatial locality leads to frequent cache misses, stalling the NPU's compute pipelines while waiting for data from slower High Bandwidth Memory (HBM) or DRAM.

NPU compilers perform sophisticated transformations to enhance spatial locality before kernel execution.

• Loop Tiling/Blocking: This critical optimization breaks large loops into smaller blocks that fit into the NPU's scratchpad memory (SRAM) or L1/L2 cache. Data within a tile is reused heavily, maximizing locality before eviction.
• Data Layout Transformation: Compilers may alter the in-memory order of tensor dimensions (e.g., from NHWC to NCHW or a vendor-specific layout like NC/4HW4) to ensure that spatially adjacent elements in the multi-dimensional tensor are also adjacent in linear memory. This aligns the software data structure with the hardware's optimal access pattern.
• Kernel Fusion: By fusing multiple operations (e.g., convolution, bias add, activation) into a single kernel, intermediate results stay in fast register files or caches, avoiding costly round-trips to main memory and preserving locality.

Spatial locality is one of two fundamental locality principles, the other being temporal locality.

• Spatial Locality: "Access nearby data." Exploited by fetching large cache lines and prefetching. Crucial for streaming through data sets.
• Temporal Locality: "Re-access the same data soon." Exploited by keeping recently used data in faster cache levels. Crucial for reusing weights and activations.

AI Workload Example:

• Temporal: Reusing the same filter weights across all positions in a convolutional layer.
• Spatial: Accessing all input pixels needed for a single filter application.

Effective NPU programming requires optimizing for both types simultaneously, often involving trade-offs managed by the compiler's graph compilation strategies.

Modern NPUs and CPUs incorporate dedicated hardware prefetchers to automatically detect and exploit spatial locality.

• Stream Prefetcher: Identifies sequential access patterns (constant stride) and prefetches subsequent cache lines ahead of the demand stream.
• Strided Prefetcher: Detects regular, non-unit strides (common in matrix operations with certain padding) and prefetches along that pattern.

These units operate transparently to software but require predictable access patterns to be effective. Erratic, pointer-chasing patterns (common in graph processing) can confuse prefetchers and waste memory bandwidth. NPU-specific prefetchers are often tuned for dense linear algebra patterns.

Ignoring spatial locality leads to several performance issues in NPU systems:

• Cache Thrashing: Poor data layout can cause useful data to be prematurely evicted from cache because incoming cache lines contain mostly unneeded data, wasting fetch bandwidth.
• Bank Conflict: In parallel architectures, if multiple processing elements simultaneously request data from the same memory bank within a stride pattern, accesses are serialized, causing stalls. Proper data layout and padding mitigate this.
• False Sharing: In multi-core NPU contexts, if two cores write to different variables that reside on the same cache line, the hardware coherence protocol invalidates the line for all cores, causing unnecessary traffic and latency, even though the cores aren't actually sharing data.

Tools for performance profiling and auto-tuning are essential to identify and rectify these locality-related bottlenecks.

Temporal locality is the principle that if a memory location is accessed, it is likely to be accessed again soon. This is the complementary concept to spatial locality and is equally critical for cache design.

• Mechanism: Exploited by keeping recently used data in fast caches (e.g., L1, L2).
• Contrast with Spatial Locality: Temporal focuses on reuse over time; spatial focuses on proximity in address space.
• NPU Impact: Kernel loops that repeatedly process the same weight tensor exhibit strong temporal locality, making small, fast caches highly effective.

A memory access pattern describes the sequence, stride, and regularity with which a program reads from or writes to memory. It is the observable behavior that gives rise to locality principles.

• Strided Access: Common in matrix operations (e.g., column-major vs. row-major). A large, non-unit stride can destroy spatial locality.
• Sequential Access: Ideal for spatial locality, enabling effective hardware prefetching.
• Random Access: Poor for locality, causing frequent cache misses. Often seen in graph processing or sparse tensor operations.
• Design Implication: NPU compilers analyze and transform computational graphs to produce memory access patterns that maximize locality for the target hardware.

A cache line (or cache block) is the fundamental unit of data transfer between a cache and main memory. Its size is a direct hardware mechanism for exploiting spatial locality.

• How it Works: When a single byte is requested, the entire cache line (e.g., 64 bytes) containing that byte is fetched into the cache.
• Spatial Locality Benefit: If subsequent accesses target nearby bytes within the same line, they are served from the fast cache—a cache hit.
• Performance Penalty: Poor spatial locality (accesses scattered across many lines) wastes memory bandwidth and cache capacity, as most fetched data goes unused.
• NPU Consideration: NPU cache line sizes influence optimal data layout and tensor tiling strategies during compilation.

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. Its primary goal is to hide memory latency.

• Hardware Prefetcher: Detects sequential or strided access patterns and issues speculative fetches for subsequent cache lines, directly capitalizing on spatial locality.
• Software Prefetching: Explicit compiler instructions (e.g., prefetch) hint to the memory subsystem about future needs.
• Efficacy Dependency: The accuracy of prefetching depends entirely on predictable, regular access patterns. Erratic patterns can cause harmful cache pollution.
• NPU Use: Crucial for streaming large tensors from HBM or DRAM into on-chip SRAM, ensuring compute units are not starved for data.

False sharing is a severe performance problem in parallel systems where threads on different cores or NPU clusters modify different variables that happen to reside on the same cache line. This invalidates the entire line for other caches, triggering excessive coherence traffic.

• Root Cause: A violation of spatial locality at the system level. Logically separate data is physically co-located.
• Symptom: High performance degradation despite no actual data dependency between threads.
• Solution: Align and pad data structures so that independent variables fall on separate cache lines.
• NPU Relevance: Critical in multi-core NPU designs where different processing clusters share a last-level cache. Poor data layout can cause clusters to inadvertently thrash each other's cache lines.

Scratchpad memory is a small, software-managed, on-chip SRAM in accelerators like NPUs. Unlike a hardware-managed cache, the compiler explicitly controls what data is placed into and evicted from the SPM.

• Contrast with Cache: A cache uses hardware logic and access patterns (locality) to manage data. An SPM relies on compiler analysis and explicit DMA commands.
• Spatial Locality Exploitation: The compiler uses knowledge of the algorithm's access patterns to tile data and schedule transfers, maximizing the utility of data moved into the SPM—a deterministic form of spatial locality optimization.
• Advantages: Predictable latency, no cache miss overhead, and efficient bandwidth use.
• Trade-off: Requires sophisticated, hardware-aware compilation and places the burden of locality management on the software stack.