Advanced hardware prefetching in virtual memory systems

Abstract

(English) Despite groundbreaking technological innovations, the disparity between processor and memory speeds (known as Memory Wall) is still a major performance obstacle for modern systems. Hardware prefetching is a latency-tolerance technique that has proven successful at shrinking this bottleneck. Nearly all real-world µarchitectural designs employ various prefetchers. Consequently, hardware prefetching attracts a lot of research attention. Virtual memory has been vital for the success of computing due to its programmability and security benefits. However, virtual memory does not come for free since each memory access requires a translation from the virtual to the physical address space that incurs high latency and energy overheads. To alleviate these overheads, a hardware cache, named Translation Lookaside Buffer(TLB), is typically employed to store the most recently used translations. However, TLBs are limited in capacity, thus there are not adequate for assuring high performance. Processor vendors address the need for fast address translation by providing dedicated support for virtual memory (e.g., multi-level TLBs, multiple page sizes). Despite the existence of such support, the advent of applications with large data and code footprints aggravates the pressure placed on the virtual memory subsystem, resulting in frequent page walks that deteriorate system's performance. This dissertation argues that hardware prefetching can attenuate the Memory Wall bottleneck in virtual memory systems. To support our claim, we design and propose fully-legacy preserving TLB prefetching schemes and exploit address translation metadata that are available at the µarchitecture to improve the effectiveness of the prefetchers operating in the physical address space. To reduce the overheads of frequent TLB misses due to data accesses, we propose a solution that consists of the Sampling-Based Free TLB Prefetching (SBFP) scheme and the Agile TLB Prefetcher(ATP). SBFP exploits the locality in the last-level of the page table to enhance the performance of TLB prefetching. ATP combines three prefetch engines while disabling TLB prefetching during phases that does not provide benefits. Across different benchmark suites, we show that ATP combined with SBFP improves performance over the best performing prior TLB prefetcher while reducing the page walk references to the memory hierarchy. Next, we argue that instruction address translation is an emerging bottleneck in servers. To support our claim, we characterize the TLB behavior of server workloads and provide evidence that instruction address translation is a bottleneck in servers. To attenuate this bottleneck, we propose Morrigan, the first instruction TLB prefetcher. Morrigan combines a sequential prefetcher with an ensemble of hardware Markov prefetchers that build variable length Markov chains out of the instruction TLB miss stream while using a new frequency-based replacement policy. Across a set of industrial server workloads, Morrigan provides great performance gains while eliminating the majority of the demand page walks for instruction accesses. Our last contribution improves the efficacy of cache prefetchers operating in the physical address space by exploiting modern support for large pages. We propose the Page-size Propagation Module(PPM), a µarchitectural scheme that transmits the page size information to the lower-level cache prefetchers and enables safe prefetching beyond 4KB physical page boundaries. We further design a module comprised of two prefetchers that both exploit PPM but drive prefetching decisions assuming different page sizes. Our experiments reveal that the proposed page size exploitation techniques provide great performance enhancements on various state-of-the-art cache prefetchers. ¿he proposals of this dissertation are fully legacy-preserving, do not call for disruptive changes, do not require any OS involvement, and constitute practical solutions to real-world bottlenecks.

(Español) La diferencia de velocidad entre los procesadores y las memorias (conocido como Memory Wall) es uno de los mayores cuellos de botella en los sistemas actuales. Los prefetchers hardware son una técnica para tolerar la latencia de memoria que ha demostrado ser efectiva para aliviar este cuello de botella. Prácticamente todas las microarquitecturas actuales incluyen varios prefetchers. La memoria virtual ha sido vital para el éxito de los sistemas de computación debido a los beneficios que ofrece en términos de programabilidad y seguridad. Sin embargo, la memoria virtual tiene un coste alto en latencia y en energía, ya que cada acceso a memoria requiere una traducción del espacio de direcciones físico al virtual. Para aliviar estos costes, una caché hardware llamada Translation Lookahead Buffer (TLB) guarda las traducciones más recientes. Uno de los problemas de las TLBs es que tienen una capacidad limitada, lo que hace que no puedan garantizar un alto rendimiento. Los procesadores comerciales se aseguran de que la traducción de direcciones sea rápida al incluir soporte hardware dedicado a la memoria virtual (como TLBs multinivel o varios tamaños de página). Incluso con este soporte hardware, la creciente popularidad de aplicaciones con grandes cantidades de datos e instrucciones ha aumentado la presión sobre el subsistema de memoria virtual, resultando en accesos frecuentes a la tabla de páginas que deterioran el rendimiento del sistema. Esta tesis pretende atenuar el cuello de botella del Memory Wall utilizando hardware prefetchers en sistemas de memoria virtual. Para reducir las penalizaciones de los fallos frecuentes de TLB para accesos de datos, proponemos una solución llamada Sampling Based Free TLB Prefetching (SBFP) combinada con un Agile TLB Prefetcher (ATP). SBFP se beneficia de la localidad en el último nivel de la tabla de páginas para mejorar el prefetching en TLBs. ATP combina tres motores de prefetching y deshabilita el prefetching de TLB en fases donde no aporta ningún beneficio. Para varios juegos de prueba, demostramos que la combinación de ATP con SBFP mejora el rendimiento respecto al mejor prefetcher de TLB propuesto anteriormente, a la vez que reduce la cantidad de accesos a la tabla de páginas. También identificamos que la traducción de direcciones en instrucciones es un cuello de botella emergente en servidores, y lo demostramos caracterizando el comportamiento de las TLBs en estos sistemas. Para aliviar este cuello de botella proponemos Morrigan, el primer prefetcher de instrucciones para TLBs. Morrigan combina un prefetcher secuencial con un conjunto de Markov prefetchers que construyen cadenas de Markov de diferente longitud de la secuencia de fallos de instrucciones en la TLB, y también utiliza una nueva política de reemplazo basada en la frecuencia. En tareas de servidores industriales, Morrigan consigue amplios beneficios en rendimiento y elimina la mayoría de accesos a la tabla de páginas para accesos a instrucciones. La última contribución mejora la eficacia de los prefetchers de cachés que operan en el espacio de direcciones físico utilizando el soporte hardware para páginas grandes. Para ello proponemos el Page-size Propagation Module (PPM), una técnica microarchitectural que transmite el tamaño de página a los prefetchers de las cachés de último nivel para poder hacer prefetching de forma segura sobrepasando los límites de las páginas físicas de 4KB. También diseñamos otro módulo que consiste en dos prefetchers conectados al PPM y que controla las decisiones de los prefetchers asumiendo diferentes tamaños de páginas. Nuestros experimentos muestran que las técnicas propuestas para sacar beneficio del tamaño de las páginas en varios prefetchers de cachés de último nivel propuestas en el estado del arte consiguen grandes mejoras de rendimiento.