Predicting the performance of a parallel heuristic solution for the Steiner Tree Problem

Abstract

Nowadays, there is an increasing number of computer intensive applications, which exceed the capacity of a standard stand-alone computer. An alternative is to parallelize the application and run it in a cluster; there has been much work in this sense, specially in platforms and tools to build a cluster from commodity components, and to develop parallel applications. One of the problems that subsist is the one faced by the analyst when designing a new application in this environment. He must solve the trade-off between the cost of building the cluster, and the application's running time; if he under-dimensions the cluster, the running time might be too long; if he over-dimensions it, the cost might not be acceptable. This work presents an example of how analytical performance models can be applied in this context. In particular, we develop a parallel implementation of a combinatorial optimization heuristic for solving the Steiner Tree Problem, and a Petri net model which can be used to predict the running time of the application on a cluster of PCs, on the basis of measurements on stand-alone equipment. The model is validated experimentally, showing that it adequately predicts optimistic and pessimistic bounds for the measured running time.