Aplicando cadenas def-use de estructuras de datos dinamicas para la optimizacion de programas

Resumen

Abordar el problema de la optimización de códigos irregulares tiene una importancia clave, respaldada por la estimación de que más del 50% de los ciclos de reloj en supercomputadores, son consumidos por este tipo de códigos. Estos programas se caracterizan por el uso de estructuras de datos dinámicas. La tecnología de compilación actual es poco efectiva a la hora de optimizar estas aplicaciones. Fundamentalmente, porque los compiladores no son capaces de extraer Información sobre los distintos alias a las posiciones del heap, que introducen los punteros. En esta tesis se aborda el desarrollo de una técnica de extracción de cadenas de definición y uso, para sentencias con punteros. Esta técnica, que se ha Implementado como un algoritmo de compilación, permite identificar de manera precisa el punto del programa en el que se define una posición del heap, con los puntos del programa en los que se usa esa posición concreta. Esta información la hemos utilizado para desarrollar dos algoritmos de compilación adicionales: un algoritmo de poda y un test de dependencias. La novedad del algoritmo de poda es que se ha particularizado para acelerar una herramienta de análisis de forma, desarrollada por el grupo de investigación en una tesis previa. Dicho análisis de forma se basa en la ejecución simbólica de las sentencias del código y se encarga de calcular el estado del heap en cada punto del programa, información de estado que se representa en forma de grafo. El problema de este análisis de forma es que puede presentar una complejidad exponencial con el número de sentencias a analizar. Para reducir dicha complejidad, conviene reducir el número de sentencias. En concreto, sólo nos interesan aquellas sentencias que crean o modifican las estructuras de datos, y no las sentencias que las recorren o las que definen alias entre punteros. Esta es la función del algoritmo de poda implementado en esta tesis. El código podado, con menos sentencias que el código original, es el que se utiliza como entrada para la herramienta de análisis de forma. Tras la realización de una batería de experimentos con benchmarks del conjunto Olden, se ha comprobado que el algoritmo de poda puede reducir entre un 37% y un 77% el número de sentencias de los programas, consiguiéndose aceleraciones en los tiempos de la herramienta de análisis de forma de entre un 65% y un 96%. Hemos de remarcar que la información de forma que se consiguen en los códigos podados es equivalente a la que se obtiene en los códigos originales sin podar. Por otro lado, en trabajos previos del grupo de investigación, se desarrolló un test de dependencias empotrado en la herramienta de análisis de forma, que se encargaba de anotar sobre los nodos de los grafos que representan el heap, los accesos de lectura y escritura. Esta antiguo test demostró tener una complejidad exponencial. El nuevo test de dependencias que presentamos en esta tesis, representa una importante novedad respecto a otros trabajos relacionados: permite el análisis de regiones de código que crean o modifican estructuras dinámicas de datos, y lo hace con una complejidad polinómica. Este nuevo test, se basa en un novedoso análisis de conflictos que funciona de la siguiente manera: una vez seleccionada la región de código sobre la que se quiere aplicar el análisis de dependencias, se utilizan las cadenas de definición y uso de nuestro primer algoritmo de compilación para computar los paths o expresiones simbólicas de los recorridos de las sentencias de la región. Utilizando además los grafos de forma que llegan a la entrada de esa región de código, tiene lugar una operación de proyección de los paths sobre los grafos, operación que se encarga de anotar los sitios visitados en los grafos por dichos paths. Una vez construidos todos los recorridos posibles para cada sentencia, se chequea si entre dos sentencias puede haber idénticos recorridos, en cuyo caso se detecta un conflicto o dependencia. Los resultados experimentales nos han confirmado que, para los códigos del conjunto Olden, los tiempos de este análisis de conflictos es de pocos milisegundos, mejorando espectacularmente los tiempos que se obtenían en el anterior test de dependencias.