Optimización de algoritmos científicos en sistemas heterogéneos y aceleradores para computación de altas prestaciones

Resumen

1. Introducción o motivación de la tesis: Actualmente, la computación de propósito general en GPU es uno de los pilares básicos de la computación de alto rendimiento. Desde hace una década y media, se están acelerando cientos de aplicaciones en GPU en los más diversos campos, como el aprendizaje automático, el procesamiento de vídeo e imagen, y la minería de datos. Sin embargo, aún existen algoritmos científicos poco explorados, como los métodos de compresión de datos CAVLC (Context-based Adaptive Variable Length Coding), CABAC (Context-based Adaptive Binary Arithmetic Coding) y VLE (Variable-Length Encoding), y diferentes métodos de procesamiento de vídeo e imagen, como la detección de bordes de Canny no supervisada, el cálculo del descriptor de imágenes RCD (Region Covariance Descriptor), la identificación de texturas a gran escala en tiempo real y el algoritmo de eliminación de ruido de vídeo VBM3D (Video Block-Matching and 3-D Filtering). Por ello, la motivación de esta tesis ha sido investigar la posibilidad de acelerar significativamente en GPU un conjunto de algoritmos científicos pertenecientes a este grupo. 2.Contenido de la investigación: En primer lugar, se ha obtenido una implementación optimizada del algoritmo de compresión de vídeo e imagen CAVLC (Context-Adaptive Variable Length Encoding) [1], que es el método entrópico más utilizado en el estándar de codificación de vídeo H.264. La aceleración respecto a la mejor implementación anterior está entre 2.5x y 5.4x. Esta solución puede aprovecharse como el componente entrópico de codificadores software H.264 basados en GPU, y utilizarse en una amplia variedad de sistemas de compresión basados en GPU para codificar imágenes y vídeos en formatos distintos a H.264, como imágenes médicas. En segundo lugar, se ha desarrollado GUD-Canny [2], un detector de bordes de Canny no supervisado y distribuido. El sistema resuelve las principales limitaciones de las implementaciones del algoritmo de Canny, que son el cuello de botella causado por el proceso de histéresis y el uso de umbrales de histéresis fijos. Dada una imagen, esta se divide en un conjunto de sub-imágenes, y, para cada una de ellas, se calcula de forma no supervisada un par de umbrales de histéresis utilizando el método de Medina-Carnicer [3]. El detector satisface el requisito de tiempo real, al ser 0.35 ms el tiempo promedio en detectar los bordes de una imagen 512x512. En tercer lugar, se ha realizado una implementación optimizada del método de compresión de datos VLE (Variable-Length Encoding) [4], que es 2.6x más rápida en promedio que la mejor implementación anterior. Además, esta solución incluye un nuevo método scan inter-bloque que se puede usar para acelerar la propia operación scan y otros algoritmos, como el de compactación [5]. En el caso de la operación scan, se logra una aceleración de 1.62x si se usa el método propuesto en lugar del utilizado en la mejor implementación anterior de VLE. 3.Conclusión: La realización de esta tesis ha conducido a la optimización en GPU de un conjunto de algoritmos científicos (CAVLC, detector de bordes de Canny y VLE) y a la obtención de un nuevo método scan inter-bloque en GPU eficiente. Los resultados obtenidos sugieren nuevas ideas a explorar. Por un lado, el uso de CAVLCU, GUD-Canny y GVLE en la optimización de codificadores de vídeo e imagen, aplicaciones de vídeo e imagen, y sistemas de compresión de datos, respectivamente. Por otro, la utilización del método scan inter-bloque propuesto en algoritmos que requieran la operación scan. 4. Bibliografía: [1] Fuentes-Alventosa, A., Gómez-Luna, J., González-Linares, J. M., Guil, N., & Medina-Carnicer, R. (2022). CAVLCU: an efficient GPU-based implementation of CAVLC. The Journal of Supercomputing, 78(6), 7556-7590. [2] Fuentes-Alventosa, A., Gómez-Luna, J., & Medina-Carnicer, R. (2022). GUD-Canny: A real-time GPU-based unsupervised and distributed Canny edge detector. Journal of Real-Time Image Processing, 19(3), 591-605. [3] Medina-Carnicer, R., Munoz-Salinas, R., Yeguas-Bolivar, E., & Diaz-Mas, L. (2011). A novel method to look for the hysteresis thresholds for the Canny edge detector. Pattern Recognition, 44(6), 1201-1211. [4] Fuentes-Alventosa, A., Gómez-Luna, J., & Medina-Carnicer, R. (2022). GVLE: a Highly Optimized GPU-Based Implementation of Variable-Length Encoding. The Journal of Supercomputing. [5] Luna, J. G. G., Chang, L. W., Sung, I. J., Hwu, W. M., & Guil, N. (2015, September). In-place data sliding algorithms for many-core architectures. In 2015 44th International Conference on Parallel Processing (pp. 210-219). IEEE.