SEMINAR
Performance Comparison of Three Parallel String Matching Algorithms
Frederick L. Jones
Scientific Computign Program
University of Southern Mississippi
ABSTRACT
Three string matching algorithms: Brute-Force, Rabin-Karp and Knuth-Morris-Pratt will be described in both their sequential and parallel versions. Then the parallel computer system used, i.e., the USM Beowulf cluster, and the Message-Passing-Interface (MPI) will be described.
A performance comparison of the sequential versus parallel string matching algorithms will be presented. The performance comparison will note that there is a fixed cost associated with running in parallel, i.e. the addition of inter-processor data communications run time which can be 75% or more of the parallel elapsed wall clock run time.
The performance comparison of the sequential versus parallel string matching algorithms will note that due to the fixed cost of added inter-processor data communications run time, the algorithm to run in parallel should be either complicated enough or else have a large enough workload to process that the added fixed cost will be negligible.
WHERE: TEC 205
WHEN(day): Friday, April 20th, 2001
WHEN(time): 2:00 PM
EVERYBODY IS INVITED