University of South Florida
Computing Group-By and Aggregate in Massively Parallel Systems
Abstract
dc:descriptionThe semiconductor industry has mainly exploited two routes for designing microprocessors. The multi-core route aims to speed up the performance of latency-oriented processing. In contrast, the many-thread route concentrates on throughput-oriented improvement of parallel processing. Many-thread microprocessors, such as Graphics Processing Units (GPUs), are leading the computing capability for this past a decade. According to the current hardware market, at the similar price range, the ratio of peak computing power between multi-core CPUs and many-thread GPUs is up to 15X. This large performance gap on data processing has motivated many practitioners in database community to exploit computation-intensive parts on GPU for query execution. Group-By and aggregate operations are very often used together to summarize data, such that data scientists and domain experts could quickly gain analytical insights over possibly massive amounts of data. They are play fundamental and critical roles in data visualization community and contribute large part of the user experience in the interactive visualization analysis. In this research, we investigate the low-level computing features of GPUs, and we exhibit in-depth study of design, implementation, and optimization of Group-By/Aggregate algorithms on GPUs. We primarily focus on the design and implementation of hash-based Group-By/Aggregate algorithms. We then introduce an adaptive and dynamic Radix-hash algorithm, which is insensitive to input cardinality (number of distinct groups). On the other hand, we present a performance model which guides us to pick a set of bits to proceed radix hash for each pass, such that the overall group-by operation could achieve maximum throughput. We also reproduce the-start-of-art hash-base implementation on both modern CPUs and GPUs. Our experiments verify that our adaptive and dynamic algorithm chooses the optimal solution and deliver highest throughput.
Degree
thesis:*- Name thesis:degree_name
- MS in Computer Science (M.S.C.S.)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Computer Science and Engineering
- Grantor
- University of South Florida
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Mou, Chengcheng
- Contributors dc:contributor
-
- Yi-Cheng Tu, Ph.D.
- Paul A. Rosen, Ph.D.
- Srinivas Katkoori, Ph.D.
- Yu Zhang, Ph.D.
- Feng Cheng, Ph.D.
Subjects
dc:subject × 6Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.usf.edu/etd/10331