An Efficient Vector Transfer for Sparse Matrix-Vector Multiplication on Distributed Memory Systems

概要

論文の詳細を見る
This paper proposes an efficient algorithm to exchange fragments of a vector distributed among processes which repeatedly perform sparse matrix-vector multiplication in parallel and in a block-decomposed manner. The idea to reduce the communication cost for the exchange is to combine non-contiguous fragments of a vector residing in a process and required by another process to multiply the fragments by the submatrix in the receiver process. That is, the sender may send fragments and gaps between them forming a larger fragment, rather than sending each fragment individually or packing fragments into a single vector before sending. The key feature of our algorithm is to find the optimum assortment of combining, individual sending and packing based on dynamic programming from given fragments and non-linear cost functions. Our preliminary evaluation with artificially generated sparse matrices shows the optimum assortment is up to 1.5 times as fast as simple packing.
一般社団法人情報処理学会の論文
2010-02-15