Sparse matrix multiplication (SpGEMM) is a fundamental kernel used in many diverse application areas, both numerical and discrete. Recently, SpGEMM has received growing attention regarding implementations for specific (parallel) architectures. Yet, this concerns only the static problem, where both input matrices do not change. In many applications, however, matrices (or their corresponding graphs) change over time. Although recomputing from scratch is very expensive, we are not aware of any dynamic SpGEMM algorithms in the literature. In this paper, we thus propose a batch-dynamic algorithm for MPI-based parallel computing. Building on top of a distributed graph/matrix data structure that allows for fast updates, our dynamic SpGEMM reduces the communication volume significantly. It does so by exploiting that updates change far fewer matrix entries than there are non-zeros in the input operands. Our experiments with popular benchmark graphs show that our approach pays off. For batches of insertions or removals of matrix entries, our dynamic SpGEMM is substantially faster than the static state-of-the-art algorithm in CombBLAS 2.0 and in CTF.
翻译:松散的矩阵乘法( SpGEMM) 是许多不同应用领域( 包括数字和离散) 使用的基本内核 。 最近, SpGEMM 在特定( 平行) 结构的实施方面越来越受到越来越多的关注 。 然而, 这只涉及静态问题, 因为两种输入矩阵都不会改变 。 但是在许多应用中, 矩阵( 或相应的图表) 随时间变化 。 尽管从零开始的重新计算非常昂贵, 我们不知道文献中存在任何动态 SpGEM 算法 。 因此, 在本文中, 我们为基于 MPI 的平行计算提出了批量动态算法 。 在分布式图/ 矩阵数据结构之上建起一个能够快速更新的配置图/ 矩阵数据结构, 我们的动态 SpGEMM 显著地减少了通信量 。 这样做的办法是, 利用它来更新矩阵条目的变化远远少于输入操作操作中的非零。 我们用流行的基准图形实验显示我们的方法是值得的 。 对于输入或清除矩阵条目的分批量, 我们的 SpGEMMMMM 大大快于 COMLAS 2. 0 和 CTF 。