TY - GEN
T1 - M-DFA (multithreaded DFA)
T2 - 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2012
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
T3 - ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems
SP - 79
EP - 80
BT - ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems
Y2 - 29 October 2012 through 30 October 2012
ER -