Improved Methods for Divisible Load Distribution on k-Dimensional Meshes Using Multi-Installment

In the divisible load distribution, the classic methods on linear arrays divide the computation and communication processes into multiple time intervals in a pipelined fashion. K.Li (1998) has proposed a set of improved algorithms for linear arrays that can be generalized to k-dimensional meshes. In this paper, we first propose the algorithm M (multi-installment) that employs the multi- installment technique to improve the best algorithm Q proposed by Li. Second, we propose the algorithm S (start-up cost), which includes the computation and communication start-up costs in the design. Although the asymptotic speed-ups of our algorithms M and S derived from the closed-form solutions are the same as algorithm Q, our algorithms approach the optimal speed-ups considerably faster than algorithm Q as the number of processors increases. Finally, we combine algorithms M and S and propose the algorithm MS. Although algorithm MS has the same the asymptotic performance as algorithms Q and S, it achieves a better speed-up when the load to be processed is very large and the number of processors is fixed or when the load to be processed is fixed and the number of processors is small.