"Agile Paging: Exceeding the Best of Nested and Shadow Paging” by Jayneel Gandhi, has been accepted as an IEEE Micro Top Pick of the year 2016!


Abstract: Virtualization provides benefits for many workloads, but the overheads of virtualizing memory are not universally low. The cost comes from managing two levels of address translation—one in the guest virtual machine (VM) and the other in the host virtual machine monitor (VMM)— with either nested or shadow paging. Nested paging directly performs a two-level page walk that makes TLB misses slower than unvirtualized native, but enables fast page tables changes. Alternatively, shadow paging restores native TLB miss speeds, but requires costly VMM intervention on page table updates.

This paper proposes agile paging that combines both techniques and exceeds the best of both. A virtualized page walk starts with shadow paging and optionally switches in the same page walk to nested paging where frequent page table updates would cause costly VMM interventions. Agile paging enables most TLB misses to be handled as fast as native while most page table changes avoid VMM intervention. It requires modest changes to hardware (e.g., demark when to switch) and VMM policies (e.g., predict good switching opportunities).

We emulate the proposed hardware and prototype the software in Linux with KVM on x86-64. Agile paging performs more than 12% better than the best of the two techniques and comes within 4% of native execution for all workloads.

IEEE Micro Background: "IEEE Micro collects some of this year's most significant research papers in computer architecture conferences based on novelty and potential for long-term impact. It publishes these papers yearly as "Micro's Top Picks from the Computer Architecture Conferences" in its May / June issue. The Top Picks committee through this issue recognize those significant and insightful papers that have the potential to influence the work of computer architects for years to come."