Departamento de Computación

Datalog es un lenguaje basado en lógica de primer orden que fue desarrollado en los 80s como modelo de datos para bases de datos relacionales. Recientemente, ha sido utilizado en nuevas áreas de aplicación, por lo que se han hecho propuestas para ejecutar Datalog en nuevas plataformas tales como Unidades de Procesamiento Gráfico (GPUs en inglés) y MapReduce. En ese entonces como hoy en día, el interés en Datalog es el resultado de su habilidad para calcular el cierre transitivo de relaciones por medio de consultas recursivas que, en efecto, transforman las bases de datos relacionales en bases de datos deductivas o bases de conocimiento. El tema de esta tesis es el diseño, implementación y evaluación de un motor paralelo del lenguaje Datalog para GPUs. A nuestro conocimiento, es el primer motor totalmente funcional de Datalog para GPUs. Consiste en: i) un compilador que traduce los programas de Datalog en operadores de algebra relacional (selección, varios tipos de uniones y proyección); ii) un planficador que prepara y manda ejecutar estas operaciones en la GPU desde la plataforma anfitrión; iii) los algoritmos paralelos de dichas operaciones; y iv) un esquema de manejo de memoria que tiende a reducir el número de transferencias de memoria entre el anfitrión y la GPU. También incluye varias optimizaciones que aprovechan las características del lenguaje Datalog y la arquitectura de las GPUs. Nuestro motor de Datalog fue desarrollado en C utilizando la plataforma de software de Nvidia CUDA. La evaluación de nuestro motor utilizando varias consultas muestra un importante incremento en el rendimiento al compararla contra XSB y YAP, famosos motores de Prolog, y el motor de Datalog de la corporación Mitre. Para dos de las consultas, se obtuvo un incremento en el rendimiento de hasta 200 veces.

Abstract

Datalog is a language based on first order logic that was investigated as a data model for relational databases in the 1980s. It has recently been used in various new application areas, prompting proposals to run Datalog programs on new platforms such as Graphics Processing Units (GPUs) and MapReduce. Back then and nowadays, interest in Datalog has stemmed from its ability to compute the transitive closure of relations through recursive queries which, in efect, turns relational databases into deductive databases, or knowledge bases. This thesis presents the design, implementation and evaluation of a Datalog engine for GPUs. It is the rst fully functional Datalog engine for GPUs to the best of our knowledge. It consists of: i) a compiler that translates Datalog programs into relational algebra operations (select, various types of joins and project); ii) a scheduler that plans and launches such operations into the GPU from the host platform; iii) the GPU parallel algorithms of such operations; and iv) a memory management scheme that tends to reduce the number of memory transfers between the host and the GPU. It also includes various optimisations that capitalise on the characteristics of the Datalog language and the GPU architecture. Our Datalog engine was developed in C with the Nvidia CUDA software platform. The evaluation of our engine using several queries shows a dramatic performance improvement when compared against the well known Prolog engines XSB and YAP, and the Datalog engine from Mitre Corporation. For two of the queries, a performance increase of up to 200 times was achieved.