Graph memory access prediction stays accurate after shuffling
Topology Survives Shuffling: Robust Long-Context Memory Access Prediction for Graph Analytics
Machine Learning
Summary
Memory access prediction helps computers work faster by guessing where to look next in complex graph data. Existing methods tend to learn short, layout-dependent patterns, so they fail when the graph changes. The authors created LoCoMAP, a system that uses longer memory histories and can predict farther ahead, making predictions more robust to changes in graph layout. They tested it on various graph tasks and found it works well even when the node order is shuffled, meaning it learns deeper, transferable graph patterns.
What this means in practice
- •For software engineers: Improve graph processing by integrating robust memory prefetching that works across different graph layouts without retraining.
- •For hardware architects: Design memory prefetchers that leverage long-context predictors to hide latency in irregular graph workloads more effectively.
Authors
Dongyan Sun, Neelesh Gupta, Rajgopal Kannan, Viktor K. Prasanna
Abstract
Graph analytics generates irregular, topology-dependent memory-access streams via indirect traversals, limiting data prefetching. Accurate prediction enables timely prefetches that hide memory latency. However, ML predictors couple short histories with fixed horizons, fitting the training trace's node layout rather than learning transferable graph patterns. We propose LoCoMAP, a long-context representation-learning framework for memory-access prediction with independently controlled observation history and prediction horizon. We evaluate Connected Components (CC), PageRank (PR), and Single-Source Shortest Paths (SSSP) on six synthetic graph families, with Erdos-Renyi (ER) and Grid as random and deterministic controls. We test two interventions: same-family regeneration changes connectivity, while node shuffling disrupts layout but preserves connectivity. Across 18 graph-workload pairs, extending history from 8 to 128 accesses improves F1 by 7.8%, while extending prediction horizon from 8 to 512 improves F1 by 88.3%. For CC, regeneration is less disruptive than shuffling: without retraining, long context retains 95.4% of original F1 and outperforms short context in six families. Under full shuffle, long context improves CC F1 by 33.6% across ER, Barabasi-Albert, Copying Model, and Stochastic Block Model (SBM), with a 2.06x gain on SBM, but not on Watts-Strogatz or Grid, where near-zero delta mass shifts into heavy tails beyond the predictor's range. Long context outperforms short context on six real-world CC graphs. At full shuffle, long-context PR retains 57.6% of original F1 and averages 11.0% above short context. Both SSSP models retain about 30% of original F1 under full shuffle as distance updates access vertex data in a new order. Within these bounds, long-context predictors are robust across related graphs and layouts without retraining, enabling a generalizable graph prefetcher.