Prefetching

Prefetching is fundamentally a predictive technique. It relies on algorithms to forecast which data a program will need next, based on observed access patterns. Common prediction strategies include:

• Stride prefetching: Detects constant-offset patterns (e.g., array traversal).
• Stream buffers: Track sequential access streams.
• Correlation-based prefetching: Uses history tables to correlate past accesses with future ones.
• Machine learning models: More advanced implementations use lightweight neural networks or Markov predictors to model complex, non-linear access patterns. The core challenge is balancing prediction accuracy with the overhead of the prediction logic itself.

This characteristic defines how far ahead and when data is fetched. It involves a critical trade-off:

• Timeliness: Data must arrive in the cache just before the processor needs it. If it arrives too late, the processor still stalls. If it arrives too early, it may evict other useful data from the cache before being used, potentially causing cache pollution.
• Lookahead Distance: The number of memory accesses the prefetcher predicts ahead of the current demand access. A longer distance is needed to hide longer latencies (e.g., from DRAM), but prediction accuracy typically decreases with distance.
• Degree of Prefetching: How many cache lines are prefetched per prediction. An overly aggressive degree can waste memory bandwidth.

Prefetching can be implemented at different levels of the system stack, each with distinct trade-offs:

• Hardware Prefetching: Built directly into the processor's memory controller or cache hierarchy. It is transparent to software, has zero instruction overhead, and reacts at nanosecond timescales. Examples include the stream prefetchers in modern Intel and AMD CPUs. However, it is limited to recognizing simple, regular patterns.
• Software Prefetching: Uses special CPU instructions (e.g., PREFETCH intrinsics) inserted by the programmer or compiler. It can handle complex, algorithm-specific patterns but requires program analysis and adds instruction overhead. It is crucial for irregular workloads (e.g., graph traversal) where hardware prefetchers fail.
• Hybrid Approaches: Modern systems often combine both, using compiler hints to guide sophisticated hardware prefetchers.

Prefetchers exploit the fundamental principles of locality:

• Spatial Prefetching: Exploits spatial locality by fetching blocks of data adjacent to the currently accessed address. This is highly effective for sequential or strided access patterns common in array and matrix operations. It often prefetches entire cache lines or multiple lines.
• Temporal Prefetching: Aims to exploit temporal locality by re-fetching data that was accessed in the past and then evicted, predicting it will be needed again. This is more complex and less common in hardware due to the difficulty of accurate prediction and higher storage overhead for access history. Most practical prefetchers are primarily spatially oriented.

These are the primary metrics for evaluating a prefetcher's effectiveness:

• Accuracy: The fraction of prefetched cache lines that are actually used by the demand accesses before being evicted. Low accuracy indicates wasteful prefetching, consuming bandwidth and causing cache pollution.
• Coverage: The fraction of cache misses that are eliminated by successful prefetches. High coverage means the prefetcher is successfully hiding a large portion of the memory latency. An ideal prefetcher has both high accuracy and high coverage. In practice, designers often tune prefetchers to prioritize high accuracy to avoid harmful side-effects, accepting lower coverage.

Prefetching is not free; it consumes system resources and can have negative impacts:

• Memory Bandwidth Consumption: Every prefetch request uses shared memory bus and controller bandwidth, potentially starving demand requests if not throttled.
• Cache Pollution: Incorrectly prefetched data can evict more useful data, increasing miss rates for non-prefetched accesses.
• Hardware Cost: Requires dedicated logic, prediction tables, and buffers on-chip, consuming silicon area and power.
• Complexity in Coherent Systems: In multi-core systems, prefetching can trigger unnecessary cache coherence traffic if it brings data into a cache in a shared state before it is written to by another core. Effective prefetchers include throttling mechanisms and pollution filters to mitigate these costs.

Hardware prefetchers are dedicated circuits within a processor or NPU that automatically detect memory access patterns and issue speculative fetches. Common types include:

• Stride Prefetchers: Detect constant-offset patterns (e.g., accessing elements of an array).
• Stream Prefetchers: Identify sequential access patterns and prefetch subsequent cache lines.
• Correlation Prefetchers: Use history tables to correlate past access sequences with future ones. These units operate transparently to software but are limited to recognizing simple, regular patterns.

Software prefetching uses explicit instructions inserted by a programmer or compiler to hint at future data needs. On NPUs, this is often exposed via vendor intrinsics (e.g., __builtin_prefetch). Key considerations:

• Prefetch Distance: How far ahead to fetch; too close wastes the latency hide, too far risks cache pollution.
• Temporal Locality Hint: Specifies whether data will be used once (non-temporal) or reused.
• Granularity: Prefetching can target specific data structures, like weights or activations in a neural network layer, ahead of the compute kernel that needs them.

Advanced compilers for NPUs (like MLIR-based frameworks) perform polyhedral analysis on loop nests to automatically insert prefetch instructions. This analysis:

• Models data access functions within loops.
• Calculates optimal prefetch schedules to overlap memory latency with ongoing computation.
• Generates parameterized prefetch kernels that can be auto-tuned for specific hardware. This is essential for optimizing dense linear algebra operations (matmul, convolution) which have predictable, strided access patterns.

Prefetching for irregular workloads, like those in Graph Neural Networks (GNNs) or sparse attention, is significantly more challenging. Techniques include:

• Software-Managed Scratchpads: Explicitly load neighbor lists and feature vectors for the next node into a fast SRAM buffer before computation.
• Producer-Consumer Prefetching: A producer kernel prefetches data for a subsequent consumer kernel into a shared buffer, enabling pipeline parallelism.
• History-Based Prediction: Using lightweight ML models to predict which graph nodes or sparse matrix blocks will be accessed next based on traversal history.

Prefetching effectiveness is dictated by the memory hierarchy. In an NPU system, data may move through:

1. Off-Chip DRAM (HBM/GDDR): Highest latency source. Prefetch aims to hide 100s of cycles.
2. Global/Shared Memory: On-chip, higher bandwidth. Prefetch targets moving data from DRAM here.
3. Register File/Vector Units: The final destination for computation. Prefetching must be coordinated with cache policies (write-back/write-through) and DMA engines to avoid resource contention and ensure data consistency.

The success of prefetching is measured by:

• Prefetch Accuracy: Percentage of prefetched data that is actually used. Low accuracy wastes bandwidth and pollutes the cache.
• Coverage: Percentage of cache misses that were eliminated by prefetching.
• Timeliness: Data must arrive before it is needed, but not so early it gets evicted.

Common pitfalls include over-prefetching in bandwidth-bound systems, creating contention, and under-prefetching in latency-bound systems, leaving performance on the table. Effective prefetching requires careful profiling and balancing these trade-offs.

Memory latency is the time delay between a processor's request for data and the moment the data is available for use. It is measured in clock cycles or nanoseconds. Prefetching is a primary technique to hide this latency by moving data closer to the compute units before it is explicitly needed.

• Key Metric: Directly impacts instruction throughput and pipeline stalls.
• Hierarchy Impact: Latency increases dramatically at each lower level of the memory hierarchy (e.g., L1 cache vs. DRAM).
• Prefetch Goal: Initiate data movement early enough so that by the time the processor needs the data, it has already arrived, effectively reducing the perceived latency to zero.

Spatial locality is the principle that if a particular memory location is accessed, nearby memory locations are likely to be accessed soon. This predictable pattern is what makes stride prefetchers effective.

• Hardware Exploitation: Caches are designed around this principle, fetching data in blocks (cache lines).
• Prefetcher Design: A stride prefetcher detects a constant offset between successive memory accesses (e.g., iterating through an array) and issues prefetches for addresses ahead of the current access pointer.
• Performance Impact: Exploiting spatial locality through prefetching is critical for data-parallel workloads common in AI, such as convolutional operations on tensors.

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 concept behind caching, which prefetching complements.

• Cache Policy Foundation: Least Recently Used (LRU) and other cache replacement policies are designed to retain data with high temporal locality.
• Prefetching Relationship: While caching handles re-access, prefetching focuses on predicting new accesses. However, prefetching can pollute the cache if it loads data with poor temporal locality, evicting more useful data.
• Working Set: The set of data with high temporal locality for a given phase of computation.

A cache miss occurs when requested data is not found in the cache, triggering a fetch from a slower, lower level of memory. Prefetching aims to convert compulsory misses (first access) and capacity/conflict misses into cache hits.

• Miss Types:
  • Compulsory (Cold): First access to a block. Prefetching can eliminate these.
  • Capacity: Cache is too small to hold the working set. Prefetching must be accurate to avoid worsening this.
  • Conflict: Data maps to the same cache set. Prefetching can sometimes help.
• Performance Penalty: A cache miss can stall a high-performance CPU or NPU for hundreds of cycles, making accurate prefetching critical for throughput.

The memory access pattern is the sequence and stride of a program's reads and writes. Prefetching algorithms are classified by the patterns they can predict.

• Regular Patterns:
  • Sequential/Streaming: Constant stride of 1. Simple to prefetch.
  • Strided: Constant non-unit stride (e.g., 4, 8). Handled by stride prefetchers.
• Irregular Patterns:
  • Pointer-Chasing: Linked lists, trees. Difficult for hardware prefetchers; often requires software prefetching hints.
  • Indirect: A[i] = B[C[i]]. May require correlated or machine learning-based prefetchers.
• NPU Consideration: AI workload patterns (e.g., sliding windows, matrix tiles) are often regular but with large strides, demanding sophisticated prefetch logic.

Scratchpad memory (SPM) is a small, software-managed on-chip memory in accelerators like NPUs. Unlike a cache, its contents are explicitly controlled by the programmer/compiler, which makes software-controlled prefetching into the SPM a fundamental optimization.

• Determinism: Provides predictable, low-latency access, crucial for real-time systems.
• Data Movement Strategy: The compiler must schedule DMA transfers or specific load instructions to move data from DRAM to the SPM before computation. This is a form of explicit, bulk prefetching.
• Contrast with Cache: No hardware tag checks or replacement ambiguity. Prefetching into SPM is a guaranteed placement, eliminating conflict misses but requiring precise program analysis.