SC15 Austin, TX

High Level Synthesis of SPARQL Queries

Authors: Marco Minutoli (Pacific Northwest National Laboratory), Vito Giovanni Castellana (Pacific Northwest National Laboratory), Antonino Tumeo (Pacific Northwest National Laboratory)

Abstract: RDF databases naturally map to labeled, directed graphs. SPARQL is a query language for RDF databases that expresses queries as graph pattern matching operations. GEMS is a RDF database that, differently from other solutions, employs graph methods at all levels of its stack. Graph methods are inherently task parallel, but they exhibit an irregular behavior. In this poster we discuss an approach to accelerate GEMS with reconfigurable devices. The proposed approach automatically generates parallel hardware implementations of SPARQL queries using a customized High Level Synthesis (HLS) flow. The flow has been enhanced with solutions to address limitations of graph methods with conventional HLS methods, enhancing TLP extraction and management of concurrent memory operations. We have validated our approach by synthesizing and simulating seven queries from LUBM. We show that that the proposed approach provides an average speed up or 2.1 with respect to the serial version of the hardware accelerators.

Poster: pdf
Two-page extended abstract: pdf

Poster Index