Reduced Associativity Memory Mapping in Computer Systems

Virtual address translation is increasingly becoming a bottleneck for big data applications. In modern systems, virtual memory abstracts each application’s memory space, offering convenience and isolation. However, the operating system must maintain mappings between virtual addresses and physical addresses, which has become a growing challenge. Most systems use a translation lookaside buffer (TLB) to cache recently used address translations, but the number of TLB entries is highly constrained by latency requirements and grows slower than the working sets of applications. Most solutions to this problem, such as huge pages, rely on physical contiguity for performance gains. Unfortunately, the requirement for physical contiguity leads to memory fragmentation, and the cost of defragmentation can easily nullify these gains. A common belief in virtual memory systems is that virtual address space should be fully associative, which means a virtual address can be mapped to any available physical page frame. While this approach maximizes memory utilization, it requires TLBs to store the full page frame number for each virtual page number. This dissertation challenges this convention by employing reduced associativity virtual memory mapping in a modern operating system. By exploiting the fact that a virtual page can only be mapped to one of several page frames, this dissertation introduces Mosaic pages, which increase TLB reach by compressing multiple, discrete translations into one TLB entry. Mosaic leverages virtual contiguity for locality, but does not use physical contiguity. Mosaic relies on recent advances in hashing theory to constrain memory mappings, in order to realize this physical address compression without reducing memory utilization or increasing swapping. This dissertation presents a full-system prototype of Mosaic, in gem5 and Linux. In simulation and with comparable hardware to a traditional design, Mosaic reduces TLB misses in several workloads by 6–34%. Our results show that reduced associativity memory mappings do not harm performance, we never see conflicts before memory is 98% full in our experiments. Once the memory is over-committed, Mosaic swaps similar to Linux in most cases. Then, we present a vertical bucket organization for Mosaic pages to handle kernel pages or unavailable page frames when using the whole system memory. Additionally, we show Mosaic page allocator can be used to allocate kernel memory by modifying the vmalloc memory allocator.