RMG Sort: Radix-Partitioning-Based Multi-GPU Sorting
| dc.contributor.author | Ilic, Ivan | |
| dc.contributor.author | Tolovski, Ilin | |
| dc.contributor.author | Rabl, Tilmann | |
| dc.contributor.editor | König-Ries, Birgitta | |
| dc.contributor.editor | Scherzinger, Stefanie | |
| dc.contributor.editor | Lehner, Wolfgang | |
| dc.contributor.editor | Vossen, Gottfried | |
| dc.date.accessioned | 2023-02-23T13:59:47Z | |
| dc.date.available | 2023-02-23T13:59:47Z | |
| dc.date.issued | 2023 | |
| dc.description.abstract | In recent years, graphics processing units (GPUs) emerged as database accelerators due to their massive parallelism and high-bandwidth memory. Sorting is a core database operation with many applications, such as output ordering, index creation, grouping, and sort-merge joins. Many single-GPU sorting algorithms have been shown to outperform highly parallel CPU algorithms. Today's systems include multiple GPUs with direct high-bandwidth peer-to-peer (P2P) interconnects. However, previous multi-GPU sorting algorithms do not efficiently harness the P2P transfer capability of modern interconnects, such as NVLink and NVSwitch.In this paper, we propose RMG sort, a novel radix partitioning-based multi-GPU sorting algorithm. We present a most-significant-bit partitioning strategy that efficiently utilizes high-speed P2P interconnects while reducing inter-GPU communication. Independent of the number of GPUs, we exchange radix partitions between the GPUs in one all-to-all P2P swap. We evaluate RMG sort on two modern multi-GPU systems. Our experiments show that RMG sort scales well with the number of GPUs and outperforms a parallel CPU-based sort by up to 20x. Compared to two state-of-the-art merge-based multi-GPU sorting algorithms, we achieve speedups of up to 1.3x and 1.8x across both systems. | en |
| dc.identifier.doi | 10.18420/BTW2023-15 | |
| dc.identifier.isbn | 978-3-88579-725-8 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/40319 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik e.V. | |
| dc.relation.ispartof | BTW 2023 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-331 | |
| dc.subject | Multi-GPU sorting | |
| dc.subject | radix partitioning | |
| dc.subject | high-speed interconnects | |
| dc.subject | database acceleration | |
| dc.title | RMG Sort: Radix-Partitioning-Based Multi-GPU Sorting | en |
| dc.type | Text/Conference Paper | |
| gi.citation.endPage | 328 | |
| gi.citation.publisherPlace | Bonn | |
| gi.citation.startPage | 305 | |
| gi.conference.date | 06.-10. März 2023 | |
| gi.conference.location | Dresden, Germany |
Dateien
Originalbündel
1 - 1 von 1