USEFUL PARALLELISM IN A MULTIPROCESSING ENVIRONMENT.

Abstract

In the multiprocessing domain, greater computational speedup can be achieved by dedicating increasing numbers of processors to the solution of a problem, but performance can be muted by the concomitant communication overhead. Under very general assumptions about a computation, performance with respect to the size of a task and the processor allocation for that task is analyzed. Two popular communication topologies are considered, and a distributed termination algorithm, previously presented for the first topology, is extended for use with the second topology. Formulas are derived for determining the maximum number of processors that should be allocated to a given task and the minimum task size that should be chosen to yield a given efficiency. These formulas are simple and therefore well-suited for use in compilers and operating systems to obtain an appropriate allocation of processors to computations. This technique is then applied to two popular computations: the DOALL loop, and the vector sum reduction.