{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T18:28:06Z","timestamp":1772044086467,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T00:00:00Z","timestamp":1733788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2024,12,10]]},"abstract":"<jats:p>This paper proposes a scalable optimal page replacement policy (OPT) simulator called ScaleOPT to scale the OPT simulation by leveraging multi-core parallelism. Specifically, we first propose AccessMap which collects the future references of pages in parallel before the OPT simulation. It enables calculating the next reference time of the accessed page in a constant time. Second, we introduce Pipelined-Tree consisting of multiple trees which organize caches based on min-max reference times. It enables traverse and update operations of each cache to be performed in a partially parallel manner (i.e., pipelined), thereby scaling out the OPT simulation on multi-cores. Finally, we implement ScaleOPT with two techniques and evaluate it on a 72-core machine. The experimental results demonstrate that ScaleOPT improves the simulation time by up to 6.3\u00d7, 7.7\u00d7, 20.5\u00d7, and 13.9\u00d7 compared with the long-established standard algorithm-based simulator along with our AccessMap, a variable-size cache scheme, and two widely-used cache simulators (webcachesim and libCacheSim), respectively.<\/jats:p>","DOI":"10.1145\/3700426","type":"journal-article","created":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T12:12:12Z","timestamp":1734091932000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["ScaleOPT: A Scalable Optimal Page Replacement Policy Simulator"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4138-4197","authenticated-orcid":false,"given":"Hyungseok","family":"Han","sequence":"first","affiliation":[{"name":"goorm Inc., Seongnam-si, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0891-5286","authenticated-orcid":false,"given":"Sangjin","family":"Lee","sequence":"additional","affiliation":[{"name":"Chung-Ang University, Seoul, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4512-0121","authenticated-orcid":false,"given":"Yongseok","family":"Son","sequence":"additional","affiliation":[{"name":"Chung-Ang University, Seoul, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/6617.6621"},{"key":"e_1_2_1_2_1","volume-title":"Martin Kong, Sriram Krishnamoorthy, Louis-Noel Pouchet, and P Sadayappan.","author":"Bao Wenlei","year":"2019","unstructured":"Wenlei Bao, Prashant Singh Rawat, Martin Kong, Sriram Krishnamoorthy, Louis-Noel Pouchet, and P Sadayappan. 2019. Efficient cache simulation for affine computations. In Languages and Compilers for Parallel Computing. Springer International Publishing, 65--85."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.1993.134"},{"key":"e_1_2_1_4_1","volume-title":"The datacenter as a computer: An introduction to the design of warehouse-scale machines","author":"Barroso Luis Andre","unstructured":"Luis Andre Barroso and Jimmy Clidaras. 2022. The datacenter as a computer: An introduction to the design of warehouse-scale machines. Springer Nature."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/363011.363155"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3224427"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI).","author":"Berger Daniel S","year":"2017","unstructured":"Daniel S Berger, Ramesh K Sitaraman, and Mor Harchol-Balter. 2017. AdaptSize: Orchestrating the hot object memory cache in a content delivery network. In Proceedings of the 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI)."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 2017 USENIX Annual Technical Conference (ATC '17)","author":"Blankstein Aaron","year":"2017","unstructured":"Aaron Blankstein, Siddhartha Sen, and Michael J Freedman. 2017. Hyperbolic caching: Flexible caching for web applications. In Proceedings of the 2017 USENIX Annual Technical Conference (ATC '17). 499--511."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2555670.2466482"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_12_1","unstructured":"Fernando J Corbato. 1968. A paging experiment with the multics system. Technical Report. MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC. 217--228 pages."},{"key":"e_1_2_1_13_1","volume-title":"22nd USENIX Conference on File and Storage Technologies (FAST). 51--69","author":"Dai Yifan","year":"2024","unstructured":"Yifan Dai, Jing Liu, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2024. Symbiosis: The art of application and kernel cache cooperation. In 22nd USENIX Conference on File and Storage Technologies (FAST). 51--69."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627703.3650078"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.295"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/WSC.1990.129605"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3007787.3001146"},{"key":"e_1_2_1_18_1","volume-title":"Simon C Steely Jr, and Joel Emer","author":"Jaleel Aamer","year":"2010","unstructured":"Aamer Jaleel, Kevin B Theobald, Simon C Steely Jr, and Joel Emer. 2010. High performance cache replacement using re-reference interval prediction (RRIP). ACM SIGARCH computer architecture news, Vol. 38, 3 (2010), 60--71."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2005 USENIX Annual Technical Conference (ATC '05)","author":"Jiang Song","year":"2005","unstructured":"Song Jiang, Feng Chen, and Xiaodong Zhang. 2005. CLOCK-Pro: An effective improvement of the CLOCK replacement.. In Proceedings of the 2005 USENIX Annual Technical Conference (ATC '05)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/511399.511340"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 20th International Conference on Very Large Data Bases (VLDB).","author":"Johnson Theodore","year":"1994","unstructured":"Theodore Johnson, Dennis Shasha, et al. 1994. 2Q: A low overhead high performance buffer management replacement algorithm. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1177\/0037549705051697"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 6th USENIX Conference on File and Storage Technologies (FAST)","volume":"8","author":"Kim Hyojun","year":"2008","unstructured":"Hyojun Kim and Seongjun Ahn. 2008. BPLRU: A buffer management scheme for improving random writes in flash storage.. In Proceedings of the 6th USENIX Conference on File and Storage Technologies (FAST), Vol. 8. 1--14."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/359863.359878"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2001.970573"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304067"},{"key":"e_1_2_1_28_1","volume-title":"https:\/\/github.com\/1a1a11a\/libCacheSim. Last accessed","year":"2024","unstructured":"libCacheSim. 2023. https:\/\/github.com\/1a1a11a\/libCacheSim. Last accessed: Oct 10, 2024."},{"key":"e_1_2_1_29_1","volume-title":"https:\/\/linux-mm.org\/PageReplacementDesign. Last accessed","author":"PageReplacementDesign MM.","year":"2024","unstructured":"LinuxMM. 2017. PageReplacementDesign. https:\/\/linux-mm.org\/PageReplacementDesign. Last accessed: Oct 10, 2024."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.92.0078"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1090694.1090708"},{"key":"e_1_2_1_32_1","volume-title":"https:\/\/github.com\/itsjohncs\/minmaxheap-cpp. Last accessed","year":"2024","unstructured":"minmaxheap cpp. 2016. https:\/\/github.com\/itsjohncs\/minmaxheap-cpp. Last accessed: Oct 10, 2024."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1416944.1416949"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170081"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES).","author":"Jung Dawoon","year":"2006","unstructured":"Seon-yeong Park, Dawoon Jung, Jeong-uk Kang, Jin-soo Kim, and Joonwon Lee. 2006. CFLRU: A replacement algorithm for flash memory. In Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2007.25"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST).","author":"Rodriguez Liana V.","year":"2021","unstructured":"Liana V. Rodriguez, Farzana Yusuf, Steven Lyons, Eysler Paz, Raju Rangaswami, Jason Liu, Ming Zhao, and Giri Narasimhan. 2021. Learning cache replacement with CACHEUS. In Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA53966.2022.00048"},{"key":"e_1_2_1_39_1","volume-title":"22nd USENIX Conference on File and Storage Technologies (FAST). 89--105","author":"Shakiba Kia","year":"2024","unstructured":"Kia Shakiba, Sari Sultan, and Michael Stumm. 2024. Kosmo: Efficient online miss ratio curve generation for eviction policy evaluation. In 22nd USENIX Conference on File and Storage Technologies (FAST). 89--105."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI). 529--544","author":"Song Zhenyu","year":"2020","unstructured":"Zhenyu Song, Daniel S Berger, Kai Li, Anees Shaikh, Wyatt Lloyd, Soudeh Ghorbani, Changhoon Kim, Aditya Akella, Arvind Krishnamurthy, Emmett Witchel, et al. 2020. Learning relaxed Belady for content distribution network caching. In Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI). 529--544."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems.","author":"Rabin","unstructured":"Rabin A. Sugumar and Santosh G. Abraham. 1993. Efficient simulation of caches under optimal replacement with applications to miss characterization. In Proceedings of the 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627703.3650066"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3277332.3277335"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 2017 USENIX Annual Technical Conference (ATC '17)","author":"Waldspurger Carl","year":"2017","unstructured":"Carl Waldspurger, Trausti Saemundsson, Irfan Ahmad, and Nohhyun Park. 2017. Cache modeling and optimization using miniature simulations. In Proceedings of the 2017 USENIX Annual Technical Conference (ATC '17)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2750482.2750490"},{"key":"e_1_2_1_46_1","volume-title":"https:\/\/github.com\/sunnyszy\/lrb. Last accessed","year":"2024","unstructured":"webcachesim2. 2020. https:\/\/github.com\/sunnyszy\/lrb. Last accessed: Oct 10, 2024."},{"key":"e_1_2_1_47_1","volume-title":"22nd USENIX Conference on File and Storage Technologies (FAST). 347--371","author":"Lin-Kit Wong Daniel","year":"2024","unstructured":"Daniel Lin-Kit Wong, Hao Wu, Carson Molder, Sathya Gunasekar, Jimmy Lu, Snehal Khandkar, Abhinav Sharma, Daniel S Berger, Nathan Beckmann, and Gregory R Ganger. 2024. Baleen: ML admission & prefetching for flash caches. In 22nd USENIX Conference on File and Storage Technologies (FAST). 347--371."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST). 307--323","author":"Wu Kan","year":"2021","unstructured":"Kan Wu, Zhihan Guo, Guanzhou Hu, Kaiwei Tu, Ramnatthan Alagappan, Rathijit Sen, Kwanghyun Park, Andrea C Arpaci-Dusseau, and Remzi H Arpaci-Dusseau. 2021. The storage hierarchy is not a hierarchy: Optimizing caching on modern storage devices with orthus. In Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST). 307--323."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3423137"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3468521"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3379472"},{"key":"e_1_2_1_52_1","volume-title":"2020 USENIX Annual Technical Conference (ATC '20)","author":"Zhang Yu","year":"2020","unstructured":"Yu Zhang, Ping Huang, Ke Zhou, Hua Wang, Jianying Hu, Yongguang Ji, and Bin Cheng. 2020. OSCA: An online-model based cache allocation scheme in cloud block storage systems. In 2020 USENIX Annual Technical Conference (ATC '20). 785--798."},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI). 1229--1246","author":"Zhang Yazhuo","year":"2024","unstructured":"Yazhuo Zhang, Juncheng Yang, Yao Yue, Ymir Vigfusson, and KV Rashmi. 2024. SIEVE is simpler than LRU: an efficient turn-key eviction algorithm for web caches. In Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI). 1229--1246."},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST).","author":"Zheng Da","year":"2015","unstructured":"Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E Priebe, and Alexander S Szalay. 2015. FlashGraph: Processing billion-node graphs on an array of commodity SSDs. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST)."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700426","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:13:26Z","timestamp":1755908006000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,10]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,12,10]]}},"alternative-id":["10.1145\/3700426"],"URL":"https:\/\/doi.org\/10.1145\/3700426","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,10]]},"assertion":[{"value":"2024-12-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}