Técnicas de compilación para la paralelización de códigos irregulares

Abstract

La temática general de esta tesis es el desarrollo de nuevas estrategias que permiten aumentar el rendimiento en la ejecución de códigos irregulares. Hemos particularizado nuestro estudio a sistemas multiprocesadores, donde es necesario hacer un especial hincapié en dos factores que determinan de forma más importante la eficiencia de un programa: la extracción eficiente del paralelismo y la explotación, también eficiente, de la jerarquía de memoria. Debido a la estructura de esta clase de códigos, parte del proceso de análisis debe ser realizado durante la ejecución del programa. Por este motivo, un factor adicional que es necesario considerar lo supone el diseño de nuevas rutinas de análisis que minimicen su coste durante la ejecución del programa. Las principales contribuciones realizadas en esta tesis son el desarrollo de diversas técnicas que permiten caracterizar el conjunto de accesos a memoria realizados por un código irregular, una nueva estrategia de análisis de dependencias con la que podemos determinar la no existencia de conflictos de acceso a memoria entre dos códigos irregulares, un conjunto de técnicas de paralelización y mejora de la localidad, y un esquema de organización de las distintas propuestas en un árbol de decisión, que permite determinar la solución más eficiente en función de las características del problema considerado.