Rethinking Virtual Memory Translation for Parallelism

Elastic Cuckoo Page Table is 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 traditional radix page table uses a sequential pointer-chasing process of four memory lookup to find the translation.

Radix page table

Large NVM memories result in more tlb miss. Thus, the new Intel Sunny Cove microarchitecture introduces 5-level radix page tables!

Hashed page table

The major problems of hashed page tables:

  1. low spatial locality
  2. space overhead of hash tags
  3. hash collisions
  4. table resize

Placing contiguous page table entries solves the above two problems.

Cuckoo Hash solves the third.

Elastic Cuckoo Hash solves the last by performing gradual resizing.