Cycle-accurate simulations, frequently used by computer architects, incur substantial overheads. To mitigate this, recent virtual memory studies have adopted a lighter-weight methodology that leverages partial simulations of only the memory subsystem. This approach feeds simulation outputs into a mathematical linear model to predict execution runtimes. While this methodology accelerates the simulation process, its accuracy has traditionally been assumed rather than rigorously validated.
In this study, we challenge this assumption with the development of Mosalloc, the Mosaic Memory Allocator. Mosalloc supports the virtual memory of applications with a variety of page sizes, specifically 4KiB, 2MiB, and 1GiB, creating diverse \\\"mosaic\\\" memory layouts. Contrary to previous approaches that utilized a singular page size to generate merely two execution samples for model development, Mosalloc is capable of producing a broad spectrum of samples, thereby allowing empirical validation of model accuracy. Our evaluations reveal that existing models exhibit prediction errors ranging from 25% to 192%. In response, we propose Mosmodel, a new runtime model that confines the maximal cross-validation error to below 6%, significantly enhancing reliability for experimental exploration.
The efficacy of these models hinges on the availability of diverse memory layouts. As the number of feasible layouts escalates exponentially with address space size, the selection process becomes increasingly complex. To address this, we introduce Moselect, an algorithm that autonomously identifies optimal memory layouts that ensure up to 4% gaps between consecutive data points, averaging 46 layouts. Moselect not only augments model accuracy with its diverse samples but also simplifies the modeling and simulation processes. This simplification trades a marginal increase in maximal error of up to 2.5% for significant reductions in budget and execution time. Moreover, it facilitates the use of a TLB-only simulator, eliminating the need for comprehensive cache hierarchy simulations and thus minimizing development efforts.
By amalgamating Mosalloc, Moselect, and Mosmodel, we present a comprehensive framework that automates memory layout selection, benchmark execution, and accurate runtime model construction. This framework also introduces techniques to streamline operations without materially compromising accuracy. Collectively, these innovations significantly advance the state-of-the-art in virtual memory research, providing a robust platform for future exploration and development.