Hardware-acceleration of Semantic Web databases with runtime reconfigurable FPGAs

The relevance of the Semantic Web has been increased steadily over the recent years. This can be shown by the increasing number of developed and used Semantic Web tools and applications.The main idea of the Semantic Web is to consider the semantic of symbols to enable a more precise machine processing. For this purpose, the necessary links between data sets are stored in database systems. The continuously increasing size of the data sets leads to performance issues for traditional databases and even specialized Semantic Web databases. In the scope of Semantic Web databases data sets with billions of entries are available and processing of these data sets on software-based solutions is highly time consuming.Thus, in this project a hardware/software system will be investigated and developed to outsource time consuming tasks to a programmable logic chip (FPGA, Field Programmable Gate Array). The hardware acceleration of cost intensive tasks will cover the index generation as well as query processing in Semantic Web databases. During query processing the determination of which function should be mapped to the FPGA will be decided at runtime. As the mapping of the data path to the basic elements uses partial runtime reconfiguration, an optimal hardware accelerator can be provided for any query.

Das Projekt "Hardwarebeschleunigung von Semantic Web Datenbanken durch dynamisch rekonfigurierbare FPGAs" ist eine gemeinschaftliche Arbeit der AG Groppe (Universität zu Lübeck) und AG Pionteck (zur Projektlaufzeit Universität zu Lübeck, nun Universität Magdeburg). Im Rahmen dieser Projektarbeit wurden Semantic Web Datenbanksysteme im Themenfeld von Big Data Szenarien beschleunigt. Hierfür wurden hybride Datenbankserver verwendet, die neben ihrer sequentiellen Softwareverarbeitung auch eine parallele hardwareseitige Verarbeitung auf einem FPGA unterstützen. Dieser ist zur Laufzeit rekonfigurierbar, sodass die Funktion des FPGAs im System dynamisch an die momentanen Aufgaben angepasst werden kann. Für die Indexerstellungen wurden verschiedene hardwareoptimierte Datenstrukturen entwickelt: Patricia Trie für die alphabetische Sortierung von Tripeln, B+-Baum und Triplestore als Indexstruktur. Hierbei waren die hardwareoptimierten Processing-Elemente in den meisten Fällen schneller als eine reine Softwareimplementierung. Mit Hilfe von parallel arbeitenden Processing-Einheiten konnte der Speed-Up weiter erhöht werden. Abschließend wurden verschiedene Systeme entwickelt, welche eine Anfrageverarbeitung auf einem FPGA ausführen. Ziel war es, einen Operatorgraphen zur Laufzeit dynamisch auf einen FPGA abzubilden. Hierfür wurden zu Beginn verschiedene Datenbankoperatoren in Hardware implementiert und evaluiert. Die Join Operatoren können beispielsweise eine Beschleunigung von bis zu Faktor 10 aufweisen, wobei unterschiedliche Implementierungen, wie Nested Loop Join, Merge Join und die symmetrische und asymmetrische Variante des Hash Joins betrachtet wurden. Filteroperatoren wurden ebenfalls in zwei Implementierungen, einer parallelen und einer gepipelined Version, umgesetzt. Diese haben eine vergleichbare Ausführungszeit und erreichen einen Speed-Up von bis zu Faktor 5 gegenüber der Software-Verarbeitung. Dabei wurde ein Durchsatz von 100 Millionen Elementen pro Sekunde erreicht. Im nächsten Schritt wurden die Operatoren zur Synthesezeit miteinander verknüpft und auf dem FPGA ausgeführt, wobei ein Speed-Up von Faktor 10 und mehr erreicht werden konnte. Als nächster Evolutionsschritt wurden die Operatoren einzeln rekonfiguriert und mit Hilfe eines Network-on-Chips mit einander verbunden. Hier war es ein weiteres Mal möglich, Anfragen auf einen Faktor 25 im Vergleich zu der Softwareimplementierung, zu beschleunigen.