{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T10:41:32Z","timestamp":1769856092260,"version":"3.49.0"},"reference-count":74,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T00:00:00Z","timestamp":1647475200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-2114319, CNS-1909099, and CCF-1717877"],"award-info":[{"award-number":["CCF-2114319, CNS-1909099, and CCF-1717877"]}]},{"name":"IBM Center for Advanced Studies"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>\n            Data movement is a common performance bottleneck, and its chief remedy is caching. Traditional cache management is transparent to the workload: data that should be kept in cache are determined by the recency information only, while the program information, i.e., future data reuses, is not communicated to the cache. This has changed in a new cache design named\n            <jats:italic>Lease Cache<\/jats:italic>\n            . The program control is passed to the lease cache by a compiler technique called Compiler Assigned Reference Lease (CARL). This technique collects the reuse interval distribution for each reference and uses it to compute and assign the lease value to each reference.\n          <\/jats:p>\n          <jats:p>In this article, we prove that CARL is optimal under certain statistical assumptions. Based on this optimality, we prove miss curve convexity, which is useful for optimizing shared cache, and sub-partitioning monotonicity, which simplifies lease compilation. We evaluate the potential using scientific kernels from PolyBench and show that compiler insertions of up to 34 leases in program code achieve similar or better cache utilization (in variable size cache) than the optimal fixed-size caching policy, which has been unattainable with automatic caching but now within the potential of cache programming for all tested programs and most cache sizes.<\/jats:p>","DOI":"10.1145\/3498730","type":"journal-article","created":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T09:31:30Z","timestamp":1647509490000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["CARL: Compiler Assigned Reference Leasing"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4968-6659","authenticated-orcid":false,"given":"Chen","family":"Ding","sequence":"first","affiliation":[{"name":"University of Rochester, Rochester, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3751-7997","authenticated-orcid":false,"given":"Dong","family":"Chen","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0715-7313","authenticated-orcid":false,"given":"Fangzhou","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1633-397X","authenticated-orcid":false,"given":"Benjamin","family":"Reber","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4429-0623","authenticated-orcid":false,"given":"Wesley","family":"Smith","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,17]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3446804.3446842"},{"key":"e_1_3_3_3_2","volume-title":"Compilers: Principles, Techniques, and Tools (2nd ed.)","author":"Aho Alfred V.","year":"2006","unstructured":"Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley."},{"key":"e_1_3_3_4_2","volume-title":"Optimizing Compilers for Modern Architectures: A Dependence-based Approach","author":"Allen Randy","year":"2001","unstructured":"Randy Allen and Ken Kennedy. 2001. Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann Publishers."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1455567.1455599"},{"key":"e_1_3_3_6_2","volume-title":"Dependence Analysis","author":"Banerjee Utpal","year":"1997","unstructured":"Utpal Banerjee. 1997. Dependence Analysis. Kluwer. I\u2013XVII, 1\u2013214 pages."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158120"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2015.7056022"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/363011.363155"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/646667.700030"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2004.09.004"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/11847366_23"},{"key":"e_1_3_3_14_2","volume-title":"Proceedings of the International Symposium on Memory Management","author":"Brock Jacob","year":"2013","unstructured":"Jacob Brock, Xiaoming Gu, Bin Bao, and Chen Ding. 2013. Pacman: Program-assisted cache management. In Proceedings of the International Symposium on Memory Management."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2015.84"},{"key":"e_1_3_3_16_2","first-page":"150","volume-title":"Proceedings of the International Conference on Supercomputing","author":"Cascaval Calin","year":"2003","unstructured":"Calin Cascaval and David A. Padua. 2003. Estimating cache misses and locality using stack distances. In Proceedings of the International Conference on Supercomputing. 150\u2013159."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378859"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459898.3463908"},{"key":"e_1_3_3_19_2","series-title":"Lecture Notes in Computer Science","first-page":"89","volume-title":"Languages and Compilers for Parallel Computing, LCPC 2019, Atlanta, GA, October 22-24, 2019, Revised Selected Papers","author":"Chen Dong","year":"2019","unstructured":"Dong Chen, Chen Ding, and Dorin Patru. 2019. CLAM: Compiler leasing of accelerator memory. In Languages and Compilers for Parallel Computing, LCPC 2019, Atlanta, GA, October 22-24, 2019, Revised Selected Papers(Lecture Notes in Computer Science, Vol. 11998), Santosh Pande and Vivek Sarkar (Eds.), Springer, 89\u201397."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192402"},{"key":"e_1_3_3_21_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_3_22_2","volume-title":"Engineering a Compiler, 2nd Edition","author":"Cooper Keith","year":"2010","unstructured":"Keith Cooper and Linda Torczon. 2010. Engineering a Compiler, 2nd Edition. Morgan Kaufmann."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1780.1783"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/363095.363141"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3399709"},{"key":"e_1_3_3_26_2","volume-title":"Proc. 3rd International Workshop on Polyhedral Compilation Techniques (IMPACT\u201913)","author":"Doerfert Johannes","year":"2013","unstructured":"Johannes Doerfert, Clemens Hammacher, Kevin Streit, and Sebastian Hack. 2013. Spolly: Speculative optimizations in the polyhedral model. In Proc. 3rd International Workshop on Polyhedral Compilation Techniques (IMPACT\u201913), Armin Gr\u00f6\u00dflinger and Louis-No\u00ebl Pouchet."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2012.43"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1944862.1944885"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2677010"},{"key":"e_1_3_3_30_2","first-page":"27","volume-title":"Proceedings of the International Conference on Parallel Architecture and Compilation Techniques","author":"Fang Changpeng","year":"2005","unstructured":"Changpeng Fang, Steve Carr, Soner \u00d6nder, and Zhenlin Wang. 2005. Instruction based memory distance analysis and its application. In Proceedings of the International Conference on Parallel Architecture and Compilation Techniques. 27\u201337."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/325478.325479"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626412500107"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89740-8_15"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993478.1993485"},{"key":"e_1_3_3_35_2","first-page":"109","volume-title":"Proceedings of the International Symposium on Memory Management","author":"Gu Xiaoming","year":"2012","unstructured":"Xiaoming Gu and Chen Ding. 2012. A generalized theory of collaborative caching. In Proceedings of the International Symposium on Memory Management. 109\u2013120."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314606"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/339647.339660"},{"key":"e_1_3_3_38_2","volume-title":"Proceedings of the ACM Conference on Theory of Computing","author":"Hong J.","year":"1981","unstructured":"J. Hong and H. T. Kung. 1981. I\/O complexity: The red-blue pebble game. In Proceedings of the ACM Conference on Theory of Computing. Milwaukee, WI."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2611572"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3185751"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2016.17"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1815961.1815971"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837669"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/1582710.1582711"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304067"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-49051-7_10"},{"key":"e_1_3_3_47_2","first-page":"6237","volume-title":"Proceedings of the 37th International Conference on Machine Learning, (ICML\u201920), 13-18 July 2020, Virtual Event, Vol. 119","author":"Liu Evan Zheran","year":"2020","unstructured":"Evan Zheran Liu, Milad Hashemi, Kevin Swersky, Parthasarathy Ranganathan, and Junwhan Ahn. 2020. An imitation learning approach for cache replacement. In Proceedings of the 37th International Conference on Machine Learning, (ICML\u201920), 13-18 July 2020, Virtual Event, Vol. 119. PMLR, 6237\u20136247. http:\/\/proceedings.mlr.press\/v119\/liu20f.html. An Imitation Learning Approach for Cache Replacement. arXiv:2006.16239. Retrieved from https:\/\/arxiv.org\/abs\/2006.16239."},{"key":"e_1_3_3_48_2","unstructured":"Louis-Noel Pouchet and Tomofumi Yuki. 2018. PolyBench\/C 4.2. Retrieved from http:\/\/https:\/\/sourceforge.net\/projects\/polybench\/files\/."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1005686.1005691"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.92.0078"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/233561.233564"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3017992"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385989"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/503272.503283"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3422575.3422800"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA51647.2021.00033"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190227"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358319"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.165388"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/166955.166974"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/377792.377797"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/1151074.1151085"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/973097.973099"},{"key":"e_1_3_3_64_2","first-page":"487","volume-title":"Proceedings of USENIX Annual Technical Conference","author":"Waldspurger Carl A.","year":"2017","unstructured":"Carl A. Waldspurger, Trausti Saemundsson, Irfan Ahmad, and Nohhyun Park. 2017. Cache modeling and optimization using miniature simulations. In Proceedings of USENIX Annual Technical Conference. 487\u2013498. Retrieved from https:\/\/www.usenix.org\/conference\/atc17\/technical-sessions\/presentation\/waldspurger."},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2019.00056"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.5555\/645989.674328"},{"key":"e_1_3_3_67_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 J. A. 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_3_68_2","volume-title":"High Performance Compilers for Parallel Computing","author":"Wolfe M. J.","year":"1996","unstructured":"M. J. Wolfe. 1996. High Performance Compilers for Parallel Computing. Addison-Wesley, Redwood City, CA."},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.66"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451153"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.1275296"},{"key":"e_1_3_3_72_2","first-page":"191","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation","author":"Yang Juncheng","year":"2020","unstructured":"Juncheng Yang, Yao Yue, and K. V. Rashmi. 2020. A large scale analysis of hundreds of in-memory cache clusters at Twitter. In 14th USENIX Symposium on Operating Systems Design and Implementation. USENIX Association, 191\u2013208. Retrieved from https:\/\/www.usenix.org\/conference\/osdi20\/presentation\/yang."},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-015-0384-3"},{"key":"e_1_3_3_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341109"},{"key":"e_1_3_3_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/1552309.1552310"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498730","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498730","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:29Z","timestamp":1750188629000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498730"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,17]]},"references-count":74,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3498730"],"URL":"https:\/\/doi.org\/10.1145\/3498730","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,17]]},"assertion":[{"value":"2021-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}