Generalized Performance Model for Flexible Approximate String Matching on a Distributed

This paper proposes a generalized and practical parallel algorithm for flexible approximate string matching which is executed for several kinds of clusters such as homogeneous cluster and heterogeneous cluster. This parallel algorithm is based on the master- worker paradigm and it implements different partitioning schemes such as static and dynamic load balancing cooperating with different data allocation techniques such as the allocation of texts and allocation of text pointers. Furthermore, the parallel algorithm is analyzed experimentally using the Message Passing Interface (MPI) library for different strategies of load balancing and data allocation onto two kinds of clusters. Further, we propose a general performance model that can be used to predict the performance of the parallel flexible approximate string matching algorithm for both types of clusters. The theoretical performance model has been validated against experimental results and it is shown that the model is able to predict the parallel performance accurately