M-DFA (multithreaded DFA): An algorithm for reduction of state transitions and acceleration of REGEXP matching

Cheng Hung Lin, Jyh Charn Liu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

This paper proposes a multi-thread based regular expression (regexp) matching algorithm, M-DFA (multithreaded DFA), for parallel computer architectures such as multi-core processors and graphic processing units (GPU). At the thread level, one thread is designated to traverse the DFA of a possible matching path until its termination, and at the task level multiple threads concurrently match each input symbol in parallel. Given a set of regexps, the total number of (DFA) state transitions in M-DFA is significantly smaller than that of its traditional DFA counterpart. The significant saving of state transitions is contributed by elimination of backtracking transitions, which commonly occur to mapping of concurrent active states in NFA to DFA and other situations. Experimental result shows that the proposed algorithm achieves significant reduction on state and state transition. In addition, the proposed algorithm running on Nvidia® GTX 480 is 35 times faster than the popular regexp library, RE2 performed on Intel Core i7 CPU.

Original languageEnglish
Title of host publicationANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems
Pages79-80
Number of pages2
DOIs
Publication statusPublished - 2012
Event8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2012 - Austin, TX, United States
Duration: 2012 Oct 292012 Oct 30

Other

Other8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2012
CountryUnited States
CityAustin, TX
Period12/10/2912/10/30

Fingerprint

Computer architecture
Program processors
Graphics processing unit

Keywords

  • graphics processing units
  • regular expression matching

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture

Cite this

Lin, C. H., & Liu, J. C. (2012). M-DFA (multithreaded DFA): An algorithm for reduction of state transitions and acceleration of REGEXP matching. In ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems (pp. 79-80) https://doi.org/10.1145/2396556.2396572

M-DFA (multithreaded DFA) : An algorithm for reduction of state transitions and acceleration of REGEXP matching. / Lin, Cheng Hung; Liu, Jyh Charn.

ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. 2012. p. 79-80.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lin, CH & Liu, JC 2012, M-DFA (multithreaded DFA): An algorithm for reduction of state transitions and acceleration of REGEXP matching. in ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. pp. 79-80, 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2012, Austin, TX, United States, 12/10/29. https://doi.org/10.1145/2396556.2396572
Lin CH, Liu JC. M-DFA (multithreaded DFA): An algorithm for reduction of state transitions and acceleration of REGEXP matching. In ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. 2012. p. 79-80 https://doi.org/10.1145/2396556.2396572
Lin, Cheng Hung ; Liu, Jyh Charn. / M-DFA (multithreaded DFA) : An algorithm for reduction of state transitions and acceleration of REGEXP matching. ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. 2012. pp. 79-80
@inproceedings{71e31ca79c104fe0973fe14b13f3f913,
title = "M-DFA (multithreaded DFA): An algorithm for reduction of state transitions and acceleration of REGEXP matching",
abstract = "This paper proposes a multi-thread based regular expression (regexp) matching algorithm, M-DFA (multithreaded DFA), for parallel computer architectures such as multi-core processors and graphic processing units (GPU). At the thread level, one thread is designated to traverse the DFA of a possible matching path until its termination, and at the task level multiple threads concurrently match each input symbol in parallel. Given a set of regexps, the total number of (DFA) state transitions in M-DFA is significantly smaller than that of its traditional DFA counterpart. The significant saving of state transitions is contributed by elimination of backtracking transitions, which commonly occur to mapping of concurrent active states in NFA to DFA and other situations. Experimental result shows that the proposed algorithm achieves significant reduction on state and state transition. In addition, the proposed algorithm running on Nvidia{\circledR} GTX 480 is 35 times faster than the popular regexp library, RE2 performed on Intel Core i7 CPU.",
keywords = "graphics processing units, regular expression matching",
author = "Lin, {Cheng Hung} and Liu, {Jyh Charn}",
year = "2012",
doi = "10.1145/2396556.2396572",
language = "English",
isbn = "9781450316859",
pages = "79--80",
booktitle = "ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems",

}

TY - GEN

T1 - M-DFA (multithreaded DFA)

T2 - An algorithm for reduction of state transitions and acceleration of REGEXP matching

AU - Lin, Cheng Hung

AU - Liu, Jyh Charn

PY - 2012

Y1 - 2012

N2 - This paper proposes a multi-thread based regular expression (regexp) matching algorithm, M-DFA (multithreaded DFA), for parallel computer architectures such as multi-core processors and graphic processing units (GPU). At the thread level, one thread is designated to traverse the DFA of a possible matching path until its termination, and at the task level multiple threads concurrently match each input symbol in parallel. Given a set of regexps, the total number of (DFA) state transitions in M-DFA is significantly smaller than that of its traditional DFA counterpart. The significant saving of state transitions is contributed by elimination of backtracking transitions, which commonly occur to mapping of concurrent active states in NFA to DFA and other situations. Experimental result shows that the proposed algorithm achieves significant reduction on state and state transition. In addition, the proposed algorithm running on Nvidia® GTX 480 is 35 times faster than the popular regexp library, RE2 performed on Intel Core i7 CPU.

AB - This paper proposes a multi-thread based regular expression (regexp) matching algorithm, M-DFA (multithreaded DFA), for parallel computer architectures such as multi-core processors and graphic processing units (GPU). At the thread level, one thread is designated to traverse the DFA of a possible matching path until its termination, and at the task level multiple threads concurrently match each input symbol in parallel. Given a set of regexps, the total number of (DFA) state transitions in M-DFA is significantly smaller than that of its traditional DFA counterpart. The significant saving of state transitions is contributed by elimination of backtracking transitions, which commonly occur to mapping of concurrent active states in NFA to DFA and other situations. Experimental result shows that the proposed algorithm achieves significant reduction on state and state transition. In addition, the proposed algorithm running on Nvidia® GTX 480 is 35 times faster than the popular regexp library, RE2 performed on Intel Core i7 CPU.

KW - graphics processing units

KW - regular expression matching

UR - http://www.scopus.com/inward/record.url?scp=84871345827&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84871345827&partnerID=8YFLogxK

U2 - 10.1145/2396556.2396572

DO - 10.1145/2396556.2396572

M3 - Conference contribution

AN - SCOPUS:84871345827

SN - 9781450316859

SP - 79

EP - 80

BT - ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems

ER -