Virginia Tech
On the Efficient Mapping and Optimization of Irregular Workloads for Graphics Processing Units
Abstract
dc:description.abstractIrregular 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 × 8Rights
dc:rights- Statement dc:rights
-
- Creative Commons Attribution-NonCommercial 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Other
- vt_gsexam:47813