title: Query processing on heterogeneous systems
Creators: name: Rosenfeld, Viktor
Publisher: name: Technische Universität Berlin
Year: 2024
Subjects: subject: 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
subject: heterogeneous query execution
subject: heterogeneous CPU/GPU systems
subject: GPU-accelerated data processing
subject: hash aggregation
subject: user-defined functions
subject: heterogene Anfragebearbeitung
subject: heterogene CPU/GPU-Systeme
subject: GPU-beschleunigte Datenverarbeitung
subject: Hash-Aggregierung
subject: benutzerdefinierte Funktionen

description: Today's computing systems are highly heterogeneous, both in terms of the hardware that they are built from and the software that they run. This heterogeneity provides key benefits, since specialized processors provide the performance necessary to process increasing amounts of data, and specialized software system enable programmers with different needs and expertise to extract knowledge from data. However, the integration of heterogeneous hardware and software into a cohesive system poses many challenges, e.g., how to distribute work among heterogeneous processors, how to reduce the complexity of programming heterogeneous processors, and how to reduce overheads when moving data and computation between different software systems. In this thesis, we investigate how heterogeneous hardware and software impacts query processing, and develop tools to manage this heterogeneity. In our first contribution, we survey query processing systems that target both CPUs and GPUs. We develop a classification scheme to categorize how to distribute query processing tasks on these processors, and review techniques to program CPUs and GPUs in a query processing system, and to overcome the data transfer bottleneck. Our analysis shows that systems with dedicated GPUs require different strategies to distribute the workload than systems with integrated GPUs. In our second contribution, we investigate how a query processing systems can automatically adapt its low-level operator implementation to the processor it runs on. First, we perform an extensive experimental analysis of different implementations of two data processing operators on various CPUs, GPUs, and an Intel Xeon Phi coprocessor. We find that every processor requires specific implementations to achieve high performance, that heuristics derived from the analysis of one processor are not necessarily transferable to others, and that some processors are more difficult to optimize for than others. Then, we develop two algorithms to find a fast operator implementation at runtime, which differ in the amount of information they incorporate during their search. Our evaluation of these algorithms shows that it is necessary to exploit information about processor characteristics to reduce the search time for a fast implementation. In our third contribution, we focus on integrating query processing systems that run on the Java Virtual Machine (JVM) and those that execute native machine code. Concretely, we develop two approaches how to execute Java-based UDFs in a query processing engine written in C++. First, we transparently transform a tuple-based UDF into a UDF that processes an entire batch, which effectively eliminates the overhead of moving execution from the C++ engine into an embedded JVM. This approach works well if the UDF creates many objects, including Java strings. Second, we translate the UDF bytecode to LLVM IR and link it directly with the C++ engine. This approach works well if the UDF is compute-intensive. Our investigation into a variety of heterogeneous hardware and software scenarios shows that we often face similar challenges when integrating them. Thus, the techniques investigated and developed in this thesis constitute effective building blocks to extract performance from today's heterogeneous computing systems.
description: Heutige Computersysteme sind außerordentlich heterogen. Sie bestehen aus vielseitig spezialisierter Hardware und führen unterschiedlichste Softwaresysteme aus. Einerseits bietet diese Heterogenität wesentliche Vorteile, da z.B. spezialisierte Prozessoren die notwendige Leistung für die Verarbeitung wachsender Datenmengen bereitstellen und spezialisierte Softwaresysteme Programmierern mit unterschiedlichen Anforderungen und Fachkenntnissen ermöglichen, Wissen aus Daten zu erschließen. Andererseits birgt die Integration heterogener Hard- und Software aber auch viele Herausforderungen. So stellt sich beispielweise die Frage, wie die Arbeitsteilung zwischen heterogenen Prozessoren erfolgen soll, wie sich die Komplexität der Programmierung heterogener Prozessoren reduzieren lässt und wie der Overhead bei der Übertragung von Daten und der Verteilung von Berechnungen zwischen verschiedenen Softwaresystemen minimiert werden kann. In dieser Arbeit untersuchen wir, wie heterogene Hard- und Software die Anfrageverarbeitung beeinflusst, und entwickeln Werkzeuge, um diese Heterogenität zu bewältigen. Im ersten Beitrag untersuchen wir Systeme, die die Anfrageverarbeitung auf CPUs und GPUs aufteilen. Hierfür entwickeln wir ein Klassifikationsschema, um Strategien zur Verteilung von Teilaufgaben der Anfrageverarbeitung auf diesen Prozessoren zu kategorisieren. Darüber hinaus untersuchen wir Methoden um die Architektur eines Anfragesystems an heterogene Prozessoren anzupassen und um langsame Datentransfers zwischen CPU und GPU zu vermeiden. Unsere Analyse zeigt, dass Systeme mit dedizierten GPUs andere Strategien zur Arbeitsaufteilung erfordern als Systeme mit integrierten GPUs. Im zweiten Beitrag untersuchen wir, wie ein Anfrageverarbeitungssystem die Implementierung von datenverarbeitenden Operatoren automatisch an den Prozessor adaptieren kann, auf dem es ausgeführt wird. Hierfür führen wir zunächst eine umfangreiche experimentelle Analyse verschiedener Implementierungsvarianten für zwei Operatoren auf verschiedenen CPUs, GPUs und einem Intel Xeon Phi Coprozessor durch. Unsere Analyse zeigt, dass jeder Prozessor eine spezifische Implementierung benötigt, um Daten schnell zu verarbeiten. Darüber hinaus stellen wir fest, dass Heuristiken, die aus der Analyse eines bestimmten Prozessors abgeleitet wurden, nicht unbedingt auf andere Prozessoren übertragbar sind und dass einige Prozessoren schwieriger zu optimieren sind als andere. Anschließend entwickeln wir zwei Algorithmen, die es einem Anfragesystem ermöglichen, automatisch eine schnelle Operatorimplementierung zu finden. Die Algorithmen unterscheiden sich in der Art der Informationen, die sie bei der Suche berücksichtigen. Unsere Auswertung dieser Algorithmen zeigt, dass es notwendig ist, Informationen über die Eigenschaften des Prozessors zu berücksichtigen, um die Suchzeit für eine schnelle Implementierung zu reduzieren. Im dritten Beitrag befassen wir uns mit der Integration von Anfrageverarbeitungssystemen, die auf der Java Virtual Machine laufen, und solchen, die nativen Maschinencode ausführen. Konkret entwickeln wir zwei Ansätze, um Java-basierte UDF auf einem in C++ geschriebenen Anfrageverarbeitungssystem auszuführen. Im ersten Ansatz wandeln wir eine UDF, die für jedes Tupel ausgeführt wird, in eine UDF um, die einen Block von Tupel verarbeitet, wodurch der Kontextwechsel-Overhead zwischen der Ausführung von C++-Code und der UDF eliminiert wird. Dieser Ansatz funktioniert gut für UDFs, die viele Objekte erzeugen, einschließlich Java-Strings. Im zweiten Ansatz übersetzen wir die Java UDF in Maschinencode und führen sie direkt im C++ Anfragebearbeitungssystem aus. Dieser Ansatz funktioniert gut für rechenintensive UDFs. Unsere Untersuchung einer Reihe von Szenarien heterogener Hard- und Software zeigt, dass wir bei der Integration dieser Systeme oft vor ähnlichen Herausforderungen stehen. Somit stellen die in dieser Arbeit erarbeiteten Methoden wirksame Bausteine dar, um die Leistungsfähigkeit heutiger heterogener Rechensysteme auszunutzen.