Optimización de la transformada Waveletexplotación de paralelismo de grano fino

Resumen

Esta tesis aborda la explotación eficiente de paralelismo de datos en la transformada wavelet discreta en dos dimensiones (2D-DWT). Concretamente se centra en el uso de extensiones multimedia para la vectorización de sus dos algoritmos principales, el piramidal de Mallat y el esquema Lifting de Sweldens, y en la explotación del paralelismo de datos mediante procesamiento de flujos en unidades gráficas programables (GPUs). Inicialmente se realiza un minucioso análisis del comportamiento de la memoria para reducir la presión de los procesados verticales sobre la jerarquía de memoria delos procesadores superscalares de la familia Intel. Esto permite desarrollar algunas estrategias novedosas para la optimización dela localidad de los dos algorimtos, que además resultan indispensable para la explotación eficiente del paralelismo SIMD mediante extensiones multimedia. Las estrategias de sectorización propuestas utilizan una técnica de transposición local para habilitar la explotación del paralelismo SIMD en los dos procesados, horizontal y vertical. Además, se desarrolla una nueva técnica de complicación, basada en el compilador de SLP, que permite automatizar este proceso. El rendimiento alcanzado supera significativamente al proporcionado por los copiladores de Intel. Finalmente, se proponen modelos de procesamiento de flujos para la 2D-DWT, que permite la explotación de paralelismo de datos en unidades gráficas programables. Se realiza un minucioso estudio sobre su rendimiento y los parámetros de los modelos, llegando a la conclusión de que el algoritmo piramidal de Mallat es más eficiente que el esquema Lifting en este tipo de plataformas, que son además más eficientes para este tipo del algoritmo que los procesadores superescalares. Los resultados parecen además indicar que estas diferencias de rendimiento tienden a acentuarse con el desarrollo de la tecnología de Hardware Gráfico.