© 2003 by British Computer Society
Speed-up of Parallel Processing of Divisible Loads on k-dimensional Meshes and Tori
1 Department of Computer Science, State University of New York, New Paltz, NY 12561, USA Email: lik@newpaltz.edu
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 $\beta^{1-1/2^k}$, where $\beta$ 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 $2^k\beta^{1-1/2^k}$ can be achieved.