University of Illinois Urbana-Champaign

Hierarchical sparse computations and communications for solving inverse problems on supercomputers with multi-GPU nodes

Hidayetoglu, Mert

Content Files
HIDAYETOGLU-DISSERTATION-2022.pdf

Permalink

https://hdl.handle.net/2142/115942

Description

Title
Hierarchical sparse computations and communications for solving inverse problems on supercomputers with multi-GPU nodes
Author(s)
Hidayetoglu, Mert
Issue Date
2022-07-15
Director of Research (if dissertation) or Advisor (if thesis)
Hwu, Wen-mei
Doctoral Committee Chair(s)
Hwu, Wen-mei
Committee Member(s)
  • Chew, Weng Cho
  • Oelze, Michael
  • Gropp, Bill
  • Kloeckner, Andreas
Department of Study
Electrical & Computer Eng
Discipline
Electrical & Computer Engr
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
  • Inverse Problems
  • Parallel Computing
  • Inverse Scattering
  • Computational Imaging
  • Sparse Matrix Multiplication (SpMM)
  • GPU, Exascale Computing
Abstract
Solving large-scale inverse problems often incurs immense computational cost, mainly because it has high computational complexity and/or involves sparse computations. This dissertation starts with proposing fast and efficient algorithms to parallelize and accelerate solutions to inverse problems in imaging applications that involve inverse multiple-scattering tomography (mathematically nonlinear) and 3D X-ray image reconstruction (linear). Based on the insights gained from these applications, this thesis generalizes the application-specific optimizations to support a large class of sparse computations and communications at large scale. Sparse computations are investigated in the sparse matrix multiplication (SpMM) context. Prior work has shown that the performance of naive SpMM implementations is bounded by memory bandwidth. We propose, implement, and evaluate novel tiling techniques that transform the sparse matrix and use of on-chip memory and registers to improve the effective data access bandwidth and thus drastically elevate the computation throughput of SpMM on GPUs. We suggest an analytical performance model that provides insight about performance implications that accounts for the algorithmic patterns of accessing the application data (i.e., sparse matrix) and the architecturally specified behaviours of the underlying platform (i.e., GPU architecture). Using this model, we show that the achieved performance of our proposed tiling techniques indeed approaches the theoretical limit allowed by memory bandwidth for many application cases. However, there are a significant number of matrices where there is a large gap between the measured performance and that predicted by the bandwidth factors. With the guidance of the proposed model, this thesis shows load balancing and sparse matrix permutation techniques for improving the arithmetic intensity of SpMM and hence the overall performance. Often at large scale, the matrices in SpMM do not fit into a single GPU, and therefore they have to be partitioned into multiple GPUs. We investigate the hypergraph partitioning models in the context of SpMM, and propose optimization of sparse communications (i.e., hierarchical communications) on multi-GPU nodes. As a result of this study, this thesis presents a sparse communication tool, SpComm, which provides generalized primitives to implement hierarchical communications on generalized scenarios. In this thesis, we provide reproducible artifacts with extensive benchmarking on various GPU architectures, communication topologies, and mixed precisions along with application codes and open-source generalized software tools. As a result, the techniques in this thesis can be applied for solving a broad class of large-scale inverse (and forward) problems using the upcoming exascale GPU computers.
Graduation Semester
2022-08
Type of Resource
Thesis
Handle URL
https://hdl.handle.net/2142/115942
Copyright and License Information
Copyright 2022 Mert Hidayetoglu

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois