EUVIMEDEUVIMED entdecken
Crossref

Augur: Semantics-Aware Temporal Prefetching for Linked Data Structure

Feng Xue, Junliang Wu, Chenji Han, Xinyu Li, Tingting Zhang, Tianyi Liu, Fuxin Zhang

ACM Transactions on Architecture and Code Optimization · 30.09.2025 · 22 (3) · 1-27

DOI: 10.1145/3762997 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Architecture and Code Optimization, online erschienen am 19.09.2025. Verfasst von Feng Xue und 6 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 89 Literaturangaben. Gefördert von: National Key Research and Development Program of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Linked data structures (LDS), such as lists and trees, are widely used in modern applications. Traversing LDS typically involves a significant amount of pointer chasing. Due to the serial nature of memory access in pointer chasing, the incurred long memory latency of traversing LDS has become a critical performance bottleneck. Furthermore, the poor spatial locality in LDS makes it difficult for spatial prefetchers to predict access addresses. Although temporal prefetchers can handle irregular memory access patterns, hindered by the challenges of collecting semantic information, current state-of-the-art temporal prefetchers suffer from significant metadata redundancy and frequent metadata conflicts. Consequently, there remain substantial opportunities to enhance the LDS prefetching. To solve this problem, we propose Augur, a semantics-aware temporal prefetcher to enhance LDS performance. Augur utilizes a novel pruning method to obtain semantic information and effectively extracts node address correlations from the perspective of nodes in LDS, thereby diminishing the metadata redundancy and conflicts. Additionally, Augur employs efficient metadata management strategies that guarantee a minimal storage overhead. Evaluated on LDS workloads, Augur achieves an average performance speedup of 17.8% and 11.7% over the baseline stride prefetcher and state-of-the-art spatial prefetcher Berti, respectively. Furthermore, Augur outperforms the state-of-the-art temporal prefetcher MISB, Triage, and Triangel, by 17.4%, 12.8%, and 6.3%, respectively, with a significantly lower storage overhead of only 1.26 KB.

Förderung

  • National Key Research and Development Program of China

Zitieren

APA

Xue, F., Wu, J., Han, C., Li, X., Zhang, T., Liu, T., & Zhang, F. (2025). Augur: Semantics-Aware Temporal Prefetching for Linked Data Structure. ACM Transactions on Architecture and Code Optimization, 22(3), 1-27. https://doi.org/10.1145/3762997

Vancouver

Xue F, Wu J, Han C, Li X, Zhang T, Liu T, et al. Augur: Semantics-Aware Temporal Prefetching for Linked Data Structure. ACM Transactions on Architecture and Code Optimization. 2025;22(3):1-27. doi:10.1145/3762997

BibTeX
@article{Xue2025,
  author = {Xue, Feng and Wu, Junliang and Han, Chenji and Li, Xinyu and Zhang, Tingting and Liu, Tianyi and Zhang, Fuxin},
  title = {Augur: Semantics-Aware Temporal Prefetching for Linked Data Structure},
  journal = {ACM Transactions on Architecture and Code Optimization},
  year = {2025},
  volume = {22},
  number = {3},
  pages = {1--27},
  doi = {10.1145/3762997}
}
Kostenlos starten →