Regular expression matching is essential for many applications, such as finding patterns in text, exploring substrings in large DNA sequences, or lexical analysis. However, sequential regular expression matching may be time-prohibitive for large problem sizes. In this paper, we describe a novel algorithm for parallel regular expression matching via deterministic finite automata. Furthermore, we present our tool PaREM that accepts regular expressions and finite automata as input and automatically generates the corresponding code for our algorithm that is amenable for parallel execution on shared-memory systems. We evaluate our parallel algorithm empirically by comparing it with a commonly used algorithm for sequential regular expression matching. Experiments on a dual-socket shared-memory system with 24 physical cores show speed-ups of up to 21× for 48 threads.
Holub and Stekr @cite_10 propose an approach for parallel REM via DFA by splitting the input string in small chunks and running these chunks on each core, but due to pre-calculation of initial states for each sub input, this was not efficient for general DFA. Their algorithm runs efficiently for a specific type of DFA, so called synchronizing automata, that relies on the input automaton being k-local.
@cite_10
2141216597 1525776788 1990473086 2109227159
In this paper, we have considered the state minimization problem for Deterministic Finite Automata (DFA). An efficient parallel algorithm for solving the problem on an arbitrary CRCW PRAM has been proposed. For n number of states and k number of inputs in ? of the DFA to be minimized, the algorithm runs in O(kn log n) time and uses O(n log n) processors. We present implementations of parallel DFA run methods and find whether and under what conditions is worthy to use the parallel methods of simulation of run of finite automata. First, we introduce the parallel DFA run methods for general DFA, which are universal, but due to the dependency of simulation time on the number of states |Q | of automaton being run, they are suitable only for run of automata with the smaller number of states. Then we show that if we apply some restrictions to properties of automata being run, we can reach the linear speedup compared to the sequential simulation method. We designed methods benefiting from k -locality that allows optimum parallel run of exact and approximate pattern matching automata. Finally, we show the results of experiments conducted on two types of parallel computers (Cluster of workstations and Symmetric shared-memory multiprocessors). Conventionally, regular expression matching (REM) has been performed by sequentially comparing the regular expression (regex) to the input stream, which can be slow due to excessive backtracking (smith:acsac06). Alternatively, the regex can be converted to a deterministic finite automaton (DFA) for efficient matching, which however may require an extremely large state transition table (STT) due to exponential state explosion (meyer:swat71, yu:ancs06). We propose the segmented regex-NFA (SR-NFA) architecture, where the regex is first compiled into modular nondeterministic finite automata (NFA), then partitioned, optimized, and matched efficiently on modern multi-core processors. SR-NFA offers attack-resilient multi-gigabit per second matching throughput, does not suffer from either backtracking or state explosion, and can be rapidly constructed. For regex sets that construct a DFA with moderate state explosion, i.e., on average 200k states in the STT, the proposed SR-NFA is 367k times faster to construct and update and use 23k times less memory than the DFA approach. Running on an 8-core 2.6 GHz Opteron platform, our prototype achieves 2.2 Gbps average matching throughput for regex sets with up to 4,000 SR-NFA states per regex set. We present a parallel algorithm for the minimization of deterministic finite state automata (DFAs) and discuss its implementation on a connection machine CM-5 using data parallel and message passing models. We show that its time complexity on a p processor EREW PRAM (p spl les n) for inputs of size n is O([n log sup 2 n p]+log n log p) uniformly on almost all instances. The work done by our algorithm is thus within a factor of O(log n) of the best known sequential algorithm. The space used by our algorithm is linear in the input size. The actual resource requirements of our implementations are consistent with these estimates. Although parallel algorithms have been proposed for this problem in the past, they are not practical. We discuss the implementation details and the experimental results.