Back to search

Virginia Tech

On the Efficient Mapping and Optimization of Irregular Workloads for Graphics Processing Units

Abstract

dc:description.abstract

Irregular workloads, characterized by input-dependent memory accesses, control flow, and work distribution, are difficult to map efficiently to GPUs, as they exhibit poor data locality and workload imbalance. Some irregular workloads are limited by long, input-dependent chains of data dependencies despite nearly balanced work distribution, whereas others have independent operations but exhibit extreme per-thread workload variation. Consequently, there is no one-size-fits-all solution for efficiently mapping irregular computations to GPUs. To efficiently map such contrasting irregular computations to GPUs, this work presents two complementary approaches: (1) design adaptation through fine-grained domain decomposition to expose additional parallelism and (2) runtime adaptation through sparsity-aware kernel selection to select an appropriate parallelization strategy based on the sparsity pattern of the input. On an NVIDIA H100 GPU, design adaptations applied to sparse triangular solves and runtime adaptations applied to irregular set intersections deliver mean speedups of 4.6× and 1.6×, respectively, over state-of-the-art GPU implementations. Beyond the evaluation of the performance gains achieved through design and runtime adaptations, this dissertation quantifies developer productivity, performance portability across GPU architectures, and power consumption for the irregular workloads to which the adaptations are applied. In recent years, power has become a first-order constraint in large-scale HPC systems. We present workload-aware GPU power-capping approaches that predict the GPU power cap that maximizes performance/watt, delivering a mean improvement of 1.2× in energy efficiency relative to operation at the maximum supported power cap.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Engineering
Department dc:contributor.department
Electrical and Computer Engineering
Grantor dc:publisher
Virginia Tech
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gondhalekar, Atharva Madhav
Chair dc:contributor.committeechair
  • Feng, Wu-Chun
Committee members dc:contributor.committeemember
  • Hsiao, Michael S.
  • Haugen, Kjetil
  • Jian, Xun
  • Xiong, Wenjie

Subjects

dc:subject × 8

Rights

dc:rights
Statement dc:rights
  • Creative Commons Attribution-NonCommercial 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Other
vt_gsexam:47813

Chain of custody

source
Harvested from
Virginia Tech
Base URL
vtechworks.lib.vt.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Gondhalekar, Atharva Madhav. On the Efficient Mapping and Optimization of Irregular Workloads for Graphics Processing Units. doctoral thesis, Virginia Tech, 2026. https://hdl.handle.net/10919/144001