1.5D PARALLEL SPARSE MATRIX-VECTOR MULTIPLY

doi:10.1137/16M1105591

2018-01-01

Cevdet Aykanat

Bora Uçar

DOI：10.1137/16M1105591

原文链接

查看原文

摘要

En 中文

There are three common parallel sparse matrix-vector multiply algorithms: 1D row-parallel, 1D column-parallel, and 2D row-column-parallel. The 1D parallel algorithms offer the advantage of having only one communication phase. On the other hand, the 2D parallel algorithm is more scalable, but it suffers from two communication phases. Here, we introduce a novel concept of heterogeneous messages where a heterogeneous message may contain both input-vector entries and partially computed output-vector entries. This concept not only leads to a decreased number of messages but also enables fusing the input- and output-communication phases into a single phase. These findings are exploited to propose a 1.5D parallel sparse matrix-vector multiply algorithm which is called local row-column-parallel. This proposed algorithm requires a constrained fine-grain partitioning in which each fine-grain task is assigned to the processor that contains either its input vector entry, its output-vector entry, or both. We propose two methods to carry out the constrained fine-grain partitioning. We conduct our experiments on a large set of test matrices to evaluate the partitioning qualities and partitioning times of these proposed 1.5D methods.

Keyword:

sparse matrix partitioning

parallel sparse matrix-vector multiplication

directed hypergraph model

bipartite vertex cover

combinatorial scientific computing