Partitioning techniques for large-grained parallelism

A model is presented for parallel processing in loosely coupled multiprocessing environments, such as a network of computer workstations, which are amenable to large-grained parallelism. The model takes into account the overhead involved in communicating data to and from a remote processor and can be used to partition optimally a large class of computations. This class consists of computations that can be organized as a one-level tree, and are homogeneous and separable. The optimal partition can be determined for a given number of processors and, if required, the optimal number of processors to use can also be derived. The authors present experimental results that validate their model and demonstrate its effectiveness