842 (algoritmo de compresión)

842 , 8-4-2 o EFT es un algoritmo de compresión de datos sin pérdidas . Es una variación de la compresión Lempel-Ziv con una longitud de diccionario limitada. Con datos típicos, 842 ofrece entre el 80 y el 90 por ciento de la compresión de LZ77 con un rendimiento mucho mayor y menor consumo de memoria. ^{[ 1 ]} Las implementaciones de hardware también proporcionan un consumo mínimo de energía y un área mínima en el chip.

La compresión 842 se puede utilizar para la compresión de memoria virtual , para bases de datos (especialmente para almacenes orientados a columnas ) y al transmitir entrada/salida (por ejemplo, para hacer copias de seguridad o escribir en archivos de registro) .

El algoritmo opera sobre bloques de 8 bytes con subfrases de 8, 4 y 2 bytes. Se utiliza un hash de cada frase para buscar en una tabla hash con desplazamientos a un búfer de ventana deslizante de datos codificados anteriores. Las coincidencias pueden reemplazarse por el desplazamiento, por lo que el resultado para cada bloque puede ser una mezcla de datos coincidentes y nuevos datos literales. ^{[ 2 ] [ 1 ] [ 3 ]}

IBM añadió aceleradores de hardware e instrucciones para la compresión 842 a sus procesadores Power a partir de POWER7+ . ^{[ 4 ]} Además, POWER9 y Power10 añadieron aceleración de hardware para el algoritmo Deflate RFC 1951 , que utilizan zlib y gzip . ^{[ 5 ]}

En 2011 se añadió al kernel de Linux un controlador de dispositivo para la compresión 842 asistida por hardware en un procesador POWER. ^{[ 6 ]} Más recientemente, Linux puede recurrir a una implementación por software, que por supuesto es mucho más lenta. ^{[ 7 ]} zram , un módulo del kernel de Linux para unidades de RAM comprimidas , se puede configurar para usar 842.

Los investigadores han implementado 842 usando unidades de procesamiento gráfico y encontraron una descompresión aproximadamente 30 veces más rápida usando GPU dedicadas. ^{[ 8 ]} Una biblioteca de código abierto proporciona 842 para CUDA y OpenCL . ^{[ 9 ]} Una implementación de 842 en FPGA demostró un rendimiento 13 veces mejor que una implementación de software. ^{[ 10 ]}