An Optimized Strategy for Collective Communication in Data Parallelism
Hu Chang · Chinese Journal of Computers · 2008
Collective communication significantly influences the performance of data parallel applications.It is required often in two situations:One is array redistribution from phase to phase;another is data remapping after loop partition.Nevertheless,an important factor that influences the efficiency of collective communication is often neglected:When there is node contention and difference among message lengths during one particular communication step,a larger communication idle time may occur.In previous works,researchers can't completely avoid communication conflict and focus on some special cases.This paper is devoted to develop an universal and efficient communication scheduling strategy(CSS)concerning with the situation where array distributions are Block_Cyclic(k).Base on the proof for the recursive theorem of communication table elements,this strategy generates a communication scheduling table so that each column is a permutation of receiving node number in each communication step.And the messages with the close size are put into a communication step as near as possible.This indicates that the strategy not only avoids inter-processor contention,but it also minimizes real communication cost in each communication step.Finally,experimental results show that CSS has better performance than the general method and the implementation of MPI_Alltoallv.