activar - Biblioteca de compresión usando CUDA de Nvidia
cuda wikipedia (6)
Normalmente, los algoritmos de compresión no pueden hacer uso de tareas paralelas, no es fácil hacer que los algoritmos sean altamente paralelables. 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.
¿Alguien conoce un proyecto que implementa métodos de compresión estándar (como Zip, GZip, BZip2, LZMA, ...) usando la biblioteca CUDA de NVIDIA?
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é piensas sobre los pros y los contras de tal enfoque?
Los algoritmos de encriptación han tenido bastante éxito en esta área, por lo que es posible que desee analizarlos. Aquí hay un documento relacionado con el cifrado CUDA y AES: http://www.manavski.com/downloads/PID505889.pdf
No estoy enterado de que alguien haya hecho eso y lo haya hecho público. Solo en mi humilde opinión, no suena muy prometedor.
Como Martinus señala, algunos algoritmos de compresión son altamente 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 vectoriales, donde puedes 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 se adapta mejor a la CPU multinúcleo.
Los algoritmos de compresión de video pueden acelerarse mediante el 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 las subrutinas IDCT o convolución 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 accesos 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 en la GPU que la CPU porque Estoy atado a la memoria.
Estamos haciendo un intento de portar 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
El 30% es bueno, pero para aplicaciones como copias de seguridad no es suficiente por mucho.
Mi experiencia es que el flujo de datos promedio en tales casos obtiene una compresión de 1.2-1.7: 1 usando gzip y termina limitado a una tasa de salida de 30-60Mb / s (esto es a través de una amplia gama de medios modernos (circa 2010-2012) CPU de gama alta.
La limitación aquí es, por lo general, la velocidad a la que los datos se pueden alimentar a la CPU.
Desafortunadamente, para mantener feliz a una unidad de cinta LTO5, necesita una velocidad de datos en bruto (no comprimible) de alrededor de 160Mb / s. Si se alimentan datos comprimibles, se 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 hacia arriba generalmente incorporan 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 implementación de 400% o mejor para considerar que vale la pena.
Consideraciones similares se aplican a través de 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 ... :)
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, la 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 support 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