PDF de programación - mplementación en FPGAs de Algoritmos de Compresión-Descompresión para Dispositivos Móviles

Centro de Investigación y de Estudios Avanzados del

Instituto Politécnico Nacional

Unidad Zacatenco

Departamento de Computación

Implementación en FPGAs de Algoritmos de
Compresión-Descompresión para Dispositivos

Móviles

Tesis que presenta:

Oscar Alvarado Nava

para obtener el Grado de:

Maestro en Ciencias

en la Especialidad de:

Ingeniería Eléctrica

Opción:

Computación

Director de tesis:

Dr. Arturo Díaz Pérez

México, D.F.

Febrero de 2007

ii

Resumen

La Codificación Fractal de Imágenes (CFI) es una técnica de compresión con
pérdidas cuyas características son muy prometedoras para dispositivos móviles de
bajos recursos, sin embargo, se ha matenido marginada debido a la gran cantidad
operaciones que deben de llevarse a cabo para la codificación, traduciéndose en un
alto tiempo de cómputo.

Por otro lado, el desarrollo de la tecnología VLSI ha permitido crear dispositivos
programables con mayores prestaciones, los cuales no solo ofrecen una gran densidad
de compuertas para la programación de módulos de hardware, si no que además
cuentan con uno o más procesadores empotrados, permitiendo con ello la creación de
sistemas completos dentro de un solo chip (System on Chip, SoC). La utilización de
componentes hardware y software en un único sistema electrónico permite combinar
las características de flexibilidad que el software ofrece y la altas prestaciones de
cómputo y paralelismo del hardware.

Por medio del Codiseño Hardware-Software (CHS), es posible desarrollar un sis-
tema completo que mejore el desempeño de una solución puramente en software al
llevar parte de la aplicación a un hardware de propósito específico. Inicialmente se
realiza un análisis del perfil de rendimiento de la aplicación para localizar las partes
más recurrentes y costosas en cómputo. Con clasificación de las partes en base a su
costo, recurrencia y complejidad computacional, se lleva a cabo un particionamiento,
lo cual implica llevar a hardware algunas de estas partes y mantener el resto en soft-
ware. Finalmente se desarrollan interfaces o drivers para la integración de las nuevas
partes de hardware con las partes en software.

En el presente documento se presenta el CHS para el desarrollo de un sistema de
tipo SoC basado en FPGA, el cual mejora el desempeño de la solución en software
de la CFI.

iii

Abstract

The Fractal Image Coding (FIC) is a lossy compression technique with promising
features for low-resources mobil devices. However, this technique has been left aside
due to the big amount of operations required for the step. Hence, requiring large
computing time.

On the other side, VLSI technology has evolved into programmable devices with
higher capabilities. The devices not only offer a high gate density for programming
hardware modules, and devices now have one or more embedded processors. This
allows for complete system development inside a single chip (System on Chip, SoC).
Hardware and software components in a single electronic system allow to exploid the
software flexibility and hardware performance, as well as its parallelism.

A complete system can be developed with the Hardware/Software co-design (HSC)
in a way that outperforms a pure-software implementation. The performance impro-
vement is obtained when part of the application is implemented a specific-purpose
hardware. Initially, an analysis of the performance is done to find the most recurrent
and expensive (computationally speaking) parts. Some of the parts are implemented
on hardware and some in software. The selection is done by classifying the parts based
on cost, recurrence, and computational complexity. Finally, interfaces or drivers are
developed for the integration of the new hardware parts with those of software.

The present document contains the HSC for the development of a SoC system
based on FPGA. The system has a better performance than the FIC’s software im-
plementation.

v

Agradecimientos

- Al Departamento de Computación del Centro de Investigación y de Estudios

Avanzados del IPN.

- Al Consejo Nacional de Ciencia y Tecnología por el apoyo económico otorgado.

- Al Consejo Nacional de Ciencia y Tecnología por financiar parcialmente este
trabajo a través del proyecto 45306: Estudio, Análisis y Desarrollo de Algoritmos
de Muy Alto Desempeño para Arquitecturas Hardware/Software

- A la División de Ciencias Básicas e Ingeniería de la Universidad Autónoma

Metropolitana, Unidad Azcapotzalco.

vii

viii

AGRADECIMIENTOS

Índice general

Resumen

Abstract

Agradecimientos

Lista de Figuras

Lista de Tablas

1. Introducción

1.1. Motivaciones
1.2. Objetivos
1.3. Organización de la tesis

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .

2. Codificación Fractal de Imágenes

2.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Fractales en todas partes . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
2.3. Sistema de funciones iteradas
2.4. Sistema de funciones iteradas locales
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5. Transformada fractal
2.6. Ejemplo de codificación . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7. Propiedades de la codificación fractal
. . . . . . . . . . . . . . . . . .
2.7.1. Tiempos de codificación y decodificación . . . . . . . . . . . .
2.7.2. Calidad de la imagen . . . . . . . . . . . . . . . . . . . . . . .
2.7.3. La compresión de la imagen y la razón de compresión . . . . .
2.7.4.
Independencia de la resolución . . . . . . . . . . . . . . . . . .
2.8. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Codiseño Hardware-Software

3.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.
Inicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Maduración . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Sistemas en un chip basados en FPGA . . . . . . . . . . . . . . . . .

ix

III

V

VII

XI

XIV

1
1
3
5

7
7
8
8
10
12
15
18
18
20
22
24
25

27
27
28
29
31

x

ÍNDICE GENERAL

3.5. Metodología de codiseño hardware software . . . . . . . . . . . . . . .
3.5.1. Ejemplo de codiseño hardware software . . . . . . . . . . . . .
3.6. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. Codiseño Hardware-Software de la CFI

4.5.

4.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Algoritmo de la codificación fractal de imágenes . . . . . . . . . . . .
4.3. Particionamiento hardware software . . . . . . . . . . . . . . . . . . .
4.3.1. Análisis de desempeño . . . . . . . . . . . . . . . . . . . . . .
4.3.2.
. . . . . . . . . . . . . . . . . . . . . . .
Imagen de hardware
Imagen de software . . . . . . . . . . . . . . . . . . . . . . . .
4.3.3.
4.4. Unidad de transformación y comparación . . . . . . . . . . . . . . . .
4.4.1. Ruta de datos . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2. Unidad de control . . . . . . . . . . . . . . . . . . . . . . . . .
Interfaz hardware software . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1. Registros IO . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.2. Driver de software . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6.1. Sistema ACE . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6.2. Sistema RAM . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7. Sistema final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7.1. Mapa de direcciones
. . . . . . . . . . . . . . . . . . . . . . .
4.7.2. Sistema en el chip . . . . . . . . . . . . . . . . . . . . . . . . .
Implantación del sistema . . . . . . . . . . . . . . . . . . . . .
4.7.3.
4.8. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6. Sistemas adicionales

5. Resultados

5.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Plataforma de pruebas . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3. Verificación del sistema . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4. Tiempo de codificación . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1. Solución software . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.2. Solución hardware-software
. . . . . . . . . . . . . . . . . . .
5.4.3. Aceleración . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5. Análisis de resultados . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1. Análisis de recursos ocupados . . . . . . . . . . . . . . . . . .
5.5.2. Análisis de tiempos de operación . . . . . . . . . . . . . . . .

6. Conclusiones y Trabajo Futuro

6.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2. Trabajo Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A. Archivos de Configuración

35
38
42

43
43
44
47
48
51
52
53
54
60
64
66
68
69
70
70
71
72
72
74
78

79
79
80
82
83
83
84
85
85
85
87

89
89
93

95

ÍNDICE GENERAL

B. Descripción de la UTC en VHDL

xi

101

xii

ÍNDICE GENERAL

Índice de figuras

sistema de funciones iteradas de la ecuación 2.1.

2.1. Hoja de maple en resolución de 512x512 pixeles generada mediante el
. . . . . . . . . . .
2.2. La idea clave de Jacquin fue considerar una imagen formada por copias
de partes de sí misma. Las regiones R1 y R2 son similares bajo una
. . . . . . . . . . . . .
transformación apropiada en ambas imágenes.
. . . . . . . . . . . . . .
2.3. Porciones autosimilares de la imagen Lena.
2.4. de flujo para el proceso de compresión utilizando la Transformada Frac-
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5. Diagrama de flujo para e