high performance computing on graphics processing units: hgpu.org

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.