View all Seminars  |  Download ICal for this event

2-Level Page Tables (2-LPT): A building block for efficient address translation in virtualized environment

Series: M.Tech (Research) Colloquium

Speaker: Akshay Baviskar

Date/Time: Nov 30 16:30:00

Location: Online Meeting - ONLINE

Faculty Advisor: R. Govindarajan

Efficient address translation mechanisms are gaining more and more attention as the virtual address range of the processors keeps expanding and the demand for machine virtualization increases with cloud and data center-based services. Traditional radix-tree based address translations can incur significant overheads in big data applications, particularly under virtualization, due to multi-level tree walks and nested translation. The overheads stem primarily from unnecessary generality --- ability to support several hundreds of thousands of virtual memory regions in the virtual address space --- supported by current processors.
We observe that in the common case, however, a process's virtual address space contains only a few contiguously allocated sections, which can be efficiently translated using a shallow tree with two levels. We propose such a compact structure, called 2-Level Page Table(2-LPT), which is a key building block for address translation in virtualized environment. A key advantage of 2-LPT is that it maintains two levels of page tables irrespective of the size of the virtual address space. Translating a virtual address (VA) using 2-LPT is fast. A walk on a 2-LPT requires up to two memory accesses. In practice, however, the root level table is well cached in the PWC, thus, single memory access is sufficient. Under native execution, 2-LPT reduces the time spent in page walks by up to 20.9% (9.38% on average) and improves performance by up to 10.1% (1.66% on average) over the conventional four-level radix tree page tables, on a set of memory-intensive applications.
2-LPT is more beneficial under virtualization. The proposed 2-LPT design reduces the cost of nested page walk from 24 to 8 memory accesses. To achieve further reduction, we propose two optimizations: (i) Enhanced Partial Shadow Paging (ePSP) which employs a limited form of shadow paging for the root-level of 2-LPT, and (ii) Host PTE Mirroring (HPM) which allows accessing the host page table entry without performing host page table walk. These allow us to largely avoid slow VM exits while effectively reducing the number of memory access on a nested address translation to just one, on average. 2-LPT speeds up applications by 5.6%-50.9% (24.4%, on average) over the baseline with conventional nested page walks. Importantly, it reduces page walk cycles and execution time of the best performing state-of-the-art proposal by 17.1%-57.1% and by 3.9%-43.9%, respectively.
MS Team's Meeting Link:

Speaker Bio:

Host Faculty: R. Govindarajan