Studies that evaluate new architectural designs of virtual memory typically employ a "model-based" methodology that relies on simulations of the translation lookaside buffer (TLB) coupled with empirical performance models. We observe that this methodology is limited in that each simulated thread of execution has its own dedicated TLB, whereas modern processors share a single TLB among multiple threads through simultaneous multithreading (SMT). Existing model-based research is thus unable to explore virtual memory designs in SMT context. We address this problem by developing a simulator that realistically combines memory reference streams of multiple SMT threads into one TLB. Our simulator is 99% accurate across four Intel processor generations running a wide range of memory-intensive workloads. Our validation efforts lead us to discover a previously undocumented eviction policy in Broadwell TLBs.

Computer architects frequently use cycle-accurate simulations, which incur heavy overheads. Recently, virtual memory studies increasingly employ a lighter-weight methodology that utilizes partial simulations-of only the memory subsystem- whose output is fed into a mathematical linear model that predicts execution runtimes. The latter methodology is much faster, but its accuracy is only assumed, never rigorously validated.We question the assumption and put it to the test by developing Mosalloc, the Mosaic Memory Allocator. Mosalloc backs the virtual memory of applications with arbitrary combinations of 4KB, 2MB, and 1GB pages (each combination forms a "mosaic" of pages). Previous studies used a single page size per execution (either 4KB or 2MB) to generate exactly two execution samples, which defined the aforementioned linear model. In contrast, Mosalloc can generate numerous samples, allowing us to test instead of assume the model's accuracy. We find that prediction errors of existing models can be as high as 25%-192%. We propose a new model that bounds the maximal error below 3%, making it more reliable and useful for exploring new ideas."The phenomena surrounding computers are deep and obscure, requiring much experimentation to assess their nature." (A. Newell and H. A. Simon).

Linux Transparent Huge Pages (THP) are not able to minimize the virtual memory overhead because they are limited to 2MB pages. We introduce Memomania, a flexible memory allocator that is able to transparently back the application with a mixture of 2MB and 1GB pages. We use Memomania to characterize a subset of SPEC CPU2006 benchmarks and find that (1) using 1GB pages provides a notable runtime improvement compared to THP, and that (2) in some cases, allocating more 2MB pages to an application degrades its performance. We suggest that Memomania can be used in (1) placement algorithms, and (2) micro-architectural studies.

Radix page tables as implemented in the x86-64 architecture incur a penalty of four memory references for address translation upon each TLB miss. These 4 references become 24 in virtualized setups, accounting for 5%--90% of the runtime and thus motivating chip vendors to incorporate page walk caches (PWCs). Counterintuitively, an ISCA 2010 paper found that radix page tables with PWCs are superior to hashed page tables, yielding up to 5x fewer DRAM accesses per page walk. We challenge this finding and show that it is the result of comparing against a suboptimal hashed implementation---that of the Itanium architecture. We show that, when carefully optimized, hashed page tables in fact outperform existing PWC-aided x86-64 hardware, shortening benchmark runtimes by 1%--27% and 6%--32% in bare-metal and virtualized setups, without resorting to PWCs. We further show that hashed page tables are inherently more scalable than radix designs and are better suited to accommodate the ever increasing memory size; their downside is that they make it more challenging to support such features as superpages.