Hardwarebeschleunigung von Semantic Web Datenbanken durch dynamisch rekonfigurierbare FPGAs

Die Bedeutung des Semantic Webs hat in den vergangenen Jahren stetig zugenommen. Belege hierfür sind unter anderem die steigende Anzahl von entwickelten und im Einsatz befindlichen Semantic Web Tools und Applikationen.Die Kernidee des Semantic Webs ist es, durch Einbeziehung der Bedeutung von Symbolen die maschinelle Verarbeitung zu präzisieren. Die dafür benötigte Verknüpfung unterschiedlicher Datensätze erfolgt mittels Datenbanksystemen. Mit dem stetig wachsenden Umfang von Datenbanken geraten klassische Datenbanksysteme, aber auch speziell angepasste Semantic Web Datenbanksysteme zunehmend an ihre Grenzen. Gerade im Bereich der Semantic Web Datenbanken existieren mittlerweile Datensätze mit Milliarden von Einträgen, deren Bearbeitung mit rein softwarebasierten Lösungen sehr zeitintensiv ist.Im Rahmen dieses Projektes soll daher ein Hardware-/Softwaresystem erforscht und entwickelt werden, welches zeitintensive Operationen auf einen programmierbaren Logikbaustein (FPGA, Field Programmable Gate Array) auslagert. Die für eine Hardwarebeschleunigung vorgesehenen kostenintensiven Operationen umfassen dabei sowohl die einzelnen Schritte der Indexerstellung als auch die eigentliche Anfrageverarbeitung für Semantic Web Datenbanken. Die Festlegung der bei der Anfrageverarbeitung auf das FPGA auszulagernden Funktionen erfolgt zur Laufzeit. Um je nach Anfrage einen optimalen Hardwarebeschleuniger bereitstellen zu können, werden mittels partieller dynamischer Rekonfiguration des FPGAs zur Laufzeit entsprechende Datenpfade aus Grundelementen aufgebaut.

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.