Back to search

University of South Florida

Algorithms and Framework for Computing 2-body Statistics on Graphics Processing Units

Abstract

dc:description

Various types of two-body statistics (2-BS) are regarded as essential components of low-level data analysis in scientific database systems. In relational algebraic terms, a 2-BS is essentially a Cartesian product between two datasets (or two instances of the same dataset) followed by a user-defined aggregate. The quadratic complexity of these computations hinders the timely processing of data. Thus using modern parallel hardware has become an obvious solution to meet such challenges. This dissertation presents our recent work in designing and optimizing parallel algorithms for 2-BS computation on Graphics Processing Units (GPUs). The unique architecture, however, provides abundant opportunities for optimizing the algorithm towards better performance and achieving high utilization of hardware resources. While a typical 2-BS problem can be summarized into a straightforward parallel computing pattern, traditional knowledge from (general) parallel computing often falls short in delivering the best possible performance. Therefore, we present a suite of techniques to decompose 2-BS problems and methods for the effective use of computing resources on GPUs. We also developed analytical models that guided us towards finding the best parameters of our GPU programs. As a result, we achieve the design of highly-optimized 2-BS algorithms that significantly outperform the best-known GPU and CPU implementations. Although 2-BS problems share the same core computations, each 2-BS problem, however, carries its own characteristics that calls for different strategies in code optimization. For that, we developed a software framework that automatically generates high-performance GPU code based on a few parameters and short primer code inputs. We further present two case studies to demonstrate that code generated by this framework reaches a very high level of efficiency. In addition to the general problem, we also studied a particular group of 2-BS problems, in which the computation can be reduced by using an index structure. Whereas the traditional knowledge of the index tree structure cannot utilize the full performance of GPUs, we present a technique to optimize the index searching for GPUs. The GPU index-searching is verified by applications of 2-BS, which show the very high performance.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (Ph.D.)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science and Engineering
Grantor
University of South Florida
Year dc:date
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pitaksirianan, Napath
Contributors dc:contributor
  • Yicheng Tu, Ph.D.
  • Adriana Iamnitchi, Ph.D.
  • Yao Liu, Ph.D.
  • Hadi Charkhgrad, Ph.D.
  • Sagar Pandit, Ph.D.

Subjects

dc:subject × 7

Identifiers

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

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

Pitaksirianan, Napath. Algorithms and Framework for Computing 2-body Statistics on Graphics Processing Units. Dissertation thesis, University of South Florida, 2020. https://digitalcommons.usf.edu/etd/8984