2026-09-19T21:14:37Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/124226 2024-09-16 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Torrellas, Josep 2024-05 application/pdf en text Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-09-16 without embargo terms The student, Charles Block, accepted the attached license on 2024-04-01 at 17:53. The student, Charles Block, submitted this Thesis for approval on 2024-04-01 at 17:58. This Thesis was approved for publication on 2024-04-04 at 10:54. DSpace SAF Submission Ingestion Package generated from Vireo submission #20286 on 2024-09-16 at 00:33:39 A hybrid communication pattern and algorithm for distributed sparse-times-dense matrix multiplication Block, Charles 2024-04-04 High-performance Computing Distributed Algorithms Sparse Matrices Spmm Sparse matrix dense matrix multiplication (SpMM) is commonly used in applications ranging from scientific computing to graph neural networks. Typically, when SpMM is executed in a distributed platform, communication costs dominate. Such costs depend on how communication is scheduled. If it is scheduled in a sparsity-unaware manner, such as with collectives, execution is often inefficient due to unnecessary data transfers. On the other hand, if communication is scheduled in a fine-grained sparsity-aware manner, communicating only the necessary data, execution can also be inefficient due to high software overhead. We observe that individual sparse matrices often contain regions that are denser and regions that are sparser. Based on this observation, we develop a model that partitions communication into sparsity-unaware and sparsity-aware components. Leveraging the partition, we develop a new algorithm that performs collective communication for the denser regions, and fine-grained, one-sided communication for the sparser regions. We call the algorithm Two-Face. We show that Two-Face attains an average speedup of 2.11x over prior work when evaluated on a 4096-core supercomputer. Additionally, Two-Face scales well with the machine size. Text eng https://hdl.handle.net/2142/124226 Copyright 2024 Charles Block M.S. Thesis Computer Science University of Illinois at Urbana-Champaign Computer Science