{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/115942"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/115942","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Hierarchical sparse computations and communications for solving inverse problems on supercomputers with multi-GPU nodes","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-08-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-08-01","abstract_has_math":false,"creators":["Hidayetoglu, Mert"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Hwu, Wen-mei","Chew, Weng Cho","Oelze, Michael","Gropp, Bill","Kloeckner, Andreas"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-08","date_published":"2022-08","updated_at":"2026-07-22T22:24:55Z","subjects":["Inverse Problems","Parallel Computing","Inverse Scattering","Computational Imaging","Sparse Matrix Multiplication (SpMM)","GPU","Exascale Computing"],"languages":["en","eng"],"rights":["Copyright 2022 Mert Hidayetoglu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/115942","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hwu, Wen-mei","Chew, Weng Cho","Oelze, Michael","Gropp, Bill","Kloeckner, Andreas"]},{"key":"dc:creator","label":"Author","values":["Hidayetoglu, Mert"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-08","2022-07-15"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Inverse Problems","Parallel Computing","Inverse Scattering","Computational Imaging","Sparse Matrix Multiplication (SpMM)","GPU","Exascale Computing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2022 Mert Hidayetoglu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/115942"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-08-01","The student, Mert Hidayetoglu, accepted the attached license on 2022-07-15 at 13:18.","The student, Mert Hidayetoglu, submitted this Dissertation for approval on 2022-07-15 at 13:19.","This Dissertation was approved for publication on 2022-07-15 at 16:19.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18325 on 2022-11-16 at 10:56:16","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Hierarchical sparse computations and communications for solving inverse problems on supercomputers with multi-GPU nodes"]}]}],"canonical_facts":{"dc:contributor":["Hwu, Wen-mei","Chew, Weng Cho","Oelze, Michael","Gropp, Bill","Kloeckner, Andreas"],"dc:creator":["Hidayetoglu, Mert"],"dc:date":["2022-08","2022-07-15"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-08-01","The student, Mert Hidayetoglu, accepted the attached license on 2022-07-15 at 13:18.","The student, Mert Hidayetoglu, submitted this Dissertation for approval on 2022-07-15 at 13:19.","This Dissertation was approved for publication on 2022-07-15 at 16:19.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18325 on 2022-11-16 at 10:56:16","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/115942"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Mert Hidayetoglu"],"dc:subject":["Inverse Problems","Parallel Computing","Inverse Scattering","Computational Imaging","Sparse Matrix Multiplication (SpMM)","GPU","Exascale Computing"],"dc:title":["Hierarchical sparse computations and communications for solving inverse problems on supercomputers with multi-GPU nodes"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:55Z"}