Scalable data management using GPUs with fast interconnects
| dc.contributor.advisor | Markl, Volker | |
| dc.contributor.author | Lutz, Clemens | |
| dc.contributor.grantor | Technische Universität Berlin | |
| dc.contributor.referee | Markl, Volker | |
| dc.contributor.referee | Ailamaki, Anastasia | |
| dc.contributor.referee | Manegold, Stefan | |
| dc.contributor.referee | Rabl, Tilmann | |
| dc.date.accepted | 2022-11-10 | |
| dc.date.accessioned | 2022-12-14T14:02:38Z | |
| dc.date.available | 2022-12-14T14:02:38Z | |
| dc.date.issued | 2022 | |
| dc.description.abstract | Modern database management systems (DBMSs) are tasked with analyzing terabytes of data, employing a rich set of relational and machine learning operators. To process data at large scales, research efforts have strived to leverage the high computational throughput and memory bandwidth of specialized co-processors such as graphics processing units (GPUs). However, scaling data management on GPUs is challenging because (1) the on-board memory of GPUs has too little capacity for storing large data volumes, while (2) the interconnect bandwidth is not sufficient for ad hoc transfers from main memory. Thus, data management on GPUs is limited by a data transfer bottleneck. In practice, CPUs process large-scale data faster than GPUs, reducing the utility of GPUs for DBMSs. In this thesis, we investigate how a new class of fast interconnects can address the data transfer bottleneck and scale GPU-enabled data management. Fast interconnects link GPU co-processors to a CPU with high bandwidth and cache-coherence. We apply our insights to process stateful and iterative algorithms out-of-core by the examples of a hash join and k-means clustering. We first analyze the hardware properties. Our experiments show that the high interconnect bandwidth enables the GPU to efficiently process large data sets stored in main memory. Furthermore, cache-coherence facilitates new DBMS designs that tightly integrate CPU and GPU via shared data structures and pageable memory allocations. However, irregular accesses from the GPU to main memory are not efficient. Thus, the operator state of, e.g., joins does not scale beyond the GPU memory capacity. We scale joins to a large state by contributing our new Triton join algorithm. Our main insight is that fast interconnects enable GPUs to efficiently spill the join state by partitioning data out-of-core. Thus, our Triton join breaks through the GPU memory capacity limit and increases throughput by up to 2.5× compared to a radix-partitioned join on the CPU. We scale k-means to large data sets by eliminating two key sources of overhead. In existing strategies, execution crosses from the GPU to the CPU on each iteration, which results in the cross-processing and multi-pass problems. In contrast, our solution requires only a single data pass per iteration and speeds-up throughput by up to 20×. Overall, GPU-enabled DBMSs are able to overcome the data transfer bottleneck by employing new out-of-core algorithms that take advantage of fast interconnects. | en |
| dc.description.abstract | Moderne Datenbankverwaltungssysteme (DBMS) werden verwendet um Terabytes von Daten zu analysieren, wobei eine Vielzahl von relationalen und maschinell lernenden Operatoren eingesetzt werden. Um Daten in großen Massen zu verarbeiten, strebten Forschungsversuche an, den hohen Rechendurchsatz und Speicherbandbreite von spezialisierten Coprozessoren wie beispielsweise Grafikprozessoren (GPUs) zu nutzen. Jedoch stellt die Skalierung der Datenverwaltung auf GPUs eine Herausforderung dar, weil (1) der integrierte Speicher von GPUs zu wenig Kapazität für die Speicherung großer Datenmengen hat, wohingegen (2) die Bandbreite des Interconnects nicht für eine Ad-hoc-Übertragung aus dem Hauptspeicher ausreicht. Somit ist die Datenverwaltung auf GPUs durch einen Datentransfer-Engpass begrenzt. In der Praxis verarbeiten daher Hauptprozessoren (CPUs) große Datenmengen schneller als GPUs, was die Nützlichkeit von GPUs für DBMSs verringert. In dieser Dissertation untersuchen wir, wie eine neue Klasse von schnellen Interconnects den Datentransfer-Engpass beheben und die GPU-gestützte Datenverwaltung skalieren kann. Schnelle Interconnects verbinden GPU-Coprozessoren zu einer CPU mit hoher Bandbreite und Cache-Kohärenz. Wir wenden unsere Erkenntnisse an, um zustandsbehaftete und iterative Algorithmen aus dem Coprozessor ausgelagert zu verarbeiten, beispielshalber an einem Hash Join und an dem k-Means Clustering-Verfahren. Wir analysieren zunächst die Hardware-Eigenschaften. Unsere Experimente zeigen, dass die hohe Transferbandbreite der GPU ermöglicht, große, im Hauptspeicher gespeicherte Datensätze effizient zu verarbeiten. Zudem fördert die Cache-Kohärenz neue DBMS-Designs, welche die CPU und die GPU über gemeinsam genutzte Datenstrukturen und auslagerbare Speicherallokationen eng integrieren. Allerdings sind ungleich verteilte Zugriffe von der GPU aus auf den Hauptspeicher nicht effizient. Deshalb lässt sich der Operator-Zustand von z.B. Joins nicht über die Speicherkapazität der GPU hinaus skalieren. Wir skalieren Joins auf einen großen Zustand, indem wir unseren neuen Triton Join-Algorithmus einführen. Unsere wichtigste Erkenntnis ist, dass schnelle Interconnects GPUs befähigen, den Join-Zustand durch ein externes Datenpartitionierungverfahren effizient auszulagern. Somit durchbricht unser Triton Join die durch die GPU-Speicherkapazität gegebene Begrenzung und steigert den Durchsatz um bis zu dem 2,5-fachen im Vergleich zu einem Radix-partitionierten Join auf der CPU. Wir skalieren k-Means auf große Datensätze, indem wir zwei Hauptlimitationen beseitigen. Bei bestehenden Strategien wechselt die Ausführung bei jeder Iteration zwischen der GPU und der CPU hin und her, was zu den Cross-Processing- und Multi-Pass-Problemen führt. Im Gegensatz dazu erfordert unsere Lösung nur einen einzigen Datendurchlauf pro Iteration und beschleunigt den Durchsatz um bis zu 20 Mal. Insgesamt sind GPU-gestützte DBMSs in der Lage, den Datentransfer-Engpass zu überwinden, indem sie neue, Zustands-auslagerbare Algorithmen einsetzen, die die Vorteile schneller Interconnects ausnutzen. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/17803 | |
| dc.identifier.uri | https://doi.org/10.14279/depositonce-16592 | |
| dc.language.iso | en | |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
| dc.subject.ddc | 004 Datenverarbeitung; Informatik | de |
| dc.subject.ddc | 003 Systeme | de |
| dc.subject.other | GPU-accelerated data processing | en |
| dc.subject.other | relational database | en |
| dc.subject.other | single-pass k-means | en |
| dc.subject.other | data transfer bottleneck | en |
| dc.subject.other | translation lookaside buffer (TLB) | en |
| dc.subject.other | relationale Datenbank | de |
| dc.subject.other | GPU-beschleunigte Datenverarbeitung | de |
| dc.subject.other | Datentransfer-Engpass | de |
| dc.subject.other | Datentransfer-Flaschenhals | de |
| dc.subject.other | relationaler Join | de |
| dc.title | Scalable data management using GPUs with fast interconnects | en |
| dc.title.translated | Skalierbares Datenmanagement auf GPUs mit schnellen Interconnects | de |
| dc.type | Doctoral Thesis | |
| dc.type.version | acceptedVersion | |
| tub.accessrights.dnb | free | |
| tub.affiliation | Fak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatik::FG Datenbanksysteme und Informationsmanagement (DIMA) | |
| tub.publisher.universityorinstitution | Technische Universität Berlin |