Improving the SLLC Efficiency by exploiting reuse locality and adjusting prefetch
Jorge Albericio Latorre, Pablo Ibáñez, José María Llabería · Dialnet (Universidad de la Rioja) · 2013
Desde los telefonos moviles inteligentes hasta nuestro ordenador portatil los sistemas electronicos que incluyen chips multiprocesador (CMP) estan presentes en nuestra vida cotidiana de una manera abrumadora. Los CMPs contienen varios nucleos o CPUs que tienen que ser alimentados con datos provenientes de la memoria. Pero la velocidad a la que los nucleos que forman el CMP necesitan los datos es mucho mayor que la velocidad a la que la memoria es capaz de proporcionar dichos datos. De hecho, esta diferencia ha ido aumentando desde practicamente el dia en el que ambos dispositivos fueron concebidos. Esta diferencia en el rendimiento de ambos dispositivos se ha venido a llamar the memory gap. Al mismo tiempo que dicha diferencia aumentaba, los lenguajes de programacion proporcionaban a los programadores modelos de memoria que podian acceder a un espacio practicamente infinito y al que, ademas, se accedia de manera instantanea. Pero el tamano de cualquier estructura hardware esta intimamente relacionado con su tiempo de acceso y este sera mayor cuanto mayor sea el tamano la estructura hardware a acceder. Con el animo de deshacer esta aparente contradiccion, los arquitectos de computadores incluyeron memorias intermedias entre las CPUs y la grande, aunque al mismo tiempo lenta, memoria principal. Estas memorias intermedias se denominan memorias cache o simplemente caches. Debido a la gran diferencia que existe entre la velocidad del procesador y la de la memoria principal. Los CMPs en la actualidad estan provistos de una jerarquia de memorias cache que tiene dos o tres niveles. Las caches que estan cerca del procesador solo contienen unos pocos kilobytes (entre 4 y 64) accesibles en uno o pocos ciclos de reloj, mientras que las que se encuentran mas alejadas del procesador pueden llegar a contener varios megabytes y tener un tiempo de acceso de varias decenas de ciclos. Los programas al ser ejecutados muestran una propiedad llamada localidad que se expresa en los ejes espacial y temporal. La localidad temporal es la propiedad que dice que el programa volvera a usar datos que uso recientemente, cuanto mas recientemente los uso, mas probable es que vuelva a hacerlo. Mientras que la localidad espacial es la propiedad que dice que el programa tendera a usar datos que estan proximos en el espacio de memoria a datos que uso recientemente. Las memorias cache han sido disenadas tradicionalmente para explotar la localidad. En concreto, la localidad temporal se explotaba mediante una adecuada politica de reemplazo, mientras que la localidad espacial se explota al contener cada bloque de cache varios datos o palabras. Un modo adicional de conseguir explotar una mayor cantidad de localidad espacial es mediante el uso de la tecnica llamada prebusqueda. La politica de reemplazo influye de manera critica en la tasa de aciertos de la memoria cache. En un CMP provisto de una jerarquia de memorias cache, la localidad temporal se explota en aquellos niveles mas cercanos a los nucleos. Asi que muchos de los bloques insertados en la SLLC son de un solo uso, es decir, estos bloques no experimentaran ningun acierto mas durante todo el tiempo que permanezcan en la SLLC. Sin embargo, aquellos bloques que lleguen a experimentar un acierto en la SLLC, normalmente experimentaran muchos mas aciertos. Por lo tanto, que la politica de reemplazo base sus decisiones en la posible explotacion de la localidad temporal, es una asuncion invalida cuando hablamos de la SLLC. Por el contrario, Este comportamiento indica que dicha politica de reemplazo de la SLLC deberia estar basada en el reuso1 en lugar de en la localidad temporal. La prebusqueda hardware tiene por objetivo cargar en la cache datos antes de que sea el procesador quien los pida. La validez de esta tecnica a la hora de reducir la latencia media de acceso a memoria ha sido ampliamente demostrada. La prebusqueda funciona especialmente bien en las jerarquias de memoria de sistemas monoprocesador, donde solamente hay un flujo de datos entre el procesador y la memoria. Sin embargo, cuando la prebusqueda se usa en un sistema multiprocesador donde diferentes aplicaciones se estan ejecutando al mismo tiempo, las prebusquedas asociadas a un nucleo podrian interferir con los datos cargados en la cache por otro nucleo, provocando la eliminacion de los contenidos de otra aplicacion y danando su rendimiento. Es necesario por tanto un mecanismo para regular la prebusqueda asociada a cada uno de los nucleos. Este mecanismo deberia tener por objetivo el mejorar el rendimiento general del sistema. 1 Aunque el DRAE no contenga su definicion, usaremos aqui el verbo reusar (asi como sus formas derivadas) como sinonimo de volver a utilizar. Cada fallo en la SLLC provoca un acceso a la memoria principal que se encuentra fuera del chip. Ademas la memoria principal esta hecha de chips de DRAM. Ambos factores incrementan su latencia de acceso, latencia que se suma a cada uno de los accesos que falla en la SLLC, penalizando a la vez la latencia media de acceso a memoria. Por lo tanto, la tasa de aciertos de la SLLC es un factor critico para lograr una latencia media de acceso a memoria optima. Esta tesis fija su atencion en la eficiencia de los dos aspectos comentados con anterioridad: la eficiencia de la prebusqueda y la eficiencia de la politica de reemplazo. Las contribuciones principales de esta tesis son las siguientes: 1) Enunciamos una propiedad llamada localidad de reuso que dice que i) los bloques de cache que hayan sido usados mas de una vez tienen una alta probabilidad de ser usados muchas veces en el futuro. ii) Los bloques de cache recientemente reusados son mas utiles que otros reusados previamente. Defendemos en esta tesis que el patron de acceso a la SLLC muestra localidad de reuso. 2) En esta tesis se proponen dos algoritmos de reemplazo capaces de explotar la localidad de reuso, Least-recently reused (LRR) y Not-recently reused (NRR). Estos dos nuevos algoritmos son modificaciones de otros dos muy bien conocidos: Least-recently used (LRU) y Not-recently used (NRU). Dichos algoritmos fueron disenados para explotar la localidad temporal, mientras que los nuestros explotan la local- idad de reuso. Las modificaciones propuestas no suponen ninguna sobrecarga hardware respecto a los algoritmos base. Durante esta tesis se muestra que nuestros algoritmos mejoran consistentemente el rendimiento de los originales. 3) Proponemos un novedoso diseno para la SLLC llamado Reuse Cache. En este diseno los arrays de etiquetas y datos de la cache estan desacoplados. Solamente se almacenan en el array de datos aquellos bloques que hayan mostrado reuso. El array de etiquetas se usa para detectar reuso y mantener la coherencia. Esta estructura permite reducir el tamano del array de datos de manera drastica. Como ejemplo, una Reuse Cache con un array de etiquetas equivalente al de una cache convencional de 4MB y un array de datos de 1MB, tiene el mismo rendimiento medio que una cache convencional de 8MB, pero con un ahorro de almacenamiento de en torno al 84%. 4) Un controlador de bajo coste llamado ABS capaz de ajustar la agresividad de la prebusqueda asociada a cada uno de los nucleos de un CMP pero con el animo de mejorar el rendimiento general del sistema. El controlador funciona de manera aislada en cada uno de los bancos de la SLLC y recoge metricas locales. Para optimizar el rendimiento global del sistema busca la combinacion optima de valores de la agresividad de prebusqueda. Para inferir cual es esa combinacion optima usa una estrategia de busqueda hill-climbing.