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

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Hidayetoglu, Mert

Contributors dc:contributor

• Hwu, Wen-mei
• Chew, Weng Cho
• Oelze, Michael
• Gropp, Bill
• Kloeckner, Andreas

• Inverse Problems
• Parallel Computing
• Inverse Scattering
• Computational Imaging
• Sparse Matrix Multiplication (SpMM)
• GPU
• Exascale Computing

Statement dc:rights

• Copyright 2022 Mert Hidayetoglu

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F115942