Scheduling divisible loads in a three-dimensional mesh of processors

We study distributed processing of a divisible load in a three-dimensional mesh of communicating processors. The objective is to find distribution of the load among processors which guarantees minimal processing time, We describe a family of load distribution algorithms and obtain closed-form formulae for optimal load shares allocated to processors in each algorithm. Our model takes into consideration communication delays involved in moving load shares from one processor to another. In large meshes our algorithms attain speedup limit of 1 + p/rho, where p is the number of communication ports used simultaneously by each processor in data transfer and rho is the ratio of processing to communication transfer rate. We also show a matching upper bound on the speedup in this topology. (C) 1999 Elsevier Science B.V. All rights reserved.