Memory Prefetching

The most fundamental technique, sequential prefetching predicts that if address N is accessed, addresses N+1, N+2, etc., will soon be needed. It is highly effective for streaming data, array traversals, and loading contiguous blocks from storage.

• Mechanism: A simple stride detector triggers prefetches for subsequent cache lines.
• Hardware Implementation: Common in CPU cache controllers for L1 and L2 caches.
• Limitation: Fails with non-sequential, random, or pointer-chasing access patterns.

Stride prefetching detects constant-offset patterns in memory accesses (e.g., accessing elements in a multi-dimensional array with a fixed stride). It learns the stride distance and prefetches addresses accordingly.

• Algorithm: Monitors the difference (delta) between successive memory addresses. A consistent delta establishes a stride pattern.
• Use Case: Essential for scientific computing, matrix operations, and regular loop structures.
• Example: In a loop accessing array[i][j] where j is the inner loop, the stride is the size of the data type.

A Markov prefetcher uses a state machine or table to learn probabilistic transitions between memory addresses. If address A is frequently followed by address B, it will prefetch B upon seeing A.

• Model: Builds a graph where nodes are addresses and edges represent observed transitions with probabilities.
• Strength: Can capture complex, non-sequential correlations, such as pointer-based data structures (trees, graphs).
• Cost: Requires significant storage for the transition table and logic for training and prediction.

This technique identifies and exploits correlation between different memory access streams. It uses a history buffer of recent accesses to find repeating sequences.

• Global History Buffer (GHB): A common structure that stores a compressed history of recent misses. Prefetchers like the Access Map Pattern Matching (AMPM) use the GHB to detect patterns.
• Operation: On a miss, it searches the history for a matching sequence and prefetches the addresses that followed that sequence previously.
• Application: Effective for irregular patterns with long-term repetition, common in server and database workloads.

Software prefetching involves explicit programmer or compiler insertion of prefetch instructions (e.g., __builtin_prefetch in C/C++) into the code. This provides precise, semantic control over what data to fetch and when.

• Control: The developer specifies the memory address and a hint about the intended use (e.g., for read or write).
• Advantage: Can prefetch data for complex, algorithmic patterns that hardware cannot easily predict.
• Challenge: Requires deep understanding of the algorithm and data layout; incorrect prefetches can pollute the cache and degrade performance.

In agentic systems, prefetching extends beyond raw addresses to the semantic retrieval of context. The system predicts which knowledge, tools, or API schemas an autonomous agent will need next based on its plan or current task state.

• Semantic Prefetching: Uses the agent's goal or a step in its reasoning loop to pre-load relevant context from a vector store or knowledge graph.
• Tool Prefetching: Anticipates which external tools or APIs an agent will call and pre-loads their specifications or authentication tokens.
• Benefit: Dramatically reduces the latency of retrieval-augmented generation (RAG) and tool-calling loops, critical for maintaining agent responsiveness.

The multi-level structure of CPU caches where each successive level is larger, slower, and shared among more cores. Prefetching operates within this hierarchy, predicting and moving data from main memory (RAM) into these faster caches before the CPU needs it.

• L1 Cache: Fastest, smallest, private per core.
• L2 Cache: Larger, slower, often private or shared between a few cores.
• L3 Cache: Largest, slowest (but still faster than RAM), shared among all cores on a chip.

The principle that programs tend to access data in predictable patterns, which prefetching algorithms exploit. There are two key types:

• Temporal Locality: Recently accessed data is likely to be accessed again soon.
• Spatial Locality: Data located near recently accessed data is likely to be accessed next (e.g., the next element in an array). Prefetchers analyze these patterns to load anticipated data into cache, reducing cache misses and improving performance.

A specialized cache for virtual memory address translations. Just as a data prefetcher predicts data accesses, a TLB prefetcher predicts future page table walks. It speculatively loads page table entries (mappings from virtual to physical addresses) into the TLB before a memory access requires them, hiding the latency of the page table lookup process.

The hardware component that manages memory access, performing virtual-to-physical address translation, memory protection, and cache control. The MMU interacts directly with prefetching logic. When a prefetcher predicts a future memory address, the MMU must translate that virtual address and check permissions before the data can be fetched into the cache hierarchy.

A memory design for multi-processor systems where a processor can access its local memory faster than non-local memory (memory attached to another processor). NUMA-aware prefetching is crucial; a prefetcher must not only predict what data to fetch but also from which memory node, as fetching from a remote node incurs significantly higher latency, potentially negating the benefit of prefetching.

A capability that allows hardware subsystems (like storage or network controllers) to transfer data to/from main memory independently of the CPU. While not prefetching per se, DMA is a related offloading mechanism. It allows large, predictable data transfers (e.g., loading a file from disk) to occur without CPU intervention, freeing the CPU and its prefetchers to focus on optimizing access to the application's working set in cache.