Memory-Efficient Hashed Page Tables

Jovan Stojkovic, Namrata Mantri, Dimitrios Skarlatos, Tianyin Xu, Josep Torrellas

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


Conventional radix-tree page tables have scalability challenges, as address translation following a TLB miss potentially requires multiple memory accesses in sequence. An alternative is hashed page tables (HPTs) where, conceptually, address translation needs only one memory access. Traditionally, HPTs have been shunned due to high costs of handling conflicts and other limitations. However, recent advances have made HPTs compelling. Still, a major issue in HPT designs is their requirement for substantial contiguous physical memory.This paper addresses this problem. To minimize HPTs' contiguous memory needs, it introduces the Logical to Physical (L2P) Table and the use of Dynamically-Changing Chunk Sizes. These techniques break down the HPT into discontiguous physical-memory chunks. In addition, the paper also introduces two techniques that minimize HPTs' total memory needs and, indirectly, reduce the memory contiguity requirements. These techniques are In-place Page Table Resizing and Per-way Resizing. We call our complete design Memory-Efficient HPTs (ME-HPTs). Compared to state-of-the-art HPTs, ME-HPTs: (i) reduce the contiguous memory allocation needs by 92% on average, and (ii) improve the performance by 8.9% on average. For the two most demanding workloads, the contiguous memory requirements decrease from 64MB to 1MB. In addition, compared to state-of-the-art radix-tree page tables, ME-HPTs achieve an average speedup of 1.23× (without huge pages) and 1.28× (with huge pages).

Original languageEnglish (US)
Title of host publication2023 IEEE International Symposium on High-Performance Computer Architecture, HPCA 2023 - Proceedings
PublisherIEEE Computer Society
Number of pages15
ISBN (Electronic)9781665476522
StatePublished - 2023
Event29th IEEE International Symposium on High-Performance Computer Architecture, HPCA 2023 - Montreal, Canada
Duration: Feb 25 2023Mar 1 2023

Publication series

NameProceedings - International Symposium on High-Performance Computer Architecture
ISSN (Print)1530-0897


Conference29th IEEE International Symposium on High-Performance Computer Architecture, HPCA 2023


  • Hashed page tables
  • Page tables
  • Virtual memory

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Memory-Efficient Hashed Page Tables'. Together they form a unique fingerprint.

Cite this