Optimization of sparse matrix redistribution on multicomputers

In many scientific applications, dynamic data redistribution of sparse matrices is used to enhance the performance of SPMD programs. Since the redistribution is performed at runtime, it is critical to the performance of a parallel program. We present a method which aims to improve the efficiency of block-cyclic data redistribution of sparse matrices. The main idea of the proposed technique is first to develop closed forms for generating the vector index set of each source/destination processor. Based on the vector index set and the non-zero structure of sparse matrices, two efficient algorithms, vector2message (v2m) and message2vector (m2v) can be derived. The v2m algorithm is used to extract non-zero elements from the source matrix and packs them into messages while m2v is used to unpack messages and construct the destination matrix. A theoretical model to analyze the performance of the proposed technique is also presented in the paper. Our method is compared to a dense redistribution strategy and the histogram method on an IBM SP2 parallel machine. The experimental results show that our techniques can efficiently perform sparse matrix data redistribution.