Toward Intelligent Prefetching: A Survey on Complex Memory Access Prediction Techniques

Abstract

Data prefetching is a critical technique for bridging the processor-memory performance gap by predicting future memory accesses and retrieving data into on-chip caches before demand. While traditional prefetchers based on next-line, stride, and correlation heuristics perform well for regular access patterns, they are fundamentally inadequate for the irregular, data-dependent patterns prevalent in modern workloads such as graph analytics, sparse matrix computations, and pointer-intensive applications. This survey presents a systematic review of papers using a PRISMA-guided selection methodology. We propose a structured taxonomy that organizes prefetching techniques across three dimensions: locality type, including spatial and temporal locality; implementation layer, including hardware, software, and hybrid approaches; and, for the increasingly important class of ML-based prefetchers, learning paradigm, including supervised, reinforcement, and unsupervised learning, paired with training mode, including online and offline training. Through a multi-dimensional comparative analysis of ML-based prefetchers evaluated across storage overhead, accuracy, inference latency, hardware feasibility, and generalization ability, we identify three key findings: an accuracy-overhead Pareto frontier defined by model class, a natural architectural mapping between model complexity and cache hierarchy level, and a fundamental tension between runtime adaptability and model capacity that motivates hierarchical ensemble architectures.