KPN-based parallelization of Wu–Manber algorithm on multi-core machines

ORCID Identifiers

0000-0003-1150-2404

Document Type

Article

Source of Publication

Cluster Computing

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.

ISSN

1386-7857

Publisher

Springer

Volume

23

Issue

2

First Page

725

Last Page

734

Disciplines

Computer Sciences | Life Sciences

Keywords

Data parallelism, Function parallelism, Intrusion detection, Kahn process network, Pattern matching, Wu–Manber

Scopus ID

85068881258

Indexed in Scopus

yes

Open Access

no

Link to Full Text

Share

COinS