Smart memory management through locality analysis
Sánchez Navarro, Francisco Jesús · TDX (Tesis Doctorals en Xarxa) · 2001
Las memorias cache fueron incorporadas en los microprocesadores ya desde los primeros tiempos, y representan la solucion mas comun para tratar la diferencia de velocidad entre el procesador y la memoria. Sin embargo, muchos estudios senalan que la capacidad de almacenamiento de la cache es malgastada muchas veces, lo cual tiene un impacto directo en el rendimiento del procesador. Aunque una cache esta disenada para explotar diferentes tipos de localidad, todas la referencias a memoria son tratadas de la misma forma, ignorando comportamientos particulares de localidad. El uso restringido de la informacion de localidad para cada acceso a memoria puede limitar la eficiencia de la cache. En esta tesis se demuestra como un analisis de localidad de datos puede ayudar al investigador a entender donde y porque ocurren los fallos de cache, y proponer entonces diferentes tecnicas que hacen uso de esta informacion con el objetivo de mejorar el rendimiento de la memoria cache. Proponemos tecnicas en las cuales la informacion de localidad obtenida por el analizador de localidad es pasada desde el compilador al hardware a traves del ISA para guiar el manejo de los accesos a memoria. Hemos desarrollado un analisis estatico de localidad de datos. Este analisis esta basado en los vectores de reuso y contiene los tres tipicos pasos: reuso, volumen y analisis de interferencias. Comparado con trabajos previos, tanto el analisis de volumenes como el de interferencias ha sido mejorado utilizando informacion de profiling asi como un analisis de interferencias mas preciso. El analizador de localidad de datos propuesto ha sido incluido como un paso mas en un compilador de investigacion. Los resultados demuestran que, para aplicaciones numericas, el analisis es muy preciso y el overhead de calculo es bajo. Este analisis es la base para todas las otras partes de la tesis. Ademas, para algunas propuestas en la ultima parte de la tesis, hemos usado un analisis de localidad de datos basado en las ecuaciones de fallos de cache. Este analisis, aunque requiere mas tiempo de calculo, es mas preciso y mas apropiado para caches asociativas por conjuntos. El uso de dos analisis de localidad diferentes tambien demuestra que las propuestas arquitectonicas de esta tesis son independientes del analisis de localidad particular utilizado. Despues de mostrar la precision del analisis, lo hemos utilizado para estudiar el comportamiento de localidad exhibido por los programas SPECfp95. Este tipo de analisis es necesario antes de proponer alguna nueva tecnica ya que ayuda al investigador a entender porque ocurren los fallos de cache. Se muestra que con el analisis propuesto se puede estudiar de forma muy precisa la localidad de un programa y detectar donde estan los puntos negros asi como la razon de estos fallos en cache. Este estudio del comportamiento de localidad de diferentes programas es la base y motivacion para las diferentes tecnicas propuestas en esta tesis para mejorar el rendimiento de la memoria. Asi, usando el analisis de localidad de datos y basandonos en los resultados obtenidos despues de analizar el comportamiento de localidad de un conjunto de programas, proponemos utilizar este analisis con el objetivo de guiar tres tecnicas diferentes: (i) manejo de caches multimodulo, (ii) prebusqueda software para bucles con planificacion modulo, y (iii) planificacion de instrucciones de arquitecturas VLIW clusterizadas. El primer uso del analisis de localidad propuesto es el manejo de una novedosa organizacion de cache. Esta cache soporta bypass y/o esta compuesta por diferentes modulos, cada uno orientado a explotar un tipo particular de localidad. La mayor diferencia de esta cache con respecto propuestas previas es que la decision de cachear o no, o en que modulo un nuevo bloque es almacenado, esta controlado por algunos bits en las instrucciones de memoria (pistas de localidad). Estas pistas (hints) son fijadas en tiempo de compilacion utilizando el analisis de localidad propuesto. Asi, la complejidad del manejo de esta cache se mantiene bajo ya que no requiere ningun hardware adicional. Los resultados demuestran que caches mas pequenas con un manejo mas inteligente pueden funcionar tan bien (o mejor) que caches convencionales mas grandes. Hemos utilizado tambien el analisis de localidad para estudiar la interaccion entre la segmentacion software y la prebusqueda software. La segmentacion software es una tecnica muy efectiva para la planificacion de codigo en bucles (principalmente en aplicaciones numericas en procesadores VLIW). El esquema mas popular de prebusqueda software se llama planificacion modulo. Muchos trabajos sobre planificacion modulo se pueden encontrar en la literatura, pero casi todos ellos consideran una suposicion critica: consideran un comportamiento optimista de la cache (en otras palabras, usan siempre la latencia de acierto cuando planifican instrucciones de memoria). Asi, los resultados que presentan ignoran los efectos del bloqueo debido a dependencias con instrucciones de memoria. En esta parte de la tesis mostramos que esta suposicion puede llevar a planificaciones cuyo rendimiento es bastante mas bajo cuando se considera una memoria real. Nosotros proponemos un algoritmo para planificar instrucciones de memoria en bucles con planificacion modulo. Hemos estudiado diferentes estrategias de prebusqueda software y finalmente hemos propuesto un algoritmo que realiza prebusqueda basandose en el analisis de localidad y en la forma del grafo de dependencias del bucle. Los resultados obtenidos demuestran que el esquema propuesto mejora el rendimiento de las otras heuristicas ya que obtiene un mejor compromiso entre tiempo de calculo y de bloqueo. Finalmente, el ultimo uso del analisis de localidad estudiado en esta tesis es para guiar un planificador de instrucciones para arquitecturas VLIW clusterizadas. Las arquitecturas clusterizadas estan siendo una tendencia comun en el diseno de procesadores empotrados/DSP. Tipicamente, el nucleo de estos procesadores esta basado en un diseno VLIW el cual particiona tanto el banco de registros como las unidades funcionales. En este trabajo vamos un paso mas alla y tambien hacemos la particion de la memoria cache. En este caso, tanto las comunicaciones entre registros como entre memorias han de ser consideradas. Nosotros proponemos un algoritmo que realiza la particion del grafo asi como la planificacion de instrucciones en un unico paso en lugar de hacerlo secuencialmente, lo cual se demuestra que es mas efectivo. Este algoritmo es mejorado anadiendo una analisis basado en las ecuaciones de fallos de cache con el objetivo de guiar en la planificacion de las instrucciones de memoria para reducir no solo comunicaciones entre registros, sino tambien fallos de cache. --------------------------------------------------------