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.
@inproceedings{block24twoface,author={Block, Charles and Gerogiannis, Gerasimos and Mendis, Charith and Azad, Ariful and Torrellas, Josep},title={Two-Face: Combining Collective and One-Sided Communication for Efficient Distributed SpMM},year={2024},isbn={9798400703850},publisher={Association for Computing Machinery},address={New York, NY, USA},url={https://doi.org/10.1145/3620665.3640427},doi={10.1145/3620665.3640427},booktitle={Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2},pages={1200–1217},numpages={18},keywords={high-performance computing, distributed algorithms, sparse matrices, SpMM},location={La Jolla, CA, USA},series={ASPLOS '24}}