PDF de programación - Cálculo en Tiempo Real de Identificadores Robustos para Objetos Multimedia mediante una Arquitectura Paralela CPU-GPU

Cálculo en Tiempo Real de Identiicadores
Robustos para Objetos Multimedia mediante

una Arquitectura Paralela CPU-GPU

Lic. Natalia Carolina Miranda

UNIVERSIDAD NACIONAL DE SAN LUIS

FACULTAD DE CIANCIAS FÍSICO, MATEMÁTICA Y NATURALES

DEPARTAMENTO DE INFORMÁTICA

TESIS PARA OPTAR AL GRADO DE DOCTOR

EN CIENCIAS DE LA COMPUTACIÓN

Cálculo en Tiempo Real de Identiicadores
Robustos para Objetos Multimedia mediante

una Arquitectura Paralela CPU-GPU

Lic. Natalia Carolina Miranda

Director

Dr. Chávez Edgar Leonel

Co-Director

Dra. Piccoli María Fabiana

La Plata, abril de 2014

Miranda, Natalia Carolina
Cálculo en tiempo real de identiicadores robustos para objetos
multimedia mediante una arquitectura paralela CPU-GPU / Natalia
Carolina Miranda. - 1a ed. - La Plata: Universidad Nacional de La Plata.
Facultad de Informática, 2016.
235 p.; 24 x 16 cm.

ISBN 978-950-34-1302-9

1. Informática. 2. Tesis Doctorales. I. Título.
CDD 004.0711

Primera edición, 2016
ISBN N.º 978-950-34-1302-9

Queda hecho el depósito que marca la Ley 11723
Impreso en Argentina

A mis dos soles: Mateo y Enrique.

A mis padres.

Agradecimientos

Han pasado muchos años desde que comencé la tesis y esta es la
parte más difícil para mí, expresar mi reconocimiento a todas aquellas
personas que lo hicieron posible. Todos, desde el lugar que les tocó
participar, contribuyeron a la concreción de éste, hasta ahora el trabajo
más importante y de mayor envergadura que haya encarado en mi vida
académica. Probablemente me olvidaré de nombrar a algunas personas,
y espero que me perdonen.
En primer lugar quiero agradecer a mis directores de tesis, el Dr. Edgar
Chávez y la Dra. Fabiana Piccoli. Al Dr. Edgar Chávez por creer en mí aún
sin conocerme, por haberme brindado todo lo que estuvo a su alcance y
haber hecho posible, a pesar de las distancias y limitaciones, el desarrollo
de este trabajo. A la Dra. Fabiana Piccoli por su apoyo ininito, por los
aportes, los concejos y el tiempo que me dedicó para resolver todas mis
inquietudes. En ella no solo encontré una profesora sino también a una
amiga con la que podía coniar.
Mi agradecimiento se hace extensivo a la Fac. Cs. Fca. Matemática y
Naturales, especialmente al departamento de Informática, al proyecto
de investigación al que pertenezco y a CONICET por todo el apoyo
brindado.
Quiero agradecer a aquellas personas que me brindaron su amistad y su
apoyo desinteresado:

• A Nora Reyes por estar siempre dispuesta a responder mis consultas,
por el tiempo que me dedicó para ayudarme, aconsejarme y brindarme
sus valiosos aportes.

• A Gabriela Palacio y Cecilia Palacios por escucharme y apoyarme

incondicionalmente, gracias por estar a mi lado.

• A Mariela Lopresti por escuchar y ayudar en la solución de problemas
compartidos y a Mercedes Barrionuevo por brindarme aliento y apoyo.
• A Jacqueline Fernández por todo el tiempo que pasamos juntas

realizando los trabajos para aprobar los cursos de postgrado.

• A todos aquellos profesores que de una forma u otra me impulsaron

a seguir formándome y a seguir en esta disciplina.

Quiero agradecer a mi familia (hermanos, suegros, cuñados y sobrinos)
y amigos quienes sin conocer lo que signiica realizar un doctorado
brindaron su apoyo y concejo.
Por último mi especial agradecimiento a mi esposo Enrique y mi hijo
Mateo no sólo por permitirme hacer esta tesis, quitándoles tiempo para
disfrutar juntos, sino porque sin ellos mi vida estaría vacía y mis logros
académicos carecerían de sentido.
A mis padres que siempre estuvieron conmigo y se alegran de cada uno
de mis logros. Por cuidar de Mateo cuando yo no estaba en casa.
A todos y cada uno de los que colaboraron, hasta del lugar más pequeño.
¡¡¡ Muchas Gracias!!!

Índice General





de Características

Espacios Métricos

1 Introducción













1.1.1. Huella Digital de Audio: Extracción

1.1.2. Recuperación de Objetos Multimedia:

1.1.3. Limitaciones de GPGPU y CUDA

1.1 Descripción de la Problemática





1.2 Objetivos
1.3 Principales Contribuciones y Publicaciones



1.4 Organización de la Tesis

1.3.1. Huella Digital de Audio
1.3.2. Espacios Métricos
1.3.3. Publicaciones de Transferencia de desarrollo.

Basado en el Contenido
2.3.1. Extracción de Características
2.3.1.1. Módulo Front-End
2.3.1.2. Módulo Modelado de la AFP

2 Huella Digital de Audio














2.1 Propiedades deseables en una AFP
2.2 Aplicaciones de la AFP
2.3 Estructura General de un Sistema de Huella Digital




2.4 Proceso Secuencial AFP basado en Entropía




2.5 Resumen

2.4.1. Entropía
2.4.2. AFPs Basadas en la Entropía
2.4.2.1. Time-Domán Entropy Signature: TES
2.4.2.2. Multi-Band Spectral Entropy Signature: MBSES



3 Espacios Métricos: Generalidades



3.1 Espacios Métricos


3.1.1. Funciones de Distancia

17
21

22

23
24
24
25
26
27
27
29

33
33
36

37
39
39
42
44
46
47
48
49
52

55
55
56











3.3.1. Método de Fuerza Bruta
3.3.2. Métodos Basados en Índices

3.2 Búsquedas por Similitud
3.3 Estrategias Utilizadas en Espacios Métricos


3.4 Algoritmo SAT+



3.5 Resumen

3.4.1. Construcción del SAT+
3.4.2. Búsqueda por Rango
3.4.3. Búsqueda de Vecinos más Cercanos



4 GPGPU














4.2.1. CPU y GPU
4.2.2. Evolución Histórica de la GPU
4.2.3. GPU y Computación de Alto Desempeño
4.2.4. GPGPU: Computación de Propósito General


4.1 Computación de Alto Desempeño
4.2 Unidad de Procesamiento Gráico: GPU





4.3 Programación de GPUs: CUDA



4.4 Modelo de Ejecución
4.5 Resumen

4.3.1. Arquitectura de GPU según CUDA
4.3.2. Modelo de Programación CUDA
4.3.3. Generalidades de la Programación con CUDA





en GPU



5.2.1. Aspectos de Diseño
5.2.1.1. Etapa Hanning y FFT
5.2.1.2. Etapa Entropía
5.2.1.3. Obtención AFP
5.2.2. Aspectos de Implementación

5 Huella Digital de Audio en GPU













5.1 Estado del Arte
5.2 Cálculo de la AFP MBSESGPU





5.3 Cálculo de la AFP TESGPU

5.3.1. Aspectos de Diseño

5.3.2. Aspectos de Implementación
5.4 TESGPU vs MBSESGPU
5.5 Estado del Arte vs TESGPU y MBSESGPU

58
62
63
63
66
67
69
70
70

73
74
75
76
79
81

82
86
87
88
89
97
102

103
103
107
108
108
109
112
112
114
115
117
119
120




5.6 Resultados Experimentales
5.7 Resumen



6.1.1. Método de Fuerza Bruta
6.1.1.1. Aspectos Algorítmicos
6.1.1.2. Aspectos de la Implementación
6.1.2. Método Utilizando Índices Métricos
6.1.2.1. Descripción Algorítmica
6.1.2.2. Descripción de la Implementación

6 Espacios Métricos en GPU



















6.1 Estado del Arte






6.2 Consulta por k-NN: Top-K
6.2.1. Aspectos Algorítmicos


6.2.2. Aspectos de la Implementación
6.3 Otras Consultas resueltas con Top-K
6.4 Resolviendo Múltiples Consultas k-NN
6.5 Resultados Experimentales

6.5.1 Consulta por Rango
6.5.2 Consultas k-NN


6.5.3 Consulta all-k-NN
6.6 Top-K vs Estado del Arte
6.7 Resumen



Conclusiones y trabajos futuros

A Generaciones de Arquitectura de GPU Nvidia
A.1 Arquitectura G80
A.2 Arquitectura GT200
A.3 Arquitectura Fermi (GF100)
A.4 Arquitectura Kepler (GK110)
B Otros Desarrollos en GPU
B.1 Propuesta all-k-NN aproximado

B.2 Propuesta Men-M

C Ventajas y Desventajas del Estado del Arte

B.1.0.1. Desarrollo en GPU

B.2.0.2. Desarrollo en GPU





Bibliografía





121
126

129
129
130
131
135
140
141
143
146
149
150
154
157
157
159
164
178
182
183

185

191
191
197
199
204
209
209
210
214
215
217

222

Índice de Figuras

2.1 Estructura General de un Sistema de AFP Basado en el

Contenido según [CBKH05]



38



según [CBKH05]

2.2 Estructura de la Extracción de Características de una AFP
40

44
2.3 Proceso Secuencial AFP
48
2.4 Proceso Secuencial AFP para TES
50
2.5 Distintas curvas según las bandas de la escala de Bark
51
2.6 Proceso Secuencial AFP para MBSES
53
2.7 Escala de Barks para la Estimación de las Bandas Críticas
59
3.1 Ejemplo de una Búsqueda por Rango
60
3.2 Ejemplo de una Búsqueda de los k-NN con k=2
61
3.3 Ejemplo de una Búsqueda de los all-k-NN para k=2
62
3.4 Ejemplo de una Búsqueda join k-NN para k=2
68
3.5 Ejemplos de SAT+
77
4.1 Arquitectura CPU vs Arquitectura GPU
87
4.2 Arquitectura CUDA de la GPU
89
4.3 Threads y jerarquía de memoria
92
4.4 Organización de los threads en un bloque
93
4.5 Organización de los Bloques en un Grid
94
4.6 Esquema de la estructura de un programa en CUDA
4.7 Jerarquía de memoria y accesos
95
4.8 Ejecución de un programa CUDA C en un Sistema CPU-GPU 98
4.9 Flujo de procesamiento de un kernel en la GPU
99
100
4.10 División de N bloques en warps
107
5.1 Proceso Paralelo para la obtención de la AFP MBSESGPU
110
5.2 Etapa Entropía para cada Frame
5.3 Proceso Paralelo para la obtención de la AFP TES
114
123
5.4 Aceleración de MBSESGPU y TESGPU en 3 GPU
5.5 Througput de MBSESGPU y TESGPU en 3 GPU
125

126

161

162









en 3 GPUs

en 3 GPUs

127
147
148
155
156

para Colors y Vocab

en 3 GPU para A-218 y distintos tamaños de frame

5.6 Througput de AFP MBSESGPU vs. TESGPU
5.7 Tiempos de Ejecución de MBSESGPU y TESGPU

6.1 Proceso Completo Top-K
6.2 Proceso Genérico para obtener los k-NN de una consulta q
6.3 Búsqueda por rango
6.4 Búsqueda por All-k-NN
6.5 Aceleración de la Consulta por Rango para BD de Vectores

6.6 Aceleración de la Consulta por Rango para BD de String

6.7 Througput de la Consulta por Rango paralela y secuencial
164

6.8 Aceleración de la Consulta por k-NN para Nasa en 2 GPUs
165
6.9 Aceleración de la Consulta por k-NN para Colors en 3 GPUs 167
6.10 Aceleración de la Consulta por k-NN para English en 3 GPUs 169
170
6.11 Aceleración de la Cons