Reducing the costs of virtual memory through better data structures


Virtual memory imposes a pervasive performance cost: every memory reference must undergo translation from a virtual address to a physical one. CPUs accelerate this task with Translation Lookaside Buffers (TLBs), which are small caches of recently used translations. Unfortunately, TLBs are small, but modern workloads are growing, meaning that TLB hit rates are declining. When the TLB can't serve a translation, the CPU must perform a lookup in the page table. Unfortunately, page-table lookups are also getting more expensive, due to the transition from 32-bit to 64-bit address spaces and due to the increasing use of virtualization, which squares the worst-case translation cost.

This project is exploring new hashing-based techniques to (1) increase the number of translations that a TLB can hold and, (2) reduce the cost of TLB misses.


External Researchers

  • Donald E. Porter
  • Guido Tagliavini
  • Janet Vorobyeva
  • Jun Yuan
  • Martin Farach-Colton
  • Michael A. Bender
  • Nirjhar Mukherjee
  • Sudarsan Kannan
  • William Jannen

Related Publications


  • Active VMW Software Systems Projects

Research Areas

  • Data Structures
  • Virtual Memory