Scheduling a divisible task in a two-dimensional toroidal mesh

In this paper, a problem of scheduling an arbitrarily divisible task is con sidered. Taking into account both communication delays and computation time we propose a scheduling method which minimizes total execution time. We fo cus on two dimensional processor networks assuming a circuit-switching rout ing mechanism. The scheduling method uses a scattering scheme proposed in P eters and Syska (IEEE Trans. Parallel Distributed Systems 7(3) (1996) 246-2 55) to distribute parts of the task to processors in a minimum time. We sho w bow to model and solve this problem with a set of algebraic equations. A solution of the latter allows one to analyze the performance of the network depending on various actual parameters of the task and the parallel machin e. Though the method is defined for a particular architecture and scatterin g scheme it can be generalized to analyze other architectures of parallel c omputer systems. (C) 1999 Elsevier Science B.V. All rights reserved.