论文标题
大规模多编码和高标志性稀疏矩阵的有效分布式换位
Efficient Distributed Transposition Of Large-Scale Multigraphs And High-Cardinality Sparse Matrices
论文作者
论文摘要
基于图的表示是广泛的科学问题。 图形连接通常表示为压缩稀疏行格式中的稀疏矩阵。大规模图依靠分布式存储，将不同的行子集分配给计算节点。 有效的矩阵转置是非常重要的操作，提供了反向图路径和列订购的矩阵视图。对于简单的图形模型，对此操作进行了很好的研究。然而，其对多编码和更高心电连接矩阵的分辨率是不存在的。 我们通过提供理论模型，算法细节，基于MPI的实现以及此类复杂模型的数学声音证明来推动最新的分布式换位方法。基准结果分别显示出理想和几乎理想的缩放属性，分别是完美均衡的数据集
Graph-based representations underlie a wide range of scientific problems. Graph connectivity is typically represented as a sparse matrix in the Compressed Sparse Row format. Large-scale graphs rely on distributed storage, allocating distinct subsets of rows to compute nodes. Efficient matrix transpose is an operation of high importance, providing the reverse graph pathways and a column-ordered matrix view. This operation is well studied for simple graph models. Nevertheless, its resolution for multigraphs and higher-cardinality connectivity matrices is unexistent. We advance state-of-the-art distributed transposition methods by providing a theoretical model, algorithmic details, MPI-based implementation and proof of mathematical soundness for such complex models. Benchmark results demonstrate ideal and almost ideal scaling properties for perfectly- and heterogeneously-balanced datasets, respectively
