{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T14:10:10Z","timestamp":1755871810683,"version":"3.44.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"National Science Foundation","award":["CCF-2217395, CCF-2114319, CNS-1909099"],"award-info":[{"award-number":["CCF-2217395, CCF-2114319, CNS-1909099"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>Traditional workload analysis uses discrete times measured by data accesses. An example is the classic independent reference model (IRM). Effective solutions have been developed to model workloads with stochastic access patterns, but they incur a high cost for Zipfian workloads, which may contain millions of items each accessed with a different frequency.<\/jats:p>\n          <jats:p>This article first presents a continuous-time model of locality for workloads with stochastic access patterns. It shows that two previous techniques by Dan and Towsley and by Denning and Schwartz can be interpreted as a single model using different discrete times. Using continuous time, it derives a closed-form solution for an item and a general solution, that is, a differentiable function. In addition, the article presents an approximation technique by grouping items into partitions.<\/jats:p>\n          <jats:p>When evaluated using Zipfian workloads, it shows that a workload with millions of items can be approximated using a small number of partitions, and the continuous-time model has greater accuracy and is faster to compute numerically. For the largest data size verifiable using trace generation and simulation, the new techniques reduce the time of locality analysis by six orders of magnitude.<\/jats:p>","DOI":"10.1145\/3746450","type":"journal-article","created":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T07:07:16Z","timestamp":1751440036000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Continuous-Time Modeling of Zipfian Workload Locality"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-4034-2584","authenticated-orcid":false,"given":"Yiyang","family":"Wang","sequence":"first","affiliation":[{"name":"Computer Science, University of Rochester","place":["Rochester, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4968-6659","authenticated-orcid":false,"given":"Chen","family":"Ding","sequence":"additional","affiliation":[{"name":"Computer Science, University of Rochester","place":["Rochester, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-8479-3617","authenticated-orcid":false,"given":"Leo","family":"Sciortino","sequence":"additional","affiliation":[{"name":"Computer Science, University of Rochester","place":["Rochester, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2100-1517","authenticated-orcid":false,"given":"Linlin","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Rochester Institute of Technology","place":["Rochester, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,8,22]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254766"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2015.7056022"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1147\/rd.194.0353"},{"key":"e_1_3_2_5_2","unstructured":"Christian Berthet. 2017. Approximation of LRU caches miss rate: Application to power-law popularities. arXiv preprint arXiv:1705.10738. https:\/\/arxiv.org\/abs\/1705.10738"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2014.6883477"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459898.3463908"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2989081.2989119"},{"key":"e_1_3_2_9_2","volume-title":"Operating Systems Theory","author":"Jr. Edward G. Coffman","year":"1973","unstructured":"Edward G. Coffman Jr. and Peter J. Denning. 1973. Operating Systems Theory. Prentice-Hall."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/98457.98525"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/361268.361281"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359634"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1944862.1944885"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2010.5452069"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80014-7"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3185751"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/347837.347872"},{"key":"e_1_3_2_18_2","unstructured":"Joseph Izraelevitz Jian Yang Lu Zhang Juno Kim Xiao Liu Amirsaman Memaripour Yun Joon Soh Zixuan Wang Yi Xu Subramanya R. Dulloor Jishen Zhao and Steven Swanson. 2019. Basic performance measurements of the Intel Optane DC persistent memory module. arXiv preprint arXiv:1903.05714. https:\/\/arxiv.org\/abs\/1903.05714"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1815961.1815971"},{"key":"e_1_3_2_20_2","first-page":"485","volume-title":"Proceedings of the IFIP Congress","author":"King W. F.","year":"1971","unstructured":"W. F. King. 1971. Analysis of demand paging algorithms. In Proceedings of the IFIP Congress. 485\u2013490."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304067"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.92.0078"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.2172\/6051879"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357526.3357568"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","unstructured":"Ian Prechtl Chen Ding and Dorin Patru. 2020. Design and Evaluation of a Fixed-size Programmable Working-set Cache on FPGAs. (March2020). preprint online at DOI:10.13140\/RG.2.2.24423.60320.","DOI":"10.13140\/RG.2.2.24423.60320"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3422575.3422800"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3600090"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190227"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3488423.3519331"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357526.3357528"},{"key":"e_1_3_2_32_2","first-page":"95","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST)","author":"Waldspurger Carl A.","year":"2015","unstructured":"Carl A. Waldspurger, Nohhyun Park, Alexander T. Garthwaite, and Irfan Ahmad. 2015. Efficient MRC construction with SHARDS. In Proceedings of the USENIX Conference on File and Storage Technologies (FAST). 95\u2013110. Retrieved from https:\/\/www.usenix.org\/conference\/fast15\/technical-sessions\/presentation\/waldspurger"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2019.00056"},{"key":"e_1_3_2_34_2","first-page":"335","volume-title":"Proceedings of the Symposium on Operating Systems Design and Implementation","author":"Wires Jake","year":"2014","unstructured":"Jake Wires, Stephen Ingram, Zachary Drudi, Nicholas JA Harvey, Andrew Warfield, and Coho Data. 2014. Characterizing storage workloads with counter stacks. In Proceedings of the Symposium on Operating Systems Design and Implementation. USENIX Association, 335\u2013349."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.66"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451153"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3468521"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613147"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341109"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1552309.1552310"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3746450","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:29:23Z","timestamp":1755869363000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3746450"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,22]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3746450"],"URL":"https:\/\/doi.org\/10.1145\/3746450","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2025,8,22]]},"assertion":[{"value":"2024-05-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}