Planificación de tareas considerando la contención en la jerarquía de memoria de procesadores multinúcleo

Abstract

[ES] Con el objetivo de mejorar el rendimiento de los CMPs, parte de la investigación reciente se ha centrado en la planificación de procesos para limitar la contención provocada por el limitado ancho de banda. Hoy en dia, los CMPs comerciales implementan jerarquías de cache multinivel, donde las caches del último nivel son compartidas por al menos dos caches del nivel inferior. A su vez, estas caches pueden ser compartidas por varios núcleos multihilo. Con este diseño, los puntos de contención pueden aparecer a lo largo de toda la jerarquía de memoria del procesador. Además, el rendimiento de las cargas varía ampliamente en función de rendimiento de las aplicaciones en la LLC. Se espera que estos problemas se agraven en futuros procesadores, pues el número de núcleos, hilos de ejecución, y por tanto, grado de compartición de las caches se incrementa en cada generación. En este trabajo presentamos un conjunto de tests para determinar de manera experimental las características de la LLC, es decir, la geometría de la cache (número de conjuntos, número de vías y tamaño de la línea) y su arquitectura (privada o compartida) utilizando huge pages y contadores de prestaciones. Después, se caracteriza el impacto en el rendimiento de la contención en los diferentes puntos de contención que aparecen en el subsistema de memoria. Finalmente, proponemos una política de planificación genérica para CMPs que considera el ancho de banda disponible en cada nivel de la jerarquía de cache y la degradación del IPC que cada benchmark sufre debida a la contención en memoria principal. El algoritmo propuesto selecciona los procesos para ser ejecutados concurrentemente y los ubica en los núcleos para minimizar los efectos de la contención. La propuesta se ha implementado y evaluado en un procesador comercial con cuatro núcleos y sin capacidades multi-hilo, que implementa una jerarquía de cache relativamente pequeña con dos niveles de cache. A pesar de ello, la propuesta ofrece un incremento de prestaciones medio superior al 6.5% al compararla con la planificación de Linux, mientras que este incremento está por debajo del 3.3% para un planificador del estado del arte que considera la contención en el acceso a memoria. Es más, en algunas cargas la propuesta triplica la aceleración ofrecida por el planificador citado.

[EN] In order to improve CMP performance, recent research has focused on scheduling to mitigate contention produced by the limited memory bandwidth. Nowadays, commercial CMPs implement multi-level cache hierarchies where last level caches are shared by at least two cache structures located at the immediately lower cache level. In turn, these caches can be shared by several multithreaded cores. In this microprocessor design, contention points may appear along the whole memory hierarchy. Besides, in these architectures the performance of multiprogrammed workloads widely varies depending on the performance of the LLC. Moreover, these problems are expected to aggravate in future technologies, since the number of cores and hardware threads, and consequently the size of the shared caches increases with each microprocessor generation. In this work we present a set of tests to experimentally determine the LLC features, that is, the cache geometry (number of sets, number of ways, and line size) and cache architecture type (private or shared) using huge pages and performance counters. Then we characterize the impact on performance of the different contention points that appear along the memory subsystem. Finally, we propose a generic scheduling strategy for CMPs that takes into account the available bandwidth at each level of the cache hierarchy and the IPC degradation each benchmark suffers due to main memory contention. The proposed strategy selects the processes to be co-scheduled and allocates them to cores in order to minimize contention effects.

The proposal has been implemented and evaluated in a commercial single-threaded quad-core processor with a relatively small two-level cache hierarchy. Despite this small cache hierarchy presents less contention than more recent processor designs, the proposal reaches, on average, a performance improvement above 6.5% when compared with the Linux scheduler while this figure is below 3.2% for an state-of-theart memory-aware scheduler. Moreover, in some mixes the proposal triples the speedup achieved by the latter scheduler.