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 indep endent parts solved in parallel by distributed computers. A simple model of a communication delay and a computation time is adopted, based on which va rious computer architectures and communication methods are analyzed. We rev iew 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.