Python Based Parallel Application of Knuth-Morris-Pratt Algorithm

Aygun S., Güneş E. O., Kouhalvandi L.

4th IEEE Workshop on Advances in Information, Electronic and Electrical Engineering (AIEEE), Vilnius, Lithuania, 10 - 12 November 2016 identifier

  • Publication Type: Conference Paper / Full Text
  • City: Vilnius
  • Country: Lithuania
  • Istanbul Technical University Affiliated: Yes


Parallel computations in multicore architectures are in big interest these days. Nearly all newly manufactured computers have multicores inside, so these architectures must be efficiently used. In this paper, we introduce the effect of parallel algorithms and multiprocessing in the Knuth-Morris-Pratt, KMP searching algorithm. Searching algorithms in computer science are used in many applications and their complexity analysis is important. More crucially, reducing the computation time heals the success of the application itself especially in the big data. Therefore, the previously proposed KMP algorithm is become parallel which runs on Python development environment in this study. Computation time and speed-up are going to be inspected at the end of the work. This work actually constructs a framework for electronics circuit design and image processing concepts in terms of parallel synthesis and multiprocessing applications for further researches. Parallel KMP is to be used in parallel image processing applications for further researches. This paper is organized by first giving the definition of the string search algorithm together with details of KMP algorithm in the sequential fashion. Then, parallelization of the algorithm is going to be presented by showing the performance details like timing and speed up.