Y. Yan, X. Zhang and Y. Song 
``An effective and practical performance prediction model for 
parallel computing on non-dedicated heterogeneous NOW" 

Journal of Parallel and Distributed Computing, Vol. 35, No. 2, 
1996, pp. 156-172.  

Abstract
--------

Networks of Workstations (NOW) are receiving increased attention as
a viable platform for high performance parallel computations.
Heterogeneity and time-sharing are two characteristics that distinguish
the NOW systems from conventional multiprocessor/multicomputer systems
which are homogeneous and dedicated. It is important to have
a practical
model for users to predict
the execution times of large-scale parallel applications
on nondedicated heterogeneous NOW.
Another objective of this study is to provide insight into
dynamic performance of parallel computing, and into effects of program
structures and system factors on such a platform.

In this paper, we study performance predictions for parallel computing on
nondedicated heterogeneous networks of workstations.
Our approach is based on a two-level model.
On the top level a semi-deterministic task graph is used to capture the
parallel execution behavior including the variances of
communications and synchronizations.
On the bottom level, a discrete time model is used to quantify effects from
NOW systems. An iterative process is used
to determine the interactive effects between network contention and task
execution. We validate the prediction model using experiments on
a nondedicated
heterogeneous NOW. The maximal differences between
predicted results and measurement results were less than
10% in most cases, and 15% in worst cases.