http://swrc.ontoware.org/ontology#Article
Simultaneous Finite Automata : An Efficient Data-Parallel Model for Regular Expression Matching
en
Sin'ya Ryoma
Matsuzaki Kiminori
Sassa Masataka
Automata play important roles in wide area of computing and the growth of multicores calls for their efficient parallel implementation. Though it is known in theory that we can perform the computation of a finite automaton in parallel by simulating transitions, its implementation has a large overhead due to the simulation. In this paper we propose a new automaton called simultaneous finite automaton (SFA) for efficient parallel computation of an automaton. The key idea is to extend an automaton so that it involves the simulation of transitions. Since an SFA itself has a good property of parallelism, we can develop easily a parallel implementation without overheads. We have implemented a regular expression matcher based on SFA, and it has achieved over 10-times speedups on an environment with dual hexa-core CPUs in a typical case.
Parallel Processing (ICPP), 2013 42nd International Conference on
220-229
2013
10.1109/ICPP.2013.31
IEEE, Ryoma Sinya ; Kiminori Matsuzaki, Masataka Sassa, Parallel Processing (ICPP), 2013 42nd International Conference on, 2013, p220-229
IEEE