Abstract
This paper presents an analytical performance prediction model that can be used to predict the execution time, speedup and similar performance metrics of four approximate string searching implementations running on an MPI cluster of heterogeneous workstations. The four implementations are based on master-worker model using static and dynamic allocation of the text collection. The developed performance model has been validated on a 8-cluster of heterogeneous workstations and it has been shown that the model is able to predict the execution time and other performance metrics of four parallel implementations accurately.