Desempeño computacional del algoritmo de decodificación Hoffman en un gpu

Abstract

Esta investigación está motivada por la creciente necesidad de procesar grandes volúmenes de información y por las oportunidades que actualmente están ofreciendo las GPUs (Graphics Processing Unit) para realizar dicho procesamiento. Esta arquitectura computacional de altas prestaciones, ofrece la posibilidad de aplicar técnicas de coprocesamiento entre CPU y GPU para distribuir la carga computacional entre la capacidad de cómputo predominantemente secuencial de la CPU y la capacidad paralela de la GPU. El algoritmo de codificación-decodificación Huffman es uno de los algoritmos más utilizados para reducir la redundancia de información presente en grandes volúmenes de datos [1], con esto, se busca reducir los tiempos de transmisión y procesamiento de la información, sin embargo, es un algoritmo estrictamente secuencial debido a la longitud variable de los símbolos de codificación que genera. El algoritmo de Huffman concatena los símbolos prefijos de codificación sin identificador y para poder implementar la decodificación mediante técnicas de co-procesamiento CPU-GPU se requiere diseñar e implementar una estrategia que permita paralelar el algoritmo de decodificación. La investigación permitió implementar el algoritmo de codificación-decodificación Huffman en una CPU y el algoritmo de decodificación Huffman en una GPU. Como fruto del trabajo investigativo, se presentan técnicas de programación que permiten procesar bits en lenguaje C para el proceso de codificación y técnicas que permiten paralelar el algoritmo de decodificación. De este modo, se puede utilizar el diccionario de símbolos prefijos de longitud variable y además, disminuir el tiempo de procesamiento del algoritmo de decodificación. La implementación que llevamos a cabo, muestra una reducción en el tiempo de procesamiento del algoritmo de decodificación en la GPU. Los resultados experimentales del trabajo realizado muestran que la estrategia paralela propuesta es hasta 16.72x más rápida que el algoritmo de decodificación ejecutado en una CPU.