Near-Data Query Processing on Heterogeneous FPGA-based Systems

Language
en
Document Type
Doctoral Thesis
Issue Date
2022-04-25
Issue Year
2022
Authors
Becher, Andreas
Editor
Abstract

Query processing is a traditional yet still ongoing field of research. Its significance is derived from the increase of data created and processed every day and the opportunities provided by the analysis of the data. In today’s world, complete businesses are built on top of sophisticated data processing capabilities. However, with the increase of data, processing these huge amounts of data becomes more and more challenging. This is not only because of the time and resources it takes to process such amounts of data but also due to the energy costs. Consequently, researchers broadened the range of processing architectures to investigate for query processing beyond traditional processor-based systems. Next to programmable graphic processing units (GPUs), field programmable gate arrays (FPGAs) have become of great interest due to their unique features. FPGAs not only allow for the construction of highly optimized hardware circuits for specific tasks but also enable the adaption of hardware to the tasks during runtime. Hence, many researchers have presented various proposals to exploit the features provided by FPGAs. Although the proposed systems can achieve high throughput and efficiency in general, they are often not able to accelerate queries that haven’t been considered during their design. Performance and efficiency can only be gained best through specialization, and thus, a system should adapt to an incoming and unknown query. This is possible with FPGAs due to their ability to be reconfigured fully or in parts during runtime. However, this comes at the cost of high startup times as the FPGA has to be configured according to the query prior to the execution of the query. Furthermore, it is almost impossible to generate hardware configurations for every possible query. This thesis introduces an innovative FPGA-based near-data processing system able to process a wide variety of queries at I/O-rate (line-rate). It is based on reconfigurable and parametrizable accelerators. The accelerators are composed of parametrizable modules within a library. These modules do not only implement a specific operator for a specific type but are optimized to implement operators for multiple types or even multiple functions without a drastic increase of resources. Another contribution of this thesis is the concept of optimistic query processing for demanding operators such as the join and regular matching operator. It is based on the idea to approximately filter as much data as possible in hardware without removing tuples that should be kept. The resulting, often reduced, intermediate table is guaranteed to be a superset of the accurate filter operation. A software-based operator implementation can then be applied on an intermediate table with less tuples to finalize the operation. As an example, the implementation of a module for regular expression matching is presented. Equipped with a parameter sequencer, accelerators assembled from this library are able to implement a greater variety of queries by setting the parameters of the modules according to the query to process. However, the schema which the tables are stored in also influences the design of the accelerator and, therefore, may limit the types of queries it can implement. For this, a hardware unit called ReOrder is introduced. It decouples the table schema and storage layout from the accelerator enabling all accelerators to be used on every table with row-oriented and column-oriented storage layouts. Even though the developed accelerators are able to implement a wide variety of queries, no one-fits-all accelerator is possible. Consequently, the system is designed to concatenate multiple partially reconfigurable (i.e., exchangeable) accelerators without a decrease in tuple throughput. This increases the types of queries that can be processed even further. As accelerators might not use all available resources within a partially reconfigurable FPGA region, the idea of in situ statistics generation is proposed. In situ statistics modules can utilize the free resources to gather information on the table that is processed by an accelerator without additional costs in terms of time. Complementary to the hardware related parts already mentioned, a control software managing the execution of a query on such a system is presented as well. Starting from the basic components needed to execute queries on the platform, the description goes into depth on the particularities of such a FPGA-based query execution system. Especially the query placement problem which describes the problem of finding a query-specific-configuration of the system’s hardware according to an incoming query is formulated. In addition, the challenges to obtain an optimal placement is discussed and exemplified using the problem of buffer assignment. Afterwards, the parameters of the modules have to be generated. In this regard, an algorithm to obtain the parameters for a ReOrder unit is presented and evaluated in depth. Additionally, considerations about parameter generators for a histogram module and the optimistic regular expression matching module are provided. Finally, an implemented prototype of the system called ReProVide unit has been evaluated. It is able to provide I/O-rate processing of simple as well as complex queries. Compared to a software-based in-memory database system executed on an ARM processor, queries could be executed 19.9× faster on the prototype on average. When executed on an x86 processor, comparable execution times have been observed. This means the prototype system storing the tables on two solid states drives was able to process queries as fast as an x86 system holding the tables in memory. Furthermore, the prototype built is shown to be very energy-efficient, consuming only less than 25% of the energy consumed by the x86 system on average.

Abstract

Die Verarbeitung von Datenbankanfragen ist ein seit langem bekanntes jedoch stets aktuelles Forschungsgebiet. Die Bedeutung ergibt sich aus der Zunahme der täglich erstellten und verarbeiteten Menge an Daten und den Möglichkeiten, die sich aus der Analyse dieser ergeben. Heutzutage existieren Unternehmen, deren ganzes Geschäftsmodell auf der Verarbeitung von riesigen Datenmengen basiert. Mit der Zunahme der Daten wird die Verarbeitung dieser riesigen Datenmengen jedoch immer schwieriger. Dies liegt nicht nur an der Zeit und den Ressourcen, die für die Verarbeitung solcher Datenmengen erforderlich ist, sondern auch an den Energiekosten die dabei entstehen. Infolgedessen untersuchen Forscher, welche Alternativen es zu der Verarbeitung auf bereits bestehenden Computersystemen gibt. Neben programmierbaren Grafikprozessoren (GPUs) sind vor allem Field Programmable Gate-Arrays (FPGAs) aufgrund ihrer einzigartigen Eigenschaften in den Fokus der Forschung gerückt. FPGAs ermöglichen nicht nur den Aufbau hochoptimierter Hardwareschaltungen für bestimmte Aufgaben, sondern auch die Anpassung der Hardware an die Aufgaben zur Laufzeit. Obwohl die von Forschern bereits vorgeschlagenen Systeme einen hohen Durchsatz und eine hohe Effizienz erzielen können, sind sie häufig nicht in der Lage, beliebige Abfragen zu beschleunigen. Dies liegt daran, dass Eigenschaften wie Verarbeitungsgeschwindigkeit und Effizienz durch die Spezialisierung erzielt werden. Spezialisierungen schränken jedoch häufig die Fähigkeit eines Systems ein, sich an noch unbekannte Abfragen anzupassen. Um diesem Problem entgegenzuwirken, wird die Fähigkeit von FPGAs genutzt, die gesamte Schaltung oder Teile davon während der Laufzeit neu zu konfigurieren. Dies sorgt jedoch für eine gewisse Latenz bei der Ausführung, da der FPGA zuvor entsprechend der Anfrage konfiguriert werden muss. Speziell für Datenbankanfragen ist es darüber hinaus nahezu unmöglich Hardwarekonfigurationen für alle möglichen Anfragen, die ausgeführt werden sollen, zu generieren. In dieser Arbeit wird ein innovatives datennahes (near-data) Verarbeitungssystem vorgestellt, das eine Vielzahl von Anfragen mit IO-Rate (Line-Rate) verarbeiten kann. Es basiert auf rekonfigurierbaren und parametrierbaren Beschleunigern. Dabei besteht jeder Beschleuniger aus unterschiedlichen parametrierbaren Modulen, welche in einer Bibliothek hinterlegt sind. Diese Module implementieren nicht nur einen bestimmten Operator für einen bestimmten Datentyp, sondern versuchen mehrere Typen oder sogar mehrere Operationen zu implementieren, ohne dass die Ressourcen, die hierfür benötigt werden, drastisch anwachsen. Darüber hinaus werden spezielle Module bereitgestellt, welche auch komplexere Operatoren, wie etwa den Join-Operator oder den Operator um reguläre Ausdrücke auszuwerten, beschleunigen können. Zusammen mit einem Parametersequenzer können aus Modulen aus dieser Bibliothek Beschleuniger erstellt werden, welche eine größere Menge an Abfragen implementieren, indem sie die Parameter der genutzten Module entsprechend der geforderten Abfrage bereitstellen. Jedoch beinflusst das Schema einer Tabelle auch das Design der Beschleuniger und begrenzt somit die Anzahl der ausführbaren Abfragen. Um dem entgegenzuwirken wird die ReOrder-Einheit eingeführt. Sie entkoppelt das Tabellenschema und die Art und Weise, wie eine Tabelle gespeichert wird, von dem erwarteten Datenformat eines Beschleunigers. Damit ermöglicht die ReOrder-Einheit die Verwendung aller Beschleuniger ungeachtet der Eigenschaften einer im Speicher abgelegten Tabelle. Obwohl die entwickelten Beschleuniger eine Vielzahl von Abfragen implementieren können, ist es nicht möglich, einen einzigen Beschleuniger zu konstruieren, der jede mögliche Anfrage auf jede mögliche Tabelle ausführen kann. Folglich ist das System so ausgelegt, dass es mehrere partiell rekonfigurierbare (d. h. Austauschbare) Beschleuniger in Reihe schalten kann, ohne den Datendurchsatz zu verringern. Dies kann die Anzahl der Anfragen, die verarbeitet werden können, zusätzlich erhöhen. Viele partiell rekonfigurierbare Beschleuniger können jedoch meist nicht die ihnen zur Verfügung gestellte Fläche gänzlich ausnutzen. Um die in der partiell rekonfigurierbaren Fläche vorhandenen, aber vom Beschleuniger ungenutzten Ressourcen trotzdem sinnvoll verwenden zu können, werden sogenannte In-situ-Statistikmodule vorgeschlagen. Diese Module können genutzt werden, um mithilfe freier Ressourcen Informationen über eine zu verarbeitende Tabelle zu sammeln, ohne dabei eine höhere Laufzeit des Beschleunigers zu verursachen. Ergänzend zu den bereits erwähnten hardwarebezogenen Teilen wird auch die oftware vorgestellt, die zum Ausführen einer Abfrage auf einem solchen System erforderlich ist. Ausgehend von den grundlegenden Komponenten, die zur Nutzung der Plattform erforderlich sind, werden die Besonderheiten eines solchen Systems ausführlich beschrieben. Insbesondere wird das Problem der Platzierung von Abfragen formuliert, das darin besteht, eine abfragespezifische Konfiguration der Systemhardware gemäß einer eingehenden Abfrage zu finden. Darüber hinaus werden die Herausforderungen zur Erzielung einer optimalen Platzierung anhand der Auswahl von Puffermöglichkeiten diskutiert und veranschaulicht. Eine weitere wichtige Aufgabe ist die Erzeugung der Parameter, die für die Beschleuniger notwendig sind. In diesem Zusammenhang wird der Algorithmus zum Erzeugen der Parameter für die ReOrder-Einheit vorgestellt und die Qualität der erzeugten Parameter untersucht. Darüber hinaus werden Überlegungen zu Parametergeneratoren für ein Histogrammmodul und das Modul zur Anpassung regulärer Ausdrücke bereitgestellt. Außerdem wird ein implementierter Prototyp beschrieben und evaluiert. Er ist in der Lage, einfache und komplexe Abfragen mit der maximalen Datenrate, die von angeschlossenen Solid-State-Laufwerken bereit gestellt wird, zu verarbeiten. Im Vergleich zu einem softwarebasierten In-Memory-Datenbanksystem, das auf einem ARM-Prozessor ausgeführt wird, wurden Abfragen für den Prototyp im Durchschnitt 19,9-mal schneller ausgewertet. Bei der Ausführung auf einem x86-Prozessor wurden mit dem Prototyp vergleichbare Ausführungszeiten beobachtet. Dies bedeutet, dass das Prototypsystem, in dem die Tabellen auf zwei Solid-State-Laufwerken gespeichert sind, Abfragen so schnell verarbeiten konnte wie ein x86-System, welches die Tabellen im Hauptspeicher vorhält. Der Prototyp benötigte darüber hinaus nur etwa 25% der vom x86-System benötigten Energie.

DOI
Faculties & Collections
Zugehörige ORCIDs