Distributed-Memory Hierarchical Compression of Dense SPD Matrices
Distributed-Memory Hierarchical Compression of Dense SPD Matrices
复制标题
密集 SPD 矩阵的分布式内存分层压缩
DOI：
10.1109/sc.2018.00018
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
G. Biros
中科院分区：
文献类型：
--
作者：
Chenhan D. Yu;Severin Reiz;G. Biros
我们提出了一种用于对称正定（SPD）矩阵的分层压缩的分布式内存算法。我们的方法基于 GOFMM，该算法出现在 doi:10.1145/3126908.3126921 中。对于许多 SPD 矩阵，GOFMM 可以实现压缩和近似矩阵向量乘法，对于许多矩阵来说，这可以达到 N log N 次，而不是密集矩阵所需的 N<sup>2</sup> 次。但 GOFMM 仅支持共享内存并行。在本文中，我们使用消息传递接口（MPI）并将GOFMM的思想扩展到分布式内存设置。我们还提出并实现了一种异步算法以实现更快的乘法。我们在与图、神经网络和协方差算子相关的一系列 SPD 矩阵上展示了不同的使用场景。我们展示了德克萨斯高级计算中心的“Stampede 2”系统的结果。我们还与 STRUMPACK 软件包进行了比较，据我们所知，它是唯一可以并行压缩任意 SPD 矩阵的可用软件。在最大规模的运行中，我们能够在不到三分钟的时间内压缩 67M x 67M 的矩阵，并在 6,144 个英特尔“Skylake”内核上在 5 秒内执行 512 个向量的乘法。
We present a distributed memory algorithm for the hierarchical compression of symmetric positive definite (SPD) matrices. Our method is based on GOFMM, an algorithm that appeared in doi:10.1145/3126908.3126921. For many SPD matrices, GOFMM enables compression and approximate matrix-vector multiplication that for many matrices can reach N log N time—as opposed to N<sup>2</sup> required for a dense matrix. But GOFMM supports only shared memory parallelism. In this paper, we use the message passing interface (MPI) and extend the ideas of GOFMM to the distributed memory setting. We also propose and implement an asynchronous algorithm for faster multiplication. We present different usage scenarios on a selection of SPD matrices that are related to graphs, neural-networks, and covariance operators. We present results on the Texas Advanced Computing Center's “Stampede 2” system. We also compare with the STRUMPACK software package, which, to our knowledge, is the only other available software that can compress arbitrary SPD matrices in parallel. In our largest run, we were able to compress a 67M-by-67M matrix in less than three minutes and perform a multiplication with 512 vectors within 5 seconds on 6,144 Intel “Skylake” cores.