Efficient fine-grained virtual memory (2018)

Virtual memory in modern computer systems provides a single abstraction of the memory hierarchy.\nBy hiding fragmentation and overlays of physical memory, virtual memory frees applications from managing physical memory and improves programmability.\nHowever, virtual memory often introduces noticeable overhead. \nState-of-the-art systems use a paged virtual memory that maps virtual addresses to physical addresses \nin page granularity (typically 4 KiB ).This mapping is stored as a page table. Before accessing physically addressed memory, the page table is accessed \nto translate virtual addresses to physical addresses. Research shows that the overhead of accessing the page table can even exceed the execution time for some important applications.\nIn addition, this fine-grained mapping changes the access patterns between virtual and physical address spaces, introducing difficulties to many architecture techniques, such as caches and prefecthers.\n\nIn this dissertation, I propose architecture mechanisms to reduce the overhead of accessing and managing fine-grained virtual memory without compromising existing benefits. \nThere are three main contributions in this dissertation.\n\nFirst, I investigate the impact of address translation on cache. I examine the restriction of virtually indexed, physically tagged (VIPT) caches with fine-grained paging and conclude that this restriction may lead to sub-optimal cache designs. \nI introduce a novel cache strategy, speculatively indexed, physically tagged (SIPT) to enable flexible cache indexing under fine-grained page mapping. \nSIPT speculates on the value of a few more index bits (1 - 3 in our experiments) to access the cache speculatively before translation, and then verify that the physical tag matches after translation. \nUtilizing the fact that a simple relation generally exists between virtual and physical addresses, because memory allocators often exhibit contiguity, I also propose low-cost mechanisms to predict and correct potential mis-speculations.\n\nNext, I focus on reducing the overhead of address translation for fine-grained virtual memory. I propose a novel architecture mechanism, Embedded Page Translation Information (EMPTI), \nto provide general fine-grained page translation information on top of coarse-grained virtual memory. \n\nEMPTI does so by speculating that a virtual address is mapped to a pre-determined physical location and then verifying the translation with a very-low-cost access to metadata embedded with data.\nCoarse-grained virtual memory mechanisms (e.g., segmentation) are used to suggest the pre-determined physical location for each virtual page. \nOverall, EMPTI achieves the benefits of low overhead translation while keeping the flexibility and programmability of fine-grained paging.\n\nFinally, I improve the efficiency of metadata caching based on the fact that memory mapping contiguity generally exists beyond a page boundary.\nIn state-of-the-art architectures, caches treat PTEs (page table entries) as regular data. Although this is simple and straightforward,\nit fails to maximize the storage efficiency of metadata. \nEach page in the contiguously mapped region costs a full 8-byte PTE. However, the delta between virtual addresses and physical addresses remain the same and most metadata are identical.\nI propose a novel microarchitectural mechanism that expands the effective PTE storage in the last-level-cache (LLC) and reduces the number of page-walk accesses that miss the LLC.