riously hard because of the heterogeneity and non-dedicated system effects of the underlying system. In this paper, we focus on developing a practical performance prediction methodology for such a network of workstations.
Quite a few researchers [1,3,7,8,9,12] have contributed useful results to the performance prediction of parallel computing in dedicated homogeneous parallel environments. A two-level prediction framework has been widely used in existing prediction methods with the objective of separating the performance factors arising from the two logic levels: the application level and the system level. These prediction methods differ in the way they model the nondeterministic nature of system effects, such as interprocess communication events, contention for shared resources, and program structures. These methods fall into two classes: stochastic methods and deterministic methods. In stochastic models, nondeterminism is reflected by taking into account the variance or distribution of execution times of the synchronizing processes in the program. However, as surveyed and shown in [1], the stochastic models proposed so far have never been evaluated with regard to efficiency and accuracy for actual applications because those models require complex solution techniques, as well as the assumption of exponential task times for analytical tractability.
In deterministic models, the variance of execution times is assumed to be negligible and these execution times are represented as deterministic quantities. Intuition and conceptual simplification are the major advantages of deterministic models which make it possible to predict execution of an application program. In [1,4], the authors have demonstrated the deterministic assumption to be practical. The major limitation of deterministic models is that they fail to reflect the effect of network contention, which is an important factor affecting the execution of many applications in some network architectures, such as Ethernet. In [1,7,12], network contention is analyzed based on numerical techniques involving queuing networks or even Markov chains. These techniques may be intractable for real world applications that have complicated communication patterns. In [4], the communication overhead is deterministically decided by four parameters: network bandwidth, communication startup time, maximal bit transmission time and the number of processors. This model may not