Speed-up of Parallel Processing of Divisible Loads on k-dimensional Meshes and Tori

A divisible load distribution algorithm on k-dimensional meshes and tori is proposed and analyzed. It is found that by using our algorithm, the speed-up of parallel processing of a divisible load on k-dimensional meshes and tori is bounded from above by a quantity independent of network size, due to communication overhead and limited network connectivity. In particular, it is shown that for k-dimensional meshes and tori, as the network size becomes large, the asymptotic speed-up of processing divisible loads with corner initial processors is approximately β1-1/2k, where β is the ratio of the time for computing a unit load to the time for communicating a unit load. It is also proved that by choosing interior initial processors, an asymptotic speed-up of 2k β1-1/2k can be achieved.