Multiplying two sparse matrices (spgemm) is a common computational primitive used in many areas including graph algorithms, bioinformatics, algebraic multigrid solvers, and randomized sketching. distributed-memory par...
详细信息
ISBN:
(数字)9798350352917
ISBN:
(纸本)9798350352924;9798350352917
Multiplying two sparse matrices (spgemm) is a common computational primitive used in many areas including graph algorithms, bioinformatics, algebraic multigrid solvers, and randomized sketching. distributed-memory parallel algorithms for spgemm have mainly focused on sparsity-oblivious approaches that use 2d and 3d partitioning. sparsity-aware1dalgorithms can theoretically reduce communication by not fetching nonzeros of the sparse matrices that do not participate in the multiplication. Here, we present a distributed-memory 1dspgemmalgorithm and implementation. It uses MPI RdMA operations to mitigate the cost of packing/unpacking submatrices for communication, and it uses a block fetching strategy to avoid excessive fine-grained messaging. Our results show that our 1d implementation outperforms state-of-the-art 2d and 3d implementations within CombBLAS for many configurations, inputs, and use cases, while remaining conceptually simpler.
暂无评论