Divisible task scheduling - Concept and verification

In this work the idea of a divisible task is presented. The divisible task is a computation which can be divided with arbitrary granularity into independent parts solved in parallel by distributed computers. A simple model of a communication delay and a computation time is adopted, based on which various computer architectures and communication methods are analyzed. We review the ways of applying the divisible task concept in the case of a linear array, star, bus, hypercube, and mesh of processors. Then, the results of an empirical justification of the analysis are presented. (C) 1999 Elsevier Science B.V. All rights reserved.