Runtime Data Redistribution on Sparse Matrices

C.-H. Hsu (PRC)


runtime redistribution, data distribution, sparse matrices, distributed memory multi-computers


Data redistribution of sparse matrix is used to maintain locality of data access patterns and parallelism in SPMD program sin many scientific applications. Runtime redistribution of sparse matrices is a difficult problem that has recently received considerable attention. This article deals with the efficieny of runtime block-cyclic data redistribution on sparse matrix. An efficient method for generating vector index oset of source/destination processor is presented. Based on the vector index set and non-zero structure of local sparse matrix, two efficient algorithms were derived to perform the sparse matrix data redistribution. One is used toe extract non-zero elements from compressed structures and pack them into messages. The other one is used to unpack received messages and construct the destination matrix. Our implementation is compared to a dense redistribution strategy and the Histogram method based on the MPI communication library. The results presented show the efficiency of our techniques compared to the prior methods.

Important Links:

Go Back