Paging and the address-translation problem

Michael A. Bender, Abhishek Bhattacharjee, Alex Conway, Martín Farach-Colton, Rob Johnson, Sudarsun Kannan, William Kuszmaul, Nirjhar Mukherjee, Don Porter, Guido Tagliavini, Janet Vorobyeva, Evan West

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

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. 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 many 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. This paper 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.

Original languageEnglish (US)
Title of host publicationSPAA 2021 - Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages105-117
Number of pages13
ISBN (Electronic)9781450380706
DOIs
StatePublished - Jul 6 2021
Event33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021 - Virtual, Online, United States
Duration: Jul 6 2021Jul 8 2021

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021
Country/TerritoryUnited States
CityVirtual, Online
Period7/6/217/8/21

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • Address translation
  • Hashing
  • Iceberg
  • Paging
  • Tlb
  • Virtual memory

Fingerprint

Dive into the research topics of 'Paging and the address-translation problem'. Together they form a unique fingerprint.

Cite this