proyecto final 2015 (PDF)

Universidad de la República
Facultad de Ingeniería
Instituto de Computación

Informe de Proyecto de Grado

Uso de aceleradores de hardware en sistemas de Bases de
Datos relacionales

Autores:
Lesly Acuña
Valentina Parula

Tutores:
Lorena Etcheverry
Pablo Ezzatti

Resumen
En la actualidad, la utilización de las GPUs para el cómputo de problemas de propósito
general ha aumentado. A su vez, los sistemas manejadores de bases de datos son una
herramienta muy utilizada en el campo de la computación. Dichas herramientas implican
altos niveles de requerimiento de cómputo, los cuáles llevan un tiempo significativo de
ejecución.
En este proyecto se busca estudiar la utilización de las GPUs como aceleradores de hardware de manejadores de bases de datos. Para ello como primer paso se realiza un análisis de
los manejadores actualmente disponibles que utilizan GPUs para acelerar su procesamiento, poniendo foco en la utilización que realizan de la GPU. De este análisis se desprende
que existen tres enfoques diferentes de utilización de las GPUs. El primero es realizar todo el procesamiento en GPU, utilizando la CPU para despachar las consultas y obtener
resultados. El segundo, es un enfoque híbrido en el que se realiza parte del procesamiento
en GPU y parte del procesamiento en CPU, a este procesamiento se le llamará enfoque
híbrido no concurrente. Existe un tercer enfoque que consiste en realizar el procesamiento
en paralelo en la GPU y en la CPU. Dicho enfoque se llamará enfoque híbrido concurrente.
Si bien los manejadores estudiados utilizan el primer y segundo enfoque, ninguno de estos
realiza un procesamiento híbrido concurrente para ejecutar las operaciones.
Por último, en el contexto de este proyecto se propone e implementa un algoritmo
híbrido concurrente para la operación de Join. Dicho algoritmo permite utilizar los recursos
de CPU y GPU, minimizando así los recursos ociosos. A su vez, se busca que la ejecución
mejore los tiempos de respuesta de dicha operación, mejorando los tiempos de la ejecución
de las consultas en general. Esta implementación se integra a uno de los manejadores
relevados (CoGaDB). La evaluación experimental muestra que para grandes volúmenes de
datos, al utilizar el algoritmo de Join híbrido concurrente se hace un mejor uso de los
recursos, obteniendo como resultado mejores tiempos de ejecución de consultas.
Palabras clave GPU, DBMS, Bases de Datos Relacionales, Bases de datos columnares,
Aceleradores de Hardware, Optimización de consultas, CoGaDB

Índice general
1. Introducción
1.1. Objetivos del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Logros obtenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
2
2

2. Conceptos preliminares
2.1. Bases de Datos Relacionales . . . . . . .
2.2. Sistemas Manejadores de Bases de Datos
2.2.1. Arquitectura . . . . . . . . . . .
2.3. Tarjetas Gráficas (GPUs) . . . . . . . .
2.3.1. CUDA . . . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

3
. 3
. 7
. 7
. 12
. 12

3. Bases de Datos y GPUs
3.1. GPUQP . . . . . . . . . . .
3.2. Virginian . . . . . . . . . .
3.3. GPUDB . . . . . . . . . . .
3.4. MapD . . . . . . . . . . . .
3.5. Ocelot . . . . . . . . . . . .
3.6. OmniDB . . . . . . . . . . .
3.7. CoGaDB . . . . . . . . . . .
3.8. Comparación de los DBMS

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

15
15
15
16
16
16
16
16
17

.
.
.
.
.
.

19
19
20
21
21
22
22

.
.
.
.
.
.
.
.

23
23
24
26
28
29
29
30
30

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

4. CoGaDB
4.1. Arquitectura . . . . . . . . . . . . . . .
4.2. HyPE . . . . . . . . . . . . . . . . . . .
4.3. Lenguajes y bibliotecas utilizadas . . . .
4.4. Almacenamiento y compresión de datos
4.5. Procesamiento y ejecución de consultas .
4.6. Transferencia de datos a la GPU . . . .

.
.
.
.
.
.

5. Prueba de Concepto
5.1. Descripción del problema . . . . . . . . .
5.2. Diseño . . . . . . . . . . . . . . . . . . . .
5.3. Implementación . . . . . . . . . . . . . . .
5.3.1. Algoritmos implementados . . . . .
5.3.2. Decisiones tomadas . . . . . . . . .
5.3.3. Dificultades encontradas durante la
5.4. Evaluación experimental . . . . . . . . . .
5.4.1. Plataforma de hardware . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
implementación
. . . . . . . . . .
. . . . . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

ÍNDICE GENERAL
5.4.2. Casos de prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.4.3. Definición del contexto utilizado en las pruebas . . . . . . . . . . . . 31
5.4.4. Resultados experimentales . . . . . . . . . . . . . . . . . . . . . . . . 32
6. Conclusiones y trabajo futuro
39
6.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.2. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
A. Manual de referencia de CoGaDB
A.1. Instalación . . . . . . . . . . . . . . .
A.1.1. Requisitos de Hardware . . .
A.1.2. Pre-instalación . . . . . . . .
A.1.3. Instalación . . . . . . . . . .
A.2. Ejecución . . . . . . . . . . . . . . .
A.2.1. Ejecutar en Terminal . . . . .
A.2.2. Ejecutar utilizando la interfaz
A.2.3. Generar la documentación . .
A.3. Comandos disponibles . . . . . . . .
A.4. Observaciones encontradas . . . . . .
A.5. TPC-H . . . . . . . . . . . . . . . . .

. . .
. . .
. . .
. . .
. . .
. . .
web
. . .
. . .
. . .
. . .

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

41
41
41
41
41
42
42
42
43
43
44
45

B. Bugs en CoGaDB
47
B.1. Bugs encontrados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
B.2. Solución de los bugs encontrados . . . . . . . . . . . . . . . . . . . . . . . . 47
C. Código de la implementación
C.1. base_column.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.2. base_table.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.3. column.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49
49
51
54

D. Resultados detallados de las ejecuciones
57
D.1. Resultados de las ejecuciones variando los porcentajes de CPU utilizados,
tomando tamaño de tabla fijo . . . . . . . . . . . . . . . . . . . . . . . . . . 57
D.2. Tablas de resultados utilizando otros tamaños de tabla . . . . . . . . . . . . 65

Índice de tablas
3.1. Comparación del año de presentación y lenguaje utilizado en los manejadores
de BD que utilizan GPUs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2. Comparación de los manejadores de BD que utilizan GPUs disponibles basada en la utilización de datos y el modo de ejecución. . . . . . . . . . . . . 17
3.3. Comparación de los manejadores de BD basada en la utilización de las GPUs. 18
5.1. Promedios de tiempos de ejecución (en milisegundos) para el algoritmo provisto por CoGaDB con distintos tamaños de tablas. . . . . . . . . . . . . . . 32
5.2. Promedios de tiempos de ejecución (en milisegundos) para el algoritmo híbrido concurrente con cpu_per óptimo y distintos tamaños de tablas. . . . . 33
5.3. Tiempo promedio de ejecución (en milisegundos) del algoritmo de Join híbrido para tamaño de tabla fijo, variando el cpu_per. . . . . . . . . . . . . . 34
D.1. Resultados de las ejecuciones utilizando el algoritmo provisto por CoGaDB
para CPU y GPU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.2. Ejecución del algoritmo híbrido concurrente con cpu_per 0 y 1, simulando
la ejecución en GPU y CPU respectivamente. . . . . . . . . . . . . . . . . .
D.3. Resultados de las ejecuciones del algoritmo híbrido concurrente con distintos
porcentajes de procesamiento en CPU. . . . . . . . . . . . . . . . . . . . . .
D.4. Resultados de las ejecuciones del algoritmo híbrido concurrente para distintos porcentajes de CPU y del algoritmo provisto por CoGaDB en CPU y
GPU, tomando la primer tabla del Join con seis elementos. . . . . . . . . .
D.5. Resultados del algoritmo híbrido concurrente para distintos porcentajes de
CPU y del algoritmo provisto por CoGaDB en CPU y GPU, tomando la
primer tabla del Join con 586 elementos. . . . . . . . . . . . . . . . . . . . .
D.6. Resultados de las ejecuciones del algoritmo híbrido concurrente para distintos porcentajes de CPU y del algoritmo provisto por CoGaDB en CPU y
GPU, tomando la primer tabla del Join con 6005 elementos. . . . . . . . . .
D.7. Resultados de las ejecuciones del algoritmo híbrido concurrente para distintos porcentajes de CPU y del algoritmo provisto por CoGaDB en CPU y
GPU, tomando la primer tabla del Join con 60175 elementos. . . . . . . . .
D.8. Resultados de las ejecuciones del algoritmo híbrido concurrente para distintos porcentajes de CPU y del algoritmo provisto por CoGaDB en CPU y
GPU, tomando la primer tabla del Join con 1199969 elementos. . . . . . . .
D.9. Resultados de las ejecuciones del algoritmo híbrido concurrente para distintos porcentajes de CPU y del algoritmo provisto por CoGaDB en CPU y
GPU, tomando la primer tabla del Join con 2999671 elementos. . . . . . . .

57
61
64

66

67

68

69

70

71

ÍNDICE DE TABLAS
D.10.Resultados del algoritmo híbrido concurrente para distintos porcentajes de
CPU y del algoritmo provisto CoGaDB en CPU y GPU, tomando la primer
tabla del Join con 12002430 elementos. . . . . . . . . . . . . . . . . . . . . . 72
D.11.Resultados de las ejecuciones del algoritmo híbrido concurrente para distintos porcentajes de CPU y del algoritmo provisto por CoGaDB en CPU y
GPU, tomando la primer tabla del Join con 30006075 elementos. . . . . . . 73

Índice de figuras
2.1.
2.2.
2.3.
2.4.
2.5.
2.6.
2.7.
2.8.

Ejemplos para los dos tipos de Inner Join. . . . . . . . . . . . . . . . . . . . 5
Ejemplos para los dos tipos de Outer Join. . . . . . . . . . . . . . . . . . . . 5
Arquitectura típica de un DBMS. . . . . . . . . . . . . . . . . . . . . . . . . 7
Ejemplo de entrada y salida de la interfaz SQL. . . . . . . . . . . . . . . . . 7
Ejemplo de entrada y salida del optimizador lógico. . . . . . . . . . . . . . . 8
Ejemplo de entrada y salida del optimizador físico. . . . . . . . . . . . . . . 9
Modelos de procesamiento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Ejemplo de almacenamiento orientado a columnas y su capacidad de compresión. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.9. Proceso de ejecución de una consulta SQL en una arquitectura típica DBMS.
Adaptada de [15]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.10. Diferencia entre la arquitectura típica de una CPU y la de una GPU. Tomada
de [28]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.1. Arquitectura de CoGaDB. Adaptada de [10]. . . . . . . . . . . . . . . . . . 19
4.2. Utilización de HyPE en CoGaDB. Adaptada de [11]. . . . . . . . . . . . . . 20
4.3. Utilización de HyPE en CoGaDB. Tomada de [11]. . . . . . . . . . . . . . . 21
5.1.
5.2.
5.3.
5.4.
5.5.

Representación de la solución en alto nivel del Join híbrido concurrente. . .
Operaciones del Join en CoGaDB. . . . . . . . . . . . . . . . . . . . . . . .
Operaciones que realiza el Join híbrido concurrente. . . . . . . . . . . . . .
Partición de la columna en la operación de Join propuesta. . . . . . . . . .
Ejecución del Join con las particiones de la primer columna y la segunda
columna. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6. Unión de LookupTable resultado de los Joins. . . . . . . . . . . . . . . . . .
5.7. Modelo relacional de TPCH. Tomada de [14]. . . . . . . . . . . . . . . . . .
5.8. Variación del cpu_per óptimo para distintos tamaños de tablas. . . . . . . .
5.9. Tiempos promedios de ejecución de la consulta para distintos valores de
cpu_per. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.10. Distribución (en %) del tiempo de ejecución del algoritmo de Join de CoGaDB en cada dispositivo. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.11. Distribución (en %) de los tiempos de ejecución del algortimo de Join híbrido
concurrente con valor de cpu_per óptimo. . . . . . . . . . . . . . . . . . . .
5.12. Distribución (en %) del tiempo de ejecución del Join híbrido concurrente en
cada dispositivo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.13. Tiempos de ejecución de la misma consulta para distintos tamaños de tablas
en CPU, GPU y del porcentaje óptimo en el algoritmo híbrido. . . . . . . .

23
24
25
26
27
27
31
33
34
35
35
36
37