A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices
A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices
复制标题
DOI：
10.1145/3218176.3218231
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
D. Richters;Michael Lass;A. Walther;Christian Plessl;T. Kuhne
中科院分区：
文献类型：
--
作者：
D. Richters;Michael Lass;A. Walther;Christian Plessl;T. Kuhne
我们提出了子矩阵方法，一个高度并行化的方法近似计算大型稀疏对称矩阵的逆p次根，这是需要在不同的科学应用。按照近似计算的思想，我们允许最终结果的不精确性，以利用输入矩阵的稀疏性，并允许大规模并行执行。对于一个n × n矩阵，该算法允许分布在n个节点的计算只有很少的通信开销。结果矩阵表现出与输入矩阵相同的稀疏模式，允许有效地重用分配的数据结构。我们评估算法的误差，它引入到计算结果，以及它的性能和可扩展性。我们表明，错误是相对有限的条件良好的矩阵，结果仍然是有价值的错误弹性的应用，如预处理，即使是病态矩阵。我们讨论的执行时间和缩放的算法在理论上，并提出了一个分布式实现的算法使用MPI和OpenMP。我们通过在由1024个CPU核心组成的高性能计算集群上运行它来展示这种实现的可扩展性，与单线程执行相比，速度提高了665倍。
We present the submatrix method, a highly parallelizable method for the approximate calculation of inverse p-th roots of large sparse symmetric matrices which are required in different scientific applications. Following the idea of Approximate Computing, we allow imprecision in the final result in order to utilize the sparsity of the input matrix and to allow massively parallel execution. For an n x n matrix, the proposed algorithm allows to distribute the calculations over n nodes with only little communication overhead. The result matrix exhibits the same sparsity pattern as the input matrix, allowing for efficient reuse of allocated data structures. We evaluate the algorithm with respect to the error that it introduces into calculated results, as well as its performance and scalability. We demonstrate that the error is relatively limited for well-conditioned matrices and that results are still valuable for error-resilient applications like preconditioning even for ill-conditioned matrices. We discuss the execution time and scaling of the algorithm on a theoretical level and present a distributed implementation of the algorithm using MPI and OpenMP. We demonstrate the scalability of this implementation by running it on a high-performance compute cluster comprised of 1024 CPU cores, showing a speedup of 665x compared to single-threaded execution.