Advisor: Michela Becchi (North Carolina State University)
Abstract: Pattern matching is a computation that maps naturally onto finite automata (FA) abstractions. There has been a substantial amount of work on accelerating FA processing on various parallel platforms. However, the advantages and disadvantages of different automata processing accelerators and the innovation space in this area are still unclear. We target this problem and propose a compiler tool-chain that automates the deployment of non-deterministic finite automata (NFAs) onto different target platforms. Using this toolchain, we perform an apples-to-apples comparison between AP, GPU- and FPGA-based NFA accelerator designs on large-scale datasets. Specifically, we observe that memory-based designs are limited by memory size and bandwidth. To address this issue, we target fixed-topology NFAs and propose a memory-efficient design that embeds the automata topology in code and stores only the transition symbols in memory. Our solution is suitable for SIMD architectures and is called SIMD_NFA. We design a compiler that automates the deployment of this design on SIMD platforms. We showcase our compiler framework on GPU and Intel platforms. Additionally, we observe that for NFAs with a grid-like fixed-topology (e.g., NFAs for Levenshtein and Hamming distance-based matching), transitions do not need to be encoded within the traversal code but can be inferred from the reference string to be matched and the knowledge of the NFA topology. Lastly, SIMD_NFA is a good fit for FPGA deployment using OpenCL-to-FPGA toolchains. We investigate the deployment of the OpenCL version of SIMD_NFA, on FPGA and explore a set of optimizations techniques to retarget SIMD_NFA to FPGA.
Thesis Canvas: pdf