¿Alguien conoce un proyecto que implemente métodos de compresión estándar (como Zip, GZip, BZip2, LZMA, ...) utilizando el CUDA library de NVIDIA?Biblioteca de compresión utilizando Nvidia's CUDA
Me preguntaba si los algoritmos que pueden hacer uso de muchas tareas paralelas (como la compresión) no se ejecutarían mucho más rápido en una tarjeta gráfica que con una CPU dual o quadcore.
¿Qué opinas sobre los pros y contras de este enfoque?
No estoy al tanto de que alguien haya hecho eso y lo haya hecho público. Solo en mi humilde opinión, no suena muy prometedor.
Como señala Martinus, algunos algoritmos de compresión son muy seriales. Los algoritmos de compresión de bloques como LZW se pueden paralelizar codificando cada bloque de forma independiente. Ziping un gran árbol de archivos se puede paralelizar en el nivel de archivo.
Sin embargo, ninguno de estos es realmente el paralelismo estilo SIMD (Single Instruction Multiple Data), y no son masivamente paralelos.
Las GPU son básicamente procesadores de vectores, donde puede hacer cientos o miles de instrucciones ADD todo en el paso de bloqueo, y ejecutar programas donde hay muy pocas ramas dependientes de datos.
Los algoritmos de compresión en general suenan más como un modelo de programación SPMD (Single Program Multiple Data) o MIMD (Multiple Instruction Multiple Data), que es más adecuado para coops multinúcleo.
Los algoritmos de compresión de video pueden acelerarse mediante procesamiento GPGPU como CUDA solo en la medida en que haya un gran número de bloques de píxeles que se están transformando o convolucionando coseno (para detección de movimiento) en paralelo, y la IDCT o convolución las subrutinas pueden expresarse con código sin sucursales. A las GPU también les gustan los algoritmos que tienen alta intensidad numérica (la relación entre operaciones matemáticas y acceso a memoria). Los algoritmos con baja intensidad numérica (como agregar dos vectores) pueden ser masivamente paralelos y SIMD, pero aún más lentos la CPU porque están limitados por la memoria.
. Mi primer pensamiento sobre la paralelización fue con el "gran árbol de archivos", pero las otras razones que mencionaste me han convencido, gracias. – Xn0vv3r
¿Puede hacer referencia a medidas que muestran que los algoritmos de memoria (como la suma de dos vectores) se ejecutan más lentamente en la GPU que en la CPU? –
@bene No dije eso correctamente. Los algoritmos de límite de memoria pueden ejecutarse tan rápido o más rápido en un gpu: la mayoría de los gpus tienen un ancho de banda de memoria muy alto. Cualquiera que sea el procesador que tenga este ancho de banda de memoria efectivo más alto ejecutará esos algoritmos más rápido. Sin embargo, si está tomando datos en la CPU, transfiriéndolos a la GPU (generalmente a través de un bus PCIE), luego haciendo la adición, luego transfiriendo los datos a la CPU, que siempre será mucho más lento, y es muy fácil construir un punto de referencia para esto. –
Normalmente, los algoritmos de compresión no pueden hacer uso de tareas paralelas, no es fácil hacer que los algoritmos sean altamente paralelizables. En sus ejemplos, TAR no es un algoritmo de compresión, y el único algoritmo que puede ser altamente paralelizable es BZIP porque es un algoritmo de compresión de bloques. Cada bloque se puede comprimir por separado, pero esto requeriría mucha y mucha memoria. LZMA no funciona en paralelo tampoco, cuando se ve 7zip usando múltiples hilos esto se debe a que 7zip divide la secuencia de datos en 2 flujos diferentes que cada uno se comprime con LZMA en una secuencia separada, por lo que el algoritmo de compresión no es paralímpico. Esta división solo funciona cuando los datos lo permiten.
Los algoritmos de encriptación han sido bastante exitosos en esta área, por lo que es posible que desee examinarlos. Aquí hay un documento relacionado con el cifrado CUDA y AES: http://www.manavski.com/downloads/PID505889.pdf
Con un rápido vistazo, que parece acelerar el cifrado de cada bloque. No ayuda que las cifras de bloqueo se encadenen para evitar ciertos tipos de ataques. http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation – Calyth
Es cierto que el documento no lo cubre, pero hay un artículo en gemas de GPU que un compañero de trabajo escribió sobre la descripción de AES con el código de Shafer, no sobre Cuda, que cubre el encadenamiento. Lamentablemente, el artículo no está en la web. De todos modos, el encadenamiento puede ser manejado por la GPU –
Estamos intentando transferir bzip2 a CUDA. :) Hasta ahora (y con solo pruebas aproximadas), nuestra Transformación Burrows-Wheeler es un 30% más rápida que el algoritmo serial. http://bzip2.github.com
Por lo que puedo ver, bzip2 usa múltiples núcleos de CPU, pero no CUDA. El enlace está roto. El enlace actual parece ser http://www.bzip.org/ –
Hemos finalizado la primera fase de investigación para aumentar el rendimiento de los algoritmos de compresión de datos sin pérdida. Bzip2 fue elegido para el prototipo, nuestro equipo optimizó solo una operación: transformación Burrows-Wheeler, y obtuvimos algunos resultados: aceleración 2x-4x en buenos archivos comprimibles. El código funciona más rápido en todas nuestras pruebas.
Vamos a completar bzip2, deflate de soporte y LZMA para algunas tareas de la vida real como: tráfico HTTP y compresión de copias de seguridad.
enlace del blog: http://www.wave-access.com/public_en/blog/2011/april/22/breakthrough-in-cuda-data-compression.aspx
Más uno para dar seguimiento a esta pregunta un año después de su publicación. Además, su trabajo parece interesante, gracias – eSniff
4 años pasados ... A todos (I) nos gustaría saber más acerca de su proyecto. ¿Cuáles son los resultados? ¿Dónde podemos encontrar fuentes, si están disponibles? En espera de sus comentarios – Jet
Alexander, alguna noticia? ¿El código está disponible en alguna parte? – einpoklum
30% es agradable, pero para aplicaciones como las copias de seguridad no es suficiente por un tiro largo.
Mi experiencia es que la corriente de datos promedio en tales casos obtiene compresión de 1.2-1.7: 1 usando gzip y termina limitada a una tasa de salida de 30-60Mb/s (esto es en una amplia gama de modernos (circa 2010) CPU de gama alta medio -2012).
la limitación aquí es generalmente la velocidad a la que los datos se pueden introducir en la propia CPU.
por desgracia, con el fin de mantener una cinta LTO5 unidad feliz, que necesita a raw (velocidad de datos no comprimible) de alrededor de 160Mb/s. Si los datos se pueden alimentar requieren velocidades de datos aún más rápidas.
La compresión LTO es claramente mucho más rápida, pero algo ineficiente (equivalente a gzip -1 - es lo suficientemente bueno para la mayoría de los propósitos). Las unidades LTO4 y superiores suelen tener motores de cifrado AES-256 que también pueden mantener este tipo de velocidades.
Lo que esto significa para mi caso es que necesitaría una imprementación de 400% o más para que valga la pena.
Se aplican consideraciones similares a través de las LAN. A 30 Mb/s, la compresión es un obstáculo en las redes de clase Gb y la pregunta es si gastar más en redes o en compresión ... :)
¿Qué es CUDAS limitaciones de memoria? Es decir. son bloques de 4K a 32K para manejar datos en paralelo, gzip se puede comprimir en paralelo al no guardar el diccionario entre bloques, esto aumenta el tamaño del archivo en ~ 5%. Ver. Dictzip para un ejemplo. –
Esta presentación se centra en Gzip y obtiene una aceleración en el orden de 10 http://on-demand.gputechconf.com/gtc/2014/presentations/S4459-parallel-lossless-compression-using-gpus.pdf –