Limitations of Cycle Stealing for Parallel Processing on a Network of Homogeneous Workstations

The low cost and availability of clusters of workstations have lead researchers to re-explore distributed computing using independent workstations. This approach may provide better cost/performance than tightly coupled multiprocessors. In practice, this approach often utilizes wasted cycles to run parallel jobs. In this paper we address the feasibility of such a non-dedicated parallel processing environment assuming workstation processes have preemptive priority over parallel tasks. We develop an analytical model to predict parallel job response times. Our model provides insight into how significantly workstation owner interference degrades parallel program performance. It forms the foundation for efficient, feasible task partioning and scheduling in a non-dedicated network environment. A new term task ratio, which relates the parallel task demand to the mean service demand of non parallel workstation processes, is introduced. We propose that task ratio is a useful metric for determini..