Elastic cuckoo page tables: Rethinking virtual memory translation for parallelism

Dimitrios Skarlatos, Apostolos Kokolis, Tianyin Xu, Josep Torrellas

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

Abstract

The unprecedented growth in the memory needs of emerging memory-intensive workloads has made virtual memory translation a major performance bottleneck. To address this problem, this paper introduces Elastic Cuckoo Page Tables, a novel page table design that transforms the sequential pointer-chasing operation used by conventional multi-level radix page tables into fully-parallel look-ups. The resulting design harvests, for the first time, the benefits of memory-level parallelism for address translation. Elastic cuckoo page tables use Elastic Cuckoo Hashing, a novel extension of cuckoo hashing that supports efficient page table resizing. Elastic cuckoo page tables efficiently resolve hash collisions, provide process-private page tables, support multiple page sizes and page sharing among processes, and dynamically adapt page table sizes to meet application requirements. We evaluate elastic cuckoo page tables with full-system simulations of an 8-core processor using a set of graph analytics, bioinformatics, HPC, and system workloads. Elastic cuckoo page tables reduce the address translation overhead by an average of 41% over conventional radix page tables. The result is a 3-18% speed-up in application execution.

Original languageEnglish (US)
Title of host publicationASPLOS 2020 - 25th International Conference on Architectural Support for Programming Languages and Operating Systems
PublisherAssociation for Computing Machinery
Pages1093-1108
Number of pages16
ISBN (Electronic)9781450371025
DOIs
StatePublished - Mar 9 2020
Event25th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2020 - Lausanne, Switzerland
Duration: Mar 16 2020Mar 20 2020

Publication series

NameInternational Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS

Conference

Conference25th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2020
CountrySwitzerland
CityLausanne
Period3/16/203/20/20

Keywords

  • Cuckoo Hashing
  • Page Tables
  • Virtual Memory

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Elastic cuckoo page tables: Rethinking virtual memory translation for parallelism'. Together they form a unique fingerprint.

  • Cite this

    Skarlatos, D., Kokolis, A., Xu, T., & Torrellas, J. (2020). Elastic cuckoo page tables: Rethinking virtual memory translation for parallelism. In ASPLOS 2020 - 25th International Conference on Architectural Support for Programming Languages and Operating Systems (pp. 1093-1108). (International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS). Association for Computing Machinery. https://doi.org/10.1145/3373376.3378493