PATHFINDER: Practical Real-Time Learning for Data Prefetching

Neural prefetchers predict memory accesses well but cost hours of GPU training per program and a model far too large to sit next to a cache, so nobody ships them; Pathfinder (University of Utah) keeps the neural idea and swaps the neuron — spiking neurons add instead of multiplying, and they retune their own weights from the timing of their own spikes while inference is happening, so the prefetcher learns a new pattern within hundreds of cycles instead of hours, in 0.23 square millimetres — and the paper is unusually honest that the result is competitive rather than a breakthrough.

Why this problem is worth solving

The gap between what a processor can compute and what memory can supply keeps widening, and guessing well is one of the few remaining defences.

What has blocked that promise is not the prediction quality but the way the learning works.

What people did before, and where it broke

• Detect strides, offsets and repeating gaps with tables. The mainstream of prefetching, and what commercial processors actually ship. Where it broke. Each pattern family needs its own rules and its own tables, so covering the space means assembling an ensemble of specialised designs, and none of them tolerates noise in the access stream well.
• Record and replay address correlations. A temporal prefetcher remembers which addresses followed which, and replays the sequence when it recognises the start. Where it broke. It handles irregular pointer-chasing patterns that stride detection cannot, but it needs substantial storage for the history, and it can only replay what it has already seen.
• Train a recurrent network on address gaps. A published neural prefetcher clusters addresses to keep the vocabulary of gaps manageable, then trains a stack of recurrent layers to predict the next one. Where it broke. Training happens beforehand on part of the trace, so during deployment the model keeps meeting gaps it has never seen. Training it on three times as much data reduced unseen gaps by a tenth.
• Train a hierarchical network on address correlations. The strongest published neural prefetcher splits the prediction of page and offset across several recurrent models. Where it broke. It collects a fifty-million-instruction trace, trains for hours on a GPU, and deploys the model for the following fifty million instructions. Both the training and the inference cost sit orders of magnitude above what a hardware prefetcher can afford.
• Use reinforcement learning to find useful gaps at run time. A recent design learns online with low implementation complexity, which solves the adaptation problem directly. Where it broke. It learns by exploring, and the random exploration issues useless prefetches, consumes bandwidth chasing unpredictable patterns, and can settle into a poor local answer — this paper observes it fixing on a gap of one in a workload where better gaps existed.
• The gap. Everyone kept the neuron and argued about the network. Gradient descent is a global process over a labelled dataset, so anything built on it inherits a separate training phase, a large model, and an inability to react to the program actually running.

How Pathfinder predicts the next access

The idea

Change the neuron rather than the network, because the learning rule is what makes it unbuildable. Every previous neural prefetcher kept the artificial neuron and varied the architecture, which means it inherited gradient descent — a global optimisation over a labelled dataset, needing something like ten to the seventeenth operations to produce one model, and therefore a separate training phase, a large result, and no way to react to the program actually running. A spiking neuron has none of those properties. It integrates weighted input into a potential, leaks when idle, and fires on crossing a threshold, so it needs adders and no multipliers, which is why far more of them fit in a given area. More importantly it learns by a rule that consults only its own input and output timing, so a weight update is a local event costing almost nothing and happening while prediction happens. The prefetcher is never not training. Treating the spiking neuron as a hardware building block whose real constraint is where the weights live is the same engineering reality as the neuromorphic mapping work covered elsewhere on this site, which finds the same thing here — the weight buffer is 56 percent of the area and 94 percent of the power.

Learn from the program in front of you, not from a trace of a different one. The epoch structure of prior neural prefetchers is not incidental; it is what gradient descent forces. Collect, train, deploy, repeat, with the model frozen throughout its deployment and derived from behaviour that has already finished. Pathfinder reacts within hundreds of cycles, and it carries a second adaptation mechanism on top of the weight updates — every neuron label has a three-bit saturating counter that increments when the prediction was right and decrements when it was wrong, and at zero the label is simply erased so the neuron can be recruited for a different pattern. That matters because programs move between phases, and a design that keeps learning also has to keep forgetting. The paper measures the agility directly and finds the network re-labelling constantly, with only a handful of distinct gaps dominating any thousand-access window. Preferring what the running program is doing now over a profile of what it did earlier is the same argument as the runtime prefetch generation work covered elsewhere on this site.

Take the honest result, which is competitive rather than better. This is the rare paper that states its own limitation in the abstract and again in the introduction — it falls short of a large jump in prefetching performance, and more innovation in the algorithms is needed to realise the potential. The averages come out close to the best existing prefetchers rather than above them, with each design winning on a different part of the benchmark set, and the recommended configuration is an ensemble that prioritises Pathfinder and fills leftover slots from a next-line and a temporal prefetcher, edging out the best baseline by 0.3 percent. The paper argues that this is still the right thing to publish, because a design that is implementable today at under one percent of a processor is a better foundation for follow-up work than a design that is more accurate and cannot be built. Building a predictor meant to complement an existing one rather than replace it is the same posture as the priority-directed instruction prefetching work covered elsewhere on this site.

Turning a page access pattern into a prediction

Working per page and per instruction is what keeps the pattern coherent. Interleaved accesses from other instructions or other pages would otherwise mix into the history and destroy it. The cost is that nothing can be predicted about the first access to a page that has not been touched recently, which the paper leaves for future work.

Why it works

• Spiking neurons remove the multipliers. A potential is updated by adding a weight and reduced by leaking → so a neuron is two adders and a comparator instead of a multiply-accumulate array → which is why fifty of them plus their weights fit in about a fifth of a square millimetre at 12 nanometres.
• Local learning removes the training phase. A weight update needs only the timing of one neuron own inputs against its own output → so there is no global cost function, no labelled dataset, and no backward pass to schedule → and learning becomes something that happens during inference rather than instead of it.
• Framing the history as an image imports a solved problem. Recognising a fixed-size binary grid is exactly what spiking networks have already been shown to do well → so the authors could take an existing handwritten-digit model and change only the input shape → and pattern recognition arrives with noise tolerance already attached, at least in principle.
• Competition through inhibition assigns patterns to neurons automatically. Each neuron that fires suppresses all the others through a paired inhibitory neuron → so distinct patterns settle onto distinct neurons without anyone deciding which → and turning the inhibition down is a single knob that lets several neurons fire when higher prefetch degree is wanted.
• Confidence counters supply the forgetting that learning needs. Weight updates make neurons better at patterns but never retire a stale prediction → so a three-bit counter tracks whether each label is still correct and erases it at zero → which frees the neuron to be recruited when the program moves to a new phase.

What it costs (trade-offs and scope)

• The result is a tie, and the paper says so. The abstract states that more innovation in these algorithms is needed to maximise their potential, and the introduction says the work falls short of a large jump in performance. The conclusion describes the averages as similar to existing prefetchers, with each winning on a different part of the suite. The recommended ensemble beats the best baseline by 0.3 percent.
• It loses to the offline neural prefetcher where neural prediction helps most. On the four workloads where a neural approach genuinely beats a temporal prefetcher, Pathfinder is worse than the offline model on three, which the paper attributes directly to learning on the fly rather than training precisely on the whole trace.
• On one irregular workload it barely predicts at all. Where the reinforcement-learning prefetcher issued 1.95 million prefetches, Pathfinder issued about 1400 — it almost never reached high enough confidence. Being selective produces good accuracy and, in that case, essentially no coverage.
• A rule-based prefetcher wins outright on four other workloads. Recording and replaying address correlations substantially outperforms both neural approaches on four benchmarks, and the ensemble only partly recovers this because its priority ordering is fixed, so it sometimes behaves like Pathfinder alone and therefore worse than the temporal prefetcher alone.
• The headline margin over the offline gap predictor depends on how much that baseline was trained. It was trained on the first tenth of each trace, so it keeps meeting gaps it has never seen. Training it on three tenths recovered 4.6 percent of performance, against a reported 18.7 percent margin.
• Power is not the strong point. The area is smaller than the reinforcement-learning comparison, 0.23 against 0.33 square millimetres, but the power is roughly nine times higher, half a watt against 55 milliwatts, because the weights sit in register files. The weight buffer alone is 94 percent of the power.
• The predictions come from a software network, not the hardware. The prefetch decisions were produced by a GPU simulator of the spiking network; the register-transfer implementation was built and verified separately to measure area and power. These are two different artefacts.
• The noise tolerance is asserted more than demonstrated. The worked example feeds three slightly perturbed versions of a learned pattern, and the trained neuron recognises one of the three. The other two fire different neurons.
• Scope is narrow by construction. Only the next block within an already-touched page is predicted, so the first access to a cold page is future work. Evaluation is single-threaded, one million loads per benchmark across eleven traces, prefetching into the last-level cache only.

The evaluation

Check yourself

Sources

The paper is “Pathfinder: Practical Real-Time Learning for Data Prefetching” by Lin Jia, James Patrick McMahon, Sumanth Gudaparthi, Shreyas Singh and Rajeev Balasubramonian, all at the University of Utah, published at ASPLOS 2024 Volume 3, pages 785-800, DOI 10.1145/3620666.3651332. It is open access under a Creative Commons Attribution licence.

This explainer is written from the full text of the published paper. Everything above comes from its own sections 2 through 6: the argument in section 2.3 for why a neural prefetcher is worth pursuing at all, namely that rule-based designs need a separate set of rules per pattern family and tolerate noise poorly; the section 2.4 description of leaky-integrate-and-fire neurons and the spike timing rule, including the concession that spiking networks have historically lagged the accuracy of gradient descent; the section 3 architecture with its input layer sized by gap range and history length, fifty excitatory and fifty inhibitory neurons, and the encoding of the gap history as a binary grid processed as a Poisson spike train over 32 ticks; the training and inference tables that assign labels to self-organised neurons and the three-bit confidence counters that erase them; the extensions for multi-degree prefetching by two labels per neuron, for the first accesses to a page, for widening sparse pixels and shifting the middle gap against aliasing, and for approximating 32 ticks with one; the hardware estimates from a synthesised fifty-neuron implementation at 12 nanometres and from a cache model for the tables; the section 4 methodology using a simulator fork from the offline neural prefetcher authors over eleven traces from four benchmark suites at one million loads each; and the section 5 results, including the per-workload discussion of where the temporal prefetcher and the offline neural prefetcher each win, the issued-prefetch counts, the sensitivity studies on gap range, neuron count, tick count and periodic learning, and the repeated statements in the abstract, introduction and conclusion that the outcome is competitive rather than superior.