An empirical approach to communication and performance modeling for message passing parallel applications on cluster systems

The objective of this dissertation is twofold: (1) identification and quantification of network self-similarity in communication patterns of scientific applications on time-sharing cluster systems; and (2) empirical study of application-level performance degradation by sharing resources on such cluster systems. To accomplish these objectives, a software tool, COWPANTS (Cluster of Workstations Performance ANalyzer with Task Simulator), has been developed. The tool provides a simulated yet realistic parallel processing environment from which communication patterns are collected and analyzed for self-similarity. The level of self-similarity is determined with a point estimation of the Hurst parameter using several statistical methods. In addition, we introduce a novel approach to an interval estimation of Hurst parameter using the parametric bootstrapping method. Lastly, with the simulation and sampling capability of COWPANTS, empirical performance statistics are gathered to identify application-level performance slowdown due to resource sharing. From these results we are able to suggest combinations of parallel jobs that tend to yield the least application response time delay on time-sharing non-dedicated cluster systems.;In the time-sharing non-dedicated cluster systems which allow parallel jobs to run on a set of nodes with other parallel jobs, competition for CPU and network resources results in application response time delay and in turn delayed communication traffic completion. This deferment effect is expected to result in application slowdown at the user level. It may also suggest higher levels of long-range dependence in network packet traffic. Our study empirically quantifies self-similarity and application slowdown under the resource sharing environment for parallel processing. The approach we used for the parameter's point and interval estimates is a first attempt to a rigorous, quantitative measure of self-similarity in parallel processing communication, which in turn enables more accurate performance modeling of message passing parallel programs. And the results in our comparative application response time study may provide valuable insight that could lead to better resource management systems and scheduling schemes on time-sharing cluster systems and grid systems.