PDF de programación - Compresión transparente para sistemas embebidos

Compresión transparente
para sistemas embebidos

Matías Zabaljáuregui

[email protected]

La Plata, Febrero de 2007

1

Indice General

1 Introducción

2 Algoritmos de compresión de datos

2.1 Métodos Estadísticos . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Compresión Huffman . . . . . . . . . . . . . . . . . . .
2.1.2 Codificación Aritmética . . . . . . . . . . . . . . . . .
2.1.3 Modelos basados en el contexto . . . . . . . . . . . . .
2.2 Métodos de diccionario . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Lempel-Ziv . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Métodos Híbridos . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 WKdm . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 DEFLATE/zlib . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1 El algoritmo DEFLATE . . . . . . . . . . . . . . . . .
2.4.2 La implementación zlib . . . . . . . . . . . . . . . . .

3 Introducción a la compresión transparente en sistemas de

archivos
3.1 Objetivos de diseño de un sistema de archivos comprimido . .
3.2 Compresión en un sistema de archivos estructurado como log
Sistemas de archivos estructurados como Log . . . . .

3.2.1

4 La tecnología Flash y JFFS2

4.1 Memorias Flash . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Capas de traducción y sistemas de archivos para me-
morias Flash . . . . . . . . . . . . . . . . . . . . . . .
4.2 Journaling Flash File System . . . . . . . . . . . . . . . . . .
4.2.1 La evolución de JFFS . . . . . . . . . . . . . . . . . .

5 Las pruebas realizadas con OLPC

5.1 Especificaciones de hardware de la placa OLPC . . . . . . . .
5.2 La configuración del framework de compresión y el método
utilizado para medir el tiempo
. . . . . . . . . . . . . . . . .
5.2.1 La compresión utilizada . . . . . . . . . . . . . . . . .
5.2.2 Midiendo el tiempo para leer o escribir un bloque de
. . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.3 Midiendo la latencia de comprimir o descomprimir los
. . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Los resultados obtenidos . . . . . . . . . . . . . . . . . . . . .

datos

datos

6 Conclusiones

1

2

3
4
4
4
5
5
6
6
6
7
8
9

9
10
11
13

14
14

15
16
17

19
19

20
20

20

22
23

25

1 Introducción

Las ventajas de las técnicas de compresión al vuelo se han estudiado desde
hace ya una década para su posible utilización en los diferentes subsistemas
del kernel de un sistema operativo. Se han planteado soluciones de compre-
sión transparente para el usuario de datos almacenados en memoria o disco
y datos enviados por la red, con resultados notables.

Por ejemplo, la memoria disponible insuficiente en sistemas embebidos
es un problema crítico que afecta la performance y confiabilidad de los dis-
positivos. Una posible solución para manejar este problema es comprimir
bloques de memoria accedidos infrecuentemente cuando el sistema se queda
sin memoria, y descomprimir la memoria cuando se necesite nuevamente, li-
berando memoria que puede ser realocada[11]. Por otro lado, la compresión
adaptativa y transparente de los datos enviados por la red permite reduc-
ciones sustanciales del uso del ancho de banda disponible en los enlaces de
comunicaciones.

Desde hace tiempo se plantea la opción de comprimir los datos que se
almacenan en los discos o dispositivos similares como una forma de incre-
mentar el espacio de almacenamiento efectivo. Una alternativa para im-
plementar esta idea de manera transparente para el usuario y sin tener que
realizar modificaciones importantes al diseño del sistema operativo es incluir
funcionalidad extra a un sistema de archivos, de manera tal que cuando el
usuario escriba datos al sistema de archivos, éste los comprima justo antes
de volcarlos en el disco y cuando el usuario intente recuperar sus datos, el
sistema de archivos los descomprima.

Este trabajo estudia las ventajas de aplicar esta última idea a un siste-
ma de archivos especialmente diseñado para memorias Flash. Actualmente,
la tecnología Flash es la mejor sustitución de un disco rígido en un dis-
positivo embebido. Tiene algunas características que la posicionan como la
solución más conveniente: es rápida, consume menos energía y produce me-
nos calor que un disco rígido, y no tiene partes móviles. A diferencia de un
disco, el procesador puede acceder directamente a los bits almacenados en
la memoria Flash como lo hace con una RAM o ROM, haciendo posible la
ejecución en el lugar (eXecution In Place o XIP) reduciendo de esta forma
los requerimientos de memoria RAM del dispositivo1.

El sistema de archivos estudiado se basa en el concepto de estructurar
los datos como un conjunto de entradas secuenciales en un log, en lugar de
acceder aleatoriamente a los bloques de un disco. Más allá de las ventajas
que presenta este diseño con respecto a la forma de acceso de las memorias
Flash, los sistemas de archivos estructurados en logs facilitan varios aspectos
de la implementación de la compresión al vuelo de los datos.

Para comprobar los beneficios en espacio de almacenamiento y medir el

1Esto sólo se aplica a algunas variantes de Flash.

2

overhead introducido por el procesamiento extra en compresión y descom-
presión, se escribieron programas de benchmark específicos para este trabajo
y se agregó código al kernel Linux para calcular las latencias. Las pruebas se
realizaron sobre hardware prototípico proveniente del proyecto One Laptop
Per Child del MIT.

El resto del informe se organiza de la siguiente manera: la sección 2 in-
troduce conceptualmente los algoritmos más utilizados para la compresión
de datos, prestando mayor atención a cuestiones de eficiencia en el uso de
recursos y complejidad temporal ya que, en este contexto, estos indicadores
son tan importantes como la relación de compresión. La sección 3 presenta
las ideas relacionadas con la compresión de datos incluida como una funcio-
nalidad adicional de un sistema de archivos y explica los principios en los
que se basan los sistemas de archivos estructrados como logs y el motivo por
el cual facilitan la compresión de los datos. La sección 4 describe brevemen-
te la tecnología Flash y las alternativas de software para manejarlas, y se
mencionan las particularidades del Journaling Flash sistema de archivos, en
particular con respecto a la compresión. Finalmente, la sección 5 presenta
en detalle la metodología y los resultados de las pruebas realizadas sobre el
dispositivo mencionado.

2 Algoritmos de compresión de datos

Hay algunas características deseables que debe tener un compresor de datos
para ser efectivo en el contexto de los sistemas embebidos. Estas incluyen
la habilidad de comprimir los datos con una relación suficiente para que se
justifique el overhead, poco uso persistente de memoria y una gran veloci-
dad de compresión y descompresión. Los indicadores de estas variables son
escenciales al elegir el algoritmo de compresión más apropiado.

Existen dos categorías principales de técnicas de compresión de datos:
aquellos que utilizan métodos estadísticos y aquellos que requieren el uso de
un diccionario. Ambas técnicas son muy utilizadas pero los esquemas basa-
dos en diccionario tienden a ser más usados para aplicaciones de archivos,
mientras que las situaciones de tiempo real típicamente requieren esquemas
de compresión estadísticos. La causa de esto es que los métodos basados en
diccionario tienden a ser lentos en la compresión y más veloces para des-
comprimir, mientras que los métodos estadísticos son igualmente veloces en
ambas operaciones.

En el dominio estudiado, la compresión de los datos intenta realizarse
con una aproximación de tiempo real (aunque no se exige la rigurosidad
de los estándares de tiempo real hard). Sin embargo, como cada bloque
de datos que se comprima eventualmente será descomprimido, la velocidad
combinada de compresión y descompresión puede ser tan importante co-
mo las velocidades de cada una de estas operaciones por separado. Por lo

3

tanto, ambos tipos de algoritmos, e incluso combinaciones de estas técnicas
deberían compararse para obtener el mejor resultado. La tabla 1 sumariza
información relacionada con la performance esperada de cada algoritmo.

Tipo

Algoritmo
Huffman
Aritmético Estadístico
Estadístico
Estadístico
Diccionario

PPM
CTW
LZO
WKdm
WKS

dependiente del contexto
dependiente del contexto

aprox. N (d)
aprox. N (d)
aprox. N (d)

Híbrido
Híbrido

Cuadro 1: Algoritmos de Compresión de datos

Complejidad Temporal
Estadístico N (n + log (2n-1)) + Sn
N (log (n) + a) + S n

Relacion de comp. Memoria persis.

Promedio
Promedio

Buena
Buena
Buena
Buena
Buena

Ninguna
Ninguna
Ninguna
Ninguna
Ninguna
Ninguna
Ninguna

2.1 Métodos Estadísticos

Los esquemas estadísticos de compresión determinan el código de salida ba-
sados en la probabilidad de ocurrencia de los símbolos de entrada y son
típicamente utilizados en aplicaciones de tiempo real. Como los algoritmos
de compresión y descompresión tienden a ser simétricos, la compresión y
descompresión usualmente requiere la misma cantidad de tiempo para com-
pletarse.

2.1.1 Compresión Huffman

El método Huffman es tal vez la técnica más comúnmente utilizada de com-
presión estadística. Durante el proceso de codificación, éste método cons-
truye una lista de todos los símbolos de entrada, ordenados en base a sus
probabilidades. El algoritmo luego construye un árbol, con un símbolo en
cada hoja, y recorre el árbol para determinar los códigos para cada símbolo.
Los símbolos con más probabilidad de ocurrencia tienen códigos más cor-
tos. La decodificación utiliza el código para recorrer el árbol hasta llegar al
símbolo.

La complejidad en el tiempo de una implementación adaptativa de la
codificación Huffman es lineal: N (n + log (2n-1)) + Sn, donde N es el número
total de símbolos de entrada, n es el número real de símbolos