{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:16:40Z","timestamp":1757621800533,"version":"3.44.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"NSF","award":["CCF-2106827, CCF-1725543, CSR-1763680, CCF-1716252, CNS-1938709, CCF-1617618, CCF-1916817, CCF-2106999, CSR-1938180, CCF-1715777, and NRT-HDR 2125295"],"award-info":[{"award-number":["CCF-2106827, CCF-1725543, CSR-1763680, CCF-1716252, CNS-1938709, CCF-1617618, CCF-1916817, CCF-2106999, CSR-1938180, CCF-1715777, and NRT-HDR 2125295"]}]},{"DOI":"10.13039\/100006602","name":"United States Air Force Research Laboratory","doi-asserted-by":"crossref","award":["FA8750-19-2-1000"],"award-info":[{"award-number":["FA8750-19-2-1000"]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>The classical paging problem, introduced by Sleator and Tarjan in 1985, formalizes the problem of caching pages in RAM in order to minimize IOs. Their online formulation ignores the cost of address translation: Programs refer to data via virtual addresses, and these must be translated into physical locations in RAM. Although the cost of an individual address translation is much smaller than that of an IO, every memory access involves an address translation, whereas IOs can be infrequent. In practice, one can spend money to avoid paging by over-provisioning RAM; in contrast, address translation is effectively unavoidable. Thus address-translation costs can sometimes dominate paging costs, and systems must simultaneously optimize both.<\/jats:p>\n          <jats:p>\n            To mitigate the cost of address translation, all modern CPUs have translation lookaside buffers (TLBs), which are hardware caches of common address translations. What makes TLBs interesting is that a single TLB entry can potentially encode the address translation for\n            <jats:italic toggle=\"yes\">many<\/jats:italic>\n            addresses. This is typically achieved via the use of huge pages, which translate runs of contiguous virtual addresses to runs of contiguous physical addresses. Huge pages reduce TLB misses at the cost of increasing the IOs needed to maintain contiguity in RAM. This tradeoff between TLB misses and IOs suggests that the classical paging problem does not tell the full story.\n          <\/jats:p>\n          <jats:p>This article introduces the Address-Translation Problem, which formalizes the problem of maintaining a TLB, a page table, and RAM in order to minimize the total cost of both TLB misses and IOs. We present an algorithm that achieves the benefits of huge pages for TLB misses without the downsides of huge pages for IOs.<\/jats:p>","DOI":"10.1145\/3737700","type":"journal-article","created":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T12:19:53Z","timestamp":1749039593000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Paging and the Address-Translation Problem"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7639-530X","authenticated-orcid":false,"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2742-2679","authenticated-orcid":false,"given":"Abhishek","family":"Bhattacharjee","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, Connecticut, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4890-7413","authenticated-orcid":false,"given":"Alex","family":"Conway","sequence":"additional","affiliation":[{"name":"Cornell University, New York City, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3616-7788","authenticated-orcid":false,"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"New York University, New York City, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0784-7410","authenticated-orcid":false,"given":"Rob","family":"Johnson","sequence":"additional","affiliation":[{"name":"VMware Research, Palo Alto, California, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4009-8586","authenticated-orcid":false,"given":"Sudarsun","family":"Kannan","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, New Jersey, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3855-3036","authenticated-orcid":false,"given":"William","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3327-8442","authenticated-orcid":false,"given":"Nirjhar","family":"Mukherjee","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9804-0857","authenticated-orcid":false,"given":"Don","family":"Porter","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill, Chapel Hill, North Carolina, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8493-1395","authenticated-orcid":false,"given":"Guido","family":"Tagliavini","sequence":"additional","affiliation":[{"name":"Google, Sunnyvale, California, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9396-6081","authenticated-orcid":false,"given":"Janet","family":"Vorobyeva","sequence":"additional","affiliation":[{"name":"University of California San Diego, La Jolla, California, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5974-7745","authenticated-orcid":false,"given":"Evan","family":"West","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, New York, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,9,8]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Couchbase. 2021. Disabling Transparent Huge Pages (THP). Retrieved February 11 2021 from https:\/\/docs.couchbase.com\/server\/current\/install\/thp-disable.html"},{"key":"e_1_3_2_3_2","unstructured":"MongoDB. 2021. Disable Transparent Huge Pages (THP). Retrieved February 11 2021 from https:\/\/docs.mongodb.com\/manual\/tutorial\/transparent-huge-pages\/"},{"key":"e_1_3_2_4_2","unstructured":"Oracle Database. 2021. Disabling Transparent Hugepages. Retrieved February 11 2021 from https:\/\/docs.oracle.com\/en\/database\/oracle\/oracle-database\/12.2\/ladbi\/disabling-transparent-hugepages.html"},{"key":"e_1_3_2_5_2","unstructured":"Percona. 2021. Settling the Myth of Transparent Hugepages for Databases. Retrieved February 11 2021 from https:\/\/www.percona.com\/blog\/2019\/03\/06\/settling-the-myth-of-transparent-hugepages-for-databases\/"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72914-3_13"},{"key":"e_1_3_2_8_2","unstructured":"AMD Inc. 2008. AMD-V nested paging."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2485922.2485943"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3625817"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch21"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591084"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2017.3711640"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037705"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/290169"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.001"},{"key":"e_1_3_2_17_2","first-page":", 374","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Brehob Mark","year":"2001","unstructured":"Mark Brehob, Richard Enbody, Eric Torng, and Stephen Wagner. 2001. On-line restricted caching. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 374\u2013383."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_18"},{"key":"e_1_3_2_19_2","unstructured":"WikiChip. 2020. Intel\u2019s Cascade Lake Microarchitecture. Retrieved February 2 2020 from https:\/\/en.wikichip.org\/wiki\/intel\/microarchitectures\/cascade_lake"},{"key":"e_1_3_2_20_2","volume-title":"A Paging Experiment with the Multics System","author":"Corbat\u00f3 Fernando J.","year":"1969","unstructured":"Fernando J. Corbat\u00f3. 1969. A Paging Experiment with the Multics System. MIT Project MAC Report MAC-M-384."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037704"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/363095.363141"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77891-2_2"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.04.023"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2015.7056035"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_3_2_27_2","first-page":"499","article-title":"Online companion caching","volume":"324","author":"Fiat Amos","year":"2002","unstructured":"Amos Fiat, Manor Mendel, and Steven Seiden. 2002. Online companion caching. Theoretical Computer Science 324 (September 2002), 499\u2013511.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071383"},{"key":"e_1_3_2_30_2","unstructured":"Mel Gorman. 2010. Linux Huge Pages. Retrieved from https:\/\/lwn.net\/Articles\/375096\/"},{"key":"e_1_3_2_31_2","unstructured":"Mel Gorman. 2018. AMD Zen Architecture. Retrieved from https:\/\/en.wikichip.org\/wiki\/amd\/microarchitectures\/zen"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582021"},{"key":"e_1_3_2_33_2","unstructured":"Intel Inc. 2016. Intel\u00ae 64 and IA-32 architectures software developer\u2019s manual volume 3A: System programming guide Part 1."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2016.7446100"},{"key":"e_1_3_2_35_2","first-page":"705","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI)","author":"Kwon Youngjin","year":"2016","unstructured":"Youngjin Kwon, Hangchen Yu, Simon Peter, Christopher J. Rossbach, and Emmett Witchel. 2016. Coordinated and efficient huge page management with Ingens. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI). USENIX Association, 705\u2013721."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060289.1060299"},{"key":"e_1_3_2_37_2","unstructured":"Stanko Novakovic Yizhou Shan Aasheesh Kolli Michael Cui Yiying Zhang Haggai Eran Liran Liss Michael Wei Dan Tsafrir and Marcos K. Aguilera. 2019. Storm: A fast transactional dataplane for remote data structures. arXiv:1902.02411. Retrieved from https:\/\/arxiv.org\/abs\/1902.02411"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304064"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3296957.3173203"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3140659.3080217"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3079856.3080217"},{"key":"e_1_3_2_42_2","first-page":"555","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Peserico Enoch","year":"2003","unstructured":"Enoch Peserico. 2003. Online paging with arbitrary associativity. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 555\u2013564."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2014.6835964"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2012.32"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2830772.2830773"},{"key":"e_1_3_2_46_2","unstructured":"H. Prokop. 1999. Cache Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49543-6_13"},{"key":"e_1_3_2_48_2","unstructured":"7-Zip LZMA Benchmark. 2021. SandyBridge. Retrieved from https:\/\/www.7-cpu.com\/cpu\/SandyBridge.html"},{"key":"e_1_3_2_49_2","first-page":"829","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Sen Sandeep","year":"2000","unstructured":"Sandeep Sen and Siddhartha Chatterjee. 2000. Towards a theory of cache-efficient algorithms. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, 829\u2013838."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3102980.3102982"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322223"},{"key":"e_1_3_2_54_2","first-page":"111","volume-title":"Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI \u201920)","author":"Yang Jian","year":"2020","unstructured":"Jian Yang, Joseph Izraelevitz, and Steven Swanson. 2020. FileMR: Rethinking RDMA networking for scalable persistent memory. In Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI \u201920). USENIX Association, 111\u2013125."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"e_1_3_2_56_2","first-page":"82","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Young Neal E.","year":"1998","unstructured":"Neal E. Young. 1998. On-line file caching. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, 82\u201386."},{"key":"e_1_3_2_57_2","unstructured":"WikiChip. 2020. AMD\u2019s Zen Microarchitecture. Retrieved July15 2020 from https:\/\/en.wikichip.org\/wiki\/amd\/microarchitectures\/zen"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3737700","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T15:51:25Z","timestamp":1757346685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3737700"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,8]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3737700"],"URL":"https:\/\/doi.org\/10.1145\/3737700","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,9,8]]},"assertion":[{"value":"2021-12-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}