PERFORMANCE MODELLING OF COOPERATING TASKS IN PC CLUSTERS

Abstract

Although parallel processing is a promising way of increasing the performance cost efficiently, it is important to find the balance between the potential speed-up benefits and overheads due to the organization and the increased communication. Finding the optimal distribution of co-operating tasks, minimizing overheads and maximizing execution speed are often completed based on performance prediction. Complexity of prediction gradually increases with the number of links between the cooperating tasks. In this paper the efforts are focused on building up a performance model for a category of tasks running on clusters of workstations, where the result is expected at the same node the input was fed in, and a strong dependence between the partial solutions must be resolved to obtain the final result. In this domain we investigate the possibilities of prediction and minimization of execution time in the function of the cluster size. To show the utility of our model, the results are demonstrated on the common, widely used area of integer sorting. Modelling the execution time of different sorting algorithms has a strong mathematical background, which enables to easily build up formulas for the expected execution times helping to determine the optimal cluster size. As a conclusion, we show the execution times of the sorting algorithm measured on a test cluster, and compare the predicted times and the measured results.