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

Cheng Hung Lin, Jyh Charn Liu

研究成果: 書貢獻/報告類型會議論文篇章

1 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
主出版物標題ANCS 2012 - Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems
頁面79-80
頁數2
DOIs
出版狀態已發佈 - 2012
事件8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2012 - Austin, TX, 美国
持續時間: 2012 十月 292012 十月 30

其他

其他8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2012
國家美国
城市Austin, TX
期間2012/10/292012/10/30

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture

指紋 深入研究「M-DFA (multithreaded DFA): An algorithm for reduction of state transitions and acceleration of REGEXP matching」主題。共同形成了獨特的指紋。

引用此