Non Homogeneous Parallel Computations I. Synchronization Analysis of Parallel Algorithms
Dan Cristian Marinescu, John R. Rice · Purdue e-Pubs (Purdue University System) · 1987
We investigate the effect of non-deterministic execution times upon the "speed-up" factor in the parallel execution of algorithms.This investigation has been triggered by the observation reported in [8] concerning modeling of the Schwartz splitting algorithm for the numerical solution of partial differential equations.While the modeling of an unsynchronized execution leads to a very high processor utilization, requiring synchronization conditions results in a considerably lower level of perfonnance.In this paper we show that this effect is quite general for nonhomogeneous parallel com~ putations.We consider a set of computations that may be executed in parallel and which are related but not homogeneous.That is, there are differences in me execution times of the computations.We focus our attention on the affects of imposing synchronization upon such computations and show that this can result in a substantial penalty to the performance of parallel computations.