Compressed caching and modern virtual memory simulation

Abstract

CPU speeds have increased so quickly that few program suffer from a lack of CPU capacity. However, many program in all domains of computing are hindered by the slowness of memory at some level of the virtual memory hierarchy. One of the greatest pitfalls in system performance is that of virtual memory paging. Improving the performance of this part of the virtual memory hierarchy is essential. However, the understanding of program reference behavior and its relation to virtual memory design and performance has not been significantly advanced in the past thirty years. Recent ideas that could improve virtual memories have been evaluated through direct implementation as part of an operating system kernel. Unfortunately, this approach does not allow for controlled, reproducible experiments that help a researcher to understand how program use their memory. Trace-driven simulation allows for these kinds of controlled, scientific experiments. However, the difficulties in gathering, storing, and processing large reference traces have kept researchers from adopting this approach. This dissertation begins by outlining an approach to reducing reference traces for use in simulations of virtual memory. We have used reference traces to explore compressed caching—the insertion of a new, compressed level of RAM into the memory hierarchy. We will present the trace-driven investigations into the compression of in-memory data. We will also present a new, principled approach to making page replacement and compressed caching agilely adapt to a program's reference behavior, made possible by controlled simulations.