AN EFFECTIVE AND PRACTICAL PERFORMANCE PREDICTION MODEL FOR PARALLEL COMPUTING ON NONDEDICATED HETEROGENEOUS NOW

Networks of workstations (NOW) are receiving increased attention as a viable platform for high performance parallel computations. Heterogene ity and time-sharing are two characteristics that distinguish the NOW systems from conventional multiprocessor/multicomputer systems which a re homogeneous and dedicated. It is important to have a practical mode l for users to predict the execution times of large-scale parallel app lications on nondedicated heterogeneous NOW. Another objective of this study is to provide insight into the dynamic performance of parallel computing and into the effects of program structures and system factor s on such a platform. In this paper, we study performance predictions for parallel computing on nondedicated heterogeneous networks of works tations. Our approach is based on a two-level model. On the top level, a semideterministic task graph is used to capture the parallel execut ion behavior including the variances of communication and synchronizat ion. On the bottom level, a discrete time model is used to quantify ef fects 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 hete rogeneous NOW. The maximum differences between predicted results and m easured results were less than 10% in most cases and 15% in the worst cases. (C) 1996 Academic Press, Inc.