1Parallel Implementation of Exact Two Dimensional Pattern Matching Algorithms using MPI and

Abstract—The need for processing power is constantly increas-ing as more processing-demanding and time-critical applications appear. Parallel processing has emerged as an efficient and cost-effective solution, since low-end workstations and multiprocessors are cheaply available in the commodity market. In this paper, experimental results are presented on the parallel processing of the Naive, Karp and Rabin, Zhu and Takaoka, Baeza-Yates and Regnier and the Baker and Bird exact two dimensional on-line pattern matching algorithms. The algorithms are implemented using MPI and OpenMP, the two most widely used APIs for distributed and shared memory parallelization respectively. The performance of the parallel implementations is evaluated when used on a homogeneous cluster of workstations and a multicore processor. Index Terms—pattern matching, algorithms, parallelization, shared memory, distributed memory, OpenMP, MP