PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Memory Access Patterns

Milad Hashemi, Kevin Swersky, Jamie A. Smith, Grant Ayers, Heiner Litz, Jichuan Chang, Christos Kozyrakis, Parthasarathy Ranganathan

arXiv:1803.02329v1cs.LGstat.ML

TL;DR

Memory access prediction is difficult because memory latency creates a major bottleneck and address spaces are sparse. The paper applies recurrent neural networks to prefetching through sequence-based classification, finding higher precision and recall than table-based approaches while identifying important deployment limitations.

  • Problem

    Memory performance is a critical bottleneck, and learning cache-miss access patterns remains difficult because application address spaces are extremely sparse.

  • Method

    The paper discretizes memory addresses into a vocabulary and applies recurrent neural networks to predict future cache misses from access-trace features.

  • Results

    Recurrent neural networks significantly outperform state-of-the-art traditional hardware prefetchers on benchmark datasets, with higher precision and recall.

  • Takeaways & Limitations

    The results demonstrate the potential of neural networks as practical replacements for traditional hardware prefetchers and motivate further machine-learning research in computer architecture.

  • Takeaways & Limitations

    The train-offline, test-online setup may become less effective as accurate prefetching changes the cache-miss distribution, while online adaptation could increase computational and memory burden.

Abstract

from arXiv · show

The explosion in workload complexity and the recent slow-down in Moore's law scaling call for new approaches towards efficient computing. Researchers are now beginning to use recent advances in machine learning in software optimizations, augmenting or replacing traditional heuristics and data structures. However, the space of machine learning for computer hardware architecture is only lightly explored. In this paper, we demonstrate the potential of deep learning to address the von Neumann bottleneck of memory performance. We focus on the critical problem of learning memory access patterns, with the goal of constructing accurate and efficient memory prefetchers. We relate contemporary prefetching strategies to n-gram models in natural language processing, and show how recurrent neural networks can serve as a drop-in replacement. On a suite of challenging benchmark datasets, we find that neural networks consistently demonstrate superior performance in terms of precision and recall. This work represents the first step towards practical neural-network based prefetching, and opens a wide range of exciting directions for machine learning in computer architecture research.

1. Introduction

The paper applies sequence-based neural networks to memory prefetching, targeting the memory wall and the limitations of traditional hardware predictors. It frames prefetching as a sparse sequence-prediction problem and reports that recurrent models outperform traditional prefetchers.

  • Prefetching mitigates the memory wall by predicting which data to bring into cache before use.Modern applications can spend over 50% of compute cycles waiting for memory.
  • Traditional table-based predictors become costly to scale as modern workloads develop very large working sets.
  • Neural networks offer a sequence-learning approach to microarchitectural prediction, extending techniques used in natural language processing.
  • The paper treats memory addresses as a large, sparse output space and uses recurrent neural networks to model the next access.This reframes prefetching as analogous to next-word or character prediction.
  • On benchmark datasets, recurrent neural networks significantly outperform state-of-the-art traditional hardware prefetchers in precision and recall.The models also produce interpretable representations of semantic information in memory access traces.

2. Background

Hardware prefetchers predict future memory accesses from past history using stride or correlation patterns. The paper places recurrent models in this sequence-prediction landscape and describes LSTMs as a mechanism for modeling long-range dependencies.

  • Stride prefetchers learn stable address deltas and prefetch ahead of a repeatable demand stream.For example, accesses 0, 4, 8, 12 imply a stride of four.
  • Correlation prefetchers store access history in large tables to predict irregular patterns beyond a single stable stride.
  • Deep learning models, including recurrent neural networks, are widely used for sequential prediction and can model long-range dependencies.
  • An LSTM maintains hidden and cell states, with input, forget, and output gates controlling stored and propagated information.
  • Each LSTM step computes the gates, updates the cell state, and computes the hidden output state.
  • The gate equations use concatenated current input and previous hidden state, elementwise multiplication, sigmoid nonlinearity, layer weights, and biases.LSTM layers may be stacked so one layer’s output becomes the next layer’s input.

3. Problem Formulation

The paper formulates prefetching as prediction from cache-miss addresses and instruction addresses, then converts sparse address regression into vocabulary-based classification. It further uses address deltas to improve consistency across executions.

  • 3.1. Prefetching as a Prediction Problem: Prefetching predicts future cache-missing memory accesses from past access history.
  • 3.1. Prefetching as a Prediction Problem: Many prefetchers use cache-miss address sequences and associated program-counter sequences as prediction features.
  • 3.1. Prefetching as a Prediction Problem: Program-counter sequences expose higher-level control-flow patterns, while miss-address sequences indicate which address to prefetch next.Both features are represented as 64-bit integers.
  • 3.1. Prefetching as a Prediction Problem: O(100M) cache misses contain only O(10M) unique addresses on average within a 2^64 physical address space, making regression difficult.The address space is sparse, wide, and severely multimodal.
  • 3.1. Prefetching as a Prediction Problem: Figure 1 illustrates sparse cache-miss addresses at multiple scales on the omnetpp benchmark.
  • 3.2. Prefetching as Classification: The method treats addresses as a discrete vocabulary and performs classification, analogous to next-word or character prediction in NLP.
  • 3.2. Prefetching as Classification: 2^64 possible softmax targets require quantization, while cache-line accuracy usually requires predictions within 64 bytes.Page-level predictions within 4096 bytes would still leave 2^52 possible targets.
  • 3.2. Prefetching as Classification: A training-derived vocabulary of common addresses reduces target size, but unseen test-time addresses limit coverage.

4. Models

The paper introduces two LSTM-based prefetching models: an embedding LSTM and a clustering-based LSTM that exploits local address-space structure to reduce vocabulary and model size.

  • Embedding LSTM: The embedding LSTM uses categorical input and output delta representations, embeds the PC and delta, and classifies over a restricted delta vocabulary.It concatenates the embeddings before feeding them to a two-layer LSTM; the highest-probability deltas are selected for prefetching.
  • Embedding LSTM: The embedding LSTM selects the top-10 predictions at each timestep, trading higher cache-hit probability against possible eviction of useful cache items.The paper does not explore beam search or direct multi-step prediction.
  • Embedding LSTM: Large vocabularies increase computational and storage footprint, while vocabulary truncation caps accuracy and rare deltas create a rare-word problem.These limitations constrain model size, achievable accuracy, and learning for infrequent patterns.
  • Clustering + LSTM: The clustering-based LSTM partitions addresses into k-means regions and computes within-cluster deltas, producing smaller delta sets than the global vocabulary.Figure 3 shows two of six omnetpp clusters, with accesses colored by their generating PC.
  • Clustering + LSTM: A multi-task LSTM models all clusters with tied weights while using cluster ID as an additional feature that supplies cluster-specific biases.This reduces model size while preserving separate cluster-conditioned behavior.
  • Clustering + LSTM: Cluster-local deltas can be normalized as real-valued inputs, avoiding a large embedding matrix while retaining classification for next-delta prediction.Regression remained too inaccurate to be practical, and de-normalization can magnify small inaccuracies.
  • Clustering + LSTM: The clustering-based model requires address-space preprocessing and models only local context, so it cannot model dynamics causing accesses to move between regions.Its design specifically exploits rich local address-space context.

5. Experiments

The experiments evaluate LSTM-based prefetchers on cache-miss traces from SPEC CPU2006 and Google web search, comparing them with traditional hardware designs. Across benchmarks, LSTMs generally dominate in precision, while clustering improves recall relative to the embedding model.

  • 5. Experiments: The evaluation measures neural prefetchers' ability to predict cache misses against traditional hardware prefetchers.Cache-miss sequences are derived by simulating dynamic memory traces through an Intel Broadwell cache model.
  • 5.1. Data Collection: The benchmark suite combines memory-intensive SPEC CPU2006 applications with Google's enterprise-scale web search workload.SPEC CPU2006 provides standard system benchmarks, while web search adds a workload with larger working sets and industrial relevance.
  • 5.1. Data Collection: Traces are split into 70% training and 30% evaluation, with each LSTM trained independently on each dataset.The embedding LSTM uses ADAM, whereas the clustering LSTM uses Adagrad.
  • 5.2. Evaluation Metrics: Precision-at-10 counts a prediction as correct when the true delta appears among the model's 10 highest-probability predictions.Labels outside the model's output vocabulary count as failures.
  • 5.2. Evaluation Metrics: Recall-at-10 measures the diversity of deltas predicted across the test set, without weighting deltas by their relative frequency.This metric uses the cardinality of predicted deltas over all test-time predictions.
  • 5.4. Model Comparison: LSTM models generally dominate traditional prefetchers in precision, while the stream prefetcher achieves high recall through its dynamic vocabulary.The GHB PC/DC prefetcher targets more complex patterns but has lower recall than the stream prefetcher.
  • 5.4. Model Comparison: The clustering + LSTM tends to achieve higher recall than the embedding LSTM, although neither model clearly outperforms the other in precision.The authors attribute the recall difference likely to the clustering model's multiple vocabularies and suggest ensembling as future work.
  • 5.5. Predictive information of ∆s vs PCs: Delta sequences provide most information for high precision, whereas PC sequences improve recall.The ablation removes one delta or PC input to compare the information content of the two modalities.

6. Related Work

Related work connects machine learning in microarchitecture with branch prediction, memory-controller scheduling, performance tuning, and hardware or software feature analysis. It also covers neural approaches to prefetching, learned data structures, program behavior, program synthesis, and source-code modeling.

  • 6.1. Machine Learning in Microarchitecture: Machine learning has been applied to microarchitecture through branch prediction, memory-controller scheduling, performance tuning, and bandit-based feature analysis.These applications use linear classification, reinforcement learning, performance knobs, or bandit methods for hardware-related decisions.
  • 6.1. Machine Learning in Microarchitecture: Prior LSTM prefetching work modeled regular non-stride patterns with squared-loss regression on randomly generated traces.The cited work identifies irregular patterns caused by workload behavior or multicore reordering as challenging for regression-based approaches.
  • 6.1. Machine Learning in Microarchitecture: Learned database indexes replace generic structures such as b-trees and bloom filters with models adapted to data distributions.The paper relates its clustering approach to this distribution-specific modeling strategy.
  • 6.2. Learning Program Behavior: Memory traces provide a bottom-up representation of dynamic program behavior, complementing top-down neural modeling of program structure.This distinction frames memory-access learning as a different view of program behavior from source-code-oriented approaches.
  • 6.2. Learning Program Behavior: Program-synthesis research has used LSTMs to generate outputs from program representations and Neural Turing Machines to solve sorting, copying, and associative-recall tasks.The Neural Turing Machine augments an LSTM with external memory and attention.
  • 6.2. Learning Program Behavior: Source-code modeling includes probabilistic grammars, n-gram language models, neural language models, and neural mining of online code repositories.These methods model source code directly rather than modeling properties of the resulting program.

7. Conclusion and Future Work

The paper finds that neural models can outperform table-based prefetchers while revealing program structure in memory traces. It identifies offline evaluation, timeliness, runtime adaptation, reinforcement learning, and hardware implementation as important future challenges.

  • Neural prefetching models demonstrate significantly higher precision and recall than table-based approaches.
  • The study evaluates an offline-trained, online-tested model using precision and recall, but accurate prefetching can change cache-miss distributions and reduce a static RNN’s effectiveness.
  • Future work includes online RNN adaptation, training on hits and misses, reinforcement learning, and controlling prefetcher aggressiveness in dynamic environments.
  • Prefetch timeliness matters because fetching too early can evict unused data, whereas fetching too late leaves little latency benefit.
  • The hardware feasibility of RNN prefetchers remains unevaluated, including whether accelerators can meet latency demands.
  • Replacing microarchitectural heuristics with learned systems raises broader questions beyond prefetching, including other speculative execution structures.
  • t-SNE analyses indicate that memory traces reflect program behavior and that learned representations capture program structure.

A. Interpreting t-SNE Plots

Mapping PCs back to source code shows that the model learned program structure in the challenging mcf and omnetpp applications.

  • The model learned program structure, as shown by mapping PCs back to source code in mcf and omnetpp.

A.1. mcf

The mcf analysis shows that t-SNE clusters group memory-access instructions by recurring program structures, including loop unrolling, linked-list traversal, and list insertion or removal.

  • mcf: A function from mcf appears in two different t-SNE clusters.
  • mcf: One cluster contains repeated instances of line 4 produced by loop unrolling at three different PCs.
  • mcf: A second cluster contains PCs responsible for linked-list traversal at lines 11 and 16.
  • mcf: The t-SNE visualization concatenates delta and PC embeddings and colors them by PC instruction for omnetpp.
  • mcf: The analyzed code inserts and removes items into an owner’s list.
  • mcf: The source code includes separate paths for removing an item from an owner’s child list and inserting it as the first element.
  • mcf: The main insertion and removal paths are mapped to the same t-SNE cluster.
  • mcf: The assembly examples show different PCs implementing the removal and insertion operations.

B. Experimental Results

The experimental precision and recall results are reported in Tables 2 and 3, while the LSTM hyperparameters are reported in Table 4.

  • Precision and recall experimental results are provided in Tables 2 and 3, respectively.
  • The hyperparameters for both LSTM models are provided in Table 4.

D. K-Means Clustering on an Address Trace

This section presents k-means clustering results for an omnetpp memory-address trace, alongside experimental precision, recall, and model-training hyperparameter tables.

  • D. K-Means Clustering on an Address Trace: The experiment runs k-means with 6 clusters on 10^6 addresses from omnetpp.
  • D. K-Means Clustering on an Address Trace: Table 2 reports experimental results for precision.
  • D. K-Means Clustering on an Address Trace: Table 3 reports experimental results for recall.
  • D. K-Means Clustering on an Address Trace: Table 4 lists the training hyperparameters for each model.
  • D. K-Means Clustering on an Address Trace: Figure 9 shows one million omnetpp memory accesses after k-means clustering on the address space.The figure concerns the address-trace structure after clustering.
Loading 1803.02329v1…