Finite state automata (FSA) are ubiquitous in computer science. Two of the most important algorithms for FSA processing are the conversion of a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA), and then the production of the unique minimal DFA for the original NFA. We exhibit a parallel disk-based algorithm that uses a cluster of 29 commodity computers to produce an intermediate DFA with almost two billion states and then continues by producing the corresponding unique minimal DFA with less than 800,000 states. The largest previous such computation in the literature was carried out on a 512-processor CM-5 supercomputer in 1996. That computation produced an intermediate DFA with 525,000 states and an unreported number of states for the corresponding minimal DFA. The work is used to provide strong experimental evidence satisfying a conjecture on a series of token passing networks. The conjecture concerns stack sortable permutations for a finite stack and a 3-buffer. The origins of this problem lie in the work on restricted permutations begun by Knuth and Tarjan in the late 1960s. The parallel disk-based computation is also compared with both a single-threaded and multi-threaded RAM-based implementation using a 16-core 128 GB large shared memory computer.
Parallel DFA minimization has been considered since the 1990s. All existing parallel algorithms are for shared memory machines, either using the CRCW PRAM model @cite_11 , the CREW pram model @cite_1 , or the EREW PRAM model @cite_26 . All of these algorithms are applicable for tightly coupled parallel machines with shared RAM and they make heavy use of random access to shared memory. In addition, @cite_26 minimized a 525,000-state DFA on the CM-5 supercomputer.
@cite_26 @cite_1 @cite_11
2141216597 2169680978 2109227159 2066015450
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 techniques to parallelize membership tests for Deterministic Finite Automata (DFAs). Our method searches arbitrary regular expressions by matching multiple bytes in parallel using speculation. We partition the input string into chunks, match chunks in parallel, and combine the matching results. Our parallel matching algorithm exploits structural DFA properties to minimize the speculative overhead. Unlike previous approaches, our speculation is failure-free, i.e., (1) sequential semantics are maintained, and (2) speed-downs are avoided altogether. On architectures with a SIMD gather-operation for indexed memory loads, our matching operation is fully vectorized. The proposed load-balancing scheme uses an off-line profiling step to determine the matching capacity of each participating processor. Based on matching capacities, DFA matches are load-balanced on inhomogeneous parallel architectures such as cloud computing environments. We evaluated our speculative DFA membership test for a representative set of benchmarks from the Perl-compatible Regular Expression (PCRE) library and the PROSITE protein database. Evaluation was conducted on a 4 CPU (40 cores) shared-memory node of the Intel Academic Program Manycore Testing Lab (Intel MTL), on the Intel AVX2 SDE simulator for 8-way fully vectorized SIMD execution, and on a 20-node (288 cores) cluster on the Amazon EC2 computing cloud. Obtained speedups are on the order of @math O 1 + | P | - 1 | Q | · ? , where @math | P | denotes the number of processors or SIMD units, @math | Q | denotes the number of DFA states, and @math 0 < ? ≤ 1 represents a statically computed DFA property. For all observed cases, we found that @math 0.02 < ? < 0.47 . Actual speedups range from 2.3 @math × to 38.8 @math × for up to 512 DFA states for PCRE, and between 1.3 @math × and 19.9 @math × for up to 1,288 DFA states for PROSITE on a 40-core MTL node. Speedups on the EC2 computing cloud range from 5.0 @math × to 65.8 @math × for PCRE, and from 5.0 @math × to 138.5 @math × for PROSITE. Speedups of our C-based DFA matcher over the Perl-based ScanProsite scan tool range from 559.3 @math × to 15079.7 @math × on a 40-core MTL node. We show the scalability of our approach for input-sizes of up to 10 GB. 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. The power of shared-memory in models of parallel computation is studied, and a novel distributed data structure that eliminates the need for shared memory without significantly increasing the run time of the parallel computation is described. More specifically, it is shown how a complete network of processors can deterministically simulate one PRAM step in O (log n (log log n ) 2 ) time when both models use n processors and the size of the PRAM's shared memory is polynomial in n . (The best previously known upper bound was the trivial O ( n )). It is established that this upper bound is nearly optimal, and it is proved that an on-line simulation of T PRAM steps by a complete network of processors requires O( T (log n log log n )) time. A simple consequence of the upper bound is that an Ultracomputer (the currently feasible general-purpose parallel machine) can simulate one step of a PRAM (the most convenient parallel model to program) in O ((log n ) 2 log log n ) steps.