Processor Replacement Method for Communication Immune Data Redistribution in Parallelizing HPF Compilers

摘要

Dynamic data redistribution is used to enhance algorithm performance and achieve data locality in parallel programs on distributed memory multi-computers. In this paper, we present a new technique, the Processor Replacement Method (PRM) aims to eliminate the cost of data exchange in BLOCK-CYCLIC data redistribution on symmetric matrices. Based on a processor id realignment function and a local matrix transposition scheme, inter-processor communication can be totally eliminated in runtime redistribution. A significant improvement of this approach is that dynamic data redistribution can be performed without inter-processor communication. The only cost occurred in runtime is to perform local matrix transposition. Another contribution of the present technique is that PRM can be applied in both dense and sparse applications. The theoretical analysis and experimental result congruously show that the proposed technique provides preeminent performance in runtime data redistribution.