Performance analysis of task-based algorithms on heterogeneous systems with message passing

We address the problem of performance analysis and prediction of a class of parallel applications on heterogeneous systems. Our attention is oriented towards workstation networks programmed using message passing libraries. Particularly, we consider a switched Ethernet based network and we use PVM as parallel tool, adopting the master worker model with the task farm paradigm. The simulation applied to the matrix multiplication example yields results in good agreement with the experimental ones. The model makes possible to estimate the computation and communication times and the idle time due to unbalancing, provided that the computation and communication complexity at the task level is known. In this way we are able to evaluate how the efficiency varies with the task granularity and the degree of heterogeneity of the network. The analysis can be easily modified to copy with other message passing environments.