Runtime-assisted coherent caching

Abstract

In the middle of the 2000s a fundamental change of course occurred in computer architecture because techniques such as frequency scaling and instruction level parallelism were providing rapidly diminishing returns. Since then, scaling up threadlevel parallelism through increasingly parallel multicore processors has become the primary driver of performance gains, exacerbating the pre-existing problem of the Memory Wall. In response to this, cache and memory architecture have become more complex, while still maintaining a shared view of memory to software. As trends such as increasing parallelism and heterogeneity continue apace, the contribution of the memory hierarchy as a proportion of the overall system performance profile will continue to grow. Since the middle of the 2000s, thread-level parallelism has increased across almost all computer processor designs, bringing the problem of programmability into sharper focus. One of the most promising developments in programming models in the past fifteen years has been task-based programming models. Such programming models provide ease programmability for the user, at a level which is abstract enough to allow the runtime system layer to expertly optimise execution for the underlying hardware. The main goal of this thesis is to exploit information available in task-based programming models to drive optimisations in the memory hierarchy, through a hardware/software co-design approach. Data movement becomes the primary factor affecting power and performance as shared memory system architectures scale up in core count and therefore network diameter. The first contribution of this thesis studies the ability of a task-based programming model to constrain data movement in a real, very large shared memory system. It characterises directly and in detail the effectiveness of the programming model’s runtime system at minimising data traffic in the hardware. The analysis demonstrates that the runtime system can maximise locality between tasks and the data they use, thus minimising the traffic in the cache coherent interconnect. The second and third contributions of this thesis investigate hardware/software co-design proposals to increase efficiency within the on-chip memory hierarchy. These two contributions exploit information already captured in existing taskbased programming models. They communicate this information from the runtime system to the hardware and use it there to drive power, performance and area improvements in the memory hierarchy. A simulator based approach is used to model and analyse both the second and third contributions. Scaling cache coherence among growing numbers of private caches is a crucial issue in computer architecture as core counts continue to increase. Improving the scalability of cache coherence is the topic of the second contribution. It demonstrates the ability of a runtime system and hardware co-design approach to dramatically reduce capacity demand on the coherence directory, which is a central issue in scaling cache coherence among private caches. Non-uniform cache access (NUCA) shared caches are also increasing in size and share of on-chip resources, as they are the last line of defence against costly off-chip memory accesses. The third proposal focuses on optimising such NUCA caches to increase their effectiveness at dealing with the bottleneck between computation and memory. It shows a runtime system and hardware co-design approach can successfully reduce the network distance costs in a shared NUCA cache. Together the three contributions of this thesis demonstrate the potential for task-based programming models to address key elements of scalability in the memory hierarchy of future systems at the level of private caches, shared caches and main memory.

A mediados de los 2000 se produjo un cambio fundamental en el campo de la arquitectura de computadores debido a que técnicas como el escalado de frecuencia y el paralelismo a nivel de instrucción dejaron de proveer mejoras significativas. Desde entonces, la mejora en rendimiento se ha basado en explotar el paralelismo a través de incrementar el número de núcleos en los procesadores, lo que ha exacerbado el problema ya existente del muro de moria. En respuesta a este problema, se han desarrollado jerarquías de caché y de memoria más complejas, aún manteniendo el paradigma de memoria compartida desde el punto de vista del software. Como consecuencia de la tendencia de incrementar el paralelismo y la heterogeneidad, la importancia de la jerarquía de la memoria en el rendimiento global del sistema no ha parado de crecer. Otra consecuencia del aumento en el número de núcleos desde mediados de los 2000 es el deterioro de la programabilidad. Unos de los avances más importantes en el área de los modelos de programación han sido los modelos de programación paralelos basados en tareas. Estos modelos de programación facilitan la programación para el usuario y ofrecen un nivel de abstracción suficiente para que sus librerías de gestión optimicen la ejecución paralela para el hardware sobre el que se ejecutan las aplicaciones. El objetivo de esta tesis es aprovechar la información disponible en las librerías de gestión de modelos de programación paralelos basados en tareas para optimizar las jerarquías de memoria en un enfoque de co-diseño de hardware y software. La primera contribución de esta tesis estudia la habilidad de las librerías de gestión de modelos de programación paralelos basados en tareas para restringir las transferencias de datos en un sistema real de memoria compartida de gran escala. Esta contribución caracteriza directamente y en detalle la capacidad de las librerías de gestión de minimizar el tráfico de datos en el hardware. El análisis demuestra que las librerías de gestión pueden maximizar la localidad entre las tareas y los datos que utilizan, minimizando el tráfico de coherencia de cachés en la red de interconexión. La segunda y la tercera contribución de esta tesis proponen co-diseños de hardware y software para mejorar la eficiencia de las jerarquías de cachés. Estas dos contribuciones aprovechan la información disponible en las librerías de gestión de modelos de programación paralelos basados en tareas, comunican la información de las librerías al hardware y éste utiliza la información para mejorar el consumo energético y el rendimiento en la jerarquía de cachés. La segunda contribución trata de mejorar la escalabilidad de los protocolos de coherencia de cachés. El escalado de los protocolos de coherencia es un problema fundamental en arquitecturas con elevado número de núcleos. Esta contribución demuestra los beneficios de co-diseñar las librerías de gestión y el hardware, que consigue reducir drásticamente la presión sobre el directorio del protocolo de coherencia de caches, que es uno de los mayores problemas para escalar los protocolos de coherencia. La tercera contribución de esta tesis propone optimizar las cachés compartidas con tiempo de acceso no uniforme (NUCA) y aumentar su eficiencia para lidiar con el problema del muro de memoria. Las cachés NUCA también son cada vez más grandes y tienen más importancia, ya que son las última línea de defensa ante los costosos accesos a memoria. Esta contribución muestra que un co-diseño de las librerías de gestión y las cachés NUCA puede mejorar la gestión de estas memorias y reducir los costes de las transferencias de memoria en la red de interconexión. Las tres contribuciones de esta tesis demuestran el potencial que poseen las librerías de gestión de los modelos de programación basados en tareas para optimizar aspectos claves de las jerarquías de memoria y mejorar la escalabilidad