Skip to main content
Article
KPN-based parallelization of Wu–Manber algorithm on multi-core machines
Cluster Computing
  • Monther Aldwairi, Jordan University of Science and Technology
  • Abdulmughni Y. Hamzah, Jordan University of Science and Technology
  • Moath Jarrah, Jordan University of Science and Technology
ORCID Identifiers

0000-0003-1150-2404

Document Type
Article
Publication Date
6-1-2020
Abstract

© 2019, Springer Science+Business Media, LLC, part of Springer Nature. Pattern matching is the most time consuming task in many cybersecurity, bioinformatics and computational biological applications. Speeding up the pattern matching task is an essential step for the success of the aforementioned applications. Wu–Manber algorithm is one of the fastest and most widely used algorithms for multi-pattern matching. Many researchers focused on improving the performance of Wu–Manber algorithm and this work presents a novel attempt parallelize Wu–Manber and make it suitable for multi-core machines. This paper uses Kahn processing network (KPN) model to effectively parallelize data and functional tasks. KPN suggests a parallel programming model that can be utilized in today’s multi-core machines. Hence, we use the KPN model to tailor the execution of Wu–Manber algorithm by breaking down the complexity of data sharing and task processing. The data parallelization is implemented using concurrent executions of multiple KPNs. In addition, task parallelization is achieved within each executing KPN. A single KPN consists of two threads, a producer thread and a consumer thread. The proposed KPN-based parallelization achieves up to 4× speedup over the serial implementation of the algorithm. Finally, the algorithm performance scales well with increasing workloads and the speedup up remains almost constant with increasing number of attack signatures.

Publisher
Springer
Keywords
  • Data parallelism,
  • Function parallelism,
  • Intrusion detection,
  • Kahn process network,
  • Pattern matching,
  • Wu–Manber
Scopus ID
85068881258
Indexed in Scopus
Yes
Open Access
No
https://doi.org/10.1007/s10586-019-02955-9
Citation Information
Monther Aldwairi, Abdulmughni Y. Hamzah and Moath Jarrah. "KPN-based parallelization of Wu–Manber algorithm on multi-core machines" Cluster Computing Vol. 23 Iss. 2 (2020) p. 725 - 734 ISSN: <a href="https://v2.sherpa.ac.uk/id/publication/issn/1386-7857" target="_blank">1386-7857</a>
Available at: http://works.bepress.com/monther-aldwairi/44/