Implementation of the Approximate String Matching Application on a Cluster of Heterogeneous Workstations

Published in Volume XI, 2002, p. 193-204

Author(s): Panagiotis MICHIAILIDIS

Abstract

In this paper we present a distributed approximate string matching implementation on a parallel architecture with heterogeneous workstations using MPI library. This implementation is based on the following optimal distribution strategy in order to minimise the string matching time: text collection is distributed proportional to workstation's speed. We tested this distributed implementation and drew experimental results. Using the optimal distribution method, the obtained time reduction of approximate string matching algorithm were between 73.75\% and 83.05\%, compared to the uniform allocation method. Further, we also proposed an analytical model that agrees well with our experimental measurements.