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 。

0
下载
关闭预览

相关内容

FAST:Conference on File and Storage Technologies。 Explanation:文件和存储技术会议。 Publisher:USENIX。 SIT:http://dblp.uni-trier.de/db/conf/fast/
专知会员服务
52+阅读 · 2020年11月3日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
专知会员服务
60+阅读 · 2020年3月19日
专知会员服务
109+阅读 · 2020年3月12日
【大规模数据系统,552页ppt】Large-scale Data Systems
专知会员服务
60+阅读 · 2019年12月21日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年4月18日
Arxiv
0+阅读 · 2022年4月18日
Pre-Training on Dynamic Graph Neural Networks
Arxiv
1+阅读 · 2022年4月18日
Arxiv
0+阅读 · 2022年4月17日
Warped Dynamic Linear Models for Time Series of Counts
Arxiv
19+阅读 · 2020年7月13日
已删除
Arxiv
32+阅读 · 2020年3月23日
VIP会员
相关VIP内容
专知会员服务
52+阅读 · 2020年11月3日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
专知会员服务
60+阅读 · 2020年3月19日
专知会员服务
109+阅读 · 2020年3月12日
【大规模数据系统,552页ppt】Large-scale Data Systems
专知会员服务
60+阅读 · 2019年12月21日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
相关资讯
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关论文
Arxiv
0+阅读 · 2022年4月18日
Arxiv
0+阅读 · 2022年4月18日
Pre-Training on Dynamic Graph Neural Networks
Arxiv
1+阅读 · 2022年4月18日
Arxiv
0+阅读 · 2022年4月17日
Warped Dynamic Linear Models for Time Series of Counts
Arxiv
19+阅读 · 2020年7月13日
已删除
Arxiv
32+阅读 · 2020年3月23日
相关基金
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员