Improving the performance and energy-efficiency of virtual memory (2016)

Virtual memory improves programmer productivity, enhances process security, and increases memory utilization. However, virtual memory requires an address translation from the virtual to the physical address space on every memory operation. Page-based implementations of virtual memory divide physical memory into fixed size pages, and use a per-process page table to map virtual pages to physical pages. The hardware key component for accelerating address translation is the Translation Lookaside Buffer (TLB), that holds recently used mappings from the virtual to the physical address space. However, address translation still incurs high (i) performance overheads due to costly page table walks after TLB misses, and (ii) energy overheads due to frequent TLB lookups on every memory operation. This thesis quantifies these overheads and proposes techniques to mitigate them. In this thesis we argue that fixed size page-based approaches for address translation exhibit limited potential for improving TLB performance because they increase the TLB reach by a fixed amount. To overcome the limitations of such approaches, we introduce the concept of range translations and we show how they can significantly improve the performance and energy-efficiency of address translation. We first comprehensively quantify the address translation performance overhead on a collection of emerging scale-out applications. We show that address translation accounts for up to 16% of the total execution time. We find that huge pages may improve the application performance by reducing the time spent in page walks, enabling better exploitation of the available execution resources. However, the limited hardware support for huge pages in combination with the workloads' low memory locality leave ample space for performance optimizations. To reduce the performance overheads of address translation, we propose Redundant Memory Mappings (RMM). RMM provides an efficient alternative representation of many virtual-to-physical mappings. We define a range translation be a subset of a process's pages that are virtually and physically contiguous. RMM translates each range translation with a single range table entry, enabling a modest number of entries to translate most of the process's address space. RMM operates in parallel with standard paging and introduces a software range table and a hardware range TLB with arbitrarily large reach that is accessed in parallel with the regular L2-page TLB. We modify the operating system to automatically detect ranges and to increase their likelihood with eager paging. RMM is thus transparent to applications. We prototype RMM software in Linux and emulate the hardware. RMM reduces the overhead of virtual memory to less than 1% on average on a wide range of workloads. To reduce the energy cost of address translation, we propose the Lite mechanism and the TLB-Lite and RMM-Lite designs. Lite monitors the performance and utility of L1 TLBs, and adaptively changes their sizes with way-disabling. The resulting TLB-Lite design targets commodity processors with TLB support for huge pages and opportunistically reduces the dynamic energy spent in address translation with minimal impact on TLB miss cycles. To further provide more energy-efficient address translation, we propose RMM-Lite that adds to RMM an L1-range TLB, that is accessed in parallel with the regular L1-page TLB, and the Lite mechanism. The high hit ratio of the L1-range TLB allows Lite to downsize the L1-page TLBs more aggressively. RMM-Lite reduces the dynamic energy spent in address translation by 71% on average. Above the near-zero L2 TLB misses from RMM, RMM-Lite further reduces the overhead from L1 TLB misses by 99\%. The proposed designs target current and future high-performance and energy-efficient memory systems to meet the ever increasing memory demands of applications. La memoria virtual aumenta la productividad del programador, provee seguridad a los procesos e incrementa la utilización de la memoria. No obstante, la memoria virtual requiere de una traducción de direcciones entre los espacios de direcciones virtual y físico en cada operación de memoria. La implementación de la memoria virtual paginada divide la memoria física en páginas de tamaño fijo. El principal componente para acelerar la traducción de direcciones es la TLB (Translation Lookaside Buffer). Sin embargo, la traducción de direcciones tiene un alto coste en el rendimiento, por la necesidad de buscar en la tabla de páginas después de un fallo de TLB, y por el coste energético por las frecuentes búsquedas en la TLB (una por cada operación de memoria). En esta tesis defendemos que los mecanismos de traducción basados en páginas tienen un potencial limitado para aumentar el rendimiento de la TLB. Principalmente porque solo se puede aumentar en una cantidad limitada el conjunto de direcciones que la TLB puede traducir. Para superar esta limitaciones, introducimos el concepto de traducciones por rangos y mostramos como este mecanismo puede mejorar significativamente el rendimiento y la eficiencia energética en la traducción de direcciones. Primero, cuantificamos la pérdida de rendimiento debido a la traducción en aplicaciones emergentes que escalan bien al agregar más procesadores. Mostramos que en estas aplicaciones la traducción de direcciones es responsable de hasta el 16% del tiempo de ejecución. Además, también mostramos que las páginas grandes pueden mejorar el rendimiento de las aplicaciones, permitiendo un mejor uso de los recursos disponibles. Sin embargo, el limitado soporte del hardware para páginas grandes, combinado con cargas de trabajo con poca localidad, nos deja mucho espacio para la optimización. Para reducir los costes de rendimiento de la traducción de direcciones, proponemos RMM (Redundant Memory Mappings). RMM esta basado en rangos de páginas y ofrece una vía alternativa eficiente para representar muchas traducciones. Definimos un rango de traducción como un subconjunto de páginas contiguas de un proceso, tanto en el espacio virtual como en el físico. RMM traduce con un pequeño número de rangos la mayor parte del espacio de direcciones del proceso, y opera en paralelo con el sistema estándar de paginación, agregando una tabla de rangos implementada en software y una TLB de rangos de dimensión arbitraria, accedida en paralelo por la TLB de segundo nivel. Modificamos el sistema operativo para que automáticamente detecte los rangos y aumente su probabilidad de uso. RMM es un mecanismo transparente a las aplicaciones y reduce la pérdida de rendimiento de la memoria virtual hasta algo menos del 1% de media. Para reducir los costes energéticos en la traducción de direcciones, diseñamos el mecanismo Lite, e introducimos los diseños TLBLite y RMMLite. Lite monitora el rendimiento y la utilización de la TLB de primer nivel y adapta su tamaño apagando vías. TLBLite esta orientado a los procesadores actuales que soportan páginas grandes. TLBLite reduce el consumo de energía dinámica usado en la traducción de direcciones, con un impacto mínimo de ciclos en los fallos de TLB. Para hacer aún más eficiente energéticamente la traducción de direcciones proponemos RRMLite, el cual agrega a RMM una TLB de rango paralela a la TLB de primer nivel que tiene el mecanismo Lite. El alto ratio de aciertos en la RMM de primer nivel nos permite deshabilitar vías de la TLB de primer nivel de forma agresiva. RMMLite reduce la energía dinámica total utilizada para la traducción de direcciones en un promedio del 71%. Las técnicas propuestas están diseñadas para soportar sistemas de memoria de alto rendimiento, además de ser eficientes energéticamente, y por lo tanto podrán ser usadas tanto por las aplicaciones actuales como para las futuras que incrementarán su requerimiento a memoria.