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

Hidayetoglu, Mert

Permalink

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

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

Copyright and License Information

Copyright 2022 Mert Hidayetoglu

Owning Collections