{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T07:15:35Z","timestamp":1758438935326,"version":"3.44.0"},"reference-count":89,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"National Key Research and Development Program of China","award":["2022YFB3105100"],"award-info":[{"award-number":["2022YFB3105100"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3762997","type":"journal-article","created":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T11:50:47Z","timestamp":1755863447000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Augur: Semantics-Aware Temporal Prefetching for Linked Data Structure"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-3118-8477","authenticated-orcid":false,"given":"Feng","family":"Xue","sequence":"first","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences","place":["Beijing, China"]},{"name":"University of Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6118-3541","authenticated-orcid":false,"given":"Junliang","family":"Wu","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences","place":["Beijing, China"]},{"name":"University of Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-1247-9644","authenticated-orcid":false,"given":"Chenji","family":"Han","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences","place":["Beijing, China"]},{"name":"University of Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2640-8173","authenticated-orcid":false,"given":"Xinyu","family":"Li","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences","place":["Beijing, China"]},{"name":"University of Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1724-4904","authenticated-orcid":false,"given":"Tingting","family":"Zhang","sequence":"additional","affiliation":[{"name":"Loongson Technology Co. Ltd.","place":["Beijing, China"]},{"name":"Institute of Computing Technology Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5341-1343","authenticated-orcid":false,"given":"Tianyi","family":"Liu","sequence":"additional","affiliation":[{"name":"The University of Texas at San Antonio","place":["San Antonio, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0430-3669","authenticated-orcid":false,"given":"Fuxin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,19]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"OLogN Technologies AG. 2018. Alloc Test. Retrieved August 16 2025 from http:\/\/ithare.com\/testing-memory-allocators-ptmalloc2-tcmalloc-hoard-jemalloc-while-trying-to-simulate-real-world-loads\/"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3296957.3173189"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA59077.2024.00090"},{"key":"e_1_3_1_5_2","first-page":"91","volume-title":"Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques","author":"Al-Sukhni Hassan","year":"2003","unstructured":"Hassan Al-Sukhni, Daniel A. Connors, and Ian Bratt. 2003. Compiler-directed content-aware prefetching for dynamic data structures. In Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques. IEEE, Los Alamitos, CA, USA, 91."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/379240.379251"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2014.6974670"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00021"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2019.00053"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3085572"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544839"},{"key":"e_1_3_1_12_2","unstructured":"Scott Beamer Krste Asanovi\u0107 and David Patterson. 2015. The GAP benchmark suite. (2015). arXiv:1508.03619. Retrieved from https:\/\/arxiv.org\/abs\/1508.03619"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/1247360.1247401"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480114"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358325"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3185768.3185771"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2370816.2370832"},{"issue":"2","key":"e_1_3_1_18_2","first-page":"186","article-title":"Simultaneous subordinate microthreading (SSMT)","volume":"27","author":"Chappell Robert S.","year":"1999","unstructured":"Robert S. Chappell, Jared Stark, Sangwook P. Kim, Steven K. Reinhardt, and Yale N. Patt. 1999. Simultaneous subordinate microthreading (SSMT). Annual International Symposium on Computer Architecture 27, 2 (1996), 186\u2013195.","journal-title":"Annual International Symposium on Computer Architecture"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.381947"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/986533.986536"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2007.23"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2002.1176239"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/563998.564037"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/605432.605427"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/263580.263597"},{"key":"e_1_3_1_27_2","first-page":"1173","volume-title":"Proceedings of the 51st Annual International Symposium on Computer Architecture.","author":"Duong Quang","year":"2025","unstructured":"Quang Duong, Akanksha Jain, and Calvin Lin. 2025. A new formulation of neural data prefetching. In Proceedings of the 51st Annual International Symposium on Computer Architecture.IEEE, 1173\u20131187."},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2009.4798232"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA57654.2024.00040"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","unstructured":"Nathan Gober Gino Chacon Lei Wang Paul V. Gratz Daniel A. Jimenez Elvira Teran Seth Pugsley and Jinchun Kim. 2022. The championship simulator: Architectural simulation for education and competition. (2022). DOI:10.48550\/arXiv.2210.14324","DOI":"10.48550\/arXiv.2210.14324"},{"key":"e_1_3_1_31_2","unstructured":"Google. 2021. LevelDB. Retrieved August 16 2025 from https:\/\/github.com\/google\/leveldb"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480058"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2016.7783764"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2830772.2830812"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1186736.1186737"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2967938.2967958"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2016.7753257"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2003.1183549"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2540708.2540730"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO56248.2022.00071"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/264107.264207"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2014.29"},{"issue":"1","key":"e_1_3_1_43_2","first-page":"393","article-title":"Inter-core prefetching for multicore processors using migrating helper threads","volume":"39","author":"Kamruzzaman Md","year":"2011","unstructured":"Md Kamruzzaman, Steven Swanson, and Dean M. Tullsen. 2011. Inter-core prefetching for multicore processors using migrating helper threads. Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems 39, 1 (2011), 393\u2013404.","journal-title":"Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems"},{"key":"e_1_3_1_44_2","first-page":"206","volume-title":"Proceedings of the 6th International Symposium on High-Performance Computer Architecture.","author":"Karlsson Magnus","year":"2000","unstructured":"Magnus Karlsson, Fredrik Dahlgren, and Per Stenstrom. 2000. A prefetching technique for irregular accesses to linked data structures. In Proceedings of the 6th International Symposium on High-Performance Computer Architecture.. IEEE, Los Alamitos, CA, USA, 206\u2013217."},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2013.61"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2016.7783763"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2018.00018"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2008.224"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.1995.476830"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/379240.379250"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/237090.237190"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2016.7446087"},{"key":"e_1_3_1_53_2","article-title":"Introducing the graph 500","author":"Murphy Richard C.","year":"2010","unstructured":"Richard C. Murphy, Kyle B. Wheeler, Brian W. Barrett, and James A. Ang. 2010. Introducing the graph 500. Cray Users Group (2010). Retrieved August 16, 2025 from https:\/\/graph500.org","journal-title":"Cray Users Group"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2005.11"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2005.49"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.5555\/1116644.1116665"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2003.1183532"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2003.1261383"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA52012.2021.00024"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00040"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3613424.3614255"},{"key":"e_1_3_1_62_2","first-page":"975","volume-title":"Proceedings of the 55th Annual IEEE\/ACM International Symposium on Microarchitecture.","author":"Navarro-Torres Agust\u00edn","year":"2023","unstructured":"Agust\u00edn Navarro-Torres, Biswabandan Panda, Jes\u00fas Alastruey-Bened\u00e9, Pablo Ib\u00e1\u00f1ez, V\u00edctor Vi\u00f1als Y\u00fafera, and Alberto Ros. 2023. Berti: An accurate local-delta data prefetcher. In Proceedings of the 55th Annual IEEE\/ACM International Symposium on Microarchitecture.IEEE, 975\u2013991."},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2004.10030"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2018.00019"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA45697.2020.00021"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/3613424.3614245"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/2749469.2749473"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/3345000"},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2014.6835971"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150019.1136501"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/291069.291034"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/300979.300989"},{"key":"e_1_3_1_73_2","volume-title":"Proceedings of the 5th JILP Workshop on Computer Architecture Competitions: Championship Branch Prediction.","author":"Seznec Andr\u00e9","year":"2016","unstructured":"Andr\u00e9 Seznec. 2016. Tage-sc-l branch predictors again. In Proceedings of the 5th JILP Workshop on Computer Architecture Competitions: Championship Branch Prediction."},{"key":"e_1_3_1_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/605432.605403"},{"key":"e_1_3_1_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/2830772.2830793"},{"key":"e_1_3_1_76_2","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446752"},{"key":"e_1_3_1_77_2","doi-asserted-by":"publisher","DOI":"10.5555\/545215.545235"},{"key":"e_1_3_1_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555766"},{"key":"e_1_3_1_79_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2006.38"},{"key":"e_1_3_1_80_2","volume-title":"Arm Cortex-X3 Core Technical Reference Manual","author":"Technology Arm","year":"2022","unstructured":"Arm Technology. 2022. Arm Cortex-X3 Core Technical Reference Manual. Retrieved August 16, 2025 from https:\/\/developer.arm.com\/documentation\/101593\/0102\/"},{"key":"e_1_3_1_81_2","first-page":"956","volume-title":"Proceedings of the 55th Annual IEEE\/ACM International Symposium on Microarchitecture.","author":"Vavouliotis Georgios","year":"2023","unstructured":"Georgios Vavouliotis, Gino Chacon, Lluc Alvarez, Paul V. Gratz, Daniel A. Jim\u00e9nez, and Marc Casas. 2023. Page size aware cache prefetching. In Proceedings of the 55th Annual IEEE\/ACM International Symposium on Microarchitecture.IEEE, Los Alamitos, CA, USA, 956\u2013974."},{"key":"e_1_3_1_82_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2009.4798239"},{"key":"e_1_3_1_83_2","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2010.21"},{"key":"e_1_3_1_84_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2005.50"},{"key":"e_1_3_1_85_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2021.3065909"},{"key":"e_1_3_1_86_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358300"},{"key":"e_1_3_1_87_2","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322225"},{"key":"e_1_3_1_88_2","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512555"},{"key":"e_1_3_1_89_2","doi-asserted-by":"publisher","DOI":"10.1145\/335231.335248"},{"key":"e_1_3_1_90_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2007.346187"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3762997","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T00:48:10Z","timestamp":1758329290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3762997"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,19]]},"references-count":89,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3762997"],"URL":"https:\/\/doi.org\/10.1145\/3762997","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2025,9,19]]},"assertion":[{"value":"2024-11-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-14","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}