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, Litvanya, 10 - 12 Kasım 2016 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Basıldığı Şehir: Vilnius
  • Basıldığı Ülke: Litvanya
  • İstanbul Teknik Üniversitesi Adresli: Evet

Özet

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.