Tecnicas de optimizacion de localidad en sistemas computacionales

Resumen

RESUMEN: En esta tesis se ha realizado el estudio y mejora de las técnicas de optimización de localidad cache que aplican los compiladores, junto con el desarrollo de nuevos métodos de optimización que pueden ser utilizados por los compiladores tanto para sistemas de propósito general como para sistemas empotrados o de propósito específico. En concreto: Se ha definido un nuevo esquema de trabajo para el desarrollo de técnicas de optimización de localidad de la jerarquía cache a partir del análisis del LMAD (Descriptor de acceso lineal a memoria). En base al esquema anterior se presenta un nuevo algoritmo para realizar permutación de bucles, realizando una comparación exhaustiva con los principales algoritmos existentes para realizar esta técnica. Se ha creado un nuevo algoritmo para realizar padding, que permite determinar de forma sencilla y directa las dimensiones óptimas de estructuras de datos para maximizar la ocupación de la cache. Junto con un nuevo algoritmo, basado en padding que permite que la re-dimensión de la estructura de datos sea óptima para todos los niveles de la jerarquía cache. También basándose en el redimensionado de estructuras de datos, se presenta una técnica que define el tamaño óptimo de los arrays para que la ocupación de la cache sea máxima en las referencias a dichos arrays en todos los bucles del programa. Y se indica el método para realizar la ocupación "ordenada" de la cache mediante dicho redimensionado. Se implementa un nuevo método de tiling que calcula los tamaños de los tiles para optimizar la utilización de todos los niveles de la jerarquía cache. Y finalmente, se desarrolla una técnica para conocer, en tiempo de compilación, la información contenida en la cache cuando finalice la ejecución de un bucle.