A2P: Attention-based Memory Access Prediction for Graph Analytics

Pengmiao Zhang, Rajgopal Kannan, Anant Nori, Viktor Prasanna

2022

Abstract

Graphs are widely used to represent real-life applications including social networks, web search engines, bioinformatics, etc. With the rise of Big Data, graph analytics offers significant potential in exploring challenging problems on relational data. Graph analytics is typically memory-bound. One way to hide the memory access latency is through data prefetching, which relies on accurate memory access prediction. Traditional prefetchers with pre-defined rules cannot adapt to complex graph analytics memory patterns. Recently, Machine Learning (ML) models, especially Long Short-Term Memory (LSTM), have shown improved performance for memory access prediction. However, existing models have shortcomings including unstable LSTM models, interleaved patterns in labels using consecutive deltas (difference between addresses), and large output dimensions. We propose A2P, a novel attention-based memory access prediction model for graph analytics. We apply multi-head attention to extract features, which are easier to be trained than LSTM. We design a novel bitmap labeling method, which collects future deltas within a spatial range and makes the patterns easier to be learned. By constraining the prediction range, bitmap labeling provides up to 5K compression for model output dimension. We further introduce a novel concept of super page, which allows the model prediction to break the constraint of a physical page. For the widely used GAP benchmark, our results show that for the top three predictions, A2P outperforms the widely used state-of-the-art LSTM-based model by 23.1% w.r.t. Precision, 21.2% w.r.t. Recall, and 10.4% w.r.t. Coverage.

Paper Citation

in Harvard Style

Zhang P., Kannan R., Nori A. and Prasanna V. (2022). A2P: Attention-based Memory Access Prediction for Graph Analytics. In Proceedings of the 11th International Conference on Data Science, Technology and Applications - Volume 1: DATA, ISBN 978-989-758-583-8, pages 135-145. DOI: 10.5220/0011309700003269

in Bibtex Style

@conference{data22,
author={Pengmiao Zhang and Rajgopal Kannan and Anant Nori and Viktor Prasanna},
title={A2P: Attention-based Memory Access Prediction for Graph Analytics},
booktitle={Proceedings of the 11th International Conference on Data Science, Technology and Applications - Volume 1: DATA,},
year={2022},
pages={135-145},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0011309700003269},
isbn={978-989-758-583-8},
}

in EndNote Style

TY - CONF

JO - Proceedings of the 11th International Conference on Data Science, Technology and Applications - Volume 1: DATA,
TI - A2P: Attention-based Memory Access Prediction for Graph Analytics
SN - 978-989-758-583-8
AU - Zhang P.
AU - Kannan R.
AU - Nori A.
AU - Prasanna V.
PY - 2022
SP - 135
EP - 145
DO - 10.5220/0011309700003269