Hardware-acceleration of Semantic Web databases with runtime reconfigurable FPGAs

• Applicants: Professor Dr. Sven Groppe; Professor Dr.-Ing. Thilo Pionteck
• Subject Area: Computer Architecture, Embedded and Massively Parallel Systems ; Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2013 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 241700592

• Final Report Year: 2017

Final Report Abstract

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.

Publications

• Parallel and Pipelined Filter Operator for Hardware-Accelerated Operator Graphs in Semantic Web Databases in: Proceedings of the 14th IEEE International Conference on Computer and Information Technology (CIT 2014), 2014, IEEE, Xi’an, China
  Stefan Werner, Dennis Heinrich, Marc Stelzner, Sven Groppe, Rico Backasch, Thilo Pionteck
  
• Accelerated join evaluation in Semantic Web databases by using FPGAs in: Concurrency and Computation: Practice and Experience, 2015
  Stefan Werner, Dennis Heinrich, Marc Stelzner, Volker Linnemann, Thilo Pionteck, Sven Groppe
  
• An Optimized Radix-Tree for Hardware-Accelerated Dictionary Generation for Semantic Web Databases in: Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig), 2015, IEEE, Cancun, Mexico
  Christopher Blochwitz, Jan Moritz Joseph, Rico Backasch, Stefan Werner, Dennis Heinrich, Sven Groppe, Thilo Pionteck
  
• Hybrid FPGA Approach for a B+ Tree in a Semantic Web Database System in: Proceedings of the 10th International Symposium on Reconfigurable Communication-centric Systemson-Chip (ReCoSoC 2015), 2015, IEEE, Bremen, Germany
  Dennis Heinrich, Stefan Werner, Marc Stelzner, Christopher Blochwitz, Thilo Pionteck, Sven Groppe
  
• PatTrie-Sort - External String Sorting based on Patricia Tries in: Open Journal of Databases (OJDB), 2015, Vol.2, (1), p.36-50
  Sven Groppe, Dennis Heinrich, Stefan Werner, Christopher Blochwitz, Thilo Pionteck
  
• Hardware-accelerated Radix-Tree based string sorting for Big Data applications in: Proceedings of the 30th International Conference of Architecture of Computing Systems (ARCS 2017), 2017, Springer, Vienna, Austria
  Christopher Blochwitz, Julian Wolff, Jan Moritz Joseph, Stefan Werner, Dennis Heinrich, Sven Groppe, Thilo Pionteck