Automata Processing: from Application Acceleration to Hardware Design

Inexact pattern matching is widely used in many fields, such as machine learning, network intrusion detection, bioinformatics, and many other applications. Inexact pattern matching is usually the most time-consuming phase in such applications, because of the complexity of inexact matching between the input string and a large number of reference patterns; thus, reducing inexact matching time is key to accelerate such applications. Automata processing is a computational model that is widely used for matching regular expressions and can be used for inexact pattern matching. However, because of the memory bottleneck due to the random memory behavior of automata processing on von-Neumann architectures, the performance is not satisfying, especially for large-scale applications, and this requires hardware acceleration. This dissertation studies the potential benefits of spatial architectures, which can process certain computation using reconfigurable processing elements.

To understand better how automata processing could be used to accelerate inexact pattern matching, we use Entity Resolution and searching for potential gRNA off-targets for CRISPR/Cas9 as two case studies. We solve the two problems using automata-based approaches, and evaluate the performance on both von-Neumann architectures (CPUs and GPUs) and spatial architectures (Micron's Automata Processor and FPGAs). We find that automata engines on spatial architectures show a clear advantage over methods on von-Neumann architectures. Therefore, we provide an automated automata processing framework using FPGAs on cloud-based platforms, and propose several novel features to further improve the performance. Finally, to reduce the high compilation overhead on FPGAs, we propose three different methods, including symbol-only reconfiguration, a new workflow using Xilinx Object file, and modular synthesis and reuse of I/O template.