Back to search

University of South Florida

Computing Group-By and Aggregate in Massively Parallel Systems

Abstract

dc:description

The 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 × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/10331

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Mou, Chengcheng. Computing Group-By and Aggregate in Massively Parallel Systems. Thesis thesis, University of South Florida, 2022. https://digitalcommons.usf.edu/etd/10331